aboutsummaryrefslogtreecommitdiff
path: root/src/share/vm/memory/binaryTreeDictionary.hpp
blob: 757eb4fdac9b4d21ba2e4713df028ade5f5d7b42 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
/*
 * Copyright (c) 2001, 2012, Oracle and/or its affiliates. All rights reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
 * or visit www.oracle.com if you need additional information or have any
 * questions.
 *
 */

#ifndef SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP
#define SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP

#include "memory/freeBlockDictionary.hpp"
#include "memory/freeList.hpp"

/*
 * A binary tree based search structure for free blocks.
 * This is currently used in the Concurrent Mark&Sweep implementation, but
 * will be used for free block management for metadata.
 */

// A TreeList is a FreeList which can be used to maintain a
// binary tree of free lists.

template <class Chunk_t, template <class> class FreeList_t> class TreeChunk;
template <class Chunk_t, template <class> class FreeList_t> class BinaryTreeDictionary;
template <class Chunk_t, template <class> class FreeList_t> class AscendTreeCensusClosure;
template <class Chunk_t, template <class> class FreeList_t> class DescendTreeCensusClosure;
template <class Chunk_t, template <class> class FreeList_t> class DescendTreeSearchClosure;

template <class Chunk_t, template <class> class FreeList_t>
class TreeList : public FreeList_t<Chunk_t> {
  friend class TreeChunk<Chunk_t, FreeList_t>;
  friend class BinaryTreeDictionary<Chunk_t, FreeList_t>;
  friend class AscendTreeCensusClosure<Chunk_t, FreeList_t>;
  friend class DescendTreeCensusClosure<Chunk_t, FreeList_t>;
  friend class DescendTreeSearchClosure<Chunk_t, FreeList_t>;

  TreeList<Chunk_t, FreeList_t>* _parent;
  TreeList<Chunk_t, FreeList_t>* _left;
  TreeList<Chunk_t, FreeList_t>* _right;

 protected:

  TreeList<Chunk_t, FreeList_t>* parent() const { return _parent; }
  TreeList<Chunk_t, FreeList_t>* left()   const { return _left;   }
  TreeList<Chunk_t, FreeList_t>* right()  const { return _right;  }

  // Wrapper on call to base class, to get the template to compile.
  Chunk_t* head() const { return FreeList_t<Chunk_t>::head(); }
  Chunk_t* tail() const { return FreeList_t<Chunk_t>::tail(); }
  void set_head(Chunk_t* head) { FreeList_t<Chunk_t>::set_head(head); }
  void set_tail(Chunk_t* tail) { FreeList_t<Chunk_t>::set_tail(tail); }

  size_t size() const { return FreeList_t<Chunk_t>::size(); }

  // Accessors for links in tree.

  void set_left(TreeList<Chunk_t, FreeList_t>* tl) {
    _left   = tl;
    if (tl != NULL)
      tl->set_parent(this);
  }
  void set_right(TreeList<Chunk_t, FreeList_t>* tl) {
    _right  = tl;
    if (tl != NULL)
      tl->set_parent(this);
  }
  void set_parent(TreeList<Chunk_t, FreeList_t>* tl)  { _parent = tl;   }

  void clear_left()               { _left = NULL;   }
  void clear_right()              { _right = NULL;  }
  void clear_parent()             { _parent = NULL; }
  void initialize()               { clear_left(); clear_right(), clear_parent(); FreeList_t<Chunk_t>::initialize(); }

  // For constructing a TreeList from a Tree chunk or
  // address and size.
  TreeList();
  static TreeList<Chunk_t, FreeList_t>*
          as_TreeList(TreeChunk<Chunk_t, FreeList_t>* tc);
  static TreeList<Chunk_t, FreeList_t>* as_TreeList(HeapWord* addr, size_t size);

  // Returns the head of the free list as a pointer to a TreeChunk.
  TreeChunk<Chunk_t, FreeList_t>* head_as_TreeChunk();

  // Returns the first available chunk in the free list as a pointer
  // to a TreeChunk.
  TreeChunk<Chunk_t, FreeList_t>* first_available();

  // Returns the block with the largest heap address amongst
  // those in the list for this size; potentially slow and expensive,
  // use with caution!
  TreeChunk<Chunk_t, FreeList_t>* largest_address();

  TreeList<Chunk_t, FreeList_t>* get_better_list(
    BinaryTreeDictionary<Chunk_t, FreeList_t>* dictionary);

  // remove_chunk_replace_if_needed() removes the given "tc" from the TreeList.
  // If "tc" is the first chunk in the list, it is also the
  // TreeList that is the node in the tree.  remove_chunk_replace_if_needed()
  // returns the possibly replaced TreeList* for the node in
  // the tree.  It also updates the parent of the original
  // node to point to the new node.
  TreeList<Chunk_t, FreeList_t>* remove_chunk_replace_if_needed(TreeChunk<Chunk_t, FreeList_t>* tc);
  // See FreeList.
  void return_chunk_at_head(TreeChunk<Chunk_t, FreeList_t>* tc);
  void return_chunk_at_tail(TreeChunk<Chunk_t, FreeList_t>* tc);
};

// A TreeChunk is a subclass of a Chunk that additionally
// maintains a pointer to the free list on which it is currently
// linked.
// A TreeChunk is also used as a node in the binary tree.  This
// allows the binary tree to be maintained without any additional
// storage (the free chunks are used).  In a binary tree the first
// chunk in the free list is also the tree node.  Note that the
// TreeChunk has an embedded TreeList for this purpose.  Because
// the first chunk in the list is distinguished in this fashion
// (also is the node in the tree), it is the last chunk to be found
// on the free list for a node in the tree and is only removed if
// it is the last chunk on the free list.

template <class Chunk_t, template <class> class FreeList_t>
class TreeChunk : public Chunk_t {
  friend class TreeList<Chunk_t, FreeList_t>;
  TreeList<Chunk_t, FreeList_t>* _list;
  TreeList<Chunk_t, FreeList_t> _embedded_list;  // if non-null, this chunk is on _list

  static size_t _min_tree_chunk_size;

 protected:
  TreeList<Chunk_t, FreeList_t>* embedded_list() const { return (TreeList<Chunk_t, FreeList_t>*) &_embedded_list; }
  void set_embedded_list(TreeList<Chunk_t, FreeList_t>* v) { _embedded_list = *v; }
 public:
  TreeList<Chunk_t, FreeList_t>* list() { return _list; }
  void set_list(TreeList<Chunk_t, FreeList_t>* v) { _list = v; }
  static TreeChunk<Chunk_t, FreeList_t>* as_TreeChunk(Chunk_t* fc);
  // Initialize fields in a TreeChunk that should be
  // initialized when the TreeChunk is being added to
  // a free list in the tree.
  void initialize() { embedded_list()->initialize(); }

  Chunk_t* next() const { return Chunk_t::next(); }
  Chunk_t* prev() const { return Chunk_t::prev(); }
  size_t size() const volatile { return Chunk_t::size(); }

  static size_t min_size() {
    return _min_tree_chunk_size;
  }

  // debugging
  void verify_tree_chunk_list() const;
  void assert_is_mangled() const;
};


template <class Chunk_t, template <class> class FreeList_t>
class BinaryTreeDictionary: public FreeBlockDictionary<Chunk_t> {
  friend class VMStructs;
  size_t     _total_size;
  size_t     _total_free_blocks;
  TreeList<Chunk_t, FreeList_t>* _root;

  // private accessors
  void set_total_size(size_t v) { _total_size = v; }
  virtual void inc_total_size(size_t v);
  virtual void dec_total_size(size_t v);
  void set_total_free_blocks(size_t v) { _total_free_blocks = v; }
  TreeList<Chunk_t, FreeList_t>* root() const { return _root; }
  void set_root(TreeList<Chunk_t, FreeList_t>* v) { _root = v; }

  // This field is added and can be set to point to the
  // the Mutex used to synchronize access to the
  // dictionary so that assertion checking can be done.
  // For example it is set to point to _parDictionaryAllocLock.
  NOT_PRODUCT(Mutex* _lock;)

  // Remove a chunk of size "size" or larger from the tree and
  // return it.  If the chunk
  // is the last chunk of that size, remove the node for that size
  // from the tree.
  TreeChunk<Chunk_t, FreeList_t>* get_chunk_from_tree(size_t size, enum FreeBlockDictionary<Chunk_t>::Dither dither);
  // Remove this chunk from the tree.  If the removal results
  // in an empty list in the tree, remove the empty list.
  TreeChunk<Chunk_t, FreeList_t>* remove_chunk_from_tree(TreeChunk<Chunk_t, FreeList_t>* tc);
  // Remove the node in the trees starting at tl that has the
  // minimum value and return it.  Repair the tree as needed.
  TreeList<Chunk_t, FreeList_t>* remove_tree_minimum(TreeList<Chunk_t, FreeList_t>* tl);
  // Add this free chunk to the tree.
  void       insert_chunk_in_tree(Chunk_t* freeChunk);
 public:

  // Return a list of the specified size or NULL from the tree.
  // The list is not removed from the tree.
  TreeList<Chunk_t, FreeList_t>* find_list (size_t size) const;

  void       verify_tree() const;
  // verify that the given chunk is in the tree.
  bool       verify_chunk_in_free_list(Chunk_t* tc) const;
 private:
  void          verify_tree_helper(TreeList<Chunk_t, FreeList_t>* tl) const;
  static size_t verify_prev_free_ptrs(TreeList<Chunk_t, FreeList_t>* tl);

