Mercurial > hg > graal-jvmci-8
comparison src/share/vm/memory/binaryTreeDictionary.cpp @ 14909:4ca6dc0799b6
Backout jdk9 merge
author | Gilles Duboscq <duboscq@ssw.jku.at> |
---|---|
date | Tue, 01 Apr 2014 13:57:07 +0200 |
parents | aa8fab3bed11 |
children | 52b4284cb496 |
comparison
equal
deleted
inserted
replaced
14908:8db6e76cb658 | 14909:4ca6dc0799b6 |
---|---|
42 //////////////////////////////////////////////////////////////////////////////// | 42 //////////////////////////////////////////////////////////////////////////////// |
43 // A binary tree based search structure for free blocks. | 43 // A binary tree based search structure for free blocks. |
44 // This is currently used in the Concurrent Mark&Sweep implementation. | 44 // This is currently used in the Concurrent Mark&Sweep implementation. |
45 //////////////////////////////////////////////////////////////////////////////// | 45 //////////////////////////////////////////////////////////////////////////////// |
46 | 46 |
47 template <class Chunk_t, class FreeList_t> | 47 template <class Chunk_t, template <class> class FreeList_t> |
48 size_t TreeChunk<Chunk_t, FreeList_t>::_min_tree_chunk_size = sizeof(TreeChunk<Chunk_t, FreeList_t>)/HeapWordSize; | 48 size_t TreeChunk<Chunk_t, FreeList_t>::_min_tree_chunk_size = sizeof(TreeChunk<Chunk_t, FreeList_t>)/HeapWordSize; |
49 | 49 |
50 template <class Chunk_t, class FreeList_t> | 50 template <class Chunk_t, template <class> class FreeList_t> |
51 TreeChunk<Chunk_t, FreeList_t>* TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(Chunk_t* fc) { | 51 TreeChunk<Chunk_t, FreeList_t>* TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(Chunk_t* fc) { |
52 // Do some assertion checking here. | 52 // Do some assertion checking here. |
53 return (TreeChunk<Chunk_t, FreeList_t>*) fc; | 53 return (TreeChunk<Chunk_t, FreeList_t>*) fc; |
54 } | 54 } |
55 | 55 |
56 template <class Chunk_t, class FreeList_t> | 56 template <class Chunk_t, template <class> class FreeList_t> |
57 void TreeChunk<Chunk_t, FreeList_t>::verify_tree_chunk_list() const { | 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(); | 58 TreeChunk<Chunk_t, FreeList_t>* nextTC = (TreeChunk<Chunk_t, FreeList_t>*)next(); |
59 if (prev() != NULL) { // interior list node shouldn't have tree fields | 59 if (prev() != NULL) { // interior list node shouldn'r have tree fields |
60 guarantee(embedded_list()->parent() == NULL && embedded_list()->left() == NULL && | 60 guarantee(embedded_list()->parent() == NULL && embedded_list()->left() == NULL && |
61 embedded_list()->right() == NULL, "should be clear"); | 61 embedded_list()->right() == NULL, "should be clear"); |
62 } | 62 } |
63 if (nextTC != NULL) { | 63 if (nextTC != NULL) { |
64 guarantee(as_TreeChunk(nextTC->prev()) == this, "broken chain"); | 64 guarantee(as_TreeChunk(nextTC->prev()) == this, "broken chain"); |
65 guarantee(nextTC->size() == size(), "wrong size"); | 65 guarantee(nextTC->size() == size(), "wrong size"); |
66 nextTC->verify_tree_chunk_list(); | 66 nextTC->verify_tree_chunk_list(); |
67 } | 67 } |
68 } | 68 } |
69 | 69 |
70 template <class Chunk_t, class FreeList_t> | 70 template <class Chunk_t, template <class> class FreeList_t> |
71 TreeList<Chunk_t, FreeList_t>::TreeList() : _parent(NULL), | 71 TreeList<Chunk_t, FreeList_t>::TreeList() : _parent(NULL), |
72 _left(NULL), _right(NULL) {} | 72 _left(NULL), _right(NULL) {} |
73 | 73 |
74 template <class Chunk_t, class FreeList_t> | 74 template <class Chunk_t, template <class> class FreeList_t> |
75 TreeList<Chunk_t, FreeList_t>* | 75 TreeList<Chunk_t, FreeList_t>* |
76 TreeList<Chunk_t, FreeList_t>::as_TreeList(TreeChunk<Chunk_t,FreeList_t>* tc) { | 76 TreeList<Chunk_t, FreeList_t>::as_TreeList(TreeChunk<Chunk_t,FreeList_t>* tc) { |
77 // This first free chunk in the list will be the tree list. | 77 // This first free chunk in the list will be the tree list. |
78 assert((tc->size() >= (TreeChunk<Chunk_t, FreeList_t>::min_size())), | 78 assert((tc->size() >= (TreeChunk<Chunk_t, FreeList_t>::min_size())), |
79 "Chunk is too small for a TreeChunk"); | 79 "Chunk is too small for a TreeChunk"); |
86 tl->set_count(1); | 86 tl->set_count(1); |
87 assert(tl->parent() == NULL, "Should be clear"); | 87 assert(tl->parent() == NULL, "Should be clear"); |
88 return tl; | 88 return tl; |
89 } | 89 } |
90 | 90 |
91 template <class Chunk_t, class FreeList_t> | 91 |
92 template <class Chunk_t, template <class> class FreeList_t> | |
93 TreeList<Chunk_t, FreeList_t>* | |
94 get_chunk(size_t size, enum FreeBlockDictionary<Chunk_t>::Dither dither) { | |
95 FreeBlockDictionary<Chunk_t>::verify_par_locked(); | |
96 Chunk_t* res = get_chunk_from_tree(size, dither); | |
97 assert(res == NULL || res->is_free(), | |
98 "Should be returning a free chunk"); | |
99 assert(dither != FreeBlockDictionary<Chunk_t>::exactly || | |
100 res->size() == size, "Not correct size"); | |
101 return res; | |
102 } | |
103 | |
104 template <class Chunk_t, template <class> class FreeList_t> | |
92 TreeList<Chunk_t, FreeList_t>* | 105 TreeList<Chunk_t, FreeList_t>* |
93 TreeList<Chunk_t, FreeList_t>::as_TreeList(HeapWord* addr, size_t size) { | 106 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; | 107 TreeChunk<Chunk_t, FreeList_t>* tc = (TreeChunk<Chunk_t, FreeList_t>*) addr; |
95 assert((size >= TreeChunk<Chunk_t, FreeList_t>::min_size()), | 108 assert((size >= TreeChunk<Chunk_t, FreeList_t>::min_size()), |
96 "Chunk is too small for a TreeChunk"); | 109 "Chunk is too small for a TreeChunk"); |
110 // Specialize for AdaptiveFreeList which tries to avoid | 123 // Specialize for AdaptiveFreeList which tries to avoid |
111 // splitting a chunk of a size that is under populated in favor of | 124 // 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 | 125 // an over populated size. The general get_better_list() just returns |
113 // the current list. | 126 // the current list. |
114 template <> | 127 template <> |
115 TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >* | 128 TreeList<FreeChunk, AdaptiveFreeList>* |
116 TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >::get_better_list( | 129 TreeList<FreeChunk, AdaptiveFreeList>::get_better_list( |
117 BinaryTreeDictionary<FreeChunk, ::AdaptiveFreeList<FreeChunk> >* dictionary) { | 130 BinaryTreeDictionary<FreeChunk, ::AdaptiveFreeList>* dictionary) { |
118 // A candidate chunk has been found. If it is already under | 131 // A candidate chunk has been found. If it is already under |
119 // populated, get a chunk associated with the hint for this | 132 // populated, get a chunk associated with the hint for this |
120 // chunk. | 133 // chunk. |
121 | 134 |
122 TreeList<FreeChunk, ::AdaptiveFreeList<FreeChunk> >* curTL = this; | 135 TreeList<FreeChunk, ::AdaptiveFreeList>* curTL = this; |
123 if (surplus() <= 0) { | 136 if (surplus() <= 0) { |
124 /* Use the hint to find a size with a surplus, and reset the hint. */ | 137 /* Use the hint to find a size with a surplus, and reset the hint. */ |
125 TreeList<FreeChunk, ::AdaptiveFreeList<FreeChunk> >* hintTL = this; | 138 TreeList<FreeChunk, ::AdaptiveFreeList>* hintTL = this; |
126 while (hintTL->hint() != 0) { | 139 while (hintTL->hint() != 0) { |
127 assert(hintTL->hint() > hintTL->size(), | 140 assert(hintTL->hint() > hintTL->size(), |
128 "hint points in the wrong direction"); | 141 "hint points in the wrong direction"); |
129 hintTL = dictionary->find_list(hintTL->hint()); | 142 hintTL = dictionary->find_list(hintTL->hint()); |
130 assert(curTL != hintTL, "Infinite loop"); | 143 assert(curTL != hintTL, "Infinite loop"); |
148 } | 161 } |
149 return curTL; | 162 return curTL; |
150 } | 163 } |
151 #endif // INCLUDE_ALL_GCS | 164 #endif // INCLUDE_ALL_GCS |
152 | 165 |
153 template <class Chunk_t, class FreeList_t> | 166 template <class Chunk_t, template <class> class FreeList_t> |
154 TreeList<Chunk_t, FreeList_t>* | 167 TreeList<Chunk_t, FreeList_t>* |
155 TreeList<Chunk_t, FreeList_t>::get_better_list( | 168 TreeList<Chunk_t, FreeList_t>::get_better_list( |
156 BinaryTreeDictionary<Chunk_t, FreeList_t>* dictionary) { | 169 BinaryTreeDictionary<Chunk_t, FreeList_t>* dictionary) { |
157 return this; | 170 return this; |
158 } | 171 } |
159 | 172 |
160 template <class Chunk_t, class FreeList_t> | 173 template <class Chunk_t, template <class> class FreeList_t> |
161 TreeList<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::remove_chunk_replace_if_needed(TreeChunk<Chunk_t, FreeList_t>* tc) { | 174 TreeList<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::remove_chunk_replace_if_needed(TreeChunk<Chunk_t, FreeList_t>* tc) { |
162 | 175 |
163 TreeList<Chunk_t, FreeList_t>* retTL = this; | 176 TreeList<Chunk_t, FreeList_t>* retTL = this; |
164 Chunk_t* list = head(); | 177 Chunk_t* list = head(); |
165 assert(!list || list != list->next(), "Chunk on list twice"); | 178 assert(!list || list != list->next(), "Chunk on list twice"); |
232 } | 245 } |
233 // Chunk is interior to the list | 246 // Chunk is interior to the list |
234 prevFC->link_after(nextTC); | 247 prevFC->link_after(nextTC); |
235 } | 248 } |
236 | 249 |
237 // Below this point the embedded TreeList<Chunk_t, FreeList_t> being used for the | 250 // Below this point the embeded TreeList<Chunk_t, FreeList_t> being used for the |
238 // tree node may have changed. Don't use "this" | 251 // tree node may have changed. Don't use "this" |
239 // TreeList<Chunk_t, FreeList_t>*. | 252 // TreeList<Chunk_t, FreeList_t>*. |
240 // chunk should still be a free chunk (bit set in _prev) | 253 // chunk should still be a free chunk (bit set in _prev) |
241 assert(!retTL->head() || retTL->size() == retTL->head()->size(), | 254 assert(!retTL->head() || retTL->size() == retTL->head()->size(), |
242 "Wrong sized chunk in list"); | 255 "Wrong sized chunk in list"); |
271 assert(retTL->tail() == NULL || retTL->tail()->next() == NULL, | 284 assert(retTL->tail() == NULL || retTL->tail()->next() == NULL, |
272 "list invariant"); | 285 "list invariant"); |
273 return retTL; | 286 return retTL; |
274 } | 287 } |
275 | 288 |
276 template <class Chunk_t, class FreeList_t> | 289 template <class Chunk_t, template <class> class FreeList_t> |
277 void TreeList<Chunk_t, FreeList_t>::return_chunk_at_tail(TreeChunk<Chunk_t, FreeList_t>* chunk) { | 290 void TreeList<Chunk_t, FreeList_t>::return_chunk_at_tail(TreeChunk<Chunk_t, FreeList_t>* chunk) { |
278 assert(chunk != NULL, "returning NULL chunk"); | 291 assert(chunk != NULL, "returning NULL chunk"); |
279 assert(chunk->list() == this, "list should be set for chunk"); | 292 assert(chunk->list() == this, "list should be set for chunk"); |
280 assert(tail() != NULL, "The tree list is embedded in the first chunk"); | 293 assert(tail() != NULL, "The tree list is embedded in the first chunk"); |
281 // which means that the list can never be empty. | 294 // which means that the list can never be empty. |
286 Chunk_t* fc = tail(); | 299 Chunk_t* fc = tail(); |
287 fc->link_after(chunk); | 300 fc->link_after(chunk); |
288 this->link_tail(chunk); | 301 this->link_tail(chunk); |
289 | 302 |
290 assert(!tail() || size() == tail()->size(), "Wrong sized chunk in list"); | 303 assert(!tail() || size() == tail()->size(), "Wrong sized chunk in list"); |
291 FreeList_t::increment_count(); | 304 FreeList_t<Chunk_t>::increment_count(); |
292 debug_only(this->increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));) | 305 debug_only(this->increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));) |
293 assert(head() == NULL || head()->prev() == NULL, "list invariant"); | 306 assert(head() == NULL || head()->prev() == NULL, "list invariant"); |
294 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); | 307 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); |
295 } | 308 } |
296 | 309 |
297 // Add this chunk at the head of the list. "At the head of the list" | 310 // 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 | 311 // is defined to be after the chunk pointer to by head(). This is |
299 // because the TreeList<Chunk_t, FreeList_t> is embedded in the first TreeChunk<Chunk_t, FreeList_t> in the | 312 // 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>. | 313 // list. See the definition of TreeChunk<Chunk_t, FreeList_t>. |
301 template <class Chunk_t, class FreeList_t> | 314 template <class Chunk_t, template <class> class FreeList_t> |
302 void TreeList<Chunk_t, FreeList_t>::return_chunk_at_head(TreeChunk<Chunk_t, FreeList_t>* chunk) { | 315 void TreeList<Chunk_t, FreeList_t>::return_chunk_at_head(TreeChunk<Chunk_t, FreeList_t>* chunk) { |
303 assert(chunk->list() == this, "list should be set for chunk"); | 316 assert(chunk->list() == this, "list should be set for chunk"); |
304 assert(head() != NULL, "The tree list is embedded in the first chunk"); | 317 assert(head() != NULL, "The tree list is embedded in the first chunk"); |
305 assert(chunk != NULL, "returning NULL chunk"); | 318 assert(chunk != NULL, "returning NULL chunk"); |
306 assert(!this->verify_chunk_in_free_list(chunk), "Double entry"); | 319 assert(!this->verify_chunk_in_free_list(chunk), "Double entry"); |
314 assert(tail() == NULL, "List is inconsistent"); | 327 assert(tail() == NULL, "List is inconsistent"); |
315 this->link_tail(chunk); | 328 this->link_tail(chunk); |
316 } | 329 } |
317 head()->link_after(chunk); | 330 head()->link_after(chunk); |
318 assert(!head() || size() == head()->size(), "Wrong sized chunk in list"); | 331 assert(!head() || size() == head()->size(), "Wrong sized chunk in list"); |
319 FreeList_t::increment_count(); | 332 FreeList_t<Chunk_t>::increment_count(); |
320 debug_only(this->increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));) | 333 debug_only(this->increment_returned_bytes_by(chunk->size()*sizeof(HeapWord));) |
321 assert(head() == NULL || head()->prev() == NULL, "list invariant"); | 334 assert(head() == NULL || head()->prev() == NULL, "list invariant"); |
322 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); | 335 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); |
323 } | 336 } |
324 | 337 |
325 template <class Chunk_t, class FreeList_t> | 338 template <class Chunk_t, template <class> class FreeList_t> |
326 void TreeChunk<Chunk_t, FreeList_t>::assert_is_mangled() const { | 339 void TreeChunk<Chunk_t, FreeList_t>::assert_is_mangled() const { |
327 assert((ZapUnusedHeapArea && | 340 assert((ZapUnusedHeapArea && |
328 SpaceMangler::is_mangled((HeapWord*) Chunk_t::size_addr()) && | 341 SpaceMangler::is_mangled((HeapWord*) Chunk_t::size_addr()) && |
329 SpaceMangler::is_mangled((HeapWord*) Chunk_t::prev_addr()) && | 342 SpaceMangler::is_mangled((HeapWord*) Chunk_t::prev_addr()) && |
330 SpaceMangler::is_mangled((HeapWord*) Chunk_t::next_addr())) || | 343 SpaceMangler::is_mangled((HeapWord*) Chunk_t::next_addr())) || |
331 (size() == 0 && prev() == NULL && next() == NULL), | 344 (size() == 0 && prev() == NULL && next() == NULL), |
332 "Space should be clear or mangled"); | 345 "Space should be clear or mangled"); |
333 } | 346 } |
334 | 347 |
335 template <class Chunk_t, class FreeList_t> | 348 template <class Chunk_t, template <class> class FreeList_t> |
336 TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::head_as_TreeChunk() { | 349 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), | 350 assert(head() == NULL || (TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(head())->list() == this), |
338 "Wrong type of chunk?"); | 351 "Wrong type of chunk?"); |
339 return TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(head()); | 352 return TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(head()); |
340 } | 353 } |
341 | 354 |
342 template <class Chunk_t, class FreeList_t> | 355 template <class Chunk_t, template <class> class FreeList_t> |
343 TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::first_available() { | 356 TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::first_available() { |
344 assert(head() != NULL, "The head of the list cannot be NULL"); | 357 assert(head() != NULL, "The head of the list cannot be NULL"); |
345 Chunk_t* fc = head()->next(); | 358 Chunk_t* fc = head()->next(); |
346 TreeChunk<Chunk_t, FreeList_t>* retTC; | 359 TreeChunk<Chunk_t, FreeList_t>* retTC; |
347 if (fc == NULL) { | 360 if (fc == NULL) { |
354 } | 367 } |
355 | 368 |
356 // Returns the block with the largest heap address amongst | 369 // Returns the block with the largest heap address amongst |
357 // those in the list for this size; potentially slow and expensive, | 370 // those in the list for this size; potentially slow and expensive, |
358 // use with caution! | 371 // use with caution! |
359 template <class Chunk_t, class FreeList_t> | 372 template <class Chunk_t, template <class> class FreeList_t> |
360 TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::largest_address() { | 373 TreeChunk<Chunk_t, FreeList_t>* TreeList<Chunk_t, FreeList_t>::largest_address() { |
361 assert(head() != NULL, "The head of the list cannot be NULL"); | 374 assert(head() != NULL, "The head of the list cannot be NULL"); |
362 Chunk_t* fc = head()->next(); | 375 Chunk_t* fc = head()->next(); |
363 TreeChunk<Chunk_t, FreeList_t>* retTC; | 376 TreeChunk<Chunk_t, FreeList_t>* retTC; |
364 if (fc == NULL) { | 377 if (fc == NULL) { |
377 } | 390 } |
378 assert(retTC->list() == this, "Wrong type of chunk."); | 391 assert(retTC->list() == this, "Wrong type of chunk."); |
379 return retTC; | 392 return retTC; |
380 } | 393 } |
381 | 394 |
382 template <class Chunk_t, class FreeList_t> | 395 template <class Chunk_t, template <class> class FreeList_t> |
383 BinaryTreeDictionary<Chunk_t, FreeList_t>::BinaryTreeDictionary(MemRegion mr) { | 396 BinaryTreeDictionary<Chunk_t, FreeList_t>::BinaryTreeDictionary(MemRegion mr) { |
384 assert((mr.byte_size() > min_size()), "minimum chunk size"); | 397 assert((mr.byte_size() > min_size()), "minimum chunk size"); |
385 | 398 |
386 reset(mr); | 399 reset(mr); |
387 assert(root()->left() == NULL, "reset check failed"); | 400 assert(root()->left() == NULL, "reset check failed"); |
390 assert(root()->head()->prev() == NULL, "reset check failed"); | 403 assert(root()->head()->prev() == NULL, "reset check failed"); |
391 assert(total_size() == root()->size(), "reset check failed"); | 404 assert(total_size() == root()->size(), "reset check failed"); |
392 assert(total_free_blocks() == 1, "reset check failed"); | 405 assert(total_free_blocks() == 1, "reset check failed"); |
393 } | 406 } |
394 | 407 |
395 template <class Chunk_t, class FreeList_t> | 408 template <class Chunk_t, template <class> class FreeList_t> |
396 void BinaryTreeDictionary<Chunk_t, FreeList_t>::inc_total_size(size_t inc) { | 409 void BinaryTreeDictionary<Chunk_t, FreeList_t>::inc_total_size(size_t inc) { |
397 _total_size = _total_size + inc; | 410 _total_size = _total_size + inc; |
398 } | 411 } |
399 | 412 |
400 template <class Chunk_t, class FreeList_t> | 413 template <class Chunk_t, template <class> class FreeList_t> |
401 void BinaryTreeDictionary<Chunk_t, FreeList_t>::dec_total_size(size_t dec) { | 414 void BinaryTreeDictionary<Chunk_t, FreeList_t>::dec_total_size(size_t dec) { |
402 _total_size = _total_size - dec; | 415 _total_size = _total_size - dec; |
403 } | 416 } |
404 | 417 |
405 template <class Chunk_t, class FreeList_t> | 418 template <class Chunk_t, template <class> class FreeList_t> |
406 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset(MemRegion mr) { | 419 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset(MemRegion mr) { |
407 assert((mr.byte_size() > min_size()), "minimum chunk size"); | 420 assert((mr.byte_size() > min_size()), "minimum chunk size"); |
408 set_root(TreeList<Chunk_t, FreeList_t>::as_TreeList(mr.start(), mr.word_size())); | 421 set_root(TreeList<Chunk_t, FreeList_t>::as_TreeList(mr.start(), mr.word_size())); |
409 set_total_size(mr.word_size()); | 422 set_total_size(mr.word_size()); |
410 set_total_free_blocks(1); | 423 set_total_free_blocks(1); |
411 } | 424 } |
412 | 425 |
413 template <class Chunk_t, class FreeList_t> | 426 template <class Chunk_t, template <class> class FreeList_t> |
414 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset(HeapWord* addr, size_t byte_size) { | 427 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset(HeapWord* addr, size_t byte_size) { |
415 MemRegion mr(addr, heap_word_size(byte_size)); | 428 MemRegion mr(addr, heap_word_size(byte_size)); |
416 reset(mr); | 429 reset(mr); |
417 } | 430 } |
418 | 431 |
419 template <class Chunk_t, class FreeList_t> | 432 template <class Chunk_t, template <class> class FreeList_t> |
420 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset() { | 433 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset() { |
421 set_root(NULL); | 434 set_root(NULL); |
422 set_total_size(0); | 435 set_total_size(0); |
423 set_total_free_blocks(0); | 436 set_total_free_blocks(0); |
424 } | 437 } |
425 | 438 |
426 // Get a free block of size at least size from tree, or NULL. | 439 // Get a free block of size at least size from tree, or NULL. |
427 template <class Chunk_t, class FreeList_t> | 440 template <class Chunk_t, template <class> class FreeList_t> |
428 TreeChunk<Chunk_t, FreeList_t>* | 441 TreeChunk<Chunk_t, FreeList_t>* |
429 BinaryTreeDictionary<Chunk_t, FreeList_t>::get_chunk_from_tree( | 442 BinaryTreeDictionary<Chunk_t, FreeList_t>::get_chunk_from_tree( |
430 size_t size, | 443 size_t size, |
431 enum FreeBlockDictionary<Chunk_t>::Dither dither) | 444 enum FreeBlockDictionary<Chunk_t>::Dither dither) |
432 { | 445 { |
481 verify(); | 494 verify(); |
482 } | 495 } |
483 return retTC; | 496 return retTC; |
484 } | 497 } |
485 | 498 |
486 template <class Chunk_t, class FreeList_t> | 499 template <class Chunk_t, template <class> class FreeList_t> |
487 TreeList<Chunk_t, FreeList_t>* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_list(size_t size) const { | 500 TreeList<Chunk_t, FreeList_t>* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_list(size_t size) const { |
488 TreeList<Chunk_t, FreeList_t>* curTL; | 501 TreeList<Chunk_t, FreeList_t>* curTL; |
489 for (curTL = root(); curTL != NULL;) { | 502 for (curTL = root(); curTL != NULL;) { |
490 if (curTL->size() == size) { // exact match | 503 if (curTL->size() == size) { // exact match |
491 break; | 504 break; |
500 } | 513 } |
501 return curTL; | 514 return curTL; |
502 } | 515 } |
503 | 516 |
504 | 517 |
505 template <class Chunk_t, class FreeList_t> | 518 template <class Chunk_t, template <class> class FreeList_t> |
506 bool BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_chunk_in_free_list(Chunk_t* tc) const { | 519 bool BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_chunk_in_free_list(Chunk_t* tc) const { |
507 size_t size = tc->size(); | 520 size_t size = tc->size(); |
508 TreeList<Chunk_t, FreeList_t>* tl = find_list(size); | 521 TreeList<Chunk_t, FreeList_t>* tl = find_list(size); |
509 if (tl == NULL) { | 522 if (tl == NULL) { |
510 return false; | 523 return false; |
511 } else { | 524 } else { |
512 return tl->verify_chunk_in_free_list(tc); | 525 return tl->verify_chunk_in_free_list(tc); |
513 } | 526 } |
514 } | 527 } |
515 | 528 |
516 template <class Chunk_t, class FreeList_t> | 529 template <class Chunk_t, template <class> class FreeList_t> |
517 Chunk_t* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_largest_dict() const { | 530 Chunk_t* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_largest_dict() const { |
518 TreeList<Chunk_t, FreeList_t> *curTL = root(); | 531 TreeList<Chunk_t, FreeList_t> *curTL = root(); |
519 if (curTL != NULL) { | 532 if (curTL != NULL) { |
520 while(curTL->right() != NULL) curTL = curTL->right(); | 533 while(curTL->right() != NULL) curTL = curTL->right(); |
521 return curTL->largest_address(); | 534 return curTL->largest_address(); |
526 | 539 |
527 // Remove the current chunk from the tree. If it is not the last | 540 // 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. | 541 // 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), | 542 // If it is the last chunk in the list (the next link is NULL), |
530 // remove the node and repair the tree. | 543 // remove the node and repair the tree. |
531 template <class Chunk_t, class FreeList_t> | 544 template <class Chunk_t, template <class> class FreeList_t> |
532 TreeChunk<Chunk_t, FreeList_t>* | 545 TreeChunk<Chunk_t, FreeList_t>* |
533 BinaryTreeDictionary<Chunk_t, FreeList_t>::remove_chunk_from_tree(TreeChunk<Chunk_t, FreeList_t>* tc) { | 546 BinaryTreeDictionary<Chunk_t, FreeList_t>::remove_chunk_from_tree(TreeChunk<Chunk_t, FreeList_t>* tc) { |
534 assert(tc != NULL, "Should not call with a NULL chunk"); | 547 assert(tc != NULL, "Should not call with a NULL chunk"); |
535 assert(tc->is_free(), "Header is not marked correctly"); | 548 assert(tc->is_free(), "Header is not marked correctly"); |
536 | 549 |
667 } | 680 } |
668 | 681 |
669 // Remove the leftmost node (lm) in the tree and return it. | 682 // 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 | 683 // If lm has a right child, link it to the left node of |
671 // the parent of lm. | 684 // the parent of lm. |
672 template <class Chunk_t, class FreeList_t> | 685 template <class Chunk_t, template <class> class FreeList_t> |
673 TreeList<Chunk_t, FreeList_t>* BinaryTreeDictionary<Chunk_t, FreeList_t>::remove_tree_minimum(TreeList<Chunk_t, FreeList_t>* tl) { | 686 TreeList<Chunk_t, FreeList_t>* BinaryTreeDictionary<Chunk_t, FreeList_t>::remove_tree_minimum(TreeList<Chunk_t, FreeList_t>* tl) { |
674 assert(tl != NULL && tl->parent() != NULL, "really need a proper sub-tree"); | 687 assert(tl != NULL && tl->parent() != NULL, "really need a proper sub-tree"); |
675 // locate the subtree minimum by walking down left branches | 688 // locate the subtree minimum by walking down left branches |
676 TreeList<Chunk_t, FreeList_t>* curTL = tl; | 689 TreeList<Chunk_t, FreeList_t>* curTL = tl; |
677 for (; curTL->left() != NULL; curTL = curTL->left()); | 690 for (; curTL->left() != NULL; curTL = curTL->left()); |
688 } | 701 } |
689 } else { | 702 } else { |
690 // The only use of this method would not pass the root of the | 703 // 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 | 704 // tree (as indicated by the assertion above that the tree list |
692 // has a parent) but the specification does not explicitly exclude the | 705 // has a parent) but the specification does not explicitly exclude the |
693 // passing of the root so accommodate it. | 706 // passing of the root so accomodate it. |
694 set_root(NULL); | 707 set_root(NULL); |
695 } | 708 } |
696 debug_only( | 709 debug_only( |
697 curTL->clear_parent(); // Test if this needs to be cleared | 710 curTL->clear_parent(); // Test if this needs to be cleared |
698 curTL->clear_right(); // recall, above, left child is already null | 711 curTL->clear_right(); // recall, above, left child is already null |
702 verify_tree(); | 715 verify_tree(); |
703 } | 716 } |
704 return curTL; | 717 return curTL; |
705 } | 718 } |
706 | 719 |
707 template <class Chunk_t, class FreeList_t> | 720 template <class Chunk_t, template <class> class FreeList_t> |
708 void BinaryTreeDictionary<Chunk_t, FreeList_t>::insert_chunk_in_tree(Chunk_t* fc) { | 721 void BinaryTreeDictionary<Chunk_t, FreeList_t>::insert_chunk_in_tree(Chunk_t* fc) { |
709 TreeList<Chunk_t, FreeList_t> *curTL, *prevTL; | 722 TreeList<Chunk_t, FreeList_t> *curTL, *prevTL; |
710 size_t size = fc->size(); | 723 size_t size = fc->size(); |
711 | 724 |
712 assert((size >= min_size()), | 725 assert((size >= min_size()), |
768 if (FLSVerifyDictionary) { | 781 if (FLSVerifyDictionary) { |
769 verify_tree(); | 782 verify_tree(); |
770 } | 783 } |
771 } | 784 } |
772 | 785 |
773 template <class Chunk_t, class FreeList_t> | 786 template <class Chunk_t, template <class> class FreeList_t> |
774 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::max_chunk_size() const { | 787 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::max_chunk_size() const { |
775 FreeBlockDictionary<Chunk_t>::verify_par_locked(); | 788 FreeBlockDictionary<Chunk_t>::verify_par_locked(); |
776 TreeList<Chunk_t, FreeList_t>* tc = root(); | 789 TreeList<Chunk_t, FreeList_t>* tc = root(); |
777 if (tc == NULL) return 0; | 790 if (tc == NULL) return 0; |
778 for (; tc->right() != NULL; tc = tc->right()); | 791 for (; tc->right() != NULL; tc = tc->right()); |
779 return tc->size(); | 792 return tc->size(); |
780 } | 793 } |
781 | 794 |
782 template <class Chunk_t, class FreeList_t> | 795 template <class Chunk_t, template <class> class FreeList_t> |
783 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_list_length(TreeList<Chunk_t, FreeList_t>* tl) const { | 796 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_list_length(TreeList<Chunk_t, FreeList_t>* tl) const { |
784 size_t res; | 797 size_t res; |
785 res = tl->count(); | 798 res = tl->count(); |
786 #ifdef ASSERT | 799 #ifdef ASSERT |
787 size_t cnt; | 800 size_t cnt; |
790 assert(res == cnt, "The count is not being maintained correctly"); | 803 assert(res == cnt, "The count is not being maintained correctly"); |
791 #endif | 804 #endif |
792 return res; | 805 return res; |
793 } | 806 } |
794 | 807 |
795 template <class Chunk_t, class FreeList_t> | 808 template <class Chunk_t, template <class> class FreeList_t> |
796 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_size_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const { | 809 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_size_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const { |
797 if (tl == NULL) | 810 if (tl == NULL) |
798 return 0; | 811 return 0; |
799 return (tl->size() * total_list_length(tl)) + | 812 return (tl->size() * total_list_length(tl)) + |
800 total_size_in_tree(tl->left()) + | 813 total_size_in_tree(tl->left()) + |
801 total_size_in_tree(tl->right()); | 814 total_size_in_tree(tl->right()); |
802 } | 815 } |
803 | 816 |
804 template <class Chunk_t, class FreeList_t> | 817 template <class Chunk_t, template <class> class FreeList_t> |
805 double BinaryTreeDictionary<Chunk_t, FreeList_t>::sum_of_squared_block_sizes(TreeList<Chunk_t, FreeList_t>* const tl) const { | 818 double BinaryTreeDictionary<Chunk_t, FreeList_t>::sum_of_squared_block_sizes(TreeList<Chunk_t, FreeList_t>* const tl) const { |
806 if (tl == NULL) { | 819 if (tl == NULL) { |
807 return 0.0; | 820 return 0.0; |
808 } | 821 } |
809 double size = (double)(tl->size()); | 822 double size = (double)(tl->size()); |
811 curr += sum_of_squared_block_sizes(tl->left()); | 824 curr += sum_of_squared_block_sizes(tl->left()); |
812 curr += sum_of_squared_block_sizes(tl->right()); | 825 curr += sum_of_squared_block_sizes(tl->right()); |
813 return curr; | 826 return curr; |
814 } | 827 } |
815 | 828 |
816 template <class Chunk_t, class FreeList_t> | 829 template <class Chunk_t, template <class> class FreeList_t> |
817 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_free_blocks_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const { | 830 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_free_blocks_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const { |
818 if (tl == NULL) | 831 if (tl == NULL) |
819 return 0; | 832 return 0; |
820 return total_list_length(tl) + | 833 return total_list_length(tl) + |
821 total_free_blocks_in_tree(tl->left()) + | 834 total_free_blocks_in_tree(tl->left()) + |
822 total_free_blocks_in_tree(tl->right()); | 835 total_free_blocks_in_tree(tl->right()); |
823 } | 836 } |
824 | 837 |
825 template <class Chunk_t, class FreeList_t> | 838 template <class Chunk_t, template <class> class FreeList_t> |
826 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::num_free_blocks() const { | 839 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::num_free_blocks() const { |
827 assert(total_free_blocks_in_tree(root()) == total_free_blocks(), | 840 assert(total_free_blocks_in_tree(root()) == total_free_blocks(), |
828 "_total_free_blocks inconsistency"); | 841 "_total_free_blocks inconsistency"); |
829 return total_free_blocks(); | 842 return total_free_blocks(); |
830 } | 843 } |
831 | 844 |
832 template <class Chunk_t, class FreeList_t> | 845 template <class Chunk_t, template <class> class FreeList_t> |
833 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::tree_height_helper(TreeList<Chunk_t, FreeList_t>* tl) const { | 846 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::tree_height_helper(TreeList<Chunk_t, FreeList_t>* tl) const { |
834 if (tl == NULL) | 847 if (tl == NULL) |
835 return 0; | 848 return 0; |
836 return 1 + MAX2(tree_height_helper(tl->left()), | 849 return 1 + MAX2(tree_height_helper(tl->left()), |
837 tree_height_helper(tl->right())); | 850 tree_height_helper(tl->right())); |
838 } | 851 } |
839 | 852 |
840 template <class Chunk_t, class FreeList_t> | 853 template <class Chunk_t, template <class> class FreeList_t> |
841 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::tree_height() const { | 854 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::tree_height() const { |
842 return tree_height_helper(root()); | 855 return tree_height_helper(root()); |
843 } | 856 } |
844 | 857 |
845 template <class Chunk_t, class FreeList_t> | 858 template <class Chunk_t, template <class> class FreeList_t> |
846 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_nodes_helper(TreeList<Chunk_t, FreeList_t>* tl) const { | 859 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_nodes_helper(TreeList<Chunk_t, FreeList_t>* tl) const { |
847 if (tl == NULL) { | 860 if (tl == NULL) { |
848 return 0; | 861 return 0; |
849 } | 862 } |
850 return 1 + total_nodes_helper(tl->left()) + | 863 return 1 + total_nodes_helper(tl->left()) + |
851 total_nodes_helper(tl->right()); | 864 total_nodes_helper(tl->right()); |
852 } | 865 } |
853 | 866 |
854 template <class Chunk_t, class FreeList_t> | 867 template <class Chunk_t, template <class> class FreeList_t> |
855 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_nodes_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const { | 868 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_nodes_in_tree(TreeList<Chunk_t, FreeList_t>* tl) const { |
856 return total_nodes_helper(root()); | 869 return total_nodes_helper(root()); |
857 } | 870 } |
858 | 871 |
859 template <class Chunk_t, class FreeList_t> | 872 template <class Chunk_t, template <class> class FreeList_t> |
860 void BinaryTreeDictionary<Chunk_t, FreeList_t>::dict_census_update(size_t size, bool split, bool birth){} | 873 void BinaryTreeDictionary<Chunk_t, FreeList_t>::dict_census_update(size_t size, bool split, bool birth){} |
861 | 874 |
862 #if INCLUDE_ALL_GCS | 875 #if INCLUDE_ALL_GCS |
863 template <> | 876 template <> |
864 void AFLBinaryTreeDictionary::dict_census_update(size_t size, bool split, bool birth) { | 877 void AFLBinaryTreeDictionary::dict_census_update(size_t size, bool split, bool birth){ |
865 TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >* nd = find_list(size); | 878 TreeList<FreeChunk, AdaptiveFreeList>* nd = find_list(size); |
866 if (nd) { | 879 if (nd) { |
867 if (split) { | 880 if (split) { |
868 if (birth) { | 881 if (birth) { |
869 nd->increment_split_births(); | 882 nd->increment_split_births(); |
870 nd->increment_surplus(); | 883 nd->increment_surplus(); |
888 // This is a birth associated with a LinAB. The chunk | 901 // This is a birth associated with a LinAB. The chunk |
889 // for the LinAB is not in the dictionary. | 902 // for the LinAB is not in the dictionary. |
890 } | 903 } |
891 #endif // INCLUDE_ALL_GCS | 904 #endif // INCLUDE_ALL_GCS |
892 | 905 |
893 template <class Chunk_t, class FreeList_t> | 906 template <class Chunk_t, template <class> class FreeList_t> |
894 bool BinaryTreeDictionary<Chunk_t, FreeList_t>::coal_dict_over_populated(size_t size) { | 907 bool BinaryTreeDictionary<Chunk_t, FreeList_t>::coal_dict_over_populated(size_t size) { |
895 // For the general type of freelists, encourage coalescing by | 908 // For the general type of freelists, encourage coalescing by |
896 // returning true. | 909 // returning true. |
897 return true; | 910 return true; |
898 } | 911 } |
900 #if INCLUDE_ALL_GCS | 913 #if INCLUDE_ALL_GCS |
901 template <> | 914 template <> |
902 bool AFLBinaryTreeDictionary::coal_dict_over_populated(size_t size) { | 915 bool AFLBinaryTreeDictionary::coal_dict_over_populated(size_t size) { |
903 if (FLSAlwaysCoalesceLarge) return true; | 916 if (FLSAlwaysCoalesceLarge) return true; |
904 | 917 |
905 TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >* list_of_size = find_list(size); | 918 TreeList<FreeChunk, AdaptiveFreeList>* list_of_size = find_list(size); |
906 // None of requested size implies overpopulated. | 919 // None of requested size implies overpopulated. |
907 return list_of_size == NULL || list_of_size->coal_desired() <= 0 || | 920 return list_of_size == NULL || list_of_size->coal_desired() <= 0 || |
908 list_of_size->count() > list_of_size->coal_desired(); | 921 list_of_size->count() > list_of_size->coal_desired(); |
909 } | 922 } |
910 #endif // INCLUDE_ALL_GCS | 923 #endif // INCLUDE_ALL_GCS |
913 // do_list() walks the free list in a node applying the closure | 926 // do_list() walks the free list in a node applying the closure |
914 // to each free chunk in the list | 927 // to each free chunk in the list |
915 // do_tree() walks the nodes in the binary tree applying do_list() | 928 // do_tree() walks the nodes in the binary tree applying do_list() |
916 // to each list at each node. | 929 // to each list at each node. |
917 | 930 |
918 template <class Chunk_t, class FreeList_t> | 931 template <class Chunk_t, template <class> class FreeList_t> |
919 class TreeCensusClosure : public StackObj { | 932 class TreeCensusClosure : public StackObj { |
920 protected: | 933 protected: |
921 virtual void do_list(FreeList_t* fl) = 0; | 934 virtual void do_list(FreeList_t<Chunk_t>* fl) = 0; |
922 public: | 935 public: |
923 virtual void do_tree(TreeList<Chunk_t, FreeList_t>* tl) = 0; | 936 virtual void do_tree(TreeList<Chunk_t, FreeList_t>* tl) = 0; |
924 }; | 937 }; |
925 | 938 |
926 template <class Chunk_t, class FreeList_t> | 939 template <class Chunk_t, template <class> class FreeList_t> |
927 class AscendTreeCensusClosure : public TreeCensusClosure<Chunk_t, FreeList_t> { | 940 class AscendTreeCensusClosure : public TreeCensusClosure<Chunk_t, FreeList_t> { |
928 public: | 941 public: |
929 void do_tree(TreeList<Chunk_t, FreeList_t>* tl) { | 942 void do_tree(TreeList<Chunk_t, FreeList_t>* tl) { |
930 if (tl != NULL) { | 943 if (tl != NULL) { |
931 do_tree(tl->left()); | 944 do_tree(tl->left()); |
933 do_tree(tl->right()); | 946 do_tree(tl->right()); |
934 } | 947 } |
935 } | 948 } |
936 }; | 949 }; |
937 | 950 |
938 template <class Chunk_t, class FreeList_t> | 951 template <class Chunk_t, template <class> class FreeList_t> |
939 class DescendTreeCensusClosure : public TreeCensusClosure<Chunk_t, FreeList_t> { | 952 class DescendTreeCensusClosure : public TreeCensusClosure<Chunk_t, FreeList_t> { |
940 public: | 953 public: |
941 void do_tree(TreeList<Chunk_t, FreeList_t>* tl) { | 954 void do_tree(TreeList<Chunk_t, FreeList_t>* tl) { |
942 if (tl != NULL) { | 955 if (tl != NULL) { |
943 do_tree(tl->right()); | 956 do_tree(tl->right()); |
947 } | 960 } |
948 }; | 961 }; |
949 | 962 |
950 // For each list in the tree, calculate the desired, desired | 963 // For each list in the tree, calculate the desired, desired |
951 // coalesce, count before sweep, and surplus before sweep. | 964 // coalesce, count before sweep, and surplus before sweep. |
952 template <class Chunk_t, class FreeList_t> | 965 template <class Chunk_t, template <class> class FreeList_t> |
953 class BeginSweepClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { | 966 class BeginSweepClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { |
954 double _percentage; | 967 double _percentage; |
955 float _inter_sweep_current; | 968 float _inter_sweep_current; |
956 float _inter_sweep_estimate; | 969 float _inter_sweep_estimate; |
957 float _intra_sweep_estimate; | 970 float _intra_sweep_estimate; |
980 | 993 |
981 // Used to search the tree until a condition is met. | 994 // Used to search the tree until a condition is met. |
982 // Similar to TreeCensusClosure but searches the | 995 // Similar to TreeCensusClosure but searches the |
983 // tree and returns promptly when found. | 996 // tree and returns promptly when found. |
984 | 997 |
985 template <class Chunk_t, class FreeList_t> | 998 template <class Chunk_t, template <class> class FreeList_t> |
986 class TreeSearchClosure : public StackObj { | 999 class TreeSearchClosure : public StackObj { |
987 protected: | 1000 protected: |
988 virtual bool do_list(FreeList_t* fl) = 0; | 1001 virtual bool do_list(FreeList_t<Chunk_t>* fl) = 0; |
989 public: | 1002 public: |
990 virtual bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) = 0; | 1003 virtual bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) = 0; |
991 }; | 1004 }; |
992 | 1005 |
993 #if 0 // Don't need this yet but here for symmetry. | 1006 #if 0 // Don't need this yet but here for symmetry. |
994 template <class Chunk_t, class FreeList_t> | 1007 template <class Chunk_t, template <class> class FreeList_t> |
995 class AscendTreeSearchClosure : public TreeSearchClosure<Chunk_t> { | 1008 class AscendTreeSearchClosure : public TreeSearchClosure<Chunk_t> { |
996 public: | 1009 public: |
997 bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) { | 1010 bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) { |
998 if (tl != NULL) { | 1011 if (tl != NULL) { |
999 if (do_tree(tl->left())) return true; | 1012 if (do_tree(tl->left())) return true; |
1003 return false; | 1016 return false; |
1004 } | 1017 } |
1005 }; | 1018 }; |
1006 #endif | 1019 #endif |
1007 | 1020 |
1008 template <class Chunk_t, class FreeList_t> | 1021 template <class Chunk_t, template <class> class FreeList_t> |
1009 class DescendTreeSearchClosure : public TreeSearchClosure<Chunk_t, FreeList_t> { | 1022 class DescendTreeSearchClosure : public TreeSearchClosure<Chunk_t, FreeList_t> { |
1010 public: | 1023 public: |
1011 bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) { | 1024 bool do_tree(TreeList<Chunk_t, FreeList_t>* tl) { |
1012 if (tl != NULL) { | 1025 if (tl != NULL) { |
1013 if (do_tree(tl->right())) return true; | 1026 if (do_tree(tl->right())) return true; |
1018 } | 1031 } |
1019 }; | 1032 }; |
1020 | 1033 |
1021 // Searches the tree for a chunk that ends at the | 1034 // Searches the tree for a chunk that ends at the |
1022 // specified address. | 1035 // specified address. |
1023 template <class Chunk_t, class FreeList_t> | 1036 template <class Chunk_t, template <class> class FreeList_t> |
1024 class EndTreeSearchClosure : public DescendTreeSearchClosure<Chunk_t, FreeList_t> { | 1037 class EndTreeSearchClosure : public DescendTreeSearchClosure<Chunk_t, FreeList_t> { |
1025 HeapWord* _target; | 1038 HeapWord* _target; |
1026 Chunk_t* _found; | 1039 Chunk_t* _found; |
1027 | 1040 |
1028 public: | 1041 public: |
1029 EndTreeSearchClosure(HeapWord* target) : _target(target), _found(NULL) {} | 1042 EndTreeSearchClosure(HeapWord* target) : _target(target), _found(NULL) {} |
1030 bool do_list(FreeList_t* fl) { | 1043 bool do_list(FreeList_t<Chunk_t>* fl) { |
1031 Chunk_t* item = fl->head(); | 1044 Chunk_t* item = fl->head(); |
1032 while (item != NULL) { | 1045 while (item != NULL) { |
1033 if (item->end() == (uintptr_t*) _target) { | 1046 if (item->end() == (uintptr_t*) _target) { |
1034 _found = item; | 1047 _found = item; |
1035 return true; | 1048 return true; |
1039 return false; | 1052 return false; |
1040 } | 1053 } |
1041 Chunk_t* found() { return _found; } | 1054 Chunk_t* found() { return _found; } |
1042 }; | 1055 }; |
1043 | 1056 |
1044 template <class Chunk_t, class FreeList_t> | 1057 template <class Chunk_t, template <class> class FreeList_t> |
1045 Chunk_t* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_chunk_ends_at(HeapWord* target) const { | 1058 Chunk_t* BinaryTreeDictionary<Chunk_t, FreeList_t>::find_chunk_ends_at(HeapWord* target) const { |
1046 EndTreeSearchClosure<Chunk_t, FreeList_t> etsc(target); | 1059 EndTreeSearchClosure<Chunk_t, FreeList_t> etsc(target); |
1047 bool found_target = etsc.do_tree(root()); | 1060 bool found_target = etsc.do_tree(root()); |
1048 assert(found_target || etsc.found() == NULL, "Consistency check"); | 1061 assert(found_target || etsc.found() == NULL, "Consistency check"); |
1049 assert(!found_target || etsc.found() != NULL, "Consistency check"); | 1062 assert(!found_target || etsc.found() != NULL, "Consistency check"); |
1050 return etsc.found(); | 1063 return etsc.found(); |
1051 } | 1064 } |
1052 | 1065 |
1053 template <class Chunk_t, class FreeList_t> | 1066 template <class Chunk_t, template <class> class FreeList_t> |
1054 void BinaryTreeDictionary<Chunk_t, FreeList_t>::begin_sweep_dict_census(double coalSurplusPercent, | 1067 void BinaryTreeDictionary<Chunk_t, FreeList_t>::begin_sweep_dict_census(double coalSurplusPercent, |
1055 float inter_sweep_current, float inter_sweep_estimate, float intra_sweep_estimate) { | 1068 float inter_sweep_current, float inter_sweep_estimate, float intra_sweep_estimate) { |
1056 BeginSweepClosure<Chunk_t, FreeList_t> bsc(coalSurplusPercent, inter_sweep_current, | 1069 BeginSweepClosure<Chunk_t, FreeList_t> bsc(coalSurplusPercent, inter_sweep_current, |
1057 inter_sweep_estimate, | 1070 inter_sweep_estimate, |
1058 intra_sweep_estimate); | 1071 intra_sweep_estimate); |
1060 } | 1073 } |
1061 | 1074 |
1062 // Closures and methods for calculating total bytes returned to the | 1075 // Closures and methods for calculating total bytes returned to the |
1063 // free lists in the tree. | 1076 // free lists in the tree. |
1064 #ifndef PRODUCT | 1077 #ifndef PRODUCT |
1065 template <class Chunk_t, class FreeList_t> | 1078 template <class Chunk_t, template <class> class FreeList_t> |
1066 class InitializeDictReturnedBytesClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { | 1079 class InitializeDictReturnedBytesClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { |
1067 public: | 1080 public: |
1068 void do_list(FreeList_t* fl) { | 1081 void do_list(FreeList_t<Chunk_t>* fl) { |
1069 fl->set_returned_bytes(0); | 1082 fl->set_returned_bytes(0); |
1070 } | 1083 } |
1071 }; | 1084 }; |
1072 | 1085 |
1073 template <class Chunk_t, class FreeList_t> | 1086 template <class Chunk_t, template <class> class FreeList_t> |
1074 void BinaryTreeDictionary<Chunk_t, FreeList_t>::initialize_dict_returned_bytes() { | 1087 void BinaryTreeDictionary<Chunk_t, FreeList_t>::initialize_dict_returned_bytes() { |
1075 InitializeDictReturnedBytesClosure<Chunk_t, FreeList_t> idrb; | 1088 InitializeDictReturnedBytesClosure<Chunk_t, FreeList_t> idrb; |
1076 idrb.do_tree(root()); | 1089 idrb.do_tree(root()); |
1077 } | 1090 } |
1078 | 1091 |
1079 template <class Chunk_t, class FreeList_t> | 1092 template <class Chunk_t, template <class> class FreeList_t> |
1080 class ReturnedBytesClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { | 1093 class ReturnedBytesClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { |
1081 size_t _dict_returned_bytes; | 1094 size_t _dict_returned_bytes; |
1082 public: | 1095 public: |
1083 ReturnedBytesClosure() { _dict_returned_bytes = 0; } | 1096 ReturnedBytesClosure() { _dict_returned_bytes = 0; } |
1084 void do_list(FreeList_t* fl) { | 1097 void do_list(FreeList_t<Chunk_t>* fl) { |
1085 _dict_returned_bytes += fl->returned_bytes(); | 1098 _dict_returned_bytes += fl->returned_bytes(); |
1086 } | 1099 } |
1087 size_t dict_returned_bytes() { return _dict_returned_bytes; } | 1100 size_t dict_returned_bytes() { return _dict_returned_bytes; } |
1088 }; | 1101 }; |
1089 | 1102 |
1090 template <class Chunk_t, class FreeList_t> | 1103 template <class Chunk_t, template <class> class FreeList_t> |
1091 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::sum_dict_returned_bytes() { | 1104 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::sum_dict_returned_bytes() { |
1092 ReturnedBytesClosure<Chunk_t, FreeList_t> rbc; | 1105 ReturnedBytesClosure<Chunk_t, FreeList_t> rbc; |
1093 rbc.do_tree(root()); | 1106 rbc.do_tree(root()); |
1094 | 1107 |
1095 return rbc.dict_returned_bytes(); | 1108 return rbc.dict_returned_bytes(); |
1096 } | 1109 } |
1097 | 1110 |
1098 // Count the number of entries in the tree. | 1111 // Count the number of entries in the tree. |
1099 template <class Chunk_t, class FreeList_t> | 1112 template <class Chunk_t, template <class> class FreeList_t> |
1100 class treeCountClosure : public DescendTreeCensusClosure<Chunk_t, FreeList_t> { | 1113 class treeCountClosure : public DescendTreeCensusClosure<Chunk_t, FreeList_t> { |
1101 public: | 1114 public: |
1102 uint count; | 1115 uint count; |
1103 treeCountClosure(uint c) { count = c; } | 1116 treeCountClosure(uint c) { count = c; } |
1104 void do_list(FreeList_t* fl) { | 1117 void do_list(FreeList_t<Chunk_t>* fl) { |
1105 count++; | 1118 count++; |
1106 } | 1119 } |
1107 }; | 1120 }; |
1108 | 1121 |
1109 template <class Chunk_t, class FreeList_t> | 1122 template <class Chunk_t, template <class> class FreeList_t> |
1110 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_count() { | 1123 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_count() { |
1111 treeCountClosure<Chunk_t, FreeList_t> ctc(0); | 1124 treeCountClosure<Chunk_t, FreeList_t> ctc(0); |
1112 ctc.do_tree(root()); | 1125 ctc.do_tree(root()); |
1113 return ctc.count; | 1126 return ctc.count; |
1114 } | 1127 } |
1115 #endif // PRODUCT | 1128 #endif // PRODUCT |
1116 | 1129 |
1117 // Calculate surpluses for the lists in the tree. | 1130 // Calculate surpluses for the lists in the tree. |
1118 template <class Chunk_t, class FreeList_t> | 1131 template <class Chunk_t, template <class> class FreeList_t> |
1119 class setTreeSurplusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { | 1132 class setTreeSurplusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { |
1120 double percentage; | 1133 double percentage; |
1121 public: | 1134 public: |
1122 setTreeSurplusClosure(double v) { percentage = v; } | 1135 setTreeSurplusClosure(double v) { percentage = v; } |
1123 void do_list(FreeList<Chunk_t>* fl) {} | 1136 void do_list(FreeList<Chunk_t>* fl) {} |
1129 (ssize_t)((double)fl->desired() * splitSurplusPercent)); | 1142 (ssize_t)((double)fl->desired() * splitSurplusPercent)); |
1130 } | 1143 } |
1131 #endif // INCLUDE_ALL_GCS | 1144 #endif // INCLUDE_ALL_GCS |
1132 }; | 1145 }; |
1133 | 1146 |
1134 template <class Chunk_t, class FreeList_t> | 1147 template <class Chunk_t, template <class> class FreeList_t> |
1135 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_surplus(double splitSurplusPercent) { | 1148 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_surplus(double splitSurplusPercent) { |
1136 setTreeSurplusClosure<Chunk_t, FreeList_t> sts(splitSurplusPercent); | 1149 setTreeSurplusClosure<Chunk_t, FreeList_t> sts(splitSurplusPercent); |
1137 sts.do_tree(root()); | 1150 sts.do_tree(root()); |
1138 } | 1151 } |
1139 | 1152 |
1140 // Set hints for the lists in the tree. | 1153 // Set hints for the lists in the tree. |
1141 template <class Chunk_t, class FreeList_t> | 1154 template <class Chunk_t, template <class> class FreeList_t> |
1142 class setTreeHintsClosure : public DescendTreeCensusClosure<Chunk_t, FreeList_t> { | 1155 class setTreeHintsClosure : public DescendTreeCensusClosure<Chunk_t, FreeList_t> { |
1143 size_t hint; | 1156 size_t hint; |
1144 public: | 1157 public: |
1145 setTreeHintsClosure(size_t v) { hint = v; } | 1158 setTreeHintsClosure(size_t v) { hint = v; } |
1146 void do_list(FreeList<Chunk_t>* fl) {} | 1159 void do_list(FreeList<Chunk_t>* fl) {} |
1155 } | 1168 } |
1156 } | 1169 } |
1157 #endif // INCLUDE_ALL_GCS | 1170 #endif // INCLUDE_ALL_GCS |
1158 }; | 1171 }; |
1159 | 1172 |
1160 template <class Chunk_t, class FreeList_t> | 1173 template <class Chunk_t, template <class> class FreeList_t> |
1161 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_hints(void) { | 1174 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_hints(void) { |
1162 setTreeHintsClosure<Chunk_t, FreeList_t> sth(0); | 1175 setTreeHintsClosure<Chunk_t, FreeList_t> sth(0); |
1163 sth.do_tree(root()); | 1176 sth.do_tree(root()); |
1164 } | 1177 } |
1165 | 1178 |
1166 // Save count before previous sweep and splits and coalesces. | 1179 // Save count before previous sweep and splits and coalesces. |
1167 template <class Chunk_t, class FreeList_t> | 1180 template <class Chunk_t, template <class> class FreeList_t> |
1168 class clearTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { | 1181 class clearTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { |
1169 void do_list(FreeList<Chunk_t>* fl) {} | 1182 void do_list(FreeList<Chunk_t>* fl) {} |
1170 | 1183 |
1171 #if INCLUDE_ALL_GCS | 1184 #if INCLUDE_ALL_GCS |
1172 void do_list(AdaptiveFreeList<Chunk_t>* fl) { | 1185 void do_list(AdaptiveFreeList<Chunk_t>* fl) { |
1177 fl->set_split_deaths(0); | 1190 fl->set_split_deaths(0); |
1178 } | 1191 } |
1179 #endif // INCLUDE_ALL_GCS | 1192 #endif // INCLUDE_ALL_GCS |
1180 }; | 1193 }; |
1181 | 1194 |
1182 template <class Chunk_t, class FreeList_t> | 1195 template <class Chunk_t, template <class> class FreeList_t> |
1183 void BinaryTreeDictionary<Chunk_t, FreeList_t>::clear_tree_census(void) { | 1196 void BinaryTreeDictionary<Chunk_t, FreeList_t>::clear_tree_census(void) { |
1184 clearTreeCensusClosure<Chunk_t, FreeList_t> ctc; | 1197 clearTreeCensusClosure<Chunk_t, FreeList_t> ctc; |
1185 ctc.do_tree(root()); | 1198 ctc.do_tree(root()); |
1186 } | 1199 } |
1187 | 1200 |
1188 // Do reporting and post sweep clean up. | 1201 // Do reporting and post sweep clean up. |
1189 template <class Chunk_t, class FreeList_t> | 1202 template <class Chunk_t, template <class> class FreeList_t> |
1190 void BinaryTreeDictionary<Chunk_t, FreeList_t>::end_sweep_dict_census(double splitSurplusPercent) { | 1203 void BinaryTreeDictionary<Chunk_t, FreeList_t>::end_sweep_dict_census(double splitSurplusPercent) { |
1191 // Does walking the tree 3 times hurt? | 1204 // Does walking the tree 3 times hurt? |
1192 set_tree_surplus(splitSurplusPercent); | 1205 set_tree_surplus(splitSurplusPercent); |
1193 set_tree_hints(); | 1206 set_tree_hints(); |
1194 if (PrintGC && Verbose) { | 1207 if (PrintGC && Verbose) { |
1196 } | 1209 } |
1197 clear_tree_census(); | 1210 clear_tree_census(); |
1198 } | 1211 } |
1199 | 1212 |
1200 // Print summary statistics | 1213 // Print summary statistics |
1201 template <class Chunk_t, class FreeList_t> | 1214 template <class Chunk_t, template <class> class FreeList_t> |
1202 void BinaryTreeDictionary<Chunk_t, FreeList_t>::report_statistics() const { | 1215 void BinaryTreeDictionary<Chunk_t, FreeList_t>::report_statistics() const { |
1203 FreeBlockDictionary<Chunk_t>::verify_par_locked(); | 1216 FreeBlockDictionary<Chunk_t>::verify_par_locked(); |
1204 gclog_or_tty->print("Statistics for BinaryTreeDictionary:\n" | 1217 gclog_or_tty->print("Statistics for BinaryTreeDictionary:\n" |
1205 "------------------------------------\n"); | 1218 "------------------------------------\n"); |
1206 size_t total_size = total_chunk_size(debug_only(NULL)); | 1219 size_t total_size = total_chunk_size(debug_only(NULL)); |
1215 } | 1228 } |
1216 | 1229 |
1217 // Print census information - counts, births, deaths, etc. | 1230 // Print census information - counts, births, deaths, etc. |
1218 // for each list in the tree. Also print some summary | 1231 // for each list in the tree. Also print some summary |
1219 // information. | 1232 // information. |
1220 template <class Chunk_t, class FreeList_t> | 1233 template <class Chunk_t, template <class> class FreeList_t> |
1221 class PrintTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { | 1234 class PrintTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { |
1222 int _print_line; | 1235 int _print_line; |
1223 size_t _total_free; | 1236 size_t _total_free; |
1224 FreeList_t _total; | 1237 FreeList_t<Chunk_t> _total; |
1225 | 1238 |
1226 public: | 1239 public: |
1227 PrintTreeCensusClosure() { | 1240 PrintTreeCensusClosure() { |
1228 _print_line = 0; | 1241 _print_line = 0; |
1229 _total_free = 0; | 1242 _total_free = 0; |
1230 } | 1243 } |
1231 FreeList_t* total() { return &_total; } | 1244 FreeList_t<Chunk_t>* total() { return &_total; } |
1232 size_t total_free() { return _total_free; } | 1245 size_t total_free() { return _total_free; } |
1233 void do_list(FreeList<Chunk_t>* fl) { | 1246 void do_list(FreeList<Chunk_t>* fl) { |
1234 if (++_print_line >= 40) { | 1247 if (++_print_line >= 40) { |
1235 FreeList_t::print_labels_on(gclog_or_tty, "size"); | 1248 FreeList_t<Chunk_t>::print_labels_on(gclog_or_tty, "size"); |
1236 _print_line = 0; | 1249 _print_line = 0; |
1237 } | 1250 } |
1238 fl->print_on(gclog_or_tty); | 1251 fl->print_on(gclog_or_tty); |
1239 _total_free += fl->count() * fl->size() ; | 1252 _total_free += fl->count() * fl->size() ; |
1240 total()->set_count( total()->count() + fl->count() ); | 1253 total()->set_count( total()->count() + fl->count() ); |
1241 } | 1254 } |
1242 | 1255 |
1243 #if INCLUDE_ALL_GCS | 1256 #if INCLUDE_ALL_GCS |
1244 void do_list(AdaptiveFreeList<Chunk_t>* fl) { | 1257 void do_list(AdaptiveFreeList<Chunk_t>* fl) { |
1245 if (++_print_line >= 40) { | 1258 if (++_print_line >= 40) { |
1246 FreeList_t::print_labels_on(gclog_or_tty, "size"); | 1259 FreeList_t<Chunk_t>::print_labels_on(gclog_or_tty, "size"); |
1247 _print_line = 0; | 1260 _print_line = 0; |
1248 } | 1261 } |
1249 fl->print_on(gclog_or_tty); | 1262 fl->print_on(gclog_or_tty); |
1250 _total_free += fl->count() * fl->size() ; | 1263 _total_free += fl->count() * fl->size() ; |
1251 total()->set_count( total()->count() + fl->count() ); | 1264 total()->set_count( total()->count() + fl->count() ); |
1260 total()->set_split_deaths(total()->split_deaths() + fl->split_deaths()); | 1273 total()->set_split_deaths(total()->split_deaths() + fl->split_deaths()); |
1261 } | 1274 } |
1262 #endif // INCLUDE_ALL_GCS | 1275 #endif // INCLUDE_ALL_GCS |
1263 }; | 1276 }; |
1264 | 1277 |
1265 template <class Chunk_t, class FreeList_t> | 1278 template <class Chunk_t, template <class> class FreeList_t> |
1266 void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_dict_census(void) const { | 1279 void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_dict_census(void) const { |
1267 | 1280 |
1268 gclog_or_tty->print("\nBinaryTree\n"); | 1281 gclog_or_tty->print("\nBinaryTree\n"); |
1269 FreeList_t::print_labels_on(gclog_or_tty, "size"); | 1282 FreeList_t<Chunk_t>::print_labels_on(gclog_or_tty, "size"); |
1270 PrintTreeCensusClosure<Chunk_t, FreeList_t> ptc; | 1283 PrintTreeCensusClosure<Chunk_t, FreeList_t> ptc; |
1271 ptc.do_tree(root()); | 1284 ptc.do_tree(root()); |
1272 | 1285 |
1273 FreeList_t* total = ptc.total(); | 1286 FreeList_t<Chunk_t>* total = ptc.total(); |
1274 FreeList_t::print_labels_on(gclog_or_tty, " "); | 1287 FreeList_t<Chunk_t>::print_labels_on(gclog_or_tty, " "); |
1275 } | 1288 } |
1276 | 1289 |
1277 #if INCLUDE_ALL_GCS | 1290 #if INCLUDE_ALL_GCS |
1278 template <> | 1291 template <> |
1279 void AFLBinaryTreeDictionary::print_dict_census(void) const { | 1292 void AFLBinaryTreeDictionary::print_dict_census(void) const { |
1280 | 1293 |
1281 gclog_or_tty->print("\nBinaryTree\n"); | 1294 gclog_or_tty->print("\nBinaryTree\n"); |
1282 AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, "size"); | 1295 AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, "size"); |
1283 PrintTreeCensusClosure<FreeChunk, AdaptiveFreeList<FreeChunk> > ptc; | 1296 PrintTreeCensusClosure<FreeChunk, AdaptiveFreeList> ptc; |
1284 ptc.do_tree(root()); | 1297 ptc.do_tree(root()); |
1285 | 1298 |
1286 AdaptiveFreeList<FreeChunk>* total = ptc.total(); | 1299 AdaptiveFreeList<FreeChunk>* total = ptc.total(); |
1287 AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, " "); | 1300 AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, " "); |
1288 total->print_on(gclog_or_tty, "TOTAL\t"); | 1301 total->print_on(gclog_or_tty, "TOTAL\t"); |
1296 (double)(total->desired() - total->count()) | 1309 (double)(total->desired() - total->count()) |
1297 /(total->desired() != 0 ? (double)total->desired() : 1.0)); | 1310 /(total->desired() != 0 ? (double)total->desired() : 1.0)); |
1298 } | 1311 } |
1299 #endif // INCLUDE_ALL_GCS | 1312 #endif // INCLUDE_ALL_GCS |
1300 | 1313 |
1301 template <class Chunk_t, class FreeList_t> | 1314 template <class Chunk_t, template <class> class FreeList_t> |
1302 class PrintFreeListsClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { | 1315 class PrintFreeListsClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { |
1303 outputStream* _st; | 1316 outputStream* _st; |
1304 int _print_line; | 1317 int _print_line; |
1305 | 1318 |
1306 public: | 1319 public: |
1307 PrintFreeListsClosure(outputStream* st) { | 1320 PrintFreeListsClosure(outputStream* st) { |
1308 _st = st; | 1321 _st = st; |
1309 _print_line = 0; | 1322 _print_line = 0; |
1310 } | 1323 } |
1311 void do_list(FreeList_t* fl) { | 1324 void do_list(FreeList_t<Chunk_t>* fl) { |
1312 if (++_print_line >= 40) { | 1325 if (++_print_line >= 40) { |
1313 FreeList_t::print_labels_on(_st, "size"); | 1326 FreeList_t<Chunk_t>::print_labels_on(_st, "size"); |
1314 _print_line = 0; | 1327 _print_line = 0; |
1315 } | 1328 } |
1316 fl->print_on(gclog_or_tty); | 1329 fl->print_on(gclog_or_tty); |
1317 size_t sz = fl->size(); | 1330 size_t sz = fl->size(); |
1318 for (Chunk_t* fc = fl->head(); fc != NULL; | 1331 for (Chunk_t* fc = fl->head(); fc != NULL; |
1322 fc->cantCoalesce() ? "\t CC" : ""); | 1335 fc->cantCoalesce() ? "\t CC" : ""); |
1323 } | 1336 } |
1324 } | 1337 } |
1325 }; | 1338 }; |
1326 | 1339 |
1327 template <class Chunk_t, class FreeList_t> | 1340 template <class Chunk_t, template <class> class FreeList_t> |
1328 void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_free_lists(outputStream* st) const { | 1341 void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_free_lists(outputStream* st) const { |
1329 | 1342 |
1330 FreeList_t::print_labels_on(st, "size"); | 1343 FreeList_t<Chunk_t>::print_labels_on(st, "size"); |
1331 PrintFreeListsClosure<Chunk_t, FreeList_t> pflc(st); | 1344 PrintFreeListsClosure<Chunk_t, FreeList_t> pflc(st); |
1332 pflc.do_tree(root()); | 1345 pflc.do_tree(root()); |
1333 } | 1346 } |
1334 | 1347 |
1335 // Verify the following tree invariants: | 1348 // Verify the following tree invariants: |
1336 // . _root has no parent | 1349 // . _root has no parent |
1337 // . parent and child point to each other | 1350 // . parent and child point to each other |
1338 // . each node's key correctly related to that of its child(ren) | 1351 // . each node's key correctly related to that of its child(ren) |
1339 template <class Chunk_t, class FreeList_t> | 1352 template <class Chunk_t, template <class> class FreeList_t> |
1340 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_tree() const { | 1353 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_tree() const { |
1341 guarantee(root() == NULL || total_free_blocks() == 0 || | 1354 guarantee(root() == NULL || total_free_blocks() == 0 || |
1342 total_size() != 0, "_total_size shouldn't be 0?"); | 1355 total_size() != 0, "_total_size should't be 0?"); |
1343 guarantee(root() == NULL || root()->parent() == NULL, "_root shouldn't have parent"); | 1356 guarantee(root() == NULL || root()->parent() == NULL, "_root shouldn't have parent"); |
1344 verify_tree_helper(root()); | 1357 verify_tree_helper(root()); |
1345 } | 1358 } |
1346 | 1359 |
1347 template <class Chunk_t, class FreeList_t> | 1360 template <class Chunk_t, template <class> class FreeList_t> |
1348 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_prev_free_ptrs(TreeList<Chunk_t, FreeList_t>* tl) { | 1361 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_prev_free_ptrs(TreeList<Chunk_t, FreeList_t>* tl) { |
1349 size_t ct = 0; | 1362 size_t ct = 0; |
1350 for (Chunk_t* curFC = tl->head(); curFC != NULL; curFC = curFC->next()) { | 1363 for (Chunk_t* curFC = tl->head(); curFC != NULL; curFC = curFC->next()) { |
1351 ct++; | 1364 ct++; |
1352 assert(curFC->prev() == NULL || curFC->prev()->is_free(), | 1365 assert(curFC->prev() == NULL || curFC->prev()->is_free(), |
1356 } | 1369 } |
1357 | 1370 |
1358 // Note: this helper is recursive rather than iterative, so use with | 1371 // Note: this helper is recursive rather than iterative, so use with |
1359 // caution on very deep trees; and watch out for stack overflow errors; | 1372 // caution on very deep trees; and watch out for stack overflow errors; |
1360 // In general, to be used only for debugging. | 1373 // In general, to be used only for debugging. |
1361 template <class Chunk_t, class FreeList_t> | 1374 template <class Chunk_t, template <class> class FreeList_t> |
1362 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_tree_helper(TreeList<Chunk_t, FreeList_t>* tl) const { | 1375 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_tree_helper(TreeList<Chunk_t, FreeList_t>* tl) const { |
1363 if (tl == NULL) | 1376 if (tl == NULL) |
1364 return; | 1377 return; |
1365 guarantee(tl->size() != 0, "A list must has a size"); | 1378 guarantee(tl->size() != 0, "A list must has a size"); |
1366 guarantee(tl->left() == NULL || tl->left()->parent() == tl, | 1379 guarantee(tl->left() == NULL || tl->left()->parent() == tl, |
1385 } | 1398 } |
1386 verify_tree_helper(tl->left()); | 1399 verify_tree_helper(tl->left()); |
1387 verify_tree_helper(tl->right()); | 1400 verify_tree_helper(tl->right()); |
1388 } | 1401 } |
1389 | 1402 |
1390 template <class Chunk_t, class FreeList_t> | 1403 template <class Chunk_t, template <class> class FreeList_t> |
1391 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify() const { | 1404 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify() const { |
1392 verify_tree(); | 1405 verify_tree(); |
1393 guarantee(total_size() == total_size_in_tree(root()), "Total Size inconsistency"); | 1406 guarantee(total_size() == total_size_in_tree(root()), "Total Size inconsistency"); |
1394 } | 1407 } |
1395 | 1408 |
1396 template class TreeList<Metablock, FreeList<Metablock> >; | 1409 template class TreeList<Metablock, FreeList>; |
1397 template class BinaryTreeDictionary<Metablock, FreeList<Metablock> >; | 1410 template class BinaryTreeDictionary<Metablock, FreeList>; |
1398 template class TreeChunk<Metablock, FreeList<Metablock> >; | 1411 template class TreeChunk<Metablock, FreeList>; |
1399 | 1412 |
1400 template class TreeList<Metachunk, FreeList<Metachunk> >; | 1413 template class TreeList<Metachunk, FreeList>; |
1401 template class BinaryTreeDictionary<Metachunk, FreeList<Metachunk> >; | 1414 template class BinaryTreeDictionary<Metachunk, FreeList>; |
1402 template class TreeChunk<Metachunk, FreeList<Metachunk> >; | 1415 template class TreeChunk<Metachunk, FreeList>; |
1403 | 1416 |
1404 | 1417 |
1405 #if INCLUDE_ALL_GCS | 1418 #if INCLUDE_ALL_GCS |
1406 // Explicitly instantiate these types for FreeChunk. | 1419 // Explicitly instantiate these types for FreeChunk. |
1407 template class TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >; | 1420 template class TreeList<FreeChunk, AdaptiveFreeList>; |
1408 template class BinaryTreeDictionary<FreeChunk, AdaptiveFreeList<FreeChunk> >; | 1421 template class BinaryTreeDictionary<FreeChunk, AdaptiveFreeList>; |
1409 template class TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >; | 1422 template class TreeChunk<FreeChunk, AdaptiveFreeList>; |
1410 | 1423 |
1411 #endif // INCLUDE_ALL_GCS | 1424 #endif // INCLUDE_ALL_GCS |