---
tags: System Software, 作業系統
---
# littlefs
## 儲存裝置
記憶體的類型可以根據儲存能力與供電關係區分為[揮發性記憶體](https://en.wikipedia.org/wiki/Volatile_memory) 以及[非揮發性記憶體](https://en.wikipedia.org/wiki/Non-volatile_memory)。
揮發性記憶體是指當電流中斷後，所儲存的資料便會消失的電腦記憶體，其中常見的有:
* [DRAM](https://en.wikipedia.org/wiki/Dynamic_random-access_memory): 電路結構相對簡單，所以功耗低、價格也較低。缺點就是讀寫速度慢，目前通常應用於主記憶體上
* [SRAM](https://en.wikipedia.org/wiki/Static_random-access_memory): 電路結構相對複雜，所以價格與功耗都較大，目前通常應用於[快取 (Cache)](https://en.wikipedia.org/wiki/Cache_(computing)) 上
而非揮發性記憶體則可以在電流關掉後仍被保存。非揮發性記憶體中，依據記憶體內的資料是否能在使用系統時隨時改寫為標準，可分為兩大類:
* [ROM](https://en.wikipedia.org/wiki/Read-only_memory): 這種記憶體的特性是任何情況下都不會改變，電腦只能讀取儲存在上面的指令(instruction)。這種記憶體多用來儲存特定功能的程式，如特定的 firmware，BIOS。
* 隨著技術的演變也發展出可以抹除資料的 ROM，不過技術不歸類於 ROM，比較嚴謹的分類請參考 wiki 的內容說明
* [Flash memory](https://en.wikipedia.org/wiki/Flash_memory): flash memory 是允許被多次擦(erase)或寫(program)的記憶體。這種技術主要用於一般性資料儲存，允許高效的在電腦與其他數位產品間交換傳輸資料，如記憶卡與隨身碟
## listtlefs 簡介
littlefs 的 [DESIGN.md](https://github.com/littlefs-project/littlefs/blob/master/DESIGN.md) 詳盡的敘述了其設計的理念，十分值得一讀。以下摘錄並翻譯其重點。
### 問題
littlefs 的目標通常是使用在具有大約 32 KiB RAM 和 512 KiB ROM 的 32 位微控制器上。這些硬體通常具有大約 4 MiB 存儲空間的 SPI Nor flash。由於這些設備的儲存空間對於 Linux 和大多數現有的檔案系統來說太小了，因此需要針對此特性重新編寫適合的程式碼。
除了儲存空間的考量，flash 的資料更新策略也影響了其檔案系統的設計。在 flash 中，儲存空間被劃分為許多相同尺寸 block，而每個 block 又被切割成相同大小的 page。資料的寫入是以 page 為單位的，被寫過的 page 不能重新寫入，必須先經過 erase 動作才能再次寫入，然而 erase 操作是以 block 為單位。因此，在 flash 上的檔案系統考量點就與普通的檔案系統有所不同。此外，flash 中每個 block 的抹除次數也是有限的，超過次數的 block 將無法正常地執行讀寫動作。
既然 littefs 主要目標是在記憶體有限的[微控制器(microcontrollers)](https://en.wikipedia.org/wiki/Microcontroller)上，而這些嵌入式設備經常有斷電的問題發生。因此，考量點必須放在如何在妥善使用內存的前提下構建一個能夠抵禦斷電並降低快閃記憶體磨損(flash wear)的檔案系統。檔案系統的設計需要考量：
* 斷電恢復: 在這些系統上，任何時候都可能斷電。如果斷電破壞了任何資料結構，可能導致設備無法恢復。因此檔案系統必須成在能從任何寫操作期間從斷電中恢復。
* 降低 flash 耗損: 由於對 flash 的寫入容易造成耗損，檔案系統重複寫入同一個 block 是應該避免的行為，否則會導致設備過早結束壽命
* 有限的 RAM 與 ROM: 即使不考慮上述的要求，這些系統的記憶體量非常有限仍是顯而易見的問題。許多現有的檔案系統設計可能依賴相對大量的 RAM 來儲存檔案系統的 metadata。對於 ROM 而言，這意味著需要保持我們的設計的簡單並且可以重用重用程式碼。對於 RAM，則必須確保其使用量不會隨著檔案系統大小或檔案數量的變化而對應的增長。
> 延伸閱讀: [SSD for beginners](https://hackmd.io/@RinHizakura/Hy89c4sFF)
### 現有的實作
1. 例如 [FAT](https://en.wikipedia.org/wiki/Design_of_the_FAT_file_system) 和 [ext2](https://en.wikipedia.org/wiki/Ext2) 是 block-based、相對簡單的檔案系統:
* 儲存被以 block 為單位分割，每個檔案都放在 block 的集合中
* 更新檔案就直接對 block 進行改寫即可，也因此這些檔案系統沒有斷電恢復能力
* 因為儲存位置和特定數據的綁定關係降低了檔案系統對 flash 耗損能力的考量
2. 相對複雜的 [logging filesystems](https://en.wikipedia.org/wiki/Log-structured_file_system)，例如 JFFS、YAFFS 和 SPIFFS:
* 不會將存儲位置和數據進行綁定;不嚴謹的說，可以把儲存空間想像成 circular log buffer，對檔案的修改就往 buffer 去 append，而非回到原始檔案的 block 進行重寫，而讀取則需要遍曆整個 log 以重建檔案
* 有些 logging filesystems 可以通過 cache 檔案以降低讀取成本，但是天下沒有白吃的午餐，對 RAM 的使用會因此被相對增加，因此關鍵在兩者的權衡
* 這種設計的主要缺點是性能，因為會需要 garbage collection 來回收過期的資料
* 由於同一檔案的新資料不會直接覆蓋舊資料，搭配 checking region 可以做到斷電恢復
> 更多的考量可以參考:
> * [Log-structured File System](https://zhuanlan.zhihu.com/p/41358013)
> * [log structured file systems](https://medium.com/fcamels-notes/log-structured-file-systems-4520f26fb8e4)
3. [journaling filesystem](https://en.wikipedia.org/wiki/Journaling_file_system) 是基於 blocked-based 與 logging filesystems 的產物，例如 [ext4](https://en.wikipedia.org/wiki/Ext4) 和 [NTFS](https://en.wikipedia.org/wiki/NTFS):
* 相當於是從前面的兩個實作取捨了最佳的部份，其性能可以與 block-based 一樣快 (雖然 journal 的更新也有一些小成本)，並且 journal 更新的 atomical 允許斷電恢復
* journaling filesystem 相對更複雜，因為實際上有兩個檔案系統平行運作，造成程式碼大小成本
* 由於儲存位置和數據之間的密切關係，它們也沒有提供耗損保護
> 關於檔案系統更新的 atomical 之必要性可參考:
> * [Crash Consistency: FSCK and Journaling](https://medium.com/fcamels-notes/crash-consistency-fsck-and-journaling-52e6f6b14836)
>
> 簡而言之，atomic update 提供滿足了斷電恢復的能力(資料不會有毀損的中間狀態)
4. copy-on-write (COW) filesystems:
* 與 block-based 的檔案系統非常相似，但不是直接就地更新 block，而是通過建立並更改，並將對舊 block 的 reference 替換新的塊來完成更新。整個更新會遞迴地向上推直到我們到達檔案系統的根目錄(root)
* COW 檔案系統提供與 block-based 的文件系統非常相似的性能，同時設法實現 atomic update
* 數據與儲存位置可以分離，有可能降低 flash 的耗損
* 但是更新需要無限向上直到到達根目錄，所以更新可能級聯成比原始數據更大的寫入內容
* 這些更新可能導致檔案系統以外的部分更早磨損
> * [Crash Consistency: FSCK and Journaling](https://medium.com/fcamels-notes/crash-consistency-fsck-and-journaling-52e6f6b14836)
### 實作
littlefs 背後的理念是。對於 metadata 的儲存，由兩個小的 block logs 構建而成，這些 log 為檔案系統上任何位置的 metadata 提供 atomic update，並可以被快速的更新。在 file data 的部份則採取 block-based 的 copy-on-write (COW) 機制。
#### Metadata pairs
littlefs 維護兩個 block logs，使得檔案系統可以達到 atomic update 之目的。為什麼是兩個呢？因為 flash 的寫入粒度是有限制的(已經 erase 的 block 一次可以寫入的單位較小，但 erase 則需要一次操作完整的 block)，這意味著為了讓 circular buffer 運作，我們需要不止一個 block。
> [基于Flash的SSD](https://zhuanlan.zhihu.com/p/107797951)
littlefs 為每個 metadata pair 儲存兩個 block address，為了確定哪個 metadata block 是最新的，額外儲存了使用 [Serial number arithmetic](https://en.wikipedia.org/wiki/Serial_number_arithmetic) 比較先後的 revision count。這個 counter 還讓我們大致了解發生了多少次 erase。
metadata 如何被 atomic update 呢？這需要兩部分：redundancy 和 error detection。error detection 可以通過 checksum，littelfs 裡選用的方法是 32 bits [CRC](https://en.wikipedia.org/wiki/Cyclic_redundancy_check)。另一方面，redundancy 需要區分成多個階段：
1. 如果 block 未滿並且新 entry 的大小足以被其容納，我們可以簡單地將其附加到 log 中。因為不會覆蓋原始存在的內容，如果我們在追加期間斷電，仍然保有原始的檔案狀態
```
commit A
.----------------.----------------. .----------------.----------------.
| revision 1 | revision 0 | => | revision 1 | revision 0 |
|----------------|----------------| |----------------|----------------|
| | | | | A | |
| v | | |----------------| |
| | | | checksum | |
| | | |----------------| |
| | | | | | |
| | | | v | |
| | | | | |
| | | | | |
| | | | | |
| | | | | |
'----------------'----------------' '----------------'----------------'
```
* littlefs 不會為每個新的 entry 維護 checksum，雖然許多 log filesystem 都這樣做，但它限制了可以在單個 atomic operation 中更新的內容。littlefs 將多個 entry 分組到一個共享的 checksum，這樣就可以一次更新多個不相關的 metadata(只要它們位於相同的 metadata block)
2. 如果我們 block 已經滿了，而我們需要寫入新的 entry，為此就需要刪除過時的 entry，littlefs 將這種 garbage collection 稱為 compaction:
* littlefs 的回收機制相對簡單。為了避免 RAM 耗損，採用 brute force 的檢查每個 entry 是否存在新的版本。如果該 entry 是最新的，將其加到我們的新 block 中
* 這就是擁有兩個 block 的重要之處，如果發生斷電，我們仍然擁有原始區塊中的所有內容
```
commit B', need to compact
.----------------.----------------. .----------------.----------------.
| revision 1 | revision 0 | => | revision 1 | revision 2 |
|----------------|----------------| |----------------|----------------|
| A | | | A | A' |
|----------------| | |----------------|----------------|
| checksum | | | checksum | B' |
|----------------| | |----------------|----------------|
| B | | | B | checksum |
|----------------| | |----------------|----------------|
| A' | | | A' | | |
|----------------| | |----------------| v |
| checksum | | | checksum | |
|----------------| | |----------------| |
'----------------'----------------' '----------------'----------------'
```
3. 如果 block 已經滿了條目而且找不到任何 garbage 那怎麼辦？littlefs 將原始的 metadata pair 拆為兩個 metadata pair，每個 pair 含一半的 entry，並通過一個 tail pointer 連接，這種操作稱為 split
```
commit C and D, need to split
.----------------.----------------. .----------------.----------------.
| revision 1 | revision 2 | => | revision 3 | revision 2 |
|----------------|----------------| |----------------|----------------|
| A | A' | | A' | A' |
|----------------|----------------| |----------------|----------------|
| checksum | B' | | B' | B' |
|----------------|----------------| |----------------|----------------|
| B | checksum | | tail ---------------------.
|----------------|----------------| |----------------|----------------| |
| A' | | | | checksum | | |
|----------------| v | |----------------| | |
| checksum | | | | | | |
|----------------| | | v | | |
'----------------'----------------' '----------------'----------------' |
.----------------.---------'
v v
.----------------.----------------.
| revision 1 | revision 0 |
|----------------|----------------|
| C | |
|----------------| |
| D | |
|----------------| |
| checksum | |
|----------------| |
| | | |
| v | |
| | |
| | |
'----------------'----------------'
```
在這種小型 log 的機制，還有另一種複雜性。垃圾收集的成本不僅取決於其一次性成本(在 littlefs $O(n^2)$)，還取決於垃圾收集發生的頻率。
如果考慮一個 log 的填滿程度與回收成本的關係，會如下圖所示，可以看到是呈現指數成長的:
:::danger
~~由於筆者小時候沒把數學學好~~，對推導有興趣的人可以自己從原文察看
:::
為了避免這種增長所帶來的問題，littlefs 在 compaction 之前去檢查我們是否符合限制，超過 50% 的時候就會去做 split，這將垃圾收集的開銷限制為運行時成本的 2 倍。但是，以 50% 的容量作 split 意味著在最好的情況下，我們的 metadata pair 只有 1/2 滿。如果考慮有第二個 block，事實上每個 metadata pair 的成本是原始資料大小的 4 倍。想必如果所有的資料都採用這種設計儲存，會讓使用者不大高興，我們需要在儲存大量數據時使用另一個機制來解決這個問題。
### CTZ skip-lists
如前所述，metadata pair 提供了高效的 atomic update，但儲存成本太高了。littlefs 通過 metadata pair 僅用來存 Copy-on-write data structure 之 reference，而後者才保存真正的資料本身來解決此問題。Copy-on-write data structure 是一種底層元素是不可變(immutable)的結構。對數據進行更改需要建立包含原始數據副本的新元素，然後把 reference 替換為對新元素的 reference。通常，COW data structure 的性能取決於替換部分數據後可以重用多少舊元素
首先，讓我們假設將檔案放在一個簡單的 COW linked list 中。寫檔的話就是 append 一個 block 到 linked list 的尾端，根據 COW data structure 的，這意味著我們必須更新最後一個 block 以指向新 block，這需要一個 COW 操作，然後需要更新倒數第二個、倒數第三個，依此類推，直到我們複製出整個檔案。
```
A linked-list
.--------. .--------. .--------. .--------. .--------. .--------.
| data 0 |->| data 1 |->| data 2 |->| data 4 |->| data 5 |->| data 6 |
| | | | | | | | | | | |
| | | | | | | | | | | |
'--------' '--------' '--------' '--------' '--------' '--------'
```
:::info
```
.--------. .--------.
| root | write |new root|
| | ==> | |
| | | |
'--------' '--------'
.-' '-. | '-.
| .-------|------------------' v
v v v .--------.
.--------. .--------. | new B |
| A | | B | | |
| | | | | |
| | | | '--------'
'--------' '--------' .-' |
.-' .-' '-. .------------|------'
| | | | v
v v v v .--------.
.--------. .--------. .--------. | new D |
| C | | D | | E | | |
| | | | | | | |
| | | | | | '--------'
'--------' '--------' '--------'
```
如上圖，當我們做了更新 D 的操作，需要連同更新往上的 B 和 root
:::
為了避免追加 block 的大量複製操作，我們可以改成逆向的 linked list。如此一來，append block 只需要更新新的 block 就好了。當然如果我們是在更新中間的 block，我們仍然需要複製隨後的 block，但由於大多數檔案寫入是線性的，因此檔案系統假設大多數的檔案操作都是這種類型而從中得到優勢。
```
A backwards linked-list
.--------. .--------. .--------. .--------. .--------. .--------.
| data 0 |<-| data 1 |<-| data 2 |<-| data 4 |<-| data 5 |<-| data 6 |
| | | | | | | | | | | |
| | | | | | | | | | | |
'--------' '--------' '--------' '--------' '--------' '--------'
```
既然逆向的 linked list 結構那麼好，一般的 Cow file system 為甚麼不是如此設計呢?顯然逆向的 linked list 有一個相當明顯的問題: 遍歷檔案的成本是 $O(n^2)$，意及讀取一個檔案需要順向結構的 2 倍之時間成本。
因此，littefs 使用的結構實際上是一種特殊的 [Skip list](https://en.wikipedia.org/wiki/Skip_list)，它結合了 count-trailing-zeros (CTZ) 指令的一些特性。總而來說，block N 如果是一個能被 $2^X$ 整除的數，那麼他就存在指向 $N – 2^X$ 的 pointer，而它擁有的 pointer 數量就會是 $ctz(N)+1$，下面以幾個範例驗證。
| N= | 指向 -> | pointer 數量 |
|:---------- |:------------------------- |:------------ |
| 6(0x110) | (6 - 2) | 1 |
| 8(0x1000) | (8 - 2), (8 - 4), (8 - 8) | 3 |
| 12(0x1100) | (12 - 2), (12 - 4) | 2 |
於是，例如從第五個 block 走到第一個 block，需要 5->4->2->1，可以越過 block 3，而如果要走到第 0 個 block 則可以 5->4->0 兩步即可。
如何儲存 CTZ skip list？我們需要一個指向 head block (即最尾端 append 的 block，以上圖 `A backwards linked-list` 為例是 data6) 的指標、skip list 的大小、head block 之 index(以上圖 `A backwards linked-list` 就是 6) 以及指標在該 block 中的 offset。但因為每個大小都會映射到一個唯一的 index + offset。所以實際上只要儲存一個 pointer 以及 skiplist 之大小。
假設檔案大小為 $N$，而每個 block 的大小為 $B$，新增的第 $i$ 個 block 為了形成 linked list 需要犧牲 $ctz(i)+1$ 的空間來存放指標，又每個指標大小是 $w/8$($w$ 為一個 cpu 架構下 word 的 bits 數量)，那麼設 $n$ 是 head block 的 index，我們可以得到以下的式子:
$$
N = \sum_{i=0}^{n}{[B - \frac{w}{8}(ctz(i) + 1)]}
$$
有了 n 之後再結合大小可以推導出 offset，不過這個計算 $n$ 的複雜度不是 O(1)，因此 littlefs 中採取了一些調整。因為筆者的數學確實不是很能理解該內容，對數學推導有興趣者只能自行參考原文了QQ
### The block allocator
現在，我們需要一個 block allocator 來決定下一個要使用哪個 block。一般而言，block 的分配會透過在檔案系統上的 freelist 或 bitmap 等結構記錄。然而考慮斷電恢復的要求，保持這些結構的一致性變得困難，結構的錯誤都可能導致某些 block 遺失等問題。一種謹慎的作法是 brute force traversal，可以遍歷儲存的每個 block 並檢查是否檔案系統的樹上的 block 吻合，但是，這種作法顯然就不太有效率。
littlefs 中的 block allocator 是 bitmap 和 brute force traversal 之間的折衷。相較對整個儲存空間的 bitmap，littlefs 使用一個小的且固定大小的 bitmap，稱為 lookahead buffer 來追蹤部份的 block。在分配期間，先從 lookahead buffer 中取出可用的塊。如果 lookahead buffer 為空，則繼續掃描檔案系統以獲取更多 free block，填充 lookahead buffer。
下面展示在檔案系統上分配 4 個 block，具有 32 bits lookahead buffer 和總共 128 個block 的儲存空間的情況：
```
1. boot... lookahead:
fs blocks: fffff9fffffffffeffffffffffff0000
2. scanning... /* 掃描前 32 個 block 並建立對應的 lookahead buffer */
lookahead: fffff9ff
fs blocks: fffff9fffffffffeffffffffffff0000
3. alloc = 21 /* 通過 lookahead buffer 知道第 21 / 22 個 block 是可以分配的 */
lookahead: fffffdff
fs blocks: fffffdfffffffffeffffffffffff0000
4. alloc = 22 lookahead: ffffffff
fs blocks: fffffffffffffffeffffffffffff0000
5. scanning... /* lookahead buffer 為空，滑動到下 32 個 block */
lookahead: fffffffe
fs blocks: fffffffffffffffeffffffffffff0000
6. alloc = 63 lookahead: ffffffff
fs blocks: ffffffffffffffffffffffffffff0000
7. scanning... lookahead: ffffffff
fs blocks: ffffffffffffffffffffffffffff0000
8. scanning... lookahead: ffffffff
fs blocks: ffffffffffffffffffffffffffff0000
9. scanning... lookahead: ffff0000
fs blocks: ffffffffffffffffffffffffffff0000
10. alloc = 112 lookahead: ffff8000
fs blocks: ffffffffffffffffffffffffffff8000
```
### Wear leveling
block allocator 還存在另一個使命: 降低磨損消耗。如前所述，flash 中每個 block 的抹除次數是有限的，該儲存裝置的性質應該被考慮。littlefs 有兩種防止磨損的方法：
* 檢查 bad block 的存在和恢復
* 均勻分佈 block 的磨損
以恢復而言，block allocator 不能提供太多的幫助。這個考量的實現依賴於檔案系統本身在 bad block 出現時檢測和驅逐(evict)它們的能力。在 littlefs 中，寫入時的 bad block 檢測相當簡單。因為所有寫入都必須是來自 RAM 中的某種數據，在寫入 block 後，我們可以立即讀回 disk 上的數據並驗證它是否與在 RAM 中的副本一致。如果兩者不匹配，則發生了寫入錯誤並且大概率是因為有一個 bad block 的存在。
在 write error 的情況下，一旦檢測到 bad block，因為在 RAM 中有一個該損壞數據的副本，所以我們需要做的就是驅逐 bad block 並分配一個新的，然後重複之前失敗的寫入，直到寫到 good block 為止:
```
1. 原始的檔案系統樹，update C
.----.
|root|
| |
'----'
v--' '----------------------v
.----. .----.
| A | | B |
| | | |
'----' '----'
. . v---' .
. . .----. .
. . | C | .
. . | | .
. . '----' .
. . . . .
.----.----.----.----.----.----.----.----.----.----.
| A |root| | C | B | |
| | | | | | |
'----'----'----'----'----'----'----'----'----'----'
```
```
2. v
.----.
|root|
| |
'----'
v--' '----------------------v
.----. .----.
| A | | B |
| | | |
'----' '----'
. . v---' .
. . .----. .
. . |bad | .
. . |blck| .
. . '----' .
. . . . .
.----.----.----.----.----.----.----.----.----.----.
| A |root| |bad | B | |
| | | |blck| | |
'----'----'----'----'----'----'----'----'----'----'
```
```
3. oh no! bad block! relocate C
.----.
|root|
| |
'----'
v--' '----------------------v
.----. .----.
| A | | B |
| | | |
'----' '----'
. . v---' .
. . .----. .
. . |bad | .
. . |blck| .
. . '----' .
. . . . .
.----.----.----.----.----.----.----.----.----.----.
| A |root| |bad | B |bad | |
| | | |blck| |blck| |
'----'----'----'----'----'----'----'----'----'----'
--------->
```
```
4. successfully relocated C, update B
.----.
|root|
| |
'----'
v--' '----------------------v
.----. .----.
| A | | B |
| | | |
'----' '----'
. . v---' .
. . .----. . .----.
. . |bad | . | C' |
. . |blck| . | |
. . '----' . '----'
. . . . . . .
.----.----.----.----.----.----.----.----.----.----.
| A |root| |bad | B |bad | C' | |
| | | |blck| |blck| | |
'----'----'----'----'----'----'----'----'----'----'
-------------->
```
```
5. oh no! bad block! relocate B
.----.
|root|
| |
'----'
v--' '----------------------v
.----. .----.
| A | |bad |
| | |blck|
'----' '----'
. . v---' .
. . .----. . .----.
. . |bad | . | C' |
. . |blck| . | |
. . '----' . '----'
. . . . . . .
.----.----.----.----.----.----.----.----.----.----.
| A |root| |bad |bad |bad | C' | |
| | | |blck|blck|blck| | |
'----'----'----'----'----'----'----'----'----'----'
```
```
6. oh no! bad block! relocate B
.----.
|root|
| |
'----'
v--' '----------------------v
.----. .----. .----.
| A | |bad | |bad |
| | |blck| |blck|
'----' '----' '----'
. . v---' . . .
. . .----. . .----. .
. . |bad | . | C' | .
. . |blck| . | | .
. . '----' . '----' .
. . . . . . . .
.----.----.----.----.----.----.----.----.----.----.
| A |root| |bad |bad |bad | C' |bad |
| | | |blck|blck|blck| |blck|
'----'----'----'----'----'----'----'----'----'----'
-------------->
```
```
7. successfully relocated B, update root
.----.
|root|
| |
'----'
v--' '----------------------v
.----. .----. .----.
| A | | B' | |bad |
| | | | |blck|
'----' '----' '----'
. . . | . .---' .
. . . '--------------v-------------v
. . . . .----. . .----.
. . . . |bad | . | C' |
. . . . |blck| . | |
. . . . '----' . '----'
. . . . . . . . .
.----.----.----.----.----.----.----.----.----.----.
| A |root| B' | |bad |bad |bad | C' |bad |
| | | | |blck|blck|blck| |blck|
'----'----'----'----'----'----'----'----'----'----'
------------> ------------------
```
```
8. done
.----.
|root|
| |
'----'
v--' '--v
.----. .----.
| A | | B' |
| | | |
'----' '----'
. . . '---------------------------v
. . . . .----.
. . . . | C' |
. . . . | |
. . . . '----'
. . . . . .
.----.----.----.----.----.----.----.----.----.----.
| A |root| B' | |bad |bad |bad | C' |bad |
| | | | |blck|blck|blck| |blck|
'----'----'----'----'----'----'----'----'----'----'
```
如案例中展示的，我們可能會發現新的 block 也是損壞的，但在重複這個循環後我們最終會找到一個可以寫入成功的新 block。如果始終找不到可寫入的 block，這意味著我們儲存裝置中的所有 block 都是損壞的，設備的使用壽命已經到了盡頭。此時， littlefs 將返回 "out of space" 錯誤。
在 read error 的情況下則要複雜的多，因為我們沒有在 RAM 中的數據副本，因此我們需要一種方法來重建原始數據，一種這樣的機制是[糾錯碼 (ECC)](https://en.wikipedia.org/wiki/Error_correction_code)
ECC 是 checksum 概念的擴展。在 checksum （例如 CRC）中可以檢測到數據中是否出現錯誤，而 ECC 則可以檢測並實際糾正一定數量的錯誤。但是，ECC 可以檢測到多少錯誤是有限制的([hamming bound](https://en.wikipedia.org/wiki/Hamming_bound)。隨著錯誤數量接近 hamming bound，即使仍然能夠檢測到錯誤，但無法再修復數據。換句話說，block 已經是不可恢復的。
littlefs 本身不提供 ECC，因為 ECC 的 block nature 和相對佔用較多空間的特點導致其不適用。在沒有 RAM 的情況下糾正錯誤很複雜，並且 ECC 更適合 block device 的結構。事實上，一些 NOR flash 具有用於 ECC 的額外存儲空間，許多 NAND flash 甚至可以在芯片本身上計算 ECC。
在 littlefs 中，ECC 是屬於可選的選項，可以將 ECC 用於 block device 等級以適度延長設備的使用壽命。littlefs 允許 block device 提供額外的主動錯誤檢測，會參照之來進行更激進的錯誤處理。
而對 littefs 來說，主要避免 read error 的方法則是通過主動對存儲中的所有 block 之間平均分配磨損，希望在其餘 block 接近可用壽命前都不會出現有單個 block 出現故障的情形。通常，磨損均衡算法屬於以下兩類之一：
* [動態磨損均衡算法(Dynamic wear leveling)](https://en.wikipedia.org/wiki/Wear_leveling#Dynamic_wear_leveling): 將磨損分佈在 dynamic block 上，原則上僅需考慮未被分配的 block 來實現。
* [靜態磨損均衡算法(Static wear leveling)](https://en.wikipedia.org/wiki/Wear_leveling#Static_wear_leveling): 將磨損分佈在 dynamic 和 static block 上，需要考慮已經包含數據捍未包含數據的 block。
考慮實現的程式碼規模和複雜度，littlefs 採用前者。並且 littlefs 是使用統計式的磨損均衡算法來近似動態磨損均衡算法。簡單來說，littlefs 不會主動跟踪每個 block 實際的磨損次數，而是依靠均勻分佈(uniform distribution)的分配 free block 來近似。磨損的均勻分佈由 block allocator 來實現，它在兩個部分創建均勻分佈。簡單的部分是當設備通電時，在這種情況下，線性並循環(circular)的分配 block。更難的部分是當設備斷電時，不能只是從存儲的開始位置重新啟動 allocator。為了達到均勻分佈的目的，每次掛載檔案系統時，都會將 allocator 在隨機的偏移量位置啟動。只要這個隨機偏移是均勻的，block 的分配模式也就會是均勻分佈的了。
littlefs 使用儲存裝置上的數據來直接驅動我們的隨機數生成器(random number generator)。通過對每個 metadata pair 的 checksum 進行 xor 來實現的(這些計算可以在獲取和掛載檔案系統時一併完成)。注意這個隨機數生成器並不完美("不夠隨機")，它只在檔案系統被修改時返回唯一的隨機數，但這正好滿足我們想要在 allocator 中均衡分配磨損的目的。
總結來說，bad block detection 和 wear leveling 共同提供了一種解決方案以避免檔案系統因磨損而過早結束壽命。littlefs 的 wear leveling 算法提供了一個關鍵特性：可以通過增加存儲大小來延長設備的使用壽命。如果需要更佳的磨損均衡，則進一步可以將 littlefs 與 [Flash translation layer(FTL)](https://en.wikipedia.org/wiki/Flash_memory_controller#Flash_translation_layer_(FTL)_and_mapping) 結合起來。
### Files
在分析了所有 littlefs 結構之後，我們來看看檔案是如何在該檔案系統上被保存的。
一種最標準的儲存方式是: 我們可以為每個檔案提供一個 CTZ-skiplist，並將其儲存在一個 metadata pair 中，後者作為文件的 inode。
```
.--------.
.|metadata|
|| |
|| |
|'--------'
'----|---'
v
.--------. .--------. .--------. .--------.
| data 0 |<-| data 1 |<-| data 2 |<-| data 3 |
| |<-| |--| | | |
| | | | | | | |
'--------' '--------' '--------' '--------'
```
然而，當檔案很小時，這個設計對空間的浪費是很大的。假設現在我們要儲存一個 4 bytes 的檔案，依據前面的敘述，我們將需要 1 個 metadata pair (2 個 blocks)以及一個屬於 skiplist 的 block，假設 block 的大小是一般 NOR flash 常見的 4 KiB，那麼相當於是儲存這個 4 bytes 的檔案需要 3 個 block = 12KiB 空間，這是很不得了的消耗。
為此，我們可以做一些改進。首先，可以將多個檔案存儲在單個 metadata pair 中;其次，對於非常小的文件，我們使用 CTZ skiplist 儲存其實顯得比較多餘。因為 metadata pair 的存儲成本約為 4 倍，因此如果我們的文件小於 block 大小的 1/4，則使用 CTZ skiplist 的作法沒有任何收益。因此在這種情況下，可以將檔案本身直接存儲在我們目錄的 metadata pair 中，稱之為 inline file，這表示之前的 4 bytes 文件現在只在儲存裝置上佔用 16 bytes。
### Directories
有了檔案之後，現在我們需要目錄的概念來存儲之。。littefs 希望嚴格綁定目錄和 metadata pair 的關係，但有一些複雜的問題需要被解決。
就目錄本身而言，每個都是 metadata pair 的 linked list。這讓我們可以在每個目錄中存儲無限數量的檔案。我們可以在 metadata pair 中存儲其他目錄的 pointer，這就形成一個目錄樹。
```
.--------.
.| root |
|| |
|| |
|'--------'
'---|--|-'
.-' '-------------------------.
v v
.--------. .--------. .--------.
.| dir A |------->| dir A | .| dir B |
|| | || | || |
|| | || | || |
|'--------' |'--------' |'--------'
'---|--|-' '----|---' '---|--|-'
.-' '-. | .-' '-.
v v v v v
.--------. .--------. .--------. .--------. .--------.
| file C | | file D | | file E | | file F | | file G |
| | | | | | | | | |
| | | | | | | | | |
'--------' '--------' '--------' '--------' '--------'
```
但是單純的樹狀結構之 traversal 無法透過恆定數量的記憶體來完成，換句話說任何 recursion 方式都是不適合的。由於我們的 block allocator 涉及對整個檔案系統樹進行迭代，且可能在一次分配中多次迭代，因此 traversal 檔案系統的問題需要被解決。
作為解決方案，littlefs 將樹上的每個目錄透過 linked list 串接起來，其稱為 threaded linked-list 。換句話說，每個目錄不僅包含指向其所有子目錄或檔案的 pointer，還包含指向下一個目錄的 pointer。由於我們只使用 threaded linked-list 來檢查檔案是否存在，因此順序實際上並不重要，這個設計也就是合理的。
```
.--------.
.| root |-.
|| | |
.-------|| |-'
| |'--------'
| '---|--|-'
| .-' '-------------------------.
| v v
| .--------. .--------. .--------.
'->| dir A |------->| dir A |------->| dir B |
|| | || | || |
|| | || | || |
|'--------' |'--------' |'--------'
'---|--|-' '----|---' '---|--|-'
.-' '-. | .-' '-.
v v v v v
.--------. .--------. .--------. .--------. .--------.
| file C | | file D | | file E | | file F | | file G |
| | | | | | | | | |
| | | | | | | | | |
'--------' '--------' '--------' '--------' '--------'
```
threaded linked-list 也帶來一些新的挑戰。現在，無論何時我們想要操作目錄樹時，我們發現自己必須更新兩個 pointer 而不是一個。這在 atomic operation 的需求(斷電恢復)上導致一些困難。
為了解決這個問題，我們的 threaded linked-list 有一些調整: 它將不僅包含在我們的檔案系統中找到的 metadata pair，還允許包含由於斷電而沒有 parent 的 metadata pair。這些被稱為 orphaned metadata pairs，這些 orphaned metadata pairs 帶來了斷電恢復操作的可能性。
首先來看加入新目錄的案例:
```
.--------.
.| root |-.
|| | |
.-------|| |-'
| |'--------'
| '---|--|-'
| .-' '-.
| v v
| .--------. .--------.
'->| dir A |->| dir C |
|| | || |
|| | || |
|'--------' |'--------'
'--------' '--------'
allocate dir B
=>
.--------.
.| root |-.
|| | |
.-------|| |-'
| |'--------'
| '---|--|-'
| .-' '-.
| v v
| .--------. .--------.
'->| dir A |--->| dir C |
|| | .->| |
|| | | || |
|'--------' | |'--------'
'--------' | '--------'
|
.--------. |
.| dir B |-'
|| |
|| |
|'--------'
'--------'
insert dir B into threaded linked-list, creating an orphan
=>
.--------.
.| root |-.
|| | |
.-------|| |-'
| |'--------'
| '---|--|-'
| .-' '-------------.
| v v
| .--------. .--------. .--------.
'->| dir A |->| dir B |->| dir C |
|| | || orphan!| || |
|| | || | || |
|'--------' |'--------' |'--------'
'--------' '--------' '--------'
add dir B to parent directory
=>
.--------.
.| root |-.
|| | |
.-------------|| |-'
| |'--------'
| '--|-|-|-'
| .------' | '-------.
| v v v
| .--------. .--------. .--------.
'->| dir A |->| dir B |->| dir C |
|| | || | || |
|| | || | || |
|'--------' |'--------' |'--------'
'--------' '--------' '--------'
```
而移除目錄的案例為:
```
.--------.
.| root |-.
|| | |
.-------------|| |-'
| |'--------'
| '--|-|-|-'
| .------' | '-------.
| v v v
| .--------. .--------. .--------.
'->| dir A |->| dir B |->| dir C |
|| | || | || |
|| | || | || |
|'--------' |'--------' |'--------'
'--------' '--------' '--------'
remove dir B from parent directory, creating an orphan
=>
.--------.
.| root |-.
|| | |
.-------|| |-'
| |'--------'
| '---|--|-'
| .-' '-------------.
| v v
| .--------. .--------. .--------.
'->| dir A |->| dir B |->| dir C |
|| | || orphan!| || |
|| | || | || |
|'--------' |'--------' |'--------'
'--------' '--------' '--------'
remove dir B from threaded linked-list, returning dir B to free blocks
=>
.--------.
.| root |-.
|| | |
.-------|| |-'
| |'--------'
| '---|--|-'
| .-' '-.
| v v
| .--------. .--------.
'->| dir A |->| dir C |
|| | || |
|| | || |
|'--------' |'--------'
'--------' '--------'
```
除了對目錄樹操作之外，當遇到 bad block 的問題時，我們還可以使用 orphan 的概念來替換 metadata pair 中的該 block。如果我們在替換中途斷電，我們最終可能會遇到一種情況：檔案系統仍 reference 即將被移除的 block，而 threaded linked-list 則包含該用來替換的 block(尚未指定其 parent)，我們稱後者的 block 為 half-orphan。
:::danger
這段原文裡的敘述是說
> If we lose power while evicting a metadata block we may end up with a situation where the filesystem references the replacement block while the threaded linked-list still contains the evicted block.
我的理解其直翻的意思是: 檔案系統 reference 用來替換的 block，而 threaded linked-list 仍然包含即將被移除的 block。但這個敘述看起來和圖中的表示不太符合?
:::
```
.--------.
.| root |-.
|| | |
.-------------|| |-'
| |'--------'
| '--|-|-|-'
| .------' | '-------.
| v v v
| .--------. .--------. .--------.
'->| dir A |->| dir B |->| dir C |
|| | || | || |
|| | || | || |
|'--------' |'--------' |'--------'
'--------' '--------' '--------'
try to write to dir B
=>
.--------.
.| root |-.
|| | |
.----------------|| |-'
| |'--------'
| '-|-||-|-'
| .--------' || '-----.
| v |v v
| .--------. .--------. .--------.
'->| dir A |---->| dir B |->| dir C |
|| |-. | | || |
|| | | | | || |
|'--------' | '--------' |'--------'
'--------' | v '--------'
| .--------.
'->| dir B |
| bad |
| block! |
'--------'
oh no! bad block detected, allocate replacement
=>
.--------.
.| root |-.
|| | |
.----------------|| |-'
| |'--------'
| '-|-||-|-'
| .--------' || '-------.
| v |v v
| .--------. .--------. .--------.
'->| dir A |---->| dir B |--->| dir C |
|| |-. | | .->| |
|| | | | | | || |
|'--------' | '--------' | |'--------'
'--------' | v | '--------'
| .--------. |
'->| dir B | |
| bad | |
| block! | |
'--------' |
|
.--------. |
| dir B |--'
| |
| |
'--------'
insert replacement in threaded linked-list, creating a half-orphan
=>
.--------.
.| root |-.
|| | |
.----------------|| |-'
| |'--------'
| '-|-||-|-'
| .--------' || '-------.
| v |v v
| .--------. .--------. .--------.
'->| dir A |---->| dir B |--->| dir C |
|| |-. | | .->| |
|| | | | | | || |
|'--------' | '--------' | |'--------'
'--------' | v | '--------'
| .--------. |
| | dir B | |
| | bad | |
| | block! | |
| '--------' |
| |
| .--------. |
'->| dir B |--'
| half |
| orphan!|
'--------'
fix reference in parent directory
=>
.--------.
.| root |-.
|| | |
.-------------|| |-'
| |'--------'
| '--|-|-|-'
| .------' | '-------.
| v v v
| .--------. .--------. .--------.
'->| dir A |->| dir B |->| dir C |
|| | || | || |
|| | || | || |
|'--------' |'--------' |'--------'
'--------' '--------' '--------'
```
找到 orphan 和 half-orphan 的成本比較高，需要將每個 metadata pair 與每個directory entry 進行比較(複雜度是 $O(n^2)$)。但代價換來的是一個可以適應斷電的檔案系統，且恢復僅需要有限數量的記憶體。不幸中的大幸是，我們只需要在裝置啟動時檢查 orphan(假設供電正常，使否有 atomic operation 並不構成問題)，且 read-only 的 littlefs 可以完全忽略 threaded linked-list (沒有更改目錄結構的問題)。
### The move problem
littlefs 還有最後一個挑戰要克服：如何在兩個目錄之間 atomically 地移動檔案？
在 littlefs 中，至今為止我們還未討論創建跨越多個目錄的檔案移動。檔案系統必須至少經歷兩個不同的狀態才能完成一次移動，而由於檔案移動是檔案系統同步的一種常見形式。作為一個專為斷電而設計的檔案系統，必須要確保讓移動的正確性。
* 我們絕對不能讓斷電導致檔案重複或丟失，只有 threaded linked-list 可以處於被動，因為它不是面向使用者的，可以在內部處理極端情況
* 一些檔案系統會沿目錄樹向上傳遞 COW 操作，直到找到 source 與 destination 間共同的 parent。不幸的是，但這與 threaded linked-list 的設計之交互很差，並帶來了磨損也會一併向上傳遞的問題
* 在舊版本的 littlefs 中，解決方案試圖通過 source 與 destination 之間來回移動、標記和取消標記檔案的移動來解決這個問題，該方法雖然可行但效率不佳，因為查找失敗的移動成本很高，並且需要為每個文件提供唯一 identifier
取而代之的，新版本的 littlefs 運用一種稱為 global state 的機制。
global state 是一小組可以從任何 metadata pair 更新的狀態，透過將 global state 與 metadata pair 結合可以給予更新多個目錄的能力，其為我們提供了一種製作複雜 atomic operation 的手段。
首先，通過將檔案系統中的所有 "delta" xor 在一起，可以構建出實際的 global state。
```
.--------. .--------. .--------. .--------. .--------.
.| |->| gdelta |->| |->| gdelta |->| gdelta |
|| | || 0x23 | || | || 0xff | || 0xce |
|| | || | || | || | || |
|'--------' |'--------' |'--------' |'--------' |'--------'
'--------' '----|---' '--------' '----|---' '----|---'
v v v
0x00 --> xor ------------------> xor ------> xor --> gstate 0x12
```
對於 global state 的更新，我們將已知的 global state 與我們的更改中的任何現有 delta 進行 xor。將此 delta 更新到 metadata pair 的同時也將更新到檔案系統的 global state。
* 0x12 是原本的 global state
* 把 global state 更新到 0xab 且針對原本 delta 為 0xff 的資料 -> $\text{0x12} \oplus \text{0xab} \oplus \text{0x12} = \text{0x46}$
```
.--------. .--------. .--------. .--------. .--------.
.| |->| gdelta |->| |->| gdelta |->| gdelta |
|| | || 0x23 | || | || 0xff | || 0xce |
|| | || | || | || | || |
|'--------' |'--------' |'--------' |'--------' |'--------'
'--------' '----|---' '--------' '--|---|-' '----|---'
v v | v
0x00 --> xor ----------------> xor -|------> xor --> gstate = 0x12
| |
| |
change gstate to 0xab --> xor <------------|--------------------------'
=> | v
'------------> xor
|
v
.--------. .--------. .--------. .--------. .--------.
.| |->| gdelta |->| |->| gdelta |->| gdelta |
|| | || 0x23 | || | || 0x46 | || 0xce |
|| | || | || | || | || |
|'--------' |'--------' |'--------' |'--------' |'--------'
'--------' '----|---' '--------' '----|---' '----|---'
v v v
0x00 --> xor ------------------> xor ------> xor --> gstate = 0xab
```
為了提高更新效率，我們總是在 RAM 中保留一份 global state 的副本，因此只需要在在檔案系統掛載時首次遍歷我們的 metadata pair 並構建之即可。
global state 帶來的開銷非常昂貴。我們在 RAM 中保留一個副本，並在需要在無限數量的 metadata pair 中保留一個 delta。但是，global state 的確也為 atomically 的檔案移動效率帶來了價值。
現在我們可以解決檔案移動的問題了。我們可以在建立新檔案時 atomically 的建立描述移動的 global state，並且在刪除舊檔案時 atomically 的清除這個移動狀態。
```
.--------. gstate = no move
.| root |-.
|| | |
.-------------|| |-'
| |'--------'
| '--|-|-|-'
| .------' | '-------.
| v v v
| .--------. .--------. .--------.
'->| dir A |->| dir B |->| dir C |
|| | || | || |
|| | || | || |
|'--------' |'--------' |'--------'
'----|---' '--------' '--------'
v
.--------.
| file D |
| |
| |
'--------'
begin move, add reference in dir C, change gstate to have move
=>
.--------. gstate = moving file D in dir A (m1)
.| root |-.
|| | |
.-------------|| |-'
| |'--------'
| '--|-|-|-'
| .------' | '-------.
| v v v
| .--------. .--------. .--------.
'->| dir A |->| dir B |->| dir C |
|| | || | || gdelta |
|| | || | || =m1 |
|'--------' |'--------' |'--------'
'----|---' '--------' '----|---'
| .----------------'
v v
.--------.
| file D |
| |
| |
'--------'
complete move, remove reference in dir A, change gstate to no move
=>
.--------. gstate = no move (m1^~m1)
.| root |-.
|| | |
.-------------|| |-'
| |'--------'
| '--|-|-|-'
| .------' | '-------.
| v v v
| .--------. .--------. .--------.
'->| dir A |->| dir B |->| dir C |
|| gdelta | || | || gdelta |
|| =~m1 | || | || =m1 |
|'--------' |'--------' |'--------'
'--------' '--------' '----|---'
v
.--------.
| file D |
| |
| |
'--------'
```
如果在檔案移動期間發生斷電，並且檔案重複存在在 source 和 destination 中，我們可以使用 global state 中的信息來進行恢復。
```
.--------. gstate = moving file D in dir A (m1)
.| root |-. ^
|| |------------> xor
.---------------|| |-' ^
| |'--------' |
| '--|-|-|-' |
| .--------' | '---------. |
| | | | |
| | .----------> xor --------> xor
| v | v ^ v ^
| .--------. | .--------. | .--------. |
'->| dir A |-|->| dir B |-|->| dir C | |
|| |-' || |-' || gdelta |-'
|| | || | || =m1 |
|'--------' |'--------' |'--------'
'----|---' '--------' '----|---'
| .---------------------'
v v
.--------.
| file D |
| |
| |
'--------'
```
移動目錄也是相同道理。且因為如前所述 threaded linked-list 的目錄順序並不重要，因此其保持不變仍可以正常工作，
```
.--------. gstate = no move (m1^~m1)
.| root |-.
|| | |
.-------------|| |-'
| |'--------'
| '--|-|-|-'
| .------' | '-------.
| v v v
| .--------. .--------. .--------.
'->| dir A |->| dir B |->| dir C |
|| gdelta | || | || gdelta |
|| =~m1 | || | || =m1 |
|'--------' |'--------' |'--------'
'--------' '--------' '----|---'
v
.--------.
| file D |
| |
| |
'--------'
begin move, add reference in dir C, change gstate to have move
=>
.--------. gstate = moving dir B in root (m1^~m1^m2)
.| root |-.
|| | |
.--------------|| |-'
| |'--------'
| '--|-|-|-'
| .-------' | '----------.
| v | v
| .--------. | .--------.
'->| dir A |-. | .->| dir C |
|| gdelta | | | | || gdelta |
|| =~m1 | | | | || =m1^m2 |
|'--------' | | | |'--------'
'--------' | | | '---|--|-'
| | .-------' |
| v v | v
| .--------. | .--------.
'->| dir B |-' | file D |
|| | | |
|| | | |
|'--------' '--------'
'--------'
complete move, remove reference in root, change gstate to no move
=>
.--------. gstate = no move (m1^~m1^m2^~m2)
.| root |-.
|| gdelta | |
.-----------|| =~m2 |-'
| |'--------'
| '---|--|-'
| .-----' '-----.
| v v
| .--------. .--------.
'->| dir A |-. .->| dir C |
|| gdelta | | | || gdelta |
|| =~m1 | | '-|| =m1^m2 |-------.
|'--------' | |'--------' |
'--------' | '---|--|-' |
| .-' '-. |
| v v |
| .--------. .--------. |
'->| dir B |--| file D |-'
|| | | |
|| | | |
|'--------' '--------'
'--------'
```
## libfuse
* [littlefs-fuse](https://github.com/littlefs-project/littlefs-fuse)
* 一個掛載在 userspace 的小型檔案系統範例: [chisai-fs](https://github.com/RinHizakura/chisai-fs)
## Ref
> * [LittleFs文件系统](https://www.jianshu.com/p/e229247c4f6b)
> * [成大資工 wiki-Flash](http://wiki.csie.ncku.edu.tw/embedded/Flash)
Sign in with Wallet
Connect another wallet