Linux 内存回收机制

【基本结构】
5条lru链表:
anonymous active
anonymous inactive
file active
file inactive
unevictable
根据page的属性(是否mlock)判断是否放到unevictable list,根据pg_active和pg_active标志在active和inactive之间流动。

【在active和inactive之间流动的核心为:】

– 如果页面被认为是活跃的,则将该页的 PG_active 置位;否则,不置位。
– 当页面被访问时,检查该页的 PG_referenced 位,若未被置位,则置位之;若发现该页的 PG_referenced 已经被置位了,则意味着该页经常被访问,这时,若该页在 inactive 链表上,则置位其 PG_active 位,将其移动到 active 链表上去,并清除其 PG_referenced 位的设置;如果页面的 PG_referenced 位被置位了一段时间后,该页面没有被再次访问,那么 Linux 操作系统会清除该页面的 PG_referenced 位,因为这意味着这个页面最近这段时间都没有被访问。
– PG_referenced 位同样也可以用于页面从 active 链表移动到 inactive 链表。对于某个在 active 链表上的页面来说,其 PG_active 位被置位,如果 PG_referenced 位未被置位,给定一段时间之后,该页面如果还是没有被访问,那么该页面会被清除其 PG_active 位,挪到 inactive 链表上去。

【思考】

个人觉得,second chance回收算法在某种意义上也可以完成上面的意图,即发现某个page被pg_referenced置位了,那么把他移到链表的尾部(最新被访问),这样就不需要多个list了。但是这样就不能统计nr_active和nr_inactive了,而Linux的回收算法还会把这两个链表的长度考虑进去,做到一定程度的平衡,或者说主动的进行双向的流动,而上面说的second chance一条链的算法做不到主动去平衡。有了主动平衡,在回收的时候可以只遍历inactive链表,减少了一次性扫描太多page的可能性,一定程度上可以缓解系统性能抖动。
分了anonymous和file两种链的目的,我目前只考虑到可以在回写时区别调用不同的函数,一个写到swap,一个调用相应文件系统的回写函数
freelist保存了free的物理页,kswapd和alloc_slowpath会给他添砖加瓦,而程序的释放等是其收入的主要来源。kswapd周期性的唤醒或者被alloc_slowpath唤醒(如果分配内存的函数没能从freelist上找到所需的order的内存,那么就要悲剧的进入slowpath了,现象就是程序卡顿了,qps下降了。。。),判断当前内存(某个zone,如果有numa)是否balance,这里的balance可以简单理解为(2.6.32内核)是否低于low water mark(通过vm.min_free_kbytes的设定值计算出来的一个下限水位值),如果低于这个值,那么kswapd会shrink上面那些list,然后释放出来的page,挂到freelist里面,直到内存达到high water mark

【shrink list的顺序?】

enum lru_list {
    LRU_INACTIVE_ANON = LRU_BASE,
    LRU_ACTIVE_ANON = LRU_BASE + LRU_ACTIVE,
    LRU_INACTIVE_FILE = LRU_BASE + LRU_FILE,
    LRU_ACTIVE_FILE = LRU_BASE + LRU_FILE + LRU_ACTIVE,
    LRU_UNEVICTABLE,
    NR_LRU_LISTS
};
#define for_each_lru(lru) for (lru = 0; lru < NR_LRU_LISTS; lru++)
#define for_each_evictable_lru(lru) for (lru = 0; lru <= LRU_ACTIVE_FILE; lru++)
但是真正回收的时候,还是要给active几分面子的:
static unsigned long shrink_list(enum lru_list lru, unsigned long nr_to_scan,
                 struct lruvec *lruvec, struct scan_control *sc)
{
    if (is_active_lru(lru)) {
        if (inactive_list_is_low(lruvec, lru))
            shrink_active_list(nr_to_scan, lruvec, sc, lru);
        return 0;
    }
    return shrink_inactive_list(nr_to_scan, lruvec, sc, lru);
}

【什么样的page可以被回收 】

要看具体的配置,具体干活的函数在这里:__isolate_lru_page
基本上都可以除了unevictable不可以
如果是脏页:
Only pages without mappings or that have a
             * ->migratepage callback are possible to migrate
             * without blocking
migratepage是什么鬼:在move_to_new_page函数中找到下面一段注释
        /*
         * Most pages have a mapping and most filesystems provide a
         * migratepage callback. Anonymous pages are part of swap
         * space which also has its own migratepage callback. This
         * is the most common path for page migration.
         */

【参考文献】

PAUSE指令

内核中的嵌入式汇编代码”rep;nop”会被编译为PAUSE指令,Intel Pentium4以后的CPU支持,之前的就相当于NOP。为啥rep;nop不是指循环执行nop同时递减ecx的值呢,这还真是之前困扰过我的问题,有篇文章用代码解释了这个问题-链接-。而博主自己也在虚拟机里面将cpu_relax()中的rep;nop替换为nop,前后均在host上抓取vmexit和trace kvm_exit数据,结果显示,PAUSE_INSTRUCTION造成的退出消失了。

