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 assert(!this->verify_chunk_in_free_list(chunk), "Double entry"); 233 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 234 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 235 236 Chunk_t* fc = tail(); 237 fc->link_after(chunk); 238 this->link_tail(chunk); 239 240 assert(!tail() || size() == tail()->size(), "Wrong sized chunk in list"); 241 FreeList_t::increment_count(); 242 debug_only(this->increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));) 243 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 244 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 245 } 246 247 // Add this chunk at the head of the list. "At the head of the list" 248 // is defined to be after the chunk pointer to by head(). This is 249 // because the TreeList<Chunk_t, FreeList_t> is embedded in the first TreeChunk<Chunk_t, FreeList_t> in the 250 // list. See the definition of TreeChunk<Chunk_t, FreeList_t>. 251 template <class Chunk_t, class FreeList_t> 252 void TreeList<Chunk_t, FreeList_t>::return_chunk_at_head(TreeChunk<Chunk_t, FreeList_t>* chunk) { 253 assert(chunk->list() == this, "list should be set for chunk"); 254 assert(head() != NULL, "The tree list is embedded in the first chunk"); 255 assert(chunk != NULL, "returning NULL chunk"); 256 assert(!this->verify_chunk_in_free_list(chunk), "Double entry"); 257 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 258 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 259 260 Chunk_t* fc = head()->next(); 261 if (fc != NULL) { 262 chunk->link_after(fc); 263 } else { 264 assert(tail() == NULL, "List is inconsistent"); 265 this->link_tail(chunk); 266 } 267 head()->link_after(chunk); 268 assert(!head() || size() == head()->size(), "Wrong sized chunk in list"); 269 FreeList_t::increment_count(); 270 debug_only(this->increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));) 271 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 272 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 273 } 274 275 template <class Chunk_t, class FreeList_t> 276 void TreeChunk<Chunk_t, FreeList_t>::assert_is_mangled() const { 277 assert((ZapUnusedHeapArea && 278 SpaceMangler::is_mangled((HeapWord*) Chunk_t::size_addr()) && 279 SpaceMangler::is_mangled((HeapWord*) Chunk_t::prev_addr()) && 280 SpaceMangler::is_mangled((HeapWord*) Chunk_t::next_addr())) || 281 (size() == 0 && prev() == NULL && next() == NULL), 282 "Space should be clear or mangled"); 283 } 284 285 template <class Chunk_t, class FreeList_t> 286 TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::head_as_TreeChunk() { 287 assert(head() == NULL || (TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(head())->list() == this), 288 "Wrong type of chunk?"); 289 return TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(head()); 290 } 291 292 template <class Chunk_t, class FreeList_t> 293 TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::first_available() { 294 assert(head() != NULL, "The head of the list cannot be NULL"); 295 Chunk_t* fc = head()->next(); 296 TreeChunk<Chunk_t, FreeList_t>* retTC; 297 if (fc == NULL) { 298 retTC = head_as_TreeChunk(); 299 } else { 300 retTC = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(fc); 301 } 302 assert(retTC->list() == this, "Wrong type of chunk."); 303 return retTC; 304 } 305 306 // Returns the block with the largest heap address amongst 307 // those in the list for this size; potentially slow and expensive, 308 // use with caution! 309 template <class Chunk_t, class FreeList_t> 310 TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::largest_address() { 311 assert(head() != NULL, "The head of the list cannot be NULL"); 312 Chunk_t* fc = head()->next(); 313 TreeChunk<Chunk_t, FreeList_t>* retTC; 314 if (fc == NULL) { 315 retTC = head_as_TreeChunk(); 316 } else { 317 // walk down the list and return the one with the highest 318 // heap address among chunks of this size. 319 Chunk_t* last = fc; 320 while (fc->next() != NULL) { 321 if ((HeapWord*)last < (HeapWord*)fc) { 322 last = fc; 323 } 324 fc = fc->next(); 325 } 326 retTC = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(last); 327 } 328 assert(retTC->list() == this, "Wrong type of chunk."); 329 return retTC; 330 } 331 332 template <class Chunk_t, class FreeList_t> 333 BinaryTreeDictionary<Chunk_t, FreeList_t>::BinaryTreeDictionary(MemRegion mr) { 334 assert((mr.byte_size() > min_size()), "minimum chunk size"); 335 336 reset(mr); 337 assert(root()->left() == NULL, "reset check failed"); 338 assert(root()->right() == NULL, "reset check failed"); 339 assert(root()->head()->next() == NULL, "reset check failed"); 340 assert(root()->head()->prev() == NULL, "reset check failed"); 341 assert(total_size() == root()->size(), "reset check failed"); 342 assert(total_free_blocks() == 1, "reset check failed"); 343 } 344 345 template <class Chunk_t, class FreeList_t> 346 void BinaryTreeDictionary<Chunk_t, FreeList_t>::inc_total_size(size_t inc) { 347 _total_size = _total_size + inc; 348 } 349 350 template <class Chunk_t, class FreeList_t> 351 void BinaryTreeDictionary<Chunk_t, FreeList_t>::dec_total_size(size_t dec) { 352 _total_size = _total_size - dec; 353 } 354 355 template <class Chunk_t, class FreeList_t> 356 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset(MemRegion mr) { 357 assert((mr.byte_size() > min_size()), "minimum chunk size"); 358 set_root(TreeList<Chunk_t, FreeList_t>::as_TreeList(mr.start(), mr.word_size())); 359 set_total_size(mr.word_size()); 360 set_total_free_blocks(1); 361 } 362 363 template <class Chunk_t, class FreeList_t> 364 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset(HeapWord* addr, size_t byte_size) { 365 MemRegion mr(addr, heap_word_size(byte_size)); 366 reset(mr); 367 } 368 369 template <class Chunk_t, class FreeList_t> 370 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset() { 371 set_root(NULL); 372 set_total_size(0); 373 set_total_free_blocks(0); 374 } 375 376 // Get a free block of size at least size from tree, or NULL. 377 template <class Chunk_t, class FreeList_t> 378 TreeChunk<Chunk_t, FreeList_t>* 379 BinaryTreeDictionary<Chunk_t, FreeList_t>::get_chunk_from_tree(size_t size) 380 { 381 TreeList<Chunk_t, FreeList_t> *curTL, *prevTL; 382 TreeChunk<Chunk_t, FreeList_t>* retTC = NULL; 383 384 assert((size >= min_size()), "minimum chunk size"); 385 if (FLSVerifyDictionary) { 386 verify_tree(); 387 } 388 // starting at the root, work downwards trying to find match. 389 // Remember the last node of size too great or too small. 390 for (prevTL = curTL = root(); curTL != NULL;) { 391 if (curTL->size() == size) { // exact match 392 break; 393 } 394 prevTL = curTL; 395 if (curTL->size() < size) { // proceed to right sub-tree 396 curTL = curTL->right(); 397 } else { // proceed to left sub-tree 398 assert(curTL->size() > size, "size inconsistency"); 399 curTL = curTL->left(); 400 } 401 } 402 if (curTL == NULL) { // couldn't find exact match 403 404 // try and find the next larger size by walking back up the search path 405 for (curTL = prevTL; curTL != NULL;) { 406 if (curTL->size() >= size) break; 407 else curTL = curTL->parent(); 408 } 409 assert(curTL == NULL || curTL->count() > 0, 410 "An empty list should not be in the tree"); 411 } 412 if (curTL != NULL) { 413 assert(curTL->size() >= size, "size inconsistency"); 414 415 curTL = curTL->get_better_list(this); 416 417 retTC = curTL->first_available(); 418 assert((retTC != NULL) && (curTL->count() > 0), 419 "A list in the binary tree should not be NULL"); 420 assert(retTC->size() >= size, 421 "A chunk of the wrong size was found"); 422 remove_chunk_from_tree(retTC); 423 assert(retTC->is_free(), "Header is not marked correctly"); 424 } 425 426 if (FLSVerifyDictionary) { 427 verify(); 428 } 429 return retTC; 430 } 431 432 template <class Chunk_t, class FreeList_t> 433 TreeList<Chunk_t, FreeList_t>* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_list(size_t size) const { 434 TreeList<Chunk_t, FreeList_t>* curTL; 435 for (curTL = root(); curTL != NULL;) { 436 if (curTL->size() == size) { // exact match 437 break; 438 } 439 440 if (curTL->size() < size) { // proceed to right sub-tree 441 curTL = curTL->right(); 442 } else { // proceed to left sub-tree 443 assert(curTL->size() > size, "size inconsistency"); 444 curTL = curTL->left(); 445 } 446 } 447 return curTL; 448 } 449 450 451 template <class Chunk_t, class FreeList_t> 452 bool BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_chunk_in_free_list(Chunk_t* tc) const { 453 size_t size = tc->size(); 454 TreeList<Chunk_t, FreeList_t>* tl = find_list(size); 455 if (tl == NULL) { 456 return false; 457 } else { 458 return tl->verify_chunk_in_free_list(tc); 459 } 460 } 461 462 template <class Chunk_t, class FreeList_t> 463 Chunk_t* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_largest_dict() const { 464 TreeList<Chunk_t, FreeList_t> *curTL = root(); 465 if (curTL != NULL) { 466 while(curTL->right() != NULL) curTL = curTL->right(); 467 return curTL->largest_address(); 468 } else { 469 return NULL; 470 } 471 } 472 473 // Remove the current chunk from the tree. If it is not the last 474 // chunk in a list on a tree node, just unlink it. 475 // If it is the last chunk in the list (the next link is NULL), 476 // remove the node and repair the tree. 477 template <class Chunk_t, class FreeList_t> 478 TreeChunk<Chunk_t, FreeList_t>* 479 BinaryTreeDictionary<Chunk_t, FreeList_t>::remove_chunk_from_tree(TreeChunk<Chunk_t, FreeList_t>* tc) { 480 assert(tc != NULL, "Should not call with a NULL chunk"); 481 assert(tc->is_free(), "Header is not marked correctly"); 482 483 TreeList<Chunk_t, FreeList_t> *newTL, *parentTL; 484 TreeChunk<Chunk_t, FreeList_t>* retTC; 485 TreeList<Chunk_t, FreeList_t>* tl = tc->list(); 486 debug_only( 487 bool removing_only_chunk = false; 488 if (tl == _root) { 489 if ((_root->left() == NULL) && (_root->right() == NULL)) { 490 if (_root->count() == 1) { 491 assert(_root->head() == tc, "Should only be this one chunk"); 492 removing_only_chunk = true; 493 } 494 } 495 } 496 ) 497 assert(tl != NULL, "List should be set"); 498 assert(tl->parent() == NULL || tl == tl->parent()->left() || 499 tl == tl->parent()->right(), "list is inconsistent"); 500 501 bool complicated_splice = false; 502 503 retTC = tc; 504 // Removing this chunk can have the side effect of changing the node 505 // (TreeList<Chunk_t, FreeList_t>*) in the tree. If the node is the root, update it. 506 TreeList<Chunk_t, FreeList_t>* replacementTL = tl->remove_chunk_replace_if_needed(tc); 507 assert(tc->is_free(), "Chunk should still be free"); 508 assert(replacementTL->parent() == NULL || 509 replacementTL == replacementTL->parent()->left() || 510 replacementTL == replacementTL->parent()->right(), 511 "list is inconsistent"); 512 if (tl == root()) { 513 assert(replacementTL->parent() == NULL, "Incorrectly replacing root"); 514 set_root(replacementTL); 515 } 516 #ifdef ASSERT 517 if (tl != replacementTL) { 518 assert(replacementTL->head() != NULL, 519 "If the tree list was replaced, it should not be a NULL list"); 520 TreeList<Chunk_t, FreeList_t>* rhl = replacementTL->head_as_TreeChunk()->list(); 521 TreeList<Chunk_t, FreeList_t>* rtl = 522 TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(replacementTL->tail())->list(); 523 assert(rhl == replacementTL, "Broken head"); 524 assert(rtl == replacementTL, "Broken tail"); 525 assert(replacementTL->size() == tc->size(), "Broken size"); 526 } 527 #endif 528 529 // Does the tree need to be repaired? 530 if (replacementTL->count() == 0) { 531 assert(replacementTL->head() == NULL && 532 replacementTL->tail() == NULL, "list count is incorrect"); 533 // Find the replacement node for the (soon to be empty) node being removed. 534 // if we have a single (or no) child, splice child in our stead 535 if (replacementTL->left() == NULL) { 536 // left is NULL so pick right. right may also be NULL. 537 newTL = replacementTL->right(); 538 debug_only(replacementTL->clear_right();) 539 } else if (replacementTL->right() == NULL) { 540 // right is NULL 541 newTL = replacementTL->left(); 542 debug_only(replacementTL->clear_left();) 543 } else { // we have both children, so, by patriarchal convention, 544 // my replacement is least node in right sub-tree 545 complicated_splice = true; 546 newTL = remove_tree_minimum(replacementTL->right()); 547 assert(newTL != NULL && newTL->left() == NULL && 548 newTL->right() == NULL, "sub-tree minimum exists"); 549 } 550 // newTL is the replacement for the (soon to be empty) node. 551 // newTL may be NULL. 552 // should verify; we just cleanly excised our replacement 553 if (FLSVerifyDictionary) { 554 verify_tree(); 555 } 556 // first make newTL my parent's child 557 if ((parentTL = replacementTL->parent()) == NULL) { 558 // newTL should be root 559 assert(tl == root(), "Incorrectly replacing root"); 560 set_root(newTL); 561 if (newTL != NULL) { 562 newTL->clear_parent(); 563 } 564 } else if (parentTL->right() == replacementTL) { 565 // replacementTL is a right child 566 parentTL->set_right(newTL); 567 } else { // replacementTL is a left child 568 assert(parentTL->left() == replacementTL, "should be left child"); 569 parentTL->set_left(newTL); 570 } 571 debug_only(replacementTL->clear_parent();) 572 if (complicated_splice) { // we need newTL to get replacementTL's 573 // two children 574 assert(newTL != NULL && 575 newTL->left() == NULL && newTL->right() == NULL, 576 "newTL should not have encumbrances from the past"); 577 // we'd like to assert as below: 578 // assert(replacementTL->left() != NULL && replacementTL->right() != NULL, 579 // "else !complicated_splice"); 580 // ... however, the above assertion is too strong because we aren't 581 // guaranteed that replacementTL->right() is still NULL. 582 // Recall that we removed 583 // the right sub-tree minimum from replacementTL. 584 // That may well have been its right 585 // child! So we'll just assert half of the above: 586 assert(replacementTL->left() != NULL, "else !complicated_splice"); 587 newTL->set_left(replacementTL->left()); 588 newTL->set_right(replacementTL->right()); 589 debug_only( 590 replacementTL->clear_right(); 591 replacementTL->clear_left(); 592 ) 593 } 594 assert(replacementTL->right() == NULL && 595 replacementTL->left() == NULL && 596 replacementTL->parent() == NULL, 597 "delete without encumbrances"); 598 } 599 600 assert(total_size() >= retTC->size(), "Incorrect total size"); 601 dec_total_size(retTC->size()); // size book-keeping 602 assert(total_free_blocks() > 0, "Incorrect total count"); 603 set_total_free_blocks(total_free_blocks() - 1); 604 605 assert(retTC != NULL, "null chunk?"); 606 assert(retTC->prev() == NULL && retTC->next() == NULL, 607 "should return without encumbrances"); 608 if (FLSVerifyDictionary) { 609 verify_tree(); 610 } 611 assert(!removing_only_chunk || _root == NULL, "root should be NULL"); 612 return TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(retTC); 613 } 614 615 // Remove the leftmost node (lm) in the tree and return it. 616 // If lm has a right child, link it to the left node of 617 // the parent of lm. 618 template <class Chunk_t, class FreeList_t> 619 TreeList<Chunk_t, FreeList_t>* BinaryTreeDictionary<Chunk_t, FreeList_t>::remove_tree_minimum(TreeList<Chunk_t, FreeList_t>* tl) { 620 assert(tl != NULL && tl->parent() != NULL, "really need a proper sub-tree"); 621 // locate the subtree minimum by walking down left branches 622 TreeList<Chunk_t, FreeList_t>* curTL = tl; 623 for (; curTL->left() != NULL; curTL = curTL->left()); 624 // obviously curTL now has at most one child, a right child 625 if (curTL != root()) { // Should this test just be removed? 626 TreeList<Chunk_t, FreeList_t>* parentTL = curTL->parent(); 627 if (parentTL->left() == curTL) { // curTL is a left child 628 parentTL->set_left(curTL->right()); 629 } else { 630 // If the list tl has no left child, then curTL may be 631 // the right child of parentTL. 632 assert(parentTL->right() == curTL, "should be a right child"); 633 parentTL->set_right(curTL->right()); 634 } 635 } else { 636 // The only use of this method would not pass the root of the 637 // tree (as indicated by the assertion above that the tree list 638 // has a parent) but the specification does not explicitly exclude the 639 // passing of the root so accommodate it. 640 set_root(NULL); 641 } 642 debug_only( 643 curTL->clear_parent(); // Test if this needs to be cleared 644 curTL->clear_right(); // recall, above, left child is already null 645 ) 646 // we just excised a (non-root) node, we should still verify all tree invariants 647 if (FLSVerifyDictionary) { 648 verify_tree(); 649 } 650 return curTL; 651 } 652 653 template <class Chunk_t, class FreeList_t> 654 void BinaryTreeDictionary<Chunk_t, FreeList_t>::insert_chunk_in_tree(Chunk_t* fc) { 655 TreeList<Chunk_t, FreeList_t> *curTL, *prevTL; 656 size_t size = fc->size(); 657 658 assert((size >= min_size()), 659 SIZE_FORMAT " is too small to be a TreeChunk<Chunk_t, FreeList_t> " SIZE_FORMAT, 660 size, min_size()); 661 if (FLSVerifyDictionary) { 662 verify_tree(); 663 } 664 665 fc->clear_next(); 666 fc->link_prev(NULL); 667 668 // work down from the _root, looking for insertion point 669 for (prevTL = curTL = root(); curTL != NULL;) { 670 if (curTL->size() == size) // exact match 671 break; 672 prevTL = curTL; 673 if (curTL->size() > size) { // follow left branch 674 curTL = curTL->left(); 675 } else { // follow right branch 676 assert(curTL->size() < size, "size inconsistency"); 677 curTL = curTL->right(); 678 } 679 } 680 TreeChunk<Chunk_t, FreeList_t>* tc = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(fc); 681 // This chunk is being returned to the binary tree. Its embedded 682 // TreeList<Chunk_t, FreeList_t> should be unused at this point. 683 tc->initialize(); 684 if (curTL != NULL) { // exact match 685 tc->set_list(curTL); 686 curTL->return_chunk_at_tail(tc); 687 } else { // need a new node in tree 688 tc->clear_next(); 689 tc->link_prev(NULL); 690 TreeList<Chunk_t, FreeList_t>* newTL = TreeList<Chunk_t, FreeList_t>::as_TreeList(tc); 691 assert(((TreeChunk<Chunk_t, FreeList_t>*)tc)->list() == newTL, 692 "List was not initialized correctly"); 693 if (prevTL == NULL) { // we are the only tree node 694 assert(root() == NULL, "control point invariant"); 695 set_root(newTL); 696 } else { // insert under prevTL ... 697 if (prevTL->size() < size) { // am right child 698 assert(prevTL->right() == NULL, "control point invariant"); 699 prevTL->set_right(newTL); 700 } else { // am left child 701 assert(prevTL->size() > size && prevTL->left() == NULL, "cpt pt inv"); 702 prevTL->set_left(newTL); 703 } 704 } 705 } 706 assert(tc->list() != NULL, "Tree list should be set"); 707 708 inc_total_size(size); 709 // Method 'total_size_in_tree' walks through the every block in the 710 // tree, so it can cause significant performance loss if there are 711 // many blocks in the tree 712 assert(!FLSVerifyDictionary || total_size_in_tree(root()) == total_size(), "_total_size inconsistency"); 713 set_total_free_blocks(total_free_blocks() + 1); 714 if (FLSVerifyDictionary) { 715 verify_tree(); 716 } 717 } 718 719 template <class Chunk_t, class FreeList_t> 720 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::max_chunk_size() const { 721 verify_par_locked(); 722 TreeList<Chunk_t, FreeList_t>* tc = root(); 723 if (tc == NULL) return 0; 724 for (; tc->right() != NULL; tc = tc->right()); 725 return tc->size(); 726 } 727 728 template <class Chunk_t, class FreeList_t> 729 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_list_length(TreeList<Chunk_t, FreeList_t>* tl) const { 730 size_t res; 731 res = tl->count(); 732 #ifdef ASSERT 733 size_t cnt; 734 Chunk_t* tc = tl->head(); 735 for (cnt = 0; tc != NULL; tc = tc->next(), cnt++); 736 assert(res == cnt, "The count is not being maintained correctly"); 737 #endif 738 return res; 739 } 740 741 template <class Chunk_t, class FreeList_t> 742 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_size_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const { 743 if (tl == NULL) 744 return 0; 745 return (tl->size() * total_list_length(tl)) + 746 total_size_in_tree(tl->left()) + 747 total_size_in_tree(tl->right()); 748 } 749 750 template <class Chunk_t, class FreeList_t> 751 double BinaryTreeDictionary<Chunk_t, FreeList_t>::sum_of_squared_block_sizes(TreeList<Chunk_t, FreeList_t>* const tl) const { 752 if (tl == NULL) { 753 return 0.0; 754 } 755 double size = (double)(tl->size()); 756 double curr = size * size * total_list_length(tl); 757 curr += sum_of_squared_block_sizes(tl->left()); 758 curr += sum_of_squared_block_sizes(tl->right()); 759 return curr; 760 } 761 762 template <class Chunk_t, class FreeList_t> 763 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_free_blocks_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const { 764 if (tl == NULL) 765 return 0; 766 return total_list_length(tl) + 767 total_free_blocks_in_tree(tl->left()) + 768 total_free_blocks_in_tree(tl->right()); 769 } 770 771 template <class Chunk_t, class FreeList_t> 772 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::num_free_blocks() const { 773 assert(total_free_blocks_in_tree(root()) == total_free_blocks(), 774 "_total_free_blocks inconsistency"); 775 return total_free_blocks(); 776 } 777 778 template <class Chunk_t, class FreeList_t> 779 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::tree_height_helper(TreeList<Chunk_t, FreeList_t>* tl) const { 780 if (tl == NULL) 781 return 0; 782 return 1 + MAX2(tree_height_helper(tl->left()), 783 tree_height_helper(tl->right())); 784 } 785 786 template <class Chunk_t, class FreeList_t> 787 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::tree_height() const { 788 return tree_height_helper(root()); 789 } 790 791 template <class Chunk_t, class FreeList_t> 792 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_nodes_helper(TreeList<Chunk_t, FreeList_t>* tl) const { 793 if (tl == NULL) { 794 return 0; 795 } 796 return 1 + total_nodes_helper(tl->left()) + 797 total_nodes_helper(tl->right()); 798 } 799 800 template <class Chunk_t, class FreeList_t> 801 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_nodes_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const { 802 return total_nodes_helper(root()); 803 } 804 805 // Searches the tree for a chunk that ends at the 806 // specified address. 807 template <class Chunk_t, class FreeList_t> 808 class EndTreeSearchClosure : public DescendTreeSearchClosure<Chunk_t, FreeList_t> { 809 HeapWord* _target; 810 Chunk_t* _found; 811 812 public: 813 EndTreeSearchClosure(HeapWord* target) : _target(target), _found(NULL) {} 814 bool do_list(FreeList_t* fl) { 815 Chunk_t* item = fl->head(); 816 while (item != NULL) { 817 if (item->end() == (uintptr_t*) _target) { 818 _found = item; 819 return true; 820 } 821 item = item->next(); 822 } 823 return false; 824 } 825 Chunk_t* found() { return _found; } 826 }; 827 828 template <class Chunk_t, class FreeList_t> 829 Chunk_t* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_chunk_ends_at(HeapWord* target) const { 830 EndTreeSearchClosure<Chunk_t, FreeList_t> etsc(target); 831 bool found_target = etsc.do_tree(root()); 832 assert(found_target || etsc.found() == NULL, "Consistency check"); 833 assert(!found_target || etsc.found() != NULL, "Consistency check"); 834 return etsc.found(); 835 } 836 837 // Closures and methods for calculating total bytes returned to the 838 // free lists in the tree. 839 #ifndef PRODUCT 840 template <class Chunk_t, class FreeList_t> 841 class InitializeDictReturnedBytesClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { 842 public: 843 void do_list(FreeList_t* fl) { 844 fl->set_returned_bytes(0); 845 } 846 }; 847 848 template <class Chunk_t, class FreeList_t> 849 void BinaryTreeDictionary<Chunk_t, FreeList_t>::initialize_dict_returned_bytes() { 850 InitializeDictReturnedBytesClosure<Chunk_t, FreeList_t> idrb; 851 idrb.do_tree(root()); 852 } 853 854 template <class Chunk_t, class FreeList_t> 855 class ReturnedBytesClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { 856 size_t _dict_returned_bytes; 857 public: 858 ReturnedBytesClosure() { _dict_returned_bytes = 0; } 859 void do_list(FreeList_t* fl) { 860 _dict_returned_bytes += fl->returned_bytes(); 861 } 862 size_t dict_returned_bytes() { return _dict_returned_bytes; } 863 }; 864 865 template <class Chunk_t, class FreeList_t> 866 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::sum_dict_returned_bytes() { 867 ReturnedBytesClosure<Chunk_t, FreeList_t> rbc; 868 rbc.do_tree(root()); 869 870 return rbc.dict_returned_bytes(); 871 } 872 873 // Count the number of entries in the tree. 874 template <class Chunk_t, class FreeList_t> 875 class treeCountClosure : public DescendTreeCensusClosure<Chunk_t, FreeList_t> { 876 public: 877 uint count; 878 treeCountClosure(uint c) { count = c; } 879 void do_list(FreeList_t* fl) { 880 count++; 881 } 882 }; 883 884 template <class Chunk_t, class FreeList_t> 885 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_count() { 886 treeCountClosure<Chunk_t, FreeList_t> ctc(0); 887 ctc.do_tree(root()); 888 return ctc.count; 889 } 890 891 template <class Chunk_t, class FreeList_t> 892 Mutex* BinaryTreeDictionary<Chunk_t, FreeList_t>::par_lock() const { 893 return _lock; 894 } 895 896 template <class Chunk_t, class FreeList_t> 897 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_par_lock(Mutex* lock) { 898 _lock = lock; 899 } 900 901 template <class Chunk_t, class FreeList_t> 902 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_par_locked() const { 903 #ifdef ASSERT 904 Thread* my_thread = Thread::current(); 905 if (my_thread->is_GC_task_thread()) { 906 assert(par_lock() != NULL, "Should be using locking?"); 907 assert_lock_strong(par_lock()); 908 } 909 #endif // ASSERT 910 } 911 #endif // PRODUCT 912 913 // Print summary statistics 914 template <class Chunk_t, class FreeList_t> 915 void BinaryTreeDictionary<Chunk_t, FreeList_t>::report_statistics(outputStream* st) const { 916 verify_par_locked(); 917 st->print_cr("Statistics for BinaryTreeDictionary:"); 918 st->print_cr("------------------------------------"); 919 size_t total_size = total_chunk_size(debug_only(NULL)); 920 size_t free_blocks = num_free_blocks(); 921 st->print_cr("Total Free Space: " SIZE_FORMAT, total_size); 922 st->print_cr("Max Chunk Size: " SIZE_FORMAT, max_chunk_size()); 923 st->print_cr("Number of Blocks: " SIZE_FORMAT, free_blocks); 924 if (free_blocks > 0) { 925 st->print_cr("Av. Block Size: " SIZE_FORMAT, total_size/free_blocks); 926 } 927 st->print_cr("Tree Height: " SIZE_FORMAT, tree_height()); 928 } 929 930 template <class Chunk_t, class FreeList_t> 931 class PrintFreeListsClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { 932 outputStream* _st; 933 int _print_line; 934 935 public: 936 PrintFreeListsClosure(outputStream* st) { 937 _st = st; 938 _print_line = 0; 939 } 940 void do_list(FreeList_t* fl) { 941 if (++_print_line >= 40) { 942 FreeList_t::print_labels_on(_st, "size"); 943 _print_line = 0; 944 } 945 fl->print_on(_st); 946 size_t sz = fl->size(); 947 for (Chunk_t* fc = fl->head(); fc != NULL; 948 fc = fc->next()) { 949 _st->print_cr("\t[" PTR_FORMAT "," PTR_FORMAT ") %s", 950 p2i(fc), p2i((HeapWord*)fc + sz), 951 fc->cantCoalesce() ? "\t CC" : ""); 952 } 953 } 954 }; 955 956 template <class Chunk_t, class FreeList_t> 957 void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_free_lists(outputStream* st) const { 958 959 FreeList_t::print_labels_on(st, "size"); 960 PrintFreeListsClosure<Chunk_t, FreeList_t> pflc(st); 961 pflc.do_tree(root()); 962 } 963 964 // Verify the following tree invariants: 965 // . _root has no parent 966 // . parent and child point to each other 967 // . each node's key correctly related to that of its child(ren) 968 template <class Chunk_t, class FreeList_t> 969 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_tree() const { 970 guarantee(root() == NULL || total_free_blocks() == 0 || 971 total_size() != 0, "_total_size shouldn't be 0?"); 972 guarantee(root() == NULL || root()->parent() == NULL, "_root shouldn't have parent"); 973 verify_tree_helper(root()); 974 } 975 976 template <class Chunk_t, class FreeList_t> 977 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_prev_free_ptrs(TreeList<Chunk_t, FreeList_t>* tl) { 978 size_t ct = 0; 979 for (Chunk_t* curFC = tl->head(); curFC != NULL; curFC = curFC->next()) { 980 ct++; 981 assert(curFC->prev() == NULL || curFC->prev()->is_free(), 982 "Chunk should be free"); 983 } 984 return ct; 985 } 986 987 // Note: this helper is recursive rather than iterative, so use with 988 // caution on very deep trees; and watch out for stack overflow errors; 989 // In general, to be used only for debugging. 990 template <class Chunk_t, class FreeList_t> 991 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_tree_helper(TreeList<Chunk_t, FreeList_t>* tl) const { 992 if (tl == NULL) 993 return; 994 guarantee(tl->size() != 0, "A list must has a size"); 995 guarantee(tl->left() == NULL || tl->left()->parent() == tl, 996 "parent<-/->left"); 997 guarantee(tl->right() == NULL || tl->right()->parent() == tl, 998 "parent<-/->right");; 999 guarantee(tl->left() == NULL || tl->left()->size() < tl->size(), 1000 "parent !> left"); 1001 guarantee(tl->right() == NULL || tl->right()->size() > tl->size(), 1002 "parent !< left"); 1003 guarantee(tl->head() == NULL || tl->head()->is_free(), "!Free"); 1004 guarantee(tl->head() == NULL || tl->head_as_TreeChunk()->list() == tl, 1005 "list inconsistency"); 1006 guarantee(tl->count() > 0 || (tl->head() == NULL && tl->tail() == NULL), 1007 "list count is inconsistent"); 1008 guarantee(tl->count() > 1 || tl->head() == tl->tail(), 1009 "list is incorrectly constructed"); 1010 size_t count = verify_prev_free_ptrs(tl); 1011 guarantee(count == (size_t)tl->count(), "Node count is incorrect"); 1012 if (tl->head() != NULL) { 1013 tl->head_as_TreeChunk()->verify_tree_chunk_list(); 1014 } 1015 verify_tree_helper(tl->left()); 1016 verify_tree_helper(tl->right()); 1017 } 1018 1019 template <class Chunk_t, class FreeList_t> 1020 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify() const { 1021 verify_tree(); 1022 guarantee(total_size() == total_size_in_tree(root()), "Total Size inconsistency"); 1023 } 1024 1025 template <class Chunk_t, class FreeList_t> 1026 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_chunk_size(debug_only(const Mutex* lock)) const { 1027 debug_only( 1028 if (lock != NULL && lock->owned_by_self()) { 1029 assert(total_size_in_tree(root()) == total_size(), 1030 "_total_size inconsistency"); 1031 } 1032 ) 1033 return total_size(); 1034 } 1035 1036 #endif // SHARE_VM_MEMORY_BINARYTREEDICTIONARY_INLINE_HPP