[Cyan]<D0Docs>OldCedarOpcodes.Bravo!1

In addition to regular Mesa opcodes, Rubicon Cedar uses 16 ESC and one regular opcode to manage Cedar collector, type machinery, and allocation. Paul Rovner judged these activities frequent enough to warrant microcode implementation. I think that collector opcodes used about 15% to 20% of all cycles on the Dolphin when they trapped and were emulated by Mesa procedures; microcoding reduced the time to about 2% of all cycles. Microcoding the GetRefType and GetCRefType opcodes was also worth about 10% to 15%--these are just guesses, not measured results. Implementation of the trap procedures could perhaps have been made faster with no prospect for microcode implementation, in which case the advantage of special microcode would be less.

Collector opcodes are primarily concerned with managing a data structure that controls the incremental garbage collector. Each collectable object is identified by a 32-bit pointer to its origin (Ref) and has a Reference Count Entry (RCE) which contains the RefCnt for the object; for Rubicon Cedar the virtual memory (VM) size is assumed to be 22 bits, and this size limit is embedded in the RCE format; furthermore, objects are required to start on 32-bit boundaries, so Refs are always even--effectively only 21 bits.

Cedar knows how to enumerate all Refs in collectable storage. In other words, it knows which fields contain Refs in every type of object and can find the type of any referent. It does this through data structures which will be discussed in a later section. In addition, each pointer to a collectable object is to its base, not to its interior, which simplifies the algorithm for mapping Refs to RCEs.

The Cedar collector provides for "package references" within a client program’s own allocation package. By offsetting RefCnt by the number of package references, the client’s allocator can be notified by the collector when one of its objects has fallen into disuse. To allow for package references within the allocation machinery, RefCnt is offset by a constant RCFinalize (.eq. 3). RefCnt .eq. RCFinalize indicates no user references; RCFinalize+1 indicates 1 user pointer, etc. RCFinalize .eq. 3 allows up to 2 package references within a client’s allocator. So RefCnt .gr. RCFinalize indicates "in use"; 1 to RCFinalize means "collectable", "being finalized", or "just created"; 0 is an illegal value for the convenience of microcode error checks. RefCnt will be correct so long as it does not reach its maximum value (177b for Rubicon); if the maximum value is ever reached, then RefCnt will freeze at that value and the referent will become incrementally uncollectable--this situation is referred to as a "pinned reference count".

Consequently, an unpinned RefCnt will be correct for all pointers in storage except those in local frames and process evaluation stacks. These other potential Refs are guarded by a conservative marking algorithm applied at the onset of a collection--the OnStack bit is set to 1 in each RCE which might be pointed at from some uncounted place. The exact methods of handling the OnStack bit are discussed below. The essential property of this bit is that it tells the collector not to reclaim an object.

The algorithm should estimate what resources (VM, RCE’s, FL cells, blocks of some particular type, etc.) will be recovered by the collection, vs. the resources (CPU time, disk thrashing, storage, etc.) taken from other uses by the collection. To help in this estimation, the collector opcodes keep an exact count of the number of RCEs with RefCnt .eq. RCFinalize--these are the top level collectable objects barring OnStack marking. For each object collected, there may be subsidiary objects pointed at by Refs inside the first--each of these will have RefCnt decremented, and some will become collectable. Statistics from past collections or the allocator may improve the guess about object sizes and words collected as a function of top level collectable objects. I am not sure what the Collector does at present.

(4) When a collection starts, the Collector sets OnStack=1 in RCEMask and executes a GCSetup to transmit the RCEMask change to microcode, in case the RCEMask word is cached. The only operations affected by OnStack in RCEMask are CreateRef and AssignRef, which sets OnStack=1 when decrementing RefCnt as described later.

(5) The collector then carries out OnStack marking in high priority mode. During this phase, no other Cedar processes run. Every word pair in a local frame or evaluation stack of a Cedar process is examined for the possibility of its being a Ref; if it is possibly a Ref, then it is marked OnStack. In the present system, the rules for weeding out non-Refs are as follows: (a) If the doubleword value is odd, then it is not a Ref; (b) if it does not point at collectable storage, it is not a Ref. The Collector uses the AlterCount opcode for OnStack marking.

