阅读《现代操作系统原理与实现》一书的笔记，也算是对xv6中文件系统一章的补充。
介绍
每个文件实质上是一个有名字的字符序列，序列的内容为文件数据，而序列长度、序列的修改时间等描述文件数据的属性、支撑文件功能的其他信息称为文件元数据。应用程序使用一组特定的接口对文件进行访问，如open、lseek、read、write和close等。
下面我们以 Linux上一个简化的网络文件下载流程为例，介绍存储栈中的各部分如何协作完成应用程序的文件请求。当下载工具从网络中获取到文件内容之后，文件内容被暂存在下载工具的内存中。为了将这些数据持久保存下来，下载工具向操作系统发起一系列系统调用（如 open 和 write等）。在处理系统调用时Linux内核会调用其虚拟文件系统（Virtual File System，VFS）处理文件请求。VFS如同个大管家，负责管理具体的文件系统，并提供一系列服务，如页缓存（page cache）、inode 缓存（icache）和目录项缓存（dcache）等。VFS在解析用户的请求后，调用具体的文件系统的接口进一步处理请求。Ext4等具体的文件系统会根据请求对数据进行读取或修改。当需要访问存储设备上的数据时，文件系统会创建对存储块的访问请求，并发送给 I/O 调度器。由于可能同时存在多个对存储设备的访问请求，I/O 调度器根据预定策略对这些请求进行调度，以一定的顺序将请求发送给设备驱动。最终，设备驱动与存储设备进行交互并完成请求。在存储设备完成写人请求后，下载的文件便被持久保存到了存储设备之中。
这里相较于xv6，出现了一个新的概念，即虚拟文件系统VFS，用于管理不同的文件系统。
基于inode的文件系统
inode与文件
inode（index node）就是用来记录磁盘块的一种结构，记录了一个文件所对应的所有存储块号。每个inode对应一个文件，通过一个inode，就可以访问这个文件所有的数据。
下图展现了inode的结构，区别于xv6中inode的结构（主要是对数据块的索引，但也是分为直接索引和间接索引）。为了能支持更大的文件的同时节约空间，inode采用类似虚拟内存中的页表，采用分级的方式来组织存储块号。采用三级存储指针：
- 直接指针：直接指向保存了文件数据的数据块
- 间接指针，指向一个一级索引块，一级索引块存放着指向数据块的指针
- 二级间接指针：指向一个二级索引块，二级索引块中的每个指针指向一个一级索引块
从上述组织方式中可以看出，一个文件系统所支持的最大文件大小受文件数据组织方式的限制。因此，我们可以通过调整节点的设计来改变其所能管理的最大文件大小。例如，为了管理更大的文件，inode中的索引可以使用更多的二级间接指针，甚至启用三级或者四级间接指针。
POSIX中定义的部分文件元数据（inode），可以看到比起xv6中定义的元数据更丰富。
Linux中支持的文件类型，相比xv6，也更多。
文件名与目录
为了对用户更加友好，文件系统加人了字符串形式的文件名，从而增加了一层从文件名字符串到inode号之间的映射。字符串形式的文件名不但更方便记忆，也使文件名与文件具体的存储位置解耦。但是前面对inode的介绍可以知道，文件名并不是文件的元数据，文件名存储在目录结构中。
下图是一个目录项内的结构。
请忽略图中被误扫进去的蚊子
目录的大小并不取决于目录中的文件大小，而是取决于文件的数量以及文件名的长度
对目录的操作主要包括查找、遍历、增加和删除目录项：
- 查找：在目录中查找某个文件时，文件系统从目录文件中存放的第一个目录项开始，依次比较目录项中存放的文件名。当目录项中的文件名与要查找的文件名相同时，文件系统根据该目录项保存的inode号找到文件的节点，从而在inode上进行各种操作。
- 遍历：目录的遍历操作与查找操作类似，文件系统依次检查目录文件中保存的所有有效（即还未被删除的）目录项，并通过回调函数等方式返回结果。
- 增加：当一个新的文件被创建时，文件系统会在其父目录中增加一个新的目录项记录所创建文件的文件名和模式号。为了节省存储空间，如果目录文件中有无效（即已被删除）目录项，且该目录项空间足够，则文件系统可以重用此目录项的位置存放新的目录项。如果没有合适的无效目录项，则新的目录项会以追加的方式记录在目录文件末尾。
- 删除：当一个文件被删除时，文件系统会从其父目录中删除对应的目录项。删除操作通过将目标目录项中的inode号变为0来标记这个目录项是无效的。这种方法无须为目录有效性信息预留额外的存储空间，可以更加高效地利用空间。同时在进行文件删除时，可以将相邻的无效目录项进行合并，以允许更长的新目录项重新利用这些空间。
POSIX中，每个目录中有两个特殊的目录项：”.”和”..”，即此目录和父目录（根目录，这两个目录项都是根目录本身），这两个目录项由文件系统进行管理，与目录文件一同被创建和删除。
硬链接和符号链接
硬链接
Linux中，可通过”ln file link”为file文件创建另外一个名字link，这里的link就是file的硬链接。当用户创建一个新的硬链接时，文件系统并不会创建一个新的inode，而是先找到目标文件的inode，随后在目标路径的父目录中增加一个指向此inode的新目录项。硬链接与目标文件地位等同，对其中任何一个硬链接的读写操作或者元数据修改，都会影响到指向同一inode的其他硬链接。对于删除操作，只有当所有指向这个inode的全部硬链接都被删除时，这个inode及其数据才会被删除。
符号链接
符号链接又称为软链接，是一种特殊的文件类型。在Linux中，可以通过”ln -s file slink”来为文件创建名为slink的软链接。与常规文件保存数据，目录文件保存目录项不同，符号链接文件中保存的是一个字符串，表示一个文件路径。
一般来说，除了创建、删除和更新其元数据之外，符号链接文件本身只支持读取操作。读取操作的实现也很简单：只需要找到符号链接文件的inode，并返回其中保存的路径即可。如果需要修改一个符号链接文件中的内容，一般需要先删除原文件，再使用新的路径创建一个名字相同的符号链接文件。符号链接文件本身的操作和实现并不复杂，但是其对路径解析的过程会产生较大影响。在不考虑符号链接的情况下，从一个路径得到其所代表的文件非常简单与直接：只需在每一层目录中，查找路径里的下一个文件，直到整个路径都被解析完毕，最终得到的文件便是目标文件。然而在支持符号链接的情况下，每解析完路径中的一部分，文件系统都需要判断当前得到的文件是否为符号链接。如果是符号链接，要先跟随符号链接 中的路径找到目标文件，再继续解析原路径的剩金部分。
符号链接和硬链接的比较
- 当应用程序访问一个以目标文件路径为内容的符号链接时，文件系统读取符号链接中保存的路径，并继续进行解析，最终找到目标文件。
- 而当应用程序访问一个指向目标文件的硬链接时，其直接通过硬链接的目录项访问到目标文件的inode。
- 此外，由于符号链接有自己的inode结构，其有自己的权限、时间等元数据，且删除符号链接本身，不会影响其目标文件。
- 硬链接与目标文件共享同一个inode结构，两者是等价的，并没有主次之分。删除其中的任意一个，应用程序依然可以通过未删除的另一个路径对文件数据进行访问。
- 除此之外，符号链接与硬链接对目标文件的要求还有所差别。在一个符号链接中，用户可以随意存放目标路径，即使这个目标路径不存在。只有在跟随符号链接进行路径解析时，符号链接中的路径才会真正被使用。也只有此时，符号链接中的路径不存在等问题才会引发文件系统报错。而对于硬链接，用户无法成功地创建一个指向不存在的文件的硬链接。同时，硬链接还要求目标文件不能为目录。
- 由于对目标文件的要求不同，符号链接不受文件系统边界的限制，即在一个文件系统中，可以创建一个指向其他文件系统的符号链接；而硬链接的目标文件只能与被链接的目标文件处于同一个文件系统中。
存储布局
不同于xv6，实际中文件系统的存储布局也有所异同。
此外不同的文件系统通常会使用不同的魔法数字（保存在超级快中的元数据），通过读取魔法数字，操作系统可以得知存储设备上文件系统的类型和存储布局。
理论上说，只有文件数据区域被用来存放应用程序的数据。因此在一个存储设备上创建新的文件系统后，文件系统显示的可用大小往往比存储设备的总容量小。
虚拟文件系统
在计算机系统中可能同时存在多种文件系统，在操作系统中，虚拟文件系统VFS对多种文件系统进行管理和协调，允许它们在同一个操作系统上共同工作。不同文件系统在存储设备上使用不同的数据结构和方法保存文件。为了让这些文件系统工作在同一个操作系统之上，VFS定义了一系列内存数据结构，并要求底层的不同文件系统提供指定的方法，然后利用这些方法将存储设备上的不同文件系统的元数据统一转换为VFS的内存数据结构。最后VFS通过这些内存数据结构，向上为应用程序提供统一的文件系统服务。
这一部分和xv6中内存的inode部分有一丝相似性
面向文件系统的接口
Linux VFS定义的内存数据结构：
- VFS中的超级块：VFS定义了自己的内存超级块结构，其中保存了文件系统的通用元数据信息，如文件系统的类型、版本、挂载点信息等。每个挂载的文件系统实例均在内存中维护了一个VFS超级块结构。VFS通过这些超级块结构中的通用的元数据信息对多个文件系统实例进行管理。除了这些通用元数据信息之外，VFS的超级块结构中还预留了一个指针。文件系统可以将该指针指向其特有的超级块信息。这种设计既达到了统一数据结构的目的，又保留了不同文件系统的特有信息，增加了VFS下文件系统的灵活性。
- VFS中的inode：Linux在VFS中同样定义了内存inode结构，用于保存基本的文件元数据。若文件系统想要在内存imode结构中记录额外信息，其需要在为VFS的inode结构分配空间时多分配一些空间，之后通过计算偏移量的方式将额外信息保存在VFS的inode结构之外。为了快速定位和使用inode，VFS维护了一个inode缓存(icache)。VFS的inode缓存使用哈希表保存了操作系统中所有的inode结构。当应用程序或者文件系统需要使用某个inode，且此inode保存在icache中时，可以直接从缓存中访问该inode，从而避免了一次耗时的存储设备访问。
- VFS中的文件数据管理：每个的inode会使用基数树（radix tree）表示一个文件的数据。基数树中的每个叶子节点为一个内存页，保存了文件数据的一部分。这个基数树为这个文件的页缓存建立了索引。
- VFS中的目录项：VFS中的目录项是在内存中保存文件名和目标inode号的结构。正如icache一样，VFS在内存中为目录项维护了一个缓存，称为目录项缓存dcache。
文件系统一般会先将存储设备上的数据读入内存后，再进行修改，修改完毕后再以块为粒度写回存储设备。
下图展示了一个应用程序通过系统调用访问文件系统的例子，VFS会根据系统调用的内容和上下文识别出对应的文件系统类型。
文件描述符：文件描述符实际上是一个整数，通常由vfs进行维护，vfs为操作系统中的每个进程维护一个文件描述符表，该表以文件描述符为索引，保存了一组文件描述结构。每个文件描述结构中记录了一个被打开文件的各种信息，如目标inode(即被打开文件的inode)、文件当前的读写位置和文件打开的模式等。
绝对路径和相对路径：在不同的上下文中，一个绝对路径在系统中指代的文件是固定的。相对路径到底指代哪个文件，取决于其工作目录，在对相对路径进行解析时，是从其工作目录开始查找。在没有指定工作目录时，VFS会默认使用每个进程的当前工作目录，VFS为每个进程维护了一个当前工作目录。
对于文件读请求来说，文件系统将从其保存的文件数据中读取相应的数据，并拷贝到用户提供的缓冲区中。而对于写请求来说，用户需先将要写入文件的数据填充到缓冲区中，之后再调用写接口。文件系统会从用户提供的缓冲区中读取数据，并将其保存到相应的文件中。可以发现POSIX的read和write接口中并未指定文件读写的开始位置，是由于VFS为每个打开的文件保存了一个当前位置，即文件描述结构中的文件当前读写位置。为了控制文件读写位置，POSIX中还定义了lseek接口，应用程序可以调用lseek接口来调整文件描述接口中保存的文件读写位置。在频繁地随机访问文件时，每次都通过lseek后再进行读写操作是比较耗时地因此，POSIX中也提供了以“P”开头的读写接口，允许应用程序在进行读写时直接指定开始位置。
对于写入操作来说，若写入的位置超出了文件当前的末尾，则文件的大小会增大。如果写入的数据超过了文件的最后一个数据块，则文件系统会首先从存储设备中分配新的数据块，并将数据块记录在inode的文件缩影结构中，此后文件系统便可以进行正常的数据拷贝操作。
页缓存、直接I/O与内存映射
在前面的讨论中，我们假设对文件系统中结构的修改都是直接在存储设备中进行的。然而在存储设备上直接访问数据有两个问题。首先，目前大多数存储设备都是块接口，读写粒度为一个块，大小通常为512个字节或者4096个字节。然而文件系统所进行的更改往往并非对齐到块的边界，其读写的字节数也并非恰好为块大小的整数倍。其次，存储设备的访问速度慢，与内存相比要慢几个数量级，大量频繁的存储设备访问操作会成为应用程序的性能瓶颈。
读缓存
因此，文件系统使用内存作为中转来解决访问粒度不一致的问题。但其中一个明显的问题是，若每个文件请求中每个结构的修改都经过完整的“读取磁盘到内存—修改内存中的文件—写回到磁盘”过程，将会产生大量的磁盘访问。但我们可以做一些优化：文件的访问具有时间局限性，当文件系统中设备中读取了某个文件的数据之后，可以让这些数据继续保留在内存中一段时间。这样，当应用程序需要再次读取这些数据时，就可以从此前保留在内存中的数据中读取，从而避免了存储设备的访问，这便是文件系统的读缓存。当读缓存占用过多内存时，操作系统会使用LRU等策略回收读缓存占用的内存。
写缓存
当文件系统修改完文件数据后，其修改会被暂存在写缓冲区的内存页中。如果后续的文件请求需要读取或者修改相同存储块中的数据，文件系统可以直接在写缓冲区对应的内存页上进行读取或者修改。当可用内存不足，或者对应的fsync（确保文件的更新操作被永久保存，以防止数据丢失或损坏）被调用时，写缓冲区内存页中的数据才被写回到存储设备对应的存储块之中。这样，一段时间内同一个存储块上的多个写请求可以合并成一个磁盘写操作。
页缓存
Linux系统中，读缓存与写缓存区的功能被合并起来管理，称为页缓存。页缓存以内存页为单位，将存储设别中的存储位置映射到内存中。文件系统通过调用VFS提供的相应接口对页缓存进行操作。当一个文件被读取时，文件系统会先检查其内容是否已经保存在页缓存中。如果文件数据已保存在页缓存中，则文件系统直接从页缓存中读取数据返回给应用程序；否则文件系统会在页缓存中创建新的内存页，并从存储设备中读取相关的数据，然后将其保存在创建的内存页中。之后，文件系统从内存页中读取相应的数据，返回给应用程序。
在进行文件修改时，文件系统同样会首先检查页缓存。如果要修改的数据已经在页缓存中，文件系统可以直接修改页缓存中的数据，并将该页标记为脏页；若不在页缓存中，文件系统同样先创建页缓存并从存储设备中读取数据，然后在页缓存中进行修改并标记该页为脏页（表示其中的数据与磁盘中的数据有所区别）。标记为脏页的缓存会由文件系统定期写回到存储设备中，然后再次变为干净页。当操价系统内存不足或者应用程序调用fsync时，文件系统也会将脏页中的数据写回到存储设备中。
页缓存是持久化和性能之间权衡的产物，文件系统将是否使用页缓存的判断和选择交给了应用程序。若文件系统不要使用页缓存，这种文件访问方式就是直接I/O。而对应的，使用页缓存的文件请求称为缓存I/O。除了文件的read和write接口外，应用程序还可以通过内存映射机制，以访问内存的形式访问文件内容。
多种文件系统的组织和管理
Linux使用简单的链表结构，将其支持的所有文件系统保存起来，包括内嵌的文件系统和运行时作为模块加载的文件系统。一般来说，每个文件系统在设计时都会有其本身的内部结构。这些结构均会有一个固定的入口保存在超级块中。通常这个入口为文件系统的根目录。
下图展示了文件系统的挂载，FS0为根文件系统，作为VFS文件系统树的基础。在根文件系统的基础上，其他文件系统可以被自由的挂载到VFS文件系统树上的任何一个目录之上，比如FS1，FS2，这些都称为挂载点。
并不要求挂载点在挂载时一定是空目录。挂载点原有的内容会临时覆盖，但并不会丢失。当所挂载的文件系统被卸载时，这些原有内容又可以被再次访问到。
伪文件系统
Linux中还有一些不用于保存文件数据的文件系统，称为伪文件系统。
其他文件系统
文件分配表(文件分配表，FAT)是一种组织文件系统的架构。1977年，比尔盖茨和马克麦克唐纳创建了第一个基于FAT的文件系统，用于管理微软系统中的存储设备。自被搭载在Windows操作系统中至今，基于FAT的文件系统从早期的FAT 12、FAT 16逐步发展到现在被广泛使用的FAT 32和exFAT等文件系统。FAT是FAT文件系统的核心。本质上，FAT将一个文件的多个数据簇以链表形式进行索引。相对于inode索引文件数据的方法，FAT的方法更加简单直接。然而FAT所使用的链式结构在查找时并不高效。如果要访问一个文件的中间 部分，FAT文件系统不得不逐个簇进行查找，使得大文件的访存变得尤其缓慢。这也是Ntfs等后续文件系统出现的原因之一。
由于FAT 文件系统设计和实现的简单性，FAT 文件系统依然被广泛用于各种设备和场景中。例如，UEFI中 EFI分区上的文件系统便是基于FAT 文件系统进行设计的，且与 FAT 文件系统兼容。
基于inode的文件系统：UFS，ext2/3/4，XFS，JFS
NTFS ( New Technology File System）是在FAT系统后，另外一个在Windows 操作系统中广泛使用的文件系统。相对于此前的 FAT 文件系统，NTFS在功能
性能、可靠性等方面进行了诸多提升，并解除了原有 FAT 文件系统中的诸多限制。
FUSE和用户态文件系统
