Micrium全家桶之uC-FS: 0x02 NAND FTL算法原理詳解

本文轉(zhuǎn)自公眾號(hào)，歡迎關(guān)注

Micrium全家桶之uC-FS: 0x02 NAND FTL算法原理詳解 (qq.com)

前言

uC-FS的NAND驅(qū)動(dòng)實(shí)現(xiàn)基于一篇論文:《KAST: K-Associative Sector Translation for NAND Flash Memory in Real-Time Systems》所以有必要先介紹下該論文的內(nèi)容,以便后面理解代碼的實(shí)現(xiàn)。

物理地址和邏輯地址的映射

NAND的特點(diǎn)是寫數(shù)據(jù)前必須擦除,即擦除后數(shù)據(jù)為1,寫只能由1寫為0.擦除單位為塊,寫數(shù)據(jù)單位為頁(yè),對(duì)于SLC塊一般由64個(gè)PAGE組成,而PAGE一般大小是2KB。

FTL管理物理地址和邏輯地址的映射,根據(jù)管理的顆粒度,可以分為塊(BLOCK)級(jí)別的映射,和頁(yè)(PAGE)級(jí)別的映射。前者更新數(shù)據(jù)以塊為單位,后者以頁(yè)為單位。

對(duì)于塊級(jí)別的管理,哪怕是只更新塊的一個(gè)PAGE的數(shù)據(jù),所有屬于該塊的不需要修改的PAGE數(shù)據(jù)和需要修改的PAGE的數(shù)據(jù)都需要重新寫入一個(gè)新開辟出來(lái)的物理塊中。使得管理成本變高。

為了獲得更高的性能,一般頁(yè)級(jí)別的管理用的更多。

假設(shè)一個(gè)塊由64個(gè)頁(yè)組成。開始時(shí)邏輯頁(yè)地址為0的PAGE,映射到第二個(gè)物理塊的第一個(gè)PAGE，其頁(yè)物理地址為64.那么當(dāng)需要更新邏輯地址為0的PAGE時(shí),只需要將更新的內(nèi)容寫入第65個(gè)物理PAGE,將映射表的對(duì)應(yīng)關(guān)系，由邏輯PAGE地址為0映射原來(lái)的物理PAGE地址64，改為映射物理PAGE地址65。因?yàn)镹AND是塊擦除，PAGE編程，所以塊擦除后后面的PAGE寫不再需要擦除。后續(xù)再繼續(xù)更新邏輯PAGE地址0的時(shí)候，再往后映射到66等等，直到最后映射到第127個(gè)物理頁(yè)。此時(shí)再更新邏輯PAGE0時(shí)則需要將第二個(gè)物理塊的內(nèi)容復(fù)制到新開辟的塊中了，然后將該物理塊擦除又可以作為新的更新塊使用。注:上述的物理塊2即為更新塊或者LOG塊, 可以看出基于頁(yè)的管理擦除次數(shù)遠(yuǎn)低于基于塊的管理,后者每更新一個(gè)PAGE都需要擦除一個(gè)塊然后寫一個(gè)塊，而前者擦除次數(shù)大大減少。

基于PAGE管理的缺點(diǎn)是需要更大的映射表緩存，因?yàn)轭w粒度變小了，一個(gè)PAGE就需要一個(gè)映射項(xiàng)，這對(duì)于嵌入式領(lǐng)域尤其是資源受限的場(chǎng)景是一個(gè)限制。

塊回收

以上舉例的是基于更新塊，LOG的方式，即更新一個(gè)邏輯PAGE的內(nèi)容不是直接修改其對(duì)應(yīng)的物理PAGE的內(nèi)容,而是將其內(nèi)容寫入一個(gè)更新塊的某個(gè)PAGE,然后修改其映射關(guān)系,直到更新塊寫完或者更新塊不夠用了，然后將更新塊的內(nèi)容寫入一個(gè)新開辟的塊，修改映射關(guān)系，此時(shí)原來(lái)的塊就是無(wú)效的了。隨著修改的增多無(wú)效塊越來(lái)越多，無(wú)法開辟新的塊了此時(shí)就需要回收無(wú)效塊。

需要注意的是上述無(wú)效塊中可能有一部分PAGE是包含有效數(shù)據(jù)一部分是無(wú)效數(shù)據(jù)的，所以如果需要回收，需要將其有效數(shù)據(jù)復(fù)制到新開辟的塊中，然后擦除該無(wú)效塊，此時(shí)該塊就可以作為后續(xù)開辟塊使用了。上述回收工作需要遍歷所有塊的所有PAGE是一個(gè)非常耗時(shí)的過程，并且時(shí)間是波動(dòng)的，且波動(dòng)很大，這種波動(dòng)是不適合嵌入式場(chǎng)景的，尤其是實(shí)時(shí)系統(tǒng)的。

混合管理

綜合塊管理的性能低，管理消耗大，需要緩存低；頁(yè)管理的需要緩存大，性能高，管理消耗低的優(yōu)缺點(diǎn)，混合管理方式是一個(gè)妥協(xié)或者綜合的方式。

很多領(lǐng)域在面對(duì)矛盾的時(shí)候解決辦法就是綜合，妥協(xié)取中間，這也契合中庸的哲學(xué)思想。

這種綜合的方式

將物理塊分為數(shù)據(jù)塊DATA BLOCK和日志塊LOG BLOCK，日志塊稱為L(zhǎng)OG BUFFER，基于該方式的FTL即稱為log buffer-based FTL。所謂的綜合或者混合即LOG BLOCK采用PAGE級(jí)別的管理，而DATA BLOCK采用塊級(jí)別的管理。LOG BLOCK的最大數(shù)量決定了PAGE級(jí)別映射表的大小。當(dāng)有寫更新請(qǐng)求時(shí)，先將更新數(shù)據(jù)寫入LOG BLOCK原來(lái)舊的DATA BLOCK的數(shù)據(jù)設(shè)置為無(wú)效，如果LOG塊寫滿且沒有空閑的LOG塊時(shí)則需要將LOG塊的有效內(nèi)容(注意LOG塊中不一定全部是有效數(shù)據(jù))移動(dòng)到空閑的DATA塊中，然后擦除LOG塊以便后面繼續(xù)作為L(zhǎng)OG BUFFER使用。上述過程即稱為塊合并block merge。

block merge是基于LOG塊的，只有LOG塊寫滿且無(wú)LOG塊可用時(shí)才會(huì)執(zhí)行merge，所以其比基于PAGE的管理的垃圾回收消耗低很多，而又不需要太大的映射表緩存(因?yàn)榛赑AGE管理的LOG塊數(shù)量不多)，所以更適合于嵌入式系統(tǒng)。

塊關(guān)聯(lián)映射block associative mapping (BAST Block Associative Sector Translation )

一個(gè)LOG塊只關(guān)聯(lián)一個(gè)DATA塊,即只有同一個(gè)DATA塊的PAGE數(shù)據(jù)可以寫入同一個(gè)LOG塊。

如上圖LLBN表示LOG塊邏輯地址,這里有4個(gè)LOG塊分別是L0~L3

LBN表示DATA塊邏輯地址,這里有6個(gè)DATA塊,分別是B0~B5

LPN表示PAGE邏輯地址

每個(gè)塊有4個(gè)PAGE。

當(dāng)PAGE有更新時(shí),將PAGE數(shù)據(jù)寫入LOG塊,同時(shí)將DATA塊中的PAGE置為無(wú)效(灰色部分)

假設(shè)按照p16 p20 p1 p5的次序更新，最開始更新p16時(shí)將p16寫入L0,設(shè)置B4中的p16無(wú)效，然后更新p20，此時(shí)L0中已經(jīng)有關(guān)聯(lián)的B4的數(shù)據(jù)了，由于一個(gè)LOG塊只能關(guān)聯(lián)一個(gè)DATA塊，所以p20不能寫入L0，只能找后續(xù)的寫入L1，后面的p1寫入L2，p5寫入L3也是同樣的道理。此時(shí)如果繼續(xù)有B2和B3的PAGE需要更新，而此時(shí)4個(gè)LOG塊都關(guān)聯(lián)了非B2和B3的塊，此時(shí)就需要merge LOG塊，釋放LOG塊來(lái)關(guān)聯(lián)新的B2和B3的修改。