上文中还翻译了Intel的spec,大概说了下pause指令有两种功能,一方面是可以解决memory order violation问题,另一方面可以降低循环等待的能耗。

什么是memory order violation?看这里。简单说下就是cpu的pipeline会根据执行代码的情况来预测即将执行的指令,提前将这些指令放入流水线中,达到一定的并行计算优化性能的目的,但是总会事与愿违,在spinlock代码实现中,如果不加入pause指令,很容易造成pipeline被“读入lockvar,比较lockvar是否为0”这样指令刷屏了,这就造成了即使在lockvar已经被别的CPU更新为非0值的时候,pipeline中出现了无效指令,这种情况就是memory order violation,即本应在写内存后读取内存值的动作发生在了写入之前,于是cpu就暴力的把pipeline全部flush掉,这样就造成了性能损失,因为这里是在等待一个lockvar被改变,只要及时的对这个动作做出反应就可以了。

pause指令的出现可以给cpu一个提示,这里不要给我缓存指令,等前面的执行完再看后面的,于是大大的减少了出现无效指令的可能性(此时出现这个情况的时间窗口为:读取了lockvar,但是cmp还没有执行;与之前比起来,时间窗口大大大的缩小了,之前是预读取了很多次的“读取lockvar,与0比较,跳入再一次的读取比较的分支”这三个动作,最后一个跳转也是预测的)。

节能的效果更好理解,其实这里就是在原地踏步,不是要求一定时间内踏的次数多,而是要对出现的情况及时处理。所以加入pause可以让处理更及时,而且不必把能量浪费在多出来的无意义的指令上。

梳理一下EPT表项的建立

EPT是对虚拟机访问内存的硬件加速,其功能和影子页表一样,就是建立gpa到hpa的直接映射,访问EPT中已经建立好映射的gpa地址不触发vmexit,同时也只需要做一次pagewalk,但是第一次访问还是会vmexit,借着这个机会在退出处理函数中把对应的EPT表项建立好,这个退出名字叫EPT_VIOLATION,处理函数是handle_ept_violation。
handle_ept_violation函数里面最终调用了tdp_page_fault来为EPT建立新的entry,这个函数其实复用了影子页表的page_fault函数nonpaging_page_fault很多代码(我的理解是,EPT和影子页表都完成同样的功能只不过一个是硬件来查表一个是软件查表,但是表还是那张表),其中vcpu->arch.mmu.root_hpa保存了EPT表的基地址或者保存影子页表基地址。它调用__direct_map来完成entry的建立,后者使用了宏for_each_shadow_entry来遍历EPT表项,再调用mmu_set_spte来真正的完成表项的设置。上述宏for_each_shadow_entry长这样,它用到了root_hpa,以此为根基一层层的遍历addr(gpa)对应的entry:
#define for_each_shadow_entry(_vcpu, _addr, _walker)    \
    for (shadow_walk_init(&(_walker), _vcpu, _addr);    \
         shadow_walk_okay(&(_walker));            \
         shadow_walk_next(&(_walker)))
 
