64d3d4c4cc7798f5e7aa7a1dbb877486d51956e7
[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 //static      size_t     expand_mem = 1024*16;
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 #if MEMPOOL_DEBUG
47     printf("[%d] pool: %p  free: %p\n", myrank, pool, header);
48 #endif 
49     header->size = pool_size-sizeof(mempool_type)-sizeof(mempool_header);
50     header->mem_hndl = mem_hndl;
51     header->next_free = 0;
52 #if 1 || MEMPOOL_DEBUG 
53     printf("[%d] Initiated mempool with %d memory at %p\n",CmiMyPe(),pool_size,pool);
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         //printf("[%d] free mempool:%p\n", CmiMyPe(), mempools_head->mempool_ptr);
68         current=mempools_head;
69         mempools_head = mempools_head->next;
70         freefn(current->mempool_ptr, current->mem_hndl);
71     }
72 }
73
74 // append size before the real memory buffer
75 void*  mempool_malloc(mempool_type *mptr, int size, int expand)
76 {
77     int     bestfit_size = MAX_INT; //most close size 
78     size_t    *freelist_head = &mptr->freelist_head;
79     mempool_header    *freelist_head_ptr = mptr->freelist_head?(mempool_header*)((char*)mptr+mptr->freelist_head):NULL;
80     mempool_header    *current = freelist_head_ptr;
81     mempool_header    *previous = NULL;
82     mempool_header    *bestfit = NULL;
83     mempool_header    *bestfit_previous = NULL;
84     mempool_block     *mempools_head = &(mptr->mempools_head);
85
86 #if  MEMPOOL_DEBUG
87     CmiPrintf("[%d] request malloc from pool: %p  free_head: %p %d for size %d, \n", CmiMyPe(), mptr, freelist_head_ptr, mptr->freelist_head, size);
88 #endif
89
90 #if 1
91     while(current!= NULL)     /* best fit */
92     {
93 #if  MEMPOOL_DEBUG
94         CmiPrintf("[%d] current=%p size:%d \n", CmiMyPe(), current, current->size);
95 #endif
96         if(current->size >= size && current->size < bestfit_size)
97         {
98             bestfit_size = current->size;
99             bestfit = current;
100             bestfit_previous = previous;
101         }
102         previous = current;
103         current = current->next_free?(mempool_header*)((char*)mptr + current->next_free):NULL;
104     }
105 #else
106     while(current!= NULL)             /*  first fit */
107     {
108 #if  MEMPOOL_DEBUG
109         CmiPrintf("[%d] current=%p size:%d ->%p \n", CmiMyPe(), current, current->size, (char*)current+current->size);
110 #endif
111         CmiAssert(current->size != 0);
112         if(current->size >= size)
113         {
114             bestfit_size = current->size;
115             bestfit = current;
116             bestfit_previous = previous;
117             break;
118         }
119         previous = current;
120         current = current->next_free?(mempool_header*)((char*)mptr + current->next_free):NULL;
121     }
122 #endif
123
124     if(bestfit == NULL)
125     {
126         void *pool;
127         mempool_block   *expand_pool;
128         size_t   expand_size;
129         gni_mem_handle_t  mem_hndl;
130
131         if (!expand) return NULL;
132
133         expand_size = size;
134 //      expand_size = expand_mem>size ? expand_mem:2*size; 
135         pool = mptr->newblockfn(&expand_size, &mem_hndl);
136         expand_pool = (mempool_block*)pool;
137         expand_pool->mempool_ptr = pool;
138         expand_pool->mem_hndl = mem_hndl;
139         expand_pool->size = expand_size;
140         expand_pool->next = NULL;
141 #if MEMPOOL_DEBUG
142         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);
143 #endif
144         // FIXME: go to the end of link list
145         while (mempools_head->next != NULL) mempools_head = mempools_head->next;
146         mempools_head->next = expand_pool;
147
148         bestfit = (mempool_header*)((char*)expand_pool->mempool_ptr + sizeof(mempool_block));
149         bestfit->size = expand_size-sizeof(mempool_block);
150         bestfit->mem_hndl = expand_pool->mem_hndl;
151         bestfit->next_free = 0;
152         //bestfit_size = expand_size;
153         bestfit_size = bestfit->size;
154 #if 0
155         current = freelist_head;
156         while(current!= NULL && current < bestfit )
157         {
158           previous = current;
159           current = current->next;
160         }
161 #else
162         CmiAssert(bestfit > previous);
163 #endif
164         bestfit_previous = previous;
165         if (previous == NULL)
166            *freelist_head = (char*)bestfit - (char*)mptr;
167         else
168            previous->next_free = (char*)bestfit-(char*)mptr;
169     }
170
171     //bestfit->size = size;
172     if(bestfit_size > (size + sizeof(mempool_header))) //deduct this entry 
173     {
174         mempool_header *ptr = (mempool_header *)((char*)bestfit + size);
175         ptr->size = bestfit_size - size;
176         ptr->mem_hndl = bestfit->mem_hndl;
177         ptr->next_free = bestfit->next_free;
178         if(bestfit == freelist_head_ptr || freelist_head_ptr == NULL)
179            *freelist_head = (char*)ptr - (char*)mptr;
180         if(bestfit_previous != NULL)
181            bestfit_previous->next_free = (char*)ptr - (char*)mptr;
182     }
183     else {  
184           //delete this free entry
185         if(bestfit == freelist_head_ptr)
186             *freelist_head = freelist_head_ptr->next_free;
187         else
188             bestfit_previous->next_free = bestfit->next_free;
189     }
190 #if  MEMPOOL_DEBUG
191     printf("[%d] ++MALLOC served: %d, ptr:%p\n", CmiMyPe(), size, bestfit);
192 printf("[%d] freelist_head in malloc  offset:%d free_head: %ld %ld %d %d\n", CmiMyPe(), (char*)bestfit-(char*)mptr, *freelist_head, ((mempool_header*)((char*)mptr+*freelist_head))->next_free, bestfit_size, size);
193 #endif
194     CmiAssert(*freelist_head >= 0);
195     return (void*)bestfit;
196 }
197
198 //sorted free_list and merge it if it become continous 
199 void mempool_free(mempool_type *mptr, void *ptr_free)
200 {
201     int i;
202     int merged = 0;
203     int free_size;
204     void *free_lastbytes_pos;
205     mempool_block     *mempools_head;
206     size_t    *freelist_head;
207     mempool_header    *freelist_head_ptr;
208     mempool_header    *current;
209     mempool_header *previous = NULL;
210     mempool_header *to_free = (mempool_header *)ptr_free;
211
212     mempools_head = &(mptr->mempools_head);
213     freelist_head = &mptr->freelist_head;
214     freelist_head_ptr = mptr->freelist_head?(mempool_header*)((char*)mptr+mptr->freelist_head):NULL;
215     current = freelist_head_ptr;
216
217     free_size = to_free->size;
218     free_lastbytes_pos = (char*)ptr_free +free_size;
219
220 #if  MEMPOOL_DEBUG
221     printf("[%d] INSIDE FREE ptr=%p, size=%d freehead=%p \n", CmiMyPe(), ptr_free, free_size, freelist_head);
222 #endif
223     
224     while(current!= NULL && current < to_free )
225     {
226 #if  MEMPOOL_DEBUG
227         CmiPrintf("[%d] previous=%p, current=%p size:%d %p\n", CmiMyPe(), previous, current, current->size, (char*)current+current->size);
228 #endif
229         previous = current;
230         current = current->next_free?(mempool_header*)((char*)mptr + current->next_free):NULL;
231     }
232 #if  MEMPOOL_DEBUG
233     if (current) CmiPrintf("[%d] previous=%p, current=%p size:%d %p\n", CmiMyPe(), previous, current, current->size, free_lastbytes_pos);
234 #endif
235     //continuos with previous free space 
236     if(previous!= NULL && (char*)previous+previous->size == ptr_free &&  memcmp(&previous->mem_hndl, &to_free->mem_hndl, sizeof(gni_mem_handle_t))==0 )
237     {
238         previous->size +=  free_size;
239         merged = 1;
240     }
241     else if(current!= NULL && free_lastbytes_pos == current && memcmp(&current->mem_hndl, &to_free->mem_hndl, sizeof(gni_mem_handle_t))==0)
242     {
243         to_free->size += current->size;
244         to_free->next_free = current->next_free;
245         current = to_free;
246         merged = 1;
247         if(previous == NULL)
248             *freelist_head = (char*)current - (char*)mptr;
249         else
250             previous->next_free = (char*)to_free - (char*)mptr;
251     }
252     //continous, merge
253     if(merged) {
254        if (previous!= NULL && current!= NULL && (char*)previous + previous->size  == (char *)current && memcmp(&previous->mem_hndl, &current->mem_hndl, sizeof(gni_mem_handle_t))==0)
255       {
256          previous->size += current->size;
257          previous->next_free = current->next_free;
258       }
259     }
260     else {
261           // no merge to previous, current, create new entry
262         to_free->next_free = current?(char*)current - (char*)mptr: 0;
263         if(previous == NULL)
264             *freelist_head = (char*)to_free - (char*)mptr;
265         else
266             previous->next_free = (char*)to_free - (char*)mptr;
267     }
268 #if  MEMPOOL_DEBUG
269     printf("[%d] Memory free done %p, freelist_head=%p\n", CmiMyPe(), ptr_free,  freelist_head);
270 #endif
271
272     CmiAssert(*freelist_head >= 0);
273 }
274