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
39 template <class Chunk_t, class FreeList_t> class TreeChunk;
40 template <class Chunk_t, class FreeList_t> class BinaryTreeDictionary;
41 template <class Chunk_t, class FreeList_t> class AscendTreeCensusClosure;
42 template <class Chunk_t, class FreeList_t> class DescendTreeCensusClosure;
43 template <class Chunk_t, class FreeList_t> class DescendTreeSearchClosure;
44
45 template <class Chunk_t, class FreeList_t>
46 class TreeList : public FreeList_t {
47 friend class TreeChunk<Chunk_t, FreeList_t>;
48 friend class BinaryTreeDictionary<Chunk_t, FreeList_t>;
49 friend class AscendTreeCensusClosure<Chunk_t, FreeList_t>;
50 friend class DescendTreeCensusClosure<Chunk_t, FreeList_t>;
51 friend class DescendTreeSearchClosure<Chunk_t, FreeList_t>;
52
53 TreeList<Chunk_t, FreeList_t>* _parent;
54 TreeList<Chunk_t, FreeList_t>* _left;
55 TreeList<Chunk_t, FreeList_t>* _right;
56
57 protected:
58
59 TreeList<Chunk_t, FreeList_t>* parent() const { return _parent; }
60 TreeList<Chunk_t, FreeList_t>* left() const { return _left; }
61 TreeList<Chunk_t, FreeList_t>* right() const { return _right; }
62
63 // Wrapper on call to base class, to get the template to compile.
64 Chunk_t* head() const { return FreeList_t::head(); }
65 Chunk_t* tail() const { return FreeList_t::tail(); }
66 void set_head(Chunk_t* head) { FreeList_t::set_head(head); }
67 void set_tail(Chunk_t* tail) { FreeList_t::set_tail(tail); }
68
69 size_t size() const { return FreeList_t::size(); }
70
71 // Accessors for links in tree.
72
73 void set_left(TreeList<Chunk_t, FreeList_t>* tl) {
74 _left = tl;
75 if (tl != NULL)
76 tl->set_parent(this);
77 }
78 void set_right(TreeList<Chunk_t, FreeList_t>* tl) {
79 _right = tl;
80 if (tl != NULL)
81 tl->set_parent(this);
82 }
83 void set_parent(TreeList<Chunk_t, FreeList_t>* tl) { _parent = tl; }
84
85 void clear_left() { _left = NULL; }
86 void clear_right() { _right = NULL; }
87 void clear_parent() { _parent = NULL; }
88 void initialize() { clear_left(); clear_right(), clear_parent(); FreeList_t::initialize(); }
89
90 // For constructing a TreeList from a Tree chunk or
91 // address and size.
92 TreeList();
93 static TreeList<Chunk_t, FreeList_t>*
94 as_TreeList(TreeChunk<Chunk_t, FreeList_t>* tc);
95 static TreeList<Chunk_t, FreeList_t>* as_TreeList(HeapWord* addr, size_t size);
96
97 // Returns the head of the free list as a pointer to a TreeChunk.
98 TreeChunk<Chunk_t, FreeList_t>* head_as_TreeChunk();
99
100 // Returns the first available chunk in the free list as a pointer
101 // to a TreeChunk.
102 TreeChunk<Chunk_t, FreeList_t>* first_available();
103
104 // Returns the block with the largest heap address amongst
105 // those in the list for this size; potentially slow and expensive,
106 // use with caution!
107 TreeChunk<Chunk_t, FreeList_t>* largest_address();
108
109 TreeList<Chunk_t, FreeList_t>* get_better_list(
110 BinaryTreeDictionary<Chunk_t, FreeList_t>* dictionary);
111
112 // remove_chunk_replace_if_needed() removes the given "tc" from the TreeList.
113 // If "tc" is the first chunk in the list, it is also the
114 // TreeList that is the node in the tree. remove_chunk_replace_if_needed()
115 // returns the possibly replaced TreeList* for the node in
116 // the tree. It also updates the parent of the original
117 // node to point to the new node.
118 TreeList<Chunk_t, FreeList_t>* remove_chunk_replace_if_needed(TreeChunk<Chunk_t, FreeList_t>* tc);
119 // See FreeList.
120 void return_chunk_at_head(TreeChunk<Chunk_t, FreeList_t>* tc);
121 void return_chunk_at_tail(TreeChunk<Chunk_t, FreeList_t>* tc);
122 };
123
124 // A TreeChunk is a subclass of a Chunk that additionally
125 // maintains a pointer to the free list on which it is currently
126 // linked.
127 // A TreeChunk is also used as a node in the binary tree. This
128 // allows the binary tree to be maintained without any additional
129 // storage (the free chunks are used). In a binary tree the first
130 // chunk in the free list is also the tree node. Note that the
131 // TreeChunk has an embedded TreeList for this purpose. Because
132 // the first chunk in the list is distinguished in this fashion
133 // (also is the node in the tree), it is the last chunk to be found
134 // on the free list for a node in the tree and is only removed if
135 // it is the last chunk on the free list.
136
137 template <class Chunk_t, class FreeList_t>
138 class TreeChunk : public Chunk_t {
139 friend class TreeList<Chunk_t, FreeList_t>;
140 TreeList<Chunk_t, FreeList_t>* _list;
141 TreeList<Chunk_t, FreeList_t> _embedded_list; // if non-null, this chunk is on _list
142
143 static size_t _min_tree_chunk_size;
144
145 protected:
146 TreeList<Chunk_t, FreeList_t>* embedded_list() const { return (TreeList<Chunk_t, FreeList_t>*) &_embedded_list; }
147 void set_embedded_list(TreeList<Chunk_t, FreeList_t>* v) { _embedded_list = *v; }
148 public:
149 TreeList<Chunk_t, FreeList_t>* list() { return _list; }
150 void set_list(TreeList<Chunk_t, FreeList_t>* v) { _list = v; }
151 static TreeChunk<Chunk_t, FreeList_t>* as_TreeChunk(Chunk_t* fc);
152 // Initialize fields in a TreeChunk that should be
153 // initialized when the TreeChunk is being added to
154 // a free list in the tree.
155 void initialize() { embedded_list()->initialize(); }
156
157 Chunk_t* next() const { return Chunk_t::next(); }
158 Chunk_t* prev() const { return Chunk_t::prev(); }
159 size_t size() const volatile { return Chunk_t::size(); }
160
161 static size_t min_size();
162
163 // debugging
164 void verify_tree_chunk_list() const;
165 void assert_is_mangled() const;
166 };
167
168 template <class Chunk_t, class FreeList_t>
169 size_t TreeChunk<Chunk_t, FreeList_t>::_min_tree_chunk_size = sizeof(TreeChunk<Chunk_t, FreeList_t>)/HeapWordSize;
170 template <class Chunk_t, class FreeList_t>
171 size_t TreeChunk<Chunk_t, FreeList_t>::min_size() { return _min_tree_chunk_size; }
172
173 template <class Chunk_t, class FreeList_t>
174 class BinaryTreeDictionary: public CHeapObj<mtGC> {
175 friend class VMStructs;
176
177 protected:
178 size_t _total_size;
179 size_t _total_free_blocks;
180 TreeList<Chunk_t, FreeList_t>* _root;
181
182 // private accessors
183 void set_total_size(size_t v) { _total_size = v; }
184 void inc_total_size(size_t v);
185 void dec_total_size(size_t v);
186 void set_total_free_blocks(size_t v) { _total_free_blocks = v; }
187 TreeList<Chunk_t, FreeList_t>* root() const { return _root; }
188 void set_root(TreeList<Chunk_t, FreeList_t>* v) { _root = v; }
189
190 // This field is added and can be set to point to the
191 // the Mutex used to synchronize access to the
192 // dictionary so that assertion checking can be done.
193 // For example it is set to point to _parDictionaryAllocLock.
194 NOT_PRODUCT(Mutex* _lock;)
195
196 // Remove a chunk of size "size" or larger from the tree and
197 // return it. If the chunk
198 // is the last chunk of that size, remove the node for that size
199 // from the tree.
200 TreeChunk<Chunk_t, FreeList_t>* get_chunk_from_tree(size_t size);
201 // Remove this chunk from the tree. If the removal results
202 // in an empty list in the tree, remove the empty list.
203 TreeChunk<Chunk_t, FreeList_t>* remove_chunk_from_tree(TreeChunk<Chunk_t, FreeList_t>* tc);
204 // Remove the node in the trees starting at tl that has the
205 // minimum value and return it. Repair the tree as needed.
206 TreeList<Chunk_t, FreeList_t>* remove_tree_minimum(TreeList<Chunk_t, FreeList_t>* tl);
207 // Add this free chunk to the tree.
208 void insert_chunk_in_tree(Chunk_t* freeChunk);
209 public:
210
211 // Return a list of the specified size or NULL from the tree.
212 // The list is not removed from the tree.
213 TreeList<Chunk_t, FreeList_t>* find_list (size_t size) const;
214
215 void verify_tree() const;
216 // verify that the given chunk is in the tree.
217 bool verify_chunk_in_free_list(Chunk_t* tc) const;
218 private:
219 void verify_tree_helper(TreeList<Chunk_t, FreeList_t>* tl) const;
220 static size_t verify_prev_free_ptrs(TreeList<Chunk_t, FreeList_t>* tl);
221
222 // Returns the total number of chunks in the list.
223 size_t total_list_length(TreeList<Chunk_t, FreeList_t>* tl) const;
224 // Returns the total number of words in the chunks in the tree
225 // starting at "tl".
226 size_t total_size_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const;
227 // Returns the sum of the square of the size of each block
228 // in the tree starting at "tl".
229 double sum_of_squared_block_sizes(TreeList<Chunk_t, FreeList_t>* const tl) const;
230 // Returns the total number of free blocks in the tree starting
231 // at "tl".
232 size_t total_free_blocks_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const;
233 size_t num_free_blocks() const;
234 size_t tree_height() const;
235 size_t tree_height_helper(TreeList<Chunk_t, FreeList_t>* tl) const;
236 size_t total_nodes_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const;
237 size_t total_nodes_helper(TreeList<Chunk_t, FreeList_t>* tl) const;
238
239 public:
240 // Constructor
241 BinaryTreeDictionary() :
242 _total_size(0), _total_free_blocks(0), _root(0) {}
243
244 BinaryTreeDictionary(MemRegion mr);
245
246 // Public accessors
247 size_t total_size() const { return _total_size; }
248 size_t total_free_blocks() const { return _total_free_blocks; }
249
250 // Reset the dictionary to the initial conditions with
251 // a single free chunk.
252 void reset(MemRegion mr);
253 void reset(HeapWord* addr, size_t size);
254 // Reset the dictionary to be empty.
255 void reset();
256
257 // Return a chunk of size "size" or greater from
258 // the tree.
259 Chunk_t* get_chunk(size_t size) {
260 verify_par_locked();
261 Chunk_t* res = get_chunk_from_tree(size);
262 assert(res == NULL || res->is_free(),
263 "Should be returning a free chunk");
264 return res;
265 }
266
267 void return_chunk(Chunk_t* chunk) {
268 verify_par_locked();
269 insert_chunk_in_tree(chunk);
270 }
271
272 void remove_chunk(Chunk_t* chunk) {
273 verify_par_locked();
274 remove_chunk_from_tree((TreeChunk<Chunk_t, FreeList_t>*)chunk);
275 assert(chunk->is_free(), "Should still be a free chunk");
276 }
277
278 size_t max_chunk_size() const;
279 size_t total_chunk_size(debug_only(const Mutex* lock)) const {
280 debug_only(
281 if (lock != NULL && lock->owned_by_self()) {
282 assert(total_size_in_tree(root()) == total_size(),
283 "_total_size inconsistency");
284 }
285 )
286 return total_size();
287 }
288
289 size_t min_size() const {
290 return TreeChunk<Chunk_t, FreeList_t>::min_size();
291 }
292
293 double sum_of_squared_block_sizes() const {
294 return sum_of_squared_block_sizes(root());
295 }
296
297 Chunk_t* find_chunk_ends_at(HeapWord* target) const;
298
299 // Return the largest free chunk in the tree.
300 Chunk_t* find_largest_dict() const;
301
302 void print_free_lists(outputStream* st) const;
303
304 // For debugging. Returns the sum of the _returned_bytes for
305 // all lists in the tree.
306 size_t sum_dict_returned_bytes() PRODUCT_RETURN0;
307 // Sets the _returned_bytes for all the lists in the tree to zero.
308 void initialize_dict_returned_bytes() PRODUCT_RETURN;
309 // For debugging. Return the total number of chunks in the dictionary.
310 size_t total_count() PRODUCT_RETURN0;
311
312 void report_statistics(outputStream* st) const;
313
314 void verify() const;
315
316 Mutex* par_lock() const PRODUCT_RETURN0;
317 void set_par_lock(Mutex* lock) PRODUCT_RETURN;
318 void verify_par_locked() const PRODUCT_RETURN;
319 };
320
321
322 // Closures for walking the binary tree.
323 // do_list() walks the free list in a node applying the closure
324 // to each free chunk in the list
325 // do_tree() walks the nodes in the binary tree applying do_list()
326 // to each list at each node.
327
328 template <class Chunk_t, class FreeList_t>
329 class TreeCensusClosure : public StackObj {
330 protected:
331 virtual void do_list(FreeList_t* fl) = 0;
332 public:
333 virtual void do_tree(TreeList<Chunk_t, FreeList_t>* tl) = 0;
334 };
335
336 template <class Chunk_t, class FreeList_t>
337 class AscendTreeCensusClosure : public TreeCensusClosure<Chunk_t, FreeList_t> {
338 public:
339 void do_tree(TreeList<Chunk_t, FreeList_t>* tl) {
340 if (tl != NULL) {
341 do_tree(tl->left());
342 this->do_list(tl);
343 do_tree(tl->right());
344 }
345 }
346 };
347
348 template <class Chunk_t, class FreeList_t>
349 class DescendTreeCensusClosure : public TreeCensusClosure<Chunk_t, FreeList_t> {
350 public:
351 void do_tree(TreeList<Chunk_t, FreeList_t>* tl) {
352 if (tl != NULL) {
353 do_tree(tl->right());
354 this->do_list(tl);
355 do_tree(tl->left());
356 }
357 }
358 };
359
360 // Used to search the tree until a condition is met.
361 // Similar to TreeCensusClosure but searches the
362 // tree and returns promptly when found.
363
364 template <class Chunk_t, class FreeList_t>
365 class TreeSearchClosure : public StackObj {
366 protected:
367 virtual bool do_list(FreeList_t* fl) = 0;
368 public:
369 virtual bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) = 0;
370 };
371
372 #if 0 // Don't need this yet but here for symmetry.
373 template <class Chunk_t, class FreeList_t>
374 class AscendTreeSearchClosure : public TreeSearchClosure<Chunk_t> {
375 public:
376 bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) {
377 if (tl != NULL) {
378 if (do_tree(tl->left())) return true;
379 if (do_list(tl)) return true;
380 if (do_tree(tl->right())) return true;
381 }
382 return false;
383 }
384 };
385 #endif
386
387 template <class Chunk_t, class FreeList_t>
388 class DescendTreeSearchClosure : public TreeSearchClosure<Chunk_t, FreeList_t> {
389 public:
390 bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) {
391 if (tl != NULL) {
392 if (do_tree(tl->right())) return true;
393 if (this->do_list(tl)) return true;
394 if (do_tree(tl->left())) return true;
395 }
396 return false;
397 }
398 };
399
400 #endif // SHARE_VM_MEMORY_BINARYTREEDICTIONARY_HPP