heap.c

不错的东西 请查看 WINCE OS

    return VirtualAlloc (pAddr, cbSize, fdwAction, PAGE_READWRITE);
}

static BOOL FreeMem (LPVOID pAddr, DWORD cbSize, DWORD fdwAction, DWORD dwUnused)
{
    return VirtualFree (pAddr, cbSize, fdwAction);
}

BOOL InitNewHeap(pheap php, 
    DWORD flOptions,
    DWORD dwInitialSize,
    DWORD dwMaximumSize,
    DWORD cbRegion,
    PFN_AllocHeapMem pfnAlloc,
    PFN_FreeHeapMem pfnFree,
    DWORD dwRgnData)
{
    DWORD dwTemp;
    pitem pit;
#ifdef MEMTRACKING
    WCHAR Name[14];
#endif
    DEBUGCHK (pfnAlloc && pfnFree);

    if (!pfnAlloc (php, dwInitialSize, MEM_COMMIT, &dwRgnData))
        return FALSE;

    php->dwSig = HEAPSIG;
    php->flOptions = (WORD)flOptions;
    php->pfnAlloc = pfnAlloc;
    php->pfnFree = pfnFree;
    if (dwMaximumSize)
        php->cbMaximum = dwMaximumSize;

    InitializeCriticalSection(&php->cs);

    php->rgn.dwRgnData = dwRgnData;

    // Initialize first free item in the starting region.
    pit = FIRSTITEM(&php->rgn);
    php->rgn.pitFree = php->rgn.pitLast = pit;
    dwTemp = (dwInitialSize - SIZE_HEAP_HEAD - sizeof(item)) & ~(ALIGNBYTES-1);
    pit->size = -(int)dwTemp;
    pit->prgn = &php->rgn;
#if HEAP_SENTINELS
    memset (pit+1, 0xcc, dwTemp - sizeof(item));
    SetFreeSentinels(pit);
#endif
    DEBUGMSG(DBGFIXHP, (L"InitNewHeap: first item=%8.8lx size=%lx\r\n", pit, -pit->size));

    // Initialize the endmarker.
    pit = (pitem)((char*)pit + dwTemp);
    pit->size = 0;
    pit->cbTail = cbRegion - dwInitialSize;
#if HEAP_SENTINELS
    pit->dwSig = TAILSIG;
#endif
    DEBUGMSG(DBGFIXHP, (L"InitNewHeap: endmarker=%8.8lx size=%d extra=%lx\r\n", pit, pit->size, pit->cbTail));

    php->rgn.cbMaxFree = dwTemp;
    php->rgn.phpOwner = php;
    php->rgn.prgnLast = &php->rgn;      // point to ourself (first == last)
#ifdef MEMTRACKING
    AddTrackedItem(dwHeapMemType,php,NULL,GetCurrentProcessId(),sizeof(heap),0,0);
    swprintf(Name, L"Heap %08X", php);
    php->wMemType = (WORD)RegisterTrackedItem(Name);
#endif

    if ( !(flOptions & HEAP_IS_SHARED)) {
        // Add the new heap to the list of heaps for the current process.
        EnterCriticalSection(&csHeapList);
        php->phpNext = phpListAll;
        phpListAll = php;
        LeaveCriticalSection(&csHeapList);
    }
    return TRUE;
}


LPBYTE InitSharedHeap(LPBYTE pMem, DWORD size, DWORD reserve)
{
    pheap php;
    pitem pit;
    LPBYTE pbAlloc;

    php = (pheap)pMem;
    pit = FIRSTITEM(&php->rgn);
DEBUGMSG(1, (L"InitSharedHeap: %8.8lx %lx %lx\r\n", pMem, size, reserve));
    if (size) {
        InitNewHeap(php, HEAP_IS_SHARED, PAGE_SIZE, size, size, AllocMemVirt, FreeMem, 0);
        pbAlloc = HeapAlloc((HANDLE)php, 0, reserve);
        DEBUGCHK(pbAlloc == (LPBYTE)(pit+1));
    }
DEBUGMSG(1, (L"  InitSharedHeap: return %8.8lx\r\n", pit+1));
    return (LPBYTE)(pit+1);
}


