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