1 /*
2 * Copyright (c) 2020, 2023, Oracle and/or its affiliates. All rights reserved.
3 * Copyright (c) 2020, 2022 SAP SE. All rights reserved.
4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5 *
6 * This code is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License version 2 only, as
8 * published by the Free Software Foundation.
9 *
10 * This code is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 * version 2 for more details (a copy is included in the LICENSE file that
14 * accompanied this code).
15 *
16 * You should have received a copy of the GNU General Public License version
17 * 2 along with this work; if not, write to the Free Software Foundation,
18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 *
20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21 * or visit www.oracle.com if you need additional information or have any
22 * questions.
23 *
24 */
25
26 #include "precompiled.hpp"
27 #include "memory/metaspace/chunklevel.hpp"
28 #include "memory/metaspace/blockTree.hpp"
29 #include "memory/resourceArea.hpp"
30 #include "utilities/debug.hpp"
31 #include "utilities/globalDefinitions.hpp"
32 #include "utilities/growableArray.hpp"
33 #include "utilities/ostream.hpp"
34
35 namespace metaspace {
36
37 // Needed to prevent linker errors on MacOS and AIX
38 const size_t BlockTree::MinWordSize;
39
40 #define NODE_FORMAT \
41 "@" PTR_FORMAT \
42 ": canary " INTPTR_FORMAT \
43 ", parent " PTR_FORMAT \
44 ", left " PTR_FORMAT \
45 ", right " PTR_FORMAT \
46 ", next " PTR_FORMAT \
47 ", size " SIZE_FORMAT
48
49 #define NODE_FORMAT_ARGS(n) \
50 p2i(n), \
51 (n)->_canary, \
52 p2i((n)->_parent), \
53 p2i((n)->_left), \
54 p2i((n)->_right), \
55 p2i((n)->_next), \
56 (n)->_word_size
57
58 #ifdef ASSERT
59
60 // Tree verification
61
62 // This assert prints the tree too
63 #define tree_assert(cond, format, ...) \
64 do { \
65 if (!(cond)) { \
66 tty->print("Error in tree @" PTR_FORMAT ": ", p2i(this)); \
67 tty->print_cr(format, __VA_ARGS__); \
68 tty->print_cr("Tree:"); \
69 print_tree(tty); \
70 assert(cond, format, __VA_ARGS__); \
71 } \
72 } while (0)
73
74 // Assert, prints tree and specific given node
75 #define tree_assert_invalid_node(cond, failure_node) \
76 tree_assert(cond, "Invalid node: " NODE_FORMAT, NODE_FORMAT_ARGS(failure_node))
77
78 // walkinfo keeps a node plus the size corridor it and its children
79 // are supposed to be in.
80 struct BlockTree::walkinfo {
81 BlockTree::Node* n;
82 int depth;
83 size_t lim1; // (
84 size_t lim2; // )
85 };
86
87 // Helper for verify()
88 void BlockTree::verify_node_pointer(const Node* n) const {
89 tree_assert(os::is_readable_pointer(n),
90 "Invalid node: @" PTR_FORMAT " is unreadable.", p2i(n));
91 // If the canary is broken, this is either an invalid node pointer or
92 // the node has been overwritten. Either way, print a hex dump, then
93 // assert away.
94 if (n->_canary != Node::_canary_value) {
95 os::print_hex_dump(tty, (address)n, (address)n + sizeof(Node), 1);
96 tree_assert(false, "Invalid node: @" PTR_FORMAT " canary broken or pointer invalid", p2i(n));
97 }
98 }
99
100 void BlockTree::verify() const {
101 // Traverse the tree and test that all nodes are in the correct order.
102
103 MemRangeCounter counter;
104 if (_root != nullptr) {
105
106 ResourceMark rm;
107 GrowableArray<walkinfo> stack;
108
109 walkinfo info;
110 info.n = _root;
111 info.lim1 = 0;
112 info.lim2 = SIZE_MAX;
113 info.depth = 0;
114
115 stack.push(info);
116
117 while (stack.length() > 0) {
118 info = stack.pop();
119 const Node* n = info.n;
120
121 verify_node_pointer(n);
122
123 // Assume a (ridiculously large) edge limit to catch cases
124 // of badly degenerated or circular trees.
125 tree_assert(info.depth < 10000, "too deep (%d)", info.depth);
126 counter.add(n->_word_size);
127
128 if (n == _root) {
129 tree_assert_invalid_node(n->_parent == nullptr, n);
130 } else {
131 tree_assert_invalid_node(n->_parent != nullptr, n);
132 }
133
134 // check size and ordering
135 tree_assert_invalid_node(n->_word_size >= MinWordSize, n);
136 tree_assert_invalid_node(n->_word_size <= chunklevel::MAX_CHUNK_WORD_SIZE, n);
137 tree_assert_invalid_node(n->_word_size > info.lim1, n);
138 tree_assert_invalid_node(n->_word_size < info.lim2, n);
139
140 // Check children
141 if (n->_left != nullptr) {
142 tree_assert_invalid_node(n->_left != n, n);
143 tree_assert_invalid_node(n->_left->_parent == n, n);
144
145 walkinfo info2;
146 info2.n = n->_left;
147 info2.lim1 = info.lim1;
148 info2.lim2 = n->_word_size;
149 info2.depth = info.depth + 1;
150 stack.push(info2);
151 }
152
153 if (n->_right != nullptr) {
154 tree_assert_invalid_node(n->_right != n, n);
155 tree_assert_invalid_node(n->_right->_parent == n, n);
156
157 walkinfo info2;
158 info2.n = n->_right;
159 info2.lim1 = n->_word_size;
160 info2.lim2 = info.lim2;
161 info2.depth = info.depth + 1;
162 stack.push(info2);
163 }
164
165 // If node has same-sized siblings check those too.
166 const Node* n2 = n->_next;
167 while (n2 != nullptr) {
168 verify_node_pointer(n2);
169 tree_assert_invalid_node(n2 != n, n2); // catch simple circles
170 tree_assert_invalid_node(n2->_word_size == n->_word_size, n2);
171 counter.add(n2->_word_size);
172 n2 = n2->_next;
173 }
174 }
175 }
176
177 // At the end, check that counters match
178 // (which also verifies that we visited every node, or at least
179 // as many nodes as are in this tree)
180 _counter.check(counter);
181
182 #undef assrt0n
183 }
184
185 void BlockTree::zap_range(MetaWord* p, size_t word_size) {
186 memset(p, 0xF3, word_size * sizeof(MetaWord));
187 }
188
189 void BlockTree::print_tree(outputStream* st) const {
190
191 // Note: we do not print the tree indented, since I found that printing it
192 // as a quasi list is much clearer to the eye.
193 // We print the tree depth-first, with stacked nodes below normal ones
194 // (normal "real" nodes are marked with a leading '+')
195 if (_root != nullptr) {
196
197 ResourceMark rm;
198 GrowableArray<walkinfo> stack;
199
200 walkinfo info;
201 info.n = _root;
202 info.depth = 0;
203
204 stack.push(info);
205 while (stack.length() > 0) {
206 info = stack.pop();
207 const Node* n = info.n;
208
209 // Print node.
210 st->print("%4d + ", info.depth);
211 if (os::is_readable_pointer(n)) {
212 st->print_cr(NODE_FORMAT, NODE_FORMAT_ARGS(n));
213 } else {
214 st->print_cr("@" PTR_FORMAT ": unreadable (skipping subtree)", p2i(n));
215 continue; // don't print this subtree
216 }
217
218 // Print same-sized-nodes stacked under this node
219 for (Node* n2 = n->_next; n2 != nullptr; n2 = n2->_next) {
220 st->print_raw(" ");
221 if (os::is_readable_pointer(n2)) {
222 st->print_cr(NODE_FORMAT, NODE_FORMAT_ARGS(n2));
223 } else {
224 st->print_cr("@" PTR_FORMAT ": unreadable (skipping rest of chain).", p2i(n2));
225 break; // stop printing this chain.
226 }
227 }
228
229 // Handle children.
230 if (n->_right != nullptr) {
231 walkinfo info2;
232 info2.n = n->_right;
233 info2.depth = info.depth + 1;
234 stack.push(info2);
235 }
236 if (n->_left != nullptr) {
237 walkinfo info2;
238 info2.n = n->_left;
239 info2.depth = info.depth + 1;
240 stack.push(info2);
241 }
242 }
243
244 } else {
245 st->print_cr("<no nodes>");
246 }
247 }
248
249 #endif // ASSERT
250
251 } // namespace metaspace