一、背景

早期Android中使用jemalloc作為默認(rèn)的Native內(nèi)存分配器，但是從R開始，Scudo替代jemalloc成為了non-svelte configuration模式下默認(rèn)的內(nèi)存分配器（svelte模式下默認(rèn)的內(nèi)存分配器依然是jemalloc）。

隨著64位機(jī)器和大RAM的普及，虛擬內(nèi)存和物理內(nèi)存的瓶頸都在不斷放寬，因此給了系統(tǒng)更多的選擇，可以在性能合理的范圍內(nèi)兼顧其他特性。在所有安全性問題中，內(nèi)存漏洞發(fā)生的入侵占到了半數(shù)以上，因此如果能在Allocator中抵御入侵，那將極大地降低安全問題的數(shù)量，Scudo也由此而引入。

二、設(shè)計(jì)實(shí)現(xiàn)

Scudo的設(shè)計(jì)考慮到了安全性，但目的是在安全性和性能之間取得良好的平衡。單從性能角度分析Scudo未必超過jemalloc，雖然它的分配策略更加簡化，但為了安全性所實(shí)施的一些策略會使其喪失一些性能。

1. Scudo組件

Scudo分配器主要由Primary、Secondary、TSD、Quarantine四個(gè)組件構(gòu)成。
Primary Allocator:它通過將預(yù)留內(nèi)存區(qū)域分成相同大小的塊來更快速高效得分配較小的內(nèi)存塊。目前實(shí)現(xiàn)了兩個(gè)Primary分配器，分別針對32位和64位體系結(jié)構(gòu)。它可以通過編譯時(shí)選項(xiàng)進(jìn)行配置。
對于64位andorid R/S，Primary Allocator如圖1所示。在初始化時(shí)會mmap出256M*33大小空間，共分為33段regions，分別通過classid 0~32標(biāo)記。每段region大小為256M，且出于安全考慮其頭部會隨機(jī)空缺處1~16頁。此外，每段region中再分為特定大小的內(nèi)存塊，如class 1 region分為32Bytes，class 2 region分為48Bytes，class 32 region為64K等（class 0 region用于存放內(nèi)存管理元數(shù)據(jù)）。如此當(dāng)分配小內(nèi)存時(shí)，首先會檢查合適大小的region中是否有空閑內(nèi)存塊，如果沒有則去更高一級region中分配，當(dāng)最高一級中也沒有合適的，則會從Secondary Allocator中分配。

此外，Primary Allocator提供了cache機(jī)制來加速內(nèi)存分配。當(dāng)線程分配內(nèi)存時(shí)，會通過線程TSD中SizeClassAllocatorLocalCache對象的chunks數(shù)組來尋找合適的空閑內(nèi)存。但chunks數(shù)組的大小是有限的(默認(rèn)28個(gè))，當(dāng)它們用完時(shí)就需要補(bǔ)充空閑內(nèi)存塊了。補(bǔ)充是從region的freelist（freelist的詳細(xì)數(shù)據(jù)存放于regioninfo）中直接獲取。當(dāng)freelist中的空閑對象不夠時(shí)，會擴(kuò)張region的空閑區(qū)域。
Secondary Allocator:相對于Primary更慢，它通過底層操作系統(tǒng)的內(nèi)存映射來分配更大的內(nèi)存。并且通過Secondary分配的內(nèi)存塊兩端被保護(hù)頁包圍。
對于64位andorid R/S，Secondary Allocator主要用于分配大于64K內(nèi)存，其直接使用mmap分配出一塊新的VMA。為了加快分配速度，同時(shí)設(shè)計(jì)了相應(yīng)Cache（MapAllocatorCache），內(nèi)部最多可以緩存32個(gè)不超過2M的VMA。

TSD:?定義了每個(gè)線程的本地緩存如何操作。目前有兩種模型實(shí)現(xiàn):獨(dú)占模型，其中每個(gè)線程擁有自己的緩存;或者共享模型，其中線程共享一個(gè)固定大小的緩存池。

對于64位andoridR/S，使用共享模型，且TSD pool只有兩個(gè)TSD對象，每個(gè)TSD對象分別含有一個(gè)SizeClassAllocatorLocalCache和QuarantineCache對象。

