JINHU
页高速缓存 page cache
根据摩尔定律：芯片中的晶体管数量每隔 18 个月就会翻一番。导致 CPU 的性能和处理速度变得越来越快，而提升 CPU 的运行速度比提升内存的运行速度要容易和便宜的多，所以就导致了 CPU 与内存之间的速度差距越来越大。
CPU 与内存之间的速度差异到底有多大呢？我们知道寄存器是离 CPU 最近的，CPU 在访问寄存器的时候速度近乎于 0 个时钟周期，访问速度最快，基本没有时延。而访问内存则需要 50 - 200 个时钟周期。
所以为了弥补 CPU 与内存之间巨大的速度差异，提高 CPU 的处理效率和吞吐，于是我们引入了 L1 , L2 , L3 高速缓存集成到 CPU 中。CPU 访问高速缓存仅需要用到 1 - 30 个时钟周期，CPU 中的高速缓存是对内存热点数据的一个缓存。
而本文我们讨论的主题是内存与磁盘之间的关系，CPU 访问磁盘的速度就更慢了，需要用到大概约几千万个时钟周期.
我们可以看到 CPU 访问高速缓存的速度比访问内存的速度快大约10倍，而访问内存的速度要比访问磁盘的速度快大约 100000 倍。
引入 CPU 高速缓存的目的在于消除 CPU 与内存之间的速度差距，CPU 用高速缓存来存放内存中的热点数据。那么同样的道理，本小节中我们引入的页高速缓存 page cache 的目的是为了消除内存与磁盘之间的巨大速度差距，page cache 中缓存的是磁盘文件的热点数据。
当程序去读文件，可以通过read也可以通过mmap去读，当你通过任何一种方式从磁盘读取文件时，内核都会给你申请一个Page cache，用来缓存磁盘上的内容。这样读过一次的数据，下次读取的时候就直接从Page cache里去读。
另外我们根据程序的时间局部性原理可以知道，磁盘文件中的数据一旦被访问，那么它很有可能在短期被再次访问，如果我们访问的磁盘文件数据缓存在 page cache 中，那么当进程再次访问的时候数据就会在 page cache 中命中，这样我们就可以把对磁盘的访问变为对物理内存的访问，极大提升了对磁盘的访问性能。
程序局部性原理表现为：时间局部性和空间局部性。时间局部性是指如果程序中的某条指令一旦执行，则不久之后该指令可能再次被执行；如果某块数据被访问，则不久之后该数据可能再次被访问。空间局部性是指一旦程序访问了某个存储单元，则不久之后，其附近的存储单元也将被访问。
在Linux上直接可以通过命令来看，首先最简单的是free命令来看一下
首先我们来看看buffers和cached的定义Buffers
- 是对原始磁盘块的临时存储，也就是用来缓存磁盘的数据，通常不会特别大（20MB 左右）。这样，内核就可以把分散的写集中起来，统一优化磁盘的写入，比如可以把多次小的写合并成单次大的写等等。
- Cached 是从磁盘读取文件的页缓存，也就是用来缓存从文件读取的数据。这样，下次访问这些文件数据时，就可以直接从内存中快速获取，而不需要再次访问缓慢的磁盘
buffer cache和page cache在处理上是保持一致的，但是存在概念上的差别，page cache是针对文件的cache，buffer是针对磁盘块数据的cache，仅此而已。
page cache 的产生
Page Cache的产生有两种不同的方式
- Buffered I/O(标准I/O)
- Memory-Mapped I/O(储存映射IO)
这两种方式分别都是如何产生Page Cache的呢？
从图中可以看到，二者是都能产生Page Cache，但是二者还是有差异的
- 标准I/O是写的是用户缓存区(User page对应的内存)，然后再将用户缓存区里的数据拷贝到内核缓存区(Pagecahe Page对应的内存)；如果是读的话则是内核缓存区拷贝到用户缓存区，再从用户缓存区去读数据，也就是Buffer和文件内容不存在映射关系
- 储存映射IO，则是直接将Page Cache的Page给映射到用户空间，用户直接读写PageCache Page里的数据
从原理来说储存映射I/O要比标准的I/O效率高一些，少了“用户空间到内核空间互相拷贝”的过程。下图是一张简图描述这个过程：
- 首先，往用户缓冲区Buffer(用户空间)写入数据，然后，Buffer中的数据拷贝到内核的缓冲区(这个是PageCache Page)
- 如果内核缓冲区还没有这个page，就会发生Page Fault会去分配一个Page；如果有，就直接用这个PageCache的Page
- 拷贝结束后，该PageCache的Page是一个Dirty Page脏页，然后该Dirty Page中的内容会同步到磁盘，同步到磁盘后，该PageCache Page变味Clean Page并且继续存在系统中
我们可以通过命令查看系统中的脏页
$ cat /proc/vmstat | egrep "dirty|writeback"
nr_dirty 44
nr_writeback 0
nr_writeback_temp 0
nr_dirty_threshold 1538253
nr_dirty_background_threshold 768187
nr_dirty:表示系统中积压了多少脏页(单位为Page 4KB)
nr_writeback则表示有多少脏页正在回写到磁盘中(单位为Page 4KB)
在前边的内容中我们多次提到操作系统是将物理内存分为一个一个的页面来组织管理的，每页大小为 4k ，而磁盘中的文件数据在磁盘中是分为一个一个的块来组织管理的，每块大小也为 4k。
page cache 中缓存的就是这些内存页面，页面中的数据对应于磁盘上物理块中的数据。page cache 中缓存的大小是可以动态调整的，它可以通过占用空闲内存来扩大缓存页面的容量，当内存不足时也可以通过回收页面来缓解内存使用的压力。
当用户进程发起 read 系统调用之后，内核首先会在 page cache 中检查请求数据所在页面是否已经缓存在 page cache 中。
- 如果缓存命中，内核直接会把 page cache 中缓存的磁盘文件数据拷贝到用户空间缓冲区 Buffer 中，从而避免了龟速的磁盘 IO。
- 如果缓存没有命中，内核会分配一个物理页面，将这个新分配的页面插入 page cache 中，然后调度磁盘块 IO 驱动从磁盘中读取数据，最后用从磁盘中读取的数据填充这个物里页面。
根据前面介绍的程序时间局部性原理，当进程在不久之后再来读取数据的时候，请求的数据已经在 page cache 中了。极大地提升了文件 IO 的性能。
page cache 的回收
回收的主要方式有两种：直接回收；后台回收。
由于内核page cache的作用，写操作实际被延迟写入。当page cache里的数据被用户写入但是没有刷新到磁盘时，则该page为脏页（块设备page cache机制因为以前机械磁盘以扇区为单位读写，引入了buffer_head，每个4K的page进一步划分成8个buffer，通过buffer_head管理，因此可能只设置了部分buffer head为脏）。
脏页在以下情况下将被回写（write back）到磁盘上：
- 脏页在内存里的时间超过了阈值。
- 系统的内存紧张，低于某个阈值时，必须将所有脏页回写。
- 用户强制要求刷盘，如调用sync()、fsync()、close()等系统调用。
以前的Linux通过pbflush机制管理脏页的回写，但因为其管理了所有的磁盘的page/buffer_head，存在严重的性能瓶颈，因此从Linux 2.6.32开始，脏页回写的工作由bdi_writeback机制负责。bdi_writeback机制为每个磁盘都创建一个线程，专门负责这个磁盘的page cache或者buffer cache的数据刷新工作，以提高I/O性能。
在 kernel/sysctl.c中列出了所有的配置文件的信息
static struct ctl_table vm_table[] = {
...
{ .procname = "dirty_background_ratio",
.data = &dirty_background_ratio,
.maxlen = sizeof(dirty_background_ratio),
.mode = 0644,
.proc_handler = dirty_background_ratio_handler,
.extra1 = &zero,
.extra2 = &one_hundred,
},
{
.procname = "dirty_ratio",
.data = &vm_dirty_ratio,
.maxlen = sizeof(vm_dirty_ratio),
.mode = 0644,
.proc_handler = dirty_ratio_handler,
.extra1 = &zero,
.extra2 = &one_hundred,
},
{
.procname = "dirty_writeback_centisecs",
.data = &dirty_writeback_interval,
.maxlen = sizeof(dirty_writeback_interval),
.mode = 0644,
.proc_handler = dirty_writeback_centisecs_handler,
},
...
}
这些值在mm/page-writeback.c中有全局变量定义
int dirty_background_ratio = 10;
int vm_dirty_ratio = 20;
unsigned int dirty_writeback_interval = 5 * 100; /* centiseconds */
通过ps -aux，我们可以看到writeback的内核进程
这实际上是一个工作队列对应的进程，在default_bdi_init()中创建(mm/backing-dev.c)
static int __init default_bdi_init(void)
{
int err;
bdi_wq = alloc_workqueue("writeback", WQ_MEM_RECLAIM | WQ_FREEZABLE |
WQ_UNBOUND | WQ_SYSFS, 0);
if (!bdi_wq)
return -ENOMEM;
err = bdi_init(&noop_backing_dev_info);
return err;
}
回刷进程的核心是函数wb_workfn()，通过函数wb_init()绑定。
static int wb_init(struct bdi_writeback *wb, struct backing_dev_info *bdi
int blkcg_id, gfp_t gfp)
{
...
INIT_DELAYED_WORK(&wb->dwork, wb_workfn);
...
}
唤醒回刷进程的操作是这样的
static void wb_wakeup(struct bdi_writeback *wb)
{
spin_lock_bh(&wb->work_lock);
if (test_bit(WB_registered, &wb->state))
mod_delayed_work(bdi_wq, &wb->dwork, 0);
spin_unlock_bh(&wb->work_lock);
}
表示唤醒的回刷任务在工作队列writeback中执行，这样，就把工作队列和回刷工作绑定了，重点看看这个接口做了些什么工作
void wb_workfn(struct work_struct *work)
{
struct bdi_writeback *wb = container_of(to_delayed_work(work),
struct bdi_writeback, dwork);
long pages_written;
set_worker_desc("flush-%s", bdi_dev_name(wb->bdi));
//如果当前不是一个救援工作队列，或者当前bdi设备已注册，这是一般路径
if (likely(!current_is_workqueue_rescuer() ||
!test_bit(WB_registered, &wb->state))) {
/*
* The normal path. Keep writing back @wb until its
* work_list is empty. Note that this path is also taken
* if @wb is shutting down even when we're running off the
* rescuer as work_list needs to be drained.
*/
// 从bdi的work_list取出队列里的任务，执行脏页回写
do {
pages_written = wb_do_writeback(wb);
trace_writeback_pages_written(pages_written);
} while (!list_empty(&wb->work_list));
} else {
/*
* bdi_wq can't get enough workers and we're running off
* the emergency worker. Don't hog it. Hopefully, 1024 is
* enough for efficient IO.
*/
//只提交一个work并限制写入1024个pages
pages_written = writeback_inodes_wb(wb, 1024,
WB_REASON_FORKER_THREAD);
trace_writeback_pages_written(pages_written);
}
//如果上面处理完到现在这段间隔又有了work，再次立马启动回写进程
if (!list_empty(&wb->work_list))
wb_wakeup(wb);
else if (wb_has_dirty_io(wb) && dirty_writeback_interval)
wb_wakeup_delayed(wb);
//如果所有bdi设备上挂的dirty inode回写完，那么就重置定制器，
//再过dirty_writeback_interval，即5s后再唤醒回写进程
}
正常路径，rescue workerrescue内核线程，内存紧张时创建新的工作线程可能会失败，如果内核中有会需要回收的内存，就调用wb_do_writeback进行回。
收如果当前workqueue不能获得足够的worker进行处理，只提交一个work并限制写入1024个pages。
程代码较多，暂不去深入分析，重点关注相关的配置是如何起作用的。
触发writeback的地方主要有以下几处：
主动发起：
手动执行sysn命令
sync->
SYSCALL_DEFINE0(sync)->
sync_inodes_one_sb->
sync_inodes_sb->
bdi_queue_work
syncfs系统调用
SYSCALL_DEFINE1(syncfs, int, fd)->
sync_filesystem->
__sync_filesystem->
sync_inodes_sb->
bdi_queue_work
直接内存回收，内存不足时调用
free_more_memory->
wakeup_flusher_threads->
__bdi_start_writeback->
bdi_queue_work
分配内存空间不足，触发回写脏页腾出内存空间
__alloc_pages_nodemask->
__alloc_pages_slowpath->
__alloc_pages_direct_reclaim->
__perform_reclaim->
try_to_free_pages->
do_try_to_free_pages->
wakeup_flusher_threads->
__bdi_start_writeback->
bdi_queue_work
remount/umount操作，需要先将脏页写回
空间层面:
当系统的“dirty”的内存大于某个阈值，该阈值是在总共的“可用内存”（包括free pages 和reclaimable pages）中的占比。
参数“dirty_background_ratio”(默认值10%)，或者是绝对字节数“dirty_background_bytes”（默认值为0，表示生效）。两个参数只要谁先达到即可执行，此时就会交给专门负责writeback的background线程去处理。
参数“dirty_ratio”(默认值30%)和“dirty_bates”（默认值为0，表示生效），当“dirty”的内存达到这个比例或数量，进程则会停下write操作（被阻塞），先把“dirty”进行writeback。
时间层面：
周期性的扫描，扫描间隔用参数：dirty_writeback_interval表示，以毫秒为单位。发现存在最近一次更新时间超过某个阈值（参数：dirty_expire_interval，单位毫秒）的pages。如果每个page都维护最近更新时间，开销会很大且扫描会很耗时，因此具体实现不会以page为粒度，而是按inode中记录的dirtying-time来计算。
page cache 性能优化
通过前文我们知道了Linux是用Cache/Buffer缓存数据，提高系统的I/O性能，且有一个回刷任务在适当时候把脏数据回刷到储存介质中。那么接下来我们重点学习优化机制。
包括以下内容
1. 什么时候触发回刷？
2. 脏数据达到多少阈值还是定时触发呢？
3. 内核是如何做到回写机制的
Linux内核在/proc/sys/vm中有透出数个配置文件，可以对触发回刷的时机进行调整。内核的回刷进程是怎么运作的呢？这数个配置文件有什么作用呢？
root@root:~# sysctl -a | grep dirty
vm.dirty_background_bytes = 0
vm.dirty_background_ratio = 10
vm.dirty_bytes = 0
vm.dirty_expire_centisecs = 3000
vm.dirty_ratio = 20
vm.dirty_writeback_centisecs = 500
vm.dirtytime_expire_seconds = 43200
vm.dirty_background_ratio：
内存可以填充脏数据的百分比，这些脏数据稍后会写入磁盘。pdflush/flush/kdmflush 这些后台进程会稍后清理脏数据。比如，我有32G内存，那么有3.2G（10%的比例）的脏数据可以待着内存里，超过3.2G的话就会有后台进程来清理。
vm.dirty_ratio:
可以用脏数据填充的绝对最大系统内存量，当系统到达此点时，必须将所有脏数据提交到磁盘，同时所有新的I/O块都会被阻塞，直到脏数据被写入磁盘。这通常是长I/O卡顿的原因，但这也是保证内存中不会存在过量脏数据的保护机制。
vm.dirty_background_bytes 和 vm.dirty_bytes:
另一种指定这些参数的方法。如果设置 xxx_bytes版本，则 xxx_ratio版本将变为0，反之亦然。
vm.dirty_expire_centisecs:
指定脏数据能存活的时间。在这里它的值是30秒。当 pdflush/flush/kdmflush 在运行的时候，他们会检查是否有数据超过这个时限，如果有则会把它异步地写到磁盘中。毕竟数据在内存里待太久也会有丢失风险。
vm.dirty_writeback_centisecs:
指定多长时间 pdflush/flush/kdmflush 这些进程会唤醒一次，然后检查是否有缓存需要清理。
实际上dirty_ratio的数字大于dirty_background_ratio，是不是就不会达到dirty_ratio呢？首先达到dirty_background_ratio的条件后触发flush进程进行异步的回写操作，但是这一过程中应用进程仍然可以进行写操作，如果多个应用写入的量大于flush进程刷出的量，那自然就会达到vm.dirty_ratio这个参数所设定的阙值，此时操作系统会转入同步地进行脏页的过程，阻塞应用进程。
单纯的配置说明毕竟太抽象。结合网上的分享，我们看看在不同场景下，该如何配置？
场景1：尽可能不丢数据
有些产品形态的数据非常重要，例如行车记录仪。在满足性能要求的情况下，要做到尽可能不丢失数据。
/* 此配置不一定适合您的产品，请根据您的实际情况配置 */
dirty_background_ratio = 5
dirty_ratio = 10
dirty_writeback_centisecs = 50
dirty_expire_centisecs = 100
这样的配置有以下特点：
- 当脏数据达到可用内存的5%时唤醒回刷进程
- 脏数据达到可用内存的10%时，应用每一笔数据都必须同步等待
- 每隔500ms唤醒一次回刷进程
- 当脏数据达到可用内存的5%时唤醒回刷进程
由于发生交通事故时，行车记录仪随时可能断电，事故前1~2s的数据尤为关键。因此在保证性能满足不丢帧的情况下，尽可能回刷数据。
此配置通过减少Cache，更加频繁唤醒回刷进程的方式，尽可能让数据回刷。
此时的性能理论上会比每笔数据都O_SYNC略高，比默认配置性能低，相当于用性能换数据安全。
场景2：追求更高性能
有些产品形态不太可能会掉电，例如服务器。此时不需要考虑数据安全问题，要做到尽可能高的IO性能。
/* 此配置不一定适合您的产品，请根据您的实际情况配置 */
dirty_background_ratio = 50
dirty_ratio = 80
dirty_writeback_centisecs = 2000
dirty_expire_centisecs = 12000
这样的配置有以下特点：
- 当脏数据达到可用内存的50%时唤醒回刷进程
- 当脏数据达到可用内存的80%时，应用每一笔数据都必须同步等待
- 每隔20s唤醒一次回刷进程
- 内存中脏数据存在时间超过120s则在下一次唤醒时回刷
与场景1相比，场景2的配置通过 增大Cache，延迟回刷唤醒时间来尽可能缓存更多数据，进而实现提高性能
场景3：突然的IO峰值拖慢整体性能
什么是IO峰值？突然间大量的数据写入，导致瞬间IO压力飙升，导致瞬间IO性能狂跌，对行车记录仪而言，有可能触发视频丢帧。
/* 此配置不一定适合您的产品，请根据您的实际情况配置 */
dirty_background_ratio = 5
dirty_ratio = 80
dirty_writeback_centisecs = 500
dirty_expire_centisecs = 3000
这样的配置有以下特点：
1. 当脏数据达到可用内存的5%时唤醒回刷进程
2. 当脏数据达到可用内存的80%时，应用每一笔数据都必须同步等待
3. 每隔5s唤醒一次回刷进程
4. 内存中脏数据存在时间超过30s则在下一次唤醒时回刷
这样的配置，通过增大Cache总容量，更加频繁唤醒回刷的方式，解决IO峰值的问题，此时能保证脏数据比例保持在一个比较低的水平，当突然出现峰值，也有足够的Cache来缓存数据。
page cache 在内核中的数据结构
page cache 在内核中的数据结构是一个叫做 address_space 的结构体：struct address_space。
每个文件都会有自己的 page cache。struct address_space 结构在内存中只会保留一份。
什么意思呢？比如我们可以通过多个不同的进程打开一个相同的文件，进程每打开一个文件，内核就会为它创建 struct file 结构。这样在内核中就会有多个 struct file 结构来表示同一个文件，但是同一个文件的 page cache 也就是 struct address_space 在内核中只会有一个。
struct address_space {
struct inode *host; // 关联 page cache 对应文件的 inode
struct radix_tree_root page_tree; // 这里就是 page cache。里边缓存了文件的所有缓存页面
spinlock_t tree_lock; // 访问 page_tree 时用到的自旋锁
unsigned long nrpages; // page cache 中缓存的页面总数
..........省略..........
const struct address_space_operations *a_ops; // 定义对 page cache 中缓存页的各种操作方法
..........省略..........
}
struct inode *host ：一个文件对应一个 page cache 结构 struct address_space ，文件的 inode 描述了一个文件的所有元信息。在 struct address_space 中通过 host 指针与文件的 inode 关联。而在 inode 结构体 struct inode 中又通过 i_mapping 指针与文件的 page cache 进行关联。
struct inode {
struct address_space *i_mapping; // 关联文件的 page cache
}
struct radix_tree_root page_tree : page cache 中缓存的所有文件页全部存储在 radix_tree 这样一个高效搜索树结构当中。在文件 IO 相关的操作中，内核需要频繁大量地在 page cache 中搜索请求页是否已经缓存在页高速缓存中，所以针对 page cache 的搜索操作必须是高效的，否则引入 page cache 所带来的性能提升将会被低效的搜索开销所抵消掉。
unsigned long nrpages ：记录了当前文件对应的 page cache 缓存页面的总数。
const struct address_space_operations *a_ops ：a_ops 定义了 page cache 中所有针对缓存页的 IO 操作，提供了管理 page cache 的各种行为。比如：常用的页面读取操作 readPage() 以及页面写入操作 writePage() 等。保证了所有针对缓存页的 IO 操作必须是通过 page cache 进行的。
struct address_space_operations {
// 写入更新页面缓存
int (*writepage)(struct page *page, struct writeback_control *wbc);
// 读取页面缓存
int (*readpage)(struct file *, struct page *);
// 设置缓存页为脏页，等待后续内核回写磁盘
int (*set_page_dirty)(struct page *page);
// Direct IO 绕过 page cache 直接操作磁盘
ssize_t (*direct_IO)(struct kiocb *, struct iov_iter *iter);
........省略..........
}
前边我们提到 page cache 中缓存的不仅仅是基于文件的页，它还会缓存内存映射页，以及磁盘块设备文件，况且基于文件的内存页背后也有不同的文件系统。所以内核只是通过 a_ops 定义了操作 page cache 缓存页 IO 的通用行为定义。而具体的实现需要各个具体的文件系统通过自己定义的 address_space_operations 来描述自己如何与 page cache 进行交互。比如前边我们介绍的 ext4 文件系统就有自己的 address_space_operations 定义。
static const struct address_space_operations ext4_aops = {
.readpage = ext4_readpage,
.writepage = ext4_writepage,
.direct_IO = ext4_direct_IO,
........省略.....
};
在我们从整体上了解了 page cache 在内核中的数据结构 struct address_space 之后，我们接下来看一下 radix_tree 这个数据结构是如何支持内核来高效搜索文件页的，以及 page cache 中这些被缓存的文件页是如何组织管理的。
基树 radix_tree
正如前边我们提到的，在文件 IO 相关的操作中，内核会频繁大量地在 page cache 中查找请求页是否在页高速缓存中。还有就是当我们访问大文件时（linux 能支持大到几个 TB 的文件），page cache 中将会充斥着大量的文件页。
基于上面提到的两个原因：一个是内核对 page cache 的频繁搜索操作，另一个是 page cache 中会缓存大量的文件页。所以内核需要采用一个高效的搜索数据结构来组织管理 page cache 中的缓存页。
本小节我们就来介绍下，page cache 中用来存储缓存页的数据结构 radix_tree。
在 linux 内核 5.0 版本中 radix_tree 已被替换成 xarray 结构。感兴趣的同学可以自行了解下。
在 page cache 结构 struct address_space 中有一个类型为 struct radix_tree_root 的字段 page_tree，它表示的是 radix_tree 的根节点。
struct address_space {
struct radix_tree_root page_tree; // 这里就是 page cache。里边缓存了文件的所有缓存页面
..........省略..........
}
struct radix_tree_root {
gfp_t gfp_mask;
struct radix_tree_node __rcu *rnode; // radix_tree 根节点
};
radix_tree 中的节点类型为 struct radix_tree_node。
struct radix_tree_node {
void __rcu *slots[RADIX_TREE_MAP_SIZE]; //包含 64 个指针的数组。用于指向下一层节点或者缓存页
unsigned char offset; //父节点中指向该节点的指针在父节点 slots 数组中的偏移
unsigned char count;//记录当前节点的 slots 数组指向了多少个节点
struct radix_tree_node *parent; // 父节点指针
struct radix_tree_root *root; // 根节点
..........省略.........
unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS]; // radix_tree 中的二维标记数组，用于标记子节点的状态。
};
void __rcu *slots[RADIX_TREE_MAP_SIZE] ：radix_tree 树中的每个节点中包含一个 slots ，它是一个包含 64 个指针的数组，每个指针指向它的下一层节点或者缓存页描述符 struct page。
radix_tree 将缓存页全部存放在它的叶子结点中，所以它的叶子结点类型为 struct page。其余的节点类型为 radix_tree_node。最底层的 radix_tree_node 节点中的 slots 指向缓存页描述符 struct page。
unsigned char offset 用于表示父节点的 slots 数组中指向当前节点的指针，在父节点的slots数组中的索引。
unsigned char count 用于记录当前 radix_tree_node 的 slots 数组中指向的节点个数，因为 slots 数组中的指针有可能指向 null 。
这里大家可能已经注意到了在 struct radix_tree_node 结构中还有一个 long 型的 tags 二维数组 tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS]。那么这个二维数组到底是用来干嘛的呢？我们接着往下看
radix_tree 的标记
经过前面的介绍我们知道，页高速缓存 page cache 的引入是为了在内存中缓存磁盘的热点数据尽可能避免龟速的磁盘 IO。
而在进行文件 IO 的时候，内核会频繁大量的在 page cache 中搜索请求数据是否已经缓存在 page cache 中，如果是，内核就直接将 page cache 中的数据拷贝到用户缓冲区中。从而避免了一次磁盘 IO。
这就要求内核需要采用一种支持高效搜索的数据结构来组织管理这些缓存页，所以引入了基树 radix_tree。
到目前为止，我们还没有涉及到缓存页的状态，不过在文章的后面我们很快就会涉及到，这里提前给大家引出来，让大家脑海里先有个概念。
那么什么是缓存页的状态呢？
我们知道在 Buffered IO 模式下，对于文件 IO 的操作都是需要经过 page cache 的，后面我们即将要介绍的 write 系统调用就会将数据直接写到 page cache 中，并将该缓存页标记为脏页（PG_dirty）直接返回，随后内核会根据一定的规则来将这些脏页回写到磁盘中，在会写的过程中这些脏页又会被标记为 PG_writeback，表示该页正在被回写到磁盘。
PG_dirty 和 PG_writeback 就是缓存页的状态，而内核不仅仅是需要在 page cache 中高效搜索请求数据所在的缓存页，还需要高效搜索给定状态的缓存页。
比如：快速查找 page cache 中的所有脏页。但是如果此时 page cache 中的大部分缓存页都不是脏页，那么顺序遍历 radix_tree 的方式就实在是太慢了，所以为了快速搜索到脏页，就需要在 radix_tree 中的每个节点 radix_tree_node
中加入一个针对其所有子节点的脏页标记，如果其中一个子节点被标记被脏时，那么这个子节点对应的父节点 radix_tree_node 结构中的对应脏页标记位就会被置 1 。
而用来存储脏页标记的正是上小节中提到的 tags 二维数组。其中第一维 tags[] 用来表示标记类型，有多少标记类型，数组大小就为多少，比如 tags[0] 表示 PG_dirty 标记数组，tags[1] 表示 PG_writeback 标记数组。
第二维 tags[][] 数组则表示对应标记类型针对每一个子节点的标记位，因为一个 radix_tree_node 节点中包含 64 个指针指向对应的子节点，所以二维 tags[][] 数组的大小也为 64 ，数组中的每一位表示对应子节点的标记。tags[0][0] 指向 PG_dirty 标记数组，tags[1][0] 指向PG_writeback 标记数组。
而缓存页（ radix_tree 中的叶子结点）这些标记是存放在其对应的页描述符 struct page 里的 flag 中。
struct page {
unsigned long flags;
}
只要一个缓存页（叶子结点）被标记，那么从这个叶子结点一直到 radix_tree 根节点的路径将会全部被标记。这就好比你在一盆清水中滴入一滴墨水，不久之后整盆水就会变为黑色。
这样内核在 radix_tree 中搜索被标记的脏页（PG_dirty）或者正在回写的页（PG_writeback）时，就可以迅速跳过哪些标记为 0 的中间节点的所有子树，中间节点对应的标记为 0 说明其所有的子树中包含的缓存页（叶子结点）都是干净的（未标记）。从而达到在 radix_tree 中迅速搜索指定状态的缓存页的目的。
page cache 中查找缓存页
在我们明白了 radix_tree 这个数据结构之后，接下来我们来看一下在内核如何通过 find_get_page 在 page cache 中高效查找缓存页？
在介绍 find_get_page 之前，笔者先来带大家看看 radix_tree 具体是如何组织和管理其中的缓存页 page 的。
经过上小节相关内容的介绍，我们了解到在 radix_tree 中每个节点 radix_tree_node 包含一个大小为 64 的指针数组 slots 用于指向它的子节点或者缓存页描述符（叶子节点）。
一个 radix_tree_node 节点下边最多可容纳 64 个子节点，如果 radix_tree 的深度为 1 （不包括叶子节点），那么这颗 radix_tree 就可以缓存 64 个文件页。而每页大小为 4k，所以一颗深度为 1 的 radix_tree 可以缓存 256k 的文件内容。
而如果一颗 radix_tree 的深度为 2，那么它就可以缓存 64 * 64 = 4096 个文件页，总共可以缓存 16M 的文件内容。
依次类推我们可以得到不同的 radix_tree 深度可以缓存多大的文件内容：
| radix_tree 深度 | page 最大索引值 | 缓存文件大小 |
|---|---|---|
| 1 | 2^6 - 1 = 63 | 256K |
| 2 | 2^12 - 1 = 4095 | 16M |
| 3 | 2^18 - 1 = 262143 | 1G |
| 4 | 2^24 -1 =16777215 | 64G |
| 5 | 2^30 - 1 | 4T |
| 6 | 2^36 - 1 | 64T |
通过以上内容的介绍，我们看到在 radix_tree 是根据缓存页的 index （索引）来组织管理缓存页的，内核会根据这个 index 迅速找到对应的缓存页。在缓存页描述符 struct page 结构中保存了其在 page cache 中的索引 index。
struct page {
unsigned long flags; //缓存页标记
struct address_space *mapping; // 缓存页所在的 page cache
unsigned long index; // 页索引
...
}
事实上 find_get_page 函数也是根据缓存页描述符中的这个 index 来在 page cache 中高效查找对应的缓存页。
static inline struct page *find_get_page(struct address_space *mapping,
pgoff_t offset)
{
return pagecache_get_page(mapping, offset, 0, 0);
}
- struct address_space *mapping : 为读取文件对应的 page cache 页高速缓存。
- pgoff_t offset ： 为所请求的缓存页在 page cache 中的索引 index，类型为 long 型。
那么在内核是如何利用这个 long 型的 offset 在 page cache 中高效搜索指定的缓存页呢？
经过前边我们对 radix_tree 结构的介绍，我们已经知道 radix_tree 中每个节点 radix_tree_node 包含一个大小为 64 的指针数组 slots 用于指向它的子节点或者缓存页描述符。
一个 radix_tree_node 节点下边最多可容纳 64 个子节点，如果 radix_tree 的深度为 1 （不包括叶子节点），那么这颗 radix_tree 就可以缓存 64 个文件页。只能表示 0 - 63 的索引范围，所以 long 型的缓存页 offset 的低 6 位可以表示这个范围，对应于第一层 radix_tree_node 节点的 slots 数组下标。
如果一颗 radix_tree 的深度为 2（不包括叶子节点），那么它就可以缓存 64 * 64 = 4096 个文件页，表示的索引范围为 0 - 4095，在这种情况下，缓存页索引 offset 的低 12 位可以分成 两个 6 位的字段，高位的字段用来表示第一层节点的 slots 数组的下标，低位字段用于表示第二层节点的 slots 数组下标。
依次类推，如果 radix_tree 的深度为 6 那么它可以缓存 64T 的文件页，表示的索引范围为：0 到 2^36 - 1。 缓存页索引 offset 的低 36 位可以分成 六 个 6 位的字段。缓存页索引的最高位字段来表示 radix_tree 中的第一层节点中的 slots 数组下标，接下来的 6 位字段表示第二层节点中的 slots 数组下标，这样一直到最低的 6 位字段表示第 6 层节点中的 slots 数组下标。
通过以上根据缓存页索引 offset 的查找过程，我们看出内核在 page cache 查找缓存页的时间复杂度和 radix_tree 的深度有关。
在我们理解了内核在 radix_tree 中的查找缓存页逻辑之后，再来看 find_get_page 的代码实现就变得很简单了
struct page *pagecache_get_page(struct address_space *mapping, pgoff_t offset,
int fgp_flags, gfp_t gfp_mask)
{
struct page *page;
repeat:
// 在 radix_tree 中根据 缓存页 offset 查找缓存页
page = find_get_entry(mapping, offset);
// 缓存页不存在的话，跳转到 no_page 处理逻辑
if (!page)
goto no_page;
.......省略.......
no_page:
if (!page && (fgp_flags & FGP_CREAT)) {
// 分配新页
page = __page_cache_alloc(gfp_mask);
if (!page)
return NULL;
if (fgp_flags & FGP_ACCESSED)
//增加页的引用计数
__SetPageReferenced(page);
// 将新分配的内存页加入到页高速缓存 page cache 中
err = add_to_page_cache_lru(page, mapping, offset, gfp_mask);
.......省略.......
}
return page;
}
}
内核首先调用 find_get_entry 方法根据缓存页的 offset 到 page cache 中去查找看请求的文件页是否已经在页高速缓存中。如果存在直接返回。
如果请求的文件页不在 page cache 中，内核则会首先会在物理内存中分配一个内存页，然后将新分配的内存页加入到 page cache 中，并增加页引用计数。
随后会通过 address_space_operations 重定义的 readpage 激活块设备驱动从磁盘中读取请求数据，然后用读取到的数据填充新分配的内存页。
static const struct address_space_operations ext4_aops = {
.readpage = ext4_readpage,
.writepage = ext4_writepage,
.direct_IO = ext4_direct_IO,
........省略.....
};
