1 /*
   2  * Copyright (c) 2001, 2019, 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/g1/g1BufferNodeList.hpp"
  27 #include "gc/g1/g1CardTableEntryClosure.hpp"
  28 #include "gc/g1/g1CollectedHeap.inline.hpp"
  29 #include "gc/g1/g1DirtyCardQueue.hpp"
  30 #include "gc/g1/g1FreeIdSet.hpp"
  31 #include "gc/g1/g1RedirtyCardsQueue.hpp"
  32 #include "gc/g1/g1RemSet.hpp"
  33 #include "gc/g1/g1ThreadLocalData.hpp"
  34 #include "gc/g1/heapRegionRemSet.hpp"
  35 #include "gc/shared/suspendibleThreadSet.hpp"
  36 #include "gc/shared/workgroup.hpp"
  37 #include "runtime/atomic.hpp"
  38 #include "runtime/flags/flagSetting.hpp"
  39 #include "runtime/mutexLocker.hpp"
  40 #include "runtime/safepoint.hpp"
  41 #include "runtime/thread.inline.hpp"
  42 #include "runtime/threadSMR.hpp"
  43 
  44 // Closure used for updating remembered sets and recording references that
  45 // point into the collection set while the mutator is running.
  46 // Assumed to be only executed concurrently with the mutator. Yields via
  47 // SuspendibleThreadSet after every card.
  48 class G1RefineCardConcurrentlyClosure: public G1CardTableEntryClosure {
  49 public:
  50   bool do_card_ptr(CardValue* card_ptr, uint worker_i) {
  51     G1CollectedHeap::heap()->rem_set()->refine_card_concurrently(card_ptr, worker_i);
  52 
  53     if (SuspendibleThreadSet::should_yield()) {
  54       // Caller will actually yield.
  55       return false;
  56     }
  57     // Otherwise, we finished successfully; return true.
  58     return true;
  59   }
  60 };
  61 
  62 G1DirtyCardQueue::G1DirtyCardQueue(G1DirtyCardQueueSet* qset) :
  63   // Dirty card queues are always active, so we create them with their
  64   // active field set to true.
  65   PtrQueue(qset, true /* active */)
  66 { }
  67 
  68 G1DirtyCardQueue::~G1DirtyCardQueue() {
  69   flush();
  70 }
  71 
  72 void G1DirtyCardQueue::handle_completed_buffer() {
  73   assert(_buf != NULL, "precondition");
  74   BufferNode* node = BufferNode::make_node_from_buffer(_buf, index());
  75   G1DirtyCardQueueSet* dcqs = dirty_card_qset();
  76   if (dcqs->process_or_enqueue_completed_buffer(node)) {
  77     reset();                    // Buffer fully processed, reset index.
  78   } else {
  79     allocate_buffer();          // Buffer enqueued, get a new one.
  80   }
  81 }
  82 
  83 G1DirtyCardQueueSet::G1DirtyCardQueueSet() :
  84   PtrQueueSet(),
  85   _cbl_mon(NULL),
  86   _completed_buffers_head(NULL),
  87   _completed_buffers_tail(NULL),
  88   _num_cards(0),
  89   _process_cards_threshold(ProcessCardsThresholdNever),
  90   _process_completed_buffers(false),
  91   _max_cards(MaxCardsUnlimited),
  92   _max_cards_padding(0),
  93   _free_ids(0, num_par_ids()),
  94   _processed_buffers_mut(0),
  95   _processed_buffers_rs_thread(0)
  96 {
  97   _all_active = true;
  98 }
  99 
 100 G1DirtyCardQueueSet::~G1DirtyCardQueueSet() {
 101   abandon_completed_buffers();
 102 }
 103 
 104 // Determines how many mutator threads can process the buffers in parallel.
 105 uint G1DirtyCardQueueSet::num_par_ids() {
 106   return (uint)os::initial_active_processor_count();
 107 }
 108 
 109 void G1DirtyCardQueueSet::initialize(Monitor* cbl_mon,
 110                                      BufferNode::Allocator* allocator) {
 111   PtrQueueSet::initialize(allocator);
 112   assert(_cbl_mon == NULL, "Init order issue?");
 113   _cbl_mon = cbl_mon;
 114 }
 115 
 116 void G1DirtyCardQueueSet::handle_zero_index_for_thread(Thread* t) {
 117   G1ThreadLocalData::dirty_card_queue(t).handle_zero_index();
 118 }
 119 
 120 void G1DirtyCardQueueSet::enqueue_completed_buffer(BufferNode* cbn) {
 121   MonitorLocker ml(_cbl_mon, Mutex::_no_safepoint_check_flag);
 122   cbn->set_next(NULL);
 123   if (_completed_buffers_tail == NULL) {
 124     assert(_completed_buffers_head == NULL, "Well-formedness");
 125     _completed_buffers_head = cbn;
 126     _completed_buffers_tail = cbn;
 127   } else {
 128     _completed_buffers_tail->set_next(cbn);
 129     _completed_buffers_tail = cbn;
 130   }
 131   _num_cards += buffer_size() - cbn->index();
 132 
 133   if (!process_completed_buffers() &&
 134       (num_cards() > process_cards_threshold())) {
 135     set_process_completed_buffers(true);
 136     ml.notify_all();
 137   }
 138   verify_num_cards();
 139 }
 140 
 141 BufferNode* G1DirtyCardQueueSet::get_completed_buffer(size_t stop_at) {
 142   MutexLocker x(_cbl_mon, Mutex::_no_safepoint_check_flag);
 143 
 144   if (num_cards() <= stop_at) {
 145     return NULL;
 146   }
 147 
 148   assert(num_cards() > 0, "invariant");
 149   assert(_completed_buffers_head != NULL, "invariant");
 150   assert(_completed_buffers_tail != NULL, "invariant");
 151 
 152   BufferNode* bn = _completed_buffers_head;
 153   _num_cards -= buffer_size() - bn->index();
 154   _completed_buffers_head = bn->next();
 155   if (_completed_buffers_head == NULL) {
 156     assert(num_cards() == 0, "invariant");
 157     _completed_buffers_tail = NULL;
 158     set_process_completed_buffers(false);
 159   }
 160   verify_num_cards();
 161   bn->set_next(NULL);
 162   return bn;
 163 }
 164 
 165 #ifdef ASSERT
 166 void G1DirtyCardQueueSet::verify_num_cards() const {
 167   size_t actual = 0;
 168   BufferNode* cur = _completed_buffers_head;
 169   while (cur != NULL) {
 170     actual += buffer_size() - cur->index();
 171     cur = cur->next();
 172   }
 173   assert(actual == _num_cards,
 174          "Num entries in completed buffers should be " SIZE_FORMAT " but are " SIZE_FORMAT,
 175          _num_cards, actual);
 176 }
 177 #endif
 178 
 179 void G1DirtyCardQueueSet::abandon_completed_buffers() {
 180   BufferNode* buffers_to_delete = NULL;
 181   {
 182     MutexLocker x(_cbl_mon, Mutex::_no_safepoint_check_flag);
 183     buffers_to_delete = _completed_buffers_head;
 184     _completed_buffers_head = NULL;
 185     _completed_buffers_tail = NULL;
 186     _num_cards = 0;
 187     set_process_completed_buffers(false);
 188   }
 189   while (buffers_to_delete != NULL) {
 190     BufferNode* bn = buffers_to_delete;
 191     buffers_to_delete = bn->next();
 192     bn->set_next(NULL);
 193     deallocate_buffer(bn);
 194   }
 195 }
 196 
 197 void G1DirtyCardQueueSet::notify_if_necessary() {
 198   MonitorLocker ml(_cbl_mon, Mutex::_no_safepoint_check_flag);
 199   if (num_cards() > process_cards_threshold()) {
 200     set_process_completed_buffers(true);
 201     ml.notify_all();
 202   }
 203 }
 204 
 205 // Merge lists of buffers. Notify the processing threads.
 206 // The source queue is emptied as a result. The queues
 207 // must share the monitor.
 208 void G1DirtyCardQueueSet::merge_bufferlists(G1RedirtyCardsQueueSet* src) {
 209   assert(allocator() == src->allocator(), "precondition");
 210   const G1BufferNodeList from = src->take_all_completed_buffers();
 211   if (from._head == NULL) return;
 212 
 213   MutexLocker x(_cbl_mon, Mutex::_no_safepoint_check_flag);
 214   if (_completed_buffers_tail == NULL) {
 215     assert(_completed_buffers_head == NULL, "Well-formedness");
 216     _completed_buffers_head = from._head;
 217     _completed_buffers_tail = from._tail;
 218   } else {
 219     assert(_completed_buffers_head != NULL, "Well formedness");
 220     _completed_buffers_tail->set_next(from._head);
 221     _completed_buffers_tail = from._tail;
 222   }
 223   _num_cards += from._entry_count;
 224 
 225   assert(_completed_buffers_head == NULL && _completed_buffers_tail == NULL ||
 226          _completed_buffers_head != NULL && _completed_buffers_tail != NULL,
 227          "Sanity");
 228   verify_num_cards();
 229 }
 230 
 231 bool G1DirtyCardQueueSet::apply_closure_to_buffer(G1CardTableEntryClosure* cl,
 232                                                   BufferNode* node,
 233                                                   uint worker_i) {
 234   if (cl == NULL) return true;
 235   bool result = true;
 236   void** buf = BufferNode::make_buffer_from_node(node);
 237   size_t i = node->index();
 238   size_t limit = buffer_size();
 239   for ( ; i < limit; ++i) {
 240     CardTable::CardValue* card_ptr = static_cast<CardTable::CardValue*>(buf[i]);
 241     assert(card_ptr != NULL, "invariant");
 242     if (!cl->do_card_ptr(card_ptr, worker_i)) {
 243       result = false;           // Incomplete processing.
 244       break;
 245     }
 246   }
 247   assert(i <= buffer_size(), "invariant");
 248   node->set_index(i);
 249   return result;
 250 }
 251 
 252 #ifndef ASSERT
 253 #define assert_fully_consumed(node, buffer_size)
 254 #else
 255 #define assert_fully_consumed(node, buffer_size)                \
 256   do {                                                          \
 257     size_t _afc_index = (node)->index();                        \
 258     size_t _afc_size = (buffer_size);                           \
 259     assert(_afc_index == _afc_size,                             \
 260            "Buffer was not fully consumed as claimed: index: "  \
 261            SIZE_FORMAT ", size: " SIZE_FORMAT,                  \
 262             _afc_index, _afc_size);                             \
 263   } while (0)
 264 #endif // ASSERT
 265 
 266 bool G1DirtyCardQueueSet::process_or_enqueue_completed_buffer(BufferNode* node) {
 267   if (Thread::current()->is_Java_thread()) {
 268     // If the number of buffers exceeds the limit, make this Java
 269     // thread do the processing itself.  We don't lock to access
 270     // buffer count or padding; it is fine to be imprecise here.  The
 271     // add of padding could overflow, which is treated as unlimited.
 272     size_t limit = max_cards() + max_cards_padding();
 273     if ((num_cards() > limit) && (limit >= max_cards())) {
 274       if (mut_process_buffer(node)) {
 275         return true;
 276       }
 277     }
 278   }
 279   enqueue_completed_buffer(node);
 280   return false;
 281 }
 282 
 283 bool G1DirtyCardQueueSet::mut_process_buffer(BufferNode* node) {
 284   uint worker_id = _free_ids.claim_par_id(); // temporarily claim an id
 285   G1RefineCardConcurrentlyClosure cl;
 286   bool result = apply_closure_to_buffer(&cl, node, worker_id);
 287   _free_ids.release_par_id(worker_id); // release the id
 288 
 289   if (result) {
 290     assert_fully_consumed(node, buffer_size());
 291     Atomic::inc(&_processed_buffers_mut);
 292   }
 293   return result;
 294 }
 295 
 296 bool G1DirtyCardQueueSet::refine_completed_buffer_concurrently(uint worker_i, size_t stop_at) {
 297   G1RefineCardConcurrentlyClosure cl;
 298   return apply_closure_to_completed_buffer(&cl, worker_i, stop_at, false);
 299 }
 300 
 301 bool G1DirtyCardQueueSet::apply_closure_during_gc(G1CardTableEntryClosure* cl, uint worker_i) {
 302   assert_at_safepoint();
 303   return apply_closure_to_completed_buffer(cl, worker_i, 0, true);
 304 }
 305 
 306 bool G1DirtyCardQueueSet::apply_closure_to_completed_buffer(G1CardTableEntryClosure* cl,
 307                                                             uint worker_i,
 308                                                             size_t stop_at,
 309                                                             bool during_pause) {
 310   assert(!during_pause || stop_at == 0, "Should not leave any completed buffers during a pause");
 311   BufferNode* nd = get_completed_buffer(stop_at);
 312   if (nd == NULL) {
 313     return false;
 314   } else {
 315     if (apply_closure_to_buffer(cl, nd, worker_i)) {
 316       assert_fully_consumed(nd, buffer_size());
 317       // Done with fully processed buffer.
 318       deallocate_buffer(nd);
 319       Atomic::inc(&_processed_buffers_rs_thread);
 320     } else {
 321       // Return partially processed buffer to the queue.
 322       guarantee(!during_pause, "Should never stop early");
 323       enqueue_completed_buffer(nd);
 324     }
 325     return true;
 326   }
 327 }
 328 
 329 void G1DirtyCardQueueSet::abandon_logs() {
 330   assert(SafepointSynchronize::is_at_safepoint(), "Must be at safepoint.");
 331   abandon_completed_buffers();
 332 
 333   // Since abandon is done only at safepoints, we can safely manipulate
 334   // these queues.
 335   struct AbandonThreadLogClosure : public ThreadClosure {
 336     virtual void do_thread(Thread* t) {
 337       G1ThreadLocalData::dirty_card_queue(t).reset();
 338     }
 339   } closure;
 340   Threads::threads_do(&closure);
 341 
 342   G1BarrierSet::shared_dirty_card_queue().reset();
 343 }
 344 
 345 void G1DirtyCardQueueSet::concatenate_logs() {
 346   // Iterate over all the threads, if we find a partial log add it to
 347   // the global list of logs.  Temporarily turn off the limit on the number
 348   // of outstanding buffers.
 349   assert(SafepointSynchronize::is_at_safepoint(), "Must be at safepoint.");
 350   size_t old_limit = max_cards();
 351   set_max_cards(MaxCardsUnlimited);
 352 
 353   struct ConcatenateThreadLogClosure : public ThreadClosure {
 354     virtual void do_thread(Thread* t) {
 355       G1DirtyCardQueue& dcq = G1ThreadLocalData::dirty_card_queue(t);
 356       if (!dcq.is_empty()) {
 357         dcq.flush();
 358       }
 359     }
 360   } closure;
 361   Threads::threads_do(&closure);
 362 
 363   G1BarrierSet::shared_dirty_card_queue().flush();
 364   set_max_cards(old_limit);
 365 }