Littlefs原理分析--Fetch操作（三）-fetch的原理

Littlefs原理分析--Fetch操作（三）

作者：蒋卫峰 李涛 2022-11-07 15:27:07系统 OpenHarmony 本文介绍Fetch操作的流程及作用，描述了Littlefs中是怎样通过遍历元数据中的Tag和数据，来获取所需信息的。

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

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

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

前言

前面的littlefs原理分析文章中，第一篇介绍了littlefs的整体结构，第二篇介绍了littlefs中记录元数据的方式，即commit机制。这一篇（littlefs原理分析：（3）fetch操作）的主要内容是介绍littlefs中的fetch操作，这部分还是与元数据有关，不过commit过程是写入元数据，fetch操作是读取元数据。

commit时记录了如超级块、文件、目录的创建、删除等操作。而如何去从这些记录中获取所需的信息（如打开文件时需要从其父目录的元数据中获取文件的块指针），则是通过对元数据中tag的遍历来完成。

fetch操作实际上就是对元数据中tag的遍历，其功能是遍历指定NAME类型的tag，如查找文件、目录等，获取文件、目录id等数据。commit过程中写入tag时也是通过tag的遍历来完成的，不同的是fetch操作一般只用于读取commit中记录的数据，而commit过程中调用的lfs_dir_traverse函数一般只用于写入。

一、fetch作用说明

fetch操作在littlefs中主要用于文件和目录的读取，和目录的遍历。

下面结合具体的文件、目录操作，对其相应的commit过程、以及commit之后如何结合fetch操作获取相应数据，进行说明：

1、文件和目录的读取

在已知父目录的元数据块的情况下，文件和目录的读取可以分为以下两个步骤：

遍历查找到REG（DIR）类型的tag，获取文件（目录）名和文件（目录）id根据文件（目录）id再次遍历tag找到相应数据tag，即INLINESTRUCT或CTZSTRUCT（DIRSTRUCT）

fetch操作完成了第一步，以下结合具体案例对fetch过程进行说明：

（1）文件创建后

文件刚创建时为inline文件：

此时遍历查找到与文件路径匹配的REG类型的tag，就能够获取文件名和文件id、再通过其文件id再次遍历tag就能够获取文件的数据。

如打开刚创建的文件：

lfs_file_rawopencfg(lfs_t *lfs, lfs_file_t *file,| const char *path, int flags,| const struct lfs_file_config *cfg) | // 1. 根据路径查找对应tag和id| // 此时查找的为REG类型的tag，查找到的文件id存储在file->id|-> lfs_stag_t tag = lfs_dir_find(lfs, &file->m, &path, &file->id);|| // 2. 根据文件id查找文件数据对应tag| // 此时查找的为STRUCT类型的tag，包括inline文件和outline文件|-> tag = lfs_dir_get(lfs, &file->m, LFS_MKTAG(0x700, 0x3ff, 0),| LFS_MKTAG(LFS_TYPE_STRUCT, file->id, 8), &file->ctz);||->...

（2）文件删除后

如删除刚创建的文件：

进行文件或目录的删除操作时，会写入DELETE和CRC类型的tag。其中，CREATE和DELETE类型的tag中的id存储了相应创建或删除的文件或目录的id。

此时若再打开该文件，在遍历tag时，由于检查到了包含对应id的DELETE类型tag，则会返回失败。

在遍历获取文件、目录数据的相关函数中，对DELETE类型tag的相关检测分析如下：

// 该函数用于遍历时查找匹配的tag，如打开文件时查找匹配文件的对应taglfs_stag_t lfs_dir_fetchmatch(lfs_t *lfs,| lfs_mdir_t *dir, const lfs_block_t pair[2],| lfs_tag_t fmask, lfs_tag_t ftag, uint16_t *id,| int (*cb)(void *data, lfs_tag_t tag, const void *buffer), void *data) |-> ...|| // 如果当前遍历到的tag的类型为DELETE，且其id与tempbesttag中id相同| // 则将tempbesttag置为无效。|-> if (tag == (LFS_MKTAG(LFS_TYPE_DELETE, 0, 0) ||(LFS_MKTAG(0, 0x3ff, 0) & tempbesttag))) {| tempbesttag |= 0x80000000;| }|->...

（3）其他

目录创建、删除后的读取过程与文件创建、删除后的类似目录、文件的移动实际上是创建过程和删除过程的结合，先在新父目录下创建，再在旧父目录下删除。其读取过程也类似。

2、目录的遍历

littlefs中目录的遍历是通过TAIL类型的tag来进行的，TAIL类型tag在littlefs存储结构中已说明，分为SOFTTAIL和HARDTAIL。每个目录对应的元数据块中都可能存储指向其他目录的SOFTTAIL或者指向该目录下一个元数据块的HARDTAIL。

