annotate src/share/vm/memory/binaryTreeDictionary.hpp @ 13274:c044f8d03932

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