1 /*

     2  * Copyright (c) 2001, 2010, 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_implementation/concurrentMarkSweep/binaryTreeDictionary.hpp"

    27 #include "gc_implementation/shared/allocationStats.hpp"

    28 #include "gc_implementation/shared/spaceDecorator.hpp"

    29 #include "memory/space.inline.hpp"

    30 #include "runtime/globals.hpp"

    31 #include "utilities/ostream.hpp"

    32 

    33 ////////////////////////////////////////////////////////////////////////////////

    34 // A binary tree based search structure for free blocks.

    35 // This is currently used in the Concurrent Mark&Sweep implementation.

    36 ////////////////////////////////////////////////////////////////////////////////

    37 

    38 TreeChunk* TreeChunk::as_TreeChunk(FreeChunk* fc) {

    39   // Do some assertion checking here.

    40   return (TreeChunk*) fc;

    41 }

    42 

    43 void TreeChunk::verifyTreeChunkList() const {

    44   TreeChunk* nextTC = (TreeChunk*)next();

    45   if (prev() != NULL) { // interior list node shouldn'r have tree fields

    46     guarantee(embedded_list()->parent() == NULL && embedded_list()->left() == NULL &&

    47               embedded_list()->right()  == NULL, "should be clear");

    48   }

    49   if (nextTC != NULL) {

    50     guarantee(as_TreeChunk(nextTC->prev()) == this, "broken chain");

    51     guarantee(nextTC->size() == size(), "wrong size");

    52     nextTC->verifyTreeChunkList();

    53   }

    54 }

    55 

    56 

    57 TreeList* TreeList::as_TreeList(TreeChunk* tc) {

    58   // This first free chunk in the list will be the tree list.

    59   assert(tc->size() >= sizeof(TreeChunk), "Chunk is too small for a TreeChunk");

    60   TreeList* tl = tc->embedded_list();

    61   tc->set_list(tl);

    62 #ifdef ASSERT

    63   tl->set_protecting_lock(NULL);

    64 #endif

    65   tl->set_hint(0);

    66   tl->set_size(tc->size());

    67   tl->link_head(tc);

    68   tl->link_tail(tc);

    69   tl->set_count(1);

    70   tl->init_statistics(true /* split_birth */);

    71   tl->setParent(NULL);

    72   tl->setLeft(NULL);

    73   tl->setRight(NULL);

    74   return tl;

    75 }

    76 

    77 TreeList* TreeList::as_TreeList(HeapWord* addr, size_t size) {

    78   TreeChunk* tc = (TreeChunk*) addr;

    79   assert(size >= sizeof(TreeChunk), "Chunk is too small for a TreeChunk");

    80   // The space in the heap will have been mangled initially but

    81   // is not remangled when a free chunk is returned to the free list

    82   // (since it is used to maintain the chunk on the free list).

    83   assert((ZapUnusedHeapArea &&

    84           SpaceMangler::is_mangled((HeapWord*) tc->size_addr()) &&

    85           SpaceMangler::is_mangled((HeapWord*) tc->prev_addr()) &&

    86           SpaceMangler::is_mangled((HeapWord*) tc->next_addr())) ||

    87           (tc->size() == 0 && tc->prev() == NULL && tc->next() == NULL),

    88     "Space should be clear or mangled");

    89   tc->setSize(size);

    90   tc->linkPrev(NULL);

    91   tc->linkNext(NULL);

    92   TreeList* tl = TreeList::as_TreeList(tc);

    93   return tl;

    94 }

    95 

    96 TreeList* TreeList::removeChunkReplaceIfNeeded(TreeChunk* tc) {

    97 

    98   TreeList* retTL = this;

    99   FreeChunk* list = head();

   100   assert(!list || list != list->next(), "Chunk on list twice");

   101   assert(tc != NULL, "Chunk being removed is NULL");

   102   assert(parent() == NULL || this == parent()->left() ||

   103     this == parent()->right(), "list is inconsistent");

   104   assert(tc->isFree(), "Header is not marked correctly");

   105   assert(head() == NULL || head()->prev() == NULL, "list invariant");

   106   assert(tail() == NULL || tail()->next() == NULL, "list invariant");

   107 

   108   FreeChunk* prevFC = tc->prev();

   109   TreeChunk* nextTC = TreeChunk::as_TreeChunk(tc->next());

   110   assert(list != NULL, "should have at least the target chunk");

   111 

   112   // Is this the first item on the list?

   113   if (tc == list) {

   114     // The "getChunk..." functions for a TreeList will not return the

   115     // first chunk in the list unless it is the last chunk in the list

   116     // because the first chunk is also acting as the tree node.

   117     // When coalescing happens, however, the first chunk in the a tree

   118     // list can be the start of a free range.  Free ranges are removed

   119     // from the free lists so that they are not available to be

   120     // allocated when the sweeper yields (giving up the free list lock)

   121     // to allow mutator activity.  If this chunk is the first in the

   122     // list and is not the last in the list, do the work to copy the

   123     // TreeList from the first chunk to the next chunk and update all

   124     // the TreeList pointers in the chunks in the list.

   125     if (nextTC == NULL) {

   126       assert(prevFC == NULL, "Not last chunk in the list");

   127       set_tail(NULL);

   128       set_head(NULL);

   129     } else {

   130       // copy embedded list.

   131       nextTC->set_embedded_list(tc->embedded_list());

   132       retTL = nextTC->embedded_list();

   133       // Fix the pointer to the list in each chunk in the list.

   134       // This can be slow for a long list.  Consider having

   135       // an option that does not allow the first chunk on the

   136       // list to be coalesced.

   137       for (TreeChunk* curTC = nextTC; curTC != NULL;

   138           curTC = TreeChunk::as_TreeChunk(curTC->next())) {

   139         curTC->set_list(retTL);

   140       }

   141       // Fix the parent to point to the new TreeList.

   142       if (retTL->parent() != NULL) {

   143         if (this == retTL->parent()->left()) {

   144           retTL->parent()->setLeft(retTL);

   145         } else {

   146           assert(this == retTL->parent()->right(), "Parent is incorrect");

   147           retTL->parent()->setRight(retTL);

   148         }

   149       }

   150       // Fix the children's parent pointers to point to the

   151       // new list.

   152       assert(right() == retTL->right(), "Should have been copied");

   153       if (retTL->right() != NULL) {

   154         retTL->right()->setParent(retTL);

   155       }

   156       assert(left() == retTL->left(), "Should have been copied");

   157       if (retTL->left() != NULL) {

   158         retTL->left()->setParent(retTL);

   159       }

   160       retTL->link_head(nextTC);

   161       assert(nextTC->isFree(), "Should be a free chunk");

   162     }

   163   } else {

   164     if (nextTC == NULL) {

   165       // Removing chunk at tail of list

   166       link_tail(prevFC);

   167     }

   168     // Chunk is interior to the list

   169     prevFC->linkAfter(nextTC);

   170   }

   171 

   172   // Below this point the embeded TreeList being used for the

   173   // tree node may have changed. Don't use "this"

   174   // TreeList*.

   175   // chunk should still be a free chunk (bit set in _prev)

   176   assert(!retTL->head() || retTL->size() == retTL->head()->size(),

   177     "Wrong sized chunk in list");

   178   debug_only(

   179     tc->linkPrev(NULL);

   180     tc->linkNext(NULL);

   181     tc->set_list(NULL);

   182     bool prev_found = false;

   183     bool next_found = false;

   184     for (FreeChunk* curFC = retTL->head();

   185          curFC != NULL; curFC = curFC->next()) {

   186       assert(curFC != tc, "Chunk is still in list");

   187       if (curFC == prevFC) {

   188         prev_found = true;

   189       }

   190       if (curFC == nextTC) {

   191         next_found = true;

   192       }

   193     }

   194     assert(prevFC == NULL || prev_found, "Chunk was lost from list");

   195     assert(nextTC == NULL || next_found, "Chunk was lost from list");

   196     assert(retTL->parent() == NULL ||

   197            retTL == retTL->parent()->left() ||

   198            retTL == retTL->parent()->right(),

   199            "list is inconsistent");

   200   )

   201   retTL->decrement_count();

   202 

   203   assert(tc->isFree(), "Should still be a free chunk");

   204   assert(retTL->head() == NULL || retTL->head()->prev() == NULL,

   205     "list invariant");

   206   assert(retTL->tail() == NULL || retTL->tail()->next() == NULL,

   207     "list invariant");

   208   return retTL;

   209 }

   210 void TreeList::returnChunkAtTail(TreeChunk* chunk) {

   211   assert(chunk != NULL, "returning NULL chunk");

   212   assert(chunk->list() == this, "list should be set for chunk");

   213   assert(tail() != NULL, "The tree list is embedded in the first chunk");

   214   // which means that the list can never be empty.

   215   assert(!verifyChunkInFreeLists(chunk), "Double entry");

   216   assert(head() == NULL || head()->prev() == NULL, "list invariant");

   217   assert(tail() == NULL || tail()->next() == NULL, "list invariant");

   218 

   219   FreeChunk* fc = tail();

   220   fc->linkAfter(chunk);

   221   link_tail(chunk);

   222 

   223   assert(!tail() || size() == tail()->size(), "Wrong sized chunk in list");

   224   increment_count();

   225   debug_only(increment_returnedBytes_by(chunk->size()*sizeof(HeapWord));)

   226   assert(head() == NULL || head()->prev() == NULL, "list invariant");

   227   assert(tail() == NULL || tail()->next() == NULL, "list invariant");

   228 }

   229 

   230 // Add this chunk at the head of the list.  "At the head of the list"

   231 // is defined to be after the chunk pointer to by head().  This is

   232 // because the TreeList is embedded in the first TreeChunk in the

   233 // list.  See the definition of TreeChunk.

   234 void TreeList::returnChunkAtHead(TreeChunk* chunk) {

   235   assert(chunk->list() == this, "list should be set for chunk");

   236   assert(head() != NULL, "The tree list is embedded in the first chunk");

   237   assert(chunk != NULL, "returning NULL chunk");

   238   assert(!verifyChunkInFreeLists(chunk), "Double entry");

   239   assert(head() == NULL || head()->prev() == NULL, "list invariant");

   240   assert(tail() == NULL || tail()->next() == NULL, "list invariant");

   241 

   242   FreeChunk* fc = head()->next();

   243   if (fc != NULL) {

   244     chunk->linkAfter(fc);

   245   } else {

   246     assert(tail() == NULL, "List is inconsistent");

   247     link_tail(chunk);

   248   }

   249   head()->linkAfter(chunk);

   250   assert(!head() || size() == head()->size(), "Wrong sized chunk in list");

   251   increment_count();

   252   debug_only(increment_returnedBytes_by(chunk->size()*sizeof(HeapWord));)

   253   assert(head() == NULL || head()->prev() == NULL, "list invariant");

   254   assert(tail() == NULL || tail()->next() == NULL, "list invariant");

   255 }

   256 

   257 TreeChunk* TreeList::head_as_TreeChunk() {

   258   assert(head() == NULL || TreeChunk::as_TreeChunk(head())->list() == this,

   259     "Wrong type of chunk?");

   260   return TreeChunk::as_TreeChunk(head());

   261 }

   262 

   263 TreeChunk* TreeList::first_available() {

   264   assert(head() != NULL, "The head of the list cannot be NULL");

   265   FreeChunk* fc = head()->next();

   266   TreeChunk* retTC;

   267   if (fc == NULL) {

   268     retTC = head_as_TreeChunk();

   269   } else {

   270     retTC = TreeChunk::as_TreeChunk(fc);

   271   }

   272   assert(retTC->list() == this, "Wrong type of chunk.");

   273   return retTC;

   274 }

   275 

   276 // Returns the block with the largest heap address amongst

   277 // those in the list for this size; potentially slow and expensive,

   278 // use with caution!

   279 TreeChunk* TreeList::largest_address() {

   280   assert(head() != NULL, "The head of the list cannot be NULL");

   281   FreeChunk* fc = head()->next();

   282   TreeChunk* retTC;

   283   if (fc == NULL) {

   284     retTC = head_as_TreeChunk();

   285   } else {

   286     // walk down the list and return the one with the highest

   287     // heap address among chunks of this size.

   288     FreeChunk* last = fc;

   289     while (fc->next() != NULL) {

   290       if ((HeapWord*)last < (HeapWord*)fc) {

   291         last = fc;

   292       }

   293       fc = fc->next();

   294     }

   295     retTC = TreeChunk::as_TreeChunk(last);

   296   }

   297   assert(retTC->list() == this, "Wrong type of chunk.");

   298   return retTC;

   299 }

   300 

   301 BinaryTreeDictionary::BinaryTreeDictionary(MemRegion mr, bool splay):

   302   _splay(splay)

   303 {

   304   assert(mr.byte_size() > MIN_TREE_CHUNK_SIZE, "minimum chunk size");

   305 

   306   reset(mr);

   307   assert(root()->left() == NULL, "reset check failed");

   308   assert(root()->right() == NULL, "reset check failed");

   309   assert(root()->head()->next() == NULL, "reset check failed");

   310   assert(root()->head()->prev() == NULL, "reset check failed");

   311   assert(totalSize() == root()->size(), "reset check failed");

   312   assert(totalFreeBlocks() == 1, "reset check failed");

   313 }

   314 

   315 void BinaryTreeDictionary::inc_totalSize(size_t inc) {

   316   _totalSize = _totalSize + inc;

   317 }

   318 

   319 void BinaryTreeDictionary::dec_totalSize(size_t dec) {

   320   _totalSize = _totalSize - dec;

   321 }

   322 

   323 void BinaryTreeDictionary::reset(MemRegion mr) {

   324   assert(mr.byte_size() > MIN_TREE_CHUNK_SIZE, "minimum chunk size");

   325   set_root(TreeList::as_TreeList(mr.start(), mr.word_size()));

   326   set_totalSize(mr.word_size());

   327   set_totalFreeBlocks(1);

   328 }

   329 

   330 void BinaryTreeDictionary::reset(HeapWord* addr, size_t byte_size) {

   331   MemRegion mr(addr, heap_word_size(byte_size));

   332   reset(mr);

   333 }

   334 

   335 void BinaryTreeDictionary::reset() {

   336   set_root(NULL);

   337   set_totalSize(0);

   338   set_totalFreeBlocks(0);

   339 }

   340 

   341 // Get a free block of size at least size from tree, or NULL.

   342 // If a splay step is requested, the removal algorithm (only) incorporates

   343 // a splay step as follows:

   344 // . the search proceeds down the tree looking for a possible

   345 //   match. At the (closest) matching location, an appropriate splay step is applied

   346 //   (zig, zig-zig or zig-zag). A chunk of the appropriate size is then returned

   347 //   if available, and if it's the last chunk, the node is deleted. A deteleted

   348 //   node is replaced in place by its tree successor.

   349 TreeChunk*

   350 BinaryTreeDictionary::getChunkFromTree(size_t size, Dither dither, bool splay)

   351 {

   352   TreeList *curTL, *prevTL;

   353   TreeChunk* retTC = NULL;

   354   assert(size >= MIN_TREE_CHUNK_SIZE, "minimum chunk size");

   355   if (FLSVerifyDictionary) {

   356     verifyTree();

   357   }

   358   // starting at the root, work downwards trying to find match.

   359   // Remember the last node of size too great or too small.

   360   for (prevTL = curTL = root(); curTL != NULL;) {

   361     if (curTL->size() == size) {        // exact match

   362       break;

   363     }

   364     prevTL = curTL;

   365     if (curTL->size() < size) {        // proceed to right sub-tree

   366       curTL = curTL->right();

   367     } else {                           // proceed to left sub-tree

   368       assert(curTL->size() > size, "size inconsistency");

   369       curTL = curTL->left();

   370     }

   371   }

   372   if (curTL == NULL) { // couldn't find exact match

   373     // try and find the next larger size by walking back up the search path

   374     for (curTL = prevTL; curTL != NULL;) {

   375       if (curTL->size() >= size) break;

   376       else curTL = curTL->parent();

   377     }

   378     assert(curTL == NULL || curTL->count() > 0,

   379       "An empty list should not be in the tree");

   380   }

   381   if (curTL != NULL) {

   382     assert(curTL->size() >= size, "size inconsistency");

   383     if (UseCMSAdaptiveFreeLists) {

   384 

   385       // A candidate chunk has been found.  If it is already under

   386       // populated, get a chunk associated with the hint for this

   387       // chunk.

   388       if (curTL->surplus() <= 0) {

   389         /* Use the hint to find a size with a surplus, and reset the hint. */

   390         TreeList* hintTL = curTL;

   391         while (hintTL->hint() != 0) {

   392           assert(hintTL->hint() == 0 || hintTL->hint() > hintTL->size(),

   393             "hint points in the wrong direction");

   394           hintTL = findList(hintTL->hint());

   395           assert(curTL != hintTL, "Infinite loop");

   396           if (hintTL == NULL ||

   397               hintTL == curTL /* Should not happen but protect against it */ ) {

   398             // No useful hint.  Set the hint to NULL and go on.

   399             curTL->set_hint(0);

   400             break;

   401           }

   402           assert(hintTL->size() > size, "hint is inconsistent");

   403           if (hintTL->surplus() > 0) {

   404             // The hint led to a list that has a surplus.  Use it.

   405             // Set the hint for the candidate to an overpopulated

   406             // size.

   407             curTL->set_hint(hintTL->size());

   408             // Change the candidate.

   409             curTL = hintTL;

   410             break;

   411           }

   412           // The evm code reset the hint of the candidate as

   413           // at an interim point.  Why?  Seems like this leaves

   414           // the hint pointing to a list that didn't work.

   415           // curTL->set_hint(hintTL->size());

   416         }

   417       }

   418     }

   419     // don't waste time splaying if chunk's singleton

   420     if (splay && curTL->head()->next() != NULL) {

   421       semiSplayStep(curTL);

   422     }

   423     retTC = curTL->first_available();

   424     assert((retTC != NULL) && (curTL->count() > 0),

   425       "A list in the binary tree should not be NULL");

   426     assert(retTC->size() >= size,

   427       "A chunk of the wrong size was found");

   428     removeChunkFromTree(retTC);

   429     assert(retTC->isFree(), "Header is not marked correctly");

   430   }

   431 

   432   if (FLSVerifyDictionary) {

   433     verify();

   434   }

   435   return retTC;

   436 }

   437 

   438 TreeList* BinaryTreeDictionary::findList(size_t size) const {

   439   TreeList* curTL;

   440   for (curTL = root(); curTL != NULL;) {

   441     if (curTL->size() == size) {        // exact match

   442       break;

   443     }

   444 

   445     if (curTL->size() < size) {        // proceed to right sub-tree

   446       curTL = curTL->right();

   447     } else {                           // proceed to left sub-tree

   448       assert(curTL->size() > size, "size inconsistency");

   449       curTL = curTL->left();

   450     }

   451   }

   452   return curTL;

   453 }

   454 

   455 

   456 bool BinaryTreeDictionary::verifyChunkInFreeLists(FreeChunk* tc) const {

   457   size_t size = tc->size();

   458   TreeList* tl = findList(size);

   459   if (tl == NULL) {

   460     return false;

   461   } else {

   462     return tl->verifyChunkInFreeLists(tc);

   463   }

   464 }

   465 

   466 FreeChunk* BinaryTreeDictionary::findLargestDict() const {

   467   TreeList *curTL = root();

   468   if (curTL != NULL) {

   469     while(curTL->right() != NULL) curTL = curTL->right();

   470     return curTL->largest_address();

   471   } else {

   472     return NULL;

   473   }

   474 }

   475 

   476 // Remove the current chunk from the tree.  If it is not the last

   477 // chunk in a list on a tree node, just unlink it.

   478 // If it is the last chunk in the list (the next link is NULL),

   479 // remove the node and repair the tree.

   480 TreeChunk*

   481 BinaryTreeDictionary::removeChunkFromTree(TreeChunk* tc) {

   482   assert(tc != NULL, "Should not call with a NULL chunk");

   483   assert(tc->isFree(), "Header is not marked correctly");

   484 

   485   TreeList *newTL, *parentTL;

   486   TreeChunk* retTC;

   487   TreeList* tl = tc->list();

   488   debug_only(

   489     bool removing_only_chunk = false;

   490     if (tl == _root) {

   491       if ((_root->left() == NULL) && (_root->right() == NULL)) {

   492         if (_root->count() == 1) {

   493           assert(_root->head() == tc, "Should only be this one chunk");

   494           removing_only_chunk = true;

   495         }

   496       }

   497     }

   498   )

   499   assert(tl != NULL, "List should be set");

   500   assert(tl->parent() == NULL || tl == tl->parent()->left() ||

   501          tl == tl->parent()->right(), "list is inconsistent");

   502 

   503   bool complicatedSplice = false;

   504 

   505   retTC = tc;

   506   // Removing this chunk can have the side effect of changing the node

   507   // (TreeList*) in the tree.  If the node is the root, update it.

   508   TreeList* replacementTL = tl->removeChunkReplaceIfNeeded(tc);

   509   assert(tc->isFree(), "Chunk should still be free");

   510   assert(replacementTL->parent() == NULL ||

   511          replacementTL == replacementTL->parent()->left() ||

   512          replacementTL == replacementTL->parent()->right(),

   513          "list is inconsistent");

   514   if (tl == root()) {

   515     assert(replacementTL->parent() == NULL, "Incorrectly replacing root");

   516     set_root(replacementTL);

   517   }

   518   debug_only(

   519     if (tl != replacementTL) {

   520       assert(replacementTL->head() != NULL,

   521         "If the tree list was replaced, it should not be a NULL list");

   522       TreeList* rhl = replacementTL->head_as_TreeChunk()->list();

   523       TreeList* rtl = TreeChunk::as_TreeChunk(replacementTL->tail())->list();

   524       assert(rhl == replacementTL, "Broken head");

   525       assert(rtl == replacementTL, "Broken tail");

   526       assert(replacementTL->size() == tc->size(),  "Broken size");

   527     }

   528   )

   529 

   530   // Does the tree need to be repaired?

   531   if (replacementTL->count() == 0) {

   532     assert(replacementTL->head() == NULL &&

   533            replacementTL->tail() == NULL, "list count is incorrect");

   534     // Find the replacement node for the (soon to be empty) node being removed.

   535     // if we have a single (or no) child, splice child in our stead

   536     if (replacementTL->left() == NULL) {

   537       // left is NULL so pick right.  right may also be NULL.

   538       newTL = replacementTL->right();

   539       debug_only(replacementTL->clearRight();)

   540     } else if (replacementTL->right() == NULL) {

   541       // right is NULL

   542       newTL = replacementTL->left();

   543       debug_only(replacementTL->clearLeft();)

   544     } else {  // we have both children, so, by patriarchal convention,

   545               // my replacement is least node in right sub-tree

   546       complicatedSplice = true;

   547       newTL = removeTreeMinimum(replacementTL->right());

   548       assert(newTL != NULL && newTL->left() == NULL &&

   549              newTL->right() == NULL, "sub-tree minimum exists");

   550     }

   551     // newTL is the replacement for the (soon to be empty) node.

   552     // newTL may be NULL.

   553     // should verify; we just cleanly excised our replacement

   554     if (FLSVerifyDictionary) {

   555       verifyTree();

   556     }

   557     // first make newTL my parent's child

   558     if ((parentTL = replacementTL->parent()) == NULL) {

   559       // newTL should be root

   560       assert(tl == root(), "Incorrectly replacing root");

   561       set_root(newTL);

   562       if (newTL != NULL) {

   563         newTL->clearParent();

   564       }

   565     } else if (parentTL->right() == replacementTL) {

   566       // replacementTL is a right child

   567       parentTL->setRight(newTL);

   568     } else {                                // replacementTL is a left child

   569       assert(parentTL->left() == replacementTL, "should be left child");

   570       parentTL->setLeft(newTL);

   571     }

   572     debug_only(replacementTL->clearParent();)

   573     if (complicatedSplice) {  // we need newTL to get replacementTL's

   574                               // two children

   575       assert(newTL != NULL &&

   576              newTL->left() == NULL && newTL->right() == NULL,

   577             "newTL should not have encumbrances from the past");

   578       // we'd like to assert as below:

   579       // assert(replacementTL->left() != NULL && replacementTL->right() != NULL,

   580       //       "else !complicatedSplice");

   581       // ... however, the above assertion is too strong because we aren't

   582       // guaranteed that replacementTL->right() is still NULL.

   583       // Recall that we removed

   584       // the right sub-tree minimum from replacementTL.

   585       // That may well have been its right

   586       // child! So we'll just assert half of the above:

   587       assert(replacementTL->left() != NULL, "else !complicatedSplice");

   588       newTL->setLeft(replacementTL->left());

   589       newTL->setRight(replacementTL->right());

   590       debug_only(

   591         replacementTL->clearRight();

   592         replacementTL->clearLeft();

   593       )

   594     }

   595     assert(replacementTL->right() == NULL &&

   596            replacementTL->left() == NULL &&

   597            replacementTL->parent() == NULL,

   598         "delete without encumbrances");

   599   }

   600 

   601   assert(totalSize() >= retTC->size(), "Incorrect total size");

   602   dec_totalSize(retTC->size());     // size book-keeping

   603   assert(totalFreeBlocks() > 0, "Incorrect total count");

   604   set_totalFreeBlocks(totalFreeBlocks() - 1);

   605 

   606   assert(retTC != NULL, "null chunk?");

   607   assert(retTC->prev() == NULL && retTC->next() == NULL,

   608          "should return without encumbrances");

   609   if (FLSVerifyDictionary) {

   610     verifyTree();

   611   }

   612   assert(!removing_only_chunk || _root == NULL, "root should be NULL");

   613   return TreeChunk::as_TreeChunk(retTC);

   614 }

   615 

   616 // Remove the leftmost node (lm) in the tree and return it.

   617 // If lm has a right child, link it to the left node of

   618 // the parent of lm.

   619 TreeList* BinaryTreeDictionary::removeTreeMinimum(TreeList* tl) {

   620   assert(tl != NULL && tl->parent() != NULL, "really need a proper sub-tree");

   621   // locate the subtree minimum by walking down left branches

   622   TreeList* curTL = tl;

   623   for (; curTL->left() != NULL; curTL = curTL->left());

   624   // obviously curTL now has at most one child, a right child

   625   if (curTL != root()) {  // Should this test just be removed?

   626     TreeList* parentTL = curTL->parent();

   627     if (parentTL->left() == curTL) { // curTL is a left child

   628       parentTL->setLeft(curTL->right());

   629     } else {

   630       // If the list tl has no left child, then curTL may be

   631       // the right child of parentTL.

   632       assert(parentTL->right() == curTL, "should be a right child");

   633       parentTL->setRight(curTL->right());

   634     }

   635   } else {

   636     // The only use of this method would not pass the root of the

   637     // tree (as indicated by the assertion above that the tree list

   638     // has a parent) but the specification does not explicitly exclude the

   639     // passing of the root so accomodate it.

   640     set_root(NULL);

   641   }

   642   debug_only(

   643     curTL->clearParent();  // Test if this needs to be cleared

   644     curTL->clearRight();    // recall, above, left child is already null

   645   )

   646   // we just excised a (non-root) node, we should still verify all tree invariants

   647   if (FLSVerifyDictionary) {

   648     verifyTree();

   649   }

   650   return curTL;

   651 }

   652 

   653 // Based on a simplification of the algorithm by Sleator and Tarjan (JACM 1985).

   654 // The simplifications are the following:

   655 // . we splay only when we delete (not when we insert)

   656 // . we apply a single spay step per deletion/access

   657 // By doing such partial splaying, we reduce the amount of restructuring,

   658 // while getting a reasonably efficient search tree (we think).

   659 // [Measurements will be needed to (in)validate this expectation.]

   660 

   661 void BinaryTreeDictionary::semiSplayStep(TreeList* tc) {

   662   // apply a semi-splay step at the given node:

   663   // . if root, norting needs to be done

   664   // . if child of root, splay once

   665   // . else zig-zig or sig-zag depending on path from grandparent

   666   if (root() == tc) return;

   667   warning("*** Splaying not yet implemented; "

   668           "tree operations may be inefficient ***");

   669 }

   670 

   671 void BinaryTreeDictionary::insertChunkInTree(FreeChunk* fc) {

   672   TreeList *curTL, *prevTL;

   673   size_t size = fc->size();

   674 

   675   assert(size >= MIN_TREE_CHUNK_SIZE, "too small to be a TreeList");

   676   if (FLSVerifyDictionary) {

   677     verifyTree();

   678   }

   679   // XXX: do i need to clear the FreeChunk fields, let me do it just in case

   680   // Revisit this later

   681 

   682   fc->clearNext();

   683   fc->linkPrev(NULL);

   684 

   685   // work down from the _root, looking for insertion point

   686   for (prevTL = curTL = root(); curTL != NULL;) {

   687     if (curTL->size() == size)  // exact match

   688       break;

   689     prevTL = curTL;

   690     if (curTL->size() > size) { // follow left branch

   691       curTL = curTL->left();

   692     } else {                    // follow right branch

   693       assert(curTL->size() < size, "size inconsistency");

   694       curTL = curTL->right();

   695     }

   696   }

   697   TreeChunk* tc = TreeChunk::as_TreeChunk(fc);

   698   // This chunk is being returned to the binary tree.  Its embedded

   699   // TreeList should be unused at this point.

   700   tc->initialize();

   701   if (curTL != NULL) {          // exact match

   702     tc->set_list(curTL);

   703     curTL->returnChunkAtTail(tc);

   704   } else {                     // need a new node in tree

   705     tc->clearNext();

   706     tc->linkPrev(NULL);

   707     TreeList* newTL = TreeList::as_TreeList(tc);

   708     assert(((TreeChunk*)tc)->list() == newTL,

   709       "List was not initialized correctly");

   710     if (prevTL == NULL) {      // we are the only tree node

   711       assert(root() == NULL, "control point invariant");

   712       set_root(newTL);

   713     } else {                   // insert under prevTL ...

   714       if (prevTL->size() < size) {   // am right child

   715         assert(prevTL->right() == NULL, "control point invariant");

   716         prevTL->setRight(newTL);

   717       } else {                       // am left child

   718         assert(prevTL->size() > size && prevTL->left() == NULL, "cpt pt inv");

   719         prevTL->setLeft(newTL);

   720       }

   721     }

   722   }

   723   assert(tc->list() != NULL, "Tree list should be set");

   724 

   725   inc_totalSize(size);

   726   // Method 'totalSizeInTree' walks through the every block in the

   727   // tree, so it can cause significant performance loss if there are

   728   // many blocks in the tree

   729   assert(!FLSVerifyDictionary || totalSizeInTree(root()) == totalSize(), "_totalSize inconsistency");

   730   set_totalFreeBlocks(totalFreeBlocks() + 1);

   731   if (FLSVerifyDictionary) {

   732     verifyTree();

   733   }

   734 }

   735 

   736 size_t BinaryTreeDictionary::maxChunkSize() const {

   737   verify_par_locked();

   738   TreeList* tc = root();

   739   if (tc == NULL) return 0;

   740   for (; tc->right() != NULL; tc = tc->right());

   741   return tc->size();

   742 }

   743 

   744 size_t BinaryTreeDictionary::totalListLength(TreeList* tl) const {

   745   size_t res;

   746   res = tl->count();

   747 #ifdef ASSERT

   748   size_t cnt;

   749   FreeChunk* tc = tl->head();

   750   for (cnt = 0; tc != NULL; tc = tc->next(), cnt++);

   751   assert(res == cnt, "The count is not being maintained correctly");

   752 #endif

   753   return res;

   754 }

   755 

   756 size_t BinaryTreeDictionary::totalSizeInTree(TreeList* tl) const {

   757   if (tl == NULL)

   758     return 0;

   759   return (tl->size() * totalListLength(tl)) +

   760          totalSizeInTree(tl->left())    +

   761          totalSizeInTree(tl->right());

   762 }

   763 

   764 double BinaryTreeDictionary::sum_of_squared_block_sizes(TreeList* const tl) const {

   765   if (tl == NULL) {

   766     return 0.0;

   767   }

   768   double size = (double)(tl->size());

   769   double curr = size * size * totalListLength(tl);

   770   curr += sum_of_squared_block_sizes(tl->left());

   771   curr += sum_of_squared_block_sizes(tl->right());

   772   return curr;

   773 }

   774 

   775 size_t BinaryTreeDictionary::totalFreeBlocksInTree(TreeList* tl) const {

   776   if (tl == NULL)

   777     return 0;

   778   return totalListLength(tl) +

   779          totalFreeBlocksInTree(tl->left()) +

   780          totalFreeBlocksInTree(tl->right());

   781 }

   782 

   783 size_t BinaryTreeDictionary::numFreeBlocks() const {

   784   assert(totalFreeBlocksInTree(root()) == totalFreeBlocks(),

   785          "_totalFreeBlocks inconsistency");

   786   return totalFreeBlocks();

   787 }

   788 

   789 size_t BinaryTreeDictionary::treeHeightHelper(TreeList* tl) const {

   790   if (tl == NULL)

   791     return 0;

   792   return 1 + MAX2(treeHeightHelper(tl->left()),

   793                   treeHeightHelper(tl->right()));

   794 }

   795 

   796 size_t BinaryTreeDictionary::treeHeight() const {

   797   return treeHeightHelper(root());

   798 }

   799 

   800 size_t BinaryTreeDictionary::totalNodesHelper(TreeList* tl) const {

   801   if (tl == NULL) {

   802     return 0;

   803   }

   804   return 1 + totalNodesHelper(tl->left()) +

   805     totalNodesHelper(tl->right());

   806 }

   807 

   808 size_t BinaryTreeDictionary::totalNodesInTree(TreeList* tl) const {

   809   return totalNodesHelper(root());

   810 }

   811 

   812 void BinaryTreeDictionary::dictCensusUpdate(size_t size, bool split, bool birth){

   813   TreeList* nd = findList(size);

   814   if (nd) {

   815     if (split) {

   816       if (birth) {

   817         nd->increment_splitBirths();

   818         nd->increment_surplus();

   819       }  else {

   820         nd->increment_splitDeaths();

   821         nd->decrement_surplus();

   822       }

   823     } else {

   824       if (birth) {

   825         nd->increment_coalBirths();

   826         nd->increment_surplus();

   827       } else {

   828         nd->increment_coalDeaths();

   829         nd->decrement_surplus();

   830       }

   831     }

   832   }

   833   // A list for this size may not be found (nd == 0) if

   834   //   This is a death where the appropriate list is now

   835   //     empty and has been removed from the list.

   836   //   This is a birth associated with a LinAB.  The chunk

   837   //     for the LinAB is not in the dictionary.

   838 }

   839 

   840 bool BinaryTreeDictionary::coalDictOverPopulated(size_t size) {

   841   if (FLSAlwaysCoalesceLarge) return true;

   842 

   843   TreeList* list_of_size = findList(size);

   844   // None of requested size implies overpopulated.

   845   return list_of_size == NULL || list_of_size->coalDesired() <= 0 ||

   846          list_of_size->count() > list_of_size->coalDesired();

   847 }

   848 

   849 // Closures for walking the binary tree.

   850 //   do_list() walks the free list in a node applying the closure

   851 //     to each free chunk in the list

   852 //   do_tree() walks the nodes in the binary tree applying do_list()

   853 //     to each list at each node.

   854 

   855 class TreeCensusClosure : public StackObj {

   856  protected:

   857   virtual void do_list(FreeList* fl) = 0;

   858  public:

   859   virtual void do_tree(TreeList* tl) = 0;

   860 };

   861 

   862 class AscendTreeCensusClosure : public TreeCensusClosure {

   863  public:

   864   void do_tree(TreeList* tl) {

   865     if (tl != NULL) {

   866       do_tree(tl->left());

   867       do_list(tl);

   868       do_tree(tl->right());

   869     }

   870   }

   871 };

   872 

   873 class DescendTreeCensusClosure : public TreeCensusClosure {

   874  public:

   875   void do_tree(TreeList* tl) {

   876     if (tl != NULL) {

   877       do_tree(tl->right());

   878       do_list(tl);

   879       do_tree(tl->left());

   880     }

   881   }

   882 };

   883 

   884 // For each list in the tree, calculate the desired, desired

   885 // coalesce, count before sweep, and surplus before sweep.

   886 class BeginSweepClosure : public AscendTreeCensusClosure {

   887   double _percentage;

   888   float _inter_sweep_current;

   889   float _inter_sweep_estimate;

   890   float _intra_sweep_estimate;

   891 

   892  public:

   893   BeginSweepClosure(double p, float inter_sweep_current,

   894                               float inter_sweep_estimate,

   895                               float intra_sweep_estimate) :

   896    _percentage(p),

   897    _inter_sweep_current(inter_sweep_current),

   898    _inter_sweep_estimate(inter_sweep_estimate),

   899    _intra_sweep_estimate(intra_sweep_estimate) { }

   900 

   901   void do_list(FreeList* fl) {

   902     double coalSurplusPercent = _percentage;

   903     fl->compute_desired(_inter_sweep_current, _inter_sweep_estimate, _intra_sweep_estimate);

   904     fl->set_coalDesired((ssize_t)((double)fl->desired() * coalSurplusPercent));

   905     fl->set_beforeSweep(fl->count());

   906     fl->set_bfrSurp(fl->surplus());

   907   }

   908 };

   909 

   910 // Used to search the tree until a condition is met.

   911 // Similar to TreeCensusClosure but searches the

   912 // tree and returns promptly when found.

   913 

   914 class TreeSearchClosure : public StackObj {

   915  protected:

   916   virtual bool do_list(FreeList* fl) = 0;

   917  public:

   918   virtual bool do_tree(TreeList* tl) = 0;

   919 };

   920 

   921 #if 0 //  Don't need this yet but here for symmetry.

   922 class AscendTreeSearchClosure : public TreeSearchClosure {

   923  public:

   924   bool do_tree(TreeList* tl) {

   925     if (tl != NULL) {

   926       if (do_tree(tl->left())) return true;

   927       if (do_list(tl)) return true;

   928       if (do_tree(tl->right())) return true;

   929     }

   930     return false;

   931   }

   932 };

   933 #endif

   934 

   935 class DescendTreeSearchClosure : public TreeSearchClosure {

   936  public:

   937   bool do_tree(TreeList* tl) {

   938     if (tl != NULL) {

   939       if (do_tree(tl->right())) return true;

   940       if (do_list(tl)) return true;

   941       if (do_tree(tl->left())) return true;

   942     }

   943     return false;

   944   }

   945 };

   946 

   947 // Searches the tree for a chunk that ends at the

   948 // specified address.

   949 class EndTreeSearchClosure : public DescendTreeSearchClosure {

   950   HeapWord* _target;

   951   FreeChunk* _found;

   952 

   953  public:

   954   EndTreeSearchClosure(HeapWord* target) : _target(target), _found(NULL) {}

   955   bool do_list(FreeList* fl) {

   956     FreeChunk* item = fl->head();

   957     while (item != NULL) {

   958       if (item->end() == _target) {

   959         _found = item;

   960         return true;

   961       }

   962       item = item->next();

   963     }

   964     return false;

   965   }

   966   FreeChunk* found() { return _found; }

   967 };

   968 

   969 FreeChunk* BinaryTreeDictionary::find_chunk_ends_at(HeapWord* target) const {

   970   EndTreeSearchClosure etsc(target);

   971   bool found_target = etsc.do_tree(root());

   972   assert(found_target || etsc.found() == NULL, "Consistency check");

   973   assert(!found_target || etsc.found() != NULL, "Consistency check");

   974   return etsc.found();

   975 }

   976 

   977 void BinaryTreeDictionary::beginSweepDictCensus(double coalSurplusPercent,

   978   float inter_sweep_current, float inter_sweep_estimate, float intra_sweep_estimate) {

   979   BeginSweepClosure bsc(coalSurplusPercent, inter_sweep_current,

   980                                             inter_sweep_estimate,

   981                                             intra_sweep_estimate);

   982   bsc.do_tree(root());

   983 }

   984 

   985 // Closures and methods for calculating total bytes returned to the

   986 // free lists in the tree.

   987 NOT_PRODUCT(

   988   class InitializeDictReturnedBytesClosure : public AscendTreeCensusClosure {

   989    public:

   990     void do_list(FreeList* fl) {

   991       fl->set_returnedBytes(0);

   992     }

   993   };

   994 

   995   void BinaryTreeDictionary::initializeDictReturnedBytes() {

   996     InitializeDictReturnedBytesClosure idrb;

   997     idrb.do_tree(root());

   998   }

   999 

  1000   class ReturnedBytesClosure : public AscendTreeCensusClosure {

  1001     size_t _dictReturnedBytes;

  1002    public:

  1003     ReturnedBytesClosure() { _dictReturnedBytes = 0; }

  1004     void do_list(FreeList* fl) {

  1005       _dictReturnedBytes += fl->returnedBytes();

  1006     }

  1007     size_t dictReturnedBytes() { return _dictReturnedBytes; }

  1008   };

  1009 

  1010   size_t BinaryTreeDictionary::sumDictReturnedBytes() {

  1011     ReturnedBytesClosure rbc;

  1012     rbc.do_tree(root());

  1013 

  1014     return rbc.dictReturnedBytes();

  1015   }

  1016 

  1017   // Count the number of entries in the tree.

  1018   class treeCountClosure : public DescendTreeCensusClosure {

  1019    public:

  1020     uint count;

  1021     treeCountClosure(uint c) { count = c; }

  1022     void do_list(FreeList* fl) {

  1023       count++;

  1024     }

  1025   };

  1026 

  1027   size_t BinaryTreeDictionary::totalCount() {

  1028     treeCountClosure ctc(0);

  1029     ctc.do_tree(root());

  1030     return ctc.count;

  1031   }

  1032 )

  1033 

  1034 // Calculate surpluses for the lists in the tree.

  1035 class setTreeSurplusClosure : public AscendTreeCensusClosure {

  1036   double percentage;

  1037  public:

  1038   setTreeSurplusClosure(double v) { percentage = v; }

  1039   void do_list(FreeList* fl) {

  1040     double splitSurplusPercent = percentage;

  1041     fl->set_surplus(fl->count() -

  1042                    (ssize_t)((double)fl->desired() * splitSurplusPercent));

  1043   }

  1044 };

  1045 

  1046 void BinaryTreeDictionary::setTreeSurplus(double splitSurplusPercent) {

  1047   setTreeSurplusClosure sts(splitSurplusPercent);

  1048   sts.do_tree(root());

  1049 }

  1050 

  1051 // Set hints for the lists in the tree.

  1052 class setTreeHintsClosure : public DescendTreeCensusClosure {

  1053   size_t hint;

  1054  public:

  1055   setTreeHintsClosure(size_t v) { hint = v; }

  1056   void do_list(FreeList* fl) {

  1057     fl->set_hint(hint);

  1058     assert(fl->hint() == 0 || fl->hint() > fl->size(),

  1059       "Current hint is inconsistent");

  1060     if (fl->surplus() > 0) {

  1061       hint = fl->size();

  1062     }

  1063   }

  1064 };

  1065 

  1066 void BinaryTreeDictionary::setTreeHints(void) {

  1067   setTreeHintsClosure sth(0);

  1068   sth.do_tree(root());

  1069 }

  1070 

  1071 // Save count before previous sweep and splits and coalesces.

  1072 class clearTreeCensusClosure : public AscendTreeCensusClosure {

  1073   void do_list(FreeList* fl) {

  1074     fl->set_prevSweep(fl->count());

  1075     fl->set_coalBirths(0);

  1076     fl->set_coalDeaths(0);

  1077     fl->set_splitBirths(0);

  1078     fl->set_splitDeaths(0);

  1079   }

  1080 };

  1081 

  1082 void BinaryTreeDictionary::clearTreeCensus(void) {

  1083   clearTreeCensusClosure ctc;

  1084   ctc.do_tree(root());

  1085 }

  1086 

  1087 // Do reporting and post sweep clean up.

  1088 void BinaryTreeDictionary::endSweepDictCensus(double splitSurplusPercent) {

  1089   // Does walking the tree 3 times hurt?

  1090   setTreeSurplus(splitSurplusPercent);

  1091   setTreeHints();

  1092   if (PrintGC && Verbose) {

  1093     reportStatistics();

  1094   }

  1095   clearTreeCensus();

  1096 }

  1097 

  1098 // Print summary statistics

  1099 void BinaryTreeDictionary::reportStatistics() const {

  1100   verify_par_locked();

  1101   gclog_or_tty->print("Statistics for BinaryTreeDictionary:\n"

  1102          "------------------------------------\n");

  1103   size_t totalSize = totalChunkSize(debug_only(NULL));

  1104   size_t    freeBlocks = numFreeBlocks();

  1105   gclog_or_tty->print("Total Free Space: %d\n", totalSize);

  1106   gclog_or_tty->print("Max   Chunk Size: %d\n", maxChunkSize());

  1107   gclog_or_tty->print("Number of Blocks: %d\n", freeBlocks);

  1108   if (freeBlocks > 0) {

  1109     gclog_or_tty->print("Av.  Block  Size: %d\n", totalSize/freeBlocks);

  1110   }

  1111   gclog_or_tty->print("Tree      Height: %d\n", treeHeight());

  1112 }

  1113 

  1114 // Print census information - counts, births, deaths, etc.

  1115 // for each list in the tree.  Also print some summary

  1116 // information.

  1117 class PrintTreeCensusClosure : public AscendTreeCensusClosure {

  1118   int _print_line;

  1119   size_t _totalFree;

  1120   FreeList _total;

  1121 

  1122  public:

  1123   PrintTreeCensusClosure() {

  1124     _print_line = 0;

  1125     _totalFree = 0;

  1126   }

  1127   FreeList* total() { return &_total; }

  1128   size_t totalFree() { return _totalFree; }

  1129   void do_list(FreeList* fl) {

  1130     if (++_print_line >= 40) {

  1131       FreeList::print_labels_on(gclog_or_tty, "size");

  1132       _print_line = 0;

  1133     }

  1134     fl->print_on(gclog_or_tty);