pm-alloc.c

IBM source for pallas/vulcan/vesta

//pallas/drv/os/pm-alloc.c  version 0.1a
/*----------------------------------------------------------------------------+
|
|       This source code has been made available to you by IBM on an AS-IS
|       basis.  Anyone receiving this source is licensed under IBM
|       copyrights to use it in any way he or she deems fit, including
|       copying it, modifying it, compiling it, and redistributing it either
|       with or without modifications.  No license under IBM patents or
|       patent applications is to be implied by the copyright license.
|
|       Any user of this software should understand that IBM cannot provide
|       technical support for this software and will not be responsible for
|       any consequences resulting from the use of this software.
|
|       Any person who transfers this source code or any derivative work
|       must include the IBM copyright notice, this paragraph, and the
|       preceding two paragraphs in the transferred software.
|
|       COPYRIGHT   I B M   CORPORATION 1998
|       LICENSED MATERIAL  -  PROGRAM PROPERTY OF I B M
+----------------------------------------------------------------------------*/
//
//Comment: 
//  Physical memory block allocation routines  
//Revision Log:   
//  Sept/03/2001                         Created by YYD
//  Sept/05/2001                         Version 0.1 passed test    (YYD)
//  Oct/17/2001                          Add justified alloc        (YYD)
//  May/27/2002                          Rewrite to make it a generic 
//                                       physical heap manager (YYD)

// Compile time options :
//  Allocation strategies
//    #define __PM_ALLOC_OPTIMIZED_UTILIZATION__  // try to find best match block
//    #define __PM_ALLOC_DEBUG_CHECK_OVERRUN__       // we may check if there are memory overrun in many cases
//  Syncronization locks
//    Default is using critical sections if nothing is chosen
//    #define __PM_ALLOC_ATOM__    // if pm-alloc can be promised as atomic, else see below
//    #define __PM_ALLOC_SYNC_APP__    // if this is defined, we use only mutex to avoid re-entrance
//  Test
//    #define __PM_ALLOC_TEST__    // for testing only, should not be defined during normal use

#ifdef __PM_ALLOC_TEST__

#ifndef __PM_ALLOC_ATOM__
    #define __PM_ALLOC_ATOM__   // test is controled
#endif

#ifndef __PM_ALLOC_DEBUG
    #define  __PM_ALLOC_DEBUG 1
#endif

#define  __PM_ALLOC_DEBUG_CHECK_OVERRUN__
#define  __PM_ALLOC_OPTIMIZED_UTILIZATION__

#include <stdio.h>     // for test, std c header
#include <string.h>

// fake system functions
#define KERN_CRIT ""
#define KERN_INFO ""
#define KERN_NOTICE ""
#define printk(fmt, args...)    fprintf(stdout, fmt, ##args); fflush(stdout)
#define request_region(a, b, c)  (b)
#define release_region(a,b)
#define ioremap(a,b)    (a)
#define iounmap(a)

#ifndef __PM_ALLOC_ATOM__    // if pm-alloc can be promised as atomic
    // fake sync for test locks
    static int crit;
    #define PML_INIT()
    #define PML_DEINIT()
    static void PML_ENTER()
    {
      fprintf(stderr, "----------- Enter\n"); fflush(stderr);
      if(crit) {fprintf(stderr, "******** Mismatched enter/leave sync\n"); fflush(stderr);}
      crit=1;
    }

    static void PML_LEAVE()
    {
      if(crit) crit=0;
      else { fprintf(stderr, "********  Mismatched enter/leave sync\n"); fflush(stderr); }
      fprintf(stderr, "----------- Leave\n"); fflush(stderr);
    }
#endif

#else  // __PM_ALLOC_TEST__
// Begin Linux Specific Header
#include <linux/config.h>
#include <linux/kernel.h>
#include <linux/version.h>
#include <linux/stddef.h>
#include <linux/ioport.h>
#include <linux/string.h>    
#include <asm/io.h>
// End Linux Specific Header
#endif

#include "os/pm-alloc.h"
#include "os/helper-pool.h"
#include "os/os-generic.h"

#include "pm-alloc-local.h"

#ifdef __PM_ALLOC_ATOM__    // if pm-alloc can be promised as atomic
    #define PML_INIT()
    #define PML_ENTER()
    #define PML_LEAVE()
    #define PML_DEINIT()
