Skip to content

Latest commit

 

History

History
332 lines (217 loc) · 20.5 KB

文件系统-虚拟文件系统.md

File metadata and controls

332 lines (217 loc) · 20.5 KB

虚拟文件系统

列夫托尔斯泰说过：用户对文件系统的操作都是相似的，而文件系统的实现却各有各的不同。为了统一管理这些文件系统，linux使用虚拟文件系统来统一管理全部的文件系统。

linux虚拟文件系统结构

虚拟文件系统只存在于内存中，在操作系统初始化时加载并在关机时消亡。

以下部分参考自：https://zhuanlan.zhihu.com/p/354100369

超级块

大多数磁盘文件系统都有超级块，而虚拟文件系统的超级块便是每个磁盘文件系统的抽象。

一个超级块只对应一个磁盘文件系统，超级块包含一个根dentry作为根目录。

超级块提供的方法有：

  • 分配/释放/同步inode
  • 同步磁盘
  • 获取文件系统状态

inode节点

inode是文件系统中的元信息，管理一个打开的文件或目录。

一个文件只有一个inode，inode拥有打开的文件的所有权。

inode提供的方法有：

  • 获取自身的dentry
  • 获取符号链接路径
  • create link unlink symlink
  • mkdir rmdir mknod rename
  • xxxattr
  • update_time

dentry目录项

dentry保存了一个文件在目录树中的位置，并拥有一个inode的所有权。

每个打开的VFile都持有dentry的所有权，因此所有权路径为：

VFile -- dentry -- inode

dentry提供的方法有：

  • 判断此dentry是否有效
  • 生成哈希值
  • 比较文件名
  • 释放dentry
  • 获取自身名字

file文件

操作系统通用文件

提供的方法有：

  • llseek read write

缓存链表维护

总所周知，C++有Map，rust有BTreeMap，这些O(logn)容器看起来比愚蠢的O(N)链表快无数倍，但无论如何都不可能进行常数级时间复杂度的删除操作，但Linux利用链表可以做到这一点。

为什么链表这么快？链表不是需要遍历吗？这就是侵入式链表的特性了。侵入式链表节点嵌在数据结构内部，因此数据结构可以直接拿到自身的节点信息，因此数据结构对自身的删除操作仅仅是用prev和next两个指针修改前后的两个节点，时间复杂度为O(1)。

除此之外还需要支持查找操作。Linux使用了哈希表进行查找，每个哈希表节点都是一条链表。同上，从哈希表中的插入和删除的时间复杂度都是O(1)的。但这也意味着哈希表无法动态扩容，当文件数量较大时哈希桶的数量限制会显著降低查找速度。

文件系统挂载

深入理解Linux文件系统之文件系统挂载(上) https://zhuanlan.zhihu.com/p/378011720

深入理解Linux文件系统之文件系统挂载(下) https://zhuanlan.zhihu.com/p/378013367

一篇搞懂Linux内核源码分析--虚拟文件系统(VFS) https://zhuanlan.zhihu.com/p/472966478

这一篇包含了linux上实现的数据结构

vfs dentry cache 模块实现分析 https://zhuanlan.zhihu.com/p/457005511

Linux的VFS实现 - 番外[一] - dcache https://zhuanlan.zhihu.com/p/261669249

linux文件系统

/bin：里边包含了一般程序工具，用户、管理员、系统都可以调用。
/boot：系统启动文件和内核，在有些发行版中还包括grub，grub是一种通用的启动引导程序。
/dev：系统设备文件目录，除cpu外的所有的硬件设备都会抽象成特殊的文件放在这里，虚拟设备也放在这里。
/etc：包含了大部分重要的系统配置文件，这里文件的作用类似windows中的控制面板。
/home：一般用户目录，一般一个用户对应一个目录，保存用户的数据。
/lib、/lib64：库文件，包含了所有系统和用户需要的程序文件，64表示64位，但实际上除特殊的库，大部分还是链接到了lib目录下。
/media：磁盘设备自动挂载的位置。按照用户分类，每一个用户目录下有其磁盘目录。
/mnt：标准挂载点，可以挂载外设磁盘。
/opt：一般存放第三方软件。
/proc：包含系统资源信息的虚拟文件系统，提供了一个接触内核数据的接口，大部分是只读的，有些允许改变。系统运行时才有文件。
/root：root用户的home目录。
/sbin：系统和系统管理员用到的程序工具。
/sys：与proc类似的虚拟文件系统，都是内核提供给用户的接口，可读可写。
/tmp：系统使用的临时空间，重启后会清空。
/usr：用于存放系统应用程序。
/var：包含一些用户可变的或临时的文件，比如log文件、邮件队列、网络下载的临时文件等等。

