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 #include "precompiled.hpp"
26 #include "gc/cms/allocationStats.hpp"
27 #include "gc/shared/spaceDecorator.hpp"
28 #include "logging/logStream.inline.hpp"
29 #include "memory/binaryTreeDictionary.hpp"
30 #include "memory/freeList.hpp"
31 #include "memory/metachunk.hpp"
32 #include "memory/resourceArea.hpp"
33 #include "runtime/globals.hpp"
34 #include "utilities/macros.hpp"
35 #include "utilities/ostream.hpp"
36 #if INCLUDE_ALL_GCS
37 #include "gc/cms/adaptiveFreeList.hpp"
38 #include "gc/cms/freeChunk.hpp"
39 #endif // INCLUDE_ALL_GCS
40
41 ////////////////////////////////////////////////////////////////////////////////
42 // A binary tree based search structure for free blocks.
43 // This is currently used in the Concurrent Mark&Sweep implementation.
44 ////////////////////////////////////////////////////////////////////////////////
45
46 template <class Chunk_t, class FreeList_t>
47 TreeChunk<Chunk_t, FreeList_t>* TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(Chunk_t* fc) {
48 // Do some assertion checking here.
49 return (TreeChunk<Chunk_t, FreeList_t>*) fc;
50 }
51
52 template <class Chunk_t, class FreeList_t>
53 void TreeChunk<Chunk_t, FreeList_t>::verify_tree_chunk_list() const {
54 TreeChunk<Chunk_t, FreeList_t>* nextTC = (TreeChunk<Chunk_t, FreeList_t>*)next();
55 if (prev() != NULL) { // interior list node shouldn't have tree fields
56 guarantee(embedded_list()->parent() == NULL && embedded_list()->left() == NULL &&
57 embedded_list()->right() == NULL, "should be clear");
58 }
59 if (nextTC != NULL) {
60 guarantee(as_TreeChunk(nextTC->prev()) == this, "broken chain");
61 guarantee(nextTC->size() == size(), "wrong size");
62 nextTC->verify_tree_chunk_list();
63 }
64 }
65
66 template <class Chunk_t, class FreeList_t>
67 TreeList<Chunk_t, FreeList_t>::TreeList() : _parent(NULL),
68 _left(NULL), _right(NULL) {}
69
70 template <class Chunk_t, class FreeList_t>
71 TreeList<Chunk_t, FreeList_t>*
72 TreeList<Chunk_t, FreeList_t>::as_TreeList(TreeChunk<Chunk_t,FreeList_t>* tc) {
73 // This first free chunk in the list will be the tree list.
74 assert((tc->size() >= (TreeChunk<Chunk_t, FreeList_t>::min_size())),
75 "Chunk is too small for a TreeChunk");
76 TreeList<Chunk_t, FreeList_t>* tl = tc->embedded_list();
77 tl->initialize();
78 tc->set_list(tl);
79 tl->set_size(tc->size());
80 tl->link_head(tc);
81 tl->link_tail(tc);
82 tl->set_count(1);
83 assert(tl->parent() == NULL, "Should be clear");
84 return tl;
85 }
86
87 template <class Chunk_t, class FreeList_t>
88 TreeList<Chunk_t, FreeList_t>*
89 TreeList<Chunk_t, FreeList_t>::as_TreeList(HeapWord* addr, size_t size) {
90 TreeChunk<Chunk_t, FreeList_t>* tc = (TreeChunk<Chunk_t, FreeList_t>*) addr;
91 assert((size >= TreeChunk<Chunk_t, FreeList_t>::min_size()),
92 "Chunk is too small for a TreeChunk");
93 // The space will have been mangled initially but
94 // is not remangled when a Chunk_t is returned to the free list
95 // (since it is used to maintain the chunk on the free list).
96 tc->assert_is_mangled();
97 tc->set_size(size);
98 tc->link_prev(NULL);
99 tc->link_next(NULL);
100 TreeList<Chunk_t, FreeList_t>* tl = TreeList<Chunk_t, FreeList_t>::as_TreeList(tc);
101 return tl;
102 }
103
104
105 #if INCLUDE_ALL_GCS
106 // Specialize for AdaptiveFreeList which tries to avoid
107 // splitting a chunk of a size that is under populated in favor of
108 // an over populated size. The general get_better_list() just returns
109 // the current list.
110 template <>
111 TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >*
112 TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >::get_better_list(
113 BinaryTreeDictionary<FreeChunk, ::AdaptiveFreeList<FreeChunk> >* dictionary) {
114 // A candidate chunk has been found. If it is already under
115 // populated, get a chunk associated with the hint for this
116 // chunk.
117
118 TreeList<FreeChunk, ::AdaptiveFreeList<FreeChunk> >* curTL = this;
119 if (curTL->surplus() <= 0) {
120 /* Use the hint to find a size with a surplus, and reset the hint. */
121 TreeList<FreeChunk, ::AdaptiveFreeList<FreeChunk> >* hintTL = this;
122 while (hintTL->hint() != 0) {
123 assert(hintTL->hint() > hintTL->size(),
124 "hint points in the wrong direction");
125 hintTL = dictionary->find_list(hintTL->hint());
126 assert(curTL != hintTL, "Infinite loop");
127 if (hintTL == NULL ||
128 hintTL == curTL /* Should not happen but protect against it */ ) {
129 // No useful hint. Set the hint to NULL and go on.
130 curTL->set_hint(0);
131 break;
132 }
133 assert(hintTL->size() > curTL->size(), "hint is inconsistent");
134 if (hintTL->surplus() > 0) {
135 // The hint led to a list that has a surplus. Use it.
136 // Set the hint for the candidate to an overpopulated
137 // size.
138 curTL->set_hint(hintTL->size());
139 // Change the candidate.
140 curTL = hintTL;
141 break;
142 }
143 }
144 }
145 return curTL;
146 }
147 #endif // INCLUDE_ALL_GCS
148
149 template <class Chunk_t, class FreeList_t>
150 TreeList<Chunk_t, FreeList_t>*
151 TreeList<Chunk_t, FreeList_t>::get_better_list(
152 BinaryTreeDictionary<Chunk_t, FreeList_t>* dictionary) {
153 return this;
154 }
155
156 template <class Chunk_t, class FreeList_t>
157 TreeList<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::remove_chunk_replace_if_needed(TreeChunk<Chunk_t, FreeList_t>* tc) {
158
159 TreeList<Chunk_t, FreeList_t>* retTL = this;
160 Chunk_t* list = head();
161 assert(!list || list != list->next(), "Chunk on list twice");
162 assert(tc != NULL, "Chunk being removed is NULL");
163 assert(parent() == NULL || this == parent()->left() ||
164 this == parent()->right(), "list is inconsistent");
165 assert(tc->is_free(), "Header is not marked correctly");
166 assert(head() == NULL || head()->prev() == NULL, "list invariant");
167 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
168
169 Chunk_t* prevFC = tc->prev();
170 TreeChunk<Chunk_t, FreeList_t>* nextTC = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(tc->next());
171 assert(list != NULL, "should have at least the target chunk");
172
173 // Is this the first item on the list?
174 if (tc == list) {
175 // The "getChunk..." functions for a TreeList<Chunk_t, FreeList_t> will not return the
176 // first chunk in the list unless it is the last chunk in the list
177 // because the first chunk is also acting as the tree node.
178 // When coalescing happens, however, the first chunk in the a tree
179 // list can be the start of a free range. Free ranges are removed
180 // from the free lists so that they are not available to be
181 // allocated when the sweeper yields (giving up the free list lock)
182 // to allow mutator activity. If this chunk is the first in the
183 // list and is not the last in the list, do the work to copy the
184 // TreeList<Chunk_t, FreeList_t> from the first chunk to the next chunk and update all
185 // the TreeList<Chunk_t, FreeList_t> pointers in the chunks in the list.
186 if (nextTC == NULL) {
187 assert(prevFC == NULL, "Not last chunk in the list");
188 set_tail(NULL);
189 set_head(NULL);
190 } else {
191 // copy embedded list.
192 nextTC->set_embedded_list(tc->embedded_list());
193 retTL = nextTC->embedded_list();
194 // Fix the pointer to the list in each chunk in the list.
195 // This can be slow for a long list. Consider having
196 // an option that does not allow the first chunk on the
197 // list to be coalesced.
198 for (TreeChunk<Chunk_t, FreeList_t>* curTC = nextTC; curTC != NULL;
199 curTC = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(curTC->next())) {
200 curTC->set_list(retTL);
201 }
202 // Fix the parent to point to the new TreeList<Chunk_t, FreeList_t>.
203 if (retTL->parent() != NULL) {
204 if (this == retTL->parent()->left()) {
205 retTL->parent()->set_left(retTL);
206 } else {
207 assert(this == retTL->parent()->right(), "Parent is incorrect");
208 retTL->parent()->set_right(retTL);
209 }
210 }
211 // Fix the children's parent pointers to point to the
212 // new list.
213 assert(right() == retTL->right(), "Should have been copied");
214 if (retTL->right() != NULL) {
215 retTL->right()->set_parent(retTL);
216 }
217 assert(left() == retTL->left(), "Should have been copied");
218 if (retTL->left() != NULL) {
219 retTL->left()->set_parent(retTL);
220 }
221 retTL->link_head(nextTC);
222 assert(nextTC->is_free(), "Should be a free chunk");
223 }
224 } else {
225 if (nextTC == NULL) {
226 // Removing chunk at tail of list
227 this->link_tail(prevFC);
228 }
229 // Chunk is interior to the list
230 prevFC->link_after(nextTC);
231 }
232
233 // Below this point the embedded TreeList<Chunk_t, FreeList_t> being used for the
234 // tree node may have changed. Don't use "this"
235 // TreeList<Chunk_t, FreeList_t>*.
236 // chunk should still be a free chunk (bit set in _prev)
237 assert(!retTL->head() || retTL->size() == retTL->head()->size(),
238 "Wrong sized chunk in list");
239 debug_only(
240 tc->link_prev(NULL);
241 tc->link_next(NULL);
242 tc->set_list(NULL);
243 bool prev_found = false;
244 bool next_found = false;
245 for (Chunk_t* curFC = retTL->head();
246 curFC != NULL; curFC = curFC->next()) {
247 assert(curFC != tc, "Chunk is still in list");
248 if (curFC == prevFC) {
249 prev_found = true;
250 }
251 if (curFC == nextTC) {
252 next_found = true;
253 }
254 }
255 assert(prevFC == NULL || prev_found, "Chunk was lost from list");
256 assert(nextTC == NULL || next_found, "Chunk was lost from list");
257 assert(retTL->parent() == NULL ||
258 retTL == retTL->parent()->left() ||
259 retTL == retTL->parent()->right(),
260 "list is inconsistent");
261 )
262 retTL->decrement_count();
263
264 assert(tc->is_free(), "Should still be a free chunk");
265 assert(retTL->head() == NULL || retTL->head()->prev() == NULL,
266 "list invariant");
267 assert(retTL->tail() == NULL || retTL->tail()->next() == NULL,
268 "list invariant");
269 return retTL;
270 }
271
272 template <class Chunk_t, class FreeList_t>
273 void TreeList<Chunk_t, FreeList_t>::return_chunk_at_tail(TreeChunk<Chunk_t, FreeList_t>* chunk) {
274 assert(chunk != NULL, "returning NULL chunk");
275 assert(chunk->list() == this, "list should be set for chunk");
276 assert(tail() != NULL, "The tree list is embedded in the first chunk");
277 // which means that the list can never be empty.
278 assert(!this->verify_chunk_in_free_list(chunk), "Double entry");
279 assert(head() == NULL || head()->prev() == NULL, "list invariant");
280 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
281
282 Chunk_t* fc = tail();
283 fc->link_after(chunk);
284 this->link_tail(chunk);
285
286 assert(!tail() || size() == tail()->size(), "Wrong sized chunk in list");
287 FreeList_t::increment_count();
288 debug_only(this->increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));)
289 assert(head() == NULL || head()->prev() == NULL, "list invariant");
290 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
291 }
292
293 // Add this chunk at the head of the list. "At the head of the list"
294 // is defined to be after the chunk pointer to by head(). This is
295 // because the TreeList<Chunk_t, FreeList_t> is embedded in the first TreeChunk<Chunk_t, FreeList_t> in the
296 // list. See the definition of TreeChunk<Chunk_t, FreeList_t>.
297 template <class Chunk_t, class FreeList_t>
298 void TreeList<Chunk_t, FreeList_t>::return_chunk_at_head(TreeChunk<Chunk_t, FreeList_t>* chunk) {
299 assert(chunk->list() == this, "list should be set for chunk");
300 assert(head() != NULL, "The tree list is embedded in the first chunk");
301 assert(chunk != NULL, "returning NULL chunk");
302 assert(!this->verify_chunk_in_free_list(chunk), "Double entry");
303 assert(head() == NULL || head()->prev() == NULL, "list invariant");
304 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
305
306 Chunk_t* fc = head()->next();
307 if (fc != NULL) {
308 chunk->link_after(fc);
309 } else {
310 assert(tail() == NULL, "List is inconsistent");
311 this->link_tail(chunk);
312 }
313 head()->link_after(chunk);
314 assert(!head() || size() == head()->size(), "Wrong sized chunk in list");
315 FreeList_t::increment_count();
316 debug_only(this->increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));)
317 assert(head() == NULL || head()->prev() == NULL, "list invariant");
318 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
319 }
320
321 template <class Chunk_t, class FreeList_t>
322 void TreeChunk<Chunk_t, FreeList_t>::assert_is_mangled() const {
323 assert((ZapUnusedHeapArea &&
324 SpaceMangler::is_mangled((HeapWord*) Chunk_t::size_addr()) &&
325 SpaceMangler::is_mangled((HeapWord*) Chunk_t::prev_addr()) &&
326 SpaceMangler::is_mangled((HeapWord*) Chunk_t::next_addr())) ||
327 (size() == 0 && prev() == NULL && next() == NULL),
328 "Space should be clear or mangled");
329 }
330
331 template <class Chunk_t, class FreeList_t>
332 TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::head_as_TreeChunk() {
333 assert(head() == NULL || (TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(head())->list() == this),
334 "Wrong type of chunk?");
335 return TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(head());
336 }
337
338 template <class Chunk_t, class FreeList_t>
339 TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::first_available() {
340 assert(head() != NULL, "The head of the list cannot be NULL");
341 Chunk_t* fc = head()->next();
342 TreeChunk<Chunk_t, FreeList_t>* retTC;
343 if (fc == NULL) {
344 retTC = head_as_TreeChunk();
345 } else {
346 retTC = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(fc);
347 }
348 assert(retTC->list() == this, "Wrong type of chunk.");
349 return retTC;
350 }
351
352 // Returns the block with the largest heap address amongst
353 // those in the list for this size; potentially slow and expensive,
354 // use with caution!
355 template <class Chunk_t, class FreeList_t>
356 TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::largest_address() {
357 assert(head() != NULL, "The head of the list cannot be NULL");
358 Chunk_t* fc = head()->next();
359 TreeChunk<Chunk_t, FreeList_t>* retTC;
360 if (fc == NULL) {
361 retTC = head_as_TreeChunk();
362 } else {
363 // walk down the list and return the one with the highest
364 // heap address among chunks of this size.
365 Chunk_t* last = fc;
366 while (fc->next() != NULL) {
367 if ((HeapWord*)last < (HeapWord*)fc) {
368 last = fc;
369 }
370 fc = fc->next();
371 }
372 retTC = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(last);
373 }
374 assert(retTC->list() == this, "Wrong type of chunk.");
375 return retTC;
376 }
377
378 template <class Chunk_t, class FreeList_t>
379 BinaryTreeDictionary<Chunk_t, FreeList_t>::BinaryTreeDictionary(MemRegion mr) {
380 assert((mr.byte_size() > min_size()), "minimum chunk size");
381
382 reset(mr);
383 assert(root()->left() == NULL, "reset check failed");
384 assert(root()->right() == NULL, "reset check failed");
385 assert(root()->head()->next() == NULL, "reset check failed");
386 assert(root()->head()->prev() == NULL, "reset check failed");
387 assert(total_size() == root()->size(), "reset check failed");
388 assert(total_free_blocks() == 1, "reset check failed");
389 }
390
391 template <class Chunk_t, class FreeList_t>
392 void BinaryTreeDictionary<Chunk_t, FreeList_t>::inc_total_size(size_t inc) {
393 _total_size = _total_size + inc;
394 }
395
396 template <class Chunk_t, class FreeList_t>
397 void BinaryTreeDictionary<Chunk_t, FreeList_t>::dec_total_size(size_t dec) {
398 _total_size = _total_size - dec;
399 }
400
401 template <class Chunk_t, class FreeList_t>
402 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset(MemRegion mr) {
403 assert((mr.byte_size() > min_size()), "minimum chunk size");
404 set_root(TreeList<Chunk_t, FreeList_t>::as_TreeList(mr.start(), mr.word_size()));
405 set_total_size(mr.word_size());
406 set_total_free_blocks(1);
407 }
408
409 template <class Chunk_t, class FreeList_t>
410 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset(HeapWord* addr, size_t byte_size) {
411 MemRegion mr(addr, heap_word_size(byte_size));
412 reset(mr);
413 }
414
415 template <class Chunk_t, class FreeList_t>
416 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset() {
417 set_root(NULL);
418 set_total_size(0);
419 set_total_free_blocks(0);
420 }
421
422 // Get a free block of size at least size from tree, or NULL.
423 template <class Chunk_t, class FreeList_t>
424 TreeChunk<Chunk_t, FreeList_t>*
425 BinaryTreeDictionary<Chunk_t, FreeList_t>::get_chunk_from_tree(size_t size)
426 {
427 TreeList<Chunk_t, FreeList_t> *curTL, *prevTL;
428 TreeChunk<Chunk_t, FreeList_t>* retTC = NULL;
429
430 assert((size >= min_size()), "minimum chunk size");
431 if (FLSVerifyDictionary) {
432 verify_tree();
433 }
434 // starting at the root, work downwards trying to find match.
435 // Remember the last node of size too great or too small.
436 for (prevTL = curTL = root(); curTL != NULL;) {
437 if (curTL->size() == size) { // exact match
438 break;
439 }
440 prevTL = curTL;
441 if (curTL->size() < size) { // proceed to right sub-tree
442 curTL = curTL->right();
443 } else { // proceed to left sub-tree
444 assert(curTL->size() > size, "size inconsistency");
445 curTL = curTL->left();
446 }
447 }
448 if (curTL == NULL) { // couldn't find exact match
449
450 // try and find the next larger size by walking back up the search path
451 for (curTL = prevTL; curTL != NULL;) {
452 if (curTL->size() >= size) break;
453 else curTL = curTL->parent();
454 }
455 assert(curTL == NULL || curTL->count() > 0,
456 "An empty list should not be in the tree");
457 }
458 if (curTL != NULL) {
459 assert(curTL->size() >= size, "size inconsistency");
460
461 curTL = curTL->get_better_list(this);
462
463 retTC = curTL->first_available();
464 assert((retTC != NULL) && (curTL->count() > 0),
465 "A list in the binary tree should not be NULL");
466 assert(retTC->size() >= size,
467 "A chunk of the wrong size was found");
468 remove_chunk_from_tree(retTC);
469 assert(retTC->is_free(), "Header is not marked correctly");
470 }
471
472 if (FLSVerifyDictionary) {
473 verify();
474 }
475 return retTC;
476 }
477
478 template <class Chunk_t, class FreeList_t>
479 TreeList<Chunk_t, FreeList_t>* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_list(size_t size) const {
480 TreeList<Chunk_t, FreeList_t>* curTL;
481 for (curTL = root(); curTL != NULL;) {
482 if (curTL->size() == size) { // exact match
483 break;
484 }
485
486 if (curTL->size() < size) { // proceed to right sub-tree
487 curTL = curTL->right();
488 } else { // proceed to left sub-tree
489 assert(curTL->size() > size, "size inconsistency");
490 curTL = curTL->left();
491 }
492 }
493 return curTL;
494 }
495
496
497 template <class Chunk_t, class FreeList_t>
498 bool BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_chunk_in_free_list(Chunk_t* tc) const {
499 size_t size = tc->size();
500 TreeList<Chunk_t, FreeList_t>* tl = find_list(size);
501 if (tl == NULL) {
502 return false;
503 } else {
504 return tl->verify_chunk_in_free_list(tc);
505 }
506 }
507
508 template <class Chunk_t, class FreeList_t>
509 Chunk_t* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_largest_dict() const {
510 TreeList<Chunk_t, FreeList_t> *curTL = root();
511 if (curTL != NULL) {
512 while(curTL->right() != NULL) curTL = curTL->right();
513 return curTL->largest_address();
514 } else {
515 return NULL;
516 }
517 }
518
519 // Remove the current chunk from the tree. If it is not the last
520 // chunk in a list on a tree node, just unlink it.
521 // If it is the last chunk in the list (the next link is NULL),
522 // remove the node and repair the tree.
523 template <class Chunk_t, class FreeList_t>
524 TreeChunk<Chunk_t, FreeList_t>*
525 BinaryTreeDictionary<Chunk_t, FreeList_t>::remove_chunk_from_tree(TreeChunk<Chunk_t, FreeList_t>* tc) {
526 assert(tc != NULL, "Should not call with a NULL chunk");
527 assert(tc->is_free(), "Header is not marked correctly");
528
529 TreeList<Chunk_t, FreeList_t> *newTL, *parentTL;
530 TreeChunk<Chunk_t, FreeList_t>* retTC;
531 TreeList<Chunk_t, FreeList_t>* tl = tc->list();
532 debug_only(
533 bool removing_only_chunk = false;
534 if (tl == _root) {
535 if ((_root->left() == NULL) && (_root->right() == NULL)) {
536 if (_root->count() == 1) {
537 assert(_root->head() == tc, "Should only be this one chunk");
538 removing_only_chunk = true;
539 }
540 }
541 }
542 )
543 assert(tl != NULL, "List should be set");
544 assert(tl->parent() == NULL || tl == tl->parent()->left() ||
545 tl == tl->parent()->right(), "list is inconsistent");
546
547 bool complicated_splice = false;
548
549 retTC = tc;
550 // Removing this chunk can have the side effect of changing the node
551 // (TreeList<Chunk_t, FreeList_t>*) in the tree. If the node is the root, update it.
552 TreeList<Chunk_t, FreeList_t>* replacementTL = tl->remove_chunk_replace_if_needed(tc);
553 assert(tc->is_free(), "Chunk should still be free");
554 assert(replacementTL->parent() == NULL ||
555 replacementTL == replacementTL->parent()->left() ||
556 replacementTL == replacementTL->parent()->right(),
557 "list is inconsistent");
558 if (tl == root()) {
559 assert(replacementTL->parent() == NULL, "Incorrectly replacing root");
560 set_root(replacementTL);
561 }
562 #ifdef ASSERT
563 if (tl != replacementTL) {
564 assert(replacementTL->head() != NULL,
565 "If the tree list was replaced, it should not be a NULL list");
566 TreeList<Chunk_t, FreeList_t>* rhl = replacementTL->head_as_TreeChunk()->list();
567 TreeList<Chunk_t, FreeList_t>* rtl =
568 TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(replacementTL->tail())->list();
569 assert(rhl == replacementTL, "Broken head");
570 assert(rtl == replacementTL, "Broken tail");
571 assert(replacementTL->size() == tc->size(), "Broken size");
572 }
573 #endif
574
575 // Does the tree need to be repaired?
576 if (replacementTL->count() == 0) {
577 assert(replacementTL->head() == NULL &&
578 replacementTL->tail() == NULL, "list count is incorrect");
579 // Find the replacement node for the (soon to be empty) node being removed.
580 // if we have a single (or no) child, splice child in our stead
581 if (replacementTL->left() == NULL) {
582 // left is NULL so pick right. right may also be NULL.
583 newTL = replacementTL->right();
584 debug_only(replacementTL->clear_right();)
585 } else if (replacementTL->right() == NULL) {
586 // right is NULL
587 newTL = replacementTL->left();
588 debug_only(replacementTL->clear_left();)
589 } else { // we have both children, so, by patriarchal convention,
590 // my replacement is least node in right sub-tree
591 complicated_splice = true;
592 newTL = remove_tree_minimum(replacementTL->right());
593 assert(newTL != NULL && newTL->left() == NULL &&
594 newTL->right() == NULL, "sub-tree minimum exists");
595 }
596 // newTL is the replacement for the (soon to be empty) node.
597 // newTL may be NULL.
598 // should verify; we just cleanly excised our replacement
599 if (FLSVerifyDictionary) {
600 verify_tree();
601 }
602 // first make newTL my parent's child
603 if ((parentTL = replacementTL->parent()) == NULL) {
604 // newTL should be root
605 assert(tl == root(), "Incorrectly replacing root");
606 set_root(newTL);
607 if (newTL != NULL) {
608 newTL->clear_parent();
609 }
610 } else if (parentTL->right() == replacementTL) {
611 // replacementTL is a right child
612 parentTL->set_right(newTL);
613 } else { // replacementTL is a left child
614 assert(parentTL->left() == replacementTL, "should be left child");
615 parentTL->set_left(newTL);
616 }
617 debug_only(replacementTL->clear_parent();)
618 if (complicated_splice) { // we need newTL to get replacementTL's
619 // two children
620 assert(newTL != NULL &&
621 newTL->left() == NULL && newTL->right() == NULL,
622 "newTL should not have encumbrances from the past");
623 // we'd like to assert as below:
624 // assert(replacementTL->left() != NULL && replacementTL->right() != NULL,
625 // "else !complicated_splice");
626 // ... however, the above assertion is too strong because we aren't
627 // guaranteed that replacementTL->right() is still NULL.
628 // Recall that we removed
629 // the right sub-tree minimum from replacementTL.
630 // That may well have been its right
631 // child! So we'll just assert half of the above:
632 assert(replacementTL->left() != NULL, "else !complicated_splice");
633 newTL->set_left(replacementTL->left());
634 newTL->set_right(replacementTL->right());
635 debug_only(
636 replacementTL->clear_right();
637 replacementTL->clear_left();
638 )
639 }
640 assert(replacementTL->right() == NULL &&
641 replacementTL->left() == NULL &&
642 replacementTL->parent() == NULL,
643 "delete without encumbrances");
644 }
645
646 assert(total_size() >= retTC->size(), "Incorrect total size");
647 dec_total_size(retTC->size()); // size book-keeping
648 assert(total_free_blocks() > 0, "Incorrect total count");
649 set_total_free_blocks(total_free_blocks() - 1);
650
651 assert(retTC != NULL, "null chunk?");
652 assert(retTC->prev() == NULL && retTC->next() == NULL,
653 "should return without encumbrances");
654 if (FLSVerifyDictionary) {
655 verify_tree();
656 }
657 assert(!removing_only_chunk || _root == NULL, "root should be NULL");
658 return TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(retTC);
659 }
660
661 // Remove the leftmost node (lm) in the tree and return it.
662 // If lm has a right child, link it to the left node of
663 // the parent of lm.
664 template <class Chunk_t, class FreeList_t>
665 TreeList<Chunk_t, FreeList_t>* BinaryTreeDictionary<Chunk_t, FreeList_t>::remove_tree_minimum(TreeList<Chunk_t, FreeList_t>* tl) {
666 assert(tl != NULL && tl->parent() != NULL, "really need a proper sub-tree");
667 // locate the subtree minimum by walking down left branches
668 TreeList<Chunk_t, FreeList_t>* curTL = tl;
669 for (; curTL->left() != NULL; curTL = curTL->left());
670 // obviously curTL now has at most one child, a right child
671 if (curTL != root()) { // Should this test just be removed?
672 TreeList<Chunk_t, FreeList_t>* parentTL = curTL->parent();
673 if (parentTL->left() == curTL) { // curTL is a left child
674 parentTL->set_left(curTL->right());
675 } else {
676 // If the list tl has no left child, then curTL may be
677 // the right child of parentTL.
678 assert(parentTL->right() == curTL, "should be a right child");
679 parentTL->set_right(curTL->right());
680 }
681 } else {
682 // The only use of this method would not pass the root of the
683 // tree (as indicated by the assertion above that the tree list
684 // has a parent) but the specification does not explicitly exclude the
685 // passing of the root so accommodate it.
686 set_root(NULL);
687 }
688 debug_only(
689 curTL->clear_parent(); // Test if this needs to be cleared
690 curTL->clear_right(); // recall, above, left child is already null
691 )
692 // we just excised a (non-root) node, we should still verify all tree invariants
693 if (FLSVerifyDictionary) {
694 verify_tree();
695 }
696 return curTL;
697 }
698
699 template <class Chunk_t, class FreeList_t>
700 void BinaryTreeDictionary<Chunk_t, FreeList_t>::insert_chunk_in_tree(Chunk_t* fc) {
701 TreeList<Chunk_t, FreeList_t> *curTL, *prevTL;
702 size_t size = fc->size();
703
704 assert((size >= min_size()),
705 SIZE_FORMAT " is too small to be a TreeChunk<Chunk_t, FreeList_t> " SIZE_FORMAT,
706 size, min_size());
707 if (FLSVerifyDictionary) {
708 verify_tree();
709 }
710
711 fc->clear_next();
712 fc->link_prev(NULL);
713
714 // work down from the _root, looking for insertion point
715 for (prevTL = curTL = root(); curTL != NULL;) {
716 if (curTL->size() == size) // exact match
717 break;
718 prevTL = curTL;
719 if (curTL->size() > size) { // follow left branch
720 curTL = curTL->left();
721 } else { // follow right branch
722 assert(curTL->size() < size, "size inconsistency");
723 curTL = curTL->right();
724 }
725 }
726 TreeChunk<Chunk_t, FreeList_t>* tc = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(fc);
727 // This chunk is being returned to the binary tree. Its embedded
728 // TreeList<Chunk_t, FreeList_t> should be unused at this point.
729 tc->initialize();
730 if (curTL != NULL) { // exact match
731 tc->set_list(curTL);
732 curTL->return_chunk_at_tail(tc);
733 } else { // need a new node in tree
734 tc->clear_next();
735 tc->link_prev(NULL);
736 TreeList<Chunk_t, FreeList_t>* newTL = TreeList<Chunk_t, FreeList_t>::as_TreeList(tc);
737 assert(((TreeChunk<Chunk_t, FreeList_t>*)tc)->list() == newTL,
738 "List was not initialized correctly");
739 if (prevTL == NULL) { // we are the only tree node
740 assert(root() == NULL, "control point invariant");
741 set_root(newTL);
742 } else { // insert under prevTL ...
743 if (prevTL->size() < size) { // am right child
744 assert(prevTL->right() == NULL, "control point invariant");
745 prevTL->set_right(newTL);
746 } else { // am left child
747 assert(prevTL->size() > size && prevTL->left() == NULL, "cpt pt inv");
748 prevTL->set_left(newTL);
749 }
750 }
751 }
752 assert(tc->list() != NULL, "Tree list should be set");
753
754 inc_total_size(size);
755 // Method 'total_size_in_tree' walks through the every block in the
756 // tree, so it can cause significant performance loss if there are
757 // many blocks in the tree
758 assert(!FLSVerifyDictionary || total_size_in_tree(root()) == total_size(), "_total_size inconsistency");
759 set_total_free_blocks(total_free_blocks() + 1);
760 if (FLSVerifyDictionary) {
761 verify_tree();
762 }
763 }
764
765 template <class Chunk_t, class FreeList_t>
766 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::max_chunk_size() const {
767 verify_par_locked();
768 TreeList<Chunk_t, FreeList_t>* tc = root();
769 if (tc == NULL) return 0;
770 for (; tc->right() != NULL; tc = tc->right());
771 return tc->size();
772 }
773
774 template <class Chunk_t, class FreeList_t>
775 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_list_length(TreeList<Chunk_t, FreeList_t>* tl) const {
776 size_t res;
777 res = tl->count();
778 #ifdef ASSERT
779 size_t cnt;
780 Chunk_t* tc = tl->head();
781 for (cnt = 0; tc != NULL; tc = tc->next(), cnt++);
782 assert(res == cnt, "The count is not being maintained correctly");
783 #endif
784 return res;
785 }
786
787 template <class Chunk_t, class FreeList_t>
788 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_size_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const {
789 if (tl == NULL)
790 return 0;
791 return (tl->size() * total_list_length(tl)) +
792 total_size_in_tree(tl->left()) +
793 total_size_in_tree(tl->right());
794 }
795
796 template <class Chunk_t, class FreeList_t>
797 double BinaryTreeDictionary<Chunk_t, FreeList_t>::sum_of_squared_block_sizes(TreeList<Chunk_t, FreeList_t>* const tl) const {
798 if (tl == NULL) {
799 return 0.0;
800 }
801 double size = (double)(tl->size());
802 double curr = size * size * total_list_length(tl);
803 curr += sum_of_squared_block_sizes(tl->left());
804 curr += sum_of_squared_block_sizes(tl->right());
805 return curr;
806 }
807
808 template <class Chunk_t, class FreeList_t>
809 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_free_blocks_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const {
810 if (tl == NULL)
811 return 0;
812 return total_list_length(tl) +
813 total_free_blocks_in_tree(tl->left()) +
814 total_free_blocks_in_tree(tl->right());
815 }
816
817 template <class Chunk_t, class FreeList_t>
818 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::num_free_blocks() const {
819 assert(total_free_blocks_in_tree(root()) == total_free_blocks(),
820 "_total_free_blocks inconsistency");
821 return total_free_blocks();
822 }
823
824 template <class Chunk_t, class FreeList_t>
825 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::tree_height_helper(TreeList<Chunk_t, FreeList_t>* tl) const {
826 if (tl == NULL)
827 return 0;
828 return 1 + MAX2(tree_height_helper(tl->left()),
829 tree_height_helper(tl->right()));
830 }
831
832 template <class Chunk_t, class FreeList_t>
833 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::tree_height() const {
834 return tree_height_helper(root());
835 }
836
837 template <class Chunk_t, class FreeList_t>
838 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_nodes_helper(TreeList<Chunk_t, FreeList_t>* tl) const {
839 if (tl == NULL) {
840 return 0;
841 }
842 return 1 + total_nodes_helper(tl->left()) +
843 total_nodes_helper(tl->right());
844 }
845
846 template <class Chunk_t, class FreeList_t>
847 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_nodes_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const {
848 return total_nodes_helper(root());
849 }
850
851 template <class Chunk_t, class FreeList_t>
852 void BinaryTreeDictionary<Chunk_t, FreeList_t>::dict_census_update(size_t size, bool split, bool birth){}
853
854 #if INCLUDE_ALL_GCS
855 template <>
856 void AFLBinaryTreeDictionary::dict_census_update(size_t size, bool split, bool birth) {
857 TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >* nd = find_list(size);
858 if (nd) {
859 if (split) {
860 if (birth) {
861 nd->increment_split_births();
862 nd->increment_surplus();
863 } else {
864 nd->increment_split_deaths();
865 nd->decrement_surplus();
866 }
867 } else {
868 if (birth) {
869 nd->increment_coal_births();
870 nd->increment_surplus();
871 } else {
872 nd->increment_coal_deaths();
873 nd->decrement_surplus();
874 }
875 }
876 }
877 // A list for this size may not be found (nd == 0) if
878 // This is a death where the appropriate list is now
879 // empty and has been removed from the list.
880 // This is a birth associated with a LinAB. The chunk
881 // for the LinAB is not in the dictionary.
882 }
883 #endif // INCLUDE_ALL_GCS
884
885 template <class Chunk_t, class FreeList_t>
886 bool BinaryTreeDictionary<Chunk_t, FreeList_t>::coal_dict_over_populated(size_t size) {
887 // For the general type of freelists, encourage coalescing by
888 // returning true.
889 return true;
890 }
891
892 #if INCLUDE_ALL_GCS
893 template <>
894 bool AFLBinaryTreeDictionary::coal_dict_over_populated(size_t size) {
895 if (FLSAlwaysCoalesceLarge) return true;
896
897 TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >* list_of_size = find_list(size);
898 // None of requested size implies overpopulated.
899 return list_of_size == NULL || list_of_size->coal_desired() <= 0 ||
900 list_of_size->count() > list_of_size->coal_desired();
901 }
902 #endif // INCLUDE_ALL_GCS
903
904 // Closures for walking the binary tree.
905 // do_list() walks the free list in a node applying the closure
906 // to each free chunk in the list
907 // do_tree() walks the nodes in the binary tree applying do_list()
908 // to each list at each node.
909
910 template <class Chunk_t, class FreeList_t>
911 class TreeCensusClosure : public StackObj {
912 protected:
913 virtual void do_list(FreeList_t* fl) = 0;
914 public:
915 virtual void do_tree(TreeList<Chunk_t, FreeList_t>* tl) = 0;
916 };
917
918 template <class Chunk_t, class FreeList_t>
919 class AscendTreeCensusClosure : public TreeCensusClosure<Chunk_t, FreeList_t> {
920 public:
921 void do_tree(TreeList<Chunk_t, FreeList_t>* tl) {
922 if (tl != NULL) {
923 do_tree(tl->left());
924 this->do_list(tl);
925 do_tree(tl->right());
926 }
927 }
928 };
929
930 template <class Chunk_t, class FreeList_t>
931 class DescendTreeCensusClosure : public TreeCensusClosure<Chunk_t, FreeList_t> {
932 public:
933 void do_tree(TreeList<Chunk_t, FreeList_t>* tl) {
934 if (tl != NULL) {
935 do_tree(tl->right());
936 this->do_list(tl);
937 do_tree(tl->left());
938 }
939 }
940 };
941
942 // For each list in the tree, calculate the desired, desired
943 // coalesce, count before sweep, and surplus before sweep.
944 template <class Chunk_t, class FreeList_t>
945 class BeginSweepClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
946 double _percentage;
947 float _inter_sweep_current;
948 float _inter_sweep_estimate;
949 float _intra_sweep_estimate;
950
951 public:
952 BeginSweepClosure(double p, float inter_sweep_current,
953 float inter_sweep_estimate,
954 float intra_sweep_estimate) :
955 _percentage(p),
956 _inter_sweep_current(inter_sweep_current),
957 _inter_sweep_estimate(inter_sweep_estimate),
958 _intra_sweep_estimate(intra_sweep_estimate) { }
959
960 void do_list(FreeList<Chunk_t>* fl) {}
961
962 #if INCLUDE_ALL_GCS
963 void do_list(AdaptiveFreeList<Chunk_t>* fl) {
964 double coalSurplusPercent = _percentage;
965 fl->compute_desired(_inter_sweep_current, _inter_sweep_estimate, _intra_sweep_estimate);
966 fl->set_coal_desired((ssize_t)((double)fl->desired() * coalSurplusPercent));
967 fl->set_before_sweep(fl->count());
968 fl->set_bfr_surp(fl->surplus());
969 }
970 #endif // INCLUDE_ALL_GCS
971 };
972
973 // Used to search the tree until a condition is met.
974 // Similar to TreeCensusClosure but searches the
975 // tree and returns promptly when found.
976
977 template <class Chunk_t, class FreeList_t>
978 class TreeSearchClosure : public StackObj {
979 protected:
980 virtual bool do_list(FreeList_t* fl) = 0;
981 public:
982 virtual bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) = 0;
983 };
984
985 #if 0 // Don't need this yet but here for symmetry.
986 template <class Chunk_t, class FreeList_t>
987 class AscendTreeSearchClosure : public TreeSearchClosure<Chunk_t> {
988 public:
989 bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) {
990 if (tl != NULL) {
991 if (do_tree(tl->left())) return true;
992 if (do_list(tl)) return true;
993 if (do_tree(tl->right())) return true;
994 }
995 return false;
996 }
997 };
998 #endif
999
1000 template <class Chunk_t, class FreeList_t>
1001 class DescendTreeSearchClosure : public TreeSearchClosure<Chunk_t, FreeList_t> {
1002 public:
1003 bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) {
1004 if (tl != NULL) {
1005 if (do_tree(tl->right())) return true;
1006 if (this->do_list(tl)) return true;
1007 if (do_tree(tl->left())) return true;
1008 }
1009 return false;
1010 }
1011 };
1012
1013 // Searches the tree for a chunk that ends at the
1014 // specified address.
1015 template <class Chunk_t, class FreeList_t>
1016 class EndTreeSearchClosure : public DescendTreeSearchClosure<Chunk_t, FreeList_t> {
1017 HeapWord* _target;
1018 Chunk_t* _found;
1019
1020 public:
1021 EndTreeSearchClosure(HeapWord* target) : _target(target), _found(NULL) {}
1022 bool do_list(FreeList_t* fl) {
1023 Chunk_t* item = fl->head();
1024 while (item != NULL) {
1025 if (item->end() == (uintptr_t*) _target) {
1026 _found = item;
1027 return true;
1028 }
1029 item = item->next();
1030 }
1031 return false;
1032 }
1033 Chunk_t* found() { return _found; }
1034 };
1035
1036 template <class Chunk_t, class FreeList_t>
1037 Chunk_t* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_chunk_ends_at(HeapWord* target) const {
1038 EndTreeSearchClosure<Chunk_t, FreeList_t> etsc(target);
1039 bool found_target = etsc.do_tree(root());
1040 assert(found_target || etsc.found() == NULL, "Consistency check");
1041 assert(!found_target || etsc.found() != NULL, "Consistency check");
1042 return etsc.found();
1043 }
1044
1045 template <class Chunk_t, class FreeList_t>
1046 void BinaryTreeDictionary<Chunk_t, FreeList_t>::begin_sweep_dict_census(double coalSurplusPercent,
1047 float inter_sweep_current, float inter_sweep_estimate, float intra_sweep_estimate) {
1048 BeginSweepClosure<Chunk_t, FreeList_t> bsc(coalSurplusPercent, inter_sweep_current,
1049 inter_sweep_estimate,
1050 intra_sweep_estimate);
1051 bsc.do_tree(root());
1052 }
1053
1054 // Closures and methods for calculating total bytes returned to the
1055 // free lists in the tree.
1056 #ifndef PRODUCT
1057 template <class Chunk_t, class FreeList_t>
1058 class InitializeDictReturnedBytesClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
1059 public:
1060 void do_list(FreeList_t* fl) {
1061 fl->set_returned_bytes(0);
1062 }
1063 };
1064
1065 template <class Chunk_t, class FreeList_t>
1066 void BinaryTreeDictionary<Chunk_t, FreeList_t>::initialize_dict_returned_bytes() {
1067 InitializeDictReturnedBytesClosure<Chunk_t, FreeList_t> idrb;
1068 idrb.do_tree(root());
1069 }
1070
1071 template <class Chunk_t, class FreeList_t>
1072 class ReturnedBytesClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
1073 size_t _dict_returned_bytes;
1074 public:
1075 ReturnedBytesClosure() { _dict_returned_bytes = 0; }
1076 void do_list(FreeList_t* fl) {
1077 _dict_returned_bytes += fl->returned_bytes();
1078 }
1079 size_t dict_returned_bytes() { return _dict_returned_bytes; }
1080 };
1081
1082 template <class Chunk_t, class FreeList_t>
1083 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::sum_dict_returned_bytes() {
1084 ReturnedBytesClosure<Chunk_t, FreeList_t> rbc;
1085 rbc.do_tree(root());
1086
1087 return rbc.dict_returned_bytes();
1088 }
1089
1090 // Count the number of entries in the tree.
1091 template <class Chunk_t, class FreeList_t>
1092 class treeCountClosure : public DescendTreeCensusClosure<Chunk_t, FreeList_t> {
1093 public:
1094 uint count;
1095 treeCountClosure(uint c) { count = c; }
1096 void do_list(FreeList_t* fl) {
1097 count++;
1098 }
1099 };
1100
1101 template <class Chunk_t, class FreeList_t>
1102 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_count() {
1103 treeCountClosure<Chunk_t, FreeList_t> ctc(0);
1104 ctc.do_tree(root());
1105 return ctc.count;
1106 }
1107
1108 template <class Chunk_t, class FreeList_t>
1109 Mutex* BinaryTreeDictionary<Chunk_t, FreeList_t>::par_lock() const {
1110 return _lock;
1111 }
1112
1113 template <class Chunk_t, class FreeList_t>
1114 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_par_lock(Mutex* lock) {
1115 _lock = lock;
1116 }
1117
1118 template <class Chunk_t, class FreeList_t>
1119 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_par_locked() const {
1120 #ifdef ASSERT
1121 Thread* my_thread = Thread::current();
1122 if (my_thread->is_GC_task_thread()) {
1123 assert(par_lock() != NULL, "Should be using locking?");
1124 assert_lock_strong(par_lock());
1125 }
1126 #endif // ASSERT
1127 }
1128 #endif // PRODUCT
1129
1130 // Calculate surpluses for the lists in the tree.
1131 template <class Chunk_t, class FreeList_t>
1132 class setTreeSurplusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
1133 double percentage;
1134 public:
1135 setTreeSurplusClosure(double v) { percentage = v; }
1136 void do_list(FreeList<Chunk_t>* fl) {}
1137
1138 #if INCLUDE_ALL_GCS
1139 void do_list(AdaptiveFreeList<Chunk_t>* fl) {
1140 double splitSurplusPercent = percentage;
1141 fl->set_surplus(fl->count() -
1142 (ssize_t)((double)fl->desired() * splitSurplusPercent));
1143 }
1144 #endif // INCLUDE_ALL_GCS
1145 };
1146
1147 template <class Chunk_t, class FreeList_t>
1148 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_surplus(double splitSurplusPercent) {
1149 setTreeSurplusClosure<Chunk_t, FreeList_t> sts(splitSurplusPercent);
1150 sts.do_tree(root());
1151 }
1152
1153 // Set hints for the lists in the tree.
1154 template <class Chunk_t, class FreeList_t>
1155 class setTreeHintsClosure : public DescendTreeCensusClosure<Chunk_t, FreeList_t> {
1156 size_t hint;
1157 public:
1158 setTreeHintsClosure(size_t v) { hint = v; }
1159 void do_list(FreeList<Chunk_t>* fl) {}
1160
1161 #if INCLUDE_ALL_GCS
1162 void do_list(AdaptiveFreeList<Chunk_t>* fl) {
1163 fl->set_hint(hint);
1164 assert(fl->hint() == 0 || fl->hint() > fl->size(),
1165 "Current hint is inconsistent");
1166 if (fl->surplus() > 0) {
1167 hint = fl->size();
1168 }
1169 }
1170 #endif // INCLUDE_ALL_GCS
1171 };
1172
1173 template <class Chunk_t, class FreeList_t>
1174 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_hints(void) {
1175 setTreeHintsClosure<Chunk_t, FreeList_t> sth(0);
1176 sth.do_tree(root());
1177 }
1178
1179 // Save count before previous sweep and splits and coalesces.
1180 template <class Chunk_t, class FreeList_t>
1181 class clearTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
1182 void do_list(FreeList<Chunk_t>* fl) {}
1183
1184 #if INCLUDE_ALL_GCS
1185 void do_list(AdaptiveFreeList<Chunk_t>* fl) {
1186 fl->set_prev_sweep(fl->count());
1187 fl->set_coal_births(0);
1188 fl->set_coal_deaths(0);
1189 fl->set_split_births(0);
1190 fl->set_split_deaths(0);
1191 }
1192 #endif // INCLUDE_ALL_GCS
1193 };
1194
1195 template <class Chunk_t, class FreeList_t>
1196 void BinaryTreeDictionary<Chunk_t, FreeList_t>::clear_tree_census(void) {
1197 clearTreeCensusClosure<Chunk_t, FreeList_t> ctc;
1198 ctc.do_tree(root());
1199 }
1200
1201 // Do reporting and post sweep clean up.
1202 template <class Chunk_t, class FreeList_t>
1203 void BinaryTreeDictionary<Chunk_t, FreeList_t>::end_sweep_dict_census(double splitSurplusPercent) {
1204 // Does walking the tree 3 times hurt?
1205 set_tree_surplus(splitSurplusPercent);
1206 set_tree_hints();
1207 LogTarget(Trace, gc, freelist, stats) log;
1208 if (log.is_enabled()) {
1209 LogStream out(log);
1210 report_statistics(&out);
1211 }
1212 clear_tree_census();
1213 }
1214
1215 // Print summary statistics
1216 template <class Chunk_t, class FreeList_t>
1217 void BinaryTreeDictionary<Chunk_t, FreeList_t>::report_statistics(outputStream* st) const {
1218 verify_par_locked();
1219 st->print_cr("Statistics for BinaryTreeDictionary:");
1220 st->print_cr("------------------------------------");
1221 size_t total_size = total_chunk_size(debug_only(NULL));
1222 size_t free_blocks = num_free_blocks();
1223 st->print_cr("Total Free Space: " SIZE_FORMAT, total_size);
1224 st->print_cr("Max Chunk Size: " SIZE_FORMAT, max_chunk_size());
1225 st->print_cr("Number of Blocks: " SIZE_FORMAT, free_blocks);
1226 if (free_blocks > 0) {
1227 st->print_cr("Av. Block Size: " SIZE_FORMAT, total_size/free_blocks);
1228 }
1229 st->print_cr("Tree Height: " SIZE_FORMAT, tree_height());
1230 }
1231
1232 // Print census information - counts, births, deaths, etc.
1233 // for each list in the tree. Also print some summary
1234 // information.
1235 template <class Chunk_t, class FreeList_t>
1236 class PrintTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
1237 int _print_line;
1238 size_t _total_free;
1239 FreeList_t _total;
1240
1241 public:
1242 PrintTreeCensusClosure() {
1243 _print_line = 0;
1244 _total_free = 0;
1245 }
1246 FreeList_t* total() { return &_total; }
1247 size_t total_free() { return _total_free; }
1248 void do_list(FreeList<Chunk_t>* fl) {
1249 LogStreamHandle(Debug, gc, freelist, census) out;
1250
1251 if (++_print_line >= 40) {
1252 FreeList_t::print_labels_on(&out, "size");
1253 _print_line = 0;
1254 }
1255 fl->print_on(&out);
1256 _total_free += fl->count() * fl->size();
1257 total()->set_count(total()->count() + fl->count());
1258 }
1259
1260 #if INCLUDE_ALL_GCS
1261 void do_list(AdaptiveFreeList<Chunk_t>* fl) {
1262 LogStreamHandle(Debug, gc, freelist, census) out;
1263
1264 if (++_print_line >= 40) {
1265 FreeList_t::print_labels_on(&out, "size");
1266 _print_line = 0;
1267 }
1268 fl->print_on(&out);
1269 _total_free += fl->count() * fl->size() ;
1270 total()->set_count( total()->count() + fl->count() );
1271 total()->set_bfr_surp( total()->bfr_surp() + fl->bfr_surp() );
1272 total()->set_surplus( total()->split_deaths() + fl->surplus() );
1273 total()->set_desired( total()->desired() + fl->desired() );
1274 total()->set_prev_sweep( total()->prev_sweep() + fl->prev_sweep() );
1275 total()->set_before_sweep(total()->before_sweep() + fl->before_sweep());
1276 total()->set_coal_births( total()->coal_births() + fl->coal_births() );
1277 total()->set_coal_deaths( total()->coal_deaths() + fl->coal_deaths() );
1278 total()->set_split_births(total()->split_births() + fl->split_births());
1279 total()->set_split_deaths(total()->split_deaths() + fl->split_deaths());
1280 }
1281 #endif // INCLUDE_ALL_GCS
1282 };
1283
1284 template <class Chunk_t, class FreeList_t>
1285 void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_dict_census(outputStream* st) const {
1286
1287 st->print("BinaryTree");
1288 FreeList_t::print_labels_on(st, "size");
1289 PrintTreeCensusClosure<Chunk_t, FreeList_t> ptc;
1290 ptc.do_tree(root());
1291
1292 FreeList_t* total = ptc.total();
1293 FreeList_t::print_labels_on(st, " ");
1294 }
1295
1296 #if INCLUDE_ALL_GCS
1297 template <>
1298 void AFLBinaryTreeDictionary::print_dict_census(outputStream* st) const {
1299
1300 st->print_cr("BinaryTree");
1301 AdaptiveFreeList<FreeChunk>::print_labels_on(st, "size");
1302 PrintTreeCensusClosure<FreeChunk, AdaptiveFreeList<FreeChunk> > ptc;
1303 ptc.do_tree(root());
1304
1305 AdaptiveFreeList<FreeChunk>* total = ptc.total();
1306 AdaptiveFreeList<FreeChunk>::print_labels_on(st, " ");
1307 total->print_on(st, "TOTAL\t");
1308 st->print_cr("total_free(words): " SIZE_FORMAT_W(16) " growth: %8.5f deficit: %8.5f",
1309 ptc.total_free(),
1310 (double)(total->split_births() + total->coal_births()
1311 - total->split_deaths() - total->coal_deaths())
1312 /(total->prev_sweep() != 0 ? (double)total->prev_sweep() : 1.0),
1313 (double)(total->desired() - total->count())
1314 /(total->desired() != 0 ? (double)total->desired() : 1.0));
1315 }
1316 #endif // INCLUDE_ALL_GCS
1317
1318 template <class Chunk_t, class FreeList_t>
1319 class PrintFreeListsClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
1320 outputStream* _st;
1321 int _print_line;
1322
1323 public:
1324 PrintFreeListsClosure(outputStream* st) {
1325 _st = st;
1326 _print_line = 0;
1327 }
1328 void do_list(FreeList_t* fl) {
1329 if (++_print_line >= 40) {
1330 FreeList_t::print_labels_on(_st, "size");
1331 _print_line = 0;
1332 }
1333 fl->print_on(_st);
1334 size_t sz = fl->size();
1335 for (Chunk_t* fc = fl->head(); fc != NULL;
1336 fc = fc->next()) {
1337 _st->print_cr("\t[" PTR_FORMAT "," PTR_FORMAT ") %s",
1338 p2i(fc), p2i((HeapWord*)fc + sz),
1339 fc->cantCoalesce() ? "\t CC" : "");
1340 }
1341 }
1342 };
1343
1344 template <class Chunk_t, class FreeList_t>
1345 void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_free_lists(outputStream* st) const {
1346
1347 FreeList_t::print_labels_on(st, "size");
1348 PrintFreeListsClosure<Chunk_t, FreeList_t> pflc(st);
1349 pflc.do_tree(root());
1350 }
1351
1352 // Verify the following tree invariants:
1353 // . _root has no parent
1354 // . parent and child point to each other
1355 // . each node's key correctly related to that of its child(ren)
1356 template <class Chunk_t, class FreeList_t>
1357 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_tree() const {
1358 guarantee(root() == NULL || total_free_blocks() == 0 ||
1359 total_size() != 0, "_total_size shouldn't be 0?");
1360 guarantee(root() == NULL || root()->parent() == NULL, "_root shouldn't have parent");
1361 verify_tree_helper(root());
1362 }
1363
1364 template <class Chunk_t, class FreeList_t>
1365 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_prev_free_ptrs(TreeList<Chunk_t, FreeList_t>* tl) {
1366 size_t ct = 0;
1367 for (Chunk_t* curFC = tl->head(); curFC != NULL; curFC = curFC->next()) {
1368 ct++;
1369 assert(curFC->prev() == NULL || curFC->prev()->is_free(),
1370 "Chunk should be free");
1371 }
1372 return ct;
1373 }
1374
1375 // Note: this helper is recursive rather than iterative, so use with
1376 // caution on very deep trees; and watch out for stack overflow errors;
1377 // In general, to be used only for debugging.
1378 template <class Chunk_t, class FreeList_t>
1379 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_tree_helper(TreeList<Chunk_t, FreeList_t>* tl) const {
1380 if (tl == NULL)
1381 return;
1382 guarantee(tl->size() != 0, "A list must has a size");
1383 guarantee(tl->left() == NULL || tl->left()->parent() == tl,
1384 "parent<-/->left");
1385 guarantee(tl->right() == NULL || tl->right()->parent() == tl,
1386 "parent<-/->right");;
1387 guarantee(tl->left() == NULL || tl->left()->size() < tl->size(),
1388 "parent !> left");
1389 guarantee(tl->right() == NULL || tl->right()->size() > tl->size(),
1390 "parent !< left");
1391 guarantee(tl->head() == NULL || tl->head()->is_free(), "!Free");
1392 guarantee(tl->head() == NULL || tl->head_as_TreeChunk()->list() == tl,
1393 "list inconsistency");
1394 guarantee(tl->count() > 0 || (tl->head() == NULL && tl->tail() == NULL),
1395 "list count is inconsistent");
1396 guarantee(tl->count() > 1 || tl->head() == tl->tail(),
1397 "list is incorrectly constructed");
1398 size_t count = verify_prev_free_ptrs(tl);
1399 guarantee(count == (size_t)tl->count(), "Node count is incorrect");
1400 if (tl->head() != NULL) {
1401 tl->head_as_TreeChunk()->verify_tree_chunk_list();
1402 }
1403 verify_tree_helper(tl->left());
1404 verify_tree_helper(tl->right());
1405 }
1406
1407 template <class Chunk_t, class FreeList_t>
1408 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify() const {
1409 verify_tree();
1410 guarantee(total_size() == total_size_in_tree(root()), "Total Size inconsistency");
1411 }
1412
1413 template class TreeList<Metablock, FreeList<Metablock> >;
1414 template class BinaryTreeDictionary<Metablock, FreeList<Metablock> >;
1415 template class TreeChunk<Metablock, FreeList<Metablock> >;
1416
1417 template class TreeList<Metachunk, FreeList<Metachunk> >;
1418 template class BinaryTreeDictionary<Metachunk, FreeList<Metachunk> >;
1419 template class TreeChunk<Metachunk, FreeList<Metachunk> >;
1420
1421
1422 #if INCLUDE_ALL_GCS
1423 // Explicitly instantiate these types for FreeChunk.
1424 template class TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >;
1425 template class BinaryTreeDictionary<FreeChunk, AdaptiveFreeList<FreeChunk> >;
1426 template class TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >;
1427
1428 #endif // INCLUDE_ALL_GCS