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 39 template <class Chunk_t, class FreeList_t> class TreeChunk; 40 template <class Chunk_t, class FreeList_t> class BinaryTreeDictionary; 41 template <class Chunk_t, class FreeList_t> class AscendTreeCensusClosure; 42 template <class Chunk_t, class FreeList_t> class DescendTreeCensusClosure; 43 template <class Chunk_t, class FreeList_t> class DescendTreeSearchClosure; 44 45 template <class Chunk_t, class FreeList_t> 46 class TreeList : public FreeList_t { 47 friend class TreeChunk<Chunk_t, FreeList_t>; 48 friend class BinaryTreeDictionary<Chunk_t, FreeList_t>; 49 friend class AscendTreeCensusClosure<Chunk_t, FreeList_t>; 50 friend class DescendTreeCensusClosure<Chunk_t, FreeList_t>; 51 friend class DescendTreeSearchClosure<Chunk_t, FreeList_t>; 52 53 TreeList<Chunk_t, FreeList_t>* _parent; 54 TreeList<Chunk_t, FreeList_t>* _left; 55 TreeList<Chunk_t, FreeList_t>* _right; 56 57 protected: 58 59 TreeList<Chunk_t, FreeList_t>* parent() const { return _parent; } 60 TreeList<Chunk_t, FreeList_t>* left() const { return _left; } 61 TreeList<Chunk_t, FreeList_t>* right() const { return _right; } 62 63 // Wrapper on call to base class, to get the template to compile. 64 Chunk_t* head() const { return FreeList_t::head(); } 65 Chunk_t* tail() const { return FreeList_t::tail(); } 66 void set_head(Chunk_t* head) { FreeList_t::set_head(head); } 67 void set_tail(Chunk_t* tail) { FreeList_t::set_tail(tail); } 68 69 size_t size() const { return FreeList_t::size(); } 70 71 // Accessors for links in tree. 72 73 void set_left(TreeList<Chunk_t, FreeList_t>* tl) { 74 _left = tl; 75 if (tl != NULL) 76 tl->set_parent(this); 77 } 78 void set_right(TreeList<Chunk_t, FreeList_t>* tl) { 79 _right = tl; 80 if (tl != NULL) 81 tl->set_parent(this); 82 } 83 void set_parent(TreeList<Chunk_t, FreeList_t>* tl) { _parent = tl; } 84 85 void clear_left() { _left = NULL; } 86 void clear_right() { _right = NULL; } 87 void clear_parent() { _parent = NULL; } 88 void initialize() { clear_left(); clear_right(), clear_parent(); FreeList_t::initialize(); } 89 90 // For constructing a TreeList from a Tree chunk or 91 // address and size. 92 TreeList(); 93 static TreeList<Chunk_t, FreeList_t>* 94 as_TreeList(TreeChunk<Chunk_t, FreeList_t>* tc); 95 static TreeList<Chunk_t, FreeList_t>* as_TreeList(HeapWord* addr, size_t size); 96 97 // Returns the head of the free list as a pointer to a TreeChunk. 98 TreeChunk<Chunk_t, FreeList_t>* head_as_TreeChunk(); 99 100 // Returns the first available chunk in the free list as a pointer 101 // to a TreeChunk. 102 TreeChunk<Chunk_t, FreeList_t>* first_available(); 103 104 // Returns the block with the largest heap address amongst 105 // those in the list for this size; potentially slow and expensive, 106 // use with caution! 107 TreeChunk<Chunk_t, FreeList_t>* largest_address(); 108 109 TreeList<Chunk_t, FreeList_t>* get_better_list( 110 BinaryTreeDictionary<Chunk_t, FreeList_t>* dictionary); 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_t, FreeList_t>* remove_chunk_replace_if_needed(TreeChunk<Chunk_t, FreeList_t>* tc); 119 // See FreeList. 120 void return_chunk_at_head(TreeChunk<Chunk_t, FreeList_t>* tc); 121 void return_chunk_at_tail(TreeChunk<Chunk_t, FreeList_t>* 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 137 template <class Chunk_t, class FreeList_t> 138 class TreeChunk : public Chunk_t { 139 friend class TreeList<Chunk_t, FreeList_t>; 140 TreeList<Chunk_t, FreeList_t>* _list; 141 TreeList<Chunk_t, FreeList_t> _embedded_list; // if non-null, this chunk is on _list 142 143 static size_t _min_tree_chunk_size; 144 145 protected: 146 TreeList<Chunk_t, FreeList_t>* embedded_list() const { return (TreeList<Chunk_t, FreeList_t>*) &_embedded_list; } 147 void set_embedded_list(TreeList<Chunk_t, FreeList_t>* v) { _embedded_list = *v; } 148 public: 149 TreeList<Chunk_t, FreeList_t>* list() { return _list; } 150 void set_list(TreeList<Chunk_t, FreeList_t>* v) { _list = v; } 151 static TreeChunk<Chunk_t, FreeList_t>* as_TreeChunk(Chunk_t* fc); 152 // Initialize fields in a TreeChunk that should be 153 // initialized when the TreeChunk is being added to 154 // a free list in the tree. 155 void initialize() { embedded_list()->initialize(); } 156 157 Chunk_t* next() const { return Chunk_t::next(); } 158 Chunk_t* prev() const { return Chunk_t::prev(); } 159 size_t size() const volatile { return Chunk_t::size(); } 160 161 static size_t min_size(); 162 163 // debugging 164 void verify_tree_chunk_list() const; 165 void assert_is_mangled() const; 166 }; 167 168 template <class Chunk_t, class FreeList_t> 169 size_t TreeChunk<Chunk_t, FreeList_t>::_min_tree_chunk_size = sizeof(TreeChunk<Chunk_t, FreeList_t>)/HeapWordSize; 170 template <class Chunk_t, class FreeList_t> 171 size_t TreeChunk<Chunk_t, FreeList_t>::min_size() { return _min_tree_chunk_size; } 172 173 template <class Chunk_t, class FreeList_t> 174 class BinaryTreeDictionary: public CHeapObj<mtGC> { 175 friend class VMStructs; 176 177 protected: 178 size_t _total_size; 179 size_t _total_free_blocks; 180 TreeList<Chunk_t, FreeList_t>* _root; 181 182 // private accessors 183 void set_total_size(size_t v) { _total_size = v; } 184 void inc_total_size(size_t v); 185 void dec_total_size(size_t v); 186 void set_total_free_blocks(size_t v) { _total_free_blocks = v; } 187 TreeList<Chunk_t, FreeList_t>* root() const { return _root; } 188 void set_root(TreeList<Chunk_t, FreeList_t>* v) { _root = v; } 189 190 // This field is added and can be set to point to the 191 // the Mutex used to synchronize access to the 192 // dictionary so that assertion checking can be done. 193 // For example it is set to point to _parDictionaryAllocLock. 194 NOT_PRODUCT(Mutex* _lock;) 195 196 // Remove a chunk of size "size" or larger from the tree and 197 // return it. If the chunk 198 // is the last chunk of that size, remove the node for that size 199 // from the tree. 200 TreeChunk<Chunk_t, FreeList_t>* get_chunk_from_tree(size_t size); 201 // Remove this chunk from the tree. If the removal results 202 // in an empty list in the tree, remove the empty list. 203 TreeChunk<Chunk_t, FreeList_t>* remove_chunk_from_tree(TreeChunk<Chunk_t, FreeList_t>* tc); 204 // Remove the node in the trees starting at tl that has the 205 // minimum value and return it. Repair the tree as needed. 206 TreeList<Chunk_t, FreeList_t>* remove_tree_minimum(TreeList<Chunk_t, FreeList_t>* tl); 207 // Add this free chunk to the tree. 208 void insert_chunk_in_tree(Chunk_t* freeChunk); 209 public: 210 211 // Return a list of the specified size or NULL from the tree. 212 // The list is not removed from the tree. 213 TreeList<Chunk_t, FreeList_t>* find_list (size_t size) const; 214 215 void verify_tree() const; 216 // verify that the given chunk is in the tree. 217 bool verify_chunk_in_free_list(Chunk_t* tc) const; 218 private: 219 void verify_tree_helper(TreeList<Chunk_t, FreeList_t>* tl) const; 220 static size_t verify_prev_free_ptrs(TreeList<Chunk_t, FreeList_t>* tl); 221 222 // Returns the total number of chunks in the list. 223 size_t total_list_length(TreeList<Chunk_t, FreeList_t>* tl) const; 224 // Returns the total number of words in the chunks in the tree 225 // starting at "tl". 226 size_t total_size_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const; 227 // Returns the sum of the square of the size of each block 228 // in the tree starting at "tl". 229 double sum_of_squared_block_sizes(TreeList<Chunk_t, FreeList_t>* const tl) const; 230 // Returns the total number of free blocks in the tree starting 231 // at "tl". 232 size_t total_free_blocks_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const; 233 size_t num_free_blocks() const; 234 size_t tree_height() const; 235 size_t tree_height_helper(TreeList<Chunk_t, FreeList_t>* tl) const; 236 size_t total_nodes_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const; 237 size_t total_nodes_helper(TreeList<Chunk_t, FreeList_t>* tl) const; 238 239 public: 240 // Constructor 241 BinaryTreeDictionary() : 242 _total_size(0), _total_free_blocks(0), _root(0) {} 243 244 BinaryTreeDictionary(MemRegion mr); 245 246 // Public accessors 247 size_t total_size() const { return _total_size; } 248 size_t total_free_blocks() const { return _total_free_blocks; } 249 250 // Reset the dictionary to the initial conditions with 251 // a single free chunk. 252 void reset(MemRegion mr); 253 void reset(HeapWord* addr, size_t size); 254 // Reset the dictionary to be empty. 255 void reset(); 256 257 // Return a chunk of size "size" or greater from 258 // the tree. 259 Chunk_t* get_chunk(size_t size) { 260 verify_par_locked(); 261 Chunk_t* res = get_chunk_from_tree(size); 262 assert(res == NULL || res->is_free(), 263 "Should be returning a free chunk"); 264 return res; 265 } 266 267 void return_chunk(Chunk_t* chunk) { 268 verify_par_locked(); 269 insert_chunk_in_tree(chunk); 270 } 271 272 void remove_chunk(Chunk_t* chunk) { 273 verify_par_locked(); 274 remove_chunk_from_tree((TreeChunk<Chunk_t, FreeList_t>*)chunk); 275 assert(chunk->is_free(), "Should still be a free chunk"); 276 } 277 278 size_t max_chunk_size() const; 279 size_t total_chunk_size(debug_only(const Mutex* lock)) const { 280 debug_only( 281 if (lock != NULL && lock->owned_by_self()) { 282 assert(total_size_in_tree(root()) == total_size(), 283 "_total_size inconsistency"); 284 } 285 ) 286 return total_size(); 287 } 288 289 size_t min_size() const { 290 return TreeChunk<Chunk_t, FreeList_t>::min_size(); 291 } 292 293 double sum_of_squared_block_sizes() const { 294 return sum_of_squared_block_sizes(root()); 295 } 296 297 Chunk_t* find_chunk_ends_at(HeapWord* target) const; 298 299 // Return the largest free chunk in the tree. 300 Chunk_t* find_largest_dict() const; 301 302 void print_free_lists(outputStream* st) const; 303 304 // For debugging. Returns the sum of the _returned_bytes for 305 // all lists in the tree. 306 size_t sum_dict_returned_bytes() PRODUCT_RETURN0; 307 // Sets the _returned_bytes for all the lists in the tree to zero. 308 void initialize_dict_returned_bytes() PRODUCT_RETURN; 309 // For debugging. Return the total number of chunks in the dictionary. 310 size_t total_count() PRODUCT_RETURN0; 311 312 void report_statistics(outputStream* st) const; 313 314 void verify() const; 315 316 Mutex* par_lock() const PRODUCT_RETURN0; 317 void set_par_lock(Mutex* lock) PRODUCT_RETURN; 318 void verify_par_locked() const PRODUCT_RETURN; 319 }; 320 321 322 // Closures for walking the binary tree. 323 // do_list() walks the free list in a node applying the closure 324 // to each free chunk in the list 325 // do_tree() walks the nodes in the binary tree applying do_list() 326 // to each list at each node. 327 328 template <class Chunk_t, class FreeList_t> 329 class TreeCensusClosure : public StackObj { 330 protected: 331 virtual void do_list(FreeList_t* fl) = 0; 332 public: 333 virtual void do_tree(TreeList<Chunk_t, FreeList_t>* tl) = 0; 334 }; 335 336 template <class Chunk_t, class FreeList_t> 337 class AscendTreeCensusClosure : public TreeCensusClosure<Chunk_t, FreeList_t> { 338 public: 339 void do_tree(TreeList<Chunk_t, FreeList_t>* tl) { 340 if (tl != NULL) { 341 do_tree(tl->left()); 342 this->do_list(tl); 343 do_tree(tl->right()); 344 } 345 } 346 }; 347 348 template <class Chunk_t, class FreeList_t> 349 class DescendTreeCensusClosure : public TreeCensusClosure<Chunk_t, FreeList_t> { 350 public: 351 void do_tree(TreeList<Chunk_t, FreeList_t>* tl) { 352 if (tl != NULL) { 353 do_tree(tl->right()); 354 this->do_list(tl); 355 do_tree(tl->left()); 356 } 357 } 358 }; 359 360 // Used to search the tree until a condition is met. 361 // Similar to TreeCensusClosure but searches the 362 // tree and returns promptly when found. 363 364 template <class Chunk_t, class FreeList_t> 365 class TreeSearchClosure : public StackObj { 366 protected: 367 virtual bool do_list(FreeList_t* fl) = 0; 368 public: 369 virtual bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) = 0; 370 }; 371 372 #if 0 // Don't need this yet but here for symmetry. 373 template <class Chunk_t, class FreeList_t> 374 class AscendTreeSearchClosure : public TreeSearchClosure<Chunk_t> { 375 public: 376 bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) { 377 if (tl != NULL) { 378 if (do_tree(tl->left())) return true; 379 if (do_list(tl)) return true; 380 if (do_tree(tl->right())) return true; 381 } 382 return false; 383 } 384 }; 385 #endif 386 387 template <class Chunk_t, class FreeList_t> 388 class DescendTreeSearchClosure : public TreeSearchClosure<Chunk_t, FreeList_t> { 389 public: 390 bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) { 391 if (tl != NULL) { 392 if (do_tree(tl->right())) return true; 393 if (this->do_list(tl)) return true; 394 if (do_tree(tl->left())) return true; 395 } 396 return false; 397 } 398 }; 399 400 #endif // SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP