KSM的初始化函数ksm_init负责启动内核进程ksmd，使用语句kthread_run(ksm_scan_thread, NULL, "ksmd")，根据函数ksm_scan_thread创建了内核守护进程ksmd，在2.6.32 linux kernel中ksm默认可占用的最大内存空间是内存的1/4。ksm_scan_thread扫描线程只要内核线程未被终止就会一直执行ksm_do_scan(每个周期要扫描的页数量)，执行完一个周期后，要休眠ksm_thread_sleep_millisecs时间，如此反复。ksm_do_scan是ksm主要的功能部分，它实现了匿名页及其反向映射项的线性获取——ksm_scan_thread, 然后进行比较和页合并——cmp_and_merge_page，并且在页不满足共享条件时将页的写保护属性移除——break_cow。
现介绍cmp_and_merge_page函数的主要任务，比较和合并页函数首先将待合并的页与稳定树比较看页能否合并进稳定树，假如不能在稳定树中找到与待合并页内容一致的页，那么计算页的校验和checksum看看是否等于页原有的oldchecksum值，假如校验和未发生改变意味着页内容在两次扫描过程中未发生变化，页是非易失的，可以将此页继续与非稳定树中的页进行比较看其能否插入到非稳定树中，或者与非稳定树的页一起合并到稳定树中。具体而言，in_stable_tree(rmap_item)判断反向映射项的地址的低位是否是STABLE_FLAG，STABLE_FLAG和NODE_FLAG的含义如下：
#define NODE_FLAG 0x100 /* is a node of unstable or stable tree */
#define STABLE_FLAG 0x200 /* is a node or list item of stable tree */
remove_rmap_item_from_tree将rmap_item从稳定树或非稳定树中移除？？why
实际上假如页的反向映射项中能说明页属于稳定树时，可以什么都不做，跳过比较与合并步骤。在此，将其从稳定树中移除，等价于将原先已合并的节点中的页重新释放出来重新进行比较合并，增加了计算开销。
接下来继续分析，稳定树中相同页的查找stable_tree_search，首先找到稳定树的根节点：
root_stable_tree.rb_node，其中
static struct rb_root root_stable_tree = RB_ROOT; //定义了红黑树根结构体类型的变量root_stable_tree，并初始化为(struct rb_root) { NULL, } 而
struct rb_root
{
struct rb_node *rb_node; // rb_root结构体由指向rb_node的指针构成
}
也就是说root_stable_tree的指向rb_node的指针被复制为NULL。NULL指针的类型是rb_root结构体类型。
从稳定树的根开始，根据node获取rmap_item，调用的是rb_entry函数，函数的定义为：
#define rb_entry(ptr, type, member) container_of(ptr, type, member)。根据结构体
rmap_item中包含的组成单元rb_node类型的node得到指向rmap_item结构体的指针：
struct rmap_item {
struct list_head link;
struct mm_struct *mm;
unsigned long address; /* + low bits used for flags below */
union {
unsigned int oldchecksum; /* when unstable */
struct rmap_item *next; /* when stable */
};
union {
struct rb_node node; /* when tree node */
struct rmap_item *prev; /* in stable list */
};
};
若返回rmap_item指针不为空，也就是说可以获得反向映射项，那么调用get_ksm_page函数检查rmap_item所追踪的虚拟地址对应的page是否仍然是PageKsm, 假如页保持为PageKsm, 则可认为页内容保持不变，并返回获取的页。假如页被震动过则返回NULL。
由于稳定树中的node中得到的tree_rmap_item得到的ksm页为NULL，则说明这个反向映射项不再满足合并条件，需要从稳定树中移除，所以有了以下操作：
next_rmap_item = tree_rmap_item->next; // 首先遍历rmap_item链表
remove_rmap_item_from_tree(tree_rmap_item); //移除返回NULL的反向映射项
tree_rmap_item = next_rmap_item; //将next_rmap_item复制给下一个要操作的tree_rmap_item
操作的原因是由于稳定树的结构决定的：
但是当tree_rmap_item得到了节点对应的ksm page则跳过以上3个步骤。将得到的页与待合并的页进行比较：
ret = memcmp_pages(page, page2[0]);
根据返回值，决定如何沿着树的左右分支进行继续查找。直至找到相同页，或者遍历完成稳定树。由于同一节点上所有的rmap_item都代表同一物理页，所以只要得到有一项得到了一个ksm页，就跳到下一节点，无须获得同一节点rmap_item链的下一项。
简单看一下 memcmp_pages函数，根据要对比的两个页结构体得到两个地址，然后从地址所指向的位置取PAGE_SIZE大小进行比较：
ret = memcmp(addr1, addr2, PAGE_SIZE);
以上就是稳定树中查找的基本过程。假如可以找到内容相同的tree_rmap_item则首先判断是否为forked，假如不是同一页，那么执行try_to_merge_with_ksm_page操作，将待合并页同节点中的物理页合并。合并成功后，将它的rmap_item添加到相应节点对应的rmap_item链表尾部stable_tree_append(rmap_item, tree_rmap_item)，结束之后返回。插入到稳定树中的结构体rmap_item对应的address的地址低位被置位为0x300：
rmap_item->address |= NODE_FLAG | STABLE_FLAG;
若无法将待合并页合并进稳定树，那么接下来需要在非稳定树中继续比较，比较之前先检查一下页的校验和是否发生变化，假如校验和发生改变将新值赋值给rmap_item->oldchecksum保存起来。然后，退出此页的此次比较合并例程。
若在两次扫描过程中页的校验和未发生过变化，则可拿此页到unstable树中进行比较。
unstable_tree_search_insert这个函数在非稳定树中为正在扫描的当前页寻找内容等同页，假如没有树中没有内容一致页，则在unstable tree中插入rmap_item作为新的对象。函数返回指向的找到的待扫描页的等同页的rmap_item指针，否则返回NULL。函数即进行搜索也负责插入，这是由于它们在红黑树中共享walking算法。
unstable_tree_search_insert与stable_tree_search函数类似，区别在于最后的插入操作，插入进非稳定树的rmap_item的address的bit8-9位被置为NODE_FLAG。地址的bit0-7位是扫描完成的次数ksm_scan.seqnr & SEQNR_MASK。
可见通过检查rmap_item->address & NODE_FLAG是否为真就能判断rmap_item在不在树中。
若unstable_tree_search_insert成功找到与扫描页等同页，则将这两项合并到稳定树中
try_to_merge_two_pages，首先检查稳定树中的节点是否超过了最大可合并页数目。若未超过限制则从内核页池中分配一个页。假如要合并的两页中已经有一个ksm页，则使用try_to_merge_with_ksm_page，否则使用try_to_merge_one_page。
首先将page1拷贝到新分配的内核页中，然后调用 try_to_merge_one_page完成page1与kpage的合并，然后在将page2与kpage合并，从而实现了非稳定树中同内容页与待扫描页page2与page1合并到稳定树中。主要过程为:
copy_user_highpage(kpage, page1, addr1, vma);
err = try_to_merge_one_page(vma, page1, kpage);
if (!err) {
err = try_to_merge_with_ksm_page(mm2, addr2, page2, kpage);
其中try_to_merge_with_ksm_page与try_to_merge_two_pages类似，区别在于不分配新的内核页，最后仍然需要调用try_to_merge_one_page(vma, page1, kpage)完成合并。函数定义为：
static int try_to_merge_one_page(struct vm_area_struct *vma,
struct page *oldpage,
struct page *newpage)
try_to_merge_with_ksm_page将两个页合并为一个页，@vma存放着指向oldpage的页表项pte，@oldpage是想用newpage替换的页，@newpage想用来替代oldpage映射的页。
此处需要注意的是，oldpage是一个匿名页PageAnon，而newpage应当是一个KSM页PageKsm，或者是一个新分配的内核页使用page_add_ksm_rmap将要使其成为一个PageKsm.
try_to_merge_one_page主要功能部分由replace_page完成。
replace_page-将vma中的页用心的ksm页替换。
一旦完成页合并，我们需要将已合并页的反向映射项rmap_item从非稳定树中移除，并将其插入到稳定树中的新节点中。
rb_erase(&tree_rmap_item->node, &root_unstable_tree); //tree_rmap_item结构体属于树节点时包含rb_node结构体node，这条语句负责将node节点从非稳定树中移除
tree_rmap_item->address &= ~NODE_FLAG; //然后将address中的节点标记还原
先将非稳定树中找到的同内容页插入到稳定树stable_tree_insert(page2[0], tree_rmap_item)，然后将待合并页添加到这个节点rmap_item链表尾
stable_tree_append(rmap_item, tree_rmap_item)。假如插入失败得到的是稳定树外的2个虚拟地址指向同一个ksm页，这种情况下需要对两个反向映射项break_cow。至此
cmp_and_merge_page整个例程结束。
ksm_do_scan的最后是将未共享的ksm页用普通页替换。一次扫描在预定义scan_npages自减为零时结束。ksm_scan_thread的结束需要所有内存建议的mm结构体都被遍历到才结束：
static int ksmd_should_run(void)
{
return (ksm_run & KSM_RUN_MERGE) && !list_empty(&ksm_mm_head.mm_list);
}
mm_slot结构体ksm_mm_head是mm_slot链表的头。
用户程序通过系统调用函数madvise,最终调用ksm_madvise函数完成需要共享的mm_struct结构体注册为可合并的VM_MERGEABLE。ksm_madvise又调用
__ksm_enter(mm)完成操作。__ksm_enter(mm)将mm_struct结构体mm插入到扫描游标
ksm_scan后方，使得要扫描范围增大。
list_add_tail(&mm_slot->mm_list, &ksm_scan.mm_slot->mm_list);
没有评论:
发表评论