littlefs原理分析--存储结构(一)
littlefs原理分析--存储结构(一)
作者:蒋卫峰 李涛 2022-10-27 16:07:24系统 OpenHarmony 本文介绍littlefs的整体结构,包括超级块、文件、目录等在磁盘上的存储,以及文件、目录打开后在内存中的表示,希望能让读者对littlefs有一个大概的印象。想了解更多关于开源的内容,请访问:
51CTO开源基础软件社区
https://ost.51cto.com
前言
littlefs是一个小型的文件系统,其特点有:
(1)具有磨损均衡功能。
(2)具有掉电保护能力。
(3)适用于ROM和RAM有限的场景。
本系列文章将对littlefs的原理进行分析。作为系列的第一篇,首先对littlefs整体的存储结构进行介绍,在后面的文章中,再对具体的目录、文件操作等进行分析。
1、总览
littlefs的存储结构大体上如上图所示。其中超级块是littlefs存储目录和文件的起点,根目录紧随其后。littlefs中的目录均可以指向其他的目录,构成树状结构。在目录中可以包含多个文件,上图中右边的目录中即包含了一个inline文件和一个outline文件。
2、元数据对
在对littlefs的存储结构进行具体介绍之前,先对littlefs中一个核心的数据结构,即元数据,进行介绍。littlefs中使用元数据对存储目录信息、超级块信息、文件信息、inline文件的数据等内容,是其设计的核心数据结构。
元数据对的存储结构如下图:
以下为具体说明:
一个元数据对与物理上的两个块相对应,且均记录了一个revision count。revision count较大的块存储的为较新的内容,每当更新其中的数据时,revision count就会加1。使用两个块的好处是,当一个块放不下更新的内容时,可以将数据压缩并转存到另一个块上(如进行compact操作),避免直接破坏原有的数据。每个超级块、目录均有其对应的一个或多个元数据对,其中记录了超级块或目录相关的信息。如目录对应的元数据对中可能存储该目录下的文件信息等。元数据对以tag为单元进行信息的存储,以commit的方式进行信息的更新,这里是借鉴了logging文件系统的做法。如创建一个目录,就会在对应的元数据对中进行一次commit,记录CREATE、DIR、DIRSTRUCT等tag,最后计算CRC。元数据对每次进行commit时会计算CRC,以实现数据的校验等功能。(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中存储了文件大小和文件跳表头所在的块号:
tagdata[--32--][--32--|--32--][1|- 11 -| 10 | 10 ][--32--|--32--] ^^ ^^^^- file size || ||'-------------------- file head || |'- size (8) || '------ id |'------------ type (0x202) '----------------- valid bit3、超级块
超级块是littlefs存储目录和文件的起点,其元数据对所在的块号起始为0,1。超级块以单个或多个元数据对的方式进行存储,下图为单个元数据对存储超级块的具体情形:
其中包含了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、目录
目录的存储结构如上文总览中所示,以单个或多个元数据对的方式进行存储。以根目录为起点,通过末尾对其他元数据对的块指针,可以构成一个树形结构。
单个目录的元数据对具体存储如下图:
上图中,中间的目录使用了两个元数据对进行存储。第一个元数据对中SOFTTAIL类型的tag中存储了指向父目录中末尾目录的块指针(即在父目录中最后创建的子目录,当父目录中还没有创建子目录时,该块指针为空)。第二个元数据对中存储了创建的子目录的信息(包括CREATE、DIR、DIRSTRUCT等类型的tag),并指向了子目录。
注:上述目录与其父目录、子目录之间的链接方式只是可能的一种情况。随着目录的创建、删除、移动等操作,具体的链接方式会发生变化,具体见后面的文章。
其中相关tag的表示如下:
元数据对的块指针相关:HARDTAIL:表示同一目录的下一个元数据对的块指针。SOFTTAIL:表示不同目录的下一个元数据对的块指针。目录创建信息相关:在父目录中会记录CREATE、DIR、DIRSTRUCT、SOFTTAIL等类型的tag。DIR:存储目录名和id。DIRSTRUCT:存储创建的子目录的元数据对的块指针。SOFTTAIL:记录了创建的子目录的元数据对的块指针。(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就可以初始化为etaguint32_t etag;uint16_t count; // 目录中属性数量(文件、子目录数)// 表示下一个commit是否写入完成// 用于commit和fetch相关函数,见commit机制和tag的遍历// 当fetch时,fetch到末尾还未匹配,会把erased置为true// 在commit函数中,只有erased为true才进行commitbool 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文件。
(1)inline文件
具体tag存储信息如下:
REG:存储文件名和idINLINESTRUCT:存储inline文件的数据(2)outline文件
如上图,littlefs中outline文件的数据是用跳表存储的。其中CTZSTRUCT类型的tag中存储了文件大小和跳表头指针信息,跳表头指针指向了文件末尾的块。跳表中每个块对其他块的指针储存在该块的块头处。
跳表中块指针按固定规律分布:对block,如果可以被整除,那么该block就含有一个指向block的块指针。以block 4为例:
4可以被整除,则block 4含有即block 3的块指针。4可以被整除,则block 4含有即block 2的块指针。4可以被整除,则block 4含有即block 0的块指针。由此规律,又因为块的大小是固定的,那么只要知道文件的偏移位置,就可以获取该偏移位置所在block在跳表中的序号、该块上有几个块指针等信息:
获取跳表中块序号:根据文件偏移和块大小计算,相关函数为lfs_ctz_index。获取块头部块指针数量:用ctz指令,ctz(块序号)。(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_INLINElfs_size_t size; // 文件大小,inline和outline文件均用此记录} ctz;uint32_t flags;// INLINE、OUTLINE、DIRTY、WRITING等标志lfs_off_t pos; // 文件当前的偏移字节数lfs_block_t block; // 文件当前的blocklfs_off_t off; // 文件在当前block的偏移lfs_cache_t cache; // 文件缓存,用于读写等操作const struct lfs_file_config *cfg;// 文件的其他配置信息} lfs_file_t;6、文件和目录在内存中的表示(mlist)
littlefs中,mlist用于记录打开的文件和目录,存在于内存中。
mlist主要用于遍历打开的文件和目录。
(1)相关数据结构
mlist
typedef struct lfs {...struct lfs_mlist {struct lfs_mlist *next;// 下一个链表中的节点uint16_t id; // 文件或目录在其父目录中的iduint8_t type;// 类型,表明是文件还是目录lfs_mdir_t m;// 父目录元数据对信息} *mlist;...} lfs_t;打开的文件
typedef struct lfs_file {struct lfs_file *next; // 下一个链表中的节点uint16_t id; // 文件在父目录中的iduint8_t type;// 类型,文件类型应为LFS_REG_TYPElfs_mdir_t m;// 父目录元数据对信息// 以下成员见上文中存储结构...} lfs_file_t;打开的目录
typedef struct lfs_dir {struct lfs_dir *next;// 下一个链表中的节点uint16_t id; // 目录在父目录中的iduint8_t type;// 类型,目录应为LFS_DIR_TYPElfs_mdir_t m;// 父目录元数据对信息lfs_off_t pos; // 当前目录或文件在父目录中的位置,.和..分别为0和1lfs_block_t head[2]; // 第一个元数据对所在块号} lfs_dir_t;(2)记录打开的文件和目录
由前面的数据结构,littlefs中mlist是一个单链表,其中记录了打开的文件和目录。 mlist既可以插入lfs_file_t,也可以插入lfs_dir_t,lfs_mlist、lfs_file_t和lfs_dir_t的前几个成员的结构体是相同的。
在打开文件过程中
打开文件时,相应lfs_file_t类型的文件数据加入到mlist:
lfs_file_open(lfs_t *lfs, lfs_file_t *file, const char *path, int flags)|-> lfs_file_rawopen(lfs_t *lfs, lfs_file_t *file,|const char *path, int flags)|-> lfs_file_rawopencfg(lfs_t *lfs, lfs_file_t *file,| const char *path, int flags,| const struct lfs_file_config *cfg)|-> ...|| // 将file加入到mlist|-> lfs_mlist_append(lfs, (struct lfs_mlist *)file);||->...在关闭文件过程中
关闭文件时,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);||->...在打开目录过程中
打开命令时,相应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);在关闭目录过程中
关闭目录时,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原理。
想了解更多关于开源的内容,请访问:
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能够帮助用户们进行系统的一键安装、快速装机等,系统中的内容全面,能够为广大用户
相关文章
- 为啥Windows 10系统慢速版还不更新?
- 小白一健重装系统步骤
- 失易得数据恢复破解版使用教程
- Win10屏幕有黑边怎么办?Win10屏幕有黑边的解决方法
- Win8没有无线网络无法连接怎么解决?
- 全焦镜片一般多少钱-全焦镜片价格详情
- Win11系统edge浏览器标签页自动弹出怎么回事【详解】
- 如何看电脑是32还是64
- 电脑死机怎样办,教您处理电脑死机的办法
- 装机高手教你如何运用U盘杀毒专家
- Win8系统开关机没有声音的处理措施
- win10升级有期限吗 win10免费升级期限
- 鼠标右键菜单设置,本文教您鼠标右键菜单设置
- Linux下U盘使用图文详细教程详细说明
- 跟茶叶蛋PK 神舟Win8超极本UI43仅2299
- DosBox是啥?它对电脑有啥用处
- Win8怎样提高网速?提高网速的方法
- win10最稳定的版本是哪个 win10最稳定的版本介绍【详解】
热门系统
- 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 Win10 快速专业版X64 v2023.02最新下载
- 2绿茶系统GHOST Win7 SP1 2011 V5.1 完美激活版 下载
- 3电脑公司 GHOST XP SP3 特别版 v2011.09 下载
- 4雨林木风Ghost Win10 64位 快速专业版 v2023.01最新免费下载
- 5风林火山 Ghost WinXP SP3 极速稳定版下载_风林火山 Ghost WinXP SP3 高效稳定版下载V2023.
- 6雨林木风Ghost Win10 家庭专业版64位 v2023.03免费最新下载
- 7深度技术 Windows 10 x64 企业版 电脑城装机版2020年1月(64位) 高速下载
- 8青苹果系统Ghost win10 64位 专业装机版 v2023.01官网正版下载
- 9新萝卜家园电脑城专用系统 Windows10 x64 极速企业版2018年8月(64位)ISO镜像下载
- 10雷神win11系统专业版下载-雷神win11系统专业版 64位下载