Linux系列：文件系统 | 飙戈的博客

type

status

date

slug

summary

文件系统结构

文件系统是操作系统中负责管理持久数据的子系统，说简单点，就是负责把用户的文件存到磁盘硬件中，因为即使计算机断电了，磁盘里的数据并不会丢失，所以可以持久化的保存文件。

linux支持的文件系统类型有：

磁盘的文件系统，它是直接把数据存储在磁盘中，比如 Ext 2/3/4、XFS 等都是这类文件系统。

内存的文件系统，这类文件系统的数据不是存储在硬盘的，而是占用内存空间，我们经常用到的 /proc 和 /sys 文件系统都属于这一类读写这类文件，实际上是读写内核中相关的数据。

网络的文件系统，用来访问其他计算机主机数据的文件系统，比如 NFS、SMB 等等。

文件结构

文件系统的基本数据单位是文件。Linux 最经典的一句话是:「一切皆文件」，不仅普通的文件和目录，就连块设备、管道、socket 等，也都是统一交给文件系统管理的。

一个文件由目录项、inode和数据块组成

目录项(directory entry)：用来记录文件的名字、索引节点指针以及与其他目录项的层级关联关系。多个目录项关联起来，就会形成目录结构，但它与索引节点不同的是，目录项是由内核维护的一个数据结构，不存放于磁盘，而是缓存在内存。

索引节点(index node，inode)：用来记录文件的元信息，比如 inode 编号、文件大小、访问权限、创建时间、修改时间、数据在磁盘的位置等等。索引节点是文件的唯一标识，同样都会被存储在硬盘中，所以索引节点同样占用磁盘空间。

数据块(data block)：存储数据的地方。

由于索引节点唯一标识一个文件，而目录项记录着文件的名，所以目录项和索引节点的关系是多对一。也就是说，一个文件可以有多个别字。比如，硬链接的实现就是多个目录项中的索引节点指向同一个文件。

目录是特殊文件，和普通文件不同的是：

普通文件的data block里面保存的是文件数据，而目录文件的data block里面保存的是一项项的文件信息

。

通常，第一项是「 . 」，表示当前目录，第二项是「 .. 」，表示上一级目录，接下来就是一个哈希表，对文件名进行哈希计算，把哈希值和对应的 inode 保存起来。

目录和目录项的区别和联系：
目录是个文件，持久化存储在磁盘，而目录项是内核一个数据结构，缓存在内存。
目录文件保存的内容相当于一个目录项列表，目录项的内容是文件名和指向inode的指针。

磁盘读写的最小单位是扇区，扇区的大小只有 512B 大小，很明显，如果每次读写都以这么小为单位，那这读写的效率会非常低。所以，文件系统把多个扇区组成了一个逻辑块，每次读写的最小单位就是逻辑块(数据块)，Linux 中的逻辑块大小为 4KB，也就是一次性读写 8 个扇区，这将大大提高了磁盘的读写的效率。

整个文件结构大概如下所示：

另外，磁盘进行格式化的时候，会被分成三个存储区域，分别是超级块、索引节点区和数据块区。

超级块，用来存储文件系统的详细信息，比如块个数、块大小、空闲块等等。

索引节点区，用来存储索引节点。

虚拟文件系统

文件系统的种类众多，而操作系统希望对用户提供一个统一的接口，于是在用户层与文件系统层引入了中间层，这个中间层就称为虚拟文件系统(Virtual File System，VFS)。

VFS 定义了一组所有文件系统都支持的数据结构和标准接口，这样程序员不需要了解文件系统的工作原理，只需要了解 VFS 提供的统一接口即可。

软链接和硬链接

硬链接是多个目录项中的「索引节点」指向同一个 inode。但是 inode 是不可能跨越文件系统的，每个文件系统都有各自的 inode 数据结构和列表，所以硬链接是不可用于跨文件系统的。由于多个目录项都是指向一个 inode，那么只有删除文件的所有硬链接以及源文件时，系统才会彻底删除该文件。

软链接的多个目录项的「索引节点」分别指向不同的 inode，inode 对应的 data block 的内容是另外一个文件的地址

。所以访问软链接的时候，实际上相当于访问到了另外一个文件，所以软链接是可以跨文件系统的，甚至目标文件被删除了，链接文件还是在的，只不过指向的文件找不到了而已。

文件的存储

分配文件空间

文件的数据是要存储在硬盘上面的，数据在磁盘上的存放方式，就像程序在内存中存放的方式那样，有以下两种：

连续空间存放方式：文件存放在磁盘「连续的」物理空间中。这种模式下，文件的数据都是紧密相连，读写效率很高，因为一次磁盘寻道就可以读出整个文件；但是存在「磁盘空间碎片」和「文件⻓度不易扩展」的问题。

非连续空间存放方式：非连续空间存放方式分为「链表方式」和「索引方式」。

链表方式分配

根据实现的方式的不同，链表可分为「隐式链表」和「显式链接」两种形式。

隐式链表是指文件头要包含「第一块」和「最后一块」的位置， 并且每个数据块里面留出一个指针空间，用来存放下一个数据块的位置，这样一个数据块连着一个数据块，从链头开是就可以顺着指针找到所有的数据块，所以存放的方式可以是不连续的

。

隐式链表的存放方式的缺点在于无法直接访问数据块，只能通过指针顺序访问文件，以及数据块指针消耗了一定的存储空间。隐式链接分配的稳定性较差，系统在运行过程中由于软件或者硬件错误导致链表中的指针丢失或损坏，会导致文件数据的丢失。

显式链接是指把用于链接文件各数据块的指针，显式地存放在内存的一张链接表中，每个表项中存放链接指针，指向下一个数据块号。该表在整个磁盘仅设置一张

。这个表格称为文件分配表(File Allocation Table，FAT)。

由于查找记录的过程是在内存中进行的，因而不仅显著地提高了检索速度，而且大大减少了访问磁盘的次数。但也正是整个表都存放在内存中的关系，它的主要的缺点是不适用于大磁盘。比如，对于 200GB 的磁盘和 1KB 大小的块，这张表需要有 2 亿项，每一项对应于这 2 亿个磁盘块中的一个块，每项如果需要 4 个字节，那这张表要占用 800MB 内存，很显然 FAT 方案对于大磁盘而言不太合适。

索引方式分配

索引的实现是为每个文件创建一个「索引数据块」，里面存放的是指向「索引数据块」的指针列表。

这样只需要在创建文件的时候再创建索引数据块，而不需要创建一张全局的FAT。但是由于索引数据也是存放在磁盘块的，如果文件很小，明明只需一块就可以存放的下，但还是需要额外分配一块来存放索引数据，就会造成额外开销。

Linux文件存储的实现

根据文件的大小，存放的方式会有所变化:

如果存放文件所需的数据块小于 10 块，则采用直接查找的方式。

如果存放文件所需的数据块超过 10 块，则采用一级间接索引方式。

如果前面两种方式都不够存放大文件，则采用二级间接索引方式。

如果二级间接索引也不够存放大文件，这采用三级间接索引方式。

那么，文件头(Inode)就需要包含 13 个指针:

10 个指向数据块的指针。

第 11 个指向索引块的指针。

第 12 个指向二级索引块的指针。

第 13 个指向三级索引块的指针。

所以，这种方式能很灵活地支持小文件和大文件的存放：

对于小文件使用直接查找的方式可减少索引数据块的开销。

对于大文件则以多级索引的方式来支持，所以大文件在访问数据块时需要大量查询。

空闲空间管理

前面说到的文件的存储是针对已经被占用的数据块组织和管理，磁盘的空闲空间管理用于快速找出一个新的空闲地址空间用于存储新的数据块。接下来介绍几种常⻅的方法：

空闲表法

空闲链表法

位图法

空闲表法

空闲表法就是为所有空闲空间建立一张表，表内容包括空闲区的第一个块号和该空闲区的块个数，注意，这个方式是连续分配的。

当请求分配磁盘空间时，系统依次扫描空闲表里的内容，直到找到一个合适的空闲区域为止。当用户撤销一个文件时，系统回收文件空间。这时，也需顺序扫描空闲表，寻找一个空闲表条目并将释放空间的第一个物理块号及它占用的块数填到这个条目中。

