2018-09-13 16:37:22 weixin_42963076 阅读数 519

作为一个系统管理程序(hypervisor),Linux® 有几个创新,2.6.32 内核中一个有趣的变化是 KSM(Kernel Samepage Merging) 允许这个系统管理程序通过合并内存页面来增加并发虚拟机的数量。Linux UKSM 是国人自主研发的一个 Linux 内核相关项目,这个项目对服务器和桌面应用都可以显著的减少 Linux 系统冗余的内存,已经在 RHEL6、CentOS 6、Ubuntu 12.04 等系统充分验证和测试过。Linux相同页面合并机制(KSM)使得内存中相同的页面,可以通过修改页表的方式合并成一个。通常这个机制被应用在有众多虚拟机(目前仅支持 KVM)或者有很多冗余内存数据的场景(如有很多类似数据工作集的并行科学计算)里面。但是,目前它的实现方式仍然比较简陋,UKSM的出现,彻底消除了KSM原本局限,真正使得这项技术能被更多的普通用户使用。
众所周知,Android 内核衍生自Linux,但因平台特性,Android Kernel与 Linux Kernel演变出分歧,KSM和UKSM是意在解决内存冗余占用问题开发出的两个内核模块,他们在安装运行多个虚拟机宿主Host上表现相当出色。尤其是UKSM,较于KSM,有较高的性能、透明度和安全性,被广大Kernel内核开发人员和大型服务器用户所青睐。
我们的产品内存有限,合并冗余的内存占用,从内存优化的角度出发,KSM和UKSM无疑是比较好的选择。以下我们针对KSM和UKSM的表现作出测试,以作为UKSM和KSM是否登录产品的决策依据。
说明:KSM在Android Kernel 3.10时代就已经集成,内核开关为 CONFIG_KSM,依赖开关为CONFIG_MMU,UKSM为国人解决服务器冗余内存占用研发,可供参考的版本为0.1.2.3-for-v3.1 ~~~0.1.2.5-for-v3.18。

测试条件:
1.机型:(1G RAM/ MT6580);
2.平台:Android 7.1;
3.内核:Kernel 3.18
测试步骤:
测试机在内核中集成uksm模块,对比机关闭uksm模块,打开ksm开关,使用原生ksm模块做内存合并。测试机与对比机测试方法相同。正常开机开始统计数据(ksm和uksm守护进程CPU占用、整机内存剩余占用),开机手机静置10min,随即开始使用native应用test.bin进行内存申请和填充 “test 200 1”,申请200M内存,整块内存区域使用’1’填充,等待两分钟后重复申请填充,第4分钟同上,等待2分钟,终止数据抓取脚本。
测试原理:
测试机器在正常运行过程中,ksm/uksm对内存合并的积极性、合并效率(内存曲线展示)以及在此过程中的cpu开销(top数据体现)。

数据分析:
16min测试中对比机(ksm)和测试机(uksm)的内存波动。分析,在手机静置的10min中,uksm合并不如ksm积极,现象是在此过程中整机内存uksm略少于ksm,这一值约为30~40M。分别在10min、12min和14min时由test发起的内存申请可以看出,uksm对此200M内存的合并速度远远快于ksm,即uksm遍历合并完成200M内存耗时16s,而ksm完成此过程需要平均60s。
合并动作发生时的内存波动,可以直观展示合并效率
下面是top -m 50 中的ksmd/ukamd信息,可以看出uksm对CPU的利用率非常高,而就内存页检测而言,cpu占用稳定在1%一下,而此数据在ksmd上为均值26%,而且整机运行过程中,ksmd的cpu占用持续高波动,对功耗产生的压力较大。
这里写图片描述

这项数据表明,UKSM在Android上的表现确实优于KSM,无论从速度还是CPU资源消耗的角度。但是在小内存设备上并没有什么优势,亲测:累死累活得合并10~15M内存,功耗上来了,犯不着费这个劲,指着大内存设备上验证是否有用,毕竟国内的牛人当初整出来UKSM就是针对虚拟机服务器这种使用场景。

Linux KSM
2018-04-01 19:36:36 letterwuyu 阅读数 2643

转载:http://www.cnblogs.com/zhangzhang/archive/2012/05/23/2514336.html

简介:作为一个系统管理程序(hypervisor),Linux® 有几个创新,2.6.32 内核中一个有趣的变化是 KSM(Kernel Samepage Merging)  允许这个系统管理程序通过合并内存页面来增加并发虚拟机的数量。本文探索 KSM 背后的理念(比如存储去耦合)、KSM 的实现、以及如何管理 KSM。

服务器虚拟化

     虚拟化技术从上世纪 60 年代开始出现,经由 IBM® System/360® 大型机得以流行。50 年过后,虚拟化技术取得了跨越式发展,使得多个操作系统和应用程序共享一个服务器成为可能。这一特殊用途(称为服务器虚拟化)正在演变为数据中心,因为单个物理机能够用于托管 10 个(一般情况)或更多虚拟机(VM),如图 1 所示。这种虚拟化使基础设施更动态、更省电、(因而也)更经济。

图 1. 通过虚拟化进行的服务器合并

      页面都是相同的。假如操作系统和应用程序代码以及常量数据在 VMs 之间相同,那么这个特点就很有用。当页面惟一时,它们可以被合并,从而释放内存,供其他应用程序使用。图 2 演示了内存共享,并展示了在内容相同的 VMs 之间共享页面时更多可用闲置内存的好处。 

图 2. 跨 VMs 的内存共享

