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 idx: %d >= length: %d", idx, _leak_context_edges->length());
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 const int upper_bits = sample_object->mark().value() >> markWord::lock_bits;
272 assert((upper_bits | idx) == idx, "idx codec error : (%d | %d) != %d", upper_bits, idx, idx);
273 }
274 #endif
275
276 static void store_idx_in_markword(oop sample_object, int idx) {
277 DEBUG_ONLY(store_idx_precondition(sample_object, idx);)
278 const markWord idx_mark_word(sample_object->mark().value() | idx << markWord::lock_bits);
279 sample_object->set_mark(idx_mark_word);
280 assert(sample_object->mark().is_marked(), "must still be marked");
281 }
282
283 static const int initial_size = 64;
284
285 static int save(const StoredEdge* edge) {
286 assert(edge != nullptr, "invariant");
287 if (_leak_context_edges == nullptr) {
288 _leak_context_edges = new (mtTracing) GrowableArray<const StoredEdge*>(initial_size, mtTracing);
289 _leak_context_edges->append(nullptr); // next idx now at 1, for disambiguation in markword.
290 }
291 return _leak_context_edges->append(edge);
292 }
293
294 // We associate the leak context edge with the leak candidate object by saving the
295 // edge in an array and storing the array idx (shifted) into the markword of the candidate object.
296 static void associate_with_candidate(const StoredEdge* leak_context_edge) {
297 assert(leak_context_edge != nullptr, "invariant");
298 store_idx_in_markword(leak_context_edge->pointee(), save(leak_context_edge));
299 }
300
301 StoredEdge* EdgeStore::associate_leak_context_with_candidate(const Edge* edge) {
302 assert(edge != nullptr, "invariant");
303 assert(!contains(edge->reference()), "invariant");
304 StoredEdge* const leak_context_edge = put(edge->reference());
305 associate_with_candidate(leak_context_edge);
306 return leak_context_edge;
307 }
308
309 /*
310 * The purpose of put_chain() is to reify the edge sequence
311 * discovered during heap traversal with a normalized logical copy.
312 * This copy consist of two sub-sequences and a connecting link (skip edge).
313 *
314 * "current" can be thought of as the cursor (search) edge, it is not in the edge store.
315 * "previous" is always an edge in the edge store.
316 * The leak context edge is the edge adjacent to the leak candidate object, always an edge in the edge store.
317 */
318 void EdgeStore::put_chain(const Edge* chain, size_t length) {
319 assert(chain != nullptr, "invariant");
320 assert(chain->distance_to_root() + 1 == length, "invariant");
321 StoredEdge* const leak_context_edge = associate_leak_context_with_candidate(chain);
322 assert(leak_context_edge != nullptr, "invariant");
323 assert(leak_context_edge->parent() == nullptr, "invariant");
324
325 if (1 == length) {
326 store_gc_root_id_in_leak_context_edge(leak_context_edge, leak_context_edge);
327 return;
328 }
329
330 const Edge* current = chain->parent();
331 assert(current != nullptr, "invariant");
332 StoredEdge* previous = leak_context_edge;
333
334 // a leak context is the sequence of (limited) edges reachable from the leak candidate
335 if (put_edges(&previous, ¤t, EdgeUtils::leak_context)) {
336 // complete
337 assert(previous != nullptr, "invariant");
338 put_chain_epilogue(leak_context_edge, EdgeUtils::root(*previous));
339 return;
340 }
341
342 const size_t distance_to_root = length > EdgeUtils::leak_context ? length - 1 - EdgeUtils::leak_context : length - 1;
343 assert(current->distance_to_root() == distance_to_root, "invariant");
344
345 // a skip edge is the logical link
346 // connecting the leak context sequence with the root context sequence
347 if (put_skip_edge(&previous, ¤t, distance_to_root)) {
348 // complete
349 assert(previous != nullptr, "invariant");
350 assert(previous->is_skip_edge(), "invariant");
351 assert(previous->parent() != nullptr, "invariant");
352 put_chain_epilogue(leak_context_edge, EdgeUtils::root(*previous->parent()));
353 return;
354 }
355
356 assert(current->distance_to_root() < EdgeUtils::root_context, "invariant");
357
358 // a root context is the sequence of (limited) edges reachable from the root
359 put_edges(&previous, ¤t, EdgeUtils::root_context);
360 assert(previous != nullptr, "invariant");
361 put_chain_epilogue(leak_context_edge, EdgeUtils::root(*previous));
362 }
363
364 void EdgeStore::put_chain_epilogue(StoredEdge* leak_context_edge, const Edge* root) const {
365 assert(leak_context_edge != nullptr, "invariant");
366 assert(root != nullptr, "invariant");
367 store_gc_root_id_in_leak_context_edge(leak_context_edge, root);
368 assert(leak_context_edge->distance_to_root() + 1 <= EdgeUtils::max_ref_chain_depth, "invariant");
369 }
370
371 // To avoid another traversal to resolve the root edge id later,
372 // cache it in the immediate leak context edge for fast retrieval.
373 void EdgeStore::store_gc_root_id_in_leak_context_edge(StoredEdge* leak_context_edge, const Edge* root) const {
374 assert(leak_context_edge != nullptr, "invariant");
375 assert(leak_context_edge->gc_root_id() == 0, "invariant");
376 assert(root != nullptr, "invariant");
377 assert(root->parent() == nullptr, "invariant");
378 assert(root->distance_to_root() == 0, "invariant");
379 const StoredEdge* const stored_root = static_cast<const StoredEdge*>(root);
380 traceid root_id = stored_root->gc_root_id();
381 if (root_id == 0) {
382 root_id = get_id(root);
383 stored_root->set_gc_root_id(root_id);
384 }
385 assert(root_id != 0, "invariant");
386 leak_context_edge->set_gc_root_id(root_id);
387 assert(leak_context_edge->gc_root_id() == stored_root->gc_root_id(), "invariant");
388 }