RCMicrocodeImpl.mesa
Copyright © 1984 by Xerox Corporation. All rights reserved.
Software Implementation of the Cedar reference-counting microcode
Paul Rovner, January 13, 1984 4:34 pm
Bob Hagmann, May 10, 1984 4:26:55 pm PDT
Russ Atkinson, December 19, 1984 11:39:38 am PST
DIRECTORY
Allocator USING[FNHeaderP, NHeaderP, RefCount, maxSmallBlockSize, BlockSizeIndex, bsiEscape, NormalHeader],
AllocatorOps USING[REFToNHP, NHPToREF],
Basics USING[BITAND, BITOR, BITSHIFT, BITXOR, HighHalf, LowHalf],
Collector USING[Disposition],
PrincOpsUtils USING[ZERO],
RCMicrocodeOps USING[],
SafeStorage USING[Type, nullType],
ZCT USING[FOSTableIndex, FOSTableLength, FOSTableResidue, zctBlockWords, ZeroCountTable, zct, ZCTObject, FOSTableObject];
Stats
keepingStats: BOOL = TRUE;
stats: Stats ← [];
oldStats: Stats ← stats;
Stats:
TYPE =
RECORD [
assignRef:
INT ← 0,
# of ASSIGNREF[rhs, lhs]
assignRefNil:
INT ← 0,
# of ASSIGNREF where lhs^ = rhs & rhs = NIL
assignRefEq:
INT ← 0,
# of ASSIGNREF where lhs^ = rhs & rhs # NIL
assignRefLeft:
INT ← 0,
# of ASSIGNREF where lhs^ # NIL & rhs = NIL
assignRefRight:
INT ← 0,
# of ASSIGNREF where lhs^ = NIL & rhs # NIL
assignRefBoth:
INT ← 0
# of ASSIGNREF where lhs^ # NIL & rhs # NIL & lhs^ # rhs
];
SampleStats:
PROC
RETURNS [delta: Stats] = {
delta ← stats;
delta.assignRef ← delta.assignRef - oldStats.assignRef;
delta.assignRefNil ← delta.assignRefNil - oldStats.assignRefNil;
delta.assignRefEq ← delta.assignRefEq - oldStats.assignRefEq;
delta.assignRefLeft ← delta.assignRefLeft - oldStats.assignRefLeft;
delta.assignRefRight ← delta.assignRefRight - oldStats.assignRefRight;
delta.assignRefBoth ← delta.assignRefBoth - oldStats.assignRefBoth;
oldStats ← stats;
};
ERRORS
RCOverflowOccurred: PUBLIC ERROR = CODE;
RCUnderflowOccurred: PUBLIC ERROR = CODE;
LookFurtherAtReclaimedRef: PUBLIC ERROR = CODE;
ZCTFull: PUBLIC ERROR = CODE;
NormalFreeListEmpty: PUBLIC ERROR = CODE;
PROCEDURES
Software implementation of the Allocate MISC
zct must also include: sizeToBSI, bsiToFreeList, bsiToSize
Returns NIL IF size> Allocator.maxSmallBlockSize
may pageFault or raise ZCTFull or NormalFreeListEmpty; ifso, no changes have been made
ALLOCATE:
PUBLIC
PROC [size:
CARDINAL, type: SafeStorage.Type]
RETURNS[r:
REF ←
NIL] = {
IF ucDisabled THEN Allocate MISC TRAP with trapParam = 2
IF size <= maxSmallBlockSize
THEN {
bsi: BlockSizeIndex = zct.sizeToBSI[size];
fnhp: FNHeaderP ← zct.bsiToFreeList[bsi];
nhp: NHeaderP;
IF fnhp =
NIL
THEN
ERROR NormalFreeListEmpty;
Allocate MISC TRAP with trapParam = 6
nhp ← @fnhp.fnh;
r ← AllocatorOps.NHPToREF[nhp];
XXX touch nhp.type, .maybeOnStack, zct.markingDecrements, fnhp.nextFree
OnZ[nhp]; -- may pageFault or raise ZCTFull; ifso, no changes have been made
COMMITTED if here
zct.bsiToFreeList[bsi] ← fnhp.nextFree;
fnhp.nextFree ← NIL; -- CLEAR THE NEW OBJECT
nhp.type ← type;
nhp.maybeOnStack ← zct.markingDecrements;
};
};
Software implementation of the Free MISC
Returns FASE IF bsi = bsiEscape
may pageFault; ifso, no changes have been made
FREEPLEASE:
PUBLIC
PROC [nhp: NHeaderP]
RETURNS[success:
BOOL ←
FALSE] = {
IF ucDisabled THEN Allocate MISC TRAP with trapParam = 2
bsi: BlockSizeIndex = nhp.blockSizeIndex;
IF (success ← bsi # bsiEscape)
THEN {
fnhp: FNHeaderP = LOOPHOLE[nhp, FNHeaderP];
PrincOpsUtils.ZERO[nhp + SIZE[NormalHeader], zct.bsiToSize[bsi] - SIZE[NormalHeader]];
fnhp.fnh.type ← SafeStorage.nullType; -- mark the object as free
fnhp.nextFree ← zct.bsiToFreeList[bsi];
zct.bsiToFreeList[bsi] ← fnhp;
};
};
Software implementation of the AssignRef and AssignRefNew opCodes
This might pageFault or raise ZCTFull, RCOverflowOccurred or RCUnderflowOccurred
If this guy pageFaults or raises a signal no changes have been made
ASSIGNREF:
PUBLIC
PROC [rhs:
REF, lhs:
LONG
POINTER
TO
REF] = {
IF ucDisabled THEN opCode TRAP with trapParam = 2
lhs ← AddAlphaByte[lhs, XXX];
lhsRef: REF ← lhs^;
SELECT
TRUE
FROM
rhs = lhsRef => {
IF keepingStats
THEN
IF rhs =
NIL
THEN stats.assignRefNil ← stats.assignRefNil + 1
ELSE stats.assignRefEq ← stats.assignRefEq + 1;
};
rhs =
NIL => {
note: lhsRef # NIL
marking: BOOL = zct.markingDecrements;
lnhp: NHeaderP = AllocatorOps.REFToNHP[lhsRef];
lrc: RefCount ← lnhp.refCount;
Check for underflow and for reaching 0.
SELECT lrc
FROM
0 =>
IF lnhp.rcOverflowed
THEN
ERROR RCUnderflowOccurred
TRAP with trapParam = 3
ELSE
ERROR;
TRAP with trapParam = 5
1 =>
IF marking
OR
NOT lnhp.rcOverflowed
THEN OnZ[lnhp];
might raise RCUnderflowOccurred
ENDCASE => IF marking THEN OnZ[lnhp];
COMMITTED NOW to finish this call
IF keepingStats THEN stats.assignRefLeft ← stats.assignRefLeft + 1;
lnhp.maybeOnStack ← marking;
lnhp.refCount ← lrc - 1;
lhs^ ← rhs; -- NOT counted
};
lhsRef =
NIL => {
This is a simple case, and should happen for all first assignments to fields.
rnhp: NHeaderP ← AllocatorOps.REFToNHP[rhs]; -- subtract 2
rrc: RefCount ← rnhp.refCount;
IF rrc =
LAST[RefCount]
THEN
ERROR RCOverflowOccurred;
TRAP with trapParam = 1
COMMITTED NOW to finish this call
IF keepingStats THEN stats.assignRefRight ← stats.assignRefRight + 1;
rnhp.refCount ← rrc + 1;
rnhp.maybeOnStack ← FALSE;
lhs^ ← rhs; -- NOT counted
};
ENDCASE => {
Assert: lhsRef # NIL AND rhs # NIL AND rhs # lhsRef
marking: BOOL = zct.markingDecrements;
lnhp: NHeaderP = AllocatorOps.REFToNHP[lhsRef];
lrc: RefCount ← lnhp.refCount;
rnhp: NHeaderP ← AllocatorOps.REFToNHP[rhs];
rrc: RefCount ← rnhp.refCount;
IF rrc =
LAST[RefCount]
THEN
ERROR RCOverflowOccurred;
TRAP with trapParam = 1
Check for underflow and for reaching 0.
SELECT lrc
FROM
0 =>
IF lnhp.rcOverflowed
THEN
ERROR RCUnderflowOccurred
TRAP with trapParam = 3
ELSE
ERROR;
TRAP with trapParam = 5
1 =>
IF marking
OR
NOT lnhp.rcOverflowed
THEN OnZ[lnhp];
might raise RCUnderflowOccurred
ENDCASE => IF marking THEN OnZ[lnhp];
COMMITTED NOW to finish this call
IF keepingStats THEN stats.assignRefBoth ← stats.assignRefBoth + 1;
lnhp.maybeOnStack ← marking;
lnhp.refCount ← lrc - 1;
rnhp.refCount ← rrc + 1;
rnhp.maybeOnStack ← FALSE;
lhs^ ← rhs; -- NOT counted
};
IF keepingStats THEN stats.assignRef ← stats.assignRef + 1;
};
Software implementation of the OnZ microcode subroutine
This can pageFault or raise ZCTFull. If so, no changes have been made.
This is the only proc that
explicitly raises ZCTFull
changes zct.wp
sets nhp.inZCT ← TRUE
OnZ:
PUBLIC
PROC [nhp: NHeaderP] = {
IF
NOT nhp.inZCT
THEN {
wp: LONG POINTER TO NHeaderP;
wp ← zct.wp;
wp^ ← nhp;
-- might pageFault
wp will not point to the link word; wp^ may be left with garbage if ZCTFull is raised
IF Basics.
BITAND[Basics.LowHalf[
LOOPHOLE[wp,
LONG
CARDINAL]], zctBlockWords - 1]
= zctBlockWords - 2*SIZE[LONG POINTER]
THEN {
-- wp points to the cell before the link to the next zctBlock
IF (wp ←
LOOPHOLE[(wp+
SIZE[
LONG
POINTER])^,
-- pick up the link
LONG POINTER TO NHeaderP]) = NIL
THEN ERROR ZCTFull -- i.e. XXX TRAP with trapParam = 4
ELSE zct.wp ← wp;
now COMMITTED to finish this call
}
ELSE zct.wp ← wp + SIZE[LONG POINTER]; -- will NOT pageFault
nhp.inZCT ← TRUE; -- will NOT pagefault
};
};
Software implementation of the CreateRef MISC
CREATEREF:
PUBLIC
PROC [nhp: NHeaderP] = {
IF ucDisabled THEN CreateRef MISC TRAP with trapParam = 2
IF checking AND (nhp.refCount # 0 OR nhp.rcOverflowed) THEN ERROR;
OnZ[nhp]; -- may pageFault or raise ZCTFull; ifso, no changes have been made
nhp.maybeOnStack ← zct.markingDecrements;
};
Software implementation of the ReclaimableRef MISC
This may pageFault or raise ZCTFull; ifso, no changes have been made
RECLAIMABLEREF:
PUBLIC
PROC [nhp: NHeaderP]
RETURNS[Disposition] = {
IF ucDisabled THEN ReclaimableRef MISC TRAP with trapParam = 2
RETURN[MCRECLAIMABLEREF[nhp, FALSE]];
};
Software implementation of the MCRECLAIMABLEREF microcode subroutine
This is called from RECLAIMEDREF and from RECLAIMABLEREF
This may pageFault or raise ZCTFull; ifso, no changes have been made
MCRECLAIMABLEREF:
PROC [nhp: NHeaderP, decrPending:
BOOL]
RETURNS[d: Disposition ← continue] = {
rc: RefCount ← nhp.refCount;
IF decrPending THEN rc ← rc - 1; -- won't underflow
IF rc # 0 OR nhp.inZCT OR nhp.rcOverflowed THEN RETURN; -- leave it alone
IF nhp.maybeOnStack
OR FoundInFHSnapshot[nhp]
THEN OnZ[nhp] -- put it back; this may pageFault or raise ZCTFull
ELSE d ← (IF nhp.f THEN finalizeIt ELSE reclaimIt);
};
Software implementation of the FoundInFHSnapshot microcode subroutine
This is called only from MCRECLAIMABLEREF
FoundInFHSnapshot:
PROC [nhp: NHeaderP]
RETURNS[found:
BOOL ←
FALSE] = {
index: FOSTableIndex;
residue, entry: FOSTableResidue;
fosTable: LONG POINTER TO FOSTableObject = LOOPHOLE[zct+SIZE[ZCTObject]];
[index, residue] ← FOSTableHash[nhp];
entry ← fosTable[index];
RETURN[residue = Basics.BITAND[residue,entry]];
};
Software implementation of the FOSTableHash microcode subroutine
FOSTableHash:
PUBLIC
PROC [nhp: NHeaderP
--maybe bogus--]
RETURNS[x: FOSTableIndex, r: FOSTableResidue] = {
OPEN Basics;
lc: LONG CARDINAL = LOOPHOLE[nhp, LONG CARDINAL];
u: FOSTableResidue;
r ←
BITOR[
BITSHIFT[HighHalf[lc], 3],
BITSHIFT[LowHalf[lc], -13]];
r is all but the least significant 13 bits
u ← BITAND[r, zct.residueMask];
x ←
BITAND[
BITXOR[
BITSHIFT[LowHalf[lc], -1], u], FOSTableLength-1];
The hash function works as follows: assume the address of the REF is addr, and mask is the residue mask stored in the ZCT. The residue is addr[7..18]. The hash bucket is the low 12 bits of "(residue and mask) XOR addr[19..30]".
This works for addresses up to 25 bits in length, and can be easily extended if this is a constraint. Bit 31 is always zero (REFs are always even word alligned). The residue, mask, and the hash bucket uniquely defines the original address (since you know residue, you know addr[7..18]; now compute "(residue and mask) xor hash bucket" to get bits 19-30). Since we never use a page of VM in the first 64 pages of memory for collectable storage, the residue is never zero. The purpose of the residueMask is to change the set of REFs that collide from hash to hash. residueMask is changed at the start of an incremental collection. Note that if the mask was xor'ed in instead of being and'ed, then the location of the collisions, but not the REFs that colliside, would change from hash to hash.
};
Software implementation of the ReclaimedRef MISC
This might pageFault or raise ZCTFull, RCUnderflowOccurred or LookFurtherAtReclaimedRef
This is the only proc that raises LookFurtherAtReclaimedRef explicitly
If this proc pageFaults or raises a signal then no changes have been made.
RECLAIMEDREF:
PUBLIC
PROC [ref:
REF]
RETURNS [ans:
REF
ANY ←
NIL] = {
nhp: NHeaderP = AllocatorOps.REFToNHP[ref];
IF ucDisabled THEN ReclaimedRef MISC TRAP with trapParam = 2
CheckForRCUnderflow[nhp]; -- might raise RCUnderflowOccurred
SELECT
MCRECLAIMABLEREF[nhp,
TRUE]
FROM
continue => NULL;
reclaimIt => ans ← ref;
finalizeIt =>
ERROR LookFurtherAtReclaimedRef;
ReclaimedRef MISC TRAP, trapParam = 6
ENDCASE => ERROR;
nhp.refCount ← nhp.refCount - 1;
};
Software implementation of the CheckForRCUnderflow microcode subroutine
This is called only from ASSIGNREF and from RECLAIMEDREF
CheckForRCUnderflow:
PROC [nhp: NHeaderP] = {
rc: RefCount ← nhp.refCount;
IF checking
AND rc = 0
AND
NOT nhp.rcOverflowed
THEN
ERROR;
i.e. XXX TRAP with trapParam = 5
IF rc = 0
--was RCMicrocodeOps.rcBottom--
AND nhp.rcOverflowed
THEN ERROR RCUnderflowOccurred; -- no changes have been made
i.e. XXX TRAP with trapParam = 3
};
Software implementation of the DisableMicrocode MISC.
In addition to "disabling" rc microcode, this guy should cause the store of ucode registers back into memory (zct^).
DISABLEMICROCODE:
PUBLIC
PROC [z: ZeroCountTable] = {
cause rc operations to trap (except EnableMicrocode)
NULL; -- the real uc: ucDisabled ← TRUE
};
Software implementation of the EnableMicrocode MISC
In addition to "enabling" rc microcode, this guy should load ucode registers from memory (zct^).
ENABLEMICROCODE:
PUBLIC
PROC [z: ZeroCountTable]
RETURNS [ucVersion:
NAT] = {
RETURN[0]; -- the real uc: ucDisabled ← FALSE
};