mark_sweep.cc revision 3bb57c7b41bf5419fe895e7aa664d8d430205ba8
1/* 2 * Copyright (C) 2011 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 "mark_sweep.h" 18 19#include <functional> 20#include <numeric> 21#include <climits> 22#include <vector> 23 24#include "base/bounded_fifo.h" 25#include "base/logging.h" 26#include "base/macros.h" 27#include "base/mutex-inl.h" 28#include "base/timing_logger.h" 29#include "gc/accounting/card_table-inl.h" 30#include "gc/accounting/heap_bitmap.h" 31#include "gc/accounting/mod_union_table.h" 32#include "gc/accounting/space_bitmap-inl.h" 33#include "gc/heap.h" 34#include "gc/space/image_space.h" 35#include "gc/space/large_object_space.h" 36#include "gc/space/space-inl.h" 37#include "indirect_reference_table.h" 38#include "intern_table.h" 39#include "jni_internal.h" 40#include "monitor.h" 41#include "mark_sweep-inl.h" 42#include "mirror/art_field.h" 43#include "mirror/art_field-inl.h" 44#include "mirror/class-inl.h" 45#include "mirror/class_loader.h" 46#include "mirror/dex_cache.h" 47#include "mirror/object-inl.h" 48#include "mirror/object_array.h" 49#include "mirror/object_array-inl.h" 50#include "runtime.h" 51#include "thread-inl.h" 52#include "thread_list.h" 53#include "verifier/method_verifier.h" 54 55using ::art::mirror::ArtField; 56using ::art::mirror::Class; 57using ::art::mirror::Object; 58using ::art::mirror::ObjectArray; 59 60namespace art { 61namespace gc { 62namespace collector { 63 64// Performance options. 65constexpr bool kUseRecursiveMark = false; 66constexpr bool kUseMarkStackPrefetch = true; 67constexpr size_t kSweepArrayChunkFreeSize = 1024; 68 69// Parallelism options. 70constexpr bool kParallelCardScan = true; 71constexpr bool kParallelRecursiveMark = true; 72// Don't attempt to parallelize mark stack processing unless the mark stack is at least n 73// elements. This is temporary until we reduce the overhead caused by allocating tasks, etc.. Not 74// having this can add overhead in ProcessReferences since we may end up doing many calls of 75// ProcessMarkStack with very small mark stacks. 76constexpr size_t kMinimumParallelMarkStackSize = 128; 77constexpr bool kParallelProcessMarkStack = true; 78 79// Profiling and information flags. 80constexpr bool kCountClassesMarked = false; 81constexpr bool kProfileLargeObjects = false; 82constexpr bool kMeasureOverhead = false; 83constexpr bool kCountTasks = false; 84constexpr bool kCountJavaLangRefs = false; 85 86// Turn off kCheckLocks when profiling the GC since it slows the GC down by up to 40%. 87constexpr bool kCheckLocks = kDebugLocking; 88 89void MarkSweep::ImmuneSpace(space::ContinuousSpace* space) { 90 // Bind live to mark bitmap if necessary. 91 if (space->GetLiveBitmap() != space->GetMarkBitmap()) { 92 CHECK(space->IsContinuousMemMapAllocSpace()); 93 space->AsContinuousMemMapAllocSpace()->BindLiveToMarkBitmap(); 94 } 95 96 // Add the space to the immune region. 97 // TODO: Use space limits instead of current end_ since the end_ can be changed by dlmalloc 98 // callbacks. 99 if (immune_begin_ == NULL) { 100 DCHECK(immune_end_ == NULL); 101 SetImmuneRange(reinterpret_cast<Object*>(space->Begin()), 102 reinterpret_cast<Object*>(space->End())); 103 } else { 104 const space::ContinuousSpace* prev_space = nullptr; 105 // Find out if the previous space is immune. 106 for (const space::ContinuousSpace* cur_space : GetHeap()->GetContinuousSpaces()) { 107 if (cur_space == space) { 108 break; 109 } 110 prev_space = cur_space; 111 } 112 // If previous space was immune, then extend the immune region. Relies on continuous spaces 113 // being sorted by Heap::AddContinuousSpace. 114 if (prev_space != nullptr && IsImmuneSpace(prev_space)) { 115 immune_begin_ = std::min(reinterpret_cast<Object*>(space->Begin()), immune_begin_); 116 immune_end_ = std::max(reinterpret_cast<Object*>(space->End()), immune_end_); 117 } 118 } 119} 120 121bool MarkSweep::IsImmuneSpace(const space::ContinuousSpace* space) const { 122 return 123 immune_begin_ <= reinterpret_cast<Object*>(space->Begin()) && 124 immune_end_ >= reinterpret_cast<Object*>(space->End()); 125} 126 127void MarkSweep::BindBitmaps() { 128 timings_.StartSplit("BindBitmaps"); 129 WriterMutexLock mu(Thread::Current(), *Locks::heap_bitmap_lock_); 130 // Mark all of the spaces we never collect as immune. 131 for (const auto& space : GetHeap()->GetContinuousSpaces()) { 132 if (space->GetGcRetentionPolicy() == space::kGcRetentionPolicyNeverCollect) { 133 ImmuneSpace(space); 134 } 135 } 136 timings_.EndSplit(); 137} 138 139MarkSweep::MarkSweep(Heap* heap, bool is_concurrent, const std::string& name_prefix) 140 : GarbageCollector(heap, 141 name_prefix + 142 (is_concurrent ? "concurrent mark sweep": "mark sweep")), 143 current_mark_bitmap_(NULL), 144 mark_stack_(NULL), 145 immune_begin_(NULL), 146 immune_end_(NULL), 147 live_stack_freeze_size_(0), 148 gc_barrier_(new Barrier(0)), 149 large_object_lock_("mark sweep large object lock", kMarkSweepLargeObjectLock), 150 mark_stack_lock_("mark sweep mark stack lock", kMarkSweepMarkStackLock), 151 is_concurrent_(is_concurrent) { 152} 153 154void MarkSweep::InitializePhase() { 155 timings_.Reset(); 156 TimingLogger::ScopedSplit split("InitializePhase", &timings_); 157 mark_stack_ = heap_->mark_stack_.get(); 158 DCHECK(mark_stack_ != nullptr); 159 SetImmuneRange(nullptr, nullptr); 160 class_count_ = 0; 161 array_count_ = 0; 162 other_count_ = 0; 163 large_object_test_ = 0; 164 large_object_mark_ = 0; 165 classes_marked_ = 0; 166 overhead_time_ = 0; 167 work_chunks_created_ = 0; 168 work_chunks_deleted_ = 0; 169 reference_count_ = 0; 170 171 FindDefaultMarkBitmap(); 172 173 // Do any pre GC verification. 174 timings_.NewSplit("PreGcVerification"); 175 heap_->PreGcVerification(this); 176} 177 178void MarkSweep::ProcessReferences(Thread* self) { 179 TimingLogger::ScopedSplit split("ProcessReferences", &timings_); 180 WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); 181 GetHeap()->ProcessReferences(timings_, clear_soft_references_, &IsMarkedCallback, 182 &MarkObjectCallback, &ProcessMarkStackPausedCallback, this); 183} 184 185bool MarkSweep::HandleDirtyObjectsPhase() { 186 TimingLogger::ScopedSplit split("(Paused)HandleDirtyObjectsPhase", &timings_); 187 Thread* self = Thread::Current(); 188 Locks::mutator_lock_->AssertExclusiveHeld(self); 189 190 { 191 WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); 192 193 // Re-mark root set. 194 ReMarkRoots(); 195 196 // Scan dirty objects, this is only required if we are not doing concurrent GC. 197 RecursiveMarkDirtyObjects(true, accounting::CardTable::kCardDirty); 198 } 199 200 ProcessReferences(self); 201 202 // Only need to do this if we have the card mark verification on, and only during concurrent GC. 203 if (GetHeap()->verify_missing_card_marks_ || GetHeap()->verify_pre_gc_heap_|| 204 GetHeap()->verify_post_gc_heap_) { 205 WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); 206 // This second sweep makes sure that we don't have any objects in the live stack which point to 207 // freed objects. These cause problems since their references may be previously freed objects. 208 SweepArray(GetHeap()->allocation_stack_.get(), false); 209 // Since SweepArray() above resets the (active) allocation 210 // stack. Need to revoke the thread-local allocation stacks that 211 // point into it. 212 GetHeap()->RevokeAllThreadLocalAllocationStacks(self); 213 } 214 215 timings_.StartSplit("PreSweepingGcVerification"); 216 heap_->PreSweepingGcVerification(this); 217 timings_.EndSplit(); 218 219 // Ensure that nobody inserted items in the live stack after we swapped the stacks. 220 ReaderMutexLock mu(self, *Locks::heap_bitmap_lock_); 221 CHECK_GE(live_stack_freeze_size_, GetHeap()->GetLiveStack()->Size()); 222 223 // Disallow new system weaks to prevent a race which occurs when someone adds a new system 224 // weak before we sweep them. Since this new system weak may not be marked, the GC may 225 // incorrectly sweep it. This also fixes a race where interning may attempt to return a strong 226 // reference to a string that is about to be swept. 227 Runtime::Current()->DisallowNewSystemWeaks(); 228 return true; 229} 230 231bool MarkSweep::IsConcurrent() const { 232 return is_concurrent_; 233} 234 235void MarkSweep::MarkingPhase() { 236 TimingLogger::ScopedSplit split("MarkingPhase", &timings_); 237 Thread* self = Thread::Current(); 238 239 BindBitmaps(); 240 FindDefaultMarkBitmap(); 241 242 // Process dirty cards and add dirty cards to mod union tables. 243 heap_->ProcessCards(timings_); 244 245 // Need to do this before the checkpoint since we don't want any threads to add references to 246 // the live stack during the recursive mark. 247 timings_.NewSplit("SwapStacks"); 248 heap_->SwapStacks(self); 249 250 WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); 251 if (Locks::mutator_lock_->IsExclusiveHeld(self)) { 252 // If we exclusively hold the mutator lock, all threads must be suspended. 253 MarkRoots(); 254 if (kUseThreadLocalAllocationStack) { 255 heap_->RevokeAllThreadLocalAllocationStacks(self); 256 } 257 } else { 258 MarkThreadRoots(self); 259 // At this point the live stack should no longer have any mutators which push into it. 260 MarkNonThreadRoots(); 261 } 262 live_stack_freeze_size_ = heap_->GetLiveStack()->Size(); 263 MarkConcurrentRoots(); 264 UpdateAndMarkModUnion(); 265 MarkReachableObjects(); 266} 267 268void MarkSweep::UpdateAndMarkModUnion() { 269 for (const auto& space : heap_->GetContinuousSpaces()) { 270 if (IsImmuneSpace(space)) { 271 const char* name = space->IsZygoteSpace() ? "UpdateAndMarkZygoteModUnionTable" : 272 "UpdateAndMarkImageModUnionTable"; 273 TimingLogger::ScopedSplit split(name, &timings_); 274 accounting::ModUnionTable* mod_union_table = heap_->FindModUnionTableFromSpace(space); 275 CHECK(mod_union_table != nullptr); 276 mod_union_table->UpdateAndMarkReferences(MarkObjectCallback, this); 277 } 278 } 279} 280 281void MarkSweep::MarkThreadRoots(Thread* self) { 282 MarkRootsCheckpoint(self); 283} 284 285void MarkSweep::MarkReachableObjects() { 286 // Mark everything allocated since the last as GC live so that we can sweep concurrently, 287 // knowing that new allocations won't be marked as live. 288 timings_.StartSplit("MarkStackAsLive"); 289 accounting::ObjectStack* live_stack = heap_->GetLiveStack(); 290 heap_->MarkAllocStackAsLive(live_stack); 291 live_stack->Reset(); 292 timings_.EndSplit(); 293 // Recursively mark all the non-image bits set in the mark bitmap. 294 RecursiveMark(); 295} 296 297void MarkSweep::ReclaimPhase() { 298 TimingLogger::ScopedSplit split("ReclaimPhase", &timings_); 299 Thread* self = Thread::Current(); 300 301 if (!IsConcurrent()) { 302 ProcessReferences(self); 303 } 304 305 { 306 WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); 307 SweepSystemWeaks(); 308 } 309 310 if (IsConcurrent()) { 311 Runtime::Current()->AllowNewSystemWeaks(); 312 313 TimingLogger::ScopedSplit split("UnMarkAllocStack", &timings_); 314 WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); 315 accounting::ObjectStack* allocation_stack = GetHeap()->allocation_stack_.get(); 316 // The allocation stack contains things allocated since the start of the GC. These may have been 317 // marked during this GC meaning they won't be eligible for reclaiming in the next sticky GC. 318 // Remove these objects from the mark bitmaps so that they will be eligible for sticky 319 // collection. 320 // There is a race here which is safely handled. Another thread such as the hprof could 321 // have flushed the alloc stack after we resumed the threads. This is safe however, since 322 // reseting the allocation stack zeros it out with madvise. This means that we will either 323 // read NULLs or attempt to unmark a newly allocated object which will not be marked in the 324 // first place. 325 mirror::Object** end = allocation_stack->End(); 326 for (mirror::Object** it = allocation_stack->Begin(); it != end; ++it) { 327 const Object* obj = *it; 328 if (obj != NULL) { 329 UnMarkObjectNonNull(obj); 330 } 331 } 332 } 333 334 { 335 WriterMutexLock mu(self, *Locks::heap_bitmap_lock_); 336 337 // Reclaim unmarked objects. 338 Sweep(false); 339 340 // Swap the live and mark bitmaps for each space which we modified space. This is an 341 // optimization that enables us to not clear live bits inside of the sweep. Only swaps unbound 342 // bitmaps. 343 timings_.StartSplit("SwapBitmaps"); 344 SwapBitmaps(); 345 timings_.EndSplit(); 346 347 // Unbind the live and mark bitmaps. 348 TimingLogger::ScopedSplit split("UnBindBitmaps", &timings_); 349 GetHeap()->UnBindBitmaps(); 350 } 351} 352 353void MarkSweep::SetImmuneRange(Object* begin, Object* end) { 354 immune_begin_ = begin; 355 immune_end_ = end; 356} 357 358void MarkSweep::FindDefaultMarkBitmap() { 359 TimingLogger::ScopedSplit split("FindDefaultMarkBitmap", &timings_); 360 for (const auto& space : GetHeap()->GetContinuousSpaces()) { 361 accounting::SpaceBitmap* bitmap = space->GetMarkBitmap(); 362 if (bitmap != nullptr && 363 space->GetGcRetentionPolicy() == space::kGcRetentionPolicyAlwaysCollect) { 364 current_mark_bitmap_ = bitmap; 365 CHECK(current_mark_bitmap_ != NULL); 366 return; 367 } 368 } 369 GetHeap()->DumpSpaces(); 370 LOG(FATAL) << "Could not find a default mark bitmap"; 371} 372 373void MarkSweep::ExpandMarkStack() { 374 ResizeMarkStack(mark_stack_->Capacity() * 2); 375} 376 377void MarkSweep::ResizeMarkStack(size_t new_size) { 378 // Rare case, no need to have Thread::Current be a parameter. 379 if (UNLIKELY(mark_stack_->Size() < mark_stack_->Capacity())) { 380 // Someone else acquired the lock and expanded the mark stack before us. 381 return; 382 } 383 std::vector<Object*> temp(mark_stack_->Begin(), mark_stack_->End()); 384 CHECK_LE(mark_stack_->Size(), new_size); 385 mark_stack_->Resize(new_size); 386 for (const auto& obj : temp) { 387 mark_stack_->PushBack(obj); 388 } 389} 390 391inline void MarkSweep::MarkObjectNonNullParallel(const Object* obj) { 392 DCHECK(obj != NULL); 393 if (MarkObjectParallel(obj)) { 394 MutexLock mu(Thread::Current(), mark_stack_lock_); 395 if (UNLIKELY(mark_stack_->Size() >= mark_stack_->Capacity())) { 396 ExpandMarkStack(); 397 } 398 // The object must be pushed on to the mark stack. 399 mark_stack_->PushBack(const_cast<Object*>(obj)); 400 } 401} 402 403mirror::Object* MarkSweep::MarkObjectCallback(mirror::Object* obj, void* arg) { 404 MarkSweep* mark_sweep = reinterpret_cast<MarkSweep*>(arg); 405 mark_sweep->MarkObject(obj); 406 return obj; 407} 408 409inline void MarkSweep::UnMarkObjectNonNull(const Object* obj) { 410 DCHECK(!IsImmune(obj)); 411 // Try to take advantage of locality of references within a space, failing this find the space 412 // the hard way. 413 accounting::SpaceBitmap* object_bitmap = current_mark_bitmap_; 414 if (UNLIKELY(!object_bitmap->HasAddress(obj))) { 415 accounting::SpaceBitmap* new_bitmap = heap_->GetMarkBitmap()->GetContinuousSpaceBitmap(obj); 416 if (LIKELY(new_bitmap != NULL)) { 417 object_bitmap = new_bitmap; 418 } else { 419 MarkLargeObject(obj, false); 420 return; 421 } 422 } 423 424 DCHECK(object_bitmap->HasAddress(obj)); 425 object_bitmap->Clear(obj); 426} 427 428inline void MarkSweep::MarkObjectNonNull(const Object* obj) { 429 DCHECK(obj != NULL); 430 431 if (IsImmune(obj)) { 432 DCHECK(IsMarked(obj)); 433 return; 434 } 435 436 // Try to take advantage of locality of references within a space, failing this find the space 437 // the hard way. 438 accounting::SpaceBitmap* object_bitmap = current_mark_bitmap_; 439 if (UNLIKELY(!object_bitmap->HasAddress(obj))) { 440 accounting::SpaceBitmap* new_bitmap = heap_->GetMarkBitmap()->GetContinuousSpaceBitmap(obj); 441 if (LIKELY(new_bitmap != NULL)) { 442 object_bitmap = new_bitmap; 443 } else { 444 MarkLargeObject(obj, true); 445 return; 446 } 447 } 448 449 // This object was not previously marked. 450 if (!object_bitmap->Test(obj)) { 451 object_bitmap->Set(obj); 452 if (UNLIKELY(mark_stack_->Size() >= mark_stack_->Capacity())) { 453 // Lock is not needed but is here anyways to please annotalysis. 454 MutexLock mu(Thread::Current(), mark_stack_lock_); 455 ExpandMarkStack(); 456 } 457 // The object must be pushed on to the mark stack. 458 mark_stack_->PushBack(const_cast<Object*>(obj)); 459 } 460} 461 462// Rare case, probably not worth inlining since it will increase instruction cache miss rate. 463bool MarkSweep::MarkLargeObject(const Object* obj, bool set) { 464 // TODO: support >1 discontinuous space. 465 space::LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace(); 466 accounting::ObjectSet* large_objects = large_object_space->GetMarkObjects(); 467 if (kProfileLargeObjects) { 468 ++large_object_test_; 469 } 470 if (UNLIKELY(!large_objects->Test(obj))) { 471 if (!large_object_space->Contains(obj)) { 472 LOG(ERROR) << "Tried to mark " << obj << " not contained by any spaces"; 473 LOG(ERROR) << "Attempting see if it's a bad root"; 474 VerifyRoots(); 475 LOG(FATAL) << "Can't mark bad root"; 476 } 477 if (kProfileLargeObjects) { 478 ++large_object_mark_; 479 } 480 if (set) { 481 large_objects->Set(obj); 482 } else { 483 large_objects->Clear(obj); 484 } 485 return true; 486 } 487 return false; 488} 489 490inline bool MarkSweep::MarkObjectParallel(const Object* obj) { 491 DCHECK(obj != NULL); 492 493 if (IsImmune(obj)) { 494 DCHECK(IsMarked(obj)); 495 return false; 496 } 497 498 // Try to take advantage of locality of references within a space, failing this find the space 499 // the hard way. 500 accounting::SpaceBitmap* object_bitmap = current_mark_bitmap_; 501 if (UNLIKELY(!object_bitmap->HasAddress(obj))) { 502 accounting::SpaceBitmap* new_bitmap = heap_->GetMarkBitmap()->GetContinuousSpaceBitmap(obj); 503 if (new_bitmap != NULL) { 504 object_bitmap = new_bitmap; 505 } else { 506 // TODO: Remove the Thread::Current here? 507 // TODO: Convert this to some kind of atomic marking? 508 MutexLock mu(Thread::Current(), large_object_lock_); 509 return MarkLargeObject(obj, true); 510 } 511 } 512 513 // Return true if the object was not previously marked. 514 return !object_bitmap->AtomicTestAndSet(obj); 515} 516 517// Used to mark objects when recursing. Recursion is done by moving 518// the finger across the bitmaps in address order and marking child 519// objects. Any newly-marked objects whose addresses are lower than 520// the finger won't be visited by the bitmap scan, so those objects 521// need to be added to the mark stack. 522inline void MarkSweep::MarkObject(const Object* obj) { 523 if (obj != NULL) { 524 MarkObjectNonNull(obj); 525 } 526} 527 528void MarkSweep::MarkRoot(const Object* obj) { 529 if (obj != NULL) { 530 MarkObjectNonNull(obj); 531 } 532} 533 534void MarkSweep::MarkRootParallelCallback(mirror::Object** root, void* arg, uint32_t /*thread_id*/, 535 RootType /*root_type*/) { 536 DCHECK(root != NULL); 537 DCHECK(arg != NULL); 538 reinterpret_cast<MarkSweep*>(arg)->MarkObjectNonNullParallel(*root); 539} 540 541void MarkSweep::MarkRootCallback(Object** root, void* arg, uint32_t /*thread_id*/, 542 RootType /*root_type*/) { 543 DCHECK(root != nullptr); 544 DCHECK(arg != nullptr); 545 reinterpret_cast<MarkSweep*>(arg)->MarkObjectNonNull(*root); 546} 547 548void MarkSweep::VerifyRootCallback(const Object* root, void* arg, size_t vreg, 549 const StackVisitor* visitor) { 550 reinterpret_cast<MarkSweep*>(arg)->VerifyRoot(root, vreg, visitor); 551} 552 553void MarkSweep::VerifyRoot(const Object* root, size_t vreg, const StackVisitor* visitor) { 554 // See if the root is on any space bitmap. 555 if (GetHeap()->GetLiveBitmap()->GetContinuousSpaceBitmap(root) == NULL) { 556 space::LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace(); 557 if (!large_object_space->Contains(root)) { 558 LOG(ERROR) << "Found invalid root: " << root; 559 if (visitor != NULL) { 560 LOG(ERROR) << visitor->DescribeLocation() << " in VReg: " << vreg; 561 } 562 } 563 } 564} 565 566void MarkSweep::VerifyRoots() { 567 Runtime::Current()->GetThreadList()->VerifyRoots(VerifyRootCallback, this); 568} 569 570// Marks all objects in the root set. 571void MarkSweep::MarkRoots() { 572 timings_.StartSplit("MarkRoots"); 573 Runtime::Current()->VisitNonConcurrentRoots(MarkRootCallback, this); 574 timings_.EndSplit(); 575} 576 577void MarkSweep::MarkNonThreadRoots() { 578 timings_.StartSplit("MarkNonThreadRoots"); 579 Runtime::Current()->VisitNonThreadRoots(MarkRootCallback, this); 580 timings_.EndSplit(); 581} 582 583void MarkSweep::MarkConcurrentRoots() { 584 timings_.StartSplit("MarkConcurrentRoots"); 585 // Visit all runtime roots and clear dirty flags. 586 Runtime::Current()->VisitConcurrentRoots(MarkRootCallback, this, false, true); 587 timings_.EndSplit(); 588} 589 590class ScanObjectVisitor { 591 public: 592 explicit ScanObjectVisitor(MarkSweep* const mark_sweep) ALWAYS_INLINE 593 : mark_sweep_(mark_sweep) {} 594 595 // TODO: Fixme when anotatalysis works with visitors. 596 void operator()(Object* obj) const ALWAYS_INLINE NO_THREAD_SAFETY_ANALYSIS { 597 if (kCheckLocks) { 598 Locks::mutator_lock_->AssertSharedHeld(Thread::Current()); 599 Locks::heap_bitmap_lock_->AssertExclusiveHeld(Thread::Current()); 600 } 601 mark_sweep_->ScanObject(obj); 602 } 603 604 private: 605 MarkSweep* const mark_sweep_; 606}; 607 608template <bool kUseFinger = false> 609class MarkStackTask : public Task { 610 public: 611 MarkStackTask(ThreadPool* thread_pool, MarkSweep* mark_sweep, size_t mark_stack_size, 612 const Object** mark_stack) 613 : mark_sweep_(mark_sweep), 614 thread_pool_(thread_pool), 615 mark_stack_pos_(mark_stack_size) { 616 // We may have to copy part of an existing mark stack when another mark stack overflows. 617 if (mark_stack_size != 0) { 618 DCHECK(mark_stack != NULL); 619 // TODO: Check performance? 620 std::copy(mark_stack, mark_stack + mark_stack_size, mark_stack_); 621 } 622 if (kCountTasks) { 623 ++mark_sweep_->work_chunks_created_; 624 } 625 } 626 627 static const size_t kMaxSize = 1 * KB; 628 629 protected: 630 class ScanObjectParallelVisitor { 631 public: 632 explicit ScanObjectParallelVisitor(MarkStackTask<kUseFinger>* chunk_task) ALWAYS_INLINE 633 : chunk_task_(chunk_task) {} 634 635 void operator()(Object* obj) const { 636 MarkSweep* mark_sweep = chunk_task_->mark_sweep_; 637 mark_sweep->ScanObjectVisit(obj, 638 [mark_sweep, this](Object* /* obj */, Object* ref, const MemberOffset& /* offset */, 639 bool /* is_static */) ALWAYS_INLINE_LAMBDA { 640 if (ref != nullptr && mark_sweep->MarkObjectParallel(ref)) { 641 if (kUseFinger) { 642 android_memory_barrier(); 643 if (reinterpret_cast<uintptr_t>(ref) >= 644 static_cast<uintptr_t>(mark_sweep->atomic_finger_)) { 645 return; 646 } 647 } 648 chunk_task_->MarkStackPush(ref); 649 } 650 }); 651 } 652 653 private: 654 MarkStackTask<kUseFinger>* const chunk_task_; 655 }; 656 657 virtual ~MarkStackTask() { 658 // Make sure that we have cleared our mark stack. 659 DCHECK_EQ(mark_stack_pos_, 0U); 660 if (kCountTasks) { 661 ++mark_sweep_->work_chunks_deleted_; 662 } 663 } 664 665 MarkSweep* const mark_sweep_; 666 ThreadPool* const thread_pool_; 667 // Thread local mark stack for this task. 668 const Object* mark_stack_[kMaxSize]; 669 // Mark stack position. 670 size_t mark_stack_pos_; 671 672 void MarkStackPush(const Object* obj) ALWAYS_INLINE { 673 if (UNLIKELY(mark_stack_pos_ == kMaxSize)) { 674 // Mark stack overflow, give 1/2 the stack to the thread pool as a new work task. 675 mark_stack_pos_ /= 2; 676 auto* task = new MarkStackTask(thread_pool_, mark_sweep_, kMaxSize - mark_stack_pos_, 677 mark_stack_ + mark_stack_pos_); 678 thread_pool_->AddTask(Thread::Current(), task); 679 } 680 DCHECK(obj != nullptr); 681 DCHECK(mark_stack_pos_ < kMaxSize); 682 mark_stack_[mark_stack_pos_++] = obj; 683 } 684 685 virtual void Finalize() { 686 delete this; 687 } 688 689 // Scans all of the objects 690 virtual void Run(Thread* self) { 691 ScanObjectParallelVisitor visitor(this); 692 // TODO: Tune this. 693 static const size_t kFifoSize = 4; 694 BoundedFifoPowerOfTwo<const Object*, kFifoSize> prefetch_fifo; 695 for (;;) { 696 const Object* obj = nullptr; 697 if (kUseMarkStackPrefetch) { 698 while (mark_stack_pos_ != 0 && prefetch_fifo.size() < kFifoSize) { 699 const Object* obj = mark_stack_[--mark_stack_pos_]; 700 DCHECK(obj != nullptr); 701 __builtin_prefetch(obj); 702 prefetch_fifo.push_back(obj); 703 } 704 if (UNLIKELY(prefetch_fifo.empty())) { 705 break; 706 } 707 obj = prefetch_fifo.front(); 708 prefetch_fifo.pop_front(); 709 } else { 710 if (UNLIKELY(mark_stack_pos_ == 0)) { 711 break; 712 } 713 obj = mark_stack_[--mark_stack_pos_]; 714 } 715 DCHECK(obj != nullptr); 716 visitor(const_cast<mirror::Object*>(obj)); 717 } 718 } 719}; 720 721class CardScanTask : public MarkStackTask<false> { 722 public: 723 CardScanTask(ThreadPool* thread_pool, MarkSweep* mark_sweep, accounting::SpaceBitmap* bitmap, 724 byte* begin, byte* end, byte minimum_age, size_t mark_stack_size, 725 const Object** mark_stack_obj) 726 : MarkStackTask<false>(thread_pool, mark_sweep, mark_stack_size, mark_stack_obj), 727 bitmap_(bitmap), 728 begin_(begin), 729 end_(end), 730 minimum_age_(minimum_age) { 731 } 732 733 protected: 734 accounting::SpaceBitmap* const bitmap_; 735 byte* const begin_; 736 byte* const end_; 737 const byte minimum_age_; 738 739 virtual void Finalize() { 740 delete this; 741 } 742 743 virtual void Run(Thread* self) NO_THREAD_SAFETY_ANALYSIS { 744 ScanObjectParallelVisitor visitor(this); 745 accounting::CardTable* card_table = mark_sweep_->GetHeap()->GetCardTable(); 746 size_t cards_scanned = card_table->Scan(bitmap_, begin_, end_, visitor, minimum_age_); 747 VLOG(heap) << "Parallel scanning cards " << reinterpret_cast<void*>(begin_) << " - " 748 << reinterpret_cast<void*>(end_) << " = " << cards_scanned; 749 // Finish by emptying our local mark stack. 750 MarkStackTask::Run(self); 751 } 752}; 753 754size_t MarkSweep::GetThreadCount(bool paused) const { 755 if (heap_->GetThreadPool() == nullptr || !heap_->CareAboutPauseTimes()) { 756 return 0; 757 } 758 if (paused) { 759 return heap_->GetParallelGCThreadCount() + 1; 760 } else { 761 return heap_->GetConcGCThreadCount() + 1; 762 } 763} 764 765void MarkSweep::ScanGrayObjects(bool paused, byte minimum_age) { 766 accounting::CardTable* card_table = GetHeap()->GetCardTable(); 767 ThreadPool* thread_pool = GetHeap()->GetThreadPool(); 768 size_t thread_count = GetThreadCount(paused); 769 // The parallel version with only one thread is faster for card scanning, TODO: fix. 770 if (kParallelCardScan && thread_count > 0) { 771 Thread* self = Thread::Current(); 772 // Can't have a different split for each space since multiple spaces can have their cards being 773 // scanned at the same time. 774 timings_.StartSplit(paused ? "(Paused)ScanGrayObjects" : "ScanGrayObjects"); 775 // Try to take some of the mark stack since we can pass this off to the worker tasks. 776 const Object** mark_stack_begin = const_cast<const Object**>(mark_stack_->Begin()); 777 const Object** mark_stack_end = const_cast<const Object**>(mark_stack_->End()); 778 const size_t mark_stack_size = mark_stack_end - mark_stack_begin; 779 // Estimated number of work tasks we will create. 780 const size_t mark_stack_tasks = GetHeap()->GetContinuousSpaces().size() * thread_count; 781 DCHECK_NE(mark_stack_tasks, 0U); 782 const size_t mark_stack_delta = std::min(CardScanTask::kMaxSize / 2, 783 mark_stack_size / mark_stack_tasks + 1); 784 for (const auto& space : GetHeap()->GetContinuousSpaces()) { 785 if (space->GetMarkBitmap() == nullptr) { 786 continue; 787 } 788 byte* card_begin = space->Begin(); 789 byte* card_end = space->End(); 790 // Align up the end address. For example, the image space's end 791 // may not be card-size-aligned. 792 card_end = AlignUp(card_end, accounting::CardTable::kCardSize); 793 DCHECK(IsAligned<accounting::CardTable::kCardSize>(card_begin)); 794 DCHECK(IsAligned<accounting::CardTable::kCardSize>(card_end)); 795 // Calculate how many bytes of heap we will scan, 796 const size_t address_range = card_end - card_begin; 797 // Calculate how much address range each task gets. 798 const size_t card_delta = RoundUp(address_range / thread_count + 1, 799 accounting::CardTable::kCardSize); 800 // Create the worker tasks for this space. 801 while (card_begin != card_end) { 802 // Add a range of cards. 803 size_t addr_remaining = card_end - card_begin; 804 size_t card_increment = std::min(card_delta, addr_remaining); 805 // Take from the back of the mark stack. 806 size_t mark_stack_remaining = mark_stack_end - mark_stack_begin; 807 size_t mark_stack_increment = std::min(mark_stack_delta, mark_stack_remaining); 808 mark_stack_end -= mark_stack_increment; 809 mark_stack_->PopBackCount(static_cast<int32_t>(mark_stack_increment)); 810 DCHECK_EQ(mark_stack_end, mark_stack_->End()); 811 // Add the new task to the thread pool. 812 auto* task = new CardScanTask(thread_pool, this, space->GetMarkBitmap(), card_begin, 813 card_begin + card_increment, minimum_age, 814 mark_stack_increment, mark_stack_end); 815 thread_pool->AddTask(self, task); 816 card_begin += card_increment; 817 } 818 } 819 820 // Note: the card scan below may dirty new cards (and scan them) 821 // as a side effect when a Reference object is encountered and 822 // queued during the marking. See b/11465268. 823 thread_pool->SetMaxActiveWorkers(thread_count - 1); 824 thread_pool->StartWorkers(self); 825 thread_pool->Wait(self, true, true); 826 thread_pool->StopWorkers(self); 827 timings_.EndSplit(); 828 } else { 829 for (const auto& space : GetHeap()->GetContinuousSpaces()) { 830 if (space->GetMarkBitmap() != nullptr) { 831 // Image spaces are handled properly since live == marked for them. 832 switch (space->GetGcRetentionPolicy()) { 833 case space::kGcRetentionPolicyNeverCollect: 834 timings_.StartSplit(paused ? "(Paused)ScanGrayImageSpaceObjects" : 835 "ScanGrayImageSpaceObjects"); 836 break; 837 case space::kGcRetentionPolicyFullCollect: 838 timings_.StartSplit(paused ? "(Paused)ScanGrayZygoteSpaceObjects" : 839 "ScanGrayZygoteSpaceObjects"); 840 break; 841 case space::kGcRetentionPolicyAlwaysCollect: 842 timings_.StartSplit(paused ? "(Paused)ScanGrayAllocSpaceObjects" : 843 "ScanGrayAllocSpaceObjects"); 844 break; 845 } 846 ScanObjectVisitor visitor(this); 847 card_table->Scan(space->GetMarkBitmap(), space->Begin(), space->End(), visitor, minimum_age); 848 timings_.EndSplit(); 849 } 850 } 851 } 852} 853 854class RecursiveMarkTask : public MarkStackTask<false> { 855 public: 856 RecursiveMarkTask(ThreadPool* thread_pool, MarkSweep* mark_sweep, 857 accounting::SpaceBitmap* bitmap, uintptr_t begin, uintptr_t end) 858 : MarkStackTask<false>(thread_pool, mark_sweep, 0, NULL), 859 bitmap_(bitmap), 860 begin_(begin), 861 end_(end) { 862 } 863 864 protected: 865 accounting::SpaceBitmap* const bitmap_; 866 const uintptr_t begin_; 867 const uintptr_t end_; 868 869 virtual void Finalize() { 870 delete this; 871 } 872 873 // Scans all of the objects 874 virtual void Run(Thread* self) NO_THREAD_SAFETY_ANALYSIS { 875 ScanObjectParallelVisitor visitor(this); 876 bitmap_->VisitMarkedRange(begin_, end_, visitor); 877 // Finish by emptying our local mark stack. 878 MarkStackTask::Run(self); 879 } 880}; 881 882// Populates the mark stack based on the set of marked objects and 883// recursively marks until the mark stack is emptied. 884void MarkSweep::RecursiveMark() { 885 TimingLogger::ScopedSplit split("RecursiveMark", &timings_); 886 // RecursiveMark will build the lists of known instances of the Reference classes. See 887 // DelayReferenceReferent for details. 888 if (kUseRecursiveMark) { 889 const bool partial = GetGcType() == kGcTypePartial; 890 ScanObjectVisitor scan_visitor(this); 891 auto* self = Thread::Current(); 892 ThreadPool* thread_pool = heap_->GetThreadPool(); 893 size_t thread_count = GetThreadCount(false); 894 const bool parallel = kParallelRecursiveMark && thread_count > 1; 895 mark_stack_->Reset(); 896 for (const auto& space : GetHeap()->GetContinuousSpaces()) { 897 if ((space->GetGcRetentionPolicy() == space::kGcRetentionPolicyAlwaysCollect) || 898 (!partial && space->GetGcRetentionPolicy() == space::kGcRetentionPolicyFullCollect)) { 899 current_mark_bitmap_ = space->GetMarkBitmap(); 900 if (current_mark_bitmap_ == nullptr) { 901 continue; 902 } 903 if (parallel) { 904 // We will use the mark stack the future. 905 // CHECK(mark_stack_->IsEmpty()); 906 // This function does not handle heap end increasing, so we must use the space end. 907 uintptr_t begin = reinterpret_cast<uintptr_t>(space->Begin()); 908 uintptr_t end = reinterpret_cast<uintptr_t>(space->End()); 909 atomic_finger_ = static_cast<int32_t>(0xFFFFFFFF); 910 911 // Create a few worker tasks. 912 const size_t n = thread_count * 2; 913 while (begin != end) { 914 uintptr_t start = begin; 915 uintptr_t delta = (end - begin) / n; 916 delta = RoundUp(delta, KB); 917 if (delta < 16 * KB) delta = end - begin; 918 begin += delta; 919 auto* task = new RecursiveMarkTask(thread_pool, this, current_mark_bitmap_, start, 920 begin); 921 thread_pool->AddTask(self, task); 922 } 923 thread_pool->SetMaxActiveWorkers(thread_count - 1); 924 thread_pool->StartWorkers(self); 925 thread_pool->Wait(self, true, true); 926 thread_pool->StopWorkers(self); 927 } else { 928 // This function does not handle heap end increasing, so we must use the space end. 929 uintptr_t begin = reinterpret_cast<uintptr_t>(space->Begin()); 930 uintptr_t end = reinterpret_cast<uintptr_t>(space->End()); 931 current_mark_bitmap_->VisitMarkedRange(begin, end, scan_visitor); 932 } 933 } 934 } 935 } 936 ProcessMarkStack(false); 937} 938 939mirror::Object* MarkSweep::IsMarkedCallback(mirror::Object* object, void* arg) { 940 if (reinterpret_cast<MarkSweep*>(arg)->IsMarked(object)) { 941 return object; 942 } 943 return nullptr; 944} 945 946void MarkSweep::RecursiveMarkDirtyObjects(bool paused, byte minimum_age) { 947 ScanGrayObjects(paused, minimum_age); 948 ProcessMarkStack(paused); 949} 950 951void MarkSweep::ReMarkRoots() { 952 timings_.StartSplit("(Paused)ReMarkRoots"); 953 Runtime::Current()->VisitRoots(MarkRootCallback, this, true, true); 954 timings_.EndSplit(); 955} 956 957void MarkSweep::SweepSystemWeaks() { 958 Runtime* runtime = Runtime::Current(); 959 timings_.StartSplit("SweepSystemWeaks"); 960 runtime->SweepSystemWeaks(IsMarkedCallback, this); 961 timings_.EndSplit(); 962} 963 964mirror::Object* MarkSweep::VerifySystemWeakIsLiveCallback(Object* obj, void* arg) { 965 reinterpret_cast<MarkSweep*>(arg)->VerifyIsLive(obj); 966 // We don't actually want to sweep the object, so lets return "marked" 967 return obj; 968} 969 970void MarkSweep::VerifyIsLive(const Object* obj) { 971 Heap* heap = GetHeap(); 972 if (!heap->GetLiveBitmap()->Test(obj)) { 973 space::LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace(); 974 if (!large_object_space->GetLiveObjects()->Test(obj)) { 975 if (std::find(heap->allocation_stack_->Begin(), heap->allocation_stack_->End(), obj) == 976 heap->allocation_stack_->End()) { 977 // Object not found! 978 heap->DumpSpaces(); 979 LOG(FATAL) << "Found dead object " << obj; 980 } 981 } 982 } 983} 984 985void MarkSweep::VerifySystemWeaks() { 986 // Verify system weaks, uses a special object visitor which returns the input object. 987 Runtime::Current()->SweepSystemWeaks(VerifySystemWeakIsLiveCallback, this); 988} 989 990class CheckpointMarkThreadRoots : public Closure { 991 public: 992 explicit CheckpointMarkThreadRoots(MarkSweep* mark_sweep) : mark_sweep_(mark_sweep) {} 993 994 virtual void Run(Thread* thread) NO_THREAD_SAFETY_ANALYSIS { 995 ATRACE_BEGIN("Marking thread roots"); 996 // Note: self is not necessarily equal to thread since thread may be suspended. 997 Thread* self = Thread::Current(); 998 CHECK(thread == self || thread->IsSuspended() || thread->GetState() == kWaitingPerformingGc) 999 << thread->GetState() << " thread " << thread << " self " << self; 1000 thread->VisitRoots(MarkSweep::MarkRootParallelCallback, mark_sweep_); 1001 ATRACE_END(); 1002 if (kUseThreadLocalAllocationStack) { 1003 thread->RevokeThreadLocalAllocationStack(); 1004 } 1005 mark_sweep_->GetBarrier().Pass(self); 1006 } 1007 1008 private: 1009 MarkSweep* mark_sweep_; 1010}; 1011 1012void MarkSweep::MarkRootsCheckpoint(Thread* self) { 1013 CheckpointMarkThreadRoots check_point(this); 1014 timings_.StartSplit("MarkRootsCheckpoint"); 1015 ThreadList* thread_list = Runtime::Current()->GetThreadList(); 1016 // Request the check point is run on all threads returning a count of the threads that must 1017 // run through the barrier including self. 1018 size_t barrier_count = thread_list->RunCheckpoint(&check_point); 1019 // Release locks then wait for all mutator threads to pass the barrier. 1020 // TODO: optimize to not release locks when there are no threads to wait for. 1021 Locks::heap_bitmap_lock_->ExclusiveUnlock(self); 1022 Locks::mutator_lock_->SharedUnlock(self); 1023 ThreadState old_state = self->SetState(kWaitingForCheckPointsToRun); 1024 CHECK_EQ(old_state, kWaitingPerformingGc); 1025 gc_barrier_->Increment(self, barrier_count); 1026 self->SetState(kWaitingPerformingGc); 1027 Locks::mutator_lock_->SharedLock(self); 1028 Locks::heap_bitmap_lock_->ExclusiveLock(self); 1029 timings_.EndSplit(); 1030} 1031 1032void MarkSweep::SweepArray(accounting::ObjectStack* allocations, bool swap_bitmaps) { 1033 timings_.StartSplit("SweepArray"); 1034 Thread* self = Thread::Current(); 1035 mirror::Object* chunk_free_buffer[kSweepArrayChunkFreeSize]; 1036 size_t chunk_free_pos = 0; 1037 size_t freed_bytes = 0; 1038 size_t freed_large_object_bytes = 0; 1039 size_t freed_objects = 0; 1040 size_t freed_large_objects = 0; 1041 // How many objects are left in the array, modified after each space is swept. 1042 Object** objects = const_cast<Object**>(allocations->Begin()); 1043 size_t count = allocations->Size(); 1044 // Change the order to ensure that the non-moving space last swept as an optimization. 1045 std::vector<space::ContinuousSpace*> sweep_spaces; 1046 space::ContinuousSpace* non_moving_space = nullptr; 1047 for (space::ContinuousSpace* space : heap_->GetContinuousSpaces()) { 1048 if (space->IsAllocSpace() && !IsImmuneSpace(space) && space->GetLiveBitmap() != nullptr) { 1049 if (space == heap_->GetNonMovingSpace()) { 1050 non_moving_space = space; 1051 } else { 1052 sweep_spaces.push_back(space); 1053 } 1054 } 1055 } 1056 // Unlikely to sweep a significant amount of non_movable objects, so we do these after the after 1057 // the other alloc spaces as an optimization. 1058 if (non_moving_space != nullptr) { 1059 sweep_spaces.push_back(non_moving_space); 1060 } 1061 // Start by sweeping the continuous spaces. 1062 for (space::ContinuousSpace* space : sweep_spaces) { 1063 space::AllocSpace* alloc_space = space->AsAllocSpace(); 1064 accounting::SpaceBitmap* live_bitmap = space->GetLiveBitmap(); 1065 accounting::SpaceBitmap* mark_bitmap = space->GetMarkBitmap(); 1066 if (swap_bitmaps) { 1067 std::swap(live_bitmap, mark_bitmap); 1068 } 1069 Object** out = objects; 1070 for (size_t i = 0; i < count; ++i) { 1071 Object* obj = objects[i]; 1072 if (kUseThreadLocalAllocationStack && obj == nullptr) { 1073 continue; 1074 } 1075 if (space->HasAddress(obj)) { 1076 // This object is in the space, remove it from the array and add it to the sweep buffer 1077 // if needed. 1078 if (!mark_bitmap->Test(obj)) { 1079 if (chunk_free_pos >= kSweepArrayChunkFreeSize) { 1080 timings_.StartSplit("FreeList"); 1081 freed_objects += chunk_free_pos; 1082 freed_bytes += alloc_space->FreeList(self, chunk_free_pos, chunk_free_buffer); 1083 timings_.EndSplit(); 1084 chunk_free_pos = 0; 1085 } 1086 chunk_free_buffer[chunk_free_pos++] = obj; 1087 } 1088 } else { 1089 *(out++) = obj; 1090 } 1091 } 1092 if (chunk_free_pos > 0) { 1093 timings_.StartSplit("FreeList"); 1094 freed_objects += chunk_free_pos; 1095 freed_bytes += alloc_space->FreeList(self, chunk_free_pos, chunk_free_buffer); 1096 timings_.EndSplit(); 1097 chunk_free_pos = 0; 1098 } 1099 // All of the references which space contained are no longer in the allocation stack, update 1100 // the count. 1101 count = out - objects; 1102 } 1103 // Handle the large object space. 1104 space::LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace(); 1105 accounting::ObjectSet* large_live_objects = large_object_space->GetLiveObjects(); 1106 accounting::ObjectSet* large_mark_objects = large_object_space->GetMarkObjects(); 1107 if (swap_bitmaps) { 1108 std::swap(large_live_objects, large_mark_objects); 1109 } 1110 for (size_t i = 0; i < count; ++i) { 1111 Object* obj = objects[i]; 1112 // Handle large objects. 1113 if (kUseThreadLocalAllocationStack && obj == nullptr) { 1114 continue; 1115 } 1116 if (!large_mark_objects->Test(obj)) { 1117 ++freed_large_objects; 1118 freed_large_object_bytes += large_object_space->Free(self, obj); 1119 } 1120 } 1121 timings_.EndSplit(); 1122 1123 timings_.StartSplit("RecordFree"); 1124 VLOG(heap) << "Freed " << freed_objects << "/" << count 1125 << " objects with size " << PrettySize(freed_bytes); 1126 heap_->RecordFree(freed_objects + freed_large_objects, freed_bytes + freed_large_object_bytes); 1127 freed_objects_.FetchAndAdd(freed_objects); 1128 freed_large_objects_.FetchAndAdd(freed_large_objects); 1129 freed_bytes_.FetchAndAdd(freed_bytes); 1130 freed_large_object_bytes_.FetchAndAdd(freed_large_object_bytes); 1131 timings_.EndSplit(); 1132 1133 timings_.StartSplit("ResetStack"); 1134 allocations->Reset(); 1135 timings_.EndSplit(); 1136} 1137 1138void MarkSweep::Sweep(bool swap_bitmaps) { 1139 DCHECK(mark_stack_->IsEmpty()); 1140 TimingLogger::ScopedSplit("Sweep", &timings_); 1141 for (const auto& space : GetHeap()->GetContinuousSpaces()) { 1142 if (space->IsContinuousMemMapAllocSpace()) { 1143 space::ContinuousMemMapAllocSpace* alloc_space = space->AsContinuousMemMapAllocSpace(); 1144 TimingLogger::ScopedSplit split( 1145 alloc_space->IsZygoteSpace() ? "SweepZygoteSpace" : "SweepMallocSpace", &timings_); 1146 size_t freed_objects = 0; 1147 size_t freed_bytes = 0; 1148 alloc_space->Sweep(swap_bitmaps, &freed_objects, &freed_bytes); 1149 heap_->RecordFree(freed_objects, freed_bytes); 1150 freed_objects_.FetchAndAdd(freed_objects); 1151 freed_bytes_.FetchAndAdd(freed_bytes); 1152 } 1153 } 1154 SweepLargeObjects(swap_bitmaps); 1155} 1156 1157void MarkSweep::SweepLargeObjects(bool swap_bitmaps) { 1158 TimingLogger::ScopedSplit("SweepLargeObjects", &timings_); 1159 size_t freed_objects = 0; 1160 size_t freed_bytes = 0; 1161 GetHeap()->GetLargeObjectsSpace()->Sweep(swap_bitmaps, &freed_objects, &freed_bytes); 1162 freed_large_objects_.FetchAndAdd(freed_objects); 1163 freed_large_object_bytes_.FetchAndAdd(freed_bytes); 1164 GetHeap()->RecordFree(freed_objects, freed_bytes); 1165} 1166 1167// Process the "referent" field in a java.lang.ref.Reference. If the 1168// referent has not yet been marked, put it on the appropriate list in 1169// the heap for later processing. 1170void MarkSweep::DelayReferenceReferent(mirror::Class* klass, Object* obj) { 1171 DCHECK(klass != nullptr); 1172 DCHECK(klass->IsReferenceClass()); 1173 DCHECK(obj != NULL); 1174 heap_->DelayReferenceReferent(klass, obj, IsMarkedCallback, this); 1175} 1176 1177class MarkObjectVisitor { 1178 public: 1179 explicit MarkObjectVisitor(MarkSweep* const mark_sweep) ALWAYS_INLINE : mark_sweep_(mark_sweep) {} 1180 1181 // TODO: Fixme when anotatalysis works with visitors. 1182 void operator()(const Object* /* obj */, const Object* ref, const MemberOffset& /* offset */, 1183 bool /* is_static */) const ALWAYS_INLINE 1184 NO_THREAD_SAFETY_ANALYSIS { 1185 if (kCheckLocks) { 1186 Locks::mutator_lock_->AssertSharedHeld(Thread::Current()); 1187 Locks::heap_bitmap_lock_->AssertExclusiveHeld(Thread::Current()); 1188 } 1189 mark_sweep_->MarkObject(ref); 1190 } 1191 1192 private: 1193 MarkSweep* const mark_sweep_; 1194}; 1195 1196// Scans an object reference. Determines the type of the reference 1197// and dispatches to a specialized scanning routine. 1198void MarkSweep::ScanObject(Object* obj) { 1199 MarkObjectVisitor visitor(this); 1200 ScanObjectVisit(obj, visitor); 1201} 1202 1203void MarkSweep::ProcessMarkStackPausedCallback(void* arg) { 1204 DCHECK(arg != nullptr); 1205 reinterpret_cast<MarkSweep*>(arg)->ProcessMarkStack(true); 1206} 1207 1208void MarkSweep::ProcessMarkStackParallel(size_t thread_count) { 1209 Thread* self = Thread::Current(); 1210 ThreadPool* thread_pool = GetHeap()->GetThreadPool(); 1211 const size_t chunk_size = std::min(mark_stack_->Size() / thread_count + 1, 1212 static_cast<size_t>(MarkStackTask<false>::kMaxSize)); 1213 CHECK_GT(chunk_size, 0U); 1214 // Split the current mark stack up into work tasks. 1215 for (mirror::Object **it = mark_stack_->Begin(), **end = mark_stack_->End(); it < end; ) { 1216 const size_t delta = std::min(static_cast<size_t>(end - it), chunk_size); 1217 thread_pool->AddTask(self, new MarkStackTask<false>(thread_pool, this, delta, 1218 const_cast<const mirror::Object**>(it))); 1219 it += delta; 1220 } 1221 thread_pool->SetMaxActiveWorkers(thread_count - 1); 1222 thread_pool->StartWorkers(self); 1223 thread_pool->Wait(self, true, true); 1224 thread_pool->StopWorkers(self); 1225 mark_stack_->Reset(); 1226 CHECK_EQ(work_chunks_created_, work_chunks_deleted_) << " some of the work chunks were leaked"; 1227} 1228 1229// Scan anything that's on the mark stack. 1230void MarkSweep::ProcessMarkStack(bool paused) { 1231 timings_.StartSplit(paused ? "(Paused)ProcessMarkStack" : "ProcessMarkStack"); 1232 size_t thread_count = GetThreadCount(paused); 1233 if (kParallelProcessMarkStack && thread_count > 1 && 1234 mark_stack_->Size() >= kMinimumParallelMarkStackSize) { 1235 ProcessMarkStackParallel(thread_count); 1236 } else { 1237 // TODO: Tune this. 1238 static const size_t kFifoSize = 4; 1239 BoundedFifoPowerOfTwo<Object*, kFifoSize> prefetch_fifo; 1240 for (;;) { 1241 Object* obj = NULL; 1242 if (kUseMarkStackPrefetch) { 1243 while (!mark_stack_->IsEmpty() && prefetch_fifo.size() < kFifoSize) { 1244 Object* obj = mark_stack_->PopBack(); 1245 DCHECK(obj != NULL); 1246 __builtin_prefetch(obj); 1247 prefetch_fifo.push_back(obj); 1248 } 1249 if (prefetch_fifo.empty()) { 1250 break; 1251 } 1252 obj = prefetch_fifo.front(); 1253 prefetch_fifo.pop_front(); 1254 } else { 1255 if (mark_stack_->IsEmpty()) { 1256 break; 1257 } 1258 obj = mark_stack_->PopBack(); 1259 } 1260 DCHECK(obj != NULL); 1261 ScanObject(obj); 1262 } 1263 } 1264 timings_.EndSplit(); 1265} 1266 1267inline bool MarkSweep::IsMarked(const Object* object) const 1268 SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) { 1269 if (IsImmune(object)) { 1270 return true; 1271 } 1272 DCHECK(current_mark_bitmap_ != NULL); 1273 if (current_mark_bitmap_->HasAddress(object)) { 1274 return current_mark_bitmap_->Test(object); 1275 } 1276 return heap_->GetMarkBitmap()->Test(object); 1277} 1278 1279void MarkSweep::FinishPhase() { 1280 TimingLogger::ScopedSplit split("FinishPhase", &timings_); 1281 // Can't enqueue references if we hold the mutator lock. 1282 Heap* heap = GetHeap(); 1283 timings_.NewSplit("PostGcVerification"); 1284 heap->PostGcVerification(this); 1285 1286 timings_.NewSplit("RequestHeapTrim"); 1287 heap->RequestHeapTrim(); 1288 1289 // Update the cumulative statistics 1290 total_freed_objects_ += GetFreedObjects() + GetFreedLargeObjects(); 1291 total_freed_bytes_ += GetFreedBytes() + GetFreedLargeObjectBytes(); 1292 1293 // Ensure that the mark stack is empty. 1294 CHECK(mark_stack_->IsEmpty()); 1295 1296 if (kCountScannedTypes) { 1297 VLOG(gc) << "MarkSweep scanned classes=" << class_count_ << " arrays=" << array_count_ 1298 << " other=" << other_count_; 1299 } 1300 1301 if (kCountTasks) { 1302 VLOG(gc) << "Total number of work chunks allocated: " << work_chunks_created_; 1303 } 1304 1305 if (kMeasureOverhead) { 1306 VLOG(gc) << "Overhead time " << PrettyDuration(overhead_time_); 1307 } 1308 1309 if (kProfileLargeObjects) { 1310 VLOG(gc) << "Large objects tested " << large_object_test_ << " marked " << large_object_mark_; 1311 } 1312 1313 if (kCountClassesMarked) { 1314 VLOG(gc) << "Classes marked " << classes_marked_; 1315 } 1316 1317 if (kCountJavaLangRefs) { 1318 VLOG(gc) << "References scanned " << reference_count_; 1319 } 1320 1321 // Update the cumulative loggers. 1322 cumulative_timings_.Start(); 1323 cumulative_timings_.AddLogger(timings_); 1324 cumulative_timings_.End(); 1325 1326 // Clear all of the spaces' mark bitmaps. 1327 for (const auto& space : GetHeap()->GetContinuousSpaces()) { 1328 accounting::SpaceBitmap* bitmap = space->GetMarkBitmap(); 1329 if (bitmap != nullptr && 1330 space->GetGcRetentionPolicy() != space::kGcRetentionPolicyNeverCollect) { 1331 bitmap->Clear(); 1332 } 1333 } 1334 mark_stack_->Reset(); 1335 1336 // Reset the marked large objects. 1337 space::LargeObjectSpace* large_objects = GetHeap()->GetLargeObjectsSpace(); 1338 large_objects->GetMarkObjects()->Clear(); 1339} 1340 1341} // namespace collector 1342} // namespace gc 1343} // namespace art 1344