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