src/arch/util/mempool.c

   1
   2 /**
   3
   4 Memory pool implementation. It is used in two places-
   5 1 - For UGNI management of pinned memory
   6 2 - Isomalloc allocation
   7
   8 Memory is allocated in terms of blocks from the OS and the user
   9 is given back memory after rounding to nearest power of 2.
  10
  11 Written by Yanhua Sun 08-27-2011
  12 Generalized by Gengbin Zheng  10/5/2011
  13 Heavily modified by Nikhil Jain 11/28/2011
  14 */
  15
  16 #define MEMPOOL_DEBUG   0
  17
  18 #include "converse.h"
  19 #include <stdio.h>
  20 #include <stdlib.h>
  21 #include <string.h>
  22 #if CMK_HAS_MALLOC_H
  23 #include <malloc.h>
  24 #endif
  25
  26 #if CMK_C_INLINE
  27 #define INLINE_KEYWORD inline static
  28 #else
  29 #define INLINE_KEYWORD static
  30 #endif
  31
  32 #include "mempool.h"
  33 int cutOffPoints[] = {64,128,256,512,1024,2048,4096, 8192,16384,32768,
  34                       65536,131072,262144,524288,1048576,2097152,4194304,
  35                       8388608,16777216,33554432,67108864,134217728,268435456,
  36                       536870912,1073741824};
  37
  38 INLINE_KEYWORD int which_pow2(size_t size)
  39 {
  40   int i;
  41   for(i=0; i<cutOffNum; i++) {
  42     if(size <= cutOffPoints[i]) {
  43       return i;
  44     }
  45   }
  46   return i;
  47 }
  48
  49 //method to initialize the freelists of a newly allocated block
  50 INLINE_KEYWORD void fillblock(mempool_type *mptr,block_header *block_head,size_t pool_size,int expansion)
  51 {
  52   int         i,power;
  53   size_t      loc,left,prev,taken;
  54   slot_header *head;
  55   void        *pool;
  56
  57   for(i=0; i<cutOffNum;i++) {
  58     block_head->freelists[i] = 0;
  59   }
  60
  61   pool = block_head;
  62   taken = expansion ? sizeof(block_header) : sizeof(mempool_type);
  63   left = pool_size - taken;
  64   loc = (char*)pool + taken - (char*)mptr;
  65   power = which_pow2(left);
  66   if(left < cutOffPoints[power]) {
  67     power--;
  68   }
  69
  70   if(power == cutOffNum) {
  71     CmiAbort("Mempool-requested slot is more than what mempool can provide as\
  72     one chunk, increase cutOffNum and cutoffPoints in mempool\n");
  73   }
  74
  75 #if MEMPOOL_DEBUG
  76   CmiPrintf("Left is %d, Max power obtained is %d\n",left,power);
  77 #endif
  78
  79   for(i=power; i>=0; i--) {
  80     if(left>=cutOffPoints[i]) {
  81       block_head->freelists[i] = loc;
  82       loc += cutOffPoints[i];
  83       left -= cutOffPoints[i];
  84     }
  85   }
  86
  87   prev = 0;
  88   for(i=power; i>=0; i--) {
  89     if(block_head->freelists[i]) {
  90       head = (slot_header*)((char*)mptr+block_head->freelists[i]);
  91       head->size = i;
  92       head->status = 1;
  93       head->block_ptr = block_head;
  94       head->prev = head->next = 0;
  95       head->gprev = prev;
  96       if(i!=power) {
  97         ((slot_header*)((char*)mptr+prev))->gnext = block_head->freelists[i];
  98       }
  99       prev = block_head->freelists[i];
 100     }
 101   }
 102   head->gnext = 0;
 103 }
 104
 105 //method to check if a request can be met by this block
 106 //if yes, alter the block free list appropiately
 107 int checkblock(mempool_type *mptr,block_header *current,int power)
 108 {
 109   int         i,powiter;
 110   size_t      prev,loc,gnext;
 111   slot_header *head,*head_free,*head_move,*head_next;
 112   head_free = current->freelists[power]?(slot_header*)((char*)mptr+current->freelists[power]):NULL;
 113
 114   //if the freelist of required size is empty, check if free
 115   //list of some larger size is non-empty and break a slot from it
 116   powiter = power+1;
 117   while(head_free==NULL && powiter<cutOffNum) {
 118     if(current->freelists[powiter]) {
 119       head_move = (slot_header*)((char*)mptr+current->freelists[powiter]);
 120       gnext = head_move->gnext;
 121       loc = current->freelists[powiter];
 122       current->freelists[powiter] = head_move->next;
 123       current->freelists[power] = loc;
 124       //we get 2 entries for smallest size required
 125       loc = loc+cutOffPoints[power];
 126       for(i=power+1; i<powiter; i++) {
 127         loc = loc+cutOffPoints[i-1];
 128         current->freelists[i] = loc;
 129       }
 130
 131       head_move->size = power;
 132       prev = current->freelists[power];
 133       head_move->next = prev+cutOffPoints[power];
 134       head = (slot_header*)((char*)head_move+cutOffPoints[power]);
 135       for(i=power; i<powiter; i++) {
 136         if(i!=power) {
 137           head = (slot_header*)((char*)head+cutOffPoints[i-1]);
 138         }
 139         head->size = i;
 140         head->status = 1;
 141         head->block_ptr = current;
 142         head->prev = head->next = 0;
 143         head->gprev = prev;
 144         ((slot_header*)((char*)mptr+prev))->gnext = (char*)head-(char*)mptr;
 145         if(i!=power) {
 146           prev = prev+cutOffPoints[i-1];
 147         } else {
 148           prev = prev+cutOffPoints[i];
 149         }
 150       }
 151       ((slot_header*)((char*)head_move+cutOffPoints[power]))->prev =
 152       current->freelists[power];
 153       head->gnext = gnext;
 154       if(gnext!= 0) {
 155         ((slot_header*)((char*)mptr+gnext))->gprev = prev;
 156       }
 157       if(current->freelists[powiter]) {
 158         head_next = (slot_header*)((char*)mptr+current->freelists[powiter]);
 159         head_next->prev = 0;
 160       }
 161       head_free = (slot_header*)((char*)mptr+current->freelists[power]);
 162     }
 163     powiter++;
 164   }
 165
 166   return head_free != NULL;
 167 }
 168
 169 void removeblocks(mempool_type *mptr)
 170 {
 171   block_header *current,*prev,*tofree,*tail;
 172
 173   mempool_freeblock freefn;
 174   if(mptr == NULL) return;
 175   freefn = mptr->freeblockfn;
 176   tail = (block_header*)((char*)mptr+mptr->block_tail);
 177   current = prev = &(mptr->block_head);
 178   current = current->block_next?(block_header *)((char*)mptr+current->block_next):NULL;
 179
 180   while(current != NULL) {
 181     if(current->used <= 0) {
 182       tofree = current;
 183       current = current->block_next?(block_header *)((char*)mptr+current->block_next):NULL;
 184       if(tail == tofree) {
 185         mptr->block_tail = tofree->block_prev;
 186       }
 187       prev->block_next = tofree->block_next;
 188       if(current != NULL) {
 189         current->block_prev = tofree->block_prev;
 190       }
 191       mptr->size -= tofree->size;
 192       freefn(tofree, tofree->mem_hndl);
 193       if(mptr->size < mptr->limit) return;
 194     } else {
 195       prev = current;
 196       current = current->block_next?(block_header *)((char*)mptr+current->block_next):NULL;
 197     }
 198   }
 199 }
 200
 201 mempool_type *mempool_init(size_t pool_size, mempool_newblockfn allocfn, mempool_freeblock freefn, size_t limit)
 202 {
 203   int power;
 204   mempool_type *mptr;
 205   mem_handle_t  mem_hndl;
 206
 207   void *pool = allocfn(&pool_size, &mem_hndl, 0);
 208   mptr = (mempool_type*)pool;
 209   mptr->newblockfn = allocfn;
 210   mptr->freeblockfn = freefn;
 211   mptr->block_tail = 0;
 212   mptr->limit = limit;
 213   mptr->size = pool_size;
 214 #if CMK_USE_MEMPOOL_ISOMALLOC || (CMK_SMP && CMK_CONVERSE_UGNI)
 215   mptr->mempoolLock = CmiCreateLock();
 216 #endif
 217   mptr->block_head.mptr = (struct mempool_type *)pool;
 218   mptr->block_head.mem_hndl = mem_hndl;
 219   mptr->block_head.size = pool_size;
 220   mptr->block_head.used = 0;
 221   mptr->block_head.block_prev = 0;
 222   mptr->block_head.block_next = 0;
 223 #if CMK_CONVERSE_UGNI
 224   mptr->block_head.msgs_in_send= 0;
 225   mptr->block_head.msgs_in_recv= 0;
 226 #endif
 227   fillblock(mptr,&mptr->block_head,pool_size,0);
 228   return mptr;
 229 }
 230
 231 void mempool_destroy(mempool_type *mptr)
 232 {
 233   block_header *current,*tofree;
 234
 235   mempool_freeblock freefn;
 236   if(mptr == NULL) return;
 237   freefn= mptr->freeblockfn;
 238   current = tofree = &(mptr->block_head);
 239
 240   while(current != NULL) {
 241     tofree = current;
 242     current = current->block_next?(block_header *)((char*)mptr+current->block_next):NULL;
 243     freefn(tofree, tofree->mem_hndl);
 244   }
 245 }
 246
 247 // append slot_header size before the real memory buffer
 248 void*  mempool_malloc(mempool_type *mptr, size_t size, int expand)
 249 {
 250     void          *pool;
 251     int           i;
 252     size_t        expand_size, bestfit_size;
 253     int           power; //closest power of cutoffpoint
 254     block_header  *current,*tail;
 255     slot_header   *head_free,*head_next;
 256     mem_handle_t  mem_hndl;
 257
 258 #if CMK_USE_MEMPOOL_ISOMALLOC || (CMK_SMP && CMK_CONVERSE_UGNI)
 259     CmiLock(mptr->mempoolLock);
 260 #endif
 261
 262     bestfit_size = size + sizeof(used_header);
 263     power = which_pow2(bestfit_size);
 264     if(power == cutOffNum) {
 265       CmiAbort("Mempool-requested slot is more than what mempool can provide as\
 266       one chunk, increase cutOffNum and cutoffPoints in mempool\n");
 267     }
 268     bestfit_size = cutOffPoints[power];
 269 #if MEMPOOL_DEBUG
 270     CmiPrintf("Request size is %d, power value is %d, size is %d\n",size,power,cutOffPoints[power]);
 271 #endif
 272
 273     head_free = NULL;
 274     current = &mptr->block_head;
 275     while(current != NULL) {
 276      if(checkblock(mptr,current,power)) {
 277         head_free = current->freelists[power]?(slot_header*)((char*)mptr+current->freelists[power]):NULL;
 278         break;
 279       } else {
 280         current = current->block_next?(block_header *)((char*)mptr+current->block_next):NULL;
 281       }
 282     }
 283
 284     //no space in current blocks, get a new one
 285     if(head_free==NULL) {
 286       if (!expand) return NULL;
 287
 288 #if MEMPOOL_DEBUG
 289       CmiPrintf("Expanding size %lld limit %lld\n",mptr->size,mptr->limit);
 290 #endif
 291       //free blocks which are not being used
 292       if((mptr->size > mptr->limit) && (mptr->limit > 0)) {
 293         removeblocks(mptr);
 294       }
 295
 296       tail = (block_header*)((char*)mptr+mptr->block_tail);
 297       expand_size = 2*bestfit_size + sizeof(block_header);
 298       pool = mptr->newblockfn(&expand_size, &mem_hndl, 1);
 299       if(pool==NULL) {
 300         CmiPrintf("Mempool-Did not get memory while expanding\n");
 301         return NULL;
 302       }
 303
 304       mptr->size += expand_size;
 305       current = (block_header*)pool;
 306       tail->block_next = ((char*)current-(char*)mptr);
 307       current->block_prev = mptr->block_tail;
 308       mptr->block_tail = tail->block_next;
 309
 310       current->mptr = mptr;
 311       current->mem_hndl = mem_hndl;
 312       current->used = 0;
 313       current->size = expand_size;
 314       current->block_next = 0;
 315 #if CMK_CONVERSE_UGNI
 316       current->msgs_in_send= 0;
 317       current->msgs_in_recv = 0;
 318 #endif
 319
 320       fillblock(mptr,current,expand_size,1);
 321       if(checkblock(mptr,current,power)) {
 322         head_free = current->freelists[power]?(slot_header*)((char*)mptr+current->freelists[power]):NULL;
 323       } else {
 324         CmiPrintf("Mempool-No free block after expansion, something is broken in mempool\n");
 325         return NULL;
 326       }
 327     }
 328
 329     if(head_free!=NULL) {
 330       head_free->status = 0;
 331       current->freelists[power] = head_free->next;
 332       head_next = current->freelists[power]?(slot_header*)((char*)mptr+current->freelists[power]):NULL;
 333       if(head_next != NULL) {
 334         head_next->prev = 0;
 335       }
 336
 337       head_free->block_ptr = current;
 338       current->used += power;
 339 #if CMK_USE_MEMPOOL_ISOMALLOC || (CMK_SMP && CMK_CONVERSE_UGNI)
 340       CmiUnlock(mptr->mempoolLock);
 341 #endif
 342       return (char*)head_free + sizeof(used_header);
 343     }
 344
 345     CmiPrintf("Mempool-Reached a location which I should never have reached\n");
 346     return NULL;
 347 }
 348
 349 #if CMK_USE_MEMPOOL_ISOMALLOC || (CMK_SMP && CMK_CONVERSE_UGNI)
 350 void mempool_free_thread( void *ptr_free)
 351 {
 352     slot_header *to_free;
 353     mempool_type *mptr;
 354
 355     to_free = (slot_header *)((char*)ptr_free - sizeof(used_header));
 356     mptr = (mempool_type*)(((block_header*)(to_free->block_ptr))->mptr);
 357     CmiLock(mptr->mempoolLock);
 358     mempool_free(mptr,  ptr_free);
 359     CmiUnlock(mptr->mempoolLock);
 360 }
 361 #endif
 362
 363 void mempool_free(mempool_type *mptr, void *ptr_free)
 364 {
 365     int           i,power;
 366     size_t        prev,loc,size,left;
 367     block_header  *block_head;
 368     slot_header   *to_free, *first, *current;
 369     slot_header   *used_next,*temp;
 370
 371 #if MEMPOOL_DEBUG
 372     CmiPrintf("Free request for %lld\n",
 373               ((char*)ptr_free - (char*)mptr - sizeof(used_header)));
 374 #endif
 375
 376     to_free = (slot_header *)((char*)ptr_free - sizeof(used_header));
 377     to_free->status = 1;
 378     block_head = to_free->block_ptr;
 379     block_head->used -= to_free->size;
 380
 381     //find the neighborhood of to_free which is also free and
 382     //can be merged to get larger free slots
 383     size = 0;
 384     current = to_free;
 385     while(current->status == 1) {
 386       size += cutOffPoints[current->size];
 387       first = current;
 388       current = current->gprev?(slot_header*)((char*)mptr+current->gprev):NULL;
 389       if(current == NULL)
 390         break;
 391     }
 392
 393     size -= cutOffPoints[to_free->size];
 394     current = to_free;
 395     while(current->status == 1) {
 396       size += cutOffPoints[current->size];
 397       current = current->gnext?(slot_header*)((char*)mptr+current->gnext):NULL;
 398       if(current == NULL)
 399         break;
 400     }
 401     used_next = current;
 402
 403     //remove the free slots in neighbor hood from their respective
 404     //free lists
 405     current = first;
 406     while(current!=used_next) {
 407       if(current!=to_free) {
 408         power = current->size;
 409         temp = current->prev?(slot_header*)((char*)mptr+current->prev):NULL;
 410         if(temp!=NULL) {
 411           temp->next = current->next;
 412         } else {
 413           block_head->freelists[power] = current->next;
 414         }
 415         temp = current->next?(slot_header*)((char*)mptr+current->next):NULL;
 416         if(temp!=NULL) {
 417           temp->prev = current->prev;
 418         }
 419       }
 420       current = current->gnext?(slot_header*)((char*)mptr+current->gnext):NULL;
 421     }
 422
 423     //now create the new free slots of as large a size as possible
 424     power = which_pow2(size);
 425     if(size < cutOffPoints[power]) {
 426       power--;
 427     }
 428     left = size;
 429
 430 #if MEMPOOL_DEBUG
 431     if(CmiMyPe() == 0)
 432       printf("free was for %lld, merging for %lld, power %lld\n",to_free->size,size,power);
 433 #endif
 434
 435     loc = (char*)first - (char*)mptr;
 436     for(i=power; i>=0; i--) {
 437       if(left>=cutOffPoints[i]) {
 438         current = (slot_header*)((char*)mptr+loc);
 439         current->size = i;
 440         current->status = 1;
 441         current->block_ptr = block_head;
 442         if(i!=power) {
 443           current->gprev = prev;
 444         }
 445         current->gnext = loc + cutOffPoints[i];
 446         current->prev = 0;
 447         if(block_head->freelists[i] == 0) {
 448           current->next = 0;
 449         } else {
 450           current->next = block_head->freelists[i];
 451           temp = (slot_header*)((char*)mptr+block_head->freelists[i]);
 452           temp->prev = loc;
 453         }
 454         block_head->freelists[i] = loc;
 455         prev = loc;
 456         loc += cutOffPoints[i];
 457         left -= cutOffPoints[i];
 458       }
 459     }
 460    if(used_next!=NULL) {
 461       used_next->gprev = (char*)current - (char*)mptr;
 462     } else {
 463       current->gnext = 0;
 464     }
 465 #if MEMPOOL_DEBUG
 466     CmiPrintf("Free done\n");
 467 #endif
 468 }
 469
 470 #if CMK_CONVERSE_UGNI
 471 inline void* getNextRegisteredPool(void *current)
 472 {
 473
 474 }
 475 #endif