home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Tricks of the Windows Gam…ming Gurus (2nd Edition)
/
Disc2.iso
/
vc98
/
crt
/
src
/
sbheap.c
< prev
next >
Wrap
C/C++ Source or Header
|
1998-06-17
|
51KB
|
1,426 lines
/***
*sbheap.c - Small-block heap code
*
* Copyright (c) 1996-1998, Microsoft Corporation. All rights reserved.
*
*Purpose:
* Core code for small-block heap.
*
*******************************************************************************/
#include <stddef.h>
#include <stdlib.h>
#include <string.h>
#include <winheap.h>
#include <windows.h>
size_t __sbh_threshold = MAX_ALLOC_DATA_SIZE;
PHEADER __sbh_pHeaderList; // pointer to list start
PHEADER __sbh_pHeaderScan; // pointer to list rover
int __sbh_sizeHeaderList; // allocated size of list
int __sbh_cntHeaderList; // count of entries defined
PHEADER __sbh_pHeaderDefer;
int __sbh_indGroupDefer;
/*
* Prototypes for user functions.
*/
size_t __cdecl _get_sbh_threshold(void);
int __cdecl _set_sbh_threshold(size_t);
void DumpEntry(char *, int *);
/***
*size_t _get_sbh_threshold() - return small-block threshold
*
*Purpose:
* Return the current value of __sbh_threshold
*
*Entry:
* None.
*
*Exit:
* See above.
*
*Exceptions:
*
*******************************************************************************/
size_t __cdecl _get_sbh_threshold (void)
{
return __sbh_threshold;
}
/***
*int _set_sbh_threshold(threshold) - set small-block heap threshold
*
*Purpose:
* Set the upper limit for the size of an allocation which will be
* supported from the small-block heap.
*
*Entry:
* size_t threshold - proposed new value for __sbh_theshold
*
*Exit:
* Returns 1 if successful. Returns 0 if threshold was too big.
*
*Exceptions:
*
*******************************************************************************/
int __cdecl _set_sbh_threshold (size_t threshold)
{
// test against maximum value - if too large, return error
if (threshold > MAX_ALLOC_DATA_SIZE)
return 0;
// set the threshold value
__sbh_threshold = threshold;
return 1;
}
/***
*int __sbh_heap_init() - set small-block heap threshold
*
*Purpose:
* Allocate space for initial header list and init variables.
*
*Entry:
* None.
*
*Exit:
* Returns 1 if successful. Returns 0 if initialization failed.
*
*Exceptions:
*
*******************************************************************************/
int __cdecl __sbh_heap_init (void)
{
if (!(__sbh_pHeaderList = HeapAlloc(_crtheap, 0, 16 * sizeof(HEADER))))
return FALSE;
__sbh_pHeaderScan = __sbh_pHeaderList;
__sbh_pHeaderDefer = NULL;
__sbh_cntHeaderList = 0;
__sbh_sizeHeaderList = 16;
return TRUE;
}
/***
*PHEADER *__sbh_find_block(pvAlloc) - find block in small-block heap
*
*Purpose:
* Determine if the specified allocation block lies in the small-block
* heap and, if so, return the header to be used for the block.
*
*Entry:
* void * pvBlock - pointer to block to be freed
*
*Exit:
* If successful, a pointer to the header to use is returned.
* If unsuccessful, NULL is returned.
*
*Exceptions:
*
*******************************************************************************/
PHEADER __cdecl __sbh_find_block (void * pvAlloc)
{
PHEADER pHeaderLast = __sbh_pHeaderList + __sbh_cntHeaderList;
PHEADER pHeader;
unsigned int offRegion;
// scan through the header list to determine if entry
// is in the region heap data reserved address space
pHeader = __sbh_pHeaderList;
while (pHeader < pHeaderLast)
{
offRegion = (unsigned int)pvAlloc - (unsigned int)pHeader->pHeapData;
if (offRegion < BYTES_PER_REGION)
return pHeader;
pHeader++;
}
return NULL;
}
#ifdef _DEBUG
/***
*int __sbh_verify_block(pHeader, pvAlloc) - verify pointer in sbh
*
*Purpose:
* Test if pointer is valid within the heap header given.
*
*Entry:
* pHeader - pointer to HEADER where entry should be
* pvAlloc - pointer to test validity of
*
*Exit:
* Returns 1 if pointer is valid, else 0.
*
*Exceptions:
*
*******************************************************************************/
int __cdecl __sbh_verify_block (PHEADER pHeader, void * pvAlloc)
{
unsigned int indGroup;
unsigned int offRegion;
// calculate region offset to determine the group index
offRegion = (unsigned int)pvAlloc - (unsigned int)pHeader->pHeapData;
indGroup = offRegion / BYTES_PER_GROUP;
// return TRUE if:
// group is committed (bit in vector cleared) AND
// pointer is at paragraph boundary AND
// pointer is not at start of page
return (!(pHeader->bitvCommit & (0x80000000UL >> indGroup))) &&
(!(offRegion & 0xf)) &&
(offRegion & (BYTES_PER_PAGE - 1));
}
#endif /* _DEBUG */
/***
*void __sbh_free_block(preg, ppage, pmap) - free block
*
*Purpose:
* Free the specified block from the small-block heap.
*
*Entry:
* pHeader - pointer to HEADER of region to free memory
* pvAlloc - pointer to memory to free
*
*Exit:
* No return value.
*
*Exceptions:
*
*******************************************************************************/
void __cdecl __sbh_free_block (PHEADER pHeader, void * pvAlloc)
{
PREGION pRegion;
PGROUP pGroup;
PENTRY pHead;
PENTRY pEntry;
PENTRY pNext;
PENTRY pPrev;
void * pHeapDecommit;
int sizeEntry;
int sizeNext;
int sizePrev;
unsigned int indGroup;
unsigned int indEntry;
unsigned int indNext;
unsigned int indPrev;
unsigned int offRegion;
// region is determined by the header
pRegion = pHeader->pRegion;
// use the region offset to determine the group index
offRegion = (unsigned int)pvAlloc - (unsigned int)pHeader->pHeapData;
indGroup = offRegion / BYTES_PER_GROUP;
pGroup = &pRegion->grpHeadList[indGroup];
// get size of entry - decrement value since entry is allocated
pEntry = (PENTRY)((char *)pvAlloc - sizeof(int));
sizeEntry = pEntry->sizeFront - 1;
// point to next entry to get its size
pNext = (PENTRY)((char *)pEntry + sizeEntry);
sizeNext = pNext->sizeFront;
// get size from end of previous entry
sizePrev = ((PENTRYEND)((char *)pEntry - sizeof(int)))->sizeBack;
// test if next entry is free by an even size value
if ((sizeNext & 1) == 0)
{
// free next entry - disconnect and add its size to sizeEntry
// determine index of next entry
indNext = (sizeNext >> 4) - 1;
if (indNext > 63)
indNext = 63;
// test entry is sole member of bucket (next == prev),
if (pNext->pEntryNext == pNext->pEntryPrev)
{
// clear bit in group vector, decrement region count
// if region count is now zero, clear bit in header
// entry vector
if (indNext < 32)
{
pRegion->bitvGroupHi[indGroup] &= ~(0x80000000L >> indNext);
if (--pRegion->cntRegionSize[indNext] == 0)
pHeader->bitvEntryHi &= ~(0x80000000L >> indNext);
}
else
{
pRegion->bitvGroupLo[indGroup] &=
~(0x80000000L >> (indNext - 32));
if (--pRegion->cntRegionSize[indNext] == 0)
pHeader->bitvEntryLo &= ~(0x80000000L >> (indNext - 32));
}
}
// unlink entry from list
pNext->pEntryPrev->pEntryNext = pNext->pEntryNext;
pNext->pEntryNext->pEntryPrev = pNext->pEntryPrev;
// add next entry size to freed entry size
sizeEntry += sizeNext;
}
// compute index of free entry (plus next entry if it was free)
indEntry = (sizeEntry >> 4) - 1;
if (indEntry > 63)
indEntry = 63;
// test if previous entry is free by an even size value
if ((sizePrev & 1) == 0)
{
// free previous entry - add size to sizeEntry and
// disconnect if index changes
// get pointer to previous entry
pPrev = (PENTRY)((char *)pEntry - sizePrev);
// determine index of previous entry
indPrev = (sizePrev >> 4) - 1;
if (indPrev > 63)
indPrev = 63;
// add previous entry size to sizeEntry and determine
// its new index
sizeEntry += sizePrev;
indEntry = (sizeEntry >> 4) - 1;
if (indEntry > 63)
indEntry = 63;
// if index changed due to coalesing, reconnect to new size
if (indPrev != indEntry)
{
// disconnect entry from indPrev
// test entry is sole member of bucket (next == prev),
if (pPrev->pEntryNext == pPrev->pEntryPrev)
{
// clear bit in group vector, decrement region count
// if region count is now zero, clear bit in header
// entry vector
if (indPrev < 32)
{
pRegion->bitvGroupHi[indGroup] &=
~(0x80000000L >> indPrev);
if (--pRegion->cntRegionSize[indPrev] == 0)
pHeader->bitvEntryHi &= ~(0x80000000L >> indPrev);
}
else
{
pRegion->bitvGroupLo[indGroup] &=
~(0x80000000L >> (indPrev - 32));
if (--pRegion->cntRegionSize[indPrev] == 0)
pHeader->bitvEntryLo &=
~(0x80000000L >> (indPrev - 32));
}
}
// unlink entry from list
pPrev->pEntryPrev->pEntryNext = pPrev->pEntryNext;
pPrev->pEntryNext->pEntryPrev = pPrev->pEntryPrev;
}
// set pointer to connect it instead of the free entry
pEntry = pPrev;
}
// test if previous entry was free with an index change or allocated
if (!((sizePrev & 1) == 0 && indPrev == indEntry))
{
// connect pEntry entry to indEntry
// add entry to the start of the bucket list
pHead = (PENTRY)((char *)&pGroup->listHead[indEntry] - sizeof(int));
pEntry->pEntryNext = pHead->pEntryNext;
pEntry->pEntryPrev = pHead;
pHead->pEntryNext = pEntry;
pEntry->pEntryNext->pEntryPrev = pEntry;
// test entry is sole member of bucket (next == prev),
if (pEntry->pEntryNext == pEntry->pEntryPrev)
{
// if region count was zero, set bit in region vector
// set bit in header entry vector, increment region count
if (indEntry < 32)
{
if (pRegion->cntRegionSize[indEntry]++ == 0)
pHeader->bitvEntryHi |= 0x80000000L >> indEntry;
pRegion->bitvGroupHi[indGroup] |= 0x80000000L >> indEntry;
}
else
{
if (pRegion->cntRegionSize[indEntry]++ == 0)
pHeader->bitvEntryLo |= 0x80000000L >> (indEntry - 32);
pRegion->bitvGroupLo[indGroup] |= 0x80000000L >>
(indEntry - 32);
}
}
}
// adjust the entry size front and back
pEntry->sizeFront = sizeEntry;
((PENTRYEND)((char *)pEntry + sizeEntry -
sizeof(ENTRYEND)))->sizeBack = sizeEntry;
// one less allocation in group - test if empty
if (--pGroup->cntEntries == 0)
{
// if a group has been deferred, free that group
if (__sbh_pHeaderDefer)
{
// if now zero, decommit the group data heap
pHeapDecommit = (void *)((char *)__sbh_pHeaderDefer->pHeapData +
__sbh_indGroupDefer * BYTES_PER_GROUP);
VirtualFree(pHeapDecommit, BYTES_PER_GROUP, MEM_DECOMMIT);
// set bit in commit vector
__sbh_pHeaderDefer->bitvCommit |=
0x80000000 >> __sbh_indGroupDefer;
// clear entry vector for the group and header vector bit
// if needed
__sbh_pHeaderDefer->pRegion->bitvGroupLo[__sbh_indGroupDefer] = 0;
if (--__sbh_pHeaderDefer->pRegion->cntRegionSize[63] == 0)
__sbh_pHeaderDefer->bitvEntryLo &= ~0x00000001L;
// if commit vector is the initial value,
// remove the region if it is not the last
if (__sbh_pHeaderDefer->bitvCommit == BITV_COMMIT_INIT)
{
// release the address space for heap data
VirtualFree(__sbh_pHeaderDefer->pHeapData, 0, MEM_RELEASE);
// free the region memory area
HeapFree(_crtheap, 0, __sbh_pHeaderDefer->pRegion);
// remove entry from header list by copying over
memmove((void *)__sbh_pHeaderDefer,
(void *)(__sbh_pHeaderDefer + 1),
(int)(__sbh_pHeaderList + __sbh_cntHeaderList) -
(int)(__sbh_pHeaderDefer + 1));
__sbh_cntHeaderList--;
// if pHeader was after the one just removed, adjust it
if (pHeader > __sbh_pHeaderDefer)
pHeader--;
// initialize scan pointer to start of list
__sbh_pHeaderScan = __sbh_pHeaderList;
}
}
// defer the group just freed
__sbh_pHeaderDefer = pHeader;
__sbh_indGroupDefer = indGroup;
}
}
/***
*void * __sbh_alloc_block(intSize) - allocate a block
*
*Purpose:
* Allocate a block from the small-block heap, the specified number of
* bytes in size.
*
*Entry:
* intSize - size of the allocation request in bytes
*
*Exit:
* Returns a pointer to the newly allocated block, if successful.
* Returns NULL, if failure.
*
*Exceptions:
*
*******************************************************************************/
void * __cdecl __sbh_alloc_block (int intSize)
{
PHEADER pHeaderLast = __sbh_pHeaderList + __sbh_cntHeaderList;
PHEADER pHeader;
PREGION pRegion;
PGROUP pGroup;
PENTRY pEntry;
PENTRY pHead;
BITVEC bitvEntryLo;
BITVEC bitvEntryHi;
BITVEC bitvTest;
int sizeEntry;
int indEntry;
int indGroupUse;
int sizeNewFree;
int indNewFree;
// add 8 bytes entry overhead and round up to next para size
sizeEntry = (intSize + 2 * sizeof(int) + (BYTES_PER_PARA - 1))
& ~(BYTES_PER_PARA - 1);
// determine index and mask from entry size
// Hi MSB: bit 0 size: 1 paragraph
// bit 1 2 paragraphs
// ... ...
// bit 30 31 paragraphs
// bit 31 32 paragraphs
// Lo MSB: bit 0 size: 33 paragraph
// bit 1 34 paragraphs
// ... ...
// bit 30 63 paragraphs
// bit 31 64+ paragraphs
indEntry = (sizeEntry >> 4) - 1;
if (indEntry < 32)
{
bitvEntryHi = 0xffffffffUL >> indEntry;
bitvEntryLo = 0xffffffffUL;
}
else
{
bitvEntryHi = 0;
bitvEntryLo = 0xffffffffUL >> (indEntry - 32);
}
// scan header list from rover to end for region with a free
// entry with an adequate size
pHeader = __sbh_pHeaderScan;
while (pHeader < pHeaderLast)
{
if ((bitvEntryHi & pHeader->bitvEntryHi) |
(bitvEntryLo & pHeader->bitvEntryLo))
break;
pHeader++;
}
// if no entry, scan from list start up to the rover
if (pHeader == pHeaderLast)
{
pHeader = __sbh_pHeaderList;
while (pHeader < __sbh_pHeaderScan)
{
if ((bitvEntryHi & pHeader->bitvEntryHi) |
(bitvEntryLo & pHeader->bitvEntryLo))
break;
pHeader++;
}
// no free entry exists, scan list from rover to end
// for available groups to commit
if (pHeader == __sbh_pHeaderScan)
{
while (pHeader < pHeaderLast)
{
if (pHeader->bitvCommit)
break;
pHeader++;
}
// if no available groups, scan from start to rover
if (pHeader == pHeaderLast)
{
pHeader = __sbh_pHeaderList;
while (pHeader < __sbh_pHeaderScan)
{
if (pHeader->bitvCommit)
break;
pHeader++;
}
// if no available groups, create a new region
if (pHeader == __sbh_pHeaderScan)
if (!(pHeader = __sbh_alloc_new_region()))
return NULL;
}
// commit a new group in region associated with pHeader
if ((pHeader->pRegion->indGroupUse =
__sbh_alloc_new_group(pHeader)) == -1)
return NULL;
}
}
__sbh_pHeaderScan = pHeader;
pRegion = pHeader->pRegion;
indGroupUse = pRegion->indGroupUse;
// determine the group to allocate from
if (indGroupUse == -1 ||
!((bitvEntryHi & pRegion->bitvGroupHi[indGroupUse]) |
(bitvEntryLo & pRegion->bitvGroupLo[indGroupUse])))
{
// preferred group could not allocate entry, so
// scan through all defined vectors
indGroupUse = 0;
while (!((bitvEntryHi & pRegion->bitvGroupHi[indGroupUse]) |
(bitvEntryLo & pRegion->bitvGroupLo[indGroupUse])))
indGroupUse++;
}
pGroup = &pRegion->grpHeadList[indGroupUse];
// determine bucket index
indEntry = 0;
// get high entry intersection - if zero, use the lower one
if (!(bitvTest = bitvEntryHi & pRegion->bitvGroupHi[indGroupUse]))
{
indEntry = 32;
bitvTest = bitvEntryLo & pRegion->bitvGroupLo[indGroupUse];
}
while ((int)bitvTest >= 0)
{
bitvTest <<= 1;
indEntry++;
}
pEntry = pGroup->listHead[indEntry].pEntryNext;
// compute size and bucket index of new free entry
// for zero-sized entry, the index is -1
sizeNewFree = pEntry->sizeFront - sizeEntry;
indNewFree = (sizeNewFree >> 4) - 1;
if (indNewFree > 63)
indNewFree = 63;
// only modify entry pointers if bucket index changed
if (indNewFree != indEntry)
{
// test entry is sole member of bucket (next == prev),
if (pEntry->pEntryNext == pEntry->pEntryPrev)
{
// clear bit in group vector, decrement region count
// if region count is now zero, clear bit in region vector
if (indEntry < 32)
{
pRegion->bitvGroupHi[indGroupUse] &=
~(0x80000000L >> indEntry);
if (--pRegion->cntRegionSize[indEntry] == 0)
pHeader->bitvEntryHi &= ~(0x80000000L >> indEntry);
}
else
{
pRegion->bitvGroupLo[indGroupUse] &=
~(0x80000000L >> (indEntry - 32));
if (--pRegion->cntRegionSize[indEntry] == 0)
pHeader->bitvEntryLo &= ~(0x80000000L >> (indEntry - 32));
}
}
// unlink entry from list
pEntry->pEntryPrev->pEntryNext = pEntry->pEntryNext;
pEntry->pEntryNext->pEntryPrev = pEntry->pEntryPrev;
// if free entry size is still nonzero, reconnect it
if (sizeNewFree != 0)
{
// add entry to the start of the bucket list
pHead = (PENTRY)((char *)&pGroup->listHead[indNewFree] -
sizeof(int));
pEntry->pEntryNext = pHead->pEntryNext;
pEntry->pEntryPrev = pHead;
pHead->pEntryNext = pEntry;
pEntry->pEntryNext->pEntryPrev = pEntry;
// test entry is sole member of bucket (next == prev),
if (pEntry->pEntryNext == pEntry->pEntryPrev)
{
// if region count was zero, set bit in region vector
// set bit in group vector, increment region count
if (indNewFree < 32)
{
if (pRegion->cntRegionSize[indNewFree]++ == 0)
pHeader->bitvEntryHi |= 0x80000000L >> indNewFree;
pRegion->bitvGroupHi[indGroupUse] |=
0x80000000L >> indNewFree;
}
else
{
if (pRegion->cntRegionSize[indNewFree]++ == 0)
pHeader->bitvEntryLo |=
0x80000000L >> (indNewFree - 32);
pRegion->bitvGroupLo[indGroupUse] |=
0x80000000L >> (indNewFree - 32);
}
}
}
}
// change size of free entry (front and back)
if (sizeNewFree != 0)
{
pEntry->sizeFront = sizeNewFree;
((PENTRYEND)((char *)pEntry + sizeNewFree -
sizeof(ENTRYEND)))->sizeBack = sizeNewFree;
}
// mark the allocated entry
pEntry = (PENTRY)((char *)pEntry + sizeNewFree);
pEntry->sizeFront = sizeEntry + 1;
((PENTRYEND)((char *)pEntry + sizeEntry -
sizeof(ENTRYEND)))->sizeBack = sizeEntry + 1;
// one more allocation in group - test if group was empty
if (pGroup->cntEntries++ == 0)
{
// if allocating into deferred group, cancel deferral
if (pHeader == __sbh_pHeaderDefer &&
indGroupUse == __sbh_indGroupDefer)
__sbh_pHeaderDefer = NULL;
}
pRegion->indGroupUse = indGroupUse;
return (void *)((char *)pEntry + sizeof(int));
}
/***
*PHEADER __sbh_alloc_new_region()
*
*Purpose:
* Add a new HEADER structure in the header list. Allocate a new
* REGION structure and initialize. Reserve memory for future
* group commitments.
*
*Entry:
* None.
*
*Exit:
* Returns a pointer to newly created HEADER entry, if successful.
* Returns NULL, if failure.
*
*Exceptions:
*
*******************************************************************************/
PHEADER __cdecl __sbh_alloc_new_region (void)
{
PHEADER pHeader;
// create a new entry in the header list
// if list if full, realloc to extend its size
if (__sbh_cntHeaderList == __sbh_sizeHeaderList)
{
if (!(pHeader = (PHEADER)HeapReAlloc(_crtheap, 0, __sbh_pHeaderList,
(__sbh_sizeHeaderList + 16) * sizeof(HEADER))))
return NULL;
// update pointer and counter values
__sbh_pHeaderList = pHeader;
__sbh_sizeHeaderList += 16;
}
// point to new header in list
pHeader = __sbh_pHeaderList + __sbh_cntHeaderList;
// allocate a new region associated with the new header
if (!(pHeader->pRegion = (PREGION)HeapAlloc(_crtheap, HEAP_ZERO_MEMORY,
sizeof(REGION))))
return NULL;
// reserve address space for heap data in the region
if ((pHeader->pHeapData = VirtualAlloc(0, BYTES_PER_REGION,
MEM_RESERVE, PAGE_READWRITE)) == NULL)
{
HeapFree(_crtheap, 0, pHeader->pRegion);
return NULL;
}
// initialize alloc and commit group vectors
pHeader->bitvEntryHi = 0;
pHeader->bitvEntryLo = 0;
pHeader->bitvCommit = BITV_COMMIT_INIT;
// complete entry by incrementing list count
__sbh_cntHeaderList++;
// initialize index of group to try first (none defined yet)
pHeader->pRegion->indGroupUse = -1;
return pHeader;
}
/***
*int __sbh_alloc_new_group(pHeader)
*
*Purpose:
* Initializes a GROUP structure within HEADER pointed by pHeader.
* Commits and initializes the memory in the memory reserved by the
* REGION.
*
*Entry:
* pHeader - pointer to HEADER from which the GROUP is defined.
*
*Exit:
* Returns an index to newly created GROUP, if successful.
* Returns -1, if failure.
*
*Exceptions:
*
*******************************************************************************/
int __cdecl __sbh_alloc_new_group (PHEADER pHeader)
{
PREGION pRegion = pHeader->pRegion;
PGROUP pGroup;
PENTRY pEntry;
PENTRY pHead;
PENTRYEND pEntryEnd;
BITVEC bitvCommit;
int indCommit;
int index;
void * pHeapPage;
void * pHeapStartPage;
void * pHeapEndPage;
// determine next group to use by first bit set in commit vector
bitvCommit = pHeader->bitvCommit;
indCommit = 0;
while ((int)bitvCommit >= 0)
{
bitvCommit <<= 1;
indCommit++;
}
// allocate and initialize a new group
pGroup = &pRegion->grpHeadList[indCommit];
for (index = 0; index < 63; index++)
{
pEntry = (PENTRY)((char *)&pGroup->listHead[index] - sizeof(int));
pEntry->pEntryNext = pEntry->pEntryPrev = pEntry;
}
// commit heap memory for new group
pHeapStartPage = (void *)((char *)pHeader->pHeapData +
indCommit * BYTES_PER_GROUP);
if ((VirtualAlloc(pHeapStartPage, BYTES_PER_GROUP, MEM_COMMIT,
PAGE_READWRITE)) == NULL)
return -1;
// initialize heap data with empty page entries
pHeapEndPage = (void *)((char *)pHeapStartPage +
(PAGES_PER_GROUP - 1) * BYTES_PER_PAGE);
for (pHeapPage = pHeapStartPage; pHeapPage <= pHeapEndPage;
pHeapPage = (void *)((char *)pHeapPage + BYTES_PER_PAGE))
{
// set sentinel values at start and end of the page
*(int *)((char *)pHeapPage + 8) = -1;
*(int *)((char *)pHeapPage + BYTES_PER_PAGE - 4) = -1;
// set size and pointer info for one empty entry
pEntry = (PENTRY)((char *)pHeapPage + ENTRY_OFFSET);
pEntry->sizeFront = MAX_FREE_ENTRY_SIZE;
pEntry->pEntryNext = (PENTRY)((char *)pEntry +
BYTES_PER_PAGE);
pEntry->pEntryPrev = (PENTRY)((char *)pEntry -
BYTES_PER_PAGE);
pEntryEnd = (PENTRYEND)((char *)pEntry + MAX_FREE_ENTRY_SIZE -
sizeof(ENTRYEND));
pEntryEnd->sizeBack = MAX_FREE_ENTRY_SIZE;
}
// initialize group entry pointer for maximum size
// and set terminate list entries
pHead = (PENTRY)((char *)&pGroup->listHead[63] - sizeof(int));
pEntry = pHead->pEntryNext =
(PENTRY)((char *)pHeapStartPage + ENTRY_OFFSET);
pEntry->pEntryPrev = pHead;
pEntry = pHead->pEntryPrev =
(PENTRY)((char *)pHeapEndPage + ENTRY_OFFSET);
pEntry->pEntryNext = pHead;
pRegion->bitvGroupHi[indCommit] = 0x00000000L;
pRegion->bitvGroupLo[indCommit] = 0x00000001L;
if (pRegion->cntRegionSize[63]++ == 0)
pHeader->bitvEntryLo |= 0x00000001L;
// clear bit in commit vector
pHeader->bitvCommit &= ~(0x80000000L >> indCommit);
return indCommit;
}
/***
*int __sbh_resize_block(pHeader, pvAlloc, intNew) - resize block
*
*Purpose:
* Resize the specified block from the small-block heap.
* The allocation block is not moved.
*
*Entry:
* pHeader - pointer to HEADER containing block
* pvAlloc - pointer to block to resize
* intNew - new size of block in bytes
*
*Exit:
* Returns 1, if successful. Otherwise, 0 is returned.
*
*Exceptions:
*
*******************************************************************************/
int __cdecl __sbh_resize_block (PHEADER pHeader, void * pvAlloc, int intNew)
{
PREGION pRegion;
PGROUP pGroup;
PENTRY pHead;
PENTRY pEntry;
PENTRY pNext;
int sizeEntry;
int sizeNext;
int sizeNew;
unsigned int indGroup;
unsigned int indEntry;
unsigned int indNext;
unsigned int offRegion;
// add 8 bytes entry overhead and round up to next para size
sizeNew = (intNew + 2 * sizeof(int) + (BYTES_PER_PARA - 1))
& ~(BYTES_PER_PARA - 1);
// region is determined by the header
pRegion = pHeader->pRegion;
// use the region offset to determine the group index
offRegion = (unsigned int)pvAlloc - (unsigned int)pHeader->pHeapData;
indGroup = offRegion / BYTES_PER_GROUP;
pGroup = &pRegion->grpHeadList[indGroup];
// get size of entry - decrement value since entry is allocated
pEntry = (PENTRY)((char *)pvAlloc - sizeof(int));
sizeEntry = pEntry->sizeFront - 1;
// point to next entry to get its size
pNext = (PENTRY)((char *)pEntry + sizeEntry);
sizeNext = pNext->sizeFront;
// test if new size is larger than the current one
if (sizeNew > sizeEntry)
{
// if next entry not free, or not large enough, fail
if ((sizeNext & 1) || (sizeNew > sizeEntry + sizeNext))
return FALSE;
// disconnect next entry
// determine index of next entry
indNext = (sizeNext >> 4) - 1;
if (indNext > 63)
indNext = 63;
// test entry is sole member of bucket (next == prev),
if (pNext->pEntryNext == pNext->pEntryPrev)
{
// clear bit in group vector, decrement region count
// if region count is now zero, clear bit in header
// entry vector
if (indNext < 32)
{
pRegion->bitvGroupHi[indGroup] &= ~(0x80000000L >> indNext);
if (--pRegion->cntRegionSize[indNext] == 0)
pHeader->bitvEntryHi &= ~(0x80000000L >> indNext);
}
else
{
pRegion->bitvGroupLo[indGroup] &=
~(0x80000000L >> (indNext - 32));
if (--pRegion->cntRegionSize[indNext] == 0)
pHeader->bitvEntryLo &= ~(0x80000000L >> (indNext - 32));
}
}
// unlink entry from list
pNext->pEntryPrev->pEntryNext = pNext->pEntryNext;
pNext->pEntryNext->pEntryPrev = pNext->pEntryPrev;
// compute new size of the next entry, test if nonzero
if ((sizeNext = sizeEntry + sizeNext - sizeNew) > 0)
{
// compute start of next entry and connect it
pNext = (PENTRY)((char *)pEntry + sizeNew);
// determine index of next entry
indNext = (sizeNext >> 4) - 1;
if (indNext > 63)
indNext = 63;
// add next entry to the start of the bucket list
pHead = (PENTRY)((char *)&pGroup->listHead[indNext] -
sizeof(int));
pNext->pEntryNext = pHead->pEntryNext;
pNext->pEntryPrev = pHead;
pHead->pEntryNext = pNext;
pNext->pEntryNext->pEntryPrev = pNext;
// test entry is sole member of bucket (next == prev),
if (pNext->pEntryNext == pNext->pEntryPrev)
{
// if region count was zero, set bit in region vector
// set bit in header entry vector, increment region count
if (indNext < 32)
{
if (pRegion->cntRegionSize[indNext]++ == 0)
pHeader->bitvEntryHi |= 0x80000000L >> indNext;
pRegion->bitvGroupHi[indGroup] |= 0x80000000L >> indNext;
}
else
{
if (pRegion->cntRegionSize[indNext]++ == 0)
pHeader->bitvEntryLo |= 0x80000000L >> (indNext - 32);
pRegion->bitvGroupLo[indGroup] |=
0x80000000L >> (indNext - 32);
}
}
// adjust size fields of next entry
pNext->sizeFront = sizeNext;
((PENTRYEND)((char *)pNext + sizeNext -
sizeof(ENTRYEND)))->sizeBack = sizeNext;
}
// adjust pEntry to its new size (plus one since allocated)
pEntry->sizeFront = sizeNew + 1;
((PENTRYEND)((char *)pEntry + sizeNew -
sizeof(ENTRYEND)))->sizeBack = sizeNew + 1;
}
// not larger, test if smaller
else if (sizeNew < sizeEntry)
{
// adjust pEntry to new smaller size
pEntry->sizeFront = sizeNew + 1;
((PENTRYEND)((char *)pEntry + sizeNew -
sizeof(ENTRYEND)))->sizeBack = sizeNew + 1;
// set pEntry and sizeEntry to leftover space
pEntry = (PENTRY)((char *)pEntry + sizeNew);
sizeEntry -= sizeNew;
// determine index of entry
indEntry = (sizeEntry >> 4) - 1;
if (indEntry > 63)
indEntry = 63;
// test if next entry is free
if ((sizeNext & 1) == 0)
{
// if so, disconnect it
// determine index of next entry
indNext = (sizeNext >> 4) - 1;
if (indNext > 63)
indNext = 63;
// test entry is sole member of bucket (next == prev),
if (pNext->pEntryNext == pNext->pEntryPrev)
{
// clear bit in group vector, decrement region count
// if region count is now zero, clear bit in header
// entry vector
if (indNext < 32)
{
pRegion->bitvGroupHi[indGroup] &=
~(0x80000000L >> indNext);
if (--pRegion->cntRegionSize[indNext] == 0)
pHeader->bitvEntryHi &= ~(0x80000000L >> indNext);
}
else
{
pRegion->bitvGroupLo[indGroup] &=
~(0x80000000L >> (indNext - 32));
if (--pRegion->cntRegionSize[indNext] == 0)
pHeader->bitvEntryLo &=
~(0x80000000L >> (indNext - 32));
}
}
// unlink entry from list
pNext->pEntryPrev->pEntryNext = pNext->pEntryNext;
pNext->pEntryNext->pEntryPrev = pNext->pEntryPrev;
// add next entry size to present
sizeEntry += sizeNext;
indEntry = (sizeEntry >> 4) - 1;
if (indEntry > 63)
indEntry = 63;
}
// connect leftover space with any free next entry
// add next entry to the start of the bucket list
pHead = (PENTRY)((char *)&pGroup->listHead[indEntry] - sizeof(int));
pEntry->pEntryNext = pHead->pEntryNext;
pEntry->pEntryPrev = pHead;
pHead->pEntryNext = pEntry;
pEntry->pEntryNext->pEntryPrev = pEntry;
// test entry is sole member of bucket (next == prev),
if (pEntry->pEntryNext == pEntry->pEntryPrev)
{
// if region count was zero, set bit in region vector
// set bit in header entry vector, increment region count
if (indEntry < 32)
{
if (pRegion->cntRegionSize[indEntry]++ == 0)
pHeader->bitvEntryHi |= 0x80000000L >> indEntry;
pRegion->bitvGroupHi[indGroup] |= 0x80000000L >> indEntry;
}
else
{
if (pRegion->cntRegionSize[indEntry]++ == 0)
pHeader->bitvEntryLo |= 0x80000000L >> (indEntry - 32);
pRegion->bitvGroupLo[indGroup] |= 0x80000000L >>
(indEntry - 32);
}
}
// adjust size fields of entry
pEntry->sizeFront = sizeEntry;
((PENTRYEND)((char *)pEntry + sizeEntry -
sizeof(ENTRYEND)))->sizeBack = sizeEntry;
}
return TRUE;
}
/***
*int __sbh_heapmin() - minimize heap
*
*Purpose:
* Minimize the heap by freeing any deferred group.
*
*Entry:
* __sbh_pHeaderDefer - pointer to HEADER of deferred group
* __sbh_indGroupDefer - index of GROUP to defer
*
*Exit:
* None.
*
*Exceptions:
*
*******************************************************************************/
void __cdecl __sbh_heapmin (void)
{
void * pHeapDecommit;
// if a group has been deferred, free that group
if (__sbh_pHeaderDefer)
{
// if now zero, decommit the group data heap
pHeapDecommit = (void *)((char *)__sbh_pHeaderDefer->pHeapData +
__sbh_indGroupDefer * BYTES_PER_GROUP);
VirtualFree(pHeapDecommit, BYTES_PER_GROUP, MEM_DECOMMIT);
// set bit in commit vector
__sbh_pHeaderDefer->bitvCommit |= 0x80000000 >> __sbh_indGroupDefer;
// clear entry vector for the group and header vector bit
// if needed
__sbh_pHeaderDefer->pRegion->bitvGroupLo[__sbh_indGroupDefer] = 0;
if (--__sbh_pHeaderDefer->pRegion->cntRegionSize[63] == 0)
__sbh_pHeaderDefer->bitvEntryLo &= ~0x00000001L;
// if commit vector is the initial value,
// remove the region if it is not the last
if (__sbh_pHeaderDefer->bitvCommit == BITV_COMMIT_INIT &&
__sbh_cntHeaderList > 1)
{
// free the region memory area
HeapFree(_crtheap, 0, __sbh_pHeaderDefer->pRegion);
// remove entry from header list by copying over
memmove((void *)__sbh_pHeaderDefer, (void *)(__sbh_pHeaderDefer + 1),
(int)(__sbh_pHeaderList + __sbh_cntHeaderList) -
(int)(__sbh_pHeaderDefer + 1));
__sbh_cntHeaderList--;
}
// clear deferred condition
__sbh_pHeaderDefer = NULL;
}
}
/***
*int __sbh_heap_check() - check small-block heap
*
*Purpose:
* Perform validity checks on the small-block heap.
*
*Entry:
* There are no arguments.
*
*Exit:
* Returns 0 if the small-block is okay.
* Returns < 0 if the small-block heap has an error. The exact value
* identifies where, in the source code below, the error was detected.
*
*Exceptions:
*
*******************************************************************************/
int __cdecl __sbh_heap_check (void)
{
PHEADER pHeader;
PREGION pRegion;
PGROUP pGroup;
PENTRY pEntry;
PENTRY pNext;
PENTRY pEntryLast;
PENTRY pEntryHead;
PENTRY pEntryPage;
PENTRY pEntryPageLast;
int indHeader;
int indGroup;
int indPage;
int indEntry;
int indHead;
int sizeEntry;
int sizeTrue;
int cntAllocated;
int cntFree[64];
int cntEntries;
void * pHeapGroup;
void * pHeapPage;
void * pPageStart;
BITVEC bitvCommit;
BITVEC bitvGroupHi;
BITVEC bitvGroupLo;
BITVEC bitvEntryHi;
BITVEC bitvEntryLo;
// check validity of header list
if (IsBadWritePtr(__sbh_pHeaderList,
__sbh_cntHeaderList * sizeof(HEADER)))
return -1;
// scan for all headers in list
pHeader = __sbh_pHeaderList;
for (indHeader = 0; indHeader < __sbh_cntHeaderList; indHeader++)
{
// define region and test if valid
pRegion = pHeader->pRegion;
if (IsBadWritePtr(pRegion, sizeof(REGION)))
return -2;
// scan for all groups in region
pHeapGroup = pHeader->pHeapData;
pGroup = &pRegion->grpHeadList[0];
bitvCommit = pHeader->bitvCommit;
bitvEntryHi = 0;
bitvEntryLo = 0;
for (indGroup = 0; indGroup < GROUPS_PER_REGION; indGroup++)
{
// initialize entry vector and entry counts for group
bitvGroupHi = 0;
bitvGroupLo = 0;
cntAllocated = 0;
for (indEntry = 0; indEntry < 64; indEntry++)
cntFree[indEntry] = 0;
// test if group is committed
if ((int)bitvCommit >= 0)
{
// committed, ensure addresses are accessable
if (IsBadWritePtr(pHeapGroup, BYTES_PER_GROUP))
return -4;
// for each page in group, check validity of entries
pHeapPage = pHeapGroup;
for (indPage = 0; indPage < PAGES_PER_GROUP; indPage++)
{
// define pointers to first and past last entry
pEntry = (PENTRY)((char *)pHeapPage + ENTRY_OFFSET);
pEntryLast = (PENTRY)((char *)pEntry
+ MAX_FREE_ENTRY_SIZE);
// check front and back page sentinel values
if (*(int *)((char *)pEntry - sizeof(int)) != -1 ||
*(int *)pEntryLast != -1)
return -5;
// loop through each entry in page
do
{
// get entry size and test if allocated
sizeEntry = sizeTrue = pEntry->sizeFront;
if (sizeEntry & 1)
{
// allocated entry - set true size
sizeTrue--;
// test against maximum allocated entry size
if (sizeTrue > MAX_ALLOC_ENTRY_SIZE)
return -6;
// increment allocated count for group
cntAllocated++;
}
else
{
// free entry - determine index and increment
// count for list head checking
indEntry = (sizeTrue >> 4) - 1;
if (indEntry > 63)
indEntry = 63;
cntFree[indEntry]++;
}
// check size validity
if (sizeTrue < 0x10 || sizeTrue & 0xf
|| sizeTrue > MAX_FREE_ENTRY_SIZE)
return -7;
// check if back entry size same as front
if (((PENTRYEND)((char *)pEntry + sizeTrue
- sizeof(int)))->sizeBack != sizeEntry)
return -8;
// move to next entry in page
pEntry = (PENTRY)((char *)pEntry + sizeTrue);
}
while (pEntry < pEntryLast);
// test if last entry did not overrun page end
if (pEntry != pEntryLast)
return -8;
// point to next page in data heap
pHeapPage = (void *)((char *)pHeapPage + BYTES_PER_PAGE);
}
// check if allocated entry count is correct
if (pGroup->cntEntries != cntAllocated)
return -9;
// check validity of linked-lists of free entries
pEntryHead = (PENTRY)((char *)&pGroup->listHead[0] -
sizeof(int));
for (indHead = 0; indHead < 64; indHead++)
{
// scan through list until head is reached or expected
// number of entries traversed
cntEntries = 0;
pEntry = pEntryHead;
while ((pNext = pEntry->pEntryNext) != pEntryHead &&
cntEntries != cntFree[indHead])
{
// test if next pointer is in group data area
if ((void *)pNext < pHeapGroup || (void *)pNext >=
(void *)((char *)pHeapGroup + BYTES_PER_GROUP))
return -10;
// determine page address of next entry
pPageStart = (void *)((int)pNext &
~(BYTES_PER_PAGE - 1));
// point to first entry and past last in the page
pEntryPage = (PENTRY)((char *)pPageStart +
ENTRY_OFFSET);
pEntryPageLast = (PENTRY)((char *)pEntryPage +
MAX_FREE_ENTRY_SIZE);
// do scan from start of page
// no error checking since it was already scanned
while (pEntryPage != pEntryPageLast)
{
// if entry matches, exit loop
if (pEntryPage == pNext)
break;
// point to next entry
pEntryPage = (PENTRY)((char *)pEntryPage +
(pEntryPage->sizeFront & ~1));
}
// if page end reached, pNext was not valid
if (pEntryPage == pEntryPageLast)
return -11;
// entry valid, but check if entry index matches
// the header
indEntry = (pNext->sizeFront >> 4) - 1;
if (indEntry > 63)
indEntry = 63;
if (indEntry != indHead)
return -12;
// check if previous pointer in pNext points
// back to pEntry
if (pNext->pEntryPrev != pEntry)
return -13;
// update scan pointer and counter
pEntry = pNext;
cntEntries++;
}
// if nonzero number of entries, set bit in group
// and region vectors
if (cntEntries)
{
if (indHead < 32)
{
bitvGroupHi |= 0x80000000L >> indHead;
bitvEntryHi |= 0x80000000L >> indHead;
}
else
{
bitvGroupLo |= 0x80000000L >> (indHead - 32);
bitvEntryLo |= 0x80000000L >> (indHead - 32);
}
}
// check if list is exactly the expected size
if (pEntry->pEntryNext != pEntryHead ||
cntEntries != cntFree[indHead])
return -14;
// check if previous pointer in header points to
// last entry processed
if (pEntryHead->pEntryPrev != pEntry)
return -15;
// point to next linked-list header - note size
pEntryHead = (PENTRY)((char *)pEntryHead +
sizeof(LISTHEAD));
}
}
// test if group vector is valid
if (bitvGroupHi != pRegion->bitvGroupHi[indGroup] ||
bitvGroupLo != pRegion->bitvGroupLo[indGroup])
return -16;
// adjust for next group in region
pHeapGroup = (void *)((char *)pHeapGroup + BYTES_PER_GROUP);
pGroup++;
bitvCommit <<= 1;
}
// test if group vector is valid
if (bitvEntryHi != pHeader->bitvEntryHi ||
bitvEntryLo != pHeader->bitvEntryLo)
return -17;
// adjust for next header in list
pHeader++;
}
return 0;
}