Qurantine: 提供延遲釋放內(nèi)存的方法，防止內(nèi)存塊立即再分配。一旦達(dá)到一定的大小標(biāo)準(zhǔn)，內(nèi)存塊將被回收。這本質(zhì)上是一個(gè)延遲的空閑鏈表，它可以幫助緩解一些釋放后使用的情況。這個(gè)特性在性能和內(nèi)存占用方面是相當(dāng)昂貴的，主要由運(yùn)行時(shí)選項(xiàng)控制，默認(rèn)情況下是禁用的。

如果配置了Quarantine，那么內(nèi)存釋放的時(shí)候符合大小限制的block會被暫時(shí)隔離，狀態(tài)設(shè)置為Quarantined，而不是Available，可以檢測UAF。首先嘗試放到線程TSD對應(yīng)的QuarantineCache中，如果local quarantine cache size超標(biāo)了，則把localquarantine cache中的內(nèi)存塊全部放到前端中的global quarantine cache中。如果global quarantine cache也超標(biāo)了，則recycle釋放到TSD->SizeClassAllocatorLocalCache。

2. Chunk Header

下面是chunkheader的詳細(xì)信息，后面的數(shù)字代表每個(gè)字段所占用的bit，加起來為64bits，也即8字節(jié)。

ClassId：表示內(nèi)存塊分配自Primary中的region id，ClassId為0表示從Secondary中分配。

State：表示內(nèi)存塊當(dāng)前狀態(tài)，0 Available，1 Allocated，2 Quarantined。

OriginOrWasZeroed：當(dāng)State為allocated時(shí)，表示通過哪種方式發(fā)生的分配，譬如是new或malloc。

SizeOrUnusedBytes：當(dāng)ClassId為正數(shù)指分配的size大小，當(dāng)ClassId為0時(shí)表示未使用的字節(jié)大小。

Offset：內(nèi)存塊中chunk header的偏移。

Checksum：校驗(yàn)和，用于檢測chunk header是否被破壞。

在一個(gè)內(nèi)存地址通過free/delete釋放時(shí)，該地址需要經(jīng)過重重檢測，以保證它在使用過程中是未經(jīng)破壞的。下面按時(shí)間順序列舉出一個(gè)chunk需要經(jīng)過的檢測。
1）alignment檢測：地址必須16字節(jié)對齊，如果是一個(gè)未經(jīng)對齊的long型數(shù)字被當(dāng)成了指針，這里就可以檢測出來misaligned pointer錯(cuò)誤。

2）checksum檢測：checksum數(shù)字在deallocate時(shí)會再計(jì)算一遍，和chunk header中保存的checksum進(jìn)行比較。如果二者不相等，則會報(bào)corrupted chunkheader錯(cuò)誤。

3）state檢測：如果chunk header的state不為Allocated，表明此時(shí)不應(yīng)該釋放這塊內(nèi)存，這很有可能是一個(gè)double-free，會報(bào)invalid chunk state錯(cuò)誤。

4）type檢測：如果分配時(shí)的方法和釋放的方法不匹配，會報(bào)allocationtype mismatch錯(cuò)誤 (前提是打開DeallocTypeMismatch選項(xiàng))。

5）size檢測：如果釋放時(shí)的size和chunk header中的size不相等，會報(bào)invalid sized delete錯(cuò)誤（前提是打開DeleteSizeMismatch選項(xiàng)）。

