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