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