/* Copyright (c) 1999-2000 Microsoft Corporation.  All rights reserved. */
#include <windows.h>
#include <coredll.h>
#include "heap.h"
#include <memory.h>

// layout: (DBG = with sentinels, RET = without sentinels)
//	[4 byte size in bytes not including headers, H_FREEBLOCK set if free]
//	[4 byte signature set to FREESIGHEAD/ALLOCSIGHEAD in DBG, unused on 64 bit
//		machines RET, not present on 32 bit machines RET]
//	[n byte free or data]
//	[4 byte signature set to FREESIGTAIL/ALLOCSIGTAIL in DBG, not present in RET]
//	[4 byte unused on 64 bit machines in DBG, else not present]

extern DWORD pagemask;

extern heap ProcessHeap;

_inline void INITFREEBLOCK(LPVOID p, UINT size) {
	HEADPTR(p)->size = (size & H_SIZEMASK) | H_FREEBLOCK;
#if HEAP_SENTINELS
	HEADPTR(p)->sig = FREESIGHEAD;
	TAILPTR(p)->sig = FREESIGTAIL;
#endif
#ifdef DEBUG
	memset(HEAPTOPTR(p),0xcc,size);
#endif
}

_inline void INITUSEDBLOCK(LPVOID p, UINT size) {
	HEADPTR(p)->size = size & H_SIZEMASK;
#if HEAP_SENTINELS
	HEADPTR(p)->sig = ALLOCSIGHEAD;
	TAILPTR(p)->sig = ALLOCSIGTAIL;
#endif
}

_inline void INITDEADBLOCK(LPVOID p, UINT size) {
	HEADPTR(p)->size = (size & H_SIZEMASK) | H_DEADBLOCK;
#if HEAP_SENTINELS
	HEADPTR(p)->sig = DEADSIGHEAD;
	TAILPTR(p)->sig = DEADSIGTAIL;
#endif
}

BOOL IsSigValid(pheap pHeap, LPVOID ptr, DWORD allowfree) {
	if (!pHeap->pMem || ((DWORD)ptr < (DWORD)pHeap->pMem) || ((DWORD)ptr > (DWORD)pHeap->pHigh - HDRSIZE - TLRSIZE))
        return FALSE;
	if (!allowfree && !ISINUSE(ptr))
		return FALSE;
#if HEAP_SENTINELS
	if (HEADPTR(ptr)->sig != (ISFREE(ptr) ? FREESIGHEAD : ISDEAD(ptr) ? DEADSIGHEAD : ALLOCSIGHEAD))
		return FALSE;
#endif
	if ((DWORD)TAILPTR(ptr) + TLRSIZE > (DWORD)pHeap->pHigh)
		return FALSE;
#if HEAP_SENTINELS
	if (TAILPTR(ptr)->sig != (ISFREE(ptr) ? FREESIGTAIL : ISDEAD(ptr) ? DEADSIGTAIL :ALLOCSIGTAIL))
		return FALSE;
#endif
	return TRUE;
}

// Extend a free block, only through other free blocks
void GrowFree(pheap pHeap, LPVOID ptr) {
	LPVOID newptr;
	DWORD growth, numnew;

	growth = numnew = 0;
	newptr = NEXTBLOCK(pHeap, ptr);
	while ((newptr > ptr) && ISFREE(newptr)) {
		growth += ITEMSIZE(newptr) + HDRSIZE + TLRSIZE;
		numnew++;
		newptr = NEXTBLOCK(pHeap, newptr);
	}
	if (growth) {
		HEADPTR(ptr)->size += growth;
		pHeap->dwFree += (HDRSIZE+TLRSIZE)*numnew;
#ifdef DEBUG
		memset(HEAPTOPTR(ptr),0xcc,ITEMSIZE(ptr));
#endif
	}
	if (pHeap->dwMaxLeft && (pHeap->dwMaxLeft < ITEMSIZE(ptr)))
		pHeap->dwMaxLeft = ITEMSIZE(ptr);
}

