
??想了解更多關于開源的內容,請訪問:??
??51CTO 開源基礎軟件社區??
??https://ost.51cto.com??
前言
littlefs是一個小型的文件系統,其特點有:
(1)具有磨損均衡功能。
(2)具有掉電保護能力。
(3)適用于ROM和RAM有限的場景。
本系列文章將對littlefs的原理進行分析。作為系列的第一篇,首先對littlefs整體的存儲結構進行介紹,在后面的文章中,再對具體的目錄、文件操作等進行分析。
1、總覽
![#littlefs原理分析#[一]存儲結構-開源基礎軟件社區 #littlefs原理分析#[一]存儲結構-開源基礎軟件社區](https://dl-harmonyos.51cto.com/images/202210/69ebf180807dcccf79446356c680e088e53afb.png?x-oss-process=image/resize,w_691,h_341)
littlefs的存儲結構大體上如上圖所示。其中超級塊是littlefs存儲目錄和文件的起點,根目錄緊隨其后。littlefs中的目錄均可以指向其他的目錄,構成樹狀結構。在目錄中可以包含多個文件,上圖中右邊的目錄中即包含了一個inline文件和一個outline文件。
2、元數據對
在對littlefs的存儲結構進行具體介紹之前,先對littlefs中一個核心的數據結構,即元數據,進行介紹。littlefs中使用元數據對存儲目錄信息、超級塊信息、文件信息、inline文件的數據等內容,是其設計的核心數據結構。
元數據對的存儲結構如下圖:
![#littlefs原理分析#[一]存儲結構-開源基礎軟件社區 #littlefs原理分析#[一]存儲結構-開源基礎軟件社區](https://dl-harmonyos.51cto.com/images/202210/51c97bb5696305e6514092df17ebc5d6d36e89.png?x-oss-process=image/resize,w_227,h_125)
以下為具體說明:
- 一個元數據對與物理上的兩個塊相對應,且均記錄了一個revision count。revision count較大的塊存儲的為較新的內容,每當更新其中的數據時,revision count就會加1。使用兩個塊的好處是,當一個塊放不下更新的內容時,可以將數據壓縮并轉存到另一個塊上(如進行compact操作),避免直接破壞原有的數據。
- 每個超級塊、目錄均有其對應的一個或多個元數據對,其中記錄了超級塊或目錄相關的信息。如目錄對應的元數據對中可能存儲該目錄下的文件信息等。
- 元數據對以tag為單元進行信息的存儲,以commit的方式進行信息的更新,這里是借鑒了logging文件系統的做法。如創建一個目錄,就會在對應的元數據對中進行一次commit,記錄CREATE、DIR、DIRSTRUCT等tag,最后計算CRC。
- 元數據對每次進行commit時會計算CRC,以實現數據的校驗等功能。
(1)tag
如上文所述,tag是元數據中存儲信息的單元,其結構如下:
[---- 32 ----]
[1|-- 11 --|-- 10 --|-- 10 --]
^. ^ . ^ ^- length
|. | . '------------ id
|. '-----.------------------ type (type3)
'.-----------.------------------ valid bit
[-3-|-- 8 --]
^ ^- chunk
'------- type (type1)
其中包含了tag的有效位、類型、id、長度等信息。對于不同類型的tag,其儲存的內容也不同。通常在tag后會緊跟其相應數據的內容,如CTZSTRUCT類型的tag后的data中存儲了文件大小和文件跳表頭所在的塊號:
tag data
[-- 32 --][-- 32 --|-- 32 --]
[1|- 11 -| 10 | 10 ][-- 32 --|-- 32 --]
^ ^ ^ ^ ^ ^- file size
| | | | '-------------------- file head
| | | '- size (8)
| | '------ id
| '------------ type (0x202)
'----------------- valid bit
3、超級塊
超級塊是littlefs存儲目錄和文件的起點,其元數據對所在的塊號起始為0,1。
超級塊以單個或多個元數據對的方式進行存儲,下圖為單個元數據對存儲超級塊的具體情形:
![#littlefs原理分析#[一]存儲結構-開源基礎軟件社區 #littlefs原理分析#[一]存儲結構-開源基礎軟件社區](https://dl-harmonyos.51cto.com/images/202210/e9052d75999142f191010753d02895aeee88d2.png?x-oss-process=image/resize,w_381,h_209)
其中包含了LFS_TYPE_CREATE類型、LFS_TYPE_SUPERBLOCK類型等的tag。其中超級塊的具體數據信息存儲于LFS_TYPE_INLINESTRUCT類型的tag中。
相關數據結構如下:
typedef struct lfs_superblock {
uint32_t version; // littlefs版本
lfs_size_t block_size; // 一個塊的大小
lfs_size_t block_count; // 文件系統中塊的總數
lfs_size_t name_max; // 文件名字節數的最大值
lfs_size_t file_max; // 文件大小字節數的最大值
lfs_size_t attr_max; // 文件屬性字節數的最大值
} lfs_superblock_t;
4、目錄
目錄的存儲結構如上文總覽中所示,以單個或多個元數據對的方式進行存儲。以根目錄為起點,通過末尾對其他元數據對的塊指針,可以構成一個樹形結構。
單個目錄的元數據對具體存儲如下圖:
![#littlefs原理分析#[一]存儲結構-開源基礎軟件社區 #littlefs原理分析#[一]存儲結構-開源基礎軟件社區](https://dl-harmonyos.51cto.com/images/202210/b4e64983499afb0559d75662117ce62b015f43.png?x-oss-process=image/resize,w_809,h_271)
上圖中,中間的目錄使用了兩個元數據對進行存儲。第一個元數據對中SOFTTAIL類型的tag中存儲了指向父目錄中末尾目錄的塊指針(即在父目錄中最后創建的子目錄,當父目錄中還沒有創建子目錄時,該塊指針為空)。第二個元數據對中存儲了創建的子目錄的信息(包括CREATE、DIR、DIRSTRUCT等類型的tag),并指向了子目錄。
注:上述目錄與其父目錄、子目錄之間的鏈接方式只是可能的一種情況。隨著目錄的創建、刪除、移動等操作,具體的鏈接方式會發生變化,具體見后面的文章。
其中相關tag的表示如下:
- HARDTAIL:表示同一目錄的下一個元數據對的塊指針。
- SOFTTAIL:表示不同目錄的下一個元數據對的塊指針。
- 目錄創建信息相關:在父目錄中會記錄CREATE、DIR、DIRSTRUCT、SOFTTAIL等類型的tag。
- DIR:存儲目錄名和id。
- DIRSTRUCT:存儲創建的子目錄的元數據對的塊指針。
- SOFTTAIL:記錄了創建的子目錄的元數據對的塊指針。
(1)相關數據結構
目錄信息在內存中的表示如下:
typedef struct lfs_mdir {
lfs_block_t pair[2]; // 元數據對塊指針
uint32_t rev; // revision count
// 當前在元數據塊中的偏移
// 用于commit和fetch相關函數
// 作為起始偏移傳入,結束時保存了寫入后的偏移
lfs_off_t off;
// entry tag,用于記錄當前的ptag
// ptag用于commit過程中計算異或tag、計算CRC等,見commit機制和tag的遍歷
// 當fetch時,fetch到一個commit時,會將計算的ptag存入etag
// 當進行commit時,ptag就可以初始化為etag
uint32_t etag;
uint16_t count; // 目錄中屬性數量(文件、子目錄數)
// 表示下一個commit是否寫入完成
// 用于commit和fetch相關函數,見commit機制和tag的遍歷
// 當fetch時,fetch到末尾還未匹配,會把erased置為true
// 在commit函數中,只有erased為true才進行commit
bool erased;
bool split; // 表示當前目錄塊后面是否還有塊,為false時表示末尾
// 表示當前目錄塊中最后一個TAIL
// 既可能是HARDTAIL,也可能是SOFTTAIL
// 與fetch機制、目錄的遍歷等有關
lfs_block_t tail[2];
// 注:off、etag、erased、tail與commit機制、tag的遍歷等有關,見后面的文章
} lfs_mdir_t;
另外,littlefs中,內存中打開的目錄使用lfs_dir_t類型的數據結構進行記錄。見littlefs中mlist的介紹。
5、文件
文件的tag存儲于其父目錄的元數據對中。文件又分為inline文件和outline文件。當文件剛創建時,默認為inline文件。當文件大小超過1/8 block_size、或超過文件cache大小時,會重新分配為outline文件。
(1)inline文件
![#littlefs原理分析#[一]存儲結構-開源基礎軟件社區 #littlefs原理分析#[一]存儲結構-開源基礎軟件社區](https://dl-harmonyos.51cto.com/images/202210/11e333d8461c9a5530e699af57afff10b57f4c.png?x-oss-process=image/resize,w_171,h_180)
具體tag存儲信息如下:
- REG:存儲文件名和id
- INLINESTRUCT:存儲inline文件的數據
(2)outline文件
![#littlefs原理分析#[一]存儲結構-開源基礎軟件社區 #littlefs原理分析#[一]存儲結構-開源基礎軟件社區](https://dl-harmonyos.51cto.com/images/202210/67ac44d83d15a18b37d0158689e452b5102efd.png?x-oss-process=image/resize,w_751,h_340)
如上圖,littlefs中outline文件的數據是用跳表存儲的。其中CTZSTRUCT類型的tag中存儲了文件大小和跳表頭指針信息,跳表頭指針指向了文件末尾的塊。跳表中每個塊對其他塊的指針儲存在該塊的塊頭處。
跳表中塊指針按固定規律分布:對block
,如果
可以被
整除,那么該block就含有一個指向block
的塊指針。以block 4為例:
- 4可以被
整除,則block 4含有
即block 3的塊指針。 - 4可以被
整除,則block 4含有
即block 2的塊指針。 - 4可以被
整除,則block 4含有
即block 0的塊指針。
由此規律,又因為塊的大小是固定的,那么只要知道文件的偏移位置,就可以獲取該偏移位置所在block在跳表中的序號、該塊上有幾個塊指針等信息:
- 獲取跳表中塊序號:根據文件偏移和塊大小計算,相關函數為lfs_ctz_index。
- 獲取塊頭部塊指針數量:用ctz指令,ctz(塊序號)。
(3)相關數據結構
文件在內存中表示如下:
typedef struct lfs_file {
// 以下4個成員與mlist相關,見后文mlist的介紹
struct lfs_file *next;
uint16_t id;
uint8_t type;
lfs_mdir_t m;
struct lfs_ctz {
lfs_block_t head; // 跳表頭指針,inline文件時為LFS_BLOCK_INLINE
lfs_size_t size; // 文件大小,inline和outline文件均用此記錄
} ctz;
uint32_t flags; // INLINE、OUTLINE、DIRTY、WRITING等標志
lfs_off_t pos; // 文件當前的偏移字節數
lfs_block_t block; // 文件當前的block
lfs_off_t off; // 文件在當前block的偏移
lfs_cache_t cache; // 文件緩存,用于讀寫等操作
const struct lfs_file_config *cfg; // 文件的其他配置信息
} lfs_file_t;
6、文件和目錄在內存中的表示(mlist)
littlefs中,mlist用于記錄打開的文件和目錄,存在于內存中。
mlist主要用于遍歷打開的文件和目錄。
(1)相關數據結構
mlist
typedef struct lfs {
...
struct lfs_mlist {
struct lfs_mlist *next; // 下一個鏈表中的節點
uint16_t id; // 文件或目錄在其父目錄中的id
uint8_t type; // 類型,表明是文件還是目錄
lfs_mdir_t m; // 父目錄元數據對信息
} *mlist;
...
} lfs_t;
打開的文件
typedef struct lfs_file {
struct lfs_file *next; // 下一個鏈表中的節點
uint16_t id; // 文件在父目錄中的id
uint8_t type; // 類型,文件類型應為LFS_REG_TYPE
lfs_mdir_t m; // 父目錄元數據對信息
// 以下成員見上文中存儲結構
...
} lfs_file_t;
打開的目錄
typedef struct lfs_dir {
struct lfs_dir *next; // 下一個鏈表中的節點
uint16_t id; // 目錄在父目錄中的id
uint8_t type; // 類型,目錄應為LFS_DIR_TYPE
lfs_mdir_t m; // 父目錄元數據對信息
lfs_off_t pos; // 當前目錄或文件在父目錄中的位置,.和..分別為0和1
lfs_block_t head[2]; // 第一個元數據對所在塊號
} lfs_dir_t;
(2)記錄打開的文件和目錄
由前面的數據結構,littlefs中mlist是一個單鏈表,其中記錄了打開的文件和目錄。 mlist既可以插入lfs_file_t,也可以插入lfs_dir_t,lfs_mlist、lfs_file_t和lfs_dir_t的前幾個成員的結構體是相同的。
在打開文件過程中
打開文件時,相應lfs_file_t類型的文件數據加入到mlist:
lfs_file_open(lfs_t *lfs, lfs_file_t *file, const char *path, int flags)
|-> lfs_file_rawopen(lfs_t *lfs, lfs_file_t *file,
| const char *path, int flags)
|-> lfs_file_rawopencfg(lfs_t *lfs, lfs_file_t *file,
| const char *path, int flags,
| const struct lfs_file_config *cfg)
|-> ...
|
| // 將file加入到mlist
|-> lfs_mlist_append(lfs, (struct lfs_mlist *)file);
|
|-> ...
在關閉文件過程中
關閉文件時,mlist會刪除對應的文件:
lfs_file_close(lfs_t *lfs, lfs_file_t *file)
|-> lfs_file_rawclose(lfs_t *lfs, lfs_file_t *file)
|-> lfs_mlist_remove(lfs, (struct lfs_mlist*)file);
|
|-> ...
在打開目錄過程中
打開命令時,相應lfs_dir_t類型的目錄數據加入到mlist:
lfs_dir_open(lfs_t *lfs, lfs_dir_t *dir, const char *path)
|-> lfs_dir_rawopen(lfs_t *lfs, lfs_dir_t *dir, const char *path)
|-> ...
|
|-> lfs_mlist_append(lfs, (struct lfs_mlist *)dir);
在關閉目錄過程中
關閉目錄時,mlist中會刪除對應的目錄:
lfs_dir_close(lfs_t *lfs, lfs_dir_t *dir)
|-> lfs_dir_rawclose(lfs_t *lfs, lfs_dir_t *dir)
|-> lfs_mlist_remove(lfs, (struct lfs_mlist *)dir);
總結
本文介紹了littlefs的整體結構,包括超級塊、文件、目錄等在磁盤上的存儲,以及文件、目錄打開后在內存中的表示,希望能讓讀者對littlefs有一個大概的印象。后續的文章會繼續分析littlefs原理。
??想了解更多關于開源的內容,請訪問:??
??51CTO 開源基礎軟件社區??
??https://ost.51cto.com??。