fixheap.c

See Hanoi.cpp for the implementation of this cla

			pTrav->pCur = ptr2;
			if ((pTrav->dwFree > (pTrav->dwCommitted >> 3)) &&
				((pTrav->dwFree > pTrav->dwLastCompact + (pagemask+1)*6) ||
				 ((UserKInfo[KINX_PAGEFREE]*UserKInfo[KINX_PAGESIZE] < 2*1024*1024) &&
				  (pTrav->dwFree > pTrav->dwLastCompact + (pagemask+1)*2))))
				FixedHeapCompact(pTrav);
			return TRUE;
		}
	}
	pvaprev = 0;
	for (pva = pHeap->pVallocs; pva; pvaprev = pva, pva = pva->pnext)
		if (pva->pBase == ptr) {
    		if (!pvaprev)
    			pHeap->pVallocs = pva->pnext;
    		else
    			pvaprev->pnext = pva->pnext;
	    	VirtualFree(pva->pBase,0,MEM_RELEASE);
    		FixedHeapFree(pHeap,pva);
    		return TRUE;
		}
	DEBUGCHK(0);
	SetLastError(ERROR_INVALID_PARAMETER);
	return FALSE;
}

// Alloc a heap block
LPVOID FixedHeapAlloc(pheap pHeapIn, UINT size, BOOL zero) {
   	pheap pHeap2;
	heap newheap;
	LPVOID ptr;
	UINT increase, presize;
	pheap pHeap;
	DWORD  dwMaxLeft;
#ifdef MEMTRACKING
	WCHAR Name[14];
#endif
	if (size & 0x80000000) {
		SetLastError(ERROR_NOT_ENOUGH_MEMORY);
		return 0;
	}
	size = (size + ALIGNMASK) & ~ALIGNMASK;
    if (size >= CE_VALLOC_MINSIZE) {
    	vaheapalloc *pva;
		if (!(ptr=VirtualAlloc(0,size,MEM_RESERVE|MEM_COMMIT,PAGE_READWRITE)))
			SetLastError(ERROR_NOT_ENOUGH_MEMORY);
		else {
			if (!(pva = FixedHeapAlloc(pHeapIn,sizeof(vaheapalloc),0))) {
				VirtualFree(ptr,0,MEM_RELEASE);
				ptr = 0;
			} else {
				pva->pBase = ptr;
				pva->dwSize = (size + pagemask) & ~pagemask;
				pva->pnext = pHeapIn->pVallocs;
				pHeapIn->pVallocs = pva;
			}
		}
#ifdef DEBUG
        if (!zero && ptr)
			memset(ptr, 0xcc, pva->dwSize);
#endif    
		return ptr;
	}
	for (pHeap = pHeapIn; pHeap; pHeap = pHeap->pGrowthHeap) {
		if (!pHeap->pMem)
			if (!SetupFixedHeap(pHeap))
				return 0;
		if ((!pHeap->dwMaxLeft && (size <= pHeap->dwFree)) || (size <= pHeap->dwMaxLeft)) {
			ptr = pHeap->pCur;
			dwMaxLeft = 0;
			do {
				if (!ISINUSE(ptr)) {
					if (ISFREE(ptr)) {
						GrowFree(pHeap,ptr);
						if (ITEMSIZE(ptr) >= size)
							goto FoundBlock;
					}
					DEBUGCHK(!pHeap->dwMaxLeft || (ITEMSIZE(ptr) <= pHeap->dwMaxLeft));
					if (ITEMSIZE(ptr) > dwMaxLeft)
						dwMaxLeft = ITEMSIZE(ptr);
				}
				ptr = NEXTBLOCK(pHeap,ptr);
			} while (((DWORD)ptr > (DWORD)pHeap->pCur) || 
	                 (((DWORD)ptr + ITEMSIZE(ptr)) < (DWORD)pHeap->pCur));
	        pHeap->dwMaxLeft = dwMaxLeft;
		}
		pHeap->pCur = pHeap->pMem;
	}
	for (pHeap = pHeapIn; pHeap; pHeap = pHeap->pGrowthHeap) {
		DEBUGCHK(pHeap->pMem);
		DEBUGCHK(pHeap->pCur == pHeap->pMem);
		ptr = pHeap->pMem;
		if (size <= (pHeap->dwFree + pHeap->dwMaximumSize - pHeap->dwCommitted)) {
			do {
				if (!ISINUSE(ptr) && MakePotentialSize(pHeap,ptr,size))
					goto FoundBlock;
				pHeap->pNexttolast = ptr;
				ptr = NEXTBLOCK(pHeap,ptr);
			} while (ptr != pHeap->pMem);
		}
	}
	for (pHeap = pHeapIn; pHeap; pHeap = pHeap->pGrowthHeap) {
		DEBUGCHK(pHeap->pMem);
		DEBUGCHK(pHeap->pCur == pHeap->pMem);
		if (size <= (pHeap->dwFree + ((DWORD)pHeap->pMem + pHeap->dwMaximumSize - (DWORD)pHeap->pHigh))) {
			if (!ISFREE(pHeap->pNexttolast) || ISDEAD(pHeap->pNexttolast)) {
				ptr = pHeap->pHigh;
				presize = 0;
			} else {
				ptr = pHeap->pNexttolast;
				presize = ITEMSIZE(pHeap->pNexttolast) + HDRSIZE + TLRSIZE;
			}
			increase = (size - presize + HDRSIZE + TLRSIZE + pagemask) & ~pagemask;
			if ((DWORD)pHeap->pHigh + increase <= (DWORD)pHeap->pMem + pHeap->dwMaximumSize) {
		        pHeap->flOptions |= HEAP_IS_CHANGING_VM;
				if (VirtualAlloc(pHeap->pHigh,increase,MEM_COMMIT,PAGE_READWRITE)) {
					pHeap->pHigh = (LPVOID)((DWORD)pHeap->pHigh + increase);
					pHeap->dwCommitted += increase;
					pHeap->dwFree += increase;
					if (!presize)
						pHeap->dwFree -= (HDRSIZE+TLRSIZE);
					INITFREEBLOCK(ptr,increase-HDRSIZE-TLRSIZE+presize);
					if (pHeap->dwMaxLeft && (ITEMSIZE(ptr) > pHeap->dwMaxLeft))
						pHeap->dwMaxLeft = ITEMSIZE(ptr);
				} else
					ptr = 0;
		        pHeap->flOptions &= ~HEAP_IS_CHANGING_VM;
		        goto FoundBlock;
		    }
		}
	}
	if (pHeapIn->flOptions & HEAP_IS_NEW)
		return 0;
	newheap.pNextHeap	  = 0;
	newheap.pGrowthHeap   = 0;
	newheap.pVallocs 	  = 0;
    newheap.flOptions     = (pHeapIn->flOptions & ~HEAP_IS_CHANGING_VM) | HEAP_IS_NEW;
    newheap.dwMaximumSize = CE_FIXED_HEAP_MAXSIZE;
    newheap.pMem          = NULL;
    newheap.pHigh         = NULL;
    newheap.pCur          = NULL;
    newheap.dwCommitted   = 0;
    newheap.dwFree        = 0;
    newheap.dwLastCompact = 0;
    newheap.dwMaxLeft     = 0;
   	if ((ptr = FixedHeapAlloc(&newheap,size,zero)) && (pHeap2 = FixedHeapAlloc(&newheap,sizeof(heap),0))) {
		*pHeap2 = newheap;
		pHeap2->pGrowthHeap = pHeapIn->pGrowthHeap;
		pHeapIn->pGrowthHeap = pHeap2;
		pHeap2->flOptions &= ~HEAP_IS_NEW;
#ifdef MEMTRACKING
		swprintf(Name, L"Heap %08X", pHeap2);
		pHeap2->dwMemType     = RegisterTrackedItem(Name);
#endif
		goto done;
	}
	if (newheap.pMem) {
		VirtualFree(newheap.pMem,newheap.dwMaximumSize,MEM_DECOMMIT);
		VirtualFree(newheap.pMem, 0, MEM_RELEASE);
	}
   	return 0;
FoundBlock:
	if (ptr) {
		SplitFreeBlock(pHeap,ptr,size);
		DEBUGCHK(pHeap->dwFree >= ITEMSIZE(ptr));
		pHeap->dwFree -= ITEMSIZE(ptr);
		if (pHeap->dwMaxLeft == ITEMSIZE(ptr))
			pHeap->dwMaxLeft = 0;
		INITUSEDBLOCK(ptr,ITEMSIZE(ptr));
		pHeap->pCur = NEXTBLOCK(pHeap,ptr);
		ptr = HEAPTOPTR(ptr);
		if (zero)
			memset(ptr,0,ITEMSIZE(PTRTOHEAP(ptr)));
#ifdef DEBUG
        if (!zero) {
        	UINT loop;
        	for (loop = 0; loop < ITEMSIZE(PTRTOHEAP(ptr)); loop++)
        		DEBUGCHK(((LPBYTE)ptr)[loop] == 0xcc);
        }
#endif    
	} else
		pHeap->pCur = pHeap->pMem;
done:
	return ptr;
}

