linux 中 ext2文件系统实现

2023-12-28 01:44
文章标签 实现 linux 文件系统 ext2

本文主要是介绍linux 中 ext2文件系统实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

ext2文件系统结构

图片的svg下载链接(图中关于buffer的部分,上下两部分是重复的,是从不同维度下看的buffer结构)

linux内核本身不提供ext2文件系统的格式化功能,可以参考busybox中对mkfs.ext2的实现(mkfs.ext2.c)格式化过程简述如下:

mkfs_ext2_main():计算每个部分的资源填充super_block填充group_desc_blocks,desc中主要包含三部分数据块的块号bg_block_bitmap,bg_inode_bitmap, bg_inode_table在每个group的bitmap块中标记这些元数据块的位置为已分配(其中第一块还会有super_block)将inode_table空间初始化为0添加. .. lost_found 这三个目录项。

在busybox中块大小与总大小有关,总磁盘大小至少是64k,64k-512m是4096B,512m-4T是8192B(4T以上不考虑了)。一个group中装的block数是一块bitmap块所能承载的数(比如一块4096byte时,能代表的块数是4k*8=32k个块)

从代码流程可以看出ext2系统的布局如下:

没有引导块,super block存了整体信息,group desc存了group信息所在块号(最重要的是三种块的块号:block分配bitmap、inode分配的bitmap、inode 实际存储信息的多个块)。这两部分信息有多个备份。真正的inode和文件内容存在data block上。

ext2中inode分配

inode分配的实现在ext2_new_inode,每次尝试从inode数和block数都占用不多的group分配inode(find_group_orlov),然后从这组的bitmap中找一个合适的位置setbit,它对应了inode_table 中一段实际的磁盘空间。从slab中分配一个包含inode节点的struct ext2_inode_info,将找到的inode号填入inode->ino中,这里不需要访问设备。将inode_table对应位置所在块和inode bitmap 所在块标记为dirty(mark_buffer_dirty),之后就在合适时间等着刷盘就好了(这个链路可以参考linux buffer的回写的触发链路)。

注:存在设备上的inode状态中信息大部分来自于inode 结构。但在内存中会对这个inode结构做一个封装(ext2_inode_info),inode结构存在ext2_inode_info->vfs_inode位置。可以通过EXT2_I(struct inode *inode)函数找到inode对应的ext2_inode_info。

目录inode的分配

另外当分配一个路径时,每个dir inode有一个对应的block,上面存了ext2_dirent,它是可变长的结构(因为路径的名称可长可短)。当要删除一个路径时,不需要将后面的dirent向前补齐,而是将dirent与前一个dirent合并。所以在分配时也是同理,需要遍历dirent,将合适的dirent的空闲部分切下来作为新的dirent。

寻找目录分配在哪个group也有讲究(Orlov算法):有两个原则。1、新目录尽可能与父目录在同一个group或相近的group;2、如果未达到一定阈值,可直接分配,如果达到阈值则找离父group最近的,剩余空闲inode数大于平均的group分配。

阈值有三点(每个group的dir数之间不能差太多):

1、目录数的绝对上限:平均每group分配目录数+1/16每组分配上限(每个group的dir数不能太多)

2、空闲inode数和block数下限:group平均值-1/4每组分配上限(每个group的dir数不能太少)

3、debt = 分配目录-分配文件。要求debt * INODE_COST <  N_{group\_blocks}\times \frac{N_{dir}}{N_{block}}(根据平均每目录占用block数,计算的未来需要block数不能过载)

ext2中inode的访问

每个inode 的ext2_inode_info中有一个i_data数组,当一个inode文件中分配块数少于12时,可以直接使用i_data的前12个元素作为逻辑块1-12所对应的物理块号。当一个文件块数超过12小于1024(一个block所能装int类型的数量)时,i_data的第13位(index = 12)指向1级列表所在的块,这块中每一项表示对应逻辑块(12-1023)的物理块号。

