0%

Linux内存管理(七)页面回收

原图

Linux操作系统会使用存储设备作为交换分区,内核将很少使用的内存换出到交换分区,以便释放出物理内存,这个机制称为页交换(swapping),这些处理机制统称为页面回收(pagereclaim)。

LRU链表

Linux内核中采用的页交换算法主要是经典LRU链表算法和第二次机会(secondchance)法。 LRU是Least Recently Used的缩写,意为最近最少使用。根据局部性原理,LRU假定最近不使用的页面在较短的时间内也不会频繁使用,在内存不足时,这些页面将成为被换出的候选者。内核使用双向链表来定义LRU链表,并且根据页面的类型将LRU链表分为LRU_ANON和LRU_FILE。每种类型根据页面的活跃性分为活跃LRU链表和不活跃LRU链表,所以内核中一共有如下5个LRU链表。

  • 不活跃匿名页面链表LRU_INACTIVE_ANON
  • 活跃匿名页面链表LRU_ACTIVE_ANON
  • 不活跃文件映射页面链表LRU_INACTIVE_FILE
  • 活跃文件映射页面链表LRU_ACTIVE_FILE
  • 不可回收页面链表LRU_UNEVICTABLE

LRU链表之所以要分成这样,是因为当内存紧缺时总是优先换出文件映射的文件缓存页面(LRU FILE链表中的页面)而匿名页面总是要在写入交换分区之后,才能被换出。

LRU链表按照内存节点(之前版本是zpone)配置,也就是说,每个内存节点中都有一整套LRU链表,因此内存节点的描述符数据结构(pglist_data)中有一个成员lruvec指向这些链表。枚举类型变量lru_list列举出上述各种LRU链表的类型,lruvec数据结构中定义了上述各种LRU类型的链表。

第二次机会法

第二次机会法的改进是为了避免把经常使用的页面置换出去。当选择置换页面时,依然和经典LRU链表算法一样,选择最早置入链表的页面,第二次机会法设置了一个访问状态位(硬件控制的位),所以要检查页面的访问位。如果访问位是0,就淘汰这个页面;如果访问位是1,就给它第二次机会,并选择下一个页面来换出。当该页面得到第二次机会时,它的访问位被清零,如果该页面在此期间再次被访问过,则访问位设置为1。于是,给了第二次机会的页面将不会被淘汰,直至其他页面被淘汰(或者也给了第二次机会)。因此,如果一个页面经常被使用,其访问位总保持为1,它一直不会被淘汰。

Linux内核使用PG_active和PG_referenced 这两个标志位来实现第二次机会法。PG_active表示该页面是否活跃,PG_referenced表示该页面是否被引用过。

实现

LRU链表维护

我们需要有timestamp来标识一个page最近被访问的时间,然而像x86这样的架构并没有从硬件上提供这种机制。

Linux采用的方法是维护2个双向链表,一个是包含了最近使用页面的active list,另一个是包含了最近不使用页面的inactive list,并且在struct page的page flags中使用了PG_referenced和PG_active两个标志位来标识页面的活跃程度。

  • PG_active标志位决定page在哪个链表,也就是说active list中的pages的PG_active都为1,而inactive list中的pages的PG_active都为0。
  • PG_referenced标志位则是表明page最近是否被使用过。当一个page被访问,mark_page_accessed()会检测该page的PG_referenced位,如果PG_referenced为0,则将其置为1。

如果inactive list上PG_referenced为1的page在回收之前被再次访问到,也就是说它在inactive list中时被访问了2次,mark_page_accessed()就会调用activate_page()将其置换到active list的头部,同时将其PG_active位置1,PG_referenced位清0(可以理解为两个PG_referenced才换来一个PG_active),这个过程叫做promotion(逆袭)。

这3种情景的代码实现是这样的(为了演示需要在源代码的基础上做了简化和修改):

1
2
3
4
5
6
7
8
9
void mark_page_accessed(struct page *page)
{
if (!PageActive(page) && PageReferenced(page)) {
activate_page(page);
}
else if (!PageReferenced(page)) {
SetPageReferenced(page);
}
}

当active list中的一个page在到达链表尾端时,如果其PG_referenced位为1,则被放回链表头部,但同时其PG_referenced会被清0。如果其PG_referenced位为0,那么就会被放入inactive list的头部,这个过程叫做demotion。可见,Linux采用的这种active list和inactive list并不是严格按照时间顺序来置换page的,所以是一种伪LRU算法。

Inactive list中尾端的页面不断被释放,相当于一个消费者,active list则不断地将尾端PG_referenced为0的页面放入inactive list,相当于一个生产者。不难想象,这2个链表的锁(lru_lock)应该是高度竞争的,如果从active list向inactive list的页面转移是一个一个进行的,那对锁的争抢将会十分严重。

为了解决这个问题,内核加入了一个per-CPU的lru cache(用struct pagevec表示),从active list换出的页面先放入当前CPU的lru cache中,直到lru cache中已经积累了PAGEVEC_SIZE(15)个页面,再获取lru_lock,将这些页面批量放入inactive list中。

如果inactive list比较长,那么每个页面在被回收之前有充分的时间被再次访问,从而被promote到active list,这样可以减少刚刚被回收又发生refault的页面数量(page thrashing)。但是由于内存总量有限,inactive list较长就意味着active list相对较短,那这2个链表应该分别多长比较合适呢?

我们可以在一个页面被回收时记录一个timestamp,当这个页面refault被换入时再记录一个timestamp,如果将inactive list的长度增加,使得页面回收增长的时间超过这2个timestamp的差值时,那么这个页面就可以因为在inactive list中被再次访问,避免了被回收的命运,也减小了refault造成的开销。

可是前面也提到过,由于硬件的限制,给每个page维护一个timestamp是不现实的。还是类似的解决办法,用inactive中回收页面的个数来替代timestamp,每回收一个页面,计数器加1(相当于用counter替代了timer)。那这个counter的值保存在哪里呢?

对于属于page cache的页面,由于其被换出之前是放在radix tree/xarray中的,当页面被回收时,我们可以把它曾经所在的entry利用起来,记录一下当前的counter值,页面被换入的时候再比较一下entry中的counter值,这种entry被称为shadow entry。

对于一个基于文件的page frame,好像它既在page cache结构中,又在active/inactive list结构中?没错,放在page cache中以radix tree/xarray的方式组织,是为了方便快速查找和读写它的内容,放在active/inactive list中则是为了方便内存回收。当一个基于文件的page frame被创建时,它就已经被加入到这2个结构中了:

1
2
3
4
5
6
int add_to_page_cache_lru(struct page *page, struct address_space *mapping,
pgoff_t offset, gfp_t gfp_mask)
{
__add_to_page_cache_locked(page, mapping, offset, gfp_mask, &shadow);
lru_cache_add(page);
}

这里同样是先放入lru cache,而不是直接放进active/inactive list中。

匿名页面的处理

对于anonymous pages,总是需要先写入swap area才能回收。而对于page cache,有一些可以直接discard(比如elf的text段对应的页面,data段对应的页面中clean的部分),有一些dirty的页面需要先write back同步到磁盘。

由于有flusher thread定期的write back,回收时还是dirty的page cache页面不会太多。而且,page cache中的页面有对应的文件和在文件中的位置信息,需要换入恢复的时候也更加容易。

因此,内核通常更倾向于换出page cache中的页面,只有当内存压力变得相对严重时,才会选择回收 anonymous pages。用户可以根据具体应用场景的需要,通过"/proc/sys/vm/swappiness"调节内存回收时anonymous pages和page cache的比重。

swappiness的值从0到100不等(默认一般是60),这个值越高,则回收的时候越优先选择anonymous pages。当swappiness等于100的时候,anonymous pages和page cache就具有相同的优先级。至于为什么不从开销最小的角度将swappiness设为0,将在后面给出答案。

1
2
3
4
5
6
/*
* With swappiness at 100, anonymous and file have the same priority.
* This scanning priority is essentially the inverse of IO cost.
*/
anon_prio = swappiness;
file_prio = 200 - anon_prio

早期的Linux实现中,每个 zone 中有 active 和 inactive 两个链表,每个链表上存放的页面不区分类型。为了实现优先回收page cache,之后每个链表拆分成了LRU_ANON和LRU_FILE,因此形成了LRU_INACTIVE_ANON, LRU_ACTIVE_ANON, LRU_INACTIVE_FILE和LRU_ACTIVE_FILE四种链表,而且改成了一个node对应一组链表(per-node),由代表node的struct pglist_data中的struct lruvec包含各个链表的头结点 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#define LRU_BASE 0
#define LRU_ACTIVE 1
#define LRU_FILE 2

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

struct lruvec {
struct list_head lists[NR_LRU_LISTS];
...
}

这里还有一个LRU_UNEVICTABLE链表。这个链表存储了flag为PG_unevictable的页面,因为unevictable的页面是不可以回收的,扫描的时候忽略LRU_UNEVICTABLE链表,将可以减少回收时扫描页面的总体时间。

可以通过"/proc/zoneinfo"查看这4种链表在node的各个zone上的分布:

更丰富的信息则包含在"/proc/meminfo"中,比如"Dirty"表示修改后还没有write back的页面,"Writeback"表示正在执行I/O操作进行回写的页面,还有就是系统所有"active"和"inactive"的page cache和anonymous page的统计数据。

