2015年12月30日星期三

Linux-2.6.32.69 KSM Source code

The framework of ksm

 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);

2015年12月22日星期二

KSM code analysis

KSM code analysis








     struct task_struct {
1379         volatile long state;    /* -1 unrunnable, 0 runnable, >0 stopped */
1380         void *stack;
1381         atomic_t usage;
1382         unsigned int flags;     /* per process flags, defined below */
1383         unsigned int ptrace;
... ... 
1442         struct mm_struct *mm, *active_mm;
 
 }
 
     struct mm_struct {
371         struct vm_area_struct *mmap;            /* list of VMAs */
372         struct rb_root mm_rb;
... ...
390         int map_count;                          /* number of VMAs */
411         unsigned long start_code, end_code, start_data, end_data;
412         unsigned long start_brk, brk, start_stack;
413         unsigned long arg_start, arg_end, env_start, env_end;  
... ... 
    }
 
 
269 /*
270  * This struct defines a memory VMM memory area. There is one of these
271  * per VM-area/task.  A VM area is any part of the process virtual memory
272  * space that has a special rule for the page-fault handlers (ie a shared
273  * library, the executable area etc).
274  */
275 struct vm_area_struct {
276         /* The first cache line has the info for VMA tree walking. */
277 
278         unsigned long vm_start;         /* Our start address within vm_mm. */
279         unsigned long vm_end;           /* The first byte after our end address
280                                            within vm_mm. */
281 
282         /* linked list of VM areas per task, sorted by address */
283         struct vm_area_struct *vm_next, *vm_prev;
284 
285         struct rb_node vm_rb;
... ...
297         struct mm_struct *vm_mm;        /* The address space we belong to. */
298         pgprot_t vm_page_prot;          /* Access permissions of this VMA. */
299         unsigned long vm_flags;         /* Flags, see mm.h. */
... ...
318         struct anon_vma *anon_vma;      /* Serialized by page_table_lock */
319 
320         /* Function pointers to deal with this struct. */
321         const struct vm_operations_struct *vm_ops;
322 
323         /* Information about our backing store: */
324         unsigned long vm_pgoff;         /* Offset (within vm_file) in PAGE_SIZE
325                                            units, *not* PAGE_CACHE_SIZE */
326         struct file * vm_file;          /* File we map to (can be NULL). */
327         void * vm_private_data;         /* was vm_pte (shared mem) */
... ... 
} 
 
 
/**
 * struct mm_slot - ksm information per mm that is being scanned
 * @link: link to the mm_slots hash list链接到mm_slots的哈希表,用于查找mm_slot
 * @mm_list: link into the mm_slots list, rooted in ksm_mm_head链接到mm_slots双向链表,链表头是ksm_mm_head
 * @rmap_list: head for this mm_slot's singly-linked list of rmap_items
 * @mm: the mm that this information is valid for
 */
struct mm_slot {
 struct hlist_node link;
 struct list_head mm_list;
 struct rmap_item *rmap_list;
 struct mm_struct *mm;
};
 
ksm_mm_head是mm_slot结构体类型的对象,它的双向链表mm_list的前驱和后继指针都指向自身; 

static struct mm_slot ksm_mm_head = {
 .mm_list = LIST_HEAD_INIT(ksm_mm_head.mm_list),
}; 链表头的初始化

 
正是由于链表的初始化为指向自身,空链表的判断正是通过判定后继指针是否指向自身

/**
 * list_empty - tests whether a list is empty
 * @head: the list to test.
 */
static inline int list_empty(const struct list_head *head)                                                                                                                         
{
    return head->next == head;
}
 
 
#define LIST_HEAD_INIT(name) { &(name), &(name) }
  
 
Linux Kernel中定义的通用doubly linked list, 
struct list_head {
    struct list_head *next, *prev;
} 
可见结构体list_head为双向链表,链表中的元素只有两个指针,前驱指针指向它的前一项,后继指针指向后一项
/**
 * struct ksm_scan - cursor for scanning
 * @mm_slot: the current mm_slot we are scanning
 * @address: the next address inside that to be scanned
 * @rmap_list: link to the next rmap to be scanned in the rmap_list
 * @seqnr: count of completed full scans (needed when removing unstable node)
 *
 * There is only the one ksm_scan instance of this cursor structure.
 */