// Extend a free/dead block through other free/dead blocks if it will yield a free block of 'size'
DWORD MakePotentialSize(pheap pHeap, LPBYTE ptr, DWORD size) {
	LPBYTE ptr2 = ptr;
	int deadbytes = 0, numpieces = 0, lastdead = 0, size2, maxhit;
	do {
		numpieces++;
		if (lastdead = ISDEAD(ptr2)) {
			maxhit = (ITEMSIZE(ptr2) == pHeap->dwMaxLeft);
			deadbytes += ITEMSIZE(ptr2);
		}
		ptr2 = NEXTBLOCK(pHeap,ptr2);
	} while ((ptr2 != pHeap->pMem) && !ISINUSE(ptr2) && (ptr2 < ptr + size + HDRSIZE + TLRSIZE));
	if (ptr2 == pHeap->pMem)
		ptr2 = pHeap->pHigh;
	if (ptr + HDRSIZE + TLRSIZE + size > ptr2)
		return FALSE;
    pHeap->flOptions |= HEAP_IS_CHANGING_VM;
	if (lastdead) {
		LPBYTE tmpptr1, tmpptr2;
		tmpptr1 = (LPBYTE)((DWORD)(ptr + HDRSIZE + size + TLRSIZE + HDRSIZE + pagemask) & ~pagemask);
		tmpptr2 = (LPBYTE)((DWORD)(ptr2 - TLRSIZE) & ~pagemask);
		if (tmpptr1 < tmpptr2) {
			deadbytes -= ptr2 - TLRSIZE - tmpptr1;
			size2 = ptr2 - TLRSIZE - tmpptr1;
			ptr2 = tmpptr1 - HDRSIZE;
		} else
			lastdead = 0;
	}
	// since this does whole pages, it'll get the header for ptr2 if we're doing a lastdead
	if (!VirtualAlloc(ptr,ptr2-ptr,MEM_COMMIT, PAGE_READWRITE)) {
	    pHeap->flOptions &= ~HEAP_IS_CHANGING_VM;
		return FALSE;
	}
	if (lastdead) {
		INITDEADBLOCK(ptr2,size2);
		numpieces--;
		if (pHeap->dwMaxLeft && (pHeap->dwMaxLeft < ITEMSIZE(ptr2)))
			pHeap->dwMaxLeft = ITEMSIZE(ptr2);
		else if (maxhit)
			pHeap->dwMaxLeft = 0;
	}
    pHeap->flOptions &= ~HEAP_IS_CHANGING_VM;
	INITFREEBLOCK(ptr,ptr2-ptr-HDRSIZE-TLRSIZE);
	numpieces--;
	pHeap->dwCommitted += deadbytes;
	pHeap->dwFree += deadbytes;
    pHeap->dwFree += numpieces*(HDRSIZE+TLRSIZE);
	if (pHeap->dwMaxLeft && (pHeap->dwMaxLeft < ITEMSIZE(ptr)))
		pHeap->dwMaxLeft = ITEMSIZE(ptr);

	return TRUE;
}

// Break a free block into two pieces (if enough room)
void SplitFreeBlock(pheap pHeap, LPVOID ptr, UINT size) {
	UINT cursize;
	LPVOID ptr2;
	cursize = ITEMSIZE(ptr);
	if (pHeap->dwMaxLeft == cursize)
		pHeap->dwMaxLeft = 0;
	if (cursize - size > HDRSIZE + TLRSIZE) {
		ptr2 = (LPVOID)((DWORD)ptr + HDRSIZE + TLRSIZE + size);
		INITFREEBLOCK(ptr,size);
		INITFREEBLOCK(ptr2,cursize-size-HDRSIZE-TLRSIZE);
		// needed because of the "extension" case, since if we allowed the original free extension to be
		// added, it would immediately be removed and we'd set to 0.
		if (pHeap->dwMaxLeft && (pHeap->dwMaxLeft < ITEMSIZE(ptr2)))
			pHeap->dwMaxLeft = ITEMSIZE(ptr2);
		DEBUGCHK(pHeap->dwFree >= HDRSIZE + TLRSIZE);
		pHeap->dwFree -= HDRSIZE + TLRSIZE;
	}
}

// Shrink a block (splitting off another free block)
void ShrinkBlock(pheap pHeap, LPVOID ptr, UINT size) {
	UINT cursize;
	LPVOID ptr2;

	cursize = ITEMSIZE(ptr);
	if (cursize - size > HDRSIZE + TLRSIZE) {
		ptr2 = (LPVOID)((DWORD)ptr + HDRSIZE + TLRSIZE + size);
		HEADPTR(ptr)->size = size;
#if HEAP_SENTINELS
		TAILPTR(ptr)->sig = ALLOCSIGTAIL;
#endif
		INITFREEBLOCK(ptr2,cursize-size-HDRSIZE-TLRSIZE);
		if (pHeap->dwMaxLeft && (pHeap->dwMaxLeft < ITEMSIZE(ptr2)))
			pHeap->dwMaxLeft = ITEMSIZE(ptr2);
		pHeap->dwFree += cursize-size-HDRSIZE-TLRSIZE;
	}
}

#ifdef DEBUG