依此类推,1K-1M之间的逻辑块用i_data[13]所指向的二级块表来索引,1M-1G之间的逻辑块用i_data[14]所指向的三级块表来索引。

当读取一个block时,首先通过inode的块表找到对应逻辑块的物理块号(ext2_block_to_path)。将物理块加载到内存中,封装成一个buffer_head结构,并返回(ext2_get_block)。

buffer_head是设备与buffer之间的一个扭带,它映射了设备上的一片区域(在代码中一个buffer_head对应几个连续的block)。真正的buffer内容存在struct page对应的页空间上(页与struct page的转换关系可以参考:linux中 struct page 与物理地址的关系)

下图中filio是对page的封装,可以理解为一段连续物理内存页的集合,第一页的folio->page上存了页区间的第一个struct page,其后连续的struct folio填满了folio对应的区间。(下图中画的page指向一段页,实际上不是指针关系,而是上面链接提到的,struct page结构地址本身映射了一块内存),这些实际的物理内存组成了一段buffer。区间第一页的folio->private是buffer_head的链表,其上存了这个buffer与块设备上block内容的对应关系,其中buffer_head->b_data指向一个block大小的buffer。(下图中更正:一个buffer_head不一定对应一个块,可以对应几个连续块(注:从grow_buffers函数的注释和grow_dev_page的实现可以看出,block的大小一定比页小))

当修改文件中一段内容时,它对应的块的buffer_head会链在inode->private_list所在链表上。等待后期刷盘时遍历。如下图所示:

这里想到一个问题,当父进程fork了一个子进程,这个子进程中通过copy on write 的方式修改了一个文件的内容,会发生什么改变呢?答案是什么也不会发生,因为copy on write是在逻辑地址上做的文章(原理可以参考这篇:理解linux中反向映射与应用),这里的buffer都是物理地址。

ext2中inode块的分配

由于底层访问接口中一次只加载一个block,为了让逻辑上连续的块在物理设备上也尽可能连续,每次为inode分配逻辑块时,会启发性地,一次分配多个连续的块(ext2_get_blocks),我们重点分析下这个启发式过程。

其中每个文件可能有自己的reserve window,但并不保证分配的块一定属于这个文件,有可能在分配reserve window之前其间的物理块早被多个其它文件分配过。reserve window的作用只是说先占着,别的文件分配时会跳过这个区域,从而保证一个文件在分配时物理块尽可能在一起。分配window时的算法保证这个reserve winodw的区域至少有一个空闲块(alloc_new_reservation)。

