??想了解更多關(guān)于開源的內(nèi)容，請?jiān)L問：??

??51CTO 開源基礎(chǔ)軟件社區(qū)??

??https://ost.51cto.com??

前言

littlefs是一個(gè)小型的文件系統(tǒng)，其特點(diǎn)有：

（1）具有磨損均衡功能。

（2）具有掉電保護(hù)能力。

（3）適用于ROM和RAM有限的場景。

本系列文章將對littlefs的原理進(jìn)行分析。作為系列的第一篇，首先對littlefs整體的存儲(chǔ)結(jié)構(gòu)進(jìn)行介紹，在后面的文章中，再對具體的目錄、文件操作等進(jìn)行分析。

1、總覽

littlefs的存儲(chǔ)結(jié)構(gòu)大體上如上圖所示。其中超級塊是littlefs存儲(chǔ)目錄和文件的起點(diǎn)，根目錄緊隨其后。littlefs中的目錄均可以指向其他的目錄，構(gòu)成樹狀結(jié)構(gòu)。在目錄中可以包含多個(gè)文件，上圖中右邊的目錄中即包含了一個(gè)inline文件和一個(gè)outline文件。

2、元數(shù)據(jù)對

在對littlefs的存儲(chǔ)結(jié)構(gòu)進(jìn)行具體介紹之前，先對littlefs中一個(gè)核心的數(shù)據(jù)結(jié)構(gòu)，即元數(shù)據(jù)，進(jìn)行介紹。littlefs中使用元數(shù)據(jù)對存儲(chǔ)目錄信息、超級塊信息、文件信息、inline文件的數(shù)據(jù)等內(nèi)容，是其設(shè)計(jì)的核心數(shù)據(jù)結(jié)構(gòu)。

元數(shù)據(jù)對的存儲(chǔ)結(jié)構(gòu)如下圖：

以下為具體說明：

• 一個(gè)元數(shù)據(jù)對與物理上的兩個(gè)塊相對應(yīng)，且均記錄了一個(gè)revision count。revision count較大的塊存儲(chǔ)的為較新的內(nèi)容，每當(dāng)更新其中的數(shù)據(jù)時(shí)，revision count就會(huì)加1。使用兩個(gè)塊的好處是，當(dāng)一個(gè)塊放不下更新的內(nèi)容時(shí)，可以將數(shù)據(jù)壓縮并轉(zhuǎn)存到另一個(gè)塊上（如進(jìn)行compact操作），避免直接破壞原有的數(shù)據(jù)。
• 每個(gè)超級塊、目錄均有其對應(yīng)的一個(gè)或多個(gè)元數(shù)據(jù)對，其中記錄了超級塊或目錄相關(guān)的信息。如目錄對應(yīng)的元數(shù)據(jù)對中可能存儲(chǔ)該目錄下的文件信息等。
• 元數(shù)據(jù)對以tag為單元進(jìn)行信息的存儲(chǔ)，以commit的方式進(jìn)行信息的更新，這里是借鑒了logging文件系統(tǒng)的做法。如創(chuàng)建一個(gè)目錄，就會(huì)在對應(yīng)的元數(shù)據(jù)對中進(jìn)行一次commit，記錄CREATE、DIR、DIRSTRUCT等tag，最后計(jì)算CRC。
• 元數(shù)據(jù)對每次進(jìn)行commit時(shí)會(huì)計(jì)算CRC，以實(shí)現(xiàn)數(shù)據(jù)的校驗(yàn)等功能。

（1）tag

如上文所述，tag是元數(shù)據(jù)中存儲(chǔ)信息的單元，其結(jié)構(gòu)如下：

[----            32             ----]
[1|--  11   --|--  10  --|--  10  --]
 ^.     ^     .     ^          ^- length
 |.     |     .     '------------ id
 |.     '-----.------------------ type (type3)
 '.-----------.------------------ valid bit
  [-3-|-- 8 --]
    ^     ^- chunk
    '------- type (type1)

其中包含了tag的有效位、類型、id、長度等信息。對于不同類型的tag，其儲(chǔ)存的內(nèi)容也不同。通常在tag后會(huì)緊跟其相應(yīng)數(shù)據(jù)的內(nèi)容，如CTZSTRUCT類型的tag后的data中存儲(chǔ)了文件大小和文件跳表頭所在的塊號：