#elif !defined(__PM_ALLOC_TEST__)    // for test, we defined the fake ones
    #include "os/os-sync.h"
    #ifdef __PM_ALLOC_SYNC_APP__    // if this is defined, we use only mutex to avoid re-entrance
        #define PML_INIT()   (pPMRoot->sync = (UINT32)os_create_mutex())
        #define PML_ENTER()  os_get_mutex((MUTEX_T)pPMRoot->sync)
        #define PML_LEAVE()  os_release_mutex((MUTEX_T)pPMRoot->sync)
        #define PML_DEINIT() os_delete_mutex((MUTEX_T)pPMRoot->sync)
    #else    // we need interrupt level protection
        #define PML_INIT()
        #define PML_ENTER()  (pPMRoot->sync = os_enter_critical_section())
        #define PML_LEAVE()  os_leave_critical_section(pPMRoot->sync)
        #define PML_DEINIT()
    #endif
#endif


//#define __PM_ALLOC_DEBUG
#define  __PM_ALLOC_DEBUG_CHECK_OVERRUN__
#define  __PM_ALLOC_OPTIMIZED_UTILIZATION__


#ifdef __PM_ALLOC_DEBUG
#define __DRV_DEBUG
#endif
#include "os/drv_debug.h"


// defined the root allocation data structure

#ifdef __PM_ALLOC_DEBUG
    PM_ALLOC_FREE_NODE_T *  __PM_GET_BLOCK_POINTER_DEBUG(PM_ALLOC_ROOT_T *pPMRoot, INT n)
    {
        if (n >= (INT)pPMRoot->uTotalUnits || n < 0)
        {
            PFATAL(" Try to use an invalid block pointer !\n");
            return NULL;
        }
        return ((PM_ALLOC_FREE_NODE_T *)pPMRoot->pLogicalAddress + (n));
    }
    #define __PM_GET_BLOCK_POINTER(n)  __PM_GET_BLOCK_POINTER_DEBUG(pPMRoot, n)
#else // use macro for speed
    #define __PM_GET_BLOCK_POINTER(n)    ((PM_ALLOC_FREE_NODE_T *)pPMRoot->pLogicalAddress + (n))
#endif

#ifdef __PM_ALLOC_DEBUG_CHECK_OVERRUN__    // we may check if there are memory overrun in many cases

static void __init_overrun_check(PM_ALLOC_ROOT_T *pPMRoot, UINT block)
{
    UINT i;
    PM_ALLOC_FREE_NODE_T *pNode;
    BYTE *ptr;

    pNode = __PM_GET_BLOCK_POINTER(block);
    // ok, fill pattern
    ptr = pNode->bDummy1;
    for(i=0; i<__PM_ALLOC_DUMMY1_SIZE; i++) ptr[i] = (BYTE)i;
    ptr = pNode->bDummy2;
    for(i=0; i<__PM_ALLOC_DUMMY2_SIZE; i++) ptr[i] = (BYTE)i;
    return;
}
static void __check_overrun(PM_ALLOC_ROOT_T *pPMRoot, UINT block)
{
    UINT i;
    PM_ALLOC_FREE_NODE_T *pNode;
    BYTE *ptr;
    pNode = __PM_GET_BLOCK_POINTER(block);
    // ok, check filled pattern
    ptr = pNode->bDummy1;
    for(i=0; i<__PM_ALLOC_DUMMY1_SIZE; i++) 
        if (ptr[i] != (BYTE)i)
        {
            PDEBUGE(" **** Buffer overrun detected !\n"
                   "  Before logical_addr= 0x%8.8x, physical_addr= 0x%8.8x\n",
                   (UINT)pNode, pPMRoot->uPhysicalAddress + block*__PM_ALLOC_UNIT); 
            for(; i<__PM_ALLOC_DUMMY1_SIZE; i++) ptr[i] = (BYTE)i; // reset it
            break;
        }
    ptr = pNode->bDummy2;
    for(i=0; i<__PM_ALLOC_DUMMY2_SIZE; i++) 
        if (ptr[i] != (BYTE)i)
        {
            PDEBUGE(" **** Buffer overrun detected !\n"
                   "  After logical_addr= 0x%8.8x, physical_addr= 0x%8.8x\n",
                   (UINT)pNode, pPMRoot->uPhysicalAddress + block*__PM_ALLOC_UNIT); 
            for(; i<__PM_ALLOC_DUMMY2_SIZE; i++) ptr[i] = (BYTE)i; // reset it
            break;
        }
    return;
}

