Game Developer - August 2011

bits in the bitmask are exhausted. If a match isn’t found prior to shifting the bitmask, then the bits that are shifted off the end of the tracking unit, representing needed pages, will need to be found in the next tracking unit, and this is kept in the uPreOffset counter used in a for loop.

for( ; uPreOffset < kMemNumPagesPerUnit; ++uPreOffset)

{ if((~(aMemPage TrackingBits[ uBegTrackUnit ]) & { break;

} uPreBitMask = uPreBitMask >> 1; }

Next, a check is done to make sure the bitmask wasn’t completely exhausted, and if it was, to move to the next tracking unit and start over.

if(uPreOffset == kMemNumPagesPerUnit)

{ uBegTrackUnit++; while(aMemPage TrackingBits[ uBegTrackUnit ] == kMemTrackingUnitAllPagesInUse)

{ uBeg TrackUnit++;

} continue; }

If the bitmask wasn’t completely exhausted, then the number of remaining pages needed is calculated and checked. If more pages are needed then a check is performed to ensure more tracking units are available. When no more tracking units are available, but more pages are needed, a null is returned. In the case that enough pages have been found to fulfill the request, the pages to be assigned are marked as in use, the beginning memory address is calculated, the memory used to pad the allocation header, if any, is cleared, the allocation header is written, and the memory address immediately following the allocation header is returned. By placing the allocation header immediately prior to the memory address returned, the size and alignment information can be easily retrieved during a free method call—or anywhere it needs to be viewed, such as in a debugger— simply by moving the memory address pointer backward. See Listing 1.

5b // Find whole tracking units where all pages are available and required in fulfilling the request.

Since the tracking units are 32-bit unsigned integers, any tracking units where all pages in the tracking unit are available will have a value of zero. The number of contiguous whole tracking units to find is calculated, and then the tracking units subsequent to the starting tracking unit are evaluated. If a partially or fully-used tracking unit is encountered before all the required whole tracking units are found, then the tracking unit to start searching from is moved up to the current tracking unit, and the search for whole tracking units is terminated. If a tracking unit is completely available, it is counted and evaluation continues until failure, or all required contiguous whole tracking units are found and confirmed, as below.

u32 uNumContgTrackUnitsAvail = 0;
u32 uNumContgTrackUnits ToFind =
uNumRemPagesNeeded / kMemNumPagesPerUnit;
for(u32 i = uNxtTrackUnitToChk;
i < kMemNum TrackingUnits &&
if((~(aMemPageTrackingBits[ uNxtTrackUnitToChk ]) &
uPostBitMask)

u32 uAddress = ((uBegTrackUnit kMemNumPagesPerUnit) + uPreOffset) kMemPageSize;

memset((void*)((u32)(const_cast< void* >(kpMemory)) + uAddress), 0, uAllocHdrPadSize);

((TALLOC_HDR*)((u32)(const_cast< void* >(kpMemory)) + uAddress + uAllocHdrPadSize))->uSize = uSize;

((TALLOC_HDR*)((u32)(const_cast< void* >(kpMemory)) + uAddress + uAllocHdrPadSize))->uAlignment = uAlignment;

return (void*)((u32)(const_cast< void* >(kpMemory)) + uAddress + uAllocHdrSize);

} uBegTrackUnit = uNxtTrackUnitToChk;

Once the search has terminated or completed, the number of available whole tracking units found is compared to the number of contiguous whole tracking units required, to make sure the search wasn’t terminated early. If the search was terminated early, then the search for the requested memory must begin again at the beginning.