source: trunk/kernel/mm/khm.c @ 14

/*
 * khm.c - kernel heap manager implementation.
 * 
 * Authors  Ghassan Almaless (2008,2009,2010,2011,2012)
 *          Alain Greiner (2016)
 *
 * Copyright (c)  UPMC Sorbonne Universites
 *
 * This file is part of ALMOS-MKH.
 *
 * ALMOS-MKH is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by
 * the Free Software Foundation; version 2.0 of the License.
 *
 * ALMOS-MKH is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with ALMOS-MKH; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
 */

#include <kernel_config.h>
#include <hal_types.h>
#include <hal_special.h>
#include <spinlock.h>
#include <bits.h>
#include <printk.h>
#include <thread.h>
#include <cluster.h>
#include <page.h>
#include <ppm.h>
#include <khm.h>


////////////////////////////
void khm_init( khm_t * khm )
{
    // check config parameters
    assert( ((CONFIG_PPM_PAGE_SHIFT + CONFIG_PPM_HEAP_ORDER) < 32 ) , __FUNCTION__ ,
             "CONFIG_PPM_HEAP_ORDER too large" );

    // initialize lock
        spinlock_init( &khm->lock );  
    
    //  compute kernel heap size 
    intptr_t heap_size = (1 << CONFIG_PPM_HEAP_ORDER) << CONFIG_PPM_PAGE_SHIFT;

    // get kernel heap base from PPM 
    page_t * page      = ppm_alloc_pages( CONFIG_PPM_HEAP_ORDER );
    void   * heap_base = ppm_page2base( page );

    // initializes first block == complete heap
        khm_block_t * block = (khm_block_t *)heap_base;
        block->size = heap_size;
        block->busy = 0;

    // initializes KHM fields
        khm->base    = (intptr_t)heap_base;
        khm->size    = heap_size;
        khm->next    = (intptr_t)heap_base;
}

/////////////////////////////////
void * khm_alloc( khm_t    * khm, 
                  uint32_t   size )
{
        khm_block_t  * current;        
        khm_block_t  * next;
        uint32_t       effective_size;

    // compute actual block size
        effective_size = size + sizeof(khm_block_t);
        effective_size = ARROUND_UP( effective_size, CONFIG_CACHE_LINE_SIZE );

    // get lock protecting heap
        spinlock_lock( &khm->lock );
  
    // define a starting block to scan existing blocks 
    if( ((khm_block_t*)khm->next)->size < effective_size ) current = (khm_block_t*)khm->base;
    else                                                   current = (khm_block_t*)khm->next;

    // scan all existing blocks to find a large enough free block
        while( current->busy || (current->size < effective_size)) 
        {
        // get next block pointer
                current = (khm_block_t*)((char*)current + current->size);
    
                if( (intptr_t)current >= (khm->base + khm->size) )  // heap full
                {
                        spinlock_unlock(&khm->lock);

                        printk("\n[ERROR] in %s : failed to allocate block of size %d\n", 
                               __FUNCTION__ , effective_size );
                        return NULL;
                }
        }

    // split the current block if current block is too large
        if( (current->size - effective_size) >= CONFIG_CACHE_LINE_SIZE )
        {
        // update new free block features
                next           = (khm_block_t *)((char*)current + effective_size);
                next->size     = current->size - effective_size;
                next->busy     = 0;

        // register new free block
                khm->next = (intptr_t)next;

        // update allocated block features
                current->size  = effective_size;
                current->busy  = 1;
        }
        else
    {
        // change block state
                current->busy  = 1;
    }

    // release lock protecting heap
        spinlock_unlock( &khm->lock );

        return (char*)current + sizeof(khm_block_t);
}

///////////////////////////
void khm_free( void * ptr )
{
        khm_t * khm = &LOCAL_CLUSTER->khm;

        khm_block_t * current;
        khm_block_t * next;
  
        if(ptr == NULL) return;
  
        current = (khm_block_t *)((char*)ptr - sizeof(khm_block_t));
 
    // get lock protecting heap
        spinlock_lock(&khm->lock);

    // release block 
        current->busy = 0;
  
    // try to merge released block with the next
        while ( 1 )
        { 
        next = (khm_block_t*)((char*)current + current->size);
                if ( ((intptr_t)next >= (khm->base + khm->size)) || (next->busy == 1) ) break;
                current->size += next->size;
        }

        if( (intptr_t)current < khm->next ) khm->next = (intptr_t)current;
  
    // release lock protecting heap
        spinlock_unlock( &khm->lock );
}