duke@435: /* jmasa@3730: * Copyright (c) 2001, 2012, Oracle and/or its affiliates. All rights reserved. duke@435: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. duke@435: * duke@435: * This code is free software; you can redistribute it and/or modify it duke@435: * under the terms of the GNU General Public License version 2 only, as duke@435: * published by the Free Software Foundation. duke@435: * duke@435: * This code is distributed in the hope that it will be useful, but WITHOUT duke@435: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or duke@435: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License duke@435: * version 2 for more details (a copy is included in the LICENSE file that duke@435: * accompanied this code). duke@435: * duke@435: * You should have received a copy of the GNU General Public License version duke@435: * 2 along with this work; if not, write to the Free Software Foundation, duke@435: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. duke@435: * trims@1907: * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA trims@1907: * or visit www.oracle.com if you need additional information or have any trims@1907: * questions. duke@435: * duke@435: */ duke@435: jmasa@3730: #ifndef SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP jmasa@3730: #define SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP stefank@2314: jmasa@3730: #include "memory/freeBlockDictionary.hpp" jmasa@3730: #include "memory/freeList.hpp" stefank@2314: duke@435: /* duke@435: * A binary tree based search structure for free blocks. jmasa@3730: * This is currently used in the Concurrent Mark&Sweep implementation, but jmasa@3730: * will be used for free block management for metadata. duke@435: */ duke@435: duke@435: // A TreeList is a FreeList which can be used to maintain a duke@435: // binary tree of free lists. duke@435: jmasa@3730: template class TreeChunk; jmasa@3730: template class BinaryTreeDictionary; jmasa@3730: template class AscendTreeCensusClosure; jmasa@3730: template class DescendTreeCensusClosure; jmasa@3730: template class DescendTreeSearchClosure; duke@435: jmasa@3730: template jmasa@3730: class TreeList: public FreeList { jmasa@3730: friend class TreeChunk; jmasa@3730: friend class BinaryTreeDictionary; jmasa@3730: friend class AscendTreeCensusClosure; jmasa@3730: friend class DescendTreeCensusClosure; jmasa@3730: friend class DescendTreeSearchClosure; jmasa@3730: jmasa@3730: TreeList* _parent; jmasa@3730: TreeList* _left; jmasa@3730: TreeList* _right; duke@435: duke@435: protected: jmasa@3730: TreeList* parent() const { return _parent; } jmasa@3730: TreeList* left() const { return _left; } jmasa@3730: TreeList* right() const { return _right; } jmasa@3730: jmasa@3730: // Wrapper on call to base class, to get the template to compile. jmasa@3730: Chunk* head() const { return FreeList::head(); } jmasa@3730: Chunk* tail() const { return FreeList::tail(); } jmasa@3730: void set_head(Chunk* head) { FreeList::set_head(head); } jmasa@3730: void set_tail(Chunk* tail) { FreeList::set_tail(tail); } jmasa@3730: jmasa@3730: size_t size() const { return FreeList::size(); } duke@435: duke@435: // Accessors for links in tree. duke@435: jmasa@3730: void setLeft(TreeList* tl) { duke@435: _left = tl; duke@435: if (tl != NULL) duke@435: tl->setParent(this); duke@435: } jmasa@3730: void setRight(TreeList* tl) { duke@435: _right = tl; duke@435: if (tl != NULL) duke@435: tl->setParent(this); duke@435: } jmasa@3730: void setParent(TreeList* tl) { _parent = tl; } duke@435: duke@435: void clearLeft() { _left = NULL; } duke@435: void clearRight() { _right = NULL; } duke@435: void clearParent() { _parent = NULL; } duke@435: void initialize() { clearLeft(); clearRight(), clearParent(); } duke@435: duke@435: // For constructing a TreeList from a Tree chunk or duke@435: // address and size. jmasa@3730: static TreeList* as_TreeList(TreeChunk* tc); jmasa@3730: static TreeList* as_TreeList(HeapWord* addr, size_t size); duke@435: duke@435: // Returns the head of the free list as a pointer to a TreeChunk. jmasa@3730: TreeChunk* head_as_TreeChunk(); duke@435: duke@435: // Returns the first available chunk in the free list as a pointer duke@435: // to a TreeChunk. jmasa@3730: TreeChunk* first_available(); duke@435: ysr@1580: // Returns the block with the largest heap address amongst ysr@1580: // those in the list for this size; potentially slow and expensive, ysr@1580: // use with caution! jmasa@3730: TreeChunk* largest_address(); ysr@1580: duke@435: // removeChunkReplaceIfNeeded() removes the given "tc" from the TreeList. duke@435: // If "tc" is the first chunk in the list, it is also the duke@435: // TreeList that is the node in the tree. removeChunkReplaceIfNeeded() duke@435: // returns the possibly replaced TreeList* for the node in duke@435: // the tree. It also updates the parent of the original duke@435: // node to point to the new node. jmasa@3730: TreeList* removeChunkReplaceIfNeeded(TreeChunk* tc); duke@435: // See FreeList. jmasa@3730: void returnChunkAtHead(TreeChunk* tc); jmasa@3730: void returnChunkAtTail(TreeChunk* tc); duke@435: }; duke@435: jmasa@3730: // A TreeChunk is a subclass of a Chunk that additionally duke@435: // maintains a pointer to the free list on which it is currently duke@435: // linked. duke@435: // A TreeChunk is also used as a node in the binary tree. This duke@435: // allows the binary tree to be maintained without any additional duke@435: // storage (the free chunks are used). In a binary tree the first duke@435: // chunk in the free list is also the tree node. Note that the duke@435: // TreeChunk has an embedded TreeList for this purpose. Because duke@435: // the first chunk in the list is distinguished in this fashion duke@435: // (also is the node in the tree), it is the last chunk to be found duke@435: // on the free list for a node in the tree and is only removed if duke@435: // it is the last chunk on the free list. duke@435: jmasa@3730: template jmasa@3730: class TreeChunk : public Chunk { jmasa@3730: friend class TreeList; jmasa@3730: TreeList* _list; jmasa@3730: TreeList _embedded_list; // if non-null, this chunk is on _list duke@435: protected: jmasa@3730: TreeList* embedded_list() const { return (TreeList*) &_embedded_list; } jmasa@3730: void set_embedded_list(TreeList* v) { _embedded_list = *v; } duke@435: public: jmasa@3730: TreeList* list() { return _list; } jmasa@3730: void set_list(TreeList* v) { _list = v; } jmasa@3730: static TreeChunk* as_TreeChunk(Chunk* fc); duke@435: // Initialize fields in a TreeChunk that should be duke@435: // initialized when the TreeChunk is being added to duke@435: // a free list in the tree. duke@435: void initialize() { embedded_list()->initialize(); } duke@435: jmasa@3730: Chunk* next() const { return Chunk::next(); } jmasa@3730: Chunk* prev() const { return Chunk::prev(); } jmasa@3730: size_t size() const volatile { return Chunk::size(); } jmasa@3730: duke@435: // debugging duke@435: void verifyTreeChunkList() const; duke@435: }; duke@435: duke@435: jmasa@3730: template jmasa@3730: class BinaryTreeDictionary: public FreeBlockDictionary { dcubed@587: friend class VMStructs; duke@435: bool _splay; duke@435: size_t _totalSize; duke@435: size_t _totalFreeBlocks; jmasa@3730: TreeList* _root; jmasa@3730: bool _adaptive_freelists; duke@435: duke@435: // private accessors duke@435: bool splay() const { return _splay; } duke@435: void set_splay(bool v) { _splay = v; } duke@435: void set_totalSize(size_t v) { _totalSize = v; } duke@435: virtual void inc_totalSize(size_t v); duke@435: virtual void dec_totalSize(size_t v); duke@435: size_t totalFreeBlocks() const { return _totalFreeBlocks; } duke@435: void set_totalFreeBlocks(size_t v) { _totalFreeBlocks = v; } jmasa@3730: TreeList* root() const { return _root; } jmasa@3730: void set_root(TreeList* v) { _root = v; } jmasa@3730: bool adaptive_freelists() { return _adaptive_freelists; } jmasa@3730: jmasa@3730: // This field is added and can be set to point to the jmasa@3730: // the Mutex used to synchronize access to the jmasa@3730: // dictionary so that assertion checking can be done. jmasa@3730: // For example it is set to point to _parDictionaryAllocLock. jmasa@3730: NOT_PRODUCT(Mutex* _lock;) duke@435: duke@435: // Remove a chunk of size "size" or larger from the tree and duke@435: // return it. If the chunk duke@435: // is the last chunk of that size, remove the node for that size duke@435: // from the tree. jmasa@3730: TreeChunk* getChunkFromTree(size_t size, enum FreeBlockDictionary::Dither dither, bool splay); duke@435: // Return a list of the specified size or NULL from the tree. duke@435: // The list is not removed from the tree. jmasa@3730: TreeList* findList (size_t size) const; duke@435: // Remove this chunk from the tree. If the removal results duke@435: // in an empty list in the tree, remove the empty list. jmasa@3730: TreeChunk* removeChunkFromTree(TreeChunk* tc); duke@435: // Remove the node in the trees starting at tl that has the duke@435: // minimum value and return it. Repair the tree as needed. jmasa@3730: TreeList* removeTreeMinimum(TreeList* tl); jmasa@3730: void semiSplayStep(TreeList* tl); duke@435: // Add this free chunk to the tree. jmasa@3730: void insertChunkInTree(Chunk* freeChunk); duke@435: public: jmasa@3730: jmasa@3730: static const size_t min_tree_chunk_size = sizeof(TreeChunk)/HeapWordSize; jmasa@3730: duke@435: void verifyTree() const; duke@435: // verify that the given chunk is in the tree. jmasa@3730: bool verifyChunkInFreeLists(Chunk* tc) const; duke@435: private: jmasa@3730: void verifyTreeHelper(TreeList* tl) const; jmasa@3730: static size_t verifyPrevFreePtrs(TreeList* tl); duke@435: duke@435: // Returns the total number of chunks in the list. jmasa@3730: size_t totalListLength(TreeList* tl) const; duke@435: // Returns the total number of words in the chunks in the tree duke@435: // starting at "tl". jmasa@3730: size_t totalSizeInTree(TreeList* tl) const; duke@435: // Returns the sum of the square of the size of each block duke@435: // in the tree starting at "tl". jmasa@3730: double sum_of_squared_block_sizes(TreeList* const tl) const; duke@435: // Returns the total number of free blocks in the tree starting duke@435: // at "tl". jmasa@3730: size_t totalFreeBlocksInTree(TreeList* tl) const; duke@435: size_t numFreeBlocks() const; duke@435: size_t treeHeight() const; jmasa@3730: size_t treeHeightHelper(TreeList* tl) const; jmasa@3730: size_t totalNodesInTree(TreeList* tl) const; jmasa@3730: size_t totalNodesHelper(TreeList* tl) const; duke@435: duke@435: public: duke@435: // Constructor jmasa@3730: BinaryTreeDictionary(bool adaptive_freelists, bool splay = false); jmasa@3730: BinaryTreeDictionary(MemRegion mr, bool adaptive_freelists, bool splay = false); jmasa@3730: jmasa@3730: // Public accessors jmasa@3730: size_t totalSize() const { return _totalSize; } duke@435: duke@435: // Reset the dictionary to the initial conditions with duke@435: // a single free chunk. duke@435: void reset(MemRegion mr); duke@435: void reset(HeapWord* addr, size_t size); duke@435: // Reset the dictionary to be empty. duke@435: void reset(); duke@435: duke@435: // Return a chunk of size "size" or greater from duke@435: // the tree. duke@435: // want a better dynamic splay strategy for the future. jmasa@3730: Chunk* getChunk(size_t size, enum FreeBlockDictionary::Dither dither) { jmasa@3730: FreeBlockDictionary::verify_par_locked(); jmasa@3730: Chunk* res = getChunkFromTree(size, dither, splay()); duke@435: assert(res == NULL || res->isFree(), duke@435: "Should be returning a free chunk"); duke@435: return res; duke@435: } duke@435: jmasa@3730: void returnChunk(Chunk* chunk) { jmasa@3730: FreeBlockDictionary::verify_par_locked(); duke@435: insertChunkInTree(chunk); duke@435: } duke@435: jmasa@3730: void removeChunk(Chunk* chunk) { jmasa@3730: FreeBlockDictionary::verify_par_locked(); jmasa@3730: removeChunkFromTree((TreeChunk*)chunk); duke@435: assert(chunk->isFree(), "Should still be a free chunk"); duke@435: } duke@435: duke@435: size_t maxChunkSize() const; duke@435: size_t totalChunkSize(debug_only(const Mutex* lock)) const { duke@435: debug_only( duke@435: if (lock != NULL && lock->owned_by_self()) { duke@435: assert(totalSizeInTree(root()) == totalSize(), duke@435: "_totalSize inconsistency"); duke@435: } duke@435: ) duke@435: return totalSize(); duke@435: } duke@435: duke@435: size_t minSize() const { jmasa@3730: return min_tree_chunk_size; duke@435: } duke@435: duke@435: double sum_of_squared_block_sizes() const { duke@435: return sum_of_squared_block_sizes(root()); duke@435: } duke@435: jmasa@3730: Chunk* find_chunk_ends_at(HeapWord* target) const; duke@435: duke@435: // Find the list with size "size" in the binary tree and update duke@435: // the statistics in the list according to "split" (chunk was duke@435: // split or coalesce) and "birth" (chunk was added or removed). duke@435: void dictCensusUpdate(size_t size, bool split, bool birth); duke@435: // Return true if the dictionary is overpopulated (more chunks of duke@435: // this size than desired) for size "size". duke@435: bool coalDictOverPopulated(size_t size); duke@435: // Methods called at the beginning of a sweep to prepare the duke@435: // statistics for the sweep. duke@435: void beginSweepDictCensus(double coalSurplusPercent, ysr@1580: float inter_sweep_current, ysr@1580: float inter_sweep_estimate, ysr@1580: float intra_sweep_estimate); duke@435: // Methods called after the end of a sweep to modify the duke@435: // statistics for the sweep. duke@435: void endSweepDictCensus(double splitSurplusPercent); duke@435: // Return the largest free chunk in the tree. jmasa@3730: Chunk* findLargestDict() const; duke@435: // Accessors for statistics duke@435: void setTreeSurplus(double splitSurplusPercent); duke@435: void setTreeHints(void); duke@435: // Reset statistics for all the lists in the tree. duke@435: void clearTreeCensus(void); duke@435: // Print the statistcis for all the lists in the tree. Also may duke@435: // print out summaries. duke@435: void printDictCensus(void) const; ysr@1580: void print_free_lists(outputStream* st) const; duke@435: duke@435: // For debugging. Returns the sum of the _returnedBytes for duke@435: // all lists in the tree. duke@435: size_t sumDictReturnedBytes() PRODUCT_RETURN0; duke@435: // Sets the _returnedBytes for all the lists in the tree to zero. duke@435: void initializeDictReturnedBytes() PRODUCT_RETURN; duke@435: // For debugging. Return the total number of chunks in the dictionary. duke@435: size_t totalCount() PRODUCT_RETURN0; duke@435: duke@435: void reportStatistics() const; duke@435: duke@435: void verify() const; duke@435: }; stefank@2314: jmasa@3730: #endif // SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP