1/* 2 * Copyright (c) 2001, 2017, 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/freeList.hpp" 29 30/* 31 * A binary tree based search structure for free blocks. 32 * This is currently used in the Concurrent Mark&Sweep implementation, but 33 * will be used for free block management for metadata. 34 */ 35 36// A TreeList is a FreeList which can be used to maintain a 37// binary tree of free lists. 38 39template <class Chunk_t, class FreeList_t> class TreeChunk; 40template <class Chunk_t, class FreeList_t> class BinaryTreeDictionary; 41template <class Chunk_t, class FreeList_t> class AscendTreeCensusClosure; 42template <class Chunk_t, class FreeList_t> class DescendTreeCensusClosure; 43template <class Chunk_t, class FreeList_t> class DescendTreeSearchClosure; 44 45class FreeChunk; 46template <class> class AdaptiveFreeList; 47typedef BinaryTreeDictionary<FreeChunk, AdaptiveFreeList<FreeChunk> > AFLBinaryTreeDictionary; 48 49template <class Chunk_t, class FreeList_t> 50class TreeList : public FreeList_t { 51 friend class TreeChunk<Chunk_t, FreeList_t>; 52 friend class BinaryTreeDictionary<Chunk_t, FreeList_t>; 53 friend class AscendTreeCensusClosure<Chunk_t, FreeList_t>; 54 friend class DescendTreeCensusClosure<Chunk_t, FreeList_t>; 55 friend class DescendTreeSearchClosure<Chunk_t, FreeList_t>; 56 57 TreeList<Chunk_t, FreeList_t>* _parent; 58 TreeList<Chunk_t, FreeList_t>* _left; 59 TreeList<Chunk_t, FreeList_t>* _right; 60 61 protected: 62 63 TreeList<Chunk_t, FreeList_t>* parent() const { return _parent; } 64 TreeList<Chunk_t, FreeList_t>* left() const { return _left; } 65 TreeList<Chunk_t, FreeList_t>* right() const { return _right; } 66 67 // Wrapper on call to base class, to get the template to compile. 68 Chunk_t* head() const { return FreeList_t::head(); } 69 Chunk_t* tail() const { return FreeList_t::tail(); } 70 void set_head(Chunk_t* head) { FreeList_t::set_head(head); } 71 void set_tail(Chunk_t* tail) { FreeList_t::set_tail(tail); } 72 73 size_t size() const { return FreeList_t::size(); } 74 75 // Accessors for links in tree. 76 77 void set_left(TreeList<Chunk_t, FreeList_t>* tl) { 78 _left = tl; 79 if (tl != NULL) 80 tl->set_parent(this); 81 } 82 void set_right(TreeList<Chunk_t, FreeList_t>* tl) { 83 _right = tl; 84 if (tl != NULL) 85 tl->set_parent(this); 86 } 87 void set_parent(TreeList<Chunk_t, FreeList_t>* tl) { _parent = tl; } 88 89 void clear_left() { _left = NULL; } 90 void clear_right() { _right = NULL; } 91 void clear_parent() { _parent = NULL; } 92 void initialize() { clear_left(); clear_right(), clear_parent(); FreeList_t::initialize(); } 93 94 // For constructing a TreeList from a Tree chunk or 95 // address and size. 96 TreeList(); 97 static TreeList<Chunk_t, FreeList_t>* 98 as_TreeList(TreeChunk<Chunk_t, FreeList_t>* tc); 99 static TreeList<Chunk_t, FreeList_t>* as_TreeList(HeapWord* addr, size_t size); 100 101 // Returns the head of the free list as a pointer to a TreeChunk. 102 TreeChunk<Chunk_t, FreeList_t>* head_as_TreeChunk(); 103 104 // Returns the first available chunk in the free list as a pointer 105 // to a TreeChunk. 106 TreeChunk<Chunk_t, FreeList_t>* first_available(); 107 108 // Returns the block with the largest heap address amongst 109 // those in the list for this size; potentially slow and expensive, 110 // use with caution! 111 TreeChunk<Chunk_t, FreeList_t>* largest_address(); 112 113 TreeList<Chunk_t, FreeList_t>* get_better_list( 114 BinaryTreeDictionary<Chunk_t, FreeList_t>* dictionary); 115 116 // remove_chunk_replace_if_needed() removes the given "tc" from the TreeList. 117 // If "tc" is the first chunk in the list, it is also the 118 // TreeList that is the node in the tree. remove_chunk_replace_if_needed() 119 // returns the possibly replaced TreeList* for the node in 120 // the tree. It also updates the parent of the original 121 // node to point to the new node. 122 TreeList<Chunk_t, FreeList_t>* remove_chunk_replace_if_needed(TreeChunk<Chunk_t, FreeList_t>* tc); 123 // See FreeList. 124 void return_chunk_at_head(TreeChunk<Chunk_t, FreeList_t>* tc); 125 void return_chunk_at_tail(TreeChunk<Chunk_t, FreeList_t>* tc); 126}; 127 128// A TreeChunk is a subclass of a Chunk that additionally 129// maintains a pointer to the free list on which it is currently 130// linked. 131// A TreeChunk is also used as a node in the binary tree. This 132// allows the binary tree to be maintained without any additional 133// storage (the free chunks are used). In a binary tree the first 134// chunk in the free list is also the tree node. Note that the 135// TreeChunk has an embedded TreeList for this purpose. Because 136// the first chunk in the list is distinguished in this fashion 137// (also is the node in the tree), it is the last chunk to be found 138// on the free list for a node in the tree and is only removed if 139// it is the last chunk on the free list. 140 141template <class Chunk_t, class FreeList_t> 142class TreeChunk : public Chunk_t { 143 friend class TreeList<Chunk_t, FreeList_t>; 144 TreeList<Chunk_t, FreeList_t>* _list; 145 TreeList<Chunk_t, FreeList_t> _embedded_list; // if non-null, this chunk is on _list 146 147 static size_t _min_tree_chunk_size; 148 149 protected: 150 TreeList<Chunk_t, FreeList_t>* embedded_list() const { return (TreeList<Chunk_t, FreeList_t>*) &_embedded_list; } 151 void set_embedded_list(TreeList<Chunk_t, FreeList_t>* v) { _embedded_list = *v; } 152 public: 153 TreeList<Chunk_t, FreeList_t>* list() { return _list; } 154 void set_list(TreeList<Chunk_t, FreeList_t>* v) { _list = v; } 155 static TreeChunk<Chunk_t, FreeList_t>* as_TreeChunk(Chunk_t* fc); 156 // Initialize fields in a TreeChunk that should be 157 // initialized when the TreeChunk is being added to 158 // a free list in the tree. 159 void initialize() { embedded_list()->initialize(); } 160 161 Chunk_t* next() const { return Chunk_t::next(); } 162 Chunk_t* prev() const { return Chunk_t::prev(); } 163 size_t size() const volatile { return Chunk_t::size(); } 164 165 static size_t min_size(); 166 167 // debugging 168 void verify_tree_chunk_list() const; 169 void assert_is_mangled() const; 170}; 171 172template <class Chunk_t, class FreeList_t> 173size_t TreeChunk<Chunk_t, FreeList_t>::_min_tree_chunk_size = sizeof(TreeChunk<Chunk_t, FreeList_t>)/HeapWordSize; 174template <class Chunk_t, class FreeList_t> 175size_t TreeChunk<Chunk_t, FreeList_t>::min_size() { return _min_tree_chunk_size; } 176 177template <class Chunk_t, class FreeList_t> 178class BinaryTreeDictionary: public CHeapObj<mtGC> { 179 friend class VMStructs; 180 size_t _total_size; 181 size_t _total_free_blocks; 182 TreeList<Chunk_t, FreeList_t>* _root; 183 184 // private accessors 185 void set_total_size(size_t v) { _total_size = v; } 186 void inc_total_size(size_t v); 187 void dec_total_size(size_t v); 188 void set_total_free_blocks(size_t v) { _total_free_blocks = v; } 189 TreeList<Chunk_t, FreeList_t>* root() const { return _root; } 190 void set_root(TreeList<Chunk_t, FreeList_t>* v) { _root = v; } 191 192 // This field is added and can be set to point to the 193 // the Mutex used to synchronize access to the 194 // dictionary so that assertion checking can be done. 195 // For example it is set to point to _parDictionaryAllocLock. 196 NOT_PRODUCT(Mutex* _lock;) 197 198 // Remove a chunk of size "size" or larger from the tree and 199 // return it. If the chunk 200 // is the last chunk of that size, remove the node for that size 201 // from the tree. 202 TreeChunk<Chunk_t, FreeList_t>* get_chunk_from_tree(size_t size); 203 // Remove this chunk from the tree. If the removal results 204 // in an empty list in the tree, remove the empty list. 205 TreeChunk<Chunk_t, FreeList_t>* remove_chunk_from_tree(TreeChunk<Chunk_t, FreeList_t>* tc); 206 // Remove the node in the trees starting at tl that has the 207 // minimum value and return it. Repair the tree as needed. 208 TreeList<Chunk_t, FreeList_t>* remove_tree_minimum(TreeList<Chunk_t, FreeList_t>* tl); 209 // Add this free chunk to the tree. 210 void insert_chunk_in_tree(Chunk_t* freeChunk); 211 public: 212 213 // Return a list of the specified size or NULL from the tree. 214 // The list is not removed from the tree. 215 TreeList<Chunk_t, FreeList_t>* find_list (size_t size) const; 216 217 void verify_tree() const; 218 // verify that the given chunk is in the tree. 219 bool verify_chunk_in_free_list(Chunk_t* tc) const; 220 private: 221 void verify_tree_helper(TreeList<Chunk_t, FreeList_t>* tl) const; 222 static size_t verify_prev_free_ptrs(TreeList<Chunk_t, FreeList_t>* tl); 223 224 // Returns the total number of chunks in the list. 225 size_t total_list_length(TreeList<Chunk_t, FreeList_t>* tl) const; 226 // Returns the total number of words in the chunks in the tree 227 // starting at "tl". 228 size_t total_size_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const; 229 // Returns the sum of the square of the size of each block 230 // in the tree starting at "tl". 231 double sum_of_squared_block_sizes(TreeList<Chunk_t, FreeList_t>* const tl) const; 232 // Returns the total number of free blocks in the tree starting 233 // at "tl". 234 size_t total_free_blocks_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const; 235 size_t num_free_blocks() const; 236 size_t tree_height() const; 237 size_t tree_height_helper(TreeList<Chunk_t, FreeList_t>* tl) const; 238 size_t total_nodes_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const; 239 size_t total_nodes_helper(TreeList<Chunk_t, FreeList_t>* tl) const; 240 241 public: 242 // Constructor 243 BinaryTreeDictionary() : 244 _total_size(0), _total_free_blocks(0), _root(0) {} 245 246 BinaryTreeDictionary(MemRegion mr); 247 248 // Public accessors 249 size_t total_size() const { return _total_size; } 250 size_t total_free_blocks() const { return _total_free_blocks; } 251 252 // Reset the dictionary to the initial conditions with 253 // a single free chunk. 254 void reset(MemRegion mr); 255 void reset(HeapWord* addr, size_t size); 256 // Reset the dictionary to be empty. 257 void reset(); 258 259 // Return a chunk of size "size" or greater from 260 // the tree. 261 Chunk_t* get_chunk(size_t size) { 262 verify_par_locked(); 263 Chunk_t* res = get_chunk_from_tree(size); 264 assert(res == NULL || res->is_free(), 265 "Should be returning a free chunk"); 266 return res; 267 } 268 269 void return_chunk(Chunk_t* chunk) { 270 verify_par_locked(); 271 insert_chunk_in_tree(chunk); 272 } 273 274 void remove_chunk(Chunk_t* chunk) { 275 verify_par_locked(); 276 remove_chunk_from_tree((TreeChunk<Chunk_t, FreeList_t>*)chunk); 277 assert(chunk->is_free(), "Should still be a free chunk"); 278 } 279 280 size_t max_chunk_size() const; 281 size_t total_chunk_size(debug_only(const Mutex* lock)) const { 282 debug_only( 283 if (lock != NULL && lock->owned_by_self()) { 284 assert(total_size_in_tree(root()) == total_size(), 285 "_total_size inconsistency"); 286 } 287 ) 288 return total_size(); 289 } 290 291 size_t min_size() const { 292 return TreeChunk<Chunk_t, FreeList_t>::min_size(); 293 } 294 295 double sum_of_squared_block_sizes() const { 296 return sum_of_squared_block_sizes(root()); 297 } 298 299 Chunk_t* find_chunk_ends_at(HeapWord* target) const; 300 301 // Find the list with size "size" in the binary tree and update 302 // the statistics in the list according to "split" (chunk was 303 // split or coalesce) and "birth" (chunk was added or removed). 304 void dict_census_update(size_t size, bool split, bool birth); 305 // Return true if the dictionary is overpopulated (more chunks of 306 // this size than desired) for size "size". 307 bool coal_dict_over_populated(size_t size); 308 // Methods called at the beginning of a sweep to prepare the 309 // statistics for the sweep. 310 void begin_sweep_dict_census(double coalSurplusPercent, 311 float inter_sweep_current, 312 float inter_sweep_estimate, 313 float intra_sweep_estimate); 314 // Methods called after the end of a sweep to modify the 315 // statistics for the sweep. 316 void end_sweep_dict_census(double splitSurplusPercent); 317 // Return the largest free chunk in the tree. 318 Chunk_t* find_largest_dict() const; 319 // Accessors for statistics 320 void set_tree_surplus(double splitSurplusPercent); 321 void set_tree_hints(void); 322 // Reset statistics for all the lists in the tree. 323 void clear_tree_census(void); 324 // Print the statistics for all the lists in the tree. Also may 325 // print out summaries. 326 void print_dict_census(outputStream* st) const; 327 void print_free_lists(outputStream* st) const; 328 329 // For debugging. Returns the sum of the _returned_bytes for 330 // all lists in the tree. 331 size_t sum_dict_returned_bytes() PRODUCT_RETURN0; 332 // Sets the _returned_bytes for all the lists in the tree to zero. 333 void initialize_dict_returned_bytes() PRODUCT_RETURN; 334 // For debugging. Return the total number of chunks in the dictionary. 335 size_t total_count() PRODUCT_RETURN0; 336 337 void report_statistics(outputStream* st) const; 338 339 void verify() const; 340 341 Mutex* par_lock() const PRODUCT_RETURN0; 342 void set_par_lock(Mutex* lock) PRODUCT_RETURN; 343 void verify_par_locked() const PRODUCT_RETURN; 344}; 345 346#endif // SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP 347