注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Tsecer的回音岛

Tsecer的博客

 
 
 

日志

 
 

页面反向映射之匿名页面  

2013-11-10 18:53:20|  分类: Linux内核 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

一、基础数据结构及面临的问题
页面结构struct page对于反向映射的实现使用了两个成员:
一个是表示映射挂靠位置的内核级唯一结构。对于匿名映射来说,这个结构为一个全局的anon_vma结构;对于文件映射结构来说,这个指针指向的是一个表示地址空间的address_space结构,这个结构也就是我们通常在struct inode 结构中看到的struct address_space    *i_mapping;变量
另一个变量是相对于基础位置的页面偏移量位置,也就是page结构的
pgoff_t index;            /* Our offset within mapping. */
成员。
简单来说,这是一个非常直观的 addr + len的定界类型。只是这个addr表示的不是开始地址,而是一个逻辑结构地址,len则表示页面在一个地址空间内部的相对页面偏移量。
对于文件映射来说,这个address_space依赖于inode,inode的唯一性决定了这个结构地址的唯一性,所以所有映射到该文件的页面映射都有一个相同的落脚点;反过来说,匿名映射页面正如它们名字显示的一样,它们是“匿名的”,没有名正言顺的挂靠点。此时系统就需要为page所在的匿名映射所在的vma结构分配一个落脚点,或者说挂靠点,这个挂靠点是凭空创造而不是自然而然形成的,这个结构之后所要讨论的anon_vma结构。
从struct page的角度来看,一个页面它只有两个元素可以依靠,用来枚举所有映射了自己的vma结构。
其中的mapping指向的是一个链表头结构,一旦确定,不论vma的状态如何变化,此时page结构中指向的内容都不会随着vma的变化而变化,这也是这个中间anon_vma的意义,就是为了避免vma的频繁变化对page的影响。系统中vma结构的变化是非常的频繁和没有规律的,这些vma结构的变化包括了vma的创建(mmap创建),vma的复制(fork后dup_mm),vma的删除(进程退出),vma的合并(mprotect改变区间属性或者添加新的vma导致具有相同属性,原本间隔的vma可以连成一片)、vma的拆分(通过mprotect改变属性导致vma分裂)等,而page只管指向自己的anon_vam结构,任尔东南西北风。同时,page中index指向的位置在初始化之后也不会变化。此时如何保持vma尽可能自由合并同时保证通过在page结构内容不变的情况下可以通过page结构找到该页面所在的所有区间就是一个棘手的问题了。
二、vma复制
这种情况通常发生在进程fork时,在fork之后,子进程会复制父进程所有的vma,这就包括了父vma结构的anon_vma地址,或者说新创建的vma结构和父vma具在同一个anon_vma变量引导的队列链表中。由于页面反向映射的时候会遍历这个链表中的所有成员,所以在复制之后,通过page页面的两个变量查找所有使用了该页面的内核vma结构时可以遍历到该vma结构。这一点是我们预期和系统的效果,相当于一个页面被另一个额外的vma映射。
这是最为简单的一种情况,此时是一个等值复制,只需要将先创建的vma添加到原始vma所在的链表即可,用常见的术语来说,这个是一个identity 复制,或者说trivia复制。
二、vma的拆分
1、拆分时vma侧对anon_vma的处理
这种情况发生在刚开始一个大片的连续地址空间,它们在进程的地址空间中通过一个vma表示,这个vma中映射的页面结构通过自己的mapping指向了一个anon_vma结构,index指向了该页面在此vma结构中页面单位偏移量。然后通过mprotect在地址空间中见进行一次额外的拆分,此时一个vma将会被分割成三份,使用数字表示为
假设说从0x10000开始到0x0x1C000共三个页面,它们开始创建时全部为可读可写地址空间,并且地址空间中的页面地址均已经被分配,三个page结构的mapping指向同一个anon_vma,它们内部的index分别为0,1,2。然后通过mprotet将0x14000到0x18000地址空间的一个页面设置为只读属性,由于中间的页面属性不同,vma结构需要分裂为三个vma结构。
对于anon_vma结构来说,我们并不能指望通过它来知道所有指向该anon_vma结构的所有page结构,不可能通过anon_vma结构来找到三个page页面,进而修正这些页面结构的mapping和index成员,vma的这种变化对于page来说是透明的,但需要保证vma分裂之后page结构通过之前的anon_vma依然可以找到各自所在的vma区域。
采用的办法也比较直观,对于新分裂的每一个vma结构,它并不创建自己的anon_vma结构,而是全部共享(继承)原始vma的anon_vma结构。它无法创建自己的anon_vma结构的原因在于page结构中的mapping指向的是原始anon_vma结构,page只会通过原始anon_vma来查找所有映射了自己的vma,没有办法通知page改变mapping指向。
到这一步已经可以看,对于一个page结构来说,通过它的mapping-->>anon_vma遍历链表中所有的vma结构时,不能保证page在链表中的每一个vma区间中,例如对于前面所说的vma分裂的情况,分裂之后,anon_vma链表中的一个vma分裂为三个,均放在原始链表中,而它们对应的三个页面只在其中的一个vma结构中。
2、拆分后page侧处理
那么page在遍历自己指向的anon_vma链表时,如何确定自己是否在该节点所表示的vma结构中呢(vma分裂时,page的mapping和index均未变化的情况下)?
对于一个vma来说,它不仅有自己的起始地址和结束地址,还有一个vm_pgoff成员,在计算一个页面在进程地址空间的时候,此时执行的是下面的vma_address函数
/*
 * At what user virtual address is page expected in vma?
 */
