[TOC]

list_lru: Linux内核的可扩展对象缓存管理器

list_lru 是 Linux 内核提供的一套可扩展的、近似 LRU (Least Recently Used) 缓存列表管理机制。它专门设计用来高效地管理大量、小型、生命周期不一的内核对象，例如目录项缓存（dentries）和索引节点缓存（inodes）。

可以将其想象成一个特殊的“图书馆卡片目录系统”，这个系统需要被许多图书管理员（CPU核心）同时、频繁地访问，并且需要一种高效的方式来找出那些最久未被使用的卡片（对象）以便回收。

一、 核心问题：为什么需要 list_lru？

在理解 list_lru 的设计之前，必须先明白它要解决的核心问题：在多核环境下的锁竞争。

一个朴素的 LRU 列表实现通常是这样的：

  1. 维护一个全局的双向链表。
  2. 当一个对象被访问时，将它从链表中的当前位置移到链表头（表示最新使用）。
  3. 当需要回收内存时，从链表尾部（表示最久未使用）开始移除对象。

这种实现在单核系统上工作得很好。但在现代多核系统中，会产生一个巨大的性能瓶颈：所有 CPU 核心都必须竞争同一个全局锁来修改这个链表。由于像 dentry 这样的对象被访问得极其频繁，这个全局锁会成为系统扩展性的噩梦，导致 CPU 核心花费大量时间在等待锁上，而不是做有用的工作。

list_lru 的诞生就是为了在保持 LRU 语义的同时，最大限度地减少锁竞争。

二、 核心原理与设计：Per-CPU 列表 + 批量操作

list_lru 的天才之处在于它避免了对每个对象的每次访问都去争抢一个全局锁。它通过一个两级结构实现了这一点：

  1. Per-CPU 私有列表:

    • list_lru 不再维护一个单一的全局列表，而是在内部为**每个 CPU 核心（或每个 NUMA 节点）**都创建了一个私有的、本地的“新对象”列表。
    • 当一个对象需要被添加到 LRU 列表时（例如，一个 dentry 被创建或访问），它会被添加到当前正在执行的 CPU 核心的本地列表中。
    • 对这个本地列表的访问只需要获取该 CPU 的本地锁，甚至在某些情况下可以无锁操作。因此，不同 CPU 核心之间添加新对象的操作完全不会相互干扰。

  2. 一个全局共享列表:

    • 除了 Per-CPU 列表外，还有一个传统的、由全局锁保护的共享列表。这个列表存放的是“比较旧”的对象。

  3. 批量迁移 (Batching):

    • Per-CPU 列表并不会无限增长。当某个 Per-CPU 列表中的对象数量达到一个阈值（或者在某些其他条件下），list_lru 会执行一次批量迁移操作。
    • 它会一次性地将这个 Per-CPU 列表中的所有对象作为一个整体，移动到全局共享列表的头部。
    • 这个迁移操作虽然需要获取全局锁，但它的开销被摊销了。我们用“一次昂贵的、但 infrequent 的批量操作”替换了“无数次廉价的、但 highly contended 的单次操作”。

  4. 回收/扫描:

    • 当内核需要回收内存（例如，通过 shrinker 机制）时，回收程序只需要扫描全局共享列表。
    • 它会从全局列表的尾部开始，获取一批最久未使用的对象进行回收。

设计图示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
           CPU 0           CPU 1           CPU 2           CPU 3
          [ Local ]       [ Local ]       [ Local ]       [ Local ]
          [ List  ]       [ List  ]       [ List  ]       [ List  ]
              |               |               |               |
   (Fast, lockless add)   (Fast, lockless add)  ...           ...
              |               |               |               |
              V               V               V               V
          +-------------------------------------------------------+
          |                  BATCHING OPERATION                   |
          |          (Moves entire local list when full)          |
          +-------------------------------------------------------+
                              | (Acquires Global Lock)
                              V