/*
    @doc BOTH EXTERNAL

    @func HANDLE | HeapCreate    | Creates a new local heap
    @parm DWORD  | flOptions     | no flags supported
    @parm DWORD  | dwInitialSize | Initial committed heap size
    @parm DWORD  | dwMaximumSize | Maximum heap size
*/
HANDLE WINAPI HeapCreate(DWORD flOptions, DWORD dwInitialSize, DWORD dwMaximumSize)
{
    return ptrHeapCreate (flOptions, dwInitialSize, dwMaximumSize);
}

//
// DoHeapCreate: Worker function to create a heap, parameter already validated
//
static HANDLE DoHeapCreate(DWORD flOptions,
    DWORD dwInitialSize,
    DWORD dwMaximumSize,
    PFN_AllocHeapMem pfnAlloc,
    PFN_FreeHeapMem pfnFree)
{
    pheap php;
    DWORD cbRegion;
    DWORD dwRgnData = 0;

    // Compute size of initial memory region based upon the requested initial and maxiumum sizes.
    dwInitialSize = (dwInitialSize + PAGE_SIZE - 1) & -PAGE_SIZE;
    dwMaximumSize = (dwMaximumSize + PAGE_SIZE - 1) & -PAGE_SIZE;
    cbRegion = (dwMaximumSize == 0) ? CE_FIXED_HEAP_MAXSIZE : dwMaximumSize;
    if (dwInitialSize == 0)
        dwInitialSize = PAGE_SIZE;
    else if (dwInitialSize > cbRegion)
        dwInitialSize = cbRegion;

    // Reserve address space for the initial region and commit the initial # of pages.
    if (!(php = pfnAlloc (PSlot, cbRegion, MEM_RESERVE, &dwRgnData))
            || !InitNewHeap(php, flOptions, dwInitialSize, dwMaximumSize, cbRegion, pfnAlloc, pfnFree, dwRgnData)) {
        if (php)
            pfnFree (php, 0, MEM_RELEASE, dwRgnData);
        DEBUGMSG(DBGFIXHP, (L"   HeapCreate: Unable to allocate initial pages\r\n"));
        SetLastError(ERROR_NOT_ENOUGH_MEMORY);
        return NULL;
    }
    DEBUGMSG(DBGFIXHP, (L"   HeapCreate %8.8lx %8.8lx %8.8lx ==> %8.8lx\r\n", flOptions, dwInitialSize, dwMaximumSize, php));
    if (IsCeLogStatus(CELOGSTATUS_ENABLED_GENERAL)) {
        CELOG_HeapCreate(flOptions, dwInitialSize, dwMaximumSize, (HANDLE)php);
    }
    return (HANDLE)php;
}

HANDLE WINAPI Int_HeapCreate(DWORD flOptions, DWORD dwInitialSize, DWORD dwMaximumSize)
{
    DEBUGMSG(DBGFIXHP, (L"HeapCreate %8.8lx %8.8lx %8.8lx\r\n", flOptions, dwInitialSize, dwMaximumSize));
    if (flOptions & ~(HEAP_NO_SERIALIZE|HEAP_SHARED_READONLY)) {
        DEBUGMSG(DBGFIXHP, (L"   HeapCreate: Invalid parameter\r\n"));
        SetLastError(ERROR_INVALID_PARAMETER);
        return NULL;
    }
    return DoHeapCreate (flOptions, dwInitialSize, dwMaximumSize, (flOptions & HEAP_SHARED_READONLY)? AllocMemShare : AllocMemVirt, FreeMem);
}

//
// CeHeapCreate: Create a heap with custom allocator/deallocator
//
HANDLE WINAPI CeHeapCreate(DWORD flOptions,
    DWORD dwInitialSize,
    DWORD dwMaximumSize,
    PFN_AllocHeapMem pfnAlloc,
    PFN_FreeHeapMem pfnFree)
{
    DEBUGMSG(DBGFIXHP, (L"CeHeapCreate %8.8lx %8.8lx %8.8lx %8.8lx %.8lx\r\n", flOptions, dwInitialSize, dwMaximumSize, pfnAlloc, pfnFree));
    if (flOptions || !pfnAlloc || !pfnFree) {
        DEBUGMSG(DBGFIXHP, (L"   CeHeapCreate: Invalid parameter\r\n"));
        SetLastError(ERROR_INVALID_PARAMETER);
        return NULL;
    }
    return DoHeapCreate (flOptions, dwInitialSize, dwMaximumSize, pfnAlloc, pfnFree);
}

