| File: | jdk/src/hotspot/share/memory/metaspace/blockTree.hpp |
| Warning: | line 305, column 13 Value stored to 'successor_right_child' during its initialization is never read |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
| 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 | #ifndef SHARE_MEMORY_METASPACE_BLOCKTREE_HPP |
| 27 | #define SHARE_MEMORY_METASPACE_BLOCKTREE_HPP |
| 28 | |
| 29 | #include "memory/allocation.hpp" |
| 30 | #include "memory/metaspace/chunklevel.hpp" |
| 31 | #include "memory/metaspace/counters.hpp" |
| 32 | #include "utilities/debug.hpp" |
| 33 | #include "utilities/globalDefinitions.hpp" |
| 34 | |
| 35 | namespace metaspace { |
| 36 | |
| 37 | // BlockTree is a rather simple binary search tree. It is used to |
| 38 | // manage small to medium free memory blocks (see class FreeBlocks). |
| 39 | // |
| 40 | // There is no separation between payload (managed blocks) and nodes: the |
| 41 | // memory blocks themselves are the nodes, with the block size being the key. |
| 42 | // |
| 43 | // We store node pointer information in these blocks when storing them. That |
| 44 | // imposes a minimum size to the managed memory blocks. |
| 45 | // See get_raw_word_size_for_requested_word_size() (msCommon.hpp). |
| 46 | // |
| 47 | // We want to manage many memory blocks of the same size, but we want |
| 48 | // to prevent the tree from blowing up and degenerating into a list. Therefore |
| 49 | // there is only one node for each unique block size; subsequent blocks of the |
| 50 | // same size are stacked below that first node: |
| 51 | // |
| 52 | // +-----+ |
| 53 | // | 100 | |
| 54 | // +-----+ |
| 55 | // / \ |
| 56 | // +-----+ |
| 57 | // | 80 | |
| 58 | // +-----+ |
| 59 | // / | \ |
| 60 | // / +-----+ \ |
| 61 | // +-----+ | 80 | +-----+ |
| 62 | // | 70 | +-----+ | 85 | |
| 63 | // +-----+ | +-----+ |
| 64 | // +-----+ |
| 65 | // | 80 | |
| 66 | // +-----+ |
| 67 | // |
| 68 | // |
| 69 | // Todo: This tree is unbalanced. It would be a good fit for a red-black tree. |
| 70 | // In order to make this a red-black tree, we need an algorithm which can deal |
| 71 | // with nodes which are their own payload (most red-black tree implementations |
| 72 | // swap payloads of their nodes at some point, see e.g. j.u.TreeSet). |
| 73 | // A good example is the Linux kernel rbtree, which is a clean, easy-to-read |
| 74 | // implementation. |
| 75 | |
| 76 | class BlockTree: public CHeapObj<mtMetaspace> { |
| 77 | |
| 78 | struct Node { |
| 79 | |
| 80 | static const intptr_t _canary_value = |
| 81 | NOT_LP64(0x4e4f4445) LP64_ONLY(0x4e4f44454e4f4445ULL)0x4e4f44454e4f4445ULL; // "NODE" resp "NODENODE" |
| 82 | |
| 83 | // Note: we afford us the luxury of an always-there canary value. |
| 84 | // The space for that is there (these nodes are only used to manage larger blocks, |
| 85 | // see FreeBlocks::MaxSmallBlocksWordSize). |
| 86 | // It is initialized in debug and release, but only automatically tested |
| 87 | // in debug. |
| 88 | const intptr_t _canary; |
| 89 | |
| 90 | // Normal tree node stuff... |
| 91 | // (Note: all null if this is a stacked node) |
| 92 | Node* _parent; |
| 93 | Node* _left; |
| 94 | Node* _right; |
| 95 | |
| 96 | // Blocks with the same size are put in a list with this node as head. |
| 97 | Node* _next; |
| 98 | |
| 99 | // Word size of node. Note that size cannot be larger than max metaspace size, |
| 100 | // so this could be very well a 32bit value (in case we ever make this a balancing |
| 101 | // tree and need additional space for weighting information). |
| 102 | const size_t _word_size; |
| 103 | |
| 104 | Node(size_t word_size) : |
| 105 | _canary(_canary_value), |
| 106 | _parent(NULL__null), |
| 107 | _left(NULL__null), |
| 108 | _right(NULL__null), |
| 109 | _next(NULL__null), |
| 110 | _word_size(word_size) |
| 111 | {} |
| 112 | |
| 113 | #ifdef ASSERT1 |
| 114 | bool valid() const { |
| 115 | return _canary == _canary_value && |
| 116 | _word_size >= sizeof(Node) && |
| 117 | _word_size < chunklevel::MAX_CHUNK_WORD_SIZE; |
| 118 | } |
| 119 | #endif |
| 120 | }; |
| 121 | |
| 122 | // Needed for verify() and print_tree() |
| 123 | struct walkinfo; |
| 124 | |
| 125 | #ifdef ASSERT1 |
| 126 | // Run a quick check on a node; upon suspicion dive into a full tree check. |
| 127 | void check_node(const Node* n) const { if (!n->valid()) verify(); } |
| 128 | #endif |
| 129 | |
| 130 | public: |
| 131 | |
| 132 | // Minimum word size a block has to be to be added to this structure (note ceil division). |
| 133 | const static size_t MinWordSize = |
| 134 | (sizeof(Node) + sizeof(MetaWord) - 1) / sizeof(MetaWord); |
| 135 | |
| 136 | private: |
| 137 | |
| 138 | Node* _root; |
| 139 | |
| 140 | MemRangeCounter _counter; |
| 141 | |
| 142 | // Given a node n, add it to the list starting at head |
| 143 | static void add_to_list(Node* n, Node* head) { |
| 144 | assert(head->_word_size == n->_word_size, "sanity")do { if (!(head->_word_size == n->_word_size)) { (*g_assert_poison ) = 'X';; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/memory/metaspace/blockTree.hpp" , 144, "assert(" "head->_word_size == n->_word_size" ") failed" , "sanity"); ::breakpoint(); } } while (0); |
| 145 | n->_next = head->_next; |
| 146 | head->_next = n; |
| 147 | DEBUG_ONLY(n->_left = n->_right = n->_parent = NULL;)n->_left = n->_right = n->_parent = __null; |
| 148 | } |
| 149 | |
| 150 | // Given a node list starting at head, remove one of the follow up nodes from |
| 151 | // that list and return it. The head node gets not modified and remains in the |
| 152 | // tree. |
| 153 | // List must contain at least one other node. |
| 154 | static Node* remove_from_list(Node* head) { |
| 155 | assert(head->_next != NULL, "sanity")do { if (!(head->_next != __null)) { (*g_assert_poison) = 'X' ;; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/memory/metaspace/blockTree.hpp" , 155, "assert(" "head->_next != __null" ") failed", "sanity" ); ::breakpoint(); } } while (0); |
| 156 | Node* n = head->_next; |
| 157 | head->_next = n->_next; |
| 158 | return n; |
| 159 | } |
| 160 | |
| 161 | // Given a node c and a node p, wire up c as left child of p. |
| 162 | static void set_left_child(Node* p, Node* c) { |
| 163 | p->_left = c; |
| 164 | if (c != NULL__null) { |
| 165 | assert(c->_word_size < p->_word_size, "sanity")do { if (!(c->_word_size < p->_word_size)) { (*g_assert_poison ) = 'X';; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/memory/metaspace/blockTree.hpp" , 165, "assert(" "c->_word_size < p->_word_size" ") failed" , "sanity"); ::breakpoint(); } } while (0); |
| 166 | c->_parent = p; |
| 167 | } |
| 168 | } |
| 169 | |
| 170 | // Given a node c and a node p, wire up c as right child of p. |
| 171 | static void set_right_child(Node* p, Node* c) { |
| 172 | p->_right = c; |
| 173 | if (c != NULL__null) { |
| 174 | assert(c->_word_size > p->_word_size, "sanity")do { if (!(c->_word_size > p->_word_size)) { (*g_assert_poison ) = 'X';; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/memory/metaspace/blockTree.hpp" , 174, "assert(" "c->_word_size > p->_word_size" ") failed" , "sanity"); ::breakpoint(); } } while (0); |
| 175 | c->_parent = p; |
| 176 | } |
| 177 | } |
| 178 | |
| 179 | // Given a node n, return its successor in the tree |
| 180 | // (node with the next-larger size). |
| 181 | static Node* successor(Node* n) { |
| 182 | Node* succ = NULL__null; |
| 183 | if (n->_right != NULL__null) { |
| 184 | // If there is a right child, search the left-most |
| 185 | // child of that child. |
| 186 | succ = n->_right; |
| 187 | while (succ->_left != NULL__null) { |
| 188 | succ = succ->_left; |
| 189 | } |
| 190 | } else { |
| 191 | succ = n->_parent; |
| 192 | Node* n2 = n; |
| 193 | // As long as I am the right child of my parent, search upward |
| 194 | while (succ != NULL__null && n2 == succ->_right) { |
| 195 | n2 = succ; |
| 196 | succ = succ->_parent; |
| 197 | } |
| 198 | } |
| 199 | return succ; |
| 200 | } |
| 201 | |
| 202 | // Given a node, replace it with a replacement node as a child for its parent. |
| 203 | // If the node is root and has no parent, sets it as root. |
| 204 | void replace_node_in_parent(Node* child, Node* replace) { |
| 205 | Node* parent = child->_parent; |
| 206 | if (parent != NULL__null) { |
| 207 | if (parent->_left == child) { // Child is left child |
| 208 | set_left_child(parent, replace); |
| 209 | } else { |
| 210 | set_right_child(parent, replace); |
| 211 | } |
| 212 | } else { |
| 213 | assert(child == _root, "must be root")do { if (!(child == _root)) { (*g_assert_poison) = 'X';; report_vm_error ("/home/daniel/Projects/java/jdk/src/hotspot/share/memory/metaspace/blockTree.hpp" , 213, "assert(" "child == _root" ") failed", "must be root") ; ::breakpoint(); } } while (0); |
| 214 | _root = replace; |
| 215 | if (replace != NULL__null) { |
| 216 | replace->_parent = NULL__null; |
| 217 | } |
| 218 | } |
| 219 | return; |
| 220 | } |
| 221 | |
| 222 | // Given a node n and an insertion point, insert n under insertion point. |
| 223 | void insert(Node* insertion_point, Node* n) { |
| 224 | assert(n->_parent == NULL, "Sanity")do { if (!(n->_parent == __null)) { (*g_assert_poison) = 'X' ;; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/memory/metaspace/blockTree.hpp" , 224, "assert(" "n->_parent == __null" ") failed", "Sanity" ); ::breakpoint(); } } while (0); |
| 225 | for (;;) { |
| 226 | DEBUG_ONLY(check_node(insertion_point);)check_node(insertion_point); |
| 227 | if (n->_word_size == insertion_point->_word_size) { |
| 228 | add_to_list(n, insertion_point); // parent stays NULL in this case. |
| 229 | break; |
| 230 | } else if (n->_word_size > insertion_point->_word_size) { |
| 231 | if (insertion_point->_right == NULL__null) { |
| 232 | set_right_child(insertion_point, n); |
| 233 | break; |
| 234 | } else { |
| 235 | insertion_point = insertion_point->_right; |
| 236 | } |
| 237 | } else { |
| 238 | if (insertion_point->_left == NULL__null) { |
| 239 | set_left_child(insertion_point, n); |
| 240 | break; |
| 241 | } else { |
| 242 | insertion_point = insertion_point->_left; |
| 243 | } |
| 244 | } |
| 245 | } |
| 246 | } |
| 247 | |
| 248 | // Given a node and a wish size, search this node and all children for |
| 249 | // the node closest (equal or larger sized) to the size s. |
| 250 | Node* find_closest_fit(Node* n, size_t s) { |
| 251 | Node* best_match = NULL__null; |
| 252 | while (n != NULL__null) { |
| 253 | DEBUG_ONLY(check_node(n);)check_node(n); |
| 254 | if (n->_word_size >= s) { |
| 255 | best_match = n; |
| 256 | if (n->_word_size == s) { |
| 257 | break; // perfect match or max depth reached |
| 258 | } |
| 259 | n = n->_left; |
| 260 | } else { |
| 261 | n = n->_right; |
| 262 | } |
| 263 | } |
| 264 | return best_match; |
| 265 | } |
| 266 | |
| 267 | // Given a wish size, search the whole tree for a |
| 268 | // node closest (equal or larger sized) to the size s. |
| 269 | Node* find_closest_fit(size_t s) { |
| 270 | if (_root != NULL__null) { |
| 271 | return find_closest_fit(_root, s); |
| 272 | } |
| 273 | return NULL__null; |
| 274 | } |
| 275 | |
| 276 | // Given a node n, remove it from the tree and repair tree. |
| 277 | void remove_node_from_tree(Node* n) { |
| 278 | assert(n->_next == NULL, "do not delete a node which has a non-empty list")do { if (!(n->_next == __null)) { (*g_assert_poison) = 'X' ;; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/memory/metaspace/blockTree.hpp" , 278, "assert(" "n->_next == __null" ") failed", "do not delete a node which has a non-empty list" ); ::breakpoint(); } } while (0); |
| 279 | |
| 280 | if (n->_left == NULL__null && n->_right == NULL__null) { |
| 281 | replace_node_in_parent(n, NULL__null); |
| 282 | |
| 283 | } else if (n->_left == NULL__null && n->_right != NULL__null) { |
| 284 | replace_node_in_parent(n, n->_right); |
| 285 | |
| 286 | } else if (n->_left != NULL__null && n->_right == NULL__null) { |
| 287 | replace_node_in_parent(n, n->_left); |
| 288 | |
| 289 | } else { |
| 290 | // Node has two children. |
| 291 | |
| 292 | // 1) Find direct successor (the next larger node). |
| 293 | Node* succ = successor(n); |
| 294 | |
| 295 | // There has to be a successor since n->right was != NULL... |
| 296 | assert(succ != NULL, "must be")do { if (!(succ != __null)) { (*g_assert_poison) = 'X';; report_vm_error ("/home/daniel/Projects/java/jdk/src/hotspot/share/memory/metaspace/blockTree.hpp" , 296, "assert(" "succ != __null" ") failed", "must be"); ::breakpoint (); } } while (0); |
| 297 | |
| 298 | // ... and it should not have a left child since successor |
| 299 | // is supposed to be the next larger node, so it must be the mostleft node |
| 300 | // in the sub tree rooted at n->right |
| 301 | assert(succ->_left == NULL, "must be")do { if (!(succ->_left == __null)) { (*g_assert_poison) = 'X' ;; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/memory/metaspace/blockTree.hpp" , 301, "assert(" "succ->_left == __null" ") failed", "must be" ); ::breakpoint(); } } while (0); |
| 302 | assert(succ->_word_size > n->_word_size, "sanity")do { if (!(succ->_word_size > n->_word_size)) { (*g_assert_poison ) = 'X';; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/memory/metaspace/blockTree.hpp" , 302, "assert(" "succ->_word_size > n->_word_size" ") failed" , "sanity"); ::breakpoint(); } } while (0); |
| 303 | |
| 304 | Node* successor_parent = succ->_parent; |
| 305 | Node* successor_right_child = succ->_right; |
Value stored to 'successor_right_child' during its initialization is never read | |
| 306 | |
| 307 | // Remove successor from its parent. |
| 308 | if (successor_parent == n) { |
| 309 | |
| 310 | // special case: successor is a direct child of n. Has to be the right child then. |
| 311 | assert(n->_right == succ, "sanity")do { if (!(n->_right == succ)) { (*g_assert_poison) = 'X'; ; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/memory/metaspace/blockTree.hpp" , 311, "assert(" "n->_right == succ" ") failed", "sanity") ; ::breakpoint(); } } while (0); |
| 312 | |
| 313 | // Just replace n with this successor. |
| 314 | replace_node_in_parent(n, succ); |
| 315 | |
| 316 | // Take over n's old left child, too. |
| 317 | // We keep the successor's right child. |
| 318 | set_left_child(succ, n->_left); |
| 319 | } else { |
| 320 | // If the successors parent is not n, we are deeper in the tree, |
| 321 | // the successor has to be the left child of its parent. |
| 322 | assert(successor_parent->_left == succ, "sanity")do { if (!(successor_parent->_left == succ)) { (*g_assert_poison ) = 'X';; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/memory/metaspace/blockTree.hpp" , 322, "assert(" "successor_parent->_left == succ" ") failed" , "sanity"); ::breakpoint(); } } while (0); |
| 323 | |
| 324 | // The right child of the successor (if there was one) replaces |
| 325 | // the successor at its parent's left child. |
| 326 | set_left_child(successor_parent, succ->_right); |
| 327 | |
| 328 | // and the successor replaces n at its parent |
| 329 | replace_node_in_parent(n, succ); |
| 330 | |
| 331 | // and takes over n's old children |
| 332 | set_left_child(succ, n->_left); |
| 333 | set_right_child(succ, n->_right); |
| 334 | } |
| 335 | } |
| 336 | } |
| 337 | |
| 338 | #ifdef ASSERT1 |
| 339 | void zap_range(MetaWord* p, size_t word_size); |
| 340 | // Helper for verify() |
| 341 | void verify_node_pointer(const Node* n) const; |
| 342 | #endif // ASSERT |
| 343 | |
| 344 | public: |
| 345 | |
| 346 | BlockTree() : _root(NULL__null) {} |
| 347 | |
| 348 | // Add a memory block to the tree. Its content will be overwritten. |
| 349 | void add_block(MetaWord* p, size_t word_size) { |
| 350 | DEBUG_ONLY(zap_range(p, word_size))zap_range(p, word_size); |
| 351 | assert(word_size >= MinWordSize, "invalid block size " SIZE_FORMAT, word_size)do { if (!(word_size >= MinWordSize)) { (*g_assert_poison) = 'X';; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/memory/metaspace/blockTree.hpp" , 351, "assert(" "word_size >= MinWordSize" ") failed", "invalid block size " "%" "l" "u", word_size); ::breakpoint(); } } while (0); |
| 352 | Node* n = new(p) Node(word_size); |
| 353 | if (_root == NULL__null) { |
| 354 | _root = n; |
| 355 | } else { |
| 356 | insert(_root, n); |
| 357 | } |
| 358 | _counter.add(word_size); |
| 359 | } |
| 360 | |
| 361 | // Given a word_size, search and return the smallest block that is equal or |
| 362 | // larger than that size. Upon return, *p_real_word_size contains the actual |
| 363 | // block size. |
| 364 | MetaWord* remove_block(size_t word_size, size_t* p_real_word_size) { |
| 365 | assert(word_size >= MinWordSize, "invalid block size " SIZE_FORMAT, word_size)do { if (!(word_size >= MinWordSize)) { (*g_assert_poison) = 'X';; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/memory/metaspace/blockTree.hpp" , 365, "assert(" "word_size >= MinWordSize" ") failed", "invalid block size " "%" "l" "u", word_size); ::breakpoint(); } } while (0); |
| 366 | |
| 367 | Node* n = find_closest_fit(word_size); |
| 368 | |
| 369 | if (n != NULL__null) { |
| 370 | DEBUG_ONLY(check_node(n);)check_node(n); |
| 371 | assert(n->_word_size >= word_size, "sanity")do { if (!(n->_word_size >= word_size)) { (*g_assert_poison ) = 'X';; report_vm_error("/home/daniel/Projects/java/jdk/src/hotspot/share/memory/metaspace/blockTree.hpp" , 371, "assert(" "n->_word_size >= word_size" ") failed" , "sanity"); ::breakpoint(); } } while (0); |
| 372 | |
| 373 | if (n->_next != NULL__null) { |
| 374 | // If the node is head of a chain of same sized nodes, we leave it alone |
| 375 | // and instead remove one of the follow up nodes (which is simpler than |
| 376 | // removing the chain head node and then having to graft the follow up |
| 377 | // node into its place in the tree). |
| 378 | n = remove_from_list(n); |
| 379 | } else { |
| 380 | remove_node_from_tree(n); |
| 381 | } |
| 382 | |
| 383 | MetaWord* p = (MetaWord*)n; |
| 384 | *p_real_word_size = n->_word_size; |
| 385 | |
| 386 | _counter.sub(n->_word_size); |
| 387 | |
| 388 | DEBUG_ONLY(zap_range(p, n->_word_size))zap_range(p, n->_word_size); |
| 389 | return p; |
| 390 | } |
| 391 | return NULL__null; |
| 392 | } |
| 393 | |
| 394 | // Returns number of blocks in this structure |
| 395 | unsigned count() const { return _counter.count(); } |
| 396 | |
| 397 | // Returns total size, in words, of all elements. |
| 398 | size_t total_size() const { return _counter.total_size(); } |
| 399 | |
| 400 | bool is_empty() const { return _root == NULL__null; } |
| 401 | |
| 402 | DEBUG_ONLY(void print_tree(outputStream* st) const;)void print_tree(outputStream* st) const; |
| 403 | DEBUG_ONLY(void verify() const;)void verify() const; |
| 404 | }; |
| 405 | |
| 406 | } // namespace metaspace |
| 407 | |
| 408 | #endif // SHARE_MEMORY_METASPACE_BLOCKTREE_HPP |