1 /*
   2  * Copyright (c) 2014, 2019, 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 #include "precompiled.hpp"
  26 #include "jfr/leakprofiler/chains/bitset.inline.hpp"
  27 #include "jfr/leakprofiler/chains/dfsClosure.hpp"
  28 #include "jfr/leakprofiler/chains/edge.hpp"
  29 #include "jfr/leakprofiler/chains/edgeStore.hpp"
  30 #include "jfr/leakprofiler/chains/rootSetClosure.hpp"
  31 #include "jfr/leakprofiler/utilities/granularTimer.hpp"
  32 #include "jfr/leakprofiler/utilities/rootType.hpp"
  33 #include "jfr/leakprofiler/utilities/unifiedOop.hpp"
  34 #include "memory/iterator.inline.hpp"
  35 #include "memory/resourceArea.hpp"
  36 #include "oops/access.inline.hpp"
  37 #include "oops/oop.inline.hpp"
  38 #include "utilities/align.hpp"
  39 
  40 // max dfs depth should not exceed size of stack
  41 static const size_t max_dfs_depth = 5000;
  42 
  43 EdgeStore* DFSClosure::_edge_store = NULL;
  44 BitSet* DFSClosure::_mark_bits = NULL;
  45 const Edge* DFSClosure::_start_edge = NULL;
  46 size_t DFSClosure::_max_depth = max_dfs_depth;
  47 bool DFSClosure::_ignore_root_set = false;
  48 
  49 DFSClosure::DFSClosure() :
  50   _parent(NULL),
  51   _reference(NULL),
  52   _depth(0) {
  53 }
  54 
  55 DFSClosure::DFSClosure(DFSClosure* parent, size_t depth) :
  56   _parent(parent),
  57   _reference(NULL),
  58   _depth(depth) {
  59 }
  60 
  61 void DFSClosure::find_leaks_from_edge(EdgeStore* edge_store,
  62                                       BitSet* mark_bits,
  63                                       const Edge* start_edge) {
  64   assert(edge_store != NULL, "invariant");
  65   assert(mark_bits != NULL," invariant");
  66   assert(start_edge != NULL, "invariant");
  67 
  68   _edge_store = edge_store;
  69   _mark_bits = mark_bits;
  70   _start_edge = start_edge;
  71   _ignore_root_set = false;
  72   assert(_max_depth == max_dfs_depth, "invariant");
  73 
  74   // Depth-first search, starting from a BFS egde
  75   DFSClosure dfs;
  76   start_edge->pointee()->oop_iterate(&dfs);
  77 }
  78 
  79 void DFSClosure::find_leaks_from_root_set(EdgeStore* edge_store,
  80                                           BitSet* mark_bits) {
  81   assert(edge_store != NULL, "invariant");
  82   assert(mark_bits != NULL, "invariant");
  83 
  84   _edge_store = edge_store;
  85   _mark_bits = mark_bits;
  86   _start_edge = NULL;
  87 
  88   // Mark root set, to avoid going sideways
  89   _max_depth = 1;
  90   _ignore_root_set = false;
  91   DFSClosure dfs;
  92   RootSetClosure<DFSClosure> rs(&dfs);
  93   rs.process();
  94 
  95   // Depth-first search
  96   _max_depth = max_dfs_depth;
  97   _ignore_root_set = true;
  98   assert(_start_edge == NULL, "invariant");
  99   rs.process();
 100 }
 101 
 102 void DFSClosure::closure_impl(const oop* reference, const oop pointee) {
 103   assert(pointee != NULL, "invariant");
 104   assert(reference != NULL, "invariant");
 105 
 106   if (GranularTimer::is_finished()) {
 107      return;
 108   }
 109   if (_depth == 0 && _ignore_root_set) {
 110     // Root set is already marked, but we want
 111     // to continue, so skip is_marked check.
 112     assert(_mark_bits->is_marked(pointee), "invariant");
 113   } else {
 114     if (_mark_bits->is_marked(pointee)) {
 115       return;
 116     }
 117   }
 118 
 119   _reference = reference;
 120   _mark_bits->mark_obj(pointee);
 121   assert(_mark_bits->is_marked(pointee), "invariant");
 122 
 123   // is the pointee a sample object?
 124   if (NULL == pointee->mark()) {
 125     add_chain();
 126   }
 127 
 128   assert(_max_depth >= 1, "invariant");
 129   if (_depth < _max_depth - 1) {
 130     DFSClosure next_level(this, _depth + 1);
 131     pointee->oop_iterate(&next_level);
 132   }
 133 }
 134 
 135 void DFSClosure::add_chain() {
 136   const size_t array_length = _depth + 2;
 137 
 138   ResourceMark rm;
 139   Edge* const chain = NEW_RESOURCE_ARRAY(Edge, array_length);
 140   size_t idx = 0;
 141 
 142   // aggregate from depth-first search
 143   const DFSClosure* c = this;
 144   while (c != NULL) {
 145     const size_t next = idx + 1;
 146     chain[idx++] = Edge(&chain[next], c->reference());
 147     c = c->parent();
 148   }
 149   assert(_depth + 1 == idx, "invariant");
 150   assert(array_length == idx + 1, "invariant");
 151 
 152   // aggregate from breadth-first search
 153   if (_start_edge != NULL) {
 154     chain[idx++] = *_start_edge;
 155   } else {
 156     chain[idx - 1] = Edge(NULL, chain[idx - 1].reference());
 157   }
 158   _edge_store->put_chain(chain, idx + (_start_edge != NULL ? _start_edge->distance_to_root() : 0));
 159 }
 160 
 161 void DFSClosure::do_oop(oop* ref) {
 162   assert(ref != NULL, "invariant");
 163   assert(is_aligned(ref, HeapWordSize), "invariant");
 164   const oop pointee = *ref;
 165   if (pointee != NULL) {
 166     closure_impl(ref, pointee);
 167   }
 168 }
 169 
 170 void DFSClosure::do_oop(narrowOop* ref) {
 171   assert(ref != NULL, "invariant");
 172   assert(is_aligned(ref, sizeof(narrowOop)), "invariant");
 173   const oop pointee = RawAccess<>::oop_load(ref);
 174   if (pointee != NULL) {
 175     closure_impl(UnifiedOop::encode(ref), pointee);
 176   }
 177 }
 178 
 179 void DFSClosure::do_root(const oop* ref) {
 180   assert(ref != NULL, "invariant");
 181   assert(is_aligned(ref, HeapWordSize), "invariant");
 182   const oop pointee = *ref;
 183   assert(pointee != NULL, "invariant");
 184   closure_impl(ref, pointee);
 185 }