static inline unsigned long
vma_address(struct page *page, struct vm_area_struct *vma)
{
    pgoff_t pgoff = page->index << (PAGE_CACHE_SHIFT - PAGE_SHIFT);page中保存的页面偏移量,页面被映射时保存,分裂时不变
    unsigned long address;

    address = vma->vm_start + ((pgoff - vma->vm_pgoff) << PAGE_SHIFT);//同时参考vm_start地址和vm_pgoff变量
    if (unlikely(address < vma->vm_start || address >= vma->vm_end)) {
        /* page should be within any vma from prio_tree_next */
        BUG_ON(!PageAnon(page));
        return -EFAULT;
    }
    return address;
}
可以看到,它不是简单的通过vma的start地址加上page的index地址计算页面在进程的地址空间中的位置,同时还考虑了vma中的vm_pgoff字段。当vm_start地址变化时,vma结构中的vm_pgoff字段也会同步变化,所以在vma结构分裂之后,如果保证vm_start和vm_pgoff同时变化,则通过vma_address还是可以正确的获得page也进程空间中逻辑空间的位置。
3、拆分时对vm_pgoff的处理
同样以刚才的三个页面为例。新分裂的第二个vma结构的vm_start调整为0x14000,vm_pgoff调整为1,之前这个逻辑对应的页面中保存的index依然是1,通过vma_address依然可以获得它对应的逻辑地址空间为0x14000。相对于之前大vma的vm_start=0x10000,vm_pgoff=0,这个page获得地址依然是0x10000 + (index - vm_pgoff)=0x10000 + (1 - 0)×PAGESIZE =0x14000
而vm_start和vm_pgoff的同步变化就是在split_vma函数中完成,其中
    if (new_below)
        new->vm_end = addr;
    else {
        new->vm_start = addr;
        new->vm_pgoff += ((addr - vma->vm_start) >> PAGE_SHIFT);//vm_pgoff和start同步变化
    }
