1 /* 2 * Copyright (c) 2002, 2012, 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 import sun.jvm.hotspot.utilities.*; 35 36 /** For a set of known roots, descends recursively into the object 37 graph, for each object recording those objects (and their fields) 38 which point to it. NOTE: currently only a subset of the roots 39 known to the VM is exposed to the SA: objects on the stack, static 40 fields in classes, and JNI handles. These should be most of the 41 user-level roots keeping objects alive. */ 42 43 public class ReversePtrsAnalysis { 44 // Used for debugging this code 45 private static final boolean DEBUG = false; 46 47 public ReversePtrsAnalysis() { 48 } 49 50 /** Sets an optional progress thunk */ 51 public void setHeapProgressThunk(HeapProgressThunk thunk) { 52 progressThunk = thunk; 53 } 54 55 56 /** Runs the analysis algorithm */ 57 public void run() { 58 if (VM.getVM().getRevPtrs() != null) { 59 return; // Assume already done 60 } 61 62 VM vm = VM.getVM(); 63 rp = new ReversePtrs(); 64 vm.setRevPtrs(rp); 65 Universe universe = vm.getUniverse(); 66 CollectedHeap collHeap = universe.heap(); 67 usedSize = collHeap.used(); 68 visitedSize = 0; 69 70 // Note that an experiment to iterate the heap linearly rather 71 // than in recursive-descent order has been done. It turns out 72 // that the recursive-descent algorithm is nearly twice as fast 73 // due to the fact that it scans only live objects and (currently) 74 // only a fraction of the perm gen, namely the static fields 75 // contained in instanceKlasses. (Iterating the heap linearly 76 // would also change the semantics of the result so that 77 // ReversePtrs.get() would return a non-null value even for dead 78 // objects.) Nonetheless, the reverse pointer computation is still 79 // quite slow and optimization in field iteration of objects 80 // should be done. 81 82 if (progressThunk != null) { 83 // Get it started 84 progressThunk.heapIterationFractionUpdate(0); 85 } 86 87 // Allocate mark bits for heap 88 markBits = new MarkBits(collHeap); 89 90 // Get a hold of the object heap 91 heap = vm.getObjectHeap(); 92 93 // Do each thread's roots 94 for (JavaThread thread = VM.getVM().getThreads().first(); 95 thread != null; 96 thread = thread.next()) { 97 ByteArrayOutputStream bos = new ByteArrayOutputStream(); 98 thread.printThreadIDOn(new PrintStream(bos)); 99 String threadDesc = 100 " in thread \"" + thread.getThreadName() + 101 "\" (id " + bos.toString() + ")"; 102 doStack(thread, 103 new RootVisitor("Stack root" + threadDesc)); 104 doJNIHandleBlock(thread.activeHandles(), 105 new RootVisitor("JNI handle root" + threadDesc)); 106 } 107 108 // Do global JNI handles 109 JNIHandles handles = VM.getVM().getJNIHandles(); 110 doJNIHandleBlock(handles.globalHandles(), 111 new RootVisitor("Global JNI handle root")); 112 doJNIHandleBlock(handles.weakGlobalHandles(), 113 new RootVisitor("Weak global JNI handle root")); 114 115 // Do Java-level static fields 116 SystemDictionary sysDict = VM.getVM().getSystemDictionary(); 117 sysDict.allClassesDo(new SystemDictionary.ClassVisitor() { 118 119 public void visit(Klass k) { 120 if (k instanceof InstanceKlass) { 121 final InstanceKlass ik = (InstanceKlass)k; 122 ik.iterateStaticFields( 123 new DefaultOopVisitor() { 124 public void doOop(OopField field, boolean isVMField) { 125 Oop next = field.getValue(getObj()); 126 NamedFieldIdentifier nfi = new NamedFieldIdentifier("Static field \"" + 127 field.getID().getName() + 128 "\" in class \"" + 129 ik.getName().asString() + "\""); 130 LivenessPathElement lp = new LivenessPathElement(null, nfi); 131 rp.put(lp, next); 132 try { 133 markAndTraverse(next); 134 } catch (AddressException e) { 135 System.err.print("RevPtrs analysis: WARNING: AddressException at 0x" + 136 Long.toHexString(e.getAddress()) + 137 " while traversing static fields of InstanceKlass "); 138 ik.printValueOn(System.err); 139 System.err.println(); 140 } catch (UnknownOopException e) { 141 System.err.println("RevPtrs analysis: WARNING: UnknownOopException while " + 142 "traversing static fields of InstanceKlass "); 143 ik.printValueOn(System.err); 144 System.err.println(); 145 } 146 } 147 }); 148 } 149 } 150 }); 151 152 if (progressThunk != null) { 153 progressThunk.heapIterationComplete(); 154 } 155 156 // Clear out markBits 157 markBits = null; 158 } 159 160 161 //--------------------------------------------------------------------------- 162 // Internals only below this point 163 // 164 private HeapProgressThunk progressThunk; 165 private long usedSize; 166 private long visitedSize; 167 private double lastNotificationFraction; 168 private static final double MINIMUM_NOTIFICATION_FRACTION = 0.01; 169 private ObjectHeap heap; 170 private MarkBits markBits; 171 private int depth; // Debugging only 172 private ReversePtrs rp; 173 174 private void markAndTraverse(OopHandle handle) { 175 try { 176 markAndTraverse(heap.newOop(handle)); 177 } catch (AddressException e) { 178 System.err.println("RevPtrs analysis: WARNING: AddressException at 0x" + 179 Long.toHexString(e.getAddress()) + 180 " while traversing oop at " + handle); 181 } catch (UnknownOopException e) { 182 System.err.println("RevPtrs analysis: WARNING: UnknownOopException for " + 183 "oop at " + handle); 184 } 185 } 186 187 private void printHeader() { 188 for (int i = 0; i < depth; i++) { 189 System.err.print(" "); 190 } 191 } 192 193 private void markAndTraverse(final Oop obj) { 194 195 // End of path 196 if (obj == null) { 197 return; 198 } 199 200 // Visited object 201 if (!markBits.mark(obj)) { 202 return; 203 } 204 205 // Root of work list for objects to be visited. A simple 206 // stack for saving new objects to be analyzed. 207 208 final Stack workList = new Stack(); 209 210 // Next object to be visited. 211 Oop next = obj; 212 213 try { 214 // Node in the list currently being visited. 215 216 while (true) { 217 final Oop currObj = next; 218 219 // For the progress meter 220 if (progressThunk != null) { 221 visitedSize += currObj.getObjectSize(); 222 double curFrac = (double) visitedSize / (double) usedSize; 223 if (curFrac > 224 lastNotificationFraction + MINIMUM_NOTIFICATION_FRACTION) { 225 progressThunk.heapIterationFractionUpdate(curFrac); 226 lastNotificationFraction = curFrac; 227 } 228 } 229 230 if (DEBUG) { 231 ++depth; 232 printHeader(); 233 System.err.println("ReversePtrs.markAndTraverse(" + 234 currObj.getHandle() + ")"); 235 } 236 237 // Iterate over the references in the object. Do the 238 // reverse pointer analysis for each reference. 239 // Add the reference to the work-list so that its 240 // references will be visited. 241 currObj.iterate(new DefaultOopVisitor() { 242 public void doOop(OopField field, boolean isVMField) { 243 // "field" refers to a reference in currObj 244 Oop next = field.getValue(currObj); 245 rp.put(new LivenessPathElement(currObj, field.getID()), next); 246 if ((next != null) && markBits.mark(next)) { 247 workList.push(next); 248 } 249 } 250 }, false); 251 252 if (DEBUG) { 253 --depth; 254 } 255 256 // Get the next object to visit. 257 next = (Oop) workList.pop(); 258 } 259 } catch (EmptyStackException e) { 260 // Done 261 } catch (NullPointerException e) { 262 System.err.println("ReversePtrs: WARNING: " + e + 263 " during traversal"); 264 } catch (Exception e) { 265 System.err.println("ReversePtrs: WARNING: " + e + 266 " during traversal"); 267 } 268 } 269 270 271 class RootVisitor implements AddressVisitor { 272 RootVisitor(String baseRootDescription) { 273 this.baseRootDescription = baseRootDescription; 274 } 275 276 public void visitAddress(Address addr) { 277 Oop next = heap.newOop(addr.getOopHandleAt(0)); 278 LivenessPathElement lp = new LivenessPathElement(null, 279 new NamedFieldIdentifier(baseRootDescription + 280 " @ " + addr)); 281 rp.put(lp, next); 282 markAndTraverse(next); 283 } 284 285 public void visitCompOopAddress(Address addr) { 286 Oop next = heap.newOop(addr.getCompOopHandleAt(0)); 287 LivenessPathElement lp = new LivenessPathElement(null, 288 new NamedFieldIdentifier(baseRootDescription + 289 " @ " + addr)); 290 rp.put(lp, next); 291 markAndTraverse(next); 292 } 293 294 private String baseRootDescription; 295 } 296 297 // Traverse the roots on a given thread's stack 298 private void doStack(JavaThread thread, AddressVisitor oopVisitor) { 299 for (StackFrameStream fst = new StackFrameStream(thread); !fst.isDone(); fst.next()) { 300 fst.getCurrent().oopsDo(oopVisitor, fst.getRegisterMap()); 301 } 302 } 303 304 // Traverse a JNIHandleBlock 305 private void doJNIHandleBlock(JNIHandleBlock handles, AddressVisitor oopVisitor) { 306 handles.oopsDo(oopVisitor); 307 } 308 }