1 /* 2 * Copyright (c) 2001, 2006, 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 25 package sun.jvm.hotspot.utilities; 26 27 import java.io.*; 28 import java.util.*; 29 import sun.jvm.hotspot.debugger.*; 30 import sun.jvm.hotspot.gc_interface.*; 31 import sun.jvm.hotspot.memory.*; 32 import sun.jvm.hotspot.oops.*; 33 import 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 41 public 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 }