LRU Cache

LRU 개념

LRU(Least Recently Used)는 캐시 교체 알고리즘으로, 가장 오랫동안 사용되지 않은 항목을 우선적으로 제거합니다. 리눅스 커널은 제한된 메모리에서 최대한 많은 데이터를 캐싱하기 위해 LRU를 광범위하게 사용합니다.

LRU 존 분류

커널 페이지 캐시는 LRU를 활성(Active)과 비활성(Inactive) 두 개의 리스트로 분리하여 관리합니다:

list_lru API

list_lru는 커널 3.12에서 도입된 범용 LRU 리스트 관리 API로, inode 캐시와 dentry 캐시 등에서 사용됩니다. NUMA 인식 및 메모리 cgroup 지원을 제공합니다.

핵심 구조체

// include/linux/list_lru.h
struct list_lru_node {
    spinlock_t      lock;
    struct list_lru_one    lru;
    long            nr_items;
} ____cacheline_aligned_in_smp;

struct list_lru {
    struct list_lru_node   *node;
    struct list_head       list;
};

초기화 및 해제

// LRU 리스트 초기화
int list_lru_init(struct list_lru *lru);
int list_lru_init_memcg(struct list_lru *lru, struct shrinker *shrinker);

// LRU 리스트 해제
void list_lru_destroy(struct list_lru *lru);

기본 연산

// 항목 추가 (리스트 끝에 추가)
bool list_lru_add(struct list_lru *lru, struct list_head *item);

// 항목 제거
bool list_lru_del(struct list_lru *lru, struct list_head *item);

// 항목 수 조회
unsigned long list_lru_count_node(struct list_lru *lru, int nid);
unsigned long list_lru_count_one(struct list_lru *lru, int nid,
                                struct mem_cgroup *memcg);

순회 및 회수

// 순회 콜백 반환값
enum lru_status {
    LRU_REMOVED,        // 항목 제거됨
    LRU_REMOVED_RETRY,  // 항목 제거됨, 다시 순회
    LRU_ROTATE,         // 항목을 리스트 끝으로 이동
    LRU_SKIP,           // 항목 유지, 다음으로
    LRU_RETRY,          // 락 재획득 필요
};

typedef enum lru_status (*list_lru_walk_cb)(
    struct list_head *item,
    struct list_lru_one *list,
    spinlock_t *lock,
    void *cb_arg
);

// LRU 리스트 순회
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
);

Shrinker 인터페이스

Shrinker는 메모리 부족 시 커널이 자동으로 캐시를 회수하도록 하는 콜백 메커니즘입니다. 각 서브시스템(VFS, slab 등)은 자신의 shrinker를 등록하여 메모리 압박 시 협력합니다.

Shrinker 구조체

// include/linux/shrinker.h
struct shrinker {
    unsigned long (*count_objects)(struct shrinker *,
                                     struct shrink_control *);
    unsigned long (*scan_objects)(struct shrinker *,
                                   struct shrink_control *);

    long batch;          // 한 번에 회수할 최대 항목 수
    int seeks;           // 회수 비용 (DEFAULT_SEEKS = 2)
    unsigned flags;

    struct list_head list;
    int id;
};

struct shrink_control {
    gfp_t gfp_mask;
    int nid;                    // NUMA 노드 ID
    unsigned long nr_to_scan;  // 스캔할 항목 수
    unsigned long nr_scanned;  // 실제 스캔된 항목 수
    struct mem_cgroup *memcg;
};

Shrinker 등록

// Shrinker 등록
int register_shrinker(struct shrinker *shrinker, const char *fmt, ...);

// Shrinker 해제
void unregister_shrinker(struct shrinker *shrinker);

Shrinker 구현 예제

// fs/dcache.c - dentry 캐시 shrinker
static unsigned long dcache_lru_count(
    struct shrinker *shrink,
    struct shrink_control *sc)
{
    return list_lru_shrink_count(&dentry_cache, sc);
}

static unsigned long dcache_lru_scan(
    struct shrinker *shrink,
    struct shrink_control *sc)
{
    return list_lru_shrink_walk(&dentry_cache, sc,
                               dentry_lru_isolate, NULL);
}

static struct shrinker dcache_shrinker = {
    .count_objects = dcache_lru_count,
    .scan_objects = dcache_lru_scan,
    .seeks = DEFAULT_SEEKS,
};

커널 사용 사례

Dentry 캐시

Dentry 캐시는 파일 경로 조회를 가속화하는 핵심 구조입니다. /usr/bin/ls 같은 경로를 매번 디스크에서 조회하지 않고 메모리에 캐싱합니다.

// fs/dcache.c
static struct list_lru dentry_cache;

