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/bitset.hpp"
27 #include "jfr/leakprofiler/chains/dfsClosure.hpp"
28 #include "jfr/leakprofiler/chains/edge.hpp"
29 #include "jfr/leakprofiler/chains/edgeStore.hpp"
30 #include "jfr/leakprofiler/chains/rootSetClosure.hpp"
31 #include "jfr/leakprofiler/utilities/granularTimer.hpp"
32 #include "jfr/leakprofiler/utilities/rootType.hpp"
33 #include "jfr/leakprofiler/utilities/unifiedOop.hpp"
34 #include "memory/iterator.inline.hpp"
35 #include "memory/resourceArea.hpp"
36 #include "oops/access.inline.hpp"
37 #include "oops/oop.inline.hpp"
38 #include "utilities/align.hpp"
39
40 // max dfs depth should not exceed size of stack
41 static const size_t max_dfs_depth = 5000;
42
43 EdgeStore* DFSClosure::_edge_store = NULL;
44 BitSet* DFSClosure::_mark_bits = NULL;
45 const Edge* DFSClosure::_start_edge = NULL;
46 size_t DFSClosure::_max_depth = max_dfs_depth;
47 bool DFSClosure::_ignore_root_set = false;
48
DFSClosure()49 DFSClosure::DFSClosure() :
50 _parent(NULL),
51 _reference(NULL),
52 _depth(0) {
53 }
54
DFSClosure(DFSClosure * parent,size_t depth)55 DFSClosure::DFSClosure(DFSClosure* parent, size_t depth) :
56 _parent(parent),
57 _reference(NULL),
58 _depth(depth) {
59 }
60
find_leaks_from_edge(EdgeStore * edge_store,BitSet * mark_bits,const Edge * start_edge)61 void DFSClosure::find_leaks_from_edge(EdgeStore* edge_store,
62 BitSet* mark_bits,
63 const Edge* start_edge) {
64 assert(edge_store != NULL, "invariant");
65 assert(mark_bits != NULL," invariant");
66 assert(start_edge != NULL, "invariant");
67
68 _edge_store = edge_store;
69 _mark_bits = mark_bits;
70 _start_edge = start_edge;
71 _ignore_root_set = false;
72 assert(_max_depth == max_dfs_depth, "invariant");
73
74 // Depth-first search, starting from a BFS egde
75 DFSClosure dfs;
76 start_edge->pointee()->oop_iterate(&dfs);
77 }
78
find_leaks_from_root_set(EdgeStore * edge_store,BitSet * mark_bits)79 void DFSClosure::find_leaks_from_root_set(EdgeStore* edge_store,
80 BitSet* mark_bits) {
81 assert(edge_store != NULL, "invariant");
82 assert(mark_bits != NULL, "invariant");
83
84 _edge_store = edge_store;
85 _mark_bits = mark_bits;
86 _start_edge = NULL;
87
88 // Mark root set, to avoid going sideways
89 _max_depth = 1;
90 _ignore_root_set = false;
91 DFSClosure dfs;
92 RootSetClosure<DFSClosure> rs(&dfs);
93 rs.process();
94
95 // Depth-first search
96 _max_depth = max_dfs_depth;
97 _ignore_root_set = true;
98 assert(_start_edge == NULL, "invariant");
99 rs.process();
100 }
101
closure_impl(const oop * reference,const oop pointee)102 void DFSClosure::closure_impl(const oop* reference, const oop pointee) {
103 assert(pointee != NULL, "invariant");
104 assert(reference != NULL, "invariant");
105
106 if (GranularTimer::is_finished()) {
107 return;
108 }
109 if (_depth == 0 && _ignore_root_set) {
110 // Root set is already marked, but we want
111 // to continue, so skip is_marked check.
112 assert(_mark_bits->is_marked(pointee), "invariant");
113 } else {
114 if (_mark_bits->is_marked(pointee)) {
115 return;
116 }
117 }
118
119 _reference = reference;
120 _mark_bits->mark_obj(pointee);
121 assert(_mark_bits->is_marked(pointee), "invariant");
122
123 // is the pointee a sample object?
124 if (NULL == pointee->mark()) {
125 add_chain();
126 }
127
128 assert(_max_depth >= 1, "invariant");
129 if (_depth < _max_depth - 1) {
130 DFSClosure next_level(this, _depth + 1);
131 pointee->oop_iterate(&next_level);
132 }
133 }
134
add_chain()135 void DFSClosure::add_chain() {
136 const size_t array_length = _depth + 2;
137
138 ResourceMark rm;
139 Edge* const chain = NEW_RESOURCE_ARRAY(Edge, array_length);
140 size_t idx = 0;
141
142 // aggregate from depth-first search
143 const DFSClosure* c = this;
144 while (c != NULL) {
145 const size_t next = idx + 1;
146 chain[idx++] = Edge(&chain[next], c->reference());
147 c = c->parent();
148 }
149 assert(_depth + 1 == idx, "invariant");
150 assert(array_length == idx + 1, "invariant");
151
152 // aggregate from breadth-first search
153 if (_start_edge != NULL) {
154 chain[idx++] = *_start_edge;
155 } else {
156 chain[idx - 1] = Edge(NULL, chain[idx - 1].reference());
157 }
158 _edge_store->put_chain(chain, idx + (_start_edge != NULL ? _start_edge->distance_to_root() : 0));
159 }
160
do_oop(oop * ref)161 void DFSClosure::do_oop(oop* ref) {
162 assert(ref != NULL, "invariant");
163 assert(is_aligned(ref, HeapWordSize), "invariant");
164 const oop pointee = *ref;
165 if (pointee != NULL) {
166 closure_impl(ref, pointee);
167 }
168 }
169
do_oop(narrowOop * ref)170 void DFSClosure::do_oop(narrowOop* ref) {
171 assert(ref != NULL, "invariant");
172 assert(is_aligned(ref, sizeof(narrowOop)), "invariant");
173 const oop pointee = RawAccess<>::oop_load(ref);
174 if (pointee != NULL) {
175 closure_impl(UnifiedOop::encode(ref), pointee);
176 }
177 }
178
do_root(const oop * ref)179 void DFSClosure::do_root(const oop* ref) {
180 assert(ref != NULL, "invariant");
181 const oop pointee = UnifiedOop::dereference(ref);
182 assert(pointee != NULL, "invariant");
183 closure_impl(ref, pointee);
184 }
185