Linux I/O 栈介绍

Inode、文件、目录之间的关系之前已经探索过几次了，但是过一段时间仍然无法很轻松的回忆起他们之间的关系，正好借着这本书的文件系统部分，再对相关的逻辑进行一次梳理。

如何组织磁盘结构？

这个问题只关乎于文件系统如何在物理磁盘上组织数据。第一个问题是：给出一个文件，如何从物理磁盘中找到对应的物理块的位置？Linux 的答案是使用 inode，inode 结构体表示一个文件或者文件夹（文件夹是一种特殊文件），inode 管理着多个物理块，这些物理块连在一起就是完整的数据。

第二个问题是，物理磁盘的区域如何划分，才能正确找到文件 inode，进而获得正确的物理块信息呢？下面这张图介绍的是如何通过 inode 号找到磁盘中的 inode 结构体以及如何通过 inode 找到对应的 block，这里不涉及目录和文件的概念。

Super block 保存了 inode bitmap 区域、datablock bitmap 区域的长度，分别是 s_imap_blocks 和 s_zmap_blocks。Super block 还有一个 s_firstdatazone 字段，标识 data 区域的起始位置。

Bitmap 是位图，用于标注某一个东西是否被使用。假设第六个 inode 被使用了，那么 inode bitmap 的第 6 位就置为 1，反之置 0。同理，datablock bitmap 用于标注一个 datablock 是否被使用。

Inode 结构体的定义是（代码来自于超级古早的 linux 0.10 版本）

// d_ 前缀是指存在 disk 中的结构
// m_ 前缀是指存在 mem 中的结构
struct d_inode {
  // === snipped ===
  // 为什么让 i_zone 的数量是 9？
  unsigned short i_zone[9];
}

Linux 使用 inode 号表示一个文件，因此第 (1) 步是：如何通过 inode 号（暂定先叫 INODE_NUM）从磁盘上找到对应的 inode 结构体。第 (1.1) 步是确定该 inode 在 inode table 区域的第几个 block，即对应上图的“其中的一个 block”的过程。

经过上面的计算，我们可以从 inode table 区域取出一个 block。试试上，一个 block 比 inode 的长度多很多，换句话说一个 block 是一个小型 inode 数组。

第 (1.2) 步是确定 block 内偏移，找出我们想要的 inode。其公式是 (INODE_NUM - 1) % INODE_PER_BLOCK，对应上图是“其中的一个 inode”。

第 (2) 步是根据 inode 获得与之关联的的全部物理块。这部分映射关系保存在 inode 的 i_zone 字段中，它是一个物理块号数组，比如一个 block 的长度是 4KB 并且 i_zone[0] 的值是 90，文件是被 inode 号唯一确定的 ，那么该文件前 4KB 的数据保存在第 90 个 block 中。

现在你应该知道如何在文件系统中找到文件的全部物理块了吧。

目录是如何工作的？

上面我们介绍的是如何找到一个文件的全部物理块：文件名 -> inode -> 物理块。不过文件系统中还有目录这个非常重要的概念，Linux 的目录是一种特殊的文件。这句话的理解方式是，当我们想知道目录里面有什么子项目的时候，就要像读取文件一样读取目录中的数据，该数据包含了当前目录中包含了什么文件以及子目录，由操作系统解析这些数据并展示给用户。

一个目录项（可以表示一个文件，也可以表示一个子目录）的数据结构如下所示。

struct dir_entry {
  // inode
  unsigned short inode;
  // 名称
  char name[NAME_LEN];
  // === snipped ===
}

一个目录可以简单地理解为多个 dir_entry 组成的数组，即 dir_entry[DIR_LEN]。当从硬盘上读取到目录项数组之后，通过遍历的方式匹配文件名，并返回文件的 inode。

如何向设备读取/写入数据？

上面的两个课题都在解决如何根据 inode 找到对应的物理块。假设我们已经找到了物理块，那我们应该如何读取或者写入数据呢？文件系统（file system）读取或写入数据是按照字节流的方式，而设备层（底层存储）则是按照块方式存储的，因此需要将流转换为块方式存储。为了提升效率，文件的写入和读取都是通过缓存实现的，因此任何数据的操作都需要先将设备的中的数据拷贝到内存中。

以写操作为例（读操作类似）：

• 计算文件写入位置 pos。如果文件写入 flags 包含 O_APPEND（以追加方式），那么 pos 的值是 inode 的 size（可以理解为当前文件的结尾）。如果没有，则用文件的位置（文件当前被用户读到的位置）。
• 进入循环 i<count，i 表示已写入长度，count 表示总长度，退出条件是写入完成全部的数据。
  • 从 inode 中找到对应的块号：调用 create_block()，这个函数没有被展示，我大概猜测是去系统的块缓存中寻找指定的块，key 是 pos/BLOCK_SIZE。这个 key 会保存在 inode 的 izone 里，如果这个 block 已经存在与 izone 中，则说明已经被系统的块缓存。否则，创建一个缓存块，并更新到 izone 中。
  • 从外设中读取数据到缓存中：调用 bread() ，如果已经读取过数据了，则直接返回 buffer_head，否则，从设备读取数据。
  • 按字节向块中写入数据。

I/O 栈的层次

Linux 将 I/O 栈分为四个层次：

• 文件系统在最上层是与用户交互的，所以有文件、inode 等概念。
• 通用层是用户和硬件之间的一层抽象，在通用层之下是硬件的概念，设备可能是硬盘，可能是光盘，有很多其他的概念。向上层暴露了块的概念，如右图所示，不管下层设备是什么，能对上层提供统一的接口和概念。需要注意的是，块和扇区的比例是可以自定义的，可能是 1:1、1:2 或者任意。在通用层的块对应的数据结构是 buffer_head 结构体。