特性命名
     本文描述的特性非常新;因此,其名称经历了一些变化。您将发现这个 Linux 内核特性称为 Kernel Shared Memory 或 Kernel Samepage Merging。

     您很快就会发现,尽管 Linux 中的内存共享在虚拟环境中有优势(KSM 最初设计用于基于内核的虚拟机),但它在非虚拟环境中仍然有用。事实上,KSM 甚至在嵌入式 Linux 系统中也有用处,表明了这种方法的灵活性。下面,我们将探索这种 Linux 内存共享方法,以及如何使用该方法提高服务器的内存密度,从而增加其托管其他应用程序或 VMs 的能力。

 

其他技术支持

     存储技术中的一个称为去耦合(de-duplication)的最新进展是 Linux 和其他系统管理程序中的内存共享的先驱。去耦合这种技术通过删除冗余数据(基于数据块,或者基于更大的数据片段,比如文件)来减少已存储的数据。公共数据片段被合并(以一种 copy-on-write [CoW] 方式),释放空间供其他用途。使用这种方法,存储成本更低,最终需要的存储器也更少。鉴于当前的数据增长速度,这个功能显得非常重要。

 

KSM 操作

     KSM 作为内核中的守护进程(称为 ksmd)存在,它定期执行页面扫描,识别副本页面并合并副本,释放这些页面以供它用。KSM 执行上述操作的过程对用户透明。例如,副本页面被合并(然后被标记为只读),但是,如果这个页面的其中一个用户由于某种原因更改该页面,该用户将(以 CoW 方式)收到自己的副本。可以在内核源代码 ./mm/ksm.c 中找到 KSM 内核模块的完整实现。

     KSM 依赖高级应用程序来提供指导,根据该指导确定合并的候选内存区域。尽管 KSM 可以只扫描系统中的匿名页面,但这将浪费 CPU 和内存资源(考虑到管理页面合并进程所需的空间)。因此,应用程序可以注册可能包含副本页面的虚拟区域。

     KSM 应用程序编程接口(API)通过 madvise 系统调用(见清单 1)和一个新的建议参数(advice parameter)MADV_MERGEABLE(表明已定义的区域可以合并)来实现。可以通过 MADV_UNMERGEABLE 参数(立即从一个区域取消合并任何已合并页面)从可合并状态删除一个区域。注意,通过 madvise 来删除一个页面区域可能会导致一个 EAGAIN 错误,因为该操作可能会在取消合并过程中耗尽内存,从而可能会导致更大的麻烦(内存不足情况)。

清单 1. madvise 系统调用

#include <sys/mman.h>

int madvise( void *start, size_t length, int advice );

     一旦某个区域被定义为 “可合并”,KSM 将把该区域添加到它的工作内存列表。启用 KSM 时,它将搜索相同的页面,以写保护的 CoW 方式保留一个页面,释放另一个页面以供它用。

     KSM 使用的方法与内存去耦合中使用的方法不同。在传统的去耦合中,对象被散列化,然后使用散列值进行初始相似性检查。当散列值一致时,下一步是进行一个实际对象比较(本例中是一个内存比较),以便正式确定这些对象是否一致。KSM 在它的第一个实现中采用这种方法,但后来开发了一种更直观的方法来简化它。

     在当前的 KSM 中,页面通过两个 “红-黑” 树管理,其中一个 “红-黑” 树是临时的。第一个树称为不稳定树,用于存储还不能理解为稳定的新页面。换句话说,作为合并候选对象的页面(在一段时间内没有变化)存储在这个不稳定树中。不稳定树中的页面不是写保护的。第二个树称为稳定树,存储那些已经发现是稳定的且通过 KSM 合并的页面。为确定一个页面是否是稳定页面,KSM 使用了一个简单的 32 位校验和(checksum)。当一个页面被扫描时,它的校验和被计算且与该页面存储在一起。在一次后续扫描中,如果新计算的校验和不等于此前计算的校验和,则该页面正在更改,因此不是一个合格的合并候选对象。

     使用 KSM 进程处理一个单一的页面时,第一步是检查是否能够在稳定树中发现该页面。搜索稳定树的过程很有趣,因为每个页面都被视为一个非常大的数字(页面的内容)。一个 memcmp(内存比较)操作将在该页面和相关节点的页面上执行。如果 memcmp 返回 0,则页面相同,发现一个匹配值。反之,如果 memcmp 返回 -1,则表示候选页面小于当前节点的页面;如果返回 1,则表示候选页面大于当前节点的页面。尽管比较 4KB 的页面似乎是相当重量级的比较,但是在多数情况下,一旦发现一个差异,memcmp 将提前结束。请参见图 3 查看这个过程的视觉呈现。

图 3. 搜索树中的页面的搜索过程

     如果候选页面位于稳定树中,则该页面被合并,候选页面被释放。有关代码位于 ksm.c/stable_tree_search()(称为 ksm.c/cmp_and_merge_page())中。反之,如果没有发现候选页面,则应转到不稳定树(参见 ksm.c/unstable_tree_search())。

     在不稳定树中搜索时,第一步是重新计算页面上的校验和。如果该值与原始校验和不同,则本次扫描的后续搜索将抛弃这个页面(因为它更改了,不值得跟踪)。如果校验和没有更改,则会搜索不稳定树以寻找候选页面。不稳定树的处理与稳定树的处理有一些不同。第一,如果搜索代码没有在不稳定树中发现页面,则在不稳定树中为该页面添加一个新节点。但是如果在不稳定树中发现了页面,则合并该页面,然后将该节点迁移到稳定树中。

     当扫描完成(通过 ksm.c/ksm_do_scan() 执行)时,稳定树被保存下来,但不稳定树则被删除并在下一次扫描时重新构建。这个过程大大简化了工作,因为不稳定树的组织方式可以根据页面的变化而变化(还记得不稳定树中的页面不是写保护的吗?)。由于稳定树中的所有页面都是写保护的,因此当一个页面试图被写入时将生成一个页面故障,从而允许 CoW 进程为写入程序取消页面合并(请参见 ksm.c/break_cow())。稳定树中的孤立页面将在稍后被删除(除非该页面的两个或更多用户存在,表明该页面还在被共享)。

     如前所述,KSM 使用 “红-黑” 树来管理页面,以支持快速查询。实际上,Linux 包含了一些 “红-黑” 树作为一个可重用的数据结构,可以广泛使用它们。“红-黑” 树还可以被 Completely Fair Scheduler (CFS) 使用,以便按时间顺序存储任务。您可以在 ./lib/rbtree.c 中找到 “红-黑” 树的这个实现。

 

