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

Last change on this file since 768 was 709, checked in by alain, 9 years ago

Major release: Change the task model to implement the POSIX threads API.

  • The shell "exec" and "kill" commands can be used to activate/de-activate the applications.
  • The "pause", "resume", and "context" commands can be used to stop, restart, a single thtead or to display the thread context.

This version has been tested on the following multi-threaded applications,
that have been modified to use the POSIX threads:

  • classif
  • convol
  • transpose
  • gameoflife
  • raycast
  • Property svn:executable set to *
File size: 14.8 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    unsigned int next;
54    unsigned int id;
55    unsigned int iter;
56
57    giet_tty_printf("\nUser Heap[%d][%d] base = %x / size = %x\n", x , y , 
58                   heap[x][y].heap_base, heap[x][y].heap_size );
59    for ( id = 0 ; id < 32 ; id++ )
60    { 
61        next = heap[x][y].free[id];
62        giet_tty_printf(" - free[%d] = " , id );
63        iter = 0;
64        while ( next != 0 )
65        {
66            giet_tty_printf("%x | ", next );
67            next = (*(unsigned int*)next);
68            iter++;
69        }
70        giet_tty_printf("0\n");
71    }
72}  // end display_free_array()
73
74
75
76////////////////////////////////
77void heap_init( unsigned int x,
78                unsigned int y )
79{
80    unsigned int heap_base;        // heap segment base
81    unsigned int heap_size;        // heap segment size
82    unsigned int heap_index;       // size_index in free[array]
83
84    unsigned int alloc_base;       // alloc[] array base
85    unsigned int alloc_size;       // alloc[] array size
86    unsigned int alloc_index;      // size_index in alloc[array]
87
88    unsigned int index;            // iterator
89
90    // get heap_base, heap size, and heap index
91    giet_heap_info( &heap_base, &heap_size, x, y );
92    heap_index = GET_SIZE_INDEX( heap_size );
93
94#if GIET_DEBUG_USER_MALLOC
95giet_tty_printf("\n[DEBUG USER_MALLOC] Starting Heap[%d][%d] initialisation /"
96                " base = %x / size = %x\n", x, y, heap_base, heap_size );
97#endif
98
99    // checking heap segment constraints
100    giet_pthread_assert( (heap_size != 0) , 
101                         "error in heap_init() : heap not found"); 
102    giet_pthread_assert( (heap_size == (1<<heap_index)) ,
103                         "error in heap_init() : heap size must be power of 2");
104    giet_pthread_assert( (heap_base%heap_size == 0) ,
105                         "error in heap_init() : heap segment must be aligned\n");
106
107    // compute size of block containin alloc[] array
108    alloc_size = heap_size / MIN_BLOCK_SIZE;
109    if ( alloc_size < MIN_BLOCK_SIZE) alloc_size = MIN_BLOCK_SIZE;
110
111    // get index for the corresponding block
112    alloc_index = GET_SIZE_INDEX( alloc_size );
113
114    // compute alloc[] array base address
115    alloc_base = heap_base + heap_size - alloc_size;
116
117    // reset the free[] array
118    for ( index = 0 ; index < 32 ; index++ )
119    {
120        heap[x][y].free[index] = 0;
121    }
122
123    // reset the alloc_size array
124    unsigned int   word;
125    unsigned int*  tab = (unsigned int*)alloc_base;
126    for ( word = 0 ; word < (alloc_size>>2) ; word++ )  tab[word] = 0;
127 
128    // split the heap into various sizes blocks,
129    // initializes the free[] array and NEXT pointers
130    // base is the block base address
131    unsigned int   base = heap_base;
132    unsigned int*  ptr;
133    for ( index = heap_index-1 ; index >= alloc_index ; index-- )
134    {
135        heap[x][y].free[index] = base;
136        ptr = (unsigned int*)base;
137        *ptr = 0;
138        base = base + (1<<index);
139    }
140
141    heap[x][y].init       = HEAP_INITIALIZED;
142    heap[x][y].x          = x;
143    heap[x][y].y          = y;
144    heap[x][y].heap_base  = heap_base;
145    heap[x][y].heap_size  = heap_size;
146    heap[x][y].alloc_size = alloc_size;
147    heap[x][y].alloc_base = alloc_base;
148
149    lock_init( &heap[x][y].lock );
150
151#if GIET_DEBUG_USER_MALLOC
152giet_tty_printf("\n[DEBUG USER_MALLOC] Completing Heap[%d][%d] initialisation\n", x, y );
153display_free_array(x,y);
154#endif
155               
156}  // end heap_init()
157
158////////////////////////////////////////////
159unsigned int split_block( giet_heap_t* heap,
160                          unsigned int vaddr, 
161                          unsigned int searched_index,
162                          unsigned int requested_index )
163{
164    // push the upper half block into free[searched_index-1]
165    unsigned int* new            = (unsigned int*)(vaddr + (1<<(searched_index-1)));
166    *new                         = heap->free[searched_index-1]; 
167    heap->free[searched_index-1] = (unsigned int)new;
168       
169    if ( searched_index == requested_index + 1 )  // terminal case: return lower half block
170    {
171        return vaddr;
172    }
173    else            // non terminal case : lower half block must be split again
174    {                               
175        return split_block( heap, vaddr, searched_index-1, requested_index );
176    }
177} // end split_block()
178
179//////////////////////////////////////////
180unsigned int get_block( giet_heap_t* heap,
181                        unsigned int searched_index,
182                        unsigned int requested_index )
183{
184    // test terminal case
185    if ( (1<<searched_index) > heap->heap_size )  // failure : return a NULL value
186    {
187        return 0;
188    }
189    else                            // search a block in free[searched_index]
190    {
191        unsigned int vaddr = heap->free[searched_index];
192        if ( vaddr == 0 )     // block not found : search in free[searched_index+1]
193        {
194            return get_block( heap, searched_index+1, requested_index );
195        }
196        else                // block found : pop it from free[searched_index]
197        {
198            // pop the block from free[searched_index]
199            unsigned int next = *((unsigned int*)vaddr); 
200            heap->free[searched_index] = next;
201           
202            // test if the block must be split
203            if ( searched_index == requested_index )  // no split required
204            {
205                return vaddr;
206            }
207            else                                      // split is required
208            {
209                return split_block( heap, vaddr, searched_index, requested_index );
210            }
211        } 
212    }
213} // end get_block()
214
215////////////////////////////////////////
216void * remote_malloc( unsigned int size,
217                      unsigned int x,
218                      unsigned int y ) 
219{
220
221#if GIET_DEBUG_USER_MALLOC
222giet_tty_printf("\n[DEBUG USER_MALLOC] request for Heap[%d][%d] / size = %x\n", 
223                 x, y, size );
224#endif
225
226    // checking arguments
227    giet_pthread_assert( (size != 0) ,
228                         "error in remote_malloc() : requested size = 0 \n");
229    giet_pthread_assert( (x < X_SIZE) ,
230                         "error in remote_malloc() : x coordinate too large\n");
231    giet_pthread_assert( (y < Y_SIZE) ,
232                         "error in remote_malloc() : y coordinate too large\n");
233    giet_pthread_assert( (heap[x][y].init == HEAP_INITIALIZED) ,
234                         "error in remote_malloc() : heap not initialized\n");
235
236    // normalize size
237    if ( size < MIN_BLOCK_SIZE ) size = MIN_BLOCK_SIZE;
238
239    // compute requested_index for the free[] array
240    unsigned int requested_index = GET_SIZE_INDEX( size );
241
242    // take the lock protecting access to heap[x][y]
243    lock_acquire( &heap[x][y].lock );
244
245    // call the recursive function get_block
246    unsigned int base = get_block( &heap[x][y], 
247                                   requested_index, 
248                                   requested_index );
249
250    // check block found
251    if (base == 0)
252    {
253        lock_release( &heap[x][y].lock );
254        giet_pthread_assert( 0 , "error in remote_malloc() : no more space\n" );
255    }
256
257    // compute pointer in alloc[] array
258    unsigned offset    = (base - heap[x][y].heap_base) / MIN_BLOCK_SIZE;
259    unsigned char* ptr = (unsigned char*)(heap[x][y].alloc_base + offset);
260
261    // check the alloc[] array
262    if ( *ptr != 0 )
263    {
264        lock_release( &heap[x][y].lock );
265        giet_pthread_assert( 0 , "error in remote_malloc() : block already allocated");
266    }
267
268    // update alloc_array
269    *ptr = requested_index;
270
271    // release the lock
272    lock_release( &heap[x][y].lock );
273 
274#if GIET_DEBUG_USER_MALLOC
275giet_tty_printf("\n[DEBUG USER_MALLOC] allocated block from heap[%d][%d] : "
276                "base = %x / size = %x\n", x , y , base , size );
277display_free_array(x,y);
278#endif
279
280    return (void*)base;
281
282} // end remote_malloc()
283
284
285//////////////////////////////////
286void * malloc( unsigned int size )
287{
288    // get cluster coordinates
289    unsigned int    x;
290    unsigned int    y;
291    unsigned int    lpid;
292    giet_proc_xyp( &x, &y, &lpid );
293
294    return remote_malloc( size, x, y );
295} 
296
297///////////////////////////////////////////
298void update_free_array( giet_heap_t* heap,
299                        unsigned int base,
300                        unsigned int size_index )
301{
302    // This recursive function try to merge the released block
303    // with the companion block if this companion block is free.
304    // This companion has the same size, and almost the same address
305    // (only one address bit is different)
306    // - If the companion is not in free[size_index],
307    //   the released block is pushed in free[size_index].
308    // - If the companion is found, it is evicted from free[size_index]
309    //   and the merged bloc is pushed in the free[size_index+1].
310
311
312    // compute released block size
313    unsigned int size = 1<<size_index;
314
315    // compute companion block and merged block base addresses
316    unsigned int companion_base; 
317    unsigned int merged_base; 
318
319    if ( (base & size) == 0 )   // the released block is aligned on (2*size)
320    {
321        companion_base  = base + size;
322        merged_base     = base;
323    }
324    else
325    {
326        companion_base  = base - size;
327        merged_base     = base - size;
328    }
329
330    // scan all blocks in free[size_index]
331    // the iter & prev variables are actually addresses
332    unsigned int  found = 0;
333    unsigned int  iter  = heap->free[size_index];
334    unsigned int  prev  = (unsigned int)&heap->free[size_index];
335    while ( iter ) 
336    {
337        if ( iter == companion_base ) 
338        {
339            found = 1;
340            break;
341        }
342        prev = iter;
343        iter = *(unsigned int*)iter;
344    }
345
346    if ( found == 0 )  // Companion not found => push in free[size_index] 
347    {
348        *(unsigned int*)base   = heap->free[size_index];
349        heap->free[size_index] = base;
350    }
351    else               // Companion found : merge
352    {
353        // evict the searched block from free[size_index]
354        *(unsigned int*)prev = *(unsigned int*)iter;
355
356        // call the update_free() function for free[size_index+1]
357        update_free_array( heap, merged_base , size_index+1 );
358    }
359}
360
361//////////////////////
362void free( void* ptr )
363{
364    // get the cluster coordinate from ptr value
365    unsigned int x;
366    unsigned int y;
367    giet_get_xy( ptr, &x, &y );
368
369#if GIET_DEBUG_USER_MALLOC
370giet_tty_printf("\n[DEBUG USER_MALLOC] Free for vaddr = %x / x = %d / y = %d\n",
371                 (unsigned int)ptr, x, y );
372#endif
373
374    // check ptr value
375    unsigned int base = (unsigned int)ptr;
376    giet_pthread_assert( (base >= heap[x][y].heap_base) && 
377                         (base < (heap[x][y].heap_base + heap[x][y].heap_size)) ,
378                         "error in free() : illegal pointer for released block" );
379 
380    // get the lock protecting heap[x][y]
381    lock_acquire( &heap[x][y].lock );
382
383    // compute released block index in alloc[] array
384    unsigned index = (base - heap[x][y].heap_base ) / MIN_BLOCK_SIZE;
385 
386    // get the released block size_index
387    unsigned char* pchar      = (unsigned char*)(heap[x][y].alloc_base + index);
388    unsigned int   size_index = (unsigned int)*pchar;
389
390    // check block allocation
391    if ( size_index == 0 )
392    {
393        lock_release( &heap[x][y].lock );
394        giet_pthread_assert( 0 , "error in free() : released block not allocated");
395    }
396
397    // check released block alignment
398    if ( base % (1 << size_index) )
399    {
400        lock_release( &heap[x][y].lock );
401        giet_pthread_assert( 0 , "error in free() : released block not aligned");
402    }
403
404    // call the recursive function update_free_array()
405    update_free_array( &heap[x][y], base, size_index ); 
406
407    // release the lock
408    lock_release( &heap[x][y].lock );
409
410#if GIET_DEBUG_USER_MALLOC
411display_free_array(x,y);
412#endif
413
414} // end free()
415
416// Local Variables:
417// tab-width: 4
418// c-basic-offset: 4
419// c-file-offsets:((innamespace . 0)(inline-open . 0))
420// indent-tabs-mode: nil
421// End:
422// vim: filetype=c:expandtab:shiftwidth=4:tabstop=4:softtabstop=4
423
424
425
Note: See TracBrowser for help on using the repository browser.