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(bool notify_when_complete) :
  84   PtrQueueSet(),
  85   _cbl_mon(NULL),
  86   _completed_buffers_head(NULL),
  87   _completed_buffers_tail(NULL),
  88   _num_entries_in_completed_buffers(0),
  89   _process_completed_buffers_threshold(ProcessCompletedBuffersThresholdNever),
  90   _process_completed_buffers(false),
  91   _notify_when_complete(notify_when_complete),
  92   _max_completed_buffers(MaxCompletedBuffersUnlimited),
  93   _completed_buffers_padding(0),
  94   _free_ids(new G1FreeIdSet(0, num_par_ids())),
  95   _processed_buffers_mut(0),
  96   _processed_buffers_rs_thread(0)
  97 {
  98   _all_active = true;
  99 }
 100 
 101 G1DirtyCardQueueSet::~G1DirtyCardQueueSet() {
 102   abandon_completed_buffers();
 103   delete _free_ids;
 104 }
 105 
 106 // Determines how many mutator threads can process the buffers in parallel.
 107 uint G1DirtyCardQueueSet::num_par_ids() {
 108   return (uint)os::initial_active_processor_count();
 109 }
 110 
 111 void G1DirtyCardQueueSet::initialize(Monitor* cbl_mon,
 112                                      BufferNode::Allocator* allocator) {
 113   PtrQueueSet::initialize(allocator);
 114   assert(_cbl_mon == NULL, "Init order issue?");
 115   _cbl_mon = cbl_mon;
 116 }
 117 
 118 void G1DirtyCardQueueSet::handle_zero_index_for_thread(Thread* t) {
 119   G1ThreadLocalData::dirty_card_queue(t).handle_zero_index();
 120 }
 121 
 122 void G1DirtyCardQueueSet::enqueue_completed_buffer(BufferNode* cbn) {
 123   MutexLocker x(_cbl_mon, Mutex::_no_safepoint_check_flag);
 124   cbn->set_next(NULL);
 125   if (_completed_buffers_tail == NULL) {
 126     assert(_completed_buffers_head == NULL, "Well-formedness");
 127     _completed_buffers_head = cbn;
 128     _completed_buffers_tail = cbn;
 129   } else {
 130     _completed_buffers_tail->set_next(cbn);
 131     _completed_buffers_tail = cbn;
 132   }
 133   _num_entries_in_completed_buffers += buffer_size() - cbn->index();
 134 
 135   if (!process_completed_buffers() &&
 136       (num_completed_buffers() > process_completed_buffers_threshold())) {
 137     set_process_completed_buffers(true);
 138     if (_notify_when_complete) {
 139       _cbl_mon->notify_all();
 140     }
 141   }
 142   verify_num_entries_in_completed_buffers();
 143 }
 144 
 145 BufferNode* G1DirtyCardQueueSet::get_completed_buffer(size_t stop_at) {
 146   MutexLocker x(_cbl_mon, Mutex::_no_safepoint_check_flag);
 147 
 148   if (num_completed_buffers() <= stop_at) {
 149     return NULL;
 150   }
 151 
 152   assert(num_completed_buffers() > 0, "invariant");
 153   assert(_completed_buffers_head != NULL, "invariant");
 154   assert(_completed_buffers_tail != NULL, "invariant");
 155 
 156   BufferNode* bn = _completed_buffers_head;
 157   _num_entries_in_completed_buffers -= buffer_size() - bn->index();
 158   _completed_buffers_head = bn->next();
 159   if (_completed_buffers_head == NULL) {
 160     assert(num_completed_buffers() == 0, "invariant");
 161     _completed_buffers_tail = NULL;
 162     set_process_completed_buffers(false);
 163   }
 164   verify_num_entries_in_completed_buffers();
 165   bn->set_next(NULL);
 166   return bn;
 167 }
 168 
 169 #ifdef ASSERT
 170 void G1DirtyCardQueueSet::verify_num_entries_in_completed_buffers() const {
 171   size_t actual = 0;
 172   BufferNode* cur = _completed_buffers_head;
 173   while (cur != NULL) {
 174     actual += buffer_size() - cur->index();
 175     cur = cur->next();
 176   }
 177   assert(actual == _num_entries_in_completed_buffers,
 178          "Num entries in completed buffers should be " SIZE_FORMAT " but are " SIZE_FORMAT,
 179          _num_entries_in_completed_buffers, actual);
 180 }
 181 #endif
 182 
 183 void G1DirtyCardQueueSet::abandon_completed_buffers() {
 184   BufferNode* buffers_to_delete = NULL;
 185   {
 186     MutexLocker x(_cbl_mon, Mutex::_no_safepoint_check_flag);
 187     buffers_to_delete = _completed_buffers_head;
 188     _completed_buffers_head = NULL;
 189     _completed_buffers_tail = NULL;
 190     _num_entries_in_completed_buffers = 0;
 191     set_process_completed_buffers(false);
 192   }
 193   while (buffers_to_delete != NULL) {
 194     BufferNode* bn = buffers_to_delete;
 195     buffers_to_delete = bn->next();
 196     bn->set_next(NULL);
 197     deallocate_buffer(bn);
 198   }
 199 }
 200 
 201 void G1DirtyCardQueueSet::notify_if_necessary() {
 202   MutexLocker x(_cbl_mon, Mutex::_no_safepoint_check_flag);
 203   if (num_completed_buffers() > process_completed_buffers_threshold()) {
 204     set_process_completed_buffers(true);
 205     if (_notify_when_complete)
 206       _cbl_mon->notify();
 207   }
 208 }
 209 
 210 // Merge lists of buffers. Notify the processing threads.
 211 // The source queue is emptied as a result. The queues
 212 // must share the monitor.
 213 void G1DirtyCardQueueSet::merge_bufferlists(G1RedirtyCardsQueueSet* src) {
 214   assert(allocator() == src->allocator(), "precondition");
 215   const G1BufferNodeList from = src->take_all_completed_buffers();
 216   if (from._head == NULL) return;
 217 
 218   MutexLocker x(_cbl_mon, Mutex::_no_safepoint_check_flag);
 219   if (_completed_buffers_tail == NULL) {
 220     assert(_completed_buffers_head == NULL, "Well-formedness");
 221     _completed_buffers_head = from._head;
 222     _completed_buffers_tail = from._tail;
 223   } else {
 224     assert(_completed_buffers_head != NULL, "Well formedness");
 225     _completed_buffers_tail->set_next(from._head);
 226     _completed_buffers_tail = from._tail;
 227   }
 228   _num_entries_in_completed_buffers += from._entry_count;
 229 
 230   assert(_completed_buffers_head == NULL && _completed_buffers_tail == NULL ||
 231          _completed_buffers_head != NULL && _completed_buffers_tail != NULL,
 232          "Sanity");
 233   verify_num_entries_in_completed_buffers();
 234 }
 235 
 236 bool G1DirtyCardQueueSet::apply_closure_to_buffer(G1CardTableEntryClosure* cl,
 237                                                   BufferNode* node,
 238                                                   uint worker_i) {
 239   if (cl == NULL) return true;
 240   bool result = true;
 241   void** buf = BufferNode::make_buffer_from_node(node);
 242   size_t i = node->index();
 243   size_t limit = buffer_size();
 244   for ( ; i < limit; ++i) {
 245     CardTable::CardValue* card_ptr = static_cast<CardTable::CardValue*>(buf[i]);
 246     assert(card_ptr != NULL, "invariant");
 247     if (!cl->do_card_ptr(card_ptr, worker_i)) {
 248       result = false;           // Incomplete processing.
 249       break;
 250     }
 251   }
 252   assert(i <= buffer_size(), "invariant");
 253   node->set_index(i);
 254   return result;
 255 }
 256 
 257 #ifndef ASSERT
 258 #define assert_fully_consumed(node, buffer_size)
 259 #else
 260 #define assert_fully_consumed(node, buffer_size)                \
 261   do {                                                          \
 262     size_t _afc_index = (node)->index();                        \
 263     size_t _afc_size = (buffer_size);                           \
 264     assert(_afc_index == _afc_size,                             \
 265            "Buffer was not fully consumed as claimed: index: "  \
 266            SIZE_FORMAT ", size: " SIZE_FORMAT,                  \
 267             _afc_index, _afc_size);                             \
 268   } while (0)
 269 #endif // ASSERT
 270 
 271 bool G1DirtyCardQueueSet::process_or_enqueue_completed_buffer(BufferNode* node) {
 272   if (Thread::current()->is_Java_thread()) {
 273     // If the number of buffers exceeds the limit, make this Java
 274     // thread do the processing itself.  We don't lock to access
 275     // buffer count or padding; it is fine to be imprecise here.  The
 276     // add of padding could overflow, which is treated as unlimited.
 277     size_t max_buffers = max_completed_buffers();
 278     size_t limit = max_buffers + completed_buffers_padding();
 279     if ((num_completed_buffers() > limit) && (limit >= max_buffers)) {
 280       if (mut_process_buffer(node)) {
 281         return true;
 282       }
 283     }
 284   }
 285   enqueue_completed_buffer(node);
 286   return false;
 287 }
 288 
 289 bool G1DirtyCardQueueSet::mut_process_buffer(BufferNode* node) {
 290   uint worker_i = _free_ids->claim_par_id(); // temporarily claim an id
 291   G1RefineCardConcurrentlyClosure cl;
 292   bool result = apply_closure_to_buffer(&cl, node, worker_i);
 293   _free_ids->release_par_id(worker_i); // release the id
 294 
 295   if (result) {
 296     assert_fully_consumed(node, buffer_size());
 297     Atomic::inc(&_processed_buffers_mut);
 298   }
 299   return result;
 300 }
 301 
 302 bool G1DirtyCardQueueSet::refine_completed_buffer_concurrently(uint worker_i, size_t stop_at) {
 303   G1RefineCardConcurrentlyClosure cl;
 304   return apply_closure_to_completed_buffer(&cl, worker_i, stop_at, false);
 305 }
 306 
 307 bool G1DirtyCardQueueSet::apply_closure_during_gc(G1CardTableEntryClosure* cl, uint worker_i) {
 308   assert_at_safepoint();
 309   return apply_closure_to_completed_buffer(cl, worker_i, 0, true);
 310 }
 311 
 312 bool G1DirtyCardQueueSet::apply_closure_to_completed_buffer(G1CardTableEntryClosure* cl,
 313                                                             uint worker_i,
 314                                                             size_t stop_at,
 315                                                             bool during_pause) {
 316   assert(!during_pause || stop_at == 0, "Should not leave any completed buffers during a pause");
 317   BufferNode* nd = get_completed_buffer(stop_at);
 318   if (nd == NULL) {
 319     return false;
 320   } else {
 321     if (apply_closure_to_buffer(cl, nd, worker_i)) {
 322       assert_fully_consumed(nd, buffer_size());
 323       // Done with fully processed buffer.
 324       deallocate_buffer(nd);
 325       Atomic::inc(&_processed_buffers_rs_thread);
 326     } else {
 327       // Return partially processed buffer to the queue.
 328       guarantee(!during_pause, "Should never stop early");
 329       enqueue_completed_buffer(nd);
 330     }
 331     return true;
 332   }
 333 }
 334 
 335 void G1DirtyCardQueueSet::abandon_logs() {
 336   assert(SafepointSynchronize::is_at_safepoint(), "Must be at safepoint.");
 337   abandon_completed_buffers();
 338 
 339   // Since abandon is done only at safepoints, we can safely manipulate
 340   // these queues.
 341   struct AbandonThreadLogClosure : public ThreadClosure {
 342     virtual void do_thread(Thread* t) {
 343       G1ThreadLocalData::dirty_card_queue(t).reset();
 344     }
 345   } closure;
 346   Threads::threads_do(&closure);
 347 
 348   G1BarrierSet::shared_dirty_card_queue().reset();
 349 }
 350 
 351 void G1DirtyCardQueueSet::concatenate_logs() {
 352   // Iterate over all the threads, if we find a partial log add it to
 353   // the global list of logs.  Temporarily turn off the limit on the number
 354   // of outstanding buffers.
 355   assert(SafepointSynchronize::is_at_safepoint(), "Must be at safepoint.");
 356   size_t old_limit = max_completed_buffers();
 357   set_max_completed_buffers(MaxCompletedBuffersUnlimited);
 358 
 359   struct ConcatenateThreadLogClosure : public ThreadClosure {
 360     virtual void do_thread(Thread* t) {
 361       G1DirtyCardQueue& dcq = G1ThreadLocalData::dirty_card_queue(t);
 362       if (!dcq.is_empty()) {
 363         dcq.flush();
 364       }
 365     }
 366   } closure;
 367   Threads::threads_do(&closure);
 368 
 369   G1BarrierSet::shared_dirty_card_queue().flush();
 370   set_max_completed_buffers(old_limit);
 371 }