KSM 配置和监控

     KSM 的管理和监控通过 sysfs(位于根 /sys/kernel/mm/ksm)执行。在这个 sysfs 子目录中,您将发现一些文件,有些用于控制,其他的用于监控。

     第一个文件 run 用于启用和禁用 KSM 的页面合并。默认情况下,KSM 被禁用(0),但可以通过将一个 1 写入这个文件来启用 KSM 守护进程(例如,echo 1 > sys/kernel/mm/ksm/run)。通过写入一个 0,可以从运行状态禁用这个守护进程(但是保留合并页面的当前集合)。另外,通过写入一个 2,可以从运行状态(1)停止 KSM 并请求取消合并所有合并页面。

     KSM 运行时,可以通过 3 个参数(sysfs 中的文件)来控制它。sleep_millisecs 文件定义执行另一次页面扫描前 ksmd 休眠的毫秒数。max_kernel_pages 文件定义 ksmd 可以使用的最大页面数(默认值是可用内存的 25%,但可以写入一个 0 来指定为无限)。最后,pages_to_scan 文件定义一次给定扫描中可以扫描的页面数。任何用户都可以查看这些文件,但是用户必须拥有根权限才能修改它们。

     还有 5 个通过 sysfs 导出的可监控文件(均为只读),它们表明 ksmd 的运行情况和效果。full_scans 文件表明已经执行的全区域扫描的次数。剩下的 4 个文件表明 KSM 的页面级统计数据:

•pages_shared:KSM 正在使用的不可交换的内核页面的数量。 
•pages_sharing:一个内存存储指示。 
•pages_unshared:为合并而重复检查的惟一页面的数量。 
•pages_volatile:频繁改变的页面的数量。 
     KSM 作者定义:较高的 pages_sharing/pages_shared 比率表明高效的页面共享(反之则表明资源浪费)。

结束语

     Linux 并不是使用页面共享来改进内存效率的惟一系统管理程序,但是它的独特之处在于将其实现为一个  操作系统特性。VMware 的 ESX 服务器系统管理程序将这个特性命名为 Transparent Page Sharing (TPS),而 XEN 将其称为 Memory CoW。不管采用哪种名称和实现,这个特性都提供了更好的内存利用率,从而允许操作系统(KVM 的系统管理程序)过量使用内存,支持更多的应用程序或 VM。 您可以在最新的 2.6.32 Linux 内核中发现 KSM — 以及其他很多有趣的特性。

ksm
2012-06-21 13:47:05 wzb56 阅读数 1346

 Linux Kernel UKSM, 国内牛人研发的一个 Linux 内核相关项目

相信玩过kvm虚拟机的同学,有些可能听说过ksm(Kernel SamePage Merging ),这是一个linux核心一个内存管理机制,通过算法优化,合并内存中类似或相同的页面,提高内存的利用效率。特别相对虚拟化这类技术。比如一个系统正运行这好几个guest实例,那么就可以通过这种技术共享相同代码,比如每个guest的核心代码,那么随着guest实例增加,内存不会急剧的下降,有效的增加host的provisioning能力。而国内的能人将这一技术进一步优化,通过改进算法,对服务器和桌面应用都可以显著的减少 Linux 系统冗余的内存,

UKSM的特性包括:
全系统扫描,用户透明:能扫描所有应用程序(包括 KVM 虚拟机)中匿名映射区域的页面,不需要开发者修改一行程序就能从中获益。
极大提高了工作效率,其页面合并的速度,最高可比原本的 KSM 快 20 倍以上。
非常节省CPU,如果系统当中没有冗余页面,那么其 CPU 占用几乎观察不到,而一旦系统当中出现了冗余的内存的时候,它又能快速发现加以消除。
具体的评测请看这里:http://kerneldedup.org/projects/uksm/benchmarks/,评测数据显示,其效率相当给力!
现在 UKSM 已经发布了最新的内核 v3.3,并且提供主流发行版本(centos 6/ubuntu 12.04/Fedora 16/Archlinux/)内核基础上UKSM补丁过的内核安装包下载:http://kerneldedup.org/projects/uksm/download/
欢迎广大网友们使用,并反馈意见!
项目官方站点:http://kerneldedup.org/
参考资料:
http://en.wikipedia.org/wiki/Kernel_SamePage_Merging_(KSM)
http://www.linux-kvm.com/content/using-ksm-kernel-samepage-merging-kvm

