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/counter.hpp" 31 #include "utilities/debug.hpp" 32 #include "utilities/globalDefinitions.hpp" 33 34 namespace metaspace { 35 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 MetaspaceArene::get_raw_allocation_word_size(). 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 79 struct node_t { 80 81 // Normal tree node stuff... 82 node_t* parent; 83 node_t* left; 84 node_t* right; 85 86 // blocks with the same size are put in a list with this node as head. 87 node_t* next; 88 89 // word size of node. Note that size cannot be larger than max metaspace size, 90 // so this could be very well a 32bit value (in case we ever make this a balancing 91 // tree and need additional space for weighting information). 92 size_t size; 93 94 }; 95 96 public: 97 98 // Largest node size, (bit arbitrarily) capped at 4M since we know this to 99 // be the max possible metaspace allocation size. TODO. Do this better. 100 const static size_t maximal_word_size = 4 * M; 101 102 // We need nodes to be at least large enough to hold a node_t 103 const static size_t minimal_word_size = 104 (sizeof(node_t) + sizeof(MetaWord) - 1) / sizeof(MetaWord); 105 106 private: 107 108 node_t* _root; 109 110 // As a performance optimization, we keep the size of the largest node. 111 size_t _largest_size_added; 112 113 MemRangeCounter _counter; 114 115 // given a node n, add it to the list starting at head 116 static void add_to_list(node_t* n, node_t* head) { 117 assert(head->size == n->size, "sanity"); 118 n->next = head->next; 119 head->next = n; 120 DEBUG_ONLY(n->left = n->right = n->parent = NULL;) 121 } 122 123 // given a node list starting at head, remove one node from it and return it. 124 // List must contain at least one other node. 125 static node_t* remove_from_list(node_t* head) { 126 assert(head->next != NULL, "sanity"); 127 node_t* n = head->next; 128 if (n != NULL) { 129 head->next = n->next; 130 } 131 return n; 132 } 133 134 // Given a node n and a node p, wire up n as left child of p. 135 static void set_left_child(node_t* p, node_t* c) { 136 p->left = c; 137 if (c != NULL) { 138 assert(c->size < p->size, "sanity"); 139 c->parent = p; 140 } 141 } 142 143 // Given a node n and a node p, wire up n as right child of p. 144 static void set_right_child(node_t* p, node_t* c) { 145 p->right = c; 146 if (c != NULL) { 147 assert(c->size > p->size, "sanity"); 148 c->parent = p; 149 } 150 } 151 152 // Given a node n, return its predecessor in the tree 153 // (node with the next-smaller size). 154 static node_t* predecessor(node_t* n) { 155 node_t* pred = NULL; 156 if (n->left != NULL) { 157 pred = n->left; 158 while (pred->right != NULL) { 159 pred = pred->right; 160 } 161 } else { 162 pred = n->parent; 163 node_t* n2 = n; 164 while (pred != NULL && n2 == pred->left) { 165 n2 = pred; 166 pred = pred->parent; 167 } 168 } 169 return pred; 170 } 171 172 // Given a node n, return its predecessor in the tree 173 // (node with the next-smaller size). 174 static node_t* successor(node_t* n) { 175 node_t* succ = NULL; 176 if (n->right != NULL) { 177 // If there is a right child, search the left-most 178 // child of that child. 179 succ = n->right; 180 while (succ->left != NULL) { 181 succ = succ->left; 182 } 183 } else { 184 succ = n->parent; 185 node_t* n2 = n; 186 // As long as I am the right child of my parent, search upward 187 while (succ != NULL && n2 == succ->right) { 188 n2 = succ; 189 succ = succ->parent; 190 } 191 } 192 return succ; 193 } 194 195 // Given a node, replace it with a replacement node as a child for its parent. 196 // If the node is root and has no parent, sets it as root. 197 void replace_node_in_parent(node_t* child, node_t* replace) { 198 node_t* parent = child->parent; 199 if (parent != NULL) { 200 if (parent->left == child) { // I am a left child 201 set_left_child(parent, replace); 202 } else { 203 set_right_child(parent, replace); 204 } 205 } else { 206 assert(child == _root, "must be root"); 207 _root = replace; 208 if (replace != NULL) { 209 replace->parent = NULL; 210 } 211 } 212 return; 213 } 214 215 // Given a node n and a node forebear, insert n under forebear 216 void insert(node_t* forebear, node_t* n) { 217 if (n->size == forebear->size) { 218 add_to_list(n, forebear); // parent stays NULL in this case. 219 } else { 220 if (n->size < forebear->size) { 221 if (forebear->left == NULL) { 222 set_left_child(forebear, n); 223 } else { 224 insert(forebear->left, n); 225 } 226 } else { 227 assert(n->size > forebear->size, "sanity"); 228 if (forebear->right == NULL) { 229 set_right_child(forebear, n); 230 if (_largest_size_added < n->size) { 231 _largest_size_added = n->size; 232 } 233 } else { 234 insert(forebear->right, n); 235 } 236 } 237 } 238 } 239 240 // Given a node and a wish size, search this node and all children for 241 // the node closest (equal or larger sized) to the size s. 242 static node_t* find_closest_fit(node_t* n, size_t s) { 243 244 if (n->size == s) { 245 // Perfect fit. 246 return n; 247 248 } else if (n->size < s) { 249 // too small, dive down right side 250 if (n->right != NULL) { 251 return find_closest_fit(n->right, s); 252 } else { 253 return NULL; 254 } 255 } else { 256 // n is a possible fit 257 assert(n->size > s, "Sanity"); 258 if (n->left != NULL && n->left->size >= s) { 259 // but not the best - dive down left side. 260 return find_closest_fit(n->left, s); 261 } else { 262 // n is the best fit. 263 return n; 264 } 265 } 266 267 } 268 269 // Given a wish size, search the whole tree for a 270 // node closest (equal or larger sized) to the size s. 271 node_t* find_closest_fit(size_t s) { 272 if (_root != NULL) { 273 return find_closest_fit(_root, s); 274 } 275 return NULL; 276 } 277 278 // Given a node n, remove it from the tree and repair tree. 279 void remove_node_from_tree(node_t* n) { 280 281 assert(n->next == NULL, "do not delete a node which has a non-empty list"); 282 283 // Maintain largest size node to speed up lookup 284 if (n->size == _largest_size_added) { 285 node_t* pred = predecessor(n); 286 if (pred != NULL) { 287 _largest_size_added = pred->size; 288 } else { 289 _largest_size_added = 0; 290 } 291 } 292 293 if (n->left == NULL && n->right == NULL) { 294 replace_node_in_parent(n, NULL); 295 296 } else if (n->left == NULL && n->right != NULL) { 297 replace_node_in_parent(n, n->right); 298 299 } else if (n->left != NULL && n->right == NULL) { 300 replace_node_in_parent(n, n->left); 301 302 } else { 303 304 // Node has two children. 305 306 // 1) Find direct successor (the next larger node). 307 node_t* succ = successor(n); 308 309 // There has to be a successor since n->right was != NULL... 310 assert(succ != NULL, "must be"); 311 312 // ... and it should not have a left child since successor 313 // is supposed to be the next larger node, so it must be the mostleft node 314 // in the sub tree rooted at n->right 315 assert(succ->left == NULL, "must be"); 316 317 assert(succ->size > n->size, "sanity"); 318 319 node_t* successor_parent = succ->parent; 320 node_t* successor_right_child = succ->right; 321 322 // Remove successor from its parent. 323 if (successor_parent == n) { 324 325 // special case: successor is a direct child of n. Has to be the right child then. 326 assert(n->right == succ, "sanity"); 327 328 // Just replace n with this successor. 329 replace_node_in_parent(n, succ); 330 331 // Take over n's old left child, too. 332 // We keep the successor's right child. 333 set_left_child(succ, n->left); 334 335 } else { 336 337 // If the successors parent is not n, we are deeper in the tree, 338 // the successor has to be the left child of its parent. 339 assert(successor_parent->left == succ, "sanity"); 340 341 // The right child of the successor (if there was one) replaces the successor at its parent's left child. 342 set_left_child(successor_parent, succ->right); 343 344 // and the successor replaces n at its parent 345 replace_node_in_parent(n, succ); 346 347 // and takes over n's old children 348 set_left_child(succ, n->left); 349 set_right_child(succ, n->right); 350 351 } 352 } 353 } 354 355 #ifdef ASSERT 356 357 struct veri_data_t; 358 void verify_node_siblings(node_t* n, veri_data_t* vd) const; 359 void verify_node(node_t* n, size_t left_limit, size_t right_limit, veri_data_t* vd, int lvl) const; 360 void verify_tree() const; 361 362 void zap_range(MetaWord* p, size_t word_size); 363 364 #endif // ASSERT 365 366 367 static void print_node(outputStream* st, node_t* n, int lvl); 368 369 public: 370 371 BlockTree() : _root(NULL), _largest_size_added(0) {} 372 373 // Add a memory block to the tree. Memory block will be used to store 374 // node information. 375 void add_block(MetaWord* p, size_t word_size) { 376 DEBUG_ONLY(zap_range(p, word_size)); 377 assert(word_size >= minimal_word_size && word_size < maximal_word_size, 378 "invalid block size " SIZE_FORMAT, word_size); 379 node_t* n = (node_t*)p; 380 n->size = word_size; 381 n->next = n->left = n->right = n->parent = NULL; 382 if (_root == NULL) { 383 _root = n; 384 } else { 385 insert(_root, n); 386 } 387 _counter.add(word_size); 388 389 // Maintain largest node to speed up lookup 390 if (_largest_size_added < n->size) { 391 _largest_size_added = n->size; 392 } 393 394 } 395 396 // Given a word_size, searches and returns a block of at least that size. 397 // Block may be larger. Real block size is returned in *p_real_word_size. 398 MetaWord* get_block(size_t word_size, size_t* p_real_word_size) { 399 assert(word_size >= minimal_word_size && word_size < maximal_word_size, 400 "invalid block size " SIZE_FORMAT, word_size); 401 402 if (_largest_size_added < word_size) { 403 return NULL; 404 } 405 406 node_t* n = find_closest_fit(word_size); 407 408 if (n != NULL) { 409 assert(n->size >= word_size, "sanity"); 410 411 // If the node has siblings, remove one of them, 412 // otherwise remove this node from the tree. 413 if (n->next != NULL) { 414 n = remove_from_list(n); 415 } else { 416 remove_node_from_tree(n); 417 } 418 419 MetaWord* p = (MetaWord*)n; 420 *p_real_word_size = n->size; 421 422 _counter.sub(n->size); 423 424 DEBUG_ONLY(zap_range(p, n->size)); 425 426 return p; 427 } 428 return NULL; 429 } 430 431 432 // Returns number of blocks in this structure 433 unsigned count() const { return _counter.count(); } 434 435 // Returns total size, in words, of all elements. 436 size_t total_size() const { return _counter.total_size(); } 437 438 bool is_empty() const { return _root == NULL; } 439 440 void print_tree(outputStream* st) const; 441 442 DEBUG_ONLY(void verify() const { verify_tree(); }) 443 444 }; 445 446 } // namespace metaspace 447 448 #endif // SHARE_MEMORY_METASPACE_BLOCKTREE_HPP