FrameAllocatorImpl.mesa
Carl Hauser, November 17, 1986 12:23:38 pm PST
DIRECTORY
FrameAllocator,
Process;
Local frame allocation for mesa runtime. This implementation is constrained to having only procedures that don't require frame extensions: i.e. small frames without procedure nesting or procedure variables.
Does this sit above or below signal handling?
FrameAllocatorImpl: MONITOR
IMPORTS Process
EXPORTS FrameAllocator
~
BEGIN OPEN FrameAllocator
;
Overhead:
TYPE =
RECORD[
I've not done anything to squeeze bits out of this
seal: WORD ← FrameSeal,
item: AVItem,
size: FSIndex
];
OverheadHandle: TYPE = POINTER TO Overhead;
FrameTag: TYPE = {frame, empty, indirect, large};
FSIndex: TYPE = [0..maxFSI];
FSArrayIndex: TYPE = (FSIndex.FIRST .. FSIndex.LAST);
maxFSI: BYTE = 32; -- an arbitrary small constant
FrameSeal: WORD = 176767B; -- something to increase confidence it really is a frame;
AllocationVector: TYPE = ARRAY FSIndex OF AVItem;
AVSizes: ARRAY FSArrayIndex OF NAT = ALL[0]; -- we need a reasonable distribution of these;
AVCounts: ARRAY FSArrayIndex OF NAT = ALL[0]; -- the initial number of frames of each sizewe need a reasonable distribution of these;
AVSuccessor: ARRAY FSIndex OF FSIndex = ALL[0]; -- the successor frame size for use when all the frames of the requested size have been allocated;
AVItem:
TYPE =
RECORD[
tag: FrameTag,
item:
SELECT
OVERLAID FrameTag
FROM
frame => [handle: OverheadHandle],
empty => [],
indirect => [nextSize: FSIndex],
large => [pages: PageCount],
ENDCASE
];
av: AllocationVector;
MoreAvailable: CONDITION;
MoreNeeded: CONDITION;
sizeNeeded: FSIndex;
PageCount: TYPE = NAT;
LargeFrameFaultProc: TYPE = PROC [words: NAT] RETURNS[frame: FrameHandle, overhead: OverheadHandle, pages: PageCount];
LargeFrameFault: LargeFrameFaultProc;
Allocate:
PUBLIC ENTRY PROC [words:
NAT]
RETURNS [frame:
FrameHandle] ~ {
ENABLE UNWIND => RestoreInvariant; -- only if above signal handling
fsi: FSIndex ← GetIndex[words];
IF fsi = FSIndex.
LAST
THEN {
overhead: OverheadHandle;
pages: PageCount;
[frame, overhead, pages] ← LargeFrameFault[words];
overhead.size ← fsi;
overhead.seal ← FrameSeal;
overhead.item ← [large, large[pages]];
}
ELSE {
slot: FSIndex ← fsi;
DO
DO
IF av[slot].tag # indirect THEN EXIT;
slot ← av[slot].nextSize;
ENDLOOP;
IF av[slot].tag=empty
THEN {
sizeNeeded ← fsi;
NOTIFY MoreNeeded;
WAIT MoreAvailable;
}
ELSE EXIT;
ENDLOOP;
frame ← LOOPHOLE[LOOPHOLE[av[slot].handle, NAT]+SIZE[Overhead]];
av[slot] ← av[slot].handle^.item;
};
};
Free:
PUBLIC ENTRY PROC [frame:
FrameHandle] ~ {
ENABLE UNWIND => RestoreInvariant; -- only if above signal handling
overhead: OverheadHandle ← LOOPHOLE[LOOPHOLE[frame, NAT]-SIZE[Overhead]];
IF overhead.seal # FrameSeal THEN ERROR; -- too horrible to contemplate
overhead.item ← av[overhead.size];
av[overhead.size] ← [frame, frame[overhead]];
};
GetIndex:
PROC [words:
NAT]
RETURNS [index: FSIndex] ~ {
low: NAT ← FSIndex.FIRST;
index ← FSIndex.LAST;
Assume:
AVSizes ordered and extended (logically) by -infinity and +infinity at positions FSIndex.FIRST and FSIndex.LAST. These positions must not be referenced;
Inv:
FSIndex.FIRST <= low < index <= FSIndex.LAST AND
AVSizes[low] < words <= AVSizes[index]
WHILE low+1 # index
DO
mid: FSArrayIndex ← (low+index)/2;
Assert: mid IN FSArrayIndex;
SELECT
TRUE
FROM
words <= AVSizes[mid] => index ← mid;
words > AVSizes[mid] => low ← mid;
ENDCASE;
ENDLOOP;
};
FrameFaultProcess:
ENTRY
SAFE
PROC ~
TRUSTED {
WAIT MoreNeeded;
How do we know what size?
Die[];
};
Initialize:
ENTRY PROC []
RETURNS [] ~ {
Build the allocation vector
Process.Detach[FORK FrameFaultProcess[]];
};
END.