#littlefs原理分析#[一]存储结构

您所在的位置：网站首页 › 鸿蒙系统架构原理图片大全 › #littlefs原理分析#[一]存储结构

#littlefs原理分析#[一]存储结构

2024-07-09 21:12| 来源: 网络整理| 查看: 265

作者：蒋卫峰李涛

前言

littlefs是一个小型的文件系统，其特点有：

（1）具有磨损均衡功能；

（2）具有掉电保护能力；

（3）适用于ROM和RAM有限的场景。

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

1. 总览

littlefsstructurestructure.drawio.png

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

2. 元数据对

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

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

littlefsstructuremetadata pair.drawio.png

以下为具体说明：

一个元数据对与物理上的两个块相对应，且均记录了一个revision count。revision count较大的块存储的为较新的内容，每当更新其中的数据时，revision count就会加1。使用两个块的好处是，当一个块放不下更新的内容时，可以将数据压缩并转存到另一个块上（如进行compact操作），避免直接破坏原有的数据。每个超级块、目录均有其对应的一个或多个元数据对，其中记录了超级块或目录相关的信息。如目录对应的元数据对中可能存储该目录下的文件信息等。元数据对以tag为单元进行信息的存储，以commit的方式进行信息的更新，这里是借鉴了logging文件系统的做法。如创建一个目录，就会在对应的元数据对中进行一次commit，记录CREATE、DIR、DIRSTRUCT等tag，最后计算CRC。元数据对每次进行commit时会计算CRC，以实现数据的校验等功能。 2.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。超级块以单个或多个元数据对的方式进行存储，下图为单个元数据对存储超级块的具体情形：

littlefsstructuresuper block.drawio.png 其中包含了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. 目录

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

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

littlefsstructuredirectory.drawio.png

上图中，中间的目录使用了两个元数据对进行存储。第一个元数据对中SOFTTAIL类型的tag中存储了指向父目录中末尾目录的块指针（即在父目录中最后创建的子目录，当父目录中还没有创建子目录时，该块指针为空）。第二个元数据对中存储了创建的子目录的信息（包括CREATE、DIR、DIRSTRUCT等类型的tag），并指向了子目录。

注：上述目录与其父目录、子目录之间的链接方式只是可能的一种情况。随着目录的创建、删除、移动等操作，具体的链接方式会发生变化，具体见后面的文章。

其中相关tag的表示如下：

元数据对的块指针相关：

HARDTAIL：表示同一目录的下一个元数据对的块指针

SOFTTAIL：表示不同目录的下一个元数据对的块指针

目录创建信息相关：在父目录中会记录CREATE、DIR、DIRSTRUCT、SOFTTAIL等类型的tag

DIR：存储目录名和id

DIRSTRUCT：存储创建的子目录的元数据对的块指针

SOFTTAIL：记录了创建的子目录的元数据对的块指针

4.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文件。

5.1 inline文件

littlefsstructureinline file.drawio.png

具体tag存储信息如下：

REG：存储文件名和id

INLINESTRUCT：存储inline文件的数据

5.2 outline文件

littlefsstructureoutline file.drawio.png

如上图，littlefs中outline文件的数据是用跳表存储的。其中CTZSTRUCT类型的tag中存储了文件大小和跳表头指针信息，跳表头指针指向了文件末尾的块。跳表中每个块对其他块的指针储存在该块的块头处。

跳表中块指针按固定规律分布：对block $n$，如果$n$可以被$2^x$整除，那么该block就含有一个指向block $n-2^x$的块指针。以block 4为例：

4可以被$2^0$整除，则block 4含有$4-2^0$即block 3的块指针

4可以被$2^1$整除，则block 4含有$4-2^1$即block 2的块指针

4可以被$2^2$整除，则block 4含有$4-2^2$即block 0的块指针

由此规律，又因为块的大小是固定的，那么只要知道文件的偏移位置，就可以获取该偏移位置所在block在跳表中的序号、该块上有几个块指针等信息：

获取跳表中块序号：根据文件偏移和块大小计算，相关函数为lfs_ctz_index

获取块头部块指针数量：用ctz指令，ctz(块序号)

5.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主要用于遍历打开的文件和目录。

6.1 相关数据结构 6.1.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; 6.1.2 打开的文件 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; 6.1.3 打开的目录 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; 6.2 记录打开的文件和目录

由前面的数据结构，littlefs中mlist是一个单链表，其中记录了打开的文件和目录。 mlist既可以插入lfs_file_t，也可以插入lfs_dir_t，lfs_mlist、lfs_file_t和lfs_dir_t的前几个成员的结构体是相同的。

6.2.1 在打开文件过程中

打开文件时，相应lfs_file_t类型的文件数据加入到mlist：

关闭文件时，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); | |-> ... 6.2.3 在打开目录过程中

打开命令时，相应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); 6.2.4 在关闭目录过程中

关闭目录时，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原理。

本文作者：深开鸿Kaihong

想了解更多关于开源的内容，请访问：

51CTO 开源基础软件社区

https://ost.51cto.com/#bkwz

【本文地址】

#littlefs原理分析#[一]存储结构

#littlefs原理分析#[一]存储结构

今日新闻

推荐新闻