Game Developer - August 2011

THE INNER PRODUCT // PaUl laska

4 // Check the request to make sure it will fit in the memory being tracked. The number of pages being requested is calculated and saved. First, the number of whole pages is obtained by dividing the allocation size by the size of a page of memory. Then any remaining memory that is required will fit into one page, so one page will be added if the allocation size modulus by the size of a page of memory is anything other than zero.

const u32 uNumPagesReq = uSize / kMemPageSize + ((uSize kMemPageSize) 1 : 0);

Next the number of tracking units requested is calculated and saved in a similar fashion. The number of whole tracking units is the number of pages requested divided by the number of pages per tracking unit. Then any remaining pages will fit into one tracking unit, so one tracking unit will be added if the number of pages requested modulus by the number of pages per tracking unit is anything other than zero.

const u32 uNum TrackUnitsReq = uNumPagesReq / kMemNumPagesPerUnit + ((uNumPagesReq kMemNumPagesPerUnit) 1 : 0);

Lastly, the number of tracking units requested is compared to the total number of tracking units. If there are more tracking units being requested than the total number, the allocation failure is reported by returning NULL.

if( uNum TrackingUnitsReq > kMemNumTrackingUnits )

{ return NULL;

}

5 // Find enough contiguous pages of memory to satisfy the allocation.

The search for pages is broken up into three stages; starting point, whole tracking units, and remaining pages. The starting point looks for a tracking unit that either resolves the entire request or has pages available at the end, and is contiguous to the next tracking unit. The whole tracking units consist of 32 pages, at 4KB each, and by searching for available whole tracking units, the search is sped up by not having to do an individual search for each page internally. The remaining pages stage aims to fulfill the remainder of the request by checking the tracking unit that is contiguous to either the tracking unit used for the starting point, or the last whole tracking unit, depending on which was last used.

With the given machine architecture (Little Endian), I still think of the units of the tracking array like they are Big Endian. When the end of the tracking unit is referred to, this refers to the least significant bit. The beginning or start of the tracking unit is the most significant bit (see Figure 1).

The array of tracking units will position the end of each preceding tracking unit next to the start of the subsequent tracking unit as seen in Figure 2.

The search begins at the first tracking unit, and continues iterating over the array of tracking units until they have been exhausted.

gamE DEvElOPER | aUgUs T 2011 36

Figure 2: Preceding/Subsequent tracking units.

u32 uBeginningTrackingUnit = 0; while(uBeginning TrackingUnit < kMemNum TrackingUnits) {

5a // Find a starting point of available pages within a tracking unit.

Four potential situations exist within the first tracking unit.

1. All the pages have been used.

2. Not enough free pages exist internal to the tracking unit to fulfill the request.

3. All the pages needed to fulfill the request are contained within the starting tracking unit.

4. Available pages exist starting at some point within the tracking unit, extending to the end, and may be used in conjunction with the next tracking unit to fulfill the request if enough available contiguous pages exist.

The first two situations are not useful for fulfilling the request, so the last two are what we should test for. If there are enough pages contained within a tracking unit to fulfill the request, they can be located by building a bitmask that represents enough pages, then using that bitmask to find a match with the available pages. The number of pages not needed in a tracking unit is calculated by subtracting the number of pages needed from the number of pages per tracking unit. The bitmask is then created by bit shifting the “all pages in use” constant toward the end of the tracking unit by the number of pages not needed; this leaves the number of pages that are needed as the bitmask.

u32 uPreOffset = 0;

TRACKING_UNIT uPreBitMask = 0; if(uNumPagesReq < kMemNumPagesPerUnit)

{ uPreBitMask = kMem TrackingUnitAllPagesInUse << (kMemNumPagesPerUnit - uNumPagesReq);

}

If there are not enough available pages contained within a tracking unit to fulfill the request, then either the entire tracking unit (if all pages are available) or whatever available pages are at the end of the tracking unit can be used in conjunction with the available pages contained in the start, or the entirety of the subsequent tracking unit. The bitmask that represents all pages available is built from this.