tag                          data
[--      32      --][--      32      --|--      32      --]
[1|- 11 -| 10 | 10 ][--      32      --|--      32      --]
 ^    ^     ^    ^            ^                  ^- file size
 |    |     |    |            '-------------------- file head
 |    |     |    '- size (8)
 |    |     '------ id
 |    '------------ type (0x202)
 '----------------- valid bit

3、超級塊

超級塊是littlefs存儲(chǔ)目錄和文件的起點(diǎn)，其元數(shù)據(jù)對所在的塊號起始為0，1。
超級塊以單個(gè)或多個(gè)元數(shù)據(jù)對的方式進(jìn)行存儲(chǔ)，下圖為單個(gè)元數(shù)據(jù)對存儲(chǔ)超級塊的具體情形：

其中包含了LFS_TYPE_CREATE類型、LFS_TYPE_SUPERBLOCK類型等的tag。其中超級塊的具體數(shù)據(jù)信息存儲(chǔ)于LFS_TYPE_INLINESTRUCT類型的tag中。

相關(guān)數(shù)據(jù)結(jié)構(gòu)如下：

typedef struct lfs_superblock {
    uint32_t version;           // littlefs版本
    lfs_size_t block_size;      // 一個(gè)塊的大小
    lfs_size_t block_count;     // 文件系統(tǒng)中塊的總數(shù)
    lfs_size_t name_max;        // 文件名字節(jié)數(shù)的最大值
    lfs_size_t file_max;        // 文件大小字節(jié)數(shù)的最大值
    lfs_size_t attr_max;        // 文件屬性字節(jié)數(shù)的最大值
} lfs_superblock_t;

4、目錄

目錄的存儲(chǔ)結(jié)構(gòu)如上文總覽中所示，以單個(gè)或多個(gè)元數(shù)據(jù)對的方式進(jìn)行存儲(chǔ)。以根目錄為起點(diǎn)，通過末尾對其他元數(shù)據(jù)對的塊指針，可以構(gòu)成一個(gè)樹形結(jié)構(gòu)。

單個(gè)目錄的元數(shù)據(jù)對具體存儲(chǔ)如下圖：

上圖中，中間的目錄使用了兩個(gè)元數(shù)據(jù)對進(jìn)行存儲(chǔ)。第一個(gè)元數(shù)據(jù)對中SOFTTAIL類型的tag中存儲(chǔ)了指向父目錄中末尾目錄的塊指針（即在父目錄中最后創(chuàng)建的子目錄，當(dāng)父目錄中還沒有創(chuàng)建子目錄時(shí)，該塊指針為空）。第二個(gè)元數(shù)據(jù)對中存儲(chǔ)了創(chuàng)建的子目錄的信息（包括CREATE、DIR、DIRSTRUCT等類型的tag），并指向了子目錄。

注：上述目錄與其父目錄、子目錄之間的鏈接方式只是可能的一種情況。隨著目錄的創(chuàng)建、刪除、移動(dòng)等操作，具體的鏈接方式會(huì)發(fā)生變化，具體見后面的文章。

其中相關(guān)tag的表示如下：

• 元數(shù)據(jù)對的塊指針相關(guān)：

• HARDTAIL：表示同一目錄的下一個(gè)元數(shù)據(jù)對的塊指針。
• SOFTTAIL：表示不同目錄的下一個(gè)元數(shù)據(jù)對的塊指針。

• 目錄創(chuàng)建信息相關(guān)：在父目錄中會(huì)記錄CREATE、DIR、DIRSTRUCT、SOFTTAIL等類型的tag。

• DIR：存儲(chǔ)目錄名和id。
• DIRSTRUCT：存儲(chǔ)創(chuàng)建的子目錄的元數(shù)據(jù)對的塊指針。
• SOFTTAIL：記錄了創(chuàng)建的子目錄的元數(shù)據(jù)對的塊指針。

（1）相關(guān)數(shù)據(jù)結(jié)構(gòu)

目錄信息在內(nèi)存中的表示如下：

