# List LRU (List-based Least Recently Used)

Linux 7.0 메모리 관리 분석 시리즈

---

개요 (Overview)

List LRU는 리눅스 커널에서 범용 LRU(Least Recently Used) 인프라를 제공하는 하위 시스템입니다. dentry 캐시, inode 캐시, shmem 페이지 등 다양한 커널 캐시 항목들을 LRU 순서로 관리하고, 메모리 부족 시 효과적으로 회수할 수 있도록 합니다. List LRU는 struct list_head 기반의 단일 연결 리스트를 사용하여 구현되며, NUMA 노드별, 메모리 cgroup별로 독립적인 리스트를 유지합니다.

이 인프라의 핵심은 shrinker와의 통합입니다. list_lru_walk_one()과 같은 함수를 통해 콜백 기반으로 리스트를 순회하면서 회수 가능한 항목을 격리(isolate)하거나 제거합니다. CONFIG_MEMCG가 활성화된 시스템에서는 메모리 cgroup별로 별도의 LRU 리스트를 할당하여 컨테이너 간 메모리 격리를 보장합니다.

page reclaim에서 말하는 active/inactive anon/file LRU와는 역할이 다릅니다. List LRU는 페이지 자체를 관리하지 않고, dentry나 inode처럼 shrinker가 회수할 커널 오브젝트를 모아 두는 보조 목록입니다. 그래서 shrink_slab() 경로에서 호출되어 슬랩 계열 회수와 함께 움직이며, 페이지 회수 LRU와는 대상과 단위가 구분됩니다.

일상 비유

List LRU는 도서관에서 오래된 잡지를 정리하는 시스템과 비슷합니다. 각 주제(메모리 cgroup)별로 별도의 서가(NUMA 노드)가 있고, 각 서가에서는 읽힌 지 오래된 잡지부터 정리 대상으로 표시합니다. 정리할 때는 먼저 잡지를 빼서(isolate) 목록에서 지우고, 필요하면 다른 서가로 옮깁니다.

소스 파일

mm/list_lru.c                    ← LRU 핵심 로직 (618줄)
include/linux/list_lru.h         ← 구조체 정의, API 선언 (289줄)
mm/slab.h                        ← 내부 헬퍼
mm/internal.h                    ← set_shrinker_bit() 등
include/linux/memcontrol.h       ← memcg 연동

---

빠른 점검 명령

# 1. list_lru 관련 커널 심볼 확인
cat /proc/kallsyms | grep -E "list_lru_add|list_lru_del|list_lru_walk" | head -10

# 2. CONFIG_MEMCG 컴파일 옵션 확인
grep CONFIG_MEMCG /boot/config-$(uname -r) 2>/dev/null || zcat /proc/config.gz 2>/dev/null | grep CONFIG_MEMCG

# 3. slab 캐시 통계에서 dentry/inode 캐시 확인 (list_lru 사용처)
cat /proc/slabinfo | grep -E "dentry|inode_cache|shmem_inode_cache"

# 4. 메모리 cgroup별 메모리 사용량 확인
cat /sys/fs/cgroup/memory/memory.limit_in_bytes 2>/dev/null || cat /sys/fs/cgroup/memory.max 2>/dev/null

# 5. shrinker 등록 정보 확인
cat /sys/kernel/mm/leak_debug/objects 2>/dev/null || echo "leak_debug not available"

# 6. /proc/vmstat에서 캐시 회수 관련 카운터
cat /proc/vmstat | grep -E "pgscan|pgsteal|nr_slab|nr_dentry|nr_inode"

# 7. list_lru 관련 모듈 정보
modinfo list_lru 2>/dev/null || echo "Built-in module"

# 8. memcg slab 통계
cat /sys/fs/cgroup/memory/memory.stat 2>/dev/null | grep -E "slab|dentry|inode" | head -10

# 9. 커널 빌드 옵션에서 list_lru 관련 확인
grep -r "CONFIG_LIST_LRU" /boot/config-$(uname -r) 2>/dev/null

# 10. list_lru 사용 코드 위치 추적
grep -rn "list_lru_add\|list_lru_del\|list_lru_walk" /usr/src/linux-*/fs/ 2>/dev/null | head -10

# 11. 페이지 회수 압력과 연계 지표 확인
cat /proc/vmstat | grep -E "pgscan|pgsteal|allocstall|kswapd"