After OnStack marking, regular processes can execute CreateRef and AssignRef as usual, while the Collector is running in the background. However, if the reason for the collection is that some crucial resource has been exhausted, the other Cedar processes will wind up deferring to the collector. However, OnStack will wind up being set in RCEs created by CreateRef and in RCEs modified by AssignRef in which RefCnt winds up .le. RCFinalize, so garbage created during the collection itself will not be reclaimed until a subsequent collection.

(6) After OnStack marking, the Collector enumerates RCEs with RefCnt<=RCFinalize and OnStack=0 using the ReclaimAll opcode. For each of these, software determines whether reclaim is possible; if so, the ReclaimRef opcode is applied to Refs inside the object, and any of these having its RefCnt decremented to RCFinalize is handled in the same way as those enumerated by ReclaimAll (If RefCnt for one of these was already .le. RCFinalize, then ReclaimAll already enumerated or will enumerate it, so no futher action is necessary).

(7) When done, the collector sets OnStack mode for client processes to normal again and uses the ResetOnStack opcode to sweep the collector data structure and clear all OnStack bits. Any RCEs created for non-Ref doublewords during OnStack marking will be purged at this time.

This completes the general plan for an incremental collection. A trace and sweep collection becomes necessary when the quantity of dead but uncollectable resources (because of circularities or pinned reference counts) becomes too large; a trace and sweep is also necessary when the incremental collector’s data structure overflows and becomes unusable or when some bug is detected that indicates the incremental collector’s data structure has become unreliable. In an environment where programs ran for a long time, a compactor would also be necessary, which Cedar presently does not have--a conservative compactor along the lines of the conservative collector would prevent excessive storage fragmentation.

We next turn to details of the data structure in which RCEs are kept. The collector uses a contiguous 64k-aligned block of storage. The GC base register points at its origin and all pointers in the hash table (HT) and overflow table (OT) are relative to GC. Words of interest are as follows:

0FLdisplacement to 1st cell on free list
1FLCount
biased count of OT free list cells; trap when an OT cell is
needed and FLCount .le. 0 unless collector is running.
2RCEMask
00 if ref-counting allowed; 1 if ref-counting disabled
1:7RCEMask (always 177b)
8dOnStack (0 normally, 1 during a collection)
9:15dzeroes
3ProcNo
Collector process id (.eq. 0 when collector not running)
4- 5LP to table indexed by Ref rsh 10d containing zone (.ge 0)
or zone index (.ls. 0).??
6- 7LP to table describing zones by subzones
10- 11LP to table indexed by zone index containing LP to zone
12- 13LP to table indexed by type containing LP to canonical type
14- 15Count of HT or OT entries with RefCnt .eq. RCFinalize.
16- 113unused
114- 177Optional counters (defined for Mesa debugger prettyprint--
these counts don’t necessarily occur) defined later.
200- 377table for entries with RefCnt<=RCFinalize on ReclaimAll
400-100377HT (hash table--16 bits/cell)
100400-177777OT (overflow table--32 bits/cell, length determined by
software)

The free list pointed to by FL threads through even words of OT cells and is terminated by a 0 (odd word values are ’don’t care’). FLCount is initialized to the number of cells on the free list minus a parameter. Any process except the Collector which tries to allocate a new OT cell and finds FLCount .le. 0 will trap; trap software then wakes the Collector and blocks. The Collector process can acquire OT cells until the free list is entirely exhausted (denoted by a 0 pointer in FL).

The reason why FLCount must be biased is that, unfortunately, the Collector itself creates additional RCE’s during its OnStack marking phase and, potentially, during later phases of the collection; running out of OT cells will crash, so FLCount must be sufficiently biased that OT cells won’t be exhausted during a collection.

An RCE is accessed by hashing a 21-bit Ref into a 15-bit probe index (PI) and 6-bit residue (R). PI is bits 10:15d xor bits 16:30d; R = bits 10:15d; PI indexes HT, formatted as follows: A one-long chain is contained within the HT cell; otherwise, HT points to an OT cell containing a RCE in the 1st word and either a RCE or a pointer to another OT cell in the 2nd word. Every word in HT or OT has the following form:
If bit 0 is 0, the word is a RCE:
1:7RefCnt
8OnStack
9:15Residue (allows one extra bit)
else if bit 0 is 1, the word is a pointer or empty:
0:15dindex of next OT cell in chain (always even);
-1 denotes an empty entry (HT only--illegal in OT)

