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/g1/dirtyCardQueue.hpp"
  27 #include "gc/g1/g1BarrierSet.hpp"
  28 #include "gc/g1/g1CollectedHeap.inline.hpp"
  29 #include "gc/g1/heapRegionRemSet.hpp"
  30 #include "gc/shared/workgroup.hpp"
  31 #include "runtime/atomic.hpp"
  32 #include "runtime/mutexLocker.hpp"
  33 #include "runtime/safepoint.hpp"
  34 #include "runtime/thread.inline.hpp"
  35 
  36 // Represents a set of free small integer ids.
  37 class FreeIdSet : public CHeapObj<mtGC> {
  38   enum {
  39     end_of_list = UINT_MAX,
  40     claimed = UINT_MAX - 1
  41   };
  42 
  43   uint _size;
  44   Monitor* _mon;
  45 
  46   uint* _ids;
  47   uint _hd;
  48   uint _waiters;
  49   uint _claimed;
  50 
  51 public:
  52   FreeIdSet(uint size, Monitor* mon);
  53   ~FreeIdSet();
  54 
  55   // Returns an unclaimed parallel id (waiting for one to be released if
  56   // necessary).
  57   uint claim_par_id();
  58 
  59   void release_par_id(uint id);
  60 };
  61 
  62 FreeIdSet::FreeIdSet(uint size, Monitor* mon) :
  63   _size(size), _mon(mon), _hd(0), _waiters(0), _claimed(0)
  64 {
  65   guarantee(size != 0, "must be");
  66   _ids = NEW_C_HEAP_ARRAY(uint, size, mtGC);
  67   for (uint i = 0; i < size - 1; i++) {
  68     _ids[i] = i+1;
  69   }
  70   _ids[size-1] = end_of_list; // end of list.
  71 }
  72 
  73 FreeIdSet::~FreeIdSet() {
  74   FREE_C_HEAP_ARRAY(uint, _ids);
  75 }
  76 
  77 uint FreeIdSet::claim_par_id() {
  78   MutexLockerEx x(_mon, Mutex::_no_safepoint_check_flag);
  79   while (_hd == end_of_list) {
  80     _waiters++;
  81     _mon->wait(Mutex::_no_safepoint_check_flag);
  82     _waiters--;
  83   }
  84   uint res = _hd;
  85   _hd = _ids[res];
  86   _ids[res] = claimed;  // For debugging.
  87   _claimed++;
  88   return res;
  89 }
  90 
  91 void FreeIdSet::release_par_id(uint id) {
  92   MutexLockerEx x(_mon, Mutex::_no_safepoint_check_flag);
  93   assert(_ids[id] == claimed, "Precondition.");
  94   _ids[id] = _hd;
  95   _hd = id;
  96   _claimed--;
  97   if (_waiters > 0) {
  98     _mon->notify_all();
  99   }
 100 }
 101 
 102 DirtyCardQueue::DirtyCardQueue(DirtyCardQueueSet* dcqs, bool permanent) :
 103   // Dirty card queues are always active, so we create them with their
 104   // active field set to true.
 105   PtrQueue(dcqs != NULL ? dcqs : &G1BarrierSet::dirty_card_queue_set(), permanent, true /* active */)
 106 { }
 107 
 108 DirtyCardQueue::~DirtyCardQueue() {
 109   if (!is_permanent()) {
 110     flush();
 111   }
 112 }
 113 
 114 DirtyCardQueueSet::DirtyCardQueueSet(bool notify_when_complete) :
 115   PtrQueueSet(notify_when_complete),
 116   _mut_process_closure(NULL),
 117   _shared_dirty_card_queue(this, true /* permanent */),
 118   _free_ids(NULL),
 119   _processed_buffers_mut(0), _processed_buffers_rs_thread(0)
 120 {
 121   _all_active = true;
 122 }
 123 
 124 // Determines how many mutator threads can process the buffers in parallel.
 125 uint DirtyCardQueueSet::num_par_ids() {
 126   return (uint)os::initial_active_processor_count();
 127 }
 128 
 129 void DirtyCardQueueSet::initialize(CardTableEntryClosure* cl,
 130                                    Monitor* cbl_mon,
 131                                    Mutex* fl_lock,
 132                                    int process_completed_threshold,
 133                                    int max_completed_queue,
 134                                    Mutex* lock,
 135                                    DirtyCardQueueSet* fl_owner,
 136                                    bool init_free_ids) {
 137   _mut_process_closure = cl;
 138   PtrQueueSet::initialize(cbl_mon,
 139                           fl_lock,
 140                           process_completed_threshold,
 141                           max_completed_queue,
 142                           fl_owner);
 143   set_buffer_size(G1UpdateBufferSize);
 144   _shared_dirty_card_queue.set_lock(lock);
 145   if (init_free_ids) {
 146     _free_ids = new FreeIdSet(num_par_ids(), _cbl_mon);
 147   }
 148 }
 149 
 150 void DirtyCardQueueSet::handle_zero_index_for_thread(JavaThread* t) {
 151   t->dirty_card_queue().handle_zero_index();
 152 }
 153 
 154 bool DirtyCardQueueSet::apply_closure_to_buffer(CardTableEntryClosure* cl,
 155                                                 BufferNode* node,
 156                                                 bool consume,
 157                                                 uint worker_i) {
 158   if (cl == NULL) return true;
 159   bool result = true;
 160   void** buf = BufferNode::make_buffer_from_node(node);
 161   size_t limit = DirtyCardQueue::byte_index_to_index(buffer_size());
 162   size_t i = DirtyCardQueue::byte_index_to_index(node->index());
 163   for ( ; i < limit; ++i) {
 164     jbyte* card_ptr = static_cast<jbyte*>(buf[i]);
 165     assert(card_ptr != NULL, "invariant");
 166     if (!cl->do_card_ptr(card_ptr, worker_i)) {
 167       result = false;           // Incomplete processing.
 168       break;
 169     }
 170   }
 171   if (consume) {
 172     size_t new_index = DirtyCardQueue::index_to_byte_index(i);
 173     assert(new_index <= buffer_size(), "invariant");
 174     node->set_index(new_index);
 175   }
 176   return result;
 177 }
 178 
 179 #ifndef ASSERT
 180 #define assert_fully_consumed(node, buffer_size)
 181 #else
 182 #define assert_fully_consumed(node, buffer_size)                \
 183   do {                                                          \
 184     size_t _afc_index = (node)->index();                        \
 185     size_t _afc_size = (buffer_size);                           \
 186     assert(_afc_index == _afc_size,                             \
 187            "Buffer was not fully consumed as claimed: index: "  \
 188            SIZE_FORMAT ", size: " SIZE_FORMAT,                  \
 189             _afc_index, _afc_size);                             \
 190   } while (0)
 191 #endif // ASSERT
 192 
 193 bool DirtyCardQueueSet::mut_process_buffer(BufferNode* node) {
 194   guarantee(_free_ids != NULL, "must be");
 195 
 196   uint worker_i = _free_ids->claim_par_id(); // temporarily claim an id
 197   bool result = apply_closure_to_buffer(_mut_process_closure, node, true, worker_i);
 198   _free_ids->release_par_id(worker_i); // release the id
 199 
 200   if (result) {
 201     assert_fully_consumed(node, buffer_size());
 202     Atomic::inc(&_processed_buffers_mut);
 203   }
 204   return result;
 205 }
 206 
 207 
 208 BufferNode* DirtyCardQueueSet::get_completed_buffer(size_t stop_at) {
 209   BufferNode* nd = NULL;
 210   MutexLockerEx x(_cbl_mon, Mutex::_no_safepoint_check_flag);
 211 
 212   if (_n_completed_buffers <= stop_at) {
 213     _process_completed = false;
 214     return NULL;
 215   }
 216 
 217   if (_completed_buffers_head != NULL) {
 218     nd = _completed_buffers_head;
 219     assert(_n_completed_buffers > 0, "Invariant");
 220     _completed_buffers_head = nd->next();
 221     _n_completed_buffers--;
 222     if (_completed_buffers_head == NULL) {
 223       assert(_n_completed_buffers == 0, "Invariant");
 224       _completed_buffers_tail = NULL;
 225     }
 226   }
 227   DEBUG_ONLY(assert_completed_buffer_list_len_correct_locked());
 228   return nd;
 229 }
 230 
 231 bool DirtyCardQueueSet::apply_closure_to_completed_buffer(CardTableEntryClosure* cl,
 232                                                           uint worker_i,
 233                                                           size_t stop_at,
 234                                                           bool during_pause) {
 235   assert(!during_pause || stop_at == 0, "Should not leave any completed buffers during a pause");
 236   BufferNode* nd = get_completed_buffer(stop_at);
 237   if (nd == NULL) {
 238     return false;
 239   } else {
 240     if (apply_closure_to_buffer(cl, nd, true, worker_i)) {
 241       assert_fully_consumed(nd, buffer_size());
 242       // Done with fully processed buffer.
 243       deallocate_buffer(nd);
 244       Atomic::inc(&_processed_buffers_rs_thread);
 245     } else {
 246       // Return partially processed buffer to the queue.
 247       guarantee(!during_pause, "Should never stop early");
 248       enqueue_complete_buffer(nd);
 249     }
 250     return true;
 251   }
 252 }
 253 
 254 void DirtyCardQueueSet::par_apply_closure_to_all_completed_buffers(CardTableEntryClosure* cl) {
 255   BufferNode* nd = _cur_par_buffer_node;
 256   while (nd != NULL) {
 257     BufferNode* next = nd->next();
 258     void* actual = Atomic::cmpxchg_ptr(next, &_cur_par_buffer_node, nd);
 259     if (actual == nd) {
 260       bool b = apply_closure_to_buffer(cl, nd, false);
 261       guarantee(b, "Should not stop early.");
 262       nd = next;
 263     } else {
 264       nd = static_cast<BufferNode*>(actual);
 265     }
 266   }
 267 }
 268 
 269 // Deallocates any completed log buffers
 270 void DirtyCardQueueSet::clear() {
 271   BufferNode* buffers_to_delete = NULL;
 272   {
 273     MutexLockerEx x(_cbl_mon, Mutex::_no_safepoint_check_flag);
 274     while (_completed_buffers_head != NULL) {
 275       BufferNode* nd = _completed_buffers_head;
 276       _completed_buffers_head = nd->next();
 277       nd->set_next(buffers_to_delete);
 278       buffers_to_delete = nd;
 279     }
 280     _n_completed_buffers = 0;
 281     _completed_buffers_tail = NULL;
 282     DEBUG_ONLY(assert_completed_buffer_list_len_correct_locked());
 283   }
 284   while (buffers_to_delete != NULL) {
 285     BufferNode* nd = buffers_to_delete;
 286     buffers_to_delete = nd->next();
 287     deallocate_buffer(nd);
 288   }
 289 
 290 }
 291 
 292 void DirtyCardQueueSet::abandon_logs() {
 293   assert(SafepointSynchronize::is_at_safepoint(), "Must be at safepoint.");
 294   clear();
 295   // Since abandon is done only at safepoints, we can safely manipulate
 296   // these queues.
 297   for (JavaThread* t = Threads::first(); t; t = t->next()) {
 298     t->dirty_card_queue().reset();
 299   }
 300   shared_dirty_card_queue()->reset();
 301 }
 302 
 303 void DirtyCardQueueSet::concatenate_log(DirtyCardQueue& dcq) {
 304   if (!dcq.is_empty()) {
 305     dcq.flush();
 306   }
 307 }
 308 
 309 void DirtyCardQueueSet::concatenate_logs() {
 310   // Iterate over all the threads, if we find a partial log add it to
 311   // the global list of logs.  Temporarily turn off the limit on the number
 312   // of outstanding buffers.
 313   int save_max_completed_queue = _max_completed_queue;
 314   _max_completed_queue = max_jint;
 315   assert(SafepointSynchronize::is_at_safepoint(), "Must be at safepoint.");
 316   for (JavaThread* t = Threads::first(); t; t = t->next()) {
 317     concatenate_log(t->dirty_card_queue());
 318   }
 319   concatenate_log(_shared_dirty_card_queue);
 320   // Restore the completed buffer queue limit.
 321   _max_completed_queue = save_max_completed_queue;
 322 }