标记-清除算法中实际上有两个信息共同决定了哪些对象为垃圾对象。第一个信息是进程中当前存在的所有对象，可以用集合Live来表示它们。·第二个信息是标记时能被扫描到的对象，可以用集合Mark表示它们。最终的垃圾对象就是集合Live减去集合Mark。MarkingSweep的MarkingPhase函数的功能就是确定集合Mark。

void MarkSweep::MarkingPhase() {
  TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
  Thread* self = Thread::Current();
  BindBitmaps();
  FindDefaultSpaceBitmap();
  // Process dirty cards and add dirty cards to mod union tables.
  // If the GC type is non sticky, then we just clear the cards of the
  // alloc space instead of aging them.
  //
  // Note that it is fine to clear the cards of the alloc space here,
  // in the case of a concurrent (non-sticky) mark-sweep GC (whose
  // marking phase _is_ performed concurrently with mutator threads
  // running and possibly dirtying cards), as the whole alloc space
  // will be traced in that case, starting *after* this call to
  // Heap::ProcessCards (see calls to MarkSweep::MarkRoots and
  // MarkSweep::MarkReachableObjects). References held by objects on
  // cards that became dirty *after* the actual marking work started
  // will be marked in the pause (see MarkSweep::PausePhase), in a
  // *non-concurrent* way to prevent races with mutator threads.
  //
  // TODO: Do we need some sort of fence between the call to
  // Heap::ProcessCard and the calls to MarkSweep::MarkRoot /
  // MarkSweep::MarkReachableObjects below to make sure write
  // operations in the card table clearing the alloc space's dirty
  // cards (during the call to Heap::ProcessCard) are not reordered
  // *after* marking actually starts?
  heap_->ProcessCards(GetTimings(),
                      /* use_rem_sets= */ false,
                      /* process_alloc_space_cards= */ true,
                      /* clear_alloc_space_cards= */ GetGcType() != kGcTypeSticky);
  WriterMutexLock mu(self, *Locks::heap_bitmap_lock_);
  MarkRoots(self);
  MarkReachableObjects();
  // Pre-clean dirtied cards to reduce pauses.
  PreCleanCards();
}

(1) kGcRetentionPolicyNeverCollect表示不用对该空间的对象进行垃圾回收。

void MarkSweep::BindBitmaps() {
  TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
  WriterMutexLock mu(Thread::Current(), *Locks::heap_bitmap_lock_);
  // Mark all of the spaces we never collect as immune.
  for (const auto& space : GetHeap()->GetContinuousSpaces()) {
//(1)
    if (space->GetGcRetentionPolicy() == space::kGcRetentionPolicyNeverCollect) {
      immune_spaces_.AddSpace(space);
    }
  }
}

(1) ImageSpace重载了GetLiveBitmap和GetMarkBitmap函数，返回的都是ImageSpace的live_bitmap_,HasBoundBitmaps()返回True

void ImmuneSpaces::AddSpace(space::ContinuousSpace* space) {
  DCHECK(spaces_.find(space) == spaces_.end()) << *space;
  // Bind live to mark bitmap if necessary.
// (1)
  if (space->GetLiveBitmap() != nullptr && !space->HasBoundBitmaps()) {
    CHECK(space->IsContinuousMemMapAllocSpace());
    space->AsContinuousMemMapAllocSpace()->BindLiveToMarkBitmap();
  }
  spaces_.insert(space);
  CreateLargestImmuneRegion();
}

DlMallocSpace和RosAllocSpace回收策略是kGcRetentionPolicyAlwaysCollect

void MarkSweep::FindDefaultSpaceBitmap() {
  TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
  for (const auto& space : GetHeap()->GetContinuousSpaces()) {
    accounting::ContinuousSpaceBitmap* bitmap = space->GetMarkBitmap();
    // We want to have the main space instead of non moving if possible.
    if (bitmap != nullptr &&
        space->GetGcRetentionPolicy() == space::kGcRetentionPolicyAlwaysCollect) {
      current_space_bitmap_ = bitmap;
      // If we are not the non moving space exit the loop early since this will be good enough.
      if (space != heap_->GetNonMovingSpace()) {
        break;
      }
    }
  }
}