In other words, if only one RCE is to be found at a particular PI, then that RCE is in HT. If two RCE’s are to be found, then HT points at an OT cell containing both RCE’s; if three RCE’s are to be found, then HT points at an OT cell containing the first RCE and a pointer to a second OT cell containing two RCE’s. The OT chain is always dense, so the final entry on the chain will always contain two RCE’s--there are no "empty" entries in an OT chain.

In addition, a clever space-bumming trick greatly reduces the size of HT/OT. RCE’s with RefCnt .eq. RCFinalize+1 and OnStack .eq. 0 are discarded; this is the most common size, accounting for over 90% of of all non-garbage RCE’s. In other words, when RefCnt is being changed for a Ref not in HT/OT, RefCnt .eq. RCFinalize+1 and OnStack .eq. 0 is assumed; the RCE is recreated and modified appropriately. When RefCnt becomes .eq. RCFinalize+1, the RCE is discarded from HT/OT.

127dRemains 127d.127dRemains 127d.
RCFinalizeDestroy RCE.0Crash--bug.
no entryCreate with RefCntRCFinalize+2Destroy RCE if OnStack=0.
.eq. RCFinalize+2,no entryCreate with RefCnt=RCFinalize
OnStack=don’t care.OnStack=(RCEMask & OnStack).
.ls. RCFinalizeRefCnt ← RefCnt+1otherRefCnt ← RefCnt-1
preserving OnStack.preserving OnStack.
.gr. RCFinalizeRefCnt ← RefCnt+1,
OnStack=0 or preserved.
The above table is correct except for the ReclaimRef opcode: When there is no RCE, ReclaimRef will not recreate the RCE, as discussed in the opcode definitions below.

There are pitfalls when modifying RefCnt. One safe procedure would be to always set OnStack=1 during a collection whenever RefCnt is modified other than by the ReclaimRef opcode. However, zeroing OnStack is desirable when incrementing or decrementing RefCnt to RCFinalize+1, so that the RCE will not consume table space; if this were not done, then unnecessary RCEs could accumulate during a collection, while the collector is running in the background. For this reason, the more complicated algorithm above (still believed safe) is used.

The essential properties of the algorithm above with respect to OnStack are that whenever an AssignRef changes RefCnt to some value .le. RCFinalize during a collection, OnStack=1; but when an AssignRef increments RefCnt to RCFinalize+1, OnStack is zeroed so that the RCE can be deleted from the table. This works because any old Ref whose RefCnt is reduced by AssignRef must be "accessible", so some valid path exists to the old Ref; then the only way the object can be erroneously collected is if, after the AssignRef and before the Collector gets to it, that path becomes invalid. However, any AssignRef which makes any object in that path invalid (by decrementing its RefCnt to RCFinalize) will set OnStack=1, so the path can’t become invalid during the collection.

Although trap software exists for all Rubicon Cedar opcodes, it is an "all or nothing" bag--all opcodes which touch RCE’s must be microcoded or none. This is because preemption on a uniprocessor only happens between opcodes (Page faults are dealt with appropriately as well.), and the opcodes do not deal with the monitor locks used by the trap software. The following is a description of the opcodes:

GCSetup (Esc opcode)
At call:
0Sthe 64k bank number of the collector data structure, copied into
a base register only during initialization.
1S.ls. 0 to refetch all cached pointers and counters from storage;
.ge. 0 to copy cached pointers and counters into storage, while
loading the collector process number and RCMask into registers
from storage.
At exit:The two stack arguments are replaced by a 16-bit microcode version number.

Pointers and counters in the first 200b words of the 64k GC bank may optionally be cached in registers. GCSetup is executed once in initialization mode at the beginning of the world to load microcode counters from storage; it is executed again in update mode at the onset and end of each collection to post cached values back into storage and to update ProcNo. The two most important values to cache in registers are FL and FLCount; the next three most important are the RCMask, ProcNo, and the counter of the number of RCE’s with RefCnt .eq. RCFinalize. GCSetup ensures that software and microcode are "in sync" at crucial times. Caching these values in registers works in Rubicon because there is only one processor, and the values are modified only by microcode.

