文章详情

登录

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

选择考试省份

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团

请输入下面的图形验证码

提交验证

短信预约提醒成功

littlefs原理分析--目录操作（四）

2024-12-01 12:52

关注

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

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

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

前言

前面的三篇文章中分别介绍了littlefs的整体结构、commit机制和fetch操作。在介绍了 littlefs中元数据的读取和写入过程之后，这篇以及接下来的文章将开始对littlefs中的具体文件、目录操作和策略等进行介绍。

本文主要对目录的创建、删除和移动操作进行总结，包括目录操作的过程、操作之后目录的链接方式变化、目录操作中的一些特殊处理等。目录的读取、写入和遍历操作实际上在前面的文章中以及介绍过了，目录的读写实际上就是元数据的读写操作，目录的遍历实际上就是fetch tail的操作。

一、目录创建

1、commit过程

目录创建会进行两次commit。第一次commit时，是在新创建的目录元数据中插入指向父目录中末尾目录的块指针；第二次commit时，是在父目录元数据中插入新创建目录的块指针。

目录创建的过程是原子性的，只有第二次commit完成，父目录元数据中才会记录新创建的目录。

commit过程如下：

  1. 创建新目录。其中，SOFTTAIL指向父目录元数据中最后一个有效的SOFTTAIL，如果父目录中没有有效的SOFTTAIL，则SOFTTAIL为空。

  1. 父目录插入新目录。其中，SOFTTAIL指向子目录。

2、链接方式变化

创建目录实际上是在parent->dir tail的单链表直接插入新目录，变成parent->new dir->dir tail。

例如：向目录C中创建目录D，大致链接方式变化如下：

注：SOFTTAIL用箭头进行链接，只有SOFTTAIL为目录最后的TAIL时用实线表示。

用fetch遍历目录顺序的变化如下：

3、相关函数分析

lfs_mkdir(lfs_t *lfs, const char *path)
|-> lfs_rawmkdir(lfs_t *lfs, const char *path)
    |   // 1. 查找路径和父目录
    |-> lfs_dir_find(lfs, &cwd.m, &path, &id);
    |
    |   // 2. 分配新目录
    |-> lfs_dir_alloc(lfs, &dir);
    |
    |   // 3. 在新目录中进行commit
    |   // 存储一个指向父目录末尾目录的块指针
    |-> lfs_dir_commit(lfs, &dir, LFS_MKATTRS(
    |       {LFS_MKTAG(LFS_TYPE_SOFTTAIL, 0x3ff, 8), pred.tail}));
    |
    |   // 4. 在父目录中进行commit
    |   // 将新目录插入父目录
    |-> lfs_dir_commit(lfs, &cwd.m, LFS_MKATTRS(
    |       {LFS_MKTAG(LFS_TYPE_CREATE, id, 0), NULL},
    |       {LFS_MKTAG(LFS_TYPE_DIR, id, nlen), path},
    |       {LFS_MKTAG(LFS_TYPE_DIRSTRUCT, id, 8), dir.pair},
    |       {LFS_MKTAG_IF(!cwd.m.split,
    |           LFS_TYPE_SOFTTAIL, 0x3ff, 8), dir.pair}));

二、目录删除

1、commit过程

目录删除的过程分为两个步骤：

  1. 在其父目录中commit一个DELETE类型的tag，表示从父目录中将目录删除。该步骤与文件删除的过程类似。如下图：


2. 在被删除目录的前继目录（其tail指向被删除的目录）中commit新的SOFTTAIL类型的tag，表示断开与将要删除目录的链接。新的SOFTTAIL指向被删除目录的后继目录（被删除目录tail指向的目录）。如下图：

注：上图的commit中还有一个MOVESTATE类型的tag，该tag与gstate和orphan目录有关，见后面目录删除和移动操作中异常情况的分析。

2、链接方式变化

例如，删除目录B，其链接方式变化如下：


用fetch遍历目录顺序的变化如下：

3、相关函数分析

lfs_remove(lfs_t *lfs, const char *path)
|-> lfs_rawremove(lfs_t *lfs, const char *path)
    |   // 1. 查找路径和父目录
    |-> lfs_dir_find(lfs, &cwd, &path, NULL);
    |
    |   // 2. 在父目录中commit一个DELETE tag
    |-> lfs_dir_commit(lfs, &cwd, LFS_MKATTRS(
    |       {LFS_MKTAG(LFS_TYPE_DELETE, lfs_tag_id(tag), 0), NULL}));
    |
    |   // 3. 找到删除目录的前继目录
    |-> lfs_fs_pred(lfs, dir.m.pair, &cwd);
    |
    |   // 4. 断开删除目录与前继目录的链接
    |-> lfs_dir_drop(lfs, &cwd, &dir.m);

4、orphan目录

目录删除的过程时，有可能因为掉电等原因产生一个中间状态，即第一次commit成功，而第二次commit失败。例如，删除目录B，但只完成了第一步：

此时目录B就成了orphan目录。

为了解决这个问题，littlefs中采用了gstate机制来进行异常状态的记录和检查。

（1）gstate机制简介

gstate是littlefs内存中维护的一组全局状态，同时可作为MOVESTATE tag存储于磁盘中。简而言之，gstate机制通过如下方法记录和检查异常状态：

（2）orphan状态的记录和修复

当进行目录删除操作时，磁盘中orphan状态的记录和修复步骤如下：

  1. 第一次commit，从父目录中将目录删除。此时记录MOVESTATE tag于父目录的元数据中。链接方式变化如下图：

  1. 第二次commit，这次即可能发生在第一次commit后，也可能是掉电后通过检查gstate发现异常后的修复操作。此时记录MOVESTATE tag于被删除目录的前继目录的元数据中。该MOVESTATE tag数据与在父目录元数据中记录的值相对应，这样gstate检查时进行异或计算就可与前面记录的MOVESTATE tag进行抵消，表示异常已解决。链接方式变化如下图：

当进行目录删除操作时，内存gstate中orphan状态的记录和恢复步骤如下：

  1. 第一次commit前，标记gstate为orphan状态。这样第一次commit时就可以记录MOVESTATE tag。
  2. 第一次commit后，还原gstate

记录orphan状态相关代码分析如下：

lfs_remove(lfs_t *lfs, const char *path)
|-> lfs_rawremove(lfs_t *lfs, const char *path)
 |-> ...
 |
 |   // 在第一次commit前记录gstate
 |-> lfs_fs_preporphans(lfs, +1);
 |
 |   // 第一次commit，会记录MOVESTATE tag
 |-> lfs_dir_commit(lfs, &cwd, LFS_MKATTRS(
 |       {LFS_MKTAG(LFS_TYPE_DELETE, lfs_tag_id(tag), 0), NULL}));
 |
 |   // 在第一次commit后恢复gstate
 |-> lfs_fs_preporphans(lfs, -1);
 |
 |-> ...

修复orphan状态相关代码分析如下：

// 该函数在mount后进行检查时被调用
lfs_fs_deorphan(lfs_t *lfs)
|   // 遍历文件系统
|-> while (...) {
    |   // 1. 查找当前orphan目录的父目录
    |-> lfs_stag_t tag = lfs_fs_parent(lfs, pdir.tail, &parent);
    |
    |   // 2. 如果当前目录没有父目录，则当前目录为orphan目录，进行恢复
    |-> if (tag == LFS_ERR_NOENT) {
    |       lfs_dir_drop(lfs, &pdir, &dir);
            |   // 2.1 检查目录中的异常状态并记录于gstate
            |-> lfs_dir_getgstate(lfs, tail, &lfs->gdelta);
            |
            |   // 2.2 commit新的TAIL类型tag，完成目录删除的第二次commit操作
            |   // 同时写入MOVESTATE tag
            |-> lfs_dir_commit(lfs, dir, LFS_MKATTRS(
            |        {LFS_MKTAG(LFS_TYPE_TAIL + tail->split, 0x3ff, 8), tail->tail}));
    |   }
|   }

