////////////////////////////////////////////////////////////////////////////////
// File     : malloc.c
// Date     : 05/03/2013
// Author   : Jean-Baptiste Bréjon / alain greiner
// Copyright (c) UPMC-LIP6
////////////////////////////////////////////////////////////////////////////////

#include "malloc.h"
#include "stdio.h"

// Global variables defining the heap descriptors array (one heap per cluster)
giet_heap_t 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
////////////////////////////////
void heap_init( unsigned int x,
                unsigned int y )
{
    unsigned int heap_base;        // heap segment base
    unsigned int heap_size;        // heap segment size
    unsigned int heap_index;       // size_index in free[array]

    unsigned int alloc_base;       // alloc[] array base 
    unsigned int alloc_size;       // alloc[] array size
    unsigned int alloc_index;      // size_index in free[array]

    unsigned int index;            // iterator

    // get heap_base, heap size, and heap index
    giet_heap_info( &heap_base, &heap_size, x, y );
    heap_index = GET_SIZE_INDEX( heap_size );

    // checking heap segment constraints
    if ( heap_size == 0 )                                    // heap segment exist
    {
        giet_exit("ERROR in malloc() : heap not found \n");
    }
    if ( heap_size != (1<<heap_index) )                      // heap size power of 2
    {
        giet_exit("ERROR in malloc() : heap size must be power of 2\n");
    }
    if ( heap_base % heap_size )                             // heap segment aligned
    {
        giet_exit("ERROR in malloc() : heap segment must be aligned\n");
    }

    // compute size of block containin alloc[] array 
    alloc_size = heap_size / MIN_BLOCK_SIZE;
    if ( alloc_size < MIN_BLOCK_SIZE) alloc_size = MIN_BLOCK_SIZE;

    // get index for the corresponding block
    alloc_index = GET_SIZE_INDEX( alloc_size );

    // compute alloc[] array base address
    alloc_base = heap_base + heap_size - alloc_size;

    // reset the free[] array 
    for ( index = 0 ; index < 32 ; index++ )
    {
        heap[x][y].free[index] = 0;
    }

    // split the heap into various sizes blocks,
    // initializes the free[] array and NEXT pointers
    // base is the block base address
    unsigned int   base = heap_base;
    unsigned int*  ptr;
    for ( index = heap_index-1 ; index >= alloc_index ; index-- )
    {
        heap[x][y].free[index] = base;
        ptr = (unsigned int*)base;
        *ptr = 0;
        base = base + (1<<index);
    }

    heap[x][y].init       = HEAP_INITIALIZED;
    heap[x][y].x          = x;
    heap[x][y].y          = y;
    heap[x][y].heap_base  = heap_base;
    heap[x][y].heap_size  = heap_size;
    heap[x][y].alloc_size = alloc_size;
    heap[x][y].alloc_base = alloc_base;

    lock_release( &heap[x][y].lock );

#if GIET_DEBUG_MALLOC
giet_shr_printf("\n[MALLOC DEBUG] Heap[%d][%d] initialisation\n"
                " - heap_base  = %x\n"
                " - heap_size  = %x\n"
                " - alloc_base = %x\n"
                " - alloc_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",
                heap[x][y].x, heap[x][y].y, 
                heap[x][y].heap_base, heap[x][y].heap_size, 
                heap[x][y].alloc_base, heap[x][y].alloc_size,
                heap[x][y].free[0], heap[x][y].free[1], 
                heap[x][y].free[2], heap[x][y].free[3],
                heap[x][y].free[4], heap[x][y].free[5],
                heap[x][y].free[6], heap[x][y].free[7],
                heap[x][y].free[8], heap[x][y].free[9],
                heap[x][y].free[10], heap[x][y].free[11],
                heap[x][y].free[12], heap[x][y].free[13],
                heap[x][y].free[14], heap[x][y].free[15],
                heap[x][y].free[16], heap[x][y].free[17],
                heap[x][y].free[18], heap[x][y].free[19],
                heap[x][y].free[20], heap[x][y].free[21],
                heap[x][y].free[22], heap[x][y].free[23] );
#endif
                
}  // end heap_init()

////////////////////////////////////////////
unsigned int split_block( giet_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 )  // terminal case: 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( giet_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 (size == 0) 
    {
        giet_exit("ERROR in malloc() : requested size = 0 \n");
    }
    if ( x >= X_SIZE )
    {
        giet_exit("ERROR in malloc() : x coordinate too large\n");
    }
    if ( y >= Y_SIZE )
    {
        giet_exit("ERROR in malloc() : y coordinate too large\n");
    }

    // initializes the heap if first access
    if ( heap[x][y].init != HEAP_INITIALIZED )
    {
        heap_init( x, y );
    }

    // 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 protecting access to heap(x,y)
    lock_acquire( &heap[x][y].lock );

    // call the recursive function get_block
    unsigned int base = get_block( &heap[x][y], 
                                   requested_index, 
                                   requested_index );

    // update the alloc[] array if block found
    if ( base != 0 )
    {
        unsigned offset = (base - heap[x][y].heap_base) / MIN_BLOCK_SIZE;
        unsigned char* ptr = (unsigned char*)(heap[x][y].alloc_base + offset);
        *ptr = requested_index;
    }

    // release the lock
    lock_release( &heap[x][y].lock );
 
    return (void*)base;

} // end remote_malloc()


//////////////////////////////////
void * malloc( unsigned int size )
{
    unsigned int proc_id    = giet_procid();
    unsigned int cluster_xy = proc_id / NB_PROCS_MAX;
    unsigned int x          = cluster_xy >> Y_WIDTH;
    unsigned int y          = cluster_xy & ((1<<Y_WIDTH)-1);

    return remote_malloc( size, x, y );
} 


//////////////////////
void free( void* ptr )
{
    unsigned int vaddr = (unsigned int)ptr;

    // get the cluster coordinate
    unsigned int x;
    unsigned int y;
    giet_get_xy( ptr, &x, &y );

    // compute index in alloc[] array
    unsigned index = ( (unsigned int)ptr - heap[x][y].heap_base ) / MAX_BLOCK_SIZE;
 
    // get the freed block size_index
    unsigned char* p i        = (unsigned char*)(heap[x][y].alloc_base + index);
    unsigned int   size_index = (unsigned int)*p;

    // update the free[] array and NEXT pointer
    *(unsigned int*)ptr         = heap[x][y].free[size_index];
    heap[x][y].free[size_index] = (unsigned int)ptr;
    
    // TODO try to concatenate with another free block of same size
    // this require probably to replace this simple push by a recursive function
}




// 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