1 /*
   2  * Copyright (c) 2015, 2019, Red Hat, Inc. All rights reserved.
   3  *
   4  * This code is free software; you can redistribute it and/or modify it
   5  * under the terms of the GNU General Public License version 2 only, as
   6  * published by the Free Software Foundation.
   7  *
   8  * This code is distributed in the hope that it will be useful, but WITHOUT
   9  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  10  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  11  * version 2 for more details (a copy is included in the LICENSE file that
  12  * accompanied this code).
  13  *
  14  * You should have received a copy of the GNU General Public License version
  15  * 2 along with this work; if not, write to the Free Software Foundation,
  16  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  17  *
  18  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  19  * or visit www.oracle.com if you need additional information or have any
  20  * questions.
  21  *
  22  */
  23 
  24 #ifndef SHARE_VM_GC_SHENANDOAH_SHENANDOAHCONCURRENTMARK_INLINE_HPP
  25 #define SHARE_VM_GC_SHENANDOAH_SHENANDOAHCONCURRENTMARK_INLINE_HPP
  26 
  27 #include "gc/shenandoah/shenandoahAsserts.hpp"
  28 #include "gc/shenandoah/shenandoahBarrierSet.inline.hpp"
  29 #include "gc/shenandoah/shenandoahConcurrentMark.hpp"
  30 #include "gc/shenandoah/shenandoahHeap.inline.hpp"
  31 #include "gc/shenandoah/shenandoahMarkingContext.inline.hpp"
  32 #include "gc/shenandoah/shenandoahStringDedup.inline.hpp"
  33 #include "gc/shenandoah/shenandoahTaskqueue.inline.hpp"
  34 #include "memory/iterator.inline.hpp"
  35 #include "oops/oop.inline.hpp"
  36 #include "runtime/prefetch.inline.hpp"
  37 
  38 template <class T>
  39 void ShenandoahConcurrentMark::do_task(ShenandoahObjToScanQueue* q, T* cl, ShenandoahLiveData* live_data, ShenandoahMarkTask* task) {
  40   oop obj = task->obj();
  41 
  42   shenandoah_assert_not_forwarded(NULL, obj);
  43   shenandoah_assert_marked(NULL, obj);
  44   shenandoah_assert_not_in_cset_except(NULL, obj, _heap->cancelled_gc());
  45 
  46   if (task->is_not_chunked()) {
  47     if (obj->is_instance()) {
  48       // Case 1: Normal oop, process as usual.
  49       obj->oop_iterate(cl);
  50     } else if (obj->is_objArray()) {
  51       // Case 2: Object array instance and no chunk is set. Must be the first
  52       // time we visit it, start the chunked processing.
  53       do_chunked_array_start<T>(q, cl, obj);
  54     } else {
  55       // Case 3: Primitive array. Do nothing, no oops there. We use the same
  56       // performance tweak TypeArrayKlass::oop_oop_iterate_impl is using:
  57       // We skip iterating over the klass pointer since we know that
  58       // Universe::TypeArrayKlass never moves.
  59       assert (obj->is_typeArray(), "should be type array");
  60     }
  61     // Count liveness the last: push the outstanding work to the queues first
  62     count_liveness(live_data, obj);
  63   } else {
  64     // Case 4: Array chunk, has sensible chunk id. Process it.
  65     do_chunked_array<T>(q, cl, obj, task->chunk(), task->pow());
  66   }
  67 }
  68 
  69 inline void ShenandoahConcurrentMark::count_liveness(ShenandoahLiveData* live_data, oop obj) {
  70   size_t region_idx = _heap->heap_region_index_containing(obj);
  71   ShenandoahHeapRegion* region = _heap->get_region(region_idx);
  72   size_t size = obj->size();
  73 
  74   if (!region->is_humongous_start()) {
  75     assert(!region->is_humongous(), "Cannot have continuations here");
  76     ShenandoahLiveData cur = live_data[region_idx];
  77     size_t new_val = size + cur;
  78     if (new_val >= SHENANDOAH_LIVEDATA_MAX) {
  79       // overflow, flush to region data
  80       region->increase_live_data_gc_words(new_val);
  81       live_data[region_idx] = 0;
  82     } else {
  83       // still good, remember in locals
  84       live_data[region_idx] = (ShenandoahLiveData) new_val;
  85     }
  86   } else {
  87     shenandoah_assert_in_correct_region(NULL, obj);
  88     size_t num_regions = ShenandoahHeapRegion::required_regions(size * HeapWordSize);
  89 
  90     for (size_t i = region_idx; i < region_idx + num_regions; i++) {
  91       ShenandoahHeapRegion* chain_reg = _heap->get_region(i);
  92       assert(chain_reg->is_humongous(), "Expecting a humongous region");
  93       chain_reg->increase_live_data_gc_words(chain_reg->used() >> LogHeapWordSize);
  94     }
  95   }
  96 }
  97 
  98 template <class T>
  99 inline void ShenandoahConcurrentMark::do_chunked_array_start(ShenandoahObjToScanQueue* q, T* cl, oop obj) {
 100   assert(obj->is_objArray(), "expect object array");
 101   objArrayOop array = objArrayOop(obj);
 102   int len = array->length();
 103 
 104   if (len <= (int) ObjArrayMarkingStride*2) {
 105     // A few slices only, process directly
 106     array->oop_iterate_range(cl, 0, len);
 107   } else {
 108     int bits = log2_long(len);
 109     // Compensate for non-power-of-two arrays, cover the array in excess:
 110     if (len != (1 << bits)) bits++;
 111 
 112     // Only allow full chunks on the queue. This frees do_chunked_array() from checking from/to
 113     // boundaries against array->length(), touching the array header on every chunk.
 114     //
 115     // To do this, we cut the prefix in full-sized chunks, and submit them on the queue.
 116     // If the array is not divided in chunk sizes, then there would be an irregular tail,
 117     // which we will process separately.
 118 
 119     int last_idx = 0;
 120 
 121     int chunk = 1;
 122     int pow = bits;
 123 
 124     // Handle overflow
 125     if (pow >= 31) {
 126       assert (pow == 31, "sanity");
 127       pow--;
 128       chunk = 2;
 129       last_idx = (1 << pow);
 130       bool pushed = q->push(ShenandoahMarkTask(array, 1, pow));
 131       assert(pushed, "overflow queue should always succeed pushing");
 132     }
 133 
 134     // Split out tasks, as suggested in ObjArrayChunkedTask docs. Record the last
 135     // successful right boundary to figure out the irregular tail.
 136     while ((1 << pow) > (int)ObjArrayMarkingStride &&
 137            (chunk*2 < ShenandoahMarkTask::chunk_size())) {
 138       pow--;
 139       int left_chunk = chunk*2 - 1;
 140       int right_chunk = chunk*2;
 141       int left_chunk_end = left_chunk * (1 << pow);
 142       if (left_chunk_end < len) {
 143         bool pushed = q->push(ShenandoahMarkTask(array, left_chunk, pow));
 144         assert(pushed, "overflow queue should always succeed pushing");
 145         chunk = right_chunk;
 146         last_idx = left_chunk_end;
 147       } else {
 148         chunk = left_chunk;
 149       }
 150     }
 151 
 152     // Process the irregular tail, if present
 153     int from = last_idx;
 154     if (from < len) {
 155       array->oop_iterate_range(cl, from, len);
 156     }
 157   }
 158 }
 159 
 160 template <class T>
 161 inline void ShenandoahConcurrentMark::do_chunked_array(ShenandoahObjToScanQueue* q, T* cl, oop obj, int chunk, int pow) {
 162   assert(obj->is_objArray(), "expect object array");
 163   objArrayOop array = objArrayOop(obj);
 164 
 165   assert (ObjArrayMarkingStride > 0, "sanity");
 166 
 167   // Split out tasks, as suggested in ObjArrayChunkedTask docs. Avoid pushing tasks that
 168   // are known to start beyond the array.
 169   while ((1 << pow) > (int)ObjArrayMarkingStride && (chunk*2 < ShenandoahMarkTask::chunk_size())) {
 170     pow--;
 171     chunk *= 2;
 172     bool pushed = q->push(ShenandoahMarkTask(array, chunk - 1, pow));
 173     assert(pushed, "overflow queue should always succeed pushing");
 174   }
 175 
 176   int chunk_size = 1 << pow;
 177 
 178   int from = (chunk - 1) * chunk_size;
 179   int to = chunk * chunk_size;
 180 
 181 #ifdef ASSERT
 182   int len = array->length();
 183   assert (0 <= from && from < len, "from is sane: %d/%d", from, len);
 184   assert (0 < to && to <= len, "to is sane: %d/%d", to, len);
 185 #endif
 186 
 187   array->oop_iterate_range(cl, from, to);
 188 }
 189 
 190 class ShenandoahConcMarkSATBBufferClosure : public ShenandoahSATBBufferClosure {
 191 private:
 192   ShenandoahObjToScanQueue* _queue;
 193   ShenandoahHeap* _heap;
 194   ShenandoahMarkingContext* const _mark_context;
 195 public:
 196   ShenandoahConcMarkSATBBufferClosure(ShenandoahObjToScanQueue* q) :
 197     _queue(q),
 198     _heap(ShenandoahHeap::heap()),
 199     _mark_context(_heap->marking_context())
 200   {
 201   }
 202 
 203   void do_buffer(void **buffer, size_t size) {
 204     if (_heap->has_forwarded_objects()) {
 205       if (ShenandoahStringDedup::is_enabled()) {
 206         do_buffer_impl<RESOLVE, ENQUEUE_DEDUP>(buffer, size);
 207       } else {
 208         do_buffer_impl<RESOLVE, NO_DEDUP>(buffer, size);
 209       }
 210     } else {
 211       if (ShenandoahStringDedup::is_enabled()) {
 212         do_buffer_impl<NONE, ENQUEUE_DEDUP>(buffer, size);
 213       } else {
 214         do_buffer_impl<NONE, NO_DEDUP>(buffer, size);
 215       }
 216     }
 217   }
 218 
 219   template<UpdateRefsMode UPDATE_REFS, StringDedupMode STRING_DEDUP>
 220   void do_buffer_impl(void **buffer, size_t size) {
 221     for (size_t i = 0; i < size; ++i) {
 222       oop *p = (oop *) &buffer[i];
 223       ShenandoahConcurrentMark::mark_through_ref<oop, UPDATE_REFS, STRING_DEDUP>(p, _heap, _queue, _mark_context);
 224     }
 225   }
 226 };
 227 
 228 template<class T, UpdateRefsMode UPDATE_REFS, StringDedupMode STRING_DEDUP>
 229 inline void ShenandoahConcurrentMark::mark_through_ref(T *p, ShenandoahHeap* heap, ShenandoahObjToScanQueue* q, ShenandoahMarkingContext* const mark_context) {
 230   T o = RawAccess<>::oop_load(p);
 231   if (!CompressedOops::is_null(o)) {
 232     oop obj = CompressedOops::decode_not_null(o);
 233     switch (UPDATE_REFS) {
 234     case NONE:
 235       break;
 236     case RESOLVE:
 237       obj = ShenandoahBarrierSet::resolve_forwarded_not_null(obj);
 238       break;
 239     case SIMPLE:
 240       // We piggy-back reference updating to the marking tasks.
 241       obj = heap->update_with_forwarded_not_null(p, obj);
 242       break;
 243     case CONCURRENT:
 244       obj = heap->maybe_update_with_forwarded_not_null(p, obj);
 245       break;
 246     default:
 247       ShouldNotReachHere();
 248     }
 249 
 250     // Note: Only when concurrently updating references can obj be different
 251     // (that is, really different, not just different from-/to-space copies of the same)
 252     // from the one we originally loaded. Mutator thread can beat us by writing something
 253     // else into the location. In that case, we would mark through that updated value,
 254     // on the off-chance it is not handled by other means (e.g. via SATB). However,
 255     // if that write was NULL, we don't need to do anything else.
 256     if (UPDATE_REFS != CONCURRENT || !CompressedOops::is_null(obj)) {
 257       shenandoah_assert_not_forwarded(p, obj);
 258       shenandoah_assert_not_in_cset_except(p, obj, heap->cancelled_gc());
 259 
 260       if (mark_context->mark(obj)) {
 261         bool pushed = q->push(ShenandoahMarkTask(obj));
 262         assert(pushed, "overflow queue should always succeed pushing");
 263 
 264         if ((STRING_DEDUP == ENQUEUE_DEDUP) && ShenandoahStringDedup::is_candidate(obj)) {
 265           assert(ShenandoahStringDedup::is_enabled(), "Must be enabled");
 266           ShenandoahStringDedup::enqueue_candidate(obj);
 267         }
 268       }
 269 
 270       shenandoah_assert_marked(p, obj);
 271     }
 272   }
 273 }
 274 
 275 #endif // SHARE_VM_GC_SHENANDOAH_SHENANDOAHCONCURRENTMARK_INLINE_HPP