Linux I/O 栈介绍

文件系统、Page Cache、Vectored I/O 介绍

Table of Contents

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<counti 表示已写入长度,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