/* Copyright (c) Microsoft Corporation. All rights reserved. */ #define OPTIMIZE /* enable Base.h optimizations, since we're the "base" */ #include <stdio.h> #include <string.h> #include <mmlite.h> #include <mmmacros.h> #include "heap.h" #define DPRINT(x) #define EPRINT(x) DBG(x) #ifdef h8 // XXX if _DEBUG is not defined, sometimes HEAP_ZERO_MEMORY is strangely ignored. // XXX NEED TO DEBUG LATER #define _DEBUG #endif /* xxx not supported */ #define HEAP_GROWABLE 0x00000002 /* This code modeled after Brian Smith's heap code * * Heap code is performance sensitive. To allow selective debbugging: * * HPDBG - Add code to help debug heap trashes. */ #ifdef _DEBUG #define HPDBG #endif #if defined(_MSC_VER) && defined(HPDBG) #pragma message("heap.c: HPDBG turned on") #endif /*#define TRACE_USER_LEAKS(x) x */ #define TRACE_USER_LEAKS(x) /* Heap memory block headers */ typedef struct _USEDBLK USEDBLK, *PUSEDBLK; struct _USEDBLK { /* Allocated heap memory (multiple of 8 bytes) */ ADDR_SIZE Size; /* Includes header. flags in lsbits (see below) */ #if !defined(__HAS_LARGE_ADDRESSES) UINT Sign; /* Signature */ #endif }; typedef struct _FREEBLK FREEBLK, *PFREEBLK; struct _FREEBLK { /* Free heap memory */ ADDR_SIZE Size; /* Must match USEDBLK */ FREEBLK *pNext; /* Next free block on this list */ FREEBLK *pPrev; /* Previous free block on this list */ PUINT pThis; /* Actually, last word in block */ }; /* Flags stored in lower bits of size field in the above structures * Alignment requirements constrain how many bits we can use */ #if _UINTSIZE == 16 #define HB_ALIGN 4 /* Allocation alignment */ #else #define HB_ALIGN 8 /* Allocation alignment */ #endif #define HB_ROUNDOFF (HB_ALIGN-1) /* Used to round up allocation size */ #define HB_FREE 0x00000001 /* Block is free */ #define HB_PREVFREE 0x00000002 /* Previous block is free */ #define HB_ALL_FLAGS (HB_FREE|HB_PREVFREE) #define HB_FLAGS HB_ROUNDOFF /* Mask for all the flags we might use */ #define HB_SIZE (~HB_FLAGS) /* Mask for getting the size */ #if ((HB_FLAGS & (HB_ALL_FLAGS)) != (HB_ALL_FLAGS)) error excessive use of flags bits #endif /* * Note that the least significant bits used for flags (ie lsb of HB_FLAGS) * must be smaller or equal to HB_ROUNDOFF */ typedef struct { ADDR_SIZE Reserve; /* amount of address space reserved for the heap */ ADDR_SIZE Commit; /* of that, how much is actually committed */ ADDR_SIZE Used; /* of that, how much is actually allocated */ ADDR_SIZE MaxUsed; UINT Allocs; /* total number of alloc operations */ } HEAP_STATUS; /* Free block start with the above header and ends with a pointer * to the this header. Used block could be smaller but when freed * is converted to free block. Thus the minimum size of a block is: */ #define MINBLKSIZE ((sizeof(FREEBLK) + HB_ROUNDOFF) & HB_SIZE) /* Note that a structure in helper.c assumes one can store a LISTNODE and * a PTR in the smallest allocated block. */ typedef struct _FLH { /* Free list header */ ADDR_SIZE MaxSize; /* Size of largest block in this list */ FREEBLK Header; /* Pseudo heap header used as list head */ } FLH, * PFLH; /* Heap header */ typedef struct _HEAPINFO { /* Per-heap information */ const struct IHeapVtbl *Vtbl; /* Reserved for IHEAP vtbl */ UINT Sign; /* Signature */ UINT Refs; /* Number of references */ UINT Flags; /* Passed to CreatHeap */ PIHEAP Parent; /* For subheap deletion */ MUTEX Mx; /* Serialize access to the heap. */ HEAP_STATUS Status; /* Reserve, Commit, etc fields */ UINT FreeListCnt; /* Number of free lists */ FLH FreeList[1]; /* Free list heads, actual number == FreeListCnt */ } HEAPINFO, *PHEAPINFO; #define pHP(pHeap) ((PHEAPINFO)(pHeap)) typedef struct _HEAPINFO FirstFitHeap; typedef struct HEAPCOB FirstFitHeapFactory; #include <s_FirstFitHeap_v.c> #include <s_FirstFitHeapFactory_v.c> /* BUGBUG - Allow heap creator specify number of free lists, sizes ? */ #define FREELISTCNT 4 static const ADDR_SIZE FreeSizes[FREELISTCNT] = { 32, 128, 512, (ADDR_SIZE) -1 }; /* Allow for sanity checking via signatures of heap and/or memory blocks */ #ifdef HPDBG const BYTE HeapBlkSign[] = "HEAPBLK"; /* Only sizeof(UINT) bytes are used */ static void SetHeapSign(PHEAPINFO phi); static BOOL ChkHeapSign(PHEAPINFO phi); #if defined(__HAS_LARGE_ADDRESSES) #define SetUsedBlkSign(pblk) #define ChkUsedBlkSign(pblk) (TRUE) #else const BYTE UsedBlkSign[] = "USEDBLK"; /* Only sizeof(UINT) bytes are used */ static void SetUsedBlkSign(PUSEDBLK pblk); static BOOL ChkUsedBlkSign(PUSEDBLK pblk); #endif #else #define SetHeapSign(phi) #define ChkHeapSign(phi) (TRUE) #define SetUsedBlkSign(pblk) #define ChkUsedBlkSign(pblk) (TRUE) #ifdef _MSC_VER #pragma warning(disable:4127) /* conditional expression is constant */ #pragma warning(disable:4702) /* unreachable code */ #endif #endif #define IncUsedCnt(_phi_,_size_) \ { \ (_phi_)->Status.Used += (_size_); \ if ((_phi_)->Status.Used > (_phi_)->Status.MaxUsed) \ (_phi_)->Status.MaxUsed = (_phi_)->Status.Used; \ } #define DecUsedCnt(_phi_,_size_) ((_phi_)->Status.Used -= (_size_)) #ifdef HPDBG /* Functions below set, check heap block signatures. They enable heap * code to work from both user, kernel modes. Also, they allow easy * modification of signature implementation. */ static INLINE void SetHeapSign(PHEAPINFO phi) { phi->Sign = * (PUINT) (HeapBlkSign); } static INLINE BOOL ChkHeapSign(PHEAPINFO phi) { /* if phi points to an invalid heap block, then can't trust saved pIPrc, * so don't set error code */ return (phi->Sign == * (PUINT) (HeapBlkSign)); } static INLINE void SetUsedBlkSign(PUSEDBLK pblk) { pblk->Sign = * (PUINT) (UsedBlkSign); } static INLINE BOOL ChkUsedBlkSign(PUSEDBLK pblk) { return (pblk->Sign == * (PUINT) (UsedBlkSign)); } #endif /* The following functions should just be INLINEd for retail builds, * except some unnamed compiler does not understand inlining */ /* InsertBlk inserts free block pointed by pfh item onto the free list, * after free block pointed by pfhprev. */ #define _InsertBlkMacro(_pfh_,_pfhprev_) \ { \ (_pfh_)->pNext = (_pfhprev_)->pNext; \ (_pfh_)->pNext->pPrev = (_pfh_); \ (_pfh_)->pPrev = (_pfhprev_); \ (_pfhprev_)->pNext = (_pfh_); \ } #ifdef HPDBG static INLINE void InsertBlk(PFREEBLK pfh, PFREEBLK pfhprev) { _InsertBlkMacro(pfh,pfhprev); } #else #define InsertBlk _InsertBlkMacro #endif /* RemoveBlk removes free block pointed by pfh from the free list. */ #define _RemoveBlkMacro(_pfh_) \ { \ (_pfh_)->pNext->pPrev = (_pfh_)->pPrev; \ (_pfh_)->pPrev->pNext = (_pfh_)->pNext; \ } #ifdef HPDBG static INLINE void RemoveBlk(PFREEBLK pfh) { _RemoveBlkMacro(pfh); } #else #define RemoveBlk _RemoveBlkMacro #endif /* BlkSize returns the size of the block pointed by ph * Assumes Size field in the same place both in USEDBLK and FREEBLK */ #define _BlkSizeMacro(_ph_) ((_ph_)->Size & HB_SIZE) #ifdef HPDBG static INLINE UINT BlkSize(PUSEDBLK ph) { return _BlkSizeMacro(ph); } #else #define BlkSize _BlkSizeMacro #endif /* SetBlkSize sets the size parameter in a heap header pointed by ph * Assumes Size field in the same place both in USEDBLK and FREEBLK */ #define _SetBlkSizeMacro(_ph_,_size_) \ ((_ph_)->Size = ((_ph_)->Size & HB_FLAGS) | ((_size_) & HB_SIZE)) #ifdef HPDBG static INLINE void SetBlkSize(PUSEDBLK ph, UINT size) { _SetBlkSizeMacro(ph,size); } #else #define SetBlkSize _SetBlkSizeMacro #endif /* RoundBlock returns an appropriate heap block size for a given byte count */ #define ROUNDBLOCK(_size_) \ { \ _size_ = (_size_ + sizeof(USEDBLK) + HB_ROUNDOFF) & HB_SIZE; \ if (_size_ < MINBLKSIZE) \ _size_ = MINBLKSIZE; \ } /* Lock/Unlock functions */ #define _LockHeapMacro(_phi_,_Flags_) \ { \ if (!((_Flags_) & HEAP_NO_SERIALIZE)) \ Mutex_Lock(&(_phi_)->Mx); \ } #define _UnlockHeapMacro(_phi_,_Flags_) \ { \ if (!((_Flags_) & HEAP_NO_SERIALIZE)) \ Mutex_Unlock(&(_phi_)->Mx); \ } #ifdef HPDBG static INLINE void LockHeap(PHEAPINFO phi, UINT Flags) { _LockHeapMacro(phi,Flags); } static INLINE void UnlockHeap(PHEAPINFO phi, UINT Flags) { _UnlockHeapMacro(phi,Flags); } #else #define LockHeap _LockHeapMacro #define UnlockHeap _UnlockHeapMacro #endif PRIVATE UINT CommitHeapMemory(PTR pAddr, UINT Size); PRIVATE SCODE HPFree(IHeap *pHeap, UINT Flags, PTR pMem); PRIVATE SCODE HPValidate(IHeap *pHeap, UINT Flags, PTR pMem); /* Free any released thread stacks. Do not do this in nested calls since * the heap lock may be retaken, resulting in deadlock. */ extern PTR *ppDelayedFree; #define CHECK_DELAYED_FREE(_flags_) {if (*ppDelayedFree && !((_flags_) & HEAP_NO_SERIALIZE)) ppDelayedFree = CheckDelayedFree();} static void FreeBlk(PHEAPINFO phi, PUSEDBLK pblk, ADDR_SIZE size); static UINT CarveBlk(PHEAPINFO phi, PFREEBLK pblk, UINT size, UINT flags); /* *** HPAlloc * * Allocates a heap block of at least Size bytes from the heap pointed * by pHeap. If Flags contains HEAP_ZERO_MEMORY also zero fills the new block. * Returns pointer to the block of memory, NULL if error. */ PRIVATE PTR HPAlloc(IHeap *pHeap, UINT Flags, UINT Size, UINT Alignment) { PHEAPINFO phi; PFLH pfl; PFREEBLK pfh, pend; PUSEDBLK pbh, pendblk; UINT newcommit; INT freesize, fragsize = 0, fragsize2; PTR pbase = NULL, plim; SCODE Error; TRACE_USER_LEAKS(UINT ss = Size;) if (Flags & HEAP_CACHE_ALIGN) Alignment = _DCACHELINESIZE; if (Alignment > 1) { /* Check that it is a power of two */ if ((Alignment-1) & Alignment) { PITHREAD th = CurrentThread(); th->v->SetValue(th, THREAD_VALUE_LAST_ERROR, E_INVALID_PARAMETER); return NULL; } if (Alignment < HB_ALIGN) Alignment = HB_ALIGN; } DPRINT(("HPAlloc: pHeap %x, Flags %x, Size %x\n", (ADDRESS) pHeap, Flags, Size)); phi = (PHEAPINFO) pHeap; Flags |= phi->Flags; CHECK_DELAYED_FREE(Flags); if (!ChkHeapSign(phi)) return NULL; /* Detect really big Sizes here so that we don't have to worry about * rounding up big numbers to 0 */ if (Size >= phi->Status.Reserve) { Error = E_NOT_ENOUGH_MEMORY; goto ErrorExit; } if (Alignment > 1) { /* Need cache-aligned buffer. Calculate minimum amount of * memory to allocate, assuming ideal alignment of free block. * Note: sizeof(USEDBLK) must be integral multiple of HB_ALIGN. */ Size = (((Size + (Alignment-1)) & ~(Alignment-1)) + sizeof(USEDBLK)) & HB_SIZE; while (Size < MINBLKSIZE) { Size += Alignment; } } else { /* Use default allocation alignment. */ ROUNDBLOCK(Size); } LockHeap(phi, Flags); #ifdef HPDBG /* In debugging builds, we validate the entire heap * every so often. This will help catch lingering * heap corruption bugs without too much overhead. */ if ((phi->Status.Allocs++ & 0xf) == 0) HPValidate(pHeap, Flags | HEAP_NO_SERIALIZE, 0); #endif /* Find the first free list header that will contain a block big * enough to satisfy this allocation. * * NOTE: at the cost of heap fragmentation, we could change this * to allocate from the first free list that is guaranteed to * have a block big enough as its first entry. That would * cut down paging on swappable heaps. */ for (pfl = phi->FreeList; Size > pfl->MaxSize; ++pfl); NextFreeList: /* Look for a block big enough for us on the list head returned. * Even if we follow the advice of the NOTE above and pick a list * that will definitely contain a block big enough for us we still * have to do this scan to pass by any free list heads in the * way (they have a size of 0, so we will never try to allocate them). * * We know we have reached the end of the free list when we get to * to the first free list head (since the list is circular). */ pfh = pfl->Header.pNext; /* First real block after a list header */ pend = &(phi->FreeList[0].Header); /* list header (never equals pfh) */ for (; pfh != pend; pfh = pfh->pNext) { /* Use BlkSize(pfh) since the upper 4 bits now have other stuff such as * lock count if it is a moveable memory heap and are unused if it is a * fixed heap. */ if (BlkSize((PUSEDBLK)pfh) >= Size) { if (Alignment > 1) { /* Need aligned block. Set up pointer to start of block, * assuming, for now, that the block will be big enough. */ pbase = (PTR)(((((ADDRESS)(PBYTE)pfh) + sizeof(USEDBLK) + (Alignment-1)) & ~(Alignment-1)) - sizeof(USEDBLK)); /* Make sure that any storage fragment preceding the aligned * block is big enough to be returned to the free list. */ fragsize = ((ADDRESS)(PBYTE)pbase) - ((ADDRESS)(PBYTE)pfh); /* can be negative */ while (fragsize && fragsize < (INT)MINBLKSIZE) { pbase = (PTR)(((PBYTE)pbase) + Alignment); fragsize += Alignment; } /* Verify now that the aligned block itself is big enough. * Note that trailing fragment size fragsize2 can be negative. */ plim = (PTR)(((PBYTE)pbase) + Size); fragsize2 = (ADDRESS)((PBYTE)pfh) + BlkSize((PUSEDBLK)pfh) - ((ADDRESS)(PBYTE)plim); if (fragsize2 && fragsize2 < (INT)MINBLKSIZE) { continue; /* reject this block, resume search */ } /* This block meets the alignment and size requirements. */ if (fragsize) { /* Trim off the fragment that precedes the aligned block. * The fragment will shortly be returned to the free list. */ pfh->Size = CarveBlk(phi, pfh, fragsize, Flags); pfh = (PFREEBLK)pbase; } } break; /* Found a block big enough */ } } if (pfh == pend) { /* No blocks big enough in this free list. Check the next one. */ if (pfl != &phi->FreeList[FREELISTCNT-1]) { pfl++; goto NextFreeList; } /* There are no blocks available of the correct Size. * * Don't grow the heap and return a NULL, unless HEAP_GROWABLE */ if ((Flags & HEAP_GROWABLE) == 0) { EPRINT(("HPAlloc (Thd %x): can't grow heap %x!\n", (ADDRESS) CurrentThread(), (ADDRESS) pHeap)); Error = E_NOT_ENOUGH_MEMORY; goto FreeMutex; } /* NOTE: * In the future we might want to do compaction here, but today * we just grow the heap if there is room. See if growing would * do any good by checking if the last block before the end sentinel * is free and if so adding its size to the amount of uncommitted * memory at the end of the heap. */ /* Sentinel */ pfh = (PFREEBLK) (((PBYTE) phi) + phi->Status.Commit - sizeof(USEDBLK)); /* If the end sentinel is preceded by a free block, set pfh to it, * so our new committed memory will be appended to it. */ if (pfh->Size & HB_PREVFREE) pfh = *(((PFREEBLK *) pfh) - 1); /*fixme for true MINBLKSIZE */ freesize = BlkSize((PUSEDBLK) pfh); if (Alignment > 1) { /* Calculate base address of cache-aligned block. */ pbase = (PTR)(((((ADDRESS)(PBYTE)pfh) + sizeof(USEDBLK) + (Alignment-1)) & ~(Alignment-1)) - sizeof(USEDBLK)); /* Make sure that any storage fragment preceding the aligned * block is big enough to be returned to the free list. */ fragsize = ((ADDRESS)(PBYTE)pbase) - ((ADDRESS)(PBYTE)pfh); /* can be negative */ while (fragsize && fragsize < (INT)MINBLKSIZE) { pbase = (PTR)(((PBYTE)pbase) + Alignment); fragsize += Alignment; } /* Due to alignment constraints, we are unable to use the first * fragsize bytes of the block pointed to by pfh. */ freesize -= fragsize; /* can be negative */ /* Inflate our size requirements just enough to ensure that * the heap-storage fragment that follows our aligned block * will be big enough to be returned to the free list. */ Size += MINBLKSIZE; } /* Assume freesize < Size or that a big enough free block exists, * but was not found while searching the free list * (i.e. internal error) */ #ifdef HPDBG if (freesize >= (INT)Size) { EPRINT(("HEAP: Big enough block exists but not found earlier\n")); DebugBreak(); } #endif if (Size - freesize > phi->Status.Reserve - phi->Status.Commit) { /* Not enough space to grow the heap, return error. * * NOTE: * In the future here we might want to allocate a new non- * contiguous block of memory and stick it onto the end, using * a phoney busy block to mark off the hole (the hole could even * have a negative Size to account for the second piece being lower * than the first!). */ EPRINT(("HPAlloc (Thd %x): no room to grow heap %x!\n", (ADDRESS) CurrentThread(), (ADDRESS) pHeap)); Error = E_NOT_ENOUGH_MEMORY; goto FreeMutex; } /* pfh is now pointing just past the last busy block in the heap * (which may be the very end of the heap). Commit the memory * we need. */ newcommit = CommitHeapMemory(((PBYTE) phi) + phi->Status.Commit, Size - freesize); if (newcommit == 0) { PITHREAD th = CurrentThread(); EPRINT(("HPAlloc (Thd %x): failed commit to grow heap %x!\n", (ADDRESS) CurrentThread(), (ADDRESS) pHeap)); Error = th->v->GetValue(th, THREAD_VALUE_LAST_ERROR); goto FreeMutex; } phi->Status.Commit += newcommit; /* Put a tiny busy heap header at the very end of the heap * so we can free the true last block and mark the following * block as HB_PREVFREE without worrying about falling off the * end of the heap. Give him a Size of 0 so we can also use * him to terminate heap-walking functions. */ pendblk = ((PUSEDBLK) (((PBYTE) phi) + phi->Status.Commit)) - 1; pendblk->Size = 0; SetUsedBlkSign(pendblk); /* If the begining of the block we are allocating of is currently * one the free list, remove it */ if (pfh->Size & HB_FREE) RemoveBlk(pfh); /* About to allocate the chunk of memory pointed to by pfh. Make * sure *pfh contains the new Size of the free block there (after * adding on the new committed chunk). */ pfh->Size = ((ADDRESS)(PBYTE) pendblk) - ((ADDRESS)(PBYTE) pfh); if (Alignment > 1) { Size -= MINBLKSIZE; /* restore actual allocation size */ if (fragsize) { /* Trim off the fragment that precedes the aligned block. * The fragment will shortly be returned to the free list. */ pfh->Size = CarveBlk(phi, pfh, fragsize, Flags); pfh = (PFREEBLK)pbase; } } } pbh = (PUSEDBLK) pfh; pbh->Size = CarveBlk(phi,pfh,Size,Flags); SetUsedBlkSign(pbh); IncUsedCnt(phi,pbh->Size); if (Alignment > 1 && fragsize) { /* An unused storage fragment precedes the cache-aligned block * that we just allocated. Return fragment to free list. */ FreeBlk(phi, (PUSEDBLK)(((PBYTE)pfh) - fragsize), fragsize); } TRACE_USER_LEAKS(if (pHeap == pTheHeap) printf(" alloc %d -> %d @ %x\n", ss, Size, pbh + 1);) UnlockHeap(phi, Flags); return (PTR) (pbh + 1); FreeMutex: UnlockHeap(phi, Flags); ErrorExit: { PITHREAD th = CurrentThread(); th->v->SetValue(th, THREAD_VALUE_LAST_ERROR, Error); } EPRINT(("HPAlloc FAILED f=%x s=%x al=%x\n", Flags, Size, Alignment)); return NULL; } /* *** HPRealloc * * Reallocates the memory block pointed by pMem, in the heap pointed by * pHeap to contain at least NewSize bytes. If NewSize is greater then the * current size and Flags contain HEAP_ZERO_MEMORY zero fills new area. * If Flags doesn't contain HEAP_REALLOC_IN_PLACE_ONLY then the * block's address may change. * Returns pointer to the reallocated block, NULL if error. Note that in * case of failure the original pointer still point to the original block. * As per ANSI specs, if PTR is NULL it should do an Alloc. * As per ANSI specs, if PTR is non null and NewSize is 0 it should do a Free. */ PRIVATE PTR HPRealloc(IHeap *pHeap, UINT Flags, PTR pMem, UINT NewSize, UINT Alignment) { PHEAPINFO phi; PTR pnew; UINT oldsize; INT shrinksize; PFREEBLK pnext; PUSEDBLK pblk; SCODE Error; TRACE_USER_LEAKS(UINT ss = NewSize; PTR oo = pMem;) DPRINT(("HPRealloc: pHeap %x, Flags %x, pMem %x, NewSize %x\n", (ADDRESS) pHeap, Flags, (ADDRESS) pMem, NewSize)); /* ANSI sez.. */ if (pMem == NULL) return HPAlloc(pHeap, Flags, NewSize, Alignment); if (NewSize == 0) return (HPFree(pHeap,0,pMem)) ? NULL : pMem; if (Flags & HEAP_CACHE_ALIGN) Alignment = _DCACHELINESIZE; if (Alignment > 1) { /* Check that it is a power of two */ if ((Alignment-1) & Alignment) { Error = E_INVALID_PARAMETER; goto ErrorExit; } if (Alignment < HB_ALIGN) Alignment = HB_ALIGN; } phi = (PHEAPINFO) pHeap; Flags |= phi->Flags; CHECK_DELAYED_FREE(Flags); if (!ChkHeapSign(phi)) return NULL; /* Detect really big sizes here so that we don't have to worry about * rounding up big numbers to 0 */ if (NewSize >= phi->Status.Reserve) { Error = E_NOT_ENOUGH_MEMORY; goto ErrorExit; } /* Get pointer to block header and determine current size of block. */ pblk = ((PUSEDBLK)pMem)-1; oldsize = BlkSize(pblk); if (Alignment > 1) { /* Check the alignment of the original memory block to make sure * it begins and ends on cache-line boundaries in memory. */ if ((((ADDRESS)(PBYTE)pMem) | (oldsize - sizeof(USEDBLK))) & (Alignment-1)) { Error = E_INVALID_PARAMETER; goto ErrorExit; } /* Calculate new allocation size of cache-aligned memory block. * Note: sizeof(USEDBLK) must be integral multiple of HB_ALIGN. */ NewSize = (((NewSize + (Alignment-1)) & ~(Alignment-1)) + sizeof(USEDBLK)) & HB_SIZE; while (NewSize < MINBLKSIZE) { NewSize += Alignment; } } else { /* Use default allocation alignment. */ ROUNDBLOCK(NewSize); } LockHeap(phi, Flags); if (!ChkUsedBlkSign(pblk)) { Error = E_INVALID_PARAMETER; goto FreeMutex; } shrinksize = oldsize - NewSize; if (shrinksize >= (INT)MINBLKSIZE) { /* This a big enough shrink to carve off the end of the block */ FreeBlk(phi,(PUSEDBLK) (((PBYTE) pblk) + NewSize),shrinksize); SetBlkSize(pblk,NewSize); DecUsedCnt(phi,shrinksize); } else if (shrinksize < 0) { INT minfragsize = 0; /* This is a grow * * See if there is a next door free block big enough for us * grow into so we can realloc in place. * * NOTE: * It is possible that we are realloc'ing the last busy block * in the heap and if so we can grow in place by committing * new pages. This situation is not currently detected or * acted upon. We just allocate a new block and copy in * that case. * * We do not use pnext->Size directly with NewSize - oldsize below, * and instead use BlkSize(pnext), because the upper 4 bits of * the size field is being used for LockCount for Moveable heaps * and is unused for the Fixed Heap. These 4 bits will * affect the outcome of the comparision. */ pnext = (PFREEBLK) (((PBYTE) pblk) + oldsize); if (pnext->Size & HB_FREE) { shrinksize += BlkSize((PUSEDBLK)pnext); } if (Alignment > 1) { /* The allocated block must always begin and end on cache-line * boundaries. Any storage fragment that follows the allocated * block MUST be large enough to be returned to the free list. */ minfragsize = MINBLKSIZE; /* minimum fragment size */ } if (shrinksize && shrinksize < minfragsize) { /* We have to move the object in order to grow it. * Make sure that is ok with the caller first. */ if (!(Flags & HEAP_REALLOC_IN_PLACE_ONLY)) { /* The size we have computed in size includes a heap header. * Remove that since the call to HPAlloc bellow will * also add on a header. */ NewSize -= sizeof(USEDBLK); if (Flags & HEAP_NO_COPY) { /* Caller doesn't care about the contents of the memory * block - just allocate a new chunk and free old one */ HPFree(pHeap,HEAP_NO_SERIALIZE,pMem); pMem = HPAlloc(pHeap,Flags|HEAP_NO_SERIALIZE,NewSize,0); pblk = (PUSEDBLK)pMem - 1; } else { /* Caller cares about his data - allocate a new block * and copy the old stuff into it */ pnew = HPAlloc(pHeap,Flags|HEAP_NO_SERIALIZE,NewSize,0); if (pnew == NULL) { PITHREAD th = CurrentThread(); Error = th->v->GetValue(th, THREAD_VALUE_LAST_ERROR); goto FreeMutex; } memcpy(pnew,pMem,oldsize - sizeof(USEDBLK)); pblk = (PUSEDBLK)pnew - 1; HPFree(pHeap,HEAP_NO_SERIALIZE,pMem); pMem = pnew; } } else { /* Moving of the block is not allowed. Return error. */ Error = E_LOCKED; goto FreeMutex; } } else { /* Grow in place into the following block */ NewSize = oldsize + CarveBlk(phi,pnext,NewSize - oldsize,Flags); SetBlkSize(pblk,NewSize); IncUsedCnt(phi,NewSize - oldsize); } } else { /* This is small enough shrink such that can't create * a new FREEBLK - do nothing */ } TRACE_USER_LEAKS(if (pHeap == pTheHeap) printf(" realloc %x %d -> %d @ %x\n", oo, ss, NewSize, pMem);) UnlockHeap(phi, Flags); return pMem; FreeMutex: UnlockHeap(phi, Flags); ErrorExit: { PITHREAD th = CurrentThread(); th->v->SetValue(th, THREAD_VALUE_LAST_ERROR, Error); } return NULL; } /* ** HPFree * * Free the memory block pointed by pMem, back to the heap pointed * by pHeap. Returns TRUE, FALSE if error. */ PRIVATE SCODE HPFree(IHeap *pHeap, UINT Flags, PTR pMem) { PHEAPINFO phi; PUSEDBLK pblk; UINT size; TRACE_USER_LEAKS(UINT ss;) phi = (PHEAPINFO) pHeap; Flags |= phi->Flags; CHECK_DELAYED_FREE(Flags); if (!ChkHeapSign(phi)) goto BadHeap; /* Check block is within heap boundaries */ pblk = ((PUSEDBLK) pMem) - 1; /* Back up to heap block header */ if ((ADDRESS)pblk < ((ADDRESS)phi + sizeof(HEAPINFO) + sizeof(FLH) * (FREELISTCNT - 1)) || (ADDRESS)pblk >= ((ADDRESS)phi + phi->Status.Commit - sizeof(USEDBLK))) { goto BadHeap; } LockHeap(phi, Flags); if (!ChkUsedBlkSign(pblk)) { goto FreeMutex; } size = BlkSize(pblk); TRACE_USER_LEAKS(ss = size;) DecUsedCnt(phi,size); /* If the previous block is free, coalesce with it. */ if (pblk->Size & HB_PREVFREE) { pblk = (PUSEDBLK) *((PUINT *) pblk - 1); /* Point to prev block */ size += BlkSize(pblk); /* Remove the previous block from the free list so we can re-insert * the combined block in the right place later */ RemoveBlk((PFREEBLK) pblk); } /* Build a free header for the block and insert him on the appropriate * free list. This routine also marks the following block as HB_PREVFREE * and performs coalescing with the following block. */ FreeBlk(phi,pblk,size); TRACE_USER_LEAKS(if (pHeap==pTheHeap) printf(" free %x %d -> %d (%d) @ %x\n", pMem, ss, size, pblk->Size & HB_SIZE, pblk);) UnlockHeap(phi, Flags); return TRUE; FreeMutex: UnlockHeap(phi, Flags); BadHeap: TRACE_USER_LEAKS(printf(" BadFree(%x) !\n", pMem);) DebugBreak(); return E_INVALID_PARAMETER; } /* *** HPSize * * Returns size of chunk of memory pointed by pmem that has been allocated * out of the heap pointed by pHeap. Returns 0 if error. * Note that there is no need to lock the mutex in this call: it doesn't * modify the heap. (It is like using the memory vs eg reallocating). */ PRIVATE ADDR_SIZE HPSize(PIHEAP pHeap, UINT Flags, PTR pMem) { PHEAPINFO phi; PUSEDBLK pblk; UINT size; phi = (PHEAPINFO) pHeap; Flags |= phi->Flags; CHECK_DELAYED_FREE(Flags); if (!ChkHeapSign(phi)) return 0; pblk = ((PUSEDBLK) pMem) - 1; /* Back up to heap block header */ if (!ChkUsedBlkSign(pblk)) { PITHREAD th = CurrentThread(); th->v->SetValue(th, THREAD_VALUE_LAST_ERROR, E_INVALID_PARAMETER); return 0; } size = BlkSize(pblk) - sizeof(USEDBLK); return size; } #ifdef HPDBG static INLINE BOOL ChkBlkAddr(PHEAPINFO phi, PUSEDBLK pblk) { return (((PBYTE)phi <= (PBYTE)pblk) && (PBYTE)pblk < ((PBYTE)phi + phi->Status.Commit)); } static INLINE BOOL ChkBlkSize(UINT Size) { /* There is no point to checking * Size == Size & HB_SIZE * because the BlkSize macro guarantees that this will be true. */ return (MINBLKSIZE <= Size); } #endif /* *** HPValidate * * Validates the heap data structures. */ PRIVATE SCODE HPValidate(PIHEAP pHeap, UINT Flags, PTR pMem) { #ifdef HPDBG PHEAPINFO phi; UINT MinHeapSize; UINT FreeSize, UsedSize, FreeListSize; UINT FreeListCnt; PUSEDBLK pblk, pend; PFREEBLK pcurrf, pprevf, plastf; phi = (PHEAPINFO) pHeap; Flags |= phi->Flags; CHECK_DELAYED_FREE(Flags); LockHeap(phi, Flags); if (pMem != NULL) { /* Check validity of this specific block. */ pblk = ((PUSEDBLK) pMem) - 1; /* Back up to heap block header */ if (!ChkBlkAddr(phi, pblk)) { EPRINT(("HPValidate: pHeap %x pMem %x not in heap\n", (ADDRESS) pHeap, (ADDRESS) pMem)); goto ErrorExit; } if (!ChkUsedBlkSign(pblk)) { EPRINT(("HPValidate: pHeap %x pMem %x bad sign\n", (ADDRESS) pHeap, (ADDRESS) pMem)); goto ErrorExit; } goto GetOut; } /* Pointer is NULL --> Check validity of the entire heap. */ if (!ChkHeapSign(phi)) { goto HeapCorrupted; } /* Walk through entire heap, from low addresses to high addresses, * checking the signature on each block. */ MinHeapSize = sizeof(HEAPINFO) + sizeof(FLH) * (FREELISTCNT - 1); MinHeapSize = (MinHeapSize + HB_ROUNDOFF) & HB_SIZE; pblk = (PUSEDBLK) ((PBYTE)phi + MinHeapSize); pend = (PUSEDBLK) ((PBYTE)phi + phi->Status.Commit) - 1; FreeSize = UsedSize = 0; while (pblk < pend) { UINT Size = BlkSize(pblk); if (!ChkBlkSize(Size)) { printf("HPValidate: pHeap %x bad blk %x size %u\n", (ADDRESS) pHeap, (ADDRESS) pblk, Size); goto HeapCorrupted; } else if (pblk->Size & HB_FREE) { /* Check that the pThis pointer is good * Also, size shouldnt be too large. */ PFREEBLK *ppThis = (PFREEBLK*)((ADDRESS)pblk + Size) - 1; if (((ADDRESS)ppThis >= (ADDRESS)pend) || (*ppThis != (PFREEBLK)pblk)) { printf("HPValidate: pHeap %x bad free blk %x\n", (ADDRESS) pHeap, (ADDRESS) pblk); goto HeapCorrupted; } FreeSize += Size; } else { if (!ChkUsedBlkSign(pblk)) { printf("HPValidate: pHeap %x bad used blk %x\n", (ADDRESS) pHeap, (ADDRESS) pblk); goto HeapCorrupted; } UsedSize += Size; } /* We know Size > 0 because of the ChkBlkSize check, * so there is no danger of an infinite loop here. */ pblk = (PUSEDBLK) ((PBYTE)pblk + Size); } /* Walk through the entire free list, checking pointers. * Use FreeListSize, FreeListCnt to avoid infinite loop. */ pcurrf = plastf = &phi->FreeList[0].Header; pprevf = pcurrf->pPrev; FreeListSize = 0; FreeListCnt = 0; do { UINT Size = BlkSize((PUSEDBLK)pcurrf); if (!ChkBlkAddr(phi, (PUSEDBLK)pcurrf) || (pcurrf->pPrev != pprevf)) { printf("HPValidate: pHeap %x bad free blk %x\n", (ADDRESS) pHeap, (ADDRESS) pcurrf); goto HeapCorrupted; } if (pcurrf->Size & HB_FREE) { /* This is a normal free block, should meet size standards. */ if (!ChkBlkSize(Size)) { printf("HPValidate: pHeap %x bad free blk %x size %u\n", (ADDRESS) pHeap, (ADDRESS) pcurrf, Size); goto HeapCorrupted; } FreeListSize += Size; if (FreeListSize > FreeSize) { printf("HPValidate: pHeap %x free list loop?\n", (ADDRESS) pHeap); goto HeapCorrupted; } } else { /* This is a free list anchor and the size should be zero. */ if (pcurrf->Size != 0) { printf("HPValidate: pHeap %x bad anchor %x size %u\n", (ADDRESS) pHeap, (ADDRESS) pcurrf, Size); goto HeapCorrupted; } if (++FreeListCnt > FREELISTCNT) { printf("HPValidate: pHeap %x free list loop?\n", (ADDRESS) pHeap); goto HeapCorrupted; } } pprevf = pcurrf; pcurrf = pcurrf->pNext; } while (pcurrf != plastf); /* Sizes should agree! */ if ((FreeListCnt != FREELISTCNT) || (FreeSize != FreeListSize) || (UsedSize != phi->Status.Used)) { printf("HPValidate: pHeap %x free %x free list %x used %x phi->Status.Used %x FreeListCnt %u\n", (ADDRESS) pHeap, FreeSize, FreeListSize, UsedSize, phi->Status.Used, FreeListCnt); goto HeapCorrupted; } GetOut: UnlockHeap(phi, Flags); return S_OK; HeapCorrupted: assert(!"HPValidate: corruption detected"); DebugBreak(); ErrorExit: UnlockHeap(phi, Flags); return E_FAIL; #else UnusedParameter(pHeap); UnusedParameter(Flags); UnusedParameter(pMem); return S_OK; #endif } /* *** HPStatus * * Returns status information about this heap. */ PRIVATE SCODE HPStatus(IHeap *pHeap, ADDR_SIZE *pReserve, ADDR_SIZE *pCommit, ADDR_SIZE *pUsed, ADDR_SIZE *pMaxUsed) { PHEAPINFO phi; CHECK_DELAYED_FREE(0); phi = (PHEAPINFO) pHeap; if (!ChkHeapSign(phi)) return E_INVALID_PARAMETER; if (pReserve) *pReserve = phi->Status.Reserve; if (pCommit) *pCommit = phi->Status.Commit; if (pUsed) *pUsed = phi->Status.Used; if (pMaxUsed) { do { *pMaxUsed = phi->Status.MaxUsed; /* BUGBUG Replace with new AtomicCmpAndSwapAddress() */ /* BUGBUG Replace with new AtomicCmpAndSwapAddress() */ } while (!AtomicCmpAndSwap((UINT*) &phi->Status.MaxUsed, (UINT) *pMaxUsed, (UINT) phi->Status.Used)); } return NO_ERROR; } /* *** HPExtract * * Allocates a memory block from the heap pointed by pHeap. This routine * is similar to Alloc(), but a fourth argument, pMem, has been added. * The allocated block must contain the Size bytes of memory that begin * at address pMem, but the block may contain additional bytes. If Flags * contains HEAP_ZERO_MEMORY, the routine also zero fills the new block. * If the function is successful, it returns a pointer to the block; * otherwise, it returns NULL to indicate an error. The returned pointer * may not always be precisely equal to pMem; it may be less than pMem by * some number of bytes. The block can later be freed by calling Free(). */ PRIVATE PTR HPExtract(PIHEAP pHeap, UINT Flags, PTR pMem, UINT Size) { PHEAPINFO phi; PFLH pfl; PFREEBLK pfh, pend; PUSEDBLK pbh; UINT excess; SCODE Error; DPRINT(("HeapUse: pHeap %x, Flags %x, pMem %x, Size %x\n", (ADDRESS) pHeap, Flags, (ADDRESS) pMem, Size)); phi = (PHEAPINFO) pHeap; Flags |= phi->Flags; CHECK_DELAYED_FREE(Flags); if (!ChkHeapSign(phi)) return NULL; /* Detect really big Sizes here so that we don't have to worry about * rounding up big numbers to 0 */ if (Size >= phi->Status.Reserve) { Error = E_NOT_ENOUGH_MEMORY; goto ErrorExit2; } /* Adjust args pMem and Size to make room for free-block header * and trailer fields. This will leave the Size bytes beginning * at pMem completely unaltered (in case they already contain data * that must be preserved). (But not if Flags&HEAP_ZERO_MEMORY.) */ pMem = (PTR)((PFREEBLK)pMem - 1); Size += sizeof(FREEBLK); /* Adjust pMem and Size to conform to heap's block-alignment rules. */ Size += (ADDRESS)(PBYTE)pMem & HB_ROUNDOFF; pMem = (PTR)((ADDRESS)(PBYTE)pMem & ~HB_ROUNDOFF); Size = (Size + HB_ROUNDOFF) & ~HB_ROUNDOFF; if (Size < MINBLKSIZE) { Size = MINBLKSIZE; } LockHeap(phi, Flags); /* Find the first free list header that will contain a block big * enough to satisfy this allocation. */ for (pfl = phi->FreeList; Size > pfl->MaxSize; ++pfl); /* Look for the block that contains the starting address pMem. * We know we have reached the end of the free list when we get to * to the first free list head (since the list is circular). */ pfh = pfl->Header.pNext; /* First real block after a list header */ pend = &(phi->FreeList[0].Header); /* list header (never equals pfh) */ for (; pfh != pend; pfh = pfh->pNext) { /* * Use BlkSize(pfh) since the upper 4 bits now have other stuff * such as lock count if it is a moveable memory heap and are * unused if it is a fixed heap. */ if ((PTR)pfh <= pMem && (PBYTE)pMem < (PBYTE)pfh + BlkSize((PUSEDBLK)pfh)) { /* We found the block containing the start address pMem, but * is it big enough? Let's break out of the loop and find out. */ break; } } if (pfh == pend) { /* * The block containing address pMem is not in the free list. */ EPRINT(("HeapUse (Thd %x): can't find block in %x!\n", (ADDRESS) CurrentThread(), (ADDRESS) pHeap)); Error = E_NOT_ENOUGH_MEMORY; goto FreeMutex2; } /* Is free block containing pMem big enough to satisfy request? */ if ((PBYTE)pMem + Size > (PBYTE)pfh + BlkSize((PUSEDBLK)pfh)) { /* * No, the block starting at pMem is not big enough. */ Error = E_NOT_ENOUGH_MEMORY; goto FreeMutex2; } /* Determine whether the free block pointed to by pfh contains any * excess storage preceding our block's start address, pMem. */ excess = (ADDRESS)(PBYTE)pMem - (ADDRESS)(PBYTE)pfh; if (excess >= MINBLKSIZE) { /* Trim the excess bytes from the beginning of the block * so they can be returned to the free list later. */ excess = CarveBlk(phi, pfh, excess, Flags); assert(excess == (UINT)((ADDRESS)(PBYTE)pMem - (ADDRESS)(PBYTE)pfh)); } pbh = (PUSEDBLK)pMem; pbh->Size = CarveBlk(phi, (PFREEBLK)pbh, Size, Flags); SetUsedBlkSign(pbh); IncUsedCnt(phi, pbh->Size); /* Return any excess bytes to the free list now. */ if (excess >= MINBLKSIZE) { FreeBlk(phi, (PUSEDBLK)pfh, excess); } UnlockHeap(phi, Flags); return (PTR) (pbh + 1); FreeMutex2: UnlockHeap(phi, Flags); ErrorExit2: { PITHREAD th = CurrentThread(); th->v->SetValue(th, THREAD_VALUE_LAST_ERROR, Error); } return NULL; } /* *** Constructor: HeapCreate * * Creates heap from a block of memory. pmem points to a block of memory * in the appropriate address space to be used. InitSize is the number of * bytes already commited at the beginning of memory block. MaxSize is * total number of bytes in memory block. Flags passes HEAP_ZERO_MEMORY etc. * Returns pointer to the heap, NULL if failed. * */ SCODE FirstFitHeapFactoryCreate( PIHEAPFACTORY iThis, ADDRESS Mem, UINT Flags, ADDR_SIZE InitSize, ADDR_SIZE MaxSize, /*out*/ PIHEAP *ppHeap) { PHEAPINFO phi; PFLH pfl, pfle; const ADDR_SIZE *psizes; PUSEDBLK pfirst, pendblk; UINT MinHeapSize; SCODE Error; CHECK_DELAYED_FREE(Flags); Flags |= HEAP_GROWABLE; DPRINT(("Enter CreatHeap Mem %08x, InitSize %08x, MaxSize %08x, Flags %08x\n",Mem,InitSize,MaxSize,Flags)); /* Make sure that heap base address is properly aligned. */ Mem = (ADDRESS)((Mem + HB_ROUNDOFF) & ~HB_ROUNDOFF); assert(Mem != 0); assert((Mem & HB_ROUNDOFF) == 0); /* Round the passed in values to heap granularity * Size must be rounded DOWN or they might conflict * with something allocated after this heap */ InitSize &= HB_SIZE; MaxSize &= HB_SIZE; /* Calculate minimum heap size */ MinHeapSize = sizeof(HEAPINFO) + sizeof(FLH) * (FREELISTCNT - 1); /* Remember where the first block will start */ MinHeapSize = (MinHeapSize + HB_ROUNDOFF) & HB_SIZE; pfirst = (PUSEDBLK) (PBYTE) (Mem + MinHeapSize); /* Account for terminating fake used block, Initial free block */ MinHeapSize += (sizeof(USEDBLK) + MINBLKSIZE); /* Make sure the block passed in is big enough to hold a heap, * committed size less or equal reserved size. */ if (MaxSize < MinHeapSize || MaxSize < InitSize) { /* Reserved block too small or * commit size greater then reserved size. */ Error = E_INVALID_PARAMETER; goto ErrorExit; } /* Commit enough space at the beginning of the heap to hold a * HEAPINFO structure and a minimal free list. */ if (InitSize < MinHeapSize) { InitSize = CommitHeapMemory((PTR) Mem,MinHeapSize); if (InitSize == 0) { PITHREAD th = CurrentThread(); Error = th->v->GetValue(th, THREAD_VALUE_LAST_ERROR); goto ErrorExit; } } DPRINT(("CreatHeap before HEAPINFO initialization\n")); /* Initialize HEAPINFO structure (per-heap information). */ phi = (PHEAPINFO) (PBYTE) Mem; memset(phi, 0, sizeof(*phi)); phi->Vtbl = &FirstFitHeapVtbl; SetHeapSign(phi); phi->Refs = 1; phi->Flags = Flags; phi->Status.Reserve = MaxSize; phi->Status.Commit = InitSize; phi->Status.Used = 0; phi->Status.MaxUsed = 0; phi->Status.Allocs = 0; DPRINT(("CreatHeap after HEAPINFO initialization\n")); Mutex_Init(&phi->Mx); /* Initialize the free list heads. * In the future we might want to have the user pass in the * size of the free lists he would like (also their number), * but for now just copy them from the static list. * Notice that enough space has been reserved at the end of HEAPINFO * (and before the mutex if any) for the actual number of entries * * In fact there is one doubley linked circular list with several * anchors (list heads) in it. Free blocks are kept after the anchor * with the largest size filed that still is smaller then their sizes. * Anchors are in the free list but don't have the HB_FREE bit set. */ phi->FreeListCnt = FREELISTCNT; pfl = phi->FreeList; pfle = pfl + phi->FreeListCnt; psizes = FreeSizes; for (; pfl < pfle; ++pfl, ++psizes) { pfl->MaxSize = *psizes; pfl->Header.Size = 0; /* Note that first, last links are not set correctly */ pfl->Header.pNext = &((pfl + 1)->Header); pfl->Header.pPrev = &((pfl - 1)->Header); } /* Make the list circular by fusing the beginning and the end */ --pfl; phi->FreeList[0].Header.pPrev = &(pfl->Header); pfl->Header.pNext = &(phi->FreeList[0].Header); /* Put a tiny busy heap header at the very end of the heap * so we can free the true last block and mark the following (last) * block as HB_PREVFREE without worrying about falling off the * end of the heap. Give him a size of 0 so we can also use * him to terminate heap-walking functions. */ pendblk = ((PUSEDBLK) ((PBYTE)Mem + InitSize)) - 1; pendblk->Size = 0; SetUsedBlkSign(pendblk); /* Pretend all unused memory is a big used block and then * free it to build our initial free list. Note that FreeBlk() * doesn't check for block validity; that is why this works. * Also MinHeapSize includes reserve for one free block, acount for it. */ FreeBlk(phi,pfirst,(ADDRESS)(PBYTE)pendblk - (ADDRESS)(PBYTE)pfirst); DPRINT(("Exit CreatHeap\n")); *ppHeap = (PIHEAP) Mem; return S_OK; ErrorExit: EPRINT(("Error exit CreatHeap\n")); return Error; } PRIVATE SCODE HPCreateHeap(PIHEAP iThis, UINT Flags, UINT InitialSize, UINT MaxSize, PIHEAP *ppHeap) { SCODE sc; PIHEAP NewHeap; PHEAPINFO phi; PTR Mem = iThis->v->Alloc(iThis, Flags, MaxSize, 0); if (!Mem) return E_NOT_ENOUGH_MEMORY; sc = FirstFitHeapFactoryCreate(NULL, (ADDRESS) Mem, Flags, InitialSize, MaxSize, &NewHeap); if (FAILED(sc)) { iThis->v->Free(iThis, Flags, Mem); return sc; } phi = (PHEAPINFO) NewHeap; phi->Parent = iThis; iThis->v->AddRef(iThis); *ppHeap = NewHeap; return S_OK; } /* This routine commits, sets RW access rights to a chunk of reserved * address space in the current process address space. * BUGBUG Implement for real. */ PRIVATE UINT CommitHeapMemory(PTR pAddr, UINT Size) { UnusedParameter(pAddr); return Size; } /* This routine inserts a block of memory on the free list with no * checking for block validity. It handles coalescing with the * following block but not the previous one. The block must also * be big enough to hold a free header. The heap semaphore must * be taken already. Any existing header information is ignored and * overwritten. This routine also marks the following block as HB_PREVFREE. */ static void FreeBlk(PHEAPINFO phi, PUSEDBLK pblk, ADDR_SIZE size) { PFLH pfl; PFREEBLK pfree, pnext; pfree = (PFREEBLK) pblk; #if defined(_DEBUG) && 0 /* Overwrite the contents of the old block, to help detect bugs. */ memset((void *)(pfree + 1), 0xCC, size - sizeof(FREEBLK)); #endif /* If the following block is free, coalesce with it. * Assume that size doesn't have HB_* bits set */ pnext = (PFREEBLK) ((PBYTE) pfree + size); if (pnext->Size & HB_FREE) { size += BlkSize((PUSEDBLK) pnext); /* Remove the following block from the free list. We will insert * the combined block in the right place later */ RemoveBlk(pnext); pnext = (PFREEBLK) ((PBYTE) pfree + size); /* Recompute */ } /* Point the last UINT of the new free block to its header and * mark the following block as HB_PREVFREE; * NB: This is why MINBLKSIZE accounts for an extra PFREEBLK */ *((PFREEBLK *) pnext - 1) = (PFREEBLK) pblk; /*fixme for true MINBLKSIZE */ pnext->Size |= HB_PREVFREE; /* Find the appropriate free list to insert the block on. * The last free list node should have a size of(ADDR_SIZE)-1 so don't have * to count to make sure we don't fall off the end of the list heads. */ for (pfl = phi->FreeList; size > pfl->MaxSize; ++pfl); /* Insert the block on the free list just after the list head and * mark the header as free */ pfree->Size = size | HB_FREE; InsertBlk(pfree,&(pfl->Header)); } #if defined(h8) && defined(__RENESAS__) /* To avoid Renesas compiler bug referencing wrong address for flags arg. */ #pragma option nooptimize #endif /* This routine carves off a chunk from the top of a free block. * * This is a low level worker routine and several very specific * entry conditions must be true: * * The free block is valid. * The free block is at least as big as the chunk you want to carve. * The heap mutex is taken. * * No header is created for the carved-off piece. * * phi points to base of heap. pblk points to header of free block to * carve from. size is size of block to carve out. flags may contain * HEAP_ZERO_MEMORY. Returns count of bytes in carved off block (may differ * from size if free block wasn't big enough to make a new free block * from its end). */ static UINT CarveBlk(PHEAPINFO phi, PFREEBLK pblk, UINT size, UINT flags) { ADDR_SIZE blksize = BlkSize((PUSEDBLK) pblk); /* Remove the block from the free list if it is on it * (it will not be on the free list if it was created by * growing the heap). */ if (pblk->Size & HB_FREE) RemoveBlk(pblk); /* Take it off of free list */ if (blksize >= size + MINBLKSIZE) { /* The block is too big, carve off the end into a new free block. */ FreeBlk(phi,(PUSEDBLK) ((PBYTE) pblk + size),blksize - size); } else { /* We are using the whole free block for our purposes. * Clear the HB_PREVFREE bit in the following block * (we don't really have to do this if the following block * is free, but it is faster to do it than to check it) */ size = blksize; ((PUSEDBLK) ((PBYTE) pblk + size))->Size &= ~HB_PREVFREE; } /* Zero-fill the block if requested and return */ if (flags & HEAP_ZERO_MEMORY) memset(pblk,0,size); return size; } #if defined(h8) && defined(__RENESAS__) #pragma option #endif /* * Exported methods */ PRIVATE SCODE FirstFitHeapDestroy(IUnknown *iThis) { PHEAPINFO phi = (PHEAPINFO) iThis; if (phi->Parent) { PIHEAP Parent = phi->Parent; Parent->v->Free(Parent,0,phi); Parent->v->Release(Parent); } return S_OK; } PRIVATE UINT HPAddRef(PIHEAP pThis) { PHEAPINFO phi = (PHEAPINFO) pThis; return AtomicInc(&phi->Refs); } PRIVATE UINT HPRelease(PIHEAP pThis) { PHEAPINFO phi = (PHEAPINFO) pThis; UINT newrefs; newrefs = AtomicDec(&phi->Refs); if (newrefs == 0) FirstFitHeapDestroy((IUnknown *) phi); return newrefs; } PRIVATE SCODE HPQueryInterface(PIHEAP pThis, REFIID pIid, void* *ppUnk) { return GenericQueryInterface((IUnknown *)pThis,pIid,ppUnk,&IID_IHeap); } PRIVATE struct HEAPCOB FirstFitHeapCobObject = { &FirstFitHeapFactoryVtbl, 1 }; PIUNKNOWN FirstFitHeapCobMain(void) { return (PIUNKNOWN) &FirstFitHeapCobObject; }