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