|
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 } |