source: soft/giet_vm/giet_common/kernel_malloc.c @ 564

////////////////////////////////////////////////////////////////////////////////
// File     : kernel_malloc.c
// Date     : 05/12/2014
// Author   : alain greiner
// Copyright (c) UPMC-LIP6
////////////////////////////////////////////////////////////////////////////////
//   Implementation note:
// - As this code is used to implement the SQT lock ptotecting TTY0,
//   all functions here use the kernel _nolock_printf() function.
// - It must exist one vseg with the HEAP type in each cluster. The length
//   must be a power of 2, and the base address must be aligned.
// - All allocated blocks have a size that is a power of 2, larger or equal
//   to MIN_BLOCK_SIZE (typically 64 bytes), and are aligned.
// - All free blocks are pre-classed in 32 linked lists of free blocks, where 
//   all blocks in the same list have the same size. 
// - The NEXT pointer implementing those linked lists is written 
//   in the 4 first bytes of the block itself, using the unsigned int type.
// - The pointers on the first free block for each size are stored in an
//   array of pointers free[32] in the heap[x][y) structure itself.
// - Each kernel_heap[x][y] structure is protected by a specific 
//   queuing spin-lock.
// - The block size required can be any value, but the allocated block size
//   is the smallest power of 2 value larger or equal to the requested size.
// - It pop the linked list of free blocks corresponding to size,
//   and returns the block B if the list[size] is not empty.
// - If the list[size] is empty, it pop the list[size * 2].
//   If a block B' is found, it break this block in 2 B/2 blocks, returns 
//   the first B/2 block and push the other B/2 block into list[size].
// - If the list[size * 2] is empty, it pop the list[size * 4].
//   If a block B is found, it break this block in 3 blocks B/4, B/4 and B/2,
//   returns the first B/4 block, push the other blocks B/4 and B/2 into
//   the proper lists. etc... 
////////////////////////////////////////////////////////////////////////////////

#include "giet_config.h"
#include "hard_config.h"
#include "mapping_info.h"
#include "kernel_malloc.h"
#include "kernel_locks.h"
#include "tty0.h"
#include "utils.h"

///////////////////////////////////////////////////////////////////////////////
// Global variables defining the heap descriptors array (one heap per cluster)
///////////////////////////////////////////////////////////////////////////////

__attribute__((section(".kdata")))
kernel_heap_t kernel_heap[X_SIZE][Y_SIZE];

///////////////////////////////////////////////////////////////////////////////
// Macro returning the smallest power of 2 larger or equal to size value
///////////////////////////////////////////////////////////////////////////////
#define GET_SIZE_INDEX(size)                (size <= 0x00000001) ? 0  :\
                                            (size <= 0x00000002) ? 1  :\
                                            (size <= 0x00000004) ? 2  :\
                                            (size <= 0x00000008) ? 3  :\
                                            (size <= 0x00000010) ? 4  :\
                                            (size <= 0x00000020) ? 5  :\
                                            (size <= 0x00000040) ? 6  :\
                                            (size <= 0x00000080) ? 7  :\
                                            (size <= 0x00000100) ? 8  :\
                                            (size <= 0x00000200) ? 9  :\
                                            (size <= 0x00000400) ? 10 :\
                                            (size <= 0x00000800) ? 11 :\
                                            (size <= 0x00001000) ? 12 :\
                                            (size <= 0x00002000) ? 13 :\
                                            (size <= 0x00004000) ? 14 :\
                                            (size <= 0x00008000) ? 15 :\
                                            (size <= 0x00010000) ? 16 :\
                                            (size <= 0x00020000) ? 17 :\
                                            (size <= 0x00040000) ? 18 :\
                                            (size <= 0x00080000) ? 19 :\
                                            (size <= 0x00100000) ? 20 :\
                                            (size <= 0x00200000) ? 21 :\
                                            (size <= 0x00400000) ? 22 :\
                                            (size <= 0x00800000) ? 23 :\
                                            (size <= 0x01000000) ? 24 :\
                                            (size <= 0x02000000) ? 25 :\
                                            (size <= 0x04000000) ? 26 :\
                                            (size <= 0x08000000) ? 27 :\
                                            (size <= 0x10000000) ? 28 :\
                                            (size <= 0x20000000) ? 29 :\
                                            (size <= 0x40000000) ? 30 :\
                                            (size <= 0x80000000) ? 31 :\
                                                                   32

