FrameAllocatorImpl.mesa
Carl Hauser, November 12, 1986 11:08:37 am PST
DIRECTORY
FrameAllocator,
Process;
Local (and Global?) 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.
Is it necessary to handle global frame allocations here at all? If not the interface can be simplified.
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 FSIndex OF NAT = ALL[0]; -- we need a reasonable distribution of these;
AVCounts: ARRAY FSIndex 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;
AVSizes[mid] > words => low ← mid;
ENDCASE;
ENDLOOP;
};
FrameFaultProcess:
ENTRY
SAFE
PROC ~
TRUSTED {
WAIT MoreNeeded;
Die[];
};
Initialize:
ENTRY PROC []
RETURNS [] ~ {
Build the allocation vector
Process.Detach[FORK FrameFaultProcess[]];
};
END.