文件读写(1)--页面缓冲(PageCache)的管理

文件读写(1)-- 页面缓冲 (Page Cache) 的管理

R.wen

一、本文分析文件的读写过程。当用户进程发出一个 read() 系统调用时，它首先通过 VFS 从 disk cache 中去查找相应的文件块有没有已经被缓存起来，如果有，则不需要再次从设备中去读，直接从 CACHE 中去拷贝给用户缓冲区就可以了，否则它就要先分配一个缓冲页面，并且将其加入到对应的 inode 节点的 address_space 中，再调用 address_space 的 readpage() 函数，通过 submit_bio() 向设备发送一个请求，将所需的文件块从设备中读取出来存放在先前分配的缓冲页面中，最后再从该页面中将所需数据拷贝到用户缓冲区。

图 1

二、页面缓冲 (Page Cache) 的管理

页面缓冲的核心数据结构是 struct address_space ：

struct backing_dev_info;

struct address_space {

       struct inode           *host;            /* owner: inode, block_device */

       struct radix_tree_root    page_tree;       /* radix tree of all pages */

       rwlock_t        tree_lock;       /* and rwlock protecting it */

       unsigned int           i_mmap_writable;/* count VM_SHARED mappings */

       struct prio_tree_root      i_mmap;         /* tree of private and shared mappings */

       struct list_head       i_mmap_nonlinear;/*list VM_NONLINEAR mappings */

       spinlock_t              i_mmap_lock; /* protect tree, count, list */

       unsigned int           truncate_count;      /* Cover race condition with truncate */

       unsigned long         nrpages; /* number of total pages */

       pgoff_t                  writeback_index;/* writeback starts here */

       const struct address_space_operations *a_ops;   /* methods */

       unsigned long         flags;             /* error bits/gfp mask */

       struct backing_dev_info *backing_dev_info; /* device readahead, etc */

       spinlock_t              private_lock;   /* for use by the address_space */

       struct list_head       private_list;     /* ditto */

       struct address_space     *assoc_mapping;    /* ditto */

} __attribute__((aligned(sizeof(long))));

如下图 2 ，缓冲页面的是通过一个基数树（ Radix Tree ）来管理的，这是一个简单但非常高效的树结构。

图 2

由图 2 可以看到，当 RADIX_TREE_MAP_SHIFT 为 6 （即每个节点有 2^6 ＝ 64 个 slot ）且树高是 1 时，它可以寻址大小为 64 个页面（ 256kb ）的文件，同样，当树高为 2 时，它可以寻址 64*64 个页面 (16M) 大小的文件，如此下去，在 32 位的系统中，树高为 6 级，（最高级只有 2 位： 32-6*5 ），所以它可以寻址 2^32-1 个页面大小的文件，约为 16TB 大小，所以目前来说已经足够了。

基数树的遍历也是很简单，且类似于虚拟线性地址的转换过程。只要给定树根及文件偏移，就可以找到相应的缓存页面。再如图 2 右，如果在文件中的偏移为 131 个页面，这个偏移值的高 6 位就是第一级偏移，而低 6 位就是在第二级的偏移，依此类推。如对于偏移值 131(10000011) ，高 6 位值是 131>>6 = 2 ，所以它在第一级的偏移是 2 ，而在第 2 级的领衔就是低 6 位，值为 3 ，即偏移为 3 ，所以得到的结果如图 2 右方所示。

#define RADIX_TREE_MAP_SHIFT   (CONFIG_BASE_SMALL ? 4 : 6)

#define RADIX_TREE_MAP_SIZE      (1UL <

#define RADIX_TREE_MAX_TAGS 2

#define RADIX_TREE_TAG_LONGS /    // 其值为 64

       ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)

struct radix_tree_node {

       unsigned int    height;            /* Height from the bottom */

       unsigned int    count;

       struct rcu_head      rcu_head;

       void        *slots[RADIX_TREE_MAP_SIZE];

       unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];

};

struct radix_tree_path {

       struct radix_tree_node *node;

       int offset;

};

struct radix_tree_node {

       unsigned int    height;            /* Height from the bottom */

       unsigned int    count;

       struct rcu_head      rcu_head;

       void        *slots[RADIX_TREE_MAP_SIZE];

       unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];

};

以上是相关的几个数据结构，第一个为树根结点结构，第二个用于路径查找，第三个就是树的节点结构。

注意节点结构中的 tags 域，这个一个典型的用空间换时间的应用。它是一个二维数组，用于记录该节点下面的子节点有没有相应的标志。目前 RADIX_TREE_MAX_TAGS 为 2 ，表示只记录两个标志，其中 tags[0] 为 PAGE_CACHE_DIRTY ， tags[1] 为 PAGE_CACHE_WRITEBACK 。它表示，如果当前节点的 tags[0] 值为 1 ，那么它的子树节点就存在 PAGE_CACHE_DIRTY 节点，否则这个子树分枝就不存在着这样的节点，就不必再查找这个子树了。比如在查找 PG_dirty 的页面时，就不需要遍历整个树，而可以跳过那些 tags[0] 为 0 值的子树，这样就提高了查找效率。