Mercurial > projects > dwt2

comparison org.eclipse.core.jobs/src/org/eclipse/core/internal/jobs/DeadlockDetector.d @ 12:bc29606a740c

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