一、前言

而在 Pink（倉儲(chǔ)作業(yè)系統(tǒng)）的線上穩(wěn)定性問題中，有一個(gè)和 GC 相關(guān)的疑難雜癥，問題堆棧發(fā)生在 GC 標(biāo)記過程，但是導(dǎo)致問題的根源并不在這里，因?yàn)?GC 流程相當(dāng)復(fù)雜，無法確定問題到底出在哪個(gè)環(huán)節(jié)。于是，就對 DartVM 的 GC 流程進(jìn)行了一次完整的梳理，從 GC 整個(gè)流程逐步排查。

二、Dart 對象

要想完整的了解 GC，就要先了解 Dart 對象在 DartVM 的內(nèi)存管理是怎樣呈現(xiàn)的。這里，我們先從 Dart 對象的內(nèi)存分配來展開介紹。

對象內(nèi)存分配

編譯前：

void _syncAll() {
  final obj = TestB();
  obj.hello("arg");
}

編譯后的 FlowGraph：

@"==== package:flutter_demo/main.dart_::__syncAll@1288309603 (RegularFunction)\r\n"
@"B0[graph]:0\r\n"
@"B1[function entry]:2\r\n"
@"    CheckStackOverflow:8(stack=0, loop=0)\r\n"
@"    t0 <- AllocateObject:10(cls=TestB)\r\n"
@"    t1 <- LoadLocal(:t0 @-2)\r\n"
@"    StaticCall:12( TestB.<0> t1)\r\n"
@"    StoreLocal(obj @-1, t0)\r\n"
@"    t0 <- LoadLocal(obj @-1)\r\n"
@"    t1 <- Constant(#arg)\r\n"
@"    StaticCall:14( hello<0> t0, t1, using unchecked entrypoint, result_type = T{??})\r\n"
@"    t0 <- Constant(#null)\r\n"
@"    Return:16(t0)\r\n"
@"*** END CFG\r\n"

可以看到，一個(gè)構(gòu)造方法調(diào)用，最終會(huì)轉(zhuǎn)換為 AllocateObject 和 StaticCall 兩條指令，其中 AllocateObject 指令用來分配對象內(nèi)存，而 StaticCall 則是真正調(diào)用構(gòu)造方法。

那 AllocateObject IL 最終轉(zhuǎn)化成的機(jī)器指令又是怎樣的呢？

圖片

在將 AllocateObject 指令轉(zhuǎn)換為 AOT 指令前，會(huì)先通過 GenerateNecessaryAllocationStubs() 方法為 FlowGraph 中的每一個(gè) AllocateObject 指令所對應(yīng) Class 生成一個(gè) StubCode，StubCode::GetAllocationStubForClass() 會(huì)先檢查 對應(yīng) Class 是否已經(jīng)存在 allocation StubCode，如果已經(jīng)存在，則直接返回；如果不存在，則會(huì)執(zhí)行下面代碼，為 Class 生成 allocation StubCode。

圖片

可以看出，生成的 allocation StubCode 其實(shí)主要是使用了 object_store->allocate_object_stub()，而 object_store->allocate_object_stub() 最終指向的則是 DartVM 中的 Object::Allocate()。

生成 allocation StubCode 之后，我們來看一下 AllocateObject 指令轉(zhuǎn)成 AOT 機(jī)器指令是怎樣的。

圖片

可以看出，最終生成的機(jī)器指令主要就是對 StubCode 的調(diào)用，而調(diào)用的 StubCode 就是上文中通過 GenerateNecessaryAllocationStubs() 生成的 allocation StubCode。所以，Dart 對象的內(nèi)存分配最終是通過 DartVM 的 Object::Allocate() 來實(shí)現(xiàn)的。接下來，我們簡單看一下 Object::Allocate() 的實(shí)現(xiàn)。

圖片

可以看到，Object::Allocate() 主要是通過 DartVM 中的 heap 進(jìn)行內(nèi)存分配的，而 heap->Allocate() 的返回值就是內(nèi)存分配的地址。接下來，通過判斷 address == 0 來判斷，內(nèi)存是否分配成功，如果分配失敗，說明 heap 上已經(jīng)不能再分配更多內(nèi)存了，就會(huì)拋出 OOM。反之，則通過 NoSafepointScope 來建立非安全點(diǎn)作用域，然后，通過 InitializeObject() 為對象中屬性賦初始值，完成對象初始化。到這里，Dart 對象在內(nèi)存中的分配流程就結(jié)束了，接下來就是調(diào)用構(gòu)造函數(shù)，完成對象的真正構(gòu)造。那么，Dart 對象在內(nèi)存中的存儲(chǔ)形式是怎樣的呢？接下來，我們就來介紹一下 Dart 對象的內(nèi)存布局。

對象內(nèi)存布局

Dart 中的大部分對象都是 UntaggedObject 的形式存儲(chǔ)在內(nèi)存中，而對象之間的依賴則是通過 ObjectPtr 來維系，ObjectPtr 是指向 UntaggedObject 的指針，所以對象之間的訪問都是通過 ObjectPtr。

先看一下 UntaggedObject 的實(shí)現(xiàn)：

圖片

圖片

代碼比較長，這里直接看一下偽代碼：

class UntaggedObject {
  // 表示對象類型的 tag
  var tag;


}

UntaggedObject 是 Dart VM 中一種比較基礎(chǔ)的對象結(jié)構(gòu)，所以 Dart 中的大部分對象都是由 UntaggedObject 來承載的。由于 UntaggedObject 可以存儲(chǔ)不同類型的數(shù)據(jù)，因此需要使用 tag 字段來標(biāo)識(shí)當(dāng)前對象的類型。具體的實(shí)現(xiàn)方式是，使用 tag 字段的低位來記錄對象的類型，另外的高位用來存儲(chǔ)一些額外的信息，例如對象是否已經(jīng)被垃圾回收等。所以，UntaggedObject 可以看做是 Dart 對象的 header。

一個(gè) Dart 對象其實(shí)是由兩部分組成，一個(gè) header，一個(gè)是 fields，而 header 就是上文中的 UntaggedObject。

+-------------------+
         |    header word    |
         +-------------------+
         | instance variables|
         |     (fields)      |
         +-------------------+

Header word：包含了對象的類型信息、標(biāo)記位、長度等一些重要元信息。具體信息將根據(jù)對象的類型與具體實(shí)現(xiàn)而不同。

