1 /*
   2  * Copyright (c) 2001, 2015, 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.inline.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 bool DirtyCardQueue::apply_closure(CardTableEntryClosure* cl,
 114                                    bool consume,
 115                                    uint worker_i) {
 116   bool res = true;
 117   if (_buf != NULL) {
 118     res = apply_closure_to_buffer(cl, _buf, _index, _sz,
 119                                   consume,
 120                                   worker_i);
 121     if (res && consume) {
 122       _index = _sz;
 123     }
 124   }
 125   return res;
 126 }
 127 
 128 bool DirtyCardQueue::apply_closure_to_buffer(CardTableEntryClosure* cl,
 129                                              void** buf,
 130                                              size_t index, size_t sz,
 131                                              bool consume,
 132                                              uint worker_i) {
 133   if (cl == NULL) return true;
 134   size_t limit = byte_index_to_index(sz);
 135   for (size_t i = byte_index_to_index(index); i < limit; ++i) {
 136     jbyte* card_ptr = static_cast<jbyte*>(buf[i]);
 137     if (card_ptr != NULL) {
 138       // Set the entry to null, so we don't do it again (via the test
 139       // above) if we reconsider this buffer.
 140       if (consume) {
 141         buf[i] = NULL;
 142       }
 143       if (!cl->do_card_ptr(card_ptr, worker_i)) {
 144         return false;
 145       }
 146     }
 147   }
 148   return true;
 149 }
 150 
 151 DirtyCardQueueSet::DirtyCardQueueSet(bool notify_when_complete) :
 152   PtrQueueSet(notify_when_complete),
 153   _mut_process_closure(NULL),
 154   _shared_dirty_card_queue(this, true /* permanent */),
 155   _free_ids(NULL),
 156   _processed_buffers_mut(0), _processed_buffers_rs_thread(0)
 157 {
 158   _all_active = true;
 159 }
 160 
 161 // Determines how many mutator threads can process the buffers in parallel.
 162 uint DirtyCardQueueSet::num_par_ids() {
 163   return (uint)os::processor_count();
 164 }
 165 
 166 void DirtyCardQueueSet::initialize(CardTableEntryClosure* cl,
 167                                    Monitor* cbl_mon,
 168                                    Mutex* fl_lock,
 169                                    size_t process_completed_threshold,
 170                                    size_t max_completed_queue,
 171                                    Mutex* lock,
 172                                    DirtyCardQueueSet* fl_owner,
 173                                    bool init_free_ids) {
 174   _mut_process_closure = cl;
 175   PtrQueueSet::initialize(cbl_mon,
 176                           fl_lock,
 177                           process_completed_threshold,
 178                           max_completed_queue,
 179                           fl_owner);
 180   set_buffer_size(G1UpdateBufferSize);
 181   _shared_dirty_card_queue.set_lock(lock);
 182   if (init_free_ids) {
 183     _free_ids = new FreeIdSet(num_par_ids(), _cbl_mon);
 184   }
 185 }
 186 
 187 void DirtyCardQueueSet::handle_zero_index_for_thread(JavaThread* t) {
 188   t->dirty_card_queue().handle_zero_index();
 189 }
 190 
 191 bool DirtyCardQueueSet::mut_process_buffer(void** buf) {
 192   guarantee(_free_ids != NULL, "must be");
 193 
 194   // claim a par id
 195   uint worker_i = _free_ids->claim_par_id();
 196 
 197   bool b = DirtyCardQueue::apply_closure_to_buffer(_mut_process_closure, buf, 0,
 198                                                    _sz, true, worker_i);
 199   if (b) {
 200     Atomic::inc(&_processed_buffers_mut);
 201   }
 202 
 203   // release the id
 204   _free_ids->release_par_id(worker_i);
 205 
 206   return b;
 207 }
 208 
 209 
 210 BufferNode* DirtyCardQueueSet::get_completed_buffer(size_t stop_at) {
 211   BufferNode* nd = NULL;
 212   MutexLockerEx x(_cbl_mon, Mutex::_no_safepoint_check_flag);
 213 
 214   if ((size_t)_n_completed_buffers <= stop_at) {
 215     _process_completed = false;
 216     return NULL;
 217   }
 218 
 219   if (_completed_buffers_head != NULL) {
 220     nd = _completed_buffers_head;
 221     _completed_buffers_head = nd->next();
 222     if (_completed_buffers_head == NULL)
 223       _completed_buffers_tail = NULL;
 224     assert(_n_completed_buffers > 0, "Invariant");
 225     _n_completed_buffers--;

 226   }
 227   DEBUG_ONLY(assert_completed_buffer_list_len_correct_locked());
 228   return nd;
 229 }
 230 
 231 bool DirtyCardQueueSet::apply_closure_to_completed_buffer_helper(CardTableEntryClosure* cl,
 232                                                                  uint worker_i,
 233                                                                  BufferNode* nd) {
 234   if (nd != NULL) {
 235     void **buf = BufferNode::make_buffer_from_node(nd);
 236     size_t index = nd->index();
 237     bool b =
 238       DirtyCardQueue::apply_closure_to_buffer(cl, buf,
 239                                               index, _sz,
 240                                               true, worker_i);
 241     if (b) {
 242       deallocate_buffer(buf);
 243       return true;  // In normal case, go on to next buffer.
 244     } else {
 245       enqueue_complete_buffer(buf, index);
 246       return false;
 247     }
 248   } else {
 249     return false;
 250   }
 251 }
 252 
 253 bool DirtyCardQueueSet::apply_closure_to_completed_buffer(CardTableEntryClosure* cl,
 254                                                           uint worker_i,
 255                                                           size_t stop_at,
 256                                                           bool during_pause) {
 257   assert(!during_pause || stop_at == 0, "Should not leave any completed buffers during a pause");
 258   BufferNode* nd = get_completed_buffer(stop_at);
 259   bool res = apply_closure_to_completed_buffer_helper(cl, worker_i, nd);
 260   if (res) Atomic::inc(&_processed_buffers_rs_thread);
 261   return res;
 262 }
 263 
 264 void DirtyCardQueueSet::apply_closure_to_all_completed_buffers(CardTableEntryClosure* cl) {
 265   BufferNode* nd = _completed_buffers_head;
 266   while (nd != NULL) {
 267     bool b =
 268       DirtyCardQueue::apply_closure_to_buffer(cl,
 269                                               BufferNode::make_buffer_from_node(nd),
 270                                               0, _sz, false);
 271     guarantee(b, "Should not stop early.");
 272     nd = nd->next();
 273   }
 274 }
 275 
 276 void DirtyCardQueueSet::par_apply_closure_to_all_completed_buffers(CardTableEntryClosure* cl) {
 277   BufferNode* nd = _cur_par_buffer_node;
 278   while (nd != NULL) {
 279     BufferNode* next = (BufferNode*)nd->next();
 280     BufferNode* actual = (BufferNode*)Atomic::cmpxchg_ptr((void*)next, (volatile void*)&_cur_par_buffer_node, (void*)nd);
 281     if (actual == nd) {
 282       bool b =
 283         DirtyCardQueue::apply_closure_to_buffer(cl,
 284                                                 BufferNode::make_buffer_from_node(actual),
 285                                                 0, _sz, false);
 286       guarantee(b, "Should not stop early.");
 287       nd = next;
 288     } else {
 289       nd = actual;
 290     }
 291   }
 292 }
 293 
 294 // Deallocates any completed log buffers
 295 void DirtyCardQueueSet::clear() {
 296   BufferNode* buffers_to_delete = NULL;
 297   {
 298     MutexLockerEx x(_cbl_mon, Mutex::_no_safepoint_check_flag);
 299     while (_completed_buffers_head != NULL) {
 300       BufferNode* nd = _completed_buffers_head;
 301       _completed_buffers_head = nd->next();
 302       nd->set_next(buffers_to_delete);
 303       buffers_to_delete = nd;
 304     }
 305     _n_completed_buffers = 0;
 306     _completed_buffers_tail = NULL;
 307     DEBUG_ONLY(assert_completed_buffer_list_len_correct_locked());
 308   }
 309   while (buffers_to_delete != NULL) {
 310     BufferNode* nd = buffers_to_delete;
 311     buffers_to_delete = nd->next();
 312     deallocate_buffer(BufferNode::make_buffer_from_node(nd));
 313   }
 314 
 315 }
 316 
 317 void DirtyCardQueueSet::abandon_logs() {
 318   assert(SafepointSynchronize::is_at_safepoint(), "Must be at safepoint.");
 319   clear();
 320   // Since abandon is done only at safepoints, we can safely manipulate
 321   // these queues.
 322   for (JavaThread* t = Threads::first(); t; t = t->next()) {
 323     t->dirty_card_queue().reset();
 324   }
 325   shared_dirty_card_queue()->reset();
 326 }
 327 
 328 
 329 void DirtyCardQueueSet::concatenate_logs() {
 330   // Iterate over all the threads, if we find a partial log add it to
 331   // the global list of logs.  Temporarily turn off the limit on the number
 332   // of outstanding buffers.
 333   size_t save_max_completed_queue = _max_completed_queue;
 334   _max_completed_queue = max_jint;
 335   assert(SafepointSynchronize::is_at_safepoint(), "Must be at safepoint.");
 336   for (JavaThread* t = Threads::first(); t; t = t->next()) {
 337     DirtyCardQueue& dcq = t->dirty_card_queue();
 338     if (dcq.size() != 0) {
 339       void** buf = dcq.get_buf();
 340       // We must NULL out the unused entries, then enqueue.
 341       size_t limit = dcq.byte_index_to_index(dcq.get_index());
 342       for (size_t i = 0; i < limit; ++i) {
 343         buf[i] = NULL;
 344       }
 345       enqueue_complete_buffer(dcq.get_buf(), dcq.get_index());
 346       dcq.reinitialize();
 347     }
 348   }
 349   if (_shared_dirty_card_queue.size() != 0) {
 350     enqueue_complete_buffer(_shared_dirty_card_queue.get_buf(),
 351                             _shared_dirty_card_queue.get_index());
 352     _shared_dirty_card_queue.reinitialize();
 353   }
 354   // Restore the completed buffer queue limit.
 355   _max_completed_queue = save_max_completed_queue;
 356 }
--- EOF ---