UnsafeAllocatorImpl.Mesa
Copyright © 1985 by Xerox Corporation. All rights reserved.
Paul Rovner, November 9, 1983 8:33 am
Russ Atkinson (RRA) February 1, 1985 2:17:34 pm PST
Bob Hagmann February 19, 1985 4:26:22 pm PST
DIRECTORY
Allocator USING[bsiEscape, EHeaderP, ExtendedHeader, PUZone],
AllocatorOps USING[DoubleFreeHeader, Rover, DFHeaderP, DoCreateMediumSizedObject, DoFreeMediumSizedObject, nonNullType],
Process USING [Pause],
UnsafeStoragePrivate USING[],
VMInternal USING[partitions], -- move this to VMSideDoor
VM USING[AddressForPageNumber, Allocate, CantAllocate, Free, Interval, MakeUnchanged, nullInterval, PageCount, PagesForWords, PageNumber, PageNumberForAddress, wordsPerPage];
UnsafeAllocatorImpl:
MONITOR
protects the systemUZone free list and rover. Procs herein are simply entry procs that call back into AllocatorImpl.
IMPORTS AllocatorOps, Process, VM, VMInternal
EXPORTS AllocatorOps, UnsafeStoragePrivate
= BEGIN OPEN AllocatorOps;
ERRORS
InsufficientVM: ERROR = CODE;
TYPES
UZHandle: TYPE = LONG POINTER TO UZObject;
UZObject:
TYPE =
MACHINE
DEPENDENT
RECORD [
procs(0:0..31): LONG POINTER TO UZProcs
];
UZProcs:
TYPE =
MACHINE
DEPENDENT
RECORD [
new(0): PROC[self: UZHandle, size: CARDINAL] RETURNS[LONG POINTER],
free(1): PROC[self: UZHandle, object: LONG POINTER]
];
UNCOUNTED ZONES and their data
the permanentPageZone
ppzProcs: UZProcs ← [new: PPZNew, free: NIL];
ppzObject: UZObject ← [procs: @ppzProcs];
permanentPageZone:
PUBLIC
UNCOUNTED
ZONE ←
LOOPHOLE[
LONG[@ppzObject]];
permanentPageZone requires no ENTRY procs
permanentPageZone is ready for use
the systemUZone free list and rover
heapRoot: DoubleFreeHeader ← [
dummy entry; the "uncountedHeap" free list never has NIL ptrs
eh: [extendedSize: 0, normalHeader: [blockSizeIndex: Allocator.bsiEscape]],
nextFree: @heapRoot,
prevFree: @heapRoot
];
heapRover: Rover ← @heapRoot;
the TransientPageZone data
skipHeader: CARDINAL = SIZE[Allocator.ExtendedHeader];
skipToHeader: CARDINAL = VM.wordsPerPage - skipHeader;
MaxTransientPageSize: INT = 8; -- Maximum size kept in the cache
transientPageAllocCount: INT ← 0 ;
transientPageAllocRover: VM.PageNumber ← 0;
MaxTransientPageIntervalInRec: INT = 10;
TransientPageListRec:
TYPE =
RECORD [
prev: REF TransientPageListRec,
next: REF TransientPageListRec ← NIL,
putIndex: CARDINAL ← 1,
intervalStarts: ARRAY [1..MaxTransientPageIntervalInRec] OF VM.PageNumber ← ALL[0]
];
TransientPageList: PUBLIC ARRAY [1..MaxTransientPageSize] OF REF TransientPageListRec ← ALL[NIL];
IMPLEMENTATION of permanentPageZone
Referenced only from permanentPageZone (its NEW proc)
PPZNew:
PROC[self: UZHandle, size:
CARDINAL]
RETURNS[lp:
LONG
POINTER] = {
nPages: INT = VM.PagesForWords[size];
lp ←
VM.AddressForPageNumber
[VM.Allocate[count: nPages, in64K: TRUE ! VM.CantAllocate => GOTO noVM].page];
EXITS noVM => ERROR InsufficientVM;
IMPLEMENTATION support for the systemUZone; here because these need their own monitor
Called only from AllocatorImpl.NewHeapObject.
size includes overhead, has been quantized and is >= SIZE[DoubleFreeHeader].
This proc may return an object of a larger size than requested.
Returns NIL if free list needs expansion.
CreateMediumSizedHeapObject:
PUBLIC
ENTRY
PROC[size:
NAT]
RETURNS[
LONG
POINTER] = {
ENABLE UNWIND => NULL;
RETURN[
AllocatorOps.DoCreateMediumSizedObject[size, nonNullType, @heapRover, FALSE]];
};
Called only from ExpandDoubleFreeList and FreeHeapObject in AllocatorImpl.
Assume header is made
FreeMediumSizedHeapObject:
PUBLIC ENTRY
PROC[ptr: DFHeaderP] = {
ENABLE UNWIND => NULL;
AllocatorOps.DoFreeMediumSizedObject[ptr, heapRover];
};
IMPLEMENTATION of TransientPageZone
Allocate an object that is page aligned, and as big as needed.
NewTransientPageObject:
PUBLIC PROC[self: Allocator.PUZone, size:
CARDINAL]
RETURNS[p:
LONG
POINTER] = {
nPages: VM.PageCount = MAX[2, VM.PagesForWords[size]+1]; -- both PagesForWords and MAX calls are inlines
interval: VM.Interval ← VM.nullInterval;
ehp: Allocator.EHeaderP;
IF nPages > MaxTransientPageSize
THEN {
fall back on VM allocator for really big objects
DO
interval ← VM.Allocate[count: nPages ! VM.CantAllocate => CONTINUE;];
IF interval.page # 0 THEN EXIT;
Process.Pause[1];
ENDLOOP;
p ← VM.AddressForPageNumber[interval.page]; -- an inline
}
ELSE {
found: BOOL;
[found, p] ← getFromTransientCache[nPages]; -- an inline ENTRY
IF ~found
THEN {
No pages available of correct size. Get a new interval from VM. We maintain our oun rover so as to use up the small free chunks of VM in low memory.
IF transientPageAllocCount > 10 THEN transientPageAllocCount ← 0;
IF transientPageAllocCount = 0 THEN transientPageAllocRover ← VMInternal.partitions[normalVM].page;
transientPageAllocCount ← transientPageAllocCount + 1;
DO
interval ← VM.Allocate[count: nPages, start: transientPageAllocRover ! VM.CantAllocate => CONTINUE;];
IF interval.page # 0 THEN { p ← VM.AddressForPageNumber[interval.page]; EXIT};
Process.Pause[1];
ENDLOOP;
transientPageAllocRover ← interval.page;
};
};
p now points to the start of the allocated page interval. Skip over extra words at the start of the page, and write a header. This header may not be needed, but the normal unsafe allocator writes them, so we do it here too.
p ← p + skipToHeader;
ehp ← LOOPHOLE[p, Allocator.EHeaderP];
ehp^ ← [
sizeTag: pages,
extendedSize: nPages - 1,
normalHeader: [blockSizeIndex: Allocator.bsiEscape, type: AllocatorOps.nonNullType]
];
p ← p + skipHeader;
};
FreeTransientPageObject:
PUBLIC
PROC [self: Allocator.PUZone, object:
LONG
POINTER] = {
IF
LOOPHOLE[object,
INT] # 0
THEN {
Read header to find out how big the object is. Then free the object using either VM or our oun internal cache.
objectHdr: Allocator.EHeaderP = LOOPHOLE[object - skipHeader];
nPages: VM.PageCount = objectHdr.extendedSize+1;
interval: VM.Interval ← [page: VM.PageNumberForAddress[objectHdr], count: nPages];
IF nPages > MaxTransientPageSize
THEN {
VM.Free[interval]; -- does procedure call
RETURN;
}
ELSE {
putIntoTransientCache[interval]; -- this calls an inline, but it does a procedure call to VM.MakeUnchanged
};
};
};
Internal Procedures
getFromTransientCache:
ENTRY
PROC [nPages:
VM.PageCount]
RETURNS [found:
BOOL, address:
LONG
POINTER
TO
WORD] =
INLINE {
putIndex: INT ← TransientPageList[nPages].putIndex;
IF putIndex > 1
THEN {
putIndex← putIndex - 1;
address ← VM.AddressForPageNumber[TransientPageList[nPages].intervalStarts[putIndex]];
TransientPageList[nPages].putIndex ← putIndex;
found ← TRUE;
}
ELSE {
IF TransientPageList[nPages].prev = NIL THEN found ← FALSE
ELSE {
TransientPageList[nPages] ← TransientPageList[nPages].prev;
address ← VM.AddressForPageNumber[ TransientPageList[nPages].intervalStarts[MaxTransientPageIntervalInRec]];
TransientPageList[nPages].putIndex ← MaxTransientPageIntervalInRec;
found ← TRUE;
};
};
};
putIntoTransientCache:
ENTRY
PROC [interval:
VM.Interval] =
INLINE {
count: INT = interval.count;
putIndex: INT ← TransientPageList[count].putIndex;
VM.MakeUnchanged[interval]; -- by making the pages "unchanged", we retain the physical memory associated with this interval (decreases page faults); however we also make the page "clean" in that if it is reclaimed it will not be written to the backing file
IF putIndex > MaxTransientPageIntervalInRec
THEN {
putIndex ← 1;
IF TransientPageList[count].next =
NIL
THEN {
TransientPageList[count].next ← NEW [TransientPageListRec ← [prev: TransientPageList[count]]];
TransientPageList[count].next.prev ← TransientPageList[count];
};
TransientPageList[count] ← TransientPageList[count].next;
TransientPageList[count].putIndex ← 1;
};
TransientPageList[count].intervalStarts[putIndex] ← interval.page;
TransientPageList[count].putIndex ← putIndex + 1;
};