typedef struct lfs_mdir {
    lfs_block_t pair[2];    // 元數(shù)據(jù)對塊指針
    uint32_t rev;           // revision count

    // 當(dāng)前在元數(shù)據(jù)塊中的偏移
    // 用于commit和fetch相關(guān)函數(shù)
    // 作為起始偏移傳入，結(jié)束時(shí)保存了寫入后的偏移
    lfs_off_t off;

    // entry tag，用于記錄當(dāng)前的ptag
    // ptag用于commit過程中計(jì)算異或tag、計(jì)算CRC等，見commit機(jī)制和tag的遍歷
    // 當(dāng)fetch時(shí)，fetch到一個(gè)commit時(shí)，會(huì)將計(jì)算的ptag存入etag
    // 當(dāng)進(jìn)行commit時(shí)，ptag就可以初始化為etag
    uint32_t etag;

    uint16_t count;         // 目錄中屬性數(shù)量（文件、子目錄數(shù)）

    // 表示下一個(gè)commit是否寫入完成
    // 用于commit和fetch相關(guān)函數(shù)，見commit機(jī)制和tag的遍歷
    // 當(dāng)fetch時(shí)，fetch到末尾還未匹配，會(huì)把erased置為true
    // 在commit函數(shù)中，只有erased為true才進(jìn)行commit
    bool erased;

    bool split;             // 表示當(dāng)前目錄塊后面是否還有塊，為false時(shí)表示末尾

    // 表示當(dāng)前目錄塊中最后一個(gè)TAIL
    // 既可能是HARDTAIL，也可能是SOFTTAIL
    // 與fetch機(jī)制、目錄的遍歷等有關(guān)
    lfs_block_t tail[2];

    // 注：off、etag、erased、tail與commit機(jī)制、tag的遍歷等有關(guān)，見后面的文章
} lfs_mdir_t;

另外，littlefs中，內(nèi)存中打開的目錄使用lfs_dir_t類型的數(shù)據(jù)結(jié)構(gòu)進(jìn)行記錄。見littlefs中mlist的介紹。

5、文件

文件的tag存儲(chǔ)于其父目錄的元數(shù)據(jù)對中。文件又分為inline文件和outline文件。當(dāng)文件剛創(chuàng)建時(shí)，默認(rèn)為inline文件。當(dāng)文件大小超過1/8 block_size、或超過文件cache大小時(shí)，會(huì)重新分配為outline文件。

（1）inline文件

具體tag存儲(chǔ)信息如下：

• REG：存儲(chǔ)文件名和id
• INLINESTRUCT：存儲(chǔ)inline文件的數(shù)據(jù)

（2）outline文件

如上圖，littlefs中outline文件的數(shù)據(jù)是用跳表存儲(chǔ)的。其中CTZSTRUCT類型的tag中存儲(chǔ)了文件大小和跳表頭指針信息，跳表頭指針指向了文件末尾的塊。跳表中每個(gè)塊對其他塊的指針儲(chǔ)存在該塊的塊頭處。

跳表中塊指針按固定規(guī)律分布：對block ，如果可以被整除，那么該block就含有一個(gè)指向block 的塊指針。以block 4為例：

• 4可以被整除，則block 4含有即block 3的塊指針。
• 4可以被整除，則block 4含有即block 2的塊指針。
• 4可以被整除，則block 4含有即block 0的塊指針。

由此規(guī)律，又因?yàn)閴K的大小是固定的，那么只要知道文件的偏移位置，就可以獲取該偏移位置所在block在跳表中的序號、該塊上有幾個(gè)塊指針等信息：

• 獲取跳表中塊序號：根據(jù)文件偏移和塊大小計(jì)算，相關(guān)函數(shù)為lfs_ctz_index。
• 獲取塊頭部塊指針數(shù)量：用ctz指令，ctz(塊序號)。

（3）相關(guān)數(shù)據(jù)結(jié)構(gòu)

文件在內(nèi)存中表示如下：

