-- RTZones.Mesa: An internal Cedar system interface.
-- Defines ZONE data structures (also quantum map, object storage format)
-- last edited 12-Aug-81 15:27:01 by Willie-Sue Haugeland
-- last edited May 13, 1983 3:07 pm by Paul Rovner

DIRECTORY
RTQuanta USING[QuantumSize, QuantumIndex, QuantumCount, QuantumSizeDIV,
LASTAddress, PtrToQtmIndex],
SafeStorage USING [TypeIndex, Type],
UnsafeStorage USING [UZoneFullProc],
Runs USING [Run];

RTZones: DEFINITIONS IMPORTS RTQuanta
= BEGIN
OPEN RTQuanta, SafeStorage, UnsafeStorage;

maxSizeToZnIndex: NAT = 400B; -- even.
SizeToZn: REF ARRAY [0..maxSizeToZnIndex] OF ZONE; -- odd entries will be NIL
useSizeToZn: BOOL = TRUE;
mediumSizedZone: ZONE;

ZoneFullProc: TYPE = PROC[zone: ZONE, size: LONG CARDINAL--words--];

SizeRepresentation: TYPE = {quantized, prefixed};

QuantizedSize: PROC[size: CARDINAL] RETURNS[CARDINAL];

BaseOverhead: CARDINAL = 1;

GetQuanta: PROC[nQ: QuantumCount]
RETURNS[q: QuantumIndex, firstQuantum: BOOLEAN];

PutQuanta: PROC[q: QuantumIndex, nQ: QuantumCount];

-- Eternal refs to the built-in zones
zoneSystem: ZONE;
zoneHeapSystem: UNCOUNTED ZONE;

-- The "quantum map": VM QuantumIndex to ZoneFinger
MapQZf: TMapQZf;
TMapQZf: TYPE = LONG POINTER TO RMapQZf;
RMapQZf: TYPE = RECORD[mzs: SEQUENCE length: NAT OF ZoneFinger];

-- each ZoneFinger identifies either a prefixed ZONE or a subZone of a quantized ZONE
ZoneFinger: TYPE = MACHINE DEPENDENT RECORD
[SELECT ztype: * FROM
prefixed => [zi: ZoneIndex],
sub => [szi: SubZoneIndex],
ENDCASE];
mzVacant: ZoneFinger = [prefixed[0]];

ZoneIndex: TYPE = CARDINAL [0..LAST[CARDINAL]/2]; -- so ZoneFinger fits in 1 word
SubZoneIndex: TYPE = CARDINAL [0..LAST[CARDINAL]/2]; -- ditto

-- The map from ZoneIndex to Zone
MapZiZn: TMapZiZn;
TMapZiZn: TYPE = REF RMapZiZn;
RMapZiZn: TYPE = RECORD[zones: SEQUENCE length: NAT OF Zone];
PMapZiZn: TYPE = RECORD[zones: SEQUENCE length: NAT OF LONG UNSPECIFIED];

Zone: TYPE = REF ZoneRec;
QuantizedZone: TYPE = REF quantized ZoneRec;
PrefixedZone: TYPE = REF prefixed ZoneRec;

PZone: TYPE = LONG POINTER TO ZoneRec;
PQuantizedZone: TYPE = LONG POINTER TO quantized ZoneRec;
PPrefixedZone: TYPE = LONG POINTER TO prefixed ZoneRec;

ZoneRec: TYPE = MACHINE DEPENDENT RECORD -- used by the microcode
[ new: UNSPECIFIED, -- PROC[self: PrefixedZone, size: CARDINAL, type: Type]
-- RETURNS[REF ANY]
free: UNSPECIFIED, -- PROC[self: PrefixedZone, object: REF ANY]
LOCK: MONITORLOCK,
zi: CARDINAL, --ZoneIndex,-- -- this ZONE's zone index
linkage: ZoneLinkage, -- indicates ZONE or UNCOUNTED ZONE
qFirst: CARDINAL ← 0, --a QuantumIndex. If non-zero, this indicates that this ZONE owns
--the first quantum of its BASE, hance that adjustment by
--BaseOverhead is required in various situations
runs: Runs.Run ← NIL, -- of quanta that belong to this zone
cellsInService: LONG CARDINAL ← 0, -- don't count on it
objectsInService: LONG CARDINAL ← 0, -- ditto
overheadCells: LONG CARDINAL ← 0, -- ditto
freeLists: SELECT sr: SizeRepresentation FROM
quantized =>
[ fill: [0..LAST[CARDINAL]/2] ← 0,
qNext, qLast: CARDINAL ← 0, --QuantumIndices assigned to this subzone but not
--carved up yet and put on a free list
-- [qNext..qLast)
mAsz: CARDINAL ← 3, -- hash mask
nAsz: CARDINAL ← 0, -- number of hash table entries in use
pAsz: SubZoneArray ← szaNil -- the subzone hash table, (type, size) -> SubZoneRec
],
prefixed =>
[ fill: [0..LAST[CARDINAL]/2] ← 0,
fnd: free NodeHeader ← fndNil, -- the prefixed free list is doubly linked; the free ring
-- includes the ZoneRec, which looks like a zero-length
-- object
pfn: PFreeNode ← NIL -- the "rover" of the prefixed free list
],
ENDCASE
];