Create a RCE with RefCnt=RCFinalize-NPR. At the onset of the opcode, the RCE for the Ref may legitimately be in one of three states: (1) Non-existent; (2) RefCnt=RCFinalize+1 and OnStack=1 representing a false entry due to the collector’s conservative OnStack marking algorithm; (3) RefCnt=exactly what CreateRef would have put there had there been no RCE--this happens if the trace and sweep collection has just occurred and created an entry with RefCnt exactly equal to the value CreateRef would store into the entry. For cases (1) and (2), RefCnt is set to RCFinalize-NPR, and OnStack is set to the value in RCEMask. For case (3), if the trace and sweep is still running, the opcode traps with TrapParm=2; otherwise the opcode is a no-op.

AssignRef (Regular opcode)
At call:
(0S,,1S)long pointer to an object.
(2S,,3S)new Ref
alphadisplacement from the origin of the object to a doubleword containing
a Ref--this doubleword need not be 32-bit aligned.
At exit: Both args have been popped from the stack.

Alternatively, if the collector is not disabled (the normal case), then the following sequence of actions is carried out:
(1) If the old Ref is nil (0), then goto step 3; else RefCnt for the old Ref is decremented by 1 (see the earlier table for what happens in the special cases).
(2) Store nil into the doubleword.
(3) If the new Ref is nil, then done; else increment RefCnt for the new Ref.
(4) Store the new Ref into the doubleword.

It is possible to page fault or run out of OT cells on either RefCnt operation or to page fault or trap on the read of alpha+long pointer. A write protect fault is also possible on the write of either word (because the 2nd word might lie on a different page from the 1st) of alpha+long pointer, but this is assumed a crash condition and not handled safely.

There is no way to avoid the extraneous write of nil. If this is not done, then a page fault on the new Ref’s RCE update will produce an inconsistency between a pointer in storage and its associated RefCnt as follows:
1) Suppose new Ref’s RefCnt is one too small because a page fault aborts new Ref’s RCE update AFTER writing refNew. Another process could intervene with an AssignRef to the same alpha+long pointer and new Ref’s RefCnt would wind up one too small--disaster.
2) Alternatively, suppose new Ref’s RCE update occurs BEFORE writing refNew. Then, if another process intervenes and does an AssignRef to the same alpha+long pointer, then old Ref’s RefCnt will wind up one too small--disaster.

Since the store of new Ref and its RCE update cannot be done in a safe order, only by delaying the update of old Ref’s RCE until certain that new Ref’s RCE won’t fault is it possible to proceed safely, but the write of nil occurs in lieu of this in Rubicon.

If it was necessary to worry about safe execution in the presence of write protect faults, then a WP fault could happen when storing either word of nil at alpha+long pointer. This would be disastrous. Only by rewriting old Ref after reading it, then writing nil as an intermediate value after updating old Ref could the code be safe against this event also.

When decrementing RefCnt for the old Ref, set OnStack=RCMask&OnStack. We do this because of the following sequence:
(1) Collector completes its OnStack marking phase;
(2) Process A does a push of RefX on its stack preparatory to an AssignRef;
(3) Process B completes an AssignRef deleting the last pointer to RefX;
(4) The Collector finishes;
(5) Process A continues but RefX has been collected.
The DeleteRef part of Process B’s AssignRef must set OnStack=1 to protect Process A. An enumeration algorithm might legitimately touch objects in this way, so ruling out this case with a programming restriction is undesirable.

ReclaimAll searches HT starting at PI=0S for entries with RefCnt .le. RCFinalize & OnStack=0; if none are found then it increments 0S, checks for interrupts, and loops. If an RCE is found, then all such at that PI are stored into the 200b-word reclaim table in the GC structure, and the count of these is pushed onto 0S, leaving PI at 1S. When the last PI has been scanned, 0S=0 is returned, indicating completion. Software is expected to service all RCEs returned by ReclaimAll, and to reexecute ReclaimAll at PI+1 until a 0 count is returned. Algorithm makes use of the fact that RCFinalize is 3 (i.e., 2↑n-1), so Anding by 76200 will be 0 iff the RCE should be enumerated.

