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 "memory/binaryTreeDictionary.hpp"
29 #include "memory/freeBlockDictionary.hpp"
30 #include "memory/freeList.hpp"
31 #include "memory/metachunk.hpp"
32 #include "runtime/globals.hpp"
33 #include "utilities/macros.hpp"
34 #include "utilities/ostream.hpp"
35 #if INCLUDE_ALL_GCS
36 #include "gc/cms/adaptiveFreeList.hpp"
37 #include "gc/cms/freeChunk.hpp"
38 #endif // INCLUDE_ALL_GCS
39
40 ////////////////////////////////////////////////////////////////////////////////
41 // A binary tree based search structure for free blocks.
42 // This is currently used in the Concurrent Mark&Sweep implementation.
43 ////////////////////////////////////////////////////////////////////////////////
44
45 template <class Chunk_t, class FreeList_t>
46 size_t TreeChunk<Chunk_t, FreeList_t>::_min_tree_chunk_size = sizeof(TreeChunk<Chunk_t, FreeList_t>)/HeapWordSize;
47
48 template <class Chunk_t, class FreeList_t>
49 TreeChunk<Chunk_t, FreeList_t>* TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(Chunk_t* fc) {
50 // Do some assertion checking here.
51 return (TreeChunk<Chunk_t, FreeList_t>*) fc;
1172 fl->set_coal_births(0);
1173 fl->set_coal_deaths(0);
1174 fl->set_split_births(0);
1175 fl->set_split_deaths(0);
1176 }
1177 #endif // INCLUDE_ALL_GCS
1178 };
1179
1180 template <class Chunk_t, class FreeList_t>
1181 void BinaryTreeDictionary<Chunk_t, FreeList_t>::clear_tree_census(void) {
1182 clearTreeCensusClosure<Chunk_t, FreeList_t> ctc;
1183 ctc.do_tree(root());
1184 }
1185
1186 // Do reporting and post sweep clean up.
1187 template <class Chunk_t, class FreeList_t>
1188 void BinaryTreeDictionary<Chunk_t, FreeList_t>::end_sweep_dict_census(double splitSurplusPercent) {
1189 // Does walking the tree 3 times hurt?
1190 set_tree_surplus(splitSurplusPercent);
1191 set_tree_hints();
1192 if (PrintGC && Verbose) {
1193 report_statistics();
1194 }
1195 clear_tree_census();
1196 }
1197
1198 // Print summary statistics
1199 template <class Chunk_t, class FreeList_t>
1200 void BinaryTreeDictionary<Chunk_t, FreeList_t>::report_statistics() const {
1201 FreeBlockDictionary<Chunk_t>::verify_par_locked();
1202 gclog_or_tty->print("Statistics for BinaryTreeDictionary:\n"
1203 "------------------------------------\n");
1204 size_t total_size = total_chunk_size(debug_only(NULL));
1205 size_t free_blocks = num_free_blocks();
1206 gclog_or_tty->print("Total Free Space: " SIZE_FORMAT "\n", total_size);
1207 gclog_or_tty->print("Max Chunk Size: " SIZE_FORMAT "\n", max_chunk_size());
1208 gclog_or_tty->print("Number of Blocks: " SIZE_FORMAT "\n", free_blocks);
1209 if (free_blocks > 0) {
1210 gclog_or_tty->print("Av. Block Size: " SIZE_FORMAT "\n", total_size/free_blocks);
1211 }
1212 gclog_or_tty->print("Tree Height: " SIZE_FORMAT "\n", tree_height());
1213 }
1214
1215 // Print census information - counts, births, deaths, etc.
1216 // for each list in the tree. Also print some summary
1217 // information.
1218 template <class Chunk_t, class FreeList_t>
1219 class PrintTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
1220 int _print_line;
1221 size_t _total_free;
1222 FreeList_t _total;
1223
1224 public:
1225 PrintTreeCensusClosure() {
1226 _print_line = 0;
1227 _total_free = 0;
1228 }
1229 FreeList_t* total() { return &_total; }
1230 size_t total_free() { return _total_free; }
1231 void do_list(FreeList<Chunk_t>* fl) {
1232 if (++_print_line >= 40) {
1233 FreeList_t::print_labels_on(gclog_or_tty, "size");
1234 _print_line = 0;
1235 }
1236 fl->print_on(gclog_or_tty);
1237 _total_free += fl->count() * fl->size() ;
1238 total()->set_count( total()->count() + fl->count() );
1239 }
1240
1241 #if INCLUDE_ALL_GCS
1242 void do_list(AdaptiveFreeList<Chunk_t>* fl) {
1243 if (++_print_line >= 40) {
1244 FreeList_t::print_labels_on(gclog_or_tty, "size");
1245 _print_line = 0;
1246 }
1247 fl->print_on(gclog_or_tty);
1248 _total_free += fl->count() * fl->size() ;
1249 total()->set_count( total()->count() + fl->count() );
1250 total()->set_bfr_surp( total()->bfr_surp() + fl->bfr_surp() );
1251 total()->set_surplus( total()->split_deaths() + fl->surplus() );
1252 total()->set_desired( total()->desired() + fl->desired() );
1253 total()->set_prev_sweep( total()->prev_sweep() + fl->prev_sweep() );
1254 total()->set_before_sweep(total()->before_sweep() + fl->before_sweep());
1255 total()->set_coal_births( total()->coal_births() + fl->coal_births() );
1256 total()->set_coal_deaths( total()->coal_deaths() + fl->coal_deaths() );
1257 total()->set_split_births(total()->split_births() + fl->split_births());
1258 total()->set_split_deaths(total()->split_deaths() + fl->split_deaths());
1259 }
1260 #endif // INCLUDE_ALL_GCS
1261 };
1262
1263 template <class Chunk_t, class FreeList_t>
1264 void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_dict_census(void) const {
1265
1266 gclog_or_tty->print("\nBinaryTree\n");
1267 FreeList_t::print_labels_on(gclog_or_tty, "size");
1268 PrintTreeCensusClosure<Chunk_t, FreeList_t> ptc;
1269 ptc.do_tree(root());
1270
1271 FreeList_t* total = ptc.total();
1272 FreeList_t::print_labels_on(gclog_or_tty, " ");
1273 }
1274
1275 #if INCLUDE_ALL_GCS
1276 template <>
1277 void AFLBinaryTreeDictionary::print_dict_census(void) const {
1278
1279 gclog_or_tty->print("\nBinaryTree\n");
1280 AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, "size");
1281 PrintTreeCensusClosure<FreeChunk, AdaptiveFreeList<FreeChunk> > ptc;
1282 ptc.do_tree(root());
1283
1284 AdaptiveFreeList<FreeChunk>* total = ptc.total();
1285 AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, " ");
1286 total->print_on(gclog_or_tty, "TOTAL\t");
1287 gclog_or_tty->print(
1288 "total_free(words): " SIZE_FORMAT_W(16)
1289 " growth: %8.5f deficit: %8.5f\n",
1290 ptc.total_free(),
1291 (double)(total->split_births() + total->coal_births()
1292 - total->split_deaths() - total->coal_deaths())
1293 /(total->prev_sweep() != 0 ? (double)total->prev_sweep() : 1.0),
1294 (double)(total->desired() - total->count())
1295 /(total->desired() != 0 ? (double)total->desired() : 1.0));
1296 }
1297 #endif // INCLUDE_ALL_GCS
1298
1299 template <class Chunk_t, class FreeList_t>
1300 class PrintFreeListsClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
1301 outputStream* _st;
1302 int _print_line;
1303
1304 public:
1305 PrintFreeListsClosure(outputStream* st) {
1306 _st = st;
1307 _print_line = 0;
1308 }
1309 void do_list(FreeList_t* fl) {
1310 if (++_print_line >= 40) {
1311 FreeList_t::print_labels_on(_st, "size");
1312 _print_line = 0;
1313 }
1314 fl->print_on(gclog_or_tty);
1315 size_t sz = fl->size();
1316 for (Chunk_t* fc = fl->head(); fc != NULL;
1317 fc = fc->next()) {
1318 _st->print_cr("\t[" PTR_FORMAT "," PTR_FORMAT ") %s",
1319 p2i(fc), p2i((HeapWord*)fc + sz),
1320 fc->cantCoalesce() ? "\t CC" : "");
1321 }
1322 }
1323 };
1324
1325 template <class Chunk_t, class FreeList_t>
1326 void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_free_lists(outputStream* st) const {
1327
1328 FreeList_t::print_labels_on(st, "size");
1329 PrintFreeListsClosure<Chunk_t, FreeList_t> pflc(st);
1330 pflc.do_tree(root());
1331 }
1332
1333 // Verify the following tree invariants:
1334 // . _root has no parent
|
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 "memory/binaryTreeDictionary.hpp"
29 #include "memory/freeBlockDictionary.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>
50 TreeChunk<Chunk_t, FreeList_t>* TreeChunk<Chunk_t, FreeList_t>::as_TreeChunk(Chunk_t* fc) {
51 // Do some assertion checking here.
52 return (TreeChunk<Chunk_t, FreeList_t>*) fc;
1173 fl->set_coal_births(0);
1174 fl->set_coal_deaths(0);
1175 fl->set_split_births(0);
1176 fl->set_split_deaths(0);
1177 }
1178 #endif // INCLUDE_ALL_GCS
1179 };
1180
1181 template <class Chunk_t, class FreeList_t>
1182 void BinaryTreeDictionary<Chunk_t, FreeList_t>::clear_tree_census(void) {
1183 clearTreeCensusClosure<Chunk_t, FreeList_t> ctc;
1184 ctc.do_tree(root());
1185 }
1186
1187 // Do reporting and post sweep clean up.
1188 template <class Chunk_t, class FreeList_t>
1189 void BinaryTreeDictionary<Chunk_t, FreeList_t>::end_sweep_dict_census(double splitSurplusPercent) {
1190 // Does walking the tree 3 times hurt?
1191 set_tree_surplus(splitSurplusPercent);
1192 set_tree_hints();
1193 LogHandle(gc, freelist, stats) log;
1194 if (log.is_trace()) {
1195 ResourceMark rm;
1196 report_statistics(log.trace_stream());
1197 }
1198 clear_tree_census();
1199 }
1200
1201 // Print summary statistics
1202 template <class Chunk_t, class FreeList_t>
1203 void BinaryTreeDictionary<Chunk_t, FreeList_t>::report_statistics(outputStream* st) const {
1204 FreeBlockDictionary<Chunk_t>::verify_par_locked();
1205 st->print_cr("Statistics for BinaryTreeDictionary:");
1206 st->print_cr("------------------------------------");
1207 size_t total_size = total_chunk_size(debug_only(NULL));
1208 size_t free_blocks = num_free_blocks();
1209 st->print_cr("Total Free Space: " SIZE_FORMAT, total_size);
1210 st->print_cr("Max Chunk Size: " SIZE_FORMAT, max_chunk_size());
1211 st->print_cr("Number of Blocks: " SIZE_FORMAT, free_blocks);
1212 if (free_blocks > 0) {
1213 st->print_cr("Av. Block Size: " SIZE_FORMAT, total_size/free_blocks);
1214 }
1215 st->print_cr("Tree Height: " SIZE_FORMAT, tree_height());
1216 }
1217
1218 // Print census information - counts, births, deaths, etc.
1219 // for each list in the tree. Also print some summary
1220 // information.
1221 template <class Chunk_t, class FreeList_t>
1222 class PrintTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
1223 int _print_line;
1224 size_t _total_free;
1225 FreeList_t _total;
1226
1227 public:
1228 PrintTreeCensusClosure() {
1229 _print_line = 0;
1230 _total_free = 0;
1231 }
1232 FreeList_t* total() { return &_total; }
1233 size_t total_free() { return _total_free; }
1234 void do_list(FreeList<Chunk_t>* fl) {
1235 LogHandle(gc, freelist, census) log;
1236 outputStream* out = log.debug_stream();
1237 if (++_print_line >= 40) {
1238 ResourceMark rm;
1239 FreeList_t::print_labels_on(out, "size");
1240 _print_line = 0;
1241 }
1242 fl->print_on(out);
1243 _total_free += fl->count() * fl->size();
1244 total()->set_count(total()->count() + fl->count());
1245 }
1246
1247 #if INCLUDE_ALL_GCS
1248 void do_list(AdaptiveFreeList<Chunk_t>* fl) {
1249 LogHandle(gc, freelist, census) log;
1250 outputStream* out = log.debug_stream();
1251 if (++_print_line >= 40) {
1252 FreeList_t::print_labels_on(out, "size");
1253 _print_line = 0;
1254 }
1255 fl->print_on(out);
1256 _total_free += fl->count() * fl->size() ;
1257 total()->set_count( total()->count() + fl->count() );
1258 total()->set_bfr_surp( total()->bfr_surp() + fl->bfr_surp() );
1259 total()->set_surplus( total()->split_deaths() + fl->surplus() );
1260 total()->set_desired( total()->desired() + fl->desired() );
1261 total()->set_prev_sweep( total()->prev_sweep() + fl->prev_sweep() );
1262 total()->set_before_sweep(total()->before_sweep() + fl->before_sweep());
1263 total()->set_coal_births( total()->coal_births() + fl->coal_births() );
1264 total()->set_coal_deaths( total()->coal_deaths() + fl->coal_deaths() );
1265 total()->set_split_births(total()->split_births() + fl->split_births());
1266 total()->set_split_deaths(total()->split_deaths() + fl->split_deaths());
1267 }
1268 #endif // INCLUDE_ALL_GCS
1269 };
1270
1271 template <class Chunk_t, class FreeList_t>
1272 void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_dict_census(outputStream* st) const {
1273
1274 st->print("BinaryTree");
1275 FreeList_t::print_labels_on(st, "size");
1276 PrintTreeCensusClosure<Chunk_t, FreeList_t> ptc;
1277 ptc.do_tree(root());
1278
1279 FreeList_t* total = ptc.total();
1280 FreeList_t::print_labels_on(st, " ");
1281 }
1282
1283 #if INCLUDE_ALL_GCS
1284 template <>
1285 void AFLBinaryTreeDictionary::print_dict_census(outputStream* st) const {
1286
1287 st->print_cr("BinaryTree");
1288 AdaptiveFreeList<FreeChunk>::print_labels_on(st, "size");
1289 PrintTreeCensusClosure<FreeChunk, AdaptiveFreeList<FreeChunk> > ptc;
1290 ptc.do_tree(root());
1291
1292 AdaptiveFreeList<FreeChunk>* total = ptc.total();
1293 AdaptiveFreeList<FreeChunk>::print_labels_on(st, " ");
1294 total->print_on(st, "TOTAL\t");
1295 st->print_cr("total_free(words): " SIZE_FORMAT_W(16) " growth: %8.5f deficit: %8.5f",
1296 ptc.total_free(),
1297 (double)(total->split_births() + total->coal_births()
1298 - total->split_deaths() - total->coal_deaths())
1299 /(total->prev_sweep() != 0 ? (double)total->prev_sweep() : 1.0),
1300 (double)(total->desired() - total->count())
1301 /(total->desired() != 0 ? (double)total->desired() : 1.0));
1302 }
1303 #endif // INCLUDE_ALL_GCS
1304
1305 template <class Chunk_t, class FreeList_t>
1306 class PrintFreeListsClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> {
1307 outputStream* _st;
1308 int _print_line;
1309
1310 public:
1311 PrintFreeListsClosure(outputStream* st) {
1312 _st = st;
1313 _print_line = 0;
1314 }
1315 void do_list(FreeList_t* fl) {
1316 if (++_print_line >= 40) {
1317 FreeList_t::print_labels_on(_st, "size");
1318 _print_line = 0;
1319 }
1320 fl->print_on(_st);
1321 size_t sz = fl->size();
1322 for (Chunk_t* fc = fl->head(); fc != NULL;
1323 fc = fc->next()) {
1324 _st->print_cr("\t[" PTR_FORMAT "," PTR_FORMAT ") %s",
1325 p2i(fc), p2i((HeapWord*)fc + sz),
1326 fc->cantCoalesce() ? "\t CC" : "");
1327 }
1328 }
1329 };
1330
1331 template <class Chunk_t, class FreeList_t>
1332 void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_free_lists(outputStream* st) const {
1333
1334 FreeList_t::print_labels_on(st, "size");
1335 PrintFreeListsClosure<Chunk_t, FreeList_t> pflc(st);
1336 pflc.do_tree(root());
1337 }
1338
1339 // Verify the following tree invariants:
1340 // . _root has no parent
|