如果swappiness的值为0,那么内核在启动内存回收时,将完全忽略anonymous pages,这将带来一个好处,就是内核只需要扫描page cache对应的inactive list(LRU_ACTIVE_FILE)就可以了,根本不用扫描anonymous pages对应的inactive list(LRU_ACTIVE_ANON),这样能极大的节约内存回收时花在扫描LRU链表上的时间。

但是,swappiness设置为0只适用于系统中page cache比较多的场景,如果系统中anonymous pages比page cache多很多,只回收page cache的话,可能无法满足direct relaim或者kswapd的需求。

这时本来系统中还有很多anonymous pages可供回收以释放内存,由于swappiness的限制,内核也许只有选择OOM killer了,所以用户在设置swappiness参数的时候,需要对自己的应用场景和内存的使用情况有比较深入的了解,要不然你可能会困惑:明明available的内存还很多啊,为啥老有进程被OOM kill呢。

触发机制

Linux内核中触发页面回收的机制大致有3个。

  • 直接页面回收机制。在内核态里调用页面分配接口函数alloe_pages()分配物理页面时,由于系统内存短缺,不能满足分配请求,因此内核会直接自陷到页面回收机制,这称为直接页面回收
  • 周期性回收内存机制。这是kswapd 内核线程的工作职责。当内核路径调用alloc_pages()分配物理页面时,由于系统内存短缺,没法在低水位情况下分配出内存,因此会唤醒kswapd内核线程来异步回收内存
  • slab收割机(slab shrinker)机制。这是用来回收slb对象的。当内存短缺时,直接页面回收和周期性回收内存两种机制都会调用slab收割机机制来回收slab对象。slab机制分配的内存主要用于slab对象和kmalloc接口,也可用于内核空间的内存分配,而本节重点介绍的是用户内存的回收

读者需要注意的是,直接回收内存的进程主体是调用者本身。另外,还有一个重要的特点一直接回收内存是同步回收,这会阻塞调用者进程的执行。 kswapd本身是内核线程,它和调用者的关系是异步的。

一个理想的情况是,我们能在内存压力不那么大的时候,就提前启动内存回收。而且,在某些场景下(比如在interrupt context或持有spinlock时),内存分配根本就是不能等待的。因此,Linux中另一种更为常见的内存回收机制是使用kswapd。

每个node对应一个内核线程kswapd,kswapd在被唤醒后将扫描各个zone的内存使用状态,并据此进行必要的内存回收操作,因此kswapd的回收方式又被称为"background reclaim"。至于什么情况下触发direct reclaim,什么情况下又会触发background reclaim,是由内存的"watermark"决定的。

Kswapd虽然名字中含有"swap",但它不光处理anonymous page的swap out回收,同样处理page cache的回收,而且它还肩负着平衡active list和inactive list的重任,所以被它调用的函数叫做balance_pgdat()。

不管是direct reclaim,还是kswapd,最终都是调用shrink_zone() --> shrink_page_list() 进行回收操作。

1
2
3
4
5
6
7
8
9
10
11
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, is_file_lru(lru), sc, true))
shrink_active_list(nr_to_scan, lruvec, sc, lru);
return 0;
}

return shrink_inactive_list(nr_to_scan, lruvec, sc, lru);
}

当inactive list中的页面比较少时,shrink_active_list()会从active list尾端转移一部分页面到inactive list中。这里的“少”是相对的,通常物理内存越大,inactive list的页面占比可以越小(页面总数还是增加的),因为inactive list的长度主要是用来减少短时间内refault的。

shrink_inactive_list --> shrink_page_list 将从inactive list尾端移除选定数目的页面,进行释放。

回收一个页面之前,如果该页面当前是被映射的(根据struct page的_mapcount域判断),需要调用try_to_unmap(),通过reserve mapping更改所有指向这个页面的PTEs。对于anonymous page,还需要在swap space中分配slot,并且将这个page标记为dirty的。anonymous page是没有backing store的,从dirty的角度,它可以算是一直dirty的。

前面提到过,不是所有的页面都可以被回收的。如果检测到页面的flag是PG_locked或者是PG_reserved的,则只能跳过。对于正在回写的(flag是PG_writeback的),通常也是放弃回收,有这功夫去等待回写完成,还不如去找链表上其他的clean page。

之后,对于flag是PG_dirty的页面,启动pageout()将这些页面备份或者同步到外部磁盘,这里“备份”针对的是anonymous page,“同步”针对的是page cache。

设置不回收

进程可以用申请swap token,拥有了swap token,就可以被内存回收算法暂时豁免,除非,内存实在已经紧张的不行了。在3.4版本中被移除了。

OOM

虽然OOM killer有时候可能导致严重的损失,但总比系统完全崩溃要好。这个无辜的bad process可不是随便挑的,应该优先选择这些:

  • 占有page frames比较多的,占有的多释放的才多,kill掉才有意义
  • 静态优先级比较低的

