1 /*
2 * Copyright (c) 2020, Oracle and/or its affiliates. All rights reserved.
3 * Copyright (c) 2020 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
28 #include "memory/metaspace/msBlockTree.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 #ifdef ASSERT
38
39 // Tree verification
40
41 // These asserts prints the tree, then asserts
42 #define assrt(cond, format, ...) \
43 do { \
44 if (!(cond)) { \
45 print_tree(tty); \
46 assert(cond, format, __VA_ARGS__); \
47 } \
48 } while(0)
49
50 // This assert prints the tree, then stops (generic message)
51 #define assrt0(cond) \
52 do { \
53 if (!(cond)) { \
54 print_tree(tty); \
55 assert(cond, "sanity"); \
56 } \
57 } while(0)
58
59
60
61 // walkinfo keeps a node plus the size corridor it and its children
62 // are supposed to be in.
63 struct BlockTree::walkinfo {
64 BlockTree::Node* n;
65 int depth;
66 size_t lim1; // (
67 size_t lim2; // )
68 };
69
70 void BlockTree::verify() const {
71
72 // Traverse the tree and test that all nodes are in the correct order.
73
74 MemRangeCounter counter;
75 int longest_edge = 0;
76
77 if (_root != NULL) {
78
79 ResourceMark rm;
80
81 GrowableArray<walkinfo> stack;
82
83 walkinfo info;
84 info.n = _root;
85 info.lim1 = 0;
86 info.lim2 = SIZE_MAX;
87 info.depth = 0;
88
89 stack.push(info);
90
91 while (stack.length() > 0) {
92
93 info = stack.pop();
94 const Node* n = info.n;
95
96 // Assume a (ridiculously large) edge limit to catch cases
97 // of badly degenerated or circular trees.
98 assrt0(info.depth < 10000);
99
100 counter.add(n->_word_size);
101
102 // Verify node.
103 if (n == _root) {
104 assrt0(n->_parent == NULL);
105 } else {
106 assrt0(n->_parent != NULL);
107 }
108
109 // check size and ordering
110 assrt(n->_word_size >= MinWordSize, "bad node size " SIZE_FORMAT, n->_word_size);
111 assrt0(n->_word_size > info.lim1);
112 assrt0(n->_word_size < info.lim2);
113
114 // Check children
115 if (n->_left != NULL) {
116 assrt0(n->_left != n);
117 assrt0(n->_left->_parent == n);
118
119 walkinfo info2;
120 info2.n = n->_left;
121 info2.lim1 = info.lim1;
122 info2.lim2 = n->_word_size;
123 info2.depth = info.depth + 1;
124 stack.push(info2);
125 }
126
127 if (n->_right != NULL) {
128 assrt0(n->_right != n);
129 assrt0(n->_right->_parent == n);
130
131 walkinfo info2;
132 info2.n = n->_right;
133 info2.lim1 = n->_word_size;
134 info2.lim2 = info.lim2;
135 info2.depth = info.depth + 1;
136 stack.push(info2);
137 }
138
139 // If node has same-sized siblings check those too.
140 const Node* n2 = n->_next;
141 while (n2 != NULL) {
142 assrt0(n2 != n);
143 assrt0(n2->_word_size == n->_word_size);
144 counter.add(n2->_word_size);
145 n2 = n2->_next;
146 }
147 }
148 }
149
150 // At the end, check that counters match
151 _counter.check(counter);
152
153 }
154
155 void BlockTree::zap_range(MetaWord* p, size_t word_size) {
156 memset(p, 0xF3, word_size * sizeof(MetaWord));
157 }
158
159 #undef assrt
160 #undef assrt0
161
162 void BlockTree::print_tree(outputStream* st) const {
163
164 if (_root != NULL) {
165
166 ResourceMark rm;
167
168 GrowableArray<walkinfo> stack;
169
170 walkinfo info;
171 info.n = _root;
172 info.depth = 0;
173
174 stack.push(info);
175 while (stack.length() > 0) {
176 info = stack.pop();
177 const Node* n = info.n;
178 // Print node.
179 for (int i = 0; i < info.depth; i++) {
180 st->print("---");
181 }
182 st->print_cr("<" PTR_FORMAT " (size " SIZE_FORMAT ")", p2i(n), n->_word_size);
183 // Handle children.
184 if (n->_right != NULL) {
185 walkinfo info2;
186 info2.n = n->_right;
187 info2.depth = info.depth + 1;
188 stack.push(info2);
189 }
190 if (n->_left != NULL) {
191 walkinfo info2;
192 info2.n = n->_left;
193 info2.depth = info.depth + 1;
194 stack.push(info2);
195 }
196 }
197
198 } else {
199 st->print_cr("<no nodes>");
200 }
201 }
202
203 #endif // ASSERT
204
205 } // namespace metaspace