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 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[ 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 Definitions of TYPEs and constants for the Cedar allocator Paul Rovner, October 10, 1983 2:13 pm 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 4 words, always even-word aligned identical to the one in normalHeader feature for storage accounting experiments words, pages or bsi, as per sizeTag. includes header overhead 2 words, always even-word aligned 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 Э╩_ШJЪЬЩJЪЬ:Щ:JЪЬ%Щ%JШJЪ╧k Ь ЭЬШ,JШJЪЬЭЬЭШШЪЬЩJЪ Ь ЭЬЭЬЭЬЭЬ ╧cШDJЪ Ь ЭЬЭЬЭЬЭЬЮШKJЪ Ь ЭЬЭЬЭЬЭЬЮШMJШJЪ Ь ЭЬЭЬЭЬЭЬ Ш-JЪ ЬЭЬЭЬЭЬЭЬШ7JЪ ЬЭЬЭЬЭЬЭЬШ5JШJЪ Ь ЭЬЭЬЭЬЭЬШ.JЪ ЬЭЬЭЬЭЬЭЬШ8JЪ ЬЭЬЭЬЭЬЭЬШ6JШЪ ЬЭЬЭЬЭ ЬЭЬЮШ<ЪЭЬЭЬ ЭШ JЪЬ=Щ=JЩ7ЪЬ"Щ"JЪЬ9Щ9JЪЬ-Щ-ЧЪЬ Ш ЪЭЬЭЬЭШ%JЪЬ,ЮЩFJЩJЪЬЩJЪЬ9Ю ШCJЪЬ4Ю Ш>ЧJЪЭШJЪЬШЧЪЬ Ш ЪЭЬЭ ЬЮ ЬЭШ/JЪЬ$Ю Ш.JЪЬЮ Ш)ЧJЪЭШJЪЬШЧЧJЪЭШJЪЬШJШЧJЪЬ ЭЬШ"JЪЬЭЬШ,JШЪЬЭЬЭЬЭ Ь)ШRJЪЬ!Щ!ЧЪ ЬЭЬЭЬЭ ЬЭЬЮ Ш