一、當(dāng)前GC算法及存在的問題

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

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

總結(jié)一下，CC主要存在兩個問題：

GC過程物理內(nèi)存徒增又陡降

為保證一致性引入了ReadBarrier

二、新的Concurrent Mark Compact GC算法

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

1、UFFD特性介紹

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

此外，在沒有發(fā)生SIGBUS錯誤時，也可以利用UFFD的ioctl特性進(jìn)行目標(biāo)內(nèi)存頁的處理。

2、BumpPointerSpace分配器

CMC對應(yīng)的分配器是BumpPointerSpace，相對RegionSpace其結(jié)構(gòu)更簡單，也更利于全局的內(nèi)存拷貝壓縮。

3、GC拷貝壓縮的準(zhǔn)備工作

在CMC對象初始化的時候，也會初始化跟內(nèi)存拷貝壓縮的相關(guān)的數(shù)據(jù)結(jié)構(gòu)。

在對Heap中對象進(jìn)行全面遍歷標(biāo)記的時候，會根據(jù)對象是否存活，來記錄和累加計算其壓縮后的地址，還有被壓縮后的各個內(nèi)存頁的首個對象，主要的數(shù)據(jù)結(jié)構(gòu)有：

創(chuàng)建info_map，其中包含:

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

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

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

創(chuàng)建compaction_buffers_map：會被用于壓縮過程中的頁面級別的壓縮，作為中轉(zhuǎn)緩存，最后再通過UFFD特性被拷貝到目標(biāo)地址頁面。

① MarkingPhase階段

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

SetLiveWords記錄存活地址和大小

chunk_info_vec批量記錄活躍內(nèi)存大小

② PrepareForCompaction階段

該階段比較重要的是InitMovingSpaceFirstObjects函數(shù)。該函數(shù)會找出每個需要移動的內(nèi)存頁的第一個對象，并找出這些對象應(yīng)該被復(fù)制到的目標(biāo)頁偏移量

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

4、單頁內(nèi)存拷貝壓縮

單頁的拷貝主要是通過調(diào)用DoPageCompactionWithStateChange函數(shù)實現(xiàn)的，主要包含兩個步驟：

CompactPage：拷貝到中轉(zhuǎn)頁

CopyIoctl：通過UFFD拷貝中轉(zhuǎn)頁到目標(biāo)頁地址

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

輸入

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

處理過程

基于live_words_bitmap_來遍歷內(nèi)存頁中的存活對象，逐步將數(shù)據(jù)復(fù)制到目標(biāo)地址到中轉(zhuǎn)頁。

5、并行拷貝壓縮

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

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

GC線程串行壓縮和拷貝

Mutator線程通過SIGBUS異常異步觸發(fā)

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

6、其他內(nèi)容

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

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

壓縮后FromSpace頁的清理等。

三、CMC算法的優(yōu)缺點

1、優(yōu)點

GC過程中RSS峰值降低

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

2、缺點

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

暫時沒有實現(xiàn)YoungGC

缺頁中斷產(chǎn)生的時延可能會導(dǎo)致GC過程的性能退化

審核編輯：劉清