sbheap.c

C标准库源代码

/***
*sbheap.c -  Small-block heap code
*
*       Copyright (c) 1996-1998, Microsoft Corporation. All rights reserved.
*
*Purpose:
*       Core code for small-block heap.
*
*******************************************************************************/

#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <winheap.h>
#include <windows.h>

size_t       __sbh_threshold = MAX_ALLOC_DATA_SIZE;

PHEADER      __sbh_pHeaderList;        //  pointer to list start
PHEADER      __sbh_pHeaderScan;        //  pointer to list rover
int          __sbh_sizeHeaderList;     //  allocated size of list
int          __sbh_cntHeaderList;      //  count of entries defined

PHEADER      __sbh_pHeaderDefer;
int          __sbh_indGroupDefer;

/*
 * Prototypes for user functions.
 */
size_t __cdecl _get_sbh_threshold(void);
int    __cdecl _set_sbh_threshold(size_t);

void DumpEntry(char *, int *);

/***
*size_t _get_sbh_threshold() - return small-block threshold
*
*Purpose:
*       Return the current value of __sbh_threshold
*
*Entry:
*       None.
*
*Exit:
*       See above.
*
*Exceptions:
*
*******************************************************************************/

size_t __cdecl _get_sbh_threshold (void)
{
    return __sbh_threshold;
}

/***
*int _set_sbh_threshold(threshold) - set small-block heap threshold
*
*Purpose:
*       Set the upper limit for the size of an allocation which will be
*       supported from the small-block heap.
*
*Entry:
*       size_t threshold - proposed new value for __sbh_theshold
*
*Exit:
*       Returns 1 if successful. Returns 0 if threshold was too big.
*
*Exceptions:
*
*******************************************************************************/

int __cdecl _set_sbh_threshold (size_t threshold)
{
    //  test against maximum value - if too large, return error
    if (threshold > MAX_ALLOC_DATA_SIZE)
        return 0;

    //  set the threshold value
    __sbh_threshold = threshold;
    return 1;
}

/***
*int __sbh_heap_init() - set small-block heap threshold
*
*Purpose:
*       Allocate space for initial header list and init variables.
*
*Entry:
*       None.
*
*Exit:
*       Returns 1 if successful. Returns 0 if initialization failed.
*
*Exceptions:
*
*******************************************************************************/

int __cdecl __sbh_heap_init (void)
{
    if (!(__sbh_pHeaderList = HeapAlloc(_crtheap, 0, 16 * sizeof(HEADER))))
        return FALSE;

    __sbh_pHeaderScan = __sbh_pHeaderList;
    __sbh_pHeaderDefer = NULL;
    __sbh_cntHeaderList = 0;
    __sbh_sizeHeaderList = 16;

    return TRUE;
}

/***
*PHEADER *__sbh_find_block(pvAlloc) - find block in small-block heap
*
*Purpose:
*       Determine if the specified allocation block lies in the small-block
*       heap and, if so, return the header to be used for the block.
*
*Entry:
*       void * pvBlock - pointer to block to be freed
*
*Exit:
*       If successful, a pointer to the header to use is returned.
*       If unsuccessful, NULL is returned.
*
*Exceptions:
*
*******************************************************************************/

PHEADER __cdecl __sbh_find_block (void * pvAlloc)
{
    PHEADER         pHeaderLast = __sbh_pHeaderList + __sbh_cntHeaderList;
    PHEADER         pHeader;
    unsigned int    offRegion;

    //  scan through the header list to determine if entry
    //  is in the region heap data reserved address space
    pHeader = __sbh_pHeaderList;
    while (pHeader < pHeaderLast)
    {
        offRegion = (unsigned int)pvAlloc - (unsigned int)pHeader->pHeapData;
        if (offRegion < BYTES_PER_REGION)
            return pHeader;
        pHeader++;
    }
    return NULL;
}

#ifdef _DEBUG

/***
*int __sbh_verify_block(pHeader, pvAlloc) - verify pointer in sbh
*
*Purpose:
*       Test if pointer is valid within the heap header given.
*
*Entry:
*       pHeader - pointer to HEADER where entry should be
*       pvAlloc - pointer to test validity of
*
*Exit:
*       Returns 1 if pointer is valid, else 0.
*
*Exceptions:
*
*******************************************************************************/

int __cdecl __sbh_verify_block (PHEADER pHeader, void * pvAlloc)
{
    unsigned int    indGroup;
    unsigned int    offRegion;

    //  calculate region offset to determine the group index
    offRegion = (unsigned int)pvAlloc - (unsigned int)pHeader->pHeapData;
    indGroup = offRegion / BYTES_PER_GROUP;

    //  return TRUE if:
    //      group is committed (bit in vector cleared) AND
    //      pointer is at paragraph boundary AND
    //      pointer is not at start of page
    return (!(pHeader->bitvCommit & (0x80000000UL >> indGroup))) &&
           (!(offRegion & 0xf)) &&
           (offRegion & (BYTES_PER_PAGE - 1));
}

#endif  /* _DEBUG */

/***
*void __sbh_free_block(preg, ppage, pmap) - free block
*
*Purpose:
*       Free the specified block from the small-block heap.
*
*Entry:
*       pHeader - pointer to HEADER of region to free memory
*       pvAlloc - pointer to memory to free
*
*Exit:
*       No return value.
*
*Exceptions:
*
*******************************************************************************/

