从史前文明到女娲补天:Linux内存逆向映射(reverse mapping)技术的前世今生
当系统中的一个CPU在执行try_to_unmap_anon函数的时候,需要遍历VMA链表,这时会持有anon_vma->lock这个自旋锁。由于anon_vma存有了很多根本无关的VMA,通过,page table的检索过程,你就会发现这个VMA根本和准备unmap的page无关,因此只能scan下一个VMA,整个过程需要消耗大量的时间,延长了临界区(复杂度是O(N))。与此同时,其他CPU在试获取这把锁的时候,基本会被卡住,这时候整个系统的性能可想而知了。更加糟糕的是内核中并非只有unmap匿名页面的时候会上锁、遍历VMA链表,还有一些其他的场景也会这样(例如page_referenced函数)。想象一下,一百万个页面共享这一个anon_vma,对anon_vma->CPU在执行try_to_unmap_anon函数的时候,需要遍历VMA链表,这时会持有anon_vma->lock这个自旋锁。由于anon_vma存有了很多根本无关的VMA,通过,page table的检索过程,你就会发现这个VMA根本和准备unmap的page无关,因此只能scan下一个VMA,整个过程需要消耗大量的时间,延长了临界区(复杂度是O(N))。与此同时,其他CPU在试获取这把锁的时候,基本会被卡住,这时候整个系统的性能可想而知了。更加糟糕的是内核中并非只有unmap匿名页面的时候会上锁、遍历VMA链表,还有一些其他的场景也会这样(例如page_referenced函数)。想象一下,一百万个页面共享这一个anon_vma,对anon_vma->lock自旋锁的竞争那是相当的激烈埃
2、改进的方案
旧的方案的症结所在是anon_vma承载了太多进程的VMA了,如果能将其变成per-process的,那么问题就解决了。Rik van Riel的解决办法是为每一个进程创建一个anon_vma结构并通过各种数据结构把父子进程的anon_vma(后面简称AV)以及VMA链接在一起。为了链接anon_vma,内核引入了一个新的结构,称为anon_vma_chain(后面简称AVC):
struct anon_vma_chain {
struct vm_area_struct *vma;――指向该AVC对应的VMA
struct anon_vma *anon_vma;――指向该AVC对应的AV
struct list_head same_vma; ――链接入VMA链表的节点
struct rb_node rb;―――链接入AV红黑树的节点
unsigned long rb_subtree_last;
};
AVC是一个神奇的结构,每个AVC都有其对应的VMA和AV。所有指向相同VMA的AVC会被链接到一个链表中,链表头就是VMA的anon_vma_chain成员。而一个AV会管理若干的VMA,所有相关的VMA(其子进程或者孙进程)都挂入红黑树,根节点就是AV的rb_root成员。
这样的描述非常枯燥,估计第一次接触逆向映射的同学是不会明白的,不如我们一起来看看AV、AVC和VMA的"大厦"是如何搭建起来的。
3、当VMA和VA首次相遇
由于采用了COW技术,子进程和父进程的匿名页面往往是共享的,直到其中之一发起写操作。但是如果子进程执行了exec的系统调用,加载了自己的二进制image,这时候,子进程和父进程的执行环境(包括匿名页面)就分道扬镳了(参考flush_old_exec函数),我们的场景就是从这么一个全新的exec后的进程开始。当该进程的匿名映射VMA通过page fault分配第一个page frame的时候,内核会构建下图所示的数据关系:
上图中的AV0就是该进程的anon_vma,由于它是一个顶级结构,因此它的root和parent都是指向了自己。AV这个数据结构当然为了管理VMA了,不过新机制中,这是通过AVC进行中转的。上图中的AVC0搭建了该进程VMA和AV之间的桥梁,分别有指针指向了VMA0和AV0,此外,AVC0插入到AV的红黑树,同时也会插入到VMA的链表中。
对于这个新分配的page frame而言,它会mapping到VMA对应的某个虚拟地址上去,为了维护逆向映射的关系,struct page中的mapping指向了AV0,index成员指向了该page在整个VMA0中的偏移。图中没有画出这个关系,主要因为这是老生常谈了,相信大家都已经熟悉。
VMA0中随后可能会有若干的page frame被mapping到该VMA的某个虚拟页面,不过上面的结构不会变化,只不过每一个page中的mapping都指向了上图中的AV0。另外,上图中那个虚线绿色block的AVC0其实等于那个绿色实线的AVC0 block,也就是说这时候该VMA只有一个anon_vma_chain,即AVC0,上图只是方便表示该AVC也会被挂入VMA的链表,挂入anon_vma的红黑树而已。
如果想参考相关的代码可以仔细看看do_anonymous_page或者do_cow_fault。
4、在fork的时候,匿名映射的VMA经历了什么?
一旦fork,那么子进程会copy父进程的VMA(参考函数dup_mmap),子进程会有自己的VMA,同时也会分配自己的AV(旧的机制下,多个进程共享一个AV,而新的机制中,AV是per process的),然后建立父子进程之间的VMA、VA的"大厦",主要的步骤如下:
(1)调用anon_vma_clone函数,建立子进程VMA和"父进程们"VA的关系
(2)建立子进程VMA和子进程VA的关系
怎样叫做建立VMA和VA的关系?其实就是anon_vma_chain_link函数的调用过程,步骤如下:
(1)分配一个AVC结构,成员指针指向对应的VMA和VA
(2)将该AVC加入VMA链表
(3)将该
Linux 相关文章:
- 工控机在IC卡加油工程中的应用(05-13)
- 联网汽车为什么选择Linux开源平台?(07-10)
- 多网络和Linux代理的Android无线远程控制系统(02-02)
- 基于嵌入式Linux的家居监控系统设计(02-22)
- 基于嵌入式Linux系统的导航软件设计思路(03-17)
- 新型嵌入式机器视觉系统的设计研究(04-21)