-- 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.

Ęf˜Jš!œÇĎkœ
Ďc	œœ
œœ
œžœœœœĎnœ{Ÿ
œœœœ
œÉK˜ÜR—…—)^)Ę