Wed, 23 Dec 2009 09:23:54 -0800
6631166: CMS: better heuristics when combatting fragmentation
Summary: Autonomic per-worker free block cache sizing, tunable coalition policies, fixes to per-size block statistics, retuned gain and bandwidth of some feedback loop filters to allow quicker reactivity to abrupt changes in ambient demand, and other heuristics to reduce fragmentation of the CMS old gen. Also tightened some assertions, including those related to locking.
Reviewed-by: jmasa
1 /*
2 * Copyright 2001-2008 Sun Microsystems, Inc. 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
20 * CA 95054 USA or visit www.sun.com if you need additional information or
21 * have any questions.
22 *
23 */
25 # include "incls/_precompiled.incl"
26 # include "incls/_binaryTreeDictionary.cpp.incl"
28 ////////////////////////////////////////////////////////////////////////////////
29 // A binary tree based search structure for free blocks.
30 // This is currently used in the Concurrent Mark&Sweep implementation.
31 ////////////////////////////////////////////////////////////////////////////////
33 TreeChunk* TreeChunk::as_TreeChunk(FreeChunk* fc) {
34 // Do some assertion checking here.
35 return (TreeChunk*) fc;
36 }
38 void TreeChunk::verifyTreeChunkList() const {
39 TreeChunk* nextTC = (TreeChunk*)next();
40 if (prev() != NULL) { // interior list node shouldn'r have tree fields
41 guarantee(embedded_list()->parent() == NULL && embedded_list()->left() == NULL &&
42 embedded_list()->right() == NULL, "should be clear");
43 }
44 if (nextTC != NULL) {
45 guarantee(as_TreeChunk(nextTC->prev()) == this, "broken chain");
46 guarantee(nextTC->size() == size(), "wrong size");
47 nextTC->verifyTreeChunkList();
48 }
49 }
52 TreeList* TreeList::as_TreeList(TreeChunk* tc) {
53 // This first free chunk in the list will be the tree list.
54 assert(tc->size() >= sizeof(TreeChunk), "Chunk is too small for a TreeChunk");
55 TreeList* tl = tc->embedded_list();
56 tc->set_list(tl);
57 #ifdef ASSERT
58 tl->set_protecting_lock(NULL);
59 #endif
60 tl->set_hint(0);
61 tl->set_size(tc->size());
62 tl->link_head(tc);
63 tl->link_tail(tc);
64 tl->set_count(1);
65 tl->init_statistics(true /* split_birth */);
66 tl->setParent(NULL);
67 tl->setLeft(NULL);
68 tl->setRight(NULL);
69 return tl;
70 }
72 TreeList* TreeList::as_TreeList(HeapWord* addr, size_t size) {
73 TreeChunk* tc = (TreeChunk*) addr;
74 assert(size >= sizeof(TreeChunk), "Chunk is too small for a TreeChunk");
75 // The space in the heap will have been mangled initially but
76 // is not remangled when a free chunk is returned to the free list
77 // (since it is used to maintain the chunk on the free list).
78 assert((ZapUnusedHeapArea &&
79 SpaceMangler::is_mangled((HeapWord*) tc->size_addr()) &&
80 SpaceMangler::is_mangled((HeapWord*) tc->prev_addr()) &&
81 SpaceMangler::is_mangled((HeapWord*) tc->next_addr())) ||
82 (tc->size() == 0 && tc->prev() == NULL && tc->next() == NULL),
83 "Space should be clear or mangled");
84 tc->setSize(size);
85 tc->linkPrev(NULL);
86 tc->linkNext(NULL);
87 TreeList* tl = TreeList::as_TreeList(tc);
88 return tl;
89 }
91 TreeList* TreeList::removeChunkReplaceIfNeeded(TreeChunk* tc) {
93 TreeList* retTL = this;
94 FreeChunk* list = head();
95 assert(!list || list != list->next(), "Chunk on list twice");
96 assert(tc != NULL, "Chunk being removed is NULL");
97 assert(parent() == NULL || this == parent()->left() ||
98 this == parent()->right(), "list is inconsistent");
99 assert(tc->isFree(), "Header is not marked correctly");
100 assert(head() == NULL || head()->prev() == NULL, "list invariant");
101 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
103 FreeChunk* prevFC = tc->prev();
104 TreeChunk* nextTC = TreeChunk::as_TreeChunk(tc->next());
105 assert(list != NULL, "should have at least the target chunk");
107 // Is this the first item on the list?
108 if (tc == list) {
109 // The "getChunk..." functions for a TreeList will not return the
110 // first chunk in the list unless it is the last chunk in the list
111 // because the first chunk is also acting as the tree node.
112 // When coalescing happens, however, the first chunk in the a tree
113 // list can be the start of a free range. Free ranges are removed
114 // from the free lists so that they are not available to be
115 // allocated when the sweeper yields (giving up the free list lock)
116 // to allow mutator activity. If this chunk is the first in the
117 // list and is not the last in the list, do the work to copy the
118 // TreeList from the first chunk to the next chunk and update all
119 // the TreeList pointers in the chunks in the list.
120 if (nextTC == NULL) {
121 assert(prevFC == NULL, "Not last chunk in the list")
122 set_tail(NULL);
123 set_head(NULL);
124 } else {
125 // copy embedded list.
126 nextTC->set_embedded_list(tc->embedded_list());
127 retTL = nextTC->embedded_list();
128 // Fix the pointer to the list in each chunk in the list.
129 // This can be slow for a long list. Consider having
130 // an option that does not allow the first chunk on the
131 // list to be coalesced.
132 for (TreeChunk* curTC = nextTC; curTC != NULL;
133 curTC = TreeChunk::as_TreeChunk(curTC->next())) {
134 curTC->set_list(retTL);
135 }
136 // Fix the parent to point to the new TreeList.
137 if (retTL->parent() != NULL) {
138 if (this == retTL->parent()->left()) {
139 retTL->parent()->setLeft(retTL);
140 } else {
141 assert(this == retTL->parent()->right(), "Parent is incorrect");
142 retTL->parent()->setRight(retTL);
143 }
144 }
145 // Fix the children's parent pointers to point to the
146 // new list.
147 assert(right() == retTL->right(), "Should have been copied");
148 if (retTL->right() != NULL) {
149 retTL->right()->setParent(retTL);
150 }
151 assert(left() == retTL->left(), "Should have been copied");
152 if (retTL->left() != NULL) {
153 retTL->left()->setParent(retTL);
154 }
155 retTL->link_head(nextTC);
156 assert(nextTC->isFree(), "Should be a free chunk");
157 }
158 } else {
159 if (nextTC == NULL) {
160 // Removing chunk at tail of list
161 link_tail(prevFC);
162 }
163 // Chunk is interior to the list
164 prevFC->linkAfter(nextTC);
165 }
167 // Below this point the embeded TreeList being used for the
168 // tree node may have changed. Don't use "this"
169 // TreeList*.
170 // chunk should still be a free chunk (bit set in _prev)
171 assert(!retTL->head() || retTL->size() == retTL->head()->size(),
172 "Wrong sized chunk in list");
173 debug_only(
174 tc->linkPrev(NULL);
175 tc->linkNext(NULL);
176 tc->set_list(NULL);
177 bool prev_found = false;
178 bool next_found = false;
179 for (FreeChunk* curFC = retTL->head();
180 curFC != NULL; curFC = curFC->next()) {
181 assert(curFC != tc, "Chunk is still in list");
182 if (curFC == prevFC) {
183 prev_found = true;
184 }
185 if (curFC == nextTC) {
186 next_found = true;
187 }
188 }
189 assert(prevFC == NULL || prev_found, "Chunk was lost from list");
190 assert(nextTC == NULL || next_found, "Chunk was lost from list");
191 assert(retTL->parent() == NULL ||
192 retTL == retTL->parent()->left() ||
193 retTL == retTL->parent()->right(),
194 "list is inconsistent");
195 )
196 retTL->decrement_count();
198 assert(tc->isFree(), "Should still be a free chunk");
199 assert(retTL->head() == NULL || retTL->head()->prev() == NULL,
200 "list invariant");
201 assert(retTL->tail() == NULL || retTL->tail()->next() == NULL,
202 "list invariant");
203 return retTL;
204 }
205 void TreeList::returnChunkAtTail(TreeChunk* chunk) {
206 assert(chunk != NULL, "returning NULL chunk");
207 assert(chunk->list() == this, "list should be set for chunk");
208 assert(tail() != NULL, "The tree list is embedded in the first chunk");
209 // which means that the list can never be empty.
210 assert(!verifyChunkInFreeLists(chunk), "Double entry");
211 assert(head() == NULL || head()->prev() == NULL, "list invariant");
212 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
214 FreeChunk* fc = tail();
215 fc->linkAfter(chunk);
216 link_tail(chunk);
218 assert(!tail() || size() == tail()->size(), "Wrong sized chunk in list");
219 increment_count();
220 debug_only(increment_returnedBytes_by(chunk->size()*sizeof(HeapWord));)
221 assert(head() == NULL || head()->prev() == NULL, "list invariant");
222 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
223 }
225 // Add this chunk at the head of the list. "At the head of the list"
226 // is defined to be after the chunk pointer to by head(). This is
227 // because the TreeList is embedded in the first TreeChunk in the
228 // list. See the definition of TreeChunk.
229 void TreeList::returnChunkAtHead(TreeChunk* chunk) {
230 assert(chunk->list() == this, "list should be set for chunk");
231 assert(head() != NULL, "The tree list is embedded in the first chunk");
232 assert(chunk != NULL, "returning NULL chunk");
233 assert(!verifyChunkInFreeLists(chunk), "Double entry");
234 assert(head() == NULL || head()->prev() == NULL, "list invariant");
235 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
237 FreeChunk* fc = head()->next();
238 if (fc != NULL) {
239 chunk->linkAfter(fc);
240 } else {
241 assert(tail() == NULL, "List is inconsistent");
242 link_tail(chunk);
243 }
244 head()->linkAfter(chunk);
245 assert(!head() || size() == head()->size(), "Wrong sized chunk in list");
246 increment_count();
247 debug_only(increment_returnedBytes_by(chunk->size()*sizeof(HeapWord));)
248 assert(head() == NULL || head()->prev() == NULL, "list invariant");
249 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
250 }
252 TreeChunk* TreeList::head_as_TreeChunk() {
253 assert(head() == NULL || TreeChunk::as_TreeChunk(head())->list() == this,
254 "Wrong type of chunk?");
255 return TreeChunk::as_TreeChunk(head());
256 }
258 TreeChunk* TreeList::first_available() {
259 guarantee(head() != NULL, "The head of the list cannot be NULL");
260 FreeChunk* fc = head()->next();
261 TreeChunk* retTC;
262 if (fc == NULL) {
263 retTC = head_as_TreeChunk();
264 } else {
265 retTC = TreeChunk::as_TreeChunk(fc);
266 }
267 assert(retTC->list() == this, "Wrong type of chunk.");
268 return retTC;
269 }
271 // Returns the block with the largest heap address amongst
272 // those in the list for this size; potentially slow and expensive,
273 // use with caution!
274 TreeChunk* TreeList::largest_address() {
275 guarantee(head() != NULL, "The head of the list cannot be NULL");
276 FreeChunk* fc = head()->next();
277 TreeChunk* retTC;
278 if (fc == NULL) {
279 retTC = head_as_TreeChunk();
280 } else {
281 // walk down the list and return the one with the highest
282 // heap address among chunks of this size.
283 FreeChunk* last = fc;
284 while (fc->next() != NULL) {
285 if ((HeapWord*)last < (HeapWord*)fc) {
286 last = fc;
287 }
288 fc = fc->next();
289 }
290 retTC = TreeChunk::as_TreeChunk(last);
291 }
292 assert(retTC->list() == this, "Wrong type of chunk.");
293 return retTC;
294 }
296 BinaryTreeDictionary::BinaryTreeDictionary(MemRegion mr, bool splay):
297 _splay(splay)
298 {
299 assert(mr.byte_size() > MIN_TREE_CHUNK_SIZE, "minimum chunk size");
301 reset(mr);
302 assert(root()->left() == NULL, "reset check failed");
303 assert(root()->right() == NULL, "reset check failed");
304 assert(root()->head()->next() == NULL, "reset check failed");
305 assert(root()->head()->prev() == NULL, "reset check failed");
306 assert(totalSize() == root()->size(), "reset check failed");
307 assert(totalFreeBlocks() == 1, "reset check failed");
308 }
310 void BinaryTreeDictionary::inc_totalSize(size_t inc) {
311 _totalSize = _totalSize + inc;
312 }
314 void BinaryTreeDictionary::dec_totalSize(size_t dec) {
315 _totalSize = _totalSize - dec;
316 }
318 void BinaryTreeDictionary::reset(MemRegion mr) {
319 assert(mr.byte_size() > MIN_TREE_CHUNK_SIZE, "minimum chunk size");
320 set_root(TreeList::as_TreeList(mr.start(), mr.word_size()));
321 set_totalSize(mr.word_size());
322 set_totalFreeBlocks(1);
323 }
325 void BinaryTreeDictionary::reset(HeapWord* addr, size_t byte_size) {
326 MemRegion mr(addr, heap_word_size(byte_size));
327 reset(mr);
328 }
330 void BinaryTreeDictionary::reset() {
331 set_root(NULL);
332 set_totalSize(0);
333 set_totalFreeBlocks(0);
334 }
336 // Get a free block of size at least size from tree, or NULL.
337 // If a splay step is requested, the removal algorithm (only) incorporates
338 // a splay step as follows:
339 // . the search proceeds down the tree looking for a possible
340 // match. At the (closest) matching location, an appropriate splay step is applied
341 // (zig, zig-zig or zig-zag). A chunk of the appropriate size is then returned
342 // if available, and if it's the last chunk, the node is deleted. A deteleted
343 // node is replaced in place by its tree successor.
344 TreeChunk*
345 BinaryTreeDictionary::getChunkFromTree(size_t size, Dither dither, bool splay)
346 {
347 TreeList *curTL, *prevTL;
348 TreeChunk* retTC = NULL;
349 assert(size >= MIN_TREE_CHUNK_SIZE, "minimum chunk size");
350 if (FLSVerifyDictionary) {
351 verifyTree();
352 }
353 // starting at the root, work downwards trying to find match.
354 // Remember the last node of size too great or too small.
355 for (prevTL = curTL = root(); curTL != NULL;) {
356 if (curTL->size() == size) { // exact match
357 break;
358 }
359 prevTL = curTL;
360 if (curTL->size() < size) { // proceed to right sub-tree
361 curTL = curTL->right();
362 } else { // proceed to left sub-tree
363 assert(curTL->size() > size, "size inconsistency");
364 curTL = curTL->left();
365 }
366 }
367 if (curTL == NULL) { // couldn't find exact match
368 // try and find the next larger size by walking back up the search path
369 for (curTL = prevTL; curTL != NULL;) {
370 if (curTL->size() >= size) break;
371 else curTL = curTL->parent();
372 }
373 assert(curTL == NULL || curTL->count() > 0,
374 "An empty list should not be in the tree");
375 }
376 if (curTL != NULL) {
377 assert(curTL->size() >= size, "size inconsistency");
378 if (UseCMSAdaptiveFreeLists) {
380 // A candidate chunk has been found. If it is already under
381 // populated, get a chunk associated with the hint for this
382 // chunk.
383 if (curTL->surplus() <= 0) {
384 /* Use the hint to find a size with a surplus, and reset the hint. */
385 TreeList* hintTL = curTL;
386 while (hintTL->hint() != 0) {
387 assert(hintTL->hint() == 0 || hintTL->hint() > hintTL->size(),
388 "hint points in the wrong direction");
389 hintTL = findList(hintTL->hint());
390 assert(curTL != hintTL, "Infinite loop");
391 if (hintTL == NULL ||
392 hintTL == curTL /* Should not happen but protect against it */ ) {
393 // No useful hint. Set the hint to NULL and go on.
394 curTL->set_hint(0);
395 break;
396 }
397 assert(hintTL->size() > size, "hint is inconsistent");
398 if (hintTL->surplus() > 0) {
399 // The hint led to a list that has a surplus. Use it.
400 // Set the hint for the candidate to an overpopulated
401 // size.
402 curTL->set_hint(hintTL->size());
403 // Change the candidate.
404 curTL = hintTL;
405 break;
406 }
407 // The evm code reset the hint of the candidate as
408 // at an interim point. Why? Seems like this leaves
409 // the hint pointing to a list that didn't work.
410 // curTL->set_hint(hintTL->size());
411 }
412 }
413 }
414 // don't waste time splaying if chunk's singleton
415 if (splay && curTL->head()->next() != NULL) {
416 semiSplayStep(curTL);
417 }
418 retTC = curTL->first_available();
419 assert((retTC != NULL) && (curTL->count() > 0),
420 "A list in the binary tree should not be NULL");
421 assert(retTC->size() >= size,
422 "A chunk of the wrong size was found");
423 removeChunkFromTree(retTC);
424 assert(retTC->isFree(), "Header is not marked correctly");
425 }
427 if (FLSVerifyDictionary) {
428 verify();
429 }
430 return retTC;
431 }
433 TreeList* BinaryTreeDictionary::findList(size_t size) const {
434 TreeList* curTL;
435 for (curTL = root(); curTL != NULL;) {
436 if (curTL->size() == size) { // exact match
437 break;
438 }
440 if (curTL->size() < size) { // proceed to right sub-tree
441 curTL = curTL->right();
442 } else { // proceed to left sub-tree
443 assert(curTL->size() > size, "size inconsistency");
444 curTL = curTL->left();
445 }
446 }
447 return curTL;
448 }
451 bool BinaryTreeDictionary::verifyChunkInFreeLists(FreeChunk* tc) const {
452 size_t size = tc->size();
453 TreeList* tl = findList(size);
454 if (tl == NULL) {
455 return false;
456 } else {
457 return tl->verifyChunkInFreeLists(tc);
458 }
459 }
461 FreeChunk* BinaryTreeDictionary::findLargestDict() const {
462 TreeList *curTL = root();
463 if (curTL != NULL) {
464 while(curTL->right() != NULL) curTL = curTL->right();
465 return curTL->largest_address();
466 } else {
467 return NULL;
468 }
469 }
471 // Remove the current chunk from the tree. If it is not the last
472 // chunk in a list on a tree node, just unlink it.
473 // If it is the last chunk in the list (the next link is NULL),
474 // remove the node and repair the tree.
475 TreeChunk*
476 BinaryTreeDictionary::removeChunkFromTree(TreeChunk* tc) {
477 assert(tc != NULL, "Should not call with a NULL chunk");
478 assert(tc->isFree(), "Header is not marked correctly");
480 TreeList *newTL, *parentTL;
481 TreeChunk* retTC;
482 TreeList* tl = tc->list();
483 debug_only(
484 bool removing_only_chunk = false;
485 if (tl == _root) {
486 if ((_root->left() == NULL) && (_root->right() == NULL)) {
487 if (_root->count() == 1) {
488 assert(_root->head() == tc, "Should only be this one chunk");
489 removing_only_chunk = true;
490 }
491 }
492 }
493 )
494 assert(tl != NULL, "List should be set");
495 assert(tl->parent() == NULL || tl == tl->parent()->left() ||
496 tl == tl->parent()->right(), "list is inconsistent");
498 bool complicatedSplice = false;
500 retTC = tc;
501 // Removing this chunk can have the side effect of changing the node
502 // (TreeList*) in the tree. If the node is the root, update it.
503 TreeList* replacementTL = tl->removeChunkReplaceIfNeeded(tc);
504 assert(tc->isFree(), "Chunk should still be free");
505 assert(replacementTL->parent() == NULL ||
506 replacementTL == replacementTL->parent()->left() ||
507 replacementTL == replacementTL->parent()->right(),
508 "list is inconsistent");
509 if (tl == root()) {
510 assert(replacementTL->parent() == NULL, "Incorrectly replacing root");
511 set_root(replacementTL);
512 }
513 debug_only(
514 if (tl != replacementTL) {
515 assert(replacementTL->head() != NULL,
516 "If the tree list was replaced, it should not be a NULL list");
517 TreeList* rhl = replacementTL->head_as_TreeChunk()->list();
518 TreeList* rtl = TreeChunk::as_TreeChunk(replacementTL->tail())->list();
519 assert(rhl == replacementTL, "Broken head");
520 assert(rtl == replacementTL, "Broken tail");
521 assert(replacementTL->size() == tc->size(), "Broken size");
522 }
523 )
525 // Does the tree need to be repaired?
526 if (replacementTL->count() == 0) {
527 assert(replacementTL->head() == NULL &&
528 replacementTL->tail() == NULL, "list count is incorrect");
529 // Find the replacement node for the (soon to be empty) node being removed.
530 // if we have a single (or no) child, splice child in our stead
531 if (replacementTL->left() == NULL) {
532 // left is NULL so pick right. right may also be NULL.
533 newTL = replacementTL->right();
534 debug_only(replacementTL->clearRight();)
535 } else if (replacementTL->right() == NULL) {
536 // right is NULL
537 newTL = replacementTL->left();
538 debug_only(replacementTL->clearLeft();)
539 } else { // we have both children, so, by patriarchal convention,
540 // my replacement is least node in right sub-tree
541 complicatedSplice = true;
542 newTL = removeTreeMinimum(replacementTL->right());
543 assert(newTL != NULL && newTL->left() == NULL &&
544 newTL->right() == NULL, "sub-tree minimum exists");
545 }
546 // newTL is the replacement for the (soon to be empty) node.
547 // newTL may be NULL.
548 // should verify; we just cleanly excised our replacement
549 if (FLSVerifyDictionary) {
550 verifyTree();
551 }
552 // first make newTL my parent's child
553 if ((parentTL = replacementTL->parent()) == NULL) {
554 // newTL should be root
555 assert(tl == root(), "Incorrectly replacing root");
556 set_root(newTL);
557 if (newTL != NULL) {
558 newTL->clearParent();
559 }
560 } else if (parentTL->right() == replacementTL) {
561 // replacementTL is a right child
562 parentTL->setRight(newTL);
563 } else { // replacementTL is a left child
564 assert(parentTL->left() == replacementTL, "should be left child");
565 parentTL->setLeft(newTL);
566 }
567 debug_only(replacementTL->clearParent();)
568 if (complicatedSplice) { // we need newTL to get replacementTL's
569 // two children
570 assert(newTL != NULL &&
571 newTL->left() == NULL && newTL->right() == NULL,
572 "newTL should not have encumbrances from the past");
573 // we'd like to assert as below:
574 // assert(replacementTL->left() != NULL && replacementTL->right() != NULL,
575 // "else !complicatedSplice");
576 // ... however, the above assertion is too strong because we aren't
577 // guaranteed that replacementTL->right() is still NULL.
578 // Recall that we removed
579 // the right sub-tree minimum from replacementTL.
580 // That may well have been its right
581 // child! So we'll just assert half of the above:
582 assert(replacementTL->left() != NULL, "else !complicatedSplice");
583 newTL->setLeft(replacementTL->left());
584 newTL->setRight(replacementTL->right());
585 debug_only(
586 replacementTL->clearRight();
587 replacementTL->clearLeft();
588 )
589 }
590 assert(replacementTL->right() == NULL &&
591 replacementTL->left() == NULL &&
592 replacementTL->parent() == NULL,
593 "delete without encumbrances");
594 }
596 assert(totalSize() >= retTC->size(), "Incorrect total size");
597 dec_totalSize(retTC->size()); // size book-keeping
598 assert(totalFreeBlocks() > 0, "Incorrect total count");
599 set_totalFreeBlocks(totalFreeBlocks() - 1);
601 assert(retTC != NULL, "null chunk?");
602 assert(retTC->prev() == NULL && retTC->next() == NULL,
603 "should return without encumbrances");
604 if (FLSVerifyDictionary) {
605 verifyTree();
606 }
607 assert(!removing_only_chunk || _root == NULL, "root should be NULL");
608 return TreeChunk::as_TreeChunk(retTC);
609 }
611 // Remove the leftmost node (lm) in the tree and return it.
612 // If lm has a right child, link it to the left node of
613 // the parent of lm.
614 TreeList* BinaryTreeDictionary::removeTreeMinimum(TreeList* tl) {
615 assert(tl != NULL && tl->parent() != NULL, "really need a proper sub-tree");
616 // locate the subtree minimum by walking down left branches
617 TreeList* curTL = tl;
618 for (; curTL->left() != NULL; curTL = curTL->left());
619 // obviously curTL now has at most one child, a right child
620 if (curTL != root()) { // Should this test just be removed?
621 TreeList* parentTL = curTL->parent();
622 if (parentTL->left() == curTL) { // curTL is a left child
623 parentTL->setLeft(curTL->right());
624 } else {
625 // If the list tl has no left child, then curTL may be
626 // the right child of parentTL.
627 assert(parentTL->right() == curTL, "should be a right child");
628 parentTL->setRight(curTL->right());
629 }
630 } else {
631 // The only use of this method would not pass the root of the
632 // tree (as indicated by the assertion above that the tree list
633 // has a parent) but the specification does not explicitly exclude the
634 // passing of the root so accomodate it.
635 set_root(NULL);
636 }
637 debug_only(
638 curTL->clearParent(); // Test if this needs to be cleared
639 curTL->clearRight(); // recall, above, left child is already null
640 )
641 // we just excised a (non-root) node, we should still verify all tree invariants
642 if (FLSVerifyDictionary) {
643 verifyTree();
644 }
645 return curTL;
646 }
648 // Based on a simplification of the algorithm by Sleator and Tarjan (JACM 1985).
649 // The simplifications are the following:
650 // . we splay only when we delete (not when we insert)
651 // . we apply a single spay step per deletion/access
652 // By doing such partial splaying, we reduce the amount of restructuring,
653 // while getting a reasonably efficient search tree (we think).
654 // [Measurements will be needed to (in)validate this expectation.]
656 void BinaryTreeDictionary::semiSplayStep(TreeList* tc) {
657 // apply a semi-splay step at the given node:
658 // . if root, norting needs to be done
659 // . if child of root, splay once
660 // . else zig-zig or sig-zag depending on path from grandparent
661 if (root() == tc) return;
662 warning("*** Splaying not yet implemented; "
663 "tree operations may be inefficient ***");
664 }
666 void BinaryTreeDictionary::insertChunkInTree(FreeChunk* fc) {
667 TreeList *curTL, *prevTL;
668 size_t size = fc->size();
670 assert(size >= MIN_TREE_CHUNK_SIZE, "too small to be a TreeList");
671 if (FLSVerifyDictionary) {
672 verifyTree();
673 }
674 // XXX: do i need to clear the FreeChunk fields, let me do it just in case
675 // Revisit this later
677 fc->clearNext();
678 fc->linkPrev(NULL);
680 // work down from the _root, looking for insertion point
681 for (prevTL = curTL = root(); curTL != NULL;) {
682 if (curTL->size() == size) // exact match
683 break;
684 prevTL = curTL;
685 if (curTL->size() > size) { // follow left branch
686 curTL = curTL->left();
687 } else { // follow right branch
688 assert(curTL->size() < size, "size inconsistency");
689 curTL = curTL->right();
690 }
691 }
692 TreeChunk* tc = TreeChunk::as_TreeChunk(fc);
693 // This chunk is being returned to the binary tree. Its embedded
694 // TreeList should be unused at this point.
695 tc->initialize();
696 if (curTL != NULL) { // exact match
697 tc->set_list(curTL);
698 curTL->returnChunkAtTail(tc);
699 } else { // need a new node in tree
700 tc->clearNext();
701 tc->linkPrev(NULL);
702 TreeList* newTL = TreeList::as_TreeList(tc);
703 assert(((TreeChunk*)tc)->list() == newTL,
704 "List was not initialized correctly");
705 if (prevTL == NULL) { // we are the only tree node
706 assert(root() == NULL, "control point invariant");
707 set_root(newTL);
708 } else { // insert under prevTL ...
709 if (prevTL->size() < size) { // am right child
710 assert(prevTL->right() == NULL, "control point invariant");
711 prevTL->setRight(newTL);
712 } else { // am left child
713 assert(prevTL->size() > size && prevTL->left() == NULL, "cpt pt inv");
714 prevTL->setLeft(newTL);
715 }
716 }
717 }
718 assert(tc->list() != NULL, "Tree list should be set");
720 inc_totalSize(size);
721 // Method 'totalSizeInTree' walks through the every block in the
722 // tree, so it can cause significant performance loss if there are
723 // many blocks in the tree
724 assert(!FLSVerifyDictionary || totalSizeInTree(root()) == totalSize(), "_totalSize inconsistency");
725 set_totalFreeBlocks(totalFreeBlocks() + 1);
726 if (FLSVerifyDictionary) {
727 verifyTree();
728 }
729 }
731 size_t BinaryTreeDictionary::maxChunkSize() const {
732 verify_par_locked();
733 TreeList* tc = root();
734 if (tc == NULL) return 0;
735 for (; tc->right() != NULL; tc = tc->right());
736 return tc->size();
737 }
739 size_t BinaryTreeDictionary::totalListLength(TreeList* tl) const {
740 size_t res;
741 res = tl->count();
742 #ifdef ASSERT
743 size_t cnt;
744 FreeChunk* tc = tl->head();
745 for (cnt = 0; tc != NULL; tc = tc->next(), cnt++);
746 assert(res == cnt, "The count is not being maintained correctly");
747 #endif
748 return res;
749 }
751 size_t BinaryTreeDictionary::totalSizeInTree(TreeList* tl) const {
752 if (tl == NULL)
753 return 0;
754 return (tl->size() * totalListLength(tl)) +
755 totalSizeInTree(tl->left()) +
756 totalSizeInTree(tl->right());
757 }
759 double BinaryTreeDictionary::sum_of_squared_block_sizes(TreeList* const tl) const {
760 if (tl == NULL) {
761 return 0.0;
762 }
763 double size = (double)(tl->size());
764 double curr = size * size * totalListLength(tl);
765 curr += sum_of_squared_block_sizes(tl->left());
766 curr += sum_of_squared_block_sizes(tl->right());
767 return curr;
768 }
770 size_t BinaryTreeDictionary::totalFreeBlocksInTree(TreeList* tl) const {
771 if (tl == NULL)
772 return 0;
773 return totalListLength(tl) +
774 totalFreeBlocksInTree(tl->left()) +
775 totalFreeBlocksInTree(tl->right());
776 }
778 size_t BinaryTreeDictionary::numFreeBlocks() const {
779 assert(totalFreeBlocksInTree(root()) == totalFreeBlocks(),
780 "_totalFreeBlocks inconsistency");
781 return totalFreeBlocks();
782 }
784 size_t BinaryTreeDictionary::treeHeightHelper(TreeList* tl) const {
785 if (tl == NULL)
786 return 0;
787 return 1 + MAX2(treeHeightHelper(tl->left()),
788 treeHeightHelper(tl->right()));
789 }
791 size_t BinaryTreeDictionary::treeHeight() const {
792 return treeHeightHelper(root());
793 }
795 size_t BinaryTreeDictionary::totalNodesHelper(TreeList* tl) const {
796 if (tl == NULL) {
797 return 0;
798 }
799 return 1 + totalNodesHelper(tl->left()) +
800 totalNodesHelper(tl->right());
801 }
803 size_t BinaryTreeDictionary::totalNodesInTree(TreeList* tl) const {
804 return totalNodesHelper(root());
805 }
807 void BinaryTreeDictionary::dictCensusUpdate(size_t size, bool split, bool birth){
808 TreeList* nd = findList(size);
809 if (nd) {
810 if (split) {
811 if (birth) {
812 nd->increment_splitBirths();
813 nd->increment_surplus();
814 } else {
815 nd->increment_splitDeaths();
816 nd->decrement_surplus();
817 }
818 } else {
819 if (birth) {
820 nd->increment_coalBirths();
821 nd->increment_surplus();
822 } else {
823 nd->increment_coalDeaths();
824 nd->decrement_surplus();
825 }
826 }
827 }
828 // A list for this size may not be found (nd == 0) if
829 // This is a death where the appropriate list is now
830 // empty and has been removed from the list.
831 // This is a birth associated with a LinAB. The chunk
832 // for the LinAB is not in the dictionary.
833 }
835 bool BinaryTreeDictionary::coalDictOverPopulated(size_t size) {
836 if (FLSAlwaysCoalesceLarge) return true;
838 TreeList* list_of_size = findList(size);
839 // None of requested size implies overpopulated.
840 return list_of_size == NULL || list_of_size->coalDesired() <= 0 ||
841 list_of_size->count() > list_of_size->coalDesired();
842 }
844 // Closures for walking the binary tree.
845 // do_list() walks the free list in a node applying the closure
846 // to each free chunk in the list
847 // do_tree() walks the nodes in the binary tree applying do_list()
848 // to each list at each node.
850 class TreeCensusClosure : public StackObj {
851 protected:
852 virtual void do_list(FreeList* fl) = 0;
853 public:
854 virtual void do_tree(TreeList* tl) = 0;
855 };
857 class AscendTreeCensusClosure : public TreeCensusClosure {
858 public:
859 void do_tree(TreeList* tl) {
860 if (tl != NULL) {
861 do_tree(tl->left());
862 do_list(tl);
863 do_tree(tl->right());
864 }
865 }
866 };
868 class DescendTreeCensusClosure : public TreeCensusClosure {
869 public:
870 void do_tree(TreeList* tl) {
871 if (tl != NULL) {
872 do_tree(tl->right());
873 do_list(tl);
874 do_tree(tl->left());
875 }
876 }
877 };
879 // For each list in the tree, calculate the desired, desired
880 // coalesce, count before sweep, and surplus before sweep.
881 class BeginSweepClosure : public AscendTreeCensusClosure {
882 double _percentage;
883 float _inter_sweep_current;
884 float _inter_sweep_estimate;
885 float _intra_sweep_estimate;
887 public:
888 BeginSweepClosure(double p, float inter_sweep_current,
889 float inter_sweep_estimate,
890 float intra_sweep_estimate) :
891 _percentage(p),
892 _inter_sweep_current(inter_sweep_current),
893 _inter_sweep_estimate(inter_sweep_estimate),
894 _intra_sweep_estimate(intra_sweep_estimate) { }
896 void do_list(FreeList* fl) {
897 double coalSurplusPercent = _percentage;
898 fl->compute_desired(_inter_sweep_current, _inter_sweep_estimate, _intra_sweep_estimate);
899 fl->set_coalDesired((ssize_t)((double)fl->desired() * coalSurplusPercent));
900 fl->set_beforeSweep(fl->count());
901 fl->set_bfrSurp(fl->surplus());
902 }
903 };
905 // Used to search the tree until a condition is met.
906 // Similar to TreeCensusClosure but searches the
907 // tree and returns promptly when found.
909 class TreeSearchClosure : public StackObj {
910 protected:
911 virtual bool do_list(FreeList* fl) = 0;
912 public:
913 virtual bool do_tree(TreeList* tl) = 0;
914 };
916 #if 0 // Don't need this yet but here for symmetry.
917 class AscendTreeSearchClosure : public TreeSearchClosure {
918 public:
919 bool do_tree(TreeList* tl) {
920 if (tl != NULL) {
921 if (do_tree(tl->left())) return true;
922 if (do_list(tl)) return true;
923 if (do_tree(tl->right())) return true;
924 }
925 return false;
926 }
927 };
928 #endif
930 class DescendTreeSearchClosure : public TreeSearchClosure {
931 public:
932 bool do_tree(TreeList* tl) {
933 if (tl != NULL) {
934 if (do_tree(tl->right())) return true;
935 if (do_list(tl)) return true;
936 if (do_tree(tl->left())) return true;
937 }
938 return false;
939 }
940 };
942 // Searches the tree for a chunk that ends at the
943 // specified address.
944 class EndTreeSearchClosure : public DescendTreeSearchClosure {
945 HeapWord* _target;
946 FreeChunk* _found;
948 public:
949 EndTreeSearchClosure(HeapWord* target) : _target(target), _found(NULL) {}
950 bool do_list(FreeList* fl) {
951 FreeChunk* item = fl->head();
952 while (item != NULL) {
953 if (item->end() == _target) {
954 _found = item;
955 return true;
956 }
957 item = item->next();
958 }
959 return false;
960 }
961 FreeChunk* found() { return _found; }
962 };
964 FreeChunk* BinaryTreeDictionary::find_chunk_ends_at(HeapWord* target) const {
965 EndTreeSearchClosure etsc(target);
966 bool found_target = etsc.do_tree(root());
967 assert(found_target || etsc.found() == NULL, "Consistency check");
968 assert(!found_target || etsc.found() != NULL, "Consistency check");
969 return etsc.found();
970 }
972 void BinaryTreeDictionary::beginSweepDictCensus(double coalSurplusPercent,
973 float inter_sweep_current, float inter_sweep_estimate, float intra_sweep_estimate) {
974 BeginSweepClosure bsc(coalSurplusPercent, inter_sweep_current,
975 inter_sweep_estimate,
976 intra_sweep_estimate);
977 bsc.do_tree(root());
978 }
980 // Closures and methods for calculating total bytes returned to the
981 // free lists in the tree.
982 NOT_PRODUCT(
983 class InitializeDictReturnedBytesClosure : public AscendTreeCensusClosure {
984 public:
985 void do_list(FreeList* fl) {
986 fl->set_returnedBytes(0);
987 }
988 };
990 void BinaryTreeDictionary::initializeDictReturnedBytes() {
991 InitializeDictReturnedBytesClosure idrb;
992 idrb.do_tree(root());
993 }
995 class ReturnedBytesClosure : public AscendTreeCensusClosure {
996 size_t _dictReturnedBytes;
997 public:
998 ReturnedBytesClosure() { _dictReturnedBytes = 0; }
999 void do_list(FreeList* fl) {
1000 _dictReturnedBytes += fl->returnedBytes();
1001 }
1002 size_t dictReturnedBytes() { return _dictReturnedBytes; }
1003 };
1005 size_t BinaryTreeDictionary::sumDictReturnedBytes() {
1006 ReturnedBytesClosure rbc;
1007 rbc.do_tree(root());
1009 return rbc.dictReturnedBytes();
1010 }
1012 // Count the number of entries in the tree.
1013 class treeCountClosure : public DescendTreeCensusClosure {
1014 public:
1015 uint count;
1016 treeCountClosure(uint c) { count = c; }
1017 void do_list(FreeList* fl) {
1018 count++;
1019 }
1020 };
1022 size_t BinaryTreeDictionary::totalCount() {
1023 treeCountClosure ctc(0);
1024 ctc.do_tree(root());
1025 return ctc.count;
1026 }
1027 )
1029 // Calculate surpluses for the lists in the tree.
1030 class setTreeSurplusClosure : public AscendTreeCensusClosure {
1031 double percentage;
1032 public:
1033 setTreeSurplusClosure(double v) { percentage = v; }
1034 void do_list(FreeList* fl) {
1035 double splitSurplusPercent = percentage;
1036 fl->set_surplus(fl->count() -
1037 (ssize_t)((double)fl->desired() * splitSurplusPercent));
1038 }
1039 };
1041 void BinaryTreeDictionary::setTreeSurplus(double splitSurplusPercent) {
1042 setTreeSurplusClosure sts(splitSurplusPercent);
1043 sts.do_tree(root());
1044 }
1046 // Set hints for the lists in the tree.
1047 class setTreeHintsClosure : public DescendTreeCensusClosure {
1048 size_t hint;
1049 public:
1050 setTreeHintsClosure(size_t v) { hint = v; }
1051 void do_list(FreeList* fl) {
1052 fl->set_hint(hint);
1053 assert(fl->hint() == 0 || fl->hint() > fl->size(),
1054 "Current hint is inconsistent");
1055 if (fl->surplus() > 0) {
1056 hint = fl->size();
1057 }
1058 }
1059 };
1061 void BinaryTreeDictionary::setTreeHints(void) {
1062 setTreeHintsClosure sth(0);
1063 sth.do_tree(root());
1064 }
1066 // Save count before previous sweep and splits and coalesces.
1067 class clearTreeCensusClosure : public AscendTreeCensusClosure {
1068 void do_list(FreeList* fl) {
1069 fl->set_prevSweep(fl->count());
1070 fl->set_coalBirths(0);
1071 fl->set_coalDeaths(0);
1072 fl->set_splitBirths(0);
1073 fl->set_splitDeaths(0);
1074 }
1075 };
1077 void BinaryTreeDictionary::clearTreeCensus(void) {
1078 clearTreeCensusClosure ctc;
1079 ctc.do_tree(root());
1080 }
1082 // Do reporting and post sweep clean up.
1083 void BinaryTreeDictionary::endSweepDictCensus(double splitSurplusPercent) {
1084 // Does walking the tree 3 times hurt?
1085 setTreeSurplus(splitSurplusPercent);
1086 setTreeHints();
1087 if (PrintGC && Verbose) {
1088 reportStatistics();
1089 }
1090 clearTreeCensus();
1091 }
1093 // Print summary statistics
1094 void BinaryTreeDictionary::reportStatistics() const {
1095 verify_par_locked();
1096 gclog_or_tty->print("Statistics for BinaryTreeDictionary:\n"
1097 "------------------------------------\n");
1098 size_t totalSize = totalChunkSize(debug_only(NULL));
1099 size_t freeBlocks = numFreeBlocks();
1100 gclog_or_tty->print("Total Free Space: %d\n", totalSize);
1101 gclog_or_tty->print("Max Chunk Size: %d\n", maxChunkSize());
1102 gclog_or_tty->print("Number of Blocks: %d\n", freeBlocks);
1103 if (freeBlocks > 0) {
1104 gclog_or_tty->print("Av. Block Size: %d\n", totalSize/freeBlocks);
1105 }
1106 gclog_or_tty->print("Tree Height: %d\n", treeHeight());
1107 }
1109 // Print census information - counts, births, deaths, etc.
1110 // for each list in the tree. Also print some summary
1111 // information.
1112 class PrintTreeCensusClosure : public AscendTreeCensusClosure {
1113 int _print_line;
1114 size_t _totalFree;
1115 FreeList _total;
1117 public:
1118 PrintTreeCensusClosure() {
1119 _print_line = 0;
1120 _totalFree = 0;
1121 }
1122 FreeList* total() { return &_total; }
1123 size_t totalFree() { return _totalFree; }
1124 void do_list(FreeList* fl) {
1125 if (++_print_line >= 40) {
1126 FreeList::print_labels_on(gclog_or_tty, "size");
1127 _print_line = 0;
1128 }
1129 fl->print_on(gclog_or_tty);
1130 _totalFree += fl->count() * fl->size() ;
1131 total()->set_count( total()->count() + fl->count() );
1132 total()->set_bfrSurp( total()->bfrSurp() + fl->bfrSurp() );
1133 total()->set_surplus( total()->splitDeaths() + fl->surplus() );
1134 total()->set_desired( total()->desired() + fl->desired() );
1135 total()->set_prevSweep( total()->prevSweep() + fl->prevSweep() );
1136 total()->set_beforeSweep(total()->beforeSweep() + fl->beforeSweep());
1137 total()->set_coalBirths( total()->coalBirths() + fl->coalBirths() );
1138 total()->set_coalDeaths( total()->coalDeaths() + fl->coalDeaths() );
1139 total()->set_splitBirths(total()->splitBirths() + fl->splitBirths());
1140 total()->set_splitDeaths(total()->splitDeaths() + fl->splitDeaths());
1141 }
1142 };
1144 void BinaryTreeDictionary::printDictCensus(void) const {
1146 gclog_or_tty->print("\nBinaryTree\n");
1147 FreeList::print_labels_on(gclog_or_tty, "size");
1148 PrintTreeCensusClosure ptc;
1149 ptc.do_tree(root());
1151 FreeList* total = ptc.total();
1152 FreeList::print_labels_on(gclog_or_tty, " ");
1153 total->print_on(gclog_or_tty, "TOTAL\t");
1154 gclog_or_tty->print(
1155 "totalFree(words): " SIZE_FORMAT_W(16)
1156 " growth: %8.5f deficit: %8.5f\n",
1157 ptc.totalFree(),
1158 (double)(total->splitBirths() + total->coalBirths()
1159 - total->splitDeaths() - total->coalDeaths())
1160 /(total->prevSweep() != 0 ? (double)total->prevSweep() : 1.0),
1161 (double)(total->desired() - total->count())
1162 /(total->desired() != 0 ? (double)total->desired() : 1.0));
1163 }
1165 class PrintFreeListsClosure : public AscendTreeCensusClosure {
1166 outputStream* _st;
1167 int _print_line;
1169 public:
1170 PrintFreeListsClosure(outputStream* st) {
1171 _st = st;
1172 _print_line = 0;
1173 }
1174 void do_list(FreeList* fl) {
1175 if (++_print_line >= 40) {
1176 FreeList::print_labels_on(_st, "size");
1177 _print_line = 0;
1178 }
1179 fl->print_on(gclog_or_tty);
1180 size_t sz = fl->size();
1181 for (FreeChunk* fc = fl->head(); fc != NULL;
1182 fc = fc->next()) {
1183 _st->print_cr("\t[" PTR_FORMAT "," PTR_FORMAT ") %s",
1184 fc, (HeapWord*)fc + sz,
1185 fc->cantCoalesce() ? "\t CC" : "");
1186 }
1187 }
1188 };
1190 void BinaryTreeDictionary::print_free_lists(outputStream* st) const {
1192 FreeList::print_labels_on(st, "size");
1193 PrintFreeListsClosure pflc(st);
1194 pflc.do_tree(root());
1195 }
1197 // Verify the following tree invariants:
1198 // . _root has no parent
1199 // . parent and child point to each other
1200 // . each node's key correctly related to that of its child(ren)
1201 void BinaryTreeDictionary::verifyTree() const {
1202 guarantee(root() == NULL || totalFreeBlocks() == 0 ||
1203 totalSize() != 0, "_totalSize should't be 0?");
1204 guarantee(root() == NULL || root()->parent() == NULL, "_root shouldn't have parent");
1205 verifyTreeHelper(root());
1206 }
1208 size_t BinaryTreeDictionary::verifyPrevFreePtrs(TreeList* tl) {
1209 size_t ct = 0;
1210 for (FreeChunk* curFC = tl->head(); curFC != NULL; curFC = curFC->next()) {
1211 ct++;
1212 assert(curFC->prev() == NULL || curFC->prev()->isFree(),
1213 "Chunk should be free");
1214 }
1215 return ct;
1216 }
1218 // Note: this helper is recursive rather than iterative, so use with
1219 // caution on very deep trees; and watch out for stack overflow errors;
1220 // In general, to be used only for debugging.
1221 void BinaryTreeDictionary::verifyTreeHelper(TreeList* tl) const {
1222 if (tl == NULL)
1223 return;
1224 guarantee(tl->size() != 0, "A list must has a size");
1225 guarantee(tl->left() == NULL || tl->left()->parent() == tl,
1226 "parent<-/->left");
1227 guarantee(tl->right() == NULL || tl->right()->parent() == tl,
1228 "parent<-/->right");;
1229 guarantee(tl->left() == NULL || tl->left()->size() < tl->size(),
1230 "parent !> left");
1231 guarantee(tl->right() == NULL || tl->right()->size() > tl->size(),
1232 "parent !< left");
1233 guarantee(tl->head() == NULL || tl->head()->isFree(), "!Free");
1234 guarantee(tl->head() == NULL || tl->head_as_TreeChunk()->list() == tl,
1235 "list inconsistency");
1236 guarantee(tl->count() > 0 || (tl->head() == NULL && tl->tail() == NULL),
1237 "list count is inconsistent");
1238 guarantee(tl->count() > 1 || tl->head() == tl->tail(),
1239 "list is incorrectly constructed");
1240 size_t count = verifyPrevFreePtrs(tl);
1241 guarantee(count == (size_t)tl->count(), "Node count is incorrect");
1242 if (tl->head() != NULL) {
1243 tl->head_as_TreeChunk()->verifyTreeChunkList();
1244 }
1245 verifyTreeHelper(tl->left());
1246 verifyTreeHelper(tl->right());
1247 }
1249 void BinaryTreeDictionary::verify() const {
1250 verifyTree();
1251 guarantee(totalSize() == totalSizeInTree(root()), "Total Size inconsistency");
1252 }