空闲链表法

我们也可以使用「链表」的方式来管理空闲空间，每一个空闲块里有一个指针指向下一个空闲块，这样也能很方便的找到空闲块并管理起来。如下图：

当创建文件需要一块或几块时，就从链头上依次取下一块或几块。反之，当回收空间时，把这些空闲块依次接到链头上。

这种技术只要在主存中保存一个指针，令它指向第一个空闲块。其特点是简单，但不能随机访问，工作效率低，因为每当在链上增加或移动空闲块时需要做很多 I/O 操作，同时数据块的指针消耗了一定的存储空间。

空闲表法和空闲链表法都不适合用于大型文件系统，因为这会使空闲表或空闲链表太大。

位图法

位图是利用二进制的一位来表示磁盘中一个盘块的使用情况，磁盘上所有的盘块都有一个二进制位与之对应。当值为 0 时，表示对应的盘块空闲，值为 1 时，表示对应的盘块已分配。它形式如下：

在 Linux 文件系统就采用了位图的方式来管理空闲空间，不仅用于数据空闲块的管理，还用于 inode 空闲块的管理，因为 inode 也是存储在磁盘的，自然也要有对其管理。

文件系统结构

数据块的位图是放在磁盘块里的，假设是放在一个块里，一个块 4K，每位表示一个数据块，共可以表示 4 * 1024 * 8 = 2^15 个空闲块，由于 1 个数据块是 4K 大小，那么最大可以表示的空间为 2^15 * 4 *

1024 = 2^27 个 byte，也就是 128M。「一个块的位图 + 一系列的块」这种数据结构就表示一个块组。linux 文件系统由大量块组组成。

最前面的第一个块是引导块，在系统启动时用于启用引导，接着后面就是一个一个连续的块组了，块组的内容如下:

超级块，包含的是文件系统的重要信息，比如 inode 总个数、块总个数、每个块组的 inode 个数、每个块组的块个数等等。

块组描述符，包含文件系统中各个块组的状态，比如块组中空闲块和 inode 的数目等，每个块组都包含了文件系统中「所有块组的组描述符信息」。

数据位图和 inode 位图，用于表示对应的数据块或 inode 是空闲的，还是被使用中。

inode 列表，包含了块组中所有的 inode，inode 用于保存文件系统中与各个文件和目录相关的所有元数据。

数据块，包含文件的有用数据。

文件系统I/O

根据调用方在发起数据请求后，是否会被阻塞等待数据返回，I/O模型分为：

阻塞I/O：调用方会被阻塞，直到数据返回。

非阻塞I/O：调用方不会被阻塞，可以先做自己的事情，等数据准备好了之后再得到数据。

根据调用方是主动还是被动接受准备好的数据，I/O模型分为：

同步I/O：调用方主动轮询数据是否准备好，如果准备好就主动拉取数据。

异步I/O：调用方只需要被动等待准备好的数据。

总共可以分为以下四种I/O模型

同步阻塞I/O

同步阻塞 I/O：当用户程序执行 read ，线程会被阻塞，一直等到内核数据准备好，并把数据从内核缓冲区拷⻉到应用程序的缓冲区中，当拷⻉过程完成， read 才会返回。

注意，阻塞等待的是「内核数据准备好」和「数据从内核态拷⻉到用户态」这两个过程。

同步非阻塞I/O

同步非阻塞 I/O：非阻塞的 read 请求在数据未准备好的情况下立即返回，可以继续往下执行，此时应用程序不断轮询内核，直到数据准备好，内核将数据拷⻉到应用程序缓冲区， read 调用才可以获取到结果。

这里最后一次 read 调用，获取数据的过程，是一个同步的过程，是需要等待的过程。这里的同步指的是内核态的数据拷⻉到用户程序的缓存区这个过程。

但是单纯的同步非阻塞I/O其实应用意义不大，因为应用程序一直轮询内核的 I/O 是否准备好。如果轮询频率太高，应用程序相当于什么也做不了，只是在循环，和同步阻塞I/O没什么区别；如果轮询频率太低，可能不能及时获取数据。

