YggTransactionImpl.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.
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
Data types and variables
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;
Exported procedures for transactions
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];
};
Precommit, commit, and abort callers
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];
};
Internal procedures
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];
};
};
Internal red black procs
A Red Black tree is used to store and find transactions/subtransactions. The tree is indexed by subtransaction.
GetKeyProc: RedBlackTree.GetKey = {
PROC [data: UserData] RETURNS [Key]
trans: Trans ← NARROW[data];
RETURN[ trans ];
};
CompareProc: RedBlackTree.Compare = {
PROC [k: Key, data: UserData] RETURNS [Basics.Comparison]
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];
};
};
};
Toss old transactions process
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;
};
Initialization
Init: PROC ~ {
subtransactionAndTransactionMap ← RedBlackTree.Create[getKey: GetKeyProc, compare: CompareProc];
TRUSTED {Process.InitializeCondition[@forABit, Process.MsecToTicks[10]]; };
TRUSTED {Process.Detach[FORK CleanTransactionTableProcess[]]};
};
Init[];
END.