+--------------------------------------------------------------------------+
|                            GLOBAL SHARED LIST                            |
|                                                                          |
|  <-- HEAD (Newer batches from CPUs) . . . . . . TAIL (Oldest objects) --> |
+--------------------------------------------------------------------------+
                                                                     |
                                                                     V (Acquires Global Lock)
                                                                 PRUNING / EVICTION
                                                                 (Scans from the tail)

三、 关键数据结构与 API

  • struct list_lru:

    • 这是 list_lru 的主容器结构。
    • 它包含一个全局的自旋锁 (lock) 和一个全局的链表头 (list)。
    • 最重要的是，它包含一个指向 Per-CPU/Per-Node 列表数组的指针（struct list_lru_node *node[]），这使得它可以根据 CPU 或 NUMA 节点找到对应的本地列表。

  • struct list_lru_node:

    • 代表一个 Per-CPU/Per-Node 的本地存储。它内部也包含一个链表头 (list) 和一个本地锁。

核心 API:

  • int list_lru_init(struct list_lru *lru):
    初始化一个 list_lru 结构，包括分配和初始化其内部的 Per-CPU 列表。

  • void list_lru_add(struct list_lru *lru, struct list_head *item):
    最常用的函数。将一个新对象 item 添加到 LRU 中。这个操作通常只访问本地列表，因此速度非常快，竞争很小。

  • void list_lru_del(struct list_lru *lru, struct list_head *item):
    从 LRU 中删除一个对象。这个操作比 add 复杂，因为它需要判断 item 是在本地列表还是在全局列表中，并可能需要获取全局锁。

  • long list_lru_walk(struct list_lru *lru, list_lru_walk_cb isolate, void *cb_arg, long nr_to_walk):
    这是用于扫描和回收的核心函数。它会遍历全局列表，对每个对象调用一个由用户提供的回调函数 isolate。内存回收器（shrinker）就是通过这个函数来找到并尝试回收旧对象的。

四、 实际应用场景

list_lru 在内核中被广泛用于需要管理大量可回收对象的子系统。

  1. 目录项缓存 (Dentry Cache):

    • 这是 list_lru 的经典用例。系统中有数以万计甚至百万计的 dentry 对象。d_lru_add() 函数内部就调用了 list_lru_add()。
    • 当内存不足时，VFS shrinker 会调用 list_lru_walk 来扫描 dentry LRU，并释放那些未被使用的 dentry。

  2. 索引节点缓存 (Inode Cache):

    • 与 dentry 类似，inode_add_lru() 也是基于 list_lru 实现的。
    • 内存回收时，也会扫描 inode LRU 来回收不活跃的 inode 对象。

  3. 其他: 某些文件系统也可能使用 list_lru 来管理其私有的元数据缓存。

五、 总结

list_lru 是 Linux 内核为了应对多核时代高并发、高竞争环境而设计出的一套精妙的缓存管理方案。

核心思想:

  • 空间换时间: 使用多个 Per-CPU 列表（空间）来避免全局锁竞争（时间）。
  • 批处理摊销: 将高频的、有竞争的单次操作，替换为低频的、无竞争的本地操作，外加一次性的批量同步操作，从而将锁竞争的开销降至最低。

通过这种设计，list_lru 成功地为 dentry 和 inode 等内核中最活跃的缓存对象提供了高度可扩展的近似 LRU 管理，是保证 Linux 在现代多核服务器上依然能保持高性能的关键基础设施之一。

mm/list_lru.c

list_lru_add 将对象（item）添加到 LRU（最近最少使用）列表中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/* 调用方必须确保 memcg 生存期。 */
bool list_lru_add(struct list_lru *lru, struct list_head *item, int nid,
		  struct mem_cgroup *memcg)
{
	struct list_lru_node *nlru = &lru->node[nid];
	struct list_lru_one *l;