// b_data 是 buffer_head 对应数据的起始地址，& ~PAGE_MASK 的取反表示获取页内偏移
#define bh_offset(bh)           ((unsigned long)(bh)->b_data & ~PAGE_MASK)

struct buffer_head {
  // the page this bh is mapped to 
  struct page *b_page;
  
  // size of mapping
  size_t b_size;
  // 存储数据的内存指针（默认长度是 1024 bytes）
  // pointer to data **within the page**
  char *b_data;
  // 设备名
  unsigned short b_dev;
  // 块编号
  unsigned short b_blocknr;
}

• 通用层在创建一个新的块的时候，会以请求（request）的方式，调用驱动层让其从物理设备中读取数据，如果此时设备忙，则会将请求添加到请求队列。
• 驱动层和物理设备就是用 Port I/O + 中断的方式，这里就暂时不再赘述了。

使用 Page Cache 缓存数据

仅 Buffer Head 和 Buffer Head + Page Cache 的区别是什么？

buffer_head 最开始的版本提供一个指针，指向缓存数据的起始地址，也就是说原来 buffer_head 是直接持有数据的。而 buffer_head + page cache 模式下，指针被替换为了 b_data，指向的是某个 page 的地址。

文件的数据被保存在 page cache 中，buffer_head 是保存缓存的元数据信息的结构体。如上图中展示的那样，文件的 4096-8192B 被缓存在第二个 page 中（其他的 pages 没有画出来），每一个块的数据部分都指向了 page 的某个区域。

系统有一个公共区域专门管理块（图中 hashmap），这样的好处是一个块在多个地方被使用的情况下，可以减少读磁盘的次数。系统会把块放到一个 hashmap 中，通过 dev、block 和 size 三元组确定块的 key，这样数据只需要从内存中复制。

跨页读文件

文件是以字节流的方式读取，所以很容易出现跨页的问题，如下图所示。

系统先为 0-4096 字节和 4096-8192 字节创建两个 pages，然后从 hashmap 中找 buffer_head，如果存在则说明数据已经存在于内存中，则直接在内存之间拷贝就行，否则需要调用驱动，从外设中读取设备。

Vectored I/O

最初的 Linux 版本中，buffer_head 不仅负责块到内存的映射，而且还是一次读写的长度。假设一个块长度是 512B，那么一个 buffer_head 映射长度为 512B 的数据到内存中，那么我们读取 4096B 数据的时候，就不得不调用 8 次 read() 方法（写同理），而且调用之间原子操作，可能被其他的进程写入信息。

readv() 和 writev() 横空出世[1]，可以自己定义数据长度。事实上，上面的遍历操作由操作系统代为执行了，好处是操作系统可以很方便让其变为原子操作，对用户可以简化接口。

这就是 Vectored I/O 的初衷，让用户读取/写入的长度不再因为 buffer_head 而强行分割为 512B。

这种方式又称为 Scatter/Gather Read and Write。因为读取的时候可以将数据分散在不同的内存区域中（不同的内存区域由 iovec 结构体连接在一起），写入的时候由将不同区域的内存的数据聚合在一起。

int readv(int fd, const struct iovec* vec, size_t count); 
int writev(int fd, const struct iovec* vec, size_t count); 

struct iovec {
  void * iov_base; /*buffer's address*/
  size_t iov_len; /*buffer's size in bytes*/
}

其中，fd 是 file descriptor，vec 是把不同内存区域联系起来的关键数据结构，它本身就是一个数组，长度由 count 控制。Vec 数组组织数据的方法如下图所示，每个元素都对应着一个连续的内存区域，但是也只是一小块连续的，iovec[i] 和 iovec[i+1] 之间就一定不是连续的（因为如果是连续的，完全可以用一个元素表示），读取的时候相当于数据分散存储，写入相当于把数据聚合。

BIO

上面提到过，buffer_head 受制于自身管理的长度限制，需要把一个完整 I/O 以块为单位切分为多次，无法满足 vectored io 的要求。因此 bio 横空出世，当然我们还可以获得的其他好处是[2]：

• Bio 可以表示高端内存（high memory），因为 bio 直接与物理页打交道，buffer_head 是与指针打交道（使用虚拟地址？）；
• Bio 既可以表示普通页 I/O 也可以表示直接 I/O（这个没懂）；
• 更好的实现 Vectored I/O；
• 仅针对 I/O 操作，bio 结构体相比于 buffer_head 更轻量（比如不需要表示映射关系等）。

在出现了 bio 之后，buffer_head 结构体依然还存在，但是它的作用仅仅负责块到内存的映射。在真正向驱动发送请求的时候，则使用的是 bio 的方式。

struct bio_vec {
  // 对应的 page
struct page*bv_page;
  // 数据的长度
unsigned intbv_len;
  // page 内的 offset
unsigned intbv_offset;
};

与 buffer_head 结构体（bh）的转换关系是：

• bio->bi_io_vec[0].bv_page = bh.b_page;
• bio->bi_io_vec[0].bv_len = bh->b_size;
• bio->bi_io_vec[0].bv_offset = bh_offset(bh);，这里的 bh_offset 的定义见上面。

如上图所示，在一个 bio 里聚集里多个不连续的内存页，比较方便的实现了 Vectored I/O。

References

1. https://www.computerworld.com/article/2785907/scatter-gather-i-o.html
2. https://stackoverflow.com/questions/5484617/struct-buffer-head-inefficiency/57407020#57407020