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

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

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

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

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

為保證一致性引入了ReadBarrier

二、新的Concurrent Mark Compact GC算法

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

1、UFFD特性介紹

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

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

2、BumpPointerSpace分配器

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

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

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

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

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

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

first_objs_moving_space：會(huì)在PrepareForCompaction階段，記錄被壓縮后某頁(yè)的首個(gè)對(duì)象的源地址。

pre_compact_offset_moving_space：會(huì)記錄頁(yè)面被壓縮后的地址偏移。

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

① MarkingPhase階段

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

SetLiveWords記錄存活地址和大小

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

② PrepareForCompaction階段

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

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

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

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

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

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

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

輸入

first_objs_moving_space[idx]壓縮頁(yè)的第一個(gè)對(duì)象pre_compact_offset_moving_space[idx]壓縮頁(yè)offset

處理過程

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

5、并行拷貝壓縮

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

總之，我們可以看到會(huì)有兩種頁(yè)拷貝和壓縮：

GC線程串行壓縮和拷貝

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

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

6、其他內(nèi)容

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

CompactPage和SlidePage中的跨頁(yè)對(duì)象處理。

壓縮后FromSpace頁(yè)的清理等。

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

1、優(yōu)點(diǎn)

GC過程中RSS峰值降低

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

2、缺點(diǎn)

一次GC活躍的對(duì)象被拷貝兩次

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

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

審核編輯：劉清