如果數(shù)據(jù)更新是隨機(jī)的，那么BAST性能會(huì)比較差，因?yàn)檫@會(huì)導(dǎo)致頻繁的MERGE操作，因?yàn)橐粋€(gè)LOG塊只能映射一個(gè)DATA塊，隨機(jī)的多個(gè)DATA塊更新很快就使得LOG塊不夠用需要MERGE。這即所謂的LOG塊抖動(dòng)問題log block thrashing problem。

同時(shí)上述過程可以看到每次LOG塊MERGE時(shí)只有一個(gè)PAGE有效，剩余的3個(gè)PAGE是空的，所以空間利用率很低。

全關(guān)聯(lián)映射fully associative mapping (FAST Fully Associative SectorTranslation )

一個(gè)LOG塊可關(guān)聯(lián)任意的DATA塊,一個(gè)LOG塊可以寫入任意DATA塊的數(shù)據(jù)。

該方式可以解決BAST的LOG塊抖動(dòng)問題。

如上圖所示一個(gè)LOG塊可以關(guān)聯(lián)任意的DATA塊，所以只有一個(gè)LOG塊的所有PAGE寫滿才會(huì)執(zhí)行MERGE，所以大大減少了MERGE操作。

PAGE按更新次序依次寫入LOG塊，而不管它來(lái)自于哪個(gè)DATA塊，這可以解決LOG塊抖動(dòng)問題。

上述示例的是按照p0, p4, p8, p12, p16, p20,p1, p5 的更新次序，先寫滿L0，然后寫滿L1，此時(shí)都還不需要進(jìn)行MERGE，而如果是BAST從p16開始就需要merge了。

特別的FAST會(huì)使用一個(gè)sequential log block (SLB) 塊。該塊只關(guān)聯(lián)一個(gè)DATA塊，且該塊內(nèi)的PAGE按照in-place scheme 機(jī)制寫(按照PAGE的邏輯地址順序和偏移依次對(duì)應(yīng)寫)，所以SLB可以采用switch merge 和 partial merge方式。

然而FAST也有缺點(diǎn)，即一個(gè)LOG塊可以關(guān)聯(lián)任意的DATA塊，所以MERGE操作消耗非常大，比如上述的L0關(guān)聯(lián)了4個(gè)DATA塊，所以MERGE時(shí)需要更新4個(gè)BLOCK的數(shù)據(jù)，需要擦除4個(gè)塊，每個(gè)塊有4個(gè)PAGE所以需要拷貝4次PAGE，一共需要拷貝4x4=16個(gè)PAGE。而BAST只關(guān)聯(lián)一個(gè)DATA BLOCK沒有這個(gè)問題。

定義DATA塊關(guān)聯(lián)到LOG塊L的集合A(L),A(L)中元素的個(gè)數(shù)表示L的關(guān)聯(lián)性，表示為k(L)

所以LOG塊的MERGE消耗是

N · k(L) · Ccopy + (k(L) + 1) · Cerase

擦除次數(shù)是k(L) + 1,所有關(guān)聯(lián)的DATA塊需要擦除，還有LOG塊也需要擦除。

復(fù)制次數(shù)是N · k(L)，N是每個(gè)塊的PAGE數(shù)，k(L)個(gè)DATA塊即k(L)*N

k(l)最大即為塊中PAGE數(shù)N。所以最壞的merge時(shí)間是N^2Ccopy +(N +1)Cerase。

由于N的變化范圍很大，比如SLC一般是一個(gè)塊是64個(gè)PAGE，MLC是128個(gè)PAGE所以k(L)變化很大，所以上述公式計(jì)算出來(lái)的最好和最壞情況差別很大，也就是程序運(yùn)行時(shí)間抖動(dòng)很大，不適合嵌入式系統(tǒng)使用。

組關(guān)聯(lián)映射set associative mapping (SAST Set Associative Sector

Translation )

一組LOG塊可以關(guān)聯(lián)一組DATA塊的PAGE。

N個(gè)LOG塊只能用于K個(gè)DATA塊，即N:K log block mapping 。

所以LOG塊最大的塊關(guān)聯(lián)度是k。

如上圖所示是

