Allocator.mesa
Copyright © 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
DIRECTORY
SafeStorage USING[nullType, Type];
Allocator: DEFINITIONS
= BEGIN
Storage Structures
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
 (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)
free => [
SELECT COMPUTED ExtendedOrNormal FROM
 LOOPHOLE[ref-SIZE[NormalHeader], NHeaderP].blockSizeIndex = bsiEscape
  OR
 hp.blockSizeIndex = bsiEscape
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,
identical to the one in normalHeader
owner(0: 8..15): Owner ← 0,
feature for storage accounting experiments
extendedSize(1): CARDINAL,
words, pages or bsi, as per sizeTag. includes header overhead
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,
TRUE => q this object for finalization if refCount = 0 AND NOT rcOverflowed
FALSE => reclaim this object if refCount = 0 AND NOT rcOverflowed
refCount(0: 9..14): RefCount ← 0,
rcOverflowed(0: 15..15): BOOL ← FALSE,
TRUE => the rcOverflow bank has a deposit for this object
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
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])
RefCount: TYPE = [0..77B];
Owner: TYPE = [0..377B];
Zone Structures
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]
];
The Quantum Map
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;
element TRUE => the indexed quantum is assigned to the Cedar (collectible) allocator
END.