1 /*
2 * Copyright (C) 2014 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "concurrent_copying.h"
18
19 #include "art_field-inl.h"
20 #include "barrier.h"
21 #include "base/file_utils.h"
22 #include "base/histogram-inl.h"
23 #include "base/pointer_size.h"
24 #include "base/quasi_atomic.h"
25 #include "base/stl_util.h"
26 #include "base/systrace.h"
27 #include "class_root-inl.h"
28 #include "debugger.h"
29 #include "gc/accounting/atomic_stack.h"
30 #include "gc/accounting/heap_bitmap-inl.h"
31 #include "gc/accounting/mod_union_table-inl.h"
32 #include "gc/accounting/read_barrier_table.h"
33 #include "gc/accounting/space_bitmap-inl.h"
34 #include "gc/gc_pause_listener.h"
35 #include "gc/reference_processor.h"
36 #include "gc/space/image_space.h"
37 #include "gc/space/space-inl.h"
38 #include "gc/verification.h"
39 #include "intern_table.h"
40 #include "mirror/class-inl.h"
41 #include "mirror/object-inl.h"
42 #include "mirror/object-refvisitor-inl.h"
43 #include "mirror/object_reference.h"
44 #include "oat/image-inl.h"
45 #include "scoped_thread_state_change-inl.h"
46 #include "thread-inl.h"
47 #include "thread_list.h"
48 #include "well_known_classes.h"
49
50 namespace art HIDDEN {
51 namespace gc {
52 namespace collector {
53
54 static constexpr size_t kDefaultGcMarkStackSize = 2 * MB;
55 // If kFilterModUnionCards then we attempt to filter cards that don't need to be dirty in the mod
56 // union table. Disabled since it does not seem to help the pause much.
57 static constexpr bool kFilterModUnionCards = kIsDebugBuild;
58 // If kDisallowReadBarrierDuringScan is true then the GC aborts if there are any read barrier that
59 // occur during ConcurrentCopying::Scan in GC thread. May be used to diagnose possibly unnecessary
60 // read barriers. Only enabled for kIsDebugBuild to avoid performance hit.
61 static constexpr bool kDisallowReadBarrierDuringScan = kIsDebugBuild;
62 // Slow path mark stack size, increase this if the stack is getting full and it is causing
63 // performance problems.
64 static constexpr size_t kReadBarrierMarkStackSize = 512 * KB;
65 // Verify that there are no missing card marks.
66 static constexpr bool kVerifyNoMissingCardMarks = kIsDebugBuild;
67
ConcurrentCopying(Heap * heap,bool young_gen,bool use_generational_cc,const std::string & name_prefix,bool measure_read_barrier_slow_path)68 ConcurrentCopying::ConcurrentCopying(Heap* heap,
69 bool young_gen,
70 bool use_generational_cc,
71 const std::string& name_prefix,
72 bool measure_read_barrier_slow_path)
73 : GarbageCollector(heap,
74 name_prefix + (name_prefix.empty() ? "" : " ") +
75 "concurrent copying"),
76 region_space_(nullptr),
77 gc_barrier_(new Barrier(0)),
78 gc_mark_stack_(accounting::ObjectStack::Create("concurrent copying gc mark stack",
79 kDefaultGcMarkStackSize,
80 kDefaultGcMarkStackSize)),
81 use_generational_cc_(use_generational_cc),
82 young_gen_(young_gen),
83 rb_mark_bit_stack_(accounting::ObjectStack::Create("rb copying gc mark stack",
84 kReadBarrierMarkStackSize,
85 kReadBarrierMarkStackSize)),
86 rb_mark_bit_stack_full_(false),
87 mark_stack_lock_("concurrent copying mark stack lock", kMarkSweepMarkStackLock),
88 thread_running_gc_(nullptr),
89 is_marking_(false),
90 is_using_read_barrier_entrypoints_(false),
91 is_active_(false),
92 is_asserting_to_space_invariant_(false),
93 region_space_bitmap_(nullptr),
94 heap_mark_bitmap_(nullptr),
95 live_stack_freeze_size_(0),
96 from_space_num_bytes_at_first_pause_(0),
97 mark_stack_mode_(kMarkStackModeOff),
98 weak_ref_access_enabled_(true),
99 copied_live_bytes_ratio_sum_(0.f),
100 gc_count_(0),
101 reclaimed_bytes_ratio_sum_(0.f),
102 cumulative_bytes_moved_(0),
103 skipped_blocks_lock_("concurrent copying bytes blocks lock", kMarkSweepMarkStackLock),
104 measure_read_barrier_slow_path_(measure_read_barrier_slow_path),
105 mark_from_read_barrier_measurements_(false),
106 rb_slow_path_ns_(0),
107 rb_slow_path_count_(0),
108 rb_slow_path_count_gc_(0),
109 rb_slow_path_histogram_lock_("Read barrier histogram lock"),
110 rb_slow_path_time_histogram_("Mutator time in read barrier slow path", 500, 32),
111 rb_slow_path_count_total_(0),
112 rb_slow_path_count_gc_total_(0),
113 rb_table_(heap_->GetReadBarrierTable()),
114 force_evacuate_all_(false),
115 gc_grays_immune_objects_(false),
116 immune_gray_stack_lock_("concurrent copying immune gray stack lock",
117 kMarkSweepMarkStackLock),
118 num_bytes_allocated_before_gc_(0) {
119 static_assert(space::RegionSpace::kRegionSize == accounting::ReadBarrierTable::kRegionSize,
120 "The region space size and the read barrier table region size must match");
121 CHECK(use_generational_cc_ || !young_gen_);
122 Thread* self = Thread::Current();
123 {
124 ReaderMutexLock mu(self, *Locks::heap_bitmap_lock_);
125 // Cache this so that we won't have to lock heap_bitmap_lock_ in
126 // Mark() which could cause a nested lock on heap_bitmap_lock_
127 // when GC causes a RB while doing GC or a lock order violation
128 // (class_linker_lock_ and heap_bitmap_lock_).
129 heap_mark_bitmap_ = heap->GetMarkBitmap();
130 }
131 {
132 MutexLock mu(self, mark_stack_lock_);
133 for (size_t i = 0; i < kMarkStackPoolSize; ++i) {
134 accounting::AtomicStack<mirror::Object>* mark_stack =
135 accounting::AtomicStack<mirror::Object>::Create(
136 "thread local mark stack", GetMarkStackSize(), GetMarkStackSize());
137 pooled_mark_stacks_.push_back(mark_stack);
138 }
139 }
140 // Return type of these functions are different. And even though the base class
141 // is same, using ternary operator complains.
142 metrics::ArtMetrics* metrics = GetMetrics();
143 are_metrics_initialized_ = true;
144 if (young_gen_) {
145 gc_time_histogram_ = metrics->YoungGcCollectionTime();
146 metrics_gc_count_ = metrics->YoungGcCount();
147 metrics_gc_count_delta_ = metrics->YoungGcCountDelta();
148 gc_throughput_histogram_ = metrics->YoungGcThroughput();
149 gc_tracing_throughput_hist_ = metrics->YoungGcTracingThroughput();
150 gc_throughput_avg_ = metrics->YoungGcThroughputAvg();
151 gc_tracing_throughput_avg_ = metrics->YoungGcTracingThroughputAvg();
152 gc_scanned_bytes_ = metrics->YoungGcScannedBytes();
153 gc_scanned_bytes_delta_ = metrics->YoungGcScannedBytesDelta();
154 gc_freed_bytes_ = metrics->YoungGcFreedBytes();
155 gc_freed_bytes_delta_ = metrics->YoungGcFreedBytesDelta();
156 gc_duration_ = metrics->YoungGcDuration();
157 gc_duration_delta_ = metrics->YoungGcDurationDelta();
158 } else {
159 gc_time_histogram_ = metrics->FullGcCollectionTime();
160 metrics_gc_count_ = metrics->FullGcCount();
161 metrics_gc_count_delta_ = metrics->FullGcCountDelta();
162 gc_throughput_histogram_ = metrics->FullGcThroughput();
163 gc_tracing_throughput_hist_ = metrics->FullGcTracingThroughput();
164 gc_throughput_avg_ = metrics->FullGcThroughputAvg();
165 gc_tracing_throughput_avg_ = metrics->FullGcTracingThroughputAvg();
166 gc_scanned_bytes_ = metrics->FullGcScannedBytes();
167 gc_scanned_bytes_delta_ = metrics->FullGcScannedBytesDelta();
168 gc_freed_bytes_ = metrics->FullGcFreedBytes();
169 gc_freed_bytes_delta_ = metrics->FullGcFreedBytesDelta();
170 gc_duration_ = metrics->FullGcDuration();
171 gc_duration_delta_ = metrics->FullGcDurationDelta();
172 }
173 }
174
MarkHeapReference(mirror::HeapReference<mirror::Object> * field,bool do_atomic_update)175 void ConcurrentCopying::MarkHeapReference(mirror::HeapReference<mirror::Object>* field,
176 bool do_atomic_update) {
177 Thread* const self = Thread::Current();
178 if (UNLIKELY(do_atomic_update)) {
179 // Used to mark the referent in DelayReferenceReferent in transaction mode.
180 mirror::Object* from_ref = field->AsMirrorPtr();
181 if (from_ref == nullptr) {
182 return;
183 }
184 mirror::Object* to_ref = Mark(self, from_ref);
185 if (from_ref != to_ref) {
186 do {
187 if (field->AsMirrorPtr() != from_ref) {
188 // Concurrently overwritten by a mutator.
189 break;
190 }
191 } while (!field->CasWeakRelaxed(from_ref, to_ref));
192 // "Relaxed" is not technically sufficient by C++ rules. However, we use a "release"
193 // operation to originally store the forwarding pointer, or a constructor fence if we
194 // directly obtained to_ref from Copy(). We then count on the fact that all later accesses
195 // to the to_ref object are data/address-dependent on the forwarding pointer, and there is
196 // no reasonable way for the compiler to eliminate that depenency. This is very similar to
197 // the reasoning we must use for final fields in any case.
198 }
199 } else {
200 // Used for preserving soft references, should be OK to not have a CAS here since there should be
201 // no other threads which can trigger read barriers on the same referent during reference
202 // processing.
203 field->Assign(Mark(self, field->AsMirrorPtr()));
204 }
205 }
206
~ConcurrentCopying()207 ConcurrentCopying::~ConcurrentCopying() {
208 STLDeleteElements(&pooled_mark_stacks_);
209 }
210
RunPhases()211 void ConcurrentCopying::RunPhases() {
212 CHECK(kUseBakerReadBarrier || kUseTableLookupReadBarrier);
213 CHECK(!is_active_);
214 is_active_ = true;
215 Thread* self = Thread::Current();
216 thread_running_gc_ = self;
217 Locks::mutator_lock_->AssertNotHeld(self);
218 {
219 ReaderMutexLock mu(self, *Locks::mutator_lock_);
220 InitializePhase();
221 // In case of forced evacuation, all regions are evacuated and hence no
222 // need to compute live_bytes.
223 if (use_generational_cc_ && !young_gen_ && !force_evacuate_all_) {
224 MarkingPhase();
225 }
226 }
227 if (kUseBakerReadBarrier && kGrayDirtyImmuneObjects) {
228 // Switch to read barrier mark entrypoints before we gray the objects. This is required in case
229 // a mutator sees a gray bit and dispatches on the entrypoint. (b/37876887).
230 ActivateReadBarrierEntrypoints();
231 // Gray dirty immune objects concurrently to reduce GC pause times. We re-process gray cards in
232 // the pause.
233 ReaderMutexLock mu(self, *Locks::mutator_lock_);
234 GrayAllDirtyImmuneObjects();
235 }
236 FlipThreadRoots();
237 {
238 ReaderMutexLock mu(self, *Locks::mutator_lock_);
239 CopyingPhase();
240 }
241 // Verify no from space refs. This causes a pause.
242 if (kEnableNoFromSpaceRefsVerification) {
243 TimingLogger::ScopedTiming split("(Paused)VerifyNoFromSpaceReferences", GetTimings());
244 ScopedPause pause(this, false);
245 CheckEmptyMarkStack();
246 if (kVerboseMode) {
247 LOG(INFO) << "Verifying no from-space refs";
248 }
249 VerifyNoFromSpaceReferences();
250 if (kVerboseMode) {
251 LOG(INFO) << "Done verifying no from-space refs";
252 }
253 CheckEmptyMarkStack();
254 }
255 {
256 ReaderMutexLock mu(self, *Locks::mutator_lock_);
257 ReclaimPhase();
258 }
259 FinishPhase();
260 CHECK(is_active_);
261 is_active_ = false;
262 thread_running_gc_ = nullptr;
263 }
264
265 class ConcurrentCopying::ActivateReadBarrierEntrypointsCheckpoint : public Closure {
266 public:
ActivateReadBarrierEntrypointsCheckpoint(ConcurrentCopying * concurrent_copying)267 explicit ActivateReadBarrierEntrypointsCheckpoint(ConcurrentCopying* concurrent_copying)
268 : concurrent_copying_(concurrent_copying) {}
269
Run(Thread * thread)270 void Run(Thread* thread) override NO_THREAD_SAFETY_ANALYSIS {
271 // Note: self is not necessarily equal to thread since thread may be suspended.
272 Thread* self = Thread::Current();
273 DCHECK(thread == self ||
274 thread->IsSuspended() ||
275 thread->GetState() == ThreadState::kWaitingPerformingGc)
276 << thread->GetState() << " thread " << thread << " self " << self;
277 // Switch to the read barrier entrypoints.
278 thread->SetReadBarrierEntrypoints();
279 // If thread is a running mutator, then act on behalf of the garbage collector.
280 // See the code in ThreadList::RunCheckpoint.
281 concurrent_copying_->GetBarrier().Pass(self);
282 }
283
284 private:
285 ConcurrentCopying* const concurrent_copying_;
286 };
287
288 class ConcurrentCopying::ActivateReadBarrierEntrypointsCallback : public Closure {
289 public:
ActivateReadBarrierEntrypointsCallback(ConcurrentCopying * concurrent_copying)290 explicit ActivateReadBarrierEntrypointsCallback(ConcurrentCopying* concurrent_copying)
291 : concurrent_copying_(concurrent_copying) {}
292
Run(Thread * self)293 void Run([[maybe_unused]] Thread* self) override REQUIRES(Locks::thread_list_lock_) {
294 // This needs to run under the thread_list_lock_ critical section in ThreadList::RunCheckpoint()
295 // to avoid a race with ThreadList::Register().
296 CHECK(!concurrent_copying_->is_using_read_barrier_entrypoints_);
297 concurrent_copying_->is_using_read_barrier_entrypoints_ = true;
298 }
299
300 private:
301 ConcurrentCopying* const concurrent_copying_;
302 };
303
ActivateReadBarrierEntrypoints()304 void ConcurrentCopying::ActivateReadBarrierEntrypoints() {
305 Thread* const self = Thread::Current();
306 ActivateReadBarrierEntrypointsCheckpoint checkpoint(this);
307 ThreadList* thread_list = Runtime::Current()->GetThreadList();
308 gc_barrier_->Init(self, 0);
309 ActivateReadBarrierEntrypointsCallback callback(this);
310 const size_t barrier_count = thread_list->RunCheckpoint(&checkpoint, &callback);
311 // If there are no threads to wait which implies that all the checkpoint functions are finished,
312 // then no need to release the mutator lock.
313 if (barrier_count == 0) {
314 return;
315 }
316 ScopedThreadStateChange tsc(self, ThreadState::kWaitingForCheckPointsToRun);
317 gc_barrier_->Increment(self, barrier_count);
318 }
319
CreateInterRegionRefBitmaps()320 void ConcurrentCopying::CreateInterRegionRefBitmaps() {
321 DCHECK(use_generational_cc_);
322 DCHECK(!region_space_inter_region_bitmap_.IsValid());
323 DCHECK(!non_moving_space_inter_region_bitmap_.IsValid());
324 DCHECK(region_space_ != nullptr);
325 DCHECK(heap_->non_moving_space_ != nullptr);
326 // Region-space
327 region_space_inter_region_bitmap_ = accounting::ContinuousSpaceBitmap::Create(
328 "region-space inter region ref bitmap",
329 reinterpret_cast<uint8_t*>(region_space_->Begin()),
330 region_space_->Limit() - region_space_->Begin());
331 CHECK(region_space_inter_region_bitmap_.IsValid())
332 << "Couldn't allocate region-space inter region ref bitmap";
333
334 // non-moving-space
335 non_moving_space_inter_region_bitmap_ = accounting::ContinuousSpaceBitmap::Create(
336 "non-moving-space inter region ref bitmap",
337 reinterpret_cast<uint8_t*>(heap_->non_moving_space_->Begin()),
338 heap_->non_moving_space_->Limit() - heap_->non_moving_space_->Begin());
339 CHECK(non_moving_space_inter_region_bitmap_.IsValid())
340 << "Couldn't allocate non-moving-space inter region ref bitmap";
341 }
342
BindBitmaps()343 void ConcurrentCopying::BindBitmaps() {
344 Thread* self = Thread::Current();
345 WriterMutexLock mu(self, *Locks::heap_bitmap_lock_);
346 // Mark all of the spaces we never collect as immune.
347 for (const auto& space : heap_->GetContinuousSpaces()) {
348 if (space->GetGcRetentionPolicy() == space::kGcRetentionPolicyNeverCollect ||
349 space->GetGcRetentionPolicy() == space::kGcRetentionPolicyFullCollect) {
350 CHECK(space->IsZygoteSpace() || space->IsImageSpace());
351 immune_spaces_.AddSpace(space);
352 } else {
353 CHECK(!space->IsZygoteSpace());
354 CHECK(!space->IsImageSpace());
355 CHECK(space == region_space_ || space == heap_->non_moving_space_);
356 if (use_generational_cc_) {
357 if (space == region_space_) {
358 region_space_bitmap_ = region_space_->GetMarkBitmap();
359 } else if (young_gen_ && space->IsContinuousMemMapAllocSpace()) {
360 DCHECK_EQ(space->GetGcRetentionPolicy(), space::kGcRetentionPolicyAlwaysCollect);
361 space->AsContinuousMemMapAllocSpace()->BindLiveToMarkBitmap();
362 }
363 if (young_gen_) {
364 // Age all of the cards for the region space so that we know which evac regions to scan.
365 heap_->GetCardTable()->ModifyCardsAtomic(space->Begin(),
366 space->End(),
367 AgeCardVisitor(),
368 VoidFunctor());
369 } else {
370 // In a full-heap GC cycle, the card-table corresponding to region-space and
371 // non-moving space can be cleared, because this cycle only needs to
372 // capture writes during the marking phase of this cycle to catch
373 // objects that skipped marking due to heap mutation. Furthermore,
374 // if the next GC is a young-gen cycle, then it only needs writes to
375 // be captured after the thread-flip of this GC cycle, as that is when
376 // the young-gen for the next GC cycle starts getting populated.
377 heap_->GetCardTable()->ClearCardRange(space->Begin(), space->Limit());
378 }
379 } else {
380 if (space == region_space_) {
381 // It is OK to clear the bitmap with mutators running since the only place it is read is
382 // VisitObjects which has exclusion with CC.
383 region_space_bitmap_ = region_space_->GetMarkBitmap();
384 region_space_bitmap_->Clear(ShouldEagerlyReleaseMemoryToOS());
385 }
386 }
387 }
388 }
389 if (use_generational_cc_ && young_gen_) {
390 for (const auto& space : GetHeap()->GetDiscontinuousSpaces()) {
391 CHECK(space->IsLargeObjectSpace());
392 space->AsLargeObjectSpace()->CopyLiveToMarked();
393 }
394 }
395 }
396
InitializePhase()397 void ConcurrentCopying::InitializePhase() {
398 TimingLogger::ScopedTiming split("InitializePhase", GetTimings());
399 num_bytes_allocated_before_gc_ = static_cast<int64_t>(heap_->GetBytesAllocated());
400 if (kVerboseMode) {
401 LOG(INFO) << "GC InitializePhase";
402 LOG(INFO) << "Region-space : " << reinterpret_cast<void*>(region_space_->Begin()) << "-"
403 << reinterpret_cast<void*>(region_space_->Limit());
404 }
405 CheckEmptyMarkStack();
406 rb_mark_bit_stack_full_ = false;
407 mark_from_read_barrier_measurements_ = measure_read_barrier_slow_path_;
408 if (measure_read_barrier_slow_path_) {
409 rb_slow_path_ns_.store(0, std::memory_order_relaxed);
410 rb_slow_path_count_.store(0, std::memory_order_relaxed);
411 rb_slow_path_count_gc_.store(0, std::memory_order_relaxed);
412 }
413
414 immune_spaces_.Reset();
415 bytes_moved_.store(0, std::memory_order_relaxed);
416 objects_moved_.store(0, std::memory_order_relaxed);
417 bytes_moved_gc_thread_ = 0;
418 objects_moved_gc_thread_ = 0;
419 bytes_scanned_ = 0;
420 GcCause gc_cause = GetCurrentIteration()->GetGcCause();
421
422 force_evacuate_all_ = false;
423 if (!use_generational_cc_ || !young_gen_) {
424 if (gc_cause == kGcCauseExplicit ||
425 gc_cause == kGcCauseCollectorTransition ||
426 GetCurrentIteration()->GetClearSoftReferences()) {
427 force_evacuate_all_ = true;
428 }
429 }
430 if (kUseBakerReadBarrier) {
431 updated_all_immune_objects_.store(false, std::memory_order_relaxed);
432 // GC may gray immune objects in the thread flip.
433 gc_grays_immune_objects_ = true;
434 if (kIsDebugBuild) {
435 MutexLock mu(Thread::Current(), immune_gray_stack_lock_);
436 DCHECK(immune_gray_stack_.empty());
437 }
438 }
439 if (use_generational_cc_) {
440 done_scanning_.store(false, std::memory_order_release);
441 }
442 BindBitmaps();
443 if (kVerboseMode) {
444 LOG(INFO) << "young_gen=" << std::boolalpha << young_gen_ << std::noboolalpha;
445 LOG(INFO) << "force_evacuate_all=" << std::boolalpha << force_evacuate_all_ << std::noboolalpha;
446 LOG(INFO) << "Largest immune region: " << immune_spaces_.GetLargestImmuneRegion().Begin()
447 << "-" << immune_spaces_.GetLargestImmuneRegion().End();
448 for (space::ContinuousSpace* space : immune_spaces_.GetSpaces()) {
449 LOG(INFO) << "Immune space: " << *space;
450 }
451 LOG(INFO) << "GC end of InitializePhase";
452 }
453 if (use_generational_cc_ && !young_gen_) {
454 region_space_bitmap_->Clear(ShouldEagerlyReleaseMemoryToOS());
455 }
456 mark_stack_mode_.store(ConcurrentCopying::kMarkStackModeThreadLocal, std::memory_order_release);
457 // Mark all of the zygote large objects without graying them.
458 MarkZygoteLargeObjects();
459 }
460
461 // Used to switch the thread roots of a thread from from-space refs to to-space refs.
462 class ConcurrentCopying::ThreadFlipVisitor : public Closure, public RootVisitor {
463 public:
ThreadFlipVisitor(ConcurrentCopying * concurrent_copying,bool use_tlab)464 ThreadFlipVisitor(ConcurrentCopying* concurrent_copying, bool use_tlab)
465 : concurrent_copying_(concurrent_copying), use_tlab_(use_tlab) {
466 }
467
Run(Thread * thread)468 void Run(Thread* thread) override REQUIRES_SHARED(Locks::mutator_lock_) {
469 // We are either running this in the target thread, or the target thread will wait for us
470 // before switching back to runnable.
471 Thread* self = Thread::Current();
472 CHECK(thread == self || thread->GetState() != ThreadState::kRunnable)
473 << thread->GetState() << " thread " << thread << " self " << self;
474 thread->SetIsGcMarkingAndUpdateEntrypoints(true);
475 if (use_tlab_ && thread->HasTlab()) {
476 concurrent_copying_->region_space_->RevokeThreadLocalBuffers(thread, /*reuse=*/ false);
477 }
478 if (kUseThreadLocalAllocationStack) {
479 thread->RevokeThreadLocalAllocationStack();
480 }
481 ReaderMutexLock mu(self, *Locks::heap_bitmap_lock_);
482 // We can use the non-CAS VisitRoots functions below because we update thread-local GC roots
483 // only.
484 thread->VisitRoots(this, kVisitRootFlagAllRoots);
485 }
486
VisitRoots(mirror::Object *** roots,size_t count,const RootInfo & info)487 void VisitRoots(mirror::Object*** roots,
488 size_t count,
489 [[maybe_unused]] const RootInfo& info) override
490 REQUIRES_SHARED(Locks::mutator_lock_) {
491 Thread* self = Thread::Current();
492 for (size_t i = 0; i < count; ++i) {
493 mirror::Object** root = roots[i];
494 mirror::Object* ref = *root;
495 if (ref != nullptr) {
496 mirror::Object* to_ref = concurrent_copying_->Mark(self, ref);
497 if (to_ref != ref) {
498 *root = to_ref;
499 }
500 }
501 }
502 }
503
VisitRoots(mirror::CompressedReference<mirror::Object> ** roots,size_t count,const RootInfo & info)504 void VisitRoots(mirror::CompressedReference<mirror::Object>** roots,
505 size_t count,
506 [[maybe_unused]] const RootInfo& info) override
507 REQUIRES_SHARED(Locks::mutator_lock_) {
508 Thread* self = Thread::Current();
509 for (size_t i = 0; i < count; ++i) {
510 mirror::CompressedReference<mirror::Object>* const root = roots[i];
511 if (!root->IsNull()) {
512 mirror::Object* ref = root->AsMirrorPtr();
513 mirror::Object* to_ref = concurrent_copying_->Mark(self, ref);
514 if (to_ref != ref) {
515 root->Assign(to_ref);
516 }
517 }
518 }
519 }
520
521 private:
522 ConcurrentCopying* const concurrent_copying_;
523 const bool use_tlab_;
524 };
525
526 // Called back from Runtime::FlipThreadRoots() during a pause.
527 class ConcurrentCopying::FlipCallback : public Closure {
528 public:
FlipCallback(ConcurrentCopying * concurrent_copying)529 explicit FlipCallback(ConcurrentCopying* concurrent_copying)
530 : concurrent_copying_(concurrent_copying) {
531 }
532
Run(Thread * thread)533 void Run(Thread* thread) override REQUIRES(Locks::mutator_lock_) {
534 ConcurrentCopying* cc = concurrent_copying_;
535 TimingLogger::ScopedTiming split("(Paused)FlipCallback", cc->GetTimings());
536 // Note: self is not necessarily equal to thread since thread may be suspended.
537 Thread* self = Thread::Current();
538 if (kVerifyNoMissingCardMarks && cc->young_gen_) {
539 cc->VerifyNoMissingCardMarks();
540 }
541 CHECK_EQ(thread, self);
542 Locks::mutator_lock_->AssertExclusiveHeld(self);
543 space::RegionSpace::EvacMode evac_mode = space::RegionSpace::kEvacModeLivePercentNewlyAllocated;
544 if (cc->young_gen_) {
545 CHECK(!cc->force_evacuate_all_);
546 evac_mode = space::RegionSpace::kEvacModeNewlyAllocated;
547 } else if (cc->force_evacuate_all_) {
548 evac_mode = space::RegionSpace::kEvacModeForceAll;
549 }
550 {
551 TimingLogger::ScopedTiming split2("(Paused)SetFromSpace", cc->GetTimings());
552 // Only change live bytes for 1-phase full heap CC, that is if we are either not running in
553 // generational-mode, or it's an 'evacuate-all' mode GC.
554 cc->region_space_->SetFromSpace(
555 cc->rb_table_,
556 evac_mode,
557 /*clear_live_bytes=*/ !cc->use_generational_cc_ || cc->force_evacuate_all_);
558 }
559 cc->SwapStacks();
560 if (ConcurrentCopying::kEnableFromSpaceAccountingCheck) {
561 cc->RecordLiveStackFreezeSize(self);
562 cc->from_space_num_bytes_at_first_pause_ = cc->region_space_->GetBytesAllocated();
563 }
564 cc->is_marking_ = true;
565 if (kIsDebugBuild && !cc->use_generational_cc_) {
566 cc->region_space_->AssertAllRegionLiveBytesZeroOrCleared();
567 }
568 Runtime* runtime = Runtime::Current();
569 if (UNLIKELY(runtime->IsActiveTransaction())) {
570 CHECK(runtime->IsAotCompiler());
571 TimingLogger::ScopedTiming split3("(Paused)VisitTransactionRoots", cc->GetTimings());
572 runtime->GetClassLinker()->VisitTransactionRoots(cc);
573 }
574 if (kUseBakerReadBarrier && kGrayDirtyImmuneObjects) {
575 cc->GrayAllNewlyDirtyImmuneObjects();
576 if (kIsDebugBuild) {
577 // Check that all non-gray immune objects only reference immune objects.
578 cc->VerifyGrayImmuneObjects();
579 }
580 }
581 ObjPtr<mirror::Class> java_lang_Object =
582 GetClassRoot<mirror::Object, kWithoutReadBarrier>(runtime->GetClassLinker());
583 DCHECK(java_lang_Object != nullptr);
584 cc->java_lang_Object_ = down_cast<mirror::Class*>(cc->Mark(thread, java_lang_Object.Ptr()));
585 }
586
587 private:
588 ConcurrentCopying* const concurrent_copying_;
589 };
590
591 class ConcurrentCopying::VerifyGrayImmuneObjectsVisitor {
592 public:
VerifyGrayImmuneObjectsVisitor(ConcurrentCopying * collector)593 explicit VerifyGrayImmuneObjectsVisitor(ConcurrentCopying* collector)
594 : collector_(collector) {}
595
operator ()(ObjPtr<mirror::Object> obj,MemberOffset offset,bool) const596 void operator()(ObjPtr<mirror::Object> obj, MemberOffset offset, bool /* is_static */)
597 const ALWAYS_INLINE REQUIRES_SHARED(Locks::mutator_lock_)
598 REQUIRES_SHARED(Locks::heap_bitmap_lock_) {
599 CheckReference(obj->GetFieldObject<mirror::Object, kVerifyNone, kWithoutReadBarrier>(offset),
600 obj, offset);
601 }
602
operator ()(ObjPtr<mirror::Class> klass,ObjPtr<mirror::Reference> ref) const603 void operator()(ObjPtr<mirror::Class> klass, ObjPtr<mirror::Reference> ref) const
604 REQUIRES_SHARED(Locks::mutator_lock_) ALWAYS_INLINE {
605 CHECK(klass->IsTypeOfReferenceClass());
606 CheckReference(ref->GetReferent<kWithoutReadBarrier>(),
607 ref,
608 mirror::Reference::ReferentOffset());
609 }
610
VisitRootIfNonNull(mirror::CompressedReference<mirror::Object> * root) const611 void VisitRootIfNonNull(mirror::CompressedReference<mirror::Object>* root) const
612 ALWAYS_INLINE
613 REQUIRES_SHARED(Locks::mutator_lock_) {
614 if (!root->IsNull()) {
615 VisitRoot(root);
616 }
617 }
618
VisitRoot(mirror::CompressedReference<mirror::Object> * root) const619 void VisitRoot(mirror::CompressedReference<mirror::Object>* root) const
620 ALWAYS_INLINE
621 REQUIRES_SHARED(Locks::mutator_lock_) {
622 CheckReference(root->AsMirrorPtr(), nullptr, MemberOffset(0));
623 }
624
625 private:
626 ConcurrentCopying* const collector_;
627
CheckReference(ObjPtr<mirror::Object> ref,ObjPtr<mirror::Object> holder,MemberOffset offset) const628 void CheckReference(ObjPtr<mirror::Object> ref,
629 ObjPtr<mirror::Object> holder,
630 MemberOffset offset) const
631 REQUIRES_SHARED(Locks::mutator_lock_) {
632 if (ref != nullptr) {
633 if (!collector_->immune_spaces_.ContainsObject(ref.Ptr())) {
634 // Not immune, must be a zygote large object.
635 space::LargeObjectSpace* large_object_space =
636 Runtime::Current()->GetHeap()->GetLargeObjectsSpace();
637 CHECK(large_object_space->Contains(ref.Ptr()) &&
638 large_object_space->IsZygoteLargeObject(Thread::Current(), ref.Ptr()))
639 << "Non gray object references non immune, non zygote large object "<< ref << " "
640 << mirror::Object::PrettyTypeOf(ref) << " in holder " << holder << " "
641 << mirror::Object::PrettyTypeOf(holder) << " offset=" << offset.Uint32Value();
642 } else {
643 // Make sure the large object class is immune since we will never scan the large object.
644 CHECK(collector_->immune_spaces_.ContainsObject(
645 ref->GetClass<kVerifyNone, kWithoutReadBarrier>()));
646 }
647 }
648 }
649 };
650
VerifyGrayImmuneObjects()651 void ConcurrentCopying::VerifyGrayImmuneObjects() {
652 TimingLogger::ScopedTiming split(__FUNCTION__, GetTimings());
653 for (auto& space : immune_spaces_.GetSpaces()) {
654 DCHECK(space->IsImageSpace() || space->IsZygoteSpace());
655 accounting::ContinuousSpaceBitmap* live_bitmap = space->GetLiveBitmap();
656 VerifyGrayImmuneObjectsVisitor visitor(this);
657 live_bitmap->VisitMarkedRange(reinterpret_cast<uintptr_t>(space->Begin()),
658 reinterpret_cast<uintptr_t>(space->Limit()),
659 [&visitor](mirror::Object* obj)
660 REQUIRES_SHARED(Locks::mutator_lock_) {
661 // If an object is not gray, it should only have references to things in the immune spaces.
662 if (obj->GetReadBarrierState() != ReadBarrier::GrayState()) {
663 obj->VisitReferences</*kVisitNativeRoots=*/true,
664 kDefaultVerifyFlags,
665 kWithoutReadBarrier>(visitor, visitor);
666 }
667 });
668 }
669 }
670
671 class ConcurrentCopying::VerifyNoMissingCardMarkVisitor {
672 public:
VerifyNoMissingCardMarkVisitor(ConcurrentCopying * cc,ObjPtr<mirror::Object> holder)673 VerifyNoMissingCardMarkVisitor(ConcurrentCopying* cc, ObjPtr<mirror::Object> holder)
674 : cc_(cc),
675 holder_(holder) {}
676
operator ()(ObjPtr<mirror::Object> obj,MemberOffset offset,bool is_static) const677 void operator()(ObjPtr<mirror::Object> obj,
678 MemberOffset offset,
679 [[maybe_unused]] bool is_static) const
680 REQUIRES_SHARED(Locks::mutator_lock_) ALWAYS_INLINE {
681 if (offset.Uint32Value() != mirror::Object::ClassOffset().Uint32Value()) {
682 CheckReference(obj->GetFieldObject<mirror::Object, kDefaultVerifyFlags, kWithoutReadBarrier>(
683 offset), offset.Uint32Value());
684 }
685 }
operator ()(ObjPtr<mirror::Class> klass,ObjPtr<mirror::Reference> ref) const686 void operator()(ObjPtr<mirror::Class> klass,
687 ObjPtr<mirror::Reference> ref) const
688 REQUIRES_SHARED(Locks::mutator_lock_) ALWAYS_INLINE {
689 CHECK(klass->IsTypeOfReferenceClass());
690 this->operator()(ref, mirror::Reference::ReferentOffset(), false);
691 }
692
VisitRootIfNonNull(mirror::CompressedReference<mirror::Object> * root) const693 void VisitRootIfNonNull(mirror::CompressedReference<mirror::Object>* root) const
694 REQUIRES_SHARED(Locks::mutator_lock_) {
695 if (!root->IsNull()) {
696 VisitRoot(root);
697 }
698 }
699
VisitRoot(mirror::CompressedReference<mirror::Object> * root) const700 void VisitRoot(mirror::CompressedReference<mirror::Object>* root) const
701 REQUIRES_SHARED(Locks::mutator_lock_) {
702 CheckReference(root->AsMirrorPtr());
703 }
704
CheckReference(mirror::Object * ref,int32_t offset=-1) const705 void CheckReference(mirror::Object* ref, int32_t offset = -1) const
706 REQUIRES_SHARED(Locks::mutator_lock_) {
707 if (ref != nullptr && cc_->region_space_->IsInNewlyAllocatedRegion(ref)) {
708 LOG(FATAL_WITHOUT_ABORT)
709 << holder_->PrettyTypeOf() << "(" << holder_.Ptr() << ") references object "
710 << ref->PrettyTypeOf() << "(" << ref << ") in newly allocated region at offset=" << offset;
711 LOG(FATAL_WITHOUT_ABORT) << "time=" << cc_->region_space_->Time();
712 constexpr const char* kIndent = " ";
713 LOG(FATAL_WITHOUT_ABORT) << cc_->DumpReferenceInfo(holder_.Ptr(), "holder_", kIndent);
714 LOG(FATAL_WITHOUT_ABORT) << cc_->DumpReferenceInfo(ref, "ref", kIndent);
715 LOG(FATAL) << "Unexpected reference to newly allocated region.";
716 }
717 }
718
719 private:
720 ConcurrentCopying* const cc_;
721 const ObjPtr<mirror::Object> holder_;
722 };
723
VerifyNoMissingCardMarks()724 void ConcurrentCopying::VerifyNoMissingCardMarks() {
725 auto visitor = [&](mirror::Object* obj)
726 REQUIRES(Locks::mutator_lock_)
727 REQUIRES(!mark_stack_lock_) {
728 // Objects on clean cards should never have references to newly allocated regions. Note
729 // that aged cards are also not clean.
730 if (heap_->GetCardTable()->GetCard(obj) == gc::accounting::CardTable::kCardClean) {
731 VerifyNoMissingCardMarkVisitor internal_visitor(this, /*holder=*/ obj);
732 obj->VisitReferences</*kVisitNativeRoots=*/true, kVerifyNone, kWithoutReadBarrier>(
733 internal_visitor, internal_visitor);
734 }
735 };
736 TimingLogger::ScopedTiming split(__FUNCTION__, GetTimings());
737 region_space_->Walk(visitor);
738 {
739 ReaderMutexLock rmu(Thread::Current(), *Locks::heap_bitmap_lock_);
740 heap_->GetLiveBitmap()->Visit(visitor);
741 }
742 }
743
744 // Switch threads that from from-space to to-space refs. Forward/mark the thread roots.
FlipThreadRoots()745 void ConcurrentCopying::FlipThreadRoots() {
746 TimingLogger::ScopedTiming split("FlipThreadRoots", GetTimings());
747 if (kVerboseMode || heap_->dump_region_info_before_gc_) {
748 LOG(INFO) << "time=" << region_space_->Time();
749 region_space_->DumpNonFreeRegions(LOG_STREAM(INFO));
750 }
751 Thread* self = Thread::Current();
752 Locks::mutator_lock_->AssertNotHeld(self);
753 ThreadFlipVisitor thread_flip_visitor(this, heap_->use_tlab_);
754 FlipCallback flip_callback(this);
755
756 Runtime::Current()->GetThreadList()->FlipThreadRoots(
757 &thread_flip_visitor, &flip_callback, this, GetHeap()->GetGcPauseListener());
758
759 is_asserting_to_space_invariant_ = true;
760 QuasiAtomic::ThreadFenceForConstructor(); // TODO: Remove?
761 if (kVerboseMode) {
762 LOG(INFO) << "time=" << region_space_->Time();
763 region_space_->DumpNonFreeRegions(LOG_STREAM(INFO));
764 LOG(INFO) << "GC end of FlipThreadRoots";
765 }
766 }
767
768 template <bool kConcurrent>
769 class ConcurrentCopying::GrayImmuneObjectVisitor {
770 public:
GrayImmuneObjectVisitor(Thread * self)771 explicit GrayImmuneObjectVisitor(Thread* self) : self_(self) {}
772
operator ()(mirror::Object * obj) const773 ALWAYS_INLINE void operator()(mirror::Object* obj) const REQUIRES_SHARED(Locks::mutator_lock_) {
774 if (kUseBakerReadBarrier && obj->GetReadBarrierState() == ReadBarrier::NonGrayState()) {
775 if (kConcurrent) {
776 Locks::mutator_lock_->AssertSharedHeld(self_);
777 obj->AtomicSetReadBarrierState(ReadBarrier::NonGrayState(), ReadBarrier::GrayState());
778 // Mod union table VisitObjects may visit the same object multiple times so we can't check
779 // the result of the atomic set.
780 } else {
781 Locks::mutator_lock_->AssertExclusiveHeld(self_);
782 obj->SetReadBarrierState(ReadBarrier::GrayState());
783 }
784 }
785 }
786
Callback(mirror::Object * obj,void * arg)787 static void Callback(mirror::Object* obj, void* arg) REQUIRES_SHARED(Locks::mutator_lock_) {
788 reinterpret_cast<GrayImmuneObjectVisitor<kConcurrent>*>(arg)->operator()(obj);
789 }
790
791 private:
792 Thread* const self_;
793 };
794
GrayAllDirtyImmuneObjects()795 void ConcurrentCopying::GrayAllDirtyImmuneObjects() {
796 TimingLogger::ScopedTiming split("GrayAllDirtyImmuneObjects", GetTimings());
797 accounting::CardTable* const card_table = heap_->GetCardTable();
798 Thread* const self = Thread::Current();
799 using VisitorType = GrayImmuneObjectVisitor</* kIsConcurrent= */ true>;
800 VisitorType visitor(self);
801 WriterMutexLock mu(self, *Locks::heap_bitmap_lock_);
802 for (space::ContinuousSpace* space : immune_spaces_.GetSpaces()) {
803 DCHECK(space->IsImageSpace() || space->IsZygoteSpace());
804 accounting::ModUnionTable* table = heap_->FindModUnionTableFromSpace(space);
805 // Mark all the objects on dirty cards since these may point to objects in other space.
806 // Once these are marked, the GC will eventually clear them later.
807 // Table is non null for boot image and zygote spaces. It is only null for application image
808 // spaces.
809 if (table != nullptr) {
810 table->ProcessCards();
811 table->VisitObjects(&VisitorType::Callback, &visitor);
812 // Don't clear cards here since we need to rescan in the pause. If we cleared the cards here,
813 // there would be races with the mutator marking new cards.
814 } else {
815 // Keep cards aged if we don't have a mod-union table since we may need to scan them in future
816 // GCs. This case is for app images.
817 card_table->ModifyCardsAtomic(
818 space->Begin(),
819 space->End(),
820 [](uint8_t card) {
821 return (card != gc::accounting::CardTable::kCardClean)
822 ? gc::accounting::CardTable::kCardAged
823 : card;
824 },
825 /* card modified visitor */ VoidFunctor());
826 card_table->Scan</*kClearCard=*/ false>(space->GetMarkBitmap(),
827 space->Begin(),
828 space->End(),
829 visitor,
830 gc::accounting::CardTable::kCardAged);
831 }
832 }
833 }
834
GrayAllNewlyDirtyImmuneObjects()835 void ConcurrentCopying::GrayAllNewlyDirtyImmuneObjects() {
836 TimingLogger::ScopedTiming split("(Paused)GrayAllNewlyDirtyImmuneObjects", GetTimings());
837 accounting::CardTable* const card_table = heap_->GetCardTable();
838 using VisitorType = GrayImmuneObjectVisitor</* kIsConcurrent= */ false>;
839 Thread* const self = Thread::Current();
840 VisitorType visitor(self);
841 WriterMutexLock mu(Thread::Current(), *Locks::heap_bitmap_lock_);
842 for (space::ContinuousSpace* space : immune_spaces_.GetSpaces()) {
843 DCHECK(space->IsImageSpace() || space->IsZygoteSpace());
844 accounting::ModUnionTable* table = heap_->FindModUnionTableFromSpace(space);
845
846 // Don't need to scan aged cards since we did these before the pause. Note that scanning cards
847 // also handles the mod-union table cards.
848 card_table->Scan</*kClearCard=*/ false>(space->GetMarkBitmap(),
849 space->Begin(),
850 space->End(),
851 visitor,
852 gc::accounting::CardTable::kCardDirty);
853 if (table != nullptr) {
854 // Add the cards to the mod-union table so that we can clear cards to save RAM.
855 table->ProcessCards();
856 TimingLogger::ScopedTiming split2("(Paused)ClearCards", GetTimings());
857 card_table->ClearCardRange(space->Begin(),
858 AlignDown(space->End(), accounting::CardTable::kCardSize));
859 }
860 }
861 // Since all of the objects that may point to other spaces are gray, we can avoid all the read
862 // barriers in the immune spaces.
863 updated_all_immune_objects_.store(true, std::memory_order_relaxed);
864 }
865
SwapStacks()866 void ConcurrentCopying::SwapStacks() {
867 heap_->SwapStacks();
868 }
869
RecordLiveStackFreezeSize(Thread * self)870 void ConcurrentCopying::RecordLiveStackFreezeSize(Thread* self) {
871 WriterMutexLock mu(self, *Locks::heap_bitmap_lock_);
872 live_stack_freeze_size_ = heap_->GetLiveStack()->Size();
873 }
874
875 // Used to visit objects in the immune spaces.
ScanImmuneObject(mirror::Object * obj)876 inline void ConcurrentCopying::ScanImmuneObject(mirror::Object* obj) {
877 DCHECK(obj != nullptr);
878 DCHECK(immune_spaces_.ContainsObject(obj));
879 // Update the fields without graying it or pushing it onto the mark stack.
880 if (use_generational_cc_ && young_gen_) {
881 // Young GC does not care about references to unevac space. It is safe to not gray these as
882 // long as scan immune objects happens after scanning the dirty cards.
883 Scan<true>(obj);
884 } else {
885 Scan<false>(obj);
886 }
887 }
888
889 class ConcurrentCopying::ImmuneSpaceScanObjVisitor {
890 public:
ImmuneSpaceScanObjVisitor(ConcurrentCopying * cc)891 explicit ImmuneSpaceScanObjVisitor(ConcurrentCopying* cc)
892 : collector_(cc) {}
893
operator ()(mirror::Object * obj) const894 ALWAYS_INLINE void operator()(mirror::Object* obj) const REQUIRES_SHARED(Locks::mutator_lock_) {
895 if (kUseBakerReadBarrier && kGrayDirtyImmuneObjects) {
896 // Only need to scan gray objects.
897 if (obj->GetReadBarrierState() == ReadBarrier::GrayState()) {
898 collector_->ScanImmuneObject(obj);
899 // Done scanning the object, go back to black (non-gray). Release order
900 // required to ensure that stores of to-space references done by
901 // ScanImmuneObject() are visible before state change.
902 bool success = obj->AtomicSetReadBarrierState(
903 ReadBarrier::GrayState(), ReadBarrier::NonGrayState(), std::memory_order_release);
904 CHECK(success)
905 << Runtime::Current()->GetHeap()->GetVerification()->DumpObjectInfo(obj, "failed CAS");
906 }
907 } else {
908 collector_->ScanImmuneObject(obj);
909 }
910 }
911
Callback(mirror::Object * obj,void * arg)912 static void Callback(mirror::Object* obj, void* arg) REQUIRES_SHARED(Locks::mutator_lock_) {
913 reinterpret_cast<ImmuneSpaceScanObjVisitor*>(arg)->operator()(obj);
914 }
915
916 private:
917 ConcurrentCopying* const collector_;
918 };
919
920 template <bool kAtomicTestAndSet>
921 class ConcurrentCopying::CaptureRootsForMarkingVisitor : public RootVisitor {
922 public:
CaptureRootsForMarkingVisitor(ConcurrentCopying * cc,Thread * self)923 explicit CaptureRootsForMarkingVisitor(ConcurrentCopying* cc, Thread* self)
924 : collector_(cc), self_(self) {}
925
VisitRoots(mirror::Object *** roots,size_t count,const RootInfo & info)926 void VisitRoots(mirror::Object*** roots,
927 size_t count,
928 [[maybe_unused]] const RootInfo& info) override
929 REQUIRES_SHARED(Locks::mutator_lock_) {
930 for (size_t i = 0; i < count; ++i) {
931 mirror::Object** root = roots[i];
932 mirror::Object* ref = *root;
933 if (ref != nullptr && !collector_->TestAndSetMarkBitForRef<kAtomicTestAndSet>(ref)) {
934 collector_->PushOntoMarkStack(self_, ref);
935 }
936 }
937 }
938
VisitRoots(mirror::CompressedReference<mirror::Object> ** roots,size_t count,const RootInfo & info)939 void VisitRoots(mirror::CompressedReference<mirror::Object>** roots,
940 size_t count,
941 [[maybe_unused]] const RootInfo& info) override
942 REQUIRES_SHARED(Locks::mutator_lock_) {
943 for (size_t i = 0; i < count; ++i) {
944 mirror::CompressedReference<mirror::Object>* const root = roots[i];
945 if (!root->IsNull()) {
946 mirror::Object* ref = root->AsMirrorPtr();
947 if (!collector_->TestAndSetMarkBitForRef<kAtomicTestAndSet>(ref)) {
948 collector_->PushOntoMarkStack(self_, ref);
949 }
950 }
951 }
952 }
953
954 private:
955 ConcurrentCopying* const collector_;
956 Thread* const self_;
957 };
958
959 class ConcurrentCopying::RevokeThreadLocalMarkStackCheckpoint : public Closure {
960 public:
RevokeThreadLocalMarkStackCheckpoint(ConcurrentCopying * concurrent_copying,bool disable_weak_ref_access)961 RevokeThreadLocalMarkStackCheckpoint(ConcurrentCopying* concurrent_copying,
962 bool disable_weak_ref_access)
963 : concurrent_copying_(concurrent_copying),
964 disable_weak_ref_access_(disable_weak_ref_access) {
965 }
966
Run(Thread * thread)967 void Run(Thread* thread) override NO_THREAD_SAFETY_ANALYSIS {
968 // Note: self is not necessarily equal to thread since thread may be suspended.
969 Thread* const self = Thread::Current();
970 CHECK(thread == self ||
971 thread->IsSuspended() ||
972 thread->GetState() == ThreadState::kWaitingPerformingGc)
973 << thread->GetState() << " thread " << thread << " self " << self;
974 // Revoke thread local mark stacks.
975 {
976 MutexLock mu(self, concurrent_copying_->mark_stack_lock_);
977 accounting::AtomicStack<mirror::Object>* tl_mark_stack = thread->GetThreadLocalMarkStack();
978 if (tl_mark_stack != nullptr) {
979 concurrent_copying_->revoked_mark_stacks_.push_back(tl_mark_stack);
980 thread->SetThreadLocalMarkStack(nullptr);
981 }
982 }
983 // Disable weak ref access.
984 if (disable_weak_ref_access_) {
985 thread->SetWeakRefAccessEnabled(false);
986 }
987 // If thread is a running mutator, then act on behalf of the garbage collector.
988 // See the code in ThreadList::RunCheckpoint.
989 concurrent_copying_->GetBarrier().Pass(self);
990 }
991
992 protected:
993 ConcurrentCopying* const concurrent_copying_;
994
995 private:
996 const bool disable_weak_ref_access_;
997 };
998
999 class ConcurrentCopying::CaptureThreadRootsForMarkingAndCheckpoint :
1000 public RevokeThreadLocalMarkStackCheckpoint {
1001 public:
CaptureThreadRootsForMarkingAndCheckpoint(ConcurrentCopying * cc)1002 explicit CaptureThreadRootsForMarkingAndCheckpoint(ConcurrentCopying* cc) :
1003 RevokeThreadLocalMarkStackCheckpoint(cc, /* disable_weak_ref_access */ false) {}
1004
Run(Thread * thread)1005 void Run(Thread* thread) override
1006 REQUIRES_SHARED(Locks::mutator_lock_) {
1007 Thread* const self = Thread::Current();
1008 ReaderMutexLock mu(self, *Locks::heap_bitmap_lock_);
1009 // We can use the non-CAS VisitRoots functions below because we update thread-local GC roots
1010 // only.
1011 CaptureRootsForMarkingVisitor</*kAtomicTestAndSet*/ true> visitor(concurrent_copying_, self);
1012 thread->VisitRoots(&visitor, kVisitRootFlagAllRoots);
1013 // If thread_running_gc_ performed the root visit then its thread-local
1014 // mark-stack should be null as we directly push to gc_mark_stack_.
1015 CHECK(self == thread || self->GetThreadLocalMarkStack() == nullptr);
1016 // Barrier handling is done in the base class' Run() below.
1017 RevokeThreadLocalMarkStackCheckpoint::Run(thread);
1018 }
1019 };
1020
CaptureThreadRootsForMarking()1021 void ConcurrentCopying::CaptureThreadRootsForMarking() {
1022 TimingLogger::ScopedTiming split("CaptureThreadRootsForMarking", GetTimings());
1023 if (kVerboseMode) {
1024 LOG(INFO) << "time=" << region_space_->Time();
1025 region_space_->DumpNonFreeRegions(LOG_STREAM(INFO));
1026 }
1027 Thread* const self = Thread::Current();
1028 CaptureThreadRootsForMarkingAndCheckpoint check_point(this);
1029 ThreadList* thread_list = Runtime::Current()->GetThreadList();
1030 gc_barrier_->Init(self, 0);
1031 size_t barrier_count = thread_list->RunCheckpoint(&check_point, /* callback */ nullptr);
1032 // If there are no threads to wait which implys that all the checkpoint functions are finished,
1033 // then no need to release the mutator lock.
1034 if (barrier_count == 0) {
1035 return;
1036 }
1037 Locks::mutator_lock_->SharedUnlock(self);
1038 {
1039 ScopedThreadStateChange tsc(self, ThreadState::kWaitingForCheckPointsToRun);
1040 gc_barrier_->Increment(self, barrier_count);
1041 }
1042 Locks::mutator_lock_->SharedLock(self);
1043 if (kVerboseMode) {
1044 LOG(INFO) << "time=" << region_space_->Time();
1045 region_space_->DumpNonFreeRegions(LOG_STREAM(INFO));
1046 LOG(INFO) << "GC end of CaptureThreadRootsForMarking";
1047 }
1048 }
1049
1050 // Used to scan ref fields of an object.
1051 template <bool kHandleInterRegionRefs>
1052 class ConcurrentCopying::ComputeLiveBytesAndMarkRefFieldsVisitor {
1053 public:
ComputeLiveBytesAndMarkRefFieldsVisitor(ConcurrentCopying * collector,size_t obj_region_idx)1054 explicit ComputeLiveBytesAndMarkRefFieldsVisitor(ConcurrentCopying* collector,
1055 size_t obj_region_idx)
1056 : collector_(collector),
1057 obj_region_idx_(obj_region_idx),
1058 contains_inter_region_idx_(false) {}
1059
operator ()(mirror::Object * obj,MemberOffset offset,bool) const1060 void operator()(mirror::Object* obj, MemberOffset offset, bool /* is_static */) const
1061 ALWAYS_INLINE
1062 REQUIRES_SHARED(Locks::mutator_lock_)
1063 REQUIRES_SHARED(Locks::heap_bitmap_lock_) {
1064 DCHECK_EQ(collector_->RegionSpace()->RegionIdxForRef(obj), obj_region_idx_);
1065 DCHECK(kHandleInterRegionRefs || collector_->immune_spaces_.ContainsObject(obj));
1066 mirror::Object* ref =
1067 obj->GetFieldObject<mirror::Object, kVerifyNone, kWithoutReadBarrier>(offset);
1068 // TODO(lokeshgidra): Remove the following condition once b/173676071 is fixed.
1069 if (UNLIKELY(ref == nullptr && offset == mirror::Object::ClassOffset())) {
1070 // It has been verified as a race condition (see b/173676071)! After a small
1071 // wait when we reload the class pointer, it turns out to be a valid class
1072 // object. So as a workaround, we can continue execution and log an error
1073 // that this happened.
1074 for (size_t i = 0; i < 1000; i++) {
1075 // Wait for 1ms at a time. Don't wait for more than 1 second in total.
1076 usleep(1000);
1077 ref = obj->GetClass<kVerifyNone, kWithoutReadBarrier>();
1078 if (ref != nullptr) {
1079 LOG(ERROR) << "klass pointer for obj: "
1080 << obj << " (" << mirror::Object::PrettyTypeOf(obj)
1081 << ") found to be null first. Reloading after a small wait fetched klass: "
1082 << ref << " (" << mirror::Object::PrettyTypeOf(ref) << ")";
1083 break;
1084 }
1085 }
1086
1087 if (UNLIKELY(ref == nullptr)) {
1088 // It must be heap corruption. Remove memory protection and dump data.
1089 collector_->region_space_->Unprotect();
1090 LOG(FATAL_WITHOUT_ABORT) << "klass pointer for ref: " << obj << " found to be null.";
1091 collector_->heap_->GetVerification()->LogHeapCorruption(obj, offset, ref, /* fatal */ true);
1092 }
1093 }
1094 CheckReference(ref);
1095 }
1096
operator ()(ObjPtr<mirror::Class> klass,ObjPtr<mirror::Reference> ref) const1097 void operator()(ObjPtr<mirror::Class> klass, ObjPtr<mirror::Reference> ref) const
1098 REQUIRES_SHARED(Locks::mutator_lock_) ALWAYS_INLINE {
1099 DCHECK(klass->IsTypeOfReferenceClass());
1100 // If the referent is not null, then we must re-visit the object during
1101 // copying phase to enqueue it for delayed processing and setting
1102 // read-barrier state to gray to ensure that call to GetReferent() triggers
1103 // the read-barrier. We use same data structure that is used to remember
1104 // objects with inter-region refs for this purpose too.
1105 if (kHandleInterRegionRefs
1106 && !contains_inter_region_idx_
1107 && ref->AsReference()->GetReferent<kWithoutReadBarrier>() != nullptr) {
1108 contains_inter_region_idx_ = true;
1109 }
1110 }
1111
VisitRootIfNonNull(mirror::CompressedReference<mirror::Object> * root) const1112 void VisitRootIfNonNull(mirror::CompressedReference<mirror::Object>* root) const
1113 ALWAYS_INLINE
1114 REQUIRES_SHARED(Locks::mutator_lock_) {
1115 if (!root->IsNull()) {
1116 VisitRoot(root);
1117 }
1118 }
1119
VisitRoot(mirror::CompressedReference<mirror::Object> * root) const1120 void VisitRoot(mirror::CompressedReference<mirror::Object>* root) const
1121 ALWAYS_INLINE
1122 REQUIRES_SHARED(Locks::mutator_lock_) {
1123 CheckReference(root->AsMirrorPtr());
1124 }
1125
ContainsInterRegionRefs() const1126 bool ContainsInterRegionRefs() const ALWAYS_INLINE REQUIRES_SHARED(Locks::mutator_lock_) {
1127 return contains_inter_region_idx_;
1128 }
1129
1130 private:
CheckReference(mirror::Object * ref) const1131 void CheckReference(mirror::Object* ref) const
1132 REQUIRES_SHARED(Locks::mutator_lock_) {
1133 if (ref == nullptr) {
1134 // Nothing to do.
1135 return;
1136 }
1137 if (!collector_->TestAndSetMarkBitForRef(ref)) {
1138 collector_->PushOntoLocalMarkStack(ref);
1139 }
1140 if (kHandleInterRegionRefs && !contains_inter_region_idx_) {
1141 size_t ref_region_idx = collector_->RegionSpace()->RegionIdxForRef(ref);
1142 // If a region-space object refers to an outside object, we will have a
1143 // mismatch of region idx, but the object need not be re-visited in
1144 // copying phase.
1145 if (ref_region_idx != static_cast<size_t>(-1) && obj_region_idx_ != ref_region_idx) {
1146 contains_inter_region_idx_ = true;
1147 }
1148 }
1149 }
1150
1151 ConcurrentCopying* const collector_;
1152 const size_t obj_region_idx_;
1153 mutable bool contains_inter_region_idx_;
1154 };
1155
AddLiveBytesAndScanRef(mirror::Object * ref)1156 void ConcurrentCopying::AddLiveBytesAndScanRef(mirror::Object* ref) {
1157 DCHECK(ref != nullptr);
1158 DCHECK(!immune_spaces_.ContainsObject(ref));
1159 DCHECK(TestMarkBitmapForRef(ref));
1160 size_t obj_region_idx = static_cast<size_t>(-1);
1161 if (LIKELY(region_space_->HasAddress(ref))) {
1162 obj_region_idx = region_space_->RegionIdxForRefUnchecked(ref);
1163 // Add live bytes to the corresponding region
1164 if (!region_space_->IsRegionNewlyAllocated(obj_region_idx)) {
1165 // Newly Allocated regions are always chosen for evacuation. So no need
1166 // to update live_bytes_.
1167 size_t obj_size = ref->SizeOf<kDefaultVerifyFlags>();
1168 size_t alloc_size = RoundUp(obj_size, space::RegionSpace::kAlignment);
1169 region_space_->AddLiveBytes(ref, alloc_size);
1170 }
1171 }
1172 ComputeLiveBytesAndMarkRefFieldsVisitor</*kHandleInterRegionRefs*/ true>
1173 visitor(this, obj_region_idx);
1174 ref->VisitReferences</*kVisitNativeRoots=*/ true, kDefaultVerifyFlags, kWithoutReadBarrier>(
1175 visitor, visitor);
1176 // Mark the corresponding card dirty if the object contains any
1177 // inter-region reference.
1178 if (visitor.ContainsInterRegionRefs()) {
1179 if (obj_region_idx == static_cast<size_t>(-1)) {
1180 // If an inter-region ref has been found in a non-region-space, then it
1181 // must be non-moving-space. This is because this function cannot be
1182 // called on a immune-space object, and a large-object-space object has
1183 // only class object reference, which is either in some immune-space, or
1184 // in non-moving-space.
1185 DCHECK(heap_->non_moving_space_->HasAddress(ref));
1186 non_moving_space_inter_region_bitmap_.Set(ref);
1187 } else {
1188 region_space_inter_region_bitmap_.Set(ref);
1189 }
1190 }
1191 }
1192
1193 template <bool kAtomic>
TestAndSetMarkBitForRef(mirror::Object * ref)1194 bool ConcurrentCopying::TestAndSetMarkBitForRef(mirror::Object* ref) {
1195 accounting::ContinuousSpaceBitmap* bitmap = nullptr;
1196 accounting::LargeObjectBitmap* los_bitmap = nullptr;
1197 if (LIKELY(region_space_->HasAddress(ref))) {
1198 bitmap = region_space_bitmap_;
1199 } else if (heap_->GetNonMovingSpace()->HasAddress(ref)) {
1200 bitmap = heap_->GetNonMovingSpace()->GetMarkBitmap();
1201 } else if (immune_spaces_.ContainsObject(ref)) {
1202 // References to immune space objects are always live.
1203 DCHECK(heap_mark_bitmap_->GetContinuousSpaceBitmap(ref)->Test(ref));
1204 return true;
1205 } else {
1206 // Should be a large object. Must be aligned and the LOS must exist.
1207 if (kIsDebugBuild && (!IsAlignedParam(ref, space::LargeObjectSpace::ObjectAlignment()) ||
1208 heap_->GetLargeObjectsSpace() == nullptr)) {
1209 // It must be heap corruption. Remove memory protection and dump data.
1210 region_space_->Unprotect();
1211 heap_->GetVerification()->LogHeapCorruption(/* obj */ nullptr,
1212 MemberOffset(0),
1213 ref,
1214 /* fatal */ true);
1215 }
1216 los_bitmap = heap_->GetLargeObjectsSpace()->GetMarkBitmap();
1217 }
1218 if (kAtomic) {
1219 return (bitmap != nullptr) ? bitmap->AtomicTestAndSet(ref) : los_bitmap->AtomicTestAndSet(ref);
1220 } else {
1221 return (bitmap != nullptr) ? bitmap->Set(ref) : los_bitmap->Set(ref);
1222 }
1223 }
1224
TestMarkBitmapForRef(mirror::Object * ref)1225 bool ConcurrentCopying::TestMarkBitmapForRef(mirror::Object* ref) {
1226 if (LIKELY(region_space_->HasAddress(ref))) {
1227 return region_space_bitmap_->Test(ref);
1228 } else if (heap_->GetNonMovingSpace()->HasAddress(ref)) {
1229 return heap_->GetNonMovingSpace()->GetMarkBitmap()->Test(ref);
1230 } else if (immune_spaces_.ContainsObject(ref)) {
1231 // References to immune space objects are always live.
1232 DCHECK(heap_mark_bitmap_->GetContinuousSpaceBitmap(ref)->Test(ref));
1233 return true;
1234 } else {
1235 // Should be a large object. Must be aligned and the LOS must exist.
1236 if (kIsDebugBuild && (!IsAlignedParam(ref, space::LargeObjectSpace::ObjectAlignment()) ||
1237 heap_->GetLargeObjectsSpace() == nullptr)) {
1238 // It must be heap corruption. Remove memory protection and dump data.
1239 region_space_->Unprotect();
1240 heap_->GetVerification()->LogHeapCorruption(/* obj */ nullptr,
1241 MemberOffset(0),
1242 ref,
1243 /* fatal */ true);
1244 }
1245 return heap_->GetLargeObjectsSpace()->GetMarkBitmap()->Test(ref);
1246 }
1247 }
1248
PushOntoLocalMarkStack(mirror::Object * ref)1249 void ConcurrentCopying::PushOntoLocalMarkStack(mirror::Object* ref) {
1250 if (kIsDebugBuild) {
1251 Thread *self = Thread::Current();
1252 DCHECK_EQ(thread_running_gc_, self);
1253 DCHECK(self->GetThreadLocalMarkStack() == nullptr);
1254 }
1255 DCHECK_EQ(mark_stack_mode_.load(std::memory_order_relaxed), kMarkStackModeThreadLocal);
1256 if (UNLIKELY(gc_mark_stack_->IsFull())) {
1257 ExpandGcMarkStack();
1258 }
1259 gc_mark_stack_->PushBack(ref);
1260 }
1261
ProcessMarkStackForMarkingAndComputeLiveBytes()1262 void ConcurrentCopying::ProcessMarkStackForMarkingAndComputeLiveBytes() {
1263 // Process thread-local mark stack containing thread roots
1264 ProcessThreadLocalMarkStacks(/* disable_weak_ref_access */ false,
1265 /* checkpoint_callback */ nullptr,
1266 [this] (mirror::Object* ref)
1267 REQUIRES_SHARED(Locks::mutator_lock_) {
1268 AddLiveBytesAndScanRef(ref);
1269 });
1270 {
1271 MutexLock mu(thread_running_gc_, mark_stack_lock_);
1272 CHECK(revoked_mark_stacks_.empty());
1273 CHECK_EQ(pooled_mark_stacks_.size(), kMarkStackPoolSize);
1274 }
1275
1276 while (!gc_mark_stack_->IsEmpty()) {
1277 mirror::Object* ref = gc_mark_stack_->PopBack();
1278 AddLiveBytesAndScanRef(ref);
1279 }
1280 }
1281
1282 class ConcurrentCopying::ImmuneSpaceCaptureRefsVisitor {
1283 public:
ImmuneSpaceCaptureRefsVisitor(ConcurrentCopying * cc)1284 explicit ImmuneSpaceCaptureRefsVisitor(ConcurrentCopying* cc) : collector_(cc) {}
1285
operator ()(mirror::Object * obj) const1286 ALWAYS_INLINE void operator()(mirror::Object* obj) const REQUIRES_SHARED(Locks::mutator_lock_) {
1287 ComputeLiveBytesAndMarkRefFieldsVisitor</*kHandleInterRegionRefs*/ false>
1288 visitor(collector_, /*obj_region_idx*/ static_cast<size_t>(-1));
1289 obj->VisitReferences</*kVisitNativeRoots=*/true, kDefaultVerifyFlags, kWithoutReadBarrier>(
1290 visitor, visitor);
1291 }
1292
Callback(mirror::Object * obj,void * arg)1293 static void Callback(mirror::Object* obj, void* arg) REQUIRES_SHARED(Locks::mutator_lock_) {
1294 reinterpret_cast<ImmuneSpaceCaptureRefsVisitor*>(arg)->operator()(obj);
1295 }
1296
1297 private:
1298 ConcurrentCopying* const collector_;
1299 };
1300
1301 /* Invariants for two-phase CC
1302 * ===========================
1303 * A) Definitions
1304 * ---------------
1305 * 1) Black: marked in bitmap, rb_state is non-gray, and not in mark stack
1306 * 2) Black-clean: marked in bitmap, and corresponding card is clean/aged
1307 * 3) Black-dirty: marked in bitmap, and corresponding card is dirty
1308 * 4) Gray: marked in bitmap, and exists in mark stack
1309 * 5) Gray-dirty: marked in bitmap, rb_state is gray, corresponding card is
1310 * dirty, and exists in mark stack
1311 * 6) White: unmarked in bitmap, rb_state is non-gray, and not in mark stack
1312 *
1313 * B) Before marking phase
1314 * -----------------------
1315 * 1) All objects are white
1316 * 2) Cards are either clean or aged (cannot be asserted without a STW pause)
1317 * 3) Mark bitmap is cleared
1318 * 4) Mark stack is empty
1319 *
1320 * C) During marking phase
1321 * ------------------------
1322 * 1) If a black object holds an inter-region or white reference, then its
1323 * corresponding card is dirty. In other words, it changes from being
1324 * black-clean to black-dirty
1325 * 2) No black-clean object points to a white object
1326 *
1327 * D) After marking phase
1328 * -----------------------
1329 * 1) There are no gray objects
1330 * 2) All newly allocated objects are in from space
1331 * 3) No white object can be reachable, directly or otherwise, from a
1332 * black-clean object
1333 *
1334 * E) During copying phase
1335 * ------------------------
1336 * 1) Mutators cannot observe white and black-dirty objects
1337 * 2) New allocations are in to-space (newly allocated regions are part of to-space)
1338 * 3) An object in mark stack must have its rb_state = Gray
1339 *
1340 * F) During card table scan
1341 * --------------------------
1342 * 1) Referents corresponding to root references are gray or in to-space
1343 * 2) Every path from an object that is read or written by a mutator during
1344 * this period to a dirty black object goes through some gray object.
1345 * Mutators preserve this by graying black objects as needed during this
1346 * period. Ensures that a mutator never encounters a black dirty object.
1347 *
1348 * G) After card table scan
1349 * ------------------------
1350 * 1) There are no black-dirty objects
1351 * 2) Referents corresponding to root references are gray, black-clean or in
1352 * to-space
1353 *
1354 * H) After copying phase
1355 * -----------------------
1356 * 1) Mark stack is empty
1357 * 2) No references into evacuated from-space
1358 * 3) No reference to an object which is unmarked and is also not in newly
1359 * allocated region. In other words, no reference to white objects.
1360 */
1361
MarkingPhase()1362 void ConcurrentCopying::MarkingPhase() {
1363 TimingLogger::ScopedTiming split("MarkingPhase", GetTimings());
1364 if (kVerboseMode) {
1365 LOG(INFO) << "GC MarkingPhase";
1366 }
1367 accounting::CardTable* const card_table = heap_->GetCardTable();
1368 Thread* const self = Thread::Current();
1369 CHECK_EQ(self, thread_running_gc_);
1370 // Clear live_bytes_ of every non-free region, except the ones that are newly
1371 // allocated.
1372 region_space_->SetAllRegionLiveBytesZero();
1373 if (kIsDebugBuild) {
1374 region_space_->AssertAllRegionLiveBytesZeroOrCleared();
1375 }
1376 // Scan immune spaces
1377 {
1378 TimingLogger::ScopedTiming split2("ScanImmuneSpaces", GetTimings());
1379 for (auto& space : immune_spaces_.GetSpaces()) {
1380 DCHECK(space->IsImageSpace() || space->IsZygoteSpace());
1381 accounting::ContinuousSpaceBitmap* live_bitmap = space->GetLiveBitmap();
1382 accounting::ModUnionTable* table = heap_->FindModUnionTableFromSpace(space);
1383 ImmuneSpaceCaptureRefsVisitor visitor(this);
1384 if (table != nullptr) {
1385 table->VisitObjects(ImmuneSpaceCaptureRefsVisitor::Callback, &visitor);
1386 } else {
1387 WriterMutexLock rmu(Thread::Current(), *Locks::heap_bitmap_lock_);
1388 card_table->Scan<false>(
1389 live_bitmap,
1390 space->Begin(),
1391 space->Limit(),
1392 visitor,
1393 accounting::CardTable::kCardDirty - 1);
1394 }
1395 }
1396 }
1397 // Scan runtime roots
1398 {
1399 TimingLogger::ScopedTiming split2("VisitConcurrentRoots", GetTimings());
1400 CaptureRootsForMarkingVisitor visitor(this, self);
1401 Runtime::Current()->VisitConcurrentRoots(&visitor, kVisitRootFlagAllRoots);
1402 }
1403 {
1404 // TODO: don't visit the transaction roots if it's not active.
1405 TimingLogger::ScopedTiming split2("VisitNonThreadRoots", GetTimings());
1406 CaptureRootsForMarkingVisitor visitor(this, self);
1407 Runtime::Current()->VisitNonThreadRoots(&visitor);
1408 }
1409 // Capture thread roots
1410 CaptureThreadRootsForMarking();
1411 // Process mark stack
1412 ProcessMarkStackForMarkingAndComputeLiveBytes();
1413
1414 if (kVerboseMode) {
1415 LOG(INFO) << "GC end of MarkingPhase";
1416 }
1417 }
1418
1419 template <bool kNoUnEvac>
ScanDirtyObject(mirror::Object * obj)1420 void ConcurrentCopying::ScanDirtyObject(mirror::Object* obj) {
1421 Scan<kNoUnEvac>(obj);
1422 // Set the read-barrier state of a reference-type object to gray if its
1423 // referent is not marked yet. This is to ensure that if GetReferent() is
1424 // called, it triggers the read-barrier to process the referent before use.
1425 if (UNLIKELY((obj->GetClass<kVerifyNone, kWithoutReadBarrier>()->IsTypeOfReferenceClass()))) {
1426 mirror::Object* referent =
1427 obj->AsReference<kVerifyNone, kWithoutReadBarrier>()->GetReferent<kWithoutReadBarrier>();
1428 if (referent != nullptr && !IsInToSpace(referent)) {
1429 obj->AtomicSetReadBarrierState(ReadBarrier::NonGrayState(), ReadBarrier::GrayState());
1430 }
1431 }
1432 }
1433
1434 // Concurrently mark roots that are guarded by read barriers and process the mark stack.
CopyingPhase()1435 void ConcurrentCopying::CopyingPhase() {
1436 TimingLogger::ScopedTiming split("CopyingPhase", GetTimings());
1437 if (kVerboseMode) {
1438 LOG(INFO) << "GC CopyingPhase";
1439 }
1440 Thread* self = Thread::Current();
1441 accounting::CardTable* const card_table = heap_->GetCardTable();
1442 if (kIsDebugBuild) {
1443 MutexLock mu(self, *Locks::thread_list_lock_);
1444 CHECK(weak_ref_access_enabled_);
1445 }
1446
1447 // Scan immune spaces.
1448 // Update all the fields in the immune spaces first without graying the objects so that we
1449 // minimize dirty pages in the immune spaces. Note mutators can concurrently access and gray some
1450 // of the objects.
1451 if (kUseBakerReadBarrier) {
1452 gc_grays_immune_objects_ = false;
1453 }
1454 if (use_generational_cc_) {
1455 if (kVerboseMode) {
1456 LOG(INFO) << "GC ScanCardsForSpace";
1457 }
1458 TimingLogger::ScopedTiming split2("ScanCardsForSpace", GetTimings());
1459 WriterMutexLock rmu(Thread::Current(), *Locks::heap_bitmap_lock_);
1460 CHECK(!done_scanning_.load(std::memory_order_relaxed));
1461 if (kIsDebugBuild) {
1462 // Leave some time for mutators to race ahead to try and find races between the GC card
1463 // scanning and mutators reading references.
1464 usleep(10 * 1000);
1465 }
1466 for (space::ContinuousSpace* space : GetHeap()->GetContinuousSpaces()) {
1467 if (space->IsImageSpace() || space->IsZygoteSpace()) {
1468 // Image and zygote spaces are already handled since we gray the objects in the pause.
1469 continue;
1470 }
1471 // Scan all of the objects on dirty cards in unevac from space, and non moving space. These
1472 // are from previous GCs (or from marking phase of 2-phase full GC) and may reference things
1473 // in the from space.
1474 //
1475 // Note that we do not need to process the large-object space (the only discontinuous space)
1476 // as it contains only large string objects and large primitive array objects, that have no
1477 // reference to other objects, except their class. There is no need to scan these large
1478 // objects, as the String class and the primitive array classes are expected to never move
1479 // during a collection:
1480 // - In the case where we run with a boot image, these classes are part of the image space,
1481 // which is an immune space.
1482 // - In the case where we run without a boot image, these classes are allocated in the
1483 // non-moving space (see art::ClassLinker::InitWithoutImage).
1484 card_table->Scan<false>(
1485 space->GetMarkBitmap(),
1486 space->Begin(),
1487 space->End(),
1488 [this, space](mirror::Object* obj)
1489 REQUIRES(Locks::heap_bitmap_lock_)
1490 REQUIRES_SHARED(Locks::mutator_lock_) {
1491 // TODO: This code may be refactored to avoid scanning object while
1492 // done_scanning_ is false by setting rb_state to gray, and pushing the
1493 // object on mark stack. However, it will also require clearing the
1494 // corresponding mark-bit and, for region space objects,
1495 // decrementing the object's size from the corresponding region's
1496 // live_bytes.
1497 if (young_gen_) {
1498 // Don't push or gray unevac refs.
1499 if (kIsDebugBuild && space == region_space_) {
1500 // We may get unevac large objects.
1501 if (!region_space_->IsInUnevacFromSpace(obj)) {
1502 CHECK(region_space_bitmap_->Test(obj));
1503 region_space_->DumpRegionForObject(LOG_STREAM(FATAL_WITHOUT_ABORT), obj);
1504 LOG(FATAL) << "Scanning " << obj << " not in unevac space";
1505 }
1506 }
1507 ScanDirtyObject</*kNoUnEvac*/ true>(obj);
1508 } else if (space != region_space_) {
1509 DCHECK(space == heap_->non_moving_space_);
1510 // We need to process un-evac references as they may be unprocessed,
1511 // if they skipped the marking phase due to heap mutation.
1512 ScanDirtyObject</*kNoUnEvac*/ false>(obj);
1513 non_moving_space_inter_region_bitmap_.Clear(obj);
1514 } else if (region_space_->IsInUnevacFromSpace(obj)) {
1515 ScanDirtyObject</*kNoUnEvac*/ false>(obj);
1516 region_space_inter_region_bitmap_.Clear(obj);
1517 }
1518 },
1519 accounting::CardTable::kCardAged);
1520
1521 if (!young_gen_) {
1522 auto visitor = [this](mirror::Object* obj) REQUIRES_SHARED(Locks::mutator_lock_) {
1523 // We don't need to process un-evac references as any unprocessed
1524 // ones will be taken care of in the card-table scan above.
1525 ScanDirtyObject</*kNoUnEvac*/ true>(obj);
1526 };
1527 if (space == region_space_) {
1528 region_space_->ScanUnevacFromSpace(®ion_space_inter_region_bitmap_, visitor);
1529 } else {
1530 DCHECK(space == heap_->non_moving_space_);
1531 non_moving_space_inter_region_bitmap_.VisitMarkedRange(
1532 reinterpret_cast<uintptr_t>(space->Begin()),
1533 reinterpret_cast<uintptr_t>(space->End()),
1534 visitor);
1535 }
1536 }
1537 }
1538 // Done scanning unevac space.
1539 done_scanning_.store(true, std::memory_order_release);
1540 // NOTE: inter-region-ref bitmaps can be cleared here to release memory, if needed.
1541 // Currently we do it in ReclaimPhase().
1542 if (kVerboseMode) {
1543 LOG(INFO) << "GC end of ScanCardsForSpace";
1544 }
1545 }
1546 {
1547 // For a sticky-bit collection, this phase needs to be after the card scanning since the
1548 // mutator may read an unevac space object out of an image object. If the image object is no
1549 // longer gray it will trigger a read barrier for the unevac space object.
1550 TimingLogger::ScopedTiming split2("ScanImmuneSpaces", GetTimings());
1551 for (auto& space : immune_spaces_.GetSpaces()) {
1552 DCHECK(space->IsImageSpace() || space->IsZygoteSpace());
1553 accounting::ContinuousSpaceBitmap* live_bitmap = space->GetLiveBitmap();
1554 accounting::ModUnionTable* table = heap_->FindModUnionTableFromSpace(space);
1555 ImmuneSpaceScanObjVisitor visitor(this);
1556 if (kUseBakerReadBarrier && kGrayDirtyImmuneObjects && table != nullptr) {
1557 table->VisitObjects(ImmuneSpaceScanObjVisitor::Callback, &visitor);
1558 } else {
1559 WriterMutexLock rmu(Thread::Current(), *Locks::heap_bitmap_lock_);
1560 card_table->Scan<false>(
1561 live_bitmap,
1562 space->Begin(),
1563 space->Limit(),
1564 visitor,
1565 accounting::CardTable::kCardDirty - 1);
1566 }
1567 }
1568 }
1569 if (kUseBakerReadBarrier) {
1570 // This release fence makes the field updates in the above loop visible before allowing mutator
1571 // getting access to immune objects without graying it first.
1572 updated_all_immune_objects_.store(true, std::memory_order_release);
1573 // Now "un-gray" (conceptually blacken) immune objects concurrently accessed and grayed by
1574 // mutators. We can't do this in the above loop because we would incorrectly disable the read
1575 // barrier by un-graying (conceptually blackening) an object which may point to an unscanned,
1576 // white object, breaking the to-space invariant (a mutator shall never observe a from-space
1577 // (white) object).
1578 //
1579 // Make sure no mutators are in the middle of marking an immune object before un-graying
1580 // (blackening) immune objects.
1581 IssueEmptyCheckpoint();
1582 MutexLock mu(Thread::Current(), immune_gray_stack_lock_);
1583 if (kVerboseMode) {
1584 LOG(INFO) << "immune gray stack size=" << immune_gray_stack_.size();
1585 }
1586 for (mirror::Object* obj : immune_gray_stack_) {
1587 DCHECK_EQ(obj->GetReadBarrierState(), ReadBarrier::GrayState());
1588 bool success = obj->AtomicSetReadBarrierState(ReadBarrier::GrayState(),
1589 ReadBarrier::NonGrayState());
1590 DCHECK(success);
1591 }
1592 immune_gray_stack_.clear();
1593 }
1594
1595 {
1596 TimingLogger::ScopedTiming split2("VisitConcurrentRoots", GetTimings());
1597 Runtime::Current()->VisitConcurrentRoots(this, kVisitRootFlagAllRoots);
1598 }
1599 {
1600 // TODO: don't visit the transaction roots if it's not active.
1601 TimingLogger::ScopedTiming split5("VisitNonThreadRoots", GetTimings());
1602 Runtime::Current()->VisitNonThreadRoots(this);
1603 }
1604
1605 {
1606 TimingLogger::ScopedTiming split7("Process mark stacks and References", GetTimings());
1607
1608 // Process the mark stack once in the thread local stack mode. This marks most of the live
1609 // objects, aside from weak ref accesses with read barriers (Reference::GetReferent() and
1610 // system weaks) that may happen concurrently while we are processing the mark stack and newly
1611 // mark/gray objects and push refs on the mark stack.
1612 ProcessMarkStack();
1613
1614 ReferenceProcessor* rp = GetHeap()->GetReferenceProcessor();
1615 bool clear_soft_references = GetCurrentIteration()->GetClearSoftReferences();
1616 rp->Setup(self, this, /*concurrent=*/ true, clear_soft_references);
1617 if (!clear_soft_references) {
1618 // Forward as many SoftReferences as possible before inhibiting reference access.
1619 rp->ForwardSoftReferences(GetTimings());
1620 }
1621
1622 // We transition through three mark stack modes (thread-local, shared, GC-exclusive). The
1623 // primary reasons are that we need to use a checkpoint to process thread-local mark
1624 // stacks, but after we disable weak refs accesses, we can't use a checkpoint due to a deadlock
1625 // issue because running threads potentially blocking at WaitHoldingLocks, and that once we
1626 // reach the point where we process weak references, we can avoid using a lock when accessing
1627 // the GC mark stack, which makes mark stack processing more efficient.
1628
1629 // Switch to the shared mark stack mode. That is, revoke and process thread-local mark stacks
1630 // for the last time before transitioning to the shared mark stack mode, which would process new
1631 // refs that may have been concurrently pushed onto the mark stack during the ProcessMarkStack()
1632 // call above. At the same time, disable weak ref accesses using a per-thread flag. It's
1633 // important to do these together so that we can ensure that mutators won't
1634 // newly gray objects and push new refs onto the mark stack due to weak ref accesses and
1635 // mutators safely transition to the shared mark stack mode (without leaving unprocessed refs on
1636 // the thread-local mark stacks), without a race. This is why we use a thread-local weak ref
1637 // access flag Thread::tls32_.weak_ref_access_enabled_ instead of the global ones.
1638 // We must use a stop-the-world pause to disable weak ref access. A checkpoint may lead to a
1639 // deadlock if one mutator acquires a low-level mutex and then gets blocked while accessing
1640 // a weak-ref (after participating in the checkpoint), and another mutator indefinitely waits
1641 // for the mutex before it participates in the checkpoint. Consequently, the gc-thread blocks
1642 // forever as the checkpoint never finishes (See runtime/mutator_gc_coord.md).
1643 SwitchToSharedMarkStackMode();
1644 CHECK(!self->GetWeakRefAccessEnabled());
1645
1646 // Now that weak refs accesses are disabled, once we exhaust the shared mark stack again here
1647 // (which may be non-empty if there were refs found on thread-local mark stacks during the above
1648 // SwitchToSharedMarkStackMode() call), we won't have new refs to process, that is, mutators
1649 // (via read barriers) have no way to produce any more refs to process. Marking converges once
1650 // before we process weak refs below.
1651 ProcessMarkStack();
1652 CheckEmptyMarkStack();
1653
1654 // Switch to the GC exclusive mark stack mode so that we can process the mark stack without a
1655 // lock from this point on.
1656 SwitchToGcExclusiveMarkStackMode();
1657 CheckEmptyMarkStack();
1658 if (kVerboseMode) {
1659 LOG(INFO) << "ProcessReferences";
1660 }
1661 // Process weak references. This also marks through finalizers. Although
1662 // reference processing is "disabled", some accesses will proceed once we've ensured that
1663 // objects directly reachable by the mutator are marked, i.e. before we mark through
1664 // finalizers.
1665 ProcessReferences(self);
1666 CheckEmptyMarkStack();
1667 // JNI WeakGlobalRefs and most other system weaks cannot be processed until we're done marking
1668 // through finalizers, since such references to finalizer-reachable objects must be preserved.
1669 if (kVerboseMode) {
1670 LOG(INFO) << "SweepSystemWeaks";
1671 }
1672 SweepSystemWeaks(self);
1673 CheckEmptyMarkStack();
1674 ReenableWeakRefAccess(self);
1675 if (kVerboseMode) {
1676 LOG(INFO) << "SweepSystemWeaks done";
1677 }
1678 // Marking is done. Disable marking.
1679 DisableMarking();
1680 CheckEmptyMarkStack();
1681 }
1682
1683 if (kIsDebugBuild) {
1684 MutexLock mu(self, *Locks::thread_list_lock_);
1685 CHECK(weak_ref_access_enabled_);
1686 }
1687 if (kVerboseMode) {
1688 LOG(INFO) << "GC end of CopyingPhase";
1689 }
1690 }
1691
ReenableWeakRefAccess(Thread * self)1692 void ConcurrentCopying::ReenableWeakRefAccess(Thread* self) {
1693 if (kVerboseMode) {
1694 LOG(INFO) << "ReenableWeakRefAccess";
1695 }
1696 // Iterate all threads (don't need to or can't use a checkpoint) and re-enable weak ref access.
1697 {
1698 MutexLock mu(self, *Locks::thread_list_lock_);
1699 weak_ref_access_enabled_ = true; // This is for new threads.
1700 std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList();
1701 for (Thread* thread : thread_list) {
1702 thread->SetWeakRefAccessEnabled(true);
1703 }
1704 }
1705 // Unblock blocking threads.
1706 GetHeap()->GetReferenceProcessor()->BroadcastForSlowPath(self);
1707 Runtime::Current()->BroadcastForNewSystemWeaks();
1708 }
1709
1710 class ConcurrentCopying::DisableMarkingCheckpoint : public Closure {
1711 public:
DisableMarkingCheckpoint(ConcurrentCopying * concurrent_copying)1712 explicit DisableMarkingCheckpoint(ConcurrentCopying* concurrent_copying)
1713 : concurrent_copying_(concurrent_copying) {
1714 }
1715
Run(Thread * thread)1716 void Run(Thread* thread) override NO_THREAD_SAFETY_ANALYSIS {
1717 // Note: self is not necessarily equal to thread since thread may be suspended.
1718 Thread* self = Thread::Current();
1719 DCHECK(thread == self ||
1720 thread->IsSuspended() ||
1721 thread->GetState() == ThreadState::kWaitingPerformingGc)
1722 << thread->GetState() << " thread " << thread << " self " << self;
1723 // We sweep interpreter caches here so that it can be done after all
1724 // reachable objects are marked and the mutators can sweep their caches
1725 // without synchronization.
1726 thread->SweepInterpreterCache(concurrent_copying_);
1727 // Disable the thread-local is_gc_marking flag.
1728 // Note a thread that has just started right before this checkpoint may have already this flag
1729 // set to false, which is ok.
1730 thread->SetIsGcMarkingAndUpdateEntrypoints(false);
1731 // If thread is a running mutator, then act on behalf of the garbage collector.
1732 // See the code in ThreadList::RunCheckpoint.
1733 concurrent_copying_->GetBarrier().Pass(self);
1734 }
1735
1736 private:
1737 ConcurrentCopying* const concurrent_copying_;
1738 };
1739
1740 class ConcurrentCopying::DisableMarkingCallback : public Closure {
1741 public:
DisableMarkingCallback(ConcurrentCopying * concurrent_copying)1742 explicit DisableMarkingCallback(ConcurrentCopying* concurrent_copying)
1743 : concurrent_copying_(concurrent_copying) {
1744 }
1745
Run(Thread * self)1746 void Run([[maybe_unused]] Thread* self) override REQUIRES(Locks::thread_list_lock_) {
1747 // This needs to run under the thread_list_lock_ critical section in ThreadList::RunCheckpoint()
1748 // to avoid a race with ThreadList::Register().
1749 CHECK(concurrent_copying_->is_marking_);
1750 concurrent_copying_->is_marking_ = false;
1751 if (kUseBakerReadBarrier && kGrayDirtyImmuneObjects) {
1752 CHECK(concurrent_copying_->is_using_read_barrier_entrypoints_);
1753 concurrent_copying_->is_using_read_barrier_entrypoints_ = false;
1754 } else {
1755 CHECK(!concurrent_copying_->is_using_read_barrier_entrypoints_);
1756 }
1757 }
1758
1759 private:
1760 ConcurrentCopying* const concurrent_copying_;
1761 };
1762
IssueDisableMarkingCheckpoint()1763 void ConcurrentCopying::IssueDisableMarkingCheckpoint() {
1764 Thread* self = Thread::Current();
1765 DisableMarkingCheckpoint check_point(this);
1766 ThreadList* thread_list = Runtime::Current()->GetThreadList();
1767 gc_barrier_->Init(self, 0);
1768 DisableMarkingCallback dmc(this);
1769 size_t barrier_count = thread_list->RunCheckpoint(&check_point, &dmc);
1770 // If there are no threads to wait which implies that all the checkpoint functions are finished,
1771 // then no need to release the mutator lock.
1772 if (barrier_count == 0) {
1773 return;
1774 }
1775 // Release locks then wait for all mutator threads to pass the barrier.
1776 Locks::mutator_lock_->SharedUnlock(self);
1777 {
1778 ScopedThreadStateChange tsc(self, ThreadState::kWaitingForCheckPointsToRun);
1779 gc_barrier_->Increment(self, barrier_count);
1780 }
1781 Locks::mutator_lock_->SharedLock(self);
1782 }
1783
DisableMarking()1784 void ConcurrentCopying::DisableMarking() {
1785 // Use a checkpoint to turn off the global is_marking and the thread-local is_gc_marking flags and
1786 // to ensure no threads are still in the middle of a read barrier which may have a from-space ref
1787 // cached in a local variable.
1788 IssueDisableMarkingCheckpoint();
1789 if (kUseTableLookupReadBarrier) {
1790 heap_->rb_table_->ClearAll();
1791 DCHECK(heap_->rb_table_->IsAllCleared());
1792 }
1793 if (kIsDebugBuild) {
1794 is_mark_stack_push_disallowed_.store(1, std::memory_order_relaxed);
1795 }
1796 mark_stack_mode_.store(kMarkStackModeOff, std::memory_order_release);
1797 }
1798
IssueEmptyCheckpoint()1799 void ConcurrentCopying::IssueEmptyCheckpoint() {
1800 Thread* self = Thread::Current();
1801 ThreadList* thread_list = Runtime::Current()->GetThreadList();
1802 // Release locks then wait for all mutator threads to pass the barrier.
1803 Locks::mutator_lock_->SharedUnlock(self);
1804 thread_list->RunEmptyCheckpoint();
1805 Locks::mutator_lock_->SharedLock(self);
1806 }
1807
ExpandGcMarkStack()1808 void ConcurrentCopying::ExpandGcMarkStack() {
1809 DCHECK(gc_mark_stack_->IsFull());
1810 const size_t new_size = gc_mark_stack_->Capacity() * 2;
1811 std::vector<StackReference<mirror::Object>> temp(gc_mark_stack_->Begin(),
1812 gc_mark_stack_->End());
1813 gc_mark_stack_->Resize(new_size);
1814 for (auto& ref : temp) {
1815 gc_mark_stack_->PushBack(ref.AsMirrorPtr());
1816 }
1817 DCHECK(!gc_mark_stack_->IsFull());
1818 }
1819
PushOntoMarkStack(Thread * const self,mirror::Object * to_ref)1820 void ConcurrentCopying::PushOntoMarkStack(Thread* const self, mirror::Object* to_ref) {
1821 DCHECK_EQ(is_mark_stack_push_disallowed_.load(std::memory_order_relaxed), 0)
1822 << " " << to_ref << " " << mirror::Object::PrettyTypeOf(to_ref);
1823 CHECK(thread_running_gc_ != nullptr);
1824 MarkStackMode mark_stack_mode = mark_stack_mode_.load(std::memory_order_acquire);
1825 if (LIKELY(mark_stack_mode == kMarkStackModeThreadLocal)) {
1826 if (LIKELY(self == thread_running_gc_)) {
1827 // If GC-running thread, use the GC mark stack instead of a thread-local mark stack.
1828 CHECK(self->GetThreadLocalMarkStack() == nullptr);
1829 if (UNLIKELY(gc_mark_stack_->IsFull())) {
1830 ExpandGcMarkStack();
1831 }
1832 gc_mark_stack_->PushBack(to_ref);
1833 } else {
1834 // Otherwise, use a thread-local mark stack.
1835 accounting::AtomicStack<mirror::Object>* tl_mark_stack = self->GetThreadLocalMarkStack();
1836 if (UNLIKELY(tl_mark_stack == nullptr || tl_mark_stack->IsFull())) {
1837 MutexLock mu(self, mark_stack_lock_);
1838 // Get a new thread local mark stack.
1839 accounting::AtomicStack<mirror::Object>* new_tl_mark_stack;
1840 if (!pooled_mark_stacks_.empty()) {
1841 // Use a pooled mark stack.
1842 new_tl_mark_stack = pooled_mark_stacks_.back();
1843 pooled_mark_stacks_.pop_back();
1844 } else {
1845 // None pooled. Create a new one.
1846 new_tl_mark_stack =
1847 accounting::AtomicStack<mirror::Object>::Create(
1848 "thread local mark stack", 4 * KB, 4 * KB);
1849 }
1850 DCHECK(new_tl_mark_stack != nullptr);
1851 DCHECK(new_tl_mark_stack->IsEmpty());
1852 new_tl_mark_stack->PushBack(to_ref);
1853 self->SetThreadLocalMarkStack(new_tl_mark_stack);
1854 if (tl_mark_stack != nullptr) {
1855 // Store the old full stack into a vector.
1856 revoked_mark_stacks_.push_back(tl_mark_stack);
1857 }
1858 } else {
1859 tl_mark_stack->PushBack(to_ref);
1860 }
1861 }
1862 } else if (mark_stack_mode == kMarkStackModeShared) {
1863 // Access the shared GC mark stack with a lock.
1864 MutexLock mu(self, mark_stack_lock_);
1865 if (UNLIKELY(gc_mark_stack_->IsFull())) {
1866 ExpandGcMarkStack();
1867 }
1868 gc_mark_stack_->PushBack(to_ref);
1869 } else {
1870 CHECK_EQ(static_cast<uint32_t>(mark_stack_mode),
1871 static_cast<uint32_t>(kMarkStackModeGcExclusive))
1872 << "ref=" << to_ref
1873 << " self->gc_marking=" << self->GetIsGcMarking()
1874 << " cc->is_marking=" << is_marking_;
1875 CHECK(self == thread_running_gc_)
1876 << "Only GC-running thread should access the mark stack "
1877 << "in the GC exclusive mark stack mode. "
1878 << "ref=" << to_ref
1879 << " self->gc_marking=" << self->GetIsGcMarking()
1880 << " cc->is_marking=" << is_marking_;
1881 // Access the GC mark stack without a lock.
1882 if (UNLIKELY(gc_mark_stack_->IsFull())) {
1883 ExpandGcMarkStack();
1884 }
1885 gc_mark_stack_->PushBack(to_ref);
1886 }
1887 }
1888
GetAllocationStack()1889 accounting::ObjectStack* ConcurrentCopying::GetAllocationStack() {
1890 return heap_->allocation_stack_.get();
1891 }
1892
GetLiveStack()1893 accounting::ObjectStack* ConcurrentCopying::GetLiveStack() {
1894 return heap_->live_stack_.get();
1895 }
1896
1897 // The following visitors are used to verify that there's no references to the from-space left after
1898 // marking.
1899 class ConcurrentCopying::VerifyNoFromSpaceRefsVisitor : public SingleRootVisitor {
1900 public:
VerifyNoFromSpaceRefsVisitor(ConcurrentCopying * collector)1901 explicit VerifyNoFromSpaceRefsVisitor(ConcurrentCopying* collector)
1902 : collector_(collector) {}
1903
operator ()(mirror::Object * ref,MemberOffset offset=MemberOffset (0),mirror::Object * holder=nullptr) const1904 void operator()(mirror::Object* ref,
1905 MemberOffset offset = MemberOffset(0),
1906 mirror::Object* holder = nullptr) const
1907 REQUIRES_SHARED(Locks::mutator_lock_) ALWAYS_INLINE {
1908 if (ref == nullptr) {
1909 // OK.
1910 return;
1911 }
1912 collector_->AssertToSpaceInvariant(holder, offset, ref);
1913 if (kUseBakerReadBarrier) {
1914 CHECK_EQ(ref->GetReadBarrierState(), ReadBarrier::NonGrayState())
1915 << "Ref " << ref << " " << ref->PrettyTypeOf() << " has gray rb_state";
1916 }
1917 }
1918
VisitRoot(mirror::Object * root,const RootInfo & info)1919 void VisitRoot(mirror::Object* root, [[maybe_unused]] const RootInfo& info) override
1920 REQUIRES_SHARED(Locks::mutator_lock_) {
1921 DCHECK(root != nullptr);
1922 operator()(root);
1923 }
1924
1925 private:
1926 ConcurrentCopying* const collector_;
1927 };
1928
1929 class ConcurrentCopying::VerifyNoFromSpaceRefsFieldVisitor {
1930 public:
VerifyNoFromSpaceRefsFieldVisitor(ConcurrentCopying * collector)1931 explicit VerifyNoFromSpaceRefsFieldVisitor(ConcurrentCopying* collector)
1932 : collector_(collector) {}
1933
operator ()(ObjPtr<mirror::Object> obj,MemberOffset offset,bool is_static) const1934 void operator()(ObjPtr<mirror::Object> obj,
1935 MemberOffset offset,
1936 [[maybe_unused]] bool is_static) const
1937 REQUIRES_SHARED(Locks::mutator_lock_) ALWAYS_INLINE {
1938 mirror::Object* ref =
1939 obj->GetFieldObject<mirror::Object, kDefaultVerifyFlags, kWithoutReadBarrier>(offset);
1940 VerifyNoFromSpaceRefsVisitor visitor(collector_);
1941 visitor(ref, offset, obj.Ptr());
1942 }
operator ()(ObjPtr<mirror::Class> klass,ObjPtr<mirror::Reference> ref) const1943 void operator()(ObjPtr<mirror::Class> klass,
1944 ObjPtr<mirror::Reference> ref) const
1945 REQUIRES_SHARED(Locks::mutator_lock_) ALWAYS_INLINE {
1946 CHECK(klass->IsTypeOfReferenceClass());
1947 this->operator()(ref, mirror::Reference::ReferentOffset(), false);
1948 }
1949
VisitRootIfNonNull(mirror::CompressedReference<mirror::Object> * root) const1950 void VisitRootIfNonNull(mirror::CompressedReference<mirror::Object>* root) const
1951 REQUIRES_SHARED(Locks::mutator_lock_) {
1952 if (!root->IsNull()) {
1953 VisitRoot(root);
1954 }
1955 }
1956
VisitRoot(mirror::CompressedReference<mirror::Object> * root) const1957 void VisitRoot(mirror::CompressedReference<mirror::Object>* root) const
1958 REQUIRES_SHARED(Locks::mutator_lock_) {
1959 VerifyNoFromSpaceRefsVisitor visitor(collector_);
1960 visitor(root->AsMirrorPtr());
1961 }
1962
1963 private:
1964 ConcurrentCopying* const collector_;
1965 };
1966
1967 // Verify there's no from-space references left after the marking phase.
VerifyNoFromSpaceReferences()1968 void ConcurrentCopying::VerifyNoFromSpaceReferences() {
1969 Thread* self = Thread::Current();
1970 DCHECK(Locks::mutator_lock_->IsExclusiveHeld(self));
1971 // Verify all threads have is_gc_marking to be false
1972 {
1973 MutexLock mu(self, *Locks::thread_list_lock_);
1974 std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList();
1975 for (Thread* thread : thread_list) {
1976 CHECK(!thread->GetIsGcMarking());
1977 }
1978 }
1979
1980 auto verify_no_from_space_refs_visitor = [&](mirror::Object* obj)
1981 REQUIRES_SHARED(Locks::mutator_lock_) {
1982 CHECK(obj != nullptr);
1983 space::RegionSpace* region_space = RegionSpace();
1984 CHECK(!region_space->IsInFromSpace(obj)) << "Scanning object " << obj << " in from space";
1985 VerifyNoFromSpaceRefsFieldVisitor visitor(this);
1986 obj->VisitReferences</*kVisitNativeRoots=*/true, kDefaultVerifyFlags, kWithoutReadBarrier>(
1987 visitor,
1988 visitor);
1989 if (kUseBakerReadBarrier) {
1990 CHECK_EQ(obj->GetReadBarrierState(), ReadBarrier::NonGrayState())
1991 << "obj=" << obj << " has gray rb_state " << obj->GetReadBarrierState();
1992 }
1993 };
1994 // Roots.
1995 {
1996 ReaderMutexLock mu(self, *Locks::heap_bitmap_lock_);
1997 VerifyNoFromSpaceRefsVisitor ref_visitor(this);
1998 Runtime::Current()->VisitRoots(&ref_visitor);
1999 }
2000 // The to-space.
2001 region_space_->WalkToSpace(verify_no_from_space_refs_visitor);
2002 // Non-moving spaces.
2003 {
2004 WriterMutexLock mu(self, *Locks::heap_bitmap_lock_);
2005 heap_->GetMarkBitmap()->Visit(verify_no_from_space_refs_visitor);
2006 }
2007 // The alloc stack.
2008 {
2009 VerifyNoFromSpaceRefsVisitor ref_visitor(this);
2010 for (auto* it = heap_->allocation_stack_->Begin(), *end = heap_->allocation_stack_->End();
2011 it < end; ++it) {
2012 mirror::Object* const obj = it->AsMirrorPtr();
2013 if (obj != nullptr && obj->GetClass() != nullptr) {
2014 // TODO: need to call this only if obj is alive?
2015 ref_visitor(obj);
2016 verify_no_from_space_refs_visitor(obj);
2017 }
2018 }
2019 }
2020 // TODO: LOS. But only refs in LOS are classes.
2021 }
2022
2023 // The following visitors are used to assert the to-space invariant.
2024 class ConcurrentCopying::AssertToSpaceInvariantFieldVisitor {
2025 public:
AssertToSpaceInvariantFieldVisitor(ConcurrentCopying * collector)2026 explicit AssertToSpaceInvariantFieldVisitor(ConcurrentCopying* collector)
2027 : collector_(collector) {}
2028
operator ()(ObjPtr<mirror::Object> obj,MemberOffset offset,bool is_static) const2029 void operator()(ObjPtr<mirror::Object> obj,
2030 MemberOffset offset,
2031 [[maybe_unused]] bool is_static) const
2032 REQUIRES_SHARED(Locks::mutator_lock_) ALWAYS_INLINE {
2033 mirror::Object* ref =
2034 obj->GetFieldObject<mirror::Object, kDefaultVerifyFlags, kWithoutReadBarrier>(offset);
2035 collector_->AssertToSpaceInvariant(obj.Ptr(), offset, ref);
2036 }
operator ()(ObjPtr<mirror::Class> klass,ObjPtr<mirror::Reference> ref) const2037 void operator()(ObjPtr<mirror::Class> klass, [[maybe_unused]] ObjPtr<mirror::Reference> ref) const
2038 REQUIRES_SHARED(Locks::mutator_lock_) ALWAYS_INLINE {
2039 CHECK(klass->IsTypeOfReferenceClass());
2040 }
2041
VisitRootIfNonNull(mirror::CompressedReference<mirror::Object> * root) const2042 void VisitRootIfNonNull(mirror::CompressedReference<mirror::Object>* root) const
2043 REQUIRES_SHARED(Locks::mutator_lock_) {
2044 if (!root->IsNull()) {
2045 VisitRoot(root);
2046 }
2047 }
2048
VisitRoot(mirror::CompressedReference<mirror::Object> * root) const2049 void VisitRoot(mirror::CompressedReference<mirror::Object>* root) const
2050 REQUIRES_SHARED(Locks::mutator_lock_) {
2051 mirror::Object* ref = root->AsMirrorPtr();
2052 collector_->AssertToSpaceInvariant(/* obj */ nullptr, MemberOffset(0), ref);
2053 }
2054
2055 private:
2056 ConcurrentCopying* const collector_;
2057 };
2058
RevokeThreadLocalMarkStacks(bool disable_weak_ref_access,Closure * checkpoint_callback)2059 void ConcurrentCopying::RevokeThreadLocalMarkStacks(bool disable_weak_ref_access,
2060 Closure* checkpoint_callback) {
2061 Thread* self = Thread::Current();
2062 Locks::mutator_lock_->AssertSharedHeld(self);
2063 ThreadList* thread_list = Runtime::Current()->GetThreadList();
2064 RevokeThreadLocalMarkStackCheckpoint check_point(this, disable_weak_ref_access);
2065 if (disable_weak_ref_access) {
2066 // We're the only thread that could possibly ask for exclusive access here.
2067 Locks::mutator_lock_->SharedUnlock(self);
2068 {
2069 ScopedPause pause(this);
2070 MutexLock mu(self, *Locks::thread_list_lock_);
2071 checkpoint_callback->Run(self);
2072 for (Thread* thread : thread_list->GetList()) {
2073 check_point.Run(thread);
2074 }
2075 }
2076 Locks::mutator_lock_->SharedLock(self);
2077 } else {
2078 gc_barrier_->Init(self, 0);
2079 size_t barrier_count = thread_list->RunCheckpoint(&check_point, checkpoint_callback);
2080 // If there are no threads to wait which implys that all the checkpoint functions are finished,
2081 // then no need to release the mutator lock.
2082 if (barrier_count == 0) {
2083 return;
2084 }
2085 Locks::mutator_lock_->SharedUnlock(self);
2086 {
2087 ScopedThreadStateChange tsc(self, ThreadState::kWaitingForCheckPointsToRun);
2088 gc_barrier_->Increment(self, barrier_count);
2089 }
2090 Locks::mutator_lock_->SharedLock(self);
2091 }
2092 }
2093
RevokeThreadLocalMarkStack(Thread * thread)2094 void ConcurrentCopying::RevokeThreadLocalMarkStack(Thread* thread) {
2095 Thread* self = Thread::Current();
2096 CHECK_EQ(self, thread);
2097 MutexLock mu(self, mark_stack_lock_);
2098 accounting::AtomicStack<mirror::Object>* tl_mark_stack = thread->GetThreadLocalMarkStack();
2099 if (tl_mark_stack != nullptr) {
2100 CHECK(is_marking_);
2101 revoked_mark_stacks_.push_back(tl_mark_stack);
2102 thread->SetThreadLocalMarkStack(nullptr);
2103 }
2104 }
2105
ProcessMarkStack()2106 void ConcurrentCopying::ProcessMarkStack() {
2107 if (kVerboseMode) {
2108 LOG(INFO) << "ProcessMarkStack. ";
2109 }
2110 bool empty_prev = false;
2111 while (true) {
2112 bool empty = ProcessMarkStackOnce();
2113 if (empty_prev && empty) {
2114 // Saw empty mark stack for a second time, done.
2115 break;
2116 }
2117 empty_prev = empty;
2118 }
2119 }
2120
ProcessMarkStackOnce()2121 bool ConcurrentCopying::ProcessMarkStackOnce() {
2122 DCHECK(thread_running_gc_ != nullptr);
2123 Thread* const self = Thread::Current();
2124 DCHECK(self == thread_running_gc_);
2125 DCHECK(thread_running_gc_->GetThreadLocalMarkStack() == nullptr);
2126 size_t count = 0;
2127 MarkStackMode mark_stack_mode = mark_stack_mode_.load(std::memory_order_acquire);
2128 if (mark_stack_mode == kMarkStackModeThreadLocal) {
2129 // Process the thread-local mark stacks and the GC mark stack.
2130 count += ProcessThreadLocalMarkStacks(/* disable_weak_ref_access= */ false,
2131 /* checkpoint_callback= */ nullptr,
2132 [this] (mirror::Object* ref)
2133 REQUIRES_SHARED(Locks::mutator_lock_) {
2134 ProcessMarkStackRef(ref);
2135 });
2136 while (!gc_mark_stack_->IsEmpty()) {
2137 mirror::Object* to_ref = gc_mark_stack_->PopBack();
2138 ProcessMarkStackRef(to_ref);
2139 ++count;
2140 }
2141 gc_mark_stack_->Reset();
2142 } else if (mark_stack_mode == kMarkStackModeShared) {
2143 // Do an empty checkpoint to avoid a race with a mutator preempted in the middle of a read
2144 // barrier but before pushing onto the mark stack. b/32508093. Note the weak ref access is
2145 // disabled at this point.
2146 IssueEmptyCheckpoint();
2147 // Process the shared GC mark stack with a lock.
2148 {
2149 MutexLock mu(thread_running_gc_, mark_stack_lock_);
2150 CHECK(revoked_mark_stacks_.empty());
2151 CHECK_EQ(pooled_mark_stacks_.size(), kMarkStackPoolSize);
2152 }
2153 while (true) {
2154 std::vector<mirror::Object*> refs;
2155 {
2156 // Copy refs with lock. Note the number of refs should be small.
2157 MutexLock mu(thread_running_gc_, mark_stack_lock_);
2158 if (gc_mark_stack_->IsEmpty()) {
2159 break;
2160 }
2161 for (StackReference<mirror::Object>* p = gc_mark_stack_->Begin();
2162 p != gc_mark_stack_->End(); ++p) {
2163 refs.push_back(p->AsMirrorPtr());
2164 }
2165 gc_mark_stack_->Reset();
2166 }
2167 for (mirror::Object* ref : refs) {
2168 ProcessMarkStackRef(ref);
2169 ++count;
2170 }
2171 }
2172 } else {
2173 CHECK_EQ(static_cast<uint32_t>(mark_stack_mode),
2174 static_cast<uint32_t>(kMarkStackModeGcExclusive));
2175 {
2176 MutexLock mu(thread_running_gc_, mark_stack_lock_);
2177 CHECK(revoked_mark_stacks_.empty());
2178 CHECK_EQ(pooled_mark_stacks_.size(), kMarkStackPoolSize);
2179 }
2180 // Process the GC mark stack in the exclusive mode. No need to take the lock.
2181 while (!gc_mark_stack_->IsEmpty()) {
2182 mirror::Object* to_ref = gc_mark_stack_->PopBack();
2183 ProcessMarkStackRef(to_ref);
2184 ++count;
2185 }
2186 gc_mark_stack_->Reset();
2187 }
2188
2189 // Return true if the stack was empty.
2190 return count == 0;
2191 }
2192
2193 template <typename Processor>
ProcessThreadLocalMarkStacks(bool disable_weak_ref_access,Closure * checkpoint_callback,const Processor & processor)2194 size_t ConcurrentCopying::ProcessThreadLocalMarkStacks(bool disable_weak_ref_access,
2195 Closure* checkpoint_callback,
2196 const Processor& processor) {
2197 // Run a checkpoint to collect all thread local mark stacks and iterate over them all.
2198 RevokeThreadLocalMarkStacks(disable_weak_ref_access, checkpoint_callback);
2199 if (disable_weak_ref_access) {
2200 CHECK_EQ(static_cast<uint32_t>(mark_stack_mode_.load(std::memory_order_relaxed)),
2201 static_cast<uint32_t>(kMarkStackModeShared));
2202 }
2203 size_t count = 0;
2204 std::vector<accounting::AtomicStack<mirror::Object>*> mark_stacks;
2205 {
2206 MutexLock mu(thread_running_gc_, mark_stack_lock_);
2207 // Make a copy of the mark stack vector.
2208 mark_stacks = revoked_mark_stacks_;
2209 revoked_mark_stacks_.clear();
2210 }
2211 for (accounting::AtomicStack<mirror::Object>* mark_stack : mark_stacks) {
2212 for (StackReference<mirror::Object>* p = mark_stack->Begin(); p != mark_stack->End(); ++p) {
2213 mirror::Object* to_ref = p->AsMirrorPtr();
2214 processor(to_ref);
2215 ++count;
2216 }
2217 {
2218 MutexLock mu(thread_running_gc_, mark_stack_lock_);
2219 if (pooled_mark_stacks_.size() >= kMarkStackPoolSize) {
2220 // The pool has enough. Delete it.
2221 delete mark_stack;
2222 } else {
2223 // Otherwise, put it into the pool for later reuse.
2224 mark_stack->Reset();
2225 pooled_mark_stacks_.push_back(mark_stack);
2226 }
2227 }
2228 }
2229 if (disable_weak_ref_access) {
2230 MutexLock mu(thread_running_gc_, mark_stack_lock_);
2231 CHECK(revoked_mark_stacks_.empty());
2232 CHECK_EQ(pooled_mark_stacks_.size(), kMarkStackPoolSize);
2233 }
2234 return count;
2235 }
2236
ProcessMarkStackRef(mirror::Object * to_ref)2237 inline void ConcurrentCopying::ProcessMarkStackRef(mirror::Object* to_ref) {
2238 DCHECK(!region_space_->IsInFromSpace(to_ref));
2239 size_t obj_size = 0;
2240 space::RegionSpace::RegionType rtype = region_space_->GetRegionType(to_ref);
2241 if (kUseBakerReadBarrier) {
2242 DCHECK(to_ref->GetReadBarrierState() == ReadBarrier::GrayState())
2243 << " to_ref=" << to_ref
2244 << " rb_state=" << to_ref->GetReadBarrierState()
2245 << " is_marked=" << IsMarked(to_ref)
2246 << " type=" << to_ref->PrettyTypeOf()
2247 << " young_gen=" << std::boolalpha << young_gen_ << std::noboolalpha
2248 << " space=" << heap_->DumpSpaceNameFromAddress(to_ref)
2249 << " region_type=" << rtype;
2250 }
2251 bool add_to_live_bytes = false;
2252 // Invariant: There should be no object from a newly-allocated
2253 // region (either large or non-large) on the mark stack.
2254 DCHECK(!region_space_->IsInNewlyAllocatedRegion(to_ref)) << to_ref;
2255 bool perform_scan = false;
2256 switch (rtype) {
2257 case space::RegionSpace::RegionType::kRegionTypeUnevacFromSpace:
2258 // Mark the bitmap only in the GC thread here so that we don't need a CAS.
2259 if (!kUseBakerReadBarrier || !region_space_bitmap_->Set(to_ref)) {
2260 // It may be already marked if we accidentally pushed the same object twice due to the racy
2261 // bitmap read in MarkUnevacFromSpaceRegion.
2262 if (use_generational_cc_ && young_gen_) {
2263 CHECK(region_space_->IsLargeObject(to_ref));
2264 region_space_->ZeroLiveBytesForLargeObject(to_ref);
2265 }
2266 perform_scan = true;
2267 // Only add to the live bytes if the object was not already marked and we are not the young
2268 // GC.
2269 // Why add live bytes even after 2-phase GC?
2270 // We need to ensure that if there is a unevac region with any live
2271 // objects, then its live_bytes must be non-zero. Otherwise,
2272 // ClearFromSpace() will clear the region. Considering, that we may skip
2273 // live objects during marking phase of 2-phase GC, we have to take care
2274 // of such objects here.
2275 add_to_live_bytes = true;
2276 }
2277 break;
2278 case space::RegionSpace::RegionType::kRegionTypeToSpace:
2279 if (use_generational_cc_) {
2280 // Copied to to-space, set the bit so that the next GC can scan objects.
2281 region_space_bitmap_->Set(to_ref);
2282 }
2283 perform_scan = true;
2284 break;
2285 default:
2286 DCHECK(!region_space_->HasAddress(to_ref)) << to_ref;
2287 DCHECK(!immune_spaces_.ContainsObject(to_ref));
2288 // Non-moving or large-object space.
2289 if (kUseBakerReadBarrier) {
2290 accounting::ContinuousSpaceBitmap* mark_bitmap =
2291 heap_->GetNonMovingSpace()->GetMarkBitmap();
2292 const bool is_los = !mark_bitmap->HasAddress(to_ref);
2293 if (is_los) {
2294 if (!IsAlignedParam(to_ref, space::LargeObjectSpace::ObjectAlignment())) {
2295 // Ref is a large object that is not aligned, it must be heap
2296 // corruption. Remove memory protection and dump data before
2297 // AtomicSetReadBarrierState since it will fault if the address is not
2298 // valid.
2299 region_space_->Unprotect();
2300 heap_->GetVerification()->LogHeapCorruption(/* obj */ nullptr,
2301 MemberOffset(0),
2302 to_ref,
2303 /* fatal */ true);
2304 }
2305 DCHECK(heap_->GetLargeObjectsSpace())
2306 << "ref=" << to_ref
2307 << " doesn't belong to non-moving space and large object space doesn't exist";
2308 accounting::LargeObjectBitmap* los_bitmap =
2309 heap_->GetLargeObjectsSpace()->GetMarkBitmap();
2310 DCHECK(los_bitmap->HasAddress(to_ref));
2311 // Only the GC thread could be setting the LOS bit map hence doesn't
2312 // need to be atomically done.
2313 perform_scan = !los_bitmap->Set(to_ref);
2314 } else {
2315 // Only the GC thread could be setting the non-moving space bit map
2316 // hence doesn't need to be atomically done.
2317 perform_scan = !mark_bitmap->Set(to_ref);
2318 }
2319 } else {
2320 perform_scan = true;
2321 }
2322 }
2323 if (perform_scan) {
2324 obj_size = to_ref->SizeOf<kDefaultVerifyFlags>();
2325 if (use_generational_cc_ && young_gen_) {
2326 Scan<true>(to_ref, obj_size);
2327 } else {
2328 Scan<false>(to_ref, obj_size);
2329 }
2330 }
2331 if (kUseBakerReadBarrier) {
2332 DCHECK(to_ref->GetReadBarrierState() == ReadBarrier::GrayState())
2333 << " to_ref=" << to_ref
2334 << " rb_state=" << to_ref->GetReadBarrierState()
2335 << " is_marked=" << IsMarked(to_ref)
2336 << " type=" << to_ref->PrettyTypeOf()
2337 << " young_gen=" << std::boolalpha << young_gen_ << std::noboolalpha
2338 << " space=" << heap_->DumpSpaceNameFromAddress(to_ref)
2339 << " region_type=" << rtype
2340 // TODO: Temporary; remove this when this is no longer needed (b/116087961).
2341 << " runtime->sentinel=" << Runtime::Current()->GetSentinel().Read<kWithoutReadBarrier>();
2342 }
2343 #ifdef USE_BAKER_READ_BARRIER
2344 mirror::Object* referent = nullptr;
2345 if (UNLIKELY((to_ref->GetClass<kVerifyNone, kWithoutReadBarrier>()->IsTypeOfReferenceClass() &&
2346 (referent = to_ref->AsReference()->GetReferent<kWithoutReadBarrier>()) != nullptr &&
2347 !IsInToSpace(referent)))) {
2348 // Leave this reference gray in the queue so that GetReferent() will trigger a read barrier. We
2349 // will change it to non-gray later in ReferenceQueue::DisableReadBarrierForReference.
2350 DCHECK(to_ref->AsReference()->GetPendingNext() != nullptr)
2351 << "Left unenqueued ref gray " << to_ref;
2352 } else {
2353 // We may occasionally leave a reference non-gray in the queue if its referent happens to be
2354 // concurrently marked after the Scan() call above has enqueued the Reference, in which case the
2355 // above IsInToSpace() evaluates to true and we change the color from gray to non-gray here in
2356 // this else block.
2357 if (kUseBakerReadBarrier) {
2358 bool success = to_ref->AtomicSetReadBarrierState(
2359 ReadBarrier::GrayState(), ReadBarrier::NonGrayState(), std::memory_order_release);
2360 DCHECK(success) << "Must succeed as we won the race.";
2361 }
2362 }
2363 #else
2364 DCHECK(!kUseBakerReadBarrier);
2365 #endif
2366
2367 if (add_to_live_bytes) {
2368 // Add to the live bytes per unevacuated from-space. Note this code is always run by the
2369 // GC-running thread (no synchronization required).
2370 DCHECK(region_space_bitmap_->Test(to_ref));
2371 if (obj_size == 0) {
2372 obj_size = to_ref->SizeOf<kDefaultVerifyFlags>();
2373 }
2374 region_space_->AddLiveBytes(to_ref, RoundUp(obj_size, space::RegionSpace::kAlignment));
2375 }
2376 if (ReadBarrier::kEnableToSpaceInvariantChecks) {
2377 CHECK(to_ref != nullptr);
2378 space::RegionSpace* region_space = RegionSpace();
2379 CHECK(!region_space->IsInFromSpace(to_ref)) << "Scanning object " << to_ref << " in from space";
2380 AssertToSpaceInvariant(nullptr, MemberOffset(0), to_ref);
2381 AssertToSpaceInvariantFieldVisitor visitor(this);
2382 to_ref->VisitReferences</*kVisitNativeRoots=*/true, kDefaultVerifyFlags, kWithoutReadBarrier>(
2383 visitor,
2384 visitor);
2385 }
2386 }
2387
2388 class ConcurrentCopying::DisableWeakRefAccessCallback : public Closure {
2389 public:
DisableWeakRefAccessCallback(ConcurrentCopying * concurrent_copying)2390 explicit DisableWeakRefAccessCallback(ConcurrentCopying* concurrent_copying)
2391 : concurrent_copying_(concurrent_copying) {
2392 }
2393
Run(Thread * self)2394 void Run([[maybe_unused]] Thread* self) override REQUIRES(Locks::thread_list_lock_) {
2395 // This needs to run under the thread_list_lock_ critical section in ThreadList::RunCheckpoint()
2396 // to avoid a deadlock b/31500969.
2397 CHECK(concurrent_copying_->weak_ref_access_enabled_);
2398 concurrent_copying_->weak_ref_access_enabled_ = false;
2399 }
2400
2401 private:
2402 ConcurrentCopying* const concurrent_copying_;
2403 };
2404
SwitchToSharedMarkStackMode()2405 void ConcurrentCopying::SwitchToSharedMarkStackMode() {
2406 Thread* self = Thread::Current();
2407 DCHECK(thread_running_gc_ != nullptr);
2408 DCHECK(self == thread_running_gc_);
2409 DCHECK(thread_running_gc_->GetThreadLocalMarkStack() == nullptr);
2410 CHECK_EQ(static_cast<uint32_t>(mark_stack_mode_.load(std::memory_order_relaxed)),
2411 static_cast<uint32_t>(kMarkStackModeThreadLocal));
2412 mark_stack_mode_.store(kMarkStackModeShared, std::memory_order_release);
2413 DisableWeakRefAccessCallback dwrac(this);
2414 // Process the thread local mark stacks one last time after switching to the shared mark stack
2415 // mode and disable weak ref accesses.
2416 ProcessThreadLocalMarkStacks(/* disable_weak_ref_access= */ true,
2417 &dwrac,
2418 [this] (mirror::Object* ref)
2419 REQUIRES_SHARED(Locks::mutator_lock_) {
2420 ProcessMarkStackRef(ref);
2421 });
2422 if (kVerboseMode) {
2423 LOG(INFO) << "Switched to shared mark stack mode and disabled weak ref access";
2424 }
2425 }
2426
SwitchToGcExclusiveMarkStackMode()2427 void ConcurrentCopying::SwitchToGcExclusiveMarkStackMode() {
2428 Thread* self = Thread::Current();
2429 DCHECK(thread_running_gc_ != nullptr);
2430 DCHECK(self == thread_running_gc_);
2431 DCHECK(thread_running_gc_->GetThreadLocalMarkStack() == nullptr);
2432 CHECK_EQ(static_cast<uint32_t>(mark_stack_mode_.load(std::memory_order_relaxed)),
2433 static_cast<uint32_t>(kMarkStackModeShared));
2434 mark_stack_mode_.store(kMarkStackModeGcExclusive, std::memory_order_release);
2435 if (kVerboseMode) {
2436 LOG(INFO) << "Switched to GC exclusive mark stack mode";
2437 }
2438 }
2439
CheckEmptyMarkStack()2440 void ConcurrentCopying::CheckEmptyMarkStack() {
2441 Thread* self = Thread::Current();
2442 DCHECK(thread_running_gc_ != nullptr);
2443 DCHECK(self == thread_running_gc_);
2444 DCHECK(thread_running_gc_->GetThreadLocalMarkStack() == nullptr);
2445 MarkStackMode mark_stack_mode = mark_stack_mode_.load(std::memory_order_acquire);
2446 if (mark_stack_mode == kMarkStackModeThreadLocal) {
2447 // Thread-local mark stack mode.
2448 RevokeThreadLocalMarkStacks(false, nullptr);
2449 MutexLock mu(thread_running_gc_, mark_stack_lock_);
2450 if (!revoked_mark_stacks_.empty()) {
2451 for (accounting::AtomicStack<mirror::Object>* mark_stack : revoked_mark_stacks_) {
2452 while (!mark_stack->IsEmpty()) {
2453 mirror::Object* obj = mark_stack->PopBack();
2454 if (kUseBakerReadBarrier) {
2455 uint32_t rb_state = obj->GetReadBarrierState();
2456 LOG(INFO) << "On mark queue : " << obj << " " << obj->PrettyTypeOf() << " rb_state="
2457 << rb_state << " is_marked=" << IsMarked(obj);
2458 } else {
2459 LOG(INFO) << "On mark queue : " << obj << " " << obj->PrettyTypeOf()
2460 << " is_marked=" << IsMarked(obj);
2461 }
2462 }
2463 }
2464 LOG(FATAL) << "mark stack is not empty";
2465 }
2466 } else {
2467 // Shared, GC-exclusive, or off.
2468 MutexLock mu(thread_running_gc_, mark_stack_lock_);
2469 CHECK(gc_mark_stack_->IsEmpty());
2470 CHECK(revoked_mark_stacks_.empty());
2471 CHECK_EQ(pooled_mark_stacks_.size(), kMarkStackPoolSize);
2472 }
2473 }
2474
SweepSystemWeaks(Thread * self)2475 void ConcurrentCopying::SweepSystemWeaks(Thread* self) {
2476 TimingLogger::ScopedTiming split("SweepSystemWeaks", GetTimings());
2477 ReaderMutexLock mu(self, *Locks::heap_bitmap_lock_);
2478 Runtime::Current()->SweepSystemWeaks(this);
2479 }
2480
Sweep(bool swap_bitmaps)2481 void ConcurrentCopying::Sweep(bool swap_bitmaps) {
2482 if (use_generational_cc_ && young_gen_) {
2483 // Only sweep objects on the live stack.
2484 SweepArray(heap_->GetLiveStack(), /* swap_bitmaps= */ false);
2485 } else {
2486 {
2487 TimingLogger::ScopedTiming t("MarkStackAsLive", GetTimings());
2488 accounting::ObjectStack* live_stack = heap_->GetLiveStack();
2489 if (kEnableFromSpaceAccountingCheck) {
2490 // Ensure that nobody inserted items in the live stack after we swapped the stacks.
2491 CHECK_GE(live_stack_freeze_size_, live_stack->Size());
2492 }
2493 heap_->MarkAllocStackAsLive(live_stack);
2494 live_stack->Reset();
2495 }
2496 CheckEmptyMarkStack();
2497 TimingLogger::ScopedTiming split("Sweep", GetTimings());
2498 for (const auto& space : GetHeap()->GetContinuousSpaces()) {
2499 if (space->IsContinuousMemMapAllocSpace() && space != region_space_
2500 && !immune_spaces_.ContainsSpace(space)) {
2501 space::ContinuousMemMapAllocSpace* alloc_space = space->AsContinuousMemMapAllocSpace();
2502 TimingLogger::ScopedTiming split2(
2503 alloc_space->IsZygoteSpace() ? "SweepZygoteSpace" : "SweepAllocSpace", GetTimings());
2504 RecordFree(alloc_space->Sweep(swap_bitmaps));
2505 }
2506 }
2507 SweepLargeObjects(swap_bitmaps);
2508 }
2509 }
2510
SweepArray(accounting::ObjectStack * obj_arr,bool swap_bitmaps)2511 void ConcurrentCopying::SweepArray(accounting::ObjectStack* obj_arr, bool swap_bitmaps) {
2512 // This method is only used when Generational CC collection is enabled.
2513 DCHECK(use_generational_cc_);
2514 CheckEmptyMarkStack();
2515 TimingLogger::ScopedTiming t("SweepArray", GetTimings());
2516 std::vector<space::ContinuousSpace*> sweep_spaces;
2517 for (space::ContinuousSpace* space : heap_->GetContinuousSpaces()) {
2518 if (!space->IsAllocSpace() ||
2519 space == region_space_ ||
2520 immune_spaces_.ContainsSpace(space) ||
2521 space->GetLiveBitmap() == nullptr) {
2522 continue;
2523 }
2524 sweep_spaces.push_back(space);
2525 }
2526 GarbageCollector::SweepArray(obj_arr, swap_bitmaps, &sweep_spaces);
2527 }
2528
MarkZygoteLargeObjects()2529 void ConcurrentCopying::MarkZygoteLargeObjects() {
2530 TimingLogger::ScopedTiming split(__FUNCTION__, GetTimings());
2531 Thread* const self = Thread::Current();
2532 WriterMutexLock rmu(self, *Locks::heap_bitmap_lock_);
2533 space::LargeObjectSpace* const los = heap_->GetLargeObjectsSpace();
2534 if (los != nullptr) {
2535 // Pick the current live bitmap (mark bitmap if swapped).
2536 accounting::LargeObjectBitmap* const live_bitmap = los->GetLiveBitmap();
2537 accounting::LargeObjectBitmap* const mark_bitmap = los->GetMarkBitmap();
2538 // Walk through all of the objects and explicitly mark the zygote ones so they don't get swept.
2539 std::pair<uint8_t*, uint8_t*> range = los->GetBeginEndAtomic();
2540 live_bitmap->VisitMarkedRange(reinterpret_cast<uintptr_t>(range.first),
2541 reinterpret_cast<uintptr_t>(range.second),
2542 [mark_bitmap, los, self](mirror::Object* obj)
2543 REQUIRES(Locks::heap_bitmap_lock_)
2544 REQUIRES_SHARED(Locks::mutator_lock_) {
2545 if (los->IsZygoteLargeObject(self, obj)) {
2546 mark_bitmap->Set(obj);
2547 }
2548 });
2549 }
2550 }
2551
SweepLargeObjects(bool swap_bitmaps)2552 void ConcurrentCopying::SweepLargeObjects(bool swap_bitmaps) {
2553 TimingLogger::ScopedTiming split("SweepLargeObjects", GetTimings());
2554 if (heap_->GetLargeObjectsSpace() != nullptr) {
2555 RecordFreeLOS(heap_->GetLargeObjectsSpace()->Sweep(swap_bitmaps));
2556 }
2557 }
2558
CaptureRssAtPeak()2559 void ConcurrentCopying::CaptureRssAtPeak() {
2560 using range_t = std::pair<void*, void*>;
2561 // This operation is expensive as several calls to mincore() are performed.
2562 // Also, this must be called before clearing regions in ReclaimPhase().
2563 // Therefore, we make it conditional on the flag that enables dumping GC
2564 // performance info on shutdown.
2565 if (Runtime::Current()->GetDumpGCPerformanceOnShutdown()) {
2566 std::list<range_t> gc_ranges;
2567 auto add_gc_range = [&gc_ranges](void* start, size_t size) {
2568 void* end = static_cast<char*>(start) + RoundUp(size, gPageSize);
2569 gc_ranges.emplace_back(range_t(start, end));
2570 };
2571
2572 // region space
2573 DCHECK(IsAlignedParam(region_space_->Limit(), gPageSize));
2574 gc_ranges.emplace_back(range_t(region_space_->Begin(), region_space_->Limit()));
2575 // mark bitmap
2576 add_gc_range(region_space_bitmap_->Begin(), region_space_bitmap_->Size());
2577
2578 // non-moving space
2579 {
2580 DCHECK(IsAlignedParam(heap_->non_moving_space_->Limit(), gPageSize));
2581 gc_ranges.emplace_back(range_t(heap_->non_moving_space_->Begin(),
2582 heap_->non_moving_space_->Limit()));
2583 // mark bitmap
2584 accounting::ContinuousSpaceBitmap *bitmap = heap_->non_moving_space_->GetMarkBitmap();
2585 add_gc_range(bitmap->Begin(), bitmap->Size());
2586 // live bitmap. Deal with bound bitmaps.
2587 ReaderMutexLock mu(Thread::Current(), *Locks::heap_bitmap_lock_);
2588 if (heap_->non_moving_space_->HasBoundBitmaps()) {
2589 DCHECK_EQ(bitmap->Begin(),
2590 heap_->non_moving_space_->GetLiveBitmap()->Begin());
2591 bitmap = heap_->non_moving_space_->GetTempBitmap();
2592 } else {
2593 bitmap = heap_->non_moving_space_->GetLiveBitmap();
2594 }
2595 add_gc_range(bitmap->Begin(), bitmap->Size());
2596 }
2597 // large-object space
2598 if (heap_->GetLargeObjectsSpace()) {
2599 heap_->GetLargeObjectsSpace()->ForEachMemMap([&add_gc_range](const MemMap& map) {
2600 DCHECK(IsAlignedParam(map.BaseSize(), gPageSize));
2601 add_gc_range(map.BaseBegin(), map.BaseSize());
2602 });
2603 // mark bitmap
2604 accounting::LargeObjectBitmap* bitmap = heap_->GetLargeObjectsSpace()->GetMarkBitmap();
2605 add_gc_range(bitmap->Begin(), bitmap->Size());
2606 // live bitmap
2607 bitmap = heap_->GetLargeObjectsSpace()->GetLiveBitmap();
2608 add_gc_range(bitmap->Begin(), bitmap->Size());
2609 }
2610 // card table
2611 add_gc_range(heap_->GetCardTable()->MemMapBegin(), heap_->GetCardTable()->MemMapSize());
2612 // inter-region refs
2613 if (use_generational_cc_ && !young_gen_) {
2614 // region space
2615 add_gc_range(region_space_inter_region_bitmap_.Begin(),
2616 region_space_inter_region_bitmap_.Size());
2617 // non-moving space
2618 add_gc_range(non_moving_space_inter_region_bitmap_.Begin(),
2619 non_moving_space_inter_region_bitmap_.Size());
2620 }
2621 // Extract RSS using mincore(). Updates the cummulative RSS counter.
2622 ExtractRssFromMincore(&gc_ranges);
2623 }
2624 }
2625
ReclaimPhase()2626 void ConcurrentCopying::ReclaimPhase() {
2627 TimingLogger::ScopedTiming split("ReclaimPhase", GetTimings());
2628 if (kVerboseMode) {
2629 LOG(INFO) << "GC ReclaimPhase";
2630 }
2631 Thread* self = Thread::Current();
2632
2633 // Free data for class loaders that we unloaded. This includes removing
2634 // dead methods from JIT's internal maps. This must be done before
2635 // reclaiming the memory of the dead methods' declaring classes.
2636 Runtime::Current()->GetClassLinker()->CleanupClassLoaders();
2637
2638 {
2639 // Double-check that the mark stack is empty.
2640 // Note: need to set this after VerifyNoFromSpaceRef().
2641 is_asserting_to_space_invariant_ = false;
2642 QuasiAtomic::ThreadFenceForConstructor(); // TODO: Remove?
2643 if (kVerboseMode) {
2644 LOG(INFO) << "Issue an empty check point. ";
2645 }
2646 IssueEmptyCheckpoint();
2647 // Disable the check.
2648 if (kIsDebugBuild) {
2649 is_mark_stack_push_disallowed_.store(0, std::memory_order_relaxed);
2650 }
2651 if (kUseBakerReadBarrier) {
2652 updated_all_immune_objects_.store(false, std::memory_order_seq_cst);
2653 }
2654 CheckEmptyMarkStack();
2655 }
2656
2657 // Capture RSS at the time when memory usage is at its peak. All GC related
2658 // memory ranges like java heap, card table, bitmap etc. are taken into
2659 // account.
2660 // TODO: We can fetch resident memory for region space directly by going
2661 // through list of allocated regions. This way we can avoid calling mincore on
2662 // the biggest memory range, thereby reducing the cost of this function.
2663 CaptureRssAtPeak();
2664
2665 // Sweep the malloc spaces before clearing the from space since the memory tool mode might
2666 // access the object classes in the from space for dead objects.
2667 {
2668 WriterMutexLock mu(self, *Locks::heap_bitmap_lock_);
2669 Sweep(/* swap_bitmaps= */ false);
2670 SwapBitmaps();
2671 heap_->UnBindBitmaps();
2672
2673 // The bitmap was cleared at the start of the GC, there is nothing we need to do here.
2674 DCHECK(region_space_bitmap_ != nullptr);
2675 region_space_bitmap_ = nullptr;
2676 }
2677
2678
2679 {
2680 // Record freed objects.
2681 TimingLogger::ScopedTiming split2("RecordFree", GetTimings());
2682 // Don't include thread-locals that are in the to-space.
2683 const uint64_t from_bytes = region_space_->GetBytesAllocatedInFromSpace();
2684 const uint64_t unevac_from_bytes = region_space_->GetBytesAllocatedInUnevacFromSpace();
2685 uint64_t to_bytes = bytes_moved_.load(std::memory_order_relaxed) + bytes_moved_gc_thread_;
2686 cumulative_bytes_moved_ += to_bytes;
2687 uint64_t to_objects = objects_moved_.load(std::memory_order_relaxed) + objects_moved_gc_thread_;
2688 if (kEnableFromSpaceAccountingCheck) {
2689 CHECK_EQ(from_space_num_bytes_at_first_pause_, from_bytes + unevac_from_bytes);
2690 }
2691 // to_bytes <= from_bytes is only approximately true, because objects expand a little when
2692 // copying to non-moving space in near-OOM situations.
2693 if (from_bytes > 0) {
2694 copied_live_bytes_ratio_sum_ += static_cast<float>(to_bytes) / from_bytes;
2695 gc_count_++;
2696 }
2697
2698 // Cleared bytes and objects, populated by the call to RegionSpace::ClearFromSpace below.
2699 uint64_t cleared_bytes;
2700 uint64_t cleared_objects;
2701 bool should_eagerly_release_memory = ShouldEagerlyReleaseMemoryToOS();
2702 {
2703 TimingLogger::ScopedTiming split4("ClearFromSpace", GetTimings());
2704 region_space_->ClearFromSpace(&cleared_bytes,
2705 &cleared_objects,
2706 /*clear_bitmap*/ !young_gen_,
2707 should_eagerly_release_memory);
2708 // `cleared_bytes` may be greater than the from space equivalents since
2709 // RegionSpace::ClearFromSpace may clear empty unevac regions.
2710 CHECK_GE(cleared_bytes, from_bytes);
2711 }
2712
2713 // If we need to release available memory to the OS, go over all free
2714 // regions which the kernel might still cache.
2715 if (should_eagerly_release_memory) {
2716 TimingLogger::ScopedTiming split4("Release free regions", GetTimings());
2717 region_space_->ReleaseFreeRegions();
2718 }
2719
2720 // freed_bytes could conceivably be negative if we fall back to nonmoving space and have to
2721 // pad to a larger size.
2722 int64_t freed_bytes = (int64_t)cleared_bytes - (int64_t)to_bytes;
2723 uint64_t freed_objects = cleared_objects - to_objects;
2724 if (kVerboseMode) {
2725 LOG(INFO) << "RecordFree:"
2726 << " from_bytes=" << from_bytes
2727 << " unevac_from_bytes=" << unevac_from_bytes
2728 << " to_bytes=" << to_bytes
2729 << " freed_bytes=" << freed_bytes
2730 << " from_space size=" << region_space_->FromSpaceSize()
2731 << " unevac_from_space size=" << region_space_->UnevacFromSpaceSize()
2732 << " to_space size=" << region_space_->ToSpaceSize();
2733 LOG(INFO) << "(before) num_bytes_allocated="
2734 << heap_->num_bytes_allocated_.load();
2735 }
2736 RecordFree(ObjectBytePair(freed_objects, freed_bytes));
2737 GetCurrentIteration()->SetScannedBytes(bytes_scanned_);
2738 if (kVerboseMode) {
2739 LOG(INFO) << "(after) num_bytes_allocated="
2740 << heap_->num_bytes_allocated_.load();
2741 }
2742
2743 float reclaimed_bytes_ratio = static_cast<float>(freed_bytes) / num_bytes_allocated_before_gc_;
2744 reclaimed_bytes_ratio_sum_ += reclaimed_bytes_ratio;
2745 }
2746
2747 CheckEmptyMarkStack();
2748
2749 if (heap_->dump_region_info_after_gc_) {
2750 LOG(INFO) << "time=" << region_space_->Time();
2751 region_space_->DumpNonFreeRegions(LOG_STREAM(INFO));
2752 }
2753
2754 if (kVerboseMode) {
2755 LOG(INFO) << "GC end of ReclaimPhase";
2756 }
2757 }
2758
DumpReferenceInfo(mirror::Object * ref,const char * ref_name,const char * indent)2759 std::string ConcurrentCopying::DumpReferenceInfo(mirror::Object* ref,
2760 const char* ref_name,
2761 const char* indent) {
2762 std::ostringstream oss;
2763 oss << indent << heap_->GetVerification()->DumpObjectInfo(ref, ref_name) << '\n';
2764 if (ref != nullptr) {
2765 if (kUseBakerReadBarrier) {
2766 oss << indent << ref_name << "->GetMarkBit()=" << ref->GetMarkBit() << '\n';
2767 oss << indent << ref_name << "->GetReadBarrierState()=" << ref->GetReadBarrierState() << '\n';
2768 }
2769 }
2770 if (region_space_->HasAddress(ref)) {
2771 oss << indent << "Region containing " << ref_name << ":" << '\n';
2772 region_space_->DumpRegionForObject(oss, ref);
2773 if (region_space_bitmap_ != nullptr) {
2774 oss << indent << "region_space_bitmap_->Test(" << ref_name << ")="
2775 << std::boolalpha << region_space_bitmap_->Test(ref) << std::noboolalpha;
2776 }
2777 }
2778 return oss.str();
2779 }
2780
DumpHeapReference(mirror::Object * obj,MemberOffset offset,mirror::Object * ref)2781 std::string ConcurrentCopying::DumpHeapReference(mirror::Object* obj,
2782 MemberOffset offset,
2783 mirror::Object* ref) {
2784 std::ostringstream oss;
2785 constexpr const char* kIndent = " ";
2786 oss << kIndent << "Invalid reference: ref=" << ref
2787 << " referenced from: object=" << obj << " offset= " << offset << '\n';
2788 // Information about `obj`.
2789 oss << DumpReferenceInfo(obj, "obj", kIndent) << '\n';
2790 // Information about `ref`.
2791 oss << DumpReferenceInfo(ref, "ref", kIndent);
2792 return oss.str();
2793 }
2794
AssertToSpaceInvariant(mirror::Object * obj,MemberOffset offset,mirror::Object * ref)2795 void ConcurrentCopying::AssertToSpaceInvariant(mirror::Object* obj,
2796 MemberOffset offset,
2797 mirror::Object* ref) {
2798 CHECK_EQ(heap_->collector_type_, kCollectorTypeCC) << static_cast<size_t>(heap_->collector_type_);
2799 if (is_asserting_to_space_invariant_) {
2800 if (ref == nullptr) {
2801 // OK.
2802 return;
2803 } else if (region_space_->HasAddress(ref)) {
2804 // Check to-space invariant in region space (moving space).
2805 using RegionType = space::RegionSpace::RegionType;
2806 space::RegionSpace::RegionType type = region_space_->GetRegionTypeUnsafe(ref);
2807 if (type == RegionType::kRegionTypeToSpace) {
2808 // OK.
2809 return;
2810 } else if (type == RegionType::kRegionTypeUnevacFromSpace) {
2811 if (!IsMarkedInUnevacFromSpace(ref)) {
2812 LOG(FATAL_WITHOUT_ABORT) << "Found unmarked reference in unevac from-space:";
2813 // Remove memory protection from the region space and log debugging information.
2814 region_space_->Unprotect();
2815 LOG(FATAL_WITHOUT_ABORT) << DumpHeapReference(obj, offset, ref);
2816 Thread::Current()->DumpJavaStack(LOG_STREAM(FATAL_WITHOUT_ABORT));
2817 }
2818 CHECK(IsMarkedInUnevacFromSpace(ref)) << ref;
2819 } else {
2820 // Not OK: either a from-space ref or a reference in an unused region.
2821 if (type == RegionType::kRegionTypeFromSpace) {
2822 LOG(FATAL_WITHOUT_ABORT) << "Found from-space reference:";
2823 } else {
2824 LOG(FATAL_WITHOUT_ABORT) << "Found reference in region with type " << type << ":";
2825 }
2826 // Remove memory protection from the region space and log debugging information.
2827 region_space_->Unprotect();
2828 LOG(FATAL_WITHOUT_ABORT) << DumpHeapReference(obj, offset, ref);
2829 if (obj != nullptr) {
2830 LogFromSpaceRefHolder(obj, offset);
2831 LOG(FATAL_WITHOUT_ABORT) << "UNEVAC " << region_space_->IsInUnevacFromSpace(obj) << " "
2832 << obj << " " << obj->GetMarkBit();
2833 if (region_space_->HasAddress(obj)) {
2834 region_space_->DumpRegionForObject(LOG_STREAM(FATAL_WITHOUT_ABORT), obj);
2835 }
2836 LOG(FATAL_WITHOUT_ABORT) << "CARD " << static_cast<size_t>(
2837 *Runtime::Current()->GetHeap()->GetCardTable()->CardFromAddr(
2838 reinterpret_cast<uint8_t*>(obj)));
2839 if (region_space_->HasAddress(obj)) {
2840 LOG(FATAL_WITHOUT_ABORT) << "BITMAP " << region_space_bitmap_->Test(obj);
2841 } else {
2842 accounting::ContinuousSpaceBitmap* mark_bitmap =
2843 heap_mark_bitmap_->GetContinuousSpaceBitmap(obj);
2844 if (mark_bitmap != nullptr) {
2845 LOG(FATAL_WITHOUT_ABORT) << "BITMAP " << mark_bitmap->Test(obj);
2846 } else {
2847 accounting::LargeObjectBitmap* los_bitmap =
2848 heap_mark_bitmap_->GetLargeObjectBitmap(obj);
2849 LOG(FATAL_WITHOUT_ABORT) << "BITMAP " << los_bitmap->Test(obj);
2850 }
2851 }
2852 }
2853 ref->GetLockWord(false).Dump(LOG_STREAM(FATAL_WITHOUT_ABORT));
2854 LOG(FATAL_WITHOUT_ABORT) << "Non-free regions:";
2855 region_space_->DumpNonFreeRegions(LOG_STREAM(FATAL_WITHOUT_ABORT));
2856 PrintFileToLog("/proc/self/maps", LogSeverity::FATAL_WITHOUT_ABORT);
2857 MemMap::DumpMaps(LOG_STREAM(FATAL_WITHOUT_ABORT), /* terse= */ true);
2858 LOG(FATAL) << "Invalid reference " << ref
2859 << " referenced from object " << obj << " at offset " << offset;
2860 }
2861 } else {
2862 // Check to-space invariant in non-moving space.
2863 AssertToSpaceInvariantInNonMovingSpace(obj, ref);
2864 }
2865 }
2866 }
2867
2868 class RootPrinter {
2869 public:
RootPrinter()2870 RootPrinter() { }
2871
2872 template <class MirrorType>
VisitRootIfNonNull(mirror::CompressedReference<MirrorType> * root)2873 ALWAYS_INLINE void VisitRootIfNonNull(mirror::CompressedReference<MirrorType>* root)
2874 REQUIRES_SHARED(Locks::mutator_lock_) {
2875 if (!root->IsNull()) {
2876 VisitRoot(root);
2877 }
2878 }
2879
2880 template <class MirrorType>
VisitRoot(mirror::Object ** root)2881 void VisitRoot(mirror::Object** root)
2882 REQUIRES_SHARED(Locks::mutator_lock_) {
2883 LOG(FATAL_WITHOUT_ABORT) << "root=" << root << " ref=" << *root;
2884 }
2885
2886 template <class MirrorType>
VisitRoot(mirror::CompressedReference<MirrorType> * root)2887 void VisitRoot(mirror::CompressedReference<MirrorType>* root)
2888 REQUIRES_SHARED(Locks::mutator_lock_) {
2889 LOG(FATAL_WITHOUT_ABORT) << "root=" << root << " ref=" << root->AsMirrorPtr();
2890 }
2891 };
2892
DumpGcRoot(mirror::Object * ref)2893 std::string ConcurrentCopying::DumpGcRoot(mirror::Object* ref) {
2894 std::ostringstream oss;
2895 constexpr const char* kIndent = " ";
2896 oss << kIndent << "Invalid GC root: ref=" << ref << '\n';
2897 // Information about `ref`.
2898 oss << DumpReferenceInfo(ref, "ref", kIndent);
2899 return oss.str();
2900 }
2901
AssertToSpaceInvariant(GcRootSource * gc_root_source,mirror::Object * ref)2902 void ConcurrentCopying::AssertToSpaceInvariant(GcRootSource* gc_root_source,
2903 mirror::Object* ref) {
2904 CHECK_EQ(heap_->collector_type_, kCollectorTypeCC) << static_cast<size_t>(heap_->collector_type_);
2905 if (is_asserting_to_space_invariant_) {
2906 if (ref == nullptr) {
2907 // OK.
2908 return;
2909 } else if (region_space_->HasAddress(ref)) {
2910 // Check to-space invariant in region space (moving space).
2911 using RegionType = space::RegionSpace::RegionType;
2912 space::RegionSpace::RegionType type = region_space_->GetRegionTypeUnsafe(ref);
2913 if (type == RegionType::kRegionTypeToSpace) {
2914 // OK.
2915 return;
2916 } else if (type == RegionType::kRegionTypeUnevacFromSpace) {
2917 if (!IsMarkedInUnevacFromSpace(ref)) {
2918 LOG(FATAL_WITHOUT_ABORT) << "Found unmarked reference in unevac from-space:";
2919 // Remove memory protection from the region space and log debugging information.
2920 region_space_->Unprotect();
2921 LOG(FATAL_WITHOUT_ABORT) << DumpGcRoot(ref);
2922 }
2923 CHECK(IsMarkedInUnevacFromSpace(ref)) << ref;
2924 } else {
2925 // Not OK: either a from-space ref or a reference in an unused region.
2926 if (type == RegionType::kRegionTypeFromSpace) {
2927 LOG(FATAL_WITHOUT_ABORT) << "Found from-space reference:";
2928 } else {
2929 LOG(FATAL_WITHOUT_ABORT) << "Found reference in region with type " << type << ":";
2930 }
2931 // Remove memory protection from the region space and log debugging information.
2932 region_space_->Unprotect();
2933 LOG(FATAL_WITHOUT_ABORT) << DumpGcRoot(ref);
2934 if (gc_root_source == nullptr) {
2935 // No info.
2936 } else if (gc_root_source->HasArtField()) {
2937 ArtField* field = gc_root_source->GetArtField();
2938 LOG(FATAL_WITHOUT_ABORT) << "gc root in field " << field << " "
2939 << ArtField::PrettyField(field);
2940 RootPrinter root_printer;
2941 field->VisitRoots(root_printer);
2942 } else if (gc_root_source->HasArtMethod()) {
2943 ArtMethod* method = gc_root_source->GetArtMethod();
2944 LOG(FATAL_WITHOUT_ABORT) << "gc root in method " << method << " "
2945 << ArtMethod::PrettyMethod(method);
2946 RootPrinter root_printer;
2947 method->VisitRoots(root_printer, kRuntimePointerSize);
2948 }
2949 ref->GetLockWord(false).Dump(LOG_STREAM(FATAL_WITHOUT_ABORT));
2950 LOG(FATAL_WITHOUT_ABORT) << "Non-free regions:";
2951 region_space_->DumpNonFreeRegions(LOG_STREAM(FATAL_WITHOUT_ABORT));
2952 PrintFileToLog("/proc/self/maps", LogSeverity::FATAL_WITHOUT_ABORT);
2953 MemMap::DumpMaps(LOG_STREAM(FATAL_WITHOUT_ABORT), /* terse= */ true);
2954 LOG(FATAL) << "Invalid reference " << ref;
2955 }
2956 } else {
2957 // Check to-space invariant in non-moving space.
2958 AssertToSpaceInvariantInNonMovingSpace(/* obj= */ nullptr, ref);
2959 }
2960 }
2961 }
2962
LogFromSpaceRefHolder(mirror::Object * obj,MemberOffset offset)2963 void ConcurrentCopying::LogFromSpaceRefHolder(mirror::Object* obj, MemberOffset offset) {
2964 if (kUseBakerReadBarrier) {
2965 LOG(INFO) << "holder=" << obj << " " << obj->PrettyTypeOf()
2966 << " holder rb_state=" << obj->GetReadBarrierState();
2967 } else {
2968 LOG(INFO) << "holder=" << obj << " " << obj->PrettyTypeOf();
2969 }
2970 if (region_space_->IsInFromSpace(obj)) {
2971 LOG(INFO) << "holder is in the from-space.";
2972 } else if (region_space_->IsInToSpace(obj)) {
2973 LOG(INFO) << "holder is in the to-space.";
2974 } else if (region_space_->IsInUnevacFromSpace(obj)) {
2975 LOG(INFO) << "holder is in the unevac from-space.";
2976 if (IsMarkedInUnevacFromSpace(obj)) {
2977 LOG(INFO) << "holder is marked in the region space bitmap.";
2978 } else {
2979 LOG(INFO) << "holder is not marked in the region space bitmap.";
2980 }
2981 } else {
2982 // In a non-moving space.
2983 if (immune_spaces_.ContainsObject(obj)) {
2984 LOG(INFO) << "holder is in an immune image or the zygote space.";
2985 } else {
2986 LOG(INFO) << "holder is in a non-immune, non-moving (or main) space.";
2987 accounting::ContinuousSpaceBitmap* mark_bitmap = heap_->GetNonMovingSpace()->GetMarkBitmap();
2988 accounting::LargeObjectBitmap* los_bitmap = nullptr;
2989 const bool is_los = !mark_bitmap->HasAddress(obj);
2990 if (is_los) {
2991 DCHECK(heap_->GetLargeObjectsSpace() && heap_->GetLargeObjectsSpace()->Contains(obj))
2992 << "obj=" << obj
2993 << " LOS bit map covers the entire lower 4GB address range";
2994 los_bitmap = heap_->GetLargeObjectsSpace()->GetMarkBitmap();
2995 }
2996 if (!is_los && mark_bitmap->Test(obj)) {
2997 LOG(INFO) << "holder is marked in the non-moving space mark bit map.";
2998 } else if (is_los && los_bitmap->Test(obj)) {
2999 LOG(INFO) << "holder is marked in the los bit map.";
3000 } else {
3001 // If ref is on the allocation stack, then it is considered
3002 // mark/alive (but not necessarily on the live stack.)
3003 if (IsOnAllocStack(obj)) {
3004 LOG(INFO) << "holder is on the alloc stack.";
3005 } else {
3006 LOG(INFO) << "holder is not marked or on the alloc stack.";
3007 }
3008 }
3009 }
3010 }
3011 LOG(INFO) << "offset=" << offset.SizeValue();
3012 }
3013
IsMarkedInNonMovingSpace(mirror::Object * from_ref)3014 bool ConcurrentCopying::IsMarkedInNonMovingSpace(mirror::Object* from_ref) {
3015 DCHECK(!region_space_->HasAddress(from_ref)) << "ref=" << from_ref;
3016 DCHECK(!immune_spaces_.ContainsObject(from_ref)) << "ref=" << from_ref;
3017 if (kUseBakerReadBarrier && from_ref->GetReadBarrierStateAcquire() == ReadBarrier::GrayState()) {
3018 return true;
3019 } else if (!use_generational_cc_ || done_scanning_.load(std::memory_order_acquire)) {
3020 // Read the comment in IsMarkedInUnevacFromSpace()
3021 accounting::ContinuousSpaceBitmap* mark_bitmap = heap_->GetNonMovingSpace()->GetMarkBitmap();
3022 accounting::LargeObjectBitmap* los_bitmap = nullptr;
3023 const bool is_los = !mark_bitmap->HasAddress(from_ref);
3024 if (is_los) {
3025 DCHECK(heap_->GetLargeObjectsSpace() && heap_->GetLargeObjectsSpace()->Contains(from_ref))
3026 << "ref=" << from_ref
3027 << " doesn't belong to non-moving space and large object space doesn't exist";
3028 los_bitmap = heap_->GetLargeObjectsSpace()->GetMarkBitmap();
3029 }
3030 if (is_los ? los_bitmap->Test(from_ref) : mark_bitmap->Test(from_ref)) {
3031 return true;
3032 }
3033 }
3034 return IsOnAllocStack(from_ref);
3035 }
3036
AssertToSpaceInvariantInNonMovingSpace(mirror::Object * obj,mirror::Object * ref)3037 void ConcurrentCopying::AssertToSpaceInvariantInNonMovingSpace(mirror::Object* obj,
3038 mirror::Object* ref) {
3039 CHECK(ref != nullptr);
3040 CHECK(!region_space_->HasAddress(ref)) << "obj=" << obj << " ref=" << ref;
3041 // In a non-moving space. Check that the ref is marked.
3042 if (immune_spaces_.ContainsObject(ref)) {
3043 // Immune space case.
3044 if (kUseBakerReadBarrier) {
3045 // Immune object may not be gray if called from the GC.
3046 if (Thread::Current() == thread_running_gc_ && !gc_grays_immune_objects_) {
3047 return;
3048 }
3049 bool updated_all_immune_objects = updated_all_immune_objects_.load(std::memory_order_seq_cst);
3050 CHECK(updated_all_immune_objects || ref->GetReadBarrierState() == ReadBarrier::GrayState())
3051 << "Unmarked immune space ref. obj=" << obj << " rb_state="
3052 << (obj != nullptr ? obj->GetReadBarrierState() : 0U)
3053 << " ref=" << ref << " ref rb_state=" << ref->GetReadBarrierState()
3054 << " updated_all_immune_objects=" << updated_all_immune_objects;
3055 }
3056 } else {
3057 // Non-moving space and large-object space (LOS) cases.
3058 // If `ref` is on the allocation stack, then it may not be
3059 // marked live, but considered marked/alive (but not
3060 // necessarily on the live stack).
3061 CHECK(IsMarkedInNonMovingSpace(ref))
3062 << "Unmarked ref that's not on the allocation stack."
3063 << " obj=" << obj
3064 << " ref=" << ref
3065 << " rb_state=" << ref->GetReadBarrierState()
3066 << " is_marking=" << std::boolalpha << is_marking_ << std::noboolalpha
3067 << " young_gen=" << std::boolalpha << young_gen_ << std::noboolalpha
3068 << " done_scanning="
3069 << std::boolalpha << done_scanning_.load(std::memory_order_acquire) << std::noboolalpha
3070 << " self=" << Thread::Current();
3071 }
3072 }
3073
3074 // Used to scan ref fields of an object.
3075 template <bool kNoUnEvac>
3076 class ConcurrentCopying::RefFieldsVisitor {
3077 public:
RefFieldsVisitor(ConcurrentCopying * collector,Thread * const thread)3078 explicit RefFieldsVisitor(ConcurrentCopying* collector, Thread* const thread)
3079 : collector_(collector), thread_(thread) {
3080 // Cannot have `kNoUnEvac` when Generational CC collection is disabled.
3081 DCHECK_IMPLIES(kNoUnEvac, collector_->use_generational_cc_);
3082 }
3083
operator ()(mirror::Object * obj,MemberOffset offset,bool) const3084 void operator()(mirror::Object* obj, MemberOffset offset, bool /* is_static */)
3085 const ALWAYS_INLINE REQUIRES_SHARED(Locks::mutator_lock_)
3086 REQUIRES_SHARED(Locks::heap_bitmap_lock_) {
3087 collector_->Process<kNoUnEvac>(obj, offset);
3088 }
3089
operator ()(ObjPtr<mirror::Class> klass,ObjPtr<mirror::Reference> ref) const3090 void operator()(ObjPtr<mirror::Class> klass, ObjPtr<mirror::Reference> ref) const
3091 REQUIRES_SHARED(Locks::mutator_lock_) ALWAYS_INLINE {
3092 CHECK(klass->IsTypeOfReferenceClass());
3093 collector_->DelayReferenceReferent(klass, ref);
3094 }
3095
VisitRootIfNonNull(mirror::CompressedReference<mirror::Object> * root) const3096 void VisitRootIfNonNull(mirror::CompressedReference<mirror::Object>* root) const
3097 ALWAYS_INLINE
3098 REQUIRES_SHARED(Locks::mutator_lock_) {
3099 if (!root->IsNull()) {
3100 VisitRoot(root);
3101 }
3102 }
3103
VisitRoot(mirror::CompressedReference<mirror::Object> * root) const3104 void VisitRoot(mirror::CompressedReference<mirror::Object>* root) const
3105 ALWAYS_INLINE
3106 REQUIRES_SHARED(Locks::mutator_lock_) {
3107 collector_->MarkRoot</*kGrayImmuneObject=*/false>(thread_, root);
3108 }
3109
3110 private:
3111 ConcurrentCopying* const collector_;
3112 Thread* const thread_;
3113 };
3114
3115 template <bool kNoUnEvac>
Scan(mirror::Object * to_ref,size_t obj_size)3116 inline void ConcurrentCopying::Scan(mirror::Object* to_ref, size_t obj_size) {
3117 // Cannot have `kNoUnEvac` when Generational CC collection is disabled.
3118 DCHECK_IMPLIES(kNoUnEvac, use_generational_cc_);
3119 if (kDisallowReadBarrierDuringScan && !Runtime::Current()->IsActiveTransaction()) {
3120 // Avoid all read barriers during visit references to help performance.
3121 // Don't do this in transaction mode because we may read the old value of an field which may
3122 // trigger read barriers.
3123 Thread::Current()->ModifyDebugDisallowReadBarrier(1);
3124 }
3125 if (obj_size == 0) {
3126 obj_size = to_ref->SizeOf<kDefaultVerifyFlags>();
3127 }
3128 bytes_scanned_ += obj_size;
3129
3130 DCHECK(!region_space_->IsInFromSpace(to_ref));
3131 DCHECK_EQ(Thread::Current(), thread_running_gc_);
3132 RefFieldsVisitor<kNoUnEvac> visitor(this, thread_running_gc_);
3133 // Disable the read barrier for a performance reason.
3134 to_ref->VisitReferences</*kVisitNativeRoots=*/true, kDefaultVerifyFlags, kWithoutReadBarrier>(
3135 visitor, visitor);
3136 if (kDisallowReadBarrierDuringScan && !Runtime::Current()->IsActiveTransaction()) {
3137 thread_running_gc_->ModifyDebugDisallowReadBarrier(-1);
3138 }
3139 }
3140
3141 template <bool kNoUnEvac>
Process(mirror::Object * obj,MemberOffset offset)3142 inline void ConcurrentCopying::Process(mirror::Object* obj, MemberOffset offset) {
3143 // Cannot have `kNoUnEvac` when Generational CC collection is disabled.
3144 DCHECK_IMPLIES(kNoUnEvac, use_generational_cc_);
3145 DCHECK_EQ(Thread::Current(), thread_running_gc_);
3146 mirror::Object* ref = obj->GetFieldObject<
3147 mirror::Object, kVerifyNone, kWithoutReadBarrier, false>(offset);
3148 mirror::Object* to_ref = Mark</*kGrayImmuneObject=*/false, kNoUnEvac, /*kFromGCThread=*/true>(
3149 thread_running_gc_,
3150 ref,
3151 /*holder=*/ obj,
3152 offset);
3153 if (to_ref == ref) {
3154 return;
3155 }
3156 // This may fail if the mutator writes to the field at the same time. But it's ok.
3157 mirror::Object* expected_ref = ref;
3158 mirror::Object* new_ref = to_ref;
3159 do {
3160 if (expected_ref !=
3161 obj->GetFieldObject<mirror::Object, kVerifyNone, kWithoutReadBarrier, false>(offset)) {
3162 // It was updated by the mutator.
3163 break;
3164 }
3165 // Use release CAS to make sure threads reading the reference see contents of copied objects.
3166 } while (!obj->CasFieldObjectWithoutWriteBarrier<false, false, kVerifyNone>(
3167 offset,
3168 expected_ref,
3169 new_ref,
3170 CASMode::kWeak,
3171 std::memory_order_release));
3172 }
3173
3174 // Process some roots.
VisitRoots(mirror::Object *** roots,size_t count,const RootInfo & info)3175 inline void ConcurrentCopying::VisitRoots(mirror::Object*** roots,
3176 size_t count,
3177 [[maybe_unused]] const RootInfo& info) {
3178 Thread* const self = Thread::Current();
3179 for (size_t i = 0; i < count; ++i) {
3180 mirror::Object** root = roots[i];
3181 mirror::Object* ref = *root;
3182 mirror::Object* to_ref = Mark(self, ref);
3183 if (to_ref == ref) {
3184 continue;
3185 }
3186 Atomic<mirror::Object*>* addr = reinterpret_cast<Atomic<mirror::Object*>*>(root);
3187 mirror::Object* expected_ref = ref;
3188 mirror::Object* new_ref = to_ref;
3189 do {
3190 if (expected_ref != addr->load(std::memory_order_relaxed)) {
3191 // It was updated by the mutator.
3192 break;
3193 }
3194 } while (!addr->CompareAndSetWeakRelaxed(expected_ref, new_ref));
3195 }
3196 }
3197
3198 template<bool kGrayImmuneObject>
MarkRoot(Thread * const self,mirror::CompressedReference<mirror::Object> * root)3199 inline void ConcurrentCopying::MarkRoot(Thread* const self,
3200 mirror::CompressedReference<mirror::Object>* root) {
3201 DCHECK(!root->IsNull());
3202 mirror::Object* const ref = root->AsMirrorPtr();
3203 mirror::Object* to_ref = Mark<kGrayImmuneObject>(self, ref);
3204 if (to_ref != ref) {
3205 auto* addr = reinterpret_cast<Atomic<mirror::CompressedReference<mirror::Object>>*>(root);
3206 auto expected_ref = mirror::CompressedReference<mirror::Object>::FromMirrorPtr(ref);
3207 auto new_ref = mirror::CompressedReference<mirror::Object>::FromMirrorPtr(to_ref);
3208 // If the cas fails, then it was updated by the mutator.
3209 do {
3210 if (ref != addr->load(std::memory_order_relaxed).AsMirrorPtr()) {
3211 // It was updated by the mutator.
3212 break;
3213 }
3214 } while (!addr->CompareAndSetWeakRelaxed(expected_ref, new_ref));
3215 }
3216 }
3217
VisitRoots(mirror::CompressedReference<mirror::Object> ** roots,size_t count,const RootInfo & info)3218 inline void ConcurrentCopying::VisitRoots(mirror::CompressedReference<mirror::Object>** roots,
3219 size_t count,
3220 [[maybe_unused]] const RootInfo& info) {
3221 Thread* const self = Thread::Current();
3222 for (size_t i = 0; i < count; ++i) {
3223 mirror::CompressedReference<mirror::Object>* const root = roots[i];
3224 if (!root->IsNull()) {
3225 // kGrayImmuneObject is true because this is used for the thread flip.
3226 MarkRoot</*kGrayImmuneObject=*/true>(self, root);
3227 }
3228 }
3229 }
3230
3231 // Temporary set gc_grays_immune_objects_ to true in a scope if the current thread is GC.
3232 class ConcurrentCopying::ScopedGcGraysImmuneObjects {
3233 public:
ScopedGcGraysImmuneObjects(ConcurrentCopying * collector)3234 explicit ScopedGcGraysImmuneObjects(ConcurrentCopying* collector)
3235 : collector_(collector), enabled_(false) {
3236 if (kUseBakerReadBarrier &&
3237 collector_->thread_running_gc_ == Thread::Current() &&
3238 !collector_->gc_grays_immune_objects_) {
3239 collector_->gc_grays_immune_objects_ = true;
3240 enabled_ = true;
3241 }
3242 }
3243
~ScopedGcGraysImmuneObjects()3244 ~ScopedGcGraysImmuneObjects() {
3245 if (kUseBakerReadBarrier &&
3246 collector_->thread_running_gc_ == Thread::Current() &&
3247 enabled_) {
3248 DCHECK(collector_->gc_grays_immune_objects_);
3249 collector_->gc_grays_immune_objects_ = false;
3250 }
3251 }
3252
3253 private:
3254 ConcurrentCopying* const collector_;
3255 bool enabled_;
3256 };
3257
3258 // Fill the given memory block with a fake object. Used to fill in a
3259 // copy of objects that was lost in race.
FillWithFakeObject(Thread * const self,mirror::Object * fake_obj,size_t byte_size)3260 void ConcurrentCopying::FillWithFakeObject(Thread* const self,
3261 mirror::Object* fake_obj,
3262 size_t byte_size) {
3263 // GC doesn't gray immune objects while scanning immune objects. But we need to trigger the read
3264 // barriers here because we need the updated reference to the int array class, etc. Temporary set
3265 // gc_grays_immune_objects_ to true so that we won't cause a DCHECK failure in MarkImmuneSpace().
3266 ScopedGcGraysImmuneObjects scoped_gc_gray_immune_objects(this);
3267 CHECK_ALIGNED(byte_size, kObjectAlignment);
3268 memset(fake_obj, 0, byte_size);
3269 // Avoid going through read barrier for since kDisallowReadBarrierDuringScan may be enabled.
3270 // Explicitly mark to make sure to get an object in the to-space.
3271 mirror::Class* int_array_class = down_cast<mirror::Class*>(
3272 Mark(self, GetClassRoot<mirror::IntArray, kWithoutReadBarrier>().Ptr()));
3273 CHECK(int_array_class != nullptr);
3274 if (ReadBarrier::kEnableToSpaceInvariantChecks) {
3275 AssertToSpaceInvariant(nullptr, MemberOffset(0), int_array_class);
3276 }
3277 size_t component_size = int_array_class->GetComponentSize();
3278 CHECK_EQ(component_size, sizeof(int32_t));
3279 size_t data_offset = mirror::Array::DataOffset(component_size).SizeValue();
3280 if (data_offset > byte_size) {
3281 // An int array is too big. Use java.lang.Object.
3282 CHECK(java_lang_Object_ != nullptr);
3283 if (ReadBarrier::kEnableToSpaceInvariantChecks) {
3284 AssertToSpaceInvariant(nullptr, MemberOffset(0), java_lang_Object_);
3285 }
3286 CHECK_EQ(byte_size, java_lang_Object_->GetObjectSize<kVerifyNone>());
3287 fake_obj->SetClass(java_lang_Object_);
3288 CHECK_EQ(byte_size, (fake_obj->SizeOf<kVerifyNone>()));
3289 } else {
3290 // Use an int array.
3291 fake_obj->SetClass(int_array_class);
3292 CHECK(fake_obj->IsArrayInstance<kVerifyNone>());
3293 int32_t length = (byte_size - data_offset) / component_size;
3294 ObjPtr<mirror::Array> fake_arr = fake_obj->AsArray<kVerifyNone>();
3295 fake_arr->SetLength(length);
3296 CHECK_EQ(fake_arr->GetLength(), length)
3297 << "byte_size=" << byte_size << " length=" << length
3298 << " component_size=" << component_size << " data_offset=" << data_offset;
3299 CHECK_EQ(byte_size, (fake_obj->SizeOf<kVerifyNone>()))
3300 << "byte_size=" << byte_size << " length=" << length
3301 << " component_size=" << component_size << " data_offset=" << data_offset;
3302 }
3303 }
3304
3305 // Reuse the memory blocks that were copy of objects that were lost in race.
AllocateInSkippedBlock(Thread * const self,size_t alloc_size)3306 mirror::Object* ConcurrentCopying::AllocateInSkippedBlock(Thread* const self, size_t alloc_size) {
3307 // Try to reuse the blocks that were unused due to CAS failures.
3308 CHECK_ALIGNED(alloc_size, space::RegionSpace::kAlignment);
3309 size_t min_object_size = RoundUp(sizeof(mirror::Object), space::RegionSpace::kAlignment);
3310 size_t byte_size;
3311 uint8_t* addr;
3312 {
3313 MutexLock mu(self, skipped_blocks_lock_);
3314 auto it = skipped_blocks_map_.lower_bound(alloc_size);
3315 if (it == skipped_blocks_map_.end()) {
3316 // Not found.
3317 return nullptr;
3318 }
3319 byte_size = it->first;
3320 CHECK_GE(byte_size, alloc_size);
3321 if (byte_size > alloc_size && byte_size - alloc_size < min_object_size) {
3322 // If remainder would be too small for a fake object, retry with a larger request size.
3323 it = skipped_blocks_map_.lower_bound(alloc_size + min_object_size);
3324 if (it == skipped_blocks_map_.end()) {
3325 // Not found.
3326 return nullptr;
3327 }
3328 CHECK_ALIGNED(it->first - alloc_size, space::RegionSpace::kAlignment);
3329 CHECK_GE(it->first - alloc_size, min_object_size)
3330 << "byte_size=" << byte_size << " it->first=" << it->first << " alloc_size=" << alloc_size;
3331 }
3332 // Found a block.
3333 CHECK(it != skipped_blocks_map_.end());
3334 byte_size = it->first;
3335 addr = it->second;
3336 CHECK_GE(byte_size, alloc_size);
3337 CHECK(region_space_->IsInToSpace(reinterpret_cast<mirror::Object*>(addr)));
3338 CHECK_ALIGNED(byte_size, space::RegionSpace::kAlignment);
3339 if (kVerboseMode) {
3340 LOG(INFO) << "Reusing skipped bytes : " << reinterpret_cast<void*>(addr) << ", " << byte_size;
3341 }
3342 skipped_blocks_map_.erase(it);
3343 }
3344 memset(addr, 0, byte_size);
3345 if (byte_size > alloc_size) {
3346 // Return the remainder to the map.
3347 CHECK_ALIGNED(byte_size - alloc_size, space::RegionSpace::kAlignment);
3348 CHECK_GE(byte_size - alloc_size, min_object_size);
3349 // FillWithFakeObject may mark an object, avoid holding skipped_blocks_lock_ to prevent lock
3350 // violation and possible deadlock. The deadlock case is a recursive case:
3351 // FillWithFakeObject -> Mark(IntArray.class) -> Copy -> AllocateInSkippedBlock.
3352 FillWithFakeObject(self,
3353 reinterpret_cast<mirror::Object*>(addr + alloc_size),
3354 byte_size - alloc_size);
3355 CHECK(region_space_->IsInToSpace(reinterpret_cast<mirror::Object*>(addr + alloc_size)));
3356 {
3357 MutexLock mu(self, skipped_blocks_lock_);
3358 skipped_blocks_map_.insert(std::make_pair(byte_size - alloc_size, addr + alloc_size));
3359 }
3360 }
3361 return reinterpret_cast<mirror::Object*>(addr);
3362 }
3363
Copy(Thread * const self,mirror::Object * from_ref,mirror::Object * holder,MemberOffset offset)3364 mirror::Object* ConcurrentCopying::Copy(Thread* const self,
3365 mirror::Object* from_ref,
3366 mirror::Object* holder,
3367 MemberOffset offset) {
3368 DCHECK(region_space_->IsInFromSpace(from_ref));
3369 // If the class pointer is null, the object is invalid. This could occur for a dangling pointer
3370 // from a previous GC that is either inside or outside the allocated region.
3371 mirror::Class* klass = from_ref->GetClass<kVerifyNone, kWithoutReadBarrier>();
3372 if (UNLIKELY(klass == nullptr)) {
3373 // Remove memory protection from the region space and log debugging information.
3374 region_space_->Unprotect();
3375 heap_->GetVerification()->LogHeapCorruption(holder, offset, from_ref, /* fatal= */ true);
3376 }
3377 // There must not be a read barrier to avoid nested RB that might violate the to-space invariant.
3378 // Note that from_ref is a from space ref so the SizeOf() call will access the from-space meta
3379 // objects, but it's ok and necessary.
3380 size_t obj_size = from_ref->SizeOf<kDefaultVerifyFlags>();
3381 size_t region_space_alloc_size = RoundUp(obj_size, space::RegionSpace::kAlignment);
3382 // Large objects are never evacuated.
3383 CHECK_LE(region_space_alloc_size, space::RegionSpace::kRegionSize);
3384 size_t region_space_bytes_allocated = 0U;
3385 size_t non_moving_space_bytes_allocated = 0U;
3386 size_t bytes_allocated = 0U;
3387 size_t unused_size;
3388 bool fall_back_to_non_moving = false;
3389 mirror::Object* to_ref = region_space_->AllocNonvirtual</*kForEvac=*/ true>(
3390 region_space_alloc_size, ®ion_space_bytes_allocated, nullptr, &unused_size);
3391 bytes_allocated = region_space_bytes_allocated;
3392 if (LIKELY(to_ref != nullptr)) {
3393 DCHECK_EQ(region_space_alloc_size, region_space_bytes_allocated);
3394 } else {
3395 // Failed to allocate in the region space. Try the skipped blocks.
3396 to_ref = AllocateInSkippedBlock(self, region_space_alloc_size);
3397 if (to_ref != nullptr) {
3398 // Succeeded to allocate in a skipped block.
3399 if (heap_->use_tlab_) {
3400 // This is necessary for the tlab case as it's not accounted in the space.
3401 region_space_->RecordAlloc(to_ref);
3402 }
3403 bytes_allocated = region_space_alloc_size;
3404 heap_->num_bytes_allocated_.fetch_sub(bytes_allocated, std::memory_order_relaxed);
3405 to_space_bytes_skipped_.fetch_sub(bytes_allocated, std::memory_order_relaxed);
3406 to_space_objects_skipped_.fetch_sub(1, std::memory_order_relaxed);
3407 } else {
3408 // Fall back to the non-moving space.
3409 fall_back_to_non_moving = true;
3410 if (kVerboseMode) {
3411 LOG(INFO) << "Out of memory in the to-space. Fall back to non-moving. skipped_bytes="
3412 << to_space_bytes_skipped_.load(std::memory_order_relaxed)
3413 << " skipped_objects="
3414 << to_space_objects_skipped_.load(std::memory_order_relaxed);
3415 }
3416 to_ref = heap_->non_moving_space_->Alloc(
3417 self, obj_size, &non_moving_space_bytes_allocated, nullptr, &unused_size);
3418 if (UNLIKELY(to_ref == nullptr)) {
3419 LOG(FATAL_WITHOUT_ABORT) << "Fall-back non-moving space allocation failed for a "
3420 << obj_size << " byte object in region type "
3421 << region_space_->GetRegionType(from_ref);
3422 LOG(FATAL) << "Object address=" << from_ref << " type=" << from_ref->PrettyTypeOf();
3423 }
3424 bytes_allocated = non_moving_space_bytes_allocated;
3425 }
3426 }
3427 DCHECK(to_ref != nullptr);
3428
3429 // Copy the object excluding the lock word since that is handled in the loop.
3430 to_ref->SetClass(klass);
3431 const size_t kObjectHeaderSize = sizeof(mirror::Object);
3432 DCHECK_GE(obj_size, kObjectHeaderSize);
3433 static_assert(kObjectHeaderSize == sizeof(mirror::HeapReference<mirror::Class>) +
3434 sizeof(LockWord),
3435 "Object header size does not match");
3436 // Memcpy can tear for words since it may do byte copy. It is only safe to do this since the
3437 // object in the from space is immutable other than the lock word. b/31423258
3438 memcpy(reinterpret_cast<uint8_t*>(to_ref) + kObjectHeaderSize,
3439 reinterpret_cast<const uint8_t*>(from_ref) + kObjectHeaderSize,
3440 obj_size - kObjectHeaderSize);
3441
3442 // Attempt to install the forward pointer. This is in a loop as the
3443 // lock word atomic write can fail.
3444 while (true) {
3445 LockWord old_lock_word = from_ref->GetLockWord(false);
3446
3447 if (old_lock_word.GetState() == LockWord::kForwardingAddress) {
3448 // Lost the race. Another thread (either GC or mutator) stored
3449 // the forwarding pointer first. Make the lost copy (to_ref)
3450 // look like a valid but dead (fake) object and keep it for
3451 // future reuse.
3452 FillWithFakeObject(self, to_ref, bytes_allocated);
3453 if (!fall_back_to_non_moving) {
3454 DCHECK(region_space_->IsInToSpace(to_ref));
3455 // Record the lost copy for later reuse.
3456 heap_->num_bytes_allocated_.fetch_add(bytes_allocated, std::memory_order_relaxed);
3457 to_space_bytes_skipped_.fetch_add(bytes_allocated, std::memory_order_relaxed);
3458 to_space_objects_skipped_.fetch_add(1, std::memory_order_relaxed);
3459 MutexLock mu(self, skipped_blocks_lock_);
3460 skipped_blocks_map_.insert(std::make_pair(bytes_allocated,
3461 reinterpret_cast<uint8_t*>(to_ref)));
3462 } else {
3463 DCHECK(heap_->non_moving_space_->HasAddress(to_ref));
3464 DCHECK_EQ(bytes_allocated, non_moving_space_bytes_allocated);
3465 // Free the non-moving-space chunk.
3466 heap_->non_moving_space_->Free(self, to_ref);
3467 }
3468
3469 // Get the winner's forward ptr.
3470 mirror::Object* lost_fwd_ptr = to_ref;
3471 to_ref = reinterpret_cast<mirror::Object*>(old_lock_word.ForwardingAddress());
3472 CHECK(to_ref != nullptr);
3473 CHECK_NE(to_ref, lost_fwd_ptr);
3474 CHECK(region_space_->IsInToSpace(to_ref) || heap_->non_moving_space_->HasAddress(to_ref))
3475 << "to_ref=" << to_ref << " " << heap_->DumpSpaces();
3476 CHECK_NE(to_ref->GetLockWord(false).GetState(), LockWord::kForwardingAddress);
3477 return to_ref;
3478 }
3479
3480 // Copy the old lock word over since we did not copy it yet.
3481 to_ref->SetLockWord(old_lock_word, false);
3482 // Set the gray ptr.
3483 if (kUseBakerReadBarrier) {
3484 to_ref->SetReadBarrierState(ReadBarrier::GrayState());
3485 }
3486
3487 LockWord new_lock_word = LockWord::FromForwardingAddress(reinterpret_cast<size_t>(to_ref));
3488
3489 // Try to atomically write the fwd ptr. Make sure that the copied object is visible to any
3490 // readers of the fwd pointer.
3491 bool success = from_ref->CasLockWord(old_lock_word,
3492 new_lock_word,
3493 CASMode::kWeak,
3494 std::memory_order_release);
3495 if (LIKELY(success)) {
3496 // The CAS succeeded.
3497 DCHECK(thread_running_gc_ != nullptr);
3498 if (LIKELY(self == thread_running_gc_)) {
3499 objects_moved_gc_thread_ += 1;
3500 bytes_moved_gc_thread_ += bytes_allocated;
3501 } else {
3502 objects_moved_.fetch_add(1, std::memory_order_relaxed);
3503 bytes_moved_.fetch_add(bytes_allocated, std::memory_order_relaxed);
3504 }
3505
3506 if (LIKELY(!fall_back_to_non_moving)) {
3507 DCHECK(region_space_->IsInToSpace(to_ref));
3508 } else {
3509 DCHECK(heap_->non_moving_space_->HasAddress(to_ref));
3510 DCHECK_EQ(bytes_allocated, non_moving_space_bytes_allocated);
3511 if (!use_generational_cc_ || !young_gen_) {
3512 // Mark it in the live bitmap.
3513 CHECK(!heap_->non_moving_space_->GetLiveBitmap()->AtomicTestAndSet(to_ref));
3514 }
3515 if (!kUseBakerReadBarrier) {
3516 // Mark it in the mark bitmap.
3517 CHECK(!heap_->non_moving_space_->GetMarkBitmap()->AtomicTestAndSet(to_ref));
3518 }
3519 }
3520 if (kUseBakerReadBarrier) {
3521 DCHECK(to_ref->GetReadBarrierState() == ReadBarrier::GrayState());
3522 }
3523 DCHECK(GetFwdPtr(from_ref) == to_ref);
3524 CHECK_NE(to_ref->GetLockWord(false).GetState(), LockWord::kForwardingAddress);
3525 // Make sure that anyone who sees to_ref also sees both the object contents and the
3526 // fwd pointer.
3527 QuasiAtomic::ThreadFenceForConstructor();
3528 PushOntoMarkStack(self, to_ref);
3529 return to_ref;
3530 } else {
3531 // The CAS failed. It may have lost the race or may have failed
3532 // due to monitor/hashcode ops. Either way, retry.
3533 }
3534 }
3535 }
3536
IsMarked(mirror::Object * from_ref)3537 mirror::Object* ConcurrentCopying::IsMarked(mirror::Object* from_ref) {
3538 DCHECK(from_ref != nullptr);
3539 space::RegionSpace::RegionType rtype = region_space_->GetRegionType(from_ref);
3540 if (rtype == space::RegionSpace::RegionType::kRegionTypeToSpace) {
3541 // It's already marked.
3542 return from_ref;
3543 }
3544 mirror::Object* to_ref;
3545 if (rtype == space::RegionSpace::RegionType::kRegionTypeFromSpace) {
3546 to_ref = GetFwdPtr(from_ref);
3547 DCHECK(to_ref == nullptr || region_space_->IsInToSpace(to_ref) ||
3548 heap_->non_moving_space_->HasAddress(to_ref))
3549 << "from_ref=" << from_ref << " to_ref=" << to_ref;
3550 } else if (rtype == space::RegionSpace::RegionType::kRegionTypeUnevacFromSpace) {
3551 if (IsMarkedInUnevacFromSpace(from_ref)) {
3552 to_ref = from_ref;
3553 } else {
3554 to_ref = nullptr;
3555 }
3556 } else {
3557 // At this point, `from_ref` should not be in the region space
3558 // (i.e. within an "unused" region).
3559 DCHECK(!region_space_->HasAddress(from_ref)) << from_ref;
3560 // from_ref is in a non-moving space.
3561 if (immune_spaces_.ContainsObject(from_ref)) {
3562 // An immune object is alive.
3563 to_ref = from_ref;
3564 } else {
3565 // Non-immune non-moving space. Use the mark bitmap.
3566 if (IsMarkedInNonMovingSpace(from_ref)) {
3567 // Already marked.
3568 to_ref = from_ref;
3569 } else {
3570 to_ref = nullptr;
3571 }
3572 }
3573 }
3574 return to_ref;
3575 }
3576
IsOnAllocStack(mirror::Object * ref)3577 bool ConcurrentCopying::IsOnAllocStack(mirror::Object* ref) {
3578 // Pairs with release fence after allocation-stack push in
3579 // Heap::AllocObjectWithAllocator().
3580 std::atomic_thread_fence(std::memory_order_acquire);
3581 accounting::ObjectStack* alloc_stack = GetAllocationStack();
3582 return alloc_stack->Contains(ref);
3583 }
3584
MarkNonMoving(Thread * const self,mirror::Object * ref,mirror::Object * holder,MemberOffset offset)3585 mirror::Object* ConcurrentCopying::MarkNonMoving(Thread* const self,
3586 mirror::Object* ref,
3587 mirror::Object* holder,
3588 MemberOffset offset) {
3589 // ref is in a non-moving space (from_ref == to_ref).
3590 DCHECK(!region_space_->HasAddress(ref)) << ref;
3591 DCHECK(!immune_spaces_.ContainsObject(ref));
3592 // Use the mark bitmap.
3593 accounting::ContinuousSpaceBitmap* mark_bitmap = heap_->GetNonMovingSpace()->GetMarkBitmap();
3594 accounting::LargeObjectBitmap* los_bitmap = nullptr;
3595 const bool is_los = !mark_bitmap->HasAddress(ref);
3596 if (is_los) {
3597 if (!IsAlignedParam(ref, space::LargeObjectSpace::ObjectAlignment())) {
3598 // Ref is a large object that is not aligned, it must be heap
3599 // corruption. Remove memory protection and dump data before
3600 // AtomicSetReadBarrierState since it will fault if the address is not
3601 // valid.
3602 region_space_->Unprotect();
3603 heap_->GetVerification()->LogHeapCorruption(holder, offset, ref, /* fatal= */ true);
3604 }
3605 DCHECK(heap_->GetLargeObjectsSpace())
3606 << "ref=" << ref
3607 << " doesn't belong to non-moving space and large object space doesn't exist";
3608 los_bitmap = heap_->GetLargeObjectsSpace()->GetMarkBitmap();
3609 DCHECK(los_bitmap->HasAddress(ref));
3610 }
3611 if (use_generational_cc_) {
3612 // The sticky-bit CC collector is only compatible with Baker-style read barriers.
3613 DCHECK(kUseBakerReadBarrier);
3614 // Not done scanning, use AtomicSetReadBarrierPointer.
3615 if (!done_scanning_.load(std::memory_order_acquire)) {
3616 // Since the mark bitmap is still filled in from last GC, we can not use that or else the
3617 // mutator may see references to the from space. Instead, use the Baker pointer itself as
3618 // the mark bit.
3619 //
3620 // We need to avoid marking objects that are on allocation stack as that will lead to a
3621 // situation (after this GC cycle is finished) where some object(s) are on both allocation
3622 // stack and live bitmap. This leads to visiting the same object(s) twice during a heapdump
3623 // (b/117426281).
3624 if (!IsOnAllocStack(ref) &&
3625 ref->AtomicSetReadBarrierState(ReadBarrier::NonGrayState(), ReadBarrier::GrayState())) {
3626 // TODO: We don't actually need to scan this object later, we just need to clear the gray
3627 // bit.
3628 // We don't need to mark newly allocated objects (those in allocation stack) as they can
3629 // only point to to-space objects. Also, they are considered live till the next GC cycle.
3630 PushOntoMarkStack(self, ref);
3631 }
3632 return ref;
3633 }
3634 }
3635 if (!is_los && mark_bitmap->Test(ref)) {
3636 // Already marked.
3637 } else if (is_los && los_bitmap->Test(ref)) {
3638 // Already marked in LOS.
3639 } else if (IsOnAllocStack(ref)) {
3640 // If it's on the allocation stack, it's considered marked. Keep it white (non-gray).
3641 // Objects on the allocation stack need not be marked.
3642 if (!is_los) {
3643 DCHECK(!mark_bitmap->Test(ref));
3644 } else {
3645 DCHECK(!los_bitmap->Test(ref));
3646 }
3647 if (kUseBakerReadBarrier) {
3648 DCHECK_EQ(ref->GetReadBarrierState(), ReadBarrier::NonGrayState());
3649 }
3650 } else {
3651 // Not marked nor on the allocation stack. Try to mark it.
3652 // This may or may not succeed, which is ok.
3653 bool success = false;
3654 if (kUseBakerReadBarrier) {
3655 success = ref->AtomicSetReadBarrierState(ReadBarrier::NonGrayState(),
3656 ReadBarrier::GrayState());
3657 } else {
3658 success = is_los ?
3659 !los_bitmap->AtomicTestAndSet(ref) :
3660 !mark_bitmap->AtomicTestAndSet(ref);
3661 }
3662 if (success) {
3663 if (kUseBakerReadBarrier) {
3664 DCHECK_EQ(ref->GetReadBarrierState(), ReadBarrier::GrayState());
3665 }
3666 PushOntoMarkStack(self, ref);
3667 }
3668 }
3669 return ref;
3670 }
3671
FinishPhase()3672 void ConcurrentCopying::FinishPhase() {
3673 Thread* const self = Thread::Current();
3674 {
3675 MutexLock mu(self, mark_stack_lock_);
3676 CHECK(revoked_mark_stacks_.empty());
3677 CHECK_EQ(pooled_mark_stacks_.size(), kMarkStackPoolSize);
3678 }
3679 bool should_eagerly_release_memory = ShouldEagerlyReleaseMemoryToOS();
3680 // kVerifyNoMissingCardMarks relies on the region space cards not being cleared to avoid false
3681 // positives.
3682 if (!kVerifyNoMissingCardMarks && !use_generational_cc_) {
3683 TimingLogger::ScopedTiming split("ClearRegionSpaceCards", GetTimings());
3684 // We do not currently use the region space cards at all, madvise them away to save ram.
3685 heap_->GetCardTable()->ClearCardRange(region_space_->Begin(), region_space_->Limit());
3686 } else if (use_generational_cc_ && !young_gen_) {
3687 region_space_inter_region_bitmap_.Clear(should_eagerly_release_memory);
3688 non_moving_space_inter_region_bitmap_.Clear(should_eagerly_release_memory);
3689 }
3690 {
3691 MutexLock mu(self, skipped_blocks_lock_);
3692 skipped_blocks_map_.clear();
3693 }
3694 {
3695 ReaderMutexLock mu(self, *Locks::mutator_lock_);
3696 {
3697 WriterMutexLock mu2(self, *Locks::heap_bitmap_lock_);
3698 heap_->ClearMarkedObjects(should_eagerly_release_memory);
3699 }
3700 if (kUseBakerReadBarrier && kFilterModUnionCards) {
3701 TimingLogger::ScopedTiming split("FilterModUnionCards", GetTimings());
3702 ReaderMutexLock mu2(self, *Locks::heap_bitmap_lock_);
3703 for (space::ContinuousSpace* space : immune_spaces_.GetSpaces()) {
3704 DCHECK(space->IsImageSpace() || space->IsZygoteSpace());
3705 accounting::ModUnionTable* table = heap_->FindModUnionTableFromSpace(space);
3706 // Filter out cards that don't need to be set.
3707 if (table != nullptr) {
3708 table->FilterCards();
3709 }
3710 }
3711 }
3712 if (kUseBakerReadBarrier) {
3713 TimingLogger::ScopedTiming split("EmptyRBMarkBitStack", GetTimings());
3714 DCHECK(rb_mark_bit_stack_ != nullptr);
3715 const auto* limit = rb_mark_bit_stack_->End();
3716 for (StackReference<mirror::Object>* it = rb_mark_bit_stack_->Begin(); it != limit; ++it) {
3717 CHECK(it->AsMirrorPtr()->AtomicSetMarkBit(1, 0))
3718 << "rb_mark_bit_stack_->Begin()" << rb_mark_bit_stack_->Begin() << '\n'
3719 << "rb_mark_bit_stack_->End()" << rb_mark_bit_stack_->End() << '\n'
3720 << "rb_mark_bit_stack_->IsFull()"
3721 << std::boolalpha << rb_mark_bit_stack_->IsFull() << std::noboolalpha << '\n'
3722 << DumpReferenceInfo(it->AsMirrorPtr(), "*it");
3723 }
3724 rb_mark_bit_stack_->Reset();
3725 }
3726 }
3727 if (measure_read_barrier_slow_path_) {
3728 MutexLock mu(self, rb_slow_path_histogram_lock_);
3729 rb_slow_path_time_histogram_.AdjustAndAddValue(
3730 rb_slow_path_ns_.load(std::memory_order_relaxed));
3731 rb_slow_path_count_total_ += rb_slow_path_count_.load(std::memory_order_relaxed);
3732 rb_slow_path_count_gc_total_ += rb_slow_path_count_gc_.load(std::memory_order_relaxed);
3733 }
3734 }
3735
IsNullOrMarkedHeapReference(mirror::HeapReference<mirror::Object> * field,bool do_atomic_update)3736 bool ConcurrentCopying::IsNullOrMarkedHeapReference(mirror::HeapReference<mirror::Object>* field,
3737 bool do_atomic_update) {
3738 mirror::Object* from_ref = field->AsMirrorPtr();
3739 if (from_ref == nullptr) {
3740 return true;
3741 }
3742 mirror::Object* to_ref = IsMarked(from_ref);
3743 if (to_ref == nullptr) {
3744 return false;
3745 }
3746 if (from_ref != to_ref) {
3747 if (do_atomic_update) {
3748 do {
3749 if (field->AsMirrorPtr() != from_ref) {
3750 // Concurrently overwritten by a mutator.
3751 break;
3752 }
3753 } while (!field->CasWeakRelaxed(from_ref, to_ref));
3754 // See comment in MarkHeapReference() for memory ordering.
3755 } else {
3756 field->Assign(to_ref);
3757 }
3758 }
3759 return true;
3760 }
3761
MarkObject(mirror::Object * from_ref)3762 mirror::Object* ConcurrentCopying::MarkObject(mirror::Object* from_ref) {
3763 return Mark(Thread::Current(), from_ref);
3764 }
3765
DelayReferenceReferent(ObjPtr<mirror::Class> klass,ObjPtr<mirror::Reference> reference)3766 void ConcurrentCopying::DelayReferenceReferent(ObjPtr<mirror::Class> klass,
3767 ObjPtr<mirror::Reference> reference) {
3768 heap_->GetReferenceProcessor()->DelayReferenceReferent(klass, reference, this);
3769 }
3770
ProcessReferences(Thread * self)3771 void ConcurrentCopying::ProcessReferences(Thread* self) {
3772 // We don't really need to lock the heap bitmap lock as we use CAS to mark in bitmaps.
3773 WriterMutexLock mu(self, *Locks::heap_bitmap_lock_);
3774 GetHeap()->GetReferenceProcessor()->ProcessReferences(self, GetTimings());
3775 }
3776
RevokeAllThreadLocalBuffers()3777 void ConcurrentCopying::RevokeAllThreadLocalBuffers() {
3778 TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
3779 region_space_->RevokeAllThreadLocalBuffers();
3780 }
3781
MarkFromReadBarrierWithMeasurements(Thread * const self,mirror::Object * from_ref)3782 mirror::Object* ConcurrentCopying::MarkFromReadBarrierWithMeasurements(Thread* const self,
3783 mirror::Object* from_ref) {
3784 if (self != thread_running_gc_) {
3785 rb_slow_path_count_.fetch_add(1u, std::memory_order_relaxed);
3786 } else {
3787 rb_slow_path_count_gc_.fetch_add(1u, std::memory_order_relaxed);
3788 }
3789 ScopedTrace tr(__FUNCTION__);
3790 const uint64_t start_time = measure_read_barrier_slow_path_ ? NanoTime() : 0u;
3791 mirror::Object* ret =
3792 Mark</*kGrayImmuneObject=*/true, /*kNoUnEvac=*/false, /*kFromGCThread=*/false>(self,
3793 from_ref);
3794 if (measure_read_barrier_slow_path_) {
3795 rb_slow_path_ns_.fetch_add(NanoTime() - start_time, std::memory_order_relaxed);
3796 }
3797 return ret;
3798 }
3799
DumpPerformanceInfo(std::ostream & os)3800 void ConcurrentCopying::DumpPerformanceInfo(std::ostream& os) {
3801 GarbageCollector::DumpPerformanceInfo(os);
3802 size_t num_gc_cycles = GetCumulativeTimings().GetIterations();
3803 MutexLock mu(Thread::Current(), rb_slow_path_histogram_lock_);
3804 if (rb_slow_path_time_histogram_.SampleSize() > 0) {
3805 Histogram<uint64_t>::CumulativeData cumulative_data;
3806 rb_slow_path_time_histogram_.CreateHistogram(&cumulative_data);
3807 rb_slow_path_time_histogram_.PrintConfidenceIntervals(os, 0.99, cumulative_data);
3808 }
3809 if (rb_slow_path_count_total_ > 0) {
3810 os << "Slow path count " << rb_slow_path_count_total_ << "\n";
3811 }
3812 if (rb_slow_path_count_gc_total_ > 0) {
3813 os << "GC slow path count " << rb_slow_path_count_gc_total_ << "\n";
3814 }
3815
3816 os << "Average " << (young_gen_ ? "minor" : "major") << " GC reclaim bytes ratio "
3817 << (reclaimed_bytes_ratio_sum_ / num_gc_cycles) << " over " << num_gc_cycles
3818 << " GC cycles\n";
3819
3820 os << "Average " << (young_gen_ ? "minor" : "major") << " GC copied live bytes ratio "
3821 << (copied_live_bytes_ratio_sum_ / gc_count_) << " over " << gc_count_
3822 << " " << (young_gen_ ? "minor" : "major") << " GCs\n";
3823
3824 os << "Cumulative bytes moved " << cumulative_bytes_moved_ << "\n";
3825
3826 os << "Peak regions allocated "
3827 << region_space_->GetMaxPeakNumNonFreeRegions() << " ("
3828 << PrettySize(region_space_->GetMaxPeakNumNonFreeRegions() * space::RegionSpace::kRegionSize)
3829 << ") / " << region_space_->GetNumRegions() / 2 << " ("
3830 << PrettySize(region_space_->GetNumRegions() * space::RegionSpace::kRegionSize / 2)
3831 << ")\n";
3832 if (!young_gen_) {
3833 os << "Total madvise time " << PrettyDuration(region_space_->GetMadviseTime()) << "\n";
3834 }
3835 }
3836
3837 } // namespace collector
3838 } // namespace gc
3839 } // namespace art
3840