1 /*
2 * Copyright (c) 2001, 2015, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #include "precompiled.hpp"
26 #include "gc/cms/allocationStats.hpp"
27 #include "gc/shared/spaceDecorator.hpp"
28 #include "logging/logStream.inline.hpp"
29 #include "memory/binaryTreeDictionary.hpp"
30 #include "memory/freeBlockDictionary.hpp"
31 #include "memory/freeList.hpp"
32 #include "memory/metachunk.hpp"
33 #include "memory/resourceArea.hpp"
34 #include "runtime/globals.hpp"
35 #include "utilities/macros.hpp"
36 #include "utilities/ostream.hpp"
37 #if INCLUDE_ALL_GCS
38 #include "gc/cms/adaptiveFreeList.hpp"
39 #include "gc/cms/freeChunk.hpp"
40 #endif // INCLUDE_ALL_GCS
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
47 template <class Chunk_t, class FreeList_t>
48 size_t TreeChunk<Chunk_t, FreeList_t>::_min_tree_chunk_size = sizeof(TreeChunk<Chunk_t, FreeList_t>)/HeapWordSize;
49
50 template <class Chunk_t, class FreeList_t>
409 set_total_size(mr.word_size());
410 set_total_free_blocks(1);
411 }
412
413 template <class Chunk_t, class FreeList_t>
414 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset(HeapWord* addr, size_t byte_size) {
415 MemRegion mr(addr, heap_word_size(byte_size));
416 reset(mr);
417 }
418
419 template <class Chunk_t, class FreeList_t>
420 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset() {
421 set_root(NULL);
422 set_total_size(0);
423 set_total_free_blocks(0);
424 }
425
426 // Get a free block of size at least size from tree, or NULL.
427 template <class Chunk_t, class FreeList_t>
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)
432 {
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");
437 if (FLSVerifyDictionary) {
438 verify_tree();
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
455
456 if (dither == FreeBlockDictionary<Chunk_t>::exactly) return NULL;
457
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
469 curTL = curTL->get_better_list(this);
470
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");
476 remove_chunk_from_tree(retTC);
477 assert(retTC->is_free(), "Header is not marked correctly");
755 assert(prevTL->size() > size && prevTL->left() == NULL, "cpt pt inv");
756 prevTL->set_left(newTL);
757 }
758 }
759 }
760 assert(tc->list() != NULL, "Tree list should be set");
761
762 inc_total_size(size);
763 // Method 'total_size_in_tree' walks through the every block in the
764 // tree, so it can cause significant performance loss if there are
765 // many blocks in the tree
766 assert(!FLSVerifyDictionary || total_size_in_tree(root()) == total_size(), "_total_size inconsistency");
767 set_total_free_blocks(total_free_blocks() + 1);
768 if (FLSVerifyDictionary) {
769 verify_tree();
770 }
771 }
772
773 template <class Chunk_t, class FreeList_t>
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();
777 if (tc == NULL) return 0;
778 for (; tc->right() != NULL; tc = tc->right());
779 return tc->size();
780 }
781
782 template <class Chunk_t, class FreeList_t>
783 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_list_length(TreeList<Chunk_t, FreeList_t>* tl) const {
784 size_t res;
785 res = tl->count();
786 #ifdef ASSERT
787 size_t cnt;
788 Chunk_t* tc = tl->head();
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
795 template <class Chunk_t, class FreeList_t>
1095 return rbc.dict_returned_bytes();
1096 }
1097
1098 // Count the number of entries in the tree.
1099 template <class Chunk_t, class FreeList_t>
1100 class treeCountClosure : public DescendTreeCensusClosure<Chunk_t, FreeList_t> {
1101 public:
1102 uint count;
1103 treeCountClosure(uint c) { count = c; }
1104 void do_list(FreeList_t* fl) {
1105 count++;
1106 }
1107 };
1108
1109 template <class Chunk_t, class FreeList_t>
1110 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_count() {
1111 treeCountClosure<Chunk_t, FreeList_t> ctc(0);
1112 ctc.do_tree(root());
1113 return ctc.count;
1114 }
1115 #endif // PRODUCT
1116
1117 // Calculate surpluses for the lists in the tree.
1118 template <class Chunk_t, class FreeList_t>
1119 class setTreeSurplusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
1120 double percentage;
1121 public:
1122 setTreeSurplusClosure(double v) { percentage = v; }
1123 void do_list(FreeList<Chunk_t>* fl) {}
1124
1125 #if INCLUDE_ALL_GCS
1126 void do_list(AdaptiveFreeList<Chunk_t>* fl) {
1127 double splitSurplusPercent = percentage;
1128 fl->set_surplus(fl->count() -
1129 (ssize_t)((double)fl->desired() * splitSurplusPercent));
1130 }
1131 #endif // INCLUDE_ALL_GCS
1132 };
1133
1134 template <class Chunk_t, class FreeList_t>
1185 ctc.do_tree(root());
1186 }
1187
1188 // Do reporting and post sweep clean up.
1189 template <class Chunk_t, class FreeList_t>
1190 void BinaryTreeDictionary<Chunk_t, FreeList_t>::end_sweep_dict_census(double splitSurplusPercent) {
1191 // Does walking the tree 3 times hurt?
1192 set_tree_surplus(splitSurplusPercent);
1193 set_tree_hints();
1194 LogTarget(Trace, gc, freelist, stats) log;
1195 if (log.is_enabled()) {
1196 LogStream out(log);
1197 report_statistics(&out);
1198 }
1199 clear_tree_census();
1200 }
1201
1202 // Print summary statistics
1203 template <class Chunk_t, class FreeList_t>
1204 void BinaryTreeDictionary<Chunk_t, FreeList_t>::report_statistics(outputStream* st) const {
1205 FreeBlockDictionary<Chunk_t>::verify_par_locked();
1206 st->print_cr("Statistics for BinaryTreeDictionary:");
1207 st->print_cr("------------------------------------");
1208 size_t total_size = total_chunk_size(debug_only(NULL));
1209 size_t free_blocks = num_free_blocks();
1210 st->print_cr("Total Free Space: " SIZE_FORMAT, total_size);
1211 st->print_cr("Max Chunk Size: " SIZE_FORMAT, max_chunk_size());
1212 st->print_cr("Number of Blocks: " SIZE_FORMAT, free_blocks);
1213 if (free_blocks > 0) {
1214 st->print_cr("Av. Block Size: " SIZE_FORMAT, total_size/free_blocks);
1215 }
1216 st->print_cr("Tree Height: " SIZE_FORMAT, tree_height());
1217 }
1218
1219 // Print census information - counts, births, deaths, etc.
1220 // for each list in the tree. Also print some summary
1221 // information.
1222 template <class Chunk_t, class FreeList_t>
1223 class PrintTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
1224 int _print_line;
1225 size_t _total_free;
|
1 /*
2 * Copyright (c) 2001, 2017, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #include "precompiled.hpp"
26 #include "gc/cms/allocationStats.hpp"
27 #include "gc/shared/spaceDecorator.hpp"
28 #include "logging/logStream.inline.hpp"
29 #include "memory/binaryTreeDictionary.hpp"
30 #include "memory/freeList.hpp"
31 #include "memory/metachunk.hpp"
32 #include "memory/resourceArea.hpp"
33 #include "runtime/globals.hpp"
34 #include "utilities/macros.hpp"
35 #include "utilities/ostream.hpp"
36 #if INCLUDE_ALL_GCS
37 #include "gc/cms/adaptiveFreeList.hpp"
38 #include "gc/cms/freeChunk.hpp"
39 #endif // INCLUDE_ALL_GCS
40
41 ////////////////////////////////////////////////////////////////////////////////
42 // A binary tree based search structure for free blocks.
43 // This is currently used in the Concurrent Mark&Sweep implementation.
44 ////////////////////////////////////////////////////////////////////////////////
45
46 template <class Chunk_t, class FreeList_t>
47 size_t TreeChunk<Chunk_t, FreeList_t>::_min_tree_chunk_size = sizeof(TreeChunk<Chunk_t, FreeList_t>)/HeapWordSize;
48
49 template <class Chunk_t, class FreeList_t>
408 set_total_size(mr.word_size());
409 set_total_free_blocks(1);
410 }
411
412 template <class Chunk_t, class FreeList_t>
413 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset(HeapWord* addr, size_t byte_size) {
414 MemRegion mr(addr, heap_word_size(byte_size));
415 reset(mr);
416 }
417
418 template <class Chunk_t, class FreeList_t>
419 void BinaryTreeDictionary<Chunk_t, FreeList_t>::reset() {
420 set_root(NULL);
421 set_total_size(0);
422 set_total_free_blocks(0);
423 }
424
425 // Get a free block of size at least size from tree, or NULL.
426 template <class Chunk_t, class FreeList_t>
427 TreeChunk<Chunk_t, FreeList_t>*
428 BinaryTreeDictionary<Chunk_t, FreeList_t>::get_chunk_from_tree(size_t size)
429 {
430 TreeList<Chunk_t, FreeList_t> *curTL, *prevTL;
431 TreeChunk<Chunk_t, FreeList_t>* retTC = NULL;
432
433 assert((size >= min_size()), "minimum chunk size");
434 if (FLSVerifyDictionary) {
435 verify_tree();
436 }
437 // starting at the root, work downwards trying to find match.
438 // Remember the last node of size too great or too small.
439 for (prevTL = curTL = root(); curTL != NULL;) {
440 if (curTL->size() == size) { // exact match
441 break;
442 }
443 prevTL = curTL;
444 if (curTL->size() < size) { // proceed to right sub-tree
445 curTL = curTL->right();
446 } else { // proceed to left sub-tree
447 assert(curTL->size() > size, "size inconsistency");
448 curTL = curTL->left();
449 }
450 }
451 if (curTL == NULL) { // couldn't find exact match
452
453 // try and find the next larger size by walking back up the search path
454 for (curTL = prevTL; curTL != NULL;) {
455 if (curTL->size() >= size) break;
456 else curTL = curTL->parent();
457 }
458 assert(curTL == NULL || curTL->count() > 0,
459 "An empty list should not be in the tree");
460 }
461 if (curTL != NULL) {
462 assert(curTL->size() >= size, "size inconsistency");
463
464 curTL = curTL->get_better_list(this);
465
466 retTC = curTL->first_available();
467 assert((retTC != NULL) && (curTL->count() > 0),
468 "A list in the binary tree should not be NULL");
469 assert(retTC->size() >= size,
470 "A chunk of the wrong size was found");
471 remove_chunk_from_tree(retTC);
472 assert(retTC->is_free(), "Header is not marked correctly");
750 assert(prevTL->size() > size && prevTL->left() == NULL, "cpt pt inv");
751 prevTL->set_left(newTL);
752 }
753 }
754 }
755 assert(tc->list() != NULL, "Tree list should be set");
756
757 inc_total_size(size);
758 // Method 'total_size_in_tree' walks through the every block in the
759 // tree, so it can cause significant performance loss if there are
760 // many blocks in the tree
761 assert(!FLSVerifyDictionary || total_size_in_tree(root()) == total_size(), "_total_size inconsistency");
762 set_total_free_blocks(total_free_blocks() + 1);
763 if (FLSVerifyDictionary) {
764 verify_tree();
765 }
766 }
767
768 template <class Chunk_t, class FreeList_t>
769 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::max_chunk_size() const {
770 verify_par_locked();
771 TreeList<Chunk_t, FreeList_t>* tc = root();
772 if (tc == NULL) return 0;
773 for (; tc->right() != NULL; tc = tc->right());
774 return tc->size();
775 }
776
777 template <class Chunk_t, class FreeList_t>
778 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_list_length(TreeList<Chunk_t, FreeList_t>* tl) const {
779 size_t res;
780 res = tl->count();
781 #ifdef ASSERT
782 size_t cnt;
783 Chunk_t* tc = tl->head();
784 for (cnt = 0; tc != NULL; tc = tc->next(), cnt++);
785 assert(res == cnt, "The count is not being maintained correctly");
786 #endif
787 return res;
788 }
789
790 template <class Chunk_t, class FreeList_t>
1090 return rbc.dict_returned_bytes();
1091 }
1092
1093 // Count the number of entries in the tree.
1094 template <class Chunk_t, class FreeList_t>
1095 class treeCountClosure : public DescendTreeCensusClosure<Chunk_t, FreeList_t> {
1096 public:
1097 uint count;
1098 treeCountClosure(uint c) { count = c; }
1099 void do_list(FreeList_t* fl) {
1100 count++;
1101 }
1102 };
1103
1104 template <class Chunk_t, class FreeList_t>
1105 size_t BinaryTreeDictionary<Chunk_t, FreeList_t>::total_count() {
1106 treeCountClosure<Chunk_t, FreeList_t> ctc(0);
1107 ctc.do_tree(root());
1108 return ctc.count;
1109 }
1110
1111 template <class Chunk_t, class FreeList_t>
1112 Mutex* BinaryTreeDictionary<Chunk_t, FreeList_t>::par_lock() const {
1113 return _lock;
1114 }
1115
1116 template <class Chunk_t, class FreeList_t>
1117 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_par_lock(Mutex* lock) {
1118 _lock = lock;
1119 }
1120
1121 template <class Chunk_t, class FreeList_t>
1122 void BinaryTreeDictionary<Chunk_t, FreeList_t>::verify_par_locked() const {
1123 #ifdef ASSERT
1124 Thread* my_thread = Thread::current();
1125 if (my_thread->is_GC_task_thread()) {
1126 assert(par_lock() != NULL, "Should be using locking?");
1127 assert_lock_strong(par_lock());
1128 }
1129 #endif // ASSERT
1130 }
1131 #endif // PRODUCT
1132
1133 // Calculate surpluses for the lists in the tree.
1134 template <class Chunk_t, class FreeList_t>
1135 class setTreeSurplusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
1136 double percentage;
1137 public:
1138 setTreeSurplusClosure(double v) { percentage = v; }
1139 void do_list(FreeList<Chunk_t>* fl) {}
1140
1141 #if INCLUDE_ALL_GCS
1142 void do_list(AdaptiveFreeList<Chunk_t>* fl) {
1143 double splitSurplusPercent = percentage;
1144 fl->set_surplus(fl->count() -
1145 (ssize_t)((double)fl->desired() * splitSurplusPercent));
1146 }
1147 #endif // INCLUDE_ALL_GCS
1148 };
1149
1150 template <class Chunk_t, class FreeList_t>
1201 ctc.do_tree(root());
1202 }
1203
1204 // Do reporting and post sweep clean up.
1205 template <class Chunk_t, class FreeList_t>
1206 void BinaryTreeDictionary<Chunk_t, FreeList_t>::end_sweep_dict_census(double splitSurplusPercent) {
1207 // Does walking the tree 3 times hurt?
1208 set_tree_surplus(splitSurplusPercent);
1209 set_tree_hints();
1210 LogTarget(Trace, gc, freelist, stats) log;
1211 if (log.is_enabled()) {
1212 LogStream out(log);
1213 report_statistics(&out);
1214 }
1215 clear_tree_census();
1216 }
1217
1218 // Print summary statistics
1219 template <class Chunk_t, class FreeList_t>
1220 void BinaryTreeDictionary<Chunk_t, FreeList_t>::report_statistics(outputStream* st) const {
1221 verify_par_locked();
1222 st->print_cr("Statistics for BinaryTreeDictionary:");
1223 st->print_cr("------------------------------------");
1224 size_t total_size = total_chunk_size(debug_only(NULL));
1225 size_t free_blocks = num_free_blocks();
1226 st->print_cr("Total Free Space: " SIZE_FORMAT, total_size);
1227 st->print_cr("Max Chunk Size: " SIZE_FORMAT, max_chunk_size());
1228 st->print_cr("Number of Blocks: " SIZE_FORMAT, free_blocks);
1229 if (free_blocks > 0) {
1230 st->print_cr("Av. Block Size: " SIZE_FORMAT, total_size/free_blocks);
1231 }
1232 st->print_cr("Tree Height: " SIZE_FORMAT, tree_height());
1233 }
1234
1235 // Print census information - counts, births, deaths, etc.
1236 // for each list in the tree. Also print some summary
1237 // information.
1238 template <class Chunk_t, class FreeList_t>
1239 class PrintTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
1240 int _print_line;
1241 size_t _total_free;
|