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