1 /* 2 * Copyright (c) 2020, 2023, 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 "memory/metaspace/metablock.hpp" 33 #include "utilities/debug.hpp" 34 #include "utilities/globalDefinitions.hpp" 35 36 namespace metaspace { 37 38 // BlockTree is a rather simple binary search tree. It is used to 39 // manage medium to large free memory blocks. 40 // 41 // There is no separation between payload (managed blocks) and nodes: the 42 // memory blocks themselves are the nodes, with the block size being the key. 43 // 44 // We store node pointer information in these blocks when storing them. That 45 // imposes a minimum size to the managed memory blocks (1 word) 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); // "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 // It is initialized in debug and release, but only automatically tested 86 // in debug. 87 const intptr_t _canary; 88 89 // Normal tree node stuff... 90 // (Note: all null if this is a stacked node) 91 Node* _parent; 92 Node* _left; 93 Node* _right; 94 95 // Blocks with the same size are put in a list with this node as head. 96 Node* _next; 97 98 // Word size of node. Note that size cannot be larger than max metaspace size, 99 // so this could be very well a 32bit value (in case we ever make this a balancing 100 // tree and need additional space for weighting information). 101 const size_t _word_size; 102 103 Node(size_t word_size) : 104 _canary(_canary_value), 105 _parent(nullptr), 106 _left(nullptr), 107 _right(nullptr), 108 _next(nullptr), 109 _word_size(word_size) 110 {} 111 112 #ifdef ASSERT 113 bool valid() const { 114 return _canary == _canary_value && 115 _word_size >= sizeof(Node) && 116 _word_size < chunklevel::MAX_CHUNK_WORD_SIZE; 117 } 118 #endif 119 }; 120 121 // Needed for verify() and print_tree() 122 struct walkinfo; 123 124 #ifdef ASSERT 125 // Run a quick check on a node; upon suspicion dive into a full tree check. 126 void check_node(const Node* n) const { if (!n->valid()) verify(); } 127 #endif 128 129 public: 130 131 // Minimum word size a block has to be to be added to this structure (note ceil division). 132 const static size_t MinWordSize = 133 (sizeof(Node) + sizeof(MetaWord) - 1) / sizeof(MetaWord); 134 135 private: 136 137 Node* _root; 138 139 MemRangeCounter _counter; 140 141 // Given a node n, add it to the list starting at head 142 static void add_to_list(Node* n, Node* head) { 143 assert(head->_word_size == n->_word_size, "sanity"); 144 n->_next = head->_next; 145 head->_next = n; 146 DEBUG_ONLY(n->_left = n->_right = n->_parent = nullptr;) 147 } 148 149 // Given a node list starting at head, remove one of the follow up nodes from 150 // that list and return it. The head node gets not modified and remains in the 151 // tree. 152 // List must contain at least one other node. 153 static Node* remove_from_list(Node* head) { 154 assert(head->_next != nullptr, "sanity"); 155 Node* n = head->_next; 156 head->_next = n->_next; 157 return n; 158 } 159 160 // Given a node c and a node p, wire up c as left child of p. 161 static void set_left_child(Node* p, Node* c) { 162 p->_left = c; 163 if (c != nullptr) { 164 assert(c->_word_size < p->_word_size, "sanity"); 165 c->_parent = p; 166 } 167 } 168 169 // Given a node c and a node p, wire up c as right child of p. 170 static void set_right_child(Node* p, Node* c) { 171 p->_right = c; 172 if (c != nullptr) { 173 assert(c->_word_size > p->_word_size, "sanity"); 174 c->_parent = p; 175 } 176 } 177 178 // Given a node n, return its successor in the tree 179 // (node with the next-larger size). 180 static Node* successor(Node* n) { 181 Node* succ = nullptr; 182 if (n->_right != nullptr) { 183 // If there is a right child, search the left-most 184 // child of that child. 185 succ = n->_right; 186 while (succ->_left != nullptr) { 187 succ = succ->_left; 188 } 189 } else { 190 succ = n->_parent; 191 Node* n2 = n; 192 // As long as I am the right child of my parent, search upward 193 while (succ != nullptr && n2 == succ->_right) { 194 n2 = succ; 195 succ = succ->_parent; 196 } 197 } 198 return succ; 199 } 200 201 // Given a node, replace it with a replacement node as a child for its parent. 202 // If the node is root and has no parent, sets it as root. 203 void replace_node_in_parent(Node* child, Node* replace) { 204 Node* parent = child->_parent; 205 if (parent != nullptr) { 206 if (parent->_left == child) { // Child is left child 207 set_left_child(parent, replace); 208 } else { 209 set_right_child(parent, replace); 210 } 211 } else { 212 assert(child == _root, "must be root"); 213 _root = replace; 214 if (replace != nullptr) { 215 replace->_parent = nullptr; 216 } 217 } 218 return; 219 } 220 221 // Given a node n and an insertion point, insert n under insertion point. 222 void insert(Node* insertion_point, Node* n) { 223 assert(n->_parent == nullptr, "Sanity"); 224 for (;;) { 225 DEBUG_ONLY(check_node(insertion_point);) 226 if (n->_word_size == insertion_point->_word_size) { 227 add_to_list(n, insertion_point); // parent stays null in this case. 228 break; 229 } else if (n->_word_size > insertion_point->_word_size) { 230 if (insertion_point->_right == nullptr) { 231 set_right_child(insertion_point, n); 232 break; 233 } else { 234 insertion_point = insertion_point->_right; 235 } 236 } else { 237 if (insertion_point->_left == nullptr) { 238 set_left_child(insertion_point, n); 239 break; 240 } else { 241 insertion_point = insertion_point->_left; 242 } 243 } 244 } 245 } 246 247 // Given a node and a wish size, search this node and all children for 248 // the node closest (equal or larger sized) to the size s. 249 Node* find_closest_fit(Node* n, size_t s) { 250 Node* best_match = nullptr; 251 while (n != nullptr) { 252 DEBUG_ONLY(check_node(n);) 253 if (n->_word_size >= s) { 254 best_match = n; 255 if (n->_word_size == s) { 256 break; // perfect match or max depth reached 257 } 258 n = n->_left; 259 } else { 260 n = n->_right; 261 } 262 } 263 return best_match; 264 } 265 266 // Given a wish size, search the whole tree for a 267 // node closest (equal or larger sized) to the size s. 268 Node* find_closest_fit(size_t s) { 269 if (_root != nullptr) { 270 return find_closest_fit(_root, s); 271 } 272 return nullptr; 273 } 274 275 // Given a node n, remove it from the tree and repair tree. 276 void remove_node_from_tree(Node* n) { 277 assert(n->_next == nullptr, "do not delete a node which has a non-empty list"); 278 279 if (n->_left == nullptr && n->_right == nullptr) { 280 replace_node_in_parent(n, nullptr); 281 282 } else if (n->_left == nullptr && n->_right != nullptr) { 283 replace_node_in_parent(n, n->_right); 284 285 } else if (n->_left != nullptr && n->_right == nullptr) { 286 replace_node_in_parent(n, n->_left); 287 288 } else { 289 // Node has two children. 290 291 // 1) Find direct successor (the next larger node). 292 Node* succ = successor(n); 293 294 // There has to be a successor since n->right was != null... 295 assert(succ != nullptr, "must be"); 296 297 // ... and it should not have a left child since successor 298 // is supposed to be the next larger node, so it must be the mostleft node 299 // in the sub tree rooted at n->right 300 assert(succ->_left == nullptr, "must be"); 301 assert(succ->_word_size > n->_word_size, "sanity"); 302 303 Node* successor_parent = succ->_parent; 304 Node* successor_right_child = succ->_right; 305 306 // Remove successor from its parent. 307 if (successor_parent == n) { 308 309 // special case: successor is a direct child of n. Has to be the right child then. 310 assert(n->_right == succ, "sanity"); 311 312 // Just replace n with this successor. 313 replace_node_in_parent(n, succ); 314 315 // Take over n's old left child, too. 316 // We keep the successor's right child. 317 set_left_child(succ, n->_left); 318 } else { 319 // If the successors parent is not n, we are deeper in the tree, 320 // the successor has to be the left child of its parent. 321 assert(successor_parent->_left == succ, "sanity"); 322 323 // The right child of the successor (if there was one) replaces 324 // the successor at its parent's left child. 325 set_left_child(successor_parent, succ->_right); 326 327 // and the successor replaces n at its parent 328 replace_node_in_parent(n, succ); 329 330 // and takes over n's old children 331 set_left_child(succ, n->_left); 332 set_right_child(succ, n->_right); 333 } 334 } 335 } 336 337 #ifdef ASSERT 338 void zap_block(MetaBlock block); 339 // Helper for verify() 340 void verify_node_pointer(const Node* n) const; 341 #endif // ASSERT 342 343 public: 344 345 BlockTree() : _root(nullptr) {} 346 347 // Add a memory block to the tree. Its content will be overwritten. 348 void add_block(MetaBlock block) { 349 DEBUG_ONLY(zap_block(block);) 350 const size_t word_size = block.word_size(); 351 assert(word_size >= MinWordSize, "invalid block size " SIZE_FORMAT, word_size); 352 Node* n = new(block.base()) Node(word_size); 353 if (_root == nullptr) { 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. 363 MetaBlock remove_block(size_t word_size) { 364 assert(word_size >= MinWordSize, "invalid block size " SIZE_FORMAT, word_size); 365 366 MetaBlock result; 367 Node* n = find_closest_fit(word_size); 368 369 if (n != nullptr) { 370 DEBUG_ONLY(check_node(n);) 371 assert(n->_word_size >= word_size, "sanity"); 372 373 if (n->_next != nullptr) { 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 result = MetaBlock((MetaWord*)n, n->_word_size); 384 385 _counter.sub(n->_word_size); 386 387 DEBUG_ONLY(zap_block(result);) 388 } 389 return result; 390 } 391 392 // Returns number of blocks in this structure 393 unsigned count() const { return _counter.count(); } 394 395 // Returns total size, in words, of all elements. 396 size_t total_size() const { return _counter.total_size(); } 397 398 bool is_empty() const { return _root == nullptr; } 399 400 DEBUG_ONLY(void print_tree(outputStream* st) const;) 401 DEBUG_ONLY(void verify() const;) 402 }; 403 404 } // namespace metaspace 405 406 #endif // SHARE_MEMORY_METASPACE_BLOCKTREE_HPP --- EOF ---