#if GIET_DEBUG_SYS_MALLOC
////////////////////////////////////////////////
static void _display_free_array( unsigned int x,
                                 unsigned int y )
{
    _nolock_printf(" Kernel Heap[%d][%d]\n"
                   " - heap_base   = %x\n"
                   " - heap_size   = %x\n"
                   " - free[0]     = %x\n"
                   " - free[1]     = %x\n"
                   " - free[2]     = %x\n"
                   " - free[3]     = %x\n"
                   " - free[4]     = %x\n"
                   " - free[5]     = %x\n"
                   " - free[6]     = %x\n"
                   " - free[7]     = %x\n"
                   " - free[8]     = %x\n"
                   " - free[9]     = %x\n"
                   " - free[10]    = %x\n"
                   " - free[11]    = %x\n"
                   " - free[12]    = %x\n"
                   " - free[13]    = %x\n"
                   " - free[14]    = %x\n"
                   " - free[15]    = %x\n"
                   " - free[16]    = %x\n"
                   " - free[17]    = %x\n"
                   " - free[18]    = %x\n"
                   " - free[19]    = %x\n"
                   " - free[20]    = %x\n"
                   " - free[21]    = %x\n"
                   " - free[22]    = %x\n"
                   " - free[23]    = %x\n",
                   x, y, 
                   kernel_heap[x][y].heap_base, kernel_heap[x][y].heap_size, 
                   kernel_heap[x][y].free[0] , kernel_heap[x][y].free[1], 
                   kernel_heap[x][y].free[2] , kernel_heap[x][y].free[3],
                   kernel_heap[x][y].free[4] , kernel_heap[x][y].free[5],
                   kernel_heap[x][y].free[6] , kernel_heap[x][y].free[7],
                   kernel_heap[x][y].free[8] , kernel_heap[x][y].free[9],
                   kernel_heap[x][y].free[10], kernel_heap[x][y].free[11],
                   kernel_heap[x][y].free[12], kernel_heap[x][y].free[13],
                   kernel_heap[x][y].free[14], kernel_heap[x][y].free[15],
                   kernel_heap[x][y].free[16], kernel_heap[x][y].free[17],
                   kernel_heap[x][y].free[18], kernel_heap[x][y].free[19],
                   kernel_heap[x][y].free[20], kernel_heap[x][y].free[21],
                   kernel_heap[x][y].free[22], kernel_heap[x][y].free[23]);
}  // end display_free array()
#endif




/////////////////////////////////////////////////////
unsigned int _get_heap_info( unsigned int* heap_base,
                             unsigned int* heap_size,
                             unsigned int  x,
                             unsigned int  y )
{
    mapping_header_t  * header   = (mapping_header_t *)SEG_BOOT_MAPPING_BASE;
    mapping_vseg_t    * vsegs    = _get_vseg_base(header);
    mapping_pseg_t    * psegs    = _get_pseg_base(header);
    mapping_cluster_t * clusters = _get_cluster_base(header);

    unsigned int vseg_id;
    unsigned int pseg_id;
    unsigned int cluster_id;

    // checking coordinates
    if ( (x >= X_SIZE) || (y >= Y_SIZE) )
    {
        _nolock_printf("\n[GIET ERROR] _get_heap_info()"
                       " illegal (%d,%d) coordinates\n", x , y );
        _exit();
    }

    // scan all global vsegs
    for ( vseg_id = 0 ; vseg_id < header->globals ; vseg_id++ )
    {
        pseg_id    = vsegs[vseg_id].psegid;
        cluster_id = psegs[pseg_id].clusterid;
        if ( (vsegs[vseg_id].type == VSEG_TYPE_HEAP) &&
             (clusters[cluster_id].x == x) && 
             (clusters[cluster_id].y == y) )
        {
            *heap_base = vsegs[vseg_id].vbase;
            *heap_size = vsegs[vseg_id].length;
            return 0;
        }
    }

    return 1;
} // end _get_heap_info()



/////////////////
void _heap_init()
{
    unsigned int heap_base;
    unsigned int heap_size;
    unsigned int heap_index;
    unsigned int index;
    unsigned int x;
    unsigned int y;
    unsigned int ko;

    for ( x = 0 ; x < X_SIZE ; x++ )
    {
        for ( y = 0 ; y < Y_SIZE ; y++ )
        {
            // get heap_base, heap size, and heap index
            ko = _get_heap_info( &heap_base, &heap_size, x, y );
       
            if ( ko )  // no kernel heap found in cluster[x][y]
            {
                // initialise kernel_heap[x][y] descriptor
                kernel_heap[x][y].heap_base  = 0;
                kernel_heap[x][y].heap_size  = 0;
                _spin_lock_init( &kernel_heap[x][y].lock );
            }
            else       // kernel heap found in cluster[x][y]
            {
                heap_index = GET_SIZE_INDEX( heap_size );

                // check heap[x][y] constraints
                if ( heap_size != (1<<heap_index) )
                {
                    _nolock_printf("\n[GIET ERROR] in _heap_init()"
                                   " kernel_heap[‰d,‰d] not power of 2\n", x , y );
                    _exit();
                }
                if ( heap_base % heap_size ) 
                {
                    _nolock_printf("\n[GIET ERROR] in _heap_init()"
                                   " kernel_heap[‰d,‰d] not aligned\n", x , y );
                    _exit();
                }

                // initialise the free[] array 
                for ( index = 0 ; index < 32 ; index++ ) 
                {
                    if (index == heap_index) kernel_heap[x][y].free[index] = heap_base;
                    else                     kernel_heap[x][y].free[index] = 0;
                }

                // initialise kernel_heap[x][y] descriptor
                kernel_heap[x][y].heap_base  = heap_base;
                kernel_heap[x][y].heap_size  = heap_size;
                _spin_lock_init( &kernel_heap[x][y].lock );
            }

#if GIET_DEBUG_SYS_MALLOC
_nolock_printf("\n[DEBUG KERNEL_MALLOC] Completing kernel_heap[%d][%d]"
               " initialisation\n", x, y );
_display_free_array(x,y);
#endif
                
        }
    }
}  // end _heap_init()



