001: /*
002:
003: Derby - Class org.apache.derby.impl.services.locks.Deadlock
004:
005: Licensed to the Apache Software Foundation (ASF) under one or more
006: contributor license agreements. See the NOTICE file distributed with
007: this work for additional information regarding copyright ownership.
008: The ASF licenses this file to you under the Apache License, Version 2.0
009: (the "License"); you may not use this file except in compliance with
010: the License. You may obtain a copy of the License at
011:
012: http://www.apache.org/licenses/LICENSE-2.0
013:
014: Unless required by applicable law or agreed to in writing, software
015: distributed under the License is distributed on an "AS IS" BASIS,
016: WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
017: See the License for the specific language governing permissions and
018: limitations under the License.
019:
020: */
021:
022: package org.apache.derby.impl.services.locks;
023:
024: import org.apache.derby.iapi.services.locks.Lockable;
025: import org.apache.derby.iapi.services.locks.VirtualLockTable;
026:
027: import org.apache.derby.iapi.services.sanity.SanityManager;
028:
029: import org.apache.derby.iapi.error.StandardException;
030: import org.apache.derby.iapi.reference.SQLState;
031:
032: import org.apache.derby.iapi.sql.conn.LanguageConnectionFactory;
033: import org.apache.derby.iapi.sql.conn.LanguageConnectionContext;
034: import org.apache.derby.iapi.services.context.ContextService;
035: import org.apache.derby.iapi.store.access.TransactionController;
036: import org.apache.derby.iapi.store.access.TransactionInfo;
037:
038: import java.util.Hashtable;
039: import java.util.Enumeration;
040: import java.util.Dictionary;
041: import java.util.Stack;
042:
043: import java.util.List;
044:
045: /**
046: Code to support deadlock detection.
047: */
048:
049: class Deadlock {
050:
051: private Deadlock() {
052: }
053:
054: static Object[] look(SinglePool factory, LockSet set,
055: LockControl control, ActiveLock startingLock,
056: byte deadlockWake) {
057:
058: // step one, get a list of all waiters
059: Dictionary waiters = Deadlock.getWaiters(set);
060:
061: // This stack will track the potential deadlock chain
062: // The Stack consists of
063:
064: // start (Vector element 0)
065: // - Compatibility space of waiter A
066: // - Stack of compatibility spaces with granted lock for waiter A
067:
068: Stack chain = new Stack();
069:
070: chain.push(startingLock.getCompatabilitySpace());
071: chain.push(control.getGrants());
072: outer: for (;;) {
073:
074: if (chain.isEmpty()) {
075: // all done
076: break outer;
077: }
078:
079: List grants = (List) chain.peek();
080: if (grants.isEmpty()) {
081: // pop this list of granted locks and back to the previous one
082: rollback(chain);
083: continue outer;
084: }
085: int endStack = grants.size() - 1;
086: Object space = ((Lock) grants.get(endStack))
087: .getCompatabilitySpace();
088:
089: // this stack of granted locks can contain multiple entries
090: // for a single space. We don't want to do deadlock detection
091: // twice so check to see if we have seen this space already.
092: for (int gs = 0; gs < endStack; gs++) {
093: if (space.equals(((Lock) grants.get(gs))
094: .getCompatabilitySpace())) {
095: chain.push(space); // set up as rollback() expects.
096: rollback(chain);
097: continue outer;
098: }
099: }
100:
101: // find if this space is waiting on anyone
102: inner: for (;;) {
103: int index = chain.indexOf(space);
104: if (index != -1) {
105:
106: // We could be seeing a situation here like
107: // Granted T1{S}, T2{S}
108: // Waiting T1{X} - deadlock checking on this
109: //
110: // In this case it's not a deadlock, although it
111: // depends on the locking policy of the Lockable. E.g.
112: // Granted T1(latch)
113: // Waiting T1(latch)
114: // is a deadlock.
115: //
116:
117: if ((index == (chain.size() - 1))
118: || ((index == (chain.size() - 2)) && (index == (chain
119: .indexOf(grants) - 1)))) {
120:
121: // potential self deadlock, but probably not!
122: ActiveLock lock = (ActiveLock) waiters
123: .get(space);
124:
125: if (lock.canSkip) {
126: // not a deadlock ...
127: chain.push(space); // set up as rollback() expects.
128:
129: rollback(chain);
130: continue outer;
131: }
132: }
133:
134: return Deadlock.handle(factory, chain, index,
135: waiters, deadlockWake);
136: }
137: chain.push(space);
138:
139: Lock waitingLock = (Lock) waiters.get(space);
140: if (waitingLock == null) {
141: // end of the road, no deadlock in this path
142: // pop items until the previous Stack
143: rollback(chain);
144: continue outer;
145: }
146:
147: // Is a LockControl or another ActiveLock
148: Object waitOn = waiters.get(waitingLock);
149: if (waitOn instanceof LockControl) {
150:
151: LockControl waitOnControl = (LockControl) waitOn;
152:
153: // This lock control may have waiters but no
154: // one holding the lock. This is true if lock
155: // has just been released but the waiters haven't
156: // woken up, or they are trying to get the synchronization we hold.
157:
158: if (waitOnControl.isUnlocked()) {
159: // end of the road, no deadlock in this path
160: // pop items until the previous Stack
161: rollback(chain);
162: continue outer;
163: }
164:
165: chain.push(waitOnControl.getGrants());
166:
167: continue outer;
168: } else {
169: // simply waiting on another waiter
170: space = waitingLock.getCompatabilitySpace();
171: }
172: }
173: }
174:
175: return null;
176: }
177:
178: private static void rollback(Stack chain) {
179: do {
180: chain.pop();
181: if (chain.isEmpty())
182: return;
183: } while (!(chain.peek() instanceof List));
184:
185: // remove the last element, the one we were looking at
186: List grants = (List) chain.peek();
187: grants.remove(grants.size() - 1);
188: }
189:
190: private static Hashtable getWaiters(LockSet set) {
191:
192: Hashtable waiters = new Hashtable(set.size() * 2);
193:
194: for (Enumeration e = set.elements(); e.hasMoreElements();) {
195:
196: Control control = (Control) e.nextElement();
197:
198: control.addWaiters(waiters);
199: }
200:
201: return waiters;
202: }
203:
204: private static Object[] handle(SinglePool factory, Stack chain,
205: int start, Dictionary waiters, byte deadlockWake) {
206:
207: // If start is zero then the space that started looking for the
208: // deadlock is activly involved in the deadlock.
209:
210: Object checker = chain.elementAt(0);
211:
212: int minLockCount = Integer.MAX_VALUE;
213: Object victim = null;
214: for (int i = start; i < chain.size(); i++) {
215: Object space = chain.elementAt(i);
216: if (space instanceof List) {
217: continue;
218: }
219:
220: // See if the checker is in the deadlock and we
221: // already picked as a victim
222: if ((checker.equals(space))
223: && (deadlockWake == Constants.WAITING_LOCK_DEADLOCK)) {
224: victim = checker;
225: break;
226: }
227:
228: LockSpace ls = (LockSpace) factory.get(space);
229: if (ls == null) {
230: // space only holds latches, pick as victim
231: victim = space;
232: break;
233: }
234:
235: int spaceCount = ls.deadlockCount(minLockCount);
236:
237: if (spaceCount <= minLockCount) {
238: victim = space;
239: minLockCount = spaceCount;
240: }
241: }
242:
243: // See if the vitim is the one doing the checking
244: if (checker.equals(victim)) {
245: Object[] data = new Object[2];
246: data[0] = chain;
247: data[1] = waiters;
248: return data;
249: }
250:
251: ActiveLock victimLock = (ActiveLock) waiters.get(victim);
252:
253: victimLock.wakeUp(Constants.WAITING_LOCK_DEADLOCK);
254:
255: return null;
256:
257: }
258:
259: static StandardException buildException(SinglePool factory,
260: Object[] data) {
261:
262: Stack chain = (Stack) data[0];
263: Dictionary waiters = (Dictionary) data[1];
264:
265: LanguageConnectionContext lcc = (LanguageConnectionContext) ContextService
266: .getContext(LanguageConnectionContext.CONTEXT_ID);
267:
268: TableNameInfo tabInfo = null;
269: TransactionInfo[] tt = null;
270: TransactionController tc = null;
271:
272: if (lcc != null) {
273:
274: try {
275: tc = lcc.getTransactionExecute();
276: tabInfo = new TableNameInfo(lcc, false);
277:
278: tt = lcc.getLanguageConnectionFactory()
279: .getAccessFactory().getTransactionInfo();
280:
281: } catch (StandardException se) {
282: // just don't get any table info.
283: }
284: }
285:
286: StringBuffer sb = new StringBuffer(200);
287:
288: Hashtable attributes = new Hashtable(17);
289:
290: String victimXID = null;
291:
292: for (int i = 0; i < chain.size(); i++) {
293: Object space = chain.elementAt(i);
294: if (space instanceof List) {
295: List grants = (List) space;
296:
297: if (grants.size() != 0) {
298:
299: sb.append(" Granted XID : ");
300:
301: for (int j = 0; j < grants.size(); j++) {
302:
303: if (j != 0)
304: sb.append(", ");
305:
306: Lock gl = (Lock) grants.get(j);
307:
308: sb.append("{");
309: sb.append(gl.getCompatabilitySpace());
310: sb.append(", ");
311: sb.append(gl.getQualifier());
312: sb.append("} ");
313: }
314: sb.append('\n');
315: }
316: continue;
317: }
318: // Information about the lock we are waiting on
319: // TYPE |TABLENAME |LOCKNAME
320: Lock lock = ((Lock) waiters.get(space));
321:
322: // see if this lockable object wants to participate
323: lock.getLockable().lockAttributes(VirtualLockTable.ALL,
324: attributes);
325:
326: addInfo(sb, "Lock : ", attributes
327: .get(VirtualLockTable.LOCKTYPE));
328: if (tabInfo != null) {
329: Long conglomId = (Long) attributes
330: .get(VirtualLockTable.CONGLOMID);
331: if (conglomId == null) {
332: Long containerId = (Long) attributes
333: .get(VirtualLockTable.CONTAINERID);
334: try {
335: conglomId = new Long(tc
336: .findConglomid(containerId.longValue()));
337: } catch (StandardException se) {
338: }
339: }
340: addInfo(sb, ", ", tabInfo.getTableName(conglomId));
341: }
342: addInfo(sb, ", ", attributes.get(VirtualLockTable.LOCKNAME));
343: sb.append('\n');
344:
345: String xid = space.toString();
346: if (i == 0)
347: victimXID = xid;
348:
349: addInfo(sb, " Waiting XID : {", xid);
350: addInfo(sb, ", ", lock.getQualifier());
351: sb.append("} ");
352: if (tt != null) {
353: for (int tti = tt.length - 1; tti >= 0; tti--) {
354: TransactionInfo ti = tt[tti];
355:
356: // RESOLVE (track 2771) - not sure why
357: // ti.getTransactionIdString() or ti can return null.
358: if (ti != null) {
359: String idString = ti.getTransactionIdString();
360:
361: if (idString != null && idString.equals(xid)) {
362:
363: addInfo(sb, ", ", ti.getUsernameString());
364: addInfo(sb, ", ", ti
365: .getStatementTextString());
366: break;
367: }
368: }
369: }
370: }
371: sb.append('\n');
372:
373: attributes.clear();
374: }
375:
376: StandardException se = StandardException.newException(
377: SQLState.DEADLOCK, sb.toString(), victimXID);
378: se.setReport(factory.deadlockMonitor);
379: return se;
380: }
381:
382: private static void addInfo(StringBuffer sb, String desc,
383: Object data) {
384: sb.append(desc);
385: if (data == null)
386: data = "?";
387: sb.append(data);
388: }
389:
390: }
|