0%

Linux内存管理(九)KSM

原图

概述

KSM指Kernel SamePage Merging,即内核同页合并,用于合并内容相同的页面。KSM的出现是为了优化虚拟化中产生的冗余页面。 KSM允许合并同一个进程或不同进程之间内容相同的匿名页面,这对应用程序来说是不可见的。把这些相同的页面合并成一个只读的页面,从而释放出多余的物理页面,当应用程序需要改变页面内容时,会发生写时复制。

使能KSM

KSM只会处理通过madvise系统调用显式指定的用户进程地址空间,因此用户程序想使用这个功能就必须在分配地址空间时显式地调用madvise(addr,length,MADV_MERGEA BLE)。如果用户想在KSM中取消某一个用户进程地址空间的合并功能,也需要显式地调用madvise(addr,length,MADV_UNMERGEABLE)。 下面是测试KSM的test.c程序的代码片段,使用mmap():来创建一个文件的私有映射,并且调用memset()写入这些私有映射的内容缓存页面中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
《测试KSM的test.c程序的代码片段》
#include <stdio.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <unistd.h>
#include <fcntl.h>
int main(int argc,char *argv[])
{
char *buf;
char filename[64]="";
struct stat stat;
int size =100*4096;
int fd =0;

strcpy(filename, argv[1]);

fd = open(filename,O_RDWR | O_CREAT,0664);

fstat(fd, &stat);

buf = mmap (NULL,stat.st_size,PROT_WRITE,MAP_PRIVATE,fd,0);

memset(buf,0x55,stat.st_size);

madvise(buf,stat.st_size, MADV_MERGEABLE);

while (1)
sleep(1);
}

编译上述test.c程序。

1
gcc test.c -o test

使用dd命令创建一个ksm.dat文件,即创建100MB大小的文件。

1
dd if=/dev/zero of=ksm.dat bs=1M count=100

使能KSM。

1
echo 1 >/sys/kernel/mm/ksm/run

运行test.c程序。

1
#./test ksm.dat

过一段时间之后,查看系统有多少页面合并了。

1
2
3
4
5
6
root@benshushu#cat /sys/kernel/mm/ksm/pages_sharing
25500
root@benshushu#cat /sys/kernel/mm/ksm/pages_shared
100
root@benshushu:/home#cat /sys/kernel/mm/ksm/pages_unshared
0

可以看到pages_shared为100说明系统有100个共享的页面。若有100个页面的内同,它们可以合并成一个页面,这时pages_shared为1。 pages_sharing 为25500说明有25500个页面合并了。 100MB的内存可存放25600个页面。因此,我们可以看到,KSM把这25600个页面分别合并成1共享的页面,每一个共享页面里共享了其他的255个页面,为什么会这样?我们稍后详细解析。 pages_unshared表示当前未合并页面的数量。

1
2
3
4
rootebenshushut cat /sys/kernel/mn/ksm/stable_node_chains
1
rootebenshushut cat /sys/kernel/mm/ksm/stable_node_dups
100

stable_node_chains表示包含了链式的稳定节点的个数,当前系统中为1,说明只有一个链式的稳定节点,但是这个稳定的节点里包含了链表。 stable_node_dups表示稳定的节点所在的链表包含的元素总数。 KSM的sysfs节点在/sys/kernel/mm/ksm/目录下,其主要节点的描述如下所示。

  • run:可以设置为0~2。若设置0,暂停ksmd内核线程;若设置1,启动ksmd内核线程;若设置2,取消所有已经合并好的页面
  • full_scans: 完整扫描和合并区域的次数
  • pages_volatile: 表示还没扫描和合并的页面数量。若由于页面内容更改过快导致两次计算的校验值不相等,那么这些页面是无法添加到红黑树里的
  • sleep_millisecs: ksmd内核线程扫描一次的时间间隔
  • pages_to_scan: 单次扫描页面的数量
  • pages_shared: 合并后的页面数。如果100个页面的内容相同,那么可以把它们合并成一个页面,这时pages_shared的值为1
  • pages_sharing: 共享的页面数。如果两个页面的内容相同,它们可以合并成一个页面,那么有一个页面要作为稳定的节点,这时pages_shared的值为1,pages_sharing也为1。第3个页面也合并进来后,pages_sharing的值为2,表示两个页面共享同一个稳定的节点
  • pages_unshared: 当前未合并页面数量
  • max_page_sharing: 这是在Linux4.3内核中新增的参数,表示一个稳定的节点最多可以合并的页面数量。这个值默认是256
  • stable_node_chains: 链表类型的稳定节点的个数。每个链式的稳定节点代表页面内容相同的KM页面。这个链式的稳定节点可以包含多个dup成员,每个dup成员最多包含256个共享的页面
  • stable_node_dups: 链表中dup成员的个数。这些dup成员会连接到链式的稳定节点的hlist链表中

