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