以上內(nèi)存釋放時(shí)的檢測環(huán)節(jié)都可以和AndroidScudo官方文檔中對于典型錯(cuò)誤對應(yīng)起來，以下是Android Scudo官方文檔中對于典型錯(cuò)誤信息的分析：1）corrupted chunk header：區(qū)塊頭的校驗(yàn)和驗(yàn)證失敗?？赡茉蛴卸簠^(qū)塊頭被部分或全部覆蓋，也可能是傳遞給函數(shù)的指針不是區(qū)塊。
2）race on chunk header：兩個(gè)不同的線程會同時(shí)嘗試操控同一區(qū)塊頭。這種癥狀通常是在對該區(qū)塊執(zhí)行操作時(shí)出現(xiàn)爭用情況或通常未進(jìn)行鎖定造成的。
3）invalid chunk state：對于指定操作，區(qū)塊未處于預(yù)期狀態(tài)，例如，在嘗試釋放區(qū)塊時(shí)其處于未分配狀態(tài)，或者在嘗試回收區(qū)塊時(shí)其未處于隔離狀態(tài)。雙重釋放是造成此錯(cuò)誤的典型原因。
4）misaligned pointer：強(qiáng)制執(zhí)行基本對齊要求：32 位平臺上為 8 個(gè)字節(jié)，64 位平臺上為 16 個(gè)字節(jié)。如果傳遞給函數(shù)的指針不適合這些函數(shù)，傳遞給其中一個(gè)函數(shù)的指針就不會對齊。
5）allocation type mismatch：啟用此選項(xiàng)后，在區(qū)塊上調(diào)用的取消分配函數(shù)必須與用于分配區(qū)塊而調(diào)用的函數(shù)類型一致。類型不一致會引發(fā)安全問題。
6）invalid sized delete：如果使用的是符合 C++14 標(biāo)準(zhǔn)的刪除運(yùn)算符，在啟用可選檢查之后，取消分配區(qū)塊時(shí)傳遞的大小與分配區(qū)塊時(shí)請求的大小會出現(xiàn)不一致的情況。這通常是由于編譯器出現(xiàn)問題或是對要取消分配的對象產(chǎn)生了類型混淆。7）RSS limit exhausted：已超出選擇性指定的 RSS 大小上限。

3. 內(nèi)存分配流程

Scudo中內(nèi)存分配流程如下圖所示：

1、??根據(jù)入?yún)ize計(jì)算真正需要從Allocator分配的NeededSize（入?yún)ize對齊到alignment再加上alignment和chunk headersize中較大的），如果NeededSize超過Primary Allocator最大的size class就從Secondary Allocator分配，走步驟2，否則走步驟4。

2、??從Secondary Allocator分配：對NeededSize+LargeBlock Header Size按照PageSize大小對齊得到RoundedSize。如果RoundedSize能從MapAllocatorCache中獲取成功，則直接獲取MapAllocatorCache中的內(nèi)存塊，走步驟6。否則走步驟3

3、??需要mmap大小為RoundedSize + 2Page的VM，前后各一個(gè)Page，作用類似RedZone，注意這次mmap的權(quán)限是PROT_NONE。之后會skip一個(gè)Page大小，再次以RW方式重新map一次，大小為RoundedSize。最后跳過LargeBlock Header，獲取內(nèi)存塊地址，繼續(xù)走步驟6。

4、??從Primary Allocator分配：Primary管理著每個(gè)size class的Region，分配時(shí)先獲取線程對應(yīng)的TSD中的SizeClassAllocatorLocalCache對象，嘗試從SizeClassAllocatorLocalCache其中獲取對應(yīng)size class的空閑內(nèi)存塊，若SizeClassAllocatorLocalCache中存在指定size class的空閑內(nèi)存塊，則獲取內(nèi)存塊地址，走步驟6。

5、??如果TSD中的SizeClassAllocatorLocalCache沒有指定size class的空閑內(nèi)存塊，則再回到Primary中去從Region中以RW（Region初始化過程雖然已經(jīng)map，但是為PROT_NONE）再次map適當(dāng)大小的內(nèi)存，填充到對應(yīng)region的freelist中（以TranserBatch為node），并從free list中取一個(gè)TransferBatch填充給SizeClassAllocatorLocalCache，SizeClassAllocatorLocalCache被填充后就可以取一個(gè)空閑內(nèi)存塊，繼續(xù)下一步。如果當(dāng)前region中空閑內(nèi)存塊已全部使用完，沒有則去更高一級region中分配，當(dāng)最高一級中也沒有合適的，則會從Secondary Allocator中分配。

6、獲取到空閑內(nèi)存塊后，繼續(xù)填充chunk header，并跳過chunk header返回內(nèi)存地址給用戶。

【文章福利】小編推薦自己的Linux內(nèi)核技術(shù)交流群:【749907784】整理了一些個(gè)人覺得比較好的學(xué)習(xí)書籍、視頻資料共享在群文件里面，有需要的可以自行添加哦?。。。ê曨l教程、電子書、實(shí)戰(zhàn)項(xiàng)目及代碼)? ??

4. 內(nèi)存釋放流程

Scudo中內(nèi)存釋放流程如下圖所示：

1、獲取內(nèi)存塊的chunk header，進(jìn)行相關(guān)檢查，如：會做checksum檢查，以及分配類型是否匹配：malloc/free，delete/new， 再根據(jù)入?yún)⒌膒tr獲得用戶分配的size大小做delete size mismatch檢查等。

