13f065e08b60b233135a880d289aa9e8d8f91c1c
[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 static      size_t     expand_mem = 1024ll*1024*16;
28
29 mempool_type *mempool_init(size_t pool_size, mempool_newblockfn allocfn, mempool_freeblock freefn)
30 {
31     mempool_type *mptr;
32     mempool_header *header;
33     mem_handle_t  mem_hndl;
34
35     void *pool = allocfn(&pool_size, &mem_hndl);
36     mptr = (mempool_type*)pool;
37     mptr->newblockfn = allocfn;
38     mptr->freeblockfn = freefn;
39     mptr->mempools_head.mempool_ptr = pool;
40     mptr->mempools_head.mem_hndl = mem_hndl;
41     mptr->mempools_head.size = pool_size;
42     mptr->mempools_head.memblock_next = 0;
43     header = (mempool_header *) ((char*)pool+sizeof(mempool_type));
44     mptr->freelist_head = sizeof(mempool_type);
45     mptr->memblock_tail = 0;
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 mempool_destroy(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->memblock_next?(mempool_block *)((char*)mptr+mempools_head->memblock_next):NULL;
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     size += sizeof(mempool_header);
86
87 #if 1
88     while(current!= NULL)     /* best fit */
89     {
90 #if  MEMPOOL_DEBUG
91         CmiPrintf("[%d] current=%p size:%d \n", CmiMyPe(), current, current->size);
92 #endif
93         if(current->size >= size && current->size < bestfit_size)
94         {
95             bestfit_size = current->size;
96             bestfit = current;
97             bestfit_previous = previous;
98         }
99         previous = current;
100         current = current->next_free?(mempool_header*)((char*)mptr + current->next_free):NULL;
101     }
102 #else
103     while(current!= NULL)             /*  first fit */
104     {
105 #if  MEMPOOL_DEBUG
106         CmiPrintf("[%d] current=%p size:%d ->%p \n", CmiMyPe(), current, current->size, (char*)current+current->size);
107 #endif
108         CmiAssert(current->size != 0);
109         if(current->size >= size)
110         {
111             bestfit_size = current->size;
112             bestfit = current;
113             bestfit_previous = previous;
114             break;
115         }
116         previous = current;
117         current = current->next_free?(mempool_header*)((char*)mptr + current->next_free):NULL;
118     }
119 #endif
120
121     if(bestfit == NULL)
122     {
123         void *pool;
124         mempool_block   *expand_pool, *memblock_tail;
125         size_t   expand_size;
126         mem_handle_t  mem_hndl;
127
128         if (!expand) return NULL;
129
130         expand_size = expand_mem>size ? expand_mem:2*size; 
131         pool = mptr->newblockfn(&expand_size, &mem_hndl);
132         expand_pool = (mempool_block*)pool;
133         expand_pool->mempool_ptr = pool;
134         expand_pool->mem_hndl = mem_hndl;
135         expand_pool->size = expand_size;
136         expand_pool->memblock_next = 0;
137         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);
138
139          /* insert new block to memblock tail */
140         memblock_tail = (mempool_block*)((char*)mptr + mptr->memblock_tail);
141         memblock_tail->memblock_next = mptr->memblock_tail = (char*)expand_pool - (char*)mptr;
142
143         bestfit = (mempool_header*)((char*)expand_pool->mempool_ptr + sizeof(mempool_block));
144         bestfit->size = expand_size-sizeof(mempool_block);
145         bestfit->mem_hndl = expand_pool->mem_hndl;
146         bestfit->next_free = 0;
147         bestfit_size = expand_size-sizeof(mempool_block);
148 #if 1
149          /* insert bestfit to sorted free list */
150         previous = NULL;
151         current = freelist_head_ptr;
152         while (current) 
153         {
154             if (current > bestfit) break;
155             previous = current;
156             current = current->next_free?(mempool_header*)((char *)mptr + current->next_free):NULL;
157         };
158         bestfit->next_free = current!=NULL? (char*)current-(char*)mptr:0;
159 #else
160         CmiAssert(bestfit > previous);
161         previous->next_free = (char*)bestfit-(char*)mptr;
162 #endif
163         bestfit_previous = previous;
164         if (previous == NULL) {
165            *freelist_head = (char*)bestfit - (char*)mptr;
166            freelist_head_ptr =  bestfit;
167         }
168         else
169            previous->next_free = (char*)bestfit-(char*)mptr;
170     }
171
172     bestfit->size = size;
173     if(bestfit_size > size + sizeof(mempool_header)) //deduct this entry 
174     {
175         mempool_header *ptr = (mempool_header *)((char*)bestfit + size);
176         ptr->size = bestfit_size - size;
177         ptr->mem_hndl = bestfit->mem_hndl;
178         ptr->next_free = bestfit->next_free;
179         if(bestfit == freelist_head_ptr)
180            *freelist_head = (char*)ptr - (char*)mptr;
181         if(bestfit_previous != NULL)
182            bestfit_previous->next_free = (char*)ptr - (char*)mptr;
183     }
184     else {  
185           //delete this free entry
186         if (bestfit_size > size) {
187            bestfit->size = bestfit_size;
188         }
189         if(bestfit == freelist_head_ptr)
190             *freelist_head = freelist_head_ptr->next_free;
191         else
192             bestfit_previous->next_free = bestfit->next_free;
193     }
194 #if  MEMPOOL_DEBUG
195     printf("[%d] ++MALLOC served: %d, ptr:%p\n", CmiMyPe(), size, bestfit);
196 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);
197 #endif
198     CmiAssert(*freelist_head >= 0);
199     return (char*)bestfit + sizeof(mempool_header);
200 }
201
202 //sorted free_list and merge it if it become continous 
203 void mempool_free(mempool_type *mptr, void *ptr_free)
204 {
205     int i;
206     int merged = 0;
207     int free_size;
208     void *free_lastbytes_pos;
209     mempool_block     *mempools_head;
210     size_t    *freelist_head;
211     mempool_header    *freelist_head_ptr;
212     mempool_header    *current;
213     mempool_header *previous = NULL;
214     mempool_header *to_free;
215
216     to_free = (mempool_header *)((char*)ptr_free - sizeof(mempool_header));
217
218     mempools_head = &(mptr->mempools_head);
219     freelist_head = &mptr->freelist_head;
220     freelist_head_ptr = mptr->freelist_head?(mempool_header*)((char*)mptr+mptr->freelist_head):NULL;
221     current = freelist_head_ptr;
222
223     free_size = to_free->size;
224     free_lastbytes_pos = (char*)to_free +free_size;
225
226 #if  MEMPOOL_DEBUG
227     printf("[%d] INSIDE FREE ptr=%p, size=%d freehead=%p mutex: %p\n", CmiMyPe(), to_free, free_size, freelist_head, mptr->mutex);
228 #endif
229     
230     while(current!= NULL && current < to_free )
231     {
232 #if  MEMPOOL_DEBUG
233         CmiPrintf("[%d] previous=%p, current=%p size:%d %p\n", CmiMyPe(), previous, current, current->size, (char*)current+current->size);
234 #endif
235         previous = current;
236         current = current->next_free?(mempool_header*)((char*)mptr + current->next_free):NULL;
237     }
238 #if  MEMPOOL_DEBUG
239     if (current) CmiPrintf("[%d] previous=%p, current=%p size:%d %p\n", CmiMyPe(), previous, current, current->size, free_lastbytes_pos);
240 #endif
241     //continuos with previous free space 
242     if(previous!= NULL && (char*)previous+previous->size == (char*)to_free &&  memcmp(&previous->mem_hndl, &to_free->mem_hndl, sizeof(mem_handle_t))==0 )
243     {
244         previous->size +=  free_size;
245         merged = 1;
246     }
247     else if(current!= NULL && free_lastbytes_pos == current && memcmp(&current->mem_hndl, &to_free->mem_hndl, sizeof(mem_handle_t))==0)
248     {
249         to_free->size += current->size;
250         to_free->next_free = current->next_free;
251         current = to_free;
252         merged = 1;
253         if(previous == NULL)
254             *freelist_head = (char*)current - (char*)mptr;
255         else
256             previous->next_free = (char*)to_free - (char*)mptr;
257     }
258     //continous, merge
259     if(merged) {
260        if (previous!= NULL && current!= NULL && (char*)previous + previous->size  == (char *)current && memcmp(&previous->mem_hndl, &current->mem_hndl, sizeof(mem_handle_t))==0)
261       {
262          previous->size += current->size;
263          previous->next_free = current->next_free;
264       }
265     }
266     else {
267           // no merge to previous, current, create new entry
268         to_free->next_free = current?(char*)current - (char*)mptr: 0;
269         if(previous == NULL)
270             *freelist_head = (char*)to_free - (char*)mptr;
271         else
272             previous->next_free = (char*)to_free - (char*)mptr;
273     }
274 #if  MEMPOOL_DEBUG
275     printf("[%d] Memory free done %p, freelist_head=%p\n", CmiMyPe(), to_free,  freelist_head);
276 #endif
277
278     CmiAssert(*freelist_head >= 0);
279 }
280