UINT WINAPI _HeapDump(HLOCAL hHeap) {
    pheap  pHeap = (pheap) hHeap;
	LPVOID ptr;
	UINT retval = 0;
	vaheapalloc *pvalloc;
    if (!pHeap)
        pHeap = &ProcessHeap;
    EnterCriticalSection(&hcs);
    try {
		if (!pHeap->pMem) {
	        DEBUGMSG(1, (TEXT("_HeapDump: Heap empty\r\n")));
	        goto done;
	    }
		while (pHeap) {
		    DEBUGMSG(1, (TEXT("flOptions:     0x%08X   pMem:    0x%08X\r\npHigh:         0x%08X   pLast:   0x%08X\r\ndwMaximumSize: 0x%08X   pCur:    0x%08X\r\ndwCommitted:   0x%08X   HDRSIZE: 0x%08X\r\ndwFree:        0x%08X   TLRSIZE: 0x%08X\r\n\r\n"),
    		             pHeap->flOptions,
        		         pHeap->pMem,
            		     pHeap->pHigh,
	                	 pHeap->dwLastCompact,
		                 pHeap->dwMaximumSize,
	    	             pHeap->pCur,
	        	         pHeap->dwCommitted,
	            	     HDRSIZE,
		                 pHeap->dwFree,
		                 TLRSIZE));
			ptr = pHeap->pMem;
			do {
				if (!IsSigValid(pHeap,ptr,1)) {
					retval = 1;
					goto done;
				}
#if HEAP_SENTINELS
		        DEBUGMSG(1, (TEXT("0x%08X %s size: 0x%08X sig: 0x%08X\r\n"),
	    	             ptr, ISFREE(ptr) ? TEXT("FREEBLOCK") : ISDEAD(ptr) ? TEXT("DEADBLOCK") : TEXT("USEDBLOCK"),
	        	         ITEMSIZE(ptr), HEADPTR(ptr)->sig));
		        DEBUGMSG(1, (TEXT("0x%08X                            sig: 0x%08X\r\n"),
	    	             TAILPTR(ptr), TAILPTR(ptr)->sig));
#else
		        DEBUGMSG(1, (TEXT("0x%08X %s size: 0x%08X\r\n"),
	    	             ptr, ISFREE(ptr) ? TEXT("FREEBLOCK") : ISDEAD(ptr) ? TEXT("DEADBLOCK") :TEXT("USEDBLOCK"),
	        	         ITEMSIZE(ptr)));
#endif
			} while ((ptr = NEXTBLOCK(pHeap, ptr)) != pHeap->pMem);
			for (pvalloc = pHeap->pVallocs; pvalloc; pvalloc = pvalloc->pnext)
				DEBUGMSG(1,(TEXT("Extended block at 0x%8.8lx, length 0x%8.8lx\r\n"),pvalloc->pBase,pvalloc->dwSize));
			pHeap = pHeap->pGrowthHeap;
		}
	    DEBUGMSG(1, (TEXT("-----------------------------------------------------\r\n")));
done:
		;
	} except (EXCEPTION_EXECUTE_HANDLER) {
		retval = 1;
	}
    LeaveCriticalSection(&hcs);
	return retval;
}

#endif

BOOL WINAPI HeapValidate(HANDLE hHeap, DWORD dwFlags, LPCVOID lpMem) {
	BOOL retval = FALSE;
	LPVOID ptr, ptr2;
	pheap pHeap;
	vaheapalloc *pvalloc;
    if (dwFlags & ~HEAP_NO_SERIALIZE) {
	    SetLastError(ERROR_INVALID_PARAMETER);
		return FALSE;
    }
	EnterCriticalSection(&hcs);
	try {
		if (lpMem) {
			ptr = PTRTOHEAP(lpMem);
			for (pHeap = (pheap)hHeap; pHeap; pHeap = pHeap->pGrowthHeap) {
				 if ((ptr >= pHeap->pMem) && (ptr < pHeap->pHigh)) {
				 	retval = IsSigValid(pHeap,ptr,0);
				 	goto done;
				}
				for (pvalloc = pHeap->pVallocs; pvalloc; pvalloc = pvalloc->pnext) {
					if (pvalloc->pBase == lpMem) {
						if (!((DWORD)pvalloc->pBase & 0xffff) && (pvalloc->dwSize >= CE_VALLOC_MINSIZE))
							retval = TRUE;
						goto done;
					}
				}
			}
		} else {
			for (pHeap = (pheap)hHeap; pHeap; pHeap = pHeap->pGrowthHeap) {
				if (ptr = pHeap->pMem) {
					do {
						if (!IsSigValid(pHeap,ptr,1))
							goto done;
						ptr2 = (LPVOID)((DWORD)ptr + HDRSIZE + ITEMSIZE(ptr) + TLRSIZE);
						if (ptr2 <= ptr)
							goto done;
					} while ((ptr = ptr2) != pHeap->pHigh);
				}
				for (pvalloc = pHeap->pVallocs; pvalloc; pvalloc = pvalloc->pnext) {
					if (((DWORD)pvalloc->pBase & 0xffff) || (pvalloc->dwSize < CE_VALLOC_MINSIZE))
						goto done;
				}
			}
			retval = TRUE;
		}
done:
		;
	} except (EXCEPTION_EXECUTE_HANDLER) {
		retval = FALSE;
	}
	LeaveCriticalSection(&hcs);
#ifdef DEBUG
	if (!retval)
		_HeapDump(hHeap);
#endif
	return retval;
}