#define INIT_OVERRUN_DET(root, block)        __init_overrun_check(root, block)
#define OVERRUN_DET(root, block)             __check_overrun(root, block)

#else    // don't check for overrun

#define INIT_OVERRUN_DET(root, block)
#define OVERRUN_DET(root, block)

#endif


static void __insert_new_free_block(PM_ALLOC_ROOT_T *pPMRoot, INT npNewBlock, UINT uNewBlockUnits, INT npNext, INT npPrev, int check_merge)
{
    PM_ALLOC_FREE_NODE_T *pNewBlock = __PM_GET_BLOCK_POINTER(npNewBlock);

    pNewBlock->npAddr = npNewBlock;
    pNewBlock->uUnits = uNewBlockUnits;
    pNewBlock->npNext = npNext;
    pNewBlock->npPrev = npPrev;
    if (npNext >= 0) // we need to adjust next block's prev pointer
    {
        PM_ALLOC_FREE_NODE_T *pNextBlock = __PM_GET_BLOCK_POINTER(npNext);
        if(npNewBlock + (INT)uNewBlockUnits > npNext) // error !!!
        {
            PFATAL("Find heap curruption (overlap) !\n");
            // any way, continue
        }
        pNextBlock->npPrev = npNewBlock;
    }

    if (npPrev >= 0) // we need to adjust prev block's next pointer
    {
        PM_ALLOC_FREE_NODE_T *pPrevBlock = __PM_GET_BLOCK_POINTER(npPrev);
        if(npPrev + (INT)pPrevBlock->uUnits > npNewBlock) // error !!!
        {
            PFATAL("Find heap curruption (overlap) !\n");
            // any way, continue
        }
        pPrevBlock->npNext = npNewBlock;
    }
    // then the last one is to init overrun detection by option
    INIT_OVERRUN_DET(pPMRoot, npNewBlock);

    // for the merge case
    if (check_merge)
    {
        if (npNext >= 0 && npNewBlock + (INT)uNewBlockUnits == npNext)  // first to try next
        {
            // Ok, merge
            PM_ALLOC_FREE_NODE_T *pNextBlock = __PM_GET_BLOCK_POINTER(npNext);
            uNewBlockUnits += pNextBlock->uUnits;
            npNext = pNextBlock->npNext;
            // simply eat it
            pNewBlock->npNext = npNext;
            pNewBlock->uUnits = uNewBlockUnits;
            if(npNext >= 0)  // adjust next->prev link
            {
                PM_ALLOC_FREE_NODE_T *pNextBlock = __PM_GET_BLOCK_POINTER(npNext);
                pNextBlock->npPrev = npNewBlock;
            }
        }
        if(npPrev >= 0)
        {
            PM_ALLOC_FREE_NODE_T *pPrevBlock = __PM_GET_BLOCK_POINTER(npPrev);
            if(npPrev + (INT)pPrevBlock->uUnits == npNewBlock) // ok merge
            {
                pPrevBlock->uUnits += uNewBlockUnits;
                pPrevBlock->npNext = npNext;
                if(npNext >= 0)  // adjust next->prev link
                {
                    PM_ALLOC_FREE_NODE_T *pNextBlock = __PM_GET_BLOCK_POINTER(npNext);
                    pNextBlock->npPrev = npPrev;
                }
            }
        }
    }
    return;
}