虚拟文件系统实现-设计

设计参考了https://blog.csdn.net/21cnbao/article/details/118383912。

Linux的大多数文件操作是通过File完成的，因此文件系统只需要负责对File的管理。虚拟文件系统只需要负责两种功能：打开文件和删除文件，其中打开文件兼具创建文件的职能。为了提高速度，虚拟文件系统还需要快速地获取根目录。

文件目录相关

Linux中一个文件可能有多个硬链接节点，那么一个文件可能属于多个目录。操作系统需要获取文件父目录，那么应该返回哪一个目录？

Linux禁止硬链接目录，因此目录文件可以保存父目录的名字。

Linux虽然文件可能属于多个硬链接节点，但为什么非要获取文件的目录呢？完全可以去获取硬链接的父目录，因为不存在硬链接的硬链接。为了保证这一点，普通文件由硬链接和数据两部分组成，每个硬链接只能属于一个目录。

当rename目录时，如何快速地更新子文件指向的目录？如果目录下面有一万个文件怎么办？

为了保证rename目录的O(1)时间复杂度，rename目录时目录自身节点不能改变。因此rename的修改分为三部分，第一部分是将当前节点插入新的位置，第二部分是修改当前inode的名字，第三部分是删除原来的inode。

修改inode的名字如何保证其他访问者对数据访问的安全性？

文件名字使用Arc维护，新的名字将直接替换旧的名字，旧名字使用RCU释放。名字用seq_lock(序列锁)保护，读者获取锁不需要原子操作，当检测到写者时会等待并重试。

dentry的缓存与回收

dentry事实上持有了inode的所有权，因此对dentry的缓存等价于对inode的缓存，因此虚拟文件系统只需要处理dentry的缓存逻辑。

Linux的dentry基于内置的引用计数，但引用计数的更新实在太过繁杂，我们希望FTL OS的虚拟文件系统可以利用rust中方便的智能指针来管理生命周期。但直接使用智能指针来管理显然是不行的，因为我们要缓存目录项，即便目录项不再被外部持有。为了保证这一点，FTL OS的dentry被划分为了两个结构：Dentry和DentryCache。dentry的外部引用将持有Dentry，Dentry持有DentryCache的所有权，而只有不存在对应Dentry项的DentryCache是可以被回收的，这样就保证了被外部引用的文件不会被回收。

对于一个目录，用户显然不会持有一整个目录链的全部文件，但操作系统也应该保证这一条目录都缓存在内存中。为了做到这一点，所有的DentryCache都持有父目录的Dentry，这样保证了对任何存在于缓存的文件，操作系统中都保存了这个文件到根目录的一整条目录链。在这个方案下，只有整个缓存目录树的叶节点是可被回收的，这也是符合逻辑的树回收方案。

虚拟文件系统不应该缓存整个磁盘目录，这意味着目录项很可能并没有持有所有的子节点。FTL OS使用了如下类似Linux的方案：目录项持有所有打开的目录项的链表，搜索文件时会优先遍历此链表。如果链表中没有发现则前往哈希表中，利用“当前dentry指针”和“名字哈希值”作为索引搜索。如果还是找不到则进入搜索磁盘。dentry可能是Negative项，这表明文件不存在。

进入磁盘搜索需要获取睡眠锁。为了不出现同一个目录项被插入两次的情况，成功获取睡眠锁后还需要再检查一次目录项是否存在待搜索目录。

获取Dentry

