diff -r f5e31fb61738 -r 944e56f74fba hotspot/src/share/vm/memory/binaryTreeDictionary.cpp --- a/hotspot/src/share/vm/memory/binaryTreeDictionary.cpp Fri Oct 19 11:26:17 2012 -0700 +++ b/hotspot/src/share/vm/memory/binaryTreeDictionary.cpp Tue Sep 18 23:35:42 2012 -0700 @@ -25,9 +25,15 @@ #include "precompiled.hpp" #include "gc_implementation/shared/allocationStats.hpp" #include "memory/binaryTreeDictionary.hpp" +#include "memory/freeList.hpp" +#include "memory/freeBlockDictionary.hpp" +#include "memory/metablock.hpp" +#include "memory/metachunk.hpp" #include "runtime/globals.hpp" #include "utilities/ostream.hpp" #ifndef SERIALGC +#include "gc_implementation/concurrentMarkSweep/adaptiveFreeList.hpp" +#include "gc_implementation/concurrentMarkSweep/freeChunk.hpp" #include "gc_implementation/shared/spaceDecorator.hpp" #include "gc_implementation/concurrentMarkSweep/freeChunk.hpp" #endif // SERIALGC @@ -37,15 +43,18 @@ // This is currently used in the Concurrent Mark&Sweep implementation. //////////////////////////////////////////////////////////////////////////////// -template -TreeChunk* TreeChunk::as_TreeChunk(Chunk* fc) { +template class FreeList_t> +size_t TreeChunk::_min_tree_chunk_size = sizeof(TreeChunk)/HeapWordSize; + +template class FreeList_t> +TreeChunk* TreeChunk::as_TreeChunk(Chunk_t* fc) { // Do some assertion checking here. - return (TreeChunk*) fc; + return (TreeChunk*) fc; } -template -void TreeChunk::verify_tree_chunk_list() const { - TreeChunk* nextTC = (TreeChunk*)next(); +template class FreeList_t> +void TreeChunk::verify_tree_chunk_list() const { + TreeChunk* nextTC = (TreeChunk*)next(); if (prev() != NULL) { // interior list node shouldn'r have tree fields guarantee(embedded_list()->parent() == NULL && embedded_list()->left() == NULL && embedded_list()->right() == NULL, "should be clear"); @@ -57,53 +66,113 @@ } } +template class FreeList_t> +TreeList::TreeList() {} -template -TreeList* TreeList::as_TreeList(TreeChunk* tc) { +template class FreeList_t> +TreeList* +TreeList::as_TreeList(TreeChunk* tc) { // This first free chunk in the list will be the tree list. - assert(tc->size() >= BinaryTreeDictionary::min_tree_chunk_size, "Chunk is too small for a TreeChunk"); - TreeList* tl = tc->embedded_list(); + assert((tc->size() >= (TreeChunk::min_size())), + "Chunk is too small for a TreeChunk"); + TreeList* tl = tc->embedded_list(); + tl->initialize(); tc->set_list(tl); -#ifdef ASSERT - tl->set_protecting_lock(NULL); -#endif - tl->set_hint(0); tl->set_size(tc->size()); tl->link_head(tc); tl->link_tail(tc); tl->set_count(1); - tl->init_statistics(true /* split_birth */); - tl->set_parent(NULL); - tl->set_left(NULL); - tl->set_right(NULL); + + return tl; +} + + +template class FreeList_t> +TreeList* +get_chunk(size_t size, enum FreeBlockDictionary::Dither dither) { + FreeBlockDictionary::verify_par_locked(); + Chunk_t* res = get_chunk_from_tree(size, dither); + assert(res == NULL || res->is_free(), + "Should be returning a free chunk"); + assert(dither != FreeBlockDictionary::exactly || + res->size() == size, "Not correct size"); + return res; +} + +template class FreeList_t> +TreeList* +TreeList::as_TreeList(HeapWord* addr, size_t size) { + TreeChunk* tc = (TreeChunk*) addr; + assert((size >= TreeChunk::min_size()), + "Chunk is too small for a TreeChunk"); + // The space will have been mangled initially but + // is not remangled when a Chunk_t is returned to the free list + // (since it is used to maintain the chunk on the free list). + tc->assert_is_mangled(); + tc->set_size(size); + tc->link_prev(NULL); + tc->link_next(NULL); + TreeList* tl = TreeList::as_TreeList(tc); return tl; } -template -TreeList* TreeList::as_TreeList(HeapWord* addr, size_t size) { - TreeChunk* tc = (TreeChunk*) addr; - assert(size >= BinaryTreeDictionary::min_tree_chunk_size, "Chunk is too small for a TreeChunk"); - // The space in the heap will have been mangled initially but - // is not remangled when a free chunk is returned to the free list - // (since it is used to maintain the chunk on the free list). - assert((ZapUnusedHeapArea && - SpaceMangler::is_mangled((HeapWord*) tc->size_addr()) && - SpaceMangler::is_mangled((HeapWord*) tc->prev_addr()) && - SpaceMangler::is_mangled((HeapWord*) tc->next_addr())) || - (tc->size() == 0 && tc->prev() == NULL && tc->next() == NULL), - "Space should be clear or mangled"); - tc->set_size(size); - tc->link_prev(NULL); - tc->link_next(NULL); - TreeList* tl = TreeList::as_TreeList(tc); - return tl; + +#ifndef SERIALGC +// Specialize for AdaptiveFreeList which tries to avoid +// splitting a chunk of a size that is under populated in favor of +// an over populated size. The general get_better_list() just returns +// the current list. +template <> +TreeList* +TreeList::get_better_list( + BinaryTreeDictionary* dictionary) { + // A candidate chunk has been found. If it is already under + // populated, get a chunk associated with the hint for this + // chunk. + + TreeList* curTL = this; + if (surplus() <= 0) { + /* Use the hint to find a size with a surplus, and reset the hint. */ + TreeList* hintTL = this; + while (hintTL->hint() != 0) { + assert(hintTL->hint() > hintTL->size(), + "hint points in the wrong direction"); + hintTL = dictionary->find_list(hintTL->hint()); + assert(curTL != hintTL, "Infinite loop"); + if (hintTL == NULL || + hintTL == curTL /* Should not happen but protect against it */ ) { + // No useful hint. Set the hint to NULL and go on. + curTL->set_hint(0); + break; + } + assert(hintTL->size() > curTL->size(), "hint is inconsistent"); + if (hintTL->surplus() > 0) { + // The hint led to a list that has a surplus. Use it. + // Set the hint for the candidate to an overpopulated + // size. + curTL->set_hint(hintTL->size()); + // Change the candidate. + curTL = hintTL; + break; + } + } + } + return curTL; +} +#endif // SERIALGC + +template class FreeList_t> +TreeList* +TreeList::get_better_list( + BinaryTreeDictionary* dictionary) { + return this; } -template -TreeList* TreeList::remove_chunk_replace_if_needed(TreeChunk* tc) { +template class FreeList_t> +TreeList* TreeList::remove_chunk_replace_if_needed(TreeChunk* tc) { - TreeList* retTL = this; - Chunk* list = head(); + TreeList* retTL = this; + Chunk_t* list = head(); assert(!list || list != list->next(), "Chunk on list twice"); assert(tc != NULL, "Chunk being removed is NULL"); assert(parent() == NULL || this == parent()->left() || @@ -112,13 +181,13 @@ assert(head() == NULL || head()->prev() == NULL, "list invariant"); assert(tail() == NULL || tail()->next() == NULL, "list invariant"); - Chunk* prevFC = tc->prev(); - TreeChunk* nextTC = TreeChunk::as_TreeChunk(tc->next()); + Chunk_t* prevFC = tc->prev(); + TreeChunk* nextTC = TreeChunk::as_TreeChunk(tc->next()); assert(list != NULL, "should have at least the target chunk"); // Is this the first item on the list? if (tc == list) { - // The "getChunk..." functions for a TreeList will not return the + // The "getChunk..." functions for a TreeList will not return the // first chunk in the list unless it is the last chunk in the list // because the first chunk is also acting as the tree node. // When coalescing happens, however, the first chunk in the a tree @@ -127,8 +196,8 @@ // allocated when the sweeper yields (giving up the free list lock) // to allow mutator activity. If this chunk is the first in the // list and is not the last in the list, do the work to copy the - // TreeList from the first chunk to the next chunk and update all - // the TreeList pointers in the chunks in the list. + // TreeList from the first chunk to the next chunk and update all + // the TreeList pointers in the chunks in the list. if (nextTC == NULL) { assert(prevFC == NULL, "Not last chunk in the list"); set_tail(NULL); @@ -141,11 +210,11 @@ // This can be slow for a long list. Consider having // an option that does not allow the first chunk on the // list to be coalesced. - for (TreeChunk* curTC = nextTC; curTC != NULL; - curTC = TreeChunk::as_TreeChunk(curTC->next())) { + for (TreeChunk* curTC = nextTC; curTC != NULL; + curTC = TreeChunk::as_TreeChunk(curTC->next())) { curTC->set_list(retTL); } - // Fix the parent to point to the new TreeList. + // Fix the parent to point to the new TreeList. if (retTL->parent() != NULL) { if (this == retTL->parent()->left()) { retTL->parent()->set_left(retTL); @@ -176,9 +245,9 @@ prevFC->link_after(nextTC); } - // Below this point the embeded TreeList being used for the + // Below this point the embeded TreeList being used for the // tree node may have changed. Don't use "this" - // TreeList*. + // TreeList*. // chunk should still be a free chunk (bit set in _prev) assert(!retTL->head() || retTL->size() == retTL->head()->size(), "Wrong sized chunk in list"); @@ -188,7 +257,7 @@ tc->set_list(NULL); bool prev_found = false; bool next_found = false; - for (Chunk* curFC = retTL->head(); + for (Chunk_t* curFC = retTL->head(); curFC != NULL; curFC = curFC->next()) { assert(curFC != tc, "Chunk is still in list"); if (curFC == prevFC) { @@ -215,8 +284,8 @@ return retTL; } -template -void TreeList::return_chunk_at_tail(TreeChunk* chunk) { +template class FreeList_t> +void TreeList::return_chunk_at_tail(TreeChunk* chunk) { assert(chunk != NULL, "returning NULL chunk"); assert(chunk->list() == this, "list should be set for chunk"); assert(tail() != NULL, "The tree list is embedded in the first chunk"); @@ -225,12 +294,12 @@ assert(head() == NULL || head()->prev() == NULL, "list invariant"); assert(tail() == NULL || tail()->next() == NULL, "list invariant"); - Chunk* fc = tail(); + Chunk_t* fc = tail(); fc->link_after(chunk); link_tail(chunk); assert(!tail() || size() == tail()->size(), "Wrong sized chunk in list"); - increment_count(); + FreeList_t::increment_count(); debug_only(increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));) assert(head() == NULL || head()->prev() == NULL, "list invariant"); assert(tail() == NULL || tail()->next() == NULL, "list invariant"); @@ -238,10 +307,10 @@ // Add this chunk at the head of the list. "At the head of the list" // is defined to be after the chunk pointer to by head(). This is -// because the TreeList is embedded in the first TreeChunk in the -// list. See the definition of TreeChunk. -template -void TreeList::return_chunk_at_head(TreeChunk* chunk) { +// because the TreeList is embedded in the first TreeChunk in the +// list. See the definition of TreeChunk. +template class FreeList_t> +void TreeList::return_chunk_at_head(TreeChunk* chunk) { assert(chunk->list() == this, "list should be set for chunk"); assert(head() != NULL, "The tree list is embedded in the first chunk"); assert(chunk != NULL, "returning NULL chunk"); @@ -249,7 +318,7 @@ assert(head() == NULL || head()->prev() == NULL, "list invariant"); assert(tail() == NULL || tail()->next() == NULL, "list invariant"); - Chunk* fc = head()->next(); + Chunk_t* fc = head()->next(); if (fc != NULL) { chunk->link_after(fc); } else { @@ -258,28 +327,38 @@ } head()->link_after(chunk); assert(!head() || size() == head()->size(), "Wrong sized chunk in list"); - increment_count(); + FreeList_t::increment_count(); debug_only(increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));) assert(head() == NULL || head()->prev() == NULL, "list invariant"); assert(tail() == NULL || tail()->next() == NULL, "list invariant"); } -template -TreeChunk* TreeList::head_as_TreeChunk() { - assert(head() == NULL || TreeChunk::as_TreeChunk(head())->list() == this, - "Wrong type of chunk?"); - return TreeChunk::as_TreeChunk(head()); +template class FreeList_t> +void TreeChunk::assert_is_mangled() const { + assert((ZapUnusedHeapArea && + SpaceMangler::is_mangled((HeapWord*) Chunk_t::size_addr()) && + SpaceMangler::is_mangled((HeapWord*) Chunk_t::prev_addr()) && + SpaceMangler::is_mangled((HeapWord*) Chunk_t::next_addr())) || + (size() == 0 && prev() == NULL && next() == NULL), + "Space should be clear or mangled"); } -template -TreeChunk* TreeList::first_available() { +template class FreeList_t> +TreeChunk* TreeList::head_as_TreeChunk() { + assert(head() == NULL || (TreeChunk::as_TreeChunk(head())->list() == this), + "Wrong type of chunk?"); + return TreeChunk::as_TreeChunk(head()); +} + +template class FreeList_t> +TreeChunk* TreeList::first_available() { assert(head() != NULL, "The head of the list cannot be NULL"); - Chunk* fc = head()->next(); - TreeChunk* retTC; + Chunk_t* fc = head()->next(); + TreeChunk* retTC; if (fc == NULL) { retTC = head_as_TreeChunk(); } else { - retTC = TreeChunk::as_TreeChunk(fc); + retTC = TreeChunk::as_TreeChunk(fc); } assert(retTC->list() == this, "Wrong type of chunk."); return retTC; @@ -288,41 +367,32 @@ // Returns the block with the largest heap address amongst // those in the list for this size; potentially slow and expensive, // use with caution! -template -TreeChunk* TreeList::largest_address() { +template class FreeList_t> +TreeChunk* TreeList::largest_address() { assert(head() != NULL, "The head of the list cannot be NULL"); - Chunk* fc = head()->next(); - TreeChunk* retTC; + Chunk_t* fc = head()->next(); + TreeChunk* retTC; if (fc == NULL) { retTC = head_as_TreeChunk(); } else { // walk down the list and return the one with the highest // heap address among chunks of this size. - Chunk* last = fc; + Chunk_t* last = fc; while (fc->next() != NULL) { if ((HeapWord*)last < (HeapWord*)fc) { last = fc; } fc = fc->next(); } - retTC = TreeChunk::as_TreeChunk(last); + retTC = TreeChunk::as_TreeChunk(last); } assert(retTC->list() == this, "Wrong type of chunk."); return retTC; } -template -BinaryTreeDictionary::BinaryTreeDictionary(bool adaptive_freelists, bool splay) : - _splay(splay), _adaptive_freelists(adaptive_freelists), - _total_size(0), _total_free_blocks(0), _root(0) {} - -template -BinaryTreeDictionary::BinaryTreeDictionary(MemRegion mr, - bool adaptive_freelists, - bool splay): - _adaptive_freelists(adaptive_freelists), _splay(splay) -{ - assert(mr.word_size() >= BinaryTreeDictionary::min_tree_chunk_size, "minimum chunk size"); +template class FreeList_t> +BinaryTreeDictionary::BinaryTreeDictionary(MemRegion mr) { + assert((mr.byte_size() > min_size()), "minimum chunk size"); reset(mr); assert(root()->left() == NULL, "reset check failed"); @@ -333,52 +403,48 @@ assert(total_free_blocks() == 1, "reset check failed"); } -template -void BinaryTreeDictionary::inc_total_size(size_t inc) { +template class FreeList_t> +void BinaryTreeDictionary::inc_total_size(size_t inc) { _total_size = _total_size + inc; } -template -void BinaryTreeDictionary::dec_total_size(size_t dec) { +template class FreeList_t> +void BinaryTreeDictionary::dec_total_size(size_t dec) { _total_size = _total_size - dec; } -template -void BinaryTreeDictionary::reset(MemRegion mr) { - assert(mr.word_size() >= BinaryTreeDictionary::min_tree_chunk_size, "minimum chunk size"); - set_root(TreeList::as_TreeList(mr.start(), mr.word_size())); +template class FreeList_t> +void BinaryTreeDictionary::reset(MemRegion mr) { + assert((mr.byte_size() > min_size()), "minimum chunk size"); + set_root(TreeList::as_TreeList(mr.start(), mr.word_size())); set_total_size(mr.word_size()); set_total_free_blocks(1); } -template -void BinaryTreeDictionary::reset(HeapWord* addr, size_t byte_size) { +template class FreeList_t> +void BinaryTreeDictionary::reset(HeapWord* addr, size_t byte_size) { MemRegion mr(addr, heap_word_size(byte_size)); reset(mr); } -template -void BinaryTreeDictionary::reset() { +template class FreeList_t> +void BinaryTreeDictionary::reset() { set_root(NULL); set_total_size(0); set_total_free_blocks(0); } // Get a free block of size at least size from tree, or NULL. -// If a splay step is requested, the removal algorithm (only) incorporates -// a splay step as follows: -// . the search proceeds down the tree looking for a possible -// match. At the (closest) matching location, an appropriate splay step is applied -// (zig, zig-zig or zig-zag). A chunk of the appropriate size is then returned -// if available, and if it's the last chunk, the node is deleted. A deteleted -// node is replaced in place by its tree successor. -template -TreeChunk* -BinaryTreeDictionary::get_chunk_from_tree(size_t size, enum FreeBlockDictionary::Dither dither, bool splay) +template class FreeList_t> +TreeChunk* +BinaryTreeDictionary::get_chunk_from_tree( + size_t size, + enum FreeBlockDictionary::Dither dither) { - TreeList *curTL, *prevTL; - TreeChunk* retTC = NULL; - assert(size >= BinaryTreeDictionary::min_tree_chunk_size, "minimum chunk size"); + TreeList *curTL, *prevTL; + TreeChunk* retTC = NULL; + + assert((size >= min_size()), "minimum chunk size"); if (FLSVerifyDictionary) { verify_tree(); } @@ -398,7 +464,7 @@ } if (curTL == NULL) { // couldn't find exact match - if (dither == FreeBlockDictionary::exactly) return NULL; + if (dither == FreeBlockDictionary::exactly) return NULL; // try and find the next larger size by walking back up the search path for (curTL = prevTL; curTL != NULL;) { @@ -410,46 +476,9 @@ } if (curTL != NULL) { assert(curTL->size() >= size, "size inconsistency"); - if (adaptive_freelists()) { - // A candidate chunk has been found. If it is already under - // populated, get a chunk associated with the hint for this - // chunk. - if (curTL->surplus() <= 0) { - /* Use the hint to find a size with a surplus, and reset the hint. */ - TreeList* hintTL = curTL; - while (hintTL->hint() != 0) { - assert(hintTL->hint() == 0 || hintTL->hint() > hintTL->size(), - "hint points in the wrong direction"); - hintTL = find_list(hintTL->hint()); - assert(curTL != hintTL, "Infinite loop"); - if (hintTL == NULL || - hintTL == curTL /* Should not happen but protect against it */ ) { - // No useful hint. Set the hint to NULL and go on. - curTL->set_hint(0); - break; - } - assert(hintTL->size() > size, "hint is inconsistent"); - if (hintTL->surplus() > 0) { - // The hint led to a list that has a surplus. Use it. - // Set the hint for the candidate to an overpopulated - // size. - curTL->set_hint(hintTL->size()); - // Change the candidate. - curTL = hintTL; - break; - } - // The evm code reset the hint of the candidate as - // at an interim point. Why? Seems like this leaves - // the hint pointing to a list that didn't work. - // curTL->set_hint(hintTL->size()); - } - } - } - // don't waste time splaying if chunk's singleton - if (splay && curTL->head()->next() != NULL) { - semi_splay_step(curTL); - } + curTL = curTL->get_better_list(this); + retTC = curTL->first_available(); assert((retTC != NULL) && (curTL->count() > 0), "A list in the binary tree should not be NULL"); @@ -465,9 +494,9 @@ return retTC; } -template -TreeList* BinaryTreeDictionary::find_list(size_t size) const { - TreeList* curTL; +template class FreeList_t> +TreeList* BinaryTreeDictionary::find_list(size_t size) const { + TreeList* curTL; for (curTL = root(); curTL != NULL;) { if (curTL->size() == size) { // exact match break; @@ -484,10 +513,10 @@ } -template -bool BinaryTreeDictionary::verify_chunk_in_free_list(Chunk* tc) const { +template class FreeList_t> +bool BinaryTreeDictionary::verify_chunk_in_free_list(Chunk_t* tc) const { size_t size = tc->size(); - TreeList* tl = find_list(size); + TreeList* tl = find_list(size); if (tl == NULL) { return false; } else { @@ -495,9 +524,9 @@ } } -template -Chunk* BinaryTreeDictionary::find_largest_dict() const { - TreeList *curTL = root(); +template class FreeList_t> +Chunk_t* BinaryTreeDictionary::find_largest_dict() const { + TreeList *curTL = root(); if (curTL != NULL) { while(curTL->right() != NULL) curTL = curTL->right(); return curTL->largest_address(); @@ -510,15 +539,15 @@ // chunk in a list on a tree node, just unlink it. // If it is the last chunk in the list (the next link is NULL), // remove the node and repair the tree. -template -TreeChunk* -BinaryTreeDictionary::remove_chunk_from_tree(TreeChunk* tc) { +template class FreeList_t> +TreeChunk* +BinaryTreeDictionary::remove_chunk_from_tree(TreeChunk* tc) { assert(tc != NULL, "Should not call with a NULL chunk"); assert(tc->is_free(), "Header is not marked correctly"); - TreeList *newTL, *parentTL; - TreeChunk* retTC; - TreeList* tl = tc->list(); + TreeList *newTL, *parentTL; + TreeChunk* retTC; + TreeList* tl = tc->list(); debug_only( bool removing_only_chunk = false; if (tl == _root) { @@ -538,8 +567,8 @@ retTC = tc; // Removing this chunk can have the side effect of changing the node - // (TreeList*) in the tree. If the node is the root, update it. - TreeList* replacementTL = tl->remove_chunk_replace_if_needed(tc); + // (TreeList*) in the tree. If the node is the root, update it. + TreeList* replacementTL = tl->remove_chunk_replace_if_needed(tc); assert(tc->is_free(), "Chunk should still be free"); assert(replacementTL->parent() == NULL || replacementTL == replacementTL->parent()->left() || @@ -549,17 +578,18 @@ assert(replacementTL->parent() == NULL, "Incorrectly replacing root"); set_root(replacementTL); } - debug_only( +#ifdef ASSERT if (tl != replacementTL) { assert(replacementTL->head() != NULL, "If the tree list was replaced, it should not be a NULL list"); - TreeList* rhl = replacementTL->head_as_TreeChunk()->list(); - TreeList* rtl = TreeChunk::as_TreeChunk(replacementTL->tail())->list(); + TreeList* rhl = replacementTL->head_as_TreeChunk()->list(); + TreeList* rtl = + TreeChunk::as_TreeChunk(replacementTL->tail())->list(); assert(rhl == replacementTL, "Broken head"); assert(rtl == replacementTL, "Broken tail"); assert(replacementTL->size() == tc->size(), "Broken size"); } - ) +#endif // Does the tree need to be repaired? if (replacementTL->count() == 0) { @@ -574,7 +604,7 @@ } else if (replacementTL->right() == NULL) { // right is NULL newTL = replacementTL->left(); - debug_only(replacementTL->clearLeft();) + debug_only(replacementTL->clear_left();) } else { // we have both children, so, by patriarchal convention, // my replacement is least node in right sub-tree complicated_splice = true; @@ -623,7 +653,7 @@ newTL->set_right(replacementTL->right()); debug_only( replacementTL->clear_right(); - replacementTL->clearLeft(); + replacementTL->clear_left(); ) } assert(replacementTL->right() == NULL && @@ -644,21 +674,21 @@ verify_tree(); } assert(!removing_only_chunk || _root == NULL, "root should be NULL"); - return TreeChunk::as_TreeChunk(retTC); + return TreeChunk::as_TreeChunk(retTC); } // Remove the leftmost node (lm) in the tree and return it. // If lm has a right child, link it to the left node of // the parent of lm. -template -TreeList* BinaryTreeDictionary::remove_tree_minimum(TreeList* tl) { +template class FreeList_t> +TreeList* BinaryTreeDictionary::remove_tree_minimum(TreeList* tl) { assert(tl != NULL && tl->parent() != NULL, "really need a proper sub-tree"); // locate the subtree minimum by walking down left branches - TreeList* curTL = tl; + TreeList* curTL = tl; for (; curTL->left() != NULL; curTL = curTL->left()); // obviously curTL now has at most one child, a right child if (curTL != root()) { // Should this test just be removed? - TreeList* parentTL = curTL->parent(); + TreeList* parentTL = curTL->parent(); if (parentTL->left() == curTL) { // curTL is a left child parentTL->set_left(curTL->right()); } else { @@ -685,31 +715,14 @@ return curTL; } -// Based on a simplification of the algorithm by Sleator and Tarjan (JACM 1985). -// The simplifications are the following: -// . we splay only when we delete (not when we insert) -// . we apply a single spay step per deletion/access -// By doing such partial splaying, we reduce the amount of restructuring, -// while getting a reasonably efficient search tree (we think). -// [Measurements will be needed to (in)validate this expectation.] - -template -void BinaryTreeDictionary::semi_splay_step(TreeList* tc) { - // apply a semi-splay step at the given node: - // . if root, norting needs to be done - // . if child of root, splay once - // . else zig-zig or sig-zag depending on path from grandparent - if (root() == tc) return; - warning("*** Splaying not yet implemented; " - "tree operations may be inefficient ***"); -} - -template -void BinaryTreeDictionary::insert_chunk_in_tree(Chunk* fc) { - TreeList *curTL, *prevTL; +template class FreeList_t> +void BinaryTreeDictionary::insert_chunk_in_tree(Chunk_t* fc) { + TreeList *curTL, *prevTL; size_t size = fc->size(); - assert(size >= BinaryTreeDictionary::min_tree_chunk_size, "too small to be a TreeList"); + assert((size >= min_size()), + err_msg(SIZE_FORMAT " is too small to be a TreeChunk " SIZE_FORMAT, + size, min_size())); if (FLSVerifyDictionary) { verify_tree(); } @@ -729,9 +742,9 @@ curTL = curTL->right(); } } - TreeChunk* tc = TreeChunk::as_TreeChunk(fc); + TreeChunk* tc = TreeChunk::as_TreeChunk(fc); // This chunk is being returned to the binary tree. Its embedded - // TreeList should be unused at this point. + // TreeList should be unused at this point. tc->initialize(); if (curTL != NULL) { // exact match tc->set_list(curTL); @@ -739,8 +752,8 @@ } else { // need a new node in tree tc->clear_next(); tc->link_prev(NULL); - TreeList* newTL = TreeList::as_TreeList(tc); - assert(((TreeChunk*)tc)->list() == newTL, + TreeList* newTL = TreeList::as_TreeList(tc); + assert(((TreeChunk*)tc)->list() == newTL, "List was not initialized correctly"); if (prevTL == NULL) { // we are the only tree node assert(root() == NULL, "control point invariant"); @@ -768,30 +781,30 @@ } } -template -size_t BinaryTreeDictionary::max_chunk_size() const { - FreeBlockDictionary::verify_par_locked(); - TreeList* tc = root(); +template class FreeList_t> +size_t BinaryTreeDictionary::max_chunk_size() const { + FreeBlockDictionary::verify_par_locked(); + TreeList* tc = root(); if (tc == NULL) return 0; for (; tc->right() != NULL; tc = tc->right()); return tc->size(); } -template -size_t BinaryTreeDictionary::total_list_length(TreeList* tl) const { +template class FreeList_t> +size_t BinaryTreeDictionary::total_list_length(TreeList* tl) const { size_t res; res = tl->count(); #ifdef ASSERT size_t cnt; - Chunk* tc = tl->head(); + Chunk_t* tc = tl->head(); for (cnt = 0; tc != NULL; tc = tc->next(), cnt++); assert(res == cnt, "The count is not being maintained correctly"); #endif return res; } -template -size_t BinaryTreeDictionary::total_size_in_tree(TreeList* tl) const { +template class FreeList_t> +size_t BinaryTreeDictionary::total_size_in_tree(TreeList* tl) const { if (tl == NULL) return 0; return (tl->size() * total_list_length(tl)) + @@ -799,8 +812,8 @@ total_size_in_tree(tl->right()); } -template -double BinaryTreeDictionary::sum_of_squared_block_sizes(TreeList* const tl) const { +template class FreeList_t> +double BinaryTreeDictionary::sum_of_squared_block_sizes(TreeList* const tl) const { if (tl == NULL) { return 0.0; } @@ -811,8 +824,8 @@ return curr; } -template -size_t BinaryTreeDictionary::total_free_blocks_in_tree(TreeList* tl) const { +template class FreeList_t> +size_t BinaryTreeDictionary::total_free_blocks_in_tree(TreeList* tl) const { if (tl == NULL) return 0; return total_list_length(tl) + @@ -820,28 +833,28 @@ total_free_blocks_in_tree(tl->right()); } -template -size_t BinaryTreeDictionary::num_free_blocks() const { +template class FreeList_t> +size_t BinaryTreeDictionary::num_free_blocks() const { assert(total_free_blocks_in_tree(root()) == total_free_blocks(), "_total_free_blocks inconsistency"); return total_free_blocks(); } -template -size_t BinaryTreeDictionary::tree_height_helper(TreeList* tl) const { +template class FreeList_t> +size_t BinaryTreeDictionary::tree_height_helper(TreeList* tl) const { if (tl == NULL) return 0; return 1 + MAX2(tree_height_helper(tl->left()), tree_height_helper(tl->right())); } -template -size_t BinaryTreeDictionary::treeHeight() const { +template class FreeList_t> +size_t BinaryTreeDictionary::tree_height() const { return tree_height_helper(root()); } -template -size_t BinaryTreeDictionary::total_nodes_helper(TreeList* tl) const { +template class FreeList_t> +size_t BinaryTreeDictionary::total_nodes_helper(TreeList* tl) const { if (tl == NULL) { return 0; } @@ -849,14 +862,18 @@ total_nodes_helper(tl->right()); } -template -size_t BinaryTreeDictionary::total_nodes_in_tree(TreeList* tl) const { +template class FreeList_t> +size_t BinaryTreeDictionary::total_nodes_in_tree(TreeList* tl) const { return total_nodes_helper(root()); } -template -void BinaryTreeDictionary::dict_census_udpate(size_t size, bool split, bool birth){ - TreeList* nd = find_list(size); +template class FreeList_t> +void BinaryTreeDictionary::dict_census_update(size_t size, bool split, bool birth){} + +#ifndef SERIALGC +template <> +void BinaryTreeDictionary::dict_census_update(size_t size, bool split, bool birth){ + TreeList* nd = find_list(size); if (nd) { if (split) { if (birth) { @@ -882,16 +899,26 @@ // This is a birth associated with a LinAB. The chunk // for the LinAB is not in the dictionary. } +#endif // SERIALGC -template -bool BinaryTreeDictionary::coal_dict_over_populated(size_t size) { +template class FreeList_t> +bool BinaryTreeDictionary::coal_dict_over_populated(size_t size) { + // For the general type of freelists, encourage coalescing by + // returning true. + return true; +} + +#ifndef SERIALGC +template <> +bool BinaryTreeDictionary::coal_dict_over_populated(size_t size) { if (FLSAlwaysCoalesceLarge) return true; - TreeList* list_of_size = find_list(size); + TreeList* list_of_size = find_list(size); // None of requested size implies overpopulated. return list_of_size == NULL || list_of_size->coal_desired() <= 0 || list_of_size->count() > list_of_size->coal_desired(); } +#endif // SERIALGC // Closures for walking the binary tree. // do_list() walks the free list in a node applying the closure @@ -899,19 +926,18 @@ // do_tree() walks the nodes in the binary tree applying do_list() // to each list at each node. -template +template class FreeList_t> class TreeCensusClosure : public StackObj { protected: - virtual void do_list(FreeList* fl) = 0; + virtual void do_list(FreeList_t* fl) = 0; public: - virtual void do_tree(TreeList* tl) = 0; + virtual void do_tree(TreeList* tl) = 0; }; -template -class AscendTreeCensusClosure : public TreeCensusClosure { - using TreeCensusClosure::do_list; +template class FreeList_t> +class AscendTreeCensusClosure : public TreeCensusClosure { public: - void do_tree(TreeList* tl) { + void do_tree(TreeList* tl) { if (tl != NULL) { do_tree(tl->left()); do_list(tl); @@ -920,11 +946,10 @@ } }; -template -class DescendTreeCensusClosure : public TreeCensusClosure { - using TreeCensusClosure::do_list; +template class FreeList_t> +class DescendTreeCensusClosure : public TreeCensusClosure { public: - void do_tree(TreeList* tl) { + void do_tree(TreeList* tl) { if (tl != NULL) { do_tree(tl->right()); do_list(tl); @@ -935,8 +960,8 @@ // For each list in the tree, calculate the desired, desired // coalesce, count before sweep, and surplus before sweep. -template -class BeginSweepClosure : public AscendTreeCensusClosure { +template class FreeList_t> +class BeginSweepClosure : public AscendTreeCensusClosure { double _percentage; float _inter_sweep_current; float _inter_sweep_estimate; @@ -951,32 +976,36 @@ _inter_sweep_estimate(inter_sweep_estimate), _intra_sweep_estimate(intra_sweep_estimate) { } - void do_list(FreeList* fl) { + void do_list(FreeList* fl) {} + +#ifndef SERIALGC + void do_list(AdaptiveFreeList* fl) { double coalSurplusPercent = _percentage; fl->compute_desired(_inter_sweep_current, _inter_sweep_estimate, _intra_sweep_estimate); fl->set_coal_desired((ssize_t)((double)fl->desired() * coalSurplusPercent)); fl->set_before_sweep(fl->count()); fl->set_bfr_surp(fl->surplus()); } +#endif // SERIALGC }; // Used to search the tree until a condition is met. // Similar to TreeCensusClosure but searches the // tree and returns promptly when found. -template +template class FreeList_t> class TreeSearchClosure : public StackObj { protected: - virtual bool do_list(FreeList* fl) = 0; + virtual bool do_list(FreeList_t* fl) = 0; public: - virtual bool do_tree(TreeList* tl) = 0; + virtual bool do_tree(TreeList* tl) = 0; }; #if 0 // Don't need this yet but here for symmetry. -template -class AscendTreeSearchClosure : public TreeSearchClosure { +template class FreeList_t> +class AscendTreeSearchClosure : public TreeSearchClosure { public: - bool do_tree(TreeList* tl) { + bool do_tree(TreeList* tl) { if (tl != NULL) { if (do_tree(tl->left())) return true; if (do_list(tl)) return true; @@ -987,11 +1016,10 @@ }; #endif -template -class DescendTreeSearchClosure : public TreeSearchClosure { - using TreeSearchClosure::do_list; +template class FreeList_t> +class DescendTreeSearchClosure : public TreeSearchClosure { public: - bool do_tree(TreeList* tl) { + bool do_tree(TreeList* tl) { if (tl != NULL) { if (do_tree(tl->right())) return true; if (do_list(tl)) return true; @@ -1003,17 +1031,17 @@ // Searches the tree for a chunk that ends at the // specified address. -template -class EndTreeSearchClosure : public DescendTreeSearchClosure { +template class FreeList_t> +class EndTreeSearchClosure : public DescendTreeSearchClosure { HeapWord* _target; - Chunk* _found; + Chunk_t* _found; public: EndTreeSearchClosure(HeapWord* target) : _target(target), _found(NULL) {} - bool do_list(FreeList* fl) { - Chunk* item = fl->head(); + bool do_list(FreeList_t* fl) { + Chunk_t* item = fl->head(); while (item != NULL) { - if (item->end() == _target) { + if (item->end() == (uintptr_t*) _target) { _found = item; return true; } @@ -1021,22 +1049,22 @@ } return false; } - Chunk* found() { return _found; } + Chunk_t* found() { return _found; } }; -template -Chunk* BinaryTreeDictionary::find_chunk_ends_at(HeapWord* target) const { - EndTreeSearchClosure etsc(target); +template class FreeList_t> +Chunk_t* BinaryTreeDictionary