DIRECTORY BasicTime USING [GMT, Now, nullGMT, Period], Camelot USING [AcCommitFailed, btidT, ErSuccess, TABegin, TAEnd, TAKill, tidT], Mach USING [portT], PBasics USING [Comparison], Process USING [Detach, InitializeCondition, MsecToTicks, PauseMsec], RedBlackTree USING [Compare, Create, Delete, GetKey, Insert, Lookup, LookupNextLarger, LookupSmallest, Table, UserData], YggDIDMap USING [Abort, Commit, PreCommit], YggEnvironment USING [CommitOrAbort, DID, nullDID, nullTransID, OperationFailure, Outcome, taPort, TransID, UnknownType], YggFile USING [Abort, Commit, PreCommit], YggLock USING [ReleaseTransactionLocks], YggNaming USING [Abort, Commit, PreCommit], YggRep USING [Abort, Commit, PreCommit, VDoc], YggTransaction USING [Outcome, TransID]; YggTransactionImpl: CEDAR MONITOR IMPORTS BasicTime, Camelot, Process, RedBlackTree, YggDIDMap, YggEnvironment, YggFile, YggLock, YggNaming, YggRep EXPORTS YggTransaction ~ BEGIN TransID: TYPE = YggEnvironment.TransID; -- really a Camelot.tidT RequestedOutcome: TYPE = YggEnvironment.CommitOrAbort; Outcome: TYPE = YggEnvironment.Outcome; Unknown: PUBLIC ERROR [what: YggEnvironment.UnknownType] = CODE; OperationFailed: PUBLIC ERROR [why: YggEnvironment.OperationFailure] = CODE; nullTransID: PUBLIC TransID; subtransactionAndTransactionMap: RedBlackTree.Table; Trans: TYPE = REF TransRep; TransRep: TYPE = RECORD [ transID: TransID, outcome: Outcome, latched: BOOL _ FALSE, finishTime: BasicTime.GMT _ BasicTime.nullGMT, suspendTime: BasicTime.GMT _ BasicTime.nullGMT, parentTrans: Trans, -- circular data structures subTrans: LIST OF Trans, possibleDocumentUpdates: LIST OF YggRep.VDoc _ NIL, defaultContainer: YggEnvironment.DID _ YggEnvironment.nullDID ]; forABit: CONDITION; IsTopLevel: PUBLIC PROC [transID: TransID] RETURNS [topLevel: BOOL] ~ { IF transID.top.nodeId = transID.bottom.nodeId AND transID.top.randomBits = transID.bottom.randomBits AND transID.top.highTicker = transID.bottom.highTicker AND transID.top.lowTicker = transID.bottom.lowTicker THEN RETURN [TRUE] ELSE RETURN [FALSE]; }; IsNullTrans: PUBLIC PROC [ transID: YggTransaction.TransID] RETURNS [null: BOOL] ~ { IF transID.top.nodeId = YggEnvironment.nullTransID.top.nodeId AND transID.top.randomBits = YggEnvironment.nullTransID.top.randomBits AND transID.top.highTicker = YggEnvironment.nullTransID.top.highTicker AND transID.top.lowTicker = YggEnvironment.nullTransID.top.lowTicker THEN RETURN [TRUE] ELSE RETURN [FALSE]; }; EqualTrans: PUBLIC PROC [transID1: TransID, transID2: TransID] RETURNS [equal: BOOL] ~ { EqualBTid: PROC [bTid1, bTid2: Camelot.btidT] RETURNS [equal: BOOL] ~ { IF bTid1.nodeId = bTid2.nodeId AND bTid1.randomBits = bTid2.randomBits AND bTid1.highTicker = bTid2.highTicker AND bTid1.lowTicker = bTid2.lowTicker THEN RETURN [TRUE] ELSE RETURN [FALSE]; }; IF EqualBTid[transID1.top, transID2.top] AND EqualBTid[transID1.bottom, transID2.bottom] THEN RETURN [TRUE] ELSE RETURN [FALSE]; }; CompareTrans: PUBLIC PROC [transID1: TransID, transID2: TransID] RETURNS [comp: PBasics.Comparison] ~ { CompareBTid: PROC [bTid1, bTid2: Camelot.btidT] RETURNS [bcomp: PBasics.Comparison] ~ { SELECT bTid1.lowTicker FROM > bTid2.lowTicker => RETURN [greater]; < bTid2.lowTicker => RETURN [less]; ENDCASE => { SELECT bTid1.highTicker FROM > bTid2.highTicker => RETURN [greater]; < bTid2.highTicker => RETURN [less]; ENDCASE => { SELECT bTid1.nodeId FROM > bTid2.nodeId => RETURN [greater]; < bTid2.nodeId => RETURN [less]; ENDCASE => RETURN [equal]; }; }; }; comp _ CompareBTid[transID1.top, transID2.top]; IF comp = equal THEN comp _ CompareBTid[transID1.bottom, transID2.bottom]; }; CreateTrans: PUBLIC PROC [parentTransID: TransID] RETURNS [transID: TransID _ nullTransID] ~ { newTid: Camelot.tidT; [newTid: newTid] _ Camelot.TABegin[taPort: YggEnvironment.taPort, parentTid: parentTransID, transType: ttOvnvStandard, raiseSignal: TRUE]; IF ~noteNewTrans[newTid, parentTransID] THEN ERROR; transID _ newTid; }; NotePossibleDocumentUpdate: PUBLIC PROC [transID: TransID, vDoc: YggRep.VDoc] ~ { transFound: BOOL _ FALSE; trans: Trans _ NIL; [transFound: transFound, trans: trans] _ findTrans[transID]; IF transFound THEN { FOR pD: LIST OF YggRep.VDoc _ trans.possibleDocumentUpdates, pD.rest UNTIL pD = NIL DO IF pD.first = vDoc THEN {unlatchTrans[trans]; RETURN;}; ENDLOOP; trans.possibleDocumentUpdates _ CONS[vDoc, trans.possibleDocumentUpdates]; unlatchTrans[trans]; }; }; GetPossibleDocumentUpdates: PUBLIC PROC [transID: TransID] RETURNS [ vDocs: LIST OF YggRep.VDoc] ~ { transFound: BOOL _ FALSE; trans: Trans _ NIL; [transFound: transFound, trans: trans] _ findTrans[transID]; IF transFound THEN { unlatchTrans[trans]; RETURN [trans.possibleDocumentUpdates]; }; }; GetDefaultContainer: PUBLIC PROC [transID: TransID] RETURNS [did: YggEnvironment.DID _ YggEnvironment.nullDID] ~ { transFound: BOOL _ FALSE; trans: Trans _ NIL; [transFound: transFound, trans: trans] _ findTrans[transID]; IF transFound THEN { did _ trans.defaultContainer; unlatchTrans[trans]; }; }; SetDefaultContainer: PUBLIC PROC [transID: TransID, did: YggEnvironment.DID] ~ { transFound: BOOL _ FALSE; trans: Trans _ NIL; [transFound: transFound, trans: trans] _ findTrans[transID]; IF transFound THEN { trans.defaultContainer _ did; unlatchTrans[trans]; }; }; Check: PUBLIC PROC [ transID: YggTransaction.TransID] RETURNS [outcome: YggTransaction.Outcome _ unknown] ~ { transFound: BOOL _ FALSE; trans: Trans _ NIL; [transFound: transFound, trans: trans] _ findTrans[transID]; IF transFound THEN { unlatchTrans[trans]; RETURN [trans.outcome]; } ELSE { IF EqualTrans[transID, YggEnvironment.nullTransID] THEN RETURN [active]} ; }; GetParent: PUBLIC PROC [ transID: YggTransaction.TransID] RETURNS [transFound: BOOL _ FALSE, parentTransID: YggTransaction.TransID _ nullTransID] ~ { trans: Trans _ NIL; parentTrans: Trans _ NIL; [transFound, trans, parentTrans] _ findTrans[transID]; IF transFound AND parentTrans # NIL THEN parentTransID _ parentTrans.transID; IF transFound THEN unlatchTrans[trans]; }; Suspend: PUBLIC PROC [transID: TransID, status: INT] ~ { transFound: BOOL _ FALSE; trans: Trans _ NIL; [transFound: transFound, trans: trans] _ findTrans[transID, TRUE]; IF transFound THEN { trans.outcome _ suspended; trans.suspendTime _ BasicTime.Now[]; unlatchTrans[trans]; }; }; Finish: PUBLIC PROC [transID: TransID, requestedOutcome: RequestedOutcome] RETURNS [outcome: Outcome] ~ { transFound: BOOL _ FALSE; trans: Trans _ NIL; [transFound: transFound, trans: trans] _ findTrans[transID, TRUE]; IF transFound THEN { SELECT trans.outcome FROM active => { }; suspended => { SELECT requestedOutcome FROM commit => { unlatchTrans[trans]; ERROR OperationFailed[cantCommitSuspendedTrans]; }; abort => { unlatchTrans[trans]; ERROR OperationFailed[cantAbortSuspendedTrans]; }; ENDCASE => { unlatchTrans[trans]; ERROR; }; }; commit => { SELECT requestedOutcome FROM commit => { unlatchTrans[trans]; ERROR OperationFailed[cantCommitCommittedTrans]; }; abort => { unlatchTrans[trans]; ERROR OperationFailed[cantAbortCommittedTrans]; }; ENDCASE => { unlatchTrans[trans]; ERROR; }; }; abort => { SELECT requestedOutcome FROM commit => { unlatchTrans[trans]; ERROR OperationFailed[cantCommitAbortedTrans]; }; abort => { unlatchTrans[trans]; ERROR OperationFailed[cantAbortAbortedTrans]; }; ENDCASE => { unlatchTrans[trans]; ERROR; }; }; ENDCASE => { unlatchTrans[trans]; ERROR; }; trans.outcome _ requestedOutcome; trans.finishTime _ BasicTime.Now[]; unlatchTrans[trans]; SELECT requestedOutcome FROM commit => { status: INT; callAllPreCommitProcs[transID]; status _ Camelot.TAEnd[taPort: YggEnvironment.taPort, tid: transID, protocolType: ptNonBlocking, raiseSignal: TRUE].status; SELECT status FROM Camelot.ErSuccess => {outcome _ commit; callAllCommitProcs[transID];}; Camelot.AcCommitFailed => {outcome _ abort; callAllAbortProcs[transID];}; ENDCASE => ERROR; }; abort => { callAllAbortProcs[transID]; [] _ Camelot.TAKill[taPort: YggEnvironment.taPort, tid: transID, status: 0, raiseSignal: TRUE]; outcome _ abort; }; ENDCASE => ERROR; IF ~removeTrans[transID] THEN ERROR; } ELSE ERROR Unknown[transID]; }; callAllPreCommitProcs: PROC [transID: TransID] ~ { YggRep.PreCommit[transID]; -- Rep must preceed File (Rep writes its volatile form of document's contents, attributes, and links to its files during precommit, so some file size changes are possible) YggNaming.PreCommit[transID]; -- Naming must preceed File (Naming really does the updates during precommit, so some file size changes are possible) YggFile.PreCommit[transID]; -- File must preceed DIDMap (File performs its intentions during precommit) YggDIDMap.PreCommit[transID]; }; callAllCommitProcs: PROC [transID: TransID] ~ { YggRep.Commit[transID]; YggNaming.Commit[transID]; YggFile.Commit[transID]; YggDIDMap.Commit[transID]; [] _ YggLock.ReleaseTransactionLocks[transID, FALSE]; }; callAllAbortProcs: PROC [transID: TransID] ~ { YggRep.Abort[transID]; YggNaming.Abort[transID]; YggFile.Abort[transID]; YggDIDMap.Abort[transID]; [] _ YggLock.ReleaseTransactionLocks[transID, FALSE]; }; savedScratchTrans: Trans; savedScratchTransForEntries: Trans _ NEW[TransRep]; getScratchTrans: ENTRY PROC RETURNS [scratchTrans: Trans] ~ { ENABLE UNWIND => {}; IF savedScratchTrans # NIL THEN { scratchTrans _ savedScratchTrans; savedScratchTrans _ NIL; } ELSE { scratchTrans _ NEW[TransRep]; }; }; returnScratchRefChunk: ENTRY PROC [scratchTrans: Trans] ~ { savedScratchTrans _ scratchTrans; }; noteNewTrans: PROC [transID: TransID, parentTransID: TransID] RETURNS [parentOK: BOOL _ FALSE] ~ { newTrans: Trans; insertTrans: ENTRY PROC RETURNS [monitoredParentOK: BOOL _ FALSE] ~ { ENABLE UNWIND => {}; data: RedBlackTree.UserData; IF ~IsTopLevel[transID] THEN { savedScratchTransForEntries.transID _ parentTransID; data _ RedBlackTree.Lookup[subtransactionAndTransactionMap, savedScratchTransForEntries]; IF data = NIL THEN { RETURN[FALSE]; } ELSE { parent: Trans; parent _ NARROW[data]; parent.subTrans _ CONS[newTrans, parent.subTrans]; newTrans.parentTrans _ parent; monitoredParentOK _ TRUE; }; } ELSE monitoredParentOK _ TRUE; RedBlackTree.Insert[subtransactionAndTransactionMap, newTrans, newTrans]; RETURN [TRUE]; }; newTrans _ NEW[TransRep _ [transID: transID, outcome: active, parentTrans: NIL, subTrans: NIL]]; parentOK _ insertTrans[]; }; findTrans: ENTRY PROC [transID: TransID, setLatch: BOOL _ FALSE] RETURNS [transFound: BOOL _ FALSE, trans: Trans _ NIL, parentTrans: Trans _ NIL] ~ { ENABLE UNWIND => {}; data: RedBlackTree.UserData; savedScratchTransForEntries.transID _ transID; data _ RedBlackTree.Lookup[subtransactionAndTransactionMap, savedScratchTransForEntries]; IF data = NIL THEN { RETURN[FALSE, NIL, NIL]; } ELSE { trans _ NARROW[data]; WHILE trans.latched DO WAIT forABit ENDLOOP; trans.latched _ TRUE; RETURN[TRUE, trans, trans.parentTrans]; }; }; unlatchTrans: ENTRY PROC [trans: Trans] ~ { trans.latched _ FALSE; }; removeTrans: ENTRY PROC [transID: TransID] RETURNS [transFound: BOOL _ FALSE] ~ { data: RedBlackTree.UserData; savedScratchTransForEntries.transID _ transID; data _ RedBlackTree.Lookup[subtransactionAndTransactionMap, savedScratchTransForEntries]; IF data = NIL THEN { RETURN[FALSE]; } ELSE { trans: Trans; trans _ NARROW[data]; IF trans.parentTrans # NIL THEN { prevTrans: LIST OF Trans _ NIL; FOR lot: LIST OF Trans _ trans.parentTrans.subTrans, lot.rest UNTIL lot = NIL DO IF EqualTrans[transID, lot.first.transID] THEN { IF prevTrans = NIL THEN trans.parentTrans.subTrans _ lot.rest ELSE prevTrans.rest _ lot.rest; EXIT; }; prevTrans _ lot; REPEAT FINISHED => {ERROR}; ENDLOOP; trans.parentTrans _ NIL; }; [] _ RedBlackTree.Delete[subtransactionAndTransactionMap, savedScratchTransForEntries]; RETURN[TRUE]; }; }; GetKeyProc: RedBlackTree.GetKey = { trans: Trans _ NARROW[data]; RETURN[ trans ]; }; CompareProc: RedBlackTree.Compare = { dataTrans: Trans _ NARROW[data]; keyTrans: Trans _ NARROW[k]; SELECT keyTrans.transID.bottom.nodeId.value FROM > dataTrans.transID.bottom.nodeId.value => RETURN [greater]; < dataTrans.transID.bottom.nodeId.value => RETURN [less]; ENDCASE => { SELECT keyTrans.transID.bottom.highTicker FROM > dataTrans.transID.bottom.highTicker => RETURN [greater]; < dataTrans.transID.bottom.highTicker => RETURN [less]; ENDCASE => { SELECT keyTrans.transID.bottom.lowTicker FROM > dataTrans.transID.bottom.lowTicker => RETURN [greater]; < dataTrans.transID.bottom.lowTicker => RETURN [less]; ENDCASE => RETURN [equal]; }; }; }; milliSecondsBetweenClean: INT _ 3000; secondsToRetainTrans: INT _ 3600; -- for debugging, a long time CleanTransactionTableProcess: PROC ~ { DO data: RedBlackTree.UserData; now: BasicTime.GMT; Process.PauseMsec[milliSecondsBetweenClean]; now _ BasicTime.Now[]; data _ RedBlackTree.LookupSmallest[subtransactionAndTransactionMap]; WHILE data # NIL DO trans: Trans; trans _ NARROW[data]; IF trans.outcome # active AND BasicTime.Period[from: trans.finishTime, to: now] > secondsToRetainTrans THEN { IF ~removeTrans[trans.transID] THEN ERROR; }; data _ RedBlackTree.LookupNextLarger[subtransactionAndTransactionMap, data]; ENDLOOP; ENDLOOP; }; Init: PROC ~ { subtransactionAndTransactionMap _ RedBlackTree.Create[getKey: GetKeyProc, compare: CompareProc]; TRUSTED {Process.InitializeCondition[@forABit, Process.MsecToTicks[10]]; }; TRUSTED {Process.Detach[FORK CleanTransactionTableProcess[]]}; }; Init[]; END. BYggTransactionImpl.mesa Copyright Σ 1988, 1989 by Xerox Corporation. All rights reserved. Bob Hagmann March 24, 1989 8:52:00 am PST Handle all operations on transactions. Data types and variables Exported procedures for transactions Precommit, commit, and abort callers Internal procedures Internal red black procs A Red Black tree is used to store and find transactions/subtransactions. The tree is indexed by subtransaction. PROC [data: UserData] RETURNS [Key] PROC [k: Key, data: UserData] RETURNS [Basics.Comparison] Toss old transactions process Initialization Κ˜code•Mark outsideHeaderšœ™KšœB™BKšœ)™)—K™K™&K™šΟk ˜ Kšœ œ˜,KšœœB˜OKšœœ ˜Kšœœ˜Kšœœ7˜DJšœ œf˜xKšœ œ˜+Kšœœe˜yKšœœ˜)Kšœœ˜(Kšœ œ˜+Kšœœ"˜.Kšœœ˜(—K˜KšΡblnœœ˜!Kšœj˜qKšœ˜šœ˜K˜—head™K˜Kšœ œΟc˜AKšœœ ˜6Kšœ œ˜'Iunit˜Kšœ  œ+˜@Kšœ œ/˜LK˜Kšœ œ ˜K˜Kšœ4˜4K˜Kšœœœ ˜šœ œœ˜Kšœ˜Kšœ˜K˜K˜.Kšœ/˜/KšœŸ˜0Kšœ œœ˜Kšœœœ˜3Kšœ=˜=K˜K˜—Kšœ˜—šœ$™$š Οn œœœœ œ˜GKšœ™œ4œœœœœœ˜ψK˜—š   œœœ$œœ˜TKšœΙœDœœœœœœ˜ΈK˜—š   œœœ(œ œ˜Xš  œœœ œ˜GKšœœ%œ%œ#œœœœœœ˜ΌKšœ˜—Kšœ'œ-œœœœœœ˜€K˜—š  œœœ(œ˜gš  œœœ ˜Wšœ˜Kšœœ ˜&Kšœœ˜#šœ˜ šœ˜Kšœœ ˜'Kšœœ˜$šœ˜ šœ˜Kšœœ ˜#Kšœœ˜ Kšœœ ˜—K˜——K˜——Kšœ˜—Kšœ/˜/KšœJ˜JK˜—š  œœœœ%˜^Kšœ˜KšœŠ˜ŠKšœ&œœ˜3Kšœ˜K˜—š œœœ*˜QKšœ œœ˜Kšœœ˜Kšœ<˜<šœ œ˜š œœœ6œœ˜VKšœœœœ˜7Kšœ˜—Kšœ œ&˜JKšœ˜K˜—K˜K˜—š  œ œœ œœ˜dKšœ œœ˜Kšœ œ˜Kšœ<˜<šœ œ˜Kšœ˜Kšœ!˜'K˜—K˜K˜—š œ œœœ˜rKšœ œœ˜Kšœœ˜Kšœ<˜<šœ œ˜Kšœ˜Kšœ˜K˜—K˜K˜—š œ œ&œ˜PKšœ œœ˜Kšœœ˜Kšœ<˜<šœ œ˜Kšœ˜Kšœ˜K˜—K˜M˜—š œ œ$œ0˜mKšœ œœ˜Kšœ œ˜Kšœ<˜<šœ œ˜Kšœ˜Kšœ˜K˜—KšœR˜RK˜—š   œœœ$œœœ:˜•Kšœœ˜Kšœœ˜Kšœ6˜6Kšœ"œ%˜MKšœ œ˜'K˜—š œ œœ˜8Kšœ œœ˜Kšœœ˜KšœB˜Bšœ œ˜Kšœ˜Kšœ$˜$Kšœ˜K˜—K˜—š œœœ8œ˜iKšœ œœ˜Kšœœ˜Kšœ<œ˜Bšœ œ˜šœ˜šœ ˜ K˜—šœ˜šœ˜šœ ˜ Kšœ˜Kšœ+˜0K˜—šœ ˜ Kšœ˜Kšœ*˜/K˜—Kšœœ˜+—K˜—šœ ˜ šœ˜šœ ˜ Kšœ˜Kšœ+˜0K˜—šœ ˜ Kšœ˜Kšœ*˜/K˜—Kšœœ˜+—K˜—šœ ˜ šœ˜šœ ˜ Kšœ˜Kšœ)˜.K˜—šœ ˜ Kšœ˜Kšœ(˜-K˜—Kšœœ˜+—K˜—Kšœœ˜+—Kšœ!˜!Kšœ#˜#Kšœ˜šœ˜šœ ˜ Kšœœ˜ Kšœ˜Kšœnœ ˜{šœ˜KšœF˜FKšœI˜IKšœœ˜—K˜—šœ ˜ Kšœ˜KšœYœ˜_K˜K˜—Kšœœ˜—Kšœœœ˜$K˜—Kšœœœ˜K˜——™$K˜šΟbœœ˜2KšœŸ«˜ΗKšœŸu˜”KšœŸK˜hKšœ˜K˜K˜—š‘œœ˜/Kšœ˜Kšœ˜Kšœ˜Kšœ˜Kšœ5˜5K˜K˜—š‘œœ˜.Kšœ˜Kšœ˜Kšœ˜Kšœ˜Kšœ5˜5K˜K˜——™Kšœ˜Kšœ%œ ˜3K˜š‘œœœœ˜=J˜šœœœ˜!Kšœ!˜!Kšœœ˜K˜—šœœ˜Kšœœ ˜K˜—K˜K˜—š‘œœœ˜;Kšœ!˜!K˜K˜—š ‘ œœ,œ œœ˜bKšœ˜š ‘ œœœœœœ˜EJ˜Jšœ˜šœœ˜Jšœ4˜4JšœY˜Yšœœœ˜Kšœœ˜K˜—šœœ˜J˜Jšœ œ˜Jšœœ˜2Jšœ˜Jšœ˜K˜—K˜—Kšœ˜KšœI˜IKšœœ˜K˜—Kšœ œ=œ œ˜`Kšœ˜K˜K˜—š‘ œœœœœœœœœœ˜•J˜Jšœ˜Jšœ.˜.JšœY˜Yšœœœ˜Kšœœœœ˜K˜—šœœ˜Jšœœ˜Jšœœœ œ˜,Jšœ˜Jšœœ˜'K˜—J˜J˜—š‘ œœœ˜+Jšœ˜J˜J˜—š ‘ œ œœœœ˜QJšœ˜Jšœ.˜.JšœY˜Yšœœœ˜Kšœœ˜K˜—šœœ˜Jšœ ˜ Jšœœ˜šœœœ˜!Jšœ œœ œ˜š œœœ.œœ˜Pšœ(œ˜0Jšœ œœ&˜=Jšœœ˜ Jšœ˜J˜—J˜š˜Jšœœ˜—Jšœ˜—Jšœœ˜J˜—KšœW˜WKšœœ˜ K˜—J˜——šœ™J™rJ˜š  œ˜&Jšœœ™#Jšœœ˜Jšœ ˜J˜J˜—•StartOfExpansion[]š  œ˜%Jšœœ™9Jšœœ˜ Jšœœ˜šœ&˜0Jšœ+œ ˜K˜—K˜K˜—Kšœ˜—…—4vFE