DentryCache上包含指向Dentry的弱指针。如果弱指针有效那么直接获取即可，但如果无效则表明DentryCache处于LRU队列中，这时需要将DentryCache从LRU队列中删除，并生成一个Dentry对象并更新弱指针。

释放Dentry

持有Dentry是保证DentryCache不回收的唯一方式。当Dentry析构时会获取DentryCache自身的锁并尝试将它加入虚拟文件系统的LRU缓存队列。

获取释放的并发安全

Dentry的析构至获取DentryCache锁的过程存在时隙，这会带来潜在的并发安全困难。获取和释放涉及两个对象：DentryCache和LRU队列，这涉及两个对象之间的切换。FTL OS明确了排他所有权，即DentryCache并不是一个Arc维护的对象，而是Box维护的对象。DentryCache只能处于DentryCache和LRU队列之一，来自错误地方的访问都说明DentryCache处于移动状态，需要等待操作完成才能继续访问。使用Box维护不仅明确了所有权，还可以减少大量来自智能指针的原子开销。

所有权的移动包含类似令牌传递的三个阶段：

  • 争抢令牌
  • 中间操作
  • 令牌可见

对DentryCache的操作全部遵守这三个原则。争抢所有权是原子的，当争抢成功后才会进入中间操作，操作完成后所有权将放置到新的位置，可以被下一个操作获取。如果争抢所有权失败了则释放锁并检查是否有其他的状态发生了变化，并再次争抢。

DentryCache使用延迟释放，保证无锁并发访问的内存安全。首先明确DentryCache内部成员：

  • Dentry弱指针，必须获取LRU队列锁才能修改。
  • 关闭标志位，一旦关闭不能重启。
  • LRU队列裸指针，创建后不再修改。
  • LRU队列节点，内含一个指向自身的Box指针，必须获取LRU队列锁才能修改。
  • inode的Arc指针，创建后禁止修改。共享所有权的原因是unlink后DentryCache被删除，但inode可能仍然被文件持有。

延迟释放并不能保证100%并发安全。使用了延迟释放后我们必须保证在关闭一个对象后手动移除它的全部引用，保证对象在被释放后不会被访问到。

从DentryCache创建Dentry

操作完成约定：当所有权完整转移到dentry时操作完成。

并发操作失败方式：DentryCache只能获取一次所有权，其他并发操作都会失败。

  • 检测关闭标志位，如果已经关闭了则进入磁盘读取流程。
  • 尝试从弱指针以RCU方式读取并获取对象，如果成功了直接返回。
  • 获取失败，此时DentryCache很可能处于LRU队列中，获取LRU队列的锁。为了防止死锁，FTL OS逻辑上禁止在获取LRU队列锁之前持有Dentry的锁。
  • 检测关闭标志位，如果已经关闭了则释放LRU队列锁并进入磁盘读取流程。
  • 尝试从弱指针以RCU方式读取并获取对象，如果成功了直接返回。
  • 检测LRU队列是否拥有指向自身的Box指针。如果没有则释放锁，等待关闭标志位，节点所有权，Weak指针其中之一发生变化。
    • 如果关闭标志位有效了，直接返回未找到。
    • 如果Weak指针有效了，直接返回获取的Dentry。
    • 如果节点没有所有权（None），那么再次获取LRU队列锁重复上述流程。
  • 此时DentryCache一定被LRU队列持有，生成一个对应的Dentry对象，将所有权从LRU队列转移到Dentry中。
  • 释放LRU队列锁。
  • 获取父目录锁，将Dentry加入子目录集合中。
  • 结束。
Dentry析构时将DentryCache还给LRU队列

操作完成约定：当所有权完整转移到LRU队列时操作完成。只有所有权转移了才能创建新的Dentry。

并发操作失败方式：Dentry只能析构一次。

  • 获取父目录Dentry的子对象锁，删除自身节点，释放锁。
  • 获取LRU队列锁。
  • 将LRU队列节点插入LRU队列。
  • 将文件系统节点插入文件系统的队列。
  • 将Box从Dentry移动到LRU队列节点，这会被其他线程探测到，标志操作完成。
  • 结束