Instance variables（fields）：是一個(gè)數(shù)組，用于存儲(chǔ)類的實(shí)例變量。每個(gè)字段可以存儲(chǔ)不同的數(shù)據(jù)類型，如布爾值、數(shù)字、字符串、列表等。

接下來，我們看一下，一個(gè) Dart 對象是如何遍歷它的所有屬性：

可以看出，先通過 HeapSize() 獲取對象在 heap 中的實(shí)際大小，然后根據(jù)對象起始地址 + UntaggedObject 的大小計(jì)算得出 fileds 中保存第一個(gè) ObjectPtr 的地址，然后根據(jù)對象起始地址 + 對象時(shí)機(jī)大小 - ObjectPtr 的大小計(jì)算得出 fileds 中保存的最后一個(gè) ObjectPrt 的地址，這樣就可以通過第一個(gè) ObjectPtr 遍歷到最后一個(gè) ObjectPrt，訪問到 Dart 對象中的所有屬性。

對象指針

標(biāo)記為 0 可以使 Smi 可以直接執(zhí)行很多操作，而無需取消標(biāo)記和重新標(biāo)記。

標(biāo)記為 1 的 heap 對象指針 在訪問對象時(shí)需要先取消標(biāo)記，代碼實(shí)現(xiàn)如下。

Heap 中的對象總是以雙字節(jié)增量分配的。所以 老年代中的對象是保持雙字節(jié)對齊的（address % double-word == 0），而新生代中的對象則保持雙字節(jié)對齊偏移（address % double-word == word）。這樣的話，我們僅需要通過對象地址的對齊方式就能判斷出對象是老年代 還是 新生代，也方便了在 GC 過程快速分辨出對象是新生代 還是 老年代，從而在遍歷過程中直接跳過。

圖片

三、DartVM GC

在介紹 DartVM GC 之前，我們先來看一下 DartVM 的內(nèi)存模型。

圖片

可以看到，DartVM 中可以運(yùn)行多個(gè) isolate group，而一個(gè) ioslate group 中又運(yùn)行著多個(gè) isolate，對于 Flutter 應(yīng)用來說，通常只有 一個(gè) isolate group，運(yùn)行 main() 方法的 Root Isolate 和其他 isolate，其他 isolate 也是通過 Root Isolate 孵化而來，所以都隸屬同一個(gè) isolate group。每個(gè) isolate group 都有一個(gè)單獨(dú)的 Heap，Heap 又分為新生代和老年代，所以 DartVM 采用的 GC 方式是分代 GC。新生代使用 Scavenge 進(jìn)行垃圾回收，老年代則是使用 Mark-Sweep 和 Mark-Compact 進(jìn)行垃圾回收。Scavenge 采用的 GC 算法是 Copying GC，而 Copying GC 算法的思路是把內(nèi)存分為兩個(gè)空間，這里可以稱之為 from-space 和 to-space。接下來，我們來看一下 Scavenge GC 的具體實(shí)現(xiàn)。

Scavenge

可以看到，Scavenge 會(huì)在 主線程和 多個(gè) helper thread 上并發(fā)執(zhí)行 ParallelScavengerTask，接下來看一下 ParallelScavengerTask 的實(shí)現(xiàn)。

ParallelScavengerTask 中會(huì)通過 ProcessRoots() 來遍歷整個(gè) heap 上的所有根對象 以及 RememberedSet 中的對象，而 RememberedSet 中的對象不一定是根對象，也可能是普通的老年代對象，但是它的屬性中保存了新生代對象的指針，因?yàn)樾律鷮ο笤谝苿?dòng)之后，也要更新老年代對象中的對象指針，所以ProcessRoots() 會(huì)把這類對象也看做根對象進(jìn)行遍歷。

然后再通過 ParallelScavengerVisitor 訪問所有的根對象，如果根對象是：

圖片

ScavengePointer() 會(huì)通過 ScavengeObject() 將當(dāng)前屬性對象轉(zhuǎn)移至新生代的 to-space 或者老年代分頁上，如果是轉(zhuǎn)移至老年代分頁上，則會(huì)將當(dāng)前屬性對象記錄到 promoted_list_ 隊(duì)列中；之后便將新對象的地址賦值到根對象的屬性，完成對象引用更新。

圖片

ParallelScavengerTask 中執(zhí)行完 ProcessRoots() 之后，便開始執(zhí)行 ProcessToSpace() 遍歷 to-space 區(qū)域中的對象，而此時(shí) to-space 區(qū)域中存放的正是剛剛復(fù)制過來的根對象，然后通過 ProcessCopied() 遍歷根對象中的所有屬性。

圖片

遍歷到的屬性對象，如果是新生代對象，則繼續(xù)移動(dòng)到 to-space 區(qū)域或者老年代內(nèi)存分頁中，然后用移動(dòng)后的新地址更新對象屬性的對象指針。

移動(dòng)后的對象因?yàn)榉湃氲搅?to-space 區(qū)域，此時(shí)新加入到 to-space 的對象也將被遍歷，這樣根對象的屬性遍歷結(jié)束后會(huì)緊接著遍歷屬性對象中的屬性，然后新的屬性對象又被移動(dòng)到 to-space 區(qū)域。這樣周而復(fù)始，就達(dá)到了廣度優(yōu)先遍歷的效果。所有被根對象直接引用或者間接引用到的對象都會(huì)被遍歷到，對象從 from-space 轉(zhuǎn)移到 to-space 或者老年代分頁上，并完成對象引用更新。

在 ScavengeObject() 移動(dòng)對象的過程中，本來在 from-space 區(qū)域的對象不一定是移動(dòng)到 to-space 區(qū)域，也有可能移動(dòng)到老年代分頁內(nèi)存上，那這些對象所關(guān)聯(lián)的屬性該怎么更新呢？這就要介紹一下 promoted_list_，在 ScavengeObject() 過程中，移動(dòng)到老年代的對象，將會(huì)被放入 promoted_list_ 集合中，當(dāng) ProcessToSpace() 結(jié)束之后，則會(huì)調(diào)用 ProcessPromotedList() 方法遍歷 promoted_list_ 集合中的對象，從而對移動(dòng)到老年代的對象的所有屬性進(jìn)行遍歷，并將其所關(guān)聯(lián)的對象指針進(jìn)行更新。

