Chinaunix首页 | 论坛 | 博客
  • 博客访问: 443534
  • 博文数量: 184
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 594
  • 用 户 组: 普通用户
  • 注册时间: 2013-12-17 16:24
个人简介

我是一只小小鸟

文章分类

全部博文(184)

文章存档

2016年(1)

2015年(55)

2014年(127)

2013年(1)

分类: LINUX

2014-05-21 10:40:09

原文地址:address_space与基树 作者:steven_miao

address_space与基树

address_space结构体,是页高速缓存(page cache)的核心数据结构。在很多时候,内核在读写磁盘时都引用页高速缓存,新页被追加到页高速缓存以满足用户态进程的读请求。如果页不在高速缓存中,新页就被追加到高速缓存。这样作的目的就是为了更快的效率,比如有一些页,经常被访问,那么此时,如果内存空间允许的话,可以考虑让它们长期驻留在页高速缓存中,这样要比从磁盘访问它们效率更高。而address_space结构体就是嵌入在页所有者的索引节点对象中的数据结构。而页描述符与它的联系是通过其中的字段mapping和index来完成的。前者指向拥有页的索引节点的address_space对象,index字段表示在所有者的地址空间中以页大小为单位的偏移量,即在所有者的磁盘映像中页中数据的位置。在页高速缓存中查找页时使用这两个字段。

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 spinlock 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 */
        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))));

比如页高速缓存中页的拥有者是一个文件的时候,那么此时索引节点的i_mapping字段总是指向索引节点的数据页所有者的address_space.而address_space对象就嵌入在VFS索引节点对象的i_data字段中。而address_space中的字段host则指向它所有者的索引节点对象。而其中的a_ops则是操作所有者页的方法。

struct address_space_operations {
        int (*writepage)(struct page *page, struct writeback_control *wbc);
        int (*readpage)(struct file *, struct page *);
        int (*sync_page)(struct page *);
        int (*writepages)(struct address_space *, struct writeback_control *);
        int (*set_page_dirty)(struct page *page);
        int (*readpages)(struct file *filp, struct address_space *mapping,struct list_head *pages, unsigned nr_pages);
        int (*prepare_write)(struct file *, struct page *, unsigned, unsigned);
        int (*commit_write)(struct file *, struct page *, unsigned, unsigned);
        sector_t (*bmap)(struct address_space *, sector_t);
        int (*invalidatepage) (struct page *, unsigned long);
        int (*releasepage) (struct page *, int);
        ssize_t (*direct_IO)(int, struct kiocb *, const struct iovec *iov,loff_t offset, unsigned long nr_segs);
};

而页高速缓存如果页数太多,而只用顺序查找的方式,那效率一定是低下的,此时就用了一个搜索树方式,其中每个address_space都对应一颗搜索树。而结构体中字段page_tree对应的就是基树的根:

struct radix_tree_root {
        unsigned int            height;
        int                     gfp_mask;
        struct radix_tree_node  *rnode;
};

struct radix_tree_node {
        unsigned int    count;
        void            *slots[RADIX_TREE_MAP_SIZE];
        unsigned long   tags[RADIX_TREE_TAGS][RADIX_TREE_TAG_LONGS];
};

根结构中的radix_tree_node对应的是树的一个节点。

#ifdef __KERNEL__
#define RADIX_TREE_MAP_SHIFT    6
#else
#define RADIX_TREE_MAP_SHIFT    3       /* For more stressful testing */
#endif
#define RADIX_TREE_TAGS         2

#define RADIX_TREE_MAP_SIZE     (1UL << RADIX_TREE_MAP_SHIFT)
#define RADIX_TREE_MAP_MASK     (RADIX_TREE_MAP_SIZE-1)

#define RADIX_TREE_TAG_LONGS    \
        ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)

在节点的结构中,包含指向所有者的页描述符的指针,其中的slot元素就是这个作用。这是一个指针数组。而count是记录节点中非空指针数量的计数器。而根结构体中的height是记录当前树的高度。gfp_mask是为新节点申请内存时的标志。*rnode指向与树第一层节点相应的数据结构。之所以这样是因为当索引页超过64个的时候,那么一个节点已经无法容纳,此时当前节点就作为树的一个节点,下面链接64个节点,在这64个节点之下,每个节点再联系相应的page.以这样的方式来组成一棵树。而给定的页索引表示页在所有者磁盘映像中的位置。内核可以通过快速搜索操作来确定所需要的页是否在页高速缓存中。当找到的时候,内核把页索引转换为基数的路经,找到页描述符所在的位置。

