# HG changeset patch # User jmasa # Date 1333075584 25200 # Node ID 9f059abe8cf27a347f04766ae91339962f44cee4 # Parent 3c91f2c9fd2101f1f5a851fa0543049ccb0341b0 7131629: Generalize the CMS free list code Summary: Make the FreeChunk, FreeList, TreeList, and BinaryTreeDictionary classes usable outside CMS. Reviewed-by: brutisso, johnc, jwilhelm Contributed-by: coleen.phillimore@oracle.com diff -r 3c91f2c9fd21 -r 9f059abe8cf2 src/share/vm/gc_implementation/concurrentMarkSweep/binaryTreeDictionary.cpp --- a/src/share/vm/gc_implementation/concurrentMarkSweep/binaryTreeDictionary.cpp Fri Apr 20 17:13:36 2012 -0700 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,1257 +0,0 @@ -/* - * Copyright (c) 2001, 2010, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * 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/concurrentMarkSweep/binaryTreeDictionary.hpp" -#include "gc_implementation/shared/allocationStats.hpp" -#include "gc_implementation/shared/spaceDecorator.hpp" -#include "memory/space.inline.hpp" -#include "runtime/globals.hpp" -#include "utilities/ostream.hpp" - -//////////////////////////////////////////////////////////////////////////////// -// A binary tree based search structure for free blocks. -// This is currently used in the Concurrent Mark&Sweep implementation. -//////////////////////////////////////////////////////////////////////////////// - -TreeChunk* TreeChunk::as_TreeChunk(FreeChunk* fc) { - // Do some assertion checking here. - return (TreeChunk*) fc; -} - -void TreeChunk::verifyTreeChunkList() 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"); - } - if (nextTC != NULL) { - guarantee(as_TreeChunk(nextTC->prev()) == this, "broken chain"); - guarantee(nextTC->size() == size(), "wrong size"); - nextTC->verifyTreeChunkList(); - } -} - - -TreeList* TreeList::as_TreeList(TreeChunk* tc) { - // This first free chunk in the list will be the tree list. - assert(tc->size() >= sizeof(TreeChunk), "Chunk is too small for a TreeChunk"); - TreeList* tl = tc->embedded_list(); - 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->setParent(NULL); - tl->setLeft(NULL); - tl->setRight(NULL); - return tl; -} - -TreeList* TreeList::as_TreeList(HeapWord* addr, size_t size) { - TreeChunk* tc = (TreeChunk*) addr; - assert(size >= sizeof(TreeChunk), "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->setSize(size); - tc->linkPrev(NULL); - tc->linkNext(NULL); - TreeList* tl = TreeList::as_TreeList(tc); - return tl; -} - -TreeList* TreeList::removeChunkReplaceIfNeeded(TreeChunk* tc) { - - TreeList* retTL = this; - FreeChunk* 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() || - this == parent()->right(), "list is inconsistent"); - assert(tc->isFree(), "Header is not marked correctly"); - assert(head() == NULL || head()->prev() == NULL, "list invariant"); - assert(tail() == NULL || tail()->next() == NULL, "list invariant"); - - FreeChunk* 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 - // 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 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); - set_head(NULL); - } else { - // copy embedded list. - nextTC->set_embedded_list(tc->embedded_list()); - retTL = nextTC->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. - 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. - if (retTL->parent() != NULL) { - if (this == retTL->parent()->left()) { - retTL->parent()->setLeft(retTL); - } else { - assert(this == retTL->parent()->right(), "Parent is incorrect"); - retTL->parent()->setRight(retTL); - } - } - // Fix the children's parent pointers to point to the - // new list. - assert(right() == retTL->right(), "Should have been copied"); - if (retTL->right() != NULL) { - retTL->right()->setParent(retTL); - } - assert(left() == retTL->left(), "Should have been copied"); - if (retTL->left() != NULL) { - retTL->left()->setParent(retTL); - } - retTL->link_head(nextTC); - assert(nextTC->isFree(), "Should be a free chunk"); - } - } else { - if (nextTC == NULL) { - // Removing chunk at tail of list - link_tail(prevFC); - } - // Chunk is interior to the list - prevFC->linkAfter(nextTC); - } - - // Below this point the embeded TreeList being used for the - // tree node may have changed. Don't use "this" - // 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"); - debug_only( - tc->linkPrev(NULL); - tc->linkNext(NULL); - tc->set_list(NULL); - bool prev_found = false; - bool next_found = false; - for (FreeChunk* curFC = retTL->head(); - curFC != NULL; curFC = curFC->next()) { - assert(curFC != tc, "Chunk is still in list"); - if (curFC == prevFC) { - prev_found = true; - } - if (curFC == nextTC) { - next_found = true; - } - } - assert(prevFC == NULL || prev_found, "Chunk was lost from list"); - assert(nextTC == NULL || next_found, "Chunk was lost from list"); - assert(retTL->parent() == NULL || - retTL == retTL->parent()->left() || - retTL == retTL->parent()->right(), - "list is inconsistent"); - ) - retTL->decrement_count(); - - assert(tc->isFree(), "Should still be a free chunk"); - assert(retTL->head() == NULL || retTL->head()->prev() == NULL, - "list invariant"); - assert(retTL->tail() == NULL || retTL->tail()->next() == NULL, - "list invariant"); - return retTL; -} -void TreeList::returnChunkAtTail(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"); - // which means that the list can never be empty. - assert(!verifyChunkInFreeLists(chunk), "Double entry"); - assert(head() == NULL || head()->prev() == NULL, "list invariant"); - assert(tail() == NULL || tail()->next() == NULL, "list invariant"); - - FreeChunk* fc = tail(); - fc->linkAfter(chunk); - link_tail(chunk); - - assert(!tail() || size() == tail()->size(), "Wrong sized chunk in list"); - increment_count(); - debug_only(increment_returnedBytes_by(chunk->size()*sizeof(HeapWord));) - assert(head() == NULL || head()->prev() == NULL, "list invariant"); - assert(tail() == NULL || tail()->next() == NULL, "list invariant"); -} - -// 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. -void TreeList::returnChunkAtHead(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"); - assert(!verifyChunkInFreeLists(chunk), "Double entry"); - assert(head() == NULL || head()->prev() == NULL, "list invariant"); - assert(tail() == NULL || tail()->next() == NULL, "list invariant"); - - FreeChunk* fc = head()->next(); - if (fc != NULL) { - chunk->linkAfter(fc); - } else { - assert(tail() == NULL, "List is inconsistent"); - link_tail(chunk); - } - head()->linkAfter(chunk); - assert(!head() || size() == head()->size(), "Wrong sized chunk in list"); - increment_count(); - debug_only(increment_returnedBytes_by(chunk->size()*sizeof(HeapWord));) - assert(head() == NULL || head()->prev() == NULL, "list invariant"); - assert(tail() == NULL || tail()->next() == NULL, "list invariant"); -} - -TreeChunk* TreeList::head_as_TreeChunk() { - assert(head() == NULL || TreeChunk::as_TreeChunk(head())->list() == this, - "Wrong type of chunk?"); - return TreeChunk::as_TreeChunk(head()); -} - -TreeChunk* TreeList::first_available() { - assert(head() != NULL, "The head of the list cannot be NULL"); - FreeChunk* fc = head()->next(); - TreeChunk* retTC; - if (fc == NULL) { - retTC = head_as_TreeChunk(); - } else { - retTC = TreeChunk::as_TreeChunk(fc); - } - assert(retTC->list() == this, "Wrong type of chunk."); - 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! -TreeChunk* TreeList::largest_address() { - assert(head() != NULL, "The head of the list cannot be NULL"); - FreeChunk* 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. - FreeChunk* last = fc; - while (fc->next() != NULL) { - if ((HeapWord*)last < (HeapWord*)fc) { - last = fc; - } - fc = fc->next(); - } - retTC = TreeChunk::as_TreeChunk(last); - } - assert(retTC->list() == this, "Wrong type of chunk."); - return retTC; -} - -BinaryTreeDictionary::BinaryTreeDictionary(MemRegion mr, bool splay): - _splay(splay) -{ - assert(mr.byte_size() > MIN_TREE_CHUNK_SIZE, "minimum chunk size"); - - reset(mr); - assert(root()->left() == NULL, "reset check failed"); - assert(root()->right() == NULL, "reset check failed"); - assert(root()->head()->next() == NULL, "reset check failed"); - assert(root()->head()->prev() == NULL, "reset check failed"); - assert(totalSize() == root()->size(), "reset check failed"); - assert(totalFreeBlocks() == 1, "reset check failed"); -} - -void BinaryTreeDictionary::inc_totalSize(size_t inc) { - _totalSize = _totalSize + inc; -} - -void BinaryTreeDictionary::dec_totalSize(size_t dec) { - _totalSize = _totalSize - dec; -} - -void BinaryTreeDictionary::reset(MemRegion mr) { - assert(mr.byte_size() > MIN_TREE_CHUNK_SIZE, "minimum chunk size"); - set_root(TreeList::as_TreeList(mr.start(), mr.word_size())); - set_totalSize(mr.word_size()); - set_totalFreeBlocks(1); -} - -void BinaryTreeDictionary::reset(HeapWord* addr, size_t byte_size) { - MemRegion mr(addr, heap_word_size(byte_size)); - reset(mr); -} - -void BinaryTreeDictionary::reset() { - set_root(NULL); - set_totalSize(0); - set_totalFreeBlocks(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. -TreeChunk* -BinaryTreeDictionary::getChunkFromTree(size_t size, Dither dither, bool splay) -{ - TreeList *curTL, *prevTL; - TreeChunk* retTC = NULL; - assert(size >= MIN_TREE_CHUNK_SIZE, "minimum chunk size"); - if (FLSVerifyDictionary) { - verifyTree(); - } - // starting at the root, work downwards trying to find match. - // Remember the last node of size too great or too small. - for (prevTL = curTL = root(); curTL != NULL;) { - if (curTL->size() == size) { // exact match - break; - } - prevTL = curTL; - if (curTL->size() < size) { // proceed to right sub-tree - curTL = curTL->right(); - } else { // proceed to left sub-tree - assert(curTL->size() > size, "size inconsistency"); - curTL = curTL->left(); - } - } - if (curTL == NULL) { // couldn't find exact match - // try and find the next larger size by walking back up the search path - for (curTL = prevTL; curTL != NULL;) { - if (curTL->size() >= size) break; - else curTL = curTL->parent(); - } - assert(curTL == NULL || curTL->count() > 0, - "An empty list should not be in the tree"); - } - if (curTL != NULL) { - assert(curTL->size() >= size, "size inconsistency"); - if (UseCMSAdaptiveFreeLists) { - - // 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 = findList(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) { - semiSplayStep(curTL); - } - retTC = curTL->first_available(); - assert((retTC != NULL) && (curTL->count() > 0), - "A list in the binary tree should not be NULL"); - assert(retTC->size() >= size, - "A chunk of the wrong size was found"); - removeChunkFromTree(retTC); - assert(retTC->isFree(), "Header is not marked correctly"); - } - - if (FLSVerifyDictionary) { - verify(); - } - return retTC; -} - -TreeList* BinaryTreeDictionary::findList(size_t size) const { - TreeList* curTL; - for (curTL = root(); curTL != NULL;) { - if (curTL->size() == size) { // exact match - break; - } - - if (curTL->size() < size) { // proceed to right sub-tree - curTL = curTL->right(); - } else { // proceed to left sub-tree - assert(curTL->size() > size, "size inconsistency"); - curTL = curTL->left(); - } - } - return curTL; -} - - -bool BinaryTreeDictionary::verifyChunkInFreeLists(FreeChunk* tc) const { - size_t size = tc->size(); - TreeList* tl = findList(size); - if (tl == NULL) { - return false; - } else { - return tl->verifyChunkInFreeLists(tc); - } -} - -FreeChunk* BinaryTreeDictionary::findLargestDict() const { - TreeList *curTL = root(); - if (curTL != NULL) { - while(curTL->right() != NULL) curTL = curTL->right(); - 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. -TreeChunk* -BinaryTreeDictionary::removeChunkFromTree(TreeChunk* tc) { - assert(tc != NULL, "Should not call with a NULL chunk"); - assert(tc->isFree(), "Header is not marked correctly"); - - TreeList *newTL, *parentTL; - TreeChunk* retTC; - TreeList* tl = tc->list(); - debug_only( - bool removing_only_chunk = false; - if (tl == _root) { - if ((_root->left() == NULL) && (_root->right() == NULL)) { - if (_root->count() == 1) { - assert(_root->head() == tc, "Should only be this one chunk"); - removing_only_chunk = true; - } - } - } - ) - assert(tl != NULL, "List should be set"); - assert(tl->parent() == NULL || tl == tl->parent()->left() || - tl == tl->parent()->right(), "list is inconsistent"); - - bool complicatedSplice = false; - - 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->removeChunkReplaceIfNeeded(tc); - assert(tc->isFree(), "Chunk should still be free"); - assert(replacementTL->parent() == NULL || - replacementTL == replacementTL->parent()->left() || - replacementTL == replacementTL->parent()->right(), - "list is inconsistent"); - if (tl == root()) { - assert(replacementTL->parent() == NULL, "Incorrectly replacing root"); - set_root(replacementTL); - } - debug_only( - 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(); - assert(rhl == replacementTL, "Broken head"); - assert(rtl == replacementTL, "Broken tail"); - assert(replacementTL->size() == tc->size(), "Broken size"); - } - ) - - // Does the tree need to be repaired? - if (replacementTL->count() == 0) { - assert(replacementTL->head() == NULL && - replacementTL->tail() == NULL, "list count is incorrect"); - // 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 - if (replacementTL->left() == NULL) { - // left is NULL so pick right. right may also be NULL. - newTL = replacementTL->right(); - debug_only(replacementTL->clearRight();) - } else if (replacementTL->right() == NULL) { - // right is NULL - newTL = replacementTL->left(); - debug_only(replacementTL->clearLeft();) - } else { // we have both children, so, by patriarchal convention, - // my replacement is least node in right sub-tree - complicatedSplice = true; - newTL = removeTreeMinimum(replacementTL->right()); - assert(newTL != NULL && newTL->left() == NULL && - newTL->right() == NULL, "sub-tree minimum exists"); - } - // 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 - if ((parentTL = replacementTL->parent()) == NULL) { - // newTL should be root - assert(tl == root(), "Incorrectly replacing root"); - set_root(newTL); - if (newTL != NULL) { - newTL->clearParent(); - } - } else if (parentTL->right() == replacementTL) { - // replacementTL is a right child - parentTL->setRight(newTL); - } else { // replacementTL is a left child - assert(parentTL->left() == replacementTL, "should be left child"); - parentTL->setLeft(newTL); - } - debug_only(replacementTL->clearParent();) - if (complicatedSplice) { // we need newTL to get replacementTL's - // two children - assert(newTL != NULL && - newTL->left() == NULL && newTL->right() == NULL, - "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: - assert(replacementTL->left() != NULL, "else !complicatedSplice"); - newTL->setLeft(replacementTL->left()); - newTL->setRight(replacementTL->right()); - debug_only( - replacementTL->clearRight(); - replacementTL->clearLeft(); - ) - } - assert(replacementTL->right() == NULL && - replacementTL->left() == NULL && - replacementTL->parent() == NULL, - "delete without encumbrances"); - } - - assert(totalSize() >= retTC->size(), "Incorrect total size"); - dec_totalSize(retTC->size()); // size book-keeping - assert(totalFreeBlocks() > 0, "Incorrect total count"); - set_totalFreeBlocks(totalFreeBlocks() - 1); - - assert(retTC != NULL, "null chunk?"); - assert(retTC->prev() == NULL && retTC->next() == NULL, - "should return without encumbrances"); - if (FLSVerifyDictionary) { - verifyTree(); - } - assert(!removing_only_chunk || _root == NULL, "root should be NULL"); - 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. -TreeList* BinaryTreeDictionary::removeTreeMinimum(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; - 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(); - if (parentTL->left() == curTL) { // curTL is a left child - parentTL->setLeft(curTL->right()); - } else { - // If the list tl has no left child, then curTL may be - // the right child of parentTL. - assert(parentTL->right() == curTL, "should be a right child"); - parentTL->setRight(curTL->right()); - } - } 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. - set_root(NULL); - } - debug_only( - curTL->clearParent(); // Test if this needs to be cleared - curTL->clearRight(); // recall, above, left child is already null - ) - // 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) -// . 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.] - -void BinaryTreeDictionary::semiSplayStep(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 ***"); -} - -void BinaryTreeDictionary::insertChunkInTree(FreeChunk* fc) { - TreeList *curTL, *prevTL; - size_t size = fc->size(); - - assert(size >= MIN_TREE_CHUNK_SIZE, "too small to be a TreeList"); - if (FLSVerifyDictionary) { - verifyTree(); - } - // XXX: do i need to clear the FreeChunk fields, let me do it just in case - // Revisit this later - - fc->clearNext(); - fc->linkPrev(NULL); - - // work down from the _root, looking for insertion point - for (prevTL = curTL = root(); curTL != NULL;) { - if (curTL->size() == size) // exact match - break; - prevTL = curTL; - if (curTL->size() > size) { // follow left branch - curTL = curTL->left(); - } else { // follow right branch - assert(curTL->size() < size, "size inconsistency"); - curTL = curTL->right(); - } - } - TreeChunk* tc = TreeChunk::as_TreeChunk(fc); - // This chunk is being returned to the binary tree. Its embedded - // TreeList should be unused at this point. - tc->initialize(); - if (curTL != NULL) { // exact match - tc->set_list(curTL); - curTL->returnChunkAtTail(tc); - } else { // need a new node in tree - tc->clearNext(); - tc->linkPrev(NULL); - 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"); - set_root(newTL); - } else { // insert under prevTL ... - if (prevTL->size() < size) { // am right child - assert(prevTL->right() == NULL, "control point invariant"); - prevTL->setRight(newTL); - } else { // am left child - assert(prevTL->size() > size && prevTL->left() == NULL, "cpt pt inv"); - prevTL->setLeft(newTL); - } - } - } - assert(tc->list() != NULL, "Tree list should be set"); - - inc_totalSize(size); - // 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 - assert(!FLSVerifyDictionary || totalSizeInTree(root()) == totalSize(), "_totalSize inconsistency"); - set_totalFreeBlocks(totalFreeBlocks() + 1); - if (FLSVerifyDictionary) { - verifyTree(); - } -} - -size_t BinaryTreeDictionary::maxChunkSize() const { - verify_par_locked(); - TreeList* tc = root(); - if (tc == NULL) return 0; - for (; tc->right() != NULL; tc = tc->right()); - return tc->size(); -} - -size_t BinaryTreeDictionary::totalListLength(TreeList* tl) const { - size_t res; - res = tl->count(); -#ifdef ASSERT - size_t cnt; - FreeChunk* 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; -} - -size_t BinaryTreeDictionary::totalSizeInTree(TreeList* tl) const { - if (tl == NULL) - return 0; - return (tl->size() * totalListLength(tl)) + - totalSizeInTree(tl->left()) + - totalSizeInTree(tl->right()); -} - -double BinaryTreeDictionary::sum_of_squared_block_sizes(TreeList* const tl) const { - if (tl == NULL) { - return 0.0; - } - double size = (double)(tl->size()); - double curr = size * size * totalListLength(tl); - curr += sum_of_squared_block_sizes(tl->left()); - curr += sum_of_squared_block_sizes(tl->right()); - return curr; -} - -size_t BinaryTreeDictionary::totalFreeBlocksInTree(TreeList* tl) const { - if (tl == NULL) - return 0; - return totalListLength(tl) + - totalFreeBlocksInTree(tl->left()) + - totalFreeBlocksInTree(tl->right()); -} - -size_t BinaryTreeDictionary::numFreeBlocks() const { - assert(totalFreeBlocksInTree(root()) == totalFreeBlocks(), - "_totalFreeBlocks inconsistency"); - return totalFreeBlocks(); -} - -size_t BinaryTreeDictionary::treeHeightHelper(TreeList* tl) const { - if (tl == NULL) - return 0; - return 1 + MAX2(treeHeightHelper(tl->left()), - treeHeightHelper(tl->right())); -} - -size_t BinaryTreeDictionary::treeHeight() const { - return treeHeightHelper(root()); -} - -size_t BinaryTreeDictionary::totalNodesHelper(TreeList* tl) const { - if (tl == NULL) { - return 0; - } - return 1 + totalNodesHelper(tl->left()) + - totalNodesHelper(tl->right()); -} - -size_t BinaryTreeDictionary::totalNodesInTree(TreeList* tl) const { - return totalNodesHelper(root()); -} - -void BinaryTreeDictionary::dictCensusUpdate(size_t size, bool split, bool birth){ - TreeList* nd = findList(size); - if (nd) { - if (split) { - if (birth) { - nd->increment_splitBirths(); - nd->increment_surplus(); - } else { - nd->increment_splitDeaths(); - nd->decrement_surplus(); - } - } else { - if (birth) { - nd->increment_coalBirths(); - nd->increment_surplus(); - } else { - nd->increment_coalDeaths(); - 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. -} - -bool BinaryTreeDictionary::coalDictOverPopulated(size_t size) { - if (FLSAlwaysCoalesceLarge) return true; - - TreeList* list_of_size = findList(size); - // None of requested size implies overpopulated. - return list_of_size == NULL || list_of_size->coalDesired() <= 0 || - list_of_size->count() > list_of_size->coalDesired(); -} - -// 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. - -class TreeCensusClosure : public StackObj { - protected: - virtual void do_list(FreeList* fl) = 0; - public: - virtual void do_tree(TreeList* tl) = 0; -}; - -class AscendTreeCensusClosure : public TreeCensusClosure { - public: - void do_tree(TreeList* tl) { - if (tl != NULL) { - do_tree(tl->left()); - do_list(tl); - do_tree(tl->right()); - } - } -}; - -class DescendTreeCensusClosure : public TreeCensusClosure { - public: - void do_tree(TreeList* tl) { - if (tl != NULL) { - do_tree(tl->right()); - do_list(tl); - do_tree(tl->left()); - } - } -}; - -// For each list in the tree, calculate the desired, desired -// coalesce, count before sweep, and surplus before sweep. -class BeginSweepClosure : public AscendTreeCensusClosure { - 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), - _inter_sweep_current(inter_sweep_current), - _inter_sweep_estimate(inter_sweep_estimate), - _intra_sweep_estimate(intra_sweep_estimate) { } - - void do_list(FreeList* fl) { - double coalSurplusPercent = _percentage; - fl->compute_desired(_inter_sweep_current, _inter_sweep_estimate, _intra_sweep_estimate); - fl->set_coalDesired((ssize_t)((double)fl->desired() * coalSurplusPercent)); - fl->set_beforeSweep(fl->count()); - fl->set_bfrSurp(fl->surplus()); - } -}; - -// Used to search the tree until a condition is met. -// Similar to TreeCensusClosure but searches the -// tree and returns promptly when found. - -class TreeSearchClosure : public StackObj { - protected: - virtual bool do_list(FreeList* fl) = 0; - public: - virtual bool do_tree(TreeList* tl) = 0; -}; - -#if 0 // Don't need this yet but here for symmetry. -class AscendTreeSearchClosure : public TreeSearchClosure { - public: - bool do_tree(TreeList* tl) { - if (tl != NULL) { - if (do_tree(tl->left())) return true; - if (do_list(tl)) return true; - if (do_tree(tl->right())) return true; - } - return false; - } -}; -#endif - -class DescendTreeSearchClosure : public TreeSearchClosure { - public: - bool do_tree(TreeList* tl) { - if (tl != NULL) { - if (do_tree(tl->right())) return true; - if (do_list(tl)) return true; - if (do_tree(tl->left())) return true; - } - return false; - } -}; - -// Searches the tree for a chunk that ends at the -// specified address. -class EndTreeSearchClosure : public DescendTreeSearchClosure { - HeapWord* _target; - FreeChunk* _found; - - public: - EndTreeSearchClosure(HeapWord* target) : _target(target), _found(NULL) {} - bool do_list(FreeList* fl) { - FreeChunk* item = fl->head(); - while (item != NULL) { - if (item->end() == _target) { - _found = item; - return true; - } - item = item->next(); - } - return false; - } - FreeChunk* found() { return _found; } -}; - -FreeChunk* BinaryTreeDictionary::find_chunk_ends_at(HeapWord* target) const { - EndTreeSearchClosure etsc(target); - bool found_target = etsc.do_tree(root()); - assert(found_target || etsc.found() == NULL, "Consistency check"); - assert(!found_target || etsc.found() != NULL, "Consistency check"); - return etsc.found(); -} - -void BinaryTreeDictionary::beginSweepDictCensus(double coalSurplusPercent, - float inter_sweep_current, float inter_sweep_estimate, float intra_sweep_estimate) { - BeginSweepClosure bsc(coalSurplusPercent, inter_sweep_current, - inter_sweep_estimate, - intra_sweep_estimate); - bsc.do_tree(root()); -} - -// Closures and methods for calculating total bytes returned to the -// free lists in the tree. -NOT_PRODUCT( - class InitializeDictReturnedBytesClosure : public AscendTreeCensusClosure { - public: - void do_list(FreeList* fl) { - fl->set_returnedBytes(0); - } - }; - - void BinaryTreeDictionary::initializeDictReturnedBytes() { - InitializeDictReturnedBytesClosure idrb; - idrb.do_tree(root()); - } - - class ReturnedBytesClosure : public AscendTreeCensusClosure { - size_t _dictReturnedBytes; - public: - ReturnedBytesClosure() { _dictReturnedBytes = 0; } - void do_list(FreeList* fl) { - _dictReturnedBytes += fl->returnedBytes(); - } - size_t dictReturnedBytes() { return _dictReturnedBytes; } - }; - - size_t BinaryTreeDictionary::sumDictReturnedBytes() { - ReturnedBytesClosure rbc; - rbc.do_tree(root()); - - return rbc.dictReturnedBytes(); - } - - // Count the number of entries in the tree. - class treeCountClosure : public DescendTreeCensusClosure { - public: - uint count; - treeCountClosure(uint c) { count = c; } - void do_list(FreeList* fl) { - count++; - } - }; - - size_t BinaryTreeDictionary::totalCount() { - treeCountClosure ctc(0); - ctc.do_tree(root()); - return ctc.count; - } -) - -// Calculate surpluses for the lists in the tree. -class setTreeSurplusClosure : public AscendTreeCensusClosure { - double percentage; - public: - setTreeSurplusClosure(double v) { percentage = v; } - void do_list(FreeList* fl) { - double splitSurplusPercent = percentage; - fl->set_surplus(fl->count() - - (ssize_t)((double)fl->desired() * splitSurplusPercent)); - } -}; - -void BinaryTreeDictionary::setTreeSurplus(double splitSurplusPercent) { - setTreeSurplusClosure sts(splitSurplusPercent); - sts.do_tree(root()); -} - -// Set hints for the lists in the tree. -class setTreeHintsClosure : public DescendTreeCensusClosure { - size_t hint; - public: - setTreeHintsClosure(size_t v) { hint = v; } - void do_list(FreeList* fl) { - fl->set_hint(hint); - assert(fl->hint() == 0 || fl->hint() > fl->size(), - "Current hint is inconsistent"); - if (fl->surplus() > 0) { - hint = fl->size(); - } - } -}; - -void BinaryTreeDictionary::setTreeHints(void) { - setTreeHintsClosure sth(0); - sth.do_tree(root()); -} - -// Save count before previous sweep and splits and coalesces. -class clearTreeCensusClosure : public AscendTreeCensusClosure { - void do_list(FreeList* fl) { - fl->set_prevSweep(fl->count()); - fl->set_coalBirths(0); - fl->set_coalDeaths(0); - fl->set_splitBirths(0); - fl->set_splitDeaths(0); - } -}; - -void BinaryTreeDictionary::clearTreeCensus(void) { - clearTreeCensusClosure ctc; - ctc.do_tree(root()); -} - -// Do reporting and post sweep clean up. -void BinaryTreeDictionary::endSweepDictCensus(double splitSurplusPercent) { - // Does walking the tree 3 times hurt? - setTreeSurplus(splitSurplusPercent); - setTreeHints(); - if (PrintGC && Verbose) { - reportStatistics(); - } - clearTreeCensus(); -} - -// Print summary statistics -void BinaryTreeDictionary::reportStatistics() const { - verify_par_locked(); - gclog_or_tty->print("Statistics for BinaryTreeDictionary:\n" - "------------------------------------\n"); - size_t totalSize = totalChunkSize(debug_only(NULL)); - size_t freeBlocks = numFreeBlocks(); - gclog_or_tty->print("Total Free Space: %d\n", totalSize); - gclog_or_tty->print("Max Chunk Size: %d\n", maxChunkSize()); - gclog_or_tty->print("Number of Blocks: %d\n", freeBlocks); - if (freeBlocks > 0) { - gclog_or_tty->print("Av. Block Size: %d\n", totalSize/freeBlocks); - } - gclog_or_tty->print("Tree Height: %d\n", treeHeight()); -} - -// Print census information - counts, births, deaths, etc. -// for each list in the tree. Also print some summary -// information. -class PrintTreeCensusClosure : public AscendTreeCensusClosure { - int _print_line; - size_t _totalFree; - FreeList _total; - - public: - PrintTreeCensusClosure() { - _print_line = 0; - _totalFree = 0; - } - FreeList* total() { return &_total; } - size_t totalFree() { return _totalFree; } - void do_list(FreeList* fl) { - if (++_print_line >= 40) { - FreeList::print_labels_on(gclog_or_tty, "size"); - _print_line = 0; - } - fl->print_on(gclog_or_tty); - _totalFree += fl->count() * fl->size() ; - total()->set_count( total()->count() + fl->count() ); - total()->set_bfrSurp( total()->bfrSurp() + fl->bfrSurp() ); - total()->set_surplus( total()->splitDeaths() + fl->surplus() ); - total()->set_desired( total()->desired() + fl->desired() ); - total()->set_prevSweep( total()->prevSweep() + fl->prevSweep() ); - total()->set_beforeSweep(total()->beforeSweep() + fl->beforeSweep()); - total()->set_coalBirths( total()->coalBirths() + fl->coalBirths() ); - total()->set_coalDeaths( total()->coalDeaths() + fl->coalDeaths() ); - total()->set_splitBirths(total()->splitBirths() + fl->splitBirths()); - total()->set_splitDeaths(total()->splitDeaths() + fl->splitDeaths()); - } -}; - -void BinaryTreeDictionary::printDictCensus(void) const { - - gclog_or_tty->print("\nBinaryTree\n"); - FreeList::print_labels_on(gclog_or_tty, "size"); - PrintTreeCensusClosure ptc; - ptc.do_tree(root()); - - FreeList* total = ptc.total(); - FreeList::print_labels_on(gclog_or_tty, " "); - total->print_on(gclog_or_tty, "TOTAL\t"); - gclog_or_tty->print( - "totalFree(words): " SIZE_FORMAT_W(16) - " growth: %8.5f deficit: %8.5f\n", - ptc.totalFree(), - (double)(total->splitBirths() + total->coalBirths() - - total->splitDeaths() - total->coalDeaths()) - /(total->prevSweep() != 0 ? (double)total->prevSweep() : 1.0), - (double)(total->desired() - total->count()) - /(total->desired() != 0 ? (double)total->desired() : 1.0)); -} - -class PrintFreeListsClosure : public AscendTreeCensusClosure { - outputStream* _st; - int _print_line; - - public: - PrintFreeListsClosure(outputStream* st) { - _st = st; - _print_line = 0; - } - void do_list(FreeList* fl) { - if (++_print_line >= 40) { - FreeList::print_labels_on(_st, "size"); - _print_line = 0; - } - fl->print_on(gclog_or_tty); - size_t sz = fl->size(); - for (FreeChunk* fc = fl->head(); fc != NULL; - fc = fc->next()) { - _st->print_cr("\t[" PTR_FORMAT "," PTR_FORMAT ") %s", - fc, (HeapWord*)fc + sz, - fc->cantCoalesce() ? "\t CC" : ""); - } - } -}; - -void BinaryTreeDictionary::print_free_lists(outputStream* st) const { - - FreeList::print_labels_on(st, "size"); - PrintFreeListsClosure pflc(st); - pflc.do_tree(root()); -} - -// 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) -void BinaryTreeDictionary::verifyTree() const { - guarantee(root() == NULL || totalFreeBlocks() == 0 || - totalSize() != 0, "_totalSize should't be 0?"); - guarantee(root() == NULL || root()->parent() == NULL, "_root shouldn't have parent"); - verifyTreeHelper(root()); -} - -size_t BinaryTreeDictionary::verifyPrevFreePtrs(TreeList* tl) { - size_t ct = 0; - for (FreeChunk* curFC = tl->head(); curFC != NULL; curFC = curFC->next()) { - ct++; - assert(curFC->prev() == NULL || curFC->prev()->isFree(), - "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. -void BinaryTreeDictionary::verifyTreeHelper(TreeList* tl) const { - if (tl == NULL) - return; - guarantee(tl->size() != 0, "A list must has a size"); - guarantee(tl->left() == NULL || tl->left()->parent() == tl, - "parent<-/->left"); - guarantee(tl->right() == NULL || tl->right()->parent() == tl, - "parent<-/->right");; - guarantee(tl->left() == NULL || tl->left()->size() < tl->size(), - "parent !> left"); - guarantee(tl->right() == NULL || tl->right()->size() > tl->size(), - "parent !< left"); - guarantee(tl->head() == NULL || tl->head()->isFree(), "!Free"); - guarantee(tl->head() == NULL || tl->head_as_TreeChunk()->list() == tl, - "list inconsistency"); - guarantee(tl->count() > 0 || (tl->head() == NULL && tl->tail() == NULL), - "list count is inconsistent"); - guarantee(tl->count() > 1 || tl->head() == tl->tail(), - "list is incorrectly constructed"); - size_t count = verifyPrevFreePtrs(tl); - guarantee(count == (size_t)tl->count(), "Node count is incorrect"); - if (tl->head() != NULL) { - tl->head_as_TreeChunk()->verifyTreeChunkList(); - } - verifyTreeHelper(tl->left()); - verifyTreeHelper(tl->right()); -} - -void BinaryTreeDictionary::verify() const { - verifyTree(); - guarantee(totalSize() == totalSizeInTree(root()), "Total Size inconsistency"); -} diff -r 3c91f2c9fd21 -r 9f059abe8cf2 src/share/vm/gc_implementation/concurrentMarkSweep/binaryTreeDictionary.hpp --- a/src/share/vm/gc_implementation/concurrentMarkSweep/binaryTreeDictionary.hpp Fri Apr 20 17:13:36 2012 -0700 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,296 +0,0 @@ -/* - * Copyright (c) 2001, 2010, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * 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. - * - */ - -#ifndef SHARE_VM_GC_IMPLEMENTATION_CONCURRENTMARKSWEEP_BINARYTREEDICTIONARY_HPP -#define SHARE_VM_GC_IMPLEMENTATION_CONCURRENTMARKSWEEP_BINARYTREEDICTIONARY_HPP - -#include "gc_implementation/concurrentMarkSweep/freeBlockDictionary.hpp" -#include "gc_implementation/concurrentMarkSweep/freeList.hpp" - -/* - * A binary tree based search structure for free blocks. - * This is currently used in the Concurrent Mark&Sweep implementation. - */ - -// A TreeList is a FreeList which can be used to maintain a -// binary tree of free lists. - -class TreeChunk; -class BinaryTreeDictionary; -class AscendTreeCensusClosure; -class DescendTreeCensusClosure; -class DescendTreeSearchClosure; - -class TreeList: public FreeList { - friend class TreeChunk; - friend class BinaryTreeDictionary; - friend class AscendTreeCensusClosure; - friend class DescendTreeCensusClosure; - friend class DescendTreeSearchClosure; - - protected: - TreeList* parent() const { return _parent; } - TreeList* left() const { return _left; } - TreeList* right() const { return _right; } - - // Accessors for links in tree. - - void setLeft(TreeList* tl) { - _left = tl; - if (tl != NULL) - tl->setParent(this); - } - void setRight(TreeList* tl) { - _right = tl; - if (tl != NULL) - tl->setParent(this); - } - void setParent(TreeList* tl) { _parent = tl; } - - void clearLeft() { _left = NULL; } - void clearRight() { _right = NULL; } - void clearParent() { _parent = NULL; } - void initialize() { clearLeft(); clearRight(), clearParent(); } - - // For constructing a TreeList from a Tree chunk or - // address and size. - static TreeList* as_TreeList(TreeChunk* tc); - static TreeList* as_TreeList(HeapWord* addr, size_t size); - - // Returns the head of the free list as a pointer to a TreeChunk. - TreeChunk* head_as_TreeChunk(); - - // Returns the first available chunk in the free list as a pointer - // to a TreeChunk. - TreeChunk* first_available(); - - // Returns the block with the largest heap address amongst - // those in the list for this size; potentially slow and expensive, - // use with caution! - TreeChunk* largest_address(); - - // removeChunkReplaceIfNeeded() removes the given "tc" from the TreeList. - // If "tc" is the first chunk in the list, it is also the - // TreeList that is the node in the tree. removeChunkReplaceIfNeeded() - // returns the possibly replaced TreeList* for the node in - // the tree. It also updates the parent of the original - // node to point to the new node. - TreeList* removeChunkReplaceIfNeeded(TreeChunk* tc); - // See FreeList. - void returnChunkAtHead(TreeChunk* tc); - void returnChunkAtTail(TreeChunk* tc); -}; - -// A TreeChunk is a subclass of a FreeChunk that additionally -// maintains a pointer to the free list on which it is currently -// linked. -// A TreeChunk is also used as a node in the binary tree. This -// allows the binary tree to be maintained without any additional -// storage (the free chunks are used). In a binary tree the first -// chunk in the free list is also the tree node. Note that the -// TreeChunk has an embedded TreeList for this purpose. Because -// the first chunk in the list is distinguished in this fashion -// (also is the node in the tree), it is the last chunk to be found -// on the free list for a node in the tree and is only removed if -// it is the last chunk on the free list. - -class TreeChunk : public FreeChunk { - friend class TreeList; - TreeList* _list; - TreeList _embedded_list; // if non-null, this chunk is on _list - protected: - TreeList* embedded_list() const { return (TreeList*) &_embedded_list; } - void set_embedded_list(TreeList* v) { _embedded_list = *v; } - public: - TreeList* list() { return _list; } - void set_list(TreeList* v) { _list = v; } - static TreeChunk* as_TreeChunk(FreeChunk* fc); - // Initialize fields in a TreeChunk that should be - // initialized when the TreeChunk is being added to - // a free list in the tree. - void initialize() { embedded_list()->initialize(); } - - // debugging - void verifyTreeChunkList() const; -}; - -const size_t MIN_TREE_CHUNK_SIZE = sizeof(TreeChunk)/HeapWordSize; - -class BinaryTreeDictionary: public FreeBlockDictionary { - friend class VMStructs; - bool _splay; - size_t _totalSize; - size_t _totalFreeBlocks; - TreeList* _root; - - // private accessors - bool splay() const { return _splay; } - void set_splay(bool v) { _splay = v; } - size_t totalSize() const { return _totalSize; } - void set_totalSize(size_t v) { _totalSize = v; } - virtual void inc_totalSize(size_t v); - virtual void dec_totalSize(size_t v); - size_t totalFreeBlocks() const { return _totalFreeBlocks; } - void set_totalFreeBlocks(size_t v) { _totalFreeBlocks = v; } - TreeList* root() const { return _root; } - void set_root(TreeList* v) { _root = v; } - - // Remove a chunk of size "size" or larger from the tree and - // return it. If the chunk - // is the last chunk of that size, remove the node for that size - // from the tree. - TreeChunk* getChunkFromTree(size_t size, Dither dither, bool splay); - // Return a list of the specified size or NULL from the tree. - // The list is not removed from the tree. - TreeList* findList (size_t size) const; - // Remove this chunk from the tree. If the removal results - // in an empty list in the tree, remove the empty list. - TreeChunk* removeChunkFromTree(TreeChunk* tc); - // Remove the node in the trees starting at tl that has the - // minimum value and return it. Repair the tree as needed. - TreeList* removeTreeMinimum(TreeList* tl); - void semiSplayStep(TreeList* tl); - // Add this free chunk to the tree. - void insertChunkInTree(FreeChunk* freeChunk); - public: - void verifyTree() const; - // verify that the given chunk is in the tree. - bool verifyChunkInFreeLists(FreeChunk* tc) const; - private: - void verifyTreeHelper(TreeList* tl) const; - static size_t verifyPrevFreePtrs(TreeList* tl); - - // Returns the total number of chunks in the list. - size_t totalListLength(TreeList* tl) const; - // Returns the total number of words in the chunks in the tree - // starting at "tl". - size_t totalSizeInTree(TreeList* tl) const; - // Returns the sum of the square of the size of each block - // in the tree starting at "tl". - double sum_of_squared_block_sizes(TreeList* const tl) const; - // Returns the total number of free blocks in the tree starting - // at "tl". - size_t totalFreeBlocksInTree(TreeList* tl) const; - size_t numFreeBlocks() const; - size_t treeHeight() const; - size_t treeHeightHelper(TreeList* tl) const; - size_t totalNodesInTree(TreeList* tl) const; - size_t totalNodesHelper(TreeList* tl) const; - - public: - // Constructor - BinaryTreeDictionary(MemRegion mr, bool splay = false); - - // Reset the dictionary to the initial conditions with - // a single free chunk. - void reset(MemRegion mr); - void reset(HeapWord* addr, size_t size); - // Reset the dictionary to be empty. - void reset(); - - // Return a chunk of size "size" or greater from - // the tree. - // want a better dynamic splay strategy for the future. - FreeChunk* getChunk(size_t size, Dither dither) { - verify_par_locked(); - FreeChunk* res = getChunkFromTree(size, dither, splay()); - assert(res == NULL || res->isFree(), - "Should be returning a free chunk"); - return res; - } - - void returnChunk(FreeChunk* chunk) { - verify_par_locked(); - insertChunkInTree(chunk); - } - - void removeChunk(FreeChunk* chunk) { - verify_par_locked(); - removeChunkFromTree((TreeChunk*)chunk); - assert(chunk->isFree(), "Should still be a free chunk"); - } - - size_t maxChunkSize() const; - size_t totalChunkSize(debug_only(const Mutex* lock)) const { - debug_only( - if (lock != NULL && lock->owned_by_self()) { - assert(totalSizeInTree(root()) == totalSize(), - "_totalSize inconsistency"); - } - ) - return totalSize(); - } - - size_t minSize() const { - return MIN_TREE_CHUNK_SIZE; - } - - double sum_of_squared_block_sizes() const { - return sum_of_squared_block_sizes(root()); - } - - FreeChunk* find_chunk_ends_at(HeapWord* target) const; - - // Find the list with size "size" in the binary tree and update - // the statistics in the list according to "split" (chunk was - // split or coalesce) and "birth" (chunk was added or removed). - void dictCensusUpdate(size_t size, bool split, bool birth); - // Return true if the dictionary is overpopulated (more chunks of - // this size than desired) for size "size". - bool coalDictOverPopulated(size_t size); - // Methods called at the beginning of a sweep to prepare the - // statistics for the sweep. - void beginSweepDictCensus(double coalSurplusPercent, - float inter_sweep_current, - float inter_sweep_estimate, - float intra_sweep_estimate); - // Methods called after the end of a sweep to modify the - // statistics for the sweep. - void endSweepDictCensus(double splitSurplusPercent); - // Return the largest free chunk in the tree. - FreeChunk* findLargestDict() const; - // Accessors for statistics - void setTreeSurplus(double splitSurplusPercent); - void setTreeHints(void); - // Reset statistics for all the lists in the tree. - void clearTreeCensus(void); - // Print the statistcis for all the lists in the tree. Also may - // print out summaries. - void printDictCensus(void) const; - void print_free_lists(outputStream* st) const; - - // For debugging. Returns the sum of the _returnedBytes for - // all lists in the tree. - size_t sumDictReturnedBytes() PRODUCT_RETURN0; - // Sets the _returnedBytes for all the lists in the tree to zero. - void initializeDictReturnedBytes() PRODUCT_RETURN; - // For debugging. Return the total number of chunks in the dictionary. - size_t totalCount() PRODUCT_RETURN0; - - void reportStatistics() const; - - void verify() const; -}; - -#endif // SHARE_VM_GC_IMPLEMENTATION_CONCURRENTMARKSWEEP_BINARYTREEDICTIONARY_HPP diff -r 3c91f2c9fd21 -r 9f059abe8cf2 src/share/vm/gc_implementation/concurrentMarkSweep/cmsPermGen.cpp --- a/src/share/vm/gc_implementation/concurrentMarkSweep/cmsPermGen.cpp Fri Apr 20 17:13:36 2012 -0700 +++ b/src/share/vm/gc_implementation/concurrentMarkSweep/cmsPermGen.cpp Thu Mar 29 19:46:24 2012 -0700 @@ -38,7 +38,7 @@ CMSPermGen::CMSPermGen(ReservedSpace rs, size_t initial_byte_size, CardTableRS* ct, - FreeBlockDictionary::DictionaryChoice dictionaryChoice) { + FreeBlockDictionary::DictionaryChoice dictionaryChoice) { CMSPermGenGen* g = new CMSPermGenGen(rs, initial_byte_size, -1, ct); if (g == NULL) { diff -r 3c91f2c9fd21 -r 9f059abe8cf2 src/share/vm/gc_implementation/concurrentMarkSweep/cmsPermGen.hpp --- a/src/share/vm/gc_implementation/concurrentMarkSweep/cmsPermGen.hpp Fri Apr 20 17:13:36 2012 -0700 +++ b/src/share/vm/gc_implementation/concurrentMarkSweep/cmsPermGen.hpp Thu Mar 29 19:46:24 2012 -0700 @@ -45,7 +45,7 @@ public: CMSPermGen(ReservedSpace rs, size_t initial_byte_size, - CardTableRS* ct, FreeBlockDictionary::DictionaryChoice); + CardTableRS* ct, FreeBlockDictionary::DictionaryChoice); HeapWord* mem_allocate(size_t size); @@ -65,7 +65,7 @@ // regarding not using adaptive free lists for a perm gen. ConcurrentMarkSweepGeneration(rs, initial_byte_size, // MinPermHeapExapnsion level, ct, false /* use adaptive freelists */, - (FreeBlockDictionary::DictionaryChoice)CMSDictionaryChoice) + (FreeBlockDictionary::DictionaryChoice)CMSDictionaryChoice) {} void initialize_performance_counters(); diff -r 3c91f2c9fd21 -r 9f059abe8cf2 src/share/vm/gc_implementation/concurrentMarkSweep/compactibleFreeListSpace.cpp --- a/src/share/vm/gc_implementation/concurrentMarkSweep/compactibleFreeListSpace.cpp Fri Apr 20 17:13:36 2012 -0700 +++ b/src/share/vm/gc_implementation/concurrentMarkSweep/compactibleFreeListSpace.cpp Thu Mar 29 19:46:24 2012 -0700 @@ -69,7 +69,7 @@ // Constructor CompactibleFreeListSpace::CompactibleFreeListSpace(BlockOffsetSharedArray* bs, MemRegion mr, bool use_adaptive_freelists, - FreeBlockDictionary::DictionaryChoice dictionaryChoice) : + FreeBlockDictionary::DictionaryChoice dictionaryChoice) : _dictionaryChoice(dictionaryChoice), _adaptive_freelists(use_adaptive_freelists), _bt(bs, mr), @@ -87,6 +87,8 @@ CMSConcMarkMultiple), _collector(NULL) { + assert(sizeof(FreeChunk) / BytesPerWord <= MinChunkSize, + "FreeChunk is larger than expected"); _bt.set_space(this); initialize(mr, SpaceDecorator::Clear, SpaceDecorator::Mangle); // We have all of "mr", all of which we place in the dictionary @@ -96,13 +98,13 @@ // implementation, namely, the simple binary tree (splaying // temporarily disabled). switch (dictionaryChoice) { - case FreeBlockDictionary::dictionarySplayTree: - case FreeBlockDictionary::dictionarySkipList: + case FreeBlockDictionary::dictionarySplayTree: + case FreeBlockDictionary::dictionarySkipList: default: warning("dictionaryChoice: selected option not understood; using" " default BinaryTreeDictionary implementation instead."); - case FreeBlockDictionary::dictionaryBinaryTree: - _dictionary = new BinaryTreeDictionary(mr); + case FreeBlockDictionary::dictionaryBinaryTree: + _dictionary = new BinaryTreeDictionary(mr, use_adaptive_freelists); break; } assert(_dictionary != NULL, "CMS dictionary initialization"); @@ -448,7 +450,7 @@ reportIndexedFreeListStatistics(); gclog_or_tty->print_cr("Layout of Indexed Freelists"); gclog_or_tty->print_cr("---------------------------"); - FreeList::print_labels_on(st, "size"); + FreeList::print_labels_on(st, "size"); for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) { _indexedFreeList[i].print_on(gclog_or_tty); for (FreeChunk* fc = _indexedFreeList[i].head(); fc != NULL; @@ -1331,7 +1333,7 @@ size_t currSize = numWords + MinChunkSize; assert(currSize % MinObjAlignment == 0, "currSize should be aligned"); for (i = currSize; i < IndexSetSize; i += IndexSetStride) { - FreeList* fl = &_indexedFreeList[i]; + FreeList* fl = &_indexedFreeList[i]; if (fl->head()) { ret = getFromListGreater(fl, numWords); assert(ret == NULL || ret->isFree(), "Should be returning a free chunk"); @@ -1714,7 +1716,7 @@ _dictionary->returnChunk(chunk); #ifndef PRODUCT if (CMSCollector::abstract_state() != CMSCollector::Sweeping) { - TreeChunk::as_TreeChunk(chunk)->list()->verify_stats(); + TreeChunk::as_TreeChunk(chunk)->list()->verify_stats(); } #endif // PRODUCT } @@ -1862,11 +1864,11 @@ the excess is >= MIN_CHUNK. */ size_t start = align_object_size(numWords + MinChunkSize); if (start < IndexSetSize) { - FreeList* it = _indexedFreeList; + FreeList* it = _indexedFreeList; size_t hint = _indexedFreeList[start].hint(); while (hint < IndexSetSize) { assert(hint % MinObjAlignment == 0, "hint should be aligned"); - FreeList *fl = &_indexedFreeList[hint]; + FreeList *fl = &_indexedFreeList[hint]; if (fl->surplus() > 0 && fl->head() != NULL) { // Found a list with surplus, reset original hint // and split out a free chunk which is returned. @@ -1885,7 +1887,7 @@ } /* Requires fl->size >= numWords + MinChunkSize */ -FreeChunk* CompactibleFreeListSpace::getFromListGreater(FreeList* fl, +FreeChunk* CompactibleFreeListSpace::getFromListGreater(FreeList* fl, size_t numWords) { FreeChunk *curr = fl->head(); size_t oldNumWords = curr->size(); @@ -2167,7 +2169,7 @@ assert_locked(); size_t i; for (i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) { - FreeList* fl = &_indexedFreeList[i]; + FreeList* fl = &_indexedFreeList[i]; if (PrintFLSStatistics > 1) { gclog_or_tty->print("size[%d] : ", i); } @@ -2186,7 +2188,7 @@ assert_locked(); size_t i; for (i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) { - FreeList *fl = &_indexedFreeList[i]; + FreeList *fl = &_indexedFreeList[i]; fl->set_surplus(fl->count() - (ssize_t)((double)fl->desired() * CMSSmallSplitSurplusPercent)); } @@ -2197,7 +2199,7 @@ size_t i; size_t h = IndexSetSize; for (i = IndexSetSize - 1; i != 0; i -= IndexSetStride) { - FreeList *fl = &_indexedFreeList[i]; + FreeList *fl = &_indexedFreeList[i]; fl->set_hint(h); if (fl->surplus() > 0) { h = i; @@ -2209,7 +2211,7 @@ assert_locked(); size_t i; for (i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) { - FreeList *fl = &_indexedFreeList[i]; + FreeList *fl = &_indexedFreeList[i]; fl->set_prevSweep(fl->count()); fl->set_coalBirths(0); fl->set_coalDeaths(0); @@ -2236,7 +2238,7 @@ bool CompactibleFreeListSpace::coalOverPopulated(size_t size) { if (size < SmallForDictionary) { - FreeList *fl = &_indexedFreeList[size]; + FreeList *fl = &_indexedFreeList[size]; return (fl->coalDesired() < 0) || ((int)fl->count() > fl->coalDesired()); } else { @@ -2246,14 +2248,14 @@ void CompactibleFreeListSpace::smallCoalBirth(size_t size) { assert(size < SmallForDictionary, "Size too large for indexed list"); - FreeList *fl = &_indexedFreeList[size]; + FreeList *fl = &_indexedFreeList[size]; fl->increment_coalBirths(); fl->increment_surplus(); } void CompactibleFreeListSpace::smallCoalDeath(size_t size) { assert(size < SmallForDictionary, "Size too large for indexed list"); - FreeList *fl = &_indexedFreeList[size]; + FreeList *fl = &_indexedFreeList[size]; fl->increment_coalDeaths(); fl->decrement_surplus(); } @@ -2280,14 +2282,14 @@ void CompactibleFreeListSpace::smallSplitBirth(size_t size) { assert(size < SmallForDictionary, "Size too large for indexed list"); - FreeList *fl = &_indexedFreeList[size]; + FreeList *fl = &_indexedFreeList[size]; fl->increment_splitBirths(); fl->increment_surplus(); } void CompactibleFreeListSpace::smallSplitDeath(size_t size) { assert(size < SmallForDictionary, "Size too large for indexed list"); - FreeList *fl = &_indexedFreeList[size]; + FreeList *fl = &_indexedFreeList[size]; fl->increment_splitDeaths(); fl->decrement_surplus(); } @@ -2530,7 +2532,7 @@ assert(_dictionary->minSize() <= IndexSetSize, "Some sizes can't be allocated without recourse to" " linear allocation buffers"); - assert(MIN_TREE_CHUNK_SIZE*HeapWordSize == sizeof(TreeChunk), + assert(BinaryTreeDictionary::min_tree_chunk_size*HeapWordSize == sizeof(TreeChunk), "else MIN_TREE_CHUNK_SIZE is wrong"); assert((IndexSetStride == 2 && IndexSetStart == 4) || // 32-bit (IndexSetStride == 1 && IndexSetStart == 3), "just checking"); // 64-bit @@ -2543,15 +2545,15 @@ void CompactibleFreeListSpace::printFLCensus(size_t sweep_count) const { assert_lock_strong(&_freelistLock); - FreeList total; + FreeList total; gclog_or_tty->print("end sweep# " SIZE_FORMAT "\n", sweep_count); - FreeList::print_labels_on(gclog_or_tty, "size"); + FreeList::print_labels_on(gclog_or_tty, "size"); size_t totalFree = 0; for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) { - const FreeList *fl = &_indexedFreeList[i]; + const FreeList *fl = &_indexedFreeList[i]; totalFree += fl->count() * fl->size(); if (i % (40*IndexSetStride) == 0) { - FreeList::print_labels_on(gclog_or_tty, "size"); + FreeList::print_labels_on(gclog_or_tty, "size"); } fl->print_on(gclog_or_tty); total.set_bfrSurp( total.bfrSurp() + fl->bfrSurp() ); @@ -2634,7 +2636,7 @@ res = _cfls->getChunkFromDictionaryExact(word_sz); if (res == NULL) return NULL; } else { - FreeList* fl = &_indexedFreeList[word_sz]; + FreeList* fl = &_indexedFreeList[word_sz]; if (fl->count() == 0) { // Attempt to refill this local free list. get_from_global_pool(word_sz, fl); @@ -2654,7 +2656,7 @@ // Get a chunk of blocks of the right size and update related // book-keeping stats -void CFLS_LAB::get_from_global_pool(size_t word_sz, FreeList* fl) { +void CFLS_LAB::get_from_global_pool(size_t word_sz, FreeList* fl) { // Get the #blocks we want to claim size_t n_blks = (size_t)_blocks_to_claim[word_sz].average(); assert(n_blks > 0, "Error"); @@ -2736,7 +2738,7 @@ if (num_retire > 0) { _cfls->_indexedFreeList[i].prepend(&_indexedFreeList[i]); // Reset this list. - _indexedFreeList[i] = FreeList(); + _indexedFreeList[i] = FreeList(); _indexedFreeList[i].set_size(i); } } @@ -2750,7 +2752,7 @@ } } -void CompactibleFreeListSpace:: par_get_chunk_of_blocks(size_t word_sz, size_t n, FreeList* fl) { +void CompactibleFreeListSpace:: par_get_chunk_of_blocks(size_t word_sz, size_t n, FreeList* fl) { assert(fl->count() == 0, "Precondition."); assert(word_sz < CompactibleFreeListSpace::IndexSetSize, "Precondition"); @@ -2766,12 +2768,12 @@ (cur_sz < CompactibleFreeListSpace::IndexSetSize) && (CMSSplitIndexedFreeListBlocks || k <= 1); k++, cur_sz = k * word_sz) { - FreeList fl_for_cur_sz; // Empty. + FreeList fl_for_cur_sz; // Empty. fl_for_cur_sz.set_size(cur_sz); { MutexLockerEx x(_indexedFreeListParLocks[cur_sz], Mutex::_no_safepoint_check_flag); - FreeList* gfl = &_indexedFreeList[cur_sz]; + FreeList* gfl = &_indexedFreeList[cur_sz]; if (gfl->count() != 0) { // nn is the number of chunks of size cur_sz that // we'd need to split k-ways each, in order to create @@ -2848,7 +2850,7 @@ while (n > 0) { fc = dictionary()->getChunk(MAX2(n * word_sz, _dictionary->minSize()), - FreeBlockDictionary::atLeast); + FreeBlockDictionary::atLeast); if (fc != NULL) { _bt.allocated((HeapWord*)fc, fc->size(), true /* reducing */); // update _unallocated_blk dictionary()->dictCensusUpdate(fc->size(), diff -r 3c91f2c9fd21 -r 9f059abe8cf2 src/share/vm/gc_implementation/concurrentMarkSweep/compactibleFreeListSpace.hpp --- a/src/share/vm/gc_implementation/concurrentMarkSweep/compactibleFreeListSpace.hpp Fri Apr 20 17:13:36 2012 -0700 +++ b/src/share/vm/gc_implementation/concurrentMarkSweep/compactibleFreeListSpace.hpp Thu Mar 29 19:46:24 2012 -0700 @@ -25,10 +25,10 @@ #ifndef SHARE_VM_GC_IMPLEMENTATION_CONCURRENTMARKSWEEP_COMPACTIBLEFREELISTSPACE_HPP #define SHARE_VM_GC_IMPLEMENTATION_CONCURRENTMARKSWEEP_COMPACTIBLEFREELISTSPACE_HPP -#include "gc_implementation/concurrentMarkSweep/binaryTreeDictionary.hpp" -#include "gc_implementation/concurrentMarkSweep/freeList.hpp" #include "gc_implementation/concurrentMarkSweep/promotionInfo.hpp" +#include "memory/binaryTreeDictionary.hpp" #include "memory/blockOffsetTable.inline.hpp" +#include "memory/freeList.hpp" #include "memory/space.hpp" // Classes in support of keeping track of promotions into a non-Contiguous @@ -129,10 +129,10 @@ // Linear allocation blocks LinearAllocBlock _smallLinearAllocBlock; - FreeBlockDictionary::DictionaryChoice _dictionaryChoice; - FreeBlockDictionary* _dictionary; // ptr to dictionary for large size blocks + FreeBlockDictionary::DictionaryChoice _dictionaryChoice; + FreeBlockDictionary* _dictionary; // ptr to dictionary for large size blocks - FreeList _indexedFreeList[IndexSetSize]; + FreeList _indexedFreeList[IndexSetSize]; // indexed array for small size blocks // allocation stategy bool _fitStrategy; // Use best fit strategy. @@ -169,7 +169,7 @@ // If the count of "fl" is negative, it's absolute value indicates a // number of free chunks that had been previously "borrowed" from global // list of size "word_sz", and must now be decremented. - void par_get_chunk_of_blocks(size_t word_sz, size_t n, FreeList* fl); + void par_get_chunk_of_blocks(size_t word_sz, size_t n, FreeList* fl); // Allocation helper functions // Allocate using a strategy that takes from the indexed free lists @@ -215,7 +215,7 @@ // and return it. The split off remainder is returned to // the free lists. The old name for getFromListGreater // was lookInListGreater. - FreeChunk* getFromListGreater(FreeList* fl, size_t numWords); + FreeChunk* getFromListGreater(FreeList* fl, size_t numWords); // Get a chunk in the indexed free list or dictionary, // by considering a larger chunk and splitting it. FreeChunk* getChunkFromGreater(size_t numWords); @@ -286,10 +286,10 @@ // Constructor... CompactibleFreeListSpace(BlockOffsetSharedArray* bs, MemRegion mr, bool use_adaptive_freelists, - FreeBlockDictionary::DictionaryChoice); + FreeBlockDictionary::DictionaryChoice); // accessors bool bestFitFirst() { return _fitStrategy == FreeBlockBestFitFirst; } - FreeBlockDictionary* dictionary() const { return _dictionary; } + FreeBlockDictionary* dictionary() const { return _dictionary; } HeapWord* nearLargestChunk() const { return _nearLargestChunk; } void set_nearLargestChunk(HeapWord* v) { _nearLargestChunk = v; } @@ -622,7 +622,7 @@ CompactibleFreeListSpace* _cfls; // Our local free lists. - FreeList _indexedFreeList[CompactibleFreeListSpace::IndexSetSize]; + FreeList _indexedFreeList[CompactibleFreeListSpace::IndexSetSize]; // Initialized from a command-line arg. @@ -635,7 +635,7 @@ size_t _num_blocks [CompactibleFreeListSpace::IndexSetSize]; // Internal work method - void get_from_global_pool(size_t word_sz, FreeList* fl); + void get_from_global_pool(size_t word_sz, FreeList* fl); public: CFLS_LAB(CompactibleFreeListSpace* cfls); diff -r 3c91f2c9fd21 -r 9f059abe8cf2 src/share/vm/gc_implementation/concurrentMarkSweep/concurrentMarkSweepGeneration.cpp --- a/src/share/vm/gc_implementation/concurrentMarkSweep/concurrentMarkSweepGeneration.cpp Fri Apr 20 17:13:36 2012 -0700 +++ b/src/share/vm/gc_implementation/concurrentMarkSweep/concurrentMarkSweepGeneration.cpp Thu Mar 29 19:46:24 2012 -0700 @@ -188,7 +188,7 @@ ConcurrentMarkSweepGeneration::ConcurrentMarkSweepGeneration( ReservedSpace rs, size_t initial_byte_size, int level, CardTableRS* ct, bool use_adaptive_freelists, - FreeBlockDictionary::DictionaryChoice dictionaryChoice) : + FreeBlockDictionary::DictionaryChoice dictionaryChoice) : CardGeneration(rs, initial_byte_size, level, ct), _dilatation_factor(((double)MinChunkSize)/((double)(CollectedHeap::min_fill_size()))), _debug_collection_type(Concurrent_collection_type) diff -r 3c91f2c9fd21 -r 9f059abe8cf2 src/share/vm/gc_implementation/concurrentMarkSweep/concurrentMarkSweepGeneration.hpp --- a/src/share/vm/gc_implementation/concurrentMarkSweep/concurrentMarkSweepGeneration.hpp Fri Apr 20 17:13:36 2012 -0700 +++ b/src/share/vm/gc_implementation/concurrentMarkSweep/concurrentMarkSweepGeneration.hpp Thu Mar 29 19:46:24 2012 -0700 @@ -25,10 +25,10 @@ #ifndef SHARE_VM_GC_IMPLEMENTATION_CONCURRENTMARKSWEEP_CONCURRENTMARKSWEEPGENERATION_HPP #define SHARE_VM_GC_IMPLEMENTATION_CONCURRENTMARKSWEEP_CONCURRENTMARKSWEEPGENERATION_HPP -#include "gc_implementation/concurrentMarkSweep/freeBlockDictionary.hpp" #include "gc_implementation/shared/gSpaceCounters.hpp" #include "gc_implementation/shared/gcStats.hpp" #include "gc_implementation/shared/generationCounters.hpp" +#include "memory/freeBlockDictionary.hpp" #include "memory/generation.hpp" #include "runtime/mutexLocker.hpp" #include "runtime/virtualspace.hpp" @@ -1106,7 +1106,7 @@ ConcurrentMarkSweepGeneration(ReservedSpace rs, size_t initial_byte_size, int level, CardTableRS* ct, bool use_adaptive_freelists, - FreeBlockDictionary::DictionaryChoice); + FreeBlockDictionary::DictionaryChoice); // Accessors CMSCollector* collector() const { return _collector; } @@ -1328,7 +1328,7 @@ ASConcurrentMarkSweepGeneration(ReservedSpace rs, size_t initial_byte_size, int level, CardTableRS* ct, bool use_adaptive_freelists, - FreeBlockDictionary::DictionaryChoice + FreeBlockDictionary::DictionaryChoice dictionaryChoice) : ConcurrentMarkSweepGeneration(rs, initial_byte_size, level, ct, use_adaptive_freelists, dictionaryChoice) {} diff -r 3c91f2c9fd21 -r 9f059abe8cf2 src/share/vm/gc_implementation/concurrentMarkSweep/freeBlockDictionary.cpp --- a/src/share/vm/gc_implementation/concurrentMarkSweep/freeBlockDictionary.cpp Fri Apr 20 17:13:36 2012 -0700 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,60 +0,0 @@ -/* - * Copyright (c) 2002, 2010, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * 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/concurrentMarkSweep/freeBlockDictionary.hpp" -#ifdef TARGET_OS_FAMILY_linux -# include "thread_linux.inline.hpp" -#endif -#ifdef TARGET_OS_FAMILY_solaris -# include "thread_solaris.inline.hpp" -#endif -#ifdef TARGET_OS_FAMILY_windows -# include "thread_windows.inline.hpp" -#endif -#ifdef TARGET_OS_FAMILY_bsd -# include "thread_bsd.inline.hpp" -#endif - -#ifndef PRODUCT -Mutex* FreeBlockDictionary::par_lock() const { - return _lock; -} - -void FreeBlockDictionary::set_par_lock(Mutex* lock) { - _lock = lock; -} - -void FreeBlockDictionary::verify_par_locked() const { -#ifdef ASSERT - if (ParallelGCThreads > 0) { - Thread* myThread = Thread::current(); - if (myThread->is_GC_task_thread()) { - assert(par_lock() != NULL, "Should be using locking?"); - assert_lock_strong(par_lock()); - } - } -#endif // ASSERT -} -#endif diff -r 3c91f2c9fd21 -r 9f059abe8cf2 src/share/vm/gc_implementation/concurrentMarkSweep/freeBlockDictionary.hpp --- a/src/share/vm/gc_implementation/concurrentMarkSweep/freeBlockDictionary.hpp Fri Apr 20 17:13:36 2012 -0700 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,103 +0,0 @@ -/* - * Copyright (c) 2001, 2010, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * 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. - * - */ - -#ifndef SHARE_VM_GC_IMPLEMENTATION_CONCURRENTMARKSWEEP_FREEBLOCKDICTIONARY_HPP -#define SHARE_VM_GC_IMPLEMENTATION_CONCURRENTMARKSWEEP_FREEBLOCKDICTIONARY_HPP - -#include "gc_implementation/concurrentMarkSweep/freeChunk.hpp" -#include "memory/allocation.hpp" -#include "memory/memRegion.hpp" -#include "runtime/mutex.hpp" -#include "utilities/debug.hpp" -#include "utilities/globalDefinitions.hpp" -#include "utilities/ostream.hpp" - -// A FreeBlockDictionary is an abstract superclass that will allow -// a number of alternative implementations in the future. -class FreeBlockDictionary: public CHeapObj { - public: - enum Dither { - atLeast, - exactly, - roughly - }; - enum DictionaryChoice { - dictionaryBinaryTree = 0, - dictionarySplayTree = 1, - dictionarySkipList = 2 - }; - - private: - NOT_PRODUCT(Mutex* _lock;) - - public: - virtual void removeChunk(FreeChunk* fc) = 0; - virtual FreeChunk* getChunk(size_t size, Dither dither = atLeast) = 0; - virtual void returnChunk(FreeChunk* chunk) = 0; - virtual size_t totalChunkSize(debug_only(const Mutex* lock)) const = 0; - virtual size_t maxChunkSize() const = 0; - virtual size_t minSize() const = 0; - // Reset the dictionary to the initial conditions for a single - // block. - virtual void reset(HeapWord* addr, size_t size) = 0; - virtual void reset() = 0; - - virtual void dictCensusUpdate(size_t size, bool split, bool birth) = 0; - virtual bool coalDictOverPopulated(size_t size) = 0; - virtual void beginSweepDictCensus(double coalSurplusPercent, - float inter_sweep_current, float inter_sweep_estimate, - float intra__sweep_current) = 0; - virtual void endSweepDictCensus(double splitSurplusPercent) = 0; - virtual FreeChunk* findLargestDict() const = 0; - // verify that the given chunk is in the dictionary. - virtual bool verifyChunkInFreeLists(FreeChunk* tc) const = 0; - - // Sigma_{all_free_blocks} (block_size^2) - virtual double sum_of_squared_block_sizes() const = 0; - - virtual FreeChunk* find_chunk_ends_at(HeapWord* target) const = 0; - virtual void inc_totalSize(size_t v) = 0; - virtual void dec_totalSize(size_t v) = 0; - - NOT_PRODUCT ( - virtual size_t sumDictReturnedBytes() = 0; - virtual void initializeDictReturnedBytes() = 0; - virtual size_t totalCount() = 0; - ) - - virtual void reportStatistics() const { - gclog_or_tty->print("No statistics available"); - } - - virtual void printDictCensus() const = 0; - virtual void print_free_lists(outputStream* st) const = 0; - - virtual void verify() const = 0; - - Mutex* par_lock() const PRODUCT_RETURN0; - void set_par_lock(Mutex* lock) PRODUCT_RETURN; - void verify_par_locked() const PRODUCT_RETURN; -}; - -#endif // SHARE_VM_GC_IMPLEMENTATION_CONCURRENTMARKSWEEP_FREEBLOCKDICTIONARY_HPP diff -r 3c91f2c9fd21 -r 9f059abe8cf2 src/share/vm/gc_implementation/concurrentMarkSweep/freeChunk.cpp --- a/src/share/vm/gc_implementation/concurrentMarkSweep/freeChunk.cpp Fri Apr 20 17:13:36 2012 -0700 +++ b/src/share/vm/gc_implementation/concurrentMarkSweep/freeChunk.cpp Thu Mar 29 19:46:24 2012 -0700 @@ -23,7 +23,8 @@ */ #include "precompiled.hpp" -#include "gc_implementation/concurrentMarkSweep/freeBlockDictionary.hpp" +#include "gc_implementation/concurrentMarkSweep/freeChunk.hpp" +#include "memory/freeBlockDictionary.hpp" #include "utilities/copy.hpp" #ifndef PRODUCT diff -r 3c91f2c9fd21 -r 9f059abe8cf2 src/share/vm/gc_implementation/concurrentMarkSweep/freeList.cpp --- a/src/share/vm/gc_implementation/concurrentMarkSweep/freeList.cpp Fri Apr 20 17:13:36 2012 -0700 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,360 +0,0 @@ -/* - * Copyright (c) 2001, 2010, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * 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/concurrentMarkSweep/freeBlockDictionary.hpp" -#include "gc_implementation/concurrentMarkSweep/freeList.hpp" -#include "memory/sharedHeap.hpp" -#include "runtime/globals.hpp" -#include "runtime/mutex.hpp" -#include "runtime/vmThread.hpp" - -// Free list. A FreeList is used to access a linked list of chunks -// of space in the heap. The head and tail are maintained so that -// items can be (as in the current implementation) added at the -// at the tail of the list and removed from the head of the list to -// maintain a FIFO queue. - -FreeList::FreeList() : - _head(NULL), _tail(NULL) -#ifdef ASSERT - , _protecting_lock(NULL) -#endif -{ - _size = 0; - _count = 0; - _hint = 0; - init_statistics(); -} - -FreeList::FreeList(FreeChunk* fc) : - _head(fc), _tail(fc) -#ifdef ASSERT - , _protecting_lock(NULL) -#endif -{ - _size = fc->size(); - _count = 1; - _hint = 0; - init_statistics(); -#ifndef PRODUCT - _allocation_stats.set_returnedBytes(size() * HeapWordSize); -#endif -} - -FreeList::FreeList(HeapWord* addr, size_t size) : - _head((FreeChunk*) addr), _tail((FreeChunk*) addr) -#ifdef ASSERT - , _protecting_lock(NULL) -#endif -{ - assert(size > sizeof(FreeChunk), "size is too small"); - head()->setSize(size); - _size = size; - _count = 1; - init_statistics(); -#ifndef PRODUCT - _allocation_stats.set_returnedBytes(_size * HeapWordSize); -#endif -} - -void FreeList::reset(size_t hint) { - set_count(0); - set_head(NULL); - set_tail(NULL); - set_hint(hint); -} - -void FreeList::init_statistics(bool split_birth) { - _allocation_stats.initialize(split_birth); -} - -FreeChunk* FreeList::getChunkAtHead() { - assert_proper_lock_protection(); - assert(head() == NULL || head()->prev() == NULL, "list invariant"); - assert(tail() == NULL || tail()->next() == NULL, "list invariant"); - FreeChunk* fc = head(); - if (fc != NULL) { - FreeChunk* nextFC = fc->next(); - if (nextFC != NULL) { - // The chunk fc being removed has a "next". Set the "next" to the - // "prev" of fc. - nextFC->linkPrev(NULL); - } else { // removed tail of list - link_tail(NULL); - } - link_head(nextFC); - decrement_count(); - } - assert(head() == NULL || head()->prev() == NULL, "list invariant"); - assert(tail() == NULL || tail()->next() == NULL, "list invariant"); - return fc; -} - - -void FreeList::getFirstNChunksFromList(size_t n, FreeList* fl) { - assert_proper_lock_protection(); - assert(fl->count() == 0, "Precondition"); - if (count() > 0) { - int k = 1; - fl->set_head(head()); n--; - FreeChunk* tl = head(); - while (tl->next() != NULL && n > 0) { - tl = tl->next(); n--; k++; - } - assert(tl != NULL, "Loop Inv."); - - // First, fix up the list we took from. - FreeChunk* new_head = tl->next(); - set_head(new_head); - set_count(count() - k); - if (new_head == NULL) { - set_tail(NULL); - } else { - new_head->linkPrev(NULL); - } - // Now we can fix up the tail. - tl->linkNext(NULL); - // And return the result. - fl->set_tail(tl); - fl->set_count(k); - } -} - -// Remove this chunk from the list -void FreeList::removeChunk(FreeChunk*fc) { - assert_proper_lock_protection(); - assert(head() != NULL, "Remove from empty list"); - assert(fc != NULL, "Remove a NULL chunk"); - assert(size() == fc->size(), "Wrong list"); - assert(head() == NULL || head()->prev() == NULL, "list invariant"); - assert(tail() == NULL || tail()->next() == NULL, "list invariant"); - - FreeChunk* prevFC = fc->prev(); - FreeChunk* nextFC = fc->next(); - if (nextFC != NULL) { - // The chunk fc being removed has a "next". Set the "next" to the - // "prev" of fc. - nextFC->linkPrev(prevFC); - } else { // removed tail of list - link_tail(prevFC); - } - if (prevFC == NULL) { // removed head of list - link_head(nextFC); - assert(nextFC == NULL || nextFC->prev() == NULL, - "Prev of head should be NULL"); - } else { - prevFC->linkNext(nextFC); - assert(tail() != prevFC || prevFC->next() == NULL, - "Next of tail should be NULL"); - } - decrement_count(); - assert(((head() == NULL) + (tail() == NULL) + (count() == 0)) % 3 == 0, - "H/T/C Inconsistency"); - // clear next and prev fields of fc, debug only - NOT_PRODUCT( - fc->linkPrev(NULL); - fc->linkNext(NULL); - ) - assert(fc->isFree(), "Should still be a free chunk"); - assert(head() == NULL || head()->prev() == NULL, "list invariant"); - assert(tail() == NULL || tail()->next() == NULL, "list invariant"); - assert(head() == NULL || head()->size() == size(), "wrong item on list"); - assert(tail() == NULL || tail()->size() == size(), "wrong item on list"); -} - -// Add this chunk at the head of the list. -void FreeList::returnChunkAtHead(FreeChunk* chunk, bool record_return) { - assert_proper_lock_protection(); - assert(chunk != NULL, "insert a NULL chunk"); - assert(size() == chunk->size(), "Wrong size"); - assert(head() == NULL || head()->prev() == NULL, "list invariant"); - assert(tail() == NULL || tail()->next() == NULL, "list invariant"); - - FreeChunk* oldHead = head(); - assert(chunk != oldHead, "double insertion"); - chunk->linkAfter(oldHead); - link_head(chunk); - if (oldHead == NULL) { // only chunk in list - assert(tail() == NULL, "inconsistent FreeList"); - link_tail(chunk); - } - increment_count(); // of # of chunks in list - DEBUG_ONLY( - if (record_return) { - increment_returnedBytes_by(size()*HeapWordSize); - } - ) - assert(head() == NULL || head()->prev() == NULL, "list invariant"); - assert(tail() == NULL || tail()->next() == NULL, "list invariant"); - assert(head() == NULL || head()->size() == size(), "wrong item on list"); - assert(tail() == NULL || tail()->size() == size(), "wrong item on list"); -} - -void FreeList::returnChunkAtHead(FreeChunk* chunk) { - assert_proper_lock_protection(); - returnChunkAtHead(chunk, true); -} - -// Add this chunk at the tail of the list. -void FreeList::returnChunkAtTail(FreeChunk* chunk, bool record_return) { - assert_proper_lock_protection(); - assert(head() == NULL || head()->prev() == NULL, "list invariant"); - assert(tail() == NULL || tail()->next() == NULL, "list invariant"); - assert(chunk != NULL, "insert a NULL chunk"); - assert(size() == chunk->size(), "wrong size"); - - FreeChunk* oldTail = tail(); - assert(chunk != oldTail, "double insertion"); - if (oldTail != NULL) { - oldTail->linkAfter(chunk); - } else { // only chunk in list - assert(head() == NULL, "inconsistent FreeList"); - link_head(chunk); - } - link_tail(chunk); - increment_count(); // of # of chunks in list - DEBUG_ONLY( - if (record_return) { - increment_returnedBytes_by(size()*HeapWordSize); - } - ) - assert(head() == NULL || head()->prev() == NULL, "list invariant"); - assert(tail() == NULL || tail()->next() == NULL, "list invariant"); - assert(head() == NULL || head()->size() == size(), "wrong item on list"); - assert(tail() == NULL || tail()->size() == size(), "wrong item on list"); -} - -void FreeList::returnChunkAtTail(FreeChunk* chunk) { - returnChunkAtTail(chunk, true); -} - -void FreeList::prepend(FreeList* fl) { - assert_proper_lock_protection(); - if (fl->count() > 0) { - if (count() == 0) { - set_head(fl->head()); - set_tail(fl->tail()); - set_count(fl->count()); - } else { - // Both are non-empty. - FreeChunk* fl_tail = fl->tail(); - FreeChunk* this_head = head(); - assert(fl_tail->next() == NULL, "Well-formedness of fl"); - fl_tail->linkNext(this_head); - this_head->linkPrev(fl_tail); - set_head(fl->head()); - set_count(count() + fl->count()); - } - fl->set_head(NULL); - fl->set_tail(NULL); - fl->set_count(0); - } -} - -// verifyChunkInFreeLists() is used to verify that an item is in this free list. -// It is used as a debugging aid. -bool FreeList::verifyChunkInFreeLists(FreeChunk* fc) const { - // This is an internal consistency check, not part of the check that the - // chunk is in the free lists. - guarantee(fc->size() == size(), "Wrong list is being searched"); - FreeChunk* curFC = head(); - while (curFC) { - // This is an internal consistency check. - guarantee(size() == curFC->size(), "Chunk is in wrong list."); - if (fc == curFC) { - return true; - } - curFC = curFC->next(); - } - return false; -} - -#ifndef PRODUCT -void FreeList::verify_stats() const { - // The +1 of the LH comparand is to allow some "looseness" in - // checking: we usually call this interface when adding a block - // and we'll subsequently update the stats; we cannot update the - // stats beforehand because in the case of the large-block BT - // dictionary for example, this might be the first block and - // in that case there would be no place that we could record - // the stats (which are kept in the block itself). - assert((_allocation_stats.prevSweep() + _allocation_stats.splitBirths() - + _allocation_stats.coalBirths() + 1) // Total Production Stock + 1 - >= (_allocation_stats.splitDeaths() + _allocation_stats.coalDeaths() - + (ssize_t)count()), // Total Current Stock + depletion - err_msg("FreeList " PTR_FORMAT " of size " SIZE_FORMAT - " violates Conservation Principle: " - "prevSweep(" SIZE_FORMAT ")" - " + splitBirths(" SIZE_FORMAT ")" - " + coalBirths(" SIZE_FORMAT ") + 1 >= " - " splitDeaths(" SIZE_FORMAT ")" - " coalDeaths(" SIZE_FORMAT ")" - " + count(" SSIZE_FORMAT ")", - this, _size, _allocation_stats.prevSweep(), _allocation_stats.splitBirths(), - _allocation_stats.splitBirths(), _allocation_stats.splitDeaths(), - _allocation_stats.coalDeaths(), count())); -} - -void FreeList::assert_proper_lock_protection_work() const { - assert(_protecting_lock != NULL, "Don't call this directly"); - assert(ParallelGCThreads > 0, "Don't call this directly"); - Thread* thr = Thread::current(); - if (thr->is_VM_thread() || thr->is_ConcurrentGC_thread()) { - // assert that we are holding the freelist lock - } else if (thr->is_GC_task_thread()) { - assert(_protecting_lock->owned_by_self(), "FreeList RACE DETECTED"); - } else if (thr->is_Java_thread()) { - assert(!SafepointSynchronize::is_at_safepoint(), "Should not be executing"); - } else { - ShouldNotReachHere(); // unaccounted thread type? - } -} -#endif - -// Print the "label line" for free list stats. -void FreeList::print_labels_on(outputStream* st, const char* c) { - st->print("%16s\t", c); - st->print("%14s\t" "%14s\t" "%14s\t" "%14s\t" "%14s\t" - "%14s\t" "%14s\t" "%14s\t" "%14s\t" "%14s\t" "\n", - "bfrsurp", "surplus", "desired", "prvSwep", "bfrSwep", - "count", "cBirths", "cDeaths", "sBirths", "sDeaths"); -} - -// Print the AllocationStats for the given free list. If the second argument -// to the call is a non-null string, it is printed in the first column; -// otherwise, if the argument is null (the default), then the size of the -// (free list) block is printed in the first column. -void FreeList::print_on(outputStream* st, const char* c) const { - if (c != NULL) { - st->print("%16s", c); - } else { - st->print(SIZE_FORMAT_W(16), size()); - } - st->print("\t" - SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" - SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\n", - bfrSurp(), surplus(), desired(), prevSweep(), beforeSweep(), - count(), coalBirths(), coalDeaths(), splitBirths(), splitDeaths()); -} diff -r 3c91f2c9fd21 -r 9f059abe8cf2 src/share/vm/gc_implementation/concurrentMarkSweep/freeList.hpp --- a/src/share/vm/gc_implementation/concurrentMarkSweep/freeList.hpp Fri Apr 20 17:13:36 2012 -0700 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,335 +0,0 @@ -/* - * Copyright (c) 2001, 2010, Oracle and/or its affiliates. All rights reserved. - * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. - * - * This code is free software; you can redistribute it and/or modify it - * 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. - * - */ - -#ifndef SHARE_VM_GC_IMPLEMENTATION_CONCURRENTMARKSWEEP_FREELIST_HPP -#define SHARE_VM_GC_IMPLEMENTATION_CONCURRENTMARKSWEEP_FREELIST_HPP - -#include "gc_implementation/shared/allocationStats.hpp" - -class CompactibleFreeListSpace; - -// A class for maintaining a free list of FreeChunk's. The FreeList -// maintains a the structure of the list (head, tail, etc.) plus -// statistics for allocations from the list. The links between items -// are not part of FreeList. The statistics are -// used to make decisions about coalescing FreeChunk's when they -// are swept during collection. -// -// See the corresponding .cpp file for a description of the specifics -// for that implementation. - -class Mutex; -class TreeList; - -class FreeList VALUE_OBJ_CLASS_SPEC { - friend class CompactibleFreeListSpace; - friend class VMStructs; - friend class PrintTreeCensusClosure; - - protected: - TreeList* _parent; - TreeList* _left; - TreeList* _right; - - private: - FreeChunk* _head; // Head of list of free chunks - FreeChunk* _tail; // Tail of list of free chunks - size_t _size; // Size in Heap words of each chunk - ssize_t _count; // Number of entries in list - size_t _hint; // next larger size list with a positive surplus - - AllocationStats _allocation_stats; // allocation-related statistics - -#ifdef ASSERT - Mutex* _protecting_lock; -#endif - - // Asserts false if the protecting lock (if any) is not held. - void assert_proper_lock_protection_work() const PRODUCT_RETURN; - void assert_proper_lock_protection() const { -#ifdef ASSERT - if (_protecting_lock != NULL) - assert_proper_lock_protection_work(); -#endif - } - - // Initialize the allocation statistics. - protected: - void init_statistics(bool split_birth = false); - void set_count(ssize_t v) { _count = v;} - void increment_count() { - _count++; - } - - void decrement_count() { - _count--; - assert(_count >= 0, "Count should not be negative"); - } - - public: - // Constructor - // Construct a list without any entries. - FreeList(); - // Construct a list with "fc" as the first (and lone) entry in the list. - FreeList(FreeChunk* fc); - // Construct a list which will have a FreeChunk at address "addr" and - // of size "size" as the first (and lone) entry in the list. - FreeList(HeapWord* addr, size_t size); - - // Reset the head, tail, hint, and count of a free list. - void reset(size_t hint); - - // Declare the current free list to be protected by the given lock. -#ifdef ASSERT - void set_protecting_lock(Mutex* protecting_lock) { - _protecting_lock = protecting_lock; - } -#endif - - // Accessors. - FreeChunk* head() const { - assert_proper_lock_protection(); - return _head; - } - void set_head(FreeChunk* v) { - assert_proper_lock_protection(); - _head = v; - assert(!_head || _head->size() == _size, "bad chunk size"); - } - // Set the head of the list and set the prev field of non-null - // values to NULL. - void link_head(FreeChunk* v) { - assert_proper_lock_protection(); - set_head(v); - // If this method is not used (just set the head instead), - // this check can be avoided. - if (v != NULL) { - v->linkPrev(NULL); - } - } - - FreeChunk* tail() const { - assert_proper_lock_protection(); - return _tail; - } - void set_tail(FreeChunk* v) { - assert_proper_lock_protection(); - _tail = v; - assert(!_tail || _tail->size() == _size, "bad chunk size"); - } - // Set the tail of the list and set the next field of non-null - // values to NULL. - void link_tail(FreeChunk* v) { - assert_proper_lock_protection(); - set_tail(v); - if (v != NULL) { - v->clearNext(); - } - } - - // No locking checks in read-accessors: lock-free reads (only) are benign. - // Readers are expected to have the lock if they are doing work that - // requires atomicity guarantees in sections of code. - size_t size() const { - return _size; - } - void set_size(size_t v) { - assert_proper_lock_protection(); - _size = v; - } - ssize_t count() const { - return _count; - } - size_t hint() const { - return _hint; - } - void set_hint(size_t v) { - assert_proper_lock_protection(); - assert(v == 0 || _size < v, "Bad hint"); _hint = v; - } - - // Accessors for statistics - AllocationStats* allocation_stats() { - assert_proper_lock_protection(); - return &_allocation_stats; - } - - ssize_t desired() const { - return _allocation_stats.desired(); - } - void set_desired(ssize_t v) { - assert_proper_lock_protection(); - _allocation_stats.set_desired(v); - } - void compute_desired(float inter_sweep_current, - float inter_sweep_estimate, - float intra_sweep_estimate) { - assert_proper_lock_protection(); - _allocation_stats.compute_desired(_count, - inter_sweep_current, - inter_sweep_estimate, - intra_sweep_estimate); - } - ssize_t coalDesired() const { - return _allocation_stats.coalDesired(); - } - void set_coalDesired(ssize_t v) { - assert_proper_lock_protection(); - _allocation_stats.set_coalDesired(v); - } - - ssize_t surplus() const { - return _allocation_stats.surplus(); - } - void set_surplus(ssize_t v) { - assert_proper_lock_protection(); - _allocation_stats.set_surplus(v); - } - void increment_surplus() { - assert_proper_lock_protection(); - _allocation_stats.increment_surplus(); - } - void decrement_surplus() { - assert_proper_lock_protection(); - _allocation_stats.decrement_surplus(); - } - - ssize_t bfrSurp() const { - return _allocation_stats.bfrSurp(); - } - void set_bfrSurp(ssize_t v) { - assert_proper_lock_protection(); - _allocation_stats.set_bfrSurp(v); - } - ssize_t prevSweep() const { - return _allocation_stats.prevSweep(); - } - void set_prevSweep(ssize_t v) { - assert_proper_lock_protection(); - _allocation_stats.set_prevSweep(v); - } - ssize_t beforeSweep() const { - return _allocation_stats.beforeSweep(); - } - void set_beforeSweep(ssize_t v) { - assert_proper_lock_protection(); - _allocation_stats.set_beforeSweep(v); - } - - ssize_t coalBirths() const { - return _allocation_stats.coalBirths(); - } - void set_coalBirths(ssize_t v) { - assert_proper_lock_protection(); - _allocation_stats.set_coalBirths(v); - } - void increment_coalBirths() { - assert_proper_lock_protection(); - _allocation_stats.increment_coalBirths(); - } - - ssize_t coalDeaths() const { - return _allocation_stats.coalDeaths(); - } - void set_coalDeaths(ssize_t v) { - assert_proper_lock_protection(); - _allocation_stats.set_coalDeaths(v); - } - void increment_coalDeaths() { - assert_proper_lock_protection(); - _allocation_stats.increment_coalDeaths(); - } - - ssize_t splitBirths() const { - return _allocation_stats.splitBirths(); - } - void set_splitBirths(ssize_t v) { - assert_proper_lock_protection(); - _allocation_stats.set_splitBirths(v); - } - void increment_splitBirths() { - assert_proper_lock_protection(); - _allocation_stats.increment_splitBirths(); - } - - ssize_t splitDeaths() const { - return _allocation_stats.splitDeaths(); - } - void set_splitDeaths(ssize_t v) { - assert_proper_lock_protection(); - _allocation_stats.set_splitDeaths(v); - } - void increment_splitDeaths() { - assert_proper_lock_protection(); - _allocation_stats.increment_splitDeaths(); - } - - NOT_PRODUCT( - // For debugging. The "_returnedBytes" in all the lists are summed - // and compared with the total number of bytes swept during a - // collection. - size_t returnedBytes() const { return _allocation_stats.returnedBytes(); } - void set_returnedBytes(size_t v) { _allocation_stats.set_returnedBytes(v); } - void increment_returnedBytes_by(size_t v) { - _allocation_stats.set_returnedBytes(_allocation_stats.returnedBytes() + v); - } - ) - - // Unlink head of list and return it. Returns NULL if - // the list is empty. - FreeChunk* getChunkAtHead(); - - // Remove the first "n" or "count", whichever is smaller, chunks from the - // list, setting "fl", which is required to be empty, to point to them. - void getFirstNChunksFromList(size_t n, FreeList* fl); - - // Unlink this chunk from it's free list - void removeChunk(FreeChunk* fc); - - // Add this chunk to this free list. - void returnChunkAtHead(FreeChunk* fc); - void returnChunkAtTail(FreeChunk* fc); - - // Similar to returnChunk* but also records some diagnostic - // information. - void returnChunkAtHead(FreeChunk* fc, bool record_return); - void returnChunkAtTail(FreeChunk* fc, bool record_return); - - // Prepend "fl" (whose size is required to be the same as that of "this") - // to the front of "this" list. - void prepend(FreeList* fl); - - // Verify that the chunk is in the list. - // found. Return NULL if "fc" is not found. - bool verifyChunkInFreeLists(FreeChunk* fc) const; - - // Stats verification - void verify_stats() const PRODUCT_RETURN; - - // Printing support - static void print_labels_on(outputStream* st, const char* c); - void print_on(outputStream* st, const char* c = NULL) const; -}; - -#endif // SHARE_VM_GC_IMPLEMENTATION_CONCURRENTMARKSWEEP_FREELIST_HPP diff -r 3c91f2c9fd21 -r 9f059abe8cf2 src/share/vm/gc_implementation/concurrentMarkSweep/vmStructs_cms.hpp --- a/src/share/vm/gc_implementation/concurrentMarkSweep/vmStructs_cms.hpp Fri Apr 20 17:13:36 2012 -0700 +++ b/src/share/vm/gc_implementation/concurrentMarkSweep/vmStructs_cms.hpp Thu Mar 29 19:46:24 2012 -0700 @@ -44,11 +44,11 @@ nonstatic_field(FreeChunk, _next, FreeChunk*) \ nonstatic_field(FreeChunk, _prev, FreeChunk*) \ nonstatic_field(LinearAllocBlock, _word_size, size_t) \ - nonstatic_field(FreeList, _size, size_t) \ - nonstatic_field(FreeList, _count, ssize_t) \ - nonstatic_field(BinaryTreeDictionary, _totalSize, size_t) \ - nonstatic_field(CompactibleFreeListSpace, _dictionary, FreeBlockDictionary*) \ - nonstatic_field(CompactibleFreeListSpace, _indexedFreeList[0], FreeList) \ + nonstatic_field(FreeList, _size, size_t) \ + nonstatic_field(FreeList, _count, ssize_t) \ + nonstatic_field(BinaryTreeDictionary,_totalSize, size_t) \ + nonstatic_field(CompactibleFreeListSpace, _dictionary, FreeBlockDictionary*) \ + nonstatic_field(CompactibleFreeListSpace, _indexedFreeList[0], FreeList) \ nonstatic_field(CompactibleFreeListSpace, _smallLinearAllocBlock, LinearAllocBlock) @@ -70,13 +70,13 @@ declare_toplevel_type(CompactibleFreeListSpace*) \ declare_toplevel_type(CMSCollector*) \ declare_toplevel_type(FreeChunk*) \ - declare_toplevel_type(BinaryTreeDictionary*) \ - declare_toplevel_type(FreeBlockDictionary*) \ - declare_toplevel_type(FreeList*) \ - declare_toplevel_type(FreeList) \ + declare_toplevel_type(BinaryTreeDictionary*) \ + declare_toplevel_type(FreeBlockDictionary*) \ + declare_toplevel_type(FreeList*) \ + declare_toplevel_type(FreeList) \ declare_toplevel_type(LinearAllocBlock) \ - declare_toplevel_type(FreeBlockDictionary) \ - declare_type(BinaryTreeDictionary, FreeBlockDictionary) + declare_toplevel_type(FreeBlockDictionary) \ + declare_type(BinaryTreeDictionary, FreeBlockDictionary) #define VM_INT_CONSTANTS_CMS(declare_constant) \ declare_constant(Generation::ConcurrentMarkSweep) \ diff -r 3c91f2c9fd21 -r 9f059abe8cf2 src/share/vm/memory/binaryTreeDictionary.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/share/vm/memory/binaryTreeDictionary.cpp Thu Mar 29 19:46:24 2012 -0700 @@ -0,0 +1,1343 @@ +/* + * Copyright (c) 2001, 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * 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 +TreeChunk* TreeChunk::as_TreeChunk(Chunk* fc) { + // Do some assertion checking here. + return (TreeChunk*) fc; +} + +template +void TreeChunk::verifyTreeChunkList() 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"); + } + if (nextTC != NULL) { + guarantee(as_TreeChunk(nextTC->prev()) == this, "broken chain"); + guarantee(nextTC->size() == size(), "wrong size"); + nextTC->verifyTreeChunkList(); + } +} + + +template +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(); + 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->setParent(NULL); + tl->setLeft(NULL); + tl->setRight(NULL); + 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->setSize(size); + tc->linkPrev(NULL); + tc->linkNext(NULL); + TreeList* tl = TreeList::as_TreeList(tc); + return tl; +} + +template +TreeList* TreeList::removeChunkReplaceIfNeeded(TreeChunk* tc) { + + TreeList* retTL = this; + Chunk* 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() || + this == parent()->right(), "list is inconsistent"); + assert(tc->isFree(), "Header is not marked correctly"); + 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()); + 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 + // 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 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); + set_head(NULL); + } else { + // copy embedded list. + nextTC->set_embedded_list(tc->embedded_list()); + retTL = nextTC->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. + 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. + if (retTL->parent() != NULL) { + if (this == retTL->parent()->left()) { + retTL->parent()->setLeft(retTL); + } else { + assert(this == retTL->parent()->right(), "Parent is incorrect"); + retTL->parent()->setRight(retTL); + } + } + // Fix the children's parent pointers to point to the + // new list. + assert(right() == retTL->right(), "Should have been copied"); + if (retTL->right() != NULL) { + retTL->right()->setParent(retTL); + } + assert(left() == retTL->left(), "Should have been copied"); + if (retTL->left() != NULL) { + retTL->left()->setParent(retTL); + } + retTL->link_head(nextTC); + assert(nextTC->isFree(), "Should be a free chunk"); + } + } else { + if (nextTC == NULL) { + // Removing chunk at tail of list + link_tail(prevFC); + } + // Chunk is interior to the list + prevFC->linkAfter(nextTC); + } + + // Below this point the embeded TreeList being used for the + // tree node may have changed. Don't use "this" + // 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"); + debug_only( + tc->linkPrev(NULL); + tc->linkNext(NULL); + tc->set_list(NULL); + bool prev_found = false; + bool next_found = false; + for (Chunk* curFC = retTL->head(); + curFC != NULL; curFC = curFC->next()) { + assert(curFC != tc, "Chunk is still in list"); + if (curFC == prevFC) { + prev_found = true; + } + if (curFC == nextTC) { + next_found = true; + } + } + assert(prevFC == NULL || prev_found, "Chunk was lost from list"); + assert(nextTC == NULL || next_found, "Chunk was lost from list"); + assert(retTL->parent() == NULL || + retTL == retTL->parent()->left() || + retTL == retTL->parent()->right(), + "list is inconsistent"); + ) + retTL->decrement_count(); + + assert(tc->isFree(), "Should still be a free chunk"); + assert(retTL->head() == NULL || retTL->head()->prev() == NULL, + "list invariant"); + assert(retTL->tail() == NULL || retTL->tail()->next() == NULL, + "list invariant"); + return retTL; +} + +template +void TreeList::returnChunkAtTail(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"); + // which means that the list can never be empty. + assert(!verifyChunkInFreeLists(chunk), "Double entry"); + assert(head() == NULL || head()->prev() == NULL, "list invariant"); + assert(tail() == NULL || tail()->next() == NULL, "list invariant"); + + Chunk* fc = tail(); + fc->linkAfter(chunk); + link_tail(chunk); + + assert(!tail() || size() == tail()->size(), "Wrong sized chunk in list"); + FreeList::increment_count(); + debug_only(increment_returnedBytes_by(chunk->size()*sizeof(HeapWord));) + assert(head() == NULL || head()->prev() == NULL, "list invariant"); + assert(tail() == NULL || tail()->next() == NULL, "list invariant"); +} + +// 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::returnChunkAtHead(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"); + assert(!verifyChunkInFreeLists(chunk), "Double entry"); + assert(head() == NULL || head()->prev() == NULL, "list invariant"); + assert(tail() == NULL || tail()->next() == NULL, "list invariant"); + + Chunk* fc = head()->next(); + if (fc != NULL) { + chunk->linkAfter(fc); + } else { + assert(tail() == NULL, "List is inconsistent"); + link_tail(chunk); + } + head()->linkAfter(chunk); + assert(!head() || size() == head()->size(), "Wrong sized chunk in list"); + FreeList::increment_count(); + debug_only(increment_returnedBytes_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 +TreeChunk* TreeList::first_available() { + assert(head() != NULL, "The head of the list cannot be NULL"); + Chunk* fc = head()->next(); + TreeChunk* retTC; + if (fc == NULL) { + retTC = head_as_TreeChunk(); + } else { + retTC = TreeChunk::as_TreeChunk(fc); + } + assert(retTC->list() == this, "Wrong type of chunk."); + 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 +TreeChunk* TreeList::largest_address() { + assert(head() != NULL, "The head of the list cannot be NULL"); + Chunk* 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; + while (fc->next() != NULL) { + if ((HeapWord*)last < (HeapWord*)fc) { + last = fc; + } + fc = fc->next(); + } + 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), + _totalSize(0), _totalFreeBlocks(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"); + + reset(mr); + assert(root()->left() == NULL, "reset check failed"); + assert(root()->right() == NULL, "reset check failed"); + assert(root()->head()->next() == NULL, "reset check failed"); + assert(root()->head()->prev() == NULL, "reset check failed"); + assert(totalSize() == root()->size(), "reset check failed"); + assert(totalFreeBlocks() == 1, "reset check failed"); +} + +template +void BinaryTreeDictionary::inc_totalSize(size_t inc) { + _totalSize = _totalSize + inc; +} + +template +void BinaryTreeDictionary::dec_totalSize(size_t dec) { + _totalSize = _totalSize - 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())); + set_totalSize(mr.word_size()); + set_totalFreeBlocks(1); +} + +template +void BinaryTreeDictionary::reset(HeapWord* addr, size_t byte_size) { + MemRegion mr(addr, heap_word_size(byte_size)); + reset(mr); +} + +template +void BinaryTreeDictionary::reset() { + set_root(NULL); + set_totalSize(0); + set_totalFreeBlocks(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::getChunkFromTree(size_t size, enum FreeBlockDictionary::Dither dither, bool splay) +{ + TreeList *curTL, *prevTL; + TreeChunk* retTC = NULL; + assert(size >= BinaryTreeDictionary::min_tree_chunk_size, "minimum chunk size"); + if (FLSVerifyDictionary) { + verifyTree(); + } + // starting at the root, work downwards trying to find match. + // Remember the last node of size too great or too small. + for (prevTL = curTL = root(); curTL != NULL;) { + if (curTL->size() == size) { // exact match + break; + } + prevTL = curTL; + if (curTL->size() < size) { // proceed to right sub-tree + curTL = curTL->right(); + } else { // proceed to left sub-tree + assert(curTL->size() > size, "size inconsistency"); + curTL = curTL->left(); + } + } + if (curTL == NULL) { // couldn't find exact match + + 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;) { + if (curTL->size() >= size) break; + else curTL = curTL->parent(); + } + assert(curTL == NULL || curTL->count() > 0, + "An empty list should not be in the tree"); + } + 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 = findList(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) { + semiSplayStep(curTL); + } + retTC = curTL->first_available(); + assert((retTC != NULL) && (curTL->count() > 0), + "A list in the binary tree should not be NULL"); + assert(retTC->size() >= size, + "A chunk of the wrong size was found"); + removeChunkFromTree(retTC); + assert(retTC->isFree(), "Header is not marked correctly"); + } + + if (FLSVerifyDictionary) { + verify(); + } + return retTC; +} + +template +TreeList* BinaryTreeDictionary::findList(size_t size) const { + TreeList* curTL; + for (curTL = root(); curTL != NULL;) { + if (curTL->size() == size) { // exact match + break; + } + + if (curTL->size() < size) { // proceed to right sub-tree + curTL = curTL->right(); + } else { // proceed to left sub-tree + assert(curTL->size() > size, "size inconsistency"); + curTL = curTL->left(); + } + } + return curTL; +} + + +template +bool BinaryTreeDictionary::verifyChunkInFreeLists(Chunk* tc) const { + size_t size = tc->size(); + TreeList* tl = findList(size); + if (tl == NULL) { + return false; + } else { + return tl->verifyChunkInFreeLists(tc); + } +} + +template +Chunk* BinaryTreeDictionary::findLargestDict() const { + TreeList *curTL = root(); + if (curTL != NULL) { + while(curTL->right() != NULL) curTL = curTL->right(); + 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 +TreeChunk* +BinaryTreeDictionary::removeChunkFromTree(TreeChunk* tc) { + assert(tc != NULL, "Should not call with a NULL chunk"); + assert(tc->isFree(), "Header is not marked correctly"); + + TreeList *newTL, *parentTL; + TreeChunk* retTC; + TreeList* tl = tc->list(); + debug_only( + bool removing_only_chunk = false; + if (tl == _root) { + if ((_root->left() == NULL) && (_root->right() == NULL)) { + if (_root->count() == 1) { + assert(_root->head() == tc, "Should only be this one chunk"); + removing_only_chunk = true; + } + } + } + ) + assert(tl != NULL, "List should be set"); + assert(tl->parent() == NULL || tl == tl->parent()->left() || + tl == tl->parent()->right(), "list is inconsistent"); + + bool complicatedSplice = false; + + 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->removeChunkReplaceIfNeeded(tc); + assert(tc->isFree(), "Chunk should still be free"); + assert(replacementTL->parent() == NULL || + replacementTL == replacementTL->parent()->left() || + replacementTL == replacementTL->parent()->right(), + "list is inconsistent"); + if (tl == root()) { + assert(replacementTL->parent() == NULL, "Incorrectly replacing root"); + set_root(replacementTL); + } + debug_only( + 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(); + assert(rhl == replacementTL, "Broken head"); + assert(rtl == replacementTL, "Broken tail"); + assert(replacementTL->size() == tc->size(), "Broken size"); + } + ) + + // Does the tree need to be repaired? + if (replacementTL->count() == 0) { + assert(replacementTL->head() == NULL && + replacementTL->tail() == NULL, "list count is incorrect"); + // 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 + if (replacementTL->left() == NULL) { + // left is NULL so pick right. right may also be NULL. + newTL = replacementTL->right(); + debug_only(replacementTL->clearRight();) + } else if (replacementTL->right() == NULL) { + // right is NULL + newTL = replacementTL->left(); + debug_only(replacementTL->clearLeft();) + } else { // we have both children, so, by patriarchal convention, + // my replacement is least node in right sub-tree + complicatedSplice = true; + newTL = removeTreeMinimum(replacementTL->right()); + assert(newTL != NULL && newTL->left() == NULL && + newTL->right() == NULL, "sub-tree minimum exists"); + } + // 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 + if ((parentTL = replacementTL->parent()) == NULL) { + // newTL should be root + assert(tl == root(), "Incorrectly replacing root"); + set_root(newTL); + if (newTL != NULL) { + newTL->clearParent(); + } + } else if (parentTL->right() == replacementTL) { + // replacementTL is a right child + parentTL->setRight(newTL); + } else { // replacementTL is a left child + assert(parentTL->left() == replacementTL, "should be left child"); + parentTL->setLeft(newTL); + } + debug_only(replacementTL->clearParent();) + if (complicatedSplice) { // we need newTL to get replacementTL's + // two children + assert(newTL != NULL && + newTL->left() == NULL && newTL->right() == NULL, + "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: + assert(replacementTL->left() != NULL, "else !complicatedSplice"); + newTL->setLeft(replacementTL->left()); + newTL->setRight(replacementTL->right()); + debug_only( + replacementTL->clearRight(); + replacementTL->clearLeft(); + ) + } + assert(replacementTL->right() == NULL && + replacementTL->left() == NULL && + replacementTL->parent() == NULL, + "delete without encumbrances"); + } + + assert(totalSize() >= retTC->size(), "Incorrect total size"); + dec_totalSize(retTC->size()); // size book-keeping + assert(totalFreeBlocks() > 0, "Incorrect total count"); + set_totalFreeBlocks(totalFreeBlocks() - 1); + + assert(retTC != NULL, "null chunk?"); + assert(retTC->prev() == NULL && retTC->next() == NULL, + "should return without encumbrances"); + if (FLSVerifyDictionary) { + verifyTree(); + } + assert(!removing_only_chunk || _root == NULL, "root should be NULL"); + 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::removeTreeMinimum(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; + 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(); + if (parentTL->left() == curTL) { // curTL is a left child + parentTL->setLeft(curTL->right()); + } else { + // If the list tl has no left child, then curTL may be + // the right child of parentTL. + assert(parentTL->right() == curTL, "should be a right child"); + parentTL->setRight(curTL->right()); + } + } 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. + set_root(NULL); + } + debug_only( + curTL->clearParent(); // Test if this needs to be cleared + curTL->clearRight(); // recall, above, left child is already null + ) + // 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) +// . 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::semiSplayStep(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::insertChunkInTree(Chunk* fc) { + TreeList *curTL, *prevTL; + size_t size = fc->size(); + + assert(size >= BinaryTreeDictionary::min_tree_chunk_size, "too small to be a TreeList"); + if (FLSVerifyDictionary) { + verifyTree(); + } + + fc->clearNext(); + fc->linkPrev(NULL); + + // work down from the _root, looking for insertion point + for (prevTL = curTL = root(); curTL != NULL;) { + if (curTL->size() == size) // exact match + break; + prevTL = curTL; + if (curTL->size() > size) { // follow left branch + curTL = curTL->left(); + } else { // follow right branch + assert(curTL->size() < size, "size inconsistency"); + curTL = curTL->right(); + } + } + TreeChunk* tc = TreeChunk::as_TreeChunk(fc); + // This chunk is being returned to the binary tree. Its embedded + // TreeList should be unused at this point. + tc->initialize(); + if (curTL != NULL) { // exact match + tc->set_list(curTL); + curTL->returnChunkAtTail(tc); + } else { // need a new node in tree + tc->clearNext(); + tc->linkPrev(NULL); + 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"); + set_root(newTL); + } else { // insert under prevTL ... + if (prevTL->size() < size) { // am right child + assert(prevTL->right() == NULL, "control point invariant"); + prevTL->setRight(newTL); + } else { // am left child + assert(prevTL->size() > size && prevTL->left() == NULL, "cpt pt inv"); + prevTL->setLeft(newTL); + } + } + } + assert(tc->list() != NULL, "Tree list should be set"); + + inc_totalSize(size); + // 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 + assert(!FLSVerifyDictionary || totalSizeInTree(root()) == totalSize(), "_totalSize inconsistency"); + set_totalFreeBlocks(totalFreeBlocks() + 1); + if (FLSVerifyDictionary) { + verifyTree(); + } +} + +template +size_t BinaryTreeDictionary::maxChunkSize() 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::totalListLength(TreeList* tl) const { + size_t res; + res = tl->count(); +#ifdef ASSERT + size_t cnt; + Chunk* 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::totalSizeInTree(TreeList* tl) const { + if (tl == NULL) + return 0; + return (tl->size() * totalListLength(tl)) + + totalSizeInTree(tl->left()) + + totalSizeInTree(tl->right()); +} + +template +double BinaryTreeDictionary::sum_of_squared_block_sizes(TreeList* const tl) const { + if (tl == NULL) { + return 0.0; + } + double size = (double)(tl->size()); + double curr = size * size * totalListLength(tl); + curr += sum_of_squared_block_sizes(tl->left()); + curr += sum_of_squared_block_sizes(tl->right()); + return curr; +} + +template +size_t BinaryTreeDictionary::totalFreeBlocksInTree(TreeList* tl) const { + if (tl == NULL) + return 0; + return totalListLength(tl) + + totalFreeBlocksInTree(tl->left()) + + totalFreeBlocksInTree(tl->right()); +} + +template +size_t BinaryTreeDictionary::numFreeBlocks() const { + assert(totalFreeBlocksInTree(root()) == totalFreeBlocks(), + "_totalFreeBlocks inconsistency"); + return totalFreeBlocks(); +} + +template +size_t BinaryTreeDictionary::treeHeightHelper(TreeList* tl) const { + if (tl == NULL) + return 0; + return 1 + MAX2(treeHeightHelper(tl->left()), + treeHeightHelper(tl->right())); +} + +template +size_t BinaryTreeDictionary::treeHeight() const { + return treeHeightHelper(root()); +} + +template +size_t BinaryTreeDictionary::totalNodesHelper(TreeList* tl) const { + if (tl == NULL) { + return 0; + } + return 1 + totalNodesHelper(tl->left()) + + totalNodesHelper(tl->right()); +} + +template +size_t BinaryTreeDictionary::totalNodesInTree(TreeList* tl) const { + return totalNodesHelper(root()); +} + +template +void BinaryTreeDictionary::dictCensusUpdate(size_t size, bool split, bool birth){ + TreeList* nd = findList(size); + if (nd) { + if (split) { + if (birth) { + nd->increment_splitBirths(); + nd->increment_surplus(); + } else { + nd->increment_splitDeaths(); + nd->decrement_surplus(); + } + } else { + if (birth) { + nd->increment_coalBirths(); + nd->increment_surplus(); + } else { + nd->increment_coalDeaths(); + 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 +bool BinaryTreeDictionary::coalDictOverPopulated(size_t size) { + if (FLSAlwaysCoalesceLarge) return true; + + TreeList* list_of_size = findList(size); + // None of requested size implies overpopulated. + return list_of_size == NULL || list_of_size->coalDesired() <= 0 || + list_of_size->count() > list_of_size->coalDesired(); +} + +// 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 TreeCensusClosure : public StackObj { + protected: + virtual void do_list(FreeList* fl) = 0; + public: + virtual void do_tree(TreeList* tl) = 0; +}; + +template +class AscendTreeCensusClosure : public TreeCensusClosure { + public: + void do_tree(TreeList* tl) { + if (tl != NULL) { + do_tree(tl->left()); + do_list(tl); + do_tree(tl->right()); + } + } +}; + +template +class DescendTreeCensusClosure : public TreeCensusClosure { + public: + void do_tree(TreeList* tl) { + if (tl != NULL) { + do_tree(tl->right()); + do_list(tl); + do_tree(tl->left()); + } + } +}; + +// For each list in the tree, calculate the desired, desired +// coalesce, count before sweep, and surplus before sweep. +template +class BeginSweepClosure : public AscendTreeCensusClosure { + 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), + _inter_sweep_current(inter_sweep_current), + _inter_sweep_estimate(inter_sweep_estimate), + _intra_sweep_estimate(intra_sweep_estimate) { } + + void do_list(FreeList* fl) { + double coalSurplusPercent = _percentage; + fl->compute_desired(_inter_sweep_current, _inter_sweep_estimate, _intra_sweep_estimate); + fl->set_coalDesired((ssize_t)((double)fl->desired() * coalSurplusPercent)); + fl->set_beforeSweep(fl->count()); + fl->set_bfrSurp(fl->surplus()); + } +}; + +// Used to search the tree until a condition is met. +// Similar to TreeCensusClosure but searches the +// tree and returns promptly when found. + +template +class TreeSearchClosure : public StackObj { + protected: + virtual bool do_list(FreeList* fl) = 0; + public: + virtual bool do_tree(TreeList* tl) = 0; +}; + +#if 0 // Don't need this yet but here for symmetry. +template +class AscendTreeSearchClosure : public TreeSearchClosure { + public: + bool do_tree(TreeList* tl) { + if (tl != NULL) { + if (do_tree(tl->left())) return true; + if (do_list(tl)) return true; + if (do_tree(tl->right())) return true; + } + return false; + } +}; +#endif + +template +class DescendTreeSearchClosure : public TreeSearchClosure { + public: + bool do_tree(TreeList* tl) { + if (tl != NULL) { + if (do_tree(tl->right())) return true; + if (do_list(tl)) return true; + if (do_tree(tl->left())) return true; + } + return false; + } +}; + +// Searches the tree for a chunk that ends at the +// specified address. +template +class EndTreeSearchClosure : public DescendTreeSearchClosure { + HeapWord* _target; + Chunk* _found; + + public: + EndTreeSearchClosure(HeapWord* target) : _target(target), _found(NULL) {} + bool do_list(FreeList* fl) { + Chunk* item = fl->head(); + while (item != NULL) { + if (item->end() == _target) { + _found = item; + return true; + } + item = item->next(); + } + return false; + } + Chunk* found() { return _found; } +}; + +template +Chunk* BinaryTreeDictionary::find_chunk_ends_at(HeapWord* target) const { + EndTreeSearchClosure etsc(target); + bool found_target = etsc.do_tree(root()); + assert(found_target || etsc.found() == NULL, "Consistency check"); + assert(!found_target || etsc.found() != NULL, "Consistency check"); + return etsc.found(); +} + +template +void BinaryTreeDictionary::beginSweepDictCensus(double coalSurplusPercent, + float inter_sweep_current, float inter_sweep_estimate, float intra_sweep_estimate) { + BeginSweepClosure bsc(coalSurplusPercent, inter_sweep_current, + inter_sweep_estimate, + intra_sweep_estimate); + bsc.do_tree(root()); +} + +// Closures and methods for calculating total bytes returned to the +// free lists in the tree. +#ifndef PRODUCT +template +class InitializeDictReturnedBytesClosure : public AscendTreeCensusClosure { + public: + void do_list(FreeList* fl) { + fl->set_returnedBytes(0); + } +}; + +template +void BinaryTreeDictionary::initializeDictReturnedBytes() { + InitializeDictReturnedBytesClosure idrb; + idrb.do_tree(root()); +} + +template +class ReturnedBytesClosure : public AscendTreeCensusClosure { + size_t _dictReturnedBytes; + public: + ReturnedBytesClosure() { _dictReturnedBytes = 0; } + void do_list(FreeList* fl) { + _dictReturnedBytes += fl->returnedBytes(); + } + size_t dictReturnedBytes() { return _dictReturnedBytes; } +}; + +template +size_t BinaryTreeDictionary::sumDictReturnedBytes() { + ReturnedBytesClosure rbc; + rbc.do_tree(root()); + + return rbc.dictReturnedBytes(); +} + +// Count the number of entries in the tree. +template +class treeCountClosure : public DescendTreeCensusClosure { + public: + uint count; + treeCountClosure(uint c) { count = c; } + void do_list(FreeList* fl) { + count++; + } +}; + +template +size_t BinaryTreeDictionary::totalCount() { + treeCountClosure ctc(0); + ctc.do_tree(root()); + return ctc.count; +} +#endif // PRODUCT + +// Calculate surpluses for the lists in the tree. +template +class setTreeSurplusClosure : public AscendTreeCensusClosure { + double percentage; + public: + setTreeSurplusClosure(double v) { percentage = v; } + void do_list(FreeList* fl) { + double splitSurplusPercent = percentage; + fl->set_surplus(fl->count() - + (ssize_t)((double)fl->desired() * splitSurplusPercent)); + } +}; + +template +void BinaryTreeDictionary::setTreeSurplus(double splitSurplusPercent) { + setTreeSurplusClosure sts(splitSurplusPercent); + sts.do_tree(root()); +} + +// Set hints for the lists in the tree. +template +class setTreeHintsClosure : public DescendTreeCensusClosure { + size_t hint; + public: + setTreeHintsClosure(size_t v) { hint = v; } + void do_list(FreeList* fl) { + fl->set_hint(hint); + assert(fl->hint() == 0 || fl->hint() > fl->size(), + "Current hint is inconsistent"); + if (fl->surplus() > 0) { + hint = fl->size(); + } + } +}; + +template +void BinaryTreeDictionary::setTreeHints(void) { + setTreeHintsClosure sth(0); + sth.do_tree(root()); +} + +// Save count before previous sweep and splits and coalesces. +template +class clearTreeCensusClosure : public AscendTreeCensusClosure { + void do_list(FreeList* fl) { + fl->set_prevSweep(fl->count()); + fl->set_coalBirths(0); + fl->set_coalDeaths(0); + fl->set_splitBirths(0); + fl->set_splitDeaths(0); + } +}; + +template +void BinaryTreeDictionary::clearTreeCensus(void) { + clearTreeCensusClosure ctc; + ctc.do_tree(root()); +} + +// Do reporting and post sweep clean up. +template +void BinaryTreeDictionary::endSweepDictCensus(double splitSurplusPercent) { + // Does walking the tree 3 times hurt? + setTreeSurplus(splitSurplusPercent); + setTreeHints(); + if (PrintGC && Verbose) { + reportStatistics(); + } + clearTreeCensus(); +} + +// Print summary statistics +template +void BinaryTreeDictionary::reportStatistics() const { + FreeBlockDictionary::verify_par_locked(); + gclog_or_tty->print("Statistics for BinaryTreeDictionary:\n" + "------------------------------------\n"); + size_t totalSize = totalChunkSize(debug_only(NULL)); + size_t freeBlocks = numFreeBlocks(); + gclog_or_tty->print("Total Free Space: %d\n", totalSize); + gclog_or_tty->print("Max Chunk Size: %d\n", maxChunkSize()); + gclog_or_tty->print("Number of Blocks: %d\n", freeBlocks); + if (freeBlocks > 0) { + gclog_or_tty->print("Av. Block Size: %d\n", totalSize/freeBlocks); + } + gclog_or_tty->print("Tree Height: %d\n", treeHeight()); +} + +// Print census information - counts, births, deaths, etc. +// for each list in the tree. Also print some summary +// information. +template +class PrintTreeCensusClosure : public AscendTreeCensusClosure { + int _print_line; + size_t _totalFree; + FreeList _total; + + public: + PrintTreeCensusClosure() { + _print_line = 0; + _totalFree = 0; + } + FreeList* total() { return &_total; } + size_t totalFree() { return _totalFree; } + void do_list(FreeList* fl) { + if (++_print_line >= 40) { + FreeList::print_labels_on(gclog_or_tty, "size"); + _print_line = 0; + } + fl->print_on(gclog_or_tty); + _totalFree += fl->count() * fl->size() ; + total()->set_count( total()->count() + fl->count() ); + total()->set_bfrSurp( total()->bfrSurp() + fl->bfrSurp() ); + total()->set_surplus( total()->splitDeaths() + fl->surplus() ); + total()->set_desired( total()->desired() + fl->desired() ); + total()->set_prevSweep( total()->prevSweep() + fl->prevSweep() ); + total()->set_beforeSweep(total()->beforeSweep() + fl->beforeSweep()); + total()->set_coalBirths( total()->coalBirths() + fl->coalBirths() ); + total()->set_coalDeaths( total()->coalDeaths() + fl->coalDeaths() ); + total()->set_splitBirths(total()->splitBirths() + fl->splitBirths()); + total()->set_splitDeaths(total()->splitDeaths() + fl->splitDeaths()); + } +}; + +template +void BinaryTreeDictionary::printDictCensus(void) const { + + gclog_or_tty->print("\nBinaryTree\n"); + FreeList::print_labels_on(gclog_or_tty, "size"); + PrintTreeCensusClosure ptc; + ptc.do_tree(root()); + + FreeList* total = ptc.total(); + FreeList::print_labels_on(gclog_or_tty, " "); + total->print_on(gclog_or_tty, "TOTAL\t"); + gclog_or_tty->print( + "totalFree(words): " SIZE_FORMAT_W(16) + " growth: %8.5f deficit: %8.5f\n", + ptc.totalFree(), + (double)(total->splitBirths() + total->coalBirths() + - total->splitDeaths() - total->coalDeaths()) + /(total->prevSweep() != 0 ? (double)total->prevSweep() : 1.0), + (double)(total->desired() - total->count()) + /(total->desired() != 0 ? (double)total->desired() : 1.0)); +} + +template +class PrintFreeListsClosure : public AscendTreeCensusClosure { + outputStream* _st; + int _print_line; + + public: + PrintFreeListsClosure(outputStream* st) { + _st = st; + _print_line = 0; + } + void do_list(FreeList* fl) { + if (++_print_line >= 40) { + FreeList::print_labels_on(_st, "size"); + _print_line = 0; + } + fl->print_on(gclog_or_tty); + size_t sz = fl->size(); + for (Chunk* fc = fl->head(); fc != NULL; + fc = fc->next()) { + _st->print_cr("\t[" PTR_FORMAT "," PTR_FORMAT ") %s", + fc, (HeapWord*)fc + sz, + fc->cantCoalesce() ? "\t CC" : ""); + } + } +}; + +template +void BinaryTreeDictionary::print_free_lists(outputStream* st) const { + + FreeList::print_labels_on(st, "size"); + PrintFreeListsClosure pflc(st); + pflc.do_tree(root()); +} + +// 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 +void BinaryTreeDictionary::verifyTree() const { + guarantee(root() == NULL || totalFreeBlocks() == 0 || + totalSize() != 0, "_totalSize should't be 0?"); + guarantee(root() == NULL || root()->parent() == NULL, "_root shouldn't have parent"); + verifyTreeHelper(root()); +} + +template +size_t BinaryTreeDictionary::verifyPrevFreePtrs(TreeList* tl) { + size_t ct = 0; + for (Chunk* curFC = tl->head(); curFC != NULL; curFC = curFC->next()) { + ct++; + assert(curFC->prev() == NULL || curFC->prev()->isFree(), + "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 +void BinaryTreeDictionary::verifyTreeHelper(TreeList* tl) const { + if (tl == NULL) + return; + guarantee(tl->size() != 0, "A list must has a size"); + guarantee(tl->left() == NULL || tl->left()->parent() == tl, + "parent<-/->left"); + guarantee(tl->right() == NULL || tl->right()->parent() == tl, + "parent<-/->right");; + guarantee(tl->left() == NULL || tl->left()->size() < tl->size(), + "parent !> left"); + guarantee(tl->right() == NULL || tl->right()->size() > tl->size(), + "parent !< left"); + guarantee(tl->head() == NULL || tl->head()->isFree(), "!Free"); + guarantee(tl->head() == NULL || tl->head_as_TreeChunk()->list() == tl, + "list inconsistency"); + guarantee(tl->count() > 0 || (tl->head() == NULL && tl->tail() == NULL), + "list count is inconsistent"); + guarantee(tl->count() > 1 || tl->head() == tl->tail(), + "list is incorrectly constructed"); + size_t count = verifyPrevFreePtrs(tl); + guarantee(count == (size_t)tl->count(), "Node count is incorrect"); + if (tl->head() != NULL) { + tl->head_as_TreeChunk()->verifyTreeChunkList(); + } + verifyTreeHelper(tl->left()); + verifyTreeHelper(tl->right()); +} + +template +void BinaryTreeDictionary::verify() const { + verifyTree(); + guarantee(totalSize() == totalSizeInTree(root()), "Total Size inconsistency"); +} + +#ifndef SERIALGC +// Explicitly instantiate these types for FreeChunk. +template class BinaryTreeDictionary; +template class TreeChunk; +template class TreeList; +#endif // SERIALGC diff -r 3c91f2c9fd21 -r 9f059abe8cf2 src/share/vm/memory/binaryTreeDictionary.hpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/share/vm/memory/binaryTreeDictionary.hpp Thu Mar 29 19:46:24 2012 -0700 @@ -0,0 +1,329 @@ +/* + * Copyright (c) 2001, 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * 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. + * + */ + +#ifndef SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP +#define SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP + +#include "memory/freeBlockDictionary.hpp" +#include "memory/freeList.hpp" + +/* + * A binary tree based search structure for free blocks. + * This is currently used in the Concurrent Mark&Sweep implementation, but + * will be used for free block management for metadata. + */ + +// A TreeList is a FreeList which can be used to maintain a +// binary tree of free lists. + +template class TreeChunk; +template class BinaryTreeDictionary; +template class AscendTreeCensusClosure; +template class DescendTreeCensusClosure; +template class DescendTreeSearchClosure; + +template +class TreeList: public FreeList { + friend class TreeChunk; + friend class BinaryTreeDictionary; + friend class AscendTreeCensusClosure; + friend class DescendTreeCensusClosure; + friend class DescendTreeSearchClosure; + + TreeList* _parent; + TreeList* _left; + TreeList* _right; + + protected: + TreeList* parent() const { return _parent; } + TreeList* left() const { return _left; } + TreeList* right() const { return _right; } + + // Wrapper on call to base class, to get the template to compile. + Chunk* head() const { return FreeList::head(); } + Chunk* tail() const { return FreeList::tail(); } + void set_head(Chunk* head) { FreeList::set_head(head); } + void set_tail(Chunk* tail) { FreeList::set_tail(tail); } + + size_t size() const { return FreeList::size(); } + + // Accessors for links in tree. + + void setLeft(TreeList* tl) { + _left = tl; + if (tl != NULL) + tl->setParent(this); + } + void setRight(TreeList* tl) { + _right = tl; + if (tl != NULL) + tl->setParent(this); + } + void setParent(TreeList* tl) { _parent = tl; } + + void clearLeft() { _left = NULL; } + void clearRight() { _right = NULL; } + void clearParent() { _parent = NULL; } + void initialize() { clearLeft(); clearRight(), clearParent(); } + + // For constructing a TreeList from a Tree chunk or + // address and size. + static TreeList* as_TreeList(TreeChunk* tc); + static TreeList* as_TreeList(HeapWord* addr, size_t size); + + // Returns the head of the free list as a pointer to a TreeChunk. + TreeChunk* head_as_TreeChunk(); + + // Returns the first available chunk in the free list as a pointer + // to a TreeChunk. + TreeChunk* first_available(); + + // Returns the block with the largest heap address amongst + // those in the list for this size; potentially slow and expensive, + // use with caution! + TreeChunk* largest_address(); + + // removeChunkReplaceIfNeeded() removes the given "tc" from the TreeList. + // If "tc" is the first chunk in the list, it is also the + // TreeList that is the node in the tree. removeChunkReplaceIfNeeded() + // returns the possibly replaced TreeList* for the node in + // the tree. It also updates the parent of the original + // node to point to the new node. + TreeList* removeChunkReplaceIfNeeded(TreeChunk* tc); + // See FreeList. + void returnChunkAtHead(TreeChunk* tc); + void returnChunkAtTail(TreeChunk* tc); +}; + +// A TreeChunk is a subclass of a Chunk that additionally +// maintains a pointer to the free list on which it is currently +// linked. +// A TreeChunk is also used as a node in the binary tree. This +// allows the binary tree to be maintained without any additional +// storage (the free chunks are used). In a binary tree the first +// chunk in the free list is also the tree node. Note that the +// TreeChunk has an embedded TreeList for this purpose. Because +// the first chunk in the list is distinguished in this fashion +// (also is the node in the tree), it is the last chunk to be found +// on the free list for a node in the tree and is only removed if +// it is the last chunk on the free list. + +template +class TreeChunk : public Chunk { + friend class TreeList; + TreeList* _list; + TreeList _embedded_list; // if non-null, this chunk is on _list + protected: + TreeList* embedded_list() const { return (TreeList*) &_embedded_list; } + void set_embedded_list(TreeList* v) { _embedded_list = *v; } + public: + TreeList* list() { return _list; } + void set_list(TreeList* v) { _list = v; } + static TreeChunk* as_TreeChunk(Chunk* fc); + // Initialize fields in a TreeChunk that should be + // initialized when the TreeChunk is being added to + // a free list in the tree. + void initialize() { embedded_list()->initialize(); } + + Chunk* next() const { return Chunk::next(); } + Chunk* prev() const { return Chunk::prev(); } + size_t size() const volatile { return Chunk::size(); } + + // debugging + void verifyTreeChunkList() const; +}; + + +template +class BinaryTreeDictionary: public FreeBlockDictionary { + friend class VMStructs; + bool _splay; + size_t _totalSize; + size_t _totalFreeBlocks; + TreeList* _root; + bool _adaptive_freelists; + + // private accessors + bool splay() const { return _splay; } + void set_splay(bool v) { _splay = v; } + void set_totalSize(size_t v) { _totalSize = v; } + virtual void inc_totalSize(size_t v); + virtual void dec_totalSize(size_t v); + size_t totalFreeBlocks() const { return _totalFreeBlocks; } + void set_totalFreeBlocks(size_t v) { _totalFreeBlocks = v; } + TreeList* root() const { return _root; } + void set_root(TreeList* v) { _root = v; } + bool adaptive_freelists() { return _adaptive_freelists; } + + // This field is added and can be set to point to the + // the Mutex used to synchronize access to the + // dictionary so that assertion checking can be done. + // For example it is set to point to _parDictionaryAllocLock. + NOT_PRODUCT(Mutex* _lock;) + + // Remove a chunk of size "size" or larger from the tree and + // return it. If the chunk + // is the last chunk of that size, remove the node for that size + // from the tree. + TreeChunk* getChunkFromTree(size_t size, enum FreeBlockDictionary::Dither dither, bool splay); + // Return a list of the specified size or NULL from the tree. + // The list is not removed from the tree. + TreeList* findList (size_t size) const; + // Remove this chunk from the tree. If the removal results + // in an empty list in the tree, remove the empty list. + TreeChunk* removeChunkFromTree(TreeChunk* tc); + // Remove the node in the trees starting at tl that has the + // minimum value and return it. Repair the tree as needed. + TreeList* removeTreeMinimum(TreeList* tl); + void semiSplayStep(TreeList* tl); + // Add this free chunk to the tree. + void insertChunkInTree(Chunk* freeChunk); + public: + + static const size_t min_tree_chunk_size = sizeof(TreeChunk)/HeapWordSize; + + void verifyTree() const; + // verify that the given chunk is in the tree. + bool verifyChunkInFreeLists(Chunk* tc) const; + private: + void verifyTreeHelper(TreeList* tl) const; + static size_t verifyPrevFreePtrs(TreeList* tl); + + // Returns the total number of chunks in the list. + size_t totalListLength(TreeList* tl) const; + // Returns the total number of words in the chunks in the tree + // starting at "tl". + size_t totalSizeInTree(TreeList* tl) const; + // Returns the sum of the square of the size of each block + // in the tree starting at "tl". + double sum_of_squared_block_sizes(TreeList* const tl) const; + // Returns the total number of free blocks in the tree starting + // at "tl". + size_t totalFreeBlocksInTree(TreeList* tl) const; + size_t numFreeBlocks() const; + size_t treeHeight() const; + size_t treeHeightHelper(TreeList* tl) const; + size_t totalNodesInTree(TreeList* tl) const; + size_t totalNodesHelper(TreeList* tl) const; + + public: + // Constructor + BinaryTreeDictionary(bool adaptive_freelists, bool splay = false); + BinaryTreeDictionary(MemRegion mr, bool adaptive_freelists, bool splay = false); + + // Public accessors + size_t totalSize() const { return _totalSize; } + + // Reset the dictionary to the initial conditions with + // a single free chunk. + void reset(MemRegion mr); + void reset(HeapWord* addr, size_t size); + // Reset the dictionary to be empty. + void reset(); + + // Return a chunk of size "size" or greater from + // the tree. + // want a better dynamic splay strategy for the future. + Chunk* getChunk(size_t size, enum FreeBlockDictionary::Dither dither) { + FreeBlockDictionary::verify_par_locked(); + Chunk* res = getChunkFromTree(size, dither, splay()); + assert(res == NULL || res->isFree(), + "Should be returning a free chunk"); + return res; + } + + void returnChunk(Chunk* chunk) { + FreeBlockDictionary::verify_par_locked(); + insertChunkInTree(chunk); + } + + void removeChunk(Chunk* chunk) { + FreeBlockDictionary::verify_par_locked(); + removeChunkFromTree((TreeChunk*)chunk); + assert(chunk->isFree(), "Should still be a free chunk"); + } + + size_t maxChunkSize() const; + size_t totalChunkSize(debug_only(const Mutex* lock)) const { + debug_only( + if (lock != NULL && lock->owned_by_self()) { + assert(totalSizeInTree(root()) == totalSize(), + "_totalSize inconsistency"); + } + ) + return totalSize(); + } + + size_t minSize() const { + return min_tree_chunk_size; + } + + double sum_of_squared_block_sizes() const { + return sum_of_squared_block_sizes(root()); + } + + Chunk* find_chunk_ends_at(HeapWord* target) const; + + // Find the list with size "size" in the binary tree and update + // the statistics in the list according to "split" (chunk was + // split or coalesce) and "birth" (chunk was added or removed). + void dictCensusUpdate(size_t size, bool split, bool birth); + // Return true if the dictionary is overpopulated (more chunks of + // this size than desired) for size "size". + bool coalDictOverPopulated(size_t size); + // Methods called at the beginning of a sweep to prepare the + // statistics for the sweep. + void beginSweepDictCensus(double coalSurplusPercent, + float inter_sweep_current, + float inter_sweep_estimate, + float intra_sweep_estimate); + // Methods called after the end of a sweep to modify the + // statistics for the sweep. + void endSweepDictCensus(double splitSurplusPercent); + // Return the largest free chunk in the tree. + Chunk* findLargestDict() const; + // Accessors for statistics + void setTreeSurplus(double splitSurplusPercent); + void setTreeHints(void); + // Reset statistics for all the lists in the tree. + void clearTreeCensus(void); + // Print the statistcis for all the lists in the tree. Also may + // print out summaries. + void printDictCensus(void) const; + void print_free_lists(outputStream* st) const; + + // For debugging. Returns the sum of the _returnedBytes for + // all lists in the tree. + size_t sumDictReturnedBytes() PRODUCT_RETURN0; + // Sets the _returnedBytes for all the lists in the tree to zero. + void initializeDictReturnedBytes() PRODUCT_RETURN; + // For debugging. Return the total number of chunks in the dictionary. + size_t totalCount() PRODUCT_RETURN0; + + void reportStatistics() const; + + void verify() const; +}; + +#endif // SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP diff -r 3c91f2c9fd21 -r 9f059abe8cf2 src/share/vm/memory/freeBlockDictionary.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/share/vm/memory/freeBlockDictionary.cpp Thu Mar 29 19:46:24 2012 -0700 @@ -0,0 +1,68 @@ +/* + * Copyright (c) 2002, 2010, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * 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" +#ifndef SERIALGC +#include "gc_implementation/concurrentMarkSweep/freeChunk.hpp" +#endif // SERIALGC +#include "memory/freeBlockDictionary.hpp" +#ifdef TARGET_OS_FAMILY_linux +# include "thread_linux.inline.hpp" +#endif +#ifdef TARGET_OS_FAMILY_solaris +# include "thread_solaris.inline.hpp" +#endif +#ifdef TARGET_OS_FAMILY_windows +# include "thread_windows.inline.hpp" +#endif +#ifdef TARGET_OS_FAMILY_bsd +# include "thread_bsd.inline.hpp" +#endif + +#ifndef PRODUCT +template Mutex* FreeBlockDictionary::par_lock() const { + return _lock; +} + +template void FreeBlockDictionary::set_par_lock(Mutex* lock) { + _lock = lock; +} + +template void FreeBlockDictionary::verify_par_locked() const { +#ifdef ASSERT + if (ParallelGCThreads > 0) { + Thread* myThread = Thread::current(); + if (myThread->is_GC_task_thread()) { + assert(par_lock() != NULL, "Should be using locking?"); + assert_lock_strong(par_lock()); + } + } +#endif // ASSERT +} +#endif + +#ifndef SERIALGC +// Explicitly instantiate for FreeChunk +template class FreeBlockDictionary; +#endif // SERIALGC diff -r 3c91f2c9fd21 -r 9f059abe8cf2 src/share/vm/memory/freeBlockDictionary.hpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/share/vm/memory/freeBlockDictionary.hpp Thu Mar 29 19:46:24 2012 -0700 @@ -0,0 +1,102 @@ +/* + * Copyright (c) 2001, 2012, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * 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. + * + */ + +#ifndef SHARE_VM_MEMORY_FREEBLOCKDICTIONARY_HPP +#define SHARE_VM_MEMORY_FREEBLOCKDICTIONARY_HPP + +#include "memory/allocation.hpp" +#include "runtime/mutex.hpp" +#include "utilities/debug.hpp" +#include "utilities/globalDefinitions.hpp" +#include "utilities/ostream.hpp" + +// A FreeBlockDictionary is an abstract superclass that will allow +// a number of alternative implementations in the future. +template +class FreeBlockDictionary: public CHeapObj { + public: + enum Dither { + atLeast, + exactly, + roughly + }; + enum DictionaryChoice { + dictionaryBinaryTree = 0, + dictionarySplayTree = 1, + dictionarySkipList = 2 + }; + + private: + NOT_PRODUCT(Mutex* _lock;) + + public: + virtual void removeChunk(Chunk* fc) = 0; + virtual Chunk* getChunk(size_t size, Dither dither = atLeast) = 0; + virtual void returnChunk(Chunk* chunk) = 0; + virtual size_t totalChunkSize(debug_only(const Mutex* lock)) const = 0; + virtual size_t maxChunkSize() const = 0; + virtual size_t minSize() const = 0; + // Reset the dictionary to the initial conditions for a single + // block. + virtual void reset(HeapWord* addr, size_t size) = 0; + virtual void reset() = 0; + + virtual void dictCensusUpdate(size_t size, bool split, bool birth) = 0; + virtual bool coalDictOverPopulated(size_t size) = 0; + virtual void beginSweepDictCensus(double coalSurplusPercent, + float inter_sweep_current, float inter_sweep_estimate, + float intra__sweep_current) = 0; + virtual void endSweepDictCensus(double splitSurplusPercent) = 0; + virtual Chunk* findLargestDict() const = 0; + // verify that the given chunk is in the dictionary. + virtual bool verifyChunkInFreeLists(Chunk* tc) const = 0; + + // Sigma_{all_free_blocks} (block_size^2) + virtual double sum_of_squared_block_sizes() const = 0; + + virtual Chunk* find_chunk_ends_at(HeapWord* target) const = 0; + virtual void inc_totalSize(size_t v) = 0; + virtual void dec_totalSize(size_t v) = 0; + + NOT_PRODUCT ( + virtual size_t sumDictReturnedBytes() = 0; + virtual void initializeDictReturnedBytes() = 0; + virtual size_t totalCount() = 0; + ) + + virtual void reportStatistics() const { + gclog_or_tty->print("No statistics available"); + } + + virtual void printDictCensus() const = 0; + virtual void print_free_lists(outputStream* st) const = 0; + + virtual void verify() const = 0; + + Mutex* par_lock() const PRODUCT_RETURN0; + void set_par_lock(Mutex* lock) PRODUCT_RETURN; + void verify_par_locked() const PRODUCT_RETURN; +}; + +#endif // SHARE_VM_MEMORY_FREEBLOCKDICTIONARY_HPP diff -r 3c91f2c9fd21 -r 9f059abe8cf2 src/share/vm/memory/freeList.cpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/share/vm/memory/freeList.cpp Thu Mar 29 19:46:24 2012 -0700 @@ -0,0 +1,370 @@ +/* + * Copyright (c) 2001, 2010, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * 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 "memory/freeBlockDictionary.hpp" +#include "memory/freeList.hpp" +#include "memory/sharedHeap.hpp" +#include "runtime/globals.hpp" +#include "runtime/mutex.hpp" +#include "runtime/vmThread.hpp" + +#ifndef SERIALGC +#include "gc_implementation/concurrentMarkSweep/freeChunk.hpp" +#endif // SERIALGC + +// Free list. A FreeList is used to access a linked list of chunks +// of space in the heap. The head and tail are maintained so that +// items can be (as in the current implementation) added at the +// at the tail of the list and removed from the head of the list to +// maintain a FIFO queue. + +template +FreeList::FreeList() : + _head(NULL), _tail(NULL) +#ifdef ASSERT + , _protecting_lock(NULL) +#endif +{ + _size = 0; + _count = 0; + _hint = 0; + init_statistics(); +} + +template +FreeList::FreeList(Chunk* fc) : + _head(fc), _tail(fc) +#ifdef ASSERT + , _protecting_lock(NULL) +#endif +{ + _size = fc->size(); + _count = 1; + _hint = 0; + init_statistics(); +#ifndef PRODUCT + _allocation_stats.set_returnedBytes(size() * HeapWordSize); +#endif +} + +template +void FreeList::reset(size_t hint) { + set_count(0); + set_head(NULL); + set_tail(NULL); + set_hint(hint); +} + +template +void FreeList::init_statistics(bool split_birth) { + _allocation_stats.initialize(split_birth); +} + +template +Chunk* FreeList::getChunkAtHead() { + assert_proper_lock_protection(); + assert(head() == NULL || head()->prev() == NULL, "list invariant"); + assert(tail() == NULL || tail()->next() == NULL, "list invariant"); + Chunk* fc = head(); + if (fc != NULL) { + Chunk* nextFC = fc->next(); + if (nextFC != NULL) { + // The chunk fc being removed has a "next". Set the "next" to the + // "prev" of fc. + nextFC->linkPrev(NULL); + } else { // removed tail of list + link_tail(NULL); + } + link_head(nextFC); + decrement_count(); + } + assert(head() == NULL || head()->prev() == NULL, "list invariant"); + assert(tail() == NULL || tail()->next() == NULL, "list invariant"); + return fc; +} + + +template +void FreeList::getFirstNChunksFromList(size_t n, FreeList* fl) { + assert_proper_lock_protection(); + assert(fl->count() == 0, "Precondition"); + if (count() > 0) { + int k = 1; + fl->set_head(head()); n--; + Chunk* tl = head(); + while (tl->next() != NULL && n > 0) { + tl = tl->next(); n--; k++; + } + assert(tl != NULL, "Loop Inv."); + + // First, fix up the list we took from. + Chunk* new_head = tl->next(); + set_head(new_head); + set_count(count() - k); + if (new_head == NULL) { + set_tail(NULL); + } else { + new_head->linkPrev(NULL); + } + // Now we can fix up the tail. + tl->linkNext(NULL); + // And return the result. + fl->set_tail(tl); + fl->set_count(k); + } +} + +// Remove this chunk from the list +template +void FreeList::removeChunk(Chunk*fc) { + assert_proper_lock_protection(); + assert(head() != NULL, "Remove from empty list"); + assert(fc != NULL, "Remove a NULL chunk"); + assert(size() == fc->size(), "Wrong list"); + assert(head() == NULL || head()->prev() == NULL, "list invariant"); + assert(tail() == NULL || tail()->next() == NULL, "list invariant"); + + Chunk* prevFC = fc->prev(); + Chunk* nextFC = fc->next(); + if (nextFC != NULL) { + // The chunk fc being removed has a "next". Set the "next" to the + // "prev" of fc. + nextFC->linkPrev(prevFC); + } else { // removed tail of list + link_tail(prevFC); + } + if (prevFC == NULL) { // removed head of list + link_head(nextFC); + assert(nextFC == NULL || nextFC->prev() == NULL, + "Prev of head should be NULL"); + } else { + prevFC->linkNext(nextFC); + assert(tail() != prevFC || prevFC->next() == NULL, + "Next of tail should be NULL"); + } + decrement_count(); + assert(((head() == NULL) + (tail() == NULL) + (count() == 0)) % 3 == 0, + "H/T/C Inconsistency"); + // clear next and prev fields of fc, debug only + NOT_PRODUCT( + fc->linkPrev(NULL); + fc->linkNext(NULL); + ) + assert(fc->isFree(), "Should still be a free chunk"); + assert(head() == NULL || head()->prev() == NULL, "list invariant"); + assert(tail() == NULL || tail()->next() == NULL, "list invariant"); + assert(head() == NULL || head()->size() == size(), "wrong item on list"); + assert(tail() == NULL || tail()->size() == size(), "wrong item on list"); +} + +// Add this chunk at the head of the list. +template +void FreeList::returnChunkAtHead(Chunk* chunk, bool record_return) { + assert_proper_lock_protection(); + assert(chunk != NULL, "insert a NULL chunk"); + assert(size() == chunk->size(), "Wrong size"); + assert(head() == NULL || head()->prev() == NULL, "list invariant"); + assert(tail() == NULL || tail()->next() == NULL, "list invariant"); + + Chunk* oldHead = head(); + assert(chunk != oldHead, "double insertion"); + chunk->linkAfter(oldHead); + link_head(chunk); + if (oldHead == NULL) { // only chunk in list + assert(tail() == NULL, "inconsistent FreeList"); + link_tail(chunk); + } + increment_count(); // of # of chunks in list + DEBUG_ONLY( + if (record_return) { + increment_returnedBytes_by(size()*HeapWordSize); + } + ) + assert(head() == NULL || head()->prev() == NULL, "list invariant"); + assert(tail() == NULL || tail()->next() == NULL, "list invariant"); + assert(head() == NULL || head()->size() == size(), "wrong item on list"); + assert(tail() == NULL || tail()->size() == size(), "wrong item on list"); +} + +template +void FreeList::returnChunkAtHead(Chunk* chunk) { + assert_proper_lock_protection(); + returnChunkAtHead(chunk, true); +} + +// Add this chunk at the tail of the list. +template +void FreeList::returnChunkAtTail(Chunk* chunk, bool record_return) { + assert_proper_lock_protection(); + assert(head() == NULL || head()->prev() == NULL, "list invariant"); + assert(tail() == NULL || tail()->next() == NULL, "list invariant"); + assert(chunk != NULL, "insert a NULL chunk"); + assert(size() == chunk->size(), "wrong size"); + + Chunk* oldTail = tail(); + assert(chunk != oldTail, "double insertion"); + if (oldTail != NULL) { + oldTail->linkAfter(chunk); + } else { // only chunk in list + assert(head() == NULL, "inconsistent FreeList"); + link_head(chunk); + } + link_tail(chunk); + increment_count(); // of # of chunks in list + DEBUG_ONLY( + if (record_return) { + increment_returnedBytes_by(size()*HeapWordSize); + } + ) + assert(head() == NULL || head()->prev() == NULL, "list invariant"); + assert(tail() == NULL || tail()->next() == NULL, "list invariant"); + assert(head() == NULL || head()->size() == size(), "wrong item on list"); + assert(tail() == NULL || tail()->size() == size(), "wrong item on list"); +} + +template +void FreeList::returnChunkAtTail(Chunk* chunk) { + returnChunkAtTail(chunk, true); +} + +template +void FreeList::prepend(FreeList* fl) { + assert_proper_lock_protection(); + if (fl->count() > 0) { + if (count() == 0) { + set_head(fl->head()); + set_tail(fl->tail()); + set_count(fl->count()); + } else { + // Both are non-empty. + Chunk* fl_tail = fl->tail(); + Chunk* this_head = head(); + assert(fl_tail->next() == NULL, "Well-formedness of fl"); + fl_tail->linkNext(this_head); + this_head->linkPrev(fl_tail); + set_head(fl->head()); + set_count(count() + fl->count()); + } + fl->set_head(NULL); + fl->set_tail(NULL); + fl->set_count(0); + } +} + +// verifyChunkInFreeLists() is used to verify that an item is in this free list. +// It is used as a debugging aid. +template +bool FreeList::verifyChunkInFreeLists(Chunk* fc) const { + // This is an internal consistency check, not part of the check that the + // chunk is in the free lists. + guarantee(fc->size() == size(), "Wrong list is being searched"); + Chunk* curFC = head(); + while (curFC) { + // This is an internal consistency check. + guarantee(size() == curFC->size(), "Chunk is in wrong list."); + if (fc == curFC) { + return true; + } + curFC = curFC->next(); + } + return false; +} + +#ifndef PRODUCT +template +void FreeList::verify_stats() const { + // The +1 of the LH comparand is to allow some "looseness" in + // checking: we usually call this interface when adding a block + // and we'll subsequently update the stats; we cannot update the + // stats beforehand because in the case of the large-block BT + // dictionary for example, this might be the first block and + // in that case there would be no place that we could record + // the stats (which are kept in the block itself). + assert((_allocation_stats.prevSweep() + _allocation_stats.splitBirths() + + _allocation_stats.coalBirths() + 1) // Total Production Stock + 1 + >= (_allocation_stats.splitDeaths() + _allocation_stats.coalDeaths() + + (ssize_t)count()), // Total Current Stock + depletion + err_msg("FreeList " PTR_FORMAT " of size " SIZE_FORMAT + " violates Conservation Principle: " + "prevSweep(" SIZE_FORMAT ")" + " + splitBirths(" SIZE_FORMAT ")" + " + coalBirths(" SIZE_FORMAT ") + 1 >= " + " splitDeaths(" SIZE_FORMAT ")" + " coalDeaths(" SIZE_FORMAT ")" + " + count(" SSIZE_FORMAT ")", + this, _size, _allocation_stats.prevSweep(), _allocation_stats.splitBirths(), + _allocation_stats.splitBirths(), _allocation_stats.splitDeaths(), + _allocation_stats.coalDeaths(), count())); +} + +template +void FreeList::assert_proper_lock_protection_work() const { + assert(_protecting_lock != NULL, "Don't call this directly"); + assert(ParallelGCThreads > 0, "Don't call this directly"); + Thread* thr = Thread::current(); + if (thr->is_VM_thread() || thr->is_ConcurrentGC_thread()) { + // assert that we are holding the freelist lock + } else if (thr->is_GC_task_thread()) { + assert(_protecting_lock->owned_by_self(), "FreeList RACE DETECTED"); + } else if (thr->is_Java_thread()) { + assert(!SafepointSynchronize::is_at_safepoint(), "Should not be executing"); + } else { + ShouldNotReachHere(); // unaccounted thread type? + } +} +#endif + +// Print the "label line" for free list stats. +template +void FreeList::print_labels_on(outputStream* st, const char* c) { + st->print("%16s\t", c); + st->print("%14s\t" "%14s\t" "%14s\t" "%14s\t" "%14s\t" + "%14s\t" "%14s\t" "%14s\t" "%14s\t" "%14s\t" "\n", + "bfrsurp", "surplus", "desired", "prvSwep", "bfrSwep", + "count", "cBirths", "cDeaths", "sBirths", "sDeaths"); +} + +// Print the AllocationStats for the given free list. If the second argument +// to the call is a non-null string, it is printed in the first column; +// otherwise, if the argument is null (the default), then the size of the +// (free list) block is printed in the first column. +template +void FreeList::print_on(outputStream* st, const char* c) const { + if (c != NULL) { + st->print("%16s", c); + } else { + st->print(SIZE_FORMAT_W(16), size()); + } + st->print("\t" + SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" + SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\n", + bfrSurp(), surplus(), desired(), prevSweep(), beforeSweep(), + count(), coalBirths(), coalDeaths(), splitBirths(), splitDeaths()); +} + +#ifndef SERIALGC +// Needs to be after the definitions have been seen. +template class FreeList; +#endif // SERIALGC diff -r 3c91f2c9fd21 -r 9f059abe8cf2 src/share/vm/memory/freeList.hpp --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/share/vm/memory/freeList.hpp Thu Mar 29 19:46:24 2012 -0700 @@ -0,0 +1,329 @@ +/* + * Copyright (c) 2001, 2010, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * 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. + * + */ + +#ifndef SHARE_VM_MEMORY_FREELIST_HPP +#define SHARE_VM_MEMORY_FREELIST_HPP + +#include "gc_implementation/shared/allocationStats.hpp" + +class CompactibleFreeListSpace; + +// A class for maintaining a free list of Chunk's. The FreeList +// maintains a the structure of the list (head, tail, etc.) plus +// statistics for allocations from the list. The links between items +// are not part of FreeList. The statistics are +// used to make decisions about coalescing Chunk's when they +// are swept during collection. +// +// See the corresponding .cpp file for a description of the specifics +// for that implementation. + +class Mutex; +template class TreeList; +template class PrintTreeCensusClosure; + +template +class FreeList VALUE_OBJ_CLASS_SPEC { + friend class CompactibleFreeListSpace; + friend class VMStructs; + friend class PrintTreeCensusClosure; + + private: + Chunk* _head; // Head of list of free chunks + Chunk* _tail; // Tail of list of free chunks + size_t _size; // Size in Heap words of each chunk + ssize_t _count; // Number of entries in list + size_t _hint; // next larger size list with a positive surplus + + AllocationStats _allocation_stats; // allocation-related statistics + +#ifdef ASSERT + Mutex* _protecting_lock; +#endif + + // Asserts false if the protecting lock (if any) is not held. + void assert_proper_lock_protection_work() const PRODUCT_RETURN; + void assert_proper_lock_protection() const { +#ifdef ASSERT + if (_protecting_lock != NULL) + assert_proper_lock_protection_work(); +#endif + } + + // Initialize the allocation statistics. + protected: + void init_statistics(bool split_birth = false); + void set_count(ssize_t v) { _count = v;} + void increment_count() { + _count++; + } + + void decrement_count() { + _count--; + assert(_count >= 0, "Count should not be negative"); + } + + public: + // Constructor + // Construct a list without any entries. + FreeList(); + // Construct a list with "fc" as the first (and lone) entry in the list. + FreeList(Chunk* fc); + + // Reset the head, tail, hint, and count of a free list. + void reset(size_t hint); + + // Declare the current free list to be protected by the given lock. +#ifdef ASSERT + void set_protecting_lock(Mutex* protecting_lock) { + _protecting_lock = protecting_lock; + } +#endif + + // Accessors. + Chunk* head() const { + assert_proper_lock_protection(); + return _head; + } + void set_head(Chunk* v) { + assert_proper_lock_protection(); + _head = v; + assert(!_head || _head->size() == _size, "bad chunk size"); + } + // Set the head of the list and set the prev field of non-null + // values to NULL. + void link_head(Chunk* v) { + assert_proper_lock_protection(); + set_head(v); + // If this method is not used (just set the head instead), + // this check can be avoided. + if (v != NULL) { + v->linkPrev(NULL); + } + } + + Chunk* tail() const { + assert_proper_lock_protection(); + return _tail; + } + void set_tail(Chunk* v) { + assert_proper_lock_protection(); + _tail = v; + assert(!_tail || _tail->size() == _size, "bad chunk size"); + } + // Set the tail of the list and set the next field of non-null + // values to NULL. + void link_tail(Chunk* v) { + assert_proper_lock_protection(); + set_tail(v); + if (v != NULL) { + v->clearNext(); + } + } + + // No locking checks in read-accessors: lock-free reads (only) are benign. + // Readers are expected to have the lock if they are doing work that + // requires atomicity guarantees in sections of code. + size_t size() const { + return _size; + } + void set_size(size_t v) { + assert_proper_lock_protection(); + _size = v; + } + ssize_t count() const { + return _count; + } + size_t hint() const { + return _hint; + } + void set_hint(size_t v) { + assert_proper_lock_protection(); + assert(v == 0 || _size < v, "Bad hint"); _hint = v; + } + + // Accessors for statistics + AllocationStats* allocation_stats() { + assert_proper_lock_protection(); + return &_allocation_stats; + } + + ssize_t desired() const { + return _allocation_stats.desired(); + } + void set_desired(ssize_t v) { + assert_proper_lock_protection(); + _allocation_stats.set_desired(v); + } + void compute_desired(float inter_sweep_current, + float inter_sweep_estimate, + float intra_sweep_estimate) { + assert_proper_lock_protection(); + _allocation_stats.compute_desired(_count, + inter_sweep_current, + inter_sweep_estimate, + intra_sweep_estimate); + } + ssize_t coalDesired() const { + return _allocation_stats.coalDesired(); + } + void set_coalDesired(ssize_t v) { + assert_proper_lock_protection(); + _allocation_stats.set_coalDesired(v); + } + + ssize_t surplus() const { + return _allocation_stats.surplus(); + } + void set_surplus(ssize_t v) { + assert_proper_lock_protection(); + _allocation_stats.set_surplus(v); + } + void increment_surplus() { + assert_proper_lock_protection(); + _allocation_stats.increment_surplus(); + } + void decrement_surplus() { + assert_proper_lock_protection(); + _allocation_stats.decrement_surplus(); + } + + ssize_t bfrSurp() const { + return _allocation_stats.bfrSurp(); + } + void set_bfrSurp(ssize_t v) { + assert_proper_lock_protection(); + _allocation_stats.set_bfrSurp(v); + } + ssize_t prevSweep() const { + return _allocation_stats.prevSweep(); + } + void set_prevSweep(ssize_t v) { + assert_proper_lock_protection(); + _allocation_stats.set_prevSweep(v); + } + ssize_t beforeSweep() const { + return _allocation_stats.beforeSweep(); + } + void set_beforeSweep(ssize_t v) { + assert_proper_lock_protection(); + _allocation_stats.set_beforeSweep(v); + } + + ssize_t coalBirths() const { + return _allocation_stats.coalBirths(); + } + void set_coalBirths(ssize_t v) { + assert_proper_lock_protection(); + _allocation_stats.set_coalBirths(v); + } + void increment_coalBirths() { + assert_proper_lock_protection(); + _allocation_stats.increment_coalBirths(); + } + + ssize_t coalDeaths() const { + return _allocation_stats.coalDeaths(); + } + void set_coalDeaths(ssize_t v) { + assert_proper_lock_protection(); + _allocation_stats.set_coalDeaths(v); + } + void increment_coalDeaths() { + assert_proper_lock_protection(); + _allocation_stats.increment_coalDeaths(); + } + + ssize_t splitBirths() const { + return _allocation_stats.splitBirths(); + } + void set_splitBirths(ssize_t v) { + assert_proper_lock_protection(); + _allocation_stats.set_splitBirths(v); + } + void increment_splitBirths() { + assert_proper_lock_protection(); + _allocation_stats.increment_splitBirths(); + } + + ssize_t splitDeaths() const { + return _allocation_stats.splitDeaths(); + } + void set_splitDeaths(ssize_t v) { + assert_proper_lock_protection(); + _allocation_stats.set_splitDeaths(v); + } + void increment_splitDeaths() { + assert_proper_lock_protection(); + _allocation_stats.increment_splitDeaths(); + } + + NOT_PRODUCT( + // For debugging. The "_returnedBytes" in all the lists are summed + // and compared with the total number of bytes swept during a + // collection. + size_t returnedBytes() const { return _allocation_stats.returnedBytes(); } + void set_returnedBytes(size_t v) { _allocation_stats.set_returnedBytes(v); } + void increment_returnedBytes_by(size_t v) { + _allocation_stats.set_returnedBytes(_allocation_stats.returnedBytes() + v); + } + ) + + // Unlink head of list and return it. Returns NULL if + // the list is empty. + Chunk* getChunkAtHead(); + + // Remove the first "n" or "count", whichever is smaller, chunks from the + // list, setting "fl", which is required to be empty, to point to them. + void getFirstNChunksFromList(size_t n, FreeList* fl); + + // Unlink this chunk from it's free list + void removeChunk(Chunk* fc); + + // Add this chunk to this free list. + void returnChunkAtHead(Chunk* fc); + void returnChunkAtTail(Chunk* fc); + + // Similar to returnChunk* but also records some diagnostic + // information. + void returnChunkAtHead(Chunk* fc, bool record_return); + void returnChunkAtTail(Chunk* fc, bool record_return); + + // Prepend "fl" (whose size is required to be the same as that of "this") + // to the front of "this" list. + void prepend(FreeList* fl); + + // Verify that the chunk is in the list. + // found. Return NULL if "fc" is not found. + bool verifyChunkInFreeLists(Chunk* fc) const; + + // Stats verification + void verify_stats() const PRODUCT_RETURN; + + // Printing support + static void print_labels_on(outputStream* st, const char* c); + void print_on(outputStream* st, const char* c = NULL) const; +}; + +#endif // SHARE_VM_MEMORY_FREELIST_HPP diff -r 3c91f2c9fd21 -r 9f059abe8cf2 src/share/vm/memory/generationSpec.cpp --- a/src/share/vm/memory/generationSpec.cpp Fri Apr 20 17:13:36 2012 -0700 +++ b/src/share/vm/memory/generationSpec.cpp Thu Mar 29 19:46:24 2012 -0700 @@ -68,7 +68,7 @@ ConcurrentMarkSweepGeneration* g = NULL; g = new ConcurrentMarkSweepGeneration(rs, init_size(), level, ctrs, UseCMSAdaptiveFreeLists, - (FreeBlockDictionary::DictionaryChoice)CMSDictionaryChoice); + (FreeBlockDictionary::DictionaryChoice)CMSDictionaryChoice); g->initialize_performance_counters(); @@ -88,7 +88,7 @@ ASConcurrentMarkSweepGeneration* g = NULL; g = new ASConcurrentMarkSweepGeneration(rs, init_size(), level, ctrs, UseCMSAdaptiveFreeLists, - (FreeBlockDictionary::DictionaryChoice)CMSDictionaryChoice); + (FreeBlockDictionary::DictionaryChoice)CMSDictionaryChoice); g->initialize_performance_counters(); @@ -175,7 +175,7 @@ } // XXXPERM return new CMSPermGen(perm_rs, init_size, ctrs, - (FreeBlockDictionary::DictionaryChoice)CMSDictionaryChoice); + (FreeBlockDictionary::DictionaryChoice)CMSDictionaryChoice); } #endif // SERIALGC default: diff -r 3c91f2c9fd21 -r 9f059abe8cf2 src/share/vm/precompiled/precompiled.hpp --- a/src/share/vm/precompiled/precompiled.hpp Fri Apr 20 17:13:36 2012 -0700 +++ b/src/share/vm/precompiled/precompiled.hpp Thu Mar 29 19:46:24 2012 -0700 @@ -293,13 +293,10 @@ # include "c1/c1_globals.hpp" #endif // COMPILER1 #ifndef SERIALGC -# include "gc_implementation/concurrentMarkSweep/binaryTreeDictionary.hpp" # include "gc_implementation/concurrentMarkSweep/cmsOopClosures.hpp" # include "gc_implementation/concurrentMarkSweep/compactibleFreeListSpace.hpp" # include "gc_implementation/concurrentMarkSweep/concurrentMarkSweepGeneration.hpp" -# include "gc_implementation/concurrentMarkSweep/freeBlockDictionary.hpp" # include "gc_implementation/concurrentMarkSweep/freeChunk.hpp" -# include "gc_implementation/concurrentMarkSweep/freeList.hpp" # include "gc_implementation/concurrentMarkSweep/promotionInfo.hpp" # include "gc_implementation/g1/dirtyCardQueue.hpp" # include "gc_implementation/g1/g1BlockOffsetTable.hpp" diff -r 3c91f2c9fd21 -r 9f059abe8cf2 src/share/vm/runtime/vmStructs.cpp --- a/src/share/vm/runtime/vmStructs.cpp Fri Apr 20 17:13:36 2012 -0700 +++ b/src/share/vm/runtime/vmStructs.cpp Thu Mar 29 19:46:24 2012 -0700 @@ -44,7 +44,6 @@ #include "code/vmreg.hpp" #include "compiler/oopMap.hpp" #include "compiler/compileBroker.hpp" -#include "gc_implementation/concurrentMarkSweep/freeBlockDictionary.hpp" #include "gc_implementation/shared/immutableSpace.hpp" #include "gc_implementation/shared/markSweep.hpp" #include "gc_implementation/shared/mutableSpace.hpp" @@ -55,6 +54,7 @@ #include "memory/cardTableRS.hpp" #include "memory/compactPermGen.hpp" #include "memory/defNewGeneration.hpp" +#include "memory/freeBlockDictionary.hpp" #include "memory/genCollectedHeap.hpp" #include "memory/generation.hpp" #include "memory/generationSpec.hpp"