1 #ifdef USE_PRAGMA_IDENT_SRC
2 #pragma ident "@(#)binaryTreeDictionary.cpp 1.37 07/05/05 17:05:43 JVM"
3 #endif
4 /*
5 * Copyright 2001-2006 Sun Microsystems, Inc. All Rights Reserved.
6 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
7 *
8 * This code is free software; you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License version 2 only, as
10 * published by the Free Software Foundation.
11 *
12 * This code is distributed in the hope that it will be useful, but WITHOUT
13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 * version 2 for more details (a copy is included in the LICENSE file that
16 * accompanied this code).
17 *
18 * You should have received a copy of the GNU General Public License version
19 * 2 along with this work; if not, write to the Free Software Foundation,
20 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
21 *
22 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
23 * CA 95054 USA or visit www.sun.com if you need additional information or
24 * have any questions.
25 *
57 assert(tc->size() >= sizeof(TreeChunk), "Chunk is too small for a TreeChunk");
58 TreeList* tl = tc->embedded_list();
59 tc->set_list(tl);
60 #ifdef ASSERT
61 tl->set_protecting_lock(NULL);
62 #endif
63 tl->set_hint(0);
64 tl->set_size(tc->size());
65 tl->link_head(tc);
66 tl->link_tail(tc);
67 tl->set_count(1);
68 tl->init_statistics();
69 tl->setParent(NULL);
70 tl->setLeft(NULL);
71 tl->setRight(NULL);
72 return tl;
73 }
74 TreeList* TreeList::as_TreeList(HeapWord* addr, size_t size) {
75 TreeChunk* tc = (TreeChunk*) addr;
76 assert(size >= sizeof(TreeChunk), "Chunk is too small for a TreeChunk");
77 assert(tc->size() == 0 && tc->prev() == NULL && tc->next() == NULL,
78 "Space should be clear");
79 tc->setSize(size);
80 tc->linkPrev(NULL);
81 tc->linkNext(NULL);
82 TreeList* tl = TreeList::as_TreeList(tc);
83 return tl;
84 }
85
86 TreeList* TreeList::removeChunkReplaceIfNeeded(TreeChunk* tc) {
87
88 TreeList* retTL = this;
89 FreeChunk* list = head();
90 assert(!list || list != list->next(), "Chunk on list twice");
91 assert(tc != NULL, "Chunk being removed is NULL");
92 assert(parent() == NULL || this == parent()->left() ||
93 this == parent()->right(), "list is inconsistent");
94 assert(tc->isFree(), "Header is not marked correctly");
95 assert(head() == NULL || head()->prev() == NULL, "list invariant");
96 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
97
98 FreeChunk* prevFC = tc->prev();
1057 // Print summary statistics
1058 void BinaryTreeDictionary::reportStatistics() const {
1059 verify_par_locked();
1060 gclog_or_tty->print("Statistics for BinaryTreeDictionary:\n"
1061 "------------------------------------\n");
1062 size_t totalSize = totalChunkSize(debug_only(NULL));
1063 size_t freeBlocks = numFreeBlocks();
1064 gclog_or_tty->print("Total Free Space: %d\n", totalSize);
1065 gclog_or_tty->print("Max Chunk Size: %d\n", maxChunkSize());
1066 gclog_or_tty->print("Number of Blocks: %d\n", freeBlocks);
1067 if (freeBlocks > 0) {
1068 gclog_or_tty->print("Av. Block Size: %d\n", totalSize/freeBlocks);
1069 }
1070 gclog_or_tty->print("Tree Height: %d\n", treeHeight());
1071 }
1072
1073 // Print census information - counts, births, deaths, etc.
1074 // for each list in the tree. Also print some summary
1075 // information.
1076 class printTreeCensusClosure : public AscendTreeCensusClosure {
1077 size_t _totalFree;
1078 AllocationStats _totals;
1079 size_t _count;
1080
1081 public:
1082 printTreeCensusClosure() {
1083 _totalFree = 0;
1084 _count = 0;
1085 _totals.initialize();
1086 }
1087 AllocationStats* totals() { return &_totals; }
1088 size_t count() { return _count; }
1089 void increment_count_by(size_t v) { _count += v; }
1090 size_t totalFree() { return _totalFree; }
1091 void increment_totalFree_by(size_t v) { _totalFree += v; }
1092 void do_list(FreeList* fl) {
1093 bool nl = false; // "maybe this is not needed" isNearLargestChunk(fl->head());
1094
1095 gclog_or_tty->print("%c %4d\t\t" "%7d\t" "%7d\t"
1096 "%7d\t" "%7d\t" "%7d\t" "%7d\t"
1097 "%7d\t" "%7d\t" "%7d\t"
1098 "%7d\t" "\n",
1099 " n"[nl], fl->size(), fl->bfrSurp(), fl->surplus(),
1100 fl->desired(), fl->prevSweep(), fl->beforeSweep(), fl->count(),
1101 fl->coalBirths(), fl->coalDeaths(), fl->splitBirths(),
1102 fl->splitDeaths());
1103
1104 increment_totalFree_by(fl->count() * fl->size());
1105 increment_count_by(fl->count());
1106 totals()->set_bfrSurp(totals()->bfrSurp() + fl->bfrSurp());
1107 totals()->set_surplus(totals()->splitDeaths() + fl->surplus());
1108 totals()->set_prevSweep(totals()->prevSweep() + fl->prevSweep());
1109 totals()->set_beforeSweep(totals()->beforeSweep() + fl->beforeSweep());
1110 totals()->set_coalBirths(totals()->coalBirths() + fl->coalBirths());
1111 totals()->set_coalDeaths(totals()->coalDeaths() + fl->coalDeaths());
1112 totals()->set_splitBirths(totals()->splitBirths() + fl->splitBirths());
1113 totals()->set_splitDeaths(totals()->splitDeaths() + fl->splitDeaths());
1114 }
1115 };
1116
1117 void BinaryTreeDictionary::printDictCensus(void) const {
1118
1119 gclog_or_tty->print("\nBinaryTree\n");
1120 gclog_or_tty->print(
1121 "%4s\t\t" "%7s\t" "%7s\t" "%7s\t" "%7s\t" "%7s\t"
1122 "%7s\t" "%7s\t" "%7s\t" "%7s\t" "%7s\t" "\n",
1123 "size", "bfrsurp", "surplus", "desired", "prvSwep", "bfrSwep",
1124 "count", "cBirths", "cDeaths", "sBirths", "sDeaths");
1125
1126 printTreeCensusClosure ptc;
1127 ptc.do_tree(root());
1128
1129 gclog_or_tty->print(
1130 "\t\t" "%7s\t" "%7s\t" "%7s\t" "%7s\t"
1131 "%7s\t" "%7s\t" "%7s\t" "%7s\t" "%7s\t" "\n",
1132 "bfrsurp", "surplus", "prvSwep", "bfrSwep",
1133 "count", "cBirths", "cDeaths", "sBirths", "sDeaths");
1134 gclog_or_tty->print(
1135 "%s\t\t" "%7d\t" "%7d\t" "%7d\t" "%7d\t"
1136 "%7d\t" "%7d\t" "%7d\t" "%7d\t" "%7d\t" "\n",
1137 "totl",
1138 ptc.totals()->bfrSurp(),
1139 ptc.totals()->surplus(),
1140 ptc.totals()->prevSweep(),
1141 ptc.totals()->beforeSweep(),
1142 ptc.count(),
1143 ptc.totals()->coalBirths(),
1144 ptc.totals()->coalDeaths(),
1145 ptc.totals()->splitBirths(),
1146 ptc.totals()->splitDeaths());
1147 gclog_or_tty->print("totalFree(words): %7d growth: %8.5f deficit: %8.5f\n",
1148 ptc.totalFree(),
1149 (double)(ptc.totals()->splitBirths()+ptc.totals()->coalBirths()
1150 -ptc.totals()->splitDeaths()-ptc.totals()->coalDeaths())
1151 /(ptc.totals()->prevSweep() != 0 ?
1152 (double)ptc.totals()->prevSweep() : 1.0),
1153 (double)(ptc.totals()->desired() - ptc.count())
1154 /(ptc.totals()->desired() != 0 ?
1155 (double)ptc.totals()->desired() : 1.0));
1156 }
1157
1158 // Verify the following tree invariants:
1159 // . _root has no parent
1160 // . parent and child point to each other
1161 // . each node's key correctly related to that of its child(ren)
1162 void BinaryTreeDictionary::verifyTree() const {
1163 guarantee(root() == NULL || totalFreeBlocks() == 0 ||
1164 totalSize() != 0, "_totalSize should't be 0?");
1165 guarantee(root() == NULL || root()->parent() == NULL, "_root shouldn't have parent");
1166 verifyTreeHelper(root());
1167 }
1168
1169 size_t BinaryTreeDictionary::verifyPrevFreePtrs(TreeList* tl) {
1170 size_t ct = 0;
1171 for (FreeChunk* curFC = tl->head(); curFC != NULL; curFC = curFC->next()) {
1172 ct++;
1173 assert(curFC->prev() == NULL || curFC->prev()->isFree(),
1174 "Chunk should be free");
1175 }
|
1 #ifdef USE_PRAGMA_IDENT_SRC
2 #pragma ident "@(#)binaryTreeDictionary.cpp 1.37 07/05/05 17:05:43 JVM"
3 #endif
4 /*
5 * Copyright 2001-2008 Sun Microsystems, Inc. All Rights Reserved.
6 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
7 *
8 * This code is free software; you can redistribute it and/or modify it
9 * under the terms of the GNU General Public License version 2 only, as
10 * published by the Free Software Foundation.
11 *
12 * This code is distributed in the hope that it will be useful, but WITHOUT
13 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 * version 2 for more details (a copy is included in the LICENSE file that
16 * accompanied this code).
17 *
18 * You should have received a copy of the GNU General Public License version
19 * 2 along with this work; if not, write to the Free Software Foundation,
20 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
21 *
22 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
23 * CA 95054 USA or visit www.sun.com if you need additional information or
24 * have any questions.
25 *
57 assert(tc->size() >= sizeof(TreeChunk), "Chunk is too small for a TreeChunk");
58 TreeList* tl = tc->embedded_list();
59 tc->set_list(tl);
60 #ifdef ASSERT
61 tl->set_protecting_lock(NULL);
62 #endif
63 tl->set_hint(0);
64 tl->set_size(tc->size());
65 tl->link_head(tc);
66 tl->link_tail(tc);
67 tl->set_count(1);
68 tl->init_statistics();
69 tl->setParent(NULL);
70 tl->setLeft(NULL);
71 tl->setRight(NULL);
72 return tl;
73 }
74 TreeList* TreeList::as_TreeList(HeapWord* addr, size_t size) {
75 TreeChunk* tc = (TreeChunk*) addr;
76 assert(size >= sizeof(TreeChunk), "Chunk is too small for a TreeChunk");
77 // The space in the heap will have been mangled initially but
78 // is not remangled when a free chunk is returned to the free list
79 // (since it is used to maintain the chunk on the free list).
80 assert((ZapUnusedHeapArea &&
81 SpaceMangler::is_mangled((HeapWord*) tc->size_addr()) &&
82 SpaceMangler::is_mangled((HeapWord*) tc->prev_addr()) &&
83 SpaceMangler::is_mangled((HeapWord*) tc->next_addr())) ||
84 (tc->size() == 0 && tc->prev() == NULL && tc->next() == NULL),
85 "Space should be clear or mangled");
86 tc->setSize(size);
87 tc->linkPrev(NULL);
88 tc->linkNext(NULL);
89 TreeList* tl = TreeList::as_TreeList(tc);
90 return tl;
91 }
92
93 TreeList* TreeList::removeChunkReplaceIfNeeded(TreeChunk* tc) {
94
95 TreeList* retTL = this;
96 FreeChunk* list = head();
97 assert(!list || list != list->next(), "Chunk on list twice");
98 assert(tc != NULL, "Chunk being removed is NULL");
99 assert(parent() == NULL || this == parent()->left() ||
100 this == parent()->right(), "list is inconsistent");
101 assert(tc->isFree(), "Header is not marked correctly");
102 assert(head() == NULL || head()->prev() == NULL, "list invariant");
103 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
104
105 FreeChunk* prevFC = tc->prev();
1064 // Print summary statistics
1065 void BinaryTreeDictionary::reportStatistics() const {
1066 verify_par_locked();
1067 gclog_or_tty->print("Statistics for BinaryTreeDictionary:\n"
1068 "------------------------------------\n");
1069 size_t totalSize = totalChunkSize(debug_only(NULL));
1070 size_t freeBlocks = numFreeBlocks();
1071 gclog_or_tty->print("Total Free Space: %d\n", totalSize);
1072 gclog_or_tty->print("Max Chunk Size: %d\n", maxChunkSize());
1073 gclog_or_tty->print("Number of Blocks: %d\n", freeBlocks);
1074 if (freeBlocks > 0) {
1075 gclog_or_tty->print("Av. Block Size: %d\n", totalSize/freeBlocks);
1076 }
1077 gclog_or_tty->print("Tree Height: %d\n", treeHeight());
1078 }
1079
1080 // Print census information - counts, births, deaths, etc.
1081 // for each list in the tree. Also print some summary
1082 // information.
1083 class printTreeCensusClosure : public AscendTreeCensusClosure {
1084 int _print_line;
1085 size_t _totalFree;
1086 FreeList _total;
1087
1088 public:
1089 printTreeCensusClosure() {
1090 _print_line = 0;
1091 _totalFree = 0;
1092 }
1093 FreeList* total() { return &_total; }
1094 size_t totalFree() { return _totalFree; }
1095 void do_list(FreeList* fl) {
1096 if (++_print_line >= 40) {
1097 FreeList::print_labels_on(gclog_or_tty, "size");
1098 _print_line = 0;
1099 }
1100 fl->print_on(gclog_or_tty);
1101 _totalFree += fl->count() * fl->size() ;
1102 total()->set_count( total()->count() + fl->count() );
1103 total()->set_bfrSurp( total()->bfrSurp() + fl->bfrSurp() );
1104 total()->set_surplus( total()->splitDeaths() + fl->surplus() );
1105 total()->set_desired( total()->desired() + fl->desired() );
1106 total()->set_prevSweep( total()->prevSweep() + fl->prevSweep() );
1107 total()->set_beforeSweep(total()->beforeSweep() + fl->beforeSweep());
1108 total()->set_coalBirths( total()->coalBirths() + fl->coalBirths() );
1109 total()->set_coalDeaths( total()->coalDeaths() + fl->coalDeaths() );
1110 total()->set_splitBirths(total()->splitBirths() + fl->splitBirths());
1111 total()->set_splitDeaths(total()->splitDeaths() + fl->splitDeaths());
1112 }
1113 };
1114
1115 void BinaryTreeDictionary::printDictCensus(void) const {
1116
1117 gclog_or_tty->print("\nBinaryTree\n");
1118 FreeList::print_labels_on(gclog_or_tty, "size");
1119 printTreeCensusClosure ptc;
1120 ptc.do_tree(root());
1121
1122 FreeList* total = ptc.total();
1123 FreeList::print_labels_on(gclog_or_tty, " ");
1124 total->print_on(gclog_or_tty, "TOTAL\t");
1125 gclog_or_tty->print(
1126 "totalFree(words): " SIZE_FORMAT_W(16)
1127 " growth: %8.5f deficit: %8.5f\n",
1128 ptc.totalFree(),
1129 (double)(total->splitBirths() + total->coalBirths()
1130 - total->splitDeaths() - total->coalDeaths())
1131 /(total->prevSweep() != 0 ? (double)total->prevSweep() : 1.0),
1132 (double)(total->desired() - total->count())
1133 /(total->desired() != 0 ? (double)total->desired() : 1.0));
1134 }
1135
1136 // Verify the following tree invariants:
1137 // . _root has no parent
1138 // . parent and child point to each other
1139 // . each node's key correctly related to that of its child(ren)
1140 void BinaryTreeDictionary::verifyTree() const {
1141 guarantee(root() == NULL || totalFreeBlocks() == 0 ||
1142 totalSize() != 0, "_totalSize should't be 0?");
1143 guarantee(root() == NULL || root()->parent() == NULL, "_root shouldn't have parent");
1144 verifyTreeHelper(root());
1145 }
1146
1147 size_t BinaryTreeDictionary::verifyPrevFreePtrs(TreeList* tl) {
1148 size_t ct = 0;
1149 for (FreeChunk* curFC = tl->head(); curFC != NULL; curFC = curFC->next()) {
1150 ct++;
1151 assert(curFC->prev() == NULL || curFC->prev()->isFree(),
1152 "Chunk should be free");
1153 }
|