2:3 mapping SAST 2個(gè)LOG塊最多只能關(guān)聯(lián)3個(gè)DATA塊。

所以SAST是BAST和FAST的中間妥協(xié)版本，可以綜合優(yōu)化但是不能完全解決兩者的問題。

MERGE

前面提到的LOG塊的MERGE分為三種

full merge,

Partial **merge ** , switch merge

Partial merge即LOG塊中只有部分PAGE，這些PAGE是按照邏輯PAGE的次序和偏移對(duì)應(yīng)的，還有一些間隙此時(shí)需要從DATA塊中復(fù)制這些間隙PAGE，然后和LOG塊中的內(nèi)容一起寫入新的DATA塊。

switch merge即LOG塊中已經(jīng)是和一個(gè)DATA塊對(duì)應(yīng)的序列PAGE，且寫滿，可以直接變?yōu)镈ATA塊。

Partial merge 和switch merge 只有LOG塊內(nèi)的PAGE是按照邏輯PAGE地址對(duì)應(yīng)的PAGE偏移順序?qū)懭霑r(shí)才有可能，這種方式稱為in-place機(jī)制。

KAST:K-associative mapping

BAST的MERGE太頻繁性能差，而FAST則是MERGE不頻繁但是每次MERGE的時(shí)間差異很大，都有缺點(diǎn)。所以都不適合嵌入式系統(tǒng)。

此時(shí)我們又要用到中庸思想了，本論文提出的K-associative mapping即類似于FAST，但是限制其關(guān)聯(lián)度，以減少最壞情況的消耗。

KAST整體架構(gòu)

有以下特征

l減少LOG的關(guān)聯(lián)度,不同的LBNs 更新盡可能對(duì)應(yīng)不同的LOG塊,類似于BAST。

lLOG塊最多只關(guān)聯(lián)K個(gè)DATA塊。保證 k(L) ≤ K，通過控制參數(shù)K控制最壞的MERGE時(shí)間

l包含多個(gè)SLBs ,不同于FAST只有一個(gè)SLB。SLBs的個(gè)數(shù)通過參數(shù)配置。

如果沒有后續(xù)的順序?qū)懭胝?qǐng)求，則可以將SLB更改為隨機(jī)日志塊（RLB），這里是一個(gè)很重要的思想，即動(dòng)態(tài)變化，不死板，既然后面沒有連續(xù)的PAGE寫入了，就認(rèn)為是隨機(jī)寫，就把他作為RLB塊來(lái)用，這種思想值得借鑒，即走一步看一步，結(jié)合實(shí)際情況進(jìn)行決定。

SAST也是通過將K個(gè)數(shù)據(jù)塊與日志塊集相關(guān)聯(lián)，使日志塊的塊關(guān)聯(lián)性低于K，通過對(duì)數(shù)據(jù)塊和日志塊進(jìn)行分組，SAST可以在無(wú)形中解決塊抖動(dòng)問題。

但KAST不將數(shù)據(jù)塊和日志塊分組，只是限制LOG塊的最大關(guān)聯(lián)度，這是不同點(diǎn)。

此外，KAST試圖通過在不同的日志塊之間分配不同LBN上的寫請(qǐng)求來(lái)最小化每個(gè)日志塊L的k（L）的值

如上是一個(gè)kAST的示例

寫序列p0, p4, p8, p12, p16, p20,p1, p5 ，KAST為不同的數(shù)據(jù)塊分配寫請(qǐng)求。

首先，頁(yè)面p0、p4、p8和p12被寫入不同的日志塊，這是盡可能減少LOG塊關(guān)聯(lián)的DATA塊數(shù)的思想。

然后p16和p20沒辦法只能關(guān)聯(lián)到L0和L1增加這兩個(gè)LOG塊的關(guān)聯(lián)度，注意這里是分配到L0和L1而不是都分配到L0，同樣是上述盡可能減少LOG塊關(guān)聯(lián)的DATA塊數(shù)的思想。

最后，頁(yè)p1和p5被寫入日志塊L0和L1，因?yàn)閜1所在的DATA塊已經(jīng)有p0在L0中了，所以p1放在 L0中不增加日志塊的關(guān)聯(lián)性，同樣是上述的思想。