接下來，我們來看一下 ScavengeObject() 的實(shí)現(xiàn)，也就是對象移動(dòng)到 to-space 的具體細(xì)節(jié)。

代碼較長，這里就只截出了部分細(xì)節(jié)，可以看到，ScavengeObject() 會(huì)先通過 ReadHeaderRelaxed() 獲取到對象頭，通過對象頭來判斷當(dāng)前對象是否已經(jīng)被轉(zhuǎn)移，如果已經(jīng)轉(zhuǎn)移，也直接通過 header 獲取新地址的對象，然后將新對象進(jìn)行返回。如果未轉(zhuǎn)移，則通過 NewPage::of() 獲取到對象所在的新生代內(nèi)存分頁，通過該分頁中的 survivor_end_ 來判定該對象是否是上次 GC 中的存活對象，如果不是上次 GC 的存活對象，說明是新對象，就直接通過 TryAllocateCopy() 在 to-space 上申請內(nèi)存空間得到 new_addr。接下來，就判斷 new_addr 是否為 0，如果為 0，就存在兩種情況，一個(gè)是該對象是上次 GC 的存活對象，一個(gè)是 TryAllocateCopy() 分配內(nèi)存失敗，這兩種情況下就會(huì)通過 page_space_ 在老年代內(nèi)存上分配內(nèi)存，從而使對象從新生代轉(zhuǎn)移到老年代。接下來，就是 objcpy() 將對象數(shù)據(jù)復(fù)制到新地址中。復(fù)制完成后，就會(huì)通過 ForwardingHearder 來創(chuàng)建一個(gè) forwarding_header 對象，并通過 InstallForwardingPointer 將其寫入到原來對象的對象頭中，這樣在遍歷對象過程中，快速判斷出對象是否已經(jīng)轉(zhuǎn)移，并通過對象頭快速獲取到轉(zhuǎn)移后的新地址。至此，ScavengeObject() 的流程就結(jié)束了，然后將新對象返回出去，然后上層調(diào)用點(diǎn) ScavengePointer() 就會(huì)通過這個(gè)新對象來更新對象指針?？梢钥闯觯琒cavenge 在移動(dòng)對象的同時(shí)，將對象指針也進(jìn)行更新了，這樣就只需遍歷一次新生代內(nèi)存上的對象，即可完成 GC 的主流程。所以，新生代的 GC 算法相對于其他 GC 算法要高效很多。

而 Scavenge 之所以采用 Copying GC 算法，正是因?yàn)樗鼉?yōu)秀的吞吐量，吞吐量意思就是單位時(shí)間內(nèi) GC 的處理能力，可以簡單理解為效率更好的算法吞吐量更優(yōu)秀。對比一下，Mark-Sweep 算法的消耗是根搜索和遍歷整個(gè) heap 花費(fèi)的時(shí)間之和，Copying GC 算法則是根搜索和復(fù)制存活對象。一般來說 Copying GC 算法的吞吐量會(huì)更優(yōu)秀，堆越大差距越明顯。眾所周知，在算法上，時(shí)間維度和空間維度是成反比的，既然有了這么優(yōu)秀吞吐量，那必然要犧牲一部分空間，所以 Copying GC 在內(nèi)存使用效率上相對于其他 GC 算法是比較低的。Copying GC 算法總是有一個(gè)區(qū)域無法使用，對比其他使用整堆的算法，堆的使用效率低。這是 Copying GC 算法的一個(gè)重大缺陷。

Mark-Sweep

圖片

觸發(fā) GC 的方式有兩種，一個(gè)是系統(tǒng)處于空閑狀態(tài)時(shí)，一個(gè)對象分配內(nèi)存時(shí)內(nèi)存不足，上方代碼則是 Heap::NotifyIdle() 中的一段邏輯。Heap::NotifyIdle() 是 Dart VM 中的一個(gè)函數(shù)，用于通知垃圾回收器當(dāng)前系統(tǒng)處于空閑狀態(tài)，垃圾回收器可以利用這段空閑時(shí)間進(jìn)行垃圾回收。具體來說，Heap::NotifyIdle函數(shù)會(huì)向垃圾回收器發(fā)送一個(gè)通知，告訴垃圾回收器當(dāng)前系統(tǒng)處于空閑狀態(tài)，可以進(jìn)行垃圾回收。垃圾回收器在收到通知后，會(huì)開始啟動(dòng)垃圾回收器，對堆中的垃圾對象進(jìn)行回收。這個(gè)函數(shù)可以在應(yīng)用程序中的任何時(shí)間點(diǎn)調(diào)用，例如當(dāng)應(yīng)用程序處于空閑狀態(tài)時(shí)，或者當(dāng)應(yīng)用程序需要高峰時(shí)期的性能時(shí)。

Mark-Sweep 主要分為兩個(gè)階段一個(gè)是標(biāo)記階段，另一個(gè)則是清理階段。這里我們先看一下標(biāo)記階段。

對象標(biāo)記

對象標(biāo)記是整個(gè)老年代 GC 的一個(gè)重要流程，不管是 Mark-Sweep，還是 Mark-Compact，都建立在對象標(biāo)記的基礎(chǔ)上。而對象標(biāo)記又分為并行標(biāo)記和并發(fā)標(biāo)記，這里我們以并行標(biāo)記為例來介紹一下標(biāo)記階段。并行標(biāo)記是利用多個(gè)線程同時(shí)進(jìn)行標(biāo)記任務(wù)，提高多核 CPU 的使用率，從而減少 GC 流程中對象標(biāo)記所花費(fèi)的時(shí)間，這里我們直接看一下 并行標(biāo)記過程中 MarkObjects() 具體實(shí)現(xiàn)。

