Semi-Space（SS）GC和Generational Semi-Space（GSS）GC是ART運作時引進的兩個Compacting GC。它們的共同特點是都具有一個From Space和一個To Space。在GC執行期間，在From Space配置設定的還存活的對象會被依次拷貝到To Space中，這樣就可以達到消除記憶體碎片的目的。本文就将SS GC和GSS GC的執行過程分析進行詳細分析。
老羅的新浪微網誌：http://weibo.com/shengyangluo，歡迎關注！
《Android系統源代碼情景分析》一書正在進擊的程式員網（http://0xcc0xcd.com）中連載，點選進入！
與SS GC相比，GSS GC還多了一個Promote Space。當一個對象是在上一次GC之前配置設定的，并且在目前GC中仍然是存活的，那麼它就會被拷貝到Promote Space中，而不是To Space中。這相當于是簡單地将對象劃分為新生代和老生代的，即在上一次GC之前配置設定的對象屬于老生代的，而在上一次GC之後配置設定的對象屬于新生代的。一般來說，老生代對象的存活性要比新生代的久，是以将它們拷貝到Promote Space中去，可以避免每次執行SS GC或者GSS GC時，都需要對它們進行無用的處理。
總結來說，SS GC和GSS GC的執行過程就如圖1和圖2所示：
圖1 SS GC的執行過程
圖2 GSS GC的執行過程
在圖1和圖2中，Bump Pointer Space 1和Bump Pointer Space 2就是我們前面說的From Space和To Space。接下來我們就結合源碼來詳細分析它們的執行過程。
從前面ART運作時Compacting GC為新建立對象配置設定記憶體的過程分析一文可以知道，在ART運作時内部，都是通過調用Heap類的成員函數CollectGarbageInternal開始執行GC的，是以，我們就從它開始分析SS GC和GSS GC的執行過程。
Heap類的成員函數CollectGarbageInternal的實作如下所示：
collector::GcType Heap::CollectGarbageInternal(collector::GcType gc_type, GcCause gc_cause,
bool clear_soft_references) {
Thread* self = Thread::Current();
Runtime* runtime = Runtime::Current();
......
bool compacting_gc;
{
......
MutexLock mu(self, *gc_complete_lock_);
// Ensure there is only one GC at a time.
WaitForGcToCompleteLocked(gc_cause, self);
compacting_gc = IsMovingGc(collector_type_);
// GC can be disabled if someone has a used GetPrimitiveArrayCritical.
if (compacting_gc && disable_moving_gc_count_ != 0) {
......
return collector::kGcTypeNone;
}
collector_type_running_ = collector_type_;
}
......
collector::GarbageCollector* collector = nullptr;
// TODO: Clean this up.
if (compacting_gc) {
......
switch (collector_type_) {
case kCollectorTypeSS:
// Fall-through.
case kCollectorTypeGSS:
semi_space_collector_->SetFromSpace(bump_pointer_space_);
semi_space_collector_->SetToSpace(temp_space_);
semi_space_collector_->SetSwapSemiSpaces(true);
collector = semi_space_collector_;
break;
case kCollectorTypeCC:
collector = concurrent_copying_collector_;
break;
case kCollectorTypeMC:
mark_compact_collector_->SetSpace(bump_pointer_space_);
collector = mark_compact_collector_;
break;
default:
LOG(FATAL) << "Invalid collector type " << static_cast<size_t>(collector_type_);
}
......
gc_type = collector::kGcTypeFull; // TODO: Not hard code this in.
}
......
collector->Run(gc_cause, clear_soft_references || runtime->IsZygote());
......
RequestHeapTrim();
// Enqueue cleared references.
reference_processor_.EnqueueClearedReferences(self);
// Grow the heap so that we know when to perform the next GC.
GrowForUtilization(collector);
......
FinishGC(self, gc_type);
......
return gc_type;
}
這個函數定義在檔案art/runtime/gc/heap.cc中。
Heap類的成員函數CollectGarbageInternal首先是調用成員函數WaitForGcToCompleteLocked確定目前沒有GC正在執行。如果有的話，那麼就等待它執行完成。接下來再調用成員函數IsMovingGc判斷目前要執行的GC是否是一個Compacting GC，即判斷Heap類的成員變量collector_type_指向的一個垃圾收集器是否是一個Compacting GC類型的垃圾收集器。如果是一個Compacting GC，但是目前又被禁止執行Compacting GC，即Heap類的成員變量disable_moving_gc_count_不等于0，那麼目前GC就是禁止執行的。是以在這種情況下，Heap類的成員函數CollectGarbageInternal就什麼也不做就直接傳回collector::kGcTypeNone給調用者了。
我們隻關注Compacting GC的情況，即變量compacting_gc等于true的情況。在ART運作時中，Compacting GC有四種，分别是Semi-Space GC、Generational Semi-Space GC、Mark-Compact GC和Concurrent Copying GC。其中，Semi-Space GC和Generational Semi-Space GC使用的是同一個垃圾收集器，儲存在Heap類的成員變量semi_space_collector_中，差別隻在于前者不支援分代而後者支援；Mark-Compact GC和Concurrent Copying GC使用的垃圾收集器儲存在Heap類的成員變量mark_compact_collector_和concurrent_copying_collector_中。但是，Concurrent Copying GC在Android 5.0中還沒有具體實作，是以實際上就隻有前面三種Compacting GC。
Heap類的成員變量semi_space_collector_、mark_compact_collector_和concurrent_copying_collector_的初始化發生在Heap類的構造函數中，如下所示：
Heap::Heap(size_t initial_size, size_t growth_limit, size_t min_free, size_t max_free,
double target_utilization, double foreground_heap_growth_multiplier,
size_t capacity, size_t non_moving_space_capacity, const std::string& image_file_name,
const InstructionSet image_instruction_set, CollectorType foreground_collector_type,
CollectorType background_collector_type, size_t parallel_gc_threads,
size_t conc_gc_threads, bool low_memory_mode,
size_t long_pause_log_threshold, size_t long_gc_log_threshold,
bool ignore_max_footprint, bool use_tlab,
bool verify_pre_gc_heap, bool verify_pre_sweeping_heap, bool verify_post_gc_heap,
bool verify_pre_gc_rosalloc, bool verify_pre_sweeping_rosalloc,
bool verify_post_gc_rosalloc, bool use_homogeneous_space_compaction_for_oom,
uint64_t min_interval_homogeneous_space_compaction_by_oom)
......
if (kMovingCollector) {
// TODO: Clean this up.
const bool generational = foreground_collector_type_ == kCollectorTypeGSS;
semi_space_collector_ = new collector::SemiSpace(this, generational,
generational ? "generational" : "");
garbage_collectors_.push_back(semi_space_collector_);
concurrent_copying_collector_ = new collector::ConcurrentCopying(this);
garbage_collectors_.push_back(concurrent_copying_collector_);
mark_compact_collector_ = new collector::MarkCompact(this);
garbage_collectors_.push_back(mark_compact_collector_);
}
......
}
這個函數定義在檔案art/runtime/gc/heap.cc中。
從這裡就可以看出，Heap類的成員變量semi_space_collector_、mark_compact_collector_和concurrent_copying_collector_指向的對象分别是SemiSpace、MarkCompact和ConcurrentCopying。
這裡需要注意的是Heap類的成員變量semi_space_collector_，當ART運作時啟動時指定的Foreground GC為Generational Semi-Space GC時，它所指向的SemiSpace就是支援分代的；否則的話，就不支援。
回到Heap類的成員函數CollectGarbageInternal中，當目前執行的GC是Semi-Space GC或者Generational Semi-Space GC時，From Space和To Space分别被設定為Heap類的成員變量bump_pointer_space_和temp_space_描述的Space。從前面ART運作時Compacting GC堆建立過程分析一文可以知道，這兩個成員變量描述的Space均為Bump Pointer Space。此外，此時使用的SemiSpace被告知，當GC執行完畢，需要交換From Space和To Space，也就是交換Heap類的成員變量bump_pointer_space_和temp_space_描述的兩個Bump Pointer Space。另外，當目前執行的GC是Mark-Compact GC時，隻需要指定一個Bump Pointer Space，也就是Heap類的成員變量bump_pointer_space_所指向的Bump Pointer Space。由于Concurrent Copying GC還沒有具體的實作，是以我們忽略與它相關的邏輯。
确定好目前Compacting GC所使用的垃圾收集器之後，需要将參數gc_type設定為collector::kGcTypeFull。這表示Compacting類型的GC垃圾收集器隻能執行類型為collector::kGcTypeFull。這有差別是Mark-Sweep類型的GC，它們能夠執行collector::kGcTypeSticky、collector::kGcTypePartial和collector::kGcTypeFull三種類型的GC。
無論目前的GC使用的是什麼樣的垃圾收集器，都是從調用它們的成員函數Run開始執行的。在ART運作時中，所有的垃圾收集器都是從GarbageCollector類繼承下來的，并且也繼承了GarbageCollector類的成員函數Run。是以，在ART運作時中，所有的GC都是從GarbageCollector類的成員函數Run開始的。
GC執行完畢，Heap類的成員函數CollectGarbageInternal還會做以下四件主要的事情：
1. 調用Heap類的成員函數RequestHeapTrim請求對堆記憶體進行裁剪，也就是将沒有使用到的記憶體歸還給核心。
2. 調用Heap類的成員變量reference_processor_指向的一個ReferenceProcessor對象的成員函數EnqueueClearedReferences将那些目标對象已經被回收了的引用對象增加到它們建立時指定的清單中，以便使得應用程式知道有哪些被引用對象引用的目标對象被回收了。
3. 調用Heap類的成員函數GrowForUtilization根據預先設定的堆使用率相應地設定堆的大小。
4. 調用Heap類的成員函數FinishGC通知其它等待目前GC執行完成的ART運作時線程，以便它們可以繼續往下執行自己的邏輯。
這四件事情的具體執行過程可以參考前面ART運作時垃圾收集（GC）過程分析一文，這裡不再複述。這裡我們隻關注GC的執行過程，也就是GarbageCollector類的成員函數Run的實作，如下所示：
void GarbageCollector::Run(GcCause gc_cause, bool clear_soft_references) {
ATRACE_BEGIN(StringPrintf("%s %s GC", PrettyCause(gc_cause), GetName()).c_str());
Thread* self = Thread::Current();
uint64_t start_time = NanoTime();
Iteration* current_iteration = GetCurrentIteration();
current_iteration->Reset(gc_cause, clear_soft_references);
RunPhases(); // Run all the GC phases.
// Add the current timings to the cumulative timings.
cumulative_timings_.AddLogger(*GetTimings());
// Update cumulative statistics with how many bytes the GC iteration freed.
total_freed_objects_ += current_iteration->GetFreedObjects() +
current_iteration->GetFreedLargeObjects();
total_freed_bytes_ += current_iteration->GetFreedBytes() +
current_iteration->GetFreedLargeObjectBytes();
uint64_t end_time = NanoTime();
current_iteration->SetDurationNs(end_time - start_time);
if (Locks::mutator_lock_->IsExclusiveHeld(self)) {
// The entire GC was paused, clear the fake pauses which might be in the pause times and add
// the whole GC duration.
current_iteration->pause_times_.clear();
RegisterPause(current_iteration->GetDurationNs());
}
total_time_ns_ += current_iteration->GetDurationNs();
for (uint64_t pause_time : current_iteration->GetPauseTimes()) {
pause_histogram_.AddValue(pause_time / 1000);
}
ATRACE_END();
}
這個函數定義在檔案art/runtime/gc/collector/garbage_collector.cc中。
GarbageCollector類的成員函數Run最主要的工作就是調用由子類實作的成員函數RunPhases來執行具體的GC過程，其它的額外工作就是統計GC執行完成後釋放的對象數和記憶體位元組數，以及統計GC執行過程中的停頓時間等。這些統計資料有利于我們分析不同GC的執行性能。
這篇文章我們隻關注Semi-Space GC和Generational Semi-Space GC的執行過程中，是以，接下來我們就繼續分析SemiSpace類的成員函數RunPhases的實作，如下所示：
void SemiSpace::RunPhases() {
Thread* self = Thread::Current();
InitializePhase();
// Semi-space collector is special since it is sometimes called with the mutators suspended
// during the zygote creation and collector transitions. If we already exclusively hold the
// mutator lock, then we can't lock it again since it will cause a deadlock.
if (Locks::mutator_lock_->IsExclusiveHeld(self)) {
......
MarkingPhase();
ReclaimPhase();
......
} else {
Locks::mutator_lock_->AssertNotHeld(self);
{
ScopedPause pause(this);
......
MarkingPhase();
}
{
ReaderMutexLock mu(self, *Locks::mutator_lock_);
ReclaimPhase();
}
......
}
FinishPhase();
}
這個函數定義在檔案art/runtime/gc/collector/semi_space.cc中。
從這裡就可以看出，Semi-Space GC和Generational Semi-Space GC的執行過程可以分為四個階段：
1. 初始化階段；
2. 标記階段；
3. 回收階段；
4. 結束階段。
其中，标記階段需要在挂起除目前線程之外的其它所有ART運作時線程的前提下執行，回收階段則需要在獲得Locks::mutator_lock_鎖的前提下執行。但是由于在執行同構空間壓縮和Foreground/Background GC切換時，會使用到Semi-Space GC或者Generational Semi-Space GC，并且這兩個操作均是在挂起除目前線程之外的其它所有ART運作時線程的前提下執行的，而這個挂起操作同時也會擷取Locks::mutator_lock_鎖，是以，SemiSpace類的成員函數RunPhases在執行回收階段時，就需要作出決定需不需要執行擷取Locks::mutator_lock_鎖的操作。這個決定是必要的，因為Locks::mutator_lock_不是一個遞歸鎖，也就是不允許同一個線程重複獲得，否則的話就會進入死鎖狀态。關于鎖要不要支援遞歸擷取，技術是沒有任何問題的，但是需要考慮的是對程式邏輯的影響。一般來說，支援遞歸鎖不是一個好主意，詳細說明可以參考這篇文章：http://dev.chromium.org/developers/lock-and-condition-variable。
基于上述原因，SemiSpace類的成員函數RunPhases在執行标記階段和回收階段之前，先判斷一下目前線程是否已經獲得了Locks::mutator_lock_鎖。如果已經獲得，那麼就說明除目前線程之外的其它所有ART運作時線程均已被挂起，是以這裡就可以直接執行它們。否則的話，就是要在執行标記階段之前，挂起除目前線程之外的其它所有ART運作時線程，并且在執行回收階段之前，先擷取Locks::mutator_lock_鎖。
其中，挂起除目前線程之外的其它所有ART運作時線程是通過ScopedPause類來實作。ScopedPause類對象在構造的時候，會挂起除目前線程之外的其它所有ART運作時線程，并且在析構時，自動喚醒這些被挂起的ART運作時線程，如下所示：
GarbageCollector::ScopedPause::ScopedPause(GarbageCollector* collector)
: start_time_(NanoTime()), collector_(collector) {
Runtime::Current()->GetThreadList()->SuspendAll();
}
GarbageCollector::ScopedPause::~ScopedPause() {
collector_->RegisterPause(NanoTime() - start_time_);
Runtime::Current()->GetThreadList()->ResumeAll();
}
這兩個函數定義在檔案art/runtime/gc/collector/garbage_collector.cc。
其中，ScopedPause類的構造函數和析構函數還會記錄由挂起線程而引發的程式停頓時間。
回到SemiSpace類的成員函數RunPhases，接下來我們就分别分析上述的Semi-Space GC和Generational Semi-Space GC的四個階段的執行過程。
初始化階段由SemiSpace類的成員函數InitializePhase來執行，它的實作如下所示：
void SemiSpace::InitializePhase() {
TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
mark_stack_ = heap_->GetMarkStack();
DCHECK(mark_stack_ != nullptr);
immune_region_.Reset();
is_large_object_space_immune_ = false;
saved_bytes_ = 0;
bytes_moved_ = 0;
objects_moved_ = 0;
self_ = Thread::Current();
CHECK(from_space_->CanMoveObjects()) << "Attempting to move from " << *from_space_;
// Set the initial bitmap.
to_space_live_bitmap_ = to_space_->GetLiveBitmap();
{
// TODO: I don't think we should need heap bitmap lock to Get the mark bitmap.
ReaderMutexLock mu(Thread::Current(), *Locks::heap_bitmap_lock_);
mark_bitmap_ = heap_->GetMarkBitmap();
}
if (generational_) {
promo_dest_space_ = GetHeap()->GetPrimaryFreeListSpace();
}
fallback_space_ = GetHeap()->GetNonMovingSpace();
}
這個函數定義在檔案art/runtime/gc/collector/semi_space.cc中。
SemiSpace類的成員函數InitializePhase除了初始化一些成員變量之外，最重要的就是獲得ART運作時堆的兩個Space：
1. Promote Space。如果目前執行的是Generational Semi-Space GC，那麼就需要擷取Promote Space，這是通過調用Heap類的成員函數GetPrimaryFreeListSpace獲得的。前面提到，Promote Space是用來儲存那些老生代對象的。
2. Fallback Space。無論目前執行的是Semi-Space GC還是Generational Semi-Space GC，都需要擷取這個Space，這是通過Heap類的成員函數GetNonMovingSpace獲得的，也就是ART運作時堆的Non Moving Space。Fallback Space的作用是To Space空間已滿時，可以将From Space的對象移動到Fallback Space上去。
Heap類的成員函數GetPrimaryFreeListSpace傳回來的實際上是ART運作時堆的Main Space，如下所示：
class Heap {
public:
......
space::MallocSpace* GetPrimaryFreeListSpace() {
if (kUseRosAlloc) {
DCHECK(rosalloc_space_ != nullptr);
// reinterpret_cast is necessary as the space class hierarchy
// isn't known (#included) yet here.
return reinterpret_cast<space::MallocSpace*>(rosalloc_space_);
} else {
DCHECK(dlmalloc_space_ != nullptr);
return reinterpret_cast<space::MallocSpace*>(dlmalloc_space_);
}
}
......
};
這個函數定義在檔案art/runtime/gc/heap.h中。
從前面ART運作時Compacting GC堆建立過程分析一文可以知道，Heap類的成員變量rosalloc_space_和dlmalloc_space_描述的就是ART運作時堆的Main Space。取決于常量kUseRosAlloc的值。它由Heap類的成員變量rosalloc_space_或者dlmalloc_space_指向。
從前面ART運作時Compacting GC堆建立過程分析一文也可以知道，對于Generational Semi-Space GC來說，它的Main Space其實也是Non Moving Space，這意味着Generational Semi-Space GC使用的Promote Space和Fallback Space均為ART運作時堆的Non Moving Space。
标記階段由SemiSpace類的成員函數MarkingPhase來執行，它的實作如下所示：
void SemiSpace::MarkingPhase() {
......
// Revoke the thread local buffers since the GC may allocate into a RosAllocSpace and this helps
// to prevent fragmentation.
RevokeAllThreadLocalBuffers();
if (generational_) {
if (GetCurrentIteration()->GetGcCause() == kGcCauseExplicit ||
GetCurrentIteration()->GetGcCause() == kGcCauseForNativeAlloc ||
GetCurrentIteration()->GetClearSoftReferences()) {
// If an explicit, native allocation-triggered, or last attempt
// collection, collect the whole heap.
collect_from_space_only_ = false;
}
......
}
if (!collect_from_space_only_) {
// If non-generational, always clear soft references.
// If generational, clear soft references if a whole heap collection.
GetCurrentIteration()->SetClearSoftReferences(true);
}
Locks::mutator_lock_->AssertExclusiveHeld(self_);
if (generational_) {
// If last_gc_to_space_end_ is out of the bounds of the from-space
// (the to-space from last GC), then point it to the beginning of
// the from-space. For example, the very first GC or the
// pre-zygote compaction.
if (!from_space_->HasAddress(reinterpret_cast<mirror::Object*>(last_gc_to_space_end_))) {
last_gc_to_space_end_ = from_space_->Begin();
}
// Reset this before the marking starts below.
bytes_promoted_ = 0;
}
// Assume the cleared space is already empty.
BindBitmaps();
// Process dirty cards and add dirty cards to mod-union tables.
heap_->ProcessCards(GetTimings(), kUseRememberedSet && generational_);
......
heap_->GetCardTable()->ClearCardTable();
// Need to do this before the checkpoint since we don't want any threads to add references to
// the live stack during the recursive mark.
if (kUseThreadLocalAllocationStack) {
......
heap_->RevokeAllThreadLocalAllocationStacks(self_);
}
heap_->SwapStacks(self_);
{
WriterMutexLock mu(self_, *Locks::heap_bitmap_lock_);
MarkRoots();
// Recursively mark remaining objects.
MarkReachableObjects();
}
ProcessReferences(self_);
{
ReaderMutexLock mu(self_, *Locks::heap_bitmap_lock_);
SweepSystemWeaks();
}
// Revoke buffers before measuring how many objects were moved since the TLABs need to be revoked
// before they are properly counted.
RevokeAllThreadLocalBuffers();
// Record freed memory.
const int64_t from_bytes = from_space_->GetBytesAllocated();
const int64_t to_bytes = bytes_moved_;
const uint64_t from_objects = from_space_->GetObjectsAllocated();
const uint64_t to_objects = objects_moved_;
......
// Note: Freed bytes can be negative if we copy form a compacted space to a free-list backed
// space.
RecordFree(ObjectBytePair(from_objects - to_objects, from_bytes - to_bytes));
// Clear and protect the from space.
from_space_->Clear();
......
from_space_->GetMemMap()->Protect(kProtectFromSpace ? PROT_NONE : PROT_READ);
......
if (swap_semi_spaces_) {
heap_->SwapSemiSpaces();
}
}
這個函數定義在檔案art/runtime/gc/collector/semi_space.cc中。
SemiSpace類的成員函數MarkingPhase的執行過程如下所示：
1. 調用SemiSpace類的成員函數RevokeAllThreadLocalBuffers回收各個ART運作時線程的局部配置設定緩沖區。從前面ART運作時Compacting GC為新建立對象配置設定記憶體的過程分析這篇文章可以知道，ART運作時線程的局部配置設定緩沖區是來自Bump Pointer Space或者Ros Alloc Space的。由于現在要對Bump Pointer Space進行GC處理了，是以就需要把它作為ART運作時線程局部配置設定緩沖區的那部記憶體回收回來。避免GC處理完畢後，ART運作時線程的局部配置設定緩沖區引用到不正确記憶體。
2. Generational Semi-Space GC在執行時，預設隻對From Space進行處理，即當SemiSpace類的成員變量generational_與collect_from_space_only_的值是相同的。但是如果目前的Generational Semi-Space GC是在以下三種情況下執行：
1) 應用程式顯示請求執行；
2) 由于要配置設定Native記憶體而觸發執行；
3) 請求回收那些隻被軟引用對象引用的對象。
上述三種情況都是表達目前記憶體較緊張，是以就不能隻是回收From Space的記憶體，還應該考慮回收其它Space的記憶體，例如Non Moving Space的記憶體。
3. Semi-Space GC在執行時，預設不僅對From Space的記憶體進行處理，也對其它的Space的記憶體進行處理，例如Non Moving Space的記憶體，而且也會對那些隻被軟引用對象引用的對象進行處理，是以這種情況需要将該次GC标記為清理軟引用對象。
4. 對于Generational Semi-Space GC，需要有一個标準區分新生代和老生代對象，以便後面可以确定哪些對象要移動到Promote Space，哪些對象要移動到To Space。每次Generational Semi-Space GC執行完畢，To Space目前使用的記憶體的最大值都會記錄在SemiSpace類的成員變量last_gc_to_space_end_中。這樣，下次再執行Generational Semi-Space GC時，對于From Space（即上次GC時的To Space）的對象來說，位址小于last_gc_to_space_end_都是屬于老生代對象，而大于等于last_gc_to_space_end_都大于新生代對象。這也意味着在執行Generational Semi-Space GC時，我們要保證last_gc_to_space_end_的值要位于From Space的位址空間範圍内，否則的話，上述的判斷邏輯就會存在問題。
但是在第一次Generational Semi-Space GC執行之前，SemiSpace類的成員變量last_gc_to_space_end_是初始化為nullptr的，是以這種情況就需要将其重新初始化為From Space的起始值。還有另外一種不是第一次執行Generational Semi-Space GC的情況，也需要重新初始化SemiSpace類的成員變量last_gc_to_space_end_的值為From Space的起始值。這種情況就發生在Zygote程序fork第一個子程序之前執行的那次Compact Zygote操作中。我們假設Zygote程序fork第一次子程序前，已經執行過一次Generational Semi-Space GC，然後目前的GC又被切換為Mark-Sweep GC。現在執行Compact Zygote操作，從前面ART運作時Compacting GC為新建立對象配置設定記憶體的過程分析這篇文章可以知道，這時候的From Space并不是上次Generational Semi-Space GC的To Space，而是ART運作時堆的Main Space。這樣上次記錄的last_gc_to_space_end_的值肯定不是在Main Space的位址空間範圍之内。是以。這種情況也需要将SemiSpace類的成員變量last_gc_to_space_end_的值為From Space的起始值。
5. 做好前面的四個準備工作後，就可以調用Heap類的成員函數BindBitmaps确定目前GC要處理的Space了。這一方面是與Space的回收政策有關，例如，Image Space的回收政策為kGcRetentionPolicyNeverCollect，那麼它的記憶體就永遠不會被回收。另一方面也與SemiSpace類的成員變量collect_from_space_only_的值有關。
6. 調用Heap類的成員函數ProcessCards處理ART運作時的Dirty Card。從前面ART運作時垃圾收集（GC）過程分析一文可以知道，這實際上就是将Dirty Card都收集起來，以便後面可以對它們進行處理。
7. 從前面的分析可以知道，Semi-Space GC和Generational Semi-Space GC的标記階段是在挂起除目前線程之外的所有其它ART運作時線程的前提下執行的。是以，可以保證在剛才處理Dirty Card的過程中，Dirty Card不會被并行修改，是以這時候就可以安全地對其執行清理工作，這是通過調用CardTable類的成員函數ClearCardTable實作的。
8. 每個ART運作時線程除了有一個局部配置設定緩沖區之外，還有一個局部Allocation Stack。局部Allocation Stack與局部配置設定緩沖區是類似的，它們都是為了解決在多線程情況下需要加鎖才能通路公共的Allocation Stack和配置設定緩沖區的問題。是以，這裡對局部Allocation Stack的處理與對局部配置設定緩沖區的處理類似，都是需要對它們進行回收。這是通過調用Heap類的成員函數RevokeAllThreadLocalAllocationStacks來實作的。
9. 調用Heap類的成員函數SwapStacks交換ART運作時的Allocation Stack和Live Stack。這是每次GC都必須執行的操作，為了以後能夠正确地執行Sticky GC。
10. 現在終于可以進入我們熟悉的對象遞歸标記過程了。首先是調用SemiSpace類的成員函數MarkRoots找到根集對象，然後再調用SemiSpace類的成員函數MarkReachableObjects遞歸标記從根集對象可達的對象。對于不是要對所有的Space都進行處理的GC來說，根集對象隻包含那些位于目前需要處理的Space。但是在标記可達對象時，就不僅需要考慮從根集對象可達的對象，還需要考慮從Dirty Card可達的對象。舉個例子說，堆有A、B和C三個Space，現在要對B和C進行處理。從B和C的根集對象開始，可以找到B和C的所有可達對象。但是這時候并不意味着B和C的不可達對象就是可以回收的。因為A的對象自上次GC以來，可能修改了某些成員變量，使得它們引用了B和C的對象。也就是說，這部分被A的對象引用的B和C的對象不能回收。由于我們可以通過Dirty Card來獲得A的對象的修改資訊，是以結合Dirty Card，我們就可以正确地将B和C的所有可達對象都标記出來。這部分邏輯也是SemiSpace類的成員函數MarkReachableObjects負責完成的。
11. 調用SemiSpace類的成員函數ProcessReferences處理引用對象。這個處理過程可以參考前面ART運作時垃圾收集（GC）過程分析一文的分析。
12. 調用SemiSpace類的成員函數SweepSystemWeaks處理那些沒有被标記的常量字元串、Monitor對象和在JNI建立的全局弱引用對象等。這個處理過程可以參考前面ART運作時垃圾收集（GC）過程分析一文的分析。
13. 調用從父類GarbageCollector繼承下來的成員函數RecordFree統計目前GC釋放的對象數和記憶體位元組數。由Semi-Space GC和Generational Semi-Space GC在标記對象的過程就實作了對象移動。這意味着沒有被移動的對象就是需要回收其占用的記憶體的對象，是以當标記階段結束後，就可以知道目前GC釋放的對象數和記憶體位元組數了。在調用GarbageCollector類的成員函數RecordFree統計目前GC釋放的對象數和記憶體位元組數之前，這裡又重複調用了前面提到的SemiSpace類的成員函數RevokeAllThreadLocalBuffers來回收各個ART運作時線程的局部配置設定緩沖區。這似乎是不必要的，是以這時候除了目前線程之外，其他的ART運作時線程都是被挂起的，也就是說它們不會有修改其局部配置設定緩沖區的機會。
14. 這時候From Space就派不上用場了，因為它裡面的對象要麼是被移動到了To Space或者Promote Space的，要麼是要回收的。這時候就可以将From Space使用的記憶體位址清零，并且将它們的标志設定為PROT_NONE或者PROT_READ。也就是說，将From Space使用的記憶體位址設定為不可寫入。這樣如果對From Space發生了寫操作，就能夠檢測出來。這是一種錯誤的行為，因為這個From Space即将被設定為下一次GC的To Space，而To Space隻有等到下一次GC時才允許寫入操作。
15. 如果Semi-Space GC或者Generational Semi-Space GC在執行之前，設定了交換From Space和To Space的标志，也就是SemiSpace類的成員變量swap_semi_spaces_設定為true，那麼就調用Heap類的成員函數SwapSemiSpaces交換From Space和To Space。
在以十五個操作中第1、5、8和10這四個操作，對應的函數分别為SemiSpace類的成員函數RevokeAllThreadLocalBuffers、SemiSpace類的成員函數BindBitmaps、Heap類的成員函數RevokeAllThreadLocalAllocationStacks、SemiSpace類的成員函數MarkRoots和SemiSpace類的成員函數MarkReachableObjects。接下來我們就分别對它們進行分析，以便可以更好了解Semi-Space GC或者Generational Semi-Space GC的标記階段。
SemiSpace類的成員函數RevokeAllThreadLocalBuffers的實作如下所示：
void SemiSpace::RevokeAllThreadLocalBuffers() {
TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
GetHeap()->RevokeAllThreadLocalBuffers();
}
這個函數定義在檔案art/runtime/gc/collector/semi_space.cc中。
SemiSpace類的成員函數RevokeAllThreadLocalBuffers調用Heap類的成員函數RevokeAllThreadLocalBuffers來回收所有ART運作時線程的局配置設定緩沖區，後者的實作如下所示：
void Heap::RevokeAllThreadLocalBuffers() {
if (rosalloc_space_ != nullptr) {
rosalloc_space_->RevokeAllThreadLocalBuffers();
}
if (bump_pointer_space_ != nullptr) {
bump_pointer_space_->RevokeAllThreadLocalBuffers();
}
}
這個函數定義在檔案art/runtime/gc/heap.cc中。
從前面ART運作時Compacting GC為新建立對象配置設定記憶體的過程分析一文可以知道，ART運作時線程的局部配置設定緩沖區來自于Ros Alloc Space或者Bump Pointer Space，這取決于目前使用的GC是Mark-Sweep GC還是Compacting GC。
從這裡就可以看到，來自于Ros Alloc Space和Bump Pointer Space的ART運作時線程局部分緩沖區分别是通過調用RosAllocSpace類和BumpPointerSpace類的成員函數RevokeAllThreadLocalBuffers來回收的。
RosAllocSpace類的成員函數RevokeAllThreadLocalBuffers的實作如下所示：
void RosAllocSpace::RevokeAllThreadLocalBuffers() {
rosalloc_->RevokeAllThreadLocalRuns();
}
這個函數定義在檔案art/runtime/gc/space/rosalloc_space.cc中。
RosAllocSpace類的成員變量rosalloc_指向的是一個RosAlloc對象，是以RosAllocSpace類的成員函數RevokeAllThreadLocalBuffers通過調用RosAlloc類的成員函數RevokeAllThreadLocalRuns來回收ART運作時線程局部分緩沖區，後者的實作如下所示：
void RosAlloc::RevokeAllThreadLocalRuns() {
// This is called when a mutator thread won't allocate such as at
// the Zygote creation time or during the GC pause.
MutexLock mu(Thread::Current(), *Locks::runtime_shutdown_lock_);
MutexLock mu2(Thread::Current(), *Locks::thread_list_lock_);
std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList();
for (Thread* thread : thread_list) {
RevokeThreadLocalRuns(thread);
}
RevokeThreadUnsafeCurrentRuns();
}
這個函數定義在檔案art/runtime/gc/allocator/rosalloc.cc中。
RosAlloc類的成員函數RevokeAllThreadLocalRuns首先是獲得ART運作時線程清單，然後再調用另外一個成員函數RevokeThreadLocalRuns對每一個ART運作時線程的局配置設定緩沖區進行回收。
從前面ART運作時Compacting GC為新建立對象配置設定記憶體的過程分析一文可以知道，所有index值小于kNumThreadLocalSizeBrackets的Run都是線程局部的，但是它們不一定是儲存在各個線程的一塊局部儲存中，也有可能是儲存在RosAlloc類的成員變量current_runs_描述的一個Run數組中。這取決于在Ros Alloc Space中配置設定記憶體時是否是線程安全的。這兩種類型的Run分别通過RosAlloc類的成員函數RevokeThreadLocalRuns和RevokeThreadUnsafeCurrentRuns來回收。
RosAlloc類的成員函數RevokeThreadLocalRuns的實作如下所示：
void RosAlloc::RevokeThreadLocalRuns(Thread* thread) {
Thread* self = Thread::Current();
// Avoid race conditions on the bulk free bit maps with BulkFree() (GC).
ReaderMutexLock wmu(self, bulk_free_lock_);
for (size_t idx = 0; idx < kNumThreadLocalSizeBrackets; idx++) {
MutexLock mu(self, *size_bracket_locks_[idx]);
Run* thread_local_run = reinterpret_cast<Run*>(thread->GetRosAllocRun(idx));
......
if (thread_local_run != dedicated_full_run_) {
thread->SetRosAllocRun(idx, dedicated_full_run_);
......
// Note the thread local run may not be full here.
bool dont_care;
thread_local_run->MergeThreadLocalFreeBitMapToAllocBitMap(&dont_care);
thread_local_run->SetIsThreadLocal(false);
thread_local_run->MergeBulkFreeBitMapIntoAllocBitMap();
......
RevokeRun(self, idx, thread_local_run);
}
}
}
這個函數定義在檔案art/runtime/gc/allocator/rosalloc.cc中。
從這裡就可以看到，所有index值小于kNumThreadLocalSizeBrackets的Run都會通過調用Thread類的成員函數GetRosAllocRun從參數thread描述的線程取出來，并且使用RosAlloc類的成員變量dedicated_full_run_描述的一個占坑用的Run替代它。我們在前面ART運作時Compacting GC為新建立對象配置設定記憶體的過程分析一文中提到，RosAlloc類的成員變量dedicated_full_run_是不能夠配置設定Slot的，也就是不可能從中配置設定得到記憶體的。是以，上述的替換操作實際上就相當于是完成了回收參數thread描述的線程的局部配置設定緩沖區的操作。
從Thread類的成員函數GetRosAllocRun取回來的Run在真正被回收之前，還需要進行三個處理。
第一個處理是将其Thread Local Free Bit Map的資料合并到Alloc Bit Map中去。當我們從RosAlloc中釋放一個對象時，如果這個對象所屬于的Run是一個線程局部Run，那麼隻會将該Run的Thread Local Free Bit Map的對應位設定為1，這樣可以避免去操作Alloc Bit Map，因為操作後者是需要加鎖的。現在既然這個Run要被回收了，那麼就是時候将它的Thread Local Free Bit Map的資訊轉移到Alloc Bit Map去了。這是通過調用Run類的成員函數MergeThreadLocalFreeBitMapToAllocBitMap實作的。
第二個處理是調用Run類的成員函數SetIsThreadLocal将即将要被回收的Run設定為是非線程局部的。
第三個處理是将其Bulk Free Bit Map的資料合并到Alloc Bit Map中去。當我們從RosAlloc中釋放一個對象時，如果這個對象所屬于的Run是一個非線程局部Run，那麼隻會将該Run的Bulk Free Bit Map的對應位設定為1，這樣同樣是為了避免加鎖操作Alloc Bit Map。理論上說，我們現在處理的Run是一個線程局部Run，是以它的Bulk Free Bit Map不會被操作。不過這裡似乎是為了安全起見，也會調用Run類的成員函數MergeBulkFreeBitMapIntoAllocBitMap嘗試将Bulk Free Bit Map的資訊轉移到Alloc Bit Map去。
完成了前面的三個處理之後，最後就可以調用RosAlloc類的成員函數RevokeRun執真正的回收工作了，如下所示：
void RosAlloc::RevokeRun(Thread* self, size_t idx, Run* run) {
......
if (run->IsFull()) {
if (kIsDebugBuild) {
full_runs_[idx].insert(run);
......
}
} else if (run->IsAllFree()) {
run->ZeroHeader();
MutexLock mu(self, lock_);
FreePages(self, run, true);
} else {
non_full_runs_[idx].insert(run);
......
}
}
這個函數定義在檔案art/runtime/gc/allocator/rosalloc.cc中。
如果被回收的Run的所有Slot都已經配置設定出去，那麼在Debug版本中，這個Run會被儲存在RosAlloc類的成員變量full_runs_描述的一個數組中。另一方面，如果是在非Debug版本中，就什麼也不用做。注意，在後一種情況下，盡管我們沒有将要被回收的Run儲存在任何一個地方，但是這不會導緻被回收的Run丢失，因為當我們釋放一個對象，會根據這個對象的位址找到它所在的頁，然後再根據頁标志重新找到它所在的Run。這一點可以參考RosAlloc類的成員函數BulkFree的實作。
如果被回收的Run的所有Slot都是空閑的，那麼就可以調用RosAlloc類的成員函數FreePages将它所占據的記憶體頁封裝成一個FreePageRun儲存RosAlloc類的成員變量free_page_runs_描述的一個set中去，以便後面可以對它們進行重複利用。
如果被回收的Run隻是有部分Slot是已經配置設定的，那麼就将它儲存在RosAlloc類的成員變量non_full_runs_描述的一個數組中，以及後面配置設定一個新的Run時，可以直接從該數組獲得。
回到RosAlloc類的成員函數RevokeAllThreadLocalRuns中，處理完成位于ART運作時線程的局部儲存的Run之後，接下來再調用成員函數RevokeThreadUnsafeCurrentRuns處理位于成員變量current_runs_的index值小于kNumThreadLocalSizeBrackets的Run，如下所示：
void RosAlloc::RevokeThreadUnsafeCurrentRuns() {
// Revoke the current runs which share the same idx as thread local runs.
Thread* self = Thread::Current();
for (size_t idx = 0; idx < kNumThreadLocalSizeBrackets; ++idx) {
MutexLock mu(self, *size_bracket_locks_[idx]);
if (current_runs_[idx] != dedicated_full_run_) {
RevokeRun(self, idx, current_runs_[idx]);
current_runs_[idx] = dedicated_full_run_;
}
}
}
這個函數定義在檔案art/runtime/gc/allocator/rosalloc.cc中。
對位于RosAlloc類的成員變量current_runs_的index值小于kNumThreadLocalSizeBrackets的Run的回收同樣是通過調用成員函數RevokeRun來實作的，不過由于這些Run是非線程局部的，是以在調用成員函數RevokeRun進行回收之前，不需要做一些額外的處理。
這樣，對Ros Alloc Space的線程局部配置設定緩沖區的回收就完成了，回到Heap類的成員函數RevokeAllThreadLocalBuffers中，接下來我們繼續分析BumpPointerSpace類的成員函數RevokeAllThreadLocalBuffers的實作，以便可以了解對Bump Pointer Space的線程局部配置設定緩沖區的回收過程，如下所示：
void BumpPointerSpace::RevokeAllThreadLocalBuffers() {
Thread* self = Thread::Current();
MutexLock mu(self, *Locks::runtime_shutdown_lock_);
MutexLock mu2(self, *Locks::thread_list_lock_);
// TODO: Not do a copy of the thread list?
std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList();
for (Thread* thread : thread_list) {
RevokeThreadLocalBuffers(thread);
}
}
這個函數定義在檔案art/runtime/gc/space/bump_pointer_space.cc中。
BumpPointerSpace類的成員函數RevokeAllThreadLocalBuffers首先是獲得ART運作時線程清單，然後再調用另外一個成員函數RevokeThreadLocalBuffers對每一個ART運作時線程的局配置設定緩沖區進行回收，如下所示：
void BumpPointerSpace::RevokeThreadLocalBuffers(Thread* thread) {
MutexLock mu(Thread::Current(), block_lock_);
RevokeThreadLocalBuffersLocked(thread);
}
這個函數定義在檔案art/runtime/gc/space/bump_pointer_space.cc中。
BumpPointerSpace類的成員函數RevokeThreadLocalBuffers又是通過調用另外一個成員函數RevokeThreadLocalBuffersLocked來回收參數thread描述的ART運作時線程的局部配置設定緩沖區的，後者的實作如下所示：
void BumpPointerSpace::RevokeThreadLocalBuffersLocked(Thread* thread) {
objects_allocated_.FetchAndAddSequentiallyConsistent(thread->GetThreadLocalObjectsAllocated());
bytes_allocated_.FetchAndAddSequentiallyConsistent(thread->GetThreadLocalBytesAllocated());
thread->SetTlab(nullptr, nullptr);
}
這個函數定義在檔案art/runtime/gc/space/bump_pointer_space.cc中。
對Bump Pointer Space來說，線程局部配置設定緩沖區的回收是相當簡單的，首先是将已經從線程局部配置設定緩沖區配置設定的對象數和記憶體位元組數增加到整個Bump Pointer Space的已經配置設定對象數和記憶體位元組數，接着再将線程的線程局部配置設定緩沖區資訊置為空即可，這是通過調用Thread類的成員函數SetTlab來實作的。
這樣，我們就分析完成了ART運作時線程的局部配置設定緩沖區的回收過程，回到SemiSpace類的成員函數MarkingPhase中，我們繼續分析ART運作時線程的局部Allocation Stack的回收過程，即Heap類的成員函數RevokeAllThreadLocalAllocationStacks的實作。
不過在分析Heap類的成員函數RevokeAllThreadLocalAllocationStacks的實作之前，我們先要分要Heap類的成員函數PushOnAllocationStack的實作，以便可以了解ART運作時線程的局部Allocation Stack是如何使用的。
從前面ART運作時Compacting GC為新建立對象配置設定記憶體的過程分析一文可以知道，當我們從ART運作時堆配置設定了一個對象之後，如果目前指定的配置設定器既不是kAllocatorTypeBumpPointer，也不是kAllocatorTypeTLAB，也就是目前使用的GC不是Compacting GC，那麼就調用Heap類的成員函數PushOnAllocationStack将前面已經配置設定得到的對象壓入到Allocation Stack中，以便以後可以執行Sticky GC。
Heap類的成員函數PushOnAllocationStack的實作如下所示：
inline void Heap::PushOnAllocationStack(Thread* self, mirror::Object** obj) {
if (kUseThreadLocalAllocationStack) {
if (UNLIKELY(!self->PushOnThreadLocalAllocationStack(*obj))) {
PushOnThreadLocalAllocationStackWithInternalGC(self, obj);
}
} else if (UNLIKELY(!allocation_stack_->AtomicPushBack(*obj))) {
PushOnAllocationStackWithInternalGC(self, obj);
}
}
這個函數定義在檔案art/runtime/gc/heap-inl.h中。
取決于常量kUseThreadLocalAllocationStack的值，Heap類的成員函數PushOnAllocationStack要麼把新配置設定的對象壓入到目前線程的局部Allocation Stack中，要麼壓入到全局的Allocation Stack中。
當常量kUseThreadLocalAllocationStack的值等于false時，新配置設定的對象壓入到全局Allocation Stack中，即Heap類的成員變量allocation_stack_指向的一個ObjectStack中。如果壓入失敗，就說明全局Allocation Stack已經滿了。是以就需要調用Heap類的成員函數PushOnAllocationStackWithInternalGC執行一次Sticky GC，以便可以将全局Allocation Stack清空再壓入新配置設定的對象。
Heap類的成員函數PushOnAllocationStackWithInternalGC的實作如下所示：
void Heap::PushOnAllocationStackWithInternalGC(Thread* self, mirror::Object** obj) {
// Slow path, the allocation stack push back must have already failed.
DCHECK(!allocation_stack_->AtomicPushBack(*obj));
do {
// TODO: Add handle VerifyObject.
StackHandleScope<1> hs(self);
HandleWrapper<mirror::Object> wrapper(hs.NewHandleWrapper(obj));
// Push our object into the reserve region of the allocaiton stack. This is only required due
// to heap verification requiring that roots are live (either in the live bitmap or in the
// allocation stack).
CHECK(allocation_stack_->AtomicPushBackIgnoreGrowthLimit(*obj));
CollectGarbageInternal(collector::kGcTypeSticky, kGcCauseForAlloc, false);
} while (!allocation_stack_->AtomicPushBack(*obj));
}
這個函數定義在檔案art/runtime/gc/heap.cc中。
從這裡就可以看到，Heap類的成員函數PushOnAllocationStackWithInternalGC先通過調用成員函數CollectGarbageInternal執行一次Sticky GC，然後再嘗試将新配置設定的對象壓入到全局Allocation Stack中。此過程一直重複，直到能夠成功地将新配置設定的對象壓入到全局Allocation Stack為止。注意，由于在GC的根集标記的堆驗證過程中，要求根集對象要麼位于Live Bitmap中，要麼位于全局Allocation Stack中，是以在執行Sticky GC之前，需要強制地将新配置設定的對象壓入（這時候它是一個根集對象）到全局Allocation Stack中，這是通過調用Heap類的成員變量allocation_stack_指向的一個AtomicStack對象的成員函數AtomicPushBackIgnoreGrowthLimit來實作的。
回到Heap類的成員函數PushOnAllocationStack中，當常量kUseThreadLocalAllocationStack的值等于true時，新配置設定的對象壓入到目前線程的部局Allocation Stack中，這是通過調用參數self指向的一個Thread對象的成員函數PushOnThreadLocalAllocationStack實作的，它的實作如下所示：
inline bool Thread::PushOnThreadLocalAllocationStack(mirror::Object* obj) {
......
if (tlsPtr_.thread_local_alloc_stack_top < tlsPtr_.thread_local_alloc_stack_end) {
......
*tlsPtr_.thread_local_alloc_stack_top = obj;
++tlsPtr_.thread_local_alloc_stack_top;
return true;
}
return false;
}
這個函數定義在檔案art/runtime/thread-inl.h中。
目前線程的局部Allocation Stack由Thread類的成員變量tlsPtr指向的一塊類型為tls_ptr_sized_values的局部儲存結構體的成員變量thread_local_alloc_stack_top和thread_local_alloc_stack_end來描述。其中，thread_local_alloc_stack_top描述的是棧頂，而thread_local_alloc_stack_end描述的是棧頂的最大值。
是以，将一個新配置設定對象壓入目前線程的局部Allocation Stack，實際上就是将它的位址儲存在目前線程的局部Allocation Stack的棧頂上，然後再将棧頂增加一個機關。
回到Heap類的成員函數PushOnAllocationStack中，如果新配置設定的對象不能成功壓入到目前線程的部局Allocation Stack中，也說明需要執行一次Sticky GC來清理各線程的局部Allocation Stack，以便可以壓入新配置設定的對象。這是通過調用Heap類的成員函數PushOnThreadLocalAllocationStackWithInternalGC來實作的，如下所示：
void Heap::PushOnThreadLocalAllocationStackWithInternalGC(Thread* self, mirror::Object** obj) {
// Slow path, the allocation stack push back must have already failed.
DCHECK(!self->PushOnThreadLocalAllocationStack(*obj));
mirror::Object** start_address;
mirror::Object** end_address;
while (!allocation_stack_->AtomicBumpBack(kThreadLocalAllocationStackSize, &start_address,
&end_address)) {
// TODO: Add handle VerifyObject.
StackHandleScope<1> hs(self);
HandleWrapper<mirror::Object> wrapper(hs.NewHandleWrapper(obj));
// Push our object into the reserve region of the allocaiton stack. This is only required due
// to heap verification requiring that roots are live (either in the live bitmap or in the
// allocation stack).
CHECK(allocation_stack_->AtomicPushBackIgnoreGrowthLimit(*obj));
// Push into the reserve allocation stack.
CollectGarbageInternal(collector::kGcTypeSticky, kGcCauseForAlloc, false);
}
self->SetThreadLocalAllocationStack(start_address, end_address);
// Retry on the new thread-local allocation stack.
CHECK(self->PushOnThreadLocalAllocationStack(*obj)); // Must succeed.
}
這個函數定義在檔案art/runtime/gc/heap.cc中。
線程局部Allocation Stack使用的記憶體塊實際上來自于全局Allocation Stack。現在由于目前線程的局部Allocation Stack滿了，那麼理論上就需要從全局Allocation Stack中擷取更多的記憶體來增加目前線程的局部Allocation Stack，以便可以成功地壓入新配置設定的對象。
不過，Heap類的成員函數PushOnThreadLocalAllocationStackWithInternalGC并不是通過增加目前線程原來的局部Allocation Stack的大小來滿足壓入新配置設定的對象的需求的，而是嘗試從全局Allocation Stack中給目前線程配置設定另外一塊大小為kThreadLocalAllocationStackSize的新記憶體作為局部Allocation Stack，然後再壓入新配置設定的對象。
從全局Allocation Stack中配置設定一塊新記憶體是通過調用Heap類的成員變量allocation_stack_指向的一個ObjectStack對象的成員函數AtomicBumpBack來實作的。ObjectStack類定義為AtomicStack<mirror::Object*>，是以從全局Allocation Stack中配置設定一塊新記憶體實際上是通過調用AtomicStack類的成員函數AtomicBumpBack來實作的，如下所示：
template <typename T>
class AtomicStack {
public:
......
// Atomically bump the back index by the given number of
// slots. Returns false if we overflowed the stack.
bool AtomicBumpBack(size_t num_slots, T** start_address, T** end_address) {
......
int32_t index;
int32_t new_index;
do {
index = back_index_.LoadRelaxed();
new_index = index + num_slots;
if (UNLIKELY(static_cast<size_t>(new_index) >= growth_limit_)) {
// Stack overflow.
return false;
}
} while (!back_index_.CompareExchangeWeakRelaxed(index, new_index));
*start_address = &begin_[index];
*end_address = &begin_[new_index];
......
return true;
}
......
};
這個函數定義在檔案art/runtime/gc/accounting/atomic_stack.h中。
AtomicStack類的成員變量back_index_描述的是棧頂位置，通過增加它的值即可保留一塊記憶體區域出來作為線程的局部Allocation Stack使用。
回到Heap類的成員函數PushOnThreadLocalAllocationStackWithInternalGC中，如果不能成功從全局Allocation Stack中配置設定一塊新的記憶體作為目前線程的局部Allocation Stack，那麼就隻好調用Heap類的成員函數CollectGarbageInternal執行一次Sticky GC來清理全局Allocation Stack，再重新嘗試從全局Allocation Stack中配置設定一塊新的記憶體了。在執行Sticky GC之前，同樣是先會把新配置設定的對象強制壓入到全局Allocation Stack中。
給目前線程設定一個新的局部Allocation Stack是通過調用Thread類的成員函數SetThreadLocalAllocationStack來實作的，如下所示：
inline void Thread::SetThreadLocalAllocationStack(mirror::Object** start, mirror::Object** end) {
......
tlsPtr_.thread_local_alloc_stack_end = end;
tlsPtr_.thread_local_alloc_stack_top = start;
}
這個函數定義在檔案art/runtime/thread-inl.h中。
有了這些基礎知識之後，回到SemiSpace類的成員函數MarkingPhase中，繼續分析它調用的Heap類的成員函數RevokeAllThreadLocalAllocationStacks的實作了，如下所示：
void Heap::RevokeAllThreadLocalAllocationStacks(Thread* self) {
// This must be called only during the pause.
CHECK(Locks::mutator_lock_->IsExclusiveHeld(self));
MutexLock mu(self, *Locks::runtime_shutdown_lock_);
MutexLock mu2(self, *Locks::thread_list_lock_);
std::list<Thread*> thread_list = Runtime::Current()->GetThreadList()->GetList();
for (Thread* t : thread_list) {
t->RevokeThreadLocalAllocationStack();
}
}
這個函數定義在檔案art/runtime/gc/heap.cc中。
Heap類的成員函數RevokeAllThreadLocalAllocationStacks首先是獲得目前的ART運作時線程清單，然後再通過Thread類的成員函數RevokeThreadLocalAllocationStack回收每一個ART運作時線程的局部Allocation Stack。
Thread類的成員函數RevokeThreadLocalAllocationStack的實作如下所示：
inline void Thread::RevokeThreadLocalAllocationStack() {
......
tlsPtr_.thread_local_alloc_stack_end = nullptr;
tlsPtr_.thread_local_alloc_stack_top = nullptr;
}
這個函數定義在檔案art/runtime/thread-inl.h中。
從這裡就可以看到，回收一個ART運作時線程的局部Allocation Stack，隻需要将它的棧頂指針和最大棧頂指針值設定為nullptr即可。
了解了ART運作時線程的局部配置設定緩沖和局部Allocation Stack的回收過程之後，接下來我們繼續分析SemiSpace類的成員函數BindBitmaps的實作，它是用來确定哪些Space需要進行GC，哪些Space不需要進行GC的，如下所示：
void SemiSpace::BindBitmaps() {
TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
WriterMutexLock mu(self_, *Locks::heap_bitmap_lock_);
// Mark all of the spaces we never collect as immune.
for (const auto& space : GetHeap()->GetContinuousSpaces()) {
if (space->GetGcRetentionPolicy() == space::kGcRetentionPolicyNeverCollect ||
space->GetGcRetentionPolicy() == space::kGcRetentionPolicyFullCollect) {
CHECK(immune_region_.AddContinuousSpace(space)) << "Failed to add space " << *space;
} else if (space->GetLiveBitmap() != nullptr) {
if (space == to_space_ || collect_from_space_only_) {
if (collect_from_space_only_) {
// Bind the bitmaps of the main free list space and the non-moving space we are doing a
// bump pointer space only collection.
CHECK(space == GetHeap()->GetPrimaryFreeListSpace() ||
space == GetHeap()->GetNonMovingSpace());
}
CHECK(space->IsContinuousMemMapAllocSpace());
space->AsContinuousMemMapAllocSpace()->BindLiveToMarkBitmap();
}
}
}
if (collect_from_space_only_) {
// We won't collect the large object space if a bump pointer space only collection.
is_large_object_space_immune_ = true;
}
}
這個函數定義在檔案art/runtime/gc/collector/semi_space.cc中。
Semi-Space GC和Generational Semi-Space GC隻涉及到Image Space、Zygote Space、Non Moving Space和Bump Pointer Space四種Continuous Space，它們的回收政策分别為kGcRetentionPolicyNeverCollect、kGcRetentionPolicyFullCollect、kGcRetentionPolicyAlwaysCollect和kGcRetentionPolicyAlwaysCollect。由此可見，在Semi-Space GC和Generational Semi-Space GC中，Image Space和Zygote Space都是不需要進行GC處理的，方法是将它們增加到SemiSpace類的成員變量immune_region_描述的一個無需要進行垃圾回收的區域去。
從前面ART運作時Compacting GC堆建立過程分析一文可以知道，Non Moving Space是一種Ros Alloc Space或者Dl Malloc Space，它是具有Live Bitmap的。然而，Bump Pointer Space是不具有Live Bitmap的，是以，在Semi-Space GC和Generational Semi-Space GC中，如果指定了僅僅隻處理From Space，即SemiSpace類的成員變量collect_from_space_only_等于true，那麼Non Moving Space也是不需要進行GC處理的，方法是将它的Mark Bitmap指向Live Bitmap，
此外，理論上說，Semi-Space GC和Generational Semi-Space GC的To Space隻可能是一個Bump Pointer Space，由于Bump Pointer Space不具有Live Bitmap的，是以SemiSpace類的成員函數BindBitmaps是不需要對它進行特殊處理的。但是從前面ART運作時Compacting GC為新建立對象配置設定記憶體的過程分析一文可以知道，在對Main Space執行同構空間壓縮時，也是通過執行一次Semi-Space GC和Generational Semi-Space GC來執行的。在這種情況下，To Space是一個Main Backup Space，它是具有Live Bitmap的。但是，在Semi-Space GC和Generational Semi-Space GC中，是不允許對To Space進行GC處理的。是以，當SemiSpace類的成員函數BindBitmaps當現一個Space既具有Live Bitmap，又是作為To Space時，也需要将它的Mark Bitmap指向Live Bitmap。
最後，Semi-Space GC和Generational Semi-Space GC還涉及一個Large Object Space。如果指定了僅僅隻處理From Space，即SemiSpace類的成員變量collect_from_space_only_等于true，那麼也是不需要對Large Object Space進行GC處理的。這裡通過将SemiSpace類的成員變量is_large_object_space_immune_設定為true表明不要對Large Object Space進行GC處理。
現在，準備工作已經完成，接下來我們就繼續分析SemiSpace類的成員函數MarkRoots和MarkReachableObjects，以及了解Semi-Space GC和Generational Semi-Space GC的核心執行過程，也就是将From Space拷貝到To Space或者Promote Space的過程。
SemiSpace類的成員函數MarkRoots的實作如下所示：
void SemiSpace::MarkRoots() {
TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
Runtime::Current()->VisitRoots(MarkRootCallback, this);
}
這個函數定義在檔案art/runtime/gc/collector/semi_space.cc。
SemiSpace類的成員函數MarkRoots通過調用Runtime類的成員函數VisitRoots來周遊根集對象，具體可以參考前面ART運作時垃圾收集（GC）過程分析一文，對于每一個根集對象，都會調用SemiSpace類的靜态成員函數MarkRootCallback進行處理。
SemiSpace類的靜态成員函數MarkRootCallback的實作如下所示：
void SemiSpace::MarkRootCallback(Object** root, void* arg, uint32_t /*thread_id*/,
RootType /*root_type*/) {
auto ref = StackReference<mirror::Object>::FromMirrorPtr(*root);
reinterpret_cast<SemiSpace*>(arg)->MarkObject(&ref);
if (*root != ref.AsMirrorPtr()) {
*root = ref.AsMirrorPtr();
}
}
這個函數定義在檔案art/runtime/gc/collector/semi_space.cc。
在前面ART運作時Compacting GC簡要介紹和學習計劃一文中，我們已經分析過SemiSpace類的靜态成員函數MarkRootCallback的實作了，是以這裡不再詳述。
SemiSpace類的靜态成員函數MarkRootCallback調用了另外一個成員函數MarkObject來處理根集對象root，它的實作如下所示：
template<bool kPoisonReferences>
inline void SemiSpace::MarkObject(
mirror::ObjectReference<kPoisonReferences, mirror::Object>* obj_ptr) {
mirror::Object* obj = obj_ptr->AsMirrorPtr();
if (obj == nullptr) {
return;
}
if (kUseBakerOrBrooksReadBarrier) {
// Verify all the objects have the correct forward pointer installed.
obj->AssertReadBarrierPointer();
}
if (from_space_->HasAddress(obj)) {
mirror::Object* forward_address = GetForwardingAddressInFromSpace(obj);
// If the object has already been moved, return the new forward address.
if (UNLIKELY(forward_address == nullptr)) {
forward_address = MarkNonForwardedObject(obj);
DCHECK(forward_address != nullptr);
// Make sure to only update the forwarding address AFTER you copy the object so that the
// monitor word doesn't Get stomped over.
obj->SetLockWord(
LockWord::FromForwardingAddress(reinterpret_cast<size_t>(forward_address)), false);
// Push the object onto the mark stack for later processing.
MarkStackPush(forward_address);
}
obj_ptr->Assign(forward_address);
} else if (!collect_from_space_only_ && !immune_region_.ContainsObject(obj)) {
BitmapSetSlowPathVisitor visitor(this);
if (!mark_bitmap_->Set(obj, visitor)) {
// This object was not previously marked.
MarkStackPush(obj);
}
}
}
這個函數定義在檔案art/runtime/gc/collector/semi_space-inl.h中。
在前面ART運作時Compacting GC簡要介紹和學習計劃一文中，我們已經分析過SemiSpace類的成員函數MarkObject的實作了，是以這裡不再詳述。我們重點是分析這裡調用到的SemiSpace類的另外一個成員函數MarkNonForwardedObject的實作，它涉及到對象的移動過程，如下所示：
mirror::Object* SemiSpace::MarkNonForwardedObject(mirror::Object* obj) {
const size_t object_size = obj->SizeOf();
size_t bytes_allocated;
mirror::Object* forward_address = nullptr;
if (generational_ && reinterpret_cast<byte*>(obj) < last_gc_to_space_end_) {
// If it's allocated before the last GC (older), move
// (pseudo-promote) it to the main free list space (as sort
// of an old generation.)
forward_address = promo_dest_space_->AllocThreadUnsafe(self_, object_size, &bytes_allocated,
nullptr);
if (UNLIKELY(forward_address == nullptr)) {
// If out of space, fall back to the to-space.
forward_address = to_space_->AllocThreadUnsafe(self_, object_size, &bytes_allocated, nullptr);
......
} else {
bytes_promoted_ += bytes_allocated;
......
// Handle the bitmaps marking.
accounting::ContinuousSpaceBitmap* live_bitmap = promo_dest_space_->GetLiveBitmap();
......
accounting::ContinuousSpaceBitmap* mark_bitmap = promo_dest_space_->GetMarkBitmap();
.....
if (collect_from_space_only_) {
......
// If a bump pointer space only collection, delay the live
// bitmap marking of the promoted object until it's popped off
// the mark stack (ProcessMarkStack()). The rationale: we may
// be in the middle of scanning the objects in the promo
// destination space for
// non-moving-space-to-bump-pointer-space references by
// iterating over the marked bits of the live bitmap
// (MarkReachableObjects()). If we don't delay it (and instead
// mark the promoted object here), the above promo destination
// space scan could encounter the just-promoted object and
// forward the references in the promoted object's fields even
// through it is pushed onto the mark stack. If this happens,
// the promoted object would be in an inconsistent state, that
// is, it's on the mark stack (gray) but its fields are
// already forwarded (black), which would cause a
// DCHECK(!to_space_->HasAddress(obj)) failure below.
} else {
// Mark forward_address on the live bit map.
live_bitmap->Set(forward_address);
// Mark forward_address on the mark bit map.
......
mark_bitmap->Set(forward_address);
}
}
} else {
// If it's allocated after the last GC (younger), copy it to the to-space.
forward_address = to_space_->AllocThreadUnsafe(self_, object_size, &bytes_allocated, nullptr);
if (forward_address != nullptr && to_space_live_bitmap_ != nullptr) {
to_space_live_bitmap_->Set(forward_address);
}
}
// If it's still null, attempt to use the fallback space.
if (UNLIKELY(forward_address == nullptr)) {
forward_address = fallback_space_->AllocThreadUnsafe(self_, object_size, &bytes_allocated,
nullptr);
......
accounting::ContinuousSpaceBitmap* bitmap = fallback_space_->GetLiveBitmap();
if (bitmap != nullptr) {
bitmap->Set(forward_address);
}
}
++objects_moved_;
bytes_moved_ += bytes_allocated;
// Copy over the object and add it to the mark stack since we still need to update its
// references.
saved_bytes_ +=
CopyAvoidingDirtyingPages(reinterpret_cast<void*>(forward_address), obj, object_size);
......
return forward_address;
}
這個函數定義在檔案art/runtime/gc/collector/semi_space.cc中。
參數obj就是即将要被移動的對象。它要被移動到哪裡去呢？有三個可能的地方，分别是Promote Space、To Space和Fallback Space。前面提到，對于Generational Semi-Space GC來說，Promote Space和Fallback Space實際上都是ART運作堆的Main Space。但是對于Semi-Space GC來說，沒有Promote Space，并且Fallback Space是ART運作時堆的Non Moving Space。
要将對象obj移動至Promote Space，需要滿足兩個條件。第一個條件是目前執行的是Generational Semi-Space GC，即SemiSpace類的成員變量generational_的值等于true。第二個條件是對象obj是一個老生代對象，也就是它必須要是上一次Generational Semi-Space GC執行過後才配置設定的。前面我們提到，SemiSpace類的成員變量last_gc_to_space_end_記錄的是上一次Generational Semi-Space GC執行過後，已配置設定對象在From Space（上一次Generational Semi-Space GC的To Space）占據的最大記憶體位址值。是以，隻要對象obj的位址值大于SemiSpace類的成員變量last_gc_to_space_end_的值，我們就可以認為它是一個老生代對象。
為了能夠将對象obj移動至Promote Space，我們首先需要在Promote Space中配置設定一塊與對象obj相同大小的記憶體，這是通過調用SemiSpace類的成員變量promo_dest_space_指向的一個ContinuousMemMapAllocSpace對象的成員函數AllocThreadUnsafe來實作的。但是有可能Promote Space已經滿了，不能滿足請求配置設定的記憶體。在這種情況下，就需要退回來在To Space進行申請。這意味着要将對象obj移動到To Space中去。
由于對象obj已經确定是一個在目前GC中存活的對象，是以當我們将它移動至另外一個Space時，需要将該Space的Live Bitmap的對應位設定為1。但是有一種特殊情況，就是目前執行的Generational Semi-Space GC決定僅僅對From Space進行GC處理。在這種情況下，後面在調用Heap類的成員函數MarkReachableObjects處理可達對象時，需要處理Promote Space對From Space的引用情況。這通常是通過Dirty Card來處理的。記住，當GC不是處理所有的Space的時候，所有存活的對象包括：
1. 位于需要處理的Space上的根集對象；
2. Dirty Card記錄的位于不需要處理的Space的對象對需要處理的Space上的對象的引用；
3. 上述兩種對象可達的位于需要處理的Space上的對象。
另外，在不使用Dirty Card的情況下，也有可能采用一種方法來确定上述第2種對象可達的對象，即通過周遊位于不需要處理的Space的Live Bitmap來确有哪此對象引用了需要處理的Space的對象。
如果目前執行的Generational Semi-Space GC決定僅僅對From Space進行GC處理，那麼就符合GC不是處理所有的Space的條件。在這種情況下，需要處理的Space就是From Space，而Promote Space就是不需要處理的Space。現在我們從Promote Space配置設定了一個新的對象，作為對象obj移動後的新對象，如果我們将它在Promote Space的Live Bitmap對應的位設定為1，那麼就會導緻在不使用Dirty Card的情況下，後面在調用Heap類的成員函數MarkReachableObjects處理可達對象時，會對該被移動對象obj進行處理。這樣做是不合理的，因為目前函數執行完畢，移動後的對象obj已經被壓入到Mark Stack中。壓入到Mark Stack的對象稱為Gray對象，意味着它們的引用還沒有被處理。但是在調用Heap類的成員函數MarkReachableObjects處理可達對象時，執行的操作就是處理對象的引用情況。這些引用已經被處理過的對象稱為Black對象。一個對象不可能同時作為Gray對象和Black對象存在，是以，針對這種情況，就會延遲設定被移動對象obj在Promote Space的Live Bitmap的對應位。那麼延遲到什麼時候呢？很自然地，就是延遲到Heap類的成員函數MarkReachableObjects處理完成位于不需要處理的Space的對象對位于需要處理的Space的對象的引用之後，最合适的地方就是SemiSpace類的成員函數ProcessMarkStack。後面我們将會看到相關的代碼實作。
另一方面，如果目前執行的Generational Semi-Space GC決定不僅僅是對From Space進行GC處理，也就是說也會對Promote Space也進行GC處理，這樣後面調用Heap類的成員函數MarkReachableObjects處理可達對象時，就不會涉及到Promote Space。是以，這時候就要将被移動對象在Promote Space的Live Bitmap上對應的位設定為1。同時，也會将對應的Mark Bitmap位設定為1，以表示該對象在目前Generational Semi-Space GC執行過後，仍然是存活的。
在不滿足将對象obj移動至Promote Space的條件下，接下來需要考慮的就是将對象obj移動至To Space中。于是，在這種情況下，就在To Space中配置設定一塊與對象obj相同大小的記憶體塊。由于To Space在接下來調用Heap類的成員函數MarkReachableObjects處理可達對象時不是需要處理的，是以這裡就可以将被移動對象obj在To Space的Live Bitmap的對應位設定為1。注意，前面提到，To Space有可能是一個Bump Pointer Space，也有可能是一個Main Backup Space。由于Bump Pointer Space是沒有Live Bitmap的，是以在設定被移動對象obj在To Space的Live Bitmap的對應位時，需要先判斷Live Bitmap存不存在。
最後，如果不能成功地從To Space配置設定到一塊用于移動對象obj的記憶體，那麼就隻好将對象obj移動到Fallback Space中去了。于是，在這種情況下，就在Fallback Space中配置設定一塊與對象obj相同大小的記憶體塊，并且在Fallback Space存在Live Bitmap的情況下，将移動對象obj在Fallback Space的Live Bitmap的對應位設定為1。
從目标Space中配置設定到與對象obj相同大小的記憶體塊之後，接下來要做的就是将對象obj拷貝到該塊記憶體去了，這是通過調用SemiSpace類的成員函數CopyAvoidingDirtyingPages來實作的，如下所示：
static inline size_t CopyAvoidingDirtyingPages(void* dest, const void* src, size_t size) {
if (LIKELY(size <= static_cast<size_t>(kPageSize))) {
// We will dirty the current page and somewhere in the middle of the next page. This means
// that the next object copied will also dirty that page.
// TODO: Worth considering the last object copied? We may end up dirtying one page which is
// not necessary per GC.
memcpy(dest, src, size);
return 0;
}
size_t saved_bytes = 0;
byte* byte_dest = reinterpret_cast<byte*>(dest);
......
// Process the start of the page. The page must already be dirty, don't bother with checking.
const byte* byte_src = reinterpret_cast<const byte*>(src);
const byte* limit = byte_src + size;
size_t page_remain = AlignUp(byte_dest, kPageSize) - byte_dest;
// Copy the bytes until the start of the next page.
memcpy(dest, src, page_remain);
byte_src += page_remain;
byte_dest += page_remain;
DCHECK_ALIGNED(reinterpret_cast<uintptr_t>(byte_dest), kPageSize);
DCHECK_ALIGNED(reinterpret_cast<uintptr_t>(byte_dest), sizeof(uintptr_t));
DCHECK_ALIGNED(reinterpret_cast<uintptr_t>(byte_src), sizeof(uintptr_t));
while (byte_src + kPageSize < limit) {
bool all_zero = true;
uintptr_t* word_dest = reinterpret_cast<uintptr_t*>(byte_dest);
const uintptr_t* word_src = reinterpret_cast<const uintptr_t*>(byte_src);
for (size_t i = 0; i < kPageSize / sizeof(*word_src); ++i) {
// Assumes the destination of the copy is all zeros.
if (word_src[i] != 0) {
all_zero = false;
word_dest[i] = word_src[i];
}
}
if (all_zero) {
// Avoided copying into the page since it was all zeros.
saved_bytes += kPageSize;
}
byte_src += kPageSize;
byte_dest += kPageSize;
}
// Handle the part of the page at the end.
memcpy(byte_dest, byte_src, limit - byte_src);
return saved_bytes;
}
這個函數定義在檔案art/runtime/gc/collector/semi_space.cc中。
SemiSpace類的成員函數CopyAvoidingDirtyingPages不是簡單地調用記憶體拷貝函數memcpy一塊記憶體從source拷貝到destination中，因為這樣會導緻destination對應的記憶體頁在核心中被标記為dirty，這樣的話就會增加核心對它的各種記憶體管理。這裡我們是将對象從From Space拷貝到To Space。這裡的To Space即為上次GC時的From Space。前面分析SemiSpace類的成員函數MarkingPhase提到，上次GC執行到最後，會将From Space的内容清零。是以，這裡在拷貝記憶體的過程中，就可以做一個優化，對于source中記憶體等于0的塊，可以不對destination對應的記憶體塊執行拷貝操作，這樣就可以避免它在核心中被标記為dirty。
在具體執行過程中，是按記憶體頁進行的。也就是說，對于要拷貝的内容中前後不是按記憶體頁對齊的記憶體塊，直接調用記憶體拷貝函數memcpy進行拷貝。而對于中間按記憶體頁對齊的部分記憶體，就按照word來依次檢查source中的值是否等于0。隻有在不等于0的情況下，才會将其拷貝到destination中。
這樣，根集對象的處理過程就執行完成了，接下來需要繼續調用Heap類的成員函數MarkReachableObjects處理可達對象，它的實作如下所示：
void SemiSpace::MarkReachableObjects() {
TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
{
TimingLogger::ScopedTiming t2("MarkStackAsLive", GetTimings());
accounting::ObjectStack* live_stack = heap_->GetLiveStack();
heap_->MarkAllocStackAsLive(live_stack);
live_stack->Reset();
}
for (auto& space : heap_->GetContinuousSpaces()) {
// If the space is immune then we need to mark the references to other spaces.
accounting::ModUnionTable* table = heap_->FindModUnionTableFromSpace(space);
if (table != nullptr) {
// TODO: Improve naming.
TimingLogger::ScopedTiming t2(
space->IsZygoteSpace() ? "UpdateAndMarkZygoteModUnionTable" :
"UpdateAndMarkImageModUnionTable",
GetTimings());
table->UpdateAndMarkReferences(MarkHeapReferenceCallback, this);
......
} else if (collect_from_space_only_ && space->GetLiveBitmap() != nullptr) {
// If the space has no mod union table (the non-moving space and main spaces when the bump
// pointer space only collection is enabled,) then we need to scan its live bitmap or dirty
// cards as roots (including the objects on the live stack which have just marked in the live
// bitmap above in MarkAllocStackAsLive().)
......
accounting::RememberedSet* rem_set = GetHeap()->FindRememberedSetFromSpace(space);
......
if (rem_set != nullptr) {
TimingLogger::ScopedTiming t2("UpdateAndMarkRememberedSet", GetTimings());
rem_set->UpdateAndMarkReferences(MarkHeapReferenceCallback, DelayReferenceReferentCallback,
from_space_, this);
......
} else {
TimingLogger::ScopedTiming t2("VisitLiveBits", GetTimings());
accounting::ContinuousSpaceBitmap* live_bitmap = space->GetLiveBitmap();
SemiSpaceScanObjectVisitor visitor(this);
live_bitmap->VisitMarkedRange(reinterpret_cast<uintptr_t>(space->Begin()),
reinterpret_cast<uintptr_t>(space->End()),
visitor);
}
}
}
CHECK_EQ(is_large_object_space_immune_, collect_from_space_only_);
if (is_large_object_space_immune_) {
TimingLogger::ScopedTiming t("VisitLargeObjects", GetTimings());
......
// Delay copying the live set to the marked set until here from
// BindBitmaps() as the large objects on the allocation stack may
// be newly added to the live set above in MarkAllocStackAsLive().
GetHeap()->GetLargeObjectsSpace()->CopyLiveToMarked();
// When the large object space is immune, we need to scan the
// large object space as roots as they contain references to their
// classes (primitive array classes) that could move though they
// don't contain any other references.
space::LargeObjectSpace* large_object_space = GetHeap()->GetLargeObjectsSpace();
accounting::LargeObjectBitmap* large_live_bitmap = large_object_space->GetLiveBitmap();
SemiSpaceScanObjectVisitor visitor(this);
large_live_bitmap->VisitMarkedRange(reinterpret_cast<uintptr_t>(large_object_space->Begin()),
reinterpret_cast<uintptr_t>(large_object_space->End()),
visitor);
}
// Recursively process the mark stack.
ProcessMarkStack();
}
這個函數定義在檔案art/runtime/gc/collector/semi_space.cc中。
前面提到，Heap類的成員函數MarkReachableObjects除了需要處理根集對象可達的對象之外，還需要處理Dirty Card可達對象。如果沒有使用Dirty Card，那麼就需要通過Live Bitmap來處理。從前面ART運作時Compacting GC為新建立對象配置設定記憶體的過程分析一文可以知道，當我們從ART運作時堆配置設定一個新的對象時，并不會馬上就将其對應的Live Bitmap對應的位設定為1，而隻是将其壓入到Allocation Stack中。這是因為Live Bitmap隻有在執行GC的過程中才會真正使用到，是以就可以延遲執行這一操作。現在就是位于執行GC的過程中，并且要使用到Live Bitmap中，是以就需要把儲存在Allocation Stack中的對象在其對應的Space的Live Bitmap的對應位設定為1。這是通過調用Heap類的成員函數MarkAllocStackAsLive實作的。注意，在前面分析的Heap類的成員函數MarkingPhase中，已經将ART運作時的Allocation Stack與Live Stack進行交換過了，是以這裡是針對Live Stack進行處理。
Heap類的成員函數MarkAllocStackAsLive的實作如下所示：
void Heap::MarkAllocStackAsLive(accounting::ObjectStack* stack) {
space::ContinuousSpace* space1 = main_space_ != nullptr ? main_space_ : non_moving_space_;
space::ContinuousSpace* space2 = non_moving_space_;
......
MarkAllocStack(space1->GetLiveBitmap(), space2->GetLiveBitmap(),
large_object_space_->GetLiveBitmap(), stack);
}
這個函數定義在檔案art/runtime/gc/heap.cc中。
在ART運作時堆中，從前面ART運作時Compacting GC為新建立對象配置設定記憶體的過程分析一文可以知道，儲存在Allocation Stack中的對象有可能是從Main Space、Non Moving Space或者Large Object Space中配置設定的。也就是說，Heap類的成員函數MarkAllocStackAsLive需要獲得這三個Space的Live Bitmap，以便可以設定儲存在Allocation Stack的對象的Live Bitmap對應位。
由于Main Space是不一定存在的，例如，目前GC為Compacting GC時，就沒有Main Space，這時候使用Non Moving Space的Live Bitmap來代替Main Space的Live Bitmap。有了上述三個Live Bitmap之後，接下來就調用Heap類的成員函數MarkAllocStack來标記儲存在Allocation Stack的對象的Live Bitmap位。
Heap類的成員函數MarkAllocStack的實作如下所示：
void Heap::MarkAllocStack(accounting::ContinuousSpaceBitmap* bitmap1,
accounting::ContinuousSpaceBitmap* bitmap2,
accounting::LargeObjectBitmap* large_objects,
accounting::ObjectStack* stack) {
DCHECK(bitmap1 != nullptr);
DCHECK(bitmap2 != nullptr);
mirror::Object** limit = stack->End();
for (mirror::Object** it = stack->Begin(); it != limit; ++it) {
const mirror::Object* obj = *it;
if (!kUseThreadLocalAllocationStack || obj != nullptr) {
if (bitmap1->HasAddress(obj)) {
bitmap1->Set(obj);
} else if (bitmap2->HasAddress(obj)) {
bitmap2->Set(obj);
} else {
large_objects->Set(obj);
}
}
}
}
這個函數定義在檔案art/runtime/gc/heap.cc中。
Heap類的成員函數MarkAllocStack的實作很簡單，它依次周遊儲存在Allocation Stack的每一個對象，并且判斷這些對象是位于哪個Live Bitmap中，就将哪個Live Bitmap的對應位設定為1。
這樣，ART運作時的Allocation Stack就處理完畢，回到SemiSpace類的成員函數MarkReachableObjects中，接下來開始處理那些不需要進行GC處理的Space對那些需要進行GC處理的Space的引用。要麼通過Dirty Card，要麼通過Live Bitmap來獲得上述的引用關系。通過Dirty Card處理的效率會更高，因為這種方式隻有從上一次GC以來發生過修改的對象的才會進行處理。而通過Live Bitmap處理則不管是不是上一次GC以來發生過修改，隻是存活的對象，都要進行處理。
從大的分類來看，不需要進行GC處理的Space分為Continuous Space和Discontinuous Space兩大類，其中，Discontinuous Space就隻有Large Object Space一種。接下來我們就分别分析這兩類Space的處理過程。
首先看Continuous Space的處理。并不是所有的Continuous Space都是需要處理的。從前面分析的SemiSpace類的成員函數BindBitmap可以知道，Image Space和Zygote Space是必須要進行處理的。在SemiSpace類的成員變量collect_from_space_only_等于true的情況下，Non Moving Space也是需要在這裡進行處理的。
ART運作時堆的所有Continuous Space可以通過調用Heap類的成員函數GetContinuousSpaces。獲得的Continuous Space同時也包含了Bump Pointer Space。Bump Pointer Space隻有From Space和To Space，它們都是不需要在這裡進行處理的。是以，我們需要從獲得的Continuous Space中過濾掉Bump Pointer Space。幸好，Bump Pointer Space是沒有Live Bitmap的，是以，我們可以通過這一簡單的事實将它們從獲得的Continuous Space中過濾掉。
此外，對于Image Space和Zygote Space來說，它們通過Mod Union Table來記錄它們對其它Space的引用修改情況。對于Non Moving Space來說，它通過Remember Set來記錄它對From Space的引用修改情況。無論Mod Union Table還是Remember Set，它們都是通過Dirty Card來記錄一個Space對另外一個Space的引用修改情況的。但是Non Moving Space也有可能不通過Remember Set來記錄它對From Space的引用修改情況的。這取決于常量collector::SemiSpace::kUseRememberedSet的值。
有了前面這些知識之後，我們就很容易了解Heap類的成員函數MarkReachableObjects對Image Space、Zygote Space和Non Moving Space的處理了：
1. 對于Image Space和Zygote Space，調用與它們關聯的ModUnionTable對象的成員函數UpdateAndMarkReferences處理那些從上次GC以來發生過引用類型的成員變量修改的對象。對于每一個這樣的對象，都調用SemiSpace類的靜态成員函數MarkHeapReferenceCallback對它們進行處理。
2. 對于Non Moving Space，隻有在SemiSpace類的成員變量collect_from_space_only_等于true的情況下，才需要在這裡進行處理。這一點我們在前面的分析中有提及到。如果Non Moving Space關聯有RememberSet對象，那麼就調用它的成員函數UpdateAndMarkReferences處理那些從上次GC以來發生引用類型的成員變量修改，并且這些修改後的成員變量引用了位于From Space的對象的對象。對于每一個這樣的對象，都調用SemiSpace類的靜态成員函數MarkHeapReferenceCallback或者DelayReferenceReferentCallback對它們進行處理。其中，前者用來處理非引用對象，而後者用來處理引用對象。如果Non Moving Space沒有關聯RememberSet對象，那麼就通過它的Live Bitmap來處理它的存活對象對From Space的對象的引用情況，并且是通過SemiSpaceScanObjectVisitor類來處理Non Moving Space的每一個存活對象的。
接着再看對Discontinuous Space的處理，也就是對Large Object Space的處理。前面分析SemiSpace類的成員函數BindBitmaps時提到，當SemiSpace類的成員變量is_large_object_space_immune_等于true的時候，就表示不要對Large Object Space的垃圾對象進行回收。換句話說，在這裡就需要對Large Object Space進行處理，即處理它對From Space的引用情況。這是通過周遊Large Object Space的Live Bitmap進行處理的，對于Large Object Space中的每一個存活對象，都通過SemiSpaceScanObjectVisitor類來處理它對From Space的引用情況。
在處理Large Object Space的時候，還有一點需要注意的是，前面在調用SemiSpace類的成員函數BindBitmaps中，我們隻是通過SemiSpace類的成員變量is_large_object_space_immune_記錄了Large Object Space不需要進行垃圾回收，但是沒有像其它的不需要進行垃圾回收的Space一樣，例如Non Moving Space，将它目前的Live Bitmap拷貝到Mark Bitmap中去。這樣做有兩個原因：
1. 其它的Space，也就是Non Moving Space，将它的Live Bitmap拷貝到Mark Bitmap，實際上隻是讓Mark Bitmap和Live Bitmap指向同一個Bitmap，這個操作沒有執行真正記憶體拷貝操作。
2. 将Large Object Space的Live Bitmap拷貝到Mark Bitmap，是要執行真正的記憶體拷貝操作的，因為Large Object Space和Non Moving Space的Live/Mark Bitmap實作是不一樣的。又由于在執行SemiSpace類的成員函數BindBitmaps的時候，Large Object Space的Live Bitmap還沒有包含那些儲存在Allocation Stack上的對象。是以，這裡為了減少記憶體拷貝的次數，就等到将儲存在Allocation Stack上的并且是在Large Object Space上配置設定的對象在Live Bitmap中的位都設定好之後，再調用LargeObjectSpace類的成員函數CopyLiveToMarked一次性完整地把Live Bitmap拷貝到Mark Bitmap中。
接下來，我們隻分析SemiSpace類的靜态成員函數MarkHeapReferenceCallback的實作，以便可以了解那些位于不需要進行垃圾回收的Space對需要進行垃圾回收的Space的引用情況是如何處理的，它的實作如下所示：
void SemiSpace::MarkHeapReferenceCallback(mirror::HeapReference<mirror::Object>* obj_ptr,
void* arg) {
reinterpret_cast<SemiSpace*>(arg)->MarkObject(obj_ptr);
}
這個函數定義在檔案art/runtime/gc/collector/semi_space.cc中。
從這裡就可以看到，這裡與前面處理根集對象的方式是一樣的，都是通過調用SemiSpace類的成員函數MarkObject來對對象進行标記或者移動的操作的。關于SemiSpace類的靜态成員函數MarkHeapReferenceCallback的被調用過程，還可以參考前面ART運作時Compacting GC簡要介紹和學習計劃一文。
回到Heap類的成員函數MarkReachableObjects中，這時候根集對象，以及Dirty Card引用的對象，均已經被标記和移動，現在就可以調用SemiSpace類的成員函數ProcessMarkStack對它們的可達對象進行遞歸标記和移動了。
SemiSpace類的成員函數ProcessMarkStack的實作如下所示：
void SemiSpace::ProcessMarkStack() {
TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
accounting::ContinuousSpaceBitmap* live_bitmap = nullptr;
if (collect_from_space_only_) {
// If a bump pointer space only collection (and the promotion is
// enabled,) we delay the live-bitmap marking of promoted objects
// from MarkObject() until this function.
live_bitmap = promo_dest_space_->GetLiveBitmap();
DCHECK(live_bitmap != nullptr);
accounting::ContinuousSpaceBitmap* mark_bitmap = promo_dest_space_->GetMarkBitmap();
DCHECK(mark_bitmap != nullptr);
DCHECK_EQ(live_bitmap, mark_bitmap);
}
while (!mark_stack_->IsEmpty()) {
Object* obj = mark_stack_->PopBack();
if (collect_from_space_only_ && promo_dest_space_->HasAddress(obj)) {
// obj has just been promoted. Mark the live bitmap for it,
// which is delayed from MarkObject().
DCHECK(!live_bitmap->Test(obj));
live_bitmap->Set(obj);
}
ScanObject(obj);
}
}
這個函數定義在檔案art/runtime/gc/collector/semi_space.cc中。
之前處理過的根集對象和被Dirty Card引用的對象都被壓入到了SemiSpace類的成員變量mark_stack_描述的一個Mark Stack中，現在通過調用SemiSpace類的成員函數ScanObject即可以對它們的可達對象進行遞歸周遊處理。
這裡我們就還可以看到前面分析SemiSpace類的成員函數MarkNonForwardedObject提到的在僅僅回收From Space的垃圾的情況下，對移動到Promote Space的對象的Live Bitmap位的延遲處理。也就是說，在處理Mark Stack的過程中，如果一個對象位于Promote Space中，那麼就将該對象在Promote Space的Live Bitmap位設定為1。隻有經過這樣的處理之後，後面的垃圾回收階段才能正确處理那些從From Space拷貝到Promote Space的對象。
SemiSpace類的成員函數ScanObject的實作如下所示：
void SemiSpace::ScanObject(Object* obj) {
......
SemiSpaceMarkObjectVisitor visitor(this);
obj->VisitReferences<kMovingClasses>(visitor, visitor);
}
這個函數定義在檔案art/runtime/gc/collector/semi_space.cc中。
SemiSpace類的成員函數ScanObject通過SemiSpaceMarkObjectVisitor類的操作符号重載函數()處理對象obj每一個引用類型的成員變量，如下所示：
class SemiSpaceMarkObjectVisitor {
public:
explicit SemiSpaceMarkObjectVisitor(SemiSpace* collector) : collector_(collector) {
}
void operator()(Object* obj, MemberOffset offset, bool /* is_static */) const ALWAYS_INLINE
EXCLUSIVE_LOCKS_REQUIRED(Locks::mutator_lock_, Locks::heap_bitmap_lock_) {
// Object was already verified when we scanned it.
collector_->MarkObject(obj->GetFieldObjectReferenceAddr<kVerifyNone>(offset));
}
void operator()(mirror::Class* klass, mirror::Reference* ref) const
SHARED_LOCKS_REQUIRED(Locks::mutator_lock_)
EXCLUSIVE_LOCKS_REQUIRED(Locks::heap_bitmap_lock_) {
collector_->DelayReferenceReferent(klass, ref);
}
private:
SemiSpace* const collector_;
};
SemiSpaceMarkObjectVisitor類定義在檔案art/runtime/gc/collector/semi_space.cc中。
取決于成員變量的引用類型，調用不同的版本的操作符号重載函數()。如果成員變量引用的是一個引用對象，即Soft Reference、Weak Reference、Phantom Reference和Finalizer Reference這類對象，那麼就調用SemiSpace類的成員函數DelayReferenceReferent延遲到後面調用SemiSpace類的成員函數ProcessReferences時再處理。如果成員變量引用的是一個普通對象，那麼就調用我們前面已經分析過的SemiSpace類的成員函數MarkObject對它進行标記和移動等處理。
至此，所有的存活對象就都已經标記和移動完畢，接下來就開始執行Semi-Space GC或者Generational Semi-Space GC的回收階段了，這是通過調用SemiSpace類的成員函數ReclaimPhase來實作的，如下所示：
void SemiSpace::ReclaimPhase() {
TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
WriterMutexLock mu(self_, *Locks::heap_bitmap_lock_);
// Reclaim unmarked objects.
Sweep(false);
// Swap the live and mark bitmaps for each space which we modified space. This is an
// optimization that enables us to not clear live bits inside of the sweep. Only swaps unbound
// bitmaps.
SwapBitmaps();
// Unbind the live and mark bitmaps.
GetHeap()->UnBindBitmaps();
.......
if (generational_) {
// Record the end (top) of the to space so we can distinguish
// between objects that were allocated since the last GC and the
// older objects.
last_gc_to_space_end_ = to_space_->End();
}
}
這個函數定義在檔案art/runtime/gc/collector/semi_space.cc中。
SemiSpace類的成員函數ReclaimPhase主要是執行以下四個操作：
1. 調用SemiSpace類的成員函數Sweep回收各個Space的垃圾對象，即那些Mark Bitmap位等于0，但是Live Bitmap位等于1的對象。
2. 調用從父類GarbageCollector繼承下來的成員函數SwapBitmaps交換各個Space的Mark Bitmap和Live Bitmap，以便可以将上次GC以來存活下來的對象記錄在Live Bitmap中。
3. 調用Heap類的成員函數UnBindBitmaps重置各個Space的Mark Bitmap，以便下次GC時可以使用。
4. 對于Generational Semi-Space GC，即在SemiSpace類的成員變量generational_的值等于true的情況下，将目前To Space目前已經配置設定出去的最大記憶體位址值記錄在SemiSpace類的成員變量last_gc_to_space_end_中，以前下次再執行Generational Semi-Space GC時，可以通過該成員變量來區分新生代和老生代對象。
前面三個操作可以參考前面ART運作時垃圾收集（GC）過程分析一文。這裡不再詳細分析。
這樣，Semi-Space GC或者Generational Semi-Space GC的回收階段也執行完成了，最後需要執行的一個階段是結束階段。這是通過調用SemiSpace類的成員函數FinishPhase來實作的，如下所示：
void SemiSpace::FinishPhase() {
TimingLogger::ScopedTiming t(__FUNCTION__, GetTimings());
// Null the "to" and "from" spaces since compacting from one to the other isn't valid until
// further action is done by the heap.
to_space_ = nullptr;
from_space_ = nullptr;
CHECK(mark_stack_->IsEmpty());
mark_stack_->Reset();
if (generational_) {
// Decide whether to do a whole heap collection or a bump pointer
// only space collection at the next collection by updating
// collect_from_space_only_.
if (collect_from_space_only_) {
// Disable collect_from_space_only_ if the bytes promoted since the
// last whole heap collection or the large object bytes
// allocated exceeds a threshold.
bytes_promoted_since_last_whole_heap_collection_ += bytes_promoted_;
bool bytes_promoted_threshold_exceeded =
bytes_promoted_since_last_whole_heap_collection_ >= kBytesPromotedThreshold;
uint64_t current_los_bytes_allocated = GetHeap()->GetLargeObjectsSpace()->GetBytesAllocated();
uint64_t last_los_bytes_allocated =
large_object_bytes_allocated_at_last_whole_heap_collection_;
bool large_object_bytes_threshold_exceeded =
current_los_bytes_allocated >=
last_los_bytes_allocated + kLargeObjectBytesAllocatedThreshold;
if (bytes_promoted_threshold_exceeded || large_object_bytes_threshold_exceeded) {
collect_from_space_only_ = false;
}
} else {
// Reset the counters.
bytes_promoted_since_last_whole_heap_collection_ = bytes_promoted_;
large_object_bytes_allocated_at_last_whole_heap_collection_ =
GetHeap()->GetLargeObjectsSpace()->GetBytesAllocated();
collect_from_space_only_ = true;
}
}
// Clear all of the spaces' mark bitmaps.
WriterMutexLock mu(Thread::Current(), *Locks::heap_bitmap_lock_);
heap_->ClearMarkedObjects();
}
這個函數定義在檔案art/runtime/gc/collector/semi_space.cc中。
SemiSpace類的成員函數FinishPhase主要執行以下四個操作：
1. 将SemiSpace類的成員變量from_space_和to_space_置空。這兩個成員變量在下一次執行Semi-Space GC或者Generational Semi-Space GC時之前，會被重新設定。
2. 将SemiSpace類的成員變量mark_stack_描述的Mark Stack清零。
3. 确定下一次執行Generational Semi-Space GC時，是否隻僅僅回收From Space的垃圾。如果目前執行的Generational Semi-Space GC是僅僅回收From Space的垃圾，那麼在滿足以下兩個條件之一時，下一次執行Generational Semi-Space GC時，就不是僅僅回收From Space的垃圾了：1）上一次執行不僅僅回收From Space的垃圾的Generational Semi-Space GC以來，總共移動至Promote Space的對象超過閥值kBytesPromotedThreshold（4MB）；2) 目前從Large Object Space上配置設定的記憶體位元組數，比上次執行不僅僅回收From Space的垃圾的Generational Semi-Space GC時在Large Object Space上配置設定的記憶體位元組數，超過閥值kLargeObjectBytesAllocatedThreshold（16MB）。這兩個條件的意思是說，當Promote Space或者Large Object Space可用的空閑記憶體不多時，就不能僅僅是回收From Space的垃圾，也要對它們的垃圾進行回收，不然的話，下次再執行Generational Semi-Space GC的時候，Promote Space就不夠用了，或者下次再配置設定Large Object時，Large Object Space不夠用。
4. 調用Heap類的成員函數ClearMarkedObjects清零各個Space的Mark Bitmap。
這樣，Semi-Space GC或者Generational Semi-Space GC的結束階段也執行完成了，整個Semi-Space GC或者Generational Semi-Space GC的執行過程也分析完成了。從中我們就可以看到它們與Mark-Sweep GC的兩個核心差別：
1. Semi-Space GC或者Generational Semi-Space GC的執行是Stop-the-world的，而Mark-Sweep GC可以Concurrent執行的。
2. Semi-Space GC或者Generational Semi-Space GC在執行的過程中需要兩個Space，并且需要移動對象，而Mark-Sweep GC僅需要一個Space就可以執行，并且不需要移動對象。
這樣的差別就決定了Semi-Space GC或者Generational Semi-Space GC的執行效率沒有Mark-Sweep GC高，但是由于它在移動對象的同時使得對象可以緊湊地排列在一起，進而可以解決記憶體碎片問題，這是Mark-Sweep GC沒法做到的。是以，Semi-Space GC或者Generational Semi-Space GC适合作為Background GC來執行，因為目前應用程式運作在Background時，應用程式的響應時間是不重要的，但是我們卻可以借這個時機來解決記憶體碎片問題。
在接下來一篇文章中，我們将繼續分析ART運作時引進的第三種Compacting GC -- Mark-Compact GC。Mark-Compact GC同樣可以解決記憶體碎片問題，同樣也是通過移動對象來實作的，不過它隻需要一個Space就可以執行，敬請關注！更多資訊也可以關注老羅的新浪微網誌：http://weibo.com/shengyangluo。