ext2_get_blocks():// 将块号分解为块表的分量ext2_block_to_path();// 将块表链路上的块都找到,收集到chain中// chain节点Indirect的key=下层物理块号,p=下层逻辑块号所在地址ext2_get_branch();// 选定一个目标块用来分配,原则是尽可能与同一文件分配过的块挨着// 如果上次分配的逻辑块号与物理块号刚好可用,则选定这个块号// 否则在这个块中向左找分配过的物理块号,选定接在它(逻辑上分配过的块的物理块号)后面。// 如果这一逻辑块中前面没有分配过的块,则选承载这级块表的物理块的后面一块。// 如果这是新文件,没有分配过块表,则在inode所在group的1/16*x分配// (x在0到15之间,目的是让新文件分配的物理块尽可能隔开,这样可以使同一文件的物理块尽可能挨着)ext2_find_goal();// 启发式计算一次性分配多少连续块(分配长度),// 这里不要求物理块连续,会在后面将分配长度削减到连续物理块数:// 如果块表的最后一级是中间块,则分配长度为传入的maxblocks块。// 如果maxblocks数量跨过了这个中间块,则分配长度为从逻辑块位置到这个中间块表结束的块数。// 如果块表的最后一级是叶子块,则分配长度为选定逻辑块后没有分配过的连续逻辑块块数。ext2_blks_to_allocate();// 分配块表子链// 传入参数indirect_blks指最后一级块表到分配data块还差几层// blks和goal指上面启发式计算的分配长度和启始分配块ext2_alloc_branch():ext2_alloc_blocks():// 尝试分配至少indirect_blks(新块表项)+1个块,// 其中前面的作为data块,后面的作为新块表块while (分配的连续块还不够用)ext2_new_blocks();// 将buffer_head与这个分配的连续data块绑定(不包含块表块)map_bh(bh_result, bno);// 如果分配的块数超过了最后一级块表的边界,只有一种可能// 就是新分配的块表块接在了新分配的data 块后面。// 则在buffer_head上标记一下,后面刷盘时,除了刷data block外,// 连带要检查一下后面的块,因为它可能是这个data block所在的块表块。// 一起刷盘更能保证原子性(write_boundary_block)set_buffer_boundary(bh_result);ext2_new_blocks():先尝试从选定块的group上的reserve window分配如果不能分配,其它group只取free block大于reserve window 的一半的reserve window分配如果用reserve window分配不成功,尝试不用reserve window分配,还是先goal group,再其它group。实现用了同一个入口函数 ext2_try_to_allocate_with_rsvext2_try_to_allocate_with_rsv():在尝试reserve_window的场景,尝试通过扩张reserve window的方式来满足分配大小,在有指定目标物理块的情况下,尝试让window覆盖目标块如果忽略了目标物理块,则尝试从整个group去分配。扩张有几个原则:1、如果window内已经分配过一半以上,尝试扩张一倍大小。2、如果覆盖了目标块,尝试让reserve window覆盖请求的大小3、扩张后的块内必须至少有一个free的block然后调ext2_try_to_allocate从bitmap中去找一个空闲块。当扩张大小不足以覆盖请求大小时,尝试缩短请求连续块数在不尝试reserve_window的场景,直接调ext2_try_to_allocate找空闲块ext2_try_to_allocate():// 找空闲块有一定算法:// 先从start位置到64 align 的位置结束找free bit.// 如果没找到,尝试找空字节(以8bit为单位找)。// 如果还没找到,才尝试从start位置开始,一个bit一个bit地找。find_next_usable_block();// 当找到空闲bit后,由于上面算法有以8bit为单位找的情况// 因而向前找7个bit,看有没有连续的空闲块可用for (i = 0; i < 7 && grp_goal > start && !ext2_test_bit(grp_goal - 1,bitmap_bh->b_data);i++, grp_goal--);// 返回连续块的开始位置和块数*count = num;return grp_goal - num;

向ext2文件写内容

write的调用到真正操作如下:

write->ksys_write->vfs_write->new_sync_write->call_write_iter->ext2_file_write_iter (ext2 的 op hook)->generic_file_write_iter->__generic_file_write_iter->generic_perform_write->file->f_mapping->a_ops

file的f_mapping就是inode->i_mapping,inode->i_mapping是在从slab拿一个ext2_inode_info时callback hook(init_once)中填充的。而file->f_mapping是在alloc_file时填充的(f_mapping = inode->i_mapping)。

写的过程分为write_begin,copy_page_from_iter_atomic,write_end三步。

第一步ext2_write_begin时,会做两件事,一个是准备buffer,为buffer分配页(会将folio->mapping 置为inode的i_mapping,filemap_add_folio),另一个是准备块,为刷盘区间的逻辑块分配物理块 (get_block)。

第二步迭代传入的用户空间的data,copy到buffer中(copy_page_from_iter_atomic)。

第三步ext2_write_end,标记buffer为dirty(__block_commit_write)。

在写完之后,会调一次sync,来刷盘(generic_file_write_iter->generic_write_sync)。从dirty到刷盘链路可以参考linux buffer的回写的触发链路

这篇关于linux 中 ext2文件系统实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/544810

相关文章

Linux线程同步/互斥过程详解

