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