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 IMPORTS AllocatorOps, Basics, PrincOpsUtils, UnsafeStorage, ZCT--zct-- EXPORTS RCMicrocodeOps = BEGIN OPEN Allocator, Collector, RCMicrocodeStats, ZCT; checking: BOOL = FALSE; 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^; }; RCOverflowOccurred: PUBLIC ERROR = CODE; RCUnderflowOccurred: PUBLIC ERROR = CODE; LookFurtherAtReclaimedRef: PUBLIC ERROR = CODE; ZCTFull: PUBLIC ERROR = CODE; NormalFreeListEmpty: PUBLIC ERROR = CODE; ALLOCATE: PUBLIC PROC [size: CARDINAL, type: SafeStorage.Type] RETURNS[r: REF _ NIL] = { IF size <= maxSmallBlockSize THEN { bsi: BlockSizeIndex = zct.sizeToBSI[size]; fnhp: FNHeaderP _ zct.bsiToFreeList[bsi]; nhp: NHeaderP; IF fnhp = NIL THEN ERROR NormalFreeListEmpty; nhp _ @fnhp.fnh; r _ AllocatorOps.NHPToREF[nhp]; OnZ[nhp]; -- may pageFault or raise ZCTFull; ifso, no changes have been made 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] = { 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] = { 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 => { marking: BOOL = zct.markingDecrements; lnhp: NHeaderP = AllocatorOps.REFToNHP[lhsRef]; lrc: RefCount _ lnhp.refCount; SELECT lrc FROM 0 => IF lnhp.rcOverflowed THEN ERROR RCUnderflowOccurred ELSE ERROR; 1 => { 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; }; lnhp.maybeOnStack _ marking; lnhp.refCount _ lrc - 1; lhs^ _ rhs; -- NOT counted }; lhsRef = NIL => { rnhp: NHeaderP _ AllocatorOps.REFToNHP[rhs]; -- subtract 2 rrc: RefCount _ rnhp.refCount; IF rrc = LAST[RefCount] THEN ERROR RCOverflowOccurred; 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; }; rnhp.refCount _ rrc + 1; rnhp.maybeOnStack _ FALSE; lhs^ _ rhs; -- NOT counted }; ENDCASE => { 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; SELECT lrc FROM 0 => IF lnhp.rcOverflowed THEN ERROR RCUnderflowOccurred ELSE ERROR; 1 => { IF marking OR NOT lnhp.rcOverflowed THEN OnZ[lnhp]; }; ENDCASE => IF marking THEN OnZ[lnhp]; 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] = { IF NOT nhp.inZCT THEN { wp: LONG POINTER TO NHeaderP _ zct.wp; wp^ _ nhp; IF Basics.BITAND[Basics.LowHalf[LOOPHOLE[wp, LONG CARDINAL]], zctBlockWords - 1] = zctBlockWords - 2*SIZE[LONG POINTER] THEN { 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; } 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] = { 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] = { RETURN[MCRECLAIMABLEREF[nhp, FALSE]]; }; 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); }; 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]]; }; 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]]; u _ BITAND[r, zct.residueMask]; x _ BITAND[BITXOR[BITSHIFT[LowHalf[lc], -1], u], FOSTableLength-1]; }; RECLAIMEDREF: PUBLIC PROC [ref: REF] RETURNS [ans: REF ANY _ NIL] = { nhp: NHeaderP = AllocatorOps.REFToNHP[ref]; CheckForRCUnderflow[nhp]; -- might raise RCUnderflowOccurred SELECT MCRECLAIMABLEREF[nhp, TRUE] FROM continue => NULL; reclaimIt => ans _ ref; finalizeIt => ERROR LookFurtherAtReclaimedRef; 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] = { rc: RefCount _ nhp.refCount; IF checking AND rc = 0 AND NOT nhp.rcOverflowed THEN ERROR; IF rc = 0 --was RCMicrocodeOps.rcBottom-- AND nhp.rcOverflowed THEN ERROR RCUnderflowOccurred; -- no changes have been made }; DISABLEMICROCODE: PUBLIC PROC [z: ZeroCountTable] = { NULL; -- the real uc: ucDisabled _ TRUE }; ENABLEMICROCODE: PUBLIC PROC [z: ZeroCountTable] RETURNS [ucVersion: NAT] = { RETURN[0]; -- the real uc: ucDisabled _ FALSE }; END. ~RCMicrocodeImpl.mesa Copyright c 1984, 1985, 1986 by Xerox Corporation. All rights reserved. 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 all but FOSTableHash are really INTERNAL procs of the ZCTImpl monitor FLAGS ucDisabled: BOOL; private flag kept in ucode registers Stats ERRORS 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 IF ucDisabled THEN Allocate MISC TRAP with trapParam = 2 Allocate MISC TRAP with trapParam = 6 XXX touch nhp.type, .maybeOnStack, zct.markingDecrements, fnhp.nextFree COMMITTED if here 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 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]; note: lhsRef # NIL Check for underflow and for reaching 0. TRAP with trapParam = 3 TRAP with trapParam = 5 might raise ZCTFull COMMITTED NOW to finish this call This is a simple case, and should happen for all first assignments to fields. TRAP with trapParam = 1 COMMITTED NOW to finish this call Assert: lhsRef # NIL AND rhs # NIL AND rhs # lhsRef TRAP with trapParam = 1 Check for underflow and for reaching 0. TRAP with trapParam = 3 TRAP with trapParam = 5 might raise ZCTFull COMMITTED NOW to finish this call 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 beware: might pageFault wp will not point to the link word wp^ may be left with garbage if ZCTFull is raised wp points to the cell before the link to the next zctBlock now COMMITTED to finish this call Software implementation of the CreateRef MISC IF ucDisabled THEN CreateRef MISC TRAP with trapParam = 2 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 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 Software implementation of the FoundInFHSnapshot microcode subroutine This is called only from MCRECLAIMABLEREF Software implementation of the FOSTableHash microcode subroutine r is all but the least significant 13 bits 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. IF ucDisabled THEN ReclaimedRef MISC TRAP with trapParam = 2 ReclaimedRef MISC TRAP, trapParam = 6 Software implementation of the CheckForRCUnderflow microcode subroutine This is called only from ASSIGNREF and from RECLAIMEDREF i.e. XXX TRAP with trapParam = 5 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^). cause rc operations to trap (except EnableMicrocode) Software implementation of the EnableMicrocode MISC In addition to "enabling" rc microcode, this guy should load ucode registers from memory (zct^). Κ «˜codešœ™Kšœ Οmœ=™HKšœA™AKšœ0™0Kšœ(™(K™0K˜šΟk ˜ Kšœ žœ]˜lKšœ žœ˜(Kš œžœžœžœžœžœ˜BKšœ žœ˜Kšœžœ ˜Kšœžœ˜Kšœžœ˜)Kšœ žœ˜#Kšœžœ˜%Kšžœžœq˜z——headšœž˜KšœE™EKšžœ$žœ žΟc˜FKšžœ˜Kš œžœžœžœžœ˜9—K™šœ™Kšœ žœžœ˜Kšœ8™8K™—™Kšœžœžœ˜Kšœžœ+žœ ˜HKšœ4žœ˜HKš œžœžœžœžœ˜#šΟn œžœžœžœ˜3Kšœžœžœžœžœ žœžœžœžœ ˜FKšœžœžœžœžœ žœžœžœ ˜BKšœ˜šžœžœ ž˜"Kšœ˜Kšžœ˜—Kšœ˜K˜—K˜—šœ™Kšœž œžœ˜(Kšœž œžœ˜)Kšœž œžœ˜/Kšœ ž œžœ˜Kšœž œžœ˜)—K™šœ ™ K˜šΠbkœžœžœžœžœžœžœ˜Xšœ,™,Kšœ:™:Kšœ0™0KšŸ"œŸ!™V—Kšœ8™8šžœžœ˜#Kšœ*˜*Kšœ)˜)Kšœ˜šžœžœžœžœ˜-Kšœ%™%—Kšœ˜Kšœ˜K™KšœH™HKšœ ŸB˜MK™Kšœ™Kšœ'˜'KšœžœŸ˜-Kšœ˜Kšœ)˜)Kšžœžœ'˜;K˜—Kšœ˜K˜—š ‘ œžœžœžœ žœžœ˜Jšœ(™(Kšœ™KšŸ.™.—Kšœ8™8Kšœ)˜)šžœžœ˜%Kšœžœ˜+Kšœžœ%žœ˜ZKšœ'Ÿ˜AKšœ'˜'Kšœ˜K˜—Kšœ˜K˜—š‘ œžœžœžœžœžœžœžœ˜?šœA™AKšœP™PK™C—Kšœ1™1Kšœ™Kšœžœ˜šžœžœž˜šœ˜šžœž˜šžœž˜ Kšžœ,˜0Kšžœ+˜/——K˜—šœžœ˜Kšœ™Kšœ žœ˜&Kšœ/˜/Kšœ˜K˜Kšœ'™'šžœž˜šœžœ˜šžœžœ˜Kšœ™—šžœžœ˜ Kšœ™——šœ˜Kšœ™Kšžœ žœžœžœ ˜3K˜—Kšžœžœ žœ ˜%—K˜šžœžœ˜Kšœ.˜.š žœžœžœžœž˜-Kšœ-˜-Kšœ+˜+Kšžœ˜—K˜—Kšœ!™!Kšœ˜Kšœ˜Kšœ Ÿ˜K˜—šœ žœ˜K™MKšœ.Ÿ ˜;Kšœ˜šžœžœ žœžœ˜6Kšœ™—K˜šžœžœ˜Kšœ0˜0š žœžœžœžœž˜-Kšœ'˜'Kšœ'˜'Kšžœ˜—K˜—Kšœ!™!Kšœ˜Kšœžœ˜Kšœ Ÿ˜K˜—šžœ˜ Kš œžœžœžœžœ ™3Kšœ žœ˜&Kšœ/˜/Kšœ˜Kšœ,˜,Kšœ˜šžœžœ žœžœ˜6Kšœ™—K˜Kšœ'™'šžœž˜šœžœ˜šžœžœ˜Kšœ™—šžœžœ˜ Kšœ™——šœ˜Kšœ™Kšžœ žœžœžœ ˜3K˜—Kšžœžœ žœ ˜%—K˜Kšœ!™!šžœžœ˜Kšœ.˜.š žœžœžœžœž˜-Kšœ'˜'Kšœ'˜'Kšžœ˜—š žœžœžœžœž˜-Kšœ-˜-Kšœ+˜+Kšžœ˜—K˜—Kšœ˜Kšœ˜Kšœ˜Kšœžœ˜Kšœ Ÿ˜K˜——Kšžœžœ'˜;Kšœ˜—K™š œžœžœ˜$šœ7™7KšœG™Gšœ™Kšœ™Kšœ™Kšœž™——šžœžœ žœ˜Kšœžœžœžœ˜&šœ ˜ Kšœ™Kšœ"™"Kšœ2™2—š žœžœžœžœžœ˜PKšœžœžœžœ˜&šžœ˜Kšœ:™:Kšœžœžœžœžœžœžœžœ ˜Bšžœž˜ Kšžœžœ Ÿ#˜6šžœ ˜Kšœ!™!——K˜—Kš žœžœžœžœŸ˜=—Kšžœžœ˜3Kšœ žœŸ$˜7K˜—Kšœ˜K™—š‘ œžœžœ˜*Kšœ-™-Kšœ9™9Kš žœ žœžœžœžœ˜BKšœ ŸB˜MKšœ)˜)Kšžœžœ'˜;Kšœ˜—K˜š‘œžœžœžœ˜Dšœ2™2KšœŸœ!™D—Kšœ>™>Kšžœžœžœ˜%Kšœ˜K™—š‘œžœžœžœ˜`šœD™DKšœ8™8KšœŸœ!™D—Kšœ˜Kšžœ žœŸ˜4Kš žœžœ žœžœžœŸ˜Jšžœžœ˜-Kšžœ Ÿ3˜BKšžœžœžœ žœ ˜3—Kšœ˜K™š  œžœžœžœžœ˜HšœE™EKšœ)™)—Kšœ˜Kšœ ˜ Kš œ žœžœžœžœžœ ˜IKšœ%˜%Kšœ˜KšžœΠksœ˜/Kšœ˜—K˜š   œžœžœŸœžœ*˜jKšœ@™@Kšžœ˜ Kš œžœžœžœžœžœ˜1Kšœ˜šœžœžœžœ˜AKšœ*™*—Kšœžœ˜šœžœžœžœ)˜CKšœΤΟsœ™ζKšœ~£œœ™—Kšœ˜—K™—š‘ œžœžœžœžœžœžœžœ˜Ešœ0™0KšœW™WKšœF™FKšœJ™J—Kšœ+˜+Kšœ<™