binaryTreeDictionary.hpp revision 3602:da91efe96a93
1/* 2 * Copyright (c) 2001, 2012, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 * 23 */ 24 25#ifndef SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP 26#define SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP 27 28#include "memory/freeBlockDictionary.hpp" 29#include "memory/freeList.hpp" 30 31/* 32 * A binary tree based search structure for free blocks. 33 * This is currently used in the Concurrent Mark&Sweep implementation, but 34 * will be used for free block management for metadata. 35 */ 36 37// A TreeList is a FreeList which can be used to maintain a 38// binary tree of free lists. 39 40template <class Chunk> class TreeChunk; 41template <class Chunk> class BinaryTreeDictionary; 42template <class Chunk> class AscendTreeCensusClosure; 43template <class Chunk> class DescendTreeCensusClosure; 44template <class Chunk> class DescendTreeSearchClosure; 45 46template <class Chunk> 47class TreeList: public FreeList<Chunk> { 48 friend class TreeChunk<Chunk>; 49 friend class BinaryTreeDictionary<Chunk>; 50 friend class AscendTreeCensusClosure<Chunk>; 51 friend class DescendTreeCensusClosure<Chunk>; 52 friend class DescendTreeSearchClosure<Chunk>; 53 54 TreeList<Chunk>* _parent; 55 TreeList<Chunk>* _left; 56 TreeList<Chunk>* _right; 57 58 protected: 59 TreeList<Chunk>* parent() const { return _parent; } 60 TreeList<Chunk>* left() const { return _left; } 61 TreeList<Chunk>* right() const { return _right; } 62 63 // Explicitly import these names into our namespace to fix name lookup with templates 64 using FreeList<Chunk>::head; 65 using FreeList<Chunk>::set_head; 66 67 using FreeList<Chunk>::tail; 68 using FreeList<Chunk>::set_tail; 69 using FreeList<Chunk>::link_tail; 70 71 using FreeList<Chunk>::increment_count; 72 NOT_PRODUCT(using FreeList<Chunk>::increment_returned_bytes_by;) 73 using FreeList<Chunk>::verify_chunk_in_free_list; 74 using FreeList<Chunk>::size; 75 76 // Accessors for links in tree. 77 78 void set_left(TreeList<Chunk>* tl) { 79 _left = tl; 80 if (tl != NULL) 81 tl->set_parent(this); 82 } 83 void set_right(TreeList<Chunk>* tl) { 84 _right = tl; 85 if (tl != NULL) 86 tl->set_parent(this); 87 } 88 void set_parent(TreeList<Chunk>* tl) { _parent = tl; } 89 90 void clearLeft() { _left = NULL; } 91 void clear_right() { _right = NULL; } 92 void clear_parent() { _parent = NULL; } 93 void initialize() { clearLeft(); clear_right(), clear_parent(); } 94 95 // For constructing a TreeList from a Tree chunk or 96 // address and size. 97 static TreeList<Chunk>* as_TreeList(TreeChunk<Chunk>* tc); 98 static TreeList<Chunk>* as_TreeList(HeapWord* addr, size_t size); 99 100 // Returns the head of the free list as a pointer to a TreeChunk. 101 TreeChunk<Chunk>* head_as_TreeChunk(); 102 103 // Returns the first available chunk in the free list as a pointer 104 // to a TreeChunk. 105 TreeChunk<Chunk>* first_available(); 106 107 // Returns the block with the largest heap address amongst 108 // those in the list for this size; potentially slow and expensive, 109 // use with caution! 110 TreeChunk<Chunk>* largest_address(); 111 112 // remove_chunk_replace_if_needed() removes the given "tc" from the TreeList. 113 // If "tc" is the first chunk in the list, it is also the 114 // TreeList that is the node in the tree. remove_chunk_replace_if_needed() 115 // returns the possibly replaced TreeList* for the node in 116 // the tree. It also updates the parent of the original 117 // node to point to the new node. 118 TreeList<Chunk>* remove_chunk_replace_if_needed(TreeChunk<Chunk>* tc); 119 // See FreeList. 120 void return_chunk_at_head(TreeChunk<Chunk>* tc); 121 void return_chunk_at_tail(TreeChunk<Chunk>* tc); 122}; 123 124// A TreeChunk is a subclass of a Chunk that additionally 125// maintains a pointer to the free list on which it is currently 126// linked. 127// A TreeChunk is also used as a node in the binary tree. This 128// allows the binary tree to be maintained without any additional 129// storage (the free chunks are used). In a binary tree the first 130// chunk in the free list is also the tree node. Note that the 131// TreeChunk has an embedded TreeList for this purpose. Because 132// the first chunk in the list is distinguished in this fashion 133// (also is the node in the tree), it is the last chunk to be found 134// on the free list for a node in the tree and is only removed if 135// it is the last chunk on the free list. 136 137template <class Chunk> 138class TreeChunk : public Chunk { 139 friend class TreeList<Chunk>; 140 TreeList<Chunk>* _list; 141 TreeList<Chunk> _embedded_list; // if non-null, this chunk is on _list 142 protected: 143 TreeList<Chunk>* embedded_list() const { return (TreeList<Chunk>*) &_embedded_list; } 144 void set_embedded_list(TreeList<Chunk>* v) { _embedded_list = *v; } 145 public: 146 TreeList<Chunk>* list() { return _list; } 147 void set_list(TreeList<Chunk>* v) { _list = v; } 148 static TreeChunk<Chunk>* as_TreeChunk(Chunk* fc); 149 // Initialize fields in a TreeChunk that should be 150 // initialized when the TreeChunk is being added to 151 // a free list in the tree. 152 void initialize() { embedded_list()->initialize(); } 153 154 Chunk* next() const { return Chunk::next(); } 155 Chunk* prev() const { return Chunk::prev(); } 156 size_t size() const volatile { return Chunk::size(); } 157 158 // debugging 159 void verify_tree_chunk_list() const; 160}; 161 162 163template <class Chunk> 164class BinaryTreeDictionary: public FreeBlockDictionary<Chunk> { 165 friend class VMStructs; 166 bool _splay; 167 bool _adaptive_freelists; 168 size_t _total_size; 169 size_t _total_free_blocks; 170 TreeList<Chunk>* _root; 171 172 // private accessors 173 bool splay() const { return _splay; } 174 void set_splay(bool v) { _splay = v; } 175 void set_total_size(size_t v) { _total_size = v; } 176 virtual void inc_total_size(size_t v); 177 virtual void dec_total_size(size_t v); 178 size_t total_free_blocks() const { return _total_free_blocks; } 179 void set_total_free_blocks(size_t v) { _total_free_blocks = v; } 180 TreeList<Chunk>* root() const { return _root; } 181 void set_root(TreeList<Chunk>* v) { _root = v; } 182 bool adaptive_freelists() { return _adaptive_freelists; } 183 184 // This field is added and can be set to point to the 185 // the Mutex used to synchronize access to the 186 // dictionary so that assertion checking can be done. 187 // For example it is set to point to _parDictionaryAllocLock. 188 NOT_PRODUCT(Mutex* _lock;) 189 190 // Remove a chunk of size "size" or larger from the tree and 191 // return it. If the chunk 192 // is the last chunk of that size, remove the node for that size 193 // from the tree. 194 TreeChunk<Chunk>* get_chunk_from_tree(size_t size, enum FreeBlockDictionary<Chunk>::Dither dither, bool splay); 195 // Return a list of the specified size or NULL from the tree. 196 // The list is not removed from the tree. 197 TreeList<Chunk>* find_list (size_t size) const; 198 // Remove this chunk from the tree. If the removal results 199 // in an empty list in the tree, remove the empty list. 200 TreeChunk<Chunk>* remove_chunk_from_tree(TreeChunk<Chunk>* tc); 201 // Remove the node in the trees starting at tl that has the 202 // minimum value and return it. Repair the tree as needed. 203 TreeList<Chunk>* remove_tree_minimum(TreeList<Chunk>* tl); 204 void semi_splay_step(TreeList<Chunk>* tl); 205 // Add this free chunk to the tree. 206 void insert_chunk_in_tree(Chunk* freeChunk); 207 public: 208 209 static const size_t min_tree_chunk_size = sizeof(TreeChunk<Chunk>)/HeapWordSize; 210 211 void verify_tree() const; 212 // verify that the given chunk is in the tree. 213 bool verify_chunk_in_free_list(Chunk* tc) const; 214 private: 215 void verify_tree_helper(TreeList<Chunk>* tl) const; 216 static size_t verify_prev_free_ptrs(TreeList<Chunk>* tl); 217 218 // Returns the total number of chunks in the list. 219 size_t total_list_length(TreeList<Chunk>* tl) const; 220 // Returns the total number of words in the chunks in the tree 221 // starting at "tl". 222 size_t total_size_in_tree(TreeList<Chunk>* tl) const; 223 // Returns the sum of the square of the size of each block 224 // in the tree starting at "tl". 225 double sum_of_squared_block_sizes(TreeList<Chunk>* const tl) const; 226 // Returns the total number of free blocks in the tree starting 227 // at "tl". 228 size_t total_free_blocks_in_tree(TreeList<Chunk>* tl) const; 229 size_t num_free_blocks() const; 230 size_t treeHeight() const; 231 size_t tree_height_helper(TreeList<Chunk>* tl) const; 232 size_t total_nodes_in_tree(TreeList<Chunk>* tl) const; 233 size_t total_nodes_helper(TreeList<Chunk>* tl) const; 234 235 public: 236 // Constructor 237 BinaryTreeDictionary(bool adaptive_freelists, bool splay = false); 238 BinaryTreeDictionary(MemRegion mr, bool adaptive_freelists, bool splay = false); 239 240 // Public accessors 241 size_t total_size() const { return _total_size; } 242 243 // Reset the dictionary to the initial conditions with 244 // a single free chunk. 245 void reset(MemRegion mr); 246 void reset(HeapWord* addr, size_t size); 247 // Reset the dictionary to be empty. 248 void reset(); 249 250 // Return a chunk of size "size" or greater from 251 // the tree. 252 // want a better dynamic splay strategy for the future. 253 Chunk* get_chunk(size_t size, enum FreeBlockDictionary<Chunk>::Dither dither) { 254 FreeBlockDictionary<Chunk>::verify_par_locked(); 255 Chunk* res = get_chunk_from_tree(size, dither, splay()); 256 assert(res == NULL || res->is_free(), 257 "Should be returning a free chunk"); 258 return res; 259 } 260 261 void return_chunk(Chunk* chunk) { 262 FreeBlockDictionary<Chunk>::verify_par_locked(); 263 insert_chunk_in_tree(chunk); 264 } 265 266 void remove_chunk(Chunk* chunk) { 267 FreeBlockDictionary<Chunk>::verify_par_locked(); 268 remove_chunk_from_tree((TreeChunk<Chunk>*)chunk); 269 assert(chunk->is_free(), "Should still be a free chunk"); 270 } 271 272 size_t max_chunk_size() const; 273 size_t total_chunk_size(debug_only(const Mutex* lock)) const { 274 debug_only( 275 if (lock != NULL && lock->owned_by_self()) { 276 assert(total_size_in_tree(root()) == total_size(), 277 "_total_size inconsistency"); 278 } 279 ) 280 return total_size(); 281 } 282 283 size_t min_size() const { 284 return min_tree_chunk_size; 285 } 286 287 double sum_of_squared_block_sizes() const { 288 return sum_of_squared_block_sizes(root()); 289 } 290 291 Chunk* find_chunk_ends_at(HeapWord* target) const; 292 293 // Find the list with size "size" in the binary tree and update 294 // the statistics in the list according to "split" (chunk was 295 // split or coalesce) and "birth" (chunk was added or removed). 296 void dict_census_udpate(size_t size, bool split, bool birth); 297 // Return true if the dictionary is overpopulated (more chunks of 298 // this size than desired) for size "size". 299 bool coal_dict_over_populated(size_t size); 300 // Methods called at the beginning of a sweep to prepare the 301 // statistics for the sweep. 302 void begin_sweep_dict_census(double coalSurplusPercent, 303 float inter_sweep_current, 304 float inter_sweep_estimate, 305 float intra_sweep_estimate); 306 // Methods called after the end of a sweep to modify the 307 // statistics for the sweep. 308 void end_sweep_dict_census(double splitSurplusPercent); 309 // Return the largest free chunk in the tree. 310 Chunk* find_largest_dict() const; 311 // Accessors for statistics 312 void set_tree_surplus(double splitSurplusPercent); 313 void set_tree_hints(void); 314 // Reset statistics for all the lists in the tree. 315 void clear_tree_census(void); 316 // Print the statistcis for all the lists in the tree. Also may 317 // print out summaries. 318 void print_dict_census(void) const; 319 void print_free_lists(outputStream* st) const; 320 321 // For debugging. Returns the sum of the _returned_bytes for 322 // all lists in the tree. 323 size_t sum_dict_returned_bytes() PRODUCT_RETURN0; 324 // Sets the _returned_bytes for all the lists in the tree to zero. 325 void initialize_dict_returned_bytes() PRODUCT_RETURN; 326 // For debugging. Return the total number of chunks in the dictionary. 327 size_t total_count() PRODUCT_RETURN0; 328 329 void report_statistics() const; 330 331 void verify() const; 332}; 333 334#endif // SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP 335