< prev index next >

src/share/vm/memory/binaryTreeDictionary.cpp

Print this page
rev 13203 : [mq]: freebldict
rev 13204 : imported patch dither
rev 13205 : imported patch copyyear
   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;


< prev index next >