heap.c

不错的东西 请查看 WINCE OS

        DEBUGMSG(DBGHEAP2, (L"CarveItem: Leftover %8.8lx(%lx)\r\n", pitNext, pitNext->size));
        pitNext->prgn = prgn;
#if HEAP_SENTINELS
        SetFreeSentinels(pitNext);
#endif
    }

    // update the size of the new item
    if (pitcombine) {
        DEBUGCHK ((pitcombine->size > 0) && ((DWORD) pitcombine + pitcombine->size == (DWORD) pit));
        (pit = pitcombine)->size += cbSeek;

    } else {
        pit->size = cbSeek;
    }

    // update the region's free pointer
    if (pitNext->size <= 0) {
        if (prgn->pitFree > pitNext)
            prgn->pitFree = pitNext;

        // update pitLast if we hit the end
        if (!((pitem) ((char *) pitNext - pitNext->size))->size) {
            prgn->pitLast = pitNext;
        }
    }

#if HEAP_SENTINELS
    SetSentinels(pit, dwBytes);
#else
    // zero the excess memory we allocated to it
    cbEx = pit->size - sizeof(item) - dwBytes;

    //
    // DEBUGCHK ((cbEx >= 0) && (cbEx < 16));
    if (cbEx > 0) {
        memset ((char *)(pit+1) + dwBytes, 0, cbEx);
    }
#endif
    DEBUGMSG(DBGHEAP2, (L"CarveItem returns: pit = %8.8lx pit->size = %8.8lx\r\n", pit, pit->size));
    return pit;
}


//
// Large allocation using VirtualAlloc
//
static pitem DoLargeHeapAlloc (LPVOID lpSlot, pheap php, DWORD dwBytes)
{
    pitem pitRet;
    pvaitem pva;
    DWORD dwReserve, cbSeek, dwData = 0;

    // Attempt to allocate the memory block before taking the heap critical section
    // to improve multi-threaded behavior.
    cbSeek = (dwBytes + ALIGNSIZE(sizeof(vaitem)) + PAGE_SIZE-1) & ~(PAGE_SIZE-1);
    dwReserve = (cbSeek + HEAP_SENTINELS + 0xFFFFL) & 0xFFFF0000L;
    if (!(pva = php->pfnAlloc (lpSlot, dwReserve, MEM_RESERVE, &dwData))
            || !php->pfnAlloc (pva, cbSeek, MEM_COMMIT, &dwData)) {
        if (pva)
            php->pfnFree (pva, 0, MEM_RELEASE, dwData);

        return NULL;
    }

    // New VA'ed item created.  Initialize the item structure within the vaitem.
    pva = (pvaitem)((char*)pva + (ALIGNSIZE(sizeof(vaitem)) - sizeof(vaitem)));
    pva->dwData = dwData;
    pitRet = &pva->it;
    pitRet->php = php;
    pitRet->size = (cbSeek - ALIGNSIZE(sizeof(vaitem)) + sizeof(item)) | 1;  // Tag item as VirtualAlloc'ed

#if HEAP_SENTINELS
    SetSentinels(pitRet, dwBytes);
#endif

    // Take the heap's CS and link it into the vaitem list.
    EnterCriticalSection(&php->cs);
    pva->pvaFwd = php->pvaList;
    if (php->pvaList)
        php->pvaList->pvaBak = pva;
    php->pvaList = pva;
    LeaveCriticalSection(&php->cs);

    return pitRet;
}

// find a free item of size >= cbSeek in a region (HOLDING HEAP CS).
static pitem FindFreeItemInRegion (LPVOID lpSlot, pregion prgn, int cbSeek)
{
    pitem pitStart = prgn->pitFree;
    pitem pit, pitRet, pitEnd;
    int   cbItem;
    int   nEndReached = 0;
    int   cbMax = 0;

    if (!pitStart->size)
        pitStart = FIRSTITEM (prgn);

    DEBUGMSG(DBGHEAP2, (L"1:FindFreeItemInRegion %8.8lx %8.8lx\r\n", prgn->pitFree, pitStart));
    pit = pitStart;
#ifndef FREE_POINTER_AT_LAST_FREE
    if (prgn->pitFree->size > 0)
        prgn->pitFree = prgn->pitLast;
#endif

    do {

        // find the next free item
        // NOTE: MUST SAVE THE SIZE IN LOCAL OR THERE'LL BE RACE CONDITION BECAUSE
        //       HeapReAlloc DOES NOT ACQUIRE CS while shrinking.
        while ((cbItem = pit->size) > 0) {
            pit = (pitem)((char*)pit + cbItem);
        }

        pit = MergeFreeItems (prgn, pitRet = pit);
        cbItem = -pitRet->size;

        // Is the block big enough?
        if (cbItem >= cbSeek) {

            DEBUGMSG(DBGHEAP2, (L"FindFreeItemInRegion returns pitRet = %8.8lx\r\n", pitRet));
            if (cbItem - cbSeek > cbMax)
                cbMax = cbItem - cbSeek;

            break;
        }

        if (cbMax < cbItem)
            cbMax = cbItem;

        if (nEndReached && (pit >= pitStart))
            break;

        // if we've reached the last block and the size is big enough, mark the end
        // but don't use it yet -- since it requires committing more memory
        if (!pit->size) {

            if (nEndReached ++) {
                // heap is corrupted -- faked end marker being inserted
                DEBUGMSG(DBGHEAP2, (L"!FindFreeItemInRegion: Heap is corrupted\r\n"));
                DEBUGCHK (0);
                return NULL;
            }
            pitEnd = pitRet;

            // continue search from the 1st item if not done the full pass
            pit = FIRSTITEM (prgn);
        }

    }while (!nEndReached || (pit < pitStart));

    if (cbItem < cbSeek) {

        // if we reach here, either we need to commit more memory or don't have enough room

        // if the last item examined is not the end, update it to the recorded end
        if (pit->size)
            pitRet = pitEnd;

        pitEnd = (pitem) ((char *)pitRet - pitRet->size);

        DEBUGCHK ((pitRet->size <= 0) && !pitEnd->size);

        // need an extra room for tail item. thus the check
        if (pitEnd->cbTail - pitRet->size < (int) (cbSeek + sizeof(item)))
            pitRet = NULL;

        prgn->cbMaxFree = 0;    // the number is no longer an estimate, wil be updated next
    }

    if (cbMax > prgn->cbMaxFree) {
        prgn->cbMaxFree = cbMax | (prgn->cbMaxFree & REGION_MAX_IS_ESTIMATE);
    }

    DEBUGMSG(DBGHEAP2, (L"FindFreeItemInRegion returns pitRet = %8.8lx\r\n", pitRet));
    return pitRet;
}


// find a free item of size >= cbSeek in a heap (HOLDING HEAP CS).
static pitem FindFreeItem (LPVOID lpSlot, pheap php, DWORD cbSeek, pregion *pprgn)
{
    pregion prgn = &php->rgn;
    pitem   pitRet = NULL;

    DEBUGMSG(DBGHEAP2, (L"FindFreeItem %8.8lx %8.8lx %8.8lx\r\n", lpSlot, php, cbSeek));

    // pass 1: look for regions with items large enough for us
    do {
        if (prgn->cbMaxFree >= (int) cbSeek) {
            if (pitRet = FindFreeItemInRegion (lpSlot, prgn, cbSeek)) {
                DEBUGCHK (pitRet->size <= 0);
                break;
            }
        }
    } while (prgn = prgn->prgnNext);

    // pass 2: look for all region that are estimates or need to commit memory
    if (!pitRet) {
        prgn = &php->rgn;
        do {
            // if the region has an exact upper bound, return the pitLast if there are
            // enough room at the end after committing pages
            if (!(prgn->cbMaxFree & REGION_MAX_IS_ESTIMATE)) {
                pitem pitLast = prgn->pitLast;
                pitem pitTail = (pitem) ((char *) pitLast - pitLast->size);
                if (pitTail->cbTail - pitLast->size > (int) cbSeek) {
                    pitRet = pitLast;
                    break;
                }
            } else if (pitRet = FindFreeItemInRegion (lpSlot, prgn, cbSeek)) {
                DEBUGCHK (pitRet->size <= 0);
                break;
            }
        } while (prgn = prgn->prgnNext);
    }
    *pprgn = prgn;
    DEBUGMSG(DBGHEAP2, (L"FindFreeItem returns %8.8lx, prgn = %8.8lx\r\n", pitRet, prgn));
    return pitRet;
}


/*
    @doc BOTH EXTERNAL

    @func LPVOID | HeapReAlloc | Realloc's a HeapAlloc'ed block of memory
    @parm HANDLE | hHeap     | Handle returned from CreateHeap()
    @parm DWORD  | dwFlags   | HEAP_NO_SERIALIZE, HEAP_REALLOC_IN_PLACE_ONLY and HEAP_ZERO_MEM supported
    @parm LPVOID | lpMem     | pointer to memory to realloc
    @parm DWORD  | dwBytes   | Desired size of block
*/
LPVOID WINAPI HeapReAlloc(HANDLE hHeap, DWORD dwFlags, LPVOID lpMem, DWORD dwBytes)
{
    return ptrHeapReAlloc (hHeap, dwFlags, lpMem, dwBytes);
}
LPVOID WINAPI Int_HeapReAlloc(HANDLE hHeap, DWORD dwFlags, LPVOID lpMem, DWORD dwBytes)
{
    LPVOID pRet = NULL;
    int cbItem;
    int cbOrigSize;
    int cbSeek;
    pitem pit;
    pheap php = (pheap)hHeap;
    pregion prgn;
    BOOL bZeroPtr = FALSE;      // set to TRUE if caller is using "zero based pointers"
#if HEAP_SENTINELS
    DWORD dwSize;
#endif

    if (((DWORD)hHeap>>SECTION_SHIFT) != ((DWORD)lpMem>>SECTION_SHIFT)) {
        // The ptr has been unmapped by someone or it doesn't belong to this heap.
        if ((DWORD)lpMem>>SECTION_SHIFT) {
            DEBUGMSG(DBGFIXHP, (L"   1:HeapReAlloc %8.8lx %8.8lx %8.8lx %8.8lx ==> %8.8lx (invalid parameter)\r\n", hHeap,dwFlags,lpMem,dwBytes,0));
            SetLastError(ERROR_INVALID_PARAMETER);
            return NULL;
        }
        // Restore the "slot mapping" bits to the pointer.
        lpMem = (LPVOID)((DWORD)lpMem | ((DWORD)hHeap & -(1<<SECTION_SHIFT)));
        bZeroPtr = TRUE;
    }
    pit = (pitem)((char*)lpMem - sizeof(item));
    if (dwFlags & ~(HEAP_GENERATE_EXCEPTIONS | HEAP_NO_SERIALIZE | HEAP_REALLOC_IN_PLACE_ONLY | HEAP_ZERO_MEMORY)) {
        DEBUGMSG(DBGFIXHP, (L"   2:HeapReAlloc %8.8lx %8.8lx %8.8lx %8.8lx ==> %8.8lx (invalid parameter)\r\n", hHeap,dwFlags,lpMem,dwBytes,0));
        SetLastError(ERROR_INVALID_PARAMETER);
        return NULL;
    }
    if (dwFlags & HEAP_GENERATE_EXCEPTIONS) {
        DEBUGMSG(DBGFIXHP, (L"   3:HeapReAlloc %8.8lx %8.8lx %8.8lx %8.8lx ==> %8.8lx (not supported)\r\n", hHeap,dwFlags,lpMem,dwBytes,0));
        SetLastError(ERROR_NOT_SUPPORTED);
        return NULL;
    }
    if (!hHeap || php->dwSig != HEAPSIG || (DWORD)ZeroPtr(lpMem) < 0x10000 || pit->size <= 0) {
        DEBUGMSG(DBGFIXHP, (L"   4:HeapReAlloc %8.8lx %8.8lx %8.8lx %8.8lx %8.8lx (invalid parameter)\r\n", hHeap,dwFlags,lpMem,dwBytes,pit->size));
        SetLastError(ERROR_INVALID_PARAMETER);
        return NULL;
    }
    if (dwBytes > HEAP_MAX_ALLOC) {
        DEBUGMSG(DBGFIXHP, (L"   5:HeapReAlloc %8.8lx %8.8lx %8.8lx %8.8lx ==> %8.8lx\r\n", hHeap,dwFlags,lpMem,dwBytes,0));
        SetLastError(ERROR_NOT_ENOUGH_MEMORY);
        return NULL;
    }

    cbItem = pit->size;
#if HEAP_SENTINELS
    cbOrigSize = pit->cbTrueSize;
#else
    cbOrigSize = cbItem & ~1;
#endif

    if (cbItem & 1) {
        // VirtualAlloc'ed item.  Validate that the item pointer falls correctly within a
        // 64K aligned virtual memory block and that the heap owner information in the
        // item is correct.
        pvaitem pva;
        int cbAllocated;

        --cbItem;       // Fix the item size
        pva = (pvaitem)(((DWORD)lpMem&0xFFFF0000) + (ALIGNSIZE(sizeof(vaitem)) - sizeof(vaitem)));
        cbAllocated = cbItem + (ALIGNSIZE(sizeof(vaitem)) - sizeof(item));
        if (pit != &pva->it || pit->php != php || (cbAllocated & PageMask) != 0) {
            DEBUGMSG(DBGFIXHP, (L"   6:HeapReAlloc %8.8lx %8.8lx %8.8lx %8.8lx ==> %8.8lx (invalid parameter)\r\n", hHeap,dwFlags,lpMem,dwBytes,0));
            SetLastError(ERROR_INVALID_PARAMETER);
            return NULL;
        }
#if HEAP_SENTINELS
        CheckSentinels(pit, TRUE);
#endif
        cbSeek = (dwBytes + ALIGNSIZE(sizeof(vaitem)) + PAGE_SIZE-1) & ~(PAGE_SIZE-1);
        if (cbSeek <= cbAllocated) {
            // Just use the existing block and treat this as a NOP.
#if HEAP_SENTINELS
            // If the size is changing, we must update the sentinels and
            // possibly zero out a few bytes.
            if ((dwSize = pit->cbTrueSize) != dwBytes) {
                SetSentinels(pit, dwBytes);
                if (dwSize < dwBytes && (dwFlags & HEAP_ZERO_MEMORY))
                    memset((char*)(pit+1)+dwSize, 0, dwBytes-dwSize);
            }
#endif
            pRet = pit+1;
        }
        

    } else {
        // Normal heap allocation.  Verify the region parameters.
        prgn = pit->prgn;
        if (prgn == NULL || php != prgn->phpOwner || (cbItem & (ALIGNBYTES-1)) != 0) {
            DEBUGMSG(DBGFIXHP, (L"   7:HeapReAlloc %8.8lx %8.8lx %8.8lx %8.8lx ==> %8.8lx (invalid parameter)\r\n", hHeap,dwFlags,lpMem,dwBytes,0));
            SetLastError(ERROR_INVALID_PARAMETER);
            return NULL;
        }
#if HEAP_SENTINELS
        CheckSentinels(pit, TRUE);
#endif
        cbSeek = ALIGNSIZE(dwBytes + sizeof(item) + HEAP_SENTINELS);

        if (cbSeek > cbItem) {
            // Need to grow the block. Check to see if there is a free block following
            // this one that is large enough to satisfy the request.
            pitem pitTrav, pitNext = (pitem)((char*)pit + cbItem);
            int   cbNext;

            // grab the CS
            EnterCriticalSection(&php->cs);

            if (pitNext->size > 0) {
                // release CS
                LeaveCriticalSection(&php->cs);

            } else {

                pitTrav = MergeFreeItems (prgn, pitNext);
                cbNext = -pitNext->size;

                DEBUGMSG(DBGFIXHP, (L"   8:HeapReAlloc %8.8lx %8.8lx %8.8lx %8.8lx\n", cbSeek, cbItem, cbNext, pitTrav->size));
                // do we have room to do in-place realloc?
                if ((cbItem + cbNext >= cbSeek)                 // have room by merging with free blocks?
                    || (!pitTrav->size                          // reach the end marker and have enough room?
                        && (cbItem + cbNext + pitTrav->cbTail > cbSeek))) {
                    if (pit = CarveItem (prgn, pitNext, cbSeek - cbItem, dwBytes, pit)) {
                        pRet = pit + 1;   // return value is right after the item

                        if (prgn->pitFree > pit) {
                            prgn->pitFree = (pitem) ((char *)pit + pit->size);
                        }
                    }