因为众所周知的原因(详见:http://zh.wikipedia.org/zh/%E9%98%B2%E7%81%AB%E9%95%BF%E5%9F%8E,http://t.cn/zOTcws5 http://t.cn/GxowJ ),

国内无法访问很多国外的网站,甚至包话众多的科技和学术站点,那么vpn(http://zh.wikipedia.org/wiki/%E8%99%9B%E6%93%AC%E7%A7%81%E4%BA%BA%E7%B6%B2%E8%B7%AF,http://en.wikipedia.org/wiki/Vpn)     

 为你查阅学术自来带来很大方便。好处还有很多,不便列举。只要你走出第一步,认识到有些东西的存在,那么很多慢慢也就晓得了。

2017-12-10 15:50:47 SIFT2009 阅读数 1176

ksm 是kernel samepage merge的简称,它会定期进行页而扫描,并把识别到的内存页副本进行合并,进而释放这些页面以供其他程序使用。通常合并后的页会被置为只读,当有其他程序要更改这个页面时,就会触发cow机制。系统会重新为这个程序单独生成一份副本

ksm机制

ksm维护两棵树,一棵stable树,一棵unstable树。其中stable树上维护的是已经merged过的页,由于这些页都是只读的所以基本上比较稳定。
另外一棵是unstable树,这个棵树维护的页是在一段时间内没有改变过的页,但不能保证过了这段时间会不会发生变化

具体逻辑

当分配内存时,用户可以通过madvise系统调用,将要扫描的区域加到ksm扫描的列表里面。接着,内核会起一个ksmd的系统进程,定期进行扫描。看一下具体代码

static void ksm_do_scan(unsigned int scan_npages)                                   
{                                                                                   
    struct rmap_item *rmap_item;                                                    
    struct page *uninitialized_var(page);                                           
    /* scan_npages 一次扫描的页数 */                                                                                
    while (scan_npages-- && likely(!freezing(current))) {                           
        cond_resched(); 
        /*对区间的每个page进行扫描 */                                                            
        rmap_item = scan_get_next_rmap_item(&page);                                 
        if (!rmap_item)                                                             
            return;                                                                 
        cmp_and_merge_page(page, rmap_item);                                                
        put_page(page);                                                             
    }                                                                               
}                                                                             

在分析scan_get_next_rmap_item之前,我们先来看一下struct rmap_item这个数据结构,

struct rmap_item {                                                                  
    struct rmap_item *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;                                                
        };                                                                          
    };                                                                              
};                                                                                  

这个结构描述的是虚拟地址的一个反向映射,也就是说从一个虚拟地址可以找到一个mm slot。接着,继续分析scan_get_next_rmap_item

static struct rmap_item *scan_get_next_rmap_item(struct page **page)            
{                                                                               
    struct mm_struct *mm;                                                       
    struct mm_slot *slot;                                                       
    struct vm_area_struct *vma;                                                 
    struct rmap_item *rmap_item;                                                
    int nid;                                                                    
    /* 如果扫描列表是空的则返回*/                                                                            
    if (list_empty(&ksm_mm_head.mm_list))                                       
        return NULL;                                                            

    slot = ksm_scan.mm_slot;                                                    
    if (slot == &ksm_mm_head) {                                                 
        /*                                                                      
         * A number of pages can hang around indefinitely on per-cpu            
         * pagevecs, raised page count preventing write_protect_page            
         * from merging them.  Though it doesn't really matter much,            
A         * it is puzzling to see some stuck in pages_volatile until             
         * other activity jostles them out, and they also prevented             
         * LTP's KSM test from succeeding deterministically; so drain           
         * them here (here rather than on entry to ksm_do_scan(),               
         * so we don't IPI too often when pages_to_scan is set low).            
         */                                                                     
        lru_add_drain_all();                                                    

        /*                                                                      
         * Whereas stale stable_nodes on the stable_tree itself                 
         * get pruned in the regular course of stable_tree_search(),            
         * those moved out to the migrate_nodes list can accumulate:            
         * so prune them once before each full scan. */

        if (!ksm_merge_across_nodes) {                                          
            struct stable_node *stable_node, *next;                             
            struct page *page;                                                  

            list_for_each_entry_safe(stable_node, next,                         
                         &migrate_nodes, list) {                                
                page = get_ksm_page(stable_node, false);                        
                if (page)                                                       
                    put_page(page);                                             
                cond_resched();                                                 
            }                                                                   
        }                                                                       

        for (nid = 0; nid < ksm_nr_node_ids; nid++)                             
            root_unstable_tree[nid] = RB_ROOT;                                  

        spin_lock(&ksm_mmlist_lock); 
        /*获取扫描的slot*/                                           
        slot = list_entry(slot->mm_list.next, struct mm_slot, mm_list);         
        ksm_scan.mm_slot = slot;                                                
        spin_unlock(&ksm_mmlist_lock);                                          
        /*                                                                      
         * Although we tested list_empty() above, a racing __ksm_exit           
         * of the last mm on the list may have removed it since then.           
         */  
         /*做double check 避免竞争*/                                                                   
        if (slot == &ksm_mm_head)                                               
            return NULL;                                                        
next_mm:                                                                        
        ksm_scan.address = 0;                                                   
        ksm_scan.rmap_list = &slot->rmap_list;                                  

}
    mm = slot->mm;                                                              
    down_read(&mm->mmap_sem);                                                   
    if (ksm_test_exit(mm))                                                      
        vma = NULL;                                                             
    else 
        /*根据address在mm里面找到vma*/                                                                       
        vma = find_vma(mm, ksm_scan.address);                                   

    for (; vma; vma = vma->vm_next) { 
        /*vma类型必须是VM_MERGEABLE才能进行合并*/                                          
        if (!(vma->vm_flags & VM_MERGEABLE))                                    
            continue;                                                           
        if (ksm_scan.address < vma->vm_start)                                   
            ksm_scan.address = vma->vm_start; 
            /*vma必须是anon*/                                  
        if (!vma->anon_vma)                                                     
            ksm_scan.address = vma->vm_end;                                     

        while (ksm_scan.address < vma->vm_end) {                                
            if (ksm_test_exit(mm))                                              
                break; 
            /*根据虚拟地址获取物理页*/                                                         
            *page = follow_page(vma, ksm_scan.address, FOLL_GET);               
            if (IS_ERR_OR_NULL(*page)) {                                        
                ksm_scan.address += PAGE_SIZE;                                  
                cond_resched();                                                 
                continue;                                                       
            } 
            /*必须是anon page*/                                                                  
            if (PageAnon(*page)) {                                              
                flush_anon_page(vma, *page, ksm_scan.address);                  
                flush_dcache_page(*page);
                /*创建rmat_item*/                                       
                rmap_item = get_next_rmap_item(slot,                            
                    ksm_scan.rmap_list, ksm_scan.address);                      
                if (rmap_item) {                                                
                    ksm_scan.rmap_list =                                        
                            &rmap_item->rmap_list;                              
                    ksm_scan.address += PAGE_SIZE;                              
                } else                                                          
                    put_page(*page);                                            
                up_read(&mm->mmap_sem);                                         
                return rmap_item;                                               
            }                                                                   
            put_page(*page);                                                    
            ksm_scan.address += PAGE_SIZE;                                      
            cond_resched();                                                     
        }                                                                       
    }                                                                           

