KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > apache > derby > impl > services > locks > Deadlock


1 /*
2
3    Derby - Class org.apache.derby.impl.services.locks.Deadlock
4
5    Licensed to the Apache Software Foundation (ASF) under one or more
6    contributor license agreements. See the NOTICE file distributed with
7    this work for additional information regarding copyright ownership.
8    The ASF licenses this file to you under the Apache License, Version 2.0
9    (the "License"); you may not use this file except in compliance with
10    the License. You may obtain a copy of the License at
11
12       http://www.apache.org/licenses/LICENSE-2.0
13
14    Unless required by applicable law or agreed to in writing, software
15    distributed under the License is distributed on an "AS IS" BASIS,
16    WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17    See the License for the specific language governing permissions and
18    limitations under the License.
19
20  */
21
22 package org.apache.derby.impl.services.locks;
23
24 import org.apache.derby.iapi.services.locks.Lockable;
25 import org.apache.derby.iapi.services.locks.VirtualLockTable;
26
27 import org.apache.derby.iapi.services.sanity.SanityManager;
28
29 import org.apache.derby.iapi.error.StandardException;
30 import org.apache.derby.iapi.reference.SQLState;
31
32 import org.apache.derby.iapi.sql.conn.LanguageConnectionFactory;
33 import org.apache.derby.iapi.sql.conn.LanguageConnectionContext;
34 import org.apache.derby.iapi.services.context.ContextService;
35 import org.apache.derby.iapi.store.access.TransactionController;
36 import org.apache.derby.iapi.store.access.TransactionInfo;
37
38 import java.util.Hashtable JavaDoc;
39 import java.util.Enumeration JavaDoc;
40 import java.util.Dictionary JavaDoc;
41 import java.util.Stack JavaDoc;
42
43 import java.util.List JavaDoc;
44
45 /**
46     Code to support deadlock detection.
47 */
48
49 class Deadlock {
50
51     private Deadlock() {}
52
53     static Object JavaDoc[] look(SinglePool factory, LockSet set, LockControl control, ActiveLock startingLock, byte deadlockWake) {
54
55         // step one, get a list of all waiters
56 Dictionary JavaDoc waiters = Deadlock.getWaiters(set);
57
58         // This stack will track the potential deadlock chain
59 // The Stack consists of
60
61         // start (Vector element 0)
62 // - Compatibility space of waiter A
63 // - Stack of compatibility spaces with granted lock for waiter A
64
65         Stack JavaDoc chain = new Stack JavaDoc();
66
67         chain.push(startingLock.getCompatabilitySpace());
68         chain.push(control.getGrants());
69 outer: for (;;) {
70
71             if (chain.isEmpty()) {
72                 // all done
73 break outer;
74             }
75
76             List JavaDoc grants = (List JavaDoc) chain.peek();
77             if (grants.isEmpty()) {
78                 // pop this list of granted locks and back to the previous one
79 rollback(chain);
80                 continue outer;
81             }
82             int endStack = grants.size() - 1;
83             Object JavaDoc space = ((Lock) grants.get(endStack)).getCompatabilitySpace();
84
85             // this stack of granted locks can contain multiple entries
86 // for a single space. We don't want to do deadlock detection
87 // twice so check to see if we have seen this space already.
88 for (int gs = 0; gs < endStack; gs++) {
89                 if (space.equals(((Lock) grants.get(gs)).getCompatabilitySpace())) {
90                     chain.push(space); // set up as rollback() expects.
91 rollback(chain);
92                     continue outer;
93                 }
94             }
95
96             // find if this space is waiting on anyone
97 inner: for (;;) {
98                 int index = chain.indexOf(space);
99                 if (index != -1) {
100
101                     // We could be seeing a situation here like
102 // Granted T1{S}, T2{S}
103 // Waiting T1{X} - deadlock checking on this
104 //
105 // In this case it's not a deadlock, although it
106 // depends on the locking policy of the Lockable. E.g.
107 // Granted T1(latch)
108 // Waiting T1(latch)
109 // is a deadlock.
110 //
111
112                     if ((index == (chain.size() - 1)) ||
113                         ((index == (chain.size() - 2))
114                         && (index == (chain.indexOf(grants) - 1)))) {
115
116                         // potential self deadlock, but probably not!
117 ActiveLock lock = (ActiveLock) waiters.get(space);
118
119                         if (lock.canSkip) {
120                             // not a deadlock ...
121 chain.push(space); // set up as rollback() expects.
122
123                             rollback(chain);
124                             continue outer;
125                         }
126                     }
127
128                     return Deadlock.handle(factory, chain, index, waiters, deadlockWake);
129                 }
130                 chain.push(space);
131
132                 Lock waitingLock = (Lock) waiters.get(space);
133                 if (waitingLock == null) {
134                     // end of the road, no deadlock in this path
135 // pop items until the previous Stack
136 rollback(chain);
137                     continue outer;
138                 }
139
140                 // Is a LockControl or another ActiveLock
141 Object JavaDoc waitOn = waiters.get(waitingLock);
142                 if (waitOn instanceof LockControl) {
143
144                     LockControl waitOnControl = (LockControl) waitOn;
145
146                     // This lock control may have waiters but no
147 // one holding the lock. This is true if lock
148 // has just been released but the waiters haven't
149 // woken up, or they are trying to get the synchronization we hold.
150
151                     if (waitOnControl.isUnlocked()) {
152                         // end of the road, no deadlock in this path
153 // pop items until the previous Stack
154 rollback(chain);
155                         continue outer;
156                     }
157
158                     chain.push(waitOnControl.getGrants());
159
160                     continue outer;
161                 } else {
162                     // simply waiting on another waiter
163 space = waitingLock.getCompatabilitySpace();
164                 }
165         }
166         }
167
168         return null;
169     }
170
171     private static void rollback(Stack JavaDoc chain) {
172         do {
173             chain.pop();
174             if (chain.isEmpty())
175                 return;
176         } while (!(chain.peek() instanceof List JavaDoc));
177
178         // remove the last element, the one we were looking at
179 List JavaDoc grants = (List JavaDoc) chain.peek();
180         grants.remove(grants.size() - 1);
181     }
182
183     private static Hashtable JavaDoc getWaiters(LockSet set) {
184
185         Hashtable JavaDoc waiters = new Hashtable JavaDoc(set.size() * 2);
186
187         for (Enumeration JavaDoc e = set.elements(); e.hasMoreElements(); ) {
188
189             Control control = (Control) e.nextElement();
190
191             control.addWaiters(waiters);
192         }
193
194         return waiters;
195     }
196
197     private static Object JavaDoc[] handle(SinglePool factory, Stack JavaDoc chain, int start, Dictionary JavaDoc waiters, byte deadlockWake) {
198
199         // If start is zero then the space that started looking for the
200 // deadlock is activly involved in the deadlock.
201
202         Object JavaDoc checker = chain.elementAt(0);
203
204         int minLockCount = Integer.MAX_VALUE;
205         Object JavaDoc victim = null;
206         for (int i = start; i < chain.size(); i++) {
207             Object JavaDoc space = chain.elementAt(i);
208             if (space instanceof List JavaDoc) {
209                 continue;
210             }
211
212             // See if the checker is in the deadlock and we
213 // already picked as a victim
214 if ((checker.equals(space)) && (deadlockWake == Constants.WAITING_LOCK_DEADLOCK)) {
215                 victim = checker;
216                 break;
217             }
218
219             LockSpace ls = (LockSpace) factory.get(space);
220             if (ls == null) {
221                 // space only holds latches, pick as victim
222 victim = space;
223                 break;
224             }
225
226             int spaceCount = ls.deadlockCount(minLockCount);
227
228             if (spaceCount <= minLockCount) {
229                 victim = space;
230                 minLockCount = spaceCount;
231             }
232         }
233
234         // See if the vitim is the one doing the checking
235 if (checker.equals(victim)) {
236             Object JavaDoc[] data = new Object JavaDoc[2];
237             data[0] = chain;
238             data[1] = waiters;
239             return data;
240         }
241
242         ActiveLock victimLock = (ActiveLock) waiters.get(victim);
243
244         victimLock.wakeUp(Constants.WAITING_LOCK_DEADLOCK);
245
246         return null;
247
248     }
249
250     static StandardException buildException(SinglePool factory, Object JavaDoc[] data) {
251
252         Stack JavaDoc chain = (Stack JavaDoc) data[0];
253         Dictionary JavaDoc waiters = (Dictionary JavaDoc) data[1];
254
255
256         LanguageConnectionContext lcc = (LanguageConnectionContext)
257             ContextService.getContext(LanguageConnectionContext.CONTEXT_ID);
258
259         TableNameInfo tabInfo = null;
260         TransactionInfo[] tt = null;
261         TransactionController tc = null;
262
263         if (lcc != null) {
264
265             try {
266                 tc = lcc.getTransactionExecute();
267                 tabInfo = new TableNameInfo(lcc, false);
268
269                 tt = lcc.getLanguageConnectionFactory().getAccessFactory().getTransactionInfo();
270
271             } catch (StandardException se) {
272                 // just don't get any table info.
273 }
274         }
275
276
277         StringBuffer JavaDoc sb = new StringBuffer JavaDoc(200);
278
279         Hashtable JavaDoc attributes = new Hashtable JavaDoc(17);
280
281         String JavaDoc victimXID = null;
282
283         for (int i = 0; i < chain.size(); i++) {
284             Object JavaDoc space = chain.elementAt(i);
285             if (space instanceof List JavaDoc) {
286                 List JavaDoc grants = (List JavaDoc) space;
287
288                 if (grants.size() != 0) {
289
290                     sb.append(" Granted XID : ");
291
292                     for (int j = 0; j < grants.size(); j ++) {
293
294                         if (j != 0)
295                             sb.append(", ");
296
297                         Lock gl = (Lock) grants.get(j);
298
299                         sb.append("{");
300                         sb.append(gl.getCompatabilitySpace());
301                         sb.append(", ");
302                         sb.append(gl.getQualifier());
303                         sb.append("} ");
304                     }
305                     sb.append('\n');
306                 }
307                 continue;
308             }
309             // Information about the lock we are waiting on
310 // TYPE |TABLENAME |LOCKNAME
311 Lock lock = ((Lock) waiters.get(space));
312             
313             // see if this lockable object wants to participate
314 lock.getLockable().lockAttributes(VirtualLockTable.ALL, attributes);
315
316             addInfo(sb, "Lock : ", attributes.get(VirtualLockTable.LOCKTYPE));
317             if (tabInfo != null) {
318                 Long JavaDoc conglomId = (Long JavaDoc) attributes.get(VirtualLockTable.CONGLOMID);
319                 if (conglomId == null) {
320                     Long JavaDoc containerId = (Long JavaDoc) attributes.get(VirtualLockTable.CONTAINERID);
321                     try {
322                         conglomId = new Long JavaDoc(tc.findConglomid(containerId.longValue()));
323                     } catch (StandardException se) {
324                     }
325                 }
326                 addInfo(sb, ", ", tabInfo.getTableName(conglomId));
327             }
328             addInfo(sb, ", ", attributes.get(VirtualLockTable.LOCKNAME));
329             sb.append('\n');
330
331             String JavaDoc xid = space.toString();
332             if (i == 0)
333                 victimXID = xid;
334
335
336             addInfo(sb, " Waiting XID : {", xid);
337             addInfo(sb, ", ", lock.getQualifier());
338             sb.append("} ");
339             if (tt != null) {
340                 for (int tti = tt.length - 1; tti >= 0; tti--) {
341                     TransactionInfo ti = tt[tti];
342
343                     // RESOLVE (track 2771) - not sure why
344 // ti.getTransactionIdString() or ti can return null.
345 if (ti != null)
346                     {
347                         String JavaDoc idString = ti.getTransactionIdString();
348
349                         if (idString != null && idString.equals(xid)) {
350
351                             addInfo(sb, ", ", ti.getUsernameString());
352                             addInfo(sb, ", ", ti.getStatementTextString());
353                             break;
354                         }
355                     }
356                 }
357             }
358             sb.append('\n');
359
360             attributes.clear();
361         }
362
363         StandardException se = StandardException.newException(SQLState.DEADLOCK, sb.toString(), victimXID);
364         se.setReport(factory.deadlockMonitor);
365         return se;
366     }
367
368     private static void addInfo(StringBuffer JavaDoc sb, String JavaDoc desc, Object JavaDoc data) {
369         sb.append(desc);
370         if (data == null)
371             data = "?";
372         sb.append(data);
373     }
374
375 }
376
Popular Tags