source: svn/trunk/newcon3bcm2_21bu/magnum/basemodules/mem/bmem_system.c

/***************************************************************************
 *     Copyright (c) 2002-2012, Broadcom Corporation
 *     All Rights Reserved
 *     Confidential Property of Broadcom Corporation
 *
 *  THIS SOFTWARE MAY ONLY BE USED SUBJECT TO AN EXECUTED SOFTWARE LICENSE
 *  AGREEMENT  BETWEEN THE USER AND BROADCOM.  YOU HAVE NO RIGHT TO USE OR
 *  EXPLOIT THIS MATERIAL EXCEPT SUBJECT TO THE TERMS OF SUCH AN AGREEMENT.
 *
 * $brcm_Workfile: bmem_system.c $
 * $brcm_Revision: Hydra_Software_Devel/33 $
 * $brcm_Date: 2/7/12 6:37p $
 *
 * Module Description:
 *
 * This module provides the basic functions used to implement a memory
 * manager which stores bookkeeping information in OS-allocated memory. This
 * is advantageous when the memory being managed has significant access time
 * penalties. If accessing the managed memory has no access time penalties,
 * do NOT use this module; it is algorithmically slower than direct access
 * because of the additional overhead needed.
 *
 * All of the bookeeping information close to the CPU, in "system memory".
 * To do this, there needs to be some way of associating managed memory
 * block with info about the managed memory block. In the local allocator,
 * this is done by physically locating the BlockInfo in front of the managed
 * block. This same approach can't be used if the BlockInfo lives in system
 * memory.
 *
 * Instead, a hash table is used to index the BlockInfo structures. The
 * has index is based upon the lowest significant bits of the managed memory
 * address of the block. A linked list is used in each hash bucket to handle
 * collisions. The nodes in thist list are not ordered in any way.
 *
 * When looking up a BlockInfo for a manged memory address, the address is
 * shifted and masked to give the hash key. The list of nodes at that hash
 * key is iterated over until a match is found. If we find that the lists
 * grow to an unreasonable length, then the number of hash buckets can be
 * increased. This is not done dynamically.
 *
 * Revision History:
 *
 * $brcm_Log: /magnum/basemodules/mem/bmem_system.c $
 * 
 * Hydra_Software_Devel/33   2/7/12 6:37p albertl
 * SW7425-2345: Changed total allocation and number of allocation tracking
 * to work in eFastest.
 * 
 * Hydra_Software_Devel/32   11/14/11 2:22p albertl
 * SW7425-1293: Fixed use of uncached address when cached addresses exist
 * during heap creation.  Fixed coverity issues.
 * 
 * Hydra_Software_Devel/31   9/9/11 7:10p albertl
 * SW7346-201: Moved watermark calculation to alloc and free for accurate
 * calculation.
 * 
 * Hydra_Software_Devel/30   9/7/11 2:05p albertl
 * SW7408-258: Fixed memory leak.
 * 
 * Hydra_Software_Devel/29   3/29/11 4:16p albertl
 * SW7425-247: Changed BDBG_OBJECT_DESTROY to BDBG_OBJECT_UNSET.
 * 
 * Hydra_Software_Devel/28   3/28/11 5:13p albertl
 * SW7425-247: Incorporated BDBG_OBJECT handle validation.
 * 
 * Hydra_Software_Devel/27   1/10/11 3:32p albertl
 * SW7408-193: BMEM_Heapinfo now includes high watermark.  Added
 * BMEM_Heap_ResetHighWatermark().
 * 
 * Hydra_Software_Devel/26   11/8/10 4:48p albertl
 * SW7420-1155: Fixed size calculation to match fixed implementation of
 * pEnd.
 * 
 * Hydra_Software_Devel/25   11/4/10 7:40p albertl
 * SW7420-1155: Fixed pEnd to really be last available byte and addrEnd to
 * be last byte in chunk rather than byte after that.
 * 
 * Hydra_Software_Devel/24   5/26/09 5:57p albertl
 * PR55389: Fixed mangled file.
 * 
 * Hydra_Software_Devel/23   5/26/09 5:52p albertl
 * PR55389: Replaced uintptr_t with uint32_t.
 * 
 * Hydra_Software_Devel/22   5/12/08 4:21p erickson
 * PR42628: free all mem in BMEM_P_SystemDestroyHeap
 *
 * Hydra_Software_Devel/21   7/12/07 6:26p albertl
 * PR31066:  Updated warning message to give platform and user specified
 * uiAlignment size.
 *
 * Hydra_Software_Devel/20   7/6/07 6:54p albertl
 * PR31066:  Changed BMEM_HEAP_ALIGNMENT to 6 for 7400 B0 and later and
 * 7405.  Added warnings when user specified alignment is less than and
 * forced to BMEM_HEAP_ALIGNMENT.
 *
 * Hydra_Software_Devel/19   3/15/07 7:24p albertl
 * PR28682:  Changed BMEM_GUARD_SIZE_BYTES to be dynamically calculated
 * based on runtime safety config.
 *
 * Hydra_Software_Devel/18   6/21/06 3:12p albertl
 * PR20247:  Moved safety config table to bmem.c  BMEM_P_Heap now uses a
 * BMEM_P_SafetyConfigInfo pointer to track safety configuration settings
 * instead of tracking each configuration separately.
 *
 * Hydra_Software_Devel/17   6/16/06 3:23p albertl
 * PR20247, PR20276, PR20354:  Added the ability to control debug
 * configuration at runtime.  Added address and offset checking to
 * conversion functions.  BMEM_SetCache can now only be called before
 * heaps are allocated from.  Added BMEM_Heap functions.
 *
 * Hydra_Software_Devel/16   10/7/05 3:53p jasonh
 * PR 17374: Allowed GetHeapInfo to return original creation parameters.
 *
 * Hydra_Software_Devel/15   3/17/05 6:12p pntruong
 * PR14494: Add preliminary software support to 3560 A0, remove linux
 * build warings.
 *
 * Hydra_Software_Devel/14   3/10/05 5:05p albertl
 * PR13677:  Both local and system bookkeeping made available at heap
 * creation though functions BMEM_CreateHeapSystem and
 * BMEM_CreateHeapLocal.
 *
 * Hydra_Software_Devel/13   3/2/05 3:50p jasonh
 * PR 14322: Fixing debug message argument.
 *
 * Hydra_Software_Devel/12   1/31/05 9:54a erickson
 * PR13097: if there's a leak, dump the heap (requires msg level)
 *
 * Hydra_Software_Devel/11   1/21/05 4:23p albertl
 * PR13717:  Replaced BMEM_DBG_ENTER with BDBG_ENTER.  Moved printouts to
 * DBG_MSG, fixed pvHeap.
 *
 * Hydra_Software_Devel/10   11/2/04 5:27p pntruong
 * PR13076: Initialized new members added.
 *
 * Hydra_Software_Devel/9   4/30/04 3:32p hongtaoz
 * PR8761: fixed C++ compile error.
 *
 * Hydra_Software_Devel/8   4/1/04 12:49p vsilyaev
 * PR 10201: Added memory monitor
 *
 * Hydra_Software_Devel/7   12/31/03 12:02p jasonh
 * PR 8940: Changed return type of destroyheap to void. Removed use of
 * DEBUG macro and printf.
 *
 * Hydra_Software_Devel/6   9/15/03 5:24p jasonh
 * Fixed create heap to store offset and address. Fixed return codes.
 * Added system specific destroy heap.
 *
 * Hydra_Software_Devel/5   9/5/03 5:48p hongtaoz
 * fixed compile errors.
 *
 * Hydra_Software_Devel/4   9/5/03 1:39p jasonh
 * Wrapped unused arguments with BSTD_UNUSED
 *
 * Hydra_Software_Devel/3   9/2/03 1:48p vadim
 * Some magnum updates.
 *
 * Hydra_Software_Devel/1   3/20/03 3:24p erickson
 * initial bmem work, taken from SetTop/memorylib
 *
 * SanJose_DVTSW_Devel/5   8/12/02 10:26a poz
 * Changed to kernel interface abstractions for malloc and free.
 *
 * SanJose_DVTSW_Devel\4   4/15/02 6:22p zinc
 * Fixed missed rename of HeapCheck.
 *
 * SanJose_DVTSW_Devel\3   4/15/02 3:34p poz
 * Updated function name to bcmHeapCreate.
 *
 * SanJose_DVTSW_Devel\2   4/15/02 2:30p poz
 * Modified to get semaphore when MEM_REENTRANT.
 *
 * SanJose_DVTSW_Devel\1   4/15/02 1:36p poz
 * Implementation of system-memory heap manager.
 *
 ***************************************************************************/

