binaryTreeDictionary.cpp revision 3695
/*
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
*
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work; if not, write to the Free Software Foundation,
* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
*
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
* or visit www.oracle.com if you need additional information or have any
* questions.
*
*/
#include "precompiled.hpp"
#include "gc_implementation/shared/allocationStats.hpp"
#include "memory/binaryTreeDictionary.hpp"
#include "runtime/globals.hpp"
#include "utilities/ostream.hpp"
#ifndef SERIALGC
#include "gc_implementation/shared/spaceDecorator.hpp"
#include "gc_implementation/concurrentMarkSweep/freeChunk.hpp"
#endif // SERIALGC
////////////////////////////////////////////////////////////////////////////////
// A binary tree based search structure for free blocks.
// This is currently used in the Concurrent Mark&Sweep implementation.
////////////////////////////////////////////////////////////////////////////////
template <class Chunk>
// Do some assertion checking here.
}
template <class Chunk>
}
}
}
template <class Chunk>
// This first free chunk in the list will be the tree list.
assert(tc->size() >= BinaryTreeDictionary<Chunk>::min_tree_chunk_size, "Chunk is too small for a TreeChunk");
#ifdef ASSERT
#endif
return tl;
}
template <class Chunk>
assert(size >= BinaryTreeDictionary<Chunk>::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).
"Space should be clear or mangled");
return tl;
}
template <class Chunk>
// Is this the first item on the list?
// The "getChunk..." functions for a TreeList<Chunk> 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
// list can be the start of a free range. Free ranges are removed
// from the free lists so that they are not available to be
// 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<Chunk> from the first chunk to the next chunk and update all
// the TreeList<Chunk> pointers in the chunks in the list.
} else {
// copy embedded list.
// Fix the pointer to the list in each chunk in the list.
// 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.
}
// Fix the parent to point to the new TreeList<Chunk>.
} else {
}
}
// Fix the children's parent pointers to point to the
// new list.
}
}
}
} else {
// Removing chunk at tail of list
}
// Chunk is interior to the list
}
// Below this point the embeded TreeList<Chunk> being used for the
// tree node may have changed. Don't use "this"
// TreeList<Chunk>*.
// chunk should still be a free chunk (bit set in _prev)
"Wrong sized chunk in list");
bool prev_found = false;
bool next_found = false;
prev_found = true;
}
next_found = true;
}
}
"list is inconsistent");
)
retTL->decrement_count();
"list invariant");
"list invariant");
return retTL;
}
template <class Chunk>
// which means that the list can never be empty.
}
// 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<Chunk> is embedded in the first TreeChunk<Chunk> in the
// list. See the definition of TreeChunk<Chunk>.
template <class Chunk>
} else {
}
}
template <class Chunk>
"Wrong type of chunk?");
}
template <class Chunk>
retTC = head_as_TreeChunk();
} else {
}
return retTC;
}
// Returns the block with the largest heap address amongst
// those in the list for this size; potentially slow and expensive,
// use with caution!
template <class Chunk>
retTC = head_as_TreeChunk();
} else {
// walk down the list and return the one with the highest
// heap address among chunks of this size.
}
}
}
return retTC;
}
template <class Chunk>
template <class Chunk>
bool adaptive_freelists,
bool splay):
{
}
template <class Chunk>
}
template <class Chunk>
}
template <class Chunk>
}
template <class Chunk>
}
template <class Chunk>
set_totalSize(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 <class Chunk>
BinaryTreeDictionary<Chunk>::getChunkFromTree(size_t size, enum FreeBlockDictionary<Chunk>::Dither dither, bool splay)
{
if (FLSVerifyDictionary) {
verifyTree();
}
// starting at the root, work downwards trying to find match.
// Remember the last node of size too great or too small.
break;
}
} else { // proceed to left sub-tree
}
}
// try and find the next larger size by walking back up the search path
}
"An empty list should not be in the tree");
}
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.
/* Use the hint to find a size with a surplus, and reset the hint. */
"hint points in the wrong direction");
// No useful hint. Set the hint to NULL and go on.
break;
}
// The hint led to a list that has a surplus. Use it.
// Set the hint for the candidate to an overpopulated
// size.
// Change the candidate.
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
}
"A list in the binary tree should not be NULL");
"A chunk of the wrong size was found");
}
if (FLSVerifyDictionary) {
verify();
}
return retTC;
}
template <class Chunk>
break;
}
} else { // proceed to left sub-tree
}
}
return curTL;
}
template <class Chunk>
return false;
} else {
}
}
template <class Chunk>
return curTL->largest_address();
} else {
return NULL;
}
}
// Remove the current chunk from the tree. If it is not the last
// 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 <class Chunk>
bool removing_only_chunk = false;
removing_only_chunk = true;
}
}
}
)
bool complicatedSplice = false;
// Removing this chunk can have the side effect of changing the node
// (TreeList<Chunk>*) in the tree. If the node is the root, update it.
"list is inconsistent");
}
if (tl != replacementTL) {
"If the tree list was replaced, it should not be a NULL list");
}
)
// Does the tree need to be repaired?
if (replacementTL->count() == 0) {
// Find the replacement node for the (soon to be empty) node being removed.
// if we have a single (or no) child, splice child in our stead
// left is NULL so pick right. right may also be NULL.
// right is NULL
} else { // we have both children, so, by patriarchal convention,
// my replacement is least node in right sub-tree
complicatedSplice = true;
}
// newTL is the replacement for the (soon to be empty) node.
// newTL may be NULL.
// should verify; we just cleanly excised our replacement
if (FLSVerifyDictionary) {
verifyTree();
}
// first make newTL my parent's child
// newTL should be root
newTL->clearParent();
}
// replacementTL is a right child
} else { // replacementTL is a left child
}
if (complicatedSplice) { // we need newTL to get replacementTL's
// two children
"newTL should not have encumbrances from the past");
// we'd like to assert as below:
// assert(replacementTL->left() != NULL && replacementTL->right() != NULL,
// "else !complicatedSplice");
// ... however, the above assertion is too strong because we aren't
// guaranteed that replacementTL->right() is still NULL.
// Recall that we removed
// the right sub-tree minimum from replacementTL.
// That may well have been its right
// child! So we'll just assert half of the above:
)
}
"delete without encumbrances");
}
"should return without encumbrances");
if (FLSVerifyDictionary) {
verifyTree();
}
}
// 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 <class Chunk>
// locate the subtree minimum by walking down left branches
// obviously curTL now has at most one child, a right child
} else {
// If the list tl has no left child, then curTL may be
// the right child of parentTL.
}
} else {
// The only use of this method would not pass the root of the
// tree (as indicated by the assertion above that the tree list
// has a parent) but the specification does not explicitly exclude the
// passing of the root so accomodate it.
}
)
// we just excised a (non-root) node, we should still verify all tree invariants
if (FLSVerifyDictionary) {
verifyTree();
}
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)
// 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 <class Chunk>
// 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
warning("*** Splaying not yet implemented; "
"tree operations may be inefficient ***");
}
template <class Chunk>
assert(size >= BinaryTreeDictionary<Chunk>::min_tree_chunk_size, "too small to be a TreeList<Chunk>");
if (FLSVerifyDictionary) {
verifyTree();
}
// work down from the _root, looking for insertion point
break;
} else { // follow right branch
}
}
// This chunk is being returned to the binary tree. Its embedded
// TreeList<Chunk> should be unused at this point.
tc->initialize();
} else { // need a new node in tree
"List was not initialized correctly");
} else { // insert under prevTL ...
} else { // am left child
}
}
}
// Method 'totalSizeInTree' walks through the every block in the
// tree, so it can cause significant performance loss if there are
// many blocks in the tree
if (FLSVerifyDictionary) {
verifyTree();
}
}
template <class Chunk>
}
template <class Chunk>
#ifdef ASSERT
#endif
return res;
}
template <class Chunk>
return 0;
}
template <class Chunk>
return 0.0;
}
return curr;
}
template <class Chunk>
return 0;
return totalListLength(tl) +
}
template <class Chunk>
"_totalFreeBlocks inconsistency");
return totalFreeBlocks();
}
template <class Chunk>
return 0;
}
template <class Chunk>
return treeHeightHelper(root());
}
template <class Chunk>
return 0;
}
}
template <class Chunk>
return totalNodesHelper(root());
}
template <class Chunk>
if (nd) {
if (split) {
if (birth) {
nd->increment_surplus();
} else {
nd->decrement_surplus();
}
} else {
if (birth) {
nd->increment_surplus();
} else {
nd->decrement_surplus();
}
}
}
// A list for this size may not be found (nd == 0) if
// This is a death where the appropriate list is now
// empty and has been removed from the list.
// This is a birth associated with a LinAB. The chunk
// for the LinAB is not in the dictionary.
}
template <class Chunk>
if (FLSAlwaysCoalesceLarge) return true;
// None of requested size implies overpopulated.
}
// Closures for walking the binary tree.
// do_list() walks the free list in a node applying the closure
// to each free chunk in the list
// do_tree() walks the nodes in the binary tree applying do_list()
// to each list at each node.
template <class Chunk>
class TreeCensusClosure : public StackObj {
protected:
public:
};
template <class Chunk>
public:
}
}
};
template <class Chunk>
public:
}
}
};
// For each list in the tree, calculate the desired, desired
// coalesce, count before sweep, and surplus before sweep.
template <class Chunk>
double _percentage;
float _inter_sweep_current;
float _inter_sweep_estimate;
float _intra_sweep_estimate;
public:
BeginSweepClosure(double p, float inter_sweep_current,
float inter_sweep_estimate,
float intra_sweep_estimate) :
_percentage(p),
double coalSurplusPercent = _percentage;
}
};
// Used to search the tree until a condition is met.
// Similar to TreeCensusClosure but searches the
// tree and returns promptly when found.
template <class Chunk>
class TreeSearchClosure : public StackObj {
protected:
public:
};
#if 0 // Don't need this yet but here for symmetry.
template <class Chunk>
class AscendTreeSearchClosure : public TreeSearchClosure {
public:
}
return false;
}
};
#endif
template <class Chunk>
public:
}
return false;
}
};
// Searches the tree for a chunk that ends at the
// specified address.
template <class Chunk>
public:
return true;
}
}
return false;
}
};
template <class Chunk>
}
template <class Chunk>
}
// Closures and methods for calculating total bytes returned to the
// free lists in the tree.
#ifndef PRODUCT
template <class Chunk>
public:
fl->set_returnedBytes(0);
}
};
template <class Chunk>
}
template <class Chunk>
public:
ReturnedBytesClosure() { _dictReturnedBytes = 0; }
}
};
template <class Chunk>
return rbc.dictReturnedBytes();
}
// Count the number of entries in the tree.
template <class Chunk>
public:
count++;
}
};
template <class Chunk>
}
#endif // PRODUCT
// Calculate surpluses for the lists in the tree.
template <class Chunk>
double percentage;
public:
setTreeSurplusClosure(double v) { percentage = v; }
double splitSurplusPercent = percentage;
}
};
template <class Chunk>
}
// Set hints for the lists in the tree.
template <class Chunk>
public:
"Current hint is inconsistent");
}
}
};
template <class Chunk>
}
// Save count before previous sweep and splits and coalesces.
template <class Chunk>
fl->set_coalBirths(0);
fl->set_coalDeaths(0);
fl->set_splitBirths(0);
fl->set_splitDeaths(0);
}
};
template <class Chunk>
}
// Do reporting and post sweep clean up.
template <class Chunk>
// Does walking the tree 3 times hurt?
setTreeHints();
}
}
// Print summary statistics
template <class Chunk>
"------------------------------------\n");
if (freeBlocks > 0) {
}
}
// Print census information - counts, births, deaths, etc.
// for each list in the tree. Also print some summary
// information.
template <class Chunk>
int _print_line;
public:
_print_line = 0;
_totalFree = 0;
}
if (++_print_line >= 40) {
_print_line = 0;
}
}
};
template <class Chunk>
" growth: %8.5f deficit: %8.5f\n",
}
template <class Chunk>
int _print_line;
public:
_print_line = 0;
}
if (++_print_line >= 40) {
_print_line = 0;
}
}
}
};
template <class Chunk>
}
// Verify the following tree invariants:
// . _root has no parent
// . parent and child point to each other
// . each node's key correctly related to that of its child(ren)
template <class Chunk>
totalSize() != 0, "_totalSize should't be 0?");
verifyTreeHelper(root());
}
template <class Chunk>
ct++;
"Chunk should be free");
}
return ct;
}
// Note: this helper is recursive rather than iterative, so use with
// caution on very deep trees; and watch out for stack overflow errors;
// In general, to be used only for debugging.
template <class Chunk>
return;
"parent<-/->left");
"parent<-/->right");;
"parent !> left");
"parent !< left");
"list inconsistency");
"list count is inconsistent");
"list is incorrectly constructed");
}
}
template <class Chunk>
verifyTree();
}
#ifndef SERIALGC
// Explicitly instantiate these types for FreeChunk.
template class BinaryTreeDictionary<FreeChunk>;
#endif // SERIALGC