一、當前GC算法及存在的問題

當前Android（O-T）一直使用的是Concurrent Copy GC算法（CC），該算法通過FromSpace和ToSpace兩個空間實現了非常巧妙的Copy機制，算是空間換時間（或者說復雜度），所以在GC的過程中，兩個Space會同時被利用，極端情況會占用內存會double。

此外，為了保證GC過程中，訪問對象的一致性，還引入的ReadBarrier，ReadBarrier會在訪問對象的時候判斷對象是否經過了拷貝，如果經過了拷貝需要返回拷貝后在ToSpace中的地址，反之，仍然返回拷貝前的地址。ReadBarrier會對每次對象訪問，都插入一次是否訪問的判斷，即使當前沒有在GC也會發生一次判斷。這就導致了執行了多余的指令，且在編譯結果二進制文件體積的增長。

總結一下，CC主要存在兩個問題：

GC過程物理內存徒增又陡降

為保證一致性引入了ReadBarrier

二、新的Concurrent Mark Compact GC算法

Android馬上要使能的新算法是Concurrent Mark Compact，簡稱CMC算法。CMC旨在解決上面介紹的CC算法存在的兩個問題，其中最核心的是利用Linux的UFFD特性，并且更新了Allocator算法。

1、UFFD特性介紹

UFFD全稱User Fault FD，其核心機制就是，先注冊并監控虛擬內存范圍的訪問，當該范圍的內存訪問出現異常時，比如SIGBUS錯誤時，可以把對這塊內存頁的處理交接給用戶空間。

此外，在沒有發生SIGBUS錯誤時，也可以利用UFFD的ioctl特性進行目標內存頁的處理。

2、BumpPointerSpace分配器

CMC對應的分配器是BumpPointerSpace，相對RegionSpace其結構更簡單，也更利于全局的內存拷貝壓縮。

3、GC拷貝壓縮的準備工作

在CMC對象初始化的時候，也會初始化跟內存拷貝壓縮的相關的數據結構。

在對Heap中對象進行全面遍歷標記的時候，會根據對象是否存活，來記錄和累加計算其壓縮后的地址，還有被壓縮后的各個內存頁的首個對象，主要的數據結構有：

創建info_map，其中包含:

chunk_info_vec：記錄存活對象的大小，所有該容器元素的累加和就是所有存活對象內存的大小。

first_objs_moving_space：會在PrepareForCompaction階段，記錄被壓縮后某頁的首個對象的源地址。

pre_compact_offset_moving_space：會記錄頁面被壓縮后的地址偏移。

創建compaction_buffers_map：會被用于壓縮過程中的頁面級別的壓縮，作為中轉緩存，最后再通過UFFD特性被拷貝到目標地址頁面。

① MarkingPhase階段

該階段會遍歷所有的對象，并在處理存活對象的時候，調用UpdateLivenessInfo函數，該函數主要做了下面兩個事情：

SetLiveWords記錄存活地址和大小

chunk_info_vec批量記錄活躍內存大小

② PrepareForCompaction階段

該階段比較重要的是InitMovingSpaceFirstObjects函數。該函數會找出每個需要移動的內存頁的第一個對象，并找出這些對象應該被復制到的目標頁偏移量

查找第一個live word，使用live_words_bitmap來找出第一個活動字的偏移量，然后計算出第一個活動對象的地址，并將第一個對象的地址和偏移量存儲到first_objs_moving_space和pre_compact_offset_moving_space向量中。2.函數進入一個循環，找出每個需要移動的頁的第一個對象和偏移量。并將它們存儲到first_objs_moving_space和pre_compact_offset_moving_space向量中。

4、單頁內存拷貝壓縮

單頁的拷貝主要是通過調用DoPageCompactionWithStateChange函數實現的，主要包含兩個步驟：

CompactPage：拷貝到中轉頁

CopyIoctl：通過UFFD拷貝中轉頁到目標頁地址

其中，CompactPage壓縮的輸入和處理過程如下：

輸入

first_objs_moving_space[idx]壓縮頁的第一個對象pre_compact_offset_moving_space[idx]壓縮頁offset

處理過程

基于live_words_bitmap_來遍歷內存頁中的存活對象，逐步將數據復制到目標地址到中轉頁。

5、并行拷貝壓縮

上一小節我們介紹了單頁拷貝壓縮的過程，全局的拷貝一般是從后往前的拷貝的，但是因為CMC也是并行的，所以GC過程中，非GC線程也就是Mutator線程還是會訪問對象的。CC算法是通過ReadBarrier實現這個階段數據一致性的，CMC是通過UFFD觸發的SIGBUS特性實現的，也就是當訪問一個對象時候，如果還沒有被分配就會導致SIGBUS異常，這時候虛擬機會通過UFFD的SIGBUS異常獲取缺頁的地址，從而觸發對應頁的拷貝壓縮。

總之，我們可以看到會有兩種頁拷貝和壓縮：

GC線程串行壓縮和拷貝

Mutator線程通過SIGBUS異常異步觸發

而為保證頁同時只會被一個線程處理，虛擬機通過ProcessState原子變量（每個頁都有一個）保證異步并行，等所有頁都被處理完后，GC過程就結束了。

6、其他內容

BlackAllocation（GC過程中新增的分配，被默認為黑色，不進行回收），通過SlidePage處理。

CompactPage和SlidePage中的跨頁對象處理。

壓縮后FromSpace頁的清理等。

三、CMC算法的優缺點

1、優點

GC過程中RSS峰值降低

消除了ReadBarrier，BinarySize減小，Object訪問性能提升

2、缺點

一次GC活躍的對象被拷貝兩次

暫時沒有實現YoungGC

缺頁中斷產生的時延可能會導致GC過程的性能退化

審核編輯：劉清