可以看到，MarkObjects() 中的 FLAG_marker_tasks 和 Scavenge 中的 FLAG_scavenger_tasks 相似，為了充分利用 CPU，提高 GC 的性能，通過 FLAG_marker_tasks 決定線程的個(gè)數(shù)，然后開啟多個(gè)線程并發(fā)標(biāo)記，F(xiàn)LAG_scavenger_tasks 默認(rèn)值也是 2。這里我們假設(shè) FLAG_scavenger_tasks 是 0，以單線程標(biāo)記 來梳理 對象標(biāo)記的整個(gè)流程。因?yàn)槭菃尉€程，所以這里忽略掉 ResetSlices() 的實(shí)現(xiàn)，ResetSlices() 的主要作用是進(jìn)行分片，為多個(gè)線程劃分不同的標(biāo)記任務(wù)。接下來，我們可以看到 IterateRoots()，開始遍歷根對象，從根對象開始標(biāo)記，根對象標(biāo)記之后，會(huì)將根對象添加至 work_list_。緊接著，會(huì)調(diào)用 ProcessDeferredMarking() 從 work_list_ 中取出對象，然后遍歷它的所有屬性，將屬性所關(guān)聯(lián)的對象進(jìn)行標(biāo)記，并將其再次加入 work_list_ 繼續(xù)遍歷，周而復(fù)始，就會(huì)把根對象直接引用或間接引用的對象都進(jìn)行了標(biāo)記，從而達(dá)到了從根對象開始的廣度優(yōu)先遍歷。接下來，我們看一下對象標(biāo)記 MarkObject() 的具體實(shí)現(xiàn)。

圖片

圖片

MarkObject() 截圖中刪除了部分細(xì)節(jié)，這里主要看一下關(guān)鍵流程?？梢钥吹剑琈arkObject() 會(huì)先判斷對象是否是小整形或者是新生代對象，小整形在上文有介紹到，指針即對象，無需標(biāo)記，而新生代對象也無需標(biāo)記，緊接著就是調(diào)用 TryAcquireMarkBit() 進(jìn)行標(biāo)記，標(biāo)記完成后，就會(huì)調(diào)用 PushMarked() 將對象加入到 work_list_ 中。接下來，我們看一下 DrainMarkingStack() 的實(shí)現(xiàn)，也就是遍歷 work_list_ 的實(shí)現(xiàn)。

圖片

正如上文所述，DrainMarkingStack() 會(huì)以一直從 work_list_ 中取出對象，然后通過 VisitPointersNonvirtual() 遍歷對象中的所有屬性，將屬性所關(guān)聯(lián)的對象進(jìn)行標(biāo)記，標(biāo)記之后再將其加入到 work_list_，致使繼續(xù)往下遍歷，直到 work_list_ 中的對象被清空。這樣一來，根對象直接引用和間接引用的對象都將會(huì)標(biāo)記。至此，標(biāo)記對象的核心流程就大致介紹完了。

接下來，我們看一下 Mark-Sweep 中另外一個(gè)重要的環(huán)節(jié) Sweep。

Sweep

Sweep 作為 Mark-Sweep 的重要一環(huán)，主要作用是將未標(biāo)記對象的內(nèi)存進(jìn)行清理，從而釋放出內(nèi)存空間給新對象進(jìn)行分配。

我們直接看一下 Sweep 流程中的關(guān)鍵代碼：

可以看到，老年代的 OldPage 主要是通過 sweeper 的 SweepPage() 來進(jìn)行清理的，SweepPage() 清理完成后會(huì)返回一個(gè) bool 值，表示當(dāng)前的 OldPage 是否還存在對象，如果已經(jīng)沒有對象了，則會(huì)調(diào)用 Deallocate()對當(dāng)前 OldPage 所占用的內(nèi)存進(jìn)行釋放。

接下來，我們看一下 SweepPage() 的主要實(shí)現(xiàn)。

圖片

代碼較長，這里只截出了關(guān)鍵部分，在遍歷 OldPage 上的對象時(shí)，會(huì)先取出對象的 tags 判斷是否被標(biāo)記，如果對象被標(biāo)記了，則會(huì)清除對象的標(biāo)記位，然后將對象的大小累加到 used_in_bytes 中；如果沒有標(biāo)記， 則會(huì)創(chuàng)建一個(gè) free_end 變量來記錄可以清理的結(jié)束位置，然后通過 while 循環(huán)來遍歷后續(xù)對象，直到遍歷到一個(gè)已標(biāo)記的對象，這樣做的目的是為了一次性計(jì)算出可連續(xù)清理的內(nèi)存，這樣的話就可以釋放出一個(gè)盡可能大的內(nèi)存空間來分配新的對象，可以看到，最終是通過 free_end - current 來計(jì)算出可連續(xù)釋放的空間，然后將可釋放的起始地址與大小記錄到 freelist 中，這樣后續(xù)對象在分配內(nèi)存時(shí) 就可以通過 OldPage 的 freelist 來獲取到內(nèi)存。

至此，Mark-Sweep 的流程就結(jié)束了。Mark-Sweep 作為老年代 GC 最常用的算法，也存著一些缺點(diǎn)，例如碎片化問題。為了解決碎片化問題，就引入了 Mark-Compact。接下來，我們就介紹一下老年代的另外一個(gè) GC 算法 Mark-Compact。

Mark-Compact

老年代內(nèi)存在申請內(nèi)存分頁之后，會(huì)在當(dāng)前內(nèi)存分頁尾部分配一塊內(nèi)存來存放 ForwardingPage 對象。而這個(gè) ForwardingPage 對象中則是存放了多個(gè) ForwardingBlock，F(xiàn)orwardingBlock 中則是存放當(dāng)前分頁存活對象即將轉(zhuǎn)移的新地址。

圖片

從上方代碼可以看出，整個(gè)壓縮階段主要分成兩個(gè)步驟，一個(gè) PlanPage()，一個(gè)是 SlidePage()。這里先介紹 PlanPage()，它的主要作用是計(jì)算所有存活對象需要移動(dòng)的新地址，并將其記錄到上文中所提到的 ForwardingPage 的 ForwardingBlock 中。由于跟CopyingGC 不同的是在同一塊區(qū)域操作，所以可能會(huì)出現(xiàn)移動(dòng)時(shí)把存活對象覆蓋掉的情況，所以這一步只做存活對象新地址的計(jì)算。

可以看到，PlanPage() 并沒有直接從 object_start() （分頁內(nèi)存中的第一個(gè)對象的地址）進(jìn)行處理，而是調(diào)用了 PlanBlock() 來進(jìn)行處理，顧名思義，內(nèi)存分頁會(huì)劃分成多個(gè) Block，然后對 Block 分別處理，并將計(jì)算出的新地址記錄到 ForwardingBlock 中。接下來我們看一下 PlanBlock() 的具體實(shí)現(xiàn)。

圖片

