1 /* 2 * Copyright (c) 2001, 2017, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 * 23 */ 24 25 #ifndef SHARE_VM_MEMORY_BINARYTREEDICTIONARY_INLINE_HPP 26 #define SHARE_VM_MEMORY_BINARYTREEDICTIONARY_INLINE_HPP 27 28 #include "gc/shared/spaceDecorator.hpp" 29 #include "logging/log.hpp" 30 #include "logging/logStream.hpp" 31 #include "memory/binaryTreeDictionary.hpp" 32 #include "memory/freeList.inline.hpp" 33 #include "memory/resourceArea.hpp" 34 #include "runtime/mutex.hpp" 35 #include "runtime/globals.hpp" 36 #include "utilities/macros.hpp" 37 #include "utilities/ostream.hpp" 38 39 //////////////////////////////////////////////////////////////////////////////// 40 // A binary tree based search structure for free blocks. 41 // This is currently used in the Concurrent Mark&Sweep implementation. 42 //////////////////////////////////////////////////////////////////////////////// 43 44 template <class Chunk_t, class FreeList_t> 45 TreeChunk<Chunk_t, FreeList_t>* TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(Chunk_t* fc) { 46 // Do some assertion checking here. 47 return (TreeChunk<Chunk_t, FreeList_t>*) fc; 48 } 49 50 template <class Chunk_t, class FreeList_t> 51 void TreeChunk<Chunk_t, FreeList_t>::verify_tree_chunk_list() const { 52 TreeChunk<Chunk_t, FreeList_t>* nextTC = (TreeChunk<Chunk_t, FreeList_t>*)next(); 53 if (prev() != NULL) { // interior list node shouldn't have tree fields 54 guarantee(embedded_list()->parent() == NULL && embedded_list()->left() == NULL && 55 embedded_list()->right() == NULL, "should be clear"); 56 } 57 if (nextTC != NULL) { 58 guarantee(as_TreeChunk(nextTC->prev()) == this, "broken chain"); 59 guarantee(nextTC->size() == size(), "wrong size"); 60 nextTC->verify_tree_chunk_list(); 61 } 62 } 63 64 template <class Chunk_t, class FreeList_t> 65 TreeList<Chunk_t, FreeList_t>::TreeList() : _parent(NULL), 66 _left(NULL), _right(NULL) {} 67 68 template <class Chunk_t, class FreeList_t> 69 TreeList<Chunk_t, FreeList_t>* 70 TreeList<Chunk_t, FreeList_t>::as_TreeList(TreeChunk<Chunk_t,FreeList_t>* tc) { 71 // This first free chunk in the list will be the tree list. 72 assert((tc->size() >= (TreeChunk<Chunk_t, FreeList_t>::min_size())), 73 "Chunk is too small for a TreeChunk"); 74 TreeList<Chunk_t, FreeList_t>* tl = tc->embedded_list(); 75 tl->initialize(); 76 tc->set_list(tl); 77 tl->set_size(tc->size()); 78 tl->link_head(tc); 79 tl->link_tail(tc); 80 tl->set_count(1); 81 assert(tl->parent() == NULL, "Should be clear"); 82 return tl; 83 } 84 85 template <class Chunk_t, class FreeList_t> 86 TreeList<Chunk_t, FreeList_t>* 87 TreeList<Chunk_t, FreeList_t>::as_TreeList(HeapWord* addr, size_t size) { 88 TreeChunk<Chunk_t, FreeList_t>* tc = (TreeChunk<Chunk_t, FreeList_t>*) addr; 89 assert((size >= TreeChunk<Chunk_t, FreeList_t>::min_size()), 90 "Chunk is too small for a TreeChunk"); 91 // The space will have been mangled initially but 92 // is not remangled when a Chunk_t is returned to the free list 93 // (since it is used to maintain the chunk on the free list). 94 tc->assert_is_mangled(); 95 tc->set_size(size); 96 tc->link_prev(NULL); 97 tc->link_next(NULL); 98 TreeList<Chunk_t, FreeList_t>* tl = TreeList<Chunk_t, FreeList_t>::as_TreeList(tc); 99 return tl; 100 } 101 102 103 template <class Chunk_t, class FreeList_t> 104 TreeList<Chunk_t, FreeList_t>* 105 TreeList<Chunk_t, FreeList_t>::get_better_list( 106 BinaryTreeDictionary<Chunk_t, FreeList_t>* dictionary) { 107 return this; 108 } 109 110 template <class Chunk_t, class FreeList_t> 111 TreeList<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::remove_chunk_replace_if_needed(TreeChunk<Chunk_t, FreeList_t>* tc) { 112 113 TreeList<Chunk_t, FreeList_t>* retTL = this; 114 Chunk_t* list = head(); 115 assert(!list || list != list->next(), "Chunk on list twice"); 116 assert(tc != NULL, "Chunk being removed is NULL"); 117 assert(parent() == NULL || this == parent()->left() || 118 this == parent()->right(), "list is inconsistent"); 119 assert(tc->is_free(), "Header is not marked correctly"); 120 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 121 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 122 123 Chunk_t* prevFC = tc->prev(); 124 TreeChunk<Chunk_t, FreeList_t>* nextTC = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(tc->next()); 125 assert(list != NULL, "should have at least the target chunk"); 126 127 // Is this the first item on the list? 128 if (tc == list) { 129 // The "getChunk..." functions for a TreeList<Chunk_t, FreeList_t> will not return the 130 // first chunk in the list unless it is the last chunk in the list 131 // because the first chunk is also acting as the tree node. 132 // When coalescing happens, however, the first chunk in the a tree 133 // list can be the start of a free range. Free ranges are removed 134 // from the free lists so that they are not available to be 135 // allocated when the sweeper yields (giving up the free list lock) 136 // to allow mutator activity. If this chunk is the first in the 137 // list and is not the last in the list, do the work to copy the 138 // TreeList<Chunk_t, FreeList_t> from the first chunk to the next chunk and update all 139 // the TreeList<Chunk_t, FreeList_t> pointers in the chunks in the list. 140 if (nextTC == NULL) { 141 assert(prevFC == NULL, "Not last chunk in the list"); 142 set_tail(NULL); 143 set_head(NULL); 144 } else { 145 // copy embedded list. 146 nextTC->set_embedded_list(tc->embedded_list()); 147 retTL = nextTC->embedded_list(); 148 // Fix the pointer to the list in each chunk in the list. 149 // This can be slow for a long list. Consider having 150 // an option that does not allow the first chunk on the 151 // list to be coalesced. 152 for (TreeChunk<Chunk_t, FreeList_t>* curTC = nextTC; curTC != NULL; 153 curTC = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(curTC->next())) { 154 curTC->set_list(retTL); 155 } 156 // Fix the parent to point to the new TreeList<Chunk_t, FreeList_t>. 157 if (retTL->parent() != NULL) { 158 if (this == retTL->parent()->left()) { 159 retTL->parent()->set_left(retTL); 160 } else { 161 assert(this == retTL->parent()->right(), "Parent is incorrect"); 162 retTL->parent()->set_right(retTL); 163 } 164 } 165 // Fix the children's parent pointers to point to the 166 // new list. 167 assert(right() == retTL->right(), "Should have been copied"); 168 if (retTL->right() != NULL) { 169 retTL->right()->set_parent(retTL); 170 } 171 assert(left() == retTL->left(), "Should have been copied"); 172 if (retTL->left() != NULL) { 173 retTL->left()->set_parent(retTL); 174 } 175 retTL->link_head(nextTC); 176 assert(nextTC->is_free(), "Should be a free chunk"); 177 } 178 } else { 179 if (nextTC == NULL) { 180 // Removing chunk at tail of list 181 this->link_tail(prevFC); 182 } 183 // Chunk is interior to the list 184 prevFC->link_after(nextTC); 185 } 186 187 // Below this point the embedded TreeList<Chunk_t, FreeList_t> being used for the 188 // tree node may have changed. Don't use "this" 189 // TreeList<Chunk_t, FreeList_t>*. 190 // chunk should still be a free chunk (bit set in _prev) 191 assert(!retTL->head() || retTL->size() == retTL->head()->size(), 192 "Wrong sized chunk in list"); 193 debug_only( 194 tc->link_prev(NULL); 195 tc->link_next(NULL); 196 tc->set_list(NULL); 197 bool prev_found = false; 198 bool next_found = false; 199 for (Chunk_t* curFC = retTL->head(); 200 curFC != NULL; curFC = curFC->next()) { 201 assert(curFC != tc, "Chunk is still in list"); 202 if (curFC == prevFC) { 203 prev_found = true; 204 } 205 if (curFC == nextTC) { 206 next_found = true; 207 } 208 } 209 assert(prevFC == NULL || prev_found, "Chunk was lost from list"); 210 assert(nextTC == NULL || next_found, "Chunk was lost from list"); 211 assert(retTL->parent() == NULL || 212 retTL == retTL->parent()->left() || 213 retTL == retTL->parent()->right(), 214 "list is inconsistent"); 215 ) 216 retTL->decrement_count(); 217 218 assert(tc->is_free(), "Should still be a free chunk"); 219 assert(retTL->head() == NULL || retTL->head()->prev() == NULL, 220 "list invariant"); 221 assert(retTL->tail() == NULL || retTL->tail()->next() == NULL, 222 "list invariant"); 223 return retTL; 224 } 225 226 template <class Chunk_t, class FreeList_t> 227 void TreeList<Chunk_t, FreeList_t>::return_chunk_at_tail(TreeChunk<Chunk_t, FreeList_t>* chunk) { 228 assert(chunk != NULL, "returning NULL chunk"); 229 assert(chunk->list() == this, "list should be set for chunk"); 230 assert(tail() != NULL, "The tree list is embedded in the first chunk"); 231 // which means that the list can never be empty. 232 if (FLSVerifyDictionary) { 233 // This is expensive for metaspace 234 assert(!this->verify_chunk_in_free_list(chunk), "Double entry"); 235 } 236 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 237 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 238 239 Chunk_t* fc = tail(); 240 fc->link_after(chunk); 241 this->link_tail(chunk); 242 243 assert(!tail() || size() == tail()->size(), "Wrong sized chunk in list"); 244 FreeList_t::increment_count(); 245 debug_only(this->increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));) 246 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 247 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 248 } 249 250 // Add this chunk at the head of the list. "At the head of the list" 251 // is defined to be after the chunk pointer to by head(). This is 252 // because the TreeList<Chunk_t, FreeList_t> is embedded in the first TreeChunk<Chunk_t, FreeList_t> in the 253 // list. See the definition of TreeChunk<Chunk_t, FreeList_t>. 254 template <class Chunk_t, class FreeList_t> 255 void TreeList<Chunk_t, FreeList_t>::return_chunk_at_head(TreeChunk<Chunk_t, FreeList_t>* chunk) { 256 assert(chunk->list() == this, "list should be set for chunk"); 257 assert(head() != NULL, "The tree list is embedded in the first chunk"); 258 assert(chunk != NULL, "returning NULL chunk"); 259 if (FLSVerifyDictionary) { 260 // This is expensive for metaspace 261 assert(!this->verify_chunk_in_free_list(chunk), "Double entry"); 262 } 263 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 264 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 265 266 Chunk_t* fc = head()->next(); 267 if (fc != NULL) { 268 chunk->link_after(fc); 269 } else { 270 assert(tail() == NULL, "List is inconsistent"); 271 this->link_tail(chunk); 272 } 273 head()->link_after(chunk); 274 assert(!head() || size() == head()->size(), "Wrong sized chunk in list"); 275 FreeList_t::increment_count(); 276 debug_only(this->increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));) 277 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 278 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 279 } 280 281 template <class Chunk_t, class FreeList_t> 282 void TreeChunk<Chunk_t, FreeList_t>::assert_is_mangled() const { 283 assert((ZapUnusedHeapArea && 284 SpaceMangler::is_mangled((HeapWord*) Chunk_t::size_addr()) && 285 SpaceMangler::is_mangled((HeapWord*) Chunk_t::prev_addr()) && 286 SpaceMangler::is_mangled((HeapWord*) Chunk_t::next_addr())) || 287 (size() == 0 && prev() == NULL && next() == NULL), 288 "Space should be clear or mangled"); 289 } 290 291 template <class Chunk_t, class FreeList_t> 292 TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::head_as_TreeChunk() { 293 assert(head() == NULL || (TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(head())->list() == this), 294 "Wrong type of chunk?"); 295 return TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(head()); 296 } 297 298 template <class Chunk_t, class FreeList_t> 299 TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::first_available() { 300 assert(head() != NULL, "The head of the list cannot be NULL"); 301 Chunk_t* fc = head()->next(); 302 TreeChunk<Chunk_t, FreeList_t>* retTC; 303 if (fc == NULL) { 304 retTC = head_as_TreeChunk(); 305 } else { 306 retTC = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(fc); 307 } 308 assert(retTC->list() == this, "Wrong type of chunk."); 309 return retTC; 310 } 311 312 // Returns the block with the largest heap address amongst 313 // those in the list for this size; potentially slow and expensive, 314 // use with caution! 315 template <class Chunk_t, class FreeList_t> 316 TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::largest_address() { 317 assert(head() != NULL, "The head of the list cannot be NULL"); 318 Chunk_t* fc = head()->next(); 319 TreeChunk<Chunk_t, FreeList_t>* retTC; 320 if (fc == NULL) { 321 retTC = head_as_TreeChunk(); 322 } else { 323 // walk down the list and return the one with the highest 324 // heap address among chunks of this size. 325 Chunk_t* last = fc; 326 while (fc->next() != NULL) { 327 if ((HeapWord*)last < (HeapWord*)fc) { 328 last = fc; 329 } 330 fc = fc->next(); 331 } 332 retTC = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(last); 333 } 334 assert(retTC->list() == this, "Wrong type of chunk."); 335 return retTC; 336 } 337 338 template <class Chunk_t, class FreeList_t> 339 BinaryTreeDictionary<Chunk_t, FreeList_t>::BinaryTreeDictionary(MemRegion mr) { 340 assert((mr.byte_size() > min_size()), "minimum chunk size"); 341 342 reset(mr); 343 assert(root()->left() == NULL, "reset check failed"); 344 assert(root()->right() == NULL, "reset check failed"); 345 assert(root()->head()->next() == NULL, "reset check failed"); 346 assert(root()->head()->prev() == NULL, "reset check failed"); 347 assert(total_size() == root()->size(), "reset check failed"); 348 assert(total_free_blocks() == 1, "reset check failed"); 349 } 350 351 template <class Chunk_t, class FreeList_t> 352 void BinaryTreeDictionary<Chunk_t, FreeList_t>::inc_total_size(size_t inc) { 353 _total_size = _total_size + inc; 354 } 355 356 template <class Chunk_t, class FreeList_t> 357 void BinaryTreeDictionary<Chunk_t, FreeList_t>::dec_total_size(size_t dec) { 358 _total_size = _total_size - dec; 359 } 360 361 template <class Chunk_t, class FreeList_t> 362 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset(MemRegion mr) { 363 assert((mr.byte_size() > min_size()), "minimum chunk size"); 364 set_root(TreeList<Chunk_t, FreeList_t>::as_TreeList(mr.start(), mr.word_size())); 365 set_total_size(mr.word_size()); 366 set_total_free_blocks(1); 367 } 368 369 template <class Chunk_t, class FreeList_t> 370 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset(HeapWord* addr, size_t byte_size) { 371 MemRegion mr(addr, heap_word_size(byte_size)); 372 reset(mr); 373 } 374 375 template <class Chunk_t, class FreeList_t> 376 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset() { 377 set_root(NULL); 378 set_total_size(0); 379 set_total_free_blocks(0); 380 } 381 382 // Get a free block of size at least size from tree, or NULL. 383 template <class Chunk_t, class FreeList_t> 384 TreeChunk<Chunk_t, FreeList_t>* 385 BinaryTreeDictionary<Chunk_t, FreeList_t>::get_chunk_from_tree(size_t size) 386 { 387 TreeList<Chunk_t, FreeList_t> *curTL, *prevTL; 388 TreeChunk<Chunk_t, FreeList_t>* retTC = NULL; 389 390 assert((size >= min_size()), "minimum chunk size"); 391 if (FLSVerifyDictionary) { 392 verify_tree(); 393 } 394 // starting at the root, work downwards trying to find match. 395 // Remember the last node of size too great or too small. 396 for (prevTL = curTL = root(); curTL != NULL;) { 397 if (curTL->size() == size) { // exact match 398 break; 399 } 400 prevTL = curTL; 401 if (curTL->size() < size) { // proceed to right sub-tree 402 curTL = curTL->right(); 403 } else { // proceed to left sub-tree 404 assert(curTL->size() > size, "size inconsistency"); 405 curTL = curTL->left(); 406 } 407 } 408 if (curTL == NULL) { // couldn't find exact match 409 410 // try and find the next larger size by walking back up the search path 411 for (curTL = prevTL; curTL != NULL;) { 412 if (curTL->size() >= size) break; 413 else curTL = curTL->parent(); 414 } 415 assert(curTL == NULL || curTL->count() > 0, 416 "An empty list should not be in the tree"); 417 } 418 if (curTL != NULL) { 419 assert(curTL->size() >= size, "size inconsistency"); 420 421 curTL = curTL->get_better_list(this); 422 423 retTC = curTL->first_available(); 424 assert((retTC != NULL) && (curTL->count() > 0), 425 "A list in the binary tree should not be NULL"); 426 assert(retTC->size() >= size, 427 "A chunk of the wrong size was found"); 428 remove_chunk_from_tree(retTC); 429 assert(retTC->is_free(), "Header is not marked correctly"); 430 } 431 432 if (FLSVerifyDictionary) { 433 verify(); 434 } 435 return retTC; 436 } 437 438 template <class Chunk_t, class FreeList_t> 439 TreeList<Chunk_t, FreeList_t>* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_list(size_t size) const { 440 TreeList<Chunk_t, FreeList_t>* curTL; 441 for (curTL = root(); curTL != NULL;) { 442 if (curTL->size() == size) { // exact match 443 break; 444 } 445 446 if (curTL->size() < size) { // proceed to right sub-tree 447 curTL = curTL->right(); 448 } else { // proceed to left sub-tree 449 assert(curTL->size() > size, "size inconsistency"); 450 curTL = curTL->left(); 451 } 452 } 453 return curTL; 454 } 455 456 457 template <class Chunk_t, class FreeList_t> 458 bool BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_chunk_in_free_list(Chunk_t* tc) const { 459 size_t size = tc->size(); 460 TreeList<Chunk_t, FreeList_t>* tl = find_list(size); 461 if (tl == NULL) { 462 return false; 463 } else { 464 return tl->verify_chunk_in_free_list(tc); 465 } 466 } 467 468 template <class Chunk_t, class FreeList_t> 469 Chunk_t* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_largest_dict() const { 470 TreeList<Chunk_t, FreeList_t> *curTL = root(); 471 if (curTL != NULL) { 472 while(curTL->right() != NULL) curTL = curTL->right(); 473 return curTL->largest_address(); 474 } else { 475 return NULL; 476 } 477 } 478 479 // Remove the current chunk from the tree. If it is not the last 480 // chunk in a list on a tree node, just unlink it. 481 // If it is the last chunk in the list (the next link is NULL), 482 // remove the node and repair the tree. 483 template <class Chunk_t, class FreeList_t> 484 TreeChunk<Chunk_t, FreeList_t>* 485 BinaryTreeDictionary<Chunk_t, FreeList_t>::remove_chunk_from_tree(TreeChunk<Chunk_t, FreeList_t>* tc) { 486 assert(tc != NULL, "Should not call with a NULL chunk"); 487 assert(tc->is_free(), "Header is not marked correctly"); 488 489 TreeList<Chunk_t, FreeList_t> *newTL, *parentTL; 490 TreeChunk<Chunk_t, FreeList_t>* retTC; 491 TreeList<Chunk_t, FreeList_t>* tl = tc->list(); 492 debug_only( 493 bool removing_only_chunk = false; 494 if (tl == _root) { 495 if ((_root->left() == NULL) && (_root->right() == NULL)) { 496 if (_root->count() == 1) { 497 assert(_root->head() == tc, "Should only be this one chunk"); 498 removing_only_chunk = true; 499 } 500 } 501 } 502 ) 503 assert(tl != NULL, "List should be set"); 504 assert(tl->parent() == NULL || tl == tl->parent()->left() || 505 tl == tl->parent()->right(), "list is inconsistent"); 506 507 bool complicated_splice = false; 508 509 retTC = tc; 510 // Removing this chunk can have the side effect of changing the node 511 // (TreeList<Chunk_t, FreeList_t>*) in the tree. If the node is the root, update it. 512 TreeList<Chunk_t, FreeList_t>* replacementTL = tl->remove_chunk_replace_if_needed(tc); 513 assert(tc->is_free(), "Chunk should still be free"); 514 assert(replacementTL->parent() == NULL || 515 replacementTL == replacementTL->parent()->left() || 516 replacementTL == replacementTL->parent()->right(), 517 "list is inconsistent"); 518 if (tl == root()) { 519 assert(replacementTL->parent() == NULL, "Incorrectly replacing root"); 520 set_root(replacementTL); 521 } 522 #ifdef ASSERT 523 if (tl != replacementTL) { 524 assert(replacementTL->head() != NULL, 525 "If the tree list was replaced, it should not be a NULL list"); 526 TreeList<Chunk_t, FreeList_t>* rhl = replacementTL->head_as_TreeChunk()->list(); 527 TreeList<Chunk_t, FreeList_t>* rtl = 528 TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(replacementTL->tail())->list(); 529 assert(rhl == replacementTL, "Broken head"); 530 assert(rtl == replacementTL, "Broken tail"); 531 assert(replacementTL->size() == tc->size(), "Broken size"); 532 } 533 #endif 534 535 // Does the tree need to be repaired? 536 if (replacementTL->count() == 0) { 537 assert(replacementTL->head() == NULL && 538 replacementTL->tail() == NULL, "list count is incorrect"); 539 // Find the replacement node for the (soon to be empty) node being removed. 540 // if we have a single (or no) child, splice child in our stead 541 if (replacementTL->left() == NULL) { 542 // left is NULL so pick right. right may also be NULL. 543 newTL = replacementTL->right(); 544 debug_only(replacementTL->clear_right();) 545 } else if (replacementTL->right() == NULL) { 546 // right is NULL 547 newTL = replacementTL->left(); 548 debug_only(replacementTL->clear_left();) 549 } else { // we have both children, so, by patriarchal convention, 550 // my replacement is least node in right sub-tree 551 complicated_splice = true; 552 newTL = remove_tree_minimum(replacementTL->right()); 553 assert(newTL != NULL && newTL->left() == NULL && 554 newTL->right() == NULL, "sub-tree minimum exists"); 555 } 556 // newTL is the replacement for the (soon to be empty) node. 557 // newTL may be NULL. 558 // should verify; we just cleanly excised our replacement 559 if (FLSVerifyDictionary) { 560 verify_tree(); 561 } 562 // first make newTL my parent's child 563 if ((parentTL = replacementTL->parent()) == NULL) { 564 // newTL should be root 565 assert(tl == root(), "Incorrectly replacing root"); 566 set_root(newTL); 567 if (newTL != NULL) { 568 newTL->clear_parent(); 569 } 570 } else if (parentTL->right() == replacementTL) { 571 // replacementTL is a right child 572 parentTL->set_right(newTL); 573 } else { // replacementTL is a left child 574 assert(parentTL->left() == replacementTL, "should be left child"); 575 parentTL->set_left(newTL); 576 } 577 debug_only(replacementTL->clear_parent();) 578 if (complicated_splice) { // we need newTL to get replacementTL's 579 // two children 580 assert(newTL != NULL && 581 newTL->left() == NULL && newTL->right() == NULL, 582 "newTL should not have encumbrances from the past"); 583 // we'd like to assert as below: 584 // assert(replacementTL->left() != NULL && replacementTL->right() != NULL, 585 // "else !complicated_splice"); 586 // ... however, the above assertion is too strong because we aren't 587 // guaranteed that replacementTL->right() is still NULL. 588 // Recall that we removed 589 // the right sub-tree minimum from replacementTL. 590 // That may well have been its right 591 // child! So we'll just assert half of the above: 592 assert(replacementTL->left() != NULL, "else !complicated_splice"); 593 newTL->set_left(replacementTL->left()); 594 newTL->set_right(replacementTL->right()); 595 debug_only( 596 replacementTL->clear_right(); 597 replacementTL->clear_left(); 598 ) 599 } 600 assert(replacementTL->right() == NULL && 601 replacementTL->left() == NULL && 602 replacementTL->parent() == NULL, 603 "delete without encumbrances"); 604 } 605 606 assert(total_size() >= retTC->size(), "Incorrect total size"); 607 dec_total_size(retTC->size()); // size book-keeping 608 assert(total_free_blocks() > 0, "Incorrect total count"); 609 set_total_free_blocks(total_free_blocks() - 1); 610 611 assert(retTC != NULL, "null chunk?"); 612 assert(retTC->prev() == NULL && retTC->next() == NULL, 613 "should return without encumbrances"); 614 if (FLSVerifyDictionary) { 615 verify_tree(); 616 } 617 assert(!removing_only_chunk || _root == NULL, "root should be NULL"); 618 return TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(retTC); 619 } 620 621 // Remove the leftmost node (lm) in the tree and return it. 622 // If lm has a right child, link it to the left node of 623 // the parent of lm. 624 template <class Chunk_t, class FreeList_t> 625 TreeList<Chunk_t, FreeList_t>* BinaryTreeDictionary<Chunk_t, FreeList_t>::remove_tree_minimum(TreeList<Chunk_t, FreeList_t>* tl) { 626 assert(tl != NULL && tl->parent() != NULL, "really need a proper sub-tree"); 627 // locate the subtree minimum by walking down left branches 628 TreeList<Chunk_t, FreeList_t>* curTL = tl; 629 for (; curTL->left() != NULL; curTL = curTL->left()); 630 // obviously curTL now has at most one child, a right child 631 if (curTL != root()) { // Should this test just be removed? 632 TreeList<Chunk_t, FreeList_t>* parentTL = curTL->parent(); 633 if (parentTL->left() == curTL) { // curTL is a left child 634 parentTL->set_left(curTL->right()); 635 } else { 636 // If the list tl has no left child, then curTL may be 637 // the right child of parentTL. 638 assert(parentTL->right() == curTL, "should be a right child"); 639 parentTL->set_right(curTL->right()); 640 } 641 } else { 642 // The only use of this method would not pass the root of the 643 // tree (as indicated by the assertion above that the tree list 644 // has a parent) but the specification does not explicitly exclude the 645 // passing of the root so accommodate it. 646 set_root(NULL); 647 } 648 debug_only( 649 curTL->clear_parent(); // Test if this needs to be cleared 650 curTL->clear_right(); // recall, above, left child is already null 651 ) 652 // we just excised a (non-root) node, we should still verify all tree invariants 653 if (FLSVerifyDictionary) { 654 verify_tree(); 655 } 656 return curTL; 657 } 658 659 template <class Chunk_t, class FreeList_t> 660 void BinaryTreeDictionary<Chunk_t, FreeList_t>::insert_chunk_in_tree(Chunk_t* fc) { 661 TreeList<Chunk_t, FreeList_t> *curTL, *prevTL; 662 size_t size = fc->size(); 663 664 assert((size >= min_size()), 665 SIZE_FORMAT " is too small to be a TreeChunk<Chunk_t, FreeList_t> " SIZE_FORMAT, 666 size, min_size()); 667 if (FLSVerifyDictionary) { 668 verify_tree(); 669 } 670 671 fc->clear_next(); 672 fc->link_prev(NULL); 673 674 // work down from the _root, looking for insertion point 675 for (prevTL = curTL = root(); curTL != NULL;) { 676 if (curTL->size() == size) // exact match 677 break; 678 prevTL = curTL; 679 if (curTL->size() > size) { // follow left branch 680 curTL = curTL->left(); 681 } else { // follow right branch 682 assert(curTL->size() < size, "size inconsistency"); 683 curTL = curTL->right(); 684 } 685 } 686 TreeChunk<Chunk_t, FreeList_t>* tc = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(fc); 687 // This chunk is being returned to the binary tree. Its embedded 688 // TreeList<Chunk_t, FreeList_t> should be unused at this point. 689 tc->initialize(); 690 if (curTL != NULL) { // exact match 691 tc->set_list(curTL); 692 curTL->return_chunk_at_tail(tc); 693 } else { // need a new node in tree 694 tc->clear_next(); 695 tc->link_prev(NULL); 696 TreeList<Chunk_t, FreeList_t>* newTL = TreeList<Chunk_t, FreeList_t>::as_TreeList(tc); 697 assert(((TreeChunk<Chunk_t, FreeList_t>*)tc)->list() == newTL, 698 "List was not initialized correctly"); 699 if (prevTL == NULL) { // we are the only tree node 700 assert(root() == NULL, "control point invariant"); 701 set_root(newTL); 702 } else { // insert under prevTL ... 703 if (prevTL->size() < size) { // am right child 704 assert(prevTL->right() == NULL, "control point invariant"); 705 prevTL->set_right(newTL); 706 } else { // am left child 707 assert(prevTL->size() > size && prevTL->left() == NULL, "cpt pt inv"); 708 prevTL->set_left(newTL); 709 } 710 } 711 } 712 assert(tc->list() != NULL, "Tree list should be set"); 713 714 inc_total_size(size); 715 // Method 'total_size_in_tree' walks through the every block in the 716 // tree, so it can cause significant performance loss if there are 717 // many blocks in the tree 718 assert(!FLSVerifyDictionary || total_size_in_tree(root()) == total_size(), "_total_size inconsistency"); 719 set_total_free_blocks(total_free_blocks() + 1); 720 if (FLSVerifyDictionary) { 721 verify_tree(); 722 } 723 } 724 725 template <class Chunk_t, class FreeList_t> 726 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::max_chunk_size() const { 727 verify_par_locked(); 728 TreeList<Chunk_t, FreeList_t>* tc = root(); 729 if (tc == NULL) return 0; 730 for (; tc->right() != NULL; tc = tc->right()); 731 return tc->size(); 732 } 733 734 template <class Chunk_t, class FreeList_t> 735 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_list_length(TreeList<Chunk_t, FreeList_t>* tl) const { 736 size_t res; 737 res = tl->count(); 738 #ifdef ASSERT 739 size_t cnt; 740 Chunk_t* tc = tl->head(); 741 for (cnt = 0; tc != NULL; tc = tc->next(), cnt++); 742 assert(res == cnt, "The count is not being maintained correctly"); 743 #endif 744 return res; 745 } 746 747 template <class Chunk_t, class FreeList_t> 748 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_size_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const { 749 if (tl == NULL) 750 return 0; 751 return (tl->size() * total_list_length(tl)) + 752 total_size_in_tree(tl->left()) + 753 total_size_in_tree(tl->right()); 754 } 755 756 template <class Chunk_t, class FreeList_t> 757 double BinaryTreeDictionary<Chunk_t, FreeList_t>::sum_of_squared_block_sizes(TreeList<Chunk_t, FreeList_t>* const tl) const { 758 if (tl == NULL) { 759 return 0.0; 760 } 761 double size = (double)(tl->size()); 762 double curr = size * size * total_list_length(tl); 763 curr += sum_of_squared_block_sizes(tl->left()); 764 curr += sum_of_squared_block_sizes(tl->right()); 765 return curr; 766 } 767 768 template <class Chunk_t, class FreeList_t> 769 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_free_blocks_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const { 770 if (tl == NULL) 771 return 0; 772 return total_list_length(tl) + 773 total_free_blocks_in_tree(tl->left()) + 774 total_free_blocks_in_tree(tl->right()); 775 } 776 777 template <class Chunk_t, class FreeList_t> 778 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::num_free_blocks() const { 779 assert(total_free_blocks_in_tree(root()) == total_free_blocks(), 780 "_total_free_blocks inconsistency"); 781 return total_free_blocks(); 782 } 783 784 template <class Chunk_t, class FreeList_t> 785 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::tree_height_helper(TreeList<Chunk_t, FreeList_t>* tl) const { 786 if (tl == NULL) 787 return 0; 788 return 1 + MAX2(tree_height_helper(tl->left()), 789 tree_height_helper(tl->right())); 790 } 791 792 template <class Chunk_t, class FreeList_t> 793 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::tree_height() const { 794 return tree_height_helper(root()); 795 } 796 797 template <class Chunk_t, class FreeList_t> 798 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_nodes_helper(TreeList<Chunk_t, FreeList_t>* tl) const { 799 if (tl == NULL) { 800 return 0; 801 } 802 return 1 + total_nodes_helper(tl->left()) + 803 total_nodes_helper(tl->right()); 804 } 805 806 template <class Chunk_t, class FreeList_t> 807 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_nodes_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const { 808 return total_nodes_helper(root()); 809 } 810 811 // Searches the tree for a chunk that ends at the 812 // specified address. 813 template <class Chunk_t, class FreeList_t> 814 class EndTreeSearchClosure : public DescendTreeSearchClosure<Chunk_t, FreeList_t> { 815 HeapWord* _target; 816 Chunk_t* _found; 817 818 public: 819 EndTreeSearchClosure(HeapWord* target) : _target(target), _found(NULL) {} 820 bool do_list(FreeList_t* fl) { 821 Chunk_t* item = fl->head(); 822 while (item != NULL) { 823 if (item->end() == (uintptr_t*) _target) { 824 _found = item; 825 return true; 826 } 827 item = item->next(); 828 } 829 return false; 830 } 831 Chunk_t* found() { return _found; } 832 }; 833 834 template <class Chunk_t, class FreeList_t> 835 Chunk_t* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_chunk_ends_at(HeapWord* target) const { 836 EndTreeSearchClosure<Chunk_t, FreeList_t> etsc(target); 837 bool found_target = etsc.do_tree(root()); 838 assert(found_target || etsc.found() == NULL, "Consistency check"); 839 assert(!found_target || etsc.found() != NULL, "Consistency check"); 840 return etsc.found(); 841 } 842 843 // Closures and methods for calculating total bytes returned to the 844 // free lists in the tree. 845 #ifndef PRODUCT 846 template <class Chunk_t, class FreeList_t> 847 class InitializeDictReturnedBytesClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { 848 public: 849 void do_list(FreeList_t* fl) { 850 fl->set_returned_bytes(0); 851 } 852 }; 853 854 template <class Chunk_t, class FreeList_t> 855 void BinaryTreeDictionary<Chunk_t, FreeList_t>::initialize_dict_returned_bytes() { 856 InitializeDictReturnedBytesClosure<Chunk_t, FreeList_t> idrb; 857 idrb.do_tree(root()); 858 } 859 860 template <class Chunk_t, class FreeList_t> 861 class ReturnedBytesClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { 862 size_t _dict_returned_bytes; 863 public: 864 ReturnedBytesClosure() { _dict_returned_bytes = 0; } 865 void do_list(FreeList_t* fl) { 866 _dict_returned_bytes += fl->returned_bytes(); 867 } 868 size_t dict_returned_bytes() { return _dict_returned_bytes; } 869 }; 870 871 template <class Chunk_t, class FreeList_t> 872 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::sum_dict_returned_bytes() { 873 ReturnedBytesClosure<Chunk_t, FreeList_t> rbc; 874 rbc.do_tree(root()); 875 876 return rbc.dict_returned_bytes(); 877 } 878 879 // Count the number of entries in the tree. 880 template <class Chunk_t, class FreeList_t> 881 class treeCountClosure : public DescendTreeCensusClosure<Chunk_t, FreeList_t> { 882 public: 883 uint count; 884 treeCountClosure(uint c) { count = c; } 885 void do_list(FreeList_t* fl) { 886 count++; 887 } 888 }; 889 890 template <class Chunk_t, class FreeList_t> 891 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_count() { 892 treeCountClosure<Chunk_t, FreeList_t> ctc(0); 893 ctc.do_tree(root()); 894 return ctc.count; 895 } 896 897 template <class Chunk_t, class FreeList_t> 898 Mutex* BinaryTreeDictionary<Chunk_t, FreeList_t>::par_lock() const { 899 return _lock; 900 } 901 902 template <class Chunk_t, class FreeList_t> 903 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_par_lock(Mutex* lock) { 904 _lock = lock; 905 } 906 907 template <class Chunk_t, class FreeList_t> 908 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_par_locked() const { 909 #ifdef ASSERT 910 Thread* my_thread = Thread::current(); 911 if (my_thread->is_GC_task_thread()) { 912 assert(par_lock() != NULL, "Should be using locking?"); 913 assert_lock_strong(par_lock()); 914 } 915 #endif // ASSERT 916 } 917 #endif // PRODUCT 918 919 // Print summary statistics 920 template <class Chunk_t, class FreeList_t> 921 void BinaryTreeDictionary<Chunk_t, FreeList_t>::report_statistics(outputStream* st) const { 922 verify_par_locked(); 923 st->print_cr("Statistics for BinaryTreeDictionary:"); 924 st->print_cr("------------------------------------"); 925 size_t total_size = total_chunk_size(debug_only(NULL)); 926 size_t free_blocks = num_free_blocks(); 927 st->print_cr("Total Free Space: " SIZE_FORMAT, total_size); 928 st->print_cr("Max Chunk Size: " SIZE_FORMAT, max_chunk_size()); 929 st->print_cr("Number of Blocks: " SIZE_FORMAT, free_blocks); 930 if (free_blocks > 0) { 931 st->print_cr("Av. Block Size: " SIZE_FORMAT, total_size/free_blocks); 932 } 933 st->print_cr("Tree Height: " SIZE_FORMAT, tree_height()); 934 } 935 936 template <class Chunk_t, class FreeList_t> 937 class PrintFreeListsClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { 938 outputStream* _st; 939 int _print_line; 940 941 public: 942 PrintFreeListsClosure(outputStream* st) { 943 _st = st; 944 _print_line = 0; 945 } 946 void do_list(FreeList_t* fl) { 947 if (++_print_line >= 40) { 948 FreeList_t::print_labels_on(_st, "size"); 949 _print_line = 0; 950 } 951 fl->print_on(_st); 952 size_t sz = fl->size(); 953 for (Chunk_t* fc = fl->head(); fc != NULL; 954 fc = fc->next()) { 955 _st->print_cr("\t[" PTR_FORMAT "," PTR_FORMAT ") %s", 956 p2i(fc), p2i((HeapWord*)fc + sz), 957 fc->cantCoalesce() ? "\t CC" : ""); 958 } 959 } 960 }; 961 962 template <class Chunk_t, class FreeList_t> 963 void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_free_lists(outputStream* st) const { 964 965 FreeList_t::print_labels_on(st, "size"); 966 PrintFreeListsClosure<Chunk_t, FreeList_t> pflc(st); 967 pflc.do_tree(root()); 968 } 969 970 // Verify the following tree invariants: 971 // . _root has no parent 972 // . parent and child point to each other 973 // . each node's key correctly related to that of its child(ren) 974 template <class Chunk_t, class FreeList_t> 975 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_tree() const { 976 guarantee(root() == NULL || total_free_blocks() == 0 || 977 total_size() != 0, "_total_size shouldn't be 0?"); 978 guarantee(root() == NULL || root()->parent() == NULL, "_root shouldn't have parent"); 979 verify_tree_helper(root()); 980 } 981 982 template <class Chunk_t, class FreeList_t> 983 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_prev_free_ptrs(TreeList<Chunk_t, FreeList_t>* tl) { 984 size_t ct = 0; 985 for (Chunk_t* curFC = tl->head(); curFC != NULL; curFC = curFC->next()) { 986 ct++; 987 assert(curFC->prev() == NULL || curFC->prev()->is_free(), 988 "Chunk should be free"); 989 } 990 return ct; 991 } 992 993 // Note: this helper is recursive rather than iterative, so use with 994 // caution on very deep trees; and watch out for stack overflow errors; 995 // In general, to be used only for debugging. 996 template <class Chunk_t, class FreeList_t> 997 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_tree_helper(TreeList<Chunk_t, FreeList_t>* tl) const { 998 if (tl == NULL) 999 return; 1000 guarantee(tl->size() != 0, "A list must has a size"); 1001 guarantee(tl->left() == NULL || tl->left()->parent() == tl, 1002 "parent<-/->left"); 1003 guarantee(tl->right() == NULL || tl->right()->parent() == tl, 1004 "parent<-/->right");; 1005 guarantee(tl->left() == NULL || tl->left()->size() < tl->size(), 1006 "parent !> left"); 1007 guarantee(tl->right() == NULL || tl->right()->size() > tl->size(), 1008 "parent !< left"); 1009 guarantee(tl->head() == NULL || tl->head()->is_free(), "!Free"); 1010 guarantee(tl->head() == NULL || tl->head_as_TreeChunk()->list() == tl, 1011 "list inconsistency"); 1012 guarantee(tl->count() > 0 || (tl->head() == NULL && tl->tail() == NULL), 1013 "list count is inconsistent"); 1014 guarantee(tl->count() > 1 || tl->head() == tl->tail(), 1015 "list is incorrectly constructed"); 1016 size_t count = verify_prev_free_ptrs(tl); 1017 guarantee(count == (size_t)tl->count(), "Node count is incorrect"); 1018 if (tl->head() != NULL) { 1019 tl->head_as_TreeChunk()->verify_tree_chunk_list(); 1020 } 1021 verify_tree_helper(tl->left()); 1022 verify_tree_helper(tl->right()); 1023 } 1024 1025 template <class Chunk_t, class FreeList_t> 1026 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify() const { 1027 verify_tree(); 1028 guarantee(total_size() == total_size_in_tree(root()), "Total Size inconsistency"); 1029 } 1030 1031 template <class Chunk_t, class FreeList_t> 1032 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_chunk_size(debug_only(const Mutex* lock)) const { 1033 debug_only( 1034 if (lock != NULL && lock->owned_by_self()) { 1035 assert(total_size_in_tree(root()) == total_size(), 1036 "_total_size inconsistency"); 1037 } 1038 ) 1039 return total_size(); 1040 } 1041 1042 #endif // SHARE_VM_MEMORY_BINARYTREEDICTIONARY_INLINE_HPP