Minor changes to mempool.c - add #ifdef for debug
[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
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     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.memblock_next = 0;
47     header = (mempool_header *) ((char*)pool+sizeof(mempool_type));
48     mptr->freelist_head = sizeof(mempool_type);
49     mptr->memblock_tail = 0;
50 #if MEMPOOL_DEBUG
51     printf("[%d] pool: %p  free: %p\n", myrank, pool, header);
52 #endif
53     header->size = pool_size-sizeof(mempool_type)-sizeof(mempool_header);
54     header->mem_hndl = mem_hndl;
55     header->next_free = 0;
56     return mptr;
57 }
58
59 void mempool_destroy(mempool_type *mptr)
60 {
61     mempool_block *current, *mempools_head;
62     mempool_freeblock   freefn = mptr->freeblockfn;
63
64     current = mempools_head = &(mptr->mempools_head);
65
66     while(mempools_head!= NULL)
67     {
68 #if MEMPOOL_DEBUG
69         printf("[%d] free mempool:%p\n", CmiMyPe(), mempools_head->mempool_ptr);
70 #endif
71         current=mempools_head;
72         mempools_head = mempools_head->memblock_next?(mempool_block *)((char*)mptr+mempools_head->memblock_next):NULL;
73         freefn(current->mempool_ptr, current->mem_hndl);
74     }
75 }
76
77 // append size before the real memory buffer
78 void*  mempool_malloc(mempool_type *mptr, int size, int expand)
79 {
80     int     bestfit_size = MAX_INT; //most close size 
81     size_t    *freelist_head = &mptr->freelist_head;
82     mempool_header    *freelist_head_ptr = mptr->freelist_head?(mempool_header*)((char*)mptr+mptr->freelist_head):NULL;
83     mempool_header    *current = freelist_head_ptr;
84     mempool_header    *previous = NULL;
85     mempool_header    *bestfit = NULL;
86     mempool_header    *bestfit_previous = NULL;
87     mempool_block     *mempools_head = &(mptr->mempools_head);
88
89 #if  MEMPOOL_DEBUG
90     CmiPrintf("[%d] request malloc from pool: %p  free_head: %p %d for size %d, \n", CmiMyPe(), mptr, freelist_head_ptr, mptr->freelist_head, size);
91 #endif
92
93     size += sizeof(mempool_header);
94
95 #if 1
96     while(current!= NULL)     /* best fit */
97     {
98 #if  MEMPOOL_DEBUG
99         CmiPrintf("[%d] current=%p size:%d \n", CmiMyPe(), current, current->size);
100 #endif
101         if(current->size >= size && current->size < bestfit_size)
102         {
103             bestfit_size = current->size;
104             bestfit = current;
105             bestfit_previous = previous;
106         }
107         previous = current;
108         current = current->next_free?(mempool_header*)((char*)mptr + current->next_free):NULL;
109     }
110 #else
111     while(current!= NULL)             /*  first fit */
112     {
113 #if  MEMPOOL_DEBUG
114         CmiPrintf("[%d] current=%p size:%d ->%p \n", CmiMyPe(), current, current->size, (char*)current+current->size);
115 #endif
116         CmiAssert(current->size != 0);
117         if(current->size >= size)
118         {
119             bestfit_size = current->size;
120             bestfit = current;
121             bestfit_previous = previous;
122             break;
123         }
124         previous = current;
125         current = current->next_free?(mempool_header*)((char*)mptr + current->next_free):NULL;
126     }
127 #endif
128
129     if(bestfit == NULL)
130     {
131         void *pool;
132         mempool_block   *expand_pool, *memblock_tail;
133         size_t   expand_size;
134         mem_handle_t  mem_hndl;
135
136         if (!expand) return NULL;
137
138         expand_size = expand_mem>size ? expand_mem:2*size; 
139         pool = mptr->newblockfn(&expand_size, &mem_hndl);
140         expand_pool = (mempool_block*)pool;
141         expand_pool->mempool_ptr = pool;
142         expand_pool->mem_hndl = mem_hndl;
143         expand_pool->size = expand_size;
144         expand_pool->memblock_next = 0;
145 #if MEMPOOL_DEBUG
146         printf("[%d] No memory has such free empty chunck of %d. expanding %p with new size %ld\n", CmiMyPe(), size, expand_pool->mempool_ptr, expand_size);
147 #endif
148          /* insert new block to memblock tail */
149         memblock_tail = (mempool_block*)((char*)mptr + mptr->memblock_tail);
150         memblock_tail->memblock_next = mptr->memblock_tail = (char*)expand_pool - (char*)mptr;
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 1
158          /* insert bestfit to sorted free list */
159         previous = NULL;
160         current = freelist_head_ptr;
161         while (current) 
162         {
163             if (current > bestfit) break;
164             previous = current;
165             current = current->next_free?(mempool_header*)((char *)mptr + current->next_free):NULL;
166         };
167         bestfit->next_free = current!=NULL? (char*)current-(char*)mptr:0;
168 #else
169         CmiAssert(bestfit > previous);
170         previous->next_free = (char*)bestfit-(char*)mptr;
171 #endif
172         bestfit_previous = previous;
173         if (previous == NULL) {
174            *freelist_head = (char*)bestfit - (char*)mptr;
175            freelist_head_ptr =  bestfit;
176         }
177         else
178            previous->next_free = (char*)bestfit-(char*)mptr;
179     }
180
181     bestfit->size = size;
182     if(bestfit_size > size + sizeof(mempool_header)) //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_size > size) {
196            bestfit->size = bestfit_size;
197         }
198         if(bestfit == freelist_head_ptr)
199             *freelist_head = freelist_head_ptr->next_free;
200         else
201             bestfit_previous->next_free = bestfit->next_free;
202     }
203 #if  MEMPOOL_DEBUG
204     printf("[%d] ++MALLOC served: %d, ptr:%p\n", CmiMyPe(), size, bestfit);
205 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);
206 #endif
207     CmiAssert(*freelist_head >= 0);
208     return (char*)bestfit + sizeof(mempool_header);
209 }
210
211 //sorted free_list and merge it if it become continous 
212 void mempool_free(mempool_type *mptr, void *ptr_free)
213 {
214     int i;
215     int merged = 0;
216     int free_size;
217     void *free_lastbytes_pos;
218     mempool_block     *mempools_head;
219     size_t    *freelist_head;
220     mempool_header    *freelist_head_ptr;
221     mempool_header    *current;
222     mempool_header *previous = NULL;
223     mempool_header *to_free;
224
225     to_free = (mempool_header *)((char*)ptr_free - sizeof(mempool_header));
226
227     mempools_head = &(mptr->mempools_head);
228     freelist_head = &mptr->freelist_head;
229     freelist_head_ptr = mptr->freelist_head?(mempool_header*)((char*)mptr+mptr->freelist_head):NULL;
230     current = freelist_head_ptr;
231
232     free_size = to_free->size;
233     free_lastbytes_pos = (char*)to_free +free_size;
234
235 #if  MEMPOOL_DEBUG
236     printf("[%d] INSIDE FREE ptr=%p, size=%d freehead=%p mutex: %p\n", CmiMyPe(), to_free, free_size, freelist_head, mptr->mutex);
237 #endif
238     
239     while(current!= NULL && current < to_free )
240     {
241 #if  MEMPOOL_DEBUG
242         CmiPrintf("[%d] previous=%p, current=%p size:%d %p\n", CmiMyPe(), previous, current, current->size, (char*)current+current->size);
243 #endif
244         previous = current;
245         current = current->next_free?(mempool_header*)((char*)mptr + current->next_free):NULL;
246     }
247 #if  MEMPOOL_DEBUG
248     if (current) CmiPrintf("[%d] previous=%p, current=%p size:%d %p\n", CmiMyPe(), previous, current, current->size, free_lastbytes_pos);
249 #endif
250     //continuos with previous free space 
251     if(previous!= NULL && (char*)previous+previous->size == (char*)to_free &&  memcmp(&previous->mem_hndl, &to_free->mem_hndl, sizeof(mem_handle_t))==0 )
252     {
253         previous->size +=  free_size;
254         merged = 1;
255     }
256     else if(current!= NULL && free_lastbytes_pos == current && memcmp(&current->mem_hndl, &to_free->mem_hndl, sizeof(mem_handle_t))==0)
257     {
258         to_free->size += current->size;
259         to_free->next_free = current->next_free;
260         current = to_free;
261         merged = 1;
262         if(previous == NULL)
263             *freelist_head = (char*)current - (char*)mptr;
264         else
265             previous->next_free = (char*)to_free - (char*)mptr;
266     }
267     //continous, merge
268     if(merged) {
269        if (previous!= NULL && current!= NULL && (char*)previous + previous->size  == (char *)current && memcmp(&previous->mem_hndl, &current->mem_hndl, sizeof(mem_handle_t))==0)
270       {
271          previous->size += current->size;
272          previous->next_free = current->next_free;
273       }
274     }
275     else {
276           // no merge to previous, current, create new entry
277         to_free->next_free = current?(char*)current - (char*)mptr: 0;
278         if(previous == NULL)
279             *freelist_head = (char*)to_free - (char*)mptr;
280         else
281             previous->next_free = (char*)to_free - (char*)mptr;
282     }
283 #if  MEMPOOL_DEBUG
284     printf("[%d] Memory free done %p, freelist_head=%p\n", CmiMyPe(), to_free,  freelist_head);
285 #endif
286
287     CmiAssert(*freelist_head >= 0);
288 }
289