KSM在初始化时会创建一个名为ksmd的内核线程。

1
2
3
4
5
6
<mm/ksm.c>
static int __init ksm_init(void)
{
ksm_thread = kthread_run(ksm_scan_thread, NULL, "ksmd");
}
subsys_initcall(ksm_init);

在tes.c程序中创建私有映射(MAP_PRIVATE)之后,显式地调用madvise系统调用把用户进程地址空间添加到 Linux内核的KSM系统中。

1
2
3
4
5
6
7
8
9
<madvise()->ksm_madvise()-> ksm_enter()>

int __ksm_enter(struct mm_struct *mm)
{
mm_slot = alloc_mm_slot();
insert_to_mm_slots_hash(mm, mm_slot);
list_add_tail(&mm slot->mm_list, &ksm_scan.mm_slot->mm list);
set_bit(MME_VM_MERGEABLE, &mm->flags);
}

ksm_enter()函数会把当前的 mm_struct数据结构添加到 mm_slots_hash哈希表中。另外把 mm_slot添加到 ksm_scan.mm_slot->mm_list 链表中。最后,设置mm->flags中的 MMF_VM_MERGEABLE标志位,表示这个进程已经被添加到KSM系统中.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
<ksm内核线程>

static int ksm_scan_thread(void *nothing)
{
while (!kthread_should_stop())
if (ksmd_should_run())
ksm_do_scan(ksm_thread_pages_to_scan)
if (ksmd_should_run()) {
sleep_ms =READ_ONCE(ksm_thread_sleep_millisecs);
wait_event_interruptible_timeout(ksm_iter_wait,
sleep_ms != READ_ONCE(ksm_thread_sleep_millisecs),
secs_to_jiffies(sleep_ms));
}
return 0;
}

ksm_scan_thread()是ksmd内核线程的主干,它运行 ksm_do_scan()函数,扫描和合并100个页面,见 ksm_thread_pages_to_scan参数,然后等待20ms,见 ksm_thread_sleep_millisecs参数,这两个参数可以在/sys/kernel/mm/ksm目录下设置和修改。

1
2
3
4
5
6
7
8
9
10
11
12
13
<ksmd内核线程>

static void ksm_do_scan(unsignd int scan_npages)
{
while(scan_npages-- && likely(!freezing(current))) {
cond_resched();
rmap_item = scan_get_next_rmap_item(&page);
if (!rmap_item)
return;
cmp_and_merge_page(page, rmap_item);
put_page(page)
}
}

ksm_do_scan()函数在while循环中尝试合并scan_npages个页面, scan_get_next_rmap_item()获取一个合适的匿名页面。 cmp_and_merge_page()函数会让页面在KSM中稳定和不稳定的两棵红黑树中查找是否有可以合并的对象,并且尝试合并他们。

KSM基本实现

为了让读者先有一个初步的认识,本节先介绍Lnux4.13内核之前的KSM实现,后文会介绍Linux5.0内核中的实现。

KSM机制下采用两棵红黑树来管理扫描的页面和己经合并的页面。第一棵红黑树称为不稳定红黑树,里面存放了还没有合并的页面;第二棵红黑树称为稳定红黑树,已经合并的页面会生成一个节点,这个节点为稳定节点。如两个页面的内容是一样的,KSM扫描并发现了它们,因此这两个页面就可以合并成一个页面。对于这个合并后的页面,会设置只读属性,其中一个页面会作为稳定的节点挂载到稳定的红黑树中之后,另外一个页面就会被释放了。但是这两个页面的 rmap_item数据结构会被添如到稳定节点中的 hist 链表中,如下图所示。

我们假设有3个VMA(表示进程地址空间,VMA的大小正好是一个页面的大小,分别有3个页面映射这3个VMA。这3个页面准备通过KSM来扫描和合并,这3个页面的内容是相同的。具体步骤如下。

  • 3个页面会被添加到KSM中,第一轮扫描中分别给这3个页面分配 rmap_item数据结构来描述它们,并且分别给它计算校验和,如图(a)所示
  • 第二轮扫描中,先扫描page0,若当前稳定的红黑树没有成员,那么不能比较和加入稳定的红黑树。接着,第二次计算校验值,如果 page0的校验值没有发生变化,那么把page0的rmap_item()添加到不稳定的红黑树中,如图(b)所示。如果此时校验值发生了变化,说明页面内容发生变化,这种页面不适合添加到不稳定的红黑树中
  • 扫描 page1,当前稳定的红黑树中没有成员,略过稳定的红黑树的搜索。搜索不稳定的红黑树,遍历红黑树中所有成员。 page1发现自己的内容与不稳定的红黑树中的 rmap_item()一致,因此尝试将page0和 page1合并成一个稳定的节点,合并过程就是让WMA0对映的虚拟地址、vaddr0映时到page1上。,并且把对应的PTE属性修改成只读展性。另外,VMA1映射到 page1的PTE属性也设置为只读属性。新创建一个稳定的节点,这个节点包含了page1的页帧号等信息,把这个稳定的节点添加到稳定的红黑树中。把代表page0的 map _item0和page1的rmap_item1添加到这个稳定的节点的hlist链表中,最后释放page0页面,如图(c)所示
  • 扫描page2。因为稳定的红黑树中有成员,因此,先和稳定的红黑树中的成员进行比较,检査是否可以合并。若发现page2的内容和稳定的节点内容一致,那么把VMA2中的vaddr2映射到稳定的节点对应的 page1上,并且把PTE属性设置为只读属性。把代表page2的rmap_item2添加到稳定的节点的 hlist 链表中,最后释放page2页面,如图(d)所示

上述步骤完成之后,VMAO~VMA2这3个VMA对应的虚拟地址(vadr)都映射到page1上,并且映射的3个PTE属性都是只读属性,page1生成一个稳定的节点并被添加到了稳定的红黑树中,page0和page2被释放了。

新版本KSM的新特性

新版本的KSM(如 Linux5.0内核的KSM)比 Linux4.0内核的KSM新增了两项特性。

  • 对内容全是零的页面进行特殊处理
  • 对稳定的节点的hlis链表进行改造,以防止大量的相同的页面聚集在一个稳定的节点中,导致页面迁移、内存规整等机制长时间等待这个页面

新特性中,第一项实现起来比较简单,系统中己经存在了系统零页,我们可以对这个系统零页预先计算检査和。若在扫描页面时发现页面的检査和等于系统零页的检查和,那么直接修改这个页面的映射关系,让其映射到系统零页,这样可以释放这个页面。 第二项新特性实现起来就比较复杂了。主要原因是在一些大型的服务器中,会把大量的页面(如几百万个页面)合并到一个稳定的节点中。 页面迁移机制会调用RMAP机制来遍历这个稳定节点中所有的rmap_item,如图所示。在try_to_unmap_one()函数解除页表映射关系时,需要调用 flush_tlb_page()函数来刷新TLB。CPU内部发送IPI广播来通知其他CPU做了这个TLB刷新动作,这个页面的PTE已经被解除映射关系,大概需要10pus的时间。若需要遍历1万个页表项,那么将持续100ms;若需要遍历几十万甚至几百万个页面,那么将持续更长时间。在调用my_to_unmap()函数之前需要申请这个页面的锁,但是其他进程有可能在等待这个页锁,那将会是一场“灾难”,足以让服务器宕机。具体流程如下:

1
2
3
4
5
6
7
8
9
10
11
grate_pages ()
->unmap_and_move()
->unmap_and_move()
->申请页锁
->try_to_unmap()
->rmap_walk()
->rmap_walk_ksm()
遍历稳定的节点的hlist链表中几百万个 rmap_items
->try_to_unmap_one()
->ptep_clear_flush()
->flush_tlb_page()

在 Linux4.13内核中, Red Hat工程师 Andrea Arcangeli对这个问题进行了修复。新办法是限制共享页面的数量在256以内,这样遍历256个页表项的时间将会限制在毫秒不会导致系统宕机。新的解决方案扩充了稳定节点的hlist链表结构, rmap_items 超过256个之后,扩展稳定的节点为链表。每个链表的成员都是一个稳定的节点,每个稳定的节点有一个链表,这个hlist链表中可以添加新的 rmap_items。另外,还需要把稳定的节点和链表的头在红黑树中做一个交换。 新版本的稳定的节点包含两个形态,而且它们同时存放在稳定的红黑树中,如图所示:

  • 传统的稳定的节点:兼容旧版本的稳定的节点格式。
  • 链式稳定的节点:新版本的链式节点格式。

下面以test.c程序为例,假设现在系统产生了1000个页面,并且这1000个页面的内容都是相同的,每个页面对应不同的VMA,这些VMA的大小正好是一个页面大小。接下来观察新版本的KSM如何处理这些页面,如何创建新版本的链式稳定的节点。

第1次扫描这1000个页面。第1次扫描页面时会计算每个页面的检验和。部分代码如下:

1
2
3
4
5
6
7
8
9
10
statc void cmp_and_merge_page(struct page *page, struct rmap_item *rmap_item)
{
...
checksum =calc_checksum(page);
if(rmap_item->oldchecksum != checksum) {
rmap_item->oldchecksum = checksum;
return
}
...
}

第2次扫描中,先看第一个页面(编号为page0,以此类推)的情况,它首先进入 cmp_and_merge_page()函数。具体过程如下:

  • cmp_and_merge_page()函数会遍历稳定的红黑树中每个稳定的节点,并和page0进行比较,判断内容是否一致。若内容一致,则将页面合并到稳定的节点中。因为这时 stable红黑树还是空的,所以跳过 stable_tree_searche()函数
  • 如果页面校验值不变,则遍历 unstable红黑树中的每一个 rmap_item节点。这时,不稳定的红黑树也还是空的,因此直接把 rmap_item0添加到不稳定的红黑树中,扫描第i个页面,如图所示

部分代码如下。

1
2
3
4
5
6
7
8
9
struct rmap_item * unstable_tree_search_insert()
{
...
rmap_item->address |= UNSTABLE_FLAGA;
rmap_item->address |= (ksm_scan.seqnr & SEONR_MASKD);
DO_NUMA(rmap_item->nid = nid);
rb_link_node(&rmap_item->node, parent, new);
rb_insert_color(&rmap_item->node, root);
...

接下来,扫描第2个页面(pge)。具体过程如下

  • 略过稳定的红黑树
  • 遍历不稳定的红黑树,现在不稳定的红黑树中有个成员 rmap_item0, unstable_tree_search_insert()函数取出 rmap_item0,然后和 page1进行内容比较。 try_to_merge_two_page()函数会比较 rmap_item0对应的 page0和 page1,若发现内容一致,则将其合并成一个页面。过程就是让VMA0对应的虚拟地址 vaddr0映射到 page1上,并且把对应的PTE属性修改成只读属性。另外,WMA1映射到 page1的PTE属性也设置为只读属性
  • 在 stable_tree_inserter()函数中,因为 stable红黑树为空,所以会新建一个稳定的节点(stable node数据结构),我们称它为 stable_node_dup0或者node_dup0
  • page1的页帧号也会记录在 stable_node_dup0->kpfn中,并且 rmap_list_len值为0.调用 set_page_stable_node()数把 page1设置成KSM页面,详见 mm/ksm.c文件中的代码
1
2
3
4
5
6
<mm/ksm.c>

static inline void set_page_stable_node(struct page page, struct stable_node *stable_node)
{
page->mapping =(void *)((unsigned long)stable_node | PAGE_MAPPING_KSM);
}
  • 由于这时不需要为稳定的节点建立链表,因此第1884行代码的 need_chain为ifalse最后直接把 stable_node_dup0添加到稳定的红黑树中
  • 调用 stable_tree_append(),分别把 page0对应的 rmap_item0和 page1对应的 rmap_item1添加到 stable_node_dup0->hlist 链表中。增加 ksm_pages_ shared和 ksm_pages_sharing计数,这时 ksm_pages_sharing为1, ksm_pages_shared为1, stable_node_dup0->rmap_hlist_len为2
  • 释放page0。

合并过程如图所示。

接下来,扫描第3个页面(page2)。具体过程如下。

  • 遍历 stable红黑树,见 stable_tree_search()函数。通过 rb_entry()取出稳定的红黑树节点这时,稳定的红黑树只有一个节点,那就是 stable_node_dup()
  • 调用 chain_prune()函数。在内部调用__stable_node_chain()函数时会对稳定的点行判断
1
2
3
4
5
6
7
8
9
10
11
12
13
<chain_prune()->__stable_node_chain()>

static struct page * __stable_node_chain()
{
struct stable_node *stable_node =*_stable_node;
if (!is_stable_node_chain(stable_node)) {
if (is_page_sharing_candidate(stable_node)) {
*stable_node_dup = stable_node;
return get_ksm_page(stable_node, false);
}
return NULL;
}
...
  • is_stable_node_chain判断这个稳定的节点是否为链式稳定的节点。判断依据是rmap_hlist_len是否为 STABLE_NODE_CHAIN。链式稳定的节点所在的 hlist链表是不存放rmap_item的,并且它的 rmap_hlist_len会初始化为一个固定值, STABLE_NODE_CHAIN(默认初始值为-1024),我们由此来判断该节点是否为链式稳定的节点
1
2
3
4
5
6
define STABLE_NODE_CHAIN -1024

static bool is_stable_node_chain(struct stable node *chain)
{
return chain->rmap_hlist_len == STABLE_NODE_CHATNI;
}
  • stable_node_dup0显然不是链式的稳定的节点,它是传统的稳定的节点。 is_page_sharing_candidate()判断这个节点中是否还能存放rmap_item。默认情况下,我们规定每个节点的hlist链表最多只能存放256个成员
  • 调用 get_ksm_page()函数返回 stable_node_dup0节点对应的page数据结构
  • 比较 stable_node_dup0对应的页面(即 tree_page)和page2的页面内容是否一样,若一样, stable_tree_searche()函数会返回 tree_page
  • 调用ty_to_merge_with_ksm_page()函数尝试合并 tree_page和pge2。若能合并,那么调用 stable_tree_append()函数把page2对应的 rmap_item2添加到 stable_node_dup0->hlist链表中。增加 ksm_pages_sharing的值,此时 ksm_pages_sharing的值为2。这时, stable_node_dup0->hlist_len为3
  • 释放page2

上述过程如图所示。

接下来,扫描第4个页面,一直到第256个页面。和扫描第3个页面一样,这些页面都会合并到 stable_node_dup0对应的 tree_page中,其对应的 rmap_item都会被添加到 stable_node_dup0->hlist链表中,这时stable_node_dupO->rmap_hlist_len的值为256, ksm_pages_sharing的值为255.

接下来,扫描第257个页面(p2ge256)。具体过程如下:

  • 遍历稳定的红黑树,见 stable_tree_search()函数
  • 如果在 chain_prune->__stable_node_chain()->is_page_sharing_candidate()函数中发现hlist链表的成员个数已经到达最大值( ksm_max_page_ sharing),那么会返回NULL,并且stable_node_dup参数也返回NULL
  • stable_tree_search()函数调用stable_node_dup_any()来获取稳定的节点,get_ksm_page()获取这个稳定的节点对应的 tree_page。比较 tree_page和page256的内容时发现二者是一致的,但是因为 stable_node_dup参数为NULL,所以在第1653~1666行里会返回NULL。这里在注释里对代码做了解释,当我们发现被扫描页面的内容和稳定的节点的页面内容一致时,但是因为这时稳定的节点的hlist链表已经满了,所以我们必须从不稳定的红黑树中找到另外一个页面、进行合并,创建一个新的KSM共享页面
  • 因为 stable_tree_search()函数返回NULL,所以直接遍历不稳定的红黑树。此时,不稳定的红黑树没有成员,因此可以直接把page256对应的 map_item添加到不稳定的红黑树中

接下来,扫描第258个页面(page257)。具体过程如下。

  • 遍历稳定的红黑树,见 stable_tree_search()函数。和步骤(6)一样,因为 stable_node_dup0->hlist链表满了,所以直接返回NULL
  • 调用 unstable_tree_search_insert()函数。若发现page257和不稳定红黑树的成员内容一致,返回 tree_rmap_item
  • 调用tyy_merge_two_pages()函数尝试合并pge257和 tree_page。假如它们符合合并条件,那么尝试将其合并成一个页面
  • 调用 stable_tree把这个合并后的页面添加到稳定的红黑树中。在 stable_tree_insert()函数中,遍历稳定的红黑树中的所有成员,当发现稳定的节点的页面内容和当前页面内容一致时,设置 need_chain为true并退出遍历,说明找到一个内容相同的“小伙伴”了(见1870行代码)
  • 在第1875行中,新健一个稳定的节点,称为 stable_node_dup1或者node_dup1。设置新合并页面的页帧号到 stable_node_dup1->kpfn中。 set_page_stable_node()函数把这个新合并面设置为KSM页面。这时 stable_node_dup1->rmap_hlist_len的值为0
  • 在第188行中,稳定的红黑树的节点为 stable_node_dup0,它是传统的稳定的节点在第1891行中,调用 alloc_stable_node_chain()函数重新创建一个链式稳定的节点。 chain->rmap_hlist_len的值初始化为 STABLE_NODE_CHAN,表明该节点是链式稳定的节点。増加ksm_stable_node_chains计数
  • 把链式稳定的节点替換到稳定的红黑树上的 stable_node_dup0节点,并且把stable_node_dup0节点添加到链式稳定的节点所在的 hlist 链表中,这样一个新的链式稳定的节点就创建成功了
  • 在第1897行中,把刚才新创建的 stable_node_dup1节点也添加到链式稳定的节点的hlist链表中。此时,链式稳定的节点的hlist链表中有两个成员,一个是 stable_node_dup0节点,另一个是 stable_node_dup1节点。此时, ksm_stable_node_chain为1 ksm_stable_node_dups为2
  • 在第2145~2147行中,分别调用 stable_tree_append()函数,把 rmap_item257和tree_rmap_item添加到table_node_dup1->hlist链表中。此时, stable_nodde_dup1->rmap_hist_len的值为2, ksm_pages_shared为2, ksm_pages_sharing为256整个过程如图所示

接下来,扫描第259个页面(page258)。具休过程如下。

  • 遍历stable 红黑树,见 stable_tree_searen()函数。
  • 调用 chain_prune()->__stable_node_chain()函数,由于当前的节点是链式稳定的节点,因此直接调用 stabie_node_dup()函数,详见 stable_node_dup()函数
  • 在stabie_node_dup()函数中遍历稳定的节点所在的 hlist 链表中所有的rmap_item,查找一个hlist链表中还有空间的 rmap_item。然后返回这个rmap_item对应的页面,另外stabie_node_dup指向rmap_item.此时,链式稳定的节点有两个 stable_nale_dup()分别是stabie_node_dup0和stabie_node_dup1,只有 stable_node_dup1还有空间容纳rmap_item,因此返回stabie_node_dup1对应的页面。
  • 在stable_tree_search()函数中,发现第259个页面和stabie_node_dup1对应的页面内容相同,因此返回 stabie_node_dup1对应的页面,它称为tree_page
  • 调用try_to_merge_with_ksm_page()尝试合并page258到 tree_page中。调用 stable_tree_append()函数把 rmap_item258添加到 stable_node_dup1的hlist 链表中, rmap_hlist_len的值变成了3,ksages_sharing变成了257整个过程如图所示:

接下来,扫描其他页面。具体过程如下。

(1)继续扫描其他页面,直到 stable_node_dup1->hlist链表满员为止。 (2)重复扫描第257个和第258个页面,新创建一个node_dup2节点,添加到链式稳定的节点的hlist链表中,新的 rmap_item就可以继续添加到node_dup2->hlist 链表中了。 综上所述,我们们发现新版本的KSM机制有:

  • 上述1000个相同页面会生成多个KSM页面,上图9所示的 page1是第一个KSM页面,page257是第二个KSM页面,以此类推。而在旧版本的KSM机制中,1000个页面会生成一个KSM页面,另外的999个页面都会合并到这个KSM页面中。
  • 每个KSM页面最多把256个页面合并在一起,其中还包括KSM页面自己,即最多有255个其他的页面被合并。

当RMAP机制需要遍历KSM页面时,它只需要遍历256个 rmap_items即可。如当需要迁移page1时,可以通过 page1找到 stable_node_dup0节点,因此只需要遍历和处理 node_dup0->hlist链表中的第256个rmap_items就可以迁移 page1.

malloc函数分配的内存是不能被KSM扫描的,malloc()函数分配的虚拟内存没办法保证一定是按照页面对齐的,但在madvise系统调用中,要求起始地址是按照页面对齐的。

小结

KSM的核心设计思想基于写时复制机制,也就是内容相同的页面可以合并成一个只读页面,从而释放空闲页面。 KSM最早是为了KVM虚拟机而设计的,KVM虚拟机在宿主机上使用的页面大部分是匿名页面,并且它们在宿主机中存在大量的冗余内存。对于典型的应用程序,KSM只考虑进程分配使用的匿名页面,暂时不考虑页面高速缓存的情况。一个典型的应用程序可以由以下5个内存部分组成

  • 可执行文件的内存映射(页面高速缓存)
  • 程序打开使用的匿名页面
  • 进程打开的文件映射(包括常用的或者不常用的,甚至只用一次的页面高速缓存)
  • 进程访问文件系统时产生的内容缓存
  • 进程访问内核产生时的内核缓冲器(如slab)等

设计的关键是如何寻找和比较两个相同的页面,如何让这个过程变得高效而且占用的系统资源最少,这就是一个好的设计人员应该思考的问题。首先不能用哈希算法来比较两个页面的专利问题。KSM虽然使用了 memcmp来比较,最糟糕的情况是两个页面最后的4字节不一样但是KSM使用红黑树来设计了两棵树,分别是稳定的红黑树和不稳定的红黑树,可以有效地避免最糟糕的情况。另外,KSM也巧妙地利用页面的校验和来比较不稳定的红黑树的页面最近是否被修改过,从而避开了该专利的缺陷。 页面分为物理页面和虚拟页面,多个虚拟页面可以同时映射到一个物理页面,因此需要把映射到该页面的所有PTE都解除后,才是算真正释放(这里说的PTE是指用户进程地止空间的虚拟地址映射的该页面的PTE,简称用户PTE,因此page->__mapcount成员里描述的PTE数量不包含内核线性映射的PTE)。目前有两种做法,一种做法是扫描每个进程中用户地址进程空间,由用户地址进程空间的虚拟地址查询MMU页表,找到对应的page数据结构,这样就找到了用户PTE。然后对比KSM中的稳定树和不稳定树,如果找到页面内容相同的,就把该PTE设置成写时复制,映射到KSM页面中,从而释放出一个PTE。注意,这里是释放出一个用户PTE,而不是一个物理页面(如果该物理页面只有一个PTE映射,那就是释放该页)。另外一种做法是直接扫描系统中的物理页面,然后通过RMAP来解除该页面所有的用户PTE,从而一次性地释放出物理页面。显然,目前内核的KSM是基于第一种做法。 KSM的作者在他的论文中有实测数据,但作者依然覚得有一些情况下会比较糟糕。如在一个很大内存的服务器上,很多的匿名页面都同时映射了多个虚拟页面。假设每个匿名页面都映射了1000个虚拟页面,这些虚拟页面又同时分布在不同的子进程中,那么要释放一个物理页面,需要扫描完1000个虚拟页面所在的用户地址进程空间,每次都要利用 follow_page() 查询页表,然后査询稳定树,还需要多次执行 memcmp比较,合并10000次PTE也就意味着 memcmp要执行10000次,这个过程会很漫长,在实际项目中,有很多人抱怨KSM的效率低,在很多项目是关闭该特性的。也有很多人在思考如何提高KSM的效率,包括利用新的软件算法或者利用硬件机制。

参考文献

《奔跑吧Linux内核》