2、釋放內(nèi)存有兩種去向，即是否需要進(jìn)行Quarantine，如果需要則進(jìn)行步驟3進(jìn)行Quarantine，否則釋放回Primary或Secondary, 走步驟4。

3、如果配置了Quarantine，并且釋放的時(shí)候符合大小限制的內(nèi)存塊會被暫時(shí)隔離，狀態(tài)設(shè)置為Quarantined，而不是Available，可以檢測UAF。首先嘗試放到線程TSD對應(yīng)的QuarantineCache對象（local quarantine cache size）中，如果localquarantine cache size超標(biāo)了，則把local quarantine cache中的內(nèi)存塊全部放到全局global quarantine cache中。如果global quarantinecache也超標(biāo)了，則回收釋放到Primary中。

4、通過chunk header的classid決定釋放到Primary還是Secondary中。class id = 0 代表是從Secondary Allocator分配。

5、對于Secondary Allocator，如果釋放的內(nèi)存塊小于2M，則先嘗試放到MapAllocatorCache的CachedBlock數(shù)組中，如果成功放入數(shù)組，會將當(dāng)前時(shí)間作為這個(gè)內(nèi)存塊釋放的時(shí)間，還會根據(jù)配置的gc時(shí)間間隔將數(shù)組中老化時(shí)間超過gc間隔的內(nèi)存塊釋放掉（通過madvise(MADV_DONTNEED)而不是unmap）。另外一種情況如果在放回CachedBlock數(shù)組的時(shí)候發(fā)現(xiàn)數(shù)組滿了，則會unmap數(shù)組中的所有內(nèi)存塊（累計(jì)發(fā)生4次數(shù)組滿的情況才會清空），同時(shí)當(dāng)前被釋放的block也會被unmap。

6、對于Primary Allocator，首先還是拿到當(dāng)前線程對應(yīng)的TSD并獲取TSD中的SizeClassAllocatorLocalCache對象，如果SizeClassAllocatorLocalCache不滿則直接放到cache中，free到此結(jié)束。如果SizeClassAllocatorLocalCache滿了，則將cache中一半數(shù)量的緩存內(nèi)存塊以TransferBatch為載體返回給Primary對應(yīng)Region的freelist中，之后會判斷是否需要做madvise釋放freelist中的空閑內(nèi)存塊占用的pss，判斷依據(jù)主要有當(dāng)前時(shí)間與上次釋放pss的間隔時(shí)間是否足夠，以及freelist中的內(nèi)存塊大小是否足夠大，至少要達(dá)到一個(gè)page等。最后再將當(dāng)前被釋放的內(nèi)存塊放到SizeClassAllocatorLocalCache中。

三、Scudo常用配置

Scudo被設(shè)計(jì)為高度可調(diào)和可配置的，雖然提供了一些默認(rèn)配置，但鼓勵用戶提出最適合他們用例的參數(shù)。
如Android Scudo官方文檔所描述，可以通過以下幾種方式針對各進(jìn)程定義分配器的一些參數(shù)：a、在編譯時(shí)，通過將SCUDO_DEFAULT_OPTIONS定義為默認(rèn)的選項(xiàng)字符串。
b、靜態(tài)：在程序中定義 __scudo_default_options函數(shù)（返回要解析的選項(xiàng)字符串）。該函數(shù)必須具有以下原型：extern "C" constchar *__scudo_default_options()。以這種方式定義的選項(xiàng)會替換編譯時(shí)定義的選項(xiàng)。例：extern"C" const char *__scudo_default_options(){return "delete_size_mismatch=false:release_to_os_interval_ms=-1"; }c、動態(tài)：使用環(huán)境變量 SCUDO_OPTIONS（包含要解析的選項(xiàng)字符串）。以這種方式定義的選項(xiàng)會替換通過 __scudo_default_options 定義的選項(xiàng)。例：SCUDO_OPTIONS="delete_size_mismatch=false:release_to_os_interval_ms=-1"./a.outd、通過標(biāo)準(zhǔn)的mallopt API，使用Scudo特有的參數(shù)。
主要可以使用以下選項(xiàng)：

下面是可用的" mallopt "選項(xiàng):

原文作者：內(nèi)核工匠