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