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