/*** *sbheap.c - Small-block heap code * * Copyright (c) 1996-1998, Microsoft Corporation. All rights reserved. * *Purpose: * Core code for small-block heap. * *******************************************************************************/ #include #include #include #include #include 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; }