Mercurial > hg > graal-jvmci-8
annotate src/share/vm/memory/binaryTreeDictionary.cpp @ 10241:d17700c82d7d
8006088: Incompatible heap size flags accepted by VM
Summary: Make processing of minimum, initial and maximum heap size more intiutive by removing previous limitations on allowed values, and make error reporting consistent. Further, fix errors in ergonomic heap sizing.
Reviewed-by: johnc, jwilhelm, tamao
| author | tschatzl |
|---|---|
| date | Mon, 06 May 2013 17:19:42 +0200 |
| parents | 3c9bc17b9403 |
| children | de88570fabfc |
| rev | line source |
|---|---|
| 0 | 1 /* |
| 6026 | 2 * Copyright (c) 2001, 2012, Oracle and/or its affiliates. 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 * | |
|
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
1489
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
1489
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
1489
diff
changeset
|
21 * questions. |
| 0 | 22 * |
| 23 */ | |
| 24 | |
| 1972 | 25 #include "precompiled.hpp" |
|
8001
db9981fd3124
8005915: Unify SERIALGC and INCLUDE_ALTERNATE_GCS
jprovino
parents:
7446
diff
changeset
|
26 #include "utilities/macros.hpp" |
| 1972 | 27 #include "gc_implementation/shared/allocationStats.hpp" |
| 6026 | 28 #include "memory/binaryTreeDictionary.hpp" |
| 6885 | 29 #include "memory/freeList.hpp" |
| 30 #include "memory/freeBlockDictionary.hpp" | |
| 31 #include "memory/metablock.hpp" | |
| 32 #include "memory/metachunk.hpp" | |
| 1972 | 33 #include "runtime/globals.hpp" |
| 34 #include "utilities/ostream.hpp" | |
|
8001
db9981fd3124
8005915: Unify SERIALGC and INCLUDE_ALTERNATE_GCS
jprovino
parents:
7446
diff
changeset
|
35 #include "utilities/macros.hpp" |
|
db9981fd3124
8005915: Unify SERIALGC and INCLUDE_ALTERNATE_GCS
jprovino
parents:
7446
diff
changeset
|
36 #if INCLUDE_ALL_GCS |
| 6885 | 37 #include "gc_implementation/concurrentMarkSweep/adaptiveFreeList.hpp" |
| 38 #include "gc_implementation/concurrentMarkSweep/freeChunk.hpp" | |
| 6026 | 39 #include "gc_implementation/shared/spaceDecorator.hpp" |
| 40 #include "gc_implementation/concurrentMarkSweep/freeChunk.hpp" | |
|
8001
db9981fd3124
8005915: Unify SERIALGC and INCLUDE_ALTERNATE_GCS
jprovino
parents:
7446
diff
changeset
|
41 #endif // INCLUDE_ALL_GCS |
| 0 | 42 |
| 43 //////////////////////////////////////////////////////////////////////////////// | |
| 44 // A binary tree based search structure for free blocks. | |
| 45 // This is currently used in the Concurrent Mark&Sweep implementation. | |
| 46 //////////////////////////////////////////////////////////////////////////////// | |
| 47 | |
| 6885 | 48 template <class Chunk_t, template <class> class FreeList_t> |
| 49 size_t TreeChunk<Chunk_t, FreeList_t>::_min_tree_chunk_size = sizeof(TreeChunk<Chunk_t, FreeList_t>)/HeapWordSize; | |
| 50 | |
| 51 template <class Chunk_t, template <class> class FreeList_t> | |
| 52 TreeChunk<Chunk_t, FreeList_t>* TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(Chunk_t* fc) { | |
| 0 | 53 // Do some assertion checking here. |
| 6885 | 54 return (TreeChunk<Chunk_t, FreeList_t>*) fc; |
| 0 | 55 } |
| 56 | |
| 6885 | 57 template <class Chunk_t, template <class> class FreeList_t> |
| 58 void TreeChunk<Chunk_t, FreeList_t>::verify_tree_chunk_list() const { | |
| 59 TreeChunk<Chunk_t, FreeList_t>* nextTC = (TreeChunk<Chunk_t, FreeList_t>*)next(); | |
| 0 | 60 if (prev() != NULL) { // interior list node shouldn'r have tree fields |
| 61 guarantee(embedded_list()->parent() == NULL && embedded_list()->left() == NULL && | |
| 62 embedded_list()->right() == NULL, "should be clear"); | |
| 63 } | |
| 64 if (nextTC != NULL) { | |
| 65 guarantee(as_TreeChunk(nextTC->prev()) == this, "broken chain"); | |
| 66 guarantee(nextTC->size() == size(), "wrong size"); | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
67 nextTC->verify_tree_chunk_list(); |
| 0 | 68 } |
| 69 } | |
| 70 | |
| 6885 | 71 template <class Chunk_t, template <class> class FreeList_t> |
|
7446
e51c9860cf66
8005082: NPG: Add specialized Metachunk sizes for reflection and anonymous classloaders
jmasa
parents:
7178
diff
changeset
|
72 TreeList<Chunk_t, FreeList_t>::TreeList() : _parent(NULL), |
|
e51c9860cf66
8005082: NPG: Add specialized Metachunk sizes for reflection and anonymous classloaders
jmasa
parents:
7178
diff
changeset
|
73 _left(NULL), _right(NULL) {} |
| 0 | 74 |
| 6885 | 75 template <class Chunk_t, template <class> class FreeList_t> |
| 76 TreeList<Chunk_t, FreeList_t>* | |
| 77 TreeList<Chunk_t, FreeList_t>::as_TreeList(TreeChunk<Chunk_t,FreeList_t>* tc) { | |
| 0 | 78 // This first free chunk in the list will be the tree list. |
| 6885 | 79 assert((tc->size() >= (TreeChunk<Chunk_t, FreeList_t>::min_size())), |
| 80 "Chunk is too small for a TreeChunk"); | |
| 81 TreeList<Chunk_t, FreeList_t>* tl = tc->embedded_list(); | |
| 82 tl->initialize(); | |
| 0 | 83 tc->set_list(tl); |
| 84 tl->set_size(tc->size()); | |
| 85 tl->link_head(tc); | |
| 86 tl->link_tail(tc); | |
| 87 tl->set_count(1); | |
|
7446
e51c9860cf66
8005082: NPG: Add specialized Metachunk sizes for reflection and anonymous classloaders
jmasa
parents:
7178
diff
changeset
|
88 assert(tl->parent() == NULL, "Should be clear"); |
| 6885 | 89 return tl; |
| 90 } | |
| 91 | |
| 92 | |
| 93 template <class Chunk_t, template <class> class FreeList_t> | |
| 94 TreeList<Chunk_t, FreeList_t>* | |
| 95 get_chunk(size_t size, enum FreeBlockDictionary<Chunk_t>::Dither dither) { | |
| 96 FreeBlockDictionary<Chunk_t>::verify_par_locked(); | |
| 97 Chunk_t* res = get_chunk_from_tree(size, dither); | |
| 98 assert(res == NULL || res->is_free(), | |
| 99 "Should be returning a free chunk"); | |
| 100 assert(dither != FreeBlockDictionary<Chunk_t>::exactly || | |
| 101 res->size() == size, "Not correct size"); | |
| 102 return res; | |
| 103 } | |
| 104 | |
| 105 template <class Chunk_t, template <class> class FreeList_t> | |
| 106 TreeList<Chunk_t, FreeList_t>* | |
| 107 TreeList<Chunk_t, FreeList_t>::as_TreeList(HeapWord* addr, size_t size) { | |
| 108 TreeChunk<Chunk_t, FreeList_t>* tc = (TreeChunk<Chunk_t, FreeList_t>*) addr; | |
| 109 assert((size >= TreeChunk<Chunk_t, FreeList_t>::min_size()), | |
| 110 "Chunk is too small for a TreeChunk"); | |
| 111 // The space will have been mangled initially but | |
| 112 // is not remangled when a Chunk_t is returned to the free list | |
| 113 // (since it is used to maintain the chunk on the free list). | |
| 114 tc->assert_is_mangled(); | |
| 115 tc->set_size(size); | |
| 116 tc->link_prev(NULL); | |
| 117 tc->link_next(NULL); | |
| 118 TreeList<Chunk_t, FreeList_t>* tl = TreeList<Chunk_t, FreeList_t>::as_TreeList(tc); | |
| 0 | 119 return tl; |
| 120 } | |
|
1145
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
121 |
| 6885 | 122 |
|
8001
db9981fd3124
8005915: Unify SERIALGC and INCLUDE_ALTERNATE_GCS
jprovino
parents:
7446
diff
changeset
|
123 #if INCLUDE_ALL_GCS |
| 6885 | 124 // Specialize for AdaptiveFreeList which tries to avoid |
| 125 // splitting a chunk of a size that is under populated in favor of | |
| 126 // an over populated size. The general get_better_list() just returns | |
| 127 // the current list. | |
| 128 template <> | |
| 129 TreeList<FreeChunk, AdaptiveFreeList>* | |
| 130 TreeList<FreeChunk, AdaptiveFreeList>::get_better_list( | |
| 131 BinaryTreeDictionary<FreeChunk, ::AdaptiveFreeList>* dictionary) { | |
| 132 // A candidate chunk has been found. If it is already under | |
| 133 // populated, get a chunk associated with the hint for this | |
| 134 // chunk. | |
| 135 | |
| 136 TreeList<FreeChunk, ::AdaptiveFreeList>* curTL = this; | |
| 137 if (surplus() <= 0) { | |
| 138 /* Use the hint to find a size with a surplus, and reset the hint. */ | |
| 139 TreeList<FreeChunk, ::AdaptiveFreeList>* hintTL = this; | |
| 140 while (hintTL->hint() != 0) { | |
| 141 assert(hintTL->hint() > hintTL->size(), | |
| 142 "hint points in the wrong direction"); | |
| 143 hintTL = dictionary->find_list(hintTL->hint()); | |
| 144 assert(curTL != hintTL, "Infinite loop"); | |
| 145 if (hintTL == NULL || | |
| 146 hintTL == curTL /* Should not happen but protect against it */ ) { | |
| 147 // No useful hint. Set the hint to NULL and go on. | |
| 148 curTL->set_hint(0); | |
| 149 break; | |
| 150 } | |
| 151 assert(hintTL->size() > curTL->size(), "hint is inconsistent"); | |
| 152 if (hintTL->surplus() > 0) { | |
| 153 // The hint led to a list that has a surplus. Use it. | |
| 154 // Set the hint for the candidate to an overpopulated | |
| 155 // size. | |
| 156 curTL->set_hint(hintTL->size()); | |
| 157 // Change the candidate. | |
| 158 curTL = hintTL; | |
| 159 break; | |
| 160 } | |
| 161 } | |
| 162 } | |
| 163 return curTL; | |
| 164 } | |
|
8001
db9981fd3124
8005915: Unify SERIALGC and INCLUDE_ALTERNATE_GCS
jprovino
parents:
7446
diff
changeset
|
165 #endif // INCLUDE_ALL_GCS |
| 6885 | 166 |
| 167 template <class Chunk_t, template <class> class FreeList_t> | |
| 168 TreeList<Chunk_t, FreeList_t>* | |
| 169 TreeList<Chunk_t, FreeList_t>::get_better_list( | |
| 170 BinaryTreeDictionary<Chunk_t, FreeList_t>* dictionary) { | |
| 171 return this; | |
| 0 | 172 } |
| 173 | |
| 6885 | 174 template <class Chunk_t, template <class> class FreeList_t> |
| 175 TreeList<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::remove_chunk_replace_if_needed(TreeChunk<Chunk_t, FreeList_t>* tc) { | |
| 0 | 176 |
| 6885 | 177 TreeList<Chunk_t, FreeList_t>* retTL = this; |
| 178 Chunk_t* list = head(); | |
| 0 | 179 assert(!list || list != list->next(), "Chunk on list twice"); |
| 180 assert(tc != NULL, "Chunk being removed is NULL"); | |
| 181 assert(parent() == NULL || this == parent()->left() || | |
| 182 this == parent()->right(), "list is inconsistent"); | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
183 assert(tc->is_free(), "Header is not marked correctly"); |
| 0 | 184 assert(head() == NULL || head()->prev() == NULL, "list invariant"); |
| 185 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); | |
| 186 | |
| 6885 | 187 Chunk_t* prevFC = tc->prev(); |
| 188 TreeChunk<Chunk_t, FreeList_t>* nextTC = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(tc->next()); | |
| 0 | 189 assert(list != NULL, "should have at least the target chunk"); |
| 190 | |
| 191 // Is this the first item on the list? | |
| 192 if (tc == list) { | |
| 6885 | 193 // The "getChunk..." functions for a TreeList<Chunk_t, FreeList_t> will not return the |
| 0 | 194 // first chunk in the list unless it is the last chunk in the list |
| 195 // because the first chunk is also acting as the tree node. | |
| 196 // When coalescing happens, however, the first chunk in the a tree | |
| 197 // list can be the start of a free range. Free ranges are removed | |
| 198 // from the free lists so that they are not available to be | |
| 199 // allocated when the sweeper yields (giving up the free list lock) | |
| 200 // to allow mutator activity. If this chunk is the first in the | |
| 201 // list and is not the last in the list, do the work to copy the | |
| 6885 | 202 // TreeList<Chunk_t, FreeList_t> from the first chunk to the next chunk and update all |
| 203 // the TreeList<Chunk_t, FreeList_t> pointers in the chunks in the list. | |
| 0 | 204 if (nextTC == NULL) { |
|
1489
cff162798819
6888953: some calls to function-like macros are missing semicolons
jcoomes
parents:
1145
diff
changeset
|
205 assert(prevFC == NULL, "Not last chunk in the list"); |
| 0 | 206 set_tail(NULL); |
| 207 set_head(NULL); | |
| 208 } else { | |
| 209 // copy embedded list. | |
| 210 nextTC->set_embedded_list(tc->embedded_list()); | |
| 211 retTL = nextTC->embedded_list(); | |
| 212 // Fix the pointer to the list in each chunk in the list. | |
| 213 // This can be slow for a long list. Consider having | |
| 214 // an option that does not allow the first chunk on the | |
| 215 // list to be coalesced. | |
| 6885 | 216 for (TreeChunk<Chunk_t, FreeList_t>* curTC = nextTC; curTC != NULL; |
| 217 curTC = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(curTC->next())) { | |
| 0 | 218 curTC->set_list(retTL); |
| 219 } | |
| 6885 | 220 // Fix the parent to point to the new TreeList<Chunk_t, FreeList_t>. |
| 0 | 221 if (retTL->parent() != NULL) { |
| 222 if (this == retTL->parent()->left()) { | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
223 retTL->parent()->set_left(retTL); |
| 0 | 224 } else { |
| 225 assert(this == retTL->parent()->right(), "Parent is incorrect"); | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
226 retTL->parent()->set_right(retTL); |
| 0 | 227 } |
| 228 } | |
| 229 // Fix the children's parent pointers to point to the | |
| 230 // new list. | |
| 231 assert(right() == retTL->right(), "Should have been copied"); | |
| 232 if (retTL->right() != NULL) { | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
233 retTL->right()->set_parent(retTL); |
| 0 | 234 } |
| 235 assert(left() == retTL->left(), "Should have been copied"); | |
| 236 if (retTL->left() != NULL) { | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
237 retTL->left()->set_parent(retTL); |
| 0 | 238 } |
| 239 retTL->link_head(nextTC); | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
240 assert(nextTC->is_free(), "Should be a free chunk"); |
| 0 | 241 } |
| 242 } else { | |
| 243 if (nextTC == NULL) { | |
| 244 // Removing chunk at tail of list | |
|
6970
0400886d2613
8003259: NPG: Build with gcc 4.7.2 broken by 7045397
coleenp
parents:
6885
diff
changeset
|
245 this->link_tail(prevFC); |
| 0 | 246 } |
| 247 // Chunk is interior to the list | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
248 prevFC->link_after(nextTC); |
| 0 | 249 } |
| 250 | |
| 6885 | 251 // Below this point the embeded TreeList<Chunk_t, FreeList_t> being used for the |
| 0 | 252 // tree node may have changed. Don't use "this" |
| 6885 | 253 // TreeList<Chunk_t, FreeList_t>*. |
| 0 | 254 // chunk should still be a free chunk (bit set in _prev) |
| 255 assert(!retTL->head() || retTL->size() == retTL->head()->size(), | |
| 256 "Wrong sized chunk in list"); | |
| 257 debug_only( | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
258 tc->link_prev(NULL); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
259 tc->link_next(NULL); |
| 0 | 260 tc->set_list(NULL); |
| 261 bool prev_found = false; | |
| 262 bool next_found = false; | |
| 6885 | 263 for (Chunk_t* curFC = retTL->head(); |
| 0 | 264 curFC != NULL; curFC = curFC->next()) { |
| 265 assert(curFC != tc, "Chunk is still in list"); | |
| 266 if (curFC == prevFC) { | |
| 267 prev_found = true; | |
| 268 } | |
| 269 if (curFC == nextTC) { | |
| 270 next_found = true; | |
| 271 } | |
| 272 } | |
| 273 assert(prevFC == NULL || prev_found, "Chunk was lost from list"); | |
| 274 assert(nextTC == NULL || next_found, "Chunk was lost from list"); | |
| 275 assert(retTL->parent() == NULL || | |
| 276 retTL == retTL->parent()->left() || | |
| 277 retTL == retTL->parent()->right(), | |
| 278 "list is inconsistent"); | |
| 279 ) | |
| 280 retTL->decrement_count(); | |
| 281 | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
282 assert(tc->is_free(), "Should still be a free chunk"); |
| 0 | 283 assert(retTL->head() == NULL || retTL->head()->prev() == NULL, |
| 284 "list invariant"); | |
| 285 assert(retTL->tail() == NULL || retTL->tail()->next() == NULL, | |
| 286 "list invariant"); | |
| 287 return retTL; | |
| 288 } | |
| 6026 | 289 |
| 6885 | 290 template <class Chunk_t, template <class> class FreeList_t> |
| 291 void TreeList<Chunk_t, FreeList_t>::return_chunk_at_tail(TreeChunk<Chunk_t, FreeList_t>* chunk) { | |
| 0 | 292 assert(chunk != NULL, "returning NULL chunk"); |
| 293 assert(chunk->list() == this, "list should be set for chunk"); | |
| 294 assert(tail() != NULL, "The tree list is embedded in the first chunk"); | |
| 295 // which means that the list can never be empty. | |
| 7178 | 296 assert(!this->verify_chunk_in_free_list(chunk), "Double entry"); |
| 0 | 297 assert(head() == NULL || head()->prev() == NULL, "list invariant"); |
| 298 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); | |
| 299 | |
| 6885 | 300 Chunk_t* fc = tail(); |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
301 fc->link_after(chunk); |
|
6970
0400886d2613
8003259: NPG: Build with gcc 4.7.2 broken by 7045397
coleenp
parents:
6885
diff
changeset
|
302 this->link_tail(chunk); |
| 0 | 303 |
| 304 assert(!tail() || size() == tail()->size(), "Wrong sized chunk in list"); | |
| 6885 | 305 FreeList_t<Chunk_t>::increment_count(); |
| 7178 | 306 debug_only(this->increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));) |
| 0 | 307 assert(head() == NULL || head()->prev() == NULL, "list invariant"); |
| 308 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); | |
| 309 } | |
| 310 | |
| 311 // Add this chunk at the head of the list. "At the head of the list" | |
| 312 // is defined to be after the chunk pointer to by head(). This is | |
| 6885 | 313 // because the TreeList<Chunk_t, FreeList_t> is embedded in the first TreeChunk<Chunk_t, FreeList_t> in the |
| 314 // list. See the definition of TreeChunk<Chunk_t, FreeList_t>. | |
| 315 template <class Chunk_t, template <class> class FreeList_t> | |
| 316 void TreeList<Chunk_t, FreeList_t>::return_chunk_at_head(TreeChunk<Chunk_t, FreeList_t>* chunk) { | |
| 0 | 317 assert(chunk->list() == this, "list should be set for chunk"); |
| 318 assert(head() != NULL, "The tree list is embedded in the first chunk"); | |
| 319 assert(chunk != NULL, "returning NULL chunk"); | |
| 7178 | 320 assert(!this->verify_chunk_in_free_list(chunk), "Double entry"); |
| 0 | 321 assert(head() == NULL || head()->prev() == NULL, "list invariant"); |
| 322 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); | |
| 323 | |
| 6885 | 324 Chunk_t* fc = head()->next(); |
| 0 | 325 if (fc != NULL) { |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
326 chunk->link_after(fc); |
| 0 | 327 } else { |
| 328 assert(tail() == NULL, "List is inconsistent"); | |
|
6970
0400886d2613
8003259: NPG: Build with gcc 4.7.2 broken by 7045397
coleenp
parents:
6885
diff
changeset
|
329 this->link_tail(chunk); |
| 0 | 330 } |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
331 head()->link_after(chunk); |
| 0 | 332 assert(!head() || size() == head()->size(), "Wrong sized chunk in list"); |
| 6885 | 333 FreeList_t<Chunk_t>::increment_count(); |
| 7178 | 334 debug_only(this->increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));) |
| 0 | 335 assert(head() == NULL || head()->prev() == NULL, "list invariant"); |
| 336 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); | |
| 337 } | |
| 338 | |
| 6885 | 339 template <class Chunk_t, template <class> class FreeList_t> |
| 340 void TreeChunk<Chunk_t, FreeList_t>::assert_is_mangled() const { | |
| 341 assert((ZapUnusedHeapArea && | |
| 342 SpaceMangler::is_mangled((HeapWord*) Chunk_t::size_addr()) && | |
| 343 SpaceMangler::is_mangled((HeapWord*) Chunk_t::prev_addr()) && | |
| 344 SpaceMangler::is_mangled((HeapWord*) Chunk_t::next_addr())) || | |
| 345 (size() == 0 && prev() == NULL && next() == NULL), | |
| 346 "Space should be clear or mangled"); | |
| 0 | 347 } |
| 348 | |
| 6885 | 349 template <class Chunk_t, template <class> class FreeList_t> |
| 350 TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::head_as_TreeChunk() { | |
| 351 assert(head() == NULL || (TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(head())->list() == this), | |
| 352 "Wrong type of chunk?"); | |
| 353 return TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(head()); | |
| 354 } | |
| 355 | |
| 356 template <class Chunk_t, template <class> class FreeList_t> | |
| 357 TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::first_available() { | |
|
1777
179464550c7d
6983930: CMS: Various small cleanups ca September 2010
ysr
parents:
1552
diff
changeset
|
358 assert(head() != NULL, "The head of the list cannot be NULL"); |
| 6885 | 359 Chunk_t* fc = head()->next(); |
| 360 TreeChunk<Chunk_t, FreeList_t>* retTC; | |
| 0 | 361 if (fc == NULL) { |
| 362 retTC = head_as_TreeChunk(); | |
| 363 } else { | |
| 6885 | 364 retTC = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(fc); |
| 0 | 365 } |
| 366 assert(retTC->list() == this, "Wrong type of chunk."); | |
| 367 return retTC; | |
| 368 } | |
| 369 | |
|
1145
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
370 // Returns the block with the largest heap address amongst |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
371 // those in the list for this size; potentially slow and expensive, |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
372 // use with caution! |
| 6885 | 373 template <class Chunk_t, template <class> class FreeList_t> |
| 374 TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::largest_address() { | |
|
1777
179464550c7d
6983930: CMS: Various small cleanups ca September 2010
ysr
parents:
1552
diff
changeset
|
375 assert(head() != NULL, "The head of the list cannot be NULL"); |
| 6885 | 376 Chunk_t* fc = head()->next(); |
| 377 TreeChunk<Chunk_t, FreeList_t>* retTC; | |
|
1145
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
378 if (fc == NULL) { |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
379 retTC = head_as_TreeChunk(); |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
380 } else { |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
381 // walk down the list and return the one with the highest |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
382 // heap address among chunks of this size. |
| 6885 | 383 Chunk_t* last = fc; |
|
1145
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
384 while (fc->next() != NULL) { |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
385 if ((HeapWord*)last < (HeapWord*)fc) { |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
386 last = fc; |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
387 } |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
388 fc = fc->next(); |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
389 } |
| 6885 | 390 retTC = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(last); |
|
1145
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
391 } |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
392 assert(retTC->list() == this, "Wrong type of chunk."); |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
393 return retTC; |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
394 } |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
395 |
| 6885 | 396 template <class Chunk_t, template <class> class FreeList_t> |
| 397 BinaryTreeDictionary<Chunk_t, FreeList_t>::BinaryTreeDictionary(MemRegion mr) { | |
| 398 assert((mr.byte_size() > min_size()), "minimum chunk size"); | |
| 0 | 399 |
| 400 reset(mr); | |
| 401 assert(root()->left() == NULL, "reset check failed"); | |
| 402 assert(root()->right() == NULL, "reset check failed"); | |
| 403 assert(root()->head()->next() == NULL, "reset check failed"); | |
| 404 assert(root()->head()->prev() == NULL, "reset check failed"); | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
405 assert(total_size() == root()->size(), "reset check failed"); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
406 assert(total_free_blocks() == 1, "reset check failed"); |
| 0 | 407 } |
| 408 | |
| 6885 | 409 template <class Chunk_t, template <class> class FreeList_t> |
| 410 void BinaryTreeDictionary<Chunk_t, FreeList_t>::inc_total_size(size_t inc) { | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
411 _total_size = _total_size + inc; |
| 0 | 412 } |
| 413 | |
| 6885 | 414 template <class Chunk_t, template <class> class FreeList_t> |
| 415 void BinaryTreeDictionary<Chunk_t, FreeList_t>::dec_total_size(size_t dec) { | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
416 _total_size = _total_size - dec; |
| 0 | 417 } |
| 418 | |
| 6885 | 419 template <class Chunk_t, template <class> class FreeList_t> |
| 420 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset(MemRegion mr) { | |
| 421 assert((mr.byte_size() > min_size()), "minimum chunk size"); | |
| 422 set_root(TreeList<Chunk_t, FreeList_t>::as_TreeList(mr.start(), mr.word_size())); | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
423 set_total_size(mr.word_size()); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
424 set_total_free_blocks(1); |
| 0 | 425 } |
| 426 | |
| 6885 | 427 template <class Chunk_t, template <class> class FreeList_t> |
| 428 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset(HeapWord* addr, size_t byte_size) { | |
| 0 | 429 MemRegion mr(addr, heap_word_size(byte_size)); |
| 430 reset(mr); | |
| 431 } | |
| 432 | |
| 6885 | 433 template <class Chunk_t, template <class> class FreeList_t> |
| 434 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset() { | |
| 0 | 435 set_root(NULL); |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
436 set_total_size(0); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
437 set_total_free_blocks(0); |
| 0 | 438 } |
| 439 | |
| 440 // Get a free block of size at least size from tree, or NULL. | |
| 6885 | 441 template <class Chunk_t, template <class> class FreeList_t> |
| 442 TreeChunk<Chunk_t, FreeList_t>* | |
| 443 BinaryTreeDictionary<Chunk_t, FreeList_t>::get_chunk_from_tree( | |
| 444 size_t size, | |
| 445 enum FreeBlockDictionary<Chunk_t>::Dither dither) | |
| 0 | 446 { |
| 6885 | 447 TreeList<Chunk_t, FreeList_t> *curTL, *prevTL; |
| 448 TreeChunk<Chunk_t, FreeList_t>* retTC = NULL; | |
| 449 | |
| 450 assert((size >= min_size()), "minimum chunk size"); | |
| 0 | 451 if (FLSVerifyDictionary) { |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
452 verify_tree(); |
| 0 | 453 } |
| 454 // starting at the root, work downwards trying to find match. | |
| 455 // Remember the last node of size too great or too small. | |
| 456 for (prevTL = curTL = root(); curTL != NULL;) { | |
| 457 if (curTL->size() == size) { // exact match | |
| 458 break; | |
| 459 } | |
| 460 prevTL = curTL; | |
| 461 if (curTL->size() < size) { // proceed to right sub-tree | |
| 462 curTL = curTL->right(); | |
| 463 } else { // proceed to left sub-tree | |
| 464 assert(curTL->size() > size, "size inconsistency"); | |
| 465 curTL = curTL->left(); | |
| 466 } | |
| 467 } | |
| 468 if (curTL == NULL) { // couldn't find exact match | |
| 6026 | 469 |
| 6885 | 470 if (dither == FreeBlockDictionary<Chunk_t>::exactly) return NULL; |
| 6026 | 471 |
| 0 | 472 // try and find the next larger size by walking back up the search path |
| 473 for (curTL = prevTL; curTL != NULL;) { | |
| 474 if (curTL->size() >= size) break; | |
| 475 else curTL = curTL->parent(); | |
| 476 } | |
| 477 assert(curTL == NULL || curTL->count() > 0, | |
| 478 "An empty list should not be in the tree"); | |
| 479 } | |
| 480 if (curTL != NULL) { | |
| 481 assert(curTL->size() >= size, "size inconsistency"); | |
| 482 | |
| 6885 | 483 curTL = curTL->get_better_list(this); |
| 484 | |
| 0 | 485 retTC = curTL->first_available(); |
| 486 assert((retTC != NULL) && (curTL->count() > 0), | |
| 487 "A list in the binary tree should not be NULL"); | |
| 488 assert(retTC->size() >= size, | |
| 489 "A chunk of the wrong size was found"); | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
490 remove_chunk_from_tree(retTC); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
491 assert(retTC->is_free(), "Header is not marked correctly"); |
| 0 | 492 } |
| 493 | |
| 494 if (FLSVerifyDictionary) { | |
| 495 verify(); | |
| 496 } | |
| 497 return retTC; | |
| 498 } | |
| 499 | |
| 6885 | 500 template <class Chunk_t, template <class> class FreeList_t> |
| 501 TreeList<Chunk_t, FreeList_t>* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_list(size_t size) const { | |
| 502 TreeList<Chunk_t, FreeList_t>* curTL; | |
| 0 | 503 for (curTL = root(); curTL != NULL;) { |
| 504 if (curTL->size() == size) { // exact match | |
| 505 break; | |
| 506 } | |
| 507 | |
| 508 if (curTL->size() < size) { // proceed to right sub-tree | |
| 509 curTL = curTL->right(); | |
| 510 } else { // proceed to left sub-tree | |
| 511 assert(curTL->size() > size, "size inconsistency"); | |
| 512 curTL = curTL->left(); | |
| 513 } | |
| 514 } | |
| 515 return curTL; | |
| 516 } | |
| 517 | |
| 518 | |
| 6885 | 519 template <class Chunk_t, template <class> class FreeList_t> |
| 520 bool BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_chunk_in_free_list(Chunk_t* tc) const { | |
| 0 | 521 size_t size = tc->size(); |
| 6885 | 522 TreeList<Chunk_t, FreeList_t>* tl = find_list(size); |
| 0 | 523 if (tl == NULL) { |
| 524 return false; | |
| 525 } else { | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
526 return tl->verify_chunk_in_free_list(tc); |
| 0 | 527 } |
| 528 } | |
| 529 | |
| 6885 | 530 template <class Chunk_t, template <class> class FreeList_t> |
| 531 Chunk_t* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_largest_dict() const { | |
| 532 TreeList<Chunk_t, FreeList_t> *curTL = root(); | |
| 0 | 533 if (curTL != NULL) { |
| 534 while(curTL->right() != NULL) curTL = curTL->right(); | |
|
1145
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
535 return curTL->largest_address(); |
| 0 | 536 } else { |
| 537 return NULL; | |
| 538 } | |
| 539 } | |
| 540 | |
| 541 // Remove the current chunk from the tree. If it is not the last | |
| 542 // chunk in a list on a tree node, just unlink it. | |
| 543 // If it is the last chunk in the list (the next link is NULL), | |
| 544 // remove the node and repair the tree. | |
| 6885 | 545 template <class Chunk_t, template <class> class FreeList_t> |
| 546 TreeChunk<Chunk_t, FreeList_t>* | |
| 547 BinaryTreeDictionary<Chunk_t, FreeList_t>::remove_chunk_from_tree(TreeChunk<Chunk_t, FreeList_t>* tc) { | |
| 0 | 548 assert(tc != NULL, "Should not call with a NULL chunk"); |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
549 assert(tc->is_free(), "Header is not marked correctly"); |
| 0 | 550 |
| 6885 | 551 TreeList<Chunk_t, FreeList_t> *newTL, *parentTL; |
| 552 TreeChunk<Chunk_t, FreeList_t>* retTC; | |
| 553 TreeList<Chunk_t, FreeList_t>* tl = tc->list(); | |
| 0 | 554 debug_only( |
| 555 bool removing_only_chunk = false; | |
| 556 if (tl == _root) { | |
| 557 if ((_root->left() == NULL) && (_root->right() == NULL)) { | |
| 558 if (_root->count() == 1) { | |
| 559 assert(_root->head() == tc, "Should only be this one chunk"); | |
| 560 removing_only_chunk = true; | |
| 561 } | |
| 562 } | |
| 563 } | |
| 564 ) | |
| 565 assert(tl != NULL, "List should be set"); | |
| 566 assert(tl->parent() == NULL || tl == tl->parent()->left() || | |
| 567 tl == tl->parent()->right(), "list is inconsistent"); | |
| 568 | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
569 bool complicated_splice = false; |
| 0 | 570 |
| 571 retTC = tc; | |
| 572 // Removing this chunk can have the side effect of changing the node | |
| 6885 | 573 // (TreeList<Chunk_t, FreeList_t>*) in the tree. If the node is the root, update it. |
| 574 TreeList<Chunk_t, FreeList_t>* replacementTL = tl->remove_chunk_replace_if_needed(tc); | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
575 assert(tc->is_free(), "Chunk should still be free"); |
| 0 | 576 assert(replacementTL->parent() == NULL || |
| 577 replacementTL == replacementTL->parent()->left() || | |
| 578 replacementTL == replacementTL->parent()->right(), | |
| 579 "list is inconsistent"); | |
| 580 if (tl == root()) { | |
| 581 assert(replacementTL->parent() == NULL, "Incorrectly replacing root"); | |
| 582 set_root(replacementTL); | |
| 583 } | |
| 6885 | 584 #ifdef ASSERT |
| 0 | 585 if (tl != replacementTL) { |
| 586 assert(replacementTL->head() != NULL, | |
| 587 "If the tree list was replaced, it should not be a NULL list"); | |
| 6885 | 588 TreeList<Chunk_t, FreeList_t>* rhl = replacementTL->head_as_TreeChunk()->list(); |
| 589 TreeList<Chunk_t, FreeList_t>* rtl = | |
| 590 TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(replacementTL->tail())->list(); | |
| 0 | 591 assert(rhl == replacementTL, "Broken head"); |
| 592 assert(rtl == replacementTL, "Broken tail"); | |
| 593 assert(replacementTL->size() == tc->size(), "Broken size"); | |
| 594 } | |
| 6885 | 595 #endif |
| 0 | 596 |
| 597 // Does the tree need to be repaired? | |
| 598 if (replacementTL->count() == 0) { | |
| 599 assert(replacementTL->head() == NULL && | |
| 600 replacementTL->tail() == NULL, "list count is incorrect"); | |
| 601 // Find the replacement node for the (soon to be empty) node being removed. | |
| 602 // if we have a single (or no) child, splice child in our stead | |
| 603 if (replacementTL->left() == NULL) { | |
| 604 // left is NULL so pick right. right may also be NULL. | |
| 605 newTL = replacementTL->right(); | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
606 debug_only(replacementTL->clear_right();) |
| 0 | 607 } else if (replacementTL->right() == NULL) { |
| 608 // right is NULL | |
| 609 newTL = replacementTL->left(); | |
| 6885 | 610 debug_only(replacementTL->clear_left();) |
| 0 | 611 } else { // we have both children, so, by patriarchal convention, |
| 612 // my replacement is least node in right sub-tree | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
613 complicated_splice = true; |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
614 newTL = remove_tree_minimum(replacementTL->right()); |
| 0 | 615 assert(newTL != NULL && newTL->left() == NULL && |
| 616 newTL->right() == NULL, "sub-tree minimum exists"); | |
| 617 } | |
| 618 // newTL is the replacement for the (soon to be empty) node. | |
| 619 // newTL may be NULL. | |
| 620 // should verify; we just cleanly excised our replacement | |
| 621 if (FLSVerifyDictionary) { | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
622 verify_tree(); |
| 0 | 623 } |
| 624 // first make newTL my parent's child | |
| 625 if ((parentTL = replacementTL->parent()) == NULL) { | |
| 626 // newTL should be root | |
| 627 assert(tl == root(), "Incorrectly replacing root"); | |
| 628 set_root(newTL); | |
| 629 if (newTL != NULL) { | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
630 newTL->clear_parent(); |
| 0 | 631 } |
| 632 } else if (parentTL->right() == replacementTL) { | |
| 633 // replacementTL is a right child | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
634 parentTL->set_right(newTL); |
| 0 | 635 } else { // replacementTL is a left child |
| 636 assert(parentTL->left() == replacementTL, "should be left child"); | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
637 parentTL->set_left(newTL); |
| 0 | 638 } |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
639 debug_only(replacementTL->clear_parent();) |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
640 if (complicated_splice) { // we need newTL to get replacementTL's |
| 0 | 641 // two children |
| 642 assert(newTL != NULL && | |
| 643 newTL->left() == NULL && newTL->right() == NULL, | |
| 644 "newTL should not have encumbrances from the past"); | |
| 645 // we'd like to assert as below: | |
| 646 // assert(replacementTL->left() != NULL && replacementTL->right() != NULL, | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
647 // "else !complicated_splice"); |
| 0 | 648 // ... however, the above assertion is too strong because we aren't |
| 649 // guaranteed that replacementTL->right() is still NULL. | |
| 650 // Recall that we removed | |
| 651 // the right sub-tree minimum from replacementTL. | |
| 652 // That may well have been its right | |
| 653 // child! So we'll just assert half of the above: | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
654 assert(replacementTL->left() != NULL, "else !complicated_splice"); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
655 newTL->set_left(replacementTL->left()); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
656 newTL->set_right(replacementTL->right()); |
| 0 | 657 debug_only( |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
658 replacementTL->clear_right(); |
| 6885 | 659 replacementTL->clear_left(); |
| 0 | 660 ) |
| 661 } | |
| 662 assert(replacementTL->right() == NULL && | |
| 663 replacementTL->left() == NULL && | |
| 664 replacementTL->parent() == NULL, | |
| 665 "delete without encumbrances"); | |
| 666 } | |
| 667 | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
668 assert(total_size() >= retTC->size(), "Incorrect total size"); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
669 dec_total_size(retTC->size()); // size book-keeping |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
670 assert(total_free_blocks() > 0, "Incorrect total count"); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
671 set_total_free_blocks(total_free_blocks() - 1); |
| 0 | 672 |
| 673 assert(retTC != NULL, "null chunk?"); | |
| 674 assert(retTC->prev() == NULL && retTC->next() == NULL, | |
| 675 "should return without encumbrances"); | |
| 676 if (FLSVerifyDictionary) { | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
677 verify_tree(); |
| 0 | 678 } |
| 679 assert(!removing_only_chunk || _root == NULL, "root should be NULL"); | |
| 6885 | 680 return TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(retTC); |
| 0 | 681 } |
| 682 | |
| 683 // Remove the leftmost node (lm) in the tree and return it. | |
| 684 // If lm has a right child, link it to the left node of | |
| 685 // the parent of lm. | |
| 6885 | 686 template <class Chunk_t, template <class> class FreeList_t> |
| 687 TreeList<Chunk_t, FreeList_t>* BinaryTreeDictionary<Chunk_t, FreeList_t>::remove_tree_minimum(TreeList<Chunk_t, FreeList_t>* tl) { | |
| 0 | 688 assert(tl != NULL && tl->parent() != NULL, "really need a proper sub-tree"); |
| 689 // locate the subtree minimum by walking down left branches | |
| 6885 | 690 TreeList<Chunk_t, FreeList_t>* curTL = tl; |
| 0 | 691 for (; curTL->left() != NULL; curTL = curTL->left()); |
| 692 // obviously curTL now has at most one child, a right child | |
| 693 if (curTL != root()) { // Should this test just be removed? | |
| 6885 | 694 TreeList<Chunk_t, FreeList_t>* parentTL = curTL->parent(); |
| 0 | 695 if (parentTL->left() == curTL) { // curTL is a left child |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
696 parentTL->set_left(curTL->right()); |
| 0 | 697 } else { |
| 698 // If the list tl has no left child, then curTL may be | |
| 699 // the right child of parentTL. | |
| 700 assert(parentTL->right() == curTL, "should be a right child"); | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
701 parentTL->set_right(curTL->right()); |
| 0 | 702 } |
| 703 } else { | |
| 704 // The only use of this method would not pass the root of the | |
| 705 // tree (as indicated by the assertion above that the tree list | |
| 706 // has a parent) but the specification does not explicitly exclude the | |
| 707 // passing of the root so accomodate it. | |
| 708 set_root(NULL); | |
| 709 } | |
| 710 debug_only( | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
711 curTL->clear_parent(); // Test if this needs to be cleared |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
712 curTL->clear_right(); // recall, above, left child is already null |
| 0 | 713 ) |
| 714 // we just excised a (non-root) node, we should still verify all tree invariants | |
| 715 if (FLSVerifyDictionary) { | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
716 verify_tree(); |
| 0 | 717 } |
| 718 return curTL; | |
| 719 } | |
| 720 | |
| 6885 | 721 template <class Chunk_t, template <class> class FreeList_t> |
| 722 void BinaryTreeDictionary<Chunk_t, FreeList_t>::insert_chunk_in_tree(Chunk_t* fc) { | |
| 723 TreeList<Chunk_t, FreeList_t> *curTL, *prevTL; | |
| 0 | 724 size_t size = fc->size(); |
| 725 | |
| 6885 | 726 assert((size >= min_size()), |
| 727 err_msg(SIZE_FORMAT " is too small to be a TreeChunk<Chunk_t, FreeList_t> " SIZE_FORMAT, | |
| 728 size, min_size())); | |
| 0 | 729 if (FLSVerifyDictionary) { |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
730 verify_tree(); |
| 0 | 731 } |
| 732 | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
733 fc->clear_next(); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
734 fc->link_prev(NULL); |
| 0 | 735 |
| 736 // work down from the _root, looking for insertion point | |
| 737 for (prevTL = curTL = root(); curTL != NULL;) { | |
| 738 if (curTL->size() == size) // exact match | |
| 739 break; | |
| 740 prevTL = curTL; | |
| 741 if (curTL->size() > size) { // follow left branch | |
| 742 curTL = curTL->left(); | |
| 743 } else { // follow right branch | |
| 744 assert(curTL->size() < size, "size inconsistency"); | |
| 745 curTL = curTL->right(); | |
| 746 } | |
| 747 } | |
| 6885 | 748 TreeChunk<Chunk_t, FreeList_t>* tc = TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(fc); |
|
1145
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
749 // This chunk is being returned to the binary tree. Its embedded |
| 6885 | 750 // TreeList<Chunk_t, FreeList_t> should be unused at this point. |
| 0 | 751 tc->initialize(); |
| 752 if (curTL != NULL) { // exact match | |
| 753 tc->set_list(curTL); | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
754 curTL->return_chunk_at_tail(tc); |
| 0 | 755 } else { // need a new node in tree |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
756 tc->clear_next(); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
757 tc->link_prev(NULL); |
| 6885 | 758 TreeList<Chunk_t, FreeList_t>* newTL = TreeList<Chunk_t, FreeList_t>::as_TreeList(tc); |
| 759 assert(((TreeChunk<Chunk_t, FreeList_t>*)tc)->list() == newTL, | |
| 0 | 760 "List was not initialized correctly"); |
| 761 if (prevTL == NULL) { // we are the only tree node | |
| 762 assert(root() == NULL, "control point invariant"); | |
| 763 set_root(newTL); | |
| 764 } else { // insert under prevTL ... | |
| 765 if (prevTL->size() < size) { // am right child | |
| 766 assert(prevTL->right() == NULL, "control point invariant"); | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
767 prevTL->set_right(newTL); |
| 0 | 768 } else { // am left child |
| 769 assert(prevTL->size() > size && prevTL->left() == NULL, "cpt pt inv"); | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
770 prevTL->set_left(newTL); |
| 0 | 771 } |
| 772 } | |
| 773 } | |
| 774 assert(tc->list() != NULL, "Tree list should be set"); | |
| 775 | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
776 inc_total_size(size); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
777 // Method 'total_size_in_tree' walks through the every block in the |
| 0 | 778 // tree, so it can cause significant performance loss if there are |
| 779 // many blocks in the tree | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
780 assert(!FLSVerifyDictionary || total_size_in_tree(root()) == total_size(), "_total_size inconsistency"); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
781 set_total_free_blocks(total_free_blocks() + 1); |
| 0 | 782 if (FLSVerifyDictionary) { |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
783 verify_tree(); |
| 0 | 784 } |
| 785 } | |
| 786 | |
| 6885 | 787 template <class Chunk_t, template <class> class FreeList_t> |
| 788 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::max_chunk_size() const { | |
| 789 FreeBlockDictionary<Chunk_t>::verify_par_locked(); | |
| 790 TreeList<Chunk_t, FreeList_t>* tc = root(); | |
| 0 | 791 if (tc == NULL) return 0; |
| 792 for (; tc->right() != NULL; tc = tc->right()); | |
| 793 return tc->size(); | |
| 794 } | |
| 795 | |
| 6885 | 796 template <class Chunk_t, template <class> class FreeList_t> |
| 797 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_list_length(TreeList<Chunk_t, FreeList_t>* tl) const { | |
| 0 | 798 size_t res; |
| 799 res = tl->count(); | |
| 800 #ifdef ASSERT | |
| 801 size_t cnt; | |
| 6885 | 802 Chunk_t* tc = tl->head(); |
| 0 | 803 for (cnt = 0; tc != NULL; tc = tc->next(), cnt++); |
| 804 assert(res == cnt, "The count is not being maintained correctly"); | |
| 805 #endif | |
| 806 return res; | |
| 807 } | |
| 808 | |
| 6885 | 809 template <class Chunk_t, template <class> class FreeList_t> |
| 810 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_size_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const { | |
| 0 | 811 if (tl == NULL) |
| 812 return 0; | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
813 return (tl->size() * total_list_length(tl)) + |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
814 total_size_in_tree(tl->left()) + |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
815 total_size_in_tree(tl->right()); |
| 0 | 816 } |
| 817 | |
| 6885 | 818 template <class Chunk_t, template <class> class FreeList_t> |
| 819 double BinaryTreeDictionary<Chunk_t, FreeList_t>::sum_of_squared_block_sizes(TreeList<Chunk_t, FreeList_t>* const tl) const { | |
| 0 | 820 if (tl == NULL) { |
| 821 return 0.0; | |
| 822 } | |
| 823 double size = (double)(tl->size()); | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
824 double curr = size * size * total_list_length(tl); |
| 0 | 825 curr += sum_of_squared_block_sizes(tl->left()); |
| 826 curr += sum_of_squared_block_sizes(tl->right()); | |
| 827 return curr; | |
| 828 } | |
| 829 | |
| 6885 | 830 template <class Chunk_t, template <class> class FreeList_t> |
| 831 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_free_blocks_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const { | |
| 0 | 832 if (tl == NULL) |
| 833 return 0; | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
834 return total_list_length(tl) + |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
835 total_free_blocks_in_tree(tl->left()) + |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
836 total_free_blocks_in_tree(tl->right()); |
| 0 | 837 } |
| 838 | |
| 6885 | 839 template <class Chunk_t, template <class> class FreeList_t> |
| 840 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::num_free_blocks() const { | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
841 assert(total_free_blocks_in_tree(root()) == total_free_blocks(), |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
842 "_total_free_blocks inconsistency"); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
843 return total_free_blocks(); |
| 0 | 844 } |
| 845 | |
| 6885 | 846 template <class Chunk_t, template <class> class FreeList_t> |
| 847 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::tree_height_helper(TreeList<Chunk_t, FreeList_t>* tl) const { | |
| 0 | 848 if (tl == NULL) |
| 849 return 0; | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
850 return 1 + MAX2(tree_height_helper(tl->left()), |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
851 tree_height_helper(tl->right())); |
| 0 | 852 } |
| 853 | |
| 6885 | 854 template <class Chunk_t, template <class> class FreeList_t> |
| 855 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::tree_height() const { | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
856 return tree_height_helper(root()); |
| 0 | 857 } |
| 858 | |
| 6885 | 859 template <class Chunk_t, template <class> class FreeList_t> |
| 860 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_nodes_helper(TreeList<Chunk_t, FreeList_t>* tl) const { | |
| 0 | 861 if (tl == NULL) { |
| 862 return 0; | |
| 863 } | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
864 return 1 + total_nodes_helper(tl->left()) + |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
865 total_nodes_helper(tl->right()); |
| 0 | 866 } |
| 867 | |
| 6885 | 868 template <class Chunk_t, template <class> class FreeList_t> |
| 869 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_nodes_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const { | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
870 return total_nodes_helper(root()); |
| 0 | 871 } |
| 872 | |
| 6885 | 873 template <class Chunk_t, template <class> class FreeList_t> |
| 874 void BinaryTreeDictionary<Chunk_t, FreeList_t>::dict_census_update(size_t size, bool split, bool birth){} | |
| 875 | |
|
8001
db9981fd3124
8005915: Unify SERIALGC and INCLUDE_ALTERNATE_GCS
jprovino
parents:
7446
diff
changeset
|
876 #if INCLUDE_ALL_GCS |
| 6885 | 877 template <> |
|
7947
3c327c2b6782
8004895: NPG: JMapPermCore test failure caused by warnings about missing field
jmasa
parents:
7446
diff
changeset
|
878 void AFLBinaryTreeDictionary::dict_census_update(size_t size, bool split, bool birth){ |
| 6885 | 879 TreeList<FreeChunk, AdaptiveFreeList>* nd = find_list(size); |
| 0 | 880 if (nd) { |
| 881 if (split) { | |
| 882 if (birth) { | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
883 nd->increment_split_births(); |
| 0 | 884 nd->increment_surplus(); |
| 885 } else { | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
886 nd->increment_split_deaths(); |
| 0 | 887 nd->decrement_surplus(); |
| 888 } | |
| 889 } else { | |
| 890 if (birth) { | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
891 nd->increment_coal_births(); |
| 0 | 892 nd->increment_surplus(); |
| 893 } else { | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
894 nd->increment_coal_deaths(); |
| 0 | 895 nd->decrement_surplus(); |
| 896 } | |
| 897 } | |
| 898 } | |
| 899 // A list for this size may not be found (nd == 0) if | |
| 900 // This is a death where the appropriate list is now | |
| 901 // empty and has been removed from the list. | |
| 902 // This is a birth associated with a LinAB. The chunk | |
| 903 // for the LinAB is not in the dictionary. | |
| 904 } | |
|
8001
db9981fd3124
8005915: Unify SERIALGC and INCLUDE_ALTERNATE_GCS
jprovino
parents:
7446
diff
changeset
|
905 #endif // INCLUDE_ALL_GCS |
| 0 | 906 |
| 6885 | 907 template <class Chunk_t, template <class> class FreeList_t> |
| 908 bool BinaryTreeDictionary<Chunk_t, FreeList_t>::coal_dict_over_populated(size_t size) { | |
| 909 // For the general type of freelists, encourage coalescing by | |
| 910 // returning true. | |
| 911 return true; | |
| 912 } | |
| 913 | |
|
8001
db9981fd3124
8005915: Unify SERIALGC and INCLUDE_ALTERNATE_GCS
jprovino
parents:
7446
diff
changeset
|
914 #if INCLUDE_ALL_GCS |
| 6885 | 915 template <> |
|
7947
3c327c2b6782
8004895: NPG: JMapPermCore test failure caused by warnings about missing field
jmasa
parents:
7446
diff
changeset
|
916 bool AFLBinaryTreeDictionary::coal_dict_over_populated(size_t size) { |
|
1145
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
917 if (FLSAlwaysCoalesceLarge) return true; |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
918 |
| 6885 | 919 TreeList<FreeChunk, AdaptiveFreeList>* list_of_size = find_list(size); |
| 0 | 920 // None of requested size implies overpopulated. |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
921 return list_of_size == NULL || list_of_size->coal_desired() <= 0 || |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
922 list_of_size->count() > list_of_size->coal_desired(); |
| 0 | 923 } |
|
8001
db9981fd3124
8005915: Unify SERIALGC and INCLUDE_ALTERNATE_GCS
jprovino
parents:
7446
diff
changeset
|
924 #endif // INCLUDE_ALL_GCS |
| 0 | 925 |
| 926 // Closures for walking the binary tree. | |
| 927 // do_list() walks the free list in a node applying the closure | |
| 928 // to each free chunk in the list | |
| 929 // do_tree() walks the nodes in the binary tree applying do_list() | |
| 930 // to each list at each node. | |
| 931 | |
| 6885 | 932 template <class Chunk_t, template <class> class FreeList_t> |
| 0 | 933 class TreeCensusClosure : public StackObj { |
| 934 protected: | |
| 6885 | 935 virtual void do_list(FreeList_t<Chunk_t>* fl) = 0; |
| 0 | 936 public: |
| 6885 | 937 virtual void do_tree(TreeList<Chunk_t, FreeList_t>* tl) = 0; |
| 0 | 938 }; |
| 939 | |
| 6885 | 940 template <class Chunk_t, template <class> class FreeList_t> |
| 941 class AscendTreeCensusClosure : public TreeCensusClosure<Chunk_t, FreeList_t> { | |
| 0 | 942 public: |
| 6885 | 943 void do_tree(TreeList<Chunk_t, FreeList_t>* tl) { |
| 0 | 944 if (tl != NULL) { |
| 945 do_tree(tl->left()); | |
|
6970
0400886d2613
8003259: NPG: Build with gcc 4.7.2 broken by 7045397
coleenp
parents:
6885
diff
changeset
|
946 this->do_list(tl); |
| 0 | 947 do_tree(tl->right()); |
| 948 } | |
| 949 } | |
| 950 }; | |
| 951 | |
| 6885 | 952 template <class Chunk_t, template <class> class FreeList_t> |
| 953 class DescendTreeCensusClosure : public TreeCensusClosure<Chunk_t, FreeList_t> { | |
| 0 | 954 public: |
| 6885 | 955 void do_tree(TreeList<Chunk_t, FreeList_t>* tl) { |
| 0 | 956 if (tl != NULL) { |
| 957 do_tree(tl->right()); | |
|
6970
0400886d2613
8003259: NPG: Build with gcc 4.7.2 broken by 7045397
coleenp
parents:
6885
diff
changeset
|
958 this->do_list(tl); |
| 0 | 959 do_tree(tl->left()); |
| 960 } | |
| 961 } | |
| 962 }; | |
| 963 | |
| 964 // For each list in the tree, calculate the desired, desired | |
| 965 // coalesce, count before sweep, and surplus before sweep. | |
| 6885 | 966 template <class Chunk_t, template <class> class FreeList_t> |
| 967 class BeginSweepClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { | |
| 0 | 968 double _percentage; |
| 969 float _inter_sweep_current; | |
| 970 float _inter_sweep_estimate; | |
|
1145
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
971 float _intra_sweep_estimate; |
| 0 | 972 |
| 973 public: | |
| 974 BeginSweepClosure(double p, float inter_sweep_current, | |
|
1145
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
975 float inter_sweep_estimate, |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
976 float intra_sweep_estimate) : |
| 0 | 977 _percentage(p), |
| 978 _inter_sweep_current(inter_sweep_current), | |
|
1145
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
979 _inter_sweep_estimate(inter_sweep_estimate), |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
980 _intra_sweep_estimate(intra_sweep_estimate) { } |
| 0 | 981 |
| 6885 | 982 void do_list(FreeList<Chunk_t>* fl) {} |
| 983 | |
|
8001
db9981fd3124
8005915: Unify SERIALGC and INCLUDE_ALTERNATE_GCS
jprovino
parents:
7446
diff
changeset
|
984 #if INCLUDE_ALL_GCS |
| 6885 | 985 void do_list(AdaptiveFreeList<Chunk_t>* fl) { |
| 0 | 986 double coalSurplusPercent = _percentage; |
|
1145
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
987 fl->compute_desired(_inter_sweep_current, _inter_sweep_estimate, _intra_sweep_estimate); |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
988 fl->set_coal_desired((ssize_t)((double)fl->desired() * coalSurplusPercent)); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
989 fl->set_before_sweep(fl->count()); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
990 fl->set_bfr_surp(fl->surplus()); |
| 0 | 991 } |
|
8001
db9981fd3124
8005915: Unify SERIALGC and INCLUDE_ALTERNATE_GCS
jprovino
parents:
7446
diff
changeset
|
992 #endif // INCLUDE_ALL_GCS |
| 0 | 993 }; |
| 994 | |
| 995 // Used to search the tree until a condition is met. | |
| 996 // Similar to TreeCensusClosure but searches the | |
| 997 // tree and returns promptly when found. | |
| 998 | |
| 6885 | 999 template <class Chunk_t, template <class> class FreeList_t> |
| 0 | 1000 class TreeSearchClosure : public StackObj { |
| 1001 protected: | |
| 6885 | 1002 virtual bool do_list(FreeList_t<Chunk_t>* fl) = 0; |
| 0 | 1003 public: |
| 6885 | 1004 virtual bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) = 0; |
| 0 | 1005 }; |
| 1006 | |
| 1007 #if 0 // Don't need this yet but here for symmetry. | |
| 6885 | 1008 template <class Chunk_t, template <class> class FreeList_t> |
| 1009 class AscendTreeSearchClosure : public TreeSearchClosure<Chunk_t> { | |
| 0 | 1010 public: |
| 6885 | 1011 bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) { |
| 0 | 1012 if (tl != NULL) { |
| 1013 if (do_tree(tl->left())) return true; | |
| 1014 if (do_list(tl)) return true; | |
| 1015 if (do_tree(tl->right())) return true; | |
| 1016 } | |
| 1017 return false; | |
| 1018 } | |
| 1019 }; | |
| 1020 #endif | |
| 1021 | |
| 6885 | 1022 template <class Chunk_t, template <class> class FreeList_t> |
| 1023 class DescendTreeSearchClosure : public TreeSearchClosure<Chunk_t, FreeList_t> { | |
| 0 | 1024 public: |
| 6885 | 1025 bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) { |
| 0 | 1026 if (tl != NULL) { |
| 1027 if (do_tree(tl->right())) return true; | |
|
6970
0400886d2613
8003259: NPG: Build with gcc 4.7.2 broken by 7045397
coleenp
parents:
6885
diff
changeset
|
1028 if (this->do_list(tl)) return true; |
| 0 | 1029 if (do_tree(tl->left())) return true; |
| 1030 } | |
| 1031 return false; | |
| 1032 } | |
| 1033 }; | |
| 1034 | |
| 1035 // Searches the tree for a chunk that ends at the | |
| 1036 // specified address. | |
| 6885 | 1037 template <class Chunk_t, template <class> class FreeList_t> |
| 1038 class EndTreeSearchClosure : public DescendTreeSearchClosure<Chunk_t, FreeList_t> { | |
| 0 | 1039 HeapWord* _target; |
| 6885 | 1040 Chunk_t* _found; |
| 0 | 1041 |
| 1042 public: | |
| 1043 EndTreeSearchClosure(HeapWord* target) : _target(target), _found(NULL) {} | |
| 6885 | 1044 bool do_list(FreeList_t<Chunk_t>* fl) { |
| 1045 Chunk_t* item = fl->head(); | |
| 0 | 1046 while (item != NULL) { |
| 6885 | 1047 if (item->end() == (uintptr_t*) _target) { |
| 0 | 1048 _found = item; |
| 1049 return true; | |
| 1050 } | |
| 1051 item = item->next(); | |
| 1052 } | |
| 1053 return false; | |
| 1054 } | |
| 6885 | 1055 Chunk_t* found() { return _found; } |
| 0 | 1056 }; |
| 1057 | |
| 6885 | 1058 template <class Chunk_t, template <class> class FreeList_t> |
| 1059 Chunk_t* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_chunk_ends_at(HeapWord* target) const { | |
| 1060 EndTreeSearchClosure<Chunk_t, FreeList_t> etsc(target); | |
| 0 | 1061 bool found_target = etsc.do_tree(root()); |
| 1062 assert(found_target || etsc.found() == NULL, "Consistency check"); | |
| 1063 assert(!found_target || etsc.found() != NULL, "Consistency check"); | |
| 1064 return etsc.found(); | |
| 1065 } | |
| 1066 | |
| 6885 | 1067 template <class Chunk_t, template <class> class FreeList_t> |
| 1068 void BinaryTreeDictionary<Chunk_t, FreeList_t>::begin_sweep_dict_census(double coalSurplusPercent, | |
|
1145
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1069 float inter_sweep_current, float inter_sweep_estimate, float intra_sweep_estimate) { |
| 6885 | 1070 BeginSweepClosure<Chunk_t, FreeList_t> bsc(coalSurplusPercent, inter_sweep_current, |
|
1145
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1071 inter_sweep_estimate, |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1072 intra_sweep_estimate); |
| 0 | 1073 bsc.do_tree(root()); |
| 1074 } | |
| 1075 | |
| 1076 // Closures and methods for calculating total bytes returned to the | |
| 1077 // free lists in the tree. | |
| 6026 | 1078 #ifndef PRODUCT |
| 6885 | 1079 template <class Chunk_t, template <class> class FreeList_t> |
| 1080 class InitializeDictReturnedBytesClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { | |
| 0 | 1081 public: |
| 6885 | 1082 void do_list(FreeList_t<Chunk_t>* fl) { |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1083 fl->set_returned_bytes(0); |
| 6026 | 1084 } |
| 1085 }; | |
| 0 | 1086 |
| 6885 | 1087 template <class Chunk_t, template <class> class FreeList_t> |
| 1088 void BinaryTreeDictionary<Chunk_t, FreeList_t>::initialize_dict_returned_bytes() { | |
| 1089 InitializeDictReturnedBytesClosure<Chunk_t, FreeList_t> idrb; | |
| 6026 | 1090 idrb.do_tree(root()); |
| 1091 } | |
| 0 | 1092 |
| 6885 | 1093 template <class Chunk_t, template <class> class FreeList_t> |
| 1094 class ReturnedBytesClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1095 size_t _dict_returned_bytes; |
| 6026 | 1096 public: |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1097 ReturnedBytesClosure() { _dict_returned_bytes = 0; } |
| 6885 | 1098 void do_list(FreeList_t<Chunk_t>* fl) { |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1099 _dict_returned_bytes += fl->returned_bytes(); |
| 6026 | 1100 } |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1101 size_t dict_returned_bytes() { return _dict_returned_bytes; } |
| 6026 | 1102 }; |
| 0 | 1103 |
| 6885 | 1104 template <class Chunk_t, template <class> class FreeList_t> |
| 1105 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::sum_dict_returned_bytes() { | |
| 1106 ReturnedBytesClosure<Chunk_t, FreeList_t> rbc; | |
| 6026 | 1107 rbc.do_tree(root()); |
| 0 | 1108 |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1109 return rbc.dict_returned_bytes(); |
| 6026 | 1110 } |
| 0 | 1111 |
| 6026 | 1112 // Count the number of entries in the tree. |
| 6885 | 1113 template <class Chunk_t, template <class> class FreeList_t> |
| 1114 class treeCountClosure : public DescendTreeCensusClosure<Chunk_t, FreeList_t> { | |
| 6026 | 1115 public: |
| 1116 uint count; | |
| 1117 treeCountClosure(uint c) { count = c; } | |
| 6885 | 1118 void do_list(FreeList_t<Chunk_t>* fl) { |
| 6026 | 1119 count++; |
| 1120 } | |
| 1121 }; | |
| 0 | 1122 |
| 6885 | 1123 template <class Chunk_t, template <class> class FreeList_t> |
| 1124 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_count() { | |
| 1125 treeCountClosure<Chunk_t, FreeList_t> ctc(0); | |
| 6026 | 1126 ctc.do_tree(root()); |
| 1127 return ctc.count; | |
| 1128 } | |
| 1129 #endif // PRODUCT | |
| 0 | 1130 |
| 1131 // Calculate surpluses for the lists in the tree. | |
| 6885 | 1132 template <class Chunk_t, template <class> class FreeList_t> |
| 1133 class setTreeSurplusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { | |
| 0 | 1134 double percentage; |
| 1135 public: | |
| 1136 setTreeSurplusClosure(double v) { percentage = v; } | |
| 6885 | 1137 void do_list(FreeList<Chunk_t>* fl) {} |
| 1138 | |
|
8001
db9981fd3124
8005915: Unify SERIALGC and INCLUDE_ALTERNATE_GCS
jprovino
parents:
7446
diff
changeset
|
1139 #if INCLUDE_ALL_GCS |
| 6885 | 1140 void do_list(AdaptiveFreeList<Chunk_t>* fl) { |
| 0 | 1141 double splitSurplusPercent = percentage; |
| 1142 fl->set_surplus(fl->count() - | |
| 1143 (ssize_t)((double)fl->desired() * splitSurplusPercent)); | |
| 1144 } | |
|
8001
db9981fd3124
8005915: Unify SERIALGC and INCLUDE_ALTERNATE_GCS
jprovino
parents:
7446
diff
changeset
|
1145 #endif // INCLUDE_ALL_GCS |
| 0 | 1146 }; |
| 1147 | |
| 6885 | 1148 template <class Chunk_t, template <class> class FreeList_t> |
| 1149 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_surplus(double splitSurplusPercent) { | |
| 1150 setTreeSurplusClosure<Chunk_t, FreeList_t> sts(splitSurplusPercent); | |
| 0 | 1151 sts.do_tree(root()); |
| 1152 } | |
| 1153 | |
| 1154 // Set hints for the lists in the tree. | |
| 6885 | 1155 template <class Chunk_t, template <class> class FreeList_t> |
| 1156 class setTreeHintsClosure : public DescendTreeCensusClosure<Chunk_t, FreeList_t> { | |
| 0 | 1157 size_t hint; |
| 1158 public: | |
| 1159 setTreeHintsClosure(size_t v) { hint = v; } | |
| 6885 | 1160 void do_list(FreeList<Chunk_t>* fl) {} |
| 1161 | |
|
8001
db9981fd3124
8005915: Unify SERIALGC and INCLUDE_ALTERNATE_GCS
jprovino
parents:
7446
diff
changeset
|
1162 #if INCLUDE_ALL_GCS |
| 6885 | 1163 void do_list(AdaptiveFreeList<Chunk_t>* fl) { |
| 0 | 1164 fl->set_hint(hint); |
| 1165 assert(fl->hint() == 0 || fl->hint() > fl->size(), | |
| 1166 "Current hint is inconsistent"); | |
| 1167 if (fl->surplus() > 0) { | |
| 1168 hint = fl->size(); | |
| 1169 } | |
| 1170 } | |
|
8001
db9981fd3124
8005915: Unify SERIALGC and INCLUDE_ALTERNATE_GCS
jprovino
parents:
7446
diff
changeset
|
1171 #endif // INCLUDE_ALL_GCS |
| 0 | 1172 }; |
| 1173 | |
| 6885 | 1174 template <class Chunk_t, template <class> class FreeList_t> |
| 1175 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_hints(void) { | |
| 1176 setTreeHintsClosure<Chunk_t, FreeList_t> sth(0); | |
| 0 | 1177 sth.do_tree(root()); |
| 1178 } | |
| 1179 | |
| 1180 // Save count before previous sweep and splits and coalesces. | |
| 6885 | 1181 template <class Chunk_t, template <class> class FreeList_t> |
| 1182 class clearTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { | |
| 1183 void do_list(FreeList<Chunk_t>* fl) {} | |
| 1184 | |
|
8001
db9981fd3124
8005915: Unify SERIALGC and INCLUDE_ALTERNATE_GCS
jprovino
parents:
7446
diff
changeset
|
1185 #if INCLUDE_ALL_GCS |
| 6885 | 1186 void do_list(AdaptiveFreeList<Chunk_t>* fl) { |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1187 fl->set_prev_sweep(fl->count()); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1188 fl->set_coal_births(0); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1189 fl->set_coal_deaths(0); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1190 fl->set_split_births(0); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1191 fl->set_split_deaths(0); |
| 0 | 1192 } |
|
8001
db9981fd3124
8005915: Unify SERIALGC and INCLUDE_ALTERNATE_GCS
jprovino
parents:
7446
diff
changeset
|
1193 #endif // INCLUDE_ALL_GCS |
| 0 | 1194 }; |
| 1195 | |
| 6885 | 1196 template <class Chunk_t, template <class> class FreeList_t> |
| 1197 void BinaryTreeDictionary<Chunk_t, FreeList_t>::clear_tree_census(void) { | |
| 1198 clearTreeCensusClosure<Chunk_t, FreeList_t> ctc; | |
| 0 | 1199 ctc.do_tree(root()); |
| 1200 } | |
| 1201 | |
| 1202 // Do reporting and post sweep clean up. | |
| 6885 | 1203 template <class Chunk_t, template <class> class FreeList_t> |
| 1204 void BinaryTreeDictionary<Chunk_t, FreeList_t>::end_sweep_dict_census(double splitSurplusPercent) { | |
| 0 | 1205 // Does walking the tree 3 times hurt? |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1206 set_tree_surplus(splitSurplusPercent); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1207 set_tree_hints(); |
| 0 | 1208 if (PrintGC && Verbose) { |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1209 report_statistics(); |
| 0 | 1210 } |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1211 clear_tree_census(); |
| 0 | 1212 } |
| 1213 | |
| 1214 // Print summary statistics | |
| 6885 | 1215 template <class Chunk_t, template <class> class FreeList_t> |
| 1216 void BinaryTreeDictionary<Chunk_t, FreeList_t>::report_statistics() const { | |
| 1217 FreeBlockDictionary<Chunk_t>::verify_par_locked(); | |
| 0 | 1218 gclog_or_tty->print("Statistics for BinaryTreeDictionary:\n" |
| 1219 "------------------------------------\n"); | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1220 size_t total_size = total_chunk_size(debug_only(NULL)); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1221 size_t free_blocks = num_free_blocks(); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1222 gclog_or_tty->print("Total Free Space: %d\n", total_size); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1223 gclog_or_tty->print("Max Chunk Size: %d\n", max_chunk_size()); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1224 gclog_or_tty->print("Number of Blocks: %d\n", free_blocks); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1225 if (free_blocks > 0) { |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1226 gclog_or_tty->print("Av. Block Size: %d\n", total_size/free_blocks); |
| 0 | 1227 } |
| 6885 | 1228 gclog_or_tty->print("Tree Height: %d\n", tree_height()); |
| 0 | 1229 } |
| 1230 | |
| 1231 // Print census information - counts, births, deaths, etc. | |
| 1232 // for each list in the tree. Also print some summary | |
| 1233 // information. | |
| 6885 | 1234 template <class Chunk_t, template <class> class FreeList_t> |
| 1235 class PrintTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { | |
|
12
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
1236 int _print_line; |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1237 size_t _total_free; |
| 6885 | 1238 FreeList_t<Chunk_t> _total; |
| 0 | 1239 |
| 1240 public: | |
|
1145
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1241 PrintTreeCensusClosure() { |
|
12
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
1242 _print_line = 0; |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1243 _total_free = 0; |
| 0 | 1244 } |
| 6885 | 1245 FreeList_t<Chunk_t>* total() { return &_total; } |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1246 size_t total_free() { return _total_free; } |
| 6885 | 1247 void do_list(FreeList<Chunk_t>* fl) { |
|
12
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
1248 if (++_print_line >= 40) { |
| 6885 | 1249 FreeList_t<Chunk_t>::print_labels_on(gclog_or_tty, "size"); |
|
12
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
1250 _print_line = 0; |
|
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
1251 } |
|
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
1252 fl->print_on(gclog_or_tty); |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1253 _total_free += fl->count() * fl->size() ; |
|
12
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
1254 total()->set_count( total()->count() + fl->count() ); |
| 6885 | 1255 } |
| 1256 | |
|
8001
db9981fd3124
8005915: Unify SERIALGC and INCLUDE_ALTERNATE_GCS
jprovino
parents:
7446
diff
changeset
|
1257 #if INCLUDE_ALL_GCS |
| 6885 | 1258 void do_list(AdaptiveFreeList<Chunk_t>* fl) { |
| 1259 if (++_print_line >= 40) { | |
| 1260 FreeList_t<Chunk_t>::print_labels_on(gclog_or_tty, "size"); | |
| 1261 _print_line = 0; | |
| 1262 } | |
| 1263 fl->print_on(gclog_or_tty); | |
| 1264 _total_free += fl->count() * fl->size() ; | |
| 1265 total()->set_count( total()->count() + fl->count() ); | |
| 1266 total()->set_bfr_surp( total()->bfr_surp() + fl->bfr_surp() ); | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1267 total()->set_surplus( total()->split_deaths() + fl->surplus() ); |
| 6885 | 1268 total()->set_desired( total()->desired() + fl->desired() ); |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1269 total()->set_prev_sweep( total()->prev_sweep() + fl->prev_sweep() ); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1270 total()->set_before_sweep(total()->before_sweep() + fl->before_sweep()); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1271 total()->set_coal_births( total()->coal_births() + fl->coal_births() ); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1272 total()->set_coal_deaths( total()->coal_deaths() + fl->coal_deaths() ); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1273 total()->set_split_births(total()->split_births() + fl->split_births()); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1274 total()->set_split_deaths(total()->split_deaths() + fl->split_deaths()); |
| 0 | 1275 } |
|
8001
db9981fd3124
8005915: Unify SERIALGC and INCLUDE_ALTERNATE_GCS
jprovino
parents:
7446
diff
changeset
|
1276 #endif // INCLUDE_ALL_GCS |
| 0 | 1277 }; |
| 1278 | |
| 6885 | 1279 template <class Chunk_t, template <class> class FreeList_t> |
| 1280 void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_dict_census(void) const { | |
| 0 | 1281 |
| 1282 gclog_or_tty->print("\nBinaryTree\n"); | |
| 6885 | 1283 FreeList_t<Chunk_t>::print_labels_on(gclog_or_tty, "size"); |
| 1284 PrintTreeCensusClosure<Chunk_t, FreeList_t> ptc; | |
| 0 | 1285 ptc.do_tree(root()); |
| 1286 | |
| 6885 | 1287 FreeList_t<Chunk_t>* total = ptc.total(); |
| 1288 FreeList_t<Chunk_t>::print_labels_on(gclog_or_tty, " "); | |
| 1289 } | |
| 1290 | |
|
8001
db9981fd3124
8005915: Unify SERIALGC and INCLUDE_ALTERNATE_GCS
jprovino
parents:
7446
diff
changeset
|
1291 #if INCLUDE_ALL_GCS |
| 6885 | 1292 template <> |
|
7947
3c327c2b6782
8004895: NPG: JMapPermCore test failure caused by warnings about missing field
jmasa
parents:
7446
diff
changeset
|
1293 void AFLBinaryTreeDictionary::print_dict_census(void) const { |
| 6885 | 1294 |
| 1295 gclog_or_tty->print("\nBinaryTree\n"); | |
| 1296 AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, "size"); | |
| 1297 PrintTreeCensusClosure<FreeChunk, AdaptiveFreeList> ptc; | |
| 1298 ptc.do_tree(root()); | |
| 1299 | |
| 1300 AdaptiveFreeList<FreeChunk>* total = ptc.total(); | |
| 1301 AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, " "); | |
|
12
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
1302 total->print_on(gclog_or_tty, "TOTAL\t"); |
| 0 | 1303 gclog_or_tty->print( |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1304 "total_free(words): " SIZE_FORMAT_W(16) |
|
12
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
1305 " growth: %8.5f deficit: %8.5f\n", |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1306 ptc.total_free(), |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1307 (double)(total->split_births() + total->coal_births() |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1308 - total->split_deaths() - total->coal_deaths()) |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1309 /(total->prev_sweep() != 0 ? (double)total->prev_sweep() : 1.0), |
|
12
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
1310 (double)(total->desired() - total->count()) |
|
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
1311 /(total->desired() != 0 ? (double)total->desired() : 1.0)); |
| 0 | 1312 } |
|
8001
db9981fd3124
8005915: Unify SERIALGC and INCLUDE_ALTERNATE_GCS
jprovino
parents:
7446
diff
changeset
|
1313 #endif // INCLUDE_ALL_GCS |
| 0 | 1314 |
| 6885 | 1315 template <class Chunk_t, template <class> class FreeList_t> |
| 1316 class PrintFreeListsClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { | |
|
1145
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1317 outputStream* _st; |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1318 int _print_line; |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1319 |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1320 public: |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1321 PrintFreeListsClosure(outputStream* st) { |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1322 _st = st; |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1323 _print_line = 0; |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1324 } |
| 6885 | 1325 void do_list(FreeList_t<Chunk_t>* fl) { |
|
1145
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1326 if (++_print_line >= 40) { |
| 6885 | 1327 FreeList_t<Chunk_t>::print_labels_on(_st, "size"); |
|
1145
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1328 _print_line = 0; |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1329 } |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1330 fl->print_on(gclog_or_tty); |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1331 size_t sz = fl->size(); |
| 6885 | 1332 for (Chunk_t* fc = fl->head(); fc != NULL; |
|
1145
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1333 fc = fc->next()) { |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1334 _st->print_cr("\t[" PTR_FORMAT "," PTR_FORMAT ") %s", |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1335 fc, (HeapWord*)fc + sz, |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1336 fc->cantCoalesce() ? "\t CC" : ""); |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1337 } |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1338 } |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1339 }; |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1340 |
| 6885 | 1341 template <class Chunk_t, template <class> class FreeList_t> |
| 1342 void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_free_lists(outputStream* st) const { | |
|
1145
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1343 |
| 6885 | 1344 FreeList_t<Chunk_t>::print_labels_on(st, "size"); |
| 1345 PrintFreeListsClosure<Chunk_t, FreeList_t> pflc(st); | |
|
1145
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1346 pflc.do_tree(root()); |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1347 } |
|
e018e6884bd8
6631166: CMS: better heuristics when combatting fragmentation
ysr
parents:
269
diff
changeset
|
1348 |
| 0 | 1349 // Verify the following tree invariants: |
| 1350 // . _root has no parent | |
| 1351 // . parent and child point to each other | |
| 1352 // . each node's key correctly related to that of its child(ren) | |
| 6885 | 1353 template <class Chunk_t, template <class> class FreeList_t> |
| 1354 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_tree() const { | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1355 guarantee(root() == NULL || total_free_blocks() == 0 || |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1356 total_size() != 0, "_total_size should't be 0?"); |
| 0 | 1357 guarantee(root() == NULL || root()->parent() == NULL, "_root shouldn't have parent"); |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1358 verify_tree_helper(root()); |
| 0 | 1359 } |
| 1360 | |
| 6885 | 1361 template <class Chunk_t, template <class> class FreeList_t> |
| 1362 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_prev_free_ptrs(TreeList<Chunk_t, FreeList_t>* tl) { | |
| 0 | 1363 size_t ct = 0; |
| 6885 | 1364 for (Chunk_t* curFC = tl->head(); curFC != NULL; curFC = curFC->next()) { |
| 0 | 1365 ct++; |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1366 assert(curFC->prev() == NULL || curFC->prev()->is_free(), |
| 0 | 1367 "Chunk should be free"); |
| 1368 } | |
| 1369 return ct; | |
| 1370 } | |
| 1371 | |
| 1372 // Note: this helper is recursive rather than iterative, so use with | |
| 1373 // caution on very deep trees; and watch out for stack overflow errors; | |
| 1374 // In general, to be used only for debugging. | |
| 6885 | 1375 template <class Chunk_t, template <class> class FreeList_t> |
| 1376 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_tree_helper(TreeList<Chunk_t, FreeList_t>* tl) const { | |
| 0 | 1377 if (tl == NULL) |
| 1378 return; | |
| 1379 guarantee(tl->size() != 0, "A list must has a size"); | |
| 1380 guarantee(tl->left() == NULL || tl->left()->parent() == tl, | |
| 1381 "parent<-/->left"); | |
| 1382 guarantee(tl->right() == NULL || tl->right()->parent() == tl, | |
| 1383 "parent<-/->right");; | |
| 1384 guarantee(tl->left() == NULL || tl->left()->size() < tl->size(), | |
| 1385 "parent !> left"); | |
| 1386 guarantee(tl->right() == NULL || tl->right()->size() > tl->size(), | |
| 1387 "parent !< left"); | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1388 guarantee(tl->head() == NULL || tl->head()->is_free(), "!Free"); |
| 0 | 1389 guarantee(tl->head() == NULL || tl->head_as_TreeChunk()->list() == tl, |
| 1390 "list inconsistency"); | |
| 1391 guarantee(tl->count() > 0 || (tl->head() == NULL && tl->tail() == NULL), | |
| 1392 "list count is inconsistent"); | |
| 1393 guarantee(tl->count() > 1 || tl->head() == tl->tail(), | |
| 1394 "list is incorrectly constructed"); | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1395 size_t count = verify_prev_free_ptrs(tl); |
| 0 | 1396 guarantee(count == (size_t)tl->count(), "Node count is incorrect"); |
| 1397 if (tl->head() != NULL) { | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1398 tl->head_as_TreeChunk()->verify_tree_chunk_list(); |
| 0 | 1399 } |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1400 verify_tree_helper(tl->left()); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1401 verify_tree_helper(tl->right()); |
| 0 | 1402 } |
| 1403 | |
| 6885 | 1404 template <class Chunk_t, template <class> class FreeList_t> |
| 1405 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify() const { | |
|
6028
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1406 verify_tree(); |
|
f69a5d43dc19
7164144: Fix variable naming style in freeBlockDictionary.* and binaryTreeDictionary*
jmasa
parents:
6026
diff
changeset
|
1407 guarantee(total_size() == total_size_in_tree(root()), "Total Size inconsistency"); |
| 0 | 1408 } |
| 6026 | 1409 |
| 6885 | 1410 template class TreeList<Metablock, FreeList>; |
| 1411 template class BinaryTreeDictionary<Metablock, FreeList>; | |
| 1412 template class TreeChunk<Metablock, FreeList>; | |
| 1413 | |
| 1414 template class TreeList<Metachunk, FreeList>; | |
| 1415 template class BinaryTreeDictionary<Metachunk, FreeList>; | |
| 1416 template class TreeChunk<Metachunk, FreeList>; | |
| 1417 | |
| 1418 | |
|
8001
db9981fd3124
8005915: Unify SERIALGC and INCLUDE_ALTERNATE_GCS
jprovino
parents:
7446
diff
changeset
|
1419 #if INCLUDE_ALL_GCS |
| 6026 | 1420 // Explicitly instantiate these types for FreeChunk. |
| 6885 | 1421 template class TreeList<FreeChunk, AdaptiveFreeList>; |
| 1422 template class BinaryTreeDictionary<FreeChunk, AdaptiveFreeList>; | |
| 1423 template class TreeChunk<FreeChunk, AdaptiveFreeList>; | |
| 1424 | |
|
8001
db9981fd3124
8005915: Unify SERIALGC and INCLUDE_ALTERNATE_GCS
jprovino
parents:
7446
diff
changeset
|
1425 #endif // INCLUDE_ALL_GCS |