1 /*
2 * Copyright (c) 2014, 2021, 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
25 #include "precompiled.hpp"
26 #include "jfr/leakprofiler/chains/edgeStore.hpp"
27 #include "jfr/leakprofiler/chains/edgeUtils.hpp"
28 #include "jfr/leakprofiler/sampling/objectSample.hpp"
29 #include "jfr/leakprofiler/utilities/unifiedOopRef.inline.hpp"
30 #include "oops/oop.inline.hpp"
31 #include "runtime/safepoint.hpp"
32
33 StoredEdge::StoredEdge(const Edge* parent, UnifiedOopRef reference) : Edge(parent, reference), _gc_root_id(0), _skip_length(0) {}
34
35 StoredEdge::StoredEdge(const Edge& edge) : Edge(edge), _gc_root_id(0), _skip_length(0) {}
36
37 StoredEdge::StoredEdge(const StoredEdge& edge) : Edge(edge), _gc_root_id(edge._gc_root_id), _skip_length(edge._skip_length) {}
38
39 traceid EdgeStore::_edge_id_counter = 0;
40
41 bool EdgeStore::is_empty() const {
42 return !_edges->has_entries();
43 }
44
45 void EdgeStore::on_link(EdgeEntry* entry) {
46 assert(entry != NULL, "invariant");
47 assert(entry->id() == 0, "invariant");
48 entry->set_id(++_edge_id_counter);
49 }
50
51 bool EdgeStore::on_equals(uintptr_t hash, const EdgeEntry* entry) {
52 assert(entry != NULL, "invariant");
53 assert(entry->hash() == hash, "invariant");
54 return true;
55 }
56
57 void EdgeStore::on_unlink(EdgeEntry* entry) {
58 assert(entry != NULL, "invariant");
59 // nothing
60 }
61
62 #ifdef ASSERT
63 bool EdgeStore::contains(UnifiedOopRef reference) const {
64 return get(reference) != NULL;
65 }
66 #endif
67
68 StoredEdge* EdgeStore::get(UnifiedOopRef reference) const {
69 assert(!reference.is_null(), "invariant");
70 EdgeEntry* const entry = _edges->lookup_only(reference.addr<uintptr_t>());
71 return entry != NULL ? entry->literal_addr() : NULL;
72 }
73
74 StoredEdge* EdgeStore::put(UnifiedOopRef reference) {
75 assert(!reference.is_null(), "invariant");
76 const StoredEdge e(NULL, reference);
77 assert(NULL == _edges->lookup_only(reference.addr<uintptr_t>()), "invariant");
78 EdgeEntry& entry = _edges->put(reference.addr<uintptr_t>(), e);
79 return entry.literal_addr();
80 }
81
82 traceid EdgeStore::get_id(const Edge* edge) const {
83 assert(edge != NULL, "invariant");
84 EdgeEntry* const entry = _edges->lookup_only(edge->reference().addr<uintptr_t>());
85 assert(entry != NULL, "invariant");
86 return entry->id();
87 }
88
89 traceid EdgeStore::gc_root_id(const Edge* edge) const {
90 assert(edge != NULL, "invariant");
91 const traceid gc_root_id = static_cast<const StoredEdge*>(edge)->gc_root_id();
92 if (gc_root_id != 0) {
93 return gc_root_id;
94 }
95 // not cached
96 assert(edge != NULL, "invariant");
97 const Edge* const root = EdgeUtils::root(*edge);
98 assert(root != NULL, "invariant");
99 assert(root->parent() == NULL, "invariant");
100 return get_id(root);
101 }
102
103 static const Edge* get_skip_ancestor(const Edge** current, size_t distance_to_root, size_t* skip_length) {
104 assert(distance_to_root >= EdgeUtils::root_context, "invariant");
105 assert(*skip_length == 0, "invariant");
106 *skip_length = distance_to_root - (EdgeUtils::root_context - 1);
107 const Edge* const target = EdgeUtils::ancestor(**current, *skip_length);
108 assert(target != NULL, "invariant");
109 assert(target->distance_to_root() + 1 == EdgeUtils::root_context, "invariant");
110 return target;
111 }
112
113 bool EdgeStore::put_skip_edge(StoredEdge** previous, const Edge** current, size_t distance_to_root) {
114 assert(*previous != NULL, "invariant");
115 assert((*previous)->parent() == NULL, "invariant");
116 assert(*current != NULL, "invariant");
117 assert((*current)->distance_to_root() == distance_to_root, "invariant");
118
119 if (distance_to_root < EdgeUtils::root_context) {
120 // nothing to skip
121 return false;
122 }
123
124 size_t skip_length = 0;
125 const Edge* const skip_ancestor = get_skip_ancestor(current, distance_to_root, &skip_length);
126 assert(skip_ancestor != NULL, "invariant");
127 (*previous)->set_skip_length(skip_length);
128
129 // lookup target
130 StoredEdge* stored_target = get(skip_ancestor->reference());
131 if (stored_target != NULL) {
132 (*previous)->set_parent(stored_target);
133 // linked to existing, complete
134 return true;
135 }
136
137 assert(stored_target == NULL, "invariant");
138 stored_target = put(skip_ancestor->reference());
139 assert(stored_target != NULL, "invariant");
140 (*previous)->set_parent(stored_target);
141 *previous = stored_target;
142 *current = skip_ancestor->parent();
143 return false;
144 }
145
146 static void link_edge(const StoredEdge* current_stored, StoredEdge** previous) {
147 assert(current_stored != NULL, "invariant");
148 assert(*previous != NULL, "invariant");
149 assert((*previous)->parent() == NULL, "invariant");
150 (*previous)->set_parent(current_stored);
151 }
152
153 static const StoredEdge* find_closest_skip_edge(const StoredEdge* edge, size_t* distance) {
154 assert(edge != NULL, "invariant");
155 assert(distance != NULL, "invariant");
156 const StoredEdge* current = edge;
157 *distance = 1;
158 while (current != NULL && !current->is_skip_edge()) {
159 ++(*distance);
160 current = current->parent();
161 }
162 return current;
163 }
164
165 void EdgeStore::link_with_existing_chain(const StoredEdge* current_stored, StoredEdge** previous, size_t previous_length) {
166 assert(current_stored != NULL, "invariant");
167 assert((*previous)->parent() == NULL, "invariant");
168 size_t distance_to_skip_edge; // including the skip edge itself
169 const StoredEdge* const closest_skip_edge = find_closest_skip_edge(current_stored, &distance_to_skip_edge);
170 if (closest_skip_edge == NULL) {
171 // no found skip edge implies root
172 if (distance_to_skip_edge + previous_length <= EdgeUtils::max_ref_chain_depth) {
173 link_edge(current_stored, previous);
174 return;
175 }
176 assert(current_stored->distance_to_root() == distance_to_skip_edge - 2, "invariant");
177 put_skip_edge(previous, reinterpret_cast<const Edge**>(¤t_stored), distance_to_skip_edge - 2);
178 return;
179 }
180 assert(closest_skip_edge->is_skip_edge(), "invariant");
181 if (distance_to_skip_edge + previous_length <= EdgeUtils::leak_context) {
182 link_edge(current_stored, previous);
183 return;
184 }
185 // create a new skip edge with derived information from closest skip edge
186 (*previous)->set_skip_length(distance_to_skip_edge + closest_skip_edge->skip_length());
187 (*previous)->set_parent(closest_skip_edge->parent());
188 }
189
190 StoredEdge* EdgeStore::link_new_edge(StoredEdge** previous, const Edge** current) {
191 assert(*previous != NULL, "invariant");
192 assert((*previous)->parent() == NULL, "invariant");
193 assert(*current != NULL, "invariant");
194 assert(!contains((*current)->reference()), "invariant");
195 StoredEdge* const stored_edge = put((*current)->reference());
196 assert(stored_edge != NULL, "invariant");
197 link_edge(stored_edge, previous);
198 return stored_edge;
199 }
200
201 bool EdgeStore::put_edges(StoredEdge** previous, const Edge** current, size_t limit) {
202 assert(*previous != NULL, "invariant");
203 assert(*current != NULL, "invariant");
204 size_t depth = 1;
205 while (*current != NULL && depth < limit) {
206 StoredEdge* stored_edge = get((*current)->reference());
207 if (stored_edge != NULL) {
208 link_with_existing_chain(stored_edge, previous, depth);
209 return true;
210 }
211 stored_edge = link_new_edge(previous, current);
212 assert((*previous)->parent() != NULL, "invariant");
213 *previous = stored_edge;
214 *current = (*current)->parent();
215 ++depth;
216 }
217 return NULL == *current;
218 }
219
220 static GrowableArray<const StoredEdge*>* _leak_context_edges = nullptr;
221
222 EdgeStore::EdgeStore() : _edges(new EdgeHashTable(this)) {}
223
224 EdgeStore::~EdgeStore() {
225 assert(_edges != NULL, "invariant");
226 delete _edges;
227 delete _leak_context_edges;
228 _leak_context_edges = nullptr;
229 }
230
231 static int leak_context_edge_idx(const ObjectSample* sample) {
232 assert(sample != nullptr, "invariant");
233 return static_cast<int>(sample->object()->mark().value()) >> markWord::lock_bits;
234 }
235
236 bool EdgeStore::has_leak_context(const ObjectSample* sample) const {
237 const int idx = leak_context_edge_idx(sample);
238 if (idx == 0) {
239 return false;
240 }
241 assert(idx > 0, "invariant");
242 assert(_leak_context_edges != nullptr, "invariant");
243 assert(idx < _leak_context_edges->length(), "invariant");
244 assert(_leak_context_edges->at(idx) != nullptr, "invariant");
245 return true;
246 }
247
248 const StoredEdge* EdgeStore::get(const ObjectSample* sample) const {
249 assert(sample != nullptr, "invariant");
250 if (_leak_context_edges != nullptr) {
251 assert(SafepointSynchronize::is_at_safepoint(), "invariant");
252 const int idx = leak_context_edge_idx(sample);
253 if (idx > 0) {
254 assert(idx < _leak_context_edges->length(), "invariant");
255 const StoredEdge* const edge =_leak_context_edges->at(idx);
256 assert(edge != nullptr, "invariant");
257 return edge;
258 }
259 }
260 return get(UnifiedOopRef::encode_in_native(sample->object_addr()));
261 }
262
263 #ifdef ASSERT
264 // max_idx to ensure idx fit in lower 32-bits of markword together with lock bits.
265 static constexpr const int max_idx = right_n_bits(32 - markWord::lock_bits);
266
267 static void store_idx_precondition(oop sample_object, int idx) {
268 assert(sample_object != NULL, "invariant");
269 assert(sample_object->mark().is_marked(), "invariant");
270 assert(idx > 0, "invariant");
271 assert(idx <= max_idx, "invariant");
272 }
273 #endif
274
275 static void store_idx_in_markword(oop sample_object, int idx) {
276 DEBUG_ONLY(store_idx_precondition(sample_object, idx);)
277 const markWord idx_mark_word(sample_object->mark().value() | idx << markWord::lock_bits);
278 sample_object->set_mark(idx_mark_word);
279 assert(sample_object->mark().is_marked(), "must still be marked");
280 }
281
282 static const int initial_size = 64;
283
284 static int save(const StoredEdge* edge) {
285 assert(edge != nullptr, "invariant");
286 if (_leak_context_edges == nullptr) {
287 _leak_context_edges = new (ResourceObj::C_HEAP, mtTracing)GrowableArray<const StoredEdge*>(initial_size, mtTracing);
288 _leak_context_edges->append(nullptr); // next idx now at 1, for disambiguation in markword.
289 }
290 return _leak_context_edges->append(edge);
291 }
292
293 // We associate the leak context edge with the leak candidate object by saving the
294 // edge in an array and storing the array idx (shifted) into the markword of the candidate object.
295 static void associate_with_candidate(const StoredEdge* leak_context_edge) {
296 assert(leak_context_edge != nullptr, "invariant");
297 store_idx_in_markword(leak_context_edge->pointee(), save(leak_context_edge));
298 }
299
300 StoredEdge* EdgeStore::associate_leak_context_with_candidate(const Edge* edge) {
301 assert(edge != NULL, "invariant");
302 assert(!contains(edge->reference()), "invariant");
303 StoredEdge* const leak_context_edge = put(edge->reference());
304 associate_with_candidate(leak_context_edge);
305 return leak_context_edge;
306 }
307
308 /*
309 * The purpose of put_chain() is to reify the edge sequence
310 * discovered during heap traversal with a normalized logical copy.
311 * This copy consist of two sub-sequences and a connecting link (skip edge).
312 *
313 * "current" can be thought of as the cursor (search) edge, it is not in the edge store.
314 * "previous" is always an edge in the edge store.
315 * The leak context edge is the edge adjacent to the leak candidate object, always an edge in the edge store.
316 */
317 void EdgeStore::put_chain(const Edge* chain, size_t length) {
318 assert(chain != NULL, "invariant");
319 assert(chain->distance_to_root() + 1 == length, "invariant");
320 StoredEdge* const leak_context_edge = associate_leak_context_with_candidate(chain);
321 assert(leak_context_edge != NULL, "invariant");
322 assert(leak_context_edge->parent() == NULL, "invariant");
323
324 if (1 == length) {
325 store_gc_root_id_in_leak_context_edge(leak_context_edge, leak_context_edge);
326 return;
327 }
328
329 const Edge* current = chain->parent();
330 assert(current != NULL, "invariant");
331 StoredEdge* previous = leak_context_edge;
332
333 // a leak context is the sequence of (limited) edges reachable from the leak candidate
334 if (put_edges(&previous, ¤t, EdgeUtils::leak_context)) {
335 // complete
336 assert(previous != NULL, "invariant");
337 put_chain_epilogue(leak_context_edge, EdgeUtils::root(*previous));
338 return;
339 }
340
341 const size_t distance_to_root = length > EdgeUtils::leak_context ? length - 1 - EdgeUtils::leak_context : length - 1;
342 assert(current->distance_to_root() == distance_to_root, "invariant");
343
344 // a skip edge is the logical link
345 // connecting the leak context sequence with the root context sequence
346 if (put_skip_edge(&previous, ¤t, distance_to_root)) {
347 // complete
348 assert(previous != NULL, "invariant");
349 assert(previous->is_skip_edge(), "invariant");
350 assert(previous->parent() != NULL, "invariant");
351 put_chain_epilogue(leak_context_edge, EdgeUtils::root(*previous->parent()));
352 return;
353 }
354
355 assert(current->distance_to_root() < EdgeUtils::root_context, "invariant");
356
357 // a root context is the sequence of (limited) edges reachable from the root
358 put_edges(&previous, ¤t, EdgeUtils::root_context);
359 assert(previous != NULL, "invariant");
360 put_chain_epilogue(leak_context_edge, EdgeUtils::root(*previous));
361 }
362
363 void EdgeStore::put_chain_epilogue(StoredEdge* leak_context_edge, const Edge* root) const {
364 assert(leak_context_edge != NULL, "invariant");
365 assert(root != NULL, "invariant");
366 store_gc_root_id_in_leak_context_edge(leak_context_edge, root);
367 assert(leak_context_edge->distance_to_root() + 1 <= EdgeUtils::max_ref_chain_depth, "invariant");
368 }
369
370 // To avoid another traversal to resolve the root edge id later,
371 // cache it in the immediate leak context edge for fast retrieval.
372 void EdgeStore::store_gc_root_id_in_leak_context_edge(StoredEdge* leak_context_edge, const Edge* root) const {
373 assert(leak_context_edge != NULL, "invariant");
374 assert(leak_context_edge->gc_root_id() == 0, "invariant");
375 assert(root != NULL, "invariant");
376 assert(root->parent() == NULL, "invariant");
377 assert(root->distance_to_root() == 0, "invariant");
378 const StoredEdge* const stored_root = static_cast<const StoredEdge*>(root);
379 traceid root_id = stored_root->gc_root_id();
380 if (root_id == 0) {
381 root_id = get_id(root);
382 stored_root->set_gc_root_id(root_id);
383 }
384 assert(root_id != 0, "invariant");
385 leak_context_edge->set_gc_root_id(root_id);
386 assert(leak_context_edge->gc_root_id() == stored_root->gc_root_id(), "invariant");
387 }