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