0 簡介
LittleFs設(shè)計之初的重點特性是：
（1）低資源消耗；
（2）掉電保護；
（3）擦寫均衡，
本章節(jié)重點討論第（2）和（3）這兩個特性，第（1）個特性則貫穿在整個設(shè)計過程中。后文把LittleFs簡稱為lfs。
1 具體功能介紹
1.1 掉電保護
最經(jīng)典的掉電保護方法有兩種，一種是使用日志，一種是通過COW方式。lfs結(jié)合了兩種方法，并優(yōu)化了兩種方案的缺點，提供了一套掉電保護策略。
1.1.1 日志方式
具體步驟為：
（1） 寫入數(shù)據(jù)之前，先在日志區(qū)存儲開始標志，記錄要寫入的數(shù)據(jù)位置和大?。?br>
（2） 待寫入的數(shù)據(jù)寫入日志區(qū)；
（3） 待寫入的數(shù)據(jù)寫入數(shù)據(jù)區(qū)；
（4） 寫入完成之后，在日志區(qū)記錄結(jié)束標志。
模擬掉電場景：
（1） 步驟1完成，步驟2沒有完成；重啟之后，保持原來的數(shù)據(jù)，日志無效；
（2） 步驟1，2完成了，步驟3沒有完成，嘗試把步驟2的數(shù)據(jù)寫入到數(shù)據(jù)區(qū)；
（3） 步驟1,2,3完成了，步驟4沒有完成，同樣嘗試把步驟2的數(shù)據(jù)寫入到數(shù)據(jù)區(qū)；
1.1.2 Cow機制
具體步驟為：
（1） 想更新節(jié)點F的數(shù)據(jù)，先申請一個新的節(jié)點，把F的舊數(shù)據(jù)拷貝過去，然后更新新的數(shù)據(jù)；
（2） 把父節(jié)點的指針指向新的節(jié)點，去掉舊節(jié)點的指針。
模擬掉電場景：
（1）步驟（1）完成了，步驟（2）沒有完成，則使用舊的數(shù)據(jù)，新的節(jié)點變成孤兒節(jié)點。
1.1.3 lfs掉電保護
lfs結(jié)合了日志方式和COW機制兩種方式進行掉電保護，并且優(yōu)化了兩種方案。
前面談過文件系統(tǒng)三要素，超級塊，inode，以及數(shù)據(jù)。對應lfs來說，他把超級塊以及inode通過日志的方式存儲，兩種采用統(tǒng)一的存儲結(jié)構(gòu)，后文稱兩者為元數(shù)據(jù)；普通數(shù)據(jù)則采用cow的方式存儲，采用czt逆序鏈表的方式。
1.1.3.1 元數(shù)據(jù)的存儲
元數(shù)據(jù)（對應root，dir）采用雙block的方式存儲，互為備份，每個block都有一個revision序號，值越大，表示block的數(shù)據(jù)越新，每個block默認可以存儲最多0xff個文件的數(shù)據(jù)，如果超過這個值，則需要compact（壓縮）。
Compact是干什么呢？ 即當數(shù)據(jù)的大小大于某個值的時候，把數(shù)據(jù)整合，剔除同一個id的舊的數(shù)據(jù)，然后寫入到備份block里面。
在compact的過程中，如果發(fā)現(xiàn)整合的數(shù)據(jù)還是大于某個值，怎么辦呢？需要split（分片）。
1.1.3.2 普通數(shù)據(jù)的存儲（CTZ）
Lfs的數(shù)據(jù)采用ctz鏈表的方式逆向管理，這與傳統(tǒng)的文件系統(tǒng)有比較大的差別。具體對比見下圖所示。
傳統(tǒng)的方式添加數(shù)據(jù)，需要建立舊的數(shù)據(jù)到新的數(shù)據(jù)的索引。這樣做有兩個弊端：
（1） 當數(shù)據(jù)特別多的時候，這樣一個個的索引過去查找，比較費時間。
（2） 當使用cow機制的時候，在文件后面每增加一次數(shù)據(jù)，需要把所有的索引都重新建立一個，這樣帶來的性能損耗特別大。
為了解決這兩個問題，lfs采用了下面的管理方式。
（1） 采用逆向的指針，這樣常規(guī)的追加數(shù)據(jù)，不需要額外的開銷來重新建立所有的索引；
（2） 每個偶數(shù)block有多個指針，指向更遠的數(shù)據(jù)，這樣可以在檢索的時候加快速度。
指針的建立采用了CTZ(二進制中最后一個不為0的位，其右邊0的個數(shù))的方式。大概原理就是，block N 如果是一個能被 2^X整除的數(shù)，那么他就存在指向N – 2^X的指針，指針的數(shù)目為ctz(N)+1。
從上表可以看出，block 2多一個指向0的指針，block 4多一個指向0,2的指針。
咱們已經(jīng)知道了實際數(shù)據(jù)（對應file）采用czt list的方式存儲，最新的數(shù)據(jù)block指向次新的數(shù)據(jù)block（這個是為了提高COW的效率）。
一次常規(guī)更新數(shù)據(jù)的過程大概為（實際比這個復雜很多，需要考慮cache、孤兒、crc等問題）：
（1） 往file文件中寫入數(shù)據(jù)；
（2） 申請一個新的block，并且把file文件最后一個block的數(shù)據(jù)復制到新的block，并追加要寫入的數(shù)據(jù)；
（3） 更新新block的czt list（在block的頭部會占用一定的4字節(jié)倍數(shù)的字節(jié)來記錄索引，這個czt list只是用來fseek的加快速度）；
（4） 文件fclose的時候，更新對應的元數(shù)據(jù)信息到父節(jié)點中。
掉電保護的具體場景：
- 步驟（1），（2），（3）完成了，但是（4）沒有完成。因為索引還沒有建立起來，數(shù)據(jù)雖然寫入了，但是沒有人知道，文件系統(tǒng)會丟失最新的數(shù)據(jù)，保留修改之前的數(shù)據(jù)。
-
步驟（4）過程中掉電了。步驟（4）是更新元數(shù)據(jù)，元數(shù)據(jù)采用了主備的方式，并且采取了如下的格式：
正常的提交流程為：
（1）提交tag；
（2）提交data；
（3）提交crc。
當tag和data提交了，但是CRC沒有提交的時候，crc就會校驗失敗，這個時候前面crc校驗通過的部分，就會被relocate到一個新的塊，這樣由于斷電導致的數(shù)據(jù)異常，則回退成功。注意：crc校驗的時機，在提交一個新的commit到對應的元數(shù)據(jù)的時候。
1.2 擦寫均衡
了解擦寫均衡之前，先需要知道littlefs是怎么管理物理block的，怎么才能申請到一個空閑的block。
1.2.1 Block管理
為了節(jié)省內(nèi)容，Littlefs對空閑block的管理采用了滑窗方式，滑窗的大小是可以配置，默認是32bit，對應32個block的使用情況。
當文件系統(tǒng)需要申請一個空閑的block的時候，從lookahead中尋找沒有置位的block，申請成功，則給對應的block位置1。當當前的窗口中的所有block都被占用的時候，就需要滑動窗口了，一次性滑動窗口大小的距離，即默認一次滑動32個block。
當窗口滑動了之后，lookahead中又有了新的空閑的block可以申請。
問題來了，怎么定義一個block是不是空閑的呢？
一片flash的總的block是有限的，假設(shè)其序號從0->N，lookahead對應的block范圍是I->J，Littlefs會通過lfs_fs_traverse遍歷所有使用到的block，如果這個block在I->J之間，則說明block被使用了，否則就是空閑的。
1.2.2 擦寫均衡的實現(xiàn)
通過前面的滑窗機制，可以一定程度上的避免每次操作到的都是同一個片區(qū)的block。但是這還不夠，因為每次啟動的時候，滑窗都是從block0開始滑動的，這個會導致前面的block使用頻率高于后面的block。所以，我們需要找到辦法，讓每次啟動的時候，滑窗的位置都是隨機的，極致的隨機，就是平均了。
為此，littlefs使用了crc作為隨機數(shù)，再通過簡單的運算，得到了滑窗啟動的時候的起始位置。
問題又來了，crc哪兒來的，干什么的？
Crc就是元數(shù)據(jù)提交的終結(jié)符號，用來校驗提交是不是正確的，littlefs借用了crc之間相互異或帶來的不確定性來作為滑窗的啟動地址，一定程度上復用了現(xiàn)有的機制達到了隨機的目的。
1.3 文件讀寫
寫入流程：
讀取流程：
