[Cyan]<Cedar6.1>SafeStorage>RCMicrocodeImpl.mesa!1

RCMicrocodeImpl.mesa

Software Implementation of the Cedar reference-counting microcode

Initially: Paul Rovner, January 13, 1984 4:34 pm

Bob Hagmann, May 10, 1984 4:26:55 pm PDT

Russ Atkinson (RRA) April 9, 1986 5:03:07 pm PST

DIRECTORY

Allocator USING [FNHeaderP, NHeaderP, RefCount, maxSmallBlockSize, BlockSizeIndex, bsiEscape, NormalHeader],

AllocatorOps USING [NHPToREF, REFToNHP],

Basics USING [BITAND, BITOR, BITSHIFT, BITXOR, HighHalf, LowHalf],

Collector USING [Disposition],

PrincOpsUtils USING [LongZero],

RCMicrocodeOps USING [],

RCMicrocodeStats USING [Stats, StatsPtr],

SafeStorage USING [Type, nullType],

UnsafeStorage USING [GetSystemUZone],

ZCT USING [FOSTableIndex, FOSTableLength, FOSTableResidue, zctBlockWords, ZeroCountTable, zct, ZCTObject, FOSTableObject];

RCMicrocodeImpl: PROGRAM

all but FOSTableHash are really INTERNAL procs of the ZCTImpl monitor

IMPORTS AllocatorOps, Basics, PrincOpsUtils, UnsafeStorage, ZCT--zct--

EXPORTS RCMicrocodeOps

= BEGIN OPEN Allocator, Collector, RCMicrocodeStats, ZCT;

FLAGS

checking: BOOL = FALSE;

ucDisabled: BOOL; private flag kept in ucode registers

Stats

keepingStats: BOOL ← TRUE;

stats: PUBLIC StatsPtr ← UnsafeStorage.GetSystemUZone[].NEW[Stats ← []];

oldStats: StatsPtr ← UnsafeStorage.GetSystemUZone[].NEW[Stats ← stats^];

elems: NAT = SIZE[Stats]/SIZE[INT];

SampleStats: PUBLIC PROC RETURNS [delta: Stats] = {

new: LONG POINTER TO ARRAY [0..elems) OF INT ← LOOPHOLE[LONG[@delta]];

old: LONG POINTER TO ARRAY [0..elems) OF INT ← LOOPHOLE[oldStats];

delta ← stats^;

FOR i: [0..elems) IN [0..elems) DO

new[i] ← new[i] - old[i];

ENDLOOP;

oldStats^ ← stats^;

};

ERRORS

RCOverflowOccurred: PUBLIC ERROR = CODE;

RCUnderflowOccurred: PUBLIC ERROR = CODE;

LookFurtherAtReclaimedRef: PUBLIC ERROR = CODE;

ZCTFull: PUBLIC ERROR = CODE;

NormalFreeListEmpty: PUBLIC ERROR = CODE;

PROCEDURES

ALLOCATE: PUBLIC PROC [size: CARDINAL, type: SafeStorage.Type] RETURNS[r: REF ← NIL] = {

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

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;

IF keepingStats THEN stats.createRef ← stats.createRef + 1;

};

