mark_sweep.cc revision a1602f28c0e3127ad511712d4b08db89737ae901
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 528Object* MarkSweep::MarkRootParallelCallback(Object* root, void* arg) { 529 DCHECK(root != NULL); 530 DCHECK(arg != NULL); 531 reinterpret_cast<MarkSweep*>(arg)->MarkObjectNonNullParallel(root); 532 return root; 533} 534 535Object* MarkSweep::MarkRootCallback(Object* root, void* arg) { 536 DCHECK(root != nullptr); 537 DCHECK(arg != nullptr); 538 reinterpret_cast<MarkSweep*>(arg)->MarkObjectNonNull(root); 539 return root; 540} 541 542void MarkSweep::VerifyRootCallback(const Object* root, void* arg, size_t vreg, 543 const StackVisitor* visitor) { 544 reinterpret_cast<MarkSweep*>(arg)->VerifyRoot(root, vreg, visitor); 545} 546 547void MarkSweep::VerifyRoot(const Object* root, size_t vreg, const StackVisitor* visitor) { 548 // See if the root is on any space bitmap. 549 if (GetHeap()->GetLiveBitmap()->GetContinuousSpaceBitmap(root) == NULL) { 550 space::LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace(); 551 if (!large_object_space->Contains(root)) { 552 LOG(ERROR) << "Found invalid root: " << root; 553 if (visitor != NULL) { 554 LOG(ERROR) << visitor->DescribeLocation() << " in VReg: " << vreg; 555 } 556 } 557 } 558} 559 560void MarkSweep::VerifyRoots() { 561 Runtime::Current()->GetThreadList()->VerifyRoots(VerifyRootCallback, this); 562} 563 564// Marks all objects in the root set. 565void MarkSweep::MarkRoots() { 566 timings_.StartSplit("MarkRoots"); 567 Runtime::Current()->VisitNonConcurrentRoots(MarkRootCallback, this); 568 timings_.EndSplit(); 569} 570 571void MarkSweep::MarkNonThreadRoots() { 572 timings_.StartSplit("MarkNonThreadRoots"); 573 Runtime::Current()->VisitNonThreadRoots(MarkRootCallback, this); 574 timings_.EndSplit(); 575} 576 577void MarkSweep::MarkConcurrentRoots() { 578 timings_.StartSplit("MarkConcurrentRoots"); 579 // Visit all runtime roots and clear dirty flags. 580 Runtime::Current()->VisitConcurrentRoots(MarkRootCallback, this, false, true); 581 timings_.EndSplit(); 582} 583 584class ScanObjectVisitor { 585 public: 586 explicit ScanObjectVisitor(MarkSweep* const mark_sweep) ALWAYS_INLINE 587 : mark_sweep_(mark_sweep) {} 588 589 // TODO: Fixme when anotatalysis works with visitors. 590 void operator()(Object* obj) const ALWAYS_INLINE NO_THREAD_SAFETY_ANALYSIS { 591 if (kCheckLocks) { 592 Locks::mutator_lock_->AssertSharedHeld(Thread::Current()); 593 Locks::heap_bitmap_lock_->AssertExclusiveHeld(Thread::Current()); 594 } 595 mark_sweep_->ScanObject(obj); 596 } 597 598 private: 599 MarkSweep* const mark_sweep_; 600}; 601 602template <bool kUseFinger = false> 603class MarkStackTask : public Task { 604 public: 605 MarkStackTask(ThreadPool* thread_pool, MarkSweep* mark_sweep, size_t mark_stack_size, 606 const Object** mark_stack) 607 : mark_sweep_(mark_sweep), 608 thread_pool_(thread_pool), 609 mark_stack_pos_(mark_stack_size) { 610 // We may have to copy part of an existing mark stack when another mark stack overflows. 611 if (mark_stack_size != 0) { 612 DCHECK(mark_stack != NULL); 613 // TODO: Check performance? 614 std::copy(mark_stack, mark_stack + mark_stack_size, mark_stack_); 615 } 616 if (kCountTasks) { 617 ++mark_sweep_->work_chunks_created_; 618 } 619 } 620 621 static const size_t kMaxSize = 1 * KB; 622 623 protected: 624 class ScanObjectParallelVisitor { 625 public: 626 explicit ScanObjectParallelVisitor(MarkStackTask<kUseFinger>* chunk_task) ALWAYS_INLINE 627 : chunk_task_(chunk_task) {} 628 629 void operator()(Object* obj) const { 630 MarkSweep* mark_sweep = chunk_task_->mark_sweep_; 631 mark_sweep->ScanObjectVisit(obj, 632 [mark_sweep, this](Object* /* obj */, Object* ref, const MemberOffset& /* offset */, 633 bool /* is_static */) ALWAYS_INLINE_LAMBDA { 634 if (ref != nullptr && mark_sweep->MarkObjectParallel(ref)) { 635 if (kUseFinger) { 636 android_memory_barrier(); 637 if (reinterpret_cast<uintptr_t>(ref) >= 638 static_cast<uintptr_t>(mark_sweep->atomic_finger_)) { 639 return; 640 } 641 } 642 chunk_task_->MarkStackPush(ref); 643 } 644 }); 645 } 646 647 private: 648 MarkStackTask<kUseFinger>* const chunk_task_; 649 }; 650 651 virtual ~MarkStackTask() { 652 // Make sure that we have cleared our mark stack. 653 DCHECK_EQ(mark_stack_pos_, 0U); 654 if (kCountTasks) { 655 ++mark_sweep_->work_chunks_deleted_; 656 } 657 } 658 659 MarkSweep* const mark_sweep_; 660 ThreadPool* const thread_pool_; 661 // Thread local mark stack for this task. 662 const Object* mark_stack_[kMaxSize]; 663 // Mark stack position. 664 size_t mark_stack_pos_; 665 666 void MarkStackPush(const Object* obj) ALWAYS_INLINE { 667 if (UNLIKELY(mark_stack_pos_ == kMaxSize)) { 668 // Mark stack overflow, give 1/2 the stack to the thread pool as a new work task. 669 mark_stack_pos_ /= 2; 670 auto* task = new MarkStackTask(thread_pool_, mark_sweep_, kMaxSize - mark_stack_pos_, 671 mark_stack_ + mark_stack_pos_); 672 thread_pool_->AddTask(Thread::Current(), task); 673 } 674 DCHECK(obj != nullptr); 675 DCHECK(mark_stack_pos_ < kMaxSize); 676 mark_stack_[mark_stack_pos_++] = obj; 677 } 678 679 virtual void Finalize() { 680 delete this; 681 } 682 683 // Scans all of the objects 684 virtual void Run(Thread* self) { 685 ScanObjectParallelVisitor visitor(this); 686 // TODO: Tune this. 687 static const size_t kFifoSize = 4; 688 BoundedFifoPowerOfTwo<const Object*, kFifoSize> prefetch_fifo; 689 for (;;) { 690 const Object* obj = nullptr; 691 if (kUseMarkStackPrefetch) { 692 while (mark_stack_pos_ != 0 && prefetch_fifo.size() < kFifoSize) { 693 const Object* obj = mark_stack_[--mark_stack_pos_]; 694 DCHECK(obj != nullptr); 695 __builtin_prefetch(obj); 696 prefetch_fifo.push_back(obj); 697 } 698 if (UNLIKELY(prefetch_fifo.empty())) { 699 break; 700 } 701 obj = prefetch_fifo.front(); 702 prefetch_fifo.pop_front(); 703 } else { 704 if (UNLIKELY(mark_stack_pos_ == 0)) { 705 break; 706 } 707 obj = mark_stack_[--mark_stack_pos_]; 708 } 709 DCHECK(obj != nullptr); 710 visitor(const_cast<mirror::Object*>(obj)); 711 } 712 } 713}; 714 715class CardScanTask : public MarkStackTask<false> { 716 public: 717 CardScanTask(ThreadPool* thread_pool, MarkSweep* mark_sweep, accounting::SpaceBitmap* bitmap, 718 byte* begin, byte* end, byte minimum_age, size_t mark_stack_size, 719 const Object** mark_stack_obj) 720 : MarkStackTask<false>(thread_pool, mark_sweep, mark_stack_size, mark_stack_obj), 721 bitmap_(bitmap), 722 begin_(begin), 723 end_(end), 724 minimum_age_(minimum_age) { 725 } 726 727 protected: 728 accounting::SpaceBitmap* const bitmap_; 729 byte* const begin_; 730 byte* const end_; 731 const byte minimum_age_; 732 733 virtual void Finalize() { 734 delete this; 735 } 736 737 virtual void Run(Thread* self) NO_THREAD_SAFETY_ANALYSIS { 738 ScanObjectParallelVisitor visitor(this); 739 accounting::CardTable* card_table = mark_sweep_->GetHeap()->GetCardTable(); 740 size_t cards_scanned = card_table->Scan(bitmap_, begin_, end_, visitor, minimum_age_); 741 VLOG(heap) << "Parallel scanning cards " << reinterpret_cast<void*>(begin_) << " - " 742 << reinterpret_cast<void*>(end_) << " = " << cards_scanned; 743 // Finish by emptying our local mark stack. 744 MarkStackTask::Run(self); 745 } 746}; 747 748size_t MarkSweep::GetThreadCount(bool paused) const { 749 if (heap_->GetThreadPool() == nullptr || !heap_->CareAboutPauseTimes()) { 750 return 0; 751 } 752 if (paused) { 753 return heap_->GetParallelGCThreadCount() + 1; 754 } else { 755 return heap_->GetConcGCThreadCount() + 1; 756 } 757} 758 759void MarkSweep::ScanGrayObjects(bool paused, byte minimum_age) { 760 accounting::CardTable* card_table = GetHeap()->GetCardTable(); 761 ThreadPool* thread_pool = GetHeap()->GetThreadPool(); 762 size_t thread_count = GetThreadCount(paused); 763 // The parallel version with only one thread is faster for card scanning, TODO: fix. 764 if (kParallelCardScan && thread_count > 0) { 765 Thread* self = Thread::Current(); 766 // Can't have a different split for each space since multiple spaces can have their cards being 767 // scanned at the same time. 768 timings_.StartSplit(paused ? "(Paused)ScanGrayObjects" : "ScanGrayObjects"); 769 // Try to take some of the mark stack since we can pass this off to the worker tasks. 770 const Object** mark_stack_begin = const_cast<const Object**>(mark_stack_->Begin()); 771 const Object** mark_stack_end = const_cast<const Object**>(mark_stack_->End()); 772 const size_t mark_stack_size = mark_stack_end - mark_stack_begin; 773 // Estimated number of work tasks we will create. 774 const size_t mark_stack_tasks = GetHeap()->GetContinuousSpaces().size() * thread_count; 775 DCHECK_NE(mark_stack_tasks, 0U); 776 const size_t mark_stack_delta = std::min(CardScanTask::kMaxSize / 2, 777 mark_stack_size / mark_stack_tasks + 1); 778 for (const auto& space : GetHeap()->GetContinuousSpaces()) { 779 if (space->GetMarkBitmap() == nullptr) { 780 continue; 781 } 782 byte* card_begin = space->Begin(); 783 byte* card_end = space->End(); 784 // Align up the end address. For example, the image space's end 785 // may not be card-size-aligned. 786 card_end = AlignUp(card_end, accounting::CardTable::kCardSize); 787 DCHECK(IsAligned<accounting::CardTable::kCardSize>(card_begin)); 788 DCHECK(IsAligned<accounting::CardTable::kCardSize>(card_end)); 789 // Calculate how many bytes of heap we will scan, 790 const size_t address_range = card_end - card_begin; 791 // Calculate how much address range each task gets. 792 const size_t card_delta = RoundUp(address_range / thread_count + 1, 793 accounting::CardTable::kCardSize); 794 // Create the worker tasks for this space. 795 while (card_begin != card_end) { 796 // Add a range of cards. 797 size_t addr_remaining = card_end - card_begin; 798 size_t card_increment = std::min(card_delta, addr_remaining); 799 // Take from the back of the mark stack. 800 size_t mark_stack_remaining = mark_stack_end - mark_stack_begin; 801 size_t mark_stack_increment = std::min(mark_stack_delta, mark_stack_remaining); 802 mark_stack_end -= mark_stack_increment; 803 mark_stack_->PopBackCount(static_cast<int32_t>(mark_stack_increment)); 804 DCHECK_EQ(mark_stack_end, mark_stack_->End()); 805 // Add the new task to the thread pool. 806 auto* task = new CardScanTask(thread_pool, this, space->GetMarkBitmap(), card_begin, 807 card_begin + card_increment, minimum_age, 808 mark_stack_increment, mark_stack_end); 809 thread_pool->AddTask(self, task); 810 card_begin += card_increment; 811 } 812 } 813 814 // Note: the card scan below may dirty new cards (and scan them) 815 // as a side effect when a Reference object is encountered and 816 // queued during the marking. See b/11465268. 817 thread_pool->SetMaxActiveWorkers(thread_count - 1); 818 thread_pool->StartWorkers(self); 819 thread_pool->Wait(self, true, true); 820 thread_pool->StopWorkers(self); 821 timings_.EndSplit(); 822 } else { 823 for (const auto& space : GetHeap()->GetContinuousSpaces()) { 824 if (space->GetMarkBitmap() != nullptr) { 825 // Image spaces are handled properly since live == marked for them. 826 switch (space->GetGcRetentionPolicy()) { 827 case space::kGcRetentionPolicyNeverCollect: 828 timings_.StartSplit(paused ? "(Paused)ScanGrayImageSpaceObjects" : 829 "ScanGrayImageSpaceObjects"); 830 break; 831 case space::kGcRetentionPolicyFullCollect: 832 timings_.StartSplit(paused ? "(Paused)ScanGrayZygoteSpaceObjects" : 833 "ScanGrayZygoteSpaceObjects"); 834 break; 835 case space::kGcRetentionPolicyAlwaysCollect: 836 timings_.StartSplit(paused ? "(Paused)ScanGrayAllocSpaceObjects" : 837 "ScanGrayAllocSpaceObjects"); 838 break; 839 } 840 ScanObjectVisitor visitor(this); 841 card_table->Scan(space->GetMarkBitmap(), space->Begin(), space->End(), visitor, minimum_age); 842 timings_.EndSplit(); 843 } 844 } 845 } 846} 847 848class RecursiveMarkTask : public MarkStackTask<false> { 849 public: 850 RecursiveMarkTask(ThreadPool* thread_pool, MarkSweep* mark_sweep, 851 accounting::SpaceBitmap* bitmap, uintptr_t begin, uintptr_t end) 852 : MarkStackTask<false>(thread_pool, mark_sweep, 0, NULL), 853 bitmap_(bitmap), 854 begin_(begin), 855 end_(end) { 856 } 857 858 protected: 859 accounting::SpaceBitmap* const bitmap_; 860 const uintptr_t begin_; 861 const uintptr_t end_; 862 863 virtual void Finalize() { 864 delete this; 865 } 866 867 // Scans all of the objects 868 virtual void Run(Thread* self) NO_THREAD_SAFETY_ANALYSIS { 869 ScanObjectParallelVisitor visitor(this); 870 bitmap_->VisitMarkedRange(begin_, end_, visitor); 871 // Finish by emptying our local mark stack. 872 MarkStackTask::Run(self); 873 } 874}; 875 876// Populates the mark stack based on the set of marked objects and 877// recursively marks until the mark stack is emptied. 878void MarkSweep::RecursiveMark() { 879 TimingLogger::ScopedSplit split("RecursiveMark", &timings_); 880 // RecursiveMark will build the lists of known instances of the Reference classes. See 881 // DelayReferenceReferent for details. 882 if (kUseRecursiveMark) { 883 const bool partial = GetGcType() == kGcTypePartial; 884 ScanObjectVisitor scan_visitor(this); 885 auto* self = Thread::Current(); 886 ThreadPool* thread_pool = heap_->GetThreadPool(); 887 size_t thread_count = GetThreadCount(false); 888 const bool parallel = kParallelRecursiveMark && thread_count > 1; 889 mark_stack_->Reset(); 890 for (const auto& space : GetHeap()->GetContinuousSpaces()) { 891 if ((space->GetGcRetentionPolicy() == space::kGcRetentionPolicyAlwaysCollect) || 892 (!partial && space->GetGcRetentionPolicy() == space::kGcRetentionPolicyFullCollect)) { 893 current_mark_bitmap_ = space->GetMarkBitmap(); 894 if (current_mark_bitmap_ == nullptr) { 895 continue; 896 } 897 if (parallel) { 898 // We will use the mark stack the future. 899 // CHECK(mark_stack_->IsEmpty()); 900 // This function does not handle heap end increasing, so we must use the space end. 901 uintptr_t begin = reinterpret_cast<uintptr_t>(space->Begin()); 902 uintptr_t end = reinterpret_cast<uintptr_t>(space->End()); 903 atomic_finger_ = static_cast<int32_t>(0xFFFFFFFF); 904 905 // Create a few worker tasks. 906 const size_t n = thread_count * 2; 907 while (begin != end) { 908 uintptr_t start = begin; 909 uintptr_t delta = (end - begin) / n; 910 delta = RoundUp(delta, KB); 911 if (delta < 16 * KB) delta = end - begin; 912 begin += delta; 913 auto* task = new RecursiveMarkTask(thread_pool, this, current_mark_bitmap_, start, 914 begin); 915 thread_pool->AddTask(self, task); 916 } 917 thread_pool->SetMaxActiveWorkers(thread_count - 1); 918 thread_pool->StartWorkers(self); 919 thread_pool->Wait(self, true, true); 920 thread_pool->StopWorkers(self); 921 } else { 922 // This function does not handle heap end increasing, so we must use the space end. 923 uintptr_t begin = reinterpret_cast<uintptr_t>(space->Begin()); 924 uintptr_t end = reinterpret_cast<uintptr_t>(space->End()); 925 current_mark_bitmap_->VisitMarkedRange(begin, end, scan_visitor); 926 } 927 } 928 } 929 } 930 ProcessMarkStack(false); 931} 932 933mirror::Object* MarkSweep::IsMarkedCallback(Object* object, void* arg) { 934 if (reinterpret_cast<MarkSweep*>(arg)->IsMarked(object)) { 935 return object; 936 } 937 return nullptr; 938} 939 940void MarkSweep::RecursiveMarkDirtyObjects(bool paused, byte minimum_age) { 941 ScanGrayObjects(paused, minimum_age); 942 ProcessMarkStack(paused); 943} 944 945void MarkSweep::ReMarkRoots() { 946 timings_.StartSplit("ReMarkRoots"); 947 Runtime::Current()->VisitRoots(MarkRootCallback, this, true, true); 948 timings_.EndSplit(); 949} 950 951void MarkSweep::SweepSystemWeaks() { 952 Runtime* runtime = Runtime::Current(); 953 timings_.StartSplit("SweepSystemWeaks"); 954 runtime->SweepSystemWeaks(IsMarkedCallback, this); 955 timings_.EndSplit(); 956} 957 958mirror::Object* MarkSweep::VerifySystemWeakIsLiveCallback(Object* obj, void* arg) { 959 reinterpret_cast<MarkSweep*>(arg)->VerifyIsLive(obj); 960 // We don't actually want to sweep the object, so lets return "marked" 961 return obj; 962} 963 964void MarkSweep::VerifyIsLive(const Object* obj) { 965 Heap* heap = GetHeap(); 966 if (!heap->GetLiveBitmap()->Test(obj)) { 967 space::LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace(); 968 if (!large_object_space->GetLiveObjects()->Test(obj)) { 969 if (std::find(heap->allocation_stack_->Begin(), heap->allocation_stack_->End(), obj) == 970 heap->allocation_stack_->End()) { 971 // Object not found! 972 heap->DumpSpaces(); 973 LOG(FATAL) << "Found dead object " << obj; 974 } 975 } 976 } 977} 978 979void MarkSweep::VerifySystemWeaks() { 980 // Verify system weaks, uses a special object visitor which returns the input object. 981 Runtime::Current()->SweepSystemWeaks(VerifySystemWeakIsLiveCallback, this); 982} 983 984class CheckpointMarkThreadRoots : public Closure { 985 public: 986 explicit CheckpointMarkThreadRoots(MarkSweep* mark_sweep) : mark_sweep_(mark_sweep) {} 987 988 virtual void Run(Thread* thread) NO_THREAD_SAFETY_ANALYSIS { 989 ATRACE_BEGIN("Marking thread roots"); 990 // Note: self is not necessarily equal to thread since thread may be suspended. 991 Thread* self = Thread::Current(); 992 CHECK(thread == self || thread->IsSuspended() || thread->GetState() == kWaitingPerformingGc) 993 << thread->GetState() << " thread " << thread << " self " << self; 994 thread->VisitRoots(MarkSweep::MarkRootParallelCallback, mark_sweep_); 995 ATRACE_END(); 996 mark_sweep_->GetBarrier().Pass(self); 997 } 998 999 private: 1000 MarkSweep* mark_sweep_; 1001}; 1002 1003void MarkSweep::MarkRootsCheckpoint(Thread* self) { 1004 CheckpointMarkThreadRoots check_point(this); 1005 timings_.StartSplit("MarkRootsCheckpoint"); 1006 ThreadList* thread_list = Runtime::Current()->GetThreadList(); 1007 // Request the check point is run on all threads returning a count of the threads that must 1008 // run through the barrier including self. 1009 size_t barrier_count = thread_list->RunCheckpoint(&check_point); 1010 // Release locks then wait for all mutator threads to pass the barrier. 1011 // TODO: optimize to not release locks when there are no threads to wait for. 1012 Locks::heap_bitmap_lock_->ExclusiveUnlock(self); 1013 Locks::mutator_lock_->SharedUnlock(self); 1014 ThreadState old_state = self->SetState(kWaitingForCheckPointsToRun); 1015 CHECK_EQ(old_state, kWaitingPerformingGc); 1016 gc_barrier_->Increment(self, barrier_count); 1017 self->SetState(kWaitingPerformingGc); 1018 Locks::mutator_lock_->SharedLock(self); 1019 Locks::heap_bitmap_lock_->ExclusiveLock(self); 1020 timings_.EndSplit(); 1021} 1022 1023void MarkSweep::SweepArray(accounting::ObjectStack* allocations, bool swap_bitmaps) { 1024 timings_.StartSplit("SweepArray"); 1025 Thread* self = Thread::Current(); 1026 mirror::Object* chunk_free_buffer[kSweepArrayChunkFreeSize]; 1027 size_t chunk_free_pos = 0; 1028 size_t freed_bytes = 0; 1029 size_t freed_large_object_bytes = 0; 1030 size_t freed_objects = 0; 1031 size_t freed_large_objects = 0; 1032 // How many objects are left in the array, modified after each space is swept. 1033 Object** objects = const_cast<Object**>(allocations->Begin()); 1034 size_t count = allocations->Size(); 1035 // Change the order to ensure that the non-moving space last swept as an optimization. 1036 std::vector<space::ContinuousSpace*> sweep_spaces; 1037 space::ContinuousSpace* non_moving_space = nullptr; 1038 for (space::ContinuousSpace* space : heap_->GetContinuousSpaces()) { 1039 if (space->IsAllocSpace() && !IsImmuneSpace(space) && space->GetLiveBitmap() != nullptr) { 1040 if (space == heap_->GetNonMovingSpace()) { 1041 non_moving_space = space; 1042 } else { 1043 sweep_spaces.push_back(space); 1044 } 1045 } 1046 } 1047 // Unlikely to sweep a significant amount of non_movable objects, so we do these after the after 1048 // the other alloc spaces as an optimization. 1049 if (non_moving_space != nullptr) { 1050 sweep_spaces.push_back(non_moving_space); 1051 } 1052 // Start by sweeping the continuous spaces. 1053 for (space::ContinuousSpace* space : sweep_spaces) { 1054 space::AllocSpace* alloc_space = space->AsAllocSpace(); 1055 accounting::SpaceBitmap* live_bitmap = space->GetLiveBitmap(); 1056 accounting::SpaceBitmap* mark_bitmap = space->GetMarkBitmap(); 1057 if (swap_bitmaps) { 1058 std::swap(live_bitmap, mark_bitmap); 1059 } 1060 Object** out = objects; 1061 for (size_t i = 0; i < count; ++i) { 1062 Object* obj = objects[i]; 1063 if (space->HasAddress(obj)) { 1064 // This object is in the space, remove it from the array and add it to the sweep buffer 1065 // if needed. 1066 if (!mark_bitmap->Test(obj)) { 1067 if (chunk_free_pos >= kSweepArrayChunkFreeSize) { 1068 timings_.StartSplit("FreeList"); 1069 freed_objects += chunk_free_pos; 1070 freed_bytes += alloc_space->FreeList(self, chunk_free_pos, chunk_free_buffer); 1071 timings_.EndSplit(); 1072 chunk_free_pos = 0; 1073 } 1074 chunk_free_buffer[chunk_free_pos++] = obj; 1075 } 1076 } else { 1077 *(out++) = obj; 1078 } 1079 } 1080 if (chunk_free_pos > 0) { 1081 timings_.StartSplit("FreeList"); 1082 freed_objects += chunk_free_pos; 1083 freed_bytes += alloc_space->FreeList(self, chunk_free_pos, chunk_free_buffer); 1084 timings_.EndSplit(); 1085 chunk_free_pos = 0; 1086 } 1087 // All of the references which space contained are no longer in the allocation stack, update 1088 // the count. 1089 count = out - objects; 1090 } 1091 // Handle the large object space. 1092 space::LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace(); 1093 accounting::ObjectSet* large_live_objects = large_object_space->GetLiveObjects(); 1094 accounting::ObjectSet* large_mark_objects = large_object_space->GetMarkObjects(); 1095 if (swap_bitmaps) { 1096 std::swap(large_live_objects, large_mark_objects); 1097 } 1098 for (size_t i = 0; i < count; ++i) { 1099 Object* obj = objects[i]; 1100 // Handle large objects. 1101 if (!large_mark_objects->Test(obj)) { 1102 ++freed_large_objects; 1103 freed_large_object_bytes += large_object_space->Free(self, obj); 1104 } 1105 } 1106 timings_.EndSplit(); 1107 1108 timings_.StartSplit("RecordFree"); 1109 VLOG(heap) << "Freed " << freed_objects << "/" << count 1110 << " objects with size " << PrettySize(freed_bytes); 1111 heap_->RecordFree(freed_objects + freed_large_objects, freed_bytes + freed_large_object_bytes); 1112 freed_objects_.FetchAndAdd(freed_objects); 1113 freed_large_objects_.FetchAndAdd(freed_large_objects); 1114 freed_bytes_.FetchAndAdd(freed_bytes); 1115 freed_large_object_bytes_.FetchAndAdd(freed_large_object_bytes); 1116 timings_.EndSplit(); 1117 1118 timings_.StartSplit("ResetStack"); 1119 allocations->Reset(); 1120 timings_.EndSplit(); 1121} 1122 1123void MarkSweep::Sweep(bool swap_bitmaps) { 1124 DCHECK(mark_stack_->IsEmpty()); 1125 TimingLogger::ScopedSplit("Sweep", &timings_); 1126 for (const auto& space : GetHeap()->GetContinuousSpaces()) { 1127 if (space->IsContinuousMemMapAllocSpace()) { 1128 space::ContinuousMemMapAllocSpace* alloc_space = space->AsContinuousMemMapAllocSpace(); 1129 TimingLogger::ScopedSplit split( 1130 alloc_space->IsZygoteSpace() ? "SweepZygoteSpace" : "SweepMallocSpace", &timings_); 1131 size_t freed_objects = 0; 1132 size_t freed_bytes = 0; 1133 alloc_space->Sweep(swap_bitmaps, &freed_objects, &freed_bytes); 1134 heap_->RecordFree(freed_objects, freed_bytes); 1135 freed_objects_.FetchAndAdd(freed_objects); 1136 freed_bytes_.FetchAndAdd(freed_bytes); 1137 } 1138 } 1139 SweepLargeObjects(swap_bitmaps); 1140} 1141 1142void MarkSweep::SweepLargeObjects(bool swap_bitmaps) { 1143 TimingLogger::ScopedSplit("SweepLargeObjects", &timings_); 1144 size_t freed_objects = 0; 1145 size_t freed_bytes = 0; 1146 GetHeap()->GetLargeObjectsSpace()->Sweep(swap_bitmaps, &freed_objects, &freed_bytes); 1147 freed_large_objects_.FetchAndAdd(freed_objects); 1148 freed_large_object_bytes_.FetchAndAdd(freed_bytes); 1149 GetHeap()->RecordFree(freed_objects, freed_bytes); 1150} 1151 1152// Process the "referent" field in a java.lang.ref.Reference. If the 1153// referent has not yet been marked, put it on the appropriate list in 1154// the heap for later processing. 1155void MarkSweep::DelayReferenceReferent(mirror::Class* klass, Object* obj) { 1156 DCHECK(klass != nullptr); 1157 DCHECK(klass->IsReferenceClass()); 1158 DCHECK(obj != NULL); 1159 heap_->DelayReferenceReferent(klass, obj, IsMarkedCallback, this); 1160} 1161 1162class MarkObjectVisitor { 1163 public: 1164 explicit MarkObjectVisitor(MarkSweep* const mark_sweep) ALWAYS_INLINE : mark_sweep_(mark_sweep) {} 1165 1166 // TODO: Fixme when anotatalysis works with visitors. 1167 void operator()(const Object* /* obj */, const Object* ref, const MemberOffset& /* offset */, 1168 bool /* is_static */) const ALWAYS_INLINE 1169 NO_THREAD_SAFETY_ANALYSIS { 1170 if (kCheckLocks) { 1171 Locks::mutator_lock_->AssertSharedHeld(Thread::Current()); 1172 Locks::heap_bitmap_lock_->AssertExclusiveHeld(Thread::Current()); 1173 } 1174 mark_sweep_->MarkObject(ref); 1175 } 1176 1177 private: 1178 MarkSweep* const mark_sweep_; 1179}; 1180 1181// Scans an object reference. Determines the type of the reference 1182// and dispatches to a specialized scanning routine. 1183void MarkSweep::ScanObject(Object* obj) { 1184 MarkObjectVisitor visitor(this); 1185 ScanObjectVisit(obj, visitor); 1186} 1187 1188void MarkSweep::ProcessMarkStackParallel(size_t thread_count) { 1189 Thread* self = Thread::Current(); 1190 ThreadPool* thread_pool = GetHeap()->GetThreadPool(); 1191 const size_t chunk_size = std::min(mark_stack_->Size() / thread_count + 1, 1192 static_cast<size_t>(MarkStackTask<false>::kMaxSize)); 1193 CHECK_GT(chunk_size, 0U); 1194 // Split the current mark stack up into work tasks. 1195 for (mirror::Object **it = mark_stack_->Begin(), **end = mark_stack_->End(); it < end; ) { 1196 const size_t delta = std::min(static_cast<size_t>(end - it), chunk_size); 1197 thread_pool->AddTask(self, new MarkStackTask<false>(thread_pool, this, delta, 1198 const_cast<const mirror::Object**>(it))); 1199 it += delta; 1200 } 1201 thread_pool->SetMaxActiveWorkers(thread_count - 1); 1202 thread_pool->StartWorkers(self); 1203 thread_pool->Wait(self, true, true); 1204 thread_pool->StopWorkers(self); 1205 mark_stack_->Reset(); 1206 CHECK_EQ(work_chunks_created_, work_chunks_deleted_) << " some of the work chunks were leaked"; 1207} 1208 1209// Scan anything that's on the mark stack. 1210void MarkSweep::ProcessMarkStack(bool paused) { 1211 timings_.StartSplit("ProcessMarkStack"); 1212 size_t thread_count = GetThreadCount(paused); 1213 if (kParallelProcessMarkStack && thread_count > 1 && 1214 mark_stack_->Size() >= kMinimumParallelMarkStackSize) { 1215 ProcessMarkStackParallel(thread_count); 1216 } else { 1217 // TODO: Tune this. 1218 static const size_t kFifoSize = 4; 1219 BoundedFifoPowerOfTwo<Object*, kFifoSize> prefetch_fifo; 1220 for (;;) { 1221 Object* obj = NULL; 1222 if (kUseMarkStackPrefetch) { 1223 while (!mark_stack_->IsEmpty() && prefetch_fifo.size() < kFifoSize) { 1224 Object* obj = mark_stack_->PopBack(); 1225 DCHECK(obj != NULL); 1226 __builtin_prefetch(obj); 1227 prefetch_fifo.push_back(obj); 1228 } 1229 if (prefetch_fifo.empty()) { 1230 break; 1231 } 1232 obj = prefetch_fifo.front(); 1233 prefetch_fifo.pop_front(); 1234 } else { 1235 if (mark_stack_->IsEmpty()) { 1236 break; 1237 } 1238 obj = mark_stack_->PopBack(); 1239 } 1240 DCHECK(obj != NULL); 1241 ScanObject(obj); 1242 } 1243 } 1244 timings_.EndSplit(); 1245} 1246 1247inline bool MarkSweep::IsMarked(const Object* object) const 1248 SHARED_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) { 1249 if (IsImmune(object)) { 1250 return true; 1251 } 1252 DCHECK(current_mark_bitmap_ != NULL); 1253 if (current_mark_bitmap_->HasAddress(object)) { 1254 return current_mark_bitmap_->Test(object); 1255 } 1256 return heap_->GetMarkBitmap()->Test(object); 1257} 1258 1259void MarkSweep::FinishPhase() { 1260 TimingLogger::ScopedSplit split("FinishPhase", &timings_); 1261 // Can't enqueue references if we hold the mutator lock. 1262 Heap* heap = GetHeap(); 1263 timings_.NewSplit("PostGcVerification"); 1264 heap->PostGcVerification(this); 1265 1266 timings_.NewSplit("RequestHeapTrim"); 1267 heap->RequestHeapTrim(); 1268 1269 // Update the cumulative statistics 1270 total_freed_objects_ += GetFreedObjects() + GetFreedLargeObjects(); 1271 total_freed_bytes_ += GetFreedBytes() + GetFreedLargeObjectBytes(); 1272 1273 // Ensure that the mark stack is empty. 1274 CHECK(mark_stack_->IsEmpty()); 1275 1276 if (kCountScannedTypes) { 1277 VLOG(gc) << "MarkSweep scanned classes=" << class_count_ << " arrays=" << array_count_ 1278 << " other=" << other_count_; 1279 } 1280 1281 if (kCountTasks) { 1282 VLOG(gc) << "Total number of work chunks allocated: " << work_chunks_created_; 1283 } 1284 1285 if (kMeasureOverhead) { 1286 VLOG(gc) << "Overhead time " << PrettyDuration(overhead_time_); 1287 } 1288 1289 if (kProfileLargeObjects) { 1290 VLOG(gc) << "Large objects tested " << large_object_test_ << " marked " << large_object_mark_; 1291 } 1292 1293 if (kCountClassesMarked) { 1294 VLOG(gc) << "Classes marked " << classes_marked_; 1295 } 1296 1297 if (kCountJavaLangRefs) { 1298 VLOG(gc) << "References scanned " << reference_count_; 1299 } 1300 1301 // Update the cumulative loggers. 1302 cumulative_timings_.Start(); 1303 cumulative_timings_.AddLogger(timings_); 1304 cumulative_timings_.End(); 1305 1306 // Clear all of the spaces' mark bitmaps. 1307 for (const auto& space : GetHeap()->GetContinuousSpaces()) { 1308 accounting::SpaceBitmap* bitmap = space->GetMarkBitmap(); 1309 if (bitmap != nullptr && 1310 space->GetGcRetentionPolicy() != space::kGcRetentionPolicyNeverCollect) { 1311 bitmap->Clear(); 1312 } 1313 } 1314 mark_stack_->Reset(); 1315 1316 // Reset the marked large objects. 1317 space::LargeObjectSpace* large_objects = GetHeap()->GetLargeObjectsSpace(); 1318 large_objects->GetMarkObjects()->Clear(); 1319} 1320 1321} // namespace collector 1322} // namespace gc 1323} // namespace art 1324