// Realloc a heap block
LPVOID FixedHeapReAlloc(pheap pHeap, LPVOID ptr, UINT size, BOOL zero, BOOL move) {
	LPVOID newptr;
	UINT oldsize;
	pheap pTrav;
	vaheapalloc *pva, *pvaprev;
	for (pva = pHeap->pVallocs; pva; pva = pva->pnext) {
		if (pva->pBase == ptr) {
			if (size <= pva->dwSize) {
				if (!move)
					return ptr;
				if (!(newptr = FixedHeapAlloc(pHeap,size,0)))
					return ptr;
				memcpy(newptr,ptr,size);
			} else {
				if (!move)
					return 0;
				if (!(newptr = FixedHeapAlloc(pHeap,size,0)))
					return 0;
				memcpy(newptr,ptr,pva->dwSize);
				if (zero)
					memset((LPBYTE)newptr+pva->dwSize,0,size-pva->dwSize);
			}
			VirtualFree(pva->pBase,0,MEM_RELEASE);
			if (pHeap->pVallocs == pva)
				pHeap->pVallocs = pva->pnext;
			else {
				for (pvaprev = pHeap->pVallocs; pvaprev->pnext != pva; pvaprev = pvaprev->pnext)
					;
				pvaprev->pnext = pva->pnext;
			}
    		FixedHeapFree(pHeap,pva);
			return newptr;
		}
	}
	if (size & 0x80000000) {
		SetLastError(ERROR_NOT_ENOUGH_MEMORY);
		return 0;
	}
	size = (size + ALIGNMASK) & ~ALIGNMASK;
	newptr = ptr = PTRTOHEAP(ptr);
	for (pTrav = pHeap; pTrav; pTrav = pTrav->pGrowthHeap) {
		if (pTrav->pMem && IsSigValid(pTrav,ptr,0)) {
			oldsize = ITEMSIZE(ptr);
			if (size <= oldsize) {
				ShrinkBlock(pTrav,ptr,size);
				pTrav->pCur = NEXTBLOCK(pTrav,ptr);
				newptr = HEAPTOPTR(ptr);
				goto DoneRealloc;
			}
			newptr = NEXTBLOCK(pTrav,newptr);
			if ((newptr > ptr) && ISFREE(newptr)) {
				GrowFree(pTrav,newptr);
				if (ITEMSIZE(newptr)+HDRSIZE+TLRSIZE+oldsize >= size) {
					DEBUGCHK(pTrav->dwFree >= ITEMSIZE(newptr));
					pTrav->dwFree -= ITEMSIZE(newptr);
					if (pTrav->dwMaxLeft == ITEMSIZE(newptr))
						pTrav->dwMaxLeft = 0;
					INITUSEDBLOCK(ptr,oldsize+ITEMSIZE(newptr)+HDRSIZE+TLRSIZE);
					ShrinkBlock(pTrav,ptr,size);
					pTrav->pCur = NEXTBLOCK(pTrav,ptr);
					newptr = HEAPTOPTR(ptr);
					goto DoneRealloc;
				}
				pTrav->pCur = newptr;
			}
			if (move && (newptr = FixedHeapAlloc(pHeap,size,0))) {
				memcpy(newptr,HEAPTOPTR(ptr),oldsize);
				FixedHeapFree(pHeap,HEAPTOPTR(ptr));
				goto DoneRealloc;
			}
			return 0;
		}
	}
	DEBUGCHK(0);
	return 0;
DoneRealloc:
	if (zero && (size > oldsize))
		memset((LPBYTE)newptr+oldsize,0,FixedHeapSize(pHeap,newptr)-oldsize);
	return newptr;
}

