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