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