1/*
2 * Copyright (c) 2001, 2019, 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_MEMORY_BINARYTREEDICTIONARY_HPP
26#define SHARE_MEMORY_BINARYTREEDICTIONARY_HPP
27
28#include "memory/freeList.hpp"
29#include "memory/memRegion.hpp"
30
31class Mutex;
32
33/*
34 * A binary tree based search structure for free blocks.
35 * This is currently used in the Concurrent Mark&Sweep implementation, but
36 * will be used for free block management for metadata.
37 */
38
39// A TreeList is a FreeList which can be used to maintain a
40// binary tree of free lists.
41
42template <class Chunk_t, class FreeList_t> class TreeChunk;
43template <class Chunk_t, class FreeList_t> class BinaryTreeDictionary;
44template <class Chunk_t, class FreeList_t> class AscendTreeCensusClosure;
45template <class Chunk_t, class FreeList_t> class DescendTreeCensusClosure;
46template <class Chunk_t, class FreeList_t> class DescendTreeSearchClosure;
47
48template <class Chunk_t, class FreeList_t>
49class TreeList : public FreeList_t {
50 friend class TreeChunk<Chunk_t, FreeList_t>;
51 friend class BinaryTreeDictionary<Chunk_t, FreeList_t>;
52 friend class AscendTreeCensusClosure<Chunk_t, FreeList_t>;
53 friend class DescendTreeCensusClosure<Chunk_t, FreeList_t>;
54 friend class DescendTreeSearchClosure<Chunk_t, FreeList_t>;
55
56 TreeList<Chunk_t, FreeList_t>* _parent;
57 TreeList<Chunk_t, FreeList_t>* _left;
58 TreeList<Chunk_t, FreeList_t>* _right;
59
60 protected:
61
62 TreeList<Chunk_t, FreeList_t>* parent() const { return _parent; }
63 TreeList<Chunk_t, FreeList_t>* left() const { return _left; }
64 TreeList<Chunk_t, FreeList_t>* right() const { return _right; }
65
66 // Wrapper on call to base class, to get the template to compile.
67 Chunk_t* head() const { return FreeList_t::head(); }
68 Chunk_t* tail() const { return FreeList_t::tail(); }
69 void set_head(Chunk_t* head) { FreeList_t::set_head(head); }
70 void set_tail(Chunk_t* tail) { FreeList_t::set_tail(tail); }
71
72 size_t size() const { return FreeList_t::size(); }
73
74 // Accessors for links in tree.
75
76 void set_left(TreeList<Chunk_t, FreeList_t>* tl) {
77 _left = tl;
78 if (tl != NULL)
79 tl->set_parent(this);
80 }
81 void set_right(TreeList<Chunk_t, FreeList_t>* tl) {
82 _right = tl;
83 if (tl != NULL)
84 tl->set_parent(this);
85 }
86 void set_parent(TreeList<Chunk_t, FreeList_t>* tl) { _parent = tl; }
87
88 void clear_left() { _left = NULL; }
89 void clear_right() { _right = NULL; }
90 void clear_parent() { _parent = NULL; }
91 void initialize() { clear_left(); clear_right(), clear_parent(); FreeList_t::initialize(); }
92
93 // For constructing a TreeList from a Tree chunk or
94 // address and size.
95 TreeList();
96 static TreeList<Chunk_t, FreeList_t>*
97 as_TreeList(TreeChunk<Chunk_t, FreeList_t>* tc);
98 static TreeList<Chunk_t, FreeList_t>* as_TreeList(HeapWord* addr, size_t size);
99
100 // Returns the head of the free list as a pointer to a TreeChunk.
101 TreeChunk<Chunk_t, FreeList_t>* head_as_TreeChunk();
102
103 // Returns the first available chunk in the free list as a pointer
104 // to a TreeChunk.
105 TreeChunk<Chunk_t, FreeList_t>* first_available();
106
107 // Returns the block with the largest heap address amongst
108 // those in the list for this size; potentially slow and expensive,
109 // use with caution!
110 TreeChunk<Chunk_t, FreeList_t>* largest_address();
111
112 TreeList<Chunk_t, FreeList_t>* get_better_list(
113 BinaryTreeDictionary<Chunk_t, FreeList_t>* dictionary);
114
115 // remove_chunk_replace_if_needed() removes the given "tc" from the TreeList.
116 // If "tc" is the first chunk in the list, it is also the
117 // TreeList that is the node in the tree. remove_chunk_replace_if_needed()
118 // returns the possibly replaced TreeList* for the node in
119 // the tree. It also updates the parent of the original
120 // node to point to the new node.
121 TreeList<Chunk_t, FreeList_t>* remove_chunk_replace_if_needed(TreeChunk<Chunk_t, FreeList_t>* tc);
122 // See FreeList.
123 void return_chunk_at_tail(TreeChunk<Chunk_t, FreeList_t>* tc);
124};
125
126// A TreeChunk is a subclass of a Chunk that additionally
127// maintains a pointer to the free list on which it is currently
128// linked.
129// A TreeChunk is also used as a node in the binary tree. This
130// allows the binary tree to be maintained without any additional
131// storage (the free chunks are used). In a binary tree the first
132// chunk in the free list is also the tree node. Note that the
133// TreeChunk has an embedded TreeList for this purpose. Because
134// the first chunk in the list is distinguished in this fashion
135// (also is the node in the tree), it is the last chunk to be found
136// on the free list for a node in the tree and is only removed if
137// it is the last chunk on the free list.
138
139template <class Chunk_t, class FreeList_t>
140class TreeChunk : public Chunk_t {
141 friend class TreeList<Chunk_t, FreeList_t>;
142 TreeList<Chunk_t, FreeList_t>* _list;
143 TreeList<Chunk_t, FreeList_t> _embedded_list; // if non-null, this chunk is on _list
144
145 static size_t _min_tree_chunk_size;
146
147 protected:
148 TreeList<Chunk_t, FreeList_t>* embedded_list() const { return (TreeList<Chunk_t, FreeList_t>*) &_embedded_list; }
149 void set_embedded_list(TreeList<Chunk_t, FreeList_t>* v) { _embedded_list = *v; }
150 public:
151 TreeList<Chunk_t, FreeList_t>* list() { return _list; }
152 void set_list(TreeList<Chunk_t, FreeList_t>* v) { _list = v; }
153 static TreeChunk<Chunk_t, FreeList_t>* as_TreeChunk(Chunk_t* fc);
154 // Initialize fields in a TreeChunk that should be
155 // initialized when the TreeChunk is being added to
156 // a free list in the tree.
157 void initialize() { embedded_list()->initialize(); }
158
159 Chunk_t* next() const { return Chunk_t::next(); }
160 Chunk_t* prev() const { return Chunk_t::prev(); }
161 size_t size() const volatile { return Chunk_t::size(); }
162
163 static size_t min_size();
164
165 // debugging
166 void verify_tree_chunk_list() const;
167 void assert_is_mangled() const;
168};
169
170template <class Chunk_t, class FreeList_t>
171size_t TreeChunk<Chunk_t, FreeList_t>::_min_tree_chunk_size = sizeof(TreeChunk<Chunk_t, FreeList_t>)/HeapWordSize;
172template <class Chunk_t, class FreeList_t>
173size_t TreeChunk<Chunk_t, FreeList_t>::min_size() { return _min_tree_chunk_size; }
174
175template <class Chunk_t, class FreeList_t>
176class BinaryTreeDictionary: public CHeapObj<mtGC> {
177 friend class VMStructs;
178
179 protected:
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_helper(TreeList<Chunk_t, FreeList_t>* tl) const;
239
240 public:
241 // Constructor
242 BinaryTreeDictionary() :
243 _total_size(0), _total_free_blocks(0), _root(0) {}
244
245 BinaryTreeDictionary(MemRegion mr);
246
247 // Public accessors
248 size_t total_size() const { return _total_size; }
249 size_t total_free_blocks() const { return _total_free_blocks; }
250
251 // Reset the dictionary to the initial conditions with
252 // a single free chunk.
253 void reset(MemRegion mr);
254 void reset(HeapWord* addr, size_t size);
255 // Reset the dictionary to be empty.
256 void reset();
257
258 // Return a chunk of size "size" or greater from
259 // the tree.
260 Chunk_t* get_chunk(size_t size) {
261 verify_par_locked();
262 Chunk_t* res = get_chunk_from_tree(size);
263 assert(res == NULL || res->is_free(),
264 "Should be returning a free chunk");
265 return res;
266 }
267
268 void return_chunk(Chunk_t* chunk) {
269 verify_par_locked();
270 insert_chunk_in_tree(chunk);
271 }
272
273 void remove_chunk(Chunk_t* chunk) {
274 verify_par_locked();
275 remove_chunk_from_tree((TreeChunk<Chunk_t, FreeList_t>*)chunk);
276 assert(chunk->is_free(), "Should still be a free chunk");
277 }
278
279 size_t max_chunk_size() const;
280 inline size_t total_chunk_size(debug_only(const Mutex* lock)) const;
281
282 size_t min_size() const {
283 return TreeChunk<Chunk_t, FreeList_t>::min_size();
284 }
285
286 double sum_of_squared_block_sizes() const {
287 return sum_of_squared_block_sizes(root());
288 }
289
290 Chunk_t* find_chunk_ends_at(HeapWord* target) const;
291
292 // Return the largest free chunk in the tree.
293 Chunk_t* find_largest_dict() const;
294
295 void print_free_lists(outputStream* st) const;
296
297 // For debugging. Returns the sum of the _returned_bytes for
298 // all lists in the tree.
299 size_t sum_dict_returned_bytes() PRODUCT_RETURN0;
300 // Sets the _returned_bytes for all the lists in the tree to zero.
301 void initialize_dict_returned_bytes() PRODUCT_RETURN;
302 // For debugging. Return the total number of chunks in the dictionary.
303 size_t total_count() PRODUCT_RETURN0;
304
305 void report_statistics(outputStream* st) const;
306
307 void verify() const;
308
309 Mutex* par_lock() const PRODUCT_RETURN0;
310 void set_par_lock(Mutex* lock) PRODUCT_RETURN;
311 void verify_par_locked() const PRODUCT_RETURN;
312};
313
314
315// Closures for walking the binary tree.
316// do_list() walks the free list in a node applying the closure
317// to each free chunk in the list
318// do_tree() walks the nodes in the binary tree applying do_list()
319// to each list at each node.
320
321template <class Chunk_t, class FreeList_t>
322class TreeCensusClosure : public StackObj {
323 protected:
324 virtual void do_list(FreeList_t* fl) = 0;
325 public:
326 virtual void do_tree(TreeList<Chunk_t, FreeList_t>* tl) = 0;
327};
328
329template <class Chunk_t, class FreeList_t>
330class AscendTreeCensusClosure : public TreeCensusClosure<Chunk_t, FreeList_t> {
331 public:
332 void do_tree(TreeList<Chunk_t, FreeList_t>* tl) {
333 if (tl != NULL) {
334 do_tree(tl->left());
335 this->do_list(tl);
336 do_tree(tl->right());
337 }
338 }
339};
340
341template <class Chunk_t, class FreeList_t>
342class DescendTreeCensusClosure : public TreeCensusClosure<Chunk_t, FreeList_t> {
343 public:
344 void do_tree(TreeList<Chunk_t, FreeList_t>* tl) {
345 if (tl != NULL) {
346 do_tree(tl->right());
347 this->do_list(tl);
348 do_tree(tl->left());
349 }
350 }
351};
352
353// Used to search the tree until a condition is met.
354// Similar to TreeCensusClosure but searches the
355// tree and returns promptly when found.
356
357template <class Chunk_t, class FreeList_t>
358class TreeSearchClosure : public StackObj {
359 protected:
360 virtual bool do_list(FreeList_t* fl) = 0;
361 public:
362 virtual bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) = 0;
363};
364
365#if 0 // Don't need this yet but here for symmetry.
366template <class Chunk_t, class FreeList_t>
367class AscendTreeSearchClosure : public TreeSearchClosure<Chunk_t> {
368 public:
369 bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) {
370 if (tl != NULL) {
371 if (do_tree(tl->left())) return true;
372 if (do_list(tl)) return true;
373 if (do_tree(tl->right())) return true;
374 }
375 return false;
376 }
377};
378#endif
379
380template <class Chunk_t, class FreeList_t>
381class DescendTreeSearchClosure : public TreeSearchClosure<Chunk_t, FreeList_t> {
382 public:
383 bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) {
384 if (tl != NULL) {
385 if (do_tree(tl->right())) return true;
386 if (this->do_list(tl)) return true;
387 if (do_tree(tl->left())) return true;
388 }
389 return false;
390 }
391};
392
393#endif // SHARE_MEMORY_BINARYTREEDICTIONARY_HPP
394