Fix bugs with strong versus weak reference paths.

This fixes a few issues with strong versus weak reference paths:
* It was possible to have a path from gc root with a root in the
  middle of the path.
* It was possible to have a path from gc root with a cycle, which
  would cause ahat to go into an infinite loop.
* It was still possible to have a path from gc root through weak
  references when there existed other paths from gc root only through
  strong references.

Bug: 64592321

Test: m ahat-test, with new tests added.
Change-Id: I2d3cc8c5a398aad24d70c3a428bdc3a470ddb3aa

4 files changed, 101 insertions, 34 deletions

diff --git a/tools/ahat/src/main/com/android/ahat/heapdump/AhatInstance.java b/tools/ahat/src/main/com/android/ahat/heapdump/AhatInstance.java
index cb2d738f23..1a3d127fc9 100644
--- a/tools/ahat/src/main/com/android/ahat/heapdump/AhatInstance.java
+++ b/tools/ahat/src/main/com/android/ahat/heapdump/AhatInstance.java
@@ -428,8 +428,7 @@ public abstract class AhatInstance implements Diffable<AhatInstance>,
    * Returns null if the given instance has no next instance to the gc root.
    */
   private static PathElement getNextPathElementToGcRoot(AhatInstance inst) {
-    AhatInstance parent = inst.mNextInstanceToGcRoot;
-    if (parent == null) {
+    if (inst.isRoot()) {
       return null;
     }
     return new PathElement(inst.mNextInstanceToGcRoot, inst.mNextInstanceToGcRootField);
@@ -487,40 +486,64 @@ public abstract class AhatInstance implements Diffable<AhatInstance>,
    *   mHardReverseReferences
    *   mSoftReverseReferences
    */
-  static void computeReverseReferences(AhatInstance root) {
-    // Do a breadth first search to visit the nodes.
-    Queue<Reference> bfs = new ArrayDeque<Reference>();
+  static void computeReverseReferences(SuperRoot root) {
+    // Start by doing a breadth first search through strong references.
+    // Then continue the breadth first search through weak references.
+    Queue<Reference> strong = new ArrayDeque<Reference>();
+    Queue<Reference> weak = new ArrayDeque<Reference>();
+
     for (Reference ref : root.getReferences()) {
-      bfs.add(ref);
+      strong.add(ref);
     }
-    while (!bfs.isEmpty()) {
-      Reference ref = bfs.poll();
 
-      if (ref.ref.mHardReverseReferences == null && ref.strong) {
-        // This is the first time we are seeing ref.ref through a strong
-        // reference.
+    while (!strong.isEmpty()) {
+      Reference ref = strong.poll();
+      assert ref.strong;
+
+      if (ref.ref.mNextInstanceToGcRoot == null) {
+        // This is the first time we have seen 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);
+          if (childRef.strong) {
+            strong.add(childRef);
+          } else {
+            weak.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>();
-            if (ref.ref.mNextInstanceToGcRoot == null) {
-              ref.ref.mNextInstanceToGcRoot = ref.src;
-              ref.ref.mNextInstanceToGcRootField = ref.field;
-            }
-          }
-          ref.ref.mSoftReverseReferences.add(ref.src);
+      // Note: We specifically exclude 'root' from the reverse references
+      // because it is a fake SuperRoot instance not present in the original
+      // heap dump.
+      if (ref.src != root) {
+        ref.ref.mHardReverseReferences.add(ref.src);
+      }
+    }
+
+    while (!weak.isEmpty()) {
+      Reference ref = weak.poll();
+
+      if (ref.ref.mNextInstanceToGcRoot == null) {
+        // This is the first time we have seen ref.ref.
+        ref.ref.mNextInstanceToGcRoot = ref.src;
+        ref.ref.mNextInstanceToGcRootField = ref.field;
+        ref.ref.mHardReverseReferences = new ArrayList<AhatInstance>();
+
+        for (Reference childRef : ref.ref.getReferences()) {
+          weak.add(childRef);
+        }
+      }
+
+      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);
       }
     }
   }
diff --git a/tools/ahat/src/main/com/android/ahat/heapdump/SuperRoot.java b/tools/ahat/src/main/com/android/ahat/heapdump/SuperRoot.java
index a2adbd2808..5210e31167 100644
--- a/tools/ahat/src/main/com/android/ahat/heapdump/SuperRoot.java
+++ b/tools/ahat/src/main/com/android/ahat/heapdump/SuperRoot.java
@@ -54,7 +54,7 @@ public class SuperRoot extends AhatInstance implements DominatorsComputation.Nod
       @Override
       public Reference get(int index) {
         String field = ".roots[" + Integer.toString(index) + "]";
-        return new Reference(null, field, mRoots.get(index), true);
+        return new Reference(SuperRoot.this, field, mRoots.get(index), true);
       }
     };
   }
diff --git a/tools/ahat/src/test-dump/Main.java b/tools/ahat/src/test-dump/Main.java
index 333d28c214..079be7da81 100644
--- a/tools/ahat/src/test-dump/Main.java
+++ b/tools/ahat/src/test-dump/Main.java
@@ -93,6 +93,8 @@ public class Main {
       null};
     public Reference aLongStrongPathToSamplePathObject;
     public WeakReference aShortWeakPathToSamplePathObject;
+    public WeakReference aWeakRefToGcRoot = new WeakReference(Main.class);
+    public SoftReference aWeakChain = new SoftReference(new Reference(new Reference(new Object())));
     public Object[] basicStringRef;
     public AddedObject addedObject;
     public UnchangedObject unchangedObject = new UnchangedObject();
@@ -126,10 +128,11 @@ public class Main {
           Main.class.getClassLoader(), 0x12345, 50000);
       registry.registerNativeAllocation(anObject, 0xABCDABCD);
 
-      aLongStrongPathToSamplePathObject = new Reference(new Reference(new Object()));
-      aShortWeakPathToSamplePathObject = new WeakReference(
-          ((Reference)aLongStrongPathToSamplePathObject.referent).referent,
-          referenceQueue);
+      {
+        Object object = new Object();
+        aLongStrongPathToSamplePathObject = new Reference(new Reference(new Reference(object)));
+        aShortWeakPathToSamplePathObject = new WeakReference(new Reference(object));
+      }
 
       addedObject = baseline ? null : new AddedObject();
       removedObject = baseline ? new RemovedObject() : null;
diff --git a/tools/ahat/src/test/com/android/ahat/InstanceTest.java b/tools/ahat/src/test/com/android/ahat/InstanceTest.java
index a4908fd0ab..8fbb8849f0 100644
--- a/tools/ahat/src/test/com/android/ahat/InstanceTest.java
+++ b/tools/ahat/src/test/com/android/ahat/InstanceTest.java
@@ -274,12 +274,20 @@ public class InstanceTest {
   public void gcRootPathNotWeak() throws IOException {
     TestDump dump = TestDump.getTestDump();
 
-    AhatInstance strong = dump.getDumpedAhatInstance("aLongStrongPathToSamplePathObject");
-    AhatInstance strong2 = strong.getField("referent").asAhatInstance();
-    AhatInstance object = strong2.getField("referent").asAhatInstance();
+    // The test dump is set up to have the following graph:
+    //  -S-> strong1 -S-> strong2 -S-> strong3 -S-> object
+    //  -S-> weak1 -W-> weak2 ------------------S->-/
+    // The gc root path should go through the longer chain of strong
+    // references, not the shorter chain with weak references (even though the
+    // last element in the shorter chain is a strong reference).
+
+    AhatInstance strong1 = dump.getDumpedAhatInstance("aLongStrongPathToSamplePathObject");
+    AhatInstance strong2 = strong1.getField("referent").asAhatInstance();
+    AhatInstance strong3 = strong2.getField("referent").asAhatInstance();
+    AhatInstance object = strong3.getField("referent").asAhatInstance();
 
     List<PathElement> path = object.getPathFromGcRoot();
-    assertEquals(strong2, path.get(path.size() - 2).instance);
+    assertEquals(strong3, path.get(path.size() - 2).instance);
   }
 
   @Test
@@ -368,6 +376,39 @@ public class InstanceTest {
   }
 
   @Test
+  public void weakRefToGcRoot() throws IOException {
+    TestDump dump = TestDump.getTestDump();
+    AhatInstance ref = dump.getDumpedAhatInstance("aWeakRefToGcRoot");
+
+    // The weak reference points to Main.class, which we expect will be marked
+    // as a GC root. In theory Main.class doesn't have to be a GC root, in
+    // which case this test case will need to be revised.
+    AhatInstance root = ref.getField("referent").asAhatInstance();
+    assertTrue(root.isRoot());
+
+    // We had a bug in the past where weak references to GC roots caused the
+    // roots to be incorrectly be considered weakly reachable.
+    assertTrue(root.isStronglyReachable());
+    assertFalse(root.isWeaklyReachable());
+  }
+
+  @Test
+  public void weakReferenceChain() throws IOException {
+    // If the only reference to a chain of strongly referenced objects is a
+    // weak reference, then all of the objects should be considered weakly
+    // reachable.
+    TestDump dump = TestDump.getTestDump();
+    AhatInstance ref = dump.getDumpedAhatInstance("aWeakChain");
+    AhatInstance weak1 = ref.getField("referent").asAhatInstance();
+    AhatInstance weak2 = weak1.getField("referent").asAhatInstance();
+    AhatInstance weak3 = weak2.getField("referent").asAhatInstance();
+    assertTrue(ref.isStronglyReachable());
+    assertTrue(weak1.isWeaklyReachable());
+    assertTrue(weak2.isWeaklyReachable());
+    assertTrue(weak3.isWeaklyReachable());
+  }
+
+  @Test
   public void reverseReferences() throws IOException {
     TestDump dump = TestDump.getTestDump();
     AhatInstance obj = dump.getDumpedAhatInstance("anObject");