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