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 

    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.shared.*;

    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 }