《Linux线程同步/互斥过程详解》文章讲解多线程并发访问导致竞态条件,需通过互斥锁、原子操作和条件变量实现线程安全与同步,分析死锁条件及避免方法,并介绍RAII封装技术提升资源管理效率... 目录01. 资源共享问题1.1 多线程并发访问1.2 临界区与临界资源1.3 锁的引入02. 多线程案例2.1 为

分布式锁在Spring Boot应用中的实现过程

《分布式锁在SpringBoot应用中的实现过程》文章介绍在SpringBoot中通过自定义Lock注解、LockAspect切面和RedisLockUtils工具类实现分布式锁,确保多实例并发操作... 目录Lock注解LockASPect切面RedisLockUtils工具类总结在现代微服务架构中,分布

Java使用Thumbnailator库实现图片处理与压缩功能

《Java使用Thumbnailator库实现图片处理与压缩功能》Thumbnailator是高性能Java图像处理库,支持缩放、旋转、水印添加、裁剪及格式转换,提供易用API和性能优化,适合Web应... 目录1. 图片处理库Thumbnailator介绍2. 基本和指定大小图片缩放功能2.1 图片缩放的

Python使用Tenacity一行代码实现自动重试详解

《Python使用Tenacity一行代码实现自动重试详解》tenacity是一个专为Python设计的通用重试库,它的核心理念就是用简单、清晰的方式,为任何可能失败的操作添加重试能力,下面我们就来看... 目录一切始于一个简单的 API 调用Tenacity 入门:一行代码实现优雅重试精细控制:让重试按我

Redis客户端连接机制的实现方案

《Redis客户端连接机制的实现方案》本文主要介绍了Redis客户端连接机制的实现方案,包括事件驱动模型、非阻塞I/O处理、连接池应用及配置优化,具有一定的参考价值,感兴趣的可以了解一下... 目录1. Redis连接模型概述2. 连接建立过程详解2.1 连php接初始化流程2.2 关键配置参数3. 最大连

Python实现网格交易策略的过程

《Python实现网格交易策略的过程》本文讲解Python网格交易策略,利用ccxt获取加密货币数据及backtrader回测,通过设定网格节点,低买高卖获利,适合震荡行情,下面跟我一起看看我们的第一... 网格交易是一种经典的量化交易策略,其核心思想是在价格上下预设多个“网格”,当价格触发特定网格时执行买

Oracle数据库定时备份脚本方式(Linux)

《Oracle数据库定时备份脚本方式(Linux)》文章介绍Oracle数据库自动备份方案,包含主机备份传输与备机解压导入流程,强调需提前全量删除原库数据避免报错,并需配置无密传输、定时任务及验证脚本... 目录说明主机脚本备机上自动导库脚本整个自动备份oracle数据库的过程(建议全程用root用户)总结

Linux如何查看文件权限的命令

《Linux如何查看文件权限的命令》Linux中使用ls-R命令递归查看指定目录及子目录下所有文件和文件夹的权限信息,以列表形式展示权限位、所有者、组等详细内容... 目录linux China编程查看文件权限命令输出结果示例这里是查看tomcat文件夹总结Linux 查看文件权限命令ls -l 文件或文件夹

idea的终端(Terminal)cmd的命令换成linux的命令详解

《idea的终端(Terminal)cmd的命令换成linux的命令详解》本文介绍IDEA配置Git的步骤:安装Git、修改终端设置并重启IDEA,强调顺序,作为个人经验分享,希望提供参考并支持脚本之... 目录一编程、设置前二、前置条件三、android设置四、设置后总结一、php设置前二、前置条件

python设置环境变量路径实现过程

《python设置环境变量路径实现过程》本文介绍设置Python路径的多种方法:临时设置(Windows用`set`,Linux/macOS用`export`)、永久设置(系统属性或shell配置文件... 目录设置python路径的方法临时设置环境变量(适用于当前会话)永久设置环境变量(Windows系统