21 * questions. |
21 * questions. |
22 * |
22 * |
23 */ |
23 */ |
24 |
24 |
25 #include "precompiled.hpp" |
25 #include "precompiled.hpp" |
|
26 #include "utilities/macros.hpp" |
26 #include "gc_implementation/shared/allocationStats.hpp" |
27 #include "gc_implementation/shared/allocationStats.hpp" |
27 #include "memory/binaryTreeDictionary.hpp" |
28 #include "memory/binaryTreeDictionary.hpp" |
28 #include "memory/freeList.hpp" |
29 #include "memory/freeList.hpp" |
29 #include "memory/freeBlockDictionary.hpp" |
30 #include "memory/freeBlockDictionary.hpp" |
30 #include "memory/metablock.hpp" |
31 #include "memory/metablock.hpp" |
31 #include "memory/metachunk.hpp" |
32 #include "memory/metachunk.hpp" |
32 #include "runtime/globals.hpp" |
33 #include "runtime/globals.hpp" |
33 #include "utilities/ostream.hpp" |
34 #include "utilities/ostream.hpp" |
34 #ifndef SERIALGC |
35 #include "utilities/macros.hpp" |
|
36 #if INCLUDE_ALL_GCS |
35 #include "gc_implementation/concurrentMarkSweep/adaptiveFreeList.hpp" |
37 #include "gc_implementation/concurrentMarkSweep/adaptiveFreeList.hpp" |
36 #include "gc_implementation/concurrentMarkSweep/freeChunk.hpp" |
38 #include "gc_implementation/concurrentMarkSweep/freeChunk.hpp" |
37 #include "gc_implementation/shared/spaceDecorator.hpp" |
39 #include "gc_implementation/shared/spaceDecorator.hpp" |
38 #include "gc_implementation/concurrentMarkSweep/freeChunk.hpp" |
40 #include "gc_implementation/concurrentMarkSweep/freeChunk.hpp" |
39 #endif // SERIALGC |
41 #endif // INCLUDE_ALL_GCS |
40 |
42 |
41 //////////////////////////////////////////////////////////////////////////////// |
43 //////////////////////////////////////////////////////////////////////////////// |
42 // A binary tree based search structure for free blocks. |
44 // A binary tree based search structure for free blocks. |
43 // This is currently used in the Concurrent Mark&Sweep implementation. |
45 // This is currently used in the Concurrent Mark&Sweep implementation. |
44 //////////////////////////////////////////////////////////////////////////////// |
46 //////////////////////////////////////////////////////////////////////////////// |
116 TreeList<Chunk_t, FreeList_t>* tl = TreeList<Chunk_t, FreeList_t>::as_TreeList(tc); |
118 TreeList<Chunk_t, FreeList_t>* tl = TreeList<Chunk_t, FreeList_t>::as_TreeList(tc); |
117 return tl; |
119 return tl; |
118 } |
120 } |
119 |
121 |
120 |
122 |
121 #ifndef SERIALGC |
123 #if INCLUDE_ALL_GCS |
122 // Specialize for AdaptiveFreeList which tries to avoid |
124 // Specialize for AdaptiveFreeList which tries to avoid |
123 // splitting a chunk of a size that is under populated in favor of |
125 // splitting a chunk of a size that is under populated in favor of |
124 // an over populated size. The general get_better_list() just returns |
126 // an over populated size. The general get_better_list() just returns |
125 // the current list. |
127 // the current list. |
126 template <> |
128 template <> |
158 } |
160 } |
159 } |
161 } |
160 } |
162 } |
161 return curTL; |
163 return curTL; |
162 } |
164 } |
163 #endif // SERIALGC |
165 #endif // INCLUDE_ALL_GCS |
164 |
166 |
165 template <class Chunk_t, template <class> class FreeList_t> |
167 template <class Chunk_t, template <class> class FreeList_t> |
166 TreeList<Chunk_t, FreeList_t>* |
168 TreeList<Chunk_t, FreeList_t>* |
167 TreeList<Chunk_t, FreeList_t>::get_better_list( |
169 TreeList<Chunk_t, FreeList_t>::get_better_list( |
168 BinaryTreeDictionary<Chunk_t, FreeList_t>* dictionary) { |
170 BinaryTreeDictionary<Chunk_t, FreeList_t>* dictionary) { |
869 } |
871 } |
870 |
872 |
871 template <class Chunk_t, template <class> class FreeList_t> |
873 template <class Chunk_t, template <class> class FreeList_t> |
872 void BinaryTreeDictionary<Chunk_t, FreeList_t>::dict_census_update(size_t size, bool split, bool birth){} |
874 void BinaryTreeDictionary<Chunk_t, FreeList_t>::dict_census_update(size_t size, bool split, bool birth){} |
873 |
875 |
874 #ifndef SERIALGC |
876 #if INCLUDE_ALL_GCS |
875 template <> |
877 template <> |
876 void AFLBinaryTreeDictionary::dict_census_update(size_t size, bool split, bool birth){ |
878 void AFLBinaryTreeDictionary::dict_census_update(size_t size, bool split, bool birth){ |
877 TreeList<FreeChunk, AdaptiveFreeList>* nd = find_list(size); |
879 TreeList<FreeChunk, AdaptiveFreeList>* nd = find_list(size); |
878 if (nd) { |
880 if (nd) { |
879 if (split) { |
881 if (split) { |
898 // This is a death where the appropriate list is now |
900 // This is a death where the appropriate list is now |
899 // empty and has been removed from the list. |
901 // empty and has been removed from the list. |
900 // This is a birth associated with a LinAB. The chunk |
902 // This is a birth associated with a LinAB. The chunk |
901 // for the LinAB is not in the dictionary. |
903 // for the LinAB is not in the dictionary. |
902 } |
904 } |
903 #endif // SERIALGC |
905 #endif // INCLUDE_ALL_GCS |
904 |
906 |
905 template <class Chunk_t, template <class> class FreeList_t> |
907 template <class Chunk_t, template <class> class FreeList_t> |
906 bool BinaryTreeDictionary<Chunk_t, FreeList_t>::coal_dict_over_populated(size_t size) { |
908 bool BinaryTreeDictionary<Chunk_t, FreeList_t>::coal_dict_over_populated(size_t size) { |
907 // For the general type of freelists, encourage coalescing by |
909 // For the general type of freelists, encourage coalescing by |
908 // returning true. |
910 // returning true. |
909 return true; |
911 return true; |
910 } |
912 } |
911 |
913 |
912 #ifndef SERIALGC |
914 #if INCLUDE_ALL_GCS |
913 template <> |
915 template <> |
914 bool AFLBinaryTreeDictionary::coal_dict_over_populated(size_t size) { |
916 bool AFLBinaryTreeDictionary::coal_dict_over_populated(size_t size) { |
915 if (FLSAlwaysCoalesceLarge) return true; |
917 if (FLSAlwaysCoalesceLarge) return true; |
916 |
918 |
917 TreeList<FreeChunk, AdaptiveFreeList>* list_of_size = find_list(size); |
919 TreeList<FreeChunk, AdaptiveFreeList>* list_of_size = find_list(size); |
918 // None of requested size implies overpopulated. |
920 // None of requested size implies overpopulated. |
919 return list_of_size == NULL || list_of_size->coal_desired() <= 0 || |
921 return list_of_size == NULL || list_of_size->coal_desired() <= 0 || |
920 list_of_size->count() > list_of_size->coal_desired(); |
922 list_of_size->count() > list_of_size->coal_desired(); |
921 } |
923 } |
922 #endif // SERIALGC |
924 #endif // INCLUDE_ALL_GCS |
923 |
925 |
924 // Closures for walking the binary tree. |
926 // Closures for walking the binary tree. |
925 // do_list() walks the free list in a node applying the closure |
927 // do_list() walks the free list in a node applying the closure |
926 // to each free chunk in the list |
928 // to each free chunk in the list |
927 // do_tree() walks the nodes in the binary tree applying do_list() |
929 // do_tree() walks the nodes in the binary tree applying do_list() |
977 _inter_sweep_estimate(inter_sweep_estimate), |
979 _inter_sweep_estimate(inter_sweep_estimate), |
978 _intra_sweep_estimate(intra_sweep_estimate) { } |
980 _intra_sweep_estimate(intra_sweep_estimate) { } |
979 |
981 |
980 void do_list(FreeList<Chunk_t>* fl) {} |
982 void do_list(FreeList<Chunk_t>* fl) {} |
981 |
983 |
982 #ifndef SERIALGC |
984 #if INCLUDE_ALL_GCS |
983 void do_list(AdaptiveFreeList<Chunk_t>* fl) { |
985 void do_list(AdaptiveFreeList<Chunk_t>* fl) { |
984 double coalSurplusPercent = _percentage; |
986 double coalSurplusPercent = _percentage; |
985 fl->compute_desired(_inter_sweep_current, _inter_sweep_estimate, _intra_sweep_estimate); |
987 fl->compute_desired(_inter_sweep_current, _inter_sweep_estimate, _intra_sweep_estimate); |
986 fl->set_coal_desired((ssize_t)((double)fl->desired() * coalSurplusPercent)); |
988 fl->set_coal_desired((ssize_t)((double)fl->desired() * coalSurplusPercent)); |
987 fl->set_before_sweep(fl->count()); |
989 fl->set_before_sweep(fl->count()); |
988 fl->set_bfr_surp(fl->surplus()); |
990 fl->set_bfr_surp(fl->surplus()); |
989 } |
991 } |
990 #endif // SERIALGC |
992 #endif // INCLUDE_ALL_GCS |
991 }; |
993 }; |
992 |
994 |
993 // Used to search the tree until a condition is met. |
995 // Used to search the tree until a condition is met. |
994 // Similar to TreeCensusClosure but searches the |
996 // Similar to TreeCensusClosure but searches the |
995 // tree and returns promptly when found. |
997 // tree and returns promptly when found. |
1132 double percentage; |
1134 double percentage; |
1133 public: |
1135 public: |
1134 setTreeSurplusClosure(double v) { percentage = v; } |
1136 setTreeSurplusClosure(double v) { percentage = v; } |
1135 void do_list(FreeList<Chunk_t>* fl) {} |
1137 void do_list(FreeList<Chunk_t>* fl) {} |
1136 |
1138 |
1137 #ifndef SERIALGC |
1139 #if INCLUDE_ALL_GCS |
1138 void do_list(AdaptiveFreeList<Chunk_t>* fl) { |
1140 void do_list(AdaptiveFreeList<Chunk_t>* fl) { |
1139 double splitSurplusPercent = percentage; |
1141 double splitSurplusPercent = percentage; |
1140 fl->set_surplus(fl->count() - |
1142 fl->set_surplus(fl->count() - |
1141 (ssize_t)((double)fl->desired() * splitSurplusPercent)); |
1143 (ssize_t)((double)fl->desired() * splitSurplusPercent)); |
1142 } |
1144 } |
1143 #endif // SERIALGC |
1145 #endif // INCLUDE_ALL_GCS |
1144 }; |
1146 }; |
1145 |
1147 |
1146 template <class Chunk_t, template <class> class FreeList_t> |
1148 template <class Chunk_t, template <class> class FreeList_t> |
1147 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_surplus(double splitSurplusPercent) { |
1149 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_surplus(double splitSurplusPercent) { |
1148 setTreeSurplusClosure<Chunk_t, FreeList_t> sts(splitSurplusPercent); |
1150 setTreeSurplusClosure<Chunk_t, FreeList_t> sts(splitSurplusPercent); |
1155 size_t hint; |
1157 size_t hint; |
1156 public: |
1158 public: |
1157 setTreeHintsClosure(size_t v) { hint = v; } |
1159 setTreeHintsClosure(size_t v) { hint = v; } |
1158 void do_list(FreeList<Chunk_t>* fl) {} |
1160 void do_list(FreeList<Chunk_t>* fl) {} |
1159 |
1161 |
1160 #ifndef SERIALGC |
1162 #if INCLUDE_ALL_GCS |
1161 void do_list(AdaptiveFreeList<Chunk_t>* fl) { |
1163 void do_list(AdaptiveFreeList<Chunk_t>* fl) { |
1162 fl->set_hint(hint); |
1164 fl->set_hint(hint); |
1163 assert(fl->hint() == 0 || fl->hint() > fl->size(), |
1165 assert(fl->hint() == 0 || fl->hint() > fl->size(), |
1164 "Current hint is inconsistent"); |
1166 "Current hint is inconsistent"); |
1165 if (fl->surplus() > 0) { |
1167 if (fl->surplus() > 0) { |
1166 hint = fl->size(); |
1168 hint = fl->size(); |
1167 } |
1169 } |
1168 } |
1170 } |
1169 #endif // SERIALGC |
1171 #endif // INCLUDE_ALL_GCS |
1170 }; |
1172 }; |
1171 |
1173 |
1172 template <class Chunk_t, template <class> class FreeList_t> |
1174 template <class Chunk_t, template <class> class FreeList_t> |
1173 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_hints(void) { |
1175 void BinaryTreeDictionary<Chunk_t, FreeList_t>::set_tree_hints(void) { |
1174 setTreeHintsClosure<Chunk_t, FreeList_t> sth(0); |
1176 setTreeHintsClosure<Chunk_t, FreeList_t> sth(0); |
1178 // Save count before previous sweep and splits and coalesces. |
1180 // Save count before previous sweep and splits and coalesces. |
1179 template <class Chunk_t, template <class> class FreeList_t> |
1181 template <class Chunk_t, template <class> class FreeList_t> |
1180 class clearTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { |
1182 class clearTreeCensusClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { |
1181 void do_list(FreeList<Chunk_t>* fl) {} |
1183 void do_list(FreeList<Chunk_t>* fl) {} |
1182 |
1184 |
1183 #ifndef SERIALGC |
1185 #if INCLUDE_ALL_GCS |
1184 void do_list(AdaptiveFreeList<Chunk_t>* fl) { |
1186 void do_list(AdaptiveFreeList<Chunk_t>* fl) { |
1185 fl->set_prev_sweep(fl->count()); |
1187 fl->set_prev_sweep(fl->count()); |
1186 fl->set_coal_births(0); |
1188 fl->set_coal_births(0); |
1187 fl->set_coal_deaths(0); |
1189 fl->set_coal_deaths(0); |
1188 fl->set_split_births(0); |
1190 fl->set_split_births(0); |
1189 fl->set_split_deaths(0); |
1191 fl->set_split_deaths(0); |
1190 } |
1192 } |
1191 #endif // SERIALGC |
1193 #endif // INCLUDE_ALL_GCS |
1192 }; |
1194 }; |
1193 |
1195 |
1194 template <class Chunk_t, template <class> class FreeList_t> |
1196 template <class Chunk_t, template <class> class FreeList_t> |
1195 void BinaryTreeDictionary<Chunk_t, FreeList_t>::clear_tree_census(void) { |
1197 void BinaryTreeDictionary<Chunk_t, FreeList_t>::clear_tree_census(void) { |
1196 clearTreeCensusClosure<Chunk_t, FreeList_t> ctc; |
1198 clearTreeCensusClosure<Chunk_t, FreeList_t> ctc; |
1250 fl->print_on(gclog_or_tty); |
1252 fl->print_on(gclog_or_tty); |
1251 _total_free += fl->count() * fl->size() ; |
1253 _total_free += fl->count() * fl->size() ; |
1252 total()->set_count( total()->count() + fl->count() ); |
1254 total()->set_count( total()->count() + fl->count() ); |
1253 } |
1255 } |
1254 |
1256 |
1255 #ifndef SERIALGC |
1257 #if INCLUDE_ALL_GCS |
1256 void do_list(AdaptiveFreeList<Chunk_t>* fl) { |
1258 void do_list(AdaptiveFreeList<Chunk_t>* fl) { |
1257 if (++_print_line >= 40) { |
1259 if (++_print_line >= 40) { |
1258 FreeList_t<Chunk_t>::print_labels_on(gclog_or_tty, "size"); |
1260 FreeList_t<Chunk_t>::print_labels_on(gclog_or_tty, "size"); |
1259 _print_line = 0; |
1261 _print_line = 0; |
1260 } |
1262 } |
1269 total()->set_coal_births( total()->coal_births() + fl->coal_births() ); |
1271 total()->set_coal_births( total()->coal_births() + fl->coal_births() ); |
1270 total()->set_coal_deaths( total()->coal_deaths() + fl->coal_deaths() ); |
1272 total()->set_coal_deaths( total()->coal_deaths() + fl->coal_deaths() ); |
1271 total()->set_split_births(total()->split_births() + fl->split_births()); |
1273 total()->set_split_births(total()->split_births() + fl->split_births()); |
1272 total()->set_split_deaths(total()->split_deaths() + fl->split_deaths()); |
1274 total()->set_split_deaths(total()->split_deaths() + fl->split_deaths()); |
1273 } |
1275 } |
1274 #endif // SERIALGC |
1276 #endif // INCLUDE_ALL_GCS |
1275 }; |
1277 }; |
1276 |
1278 |
1277 template <class Chunk_t, template <class> class FreeList_t> |
1279 template <class Chunk_t, template <class> class FreeList_t> |
1278 void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_dict_census(void) const { |
1280 void BinaryTreeDictionary<Chunk_t, FreeList_t>::print_dict_census(void) const { |
1279 |
1281 |
1284 |
1286 |
1285 FreeList_t<Chunk_t>* total = ptc.total(); |
1287 FreeList_t<Chunk_t>* total = ptc.total(); |
1286 FreeList_t<Chunk_t>::print_labels_on(gclog_or_tty, " "); |
1288 FreeList_t<Chunk_t>::print_labels_on(gclog_or_tty, " "); |
1287 } |
1289 } |
1288 |
1290 |
1289 #ifndef SERIALGC |
1291 #if INCLUDE_ALL_GCS |
1290 template <> |
1292 template <> |
1291 void AFLBinaryTreeDictionary::print_dict_census(void) const { |
1293 void AFLBinaryTreeDictionary::print_dict_census(void) const { |
1292 |
1294 |
1293 gclog_or_tty->print("\nBinaryTree\n"); |
1295 gclog_or_tty->print("\nBinaryTree\n"); |
1294 AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, "size"); |
1296 AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, "size"); |
1306 - total->split_deaths() - total->coal_deaths()) |
1308 - total->split_deaths() - total->coal_deaths()) |
1307 /(total->prev_sweep() != 0 ? (double)total->prev_sweep() : 1.0), |
1309 /(total->prev_sweep() != 0 ? (double)total->prev_sweep() : 1.0), |
1308 (double)(total->desired() - total->count()) |
1310 (double)(total->desired() - total->count()) |
1309 /(total->desired() != 0 ? (double)total->desired() : 1.0)); |
1311 /(total->desired() != 0 ? (double)total->desired() : 1.0)); |
1310 } |
1312 } |
1311 #endif // SERIALGC |
1313 #endif // INCLUDE_ALL_GCS |
1312 |
1314 |
1313 template <class Chunk_t, template <class> class FreeList_t> |
1315 template <class Chunk_t, template <class> class FreeList_t> |
1314 class PrintFreeListsClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { |
1316 class PrintFreeListsClosure : public AscendTreeCensusClosure<Chunk_t, FreeList_t> { |
1315 outputStream* _st; |
1317 outputStream* _st; |
1316 int _print_line; |
1318 int _print_line; |
1412 template class TreeList<Metachunk, FreeList>; |
1414 template class TreeList<Metachunk, FreeList>; |
1413 template class BinaryTreeDictionary<Metachunk, FreeList>; |
1415 template class BinaryTreeDictionary<Metachunk, FreeList>; |
1414 template class TreeChunk<Metachunk, FreeList>; |
1416 template class TreeChunk<Metachunk, FreeList>; |
1415 |
1417 |
1416 |
1418 |
1417 #ifndef SERIALGC |
1419 #if INCLUDE_ALL_GCS |
1418 // Explicitly instantiate these types for FreeChunk. |
1420 // Explicitly instantiate these types for FreeChunk. |
1419 template class TreeList<FreeChunk, AdaptiveFreeList>; |
1421 template class TreeList<FreeChunk, AdaptiveFreeList>; |
1420 template class BinaryTreeDictionary<FreeChunk, AdaptiveFreeList>; |
1422 template class BinaryTreeDictionary<FreeChunk, AdaptiveFreeList>; |
1421 template class TreeChunk<FreeChunk, AdaptiveFreeList>; |
1423 template class TreeChunk<FreeChunk, AdaptiveFreeList>; |
1422 |
1424 |
1423 #endif // SERIALGC |
1425 #endif // INCLUDE_ALL_GCS |