void d_lru_add(struct dentry *dentry)
{
    if (list_lru_add(&dentry_cache, &dentry->d_lru))
        this_cpu_inc(nr_dentry_unused);
}

void d_lru_del(struct dentry *dentry)
{
    if (list_lru_del(&dentry_cache, &dentry->d_lru))
        this_cpu_dec(nr_dentry_unused);
}

Inode 캐시

Inode 캐시는 파일의 메타데이터(크기, 권한, 타임스탬프 등)를 메모리에 유지합니다.

// fs/inode.c
static struct list_lru inode_lru;

static enum lru_status inode_lru_isolate(
    struct list_head *item,
    struct list_lru_one *lru,
    spinlock_t *lru_lock,
    void *arg)
{
    struct inode *inode = container_of(item, struct inode, i_lru);

    if (atomic_read(&inode->i_count))
        return LRU_SKIP;  // 사용 중인 inode는 유지

    if (inode->i_state & (I_REFERENCED | I_DIRTY))
        return LRU_ROTATE;  // 최근 참조됨, 리스트 끝으로

    // inode 회수
    list_lru_isolate(lru, &inode->i_lru);
    return LRU_REMOVED;
}

# Dentry 캐시 상태
cat /proc/sys/fs/dentry-state
# nr_dentry nr_unused age_limit want_pages

# Inode 캐시 상태
cat /proc/sys/fs/inode-state
# nr_inodes nr_free_inodes preshrink

# 전체 메모리 캐시
grep -E '(Cached|Buffers|Slab)' /proc/meminfo

성능 특성

LRU 연산 성능

캐시 히트율 측정

# dentry 캐시 히트율 추적 (bpftrace 필요)
sudo bpftrace -e 'kprobe:d_lookup { @lookups++; }
                 kretprobe:d_lookup /retval != 0/ { @hits++; }
                 interval:s:5 {
                   printf("Hit rate: %.2f%%\n",
                          (@hits * 100.0) / @lookups);
                   clear(@lookups); clear(@hits);
                 }'

메모리 압박 시 동작

메모리 부족 시 커널은 다음 순서로 회수를 시도합니다:

1. Inactive LRU 페이지 회수 (clean 페이지 우선)
2. Active LRU를 Inactive로 이동
3. Slab 캐시 회수 (dentry, inode 등)
4. Dirty 페이지 디스크에 기록 후 회수
5. Swap 활용 (익명 페이지)

벤치마크 결과

측정 환경: Intel Xeon E5-2680 v4 (2.4GHz), 64GB RAM, NVMe SSD, Linux 6.1

Hands-on: 커스텀 LRU 캐시

list_lru를 사용하여 최근 조회된 정수를 캐싱하는 간단한 커널 모듈을 작성합니다.

simple_lru.c

// simple_lru.c - LRU 캐시 예제
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/slab.h>
#include <linux/list_lru.h>
#include <linux/shrinker.h>
#include <linux/proc_fs.h>

#define MAX_CACHE_ITEMS 100

struct cache_item {
    int value;
    struct list_head lru;
};

static struct list_lru my_lru;
static struct shrinker *my_shrinker;
static struct kmem_cache *item_cache;

// Shrinker count 콜백
static unsigned long my_count_objects(
    struct shrinker *shrink,
    struct shrink_control *sc)
{
    return list_lru_count_node(&my_lru, sc->nid);
}

// LRU 순회 콜백
static enum lru_status item_lru_isolate(
    struct list_head *item,
    struct list_lru_one *list,
    spinlock_t *lock,
    void *arg)
{
    struct cache_item *ci = container_of(item, struct cache_item, lru);

    // 리스트에서 제거
    list_lru_isolate(list, item);

    // spinlock 해제 후 해제 (LRU_REMOVED_RETRY)
    spin_unlock(lock);
    kmem_cache_free(item_cache, ci);
    spin_lock(lock);

    return LRU_REMOVED_RETRY;
}

// Shrinker scan 콜백
static unsigned long my_scan_objects(
    struct shrinker *shrink,
    struct shrink_control *sc)
{
    return list_lru_shrink_walk(&my_lru, sc,
                               item_lru_isolate, NULL);
}

// 캐시에 값 추가
static void cache_add(int value)
{
    struct cache_item *ci;

    ci = kmem_cache_alloc(item_cache, GFP_KERNEL);
    if (!ci)
        return;

    ci->value = value;
    INIT_LIST_HEAD(&ci->lru);

    // LRU에 추가
    list_lru_add(&my_lru, &ci->lru);

    pr_info("Added %d to cache (count=%lu)\n",
            value, list_lru_count_node(&my_lru, 0));
}

