-- 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 20, 1982 10:04 am by Paul Rovner
DIRECTORY
RTQuanta USING[QuantumSize, QuantumIndex, QuantumCount, QuantumSizeDIV,
LASTAddress, PtrToQtmIndex],
RTBases USING[BaseOverhead],
RTBasic USING[Base, Pointer, TypeIndex, Type],
SafeStorage USING [SizeRepresentation, ZoneFullProc],
UnsafeStorage USING [UZoneFullProc],
Runs USING [Run];
RTZones: DEFINITIONS IMPORTS RTQuanta SHARES RTBasic
= BEGIN
OPEN RTBasic, RTQuanta, SafeStorage, UnsafeStorage;
-- 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: SafeStorage.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: SafeStorage.ZoneFullProc, base: RTBasic.Base],
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: Pointer] RETURNS[ZoneFinger] = INLINE
{ RETURN[MapQZf[MapPtrQ[ptr]]]};
MapPtrQ: PROC[ptr: 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, Pointer]]]};
MapSizeNq: PROC [size: LONG CARDINAL] RETURNS[QuantumCount] = INLINE
{RETURN[RTQuanta.QuantumSizeDIV[size+(RTBases.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: 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];
AllocateSzi: PROC RETURNS[szi: SubZoneIndex];
GetZiNext: PROC RETURNS[zi: ZoneIndex];
GetSZiNext: PROC RETURNS[szi: SubZoneIndex];
GetnZiMax: PROC RETURNS[zi: ZoneIndex];
GetnSziMax: PROC RETURNS[szi: SubZoneIndex];
SetZiNext: PROC[zi: ZoneIndex];
GetSzZi: PROC[szi: SubZoneIndex] RETURNS[ZoneIndex] =
INLINE{RETURN[MapSziSz[szi].zi]};
GetSzSize: PROC[szi: SubZoneIndex] RETURNS[CARDINAL] = INLINE{RETURN[MapSziSz[szi].size]};
GetSzType: PROC[szi: SubZoneIndex] RETURNS[type: Type] = INLINE{RETURN[MapSziSz[szi].type]};
AssignSz: PROC[szi: SubZoneIndex, sz: SubZone];
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 => z ← MapZiZn[GetSzZi[zf.szi]];
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: Pointer];
CreatePrefixedUObject: PROC[size: CARDINAL, zn: PPrefixedZone]
RETURNS[ptr: 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];
-- Software support for the microcode, or for use instead of microcode
CreateQuantizedObjectTrap: PROC[zn: PQuantizedZone, size: CARDINAL, type: Type]
RETURNS[ptr: Pointer];
CreatePrefixedObjectTrap: PROC[zn: PPrefixedZone, size: CARDINAL, type: Type]
RETURNS[ptr: Pointer];
FreeObjectTrap: PROC[ptr: Pointer];
FreeQuantizedNodeTrap: PROC[ptr: Pointer, zn: PZone];
FreePrefixedNodeTrap: PROC[ptr: Pointer, zn: PZone];
AllocateQuantizedNodeSDTrap: PROC[zn: PQuantizedZone, size: CARDINAL, type: Type]
RETURNS[ptr: Pointer];
AllocateHeapNodeSDTrap: PROC[zn: PPrefixedZone, size: CARDINAL, type: Type]
RETURNS[ptr: 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.