總之一句話即盡可能減少LOG塊的關(guān)聯(lián)性，即減小 k ( L ) 。只有LOG快不夠了再去考慮增加LOG塊的關(guān)聯(lián)度。作為一種特殊情況，SLB只與一個(gè)數(shù)據(jù)塊相關(guān)聯(lián)。當(dāng)日志塊被分配時(shí)，它被確定為SLB或RLB。

以下是LOG塊的狀態(tài)機(jī)

F , S Ri 狀態(tài)分別表示空閑SLB，和i關(guān)聯(lián)度的RLB。

初始化狀態(tài)是F，即LOG塊是空閑的沒有關(guān)聯(lián)數(shù)據(jù)。

F狀態(tài)可變?yōu)镾或者R1狀態(tài)，

Ri狀態(tài)寫PAGE，如果該P(yáng)AGE已經(jīng)屬于之前關(guān)聯(lián)的塊了則不增加關(guān)聯(lián)度，狀態(tài)不變，否則關(guān)聯(lián)度增加，變?yōu)镽i+1狀態(tài)。

如果SLB狀態(tài)寫PAGE，維持其次序，則SLB狀態(tài)S也不改變。

Ri+1也可以變?yōu)镽i狀態(tài)，如果對(duì)應(yīng)的PAGE寫到了其他的LOG塊，本LOG塊的PAGE設(shè)置為了無(wú)效。

只有在SLB的一小部分被有效數(shù)據(jù)占用的情況下，SLB才能變?yōu)闋顟B(tài)為R1或R2的RLB。

partial 或switch merge 操作將SLB日志塊改變?yōu)镕狀態(tài)，

full merge 操作將RLB改變?yōu)镕狀態(tài)，Ri狀態(tài)的RLB full merge消耗為N · i · Ccopy + (i + 1) · Cerase.

寫LOG BUFFER

當(dāng)一個(gè)PAGE需要寫入LOG BUFFER時(shí),需要查找LOG塊中有空閑空間的寫入，如果找不到則需要進(jìn)行l(wèi)og block merge操作，這個(gè)過程比較復(fù)雜，如下

首先查找是否有RLB，這個(gè)RLB中已經(jīng)有了待寫入PAGE對(duì)應(yīng)的DATA塊的其他PAGE，如果有則可以將PAGE寫入該RLB而不增加關(guān)聯(lián)度，如下圖的(b)。

如果這個(gè)PAGE在DATA塊中的偏移是0，可以將這個(gè)塊寫入SLB的第一個(gè)PAGE，因?yàn)槲覀儾聹y(cè)后續(xù)可能是連續(xù)的序列操作，這樣可以都放入一個(gè)SLB可以使用部分或者switch merge。如果后面不是序列寫也沒關(guān)系，可以再變?yōu)镽LB,如下圖的(c)。。

那么如果以上兩個(gè)條件都滿足呢? 這時(shí)我們先按照(b)Append的策略寫入RLB而先不去搜索SLB。

然后再單獨(dú)分配一個(gè)SLB。

直到后續(xù)后面RLB中的PAGE又有需要更新時(shí)，再將RLB中的PAGE序列寫入SLB中，將RLB中的PAGE設(shè)置為無(wú)效，如下圖(d)

開始時(shí)(a)->更新p0->p0放入RLB中->更新p1 p5->將p0 p1 p5按照page序號(hào)偏移寫入SLB->從DATA塊中復(fù)制未更新的p2 p3 p4到SLB中補(bǔ)齊。

以上的思想是猜測(cè)更新塊的第一個(gè)PAGE時(shí)可能不是隨機(jī)寫，后面可能有連續(xù)次序更新所以使用SLB。

如果需要更新的PAGE所在的塊已經(jīng)和一個(gè)SLB關(guān)聯(lián)，則需要將這個(gè)PAGE寫入這個(gè)SLB。如果這個(gè)寫不需要破壞SLB中原來(lái)PAGE的次序則可以直接寫入。

如果寫入這個(gè)PAGE和原來(lái)SLB中已有的PAGE中間有一個(gè)小間隙，則可以直接寫入，如下圖(b),原來(lái)SLB中有p0 p1 p2更新p5則可以直接寫入該SLB，中間p3 p4需要padding。