  // Returns the total number of chunks in the list.
  size_t     total_list_length(TreeList<Chunk_t, FreeList_t>* tl) const;
  // Returns the total number of words in the chunks in the tree
  // starting at "tl".
  size_t     total_size_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const;
  // Returns the sum of the square of the size of each block
  // in the tree starting at "tl".
  double     sum_of_squared_block_sizes(TreeList<Chunk_t, FreeList_t>* const tl) const;
  // Returns the total number of free blocks in the tree starting
  // at "tl".
  size_t     total_free_blocks_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const;
  size_t     num_free_blocks()  const;
  size_t     tree_height() const;
  size_t     tree_height_helper(TreeList<Chunk_t, FreeList_t>* tl) const;
  size_t     total_nodes_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const;
  size_t     total_nodes_helper(TreeList<Chunk_t, FreeList_t>* tl) const;

 public:
  // Constructor
  BinaryTreeDictionary() :
    _total_size(0), _total_free_blocks(0), _root(0) {}

  BinaryTreeDictionary(MemRegion mr);

  // Public accessors
  size_t total_size() const { return _total_size; }
  size_t total_free_blocks() const { return _total_free_blocks; }

  // Reset the dictionary to the initial conditions with
  // a single free chunk.
  void       reset(MemRegion mr);
  void       reset(HeapWord* addr, size_t size);
  // Reset the dictionary to be empty.
  void       reset();

  // Return a chunk of size "size" or greater from
  // the tree.
  Chunk_t* get_chunk(size_t size, enum FreeBlockDictionary<Chunk_t>::Dither dither) {
    FreeBlockDictionary<Chunk_t>::verify_par_locked();
    Chunk_t* res = get_chunk_from_tree(size, dither);
    assert(res == NULL || res->is_free(),
           "Should be returning a free chunk");
    assert(dither != FreeBlockDictionary<Chunk_t>::exactly ||
           res == NULL || res->size() == size, "Not correct size");
    return res;
  }

  void return_chunk(Chunk_t* chunk) {
    FreeBlockDictionary<Chunk_t>::verify_par_locked();
    insert_chunk_in_tree(chunk);
  }

  void remove_chunk(Chunk_t* chunk) {
    FreeBlockDictionary<Chunk_t>::verify_par_locked();
    remove_chunk_from_tree((TreeChunk<Chunk_t, FreeList_t>*)chunk);
    assert(chunk->is_free(), "Should still be a free chunk");
  }

  size_t     max_chunk_size() const;
  size_t     total_chunk_size(debug_only(const Mutex* lock)) const {
    debug_only(
      if (lock != NULL && lock->owned_by_self()) {
        assert(total_size_in_tree(root()) == total_size(),
               "_total_size inconsistency");
      }
    )
    return total_size();
  }

  size_t     min_size() const {
    return TreeChunk<Chunk_t, FreeList_t>::min_size();
  }

  double     sum_of_squared_block_sizes() const {
    return sum_of_squared_block_sizes(root());
  }

  Chunk_t* find_chunk_ends_at(HeapWord* target) const;

  // Find the list with size "size" in the binary tree and update
  // the statistics in the list according to "split" (chunk was
  // split or coalesce) and "birth" (chunk was added or removed).
  void       dict_census_update(size_t size, bool split, bool birth);
  // Return true if the dictionary is overpopulated (more chunks of
  // this size than desired) for size "size".
  bool       coal_dict_over_populated(size_t size);
  // Methods called at the beginning of a sweep to prepare the
  // statistics for the sweep.
  void       begin_sweep_dict_census(double coalSurplusPercent,
                                  float inter_sweep_current,
                                  float inter_sweep_estimate,
                                  float intra_sweep_estimate);
  // Methods called after the end of a sweep to modify the
  // statistics for the sweep.
  void       end_sweep_dict_census(double splitSurplusPercent);
  // Return the largest free chunk in the tree.
  Chunk_t* find_largest_dict() const;
  // Accessors for statistics
  void       set_tree_surplus(double splitSurplusPercent);
  void       set_tree_hints(void);
  // Reset statistics for all the lists in the tree.
  void       clear_tree_census(void);
  // Print the statistcis for all the lists in the tree.  Also may
  // print out summaries.
  void       print_dict_census(void) const;
  void       print_free_lists(outputStream* st) const;

  // For debugging.  Returns the sum of the _returned_bytes for
  // all lists in the tree.
  size_t     sum_dict_returned_bytes()     PRODUCT_RETURN0;
  // Sets the _returned_bytes for all the lists in the tree to zero.
  void       initialize_dict_returned_bytes()      PRODUCT_RETURN;
  // For debugging.  Return the total number of chunks in the dictionary.
  size_t     total_count()       PRODUCT_RETURN0;

  void       report_statistics() const;

  void       verify() const;
};

#endif // SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP