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 #include "precompiled.hpp"
  25 #include "jfr/leakprofiler/chains/bitset.hpp"
  26 #include "jfr/leakprofiler/chains/bfsClosure.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/edgeQueue.hpp"
  31 #include "jfr/leakprofiler/utilities/granularTimer.hpp"
  32 #include "jfr/leakprofiler/utilities/unifiedOop.hpp"
  33 #include "memory/iterator.inline.hpp"
  34 #include "memory/resourceArea.hpp"
  35 #include "oops/oop.inline.hpp"
  36 #include "utilities/align.hpp"
  37 
  38 BFSClosure::BFSClosure(EdgeQueue* edge_queue, EdgeStore* edge_store, BitSet* mark_bits) :
  39   _edge_queue(edge_queue),
  40   _edge_store(edge_store),
  41   _mark_bits(mark_bits),
  42   _current_parent(NULL),
  43   _current_frontier_level(0),
  44   _next_frontier_idx(0),
  45   _prev_frontier_idx(0),
  46   _dfs_fallback_idx(0),
  47   _use_dfs(false) {
  48 }
  49 
  50 static void log_frontier_level_summary(size_t level,
  51                                        size_t high_idx,
  52                                        size_t low_idx,
  53                                        size_t edge_size) {
  54   const size_t nof_edges_in_frontier = high_idx - low_idx;
  55   if (LogJFR && Verbose) tty->print_cr(
  56       "BFS front: " SIZE_FORMAT " edges: " SIZE_FORMAT " size: " SIZE_FORMAT " [KB]",
  57       level,
  58       nof_edges_in_frontier,
  59       (nof_edges_in_frontier * edge_size) / K
  60                         );
  61 }
  62 
  63 void BFSClosure::log_completed_frontier() const {
  64   log_frontier_level_summary(_current_frontier_level,
  65                              _next_frontier_idx,
  66                              _prev_frontier_idx,
  67                              _edge_queue->sizeof_edge());
  68 }
  69 
  70 void BFSClosure::log_dfs_fallback() const {
  71   const size_t edge_size = _edge_queue->sizeof_edge();
  72   // first complete summary for frontier in progress
  73   log_frontier_level_summary(_current_frontier_level,
  74                              _next_frontier_idx,
  75                              _prev_frontier_idx,
  76                              edge_size);
  77 
  78   // and then also complete the last frontier
  79   log_frontier_level_summary(_current_frontier_level + 1,
  80                              _edge_queue->bottom(),
  81                              _next_frontier_idx,
  82                              edge_size);
  83 
  84   // additional information about DFS fallover
  85   if (LogJFR && Verbose) tty->print_cr(
  86       "BFS front: " SIZE_FORMAT " filled edge queue at edge: " SIZE_FORMAT,
  87       _current_frontier_level,
  88       _dfs_fallback_idx
  89                         );
  90 
  91   const size_t nof_dfs_completed_edges = _edge_queue->bottom() - _dfs_fallback_idx;
  92   if (LogJFR && Verbose) tty->print_cr(
  93       "DFS to complete " SIZE_FORMAT " edges size: " SIZE_FORMAT " [KB]",
  94       nof_dfs_completed_edges,
  95       (nof_dfs_completed_edges * edge_size) / K
  96                         );
  97 }
  98 
  99 void BFSClosure::process() {
 100   process_root_set();
 101   process_queue();
 102 }
 103 
 104 void BFSClosure::process_root_set() {
 105   for (size_t idx = _edge_queue->bottom(); idx < _edge_queue->top(); ++idx) {
 106     const Edge* edge = _edge_queue->element_at(idx);
 107     assert(edge->parent() == NULL, "invariant");
 108     process(edge->reference(), edge->pointee());
 109   }
 110 }
 111 
 112 void BFSClosure::process(const oop* reference, const oop pointee) {
 113   closure_impl(reference, pointee);
 114 }
 115 void BFSClosure::closure_impl(const oop* reference, const oop pointee) {
 116   assert(reference != NULL, "invariant");
 117   assert(UnifiedOop::dereference(reference) == pointee, "invariant");
 118 
 119   if (GranularTimer::is_finished()) {
 120      return;
 121   }
 122 
 123   if (_use_dfs) {
 124     assert(_current_parent != NULL, "invariant");
 125     DFSClosure::find_leaks_from_edge(_edge_store, _mark_bits, _current_parent);
 126     return;
 127   }
 128 
 129   if (!_mark_bits->is_marked(pointee)) {
 130     _mark_bits->mark_obj(pointee);
 131     // is the pointee a sample object?
 132     if (NULL == pointee->mark()) {
 133       add_chain(reference, pointee);
 134     }
 135 
 136     // if we are processinig initial root set, don't add to queue
 137     if (_current_parent != NULL) {
 138       _edge_queue->add(_current_parent, reference);
 139     }
 140 
 141     if (_edge_queue->is_full()) {
 142       dfs_fallback();
 143     }
 144   }
 145 }
 146 
 147 void BFSClosure::add_chain(const oop* reference, const oop pointee) {
 148   assert(pointee != NULL, "invariant");
 149   assert(NULL == pointee->mark(), "invariant");
 150   Edge leak_edge(_current_parent, reference);
 151   _edge_store->put_chain(&leak_edge, _current_parent == NULL ? 1 : _current_frontier_level + 2);
 152 }
 153 
 154 void BFSClosure::dfs_fallback() {
 155   assert(_edge_queue->is_full(), "invariant");
 156   _use_dfs = true;
 157   _dfs_fallback_idx = _edge_queue->bottom();
 158   while (!_edge_queue->is_empty()) {
 159     const Edge* edge = _edge_queue->remove();
 160     if (edge->pointee() != NULL) {
 161       DFSClosure::find_leaks_from_edge(_edge_store, _mark_bits, edge);
 162     }
 163   }
 164 }
 165 
 166 void BFSClosure::process_queue() {
 167   assert(_current_frontier_level == 0, "invariant");
 168   assert(_next_frontier_idx == 0, "invariant");
 169   assert(_prev_frontier_idx == 0, "invariant");
 170 
 171   _next_frontier_idx = _edge_queue->top();
 172   while (!is_complete()) {
 173     iterate(_edge_queue->remove()); // edge_queue.remove() increments bottom
 174   }
 175 }
 176 
 177 void BFSClosure::step_frontier() const {
 178   log_completed_frontier();
 179   ++_current_frontier_level;
 180   _prev_frontier_idx = _next_frontier_idx;
 181   _next_frontier_idx = _edge_queue->top();
 182 }
 183 
 184 bool BFSClosure::is_complete() const {
 185   if (_edge_queue->bottom() < _next_frontier_idx) {
 186     return false;
 187   }
 188   if (_edge_queue->bottom() > _next_frontier_idx) {
 189     // fallback onto DFS as part of processing the frontier
 190     assert(_dfs_fallback_idx >= _prev_frontier_idx, "invariant");
 191     assert(_dfs_fallback_idx < _next_frontier_idx, "invariant");
 192     log_dfs_fallback();
 193     return true;
 194   }
 195   assert(_edge_queue->bottom() == _next_frontier_idx, "invariant");
 196   if (_edge_queue->is_empty()) {
 197     return true;
 198   }
 199   step_frontier();
 200   return false;
 201 }
 202 
 203 void BFSClosure::iterate(const Edge* parent) {
 204   assert(parent != NULL, "invariant");
 205   const oop pointee = parent->pointee();
 206   assert(pointee != NULL, "invariant");
 207   _current_parent = parent;
 208   pointee->oop_iterate(this);
 209 }
 210 
 211 void BFSClosure::do_oop(oop* ref) {
 212   assert(ref != NULL, "invariant");
 213   assert(is_aligned(ref, HeapWordSize), "invariant");
 214   const oop pointee = *ref;
 215   if (pointee != NULL) {
 216     closure_impl(ref, pointee);
 217   }
 218 }
 219 
 220 void BFSClosure::do_oop(narrowOop* ref) {
 221   assert(ref != NULL, "invariant");
 222   assert(is_aligned(ref, sizeof(narrowOop)), "invariant");
 223   const oop pointee = oopDesc::load_decode_heap_oop(ref);
 224   if (pointee != NULL) {
 225     closure_impl(UnifiedOop::encode(ref), pointee);
 226   }
 227 }
 228 
 229 void BFSClosure::do_root(const oop* ref) {
 230   assert(ref != NULL, "invariant");
 231   if (!_edge_queue->is_full()) {
 232     _edge_queue->add(NULL, ref);
 233   }
 234 }