而如果上述間隙比較大，或者SLB中已經(jīng)有了相應(yīng)的PAGE，如下圖SLB中已經(jīng)有了p0 p1 p2 此時(shí)認(rèn)為后面間隙比較大，或者已經(jīng)有了p0 p1 p2 p5，此時(shí)要更新p5，p5已經(jīng)在SLB中了，這兩種情況都又有兩種策略

第一種是使用partial merge，先將SLB merge到DATA塊， merge同時(shí)更新p5到DATA塊.

間隙的p3 p4 p6 p7需要從DATA塊中拷貝出來(lái)，一并merge到新的DATA塊中，如下圖(c)。

還有一種策略，如(d)將p5添加到SLB中，此時(shí)p5和前面的p0~p1不屬于同一個(gè)DATA塊則增加了關(guān)聯(lián)度。只有當(dāng)SLB中free page比較多時(shí)采用后者，因?yàn)檫@種情況我們猜測(cè)后續(xù)的序列更新的概率很小。此外，既然SLB中有很多空閑頁(yè)面，那么最好繼續(xù)使用，而不是執(zhí)行部分合并。

如果找不到上述LOG塊，即更新的PAGE所在的DATA塊已經(jīng)和LOG關(guān)聯(lián)，那么就只能增加LOG塊的關(guān)聯(lián)度。

下一步進(jìn)行時(shí)先檢查是否有SLB已經(jīng)完成的(即已經(jīng)按序列寫滿)，如果有則擦除這個(gè)SLB對(duì)應(yīng)的DATA塊，將這個(gè)SLB變?yōu)镈ATA塊，即switch merge。

由于交換機(jī)合并沒有頁(yè)面復(fù)制開銷，因此利用它比增加任何其他日志塊的塊關(guān)聯(lián)性更好。

如果PAGE的偏移是0，則跳過上述處理，直接先merge一個(gè)LOG塊，作為新SLB使用。

上述處理實(shí)際是選擇要犧牲掉哪一個(gè)LOG塊RLB去進(jìn)行MERGE，RLB的關(guān)聯(lián)度比較低，且空閑PAGE較多的有線選擇。這是出于平衡LOG塊的關(guān)聯(lián)度和空閑PAGE數(shù)。只要LOG塊的關(guān)聯(lián)度小于我們?cè)O(shè)置的K則可以增加其關(guān)聯(lián)度。

即使有一個(gè)SLB，待更新PAGE的DATA塊和該SLB無(wú)關(guān)聯(lián)，如果該SLB的空閑PAGE比較多，我們依然可以將該P(yáng)AGE寫入該SLB，增加了關(guān)聯(lián)度，但是降低了MERGE頻率，因?yàn)榭赡芎荛L(zhǎng)時(shí)間都不需要MERGE。此時(shí)SLB變?yōu)榱薘LB。

如果沒有LOG塊的關(guān)聯(lián)度小于K且有空閑塊，則無(wú)法將PAGE寫入LOG塊。

第三步則是MERGE LOG塊以或者空閑LOG塊。

首先考慮的是否有SLB可以partial merge的。如果SLB中有許多空閑PAGE，我們先不執(zhí)行partial merge，繼續(xù)保持SLB，延遲SLB的partial merge，我們可以將它用于未來(lái)的后續(xù)更新請(qǐng)求。

然后考慮的是MERGE RLB的MERGE消耗最小，空閑PAGE最小的，消耗的大小由關(guān)聯(lián)度來(lái)確定。MERGE一個(gè)LOG塊之后就有空閑的LOG塊繼續(xù)使用了。

總結(jié)

本文對(duì)uC-FS的NAND驅(qū)動(dòng)所基于的算法論文進(jìn)行了詳解，對(duì)算法有了一個(gè)整體的了解。算法到代碼的實(shí)現(xiàn)還有一個(gè)很復(fù)雜的過程，需要考慮各種細(xì)節(jié)，所以以上只是一個(gè)整體概覽。后面我們會(huì)繼續(xù)分析其代碼的實(shí)現(xiàn)細(xì)節(jié)。

審核編輯：湯梓紅