0N/A/*
3695N/A * Copyright (c) 2001, 2012, Oracle and/or its affiliates. All rights reserved.
0N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0N/A *
0N/A * This code is free software; you can redistribute it and/or modify it
0N/A * under the terms of the GNU General Public License version 2 only, as
0N/A * published by the Free Software Foundation.
0N/A *
0N/A * This code is distributed in the hope that it will be useful, but WITHOUT
0N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0N/A * version 2 for more details (a copy is included in the LICENSE file that
0N/A * accompanied this code).
0N/A *
0N/A * You should have received a copy of the GNU General Public License version
0N/A * 2 along with this work; if not, write to the Free Software Foundation,
0N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0N/A *
1472N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1472N/A * or visit www.oracle.com if you need additional information or have any
1472N/A * questions.
0N/A *
0N/A */
0N/A
3695N/A#ifndef SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP
3695N/A#define SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP
1879N/A
3695N/A#include "memory/freeBlockDictionary.hpp"
3695N/A#include "memory/freeList.hpp"
1879N/A
0N/A/*
0N/A * A binary tree based search structure for free blocks.
3695N/A * This is currently used in the Concurrent Mark&Sweep implementation, but
3695N/A * will be used for free block management for metadata.
0N/A */
0N/A
0N/A// A TreeList is a FreeList which can be used to maintain a
0N/A// binary tree of free lists.
0N/A
3695N/Atemplate <class Chunk> class TreeChunk;
3695N/Atemplate <class Chunk> class BinaryTreeDictionary;
3695N/Atemplate <class Chunk> class AscendTreeCensusClosure;
3695N/Atemplate <class Chunk> class DescendTreeCensusClosure;
3695N/Atemplate <class Chunk> class DescendTreeSearchClosure;
0N/A
3695N/Atemplate <class Chunk>
3695N/Aclass TreeList: public FreeList<Chunk> {
3695N/A friend class TreeChunk<Chunk>;
3695N/A friend class BinaryTreeDictionary<Chunk>;
3695N/A friend class AscendTreeCensusClosure<Chunk>;
3695N/A friend class DescendTreeCensusClosure<Chunk>;
3695N/A friend class DescendTreeSearchClosure<Chunk>;
3695N/A
3695N/A TreeList<Chunk>* _parent;
3695N/A TreeList<Chunk>* _left;
3695N/A TreeList<Chunk>* _right;
0N/A
0N/A protected:
3695N/A TreeList<Chunk>* parent() const { return _parent; }
3695N/A TreeList<Chunk>* left() const { return _left; }
3695N/A TreeList<Chunk>* right() const { return _right; }
3695N/A
3786N/A // Explicitly import these names into our namespace to fix name lookup with templates
3786N/A using FreeList<Chunk>::head;
3786N/A using FreeList<Chunk>::set_head;
3695N/A
3786N/A using FreeList<Chunk>::tail;
3786N/A using FreeList<Chunk>::set_tail;
3786N/A using FreeList<Chunk>::link_tail;
3786N/A
3786N/A using FreeList<Chunk>::increment_count;
3786N/A NOT_PRODUCT(using FreeList<Chunk>::increment_returned_bytes_by;)
3786N/A using FreeList<Chunk>::verify_chunk_in_free_list;
3786N/A using FreeList<Chunk>::size;
0N/A
0N/A // Accessors for links in tree.
0N/A
3697N/A void set_left(TreeList<Chunk>* tl) {
0N/A _left = tl;
0N/A if (tl != NULL)
3697N/A tl->set_parent(this);
0N/A }
3697N/A void set_right(TreeList<Chunk>* tl) {
0N/A _right = tl;
0N/A if (tl != NULL)
3697N/A tl->set_parent(this);
0N/A }
3697N/A void set_parent(TreeList<Chunk>* tl) { _parent = tl; }
0N/A
0N/A void clearLeft() { _left = NULL; }
3697N/A void clear_right() { _right = NULL; }
3697N/A void clear_parent() { _parent = NULL; }
3697N/A void initialize() { clearLeft(); clear_right(), clear_parent(); }
0N/A
0N/A // For constructing a TreeList from a Tree chunk or
0N/A // address and size.
3695N/A static TreeList<Chunk>* as_TreeList(TreeChunk<Chunk>* tc);
3695N/A static TreeList<Chunk>* as_TreeList(HeapWord* addr, size_t size);
0N/A
0N/A // Returns the head of the free list as a pointer to a TreeChunk.
3695N/A TreeChunk<Chunk>* head_as_TreeChunk();
0N/A
0N/A // Returns the first available chunk in the free list as a pointer
0N/A // to a TreeChunk.
3695N/A TreeChunk<Chunk>* first_available();
0N/A
1145N/A // Returns the block with the largest heap address amongst
1145N/A // those in the list for this size; potentially slow and expensive,
1145N/A // use with caution!
3695N/A TreeChunk<Chunk>* largest_address();
1145N/A
3697N/A // remove_chunk_replace_if_needed() removes the given "tc" from the TreeList.
0N/A // If "tc" is the first chunk in the list, it is also the
3697N/A // TreeList that is the node in the tree. remove_chunk_replace_if_needed()
0N/A // returns the possibly replaced TreeList* for the node in
0N/A // the tree. It also updates the parent of the original
0N/A // node to point to the new node.
3697N/A TreeList<Chunk>* remove_chunk_replace_if_needed(TreeChunk<Chunk>* tc);
0N/A // See FreeList.
3697N/A void return_chunk_at_head(TreeChunk<Chunk>* tc);
3697N/A void return_chunk_at_tail(TreeChunk<Chunk>* tc);
0N/A};
0N/A
3695N/A// A TreeChunk is a subclass of a Chunk that additionally
0N/A// maintains a pointer to the free list on which it is currently
0N/A// linked.
0N/A// A TreeChunk is also used as a node in the binary tree. This
0N/A// allows the binary tree to be maintained without any additional
0N/A// storage (the free chunks are used). In a binary tree the first
0N/A// chunk in the free list is also the tree node. Note that the
0N/A// TreeChunk has an embedded TreeList for this purpose. Because
0N/A// the first chunk in the list is distinguished in this fashion
0N/A// (also is the node in the tree), it is the last chunk to be found
0N/A// on the free list for a node in the tree and is only removed if
0N/A// it is the last chunk on the free list.
0N/A
3695N/Atemplate <class Chunk>
3695N/Aclass TreeChunk : public Chunk {
3695N/A friend class TreeList<Chunk>;
3695N/A TreeList<Chunk>* _list;
3695N/A TreeList<Chunk> _embedded_list; // if non-null, this chunk is on _list
0N/A protected:
3695N/A TreeList<Chunk>* embedded_list() const { return (TreeList<Chunk>*) &_embedded_list; }
3695N/A void set_embedded_list(TreeList<Chunk>* v) { _embedded_list = *v; }
0N/A public:
3695N/A TreeList<Chunk>* list() { return _list; }
3695N/A void set_list(TreeList<Chunk>* v) { _list = v; }
3695N/A static TreeChunk<Chunk>* as_TreeChunk(Chunk* fc);
0N/A // Initialize fields in a TreeChunk that should be
0N/A // initialized when the TreeChunk is being added to
0N/A // a free list in the tree.
0N/A void initialize() { embedded_list()->initialize(); }
0N/A
3695N/A Chunk* next() const { return Chunk::next(); }
3695N/A Chunk* prev() const { return Chunk::prev(); }
3695N/A size_t size() const volatile { return Chunk::size(); }
3695N/A
0N/A // debugging
3697N/A void verify_tree_chunk_list() const;
0N/A};
0N/A
0N/A
3695N/Atemplate <class Chunk>
3695N/Aclass BinaryTreeDictionary: public FreeBlockDictionary<Chunk> {
152N/A friend class VMStructs;
0N/A bool _splay;
3697N/A size_t _total_size;
3697N/A size_t _total_free_blocks;
3695N/A TreeList<Chunk>* _root;
3695N/A bool _adaptive_freelists;
0N/A
0N/A // private accessors
0N/A bool splay() const { return _splay; }
0N/A void set_splay(bool v) { _splay = v; }
3697N/A void set_total_size(size_t v) { _total_size = v; }
3697N/A virtual void inc_total_size(size_t v);
3697N/A virtual void dec_total_size(size_t v);
3697N/A size_t total_free_blocks() const { return _total_free_blocks; }
3697N/A void set_total_free_blocks(size_t v) { _total_free_blocks = v; }
3695N/A TreeList<Chunk>* root() const { return _root; }
3695N/A void set_root(TreeList<Chunk>* v) { _root = v; }
3695N/A bool adaptive_freelists() { return _adaptive_freelists; }
3695N/A
3695N/A // This field is added and can be set to point to the
3695N/A // the Mutex used to synchronize access to the
3695N/A // dictionary so that assertion checking can be done.
3695N/A // For example it is set to point to _parDictionaryAllocLock.
3695N/A NOT_PRODUCT(Mutex* _lock;)
0N/A
0N/A // Remove a chunk of size "size" or larger from the tree and
0N/A // return it. If the chunk
0N/A // is the last chunk of that size, remove the node for that size
0N/A // from the tree.
3697N/A TreeChunk<Chunk>* get_chunk_from_tree(size_t size, enum FreeBlockDictionary<Chunk>::Dither dither, bool splay);
0N/A // Return a list of the specified size or NULL from the tree.
0N/A // The list is not removed from the tree.
3697N/A TreeList<Chunk>* find_list (size_t size) const;
0N/A // Remove this chunk from the tree. If the removal results
0N/A // in an empty list in the tree, remove the empty list.
3697N/A TreeChunk<Chunk>* remove_chunk_from_tree(TreeChunk<Chunk>* tc);
0N/A // Remove the node in the trees starting at tl that has the
0N/A // minimum value and return it. Repair the tree as needed.
3697N/A TreeList<Chunk>* remove_tree_minimum(TreeList<Chunk>* tl);
3697N/A void semi_splay_step(TreeList<Chunk>* tl);
0N/A // Add this free chunk to the tree.
3697N/A void insert_chunk_in_tree(Chunk* freeChunk);
0N/A public:
3695N/A
3695N/A static const size_t min_tree_chunk_size = sizeof(TreeChunk<Chunk>)/HeapWordSize;
3695N/A
3697N/A void verify_tree() const;
0N/A // verify that the given chunk is in the tree.
3697N/A bool verify_chunk_in_free_list(Chunk* tc) const;
0N/A private:
3697N/A void verify_tree_helper(TreeList<Chunk>* tl) const;
3697N/A static size_t verify_prev_free_ptrs(TreeList<Chunk>* tl);
0N/A
0N/A // Returns the total number of chunks in the list.
3697N/A size_t total_list_length(TreeList<Chunk>* tl) const;
0N/A // Returns the total number of words in the chunks in the tree
0N/A // starting at "tl".
3697N/A size_t total_size_in_tree(TreeList<Chunk>* tl) const;
0N/A // Returns the sum of the square of the size of each block
0N/A // in the tree starting at "tl".
3695N/A double sum_of_squared_block_sizes(TreeList<Chunk>* const tl) const;
0N/A // Returns the total number of free blocks in the tree starting
0N/A // at "tl".
3697N/A size_t total_free_blocks_in_tree(TreeList<Chunk>* tl) const;
3697N/A size_t num_free_blocks() const;
0N/A size_t treeHeight() const;
3697N/A size_t tree_height_helper(TreeList<Chunk>* tl) const;
3697N/A size_t total_nodes_in_tree(TreeList<Chunk>* tl) const;
3697N/A size_t total_nodes_helper(TreeList<Chunk>* tl) const;
0N/A
0N/A public:
0N/A // Constructor
3695N/A BinaryTreeDictionary(bool adaptive_freelists, bool splay = false);
3695N/A BinaryTreeDictionary(MemRegion mr, bool adaptive_freelists, bool splay = false);
3695N/A
3695N/A // Public accessors
3697N/A size_t total_size() const { return _total_size; }
0N/A
0N/A // Reset the dictionary to the initial conditions with
0N/A // a single free chunk.
0N/A void reset(MemRegion mr);
0N/A void reset(HeapWord* addr, size_t size);
0N/A // Reset the dictionary to be empty.
0N/A void reset();
0N/A
0N/A // Return a chunk of size "size" or greater from
0N/A // the tree.
0N/A // want a better dynamic splay strategy for the future.
3697N/A Chunk* get_chunk(size_t size, enum FreeBlockDictionary<Chunk>::Dither dither) {
3695N/A FreeBlockDictionary<Chunk>::verify_par_locked();
3697N/A Chunk* res = get_chunk_from_tree(size, dither, splay());
3697N/A assert(res == NULL || res->is_free(),
0N/A "Should be returning a free chunk");
0N/A return res;
0N/A }
0N/A
3697N/A void return_chunk(Chunk* chunk) {
3695N/A FreeBlockDictionary<Chunk>::verify_par_locked();
3697N/A insert_chunk_in_tree(chunk);
0N/A }
0N/A
3697N/A void remove_chunk(Chunk* chunk) {
3695N/A FreeBlockDictionary<Chunk>::verify_par_locked();
3697N/A remove_chunk_from_tree((TreeChunk<Chunk>*)chunk);
3697N/A assert(chunk->is_free(), "Should still be a free chunk");
0N/A }
0N/A
3697N/A size_t max_chunk_size() const;
3697N/A size_t total_chunk_size(debug_only(const Mutex* lock)) const {
0N/A debug_only(
0N/A if (lock != NULL && lock->owned_by_self()) {
3697N/A assert(total_size_in_tree(root()) == total_size(),
3697N/A "_total_size inconsistency");
0N/A }
0N/A )
3697N/A return total_size();
0N/A }
0N/A
3697N/A size_t min_size() const {
3695N/A return min_tree_chunk_size;
0N/A }
0N/A
0N/A double sum_of_squared_block_sizes() const {
0N/A return sum_of_squared_block_sizes(root());
0N/A }
0N/A
3695N/A Chunk* find_chunk_ends_at(HeapWord* target) const;
0N/A
0N/A // Find the list with size "size" in the binary tree and update
0N/A // the statistics in the list according to "split" (chunk was
0N/A // split or coalesce) and "birth" (chunk was added or removed).
3697N/A void dict_census_udpate(size_t size, bool split, bool birth);
0N/A // Return true if the dictionary is overpopulated (more chunks of
0N/A // this size than desired) for size "size".
3697N/A bool coal_dict_over_populated(size_t size);
0N/A // Methods called at the beginning of a sweep to prepare the
0N/A // statistics for the sweep.
3697N/A void begin_sweep_dict_census(double coalSurplusPercent,
1145N/A float inter_sweep_current,
1145N/A float inter_sweep_estimate,
1145N/A float intra_sweep_estimate);
0N/A // Methods called after the end of a sweep to modify the
0N/A // statistics for the sweep.
3697N/A void end_sweep_dict_census(double splitSurplusPercent);
0N/A // Return the largest free chunk in the tree.
3697N/A Chunk* find_largest_dict() const;
0N/A // Accessors for statistics
3697N/A void set_tree_surplus(double splitSurplusPercent);
3697N/A void set_tree_hints(void);
0N/A // Reset statistics for all the lists in the tree.
3697N/A void clear_tree_census(void);
0N/A // Print the statistcis for all the lists in the tree. Also may
0N/A // print out summaries.
3697N/A void print_dict_census(void) const;
1145N/A void print_free_lists(outputStream* st) const;
0N/A
3697N/A // For debugging. Returns the sum of the _returned_bytes for
0N/A // all lists in the tree.
3697N/A size_t sum_dict_returned_bytes() PRODUCT_RETURN0;
3697N/A // Sets the _returned_bytes for all the lists in the tree to zero.
3697N/A void initialize_dict_returned_bytes() PRODUCT_RETURN;
0N/A // For debugging. Return the total number of chunks in the dictionary.
3697N/A size_t total_count() PRODUCT_RETURN0;
0N/A
3697N/A void report_statistics() const;
0N/A
0N/A void verify() const;
0N/A};
1879N/A
3695N/A#endif // SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP