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