Ignore:
Timestamp:
Jul 8, 2015, 4:13:47 PM (9 years ago)
Author:
alain
Message:

1) Fix a bug in the _free() function in kernel_malloc.c
2) Introduce a strlen() function in utils.c

Location:
soft/giet_vm/giet_common
Files:
5 edited

Legend:

Unmodified
Added
Removed

  • soft/giet_vm/giet_common/kernel_malloc.c

    r514 r594  
    55// Copyright (c) UPMC-LIP6
    66////////////////////////////////////////////////////////////////////////////////
    7 //   Implementation note:
     7// Implementation note:
    88// - As this code is used to implement the SQT lock ptotecting TTY0,
    99//   all functions here use the kernel _nolock_printf() function.
    1010// - It must exist one vseg with the HEAP type in each cluster. The length
    1111//   must be a power of 2, and the base address must be aligned.
     12// - An array kernel_heap[x][y] containing the heap descriptors is
     13//   stored in cluster[0][0].
     14// - Each kernel_heap[x][y] structure contains a specific queuing spin-lock.
     15////////////////////////////////////////////////////////////////////////////////
     16// Allocation policy:
    1217// - All allocated blocks have a size that is a power of 2, larger or equal
    1318//   to MIN_BLOCK_SIZE (typically 64 bytes), and are aligned.
    1419// - All free blocks are pre-classed in 32 linked lists of free blocks, where
    15 //   all blocks in the same list have the same size.
     20//   all blocks in a given list have the same size.
    1621// - The NEXT pointer implementing those linked lists is written
    1722//   in the 4 first bytes of the block itself, using the unsigned int type.
    1823// - The pointers on the first free block for each size are stored in an
    1924//   array of pointers free[32] in the heap[x][y) structure itself.
    20 // - Each kernel_heap[x][y] structure is protected by a specific
    21 //   queuing spin-lock.
    2225// - The block size required can be any value, but the allocated block size
    2326//   is the smallest power of 2 value larger or equal to the requested size.
    … …  
    3235//   the proper lists. etc...
    3336////////////////////////////////////////////////////////////////////////////////
     37// Free policy:
     38// - Each allocated block is registered in an alloc[] array of unsigned char.
     39// - This registration is required by the free() operation, because the size
     40//   of the allocated block must be obtained from the base address of the block. 
     41// - The number of entries in this array is equal to the max number
     42//   of allocated block is : heap_size / MIN_BLOCK_SIZE
     43// - For each allocated block, the value registered in the alloc[] array
     44//   is log2( size_of_allocated_block ).
     45// - The index in this array is computed from the allocated block base address:
     46//      index = (block_base - heap_base) / MIN_BLOCK_SIZE
     47// - The alloc[] array is stored at the end of heap segment. This consume
     48//   (1 / MIN_BLOCK_SIZE) of the total heap storage capacity.
     49////////////////////////////////////////////////////////////////////////////////
    3450
    3551#include "giet_config.h"
    … …  
    3854#include "kernel_malloc.h"
    3955#include "kernel_locks.h"
     56#include "sys_handler.h"
    4057#include "tty0.h"
    4158#include "utils.h"
    … …  
    4663
    4764__attribute__((section(".kdata")))
    48 kernel_heap_t kernel_heap[X_SIZE][Y_SIZE];
     65kernel_heap_t     kernel_heap[X_SIZE][Y_SIZE];
    4966
    5067///////////////////////////////////////////////////////////////////////////////
    … …  
    86103
    87104#if GIET_DEBUG_SYS_MALLOC
     105
    88106////////////////////////////////////////////////
    89107static void _display_free_array( unsigned int x,
    90108                                 unsigned int y )
    91109{
    92     _nolock_printf(" Kernel Heap[%d][%d]\n"
    93                    " - heap_base   = %x\n"
    94                    " - heap_size   = %x\n"
    95                    " - free[0]     = %x\n"
    96                    " - free[1]     = %x\n"
    97                    " - free[2]     = %x\n"
    98                    " - free[3]     = %x\n"
    99                    " - free[4]     = %x\n"
    100                    " - free[5]     = %x\n"
    101                    " - free[6]     = %x\n"
    102                    " - free[7]     = %x\n"
    103                    " - free[8]     = %x\n"
    104                    " - free[9]     = %x\n"
    105                    " - free[10]    = %x\n"
    106                    " - free[11]    = %x\n"
    107                    " - free[12]    = %x\n"
    108                    " - free[13]    = %x\n"
    109                    " - free[14]    = %x\n"
    110                    " - free[15]    = %x\n"
    111                    " - free[16]    = %x\n"
    112                    " - free[17]    = %x\n"
    113                    " - free[18]    = %x\n"
    114                    " - free[19]    = %x\n"
    115                    " - free[20]    = %x\n"
    116                    " - free[21]    = %x\n"
    117                    " - free[22]    = %x\n"
    118                    " - free[23]    = %x\n",
    119                    x, y,
    120                    kernel_heap[x][y].heap_base, kernel_heap[x][y].heap_size,
    121                    kernel_heap[x][y].free[0] , kernel_heap[x][y].free[1],
    122                    kernel_heap[x][y].free[2] , kernel_heap[x][y].free[3],
    123                    kernel_heap[x][y].free[4] , kernel_heap[x][y].free[5],
    124                    kernel_heap[x][y].free[6] , kernel_heap[x][y].free[7],
    125                    kernel_heap[x][y].free[8] , kernel_heap[x][y].free[9],
    126                    kernel_heap[x][y].free[10], kernel_heap[x][y].free[11],
    127                    kernel_heap[x][y].free[12], kernel_heap[x][y].free[13],
    128                    kernel_heap[x][y].free[14], kernel_heap[x][y].free[15],
    129                    kernel_heap[x][y].free[16], kernel_heap[x][y].free[17],
    130                    kernel_heap[x][y].free[18], kernel_heap[x][y].free[19],
    131                    kernel_heap[x][y].free[20], kernel_heap[x][y].free[21],
    132                    kernel_heap[x][y].free[22], kernel_heap[x][y].free[23]);
    133 }  // end display_free array()
     110    unsigned int next;
     111    unsigned int id;
     112    unsigned int iter;
     113
     114    _nolock_printf("\nKernel Heap[%d][%d] base = %x / size = %x\n", x , y ,
     115                   kernel_heap[x][y].heap_base, kernel_heap[x][y].heap_size );
     116    for ( id = 6 ; id < 24 ; id++ )
     117    {
     118        next = kernel_heap[x][y].free[id];
     119        _nolock_printf(" - free[%d] = " , id );
     120        iter = 0;
     121        while ( next != 0 )
     122        {
     123            _nolock_printf("%x | ", next );
     124            next = (*(unsigned int*)next);
     125            iter++;
     126        }
     127        _nolock_printf("0\n");
     128    }
     129}  // end _display_free_array()
     130
    134131#endif
    135132
    … …  
    137134
    138135
    139 /////////////////////////////////////////////////////
     136////////////////////////////////////////////////////////////////////////////////
     137// This function returns the heap_base and heap_size values for cluster[x][y],
     138// from information defined in the mapping.
     139////////////////////////////////////////////////////////////////////////////////
    140140unsigned int _get_heap_info( unsigned int* heap_base,
    141141                             unsigned int* heap_size,
    … …  
    186186    unsigned int heap_size;
    187187    unsigned int heap_index;
     188
     189    unsigned int alloc_base;
     190    unsigned int alloc_size;
     191    unsigned int alloc_index;
     192
    188193    unsigned int index;
    189194    unsigned int x;
    … …  
    195200        for ( y = 0 ; y < Y_SIZE ; y++ )
    196201        {
    197             // get heap_base, heap size, and heap index
     202            // get heap_base & heap size
    198203            ko = _get_heap_info( &heap_base, &heap_size, x, y );
    199204       
    200205            if ( ko )  // no kernel heap found in cluster[x][y]
    201206            {
    202                 // initialise kernel_heap[x][y] descriptor
     207                // initialise kernel_heap[x][y] descriptor to empty
    203208                kernel_heap[x][y].heap_base  = 0;
    204209                kernel_heap[x][y].heap_size  = 0;
    205                 _spin_lock_init( &kernel_heap[x][y].lock );
    206210            }
    207211            else       // kernel heap found in cluster[x][y]
    … …  
    223227                }
    224228
    225                 // initialise the free[] array
    226                 for ( index = 0 ; index < 32 ; index++ )
     229                // compute size of block containin alloc[] array
     230                alloc_size = heap_size / MIN_BLOCK_SIZE;
     231                if ( alloc_size < MIN_BLOCK_SIZE) alloc_size = MIN_BLOCK_SIZE;
     232
     233                // get index for the corresponding block
     234                alloc_index = GET_SIZE_INDEX( alloc_size );
     235
     236                // compute alloc[] array base address
     237                alloc_base = heap_base + heap_size - alloc_size;
     238
     239                // reset the free[] array
     240                for ( index = 0 ; index < 32 ; index++ )
    227241                {
    228                     if (index == heap_index) kernel_heap[x][y].free[index] = heap_base;
    229                     else                     kernel_heap[x][y].free[index] = 0;
     242                    kernel_heap[x][y].free[index] = 0;
    230243                }
    231244
    232                 // initialise kernel_heap[x][y] descriptor
     245                // reset the alloc_size array
     246                memset( (unsigned char*)alloc_base , 0 , alloc_size );
     247 
     248                // split the heap into various sizes blocks,
     249                // initializes the free[] array and NEXT pointers
     250                // base is the block base address
     251                unsigned int   base = heap_base;
     252                unsigned int*  ptr;
     253                for ( index = heap_index-1 ; index >= alloc_index ; index-- )
     254                {
     255                    kernel_heap[x][y].free[index] = base;
     256                    ptr = (unsigned int*)base;
     257                    *ptr = 0;
     258                    base = base + (1<<index);
     259                }
     260
    233261                kernel_heap[x][y].heap_base  = heap_base;
    234262                kernel_heap[x][y].heap_size  = heap_size;
     263                kernel_heap[x][y].alloc_size = alloc_size;
     264                kernel_heap[x][y].alloc_base = alloc_base;
     265
     266                // initialise lock
    235267                _spin_lock_init( &kernel_heap[x][y].lock );
    236268            }
    … …  
    338370    unsigned int requested_index = GET_SIZE_INDEX( size );
    339371
    340     // take the lock
     372    // get the lock protecting heap[x][y]
    341373    _spin_lock_acquire( &kernel_heap[x][y].lock );
    342374
    343     // call the recursive function get_block
     375    // call the recursive function get_block()
    344376    unsigned int base = _get_block( &kernel_heap[x][y],
    345377                                    requested_index,
    346378                                    requested_index );
     379
     380    // check block found
     381    if ( base == 0 )
     382    {
     383        _nolock_printf("\n[GIET ERROR] in _remote_malloc() : "
     384                       "no more space in kernel_heap[%d][%d]\n", x , y );
     385        _spin_lock_release( &kernel_heap[x][y].lock );
     386        _exit();
     387    }
     388
     389    // compute pointer in alloc[] array
     390    unsigned offset    = (base - kernel_heap[x][y].heap_base) / MIN_BLOCK_SIZE;
     391    unsigned char* ptr = (unsigned char*)(kernel_heap[x][y].alloc_base + offset);
     392
     393    // check the alloc[] array
     394    if ( *ptr != 0 )
     395    {
     396        _nolock_printf("\n[GIET ERROR] in _remote_malloc() for heap[%d][%d] "
     397                       "selected block %X already allocated...\n", x , y , base );
     398        _spin_lock_release( &kernel_heap[x][y].lock );
     399        _exit();
     400    }
     401
     402    // update alloc_array
     403    *ptr = requested_index;
     404
    347405    // release the lock
    348406    _spin_lock_release( &kernel_heap[x][y].lock );
    349407 
    350     if ( base == 0 )
    351     {
    352         _nolock_printf("\n[GIET ERROR] _remote_malloc() : no more space "
    353                        "in heap[%d][%d]", x, y );
    354     }
    355 
    356408#if GIET_DEBUG_SYS_MALLOC
    357 _nolock_printf("\n[DEBUG KERNEL_MALLOC] malloc vaddr %x from kernel_heap[%d][%d]\n",
    358                base , x , y );
     409_nolock_printf("\n[DEBUG KERNEL_MALLOC] _remote-malloc()"
     410               " / vaddr %x / size = %x from heap[%d][%d]\n", base , size, x , y );
    359411_display_free_array(x,y);
    360412#endif
    … …  
    365417
    366418
     419
     420//////////////////////////////////
     421void* _malloc( unsigned int size )
     422{
     423    unsigned int procid  = _get_procid();
     424    unsigned int x       = procid >> (Y_WIDTH + P_WIDTH);
     425    unsigned int y       = (procid >> P_WIDTH) & ((1<<Y_WIDTH)-1);
     426
     427    return _remote_malloc( size , x , y );
     428
     429}  // end _malloc()
     430
     431
     432///////////////////////////////////////////////
     433void _update_free_array( kernel_heap_t*  heap,
     434                         unsigned int    base,
     435                         unsigned int    size_index )
     436{
     437    // This recursive function try to merge the released block
     438    // with the companion block if this companion block is free.
     439    // This companion has the same size, and almost the same address
     440    // (only one address bit is different)
     441    // - If the companion is not in free[size_index],
     442    //   the released block is pushed in free[size_index].
     443    // - If the companion is found, it is evicted from free[size_index]
     444    //   and the merged bloc is pushed in the free[size_index+1].
     445
     446    // compute released block size
     447    unsigned int size = 1<<size_index;
     448
     449    // compute companion block and merged block base address
     450    unsigned int companion_base;
     451    unsigned int merged_base; 
     452
     453    if ( (base & size) == 0 )   // the released block is aligned on (size*2)
     454    {
     455        companion_base  = base + size;
     456        merged_base     = base;
     457    }
     458    else
     459    {
     460        companion_base  = base - size;
     461        merged_base     = base - size;
     462    }
     463
     464#if GIET_DEBUG_SYS_MALLOC > 1
     465_nolock_printf("\n[DEBUG KERNEL_MALLOC] _update_free_array() :\n"
     466               " - size           = %X\n"
     467               " - released_base  = %X\n"
     468               " - companion_base = %X\n"
     469               " - merged_base    = %X\n",
     470               size , base , companion_base , merged_base , (base & size) );
     471#endif
     472
     473    // scan all blocks in free[size_index]
     474    // the iter & prev variables are actually addresses
     475    unsigned int  found = 0;
     476    unsigned int  iter  = heap->free[size_index];
     477    unsigned int  prev  = (unsigned int)(&heap->free[size_index]);
     478    while ( iter )
     479    {
     480        if ( iter == companion_base )
     481        {
     482            found = 1;
     483            break;
     484        }
     485        prev = iter;
     486        iter = *(unsigned int*)iter;
     487    }
     488
     489    if ( found == 0 )  // Companion not found => register in free[size_index]
     490    {
     491
     492#if GIET_DEBUG_SYS_MALLOC > 1
     493_nolock_printf("\n[DEBUG KERNEL_MALLOC] _update_free_array() : companion "
     494               " not found => register block %x in free[%d]", base , size );
     495#endif
     496
     497        // push the block in free[size_index] 
     498        *(unsigned int*)base   = heap->free[size_index];
     499        heap->free[size_index] = base;
     500    }
     501    else               // Companion found : merge and try in free[size_index + 1]
     502    {
     503        // pop the companion block (address == iter) from free[size_index]
     504        *(unsigned int*)prev = *(unsigned int*)iter;
     505
     506        // call the update_free() function for free[size_index+1]
     507        _update_free_array( heap, merged_base , size_index+1 );
     508    }
     509}  // end _update_free_array()
     510
     511
     512
     513///////////////////////
     514void _free( void* ptr )
     515{
     516    // get cluster coordinates from ptr value
     517    unsigned int x;
     518    unsigned int y;
     519    _sys_xy_from_ptr( ptr, &x, &y );
     520
     521    // check ptr value
     522    unsigned int base = (unsigned int)ptr;
     523    if ( (base < kernel_heap[x][y].heap_base) ||
     524         (base >= (kernel_heap[x][y].heap_base + kernel_heap[x][y].heap_size)) )
     525    {
     526        _printf("\n[GIET ERROR] in _free() : illegal pointer for released block");
     527        _exit();
     528    }
     529 
     530    // get the lock protecting heap[x][y]
     531    _spin_lock_acquire( &kernel_heap[x][y].lock );
     532
     533    // compute released block index in alloc[] array
     534    unsigned index = (base - kernel_heap[x][y].heap_base ) / MIN_BLOCK_SIZE;
     535 
     536    // get the released block size_index
     537    unsigned char* pchar      = (unsigned char*)(kernel_heap[x][y].alloc_base + index);
     538    unsigned int   size_index = (unsigned int)*pchar;
     539
     540    // check block allocation
     541    if ( size_index == 0 )
     542    {
     543        _printf("\n[GIET ERROR] in _free() : released block %X not allocated "
     544                "in kernel_heap[%d][%d]\n", (unsigned int)ptr , x , y );
     545        _spin_lock_release( &kernel_heap[x][y].lock );
     546        _exit();
     547    }
     548
     549    // check released block alignment
     550    if ( base % (1 << size_index) )
     551    {
     552        _printf("\n[GIET ERROR] in _free() : released block %X not aligned "
     553                "in kernel_heap[%d][%d]\n", (unsigned int)ptr , x , y );
     554        _spin_lock_release( &kernel_heap[x][y].lock );
     555        _exit();
     556    }
     557
     558    // remove block from allocated blocks array
     559    *pchar = 0;
     560
     561    // call the recursive function update_free_array()
     562    _update_free_array( &kernel_heap[x][y] , base , size_index );
     563
     564    // release the lock
     565    _spin_lock_release( &kernel_heap[x][y].lock );
     566
     567#if GIET_DEBUG_SYS_MALLOC
     568_nolock_printf("\n[DEBUG KERNEL_MALLOC] _free() : vaddr = %x / size = %x "
     569               "to heap[%d][%d]\n", (unsigned int)ptr , 1<<size_index , x , y );
     570_display_free_array(x,y);
     571#endif
     572
     573}  // end _free()
    367574
    368575// Local Variables:

  • soft/giet_vm/giet_common/kernel_malloc.h

    r495 r594  
    2727    unsigned int   heap_base;       // heap base address
    2828    unsigned int   heap_size;       // heap size (bytes)
     29    unsigned int   alloc_base;      // alloc[] array base address
     30    unsigned int   alloc_size;      // alloc[] array size (bytes)
    2931    unsigned int   free[32];        // array of base addresses of free blocks
    3032                                    // (address of first block of a given size)
    … …  
    4143//////////////////////////////////////////////////////////////////////////////////
    4244
     45extern void* _malloc( unsigned int size );
     46
    4347extern void* _remote_malloc( unsigned int size,
    4448                             unsigned int x,
    4549                             unsigned int y );
     50
     51extern void _free( void* ptr );
    4652
    4753extern void _heap_init();

  • soft/giet_vm/giet_common/tty0.c

    r495 r594  
    218218                {
    219219                    buf[7 - i] = HexaTab[val % 16];
    220                     if (!(val /= 16))  break;
     220                    if (!(val = (val>>4)))  break;
    221221                }
    222222                len =  i + 1;
    223223                pbuf = &buf[7 - i];
     224                break;
     225            }
     226            case ('X'):             /* 32 bits hexadecimal unsigned  on 10 char*/
     227            {
     228                unsigned int val = va_arg( *args , unsigned int );
     229                if ( _tty0_write( "0x" , 2 ) ) goto return_error;
     230                for(i = 0; i < 8; i++)
     231                {
     232                    buf[7 - i] = HexaTab[val % 16];
     233                    val = (val>>4);
     234                }
     235                len =  8;
     236                pbuf = buf;
    224237                break;
    225238            }

  • soft/giet_vm/giet_common/utils.c

    r523 r594  
    596596}
    597597
     598////////////////////////////////////
     599unsigned int _strlen( char* string )
     600{
     601    unsigned int i = 0;
     602    while ( string[i] != 0 ) i++;
     603    return i;
     604}
     605
    598606///////////////////////////////////////
    599607unsigned int _strncmp( const char * s1,
    … …  
    616624
    617625    while (*source)
    618         *(dest++) = *(source++);
    619 
     626    {
     627        *(dest) = *(source);
     628        dest++;
     629        source++;
     630    }
     631    *dest = 0;
    620632    return dest;
    621633}
    … …  
    717729
    718730/////////////////////////////////
    719 void * memset( void*        dst,
    720                int          value,
    721                unsigned int count )
     731void* memset( void*        dst,
     732              int          value,
     733              unsigned int count )
    722734{
    723735    // word-by-word copy

  • soft/giet_vm/giet_common/utils.h

    r523 r594  
    151151extern void         _break( char* str);
    152152
     153extern unsigned int _strlen( char* str);
     154
    153155extern unsigned int _strncmp(const char*  s1,
    154156                             const char*  s2,
Note: See TracChangeset for help on using the changeset viewer.