ZoneLinkage: TYPE = RECORD
[ SELECT tag: * FROM
collectible => [fullProc: ZoneFullProc, fill: REF ANY ← NIL],
heap => [fullProc: UnsafeStorage.UZoneFullProc,
-- UNCOUNTED ZONEs get their quanta from the RootBase
typeRepresentation: BOOLEAN ← FALSE,
fill: CARDINAL ← 0]
ENDCASE];

SubZoneArray: TYPE = LONG DESCRIPTOR FOR ARRAY OF SubZoneRec;
szaNil: LONG DESCRIPTOR FOR ARRAY OF UNSPECIFIED = LOOPHOLE[descNilA];
-- done this way because Mesa doesn't recognize DESCRIPTOR[NIL, 0] as constant
descNilA: ARRAY [0..2] OF CARDINAL = [0, 0, 0];

SubZoneRec: TYPE = MACHINE DEPENDENT RECORD -- "rSz", element of hash array
[ typePad: [0..3] ← 0,
type: Type,
size: CARDINAL,
fl: FreeList ← NIL,
zi: CARDINAL--ZoneIndex--, -- my parent's index in MapZiZn (logically a backpointer)
szi: CARDINAL--SubZoneIndex-- -- my own index in MapSziSz (logically a backpointer)
];

FreeList: TYPE = LONG POINTER TO FreeList;

SubZone: TYPE = LONG POINTER TO SubZoneRec;

-- The map from subzone index to SubZone
-- MapSziSz: TMapSziSz;
-- TMapSziSz: TYPE = LONG POINTER TO RMapSziSz;
-- RMapSziSz: TYPE = RECORD[pointers: SEQUENCE length: NAT OF SubZone];

-- Constants
nZiMaxInit: NAT = 200; -- initial size of MapZiZn
nSziMaxInit: NAT = 300; -- initial size of MapSziSz
sziVacant: SubZoneIndex = 0;

-- Node structures in prefixed zones
--* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
-- all objects start on even word boundaries
-- a TypeIndex is 14 bits
-- max client object size = 64K words (free blocks can be arbitrarily big)
--* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

-- size includes the overhead; is for entire block
NodeHeader: TYPE = MACHINE DEPENDENT RECORD
[SizeLo: LongNodeSizeLo← 0,
body: SELECT state: NodeState FROM
inuse => [marked: BOOLEAN← FALSE,
type: TypeIndex--14 bits--],
free => [unused: [0..177B]← 0,
SizeHi: LongNodeSizeHi← 0,
pfnNext, pfnPrev: PFreeNode],
ENDCASE
];

NodeState: TYPE = MACHINE DEPENDENT {inuse(0), free(1)};

PNode: TYPE = LONG POINTER TO NodeHeader; -- "pn"
PFreeNode: TYPE = LONG POINTER TO free NodeHeader; -- "pfn"
InusePNode: TYPE = LONG POINTER TO inuse NodeHeader; -- "ipn"

fndNil: free NodeHeader = [body: free[0, 0, NIL, NIL]];
sizeNd: CARDINAL = SIZE[inuse NodeHeader]; -- overhead for an allocated prefixed node

LongNodeSizeLo: TYPE = CARDINAL;
LongNodeSizeHi: TYPE = [0..377B];
MinBlockSize: LongNodeSizeLo = SIZE[free NodeHeader];
LongNodeSize: TYPE = LONG CARDINAL;
LASTLongNodeSize: LongNodeSize = LAST[LONG CARDINAL]/256; -- 24 bits
MaxClientBlockSize: CARDINAL = LAST[CARDINAL] - 1; -- even size

-- procedures

