d88111e954f65ba5476875ebeb585f46027ec12b
[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 <string.h>
21 #if CMK_HAS_MALLOC_H
22 #include <malloc.h>
23 #endif
24
25 #include "mempool.h"
26
27 #if CMK_CONVERSE_GEMINI_UGNI
28 static      size_t     expand_mem = 1024ll*1024*16;
29 #else
30 static      size_t     expand_mem = 1024*16;
31 #endif 
32
33 mempool_type *mempool_init(size_t pool_size, mempool_newblockfn allocfn, mempool_freeblock freefn)
34 {
35     mempool_type *mptr;
36     mempool_header *header;
37     gni_mem_handle_t  mem_hndl;
38
39     void *pool = allocfn(&pool_size, &mem_hndl);
40     mptr = (mempool_type*)pool;
41     mptr->newblockfn = allocfn;
42     mptr->freeblockfn = freefn;
43     mptr->mempools_head.mempool_ptr = pool;
44     mptr->mempools_head.mem_hndl = mem_hndl;
45     mptr->mempools_head.size = pool_size;
46     mptr->mempools_head.next = NULL;
47     header = (mempool_header *) ((char*)pool+sizeof(mempool_type));
48     mptr->freelist_head = sizeof(mempool_type);
49     header->size = pool_size-sizeof(mempool_type)-sizeof(mempool_header);
50     header->mem_hndl = mem_hndl;
51     header->next_free = 0;
52 #if MEMPOOL_DEBUG 
53     printf("[%d] Initiated pool of size %lld at %p\n",CmiMyPe(),pool_size,mptr);
54 #endif
55     return mptr;
56 }
57
58 void mempool_destroy(mempool_type *mptr)
59 {
60     mempool_block *current, *mempools_head;
61     mempool_freeblock   freefn = mptr->freeblockfn;
62
63     current = mempools_head = &(mptr->mempools_head);
64
65     while(mempools_head!= NULL)
66     {
67         current=mempools_head;
68         mempools_head = mempools_head->next;
69         freefn(current->mempool_ptr, current->mem_hndl);
70     }
71 }
72
73 // append size before the real memory buffer
74 void*  mempool_malloc(mempool_type *mptr, int size, int expand)
75 {
76     int     bestfit_size = MAX_INT; //most close size 
77     size_t    *freelist_head = &mptr->freelist_head;
78     mempool_header    *freelist_head_ptr = mptr->freelist_head?(mempool_header*)((char*)mptr+mptr->freelist_head):NULL;
79     mempool_header    *current = freelist_head_ptr;
80     mempool_header    *previous = NULL;
81     mempool_header    *bestfit = NULL;
82     mempool_header    *bestfit_previous = NULL;
83     mempool_block     *mempools_head = &(mptr->mempools_head);
84
85 #if  MEMPOOL_DEBUG
86     CmiPrintf("[%d] request malloc from pool: %p  free_head: %p %d for size %d, \n", CmiMyPe(), mptr, freelist_head_ptr, mptr->freelist_head, size);
87 #endif
88
89     size += sizeof(mempool_header);
90
91 #if 1
92     while(current!= NULL)     /* best fit */
93     {
94 #if  MEMPOOL_DEBUG
95         CmiPrintf("[%d] current=%p size:%d \n", CmiMyPe(), current, current->size);
96 #endif
97         if(current->size >= size && current->size < bestfit_size)
98         {
99             bestfit_size = current->size;
100             bestfit = current;
101             bestfit_previous = previous;
102         }
103         previous = current;
104         current = current->next_free?(mempool_header*)((char*)mptr + current->next_free):NULL;
105     }
106 #else
107     while(current!= NULL)             /*  first fit */
108     {
109 #if  MEMPOOL_DEBUG
110         CmiPrintf("[%d] current=%p size:%d ->%p \n", CmiMyPe(), current, current->size, (char*)current+current->size);
111 #endif
112         CmiAssert(current->size != 0);
113         if(current->size >= size)
114         {
115             bestfit_size = current->size;
116             bestfit = current;
117             bestfit_previous = previous;
118             break;
119         }
120         previous = current;
121         current = current->next_free?(mempool_header*)((char*)mptr + current->next_free):NULL;
122     }
123 #endif
124
125     if(bestfit == NULL)
126     {
127 #if MEMPOOL_DEBUG 
128         printf("[%d] Expanding pool %p by %d\n",CmiMyPe(),mptr,CthSelf());
129 #endif
130         void *pool;
131         mempool_block   *expand_pool;
132         size_t   expand_size;
133         gni_mem_handle_t  mem_hndl;
134
135         if (!expand) return NULL;
136
137         expand_size = expand_mem>size ? expand_mem:2*size; 
138         pool = mptr->newblockfn(&expand_size, &mem_hndl);
139         expand_pool = (mempool_block*)pool;
140         expand_pool->mempool_ptr = pool;
141         expand_pool->mem_hndl = mem_hndl;
142         expand_pool->size = expand_size;
143         expand_pool->next = NULL;
144 #if  MEMPOOL_DEBUG
145         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);
146 #endif
147         // FIXME: go to the end of link list
148         //while (mempools_head->next != NULL && mempools_head < expand_pool) mempools_head = mempools_head->next;
149         while (mempools_head->next != NULL) mempools_head = mempools_head->next;
150         mempools_head->next = expand_pool;
151
152         bestfit = (mempool_header*)((char*)expand_pool->mempool_ptr + sizeof(mempool_block));
153         bestfit->size = expand_size-sizeof(mempool_block);
154         bestfit->mem_hndl = expand_pool->mem_hndl;
155         bestfit->next_free = 0;
156         bestfit_size = expand_size-sizeof(mempool_block);
157 #if 0
158         current = freelist_head_ptr;
159         while(current!= NULL && current < bestfit )
160         {
161           previous = current;
162           current = current->next_free?(mempool_header*)((char *)mptr + current->next_free):NULL;
163         }
164 #elif 0
165         CmiAssert(bestfit > previous);
166 #endif
167         bestfit_previous = previous;
168         if (previous == NULL) {
169            *freelist_head = (char*)bestfit - (char*)mptr;
170            freelist_head_ptr =  bestfit;
171         }
172         else
173            previous->next_free = (char*)bestfit-(char*)mptr;
174     }
175
176     bestfit->size = size;
177     if(bestfit_size > size + sizeof(mempool_header)) //deduct this entry 
178     {
179         mempool_header *ptr = (mempool_header *)((char*)bestfit + size);
180         ptr->size = bestfit_size - size;
181         ptr->mem_hndl = bestfit->mem_hndl;
182         ptr->next_free = bestfit->next_free;
183         if(bestfit == freelist_head_ptr)
184            *freelist_head = (char*)ptr - (char*)mptr;
185         if(bestfit_previous != NULL)
186            bestfit_previous->next_free = (char*)ptr - (char*)mptr;
187     }
188     else {  
189           //delete this free entry
190         if (bestfit_size > size) {
191            bestfit->size = bestfit_size;
192         }
193         if(bestfit == freelist_head_ptr)
194             *freelist_head = freelist_head_ptr->next_free;
195         else
196             bestfit_previous->next_free = bestfit->next_free;
197     }
198 #if  MEMPOOL_DEBUG
199     printf("[%d] ++MALLOC served: %d, ptr:%p\n", CmiMyPe(), size, bestfit);
200 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);
201 #endif
202     CmiAssert(*freelist_head >= 0);
203     return (char*)bestfit + sizeof(mempool_header);
204 }
205
206 //sorted free_list and merge it if it become continous 
207 void mempool_free(mempool_type *mptr, void *ptr_free)
208 {
209     int i;
210     int merged = 0;
211     int free_size;
212     void *free_lastbytes_pos;
213     mempool_block     *mempools_head;
214     size_t    *freelist_head;
215     mempool_header    *freelist_head_ptr;
216     mempool_header    *current;
217     mempool_header *previous = NULL;
218     mempool_header *to_free;
219
220     to_free = (mempool_header *)((char*)ptr_free - sizeof(mempool_header));
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*)to_free +free_size;
229
230 #if  MEMPOOL_DEBUG
231     printf("[%d] INSIDE FREE ptr=%p, size=%d freehead=%p mutex: %p\n", CmiMyPe(), to_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     while(current!= NULL && memcmp(&current->mem_hndl, &to_free->mem_hndl, sizeof(gni_mem_handle_t))!=0)
243     {
244 #if  MEMPOOL_DEBUG
245         CmiPrintf("[%d] previous=%p, current=%p size:%d %p\n", CmiMyPe(), previous, current, current->size, (char*)current+current->size);
246 #endif
247         previous = current;
248         current = current->next_free?(mempool_header*)((char*)mptr + current->next_free):NULL;
249     }
250     while(current!= NULL && current < to_free && memcmp(&current->mem_hndl, &to_free->mem_hndl, sizeof(gni_mem_handle_t))==0)
251     {
252 #if  MEMPOOL_DEBUG
253         CmiPrintf("[%d] previous=%p, current=%p size:%d %p\n", CmiMyPe(), previous, current, current->size, (char*)current+current->size);
254 #endif
255         previous = current;
256         current = current->next_free?(mempool_header*)((char*)mptr + current->next_free):NULL;
257     }
258 #if  MEMPOOL_DEBUG
259     if (current) CmiPrintf("[%d] previous=%p, current=%p size:%d %p\n", CmiMyPe(), previous, current, current->size, free_lastbytes_pos);
260 #endif
261     //continuos with previous free space 
262     if(previous!= NULL && (char*)previous+previous->size == (char*)to_free &&  memcmp(&previous->mem_hndl, &to_free->mem_hndl, sizeof(gni_mem_handle_t))==0 )
263     {
264         previous->size +=  free_size;
265         merged = 1;
266     }
267     else if(current!= NULL && free_lastbytes_pos == current && memcmp(&current->mem_hndl, &to_free->mem_hndl, sizeof(gni_mem_handle_t))==0)
268     {
269         to_free->size += current->size;
270         to_free->next_free = current->next_free;
271         current = to_free;
272         merged = 1;
273         if(previous == NULL)
274             *freelist_head = (char*)current - (char*)mptr;
275         else
276             previous->next_free = (char*)to_free - (char*)mptr;
277     }
278     //continous, merge
279     if(merged) {
280        if (previous!= NULL && current!= NULL && (char*)previous + previous->size  == (char *)current && memcmp(&previous->mem_hndl, &current->mem_hndl, sizeof(gni_mem_handle_t))==0)
281       {
282          previous->size += current->size;
283          previous->next_free = current->next_free;
284       }
285     }
286     else {
287           // no merge to previous, current, create new entry
288         to_free->next_free = current?(char*)current - (char*)mptr: 0;
289         if(previous == NULL)
290             *freelist_head = (char*)to_free - (char*)mptr;
291         else
292             previous->next_free = (char*)to_free - (char*)mptr;
293     }
294 #if  MEMPOOL_DEBUG
295     printf("[%d] Memory free done %p, freelist_head=%p\n", CmiMyPe(), to_free,  freelist_head);
296 #endif
297
298     CmiAssert(*freelist_head >= 0);
299 }
300