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 "classfile/javaClasses.hpp"
27 #include "jfr/leakprofiler/chains/edge.hpp"
28 #include "jfr/leakprofiler/chains/edgeStore.hpp"
29 #include "jfr/leakprofiler/chains/edgeUtils.hpp"
30 #include "jfr/leakprofiler/utilities/unifiedOop.hpp"
31 #include "oops/fieldStreams.hpp"
32 #include "oops/instanceKlass.hpp"
33 #include "oops/oopsHierarchy.hpp"
34 #include "runtime/handles.inline.hpp"
35
36 bool EdgeUtils::is_leak_edge(const Edge& edge) {
37 return (const Edge*)edge.pointee()->mark() == &edge;
38 }
39
40 bool EdgeUtils::is_root(const Edge& edge) {
41 return edge.is_root();
42 }
43
44 static int field_offset(const Edge& edge) {
45 assert(!edge.is_root(), "invariant");
46 const oop ref_owner = edge.reference_owner();
47 assert(ref_owner != NULL, "invariant");
48 const oop* reference = UnifiedOop::decode(edge.reference());
49 assert(reference != NULL, "invariant");
50 assert(!UnifiedOop::is_narrow(reference), "invariant");
51 assert(!ref_owner->is_array(), "invariant");
52 assert(ref_owner->is_instance(), "invariant");
53 const int offset = (int)pointer_delta(reference, ref_owner, sizeof(char));
54 assert(offset < (ref_owner->size() * HeapWordSize), "invariant");
55 return offset;
56 }
57
58 static const InstanceKlass* field_type(const Edge& edge) {
59 assert(!edge.is_root() || !EdgeUtils::is_array_element(edge), "invariant");
60 return (const InstanceKlass*)edge.reference_owner_klass();
61 }
62
63 const Symbol* EdgeUtils::field_name_symbol(const Edge& edge) {
64 assert(!edge.is_root(), "invariant");
65 assert(!is_array_element(edge), "invariant");
66 const int offset = field_offset(edge);
67 const InstanceKlass* ik = field_type(edge);
68 while (ik != NULL) {
69 JavaFieldStream jfs(ik);
70 while (!jfs.done()) {
71 if (offset == jfs.offset()) {
72 return jfs.name();
73 }
74 jfs.next();
75 }
76 ik = (InstanceKlass*)ik->super();
77 }
78 return NULL;
79 }
80
81 jshort EdgeUtils::field_modifiers(const Edge& edge) {
82 const int offset = field_offset(edge);
83 const InstanceKlass* ik = field_type(edge);
84
85 while (ik != NULL) {
86 JavaFieldStream jfs(ik);
87 while (!jfs.done()) {
88 if (offset == jfs.offset()) {
89 return jfs.access_flags().as_short();
90 }
91 jfs.next();
92 }
93 ik = (InstanceKlass*)ik->super();
94 }
95 return 0;
96 }
97
98 bool EdgeUtils::is_array_element(const Edge& edge) {
99 assert(!edge.is_root(), "invariant");
100 const oop ref_owner = edge.reference_owner();
101 assert(ref_owner != NULL, "invariant");
102 return ref_owner->is_objArray();
103 }
104
105 static int array_offset(const Edge& edge) {
106 assert(!edge.is_root(), "invariant");
107 const oop ref_owner = edge.reference_owner();
108 assert(ref_owner != NULL, "invariant");
109 const oop* reference = UnifiedOop::decode(edge.reference());
110 assert(reference != NULL, "invariant");
111 assert(!UnifiedOop::is_narrow(reference), "invariant");
112 assert(ref_owner->is_array(), "invariant");
113 const objArrayOop ref_owner_array = static_cast<const objArrayOop>(ref_owner);
114 const int offset = (int)pointer_delta(reference, ref_owner_array->base(), heapOopSize);
115 assert(offset >= 0 && offset < ref_owner_array->length(), "invariant");
116 return offset;
117 }
118
119 int EdgeUtils::array_index(const Edge& edge) {
120 return is_array_element(edge) ? array_offset(edge) : 0;
121 }
122
123 int EdgeUtils::array_size(const Edge& edge) {
124 if (is_array_element(edge)) {
125 const oop ref_owner = edge.reference_owner();
126 assert(ref_owner != NULL, "invariant");
127 assert(ref_owner->is_objArray(), "invariant");
128 return ((objArrayOop)(ref_owner))->length();
129 }
130 return 0;
131 }
132
133 const Edge* EdgeUtils::root(const Edge& edge) {
134 const Edge* current = &edge;
135 const Edge* parent = current->parent();
136 while (parent != NULL) {
137 current = parent;
138 parent = current->parent();
139 }
140 return current;
141 }
142
143 // The number of references associated with the leak node;
144 // can be viewed as the leak node "context".
145 // Used to provide leak context for a "capped/skipped" reference chain.
146 static const size_t leak_context = 100;
147
148 // The number of references associated with the root node;
149 // can be viewed as the root node "context".
150 // Used to provide root context for a "capped/skipped" reference chain.
151 static const size_t root_context = 100;
152
153 // A limit on the reference chain depth to be serialized,
154 static const size_t max_ref_chain_depth = leak_context + root_context;
155
156 const RoutableEdge* skip_to(const RoutableEdge& edge, size_t skip_length) {
157 const RoutableEdge* current = &edge;
158 const RoutableEdge* parent = current->physical_parent();
159 size_t seek = 0;
160 while (parent != NULL && seek != skip_length) {
161 seek++;
162 current = parent;
163 parent = parent->physical_parent();
164 }
165 return current;
166 }
167
168 #ifdef ASSERT
169 static void validate_skip_target(const RoutableEdge* skip_target) {
170 assert(skip_target != NULL, "invariant");
171 assert(skip_target->distance_to_root() + 1 == root_context, "invariant");
172 assert(skip_target->is_sentinel(), "invariant");
173 }
174
175 static void validate_new_skip_edge(const RoutableEdge* new_skip_edge, const RoutableEdge* last_skip_edge, size_t adjustment) {
176 assert(new_skip_edge != NULL, "invariant");
177 assert(new_skip_edge->is_skip_edge(), "invariant");
178 if (last_skip_edge != NULL) {
179 const RoutableEdge* const target = skip_to(*new_skip_edge->logical_parent(), adjustment);
180 validate_skip_target(target->logical_parent());
181 return;
182 }
183 assert(last_skip_edge == NULL, "invariant");
184 // only one level of logical indirection
185 validate_skip_target(new_skip_edge->logical_parent());
186 }
187 #endif // ASSERT
188
189 static void install_logical_route(const RoutableEdge* new_skip_edge, size_t skip_target_distance) {
190 assert(new_skip_edge != NULL, "invariant");
191 assert(!new_skip_edge->is_skip_edge(), "invariant");
192 assert(!new_skip_edge->processed(), "invariant");
193 const RoutableEdge* const skip_target = skip_to(*new_skip_edge, skip_target_distance);
194 assert(skip_target != NULL, "invariant");
195 new_skip_edge->set_skip_edge(skip_target);
196 new_skip_edge->set_skip_length(skip_target_distance);
197 assert(new_skip_edge->is_skip_edge(), "invariant");
198 assert(new_skip_edge->logical_parent() == skip_target, "invariant");
199 }
200
201 static const RoutableEdge* find_last_skip_edge(const RoutableEdge& edge, size_t& distance) {
202 assert(distance == 0, "invariant");
203 const RoutableEdge* current = &edge;
204 while (current != NULL) {
205 if (current->is_skip_edge() && current->skip_edge()->is_sentinel()) {
206 return current;
207 }
208 current = current->physical_parent();
209 ++distance;
210 }
211 return current;
212 }
213
214 static void collapse_overlapping_chain(const RoutableEdge& edge,
215 const RoutableEdge* first_processed_edge,
216 size_t first_processed_distance) {
217 assert(first_processed_edge != NULL, "invariant");
218 // first_processed_edge is already processed / written
219 assert(first_processed_edge->processed(), "invariant");
220 assert(first_processed_distance + 1 <= leak_context, "invariant");
221
222 // from this first processed edge, attempt to fetch the last skip edge
223 size_t last_skip_edge_distance = 0;
224 const RoutableEdge* const last_skip_edge = find_last_skip_edge(*first_processed_edge, last_skip_edge_distance);
225 const size_t distance_discovered = first_processed_distance + last_skip_edge_distance + 1;
226
227 if (distance_discovered <= leak_context || (last_skip_edge == NULL && distance_discovered <= max_ref_chain_depth)) {
228 // complete chain can be accommodated without modification
229 return;
230 }
231
232 // backtrack one edge from existing processed edge
233 const RoutableEdge* const new_skip_edge = skip_to(edge, first_processed_distance - 1);
234 assert(new_skip_edge != NULL, "invariant");
235 assert(!new_skip_edge->processed(), "invariant");
236 assert(new_skip_edge->parent() == first_processed_edge, "invariant");
237
238 size_t adjustment = 0;
239 if (last_skip_edge != NULL) {
240 assert(leak_context - 1 > first_processed_distance - 1, "invariant");
241 adjustment = leak_context - first_processed_distance - 1;
242 assert(last_skip_edge_distance + 1 > adjustment, "invariant");
243 install_logical_route(new_skip_edge, last_skip_edge_distance + 1 - adjustment);
244 } else {
245 install_logical_route(new_skip_edge, last_skip_edge_distance + 1 - root_context);
246 new_skip_edge->logical_parent()->set_skip_length(1); // sentinel
247 }
248
249 DEBUG_ONLY(validate_new_skip_edge(new_skip_edge, last_skip_edge, adjustment);)
250 }
251
252 static void collapse_non_overlapping_chain(const RoutableEdge& edge,
253 const RoutableEdge* first_processed_edge,
254 size_t first_processed_distance) {
255 assert(first_processed_edge != NULL, "invariant");
256 assert(!first_processed_edge->processed(), "invariant");
257 // this implies that the first "processed" edge is the leak context relative "leaf"
258 assert(first_processed_distance + 1 == leak_context, "invariant");
259
260 const size_t distance_to_root = edge.distance_to_root();
261 if (distance_to_root + 1 <= max_ref_chain_depth) {
262 // complete chain can be accommodated without constructing a skip edge
263 return;
264 }
265
266 install_logical_route(first_processed_edge, distance_to_root + 1 - first_processed_distance - root_context);
267 first_processed_edge->logical_parent()->set_skip_length(1); // sentinel
268
269 DEBUG_ONLY(validate_new_skip_edge(first_processed_edge, NULL, 0);)
270 }
271
272 static const RoutableEdge* processed_edge(const RoutableEdge& edge, size_t& distance) {
273 assert(distance == 0, "invariant");
274 const RoutableEdge* current = &edge;
275 while (current != NULL && distance < leak_context - 1) {
276 if (current->processed()) {
277 return current;
278 }
279 current = current->physical_parent();
280 ++distance;
281 }
282 assert(distance <= leak_context - 1, "invariant");
283 return current;
284 }
285
286 /*
287 * Some vocabulary:
288 * -----------
289 * "Context" is an interval in the chain, it is associcated with an edge and it signifies a number of connected edges.
290 * "Processed / written" means an edge that has already been serialized.
291 * "Skip edge" is an edge that contains additional information for logical routing purposes.
292 * "Skip target" is an edge used as a destination for a skip edge
293 */
294 void EdgeUtils::collapse_chain(const RoutableEdge& edge) {
295 assert(is_leak_edge(edge), "invariant");
296
297 // attempt to locate an already processed edge inside current leak context (if any)
298 size_t first_processed_distance = 0;
299 const RoutableEdge* const first_processed_edge = processed_edge(edge, first_processed_distance);
300 if (first_processed_edge == NULL) {
301 return;
302 }
303
304 if (first_processed_edge->processed()) {
305 collapse_overlapping_chain(edge, first_processed_edge, first_processed_distance);
306 } else {
307 collapse_non_overlapping_chain(edge, first_processed_edge, first_processed_distance);
308 }
309
310 assert(edge.logical_distance_to_root() + 1 <= max_ref_chain_depth, "invariant");
311 }