projects/dwt2: org.eclipse.core.jobs/src/org/eclipse/core/internal/jobs/DeadlockDetector.d annotate

author	Frank Benoit <benoit@tionex.de>
date	Sat, 14 Mar 2009 18:23:29 +0100
parents
children	6f068362a363

rev	line source
12 bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	1 /*******************************************************************************
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	2 * Copyright (c) 2003, 2006 IBM Corporation and others.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	3 * All rights reserved. This program and the accompanying materials
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	4 * are made available under the terms of the Eclipse Public License v1.0
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	5 * which accompanies this distribution, and is available at
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	6 * http://www.eclipse.org/legal/epl-v10.html
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	7 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	8 * Contributors:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	9 * IBM Corporation - initial API and implementation
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	10 * Port to the D programming language:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	11 * Frank Benoit <benoit@tionex.de>
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	12 *******************************************************************************/
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	13 module org.eclipse.core.internal.jobs.DeadlockDetector;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	14
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	15 import java.lang.JThread;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	16 import tango.io.Stdout;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	17 import tango.text.convert.Format;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	18
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	19 import java.lang.all;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	20 import java.util.ArrayList;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	21 import java.util.Set;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	22
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	23 import org.eclipse.core.internal.runtime.RuntimeLog;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	24 import org.eclipse.core.runtime.Assert;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	25 import org.eclipse.core.runtime.IStatus;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	26 import org.eclipse.core.runtime.MultiStatus;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	27 import org.eclipse.core.runtime.Status;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	28 import org.eclipse.core.runtime.jobs.ILock;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	29 import org.eclipse.core.runtime.jobs.ISchedulingRule;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	30 import org.eclipse.core.internal.jobs.Deadlock;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	31 import org.eclipse.core.internal.jobs.JobManager;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	32
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	33 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	34 * Stores all the relationships between locks (rules are also considered locks),
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	35 * and the threads that own them. All the relationships are stored in a 2D integer array.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	36 * The rows in the array are threads, while the columns are locks.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	37 * Two corresponding arrayLists store the actual threads and locks.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	38 * The index of a thread in the first arrayList is the index of the row in the graph.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	39 * The index of a lock in the second arrayList is the index of the column in the graph.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	40 * An entry greater than 0 in the graph is the number of times a thread in the entry's row
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	41 * acquired the lock in the entry's column.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	42 * An entry of -1 means that the thread is waiting to acquire the lock.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	43 * An entry of 0 means that the thread and the lock have no relationship.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	44 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	45 * The difference between rules and locks is that locks can be suspended, while
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	46 * rules are implicit locks and as such cannot be suspended.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	47 * To resolve deadlock, the graph will first try to find a thread that only owns
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	48 * locks. Failing that, it will find a thread in the deadlock that owns at least
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	49 * one lock and suspend it.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	50 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	51 * Deadlock can only occur among locks, or among locks in combination with rules.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	52 * Deadlock among rules only is impossible. Therefore, in any deadlock one can always
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	53 * find a thread that owns at least one lock that can be suspended.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	54 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	55 * The implementation of the graph assumes that a thread can only own 1 rule at
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	56 * any one time. It can acquire that rule several times, but a thread cannot
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	57 * acquire 2 non-conflicting rules at the same time.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	58 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	59 * The implementation of the graph will sometimes also find and resolve bogus deadlocks.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	60 * graph: assuming this rule hierarchy:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	61 * R2 R3 L1 R1
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	62 * J1 1 0 0 / \
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	63 * J2 0 1 -1 R2 R3
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	64 * J3 -1 0 1
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	65 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	66 * If in the above situation job4 decides to acquire rule1, then the graph will transform
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	67 * to the following:
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	68 * R2 R3 R1 L1
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	69 * J1 1 0 1 0
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	70 * J2 1 1 1 -1
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	71 * J3 -1 0 0 1
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	72 * J4 0 0 -1 0
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	73 *
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	74 * and the graph will assume that job2 and job3 are deadlocked and suspend lock1 of job3.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	75 * The reason the deadlock is bogus is that the deadlock is unlikely to actually happen (the threads
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	76 * are currently not deadlocked, but might deadlock later on when it is too late to detect it)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	77 * Therefore, in order to make sure that no deadlock is possible,
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	78 * the deadlock will still be resolved at this point.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	79 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	80 class DeadlockDetector {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	81 private static int NO_STATE = 0;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	82 //state variables in the graph
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	83 private static int WAITING_FOR_LOCK = -1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	84 //empty matrix
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	85 private static const int[][] EMPTY_MATRIX = null;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	86 //matrix of relationships between threads and locks
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	87 private int[][] graph = EMPTY_MATRIX;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	88 //index is column in adjacency matrix for the lock
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	89 private final ArrayList locks;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	90 //index is row in adjacency matrix for the thread
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	91 private final ArrayList lockThreads;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	92 //whether the graph needs to be resized
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	93 private bool resize = false;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	94
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	95 public this(){
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	96 locks = new ArrayList();
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	97 lockThreads = new ArrayList();
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	98 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	99
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	100 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	101 * Recursively check if any of the threads that prevent the current thread from running
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	102 * are actually deadlocked with the current thread.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	103 * Add the threads that form deadlock to the deadlockedThreads list.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	104 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	105 private bool addCycleThreads(ArrayList deadlockedThreads, JThread next) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	106 //get the thread that block the given thread from running
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	107 JThread[] blocking = blockingThreads(next);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	108 //if the thread is not blocked by other threads, then it is not part of a deadlock
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	109 if (blocking.length is 0)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	110 return false;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	111 bool inCycle = false;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	112 for (int i = 0; i < blocking.length; i++) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	113 //if we have already visited the given thread, then we found a cycle
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	114 if (deadlockedThreads.contains(blocking[i])) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	115 inCycle = true;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	116 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	117 //otherwise, add the thread to our list and recurse deeper
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	118 deadlockedThreads.add(blocking[i]);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	119 //if the thread is not part of a cycle, remove it from the list
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	120 if (addCycleThreads(deadlockedThreads, blocking[i]))
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	121 inCycle = true;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	122 else
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	123 deadlockedThreads.remove(blocking[i]);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	124 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	125 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	126 return inCycle;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	127 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	128
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	129 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	130 * Get the thread(s) that own the lock this thread is waiting for.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	131 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	132 private JThread[] blockingThreads(JThread current) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	133 //find the lock this thread is waiting for
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	134 ISchedulingRule lock = cast(ISchedulingRule) getWaitingLock(current);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	135 return getThreadsOwningLock(lock);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	136 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	137
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	138 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	139 * Check that the addition of a waiting thread did not produce deadlock.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	140 * If deadlock is detected return true, else return false.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	141 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	142 private bool checkWaitCycles(int[] waitingThreads, int lockIndex) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	143 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	144 * find the lock that this thread is waiting for
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	145 * recursively check if this is a cycle (i.e. a thread waiting on itself)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	146 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	147 for (int i = 0; i < graph.length; i++) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	148 if (graph[i][lockIndex] > NO_STATE) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	149 if (waitingThreads[i] > NO_STATE) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	150 return true;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	151 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	152 //keep track that we already visited this thread
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	153 waitingThreads[i]++;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	154 for (int j = 0; j < graph[i].length; j++) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	155 if (graph[i][j] is WAITING_FOR_LOCK) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	156 if (checkWaitCycles(waitingThreads, j))
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	157 return true;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	158 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	159 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	160 //this thread is not involved in a cycle yet, so remove the visited flag
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	161 waitingThreads[i]--;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	162 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	163 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	164 return false;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	165 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	166
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	167 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	168 * Returns true IFF the matrix contains a row for the given thread.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	169 * (meaning the given thread either owns locks or is waiting for locks)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	170 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	171 bool contains(JThread t) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	172 return lockThreads.contains(t);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	173 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	174
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	175 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	176 * A new rule was just added to the graph.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	177 * Find a rule it conflicts with and update the new rule with the number of times
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	178 * it was acquired implicitly when threads acquired conflicting rule.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	179 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	180 private void fillPresentEntries(ISchedulingRule newLock, int lockIndex) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	181 //fill in the entries for the new rule from rules it conflicts with
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	182 for (int j = 0; j < locks.size(); j++) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	183 if ((j !is lockIndex) && (newLock.isConflicting(cast(ISchedulingRule) locks.get(j)))) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	184 for (int i = 0; i < graph.length; i++) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	185 if ((graph[i][j] > NO_STATE) && (graph[i][lockIndex] is NO_STATE))
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	186 graph[i][lockIndex] = graph[i][j];
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	187 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	188 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	189 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	190 //now back fill the entries for rules the current rule conflicts with
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	191 for (int j = 0; j < locks.size(); j++) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	192 if ((j !is lockIndex) && (newLock.isConflicting(cast(ISchedulingRule) locks.get(j)))) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	193 for (int i = 0; i < graph.length; i++) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	194 if ((graph[i][lockIndex] > NO_STATE) && (graph[i][j] is NO_STATE))
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	195 graph[i][j] = graph[i][lockIndex];
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	196 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	197 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	198 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	199 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	200
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	201 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	202 * Returns all the locks owned by the given thread
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	203 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	204 private Object[] getOwnedLocks(JThread current) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	205 ArrayList ownedLocks = new ArrayList(1);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	206 int index = indexOf(current, false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	207
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	208 for (int j = 0; j < graph[index].length; j++) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	209 if (graph[index][j] > NO_STATE)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	210 ownedLocks.add(locks.get(j));
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	211 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	212 if (ownedLocks.size() is 0)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	213 Assert.isLegal(false, "A thread with no locks is part of a deadlock."); //$NON-NLS-1$
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	214 return ownedLocks.toArray();
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	215 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	216
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	217 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	218 * Returns an array of threads that form the deadlock (usually 2).
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	219 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	220 private JThread[] getThreadsInDeadlock(JThread cause) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	221 ArrayList deadlockedThreads = new ArrayList(2);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	222 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	223 * if the thread that caused deadlock doesn't own any locks, then it is not part
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	224 * of the deadlock (it just caused it because of a rule it tried to acquire)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	225 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	226 if (ownsLocks(cause))
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	227 deadlockedThreads.add(cause);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	228 addCycleThreads(deadlockedThreads, cause);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	229 return arraycast!(JThread)( deadlockedThreads.toArray());
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	230 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	231
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	232 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	233 * Returns the thread(s) that own the given lock.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	234 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	235 private JThread[] getThreadsOwningLock(ISchedulingRule rule) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	236 if (rule is null)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	237 return new JThread[0];
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	238 int lockIndex = indexOf(rule, false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	239 ArrayList blocking = new ArrayList(1);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	240 for (int i = 0; i < graph.length; i++) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	241 if (graph[i][lockIndex] > NO_STATE)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	242 blocking.add(lockThreads.get(i));
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	243 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	244 if ((blocking.size() is 0) && (JobManager.DEBUG_LOCKS))
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	245 Stdout.formatln(Format("Lock {} is involved in deadlock but is not owned by any thread.", rule )); //$NON-NLS-1$ //$NON-NLS-2$
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	246 if ((blocking.size() > 1) && (cast(ILock)rule ) && (JobManager.DEBUG_LOCKS))
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	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$
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	248 return arraycast!(JThread)( blocking.toArray());
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	249 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	250
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	251 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	252 * Returns the lock the given thread is waiting for.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	253 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	254 private Object getWaitingLock(JThread current) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	255 int index = indexOf(current, false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	256 //find the lock that this thread is waiting for
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	257 for (int j = 0; j < graph[index].length; j++) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	258 if (graph[index][j] is WAITING_FOR_LOCK)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	259 return locks.get(j);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	260 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	261 //it can happen that a thread is not waiting for any lock (it is not really part of the deadlock)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	262 return null;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	263 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	264
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	265 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	266 * Returns the index of the given lock in the lock array. If the lock is
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	267 * not present in the array, it is added to the end.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	268 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	269 private int indexOf(ISchedulingRule lock, bool add) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	270 int index = locks.indexOf(cast(Object)lock);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	271 if ((index < 0) && add) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	272 locks.add(cast(Object)lock);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	273 resize = true;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	274 index = locks.size() - 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	275 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	276 return index;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	277 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	278
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	279 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	280 * Returns the index of the given thread in the thread array. If the thread
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	281 * is not present in the array, it is added to the end.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	282 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	283 private int indexOf(JThread owner, bool add) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	284 int index = lockThreads.indexOf(owner);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	285 if ((index < 0) && add) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	286 lockThreads.add(owner);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	287 resize = true;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	288 index = lockThreads.size() - 1;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	289 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	290 return index;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	291 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	292
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	293 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	294 * Returns true IFF the adjacency matrix is empty.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	295 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	296 bool isEmpty() {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	297 return (locks.size() is 0) && (lockThreads.size() is 0) && (graph.length is 0);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	298 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	299
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	300 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	301 * The given lock was acquired by the given thread.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	302 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	303 void lockAcquired(JThread owner, ISchedulingRule lock) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	304 int lockIndex = indexOf(lock, true);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	305 int threadIndex = indexOf(owner, true);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	306 if (resize)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	307 resizeGraph();
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	308 if (graph[threadIndex][lockIndex] is WAITING_FOR_LOCK)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	309 graph[threadIndex][lockIndex] = NO_STATE;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	310 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	311 * acquire all locks that conflict with the given lock
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	312 * or conflict with a lock the given lock will acquire implicitly
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	313 * (locks are acquired implicitly when a conflicting lock is acquired)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	314 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	315 ArrayList conflicting = new ArrayList(1);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	316 //only need two passes through all the locks to pick up all conflicting rules
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	317 int NUM_PASSES = 2;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	318 conflicting.add(cast(Object)lock);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	319 graph[threadIndex][lockIndex]++;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	320 for (int i = 0; i < NUM_PASSES; i++) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	321 for (int k = 0; k < conflicting.size(); k++) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	322 ISchedulingRule current = cast(ISchedulingRule) conflicting.get(k);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	323 for (int j = 0; j < locks.size(); j++) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	324 ISchedulingRule possible = cast(ISchedulingRule) locks.get(j);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	325 if (current.isConflicting(possible) && !conflicting.contains(cast(Object)possible)) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	326 conflicting.add(cast(Object)possible);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	327 graph[threadIndex][j]++;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	328 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	329 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	330 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	331 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	332 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	333
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	334 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	335 * The given lock was released by the given thread. Update the graph.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	336 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	337 void lockReleased(JThread owner, ISchedulingRule lock) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	338 int lockIndex = indexOf(lock, false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	339 int threadIndex = indexOf(owner, false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	340 //make sure the lock and thread exist in the graph
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	341 if (threadIndex < 0) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	342 if (JobManager.DEBUG_LOCKS)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	343 Stdout.formatln("[lockReleased] Lock {} was already released by thread {}", lock, owner.getName()); //$NON-NLS-1$ //$NON-NLS-2$
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	344 return;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	345 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	346 if (lockIndex < 0) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	347 if (JobManager.DEBUG_LOCKS)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	348 Stdout.formatln("[lockReleased] Thread {} already released lock {}", owner.getName(), lock); //$NON-NLS-1$ //$NON-NLS-2$
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	349 return;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	350 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	351 //if this lock was suspended, set it to NO_STATE
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	352 if ((cast(ILock)lock ) && (graph[threadIndex][lockIndex] is WAITING_FOR_LOCK)) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	353 graph[threadIndex][lockIndex] = NO_STATE;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	354 return;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	355 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	356 //release all locks that conflict with the given lock
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	357 //or release all rules that are owned by the given thread, if we are releasing a rule
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	358 for (int j = 0; j < graph[threadIndex].length; j++) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	359 if ((lock.isConflicting(cast(ISchedulingRule) locks.get(j))) \|\| (!(cast(ILock)lock ) && !(cast(ILock)locks.get(j)) && (graph[threadIndex][j] > NO_STATE))) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	360 if (graph[threadIndex][j] is NO_STATE) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	361 if (JobManager.DEBUG_LOCKS)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	362 Stdout.formatln("[lockReleased] More releases than acquires for thread {} and lock {}", owner.getName(), lock); //$NON-NLS-1$ //$NON-NLS-2$
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	363 } else {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	364 graph[threadIndex][j]--;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	365 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	366 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	367 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	368 //if this thread just released the given lock, try to simplify the graph
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	369 if (graph[threadIndex][lockIndex] is NO_STATE)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	370 reduceGraph(threadIndex, lock);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	371 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	372
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	373 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	374 * The given scheduling rule is no longer used because the job that invoked it is done.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	375 * Release this rule regardless of how many times it was acquired.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	376 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	377 void lockReleasedCompletely(JThread owner, ISchedulingRule rule) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	378 int ruleIndex = indexOf(rule, false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	379 int threadIndex = indexOf(owner, false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	380 //need to make sure that the given thread and rule were not already removed from the graph
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	381 if (threadIndex < 0) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	382 if (JobManager.DEBUG_LOCKS)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	383 Stdout.formatln("[lockReleasedCompletely] Lock {} was already released by thread {}", rule, owner.getName()); //$NON-NLS-1$ //$NON-NLS-2$
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	384 return;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	385 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	386 if (ruleIndex < 0) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	387 if (JobManager.DEBUG_LOCKS)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	388 Stdout.formatln("[lockReleasedCompletely] Thread {} already released lock {}", owner.getName(), rule); //$NON-NLS-1$ //$NON-NLS-2$
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	389 return;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	390 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	391 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	392 * set all rules that are owned by the given thread to NO_STATE
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	393 * (not just rules that conflict with the rule we are releasing)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	394 * if we are releasing a lock, then only update the one entry for the lock
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	395 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	396 for (int j = 0; j < graph[threadIndex].length; j++) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	397 if (!(cast(ILock)locks.get(j) ) && (graph[threadIndex][j] > NO_STATE))
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	398 graph[threadIndex][j] = NO_STATE;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	399 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	400 reduceGraph(threadIndex, rule);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	401 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	402
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	403 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	404 * The given thread could not get the given lock and is waiting for it.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	405 * Update the graph.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	406 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	407 Deadlock lockWaitStart(JThread client, ISchedulingRule lock) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	408 setToWait(client, lock, false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	409 int lockIndex = indexOf(lock, false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	410 int[] temp = new int[lockThreads.size()];
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	411 //check if the addition of the waiting thread caused deadlock
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	412 if (!checkWaitCycles(temp, lockIndex))
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	413 return null;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	414 //there is a deadlock in the graph
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	415 JThread[] threads = getThreadsInDeadlock(client);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	416 JThread candidate = resolutionCandidate(threads);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	417 ISchedulingRule[] locksToSuspend = realLocksForThread(candidate);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	418 Deadlock deadlock = new Deadlock(threads, locksToSuspend, candidate);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	419 //find a thread whose locks can be suspended to resolve the deadlock
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	420 if (JobManager.DEBUG_LOCKS)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	421 reportDeadlock(deadlock);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	422 if (JobManager.DEBUG_DEADLOCK)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	423 throw new IllegalStateException(Format("Deadlock detected. Caused by thread {}.", client.getName())); //$NON-NLS-1$
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	424 // Update the graph to indicate that the locks will now be suspended.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	425 // To indicate that the lock will be suspended, we set the thread to wait for the lock.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	426 // When the lock is forced to be released, the entry will be cleared.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	427 for (int i = 0; i < locksToSuspend.length; i++)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	428 setToWait(deadlock.getCandidate(), locksToSuspend[i], true);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	429 return deadlock;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	430 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	431
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	432 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	433 * The given thread has stopped waiting for the given lock.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	434 * Update the graph.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	435 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	436 void lockWaitStop(JThread owner, ISchedulingRule lock) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	437 int lockIndex = indexOf(lock, false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	438 int threadIndex = indexOf(owner, false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	439 //make sure the thread and lock exist in the graph
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	440 if (threadIndex < 0) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	441 if (JobManager.DEBUG_LOCKS)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	442 Stdout.formatln("Thread {} was already removed.", owner.getName() ); //$NON-NLS-1$ //$NON-NLS-2$
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	443 return;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	444 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	445 if (lockIndex < 0) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	446 if (JobManager.DEBUG_LOCKS)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	447 Stdout.formatln("Lock {} was already removed.", lock ); //$NON-NLS-1$ //$NON-NLS-2$
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	448 return;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	449 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	450 if (graph[threadIndex][lockIndex] !is WAITING_FOR_LOCK)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	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$
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	452 graph[threadIndex][lockIndex] = NO_STATE;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	453 reduceGraph(threadIndex, lock);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	454 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	455
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	456 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	457 * Returns true IFF the given thread owns a single lock
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	458 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	459 private bool ownsLocks(JThread cause) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	460 int threadIndex = indexOf(cause, false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	461 for (int j = 0; j < graph[threadIndex].length; j++) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	462 if (graph[threadIndex][j] > NO_STATE)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	463 return true;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	464 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	465 return false;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	466 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	467
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	468 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	469 * Returns true IFF the given thread owns a single real lock.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	470 * A real lock is a lock that can be suspended.
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	471 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	472 private bool ownsRealLocks(JThread owner) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	473 int threadIndex = indexOf(owner, false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	474 for (int j = 0; j < graph[threadIndex].length; j++) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	475 if (graph[threadIndex][j] > NO_STATE) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	476 Object lock = locks.get(j);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	477 if (cast(ILock)lock )
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	478 return true;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	479 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	480 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	481 return false;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	482 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	483
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	484 /**
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	485 * Return true IFF this thread owns rule locks (i.e. implicit locks which
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	486 * cannot be suspended)
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	487 */
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	488 private bool ownsRuleLocks(JThread owner) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	489 int threadIndex = indexOf(owner, false);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	490 for (int j = 0; j < graph[threadIndex].length; j++) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	491 if (graph[threadIndex][j] > NO_STATE) {
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	492 Object lock = locks.get(j);
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	493 if (!(cast(ILock)lock ))
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	494 return true;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	495 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	496 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	497 return false;
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	498 }
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	499
bc29606a740c Added dwt-addons in original directory structure of eclipse.org Frank Benoit <benoit@tionex.de> parents: diff changeset	500 /**

12

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

1 /*******************************************************************************

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

4 * are made available under the terms of the Eclipse Public License v1.0

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

5 * which accompanies this distribution, and is available at

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

6 * http://www.eclipse.org/legal/epl-v10.html

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

7 *

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

8 * Contributors:

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

9 * IBM Corporation - initial API and implementation

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

10 * Port to the D programming language:

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

11 * Frank Benoit <benoit@tionex.de>

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

12 *******************************************************************************/

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

13 module org.eclipse.core.internal.jobs.DeadlockDetector;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

14

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

15 import java.lang.JThread;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

16 import tango.io.Stdout;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

17 import tango.text.convert.Format;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

18

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

19 import java.lang.all;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

20 import java.util.ArrayList;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

21 import java.util.Set;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

22

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

23 import org.eclipse.core.internal.runtime.RuntimeLog;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

24 import org.eclipse.core.runtime.Assert;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

25 import org.eclipse.core.runtime.IStatus;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

26 import org.eclipse.core.runtime.MultiStatus;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

27 import org.eclipse.core.runtime.Status;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

28 import org.eclipse.core.runtime.jobs.ILock;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

29 import org.eclipse.core.runtime.jobs.ISchedulingRule;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

30 import org.eclipse.core.internal.jobs.Deadlock;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

31 import org.eclipse.core.internal.jobs.JobManager;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

32

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

33 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

34 * Stores all the relationships between locks (rules are also considered locks),

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

35 * and the threads that own them. All the relationships are stored in a 2D integer array.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

36 * The rows in the array are threads, while the columns are locks.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

37 * Two corresponding arrayLists store the actual threads and locks.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

38 * The index of a thread in the first arrayList is the index of the row in the graph.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

39 * The index of a lock in the second arrayList is the index of the column in the graph.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

40 * An entry greater than 0 in the graph is the number of times a thread in the entry's row

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

41 * acquired the lock in the entry's column.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

42 * An entry of -1 means that the thread is waiting to acquire the lock.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

43 * An entry of 0 means that the thread and the lock have no relationship.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

44 *

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

45 * The difference between rules and locks is that locks can be suspended, while

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

46 * rules are implicit locks and as such cannot be suspended.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

47 * To resolve deadlock, the graph will first try to find a thread that only owns

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

48 * locks. Failing that, it will find a thread in the deadlock that owns at least

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

49 * one lock and suspend it.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

50 *

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

51 * Deadlock can only occur among locks, or among locks in combination with rules.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

52 * Deadlock among rules only is impossible. Therefore, in any deadlock one can always

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

53 * find a thread that owns at least one lock that can be suspended.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

54 *

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

55 * The implementation of the graph assumes that a thread can only own 1 rule at

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

56 * any one time. It can acquire that rule several times, but a thread cannot

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

57 * acquire 2 non-conflicting rules at the same time.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

58 *

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

59 * The implementation of the graph will sometimes also find and resolve bogus deadlocks.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

60 * graph: assuming this rule hierarchy:

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

61 * R2 R3 L1 R1

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

62 * J1 1 0 0 / \

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

63 * J2 0 1 -1 R2 R3

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

64 * J3 -1 0 1

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

65 *

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

66 * If in the above situation job4 decides to acquire rule1, then the graph will transform

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

67 * to the following:

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

68 * R2 R3 R1 L1

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

69 * J1 1 0 1 0

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

70 * J2 1 1 1 -1

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

71 * J3 -1 0 0 1

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

72 * J4 0 0 -1 0

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

73 *

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

74 * and the graph will assume that job2 and job3 are deadlocked and suspend lock1 of job3.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

75 * The reason the deadlock is bogus is that the deadlock is unlikely to actually happen (the threads

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

76 * are currently not deadlocked, but might deadlock later on when it is too late to detect it)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

77 * Therefore, in order to make sure that no deadlock is possible,

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

78 * the deadlock will still be resolved at this point.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

79 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

80 class DeadlockDetector {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

81 private static int NO_STATE = 0;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

82 //state variables in the graph

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

83 private static int WAITING_FOR_LOCK = -1;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

84 //empty matrix

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

85 private static const int[][] EMPTY_MATRIX = null;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

86 //matrix of relationships between threads and locks

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

87 private int[][] graph = EMPTY_MATRIX;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

88 //index is column in adjacency matrix for the lock

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

89 private final ArrayList locks;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

90 //index is row in adjacency matrix for the thread

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

91 private final ArrayList lockThreads;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

92 //whether the graph needs to be resized

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

93 private bool resize = false;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

94

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

95 public this(){

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

96 locks = new ArrayList();

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

97 lockThreads = new ArrayList();

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

98 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

99

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

100 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

101 * Recursively check if any of the threads that prevent the current thread from running

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

102 * are actually deadlocked with the current thread.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

103 * Add the threads that form deadlock to the deadlockedThreads list.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

104 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

105 private bool addCycleThreads(ArrayList deadlockedThreads, JThread next) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

106 //get the thread that block the given thread from running

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

107 JThread[] blocking = blockingThreads(next);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

108 //if the thread is not blocked by other threads, then it is not part of a deadlock

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

109 if (blocking.length is 0)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

110 return false;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

111 bool inCycle = false;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

112 for (int i = 0; i < blocking.length; i++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

113 //if we have already visited the given thread, then we found a cycle

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

114 if (deadlockedThreads.contains(blocking[i])) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

115 inCycle = true;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

116 } else {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

117 //otherwise, add the thread to our list and recurse deeper

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

118 deadlockedThreads.add(blocking[i]);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

119 //if the thread is not part of a cycle, remove it from the list

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

120 if (addCycleThreads(deadlockedThreads, blocking[i]))

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

121 inCycle = true;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

122 else

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

123 deadlockedThreads.remove(blocking[i]);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

124 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

125 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

126 return inCycle;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

127 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

128

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

129 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

130 * Get the thread(s) that own the lock this thread is waiting for.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

131 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

132 private JThread[] blockingThreads(JThread current) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

133 //find the lock this thread is waiting for

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

134 ISchedulingRule lock = cast(ISchedulingRule) getWaitingLock(current);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

135 return getThreadsOwningLock(lock);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

136 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

137

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

138 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

139 * Check that the addition of a waiting thread did not produce deadlock.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

140 * If deadlock is detected return true, else return false.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

141 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

142 private bool checkWaitCycles(int[] waitingThreads, int lockIndex) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

143 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

144 * find the lock that this thread is waiting for

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

145 * recursively check if this is a cycle (i.e. a thread waiting on itself)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

146 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

147 for (int i = 0; i < graph.length; i++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

148 if (graph[i][lockIndex] > NO_STATE) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

149 if (waitingThreads[i] > NO_STATE) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

150 return true;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

151 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

152 //keep track that we already visited this thread

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

153 waitingThreads[i]++;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

154 for (int j = 0; j < graph[i].length; j++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

155 if (graph[i][j] is WAITING_FOR_LOCK) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

156 if (checkWaitCycles(waitingThreads, j))

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

157 return true;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

158 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

159 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

160 //this thread is not involved in a cycle yet, so remove the visited flag

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

161 waitingThreads[i]--;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

162 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

163 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

164 return false;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

165 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

166

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

167 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

168 * Returns true IFF the matrix contains a row for the given thread.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

169 * (meaning the given thread either owns locks or is waiting for locks)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

170 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

171 bool contains(JThread t) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

172 return lockThreads.contains(t);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

173 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

174

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

175 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

176 * A new rule was just added to the graph.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

177 * Find a rule it conflicts with and update the new rule with the number of times

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

178 * it was acquired implicitly when threads acquired conflicting rule.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

179 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

180 private void fillPresentEntries(ISchedulingRule newLock, int lockIndex) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

181 //fill in the entries for the new rule from rules it conflicts with

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

182 for (int j = 0; j < locks.size(); j++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

183 if ((j !is lockIndex) && (newLock.isConflicting(cast(ISchedulingRule) locks.get(j)))) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

184 for (int i = 0; i < graph.length; i++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

185 if ((graph[i][j] > NO_STATE) && (graph[i][lockIndex] is NO_STATE))

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

186 graph[i][lockIndex] = graph[i][j];

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

187 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

188 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

189 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

190 //now back fill the entries for rules the current rule conflicts with

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

191 for (int j = 0; j < locks.size(); j++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

192 if ((j !is lockIndex) && (newLock.isConflicting(cast(ISchedulingRule) locks.get(j)))) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

193 for (int i = 0; i < graph.length; i++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

194 if ((graph[i][lockIndex] > NO_STATE) && (graph[i][j] is NO_STATE))

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

195 graph[i][j] = graph[i][lockIndex];

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

196 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

197 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

198 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

199 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

200

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

201 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

202 * Returns all the locks owned by the given thread

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

203 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

204 private Object[] getOwnedLocks(JThread current) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

205 ArrayList ownedLocks = new ArrayList(1);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

206 int index = indexOf(current, false);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

207

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

208 for (int j = 0; j < graph[index].length; j++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

209 if (graph[index][j] > NO_STATE)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

210 ownedLocks.add(locks.get(j));

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

211 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

212 if (ownedLocks.size() is 0)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

213 Assert.isLegal(false, "A thread with no locks is part of a deadlock."); //$NON-NLS-1$

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

214 return ownedLocks.toArray();

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

215 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

216

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

217 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

218 * Returns an array of threads that form the deadlock (usually 2).

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

219 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

220 private JThread[] getThreadsInDeadlock(JThread cause) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

221 ArrayList deadlockedThreads = new ArrayList(2);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

222 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

223 * if the thread that caused deadlock doesn't own any locks, then it is not part

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

224 * of the deadlock (it just caused it because of a rule it tried to acquire)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

225 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

226 if (ownsLocks(cause))

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

227 deadlockedThreads.add(cause);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

228 addCycleThreads(deadlockedThreads, cause);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

229 return arraycast!(JThread)( deadlockedThreads.toArray());

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

230 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

231

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

232 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

233 * Returns the thread(s) that own the given lock.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

234 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

235 private JThread[] getThreadsOwningLock(ISchedulingRule rule) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

236 if (rule is null)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

237 return new JThread[0];

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

238 int lockIndex = indexOf(rule, false);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

239 ArrayList blocking = new ArrayList(1);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

240 for (int i = 0; i < graph.length; i++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

241 if (graph[i][lockIndex] > NO_STATE)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

242 blocking.add(lockThreads.get(i));

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

243 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

244 if ((blocking.size() is 0) && (JobManager.DEBUG_LOCKS))

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

245 Stdout.formatln(Format("Lock {} is involved in deadlock but is not owned by any thread.", rule )); //$NON-NLS-1$ //$NON-NLS-2$

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

246 if ((blocking.size() > 1) && (cast(ILock)rule ) && (JobManager.DEBUG_LOCKS))

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

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$

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

248 return arraycast!(JThread)( blocking.toArray());

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

249 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

250

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

251 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

252 * Returns the lock the given thread is waiting for.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

253 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

254 private Object getWaitingLock(JThread current) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

255 int index = indexOf(current, false);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

256 //find the lock that this thread is waiting for

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

257 for (int j = 0; j < graph[index].length; j++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

258 if (graph[index][j] is WAITING_FOR_LOCK)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

259 return locks.get(j);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

260 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

261 //it can happen that a thread is not waiting for any lock (it is not really part of the deadlock)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

262 return null;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

263 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

264

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

265 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

266 * Returns the index of the given lock in the lock array. If the lock is

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

267 * not present in the array, it is added to the end.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

268 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

269 private int indexOf(ISchedulingRule lock, bool add) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

270 int index = locks.indexOf(cast(Object)lock);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

271 if ((index < 0) && add) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

272 locks.add(cast(Object)lock);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

273 resize = true;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

274 index = locks.size() - 1;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

275 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

276 return index;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

277 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

278

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

279 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

280 * Returns the index of the given thread in the thread array. If the thread

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

281 * is not present in the array, it is added to the end.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

282 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

283 private int indexOf(JThread owner, bool add) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

284 int index = lockThreads.indexOf(owner);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

285 if ((index < 0) && add) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

286 lockThreads.add(owner);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

287 resize = true;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

288 index = lockThreads.size() - 1;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

289 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

290 return index;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

291 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

292

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

293 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

294 * Returns true IFF the adjacency matrix is empty.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

295 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

296 bool isEmpty() {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

297 return (locks.size() is 0) && (lockThreads.size() is 0) && (graph.length is 0);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

298 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

299

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

300 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

301 * The given lock was acquired by the given thread.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

302 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

303 void lockAcquired(JThread owner, ISchedulingRule lock) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

304 int lockIndex = indexOf(lock, true);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

305 int threadIndex = indexOf(owner, true);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

306 if (resize)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

307 resizeGraph();

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

308 if (graph[threadIndex][lockIndex] is WAITING_FOR_LOCK)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

309 graph[threadIndex][lockIndex] = NO_STATE;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

310 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

311 * acquire all locks that conflict with the given lock

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

312 * or conflict with a lock the given lock will acquire implicitly

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

313 * (locks are acquired implicitly when a conflicting lock is acquired)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

314 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

315 ArrayList conflicting = new ArrayList(1);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

316 //only need two passes through all the locks to pick up all conflicting rules

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

317 int NUM_PASSES = 2;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

318 conflicting.add(cast(Object)lock);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

319 graph[threadIndex][lockIndex]++;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

320 for (int i = 0; i < NUM_PASSES; i++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

321 for (int k = 0; k < conflicting.size(); k++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

322 ISchedulingRule current = cast(ISchedulingRule) conflicting.get(k);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

323 for (int j = 0; j < locks.size(); j++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

324 ISchedulingRule possible = cast(ISchedulingRule) locks.get(j);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

325 if (current.isConflicting(possible) && !conflicting.contains(cast(Object)possible)) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

326 conflicting.add(cast(Object)possible);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

327 graph[threadIndex][j]++;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

328 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

329 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

330 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

331 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

332 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

333

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

334 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

335 * The given lock was released by the given thread. Update the graph.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

336 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

337 void lockReleased(JThread owner, ISchedulingRule lock) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

338 int lockIndex = indexOf(lock, false);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

339 int threadIndex = indexOf(owner, false);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

340 //make sure the lock and thread exist in the graph

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

341 if (threadIndex < 0) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

342 if (JobManager.DEBUG_LOCKS)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

343 Stdout.formatln("[lockReleased] Lock {} was already released by thread {}", lock, owner.getName()); //$NON-NLS-1$ //$NON-NLS-2$

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

344 return;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

345 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

346 if (lockIndex < 0) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

347 if (JobManager.DEBUG_LOCKS)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

348 Stdout.formatln("[lockReleased] Thread {} already released lock {}", owner.getName(), lock); //$NON-NLS-1$ //$NON-NLS-2$

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

349 return;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

350 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

351 //if this lock was suspended, set it to NO_STATE

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

352 if ((cast(ILock)lock ) && (graph[threadIndex][lockIndex] is WAITING_FOR_LOCK)) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

353 graph[threadIndex][lockIndex] = NO_STATE;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

354 return;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

355 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

356 //release all locks that conflict with the given lock

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

357 //or release all rules that are owned by the given thread, if we are releasing a rule

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

358 for (int j = 0; j < graph[threadIndex].length; j++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

359 if ((lock.isConflicting(cast(ISchedulingRule) locks.get(j))) || (!(cast(ILock)lock ) && !(cast(ILock)locks.get(j)) && (graph[threadIndex][j] > NO_STATE))) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

360 if (graph[threadIndex][j] is NO_STATE) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

361 if (JobManager.DEBUG_LOCKS)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

362 Stdout.formatln("[lockReleased] More releases than acquires for thread {} and lock {}", owner.getName(), lock); //$NON-NLS-1$ //$NON-NLS-2$

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

363 } else {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

364 graph[threadIndex][j]--;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

365 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

366 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

367 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

368 //if this thread just released the given lock, try to simplify the graph

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

369 if (graph[threadIndex][lockIndex] is NO_STATE)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

370 reduceGraph(threadIndex, lock);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

371 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

372

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

373 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

374 * The given scheduling rule is no longer used because the job that invoked it is done.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

375 * Release this rule regardless of how many times it was acquired.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

376 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

377 void lockReleasedCompletely(JThread owner, ISchedulingRule rule) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

378 int ruleIndex = indexOf(rule, false);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

379 int threadIndex = indexOf(owner, false);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

380 //need to make sure that the given thread and rule were not already removed from the graph

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

381 if (threadIndex < 0) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

382 if (JobManager.DEBUG_LOCKS)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

383 Stdout.formatln("[lockReleasedCompletely] Lock {} was already released by thread {}", rule, owner.getName()); //$NON-NLS-1$ //$NON-NLS-2$

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

384 return;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

385 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

386 if (ruleIndex < 0) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

387 if (JobManager.DEBUG_LOCKS)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

388 Stdout.formatln("[lockReleasedCompletely] Thread {} already released lock {}", owner.getName(), rule); //$NON-NLS-1$ //$NON-NLS-2$

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

389 return;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

390 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

391 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

392 * set all rules that are owned by the given thread to NO_STATE

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

393 * (not just rules that conflict with the rule we are releasing)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

394 * if we are releasing a lock, then only update the one entry for the lock

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

395 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

396 for (int j = 0; j < graph[threadIndex].length; j++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

397 if (!(cast(ILock)locks.get(j) ) && (graph[threadIndex][j] > NO_STATE))

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

398 graph[threadIndex][j] = NO_STATE;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

399 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

400 reduceGraph(threadIndex, rule);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

401 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

402

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

403 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

404 * The given thread could not get the given lock and is waiting for it.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

405 * Update the graph.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

406 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

407 Deadlock lockWaitStart(JThread client, ISchedulingRule lock) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

408 setToWait(client, lock, false);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

409 int lockIndex = indexOf(lock, false);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

410 int[] temp = new int[lockThreads.size()];

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

411 //check if the addition of the waiting thread caused deadlock

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

412 if (!checkWaitCycles(temp, lockIndex))

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

413 return null;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

414 //there is a deadlock in the graph

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

415 JThread[] threads = getThreadsInDeadlock(client);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

416 JThread candidate = resolutionCandidate(threads);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

417 ISchedulingRule[] locksToSuspend = realLocksForThread(candidate);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

418 Deadlock deadlock = new Deadlock(threads, locksToSuspend, candidate);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

419 //find a thread whose locks can be suspended to resolve the deadlock

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

420 if (JobManager.DEBUG_LOCKS)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

421 reportDeadlock(deadlock);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

422 if (JobManager.DEBUG_DEADLOCK)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

423 throw new IllegalStateException(Format("Deadlock detected. Caused by thread {}.", client.getName())); //$NON-NLS-1$

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

424 // Update the graph to indicate that the locks will now be suspended.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

425 // To indicate that the lock will be suspended, we set the thread to wait for the lock.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

426 // When the lock is forced to be released, the entry will be cleared.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

427 for (int i = 0; i < locksToSuspend.length; i++)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

428 setToWait(deadlock.getCandidate(), locksToSuspend[i], true);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

429 return deadlock;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

430 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

431

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

432 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

433 * The given thread has stopped waiting for the given lock.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

434 * Update the graph.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

435 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

436 void lockWaitStop(JThread owner, ISchedulingRule lock) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

437 int lockIndex = indexOf(lock, false);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

438 int threadIndex = indexOf(owner, false);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

439 //make sure the thread and lock exist in the graph

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

440 if (threadIndex < 0) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

441 if (JobManager.DEBUG_LOCKS)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

442 Stdout.formatln("Thread {} was already removed.", owner.getName() ); //$NON-NLS-1$ //$NON-NLS-2$

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

443 return;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

444 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

445 if (lockIndex < 0) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

446 if (JobManager.DEBUG_LOCKS)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

447 Stdout.formatln("Lock {} was already removed.", lock ); //$NON-NLS-1$ //$NON-NLS-2$

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

448 return;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

449 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

450 if (graph[threadIndex][lockIndex] !is WAITING_FOR_LOCK)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

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$

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

452 graph[threadIndex][lockIndex] = NO_STATE;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

453 reduceGraph(threadIndex, lock);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

454 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

455

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

456 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

457 * Returns true IFF the given thread owns a single lock

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

458 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

459 private bool ownsLocks(JThread cause) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

460 int threadIndex = indexOf(cause, false);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

461 for (int j = 0; j < graph[threadIndex].length; j++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

462 if (graph[threadIndex][j] > NO_STATE)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

463 return true;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

464 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

465 return false;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

466 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

467

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

468 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

469 * Returns true IFF the given thread owns a single real lock.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

470 * A real lock is a lock that can be suspended.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

471 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

472 private bool ownsRealLocks(JThread owner) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

473 int threadIndex = indexOf(owner, false);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

474 for (int j = 0; j < graph[threadIndex].length; j++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

475 if (graph[threadIndex][j] > NO_STATE) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

476 Object lock = locks.get(j);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

477 if (cast(ILock)lock )

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

478 return true;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

479 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

480 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

481 return false;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

482 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

483

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

484 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

485 * Return true IFF this thread owns rule locks (i.e. implicit locks which

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

486 * cannot be suspended)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

487 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

488 private bool ownsRuleLocks(JThread owner) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

489 int threadIndex = indexOf(owner, false);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

490 for (int j = 0; j < graph[threadIndex].length; j++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

491 if (graph[threadIndex][j] > NO_STATE) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

492 Object lock = locks.get(j);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

493 if (!(cast(ILock)lock ))

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

494 return true;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

495 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

496 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

497 return false;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

498 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

499

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

500 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

501 * Returns an array of real locks that are owned by the given thread.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

502 * Real locks are locks that implement the ILock interface and can be suspended.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

503 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

504 private ISchedulingRule[] realLocksForThread(JThread owner) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

505 int threadIndex = indexOf(owner, false);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

506 ArrayList ownedLocks = new ArrayList(1);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

507 for (int j = 0; j < graph[threadIndex].length; j++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

508 if ((graph[threadIndex][j] > NO_STATE) && (cast(ILock)locks.get(j) ))

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

509 ownedLocks.add(locks.get(j));

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

510 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

511 if (ownedLocks.size() is 0)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

512 Assert.isLegal(false, "A thread with no real locks was chosen to resolve deadlock."); //$NON-NLS-1$

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

513 return arraycast!(ISchedulingRule)( ownedLocks.toArray());

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

514 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

515

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

516 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

517 * The matrix has been simplified. Check if any unnecessary rows or columns

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

518 * can be removed.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

519 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

520 private void reduceGraph(int row, ISchedulingRule lock) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

521 int numLocks = locks.size();

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

522 bool[] emptyColumns = new bool[numLocks];

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

523

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

524 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

525 * find all columns that could possibly be empty

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

526 * (consist of locks which conflict with the given lock, or of locks which are rules)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

527 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

528 for (int j = 0; j < numLocks; j++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

529 if ((lock.isConflicting(cast(ISchedulingRule) locks.get(j))) || !(cast(ILock)locks.get(j)))

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

530 emptyColumns[j] = true;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

531 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

532

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

533 bool rowEmpty = true;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

534 int numEmpty = 0;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

535 //check if the given row is empty

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

536 for (int j = 0; j < graph[row].length; j++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

537 if (graph[row][j] !is NO_STATE) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

538 rowEmpty = false;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

539 break;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

540 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

541 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

542 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

543 * Check if the possibly empty columns are actually empty.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

544 * If a column is actually empty, remove the corresponding lock from the list of locks

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

545 * Start at the last column so that when locks are removed from the list,

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

546 * the index of the remaining locks is unchanged. Store the number of empty columns.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

547 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

548 for (int j = emptyColumns.length - 1; j >= 0; j--) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

549 for (int i = 0; i < graph.length; i++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

550 if (emptyColumns[j] && (graph[i][j] !is NO_STATE)) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

551 emptyColumns[j] = false;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

552 break;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

553 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

554 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

555 if (emptyColumns[j]) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

556 locks.remove(j);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

557 numEmpty++;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

558 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

559 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

560 //if no columns or rows are empty, return right away

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

561 if ((numEmpty is 0) && (!rowEmpty))

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

562 return;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

563

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

564 if (rowEmpty)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

565 lockThreads.remove(row);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

566

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

567 //new graph (the list of locks and the list of threads are already updated)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

568 final int numThreads = lockThreads.size();

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

569 numLocks = locks.size();

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

570 //optimize empty graph case

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

571 if (numThreads is 0 && numLocks is 0) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

572 graph = EMPTY_MATRIX;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

573 return;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

574 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

575 int[][] tempGraph = new int[][](numThreads,numLocks);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

576

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

577 //the number of rows we need to skip to get the correct entry from the old graph

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

578 int numRowsSkipped = 0;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

579 for (int i = 0; i < graph.length - numRowsSkipped; i++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

580 if ((i is row) && rowEmpty) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

581 numRowsSkipped++;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

582 //check if we need to skip the last row

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

583 if (i >= graph.length - numRowsSkipped)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

584 break;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

585 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

586 //the number of columns we need to skip to get the correct entry from the old graph

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

587 //needs to be reset for every new row

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

588 int numColsSkipped = 0;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

589 for (int j = 0; j < graph[i].length - numColsSkipped; j++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

590 while (emptyColumns[j + numColsSkipped]) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

591 numColsSkipped++;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

592 //check if we need to skip the last column

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

593 if (j >= graph[i].length - numColsSkipped)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

594 break;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

595 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

596 //need to break out of the outer loop

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

597 if (j >= graph[i].length - numColsSkipped)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

598 break;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

599 tempGraph[i][j] = graph[i + numRowsSkipped][j + numColsSkipped];

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

600 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

601 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

602 graph = tempGraph;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

603 Assert.isTrue(numThreads is graph.length, "Rows and threads don't match."); //$NON-NLS-1$

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

604 Assert.isTrue(numLocks is ((graph.length > 0) ? graph[0].length : 0), "Columns and locks don't match."); //$NON-NLS-1$

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

605 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

606

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

607 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

608 * Adds a 'deadlock detected' message to the log with a stack trace.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

609 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

610 private void reportDeadlock(Deadlock deadlock) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

611 String msg = "Deadlock detected. All locks owned by thread " ~ deadlock.getCandidate().getName() ~ " will be suspended."; //$NON-NLS-1$ //$NON-NLS-2$

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

612 MultiStatus main = new MultiStatus(JobManager.PI_JOBS, JobManager.PLUGIN_ERROR, msg, new IllegalStateException());

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

613 JThread[] threads = deadlock.getThreads();

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

614 for (int i = 0; i < threads.length; i++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

615 Object[] ownedLocks = getOwnedLocks(threads[i]);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

616 Object waitLock = getWaitingLock(threads[i]);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

617 StringBuffer buf = new StringBuffer("Thread "); //$NON-NLS-1$

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

618 buf.append(threads[i].getName());

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

619 buf.append(" has locks: "); //$NON-NLS-1$

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

620 for (int j = 0; j < ownedLocks.length; j++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

621 buf.append(Format("{}",ownedLocks[j]));

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

622 buf.append((j < ownedLocks.length - 1) ? ", " : " "); //$NON-NLS-1$ //$NON-NLS-2$

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

623 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

624 buf.append("and is waiting for lock "); //$NON-NLS-1$

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

625 buf.append(Format("{}",waitLock));

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

626 Status child = new Status(IStatus.ERROR, JobManager.PI_JOBS, JobManager.PLUGIN_ERROR, buf.toString(), null);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

627 main.add(child);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

628 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

629 RuntimeLog.log(main);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

630 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

631

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

632 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

633 * The number of threads/locks in the graph has changed. Update the

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

634 * underlying matrix.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

635 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

636 private void resizeGraph() {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

637 // a new row and/or a new column was added to the graph.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

638 // since new rows/columns are always added to the end, just transfer

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

639 // old entries to the new graph, with the same indices.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

640 final int newRows = lockThreads.size();

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

641 final int newCols = locks.size();

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

642 //optimize 0x0 and 1x1 matrices

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

643 if (newRows is 0 && newCols is 0) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

644 graph = EMPTY_MATRIX;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

645 return;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

646 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

647 int[][] tempGraph = new int[][](newRows,newCols);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

648 for (int i = 0; i < graph.length; i++)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

649 System.arraycopy(graph[i], 0, tempGraph[i], 0, graph[i].length);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

650 graph = tempGraph;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

651 resize = false;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

652 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

653

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

654 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

655 * Get the thread whose locks can be suspended. (i.e. all locks it owns are

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

656 * actual locks and not rules). Return the first thread in the array by default.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

657 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

658 private JThread resolutionCandidate(JThread[] candidates) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

659 //first look for a candidate that has no scheduling rules

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

660 for (int i = 0; i < candidates.length; i++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

661 if (!ownsRuleLocks(candidates[i]))

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

662 return candidates[i];

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

663 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

664 //next look for any candidate with a real lock (a lock that can be suspended)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

665 for (int i = 0; i < candidates.length; i++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

666 if (ownsRealLocks(candidates[i]))

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

667 return candidates[i];

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

668 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

669 //unnecessary, return the first entry in the array by default

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

670 return candidates[0];

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

671 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

672

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

673 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

674 * The given thread is waiting for the given lock. Update the graph.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

675 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

676 private void setToWait(JThread owner, ISchedulingRule lock, bool suspend) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

677 bool needTransfer = false;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

678 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

679 * if we are adding an entry where a thread is waiting on a scheduling rule,

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

680 * then we need to transfer all positive entries for a conflicting rule to the

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

681 * newly added rule in order to synchronize the graph.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

682 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

683 if (!suspend && !(cast(ILock)lock))

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

684 needTransfer = true;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

685 int lockIndex = indexOf(lock, !suspend);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

686 int threadIndex = indexOf(owner, !suspend);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

687 if (resize)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

688 resizeGraph();

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

689

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

690 graph[threadIndex][lockIndex] = WAITING_FOR_LOCK;

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

691 if (needTransfer)

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

692 fillPresentEntries(lock, lockIndex);

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

693 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

694

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

695 /**

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

696 * Prints out the current matrix to standard output.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

697 * Only used for debugging.

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

698 */

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

699 public String toDebugString() {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

700 StringBuffer sb = new StringBuffer();

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

701 sb.append(" :: \n"); //$NON-NLS-1$

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

702 for (int j = 0; j < locks.size(); j++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

703 sb.append(" ");

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

704 sb.append( locks.get(j).toString );

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

705 sb.append(",");

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

706 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

707 sb.append("\n");

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

708 for (int i = 0; i < graph.length; i++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

709 sb.append(" ");

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

710 sb.append( (cast(JThread) lockThreads.get(i)).getName() );

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

711 sb.append(" : ");

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

712 for (int j = 0; j < graph[i].length; j++) {

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

713 sb.append(" ");

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

714 sb.append(Integer.toString(graph[i][j])); //$NON-NLS-1$

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

715 sb.append(",");

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

716 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

717 sb.append("\n");

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

718 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

719 sb.append("-------\n"); //$NON-NLS-1$

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

720 return sb.toString();

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

721 }

bc29606a740c Added dwt-addons in original directory structure of eclipse.org

Frank Benoit <benoit@tionex.de>

parents:

diff changeset

722 }

Mercurial > projects > dwt2

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