//////////////////////////////////////////////
unsigned int _split_block( kernel_heap_t* heap,
                           unsigned int   vaddr, 
                           unsigned int   searched_index,
                           unsigned int   requested_index )
{
    // push the upper half block into free[searched_index-1]
    unsigned int* new            = (unsigned int*)(vaddr + (1<<(searched_index-1)));
    *new                         = heap->free[searched_index-1]; 
    heap->free[searched_index-1] = (unsigned int)new;
        
    if ( searched_index == requested_index + 1 )  //  return lower half block 
    {
        return vaddr;
    }
    else            // non terminal case : lower half block must be split again
    {                               
        return _split_block( heap, vaddr, searched_index-1, requested_index );
    }
} // end _split_block()



/////////////////////////////////////////////
unsigned int _get_block( kernel_heap_t* heap,
                         unsigned int   searched_index,
                         unsigned int   requested_index )
{
    // test terminal case
    if ( (1<<searched_index) > heap->heap_size )  // failure : return a NULL value
    {
        return 0;
    }
    else                            // search a block in free[searched_index]
    {
        unsigned int vaddr = heap->free[searched_index];
        if ( vaddr == 0 )     // block not found : search in free[searched_index+1]
        {
            return _get_block( heap, searched_index+1, requested_index );
        }
        else                // block found : pop it from free[searched_index] 
        {
            // pop the block from free[searched_index]
            unsigned int next = *((unsigned int*)vaddr); 
            heap->free[searched_index] = next;
            
            // test if the block must be split
            if ( searched_index == requested_index )  // no split required
            {
                return vaddr;
            }
            else                                      // split is required
            {
                return _split_block( heap, vaddr, searched_index, requested_index );
            }
        } 
    }
} // end _get_block()



////////////////////////////////////////
void* _remote_malloc( unsigned int size,
                      unsigned int x,
                      unsigned int y ) 
{
    // checking arguments
    if ( x >= X_SIZE )
    {
        _nolock_printf("\n[GIET ERROR] _remote_malloc() : x coordinate too large\n");
        _exit();
    }
    if ( y >= Y_SIZE )
    {
        _nolock_printf("\n[GIET ERROR] _remote_malloc() : y coordinate too large\n");
        _exit();
    }
    if ( kernel_heap[x][y].heap_size == 0 )
    {
        _nolock_printf("\n[GIET ERROR] _remote_malloc() : No heap[%d][%d]\n", x, y );
        _exit();
     
    }

    // normalize size
    if ( size < MIN_BLOCK_SIZE ) size = MIN_BLOCK_SIZE;

    // compute requested_index for the free[] array
    unsigned int requested_index = GET_SIZE_INDEX( size );

    // take the lock 
    _spin_lock_acquire( &kernel_heap[x][y].lock );

    // call the recursive function get_block
    unsigned int base = _get_block( &kernel_heap[x][y], 
                                    requested_index, 
                                    requested_index );
    // release the lock
    _spin_lock_release( &kernel_heap[x][y].lock );
 
    if ( base == 0 )
    {
        _nolock_printf("\n[GIET ERROR] _remote_malloc() : no more space "
                       "in heap[%d][%d]", x, y );
    }

#if GIET_DEBUG_SYS_MALLOC
_nolock_printf("\n[DEBUG KERNEL_MALLOC] malloc vaddr %x from kernel_heap[%d][%d]\n", 
               base , x , y );
_display_free_array(x,y);
#endif

    return (void*)base;

} // end _remote_malloc()



// Local Variables:
// tab-width: 4
// c-basic-offset: 4
// c-file-offsets:((innamespace . 0)(inline-open . 0))
// indent-tabs-mode: nil
// End:
// vim: filetype=c:expandtab:shiftwidth=4:tabstop=4:softtabstop=4