THE INNER PRODUCT // PaUl laska
4 // Check the request to make sure it will fit in the memory being
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 )
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.
uPreBitMask = kMem TrackingUnitAllPagesInUse;
Once the bitmask is created it is repeatedly checked and shifted toward
the end of the tracking unit until a match to the bitmask is found, or all