如何从一个目录跳转到其后继目录，其实就是通过fetch tail的操作实现。

本节中着重介绍fetch tail的过程，即已知其父目录的情况下，如何跳转到后继目录。目录的链接方式见后面的文章。

（1）fetch tail

在父目录中会记录其子目录的创建信息，并会有相应的SOFTTAIL指向该子目录。具体目录操作后目录的链接方式见后面的文章，这里只是以一个包含多个子目录的父目录的例子来对fetch tail的过程进行说明。

下图中父目录有两个元数据对，包含了指向子目录A、B、C的SOFTTAIL：

在fetch操作对应函数lfs_dir_fetchmatch中，能够检查到TAIL类型的tag更新传入的参数dir->tail，保存TAIL指向的元数据对块。

littlefs中通常是fetch最后一个TAIL，在上图中即为HARDTAIL和目录C。littlefs目录链接相关的机制保证这样遍历能够从根目录遍历完所有目录。相关函数为lfs_dir_fetch：

int lfs_dir_fetch(lfs_t *lfs,lfs_mdir_t *dir, // fetch tail结果存储在dir->tail中const lfs_block_t pair[2] // 父目录元数据对所在块) {// 调用lfs_dir_fetchmatch实现// 其中fmask、ftag为-1，表示不进行匹配，会fetch到元数据末尾return (int)lfs_dir_fetchmatch(lfs, dir, pair,(lfs_tag_t)-1, (lfs_tag_t)-1, NULL, NULL, NULL);}

因为TAIL类型的tag分为SOFTTAIL和HARDTAIL，因此最后dir->tail中保存的tail既可能是HARDTAIL，也可能是SOFTTAIL。以上图为例：

第一次调用lfs_dir_fetch，dir->tail中保存的tail为HARDTAIL，指向该目录的下一个元数据块第二次调用lfs_dir_fetch，dir->tail中保存的tail为SOFTTAIL，指向子目录C

（2）fetch下一个目录

上小节中，lfs_dir_fetch既可以fetch HARDTAIL，也可以fetch SOFTTAIL。而fetch过程中同时会更新dir->split成员，该成员表示当前目录块是否有再分，当dir->split为false即表示在当前目录块的末尾。

由此littlefs中常用以下方法fetch下一个目录：

lfs_mdir_t m = dir.m;while (m.split) {lfs_dir_fetch(lfs, &m, m.tail);}

（3）目录删除和移动后

如果SOFTTAIL对应的目录已被删除或移动，那么在该CREATE等tag后应有一个DELETE类型的tag。但该DELETE类型tag对fetch tail的过程没有影响。目录的链接方式只与SOFTTAIL类型tag有关。目录删除和移动后具体的链接方式变化见后面的文章。

二、fetch流程

fetch操作的相关函数为lfs_dir_fetchmatch，该函数遍历tag并从中匹配和获取数据。该函数定义在上节中已提到，该函数匹配到tag之后会执行相应的回调函数，回调函数一般为对tag和相应数据进行进一步的比较和匹配。流程如下：

代码分析如下：

static lfs_stag_t lfs_dir_fetchmatch(lfs_t *lfs,| lfs_mdir_t *dir, const lfs_block_t pair[2],| lfs_tag_t fmask, lfs_tag_t ftag, uint16_t *id,| int (*cb)(void *data, lfs_tag_t tag, const void *buffer), void *data) {| // 用besttag保存最佳匹配结果|-> lfs_stag_t besttag = -1;||-> ...|| // 准备用于暂存每次匹配中的最佳匹配结果、更新等变量|-> uint16_t tempcount = 0;| lfs_block_t temptail[2] = {LFS_BLOCK_NULL, LFS_BLOCK_NULL};| bool tempsplit = false;| lfs_stag_t tempbesttag = besttag;|| // fetch主流程|-> while (true) {| // 1. 从磁盘中解析下一个tag并计算tag的CRC|-> lfs_bd_read(lfs,| NULL, &lfs->rcache, lfs->cfg->block_size,| dir->pair[0], off, &tag, sizeof(tag));| crc = lfs_crc(crc, &tag, sizeof(tag));| tag = lfs_frombe32(tag) ^ ptag;|| // 2. 检查边界，当不在范围内或tag无效时跳出循环|-> if (!lfs_tag_isvalid(tag)) {| dir->erased = (lfs_tag_type1(ptag) == LFS_TYPE_CRC &&| dir->off % lfs->cfg->prog_size == 0);| break;| } else if (off + lfs_tag_dsize(tag) > lfs->cfg->block_size) {| dir->erased = false;| break;| }|| // 3. 如果tag为CRC，则检查CRC并更新最佳匹配结果|-> if (lfs_tag_type1(tag) == LFS_TYPE_CRC) {| // 3.1 检查CRC|-> uint32_t dcrc;| lfs_bd_read(lfs,| NULL, &lfs->rcache, lfs->cfg->block_size,| dir->pair[0], off+sizeof(tag), &dcrc, sizeof(dcrc));| if (crc != dcrc) {| dir->erased = false;| break;| }|| // 3.2 更新最佳匹配结果等|-> besttag = tempbesttag;| dir->off = off + lfs_tag_dsize(tag);| dir->etag = ptag;| dir->count = tempcount;| dir->tail[0] = temptail[0];| dir->tail[1] = temptail[1];| dir->split = tempsplit;|| // 3.3 重置CRC|-> crc = 0xffffffff;| continue;}|| // 4. 计算entry的CRC|-> for (lfs_off_t j = sizeof(tag); j < lfs_tag_dsize(tag); j++) {| uint8_t dat;| lfs_bd_read(lfs,| NULL, &lfs->rcache, lfs->cfg->block_size,| dir->pair[0], off+j, &dat, 1);| ...| crc = lfs_crc(crc, &dat, 1);| }|| // 5. 根据tag类型进行相应更新|-> if (lfs_tag_type1(tag) == LFS_TYPE_NAME) {| // 5.1 tag为NAME类型，则根据其中id更新目录中count | // 目录中的最后一个id为count-1| if (lfs_tag_id(tag) >= tempcount) {| tempcount = lfs_tag_id(tag) + 1;| }| } else if (lfs_tag_type1(tag) == LFS_TYPE_SPLICE) {| // 5.2 tag为DELETE类型，如果id和目前的最佳匹配结果对应| // 则将最佳匹配结果置为无效| if (tag == (LFS_MKTAG(LFS_TYPE_DELETE, 0, 0) || (LFS_MKTAG(0, 0x3ff, 0) & tempbesttag))) {| tempbesttag |= 0x80000000;| }| ...| } else if (lfs_tag_type1(tag) == LFS_TYPE_TAIL) {| // 5.3 tag为TAIL类型，则更新tempsplit和temptail| tempsplit = (lfs_tag_chunk(tag) & 1);| lfs_bd_read(lfs,| NULL, &lfs->rcache, lfs->cfg->block_size,| dir->pair[0], off+sizeof(tag), &temptail, 8);| ...| }|| // 6. 先用fmask和ftag参数进行初次匹配|-> if ((fmask & tag) == (fmask & ftag)) {| // 6.1 如果匹配则调用cb回调函数进行进一步匹配 | int res = cb(data, tag, &(struct lfs_diskoff){| dir->pair[0], off+sizeof(tag)});| ... | // 6.2 如果匹配成功则更新到最佳匹配结果 | if (res == LFS_CMP_EQ) {| tempbesttag = tag;| } else if (...)| ...| }| }|| // 如果读到结束，则根据最佳匹配结果返回相应值|-> if (dir->off > 0) {| ... || if (lfs_tag_isvalid(besttag)) {| return besttag;| } else if (lfs_tag_id(besttag) < dir->count) {| return LFS_ERR_NOENT;| } else {| return 0;| }| }||->...

1、tag和数据的读取

如上文中对fetch流程的分析，也和commit时tag和数据写入的过程类似，fetch等操作时遍历读取tag的数据如下图所示：

如上图，tag和数据的读取过程实际上与commit时tag和数据写入的过程相对称。在tag和数据的读取过程中，ptag用于进行tag的异或运算，其初始化值为0xffffffff。ptag会依次与将要commit的tag（如上图中的tagA、tagB、tagC）进行异或运算，每次运算后的结果即为读取出来的tag。同时每读取一个tag后，其对应的数据也能够相应进行解析。

2、crc的校验

如上文中对fetch流程的分析，在fetch过程中会进行crc的校验，以检验commit是否有效。crc校验时仍用lfs_crc函数进行计算，该函数在上一篇文章中已作说明。

crc校验从元数据块中的revision count开始，逐个与tag或数据进行计算，每当遇到crc tag时，则将当前crc结果与crc tag对应crc值进行比对。如果不匹配，则当前commit以及其后的commit中所有tag和数据将会被视为无效。crc的校验使得commit操作具有原子性。

总结

本文介绍了fetch操作的流程及作用，描述了littlefs中是怎样通过遍历元数据中的tag和数据，来获取所需信息的。后面的文章将会开始介绍具体的目录和文件操作。

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

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

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

责任编辑：jianghua 来源：51CTO开源基础软件社区 LittlefsFetch操作