MEM_HANDLE_T pm_alloc_physical_justify(void *pRoot, UINT uNumBytes, UINT uJustify)
{
    UINT uReqUnits;
    UINT uJustifyUnits;
    UINT uJustifyAdjust;
    INT  npBestFitBlock;
    UINT uBestFitUnits;
    MEM_HANDLE_T hRtn = NULL;

    PM_ALLOC_ROOT_T *pPMRoot = (PM_ALLOC_ROOT_T *) pRoot;

    if(!pPMRoot || pPMRoot->init_magic != __PM_INIT_MAGIC) 
    {
        PFATAL("Tried to use an invalid heap root pointer !\n");
        return NULL;
    } 
    
    if (0 == uNumBytes)   return NULL;  // nothing to alloc
    if (0 == pPMRoot->uTotalUnits)// uninitialized
    {
        PFATAL("Tried to allocate before heap is initialized !\n");
        return NULL;
    }

    // check for justification condition
    if(uJustify > __PM_ALLOC_UNIT)
    {
        UINT n=0, j=0, b=1;
        while(b)
        {
            if(uJustify & b) { n = b; j++; }
            b <<= 1;
        }
        if(j > 1 ) 
        {
            if(n<<1) 
            {
                PDEBUG("Justification condition modified from 0x%8.8x to 0x%8.8x\n", uJustify, n<<1);
                uJustify = n<<1;
            }
            else
            {
                PDEBUG("Justification condition %8.8x can not be satisfied!\n", uJustify);
                return NULL;
            }
        }
    }
    else
    {
        uJustify = 0; // since it's less than our basic justification bound
    }

    uJustifyUnits = uJustify / __PM_ALLOC_UNIT; // and now the justification in units

    if(uJustifyUnits)   // also add the base adjust
        uJustifyAdjust = (pPMRoot->uPhysicalAddress/__PM_ALLOC_UNIT) %  uJustifyUnits;
    else
        uJustifyAdjust = 0;

    // calculate the required units
    uReqUnits = (uNumBytes + __PM_ALLOC_UNIT - 1) / __PM_ALLOC_UNIT;


    PDEBUG(" Try to allocate %d bytes\n", uNumBytes);
    //########################################################################
    PML_ENTER();

    if (os_get_pool_status(&pPMRoot->handlePool) <= 0) goto __pm_alloc_just_out; // out of handle

    if (uReqUnits > pPMRoot->uFreeUnits) {
        printk("pm_alloc_physical_justify: not enough free memory available\n");
        goto __pm_alloc_just_out;    // out of memory
    }
    if (pPMRoot->npFreeList < 0) // something wrong with the free list, this should never happen
    {
        // there ares still
        PFATAL("Allocation heap corrupted !\n");
        goto __pm_alloc_just_out;
    }

    PDEBUG(" Lookup heap\n");
    // search for the best fit
    npBestFitBlock = -1; uBestFitUnits = 0;
    {
        INT npCurr;
        PM_ALLOC_FREE_NODE_T *pCurrBlock;

        // the first free
        npCurr = pPMRoot->npFreeList;
        while(npCurr >= 0) 
        {
            pCurrBlock = __PM_GET_BLOCK_POINTER(npCurr);
            if (pCurrBlock->uUnits >= uReqUnits)  // this one possiblly fits
            {

                if(uJustifyUnits) // check if justification is required
                {
                    // the number of units skipped for justification requirements
                    UINT uAdjust = uJustifyUnits - ((UINT)pCurrBlock->npAddr+uJustifyAdjust)%uJustifyUnits;
                    if(pCurrBlock->uUnits < uReqUnits + uAdjust) // justify condition not fit
                    {
                        if(pCurrBlock->npNext < 0) break;
                        if(npCurr >= pCurrBlock->npNext)
                        {
                            PFATAL("Allocation heap corrupted !\n");
                            goto __pm_alloc_just_out;
                        }
                        npCurr = pCurrBlock->npNext;    // look for next
                        continue;
                    }
                }
                // ok justification is fine
#ifdef __PM_ALLOC_OPTIMIZED_UTILIZATION__  // try to find best match block
                if (npBestFitBlock < 0 || uBestFitUnits > pCurrBlock->uUnits)
                {
                    npBestFitBlock = npCurr;
                    uBestFitUnits = pCurrBlock->uUnits;
                    if (uBestFitUnits == uReqUnits) // yeah, here we go
                        break;
                }
#else    // just use the first fit
                npBestFitBlock = npCurr;
                uBestFitUnits = pCurrBlock->uUnits;
                break;
#endif
            }
            if(pCurrBlock->npNext < 0) break;   // end of heap
            if(npCurr >= pCurrBlock->npNext)    // check for heap corrupt
            {
                PFATAL("Allocation heap corrupted !\n");
                goto __pm_alloc_just_out;
            }
            npCurr = pCurrBlock->npNext;    // look for next
        }
    }
    if (npBestFitBlock < 0) // :-(, Are you too greedy? I could not find such a big block due to mem fragmentation
    {
        goto __pm_alloc_just_out;