逆向映射的两个问题
本文是原「蜗窝讨论区」的历史存档（2017-09-11），来自版块「Linux kernel技术问答」，共 2 帖。讨论区已停止服务，此处仅供查阅。
问题：书上讲子进程发生COW，会分配新的页面。那么，如果是父进程先遇见COW，是会为父进程还是子进程分配新的页面？这时候匿名页面如何构建AV、AVC和VMA的关系？
回答： 如果父进程首先访问，那么它先COW，调用do_wp_page，分配page frame，然后copy，然后建立和自己AV的关系。这时候，子进程的pte仍然指向old page（但是这时候不是和父进程分享该page，而是自己独占了），old page指向父进程的AV。
当子进程访问该页面的时候，也是会page fault，调用do_wp_page，不过这时候不需要分配新的page了（因为该page是自己独占的），而是调用page_move_anon_rmap，从而指向了自己的AV。
问题：从v2.6.34开始，anon_vma中的AVC，是被组织成rbtree的。可是，该rbtree，除了insert和remove操作，就只有一种操作了：遍历。 这个我不能理解，因为任何数据结构的遍历，都是O(N)的，那么为什么(不像原来一样)用list呢？
回答： 大家比较熟悉的场景都是进程fork的场景，例如：进程P，包含一个VMA（a，b），进程P fork了999个子进程，在这个场景下： 1、 P进程AV红黑树中有1000个VMA并且所有的VMA的起始地址都是（a，b），当然是在不同地址空间 2、 子进程AV红黑树中只有1个VMA 在这样的场景下，anon_vma_interval_tree_foreach会遍历每一个VMA，这是没有办法的事情。不过还有一个场景也很有意思，如果一个进程，有一个很大的VMA，随着用户空间修改部分映射的属性（例如mprotect），这个大的VMA会不断的分裂。这些分裂的VMA（x0～xn）会共享一个AV（当然，前提是VMA是匿名映射），这时候，一个进程内，非常多的VMA（起始地址都不一样）共享一个AV结构，而这个AV结构的红黑树中根据起始地址挂入分裂后的VMA（x0～xn），这时候，anon_vma_interval_tree_foreach就有意义了，如果是链表，对于给定的page，那么的确是需要一个个的匹配，但实际上x0～xn只有一个是真正match这个page的，如果是红黑树，那么anon_vma_interval_tree_foreach不会遍历，会直接命中对应的VMA。