0 簡介
LittleFs設計之初的重點特性是：
（1）低資源消耗铅辞；
（2）掉電保護厌漂；
（3）擦寫均衡，
本章節(jié)重點討論第（2）和（3）這兩個特性斟珊，第（1）個特性則貫穿在整個設計過程中苇倡。后文把LittleFs簡稱為lfs。
1 具體功能介紹
1.1 掉電保護
最經典的掉電保護方法有兩種囤踩，一種是使用日志旨椒，一種是通過COW方式。lfs結合了兩種方法堵漱，并優(yōu)化了兩種方案的缺點综慎，提供了一套掉電保護策略。
1.1.1 日志方式
具體步驟為：
（1） 寫入數(shù)據(jù)之前勤庐，先在日志區(qū)存儲開始標志示惊，記錄要寫入的數(shù)據(jù)位置和大小愉镰；
（2） 待寫入的數(shù)據(jù)寫入日志區(qū)米罚；
（3） 待寫入的數(shù)據(jù)寫入數(shù)據(jù)區(qū)；
（4） 寫入完成之后岛杀，在日志區(qū)記錄結束標志。
模擬掉電場景：
（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結合了日志方式和COW機制兩種方式進行掉電保護橄霉，并且優(yōu)化了兩種方案窃爷。
前面談過文件系統(tǒng)三要素，超級塊酪劫，inode吞鸭，以及數(shù)據(jù)。對應lfs來說覆糟，他把超級塊以及inode通過日志的方式存儲刻剥，兩種采用統(tǒng)一的存儲結構，后文稱兩者為元數(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的指針蜒车。
咱們已經知道了實際數(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é)省內容，Littlefs對空閑block的管理采用了滑窗方式松邪，滑窗的大小是可以配置坞琴，默認是32bit，對應32個block的使用情況逗抑。
當文件系統(tǒng)需要申請一個空閑的block的時候剧辐，從lookahead中尋找沒有置位的block，申請成功邮府，則給對應的block位置1荧关。當當前的窗口中的所有block都被占用的時候，就需要滑動窗口了褂傀，一次性滑動窗口大小的距離忍啤，即默認一次滑動32個block。
當窗口滑動了之后仙辟，lookahead中又有了新的空閑的block可以申請同波。
問題來了鳄梅，怎么定義一個block是不是空閑的呢？
一片flash的總的block是有限的未檩，假設其序號從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ù)提交的終結符號，用來校驗提交是不是正確的可都，littlefs借用了crc之間相互異或帶來的不確定性來作為滑窗的啟動地址缓待，一定程度上復用了現(xiàn)有的機制達到了隨機的目的。
1.3 文件讀寫
寫入流程：
讀取流程：
