<> <> <<>> DIRECTORY FrameAllocator, Process; <<>> <> <<>> <> <<>> FrameAllocatorImpl: MONITOR IMPORTS Process EXPORTS FrameAllocator ~ BEGIN OPEN FrameAllocator; Overhead: TYPE = RECORD[ <> 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] ~ { <
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] ~ { <
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; <> <> <> <> <> WHILE low+1 # index DO mid: FSArrayIndex _ (low+index)/2; <> SELECT TRUE FROM words <= AVSizes[mid] => index _ mid; words > AVSizes[mid] => low _ mid; ENDCASE; ENDLOOP; }; FrameFaultProcess: ENTRY SAFE PROC ~ TRUSTED { WAIT MoreNeeded; <> <> }; Initialize: ENTRY PROC [] RETURNS [] ~ { <> Process.Detach[FORK FrameFaultProcess[]]; }; Initialize[]; END.