1 /*

     2  * Copyright (c) 2014, 2018, 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 "logging/log.hpp"

    34 #include "memory/resourceArea.hpp"

    35 #include "oops/access.inline.hpp"

    36 #include "oops/oop.inline.hpp"

    37 #include "utilities/align.hpp"

    38 

    39 BFSClosure::BFSClosure(EdgeQueue* edge_queue, EdgeStore* edge_store, BitSet* mark_bits) :

    40   _edge_queue(edge_queue),

    41   _edge_store(edge_store),

    42   _mark_bits(mark_bits),

    43   _current_parent(NULL),

    44   _current_frontier_level(0),

    45   _next_frontier_idx(0),

    46   _prev_frontier_idx(0),

    47   _dfs_fallback_idx(0),

    48   _use_dfs(false) {

    49 }

    50 

    51 static void log_frontier_level_summary(size_t level,

    52                                        size_t high_idx,

    53                                        size_t low_idx,

    54                                        size_t edge_size) {

    55   const size_t nof_edges_in_frontier = high_idx - low_idx;

    56   log_trace(jfr, system)(

    57       "BFS front: " SIZE_FORMAT " edges: " SIZE_FORMAT " size: " SIZE_FORMAT " [KB]",

    58       level,

    59       nof_edges_in_frontier,

    60       (nof_edges_in_frontier * edge_size) / K

    61                         );

    62 }

    63 

    64 void BFSClosure::log_completed_frontier() const {

    65   log_frontier_level_summary(_current_frontier_level,

    66                              _next_frontier_idx,

    67                              _prev_frontier_idx,

    68                              _edge_queue->sizeof_edge());

    69 }

    70 

    71 void BFSClosure::log_dfs_fallback() const {

    72   const size_t edge_size = _edge_queue->sizeof_edge();

    73   // first complete summary for frontier in progress

    74   log_frontier_level_summary(_current_frontier_level,

    75                              _next_frontier_idx,

    76                              _prev_frontier_idx,

    77                              edge_size);

    78 

    79   // and then also complete the last frontier

    80   log_frontier_level_summary(_current_frontier_level + 1,

    81                              _edge_queue->bottom(),

    82                              _next_frontier_idx,

    83                              edge_size);

    84 

    85   // additional information about DFS fallover

    86   log_trace(jfr, system)(

    87       "BFS front: " SIZE_FORMAT " filled edge queue at edge: " SIZE_FORMAT,

    88       _current_frontier_level,

    89       _dfs_fallback_idx

    90                         );

    91 

    92   const size_t nof_dfs_completed_edges = _edge_queue->bottom() - _dfs_fallback_idx;

    93   log_trace(jfr, system)(

    94       "DFS to complete " SIZE_FORMAT " edges size: " SIZE_FORMAT " [KB]",

    95       nof_dfs_completed_edges,

    96       (nof_dfs_completed_edges * edge_size) / K

    97                         );

    98 }

    99 

   100 void BFSClosure::process() {

   101 

   102   process_root_set();

   103   process_queue();

   104 }

   105 

   106 void BFSClosure::process_root_set() {

   107   for (size_t idx = _edge_queue->bottom(); idx < _edge_queue->top(); ++idx) {

   108     const Edge* edge = _edge_queue->element_at(idx);

   109     assert(edge->parent() == NULL, "invariant");

   110     process(edge->reference(), edge->pointee());

   111   }

   112 }

   113 

   114 void BFSClosure::process(const oop* reference, const oop pointee) {

   115   closure_impl(reference, pointee);

   116 }

   117 void BFSClosure::closure_impl(const oop* reference, const oop pointee) {

   118   assert(reference != NULL, "invariant");

   119   assert(UnifiedOop::dereference(reference) == pointee, "invariant");

   120 

   121   if (GranularTimer::is_finished()) {

   122      return;

   123   }

   124 

   125   if (_use_dfs) {

   126     assert(_current_parent != NULL, "invariant");

   127     DFSClosure::find_leaks_from_edge(_edge_store, _mark_bits, _current_parent);

   128     return;

   129   }

   130 

   131   if (!_mark_bits->is_marked(pointee)) {

   132     _mark_bits->mark_obj(pointee);

   133     // is the pointee a sample object?

   134     if (NULL == pointee->mark()) {

   135       add_chain(reference, pointee);

   136     }

   137 

   138     // if we are processinig initial root set, don't add to queue

   139     if (_current_parent != NULL) {

   140       assert(_current_parent->distance_to_root() == _current_frontier_level, "invariant");

   141       _edge_queue->add(_current_parent, reference);

   142     }

   143 

   144     if (_edge_queue->is_full()) {

   145       dfs_fallback();

   146     }

   147   }

   148 }

   149 

   150 void BFSClosure::add_chain(const oop* reference, const oop pointee) {

   151   assert(pointee != NULL, "invariant");

   152   assert(NULL == pointee->mark(), "invariant");

   153 

   154   const size_t length = _current_parent == NULL ? 1 : _current_parent->distance_to_root() + 2;

   155   ResourceMark rm;

   156   Edge* const chain = NEW_RESOURCE_ARRAY(Edge, length);

   157   size_t idx = 0;

   158   chain[idx++] = Edge(NULL, reference);

   159   // aggregate from breadth-first search

   160   const Edge* current = _current_parent;

   161   while (current != NULL) {

   162     chain[idx++] = Edge(NULL, current->reference());

   163     current = current->parent();

   164   }

   165   assert(length == idx, "invariant");

   166   _edge_store->add_chain(chain, length);

   167 }

   168 

   169 void BFSClosure::dfs_fallback() {

   170   assert(_edge_queue->is_full(), "invariant");

   171   _use_dfs = true;

   172   _dfs_fallback_idx = _edge_queue->bottom();

   173   while (!_edge_queue->is_empty()) {

   174     const Edge* edge = _edge_queue->remove();

   175     if (edge->pointee() != NULL) {

   176       DFSClosure::find_leaks_from_edge(_edge_store, _mark_bits, edge);

   177     }

   178   }

   179 }

   180 

   181 void BFSClosure::process_queue() {

   182   assert(_current_frontier_level == 0, "invariant");

   183   assert(_next_frontier_idx == 0, "invariant");

   184   assert(_prev_frontier_idx == 0, "invariant");

   185 

   186   _next_frontier_idx = _edge_queue->top();

   187   while (!is_complete()) {

   188     iterate(_edge_queue->remove()); // edge_queue.remove() increments bottom

   189   }

   190 }

   191 

   192 void BFSClosure::step_frontier() const {

   193   log_completed_frontier();

   194   ++_current_frontier_level;

   195   _prev_frontier_idx = _next_frontier_idx;

   196   _next_frontier_idx = _edge_queue->top();

   197 }

   198 

   199 bool BFSClosure::is_complete() const {

   200   if (_edge_queue->bottom() < _next_frontier_idx) {

   201     return false;

   202   }

   203   if (_edge_queue->bottom() > _next_frontier_idx) {

   204     // fallback onto DFS as part of processing the frontier

   205     assert(_dfs_fallback_idx >= _prev_frontier_idx, "invariant");

   206     assert(_dfs_fallback_idx < _next_frontier_idx, "invariant");

   207     log_dfs_fallback();

   208     return true;

   209   }

   210   assert(_edge_queue->bottom() == _next_frontier_idx, "invariant");

   211   if (_edge_queue->is_empty()) {

   212     return true;

   213   }

   214   step_frontier();

   215   return false;

   216 }

   217 

   218 void BFSClosure::iterate(const Edge* parent) {

   219   assert(parent != NULL, "invariant");

   220   const oop pointee = parent->pointee();

   221   assert(pointee != NULL, "invariant");

   222   _current_parent = parent;

   223   pointee->oop_iterate(this);

   224 }

   225 

   226 void BFSClosure::do_oop(oop* ref) {

   227   assert(ref != NULL, "invariant");

   228   assert(is_aligned(ref, HeapWordSize), "invariant");

   229   const oop pointee = *ref;

   230   if (pointee != NULL) {

   231     closure_impl(ref, pointee);

   232   }

   233 }

   234 

   235 void BFSClosure::do_oop(narrowOop* ref) {

   236   assert(ref != NULL, "invariant");

   237   assert(is_aligned(ref, sizeof(narrowOop)), "invariant");

   238   const oop pointee = RawAccess<>::oop_load(ref);

   239   if (pointee != NULL) {

   240     closure_impl(UnifiedOop::encode(ref), pointee);

   241   }

   242 }