DIRECTORY FinalizeOps0, ForkOps, Finalize, List, RefTab; FinalizeOps0Impl: CEDAR MONITOR LOCKS cr USING cr: REF ContextRec IMPORTS Finalize, ForkOps, List, RefTab EXPORTS FinalizeOps0 = BEGIN OPEN FinalizeOps0; ContextRep: PUBLIC TYPE = ContextRec; ContextRec: TYPE = MONITORED RECORD [ fq: Finalize.FinalizationQueue, kind: ContextKind, tab: RefTab.Ref ¬ NIL, --(key -> entry); NIL for some kind's inverted: RefTab.Ref ¬ NIL, --(handle -> entry); NIL for some kind's lockList: List.LORA ¬ NIL, --length bounded by number of processes ! lockHead: Key ¬, --logically added to lockList (to reduce memory allocatons) equal: EqualProc ¬ NIL, create: CreateProc, finalize: FinalizeProc, ms: INT ¬ 1000, contextData: REF ¬ NIL, recheck: CONDITION ]; Entry: TYPE = REF EntryRec; EntryRec: TYPE = RECORD [key: Key, handle: Finalize.Handle, preventFinalization: BOOL]; cachesContext: Context ¬ CreateTheFirstContext[]; free: Key ¬ cachesContext; --use a non-NIL value to make NIL a valid key ContextCreator: CreateProc = { cr: REF ContextRec ¬ NARROW[key]; ForkOps.ForkPeriodically[ms: cr.ms, proc: FinalizePseudoProcess, data: cr]; RETURN [NEW[ContextRefRep ¬ cr]]; }; ContextFinalizor: FinalizeProc = { ctx: REF ContextRefRep ¬ NARROW[object]; cr: REF ContextRec ¬ ctx­; ForkOps.Stop[FinalizePseudoProcess, cr, FALSE]; cr.tab ¬ cr.inverted ¬ NIL; cr.contextData ¬ NIL; cr.fq ¬ NIL; }; CreateTheFirstContext: PROC [] RETURNS [context: REF ContextRefRep] = { cr: REF ContextRec ¬ NEW[ContextRec ¬ [ fq: Finalize.NewFQ[], kind: finalize, create: ContextCreator, finalize: ContextFinalizor, lockHead: free ]]; context ¬ NARROW[ContextCreator[cr, NIL]]; -- ! direct call to brake recursion }; CreateContext: PUBLIC PROC [create: CreateProc, equal: EqualProc, hash: HashProc, finalize: FinalizeProc, contextData: REF, kind: ContextKind, millisecondsBetweenChecks: INT] RETURNS [context: Context] = { cr: REF ContextRec; IF millisecondsBetweenChecks<=300 THEN millisecondsBetweenChecks ¬ 2000; SELECT kind FROM finalizeWithSymTabCase => { equal ¬ RefTab.EqualRope; hash ¬ RefTab.HashRope; kind ¬ finalizeWithRefTab }; finalizeWithSymTabNoCase => { equal ¬ RefTab.EqualRopeCaseless; hash ¬ RefTab.HashRopeCaseless; kind ¬ finalizeWithRefTab }; ENDCASE => {}; cr ¬ NEW[ContextRec ¬ [ fq: Finalize.NewFQ[], kind: kind, create: create, equal: equal, finalize: finalize, ms: millisecondsBetweenChecks, lockHead: free, contextData: contextData ]]; IF kind#finalize THEN cr.inverted ¬ RefTab.Create[]; IF kind=finalizeWithRefTab THEN cr.tab ¬ RefTab.Create[equal: equal, hash: hash]; context ¬ NARROW[GetOrCreateObject[cachesContext, cr, NIL], REF ContextRefRep]; }; Enter: ENTRY PROC [cr: REF ContextRec, key: REF] = { ENABLE UNWIND => NULL; Match: INTERNAL PROC [thatKey: REF] RETURNS [BOOL] = INLINE { RETURN [ thatKey=key OR (cr.equal#NIL AND cr.equal[key, thatKey]) ]; }; Occupied: INTERNAL PROC [cr: REF ContextRec, key: REF] RETURNS [BOOL ¬ FALSE] = { IF cr.lockHead#free THEN { IF Match[cr.lockHead] THEN RETURN [TRUE]; }; FOR l: List.LORA ¬ cr.lockList, l.rest WHILE l#NIL DO --bounded by number of processes IF Match[l.first] THEN RETURN [TRUE]; ENDLOOP }; WHILE (cr.lockHead#free OR cr.lockList#NIL) AND Occupied[cr, key] DO WAIT cr.recheck ENDLOOP; IF cr.lockHead=free THEN cr.lockHead ¬ key --worthy reduction of memory allocations for most calls ELSE cr.lockList ¬ CONS[key, cr.lockList]; }; Leave: ENTRY PROC [cr: REF ContextRec, key: REF] = { IF cr.lockHead=key THEN cr.lockHead ¬ free ELSE cr.lockList ¬ List.Remove[key, cr.lockList]; BROADCAST cr.recheck }; GetOrCreateObject: PUBLIC PROC [context: Context, key: Key, create: CreateProc] RETURNS [ob: Object] = { cr: REF ContextRec ¬ context­; CreateNew: PROC [cr: REF ContextRec, key: REF, create: CreateProc] RETURNS [ob: Object ¬ NIL] = { cp: CreateProc = IF create = NIL THEN cr.create ELSE create; ob ¬ cp[key: key, contextData: cr.contextData ! UNWIND => CONTINUE]; IF ob#NIL THEN { h: Finalize.Handle ¬ Finalize.EnableFinalization[ob, cr.fq]; IF cr.kind#finalize THEN { entry: Entry ¬ NEW[EntryRec ¬ [key: key, handle: h, preventFinalization: FALSE]]; IF cr.tab#NIL THEN [] ¬ RefTab.Store[cr.tab, key, entry]; [] ¬ RefTab.Store[cr.inverted, h, entry]; }; }; }; SELECT cr.kind FROM finalize, finalizeWithKey => { ob ¬ CreateNew[cr, key, create]; }; finalizeWithRefTab => { Enter[cr, key]; WITH RefTab.Fetch[cr.tab, key].val SELECT FROM entry: Entry => { oldState: Finalize.FinalizationState; ob ¬ Finalize.HandleToObject[entry.handle]; oldState ¬ Finalize.ReenableFinalization[entry.handle, cr.fq]; SELECT oldState FROM enabled, onFQ => {}; disabled => { IF entry.preventFinalization THEN ERROR; --cant happen since changed in enter/leave monitor only; [if error happens anyway it means that clients EqualProc and HashProc's fail required invariant] entry.preventFinalization ¬ TRUE }; ENDCASE => ERROR; }; ENDCASE => ob ¬ CreateNew[cr, key, create]; Leave[cr, key]; }; ENDCASE => ERROR; }; FinalizePseudoProcess: PROC [data: REF] = { cr: REF ContextRec = NARROW[data]; object: Object; WHILE ~Finalize.FQEmpty[cr.fq] DO reEnable: BOOL ¬ FALSE; handle: Finalize.Handle ¬ Finalize.FQNext[cr.fq]; SELECT cr.kind FROM finalize => IF cr.finalize#NIL THEN { nilKey: REF = NIL; object ¬ Finalize.HandleToObject[handle]; reEnable ¬ cr.finalize[object, nilKey, cr.contextData ! UNWIND => CONTINUE]; IF reEnable THEN { [] ¬ Finalize.ReenableFinalization[handle, cr.fq]; }; }; finalizeWithKey => { entry: Entry ¬ NARROW[RefTab.Fetch[cr.inverted, handle].val]; [] ¬ RefTab.Delete[cr.inverted, handle]; IF cr.finalize#NIL THEN { object ¬ Finalize.HandleToObject[handle]; reEnable ¬ cr.finalize[object, entry.key, cr.contextData ! UNWIND => CONTINUE]; IF reEnable THEN { [] ¬ Finalize.ReenableFinalization[entry.handle, cr.fq]; [] ¬ RefTab.Store[cr.inverted, entry.handle, entry]; }; }; }; finalizeWithRefTab => { entry: Entry ¬ NARROW[RefTab.Fetch[cr.inverted, handle].val]; Enter[cr, entry.key]; IF entry.preventFinalization THEN entry.preventFinalization ¬ FALSE ELSE { [] ¬ RefTab.Delete[cr.inverted, handle]; [] ¬ RefTab.Delete[cr.tab, entry.key]; IF cr.finalize#NIL THEN { object ¬ Finalize.HandleToObject[handle]; reEnable ¬ cr.finalize[object, entry.key, cr.contextData ! UNWIND => CONTINUE]; IF reEnable THEN { [] ¬ Finalize.ReenableFinalization[entry.handle, cr.fq]; [] ¬ RefTab.Store[cr.tab, entry.key, entry]; [] ¬ RefTab.Store[cr.inverted, entry.handle, entry]; }; }; }; Leave[cr, entry.key]; }; ENDCASE => ERROR; ENDLOOP; }; END. Ϊ FinalizeOps0Impl.mesa Copyright Σ 1989, 1991 by Xerox Corporation. All rights reserved. Created by Christian Jacobi, December 1, 1989 4:21:07 pm PST Christian Jacobi, April 19, 1993 11:00 am PDT Willie-s, September 27, 1991 5:54 pm PDT --Context of caches... --We want to garbage collect caches in spite of the FinalizePseudoProcess --A per key lock acquire. --A per key lock release. --<> ENABLE UNWIND => NULL; --Silly window between removage from list and finalization. --Note: there is only one finalizer process; a Reenabled object can not reach disabled state before that one cleared the prevention flag. PROBABLY NOT REASONABLE TO IMPLEMENT ! EachObjectAction: TYPE = PROC [key: Key, object: Object] RETURNS [quit: BOOL _ FALSE]; If this procedure survives the test of implementation; it should be made the same as in RefTab. Enumerate: PROC [context: Context, action: EachObjectAction] RETURNS [q: BOOL] = { ... enumerates objects currently in context in unspecified order; objects created during enumeration may or may not be seen; applies action to each object until action returns TRUE or no more objects; returns TRUE if some action returns TRUE Logical Error: If object on finalization queue but later is revived, enumeration misses object NestedAction: RefTab.EachPairAction = { doThis: BOOL _ FALSE; entry: Entry _ NARROW[val]; object: Object _ Finalize.HandleToObject[handle]; Enter[cr, entry.key]; SELECT Finalize.GetFinalizationState[entry.handle] FROM enabled => {doThis _ TRUE}; onFQ => {doThis _ FALSE}; ??? disabled => {doThis _ FALSE}; ??? ENDCASE => ERROR; Leave[cr, entry.key]; IF doThis THEN quit _ action[key, object] }; cr: REF ContextRec _ context^; q _ RefTab.Pairs[cr.tab, NestedAction]; }; Κ W•NewlineDelimiter –(cedarcode) style™code™Kšœ Οeœ7™BKšœ<™Kšœ˜—K˜šŸœžœžœ žœ˜Gšœžœžœ˜'K˜%Kšœ3˜3Kšœ˜Kšœ˜—Kšœ žœžœ #˜NKšœ˜K˜—š Ÿ œžœžœ]žœ0žœžœ˜ΝKšœžœ ˜Kšžœ žœ"˜Hšžœž˜šœ˜Kšœ˜Kšœ˜Kšœ˜Kšœ˜—šœ˜Kšœ"˜"Kšœ ˜ Kšœ˜Kšœ˜—Kšžœ˜—šœžœ˜K˜#Kšœ2˜2Kšœ˜Kšœ˜Kšœ˜Kšœ˜—Kšžœžœ˜4Kšžœžœ2˜QKšœ žœ&žœžœ˜OK˜—K˜š Ÿœžœžœžœžœ˜4Kšœžœ™Kšžœžœžœ˜šŸœžœžœ žœžœžœžœ˜=Kšžœžœ žœžœ˜DK˜—šŸœžœžœžœžœžœžœžœ˜Qšžœžœ˜Kšžœžœžœžœ˜)K˜—š žœ žœžœžœžœ  ˜VKšžœžœžœžœ˜%Kšž˜—K˜—š žœžœ žœžœžœ˜EKšžœ ˜Kšžœ˜—šžœ˜Kšžœ 7˜NKšžœžœ˜*—K˜—K˜š Ÿœžœžœžœžœ˜4Kšœ™Jšœ+™+šžœ˜Kšžœ˜Kšžœ-˜1—Kšž œ ˜K˜—K˜šŸœžœžœ2žœ˜hKšœžœ˜ š Ÿ œžœžœžœžœžœ˜aKš œžœ žœžœ žœ˜šžœ ž˜Kšœ˜šœ ˜ Kšœ;™;Kšœ‰™‰Kšžœžœžœ š˜ΓKšœž˜ K˜—Kšžœžœ˜—K˜—Kšžœ$˜+—Kšœ˜K˜—Kšžœžœ˜—Kšœ˜—K˜šŸœžœžœ˜+Kšœžœžœ˜"Kšœ˜šžœž˜!Kšœ žœžœ˜K˜1šžœ ž˜šœ žœ žœžœ˜%Kšœžœžœ˜K˜)Kšœ8žœžœ˜Lšžœ žœ˜K˜2K˜—K˜—šœ˜Kšœžœ(˜=Kšœ(˜(šžœ žœžœ˜K˜)Kšœ;žœžœ˜Ošžœ žœ˜K˜8Kšœ4˜4K˜—Kšœ˜—K˜—šœ˜Kšœžœ(˜=Kšœ˜šžœ˜Kšžœž˜&šžœ˜Kšœ(˜(Kšœ&˜&šžœ žœžœ˜K˜)Kšœ;žœžœ˜Ošžœ žœ˜K˜8Kšœ,˜,Kšœ4˜4K˜—Kšœ˜—K˜——Kšœ˜K˜—Kšžœžœ˜—Kšžœ˜—Kšœ˜—K˜Kšžœ˜K™™'š œžœžœžœžœžœ™VK™_—šŸ œžœ.žœžœ™RKšœ°žœžœž™ρKšΟb^™^šŸ œ™'Kšœžœžœ™Kšœžœ™K™1Kšœ™šžœ-ž™7Kšœžœ™Kšœžœ™Kšœžœ™!Kšžœžœ™—Kšœ™Kšžœžœ™*K™—Kšœžœ™Kšœ(™(K™——K™K™—…—ˆ)Ή