而通过基树的查找到底是如何进行的呢?比如现在有一个第二层节点下的page,如果从根开始找,那么就要先找到page所在的第二层节点,而第二层节点对应的是第一层节点的一个数组下标。那么方法就是当只有一层的时候,那么数组下标就是所需要的page.也就是页索引的低6位是需要的slot的数组下标。可是当拥有两层的时候,那么页索引的低12位分成两部分,高位是找到page所在的节点在上层节点中的slot数组下标。而低位部分则是第二层节点的slot数组下标,如此就可以通过两次找到page.当是6层的时候,页索引的最高两位表示第一层节点数组的下标,接下来的6位表示第二层节点数组的下标,这样一直到最低的6位,他们表示第六层节点数组的下标。以上就是基树搜索的思想。

而关于页高速缓存的还有几个常用处理函数:查找页,增加页,删除页更新页。

struct page * find_get_page(struct address_space *mapping, unsigned long offset)
unsigned find_get_pages(struct address_space *mapping, pgoff_t start,unsigned int nr_pages, struct page **pages)
struct page *find_lock_page(struct address_space *mapping,unsigned long offset)
struct page *find_trylock_page(struct address_space *mapping, unsigned long offset)
struct page *find_or_create_page(struct address_space *mapping,unsigned long index, unsigned int gfp_mask)
int add_to_page_cache(struct page *page, struct address_space *mapping,pgoff_t offset, int gfp_mask)
remove_from_page_cache(struct page *page)

以上就是查找页相关的函数。查找一个页面使用的就是上面所言的搜索树方式。几个函数也大同小异。

struct page * find_get_page(struct address_space *mapping, unsigned long offset)
{
        struct page *page;
        spin_lock_irq(&mapping->tree_lock);
        page = radix_tree_lookup(&mapping->page_tree, offset);
        if (page)
                page_cache_get(page);
        spin_unlock_irq(&mapping->tree_lock);
        return page;
}

void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
{
        unsigned int height, shift;
        struct radix_tree_node **slot;
        height = root->height;
        if (index > radix_tree_maxindex(height))
                return NULL;
        shift = (height-1) * RADIX_TREE_MAP_SHIFT;
        slot = &root->rnode;
        while (height > 0) {
                if (*slot == NULL)
                        return NULL;
                slot = (struct radix_tree_node **)((*slot)->slots + ((index >> shift) & RADIX_TREE_MAP_MASK));
                shift -= RADIX_TREE_MAP_SHIFT;
                height--;
        }

        return *slot;
}

在此函数中,重点是依靠radix_tree_lookup函数来完成的,他的目的找到一个页。他的两个参数也是address_space对象和偏移量。在radix函数中,首先就是要验证索引是否大于树的深度,如果大于,那么肯定找不到目标页。函数中的shift始终是一个重点,因为他决定了每次找寻的步移。slot是记录节点下面各个元素的。从根开始。逐步按照层次推进寻找。(*slot)->slots + ((index >> shift) & RADIX_TREE_MAP_MASK)这段就是上面谈到的,找到在节点上的page,也就是page所对应节点的slot数组下标。而find_get_pages函数则是实现在高速缓存中查找一组具有相邻索引的页。比如函数中多出的几个参数:start(地址空间中相对于搜索起始位置的偏移量),nr_pages(所检索到页的最大数量),**pages(指向该函数赋值的页描述符数组的指针)。在函数中,那个for循环体中的ret,就是找到的页数。而具体实现过程,则是依靠函数radix_tree_gang_lookup来完成的。函数很简单。作用就是实现在高速缓存中查找一组具有相邻索引的页。

unsigned find_get_pages(struct address_space *mapping, pgoff_t start,unsigned int nr_pages, struct page **pages)
{
        unsigned int i;
        unsigned int ret;
        spin_lock_irq(&mapping->tree_lock);
        ret = radix_tree_gang_lookup(&mapping->page_tree,(void **)pages, start, nr_pages);
        for (i = 0; i < ret; i++)
                page_cache_get(pages[i]);
        spin_unlock_irq(&mapping->tree_lock);
        return ret;
}