三、vma的合并
1、合并时的问题
如果有两片读写属性相同的vma,他们中间相隔了一个页面,被分割为两个独立的vma结构,如果一次mmap将中见的空洞也映射为相同的属性,那么此时三部分vma将可以合成一个大的vma结构。再用数值说明如下
[0x10000,0x14000]的页面为可读可写、[0x18000,0x1c000]页面也为可读可写,中间的[0x14000,0x18000]页面不在进程的地址空间中。如果通过mmap将中间的[0x14000,0x18000]设置为可读可写,三个vma就可以合并为一个大的vma结构,那么page结构遍历时将如何处理呢?
事实上此时vma并不能像我们预期的那样就行一个大一统的合并,而是只能进行部分合并。因为原始的两个page在两个不同的anon_vma引导的链表上,在不能修改page结构的mapping及index前提下,如果将三个区间合并,新合并的vma只能出现在一个anon_vma引导的链表上,必然会导致之前两个vma中的某个page通过mapping无法找到自己所在的vma结构。
2、一个anon_vma阻止vma合并的例子
我们通过下面的程序来说明这个问题
tsecer@harry:/home/tsecer/nomerge>cat main.c
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
int main()
{
        const int PAGESIZE = 0x4000;
        void *START    = (void*)0x10000000;

        int * addr =(int*)mmap(START, PAGESIZE, PROT_READ|PROT_WRITE, MAP_ANON | MAP_PRIVATE, 0 , 0);
        *addr = 0;//stamp the address

        addr = (int*)mmap(START + PAGESIZE * 2, PAGESIZE, PROT_READ|PROT_WRITE, MAP_ANON | MAP_PRIVATE, 0 , 0);
        *addr = 0;//stamp the address
         addr = (int*)mmap(START + PAGESIZE * 1, PAGESIZE, PROT_READ|PROT_WRITE, MAP_ANON | MAP_PRIVATE, 0 , 0);
        sleep(10000);
}
tsecer@harry:/home/tsecer/nomerge>gcc main.c -o nomerge
tsecer@harry:/home/tsecer/nomerge>./nomerge &
[1] 6242
tsecer@harry:/home/tsecer/nomerge>cat /proc/6242/maps
08048000-08049000 r-xp 00000000 08:01 478012     /home/tsecer/nomerge/nomerge
08049000-0804a000 rw-p 00000000 08:01 478012     /home/tsecer/nomerge/nomerge
10000000-10008000 rw-p 10000000 00:00 0 两个区间的anon_vma结构不同,导致区间相邻,属性相同,但是区间不能
10008000-1000c000 rw-p 10008000 00:00 0 合并为同一个vma结构
b7e07000-b7e08000 rw-p b7e07000 00:00 0
b7e08000-b7f42000 r-xp 00000000 08:01 218666     /lib/libc-2.4.so
b7f42000-b7f44000 r--p 00139000 08:01 218666     /lib/libc-2.4.so
b7f44000-b7f46000 rw-p 0013b000 08:01 218666     /lib/libc-2.4.so
b7f46000-b7f49000 rw-p b7f46000 00:00 0
b7f53000-b7f54000 rw-p b7f53000 00:00 0
b7f54000-b7f6f000 r-xp 00000000 08:01 218607     /lib/ld-2.4.so
b7f6f000-b7f71000 rw-p 0001a000 08:01 218607     /lib/ld-2.4.so
bfadc000-bfaf2000 rw-p bfadc000 00:00 0          [stack]
bfffe000-bffff000 r-xp bfffe000 00:00 0
tsecer@harry:/home/tsecer/nomerge>
在程序mmap之后,故意通过
*addr = 0
来制造缺页异常为这个vma分配anon_vma结构,阻止在mmap中间空洞时进行vma的合并。可以看到,vma还是顽强的进行了最大可能性的合并,就是新mmap的vma区间和紧邻的前一个vma进行了合并,具体的判断为从vma_merge函数开始,依次进入
static int
can_vma_merge_before(struct vm_area_struct *vma, unsigned long vm_flags,
    struct anon_vma *anon_vma, struct file *file, pgoff_t vm_pgoff)
{
    if (is_mergeable_vma(vma, file, vm_flags) &&
        is_mergeable_anon_vma(anon_vma, vma->anon_vma)) {
        if (vma->vm_pgoff == vm_pgoff)
            return 1;
    }
    return 0;
}