    /*没有找到*/                                                                          
    if (ksm_test_exit(mm)) {                                                    
        ksm_scan.address = 0;                                                   
        ksm_scan.rmap_list = &slot->rmap_list;                                  
    } 

    /*将slot从scan的rmap_list中去除*/
    remove_trailing_rmap_items(slot, ksm_scan.rmap_list);                       

    spin_lock(&ksm_mmlist_lock);                                                
    ksm_scan.mm_slot = list_entry(slot->mm_list.next,                           
                        struct mm_slot, mm_list);                               
    if (ksm_scan.address == 0) {                                                
        /*                                                                      
         * We've completed a full scan of all vmas, holding mmap_sem            
         * throughout, and found no VM_MERGEABLE: so do the same as             
         * __ksm_exit does to remove this mm from all our lists now.            
         * This applies either when cleaning up after __ksm_exit                
         * (but beware: we can reach here even before __ksm_exit),              
         * or when all VM_MERGEABLE areas have been unmapped (and               
         * mmap_sem then protects against race with MADV_MERGEABLE).            
         */                                                                     
        hash_del(&slot->link);                                                  
        list_del(&slot->mm_list);                                               
        spin_unlock(&ksm_mmlist_lock);                                          

        free_mm_slot(slot);                                                     
        clear_bit(MMF_VM_MERGEABLE, &mm->flags);                                
        up_read(&mm->mmap_sem);                                                 
        mmdrop(mm);                                                             
    } else {                                                                    
        up_read(&mm->mmap_sem);                                                 
        /*                                                                      
         * up_read(&mm->mmap_sem) first because after                           
         * spin_unlock(&ksm_mmlist_lock) run, the "mm" may                      
         * already have been freed under us by __ksm_exit()                     
         * because the "mm_slot" is still hashed and                            
         * ksm_scan.mm_slot doesn't point to it anymore.                        
         */                                                                     
        spin_unlock(&ksm_mmlist_lock);                                          
    }                                                                           

    /* Repeat until we've completed scanning the whole list */  
    /*继续扫描*/                
    slot = ksm_scan.mm_slot;                                                    
    if (slot != &ksm_mm_head)                                                   
        goto next_mm;                                                           

    ksm_scan.seqnr++;                                                           
    return NULL;                                                                
}                                         
static void cmp_and_merge_page(struct page *page, struct rmap_item *rmap_item)  
{                                                                               
    struct rmap_item *tree_rmap_item;                                           
    struct page *tree_page = NULL;                                              
    struct stable_node *stable_node;                                            
    struct page *kpage;                                                         
    unsigned int checksum;                                                      
    int err;                                                                    

    stable_node = page_stable_node(page);                                       
    if (stable_node) { 
       /*如果是ksm page但是不在migrate_nodes 列表上,但是nid不同*/                                                         
        if (stable_node->head != &migrate_nodes &&                              
            get_kpfn_nid(stable_node->kpfn) != NUMA(stable_node->nid)) {        
            rb_erase(&stable_node->node,                                        
                 root_stable_tree + NUMA(stable_node->nid));                    
            stable_node->head = &migrate_nodes;                                 
            list_add(&stable_node->list, stable_node->head);                    
        } 
        /*如果这个页不在migrate_nodes lits上,但是rmap_item在stable_node 说明这个是ksm page fork出来的*/                                                                      
        if (stable_node->head != &migrate_nodes &&                              
            rmap_item->head == stable_node)                                     
            return;                                                             
    }                                                                           

    /* We first start with searching the page inside the stable tree */  
    /*先在stable树上找到这个page*/       
    kpage = stable_tree_search(page); 
    /*如果是同一个page则直接把这个page释放,并返回*/                                          
    if (kpage == page && rmap_item->head == stable_node) {                      
        put_page(kpage);                                                        
        return;                                                                 
    } 

    /*暂时将rmap_item从list中去除 */
    remove_rmap_item_from_tree(rmap_item);                                          

    if (kpage) { 
        /*尝试去合并这两个page*/                                                                   
        err = try_to_merge_with_ksm_page(rmap_item, page, kpage);                   
        if (!err) {                                                                 
            /*                                                                      
             * The page was successfully merged:                                    
             * add its rmap_item to the stable tree.                                
             */                                                                     
            lock_page(kpage);  
            /*如果合并成功,则半rmap_item添加到stable tree*/                                                     
            stable_tree_append(rmap_item, page_stable_node(kpage));                 
            unlock_page(kpage);                                                     
        }                                                                           
        put_page(kpage);                                                            
        return;                                                                     
    }
        /*                                                                                                                                                                            
     * If the hash value of the page has changed from the last time             
     * we calculated it, this page is changing frequently: therefore we         
     * don't want to insert it in the unstable tree, and we don't want          
     * to waste our time searching for something identical to it there.         
     */ 
     /*如果page 变化频率比较高,则先不要把它放到unstable树上*/                                                                        
    checksum = calc_checksum(page);                                             
    if (rmap_item->oldchecksum != checksum) {                                   
        rmap_item->oldchecksum = checksum;                                      
        return;                                                                 
    }                                                                           

    /*                                                                          
     * Same checksum as an empty page. We attempt to merge it with the          
     * appropriate zero page if the user enabled this via sysfs.                
     */                                                                         
    if (ksm_use_zero_pages && (checksum == zero_checksum)) {                    
        struct vm_area_struct *vma;                                             

        vma = find_mergeable_vma(rmap_item->mm, rmap_item->address);            
        err = try_to_merge_one_page(vma, page,                                  
                        ZERO_PAGE(rmap_item->address));                         
        /*                                                                      
         * In case of failure, the page was not really empty, so we             
         * need to continue. Otherwise we're done.                              
         */                                                                     
        if (!err)                                                               
            return;                                                             
    }  
    /*如果变化的频率不是很高,则在非稳定树上找到相同页*/
        tree_rmap_item =                                                            
        unstable_tree_search_insert(rmap_item, page, &tree_page);               
    if (tree_rmap_item) {  
        /*尝试合并这两个页*/                                                     
        kpage = try_to_merge_two_pages(rmap_item, page,                         
                        tree_rmap_item, tree_page);                             
        put_page(tree_page);                                                    
        if (kpage) {                                                            
            /*                                                                  
             * The pages were successfully merged: insert new                   
             * node in the stable tree and add both rmap_items.                 
             */  
             /*如果合并成功,则把这个page插入到stable stree上*/                                                               
            lock_page(kpage);                                                   
            stable_node = stable_tree_insert(kpage);                            
            if (stable_node) {
                /*把两个rmap_item都放到stable_node的hash 表上*/                                                  
                stable_tree_append(tree_rmap_item, stable_node);                
                stable_tree_append(rmap_item, stable_node);                     
            }                                                                   
            unlock_page(kpage);                                                 

            /*                                                                  
             * If we fail to insert the page into the stable tree,              
             * we will have 2 virtual addresses that are pointing               
             * to a ksm page left outside the stable tree,                      
             * in which case we need to break_cow on both.                      
             */                                                                 
            if (!stable_node) {                                                 
/*如果失败,则把ksm page 再copy一份给正在发起写动作的应用,*/                break_cow(tree_rmap_item);                                      
                break_cow(rmap_item);                                           
            }                                                                   
        }                                                                       
    }                                                                           
}                                                                                                                   

