|
122
|
1 /*******************************************************************************
|
|
|
2 * Copyright (c) 2003, 2006 IBM Corporation and others.
|
|
|
3 * All rights reserved. This program and the accompanying materials
|
|
|
4 * are made available under the terms of the Eclipse Public License v1.0
|
|
|
5 * which accompanies this distribution, and is available at
|
|
|
6 * http://www.eclipse.org/legal/epl-v10.html
|
|
|
7 *
|
|
|
8 * Contributors:
|
|
|
9 * IBM Corporation - initial API and implementation
|
|
|
10 * Port to the D programming language:
|
|
|
11 * Frank Benoit <benoit@tionex.de>
|
|
|
12 *******************************************************************************/
|
|
|
13 module dwtx.core.internal.jobs.DeadlockDetector;
|
|
|
14
|
|
|
15 import tango.core.Thread;
|
|
|
16 import tango.io.Stdout;
|
|
|
17 import tango.text.convert.Format;
|
|
|
18
|
|
|
19 import dwt.dwthelper.utils;
|
|
|
20 import dwtx.dwtxhelper.Collection;
|
|
|
21
|
|
|
22 import dwtx.core.internal.runtime.RuntimeLog;
|
|
|
23 import dwtx.core.runtime.Assert;
|
|
|
24 import dwtx.core.runtime.IStatus;
|
|
|
25 import dwtx.core.runtime.MultiStatus;
|
|
|
26 import dwtx.core.runtime.Status;
|
|
|
27 import dwtx.core.runtime.jobs.ILock;
|
|
|
28 import dwtx.core.runtime.jobs.ISchedulingRule;
|
|
|
29 import dwtx.core.internal.jobs.Deadlock;
|
|
|
30 import dwtx.core.internal.jobs.JobManager;
|
|
|
31
|
|
|
32 /**
|
|
|
33 * Stores all the relationships between locks (rules are also considered locks),
|
|
|
34 * and the threads that own them. All the relationships are stored in a 2D integer array.
|
|
|
35 * The rows in the array are threads, while the columns are locks.
|
|
|
36 * Two corresponding arrayLists store the actual threads and locks.
|
|
|
37 * The index of a thread in the first arrayList is the index of the row in the graph.
|
|
|
38 * The index of a lock in the second arrayList is the index of the column in the graph.
|
|
|
39 * An entry greater than 0 in the graph is the number of times a thread in the entry's row
|
|
|
40 * acquired the lock in the entry's column.
|
|
|
41 * An entry of -1 means that the thread is waiting to acquire the lock.
|
|
|
42 * An entry of 0 means that the thread and the lock have no relationship.
|
|
|
43 *
|
|
|
44 * The difference between rules and locks is that locks can be suspended, while
|
|
|
45 * rules are implicit locks and as such cannot be suspended.
|
|
|
46 * To resolve deadlock, the graph will first try to find a thread that only owns
|
|
|
47 * locks. Failing that, it will find a thread in the deadlock that owns at least
|
|
|
48 * one lock and suspend it.
|
|
|
49 *
|
|
|
50 * Deadlock can only occur among locks, or among locks in combination with rules.
|
|
|
51 * Deadlock among rules only is impossible. Therefore, in any deadlock one can always
|
|
|
52 * find a thread that owns at least one lock that can be suspended.
|
|
|
53 *
|
|
|
54 * The implementation of the graph assumes that a thread can only own 1 rule at
|
|
|
55 * any one time. It can acquire that rule several times, but a thread cannot
|
|
|
56 * acquire 2 non-conflicting rules at the same time.
|
|
|
57 *
|
|
|
58 * The implementation of the graph will sometimes also find and resolve bogus deadlocks.
|
|
|
59 * graph: assuming this rule hierarchy:
|
|
|
60 * R2 R3 L1 R1
|
|
|
61 * J1 1 0 0 / \
|
|
|
62 * J2 0 1 -1 R2 R3
|
|
|
63 * J3 -1 0 1
|
|
|
64 *
|
|
|
65 * If in the above situation job4 decides to acquire rule1, then the graph will transform
|
|
|
66 * to the following:
|
|
|
67 * R2 R3 R1 L1
|
|
|
68 * J1 1 0 1 0
|
|
|
69 * J2 1 1 1 -1
|
|
|
70 * J3 -1 0 0 1
|
|
|
71 * J4 0 0 -1 0
|
|
|
72 *
|
|
|
73 * and the graph will assume that job2 and job3 are deadlocked and suspend lock1 of job3.
|
|
|
74 * The reason the deadlock is bogus is that the deadlock is unlikely to actually happen (the threads
|
|
|
75 * are currently not deadlocked, but might deadlock later on when it is too late to detect it)
|
|
|
76 * Therefore, in order to make sure that no deadlock is possible,
|
|
|
77 * the deadlock will still be resolved at this point.
|
|
|
78 */
|
|
|
79 class DeadlockDetector {
|
|
|
80 private static int NO_STATE = 0;
|
|
|
81 //state variables in the graph
|
|
|
82 private static int WAITING_FOR_LOCK = -1;
|
|
|
83 //empty matrix
|
|
|
84 private static const int[][] EMPTY_MATRIX = null;
|
|
|
85 //matrix of relationships between threads and locks
|
|
|
86 private int[][] graph = EMPTY_MATRIX;
|
|
|
87 //index is column in adjacency matrix for the lock
|
|
|
88 private final ArrayList locks;
|
|
|
89 //index is row in adjacency matrix for the thread
|
|
|
90 private final ArrayList lockThreads;
|
|
|
91 //whether the graph needs to be resized
|
|
|
92 private bool resize = false;
|
|
|
93
|
|
|
94 public this(){
|
|
|
95 locks = new ArrayList();
|
|
|
96 lockThreads = new ArrayList();
|
|
|
97 }
|
|
|
98
|
|
|
99 /**
|
|
|
100 * Recursively check if any of the threads that prevent the current thread from running
|
|
|
101 * are actually deadlocked with the current thread.
|
|
|
102 * Add the threads that form deadlock to the deadlockedThreads list.
|
|
|
103 */
|
|
|
104 private bool addCycleThreads(ArrayList deadlockedThreads, Thread next) {
|
|
|
105 //get the thread that block the given thread from running
|
|
|
106 Thread[] blocking = blockingThreads(next);
|
|
|
107 //if the thread is not blocked by other threads, then it is not part of a deadlock
|
|
|
108 if (blocking.length is 0)
|
|
|
109 return false;
|
|
|
110 bool inCycle = false;
|
|
|
111 for (int i = 0; i < blocking.length; i++) {
|
|
|
112 //if we have already visited the given thread, then we found a cycle
|
|
|
113 if (deadlockedThreads.contains(blocking[i])) {
|
|
|
114 inCycle = true;
|
|
|
115 } else {
|
|
|
116 //otherwise, add the thread to our list and recurse deeper
|
|
|
117 deadlockedThreads.add(blocking[i]);
|
|
|
118 //if the thread is not part of a cycle, remove it from the list
|
|
|
119 if (addCycleThreads(deadlockedThreads, blocking[i]))
|
|
|
120 inCycle = true;
|
|
|
121 else
|
|
|
122 deadlockedThreads.remove(blocking[i]);
|
|
|
123 }
|
|
|
124 }
|
|
|
125 return inCycle;
|
|
|
126 }
|
|
|
127
|
|
|
128 /**
|
|
|
129 * Get the thread(s) that own the lock this thread is waiting for.
|
|
|
130 */
|
|
|
131 private Thread[] blockingThreads(Thread current) {
|
|
|
132 //find the lock this thread is waiting for
|
|
|
133 ISchedulingRule lock = cast(ISchedulingRule) getWaitingLock(current);
|
|
|
134 return getThreadsOwningLock(lock);
|
|
|
135 }
|
|
|
136
|
|
|
137 /**
|
|
|
138 * Check that the addition of a waiting thread did not produce deadlock.
|
|
|
139 * If deadlock is detected return true, else return false.
|
|
|
140 */
|
|
|
141 private bool checkWaitCycles(int[] waitingThreads, int lockIndex) {
|
|
|
142 /**
|
|
|
143 * find the lock that this thread is waiting for
|
|
|
144 * recursively check if this is a cycle (i.e. a thread waiting on itself)
|
|
|
145 */
|
|
|
146 for (int i = 0; i < graph.length; i++) {
|
|
|
147 if (graph[i][lockIndex] > NO_STATE) {
|
|
|
148 if (waitingThreads[i] > NO_STATE) {
|
|
|
149 return true;
|
|
|
150 }
|
|
|
151 //keep track that we already visited this thread
|
|
|
152 waitingThreads[i]++;
|
|
|
153 for (int j = 0; j < graph[i].length; j++) {
|
|
|
154 if (graph[i][j] is WAITING_FOR_LOCK) {
|
|
|
155 if (checkWaitCycles(waitingThreads, j))
|
|
|
156 return true;
|
|
|
157 }
|
|
|
158 }
|
|
|
159 //this thread is not involved in a cycle yet, so remove the visited flag
|
|
|
160 waitingThreads[i]--;
|
|
|
161 }
|
|
|
162 }
|
|
|
163 return false;
|
|
|
164 }
|
|
|
165
|
|
|
166 /**
|
|
|
167 * Returns true IFF the matrix contains a row for the given thread.
|
|
|
168 * (meaning the given thread either owns locks or is waiting for locks)
|
|
|
169 */
|
|
|
170 bool contains(Thread t) {
|
|
|
171 return lockThreads.contains(t);
|
|
|
172 }
|
|
|
173
|
|
|
174 /**
|
|
|
175 * A new rule was just added to the graph.
|
|
|
176 * Find a rule it conflicts with and update the new rule with the number of times
|
|
|
177 * it was acquired implicitly when threads acquired conflicting rule.
|
|
|
178 */
|
|
|
179 private void fillPresentEntries(ISchedulingRule newLock, int lockIndex) {
|
|
|
180 //fill in the entries for the new rule from rules it conflicts with
|
|
|
181 for (int j = 0; j < locks.size(); j++) {
|
|
|
182 if ((j !is lockIndex) && (newLock.isConflicting(cast(ISchedulingRule) locks.get(j)))) {
|
|
|
183 for (int i = 0; i < graph.length; i++) {
|
|
|
184 if ((graph[i][j] > NO_STATE) && (graph[i][lockIndex] is NO_STATE))
|
|
|
185 graph[i][lockIndex] = graph[i][j];
|
|
|
186 }
|
|
|
187 }
|
|
|
188 }
|
|
|
189 //now back fill the entries for rules the current rule conflicts with
|
|
|
190 for (int j = 0; j < locks.size(); j++) {
|
|
|
191 if ((j !is lockIndex) && (newLock.isConflicting(cast(ISchedulingRule) locks.get(j)))) {
|
|
|
192 for (int i = 0; i < graph.length; i++) {
|
|
|
193 if ((graph[i][lockIndex] > NO_STATE) && (graph[i][j] is NO_STATE))
|
|
|
194 graph[i][j] = graph[i][lockIndex];
|
|
|
195 }
|
|
|
196 }
|
|
|
197 }
|
|
|
198 }
|
|
|
199
|
|
|
200 /**
|
|
|
201 * Returns all the locks owned by the given thread
|
|
|
202 */
|
|
|
203 private Object[] getOwnedLocks(Thread current) {
|
|
|
204 ArrayList ownedLocks = new ArrayList(1);
|
|
|
205 int index = indexOf(current, false);
|
|
|
206
|
|
|
207 for (int j = 0; j < graph[index].length; j++) {
|
|
|
208 if (graph[index][j] > NO_STATE)
|
|
|
209 ownedLocks.add(locks.get(j));
|
|
|
210 }
|
|
|
211 if (ownedLocks.size() is 0)
|
|
|
212 Assert.isLegal(false, "A thread with no locks is part of a deadlock."); //$NON-NLS-1$
|
|
|
213 return ownedLocks.toArray();
|
|
|
214 }
|
|
|
215
|
|
|
216 /**
|
|
|
217 * Returns an array of threads that form the deadlock (usually 2).
|
|
|
218 */
|
|
|
219 private Thread[] getThreadsInDeadlock(Thread cause) {
|
|
|
220 ArrayList deadlockedThreads = new ArrayList(2);
|
|
|
221 /**
|
|
|
222 * if the thread that caused deadlock doesn't own any locks, then it is not part
|
|
|
223 * of the deadlock (it just caused it because of a rule it tried to acquire)
|
|
|
224 */
|
|
|
225 if (ownsLocks(cause))
|
|
|
226 deadlockedThreads.add(cause);
|
|
|
227 addCycleThreads(deadlockedThreads, cause);
|
|
|
228 return arraycast!(Thread)( deadlockedThreads.toArray());
|
|
|
229 }
|
|
|
230
|
|
|
231 /**
|
|
|
232 * Returns the thread(s) that own the given lock.
|
|
|
233 */
|
|
|
234 private Thread[] getThreadsOwningLock(ISchedulingRule rule) {
|
|
|
235 if (rule is null)
|
|
|
236 return new Thread[0];
|
|
|
237 int lockIndex = indexOf(rule, false);
|
|
|
238 ArrayList blocking = new ArrayList(1);
|
|
|
239 for (int i = 0; i < graph.length; i++) {
|
|
|
240 if (graph[i][lockIndex] > NO_STATE)
|
|
|
241 blocking.add(lockThreads.get(i));
|
|
|
242 }
|
|
|
243 if ((blocking.size() is 0) && (JobManager.DEBUG_LOCKS))
|
|
|
244 Stdout.formatln(Format("Lock {} is involved in deadlock but is not owned by any thread.", rule )); //$NON-NLS-1$ //$NON-NLS-2$
|
|
|
245 if ((blocking.size() > 1) && (cast(ILock)rule ) && (JobManager.DEBUG_LOCKS))
|
|
|
246 Stdout.formatln(Format("Lock {} is owned by more than 1 thread, but it is not a rule.", rule )); //$NON-NLS-1$ //$NON-NLS-2$
|
|
|
247 return arraycast!(Thread)( blocking.toArray());
|
|
|
248 }
|
|
|
249
|
|
|
250 /**
|
|
|
251 * Returns the lock the given thread is waiting for.
|
|
|
252 */
|
|
|
253 private Object getWaitingLock(Thread current) {
|
|
|
254 int index = indexOf(current, false);
|
|
|
255 //find the lock that this thread is waiting for
|
|
|
256 for (int j = 0; j < graph[index].length; j++) {
|
|
|
257 if (graph[index][j] is WAITING_FOR_LOCK)
|
|
|
258 return locks.get(j);
|
|
|
259 }
|
|
|
260 //it can happen that a thread is not waiting for any lock (it is not really part of the deadlock)
|
|
|
261 return null;
|
|
|
262 }
|
|
|
263
|
|
|
264 /**
|
|
|
265 * Returns the index of the given lock in the lock array. If the lock is
|
|
|
266 * not present in the array, it is added to the end.
|
|
|
267 */
|
|
|
268 private int indexOf(ISchedulingRule lock, bool add) {
|
|
|
269 int index = locks.indexOf(cast(Object)lock);
|
|
|
270 if ((index < 0) && add) {
|
|
|
271 locks.add(cast(Object)lock);
|
|
|
272 resize = true;
|
|
|
273 index = locks.size() - 1;
|
|
|
274 }
|
|
|
275 return index;
|
|
|
276 }
|
|
|
277
|
|
|
278 /**
|
|
|
279 * Returns the index of the given thread in the thread array. If the thread
|
|
|
280 * is not present in the array, it is added to the end.
|
|
|
281 */
|
|
|
282 private int indexOf(Thread owner, bool add) {
|
|
|
283 int index = lockThreads.indexOf(owner);
|
|
|
284 if ((index < 0) && add) {
|
|
|
285 lockThreads.add(owner);
|
|
|
286 resize = true;
|
|
|
287 index = lockThreads.size() - 1;
|
|
|
288 }
|
|
|
289 return index;
|
|
|
290 }
|
|
|
291
|
|
|
292 /**
|
|
|
293 * Returns true IFF the adjacency matrix is empty.
|
|
|
294 */
|
|
|
295 bool isEmpty() {
|
|
|
296 return (locks.size() is 0) && (lockThreads.size() is 0) && (graph.length is 0);
|
|
|
297 }
|
|
|
298
|
|
|
299 /**
|
|
|
300 * The given lock was acquired by the given thread.
|
|
|
301 */
|
|
|
302 void lockAcquired(Thread owner, ISchedulingRule lock) {
|
|
|
303 int lockIndex = indexOf(lock, true);
|
|
|
304 int threadIndex = indexOf(owner, true);
|
|
|
305 if (resize)
|
|
|
306 resizeGraph();
|
|
|
307 if (graph[threadIndex][lockIndex] is WAITING_FOR_LOCK)
|
|
|
308 graph[threadIndex][lockIndex] = NO_STATE;
|
|
|
309 /**
|
|
|
310 * acquire all locks that conflict with the given lock
|
|
|
311 * or conflict with a lock the given lock will acquire implicitly
|
|
|
312 * (locks are acquired implicitly when a conflicting lock is acquired)
|
|
|
313 */
|
|
|
314 ArrayList conflicting = new ArrayList(1);
|
|
|
315 //only need two passes through all the locks to pick up all conflicting rules
|
|
|
316 int NUM_PASSES = 2;
|
|
|
317 conflicting.add(cast(Object)lock);
|
|
|
318 graph[threadIndex][lockIndex]++;
|
|
|
319 for (int i = 0; i < NUM_PASSES; i++) {
|
|
|
320 for (int k = 0; k < conflicting.size(); k++) {
|
|
|
321 ISchedulingRule current = cast(ISchedulingRule) conflicting.get(k);
|
|
|
322 for (int j = 0; j < locks.size(); j++) {
|
|
|
323 ISchedulingRule possible = cast(ISchedulingRule) locks.get(j);
|
|
|
324 if (current.isConflicting(possible) && !conflicting.contains(cast(Object)possible)) {
|
|
|
325 conflicting.add(cast(Object)possible);
|
|
|
326 graph[threadIndex][j]++;
|
|
|
327 }
|
|
|
328 }
|
|
|
329 }
|
|
|
330 }
|
|
|
331 }
|
|
|
332
|
|
|
333 /**
|
|
|
334 * The given lock was released by the given thread. Update the graph.
|
|
|
335 */
|
|
|
336 void lockReleased(Thread owner, ISchedulingRule lock) {
|
|
|
337 int lockIndex = indexOf(lock, false);
|
|
|
338 int threadIndex = indexOf(owner, false);
|
|
|
339 //make sure the lock and thread exist in the graph
|
|
|
340 if (threadIndex < 0) {
|
|
|
341 if (JobManager.DEBUG_LOCKS)
|
|
|
342 Stdout.formatln("[lockReleased] Lock {} was already released by thread {}", lock, owner.name()); //$NON-NLS-1$ //$NON-NLS-2$
|
|
|
343 return;
|
|
|
344 }
|
|
|
345 if (lockIndex < 0) {
|
|
|
346 if (JobManager.DEBUG_LOCKS)
|
|
|
347 Stdout.formatln("[lockReleased] Thread {} already released lock {}", owner.name(), lock); //$NON-NLS-1$ //$NON-NLS-2$
|
|
|
348 return;
|
|
|
349 }
|
|
|
350 //if this lock was suspended, set it to NO_STATE
|
|
|
351 if ((cast(ILock)lock ) && (graph[threadIndex][lockIndex] is WAITING_FOR_LOCK)) {
|
|
|
352 graph[threadIndex][lockIndex] = NO_STATE;
|
|
|
353 return;
|
|
|
354 }
|
|
|
355 //release all locks that conflict with the given lock
|
|
|
356 //or release all rules that are owned by the given thread, if we are releasing a rule
|
|
|
357 for (int j = 0; j < graph[threadIndex].length; j++) {
|
|
|
358 if ((lock.isConflicting(cast(ISchedulingRule) locks.get(j))) || (!(cast(ILock)lock ) && !(cast(ILock)locks.get(j)) && (graph[threadIndex][j] > NO_STATE))) {
|
|
|
359 if (graph[threadIndex][j] is NO_STATE) {
|
|
|
360 if (JobManager.DEBUG_LOCKS)
|
|
|
361 Stdout.formatln("[lockReleased] More releases than acquires for thread {} and lock {}", owner.name(), lock); //$NON-NLS-1$ //$NON-NLS-2$
|
|
|
362 } else {
|
|
|
363 graph[threadIndex][j]--;
|
|
|
364 }
|
|
|
365 }
|
|
|
366 }
|
|
|
367 //if this thread just released the given lock, try to simplify the graph
|
|
|
368 if (graph[threadIndex][lockIndex] is NO_STATE)
|
|
|
369 reduceGraph(threadIndex, lock);
|
|
|
370 }
|
|
|
371
|
|
|
372 /**
|
|
|
373 * The given scheduling rule is no longer used because the job that invoked it is done.
|
|
|
374 * Release this rule regardless of how many times it was acquired.
|
|
|
375 */
|
|
|
376 void lockReleasedCompletely(Thread owner, ISchedulingRule rule) {
|
|
|
377 int ruleIndex = indexOf(rule, false);
|
|
|
378 int threadIndex = indexOf(owner, false);
|
|
|
379 //need to make sure that the given thread and rule were not already removed from the graph
|
|
|
380 if (threadIndex < 0) {
|
|
|
381 if (JobManager.DEBUG_LOCKS)
|
|
|
382 Stdout.formatln("[lockReleasedCompletely] Lock {} was already released by thread {}", rule, owner.name()); //$NON-NLS-1$ //$NON-NLS-2$
|
|
|
383 return;
|
|
|
384 }
|
|
|
385 if (ruleIndex < 0) {
|
|
|
386 if (JobManager.DEBUG_LOCKS)
|
|
|
387 Stdout.formatln("[lockReleasedCompletely] Thread {} already released lock {}", owner.name(), rule); //$NON-NLS-1$ //$NON-NLS-2$
|
|
|
388 return;
|
|
|
389 }
|
|
|
390 /**
|
|
|
391 * set all rules that are owned by the given thread to NO_STATE
|
|
|
392 * (not just rules that conflict with the rule we are releasing)
|
|
|
393 * if we are releasing a lock, then only update the one entry for the lock
|
|
|
394 */
|
|
|
395 for (int j = 0; j < graph[threadIndex].length; j++) {
|
|
|
396 if (!(cast(ILock)locks.get(j) ) && (graph[threadIndex][j] > NO_STATE))
|
|
|
397 graph[threadIndex][j] = NO_STATE;
|
|
|
398 }
|
|
|
399 reduceGraph(threadIndex, rule);
|
|
|
400 }
|
|
|
401
|
|
|
402 /**
|
|
|
403 * The given thread could not get the given lock and is waiting for it.
|
|
|
404 * Update the graph.
|
|
|
405 */
|
|
|
406 Deadlock lockWaitStart(Thread client, ISchedulingRule lock) {
|
|
|
407 setToWait(client, lock, false);
|
|
|
408 int lockIndex = indexOf(lock, false);
|
|
|
409 int[] temp = new int[lockThreads.size()];
|
|
|
410 //check if the addition of the waiting thread caused deadlock
|
|
|
411 if (!checkWaitCycles(temp, lockIndex))
|
|
|
412 return null;
|
|
|
413 //there is a deadlock in the graph
|
|
|
414 Thread[] threads = getThreadsInDeadlock(client);
|
|
|
415 Thread candidate = resolutionCandidate(threads);
|
|
|
416 ISchedulingRule[] locksToSuspend = realLocksForThread(candidate);
|
|
|
417 Deadlock deadlock = new Deadlock(threads, locksToSuspend, candidate);
|
|
|
418 //find a thread whose locks can be suspended to resolve the deadlock
|
|
|
419 if (JobManager.DEBUG_LOCKS)
|
|
|
420 reportDeadlock(deadlock);
|
|
|
421 if (JobManager.DEBUG_DEADLOCK)
|
|
|
422 throw new IllegalStateException(Format("Deadlock detected. Caused by thread {}.", client.name())); //$NON-NLS-1$
|
|
|
423 // Update the graph to indicate that the locks will now be suspended.
|
|
|
424 // To indicate that the lock will be suspended, we set the thread to wait for the lock.
|
|
|
425 // When the lock is forced to be released, the entry will be cleared.
|
|
|
426 for (int i = 0; i < locksToSuspend.length; i++)
|
|
|
427 setToWait(deadlock.getCandidate(), locksToSuspend[i], true);
|
|
|
428 return deadlock;
|
|
|
429 }
|
|
|
430
|
|
|
431 /**
|
|
|
432 * The given thread has stopped waiting for the given lock.
|
|
|
433 * Update the graph.
|
|
|
434 */
|
|
|
435 void lockWaitStop(Thread owner, ISchedulingRule lock) {
|
|
|
436 int lockIndex = indexOf(lock, false);
|
|
|
437 int threadIndex = indexOf(owner, false);
|
|
|
438 //make sure the thread and lock exist in the graph
|
|
|
439 if (threadIndex < 0) {
|
|
|
440 if (JobManager.DEBUG_LOCKS)
|
|
|
441 Stdout.formatln("Thread {} was already removed.", owner.name() ); //$NON-NLS-1$ //$NON-NLS-2$
|
|
|
442 return;
|
|
|
443 }
|
|
|
444 if (lockIndex < 0) {
|
|
|
445 if (JobManager.DEBUG_LOCKS)
|
|
|
446 Stdout.formatln("Lock {} was already removed.", lock ); //$NON-NLS-1$ //$NON-NLS-2$
|
|
|
447 return;
|
|
|
448 }
|
|
|
449 if (graph[threadIndex][lockIndex] !is WAITING_FOR_LOCK)
|
|
|
450 Assert.isTrue(false, Format("Thread {} was not waiting for lock {} so it could not time out.", owner.name(), (cast(Object)lock).toString())); //$NON-NLS-1$ //$NON-NLS-2$ //$NON-NLS-3$
|
|
|
451 graph[threadIndex][lockIndex] = NO_STATE;
|
|
|
452 reduceGraph(threadIndex, lock);
|
|
|
453 }
|
|
|
454
|
|
|
455 /**
|
|
|
456 * Returns true IFF the given thread owns a single lock
|
|
|
457 */
|
|
|
458 private bool ownsLocks(Thread cause) {
|
|
|
459 int threadIndex = indexOf(cause, false);
|
|
|
460 for (int j = 0; j < graph[threadIndex].length; j++) {
|
|
|
461 if (graph[threadIndex][j] > NO_STATE)
|
|
|
462 return true;
|
|
|
463 }
|
|
|
464 return false;
|
|
|
465 }
|
|
|
466
|
|
|
467 /**
|
|
|
468 * Returns true IFF the given thread owns a single real lock.
|
|
|
469 * A real lock is a lock that can be suspended.
|
|
|
470 */
|
|
|
471 private bool ownsRealLocks(Thread owner) {
|
|
|
472 int threadIndex = indexOf(owner, false);
|
|
|
473 for (int j = 0; j < graph[threadIndex].length; j++) {
|
|
|
474 if (graph[threadIndex][j] > NO_STATE) {
|
|
|
475 Object lock = locks.get(j);
|
|
|
476 if (cast(ILock)lock )
|
|
|
477 return true;
|
|
|
478 }
|
|
|
479 }
|
|
|
480 return false;
|
|
|
481 }
|
|
|
482
|
|
|
483 /**
|
|
|
484 * Return true IFF this thread owns rule locks (i.e. implicit locks which
|
|
|
485 * cannot be suspended)
|
|
|
486 */
|
|
|
487 private bool ownsRuleLocks(Thread owner) {
|
|
|
488 int threadIndex = indexOf(owner, false);
|
|
|
489 for (int j = 0; j < graph[threadIndex].length; j++) {
|
|
|
490 if (graph[threadIndex][j] > NO_STATE) {
|
|
|
491 Object lock = locks.get(j);
|
|
|
492 if (!(cast(ILock)lock ))
|
|
|
493 return true;
|
|
|
494 }
|
|
|
495 }
|
|
|
496 return false;
|
|
|
497 }
|
|
|
498
|
|
|
499 /**
|
|
|
500 * Returns an array of real locks that are owned by the given thread.
|
|
|
501 * Real locks are locks that implement the ILock interface and can be suspended.
|
|
|
502 */
|
|
|
503 private ISchedulingRule[] realLocksForThread(Thread owner) {
|
|
|
504 int threadIndex = indexOf(owner, false);
|
|
|
505 ArrayList ownedLocks = new ArrayList(1);
|
|
|
506 for (int j = 0; j < graph[threadIndex].length; j++) {
|
|
|
507 if ((graph[threadIndex][j] > NO_STATE) && (cast(ILock)locks.get(j) ))
|
|
|
508 ownedLocks.add(locks.get(j));
|
|
|
509 }
|
|
|
510 if (ownedLocks.size() is 0)
|
|
|
511 Assert.isLegal(false, "A thread with no real locks was chosen to resolve deadlock."); //$NON-NLS-1$
|
|
|
512 return arraycast!(ISchedulingRule)( ownedLocks.toArray());
|
|
|
513 }
|
|
|
514
|
|
|
515 /**
|
|
|
516 * The matrix has been simplified. Check if any unnecessary rows or columns
|
|
|
517 * can be removed.
|
|
|
518 */
|
|
|
519 private void reduceGraph(int row, ISchedulingRule lock) {
|
|
|
520 int numLocks = locks.size();
|
|
|
521 bool[] emptyColumns = new bool[numLocks];
|
|
|
522
|
|
|
523 /**
|
|
|
524 * find all columns that could possibly be empty
|
|
|
525 * (consist of locks which conflict with the given lock, or of locks which are rules)
|
|
|
526 */
|
|
|
527 for (int j = 0; j < numLocks; j++) {
|
|
|
528 if ((lock.isConflicting(cast(ISchedulingRule) locks.get(j))) || !(cast(ILock)locks.get(j)))
|
|
|
529 emptyColumns[j] = true;
|
|
|
530 }
|
|
|
531
|
|
|
532 bool rowEmpty = true;
|
|
|
533 int numEmpty = 0;
|
|
|
534 //check if the given row is empty
|
|
|
535 for (int j = 0; j < graph[row].length; j++) {
|
|
|
536 if (graph[row][j] !is NO_STATE) {
|
|
|
537 rowEmpty = false;
|
|
|
538 break;
|
|
|
539 }
|
|
|
540 }
|
|
|
541 /**
|
|
|
542 * Check if the possibly empty columns are actually empty.
|
|
|
543 * If a column is actually empty, remove the corresponding lock from the list of locks
|
|
|
544 * Start at the last column so that when locks are removed from the list,
|
|
|
545 * the index of the remaining locks is unchanged. Store the number of empty columns.
|
|
|
546 */
|
|
|
547 for (int j = emptyColumns.length - 1; j >= 0; j--) {
|
|
|
548 for (int i = 0; i < graph.length; i++) {
|
|
|
549 if (emptyColumns[j] && (graph[i][j] !is NO_STATE)) {
|
|
|
550 emptyColumns[j] = false;
|
|
|
551 break;
|
|
|
552 }
|
|
|
553 }
|
|
|
554 if (emptyColumns[j]) {
|
|
|
555 locks.remove(j);
|
|
|
556 numEmpty++;
|
|
|
557 }
|
|
|
558 }
|
|
|
559 //if no columns or rows are empty, return right away
|
|
|
560 if ((numEmpty is 0) && (!rowEmpty))
|
|
|
561 return;
|
|
|
562
|
|
|
563 if (rowEmpty)
|
|
|
564 lockThreads.remove(row);
|
|
|
565
|
|
|
566 //new graph (the list of locks and the list of threads are already updated)
|
|
|
567 final int numThreads = lockThreads.size();
|
|
|
568 numLocks = locks.size();
|
|
|
569 //optimize empty graph case
|
|
|
570 if (numThreads is 0 && numLocks is 0) {
|
|
|
571 graph = EMPTY_MATRIX;
|
|
|
572 return;
|
|
|
573 }
|
|
|
574 int[][] tempGraph = new int[][](numThreads,numLocks);
|
|
|
575
|
|
|
576 //the number of rows we need to skip to get the correct entry from the old graph
|
|
|
577 int numRowsSkipped = 0;
|
|
|
578 for (int i = 0; i < graph.length - numRowsSkipped; i++) {
|
|
|
579 if ((i is row) && rowEmpty) {
|
|
|
580 numRowsSkipped++;
|
|
|
581 //check if we need to skip the last row
|
|
|
582 if (i >= graph.length - numRowsSkipped)
|
|
|
583 break;
|
|
|
584 }
|
|
|
585 //the number of columns we need to skip to get the correct entry from the old graph
|
|
|
586 //needs to be reset for every new row
|
|
|
587 int numColsSkipped = 0;
|
|
|
588 for (int j = 0; j < graph[i].length - numColsSkipped; j++) {
|
|
|
589 while (emptyColumns[j + numColsSkipped]) {
|
|
|
590 numColsSkipped++;
|
|
|
591 //check if we need to skip the last column
|
|
|
592 if (j >= graph[i].length - numColsSkipped)
|
|
|
593 break;
|
|
|
594 }
|
|
|
595 //need to break out of the outer loop
|
|
|
596 if (j >= graph[i].length - numColsSkipped)
|
|
|
597 break;
|
|
|
598 tempGraph[i][j] = graph[i + numRowsSkipped][j + numColsSkipped];
|
|
|
599 }
|
|
|
600 }
|
|
|
601 graph = tempGraph;
|
|
|
602 Assert.isTrue(numThreads is graph.length, "Rows and threads don't match."); //$NON-NLS-1$
|
|
|
603 Assert.isTrue(numLocks is ((graph.length > 0) ? graph[0].length : 0), "Columns and locks don't match."); //$NON-NLS-1$
|
|
|
604 }
|
|
|
605
|
|
|
606 /**
|
|
|
607 * Adds a 'deadlock detected' message to the log with a stack trace.
|
|
|
608 */
|
|
|
609 private void reportDeadlock(Deadlock deadlock) {
|
|
|
610 String msg = "Deadlock detected. All locks owned by thread " ~ deadlock.getCandidate().name() ~ " will be suspended."; //$NON-NLS-1$ //$NON-NLS-2$
|
|
|
611 MultiStatus main = new MultiStatus(JobManager.PI_JOBS, JobManager.PLUGIN_ERROR, msg, new IllegalStateException());
|
|
|
612 Thread[] threads = deadlock.getThreads();
|
|
|
613 for (int i = 0; i < threads.length; i++) {
|
|
|
614 Object[] ownedLocks = getOwnedLocks(threads[i]);
|
|
|
615 Object waitLock = getWaitingLock(threads[i]);
|
|
|
616 StringBuffer buf = new StringBuffer("Thread "); //$NON-NLS-1$
|
|
|
617 buf.append(threads[i].name());
|
|
|
618 buf.append(" has locks: "); //$NON-NLS-1$
|
|
|
619 for (int j = 0; j < ownedLocks.length; j++) {
|
|
|
620 buf.append(Format("{}",ownedLocks[j]));
|
|
|
621 buf.append((j < ownedLocks.length - 1) ? ", " : " "); //$NON-NLS-1$ //$NON-NLS-2$
|
|
|
622 }
|
|
|
623 buf.append("and is waiting for lock "); //$NON-NLS-1$
|
|
|
624 buf.append(Format("{}",waitLock));
|
|
|
625 Status child = new Status(IStatus.ERROR, JobManager.PI_JOBS, JobManager.PLUGIN_ERROR, buf.toString(), null);
|
|
|
626 main.add(child);
|
|
|
627 }
|
|
|
628 RuntimeLog.log(main);
|
|
|
629 }
|
|
|
630
|
|
|
631 /**
|
|
|
632 * The number of threads/locks in the graph has changed. Update the
|
|
|
633 * underlying matrix.
|
|
|
634 */
|
|
|
635 private void resizeGraph() {
|
|
|
636 // a new row and/or a new column was added to the graph.
|
|
|
637 // since new rows/columns are always added to the end, just transfer
|
|
|
638 // old entries to the new graph, with the same indices.
|
|
|
639 final int newRows = lockThreads.size();
|
|
|
640 final int newCols = locks.size();
|
|
|
641 //optimize 0x0 and 1x1 matrices
|
|
|
642 if (newRows is 0 && newCols is 0) {
|
|
|
643 graph = EMPTY_MATRIX;
|
|
|
644 return;
|
|
|
645 }
|
|
|
646 int[][] tempGraph = new int[][](newRows,newCols);
|
|
|
647 for (int i = 0; i < graph.length; i++)
|
|
|
648 System.arraycopy(graph[i], 0, tempGraph[i], 0, graph[i].length);
|
|
|
649 graph = tempGraph;
|
|
|
650 resize = false;
|
|
|
651 }
|
|
|
652
|
|
|
653 /**
|
|
|
654 * Get the thread whose locks can be suspended. (i.e. all locks it owns are
|
|
|
655 * actual locks and not rules). Return the first thread in the array by default.
|
|
|
656 */
|
|
|
657 private Thread resolutionCandidate(Thread[] candidates) {
|
|
|
658 //first look for a candidate that has no scheduling rules
|
|
|
659 for (int i = 0; i < candidates.length; i++) {
|
|
|
660 if (!ownsRuleLocks(candidates[i]))
|
|
|
661 return candidates[i];
|
|
|
662 }
|
|
|
663 //next look for any candidate with a real lock (a lock that can be suspended)
|
|
|
664 for (int i = 0; i < candidates.length; i++) {
|
|
|
665 if (ownsRealLocks(candidates[i]))
|
|
|
666 return candidates[i];
|
|
|
667 }
|
|
|
668 //unnecessary, return the first entry in the array by default
|
|
|
669 return candidates[0];
|
|
|
670 }
|
|
|
671
|
|
|
672 /**
|
|
|
673 * The given thread is waiting for the given lock. Update the graph.
|
|
|
674 */
|
|
|
675 private void setToWait(Thread owner, ISchedulingRule lock, bool suspend) {
|
|
|
676 bool needTransfer = false;
|
|
|
677 /**
|
|
|
678 * if we are adding an entry where a thread is waiting on a scheduling rule,
|
|
|
679 * then we need to transfer all positive entries for a conflicting rule to the
|
|
|
680 * newly added rule in order to synchronize the graph.
|
|
|
681 */
|
|
|
682 if (!suspend && !(cast(ILock)lock))
|
|
|
683 needTransfer = true;
|
|
|
684 int lockIndex = indexOf(lock, !suspend);
|
|
|
685 int threadIndex = indexOf(owner, !suspend);
|
|
|
686 if (resize)
|
|
|
687 resizeGraph();
|
|
|
688
|
|
|
689 graph[threadIndex][lockIndex] = WAITING_FOR_LOCK;
|
|
|
690 if (needTransfer)
|
|
|
691 fillPresentEntries(lock, lockIndex);
|
|
|
692 }
|
|
|
693
|
|
|
694 /**
|
|
|
695 * Prints out the current matrix to standard output.
|
|
|
696 * Only used for debugging.
|
|
|
697 */
|
|
|
698 public String toDebugString() {
|
|
|
699 StringBuffer sb = new StringBuffer();
|
|
|
700 sb.append(" :: \n"); //$NON-NLS-1$
|
|
|
701 for (int j = 0; j < locks.size(); j++) {
|
|
|
702 sb.append(" ");
|
|
|
703 sb.append( locks.get(j).toString );
|
|
|
704 sb.append(",");
|
|
|
705 }
|
|
|
706 sb.append("\n");
|
|
|
707 for (int i = 0; i < graph.length; i++) {
|
|
|
708 sb.append(" ");
|
|
|
709 sb.append( (cast(Thread) lockThreads.get(i)).name() );
|
|
|
710 sb.append(" : ");
|
|
|
711 for (int j = 0; j < graph[i].length; j++) {
|
|
|
712 sb.append(" ");
|
|
|
713 sb.append(Integer.toString(graph[i][j])); //$NON-NLS-1$
|
|
|
714 sb.append(",");
|
|
|
715 }
|
|
|
716 sb.append("\n");
|
|
|
717 }
|
|
|
718 sb.append("-------\n"); //$NON-NLS-1$
|
|
|
719 return sb.toString();
|
|
|
720 }
|
|
|
721 }
|