AlterCount (Esc opcode)
At call:
0S,,1SRef.
2SRCE modifier in RCE format--RefCnt field is twos-complement added to the
RefCnt field of the RCE and OnStack field is OR’ed into the OnStack
field of the RCE. In other words, OnStack is conditionally set to 1.
At exit:Arguments are popped from the stack; returns nothing.

This opcode is used to modify the values in RCE’s in more-or-less arbitrary ways, but its envisioned use is only in the following situations:
(1) To set OnStack=1 for pointers in local frames and process evaluation stacks at the onset of a collection. The conservative algorithm may use bogus Refs during this phase.
(2) To reenter a RCE found absent by ReclaimRef that cannot be reclaimed for some reason (subtract 1 from RefCnt field).
(3) To destroy a Ref whose RCE was returned by ReclaimAll (Add n to RefCnt such that the old RefCnt+n=RCFinalize+1).
(4) By the trace-and-sweep collector when rebuilding HT/OT.

If an RCE for the Ref exists, ReclaimRef subtracts 1 from RefCnt and returns nil; if no RCE exists (indicating RefCnt=RCFinalize+1 & OnStack=0), it returns the Ref unchanged. ReclaimRef is used by the collector for each Ref within a reclaimed object. Since RCEs which already had RefCnt .le. RCFinalize & OnStack=0 were (or will be) enumerated by ReclaimAll or by an earlier ReclaimRef, only those being decremented from RCFinalize+1 to RCFinalize need be reported. Note that a new RCE is not created--the collector must subsequently do an AlterCount -1 to fixup RefCnt if it doesn’t collect the object for some reason.

This opcode resets all OnStack bits at the end of a collection. It sequences through the chain at each PI, clearing all OnStack bits; this may eliminate an RCE altogether if RefCnt=RCFinalize+1. Then it increments the PI at 0S, checks for interrupts, and loops.

Zeroes the block using 0S as a state variable across interrupts. The AssignRef opcode requires that doublewords containing Refs be zeroed initially, so that the old Ref will be nil when AssignRef is executed; similarly, the trace and sweep collector requires that storage being allocated for an object have nil in all fields which are pointers to Refs before that storage becomes an object.

AssignRef, CreateRef, and AlterCount use two principal subroutines, "Find" and "Store", to do most of the work in the HT/OT data structure. "Find" in essence converts a Ref into the following results:
its RCE;
a pointer to the HT/OT word holding the RCE;
a pointer to the "predecessor" of that place;
the contents of the other word of the OT cell (if from an OT cell).
An absent entry (RefCnt .eq. RCFinalize+1) is recreated with OnStack=0.

The caller of "Find" always modifies the RefCnt or OnStack fields of the RCE and then calls "Store" to dispose of the results. "Store" distinguishes the three cases as follows:
If predecessor .eq. location of RCE, then RCE is in HT;
If predecessor .ne. location of RCE and location of RCE odd, then entry is
in odd word of OT cell;
If predecessor .ne. location of RCE and location of RCE even, then entry is
in even word of OT cell.
"Store" will check for RefCnt .eq. RCFinalize+1 and OnStack=0; if so, it destroys the RCE and collapses the HT/OT structure appropriately. Collapsing consists of storing "empty" in HT (if no OT cells were involved), or of copying the other word of the OT cell into the predecessor and chaining the FL cell onto the free list.

In Trinity Pilot, only Esc and EscL opcodes are assigned a special table for trapping--this is more general than Rubicon Pilot, but does not include the additional trap table for regular opcodes thrown in for Rubicon Cedar. This seemed to make sense for Trinity, where it was assumed that all regular opcodes would exist in microcode and not trap. However, it presents a problem for the AssignRef regular opcode. Unlike other regular opcodes, AssignRef could trap, even though it were implemented in microcode (which be not necessarily true either). To avoid this problem in Trinity, AssignRef traps as though it were the Esc 0 opcode, which can’t trap.