static inline int is_mergeable_anon_vma(struct anon_vma *anon_vma1,
                    struct anon_vma *anon_vma2)
{
    return !anon_vma1 || !anon_vma2 || (anon_vma1 == anon_vma2);
}
可以看到的是,mergeable的判断要求anon_vma一个为空,或者两者相同,注意,不是结构内容相同,而是结构地址相同,必须为同一个anon_vma对象。
四、映射相关代码注释中常见的case的出处
在rmap及mmap中有很多说明case的情况(例如vma_adjust函数中的注释),这个case只得就是vma_merge函数之前注释的一些情况。这个文字在一些源码编辑器里显示可能不齐(下面拷贝出来之后,在这个页面里显示也没有按作者的本意对齐),例如sourceinsight中,所以在文本中显示可以看出作者的意思。其中AAA表示新操作的区间,它和它下面一行通过P、N、X表示的、和AAA逻辑地址空间重合的地址空间的内存布局情况,其中P和N的内存属性不同,而X的属性未知,因为正常情况下只有Prev和Next,而X则为合并之后面新的新的内存区域的属性
/*
 * Given a mapping request (addr,end,vm_flags,file,pgoff), figure out
 * whether that can be merged with its predecessor or its successor.
 * Or both (it neatly fills a hole).
 *
 * In most cases - when called for mmap, brk or mremap - [addr,end) is
 * certain not to be mapped by the time vma_merge is called; but when
 * called for mprotect, it is certain to be already mapped (either at
 * an offset within prev, or at the start of next), and the flags of
 * this area are about to be changed to vm_flags - and the no-change
 * case has already been eliminated.
 *
 * The following mprotect cases have to be considered, where AAAA is
 * the area passed down from mprotect_fixup, never extending beyond one
 * vma, PPPPPP is the prev vma specified, and NNNNNN the next vma after:
 *
 *     AAAA                                AAAA                AAAA          AAAA
 *    PPPPPPNNNNNN    PPPPPPNNNNNN    PPPPPPNNNNNN    PPPPNNNNXXXX
 *    cannot merge    might become    might become    might become
 *                    PPNNNNNNNNNN    PPPPPPPPPPNN    PPPPPPPPPPPP 6 or
 *    mmap, brk or    case 4 below    case 5 below    PPPPPPPPXXXX 7 or
 *    mremap move:                                                    PPPPNNNNNNNN 8
 *           AAAA
 *    PPPP    NNNN    PPPPPPPPPPPP    PPPPPPPPNNNN    PPPPNNNNNNNN
 *    might become    case 1 below    case 2 below    case 3 below
 *
 * Odd one out? Case 8, because it extends NNNN but needs flags of XXXX:
 * mprotect_fixup updates vm_flags & vm_page_prot on successful return.
 */
其中这一组每一列为一组,子上而下
 *     AAAA                            AAAA                                   AAAA                   AAAA
 *    PPPPPPNNNNNN    PPPPPPNNNNNN    PPPPPPNNNNNN    PPPPNNNNXXXX
 *    cannot merge            might become           might become             might become
 *                                     PPNNNNNNNNNN    PPPPPPPPPPNN      PPPPPPPPPPPP 6 or
 *                                     case 4 below              case 5 below              PPPPPPPPXXXX 7 or
 *                                                                                                           PPPPNNNNNNNN 8
接下来以行为单位
      mmap, brk or
      mremap move:
 *             AAAA
 *    PPPP         NNNN    PPPPPPPPPPPP    PPPPPPPPNNNN    PPPPNNNNNNNN
 *    might become           case 1 below           case 2 below             case 3 below
  评论这张
 
阅读(1274)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017