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