#include "bstd.h"
#include "bmem.h"
#include "bmem_config.h"
#include "bmem_priv.h"
#include "bmem_debug.h"
#include "bkni.h"

BDBG_MODULE(BMEM);

/* The number of hash buckets to be used to store BlockInfo blocks */
#define BMEM_SYS_NUM_BUCKETS 256 /* must be a power of two */

/* Calculates the hash key given a managed memory address */
#define BUCKET_IDX(addr) (((addr) >> pshi->uiAlignment) & (BMEM_SYS_NUM_BUCKETS-1))


/***************************************************************************
 * BMEM_P_BINode - Stores managed block info for the system heap manger.
 *
 * Contains information about the managed block (the BlockInfo) as well as
 * members traversing the system-memory data structures.
 *
 */
typedef struct BMEM_P_BINode BMEM_P_BINode;
struct BMEM_P_BINode
{
        BMEM_P_BlockInfo pbi;   /* Managed block info. */
                               /* Must be the first entry in this struct! */

        uint32_t addr;         /* Managed memory block base address */
        BMEM_P_BINode *pbiNext; /* Pointer to next node in the hash bucket */
        BMEM_P_BINode *pbiPrev; /* Pointer to previous node in the hash bucket */
};

/***************************************************************************
 * BMEM_P_SystemHeapInfo - Stores heap-wide info for the system heap manager.
 *
 * Heap-wide information specific to the System heap manager.
 *
 */
