test/913-heaps/src/art/Test913.java - LeafOS-Project/android_art - Gitiles

 /*
  * Copyright (C) 2016 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 art;

 import java.io.BufferedReader;
 import java.io.File;
 import java.io.FileReader;
 import java.util.ArrayList;
 import java.util.Arrays;
 import java.util.Collections;
 import java.util.HashMap;
 import java.util.HashSet;
 import java.util.concurrent.CountDownLatch;

 public class Test913 {
   public static void run() throws Exception {
     doTest();

     // Use a countdown latch for synchronization, as join() will introduce more roots.
     final CountDownLatch cdl1 = new CountDownLatch(1);

     // Run the follow-references tests on a dedicated thread so we know the specific Thread type.
     Thread t = new Thread() {
       @Override
       public void run() {
         try {
           Test913.runFollowReferences();
         } catch (Exception e) {
           throw new RuntimeException(e);
         }
         cdl1.countDown();
       }
     };
     t.start();
     cdl1.await();

     doExtensionTests();
   }

   public static void runFollowReferences() throws Exception {
     new TestConfig().doFollowReferencesTest();

     Runtime.getRuntime().gc();
     Runtime.getRuntime().gc();

     new TestConfig(null, 0, 1, -1).doFollowReferencesTest();

     Runtime.getRuntime().gc();
     Runtime.getRuntime().gc();

     new TestConfig(null, 0, Integer.MAX_VALUE, 1).doFollowReferencesTest();

     Runtime.getRuntime().gc();
     Runtime.getRuntime().gc();

     doStringTest();

     Runtime.getRuntime().gc();
     Runtime.getRuntime().gc();

     doPrimitiveArrayTest();
     doPrimitiveFieldTest();

     Runtime.getRuntime().gc();
     Runtime.getRuntime().gc();

     // Test klass filter.
     System.out.println("--- klass ---");
     new TestConfig(A.class, 0).doFollowReferencesTest();

     // Test heap filter.
     System.out.println("--- heap_filter ---");
     System.out.println("---- tagged objects");
     new TestConfig(null, 0x4).doFollowReferencesTest();
     System.out.println("---- untagged objects");
     new TestConfig(null, 0x8).doFollowReferencesTest();
     System.out.println("---- tagged classes");
     new TestConfig(null, 0x10).doFollowReferencesTest();
     System.out.println("---- untagged classes");
     new TestConfig(null, 0x20).doFollowReferencesTest();
   }

   public static void doTest() throws Exception {
     setupGcCallback();

     enableGcTracking(true);
     runGc();
     enableGcTracking(false);
   }

   public static void doStringTest() throws Exception {
     final String str = new String("HelloWorld");
     final String str2 = new String("");
     Object o = new Object() {
       String s = str;
       String s2 = str2;
     };

     setTag(str, 1);
     setTag(str2, 2);
     System.out.println(Arrays.toString(followReferencesString(o)));
     System.out.println(getTag(str));
     System.out.println(getTag(str2));
   }

   public static void doPrimitiveArrayTest() throws Exception {
     final boolean[] zArray = new boolean[] { false, true };
     setTag(zArray, 1);

     final byte[] bArray = new byte[] { 1, 2, 3 };
     setTag(bArray, 2);

     final char[] cArray = new char[] { 'A', 'Z' };
     setTag(cArray, 3);

     final short[] sArray = new short[] { 1, 2, 3 };
     setTag(sArray, 4);

     final int[] iArray = new int[] { 1, 2, 3 };
     setTag(iArray, 5);

     final float[] fArray = new float[] { 0.0f, 1.0f };
     setTag(fArray, 6);

     final long[] lArray = new long[] { 1, 2, 3 };
     setTag(lArray, 7);

     final double[] dArray = new double[] { 0.0, 1.0 };
     setTag(dArray, 8);

     Object o = new Object() {
       Object z = zArray;
       Object b = bArray;
       Object c = cArray;
       Object s = sArray;
       Object i = iArray;
       Object f = fArray;
       Object l = lArray;
       Object d = dArray;
     };

     System.out.println(followReferencesPrimitiveArray(o));
     System.out.print(getTag(zArray));
     System.out.print(getTag(bArray));
     System.out.print(getTag(cArray));
     System.out.print(getTag(sArray));
     System.out.print(getTag(iArray));
     System.out.print(getTag(fArray));
     System.out.print(getTag(lArray));
     System.out.println(getTag(dArray));
   }

   public static void doPrimitiveFieldTest() throws Exception {
     // Force GCs to clean up dirt.
     Runtime.getRuntime().gc();
     Runtime.getRuntime().gc();

     doTestPrimitiveFieldsClasses();

     doTestPrimitiveFieldsIntegral();

     // Force GCs to clean up dirt.
     Runtime.getRuntime().gc();
     Runtime.getRuntime().gc();

     doTestPrimitiveFieldsFloat();

     // Force GCs to clean up dirt.
     Runtime.getRuntime().gc();
     Runtime.getRuntime().gc();
   }

   private static void doTestPrimitiveFieldsClasses() {
     setTag(IntObject.class, 10000);
     System.out.println(followReferencesPrimitiveFields(IntObject.class));
     System.out.println(getTag(IntObject.class));
     setTag(IntObject.class, 0);

     setTag(FloatObject.class, 10000);
     System.out.println(followReferencesPrimitiveFields(FloatObject.class));
     System.out.println(getTag(FloatObject.class));
     setTag(FloatObject.class, 0);

     boolean correctHeapValue = false;
     setTag(Inf1.class, 10000);
     String heapTrace = followReferencesPrimitiveFields(Inf1.class);

     if (!checkInitialized(Inf1.class)) {
       correctHeapValue = heapTrace.equals("10000@0 (static, int, index=0) 0000000000000000");
     } else {
       correctHeapValue = heapTrace.equals("10000@0 (static, int, index=0) 0000000000000001");
     }

     if (!correctHeapValue)
       System.out.println("Heap Trace for Inf1 is not as expected:\n" + heapTrace);

     System.out.println(getTag(Inf1.class));
     setTag(Inf1.class, 0);

     setTag(Inf2.class, 10000);
     heapTrace = followReferencesPrimitiveFields(Inf2.class);

     if (!checkInitialized(Inf2.class)) {
       correctHeapValue = heapTrace.equals("10000@0 (static, int, index=1) 0000000000000000");
     } else {
       correctHeapValue = heapTrace.equals("10000@0 (static, int, index=1) 0000000000000001");
     }

     if (!correctHeapValue)
       System.out.println("Heap Trace for Inf2 is not as expected:\n" + heapTrace);
     System.out.println(getTag(Inf2.class));
     setTag(Inf2.class, 0);
   }

   private static void doTestPrimitiveFieldsIntegral() {
     IntObject intObject = new IntObject();
     setTag(intObject, 10000);
     System.out.println(followReferencesPrimitiveFields(intObject));
     System.out.println(getTag(intObject));
   }

   private static void doTestPrimitiveFieldsFloat() {
     FloatObject floatObject = new FloatObject();
     setTag(floatObject, 10000);
     System.out.println(followReferencesPrimitiveFields(floatObject));
     System.out.println(getTag(floatObject));
   }

   static ArrayList<Object> extensionTestHolder;

   private static void doExtensionTests() {
     checkForExtensionApis();

     extensionTestHolder = new ArrayList<>();
     System.out.println();

     try {
       getHeapName(-1);
       System.out.println("Expected failure for -1");
     } catch (Exception e) {
     }
     System.out.println(getHeapName(0));
     System.out.println(getHeapName(1));
     System.out.println(getHeapName(2));
     System.out.println(getHeapName(3));
     try {
       getHeapName(4);
       System.out.println("Expected failure for -1");
     } catch (Exception e) {
     }

     System.out.println();

     setTag(Object.class, 100000);
     int objectClassHeapId = getObjectHeapId(100000);
     int objClassExpectedHeapId = hasImage() ? 1 : 3;
     if (objectClassHeapId != objClassExpectedHeapId) {
       throw new RuntimeException("Expected object class in heap " + objClassExpectedHeapId +
           " but received " + objectClassHeapId);
     }

     A a = new A();
     extensionTestHolder.add(a);
     setTag(a, 100001);
     System.out.println(getObjectHeapId(100001));

     checkGetObjectHeapIdInCallback(100000, objClassExpectedHeapId);
     checkGetObjectHeapIdInCallback(100001, 3);

     long baseTag = 30000000;
     setTag(Object.class, baseTag + objClassExpectedHeapId);
     setTag(Class.class, baseTag + objClassExpectedHeapId);
     Object o = new Object();
     extensionTestHolder.add(o);
     setTag(o, baseTag + 3);

     iterateThroughHeapExt();

     extensionTestHolder = null;
   }

   private static void runGc() {
     clearStats();
     forceGarbageCollection();
     printStats();
   }

   private static void clearStats() {
     getGcStarts();
     getGcFinishes();
   }

   private static void printStats() {
     System.out.println("---");
     int s = getGcStarts();
     int f = getGcFinishes();
     System.out.println((s > 0) + " " + (f > 0));
   }

   private static boolean hasImage() {
     try {
       int pid = Integer.parseInt(new File("/proc/self").getCanonicalFile().getName());
       BufferedReader reader = new BufferedReader(new FileReader("/proc/" + pid + "/maps"));
       String line;
       while ((line = reader.readLine()) != null) {
         // On host the mappings end with .art and on device they end with .art]
         if (line.endsWith(".art]") || line.endsWith(".art")) {
           reader.close();
           return true;
         }
       }
       reader.close();
       return false;
     } catch (Exception e) {
       throw new RuntimeException(e);
     }
   }

   private static class TestConfig {
     private Class<?> klass = null;
     private int heapFilter = 0;
     private int stopAfter = Integer.MAX_VALUE;
     private int followSet = -1;

     public TestConfig() {
     }
     public TestConfig(Class<?> klass, int heapFilter) {
       this.klass = klass;
       this.heapFilter = heapFilter;
     }
     public TestConfig(Class<?> klass, int heapFilter, int stopAfter, int followSet) {
       this.klass = klass;
       this.heapFilter = heapFilter;
       this.stopAfter = stopAfter;
       this.followSet = followSet;
     }

     public void doFollowReferencesTest() throws Exception {
       // Force GCs to clean up dirt.
       Runtime.getRuntime().gc();
       Runtime.getRuntime().gc();

       setTag(Thread.currentThread(), 3000);

       {
         ArrayList<Object> tmpStorage = new ArrayList<>();
         doFollowReferencesTestNonRoot(tmpStorage);
         tmpStorage = null;
       }

       // Force GCs to clean up dirt.
       Runtime.getRuntime().gc();
       Runtime.getRuntime().gc();

       doFollowReferencesTestRoot();

       // Force GCs to clean up dirt.
       Runtime.getRuntime().gc();
       Runtime.getRuntime().gc();
     }

     private void doFollowReferencesTestNonRoot(ArrayList<Object> tmpStorage) {
       Verifier v = new Verifier();
       tagClasses(v);
       A a = createTree(v);
       tmpStorage.add(a);
       v.add("0@0", "1@1000");  // tmpStorage[0] --(array-element)--> a.

       doFollowReferencesTestImpl(null, stopAfter, followSet, null, v, null);
       doFollowReferencesTestImpl(a.foo2, stopAfter, followSet, null, v, "3@1001");

       tmpStorage.clear();
     }

     private void doFollowReferencesTestRoot() {
       Verifier v = new Verifier();
       tagClasses(v);
       A a = createTree(v);

       doFollowReferencesTestImpl(null, stopAfter, followSet, a, v, null);
       doFollowReferencesTestImpl(a.foo2, stopAfter, followSet, a, v, "3@1001");
     }

     private void doFollowReferencesTestImpl(A root, int stopAfter, int followSet,
         Object asRoot, Verifier v, String additionalEnabled) {
       String[] lines =
           followReferences(heapFilter, klass, root, stopAfter, followSet, asRoot);

       v.process(lines, additionalEnabled, heapFilter != 0 || klass != null);
     }

     private static void tagClasses(Verifier v) {
       setTag(A.class, 1000);
       registerClass(1000, A.class);

       setTag(B.class, 1001);
       registerClass(1001, B.class);
       v.add("1001@0", "1000@0");  // B.class --(superclass)--> A.class.

       setTag(C.class, 1002);
       registerClass(1002, C.class);
       v.add("1002@0", "1001@0");  // C.class --(superclass)--> B.class.
       v.add("1002@0", "2001@0");  // C.class --(interface)--> I2.class.

       setTag(I1.class, 2000);
       registerClass(2000, I1.class);

       setTag(I2.class, 2001);
       registerClass(2001, I2.class);
       v.add("2001@0", "2000@0");  // I2.class --(interface)--> I1.class.
     }

     private static A createTree(Verifier v) {
       A aInst = new A();
       setTag(aInst, 1);
       String aInstStr = "1@1000";
       String aClassStr = "1000@0";
       v.add(aInstStr, aClassStr);  // A -->(class) --> A.class.

       A a2Inst = new A();
       setTag(a2Inst, 2);
       aInst.foo = a2Inst;
       String a2InstStr = "2@1000";
       v.add(a2InstStr, aClassStr);  // A2 -->(class) --> A.class.
       v.add(aInstStr, a2InstStr);   // A -->(field) --> A2.

       B bInst = new B();
       setTag(bInst, 3);
       aInst.foo2 = bInst;
       String bInstStr = "3@1001";
       String bClassStr = "1001@0";
       v.add(bInstStr, bClassStr);  // B -->(class) --> B.class.
       v.add(aInstStr, bInstStr);   // A -->(field) --> B.

       A a3Inst = new A();
       setTag(a3Inst, 4);
       bInst.bar = a3Inst;
       String a3InstStr = "4@1000";
       v.add(a3InstStr, aClassStr);  // A3 -->(class) --> A.class.
       v.add(bInstStr, a3InstStr);   // B -->(field) --> A3.

       C cInst = new C();
       setTag(cInst, 5);
       bInst.bar2 = cInst;
       String cInstStr = "5@1000";
       String cClassStr = "1002@0";
       v.add(cInstStr, cClassStr);  // C -->(class) --> C.class.
       v.add(bInstStr, cInstStr);   // B -->(field) --> C.

       A a4Inst = new A();
       setTag(a4Inst, 6);
       cInst.baz = a4Inst;
       String a4InstStr = "6@1000";
       v.add(a4InstStr, aClassStr);  // A4 -->(class) --> A.class.
       v.add(cInstStr, a4InstStr);   // C -->(field) --> A4.

       cInst.baz2 = aInst;
       v.add(cInstStr, aInstStr);  // C -->(field) --> A.

       A[] aArray = new A[2];
       setTag(aArray, 500);
       aArray[1] = a2Inst;
       cInst.array = aArray;
       String aArrayStr = "500@0";
       v.add(cInstStr, aArrayStr);
       v.add(aArrayStr, a2InstStr);

       return aInst;
     }
   }

   public static class A {
     public A foo;
     public A foo2;

     public A() {}
     public A(A a, A b) {
       foo = a;
       foo2 = b;
     }
   }

   public static class B extends A {
     public A bar;
     public A bar2;

     public B() {}
     public B(A a, A b) {
       bar = a;
       bar2 = b;
     }
   }

   public static interface I1 {
     public final static int i1Field = 1;
   }

   public static interface I2 extends I1 {
     public final static int i2Field = 2;
   }

   public static class C extends B implements I2 {
     public A baz;
     public A baz2;
     public A[] array;

     public C() {}
     public C(A a, A b) {
       baz = a;
       baz2 = b;
     }
   }

   private static interface Inf1 {
     public final static int A = 1;
   }

   private static interface Inf2 extends Inf1 {
     public final static int B = 1;
   }

   private static class IntObject implements Inf1 {
     byte b = (byte)1;
     char c= 'a';
     short s = (short)2;
     int i = 3;
     long l = 4;
     Object o = new Object();
     static int sI = 5;
   }

   private static class FloatObject extends IntObject implements Inf2 {
     float f = 1.23f;
     double d = 1.23;
     Object p = new Object();
     static int sI = 6;
   }

   public static class Verifier {
     // Should roots with vreg=-1 be printed?
     public final static boolean PRINT_ROOTS_WITH_UNKNOWN_VREG = false;

     public static class Node {
       public String referrer;

       public HashSet<String> referrees = new HashSet<>();

       public Node(String r) {
         referrer = r;
       }

       public boolean isRoot() {
         return referrer.startsWith("root@");
       }
     }

     HashMap<String, Node> nodes = new HashMap<>();

     public Verifier() {
     }

     public void add(String referrer, String referree) {
       if (!nodes.containsKey(referrer)) {
         nodes.put(referrer, new Node(referrer));
       }
       if (referree != null) {
         nodes.get(referrer).referrees.add(referree);
       }
     }

     public void process(String[] lines, String additionalEnabledReferrer, boolean filtered) {
       // This method isn't optimal. The loops could be merged. However, it's more readable if
       // the different parts are separated.

       ArrayList<String> rootLines = new ArrayList<>();
       ArrayList<String> nonRootLines = new ArrayList<>();

       // Check for consecutive chunks of referrers. Also ensure roots come first.
       {
         String currentHead = null;
         boolean rootsDone = false;
         HashSet<String> completedReferrers = new HashSet<>();
         for (String l : lines) {
           String referrer = getReferrer(l);

           if (isRoot(referrer)) {
             if (rootsDone) {
               System.out.println("ERROR: Late root " + l);
               print(lines);
               return;
             }
             rootLines.add(l);
             continue;
           }

           rootsDone = true;

           if (currentHead == null) {
             currentHead = referrer;
           } else {
             // Ignore 0@0, as it can happen at any time (as it stands for all other objects).
             if (!currentHead.equals(referrer) && !referrer.equals("0@0")) {
               completedReferrers.add(currentHead);
               currentHead = referrer;
               if (completedReferrers.contains(referrer)) {
                 System.out.println("Non-contiguous referrer " + l);
                 print(lines);
                 return;
               }
             }
           }
           nonRootLines.add(l);
         }
       }

       // Sort (root order is not specified) and print the roots.
       // TODO: What about extra roots? JNI and the interpreter seem to introduce those (though it
       //       isn't clear why a debuggable-AoT test doesn't have the same, at least for locals).
       //       For now, swallow duplicates, and resolve once we have the metadata for the roots.
       {
         Collections.sort(rootLines);
         String lastRoot = null;
         for (String l : rootLines) {
           if (lastRoot != null && lastRoot.equals(l)) {
             continue;
           }
           lastRoot = l;
           if (!PRINT_ROOTS_WITH_UNKNOWN_VREG && l.indexOf("vreg=-1") > 0) {
             continue;
           }
           System.out.println(l);
         }
       }

       if (filtered) {
         // If we aren't tracking dependencies, just sort the lines and print.
         // TODO: As the verifier is currently using the output lines to track dependencies, we
         //       cannot verify that output is correct when parts of it are suppressed by filters.
         //       To correctly track this we need to take node information into account, and
         //       actually analyze the graph.
         Collections.sort(nonRootLines);
         for (String l : nonRootLines) {
           System.out.println(l);
         }

         System.out.println("---");
         return;
       }

       // Iterate through the lines, keeping track of which referrers are visited, to ensure the
       // order is acceptable.
       HashSet<String> enabled = new HashSet<>();
       if (additionalEnabledReferrer != null) {
         enabled.add(additionalEnabledReferrer);
       }
       // Always add "0@0".
       enabled.add("0@0");

       for (String l : lines) {
         String referrer = getReferrer(l);
         String referree = getReferree(l);
         if (isRoot(referrer)) {
           // For a root src, just enable the referree.
           enabled.add(referree);
         } else {
           // Check that the referrer is enabled (may be visited).
           if (!enabled.contains(referrer)) {
             System.out.println("Referrer " + referrer + " not enabled: " + l);
             print(lines);
             return;
           }
           enabled.add(referree);
         }
       }

       // Now just sort the non-root lines and output them
       Collections.sort(nonRootLines);
       for (String l : nonRootLines) {
         System.out.println(l);
       }

       System.out.println("---");
     }

     public static boolean isRoot(String ref) {
       return ref.startsWith("root@");
     }

     private static String getReferrer(String line) {
       int i = line.indexOf(" --");
       if (i <= 0) {
         throw new IllegalArgumentException(line);
       }
       int j = line.indexOf(' ');
       if (i != j) {
         throw new IllegalArgumentException(line);
       }
       return line.substring(0, i);
     }

     private static String getReferree(String line) {
       int i = line.indexOf("--> ");
       if (i <= 0) {
         throw new IllegalArgumentException(line);
       }
       int j = line.indexOf(' ', i + 4);
       if (j < 0) {
         throw new IllegalArgumentException(line);
       }
       return line.substring(i + 4, j);
     }

     private static void print(String[] lines) {
       for (String l : lines) {
         System.out.println(l);
       }
     }
   }

   private static void setTag(Object o, long tag) {
     Main.setTag(o, tag);
   }
   private static long getTag(Object o) {
     return Main.getTag(o);
   }

   private static native boolean checkInitialized(Class<?> klass);
   private static native void setupGcCallback();
   private static native void enableGcTracking(boolean enable);
   private static native int getGcStarts();
   private static native int getGcFinishes();
   private static native void forceGarbageCollection();

   private static native void checkForExtensionApis();
   private static native int getObjectHeapId(long tag);
   private static native String getHeapName(int heapId);
   private static native void checkGetObjectHeapIdInCallback(long tag, int heapId);

   public static native String[] followReferences(int heapFilter, Class<?> klassFilter,
       Object initialObject, int stopAfter, int followSet, Object jniRef);
   public static native String[] followReferencesString(Object initialObject);
   public static native String followReferencesPrimitiveArray(Object initialObject);
   public static native String followReferencesPrimitiveFields(Object initialObject);

   private static native void iterateThroughHeapExt();

   private static native void registerClass(long tag, Object obj);
 }
	/*
	* Copyright (C) 2016 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 art;

	import java.io.BufferedReader;
	import java.io.File;
	import java.io.FileReader;
	import java.util.ArrayList;
	import java.util.Arrays;
	import java.util.Collections;
	import java.util.HashMap;
	import java.util.HashSet;
	import java.util.concurrent.CountDownLatch;

	public class Test913 {
	public static void run() throws Exception {
	doTest();

	// Use a countdown latch for synchronization, as join() will introduce more roots.
	final CountDownLatch cdl1 = new CountDownLatch(1);

	// Run the follow-references tests on a dedicated thread so we know the specific Thread type.
	Thread t = new Thread() {
	@Override
	public void run() {
	try {
	Test913.runFollowReferences();
	} catch (Exception e) {
	throw new RuntimeException(e);
	}
	cdl1.countDown();
	}
	};
	t.start();
	cdl1.await();

	doExtensionTests();
	}

	public static void runFollowReferences() throws Exception {
	new TestConfig().doFollowReferencesTest();

	Runtime.getRuntime().gc();
	Runtime.getRuntime().gc();

	new TestConfig(null, 0, 1, -1).doFollowReferencesTest();

	Runtime.getRuntime().gc();
	Runtime.getRuntime().gc();

	new TestConfig(null, 0, Integer.MAX_VALUE, 1).doFollowReferencesTest();

	Runtime.getRuntime().gc();
	Runtime.getRuntime().gc();

	doStringTest();

	Runtime.getRuntime().gc();
	Runtime.getRuntime().gc();

	doPrimitiveArrayTest();
	doPrimitiveFieldTest();

	Runtime.getRuntime().gc();
	Runtime.getRuntime().gc();

	// Test klass filter.
	System.out.println("--- klass ---");
	new TestConfig(A.class, 0).doFollowReferencesTest();

	// Test heap filter.
	System.out.println("--- heap_filter ---");
	System.out.println("---- tagged objects");
	new TestConfig(null, 0x4).doFollowReferencesTest();
	System.out.println("---- untagged objects");
	new TestConfig(null, 0x8).doFollowReferencesTest();
	System.out.println("---- tagged classes");
	new TestConfig(null, 0x10).doFollowReferencesTest();
	System.out.println("---- untagged classes");
	new TestConfig(null, 0x20).doFollowReferencesTest();
	}

	public static void doTest() throws Exception {
	setupGcCallback();

	enableGcTracking(true);
	runGc();
	enableGcTracking(false);
	}

	public static void doStringTest() throws Exception {
	final String str = new String("HelloWorld");
	final String str2 = new String("");
	Object o = new Object() {
	String s = str;
	String s2 = str2;
	};

	setTag(str, 1);
	setTag(str2, 2);
	System.out.println(Arrays.toString(followReferencesString(o)));
	System.out.println(getTag(str));
	System.out.println(getTag(str2));
	}

	public static void doPrimitiveArrayTest() throws Exception {
	final boolean[] zArray = new boolean[] { false, true };
	setTag(zArray, 1);

	final byte[] bArray = new byte[] { 1, 2, 3 };
	setTag(bArray, 2);

	final char[] cArray = new char[] { 'A', 'Z' };
	setTag(cArray, 3);

	final short[] sArray = new short[] { 1, 2, 3 };
	setTag(sArray, 4);

	final int[] iArray = new int[] { 1, 2, 3 };
	setTag(iArray, 5);

	final float[] fArray = new float[] { 0.0f, 1.0f };
	setTag(fArray, 6);

	final long[] lArray = new long[] { 1, 2, 3 };
	setTag(lArray, 7);

	final double[] dArray = new double[] { 0.0, 1.0 };
	setTag(dArray, 8);

	Object o = new Object() {
	Object z = zArray;
	Object b = bArray;
	Object c = cArray;
	Object s = sArray;
	Object i = iArray;
	Object f = fArray;
	Object l = lArray;
	Object d = dArray;
	};

	System.out.println(followReferencesPrimitiveArray(o));
	System.out.print(getTag(zArray));
	System.out.print(getTag(bArray));
	System.out.print(getTag(cArray));
	System.out.print(getTag(sArray));
	System.out.print(getTag(iArray));
	System.out.print(getTag(fArray));
	System.out.print(getTag(lArray));
	System.out.println(getTag(dArray));
	}

	public static void doPrimitiveFieldTest() throws Exception {
	// Force GCs to clean up dirt.
	Runtime.getRuntime().gc();
	Runtime.getRuntime().gc();

	doTestPrimitiveFieldsClasses();

	doTestPrimitiveFieldsIntegral();

	// Force GCs to clean up dirt.
	Runtime.getRuntime().gc();
	Runtime.getRuntime().gc();

	doTestPrimitiveFieldsFloat();

	// Force GCs to clean up dirt.
	Runtime.getRuntime().gc();
	Runtime.getRuntime().gc();
	}

	private static void doTestPrimitiveFieldsClasses() {
	setTag(IntObject.class, 10000);
	System.out.println(followReferencesPrimitiveFields(IntObject.class));
	System.out.println(getTag(IntObject.class));
	setTag(IntObject.class, 0);

	setTag(FloatObject.class, 10000);
	System.out.println(followReferencesPrimitiveFields(FloatObject.class));
	System.out.println(getTag(FloatObject.class));
	setTag(FloatObject.class, 0);

	boolean correctHeapValue = false;
	setTag(Inf1.class, 10000);
	String heapTrace = followReferencesPrimitiveFields(Inf1.class);

	if (!checkInitialized(Inf1.class)) {
	correctHeapValue = heapTrace.equals("10000@0 (static, int, index=0) 0000000000000000");
	} else {
	correctHeapValue = heapTrace.equals("10000@0 (static, int, index=0) 0000000000000001");
	}

	if (!correctHeapValue)
	System.out.println("Heap Trace for Inf1 is not as expected:\n" + heapTrace);

	System.out.println(getTag(Inf1.class));
	setTag(Inf1.class, 0);

	setTag(Inf2.class, 10000);
	heapTrace = followReferencesPrimitiveFields(Inf2.class);

	if (!checkInitialized(Inf2.class)) {
	correctHeapValue = heapTrace.equals("10000@0 (static, int, index=1) 0000000000000000");
	} else {
	correctHeapValue = heapTrace.equals("10000@0 (static, int, index=1) 0000000000000001");
	}

	if (!correctHeapValue)
	System.out.println("Heap Trace for Inf2 is not as expected:\n" + heapTrace);
	System.out.println(getTag(Inf2.class));
	setTag(Inf2.class, 0);
	}

	private static void doTestPrimitiveFieldsIntegral() {
	IntObject intObject = new IntObject();
	setTag(intObject, 10000);
	System.out.println(followReferencesPrimitiveFields(intObject));
	System.out.println(getTag(intObject));
	}

	private static void doTestPrimitiveFieldsFloat() {
	FloatObject floatObject = new FloatObject();
	setTag(floatObject, 10000);
	System.out.println(followReferencesPrimitiveFields(floatObject));
	System.out.println(getTag(floatObject));
	}

	static ArrayList<Object> extensionTestHolder;

	private static void doExtensionTests() {
	checkForExtensionApis();

	extensionTestHolder = new ArrayList<>();
	System.out.println();

	try {
	getHeapName(-1);
	System.out.println("Expected failure for -1");
	} catch (Exception e) {
	}
	System.out.println(getHeapName(0));
	System.out.println(getHeapName(1));
	System.out.println(getHeapName(2));
	System.out.println(getHeapName(3));
	try {
	getHeapName(4);
	System.out.println("Expected failure for -1");
	} catch (Exception e) {
	}

	System.out.println();

	setTag(Object.class, 100000);
	int objectClassHeapId = getObjectHeapId(100000);
	int objClassExpectedHeapId = hasImage() ? 1 : 3;
	if (objectClassHeapId != objClassExpectedHeapId) {
	throw new RuntimeException("Expected object class in heap " + objClassExpectedHeapId +
	" but received " + objectClassHeapId);
	}

	A a = new A();
	extensionTestHolder.add(a);
	setTag(a, 100001);
	System.out.println(getObjectHeapId(100001));

	checkGetObjectHeapIdInCallback(100000, objClassExpectedHeapId);
	checkGetObjectHeapIdInCallback(100001, 3);

	long baseTag = 30000000;
	setTag(Object.class, baseTag + objClassExpectedHeapId);
	setTag(Class.class, baseTag + objClassExpectedHeapId);
	Object o = new Object();
	extensionTestHolder.add(o);
	setTag(o, baseTag + 3);

	iterateThroughHeapExt();

	extensionTestHolder = null;
	}

	private static void runGc() {
	clearStats();
	forceGarbageCollection();
	printStats();
	}

	private static void clearStats() {
	getGcStarts();
	getGcFinishes();
	}

	private static void printStats() {
	System.out.println("---");
	int s = getGcStarts();
	int f = getGcFinishes();
	System.out.println((s > 0) + " " + (f > 0));
	}

	private static boolean hasImage() {
	try {
	int pid = Integer.parseInt(new File("/proc/self").getCanonicalFile().getName());
	BufferedReader reader = new BufferedReader(new FileReader("/proc/" + pid + "/maps"));
	String line;
	while ((line = reader.readLine()) != null) {
	// On host the mappings end with .art and on device they end with .art]
	if (line.endsWith(".art]") \|\| line.endsWith(".art")) {
	reader.close();
	return true;
	}
	}
	reader.close();
	return false;
	} catch (Exception e) {
	throw new RuntimeException(e);
	}
	}

	private static class TestConfig {
	private Class<?> klass = null;
	private int heapFilter = 0;
	private int stopAfter = Integer.MAX_VALUE;
	private int followSet = -1;

	public TestConfig() {
	}
	public TestConfig(Class<?> klass, int heapFilter) {
	this.klass = klass;
	this.heapFilter = heapFilter;
	}
	public TestConfig(Class<?> klass, int heapFilter, int stopAfter, int followSet) {
	this.klass = klass;
	this.heapFilter = heapFilter;
	this.stopAfter = stopAfter;
	this.followSet = followSet;
	}

	public void doFollowReferencesTest() throws Exception {
	// Force GCs to clean up dirt.
	Runtime.getRuntime().gc();
	Runtime.getRuntime().gc();

	setTag(Thread.currentThread(), 3000);

	{
	ArrayList<Object> tmpStorage = new ArrayList<>();
	doFollowReferencesTestNonRoot(tmpStorage);
	tmpStorage = null;
	}

	// Force GCs to clean up dirt.
	Runtime.getRuntime().gc();
	Runtime.getRuntime().gc();

	doFollowReferencesTestRoot();

	// Force GCs to clean up dirt.
	Runtime.getRuntime().gc();
	Runtime.getRuntime().gc();
	}

	private void doFollowReferencesTestNonRoot(ArrayList<Object> tmpStorage) {
	Verifier v = new Verifier();
	tagClasses(v);
	A a = createTree(v);
	tmpStorage.add(a);
	v.add("0@0", "1@1000"); // tmpStorage[0] --(array-element)--> a.

	doFollowReferencesTestImpl(null, stopAfter, followSet, null, v, null);
	doFollowReferencesTestImpl(a.foo2, stopAfter, followSet, null, v, "3@1001");

	tmpStorage.clear();
	}

	private void doFollowReferencesTestRoot() {
	Verifier v = new Verifier();
	tagClasses(v);
	A a = createTree(v);

	doFollowReferencesTestImpl(null, stopAfter, followSet, a, v, null);
	doFollowReferencesTestImpl(a.foo2, stopAfter, followSet, a, v, "3@1001");
	}

	private void doFollowReferencesTestImpl(A root, int stopAfter, int followSet,
	Object asRoot, Verifier v, String additionalEnabled) {
	String[] lines =
	followReferences(heapFilter, klass, root, stopAfter, followSet, asRoot);

	v.process(lines, additionalEnabled, heapFilter != 0 \|\| klass != null);
	}

	private static void tagClasses(Verifier v) {
	setTag(A.class, 1000);
	registerClass(1000, A.class);

	setTag(B.class, 1001);
	registerClass(1001, B.class);
	v.add("1001@0", "1000@0"); // B.class --(superclass)--> A.class.

	setTag(C.class, 1002);
	registerClass(1002, C.class);
	v.add("1002@0", "1001@0"); // C.class --(superclass)--> B.class.
	v.add("1002@0", "2001@0"); // C.class --(interface)--> I2.class.

	setTag(I1.class, 2000);
	registerClass(2000, I1.class);

	setTag(I2.class, 2001);
	registerClass(2001, I2.class);
	v.add("2001@0", "2000@0"); // I2.class --(interface)--> I1.class.
	}

	private static A createTree(Verifier v) {
	A aInst = new A();
	setTag(aInst, 1);
	String aInstStr = "1@1000";
	String aClassStr = "1000@0";
	v.add(aInstStr, aClassStr); // A -->(class) --> A.class.

	A a2Inst = new A();
	setTag(a2Inst, 2);
	aInst.foo = a2Inst;
	String a2InstStr = "2@1000";
	v.add(a2InstStr, aClassStr); // A2 -->(class) --> A.class.
	v.add(aInstStr, a2InstStr); // A -->(field) --> A2.

	B bInst = new B();
	setTag(bInst, 3);
	aInst.foo2 = bInst;
	String bInstStr = "3@1001";
	String bClassStr = "1001@0";
	v.add(bInstStr, bClassStr); // B -->(class) --> B.class.
	v.add(aInstStr, bInstStr); // A -->(field) --> B.

	A a3Inst = new A();
	setTag(a3Inst, 4);
	bInst.bar = a3Inst;
	String a3InstStr = "4@1000";
	v.add(a3InstStr, aClassStr); // A3 -->(class) --> A.class.
	v.add(bInstStr, a3InstStr); // B -->(field) --> A3.

	C cInst = new C();
	setTag(cInst, 5);
	bInst.bar2 = cInst;
	String cInstStr = "5@1000";
	String cClassStr = "1002@0";
	v.add(cInstStr, cClassStr); // C -->(class) --> C.class.
	v.add(bInstStr, cInstStr); // B -->(field) --> C.

	A a4Inst = new A();
	setTag(a4Inst, 6);
	cInst.baz = a4Inst;
	String a4InstStr = "6@1000";
	v.add(a4InstStr, aClassStr); // A4 -->(class) --> A.class.
	v.add(cInstStr, a4InstStr); // C -->(field) --> A4.

	cInst.baz2 = aInst;
	v.add(cInstStr, aInstStr); // C -->(field) --> A.

	A[] aArray = new A[2];
	setTag(aArray, 500);
	aArray[1] = a2Inst;
	cInst.array = aArray;
	String aArrayStr = "500@0";
	v.add(cInstStr, aArrayStr);
	v.add(aArrayStr, a2InstStr);

	return aInst;
	}
	}

	public static class A {
	public A foo;
	public A foo2;

	public A() {}
	public A(A a, A b) {
	foo = a;
	foo2 = b;
	}
	}

	public static class B extends A {
	public A bar;
	public A bar2;

	public B() {}
	public B(A a, A b) {
	bar = a;
	bar2 = b;
	}
	}

	public static interface I1 {
	public final static int i1Field = 1;
	}

	public static interface I2 extends I1 {
	public final static int i2Field = 2;
	}

	public static class C extends B implements I2 {
	public A baz;
	public A baz2;
	public A[] array;

	public C() {}
	public C(A a, A b) {
	baz = a;
	baz2 = b;
	}
	}

	private static interface Inf1 {
	public final static int A = 1;
	}

	private static interface Inf2 extends Inf1 {
	public final static int B = 1;
	}

	private static class IntObject implements Inf1 {
	byte b = (byte)1;
	char c= 'a';
	short s = (short)2;
	int i = 3;
	long l = 4;
	Object o = new Object();
	static int sI = 5;
	}

	private static class FloatObject extends IntObject implements Inf2 {
	float f = 1.23f;
	double d = 1.23;
	Object p = new Object();
	static int sI = 6;
	}

	public static class Verifier {
	// Should roots with vreg=-1 be printed?
	public final static boolean PRINT_ROOTS_WITH_UNKNOWN_VREG = false;

	public static class Node {
	public String referrer;

	public HashSet<String> referrees = new HashSet<>();

	public Node(String r) {
	referrer = r;
	}

	public boolean isRoot() {
	return referrer.startsWith("root@");
	}
	}

	HashMap<String, Node> nodes = new HashMap<>();

	public Verifier() {
	}

	public void add(String referrer, String referree) {
	if (!nodes.containsKey(referrer)) {
	nodes.put(referrer, new Node(referrer));
	}
	if (referree != null) {
	nodes.get(referrer).referrees.add(referree);
	}
	}

	public void process(String[] lines, String additionalEnabledReferrer, boolean filtered) {
	// This method isn't optimal. The loops could be merged. However, it's more readable if
	// the different parts are separated.

	ArrayList<String> rootLines = new ArrayList<>();
	ArrayList<String> nonRootLines = new ArrayList<>();

	// Check for consecutive chunks of referrers. Also ensure roots come first.
	{
	String currentHead = null;
	boolean rootsDone = false;
	HashSet<String> completedReferrers = new HashSet<>();
	for (String l : lines) {
	String referrer = getReferrer(l);

	if (isRoot(referrer)) {
	if (rootsDone) {
	System.out.println("ERROR: Late root " + l);
	print(lines);
	return;
	}
	rootLines.add(l);
	continue;
	}

	rootsDone = true;

	if (currentHead == null) {
	currentHead = referrer;
	} else {
	// Ignore 0@0, as it can happen at any time (as it stands for all other objects).
	if (!currentHead.equals(referrer) && !referrer.equals("0@0")) {
	completedReferrers.add(currentHead);
	currentHead = referrer;
	if (completedReferrers.contains(referrer)) {
	System.out.println("Non-contiguous referrer " + l);
	print(lines);
	return;
	}
	}
	}
	nonRootLines.add(l);
	}
	}

	// Sort (root order is not specified) and print the roots.
	// TODO: What about extra roots? JNI and the interpreter seem to introduce those (though it
	// isn't clear why a debuggable-AoT test doesn't have the same, at least for locals).
	// For now, swallow duplicates, and resolve once we have the metadata for the roots.
	{
	Collections.sort(rootLines);
	String lastRoot = null;
	for (String l : rootLines) {
	if (lastRoot != null && lastRoot.equals(l)) {
	continue;
	}
	lastRoot = l;
	if (!PRINT_ROOTS_WITH_UNKNOWN_VREG && l.indexOf("vreg=-1") > 0) {
	continue;
	}
	System.out.println(l);
	}
	}

	if (filtered) {
	// If we aren't tracking dependencies, just sort the lines and print.
	// TODO: As the verifier is currently using the output lines to track dependencies, we
	// cannot verify that output is correct when parts of it are suppressed by filters.
	// To correctly track this we need to take node information into account, and
	// actually analyze the graph.
	Collections.sort(nonRootLines);
	for (String l : nonRootLines) {
	System.out.println(l);
	}

	System.out.println("---");
	return;
	}

	// Iterate through the lines, keeping track of which referrers are visited, to ensure the
	// order is acceptable.
	HashSet<String> enabled = new HashSet<>();
	if (additionalEnabledReferrer != null) {
	enabled.add(additionalEnabledReferrer);
	}
	// Always add "0@0".
	enabled.add("0@0");

	for (String l : lines) {
	String referrer = getReferrer(l);
	String referree = getReferree(l);
	if (isRoot(referrer)) {
	// For a root src, just enable the referree.
	enabled.add(referree);
	} else {
	// Check that the referrer is enabled (may be visited).
	if (!enabled.contains(referrer)) {
	System.out.println("Referrer " + referrer + " not enabled: " + l);
	print(lines);
	return;
	}
	enabled.add(referree);
	}
	}

	// Now just sort the non-root lines and output them
	Collections.sort(nonRootLines);
	for (String l : nonRootLines) {
	System.out.println(l);
	}

	System.out.println("---");
	}

	public static boolean isRoot(String ref) {
	return ref.startsWith("root@");
	}

	private static String getReferrer(String line) {
	int i = line.indexOf(" --");
	if (i <= 0) {
	throw new IllegalArgumentException(line);
	}
	int j = line.indexOf(' ');
	if (i != j) {
	throw new IllegalArgumentException(line);
	}
	return line.substring(0, i);
	}

	private static String getReferree(String line) {
	int i = line.indexOf("--> ");
	if (i <= 0) {
	throw new IllegalArgumentException(line);
	}
	int j = line.indexOf(' ', i + 4);
	if (j < 0) {
	throw new IllegalArgumentException(line);
	}
	return line.substring(i + 4, j);
	}

	private static void print(String[] lines) {
	for (String l : lines) {
	System.out.println(l);
	}
	}
	}

	private static void setTag(Object o, long tag) {
	Main.setTag(o, tag);
	}
	private static long getTag(Object o) {
	return Main.getTag(o);
	}

	private static native boolean checkInitialized(Class<?> klass);
	private static native void setupGcCallback();
	private static native void enableGcTracking(boolean enable);
	private static native int getGcStarts();
	private static native int getGcFinishes();
	private static native void forceGarbageCollection();

	private static native void checkForExtensionApis();
	private static native int getObjectHeapId(long tag);
	private static native String getHeapName(int heapId);
	private static native void checkGetObjectHeapIdInCallback(long tag, int heapId);

	public static native String[] followReferences(int heapFilter, Class<?> klassFilter,
	Object initialObject, int stopAfter, int followSet, Object jniRef);
	public static native String[] followReferencesString(Object initialObject);
	public static native String followReferencesPrimitiveArray(Object initialObject);
	public static native String followReferencesPrimitiveFields(Object initialObject);

	private static native void iterateThroughHeapExt();

	private static native void registerClass(long tag, Object obj);
	}