Merge "ahat: Switch to a custom dominators implementation."
diff --git a/tools/ahat/src/ObjectsHandler.java b/tools/ahat/src/ObjectsHandler.java
index 86d48f1..fd226c2 100644
--- a/tools/ahat/src/ObjectsHandler.java
+++ b/tools/ahat/src/ObjectsHandler.java
@@ -43,13 +43,7 @@
Site site = mSnapshot.getSite(id, depth);
List<AhatInstance> insts = new ArrayList<AhatInstance>();
- for (AhatInstance inst : site.getObjects()) {
- if ((heapName == null || inst.getHeap().getName().equals(heapName))
- && (className == null || inst.getClassName().equals(className))) {
- insts.add(inst);
- }
- }
-
+ site.getObjects(heapName, className, insts);
Collections.sort(insts, Sort.defaultInstanceCompare(mSnapshot));
doc.title("Objects");
diff --git a/tools/ahat/src/Summarizer.java b/tools/ahat/src/Summarizer.java
index 016eab4..3e9da31 100644
--- a/tools/ahat/src/Summarizer.java
+++ b/tools/ahat/src/Summarizer.java
@@ -60,14 +60,7 @@
formatted.append("root ");
}
- // Annotate classes as classes.
- DocString linkText = new DocString();
- if (inst.isClassObj()) {
- linkText.append("class ");
- }
-
- linkText.append(inst.toString());
-
+ DocString linkText = DocString.text(inst.toString());
if (inst.isPlaceHolder()) {
// Don't make links to placeholder objects.
formatted.append(linkText);
diff --git a/tools/ahat/src/dominators/DominatorsComputation.java b/tools/ahat/src/dominators/DominatorsComputation.java
new file mode 100644
index 0000000..9a2a272
--- /dev/null
+++ b/tools/ahat/src/dominators/DominatorsComputation.java
@@ -0,0 +1,260 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.ahat.dominators;
+
+import java.util.ArrayDeque;
+import java.util.ArrayList;
+import java.util.Deque;
+import java.util.List;
+import java.util.Queue;
+
+/**
+ * Generic DominatorsComputation.
+ *
+ * To use the dominators computation, have your graph nodes implement the
+ * DominatorsComputation.Node interface, then call
+ * DominatorsComputation.computeDominators on the single root node.
+ */
+public class DominatorsComputation {
+ /**
+ * Interface for a directed graph to perform the dominators computation on.
+ */
+ public interface Node {
+ /**
+ * Associate the given dominator state with this node.
+ */
+ void setDominatorsComputationState(Object state);
+
+ /**
+ * Get the most recent dominator state associated with this node using
+ * setDominatorsComputationState. If setDominatorsComputationState has not
+ * yet been called, this should return null.
+ */
+ Object getDominatorsComputationState();
+
+ /**
+ * Return a collection of nodes referenced from this node, for the
+ * purposes of computing dominators.
+ */
+ Iterable<? extends Node> getReferencesForDominators();
+
+ /**
+ * Update this node's dominator based on the results of the dominators
+ * computation.
+ */
+ void setDominator(Node dominator);
+ }
+
+ // NodeS is information associated with a particular node for the
+ // purposes of computing dominators.
+ // By convention we use the suffix 'S' to name instances of NodeS.
+ private static class NodeS {
+ // The node that this NodeS is associated with.
+ public Node node;
+
+ // Unique identifier for this node, in increasing order based on the order
+ // this node was visited in a depth first search from the root. In
+ // particular, given nodes A and B, if A.id > B.id, then A cannot be a
+ // dominator of B.
+ public long id;
+
+ // Upper bound on the id of this node's dominator.
+ // The true immediate dominator of this node must have id <= domid.
+ // This upper bound is slowly tightened as part of the dominators
+ // computation.
+ public long domid;
+
+ // The current candidate dominator for this node.
+ // Invariant: (domid < domS.id) implies this node is on the queue of
+ // nodes to be revisited.
+ public NodeS domS;
+
+ // A node with a reference to this node that is one step closer to the
+ // root than this node.
+ // Invariant: srcS.id < this.id
+ public NodeS srcS;
+
+ // The set of nodes X reachable by 'this' on a path of nodes from the
+ // root with increasing ids (possibly excluding X) that this node does not
+ // dominate (this.id > X.domid).
+ // We can use a List instead of a Set for this because we guarentee that
+ // we don't add the same node more than once to the list (see below).
+ public List<NodeS> undom = new ArrayList<NodeS>();
+
+ // The largest id of the node X for which we did X.undom.add(this).
+ // This is an optimization to avoid adding duplicate node entries to the
+ // undom set.
+ //
+ // The first time we see this node, we reach it through a path of nodes
+ // with IDs 0,...,a,this. These form our src chain to the root.
+ //
+ // The next time we see this node, we reach it through a path of nodes
+ // with IDS 0,...,b,c,...,d,this. Where all 0,...,b < a and all c,...,d > a.
+ //
+ // The next time we see this node, we reach it through a path of nodes
+ // with IDS 0,...,e,f,...,g,this. With all 0,...,e < d and all f,...,g > d.
+ // And so on.
+ //
+ // The first time we see this node, we set undomid to a.id. Nodes 0,...,a
+ // will be added as undom in the 'revisit' phase of the node.
+ //
+ // The next times we see this node, we mark a+,...,d as undom and
+ // change undomid to d. And so on.
+ public long undomid;
+ }
+
+ private static class Link {
+ public NodeS srcS;
+ public Node dst;
+
+ public Link(NodeS srcS, Node dst) {
+ this.srcS = srcS;
+ this.dst = dst;
+ }
+ }
+
+ /**
+ * Compute the dominator tree rooted at the given node.
+ * There must not be any incoming references to the root node.
+ */
+ public static void computeDominators(Node root) {
+ long id = 0;
+
+ // List of all nodes seen. We keep track of this here to update all the
+ // dominators once we are done.
+ List<NodeS> nodes = new ArrayList<NodeS>();
+
+ // The set of nodes N such that N.domid < N.domS.id. These nodes need
+ // to be revisisted because their dominator is clearly wrong.
+ // Use a Queue instead of a Set because performance will be better. We
+ // avoid adding nodes already on the queue by checking whether it was
+ // already true that N.domid < N.domS.id, in which case the node is
+ // already on the queue.
+ Queue<NodeS> revisit = new ArrayDeque<NodeS>();
+
+ // Set up the root node specially.
+ NodeS rootS = new NodeS();
+ rootS.node = root;
+ rootS.id = id++;
+ root.setDominatorsComputationState(rootS);
+
+ // 1. Do a depth first search of the nodes, label them with ids and come
+ // up with intial candidate dominators for them.
+ Deque<Link> dfs = new ArrayDeque<Link>();
+ for (Node child : root.getReferencesForDominators()) {
+ dfs.push(new Link(rootS, child));
+ }
+
+ while (!dfs.isEmpty()) {
+ Link link = dfs.pop();
+ NodeS dstS = (NodeS)link.dst.getDominatorsComputationState();
+ if (dstS == null) {
+ // This is the first time we have seen the node. The candidate
+ // dominator is link src.
+ dstS = new NodeS();
+ dstS.node = link.dst;
+ dstS.id = id++;
+ dstS.domid = link.srcS.id;
+ dstS.domS = link.srcS;
+ dstS.srcS = link.srcS;
+ dstS.undomid = dstS.domid;
+ nodes.add(dstS);
+ link.dst.setDominatorsComputationState(dstS);
+
+ for (Node child : link.dst.getReferencesForDominators()) {
+ dfs.push(new Link(dstS, child));
+ }
+ } else {
+ // We have seen the node already. Update the state based on the new
+ // potential dominator.
+ NodeS srcS = link.srcS;
+ boolean revisiting = dstS.domid < dstS.domS.id;
+
+ while (srcS.id > dstS.domid) {
+ if (srcS.id > dstS.undomid) {
+ srcS.undom.add(dstS);
+ }
+ srcS = srcS.srcS;
+ }
+ dstS.undomid = link.srcS.id;
+
+ if (srcS.id < dstS.domid) {
+ // In this case, dstS.domid must be wrong, because we just found a
+ // path to dstS that does not go through dstS.domid:
+ // All nodes from root to srcS have id < domid, and all nodes from
+ // srcS to dstS had id > domid, so dstS.domid cannot be on this path
+ // from root to dstS.
+ dstS.domid = srcS.id;
+ if (!revisiting) {
+ revisit.add(dstS);
+ }
+ }
+ }
+ }
+
+ // 2. Continue revisiting nodes until they all satisfy the requirement
+ // that domS.id <= domid.
+ while (!revisit.isEmpty()) {
+ NodeS nodeS = revisit.poll();
+ NodeS domS = nodeS.domS;
+ assert nodeS.domid < domS.id;
+ while (domS.id > nodeS.domid) {
+ if (domS.domS.id < nodeS.domid) {
+ // In this case, nodeS.domid must be wrong, because there is a path
+ // from root to nodeS that does not go through nodeS.domid:
+ // * We can go from root to domS without going through nodeS.domid,
+ // because otherwise nodeS.domid would dominate domS, not
+ // domS.domS.
+ // * We can go from domS to nodeS without going through nodeS.domid
+ // because we know nodeS is reachable from domS on a path of nodes
+ // with increases ids, which cannot include nodeS.domid, which
+ // has a smaller id than domS.
+ nodeS.domid = domS.domS.id;
+ }
+ domS.undom.add(nodeS);
+ domS = domS.srcS;
+ }
+ nodeS.domS = domS;
+ nodeS.domid = domS.id;
+
+ for (NodeS xS : nodeS.undom) {
+ if (domS.id < xS.domid) {
+ // In this case, xS.domid must be wrong, because there is a path
+ // from the root to xX that does not go through xS.domid:
+ // * We can go from root to nodeS without going through xS.domid,
+ // because otherwise xS.domid would dominate nodeS, not domS.
+ // * We can go from nodeS to xS without going through xS.domid
+ // because we know xS is reachable from nodeS on a path of nodes
+ // with increasing ids, which cannot include xS.domid, which has
+ // a smaller id than nodeS.
+ boolean revisiting = xS.domid < xS.domS.id;
+ xS.domid = domS.id;
+ if (!revisiting) {
+ revisit.add(xS);
+ }
+ }
+ }
+ }
+
+ // 3. Update the dominators of the nodes.
+ root.setDominatorsComputationState(null);
+ for (NodeS nodeS : nodes) {
+ nodeS.node.setDominator(nodeS.domS.node);
+ nodeS.node.setDominatorsComputationState(null);
+ }
+ }
+}
diff --git a/tools/ahat/src/heapdump/AhatArrayInstance.java b/tools/ahat/src/heapdump/AhatArrayInstance.java
index d88cf94..6d4485d 100644
--- a/tools/ahat/src/heapdump/AhatArrayInstance.java
+++ b/tools/ahat/src/heapdump/AhatArrayInstance.java
@@ -20,6 +20,7 @@
import com.android.tools.perflib.heap.Instance;
import java.nio.charset.StandardCharsets;
import java.util.AbstractList;
+import java.util.Collections;
import java.util.List;
public class AhatArrayInstance extends AhatInstance {
@@ -37,8 +38,8 @@
super(id);
}
- @Override void initialize(AhatSnapshot snapshot, Instance inst) {
- super.initialize(snapshot, inst);
+ @Override void initialize(AhatSnapshot snapshot, Instance inst, Site site) {
+ super.initialize(snapshot, inst, site);
ArrayInstance array = (ArrayInstance)inst;
switch (array.getArrayType()) {
@@ -49,10 +50,6 @@
if (objects[i] != null) {
Instance ref = (Instance)objects[i];
insts[i] = snapshot.findInstance(ref.getId());
- if (ref.getNextInstanceToGcRoot() == inst) {
- String field = "[" + Integer.toString(i) + "]";
- insts[i].setNextInstanceToGcRoot(this, field);
- }
}
}
mValues = new AbstractList<Value>() {
@@ -132,6 +129,35 @@
return mValues.get(index);
}
+ @Override
+ ReferenceIterator getReferences() {
+ // The list of references will be empty if this is a primitive array.
+ List<Reference> refs = Collections.emptyList();
+ if (!mValues.isEmpty()) {
+ Value first = mValues.get(0);
+ if (first == null || first.isAhatInstance()) {
+ refs = new AbstractList<Reference>() {
+ @Override
+ public int size() {
+ return mValues.size();
+ }
+
+ @Override
+ public Reference get(int index) {
+ Value value = mValues.get(index);
+ if (value != null) {
+ assert value.isAhatInstance();
+ String field = "[" + Integer.toString(index) + "]";
+ return new Reference(AhatArrayInstance.this, field, value.asAhatInstance(), true);
+ }
+ return null;
+ }
+ };
+ }
+ }
+ return new ReferenceIterator(refs);
+ }
+
@Override public boolean isArrayInstance() {
return true;
}
diff --git a/tools/ahat/src/heapdump/AhatClassInstance.java b/tools/ahat/src/heapdump/AhatClassInstance.java
index 158de52..2115923 100644
--- a/tools/ahat/src/heapdump/AhatClassInstance.java
+++ b/tools/ahat/src/heapdump/AhatClassInstance.java
@@ -19,6 +19,7 @@
import com.android.tools.perflib.heap.ClassInstance;
import com.android.tools.perflib.heap.Instance;
import java.awt.image.BufferedImage;
+import java.util.AbstractList;
import java.util.Arrays;
import java.util.List;
@@ -29,8 +30,8 @@
super(id);
}
- @Override void initialize(AhatSnapshot snapshot, Instance inst) {
- super.initialize(snapshot, inst);
+ @Override void initialize(AhatSnapshot snapshot, Instance inst, Site site) {
+ super.initialize(snapshot, inst, site);
ClassInstance classInst = (ClassInstance)inst;
List<ClassInstance.FieldValue> fieldValues = classInst.getValues();
@@ -40,15 +41,7 @@
String name = field.getField().getName();
String type = field.getField().getType().toString();
Value value = snapshot.getValue(field.getValue());
-
mFieldValues[i] = new FieldValue(name, type, value);
-
- if (field.getValue() instanceof Instance) {
- Instance ref = (Instance)field.getValue();
- if (ref.getNextInstanceToGcRoot() == inst) {
- value.asAhatInstance().setNextInstanceToGcRoot(this, "." + name);
- }
- }
}
}
@@ -101,6 +94,30 @@
return Arrays.asList(mFieldValues);
}
+ @Override
+ ReferenceIterator getReferences() {
+ List<Reference> refs = new AbstractList<Reference>() {
+ @Override
+ public int size() {
+ return mFieldValues.length;
+ }
+
+ @Override
+ public Reference get(int index) {
+ FieldValue field = mFieldValues[index];
+ Value value = field.value;
+ if (value != null && value.isAhatInstance()) {
+ boolean strong = !field.name.equals("referent")
+ || !isInstanceOfClass("java.lang.ref.Reference");
+ AhatInstance ref = value.asAhatInstance();
+ return new Reference(AhatClassInstance.this, "." + field.name, ref, strong);
+ }
+ return null;
+ }
+ };
+ return new ReferenceIterator(refs);
+ }
+
/**
* Returns true if this is an instance of a class with the given name.
*/
diff --git a/tools/ahat/src/heapdump/AhatClassObj.java b/tools/ahat/src/heapdump/AhatClassObj.java
index c5ade1d..052d7a8 100644
--- a/tools/ahat/src/heapdump/AhatClassObj.java
+++ b/tools/ahat/src/heapdump/AhatClassObj.java
@@ -19,6 +19,7 @@
import com.android.tools.perflib.heap.ClassObj;
import com.android.tools.perflib.heap.Field;
import com.android.tools.perflib.heap.Instance;
+import java.util.AbstractList;
import java.util.Arrays;
import java.util.Collection;
import java.util.List;
@@ -34,8 +35,8 @@
super(id);
}
- @Override void initialize(AhatSnapshot snapshot, Instance inst) {
- super.initialize(snapshot, inst);
+ @Override void initialize(AhatSnapshot snapshot, Instance inst, Site site) {
+ super.initialize(snapshot, inst, site);
ClassObj classObj = (ClassObj)inst;
mClassName = classObj.getClassName();
@@ -58,13 +59,6 @@
String type = field.getKey().getType().toString();
Value value = snapshot.getValue(field.getValue());
mStaticFieldValues[index++] = new FieldValue(name, type, value);
-
- if (field.getValue() instanceof Instance) {
- Instance ref = (Instance)field.getValue();
- if (ref.getNextInstanceToGcRoot() == inst) {
- value.asAhatInstance().setNextInstanceToGcRoot(this, "." + name);
- }
- }
}
}
@@ -96,6 +90,27 @@
return Arrays.asList(mStaticFieldValues);
}
+ @Override
+ ReferenceIterator getReferences() {
+ List<Reference> refs = new AbstractList<Reference>() {
+ @Override
+ public int size() {
+ return mStaticFieldValues.length;
+ }
+
+ @Override
+ public Reference get(int index) {
+ FieldValue field = mStaticFieldValues[index];
+ Value value = field.value;
+ if (value != null && value.isAhatInstance()) {
+ return new Reference(AhatClassObj.this, "." + field.name, value.asAhatInstance(), true);
+ }
+ return null;
+ }
+ };
+ return new ReferenceIterator(refs);
+ }
+
@Override public boolean isClassObj() {
return true;
}
@@ -105,11 +120,10 @@
}
@Override public String toString() {
- return mClassName;
+ return "class " + mClassName;
}
@Override AhatInstance newPlaceHolderInstance() {
return new AhatPlaceHolderClassObj(this);
}
}
-
diff --git a/tools/ahat/src/heapdump/AhatInstance.java b/tools/ahat/src/heapdump/AhatInstance.java
index af369d9..8905b76 100644
--- a/tools/ahat/src/heapdump/AhatInstance.java
+++ b/tools/ahat/src/heapdump/AhatInstance.java
@@ -16,39 +16,48 @@
package com.android.ahat.heapdump;
+import com.android.ahat.dominators.DominatorsComputation;
import com.android.tools.perflib.heap.ClassObj;
import com.android.tools.perflib.heap.Instance;
-import com.android.tools.perflib.heap.RootObj;
import java.awt.image.BufferedImage;
import java.util.ArrayDeque;
import java.util.ArrayList;
-import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
import java.util.Deque;
import java.util.List;
+import java.util.Queue;
-public abstract class AhatInstance implements Diffable<AhatInstance> {
- private long mId;
+public abstract class AhatInstance implements Diffable<AhatInstance>,
+ DominatorsComputation.Node {
+ // The id of this instance from the heap dump.
+ private final long mId;
+
+ // Fields initialized in initialize().
private Size mSize;
- private Size[] mRetainedSizes; // Retained size indexed by heap index
- private boolean mIsReachable;
private AhatHeap mHeap;
- private AhatInstance mImmediateDominator;
- private AhatInstance mNextInstanceToGcRoot;
- private String mNextInstanceToGcRootField = "???";
private AhatClassObj mClassObj;
- private AhatInstance[] mHardReverseReferences;
- private AhatInstance[] mSoftReverseReferences;
private Site mSite;
// If this instance is a root, mRootTypes contains a set of the root types.
// If this instance is not a root, mRootTypes is null.
private List<String> mRootTypes;
- // List of instances this instance immediately dominates.
- private List<AhatInstance> mDominated = new ArrayList<AhatInstance>();
+ // Fields initialized in computeReverseReferences().
+ private AhatInstance mNextInstanceToGcRoot;
+ private String mNextInstanceToGcRootField;
+ private ArrayList<AhatInstance> mHardReverseReferences;
+ private ArrayList<AhatInstance> mSoftReverseReferences;
+ // Fields initialized in DominatorsComputation.computeDominators().
+ // mDominated - the list of instances immediately dominated by this instance.
+ // mRetainedSizes - retained size indexed by heap index.
+ private AhatInstance mImmediateDominator;
+ private List<AhatInstance> mDominated = new ArrayList<AhatInstance>();
+ private Size[] mRetainedSizes;
+ private Object mDominatorsComputationState;
+
+ // The baseline instance for purposes of diff.
private AhatInstance mBaseline;
public AhatInstance(long id) {
@@ -62,58 +71,16 @@
* There is no guarantee that the AhatInstances returned by
* snapshot.findInstance have been initialized yet.
*/
- void initialize(AhatSnapshot snapshot, Instance inst) {
- mId = inst.getId();
+ void initialize(AhatSnapshot snapshot, Instance inst, Site site) {
mSize = new Size(inst.getSize(), 0);
- mIsReachable = inst.isReachable();
-
- List<AhatHeap> heaps = snapshot.getHeaps();
-
mHeap = snapshot.getHeap(inst.getHeap().getName());
- Instance dom = inst.getImmediateDominator();
- if (dom == null || dom instanceof RootObj) {
- mImmediateDominator = null;
- } else {
- mImmediateDominator = snapshot.findInstance(dom.getId());
- mImmediateDominator.mDominated.add(this);
- }
-
ClassObj clsObj = inst.getClassObj();
if (clsObj != null) {
mClassObj = snapshot.findClassObj(clsObj.getId());
}
- // A couple notes about reverse references:
- // * perflib sometimes returns unreachable reverse references. If
- // snapshot.findInstance returns null, it means the reverse reference is
- // not reachable, so we filter it out.
- // * We store the references as AhatInstance[] instead of
- // ArrayList<AhatInstance> because it saves a lot of space and helps
- // with performance when there are a lot of AhatInstances.
- ArrayList<AhatInstance> ahatRefs = new ArrayList<AhatInstance>();
- ahatRefs = new ArrayList<AhatInstance>();
- for (Instance ref : inst.getHardReverseReferences()) {
- AhatInstance ahat = snapshot.findInstance(ref.getId());
- if (ahat != null) {
- ahatRefs.add(ahat);
- }
- }
- mHardReverseReferences = new AhatInstance[ahatRefs.size()];
- ahatRefs.toArray(mHardReverseReferences);
-
- List<Instance> refs = inst.getSoftReverseReferences();
- ahatRefs.clear();
- if (refs != null) {
- for (Instance ref : refs) {
- AhatInstance ahat = snapshot.findInstance(ref.getId());
- if (ahat != null) {
- ahatRefs.add(ahat);
- }
- }
- }
- mSoftReverseReferences = new AhatInstance[ahatRefs.size()];
- ahatRefs.toArray(mSoftReverseReferences);
+ mSite = site;
}
/**
@@ -166,7 +133,7 @@
* Returns whether this object is strongly-reachable.
*/
public boolean isReachable() {
- return mIsReachable;
+ return mImmediateDominator != null;
}
/**
@@ -177,6 +144,12 @@
}
/**
+ * Returns an iterator over the references this AhatInstance has to other
+ * AhatInstances.
+ */
+ abstract ReferenceIterator getReferences();
+
+ /**
* Returns true if this instance is marked as a root instance.
*/
public boolean isRoot() {
@@ -227,13 +200,6 @@
}
/**
- * Sets the allocation site of this instance.
- */
- void setSite(Site site) {
- mSite = site;
- }
-
- /**
* Returns true if the given instance is a class object
*/
public boolean isClassObj() {
@@ -311,14 +277,20 @@
* Returns a list of objects with hard references to this object.
*/
public List<AhatInstance> getHardReverseReferences() {
- return Arrays.asList(mHardReverseReferences);
+ if (mHardReverseReferences != null) {
+ return mHardReverseReferences;
+ }
+ return Collections.emptyList();
}
/**
* Returns a list of objects with soft references to this object.
*/
public List<AhatInstance> getSoftReverseReferences() {
- return Arrays.asList(mSoftReverseReferences);
+ if (mSoftReverseReferences != null) {
+ return mSoftReverseReferences;
+ }
+ return Collections.emptyList();
}
/**
@@ -425,8 +397,10 @@
}
void setNextInstanceToGcRoot(AhatInstance inst, String field) {
- mNextInstanceToGcRoot = inst;
- mNextInstanceToGcRootField = field;
+ if (mNextInstanceToGcRoot == null && !isRoot()) {
+ mNextInstanceToGcRoot = inst;
+ mNextInstanceToGcRootField = field;
+ }
}
/** Returns a human-readable identifier for this object.
@@ -466,6 +440,47 @@
}
/**
+ * Initialize the reverse reference fields of this instance and all other
+ * instances reachable from it. Initializes the following fields:
+ * mNextInstanceToGcRoot
+ * mNextInstanceToGcRootField
+ * mHardReverseReferences
+ * mSoftReverseReferences
+ */
+ static void computeReverseReferences(AhatInstance root) {
+ // Do a breadth first search to visit the nodes.
+ Queue<Reference> bfs = new ArrayDeque<Reference>();
+ for (Reference ref : root.getReferences()) {
+ bfs.add(ref);
+ }
+ while (!bfs.isEmpty()) {
+ Reference ref = bfs.poll();
+
+ if (ref.ref.mHardReverseReferences == null) {
+ // This is the first time we are seeing ref.ref.
+ ref.ref.mNextInstanceToGcRoot = ref.src;
+ ref.ref.mNextInstanceToGcRootField = ref.field;
+ ref.ref.mHardReverseReferences = new ArrayList<AhatInstance>();
+ for (Reference childRef : ref.ref.getReferences()) {
+ bfs.add(childRef);
+ }
+ }
+
+ // Note: ref.src is null when the src is the SuperRoot.
+ if (ref.src != null) {
+ if (ref.strong) {
+ ref.ref.mHardReverseReferences.add(ref.src);
+ } else {
+ if (ref.ref.mSoftReverseReferences == null) {
+ ref.ref.mSoftReverseReferences = new ArrayList<AhatInstance>();
+ }
+ ref.ref.mSoftReverseReferences.add(ref.src);
+ }
+ }
+ }
+ }
+
+ /**
* Recursively compute the retained size of the given instance and all
* other instances it dominates.
*/
@@ -486,8 +501,10 @@
for (int i = 0; i < numHeaps; i++) {
inst.mRetainedSizes[i] = Size.ZERO;
}
- inst.mRetainedSizes[inst.mHeap.getIndex()] =
- inst.mRetainedSizes[inst.mHeap.getIndex()].plus(inst.mSize);
+ if (!(inst instanceof SuperRoot)) {
+ inst.mRetainedSizes[inst.mHeap.getIndex()] =
+ inst.mRetainedSizes[inst.mHeap.getIndex()].plus(inst.mSize);
+ }
deque.push(inst);
for (AhatInstance dominated : inst.mDominated) {
deque.push(dominated);
@@ -501,4 +518,25 @@
}
}
}
+
+ @Override
+ public void setDominatorsComputationState(Object state) {
+ mDominatorsComputationState = state;
+ }
+
+ @Override
+ public Object getDominatorsComputationState() {
+ return mDominatorsComputationState;
+ }
+
+ @Override
+ public Iterable<? extends DominatorsComputation.Node> getReferencesForDominators() {
+ return new DominatorReferenceIterator(getReferences());
+ }
+
+ @Override
+ public void setDominator(DominatorsComputation.Node dominator) {
+ mImmediateDominator = (AhatInstance)dominator;
+ mImmediateDominator.mDominated.add(this);
+ }
}
diff --git a/tools/ahat/src/heapdump/AhatPlaceHolderInstance.java b/tools/ahat/src/heapdump/AhatPlaceHolderInstance.java
index 4aac804..d797b11 100644
--- a/tools/ahat/src/heapdump/AhatPlaceHolderInstance.java
+++ b/tools/ahat/src/heapdump/AhatPlaceHolderInstance.java
@@ -16,6 +16,9 @@
package com.android.ahat.heapdump;
+import java.util.Collections;
+import java.util.List;
+
/**
* Generic PlaceHolder instance to take the place of a real AhatInstance for
* the purposes of displaying diffs.
@@ -60,4 +63,10 @@
@Override public boolean isPlaceHolder() {
return true;
}
+
+ @Override
+ ReferenceIterator getReferences() {
+ List<Reference> refs = Collections.emptyList();
+ return new ReferenceIterator(refs);
+ }
}
diff --git a/tools/ahat/src/heapdump/AhatSnapshot.java b/tools/ahat/src/heapdump/AhatSnapshot.java
index 35d6c8a..7df78c5 100644
--- a/tools/ahat/src/heapdump/AhatSnapshot.java
+++ b/tools/ahat/src/heapdump/AhatSnapshot.java
@@ -16,6 +16,7 @@
package com.android.ahat.heapdump;
+import com.android.ahat.dominators.DominatorsComputation;
import com.android.tools.perflib.captures.DataBuffer;
import com.android.tools.perflib.captures.MemoryMappedFileBuffer;
import com.android.tools.perflib.heap.ArrayInstance;
@@ -42,7 +43,7 @@
private final Site mRootSite = new Site("ROOT");
// Collection of objects whose immediate dominator is the SENTINEL_ROOT.
- private final List<AhatInstance> mRooted = new ArrayList<AhatInstance>();
+ private final List<AhatInstance> mRooted;
// List of all ahat instances stored in increasing order by id.
private final List<AhatInstance> mInstances = new ArrayList<AhatInstance>();
@@ -80,7 +81,6 @@
*/
private AhatSnapshot(DataBuffer buffer, ProguardMap map) throws IOException {
Snapshot snapshot = Snapshot.createSnapshot(buffer, map);
- snapshot.computeDominators();
// Properly label the class of class objects in the perflib snapshot.
final ClassObj javaLangClass = snapshot.findClass("java.lang.Class");
@@ -139,46 +139,45 @@
// and instances.
for (AhatInstance ahat : mInstances) {
Instance inst = snapshot.findInstance(ahat.getId());
- ahat.initialize(this, inst);
- Long registeredNativeSize = registeredNative.get(inst);
- if (registeredNativeSize != null) {
- ahat.addRegisteredNativeSize(registeredNativeSize);
- }
-
- if (inst.getImmediateDominator() == Snapshot.SENTINEL_ROOT) {
- mRooted.add(ahat);
- }
-
- if (inst.isReachable()) {
- ahat.getHeap().addToSize(ahat.getSize());
- }
-
- // Update sites.
StackFrame[] frames = null;
StackTrace stack = inst.getStack();
if (stack != null) {
frames = stack.getFrames();
}
Site site = mRootSite.add(frames, frames == null ? 0 : frames.length, ahat);
- ahat.setSite(site);
+ ahat.initialize(this, inst, site);
+
+ Long registeredNativeSize = registeredNative.get(inst);
+ if (registeredNativeSize != null) {
+ ahat.addRegisteredNativeSize(registeredNativeSize);
+ }
}
// Record the roots and their types.
+ SuperRoot superRoot = new SuperRoot();
for (RootObj root : snapshot.getGCRoots()) {
Instance inst = root.getReferredInstance();
if (inst != null) {
- findInstance(inst.getId()).addRootType(root.getRootType().toString());
+ AhatInstance ahat = findInstance(inst.getId());
+ if (!ahat.isRoot()) {
+ superRoot.addRoot(ahat);
+ }
+ ahat.addRootType(root.getRootType().toString());
}
}
snapshot.dispose();
- // Compute the retained sizes of objects. We do this explicitly now rather
- // than relying on the retained sizes computed by perflib so that
- // registered native sizes are included.
- for (AhatInstance inst : mRooted) {
- AhatInstance.computeRetainedSize(inst, mHeaps.size());
+ AhatInstance.computeReverseReferences(superRoot);
+ DominatorsComputation.computeDominators(superRoot);
+ AhatInstance.computeRetainedSize(superRoot, mHeaps.size());
+
+ mRooted = superRoot.getDominated();
+ for (AhatHeap heap : mHeaps) {
+ heap.addToSize(superRoot.getRetainedSize(heap));
}
+
+ mRootSite.computeObjectsInfos(mHeaps.size());
}
/**
diff --git a/tools/ahat/src/heapdump/DominatorReferenceIterator.java b/tools/ahat/src/heapdump/DominatorReferenceIterator.java
new file mode 100644
index 0000000..ce2e6ef
--- /dev/null
+++ b/tools/ahat/src/heapdump/DominatorReferenceIterator.java
@@ -0,0 +1,61 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.ahat.heapdump;
+
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
+/**
+ * Reference iterator used for the dominators computation.
+ * This visits only strong references.
+ */
+class DominatorReferenceIterator implements Iterator<AhatInstance>,
+ Iterable<AhatInstance> {
+ private ReferenceIterator mIter;
+ private AhatInstance mNext;
+
+ public DominatorReferenceIterator(ReferenceIterator iter) {
+ mIter = iter;
+ mNext = null;
+ }
+
+ @Override
+ public boolean hasNext() {
+ while (mNext == null && mIter.hasNext()) {
+ Reference ref = mIter.next();
+ if (ref.strong) {
+ mNext = ref.ref;
+ }
+ }
+ return mNext != null;
+ }
+
+ @Override
+ public AhatInstance next() {
+ if (hasNext()) {
+ AhatInstance next = mNext;
+ mNext = null;
+ return next;
+ }
+ throw new NoSuchElementException();
+ }
+
+ @Override
+ public Iterator<AhatInstance> iterator() {
+ return this;
+ }
+}
diff --git a/tools/ahat/src/heapdump/Reference.java b/tools/ahat/src/heapdump/Reference.java
new file mode 100644
index 0000000..980f278
--- /dev/null
+++ b/tools/ahat/src/heapdump/Reference.java
@@ -0,0 +1,38 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.ahat.heapdump;
+
+/**
+ * Reference represents a reference from 'src' to 'ref' through 'field'.
+ * Field is a string description for human consumption. This is typically
+ * either "." followed by the field name or an array subscript such as "[4]".
+ * 'strong' is true if this is a strong reference, false if it is a
+ * weak/soft/other reference.
+ */
+public class Reference {
+ public final AhatInstance src;
+ public final String field;
+ public final AhatInstance ref;
+ public final boolean strong;
+
+ public Reference(AhatInstance src, String field, AhatInstance ref, boolean strong) {
+ this.src = src;
+ this.field = field;
+ this.ref = ref;
+ this.strong = strong;
+ }
+}
diff --git a/tools/ahat/src/heapdump/ReferenceIterator.java b/tools/ahat/src/heapdump/ReferenceIterator.java
new file mode 100644
index 0000000..a707fb2
--- /dev/null
+++ b/tools/ahat/src/heapdump/ReferenceIterator.java
@@ -0,0 +1,65 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.ahat.heapdump;
+
+import java.util.Iterator;
+import java.util.List;
+import java.util.NoSuchElementException;
+
+class ReferenceIterator implements Iterator<Reference>,
+ Iterable<Reference> {
+ private List<Reference> mRefs;
+ private int mLength;
+ private int mNextIndex;
+ private Reference mNext;
+
+ /**
+ * Construct a ReferenceIterator that iterators over the given list of
+ * references. Elements of the given list of references may be null, in
+ * which case the ReferenceIterator will skip over them.
+ */
+ public ReferenceIterator(List<Reference> refs) {
+ mRefs = refs;
+ mLength = refs.size();
+ mNextIndex = 0;
+ mNext = null;
+ }
+
+ @Override
+ public boolean hasNext() {
+ while (mNext == null && mNextIndex < mLength) {
+ mNext = mRefs.get(mNextIndex);
+ mNextIndex++;
+ }
+ return mNext != null;
+ }
+
+ @Override
+ public Reference next() {
+ if (!hasNext()) {
+ throw new NoSuchElementException();
+ }
+ Reference next = mNext;
+ mNext = null;
+ return next;
+ }
+
+ @Override
+ public Iterator<Reference> iterator() {
+ return this;
+ }
+}
diff --git a/tools/ahat/src/heapdump/Site.java b/tools/ahat/src/heapdump/Site.java
index fdd4eea..f0fc5d2 100644
--- a/tools/ahat/src/heapdump/Site.java
+++ b/tools/ahat/src/heapdump/Site.java
@@ -42,15 +42,15 @@
private int mDepth;
// The total size of objects allocated in this site (including child sites),
- // organized by heap index. Heap indices outside the range of mSizesByHeap
- // implicitly have size 0.
+ // organized by heap index. Computed as part of computeObjectsInfos.
private Size[] mSizesByHeap;
// List of child sites.
private List<Site> mChildren;
- // List of all objects allocated in this site (including child sites).
+ // List of objects allocated at this site (not including child sites).
private List<AhatInstance> mObjects;
+
private List<ObjectsInfo> mObjectsInfos;
private Map<AhatHeap, Map<AhatClassObj, ObjectsInfo>> mObjectsInfoMap;
@@ -111,7 +111,6 @@
mLineNumber = line;
mId = id;
mDepth = depth;
- mSizesByHeap = new Size[0];
mChildren = new ArrayList<Site>();
mObjects = new ArrayList<AhatInstance>();
mObjectsInfos = new ArrayList<ObjectsInfo>();
@@ -130,67 +129,102 @@
}
private static Site add(Site site, StackFrame[] frames, int depth, AhatInstance inst) {
- while (true) {
- site.mObjects.add(inst);
+ while (depth > 0) {
+ StackFrame next = frames[depth - 1];
+ Site child = null;
+ for (int i = 0; i < site.mChildren.size(); i++) {
+ Site curr = site.mChildren.get(i);
+ if (curr.mLineNumber == next.getLineNumber()
+ && curr.mMethodName.equals(next.getMethodName())
+ && curr.mSignature.equals(next.getSignature())
+ && curr.mFilename.equals(next.getFilename())) {
+ child = curr;
+ break;
+ }
+ }
+ if (child == null) {
+ child = new Site(site, next.getMethodName(), next.getSignature(),
+ next.getFilename(), next.getLineNumber(), inst.getId(), depth - 1);
+ site.mChildren.add(child);
+ }
+ depth = depth - 1;
+ site = child;
+ }
+ site.mObjects.add(inst);
+ return site;
+ }
- ObjectsInfo info = site.getObjectsInfo(inst.getHeap(), inst.getClassObj());
+ /**
+ * Recompute the ObjectsInfos for this and all child sites.
+ * This should be done after the sites tree has been formed. It should also
+ * be done after dominators computation has been performed to ensure only
+ * reachable objects are included in the ObjectsInfos.
+ *
+ * @param numHeaps - The number of heaps in the heap dump.
+ */
+ void computeObjectsInfos(int numHeaps) {
+ // Count up the total sizes by heap.
+ mSizesByHeap = new Size[numHeaps];
+ for (int i = 0; i < numHeaps; ++i) {
+ mSizesByHeap[i] = Size.ZERO;
+ }
+
+ // Add all reachable objects allocated at this site.
+ for (AhatInstance inst : mObjects) {
if (inst.isReachable()) {
AhatHeap heap = inst.getHeap();
- if (heap.getIndex() >= site.mSizesByHeap.length) {
- Size[] newSizes = new Size[heap.getIndex() + 1];
- for (int i = 0; i < site.mSizesByHeap.length; i++) {
- newSizes[i] = site.mSizesByHeap[i];
- }
- for (int i = site.mSizesByHeap.length; i < heap.getIndex() + 1; i++) {
- newSizes[i] = Size.ZERO;
- }
- site.mSizesByHeap = newSizes;
- }
- site.mSizesByHeap[heap.getIndex()]
- = site.mSizesByHeap[heap.getIndex()].plus(inst.getSize());
-
+ Size size = inst.getSize();
+ ObjectsInfo info = getObjectsInfo(heap, inst.getClassObj());
info.numInstances++;
- info.numBytes = info.numBytes.plus(inst.getSize());
+ info.numBytes = info.numBytes.plus(size);
+ mSizesByHeap[heap.getIndex()] = mSizesByHeap[heap.getIndex()].plus(size);
}
+ }
- if (depth > 0) {
- StackFrame next = frames[depth - 1];
- Site child = null;
- for (int i = 0; i < site.mChildren.size(); i++) {
- Site curr = site.mChildren.get(i);
- if (curr.mLineNumber == next.getLineNumber()
- && curr.mMethodName.equals(next.getMethodName())
- && curr.mSignature.equals(next.getSignature())
- && curr.mFilename.equals(next.getFilename())) {
- child = curr;
- break;
- }
- }
- if (child == null) {
- child = new Site(site, next.getMethodName(), next.getSignature(),
- next.getFilename(), next.getLineNumber(), inst.getId(), depth - 1);
- site.mChildren.add(child);
- }
- depth = depth - 1;
- site = child;
- } else {
- return site;
+ // Add objects allocated in child sites.
+ for (Site child : mChildren) {
+ child.computeObjectsInfos(numHeaps);
+ for (ObjectsInfo childInfo : child.mObjectsInfos) {
+ ObjectsInfo info = getObjectsInfo(childInfo.heap, childInfo.classObj);
+ info.numInstances += childInfo.numInstances;
+ info.numBytes = info.numBytes.plus(childInfo.numBytes);
+ }
+ for (int i = 0; i < numHeaps; ++i) {
+ mSizesByHeap[i] = mSizesByHeap[i].plus(child.mSizesByHeap[i]);
}
}
}
// Get the size of a site for a specific heap.
public Size getSize(AhatHeap heap) {
- int index = heap.getIndex();
- return index >= 0 && index < mSizesByHeap.length ? mSizesByHeap[index] : Size.ZERO;
+ return mSizesByHeap[heap.getIndex()];
}
/**
- * Get the list of objects allocated under this site. Includes objects
- * allocated in children sites.
+ * Collect the objects allocated under this site, optionally filtered by
+ * heap name or class name. Includes objects allocated in children sites.
+ * @param heapName - The name of the heap the collected objects should
+ * belong to. This may be null to indicate objects of
+ * every heap should be collected.
+ * @param className - The name of the class the collected objects should
+ * belong to. This may be null to indicate objects of
+ * every class should be collected.
+ * @param objects - Out parameter. A collection of objects that all
+ * collected objects should be added to.
*/
- public Collection<AhatInstance> getObjects() {
- return mObjects;
+ public void getObjects(String heapName, String className, Collection<AhatInstance> objects) {
+ for (AhatInstance inst : mObjects) {
+ if ((heapName == null || inst.getHeap().getName().equals(heapName))
+ && (className == null || inst.getClassName().equals(className))) {
+ objects.add(inst);
+ }
+ }
+
+ // Recursively visit children. Recursion should be okay here because the
+ // stack depth is limited by a reasonable amount (128 frames or so).
+ for (Site child : mChildren) {
+ child.getObjects(heapName, className, objects);
+ }
}
/**
@@ -220,8 +254,8 @@
// Get the combined size of the site for all heaps.
public Size getTotalSize() {
Size total = Size.ZERO;
- for (int i = 0; i < mSizesByHeap.length; i++) {
- total = total.plus(mSizesByHeap[i]);
+ for (Size size : mSizesByHeap) {
+ total = total.plus(size);
}
return total;
}
diff --git a/tools/ahat/src/heapdump/SuperRoot.java b/tools/ahat/src/heapdump/SuperRoot.java
new file mode 100644
index 0000000..54410cf
--- /dev/null
+++ b/tools/ahat/src/heapdump/SuperRoot.java
@@ -0,0 +1,57 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.ahat.heapdump;
+
+import com.android.ahat.dominators.DominatorsComputation;
+import java.util.AbstractList;
+import java.util.ArrayList;
+import java.util.List;
+
+public class SuperRoot extends AhatInstance implements DominatorsComputation.Node {
+ private List<AhatInstance> mRoots = new ArrayList<AhatInstance>();
+ private Object mDominatorsComputationState;
+
+ public SuperRoot() {
+ super(0);
+ }
+
+ public void addRoot(AhatInstance root) {
+ mRoots.add(root);
+ }
+
+ @Override
+ public String toString() {
+ return "SUPER_ROOT";
+ }
+
+ @Override
+ ReferenceIterator getReferences() {
+ List<Reference> refs = new AbstractList<Reference>() {
+ @Override
+ public int size() {
+ return mRoots.size();
+ }
+
+ @Override
+ public Reference get(int index) {
+ String field = ".roots[" + Integer.toString(index) + "]";
+ return new Reference(null, field, mRoots.get(index), true);
+ }
+ };
+ return new ReferenceIterator(refs);
+ }
+}
diff --git a/tools/ahat/test-dump/Main.java b/tools/ahat/test-dump/Main.java
index 3d3de78..13fd102 100644
--- a/tools/ahat/test-dump/Main.java
+++ b/tools/ahat/test-dump/Main.java
@@ -60,6 +60,14 @@
public StackSmasher child;
}
+ public static class Reference {
+ public Object referent;
+
+ public Reference(Object referent) {
+ this.referent = referent;
+ }
+ }
+
// We will take a heap dump that includes a single instance of this
// DumpedStuff class. Objects stored as fields in this class can be easily
// found in the hprof dump by searching for the instance of the DumpedStuff
@@ -71,6 +79,7 @@
public char[] charArray = "char thing".toCharArray();
public String nullString = null;
public Object anObject = new Object();
+ public Reference aReference = new Reference(anObject);
public ReferenceQueue<Object> referenceQueue = new ReferenceQueue<Object>();
public PhantomReference aPhantomReference = new PhantomReference(anObject, referenceQueue);
public WeakReference aWeakReference = new WeakReference(anObject, referenceQueue);
diff --git a/tools/ahat/test/DominatorsTest.java b/tools/ahat/test/DominatorsTest.java
new file mode 100644
index 0000000..0424e10
--- /dev/null
+++ b/tools/ahat/test/DominatorsTest.java
@@ -0,0 +1,298 @@
+/*
+ * Copyright (C) 2017 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.ahat;
+
+import com.android.ahat.dominators.DominatorsComputation;
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.List;
+import org.junit.Test;
+import static org.junit.Assert.assertEquals;
+
+public class DominatorsTest {
+ private static class Node implements DominatorsComputation.Node {
+ public String name;
+ public List<Node> depends = new ArrayList<Node>();
+ public Node dominator;
+ private Object dominatorsComputationState;
+
+ public Node(String name) {
+ this.name = name;
+ }
+
+ public void computeDominators() {
+ DominatorsComputation.computeDominators(this);
+ }
+
+ public String toString() {
+ return name;
+ }
+
+ @Override
+ public void setDominatorsComputationState(Object state) {
+ dominatorsComputationState = state;
+ }
+
+ @Override
+ public Object getDominatorsComputationState() {
+ return dominatorsComputationState;
+ }
+
+ @Override
+ public Collection<Node> getReferencesForDominators() {
+ return depends;
+ }
+
+ @Override
+ public void setDominator(DominatorsComputation.Node dominator) {
+ this.dominator = (Node)dominator;
+ }
+ }
+
+ @Test
+ public void singleNode() {
+ // --> n
+ // Trivial case.
+ Node n = new Node("n");
+ n.computeDominators();
+ }
+
+ @Test
+ public void parentWithChild() {
+ // --> parent --> child
+ // The child node is dominated by the parent.
+ Node parent = new Node("parent");
+ Node child = new Node("child");
+ parent.depends = Arrays.asList(child);
+
+ parent.computeDominators();
+ assertEquals(parent, child.dominator);
+ }
+
+ @Test
+ public void reachableTwoWays() {
+ // /-> right -->\
+ // --> parent child
+ // \-> left --->/
+ // The child node can be reached either by right or by left.
+ Node parent = new Node("parent");
+ Node right = new Node("right");
+ Node left = new Node("left");
+ Node child = new Node("child");
+ parent.depends = Arrays.asList(left, right);
+ right.depends = Arrays.asList(child);
+ left.depends = Arrays.asList(child);
+
+ parent.computeDominators();
+ assertEquals(parent, left.dominator);
+ assertEquals(parent, right.dominator);
+ assertEquals(parent, child.dominator);
+ }
+
+ @Test
+ public void reachableDirectAndIndirect() {
+ // /-> right -->\
+ // --> parent -----------> child
+ // The child node can be reached either by right or parent.
+ Node parent = new Node("parent");
+ Node right = new Node("right");
+ Node child = new Node("child");
+ parent.depends = Arrays.asList(right, child);
+ right.depends = Arrays.asList(child);
+
+ parent.computeDominators();
+ assertEquals(parent, child.dominator);
+ assertEquals(parent, right.dominator);
+ }
+
+ @Test
+ public void subDominator() {
+ // --> parent --> middle --> child
+ // The child is dominated by an internal node.
+ Node parent = new Node("parent");
+ Node middle = new Node("middle");
+ Node child = new Node("child");
+ parent.depends = Arrays.asList(middle);
+ middle.depends = Arrays.asList(child);
+
+ parent.computeDominators();
+ assertEquals(parent, middle.dominator);
+ assertEquals(middle, child.dominator);
+ }
+
+ @Test
+ public void childSelfLoop() {
+ // --> parent --> child -\
+ // \<---/
+ // The child points back to itself.
+ Node parent = new Node("parent");
+ Node child = new Node("child");
+ parent.depends = Arrays.asList(child);
+ child.depends = Arrays.asList(child);
+
+ parent.computeDominators();
+ assertEquals(parent, child.dominator);
+ }
+
+ @Test
+ public void singleEntryLoop() {
+ // --> parent --> a --> b --> c -\
+ // \<------------/
+ // There is a loop in the graph, with only one way into the loop.
+ Node parent = new Node("parent");
+ Node a = new Node("a");
+ Node b = new Node("b");
+ Node c = new Node("c");
+ parent.depends = Arrays.asList(a);
+ a.depends = Arrays.asList(b);
+ b.depends = Arrays.asList(c);
+ c.depends = Arrays.asList(a);
+
+ parent.computeDominators();
+ assertEquals(parent, a.dominator);
+ assertEquals(a, b.dominator);
+ assertEquals(b, c.dominator);
+ }
+
+ @Test
+ public void multiEntryLoop() {
+ // --> parent --> right --> a --> b ----\
+ // \ \<-- c <---/
+ // \--> left --->--------/
+ // There is a loop in the graph, with two different ways to enter the
+ // loop.
+ Node parent = new Node("parent");
+ Node left = new Node("left");
+ Node right = new Node("right");
+ Node a = new Node("a");
+ Node b = new Node("b");
+ Node c = new Node("c");
+ parent.depends = Arrays.asList(left, right);
+ right.depends = Arrays.asList(a);
+ left.depends = Arrays.asList(c);
+ a.depends = Arrays.asList(b);
+ b.depends = Arrays.asList(c);
+ c.depends = Arrays.asList(a);
+
+ parent.computeDominators();
+ assertEquals(parent, right.dominator);
+ assertEquals(parent, left.dominator);
+ assertEquals(parent, a.dominator);
+ assertEquals(parent, c.dominator);
+ assertEquals(a, b.dominator);
+ }
+
+ @Test
+ public void dominatorOverwrite() {
+ // /---------> right <--\
+ // --> parent --> child <--/ /
+ // \---> left ---------/
+ // Test a strange case where we have had trouble in the past with a
+ // dominator getting improperly overwritten. The relevant features of this
+ // case are: 'child' is visited after 'right', 'child' is dominated by
+ // 'parent', and 'parent' revisits 'right' after visiting 'child'.
+ Node parent = new Node("parent");
+ Node right = new Node("right");
+ Node left = new Node("left");
+ Node child = new Node("child");
+ parent.depends = Arrays.asList(left, child, right);
+ left.depends = Arrays.asList(right);
+ right.depends = Arrays.asList(child);
+
+ parent.computeDominators();
+ assertEquals(parent, left.dominator);
+ assertEquals(parent, child.dominator);
+ assertEquals(parent, right.dominator);
+ }
+
+ @Test
+ public void stackOverflow() {
+ // --> a --> b --> ... --> N
+ // Verify we don't smash the stack for deep chains.
+ Node root = new Node("root");
+ Node curr = root;
+ for (int i = 0; i < 10000; ++i) {
+ Node node = new Node("n" + i);
+ curr.depends.add(node);
+ curr = node;
+ }
+
+ root.computeDominators();
+ }
+
+ @Test
+ public void hiddenRevisit() {
+ // /-> left ---->---------\
+ // --> parent \---> a --> b --> c
+ // \-> right -/
+ // Test a case we have had trouble in the past.
+ // When a's dominator is updated from left to parent, that should trigger
+ // all reachable children's dominators to be updated too. In particular,
+ // c's dominator should be updated, even though b's dominator is
+ // unchanged.
+ Node parent = new Node("parent");
+ Node right = new Node("right");
+ Node left = new Node("left");
+ Node a = new Node("a");
+ Node b = new Node("b");
+ Node c = new Node("c");
+ parent.depends = Arrays.asList(right, left);
+ left.depends = Arrays.asList(a, c);
+ right.depends = Arrays.asList(a);
+ a.depends = Arrays.asList(b);
+ b.depends = Arrays.asList(c);
+
+ parent.computeDominators();
+ assertEquals(parent, left.dominator);
+ assertEquals(parent, right.dominator);
+ assertEquals(parent, a.dominator);
+ assertEquals(parent, c.dominator);
+ assertEquals(a, b.dominator);
+ }
+
+ @Test
+ public void preUndominatedUpdate() {
+ // /--------->--------\
+ // / /---->----\
+ // --> p -> a --> b --> c --> d --> e
+ // \---------->----------/
+ // Test a case we have had trouble in the past.
+ // The candidate dominator for e is revised from d to a, then d is shown
+ // to be reachable from p. Make sure that causes e's dominator to be
+ // refined again from a to p. The extra nodes are there to ensure the
+ // necessary scheduling to expose the bug we had.
+ Node p = new Node("p");
+ Node a = new Node("a");
+ Node b = new Node("b");
+ Node c = new Node("c");
+ Node d = new Node("d");
+ Node e = new Node("e");
+ p.depends = Arrays.asList(d, a);
+ a.depends = Arrays.asList(e, b);
+ b.depends = Arrays.asList(d, c);
+ c.depends = Arrays.asList(d);
+ d.depends = Arrays.asList(e);
+
+ p.computeDominators();
+ assertEquals(p, a.dominator);
+ assertEquals(a, b.dominator);
+ assertEquals(b, c.dominator);
+ assertEquals(p, d.dominator);
+ assertEquals(p, e.dominator);
+ }
+}
diff --git a/tools/ahat/test/InstanceTest.java b/tools/ahat/test/InstanceTest.java
index 71b081c..f0e7f44 100644
--- a/tools/ahat/test/InstanceTest.java
+++ b/tools/ahat/test/InstanceTest.java
@@ -337,7 +337,7 @@
public void classObjToString() throws IOException {
TestDump dump = TestDump.getTestDump();
AhatInstance obj = dump.getAhatSnapshot().findClass("Main");
- assertEquals("Main", obj.toString());
+ assertEquals("class Main", obj.toString());
}
@Test
@@ -370,6 +370,18 @@
}
@Test
+ public void reverseReferences() throws IOException {
+ TestDump dump = TestDump.getTestDump();
+ AhatInstance obj = dump.getDumpedAhatInstance("anObject");
+ AhatInstance ref = dump.getDumpedAhatInstance("aReference");
+ AhatInstance weak = dump.getDumpedAhatInstance("aWeakReference");
+ assertTrue(obj.getHardReverseReferences().contains(ref));
+ assertFalse(obj.getHardReverseReferences().contains(weak));
+ assertFalse(obj.getSoftReverseReferences().contains(ref));
+ assertTrue(obj.getSoftReverseReferences().contains(weak));
+ }
+
+ @Test
public void asStringEmbedded() throws IOException {
// Set up a heap dump with an instance of java.lang.String of
// "hello" with instance id 0x42 that is backed by a char array that is
diff --git a/tools/ahat/test/Tests.java b/tools/ahat/test/Tests.java
index a95788e..a1e3246 100644
--- a/tools/ahat/test/Tests.java
+++ b/tools/ahat/test/Tests.java
@@ -24,6 +24,7 @@
args = new String[]{
"com.android.ahat.DiffFieldsTest",
"com.android.ahat.DiffTest",
+ "com.android.ahat.DominatorsTest",
"com.android.ahat.InstanceTest",
"com.android.ahat.NativeAllocationTest",
"com.android.ahat.ObjectHandlerTest",