1 /* 2 * Copyright (c) 2001, 2015, 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 #include "precompiled.hpp" 26 #include "gc/cms/allocationStats.hpp" 27 #include "gc/shared/spaceDecorator.hpp" 28 #include "memory/binaryTreeDictionary.hpp" 29 #include "memory/freeBlockDictionary.hpp" 30 #include "memory/freeList.hpp" 31 #include "memory/metachunk.hpp" 32 #include "memory/resourceArea.hpp" 33 #include "runtime/globals.hpp" 34 #include "utilities/macros.hpp" 35 #include "utilities/ostream.hpp" 36 #if INCLUDE_ALL_GCS 37 #include "gc/cms/adaptiveFreeList.hpp" 38 #include "gc/cms/freeChunk.hpp" 39 #endif // INCLUDE_ALL_GCS 40 41 //////////////////////////////////////////////////////////////////////////////// 42 // A binary tree based search structure for free blocks. 43 // This is currently used in the Concurrent Mark&Sweep implementation. 44 //////////////////////////////////////////////////////////////////////////////// 45 46 template <class Chunk_t, class FreeList_t> 47 size_t TreeChunk<Chunk_t, FreeList_t>::_min_tree_chunk_size = sizeof(TreeChunk<Chunk_t, FreeList_t>)/HeapWordSize; 48 49 template <class Chunk_t, class FreeList_t> 50 TreeChunk<Chunk_t, FreeList_t>* TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(Chunk_t* fc) { 51 // Do some assertion checking here. 52 return (TreeChunk<Chunk_t, FreeList_t>*) fc; 53 } 54 55 template <class Chunk_t, class FreeList_t> 56 void TreeChunk<Chunk_t, FreeList_t>::verify_tree_chunk_list() const { 57 TreeChunk<Chunk_t, FreeList_t>* nextTC = (TreeChunk<Chunk_t, FreeList_t>*)next(); 58 if (prev() != NULL) { // interior list node shouldn't have tree fields 59 guarantee(embedded_list()->parent() == NULL && embedded_list()->left() == NULL && 60 embedded_list()->right() == NULL, "should be clear"); 61 } 62 if (nextTC != NULL) { 63 guarantee(as_TreeChunk(nextTC->prev()) == this, "broken chain"); 64 guarantee(nextTC->size() == size(), "wrong size"); 65 nextTC->verify_tree_chunk_list(); 66 } 67 } 68 69 template <class Chunk_t, class FreeList_t> 70 TreeList<Chunk_t, FreeList_t>::TreeList() : _parent(NULL), 71 _left(NULL), _right(NULL) {} 72 73 template <class Chunk_t, class FreeList_t> 74 TreeList<Chunk_t, FreeList_t>* 75 TreeList<Chunk_t, FreeList_t>::as_TreeList(TreeChunk<Chunk_t,FreeList_t>* tc) { 76 // This first free chunk in the list will be the tree list. 77 assert((tc->size() >= (TreeChunk<Chunk_t, FreeList_t>::min_size())), 78 "Chunk is too small for a TreeChunk"); 79 TreeList<Chunk_t, FreeList_t>* tl = tc->embedded_list(); 80 tl->initialize(); 81 tc->set_list(tl); 82 tl->set_size(tc->size()); 83 tl->link_head(tc); 84 tl->link_tail(tc); 85 tl->set_count(1); 86 assert(tl->parent() == NULL, "Should be clear"); 87 return tl; 88 } 89 90 template <class Chunk_t, class FreeList_t> 91 TreeList<Chunk_t, FreeList_t>* 92 TreeList<Chunk_t, FreeList_t>::as_TreeList(HeapWord* addr, size_t size) { 93 TreeChunk<Chunk_t, FreeList_t>* tc = (TreeChunk<Chunk_t, FreeList_t>*) addr; 94 assert((size >= TreeChunk<Chunk_t, FreeList_t>::min_size()), 95 "Chunk is too small for a TreeChunk"); 96 // The space will have been mangled initially but 97 // is not remangled when a Chunk_t is returned to the free list 98 // (since it is used to maintain the chunk on the free list). 99 tc->assert_is_mangled(); 100 tc->set_size(size); 101 tc->link_prev(NULL); 102 tc->link_next(NULL); 103 TreeList<Chunk_t, FreeList_t>* tl = TreeList<Chunk_t, FreeList_t>::as_TreeList(tc); 104 return tl; 105 } 106 107 108 #if INCLUDE_ALL_GCS 109 // Specialize for AdaptiveFreeList which tries to avoid 110 // splitting a chunk of a size that is under populated in favor of 111 // an over populated size. The general get_better_list() just returns 112 // the current list. 113 template <> 114 TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >* 115 TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >::get_better_list( 116 BinaryTreeDictionary<FreeChunk, ::AdaptiveFreeList<FreeChunk> >* dictionary) { 117 // A candidate chunk has been found. If it is already under 118 // populated, get a chunk associated with the hint for this 119 // chunk. 120 121 TreeList<FreeChunk, ::AdaptiveFreeList<FreeChunk> >* curTL = this; 122 if (curTL->surplus() <= 0) { 123 /* Use the hint to find a size with a surplus, and reset the hint. */ 124 TreeList<FreeChunk, ::AdaptiveFreeList<FreeChunk> >* hintTL = this; 125 while (hintTL->hint() != 0) { 126 assert(hintTL->hint() > hintTL->size(), 127 "hint points in the wrong direction"); 128 hintTL = dictionary->find_list(hintTL->hint()); 129 assert(curTL != hintTL, "Infinite loop"); 130 if (hintTL == NULL || 131 hintTL == curTL /* Should not happen but protect against it */ ) { 132 // No useful hint. Set the hint to NULL and go on. 133 curTL->set_hint(0); 134 break; 135 } 136 assert(hintTL->size() > curTL->size(), "hint is inconsistent"); 137 if (hintTL->surplus() > 0) { 138 // The hint led to a list that has a surplus. Use it. 139 // Set the hint for the candidate to an overpopulated 140 // size. 141 curTL->set_hint(hintTL->size()); 142 // Change the candidate. 143 curTL = hintTL; 144 break; 145 } 146 } 147 } 148 return curTL; 149 } 150 #endif // INCLUDE_ALL_GCS 151 152 template <class Chunk_t, class FreeList_t> 153 TreeList<Chunk_t, FreeList_t>* 154 TreeList<Chunk_t, FreeList_t>::get_better_list( 155 BinaryTreeDictionary<Chunk_t, FreeList_t>* dictionary) { 156 return this; 157 } 158 159 template <class Chunk_t, class FreeList_t> 160 TreeList<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::remove_chunk_replace_if_needed(TreeChunk<Chunk_t, FreeList_t>* tc) { 161 162 TreeList<Chunk_t, FreeList_t>* retTL = this; 163 Chunk_t* list = head(); 164 assert(!list || list != list->next(), "Chunk on list twice"); 165 assert(tc != NULL, "Chunk being removed is NULL"); 166 assert(parent() == NULL || this == parent()->left() || 167 this == parent()->right(), "list is inconsistent"); 168 assert(tc->is_free(), "Header is not marked correctly"); 169 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 170 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 171 172 Chunk_t* prevFC = tc->prev(); 173 TreeChunk<Chunk_t, FreeList_t>* nextTC = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(tc->next()); 174 assert(list != NULL, "should have at least the target chunk"); 175 176 // Is this the first item on the list? 177 if (tc == list) { 178 // The "getChunk..." functions for a TreeList<Chunk_t, FreeList_t> will not return the 179 // first chunk in the list unless it is the last chunk in the list 180 // because the first chunk is also acting as the tree node. 181 // When coalescing happens, however, the first chunk in the a tree 182 // list can be the start of a free range. Free ranges are removed 183 // from the free lists so that they are not available to be 184 // allocated when the sweeper yields (giving up the free list lock) 185 // to allow mutator activity. If this chunk is the first in the 186 // list and is not the last in the list, do the work to copy the 187 // TreeList<Chunk_t, FreeList_t> from the first chunk to the next chunk and update all 188 // the TreeList<Chunk_t, FreeList_t> pointers in the chunks in the list. 189 if (nextTC == NULL) { 190 assert(prevFC == NULL, "Not last chunk in the list"); 191 set_tail(NULL); 192 set_head(NULL); 193 } else { 194 // copy embedded list. 195 nextTC->set_embedded_list(tc->embedded_list()); 196 retTL = nextTC->embedded_list(); 197 // Fix the pointer to the list in each chunk in the list. 198 // This can be slow for a long list. Consider having 199 // an option that does not allow the first chunk on the 200 // list to be coalesced. 201 for (TreeChunk<Chunk_t, FreeList_t>* curTC = nextTC; curTC != NULL; 202 curTC = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(curTC->next())) { 203 curTC->set_list(retTL); 204 } 205 // Fix the parent to point to the new TreeList<Chunk_t, FreeList_t>. 206 if (retTL->parent() != NULL) { 207 if (this == retTL->parent()->left()) { 208 retTL->parent()->set_left(retTL); 209 } else { 210 assert(this == retTL->parent()->right(), "Parent is incorrect"); 211 retTL->parent()->set_right(retTL); 212 } 213 } 214 // Fix the children's parent pointers to point to the 215 // new list. 216 assert(right() == retTL->right(), "Should have been copied"); 217 if (retTL->right() != NULL) { 218 retTL->right()->set_parent(retTL); 219 } 220 assert(left() == retTL->left(), "Should have been copied"); 221 if (retTL->left() != NULL) { 222 retTL->left()->set_parent(retTL); 223 } 224 retTL->link_head(nextTC); 225 assert(nextTC->is_free(), "Should be a free chunk"); 226 } 227 } else { 228 if (nextTC == NULL) { 229 // Removing chunk at tail of list 230 this->link_tail(prevFC); 231 } 232 // Chunk is interior to the list 233 prevFC->link_after(nextTC); 234 } 235 236 // Below this point the embedded TreeList<Chunk_t, FreeList_t> being used for the 237 // tree node may have changed. Don't use "this" 238 // TreeList<Chunk_t, FreeList_t>*. 239 // chunk should still be a free chunk (bit set in _prev) 240 assert(!retTL->head() || retTL->size() == retTL->head()->size(), 241 "Wrong sized chunk in list"); 242 debug_only( 243 tc->link_prev(NULL); 244 tc->link_next(NULL); 245 tc->set_list(NULL); 246 bool prev_found = false; 247 bool next_found = false; 248 for (Chunk_t* curFC = retTL->head(); 249 curFC != NULL; curFC = curFC->next()) { 250 assert(curFC != tc, "Chunk is still in list"); 251 if (curFC == prevFC) { 252 prev_found = true; 253 } 254 if (curFC == nextTC) { 255 next_found = true; 256 } 257 } 258 assert(prevFC == NULL || prev_found, "Chunk was lost from list"); 259 assert(nextTC == NULL || next_found, "Chunk was lost from list"); 260 assert(retTL->parent() == NULL || 261 retTL == retTL->parent()->left() || 262 retTL == retTL->parent()->right(), 263 "list is inconsistent"); 264 ) 265 retTL->decrement_count(); 266 267 assert(tc->is_free(), "Should still be a free chunk"); 268 assert(retTL->head() == NULL || retTL->head()->prev() == NULL, 269 "list invariant"); 270 assert(retTL->tail() == NULL || retTL->tail()->next() == NULL, 271 "list invariant"); 272 return retTL; 273 } 274 275 template <class Chunk_t, class FreeList_t> 276 void TreeList<Chunk_t, FreeList_t>::return_chunk_at_tail(TreeChunk<Chunk_t, FreeList_t>* chunk) { 277 assert(chunk != NULL, "returning NULL chunk"); 278 assert(chunk->list() == this, "list should be set for chunk"); 279 assert(tail() != NULL, "The tree list is embedded in the first chunk"); 280 // which means that the list can never be empty. 281 assert(!this->verify_chunk_in_free_list(chunk), "Double entry"); 282 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 283 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 284 285 Chunk_t* fc = tail(); 286 fc->link_after(chunk); 287 this->link_tail(chunk); 288 289 assert(!tail() || size() == tail()->size(), "Wrong sized chunk in list"); 290 FreeList_t::increment_count(); 291 debug_only(this->increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));) 292 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 293 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 294 } 295 296 // Add this chunk at the head of the list. "At the head of the list" 297 // is defined to be after the chunk pointer to by head(). This is 298 // because the TreeList<Chunk_t, FreeList_t> is embedded in the first TreeChunk<Chunk_t, FreeList_t> in the 299 // list. See the definition of TreeChunk<Chunk_t, FreeList_t>. 300 template <class Chunk_t, class FreeList_t> 301 void TreeList<Chunk_t, FreeList_t>::return_chunk_at_head(TreeChunk<Chunk_t, FreeList_t>* chunk) { 302 assert(chunk->list() == this, "list should be set for chunk"); 303 assert(head() != NULL, "The tree list is embedded in the first chunk"); 304 assert(chunk != NULL, "returning NULL chunk"); 305 assert(!this->verify_chunk_in_free_list(chunk), "Double entry"); 306 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 307 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 308 309 Chunk_t* fc = head()->next(); 310 if (fc != NULL) { 311 chunk->link_after(fc); 312 } else { 313 assert(tail() == NULL, "List is inconsistent"); 314 this->link_tail(chunk); 315 } 316 head()->link_after(chunk); 317 assert(!head() || size() == head()->size(), "Wrong sized chunk in list"); 318 FreeList_t::increment_count(); 319 debug_only(this->increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));) 320 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 321 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 322 } 323 324 template <class Chunk_t, class FreeList_t> 325 void TreeChunk<Chunk_t, FreeList_t>::assert_is_mangled() const { 326 assert((ZapUnusedHeapArea && 327 SpaceMangler::is_mangled((HeapWord*) Chunk_t::size_addr()) && 328 SpaceMangler::is_mangled((HeapWord*) Chunk_t::prev_addr()) && 329 SpaceMangler::is_mangled((HeapWord*) Chunk_t::next_addr())) || 330 (size() == 0 && prev() == NULL && next() == NULL), 331 "Space should be clear or mangled"); 332 } 333 334 template <class Chunk_t, class FreeList_t> 335 TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::head_as_TreeChunk() { 336 assert(head() == NULL || (TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(head())->list() == this), 337 "Wrong type of chunk?"); 338 return TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(head()); 339 } 340 341 template <class Chunk_t, class FreeList_t> 342 TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::first_available() { 343 assert(head() != NULL, "The head of the list cannot be NULL"); 344 Chunk_t* fc = head()->next(); 345 TreeChunk<Chunk_t, FreeList_t>* retTC; 346 if (fc == NULL) { 347 retTC = head_as_TreeChunk(); 348 } else { 349 retTC = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(fc); 350 } 351 assert(retTC->list() == this, "Wrong type of chunk."); 352 return retTC; 353 } 354 355 // Returns the block with the largest heap address amongst 356 // those in the list for this size; potentially slow and expensive, 357 // use with caution! 358 template <class Chunk_t, class FreeList_t> 359 TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::largest_address() { 360 assert(head() != NULL, "The head of the list cannot be NULL"); 361 Chunk_t* fc = head()->next(); 362 TreeChunk<Chunk_t, FreeList_t>* retTC; 363 if (fc == NULL) { 364 retTC = head_as_TreeChunk(); 365 } else { 366 // walk down the list and return the one with the highest 367 // heap address among chunks of this size. 368 Chunk_t* last = fc; 369 while (fc->next() != NULL) { 370 if ((HeapWord*)last < (HeapWord*)fc) { 371 last = fc; 372 } 373 fc = fc->next(); 374 } 375 retTC = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(last); 376 } 377 assert(retTC->list() == this, "Wrong type of chunk."); 378 return retTC; 379 } 380 381 template <class Chunk_t, class FreeList_t> 382 BinaryTreeDictionary<Chunk_t, FreeList_t>::BinaryTreeDictionary(MemRegion mr) { 383 assert((mr.byte_size() > min_size()), "minimum chunk size"); 384 385 reset(mr); 386 assert(root()->left() == NULL, "reset check failed"); 387 assert(root()->right() == NULL, "reset check failed"); 388 assert(root()->head()->next() == NULL, "reset check failed"); 389 assert(root()->head()->prev() == NULL, "reset check failed"); 390 assert(total_size() == root()->size(), "reset check failed"); 391 assert(total_free_blocks() == 1, "reset check failed"); 392 } 393 394 template <class Chunk_t, class FreeList_t> 395 void BinaryTreeDictionary<Chunk_t, FreeList_t>::inc_total_size(size_t inc) { 396 _total_size = _total_size + inc; 397 } 398 399 template <class Chunk_t, class FreeList_t> 400 void BinaryTreeDictionary<Chunk_t, FreeList_t>::dec_total_size(size_t dec) { 401 _total_size = _total_size - dec; 402 } 403 404 template <class Chunk_t, class FreeList_t> 405 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset(MemRegion mr) { 406 assert((mr.byte_size() > min_size()), "minimum chunk size"); 407 set_root(TreeList<Chunk_t, FreeList_t>::as_TreeList(mr.start(), mr.word_size())); 408 set_total_size(mr.word_size()); 409 set_total_free_blocks(1); 410 } 411 412 template <class Chunk_t, class FreeList_t> 413 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset(HeapWord* addr, size_t byte_size) { 414 MemRegion mr(addr, heap_word_size(byte_size)); 415 reset(mr); 416 } 417 418 template <class Chunk_t, class FreeList_t> 419 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset() { 420 set_root(NULL); 421 set_total_size(0); 422 set_total_free_blocks(0); 423 } 424 425 // Get a free block of size at least size from tree, or NULL. 426 template <class Chunk_t, class FreeList_t> 427 TreeChunk<Chunk_t, FreeList_t>* 428 BinaryTreeDictionary<Chunk_t, FreeList_t>::get_chunk_from_tree( 429 size_t size, 430 enum FreeBlockDictionary<Chunk_t>::Dither dither) 431 { 432 TreeList<Chunk_t, FreeList_t> *curTL, *prevTL; 433 TreeChunk<Chunk_t, FreeList_t>* retTC = NULL; 434 435 assert((size >= min_size()), "minimum chunk size"); 436 if (FLSVerifyDictionary) { 437 verify_tree(); 438 } 439 // starting at the root, work downwards trying to find match. 440 // Remember the last node of size too great or too small. 441 for (prevTL = curTL = root(); curTL != NULL;) { 442 if (curTL->size() == size) { // exact match 443 break; 444 } 445 prevTL = curTL; 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 if (curTL == NULL) { // couldn't find exact match 454 455 if (dither == FreeBlockDictionary<Chunk_t>::exactly) return NULL; 456 457 // try and find the next larger size by walking back up the search path 458 for (curTL = prevTL; curTL != NULL;) { 459 if (curTL->size() >= size) break; 460 else curTL = curTL->parent(); 461 } 462 assert(curTL == NULL || curTL->count() > 0, 463 "An empty list should not be in the tree"); 464 } 465 if (curTL != NULL) { 466 assert(curTL->size() >= size, "size inconsistency"); 467 468 curTL = curTL->get_better_list(this); 469 470 retTC = curTL->first_available(); 471 assert((retTC != NULL) && (curTL->count() > 0), 472 "A list in the binary tree should not be NULL"); 473 assert(retTC->size() >= size, 474 "A chunk of the wrong size was found"); 475 remove_chunk_from_tree(retTC); 476 assert(retTC->is_free(), "Header is not marked correctly"); 477 } 478 479 if (FLSVerifyDictionary) { 480 verify(); 481 } 482 return retTC; 483 } 484 485 template <class Chunk_t, class FreeList_t> 486 TreeList<Chunk_t, FreeList_t>* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_list(size_t size) const { 487 TreeList<Chunk_t, FreeList_t>* curTL; 488 for (curTL = root(); curTL != NULL;) { 489 if (curTL->size() == size) { // exact match 490 break; 491 } 492 493 if (curTL->size() < size) { // proceed to right sub-tree 494 curTL = curTL->right(); 495 } else { // proceed to left sub-tree 496 assert(curTL->size() > size, "size inconsistency"); 497 curTL = curTL->left(); 498 } 499 } 500 return curTL; 501 } 502 503 504 template <class Chunk_t, class FreeList_t> 505 bool BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_chunk_in_free_list(Chunk_t* tc) const { 506 size_t size = tc->size(); 507 TreeList<Chunk_t, FreeList_t>* tl = find_list(size); 508 if (tl == NULL) { 509 return false; 510 } else { 511 return tl->verify_chunk_in_free_list(tc); 512 } 513 } 514 515 template <class Chunk_t, class FreeList_t> 516 Chunk_t* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_largest_dict() const { 517 TreeList<Chunk_t, FreeList_t> *curTL = root(); 518 if (curTL != NULL) { 519 while(curTL->right() != NULL) curTL = curTL->right(); 520 return curTL->largest_address(); 521 } else { 522 return NULL; 523 } 524 } 525 526 // Remove the current chunk from the tree. If it is not the last 527 // chunk in a list on a tree node, just unlink it. 528 // If it is the last chunk in the list (the next link is NULL), 529 // remove the node and repair the tree. 530 template <class Chunk_t, class FreeList_t> 531 TreeChunk<Chunk_t, FreeList_t>* 532 BinaryTreeDictionary<Chunk_t, FreeList_t>::remove_chunk_from_tree(TreeChunk<Chunk_t, FreeList_t>* tc) { 533 assert(tc != NULL, "Should not call with a NULL chunk"); 534 assert(tc->is_free(), "Header is not marked correctly"); 535 536 TreeList<Chunk_t, FreeList_t> *newTL, *parentTL; 537 TreeChunk<Chunk_t, FreeList_t>* retTC; 538 TreeList<Chunk_t, FreeList_t>* tl = tc->list(); 539 debug_only( 540 bool removing_only_chunk = false; 541 if (tl == _root) { 542 if ((_root->left() == NULL) && (_root->right() == NULL)) { 543 if (_root->count() == 1) { 544 assert(_root->head() == tc, "Should only be this one chunk"); 545 removing_only_chunk = true; 546 } 547 } 548 } 549 ) 550 assert(tl != NULL, "List should be set"); 551 assert(tl->parent() == NULL || tl == tl->parent()->left() || 552 tl == tl->parent()->right(), "list is inconsistent"); 553 554 bool complicated_splice = false; 555 556 retTC = tc; 557 // Removing this chunk can have the side effect of changing the node 558 // (TreeList<Chunk_t, FreeList_t>*) in the tree. If the node is the root, update it. 559 TreeList<Chunk_t, FreeList_t>* replacementTL = tl->remove_chunk_replace_if_needed(tc); 560 assert(tc->is_free(), "Chunk should still be free"); 561 assert(replacementTL->parent() == NULL || 562 replacementTL == replacementTL->parent()->left() || 563 replacementTL == replacementTL->parent()->right(), 564 "list is inconsistent"); 565 if (tl == root()) { 566 assert(replacementTL->parent() == NULL, "Incorrectly replacing root"); 567 set_root(replacementTL); 568 } 569 #ifdef ASSERT 570 if (tl != replacementTL) { 571 assert(replacementTL->head() != NULL, 572 "If the tree list was replaced, it should not be a NULL list"); 573 TreeList<Chunk_t, FreeList_t>* rhl = replacementTL->head_as_TreeChunk()->list(); 574 TreeList<Chunk_t, FreeList_t>* rtl = 575 TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(replacementTL->tail())->list(); 576 assert(rhl == replacementTL, "Broken head"); 577 assert(rtl == replacementTL, "Broken tail"); 578 assert(replacementTL->size() == tc->size(), "Broken size"); 579 } 580 #endif 581 582 // Does the tree need to be repaired? 583 if (replacementTL->count() == 0) { 584 assert(replacementTL->head() == NULL && 585 replacementTL->tail() == NULL, "list count is incorrect"); 586 // Find the replacement node for the (soon to be empty) node being removed. 587 // if we have a single (or no) child, splice child in our stead 588 if (replacementTL->left() == NULL) { 589 // left is NULL so pick right. right may also be NULL. 590 newTL = replacementTL->right(); 591 debug_only(replacementTL->clear_right();) 592 } else if (replacementTL->right() == NULL) { 593 // right is NULL 594 newTL = replacementTL->left(); 595 debug_only(replacementTL->clear_left();) 596 } else { // we have both children, so, by patriarchal convention, 597 // my replacement is least node in right sub-tree 598 complicated_splice = true; 599 newTL = remove_tree_minimum(replacementTL->right()); 600 assert(newTL != NULL && newTL->left() == NULL && 601 newTL->right() == NULL, "sub-tree minimum exists"); 602 } 603 // newTL is the replacement for the (soon to be empty) node. 604 // newTL may be NULL. 605 // should verify; we just cleanly excised our replacement 606 if (FLSVerifyDictionary) { 607 verify_tree(); 608 } 609 // first make newTL my parent's child 610 if ((parentTL = replacementTL->parent()) == NULL) { 611 // newTL should be root 612 assert(tl == root(), "Incorrectly replacing root"); 613 set_root(newTL); 614 if (newTL != NULL) { 615 newTL->clear_parent(); 616 } 617 } else if (parentTL->right() == replacementTL) { 618 // replacementTL is a right child 619 parentTL->set_right(newTL); 620 } else { // replacementTL is a left child 621 assert(parentTL->left() == replacementTL, "should be left child"); 622 parentTL->set_left(newTL); 623 } 624 debug_only(replacementTL->clear_parent();) 625 if (complicated_splice) { // we need newTL to get replacementTL's 626 // two children 627 assert(newTL != NULL && 628 newTL->left() == NULL && newTL->right() == NULL, 629 "newTL should not have encumbrances from the past"); 630 // we'd like to assert as below: 631 // assert(replacementTL->left() != NULL && replacementTL->right() != NULL, 632 // "else !complicated_splice"); 633 // ... however, the above assertion is too strong because we aren't 634 // guaranteed that replacementTL->right() is still NULL. 635 // Recall that we removed 636 // the right sub-tree minimum from replacementTL. 637 // That may well have been its right 638 // child! So we'll just assert half of the above: 639 assert(replacementTL->left() != NULL, "else !complicated_splice"); 640 newTL->set_left(replacementTL->left()); 641 newTL->set_right(replacementTL->right()); 642 debug_only( 643 replacementTL->clear_right(); 644 replacementTL->clear_left(); 645 ) 646 } 647 assert(replacementTL->right() == NULL && 648 replacementTL->left() == NULL && 649 replacementTL->parent() == NULL, 650 "delete without encumbrances"); 651 } 652 653 assert(total_size() >= retTC->size(), "Incorrect total size"); 654 dec_total_size(retTC->size()); // size book-keeping 655 assert(total_free_blocks() > 0, "Incorrect total count"); 656 set_total_free_blocks(total_free_blocks() - 1); 657 658 assert(retTC != NULL, "null chunk?"); 659 assert(retTC->prev() == NULL && retTC->next() == NULL, 660 "should return without encumbrances"); 661 if (FLSVerifyDictionary) { 662 verify_tree(); 663 } 664 assert(!removing_only_chunk || _root == NULL, "root should be NULL"); 665 return TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(retTC); 666 } 667 668 // Remove the leftmost node (lm) in the tree and return it. 669 // If lm has a right child, link it to the left node of 670 // the parent of lm. 671 template <class Chunk_t, class FreeList_t> 672 TreeList<Chunk_t, FreeList_t>* BinaryTreeDictionary<Chunk_t, FreeList_t>::remove_tree_minimum(TreeList<Chunk_t, FreeList_t>* tl) { 673 assert(tl != NULL && tl->parent() != NULL, "really need a proper sub-tree"); 674 // locate the subtree minimum by walking down left branches 675 TreeList<Chunk_t, FreeList_t>* curTL = tl; 676 for (; curTL->left() != NULL; curTL = curTL->left()); 677 // obviously curTL now has at most one child, a right child 678 if (curTL != root()) { // Should this test just be removed? 679 TreeList<Chunk_t, FreeList_t>* parentTL = curTL->parent(); 680 if (parentTL->left() == curTL) { // curTL is a left child 681 parentTL->set_left(curTL->right()); 682 } else { 683 // If the list tl has no left child, then curTL may be 684 // the right child of parentTL. 685 assert(parentTL->right() == curTL, "should be a right child"); 686 parentTL->set_right(curTL->right()); 687 } 688 } else { 689 // The only use of this method would not pass the root of the 690 // tree (as indicated by the assertion above that the tree list 691 // has a parent) but the specification does not explicitly exclude the 692 // passing of the root so accommodate it. 693 set_root(NULL); 694 } 695 debug_only( 696 curTL->clear_parent(); // Test if this needs to be cleared 697 curTL->clear_right(); // recall, above, left child is already null 698 ) 699 // we just excised a (non-root) node, we should still verify all tree invariants 700 if (FLSVerifyDictionary) { 701 verify_tree(); 702 } 703 return curTL; 704 } 705 706 template <class Chunk_t, class FreeList_t> 707 void BinaryTreeDictionary<Chunk_t, FreeList_t>::insert_chunk_in_tree(Chunk_t* fc) { 708 TreeList<Chunk_t, FreeList_t> *curTL, *prevTL; 709 size_t size = fc->size(); 710 711 assert((size >= min_size()), 712 SIZE_FORMAT " is too small to be a TreeChunk<Chunk_t, FreeList_t> " SIZE_FORMAT, 713 size, min_size()); 714 if (FLSVerifyDictionary) { 715 verify_tree(); 716 } 717 718 fc->clear_next(); 719 fc->link_prev(NULL); 720 721 // work down from the _root, looking for insertion point 722 for (prevTL = curTL = root(); curTL != NULL;) { 723 if (curTL->size() == size) // exact match 724 break; 725 prevTL = curTL; 726 if (curTL->size() > size) { // follow left branch 727 curTL = curTL->left(); 728 } else { // follow right branch 729 assert(curTL->size() < size, "size inconsistency"); 730 curTL = curTL->right(); 731 } 732 } 733 TreeChunk<Chunk_t, FreeList_t>* tc = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(fc); 734 // This chunk is being returned to the binary tree. Its embedded 735 // TreeList<Chunk_t, FreeList_t> should be unused at this point. 736 tc->initialize(); 737 if (curTL != NULL) { // exact match 738 tc->set_list(curTL); 739 curTL->return_chunk_at_tail(tc); 740 } else { // need a new node in tree 741 tc->clear_next(); 742 tc->link_prev(NULL); 743 TreeList<Chunk_t, FreeList_t>* newTL = TreeList<Chunk_t, FreeList_t>::as_TreeList(tc); 744 assert(((TreeChunk<Chunk_t, FreeList_t>*)tc)->list() == newTL, 745 "List was not initialized correctly"); 746 if (prevTL == NULL) { // we are the only tree node 747 assert(root() == NULL, "control point invariant"); 748 set_root(newTL); 749 } else { // insert under prevTL ... 750 if (prevTL->size() < size) { // am right child 751 assert(prevTL->right() == NULL, "control point invariant"); 752 prevTL->set_right(newTL); 753 } else { // am left child 754 assert(prevTL->size() > size && prevTL->left() == NULL, "cpt pt inv"); 755 prevTL->set_left(newTL); 756 } 757 } 758 } 759 assert(tc->list() != NULL, "Tree list should be set"); 760 761 inc_total_size(size); 762 // Method 'total_size_in_tree' walks through the every block in the 763 // tree, so it can cause significant performance loss if there are 764 // many blocks in the tree 765 assert(!FLSVerifyDictionary || total_size_in_tree(root()) == total_size(), "_total_size inconsistency"); 766 set_total_free_blocks(total_free_blocks() + 1); 767 if (FLSVerifyDictionary) { 768 verify_tree(); 769 } 770 } 771 772 template <class Chunk_t, class FreeList_t> 773 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::max_chunk_size() const { 774 FreeBlockDictionary<Chunk_t>::verify_par_locked(); 775 TreeList<Chunk_t, FreeList_t>* tc = root(); 776 if (tc == NULL) return 0; 777 for (; tc->right() != NULL; tc = tc->right()); 778 return tc->size(); 779 } 780 781 template <class Chunk_t, class FreeList_t> 782 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_list_length(TreeList<Chunk_t, FreeList_t>* tl) const { 783 size_t res; 784 res = tl->count(); 785 #ifdef ASSERT 786 size_t cnt; 787 Chunk_t* tc = tl->head(); 788 for (cnt = 0; tc != NULL; tc = tc->next(), cnt++); 789 assert(res == cnt, "The count is not being maintained correctly"); 790 #endif 791 return res; 792 } 793 794 template <class Chunk_t, class FreeList_t> 795 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_size_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const { 796 if (tl == NULL) 797 return 0; 798 return (tl->size() * total_list_length(tl)) + 799 total_size_in_tree(tl->left()) + 800 total_size_in_tree(tl->right()); 801 } 802 803 template <class Chunk_t, class FreeList_t> 804 double BinaryTreeDictionary<Chunk_t, FreeList_t>::sum_of_squared_block_sizes(TreeList<Chunk_t, FreeList_t>* const tl) const { 805 if (tl == NULL) { 806 return 0.0; 807 } 808 double size = (double)(tl->size()); 809 double curr = size * size * total_list_length(tl); 810 curr += sum_of_squared_block_sizes(tl->left()); 811 curr += sum_of_squared_block_sizes(tl->right()); 812 return curr; 813 } 814 815 template <class Chunk_t, class FreeList_t> 816 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_free_blocks_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const { 817 if (tl == NULL) 818 return 0; 819 return total_list_length(tl) + 820 total_free_blocks_in_tree(tl->left()) + 821 total_free_blocks_in_tree(tl->right()); 822 } 823 824 template <class Chunk_t, class FreeList_t> 825 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::num_free_blocks() const { 826 assert(total_free_blocks_in_tree(root()) == total_free_blocks(), 827 "_total_free_blocks inconsistency"); 828 return total_free_blocks(); 829 } 830 831 template <class Chunk_t, class FreeList_t> 832 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::tree_height_helper(TreeList<Chunk_t, FreeList_t>* tl) const { 833 if (tl == NULL) 834 return 0; 835 return 1 + MAX2(tree_height_helper(tl->left()), 836 tree_height_helper(tl->right())); 837 } 838 839 template <class Chunk_t, class FreeList_t> 840 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::tree_height() const { 841 return tree_height_helper(root()); 842 } 843 844 template <class Chunk_t, class FreeList_t> 845 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_nodes_helper(TreeList<Chunk_t, FreeList_t>* tl) const { 846 if (tl == NULL) { 847 return 0; 848 } 849 return 1 + total_nodes_helper(tl->left()) + 850 total_nodes_helper(tl->right()); 851 } 852 853 template <class Chunk_t, class FreeList_t> 854 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_nodes_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const { 855 return total_nodes_helper(root()); 856 } 857 858 template <class Chunk_t, class FreeList_t> 859 void BinaryTreeDictionary<Chunk_t, FreeList_t>::dict_census_update(size_t size, bool split, bool birth){} 860 861 #if INCLUDE_ALL_GCS 862 template <> 863 void AFLBinaryTreeDictionary::dict_census_update(size_t size, bool split, bool birth) { 864 TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >* nd = find_list(size); 865 if (nd) { 866 if (split) { 867 if (birth) { 868 nd->increment_split_births(); 869 nd->increment_surplus(); 870 } else { 871 nd->increment_split_deaths(); 872 nd->decrement_surplus(); 873 } 874 } else { 875 if (birth) { 876 nd->increment_coal_births(); 877 nd->increment_surplus(); 878 } else { 879 nd->increment_coal_deaths(); 880 nd->decrement_surplus(); 881 } 882 } 883 } 884 // A list for this size may not be found (nd == 0) if 885 // This is a death where the appropriate list is now 886 // empty and has been removed from the list. 887 // This is a birth associated with a LinAB. The chunk 888 // for the LinAB is not in the dictionary. 889 } 890 #endif // INCLUDE_ALL_GCS 891 892 template <class Chunk_t, class FreeList_t> 893 bool BinaryTreeDictionary<Chunk_t, FreeList_t>::coal_dict_over_populated(size_t size) { 894 // For the general type of freelists, encourage coalescing by 895 // returning true. 896 return true; 897 } 898 899 #if INCLUDE_ALL_GCS 900 template <> 901 bool AFLBinaryTreeDictionary::coal_dict_over_populated(size_t size) { 902 if (FLSAlwaysCoalesceLarge) return true; 903 904 TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >* list_of_size = find_list(size); 905 // None of requested size implies overpopulated. 906 return list_of_size == NULL || list_of_size->coal_desired() <= 0 || 907 list_of_size->count() > list_of_size->coal_desired(); 908 } 909 #endif // INCLUDE_ALL_GCS 910 911 // Closures for walking the binary tree. 912 // do_list() walks the free list in a node applying the closure 913 // to each free chunk in the list 914 // do_tree() walks the nodes in the binary tree applying do_list() 915 // to each list at each node. 916 917 template <class Chunk_t, class FreeList_t> 918 class TreeCensusClosure : public StackObj { 919 protected: 920 virtual void do_list(FreeList_t* fl) = 0; 921 public: 922 virtual void do_tree(TreeList<Chunk_t, FreeList_t>* tl) = 0; 923 }; 924 925 template <class Chunk_t, class FreeList_t> 926 class AscendTreeCensusClosure : public TreeCensusClosure<Chunk_t, FreeList_t> { 927 public: 928 void do_tree(TreeList<Chunk_t, FreeList_t>* tl) { 929 if (tl != NULL) { 930 do_tree(tl->left()); 931 this->do_list(tl); 932 do_tree(tl->right()); 933 } 934 } 935 }; 936 937 template <class Chunk_t, class FreeList_t> 938 class DescendTreeCensusClosure : public TreeCensusClosure<Chunk_t, FreeList_t> { 939 public: 940 void do_tree(TreeList<Chunk_t, FreeList_t>* tl) { 941 if (tl != NULL) { 942 do_tree(tl->right()); 943 this->do_list(tl); 944 do_tree(tl->left()); 945 } 946 } 947 }; 948 949 // For each list in the tree, calculate the desired, desired 950 // coalesce, count before sweep, and surplus before sweep. 951 template <class Chunk_t, class FreeList_t> 952 class BeginSweepClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { 953 double _percentage; 954 float _inter_sweep_current; 955 float _inter_sweep_estimate; 956 float _intra_sweep_estimate; 957 958 public: 959 BeginSweepClosure(double p, float inter_sweep_current, 960 float inter_sweep_estimate, 961 float intra_sweep_estimate) : 962 _percentage(p), 963 _inter_sweep_current(inter_sweep_current), 964 _inter_sweep_estimate(inter_sweep_estimate), 965 _intra_sweep_estimate(intra_sweep_estimate) { } 966 967 void do_list(FreeList<Chunk_t>* fl) {} 968 969 #if INCLUDE_ALL_GCS 970 void do_list(AdaptiveFreeList<Chunk_t>* fl) { 971 double coalSurplusPercent = _percentage; 972 fl->compute_desired(_inter_sweep_current, _inter_sweep_estimate, _intra_sweep_estimate); 973 fl->set_coal_desired((ssize_t)((double)fl->desired() * coalSurplusPercent)); 974 fl->set_before_sweep(fl->count()); 975 fl->set_bfr_surp(fl->surplus()); 976 } 977 #endif // INCLUDE_ALL_GCS 978 }; 979 980 // Used to search the tree until a condition is met. 981 // Similar to TreeCensusClosure but searches the 982 // tree and returns promptly when found. 983 984 template <class Chunk_t, class FreeList_t> 985 class TreeSearchClosure : public StackObj { 986 protected: 987 virtual bool do_list(FreeList_t* fl) = 0; 988 public: 989 virtual bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) = 0; 990 }; 991 992 #if 0 // Don't need this yet but here for symmetry. 993 template <class Chunk_t, class FreeList_t> 994 class AscendTreeSearchClosure : public TreeSearchClosure<Chunk_t> { 995 public: 996 bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) { 997 if (tl != NULL) { 998 if (do_tree(tl->left())) return true; 999 if (do_list(tl)) return true; 1000 if (do_tree(tl->right())) return true; 1001 } 1002 return false; 1003 } 1004 }; 1005 #endif 1006 1007 template <class Chunk_t, class FreeList_t> 1008 class DescendTreeSearchClosure : public TreeSearchClosure<Chunk_t, FreeList_t> { 1009 public: 1010 bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) { 1011 if (tl != NULL) { 1012 if (do_tree(tl->right())) return true; 1013 if (this->do_list(tl)) return true; 1014 if (do_tree(tl->left())) return true; 1015 } 1016 return false; 1017 } 1018 }; 1019 1020 // Searches the tree for a chunk that ends at the 1021 // specified address. 1022 template <class Chunk_t, class FreeList_t> 1023 class EndTreeSearchClosure : public DescendTreeSearchClosure<Chunk_t, FreeList_t> { 1024 HeapWord* _target; 1025 Chunk_t* _found; 1026 1027 public: 1028 EndTreeSearchClosure(HeapWord* target) : _target(target), _found(NULL) {} 1029 bool do_list(FreeList_t* fl) { 1030 Chunk_t* item = fl->head(); 1031 while (item != NULL) { 1032 if (item->end() == (uintptr_t*) _target) { 1033 _found = item; 1034 return true; 1035 } 1036 item = item->next(); 1037 } 1038 return false; 1039 } 1040 Chunk_t* found() { return _found; } 1041 }; 1042 1043 template <class Chunk_t, class FreeList_t> 1044 Chunk_t* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_chunk_ends_at(HeapWord* target) const { 1045 EndTreeSearchClosure<Chunk_t, FreeList_t> etsc(target); 1046 bool found_target = etsc.do_tree(root()); 1047 assert(found_target || etsc.found() == NULL, "Consistency check"); 1048 assert(!found_target || etsc.found() != NULL, "Consistency check"); 1049 return etsc.found(); 1050 } 1051 1052 template <class Chunk_t, class FreeList_t> 1053 void BinaryTreeDictionary<Chunk_t, FreeList_t>::begin_sweep_dict_census(double coalSurplusPercent, 1054 float inter_sweep_current, float inter_sweep_estimate, float intra_sweep_estimate) { 1055 BeginSweepClosure<Chunk_t, FreeList_t> bsc(coalSurplusPercent, inter_sweep_current, 1056 inter_sweep_estimate, 1057 intra_sweep_estimate); 1058 bsc.do_tree(root()); 1059 } 1060 1061 // Closures and methods for calculating total bytes returned to the 1062 // free lists in the tree. 1063 #ifndef PRODUCT 1064 template <class Chunk_t, class FreeList_t> 1065 class InitializeDictReturnedBytesClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { 1066 public: 1067 void do_list(FreeList_t* fl) { 1068 fl->set_returned_bytes(0); 1069 } 1070 }; 1071 1072 template <class Chunk_t, class FreeList_t> 1073 void BinaryTreeDictionary<Chunk_t, FreeList_t>::initialize_dict_returned_bytes() { 1074 InitializeDictReturnedBytesClosure<Chunk_t, FreeList_t> idrb; 1075 idrb.do_tree(root()); 1076 } 1077 1078 template <class Chunk_t, class FreeList_t> 1079 class ReturnedBytesClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { 1080 size_t _dict_returned_bytes; 1081 public: 1082 ReturnedBytesClosure() { _dict_returned_bytes = 0; } 1083 void do_list(FreeList_t* fl) { 1084 _dict_returned_bytes += fl->returned_bytes(); 1085 } 1086 size_t dict_returned_bytes() { return _dict_returned_bytes; } 1087 }; 1088 1089 template <class Chunk_t, class FreeList_t> 1090 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::sum_dict_returned_bytes() { 1091 ReturnedBytesClosure<Chunk_t, FreeList_t> rbc; 1092 rbc.do_tree(root()); 1093 1094 return rbc.dict_returned_bytes(); 1095 } 1096 1097 // Count the number of entries in the tree. 1098 template <class Chunk_t, class FreeList_t> 1099 class treeCountClosure : public DescendTreeCensusClosure<Chunk_t, FreeList_t> { 1100 public: 1101 uint count; 1102 treeCountClosure(uint c) { count = c; } 1103 void do_list(FreeList_t* fl) { 1104 count++; 1105 } 1106 }; 1107 1108 template <class Chunk_t, class FreeList_t> 1109 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_count() { 1110 treeCountClosure<Chunk_t, FreeList_t> ctc(0); 1111 ctc.do_tree(root()); 1112 return ctc.count; 1113 } 1114 #endif // PRODUCT 1115 1116 // Calculate surpluses for the lists in the tree. 1117 template <class Chunk_t, class FreeList_t> 1118 class setTreeSurplusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { 1119 double percentage; 1120 public: 1121 setTreeSurplusClosure(double v) { percentage = v; } 1122 void do_list(FreeList<Chunk_t>* fl) {} 1123 1124 #if INCLUDE_ALL_GCS 1125 void do_list(AdaptiveFreeList<Chunk_t>* fl) { 1126 double splitSurplusPercent = percentage; 1127 fl->set_surplus(fl->count() - 1128 (ssize_t)((double)fl->desired() * splitSurplusPercent)); 1129 } 1130 #endif // INCLUDE_ALL_GCS 1131 }; 1132 1133 template <class Chunk_t, class FreeList_t> 1134 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_surplus(double splitSurplusPercent) { 1135 setTreeSurplusClosure<Chunk_t, FreeList_t> sts(splitSurplusPercent); 1136 sts.do_tree(root()); 1137 } 1138 1139 // Set hints for the lists in the tree. 1140 template <class Chunk_t, class FreeList_t> 1141 class setTreeHintsClosure : public DescendTreeCensusClosure<Chunk_t, FreeList_t> { 1142 size_t hint; 1143 public: 1144 setTreeHintsClosure(size_t v) { hint = v; } 1145 void do_list(FreeList<Chunk_t>* fl) {} 1146 1147 #if INCLUDE_ALL_GCS 1148 void do_list(AdaptiveFreeList<Chunk_t>* fl) { 1149 fl->set_hint(hint); 1150 assert(fl->hint() == 0 || fl->hint() > fl->size(), 1151 "Current hint is inconsistent"); 1152 if (fl->surplus() > 0) { 1153 hint = fl->size(); 1154 } 1155 } 1156 #endif // INCLUDE_ALL_GCS 1157 }; 1158 1159 template <class Chunk_t, class FreeList_t> 1160 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_hints(void) { 1161 setTreeHintsClosure<Chunk_t, FreeList_t> sth(0); 1162 sth.do_tree(root()); 1163 } 1164 1165 // Save count before previous sweep and splits and coalesces. 1166 template <class Chunk_t, class FreeList_t> 1167 class clearTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { 1168 void do_list(FreeList<Chunk_t>* fl) {} 1169 1170 #if INCLUDE_ALL_GCS 1171 void do_list(AdaptiveFreeList<Chunk_t>* fl) { 1172 fl->set_prev_sweep(fl->count()); 1173 fl->set_coal_births(0); 1174 fl->set_coal_deaths(0); 1175 fl->set_split_births(0); 1176 fl->set_split_deaths(0); 1177 } 1178 #endif // INCLUDE_ALL_GCS 1179 }; 1180 1181 template <class Chunk_t, class FreeList_t> 1182 void BinaryTreeDictionary<Chunk_t, FreeList_t>::clear_tree_census(void) { 1183 clearTreeCensusClosure<Chunk_t, FreeList_t> ctc; 1184 ctc.do_tree(root()); 1185 } 1186 1187 // Do reporting and post sweep clean up. 1188 template <class Chunk_t, class FreeList_t> 1189 void BinaryTreeDictionary<Chunk_t, FreeList_t>::end_sweep_dict_census(double splitSurplusPercent) { 1190 // Does walking the tree 3 times hurt? 1191 set_tree_surplus(splitSurplusPercent); 1192 set_tree_hints(); 1193 LogHandle(gc, freelist, stats) log; 1194 if (log.is_trace()) { 1195 ResourceMark rm; 1196 report_statistics(log.trace_stream()); 1197 } 1198 clear_tree_census(); 1199 } 1200 1201 // Print summary statistics 1202 template <class Chunk_t, class FreeList_t> 1203 void BinaryTreeDictionary<Chunk_t, FreeList_t>::report_statistics(outputStream* st) const { 1204 FreeBlockDictionary<Chunk_t>::verify_par_locked(); 1205 st->print_cr("Statistics for BinaryTreeDictionary:"); 1206 st->print_cr("------------------------------------"); 1207 size_t total_size = total_chunk_size(debug_only(NULL)); 1208 size_t free_blocks = num_free_blocks(); 1209 st->print_cr("Total Free Space: " SIZE_FORMAT, total_size); 1210 st->print_cr("Max Chunk Size: " SIZE_FORMAT, max_chunk_size()); 1211 st->print_cr("Number of Blocks: " SIZE_FORMAT, free_blocks); 1212 if (free_blocks > 0) { 1213 st->print_cr("Av. Block Size: " SIZE_FORMAT, total_size/free_blocks); 1214 } 1215 st->print_cr("Tree Height: " SIZE_FORMAT, tree_height()); 1216 } 1217 1218 // Print census information - counts, births, deaths, etc. 1219 // for each list in the tree. Also print some summary 1220 // information. 1221 template <class Chunk_t, class FreeList_t> 1222 class PrintTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { 1223 int _print_line; 1224 size_t _total_free; 1225 FreeList_t _total; 1226 1227 public: 1228 PrintTreeCensusClosure() { 1229 _print_line = 0; 1230 _total_free = 0; 1231 } 1232 FreeList_t* total() { return &_total; } 1233 size_t total_free() { return _total_free; } 1234 void do_list(FreeList<Chunk_t>* fl) { 1235 LogHandle(gc, freelist, census) log; 1236 outputStream* out = log.debug_stream(); 1237 if (++_print_line >= 40) { 1238 ResourceMark rm; 1239 FreeList_t::print_labels_on(out, "size"); 1240 _print_line = 0; 1241 } 1242 fl->print_on(out); 1243 _total_free += fl->count() * fl->size(); 1244 total()->set_count(total()->count() + fl->count()); 1245 } 1246 1247 #if INCLUDE_ALL_GCS 1248 void do_list(AdaptiveFreeList<Chunk_t>* fl) { 1249 LogHandle(gc, freelist, census) log; 1250 outputStream* out = log.debug_stream(); 1251 if (++_print_line >= 40) { 1252 FreeList_t::print_labels_on(out, "size"); 1253 _print_line = 0; 1254 } 1255 fl->print_on(out); 1256 _total_free += fl->count() * fl->size() ; 1257 total()->set_count( total()->count() + fl->count() ); 1258 total()->set_bfr_surp( total()->bfr_surp() + fl->bfr_surp() ); 1259 total()->set_surplus( total()->split_deaths() + fl->surplus() ); 1260 total()->set_desired( total()->desired() + fl->desired() ); 1261 total()->set_prev_sweep( total()->prev_sweep() + fl->prev_sweep() ); 1262 total()->set_before_sweep(total()->before_sweep() + fl->before_sweep()); 1263 total()->set_coal_births( total()->coal_births() + fl->coal_births() ); 1264 total()->set_coal_deaths( total()->coal_deaths() + fl->coal_deaths() ); 1265 total()->set_split_births(total()->split_births() + fl->split_births()); 1266 total()->set_split_deaths(total()->split_deaths() + fl->split_deaths()); 1267 } 1268 #endif // INCLUDE_ALL_GCS 1269 }; 1270 1271 template <class Chunk_t, class FreeList_t> 1272 void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_dict_census(outputStream* st) const { 1273 1274 st->print("BinaryTree"); 1275 FreeList_t::print_labels_on(st, "size"); 1276 PrintTreeCensusClosure<Chunk_t, FreeList_t> ptc; 1277 ptc.do_tree(root()); 1278 1279 FreeList_t* total = ptc.total(); 1280 FreeList_t::print_labels_on(st, " "); 1281 } 1282 1283 #if INCLUDE_ALL_GCS 1284 template <> 1285 void AFLBinaryTreeDictionary::print_dict_census(outputStream* st) const { 1286 1287 st->print_cr("BinaryTree"); 1288 AdaptiveFreeList<FreeChunk>::print_labels_on(st, "size"); 1289 PrintTreeCensusClosure<FreeChunk, AdaptiveFreeList<FreeChunk> > ptc; 1290 ptc.do_tree(root()); 1291 1292 AdaptiveFreeList<FreeChunk>* total = ptc.total(); 1293 AdaptiveFreeList<FreeChunk>::print_labels_on(st, " "); 1294 total->print_on(st, "TOTAL\t"); 1295 st->print_cr("total_free(words): " SIZE_FORMAT_W(16) " growth: %8.5f deficit: %8.5f", 1296 ptc.total_free(), 1297 (double)(total->split_births() + total->coal_births() 1298 - total->split_deaths() - total->coal_deaths()) 1299 /(total->prev_sweep() != 0 ? (double)total->prev_sweep() : 1.0), 1300 (double)(total->desired() - total->count()) 1301 /(total->desired() != 0 ? (double)total->desired() : 1.0)); 1302 } 1303 #endif // INCLUDE_ALL_GCS 1304 1305 template <class Chunk_t, class FreeList_t> 1306 class PrintFreeListsClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { 1307 outputStream* _st; 1308 int _print_line; 1309 1310 public: 1311 PrintFreeListsClosure(outputStream* st) { 1312 _st = st; 1313 _print_line = 0; 1314 } 1315 void do_list(FreeList_t* fl) { 1316 if (++_print_line >= 40) { 1317 FreeList_t::print_labels_on(_st, "size"); 1318 _print_line = 0; 1319 } 1320 fl->print_on(_st); 1321 size_t sz = fl->size(); 1322 for (Chunk_t* fc = fl->head(); fc != NULL; 1323 fc = fc->next()) { 1324 _st->print_cr("\t[" PTR_FORMAT "," PTR_FORMAT ") %s", 1325 p2i(fc), p2i((HeapWord*)fc + sz), 1326 fc->cantCoalesce() ? "\t CC" : ""); 1327 } 1328 } 1329 }; 1330 1331 template <class Chunk_t, class FreeList_t> 1332 void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_free_lists(outputStream* st) const { 1333 1334 FreeList_t::print_labels_on(st, "size"); 1335 PrintFreeListsClosure<Chunk_t, FreeList_t> pflc(st); 1336 pflc.do_tree(root()); 1337 } 1338 1339 // Verify the following tree invariants: 1340 // . _root has no parent 1341 // . parent and child point to each other 1342 // . each node's key correctly related to that of its child(ren) 1343 template <class Chunk_t, class FreeList_t> 1344 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_tree() const { 1345 guarantee(root() == NULL || total_free_blocks() == 0 || 1346 total_size() != 0, "_total_size shouldn't be 0?"); 1347 guarantee(root() == NULL || root()->parent() == NULL, "_root shouldn't have parent"); 1348 verify_tree_helper(root()); 1349 } 1350 1351 template <class Chunk_t, class FreeList_t> 1352 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_prev_free_ptrs(TreeList<Chunk_t, FreeList_t>* tl) { 1353 size_t ct = 0; 1354 for (Chunk_t* curFC = tl->head(); curFC != NULL; curFC = curFC->next()) { 1355 ct++; 1356 assert(curFC->prev() == NULL || curFC->prev()->is_free(), 1357 "Chunk should be free"); 1358 } 1359 return ct; 1360 } 1361 1362 // Note: this helper is recursive rather than iterative, so use with 1363 // caution on very deep trees; and watch out for stack overflow errors; 1364 // In general, to be used only for debugging. 1365 template <class Chunk_t, class FreeList_t> 1366 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_tree_helper(TreeList<Chunk_t, FreeList_t>* tl) const { 1367 if (tl == NULL) 1368 return; 1369 guarantee(tl->size() != 0, "A list must has a size"); 1370 guarantee(tl->left() == NULL || tl->left()->parent() == tl, 1371 "parent<-/->left"); 1372 guarantee(tl->right() == NULL || tl->right()->parent() == tl, 1373 "parent<-/->right");; 1374 guarantee(tl->left() == NULL || tl->left()->size() < tl->size(), 1375 "parent !> left"); 1376 guarantee(tl->right() == NULL || tl->right()->size() > tl->size(), 1377 "parent !< left"); 1378 guarantee(tl->head() == NULL || tl->head()->is_free(), "!Free"); 1379 guarantee(tl->head() == NULL || tl->head_as_TreeChunk()->list() == tl, 1380 "list inconsistency"); 1381 guarantee(tl->count() > 0 || (tl->head() == NULL && tl->tail() == NULL), 1382 "list count is inconsistent"); 1383 guarantee(tl->count() > 1 || tl->head() == tl->tail(), 1384 "list is incorrectly constructed"); 1385 size_t count = verify_prev_free_ptrs(tl); 1386 guarantee(count == (size_t)tl->count(), "Node count is incorrect"); 1387 if (tl->head() != NULL) { 1388 tl->head_as_TreeChunk()->verify_tree_chunk_list(); 1389 } 1390 verify_tree_helper(tl->left()); 1391 verify_tree_helper(tl->right()); 1392 } 1393 1394 template <class Chunk_t, class FreeList_t> 1395 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify() const { 1396 verify_tree(); 1397 guarantee(total_size() == total_size_in_tree(root()), "Total Size inconsistency"); 1398 } 1399 1400 template class TreeList<Metablock, FreeList<Metablock> >; 1401 template class BinaryTreeDictionary<Metablock, FreeList<Metablock> >; 1402 template class TreeChunk<Metablock, FreeList<Metablock> >; 1403 1404 template class TreeList<Metachunk, FreeList<Metachunk> >; 1405 template class BinaryTreeDictionary<Metachunk, FreeList<Metachunk> >; 1406 template class TreeChunk<Metachunk, FreeList<Metachunk> >; 1407 1408 1409 #if INCLUDE_ALL_GCS 1410 // Explicitly instantiate these types for FreeChunk. 1411 template class TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >; 1412 template class BinaryTreeDictionary<FreeChunk, AdaptiveFreeList<FreeChunk> >; 1413 template class TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >; 1414 1415 #endif // INCLUDE_ALL_GCS