Home [草稿] Linux内核的内存回收机制
Post
Cancel

[草稿] Linux内核的内存回收机制

回顾自己的陈年笔记,诧异于以前还整理过这方面的资料。可惜我完全没有印象,不如重新整理一遍,Linux版本更新为6.4.8。

NOTE: 本文暂不包含MGLRU部分(Pixel 8 / Android 14默认启用),后面有机会再另开一篇文章。

内存回收类型

内存回收分为:

  • 快速回收。
  • 直接回收。
  • kswapd回收。

主要区分点是触发时机和处理页面类型。

快速回收的触发时机为低水位快速路径内存分配失败时。可以处理非脏页。

直接回收的触发时机为慢速路径内存分配过程中,内存整理失败时。可以处理非脏页。

kswapd回收的触发时机为快速路径分配失败后,进入慢速分配路径,先于直接回收执行kswapd回收。可以处理所有页面,包括脏页。

它们的共同点是均使用LRU链表等数据结构作为回收用的容器,并且回收流程相似。对于匿名页,可以放入到swap分区;对于文件页,脏页可以进行写回操作,非脏页直接释放即可。

数据结构

数据结构主要是LRU链表(lruvec),以及LRU缓存(pagevec)。

LRU缓存

LRU缓存的数据结构如下:

/* Layout must match folio_batch */
struct pagevec {
        unsigned char nr;
        bool percpu_pvec_drained;
        struct page *pages[PAGEVEC_SIZE];
};

/**
 * struct folio_batch - A collection of folios.
 *
 * The folio_batch is used to amortise the cost of retrieving and
 * operating on a set of folios.  The order of folios in the batch may be
 * significant (eg delete_from_page_cache_batch()).  Some users of the
 * folio_batch store "exceptional" entries in it which can be removed
 * by calling folio_batch_remove_exceptionals().
 */
struct folio_batch {
        unsigned char nr;
        bool percpu_pvec_drained;
        struct folio *folios[PAGEVEC_SIZE];
};

/*
 * The following folio batches are grouped together because they are protected
 * by disabling preemption (and interrupts remain enabled).
 */
struct cpu_fbatches {
        local_lock_t lock;
        struct folio_batch lru_add;
        struct folio_batch lru_deactivate_file;
        struct folio_batch lru_deactivate;
        struct folio_batch lru_lazyfree;
#ifdef CONFIG_SMP
        struct folio_batch activate;
#endif
};

LRU缓存pagevec通过pagefolio的封装关联folio_batchcpu_fbatches,前者提供批量页面(改为folio形式)操作,后者提供每CPU同名变量cpu_fbatches缓存。因此LRU缓存是folio兼容的。

提供LRU缓存的目的是为了减缓频繁的锁操作,如果LRU每次对单个页的添加移除都需要操作LRU上的锁,那么会有不必要的冲突。因此,使用LRU缓存来提供批量操作:先将需要变动的页面放入到LRU缓存中,再批量处理。LRU缓存能批量处理的页面数为PAGEVEC_SIZE,即固定值15,这个数字加上首部数据符合2的幂。

15 pointers + header align the pagevec structure to a power of two.

LRU链表

LRU链表存放于per-node级别的pglist_data中,数据结构如下:

struct lruvec {
        struct list_head                lists[NR_LRU_LISTS];
        /* per lruvec lru_lock for memcg */
        spinlock_t                      lru_lock;
        /*
         * These track the cost of reclaiming one LRU - file or anon -
         * over the other. As the observed cost of reclaiming one LRU
         * increases, the reclaim scan balance tips toward the other.
         */
        unsigned long                   anon_cost;
        unsigned long                   file_cost;
        /* Non-resident age, driven by LRU movement */
        atomic_long_t                   nonresident_age;
        /* Refaults at the time of last reclaim cycle */
        unsigned long                   refaults[ANON_AND_FILE];
        /* Various lruvec state flags (enum lruvec_flags) */
        unsigned long                   flags;
#ifdef CONFIG_LRU_GEN
        /* evictable pages divided into generations */
        struct lru_gen_folio            lrugen;
        /* to concurrently iterate lru_gen_mm_list */
        struct lru_gen_mm_state         mm_state;
#endif
#ifdef CONFIG_MEMCG
        struct pglist_data *pgdat;
#endif
};

