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