三、目录移动

1、commit过程

littlefs中将目录或文件从旧的父目录移动到新的父目录下主要经过两个步骤：

  1. 在新父目录中commit，创建目录并指向将要移动的目录。其中，如果新父目录下已经存在一个同名的文件或目录，需要先将其删除。值得注意的是，与创建目录时不同，这里父目录下并没有commit一个SOFTTAIL类型的tag。如下图：

  1. 在旧父目录中commit，删除要移动的目录。如下图：

注：上图的commit中还有一个MOVESTATE类型的tag，该tag与gstate和move状态有关，见后面move状态相关分析。

2、链接方式变化

在目录的移动过程中，新父目录中没有commit一个新的SOFTTAIL，旧父目录中也没有commit一个新的SOFTTAIL覆盖原来的SOFTTAIL。由于链接方式和遍历顺序只与TAIL类型的tag有关，因此目录移动后，其链接方式并没有变化，只是存储结构发生了变化，遍历时目录的顺序仍然不变。

3、相关函数分析

lfs_rename(lfs_t *lfs, const char *oldpath, const char *newpath)
|-> lfs_rawrename(lfs_t *lfs, const char *oldpath, const char *newpath)
    |   // 1. 查找旧路径和旧父目录
    |-> lfs_stag_t oldtag = lfs_dir_find(lfs, &oldcwd, &oldpath, NULL);
    |
    |   // 2. 查找新路径和新父目录
    |-> lfs_stag_t prevtag = lfs_dir_find(lfs, &newcwd, &newpath, &newid);
    |
    |   // 3. 在新父目录中进行commit
    |   // 3.1 如果新路径下已经存在一个文件或目录，则将其删除
    |   // 3.2 在新父目录下创建将要移动的目录
    |-> lfs_dir_commit(lfs, &newcwd, LFS_MKATTRS(
    |       {LFS_MKTAG_IF(prevtag != LFS_ERR_NOENT,
    |           LFS_TYPE_DELETE, newid, 0), NULL},
    |       {LFS_MKTAG(LFS_TYPE_CREATE, newid, 0), NULL},
    |       {LFS_MKTAG(lfs_tag_type3(oldtag), newid, strlen(newpath)), newpath},
    |       {LFS_MKTAG(LFS_FROM_MOVE, newid, lfs_tag_id(oldtag)), &oldcwd},
    |       {LFS_MKTAG_IF(samepair,
    |           LFS_TYPE_DELETE, newoldid, 0), NULL}));
    |
    |   // 4. 在旧父目录中删除被移动目录
    |-> lfs_dir_commit(lfs, &oldcwd, LFS_MKATTRS(
    |           {LFS_MKTAG(LFS_TYPE_DELETE, lfs_tag_id(oldtag), 0), NULL})

4、move状态

与目录删除过程中类似，在目录移动的过程中，当第一次commit成功，但第二次commit因为掉电等原因未完成时，也产生一个中间状态。例如，将目录C从A移动到B：

注：上图中实线只表示存储结构关系。

此时目录B标记为move状态。同样的，move状态也是通过gstate机制进行检查和修复。

（1）move状态的记录和修复

当进行目录移动操作时，与orphan状态的记录和恢复类似，磁盘中orphan状态的记录和修复步骤如下：

  1. 第一次commit，在新父目录下创建目录，此时记录MOVESTATE tag于新父目录的元数据中。存储结构变化如下图：


2. 第二次commit，从旧父目录中删除目录，此时记录MOVESTATE tag于旧目录的元数据中。类似的，这次即可能发生在第一次commit后，也可能是掉电后通过检查gstate发现异常后的修复操作。链接方式变化如下图：


当进行目录删除操作时，内存gstate中move状态的记录和恢复步骤如下：

  1. 第一次commit前，标记gstate为move状态。这样第一次commit时就可以记录MOVESTATE tag。
  2. 第一次commit后，还原gstate

记录move状态相关代码分析如下：

lfs_rename(lfs_t *lfs, const char *oldpath, const char *newpath)
|-> lfs_rawrename(lfs_t *lfs, const char *oldpath, const char *newpath)
    |-> ...
    |
    |   // 1. 在第一次commit前记录move状态到gstate
    |-> lfs_fs_prepmove(lfs, newoldid, oldcwd.pair);
    |
    |   // 2. 在新父目录中进行commit
    |-> lfs_dir_commit(lfs, &newcwd, LFS_MKATTRS(
    |       {LFS_MKTAG_IF(prevtag != LFS_ERR_NOENT,
    |           LFS_TYPE_DELETE, newid, 0), NULL},
    |       {LFS_MKTAG(LFS_TYPE_CREATE, newid, 0), NULL},
    |       {LFS_MKTAG(lfs_tag_type3(oldtag), newid, strlen(newpath)), newpath},
    |       {LFS_MKTAG(LFS_FROM_MOVE, newid, lfs_tag_id(oldtag)), &oldcwd},
    |       {LFS_MKTAG_IF(samepair,
    |           LFS_TYPE_DELETE, newoldid, 0), NULL}));
    |
    |   // 3. 恢复gstate中的move状态
    |-> lfs_fs_prepmove(lfs, 0x3ff, NULL);
    |
    |   // 4. 在旧父目录中删除被移动目录
    |-> lfs_dir_commit(lfs, &oldcwd, LFS_MKATTRS(
    |           {LFS_MKTAG(LFS_TYPE_DELETE, lfs_tag_id(oldtag), 0), NULL})

修复move状态相关代码分析如下：

// 该函数在mount后进行检查时被调用
lfs_fs_demove(lfs_t *lfs)
|-> ...
|
|   // 在新目录中删除被移动目录的id，并恢复gstate
|-> uint16_t moveid = lfs_tag_id(lfs->gdisk.tag);
|   lfs_fs_prepmove(lfs, 0x3ff, NULL);
|   lfs_dir_commit(lfs, &movedir, LFS_MKATTRS(
|           {LFS_MKTAG(LFS_TYPE_DELETE, moveid, 0), NULL}));

总结

本文对目录创建、目录删除和目录移动操作进行了分析，包括目录操作的过程、操作之后目录的链接方式变化、目录操作中的一些特殊处理等内容。接下来的文章将会介绍littlefs系统的文件相关操作。

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

​​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推送时光机

littlefs原理分析--目录操作（四）

后端开发littlefs目录操作2024-12-01

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

后端开发LittlefsFetch操作2024-12-01

Linux/Unix操作系统目录结构的示例分析

后端开发2023-06-13

python文件目录操作之os模块的示例分析

后端开发2023-06-15

Java文件与IO流操作原理详细分析

后端开发2024-04-02

node.js中fs文件系统目录操作与文件信息操作的示例分析

后端开发2024-04-02

vue项目环境搭建 启动 移植操作示例及目录结构分析

后端开发2024-04-02

ThinkPHP框架SQL操作链式写法原理的示例分析

后端开发2023-06-14

Docker和宿主机操作系统文件目录互相隔离的实现原理

后端开发2023-06-04

基于红黑树插入操作原理及java实现的示例分析

后端开发2023-05-30

Android系统 Settings数据库读写操作和数据监听变化原理分析

后端开发2023-09-02

【综合评价分析】熵权算法确定权重 原理+完整MATLAB代码+详细注释+操作实列

后端开发2023-08-31
位置：首页-资讯-后端开发
咦！没有更多了？去看看其它编程学习网 内容吧
首页课程
资料下载问答资讯