a better mempool interface that gets ride of uGNI specific stuff
[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 gni_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
9 */
10
11 #define MEMPOOL_DEBUG   0
12
13 #define POOLS_NUM       2
14 #define MAX_INT        2147483647
15
16 #include "converse.h"
17
18 #include <stdio.h>
19 #include <stdlib.h>
20 #include <stdint.h>
21 #include <string.h>
22 #if CMK_HAS_MALLOC_H
23 #include <malloc.h>
24 #endif
25
26 #include "mempool.h"
27
28 static      size_t     expand_mem = 1024ll*1024*16;
29
30 mempool_type *mempool_init(size_t pool_size, mempool_newblockfn allocfn, mempool_freeblock freefn)
31 {
32     mempool_type *mptr;
33     mempool_header *header;
34     gni_mem_handle_t  mem_hndl;
35
36     void *pool = allocfn(pool_size, &mem_hndl);
37     mptr = (mempool_type*)pool;
38     mptr->newblockfn = allocfn;
39     mptr->freeblockfn = freefn;
40     mptr->mempools_head.mempool_ptr = pool;
41     mptr->mempools_head.mem_hndl = mem_hndl;
42     mptr->mempools_head.size = pool_size;
43     mptr->mempools_head.next = NULL;
44     header = (mempool_header *) ((char*)pool+sizeof(mempool_type));
45     mptr->freelist_head = sizeof(mempool_type);
46 //printf("[%d] pool: %p  free: %p\n", myrank, pool, header);
47     header->size = pool_size-sizeof(mempool_type)-sizeof(mempool_header);
48     header->mem_hndl = mem_hndl;
49     header->next_free = 0;
50     return mptr;
51 }
52
53 void kill_allmempool(mempool_type *mptr)
54 {
55     mempool_block *current, *mempools_head;
56     mempool_freeblock   freefn = mptr->freeblockfn;
57
58     current = mempools_head = &(mptr->mempools_head);
59
60     while(mempools_head!= NULL)
61     {
62         //printf("[%d] free mempool:%p\n", CmiMyPe(), mempools_head->mempool_ptr);
63         current=mempools_head;
64         mempools_head = mempools_head->next;
65         freefn(current->mempool_ptr, current->mem_hndl);
66     }
67 }
68
69 // append size before the real memory buffer
70 void*  mempool_malloc(mempool_type *mptr, int size, int expand)
71 {
72     int     bestfit_size = MAX_INT; //most close size 
73     size_t    *freelist_head = &mptr->freelist_head;
74     mempool_header    *freelist_head_ptr = mptr->freelist_head?(mempool_header*)((char*)mptr+mptr->freelist_head):NULL;
75     mempool_header    *current = freelist_head_ptr;
76     mempool_header    *previous = NULL;
77     mempool_header    *bestfit = NULL;
78     mempool_header    *bestfit_previous = NULL;
79     mempool_block     *mempools_head = &(mptr->mempools_head);
80
81 #if  MEMPOOL_DEBUG
82     CmiPrintf("[%d] request malloc from pool: %p  free_head: %p %d for size %d, \n", CmiMyPe(), mptr, freelist_head_ptr, mptr->freelist_head, size);
83 #endif
84
85 #if 1
86     while(current!= NULL)     /* best fit */
87     {
88 #if  MEMPOOL_DEBUG
89         CmiPrintf("[%d] current=%p size:%d \n", CmiMyPe(), current, current->size);
90 #endif
91         if(current->size >= size && current->size < bestfit_size)
92         {
93             bestfit_size = current->size;
94             bestfit = current;
95             bestfit_previous = previous;
96         }
97         previous = current;
98         current = current->next_free?(mempool_header*)((char*)mptr + current->next_free):NULL;
99     }
100 #else
101     while(current!= NULL)             /*  first fit */
102     {
103 #if  MEMPOOL_DEBUG
104         CmiPrintf("[%d] current=%p size:%d ->%p \n", CmiMyPe(), current, current->size, (char*)current+current->size);
105 #endif
106         CmiAssert(current->size != 0);
107         if(current->size >= size)
108         {
109             bestfit_size = current->size;
110             bestfit = current;
111             bestfit_previous = previous;
112             break;
113         }
114         previous = current;
115         current = current->next_free?(mempool_header*)((char*)mptr + current->next_free):NULL;
116     }
117 #endif
118
119     if(bestfit == NULL)
120     {
121         void *pool;
122         mempool_block   *expand_pool;
123         size_t   expand_size;
124         gni_mem_handle_t  mem_hndl;
125
126         if (!expand) return NULL;
127
128         expand_size = expand_mem>size ? expand_mem:2*size; 
129         pool = mptr->newblockfn(expand_size, &mem_hndl);
130         expand_pool = (mempool_block*)pool;
131         expand_pool->mempool_ptr = pool;
132         expand_pool->mem_hndl = mem_hndl;
133         expand_pool->size = expand_size;
134         expand_pool->next = NULL;
135         printf("[%d] No memory has such free empty chunck of %d. expanding %p with new size %d\n", CmiMyPe(), size, expand_pool->mempool_ptr, expand_size);
136           // FIXME: go to the end of link list
137         while (mempools_head->next != NULL) mempools_head = mempools_head->next;
138         mempools_head->next = expand_pool;
139
140         bestfit = (mempool_header*)((char*)expand_pool->mempool_ptr + sizeof(mempool_block));
141         bestfit->size = expand_size-sizeof(mempool_block);
142         bestfit->mem_hndl = expand_pool->mem_hndl;
143         bestfit->next_free = 0;
144         bestfit_size = expand_size;
145 #if 0
146         current = freelist_head;
147         while(current!= NULL && current < bestfit )
148         {
149           previous = current;
150           current = current->next;
151         }
152 #else
153         CmiAssert(bestfit > previous);
154 #endif
155         bestfit_previous = previous;
156         if (previous == NULL)
157            *freelist_head = (char*)bestfit - (char*)mptr;
158         else
159            previous->next_free = (char*)bestfit-(char*)mptr;
160     }
161
162     bestfit->size = size;
163     if(bestfit_size > size) //deduct this entry 
164     {
165         mempool_header *ptr = (mempool_header *)((char*)bestfit + size);
166         ptr->size = bestfit_size - size;
167         ptr->mem_hndl = bestfit->mem_hndl;
168         ptr->next_free = bestfit->next_free;
169         if(bestfit == freelist_head_ptr)
170            *freelist_head = (char*)ptr - (char*)mptr;
171         if(bestfit_previous != NULL)
172            bestfit_previous->next_free = (char*)ptr - (char*)mptr;
173     }
174     else {  
175           //delete this free entry
176         if(bestfit == freelist_head_ptr)
177             *freelist_head = freelist_head_ptr->next_free;
178         else
179             bestfit_previous->next_free = bestfit->next_free;
180     }
181 #if  MEMPOOL_DEBUG
182     printf("[%d] ++MALLOC served: %d, ptr:%p\n", CmiMyPe(), size, bestfit);
183 printf("[%d] freelist_head in malloc  offset:%d free_head: %ld %ld %d %d\n", myrank, (char*)bestfit-(char*)mptr, *freelist_head, ((mempool_header*)((char*)mptr+*freelist_head))->next_free, bestfit_size, size);
184 #endif
185     CmiAssert(*freelist_head >= 0);
186     return (char*)bestfit;
187 }
188
189 //sorted free_list and merge it if it become continous 
190 void mempool_free(mempool_type *mptr, void *ptr_free)
191 {
192     int i;
193     int merged = 0;
194     int free_size;
195     void *free_lastbytes_pos;
196     mempool_block     *mempools_head;
197     size_t    *freelist_head;
198     mempool_header    *freelist_head_ptr;
199     mempool_header    *current;
200     mempool_header *previous = NULL;
201     mempool_header *to_free = (mempool_header *)ptr_free;
202
203     mempools_head = &(mptr->mempools_head);
204     freelist_head = &mptr->freelist_head;
205     freelist_head_ptr = mptr->freelist_head?(mempool_header*)((char*)mptr+mptr->freelist_head):NULL;
206     current = freelist_head_ptr;
207
208     free_size = to_free->size;
209     free_lastbytes_pos = (char*)ptr_free +free_size;
210
211 #if  MEMPOOL_DEBUG
212     printf("[%d] INSIDE FREE ptr=%p, size=%d freehead=%p mutex: %p\n", CmiMyPe(), ptr_free, free_size, freelist_head, mptr->mutex);
213 #endif
214     
215     while(current!= NULL && current < to_free )
216     {
217 #if  MEMPOOL_DEBUG
218         CmiPrintf("[%d] previous=%p, current=%p size:%d %p\n", CmiMyPe(), previous, current, current->size, (char*)current+current->size);
219 #endif
220         previous = current;
221         current = current->next_free?(mempool_header*)((char*)mptr + current->next_free):NULL;
222     }
223 #if  MEMPOOL_DEBUG
224     if (current) CmiPrintf("[%d] previous=%p, current=%p size:%d %p\n", CmiMyPe(), previous, current, current->size, free_lastbytes_pos);
225 #endif
226     //continuos with previous free space 
227     if(previous!= NULL && (char*)previous+previous->size == ptr_free &&  memcmp(&previous->mem_hndl, &to_free->mem_hndl, sizeof(gni_mem_handle_t))==0 )
228     {
229         previous->size +=  free_size;
230         merged = 1;
231     }
232     else if(current!= NULL && free_lastbytes_pos == current && memcmp(&current->mem_hndl, &to_free->mem_hndl, sizeof(gni_mem_handle_t))==0)
233     {
234         to_free->size += current->size;
235         to_free->next_free = current->next_free;
236         current = to_free;
237         merged = 1;
238         if(previous == NULL)
239             *freelist_head = (char*)current - (char*)mptr;
240         else
241             previous->next_free = (char*)to_free - (char*)mptr;
242     }
243     //continous, merge
244     if(merged) {
245        if (previous!= NULL && current!= NULL && (char*)previous + previous->size  == (char *)current && memcmp(&previous->mem_hndl, &current->mem_hndl, sizeof(gni_mem_handle_t))==0)
246       {
247          previous->size += current->size;
248          previous->next_free = current->next_free;
249       }
250     }
251     else {
252           // no merge to previous, current, create new entry
253         to_free->next_free = current?(char*)current - (char*)mptr: 0;
254         if(previous == NULL)
255             *freelist_head = (char*)to_free - (char*)mptr;
256         else
257             previous->next_free = (char*)to_free - (char*)mptr;
258     }
259 #if  MEMPOOL_DEBUG
260     printf("[%d] Memory free done %p, freelist_head=%p\n", CmiMyPe(), ptr_free,  freelist_head);
261 #endif
262
263     CmiAssert(*freelist_head >= 0);
264 }
265