可以看到，PlanBlock() 會(huì)先通過 first_object 計(jì)算得到 Block 中的起始地址，然后通過 kBlockSize 計(jì)算的得出 Block 的結(jié)束地址，然后通過起始地址遍歷 Block 中的所有對象。如果當(dāng)前遍歷到的對象被標(biāo)記了，則會(huì)通過 RecordLive() 記錄到 ForwardingBlock 中，而 RecordLive() 內(nèi)部使用了一些黑魔法，它并沒有直接保存對象轉(zhuǎn)移的新地址，而是先計(jì)算出對象在 Block 中的偏移量，然后通過這個(gè)偏移量對 live_bitvector_ 進(jìn)行位移計(jì)算得到一個(gè) bit 位， 用這個(gè) bit 位來記錄該對象是否存活。當(dāng) Block 中的所有對象都遍歷完成后，通過 set_new_address() 整個(gè) Block 中對象轉(zhuǎn)移的新地址。所以，每個(gè) Block 都只會(huì)存儲(chǔ)一個(gè)新地址，那 Block 中的所有存活對象，怎么根據(jù)這個(gè)新地址進(jìn)行移動(dòng)呢？這就要介紹一下 SlidePage() 中的 SlideBlock()，這里我們就不再關(guān)注 SlidePage() 了，因?yàn)樗膶?shí)現(xiàn)和 PlanPage() 差不多，里面循環(huán)調(diào)用了 SlideBlock()，這里我們直接看一下 SlideBlock() 的實(shí)現(xiàn)。

SlideBlock() 代碼較長，只截了其中最關(guān)鍵的一部分，可以看到，在遍歷 Block 中的對象時(shí)，會(huì)先通過 forwarding_block 獲取到對象的新地址，然后將新地址轉(zhuǎn)化為 UntaggedObject 的對象指針，然后通過 memmove() 將舊地址中的數(shù)據(jù)移動(dòng)到新地址，最后通過 VisitPointers() 將對象中的屬性所引用的對象指針進(jìn)行更新。

看到這里，我們對 Compact（內(nèi)存壓縮） 已經(jīng)有了一個(gè)大致的了解，CompactTask 先通過 PlanPage() 遍歷老年代分頁內(nèi)存上的所有標(biāo)記對象，然后計(jì)算出他們將要移動(dòng)的新地址，然后再通過 SlidePage() 再次遍歷老年代內(nèi)存上的對象，將存活的對象移動(dòng)到新地址，在對象移動(dòng)的同時(shí)去更新對象屬性中的對象指針（也就是對象之間的引用關(guān)系）。

接下來看一下 VisitPointers() 的實(shí)現(xiàn)，看一下對象屬性中的對象指針是如何更新的。

圖片

可以看到，VisitPointers() 會(huì)遍歷對象屬性中的所有對象指針，然后調(diào)用 ForwardPointer() 完成對象指針更新。接下來，我們看一下 ForwardPointer() 的實(shí)現(xiàn)。

圖片

可以看到，它會(huì)先通過 OldPage::of() 找到對象指針?biāo)趦?nèi)存分頁，然后獲取到它的 forwarding_page，通過 forwarding_page 查詢出對象的新地址，然后再用新地址更新對象指針。

在 PlanPage() 和 SlidePage() 執(zhí)行結(jié)束之后，Compact 流程就接近尾聲了，剩下的就是掃尾工作了，其實(shí)還是對象引用的更新，SlidePage() 中移動(dòng)對象同時(shí)雖然會(huì)更新對象指針，但是這僅僅是處理了老年代內(nèi)存分頁上對象之間的引用，但是像新生代對象，它的對象屬性中可能也存在老年代對象的對象指針，它們之間的引用關(guān)系還沒有被更新。所以，接下來就是更新非老年代對象中的對象指針。

圖片

通過注釋可以看出，接下來的就主要是對 large_page 與新生代內(nèi)存中的對象進(jìn)行對象指針更新。至此，Compact 的流程就基本結(jié)束了。

通過以上分析，可以發(fā)現(xiàn)，相對于 CopyingGC、Mark-Sweep，Mark-Compact 也存在著優(yōu)缺點(diǎn)。

優(yōu)點(diǎn)：

可有效利用堆：比起 CopyingGC 算法，它可利用的堆內(nèi)存空間更大；同時(shí)也不存在內(nèi)存碎片，所以比起 Mark-Sweep，可利用空間也是更大。

缺點(diǎn)：

壓縮過程有計(jì)算成本。整個(gè)標(biāo)記壓縮流程必須對整個(gè)堆進(jìn)行 3 次遍歷，執(zhí)行該算法花費(fèi)的時(shí)間是和堆大小成正比的，吞吐量要劣于其他算法。

并發(fā)標(biāo)記

但是，并發(fā)標(biāo)記并不是在所有場景下都使用的。當(dāng)內(nèi)存到達(dá)一定閾值，相當(dāng)吃緊的情況下，還是會(huì)采取并行標(biāo)記的方式，掛起所有 isolate 線程，直到整個(gè) GC 流程結(jié)束。

接下來，我們來看一下 StartConcurrentMark() 是如何實(shí)現(xiàn)并發(fā)標(biāo)記的。

圖片

可以看到，StartConcurrentMark() 會(huì)先 通過 ResetSlices() 計(jì)算分片個(gè)數(shù)，新生代對象作為 GC 標(biāo)記的根對象，為了提高標(biāo)記效率，多個(gè)標(biāo)記線程會(huì)同時(shí)遍歷新生代對象，所以通過分片的方式可以讓多個(gè)標(biāo)記線程能夠盡然有序的遍歷新生代分頁內(nèi)存上的對象。接下來，就是通過 thread_pool() 來分配多個(gè)線程來執(zhí)行標(biāo)記任務(wù) ConcurrentMarkTask，num_tasks 就是并發(fā)標(biāo)記的線程個(gè)數(shù)，之所以減 1，是因?yàn)楫?dāng)前主線程也作為標(biāo)記任務(wù)的一員，但是主線程只會(huì)調(diào)用 IterateRoots() 來遍歷根對象，后續(xù) work_list_ 中的對象則是通過 thread_pool() 重新分配一個(gè)線程來執(zhí)行 ConcurrentMarkTask，主線程的標(biāo)記任務(wù)到此就基本結(jié)束了，接下來就是通過 root_slices_monitor_ 同步鎖，等待所有根對象遍歷完成。剩下的都交給了 ConcurrentMarkTask 來完成。接下來，我們就看一下 ConcurrentMarkTask 的實(shí)現(xiàn)。