MarkRoots标记根对象

(1) MarkSweep成员变量mark_bitmap_类型为HeapBitmap，它其实就是Heap的mark_bitmap_成员。HeapBitmap包含了所有连续空间对象的mark_bitmap_成员。不过，对ImageSpace来说，它的live_bitmap_也被包含在Heap mark_bitmap_中了。在下面这行代码中，Test函数将测试obj在位图中对应的位是否为1。一个Obj如果位于ImageSpace空间的话，它一定是存活的（同时也是早就被标记了的。因为ImageSpace->GetMarkBitmap返回的也是live_bitmap_）
(2) 由FindDefaultSpaceBitmap函数可知，current_space_bitmap_为某个空间对象的mark_bitmap_。判断一个Obj是否被标记的标准就是该Obj在mark_bitmap_中对应位的值是否为1。所以，本段代码的主要工作可总结为：
1.HasAddress检查current_space_bitmap_对应的内存空间是否包含了obj对象
2.如果满足条件，则调用Set函数设置obj对应位的值为1。于是，这个Obj就算被标记了。
3.Set函数返回该位的旧值。如果旧值为0，说明这个obj之前没有被标记。调用PushOnMarkStack将obj加入到MarkSweepmark_stack_容器中。mark_stack_为一个ObjectStack对象。

(3) 新标记的obj保存在mark_stack_中。

inline void MarkSweep::MarkObjectNonNull(mirror::Object* obj,
                                         mirror::Object* holder,
                                         MemberOffset offset) {
  if (kUseBakerReadBarrier) {
    // Verify all the objects have the correct state installed.
    obj->AssertReadBarrierState();
  }
//(1)
  if (immune_spaces_.IsInImmuneRegion(obj)) {
    if (kCountMarkedObjects) {
      ++mark_immune_count_;
    }
    DCHECK(mark_bitmap_->Test(obj));
//(2)
  } else if (LIKELY(current_space_bitmap_->HasAddress(obj))) {
    if (kCountMarkedObjects) {
      ++mark_fastpath_count_;
    }
    if (UNLIKELY(!current_space_bitmap_->Set(obj))) {
      PushOnMarkStack(obj);  // This object was not previously marked.
    }
  } else {
    if (kCountMarkedObjects) {
      ++mark_slowpath_count_;
    }
    MarkObjectSlowPath visitor(this, holder, offset);
    // TODO: We already know that the object is not in the current_space_bitmap_ but MarkBitmap::Set
    // will check again.
//(3)
    if (!mark_bitmap_->Set(obj, visitor)) {
      PushOnMarkStack(obj);  // Was not already marked, push.
    }
  }
}

MarkReachableObjects

从根对象出发以标记所有能追踪到的对象。

void MarkSweep::MarkReachableObjects() {


  UpdateAndMarkModUnion();
  // Recursively mark all the non-image bits set in the mark bitmap.
  RecursiveMark();
}

在MarkRoots函数中，immune_spaces_的空间中的对象没有被“标记”（或者说早就被标记好了）。原因就是上文MarkObjectNonNull代码注释中所述的那样，这些空间中的对象无须标记——比如ImageSpace中的对象可能都是长期存活的，永远不会是垃圾。但是，它们的引用型成员变量指向的对象却可能位于其他空间。这些对象需要被找到并且标记。UpdateAndMarkModUnion会处理这个问题。

void MarkSweep::UpdateAndMarkModUnion() {
  for (const auto& space : immune_spaces_.GetSpaces()) {
    const char* name = space->IsZygoteSpace()
        ? "UpdateAndMarkZygoteModUnionTable"
        : "UpdateAndMarkImageModUnionTable";
    DCHECK(space->IsZygoteSpace() || space->IsImageSpace()) << *space;
    TimingLogger::ScopedTiming t(name, GetTimings());
    accounting::ModUnionTable* mod_union_table = heap_->FindModUnionTableFromSpace(space);
    if (mod_union_table != nullptr) {
      mod_union_table->UpdateAndMarkReferences(this);
    } else {
      // No mod-union table, scan all the live bits. This can only occur for app images.
      space->GetLiveBitmap()->VisitMarkedRange(reinterpret_cast<uintptr_t>(space->Begin()),
                                               reinterpret_cast<uintptr_t>(space->End()),
                                               ScanObjectVisitor(this));
    }
  }
}

