1 /*
2 * Copyright (c) 2001, 2008, 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 "incls/_precompiled.incl"
26 # include "incls/_binaryTreeDictionary.cpp.incl"
27
28 ////////////////////////////////////////////////////////////////////////////////
29 // A binary tree based search structure for free blocks.
30 // This is currently used in the Concurrent Mark&Sweep implementation.
31 ////////////////////////////////////////////////////////////////////////////////
32
33 TreeChunk* TreeChunk::as_TreeChunk(FreeChunk* fc) {
34 // Do some assertion checking here.
35 return (TreeChunk*) fc;
36 }
37
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 }
50
51
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 }
71
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 }
90
91 TreeList* TreeList::removeChunkReplaceIfNeeded(TreeChunk* tc) {
92
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");
102
103 FreeChunk* prevFC = tc->prev();
104 TreeChunk* nextTC = TreeChunk::as_TreeChunk(tc->next());
105 assert(list != NULL, "should have at least the target chunk");
106
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 }
166
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();
197
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");
213
214 FreeChunk* fc = tail();
215 fc->linkAfter(chunk);
216 link_tail(chunk);
217
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 }
224
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");
236
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 }
251
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 }
257
258 TreeChunk* TreeList::first_available() {
259 assert(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 }
270
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 assert(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 }
295
296 BinaryTreeDictionary::BinaryTreeDictionary(MemRegion mr, bool splay):
297 _splay(splay)
298 {
299 assert(mr.byte_size() > MIN_TREE_CHUNK_SIZE, "minimum chunk size");
300
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 }
309
310 void BinaryTreeDictionary::inc_totalSize(size_t inc) {
311 _totalSize = _totalSize + inc;
312 }
313
314 void BinaryTreeDictionary::dec_totalSize(size_t dec) {
315 _totalSize = _totalSize - dec;
316 }
317
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 }
324
325 void BinaryTreeDictionary::reset(HeapWord* addr, size_t byte_size) {
326 MemRegion mr(addr, heap_word_size(byte_size));
327 reset(mr);
328 }
329
330 void BinaryTreeDictionary::reset() {
331 set_root(NULL);
332 set_totalSize(0);
333 set_totalFreeBlocks(0);
334 }
335
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) {
379
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 }
426
427 if (FLSVerifyDictionary) {
428 verify();
429 }
430 return retTC;
431 }
432
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 }
439
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 }
449
450
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 }
460
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 }
470
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");
479
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");
497
498 bool complicatedSplice = false;
499
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 )
524
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 }
595
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);
600
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 }
610
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 }
647
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.]
655
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 }
665
666 void BinaryTreeDictionary::insertChunkInTree(FreeChunk* fc) {
667 TreeList *curTL, *prevTL;
668 size_t size = fc->size();
669
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
676
677 fc->clearNext();
678 fc->linkPrev(NULL);
679
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");
719
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 }
730
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 }
738
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 }
750
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 }
758
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 }
769
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 }
777
778 size_t BinaryTreeDictionary::numFreeBlocks() const {
779 assert(totalFreeBlocksInTree(root()) == totalFreeBlocks(),
780 "_totalFreeBlocks inconsistency");
781 return totalFreeBlocks();
782 }
783
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 }
790
791 size_t BinaryTreeDictionary::treeHeight() const {
792 return treeHeightHelper(root());
793 }
794
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 }
802
803 size_t BinaryTreeDictionary::totalNodesInTree(TreeList* tl) const {
804 return totalNodesHelper(root());
805 }
806
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 }
834
835 bool BinaryTreeDictionary::coalDictOverPopulated(size_t size) {
836 if (FLSAlwaysCoalesceLarge) return true;
837
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 }
843
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.
849
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 };
856
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 };
867
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 };
878
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;
886
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) { }
895
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 };
904
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.
908
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 };
915
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
929
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 };
941
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;
947
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 };
963
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 }
971
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 }
979
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 };
989
990 void BinaryTreeDictionary::initializeDictReturnedBytes() {
991 InitializeDictReturnedBytesClosure idrb;
992 idrb.do_tree(root());
993 }
994
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 };
1004
1005 size_t BinaryTreeDictionary::sumDictReturnedBytes() {
1006 ReturnedBytesClosure rbc;
1007 rbc.do_tree(root());
1008
1009 return rbc.dictReturnedBytes();
1010 }
1011
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 };
1021
1022 size_t BinaryTreeDictionary::totalCount() {
1023 treeCountClosure ctc(0);
1024 ctc.do_tree(root());
1025 return ctc.count;
1026 }
1027 )
1028
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 };
1040
1041 void BinaryTreeDictionary::setTreeSurplus(double splitSurplusPercent) {
1042 setTreeSurplusClosure sts(splitSurplusPercent);
1043 sts.do_tree(root());
1044 }
1045
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 };
1060
1061 void BinaryTreeDictionary::setTreeHints(void) {
1062 setTreeHintsClosure sth(0);
1063 sth.do_tree(root());
1064 }
1065
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 };
1076
1077 void BinaryTreeDictionary::clearTreeCensus(void) {
1078 clearTreeCensusClosure ctc;
1079 ctc.do_tree(root());
1080 }
1081
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 }
1092
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 }
1108
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;
1116
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 };
1143
1144 void BinaryTreeDictionary::printDictCensus(void) const {
1145
1146 gclog_or_tty->print("\nBinaryTree\n");
1147 FreeList::print_labels_on(gclog_or_tty, "size");
1148 PrintTreeCensusClosure ptc;
1149 ptc.do_tree(root());
1150
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 }
1164
1165 class PrintFreeListsClosure : public AscendTreeCensusClosure {
1166 outputStream* _st;
1167 int _print_line;
1168
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 };
1189
1190 void BinaryTreeDictionary::print_free_lists(outputStream* st) const {
1191
1192 FreeList::print_labels_on(st, "size");
1193 PrintFreeListsClosure pflc(st);
1194 pflc.do_tree(root());
1195 }
1196
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 }
1207
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 }
1217
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 }
1248
1249 void BinaryTreeDictionary::verify() const {
1250 verifyTree();
1251 guarantee(totalSize() == totalSizeInTree(root()), "Total Size inconsistency");
1252 }