unsigned int radix_tree_gang_lookup(struct radix_tree_root *root, void **results,unsigned long first_index, unsigned int max_items)
{
        const unsigned long max_index = radix_tree_maxindex(root->height);
        unsigned long cur_index = first_index;
        unsigned int ret = 0;
        while (ret < max_items) {
                unsigned int nr_found;
                unsigned long next_index;       /* Index of next search */
                if (cur_index > max_index)
                        break;
                nr_found = __lookup(root, results + ret, cur_index,max_items - ret, &next_index);
                ret += nr_found;
                if (next_index == 0)
                        break;
                cur_index = next_index;
        }
        return ret;
}

除了上面两个函数外,还有关于增加页的函数,这个函数的目的是把一个新页的描述符插入到页高速缓存。其中的参数page是页描述符地址、mapping是address_space对象的地址、offset是在地址空间内的页索引的值,gfp_mask是为基数分配新节点时所使用的内存分配标志.

int add_to_page_cache(struct page *page, struct address_space *mapping,pgoff_t offset, int gfp_mask)
{
        int error = radix_tree_preload(gfp_mask & ~__GFP_HIGHMEM);
        if (error == 0) {
                spin_lock_irq(&mapping->tree_lock);
                error = radix_tree_insert(&mapping->page_tree, offset, page);
                if (!error) {
                        page_cache_get(page);
                        SetPageLocked(page);
                        page->mapping = mapping;
                        page->index = offset;
                        mapping->nrpages++;
                        pagecache_acct(1);
                }
                spin_unlock_irq(&mapping->tree_lock);
                radix_tree_preload_end();
        }
        return error;
}

在radix_tree_preload函数中,关键的一句是:node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);其中这个node结构就是struct radix_tree_node *node类型。这个函数以前谈过是高速缓存申请函数。是slab分配器中的,分陪的是slab对象。再返回函数add_to_page_cache,如果分配成功,则就要插入这个节点。radix_tree_insert函数的作用就是。他的三个参数的功能就是传入插入点,插入对象,以及offset.在这个函数中,首先是判断的是如果可以插入到当前深度,那么就插入,否则在去寻找定位。

if ((!index && !root->rnode) || index > radix_tree_maxindex(root->height)) {
                error = radix_tree_extend(root, index);
                if (error)
                        return error;
        }

其中的函数radix_tree_maxindex的作用就是获得最大索引,这个判断的目的就在于,如果当前节点超过了树本身具有的深度,那么就要再加一层。函数radix_tree_extend的作用就是通过增加适当数量的节点来增加树的深度。如果这步不存在,那么就按部就班的进行:

        slot = &root->rnode;
        height = root->height;
        shift = (height-1) * RADIX_TREE_MAP_SHIFT;
        offset = 0; 

在循环体中,从根节点开始遍历,直到最深的一层。如果根节点的slot为null,那么就要申请一个,在radix_tree_node_alloc函数中,重要的一句就是:ret = kmem_cache_alloc(radix_tree_node_cachep, root->gfp_mask);在循环体后面就是将页找到适当的位置。然后返回0.

        while (height > 0) {
                if (*slot == NULL) {
                        if (!(tmp = radix_tree_node_alloc(root)))
                                return -ENOMEM;
                        *slot = tmp;
                        if (node)
                                node->count++;
                }

                offset = (index >> shift) & RADIX_TREE_MAP_MASK;
                node = *slot;
                slot = (struct radix_tree_node **)(node->slots + offset);
                shift -= RADIX_TREE_MAP_SHIFT;
                height--;
        }

如果函数成功返回0,那么在add_to_page_cache函数中,就开始设置。然后调用radix_tree_preload_end()。重新启用内核抢占。

if (!error) {
                  page_cache_get(page);
                  SetPageLocked(page);
                  page->mapping = mapping;
                  page->index = offset;
                  mapping->nrpages++;
                  pagecache_acct(1);
            }

删除页的函数,remove_from_page_cache的作用就是从高速缓存中删除页描述符。可见最后落实的函数是radix_tree_delete.

void __remove_from_page_cache(struct page *page)
{
        struct address_space *mapping = page->mapping;

        radix_tree_delete(&mapping->page_tree, page->index);
        page->mapping = NULL;
        mapping->nrpages--;
        pagecache_acct(-1);
}

void remove_from_page_cache(struct page *page)
{
        struct address_space *mapping = page->mapping;
        if (unlikely(!PageLocked(page)))
                PAGE_BUG(page);
        spin_lock_irq(&mapping->tree_lock);
        __remove_from_page_cache(page);
        spin_unlock_irq(&mapping->tree_lock);
}
阅读(554) | 评论(0) | 转发(0) |
0

上一篇:memory.c

下一篇:linux内核之页高速缓存

给主人留下些什么吧!~~