看一下merge_with_ksm_page逻辑

static int try_to_merge_with_ksm_page(struct rmap_item *rmap_item,              
                      struct page *page, struct page *kpage)                    
{   
    /*通过rmap_item找到 mm*/                                                                            
    struct mm_struct *mm = rmap_item->mm;                                       
    struct vm_area_struct *vma;                                                 
    int err = -EFAULT;                                                          

    down_read(&mm->mmap_sem); 
    /*通过虚拟地址找到vma区域*/                                                  
    vma = find_mergeable_vma(mm, rmap_item->address);                           
    if (!vma)                                                                   
        goto out;                                                               

    err = try_to_merge_one_page(vma, page, kpage);                              
    if (err)                                                                    
        goto out;                                                               

    /* Unstable nid is in union with stable anon_vma: remove first */           
    remove_rmap_item_from_tree(rmap_item);                                      

    /* Must get reference to anon_vma while still holding mmap_sem */           
    rmap_item->anon_vma = vma->anon_vma;                                        
    get_anon_vma(vma->anon_vma);                                                
out:                                                                            
    up_read(&mm->mmap_sem);                                                     
    return err;                                                                 
}                

看一下try_to_merge_one_page这个函数的逻辑

static int try_to_merge_one_page(struct vm_area_struct *vma,                    
                 struct page *page, struct page *kpage)                         
{                                                                               
    pte_t orig_pte = __pte(0);                                                  
    int err = -EFAULT;                                                          
     /*如果两个page相等说明是通过ksm page fork出来的*/                                                                           
    if (page == kpage)          /* ksm page forked */                           
        return 0;                                                               
     /*如果不是匿名页则跳出*/                                                                           
    if (!PageAnon(page))                                                        
        goto out;                                                               

    /*                                                                          
     * We need the page lock to read a stable PageSwapCache in                  
     * write_protect_page().  We use trylock_page() instead of                  
     * lock_page() because we don't want to wait here - we                      
     * prefer to continue scanning and merging different pages,                 
     * then come back to this page when it is unlocked.                         
     */                                                                         
    if (!trylock_page(page))                                                    
        goto out;                                                               
    /*如果是大页,则需要split*/                                                                            
    if (PageTransCompound(page)) {                                              
        err = split_huge_page(page);                                            
        if (err)                                                                
            goto out_unlock;                                                    
    }                                                                           