mmu_set_spte建立entry的时候,要分情况,对RAM和MMIO要区别对待,比如对qemu模拟的设备mmio引发的violation,就需要特殊处理:
先判断不是RAM:is_rmap_spte,即目前没有被标记为present的spte;
然后set_spte》set_mmio_spte
》is_noslot_pfn这里判断该pfn是否在memslot里面,这是另外一个故事。qemu为虚拟机准备的RAM都在memslot里面,mmio一般不属于,除非是直通设备的情况。(注:针对直通设备,qemu调用assigned_dev_register_regions 这个函数处理直通设备的mmio空间和pio空间,它把直通设备的mmio空间通过sysfs文件做mmap到qemu地址空间,然把这一段hva地址做成一个ram类型的新的memory region给注册给虚拟机,让虚拟机把这一段地址当作内存来处理,于是这一段地址也在memslot范围内。)
》mark_mmio_spte,这里为该spte打上mask:mask |= shadow_mmio_mask | access | gfn << PAGE_SHIFT;
当下次访问这个gfn时,发生ept violation,handle_ept_violation函数调用:
handle_mmio_page_fault》handle_mmio_page_fault_common
    if (quickly_check_mmio_pf(vcpu, addr, direct))
        return RET_MMIO_PF_EMULATE;
 
    spte = walk_shadow_page_get_mmio_spte(vcpu, addr);
    if (is_mmio_spte(spte)) {
        gfn_t gfn = get_mmio_spte_gfn(spte);
        unsigned access = get_mmio_spte_access(spte);
 
        if (!check_mmio_spte(vcpu->kvm, spte))
            return RET_MMIO_PF_INVALID;
 
        if (direct)
            addr = 0;
 
        trace_handle_mmio_page_fault(addr, gfn, access);
        vcpu_cache_mmio_info(vcpu, addr, gfn, access);
        return RET_MMIO_PF_EMULATE;
从is_mmio_spte 开始看起,首先判断是否是mmio,如果是则获取gfn,访问权限等信息,保存到vcpu结构的相关域中,最后返回,这个返回最终会引发重退出,回到qemu中模拟。开始的两行是一个优化,上一次查询结构保存在上面说的vcpu结构中,所以可以尝试一下,万一匹配了呢!而且前后访问同一个mmio的gfn的情况应该是很普遍的,因为配置设备寄存器往往是一系列的动作。

为了满足强迫症病人的需求,我们再看一下这个tdp_page_fault是从哪里来的:
handle_ept_violation》kvm_mmu_page_fault》vcpu->arch.mmu.page_fault,最后这个函数是不同架构在初始化的时候注册的,拿x86来说具体如下:
int kvm_mmu_create(struct kvm_vcpu *vcpu)
{
    ASSERT(vcpu);
 
    vcpu->arch.walk_mmu = &vcpu->arch.mmu;
    vcpu->arch.mmu.root_hpa = INVALID_PAGE;
    vcpu->arch.mmu.translate_gpa = translate_gpa;
    vcpu->arch.nested_mmu.translate_gpa = translate_nested_gpa;
 
    return alloc_mmu_pages(vcpu);
}
上述函数在kvm_arch_vcpu_init里面调用,这个是从qemu初始化vcpu发起的动作,具体的:
kvm_vm_ioctl_create_vcpu》kvm_arch_vcpu_create》kvm_x86_ops->vcpu_create==vmx_create_vcpu》kvm_vcpu_init》kvm_arch_vcpu_init
接下来,这个系统调用进一步对vcpu进行设置:(tdp two-dimentional paging)
kvm_vm_ioctl_create_vcpu 》kvm_arch_vcpu_setup》kvm_mmu_setup》init_kvm_mmu》init_kvm_tdp_mmu
static int init_kvm_tdp_mmu(struct kvm_vcpu *vcpu)
{
    struct kvm_mmu *context = vcpu->arch.walk_mmu;
 
    context->base_role.word = 0;
    context->new_cr3 = nonpaging_new_cr3;
    context->page_fault = tdp_page_fault;
上面其实是针对tdp_enabled==true场景来分析的,如果为false,即没有EPT等硬件的支持,那么要走另一条路:
static void init_kvm_mmu(struct kvm_vcpu *vcpu)
{
    if (mmu_is_nested(vcpu))
        return init_kvm_nested_mmu(vcpu);
    else if (tdp_enabled)
        return init_kvm_tdp_mmu(vcpu);
    else
        return init_kvm_softmmu(vcpu);
}
init_kvm_softmmu》kvm_init_shadow_mmu》nonpaging_init_context》context->page_fault = nonpaging_page_fault;
nonpaging_page_fault里面同样调用了handle_mmio_page_fault,也通过调用nonpaging_map,间接地调用了__direct_map,而tdp_page_fault就是糅合了这些调用,重写了tdp版本的page_fault处理函数。

KVM直通设备的配置空间访问

KVM提供了设备直通的方式:kvm assgined device。很多人认为直通设备是直接分配给虚拟机的,那么它的配置空间也应该由虚拟机直接访问,但这是个误区,即使很多从事虚拟化多年的老司机也有这个误解。

实际上,从qemu代码里面可以看到,直通设备是由qemu模拟的一个特殊的pci设备,对这个设备的配置空间读写都由qemu代理。这样做的原因在笔者看来,一方面是考虑到安全因素,不放心让虚拟机直接操作硬件,因为虚拟机里面的设备驱动是不可控的;另一方面,qemu需要在必要的时候截获对配置空间的访问来完成一些对hypervisor的配置,比如对msix entry page的配置,qemu必须拿到guest分配的中断vector,这样才能配置好hypervisor(具体是KVM模块实例中的数据结构)完成对直通设备中断的路由,这个内容我们以后详述,本文重点是直通设备的配置空间访问。

qemu中的pci-assign.c是直通设备模拟的代码所在。其中assigned_initfn函数是直通设备模型实例的初始化函数,这里需要啰嗦一下,qemu1.0对设备模拟代码框架进行了重构,融入了面向对象的编程理念,所有的设备都进行了分门别类,一层层的定义了很多设备的抽象类型以及由这些类型继承而来的子类型,比如virtio-net设备的继承链是object->device->pci->virtio-pci->virtio-net。这些类型就是一个个对象,他们的实例化由自己的初始化函数来做。回到assigned_initfn,get_real_device函数通过sysfs打开了直通设备的配置空间(比如/sys/bus/pci/devices/0000:00:01.0/config)并读取其内容,同时打开了BAR指向的资源(类似/sys/bus/pci/0000:00:01.0/resource0)文件,并在assigned_dev_register_regions函数里将resource文件做了mmap,然后组装好MemoryRegion(qemu对虚拟机物理地址空间管理使用的数据结构,主要用来处理虚拟机对设备的控制层面的PIO和mmio访问),这里面会注册对这一段地址访问的操作函数,调用的时机就是在虚拟机访问这些内存地址发生退出的时候。虚拟机访问MemoryRegion包含的地址时,发生EPT_VIOLATION,进而退出到qemu中,qemu根据其所属的memoryregion来决定如何处理这个退出,比如调用这个region注册的读写函数。而这里所注册的读写函数就是读写真实设备BAR指向的配置寄存器了。