1/*
2 * Copyright (c) 2001, 2015, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25package sun.jvm.hotspot.utilities;
26
27import java.io.*;
28import java.util.*;
29import sun.jvm.hotspot.debugger.*;
30import sun.jvm.hotspot.gc.shared.*;
31import sun.jvm.hotspot.memory.*;
32import sun.jvm.hotspot.oops.*;
33import sun.jvm.hotspot.runtime.*;
34
35/** Finds all paths from roots to the specified set of objects. NOTE:
36    currently only a subset of the roots known to the VM is exposed to
37    the SA: objects on the stack, static fields in classes, and JNI
38    handles. These should be most of the user-level roots keeping
39    objects alive. */
40
41public class LivenessAnalysis {
42  // Used for debugging this code
43  private static final boolean DEBUG = false;
44
45  private LivenessAnalysis() {}
46
47  public static LivenessPathList computeAllLivenessPaths(Oop target) {
48    LivenessPathList list = computeAllLivenessPaths(target, true);
49    if ((list == null) || (list.size() == 0)) {
50      // Dead object
51      return null;
52    }
53    return list;
54  }
55
56  //---------------------------------------------------------------------------
57  // Internals only below this point
58  //
59
60  // Returns true if a new path was completed, otherwise false
61  // indicating there were no more paths to complete.
62  //
63  // The trimPathsThroughPopularObjects flag alters the behavior of
64  // the returned results. If true, then if multiple paths to
65  // different roots all go through a particular popular object, those
66  // paths will be truncated and only one (arbitrary one) will be be
67  // returned. On the other hand, if the target object itself is
68  // popular and there are multiple distinct paths to it (indicating
69  // that there are multiple objects pointing directly to it) then all
70  // of those paths will be reported.
71  private static LivenessPathList computeAllLivenessPaths(Oop target, boolean trimPathsThroughPopularObjects) {
72    ReversePtrs rev = VM.getVM().getRevPtrs();
73    if (rev == null) {
74      throw new RuntimeException("LivenessAnalysis requires ReversePtrs to have been computed");
75    }
76
77    // Currently the reverse pointer analysis returns non-null results
78    // only for live objects
79    if (rev.get(target) == null) {
80      // Object is dead
81      return null;
82    }
83
84    // HashSet of Oops acting as a bit mask indicating which ones have
85    // already been traversed
86    Set/*<Oop>*/ visitedOops = new HashSet/*<Oop>*/();
87
88      // IdentityHashMap of LivenessElements acting as a bit mask
89      // indicating which roots have already been traversed
90    Map/*<LivenessElement, LivenessElement>*/ visitedRoots =
91      new IdentityHashMap/*<LivenessElement, LivenessElement>*/();
92
93    visitedOops.add(target);
94
95    // Construct the initial LivenessPath
96    LivenessPathList list = new LivenessPathList();
97    {
98      LivenessPath path = new LivenessPath();
99      path.push(new LivenessPathElement(target, null));
100      list.add(path);
101    }
102
103    // Iterate until done
104    while (true) {
105      // See if there are any incomplete paths left
106      LivenessPath path = null;
107
108      for (int i = list.size() - 1; i >= 0; i--) {
109        LivenessPath tmp = list.get(i);
110        if (!tmp.isComplete()) {
111          path = tmp;
112          break;
113        }
114      }
115
116      // If no incomplete paths left, return
117      if (path == null) {
118        return list;
119      }
120
121      // Try to complete this path
122
123      // Remove the path from the list of reported ones in
124      // anticipation of completing it
125      list.remove(path);
126
127      try {
128        // Fetch next set of reverse pointers for the last object on
129        // the list
130        ArrayList/*<LivenessPathElement>*/ nextPtrs =
131          rev.get(path.peek().getObj());
132
133        // Depending on exactly what the reverse pointers analysis
134        // yields, these results may be null, although currently they
135        // won't be
136        if (nextPtrs != null) {
137          // Iterate these
138          for (Iterator iter = nextPtrs.iterator(); iter.hasNext(); ) {
139            LivenessPathElement nextElement = (LivenessPathElement) iter.next();
140            // See whether we've visited this element yet
141            if ((nextElement.isRoot() && (visitedRoots.get(nextElement) == null)) ||
142                (!nextElement.isRoot() && !visitedOops.contains(nextElement.getObj()))) {
143              // Show we've visited this one
144              if (nextElement.isRoot()) {
145                visitedRoots.put(nextElement, nextElement);
146              } else {
147                visitedOops.add(nextElement.getObj());
148              }
149
150              // Create a new LivenessPath for each one
151              LivenessPath nextPath = path.copy();
152              nextPath.push(nextElement);
153
154              // Regardless of whether we found a root, put the
155              // original path back on the list because we're going to
156              // do depth-first searching rather than breadth-first
157              list.add(path);
158              list.add(nextPath);
159
160              // See whether this path is complete (i.e., it
161              // terminates in a root)
162              if (trimPathsThroughPopularObjects && nextElement.isRoot()) {
163                // Go back through the path list and remove all
164                // incomplete paths ending in any of the intermediate
165                // (non-root and non-terminal) nodes in this path.
166                // This has the effect of removing multiple paths
167                // going through popular objects.
168                for (int i = 1; i < nextPath.size() - 1; i++) {
169                  LivenessPathElement el = nextPath.get(i);
170                  int j = 0;
171                  while (j < list.size()) {
172                    LivenessPath curPath = list.get(j);
173                    // We can use an object identity since these
174                    // intermediate nodes are canonicalized via the
175                    // ReversePtrsAnalysis
176                    if (curPath.peek() == el) {
177                      list.remove(curPath);
178                    } else {
179                      j++;
180                    }
181                  }
182                }
183              }
184
185              // Do depth-first searching, not breadth-first
186              break;
187            }
188          }
189        }
190      } catch (Exception e) {
191        System.err.println("LivenessAnalysis: WARNING: " + e +
192                           " during traversal");
193      }
194    }
195  }
196}
197