本文轉自公眾號，歡迎關注

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

前言

uC-FS的NAND驅動實現基于一篇論文:《KAST: K-Associative Sector Translation for NAND Flash Memory in Real-Time Systems》所以有必要先介紹下該論文的內容,以便后面理解代碼的實現。

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

NAND的特點是寫數據前必須擦除,即擦除后數據為1,寫只能由1寫為0.擦除單位為塊,寫數據單位為頁,對于SLC塊一般由64個PAGE組成,而PAGE一般大小是2KB。

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

對于塊級別的管理,哪怕是只更新塊的一個PAGE的數據,所有屬于該塊的不需要修改的PAGE數據和需要修改的PAGE的數據都需要重新寫入一個新開辟出來的物理塊中。使得管理成本變高。

為了獲得更高的性能,一般頁級別的管理用的更多。

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

基于PAGE管理的缺點是需要更大的映射表緩存，因為顆粒度變小了，一個PAGE就需要一個映射項，這對于嵌入式領域尤其是資源受限的場景是一個限制。

塊回收

以上舉例的是基于更新塊，LOG的方式，即更新一個邏輯PAGE的內容不是直接修改其對應的物理PAGE的內容,而是將其內容寫入一個更新塊的某個PAGE,然后修改其映射關系,直到更新塊寫完或者更新塊不夠用了，然后將更新塊的內容寫入一個新開辟的塊，修改映射關系，此時原來的塊就是無效的了。隨著修改的增多無效塊越來越多，無法開辟新的塊了此時就需要回收無效塊。

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

混合管理

綜合塊管理的性能低，管理消耗大，需要緩存低；頁管理的需要緩存大，性能高，管理消耗低的優缺點，混合管理方式是一個妥協或者綜合的方式。

很多領域在面對矛盾的時候解決辦法就是綜合，妥協取中間，這也契合中庸的哲學思想。

這種綜合的方式

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

block merge是基于LOG塊的，只有LOG塊寫滿且無LOG塊可用時才會執行merge，所以其比基于PAGE的管理的垃圾回收消耗低很多，而又不需要太大的映射表緩存(因為基于PAGE管理的LOG塊數量不多)，所以更適合于嵌入式系統。

塊關聯映射block associative mapping (BAST Block Associative Sector Translation )

一個LOG塊只關聯一個DATA塊,即只有同一個DATA塊的PAGE數據可以寫入同一個LOG塊。

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

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

LPN表示PAGE邏輯地址

每個塊有4個PAGE。

當PAGE有更新時,將PAGE數據寫入LOG塊,同時將DATA塊中的PAGE置為無效(灰色部分)

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

如果數據更新是隨機的，那么BAST性能會比較差，因為這會導致頻繁的MERGE操作，因為一個LOG塊只能映射一個DATA塊，隨機的多個DATA塊更新很快就使得LOG塊不夠用需要MERGE。這即所謂的LOG塊抖動問題log block thrashing problem。

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

全關聯映射fully associative mapping (FAST Fully Associative SectorTranslation )

一個LOG塊可關聯任意的DATA塊,一個LOG塊可以寫入任意DATA塊的數據。

該方式可以解決BAST的LOG塊抖動問題。

如上圖所示一個LOG塊可以關聯任意的DATA塊，所以只有一個LOG塊的所有PAGE寫滿才會執行MERGE，所以大大減少了MERGE操作。

PAGE按更新次序依次寫入LOG塊，而不管它來自于哪個DATA塊，這可以解決LOG塊抖動問題。

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

特別的FAST會使用一個sequential log block (SLB) 塊。該塊只關聯一個DATA塊，且該塊內的PAGE按照in-place scheme 機制寫(按照PAGE的邏輯地址順序和偏移依次對應寫)，所以SLB可以采用switch merge 和 partial merge方式。

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

定義DATA塊關聯到LOG塊L的集合A(L),A(L)中元素的個數表示L的關聯性，表示為k(L)

所以LOG塊的MERGE消耗是

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

擦除次數是k(L) + 1,所有關聯的DATA塊需要擦除，還有LOG塊也需要擦除。

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

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

由于N的變化范圍很大，比如SLC一般是一個塊是64個PAGE，MLC是128個PAGE所以k(L)變化很大，所以上述公式計算出來的最好和最壞情況差別很大，也就是程序運行時間抖動很大，不適合嵌入式系統使用。

組關聯映射set associative mapping (SAST Set Associative Sector

Translation )

一組LOG塊可以關聯一組DATA塊的PAGE。

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

所以LOG塊最大的塊關聯度是k。

如上圖所示是

2:3 mapping SAST 2個LOG塊最多只能關聯3個DATA塊。

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

MERGE

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

full merge,

Partial **merge ** , switch merge

Partial merge即LOG塊中只有部分PAGE，這些PAGE是按照邏輯PAGE的次序和偏移對應的，還有一些間隙此時需要從DATA塊中復制這些間隙PAGE，然后和LOG塊中的內容一起寫入新的DATA塊。

switch merge即LOG塊中已經是和一個DATA塊對應的序列PAGE，且寫滿，可以直接變為DATA塊。

Partial merge 和switch merge 只有LOG塊內的PAGE是按照邏輯PAGE地址對應的PAGE偏移順序寫入時才有可能，這種方式稱為in-place機制。

KAST:K-associative mapping

BAST的MERGE太頻繁性能差，而FAST則是MERGE不頻繁但是每次MERGE的時間差異很大，都有缺點。所以都不適合嵌入式系統。

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

KAST整體架構

有以下特征