# 12. 현재 메모리 압력 확인
cat /proc/pressure/memory

# 13. 스왑 상태 확인
swapon --show

# 14. 스왑 정책 확인
cat /proc/sys/vm/swappiness

---

핵심 자료구조

1. `struct list_lru_one` — 개별 LRU 리스트

각 memcg + NUMA node 조합에 하나씩 존재하는 기본 LRU 리스트입니다.

// include/linux/list_lru.h:31-37
struct list_lru_one {
struct list_head    list;       // 연결 리스트 헤드
// memcg reparenting 중 음수가 될 수 있음
long                nr_items;   // 현재 리스트의 아이템 수
// 모든 필드를 보호하는 스핀락
spinlock_t          lock;
};

2. `struct list_lru_node` — NUMA 노드별 LRU

NUMA 시스템에서 각 노드마다 하나씩 존재하며, 루트 cgroup용 글로벌 LRU와 카운터를 포함합니다.

// include/linux/list_lru.h:45-49
struct list_lru_node {
// 루트 cgroup용 글로벌 리스트
struct list_lru_one lru;
atomic_long_t       nr_items;   // 전체 아이템 수 (atomic)
} ____cacheline_aligned_in_smp;

3. `struct list_lru_memcg` — memcg별 LRU

메모리 cgroup이 할당될 때마다 동적으로 할당되는 per-memcg LRU입니다.

// include/linux/list_lru.h:39-43
struct list_lru_memcg {
struct rcu_head     rcu;        // RCU 해제용
// 노드별 per-cgroup 리스트 (유연한 배열)
struct list_lru_one node[];
};

4. `struct list_lru` — 최상위 LRU 구조체

List LRU의 최상위 구조체로, 모든 NUMA 노드와 memcg 정보를 관리합니다.

// include/linux/list_lru.h:51-62
struct list_lru {
struct list_lru_node    *node;      // NUMA 노드별 LRU 배열
#ifdef CONFIG_MEMCG
struct list_head        list;       // memcg_list_lrus 연결용
int                     shrinker_id; // 연결된 shrinker ID
bool                    memcg_aware; // memcg 인식 여부
struct xarray           xa;         // memcg ID → list_lru_memcg 매핑
#endif
#ifdef CONFIG_LOCKDEP
struct lock_class_key   *key;       // lockdep 클래스 키
#endif
};

5. `enum lru_status` — walk 콜백 반환 값

list_lru_walk_one()의 콜백 함수가 반환하는 상태 값입니다.

// include/linux/list_lru.h:19-29
enum lru_status {
LRU_REMOVED,        // 아이템이 리스트에서 제거됨
LRU_REMOVED_RETRY,  // 제거됨, 잠금 해제 후 다시 시도
LRU_ROTATE,         // 아이템이 참조됨, 다시 순회
LRU_SKIP,           // 아이템 잠금 불가, 건너뜀
LRU_RETRY,          // 아이템 해제 불가, 다시 시도
LRU_STOP,           // 순회 중지
};

---

핵심 함수

1. `list_lru_add()` / `list_lru_add_obj()`

LRU 리스트에 아이템을 추가합니다. list_lru_add()는 명시적으로 nid와 memcg를 지정하고, list_lru_add_obj()는 아이템의 물리 주소에서 자동으로 결정합니다.

// mm/list_lru.c:161-181
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;

l = lock_list_lru_of_memcg(lru, nid, memcg, false, false);
if (!l)
return false;
if (list_empty(item)) {
list_add_tail(item, &l->list);
// 첫 번째 요소 추가 시 shrinker 비트 설정
if (!l->nr_items++)
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;
}

분기 로직:

lock_list_lru_of_memcg()로 memcg별 리스트 획득 실패 시 false 반환

아이템이 이미 리스트에 있는 경우(list_empty() 실패) 추가하지 않음

첫 번째 요소 추가 시 set_shrinker_bit()로 shrinker에 알림

2. `list_lru_del()` / `list_lru_del_obj()`

LRU 리스트에서 아이템을 삭제합니다.

// mm/list_lru.c:201-218
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_empty()가 true인 경우)은 삭제하지 않음

list_del_init()으로 제거 후 초기화

3. `__list_lru_walk_one()` — 핵심 순회 로직

LRU 리스트를 순회하면서 콜백 함수를 호출하여 항목을 격리하거나 제거합니다.

