pagecache

页高速缓存引入
1、快速定位含有给定所有者相关数据的特定页；
2、记录在读或写页中的数据时应当如何处理高速缓存中的的每个页。

页高速缓存的核心数据结构是address_space对象。这是一个嵌入在页所有者的索引节点对象中的数据结构。
struct address_space {
    struct inode        *host;        /* owner: inode, block_device */
    struct radix_tree_root    page_tree;    /* radix tree of all pages */
    spinlock_t        tree_lock;    /* and lock 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))));
在linux中，通常会支持大到几个TB的文件，而对于这样的文件，当进行文件访问时，页高速缓存中可能充满了
很多的文件页，这样如果要进行顺序扫描，就会消耗掉大量的时间，linux在address_space中引入了一棵搜索树。
其中，page_tree字段是基树的根，下面是page_stree字段对应结构体的定义：
struct radix_tree_root {
    unsigned int         height;
    gfp_t            gfp_mask;
    struct radix_tree_node    *rnode;
};
struct radix_tree_node {
    unsigned int     height;
    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];
};
RADIX_TREE_MAP_SIZE    =    64;
RADIX_TREE_MAX_TAGS    =     2;
RADIX_TREE_TAG_LONGS    =     8;
page_stree字段指向所有者的页描述符号指针。这包含指向所有的页描述符的指针，给定的页索引表示页在所有者
磁盘影像中的位置。内核可以通过快速搜索来确定所需要的页是否在页高速缓存中。如果要查找所需要的页，内核将页
索引转换成基树中的路径，并快速找到页描述符所在的位置。如果找到了，内核可以从基树获得页描述符，而且可以
很快确定所找到的页是否是脏页，以及其数据的I/O传送的是否正在进行。

根据radix_tree_node的定义，会发现，基树中的每个节点可以有多到64个指针指向其他节点或页描述符。底层节点
存放指向页描述符的指针，上层的节点存放指向其他节点的指针。radix_tree_node中的slots字段指的即是这64个
指针的数组，count是记录节点中非空指针数量的计数器，tags是二维的标志数组。每一棵基树的根均由radix_tree_root
数据结构表示：height表示树的深度，gfp_mask表示新节点请求内存时所使用的标志，rnode指向与树中第一层节点
相应的数据结构radix_tree_node。基树节点中的tags数组作为基树的标记字段。
由于页索引仅仅放在32位变量中的缘故，当深度为6时，最高层的节点最多可以有4个孩子节点，实现如下：
如果深度为1，那么页索引只需要使用最低6位即可；如果深度为2，那么需要页索引的最低12位，其中高6位为第一层的
索引，低6位为第二层的索引...如此下去，就可以搜索完6层的基树，其中最高的那一层只能使用4个节点。

页高速缓存的处理函数
find_get_page    /* 已知address_space地址， 通过已给offset找出对应的page*/
/**
 * find_get_page - find and get a page reference
 * @mapping: the address_space to search
 * @offset: the page index
 *
 * Is there a pagecache struct page at the given (mapping, offset) tuple?
 * If yes, increment its refcount and return it; if no, return NULL.
 */
struct page *find_get_page(struct address_space *mapping, pgoff_t offset)
{
    void **pagep;
    struct page *page;

    rcu_read_lock();
repeat:
    page = NULL;
    pagep = radix_tree_lookup_slot(&mapping->page_tree, offset);
    /* 由基树的根，通过索引值offset得到相应的页 */
    if (pagep) {
        page = radix_tree_deref_slot(pagep);
        if (unlikely(!page || page == RADIX_TREE_RETRY))
            goto repeat;

        if (!page_cache_get_speculative(page))
            goto repeat;

        /*
         * Has the page moved?
         * This is part of the lockless pagecache protocol. See
         * include/linux/pagemap.h for details.
         */
        if (unlikely(page != *pagep)) {
            page_cache_release(page);
            goto repeat;
        }
    }
    rcu_read_unlock();

    return page;
}
radix_tree_lookup_slot的实现
/**
 *    radix_tree_lookup_slot    -    lookup a slot in a radix tree
 *    @root:        radix tree root
 *    @index:        index key
 *
 *    Returns:  the slot corresponding to the position @index in the
 *    radix tree @root. This is useful for update-if-exists operations.
 *
 *    This function can be called under rcu_read_lock iff the slot is not
 *    modified by radix_tree_replace_slot, otherwise it must be called
 *    exclusive from other writers. Any dereference of the slot must be done
 *    using radix_tree_deref_slot.
 */
void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
{
    unsigned int height, shift;
    struct radix_tree_node *node, **slot;
    ...
    node = radix_tree_indirect_to_ptr(node);
    /* 得到对应的树根节点 */
    height = node->height;
    /* 提取基树深度 */
    if (index > radix_tree_maxindex(height))
        return NULL;
    /* 超过最大深度则返回NULL */

    shift = (height-1) * RADIX_TREE_MAP_SHIFT;
    /* 计算左移值，由于基树的搜索是由高层向底层逐层解析搜索，所以shift的计算是关键 */

    do {
        slot = (struct radix_tree_node **)
            (node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK));
        /* 搜索当前基树层，通过左移获得准确的slot值 */
        node = rcu_dereference(*slot);
        if (node == NULL)
            return NULL;

        shift -= RADIX_TREE_MAP_SHIFT;
        /* 左移值减RADIX_TREE_MAP_SHIFT(值的确定与系统结构有关) */
        height--;
        /* 搜索完一层，深度减少1 */
    } while (height > 0);

    return (void **)slot;
    /* 最终返回寻找到的slot */
}

向基树中增加页
static inline int add_to_page_cache(struct page *page, struct address_space *mapping,
                pgoff_t offset, gfp_t gfp_mask)
{
    int error;
    __set_page_locked(page);
    /* 为page设置PG_locked，防止其他内核路径并发访问该页 */
    error = add_to_page_cache_locked(page, mapping, offset, gfp_mask);
    /* 向页高速缓存增加一个页，成功返回0 */
    if (unlikely(error)) {
        __clear_page_locked(page);
    }
    return error;
}

从基树中删除页
remove_from_page_cache(struct page *page);

参考：《Understanding The Linux Kernel》