1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/jfr/leakprofiler/chains/bfsClosure.cpp Mon Aug 12 18:30:40 2019 +0300
1.3 @@ -0,0 +1,241 @@
1.4 +/*
1.5 + * Copyright (c) 2014, 2018, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation.
1.11 + *
1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.15 + * version 2 for more details (a copy is included in the LICENSE file that
1.16 + * accompanied this code).
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License version
1.19 + * 2 along with this work; if not, write to the Free Software Foundation,
1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.21 + *
1.22 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.23 + * or visit www.oracle.com if you need additional information or have any
1.24 + * questions.
1.25 + *
1.26 + */
1.27 +#include "precompiled.hpp"
1.28 +#include "jfr/leakprofiler/chains/bitset.hpp"
1.29 +#include "jfr/leakprofiler/chains/bfsClosure.hpp"
1.30 +#include "jfr/leakprofiler/chains/dfsClosure.hpp"
1.31 +#include "jfr/leakprofiler/chains/edge.hpp"
1.32 +#include "jfr/leakprofiler/chains/edgeStore.hpp"
1.33 +#include "jfr/leakprofiler/chains/edgeQueue.hpp"
1.34 +#include "jfr/leakprofiler/utilities/granularTimer.hpp"
1.35 +#include "jfr/leakprofiler/utilities/unifiedOop.hpp"
1.36 +#include "memory/iterator.inline.hpp"
1.37 +#include "memory/resourceArea.hpp"
1.38 +#include "oops/oop.inline.hpp"
1.39 +#include "utilities/align.hpp"
1.40 +
1.41 +BFSClosure::BFSClosure(EdgeQueue* edge_queue, EdgeStore* edge_store, BitSet* mark_bits) :
1.42 + _edge_queue(edge_queue),
1.43 + _edge_store(edge_store),
1.44 + _mark_bits(mark_bits),
1.45 + _current_parent(NULL),
1.46 + _current_frontier_level(0),
1.47 + _next_frontier_idx(0),
1.48 + _prev_frontier_idx(0),
1.49 + _dfs_fallback_idx(0),
1.50 + _use_dfs(false) {
1.51 +}
1.52 +
1.53 +static void log_frontier_level_summary(size_t level,
1.54 + size_t high_idx,
1.55 + size_t low_idx,
1.56 + size_t edge_size) {
1.57 + const size_t nof_edges_in_frontier = high_idx - low_idx;
1.58 + if (LogJFR && Verbose) tty->print_cr(
1.59 + "BFS front: " SIZE_FORMAT " edges: " SIZE_FORMAT " size: " SIZE_FORMAT " [KB]",
1.60 + level,
1.61 + nof_edges_in_frontier,
1.62 + (nof_edges_in_frontier * edge_size) / K
1.63 + );
1.64 +}
1.65 +
1.66 +void BFSClosure::log_completed_frontier() const {
1.67 + log_frontier_level_summary(_current_frontier_level,
1.68 + _next_frontier_idx,
1.69 + _prev_frontier_idx,
1.70 + _edge_queue->sizeof_edge());
1.71 +}
1.72 +
1.73 +void BFSClosure::log_dfs_fallback() const {
1.74 + const size_t edge_size = _edge_queue->sizeof_edge();
1.75 + // first complete summary for frontier in progress
1.76 + log_frontier_level_summary(_current_frontier_level,
1.77 + _next_frontier_idx,
1.78 + _prev_frontier_idx,
1.79 + edge_size);
1.80 +
1.81 + // and then also complete the last frontier
1.82 + log_frontier_level_summary(_current_frontier_level + 1,
1.83 + _edge_queue->bottom(),
1.84 + _next_frontier_idx,
1.85 + edge_size);
1.86 +
1.87 + // additional information about DFS fallover
1.88 + if (LogJFR && Verbose) tty->print_cr(
1.89 + "BFS front: " SIZE_FORMAT " filled edge queue at edge: " SIZE_FORMAT,
1.90 + _current_frontier_level,
1.91 + _dfs_fallback_idx
1.92 + );
1.93 +
1.94 + const size_t nof_dfs_completed_edges = _edge_queue->bottom() - _dfs_fallback_idx;
1.95 + if (LogJFR && Verbose) tty->print_cr(
1.96 + "DFS to complete " SIZE_FORMAT " edges size: " SIZE_FORMAT " [KB]",
1.97 + nof_dfs_completed_edges,
1.98 + (nof_dfs_completed_edges * edge_size) / K
1.99 + );
1.100 +}
1.101 +
1.102 +void BFSClosure::process() {
1.103 +
1.104 + process_root_set();
1.105 + process_queue();
1.106 +}
1.107 +
1.108 +void BFSClosure::process_root_set() {
1.109 + for (size_t idx = _edge_queue->bottom(); idx < _edge_queue->top(); ++idx) {
1.110 + const Edge* edge = _edge_queue->element_at(idx);
1.111 + assert(edge->parent() == NULL, "invariant");
1.112 + process(edge->reference(), edge->pointee());
1.113 + }
1.114 +}
1.115 +
1.116 +void BFSClosure::process(const oop* reference, const oop pointee) {
1.117 + closure_impl(reference, pointee);
1.118 +}
1.119 +void BFSClosure::closure_impl(const oop* reference, const oop pointee) {
1.120 + assert(reference != NULL, "invariant");
1.121 + assert(UnifiedOop::dereference(reference) == pointee, "invariant");
1.122 +
1.123 + if (GranularTimer::is_finished()) {
1.124 + return;
1.125 + }
1.126 +
1.127 + if (_use_dfs) {
1.128 + assert(_current_parent != NULL, "invariant");
1.129 + DFSClosure::find_leaks_from_edge(_edge_store, _mark_bits, _current_parent);
1.130 + return;
1.131 + }
1.132 +
1.133 + if (!_mark_bits->is_marked(pointee)) {
1.134 + _mark_bits->mark_obj(pointee);
1.135 + // is the pointee a sample object?
1.136 + if (NULL == pointee->mark()) {
1.137 + add_chain(reference, pointee);
1.138 + }
1.139 +
1.140 + // if we are processinig initial root set, don't add to queue
1.141 + if (_current_parent != NULL) {
1.142 + assert(_current_parent->distance_to_root() == _current_frontier_level, "invariant");
1.143 + _edge_queue->add(_current_parent, reference);
1.144 + }
1.145 +
1.146 + if (_edge_queue->is_full()) {
1.147 + dfs_fallback();
1.148 + }
1.149 + }
1.150 +}
1.151 +
1.152 +void BFSClosure::add_chain(const oop* reference, const oop pointee) {
1.153 + assert(pointee != NULL, "invariant");
1.154 + assert(NULL == pointee->mark(), "invariant");
1.155 +
1.156 + const size_t length = _current_parent == NULL ? 1 : _current_parent->distance_to_root() + 2;
1.157 + ResourceMark rm;
1.158 + Edge* const chain = NEW_RESOURCE_ARRAY(Edge, length);
1.159 + size_t idx = 0;
1.160 + chain[idx++] = Edge(NULL, reference);
1.161 + // aggregate from breadth-first search
1.162 + const Edge* current = _current_parent;
1.163 + while (current != NULL) {
1.164 + chain[idx++] = Edge(NULL, current->reference());
1.165 + current = current->parent();
1.166 + }
1.167 + assert(length == idx, "invariant");
1.168 + _edge_store->add_chain(chain, length);
1.169 +}
1.170 +
1.171 +void BFSClosure::dfs_fallback() {
1.172 + assert(_edge_queue->is_full(), "invariant");
1.173 + _use_dfs = true;
1.174 + _dfs_fallback_idx = _edge_queue->bottom();
1.175 + while (!_edge_queue->is_empty()) {
1.176 + const Edge* edge = _edge_queue->remove();
1.177 + if (edge->pointee() != NULL) {
1.178 + DFSClosure::find_leaks_from_edge(_edge_store, _mark_bits, edge);
1.179 + }
1.180 + }
1.181 +}
1.182 +
1.183 +void BFSClosure::process_queue() {
1.184 + assert(_current_frontier_level == 0, "invariant");
1.185 + assert(_next_frontier_idx == 0, "invariant");
1.186 + assert(_prev_frontier_idx == 0, "invariant");
1.187 +
1.188 + _next_frontier_idx = _edge_queue->top();
1.189 + while (!is_complete()) {
1.190 + iterate(_edge_queue->remove()); // edge_queue.remove() increments bottom
1.191 + }
1.192 +}
1.193 +
1.194 +void BFSClosure::step_frontier() const {
1.195 + log_completed_frontier();
1.196 + ++_current_frontier_level;
1.197 + _prev_frontier_idx = _next_frontier_idx;
1.198 + _next_frontier_idx = _edge_queue->top();
1.199 +}
1.200 +
1.201 +bool BFSClosure::is_complete() const {
1.202 + if (_edge_queue->bottom() < _next_frontier_idx) {
1.203 + return false;
1.204 + }
1.205 + if (_edge_queue->bottom() > _next_frontier_idx) {
1.206 + // fallback onto DFS as part of processing the frontier
1.207 + assert(_dfs_fallback_idx >= _prev_frontier_idx, "invariant");
1.208 + assert(_dfs_fallback_idx < _next_frontier_idx, "invariant");
1.209 + log_dfs_fallback();
1.210 + return true;
1.211 + }
1.212 + assert(_edge_queue->bottom() == _next_frontier_idx, "invariant");
1.213 + if (_edge_queue->is_empty()) {
1.214 + return true;
1.215 + }
1.216 + step_frontier();
1.217 + return false;
1.218 +}
1.219 +
1.220 +void BFSClosure::iterate(const Edge* parent) {
1.221 + assert(parent != NULL, "invariant");
1.222 + const oop pointee = parent->pointee();
1.223 + assert(pointee != NULL, "invariant");
1.224 + _current_parent = parent;
1.225 + pointee->oop_iterate(this);
1.226 +}
1.227 +
1.228 +void BFSClosure::do_oop(oop* ref) {
1.229 + assert(ref != NULL, "invariant");
1.230 + assert(is_aligned(ref, HeapWordSize), "invariant");
1.231 + const oop pointee = *ref;
1.232 + if (pointee != NULL) {
1.233 + closure_impl(ref, pointee);
1.234 + }
1.235 +}
1.236 +
1.237 +void BFSClosure::do_oop(narrowOop* ref) {
1.238 + assert(ref != NULL, "invariant");
1.239 + assert(is_aligned(ref, sizeof(narrowOop)), "invariant");
1.240 + const oop pointee = oopDesc::load_decode_heap_oop(ref);
1.241 + if (pointee != NULL) {
1.242 + closure_impl(UnifiedOop::encode(ref), pointee);
1.243 + }
1.244 +}