struct ksm_scan {
 struct mm_slot *mm_slot;  正在扫描的mm_slot
 unsigned long address;     下次要扫描的地址
 struct rmap_item **rmap_list; 指向rmap链表中下一个要扫描的rmap项
        unsigned long seqnr; 实现已完成的完整扫描计数,移除非稳定结点时使用
};
 ksm_scan结构体的类型的ksm_scan中mm_slot指针指向了mm链表的链表头项
static struct ksm_scan ksm_scan = {
    .mm_slot = &ksm_mm_head,
};
扫描游标结构体中指向正在扫描的mm_slot的指针被初始化为mm链表的链表头




/**
 * struct rmap_item - reverse mapping item for virtual addresses
 * @rmap_list: next rmap_item in mm_slot's singly-linked rmap_list
 * @anon_vma: pointer to anon_vma for this mm,address, when in stable tree
 * @nid: NUMA node id of unstable tree in which linked (may not match page)
 * @mm: the memory structure this rmap_item is pointing into
 * @address: the virtual address this rmap_item tracks (+ flags in low bits)
 * @oldchecksum: previous checksum of the page at that virtual address
 * @node: rb node of this rmap_item in the unstable tree
 * @head: pointer to stable_node heading this list in the stable tree
 * @hlist: link into hlist of rmap_items hanging off that stable_node
 */
struct rmap_item {
 struct rmap_item *rmap_list; 指向mm_slot内的单向rmap_list链表
 union {
  struct anon_vma *anon_vma; /* when stable */
#ifdef CONFIG_NUMA
  int nid;  /* when node of unstable tree */
#endif
 };
 struct mm_struct *mm; 这个反向映射项指向的内存结构
 unsigned long address;  /* + low bits used for flags below */
 unsigned int oldchecksum; /* when unstable */
 union {
  struct rb_node node; /* when node of unstable tree */
  struct {  /* when listed from stable tree */
   struct stable_node *head;
   struct hlist_node hlist;
  };
 };
};
 
定义了KSM_RUN的4种取值,分别对应与停止,运行合并,逆合并以及离线状态 
#define KSM_RUN_STOP    0
#define KSM_RUN_MERGE   1
#define KSM_RUN_UNMERGE 2
#define KSM_RUN_OFFLINE 4
这个值可以通过echo相应的值到/sys/kernel/mm/ksm/run实时改变

初始值为KSM_RUN_STOP:
static unsigned long ksm_run = KSM_RUN_STOP;

初始化函数ksm_init中,创建了KSM的内核线程,

ksm_thread = kthread_run(ksm_scan_thread, NULL, "ksmd");

内核线程的调度由内核负责,一个内核线程处于阻塞状态时不影响其他的内核线程,因为其是调度的基本单位。
这与用户线程是不一样的。因为内核线程只运行在内核态,因此,它只能使用大于PAGE_OFFSET(3G)的地址空间。
内核线程和普通的进程间的区别在于内核线程没有独立的地址空间,mm指针被设置为
NULL;它只在 内核空间运行,从来不切换到用户空间去;并且和普通进程一样,可以被调度,也可以被抢占。
内核线程或叫守护进程,系统中以d结尾的进程名,就是内核线程。
创建内核线程的最基本的两个接口函数是:
 
kthread_run(threadfn, data, namefmt, ...)

kernel_thread(int(* fn)(void *),void * arg,unsigned long flags)
在ksm.c中用到的是kthread_run, 

