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
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[];
--Context of caches...
--We want to garbage collect caches in spite of the FinalizePseudoProcess
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] = {
--A per key lock acquire.
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] = {
--A per key lock release.
--<<Doesn't crash!>> ENABLE UNWIND => NULL;
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 => {
--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.
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.
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];
};