001: /*
002: * All content copyright (c) 2003-2006 Terracotta, Inc., except as may otherwise be noted in a separate copyright notice. All rights reserved.
003: */
004: package com.tc.objectserver.lockmanager.impl;
005:
006: import com.tc.objectserver.lockmanager.api.DeadlockResults;
007:
008: import java.util.ArrayList;
009: import java.util.Collection;
010: import java.util.HashSet;
011: import java.util.Iterator;
012: import java.util.List;
013: import java.util.Set;
014:
015: class DeadlockDetector {
016: private static final ServerThreadContext[] EMPTY_TXN_ARRAY = new ServerThreadContext[] {};
017:
018: private final DeadlockResults listener;
019: private final Set inDeadlock = new HashSet();
020:
021: DeadlockDetector(DeadlockResults listener) {
022: this .listener = listener;
023: }
024:
025: void detect(Iterator openTransactions) {
026: while (openTransactions.hasNext()) {
027: ServerThreadContext txn = (ServerThreadContext) openTransactions
028: .next();
029: txn.setCycle(null); // null this out just in case it was corrupted by some exception in a previous scan
030:
031: if (!inDeadlock.contains(txn)) {
032: visit(txn);
033: }
034: }
035: }
036:
037: private void visit(final ServerThreadContext me) {
038: if (!me.isWaiting())
039: return;
040:
041: final Lock waitingOn = me.getWaitingOn();
042: final Collection holders = waitingOn.getHoldersCollection();
043:
044: for (final Iterator iter = holders.iterator(); iter.hasNext();) {
045: Holder holder = (Holder) iter.next();
046: ServerThreadContext them = holder.getThreadContext();
047:
048: if (!them.equals(me)) {
049: if (them.isWaiting()) {
050: me.setCycle(them);
051: if (them.getCycle() != null) {
052: handleDeadlock(me, them);
053: } else {
054: visit(them);
055: }
056: me.setCycle(null);
057: }
058: }
059: }
060: }
061:
062: private void handleDeadlock(ServerThreadContext me,
063: ServerThreadContext them) {
064: List txnList = getTransactionsInCycle(me, them);
065: inDeadlock.addAll(txnList);
066:
067: DeadlockChainImpl head = null;
068: DeadlockChainImpl link = null;
069:
070: ServerThreadContext[] txnArray = (ServerThreadContext[]) txnList
071: .toArray(EMPTY_TXN_ARRAY);
072: for (int i = 0, n = txnArray.length; i < n; i++) {
073: ServerThreadContext txn = txnArray[i];
074: DeadlockChainImpl tmp = new DeadlockChainImpl(txn.getId(),
075: txn.getWaitingOn().getLockID());
076:
077: if (head == null) {
078: head = tmp;
079: }
080:
081: if (link != null) {
082: link.setNextLink(tmp);
083: }
084:
085: link = tmp;
086: }
087:
088: link.setNextLink(head);
089:
090: listener.foundDeadlock(head);
091: }
092:
093: private static List getTransactionsInCycle(ServerThreadContext me,
094: ServerThreadContext them) {
095: List txns = new ArrayList();
096: txns.add(me);
097:
098: do {
099: txns.add(them);
100: them = them.getCycle();
101: } while (!them.equals(me));
102:
103: return txns;
104: }
105: }
|