typedef struct BMEM_P_SystemHeapInfo
{
        unsigned int uiAlignment;
        BMEM_P_BINode *anodes[BMEM_SYS_NUM_BUCKETS];
} BMEM_P_SystemHeapInfo;

/**********************************************************************func*
 * BMEM_P_SystemGetAddress - Get the managed memory base address for a
 *                           block.
 *
 * Returns:
 *    0 if a NULL BlockInfo is given, otherwise the base address.
 */

uint32_t BMEM_P_SystemGetAddress
(
        BMEM_Handle pheap,
        BMEM_P_BlockInfo *pbi
)
{
        BSTD_UNUSED( pheap );

        if( pbi == NULL )
        {
                return 0;
        }

        /* We'll take advantage of BINode having the BlockInfo right at the
         * front and just magically cast it.
         */
        return ((BMEM_P_BINode *) pbi)->addr;
}

/**********************************************************************func*
 * BMEM_P_SystemGetBlockInfo - Get the bookkeeping info for a managed base
 *                             address.
 *
 * This function finds the bookeeping information for a given base address.
 * If the given base address has no bookkeeping information assigned to it,
 * a new BlockInfo is allocated from the system heap and added to the hash.
 * The new BlockInfo is then returned.
 *
 * Returns:
 *    On success, a pointer to the BlockInfo for the managed base address.
 *    On failure (which can occur if the system heap is full), NULL.
 *
 */

BMEM_P_BlockInfo *BMEM_P_SystemGetBlockInfo
(
        BMEM_Handle pheap,
        uint32_t addr
)
{
        BMEM_P_SystemHeapInfo *pshi = (BMEM_P_SystemHeapInfo *)(pheap->pvData);
        int idx = BUCKET_IDX(addr);

        BMEM_P_BINode *pbinode = pshi->anodes[idx];

        while(pbinode!=NULL && pbinode->addr!=addr)
        {
                pbinode = pbinode->pbiNext;
        }

        if(pbinode == NULL)
        {
                /* No entry found. Make a new one */
                pbinode = (BMEM_P_BINode *)BKNI_Malloc(sizeof(BMEM_P_BINode));
                if(pbinode == NULL)
                {
                        BDBG_ERR(("Out of system memory. Can't allocate bookkeeping!"));
                        return NULL;
                }
                pbinode->addr = addr;
                pbinode->pbiNext = pshi->anodes[idx];
                pbinode->pbiPrev = NULL;
                pshi->anodes[idx] = pbinode;

                if(pbinode->pbiNext!=NULL)
                {
                        pbinode->pbiNext->pbiPrev = pbinode;
                }
        }

        /* We'll take advantage of BINode having the BlockInfo right at the
         * front and just magically cast it.
         */
        return (BMEM_P_BlockInfo *)pbinode;
}