磁盘读取路径

当父目录找不到某个名字对应的DentryCache时将进入磁盘读取路径，此时会进入具体的文件系统利用名字查找。

  • 获取父目录睡眠锁
  • 检测父目录版本号是否改变，此版本号在首次查找时记录。
    • 如果版本号改变了则释放睡眠锁，在索引器中查找子对象，找不到则重来。
  • 检测磁盘查找失败，如果失败了直接返回。如果成功会获取到FsInode。
  • 从FsInode生成DentryCache以及对应的Dentry。
  • 将DentryCache加入索引器。
  • 获取自身的子对象锁，将生成的Dentry插入。
  • 版本号以Release内存序递增1。
  • 释放睡眠锁。
  • 返回Dentry，结束。

文件的删除

Dentry持有inode的所有权，但此所有权不是唯一所有权。因为Linux允许匿名inode的存在。文件打开后立刻unlink，此时文件仍然是可以读取的，但它已经不再处于目录树中了，自然也不存在对应的Dentry对象。

这也导致了FTL OS需要分开管理目录项的删除和数据的删除。对于FAT32文件系统，文件是不存在链接数的，它对应的目录项就持有了全部所有权。如果要允许目录项的提前删除需要一些更复杂的逻辑，例如缓存目录项。但文件的删除并不是瞬间的，这需要在异步上下文运行，于是非异步的析构函数就不够用了。

可以采用延迟析构的方式解决此问题。当inode析构函数运行后，如果它处于unlink状态则在内核中生成一个删除线程。当然异步线程也可以注册到代理线程中来阻塞它的运行并降低内核开销。

虚拟文件系统删除目录项的过程是：

  • 获取待删除文件的Dentry并移出所有权。Dentry保证了所有权不会出现在LRU队列中。
  • 将DentryCache标记为删除。
  • 从索引器中删除DentryCache。
  • 从父目录的子目录项中删除Dentry。
  • RCU释放DentryCache。

挂载

单个目录被挂载多个文件系统

事实上并没有发生单个目录被挂载了多个文件系统。每个挂载点都有对应的目录，对于目录A，将文件系统X挂载到A，再将文件系统Y挂载到A，事实上文件系统并没有挂载到A，而是挂载到了文件系统X的目录项A'上。

多个目录挂载了单个文件系统

当一个文件系统被挂载到多个目录时这多个目录会共享文件系统的所有权，只有最后一个目录释放才会释放文件系统。为了达到这一点，inode需要具有查找自己是否被挂载的能力。考虑在inode上放置挂载点的侵入式链表节点，这些节点保证使用同一个文件系统。如果inode上发现了挂载点则任选一个节点获取文件系统并直接获取智能指针。

取消挂载umount

只有最后一个挂载点释放后才会清空缓存，这会删除全部不包含外部引用的DentryCache。为了实现这一点，当Dentry被删除时，不仅需要加入全局LRU队列，还需要加入文件系统自身的LRU队列。umount会不断尝试删除全部的DentryCache，如果这个文件系统没有被外部使用，那么最终只会剩下根目录和它的inode。此时释放这个inode并标记根目录为关闭，一旦根目录关闭了这个文件系统就处于关闭状态了，拒绝外界的一切操作，释放根目录后取消挂载就结束了。

如果这个挂载点下有其他挂载点将禁止取消挂载操作。

虚拟文件系统实现-架构

FTL OS对Linux的虚拟文件系统有所简化。没有实现negative目录项。没有实现rename、copy操作。

Linux的文件系统区分大小写，因此名字的哈希值为直接计算。如果需要区分大小写需要增加另一个不区分大小写的哈希表，目前尚未实现。

虚拟文件系统广泛使用RCU机制来处理内部各个组件的更新。RCU会延迟析构函数的运行，如果某个组件被检测到处于未关闭状态，那么直到await的执行组件上每个成员都保证不被析构。因此如果只是短时间地查询组件只需要检测关闭标志位即可。如果需要长时间地查看组件则需要持有共享所有权。

