# Page Fram Reclaim Algorithm 内存回收的算法，在Gorman的巨著[Understanding the Linux Virtual Memory Manager](https://www.kernel.org/doc/gorman/html/understand/)中有详细的介绍。 [Page Frame Reclaim Algorithm](https://www.kernel.org/doc/gorman/html/understand/understand013.html) 虽然这部分已经是古董级的材料了，但是作为原理还是很值得研究的。 ## LRU定义 回收策略通常被称为Least Recently Used (LRU)。在内核中，对应的数据结构是lruvec。 ``` lruvec +-------------------------------+ |lists[NR_LRU_LISTS] | | (struct list_head) | |lru_lock | | (spinlock_t) | |anon_cost | |file_cost | | (unsigned long) | |nonresident_age | | (atomic_long_t) | |flags | | (unsigned long) | |refaults[ANON_AND_FILE] | | (unsigned long) | |pgdat | | (struct pglist_data*) | +-------------------------------+ ``` 其中lists代表的就是大名鼎鼎的lru lists。这个上面一共有五个链表： ``` * LRU_INACTIVE_ANON * LRU_ACTIVE_ANON * LRU_INACTIVE_FILE * LRU_ACTIVE_FILE * LRU_UNEVICTABLE ``` 简单来说，回收的过程就是从lru lists上找到合适的page做回收。 ### lruvec在哪里 lruvec是可以理解成一个系统中已经分配除去的页面的集散地，目的是为了后续释放而存在的。要找到这个lruvec在哪里，我们就要看folio\_lruvec()这个函数。 毕竟内核演化这么多年了，这个lruvec可能出现在两个不同的位置。PS：当然不是同时出现。 * pgdat->\_\_lruvec: 没有memcg，或者有memcg但是disable的情况下 * memcg的lruvec: 有memcg且enable的情况下 所以在操作lruvec时，会先找到folio对应的memcg，然后去操作。 ## 把页放到lru上之前 lru是这样一个数据结构，就好像一个收纳箱。我们把使用的页放在里面，当这个箱子塞满的时候，我们就要清理这个箱子。为了能够更好的清理，我们按照了一定算法在这个箱子里摆放页。这个工作在内核中就是PFRA(Page Frame Reclaim Algorithm)算法了。 为了更好的理解这个算法，我们可以将这个过程进一步拆解为： * 将页存放进箱子和箱子内腾挪的步骤 * 腾挪操作的算法原理 第一步完全是为了更好理解内核代码做的工程化拆解，也是本小节的主要内容。但是再放到lru之前，内核为了减少竞争，增加了一个存放的缓存空间。 ### cpu\_fbatches 说实话，下面的pagevec我已经全忘记了。现在,2025.10.06，重看这部分代码，pagevec已经消失了。如果我没有猜错的话，替代pagevec的，就是cpu\_fbatches。 首先，这也是一个percpu的变量，可以也是一个加入到lru之前的缓冲区。 ``` cpu_fbatches +-------------------------------+ |lock | | (local_lock_t) | |lru_add | |lru_deactivate_file | |lru_deactivate | |lru_lazyfree | |lru_activate | | (struct folio_batch) | | +--------------------------+ | |i | | |nr | | | (unsigned char) | | |pages[PAGEVEC_SIZE] | | | (struct page*) | | |percpu_pvec_drained | | | (bool) | | +--------------------------+ |lock_irq | | (local_lock_t) | |lru_move_tail | | (struct folio_batch) | +-------------------------------+ ``` 这么看，其实和原来的lru\_pvecs很像，不过是用folio\_batch替换了之前的pagevec。然后再一看，folio\_batch和pagevec也是很像的。所以这个其实就是从page到folio的一个变化。 对应的commit也可以看出这个变化。 ``` commit 10331795fb7991a39ebd0330fdb074cbd81fef48 Author: Matthew Wilcox (Oracle) Date: Mon Dec 6 15:24:51 2021 -0500 pagevec: Add folio_batch The folio_batch is the same as the pagevec, except that it is typed to contain folios and not pages. ``` 除了数据结构的变化，操作上也发生了变化。我猜现在操作上主要都集中到了函数folio\_batch\_add\_and\_move()。 ``` static void __folio_batch_add_and_move(struct folio_batch __percpu *fbatch, struct folio *folio, move_fn_t move_fn, bool disable_irq) { unsigned long flags; folio_get(folio); if (disable_irq) local_lock_irqsave(&cpu_fbatches.lock_irq, flags); else local_lock(&cpu_fbatches.lock); if (!folio_batch_add(this_cpu_ptr(fbatch), folio) || !folio_may_be_lru_cached(folio) || lru_cache_disabled()) folio_batch_move_lru(this_cpu_ptr(fbatch), move_fn); if (disable_irq) local_unlock_irqrestore(&cpu_fbatches.lock_irq, flags); else local_unlock(&cpu_fbatches.lock); } #define folio_batch_add_and_move(folio, op) \ __folio_batch_add_and_move( \ &cpu_fbatches.op, \ folio, \ op, \ offsetof(struct cpu_fbatches, op) >= \ offsetof(struct cpu_fbatches, lock_irq) \ ) ``` 不得不说，内核开发者这些c语言大师对代码的精妙处理。这种代码都写得出来。 第一步是将folio添加到对应的folio\_batch中，起到了缓存的作用。如果对应的folio\_batch满了，才会使用folio\_batch\_move\_lru()，并通过对应的move\_fn对folio进行处理。: ``` static void folio_batch_move_lru(struct folio_batch *fbatch, move_fn_t move_fn) { int i; struct lruvec *lruvec = NULL; unsigned long flags = 0; for (i = 0; i < folio_batch_count(fbatch); i++) { struct folio *folio = fbatch->folios[i]; /* block memcg migration while the folio moves between lru */ if (move_fn != lru_add && !folio_test_clear_lru(folio)) continue; folio_lruvec_relock_irqsave(folio, &lruvec, &flags); move_fn(lruvec, folio); folio_set_lru(folio); } if (lruvec) unlock_page_lruvec_irqrestore(lruvec, flags); folios_put(fbatch); } ``` 从cpu\_fbatches的定义可以看出，这里的move\_fn有6种可能性: * lru\_add * lru\_deactivate\_file * lru\_deactivate * lru\_lazyfree * lru\_activate * lru\_move\_tail 而这些就是将folio放到对应lruvec上链表的具体操作了。 ### mlock\_fbatch 除了上面者几种batch，还有一个比较特殊的batch -- mlock\_fbatch。 这个是专门为mlock相关的操作使用的。 ### pagevec -- 老版本 半路杀出个程咬金，lruvec的怎么又出来了个pagevec？怎么讲呢，内核为了减少锁竞争，在把页放入lruvec前，先放到percpu的pagevec上。相当于做了一个软cache。 我们先来看看内核中有多少pagevec。 ``` lru_pvecs lru_rotate +-------------------------------+ +-------------------------------+ |lock | |lock | | (local_lock_t) | | (local_lock_t) | |lru_add | |pvec | |lru_deactivate_file | | (struct pagevec) | |lru_deactivate | +-------------------------------+ |lru_lazyfree | |activate_page | | (struct pagevec) | | +--------------------------+ mlock_pvec(struct pagevec) | |pages[PAGEVEC_SIZE] | +-------------------------------+ | | (struct page*) | | | | |nr | +-------------------------------+ | | (unsigned char) | | |percpu_pvec_drained | | | (bool) | | | | +----+--------------------------+ ``` 考虑到内核中还有别的子系统使用pagevec，这里只列出和lru相关的。所以这么数来，一共有七个相关的pagevec。而对于每一个pagevec，内核中都有对应的函数处理。咱们先把相关的函数展示出来。 ``` folio_rotate_reclaimable lru_rotate.pvec | | folio_activate deactivate_page lru_pvecs.activate_page lru_pvecs.lru_deactivate | / / / / folio_add_lru | deactivate_file_folio mark_page_lazyfree lru_pvecs.lru_add lru_pvecs.lru_deactivate_file lru_pvecs.lru_lazyfree \ | / / / \ | / / / v v v v v pagevec_add_and_need_flush / \ / \ __pagevec_lru_add pagevec_lru_move_fn mlock_page_drain mlock_folio mlock_new_page munlock_page \ \ / / \ \ / / \ \ / / mlock_pagevec / \ / \ __mlock_page __mlock_new_page __munlock_page ``` 本来我想把这两个合一块的，社区没同意。也好，那就分开看看。 先解释一下上面的图： * mlock\_pvec 比较独立。添加到mlock\_pvec后，由mlock\_pagevec加到lru上 * 其余的pagevec都通过pagevec\_add\_and\_need\_flush检查后，做相应的操作 * folio\_add\_lru/mlock\_new\_page 是两个加入到pagevec的入口函数 ### 消失的LRU\_UNEVICTABLE 在lruvec定义中，lru的list一共有五个。但是仔细看真正操作list的函数：lruvec\_add\_folio()/lruvec\_add\_folio\_tail()，最后都过滤了LRU\_UNEVICTABLE。当时我很纳闷究竟什么时候会添加到这个链表。 直到看到了\_\_mlock\_folio()的注释。 ``` * An mlocked folio [folio_test_mlocked(folio)] is unevictable. As such, it * will be ostensibly placed on the LRU "unevictable" list (actually no such * list exists), rather than the [in]active lists. PG_unevictable is set to * indicate the unevictable state. ``` 实际上根本就没有用这个链表，也是，不需要回收，所以也不会去扫描吧。 ## API 整理 最核心操作lruvec的函数只有三个： * lruvec\_add\_folio() * lruvec\_add\_folio\_tail() * lruvec\_del\_folio() 但根据不同的需求，内核中对操作进行了一定的封装，下面尝试按照不同的类型分类整理。 ``` folio_add_lru() folio_activate() folio_deactivate() mlock_folio() deactivate_file_folio() mlock_new_folio() folio_mark_lazyfree() munlock_folio() folio_rotate_reclaimable() | | | | | | v v mlock_folio_batch() folio_batch_add_and_move() | | | | | | v v __mlock_new_folio() lru_add() move_folios_to_lru() __mlock_folio() lru_activate() drain_evictable() __munlock_folio() lru_deactivate() check_move_unevictable_folios() lru_deactivate_file() sort_folio() lru_lazyfree() \ | / \ | / \ | / v lruvec_add_folio() lru_move_tail() lru_deactivate_file() | | v lruvec_add_folio_tail() __mlock_folio() __page_cache_release() folio_isolate_lru() __munlock_folio() lru_move_tail() fill_evictable() lru_activate() check_move_unevictable_folios() lru_deactivate() lru_deactivate_file() isolate_migratepages_block() lru_lazyfree() \ | / \ | / \ | / v lruvec_del_folio() ``` 虽然有很多函数会调用lruvec\_add\_folio()/lruvec\_del\_folio()，但并不是表示folio就添加到lruvec或者从lruvec上删除了。因为很多操作是从一个链表移动到了另一个链表。 真正添加到lruvec的： * \_\_mlock\_new\_folio() * lru\_add() * move\_folios\_to\_lru() 真正从lruvec删除的： * \_\_page\_cache\_release() * folio\_isolate\_lru() 另外mlock是比较特殊的一支，他还用了单独的mlock\_fbatch.