You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@geode.apache.org by bs...@apache.org on 2015/08/12 18:00:14 UTC
incubator-geode git commit: improvements to deadlock detection.
Addition of a main method to DeadlockDetector that recognizes
findDeepestGraph, findDeadlockOnly,
findThread and print commands. We need a project to enable dependency
monitoring in proces
Repository: incubator-geode
Updated Branches:
refs/heads/feature/GEODE-77 3c560cb93 -> 52f8ce6d1
improvements to deadlock detection. Addition of a main method to DeadlockDetector that recognizes findDeepestGraph, findDeadlockOnly, findThread and print commands. We need a project to enable dependency monitoring in processes spawned with Gfsh and to collect dependencies and serialize them to disk so that this tool can be used to analyse distributed systems.
Project: http://git-wip-us.apache.org/repos/asf/incubator-geode/repo
Commit: http://git-wip-us.apache.org/repos/asf/incubator-geode/commit/52f8ce6d
Tree: http://git-wip-us.apache.org/repos/asf/incubator-geode/tree/52f8ce6d
Diff: http://git-wip-us.apache.org/repos/asf/incubator-geode/diff/52f8ce6d
Branch: refs/heads/feature/GEODE-77
Commit: 52f8ce6d17991eec951d7bf167ff4611ed8093cc
Parents: 3c560cb
Author: Bruce Schuchardt <bs...@pivotal.io>
Authored: Wed Aug 12 08:57:54 2015 -0700
Committer: Bruce Schuchardt <bs...@pivotal.io>
Committed: Wed Aug 12 08:57:54 2015 -0700
----------------------------------------------------------------------
.../internal/deadlock/DeadlockDetector.java | 175 ++++++++++++++++++-
.../internal/deadlock/DependencyGraph.java | 138 +++++++++++++--
.../internal/deadlock/LocalThread.java | 2 +-
3 files changed, 291 insertions(+), 24 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/incubator-geode/blob/52f8ce6d/gemfire-core/src/main/java/com/gemstone/gemfire/distributed/internal/deadlock/DeadlockDetector.java
----------------------------------------------------------------------
diff --git a/gemfire-core/src/main/java/com/gemstone/gemfire/distributed/internal/deadlock/DeadlockDetector.java b/gemfire-core/src/main/java/com/gemstone/gemfire/distributed/internal/deadlock/DeadlockDetector.java
index ec619b4..e361184 100644
--- a/gemfire-core/src/main/java/com/gemstone/gemfire/distributed/internal/deadlock/DeadlockDetector.java
+++ b/gemfire-core/src/main/java/com/gemstone/gemfire/distributed/internal/deadlock/DeadlockDetector.java
@@ -7,6 +7,10 @@
*/
package com.gemstone.gemfire.distributed.internal.deadlock;
+import java.io.BufferedInputStream;
+import java.io.File;
+import java.io.FileInputStream;
+import java.io.ObjectInputStream;
import java.io.Serializable;
import java.lang.management.LockInfo;
import java.lang.management.ManagementFactory;
@@ -17,6 +21,7 @@ import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.LinkedList;
+import java.util.List;
import java.util.Map;
import java.util.Set;
@@ -36,6 +41,9 @@ import java.util.Set;
* not reported by the VM - such as the association between message senders and
* processors in different VMs.
*
+ * This class also has a main() method that can read serialized DependencyGraphs
+ * from multiple JVMs, merge them and perform various analysis on them.
+ *
* @author dsmith
*
*/
@@ -51,9 +59,7 @@ public class DeadlockDetector {
* be analyzed.
*/
public void addDependencies(Set<Dependency> dependencies) {
- for (Dependency dep : dependencies) {
- graph.addEdge(dep);
- }
+ graph.addEdges(dependencies);
}
/**
@@ -89,7 +95,10 @@ public class DeadlockDetector {
* Threads may depend on locks, or on other resources that are tracked by the
* {@link DependencyMonitor}.
*
- * @return All of the dependencies between threads an locks or other resources
+ * @arg locality a name tag to stick on entities to help associate them with
+ * this JVM and distinguish them from entities from other jvms
+ *
+ * @return All of the dependencies between threads and locks or other resources
* on this VM.
*/
public static Set<Dependency> collectAllDependencies(Serializable locality) {
@@ -139,29 +148,82 @@ public class DeadlockDetector {
public static String prettyFormat(Collection<Dependency> deadlock) {
StringBuilder text = new StringBuilder();
LinkedHashSet<LocalThread> threads = new LinkedHashSet<LocalThread>();
+
+ Set<Object> seenDependers = new HashSet<>();
+ Object lastDependsOn = text;
+ Object lastDepender = text;
+
for (Dependency dep : deadlock) {
Object depender = dep.getDepender();
Object dependsOn = dep.getDependsOn();
+
+ String dependerString;
+ if (lastDependsOn.equals(depender)) {
+ dependerString = "which";
+ } else if (lastDepender.equals(depender)){
+ dependerString = "and";
+ } else {
+ dependerString = String.valueOf(depender);
+ }
+ lastDepender = depender;
+ lastDependsOn = dependsOn;
+
+ String also = seenDependers.contains(depender)? " also" : "";
+ seenDependers.add(depender);
+
if (depender instanceof LocalThread) {
- text.append(depender + " is waiting on " + dependsOn + "\n");
+ text.append(dependerString).append(" is").append(also).append(" waiting on ").append(dependsOn).append("\n");
threads.add((LocalThread) depender);
} else if (dependsOn instanceof LocalThread) {
- text.append(depender + " is held by " + dependsOn + "\n");
+ text.append(dependerString).append(" is held by thread ").append(dependsOn).append("\n");
threads.add((LocalThread) dependsOn);
} else {
- text.append(depender + " is waiting for " + dependsOn + "\n");
+ text.append(dependerString).append(" is").append(also).append(" waiting for ").append(dependsOn).append("\n");
}
+ text.append("\n");
}
text.append("\nStack traces for involved threads\n");
for (LocalThread threadInfo : threads) {
- text.append(
- threadInfo.getLocatility() + ":" + threadInfo.getThreadStack())
+ text.append(threadInfo.getLocatility())
+ .append(":")
+ .append(threadInfo.getThreadStack())
.append("\n\n");
}
return text.toString();
}
+
+
+ /**
+ * attempts to sort the given dependencies according to their contents
+ * so that dependents come after dependers.
+ * @param dependencies
+ * TODO this method needs more work
+ */
+ public static List<Dependency> sortDependencies(Collection<Dependency> dependencies) {
+ List<Dependency> result = new LinkedList<>();
+ for (Dependency dep: dependencies) {
+ boolean added = false;
+ for (int i=0; i<result.size(); i++) {
+ Dependency other = result.get(i);
+ if (other.depender.equals(dep.depender)) {
+ result.add(i, dep);
+ added = true;
+ break;
+ }
+ if (other.depender.equals(dep.dependsOn)) {
+ result.add(i, dep);
+ added = true;
+ break;
+ }
+ }
+ if (!added) {
+ result.add(dep);
+ }
+ }
+ return result;
+ }
/**
* Format dependency graph for displaying to a user.
@@ -216,4 +278,99 @@ public class DeadlockDetector {
}
return results;
}
+
+ private static DependencyGraph loadGraphs(int startingAt, String... mainArgs) throws Exception {
+ String filename;
+ if (mainArgs.length < startingAt+1) {
+ return loadGraph("thread_dependency_graph.ser");
+ }
+
+ DependencyGraph result = new DependencyGraph();
+
+ for (int i=startingAt; i<mainArgs.length; i++) {
+ filename = mainArgs[i];
+ DependencyGraph gr = loadGraph(filename);
+ if (gr == null) {
+ return null;
+ }
+ result.addEdges(gr.getEdges());
+ }
+
+ return result;
+ }
+
+ private static DependencyGraph loadGraph(String filename) throws Exception {
+ File file = new File(filename);
+ if (!file.exists()) {
+ System.err.println("unable to find " + filename);
+ System.exit(-1);
+ }
+
+ ObjectInputStream ois = new ObjectInputStream(new BufferedInputStream(new FileInputStream(file)));
+ DependencyGraph graph = (DependencyGraph) ois.readObject();
+
+ return graph;
+ }
+
+
+ private static void printHelp() {
+ System.out.println("DeadlockDetector reads serialized graphs of the state of the distributed");
+ System.out.println("system created by collectDependencies.");
+ System.out.println();
+ System.out.println("usage: ");
+ System.out.println("[print | findDeepestGraph | findDeadlockOnly | findThread threadName ] file1 ...");
+ System.out.println();
+ System.out.println("print - prints all dependencies and threads in the graph");
+ System.out.println("findDeepestGraph - looks for either a deadlock or the longest call chain in the graph");
+ System.out.println("findDeadlockOnly - looks for a deadlock in the distributed system");
+ System.out.println("findThread - finds the given thread by name/partial name and builds a dependency graph around it");
+ }
+
+ public static void main(String... args) throws Exception {
+ if (args.length == 0) {
+ printHelp();
+ return;
+ }
+
+ DependencyGraph graph;
+
+ switch (args[0]) {
+ case "print":
+ graph = loadGraphs(1, args);
+ System.out.println(prettyFormat(graph));
+ break;
+ case "findDeadlockOnly":
+ graph = loadGraphs(1, args);
+ List<Dependency> cycle = graph.findCycle();
+ if (cycle == null) {
+ System.out.println("no deadlock found");
+ } else {
+ System.out.println("deadlocked threads: \n" + cycle);
+ }
+ break;
+ case "findDeepestGraph":
+ graph = loadGraphs(1, args);
+ DependencyGraph result = graph.findDeepestGraph();
+ if (result == null) {
+ System.out.println("no deepest graph could be found!");
+ } else {
+ System.out.println("deepest graph: \n" + prettyFormat(result));
+ }
+ break;
+ case "findThread":
+ graph = loadGraphs(2, args);
+ result = graph.findDependenciesWith(args[1]);
+ if (result == null) {
+ System.out.println("thread not found!");
+ } else {
+ System.out.println(prettyFormat(sortDependencies(result.getEdges())));
+ }
+ break;
+ default:
+ printHelp();
+ break;
+ }
+
+ }
+
}
http://git-wip-us.apache.org/repos/asf/incubator-geode/blob/52f8ce6d/gemfire-core/src/main/java/com/gemstone/gemfire/distributed/internal/deadlock/DependencyGraph.java
----------------------------------------------------------------------
diff --git a/gemfire-core/src/main/java/com/gemstone/gemfire/distributed/internal/deadlock/DependencyGraph.java b/gemfire-core/src/main/java/com/gemstone/gemfire/distributed/internal/deadlock/DependencyGraph.java
index 5a93f72..e3d1e55 100644
--- a/gemfire-core/src/main/java/com/gemstone/gemfire/distributed/internal/deadlock/DependencyGraph.java
+++ b/gemfire-core/src/main/java/com/gemstone/gemfire/distributed/internal/deadlock/DependencyGraph.java
@@ -13,6 +13,7 @@ import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
+import java.util.List;
import java.util.Map;
import java.util.Set;
@@ -25,6 +26,7 @@ import java.util.Set;
*
*
* @author dsmith
+ * @author bschuchardt
*
*/
public class DependencyGraph implements Serializable {
@@ -42,22 +44,30 @@ public class DependencyGraph implements Serializable {
*/
private Set<Dependency> edges = new LinkedHashSet<Dependency>();
+ /** add a collection of edges to this graph */
+ public void addEdges(Collection<Dependency> edges) {
+ for (Dependency dep: edges) {
+ addEdge(dep);
+ }
+ }
+
/**
* Add an edge to the dependency graph.
*/
public void addEdge(Dependency dependency) {
- edges.add(dependency);
- Set<Dependency> outboundEdges = vertices.get(dependency.getDepender());
- if(outboundEdges == null) {
- outboundEdges = new HashSet();
- vertices.put(dependency.getDepender(), outboundEdges);
- }
- outboundEdges.add(dependency);
-
- if(vertices.get(dependency.getDependsOn()) == null) {
- vertices.put(dependency.getDependsOn(), new HashSet());
+ if (!edges.contains(dependency)) {
+ edges.add(dependency);
+ Set<Dependency> outboundEdges = vertices.get(dependency.getDepender());
+ if(outboundEdges == null) {
+ outboundEdges = new HashSet();
+ vertices.put(dependency.getDepender(), outboundEdges);
+ }
+ outboundEdges.add(dependency);
+
+ if(vertices.get(dependency.getDependsOn()) == null) {
+ vertices.put(dependency.getDependsOn(), new HashSet());
+ }
}
-
}
/**
@@ -77,7 +87,7 @@ public class DependencyGraph implements Serializable {
Object start = unvisited.iterator().next();
CycleHolder cycle = new CycleHolder();
- boolean foundCycle = visitCycle(start, unvisited, finished, cycle);
+ boolean foundCycle = visitCycle(start, unvisited, finished, cycle, 0);
if(foundCycle) {
return cycle.cycle;
}
@@ -87,6 +97,73 @@ public class DependencyGraph implements Serializable {
}
/**
+ * This will find the deepest call chain in the graph. If a
+ * cycle is detected it will be returned. Otherwise all
+ * subgraphs are traversed to find the one that has the most
+ * depth. This usually indicates the thread that is blocking
+ * the most other threads.
+ */
+ public DependencyGraph findDeepestGraph() {
+ int depth = 0;
+ DependencyGraph deepest = null;
+
+ for (Object dep: vertices.keySet()) {
+ int itsDepth = getDepth(dep);
+ if (itsDepth > depth) {
+ deepest = getSubGraph(dep);
+ depth = itsDepth;
+ }
+ }
+
+ return deepest;
+ }
+
+
+ public DependencyGraph findDependenciesWith(String objectName) {
+ Object obj = null;
+ Dependency objDep = null;
+ for (Dependency dep: edges) {
+ if (dep.depender.toString().contains(objectName)) {
+ obj = dep.depender;
+ objDep = dep;
+ break;
+ }
+ if (dep.dependsOn.toString().contains(objectName)) {
+ obj = dep.dependsOn;
+ objDep = dep;
+ break;
+ }
+ }
+ if (obj == null) {
+ return null;
+ }
+
+ DependencyGraph result = new DependencyGraph();
+
+ Set<Object> dependsOnObj = new HashSet<>();
+ dependsOnObj.add(obj);
+ boolean anyAdded = true;
+ while (anyAdded) {
+ anyAdded = false;
+ for (Dependency dep: edges) {
+ if (dependsOnObj.contains(dep.dependsOn)
+ && !dependsOnObj.contains(dep.depender)) {
+ anyAdded = true;
+ dependsOnObj.add(dep.depender);
+ }
+ }
+ }
+ for (Object depender: dependsOnObj) {
+ if (!result.getVertices().contains(depender)) {
+ DependencyGraph subgraph = getSubGraph(depender);
+ result.addEdges(subgraph.getEdges());
+ }
+ }
+ return result;
+ }
+
+
+ /**
* Visit a vertex for the purposes of finding a cycle in the graph.
*
* @param start
@@ -97,9 +174,10 @@ public class DependencyGraph implements Serializable {
* the set of vertices that have been completely analyzed
* @param cycle
* an object used to record the any cycles that are detected
+ * @param depth the depth of the recursion chain up to this point
*/
private boolean visitCycle(Object start, Set<Object> unvisited,
- Set<Object> finished, CycleHolder cycle) {
+ Set<Object> finished, CycleHolder cycle, int depth) {
if(finished.contains(start)) {
return false;
}
@@ -108,9 +186,11 @@ public class DependencyGraph implements Serializable {
return true;
}
+ cycle.processDepth(depth);
+
boolean foundCycle = false;
for(Dependency dep : vertices.get(start)) {
- foundCycle |= visitCycle(dep.getDependsOn(), unvisited, finished, cycle);
+ foundCycle |= visitCycle(dep.getDependsOn(), unvisited, finished, cycle, depth+1);
if(foundCycle) {
cycle.add(dep);
break;
@@ -121,6 +201,24 @@ public class DependencyGraph implements Serializable {
return foundCycle;
}
+ /** return the depth of the subgraph for the given object */
+ private int getDepth(Object depender) {
+ Set<Object> unvisited = new HashSet<Object>(vertices.keySet());
+ Set<Object> finished = new HashSet<Object>(vertices.size());
+
+ Object start = depender;
+ CycleHolder cycle = new CycleHolder();
+
+ boolean foundCycle = visitCycle(start, unvisited, finished, cycle, 0);
+
+ if(foundCycle) {
+ return Integer.MAX_VALUE;
+ } else {
+ return cycle.getMaxDepth();
+ }
+ }
+
+
/**
* Get the subgraph that the starting object has dependencies on.
*
@@ -169,6 +267,17 @@ public class DependencyGraph implements Serializable {
private static class CycleHolder {
private LinkedList<Dependency> cycle = new LinkedList<Dependency>();
private boolean cycleDone;
+ private int maxDepth = 0;
+
+ public void processDepth(int depth) {
+ if (depth > maxDepth) {
+ maxDepth = depth;
+ }
+ }
+
+ public int getMaxDepth() {
+ return maxDepth;
+ }
public void add(Dependency dep) {
if(cycleDone) {
@@ -184,4 +293,5 @@ public class DependencyGraph implements Serializable {
}
}
}
+
}
http://git-wip-us.apache.org/repos/asf/incubator-geode/blob/52f8ce6d/gemfire-core/src/main/java/com/gemstone/gemfire/distributed/internal/deadlock/LocalThread.java
----------------------------------------------------------------------
diff --git a/gemfire-core/src/main/java/com/gemstone/gemfire/distributed/internal/deadlock/LocalThread.java b/gemfire-core/src/main/java/com/gemstone/gemfire/distributed/internal/deadlock/LocalThread.java
index 1371aa2..4515acc 100644
--- a/gemfire-core/src/main/java/com/gemstone/gemfire/distributed/internal/deadlock/LocalThread.java
+++ b/gemfire-core/src/main/java/com/gemstone/gemfire/distributed/internal/deadlock/LocalThread.java
@@ -57,7 +57,7 @@ public class LocalThread implements Serializable, ThreadReference {
if(info.getLockedSynchronizers().length > 0) {
result.append("\nLocked synchronizers:");
for(LockInfo sync : info.getLockedSynchronizers()) {
- result.append("\n" + sync.getClassName() + "@" + sync.getIdentityHashCode());
+ result.append("\n" + sync.getClassName() + "@" + Integer.toHexString(sync.getIdentityHashCode()));
}
}