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