Changeset 382


Ignore:
Timestamp:
Aug 7, 2014, 12:23:12 PM (10 years ago)
Author:
alain
Message:

Major evolution of the malloc library, to provide two new services:

  • all allocated blocks are aligned, and the size is a power of 2.
  • the remote-malloc() function allows the application to explicitely define the cluster(x,y).

We keep only the close-fit allocation policy.
These services were required to implement the distributed SBT barrier.

Location:
soft/giet_vm/giet_libs
Files:
7 edited

Legend:

Unmodified
Added
Removed

  • soft/giet_vm/giet_libs/barrier.c

    r376 r382  
    77
    88#include "barrier.h"
    9 #include "remote_malloc.h"
     9#include "malloc.h"
    1010#include "stdio.h"
    1111#include "giet_config.h"
    … …  
    186186                     ( (l == 8) && ((x&0x0F) == 0) && ((y&0x0F) == 0) ) )
    187187                 {
    188                      barrier->node[x][y][l] = remote_malloc( SBT_NODE_SIZE, 0, x, y );
     188                     barrier->node[x][y][l] = remote_malloc( SBT_NODE_SIZE, x, y );
    189189
    190190#if GIET_DEBUG_SBT

  • soft/giet_vm/giet_libs/malloc.c

    r368 r382  
     1////////////////////////////////////////////////////////////////////////////////
     2// File     : malloc.c
     3// Date     : 05/03/2013
     4// Author   : Jean-Baptiste Bréjon / alain greiner
     5// Copyright (c) UPMC-LIP6
     6////////////////////////////////////////////////////////////////////////////////
    17
    28#include "malloc.h"
    3 #include "malloc_private.h"
    49#include "stdio.h"
    510
    6 #define NB_TASKS_MAX  14
    7 
    8 heap_ll * _heap_head[NB_TASKS_MAX];
    9 
    10 heap_ll * _remote_free_list[NB_TASKS_MAX] = { 0 };
    11 giet_lock_t lock_rf_list[NB_TASKS_MAX] = { {"toto",0} };
    12 
    13 unsigned int _heap_base[NB_TASKS_MAX] = { -1 };
    14 unsigned int _heap_length[NB_TASKS_MAX] = { -1 };
    15 
    16 int _first_malloc[NB_TASKS_MAX] = { 0 };
    17 
    18 
    19 #if MALLOC_SELECTED == 1
    20 
    21 #elif MALLOC_SELECTED == 2
    22 heap_ll * _prev_next_last_allocted[NB_TASKS_MAX] = { 0 };
    23 #else
    24 #define MAX_SIZE_POW2_TAB 28
    25 #define GET_TAB_INDEX(size)                 (size == 0x00000008) ? 0 :\
    26                                             (size <= 0x00000010) ? 1 :\
    27                                             (size <= 0x00000020) ? 2 :\
    28                                             (size <= 0x00000040) ? 3 :\
    29                                             (size <= 0x00000080) ? 4 :\
    30                                             (size <= 0x00000100) ? 5 :\
    31                                             (size <= 0x00000200) ? 6 :\
    32                                             (size <= 0x00000400) ? 7 :\
    33                                             (size <= 0x00000800) ? 8 :\
    34                                             (size <= 0x00001000) ? 9 :\
    35                                             (size <= 0x00002000) ? 10 :\
    36                                             (size <= 0x00004000) ? 11 :\
    37                                             (size <= 0x00008000) ? 12 :\
    38                                             (size <= 0x00010000) ? 13 :\
    39                                             (size <= 0x00020000) ? 14 :\
    40                                             (size <= 0x00040000) ? 15 :\
    41                                             (size <= 0x00080000) ? 16 :\
    42                                             (size <= 0x00100000) ? 17 :\
    43                                             (size <= 0x00200000) ? 18 :\
    44                                             (size <= 0x00400000) ? 19 :\
    45                                             (size <= 0x00800000) ? 20 :\
    46                                             (size <= 0x01000000) ? 21 :\
    47                                             (size <= 0x02000000) ? 22 :\
    48                                             (size <= 0x04000000) ? 23 :\
    49                                             (size <= 0x08000000) ? 24 :\
    50                                             (size <= 0x10000000) ? 25 :\
    51                                             (size <= 0x20000000) ? 26 :\
    52                                                                    27
    53 
    54 heap_ll * _pow2tab[NB_TASKS_MAX][MAX_SIZE_POW2_TAB] = {{ 0 }};
     11// Global variables defining the heap descriptors array (one heap per cluster)
     12giet_heap_t heap[X_SIZE][Y_SIZE];
     13
     14// Macro returning the smallest power of 2 larger or equal to size value
     15#define GET_SIZE_INDEX(size)                (size <= 0x00000001) ? 0  :\
     16                                            (size <= 0x00000002) ? 1  :\
     17                                            (size <= 0x00000004) ? 2  :\
     18                                            (size <= 0x00000008) ? 3  :\
     19                                            (size <= 0x00000010) ? 4  :\
     20                                            (size <= 0x00000020) ? 5  :\
     21                                            (size <= 0x00000040) ? 6  :\
     22                                            (size <= 0x00000080) ? 7  :\
     23                                            (size <= 0x00000100) ? 8  :\
     24                                            (size <= 0x00000200) ? 9  :\
     25                                            (size <= 0x00000400) ? 10 :\
     26                                            (size <= 0x00000800) ? 11 :\
     27                                            (size <= 0x00001000) ? 12 :\
     28                                            (size <= 0x00002000) ? 13 :\
     29                                            (size <= 0x00004000) ? 14 :\
     30                                            (size <= 0x00008000) ? 15 :\
     31                                            (size <= 0x00010000) ? 16 :\
     32                                            (size <= 0x00020000) ? 17 :\
     33                                            (size <= 0x00040000) ? 18 :\
     34                                            (size <= 0x00080000) ? 19 :\
     35                                            (size <= 0x00100000) ? 20 :\
     36                                            (size <= 0x00200000) ? 21 :\
     37                                            (size <= 0x00400000) ? 22 :\
     38                                            (size <= 0x00800000) ? 23 :\
     39                                            (size <= 0x01000000) ? 24 :\
     40                                            (size <= 0x02000000) ? 25 :\
     41                                            (size <= 0x04000000) ? 26 :\
     42                                            (size <= 0x08000000) ? 27 :\
     43                                            (size <= 0x10000000) ? 28 :\
     44                                            (size <= 0x20000000) ? 29 :\
     45                                            (size <= 0x40000000) ? 30 :\
     46                                            (size <= 0x80000000) ? 31 :\
     47                                                                   32
     48////////////////////////////////
     49void heap_init( unsigned int x,
     50                unsigned int y )
     51{
     52    unsigned int heap_base;        // heap segment base
     53    unsigned int heap_size;        // heap segment size
     54    unsigned int heap_index;       // size_index in free[array]
     55
     56    unsigned int alloc_base;       // alloc[] array base
     57    unsigned int alloc_size;       // alloc[] array size
     58    unsigned int alloc_index;      // size_index in free[array]
     59
     60    unsigned int index;            // iterator
     61
     62    // get heap_base, heap size, and heap index
     63    giet_heap_info( &heap_base, &heap_size, x, y );
     64    heap_index = GET_SIZE_INDEX( heap_size );
     65
     66    // checking heap segment constraints
     67    if ( heap_size == 0 )                                    // heap segment exist
     68    {
     69        giet_exit("ERROR in malloc() : heap not found \n");
     70    }
     71    if ( heap_size != (1<<heap_index) )                      // heap size power of 2
     72    {
     73        giet_exit("ERROR in malloc() : heap size must be power of 2\n");
     74    }
     75    if ( heap_base % heap_size )                             // heap segment aligned
     76    {
     77        giet_exit("ERROR in malloc() : heap segment must be aligned\n");
     78    }
     79
     80    // compute alloc[] minimal array size
     81    alloc_size = heap_size / MIN_BLOCK_SIZE;
     82
     83    // get index for the corresponding block
     84    alloc_index = GET_SIZE_INDEX( alloc_size );
     85
     86    // compute alloc[] array base address
     87    alloc_base = heap_base + heap_size - alloc_size;
     88
     89    // reset the free[] array
     90    for ( index = 0 ; index < 32 ; index++ )
     91    {
     92        heap[x][y].free[index] = 0;
     93    }
     94
     95    // split the heap into various sizes blocks,
     96    // initializes the free[] array and NEXT pointers
     97    // base is the block base address
     98    unsigned int   base = heap_base;
     99    unsigned int*  ptr;
     100    for ( index = heap_index-1 ; index > alloc_index ; index-- )
     101    {
     102        heap[x][y].free[index] = base;
     103        ptr = (unsigned int*)base;
     104        *ptr = 0;
     105        base = base + (1<<index);
     106    }
     107
     108    heap[x][y].init       = HEAP_INITIALIZED;
     109    heap[x][y].x          = x;
     110    heap[x][y].y          = y;
     111    heap[x][y].heap_base  = heap_base;
     112    heap[x][y].heap_size  = heap_size;
     113    heap[x][y].alloc_size = alloc_size;
     114    heap[x][y].alloc_base = alloc_base;
     115
     116    lock_release( &heap[x][y].lock );
     117
     118#if GIET_DEBUG_MALLOC
     119giet_shr_printf("\n[MALLOC DEBUG] Heap[%d][%d] initialisation\n"
     120                " - heap_base  = %x\n"
     121                " - heap_size  = %x\n"
     122                " - alloc_base = %x\n"
     123                " - alloc_size = %x\n"
     124                " - free[0]    = %x\n"
     125                " - free[1]    = %x\n"
     126                " - free[2]    = %x\n"
     127                " - free[3]    = %x\n"
     128                " - free[4]    = %x\n"
     129                " - free[5]    = %x\n"
     130                " - free[6]    = %x\n"
     131                " - free[7]    = %x\n"
     132                " - free[8]    = %x\n"
     133                " - free[9]    = %x\n"
     134                " - free[10]   = %x\n"
     135                " - free[11]   = %x\n"
     136                " - free[12]   = %x\n"
     137                " - free[13]   = %x\n"
     138                " - free[14]   = %x\n"
     139                " - free[15]   = %x\n"
     140                " - free[16]   = %x\n"
     141                " - free[17]   = %x\n"
     142                " - free[18]   = %x\n"
     143                " - free[19]   = %x\n"
     144                " - free[20]   = %x\n"
     145                " - free[21]   = %x\n"
     146                " - free[22]   = %x\n"
     147                " - free[23]   = %x\n",
     148                heap[x][y].x, heap[x][y].y,
     149                heap[x][y].heap_base, heap[x][y].heap_size,
     150                heap[x][y].alloc_base, heap[x][y].alloc_size,
     151                heap[x][y].free[0], heap[x][y].free[1],
     152                heap[x][y].free[2], heap[x][y].free[3],
     153                heap[x][y].free[4], heap[x][y].free[5],
     154                heap[x][y].free[6], heap[x][y].free[7],
     155                heap[x][y].free[8], heap[x][y].free[9],
     156                heap[x][y].free[10], heap[x][y].free[11],
     157                heap[x][y].free[12], heap[x][y].free[13],
     158                heap[x][y].free[14], heap[x][y].free[15],
     159                heap[x][y].free[16], heap[x][y].free[17],
     160                heap[x][y].free[18], heap[x][y].free[19],
     161                heap[x][y].free[20], heap[x][y].free[21],
     162                heap[x][y].free[22], heap[x][y].free[23] );
    55163#endif
    56 
    57 
    58 #if DEBUG_MALLOC == 1             
    59 #define giet_printf(...)                \
    60     ({                                      \
    61      giet_tty_printf(__VA_ARGS__);       \
    62      })                                 
    63 #else
    64 #define giet_printf(...) ({   })
    65 #endif
    66 
    67 
    68 
    69 #if MALLOC_SELECTED == 1
    70 /*########################################################################*/
    71 /**************************************************************************/
    72 /**********                     WORST-FIT                       ***********/
    73 /**************************************************************************/
    74 /*########################################################################*/
    75 heap_ll *get_prev_fit_chunk(unsigned int size) {
    76     int task_id = giet_global_task_id();
    77     int check_remote_free_list = 0;
    78 after_remote_list_check :
    79     if (_heap_head[task_id] == 0x0) {
    80         if(check_remote_free_list == 0)
     164               
     165}  // end heap_init()
     166
     167////////////////////////////////////////////
     168unsigned int split_block( giet_heap_t* heap,
     169                          unsigned int vaddr,
     170                          unsigned int searched_index,
     171                          unsigned int requested_index )
     172{
     173    // push the upper half block into free[searched_index-1]
     174    unsigned int* new            = (unsigned int*)(vaddr + (1<<(searched_index-1)));
     175    *new                         = heap->free[searched_index-1];
     176    heap->free[searched_index-1] = (unsigned int)new;
     177       
     178    if ( searched_index == requested_index + 1 )  // terminal case: return lower half block
     179    {
     180        return vaddr;
     181    }
     182    else            // non terminal case : lower half block must be split again
     183    {                               
     184        return split_block( heap, vaddr, searched_index-1, requested_index );
     185    }
     186} // end split_block()
     187
     188//////////////////////////////////////////
     189unsigned int get_block( giet_heap_t* heap,
     190                        unsigned int searched_index,
     191                        unsigned int requested_index )
     192{
     193    // test terminal case
     194    if ( (1<<searched_index) > heap->heap_size )  // failure : return a NULL value
     195    {
     196        return 0;
     197    }
     198    else                            // search a block in free[searched_index]
     199    {
     200        unsigned int vaddr = heap->free[searched_index];
     201        if ( vaddr == 0 )     // block not found : search in free[searched_index+1]
    81202        {
    82             heap_ll * poped_block;
    83             heap_ll * head_of_rf;
    84             check_remote_free_list = 1;
    85 
    86             head_of_rf = pop_ptr();
    87 
    88             while((poped_block = pop_remote_free_list(&head_of_rf)) != 0x0)
     203            return get_block( heap, searched_index+1, requested_index );
     204        }
     205        else                // block found : pop it from free[searched_index]
     206        {
     207            // pop the block from free[searched_index]
     208            unsigned int next = *((unsigned int*)vaddr);
     209            heap->free[searched_index] = next;
     210           
     211            // test if the block must be split
     212            if ( searched_index == requested_index )  // no split required
    89213            {
    90                 update_chunk_list((unsigned int)poped_block, poped_block->chunk_length);
     214                return vaddr;
    91215            }
    92             goto after_remote_list_check;
    93         }
    94         return ((heap_ll *) 0x01);
    95     }
    96     int found = 0;
    97     heap_ll * ptr_to_chunk_list = _heap_head[task_id];
    98     heap_ll * tmp = 0x0;
    99     heap_ll * prev = 0x0;
    100     heap_ll * prev_tmp = 0x0;
    101     while (ptr_to_chunk_list != 0x0) {
    102         if (size <= ptr_to_chunk_list->chunk_length) {
    103             if (tmp == 0x0 || ptr_to_chunk_list->chunk_length > tmp->chunk_length) {
    104                 prev_tmp = prev;
    105                 tmp = ptr_to_chunk_list;
    106                 found = 1;
     216            else                                      // split is required
     217            {
     218                return split_block( heap, vaddr, searched_index, requested_index );
    107219            }
    108         }
    109         prev = ptr_to_chunk_list;
    110         ptr_to_chunk_list = ptr_to_chunk_list->next;
    111     }
    112     if (found == 1)
    113     {
    114         return prev_tmp; // case when prev_tmp == 0x0 is handled in the calling function
    115     }
    116     else
    117     {
    118         if(check_remote_free_list == 0)
    119         {
    120             heap_ll * poped_block;
    121             heap_ll * head_of_rf;
    122             check_remote_free_list = 1;
    123 
    124             head_of_rf = pop_ptr();
    125 
    126             while((poped_block = pop_remote_free_list(&head_of_rf)) != 0x0)
    127             {
    128                 update_chunk_list((unsigned int)poped_block, poped_block->chunk_length);
    129             }
    130             goto after_remote_list_check;
    131         }
    132         return (heap_ll *) 0x1;
    133     }
     220        }
     221    }
     222} // end get_block()
     223
     224////////////////////////////////////////
     225void * remote_malloc( unsigned int size,
     226                      unsigned int x,
     227                      unsigned int y )
     228{
     229    // checking arguments
     230    if (size == 0)
     231    {
     232        giet_exit("ERROR in malloc() : requested size = 0 \n");
     233    }
     234    if ( x >= X_SIZE )
     235    {
     236        giet_exit("ERROR in malloc() : x coordinate too large\n");
     237    }
     238    if ( y >= Y_SIZE )
     239    {
     240        giet_exit("ERROR in malloc() : y coordinate too large\n");
     241    }
     242
     243    // initializes the heap if first access
     244    if ( heap[x][y].init != HEAP_INITIALIZED )
     245    {
     246        heap_init( x, y );
     247    }
     248
     249    // compute requested_index for the free[] array
     250    unsigned int requested_index = GET_SIZE_INDEX( size );
     251
     252    // take the lock protecting access to heap(x,y)
     253    lock_acquire( &heap[x][y].lock );
     254
     255    // call the recursive function get_block
     256    unsigned int base = get_block( &heap[x][y],
     257                                   requested_index,
     258                                   requested_index );
     259
     260    // update the alloc[] array
     261    unsigned offset = (base - heap[x][y].heap_base) / MIN_BLOCK_SIZE;
     262    unsigned char* ptr = (unsigned char*)(heap[x][y].alloc_base + offset);
     263    *ptr = requested_index;
     264
     265    // release the lock
     266    lock_release( &heap[x][y].lock );
     267 
     268    return (void*)base;
     269
     270} // end remote_malloc()
     271
     272
     273//////////////////////////////////
     274void * malloc( unsigned int size )
     275{
     276    unsigned int proc_id    = giet_procid();
     277    unsigned int cluster_xy = proc_id / NB_PROCS_MAX;
     278    unsigned int x          = cluster_xy >> Y_WIDTH;
     279    unsigned int y          = cluster_xy & ((1<<Y_WIDTH)-1);
     280
     281    return remote_malloc( size, x, y );
     282}
     283
     284
     285//////////////////////
     286void free( void* ptr )
     287{
     288    // To be done
     289    // - first : to compute the cluster coordinate
     290    // - second : retrieve the block length from the
     291    // - third : try to concatenate with another free block of same size
     292    // - fourth : update the free[] array
    134293}
    135 
    136 
    137 
    138 void * malloc(unsigned int size) {
    139     int task_id = giet_global_task_id();
    140 
    141     giet_printf("############ MALLOC ############\n\n");
    142     if (size == 0) {
    143 
    144         giet_printf(" SIZE = 0 \n");
    145         return 0x0;
    146     }
    147 
    148     /****** First call to malloc ******/
    149     if (_first_malloc[task_id] == 0) {
    150         giet_heap_info(&_heap_base[task_id], &_heap_length[task_id]);
    151 
    152         if (_heap_length[task_id] == 0) {
    153             giet_printf("*** Error: Malloc called in task %d and no heap was defined.\n", task_id);
    154             return 0x0;
    155         }
    156         _heap_head[task_id] = (heap_ll *) _heap_base[task_id];
    157         _heap_head[task_id]->chunk_length = _heap_length[task_id];
    158         _heap_head[task_id]->next = 0x0;
    159 
    160 
    161         _first_malloc[task_id] = 1;
    162     }
    163 
    164     /****** Size align ******/
    165     int size_align = size;
    166     if (size % 4 != 0) {
    167         size_align = ((size / 4) + 1) * 4;
    168     }
    169 
    170 
    171 
    172     giet_printf("Looking for size : %d\n", size_align + 4);
    173     /****** Get prev victim from the chunks list ******/
    174     heap_ll *victim;
    175     heap_ll *prev_victim;
    176     //// WORST
    177 
    178     if ((prev_victim = get_prev_fit_chunk(size_align + 4)) == (heap_ll *) 0x1) {
    179         return 0x0;             // no chunk of this size avaiable, 0x1 : no suitable chunk found
    180     }
    181     else {
    182         if (prev_victim != 0x0) {
    183             // victim != HEAD
    184             victim = prev_victim->next;
    185         }
    186         else {
    187             victim = _heap_head[task_id];
    188         }
    189     }
    190     /****** Get Victim Base ******/
    191     unsigned int victim_vbase = (unsigned int) victim;  // overhead
    192 
    193     /****** update the chunks list ******/
    194     if (victim->chunk_length == size_align + 4) {
    195         // if it is an exact match
    196         if (prev_victim == 0x0) {
    197             // if victim == head
    198             _heap_head[task_id] = victim->next;
    199         }
    200         else {
    201             prev_victim->next = victim->next;
    202         }
    203     }
    204     else {
    205         // if its not an exact match then update chunk base and length
    206         heap_ll * tmp_chunk = victim;
    207         victim = (heap_ll *) (((unsigned int) victim) + (size_align + 4));
    208 
    209         giet_printf("NEXT CHUNK is at @ : 0x%x + 0x%x = 0x%x\n",
    210                 (unsigned int) tmp_chunk,
    211                 (unsigned int) ((size_align + 4) / 4),
    212                 (unsigned int) victim);
    213 
    214         victim->chunk_length = tmp_chunk->chunk_length - (size_align + 4);
    215         victim->next = tmp_chunk->next;
    216         if (prev_victim == 0x0) {
    217             _heap_head[task_id] = victim;
    218         }
    219         else {
    220             prev_victim->next = victim;
    221         }
    222     }
    223 
    224     /****** Write Overhead ******/
    225     *((unsigned int *) victim_vbase) = size_align;      // writing overhead on the first word
    226 
    227     giet_printf("BLOCK SUCCESSFULLY ALLOCATED at @ 0x%x user will write at @ 0x%x\n\n"\
    228             ,(unsigned int)(victim_vbase),(unsigned int) (victim_vbase + 4));
    229     return (unsigned int *) (victim_vbase + 4);
    230 }
    231 
    232 
    233 
    234 /* this function tries to merge the block to free with chunks in the list if
    235  * they are contiguous
    236  * the block can be merged two times.
    237  */
    238 void update_chunk_list(unsigned int block_base, unsigned int block_length) {
    239     /* entire heap is allocated : create a new block of size block_length and give it to the head  */
    240     int task_id = giet_global_task_id();
    241     if (_heap_head[task_id] == 0x0) {
    242         ((heap_ll *) block_base)->chunk_length = block_length;
    243         ((heap_ll *) block_base)->next = 0x0;
    244         _heap_head[task_id] = ((heap_ll *) block_base);
    245 
    246         giet_printf("****** NEW BLOCK ******\n"
    247                 "@ : %x\n"
    248                 "Length : %d o\n"
    249                 "***********************\n",
    250                 block_base,
    251                 (unsigned int) (((heap_ll *) block_base)->chunk_length));
    252         return;
    253     }
    254 
    255 
    256     /* Test for each Chunk in my list if the block can be merged with */
    257     heap_ll *ptr_to_chunk_list = _heap_head[task_id]; // move through the list
    258     heap_ll *prev = 0x0; // pointer on the previous visited chunk in the list
    259     heap_ll *prev_block_base = 0x0; // pointer on the previous chunk of the chunk that contains the merged block in the list
    260     unsigned int chunk_length;
    261     int block_merged = 0; // =1 when the block has already been merged with a chunk in the list
    262     while (ptr_to_chunk_list != 0x0) {
    263         chunk_length = ptr_to_chunk_list->chunk_length;
    264         /*  [.....|ptr|block|.....] */
    265         if ((unsigned int) (ptr_to_chunk_list) + chunk_length == block_base) {
    266 
    267             giet_printf("****** BLOCK MERGED ******\n"
    268                     "CHUNK : %x of size %d o\n"
    269                     "merged with \n"
    270                     "BLOCK : %x of size %d o\n"
    271                     "***********************\n",
    272                     (unsigned int) ptr_to_chunk_list,
    273                     ptr_to_chunk_list->chunk_length, block_base,
    274                     block_length);
    275 
    276             /* update the size */
    277             ptr_to_chunk_list->chunk_length = chunk_length + block_length;
    278 
    279             /* [.....|ptr|[block|old_ptr]|.....]
    280              *  remove ptr from the list
    281              *  update next pointer
    282              *  update the previous chunk of block base to point to ptr
    283              */
    284             if (block_merged == 1) {
    285                 prev->next = ptr_to_chunk_list->next;
    286                 ptr_to_chunk_list->next = ((heap_ll *) block_base)->next;
    287                 if (prev_block_base != 0x0) {
    288                     prev_block_base->next = ptr_to_chunk_list;
    289                 }
    290                 else {
    291                     _heap_head[task_id] = ptr_to_chunk_list;
    292                 }
    293             }
    294             /****** for next turn ******/
    295             block_base = (unsigned int) ptr_to_chunk_list;
    296             block_length = ptr_to_chunk_list->chunk_length;
    297 
    298             giet_printf("****** NEW BLOCK ******\n"
    299                     "@ : %x\n"
    300                     "Length : %d o\n"
    301                     "***********************\n",
    302                     (unsigned int) ptr_to_chunk_list,
    303                     (unsigned int) (ptr_to_chunk_list->chunk_length));
    304             prev_block_base = prev;
    305             prev = ptr_to_chunk_list;
    306             ptr_to_chunk_list = ptr_to_chunk_list->next;
    307             block_merged = 1;
    308             continue;
    309 
    310         } // end [.....|ptr|block|.....]
    311         /*  [......|block|ptr|.....] */
    312         if (block_base + block_length == (unsigned int) ptr_to_chunk_list) {
    313 
    314             giet_printf("****** BLOCK MERGED ******\n"
    315                     "BLOCK : %x of size %d o\n"
    316                     "merged with \n"
    317                     "CHUNK : %x of size %d o\n"
    318                     "***********************\n",
    319                     block_base, block_length,
    320                     (unsigned int) ptr_to_chunk_list,
    321                     ptr_to_chunk_list->chunk_length);
    322 
    323             /* update the size */
    324             ((heap_ll *) block_base)->chunk_length = block_length + chunk_length;
    325 
    326             /* [.....|block|ptr|......] */
    327             if (block_merged == 0) {
    328                 /* update next pointer
    329                  *  update the previous chunk of ptr to point to block_base
    330                  */
    331                 ((heap_ll *) block_base)->next = ptr_to_chunk_list->next;
    332                 if (prev == 0x0) {
    333                     _heap_head[task_id] = ((heap_ll *) block_base);
    334                 }
    335                 else {
    336                     prev->next = ((heap_ll *) block_base);
    337                 }
    338             }
    339             /* [.....[old_ptr|block]|ptr|......] */
    340             else {
    341                 /* remove ptr from the list */
    342                 prev->next = ptr_to_chunk_list->next;
    343             }
    344 
    345             ptr_to_chunk_list = ((heap_ll *) block_base);
    346             block_length = ptr_to_chunk_list->chunk_length;
    347 
    348             giet_printf("****** NEW BLOCK ******\n"
    349                     "@ : %x\n"
    350                     "Length : %d o\n"
    351                     "***********************\n",
    352                     (unsigned int) ptr_to_chunk_list,
    353                     (unsigned int) (ptr_to_chunk_list->chunk_length));
    354             prev_block_base = prev;
    355             block_merged = 1;
    356         } // end [......|block|ptr|.....]
    357         prev = ptr_to_chunk_list;
    358         ptr_to_chunk_list = ptr_to_chunk_list->next;
    359     } // end while
    360     if (block_merged == 1) {
    361         return;
    362     }
    363     /* if the block cant be merge
    364      *  create new block and add it to the end of the list
    365      */
    366     ((heap_ll *) block_base)->chunk_length = block_length;
    367     ((heap_ll *) block_base)->next = 0x0;
    368     prev->next = ((heap_ll *) block_base);
    369 
    370     giet_printf("****** NEW BLOCK ******\n"
    371             "@ : %x\n"
    372             "Length : %d o\n"
    373             "***********************\n",
    374             block_base,
    375             (unsigned int) (((heap_ll *) block_base)->chunk_length));
    376     return;
    377 
    378 }
    379 
    380 
    381 
    382 /*########################################################################*/
    383 /**************************************************************************/
    384 /**********                 END WORST-FIT                       ***********/
    385 /**************************************************************************/
    386 /*########################################################################*/
    387 #elif MALLOC_SELECTED == 2 // Next Fit
    388 /*########################################################################*/
    389 /**************************************************************************/
    390 /**********                   NEXT-FIT                          ***********/
    391 /**************************************************************************/
    392 /*########################################################################*/
    393 
    394 heap_ll * get_prev_fit_chunk(unsigned int size) {
    395     int task_id = giet_global_task_id();
    396     int check_remote_free_list = 0;
    397 after_remote_list_check_n : //n for next_fit
    398     if (_heap_head[task_id] == 0x0) {
    399         if(check_remote_free_list == 0)
    400         {
    401             heap_ll * poped_block;
    402             heap_ll * head_of_rf;
    403             check_remote_free_list = 1;
    404 
    405             head_of_rf = pop_ptr();
    406 
    407             while((poped_block = pop_remote_free_list(&head_of_rf)) != 0x0)
    408             {
    409                 update_chunk_list((unsigned int)poped_block, poped_block->chunk_length);
    410             }
    411             goto after_remote_list_check_n;
    412         }
    413         return ((heap_ll *) 0x1);
    414     }
    415 
    416     heap_ll * ptr_to_chunk_list;
    417     heap_ll * prev = 0x0;
    418     heap_ll * tmp_turn = 0x0;
    419 
    420     if (_prev_next_last_allocted[task_id] == 0x0 || _prev_next_last_allocted[task_id]->next == 0x0) {
    421         ptr_to_chunk_list = _heap_head[task_id];
    422     }
    423     else
    424     {
    425         ptr_to_chunk_list = _prev_next_last_allocted[task_id]->next;
    426     }
    427 
    428     tmp_turn = (ptr_to_chunk_list == 0x0)?_heap_head[task_id]:ptr_to_chunk_list;
    429     do {
    430         if (ptr_to_chunk_list == 0x0) {
    431             // simulate circular list
    432             ptr_to_chunk_list = _heap_head[task_id];
    433             if (ptr_to_chunk_list == tmp_turn) break;
    434         }
    435 
    436         if (size <= ptr_to_chunk_list->chunk_length) {
    437             return prev;
    438         }
    439         prev = ptr_to_chunk_list;
    440         ptr_to_chunk_list = ptr_to_chunk_list->next;
    441     } while (ptr_to_chunk_list != tmp_turn);
    442     if(check_remote_free_list == 0)
    443     {
    444         heap_ll * poped_block;
    445         heap_ll * head_of_rf;
    446         check_remote_free_list = 1;
    447 
    448         head_of_rf = pop_ptr();
    449 
    450         while((poped_block = pop_remote_free_list(&head_of_rf)) != 0x0)
    451         {
    452             update_chunk_list((unsigned int)poped_block, poped_block->chunk_length);
    453         }
    454         goto after_remote_list_check_n;
    455     }
    456 
    457     return (heap_ll *) 0x1;
    458 }
    459 
    460 
    461 void * malloc(unsigned int size) {
    462 
    463     int task_id = giet_global_task_id();
    464 
    465     giet_printf("############ MALLOC ############\n\n");
    466     if (size == 0) {
    467 
    468         giet_printf(" SIZE = 0 \n");
    469         return 0x0;
    470     }
    471 
    472     /****** First call to malloc ******/
    473     if (_first_malloc[task_id] == 0) {
    474         giet_heap_info(&_heap_base[task_id], &_heap_length[task_id]);
    475 
    476         if (_heap_length[task_id] == 0) {
    477             giet_printf("*** Error: Malloc called in task %d while no heap was defined.\n", task_id);
    478             return 0x0;
    479         }
    480 
    481         _heap_head[task_id] = (heap_ll *) _heap_base[task_id];
    482         _heap_head[task_id]->chunk_length = _heap_length[task_id];
    483         _heap_head[task_id]->next = 0x0;
    484 
    485         _prev_next_last_allocted[task_id] = 0x0;
    486 
    487         _first_malloc[task_id] = 1;
    488     }
    489 
    490     /****** Size align ******/
    491     int size_align = size;
    492     if (size % 4 != 0) {
    493         size_align = ((size / 4) + 1) * 4;
    494     }
    495 
    496 
    497 
    498     giet_printf("Looking for size : %d\n", size_align + 4);
    499     /****** Get prev victim from the chunks list ******/
    500     heap_ll *victim;
    501     heap_ll *prev_victim;
    502 
    503     if ((prev_victim = get_prev_fit_chunk(size_align + 4)) == (heap_ll *) 0x1) {
    504         return 0x0;             // no chunk of this size avaiable, 0x1 : no suitable chunk found
    505     }
    506     else {
    507         if (prev_victim != 0x0) {
    508             // victim != _next_last_allocted
    509             if (prev_victim->next == 0x0) {
    510                 // victim == HEAD
    511                 victim = _heap_head[task_id];
    512             }
    513             else {
    514                 victim = prev_victim->next;
    515             }
    516         }
    517         else
    518         {
    519             if (_prev_next_last_allocted[task_id] == 0x0 || _prev_next_last_allocted[task_id]->next == 0x0) {
    520                 victim =_heap_head[task_id];
    521             }
    522             else {
    523                 victim = _prev_next_last_allocted[task_id]->next;
    524             }
    525         }
    526     }
    527 
    528     /****** Get Victim Base ******/
    529     unsigned int victim_vbase = (unsigned int) victim; // overhead
    530 
    531     /****** update the chunks list ******/
    532     if (victim->chunk_length - (size_align + 4) < 8) {
    533         // if it is an exact match
    534         size_align = size_align + (victim->chunk_length - (size_align + 4));
    535 
    536         if (prev_victim == 0x0) {
    537             // if victim == head
    538             if (_prev_next_last_allocted[task_id] == 0x0 || _prev_next_last_allocted[task_id]->next == 0x0) {
    539                 _heap_head[task_id] = victim->next;
    540             }
    541             else {
    542                 _prev_next_last_allocted[task_id]->next = victim->next;
    543             }
    544             _prev_next_last_allocted[task_id] = victim->next;
    545         }
    546         else {
    547             if (prev_victim->next == 0x0) {
    548                 _heap_head[task_id] = victim->next;
    549             }
    550             else {
    551                 prev_victim->next = victim->next;
    552             }
    553             _prev_next_last_allocted[task_id] = prev_victim;
    554         }
    555     }
    556     else {
    557         // if its not an exact match then update chunk base and length
    558         heap_ll * tmp_chunk = victim;
    559         victim = (heap_ll *) (((unsigned int) victim) + (size_align + 4));
    560 
    561         giet_printf("NEXT CHUNK is at @ : 0x%x + 0x%x = 0x%x\n",
    562                 (unsigned int) tmp_chunk,
    563                 (unsigned int) ((size_align + 4) / 4),
    564                 (unsigned int) victim);
    565 
    566         victim->chunk_length = tmp_chunk->chunk_length - (size_align + 4);
    567         victim->next = tmp_chunk->next;
    568         if (prev_victim == 0x0) {
    569             if (_prev_next_last_allocted[task_id] == 0x0 || _prev_next_last_allocted[task_id]->next == 0x0) {
    570                 _heap_head[task_id] = victim;
    571             }
    572             else {
    573                 _prev_next_last_allocted[task_id]->next = victim;
    574             }
    575             _prev_next_last_allocted[task_id] = victim->next;
    576         }
    577         else {
    578             if (prev_victim->next == 0x0) {
    579                 _heap_head[task_id] = victim;
    580             }
    581             else {
    582                 prev_victim->next = victim;
    583             }
    584             _prev_next_last_allocted[task_id] = prev_victim;
    585         }
    586     }
    587 
    588     /****** Write Overhead ******/
    589     *((unsigned int *) victim_vbase) = size_align;      // writing overhead on the first word
    590 
    591     giet_printf("BLOCK SUCCESSFULLY ALLOCATED at @ 0x%x user will write at @ 0x%x\n\n"\
    592             ,(unsigned int)(victim_vbase),(unsigned int )(victim_vbase + 4));
    593     return (unsigned int *) (victim_vbase + 4);
    594 }
    595 
    596 
    597 
    598 /* this function tries to merge the block to free with chunks in the list if they are contiguous
    599  * the block can be merged two times.
    600  */
    601 
    602 void update_chunk_list(unsigned int block_base, unsigned int block_length) {
    603     int task_id = giet_global_task_id();
    604     /* entire heap is allocated : create a new block of size block_length and give it to the head  */
    605     if (_heap_head[task_id] == 0x0) {
    606         ((heap_ll *) block_base)->chunk_length = block_length;
    607         ((heap_ll *) block_base)->next = 0x0;
    608         _heap_head[task_id] = ((heap_ll *) block_base);
    609 
    610         giet_printf("****** NEW BLOCK ******\n"
    611                 "@ : %x\n"
    612                 "Length : %d o\n"
    613                 "***********************\n",
    614                 block_base,
    615                 (unsigned int) (((heap_ll *) block_base)->chunk_length));
    616         return;
    617     }
    618 
    619     /* Test for each Chunk in my list if the block can be merged with */
    620     heap_ll * ptr_to_chunk_list = _heap_head[task_id]; // move through the list
    621     heap_ll * prev = 0x0; // pointer on the previous visited chunk in the list
    622     heap_ll * prev_block_base = 0x0; // pointer on the previous chunk of the chunk that contains the merged block in the list
    623     unsigned int chunk_length;
    624     int block_merged = 0; // =1 when the block has already been merged with a chunk in the list
    625     while (ptr_to_chunk_list != 0x0) {
    626         chunk_length = ptr_to_chunk_list->chunk_length;
    627         /*  [.....|ptr|block|.....] */
    628         if ((unsigned int) (ptr_to_chunk_list) + chunk_length == block_base) {
    629 
    630             giet_printf("****** BLOCK MERGED ******\n"
    631                     "CHUNK : %x of size %d o\n"
    632                     "merged with \n"
    633                     "BLOCK : %x of size %d o\n"
    634                     "***********************\n",
    635                     (unsigned int) ptr_to_chunk_list,
    636                     ptr_to_chunk_list->chunk_length, block_base,
    637                     block_length);
    638             if (_prev_next_last_allocted[task_id] == ptr_to_chunk_list) {
    639                 _prev_next_last_allocted[task_id] = ptr_to_chunk_list->next;
    640             }
    641 
    642             /* update the size */
    643             ptr_to_chunk_list->chunk_length = chunk_length + block_length;
    644 
    645             /* [.....|ptr|[block|old_ptr]|.....]
    646              *  remove ptr from the list
    647              *  update next pointer
    648              *  update the previous chunk of block base to point to ptr
    649              */
    650             if (block_merged == 1) {
    651                 prev->next = ptr_to_chunk_list->next;
    652                 ptr_to_chunk_list->next = ((heap_ll *) block_base)->next;
    653 
    654                 if (prev_block_base != 0x0) {
    655                     prev_block_base->next = ptr_to_chunk_list;
    656                 }
    657                 else {
    658                     _heap_head[task_id] = ptr_to_chunk_list;
    659                 }
    660             }
    661             /****** for next turn ******/
    662             block_base = (unsigned int) ptr_to_chunk_list;
    663             block_length = ptr_to_chunk_list->chunk_length;
    664 
    665             giet_printf("****** NEW BLOCK ******\n"
    666                     "@ : %x\n"
    667                     "Length : %d o\n"
    668                     "***********************\n",
    669                     (unsigned int) ptr_to_chunk_list,
    670                     (unsigned int) (ptr_to_chunk_list->chunk_length));
    671             prev_block_base = prev;
    672             prev = ptr_to_chunk_list;
    673             ptr_to_chunk_list = ptr_to_chunk_list->next;
    674             block_merged = 1;
    675             continue;
    676 
    677         } // end [.....|ptr|block|.....]
    678         /*  [......|block|ptr|.....] */
    679         if (block_base + block_length == (unsigned int) ptr_to_chunk_list) {
    680 
    681             giet_printf("****** BLOCK MERGED ******\n"
    682                     "BLOCK : %x of size %d o\n"
    683                     "merged with \n"
    684                     "CHUNK : %x of size %d o\n"
    685                     "***********************\n",
    686                     block_base, block_length,
    687                     (unsigned int) ptr_to_chunk_list,
    688                     ptr_to_chunk_list->chunk_length);
    689 
    690             if (_prev_next_last_allocted[task_id] == ptr_to_chunk_list) {
    691                 _prev_next_last_allocted[task_id] = ptr_to_chunk_list->next;
    692             }
    693 
    694             /* update the size */
    695             ((heap_ll *) block_base)->chunk_length = block_length + chunk_length;
    696 
    697             /* [.....|block|ptr|......] */
    698             if (block_merged == 0) {
    699                 /* update next pointer
    700                  *  update the previous chunk of ptr to point to block_base
    701                  */
    702                 ((heap_ll *) block_base)->next = ptr_to_chunk_list->next;
    703                 if (prev == 0x0) {
    704                     _heap_head[task_id] = ((heap_ll *) block_base);
    705                 }
    706                 else {
    707                     prev->next = ((heap_ll *) block_base);
    708                 }
    709             }
    710             /* [.....[old_ptr|block]|ptr|......] */
    711             else {
    712                 /* remove ptr from the list */
    713                 prev->next = ptr_to_chunk_list->next;
    714                 if (prev_block_base != 0x0) {
    715                     prev_block_base->next = ((heap_ll *)block_base);
    716                 }
    717                 else {
    718                     _heap_head[task_id] = ((heap_ll *)block_base);
    719                 }
    720             }
    721 
    722             ptr_to_chunk_list = ((heap_ll *) block_base);
    723             block_length = ptr_to_chunk_list->chunk_length;
    724 
    725             giet_printf("****** NEW BLOCK ******\n"
    726                     "@ : %x\n"
    727                     "Length : %d o\n"
    728                     "***********************\n",
    729                     (unsigned int) ptr_to_chunk_list,
    730                     (unsigned int) (ptr_to_chunk_list->chunk_length));
    731             prev_block_base = prev;
    732             block_merged = 1;
    733         } // end [......|block|ptr|.....]
    734 
    735         prev = ptr_to_chunk_list;
    736         ptr_to_chunk_list = ptr_to_chunk_list->next;
    737     } // end while
    738 
    739     if (block_merged == 1) {
    740         return;
    741     }
    742 
    743     /* if the block cant be merge
    744      *  create new block and add it to the end of the list
    745      */
    746     ((heap_ll *) block_base)->chunk_length = block_length;
    747     ((heap_ll *) block_base)->next = 0x0;
    748     prev->next = ((heap_ll *) block_base);
    749 
    750 
    751     giet_printf("****** NEW BLOCK ******\n"
    752             "@ : %x\n"
    753             "Length : %d o\n"
    754             "***********************\n",
    755             block_base,
    756             (unsigned int) (((heap_ll *) block_base)->chunk_length));
    757     return;
    758 }
    759 
    760 
    761 
    762 /*########################################################################*/
    763 /**************************************************************************/
    764 /**********                 END NEXT-FIT                        ***********/
    765 /**************************************************************************/
    766 /*########################################################################*/
    767 
    768 #else // Default case : New Fit
    769 
    770 /*########################################################################*/
    771 /**************************************************************************/
    772 /**********                    CLOSE-FIT                        ***********/
    773 /**************************************************************************/
    774 /*########################################################################*/
    775 
    776 
    777 int get_prev_fit_chunk(unsigned int size) {
    778     int task_id = giet_global_task_id();
    779     int check_remote_free_list = 0;
    780     int index;
    781 after_remote_list_check_c : //c for close fit
    782     index = GET_TAB_INDEX(size);
    783     while (index != MAX_SIZE_POW2_TAB) {
    784         if (_pow2tab[task_id][index] != 0x0) {
    785             return index;
    786         }
    787         index++;
    788     }
    789 
    790     if(check_remote_free_list == 0)
    791     {
    792         heap_ll * poped_block;
    793         heap_ll * head_of_rf;
    794         check_remote_free_list = 1;
    795 
    796         head_of_rf = pop_ptr();
    797 
    798         while((poped_block = pop_remote_free_list(&head_of_rf)) != 0x0)
    799         {
    800             update_chunk_list((unsigned int)poped_block, poped_block->chunk_length);
    801         }
    802         goto after_remote_list_check_c;
    803     }
    804 
    805     return -1;
    806 }
    807 
    808 
    809 
    810 void * malloc(unsigned int size) {
    811     int task_id = giet_global_task_id();
    812 
    813     giet_printf("############ MALLOC ############\n\n");
    814     if(size == 0) {
    815 
    816         giet_printf(" SIZE = 0 \n");
    817         return 0x0;
    818     }
    819     if (size > 0x20000000) {
    820 
    821         giet_printf("ERROR max size = %d\n",0x20000000);
    822         return 0x0;
    823     }
    824     if (size < 8) {
    825         size = 8;
    826     }
    827 
    828     /****** First call to malloc ******/
    829     if (_first_malloc[task_id] == 0) {
    830         giet_heap_info( &_heap_base[task_id],
    831                         &_heap_length[task_id],
    832                         0xFFFFFFFF,
    833                         0xFFFFFFFF );
    834 
    835         if (_heap_length[task_id] == 0) {
    836             giet_printf("*** Error: Malloc called in task %d while no heap was defined.\n", task_id);
    837             return 0x0;
    838         }
    839 
    840         int index = GET_TAB_INDEX(_heap_length[task_id]);
    841 
    842         _pow2tab[task_id][index] = (heap_ll *) _heap_base[task_id];
    843         _pow2tab[task_id][index]->chunk_length = _heap_length[task_id];
    844         _pow2tab[task_id][index]->next = 0x0;
    845 
    846         *((unsigned int *) ((_heap_base[task_id] +_heap_length[task_id]) - 4))     = _heap_length[task_id];
    847 
    848         _first_malloc[task_id] = 1;
    849     }
    850 
    851     /****** Size align ******/
    852     int size_align = size;
    853     if (size % 4 != 0) {
    854         size_align = ((size / 4) + 1) * 4;
    855     }
    856 
    857 
    858     giet_printf("Looking for size : %d %d = %d\n", size_align, 4,size_align+4);
    859 
    860 
    861     /****** Get tab index of the victim from the chunks list ******/
    862     heap_ll * victim;
    863     int index;
    864     if ((index = get_prev_fit_chunk(size_align + 4)) == -1) {
    865         return 0x0;
    866     }
    867     victim = _pow2tab[task_id][index];
    868 
    869     /****** Get Victim Base ******/
    870     unsigned int victim_vbase = (unsigned int) victim;  // overhead
    871 
    872 
    873     /****** update the chunks list ******/
    874     _pow2tab[task_id][index] = _pow2tab[task_id][index]->next;
    875 
    876     if ((victim->chunk_length - (size_align + 4)) < 12) {
    877         size_align = size_align + (victim->chunk_length - (size_align + 4));
    878     }
    879     else {
    880         // if its not an exact match then update chunk base and length
    881         unsigned int new_size = victim->chunk_length - (size_align + 4); // get the new size;
    882         unsigned int new_index = GET_TAB_INDEX(new_size);                 // get the new index;
    883         heap_ll * new_chunk = (heap_ll *) (((unsigned int) victim) + (size_align + 4)); //update new_chunk @
    884         new_chunk->chunk_length = new_size;                                // write new size
    885         *((unsigned int *) ((unsigned int) new_chunk + new_size - 4)) = new_size;                                // on both side of the block
    886         new_chunk->next = _pow2tab[task_id][new_index];                     // insert new_chunk @ the new index
    887         _pow2tab[task_id][new_index] = new_chunk;
    888 
    889 
    890         giet_printf("NEXT CHUNK is at @ : 0x%x + 0x%x = 0x%x : @ of size over the block : %x\n",
    891                 (unsigned int) victim,
    892                 (unsigned int) ((size_align + 4) / 4),
    893                 (unsigned int) new_chunk,
    894                 ((unsigned int) new_chunk + new_chunk->chunk_length) - 4);
    895     }
    896 
    897     /****** Write Overhead ******/
    898     *((unsigned int *) victim_vbase) = size_align;      // writing overhead on the first word
    899 
    900     giet_printf("BLOCK SUCCESSFULLY ALLOCATED at @ 0x%x user will write at @ 0x%x\n\n",\
    901             (unsigned int)(victim_vbase), (unsigned int ) (victim_vbase + 4));
    902 
    903     return (unsigned int *) (victim_vbase + 4);
    904 }
    905 
    906 
    907 
    908 /* this function tries to merge the block to free with chunks in the list if they are contiguous
    909  * the block can be merged two times.
    910  */
    911 void update_chunk_list(unsigned int block_base, unsigned int block_length) {
    912     int task_id = giet_global_task_id();
    913 
    914     int left_merging               = 0;
    915     unsigned int left_block_size   = 0;
    916     unsigned int left_block_index  = 0;
    917     heap_ll * left_block_addr      = 0x0;
    918 
    919     int right_merging              = 0;
    920     unsigned int right_block_size  = 0;
    921     unsigned int right_block_index = 0;
    922     heap_ll * right_block_addr     = 0x0;
    923 
    924     if (block_base - 4 >= _heap_base[task_id]) {
    925 
    926 
    927         giet_printf("############# LEFT MERGE #############\n\n");
    928         left_block_size = *((unsigned int *) (block_base - 4));
    929         left_block_index = GET_TAB_INDEX(left_block_size);
    930         left_block_addr = (heap_ll *)(block_base - left_block_size);
    931         left_merging = 1;
    932     }
    933 
    934     if ((block_base + block_length) <= (_heap_base[task_id] + _heap_length[task_id]) - 8) {
    935 
    936         giet_printf("############# RIGHT MERGE #############\n\n");
    937         right_block_size = ((heap_ll *)(block_base + block_length))->chunk_length;
    938         right_block_index = GET_TAB_INDEX(right_block_size);
    939         right_block_addr = (heap_ll *) (block_base + block_length);
    940         right_merging = 1;
    941     }
    942 
    943 
    944     giet_printf("############# END PREP MERGE #############\n\n");
    945 
    946     heap_ll * ptr_to_chunk = 0x0;
    947     heap_ll * prev_ptr_to_chunk = 0x0;
    948 
    949     heap_ll * ptr_to_chunk_right = 0x0;
    950     heap_ll * prev_ptr_to_chunk_right = 0x0;
    951 
    952     unsigned int new_size = block_length;
    953     unsigned int new_index = 0;
    954     int merged_left = 0;
    955     heap_ll * new_addr = 0x0;
    956 
    957 
    958 
    959     /* try to merge with left block */
    960     if (left_merging == 1 &&
    961             (unsigned int) left_block_addr >= _heap_base[task_id] &&
    962             (unsigned int) left_block_addr <= block_base - 12) {
    963         ptr_to_chunk = _pow2tab[task_id][left_block_index];
    964         while (ptr_to_chunk != 0x0) {
    965             if (ptr_to_chunk == left_block_addr && ptr_to_chunk->chunk_length == left_block_size) {
    966                 new_size = new_size + left_block_size;
    967                 if (prev_ptr_to_chunk == 0x0) {
    968                     _pow2tab[task_id][left_block_index] = ptr_to_chunk->next;
    969                 }
    970                 else {
    971                     prev_ptr_to_chunk->next = ptr_to_chunk->next;
    972                 }
    973                 merged_left = 1;
    974                 break;
    975             }
    976             else if (ptr_to_chunk == right_block_addr && ptr_to_chunk->chunk_length == right_block_size) {
    977                 ptr_to_chunk_right = ptr_to_chunk;
    978                 prev_ptr_to_chunk_right = prev_ptr_to_chunk;
    979             }
    980             prev_ptr_to_chunk = ptr_to_chunk;
    981             ptr_to_chunk = ptr_to_chunk->next;
    982         }
    983     }
    984 
    985     if (right_block_index != left_block_index) {
    986         prev_ptr_to_chunk = 0x0;
    987         ptr_to_chunk = _pow2tab[task_id][right_block_index];
    988     }
    989     else {
    990         ptr_to_chunk = ptr_to_chunk_right;
    991         prev_ptr_to_chunk = prev_ptr_to_chunk_right;
    992     }
    993 
    994     /* try to merge with right block */
    995     if (right_merging == 1 &&
    996             (unsigned int) right_block_addr >= block_base + block_length &&
    997             (unsigned int) right_block_addr <= (_heap_base[task_id] + _heap_length[task_id]) - 12) {
    998         while (ptr_to_chunk != 0x0) {
    999             if (ptr_to_chunk == right_block_addr && ptr_to_chunk->chunk_length == right_block_size) {
    1000                 new_size = new_size + right_block_size;
    1001                 if (prev_ptr_to_chunk == 0x0) {
    1002                     _pow2tab[task_id][right_block_index] = ptr_to_chunk->next;
    1003                 }
    1004                 else {
    1005                     prev_ptr_to_chunk->next = ptr_to_chunk->next;
    1006                 }
    1007                 break;
    1008             }
    1009             prev_ptr_to_chunk = ptr_to_chunk;
    1010             ptr_to_chunk = ptr_to_chunk->next;
    1011         }
    1012     }
    1013     new_index = GET_TAB_INDEX(new_size);
    1014     if (merged_left == 1) {
    1015         new_addr = (heap_ll *) (block_base - left_block_size);
    1016     }
    1017     else {
    1018         new_addr = (heap_ll *) block_base;
    1019     }
    1020     new_addr->chunk_length = new_size;
    1021     *((unsigned int *) ((unsigned int) new_addr + (new_addr->chunk_length - 4))) = new_size;
    1022     new_addr->next = _pow2tab[task_id][new_index];
    1023     _pow2tab[task_id][new_index] = new_addr;
    1024 
    1025     giet_printf("########################  UPDT SUCCESS ######################\n");
    1026 
    1027     return;
    1028 }
    1029 
    1030 
    1031 
    1032 
    1033 /*########################################################################*/
    1034 /**************************************************************************/
    1035 /**********                 END CLOSE-FIT                       ***********/
    1036 /**************************************************************************/
    1037 /*########################################################################*/
    1038 
    1039 #endif // New Fit
    1040 
    1041 heap_ll * pop_remote_free_list(heap_ll ** head)
    1042 {
    1043 
    1044     heap_ll * poped_block;
    1045 
    1046     if (*head == 0x0)
    1047     {
    1048         giet_printf(" no block to pop\n");
    1049         return 0x0;
    1050     }
    1051     else
    1052     {
    1053         poped_block = *head;
    1054         *head = (*head)->next;
    1055 
    1056         giet_printf(" : @%x, size : %x\n", poped_block, poped_block->chunk_length);
    1057     }
    1058 
    1059     return poped_block;
    1060 }
    1061 
    1062 heap_ll * pop_ptr(void)
    1063 {
    1064     int task_id = giet_global_task_id();
    1065     heap_ll * head_of_rf_list;
    1066     giet_printf(" -- POP lock acquire -- for %d : @ : %x\n", task_id, &lock_rf_list[task_id]);
    1067     lock_acquire(&lock_rf_list[task_id]);
    1068     giet_printf(" -- POP lock acquired --\n");
    1069 
    1070     head_of_rf_list = _remote_free_list[task_id];
    1071     _remote_free_list[task_id] = 0x0;
    1072 
    1073     lock_release(&lock_rf_list[task_id]);
    1074     return head_of_rf_list;
    1075 
    1076 }
    1077 
    1078 void insert_in_remote_free_list(unsigned int remote_owner_id, unsigned int block_base, unsigned int block_length)
    1079 {
    1080 
    1081     giet_printf("############### INSERT \n");
    1082     ((heap_ll *)block_base)->chunk_length = block_length;
    1083 
    1084     giet_printf(" -- INSERT lock acquire -- for %d : @ : %x\n", remote_owner_id, &lock_rf_list[remote_owner_id]);
    1085     lock_acquire(&lock_rf_list[remote_owner_id]);
    1086 
    1087     giet_printf(" -- INSERT lock acquired -- \n");
    1088 
    1089     // insertion en début de liste
    1090     giet_printf("  in remote_owner %d ...\n", remote_owner_id);
    1091     if (_remote_free_list[remote_owner_id] == 0x0)
    1092     {
    1093         ((heap_ll *)block_base)->next = 0x0;
    1094     }
    1095     else
    1096     {
    1097         ((heap_ll *)block_base)->next = _remote_free_list[remote_owner_id];
    1098     }
    1099     _remote_free_list[remote_owner_id] = ((heap_ll *)block_base);
    1100 
    1101     giet_printf("  : OK\n\n");
    1102     giet_printf(" new head : %x : of size : %x, with next : %x\n", _remote_free_list[remote_owner_id], _remote_free_list[remote_owner_id]->chunk_length, _remote_free_list[remote_owner_id]->next);
    1103 
    1104     lock_release(&lock_rf_list[remote_owner_id]);
    1105 
    1106     return;
    1107 }
    1108 
    1109 void free(void * ptr) {
    1110     int i = 0;
    1111     while (i != NB_TASKS_MAX)
    1112     {
    1113         if( _heap_base[i] == -1)
    1114         {
    1115             continue;
    1116         }
    1117         if ((unsigned int)ptr > _heap_base[i] && (unsigned int)ptr < _heap_base[i] + _heap_length[i])
    1118         {
    1119             break;
    1120         }
    1121         i++;
    1122     }
    1123 
    1124     int task_id = giet_global_task_id();
    1125     unsigned int * to_free = ptr;
    1126     unsigned int heapB;
    1127     unsigned int heapL;
    1128     unsigned int overhead;
    1129     unsigned int block_base;
    1130     unsigned int block_length;
    1131     unsigned int remote_free_needed;
    1132     unsigned int remote_owner_id;
    1133     if (i == task_id)
    1134     {
    1135 
    1136         giet_printf("############# FREE  #############\n\n");
    1137         remote_free_needed = 0;
    1138         remote_owner_id = -1;
    1139         heapB = _heap_base[task_id];
    1140         heapL = _heap_length[task_id];
    1141     }
    1142     else
    1143     {
    1144 
    1145         giet_printf("############# REMOTE FREE  #############\n\n");
    1146         remote_free_needed = 1;
    1147         remote_owner_id = i;
    1148         heapB = _heap_base[remote_owner_id];
    1149         heapL = _heap_length[remote_owner_id];
    1150     }
    1151 
    1152 
    1153     /****** CHECK PTR ******/
    1154     if (to_free == 0x0) {
    1155 
    1156         giet_printf("free == 0x0\n");
    1157         return;
    1158     }
    1159     // check alignement of ptr
    1160     if (((unsigned int) to_free) % 4 != 0) {
    1161 
    1162         giet_printf("allignement of ptr  %x = %d\n", (unsigned int) to_free, (unsigned int) to_free % 4);
    1163         return;
    1164     }
    1165     // check if the @ of ptr matches the range of the heap
    1166     if (!((unsigned int) to_free >= heapB && (unsigned int) to_free < heapB + heapL)) {
    1167 
    1168         giet_printf("check if it matches the range of the heap\n");
    1169         return;
    1170     }
    1171 
    1172     // get the 4 bytes before the ptr that contains the size of the block
    1173     overhead = *(to_free - 1);
    1174     // check alignement of overhead
    1175     if (overhead % 4 != 0) {
    1176 
    1177         giet_printf("check alignement of overhead\n");
    1178         return;
    1179     }
    1180     // check if (overhead + to_free) matches the range of the heap
    1181     if ((((unsigned int) (to_free) + overhead) - 4) > heapB + heapL) {
    1182 
    1183         giet_printf ("check if (overhead + to_free) matches the range of the heap\n");
    1184         return;
    1185     }
    1186 
    1187     block_base = (unsigned int) (to_free - 1);
    1188     block_length = overhead + 4;
    1189 
    1190     if (remote_free_needed == 0)
    1191     {
    1192 
    1193         giet_printf("############# UPDATE CL :  FREE %x of size %d #############\n\n",block_base, block_length);
    1194         update_chunk_list(block_base, block_length);
    1195     }
    1196     else
    1197     {
    1198 
    1199         giet_printf("############# INSERT IN RF %d :  FREE %x of size %d #############\n\n", remote_owner_id, block_base, block_length);
    1200         insert_in_remote_free_list(remote_owner_id, block_base, block_length);
    1201     }
    1202 
    1203 
    1204     giet_printf("BLOCK SUCCESSFULLY FREED\n\n");
    1205 
    1206     return;
    1207 }
    1208 
    1209 
    1210294
    1211295

  • soft/giet_vm/giet_libs/malloc.h

    r295 r382  
    1 ////////////////////////////////////////////////////////////////////////////
     1////////////////////////////////////////////////////////////////////////////////
    22// File     : malloc.h
    33// Date     : 05/03/2013
    4 // Author   : Jean-Baptiste Bréjon
     4// Author   : Jean-Baptiste Bréjon / alain greiner
    55// Copyright (c) UPMC-LIP6
    6 ////////////////////////////////////////////////////////////////////////////
     6////////////////////////////////////////////////////////////////////////////////
     7// Initialisation policy:
     8//   Each heap(x,y) structure is initialized by the malloc() or remote_malloc()
     9//   function, when this function is called the first time.
     10//   The function hep_init() initialise the free blocks linked lists as
     11//   explained below.
     12////////////////////////////////////////////////////////////////////////////////
     13// Free blocks organisation:
     14// - All free blocks have a size that is a power of 2, larger or equal
     15//   to MIN_BLOCK_SIZE (typically 128 bytes).
     16// - All free blocks are aligned.
     17// - They are pre-classed in NB_SIZES linked lists, where all blocks in the
     18//   same list have the same size.
     19// - The NEXT pointer implementing those linked lists is written
     20//   in the 4 first bytes of the block itself, using the unsigned int type.
     21// - The pointers on the first free block for each size are stored in an
     22//   array of pointers free[32] in the heap(x,y) descriptor.
     23////////////////////////////////////////////////////////////////////////////////
     24// Allocation policy:
     25// - The block size required by the user can be any value, but the allocated
     26//   block size can be larger than the requested size:
     27// - The allocator computes actual_size, that is the smallest power of 2
     28//   value larger or equal to the requested size AND larger or equal to
     29//   MIN_BLOCK_SIZE.
     30// - It pop the linked list of free blocks corresponding to actual_size,
     31//   and returns the block B if the list[actual_size] is not empty.
     32// - If the list[actual_size] is empty, it pop the list[actual_size * 2].
     33//   If a block B' is found, it break this block in 2 B/2 blocks, returns
     34//   the first B/2 block and push the other B/2 block into list[actual_size].
     35// - If the list[actual_size * 2] is empty, it pop the list[actual_size * 4].
     36//   If a block B is found, it break this block in 3 blocks B/4, B/4 and B/2,
     37//   returns the first B/4 block, push the other blocks B/4 and B/2 into
     38//   the proper lists. etc...
     39// - If no block satisfying the request is available it returns a failure
     40//   (NULL pointer).
     41// - This allocation policy has the nice following property:
     42//   If the heap segment is aligned (the heap_base is a multiple of the
     43//   heap_base), all allocated blocks are aligned on the actual_size.
     44////////////////////////////////////////////////////////////////////////////////
     45// Free policy:
     46// - Each allocated block is registered in an alloc[] array of unsigned char.
     47// - This registration is required by the free() operation, because the size
     48//   of the allocated block must obtained from the base address of the block. 
     49// - The number of entries in this array is equal to the max number
     50//   of allocated block is : heap_size / 128.
     51// - For each allocated block, the value registered in the alloc[] array
     52//   is log2( size_of_allocated_block ).
     53// - The index in this array is computed from the allocated block base address:
     54//      index = (block_base - heap_base) / MIN_BLOCK_SIZE
     55// - The allocated[] array is stored at the end of heap segment. This consume
     56//   (1 / MIN_BLOCK_SIZE) of the total heap storage capacity.
     57////////////////////////////////////////////////////////////////////////////////
    758
    859#ifndef _MALLOC_H_
    960#define _MALLOC_H_
    1061
    11 //#define DEBUG_MALLOC 1
    12 
    1362#include "giet_config.h"
    1463#include "spin_lock.h"
    1564
    16 //#define MALLOC_SELECTED 2
     65// There is the magic number indicating that heap(x,y) has been initialized.
    1766
    18 void * malloc(unsigned int size);
    19 void free(void * ptr);
     67#define HEAP_INITIALIZED    0xDEADBEEF
     68
     69#define MIN_BLOCK_SIZE      0x80
     70
     71////////////////////////////////////////////////////////////////////////////////
     72// heap(x,y) descriptor (one per cluster)
     73////////////////////////////////////////////////////////////////////////////////
     74typedef struct giet_heap_s
     75{
     76    unsigned int   init;            // initialised <=> value == HEAP_INITIALIZED
     77    unsigned int   x;               // cluster X coordinate
     78    unsigned int   y;               // cluster Y coordinate
     79    unsigned int   heap_base;       // heap base address
     80    unsigned int   heap_size;       // heap size (bytes)
     81    unsigned int   alloc_base;      // alloc[] array base address
     82    unsigned int   alloc_size;      // alloc[] array size (bytes)
     83    giet_lock_t    lock;            // lock protecting exclusive access
     84    unsigned int   free[32];        // array of base addresses of free blocks
     85                                    // (address of first block of a given size)
     86} giet_heap_t;
     87
     88///////// user functions /////////////////
     89
     90extern void* malloc( unsigned int size );
     91
     92extern void* remote_malloc( unsigned int size,
     93                            unsigned int x,
     94                            unsigned int y );
     95
     96extern void free(void * ptr);
    2097
    2198

  • soft/giet_vm/giet_libs/stdio.c

    r368 r382  
    179179    if (ret)
    180180    {
    181         giet_exit("error in giet_tty_printf()");
     181        giet_exit("ERROR in giet_tty_printf()");
    182182    }
    183183} // end giet_tty_printf()

  • soft/giet_vm/giet_libs/stdio.h

    r368 r382  
    112112
    113113//////////////////////////////////////////////////////////////////////////
     114// This function returns the processor identifier.
     115//////////////////////////////////////////////////////////////////////////
     116extern int giet_procid();
     117
     118//////////////////////////////////////////////////////////////////////////
     119// This function returns the local processor time.
     120//////////////////////////////////////////////////////////////////////////
     121extern int giet_proctime();
     122
     123//////////////////////////////////////////////////////////////////////////
     124// This function returns a pseudo-random value derived from the processor
     125// cycle count. This value is comprised between 0 & 65535.
     126/////////////////////////////////////////////////////////////////////////
     127extern int giet_rand();
     128
     129//////////////////////////////////////////////////////////////////////////
    114130//////////////////////////////////////////////////////////////////////////
    115131//             TTY device related system calls
    … …  
    352368//////////////////////////////////////////////////////////////////////////
    353369//////////////////////////////////////////////////////////////////////////
    354 //                    Miscelaneous system calls
    355 //////////////////////////////////////////////////////////////////////////
    356 //////////////////////////////////////////////////////////////////////////
    357 
    358 //////////////////////////////////////////////////////////////////////////
    359 // This function returns the processor identifier.
    360 //////////////////////////////////////////////////////////////////////////
    361 extern int giet_procid();
    362 
    363 //////////////////////////////////////////////////////////////////////////
    364 // This function returns the local processor time.
    365 //////////////////////////////////////////////////////////////////////////
    366 extern int giet_proctime();
     370//                    Task context system calls
     371//////////////////////////////////////////////////////////////////////////
     372//////////////////////////////////////////////////////////////////////////
    367373
    368374//////////////////////////////////////////////////////////////////////////
    … …  
    383389
    384390//////////////////////////////////////////////////////////////////////////
    385 // This function returns a pseudo-random value derived from the processor
    386 // cycle count. This value is comprised between 0 & 65535.
    387 /////////////////////////////////////////////////////////////////////////
    388 extern int giet_rand();
     391//////////////////////////////////////////////////////////////////////////
     392//                    Miscelaneous system calls
     393//////////////////////////////////////////////////////////////////////////
     394//////////////////////////////////////////////////////////////////////////
    389395
    390396//////////////////////////////////////////////////////////////////////////
    … …  
    393399// It does not consume processor cycles anymore.
    394400//////////////////////////////////////////////////////////////////////////
    395 extern void giet_exit();
     401extern void giet_exit( char* string );
    396402
    397403//////////////////////////////////////////////////////////////////////////

  • soft/giet_vm/giet_libs/stdlib.c

    r352 r382  
    99
    1010///////////////////////////////////////////////////////////////////////////////////
    11 // int atoi ( char * str )
     11int atoi(char *str)
    1212///////////////////////////////////////////////////////////////////////////////////
    13        
    14 int atoi(char *str)
    1513{
    1614    int res  = 0; // Initialize result
    … …  
    3432       
    3533////////////////////////////////////////////////////////////////////////////////////////
    36 //  mempcy()
    37 // GCC requires this function. Taken from MutekH.
     34void * memcpy(void *_dst, const void * _src, unsigned int size)
    3835////////////////////////////////////////////////////////////////////////////////////////
    39 void * memcpy(void *_dst, const void * _src, unsigned int size)
    4036{
    4137    unsigned int * dst = _dst;
    … …  
    6056}
    6157
    62 
    6358////////////////////////////////////////////////////////////////////////////////////////
    64 //  memset()
    65 // GCC requires this function. Taken from MutekH.
     59inline void * memset(void * dst, int s, unsigned int size)
    6660////////////////////////////////////////////////////////////////////////////////////////
    67 inline void * memset(void * dst, int s, unsigned int count)
    6861{
    6962    char * a = (char *) dst;
    70     while (count--)
     63    while (size--)
    7164    {
    7265        *a++ = (char)s;

  • soft/giet_vm/giet_libs/stdlib.h

    r356 r382  
    99#define _STDLIB_H
    1010
    11 int atoi (char * str);
     11////////////////////////////////////////////////////////////////////////////////////////
     12// This function translate a character string to a signed integer. 
     13// For a negative value, the first character must be a '-' (minus) character.
     14////////////////////////////////////////////////////////////////////////////////////////
     15int atoi ( char * str );
    1216
    1317////////////////////////////////////////////////////////////////////////////////////////
    14 //  mempcy()
     18// This function copies size bytes from the src source buffer
     19// to the dst destination buffer.
    1520// GCC requires this function. Taken from MutekH.
    1621////////////////////////////////////////////////////////////////////////////////////////
    17 void * memcpy(void *_dst, const void * _src, unsigned int size);
     22void* memcpy( void*         dst,
     23              const void*   src,
     24              unsigned int  size );
    1825
    1926////////////////////////////////////////////////////////////////////////////////////////
    20 //  memset()
     27// This function initializes size bytes in the dst destination buffer,
     28// with the value defined by (char)s.
    2129// GCC requires this function. Taken from MutekH.
    2230////////////////////////////////////////////////////////////////////////////////////////
    23 inline void * memset(void * dst, int s, unsigned int count);
     31inline void* memset( void*        dst,
     32                     int          s,
     33                     unsigned int size );
    2434
    2535#endif
Note: See TracChangeset for help on using the changeset viewer.