// mm/list_lru.c:279-334
static unsigned long
__list_lru_walk_one(struct list_lru *lru, int nid, struct mem_cgroup *memcg,
list_lru_walk_cb isolate, void *cb_arg,
unsigned long *nr_to_walk, bool irq_off)
{
struct list_lru_node *nlru = &lru->node[nid];
struct list_lru_one *l = NULL;
struct list_head *item, *n;
unsigned long isolated = 0;

restart:
l = lock_list_lru_of_memcg(lru, nid, memcg, irq_off, true);
if (!l)
return isolated;
list_for_each_safe(item, n, &l->list) {
enum lru_status ret;

if (!*nr_to_walk)
break;
--*nr_to_walk;

ret = isolate(item, l, cb_arg);
switch (ret) {
case LRU_RETRY:
goto restart;
case LRU_REMOVED_RETRY:
fallthrough;
case LRU_REMOVED:
isolated++;
atomic_long_dec(&nlru->nr_items);
if (ret == LRU_REMOVED_RETRY)
goto restart;
break;
case LRU_ROTATE:
list_move_tail(item, &l->list);
break;
case LRU_SKIP:
break;
case LRU_STOP:
goto out;
default:
BUG();
}
}
unlock_list_lru(l, irq_off);
out:
return isolated;
}

분기 로직:

LRU_RETRY: 잠금 해제 후 처음부터 다시 순회

LRU_REMOVED_RETRY: 아이템 제거 후 다시 순회

LRU_REMOVED: 아이템 제거, 다음 항목으로 이동

LRU_ROTATE: 아이템을 리스트 끝으로 이동

LRU_SKIP: 건너뜀

LRU_STOP: 순회 중지

4. `list_lru_walk_node()` — 노드 전체 순회

특정 NUMA 노드의 모든 memcg에 대해 LRU 순회를 수행합니다.

// mm/list_lru.c:355-391
unsigned long list_lru_walk_node(struct list_lru *lru, int nid,
list_lru_walk_cb isolate, void *cb_arg,
unsigned long *nr_to_walk)
{
long isolated = 0;

isolated += list_lru_walk_one(lru, nid, NULL, isolate, cb_arg,
nr_to_walk);

#ifdef CONFIG_MEMCG
if (*nr_to_walk > 0 && list_lru_memcg_aware(lru)) {
struct list_lru_memcg *mlru;
struct mem_cgroup *memcg;
unsigned long index;

xa_for_each(&lru->xa, index, mlru) {
rcu_read_lock();
memcg = mem_cgroup_from_private_id(index);
if (!mem_cgroup_tryget(memcg)) {
rcu_read_unlock();
continue;
}
rcu_read_unlock();
isolated += __list_lru_walk_one(lru, nid, memcg,
isolate, cb_arg,
nr_to_walk, false);
mem_cgroup_put(memcg);

if (*nr_to_walk <= 0)
break;
}
}
#endif

return isolated;
}

분기 로직:

먼저 루트 memcg(NULL)의 LRU를 순회

memcg_aware인 경우 Xarray를 순회하며 각 memcg의 LRU를 순회

memcg 참조 카운트 실패 시 해당 memcg는 건너뜀

5. `__list_lru_init()` / `list_lru_destroy()`

List LRU의 초기화와 소멸을 담당합니다.

// mm/list_lru.c:574-600
int __list_lru_init(struct list_lru *lru, bool memcg_aware, struct shrinker *shrinker)
{
int i;

#ifdef CONFIG_MEMCG
if (shrinker)
lru->shrinker_id = shrinker->id;
else
lru->shrinker_id = -1;

if (mem_cgroup_kmem_disabled())
memcg_aware = false;
#endif

lru->node = kzalloc_objs(*lru->node, nr_node_ids);
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;
}

---

호출 흐름

LRU 추가/삭제 흐름

list_lru_add_obj() / list_lru_del_obj()
├─ virt_to_page() → page_to_nid() → NUMA 노드 결정
├─ mem_cgroup_from_virt() → memcg 결정 (memcg_aware인 경우)
└─ list_lru_add() / list_lru_del()
├─ lock_list_lru_of_memcg()
│    ├─ list_lru_from_memcg_idx() → memcg별 list_lru_one 획득
│    └─ lock_list_lru() → 스핀락 획득
├─ list_add_tail() / list_del_init()
├─ set_shrinker_bit() (첫 추가 시)
└─ unlock_list_lru()