// Initialize a heap
BOOL SetupFixedHeap(pheap pHeap) {
	LPVOID pMem;
	if (!(pMem = VirtualAlloc(NULL,pHeap->dwMaximumSize,MEM_RESERVE,PAGE_NOACCESS)))
        return FALSE;
	pHeap->dwCommitted = pagemask + 1;
    if (!VirtualAlloc(pMem,pHeap->dwCommitted, MEM_COMMIT, PAGE_READWRITE)) {
    	VirtualFree(pMem,0,MEM_RELEASE);
		return FALSE;
	}
	DEBUGCHK(pHeap->dwCommitted >= HDRSIZE + TLRSIZE);
	pHeap->dwFree = pHeap->dwCommitted - HDRSIZE - TLRSIZE;
	pHeap->pHigh = (LPVOID)((LPBYTE)pMem + pHeap->dwCommitted);
	INITFREEBLOCK(pMem,pHeap->dwFree);
	pHeap->pCur = pMem;
	pHeap->pMem = pMem;	// heap is now initialized - this must come LAST!
	pHeap->dwMaxLeft = ITEMSIZE(pHeap->pCur);
	return TRUE;
}

LPBYTE InitSharedHeap(LPBYTE pMem, DWORD size, DWORD reserve) {
	LPBYTE pReserved, pData;
	pheap pHeap;
	LPVOID pAlloc;
	pReserved = pMem + ((sizeof(heap)+ALIGNMASK)&~ALIGNMASK);
	if (size) {
	    pAlloc = VirtualAlloc(pMem,pagemask+1, MEM_COMMIT, PAGE_READWRITE);
    	DEBUGCHK(pAlloc == pMem);
		pHeap = (pheap)pMem;
		pData = pReserved + ((reserve+ALIGNMASK)&~ALIGNMASK);
		size -= (pData - pMem);
		size &= ~ALIGNMASK;
		pHeap->dwCommitted   = pagemask + 1 - (pData - pMem);
		pHeap->pVallocs      = 0;
		pHeap->pGrowthHeap   = 0;
	    pHeap->flOptions     = HEAP_IS_SHARED;
	    pHeap->dwMaximumSize = size;
	    pHeap->pMem          = pData;
	    pHeap->pCur          = pData;
	    pHeap->pHigh         = (LPVOID)((LPBYTE)pData+pHeap->dwCommitted);
		DEBUGCHK(pHeap->dwCommitted >= HDRSIZE-TLRSIZE);
	    pHeap->dwFree        = pHeap->dwCommitted-HDRSIZE-TLRSIZE;
	    pHeap->dwLastCompact = 0;
		INITFREEBLOCK(pData,pHeap->dwFree);
	}
	return pReserved;
}

// Get size of heap block
DWORD FixedHeapSize(pheap pHeap, LPVOID ptr) {
	LPVOID ptr2;
	vaheapalloc *pva;
	pheap pTrav;
	EnterCriticalSection(&hcs);
	ptr2 = PTRTOHEAP(ptr);
	for (pTrav = pHeap; pTrav; pTrav = pTrav->pGrowthHeap) {
		if (pTrav->pMem && IsSigValid(pTrav,ptr2,0)) {
			LeaveCriticalSection(&hcs);
			return ITEMSIZE(ptr2);
		}
	}
	for (pva = pHeap->pVallocs; pva; pva = pva->pnext)
		if (pva->pBase == ptr) {
			LeaveCriticalSection(&hcs);
			return pva->dwSize;
		}
	LeaveCriticalSection(&hcs);
	return (DWORD)-1;
}

// Free a heap block
BOOL FixedHeapFree(pheap pHeap, LPVOID ptr) {
	LPVOID ptr2;
	vaheapalloc *pva, *pvaprev;
	pheap pTrav;
	ptr2 = PTRTOHEAP(ptr);
	for (pTrav = pHeap; pTrav; pTrav = pTrav->pGrowthHeap) {
		if (pTrav->pMem && IsSigValid(pTrav,ptr2,0)) {
			pTrav->dwFree += ITEMSIZE(ptr2);
			INITFREEBLOCK(ptr2,ITEMSIZE(ptr2));
			GrowFree(pTrav,ptr2);