fc9fd14aac29e9211cee9232ca5406259cd795e4
[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))%255, size);
110     return alloc_ptr;
111 }
112
113 //sorted free_list and merge it if it become continous 
114 void mempool_free(void *ptr_free)
115 {
116     int i;
117     int merged = 0;
118     int free_size;
119     void *free_firstbytes_pos = ptr_free-SIZE_BYTES;
120     void *free_lastbytes_pos;
121     free_block_entry *new_entry; 
122     free_block_entry *current = freelist_head;
123     free_block_entry *previous = NULL;
124     
125     memcpy(&free_size, free_firstbytes_pos, SIZE_BYTES);
126     printf("--FREE request :ptr=%p, size=%d\n", ptr_free, free_size); 
127     free_lastbytes_pos = ptr_free +free_size;
128
129     for(i=0; i<free_size; i++)
130     {
131         if( (int)(*((char*)ptr_free+i)) != ((long int)(ptr_free+free_size))%255)
132         {
133             printf("verifying fails\n");
134             exit(2);
135         }
136     }
137
138     while(current!= NULL && current->mempool_ptr < ptr_free )
139     {
140         previous = current;
141         current = current->next;
142     }
143     //continuos with previous free space 
144     if(previous!= NULL && previous->mempool_ptr + previous->size  == free_firstbytes_pos)
145     {
146         previous->size += (free_size + SIZE_BYTES);
147         merged = 1;
148     }
149     
150     if(current!= NULL && free_lastbytes_pos == current->mempool_ptr)
151     {
152         current->mempool_ptr = free_firstbytes_pos;
153         current->size +=  (free_size + SIZE_BYTES);
154         merged = 1;
155     }
156     //continous, merge
157     if(previous!= NULL && current!= NULL && previous->mempool_ptr + previous->size  == current->mempool_ptr)
158     {
159        previous->size += current->size;
160        previous->next = current->next;
161        free(current);
162     }
163     // no merge to previous, current, create new entry
164     if(merged == 0)
165     {
166         new_entry = malloc(sizeof(free_block_entry));
167         new_entry->mempool_ptr = free_firstbytes_pos;
168         new_entry->size = free_size + SIZE_BYTES;
169         new_entry->next = current;
170         if(previous == NULL)
171             freelist_head = new_entry;
172         else
173             previous->next = new_entry;
174     }
175 }
176
177
178 // external interface 
179 void* syh_malloc(int size)
180 {
181     int pool_index;
182     if(size < 1024*512)
183     {
184         pool_index = 0;
185     }else 
186         pool_index = 1;
187
188     mempool = mempools_data[pool_index].mempool_base_addr;
189     freelist_head = mempools_data[pool_index].freelist_head;
190     
191     if(mempool == NULL)
192     {
193         init_mempool(MEMPOOL_SIZE[pool_index]);
194         mempools_data[pool_index].mempool_base_addr = mempool;
195         mempools_data[pool_index].freelist_head = freelist_head;
196     }   
197     return mempool_malloc(size);
198 }
199
200 void syh_free(void *ptr)
201 {
202     int i=0;
203     for(i=0; i<2; i++)
204     {
205         if(ptr> mempools_data[i].mempool_base_addr && ptr< mempools_data[i].mempool_base_addr + MEMPOOL_SIZE[i])
206         {
207             mempool = mempools_data[i].mempool_base_addr;
208             freelist_head = mempools_data[i].freelist_head;
209             break;
210         }
211     }
212     mempool_free(ptr);
213 }
214 #define MAX_BINS  32
215 void*  malloc_list[32];
216 int    empty_pos = 0;
217
218 int main(int argc, char* argv[])
219 {
220
221     void *ptr;
222     int iter = atoi(argv[1]);
223     int i, size;
224     //init_mempool();
225     //srand(time(NULL));    
226     
227     for(i=0; i<iter; i++)
228     {
229         size = (rand()%(9)) + 8;
230         if(empty_pos == MAX_BINS)
231         {
232             empty_pos--;
233             syh_free(malloc_list[empty_pos]);
234         }
235         while( (malloc_list[empty_pos] = syh_malloc(size)) == NULL)
236         {
237             empty_pos--;
238             syh_free(malloc_list[empty_pos]);
239         }
240         empty_pos++;
241         if(rand()%3 == 0 && empty_pos>0)
242         {
243             empty_pos--;
244             syh_free(malloc_list[empty_pos]);
245         }
246     }
247
248     kill_allmempool();
249 }