0OTCarNotEntryEven word of OT cell not a RCE (.ls. 0)
1BadOTPointerPointer in HT or OT .ls. OTOffset
2RefNotEvenRef arg not even
3BadCreateCreateRef on already-existing RCE with OnStack=0
4RCBelowZeroAttempt to make RefCnt<0
6? reported by Dorado microcode.
7BadMapIndexTable index .gr. word 0 of the table
10bReferentOnFL
11bBadFLPointer1Pointer from free list odd
12bBadFLPointer2Pointer from free list .ls. 100400b.
13bDelBadPtrPointer added to FL not even or .ls. 100400b
14bBadPackRefCntPackage reference count not in range 0 to 2.

The GC structure includes a number of 32-bit counters that hold various kinds of information. Most of these counters are not algorithmically important--they were put in at one time so we could monitor how often some opcode was being executed or some event happened. There is no guarantee that one of these counters is, in fact, implemented, though software exists to display some of them.

However, some other counters could be algorithmically important. One proposed algorithm for deciding when to do a collection needs the best guess possible for the amount of storage reclaimable by a collection. An estimate for this quantity can be made by estimating:
(1) No. Refs enumerated by ReclaimAll that will be freed;
(2) Expected number of Refs reclaimed for each one enumerated;
(3) Expected size of each item reclaimed.
(1) can be approximated by the number of Refs with RefCnt=RCFinalize now minus some kind of correction for the number of these that will be marked OnStack. (2) can be estimated by its historical average. (3) can be estimated either by tracking block size and number of frees in previous collections, by tracking storage allocated since the last collection, or in some similar way.

ACZeroCtr, ACSubCtr, ACAddCtr, OTDelCtr, OTCreCtr, HTDelCtr, HTCreCtr are displayed by software as of 18 February 1982, but not used algorithmically (therefor can change or deimplement). Dorado has the AC*Ctrs used for all Find calls not just AlterCount calls.

114bFreeQCtrFreeQuantized completions
116bFreeHCtrFreeHeap completions
120bFreeObjCtrFreeObject completions
122bAllocQCtrAllocate Quantized completions
124bAllocHCtrAllocate Heap completions
126bRefTypeCtrRefType completions
130bCRefTypeCtrCRefType completions
132bACIllCtrAlterCount calls with NIL or odd Ref arg.
134bACZeroCtrAlterCount completions not changing RefCnt
(must be setting OnStack=1).
136bACSubCtrAlterCount completions subtracting from RefCnt (must
be fixing RefCnt for a ReclaimRef which found no RCE
but had finalization).
140bACAddCtrAlterCount completions adding to RefCnt (must be
flushing RCE delivered by ReclaimAll).
142bOTDelCtrOT cell deletions
144bOTCreCtrOT cell creations
146bHTDelCtrHT deletions
150bHTCreCtrHT creations
1532bRRNilCtrReclaimRef completions with NIL arg
154bRRNoDelCtrReclaimRef completions (not deleted)
156bRRDelCtrReclaimRef completions (already deleted)
162bRACtrReclaimAll completions
164bCRCtrCreateRef completions
166bARCtrAssignRef completions refNew non-NIL
(not including those with the collector disabled).
172bRONilCtrRefOld=NIL in AssignRef (+ page fault restarts
and collector disabled AssignRefs as an error term)
174bRNNilCtrAssignRef completions with RefNew=NIL
176bROeqRNCtrRefOld=RefNew in AssignRef

Ref rshift 12d is the index into the quantum map, a table in which word 0 is the number of entries N, and words 1 to N are the entries. The pointers to the quantum and subzone maps are obtained from the GC structure. If the Ref is Nil, return 0 (NilType); otherwise, read the QMap word for the Ref at QMap[(Ref rsh 12d) + 1]. If QMap entry .ge. 0, Ref points at a prefixed object with type in the right 14d bits at Ref[-1]. Otherwise, 2*(QMap entry)+1 is an index to the subzone map, which has table length in word 0 and long pointers at words 1-2, 3-4, etc. The long pointer in this table points at the word containing the type.

Trap with parameter=1 if not canonicalized yet. The type of the Ref is determined in the same way as the RefType opcode. The CMap table is another table of long pointers pointed at by the GC structure in which the length of the table is in word 0 and the long pointers in words 1-2, 3-4, etc. If the type is less than the table length, then return the word pointed at by the long pointer in the CMap table; otherwise, give the not-canonicalized-yet trap.