Ignore:
Timestamp:
Aug 11, 2014, 9:32:24 PM (10 years ago)
Author:
alain
Message:

Introducing an improved free() in the malloc.h library.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • soft/giet_vm/giet_libs/malloc.c

    r390 r394  
    4646                                            (size <= 0x80000000) ? 31 :\
    4747                                                                   32
    48 ////////////////////////////////
    49 void 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 size of block containin alloc[] array
    81     alloc_size = heap_size / MIN_BLOCK_SIZE;
    82     if ( alloc_size < MIN_BLOCK_SIZE) alloc_size = MIN_BLOCK_SIZE;
    83 
    84     // get index for the corresponding block
    85     alloc_index = GET_SIZE_INDEX( alloc_size );
    86 
    87     // compute alloc[] array base address
    88     alloc_base = heap_base + heap_size - alloc_size;
    89 
    90     // reset the free[] array
    91     for ( index = 0 ; index < 32 ; index++ )
    92     {
    93         heap[x][y].free[index] = 0;
    94     }
    95 
    96     // split the heap into various sizes blocks,
    97     // initializes the free[] array and NEXT pointers
    98     // base is the block base address
    99     unsigned int   base = heap_base;
    100     unsigned int*  ptr;
    101     for ( index = heap_index-1 ; index >= alloc_index ; index-- )
    102     {
    103         heap[x][y].free[index] = base;
    104         ptr = (unsigned int*)base;
    105         *ptr = 0;
    106         base = base + (1<<index);
    107     }
    108 
    109     heap[x][y].init       = HEAP_INITIALIZED;
    110     heap[x][y].x          = x;
    111     heap[x][y].y          = y;
    112     heap[x][y].heap_base  = heap_base;
    113     heap[x][y].heap_size  = heap_size;
    114     heap[x][y].alloc_size = alloc_size;
    115     heap[x][y].alloc_base = alloc_base;
    116 
    117     lock_release( &heap[x][y].lock );
    118 
    119 #if GIET_DEBUG_MALLOC
    120 giet_shr_printf("\n[MALLOC DEBUG] Heap[%d][%d] initialisation\n"
    121                 " - heap_base  = %x\n"
    122                 " - heap_size  = %x\n"
    123                 " - alloc_base = %x\n"
    124                 " - alloc_size = %x\n"
    125                 " - free[0]    = %x\n"
    126                 " - free[1]    = %x\n"
    127                 " - free[2]    = %x\n"
    128                 " - free[3]    = %x\n"
    129                 " - free[4]    = %x\n"
    130                 " - free[5]    = %x\n"
    131                 " - free[6]    = %x\n"
    132                 " - free[7]    = %x\n"
    133                 " - free[8]    = %x\n"
    134                 " - free[9]    = %x\n"
    135                 " - free[10]   = %x\n"
    136                 " - free[11]   = %x\n"
    137                 " - free[12]   = %x\n"
    138                 " - free[13]   = %x\n"
    139                 " - free[14]   = %x\n"
    140                 " - free[15]   = %x\n"
    141                 " - free[16]   = %x\n"
    142                 " - free[17]   = %x\n"
    143                 " - free[18]   = %x\n"
    144                 " - free[19]   = %x\n"
    145                 " - free[20]   = %x\n"
    146                 " - free[21]   = %x\n"
    147                 " - free[22]   = %x\n"
    148                 " - free[23]   = %x\n",
     48////////////////////////////////////////
     49void display_free_array( unsigned int x,
     50                         unsigned int y )
     51{
     52    giet_shr_printf(
     53                " - coordinates = [%d][%d]\n"
     54                " - heap_base   = %x\n"
     55                " - heap_size   = %x\n"
     56                " - alloc_base  = %x\n"
     57                " - alloc_size  = %x\n"
     58                " - free[0]     = %x\n"
     59                " - free[1]     = %x\n"
     60                " - free[2]     = %x\n"
     61                " - free[3]     = %x\n"
     62                " - free[4]     = %x\n"
     63                " - free[5]     = %x\n"
     64                " - free[6]     = %x\n"
     65                " - free[7]     = %x\n"
     66                " - free[8]     = %x\n"
     67                " - free[9]     = %x\n"
     68                " - free[10]    = %x\n"
     69                " - free[11]    = %x\n"
     70                " - free[12]    = %x\n"
     71                " - free[13]    = %x\n"
     72                " - free[14]    = %x\n"
     73                " - free[15]    = %x\n"
     74                " - free[16]    = %x\n"
     75                " - free[17]    = %x\n"
     76                " - free[18]    = %x\n"
     77                " - free[19]    = %x\n"
     78                " - free[20]    = %x\n"
     79                " - free[21]    = %x\n"
     80                " - free[22]    = %x\n"
     81                " - free[23]    = %x\n",
    14982                heap[x][y].x, heap[x][y].y,
    15083                heap[x][y].heap_base, heap[x][y].heap_size,
    … …  
    16295                heap[x][y].free[20], heap[x][y].free[21],
    16396                heap[x][y].free[22], heap[x][y].free[23] );
     97}  // end display_free array()
     98
     99////////////////////////////////
     100void heap_init( unsigned int x,
     101                unsigned int y )
     102{
     103    unsigned int heap_base;        // heap segment base
     104    unsigned int heap_size;        // heap segment size
     105    unsigned int heap_index;       // size_index in free[array]
     106
     107    unsigned int alloc_base;       // alloc[] array base
     108    unsigned int alloc_size;       // alloc[] array size
     109    unsigned int alloc_index;      // size_index in free[array]
     110
     111    unsigned int index;            // iterator
     112
     113    // get heap_base, heap size, and heap index
     114    giet_heap_info( &heap_base, &heap_size, x, y );
     115    heap_index = GET_SIZE_INDEX( heap_size );
     116
     117    // checking heap segment constraints
     118    if ( heap_size == 0 )                                    // heap segment exist
     119    {
     120        giet_exit("ERROR in malloc() : heap not found \n");
     121    }
     122    if ( heap_size != (1<<heap_index) )                      // heap size power of 2
     123    {
     124        giet_exit("ERROR in malloc() : heap size must be power of 2\n");
     125    }
     126    if ( heap_base % heap_size )                             // heap segment aligned
     127    {
     128        giet_exit("ERROR in malloc() : heap segment must be aligned\n");
     129    }
     130
     131    // compute size of block containin alloc[] array
     132    alloc_size = heap_size / MIN_BLOCK_SIZE;
     133    if ( alloc_size < MIN_BLOCK_SIZE) alloc_size = MIN_BLOCK_SIZE;
     134
     135    // get index for the corresponding block
     136    alloc_index = GET_SIZE_INDEX( alloc_size );
     137
     138    // compute alloc[] array base address
     139    alloc_base = heap_base + heap_size - alloc_size;
     140
     141    // reset the free[] array
     142    for ( index = 0 ; index < 32 ; index++ )
     143    {
     144        heap[x][y].free[index] = 0;
     145    }
     146
     147    // split the heap into various sizes blocks,
     148    // initializes the free[] array and NEXT pointers
     149    // base is the block base address
     150    unsigned int   base = heap_base;
     151    unsigned int*  ptr;
     152    for ( index = heap_index-1 ; index >= alloc_index ; index-- )
     153    {
     154        heap[x][y].free[index] = base;
     155        ptr = (unsigned int*)base;
     156        *ptr = 0;
     157        base = base + (1<<index);
     158    }
     159
     160    heap[x][y].init       = HEAP_INITIALIZED;
     161    heap[x][y].x          = x;
     162    heap[x][y].y          = y;
     163    heap[x][y].heap_base  = heap_base;
     164    heap[x][y].heap_size  = heap_size;
     165    heap[x][y].alloc_size = alloc_size;
     166    heap[x][y].alloc_base = alloc_base;
     167
     168    lock_release( &heap[x][y].lock );
     169
     170#if GIET_DEBUG_MALLOC
     171giet_shr_printf("\n[MALLOC DEBUG] Completing Heap[%d][%d] initialisation\n", x, y );
     172display_free_array(x,y);
    164173#endif
    165174               
    … …  
    254263    unsigned int requested_index = GET_SIZE_INDEX( size );
    255264
    256     // take the lock protecting access to heap(x,y)
     265    // take the lock protecting access to heap[x][y]
    257266    lock_acquire( &heap[x][y].lock );
    258267
    … …  
    273282    lock_release( &heap[x][y].lock );
    274283 
     284#if GIET_DEBUG_MALLOC
     285giet_shr_printf("\n[MALLOC DEBUG] Malloc for Heap[%d][%d] / size = %x / base = %x\n",
     286                 x, y, size, base );
     287display_free_array(x,y);
     288#endif
     289
    275290    return (void*)base;
    276291
    … …  
    289304}
    290305
     306///////////////////////////////////////////
     307void update_free_array( giet_heap_t* heap,
     308                        unsigned int base,
     309                        unsigned int size_index )
     310{
     311    // This recursive function try to merge the released block
     312    // with the companion block if this companion block is free.
     313    // This companion has the same size, and almost the same address
     314    // (only one address bit is different)
     315    // - If the companion is not in free[size_index],
     316    //   the released block is pushed in free[size_index].
     317    // - If the companion is found, it is evicted from free[size_index]
     318    //   and the merged bloc is pushed in the free[size_index+1].
     319
     320
     321    // compute released block size
     322    unsigned int size = 1<<size_index;
     323
     324    // compute companion_base and merged_base
     325    unsigned int companion_base;   // companion block base address
     326    unsigned int merged_base;      // merged block base address
     327    if ( base % (size<<1) )
     328    {
     329        companion_base  = base + size;
     330        merged_base     = base;
     331    }
     332    else
     333    {
     334        companion_base  = base - size;
     335        merged_base     = base - size;
     336    }
     337
     338    // scan all blocks in free[size_index]
     339    // the iter & prev variables are actually addresses
     340    unsigned int  found = 0;
     341    unsigned int  iter  = heap->free[size_index];
     342    unsigned int  prev  = (unsigned int)&heap->free[size_index];
     343    while ( iter != 0 )
     344    {
     345        if ( iter == companion_base )
     346        {
     347            found = 1;
     348            break;
     349        }
     350        iter = *(unsigned int*)iter;
     351        prev = iter;
     352    }
     353
     354    if ( found == 0 )  // Companion not found
     355    {
     356        // push the block in free[size_index] 
     357        *(unsigned int*)base   = heap->free[size_index];
     358        heap->free[size_index] = base;
     359    }
     360    else               // Companion found : merge
     361    {
     362        // evict the searched block from free[size_index]
     363        *(unsigned int*)prev = *(unsigned int*)iter;
     364
     365        // call the update_free() function for free[size_index+1]
     366        update_free_array( heap, merged_base , size_index+1 );
     367    }
     368}
    291369
    292370//////////////////////
    293371void free( void* ptr )
    294372{
    295     unsigned int vaddr = (unsigned int)ptr;
    296 
    297     // get the cluster coordinate
     373    // get the cluster coordinate from ptr value
    298374    unsigned int x;
    299375    unsigned int y;
    300376    giet_get_xy( ptr, &x, &y );
    301377
    302     // compute index in alloc[] array
    303     unsigned index = ( (unsigned int)ptr - heap[x][y].heap_base ) / MAX_BLOCK_SIZE;
     378    // get the lock protecting heap[x][y]
     379    lock_acquire( &heap[x][y].lock );
     380
     381    // check ptr value
     382    unsigned int base = (unsigned int)ptr;
     383    if ( (base < heap[x][y].heap_base) ||
     384         (base >= (heap[x][y].heap_base + heap[x][y].heap_size)) )
     385    {
     386        giet_exit("ERROR in free() : illegal pointer for released block");
     387    }
    304388 
    305     // get the freed block size_index
    306     unsigned char* p i        = (unsigned char*)(heap[x][y].alloc_base + index);
    307     unsigned int   size_index = (unsigned int)*p;
    308 
    309     // update the free[] array and NEXT pointer
    310     *(unsigned int*)ptr         = heap[x][y].free[size_index];
    311     heap[x][y].free[size_index] = (unsigned int)ptr;
    312    
    313     // TODO try to concatenate with another free block of same size
    314     // this require probably to replace this simple push by a recursive function
    315 }
     389    // compute released block index in alloc[] array
     390    unsigned index = (base - heap[x][y].heap_base ) / MIN_BLOCK_SIZE;
     391 
     392    // get the released block size_index
     393    unsigned char* pchar      = (unsigned char*)(heap[x][y].alloc_base + index);
     394    unsigned int   size_index = (unsigned int)*pchar;
     395
     396    // check released block alignment
     397    if ( base % (1 << size_index) )
     398    {
     399        giet_exit("ERROR in free() : released block not aligned");
     400    }
     401
     402    // call the recursive function update_free_array()
     403    update_free_array( &heap[x][y], base, size_index );
     404
     405    // release the lock
     406    lock_release( &heap[x][y].lock );
     407
     408#if GIET_DEBUG_MALLOC
     409giet_shr_printf("\n[MALLOC DEBUG] Free for Heap[%d][%d] / base = %x / size = %x\n",
     410                 x, y, base, 1<<size_index );
     411display_free_array(x,y);
     412#endif
     413
     414} // end free()
    316415
    317416
Note: See TracChangeset for help on using the changeset viewer.