    /*                                                                          
     * If this anonymous page is mapped only here, its pte may need             
     * to be write-protected.  If it's mapped elsewhere, all of its             
     * ptes are necessarily already write-protected.  But in either             
     * case, we need to lock and check page_count is not raised.                
     */                                                                         
    if (write_protect_page(vma, page, &orig_pte) == 0) {                        
        if (!kpage) {                                                           
            /*                                                                  
             * While we hold page lock, upgrade page from                       
             * PageAnon+anon_vma to PageKsm+NULL stable_node:                   
             * stable_tree_insert() will update stable_node.                    
             */                                                                 
            set_page_stable_node(page, NULL);                                   
            mark_page_accessed(page);                                           
            /*                                                                  
             * Page reclaim just frees a clean page with no dirty               
             * ptes: make sure that the ksm page would be swapped.              
             */                                                                 
            if (!PageDirty(page))                                               
                SetPageDirty(page);                                             
            err = 0;  
            else if (pages_identical(page, kpage))  
                /*如果页内容相同,则替换*/ 
                err = replace_page(vma, page, kpage, orig_pte);               
}    
 /*如果vma 类型是VM_LOCKED 还需要把原来的page解锁,否则无法释放*/       
if ((vma->vm_flags & VM_LOCKED) && kpage && !err) {                         
        munlock_vma_page(page);                                                     
        if (!PageMlocked(kpage)) {                                                  
            unlock_page(page);                                                      
            lock_page(kpage);                                                       
            mlock_vma_page(kpage);                                                  
            page = kpage;       /* for final unlock */                              
        }                                                                           
    }                                                                               

out_unlock:                                                                         
    unlock_page(page);                                                              
out:                                                                                
    return err;                                                                     
}                  

ksm的使用

1.开关

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

2.控制

/sys/kernel/mm/ksm/sleep_millisecs :定期扫描的间隔
pages_to_scan:一次扫描的页数

3.监控

page_shared:稳定树上的page数
page_unshared:非稳定树上的page数
pages_sharing:表示有多少页被共享,举个例子:比如10个页合并到一个页面上,则sharing 为9,而shared为1.那么节省了8个页

本文转自 https://www.kernelnote.com/entry/linux-ksm-merge

2019-06-17 15:26:13 weixin_41738417 阅读数 162

简介:作为一个系统管理程序(hypervisor),Linux® 有几个创新,2.6.32 内核中一个有趣的变化是 KSM(Kernel Samepage Merging)  允许这个系统管理程序通过合并内存页面来增加并发虚拟机的数量。本文探索 KSM 背后的理念(比如存储去耦合)、KSM 的实现、以及如何管理 KSM。

 

服务器虚拟化

     虚拟化技术从上世纪 60 年代开始出现,经由 IBM® System/360® 大型机得以流行。50 年过后,虚拟化技术取得了跨越式发展,使得多个操作系统和应用程序共享一个服务器成为可能。这一特殊用途(称为服务器虚拟化)正在演变为数据中心,因为单个物理机能够用于托管 10 个(一般情况)或更多虚拟机(VM),如图 1 所示。这种虚拟化使基础设施更动态、更省电、(因而也)更经济。

图 1. 通过虚拟化进行的服务器合并

      页面都是相同的。假如操作系统和应用程序代码以及常量数据在 VMs 之间相同,那么这个特点就很有用。当页面惟一时,它们可以被合并,从而释放内存,供其他应用程序使用。图 2 演示了内存共享,并展示了在内容相同的 VMs 之间共享页面时更多可用闲置内存的好处。 

图 2. 跨 VMs 的内存共享

特性命名
     本文描述的特性非常新;因此,其名称经历了一些变化。您将发现这个 Linux 内核特性称为 Kernel Shared Memory 或 Kernel Samepage Merging。

     您很快就会发现,尽管 Linux 中的内存共享在虚拟环境中有优势(KSM 最初设计用于基于内核的虚拟机),但它在非虚拟环境中仍然有用。事实上,KSM 甚至在嵌入式 Linux 系统中也有用处,表明了这种方法的灵活性。下面,我们将探索这种 Linux 内存共享方法,以及如何使用该方法提高服务器的内存密度,从而增加其托管其他应用程序或 VMs 的能力。

 

其他技术支持

     存储技术中的一个称为去耦合(de-duplication)的最新进展是 Linux 和其他系统管理程序中的内存共享的先驱。去耦合这种技术通过删除冗余数据(基于数据块,或者基于更大的数据片段,比如文件)来减少已存储的数据。公共数据片段被合并(以一种 copy-on-write [CoW] 方式),释放空间供其他用途。使用这种方法,存储成本更低,最终需要的存储器也更少。鉴于当前的数据增长速度,这个功能显得非常重要。

 

KSM 操作

     KSM 作为内核中的守护进程(称为 ksmd)存在,它定期执行页面扫描,识别副本页面并合并副本,释放这些页面以供它用。KSM 执行上述操作的过程对用户透明。例如,副本页面被合并(然后被标记为只读),但是,如果这个页面的其中一个用户由于某种原因更改该页面,该用户将(以 CoW 方式)收到自己的副本。可以在内核源代码 ./mm/ksm.c 中找到 KSM 内核模块的完整实现。

     KSM 依赖高级应用程序来提供指导,根据该指导确定合并的候选内存区域。尽管 KSM 可以只扫描系统中的匿名页面,但这将浪费 CPU 和内存资源(考虑到管理页面合并进程所需的空间)。因此,应用程序可以注册可能包含副本页面的虚拟区域。

     KSM 应用程序编程接口(API)通过 madvise 系统调用(见清单 1)和一个新的建议参数(advice parameter)MADV_MERGEABLE(表明已定义的区域可以合并)来实现。可以通过 MADV_UNMERGEABLE 参数(立即从一个区域取消合并任何已合并页面)从可合并状态删除一个区域。注意,通过 madvise 来删除一个页面区域可能会导致一个 EAGAIN 错误,因为该操作可能会在取消合并过程中耗尽内存,从而可能会导致更大的麻烦(内存不足情况)。

清单 1. madvise 系统调用

#include <sys/mman.h>

int madvise( void *start, size_t length, int advice );

     一旦某个区域被定义为 “可合并”,KSM 将把该区域添加到它的工作内存列表。启用 KSM 时,它将搜索相同的页面,以写保护的 CoW 方式保留一个页面,释放另一个页面以供它用。

     KSM 使用的方法与内存去耦合中使用的方法不同。在传统的去耦合中,对象被散列化,然后使用散列值进行初始相似性检查。当散列值一致时,下一步是进行一个实际对象比较(本例中是一个内存比较),以便正式确定这些对象是否一致。KSM 在它的第一个实现中采用这种方法,但后来开发了一种更直观的方法来简化它。