/** Create a new memory region for an existing heap.
 */
static pregion CreateNewRegion(LPVOID lpSlot, pheap php, int cbSeek)
{
    pregion prgn, prgnLast;
    pitem pit;
    DWORD dwRgnData = 0;

    DEBUGCHK(php->cbMaximum == 0 && php->pfnAlloc);
    cbSeek = (cbSeek + SIZE_REGION_HEAD + sizeof(item) + PAGE_SIZE-1) & -PAGE_SIZE;

    // Reserve address space for the region and commit the initial # of pages.
    if (!(prgn = php->pfnAlloc (lpSlot, CE_FIXED_HEAP_MAXSIZE, MEM_RESERVE, &dwRgnData))
            || !php->pfnAlloc (prgn, cbSeek, MEM_COMMIT, &dwRgnData)) {
        if (prgn)
            php->pfnFree (prgn, 0, MEM_RELEASE, dwRgnData);
        DEBUGMSG(DBGHEAP2, (L"   HeapAllocate: Unable to allocate new region\r\n"));
        SetLastError(ERROR_NOT_ENOUGH_MEMORY);
        return NULL;
    }

    // Initialize the first free item in the region.
    pit = FIRSTITEM(prgn);
    prgn->pitFree = prgn->pitLast = pit;
    prgn->prgnNext = 0;           // we'll be the last in the list
    prgn->dwRgnData = dwRgnData;
    pit->prgn = prgn;
    cbSeek -= SIZE_REGION_HEAD + sizeof(item);
    pit->size = -cbSeek;
#if HEAP_SENTINELS
    memset (pit+1, 0xcc, cbSeek - sizeof(item));
    SetFreeSentinels(pit);
#endif
    DEBUGMSG(DBGHEAP2, (L"CreateNewRegion: first item=%8.8lx size=%lx\r\n", pit, -pit->size));

    // Initizize the endmarker.
    pit = (pitem)((char*)pit + cbSeek);
    pit->size = 0;
    pit->cbTail = (CE_FIXED_HEAP_MAXSIZE - cbSeek) & -PAGE_SIZE;
#if HEAP_SENTINELS
    pit->dwSig = TAILSIG;
#endif
    DEBUGMSG(DBGHEAP2, (L"CreateNewRegion: endmarker=%8.8lx size=%d extra=%lx\r\n", pit, pit->size, pit->cbTail));

    // Initialize the region structure and link it into the heap's region list.
    prgn->cbMaxFree = cbSeek;
    prgn->phpOwner = php;

    prgnLast = php->rgn.prgnLast;
    php->rgn.prgnLast = prgnLast->prgnNext = prgn;

    return prgn;
}

/** Delete an extended memory region for a heap
 */
static void DeleteRegion(pregion prgnDel)
{
    pheap php = prgnDel->phpOwner;
    pregion prgn;

    DEBUGCHK(php->dwSig == HEAPSIG);
    prgn = &php->rgn;
    do {
        if (prgn->prgnNext == prgnDel) {
            DWORD dwRgnData = prgnDel->dwRgnData;
            prgn->prgnNext = prgnDel->prgnNext;
            php->pfnFree (prgnDel, CE_FIXED_HEAP_MAXSIZE, MEM_DECOMMIT, dwRgnData);
            php->pfnFree (prgnDel, 0, MEM_RELEASE, dwRgnData);
            return;
        }
    } while ((prgn = prgn->prgnNext) != NULL);
    DEBUGMSG(1, (L"DeleteRegion: 0x%08X not found in Heap 0x%08X\r\n", prgnDel, php));
    DEBUGCHK(0);
}