void MarkSweep::RecursiveMark() {
  ProcessMarkStack(false);
}

// Scan anything that's on the mark stack.
void MarkSweep::ProcessMarkStack(bool paused) {
  TimingLogger::ScopedTiming t(paused ? "(Paused)ProcessMarkStack" : __FUNCTION__, GetTimings());
  size_t thread_count = GetThreadCount(paused);
  if (kParallelProcessMarkStack && thread_count > 1 &&
      mark_stack_->Size() >= kMinimumParallelMarkStackSize) {
    ProcessMarkStackParallel(thread_count);
  } else {
    // TODO: Tune this.
    static const size_t kFifoSize = 4;
    BoundedFifoPowerOfTwo<mirror::Object*, kFifoSize> prefetch_fifo;
    for (;;) {
      mirror::Object* obj = nullptr;
      if (kUseMarkStackPrefetch) {
        while (!mark_stack_->IsEmpty() && prefetch_fifo.size() < kFifoSize) {
          mirror::Object* mark_stack_obj = mark_stack_->PopBack();
          DCHECK(mark_stack_obj != nullptr);
          __builtin_prefetch(mark_stack_obj);
          prefetch_fifo.push_back(mark_stack_obj);
        }
        if (prefetch_fifo.empty()) {
          break;
        }
        obj = prefetch_fifo.front();
        prefetch_fifo.pop_front();
      } else {
        if (mark_stack_->IsEmpty()) {
          break;
        }
        obj = mark_stack_->PopBack();
      }
      DCHECK(obj != nullptr);
      ScanObject(obj);
    }
  }
}

最终标记的信息保存在各个Space的mark_bitmap_中。

(1) allocation_stack_.swap(live_stack_);交换之前，live_stack_的内容为空，而allocation_stack_则保存了mutator线程创建的对象。交换后，live_stack_保存了mutator所创建的对象，而allocation_stack_则变为空的容器。

void MarkSweep::PausePhase() {
  TimingLogger::ScopedTiming t("(Paused)PausePhase", GetTimings());
  Thread* self = Thread::Current();
  Locks::mutator_lock_->AssertExclusiveHeld(self);
  if (IsConcurrent()) {
    // Handle the dirty objects if we are a concurrent GC.
    WriterMutexLock mu(self, *Locks::heap_bitmap_lock_);
    // Re-mark root set.
    ReMarkRoots();
    // Scan dirty objects, this is only required if we are doing concurrent GC.
    RecursiveMarkDirtyObjects(true, accounting::CardTable::kCardDirty);
  }
  {
    TimingLogger::ScopedTiming t2("SwapStacks", GetTimings());
    WriterMutexLock mu(self, *Locks::heap_bitmap_lock_);
//(1)
    heap_->SwapStacks();
    live_stack_freeze_size_ = heap_->GetLiveStack()->Size();
    // Need to revoke all the thread local allocation stacks since we just swapped the allocation
    // stacks and don't want anybody to allocate into the live stack.
    RevokeAllThreadLocalAllocationStacks(self);
  }
  heap_->PreSweepingGcVerification(this);
  // Disallow new system weaks to prevent a race which occurs when someone adds a new system
  // weak before we sweep them. Since this new system weak may not be marked, the GC may
  // incorrectly sweep it. This also fixes a race where interning may attempt to return a strong
  // reference to a string that is about to be swept.
  Runtime::Current()->DisallowNewSystemWeaks();
  // Enable the reference processing slow path, needs to be done with mutators paused since there
  // is no lock in the GetReferent fast path.
  GetHeap()->GetReferenceProcessor()->EnableSlowPath();
}

三色标记在MarkSweep中体现也并不直接。简单来说，位于mark_stack_中的对象都是灰色，而从mark_stack_中移除出来的对象就是黑色（说明这个对象已经被搜索）。剩下的就是白色垃圾了。