/**********************************************************************func*
 * BMEM_P_SystemDropBlockInfo -
 *    Free up the bookkeeping info for a managed memory base address
 *
 * Returns:
 *    void
 */

void BMEM_P_SystemDropBlockInfo
(
        BMEM_Handle pheap,
        BMEM_P_BlockInfo *pbi
)
{
        BMEM_P_SystemHeapInfo *pshi = (BMEM_P_SystemHeapInfo *)pheap->pvData;
        /* We'll take advantage of BINode having the BlockInfo right at the
         * front and just magically cast it.
         */
        BMEM_P_BINode *pbinode = (BMEM_P_BINode *) pbi;
        int idx = BUCKET_IDX(pbinode->addr);

        /* Remove the BINode from the list in the hash table. */
        if(pbinode->pbiPrev != NULL)
        {
                pbinode->pbiPrev->pbiNext = pbinode->pbiNext;
        }
        if(pbinode->pbiNext != NULL)
        {
                pbinode->pbiNext->pbiPrev = pbinode->pbiPrev;
        }

        if(pshi->anodes[idx] == pbinode)
        {
                pshi->anodes[idx] = pbinode->pbiNext;
        }

        BKNI_Free(pbinode);
}

/**********************************************************************func*
 * bcmHeapCreate - Initializes the heap with local bookkeeping.
 *
 * This function inititalizes a heap at a given location and size.
 * Any previous allocations in the chunk of memory handed over to this
 * function are lost. Every heap has a base minimum alignment for all of
 * the allocations within that heap. (However, you can specify a greater
 * alignment when actually doing an allocation.)
 *
 * In this implementation, memory in the CPU's system heap is used to store
 * the bookkeeping information for the heap.
 *
 * Returns:
 *   Returns true if heap is initialized, or false if the size of the heap
 *   is too small to manage or there isn't enough system memory to allocate
 *   bookkeeping information.
 *
 */
BERR_Code BMEM_CreateHeapSystem
(
        BMEM_Handle  *ppHeap,      /* Address to store pointer of new heap info structure */
        void         *pvHeap,      /* Pointer to beginning of memory chunk to manage */
        uint32_t      ulOffset,    /* Device offset of initial location */
        size_t        zSize,       /* Size of chunk to manage in bytes */
        unsigned int  uiAlignment  /* Minimum alignment for all allocations in the heap */
)
{
        BMEM_Heap_Settings stHeapSettings;
        BMEM_Heap_Settings *pHeapSettings = &stHeapSettings;

        BMEM_Heap_GetDefaultSettings(pHeapSettings);

        pHeapSettings->uiAlignment = uiAlignment;
        pHeapSettings->eBookKeeping = BMEM_BOOKKEEPING_SYSTEM;

        return BMEM_Heap_Create(NULL, pvHeap, ulOffset, zSize, pHeapSettings, ppHeap);
}

BERR_Code BMEM_P_SystemCreateHeap
(
        BMEM_Handle        *ppHeap,      /* Address to store pointer of new heap info structure */
        void               *pvHeap,      /* Pointer to beginning of memory chunk to manage */
        uint32_t            ulOffset,    /* Device offset of initial location */
        size_t              zSize,       /* Size of chunk to manage in bytes */
        BMEM_Heap_Settings *pHeapSettings
)
{
        BERR_Code              err = BERR_SUCCESS;
        BMEM_P_SystemHeapInfo *pshi;
        BMEM_P_BlockInfo      *pbi;
        BMEM_P_Heap           *pheap;
        uint32_t               addrHeap = (uint32_t)pvHeap;
        uint32_t               addrEnd = (uint32_t)pvHeap + zSize - 1;
        int                    i;
        unsigned int           uiAlignment = pHeapSettings->uiAlignment;
        size_t                 ulAlignedSize;
        uint32_t               eSafetyConfig = pHeapSettings->eSafetyConfig;

        BDBG_ENTER(BMEM_P_SystemCreateHeap);
        BDBG_MSG(("BMEM_P_SystemCreateHeap(%p, %p, %lu, %d)",
                ppHeap, pvHeap, zSize, (int)uiAlignment));

        if (pHeapSettings->eSafetyConfig > BMEM_P_SafetyTableSize)
        {
                /* Invalid safety config. */
                err = BERR_TRACE(BERR_INVALID_PARAMETER);
                goto done;
        }

        if (pHeapSettings->eSafetyConfig > BMEM_SAFETY_CONFIG)
        {
                /* Invalid run-time safety config. */
                        BDBG_ERR(("Run-time safety config cannot be higher than compiled safety config!"));
                        err = BERR_TRACE(BERR_INVALID_PARAMETER);
                goto done;
        }

        /* allocate heap structure */
        *ppHeap = (BMEM_P_Heap*) BKNI_Malloc( sizeof (BMEM_P_Heap) );
        if( *ppHeap == NULL )
        {
                err = BERR_TRACE(BERR_OUT_OF_SYSTEM_MEMORY);
                BDBG_ERR(( "Out of system memory. Can't allocate bookkeeping!" ));
                goto done;
        }

        /* initialize heap structure */
        pheap = (BMEM_P_Heap *) *ppHeap;
        BDBG_OBJECT_SET(pheap, BMEM_Heap);
        pheap->pFreeTop = NULL;
        pheap->pAllocTop = NULL;
        pheap->ulAlignMask = 0;
        pheap->pStart = NULL;
        pheap->pEnd = NULL;
        pheap->ulNumErrors = 0;
        pheap->pvData = NULL;
        pheap->pvHeap = pvHeap;
        pheap->ulOffset = ulOffset;
        pheap->monitor = NULL;
        pheap->pvCache = pHeapSettings->pCachedAddress;
        pheap->pfFlushCb = pHeapSettings->flush;
        pheap->pfFlushCb_isr = pHeapSettings->flush_isr;
        pheap->zSize = zSize;
        pheap->ulNumAllocated = 0;
        pheap->ulTotalAllocated = 0;
        pheap->ulHighWatermark = 0;

        pheap->pSafetyConfigInfo = &(BMEM_P_SafetyConfigTbl[eSafetyConfig]);
        pheap->ulGuardSizeBytes  = pheap->pSafetyConfigInfo->iGuardSize * BMEM_GUARD_UNIT_BYTES;

        pheap->eBookKeeping = pHeapSettings->eBookKeeping;
        pheap->bCacheLocked = false;

        pheap->pGetAddressFunc = &BMEM_P_SystemGetAddress;
        pheap->pGetBlockInfoFunc = &BMEM_P_SystemGetBlockInfo;
        pheap->pDropBlockInfoFunc = &BMEM_P_SystemDropBlockInfo;
        pheap->pDestroyHeapFunc = &BMEM_P_SystemDestroyHeap;

#if (BMEM_REENTRANT_CONFIG==BMEM_REENTRANT)
        /* create mutex for re-entrant control */
        err = BERR_TRACE(BKNI_CreateMutex(&(pheap->pMutex)));
        if (err != BERR_SUCCESS)
        {
                goto done;
        }
#endif


        /* Force at least the minimum heap alignment */
        if(uiAlignment < BMEM_HEAP_ALIGNMENT)
        {
                BDBG_WRN(("uiAlignment %d less than platform minimum %d.  Setting alignment to minimum.", uiAlignment, BMEM_HEAP_ALIGNMENT));
                uiAlignment = BMEM_HEAP_ALIGNMENT;
        }
        pheap->uiAlignment = uiAlignment;
        pheap->ulAlignMask = (1L << uiAlignment) - 1;

        /* Align the heap to be on the requested alignment. */
        pheap->pStart = (uint8_t *)((addrHeap+pheap->ulAlignMask) & ~pheap->ulAlignMask);
        /* Last usable byte after alignment. */
        pheap->pEnd = (uint8_t *)(((addrEnd + 1) & ~pheap->ulAlignMask) - 1);

        /* Allocate the hash buckets for storing the BlockInfos */
        pheap->pvData = BKNI_Malloc(sizeof(BMEM_P_SystemHeapInfo));
        if(pheap->pvData == NULL)
        {
                /* unable to allocate */
                err = BERR_OUT_OF_SYSTEM_MEMORY;
                BDBG_ERR(("Out of system memory. Can't allocate hash table!"));
                goto done;
        }
        pshi = (BMEM_P_SystemHeapInfo *)pheap->pvData;

        /* initialize table */
        for(i = 0; i<BMEM_SYS_NUM_BUCKETS; ++i)
        {
                pshi->anodes[i] = NULL;
        }
        pshi->uiAlignment = uiAlignment;

        /*
         * Starting here, it's safe to make calls to the other heap management
         * functions.
         */

        /* Make the first block, which represents the remaining (free) heap */
        pbi = BMEM_P_SystemGetBlockInfo(pheap, (uint32_t)pheap->pStart);
        
        ulAlignedSize = pheap->pEnd-pheap->pStart+1;

        /* heap size greater than bookkeeping? */
        if(ulAlignedSize > BMEM_BOOKKEEPING_SIZE_SYSTEM)
        {
                /* Create a free block representing the entire heap. */
                pbi->ulSize = ulAlignedSize;
                pbi->ulFrontScrap = 0;
                pbi->ulBackScrap = 0;
                pbi->pnext = NULL;
                BMEM_P_FillGuard(pheap, pbi);

                pheap->pFreeTop = pbi;

        /* memory isn't even large enough for bookkeeping */
        } else
        {
                /* cannot create heap from this memory */
                pheap->pFreeTop = NULL;
                err = BERR_INVALID_PARAMETER;
        }

#if BMEM_CHECK_ALL_GUARDS
        if (pheap->pSafetyConfigInfo->bCheckAllGuards)
        {
                /* heap has been created? */
                if (err == BERR_SUCCESS)
                {
                        /* validate heap */
                        err = BMEM_ValidateHeap(pheap);
                }
        }
#endif

done:
        /* free heap if error occured */
        if ((err != BERR_SUCCESS) && *ppHeap!=NULL)
        {
                /* destroy heap */
                BMEM_DestroyHeap(*ppHeap);
                *ppHeap = NULL;
        }

        /* return status */
        BDBG_MSG(("BMEM_P_SystemCreateHeap = %ul", err));
        BDBG_LEAVE(BMEM_P_SystemCreateHeap);
        return err;
}

/***************************************************************************/
void BMEM_P_SystemDestroyHeap
(
        BMEM_Handle pheap
)
{
#if BMEM_CHECK_ALL_GUARDS
        BERR_Code err;
#endif
        BMEM_P_SystemHeapInfo *pshi;
        unsigned i;

        BDBG_OBJECT_ASSERT(pheap, BMEM_Heap);

#if BMEM_CHECK_ALL_GUARDS
        if (pheap->pSafetyConfigInfo->bCheckAllGuards)
        {
                /* validate heap */
                err = BERR_TRACE(BMEM_ValidateHeap(pheap));
                if (err != BERR_SUCCESS)
                {
                        /* error validating heap */
                        goto done;
                }
        }
#endif

        /* blocks still allocated? */
        if (pheap->pAllocTop)
        {
                /* leaked resource */
                BDBG_ERR(("Leaked resource -- unfreed blocks detected"));
                BMEM_Dbg_DumpHeap(pheap);
        }

        /* free system hash table (should be empty since there
           are no outstanding allocations) */
        pshi = (BMEM_P_SystemHeapInfo *)(pheap->pvData);
        for (i=0;i<BMEM_SYS_NUM_BUCKETS;i++) {
                BMEM_P_BINode *pbi = pshi->anodes[i];
                BMEM_P_BINode *pbiNext;
                while(pbi) {
                        pbiNext = pbi->pbiNext;
                        BKNI_Free(pbi);
                        pbi = pbiNext;
                }
        }

        BKNI_Free(pheap->pvData);

#if (BMEM_REENTRANT_CONFIG==BMEM_REENTRANT)
        /* destroy mutex */
        BKNI_DestroyMutex(pheap->pMutex);
#endif

        /* free heap handle */
        BDBG_OBJECT_UNSET(pheap, BMEM_Heap);
        BKNI_Free(pheap);

done:
        /* return */
        return;
}

/* End of File */