DIRECTORY SafeStorage USING[nullType, Type]; Allocator: DEFINITIONS = BEGIN HeaderP: TYPE = LONG POINTER TO Header; -- always even-word aligned NHeaderP: TYPE = LONG POINTER TO NormalHeader; -- always even-word aligned EHeaderP: TYPE = LONG POINTER TO ExtendedHeader; -- always even-word aligned FHeaderP: TYPE = LONG POINTER TO free Header; FEHeaderP: TYPE = LONG POINTER TO extended free Header; FNHeaderP: TYPE = LONG POINTER TO normal free Header; UHeaderP: TYPE = LONG POINTER TO inUse Header; UEHeaderP: TYPE = LONG POINTER TO extended inUse Header; UNHeaderP: TYPE = LONG POINTER TO normal inUse Header; Header: TYPE = MACHINE DEPENDENT RECORD[ -- 2, 4 or 6 words SELECT COMPUTED FreeOrInUse FROM free => [ SELECT COMPUTED ExtendedOrNormal FROM extended => [feh: ExtendedHeader, nextFree: FNHeaderP], -- 6 words normal => [fnh: NormalHeader, nextFree: FNHeaderP] -- 4 words ENDCASE ], inUse => [ SELECT COMPUTED ExtendedOrNormal --ditto-- FROM extended => [ueh: ExtendedHeader], -- 4 words normal => [unh: NormalHeader] -- 2 words ENDCASE ] ENDCASE ]; FreeOrInUse: TYPE = {free, inUse}; ExtendedOrNormal: TYPE = {extended, normal}; ExtendedSizeTag: TYPE = MACHINE DEPENDENT {unused(0), words(1), pages(2), bsi(3)}; ExtendedHeader: TYPE = MACHINE DEPENDENT RECORD[ -- 4 words, always even-word aligned sizeTag(0: 0..1): ExtendedSizeTag _ words, blockSizeIndex(0: 2..7): BlockSizeIndex _ bsiEscape, owner(0: 8..15): Owner _ 0, extendedSize(1): CARDINAL, normalHeader(2): NormalHeader ]; NormalHeader: TYPE = MACHINE DEPENDENT RECORD[ -- 2 words, always even-word aligned inZCT(0: 0..0): BOOL _ FALSE, maybeOnStack(0: 1..1): BOOL _ FALSE, blockSizeIndex(0: 2..7): BlockSizeIndex, -- size includes the header overhead f(0: 8..8): BOOL _ FALSE, refCount(0: 9..14): RefCount _ 0, rcOverflowed(0: 15..15): BOOL _ FALSE, typePad(1: 0..1): [0..3] _ 0, -- TEMPORARY for compatibility type(1: 2..15): SafeStorage.Type _ SafeStorage.nullType ]; SizeToBSIObj: TYPE = PACKED ARRAY [0..maxSmallBlockSize] OF BlockSizeIndex; BSIToSizeObj: TYPE = ARRAY BlockSizeIndex OF NAT; BSIToFreeListObj: TYPE = ARRAY BlockSizeIndex OF FNHeaderP; BlockSizeIndex: TYPE = [0..77B]; -- assumed in ZCT.ZCTObject to be less than wordsPerPage/2 maxSmallBlockSize: NAT = 1076B; -- requested. i.e. does not include overhead minLargeBlockSize: NAT = 3375B; -- requested. i.e. does not include overhead bsiEscape: BlockSizeIndex = LAST[BlockSizeIndex]; -- used to identify extended headers RefCount: TYPE = [0..77B]; Owner: TYPE = [0..377B]; Zone: TYPE = REF ZoneObject; ZoneObject: TYPE = MACHINE DEPENDENT RECORD[ new(0): PROC[self: Zone, size: CARDINAL, type: SafeStorage.Type] RETURNS[REF ANY], free(1): PROC[self: Zone, object: REF ANY] ]; PUZone: TYPE = LONG POINTER TO UZone; UZone: TYPE = LONG POINTER TO UZoneObject; UZoneObject: TYPE = MACHINE DEPENDENT RECORD[ new(0): PROC[self: PUZone, size: CARDINAL] RETURNS[LONG POINTER], free(1): PROC[self: PUZone, object: LONG POINTER] ]; LastAddress: LONG CARDINAL = 77777777B; -- 24 bits wordsPerQuantum: NAT = 256; pagesPerQuantum: NAT = 1; logPagesPerQuantum: NAT = 0; QuantumIndex: TYPE = [0..177777B--LastAddress/wordsPerQuantum--]; QuantumCount: TYPE = CARDINAL; QuantumMap: TYPE = LONG POINTER TO QMObject; QMObject: TYPE = PACKED ARRAY QuantumIndex OF BOOL; END.  Allocator.mesa Copyright c 1985 by Xerox Corporation. All rights reserved. Paul Rovner, October 10, 1983 2:13 pm Russ Atkinson (RRA) February 1, 1985 12:41:41 pm PST Beach, February 22, 1985 1:42:07 pm PST Doug Wyatt, February 24, 1985 8:56:50 pm PST Definitions of TYPEs and constants for the Cedar allocator Storage Structures (LOOPHOLE[ref, NHeaderP]-SIZE[NormalHeader]).type = nullType OR (coming from the top, parsing, starting from QMap) (IF hp.blockSizeIndex = bsiEscape THEN LOOPHOLE[hp, EHeaderP].normalHeader.type = nullType ELSE LOOPHOLE[hp, NHeaderP].type = nullType) LOOPHOLE[ref-SIZE[NormalHeader], NHeaderP].blockSizeIndex = bsiEscape OR hp.blockSizeIndex = bsiEscape identical to the one in normalHeader feature for storage accounting experiments words, pages or bsi, as per sizeTag. includes header overhead TRUE => q this object for finalization if refCount = 0 AND NOT rcOverflowed FALSE => reclaim this object if refCount = 0 AND NOT rcOverflowed TRUE => the rcOverflow bank has a deposit for this object All blocks have an even number of words. A block with REQUESTED size larger than maxSmallBlockSize words requires an extended header. A block with an extended header (bsi = bsiEscape) may have a small size. The minimum block size is 4 words (SIZE[NormalHeader] + SIZE[FHeaderP]) Zone Structures The Quantum Map element TRUE => the indexed quantum is assigned to the Cedar (collectible) allocator Κz˜codešœ™Kšœ Οmœ1™—Kšž˜Kšœ˜—šœ ˜ šžœž œ  œž˜/Kšœ$  ˜.Kšœ  ˜)—Kšž˜Kšœ˜——Kšž˜Kšœ˜K˜—Kšœ žœ˜"Kšœžœ˜,K˜Kšœžœžœž œ)˜Rš œžœžœž œžœ $˜UKšœ*˜*šœ4˜4Kšœ$™$—šœ˜Kšœ*™*—šœžœ˜Kšœ=™=—Kšœ˜Kšœ˜K˜—š œžœžœž œžœ $˜SKšœžœžœ˜Kšœžœžœ˜$Kšœ* $˜Nšœ žœžœ˜KšœK™KKšœA™A—Kšœ!˜!šœžœžœ˜&Kšœ9™9—Kšœ ˜=Kšœ7˜7Kšœ˜—K˜Kš œžœžœžœžœ˜KKš œžœžœžœžœ˜1Kšœžœžœžœ ˜;Kšœžœ  :˜[Kšœžœ  -˜NKšœžœ  -˜Nšœžœ $˜WKšœ(™(Kšœ\™\KšœH™HKšœ#žœžœ ™GK˜—Kšœ žœ ˜Kšœžœ ˜—šœ™Kšœžœžœ ˜šœ žœžœ˜,Kš œ žœžœžœžœžœ˜TKšœ žœžœžœ˜*Kšœ˜—K˜Kšœžœžœ˜%Kšœžœžœ ˜*šœ žœžœ˜-Kš œ žœžœžœž œ˜CKšœ žœž œ˜1Kšœ˜——™Kšœ žœžœ  ˜3Kšœžœ˜Kšœžœ˜Kšœžœ˜Kšœžœ œ˜AKšœžœžœ˜K˜Kš œ žœžœžœžœ ˜,š œ žœžœžœžœžœ˜3KšœT™T——K˜Kšžœ˜—…— ό