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