那能不能把轮询的任务交给一个单独的线程专门完成？这就衍生了I/O多路复用技术。

I/O多路复用

I/O多路复用把轮询任务交给专门的系统函数（select/poll/epoll），当内核数据准备好时，系统函数再以事件通知应用程序进行操作。

异步I/O

实际上，无论是阻塞 I/O、非阻塞 I/O，还是基于非阻塞 I/O 的多路复用都是同步调用。

因为它们在 read 调用时，内核将数据从内核空间拷⻉到应用程序空间，过程都是需要等待的，也就是说这个过程是同步的

。如果内核实现的拷⻉效率不高，read 调用就会在这个同步过程中等待比较⻓的时间。

而真正的异步 I/O 是「内核数据准备好」和「数据从内核态拷⻉到用户态」这两个过程都不用等待。

select/poll/epoll

select/poll/epoll 是内核提供给用户态的多路复用系统调用，进程可以通过一个系统调用函数从内核中获取多个事件。

select

select 实现多路复用的方式是：

将已连接的 Socket 都放到一个文件描述符集合，然后调用 select 函数将文件描述符集合拷⻉到内核里。

内核遍历文件描述符集合检查是否有网络事件产生。当检查到有事件产生后，将此 Socket 标记为可读或可写。

把整个文件描述符集合拷⻉回用户态里，然后用户态还需要再通过遍历的方法找到可读或可写的 Socket，然后再对其处理。

select函数的格式：

select 函数监视的文件描述符分3类，分别是writefds、readfds、和exceptfds。调用后select函数会阻塞，直到有描述副就绪（有数据可读、可写、或者有except），或者超时（timeout指定等待时间，如果立即返回设为null即可），函数返回。当select函数返回后，可以通过遍历fdset，来找到就绪的描述符。

select 这种方式，需要进行 2 次「遍历文件描述符集合」和 2 次「拷⻉文件描述符集合」。select 使用固定长度的 BitsMap 来表示文件描述符集合，支持最大数量为 1024。select 目前几乎在所有的平台上支持。

poll

poll 和 select 唯一的区别是：不再用 BitsMap 来存储所关注的文件描述符，取而代之用动态数组，以链表形式来组织，突破了 select 的文件描述符个数限制，当然还会受到系统文件描述符限制。

poll函数的格式：

不同与 select 使用三个 BitsMap 来表示三个 fdset 的方式，poll 使用一个 pollfd 的指针实现。

pollfd 结构包含了要监视的 event 和发生的 event，不再使用select “参数-值”传递的方式。同时，pollfd 并没有最大数量限制（但是数量过大后性能也是会下降）。和 select 函数一样，poll 返回后，需要轮询 pollfd 来获取就绪的描述符。

select 和 poll 都需要在返回后，通过遍历文件描述符来获取已经就绪的 socket。事实上，同时连接的大量客户端在一时刻可能只有很少的处于就绪状态，因此随着监视的描述符数量的增长，其效率也会线性下降。

epoll

epoll 是在 2.6 内核中提出的，用于解决 select 和 poll 的性能问题和描述符限制问题。

epoll 需要三个函数：

epoll_create：创建一个 epoll 的句柄，size 用来告诉内核这个监听的数目一共有多大。参数 size 并不是限制了 epoll 所能监听的描述符最大个数，只是对内核初始分配内部数据结构的一个建议。当创建好 epoll 句柄后，它就会占用一个 fd 值。

epoll_ctl：把需要监控的 socket 加入内核中的红黑树里。epoll 在内核里使用红黑树来跟踪进程所有待检测的文件描述字符。这样就不需要像 select/poll 每次操作时都传入整个 socket 集合，只需要传入一个待检测的 socket。

epoll_wait：从内核返回有事件发生的文件描述符的个数。内核里维护了一个链表来记录就绪事件，并且采用事件驱动的机制，当某个 socket 有事件发生时，通过回调函数内核会将其加入到这个就绪事件链表中。不需要像 select/poll 那样轮询扫描整个 socket 集合，大大提高了检测的效率。