typedef struct lfs_file {
    // 以下4個(gè)成員與mlist相關(guān)，見后文mlist的介紹
    struct lfs_file *next;
    uint16_t id;
    uint8_t type;
    lfs_mdir_t m;

    struct lfs_ctz {
        lfs_block_t head;    // 跳表頭指針，inline文件時(shí)為LFS_BLOCK_INLINE
        lfs_size_t size;     // 文件大小，inline和outline文件均用此記錄
    } ctz;

    uint32_t flags;          // INLINE、OUTLINE、DIRTY、WRITING等標(biāo)志
    lfs_off_t pos;           // 文件當(dāng)前的偏移字節(jié)數(shù)
    lfs_block_t block;       // 文件當(dāng)前的block
    lfs_off_t off;           // 文件在當(dāng)前block的偏移
    lfs_cache_t cache;       // 文件緩存，用于讀寫等操作

    const struct lfs_file_config *cfg;    // 文件的其他配置信息
} lfs_file_t;

6、文件和目錄在內(nèi)存中的表示（mlist）

littlefs中，mlist用于記錄打開的文件和目錄，存在于內(nèi)存中。

mlist主要用于遍歷打開的文件和目錄。

（1）相關(guān)數(shù)據(jù)結(jié)構(gòu)

mlist

typedef struct lfs {
    ...
    struct lfs_mlist {
        struct lfs_mlist *next;    // 下一個(gè)鏈表中的節(jié)點(diǎn)
        uint16_t id;               // 文件或目錄在其父目錄中的id
        uint8_t type;              // 類型，表明是文件還是目錄
        lfs_mdir_t m;              // 父目錄元數(shù)據(jù)對信息
    } *mlist;
    ...
} lfs_t;

打開的文件

typedef struct lfs_file {
    struct lfs_file *next;   // 下一個(gè)鏈表中的節(jié)點(diǎn)
    uint16_t id;             // 文件在父目錄中的id
    uint8_t type;            // 類型，文件類型應(yīng)為LFS_REG_TYPE
    lfs_mdir_t m;            // 父目錄元數(shù)據(jù)對信息

    // 以下成員見上文中存儲(chǔ)結(jié)構(gòu)
    ...
} lfs_file_t;

打開的目錄

typedef struct lfs_dir {
    struct lfs_dir *next;    // 下一個(gè)鏈表中的節(jié)點(diǎn)
    uint16_t id;             // 目錄在父目錄中的id
    uint8_t type;            // 類型，目錄應(yīng)為LFS_DIR_TYPE
    lfs_mdir_t m;            // 父目錄元數(shù)據(jù)對信息

    lfs_off_t pos;           // 當(dāng)前目錄或文件在父目錄中的位置，.和..分別為0和1
    lfs_block_t head[2];     // 第一個(gè)元數(shù)據(jù)對所在塊號
} lfs_dir_t;

（2）記錄打開的文件和目錄

由前面的數(shù)據(jù)結(jié)構(gòu)，littlefs中mlist是一個(gè)單鏈表，其中記錄了打開的文件和目錄。 mlist既可以插入lfs_file_t，也可以插入lfs_dir_t，lfs_mlist、lfs_file_t和lfs_dir_t的前幾個(gè)成員的結(jié)構(gòu)體是相同的。

在打開文件過程中

打開文件時(shí)，相應(yīng)lfs_file_t類型的文件數(shù)據(jù)加入到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);
        |
        |-> ...

在關(guān)閉文件過程中

關(guān)閉文件時(shí)，mlist會(huì)刪除對應(yīng)的文件：

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);
    |
    |-> ...

在打開目錄過程中

打開命令時(shí)，相應(yīng)lfs_dir_t類型的目錄數(shù)據(jù)加入到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);

在關(guān)閉目錄過程中

關(guān)閉目錄時(shí)，mlist中會(huì)刪除對應(yīng)的目錄：

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);

總結(jié)

本文介紹了littlefs的整體結(jié)構(gòu)，包括超級塊、文件、目錄等在磁盤上的存儲(chǔ)，以及文件、目錄打開后在內(nèi)存中的表示，希望能讓讀者對littlefs有一個(gè)大概的印象。后續(xù)的文章會(huì)繼續(xù)分析littlefs原理。

??想了解更多關(guān)于開源的內(nèi)容，請?jiān)L問：??

??51CTO 開源基礎(chǔ)軟件社區(qū)??

??https://ost.51cto.com??。