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