void __cdecl __sbh_free_block (PHEADER pHeader, void * pvAlloc)
{
    PREGION         pRegion;
    PGROUP          pGroup;
    PENTRY          pHead;
    PENTRY          pEntry;
    PENTRY          pNext;
    PENTRY          pPrev;
    void *          pHeapDecommit;
    int             sizeEntry;
    int             sizeNext;
    int             sizePrev;
    unsigned int    indGroup;
    unsigned int    indEntry;
    unsigned int    indNext;
    unsigned int    indPrev;
    unsigned int    offRegion;

    //  region is determined by the header
    pRegion = pHeader->pRegion;

    //  use the region offset to determine the group index
    offRegion = (unsigned int)pvAlloc - (unsigned int)pHeader->pHeapData;
    indGroup = offRegion / BYTES_PER_GROUP;
    pGroup = &pRegion->grpHeadList[indGroup];

    //  get size of entry - decrement value since entry is allocated
    pEntry = (PENTRY)((char *)pvAlloc - sizeof(int));
    sizeEntry = pEntry->sizeFront - 1;

    //  point to next entry to get its size
    pNext = (PENTRY)((char *)pEntry + sizeEntry);
    sizeNext = pNext->sizeFront;

    //  get size from end of previous entry
    sizePrev = ((PENTRYEND)((char *)pEntry - sizeof(int)))->sizeBack;

    //  test if next entry is free by an even size value

    if ((sizeNext & 1) == 0)
    {
        //  free next entry - disconnect and add its size to sizeEntry

        //  determine index of next entry
        indNext = (sizeNext >> 4) - 1;
        if (indNext > 63)
            indNext = 63;

        //  test entry is sole member of bucket (next == prev),
        if (pNext->pEntryNext == pNext->pEntryPrev)
        {
            //  clear bit in group vector, decrement region count
            //  if region count is now zero, clear bit in header
            //  entry vector
            if (indNext < 32)
            {
                pRegion->bitvGroupHi[indGroup] &= ~(0x80000000L >> indNext);
                if (--pRegion->cntRegionSize[indNext] == 0)
                    pHeader->bitvEntryHi &= ~(0x80000000L >> indNext);
            }
            else
            {
                pRegion->bitvGroupLo[indGroup] &=
                                            ~(0x80000000L >> (indNext - 32));
                if (--pRegion->cntRegionSize[indNext] == 0)
                    pHeader->bitvEntryLo &= ~(0x80000000L >> (indNext - 32));
            }
        }

        //  unlink entry from list
        pNext->pEntryPrev->pEntryNext = pNext->pEntryNext;
        pNext->pEntryNext->pEntryPrev = pNext->pEntryPrev;

        //  add next entry size to freed entry size
        sizeEntry += sizeNext;
    }

    //  compute index of free entry (plus next entry if it was free)
    indEntry = (sizeEntry >> 4) - 1;
    if (indEntry > 63)
        indEntry = 63;

    //  test if previous entry is free by an even size value
    if ((sizePrev & 1) == 0)
    {
        //  free previous entry - add size to sizeEntry and
        //  disconnect if index changes

        //  get pointer to previous entry
        pPrev = (PENTRY)((char *)pEntry - sizePrev);

        //  determine index of previous entry
        indPrev = (sizePrev >> 4) - 1;
        if (indPrev > 63)
            indPrev = 63;

        //  add previous entry size to sizeEntry and determine
        //  its new index
        sizeEntry += sizePrev;
        indEntry = (sizeEntry >> 4) - 1;
        if (indEntry > 63)
            indEntry = 63;

        //  if index changed due to coalesing, reconnect to new size
        if (indPrev != indEntry)
        {
            //  disconnect entry from indPrev
            //  test entry is sole member of bucket (next == prev),
            if (pPrev->pEntryNext == pPrev->pEntryPrev)
            {
                //  clear bit in group vector, decrement region count
                //  if region count is now zero, clear bit in header
                //  entry vector
                if (indPrev < 32)
                {
                    pRegion->bitvGroupHi[indGroup] &=
                                                ~(0x80000000L >> indPrev);
                    if (--pRegion->cntRegionSize[indPrev] == 0)
                        pHeader->bitvEntryHi &= ~(0x80000000L >> indPrev);
                }
                else
                {
                    pRegion->bitvGroupLo[indGroup] &=
                                            ~(0x80000000L >> (indPrev - 32));
                    if (--pRegion->cntRegionSize[indPrev] == 0)
                        pHeader->bitvEntryLo &=
                                            ~(0x80000000L >> (indPrev - 32));
                }
            }

            //  unlink entry from list
            pPrev->pEntryPrev->pEntryNext = pPrev->pEntryNext;
            pPrev->pEntryNext->pEntryPrev = pPrev->pEntryPrev;
        }
        //  set pointer to connect it instead of the free entry
        pEntry = pPrev;
    }

    //  test if previous entry was free with an index change or allocated
    if (!((sizePrev & 1) == 0 && indPrev == indEntry))
    {
        //  connect pEntry entry to indEntry
        //  add entry to the start of the bucket list
        pHead = (PENTRY)((char *)&pGroup->listHead[indEntry] - sizeof(int));
        pEntry->pEntryNext = pHead->pEntryNext;
        pEntry->pEntryPrev = pHead;
        pHead->pEntryNext = pEntry;
        pEntry->pEntryNext->pEntryPrev = pEntry;

        //  test entry is sole member of bucket (next == prev),
        if (pEntry->pEntryNext == pEntry->pEntryPrev)
        {