FREEPLEASE: PUBLIC PROC [nhp: NHeaderP] RETURNS[success: BOOL ← FALSE] = {

Software implementation of the Free MISC

Returns FASE IF bsi = bsiEscape

may pageFault; ifso, no changes have been made

IF ucDisabled THEN Allocate MISC TRAP with trapParam = 2

bsi: BlockSizeIndex = nhp.blockSizeIndex;

IF (success ← bsi # bsiEscape) THEN {

fnhp: FNHeaderP = LOOPHOLE[nhp, FNHeaderP];

PrincOpsUtils.LongZero[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;

};

ASSIGNREF: PUBLIC PROC [rhs: REF, lhs: LONG POINTER TO REF] = {

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

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 => {

might raise ZCTFull

IF marking OR NOT lnhp.rcOverflowed THEN OnZ[lnhp];

};

ENDCASE => IF marking THEN OnZ[lnhp];

IF keepingStats THEN {

stats.assignRefLeft ← stats.assignRefLeft + 1;

IF NOT lnhp.rcOverflowed THEN SELECT lrc FROM

1 => stats.downToZero ← stats.downToZero + 1;

2 => stats.downToOne ← stats.downToOne + 1;

ENDCASE;

};

COMMITTED NOW to finish this call

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

IF keepingStats THEN {

stats.assignRefRight ← stats.assignRefRight + 1;

IF NOT rnhp.rcOverflowed THEN SELECT rrc FROM

0 => stats.upToOne ← stats.upToOne + 1;

1 => stats.upToTwo ← stats.upToTwo + 1;

ENDCASE;

};

COMMITTED NOW to finish this call

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 => {

might raise ZCTFull

IF marking OR NOT lnhp.rcOverflowed THEN OnZ[lnhp];

};

ENDCASE => IF marking THEN OnZ[lnhp];

COMMITTED NOW to finish this call

IF keepingStats THEN {

stats.assignRefBoth ← stats.assignRefBoth + 1;

IF NOT rnhp.rcOverflowed THEN SELECT rrc FROM

0 => stats.upToOne ← stats.upToOne + 1;

1 => stats.upToTwo ← stats.upToTwo + 1;

ENDCASE;

IF NOT lnhp.rcOverflowed THEN SELECT lrc FROM

1 => stats.downToZero ← stats.downToZero + 1;

2 => stats.downToOne ← stats.downToOne + 1;

ENDCASE;

};

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;

};

OnZ: PUBLIC PROC [nhp: NHeaderP] = {

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

IF NOT nhp.inZCT THEN {

wp: LONG POINTER TO NHeaderP ← zct.wp;

wp^ ← nhp;

beware: 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

wp ← LOOPHOLE[(wp+SIZE[LONG POINTER])^, LONG POINTER TO NHeaderP];

IF wp = 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

IF keepingStats THEN stats.onZCT ← stats.onZCT + 1;

nhp.inZCT ← TRUE; -- will NOT pagefault (in microcode)

};

CREATEREF: PUBLIC PROC [nhp: NHeaderP] = {

Software implementation of the CreateRef MISC

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;

IF keepingStats THEN stats.createRef ← stats.createRef + 1;

};

RECLAIMABLEREF: PUBLIC PROC [nhp: NHeaderP] RETURNS[Disposition] = {

Software implementation of the ReclaimableRef MISC

This may pageFault or raise ZCTFull; ifso, no changes have been made

IF ucDisabled THEN ReclaimableRef MISC TRAP with trapParam = 2

RETURN[MCRECLAIMABLEREF[nhp, FALSE]];

};

MCRECLAIMABLEREF: PROC [nhp: NHeaderP, decrPending: BOOL] RETURNS[d: Disposition ← continue] = {

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

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);

};

FoundInFHSnapshot: PROC [nhp: NHeaderP] RETURNS[found: BOOL ← FALSE] = {

Software implementation of the FoundInFHSnapshot microcode subroutine

This is called only from MCRECLAIMABLEREF

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]];

};

FOSTableHash: PUBLIC PROC [nhp: NHeaderP--maybe bogus--] RETURNS[x: FOSTableIndex, r: FOSTableResidue] = {

Software implementation of the FOSTableHash microcode subroutine

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.

};

RECLAIMEDREF: PUBLIC PROC [ref: REF] RETURNS [ans: REF ANY ← NIL] = {

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.

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;

IF keepingStats THEN {

stats.reclaimedRef ← stats.reclaimedRef + 1;

SELECT nhp.refCount FROM

1 => stats.downToZero ← stats.downToZero + 1;

2 => stats.downToOne ← stats.downToOne + 1;

ENDCASE;

};

nhp.refCount ← nhp.refCount - 1;

};

CheckForRCUnderflow: PROC [nhp: NHeaderP] = {

Software implementation of the CheckForRCUnderflow microcode subroutine

This is called only from ASSIGNREF and from RECLAIMEDREF

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

};

DISABLEMICROCODE: PUBLIC PROC [z: ZeroCountTable] = {

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

cause rc operations to trap (except EnableMicrocode)

NULL; -- the real uc: ucDisabled ← TRUE

};

ENABLEMICROCODE: PUBLIC PROC [z: ZeroCountTable] RETURNS [ucVersion: NAT] = {

Software implementation of the EnableMicrocode MISC

In addition to "enabling" rc microcode, this guy should load ucode registers from memory (zct^).

RETURN[0]; -- the real uc: ucDisabled ← FALSE

};

END.