NOTE: 如果使用了memcg,即使是UMA架构的情况,那也不只是一个lruvec。这部分细节可以看上方链接的注释。

出于页面特征(文件页和匿名页)的区分和运行效率考虑,LRU链表分为5种类型

  • ACTIVE FILE
  • INACTIVE FILE
  • ACTIVE ANON
  • INACTIVE ANON
  • UNEVICITABLE

其中UNEVICITABLE较为特殊,适用于被锁定的内存页面:

  • Those owned by ramfs.
  • Those owned by tmpfs with the noswap mount option.
  • Those mapped into SHM_LOCK’d shared memory regions.
  • Those mapped into VM_LOCKED mlock()ed VMAs.

NOTE: 在Multi-Gen LRU机制(CONFIG_LRU_GEN)中,ACTIVE和INACTIVE被归为某种generation,而generation是可配置的,并不只是ACTIVE和INACTIVE。

基本操作

LRU的基本操作(插入、移动)集中在mm/swap.c,6.x后page均经过folio封装。

比如一个add操作(folio_add_lru())的简化代码就是:

folio_add_lru(folio):
    folio_ref_inc(folio)
    local_lock(cpu_fbatches.lock)
    fbatch = this_cpu(cpu_fbatches.lru_add)
    folio_batch_add_and_move(fbatch, folio, lru_add_fn) ⭐
    local_unlock(cpu_fbatches.lock)

基本操作主要依靠folio_batch_add_and_move(..., move_fn_t)接口和接受的move_fn_t类型的回调函数lru_add_fn()完成。简单来说,接口部分就是将folio页面添加到fbatch缓存中,如果缓存已满,则遍历缓存中的所有页面并执行回调;实现部分挑选页面对应的LRU链表(lruvec_add_folio())并插入。

状态转移

     Double CLOCK lists

Per node, two clock lists are maintained for file pages: the
inactive and the active list.  Freshly faulted pages start out at
the head of the inactive list and page reclaim scans pages from the
tail.  Pages that are accessed multiple times on the inactive list
are promoted to the active list, to protect them from reclaim,
whereas active pages are demoted to the inactive list when the
active list grows too big.

  fault ------------------------+
                                |
             +--------------+   |            +-------------+
  reclaim <- |   inactive   | <-+-- demotion |    active   | <--+
             +--------------+                +-------------+    |
                    |                                           |
                    +-------------- promotion ------------------+
                                /* 状态转移 */

如上图,页面在LRU中进行状态转移的基本情况为:

  1. 当首次page fault时(产生映射),会加入到INACTIVE当中。
  2. 当INACTIVE中的page被访问多次,会promote到ACTIVE。
  3. 当ACTIVE过大时,会demote到INACTIVE(以平衡两端大小)。
  4. 页面在链表的位置按照LRU算法来定位。

referenced 状态转移 pro

实现上,页面的转移依靠page flags标记,如上图所示。这方面也可以看folio_mark_accessed()的注释。一个结论是INACTIVE链表上的页面被标记访问两遍即提升(promote)到ACTIVE链表。

NOTE: 时过境迁,上图的第一个函数mark_page_accessed已改名folio_mark_accessed,第二个函数page_referenced更改为folio_referenced

fsm 状态转移 pro max

另外提供一份更加复杂的状态转移图。这里PTE.A指的是struct page通过反向映射得到的对应页表项A位(accessed bit)的统计个数(因为一个struct page可以映射到多个PTE)。X86中的A位访问页表就会自动置一,只能通过手动的方式置零(显然kernel access可以手动控制,但是userspace没有办法)。问号?表示此时并不关心该字段。diff.表示不同的进程,因为不同的进程有不同的页表,因此可以做到PTE.A>1。回收保留(keep)操作虽然使得页面保留在原链表上,但是会置于尾部。其它的细节较多,请看作者的演讲

