--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/hotspot/test/gc/g1/humongousObjects/objectGraphTest/GC.java	Fri May 06 17:51:11 2016 +0300
@@ -0,0 +1,199 @@
+/*
+ * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ *
+ */
+
+package gc.g1.humongousObjects.objectGraphTest;
+
+import gc.testlibrary.Helpers;
+import jdk.test.lib.Asserts;
+import sun.hotspot.WhiteBox;
+
+import java.util.Arrays;
+import java.util.List;
+import java.util.function.Consumer;
+
+/**
+ * Provides methods to initiate GC of requested type and
+ * checks for states of humongous and non-humongous soft/weak externally
+ * referenced objects after GCs
+ */
+public enum GC {
+
+    YOUNG_GC {
+        @Override
+        public Runnable get() {
+            return WHITE_BOX::youngGC;
+        }
+
+        public Consumer<ReferenceInfo<Object[]>> getChecker() {
+            return getCheckerImpl(false, false, true, false);
+        }
+
+        @Override
+        public List<String> shouldContain() {
+            return Arrays.asList(GCTokens.WB_INITIATED_YOUNG_GC);
+        }
+
+        @Override
+        public List<String> shouldNotContain() {
+            return Arrays.asList(GCTokens.WB_INITIATED_MIXED_GC, GCTokens.FULL_GC, GCTokens.WB_INITIATED_CMC,
+                    GCTokens.CMC, GCTokens.YOUNG_GC);
+        }
+    },
+    FULL_GC {
+        @Override
+        public Runnable get() {
+            return System::gc;
+        }
+
+        public Consumer<ReferenceInfo<Object[]>> getChecker() {
+            return getCheckerImpl(true, false, true, false);
+        }
+
+        @Override
+        public List<String> shouldContain() {
+            return Arrays.asList(GCTokens.FULL_GC);
+        }
+
+        @Override
+        public List<String> shouldNotContain() {
+            return Arrays.asList(GCTokens.WB_INITIATED_YOUNG_GC, GCTokens.WB_INITIATED_MIXED_GC,
+                    GCTokens.WB_INITIATED_CMC, GCTokens.CMC, GCTokens.YOUNG_GC);
+        }
+    },
+
+    FULL_GC_MEMORY_PRESSURE {
+        @Override
+        public Runnable get() {
+            return WHITE_BOX::fullGC;
+        }
+
+        public Consumer<ReferenceInfo<Object[]>> getChecker() {
+            return getCheckerImpl(true, true, true, true);
+        }
+
+        @Override
+        public List<String> shouldContain() {
+            return Arrays.asList(GCTokens.FULL_GC_MEMORY_PRESSURE);
+        }
+
+        @Override
+        public List<String> shouldNotContain() {
+            return Arrays.asList(GCTokens.WB_INITIATED_YOUNG_GC, GCTokens.WB_INITIATED_MIXED_GC,
+                    GCTokens.WB_INITIATED_CMC, GCTokens.CMC, GCTokens.YOUNG_GC, GCTokens.FULL_GC);
+        }
+    };
+
+    protected String getErrorMessage(ReferenceInfo<Object[]> ref, boolean expectedNull, String gcType) {
+        return String.format("Externally effectively %s referenced %shumongous object was%s deleted after %s",
+                (ref.softlyReachable ? "soft" : "weak"), (ref.effectiveHumongous ? "" : "non-"),
+                (expectedNull ? " not" : ""), gcType);
+    }
+
+    protected Consumer<ReferenceInfo<Object[]>> getCaseCheck(boolean expectedNull) {
+        return expectedNull
+                ? r -> Asserts.assertNull(r.reference.get(), getErrorMessage(r, true, name()))
+                : r -> Asserts.assertNotNull(r.reference.get(), getErrorMessage(r, false, name()));
+    }
+
+    protected Consumer<ReferenceInfo<Object[]>> getCheckerImpl(boolean weakH, boolean softH,
+                                                               boolean weakS, boolean softS) {
+        return new Checker(getCaseCheck(weakH), getCaseCheck(softH), getCaseCheck(weakS), getCaseCheck(softS));
+    }
+
+    protected String getGcLogName(String prefix) {
+        return prefix + "_" + name() + ".gc.log";
+    }
+
+    private static final WhiteBox WHITE_BOX = WhiteBox.getWhiteBox();
+
+    /**
+     * @return method to initiate GC
+     */
+    public abstract Runnable get();
+
+    /**
+     * @return checker for objects' states after GC
+     */
+    public abstract Consumer<ReferenceInfo<Object[]>> getChecker();
+
+    /**
+     * @return list of tokens that should be contained in gc log after gc of specified type
+     */
+    public abstract List<String> shouldContain();
+
+    /**
+     * @return list of tokens that should not be contained in gc log after gc of specified type
+     */
+    public abstract List<String> shouldNotContain();
+
+
+    /**
+     * Checks object' state after gc
+     * Contains 4 Consumers which are called depending on humongous/non-humongous and
+     * external weak/soft referenced objects
+     */
+    private static class Checker implements Consumer<ReferenceInfo<Object[]>> {
+        // 4 consumers with checks for (humongous /simple objects)*(weak/soft referenced)
+        final Consumer<ReferenceInfo<Object[]>> weakHumongousCheck;
+        final Consumer<ReferenceInfo<Object[]>> softHumongousCheck;
+        final Consumer<ReferenceInfo<Object[]>> weakSimpleCheck;
+        final Consumer<ReferenceInfo<Object[]>> softSimpleCheck;
+
+        public Checker(Consumer<ReferenceInfo<Object[]>> weakHumongousCheck,
+                       Consumer<ReferenceInfo<Object[]>> softHumongousCheck,
+                       Consumer<ReferenceInfo<Object[]>> weakSimpleCheck,
+                       Consumer<ReferenceInfo<Object[]>> softSimpleCheck) {
+            this.weakHumongousCheck = weakHumongousCheck;
+            this.softHumongousCheck = softHumongousCheck;
+            this.weakSimpleCheck = weakSimpleCheck;
+            this.softSimpleCheck = softSimpleCheck;
+        }
+
+        public void accept(ReferenceInfo<Object[]> ref) {
+
+            System.out.println("reference.get() returned " + ref.reference.get());
+            if (ref.effectiveHumongous && ref.softlyReachable) {
+                System.out.println("soft and humongous");
+                softHumongousCheck.accept(ref);
+            }
+
+            if (ref.effectiveHumongous && !ref.softlyReachable) {
+                System.out.println("weak and humongous");
+                weakHumongousCheck.accept(ref);
+
+            }
+
+            if (!ref.effectiveHumongous && ref.softlyReachable) {
+                System.out.println("soft and non-humongous");
+                softSimpleCheck.accept(ref);
+            }
+
+            if (!ref.effectiveHumongous && !ref.softlyReachable) {
+                System.out.println("weak and non-humongous");
+                weakSimpleCheck.accept(ref);
+            }
+        }
+    }
+
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/hotspot/test/gc/g1/humongousObjects/objectGraphTest/GCTokens.java	Fri May 06 17:51:11 2016 +0300
@@ -0,0 +1,42 @@
+/*
+ * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ *
+ */
+
+package gc.g1.humongousObjects.objectGraphTest;
+
+/**
+ * Contains tokens that could appear in gc log
+ */
+public final class GCTokens {
+    // Private c-tor to prevent instantiating
+    private GCTokens() {
+    }
+
+    public static final String WB_INITIATED_YOUNG_GC = "Young (WhiteBox Initiated Young GC)";
+    public static final String WB_INITIATED_MIXED_GC = "Pause Mixed (WhiteBox Initiated Young GC)";
+    public static final String WB_INITIATED_CMC = "WhiteBox Initiated Concurrent Mark";
+    public static final String FULL_GC = "Full (System.gc())";
+    public static final String FULL_GC_MEMORY_PRESSURE = "WhiteBox Initiated Full GC";
+    public static final String CMC = "Concurrent Mark)";
+    public static final String YOUNG_GC = "GC pause (young)";
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/hotspot/test/gc/g1/humongousObjects/objectGraphTest/ObjectGraph.java	Fri May 06 17:51:11 2016 +0300
@@ -0,0 +1,150 @@
+/*
+ * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ *
+ */
+
+package gc.g1.humongousObjects.objectGraphTest;
+
+import java.util.ArrayDeque;
+import java.util.Deque;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import java.util.function.BiConsumer;
+import java.util.function.Consumer;
+import java.util.function.Predicate;
+
+public class ObjectGraph {
+
+    private ObjectGraph() {
+    }
+
+    public enum ReferenceType {
+        NONE,
+        WEAK,
+        SOFT,
+        STRONG;
+    }
+
+    /**
+     * Performs operation on all nodes that are reachable from initial ones
+     *
+     * @param nodes     initial nodes
+     * @param operation operation
+     */
+    public static void propagateTransitiveProperty(Set<Object[]> nodes, Consumer<Object[]> operation) {
+        Deque<Object[]> roots = new ArrayDeque<>();
+        nodes.stream().forEach(roots::push);
+        ObjectGraph.enumerateAndMark(roots, operation);
+    }
+
+    /**
+     * Connects graph's vertexes with single-directed (vertex -> neighbour) link
+     *
+     * @param vertex    who is connected
+     * @param neighbour connected to whom
+     */
+    private static void connectVertexes(Object[] vertex, Object[] neighbour) {
+
+        // check if vertex array is full
+        if (vertex[vertex.length - 1] != null) {
+            throw new Error("Array is full and no connections could be added");
+        }
+        int i = 0;
+        while (vertex[i] != null) {
+            ++i;
+        }
+        vertex[i] = neighbour;
+    }
+
+
+    /**
+     * Builds object graph using description from list of parsed nodes. Graph uses Object[] as nodes, first n elements
+     * of array are links to connected nodes, others are null. Then runs visitors on generated graph
+     *
+     * @param parsedNodes             list of nodes' description
+     * @param visitors                visitors that will visit each node of generated graph
+     * @param humongousAllocationSize size of humongous node
+     * @param simpleAllocationSize    size of simple (non-humongous) node
+     * @return root reference to generated graph
+     */
+    public static Object[] generateObjectNodes(List<TestcaseData.FinalParsedNode> parsedNodes,
+                                               Map<Predicate<TestcaseData.FinalParsedNode>,
+                                                       BiConsumer<TestcaseData.FinalParsedNode, Object[][]>> visitors,
+                                               int humongousAllocationSize, int simpleAllocationSize) {
+
+        Object[][] objectNodes = new Object[parsedNodes.size()][];
+
+        // Allocating nodes on Object[]
+        for (int i = 0; i < parsedNodes.size(); ++i) {
+            objectNodes[i] = new Object[(parsedNodes.get(i).isHumongous ?
+                    humongousAllocationSize : simpleAllocationSize)];
+        }
+
+        // Connecting nodes on allocated on Object[]
+        for (int i = 0; i < parsedNodes.size(); ++i) {
+            for (int j = 0; j < parsedNodes.get(i).getConnectedTo().size(); ++j) {
+                connectVertexes(objectNodes[i], objectNodes[parsedNodes.get(i).getConnectedTo().get(j)]);
+            }
+        }
+
+        // Calling visitors
+        visitors.entrySet()
+                .stream()
+                .forEach(
+                        entry -> parsedNodes.stream()
+                                .filter(parsedNode -> entry.getKey().test(parsedNode))
+                                .forEach(node -> entry.getValue().accept(node, objectNodes))
+                );
+
+        return objectNodes[0];
+    }
+
+    /**
+     * Enumerates graph starting with provided vertexes. All vertexes that are reachable from the provided ones are
+     * marked
+     *
+     * @param markedParents provided vertexes
+     * @param markVertex    lambda which marks vertexes
+     */
+    public static void enumerateAndMark(Deque<Object[]> markedParents,
+                                        Consumer<Object[]> markVertex) {
+        Map<Object[], Boolean> isVisited = new HashMap<>();
+        while (!markedParents.isEmpty()) {
+            Object[] vertex = markedParents.pop();
+            if (vertex == null || isVisited.containsKey(vertex)) {
+                continue;
+            }
+            isVisited.put(vertex, true);
+            markVertex.accept(vertex);
+
+            for (int i = 0; i < vertex.length; ++i) {
+                if (vertex[i] == null) {
+                    break;
+                }
+                markedParents.add((Object[]) vertex[i]);
+            }
+        }
+    }
+
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/hotspot/test/gc/g1/humongousObjects/objectGraphTest/README	Fri May 06 17:51:11 2016 +0300
@@ -0,0 +1,56 @@
+/*
+ * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ *
+ */
+
+The test checks that after different type of GC unreachable objects behave as expected:
+
+1. Young GC - weakly referenced non-humongous objects are collected, other objects are not collected.
+
+2. Full GC - weakly referenced non-humongous and humongous objects are collected, softly referenced non-humongous and
+             humongous objects are not collected.
+
+3. Full GC with memory pressure - weakly and softly referenced non-humongous and humongous objects are collected.
+
+The test gets gc type as a command line argument.
+Then the test allocates object graph in heap (currently testing scenarios are pre-generated and stored in
+TestcaseData.getPregeneratedTestcases()) with TestObjectGraphAfterGC::allocateObjectGraph.
+
+Since we are testing humongous objects we need pretty unusual nodes - arrays of Object.
+We need this since only large enough array could be Humongous object (in fact class with huge amount of fields is
+humongous too but it's for other tests).
+ObjectGraph class generates object graph with Object[] nodes. It also provides a way to collect
+information about each node using "visitor" pattern.
+
+Using visitors we build Set of ReferenceInfo instances which contains the following information:
+reference - external weak/soft reference to graph's node
+graphId and nodeId - graph's and node's ids - we need this for error handling
+softlyReachable - is node effectively referenced by external soft reference. It could be when external
+soft reference or when this node is reachable from node that exteranally referenced by soft reference
+effectiveHumongous - if node behaves effectively humongous.  It could be when node is humongous
+or when this node is reachable from humongous node.
+
+When we leave TestObjectGraphAfterGC::allocateObjectGraph we make graph reachable only with references from Set of
+ReferenceInfo instances.
+
+We run specified gc and check that each instance of ReferenceInfo set behaves as expected.
+Then we check that gc log file contains expected tokens and doesn't contain tokens that it should not contain.

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/hotspot/test/gc/g1/humongousObjects/objectGraphTest/ReferenceInfo.java	Fri May 06 17:51:11 2016 +0300
@@ -0,0 +1,63 @@
+/*
+ * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ *
+ */
+
+package gc.g1.humongousObjects.objectGraphTest;
+
+import java.lang.ref.Reference;
+
+/**
+ * Immutable structure that holds the following information about graph's node
+ * reference - weak/soft reference to graph's node
+ * graphId and nodeId - graph's and node's ids - we need this for error handling
+ * softlyReachable - is node effectively referenced by external soft reference. It could be when external
+ * soft reference or when this node is reachable from node that externally referenced by soft reference
+ * effectiveHumongous - if node behaves effectively humongous.  It could be when node is humongous
+ * or when this node is reachable from humongous node.
+ *
+ * @param <T> - actual type of node
+ */
+public class ReferenceInfo<T> {
+    public final Reference<T> reference;
+    public final String graphId;
+    public final String nodeId;
+    public final boolean softlyReachable;
+    public final boolean effectiveHumongous;
+
+    public ReferenceInfo(Reference<T> reference, String graphId, String nodeId, boolean softlyReachable,
+                         boolean effectiveHumongous) {
+        this.reference = reference;
+        this.graphId = graphId;
+        this.nodeId = nodeId;
+        this.softlyReachable = softlyReachable;
+        this.effectiveHumongous = effectiveHumongous;
+    }
+
+    @Override
+    public String toString() {
+        return String.format("Node %s is effectively %shumongous and effectively %ssoft referenced\n"
+                        + "\tReference type is %s and it points to %s", nodeId,
+                (effectiveHumongous ? "" : "non-"), (softlyReachable ? "" : "non-"),
+                reference.getClass().getSimpleName(), reference.get());
+    }
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/hotspot/test/gc/g1/humongousObjects/objectGraphTest/TestObjectGraphAfterGC.java	Fri May 06 17:51:11 2016 +0300
@@ -0,0 +1,247 @@
+/*
+ * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ *
+ */
+
+package gc.g1.humongousObjects.objectGraphTest;
+
+import jdk.test.lib.OutputAnalyzer;
+import sun.hotspot.WhiteBox;
+
+import java.io.File;
+import java.io.IOException;
+import java.lang.ref.Reference;
+import java.lang.ref.ReferenceQueue;
+import java.lang.ref.SoftReference;
+import java.lang.ref.WeakReference;
+import java.nio.file.Files;
+import java.util.Map;
+import java.util.HashMap;
+import java.util.List;
+import java.util.HashSet;
+import java.util.Set;
+import java.util.function.BiConsumer;
+import java.util.function.Consumer;
+import java.util.function.Predicate;
+import java.util.stream.Collectors;
+
+
+/**
+ * @test TestObjectGraphAfterGC
+ * @summary Checks that objects' graph behave as expected after gc
+ * @requires vm.gc=="G1" | vm.gc=="null"
+ * @requires vm.opt.ExplicitGCInvokesConcurrent != true
+ * @library /testlibrary /test/lib /
+ * @modules java.management java.base/jdk.internal.misc
+ * @build sun.hotspot.WhiteBox
+ *        gc.testlibrary.Helpers
+ *        gc.g1.humongousObjects.objectGraphTest.GCTokens
+ *        gc.g1.humongousObjects.objectGraphTest.ReferenceInfo
+ *        gc.g1.humongousObjects.objectGraphTest.GC
+ *        gc.g1.humongousObjects.objectGraphTest.ObjectGraph
+ *        gc.g1.humongousObjects.objectGraphTest.TestObjectGraphAfterGC
+ * @run driver ClassFileInstaller sun.hotspot.WhiteBox
+ *                                sun.hotspot.WhiteBox$WhiteBoxPermission
+ *
+ * @run main/othervm -Xms200M -XX:+UseG1GC -XX:+UnlockDiagnosticVMOptions -XX:+WhiteBoxAPI -Xbootclasspath/a:.
+ * -XX:G1HeapRegionSize=1M -Xlog:gc*=debug:file=TestObjectGraphAfterGC_YOUNG_GC.gc.log
+ * gc.g1.humongousObjects.objectGraphTest.TestObjectGraphAfterGC YOUNG_GC
+ *
+ * @run main/othervm -Xms200M -XX:+UseG1GC -XX:+UnlockDiagnosticVMOptions -XX:+WhiteBoxAPI -Xbootclasspath/a:.
+ * -XX:G1HeapRegionSize=1M -Xlog:gc=info:file=TestObjectGraphAfterGC_FULL_GC.gc.log
+ * gc.g1.humongousObjects.objectGraphTest.TestObjectGraphAfterGC FULL_GC
+ *
+ * @run main/othervm -Xms200M -XX:+UseG1GC -XX:+UnlockDiagnosticVMOptions -XX:+WhiteBoxAPI -Xbootclasspath/a:.
+ * -XX:G1HeapRegionSize=1M -Xlog:gc=info:file=TestObjectGraphAfterGC_FULL_GC_MEMORY_PRESSURE.gc.log
+ * gc.g1.humongousObjects.objectGraphTest.TestObjectGraphAfterGC FULL_GC_MEMORY_PRESSURE
+ *
+ */
+
+/**
+ * Checks that objects' graph behave as expected after gc
+ * See README file for detailed info on test's logic
+ */
+public class TestObjectGraphAfterGC {
+
+    private static final int simpleAllocationSize = 1024;
+
+    /**
+     * Entry point
+     *
+     * @param args - first argument - gc name
+     */
+    public static void main(String[] args) {
+
+        if (args.length < 1) {
+            throw new Error("Expected gc name wasn't provided as command line argument");
+        }
+
+        GC gcType = GC.valueOf(args[0].toUpperCase());
+
+        System.out.println("Testing " + gcType.name());
+
+        TestcaseData.getPregeneratedTestcases().stream().forEach(testcase -> {
+            System.out.println("Testcase: " + testcase);
+
+            try {
+                TestObjectGraphAfterGC.doTesting(testcase, gcType.get(), gcType.getChecker(),
+                        gcType.getGcLogName(TestObjectGraphAfterGC.class.getSimpleName()), gcType.shouldContain(),
+                        gcType.shouldNotContain());
+            } catch (IOException e) {
+                throw new Error("Problems trying to find or open " + TestObjectGraphAfterGC.class.getSimpleName()
+                        + ".gc.log", e);
+            }
+            System.out.println(" Passed");
+        });
+    }
+
+    /**
+     * Implements testing with 3 methods - allocateObjectGraph, checkResults and checkGCLog
+     *
+     * @param testcaseData     testcase in the following notation:
+     *                         H - humongous node
+     *                         S - non-humongous node
+     *                         s - external soft reference
+     *                         w - external weak reference
+     *                         Hs->Sw - 1st node is humongous, externally soft referenced and strong references to
+     *                         non-humongous node 2 which is externally weak referenced
+     *                         H->1 - humongous node connects to the first node of chain
+     * @param doGC             method that initiates gc
+     * @param checker          consumer that checks node's state after gc and throws Error if it's wrong
+     * @param gcLogName        name of gc log
+     * @param shouldContain    list of tokens that should be contained in gc log
+     * @param shouldNotContain list of tokens that should not be contained in gc log
+     * @throws IOException if there are some issues with gc log
+     */
+    private static void doTesting(String testcaseData, Runnable doGC, Consumer<ReferenceInfo<Object[]>> checker,
+                                  String gcLogName, List<String> shouldContain, List<String> shouldNotContain)
+            throws IOException {
+        Set<ReferenceInfo<Object[]>> nodeData = allocateObjectGraph(testcaseData);
+        doGC.run();
+        checkResults(nodeData, checker);
+        checkGCLog(gcLogName, shouldContain, shouldNotContain);
+    }
+
+    /**
+     * Allocates a number of objects of humongous and regular size and links then with strong references.
+     * How many objects to create, their size and links between them is encoded in the given parameters.
+     * As the result an object graph will be created.
+     * For the testing purpose for each created object (a graph node) an extra ReferenceInfo object will be created.
+     * The ReferenceInfo instances will contain either weak or soft reference to the graph node.
+     *
+     * @param testcaseData testcase in the
+     *                     <p>
+     *                     H - humongous node
+     *                     S - non-humongous node
+     *                     s - external soft reference
+     *                     w - external weak reference
+     *                     Hs->Sw - 1st node is humongous, externally soft referenced and strong references to
+     *                     non-humongous node 2 which is externally weak referenced
+     *                     H->1 - humongous node connects to the first node of chain
+     * @return set of ReferenceInfo objects containing weak/soft reference to the graph node and other data on how
+     * objects should behave after gc
+     */
+    private static Set<ReferenceInfo<Object[]>> allocateObjectGraph(String testcaseData) {
+        Map<Object[], String> nodeIds = new HashMap<>();
+        Set<Object[]> humongousNodes = new HashSet<>();
+        Set<Object[]> externalSoftReferenced = new HashSet<>();
+        Set<Object[]> externalWeakReferenced = new HashSet<>();
+
+        Map<Predicate<TestcaseData.FinalParsedNode>, BiConsumer<TestcaseData.FinalParsedNode, Object[][]>> visitors
+                = new HashMap<>();
+
+        visitors.put((parsedNode -> true),
+                (parsedNode, objects) -> nodeIds.put(objects[Integer.valueOf(parsedNode.id)], parsedNode.id)
+        );
+
+        visitors.put((parsedNode -> parsedNode.isHumongous),
+                (parsedNode, objects) -> humongousNodes.add(objects[Integer.valueOf(parsedNode.id)])
+        );
+
+        visitors.put(parsedNode -> parsedNode.getReferencesTypes().stream().
+                        anyMatch(referenceType -> referenceType == ObjectGraph.ReferenceType.SOFT),
+                (parsedNode, objects) -> externalSoftReferenced.add(objects[Integer.valueOf(parsedNode.id)])
+        );
+
+        visitors.put(parsedNode -> parsedNode.getReferencesTypes().stream().
+                        anyMatch(referenceType -> referenceType == ObjectGraph.ReferenceType.WEAK),
+                (parsedNode, objects) -> externalWeakReferenced.add(objects[Integer.valueOf(parsedNode.id)])
+        );
+
+        List<TestcaseData.FinalParsedNode> internalParsedNodes = TestcaseData.parse(testcaseData);
+
+        Object[] root = ObjectGraph.generateObjectNodes(internalParsedNodes, visitors,
+                WhiteBox.getWhiteBox().g1RegionSize(), simpleAllocationSize);
+
+        ObjectGraph.propagateTransitiveProperty(humongousNodes, humongousNodes::add);
+        Set<Object[]> effectiveSoftReferenced = new HashSet<>();
+        ObjectGraph.propagateTransitiveProperty(externalSoftReferenced, effectiveSoftReferenced::add);
+
+        // Create external references
+        ReferenceQueue<Object[]> referenceQueue = new ReferenceQueue<>();
+        Set<Reference<Object[]>> externalRefs = new HashSet<>();
+
+        externalWeakReferenced.stream()
+                .forEach(objects -> externalRefs.add(new WeakReference<>(objects, referenceQueue)));
+        externalSoftReferenced.stream()
+                .forEach(objects -> externalRefs.add(new SoftReference<>(objects, referenceQueue)));
+
+        return externalRefs.stream()
+                .map(ref -> new ReferenceInfo<>(ref, testcaseData, nodeIds.get(ref.get()),
+                        effectiveSoftReferenced.contains(ref.get()), humongousNodes.contains(ref.get())))
+                .collect(Collectors.toSet());
+
+    }
+
+    /**
+     * Checks that object' state after gc is as expected
+     *
+     * @param nodeData array with information about nodes
+     * @param checker  consumer that checks node's state after gc and throws Error if it's wrong
+     */
+    private static void checkResults(Set<ReferenceInfo<Object[]>> nodeData, Consumer<ReferenceInfo<Object[]>> checker) {
+        nodeData.stream().forEach(checker::accept);
+    }
+
+    /**
+     * Checks that gc log contains what we expected and does not contain what we didn't expect
+     *
+     * @param gcLogName        gc log name
+     * @param shouldContain    list of tokens that should be contained in gc log
+     * @param shouldNotContain list of tokens that should not be contained in gc log
+     * @throws IOException if there are some issues with gc log
+     */
+    private static void checkGCLog(String gcLogName, List<String> shouldContain, List<String> shouldNotContain)
+            throws IOException {
+
+        if (gcLogName == null) {
+            return;
+        }
+        String gcLog = new String(Files.readAllBytes(new File(gcLogName).toPath()));
+
+        OutputAnalyzer outputAnalyzer = new OutputAnalyzer(gcLog, "");
+
+        shouldContain.stream().forEach(outputAnalyzer::shouldContain);
+        shouldNotContain.stream().forEach(outputAnalyzer::shouldNotContain);
+    }
+
+}

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/hotspot/test/gc/g1/humongousObjects/objectGraphTest/TestcaseData.java	Fri May 06 17:51:11 2016 +0300
@@ -0,0 +1,207 @@
+/*
+ * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved.
+ * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
+ *
+ * This code is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License version 2 only, as
+ * published by the Free Software Foundation.
+ *
+ * This code is distributed in the hope that it will be useful, but WITHOUT
+ * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+ * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+ * version 2 for more details (a copy is included in the LICENSE file that
+ * accompanied this code).
+ *
+ * You should have received a copy of the GNU General Public License version
+ * 2 along with this work; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
+ *
+ * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
+ * or visit www.oracle.com if you need additional information or have any
+ * questions.
+ *
+ */
+
+package gc.g1.humongousObjects.objectGraphTest;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collections;
+import java.util.List;
+import java.util.stream.Collectors;
+
+public final class TestcaseData {
+    /**
+     * Temporary node description used during parsing
+     */
+    private static class InternalParsedNode {
+        public String id;
+        public final ArrayList<Integer> connectedTo = new ArrayList<>();
+        public final ArrayList<Integer> connectedFrom = new ArrayList<>();
+        public final List<ObjectGraph.ReferenceType> referencesTypes = new ArrayList<>();
+        public boolean isHumongous;
+    }
+
+    /**
+     * Immutable node description.
+     * Contains:
+     * Node id
+     * Humongous flag
+     * List of external references' types
+     * List of nodes connected to
+     */
+    public static class FinalParsedNode {
+        public final String id;
+        public final boolean isHumongous;
+        private final List<ObjectGraph.ReferenceType> referencesTypes;
+        private final ArrayList<Integer> connectedTo;
+
+
+        public FinalParsedNode(InternalParsedNode internalParsedNode) {
+            referencesTypes = internalParsedNode.referencesTypes;
+            connectedTo = internalParsedNode.connectedTo;
+            id = internalParsedNode.id;
+            isHumongous = internalParsedNode.isHumongous;
+        }
+
+        public List<ObjectGraph.ReferenceType> getReferencesTypes() {
+            return Collections.unmodifiableList(referencesTypes);
+        }
+
+        public List<Integer> getConnectedTo() {
+            return Collections.unmodifiableList(connectedTo);
+        }
+    }
+
+    /**
+     * @param testcaseDesc testcase in the following notation:
+     *                     H - humongous node
+     *                     S - non-humongous node
+     *                     s - external soft reference
+     *                     w - external weak reference
+     *                     Hs->Sw - 1st node is humongous, externally soft referenced and strong references to non-humongous node 2 which is
+     *                     externally weak referenced
+     *                     H->1 - humongous node connects to the first node of chain
+     * @return list of nodes description in FinalParsedNode structure
+     */
+    public static List<FinalParsedNode> parse(String testcaseDesc) {
+        String[] nodes = testcaseDesc.split("-");
+        List<InternalParsedNode> internalParsedNodeList = new ArrayList<>();
+
+        for (int i = 0; i < nodes.length; ++i) {
+            String node = nodes[i];
+            InternalParsedNode nd;
+            if (node.contains("1")) {
+                nd = internalParsedNodeList.get(0);
+
+            } else {
+                nd = new InternalParsedNode();
+                internalParsedNodeList.add(nd);
+                nd.id = String.valueOf(i);
+            }
+
+            if (node.startsWith(">")) {
+                nd.connectedFrom.add(i - 1);
+            }
+            if (node.endsWith("<")) {
+                nd.connectedFrom.add(i + 1);
+            }
+            if (node.contains("w")) {
+                nd.referencesTypes.add(ObjectGraph.ReferenceType.WEAK);
+            }
+
+            if (node.contains("s")) {
+                nd.referencesTypes.add(ObjectGraph.ReferenceType.SOFT);
+            }
+            if (node.contains("H")) {
+                nd.isHumongous = true;
+            }
+
+            if (node.contains("S")) {
+                nd.isHumongous = false;
+            }
+        }
+
+        // we have connectedFrom but we need to get connectedTo
+        for (int i = 0; i < internalParsedNodeList.size(); ++i) {
+            for (Integer reference : internalParsedNodeList.get(i).connectedFrom) {
+                internalParsedNodeList.get(reference).connectedTo.add(i);
+            }
+        }
+
+        List<FinalParsedNode> finalParsedNodes = internalParsedNodeList.stream().map(FinalParsedNode::new)
+                .collect(Collectors.toList());
+
+        return finalParsedNodes;
+    }
+
+    /**
+     * @return List of pregenerated testing cases
+     */
+    public static List<String> getPregeneratedTestcases() {
+        return Arrays.asList(
+                "Hw",
+                "Sw",
+                "Sw->Hw",
+                "Hw->Sw",
+                "Sw<->Hw",
+                "Sw<->Sw",
+                "Hw->Sw->Sw",
+                "Hw->Sw->Sw",
+                "Sw->Hw->Sw",
+                "Hw->Sw->Sw->1",
+                "Sw->Hw->Sw->1",
+                "Sw->Hw->Hw->1",
+                "Sw<->Hw<->Hw->1",
+                "Sw<->Hw<->Sw->1",
+                "Sw->Hw<->Sw",
+                "Hs",
+                "Ss",
+                "Ss->Hs",
+                "Hs->Ss",
+                "Ss<->Hs",
+                "Ss<->Ss",
+                "Hs->Ss->Ss",
+                "Hs->Ss->Ss",
+                "Ss->Hs->Ss",
+                "Hs->Ss->Ss->1",
+                "Ss->Hs->Ss->1",
+                "Ss->Hs->Hs->1",
+                "Ss<->Hs<->Hs->1",
+                "Ss<->Hs<->Ss->1",
+                "Ss->Hs<->Ss",
+                "Ss->Hw",
+                "Sw->Hs",
+                "Hs->Sw",
+                "Hw->Ss",
+                "Ss<->Hw",
+                "Sw<->Hs",
+                "Ss<->Sw",
+                "Sw<->Ss",
+                "Hs->Sw->Sw",
+                "Hw->Ss->Sw",
+                "Hw->Sw->Ss",
+                "Ss->Hw->Sw",
+                "Sw->Hs->Sw",
+                "Sw->Hw->Ss",
+                "Hs->Sw->Sw->1",
+                "Hw->Ss->Sw->1",
+                "Hw->Sw->Ss->1",
+                "Ss->Hw->Sw->1",
+                "Ss->Hs->Sw->1",
+                "Sw->Hw->Ss->1",
+                "Ss->Hw->Hw->1",
+                "Sw->Hs->Hw->1",
+                "Sw->Hw->Hs->1",
+                "Ss<->Hw<->Hw->1",
+                "Sw<->Hs<->Hw->1",
+                "Sw<->Hw<->Hs->1",
+                "Ss<->Hw<->Sw->1",
+                "Sw<->Hs<->Sw->1",
+                "Sw<->Hw<->Ss->1",
+                "Ss->Hw<->Sw",
+                "Sw->Hs<->Sw",
+                "Sw->Hw<->Ss"
+        );
+    }
+}