/**                   
 * kthread_run - create and wake a thread.
 * @threadfn: the function to run until signal_pending(current).
 * @data: data ptr for @threadfn.
 * @namefmt: printf-style name for the thread.
 *
 * Description: Convenient wrapper for kthread_create() followed by
 * wake_up_process().  Returns the kthread or ERR_PTR(-ENOMEM).
 */
#define kthread_run(threadfn, data, namefmt, ...)              \
({                                     \
    struct task_struct *__k                        \
        = kthread_create(threadfn, data, namefmt, ## __VA_ARGS__); \
    if (!IS_ERR(__k))                          \
        wake_up_process(__k);                      \
    __k;                                   \
})
kthread_run()负责内核线程的创建,它由kthread_create()和wake_up_process()两部分组成,这样的好处是用
kthread_run()创建的线程可以直接运行。外界调用kthread_run创建运行线程。kthread_run是个宏定义,首先调用
kthread_create()创建线程,如果创建成功,再调用wake_up_process()唤醒新创建的线程。
kthread_create()根据参数向kthread_create_list中发送一个请求,并唤醒kthreadd,之后会调用
wait_for_completion(&create.done)等待线程创建完成。新创建的线程开始运行后,入口在
kthread(),kthread()调用complete(&create->done)唤醒阻塞的模块进程,并使用
schedule()调度出去。kthread_create()被唤醒后,设置新线程的名称,并返回到kthread_run中。
kthread_run调用wake_up_process()重新唤醒新创建线程,此时新线程才开始运行kthread_run参数中的入口函数。

与线程创建有关的两个基本函数:
int kthread_stop(struct task_struct *k);

int kthread_should_stop(void);

kthread_stop()负责结束创建的线程,参数是创建时返回的task_struct指针。kthread设置标志
should_stop,并等待线程主动结束,返回线程的返回值。在调用 kthread_stop()结束线程之前一定要检查该线程是否
还在运行(通过kthread_run 返回的 task_stuct是否有效),否则会造成灾难性的后果。kthread_run的返回值tsk。
不能用tsk是否为NULL进行检查,而要用IS_ERR()宏定义检查,这是因为返回的是错误码,
大致从0xfffff000~0xffffffff。

kthread_should_stop()返回should_stop标志(参见 struct kthread )。它用于创建的线程检查结束标志,并决定是否退出。
kthread() (注:原型为:static int kthread(void *_create) )的实现在kernel/kthread.c中,头文件是include/linux/kthread.h。内核中一直运行一个线程 kthreadd,它运行kthread.c中的kthreadd函数。在kthreadd()中,不断检查一个kthread_create_list 链表。kthread_create_list中的每个节点都是一个创建内核线程的请求,kthreadd()发现链表不为空,就将其第一个节点退出链 表,并调用create_kthread()创建相应的线程。create_kthread()则进一步调用更深层的kernel_thread()创建 线程,入口函数设在kthread()中。
      外界调用kthread_stop()删除线程。kthread_stop首先设置结束标志should_stop,然后调用 wake_for_completion(&kthread->exited)上,这个其实是新线程task_struct上的 vfork_done,会在线程结束调用do_exit()时设置。

言归正传,当我们的线程创建是调用了ksm_scan_thread函数,此函数正是线程运行的函数。
  static int ksm_scan_thread(void *nothing)
{
          ...
          ksm_do_scan(ksm_thread_pages_to_scan);
          ...
}
ksm_scan_thread中最主要就是ksm_do_scan函数。
ksm_do_scan是ksm扫描器主要的工作函数,scan_npages是每次要扫描的页数目。参数ksm_thread_pages_to_scan可以通过sysfs设定,默认100。
/**
 * ksm_do_scan  - the ksm scanner main worker function.
 * @scan_npages - number of pages we want to scan before we return.
 */
static void ksm_do_scan(unsigned int scan_npages)
{
    struct rmap_item *rmap_item;
    struct page *uninitialized_var(page); //此处声明了一个未初始化的page指针,
                                                         // 其中#define uninitialized_var(x) x = *(&(x))
                                                         // 这是一个防止编译报错的小技巧
    while (scan_npages-- && likely(!freezing(current))) {
        cond_resched();
        rmap_item = scan_get_next_rmap_item(&page); //去指针的地址,也就是指向指针的指针,所以参数的类型是struct page **page.
        if (!rmap_item)
            return;
        cmp_and_merge_page(page, rmap_item);
        put_page(page);
    }   
}

此函数的两个主要函数是scan_get_rmap_item和cmp_and_merge_page.

static struct rmap_item *scan_get_next_rmap_item(struct page **page) 
{   
    ...
    *page = follow_page(vma, ksm_scan.address, FOLL_GET);  //函数follow_page的返回值类型是指向
                                           //page结构体的指针。并将返回值赋给了{(指针的指针)取值}
                                           //也就是指向struct page的指针,最终相当于给page指针赋值
                                           //得到了page的地址,起到了参数传出的效果
    ... 
}
 
在scan_get_next_rmap_item执行过程中,用到了扫描游标ksm_scan,
 slot = ksm_scan.mm_slot; 
 
 slot = list_entry(slot->mm_list.next, struct mm_slot, mm_list);                                                                          
 ksm_scan.mm_slot = slot;                                   
 
 list_entry:从一个结构的成员指针找到其容器的指针,
 #define list_entry(ptr, type, member) \ 
    container_of(ptr, type, member)
 
list_entry(ptr, type, member);
ptr 结构体中list_head指针
type 链表被嵌入的结构体类型
member 此结构体内list_head的名字 
List_entry通过mm_list.next指针,列出了mm_slot结构体的后继mm_slot的指针。
 
函数scan_get_next_rmap_item实现了mm的页遍历,使用自增的address在同一个mm寻找其所在的vma,若vma为不为匿名域,
则跳过这个VMA,继续检查下个VMA,找到匿名VMA后,需将vma的起始地址赋给address,使用这个address得到指向页结构体
的指针,检查页为匿名页后,调用get_next_rmap_item获取此页的反向映射项: 
rmap_item = get_next_rmap_item(slot, ksm_scan.rmap_list, ksm_scan.address);
然后返回rmap_item,下次执行时将接着address+PAGE_SIZE处继续执行。扫描完一个mm结构后继续扫描下一个mm,直至所
有已建议的内存空间都被检测到, ksm_scan.seqnr++,标记一次完整的扫描结束。

函数get_next_rmap_item首先检查rmap_item是否已存在在struct mm_slot的rmap_list单链表中,如没有则先建一个
rmap_item,最后返回这个反向映射项。
 
完成了rmap_item的查找过程,就要拿这个反向映射项去比较合并了,调用
 
 * cmp_and_merge_page - first see if page can be merged into the stable tree;
 * if not, compare checksum to previous and if it's the same, see if page can
 * be inserted into the unstable tree, or merged with a page already there and
 * both transferred to the stable tree.
 
 static void cmp_and_merge_page(struct page *page, struct rmap_item *rmap_item)
 //首先检查页是否是稳定树中的结点
    stable_node = page_stable_node(page);
 
 static inline struct stable_node *page_stable_node(struct page *page)
{   
    return PageKsm(page) ? page_rmapping(page) : NULL;
}
 PageKsm(page)函数,
 /*  
 * A KSM page is one of those write-protected "shared pages" or "merged pages"
 * which KSM maps into multiple mms, wherever identical anonymous page content
 * is found in VM_MERGEABLE vmas.  It's a PageAnon page, pointing not to any
 * anon_vma, but to that page's node of the stable tree.
 */ 
static inline int PageKsm(struct page *page)                                                                                                                                      
{
    return ((unsigned long)page->mapping & PAGE_MAPPING_FLAGS) ==
                (PAGE_MAPPING_ANON | PAGE_MAPPING_KSM);
}                
 
page->mapping的低比特位为1,则页指向一个anon_vma对象。
struct page{
...
union {
        struct address_space *mapping;  /* If low bit clear, points to                                                                                                            
                         * inode address_space, or NULL.
                         * If page mapped as anonymous
                         * memory, low bit is set, and
                         * it points to anon_vma object:
                         * see PAGE_MAPPING_ANON below.
                         */
}
#define PAGE_MAPPING_ANON   1
#define PAGE_MAPPING_KSM    2
#define PAGE_MAPPING_FLAGS  (PAGE_MAPPING_ANON | PAGE_MAPPING_KSM)


 * On an anonymous page mapped into a user virtual memory area,
 * page->mapping points to its anon_vma, not to a struct address_space;
 * with the PAGE_MAPPING_ANON bit set to distinguish it.  See rmap.h.
 *在映射至用户虚拟内存空间的匿名页中,page->mapping指向它的anon_vma,而不是指向一个结构体地址空间,并使用
 *PAGE_MAPPING_ANON位置位区别开来。
 * On an anonymous page in a VM_MERGEABLE area, if CONFIG_KSM is enabled,
 * the PAGE_MAPPING_KSM bit may be set along with the PAGE_MAPPING_ANON bit;
 * and then page->mapping points, not to an anon_vma, but to a private
 * structure which KSM associates with that merged page.  See ksm.h.
 *在VM_MERGEABLE域内的匿名页,假如CONFIG_KSM使能,PAGE_MAPPING_KSM位要与PAGE_MAPPING_ANON比特位同时
 *置位;这时page->mapping不再指向一个anon_vma,而是指向一个私有结构体,在这个结构体是KSM绑定给已合并页的
 * PAGE_MAPPING_KSM without PAGE_MAPPING_ANON is currently never used.
 *现在的情况是,没有PAGE_MAPPING_ANON的PAGE_MAPPING_KSM从未被使用
 * Please note that, confusingly, "page_mapping" refers to the inode
 * address_space which maps the page from disk; whereas "page_mapped"
 * refers to user virtual address space into which the page is mapped. 
请注意,page_mapping指的是页从磁盘映射的inode地址空间。而page_mapped指的是页被映射到的用户虚拟地址空间。

所以,为了核实一个页是否为KSM页,我们需要判断页是否是匿名页同时PAGE_MAPPING_FLAGS是否与预定义的标志一致。
若PageKsm(page)为真,则返回page_rmapping(page),否则返回NULL。
page_mapping最终实现调用了__page_rmapping函数,

 static inline void *__page_rmapping(struct page *page)
{
    unsigned long mapping;

    mapping = (unsigned long)page->mapping;
    mapping &= ~PAGE_MAPPING_FLAGS;
    
    return (void *)mapping;
}   
这里需要解释的是为什么要返回page->mapping & ~PAGE_MAPPING_FLAGS,这是由于我们要得到的是stable_node结构体
的指针,而stable_node结构体至少是8字节且应为4的整数倍,地址的低两位为0,但是KSM在stable_tree_insert的过程中调
用了函数set_page_stable_node,改变了struct page中的page->mapping的值:
 static inline void set_page_stable_node(struct page *page,                                                                                                                        
                    struct stable_node *stable_node)                                                                                               
{                                                                                                                                                  
    page->mapping = (void *)stable_node +                                                                                                          
                (PAGE_MAPPING_ANON | PAGE_MAPPING_KSM);                                                                                            
}
 
所以为了得到stable_node指针,我们需要将page->mapping的低两位复位为0.

接着分析cmp_and_merge_page:
假如页可以得到稳定节点stable_node,并且rmap_item->head == stable_node,也就是说页对应的反向映射项确实指向该
stable_node,那么页已经是已合并页且已插入了stable_tree,这种情况下什么都不做直接返回。
假如不是那么,首先在stable_tree寻找此页的相同内容页:
 kpage = stable_tree_search(page);