LRU 순회 흐름

list_lru_walk_node()
├─ list_lru_walk_one(NULL memcg)
│    └─ __list_lru_walk_one()
│         ├─ lock_list_lru_of_memcg()
│         ├─ list_for_each_safe() 순회
│         │    ├─ isolate() 콜백 호출
│         │    └─ lru_status에 따른 분기
│         └─ unlock_list_lru()
└─ xa_for_each() (memcg_aware인 경우)
└─ __list_lru_walk_one() (각 memcg별)

shrinker 연동 흐름

try_to_free_pages() / kswapd
└─ shrink_slab()
└─ list_lru_shrink_walk()
└─ list_lru_walk_one()
└─ __list_lru_walk_one()
└─ isolate() 콜백 → LRU_REMOVED / LRU_ROTATE / LRU_STOP

list_lru_shrink_walk()는 struct shrink_control의 nid, memcg, nr_to_scan을 그대로 받아 list_lru_walk_one()으로 넘깁니다. 이 때문에 슬랩 회수량은 페이지 회수량과 따로 움직이지만, 메모리 압력이 높을 때는 두 경로가 함께 관측됩니다.

초기화/소멸 흐름

__list_lru_init()
├─ kzalloc_objs() → node 배열 할당
├─ for_each_node() → init_one_lru() 각 노드 초기화
├─ memcg_init_list_lru() → Xarray 초기화
└─ list_lru_register() → memcg_list_lrus에 추가

list_lru_destroy()
├─ list_lru_unregister() → memcg_list_lrus에서 제거
├─ memcg_destroy_list_lru() → Xarray 항목 해제
└─ kfree(node)

---

조건별 비교

List LRU API 비교

함수	역할	memcg 처리	NUMA 처리
`list_lru_add()`	아이템 추가	명시적 memcg 지정	명시적 nid 지정
`list_lru_add_obj()`	아이템 추가	virt에서 자동 결정	virt에서 자동 결정
`list_lru_del()`	아이템 삭제	명시적 memcg 지정	명시적 nid 지정
`list_lru_del_obj()`	아이템 삭제	virt에서 자동 결정	virt에서 자동 결정
`list_lru_walk_one()`	순회	명시적 memcg	명시적 nid
`list_lru_walk_node()`	노드 전체 순회	모든 memcg 순회	명시적 nid

LRU Walk 콜백 반환값 동작

반환값	동작	잠금 상태	재시도
`LRU_REMOVED`	아이템 제거, 다음으로 이동	유지	아님
`LRU_REMOVED_RETRY`	아이템 제거, 처음부터 다시	해제 후 재획득	예
`LRU_ROTATE`	리스트 끝으로 이동	유지	아님
`LRU_SKIP`	건너뜀	유지	아님
`LRU_RETRY`	처음부터 다시	해제 후 재획득	예
`LRU_STOP`	순회 중지	유지	아님

memcg 처리 방식 비교

조건	동작
`memcg_aware = true`	Xarray에 memcg별 list_lru_memcg 할당
`memcg_aware = false`	루트 memcg의 list_lru_node.lru만 사용
memcg reparenting	부모 memcg의 LRU로 아이템 이동, src는 `LONG_MIN`으로 표시
memcg 해제	RCU를 통해 list_lru_memcg 안전하게 해제

List LRU와 page reclaim LRU 비교

구분	관리 대상	대표 경로	회수 단위	관찰 지표
List LRU	dentry, inode, shmem 같은 커널 오브젝트	`shrink_slab()` → `list_lru_shrink_walk()`	오브젝트 개수	`list_lru_count_one()`, `list_lru_count_node()`
page reclaim LRU	anon/file 페이지	`try_to_free_pages()` → `shrink_node()` → `shrink_lruvec()`	페이지 프레임	`pgscan`, `pgsteal`, `allocstall`, `kswapd`
연결점	shrinker가 drain할 대상을 제공	`list_lru_walk_node()`가 콜백 기반 순회	memcg/nid 단위	`cat /proc/pressure/memory`, `swapon --show`

---

관련 문서

메모리 관리 개요

SLUB 할당자

Shrinker

VMA / mmap

페이지 회수

Memory Cgroup