MapPtrZf: PROC[ptr: LONG POINTER] RETURNS[ZoneFinger] = INLINE
{ RETURN[MapQZf[MapPtrQ[ptr]]]};
MapPtrQ: PROC[ptr: LONG POINTER] RETURNS[QuantumIndex] = INLINE
{ RETURN[PtrToQtmIndex[ptr]]};

MapRefZf: PROC[ref: REF ANY] RETURNS[ZoneFinger] = INLINE
{ RETURN[MapQZf[MapRefQ[ref]]]};
MapRefQ: PROC[ref: REF ANY] RETURNS[QuantumIndex] = INLINE
{ RETURN[MapPtrQ[LOOPHOLE[ref, LONG POINTER]]]};

MapSizeNq: PROC [size: LONG CARDINAL] RETURNS[QuantumCount] = INLINE
{RETURN[RTQuanta.QuantumSizeDIV[size+(BaseOverhead+QuantumSize-1)]]};

IsSubZoneVacant: PROC[sz: SubZone] RETURNS[BOOLEAN] = INLINE
{RETURN[sz.szi = sziVacant]};

GetZone: PROC[zi: ZoneIndex] RETURNS[Zone];

ReturnQuanta: PROC[pzn: PZone, q: QuantumIndex, nQ: QuantumCount];

AddBlock: PROC[ptr: LONG POINTER, size: LongNodeSize, pfnPrev: PFreeNode];

NodeLength: PROC[pn: PNode] RETURNS[LongNodeSize] = INLINE
{ lnds: MDRLongNodeSize;
lnds.lnsLo← pn.SizeLo;
WITH pnx: pn SELECT FROM
inuse => lnds.lnsHi← LOOPHOLE[0];
free => lnds.lnsHi← pnx.SizeHi;
ENDCASE;

lnds.unused← LOOPHOLE[0];
RETURN[LOOPHOLE[lnds, LongNodeSize]]};

-- used to make NodeLength fast
MDRLongNodeSize: TYPE = MACHINE DEPENDENT RECORD
[lnsLo: LongNodeSizeLo,
unused: [0..377B],
lnsHi: LongNodeSizeHi
];

AllocateZi: PROC RETURNS[zi: ZoneIndex];

GetZiNext: PROC RETURNS[zi: ZoneIndex];

SetZiNext: PROC[zi: ZoneIndex];

FromCollectibleZone: PROC[refObj: REF ANY] RETURNS[BOOLEAN] = INLINE
{ z: Zone;
zf: ZoneFinger;
IF LOOPHOLE[refObj, LONG CARDINAL] > RTQuanta.LASTAddress THEN RETURN[FALSE];
zf ← MapRefZf[refObj];
WITH zf: zf SELECT FROM
sub => ERROR;
prefixed => z ← MapZiZn[zf.zi];
ENDCASE;
RETURN[z # NIL]};

-- allocation procedures, e.g. to be put in ZONE objects
NewPrefixedObject: PROC[self: PrefixedZone, size: CARDINAL, type: Type] RETURNS[REF ANY];

CreatePrefixedTypedUObject: PROC[type: Type, size: CARDINAL, zn: PPrefixedZone]
RETURNS[ptr: LONG POINTER];

CreatePrefixedUObject: PROC[size: CARDINAL, zn: PPrefixedZone]
RETURNS[ptr: LONG POINTER];

FreePrefixedObject: PROC[self: PrefixedZone, object: REF ANY];

NewQuantizedObject: PROC[self: QuantizedZone, size: CARDINAL, type: Type]
RETURNS[REF ANY];

FreeQuantizedObject: PROC[self: QuantizedZone, object: REF ANY];

NewPrefixedHeapObject: PROC[self: LONG POINTER TO PPrefixedZone, size: CARDINAL]
RETURNS[LONG POINTER];

FreePrefixedHeapObject: PROC[self: LONG POINTER TO PPrefixedZone, object: LONG POINTER];

NewQuantizedHeapObject: PROC[self: LONG POINTER TO PQuantizedZone, size: CARDINAL]
RETURNS[LONG POINTER];

FreeQuantizedHeapObject: PROC[self: LONG POINTER TO PQuantizedZone,
object: LONG POINTER];

-- NOTE this is not an ENTRY proc!! It is meant to be called while debugging
SummarizeZone: PROC[zn: PZone]
RETURNS[nQuanta, freeQuanta, objectsInService, overheadCells, freeObjects,
cellsInService, freeCells, residueCells: LONG CARDINAL];

END.