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/shared/satbMarkQueue.hpp"
  27 #include "gc/shared/collectedHeap.hpp"
  28 #include "logging/log.hpp"
  29 #include "memory/allocation.inline.hpp"
  30 #include "oops/oop.inline.hpp"
  31 #include "runtime/atomic.hpp"
  32 #include "runtime/mutexLocker.hpp"
  33 #include "runtime/orderAccess.hpp"
  34 #include "runtime/os.hpp"
  35 #include "runtime/safepoint.hpp"
  36 #include "runtime/thread.hpp"
  37 #include "runtime/threadSMR.hpp"
  38 #include "runtime/vmThread.hpp"
  39 #include "utilities/globalCounter.inline.hpp"
  40 
  41 SATBMarkQueue::SATBMarkQueue(SATBMarkQueueSet* qset) :
  42   // SATB queues are only active during marking cycles. We create
  43   // them with their active field set to false. If a thread is
  44   // created during a cycle and its SATB queue needs to be activated
  45   // before the thread starts running, we'll need to set its active
  46   // field to true. This must be done in the collector-specific
  47   // BarrierSet thread attachment protocol.
  48   PtrQueue(qset, false /* active */)
  49 { }
  50 
  51 void SATBMarkQueue::flush() {
  52   // Filter now to possibly save work later.  If filtering empties the
  53   // buffer then flush_impl can deallocate the buffer.
  54   filter();
  55   flush_impl();
  56 }
  57 
  58 // This method will first apply filtering to the buffer. If filtering
  59 // retains a small enough collection in the buffer, we can continue to
  60 // use the buffer as-is, instead of enqueueing and replacing it.
  61 
  62 void SATBMarkQueue::handle_completed_buffer() {
  63   // This method should only be called if there is a non-NULL buffer
  64   // that is full.
  65   assert(index() == 0, "pre-condition");
  66   assert(_buf != NULL, "pre-condition");
  67 
  68   filter();
  69 
  70   size_t threshold = satb_qset()->buffer_enqueue_threshold();
  71   // Ensure we'll enqueue completely full buffers.
  72   assert(threshold > 0, "enqueue threshold = 0");
  73   // Ensure we won't enqueue empty buffers.
  74   assert(threshold <= capacity(),
  75          "enqueue threshold " SIZE_FORMAT " exceeds capacity " SIZE_FORMAT,
  76          threshold, capacity());
  77 
  78   if (index() < threshold) {
  79     // Buffer is sufficiently full; enqueue and allocate a new one.
  80     enqueue_completed_buffer();
  81   } // Else continue to accumulate in buffer.
  82 }
  83 
  84 void SATBMarkQueue::apply_closure_and_empty(SATBBufferClosure* cl) {
  85   assert(SafepointSynchronize::is_at_safepoint(),
  86          "SATB queues must only be processed at safepoints");
  87   if (_buf != NULL) {
  88     cl->do_buffer(&_buf[index()], size());
  89     reset();
  90   }
  91 }
  92 
  93 #ifndef PRODUCT
  94 // Helpful for debugging
  95 
  96 static void print_satb_buffer(const char* name,
  97                               void** buf,
  98                               size_t index,
  99                               size_t capacity) {
 100   tty->print_cr("  SATB BUFFER [%s] buf: " PTR_FORMAT " index: " SIZE_FORMAT
 101                 " capacity: " SIZE_FORMAT,
 102                 name, p2i(buf), index, capacity);
 103 }
 104 
 105 void SATBMarkQueue::print(const char* name) {
 106   print_satb_buffer(name, _buf, index(), capacity());
 107 }
 108 
 109 #endif // PRODUCT
 110 
 111 SATBMarkQueueSet::SATBMarkQueueSet(BufferNode::Allocator* allocator) :
 112   PtrQueueSet(allocator),
 113   _list(),
 114   _count_and_process_flag(0),
 115   _process_completed_buffers_threshold(SIZE_MAX),
 116   _buffer_enqueue_threshold(0)
 117 {}
 118 
 119 SATBMarkQueueSet::~SATBMarkQueueSet() {
 120   abandon_completed_buffers();
 121 }
 122 
 123 // _count_and_process_flag has flag in least significant bit, count in
 124 // remaining bits.  _process_completed_buffers_threshold is scaled
 125 // accordingly, with the lsbit set, so a _count_and_process_flag value
 126 // is directly comparable with the recorded threshold value.  The
 127 // process flag is set whenever the count exceeds the threshold, and
 128 // remains set until the count is reduced to zero.
 129 
 130 // Increment count.  If count > threshold, set flag, else maintain flag.
 131 static void increment_count(volatile size_t* cfptr, size_t threshold) {
 132   size_t old;
 133   size_t value = Atomic::load(cfptr);
 134   do {
 135     old = value;
 136     value += 2;
 137     assert(value > old, "overflow");
 138     if (value > threshold) value |= 1;
 139     value = Atomic::cmpxchg(value, cfptr, old);
 140   } while (value != old);
 141 }
 142 
 143 // Decrement count.  If count == 0, clear flag, else maintain flag.
 144 static void decrement_count(volatile size_t* cfptr) {
 145   size_t old;
 146   size_t value = Atomic::load(cfptr);
 147   do {
 148     assert((value >> 1) != 0, "underflow");
 149     old = value;
 150     value -= 2;
 151     if (value <= 1) value = 0;
 152     value = Atomic::cmpxchg(value, cfptr, old);
 153   } while (value != old);
 154 }
 155 
 156 void SATBMarkQueueSet::set_process_completed_buffers_threshold(size_t value) {
 157   // Scale requested threshold to align with count field.  If scaling
 158   // overflows, just use max value.  Set process flag field to make
 159   // comparison in increment_count exact.
 160   size_t scaled_value = value << 1;
 161   if ((scaled_value >> 1) != value) {
 162     scaled_value = SIZE_MAX;
 163   }
 164   _process_completed_buffers_threshold = scaled_value | 1;
 165 }
 166 
 167 void SATBMarkQueueSet::set_buffer_enqueue_threshold_percentage(uint value) {
 168   // Minimum threshold of 1 ensures enqueuing of completely full buffers.
 169   size_t size = buffer_size();
 170   size_t enqueue_qty = (size * value) / 100;
 171   _buffer_enqueue_threshold = MAX2(size - enqueue_qty, (size_t)1);
 172 }
 173 
 174 #ifdef ASSERT
 175 void SATBMarkQueueSet::dump_active_states(bool expected_active) {
 176   log_error(gc, verify)("Expected SATB active state: %s", expected_active ? "ACTIVE" : "INACTIVE");
 177   log_error(gc, verify)("Actual SATB active states:");
 178   log_error(gc, verify)("  Queue set: %s", is_active() ? "ACTIVE" : "INACTIVE");
 179 
 180   class DumpThreadStateClosure : public ThreadClosure {
 181     SATBMarkQueueSet* _qset;
 182   public:
 183     DumpThreadStateClosure(SATBMarkQueueSet* qset) : _qset(qset) {}
 184     virtual void do_thread(Thread* t) {
 185       SATBMarkQueue& queue = _qset->satb_queue_for_thread(t);
 186       log_error(gc, verify)("  Thread \"%s\" queue: %s",
 187                             t->name(),
 188                             queue.is_active() ? "ACTIVE" : "INACTIVE");
 189     }
 190   } closure(this);
 191   Threads::threads_do(&closure);
 192 }
 193 
 194 void SATBMarkQueueSet::verify_active_states(bool expected_active) {
 195   // Verify queue set state
 196   if (is_active() != expected_active) {
 197     dump_active_states(expected_active);
 198     fatal("SATB queue set has an unexpected active state");
 199   }
 200 
 201   // Verify thread queue states
 202   class VerifyThreadStatesClosure : public ThreadClosure {
 203     SATBMarkQueueSet* _qset;
 204     bool _expected_active;
 205   public:
 206     VerifyThreadStatesClosure(SATBMarkQueueSet* qset, bool expected_active) :
 207       _qset(qset), _expected_active(expected_active) {}
 208     virtual void do_thread(Thread* t) {
 209       if (_qset->satb_queue_for_thread(t).is_active() != _expected_active) {
 210         _qset->dump_active_states(_expected_active);
 211         fatal("Thread SATB queue has an unexpected active state");
 212       }
 213     }
 214   } closure(this, expected_active);
 215   Threads::threads_do(&closure);
 216 }
 217 #endif // ASSERT
 218 
 219 void SATBMarkQueueSet::set_active_all_threads(bool active, bool expected_active) {
 220   assert(SafepointSynchronize::is_at_safepoint(), "Must be at safepoint.");
 221 #ifdef ASSERT
 222   verify_active_states(expected_active);
 223 #endif // ASSERT
 224   // Update the global state, synchronized with threads list management.
 225   {
 226     MutexLocker ml(NonJavaThreadsList_lock, Mutex::_no_safepoint_check_flag);
 227     _all_active = active;
 228   }
 229 
 230   class SetThreadActiveClosure : public ThreadClosure {
 231     SATBMarkQueueSet* _qset;
 232     bool _active;
 233   public:
 234     SetThreadActiveClosure(SATBMarkQueueSet* qset, bool active) :
 235       _qset(qset), _active(active) {}
 236     virtual void do_thread(Thread* t) {
 237       _qset->satb_queue_for_thread(t).set_active(_active);
 238     }
 239   } closure(this, active);
 240   Threads::threads_do(&closure);
 241 }
 242 
 243 bool SATBMarkQueueSet::apply_closure_to_completed_buffer(SATBBufferClosure* cl) {
 244   BufferNode* nd = get_completed_buffer();
 245   if (nd != NULL) {
 246     void **buf = BufferNode::make_buffer_from_node(nd);
 247     size_t index = nd->index();
 248     size_t size = buffer_size();
 249     assert(index <= size, "invariant");
 250     cl->do_buffer(buf + index, size - index);
 251     deallocate_buffer(nd);
 252     return true;
 253   } else {
 254     return false;
 255   }
 256 }
 257 
 258 // SATB buffer life-cycle - Per-thread queues obtain buffers from the
 259 // qset's buffer allocator, fill them, and push them onto the qset's
 260 // list.  The GC concurrently pops buffers from the qset, processes
 261 // them, and returns them to the buffer allocator for re-use.  Both
 262 // the allocator and the qset use lock-free stacks.  The ABA problem
 263 // is solved by having both allocation pops and GC pops performed
 264 // within GlobalCounter critical sections, while the return of buffers
 265 // to the allocator performs a GlobalCounter synchronize before
 266 // pushing onto the allocator's list.
 267 
 268 void SATBMarkQueueSet::enqueue_completed_buffer(BufferNode* node) {
 269   assert(node != NULL, "precondition");
 270   // Increment count and update flag appropriately.  Done before
 271   // pushing buffer so count is always at least the actual number in
 272   // the list, and decrement never underflows.
 273   increment_count(&_count_and_process_flag, _process_completed_buffers_threshold);
 274   _list.push(*node);
 275 }
 276 
 277 BufferNode* SATBMarkQueueSet::get_completed_buffer() {
 278   BufferNode* node;
 279   {
 280     GlobalCounter::CriticalSection cs(Thread::current());
 281     node = _list.pop();
 282   }
 283   if (node != NULL) {
 284     // Got a buffer so decrement count and update flag appropriately.
 285     decrement_count(&_count_and_process_flag);
 286   }
 287   return node;
 288 }
 289 
 290 #ifndef PRODUCT
 291 // Helpful for debugging
 292 
 293 #define SATB_PRINTER_BUFFER_SIZE 256
 294 
 295 void SATBMarkQueueSet::print_all(const char* msg) {
 296   char buffer[SATB_PRINTER_BUFFER_SIZE];
 297   assert(SafepointSynchronize::is_at_safepoint(), "Must be at safepoint.");
 298 
 299   tty->cr();
 300   tty->print_cr("SATB BUFFERS [%s]", msg);
 301 
 302   BufferNode* nd = _list.top();
 303   int i = 0;
 304   while (nd != NULL) {
 305     void** buf = BufferNode::make_buffer_from_node(nd);
 306     os::snprintf(buffer, SATB_PRINTER_BUFFER_SIZE, "Enqueued: %d", i);
 307     print_satb_buffer(buffer, buf, nd->index(), buffer_size());
 308     nd = nd->next();
 309     i += 1;
 310   }
 311 
 312   class PrintThreadClosure : public ThreadClosure {
 313     SATBMarkQueueSet* _qset;
 314     char* _buffer;
 315 
 316   public:
 317     PrintThreadClosure(SATBMarkQueueSet* qset, char* buffer) :
 318       _qset(qset), _buffer(buffer) {}
 319 
 320     virtual void do_thread(Thread* t) {
 321       os::snprintf(_buffer, SATB_PRINTER_BUFFER_SIZE, "Thread: %s", t->name());
 322       _qset->satb_queue_for_thread(t).print(_buffer);
 323     }
 324   } closure(this, buffer);
 325   Threads::threads_do(&closure);
 326 
 327   tty->cr();
 328 }
 329 #endif // PRODUCT
 330 
 331 void SATBMarkQueueSet::abandon_completed_buffers() {
 332   Atomic::store(&_count_and_process_flag, size_t(0));
 333   BufferNode* buffers_to_delete = _list.pop_all();
 334   while (buffers_to_delete != NULL) {
 335     BufferNode* bn = buffers_to_delete;
 336     buffers_to_delete = bn->next();
 337     bn->set_next(NULL);
 338     deallocate_buffer(bn);
 339   }
 340 }
 341 
 342 void SATBMarkQueueSet::abandon_partial_marking() {
 343   assert(SafepointSynchronize::is_at_safepoint(), "Must be at safepoint.");
 344   abandon_completed_buffers();
 345 
 346   class AbandonThreadQueueClosure : public ThreadClosure {
 347     SATBMarkQueueSet* _qset;
 348   public:
 349     AbandonThreadQueueClosure(SATBMarkQueueSet* qset) : _qset(qset) {}
 350     virtual void do_thread(Thread* t) {
 351       _qset->satb_queue_for_thread(t).reset();
 352     }
 353   } closure(this);
 354   Threads::threads_do(&closure);
 355 }