10

littlefs原理分析--存储结构(一)

 2 years ago
source link: https://www.51cto.com/article/721451.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

littlefs原理分析--存储结构(一)

作者:蒋卫峰 李涛 2022-10-27 16:07:24
本文介绍littlefs的整体结构,包括超级块、文件、目录等在磁盘上的存储,以及文件、目录打开后在内存中的表示,希望能让读者对littlefs有一个大概的印象。
02f3a549887b947eece068fa6eaf1701cf72de.png

​想了解更多关于开源的内容,请访问:​

​51CTO 开源基础软件社区​

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

littlefs是一个小型的文件系统,其特点有:

(1)具有磨损均衡功能。

(2)具有掉电保护能力。

(3)适用于ROM和RAM有限的场景。

本系列文章将对littlefs的原理进行分析。作为系列的第一篇,首先对littlefs整体的存储结构进行介绍,在后面的文章中,再对具体的目录、文件操作等进行分析。

#littlefs原理分析#[一]存储结构-开源基础软件社区

littlefs的存储结构大体上如上图所示。其中超级块是littlefs存储目录和文件的起点,根目录紧随其后。littlefs中的目录均可以指向其他的目录,构成树状结构。在目录中可以包含多个文件,上图中右边的目录中即包含了一个inline文件和一个outline文件。

2、元数据对

在对littlefs的存储结构进行具体介绍之前,先对littlefs中一个核心的数据结构,即元数据,进行介绍。littlefs中使用元数据对存储目录信息、超级块信息、文件信息、inline文件的数据等内容,是其设计的核心数据结构。

元数据对的存储结构如下图:

#littlefs原理分析#[一]存储结构-开源基础软件社区

以下为具体说明:

  • 一个元数据对与物理上的两个块相对应,且均记录了一个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原理分析#[一]存储结构-开源基础软件社区

其中包含了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;

目录的存储结构如上文总览中所示,以单个或多个元数据对的方式进行存储。以根目录为起点,通过末尾对其他元数据对的块指针,可以构成一个树形结构。

单个目录的元数据对具体存储如下图:

#littlefs原理分析#[一]存储结构-开源基础软件社区

上图中,中间的目录使用了两个元数据对进行存储。第一个元数据对中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的介绍。

文件的tag存储于其父目录的元数据对中。文件又分为inline文件和outline文件。当文件刚创建时,默认为inline文件。当文件大小超过1/8 block_size、或超过文件cache大小时,会重新分配为outline文件。

(1)inline文件

#littlefs原理分析#[一]存储结构-开源基础软件社区

具体tag存储信息如下:

  • REG:存储文件名和id
  • INLINESTRUCT:存储inline文件的数据

(2)outline文件

#littlefs原理分析#[一]存储结构-开源基础软件社区

如上图,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​​。

责任编辑:jianghua 来源: 51CTO开源基础软件社区

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK