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