001: // You can redistribute this software and/or modify it under the terms of
002: // the Ozone Core License version 1 published by ozone-db.org.
003: //
004: // The original code and portions created by SMB are
005: // Copyright (C) 1997-@year@ by SMB GmbH. All rights reserved.
006: //
007: // $Id: EdgeChasing.java,v 1.2 2002/06/08 00:49:39 mediumnet Exp $
008:
009: package org.ozoneDB.core.dr;
010:
011: import java.util.HashSet;
012:
013: import org.ozoneDB.DxLib.*;
014: import org.ozoneDB.core.*;
015: import org.ozoneDB.util.*;
016:
017: /**
018: * @author <a href="http://www.softwarebuero.de/">SMB</a>
019: * @version $Revision: 1.2 $Date: 2002/06/08 00:49:39 $
020: */
021: public final class EdgeChasing extends DeadlockRecognition {
022:
023: protected Env env;
024:
025: public EdgeChasing(Env _env) {
026: env = _env;
027: }
028:
029: public Locker detectDeadlock(Locker locker) {
030: // env.logWriter.newEntry( this, "*** detectDeadlock(): " + locker, LogWriter.DEBUG );
031: // return sendLockMessage( locker, locker, true ) ? locker : null;
032: return sendLockMessage(locker, locker, true);
033: }
034:
035: /**
036: * Recursive deadlock recognition.
037: * @return True, if this transaction is blocked by root (?)
038: */
039: public Locker sendLockMessage(Locker root, Locker locker,
040: boolean firstLevel) {
041: HashSet visitingLockers = new HashSet(); // The lockers we are currently already visiting
042:
043: return sendLockMessage(root, locker, firstLevel,
044: visitingLockers);
045: }
046:
047: /**
048: * Recursive deadlock recognition.
049: * @return True, if this transaction is blocked by root (?)
050: */
051: public Locker sendLockMessage(Locker root, Locker locker,
052: boolean firstLevel, HashSet visitingLockers) {
053: if (!locker.isDeadlocked()) {
054: if (visitingLockers.add(locker)) {
055: try {
056: env.logWriter.newEntry(this ,
057: "*** sendLockMessage(): " + locker
058: + ", visitingLockers="
059: + visitingLockers + ".",
060: LogWriter.DEBUG);
061: Lockable blocker = locker.blockedByAndPin();
062:
063: if (blocker == null) {
064: return null;
065: }
066:
067: try {
068: if (!firstLevel) {
069: if (root == locker) {
070: return null;
071: }
072:
073: if (blocker == null) {
074: return null;
075: }
076: }
077:
078: //bin selbst beim warten auf blocker blockiert; wenn ich
079: //lese-lock setzen moechte, muss ich die ta mit schreib-lock
080: //auf blocker kontrollieren; wenn schreib-lock alle ta mit
081: //lese-lock auf blocker - diese werden genau von allLockers()
082: //geliefert
083:
084: //alle ta, die mich behindern; entweder ein schreibende oder
085: //viele lesende transaktionen
086: DxCollection lockers = blocker.allLockers();
087: Locker deadLockingLocker = null;
088:
089: if (lockers != null) {
090: DxIterator it = lockers.iterator();
091:
092: while (it.next() != null) {
093: Locker nextLocker = (Locker) it
094: .object();
095: if (nextLocker != locker) {
096: if (visitingLockers
097: .contains(nextLocker)) {
098: deadLockingLocker = nextLocker;
099: /*
100: We know we already are deadlocking. But let's traverse deeper if possible.
101: In this case, we could find a second deadlock ring which the first depends
102: on.
103:
104: What if we find a deadLockingLocker, it is the only one, but a locker which this
105: locker depends on still has some locker free? If we still get deadlock-livelocks
106: (deadlocks are resolved but they happen again and again in the same way), we
107: have to consider this.
108:
109: Oh, these livelocks just happened..
110: */
111: nextLocker.setDeadlocked(true);
112: } else {
113: // deadLockingLocker = null;
114: }
115: //we are done if we have detected the first circle;
116: //go on with next candidate otherwise
117:
118: Locker deadlocker = sendLockMessage(
119: root, nextLocker, false,
120: visitingLockers);
121:
122: // We continue our traversal until we reached every potential deadlocker (we have to do this due to deadlock-loops)
123: if (deadlocker != null) {
124: if (false) {
125: return deadlocker;
126: } else {
127: deadLockingLocker = deadlocker;
128: }
129: }
130: }
131: }
132: }
133:
134: return deadLockingLocker;
135: } finally {
136: blocker.unpin();
137: }
138: } finally {
139: visitingLockers.remove(locker);
140: }
141: } else {
142: if (!locker.isDeadlocked()) {
143: locker.setDeadlocked(true);
144: env.logWriter
145: .newEntry(
146: this ,
147: "sendLockMessage(): We are about to visit "
148: + locker
149: + " twice (visitingLockers="
150: + visitingLockers
151: + "). This must not be because we would loop.",
152: LogWriter.ERROR);
153: } else {
154: env.logWriter
155: .newEntry(
156: this ,
157: "sendLockMessage(): We were about to visit "
158: + locker
159: + " twice (visitingLockers="
160: + visitingLockers
161: + "), but locker is already deadlocked.",
162: LogWriter.ERROR);
163: }
164: return locker;
165: }
166: } else {
167: // env.logWriter.newEntry(this,"sendLockMessage(): "+locker+" is deadlocked.",LogWriter.DEBUG2);
168: return locker;
169: }
170: }
171:
172: }
|