圖片

可以看到，ConcurrentMarkTask 在調(diào)用 IterateRoots() 完成根對象標(biāo)記之后，就會(huì)調(diào)用 DrainMarkingStack() 來遍歷 work_list_ 中的對象，而 DrainMarkingStack() 的實(shí)現(xiàn)在上文的對象標(biāo)記中已經(jīng)介紹過了，這里就不再贅述了。

有了并發(fā)標(biāo)記，GC 標(biāo)記任務(wù)和 isolate 線程就可以并發(fā)執(zhí)行，這樣就避免了 GC 標(biāo)記因掛起 isolate 線程帶來的長時(shí)間卡頓。

寫入屏障

在標(biāo)記過程中，當(dāng)未標(biāo)記的對象（TARGET）被賦值給已標(biāo)記對象（SOURCE）的屬性時(shí)，此時(shí) TARGET 對象理應(yīng)也該被標(biāo)記，為了防止 TARGET 對象逃逸標(biāo)記，寫入屏障會(huì)對未標(biāo)記的 TARGET 對象進(jìn)行檢查。

如果 TARGET 對象與 SOURCE 對象都是老年代對象時(shí)，寫入屏障就會(huì)對未標(biāo)記的 TARGET 對象進(jìn)行標(biāo)記，并將該對象加入到標(biāo)記隊(duì)列，致使該對象關(guān)聯(lián)的其他對象也會(huì)被標(biāo)記。

圖片

可以看到，SOURCE對象在保存 TARGET 對象指針建立引用關(guān)系時(shí)，會(huì)判斷 TARGET 對象 是否是 heap 上的對象，如果是 heap 上的對象，則會(huì)調(diào)用 CheckHeapPointerStore() 對其進(jìn)行檢查。接下來，我們看一下 CheckHeapPointerStore() 的具體實(shí)現(xiàn)。

圖片

在 CheckHeapPointerStore() 方法中，會(huì)判斷 TARGET 對象是否是新生代對象，如果是新生代對象，則會(huì)調(diào)用 EnsureInRememberedSet() 將 SOURCE 對象加入到 RememberedSet 中（主要作用于上文中介紹的 Scavenge，新生代對象轉(zhuǎn)移時(shí)能夠更新老年代對象中存儲(chǔ)的對象指針），但并未對 TARGET 對象進(jìn)行特殊處理，這是因?yàn)樾律鷮ο笤诶夏甏?GC 標(biāo)記過程中本身就作為根對象，而且在標(biāo)記結(jié)束時(shí)，會(huì)重新遍歷這些根對象。接下來，就是非新生代對象，非新生代對象只有兩種 Smi 和老年代對象，因?yàn)樵谕鈱雍瘮?shù) StorePointer() 中有判斷是否是 heap 上的對象，所以這里不可能是 Smi，只能是老年對象。老年代對象則調(diào)用 TryAcquireMarkBit() 進(jìn)行標(biāo)記，標(biāo)記成功后，將其加入到標(biāo)記隊(duì)列中（也就是上文中所提到的 work_list_），使其關(guān)聯(lián)到的對象也被遍歷標(biāo)記。

有了寫入屏障，就確保了在并發(fā)標(biāo)記時(shí)，isolate 修改 heap 對象之間的引用關(guān)系時(shí)，不會(huì)導(dǎo)致對象遺漏標(biāo)記被 GC 清理。但是寫入屏障也會(huì)帶來額外的開銷，為了減少這種開銷，就要介紹到另外一個(gè)優(yōu)化：寫入屏障消除。

寫入屏障消除

• SOURCE 對象是老年代對象，而 TARGET 對象是新生代對象，且 SOURCE 對象不在 RememberedSet 中。

1. 此場景下，會(huì)將 SOURCE 對象加入到 RememberedSet 中，作用于新生代 GC Scavenge。

• SOURCE 對象是老年代對象，TARGET 對象也是老年代且沒有被標(biāo)記，此時(shí) GC 線程正在標(biāo)記階段。

1. 此場景下，會(huì)對 TARGET 對象進(jìn)行標(biāo)記，并將 TARGET 對象加入到 work_list_ 中。

而在這兩種情況下，其實(shí)也存在著一些場景無需寫入屏障，只要在編譯時(shí)能夠判定出是這些場景，就可以消除這類的寫入屏障。我們簡單列舉一些場景：

• TARGET 對象是一個(gè)常量（因?yàn)槌Ａ勘囟ㄊ抢夏甏鷮ο?，即使在賦值給 SOURCE 對象時(shí)沒有被標(biāo)記，也會(huì)在 GC 過程中通過常量池被標(biāo)記）。
• TARGET 對象是 bool 類型（bool 類型只可能有三種情況：null、false、true，而這三個(gè)值都是常量，所以如果是 bool 類型，必定是一個(gè)常量）。
• TARGET 對象是小整形（小整形在上文中也介紹過，指針即對象，所以他不算是 heap 上的對象）。
• SOURCE 對象和 TARGET 對象是同一個(gè)對象（自身屬性持有自己）。
• SOURCE 對象是新生代對象或者是已經(jīng)被添加至 RememberedSet 的老年代對象（上文中也介紹過，新生代對象作為根對象，在標(biāo)記結(jié)束時(shí)，會(huì)重新遍歷這些根對象）。

我們可以知道，當(dāng) SOURCE 對象是通過 Object::Allocate() 進(jìn)行分配的（而不是從 heap 中加載的），它的 Allocate() 和它最近一次的屬性賦值之間如果不存在觸發(fā) GC 的 instruction，那它的屬性賦值也可以消除寫入屏障。這是因?yàn)?nbsp;Object::Allocate() 分配的對象一般情況下是新生代對象，如果是老年代對象，在 Allocate() 時(shí)會(huì)被直接修改為標(biāo)記狀態(tài)， 預(yù)先添加至 RememberedSet 和標(biāo)記隊(duì)列 work_list_ 中。

container <- AllocateObject
<intructions that do not trigger GC>
StoreInstanceField(container, value, NoBarrier)

