source: soft/giet_vm/giet_libs/malloc.c @ 570

Last change on this file since 570 was 541, checked in by bellefin, 10 years ago

Introducing user lever heap_init() into malloc library

  • Property svn:executable set to *
File size: 15.4 KB
Line 
1////////////////////////////////////////////////////////////////////////////////
2// File     : malloc.c
3// Date     : 05/03/2013
4// Author   : Jean-Baptiste Bréjon / alain greiner
5// Copyright (c) UPMC-LIP6
6////////////////////////////////////////////////////////////////////////////////
7
8#include "malloc.h"
9#include "stdio.h"
10#include "giet_config.h"
11
12// Global variables defining the heap descriptors array (one heap per cluster)
13giet_heap_t heap[X_SIZE][Y_SIZE];
14
15// Macro returning the smallest power of 2 larger or equal to size value
16#define GET_SIZE_INDEX(size)                (size <= 0x00000001) ? 0  :\
17                                            (size <= 0x00000002) ? 1  :\
18                                            (size <= 0x00000004) ? 2  :\
19                                            (size <= 0x00000008) ? 3  :\
20                                            (size <= 0x00000010) ? 4  :\
21                                            (size <= 0x00000020) ? 5  :\
22                                            (size <= 0x00000040) ? 6  :\
23                                            (size <= 0x00000080) ? 7  :\
24                                            (size <= 0x00000100) ? 8  :\
25                                            (size <= 0x00000200) ? 9  :\
26                                            (size <= 0x00000400) ? 10 :\
27                                            (size <= 0x00000800) ? 11 :\
28                                            (size <= 0x00001000) ? 12 :\
29                                            (size <= 0x00002000) ? 13 :\
30                                            (size <= 0x00004000) ? 14 :\
31                                            (size <= 0x00008000) ? 15 :\
32                                            (size <= 0x00010000) ? 16 :\
33                                            (size <= 0x00020000) ? 17 :\
34                                            (size <= 0x00040000) ? 18 :\
35                                            (size <= 0x00080000) ? 19 :\
36                                            (size <= 0x00100000) ? 20 :\
37                                            (size <= 0x00200000) ? 21 :\
38                                            (size <= 0x00400000) ? 22 :\
39                                            (size <= 0x00800000) ? 23 :\
40                                            (size <= 0x01000000) ? 24 :\
41                                            (size <= 0x02000000) ? 25 :\
42                                            (size <= 0x04000000) ? 26 :\
43                                            (size <= 0x08000000) ? 27 :\
44                                            (size <= 0x10000000) ? 28 :\
45                                            (size <= 0x20000000) ? 29 :\
46                                            (size <= 0x40000000) ? 30 :\
47                                            (size <= 0x80000000) ? 31 :\
48                                                                   32
49////////////////////////////////////////
50void display_free_array( unsigned int x,
51                         unsigned int y )
52{
53    giet_shr_printf(
54                " - heap_base   = %x\n"
55                " - heap_size   = %x\n"
56                " - alloc_base  = %x\n"
57                " - alloc_size  = %x\n"
58                " - free[0]     = %x\n"
59                " - free[1]     = %x\n"
60                " - free[2]     = %x\n"
61                " - free[3]     = %x\n"
62                " - free[4]     = %x\n"
63                " - free[5]     = %x\n"
64                " - free[6]     = %x\n"
65                " - free[7]     = %x\n"
66                " - free[8]     = %x\n"
67                " - free[9]     = %x\n"
68                " - free[10]    = %x\n"
69                " - free[11]    = %x\n"
70                " - free[12]    = %x\n"
71                " - free[13]    = %x\n"
72                " - free[14]    = %x\n"
73                " - free[15]    = %x\n"
74                " - free[16]    = %x\n"
75                " - free[17]    = %x\n"
76                " - free[18]    = %x\n"
77                " - free[19]    = %x\n"
78                " - free[20]    = %x\n"
79                " - free[21]    = %x\n"
80                " - free[22]    = %x\n"
81                " - free[23]    = %x\n",
82                heap[x][y].heap_base, heap[x][y].heap_size, 
83                heap[x][y].alloc_base, heap[x][y].alloc_size,
84                heap[x][y].free[0], heap[x][y].free[1], 
85                heap[x][y].free[2], heap[x][y].free[3],
86                heap[x][y].free[4], heap[x][y].free[5],
87                heap[x][y].free[6], heap[x][y].free[7],
88                heap[x][y].free[8], heap[x][y].free[9],
89                heap[x][y].free[10], heap[x][y].free[11],
90                heap[x][y].free[12], heap[x][y].free[13],
91                heap[x][y].free[14], heap[x][y].free[15],
92                heap[x][y].free[16], heap[x][y].free[17],
93                heap[x][y].free[18], heap[x][y].free[19],
94                heap[x][y].free[20], heap[x][y].free[21],
95                heap[x][y].free[22], heap[x][y].free[23] );
96}  // end display_free array()
97
98////////////////////////////////
99void heap_init( unsigned int x,
100                unsigned int y )
101{
102    unsigned int heap_base;        // heap segment base
103    unsigned int heap_size;        // heap segment size
104    unsigned int heap_index;       // size_index in free[array]
105
106    unsigned int alloc_base;       // alloc[] array base
107    unsigned int alloc_size;       // alloc[] array size
108    unsigned int alloc_index;      // size_index in free[array]
109
110    unsigned int index;            // iterator
111
112    // get heap_base, heap size, and heap index
113    giet_heap_info( &heap_base, &heap_size, x, y );
114    heap_index = GET_SIZE_INDEX( heap_size );
115
116#if GIET_DEBUG_USER_MALLOC
117giet_shr_printf("\n[DEBUG USER_MALLOC] Starting Heap[%d][%d] initialisation /"
118                " base = %x / size = %x\n", x, y, heap_base, heap_size );
119#endif
120
121    // checking heap segment constraints
122    if ( heap_size == 0 )                                    // heap segment exist
123    {
124        giet_exit("ERROR in malloc() : heap not found \n");
125    }
126    if ( heap_size != (1<<heap_index) )                      // heap size power of 2
127    {
128        giet_exit("ERROR in malloc() : heap size must be power of 2\n");
129    }
130    if ( heap_base % heap_size )                             // heap segment aligned
131    {
132        giet_exit("ERROR in malloc() : heap segment must be aligned\n");
133    }
134
135    // compute size of block containin alloc[] array
136    alloc_size = heap_size / MIN_BLOCK_SIZE;
137    if ( alloc_size < MIN_BLOCK_SIZE) alloc_size = MIN_BLOCK_SIZE;
138
139    // get index for the corresponding block
140    alloc_index = GET_SIZE_INDEX( alloc_size );
141
142    // compute alloc[] array base address
143    alloc_base = heap_base + heap_size - alloc_size;
144
145    // reset the free[] array
146    for ( index = 0 ; index < 32 ; index++ )
147    {
148        heap[x][y].free[index] = 0;
149    }
150
151    // split the heap into various sizes blocks,
152    // initializes the free[] array and NEXT pointers
153    // base is the block base address
154    unsigned int   base = heap_base;
155    unsigned int*  ptr;
156    for ( index = heap_index-1 ; index >= alloc_index ; index-- )
157    {
158        heap[x][y].free[index] = base;
159        ptr = (unsigned int*)base;
160        *ptr = 0;
161        base = base + (1<<index);
162    }
163
164    heap[x][y].init       = HEAP_INITIALIZED;
165    heap[x][y].x          = x;
166    heap[x][y].y          = y;
167    heap[x][y].heap_base  = heap_base;
168    heap[x][y].heap_size  = heap_size;
169    heap[x][y].alloc_size = alloc_size;
170    heap[x][y].alloc_base = alloc_base;
171
172    lock_init( &heap[x][y].lock );
173
174#if GIET_DEBUG_USER_MALLOC
175giet_shr_printf("\n[DEBUG USER_MALLOC] Completing Heap[%d][%d] initialisation\n", x, y );
176display_free_array(x,y);
177#endif
178               
179}  // end heap_init()
180
181////////////////////////////////////////////
182unsigned int split_block( giet_heap_t* heap,
183                          unsigned int vaddr, 
184                          unsigned int searched_index,
185                          unsigned int requested_index )
186{
187    // push the upper half block into free[searched_index-1]
188    unsigned int* new            = (unsigned int*)(vaddr + (1<<(searched_index-1)));
189    *new                         = heap->free[searched_index-1]; 
190    heap->free[searched_index-1] = (unsigned int)new;
191       
192    if ( searched_index == requested_index + 1 )  // terminal case: return lower half block
193    {
194        return vaddr;
195    }
196    else            // non terminal case : lower half block must be split again
197    {                               
198        return split_block( heap, vaddr, searched_index-1, requested_index );
199    }
200} // end split_block()
201
202//////////////////////////////////////////
203unsigned int get_block( giet_heap_t* heap,
204                        unsigned int searched_index,
205                        unsigned int requested_index )
206{
207    // test terminal case
208    if ( (1<<searched_index) > heap->heap_size )  // failure : return a NULL value
209    {
210        return 0;
211    }
212    else                            // search a block in free[searched_index]
213    {
214        unsigned int vaddr = heap->free[searched_index];
215        if ( vaddr == 0 )     // block not found : search in free[searched_index+1]
216        {
217            return get_block( heap, searched_index+1, requested_index );
218        }
219        else                // block found : pop it from free[searched_index]
220        {
221            // pop the block from free[searched_index]
222            unsigned int next = *((unsigned int*)vaddr); 
223            heap->free[searched_index] = next;
224           
225            // test if the block must be split
226            if ( searched_index == requested_index )  // no split required
227            {
228                return vaddr;
229            }
230            else                                      // split is required
231            {
232                return split_block( heap, vaddr, searched_index, requested_index );
233            }
234        } 
235    }
236} // end get_block()
237
238////////////////////////////////////////
239void * remote_malloc( unsigned int size,
240                      unsigned int x,
241                      unsigned int y ) 
242{
243
244#if GIET_DEBUG_USER_MALLOC
245giet_shr_printf("\n[DEBUG USER_MALLOC] Malloc request for Heap[%d][%d] / size = %x\n", 
246                 x, y, size );
247#endif
248
249    // checking arguments
250    if (size == 0) 
251    {
252        giet_exit("ERROR in malloc() : requested size = 0 \n");
253    }
254    if ( x >= X_SIZE )
255    {
256        giet_exit("ERROR in malloc() : x coordinate too large\n");
257    }
258    if ( y >= Y_SIZE )
259    {
260        giet_exit("ERROR in malloc() : y coordinate too large\n");
261    }
262
263    // checking initialization
264    if ( heap[x][y].init != HEAP_INITIALIZED )
265    {
266        giet_exit("ERROR in malloc() : heap not initialized\n");
267    }
268
269    // normalize size
270    if ( size < MIN_BLOCK_SIZE ) size = MIN_BLOCK_SIZE;
271
272    // compute requested_index for the free[] array
273    unsigned int requested_index = GET_SIZE_INDEX( size );
274
275    // take the lock protecting access to heap[x][y]
276    lock_acquire( &heap[x][y].lock );
277
278    // call the recursive function get_block
279    unsigned int base = get_block( &heap[x][y], 
280                                   requested_index, 
281                                   requested_index );
282
283    // update the alloc[] array if block found
284    if ( base != 0 )
285    {
286        unsigned offset = (base - heap[x][y].heap_base) / MIN_BLOCK_SIZE;
287        unsigned char* ptr = (unsigned char*)(heap[x][y].alloc_base + offset);
288        *ptr = requested_index;
289    }
290
291    // release the lock
292    lock_release( &heap[x][y].lock );
293 
294#if GIET_DEBUG_USER_MALLOC
295giet_shr_printf("\n[DEBUG USER_MALLOC] Malloc vaddr from Heap[%d][%d] = %x\n", 
296                x, y, base );
297display_free_array(x,y);
298#endif
299
300    return (void*)base;
301
302} // end remote_malloc()
303
304
305//////////////////////////////////
306void * malloc( unsigned int size )
307{
308    // get cluster coordinates
309    unsigned int    x;
310    unsigned int    y;
311    unsigned int    lpid;
312    giet_proc_xyp( &x, &y, &lpid );
313
314    return remote_malloc( size, x, y );
315} 
316
317///////////////////////////////////////////
318void update_free_array( giet_heap_t* heap,
319                        unsigned int base,
320                        unsigned int size_index )
321{
322    // This recursive function try to merge the released block
323    // with the companion block if this companion block is free.
324    // This companion has the same size, and almost the same address
325    // (only one address bit is different)
326    // - If the companion is not in free[size_index],
327    //   the released block is pushed in free[size_index].
328    // - If the companion is found, it is evicted from free[size_index]
329    //   and the merged bloc is pushed in the free[size_index+1].
330
331
332    // compute released block size
333    unsigned int size = 1<<size_index;
334
335    // compute companion_base and merged_base
336    unsigned int companion_base;   // companion block base address
337    unsigned int merged_base;      // merged block base address
338    if ( base % (size<<1) )
339    {
340        companion_base  = base + size;
341        merged_base     = base;
342    }
343    else
344    {
345        companion_base  = base - size;
346        merged_base     = base - size;
347    }
348
349    // scan all blocks in free[size_index]
350    // the iter & prev variables are actually addresses
351    unsigned int  found = 0;
352    unsigned int  iter  = heap->free[size_index];
353    unsigned int  prev  = (unsigned int)&heap->free[size_index];
354    while ( iter != 0 ) 
355    {
356        if ( iter == companion_base ) 
357        {
358            found = 1;
359            break;
360        }
361        iter = *(unsigned int*)iter;
362        prev = iter;
363    }
364
365    if ( found == 0 )  // Companion not found
366    {
367        // push the block in free[size_index] 
368        *(unsigned int*)base   = heap->free[size_index];
369        heap->free[size_index] = base;
370    }
371    else               // Companion found : merge
372    {
373        // evict the searched block from free[size_index]
374        *(unsigned int*)prev = *(unsigned int*)iter;
375
376        // call the update_free() function for free[size_index+1]
377        update_free_array( heap, merged_base , size_index+1 );
378    }
379}
380
381//////////////////////
382void free( void* ptr )
383{
384    // get the cluster coordinate from ptr value
385    unsigned int x;
386    unsigned int y;
387    giet_get_xy( ptr, &x, &y );
388
389#if GIET_DEBUG_USER_MALLOC
390giet_shr_printf("\n[DEBUG USER_MALLOC] Free for vaddr = %x / x = %d / y = %d\n",
391                 (unsigned int)ptr, x, y );
392#endif
393
394    // get the lock protecting heap[x][y]
395    lock_acquire( &heap[x][y].lock );
396
397    // check ptr value
398    unsigned int base = (unsigned int)ptr;
399    if ( (base < heap[x][y].heap_base) || 
400         (base >= (heap[x][y].heap_base + heap[x][y].heap_size)) )
401    {
402        giet_exit("ERROR in free() : illegal pointer for released block");
403    }
404 
405    // compute released block index in alloc[] array
406    unsigned index = (base - heap[x][y].heap_base ) / MIN_BLOCK_SIZE;
407 
408    // get the released block size_index
409    unsigned char* pchar      = (unsigned char*)(heap[x][y].alloc_base + index);
410    unsigned int   size_index = (unsigned int)*pchar;
411
412    // check released block alignment
413    if ( base % (1 << size_index) )
414    {
415        giet_exit("ERROR in free() : released block not aligned");
416    }
417
418    // call the recursive function update_free_array()
419    update_free_array( &heap[x][y], base, size_index ); 
420
421    // release the lock
422    lock_release( &heap[x][y].lock );
423
424#if GIET_DEBUG_USER_MALLOC
425display_free_array(x,y);
426#endif
427
428} // end free()
429
430
431
432
433// Local Variables:
434// tab-width: 4
435// c-basic-offset: 4
436// c-file-offsets:((innamespace . 0)(inline-open . 0))
437// indent-tabs-mode: nil
438// End:
439// vim: filetype=c:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
440
441
442
Note: See TracBrowser for help on using the repository browser.