Mercurial > hg > truffle
annotate src/share/vm/gc_implementation/concurrentMarkSweep/binaryTreeDictionary.cpp @ 94:0834225a7916
6634032: CMS: Need CMSInitiatingPermOccupancyFraction for perm, divorcing from CMSInitiatingOccupancyFraction
Summary: The option CMSInitiatingPermOccupancyFraction now controls perm triggering threshold. Even though the actual value of the threshold has not yet been changed, so there is no change in policy, we now have the infrastructure in place for dynamically deciding when to collect the perm gen, an issue that will be addressed in the near future.
Reviewed-by: jmasa
| author | ysr |
|---|---|
| date | Sun, 16 Mar 2008 21:57:25 -0700 |
| parents | 6432c3bb6240 |
| children | d1605aabd0a1 12eea04c8b06 |
| rev | line source |
|---|---|
| 0 | 1 /* |
| 2 * Copyright 2001-2006 Sun Microsystems, Inc. All Rights Reserved. | |
| 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. | |
| 4 * | |
| 5 * This code is free software; you can redistribute it and/or modify it | |
| 6 * under the terms of the GNU General Public License version 2 only, as | |
| 7 * published by the Free Software Foundation. | |
| 8 * | |
| 9 * This code is distributed in the hope that it will be useful, but WITHOUT | |
| 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
| 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
| 12 * version 2 for more details (a copy is included in the LICENSE file that | |
| 13 * accompanied this code). | |
| 14 * | |
| 15 * You should have received a copy of the GNU General Public License version | |
| 16 * 2 along with this work; if not, write to the Free Software Foundation, | |
| 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. | |
| 18 * | |
| 19 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, | |
| 20 * CA 95054 USA or visit www.sun.com if you need additional information or | |
| 21 * have any questions. | |
| 22 * | |
| 23 */ | |
| 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 } |