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
25#include "precompiled.hpp"
26#include "jfr/leakprofiler/chains/edgeStore.hpp"
27#include "jfr/leakprofiler/chains/edgeUtils.hpp"
28#include "oops/oop.inline.hpp"
29
30StoredEdge::StoredEdge() : Edge() {}
31StoredEdge::StoredEdge(const Edge* parent, const oop* reference) : Edge(parent, reference), _gc_root_id(0), _skip_length(0) {}
32
33StoredEdge::StoredEdge(const Edge& edge) : Edge(edge), _gc_root_id(0), _skip_length(0) {}
34
35StoredEdge::StoredEdge(const StoredEdge& edge) : Edge(edge), _gc_root_id(edge._gc_root_id), _skip_length(edge._skip_length) {}
36
37void StoredEdge::operator=(const StoredEdge& edge) {
38 Edge::operator=(edge);
39 _gc_root_id = edge._gc_root_id;
40 _skip_length = edge._skip_length;
41}
42
43traceid EdgeStore::_edge_id_counter = 0;
44
45EdgeStore::EdgeStore() : _edges(NULL) {
46 _edges = new EdgeHashTable(this);
47}
48
49EdgeStore::~EdgeStore() {
50 assert(_edges != NULL, "invariant");
51 delete _edges;
52}
53
54bool EdgeStore::is_empty() const {
55 return !_edges->has_entries();
56}
57
58void EdgeStore::assign_id(EdgeEntry* entry) {
59 assert(entry != NULL, "invariant");
60 assert(entry->id() == 0, "invariant");
61 entry->set_id(++_edge_id_counter);
62}
63
64bool EdgeStore::equals(const Edge& query, uintptr_t hash, const EdgeEntry* entry) {
65 assert(entry != NULL, "invariant");
66 assert(entry->hash() == hash, "invariant");
67 return true;
68}
69
70#ifdef ASSERT
71bool EdgeStore::contains(const oop* reference) const {
72 return get(reference) != NULL;
73}
74#endif
75
76StoredEdge* EdgeStore::get(const oop* reference) const {
77 assert(reference != NULL, "invariant");
78 const StoredEdge e(NULL, reference);
79 EdgeEntry* const entry = _edges->lookup_only(e, (uintptr_t)reference);
80 return entry != NULL ? entry->literal_addr() : NULL;
81}
82
83StoredEdge* EdgeStore::put(const oop* reference) {
84 assert(reference != NULL, "invariant");
85 const StoredEdge e(NULL, reference);
86 assert(NULL == _edges->lookup_only(e, (uintptr_t)reference), "invariant");
87 EdgeEntry& entry = _edges->put(e, (uintptr_t)reference);
88 return entry.literal_addr();
89}
90
91traceid EdgeStore::get_id(const Edge* edge) const {
92 assert(edge != NULL, "invariant");
93 EdgeEntry* const entry = _edges->lookup_only(*edge, (uintptr_t)edge->reference());
94 assert(entry != NULL, "invariant");
95 return entry->id();
96}
97
98traceid EdgeStore::gc_root_id(const Edge* edge) const {
99 assert(edge != NULL, "invariant");
100 const traceid gc_root_id = static_cast<const StoredEdge*>(edge)->gc_root_id();
101 if (gc_root_id != 0) {
102 return gc_root_id;
103 }
104 // not cached
105 assert(edge != NULL, "invariant");
106 const Edge* const root = EdgeUtils::root(*edge);
107 assert(root != NULL, "invariant");
108 assert(root->parent() == NULL, "invariant");
109 return get_id(root);
110}
111
112static const Edge* get_skip_ancestor(const Edge** current, size_t distance_to_root, size_t* skip_length) {
113 assert(distance_to_root >= EdgeUtils::root_context, "invariant");
114 assert(*skip_length == 0, "invariant");
115 *skip_length = distance_to_root - (EdgeUtils::root_context - 1);
116 const Edge* const target = EdgeUtils::ancestor(**current, *skip_length);
117 assert(target != NULL, "invariant");
118 assert(target->distance_to_root() + 1 == EdgeUtils::root_context, "invariant");
119 return target;
120}
121
122bool EdgeStore::put_skip_edge(StoredEdge** previous, const Edge** current, size_t distance_to_root) {
123 assert(*previous != NULL, "invariant");
124 assert((*previous)->parent() == NULL, "invariant");
125 assert(*current != NULL, "invariant");
126 assert((*current)->distance_to_root() == distance_to_root, "invariant");
127
128 if (distance_to_root < EdgeUtils::root_context) {
129 // nothing to skip
130 return false;
131 }
132
133 size_t skip_length = 0;
134 const Edge* const skip_ancestor = get_skip_ancestor(current, distance_to_root, &skip_length);
135 assert(skip_ancestor != NULL, "invariant");
136 (*previous)->set_skip_length(skip_length);
137
138 // lookup target
139 StoredEdge* stored_target = get(skip_ancestor->reference());
140 if (stored_target != NULL) {
141 (*previous)->set_parent(stored_target);
142 // linked to existing, complete
143 return true;
144 }
145
146 assert(stored_target == NULL, "invariant");
147 stored_target = put(skip_ancestor->reference());
148 assert(stored_target != NULL, "invariant");
149 (*previous)->set_parent(stored_target);
150 *previous = stored_target;
151 *current = skip_ancestor->parent();
152 return false;
153}
154
155static void link_edge(const StoredEdge* current_stored, StoredEdge** previous) {
156 assert(current_stored != NULL, "invariant");
157 assert(*previous != NULL, "invariant");
158 assert((*previous)->parent() == NULL, "invariant");
159 (*previous)->set_parent(current_stored);
160}
161
162static const StoredEdge* find_closest_skip_edge(const StoredEdge* edge, size_t* distance) {
163 assert(edge != NULL, "invariant");
164 assert(distance != NULL, "invariant");
165 const StoredEdge* current = edge;
166 *distance = 1;
167 while (current != NULL && !current->is_skip_edge()) {
168 ++(*distance);
169 current = current->parent();
170 }
171 return current;
172}
173
174void EdgeStore::link_with_existing_chain(const StoredEdge* current_stored, StoredEdge** previous, size_t previous_length) {
175 assert(current_stored != NULL, "invariant");
176 assert((*previous)->parent() == NULL, "invariant");
177 size_t distance_to_skip_edge; // including the skip edge itself
178 const StoredEdge* const closest_skip_edge = find_closest_skip_edge(current_stored, &distance_to_skip_edge);
179 if (closest_skip_edge == NULL) {
180 // no found skip edge implies root
181 if (distance_to_skip_edge + previous_length <= EdgeUtils::max_ref_chain_depth) {
182 link_edge(current_stored, previous);
183 return;
184 }
185 assert(current_stored->distance_to_root() == distance_to_skip_edge - 2, "invariant");
186 put_skip_edge(previous, reinterpret_cast<const Edge**>(&current_stored), distance_to_skip_edge - 2);
187 return;
188 }
189 assert(closest_skip_edge->is_skip_edge(), "invariant");
190 if (distance_to_skip_edge + previous_length <= EdgeUtils::leak_context) {
191 link_edge(current_stored, previous);
192 return;
193 }
194 // create a new skip edge with derived information from closest skip edge
195 (*previous)->set_skip_length(distance_to_skip_edge + closest_skip_edge->skip_length());
196 (*previous)->set_parent(closest_skip_edge->parent());
197}
198
199StoredEdge* EdgeStore::link_new_edge(StoredEdge** previous, const Edge** current) {
200 assert(*previous != NULL, "invariant");
201 assert((*previous)->parent() == NULL, "invariant");
202 assert(*current != NULL, "invariant");
203 assert(!contains((*current)->reference()), "invariant");
204 StoredEdge* const stored_edge = put((*current)->reference());
205 assert(stored_edge != NULL, "invariant");
206 link_edge(stored_edge, previous);
207 return stored_edge;
208}
209
210bool EdgeStore::put_edges(StoredEdge** previous, const Edge** current, size_t limit) {
211 assert(*previous != NULL, "invariant");
212 assert(*current != NULL, "invariant");
213 size_t depth = 1;
214 while (*current != NULL && depth < limit) {
215 StoredEdge* stored_edge = get((*current)->reference());
216 if (stored_edge != NULL) {
217 link_with_existing_chain(stored_edge, previous, depth);
218 return true;
219 }
220 stored_edge = link_new_edge(previous, current);
221 assert((*previous)->parent() != NULL, "invariant");
222 *previous = stored_edge;
223 *current = (*current)->parent();
224 ++depth;
225 }
226 return NULL == *current;
227}
228
229// Install the immediate edge into the mark word of the leak candidate object
230StoredEdge* EdgeStore::associate_leak_context_with_candidate(const Edge* edge) {
231 assert(edge != NULL, "invariant");
232 assert(!contains(edge->reference()), "invariant");
233 StoredEdge* const leak_context_edge = put(edge->reference());
234 oop sample_object = edge->pointee();
235 assert(sample_object != NULL, "invariant");
236 assert(NULL == sample_object->mark(), "invariant");
237 sample_object->set_mark(markOop(leak_context_edge));
238 return leak_context_edge;
239}
240
241/*
242 * The purpose of put_chain() is to reify the edge sequence
243 * discovered during heap traversal with a normalized logical copy.
244 * This copy consist of two sub-sequences and a connecting link (skip edge).
245 *
246 * "current" can be thought of as the cursor (search) edge, it is not in the edge store.
247 * "previous" is always an edge in the edge store.
248 * The leak context edge is the edge adjacent to the leak candidate object, always an edge in the edge store.
249 */
250void EdgeStore::put_chain(const Edge* chain, size_t length) {
251 assert(chain != NULL, "invariant");
252 assert(chain->distance_to_root() + 1 == length, "invariant");
253 StoredEdge* const leak_context_edge = associate_leak_context_with_candidate(chain);
254 assert(leak_context_edge != NULL, "invariant");
255 assert(leak_context_edge->parent() == NULL, "invariant");
256
257 if (1 == length) {
258 return;
259 }
260
261 const Edge* current = chain->parent();
262 assert(current != NULL, "invariant");
263 StoredEdge* previous = leak_context_edge;
264
265 // a leak context is the sequence of (limited) edges reachable from the leak candidate
266 if (put_edges(&previous, &current, EdgeUtils::leak_context)) {
267 // complete
268 assert(previous != NULL, "invariant");
269 put_chain_epilogue(leak_context_edge, EdgeUtils::root(*previous));
270 return;
271 }
272
273 const size_t distance_to_root = length > EdgeUtils::leak_context ? length - 1 - EdgeUtils::leak_context : length - 1;
274 assert(current->distance_to_root() == distance_to_root, "invariant");
275
276 // a skip edge is the logical link
277 // connecting the leak context sequence with the root context sequence
278 if (put_skip_edge(&previous, &current, distance_to_root)) {
279 // complete
280 assert(previous != NULL, "invariant");
281 assert(previous->is_skip_edge(), "invariant");
282 assert(previous->parent() != NULL, "invariant");
283 put_chain_epilogue(leak_context_edge, EdgeUtils::root(*previous->parent()));
284 return;
285 }
286
287 assert(current->distance_to_root() < EdgeUtils::root_context, "invariant");
288
289 // a root context is the sequence of (limited) edges reachable from the root
290 put_edges(&previous, &current, EdgeUtils::root_context);
291 assert(previous != NULL, "invariant");
292 put_chain_epilogue(leak_context_edge, EdgeUtils::root(*previous));
293}
294
295void EdgeStore::put_chain_epilogue(StoredEdge* leak_context_edge, const Edge* root) const {
296 assert(leak_context_edge != NULL, "invariant");
297 assert(root != NULL, "invariant");
298 store_gc_root_id_in_leak_context_edge(leak_context_edge, root);
299 assert(leak_context_edge->distance_to_root() + 1 <= EdgeUtils::max_ref_chain_depth, "invariant");
300}
301
302// To avoid another traversal to resolve the root edge id later,
303// cache it in the immediate leak context edge for fast retrieval.
304void EdgeStore::store_gc_root_id_in_leak_context_edge(StoredEdge* leak_context_edge, const Edge* root) const {
305 assert(leak_context_edge != NULL, "invariant");
306 assert(leak_context_edge->gc_root_id() == 0, "invariant");
307 assert(root != NULL, "invariant");
308 assert(root->parent() == NULL, "invariant");
309 assert(root->distance_to_root() == 0, "invariant");
310 const StoredEdge* const stored_root = static_cast<const StoredEdge*>(root);
311 traceid root_id = stored_root->gc_root_id();
312 if (root_id == 0) {
313 root_id = get_id(root);
314 stored_root->set_gc_root_id(root_id);
315 }
316 assert(root_id != 0, "invariant");
317 leak_context_edge->set_gc_root_id(root_id);
318 assert(leak_context_edge->gc_root_id() == stored_root->gc_root_id(), "invariant");
319}
320