/*
 * Copyright (c) 2001, 2015, 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 sun.jvm.hotspot.utilities;

import java.io.*;
import java.util.*;
import sun.jvm.hotspot.debugger.*;
import sun.jvm.hotspot.gc.shared.*;
import sun.jvm.hotspot.memory.*;
import sun.jvm.hotspot.oops.*;
import sun.jvm.hotspot.runtime.*;

Finds all paths from roots to the specified set of objects. NOTE: currently only a subset of the roots known to the VM is exposed to the SA: objects on the stack, static fields in classes, and JNI handles. These should be most of the user-level roots keeping objects alive.
/** Finds all paths from roots to the specified set of objects. NOTE: currently only a subset of the roots known to the VM is exposed to the SA: objects on the stack, static fields in classes, and JNI handles. These should be most of the user-level roots keeping objects alive. */
public class LivenessAnalysis { // Used for debugging this code private static final boolean DEBUG = false; private LivenessAnalysis() {} public static LivenessPathList computeAllLivenessPaths(Oop target) { LivenessPathList list = computeAllLivenessPaths(target, true); if ((list == null) || (list.size() == 0)) { // Dead object return null; } return list; } //--------------------------------------------------------------------------- // Internals only below this point // // Returns true if a new path was completed, otherwise false // indicating there were no more paths to complete. // // The trimPathsThroughPopularObjects flag alters the behavior of // the returned results. If true, then if multiple paths to // different roots all go through a particular popular object, those // paths will be truncated and only one (arbitrary one) will be be // returned. On the other hand, if the target object itself is // popular and there are multiple distinct paths to it (indicating // that there are multiple objects pointing directly to it) then all // of those paths will be reported. private static LivenessPathList computeAllLivenessPaths(Oop target, boolean trimPathsThroughPopularObjects) { ReversePtrs rev = VM.getVM().getRevPtrs(); if (rev == null) { throw new RuntimeException("LivenessAnalysis requires ReversePtrs to have been computed"); } // Currently the reverse pointer analysis returns non-null results // only for live objects if (rev.get(target) == null) { // Object is dead return null; } // HashSet of Oops acting as a bit mask indicating which ones have // already been traversed Set/*<Oop>*/ visitedOops = new HashSet/*<Oop>*/(); // IdentityHashMap of LivenessElements acting as a bit mask // indicating which roots have already been traversed Map/*<LivenessElement, LivenessElement>*/ visitedRoots = new IdentityHashMap/*<LivenessElement, LivenessElement>*/(); visitedOops.add(target); // Construct the initial LivenessPath LivenessPathList list = new LivenessPathList(); { LivenessPath path = new LivenessPath(); path.push(new LivenessPathElement(target, null)); list.add(path); } // Iterate until done while (true) { // See if there are any incomplete paths left LivenessPath path = null; for (int i = list.size() - 1; i >= 0; i--) { LivenessPath tmp = list.get(i); if (!tmp.isComplete()) { path = tmp; break; } } // If no incomplete paths left, return if (path == null) { return list; } // Try to complete this path // Remove the path from the list of reported ones in // anticipation of completing it list.remove(path); try { // Fetch next set of reverse pointers for the last object on // the list ArrayList/*<LivenessPathElement>*/ nextPtrs = rev.get(path.peek().getObj()); // Depending on exactly what the reverse pointers analysis // yields, these results may be null, although currently they // won't be if (nextPtrs != null) { // Iterate these for (Iterator iter = nextPtrs.iterator(); iter.hasNext(); ) { LivenessPathElement nextElement = (LivenessPathElement) iter.next(); // See whether we've visited this element yet if ((nextElement.isRoot() && (visitedRoots.get(nextElement) == null)) || (!nextElement.isRoot() && !visitedOops.contains(nextElement.getObj()))) { // Show we've visited this one if (nextElement.isRoot()) { visitedRoots.put(nextElement, nextElement); } else { visitedOops.add(nextElement.getObj()); } // Create a new LivenessPath for each one LivenessPath nextPath = path.copy(); nextPath.push(nextElement); // Regardless of whether we found a root, put the // original path back on the list because we're going to // do depth-first searching rather than breadth-first list.add(path); list.add(nextPath); // See whether this path is complete (i.e., it // terminates in a root) if (trimPathsThroughPopularObjects && nextElement.isRoot()) { // Go back through the path list and remove all // incomplete paths ending in any of the intermediate // (non-root and non-terminal) nodes in this path. // This has the effect of removing multiple paths // going through popular objects. for (int i = 1; i < nextPath.size() - 1; i++) { LivenessPathElement el = nextPath.get(i); int j = 0; while (j < list.size()) { LivenessPath curPath = list.get(j); // We can use an object identity since these // intermediate nodes are canonicalized via the // ReversePtrsAnalysis if (curPath.peek() == el) { list.remove(curPath); } else { j++; } } } } // Do depth-first searching, not breadth-first break; } } } } catch (Exception e) { System.err.println("LivenessAnalysis: WARNING: " + e + " during traversal"); } } } }