root/opal/mca/allocator/bucket/allocator_bucket_alloc.c

DEFINITIONS

1. mca_allocator_bucket_init
2. mca_allocator_bucket_alloc
3. mca_allocator_bucket_alloc_align
4. mca_allocator_bucket_realloc
5. mca_allocator_bucket_free
6. mca_allocator_bucket_cleanup

   1 /*
   2  * Copyright (c) 2004-2005 The Trustees of Indiana University and Indiana
   3  *                         University Research and Technology
   4  *                         Corporation.  All rights reserved.
   5  * Copyright (c) 2004-2005 The University of Tennessee and The University
   6  *                         of Tennessee Research Foundation.  All rights
   7  *                         reserved.
   8  * Copyright (c) 2004-2005 High Performance Computing Center Stuttgart,
   9  *                         University of Stuttgart.  All rights reserved.
  10  * Copyright (c) 2004-2005 The Regents of the University of California.
  11  *                         All rights reserved.
  12  * Copyright (c) 2007      IBM Corp.,  All rights reserved.
  13  * $COPYRIGHT$
  14  *
  15  * Additional copyrights may follow
  16  *
  17  * $HEADER$
  18  */
  19 
  20 #include "opal_config.h"
  21 #include "opal/constants.h"
  22 #include "opal/mca/allocator/bucket/allocator_bucket_alloc.h"
  23 /**
  24   * The define controls the size in bytes of the 1st bucket and hence every one
  25   * afterwards.
  26   */
  27 #define MCA_ALLOCATOR_BUCKET_1_SIZE 8
  28 /**
  29   * This is the number of left bit shifts from 1 needed to get to the number of
  30   * bytes in the initial memory buckets
  31   */
  32 #define MCA_ALLOCATOR_BUCKET_1_BITSHIFTS 3
  33 
  34  /*
  35    * Initializes the mca_allocator_bucket_options_t data structure for the passed
  36    * parameters.
  37    */
  38 mca_allocator_bucket_t * mca_allocator_bucket_init(
  39     mca_allocator_base_module_t * mem,
  40     int num_buckets,
  41     mca_allocator_base_component_segment_alloc_fn_t get_mem_funct,
  42     mca_allocator_base_component_segment_free_fn_t free_mem_funct)
  43 {
  44     mca_allocator_bucket_t * mem_options = (mca_allocator_bucket_t *) mem;
  45     int i;
  46     size_t size;
  47     /* if a bad value is used for the number of buckets, default to 30 */
  48     if(num_buckets <= 0) {
  49         num_buckets = 30;
  50     }
  51     /* initialize the array of buckets */
  52     size = sizeof(mca_allocator_bucket_bucket_t) * num_buckets;
  53     mem_options->buckets = (mca_allocator_bucket_bucket_t*) malloc(size);
  54     if(NULL == mem_options->buckets) {
  55         return(NULL);
  56     }
  57     for(i = 0; i < num_buckets; i++) {
  58         mem_options->buckets[i].free_chunk = NULL;
  59         mem_options->buckets[i].segment_head = NULL;
  60         OBJ_CONSTRUCT(&(mem_options->buckets[i].lock), opal_mutex_t);
  61     }
  62     mem_options->num_buckets = num_buckets;
  63     mem_options->get_mem_fn = get_mem_funct;
  64     mem_options->free_mem_fn = free_mem_funct;
  65     return(mem_options);
  66 }
  67 
  68 /*
  69    * Accepts a request for memory in a specific region defined by the
  70    * mca_allocator_bucket_options_t struct and returns a pointer to memory in that
  71    * region or NULL if there was an error
  72    *
  73    */
  74 void * mca_allocator_bucket_alloc(mca_allocator_base_module_t * mem,
  75                                   size_t size)
  76 {
  77     mca_allocator_bucket_t * mem_options = (mca_allocator_bucket_t *) mem;
  78     /* initialize for the later bit shifts */
  79     int bucket_num = 0;
  80     size_t bucket_size = MCA_ALLOCATOR_BUCKET_1_SIZE;
  81     size_t allocated_size;
  82     mca_allocator_bucket_chunk_header_t * chunk;
  83     mca_allocator_bucket_chunk_header_t * first_chunk;
  84     mca_allocator_bucket_segment_head_t * segment_header;
  85     /* add the size of the header into the amount we need to request */
  86     size += sizeof(mca_allocator_bucket_chunk_header_t);
  87 
  88     /* figure out which bucket it will come from. */
  89     while(size > bucket_size) {
  90         bucket_num++;
  91         bucket_size <<= 1;
  92     }
  93 
  94     /* now that we know what bucket it will come from, we must get the lock */
  95     OPAL_THREAD_LOCK(&(mem_options->buckets[bucket_num].lock));
  96     /* see if there is already a free chunk */
  97     if(NULL != mem_options->buckets[bucket_num].free_chunk) {
  98         chunk = mem_options->buckets[bucket_num].free_chunk;
  99         mem_options->buckets[bucket_num].free_chunk = chunk->u.next_free;
 100         chunk->u.bucket = bucket_num;
 101         /* go past the header */
 102         chunk += 1;
 103         /*release the lock */
 104         OPAL_THREAD_UNLOCK(&(mem_options->buckets[bucket_num].lock));
 105         return((void *) chunk);
 106     }
 107     /* figure out the size of bucket we need */
 108     allocated_size = bucket_size;
 109     /* we have to add in the size of the segment header into the
 110      * amount we need to request */
 111     allocated_size += sizeof(mca_allocator_bucket_segment_head_t);
 112     /* attempt to get the memory */
 113     segment_header = (mca_allocator_bucket_segment_head_t *)
 114                    mem_options->get_mem_fn(mem_options->super.alc_context, &allocated_size);
 115     if(NULL == segment_header) {
 116         /* release the lock */
 117         OPAL_THREAD_UNLOCK(&(mem_options->buckets[bucket_num].lock));
 118         return(NULL);
 119     }
 120     /* if were allocated more memory then we actually need, then we will try to
 121      * break it up into multiple chunks in the current bucket */
 122     allocated_size -= (sizeof(mca_allocator_bucket_segment_head_t) + bucket_size);
 123     chunk = first_chunk = segment_header->first_chunk =
 124                   (mca_allocator_bucket_chunk_header_t *) (segment_header + 1);
 125     /* add the segment into the segment list */
 126     segment_header->next_segment = mem_options->buckets[bucket_num].segment_head;
 127     mem_options->buckets[bucket_num].segment_head = segment_header;
 128     if(allocated_size >= bucket_size) {
 129         mem_options->buckets[bucket_num].free_chunk =
 130                         (mca_allocator_bucket_chunk_header_t *) ((char *) chunk + bucket_size);
 131         chunk->next_in_segment = (mca_allocator_bucket_chunk_header_t *)
 132                                    ((char *)chunk + bucket_size);
 133         while(allocated_size >= bucket_size) {
 134             chunk = (mca_allocator_bucket_chunk_header_t *) ((char *) chunk + bucket_size);
 135             chunk->u.next_free = (mca_allocator_bucket_chunk_header_t *)
 136                                  ((char *) chunk + bucket_size);
 137             chunk->next_in_segment = chunk->u.next_free;
 138             allocated_size -= bucket_size;
 139         }
 140         chunk->next_in_segment = first_chunk;
 141         chunk->u.next_free = NULL;
 142     } else {
 143         first_chunk->next_in_segment = first_chunk;
 144     }
 145     first_chunk->u.bucket = bucket_num;
 146     OPAL_THREAD_UNLOCK(&(mem_options->buckets[bucket_num].lock));
 147     /* return the memory moved past the header */
 148     return((void *) (first_chunk + 1));
 149 }
 150 
 151 /*
 152   * allocates an aligned region of memory
 153   */
 154 void * mca_allocator_bucket_alloc_align(mca_allocator_base_module_t * mem,
 155                                         size_t size, size_t alignment)
 156 {
 157     mca_allocator_bucket_t * mem_options = (mca_allocator_bucket_t *) mem;
 158     int bucket_num = 1;
 159     void * ptr;
 160     size_t aligned_max_size, bucket_size;
 161     size_t alignment_off, allocated_size;
 162     mca_allocator_bucket_chunk_header_t * chunk;
 163     mca_allocator_bucket_chunk_header_t * first_chunk;
 164     mca_allocator_bucket_segment_head_t * segment_header;
 165     char * aligned_memory;
 166 
 167     /* since we do not have a way to get pre aligned memory, we need to request
 168      * a chunk then return an aligned spot in it. In the worst case we need
 169      * the requested size plus the alignment and the header size */
 170     aligned_max_size = size + alignment + sizeof(mca_allocator_bucket_chunk_header_t)
 171                        + sizeof(mca_allocator_bucket_segment_head_t);
 172     bucket_size = size + sizeof(mca_allocator_bucket_chunk_header_t);
 173     allocated_size = aligned_max_size;
 174     /* get some memory */
 175     ptr = mem_options->get_mem_fn(mem_options->super.alc_context, &allocated_size);
 176     if(NULL == ptr) {
 177         return(NULL);
 178     }
 179     /* the first part of the memory is the segment header */
 180     segment_header = (mca_allocator_bucket_segment_head_t *) ptr;
 181     /* we temporarily define the first chunk to be right after the segment_header */
 182     first_chunk = (mca_allocator_bucket_chunk_header_t *) (segment_header + 1);
 183 
 184     /* we want to align the memory right after the header, so we go past the header */
 185     aligned_memory = (char *) (first_chunk + 1);
 186     /* figure out how much the alignment is off by */
 187     alignment_off = ((size_t)  aligned_memory) % alignment;
 188     aligned_memory += (alignment - alignment_off);
 189     /* we now have an aligned piece of memory. Now we have to put the chunk
 190      * header right before the aligned memory                           */
 191     first_chunk = (mca_allocator_bucket_chunk_header_t *) aligned_memory - 1;
 192     while(bucket_size > MCA_ALLOCATOR_BUCKET_1_SIZE) {
 193         bucket_size >>= 1;
 194         bucket_num++;
 195     }
 196     bucket_size = 1;
 197     bucket_size <<= MCA_ALLOCATOR_BUCKET_1_BITSHIFTS + bucket_num;
 198 
 199     /* if were allocated more memory then we actually need, then we will try to
 200      * break it up into multiple chunks in the current bucket */
 201     allocated_size -= aligned_max_size;
 202     chunk = segment_header->first_chunk = first_chunk;
 203     /* we now need to get a lock on the bucket */
 204     OPAL_THREAD_LOCK(&(mem_options->buckets[bucket_num].lock));
 205     /* add the segment into the segment list */
 206     segment_header->next_segment = mem_options->buckets[bucket_num].segment_head;
 207     mem_options->buckets[bucket_num].segment_head = segment_header;
 208     if(allocated_size >= bucket_size) {
 209         mem_options->buckets[bucket_num].free_chunk =
 210                         (mca_allocator_bucket_chunk_header_t *) ((char *) chunk + bucket_size);
 211         chunk->next_in_segment = (mca_allocator_bucket_chunk_header_t *)
 212                                    ((char *)chunk + bucket_size);
 213         while(allocated_size >= bucket_size) {
 214             chunk = (mca_allocator_bucket_chunk_header_t *) ((char *) chunk + bucket_size);
 215             chunk->u.next_free = (mca_allocator_bucket_chunk_header_t *)
 216                                  ((char *) chunk + bucket_size);
 217             chunk->next_in_segment = chunk->u.next_free;
 218             allocated_size -= bucket_size;
 219         }
 220         chunk->next_in_segment = first_chunk;
 221         chunk->u.next_free = NULL;
 222     } else {
 223         first_chunk->next_in_segment = first_chunk;
 224     }
 225     first_chunk->u.bucket = bucket_num;
 226     OPAL_THREAD_UNLOCK(&(mem_options->buckets[bucket_num].lock));
 227     /* return the aligned memory */
 228     return((void *) (aligned_memory));
 229 }
 230 
 231 /*
 232   * function to reallocate the segment of memory
 233   */
 234 void * mca_allocator_bucket_realloc(mca_allocator_base_module_t * mem,
 235                                     void * ptr, size_t size)
 236 {
 237     mca_allocator_bucket_t * mem_options = (mca_allocator_bucket_t *) mem;
 238     /* initialize for later bit shifts */
 239     size_t bucket_size = 1;
 240     int bucket_num;
 241     void * ret_ptr;
 242     /* get the header of the chunk */
 243     mca_allocator_bucket_chunk_header_t * chunk = (mca_allocator_bucket_chunk_header_t *) ptr - 1;
 244     bucket_num = chunk->u.bucket;
 245 
 246     bucket_size <<= (bucket_num + MCA_ALLOCATOR_BUCKET_1_BITSHIFTS);
 247     /* since the header area is not available to the user, we need to
 248      * subtract off the header size                 */
 249     bucket_size -= sizeof(mca_allocator_bucket_chunk_header_t);
 250     /* if the requested size is less than or equal to what they ask for,
 251      * just give them back what they passed in      */
 252     if(size <= bucket_size) {
 253         return(ptr);
 254     }
 255     /* we need a new space in memory, so let's get it */
 256     ret_ptr = mca_allocator_bucket_alloc((mca_allocator_base_module_t *) mem_options, size);
 257     if(NULL == ret_ptr) {
 258         /* we were unable to get a larger area of memory */
 259         return(NULL);
 260     }
 261     /* copy what they have in memory to the new spot */
 262     memcpy(ret_ptr, ptr, bucket_size);
 263     /* free the old area in memory */
 264     mca_allocator_bucket_free((mca_allocator_base_module_t *) mem_options, ptr);
 265     return(ret_ptr);
 266 }
 267 
 268 
 269 /*
 270    * Frees the passed region of memory
 271    *
 272    */
 273 void mca_allocator_bucket_free(mca_allocator_base_module_t * mem, void * ptr)
 274 {
 275     mca_allocator_bucket_t * mem_options = (mca_allocator_bucket_t *) mem;
 276     mca_allocator_bucket_chunk_header_t * chunk  = (mca_allocator_bucket_chunk_header_t *) ptr - 1;
 277     int bucket_num = chunk->u.bucket;
 278     OPAL_THREAD_LOCK(&(mem_options->buckets[bucket_num].lock));
 279     chunk->u.next_free = mem_options->buckets[bucket_num].free_chunk;
 280     mem_options->buckets[bucket_num].free_chunk = chunk;
 281     OPAL_THREAD_UNLOCK(&(mem_options->buckets[bucket_num].lock));
 282 }
 283 
 284 /*
 285    * Frees all the memory from all the buckets back to the system. Note that
 286    * this function only frees memory that was previously freed with
 287    * mca_allocator_bucket_free().
 288    *
 289    */
 290 int mca_allocator_bucket_cleanup(mca_allocator_base_module_t * mem)
 291 {
 292     mca_allocator_bucket_t * mem_options = (mca_allocator_bucket_t *) mem;
 293     int i;
 294     mca_allocator_bucket_chunk_header_t * next_chunk;
 295     mca_allocator_bucket_chunk_header_t * chunk;
 296     mca_allocator_bucket_chunk_header_t * first_chunk;
 297     mca_allocator_bucket_segment_head_t ** segment_header;
 298     mca_allocator_bucket_segment_head_t * segment;
 299     bool empty = true;
 300 
 301     for(i = 0; i < mem_options->num_buckets; i++) {
 302         OPAL_THREAD_LOCK(&(mem_options->buckets[i].lock));
 303         segment_header = &(mem_options->buckets[i].segment_head);
 304         if( NULL == (*segment_header) ) {
 305             OPAL_THREAD_UNLOCK(&(mem_options->buckets[i].lock));
 306             continue;
 307         }
 308         /* first we suppose the execution is correct and all chunks
 309          * have been correctly released. Therefore, if we make sure
 310          * all segments only contain free items then we can release
 311          * everything in one go.
 312          */
 313         empty = true;
 314         segment = mem_options->buckets[i].segment_head;
 315         while( (true == empty) && (NULL != segment) ) {
 316             first_chunk = segment->first_chunk;
 317             chunk = first_chunk;
 318             /* determine if the segment is free */
 319             do {
 320                 if(chunk->u.bucket == i) {
 321                     empty = false;
 322                     break;
 323                 }
 324                 chunk = chunk->next_in_segment;
 325             } while(chunk != first_chunk);
 326             /* go to next segment */
 327             segment = segment->next_segment;
 328         }
 329         if( true == empty ) {  /* all segments ready for release */
 330             mca_allocator_bucket_segment_head_t* next_segment;
 331             segment = mem_options->buckets[i].segment_head;
 332             while( NULL != segment ) {
 333                 next_segment = segment->next_segment;
 334                 /* free the memory */
 335                 if(mem_options->free_mem_fn)
 336                     mem_options->free_mem_fn(mem->alc_context, segment);
 337                 segment = next_segment;
 338             }
 339             mem_options->buckets[i].free_chunk = NULL;
 340             mem_options->buckets[i].segment_head = NULL;
 341         } else {
 342             /* traverse the list of segment headers until we hit NULL */
 343             while(NULL != *segment_header) {
 344                 first_chunk = (*segment_header)->first_chunk;
 345                 chunk = first_chunk;
 346                 empty = true;
 347                 /* determine if the segment is free */
 348                 do {
 349                     if(chunk->u.bucket == i) {
 350                         empty = false;
 351                     }
 352                     chunk = chunk->next_in_segment;
 353                 } while(empty && (chunk != first_chunk));
 354                 if(empty) {
 355                     chunk = first_chunk;
 356                     /* remove the chunks from the free list */
 357                     do {
 358                         if(mem_options->buckets[i].free_chunk == chunk) {
 359                             mem_options->buckets[i].free_chunk = chunk->u.next_free;
 360                         } else {
 361                             next_chunk = mem_options->buckets[i].free_chunk;
 362                             while(next_chunk->u.next_free != chunk) {
 363                                 next_chunk = next_chunk->u.next_free;
 364                             }
 365                             next_chunk->u.next_free = chunk->u.next_free;
 366                         }
 367                     } while((chunk = chunk->next_in_segment) != first_chunk);
 368                     /* set the segment list to point to the next segment */
 369                     segment = *segment_header;
 370                     *segment_header = segment->next_segment;
 371                     /* free the memory */
 372                     if(mem_options->free_mem_fn)
 373                         mem_options->free_mem_fn(mem->alc_context, segment);
 374                 } else {
 375                     /* go to next segment */
 376                     segment_header = &((*segment_header)->next_segment);
 377                 }
 378             }
 379         }
 380         /* relese the lock on the bucket */
 381         OPAL_THREAD_UNLOCK(&(mem_options->buckets[i].lock));
 382     }
 383     return(OPAL_SUCCESS);
 384 }