在此基礎(chǔ)上， 當(dāng) SOURCE 對象的 Allocate() 和它的屬性賦值之間不存在函數(shù)調(diào)用，我們可以進(jìn)一步來消除屬性賦值帶來的寫入屏障。這是因?yàn)樵?GC 之后，Thread::RestoreWriteBarrierInvariant() 會(huì)將 ExitFrame 下方的棧幀中的所有老年代對象添加至 RememberedSet 和標(biāo)記隊(duì)列 work_list_ 中（ExitFrame 是表示函數(shù)調(diào)用棧退出的特殊幀，當(dāng)函數(shù)執(zhí)行完畢時(shí)，虛擬機(jī)會(huì)將 ExitFrame 推入棧頂，以表示函數(shù)的退出）。

container <- AllocateObject
<instructions that cannot directly call Dart functions>
StoreInstanceField(container, value, NoBarrier)

圖片

可以看到，Thread::RestoreWriteBarrierInvariant() 遍歷到 ExitFrame時(shí)，會(huì)開始掃描下一個(gè)棧幀，會(huì)通過 RestoreWriteBarrierInvariantVisitor 遍歷棧幀中的所有對象，并將其 RememberedSet 和標(biāo)記隊(duì)列 work_list_ 中。所以，這個(gè)寫入屏障消除必須保證 AllocateObject 和 StoreInstanceField 必須在同一個(gè)DartFrame 中，如果它們之間存在函數(shù)調(diào)用，就無法確保它們在ExitFrame 下方的同一個(gè) DartFrame 中。

可以看到，寫入屏障消除通過在編譯時(shí)和運(yùn)行時(shí)的一些推斷，避免了一些不必要的額外開銷。

四、Safepoints

GC 的某些階段要求 Heap 不允許被 mutator 使用，我們稱之為 safepoint operations。例如：老年代 GC 并發(fā)標(biāo)記時(shí)的根對象標(biāo)記，以及標(biāo)記結(jié)束后的對象清理。

圖片

為了執(zhí)行這些操作，所有 mutator 都需要暫時(shí)停止訪問 Heap，此時(shí) mutator 就到達(dá)了“安全點(diǎn)”。已經(jīng)達(dá)到安全點(diǎn)的 mutator 將不能訪問 Heap，直到 safepoint operations 完成。

在 GC 過程中，GcSafepointOperationScope 會(huì)致使當(dāng)前線程等待所有 isolate 線程到達(dá)“安全點(diǎn)”之后才能繼續(xù)執(zhí)行，這樣就保證了后續(xù)流程中 isolate 線程不會(huì)修改 Heap 上的對象。

圖片

NotifyThreadsToGetToSafepointLevel() 會(huì)通知所有 isolate 線程當(dāng)前需要掛起。

圖片

而 WaitUntilThreadsReachedSafepointLevel() 會(huì)等待所有 isolate 線程進(jìn)入安全點(diǎn)。

圖片

對應(yīng) isolate 在發(fā)送 OOB 消息時(shí)，會(huì)處理當(dāng)前線程狀態(tài)中的 interrupt 標(biāo)記位，如果當(dāng)前線程狀態(tài)的 interrupt 標(biāo)記位滿足 kVMInterrupt，則會(huì)調(diào)用 CheckForSafepoint() 檢查當(dāng)前 isolate 是否被請求進(jìn)入“安全點(diǎn)”，如果當(dāng)前 isolate 的 safepoint_state_ 被標(biāo)記需要進(jìn)入“安全點(diǎn)”，則會(huì)調(diào)用 BlockForSafepoint() 標(biāo)記 safepoint_state_ 已進(jìn)入“安全點(diǎn)”，并掛起當(dāng)前線程，直到“安全點(diǎn)操作”結(jié)束。

圖片

圖片

圖片

因此，當(dāng) isolate 發(fā)送 OOB 消息時(shí)，就會(huì)觸發(fā)“安全點(diǎn)”檢查，從而導(dǎo)致線程掛起進(jìn)入“安全點(diǎn)”。那什么是 OOB 消息，而 OOB 消息發(fā)送又是何時(shí)被觸發(fā)的，這就要簡單介紹一下 isolate 的事件驅(qū)動(dòng)模型。正如大部分的 UI 平臺(tái)，isolate 也是通過消息隊(duì)列實(shí)現(xiàn)的事件驅(qū)動(dòng)模型。不過，在 isolate 中有兩個(gè)消息隊(duì)列，一個(gè)隊(duì)列是普通消息隊(duì)列，另一個(gè)隊(duì)列叫 OOB 消息隊(duì)列，OOB 是 "out of band" 縮寫，翻譯為帶外消息，OOB 消息用來傳送一些控制類消息，例如從當(dāng)前 isolate 生成（spawn）一個(gè)新的 isolate。我們可以在當(dāng)前 isolate 發(fā)送OOB消息給新 isolate，從而控制新 isolate。比如，暫停(pause)，恢復(fù)(resume)，終止(kill)等。

有了“安全點(diǎn)”，就保證了其他線程在 GC 過程中不能隨意訪問、操作 Heap 上的對象，確保 GC 過程中一些重要操作（根對象遍歷、內(nèi)存清理、內(nèi)存壓縮等等） 不受其他線程影響。

五、GC問題定位

圖片

可以看到，問題發(fā)生在 GC 過程中的對象遍歷標(biāo)記。起初，猜想會(huì)不會(huì)是多個(gè) isolate 線程都觸發(fā)了 GC，多線程 GC 導(dǎo)致的，但是看了 Safepoints 實(shí)現(xiàn)之后，發(fā)現(xiàn)這種情況不可能存在，于是排除了此猜想。

因?yàn)?DartVM 中的老年代內(nèi)存分頁是通過 OldPage 進(jìn)行管理的，在這些 OldPage 中，除了 code pages，其他 OldPage 都是可讀可寫的。

而 DartVM 也提供了相應(yīng)的 API 來修改 OldPage 的權(quán)限。

• PageSpace::WriteProtectCode()
• PageSpace::WriteProtect()

在 GC 標(biāo)記前，會(huì)通過 PageSpace::WriteProtectCode() 將“老年代” 中的  code pages 權(quán)限修改為可讀可寫，以便在標(biāo)記過程中對 Instructions 對象進(jìn)行標(biāo)記，在 GC 結(jié)束后，再通過 PageSpace::WriteProtectCode() 將  code pages 的權(quán)限修改為只讀。

