littlefs原理分析--目录操作(四)
littlefs原理分析--目录操作(四)
作者:蒋卫峰 李涛 2022-11-09 08:52:57系统 OpenHarmony 本文对目录创建、目录删除和目录移动操作进行了分析,包括目录操作的过程、操作之后目录的链接方式变化、目录操作中的一些特殊处理等内容。想了解更多关于开源的内容,请访问:
51CTO开源基础软件社区
https://ost.51cto.com
前言
前面的三篇文章中分别介绍了littlefs的整体结构、commit机制和fetch操作。在介绍了 littlefs中元数据的读取和写入过程之后,这篇以及接下来的文章将开始对littlefs中的具体文件、目录操作和策略等进行介绍。
本文主要对目录的创建、删除和移动操作进行总结,包括目录操作的过程、操作之后目录的链接方式变化、目录操作中的一些特殊处理等。目录的读取、写入和遍历操作实际上在前面的文章中以及介绍过了,目录的读写实际上就是元数据的读写操作,目录的遍历实际上就是fetch tail的操作。
一、目录创建
1、commit过程
目录创建会进行两次commit。第一次commit时,是在新创建的目录元数据中插入指向父目录中末尾目录的块指针;第二次commit时,是在父目录元数据中插入新创建目录的块指针。
目录创建的过程是原子性的,只有第二次commit完成,父目录元数据中才会记录新创建的目录。
commit过程如下:
创建新目录。其中,SOFTTAIL指向父目录元数据中最后一个有效的SOFTTAIL,如果父目录中没有有效的SOFTTAIL,则SOFTTAIL为空。父目录插入新目录。其中,SOFTTAIL指向子目录。2、链接方式变化
创建目录实际上是在parent->dir tail的单链表直接插入新目录,变成parent->new dir->dir tail。
例如:向目录C中创建目录D,大致链接方式变化如下:
注:SOFTTAIL用箭头进行链接,只有SOFTTAIL为目录最后的TAIL时用实线表示。
用fetch遍历目录顺序的变化如下:
前:A->C->B后:A->C->D->B3、相关函数分析
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过程
目录删除的过程分为两个步骤:
在其父目录中commit一个DELETE类型的tag,表示从父目录中将目录删除。该步骤与文件删除的过程类似。如下图:2. 在被删除目录的前继目录(其tail指向被删除的目录)中commit新的SOFTTAIL类型的tag,表示断开与将要删除目录的链接。新的SOFTTAIL指向被删除目录的后继目录(被删除目录tail指向的目录)。如下图:
注:上图的commit中还有一个MOVESTATE类型的tag,该tag与gstate和orphan目录有关,见后面目录删除和移动操作中异常情况的分析。
2、链接方式变化
例如,删除目录B,其链接方式变化如下:
用fetch遍历目录顺序的变化如下:
前:parent->C->B->A后:parent->C->A3、相关函数分析
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机制通过如下方法记录和检查异常状态:
当进行如目录删除这样可能因掉电导致异常状态的操作时,会将内存中维护的gstate在commit前标记为异常状态。因为这样可以使得commit过程中将异常状态作为MOVESTATE tag写入磁盘。(lfs_dir_commit函数会检查内存中的gstate变量,并根据gstate增加写入MOVESTATE tag)当读取磁盘元数据时,根据MOVESTATE tag中的信息,可以知道有无异常情况发生、异常情况是否解决等信息。这样检查到异常状态后,就可以根据具体情况执行修复操作。gstate检查时是通过异或操作计算所有MOVESTATE tag中的值,结果不为0则表示异常。(2)orphan状态的记录和修复
当进行目录删除操作时,磁盘中orphan状态的记录和修复步骤如下:
第一次commit,从父目录中将目录删除。此时记录MOVESTATE tag于父目录的元数据中。链接方式变化如下图:第二次commit,这次即可能发生在第一次commit后,也可能是掉电后通过检查gstate发现异常后的修复操作。此时记录MOVESTATE tag于被删除目录的前继目录的元数据中。该MOVESTATE tag数据与在父目录元数据中记录的值相对应,这样gstate检查时进行异或计算就可与前面记录的MOVESTATE tag进行抵消,表示异常已解决。链接方式变化如下图:当进行目录删除操作时,内存gstate中orphan状态的记录和恢复步骤如下:
第一次commit前,标记gstate为orphan状态。这样第一次commit时就可以记录MOVESTATE tag。第一次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中将目录或文件从旧的父目录移动到新的父目录下主要经过两个步骤:
在新父目录中commit,创建目录并指向将要移动的目录。其中,如果新父目录下已经存在一个同名的文件或目录,需要先将其删除。值得注意的是,与创建目录时不同,这里父目录下并没有commit一个SOFTTAIL类型的tag。如下图:在旧父目录中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状态的记录和修复步骤如下:
第一次commit,在新父目录下创建目录,此时记录MOVESTATE tag于新父目录的元数据中。存储结构变化如下图:2. 第二次commit,从旧父目录中删除目录,此时记录MOVESTATE tag于旧目录的元数据中。类似的,这次即可能发生在第一次commit后,也可能是掉电后通过检查gstate发现异常后的修复操作。链接方式变化如下图:
当进行目录删除操作时,内存gstate中move状态的记录和恢复步骤如下:
第一次commit前,标记gstate为move状态。这样第一次commit时就可以记录MOVESTATE tag。第一次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。
责任编辑:jianghua 来源:51CTO开源基础软件社区 littlefs目录操作推荐系统
电脑公司Ghost Win8.1 x32 精选纯净版2022年7月(免激活) ISO镜像高速下载
语言:中文版系统大小:2.98GB系统类型:Win8电脑公司Ghost Win8.1x32位纯净版V2022年7月版本集成了自2022流行的各种硬件驱动,首次进入系统即全部硬件已安装完毕。电脑公司Ghost Win8.1x32位纯净版具有更安全、更稳定、更人性化等特点。集成最常用的装机软件,精心挑选的系统维护工具,加上绿茶独有
微软Win11原版22H2下载_Win11GHOST 免 激活密钥 22H2正式版64位免费下载
语言:中文版系统大小:5.13GB系统类型:Win11微软Win11原版22H2下载_Win11GHOST 免 激活密钥 22H2正式版64位免费下载系统在家用办公上跑分表现都是非常优秀,完美的兼容各种硬件和软件,运行环境安全可靠稳定。Win11 64位 Office办公版(免费)优化 1、保留 Edge浏览器。 2、隐藏“操作中心”托盘图标。 3、保留常用组件(微软商店,计算器,图片查看器等)。 5、关闭天气资讯。
Win11 21H2 官方正式版下载_Win11 21H2最新系统免激活下载
语言:中文版系统大小:4.75GB系统类型:Win11Ghost Win11 21H2是微软在系统方面技术积累雄厚深耕多年,Ghost Win11 21H2系统在家用办公上跑分表现都是非常优秀,完美的兼容各种硬件和软件,运行环境安全可靠稳定。Ghost Win11 21H2是微软最新发布的KB5019961补丁升级而来的最新版的21H2系统,以Windows 11 21H2 22000 1219 专业版为基础进行优化,保持原汁原味,系统流畅稳定,保留常用组件
windows11中文版镜像 微软win11正式版简体中文GHOST ISO镜像64位系统下载
语言:中文版系统大小:5.31GB系统类型:Win11windows11中文版镜像 微软win11正式版简体中文GHOST ISO镜像64位系统下载,微软win11发布快大半年了,其中做了很多次补丁和修复一些BUG,比之前的版本有一些功能上的调整,目前已经升级到最新版本的镜像系统,并且优化了自动激活,永久使用。windows11中文版镜像国内镜像下载地址微软windows11正式版镜像 介绍:1、对函数算法进行了一定程度的简化和优化
微软windows11正式版GHOST ISO镜像 win11下载 国内最新版渠道下载
语言:中文版系统大小:5.31GB系统类型:Win11微软windows11正式版GHOST ISO镜像 win11下载 国内最新版渠道下载,微软2022年正式推出了win11系统,很多人迫不及待的要体验,本站提供了最新版的微软Windows11正式版系统下载,微软windows11正式版镜像 是一款功能超级强大的装机系统,是微软方面全新推出的装机系统,这款系统可以通过pe直接的完成安装,对此系统感兴趣,想要使用的用户们就快来下载
微软windows11系统下载 微软原版 Ghost win11 X64 正式版ISO镜像文件
语言:中文版系统大小:0MB系统类型:Win11微软Ghost win11 正式版镜像文件是一款由微软方面推出的优秀全新装机系统,这款系统的新功能非常多,用户们能够在这里体验到最富有人性化的设计等,且全新的柔软界面,看起来非常的舒服~微软Ghost win11 正式版镜像文件介绍:1、与各种硬件设备兼容。 更好地完成用户安装并有效地使用。2、稳定使用蓝屏,系统不再兼容,更能享受无缝的系统服务。3、为
雨林木风Windows11专业版 Ghost Win11官方正式版 (22H2) 系统下载
语言:中文版系统大小:4.75GB系统类型:雨林木风Windows11专业版 Ghost Win11官方正式版 (22H2) 系统下载在系统方面技术积累雄厚深耕多年,打造了国内重装系统行业的雨林木风品牌,其系统口碑得到许多人认可,积累了广大的用户群体,雨林木风是一款稳定流畅的系统,一直以来都以用户为中心,是由雨林木风团队推出的Windows11国内镜像版,基于国内用户的习惯,做了系统性能的优化,采用了新的系统
雨林木风win7旗舰版系统下载 win7 32位旗舰版 GHOST 免激活镜像ISO
语言:中文版系统大小:5.91GB系统类型:Win7雨林木风win7旗舰版系统下载 win7 32位旗舰版 GHOST 免激活镜像ISO在系统方面技术积累雄厚深耕多年,加固了系统安全策略,雨林木风win7旗舰版系统在家用办公上跑分表现都是非常优秀,完美的兼容各种硬件和软件,运行环境安全可靠稳定。win7 32位旗舰装机版 v2019 05能够帮助用户们进行系统的一键安装、快速装机等,系统中的内容全面,能够为广大用户
相关文章
- WinXP电脑很卡很慢怎样处理?
- 三星w23折叠手机图片-三星w23折叠手机图片展示
- 显卡类型哪种好?电脑显卡分哪几类?
- win7电脑自动调光
- Windows 10更新遇到出错代码0x80240034的处理办法
- win8点击开始图标没反应的处理操作步骤
- QQ图文详细教程之QQ勋章墙取消关闭办法_腾讯QQ
- miui12视频工具箱使用办法
- Win8更改注册表权限的办法
- Win7如何有效的屏蔽广告弹窗?
- 移动硬盘灯亮但电脑没反应怎么解决?
- 狂野之心跨平台联机能玩吗?
- WIN8开启触摸板的简单步骤
- 如何开启Win8.1计划任务 Win8.1开启计划任务的方法【详解】
- win7缺失dll文件一键修复教程【详解】
- Win8结束程序的快捷键方法
- 《火山的女儿》:走段养育女儿的当爹人生、美好与爱极致养成之旅
- Win7 64位系统中音量小喇叭无法调节音量怎样办
热门系统
- 1华硕笔记本&台式机专用系统 GhostWin7 32位正式旗舰版2018年8月(32位)ISO镜像下载
- 2深度技术 Windows 10 x86 企业版 电脑城装机版2018年10月(32位) ISO镜像免费下载
- 3雨林木风 Ghost Win7 SP1 装机版 2020年4月(32位) 提供下载
- 4电脑公司 装机专用系统Windows10 x86喜迎国庆 企业版2020年10月(32位) ISO镜像快速下载
- 5深度技术 Windows 10 x86 企业版 六一节 电脑城装机版 版本1903 2022年6月(32位) ISO镜像免费下载
- 6深度技术 Windows 10 x64 企业版 电脑城装机版2021年1月(64位) 高速下载
- 7新萝卜家园电脑城专用系统 Windows10 x64 企业版2019年10月(64位) ISO镜像免费下载
- 8新萝卜家园 GhostWin7 SP1 最新电脑城极速装机版2018年8月(32位)ISO镜像下载
- 9电脑公司Ghost Win8.1 x32 精选纯净版2022年5月(免激活) ISO镜像高速下载
- 10新萝卜家园Ghost Win8.1 X32 最新纯净版2018年05(自动激活) ISO镜像免费下载
热门文章
常用系统
- 1深度技术 GHOST XP SP3 快速装机专业版 V8.0 下载
- 2电脑公司Ghost Win8.1 x32 精选纯净版2018年4月(免激活) ISO镜像快速下载
- 3番茄花园 GHOST WIN7 SP1 X64 快速稳定版 V2017.03 (64位) 下载
- 4电脑公司 GHOST WIN7 SP1 X64 装机特别版 V2015.01(64位) 下载
- 5老机专用超流畅win7下载_老机专用超流畅win7 64位旗舰版免费下载
- 6雨林木风 GHOST WIN7 SP1 X64 装机旗舰版 V2015.09(64位) 下载
- 7萝卜家园 GHOST XP SP3 电脑专用版 V2017.06 下载
- 8笔记本&台式机专用系统 Windows10 企业版 2018年5月(64位) ISO镜像快速下载
- 9萝卜家园WIN10纯净版32位系统下载_新萝卜家园GHOST WIN10系统镜像下载V2021.02
- 10雨林木风Ghost Win10 完美版64位 v2023.03免费最新下载