另外再提一下页面的初始状态。对于匿名页,会在do_anonymous_page()(也就是page fault时)产生页面并加入到LRU中,在早期版本如5.4.1,是直接加入到ACTIVE链表中,参考这行代码;而在后期版本如5.11.22(随手找的,具体时间点请翻blame)又变动为INACTIVE链表,参考这行代码;直到6.4.8仍然是INACTIVE,但是修改成folio封装函数,参考这行代码。对于文件页就没啥好说的,必然INACTIVE。

/* 备忘录:关于初始状态 (v6.4.8) */

// 匿名页的LRU加入时机
do_anonymous_page
    folio_add_lru_vma
        folio_add_lru

// 文件页的LRU加入时机
filemap_fault
    __filemap_get_folio
        filemap_add_folio
            folio_add_lru

至于我是怎么发现匿名页行为区别的,是因为之前写了一个meminfo parser,偶然观察到不同版本的LRU统计有区别,这篇文章记录了5.15的mmap测试结果,这里又记录了5.4和5.15的差异。

工作集检测

这一块比较抽象,细节可以参考mm/workingset.c对refault distance算法的注释。

LRU的淘汰机制会导致回收抖动的存在(页面不断往复于被回收和再次载入的状态,也就是refault),因此需要工作集检测。个人理解是refault其实是应该作为活跃页面去看待,但是LRU会反复由回收载入,原因出现在把页面放入到INACTIVE上。因此,如果能检测出工作集,那就直接放入到ACTIVE链表(如上图working set refault activation),不仅少走几步弯路,也避免了错误的回收。

精准的计算是难以实现的,内核的做法是使用估算访问距离(access distance,同一页面两次访问的时间间隔中,LRU所访问的页面数)的算法。下面是对算法的一些比较枯燥的解释。

观察两个事实:

  1. 访问首次缺页异常(fault)的页面,该页面会插入到INACTIVE链表头部,相当于该链表淘汰另一个页面,并且链表上所有的页面都往尾部方向挪动一个单位;
  2. 访问INACTIVE链表上的页面若引发某页面的提升行为,那么从链表头部到该页面前的其它页面也相当于往尾部方向挪动一个单位。

得出两个结论:

  1. INACTIVE链表上,任意时间段的最小访问距离 ≈ 该时间段的淘汰次数和提升次数之和(sum)。
  2. INACTIVE链表上,如果一个页面能往尾部方向移动N个单位,至少要访问N次(其它)页面。

再次推理:

  1. in-cache distance:一个页面从载入到淘汰,那就至少访问\(NR\_inactive\)(INACTIVE链表长度)次页面。所以页面在缓存内的访问距离为\(NR\_inactive\)。
  2. out-of-cache distance:页面淘汰时的sum记为\(E\),再次载入时的sum记为\(R\),缓存外的访问距离即为\(R-E\)。(同时这个也是refault distance)
  3. complete access distance:从(new)fault到refault的完整访问距离,就是将缓存内外时间段的访问距离结合起来,即\(NR\_inactive + (R-E)\)。

推理到第三点就可以玩更抽象的了。只要访问距离小于等于内存总和,那就能让页面免受淘汰:

\[\begin{equation} \begin{aligned} NR\_inactive + (R-E) &\le total\_memory \\ NR\_inactive + (R-E) &\le NR\_inactive + NR\_active \\ (R-E) &\le NR\_active \end{aligned} \end{equation}\]

NOTE: 为什么如此绕弯路,理论上保证INACTIVE链表长度大于等于\(R\)(以fault为时间起点)不就能保证refault页面存活了吗?我觉得这确实是对的,但是工作集检测算法的妙处在于不需要这种条件,因为工作集检测出refault页面,是直接加入到ACTIVE链表,无需确保INACTIVE下限,可谓是二流企业看现金流,顶流企业看预期前景。这样避免了INACTIVE链表过长从而ACTIVE链表过短(毕竟长度不是凭空冒出来的……)导致LRU和second chance算法的缓存特性被动减弱。

但是考虑到LRU链表拆分为文件页类型和匿名页类型,式子左边的\(NR\_inactive\)应为具体的某个类型,而右边\(total\_memory\)是算上四种组合的LRU链表,也就是说最后应该是这样的形式:

对于文件页:

