duke@435: /* mikael@6198: * Copyright (c) 2001, 2013, 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: goetz@6337: template class TreeChunk; goetz@6337: template class BinaryTreeDictionary; goetz@6337: template class AscendTreeCensusClosure; goetz@6337: template class DescendTreeCensusClosure; goetz@6337: template class DescendTreeSearchClosure; duke@435: jmasa@4488: class FreeChunk; jmasa@4488: template class AdaptiveFreeList; goetz@6337: typedef BinaryTreeDictionary > AFLBinaryTreeDictionary; jmasa@4488: goetz@6337: template goetz@6337: class TreeList : public FreeList_t { jmasa@4196: friend class TreeChunk; jmasa@4196: friend class BinaryTreeDictionary; jmasa@4196: friend class AscendTreeCensusClosure; jmasa@4196: friend class DescendTreeCensusClosure; jmasa@4196: friend class DescendTreeSearchClosure; jmasa@3730: jmasa@4196: TreeList* _parent; jmasa@4196: TreeList* _left; jmasa@4196: TreeList* _right; duke@435: duke@435: protected: jmasa@3730: jmasa@4196: TreeList* parent() const { return _parent; } jmasa@4196: TreeList* left() const { return _left; } jmasa@4196: TreeList* right() const { return _right; } jmasa@3730: jmasa@4196: // Wrapper on call to base class, to get the template to compile. goetz@6337: Chunk_t* head() const { return FreeList_t::head(); } goetz@6337: Chunk_t* tail() const { return FreeList_t::tail(); } goetz@6337: void set_head(Chunk_t* head) { FreeList_t::set_head(head); } goetz@6337: void set_tail(Chunk_t* tail) { FreeList_t::set_tail(tail); } mgerdin@3822: goetz@6337: size_t size() const { return FreeList_t::size(); } duke@435: duke@435: // Accessors for links in tree. duke@435: jmasa@4196: void set_left(TreeList* tl) { duke@435: _left = tl; duke@435: if (tl != NULL) jmasa@3732: tl->set_parent(this); duke@435: } jmasa@4196: void set_right(TreeList* tl) { duke@435: _right = tl; duke@435: if (tl != NULL) jmasa@3732: tl->set_parent(this); duke@435: } jmasa@4196: void set_parent(TreeList* tl) { _parent = tl; } duke@435: jmasa@4196: void clear_left() { _left = NULL; } jmasa@3732: void clear_right() { _right = NULL; } jmasa@3732: void clear_parent() { _parent = NULL; } goetz@6337: void initialize() { clear_left(); clear_right(), clear_parent(); FreeList_t::initialize(); } duke@435: duke@435: // For constructing a TreeList from a Tree chunk or duke@435: // address and size. jmasa@4196: TreeList(); jmasa@4196: static TreeList* jmasa@4196: as_TreeList(TreeChunk* tc); jmasa@4196: 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@4196: 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@4196: 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@4196: TreeChunk* largest_address(); jmasa@4196: jmasa@4196: TreeList* get_better_list( jmasa@4196: BinaryTreeDictionary* dictionary); ysr@1580: jmasa@3732: // remove_chunk_replace_if_needed() removes the given "tc" from the TreeList. duke@435: // If "tc" is the first chunk in the list, it is also the jmasa@3732: // TreeList that is the node in the tree. remove_chunk_replace_if_needed() 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@4196: TreeList* remove_chunk_replace_if_needed(TreeChunk* tc); duke@435: // See FreeList. jmasa@4196: void return_chunk_at_head(TreeChunk* tc); jmasa@4196: void return_chunk_at_tail(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: goetz@6337: template jmasa@4196: class TreeChunk : public Chunk_t { jmasa@4196: friend class TreeList; jmasa@4196: TreeList* _list; jmasa@4196: TreeList _embedded_list; // if non-null, this chunk is on _list jmasa@4196: jmasa@4196: static size_t _min_tree_chunk_size; jmasa@4196: duke@435: protected: jmasa@4196: TreeList* embedded_list() const { return (TreeList*) &_embedded_list; } jmasa@4196: void set_embedded_list(TreeList* v) { _embedded_list = *v; } duke@435: public: jmasa@4196: TreeList* list() { return _list; } jmasa@4196: void set_list(TreeList* v) { _list = v; } jmasa@4196: static TreeChunk* as_TreeChunk(Chunk_t* 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@4196: Chunk_t* next() const { return Chunk_t::next(); } jmasa@4196: Chunk_t* prev() const { return Chunk_t::prev(); } jmasa@4196: size_t size() const volatile { return Chunk_t::size(); } jmasa@4196: jmasa@4196: static size_t min_size() { jmasa@4196: return _min_tree_chunk_size; jmasa@4196: } jmasa@3730: duke@435: // debugging jmasa@3732: void verify_tree_chunk_list() const; jmasa@4196: void assert_is_mangled() const; duke@435: }; duke@435: duke@435: goetz@6337: template jmasa@4196: class BinaryTreeDictionary: public FreeBlockDictionary { dcubed@587: friend class VMStructs; jmasa@3732: size_t _total_size; jmasa@3732: size_t _total_free_blocks; jmasa@4196: TreeList* _root; duke@435: duke@435: // private accessors jmasa@3732: void set_total_size(size_t v) { _total_size = v; } jmasa@3732: virtual void inc_total_size(size_t v); jmasa@3732: virtual void dec_total_size(size_t v); jmasa@3732: void set_total_free_blocks(size_t v) { _total_free_blocks = v; } jmasa@4196: TreeList* root() const { return _root; } jmasa@4196: void set_root(TreeList* v) { _root = v; } 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@4196: TreeChunk* get_chunk_from_tree(size_t size, enum FreeBlockDictionary::Dither dither); jmasa@4196: // Remove this chunk from the tree. If the removal results jmasa@4196: // in an empty list in the tree, remove the empty list. jmasa@4196: TreeChunk* remove_chunk_from_tree(TreeChunk* tc); jmasa@4196: // Remove the node in the trees starting at tl that has the jmasa@4196: // minimum value and return it. Repair the tree as needed. jmasa@4196: TreeList* remove_tree_minimum(TreeList* tl); jmasa@4196: // Add this free chunk to the tree. jmasa@4196: void insert_chunk_in_tree(Chunk_t* freeChunk); jmasa@4196: public: jmasa@4196: 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@4196: TreeList* find_list (size_t size) const; jmasa@3730: jmasa@3732: void verify_tree() const; duke@435: // verify that the given chunk is in the tree. jmasa@4196: bool verify_chunk_in_free_list(Chunk_t* tc) const; duke@435: private: jmasa@4196: void verify_tree_helper(TreeList* tl) const; jmasa@4196: static size_t verify_prev_free_ptrs(TreeList* tl); duke@435: duke@435: // Returns the total number of chunks in the list. jmasa@4196: size_t total_list_length(TreeList* tl) const; duke@435: // Returns the total number of words in the chunks in the tree duke@435: // starting at "tl". jmasa@4196: size_t total_size_in_tree(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@4196: 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@4196: size_t total_free_blocks_in_tree(TreeList* tl) const; jmasa@4196: size_t num_free_blocks() const; jmasa@4196: size_t tree_height() const; jmasa@4196: size_t tree_height_helper(TreeList* tl) const; jmasa@4196: size_t total_nodes_in_tree(TreeList* tl) const; jmasa@4196: size_t total_nodes_helper(TreeList* tl) const; duke@435: duke@435: public: duke@435: // Constructor jmasa@4196: BinaryTreeDictionary() : jmasa@4196: _total_size(0), _total_free_blocks(0), _root(0) {} jmasa@4196: jmasa@4196: BinaryTreeDictionary(MemRegion mr); jmasa@3730: jmasa@3730: // Public accessors jmasa@3732: size_t total_size() const { return _total_size; } jmasa@4196: size_t total_free_blocks() const { return _total_free_blocks; } 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. jmasa@4196: Chunk_t* get_chunk(size_t size, enum FreeBlockDictionary::Dither dither) { jmasa@4196: FreeBlockDictionary::verify_par_locked(); jmasa@4196: Chunk_t* res = get_chunk_from_tree(size, dither); jmasa@3732: assert(res == NULL || res->is_free(), duke@435: "Should be returning a free chunk"); jmasa@4196: assert(dither != FreeBlockDictionary::exactly || jmasa@4197: res == NULL || res->size() == size, "Not correct size"); duke@435: return res; duke@435: } duke@435: jmasa@4196: void return_chunk(Chunk_t* chunk) { jmasa@4196: FreeBlockDictionary::verify_par_locked(); jmasa@3732: insert_chunk_in_tree(chunk); duke@435: } duke@435: jmasa@4196: void remove_chunk(Chunk_t* chunk) { jmasa@4196: FreeBlockDictionary::verify_par_locked(); jmasa@4196: remove_chunk_from_tree((TreeChunk*)chunk); jmasa@3732: assert(chunk->is_free(), "Should still be a free chunk"); duke@435: } duke@435: jmasa@3732: size_t max_chunk_size() const; jmasa@3732: size_t total_chunk_size(debug_only(const Mutex* lock)) const { duke@435: debug_only( duke@435: if (lock != NULL && lock->owned_by_self()) { jmasa@3732: assert(total_size_in_tree(root()) == total_size(), jmasa@3732: "_total_size inconsistency"); duke@435: } duke@435: ) jmasa@3732: return total_size(); duke@435: } duke@435: jmasa@3732: size_t min_size() const { jmasa@4196: return TreeChunk::min_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@4196: Chunk_t* 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). jmasa@4196: void dict_census_update(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". jmasa@3732: bool coal_dict_over_populated(size_t size); duke@435: // Methods called at the beginning of a sweep to prepare the duke@435: // statistics for the sweep. jmasa@3732: void begin_sweep_dict_census(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. jmasa@3732: void end_sweep_dict_census(double splitSurplusPercent); duke@435: // Return the largest free chunk in the tree. jmasa@4196: Chunk_t* find_largest_dict() const; duke@435: // Accessors for statistics jmasa@3732: void set_tree_surplus(double splitSurplusPercent); jmasa@3732: void set_tree_hints(void); duke@435: // Reset statistics for all the lists in the tree. jmasa@3732: void clear_tree_census(void); duke@435: // Print the statistcis for all the lists in the tree. Also may duke@435: // print out summaries. jmasa@3732: void print_dict_census(void) const; ysr@1580: void print_free_lists(outputStream* st) const; duke@435: jmasa@3732: // For debugging. Returns the sum of the _returned_bytes for duke@435: // all lists in the tree. jmasa@3732: size_t sum_dict_returned_bytes() PRODUCT_RETURN0; jmasa@3732: // Sets the _returned_bytes for all the lists in the tree to zero. jmasa@3732: void initialize_dict_returned_bytes() PRODUCT_RETURN; duke@435: // For debugging. Return the total number of chunks in the dictionary. jmasa@3732: size_t total_count() PRODUCT_RETURN0; duke@435: jmasa@3732: void report_statistics() const; duke@435: duke@435: void verify() const; duke@435: }; stefank@2314: jmasa@3730: #endif // SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP