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