// Compact a heap
void FixedHeapCompact(pheap pHeap) {
	LPBYTE ptr, ptr2;
	int numpieces, deadbytes, size, size2;
	if (!(ptr = pHeap->pMem) || (pHeap->flOptions & HEAP_IS_CHANGING_VM) || (pHeap->flOptions & HEAP_IS_SHARED))
		return;
	do {
		if (ISINUSE(ptr))
			ptr = NEXTBLOCK(pHeap, ptr);
		else {
			numpieces = deadbytes = 0;
			ptr2 = ptr;
			do {
				numpieces--;
				if (ITEMSIZE(ptr2) == pHeap->dwMaxLeft)
					pHeap->dwMaxLeft = 0;
				if (ISDEAD(ptr2))
					deadbytes -= ITEMSIZE(ptr2);
			} while (((ptr2 = NEXTBLOCK(pHeap, ptr2)) != pHeap->pMem) && !ISINUSE(ptr2));
			if (ptr2 != pHeap->pMem) {
				// see if there are going to be dead pages
				if (((DWORD)(ptr + HDRSIZE + pagemask) & ~pagemask) < ((DWORD)(ptr2 - TLRSIZE) & ~pagemask)) {
					// see if there is room at the start for a live free block
					size = pagemask + 1 - ((DWORD)ptr & pagemask);
					if (size > HDRSIZE + TLRSIZE + HDRSIZE) {
						INITFREEBLOCK(ptr, size - HDRSIZE - TLRSIZE - HDRSIZE);
						if (pHeap->dwMaxLeft && (pHeap->dwMaxLeft < ITEMSIZE(ptr)))
							pHeap->dwMaxLeft = ITEMSIZE(ptr);
						ptr += size - HDRSIZE;
						numpieces++;
					}
					// now do the dead block
					size = ptr2 - ptr;
					if (((DWORD)(ptr2 - TLRSIZE) & pagemask) >= HDRSIZE + TLRSIZE)
						size -= ((DWORD)ptr2 - TLRSIZE) & pagemask;
					INITDEADBLOCK(ptr,size - HDRSIZE - TLRSIZE);
					if (pHeap->dwMaxLeft && (pHeap->dwMaxLeft < ITEMSIZE(ptr)))
						pHeap->dwMaxLeft = ITEMSIZE(ptr);
					numpieces++;
					size2 = ((DWORD)(ptr2 - TLRSIZE) & ~pagemask) - ((DWORD)(ptr + HDRSIZE + pagemask) & ~pagemask);
					VirtualFree((LPVOID)((DWORD)(ptr+HDRSIZE+pagemask) & ~pagemask), size2, MEM_DECOMMIT);
					deadbytes += size - HDRSIZE - TLRSIZE;
					ptr += size;
				}
				// Do the final free block, if any
				if (ptr != ptr2) {
					DEBUGCHK(ptr + HDRSIZE + TLRSIZE <= ptr2);
					INITFREEBLOCK(ptr, ptr2 - ptr - HDRSIZE - TLRSIZE);
					if (pHeap->dwMaxLeft && (pHeap->dwMaxLeft < ITEMSIZE(ptr)))
						pHeap->dwMaxLeft = ITEMSIZE(ptr);
					numpieces++;
				}
				pHeap->pCur = pHeap->pMem;
				pHeap->dwCommitted -= deadbytes;
				DEBUGCHK((deadbytes + numpieces * (int)(HDRSIZE + TLRSIZE) < 0) || 
					(pHeap->dwFree >= deadbytes + numpieces * (HDRSIZE + TLRSIZE)));
				pHeap->dwFree -= deadbytes + numpieces*(HDRSIZE+TLRSIZE);
				ptr = NEXTBLOCK(pHeap, ptr2);
			} else {
				if (ptr == pHeap->pMem) {
					VirtualFree(pHeap->pMem,(LPBYTE)pHeap->pHigh - ptr,MEM_DECOMMIT);
					VirtualFree(pHeap->pMem,0,MEM_RELEASE);
				    pHeap->pMem = NULL;
				    pHeap->pHigh = NULL;
				    pHeap->pCur = NULL;
				    pHeap->dwCommitted = 0;
				    pHeap->dwFree = 0;
				    pHeap->dwMaxLeft = 0;
				} else {
					// see if there are going to be free bytes
					if ((DWORD)ptr & pagemask) {
						size = pagemask + 1 - ((DWORD)ptr & pagemask);
						if (size < HDRSIZE + TLRSIZE) {
#ifdef DEBUG
							// The place we want to put the tail signature could be on a free
							// block.  Since this is only in debug, and pretty rare, just
							// ignore the case.
							pHeap->pCur = pHeap->pMem;
							break;
#else						
							size += pagemask + 1;
#endif
						}
						INITFREEBLOCK(ptr, size - HDRSIZE - TLRSIZE);
						if (pHeap->dwMaxLeft && (pHeap->dwMaxLeft < ITEMSIZE(ptr)))
							pHeap->dwMaxLeft = ITEMSIZE(ptr);
						numpieces++;
						ptr = ptr + size;
					}
					if (ptr != pHeap->pHigh) {
						size2 = (LPBYTE)pHeap->pHigh - ptr;
						VirtualFree(ptr, size2, MEM_DECOMMIT);
						deadbytes += size2;
						pHeap->pHigh = ptr;
					}
					pHeap->pCur = pHeap->pMem;
					pHeap->dwCommitted -= deadbytes;
					DEBUGCHK((deadbytes + numpieces * (int)(HDRSIZE + TLRSIZE) < 0) || 
						(pHeap->dwFree >= deadbytes + numpieces * (HDRSIZE + TLRSIZE)));
					pHeap->dwFree -= deadbytes + numpieces * (HDRSIZE + TLRSIZE);
				}
				break;
			}
		}
	} while (ptr != pHeap->pMem);
	pHeap->dwLastCompact = pHeap->dwFree;
}