     在当前的 KSM 中,页面通过两个 “红-黑” 树管理,其中一个 “红-黑” 树是临时的。第一个树称为不稳定树,用于存储还不能理解为稳定的新页面。换句话说,作为合并候选对象的页面(在一段时间内没有变化)存储在这个不稳定树中。不稳定树中的页面不是写保护的。第二个树称为稳定树,存储那些已经发现是稳定的且通过 KSM 合并的页面。为确定一个页面是否是稳定页面,KSM 使用了一个简单的 32 位校验和(checksum)。当一个页面被扫描时,它的校验和被计算且与该页面存储在一起。在一次后续扫描中,如果新计算的校验和不等于此前计算的校验和,则该页面正在更改,因此不是一个合格的合并候选对象。

     使用 KSM 进程处理一个单一的页面时,第一步是检查是否能够在稳定树中发现该页面。搜索稳定树的过程很有趣,因为每个页面都被视为一个非常大的数字(页面的内容)。一个 memcmp(内存比较)操作将在该页面和相关节点的页面上执行。如果 memcmp 返回 0,则页面相同,发现一个匹配值。反之,如果 memcmp 返回 -1,则表示候选页面小于当前节点的页面;如果返回 1,则表示候选页面大于当前节点的页面。尽管比较 4KB 的页面似乎是相当重量级的比较,但是在多数情况下,一旦发现一个差异,memcmp 将提前结束。请参见图 3 查看这个过程的视觉呈现。

图 3. 搜索树中的页面的搜索过程

     如果候选页面位于稳定树中,则该页面被合并,候选页面被释放。有关代码位于 ksm.c/stable_tree_search()(称为 ksm.c/cmp_and_merge_page())中。反之,如果没有发现候选页面,则应转到不稳定树(参见 ksm.c/unstable_tree_search())。

     在不稳定树中搜索时,第一步是重新计算页面上的校验和。如果该值与原始校验和不同,则本次扫描的后续搜索将抛弃这个页面(因为它更改了,不值得跟踪)。如果校验和没有更改,则会搜索不稳定树以寻找候选页面。不稳定树的处理与稳定树的处理有一些不同。第一,如果搜索代码没有在不稳定树中发现页面,则在不稳定树中为该页面添加一个新节点。但是如果在不稳定树中发现了页面,则合并该页面,然后将该节点迁移到稳定树中。

     当扫描完成(通过 ksm.c/ksm_do_scan() 执行)时,稳定树被保存下来,但不稳定树则被删除并在下一次扫描时重新构建。这个过程大大简化了工作,因为不稳定树的组织方式可以根据页面的变化而变化(还记得不稳定树中的页面不是写保护的吗?)。由于稳定树中的所有页面都是写保护的,因此当一个页面试图被写入时将生成一个页面故障,从而允许 CoW 进程为写入程序取消页面合并(请参见 ksm.c/break_cow())。稳定树中的孤立页面将在稍后被删除(除非该页面的两个或更多用户存在,表明该页面还在被共享)。

     如前所述,KSM 使用 “红-黑” 树来管理页面,以支持快速查询。实际上,Linux 包含了一些 “红-黑” 树作为一个可重用的数据结构,可以广泛使用它们。“红-黑” 树还可以被 Completely Fair Scheduler (CFS) 使用,以便按时间顺序存储任务。您可以在 ./lib/rbtree.c 中找到 “红-黑” 树的这个实现。

 

KSM 配置和监控

     KSM 的管理和监控通过 sysfs(位于根 /sys/kernel/mm/ksm)执行。在这个 sysfs 子目录中,您将发现一些文件,有些用于控制,其他的用于监控。

     第一个文件 run 用于启用和禁用 KSM 的页面合并。默认情况下,KSM 被禁用(0),但可以通过将一个 1 写入这个文件来启用 KSM 守护进程(例如,echo 1 > sys/kernel/mm/ksm/run)。通过写入一个 0,可以从运行状态禁用这个守护进程(但是保留合并页面的当前集合)。另外,通过写入一个 2,可以从运行状态(1)停止 KSM 并请求取消合并所有合并页面。

     KSM 运行时,可以通过 3 个参数(sysfs 中的文件)来控制它。sleep_millisecs 文件定义执行另一次页面扫描前 ksmd 休眠的毫秒数。max_kernel_pages 文件定义 ksmd 可以使用的最大页面数(默认值是可用内存的 25%,但可以写入一个 0 来指定为无限)。最后,pages_to_scan 文件定义一次给定扫描中可以扫描的页面数。任何用户都可以查看这些文件,但是用户必须拥有根权限才能修改它们。

     还有 5 个通过 sysfs 导出的可监控文件(均为只读),它们表明 ksmd 的运行情况和效果。full_scans 文件表明已经执行的全区域扫描的次数。剩下的 4 个文件表明 KSM 的页面级统计数据:

•pages_shared:KSM 正在使用的不可交换的内核页面的数量。 
•pages_sharing:一个内存存储指示。 
•pages_unshared:为合并而重复检查的惟一页面的数量。 
•pages_volatile:频繁改变的页面的数量。 
     KSM 作者定义:较高的 pages_sharing/pages_shared 比率表明高效的页面共享(反之则表明资源浪费)。

 

 

结束语

     Linux 并不是使用页面共享来改进内存效率的惟一系统管理程序,但是它的独特之处在于将其实现为一个  操作系统特性。VMware 的 ESX 服务器系统管理程序将这个特性命名为 Transparent Page Sharing (TPS),而 XEN 将其称为 Memory CoW。不管采用哪种名称和实现,这个特性都提供了更好的内存利用率,从而允许操作系统(KVM 的系统管理程序)过量使用内存,支持更多的应用程序或 VM。 您可以在最新的 2.6.32 Linux 内核中发现 KSM — 以及其他很多有趣的特性。

KSM,UKSM,PKSM(1/2)

阅读数 2389

内存管理--KSM

阅读数 148

没有更多推荐了,返回首页