\[(R-E) \le NR\_active\_file + NR\_inactive\_anon + NR\_active\_anon\]

对于匿名页:

\[(R-E) \le NR\_active\_anon + NR\_inactive\_file + NR\_active\_file\]

算法实现见workingset_refault()流程,左边的式子靠lruvec提供一个nonresident_age计数器来完成(搭配一种称为shadow entry的技巧),右边的式子就是所谓的工作集大小。总之,结论是满足以上公式就能做到上一章节图示的working set refault activation,也就是folio_set_active(folio)

全局回收

无论是快速回收、直接回收还是kswapd回收,它们的回收算法都会集中在同一个流程。

// 快速回收
get_page_from_freelist
    node_reclaim
        __node_reclaim
            shrink_node

// 直接回收
__alloc_pages_slowpath
    __alloc_pages_direct_reclaim
        __perform_reclaim
            try_to_free_pages
                do_try_to_free_pages
                    shrink_zones
                        shrink_node

// kswapd回收
kswapd
    balance_pgdat
        kswapd_shrink_node
            shrink_node

因此shrink_node()就是回收算法的核心。这里区分全局回收和memcg回收,但是由于本文作者太菜,所以只考虑全局回收。这部分包含的几块内容分小节分析。

页面扫描

回收算法需要决定扫描页面的数目,以及文件页和匿名页的扫描比例。在算法实现上,页面扫描的决策大概分了两步:一是根据当前负载分析出一些特殊场合,二是根据回收的成本来决定页面类型之间的扫描比例。页面扫描的行为有相当大量的细节集中在扫描控制结构,也可以看下里面的注释。

继续探究页面扫描之前先了解一下LRU链表的平衡处理。

链表平衡

链表平衡指的是依靠降级(demote)将过短的INACTIVE链表延长。通常来说LRU维护的准则是ACTIVE链表拥有更高占比,而INACTIVE占比在撑得住refault压力的前提下尽可能小。

为了避免极端情况,需要一些简单快速的平衡保底方法。内核中inactive_is_low()判定是直接按总内存划分比例的方式来计算的。只要\(\frac{active}{inactive} > target\_ratio\)就是low,判定为low就可能引起降级

注释里也直接给出了一些提前算好的参考值:

total memory target ratio max inactive
10MB 1 5MB
100MB 1 50MB
1GB 3 250MB
10GB 10 0.9GB
100GB 31 3GB
1TB 101 10GB
10TB 320 32GB

\(target\_ratio:1\)的代码实现也很直接,1GB以下的总内存按照1:1的比例,更高内存总量则按照\(\sqrt{\frac{10 \times (active + inactive)}{2^{18}}}:1\)比例。(\(active\)和\(inactive\)的单位是4K,除掉\(2^{18}\)就是转换到GB为单位,至于开根乘10有点像大学考试的挂科捞人算法,确实捞人也是一种balancing……)

负载分析

回到页面扫描的准备阶段,在prepare_scan_count()函数中存在几种特殊场景的判断:

  • may_deactive: 观察到refault现象且链表长度失衡。
  • cache_trim_mode: 有足够多的非活跃page cache(easily reclaimable cold cache)。
  • file_is_tiny: 内存高压,文件页过少(The file folios are dangerously low)。

When refaults are being observed, it means a new workingset is being established. Deactivate to get rid of any stale active pages quickly. mm/vmscan.c

除此以外还包括一些零散的场景,概括的判断逻辑如下表:

特殊场景 判断条件 影响
没有交换空间 !may_swap 如果满足条件,扫描平衡强制设为SCAN_FILE,表示不扫描匿名页。
接近OOM 1. !priority
2. swappiness
如果满足条件,扫描平衡强制设为SCAN_EQUAL,表示平等地扫描文件页和匿名页。
may_deactive 1. refault
2. inactive_is_low
如果满足条件,允许执行shrink_active_list()
否则,标记为skipped_deactivate,跳过降级操作,同时直接回收中的下一次启动不允许再次跳过。
cache_trim_mode 1. inactive_file > \(2^{priority}\)
2. !may_deactive(INACTIVE_FILE)
如果满足条件,扫描平衡强制设为SCAN_FILE,表示不扫描匿名页。
file_is_tiny 1. !memcg
2. inactive_file+active_file+free < high_watermark
3. !may_deactive(INACTIVE_ANON)
4. inactive_anon > \(2^{priority}\)
如果满足条件,扫描平衡强制设为SCAN_ANON,表示只扫描匿名页。

