<> <> <> <> <> <> <<>> <> <> DIRECTORY YggEnvironment, YggInternal, BasicTime, YggDIDMap USING [DocumentFromLockID, GetName], List, YggLock, YggLockControl, YggLockInternal, YggDummyProcess, Rope USING [Cat, Concat, ROPE], YggMonitoringHooks USING [TransIDFromTransHandle, TransIDToRope], YggMonitoringLog USING [notice, TransactionAbortInfo], YggTransactionMap; YggLockWatchdogImpl: CEDAR PROGRAM IMPORTS BasicTime, YggDIDMap, List, YggLock, YggLockInternal, YggDummyProcess, Rope, YggMonitoringHooks, YggMonitoringLog, YggTransactionMap EXPORTS YggInternal, YggLockControl = BEGIN LockID: TYPE = YggLock.LockID; nullLockID: LockID = YggLock.nullLockID; LockMode: TYPE = YggLock.LockMode; ModeReleasableSet: TYPE = YggLock.ModeReleasableSet; Lock: TYPE = YggLockInternal.Lock; LockRep: TYPE = YggLockInternal.LockRep; Header: TYPE = YggLockInternal.Header; Request: TYPE = YggLockInternal.Request; GrantedRequest: TYPE = YggLockInternal.GrantedRequest; WaitingRequest: TYPE = YggLockInternal.WaitingRequest; LockTransHeader: TYPE = YggLockInternal.LockTransHeader; ConflictingTranses: TYPE = RECORD[holder: YggTransactionMap.TransHandle, waiter: YggTransactionMap.TransHandle, lock: LockID]; -- typical information about a lock conflict LockTransHeaderObject: PUBLIC TYPE = YggLockInternal.LockRep.request.transHeader; <> ForkWatchdogProcess: PUBLIC PROC [ wakeupPeriod: YggDummyProcess.Milliseconds, abortWaitingRequestInterval: INT--seconds--, abortInactiveGrantedRequestInterval: INT--seconds--] = { <> TRUSTED {YggDummyProcess.Detach[FORK LockWatchdogProcess[wakeupPeriod, abortWaitingRequestInterval, abortInactiveGrantedRequestInterval]]; }; }; LockWatchdogProcess: PROC [ wakeupPeriod: YggDummyProcess.Milliseconds, abortWaitingRequestInterval: INT--seconds--, abortInactiveGrantedRequestInterval: INT--seconds--] = { wakeupPeriodsUntilTimeoutCheck: INT _ 0; numWaits: INT _ 0; p: Path _ NIL; DO YggDummyProcess.Pause[YggDummyProcess.MsecToTicks[wakeupPeriod] ! ABORTED => GOTO aborted]; <> IF (wakeupPeriodsUntilTimeoutCheck _ wakeupPeriodsUntilTimeoutCheck-1) <= 0 THEN { l: LIST OF ConflictingTranses; logProc: PROC [YggMonitoringLog.TransactionAbortInfo]; -- (used to stop race condition) [wakeupPeriodsUntilTimeoutCheck, l] _ ChooseTimeoutVictims[wakeupPeriod, abortWaitingRequestInterval]; UNTIL l = NIL DO lNext: LIST OF ConflictingTranses _ l.rest; IF (logProc _ YggMonitoringLog.notice.abortTransaction) # NIL THEN { fileName: Rope.ROPE; -- name of the file being fought over message: Rope.ROPE; message _ IF l.first.holder # NIL THEN Rope.Cat["transaction timed out on lock held by ", YggMonitoringHooks.TransIDToRope[YggMonitoringHooks.TransIDFromTransHandle[l.first.holder]]] ELSE "transaction timed out; livelock?"; fileName _ YggDIDMap.GetName[YggDIDMap.DocumentFromLockID[l.first.lock]]; message _ message.Cat[ "; waiting for ", IF fileName = NIL THEN "(NIL)" ELSE fileName ]; logProc[[ transID: YggMonitoringHooks.TransIDFromTransHandle[l.first.waiter], where: "LockWatchdogImpl.LockWatchdogProcess", why: watchDog, message: message ]]; }; YggTransactionMap.AbortUnilaterally[l.first.waiter, timeout]; YggDummyProcess.Yield[]; FREE[@l]; l _ lNext; ENDLOOP; }; <> YggDummyProcess.Yield[]; DO l: LIST OF ConflictingTranses _ GetBlockingTransactions[]; currentTime: BasicTime.GMT _ BasicTime.Now[]; noAbortDone: BOOL _ TRUE; UNTIL l = NIL DO lNext: LIST OF ConflictingTranses _ l.rest; elapsedTimeSinceLastStartWork: INT _ BasicTime.Period[from: YggTransactionMap.GetTimeOfLastStartWork[l.first.holder], to: currentTime]; IF elapsedTimeSinceLastStartWork > abortInactiveGrantedRequestInterval THEN { logProc: PROC [YggMonitoringLog.TransactionAbortInfo]; fileName: Rope.ROPE; -- name of file being fought over IF (logProc _ YggMonitoringLog.notice.abortTransaction) # NIL THEN { fileName _ YggDIDMap.GetName[YggDIDMap.DocumentFromLockID[l.first.lock]]; logProc[[ transID: YggMonitoringHooks.TransIDFromTransHandle[l.first.holder], where: "LockWatchdogImpl.LockWatchdogProcess", why: watchDog, message: Rope.Cat[ "trans is holding up ", YggMonitoringHooks.TransIDToRope[YggMonitoringHooks.TransIDFromTransHandle[l.first.waiter]], "; waiting for ", IF fileName = NIL THEN "(NIL)" ELSE fileName ] ]] }; YggTransactionMap.AbortUnilaterally[l.first.holder, blockingNewLockRequest]; YggDummyProcess.Yield[]; noAbortDone _ FALSE; }; FREE[@l]; l _ lNext; ENDLOOP; IF noAbortDone THEN EXIT; ENDLOOP; <> YggDummyProcess.Yield[]; { g: WaitingForGraph; [numWaits, g] _ ComputeWaitingForGraph[numWaits]; IF g # NIL THEN { logProc: PROC [YggMonitoringLog.TransactionAbortInfo]; -- (used to stop race condition) DO t: YggTransactionMap.TransHandle; -- transaction to kill p _ FindCycle[g, p]; IF (t _ ChooseVictim[p]) = NIL THEN GOTO freeGraph; IF (logProc _ YggMonitoringLog.notice.abortTransaction) # NIL THEN { <> deadlockList: Rope.ROPE _ NIL; FOR i: NAT IN [0 .. p.length) DO deadlockList _ deadlockList.Cat[ " ", YggMonitoringHooks.TransIDToRope[YggMonitoringHooks.TransIDFromTransHandle[p[i].waitingTrans.trans]] ]; deadlockList _ deadlockList.Cat[ "(", YggDIDMap.GetName[YggDIDMap.DocumentFromLockID[p[i].waitingTrans.waitingFor]], ")" ]; ENDLOOP; logProc[[ transID: YggMonitoringHooks.TransIDFromTransHandle[t], where: "LockWatchdogImpl.LockWatchdogProcess", why: watchDog, message: Rope.Concat["deadlock of", deadlockList] ]]; }; YggTransactionMap.AbortUnilaterally[t, deadlock]; YggDummyProcess.Yield[]; g _ EliminateTrans[g, t]; REPEAT freeGraph => FreeGraph[g]; ENDLOOP; }; }; ENDLOOP; EXITS aborted => NULL }; <> WaitMemb: PROC [trans: YggTransactionMap.TransHandle, list: LIST OF ConflictingTranses] RETURNS [BOOLEAN] ~ { <> UNTIL list = NIL DO IF trans = list.first.waiter THEN RETURN [TRUE]; list _ list.rest ENDLOOP; RETURN [FALSE] }; BlockMemb: PROC [trans: YggTransactionMap.TransHandle, list: LIST OF ConflictingTranses] RETURNS [BOOLEAN] ~ { <> UNTIL list = NIL DO IF trans = list.first.holder THEN RETURN [TRUE]; list _ list.rest ENDLOOP; RETURN [FALSE] }; ChooseTimeoutVictims: PROC [wakeupPeriod: INT--msec--, abortWaitingRequestInterval: INT--seconds--] RETURNS [wakeupPeriodsUntilTimeoutCheck: INT, l: LIST OF ConflictingTranses] = { currentTime: BasicTime.GMT = BasicTime.Now[]; secondsToNextWakeup: INT _ abortWaitingRequestInterval; NoticeWaitingRequest: PROC [wr: WaitingRequest] RETURNS [stop: BOOL] = { <> m: LockMode = ModeAfterGrantingRequest[wr]; elapsedTimeSinceWait: INT--seconds-- = BasicTime.Period[from: wr.startTime, to: currentTime]; <> IF elapsedTimeSinceWait >= abortWaitingRequestInterval THEN { IF NOT WaitMemb[wr.trans, l] THEN { <> FOR h: Lock _ wr.requestList, h.requestList UNTIL h=wr DO WITH h SELECT FROM grh: GrantedRequest => IF grh.trans # wr.trans AND NOT YggLock.Compat[m][grh.mode] THEN { l _ CONS[first: [holder: grh.trans, waiter: wr.trans, lock: YggLockInternal.LockIDFromRH[wr]], rest: l]; GOTO FoundABlocker } ENDCASE; REPEAT FoundABlocker => NULL; FINISHED => l _ CONS[first: [holder: NIL, waiter: wr.trans, lock: YggLockInternal.LockIDFromRH[wr]], rest: l]; ENDLOOP; } } ELSE { <> secondsToNextWakeup _ MIN[secondsToNextWakeup, abortWaitingRequestInterval-elapsedTimeSinceWait]; }; RETURN [stop: FALSE]; }; -- NoticeWaitingRequest l _ NIL; YggLockInternal.GetInfo[waitingRequestEnumProc: NoticeWaitingRequest]; RETURN [(secondsToNextWakeup*1000 + wakeupPeriod-1)/wakeupPeriod, l]; }; GetBlockingTransactions: PROC [] RETURNS [l: LIST OF ConflictingTranses] = { NoticeWaitingRequest: PROC [wr: WaitingRequest] RETURNS [stop: BOOL] = { <> m: LockMode = ModeAfterGrantingRequest[wr]; <> FOR h: Lock _ wr.requestList, h.requestList UNTIL h=wr DO WITH h SELECT FROM grh: GrantedRequest => IF grh.trans # wr.trans AND NOT YggLock.Compat[m][grh.mode] AND NOT BlockMemb[grh.trans, l] THEN l _ CONS[first: [holder: grh.trans, waiter: wr.trans, lock: YggLockInternal.LockIDFromRH[wr]], rest: l]; ENDCASE; ENDLOOP; RETURN [stop: FALSE]; }; l _ NIL; YggLockInternal.GetInfo[waitingRequestEnumProc: NoticeWaitingRequest]; RETURN [l]; }; ModeAfterGrantingRequest: PROC [wr: WaitingRequest] RETURNS [LockMode] = { <> FOR h: Lock _ wr.requestList, h.requestList UNTIL h=wr DO WITH h SELECT FROM grh: GrantedRequest => IF grh.trans = wr.trans THEN RETURN[YggLock.Sup[wr.mode][grh.mode]]; ENDCASE; ENDLOOP; RETURN [wr.mode]; }; <> WaitingTransHandle: TYPE = REF WaitingTransObject; WaitingTransObject: TYPE = RECORD [ trans: YggTransactionMap.TransHandle, waitingFor: LockID _ , edges: LIST OF--WaitingTransHandle--REF ANY, visited: BOOL _ FALSE, onPath: BOOL _ FALSE ]; WaitingForGraph: TYPE = LIST OF--WaitingTransHandle--REF ANY; ComputeWaitingForGraph: PROC [numWaits: INT] RETURNS [newNumWaits: INT, g: WaitingForGraph] = { <> NoticeGeneralInfo: YggLockInternal.GeneralInfoProc = { newNumWaits _ nSetCallsWaited; }; NoticeWaitingRequest: PROC [wr: WaitingRequest] RETURNS [stop: BOOL] = { <> IF newNumWaits = numWaits THEN RETURN [stop: TRUE] ELSE { IF (LookupTrans[g, wr.trans] = NIL) THEN { wt: WaitingTransHandle _ NEW[WaitingTransObject _ [trans: wr.trans, edges: NIL, waitingFor: YggLockInternal.LockIDFromRH[wr]]]; g _ CONS[first: wt, rest: g]; }; RETURN [stop: FALSE]; }; }; NoticeWaitingRequest2: PROC [wr: WaitingRequest] RETURNS [stop: BOOL] = { <> IF newNumWaits = numWaits THEN RETURN [stop: TRUE] ELSE { waiting: WaitingTransHandle = LookupTrans[g, wr.trans]; m: LockMode = ModeAfterGrantingRequest[wr]; FOR h: Lock _ wr.requestList, h.requestList UNTIL h = wr DO WITH h SELECT FROM grh: GrantedRequest => IF grh.trans # wr.trans AND NOT YggLock.Compat[m][grh.mode] THEN { granted: WaitingTransHandle _ LookupTrans[g, grh.trans]; IF granted # NIL AND NOT List.Memb[granted, waiting.edges] THEN waiting.edges _ CONS[first: granted, rest: waiting.edges]; }; ENDCASE; ENDLOOP; RETURN [stop: FALSE]; }; }; g _ NIL; YggLockInternal.GetInfo[ generalInfoProc: NoticeGeneralInfo, waitingRequestEnumProc: NoticeWaitingRequest, waitingRequestEnumProc2: NoticeWaitingRequest2]; RETURN [newNumWaits, g]; }; PathRecord: TYPE = RECORD [ length: NAT _ 0, vertices: SEQUENCE maxLength: NAT OF RECORD [ waitingTrans: WaitingTransHandle, nextEdge: LIST OF--WaitingTransHandle--REF ANY ] ]; Path: TYPE = REF PathRecord; FindCycle: PROC [g: WaitingForGraph, oldPath: Path] RETURNS [path: Path] = { <> top: LIST OF REF ANY _ g; pathLast: NAT _ 0; v: WaitingTransHandle; pathMaxLength: NAT = List.Length[g]; path _ IF oldPath # NIL AND oldPath.length >= pathMaxLength THEN oldPath ELSE NEW[PathRecord[pathMaxLength]]; DO { -- EXITS NextTopLevelVertex v _ NARROW[top.first]; IF v.visited THEN GOTO NextTopLevelVertex; DO <> path[pathLast] _ [waitingTrans: v, nextEdge: v.edges]; v.visited _ v.onPath _ TRUE; DO <> e: LIST OF REF ANY _ path[pathLast].nextEdge; IF e = NIL THEN { <> path[pathLast].waitingTrans.onPath _ FALSE; IF pathLast = 0 THEN GOTO NextTopLevelVertex; pathLast _ pathLast - 1; } ELSE { path[pathLast].nextEdge _ e.rest; v _ NARROW[e.first]; IF v.onPath THEN GOTO FoundCycle; IF NOT v.visited THEN { <> pathLast _ pathLast + 1; EXIT; }; }; ENDLOOP; ENDLOOP; EXITS NextTopLevelVertex => IF (top _ top.rest) = NIL THEN { path.length _ 0; GOTO done; }; FoundCycle => { <> cycleStart: NAT; FOR cycleStart _ 0, cycleStart+1 UNTIL path[cycleStart].waitingTrans = v DO ENDLOOP; FOR j: NAT IN [cycleStart .. pathLast] DO path[j-cycleStart] _ [path[j].waitingTrans, NIL]; ENDLOOP; path.length _ pathLast-cycleStart+1; GOTO done; }; }; ENDLOOP; EXITS done => FOR j: NAT IN [path.length .. path.maxLength) DO path[j] _ [NIL, NIL]; ENDLOOP; }; ChooseVictim: PROC [p: Path] RETURNS [YggTransactionMap.TransHandle] = { <> <> minUpdateCost: INT _ LAST[INT]; minUpdateCostTrans: YggTransactionMap.TransHandle _ NIL; FOR i: NAT IN [0 .. p.length) DO updateCost: INT _ YggTransactionMap.GetEstimatedUpdateCost[p[i].waitingTrans.trans]; IF updateCost < minUpdateCost OR minUpdateCostTrans = NIL THEN { minUpdateCost _ updateCost; minUpdateCostTrans _ p[i].waitingTrans.trans; }; ENDLOOP; RETURN [minUpdateCostTrans]; }; LookupTrans: PROC [g: WaitingForGraph, t: YggTransactionMap.TransHandle] RETURNS [wt: WaitingTransHandle] = { FOR l: LIST OF REF ANY _ g, l.rest UNTIL l = NIL DO wt: WaitingTransHandle _ NARROW[l.first]; IF wt.trans = t THEN RETURN [wt]; ENDLOOP; RETURN [NIL]; }; EliminateTrans: PROC [g: WaitingForGraph, t: YggTransactionMap.TransHandle] RETURNS [newG: WaitingForGraph]= { <> wt: WaitingTransHandle _ LookupTrans[g, t]; FreeList[wt.edges]; wt.edges _ NIL; FOR l: LIST OF REF ANY _ g, l.rest UNTIL l = NIL DO w: WaitingTransHandle _ NARROW[l.first]; w.visited _ w.onPath _ FALSE; w.edges _ List.DRemove[wt, w.edges]; ENDLOOP; RETURN [List.DRemove[wt, g]]; }; FreeGraph: PROC [g: WaitingForGraph] = { <> FOR l: LIST OF REF ANY _ g, l.rest UNTIL l = NIL DO wt: WaitingTransHandle _ NARROW[l.first]; FreeList[wt.edges]; FREE[@wt]; ENDLOOP; FreeList[g]; }; FreeList: PROC [l: LIST OF REF ANY] = { UNTIL l = NIL DO lNext: LIST OF REF ANY _ l.rest; FREE[@l]; l _ lNext; ENDLOOP; }; END.--LockWatchdogImpl CHANGE LOG Changed by MBrown on February 6, 1983 10:03 pm < abort nearly every time.>> <> <> <> <> <> <> <> <> <> <> <> <>