挂载点

  • 释放限制：由文件系统释放释放最后一个，RCU释放。
  • 获取方式：从挂载目录的指针获取挂载点。
  • 所有权：属于全局虚拟文件系统，常驻内存。当挂载点存在时对应目录项常驻内存。
  • 关闭标志位。用于配合RCU释放。释放时设置。
  • 父挂载点指针与链表节点。用于父目录取消挂载时检测到EBUSY。永不修改。这是为了保证挂载的目录不被释放。
  • 文件系统指针。
  • 全局挂载点链表节点。用于全局管理器持有所有权。修改需要持有挂载管理器的锁。
  • 挂载点所在的Dentry的智能指针。防止挂载点的目录项被淘汰或删除。当挂载点删除时会将目录里的指针复位。永不修改。

Dentry

dentry持有DentryCache的所有权，保证它不会被释放。

  • 释放限制：由Arc的引用计数释放，只能通过所有权指针读取。
  • 释放操作：将DentryCache的所有权转移到全局LRU队列。
  • 获取方式：从DentryCache生成。
  • 所有权：由外界文件与子目录DentryCache持有。
  • DentryCache所有权Box指针。释放时复位。

DentryCache

DentryCache让没有被外界引用的inode缓存在内存中。

  • 释放限制：只能被全局LRU队列或文件系统释放。
  • 释放约束：只能使用RCU释放。
  • 获取方式：父目录的子目录链表，全局哈希索引。索引ID为：{父目录指针，自身名字}。文件系统根目录不会加入哈希表。
  • 所有权：只能处于Dentry或LRU队列之一。
  • 关闭标志位。配合RCU操作，一旦关闭不能重启。
  • Dentry弱指针。用于目录树搜索。生成dentry时设置。被自旋锁保护。
  • 哈希索引链表节点。当缓存被关闭时需要移除它。修改时需要持有索引器的锁。
  • LRU队列裸指针和链表节点。节点中是LRU队列管理的所有权指针。修改时需要持有LRU队列锁。
  • 文件系统链表节点 。只有LRU队列拥有所有权时才会加入文件系统链表。修改时需要持有文件系统链表锁。
  • 挂载点指针。如果这个目录项不是是挂载点则为None。
  • inode的Arc指针。它的大多数操作都是异步的并被睡眠锁保护，提供序列号访问功能，保证序列号在锁内修改。
  • inode访问序列号。如果检测到序列号改变需要重新访问，按Acquire-Release序获取与修改。
  • 目录项名字与哈希值。使用序列锁保护，因为rename可能修改文件名。
  • 子目录链表与节点。
  • 全局根目录标志：用于到达dev、tmp、lib等系统目录。

inode

inode将对应一个磁盘上的inode节点。

虚拟文件系统保证具体文件系统的每个inode不会被创建两次，文件系统不需要去重。

inode可能并没有对应的目录项。发生这种情况的唯一可能是提前unlink，因此inode不需要索引。

  • 释放约束：Arc引用计数释放。
  • 获取方式：DentryCache与外界文件的指针。
  • 所有权：由DentryCache和外界文件持有。
  • 文件系统指针和链表节点。当析构时从文件系统中删除节点。
  • inode实现。

文件系统

  • 所有权：由所有挂载点共享所有权。
  • 获取方式：从挂载点获取。
  • DentryCache节点链表。用于umount时释放缓存。
  • inode节点链表。用于umount时判断是否全部文件都被关闭。
  • 根目录所有权指针。
  • 文件系统实现所有权Box指针。

全局管理器

全局管理器操控整个虚拟文件系统的运行，运行多个线程并行访问。

  • 挂载点所有权链表。
  • 目录项管理器，内部包含：
    • DentryCache索引器。只包含未使用的缓存。实现为哈希表-BTreeMap-哈希链表。索引为{根目录指针，名字}。
    • LRU队列。没有被外界使用的DentryCache将被LRU队列管理。
  • 根目录。根目录在操作系统初始化时将挂载磁盘。
  • 特殊系统目录。dev等系统目录不会在磁盘上保留副本，当到达根目录时需要检查。