l減少LOG的關聯度,不同的LBNs 更新盡可能對應不同的LOG塊,類似于BAST。

lLOG塊最多只關聯K個DATA塊。保證 k(L) ≤ K，通過控制參數K控制最壞的MERGE時間

l包含多個SLBs ,不同于FAST只有一個SLB。SLBs的個數通過參數配置。

如果沒有后續的順序寫入請求，則可以將SLB更改為隨機日志塊（RLB），這里是一個很重要的思想，即動態變化，不死板，既然后面沒有連續的PAGE寫入了，就認為是隨機寫，就把他作為RLB塊來用，這種思想值得借鑒，即走一步看一步，結合實際情況進行決定。

SAST也是通過將K個數據塊與日志塊集相關聯，使日志塊的塊關聯性低于K，通過對數據塊和日志塊進行分組，SAST可以在無形中解決塊抖動問題。

但KAST不將數據塊和日志塊分組，只是限制LOG塊的最大關聯度，這是不同點。

此外，KAST試圖通過在不同的日志塊之間分配不同LBN上的寫請求來最小化每個日志塊L的k（L）的值

如上是一個kAST的示例

寫序列p0, p4, p8, p12, p16, p20,p1, p5 ，KAST為不同的數據塊分配寫請求。

首先，頁面p0、p4、p8和p12被寫入不同的日志塊，這是盡可能減少LOG塊關聯的DATA塊數的思想。

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

最后，頁p1和p5被寫入日志塊L0和L1，因為p1所在的DATA塊已經有p0在L0中了，所以p1放在 L0中不增加日志塊的關聯性，同樣是上述的思想。

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

以下是LOG塊的狀態機

F , S Ri 狀態分別表示空閑SLB，和i關聯度的RLB。

初始化狀態是F，即LOG塊是空閑的沒有關聯數據。

F狀態可變為S或者R1狀態，

Ri狀態寫PAGE，如果該PAGE已經屬于之前關聯的塊了則不增加關聯度，狀態不變，否則關聯度增加，變為Ri+1狀態。

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

Ri+1也可以變為Ri狀態，如果對應的PAGE寫到了其他的LOG塊，本LOG塊的PAGE設置為了無效。

只有在SLB的一小部分被有效數據占用的情況下，SLB才能變為狀態為R1或R2的RLB。

partial 或switch merge 操作將SLB日志塊改變為F狀態，

full merge 操作將RLB改變為F狀態，Ri狀態的RLB full merge消耗為N · i · Ccopy + (i + 1) · Cerase.

寫LOG BUFFER

當一個PAGE需要寫入LOG BUFFER時,需要查找LOG塊中有空閑空間的寫入，如果找不到則需要進行log block merge操作，這個過程比較復雜，如下

首先查找是否有RLB，這個RLB中已經有了待寫入PAGE對應的DATA塊的其他PAGE，如果有則可以將PAGE寫入該RLB而不增加關聯度，如下圖的(b)。

如果這個PAGE在DATA塊中的偏移是0，可以將這個塊寫入SLB的第一個PAGE，因為我們猜測后續可能是連續的序列操作，這樣可以都放入一個SLB可以使用部分或者switch merge。如果后面不是序列寫也沒關系，可以再變為RLB,如下圖的(c)。。

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

然后再單獨分配一個SLB。

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

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

以上的思想是猜測更新塊的第一個PAGE時可能不是隨機寫，后面可能有連續次序更新所以使用SLB。

如果需要更新的PAGE所在的塊已經和一個SLB關聯，則需要將這個PAGE寫入這個SLB。如果這個寫不需要破壞SLB中原來PAGE的次序則可以直接寫入。

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

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

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

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

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

如果找不到上述LOG塊，即更新的PAGE所在的DATA塊已經和LOG關聯，那么就只能增加LOG塊的關聯度。

下一步進行時先檢查是否有SLB已經完成的(即已經按序列寫滿)，如果有則擦除這個SLB對應的DATA塊，將這個SLB變為DATA塊，即switch merge。

由于交換機合并沒有頁面復制開銷，因此利用它比增加任何其他日志塊的塊關聯性更好。

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

上述處理實際是選擇要犧牲掉哪一個LOG塊RLB去進行MERGE，RLB的關聯度比較低，且空閑PAGE較多的有線選擇。這是出于平衡LOG塊的關聯度和空閑PAGE數。只要LOG塊的關聯度小于我們設置的K則可以增加其關聯度。

即使有一個SLB，待更新PAGE的DATA塊和該SLB無關聯，如果該SLB的空閑PAGE比較多，我們依然可以將該PAGE寫入該SLB，增加了關聯度，但是降低了MERGE頻率，因為可能很長時間都不需要MERGE。此時SLB變為了RLB。

如果沒有LOG塊的關聯度小于K且有空閑塊，則無法將PAGE寫入LOG塊。

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

首先考慮的是否有SLB可以partial merge的。如果SLB中有許多空閑PAGE，我們先不執行partial merge，繼續保持SLB，延遲SLB的partial merge，我們可以將它用于未來的后續更新請求。

然后考慮的是MERGE RLB的MERGE消耗最小，空閑PAGE最小的，消耗的大小由關聯度來確定。MERGE一個LOG塊之后就有空閑的LOG塊繼續使用了。

總結

本文對uC-FS的NAND驅動所基于的算法論文進行了詳解，對算法有了一個整體的了解。算法到代碼的實現還有一個很復雜的過程，需要考慮各種細節，所以以上只是一個整體概覽。后面我們會繼續分析其代碼的實現細節。

審核編輯：湯梓紅