1 /*

     2  * Copyright (c) 2002, 2017, 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 }