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] ~ {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] ~ {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.  j  FrameAllocatorImpl.mesaCarl Hauser, November 17, 1986 12:23:38 pm PST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?I've not done anything to squeeze bits out of thisENABLE UNWIND => RestoreInvariant;  -- only if above signal handlingENABLE UNWIND => RestoreInvariant; -- only if above signal handling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]Assert: mid IN FSArrayIndex;How do we know what size?Die[];Build the allocation vectorÊ“  ˜ ™Icode™.K™ —šÏk	˜	Kšœ˜Kšœ˜—J™ K˜ K™ÐK™ K™-K™ KšÐlnœ˜Kšœ˜Kšœ˜šœœ˜K˜ —šœ
œœ˜K™2Kšœœ˜K˜K˜K˜K˜ —Kšœœœœ
˜+K˜ Kšœ
œ#˜1K˜ Kšœ	œ˜Kšœœœœ˜5K˜ KšœœÏc˜1K˜ KšœœŸ9˜UK˜ Kšœœœ	œ˜1K˜ Kš
œ	œœœœŸ.˜[K˜ Kš
œ
œœœœŸW˜…K˜ Kšœœ	œœŸc˜“K˜ K˜ šœœœ˜Kšœ˜šœœœ
˜#Kšœ"˜"Kšœ˜K˜ K˜Kš˜K˜——K˜ Kšœ˜Kšœ	œ˜Kšœ	œ˜K˜K˜ Kšœœœ˜K˜ Kš	œœœ	œœA˜vK˜ Kšœ%˜%K˜ š
Ïnœœ	œœœ˜IKšœœ9™FK˜šœœœ˜Kšœ˜K˜Kšœ2˜2K˜K˜K˜&K˜—šœ˜K˜š˜š˜Kšœœœ˜%K˜Kšœ˜—šœœ˜K˜Jšœ˜Kšœ˜K˜—Kšœ˜
Kšœ˜—Kš	œœœœœ˜@Kšœ!˜!K˜—K˜—K˜ š œœœ˜0Kšœœ8™EKš	œœœœœ˜IKšœœœŸ˜GK˜"K˜-K˜K˜ —š œœ	œœ˜8Kšœœ˜Kšœœ˜™KšœYœœœ'™™—šœ™KšœœœÏs™0Kšœ&™&—šœ˜Kšœ"˜"Kšœ¡œ™šœœœ˜Kšœ%˜%Kšœ"˜"Kšœ˜	—Kšœ˜—K˜K˜ —š
 œœœœœ˜.Kšœ˜K™K™Kšœ˜K˜ K˜ —š 
œ
œœ˜(K™Kšœœ˜)K˜K˜ —˜K˜ —Kšœ˜— …—    
ø  õ  