epoll 支持两种事件触发模式，分别是边缘触发(edge-triggered，ET)和水平触发(level-triggered，LT)。

边缘触发模式：当被监控的 Socket 描述符上有可读事件发生时，服务器端只会从 epoll_wait 中苏醒一次，即使进程没有调用 read 函数从内核读取数据，也依然只苏醒一次，因此我们程序要保证一次性将内核缓冲区的数据读取完。

水平触发模式：当被监控的 Socket 上有可读事件发生时，服务器端不断地从 epoll_wait 中苏醒，直到内核缓冲区数据被 read 函数读完才结束。

一般来说，边缘触发的效率比水平触发的效率要高，因为边缘触发可以减少 epoll_wait 的系统调用次数，系统调用也是有一定的开销的的，毕竟也存在上下文的切换。epoll 默认的触发模式是水平触发，但是可以根据应用场景设置为边缘触发模式。

如果使用边缘触发模式，I/O 事件发生时只会通知一次，而且我们不知道到底能读写多少数据，所以在收到通知后应尽可能地读写数据，以免错失读写的机会。因此，我们会循环从文件描述符读写数据，那么如果文件描述符是阻塞的，没有数据可读写时，进程会阻塞在读写函数那里，程序就没办法继续往下执行。所以使用边缘触发模式一般和非阻塞 I/O 搭配使用，程序会一直执行 I/O 操作，直到系统调用(如 read 和 write )返回错误，错误类型为 EAGAIN 或 EWOULDBLOCK 。

零拷贝

DMA

在了解零拷贝之前，我们先了解下 DMA 技术。在没有 DMA 技术前，I/O 的过程是这样的：

可以看到，整个数据的传输过程，都要需要 CPU 亲自参与搬运数据的过程，而且这个过程，CPU 是不能做其他事情的。而且由于网络传输和数据复制的速度远远低于 CPU 的速度，CPU 大部分时间都是空等，造成性能的极大浪费。所以就出现了 DMA (Direct Memory Access)技术。

DMA 技术的原理：

在进行 I/O 设备和内存的数据传输的时候，数据搬运的工作全部交给 DMA 控制器，而 CPU 不再参与任何与数据搬运相关的事情，这样 CPU 就可以去处理别的事务

。使用 DMA 技术后的 I/O 的过程是这样的：

但是注意数据从内核缓冲区拷贝到用户缓冲区这个过程，还是由 CPU 来完成的。而且read函数的调用和返回都会发生用户态和内核态的切换。这些都是比较耗时的过程。所谓的零拷贝技术，其实就是减少两个过程：

减少数据在内核缓冲区拷贝和用户缓冲区的来回复制

减少上下文切换

传统文件传输（read + write）

传统文件传输直接调用 read 和 write 函数：

发生了 4 次上下文切换，2 次 CPU 拷贝，2 次 DMA 拷贝。

mmap + write

可以用 mmap() 替换 read() 系统调用函数。mmap() 系统调用函数会直接把内核缓冲区里的数据「映射」到用户空间，这样，操作系统内核与用户空间就不需要再进行任何的数据拷⻉操作。这样就减少 1 次 CPU 拷贝。

发生了 4 次上下文切换，1 次 CPU 拷贝，2 次 DMA 拷贝。

sendfile

sendfile() 可以替代 read() 和 write() 这两个系统调用，这样就可以减少一次系统调用，也就减少了 2 次上下文切换的开销。其次，该系统调用，可以直接把内核缓冲区里的数据拷⻉到 socket 缓冲区里，不再拷⻉到用户态，这样就减少 1 次 CPU 拷贝。

发生了 2 次上下文切换，1 次 CPU 拷贝，2 次 DMA 拷贝。

如果网卡支持 SG-DMA(The Scatter-Gather Direct Memory Access) 技术，我们还可以把这 1 次 CPU 拷贝也省略。

查看网卡是否支持 scatter-gather 特性：

Linux 内核 2.4 版本开始起，对于支持网卡支持 SG-DMA 技术的情况下， sendfile() 系统调用的过程如下：

发生了 2 次上下文切换，2 次 DMA 拷贝。