//
// MergeFreeItems: Merge all free blocks and return the next item (or self if already at end)
//
static pitem MergeFreeItems (pregion prgn, pitem pit)
{
    pitem pitTrav;
    int cbItem = -pit->size;
    DEBUGCHK (cbItem >= 0);

    if (cbItem <= 0)
        return pit;

    // combine all the contigious free blocks
    while ((pitTrav = (pitem)((char*)pit + cbItem))->size < 0) {
        cbItem -= pitTrav->size;
#if HEAP_SENTINELS
        // block merged, fill 0xcc for the merged item header debug
        memset (pitTrav, 0xcc, sizeof(item));
#endif
    }


    pit->size = -cbItem;

    if (!pitTrav->size) {
        prgn->pitLast = pit;
        fFullyCompacted = FALSE;
    }

#ifdef FREE_POINTER_AT_LAST_FREE
    prgn->pitFree = pit;
#else
    if (prgn->pitFree > pit)
        prgn->pitFree = pit;
#endif

#if HEAP_SENTINELS
    SetFreeSentinels(pit);
#endif

    return pitTrav;
}

//
// Carve a required size from an item and, possibly, create a leftover item
//
static pitem CarveItem (pregion prgn, pitem pit, int cbSeek, DWORD dwBytes, pitem pitcombine)
{
    int cbItem = -pit->size;
    pitem pitNext;
#if HEAP_SENTINELS == 0
    int cbEx;
#endif

    DEBUGCHK (cbItem >= 0);

    if (cbItem < cbSeek) {

        // this is the case that we need to commit more memory
        pitem pitEnd = (pitem) ((char *) pit + cbItem);
        int cbEx;

        DEBUGCHK ((pitEnd->size == 0) && ((((DWORD)pitEnd + sizeof(item)) & (PAGE_SIZE-1)) == 0));

        // calculate much many bytes, round up to pagesize, we need to commit
        // NOTE: we need extra room for an end marker
        cbEx  = (cbSeek - cbItem + sizeof(item) + PAGE_SIZE-1) & -PAGE_SIZE;

        // commit extra memory.
        if (!prgn->phpOwner->pfnAlloc ((char *)pitEnd + sizeof(item), cbEx, MEM_COMMIT, &prgn->dwRgnData)) {
            return NULL;    // out of memory
        }

        DEBUGMSG(DBGHEAP2, (L"CarveItem: Committed more memory pitEnd = %8.8lx cbSeek = %8.8lx, cbEx = %8.8lx\r\n", pitEnd, cbSeek, cbEx));

        // create a new end marker
        pitNext = (pitem)((char*)pitEnd + cbEx);
        pitNext->size = 0;
        pitNext->cbTail = pitEnd->cbTail - cbEx;
#if HEAP_SENTINELS
        pitNext->dwSig = TAILSIG;
#endif

        DEBUGMSG(DBGHEAP2, (L"CarveItem: new endmarker %8.8lx(%lx)\r\n", pitNext, pitNext->cbTail));

        // update the size of the item
        pit->size -= cbEx;
        pit->prgn = prgn;        // it's possible (pit == pitEnd), so we need to update pit->prgn
        cbItem = -pit->size;

        if (cbItem - cbSeek > prgn->cbMaxFree) {
            // if we get more after committing...
            prgn->cbMaxFree = (cbItem - cbSeek) | (prgn->cbMaxFree & REGION_MAX_IS_ESTIMATE);
        }

        DEBUGMSG(DBGHEAP2, (L"CarveItem: pit = %8.8lx pit->size = %8.8lx\r\n", pit, pit->size));
    }

    // must have enough room
    DEBUGCHK (prgn && (prgn == pit->prgn) && (cbSeek <= cbItem));

    // if the leftover is too small, use it up
    if (cbItem <= (int) (cbSeek + sizeof(item) + HEAP_SENTINELS)) {
        cbSeek = cbItem;
    }

    // create a new item if necessary
    pitNext = (pitem)((char*) pit + cbSeek);

    if (cbItem > cbSeek) {

        // create an item for the leftover space
        pitNext->size = cbSeek - cbItem;    // Free block size is stored as negative number