文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

Littlefs原理分析--Fetch操作(三)

2024-12-01 12:53

关注

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

​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、文件和目录的读取

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

  1. 遍历查找到REG(DIR)类型的tag,获取文件(目录)名和文件(目录)id
  2. 根据文件(目录)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,如打开文件时查找匹配文件的对应tag
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)
|-> ...
|
| // 如果当前遍历到的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。以上图为例:

  1. 第一次调用lfs_dir_fetch,dir->tail中保存的tail为HARDTAIL,指向该目录的下一个元数据块
  2. 第二次调用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​

来源:51CTO开源基础软件社区内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