fix a verify problem in mempool in gemini
[charm.git] / src / arch / gemini_gni / mempool.c
1 /*****************************************************************************
2  * $Source$
3  * $Author$ Yanhua Sun 
4  * $Date$   08-27-2011
5  * $Revision$
6  *****************************************************************************/
7
8 #include <time.h>
9 #include <stdio.h>
10 #include <stdlib.h>
11 #include <string.h>
12 #define SIZE_BYTES       4
13 #define POOLS_NUM       2
14 #define MAX_INT        2147483647
15 // for small memory allocation, large allocation
16 int MEMPOOL_SIZE[POOLS_NUM] = {536870912, 536870912};
17
18 typedef struct free_block_t 
19 {
20     int     size;
21     void    *mempool_ptr;   //where this entry points to
22     struct  free_block_t *next;
23 } free_block_entry;
24
25 // multiple mempool for different size allocation
26 typedef struct mempool_block_t
27 {
28     void                *mempool_base_addr;
29     free_block_entry    *freelist_head;
30 }mempool_block;
31
32 mempool_block       mempools_data[2];
33
34 void                *mempool;
35 free_block_entry    *freelist_head;
36
37 void init_mempool( int pool_size)
38 {
39     mempool = malloc(pool_size);
40
41     printf("Mempool init with base_addr=%p\n\n", mempool);
42     freelist_head           = (free_block_entry*)malloc(sizeof(free_block_entry));
43     freelist_head->size     = pool_size;
44     freelist_head->mempool_ptr = mempool;
45     freelist_head->next     = NULL;
46 }
47
48 void kill_allmempool()
49 {
50     int i;
51     for(i=0; i<POOLS_NUM; i++)
52     {
53         if(mempools_data[i].mempool_base_addr != NULL)
54             free(mempools_data[i].mempool_base_addr);
55     }
56     //all free entry
57 }
58
59 // append size before the real memory buffer
60 void*  mempool_malloc(int size)
61 {
62     int     real_size = size + SIZE_BYTES;
63     void    *alloc_ptr;
64     int     bestfit_size = MAX_INT; //most close size  
65     free_block_entry *current = freelist_head;
66     free_block_entry *previous = NULL;
67     
68     free_block_entry *bestfit = NULL;
69     free_block_entry *bestfit_previous = NULL;
70     printf("+MALLOC request :%d\n", size);
71     if(current == NULL)
72     {
73         printf("Mempool overflow exit\n");
74         return NULL;
75     }
76     while(current!= NULL)
77     {
78         if(current->size >= real_size && current->size<bestfit_size)
79         {
80             bestfit_size = current->size;
81             bestfit = current;
82             bestfit_previous = previous;
83         }
84         previous = current;
85         current = current->next;
86     }
87     if(bestfit == NULL)
88     {
89         printf("No memory has such free empty chunck of %d\n", size);
90         return NULL;
91     }
92
93     alloc_ptr = bestfit->mempool_ptr+SIZE_BYTES;
94     memcpy(bestfit->mempool_ptr, &size, SIZE_BYTES);
95     if(bestfit->size > real_size) //deduct this entry 
96     {
97         bestfit->size -= real_size;
98         bestfit->mempool_ptr += real_size;
99     }else   //delete this free entry
100     {
101         if(bestfit == freelist_head)
102             freelist_head = NULL;
103         else
104             bestfit_previous ->next = bestfit->next;
105         free(bestfit);
106     }
107     printf("++MALLOC served: %d, ptr:%p\n", size, alloc_ptr);
108
109     //memset(alloc_ptr, ((long int)(alloc_ptr+size))%126, size);
110     //printf("Memset, %p, %d vs=%ld, vr=%ld\n", alloc_ptr, size, ((long int)(alloc_ptr+size))%126,  (*((char*)alloc_ptr)));
111     return alloc_ptr;
112 }
113
114 //sorted free_list and merge it if it become continous 
115 void mempool_free(void *ptr_free)
116 {
117     int i;
118     int merged = 0;
119     int free_size;
120     void *free_firstbytes_pos = ptr_free-SIZE_BYTES;
121     void *free_lastbytes_pos;
122     free_block_entry *new_entry; 
123     free_block_entry *current = freelist_head;
124     free_block_entry *previous = NULL;
125     
126     memcpy(&free_size, free_firstbytes_pos, SIZE_BYTES);
127     printf("--FREE request :ptr=%p, size=%d\n", ptr_free, free_size); 
128     free_lastbytes_pos = ptr_free +free_size;
129
130     /*
131     for(i=0; i<free_size; i++)
132     {
133         if( (long int)(*((char*)ptr_free+i)) != ((long int)(ptr_free+free_size))%126)
134         {
135             printf("verifying fails, %p, %d vs=%ld, vr=%ld\n", ptr_free, free_size, ((long int)(ptr_free+free_size))%126,  (long int)(*((char*)ptr_free+i)));
136             exit(2);
137         }
138     }
139 */
140     while(current!= NULL && current->mempool_ptr < ptr_free )
141     {
142         previous = current;
143         current = current->next;
144     }
145     //continuos with previous free space 
146     if(previous!= NULL && previous->mempool_ptr + previous->size  == free_firstbytes_pos)
147     {
148         previous->size += (free_size + SIZE_BYTES);
149         merged = 1;
150     }
151     
152     if(current!= NULL && free_lastbytes_pos == current->mempool_ptr)
153     {
154         current->mempool_ptr = free_firstbytes_pos;
155         current->size +=  (free_size + SIZE_BYTES);
156         merged = 1;
157     }
158     //continous, merge
159     if(previous!= NULL && current!= NULL && previous->mempool_ptr + previous->size  == current->mempool_ptr)
160     {
161        previous->size += current->size;
162        previous->next = current->next;
163        free(current);
164     }
165     // no merge to previous, current, create new entry
166     if(merged == 0)
167     {
168         new_entry = malloc(sizeof(free_block_entry));
169         new_entry->mempool_ptr = free_firstbytes_pos;
170         new_entry->size = free_size + SIZE_BYTES;
171         new_entry->next = current;
172         if(previous == NULL)
173             freelist_head = new_entry;
174         else
175             previous->next = new_entry;
176     }
177 }
178
179
180 // external interface 
181 void* syh_malloc(int size)
182 {
183     int pool_index;
184     if(size < 1024*512)
185     {
186         pool_index = 0;
187     }else 
188         pool_index = 1;
189
190     mempool = mempools_data[pool_index].mempool_base_addr;
191     freelist_head = mempools_data[pool_index].freelist_head;
192     
193     if(mempool == NULL)
194     {
195         init_mempool(MEMPOOL_SIZE[pool_index]);
196         mempools_data[pool_index].mempool_base_addr = mempool;
197         mempools_data[pool_index].freelist_head = freelist_head;
198     }   
199     return mempool_malloc(size);
200 }
201
202 void syh_free(void *ptr)
203 {
204     int i=0;
205     for(i=0; i<2; i++)
206     {
207         if(ptr> mempools_data[i].mempool_base_addr && ptr< mempools_data[i].mempool_base_addr + MEMPOOL_SIZE[i])
208         {
209             mempool = mempools_data[i].mempool_base_addr;
210             freelist_head = mempools_data[i].freelist_head;
211             break;
212         }
213     }
214     mempool_free(ptr);
215 }
216 #define MAX_BINS  32
217 void*  malloc_list[32];
218 int    empty_pos = 0;
219
220 int main(int argc, char* argv[])
221 {
222
223     void *ptr;
224     int iter = atoi(argv[1]);
225     int i, size;
226     //init_mempool();
227     //srand(time(NULL));    
228     
229     for(i=0; i<iter; i++)
230     {
231         size = (rand()%(9)) + 8;
232         if(empty_pos == MAX_BINS)
233         {
234             empty_pos--;
235             syh_free(malloc_list[empty_pos]);
236         }
237         while( (malloc_list[empty_pos] = syh_malloc(size)) == NULL)
238         {
239             empty_pos--;
240             syh_free(malloc_list[empty_pos]);
241         }
242         empty_pos++;
243         if(rand()%3 == 0 && empty_pos>0)
244         {
245             empty_pos--;
246             syh_free(malloc_list[empty_pos]);
247         }
248     }
249
250     kill_allmempool();
251 }