44 #include "utilities/quickSort.hpp"

   230 class G1RefineBufferedCards : public StackObj {

   231   BufferNode* const _node;

   232   CardTable::CardValue** const _node_buffer;

   233   const size_t _node_buffer_size;

   234   const uint _worker_id;

   235   size_t* _total_refined_cards;

   236   G1RemSet* const _g1rs;

   237 

   238   static inline int compare_card(const CardTable::CardValue* p1,

   239                                  const CardTable::CardValue* p2) {

   240     return p2 - p1;

   241   }

   242 

   243   // Sorts the cards from start_index to _node_buffer_size in *decreasing*

   244   // address order. Tests showed that this order is preferable to not sorting

   245   // or increasing address order.

   246   void sort_cards(size_t start_index) {

   247     QuickSort::sort(&_node_buffer[start_index],

   248                     _node_buffer_size - start_index,

   249                     compare_card,

   250                     false);

   251   }

   252 

   253   // Returns the index to the first clean card in the buffer.

   254   size_t clean_cards() {

   255     const size_t start = _node->index();

   256     assert(start <= _node_buffer_size, "invariant");

   257 

   258     // Two-fingered compaction algorithm similar to the filtering mechanism in

   259     // SATBMarkQueue. The main difference is that clean_card_before_refine()

   260     // could change the buffer element in-place.

   261     // We don't check for SuspendibleThreadSet::should_yield(), because

   262     // cleaning and redirtying the cards is fast.

   263     CardTable::CardValue** src = &_node_buffer[start];

   264     CardTable::CardValue** dst = &_node_buffer[_node_buffer_size];

   265     assert(src <= dst, "invariant");

   266     for ( ; src < dst; ++src) {

   267       // Search low to high for a card to keep.

   268       if (_g1rs->clean_card_before_refine(src)) {

   269         // Found keeper.  Search high to low for a card to discard.

   270         while (src < --dst) {

   271           if (!_g1rs->clean_card_before_refine(dst)) {

   272             *dst = *src;         // Replace discard with keeper.

   273             break;

   274           }

   275         }

   276         // If discard search failed (src == dst), the outer loop will also end.

   277       }

   278     }

   279 

   280     // dst points to the first retained clean card, or the end of the buffer

   281     // if all the cards were discarded.

   282     const size_t first_clean = dst - _node_buffer;

   283     assert(first_clean >= start && first_clean <= _node_buffer_size, "invariant");

   284     // Discarded cards are considered as refined.

   285     *_total_refined_cards += first_clean - start;

   286     return first_clean;

   287   }

   288 

   289   bool refine_cleaned_cards(size_t start_index) {

   290     bool result = true;

   291     size_t i = start_index;

   292     for ( ; i < _node_buffer_size; ++i) {

   293       if (SuspendibleThreadSet::should_yield()) {

   294         redirty_unrefined_cards(i);

   295         result = false;

   296         break;

   297       }

   298       _g1rs->refine_card_concurrently(_node_buffer[i], _worker_id);

   299     }

   300     _node->set_index(i);

   301     *_total_refined_cards += i - start_index;

   302     return result;

   303   }

   304 

   305   void redirty_unrefined_cards(size_t start) {

   306     for ( ; start < _node_buffer_size; ++start) {

   307       *_node_buffer[start] = G1CardTable::dirty_card_val();

   308     }

   309   }

   310 

   311 public:

   312   G1RefineBufferedCards(BufferNode* node,

   313                         size_t node_buffer_size,

   314                         uint worker_id,

   315                         size_t* total_refined_cards) :

   316     _node(node),

   317     _node_buffer(reinterpret_cast<CardTable::CardValue**>(BufferNode::make_buffer_from_node(node))),

   318     _node_buffer_size(node_buffer_size),

   319     _worker_id(worker_id),

   320     _total_refined_cards(total_refined_cards),

   321     _g1rs(G1CollectedHeap::heap()->rem_set()) {}

   322 

   323   bool refine() {

   324     size_t first_clean_index = clean_cards();

   325     if (first_clean_index == _node_buffer_size) {

   326       _node->set_index(first_clean_index);

   327       return true;

   328     }

   329     // This fence serves two purposes. First, the cards must be cleaned

   330     // before processing the contents. Second, we can't proceed with

   331     // processing a region until after the read of the region's top in

   332     // collect_and_clean_cards(), for synchronization with possibly concurrent

   333     // humongous object allocation (see comment at the StoreStore fence before

   334     // setting the regions' tops in humongous allocation path).

   335     // It's okay that reading region's top and reading region's type were racy

   336     // wrto each other. We need both set, in any order, to proceed.

   337     OrderAccess::fence();

   338     sort_cards(first_clean_index);

   339     return refine_cleaned_cards(first_clean_index);

   340   }

   341 };

   342