因?yàn)?code pages 是用來動(dòng)態(tài)分配的可執(zhí)行內(nèi)存頁，用來生成 JIT 的機(jī)器指令，所以 code pages 只讀權(quán)限導(dǎo)致的 SEGV_ACCERR 問題，只會(huì)在 Debug 包上才能復(fù)現(xiàn)，所以 release 包不會(huì)存在此問題。

而 PageSpace::WriteProtect() 也可以修改 OldPage 對應(yīng)分頁的讀寫權(quán)限，該方法可以將“老年代”上的所有 OldPage 修改為只讀權(quán)限。目前通過搜索代碼，發(fā)現(xiàn)只有一個(gè)調(diào)用時(shí)機(jī)，就是 ioslate 退出時(shí)，清理 ioslate 時(shí)會(huì)通過 WritableVMIsolateScope 對象的析構(gòu)會(huì)將 "老年代" 上的 所有 OldPage 改為只讀。OldPage 修改為只讀之后，再對 OldPage 上的對象進(jìn)行標(biāo)記時(shí)就會(huì)出現(xiàn)問題。通過模擬 WritableVMIsolateScope 對象的析構(gòu)，也復(fù)現(xiàn)了和線上完全一模一樣的 crash 堆棧。但是 isolate 正常情況下是不會(huì)退出的，所以在前期排除了這種可能。

后來，還是把猜測轉(zhuǎn)向了寫入屏障消除，會(huì)不是寫入屏障消除導(dǎo)致了對象逃逸了 GC 標(biāo)記，致使所在 OldPage 被清理釋放，再次觸發(fā) GC，遍歷到此對象指針時(shí)，對象所在的內(nèi)存已經(jīng)被釋放，野指針導(dǎo)致的 SEGV_ACCERR 問題。如果是這種情況的話，想到了一個(gè)臨時(shí)的解決方案，在 GC 標(biāo)記過程中，對 ObjectPtr 所指向地址做校驗(yàn)，判斷是否是一個(gè)合法地址。因?yàn)闃?biāo)記訪問的對象對存儲(chǔ)在 OldPage 上，所以我們只判斷一下該地址在不在 當(dāng)前"老年代"的 OldPage 的內(nèi)存區(qū)域內(nèi)，如果地址在 OldPage 內(nèi)存區(qū)域內(nèi)，說明 ObjectPtr 所指向的對象所在 OldPage 還存在，沒有被釋放，此塊內(nèi)存區(qū)域肯定是可以訪問的。

修復(fù)代碼

圖片

通過 PageSpace::ContainsUnsafe(uword addr) 方法，來判斷對象地址是否在 "老年代" 分頁內(nèi)存上，這個(gè)方法本來是輕量級(jí)的，但是 GC 過程中，需要標(biāo)記大量對象，每次標(biāo)記都要進(jìn)行這個(gè)判斷，導(dǎo)致此方法的總開銷較大，整個(gè) GC 時(shí)間被拉長。實(shí)測下來，每次 GC，都會(huì)導(dǎo)致界面 3～5s 的卡頓。所以，此方法還需要優(yōu)化。在上文中，也介紹過并發(fā)標(biāo)記，理論上 GC 標(biāo)記 和 isolate 是并發(fā)執(zhí)行的，不會(huì)影響到用戶交互。但是，GC 標(biāo)記并不是整個(gè)流程都和 isolate 并發(fā)執(zhí)行的，上文中也提到過 GcSafepointOperationScope，在 GC 標(biāo)記之前，會(huì)通過 GcSafepointOperationScope 掛起除當(dāng)前線程的所有 isolate 線程，直到當(dāng)前 GC 方法執(zhí)行結(jié)束，如果并發(fā)標(biāo)記階段，則是標(biāo)記方法執(zhí)行結(jié)束，上文中也提到過，GC 標(biāo)記的主線程會(huì)等待所有根對象標(biāo)記結(jié)束，所以根對象標(biāo)記結(jié)束后，才會(huì)進(jìn)入真正的并發(fā)標(biāo)記階段。因?yàn)榇蟛糠謫栴}都是發(fā)生在 work_list_ 中的對象標(biāo)記，我們是不是可以直接忽略根對象的標(biāo)記，在根對象標(biāo)記之后，才開啟對象指針校驗(yàn)（這樣就只能保證 work_list_ 中的對象標(biāo)記，根對象標(biāo)記還是存在問題，但是至少能減少問題出現(xiàn)的頻次）。

于是通過 GCMarker 中 root_slices_finished_ 變量來判斷根對象是否標(biāo)記結(jié)束，結(jié)束之后，才開啟對象指針校驗(yàn)。修改之后，確實(shí)不存在卡頓了，于是就開啟了上線灰度。

圖片

但是上線后，并不是很理想，GC 問題還是存在。既然猜測是寫入屏障消除導(dǎo)致的，干脆就大膽一點(diǎn)，直接把寫入屏障消除這一優(yōu)化給移除掉。寫入屏障消除這一優(yōu)化移除灰度上線之后，發(fā)現(xiàn) GC 問題還是存在。此時(shí)，思緒萬千，難道真的是 PageSpace::WriteProtect() 導(dǎo)致的，為了驗(yàn)證這一猜測，于是就在對象標(biāo)記之前加入了 RELEASE_ASSERT，判斷老年代分頁內(nèi)存是否真的被修改為了只讀權(quán)限。

上線之后，果不其然，GC 問題的堆棧信息發(fā)生了改變，錯(cuò)誤正是新加入的斷言。這就說明，老年代分頁內(nèi)存確實(shí)被修改為了只讀權(quán)限，此時(shí)去修改對象的標(biāo)記位肯定是有問題。

圖片

當(dāng)我們準(zhǔn)備更近一步時(shí)，卻因?yàn)楦哳l GC 問題的幾臺(tái)設(shè)備不再使用，失去了可用于灰度的設(shè)備，導(dǎo)致無法進(jìn)一步去驗(yàn)證問題。也因?yàn)檫@幾臺(tái)高頻 GC 問題設(shè)備的下線，GC 問題在 crash 占比中顯得不那么重要，問題就這樣淡出了我們的視線。不過還是希望后續(xù)能夠找到根因，徹底解決此問題。

六、總結(jié)&感悟