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