而不能选择这些:

  • 内核线程,因为内核线程往往执行的都是比较关键的任务
  • 进程号为1的init进程。如果父进程退出,而它的一个或多个子进程还在运行,那么这些子进程将被init进程托管,kill掉init进程是内核不允许的行为
  • 直接访问硬件设备的进程,如果强行终结这样的进程,可能将硬件置于一个不确定的状态

Refault Distance算法

在学术界和Linux内核社区,页面回收算法的优化一直没有停止过,其中Refault Distance算法在Linux3.15内核中加入,作者是社区专家Johannes Weiner,该算法目前只针对页面高速缓存类型的页面。 如下图所示,对于内容缓存类型的LRU链表来说,有两个链表值得关注,分别是活跃LRU链表和不活跃LRU链表。新产生的页面总是被添加到不活跃LRU链表的头部,页面回收也总是从不活跃LRU链表的尾部开始。不活跃LRU链表的页面第二次访问时会升级(promote)为活跃LRU链表的页面,防止被回收;另一方面,如果活跃LRU链表增长太快,那么活跃页面也会被降级(demote)到不活跃LRU链表中。

实际上,一些场景下,某些页面经常被访问,但是在下一次访问之前在不活跃LRU链表中回收并释放了它们,因此须从存储系统中读取这些内容缓存页面,这会产生颠簸(thrashing)现象。当我们观察文件缓存中不活跃LRU链表的行为特征时,会发现如下有趣特征。

  • 第一次访问一个文件缓存页面时,它被添加到不活跃LRU链表头,然后慢慢从链表头向链表尾方向移动,链表尾的内容缓存会被移出LRU链表且释放页面,这个过程叫作移出
  • 当第二次访问时,页面高速缓存被升级为活跃LRU链表中的页面高速缓存,这样不活跃LRU链表也空出一个位置,在不活跃LRU链表的页面整体移动了一个位置,这个过程叫作激活
  • 从宏观时间轴来看,移出过程处理的页面数量与激活过程处理的页面数量的总和等于不活跃LRU链表的长度NR_inactive
  • 要从不活跃LRU链表中释放一个页面,需要移动N个页面(N表示不活跃链表长度)

综合上面的一些行为特征,定义了Refault Distance的概念。第一次访问内容缓存称为fault,第二次访问该页称为refault。内容缓存页面第一次被移出LRU链表并回收的时刻称为E,第二次再访问该页面的时刻称为R,那么R-E的时间里需要移动的页面个数称为Refault Distance。

Refault Distance概念再加上第一次访问的时刻,可以用一个公式来概括第一次和第二次访问的间隙(read distance)。

read_distance=nr_inactive + (R - E)

如果页面想一直保持在LRU链表中,那么read_distance不应该比内存的大小还大;否则,该页面永远会被移出LRU链表。因此,下式成立。

NR_inactive + (R - E) ≤ NR_inactive + NR_active
(R - E) ≤ NR_active

换句话说,Refault Distance可以理解为不活跃LRU链表的“财政赤字”。如果不活跃LRU链表的长度至少再延长到Refault Distance,就可以保证该内容缓存在第二次访间之前不会被移出LRU链表并释放内存:否则,就要把该内容缓存重新加入活跃LRU链表加以保护,以防颠簸。在理想情况下,内容缓存的平均访问间隙要大于不活跃LRU链表的大小、小于总的内存大小。 上述内容讨论了两次读的间隙小于或等于内存大小的情况,即NR_inactive+(R-E)≤ NR_inactive - NR_active。如果两次读的间隙大于内存大小呢?这种特殊情况不是Refault Distance算法能解决的,因为它在第二次访问时己经永远被移出LRU链表,可以假设第二次访向发生在遥远的末来,但谁都无法保证它在LRU链表中。其实Refault Distance算法用于在第二次访问时,人为地把内容缓存添加到活跃LRU链表中,从而防止该内容缓存被移出LRU链表而带来的内存颠簸。

Refault Distance:算法如下图所示。T0时刻表示第一次访问一个内容缓存这时会调用add_to_page_cache_lru而配一个shadow来存储zone->inactive_age 值。每当有页面被升级为活跃LRU链表中的页面时,zone->inactive_age值会加1每当有面被移出不活跃LU表时,zone->inactive_age 值也加1. T1时刻,该页面被移出LRU链表并从LRU链表中回收释放因此把当前T1时刻的zone->inactive_age 的值编码存放到shadow中。T2时刻,第二次访问该页面,因此要计算Refault Distance,Refault Distance:=T2-T1,如果Retault Distances ≤ NR_active.说明该内容缓存极有可能在下一次读时已经被移出LRU链表,因此要人为地激活该页面并且将其加入活跃LRU链表中。

参考文献

https://zhuanlan.zhihu.com/p/70964195
https://zhuanlan.zhihu.com/p/72998605
《奔跑吧Linux内核》