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
41static const size_t max_dfs_depth = 5000;
42
43EdgeStore* DFSClosure::_edge_store = NULL;
44BitSet* DFSClosure::_mark_bits = NULL;
45const Edge* DFSClosure::_start_edge = NULL;
46size_t DFSClosure::_max_depth = max_dfs_depth;
47bool DFSClosure::_ignore_root_set = false;
48
49DFSClosure::DFSClosure() :
50 _parent(NULL),
51 _reference(NULL),
52 _depth(0) {
53}
54
55DFSClosure::DFSClosure(DFSClosure* parent, size_t depth) :
56 _parent(parent),
57 _reference(NULL),
58 _depth(depth) {
59}
60
61void 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
79void 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
102void 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
135void 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
161void 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
170void 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
179void DFSClosure::do_root(const oop* ref) {
180 assert(ref != NULL, "invariant");
181 assert(is_aligned(ref, HeapWordSize), "invariant");
182 const oop pointee = *ref;
183 assert(pointee != NULL, "invariant");
184 closure_impl(ref, pointee);
185}
186