    /* 锁定与内存控制组（memcg）关联的 LRU 列表 */
	l = lock_list_lru_of_memcg(lru, nid, memcg, false, false);
    /* 如果无法锁定（例如 memcg 生命周期已结束），函数返回 false，表示添加失败 */
	if (!l)
		return false;
    /* 如果对象为空，表示它可以安全地添加到 LRU 列表中 */
	if (list_empty(item)) {
        /* 将对象添加到 LRU 列表的尾部 */
		list_add_tail(item, &l->list);
		/* 如果添加了第一个元素，则设置 shrinker bit */
		if (!l->nr_items++)
            /* Shrinker 位用于标记 LRU 列表需要被回收器（Shrinker）处理 */
			set_shrinker_bit(memcg, nid, lru_shrinker_id(lru));
		unlock_list_lru(l, false);
		atomic_long_inc(&nlru->nr_items);
		return true;
	}
	unlock_list_lru(l, false);
	return false;
}

list_lru_add_obj 将对象（item）添加到 LRU（最近最少使用）列表中

  • lRU 是一种缓存管理机制，优先保留最近使用的对象并逐步移除较少使用的对象。该函数支持内存控制组（Memory Control Groups，memcg）的感知功能，以优化内存管理
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
bool list_lru_add_obj(struct list_lru *lru, struct list_head *item)
{
	bool ret;
	int nid = page_to_nid(virt_to_page(item));

    /* return false; */
	if (list_lru_memcg_aware(lru)) {
		rcu_read_lock();
		ret = list_lru_add(lru, item, nid, mem_cgroup_from_slab_obj(item));
		rcu_read_unlock();
	} else {
		ret = list_lru_add(lru, item, nid, NULL);
	}

	return ret;
}
EXPORT_SYMBOL_GPL(list_lru_add_obj);

list_lru_del 从 LRU（最近最少使用）列表中删除指定的对象（item）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* 调用方必须确保 memcg 生存期。 */
bool list_lru_del(struct list_lru *lru, struct list_head *item, int nid,
		  struct mem_cgroup *memcg)
{
	struct list_lru_node *nlru = &lru->node[nid];
	struct list_lru_one *l;
	l = lock_list_lru_of_memcg(lru, nid, memcg, false, false);
	if (!l)
		return false;
	if (!list_empty(item)) {
		list_del_init(item);
		l->nr_items--;
		unlock_list_lru(l, false);
		atomic_long_dec(&nlru->nr_items);
		return true;
	}
	unlock_list_lru(l, false);
	return false;
}

list_lru_del_obj 从 LRU（最近最少使用）列表中删除指定的对象（item

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
bool list_lru_del_obj(struct list_lru *lru, struct list_head *item)
{
	bool ret;
	int nid = page_to_nid(virt_to_page(item));

	if (list_lru_memcg_aware(lru)) {
		rcu_read_lock();
		ret = list_lru_del(lru, item, nid, mem_cgroup_from_slab_obj(item));
		rcu_read_unlock();
	} else {
		ret = list_lru_del(lru, item, nid, NULL);
	}

	return ret;
}
EXPORT_SYMBOL_GPL(list_lru_del_obj);

init_one_lru 初始化一个 list_lru_one 结构

1
2
3
4
5
6
7
8
9
10
static void init_one_lru(struct list_lru *lru, struct list_lru_one *l)
{
	INIT_LIST_HEAD(&l->list);
	spin_lock_init(&l->lock);
	l->nr_items = 0;
#ifdef CONFIG_LOCKDEP
	if (lru->key)
		lockdep_set_class(&l->lock, lru->key);
#endif
}

__list_lru_init 初始化一个 list_lru 结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int __list_lru_init(struct list_lru *lru, bool memcg_aware, struct shrinker *shrinker)
{
	int i;

	lru->node = kcalloc(nr_node_ids, sizeof(*lru->node), GFP_KERNEL);
	if (!lru->node)
		return -ENOMEM;

	for_each_node(i)
		init_one_lru(lru, &lru->node[i].lru);

	// memcg_init_list_lru(lru, memcg_aware);
	// list_lru_register(lru);

	return 0;
}
EXPORT_SYMBOL_GPL(__list_lru_init);