// /proc/simple_lru 파일 읽기
static ssize_t simple_lru_read(
    struct file *file,
    char __user *buf,
    size_t count,
    loff_t *ppos)
{
    char kbuf[64];
    int len;

    if (*ppos > 0)
        return 0;

    len = snprintf(kbuf, sizeof(kbuf), "Cache items: %lu\n",
                    list_lru_count_node(&my_lru, 0));

    if (copy_to_user(buf, kbuf, len))
        return -EFAULT;

    *ppos = len;
    return len;
}

// /proc/simple_lru 파일 쓰기
static ssize_t simple_lru_write(
    struct file *file,
    const char __user *buf,
    size_t count,
    loff_t *ppos)
{
    char kbuf[32];
    int value;

    if (count >= sizeof(kbuf))
        return -EINVAL;

    if (copy_from_user(kbuf, buf, count))
        return -EFAULT;

    kbuf[count] = '\0';

    if (kstrtoint(kbuf, 10, &value))
        return -EINVAL;

    cache_add(value);

    return count;
}

static const struct proc_ops simple_lru_ops = {
    .proc_read = simple_lru_read,
    .proc_write = simple_lru_write,
};

static int __init simple_lru_init(void)
{
    struct shrinker s = {
        .count_objects = my_count_objects,
        .scan_objects = my_scan_objects,
        .seeks = DEFAULT_SEEKS,
    };
    int i;

    // Slab 캐시 생성
    item_cache = kmem_cache_create("simple_lru_cache",
                                     sizeof(struct cache_item),
                                     0, 0, NULL);
    if (!item_cache)
        return -ENOMEM;

    // LRU 리스트 초기화
    if (list_lru_init(&my_lru)) {
        kmem_cache_destroy(item_cache);
        return -ENOMEM;
    }

    // Shrinker 등록
    my_shrinker = shrinker_alloc(0, "simple_lru");
    if (!my_shrinker) {
        list_lru_destroy(&my_lru);
        kmem_cache_destroy(item_cache);
        return -ENOMEM;
    }

    my_shrinker->count_objects = my_count_objects;
    my_shrinker->scan_objects = my_scan_objects;
    my_shrinker->seeks = DEFAULT_SEEKS;
    shrinker_register(my_shrinker);

    // /proc 파일 생성
    proc_create("simple_lru", 0666, NULL, &simple_lru_ops);

    // 초기 데이터 추가
    for (i = 1; i <= 10; i++)
        cache_add(i * 100);

    pr_info("simple_lru module loaded\n");
    return 0;
}

static void __exit simple_lru_exit(void)
{
    remove_proc_entry("simple_lru", NULL);
    shrinker_free(my_shrinker);
    list_lru_destroy(&my_lru);
    kmem_cache_destroy(item_cache);

    pr_info("simple_lru module unloaded\n");
}

module_init(simple_lru_init);
module_exit(simple_lru_exit);

MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("Simple LRU cache example");
MODULE_AUTHOR("MINZKN");

Makefile

obj-m += simple_lru.o

KDIR := /lib/modules/$(shell uname -r)/build
PWD := $(shell pwd)

all:
	$(MAKE) -C $(KDIR) M=$(PWD) modules

clean:
	$(MAKE) -C $(KDIR) M=$(PWD) clean

테스트

# 빌드
make

# 모듈 로드
sudo insmod simple_lru.ko

# 캐시 항목 수 확인
cat /proc/simple_lru
# Cache items: 10

# 새 값 추가
echo "999" | sudo tee /proc/simple_lru
cat /proc/simple_lru
# Cache items: 11

# 메모리 압박 시뮬레이션 (실제로는 메모리 부족 시 자동 호출)
# Shrinker가 오래된 항목을 회수합니다

# 커널 로그 확인
dmesg | tail -20

# 모듈 언로드
sudo rmmod simple_lru

LRU 운영 플레이북

LRU 기반 캐시는 "정책은 맞지만 락/회수 타이밍이 틀려서" 실패하는 경우가 많습니다. 삽입·접근·회수 세 경로를 분리해 검증하세요.

# 캐시/회수 동작 관측
dmesg | grep -Ei "lru|shrink|reclaim" | tail -n 100
cat /proc/meminfo | grep -E "Cached|Slab|SReclaimable"

참고 자료

• include/linux/list_lru.h - list_lru API 정의
• mm/list_lru.c - list_lru 구현
• include/linux/shrinker.h - Shrinker 인터페이스
• mm/vmscan.c - 페이지 회수 메인 로직
• fs/dcache.c - Dentry 캐시 LRU
• fs/inode.c - Inode 캐시 LRU
• Unevictable LRU Infrastructure
• Per-superblock LRU lists - LWN 아티클