NOTE: 其实priority为0就可以表达「接近OOM」的意思,swappiness不为0的判断是暗讽用户在OOM救火前就不要自作主张做压力平衡(见页面成本小节),除非你严重反对地禁止了swap。

TODO: priority和swappiness说明,默认优先级优化场景。

页面成本

匿名页和文件页的实际回收成本并不相同(可能某种页面需要更多的IO,取决于设备和负载等因素),因此需要定义成本(或者是压力,内核注释也会描述为pressure balancing)。

成本的估算定义在lru_note_cost(),会在链表缩容(ACTIVEINACTIVE)或者refault检测中触发计算。计算方式是同时考虑IO和CPU的处理开销,分别统计写页次数\(pageout\)和LRU旋转次数\(scanned - reclaimed\),最终把\(cost\)结果存放于lruvecfile_costanon_cost字段中。

\[cost = pageout \times SWAP\_CLUSTER\_MAX + (scanned - reclaimed)\]

NOTE: \(pageout\)的作用见pageout(),表示对脏页执行writepage(),清除PG_dirty和标记PG_reclaim位等操作;公式具体怎样考虑的也可以看下commit的解释,反正我也不太懂……

在一般场景(没有在特殊场景里面设置扫描平衡)中,扫描平衡模式是SCAN_FRACT,也就是基于「fractional cost model」去划分页面扫描比例,大白话就是按各自成本的倒数做除法运算

NOTE: 我调试的时候发现有点不合预期(并不是简单按成本比例的倒数,注释里提了一句we limit that influence to ensure no list gets left behind completely),主要是L3074和L3075行的叠加导致的,只能说成本对比例的影响有限。我顺手把测试样例抽离出来了,里面也有fractional cost model的简化公式,你可以自己试试。

总之,简记anon_cost为\(a\),file_cost为\(b\),swappiness为\(x\),代入算法并简化。

对于匿名页要扫描的数目为:

\[scan \times \frac{(a+2b)x}{400a+200b+(b-a)x}\]

对于文件页要扫描的数目为scan减去匿名页扫描数:

\[scan \times \frac{400a+200b-(2a+b)x}{400a+200b+(b-a)x}\]

其实了解这个公式没什么意义,一方面它不是给人看的(我是用表达式简化工具算出来的),另一方面算法总是会不断优化而变动的。

这里的扫描数目存放于nr[]数组中,会在后续链表缩容环节用到。

链表缩容

shrink-list

在全局回收算法中,完成了前面提到的准备工作后即可进入链表缩容流程shrink_list()(从shrink_lruvec()进入)。如果是简单理解的话,就是区分shrink_active_list()shrink_inactive_list(),对于遍历扫描到的页面,前者尝试降级操作,后者尝试回收操作。

但实际上shrink_list()的代码实现只能用丧心病狂来形容(被自己菜哭( ´_ゝ`)旦),先放个ULK书里的示意图吧,这是很多年前的实现不一定对得上6.x版本,需要花点时间看代码。

!!!!! WORK IN PROGRESS !!!!!

TODO

🕊️ watermark行为,boost特性等。
🕊️ 三种回收触发流程,扫描控制初始化等。
🕊️ slab缩容。

References

Overview of Memory Reclaim in the Current Upstream Kernel
深入理解Linux内存管理(七)内存回收
linux内存源码分析 - 内存回收(lru链表)
linux内存源码分析 - 内存回收(整体流程)
跟踪LRU活动情况和Refault Distance算法
Linux中的内存回收[二]
linux内存回收 之 File page的 lru list算法原理
Page PG_referenced vs PG_active bit?
Better active/inactive list balancing
Unevictable LRU Infrastructure
内存回收2:关键结构体struct scan_control

This post is licensed under CC BY 4.0 by the author.
Contents