hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/binaryTreeDictionary.hpp
--- a/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/binaryTreeDictionary.hpp Wed May 09 13:11:47 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