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 지원을 제공합니다.

핵심 구조체(Struct)

// 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를 사용하여 최근 조회된 정수를 캐싱하는 간단한 커널 모듈(Kernel Module)을 작성합니다.

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

lruvec: 페이지 LRU 벡터

커널 내부에서 페이지 프레임(Page Frame)의 LRU 관리는 lruvec 구조체를 통해 이루어집니다. 각 메모리 노드(NUMA node)와 메모리 cgroup마다 독립적인 lruvec가 존재하며, 5개의 LRU 리스트를 유지합니다.

lruvec 구조체

// include/linux/mmzone.h
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];
    /* per-lruvec lru_lock for memcg */
    spinlock_t              lru_lock;
    unsigned long           anon_cost;
    unsigned long           file_cost;
    /* Eviction counters for reclaim decisions */
    atomic_long_t           nonresident_age;
    unsigned long           refaults[ANON_AND_FILE];
    unsigned long           flags;
#ifdef CONFIG_LRU_GEN
    struct lru_gen_folio    lrugen;
    struct lru_gen_mm_state mm_state;
#endif
};

Folio 기반 LRU

Linux 5.16부터 struct page 대신 struct folio를 사용하는 LRU 관리가 도입되었습니다. Folio는 단일 또는 복합(compound) 페이지를 추상화하며, LRU 리스트 조작 시 tail 페이지를 별도로 처리할 필요를 제거합니다.

// include/linux/mm_inline.h

/* folio를 적절한 LRU 리스트에 추가 */
static inline void lruvec_add_folio(
    struct lruvec *lruvec,
    struct folio *folio)
{
    enum lru_list lru = folio_lru_list(folio);

    update_lru_size(lruvec, lru, folio_zonenum(folio),
                    folio_nr_pages(folio));
    if (lru != LRU_UNEVICTABLE)
        list_add(&folio->lru, &lruvec->lists[lru]);
}

/* folio의 LRU 리스트 결정 */
static inline enum lru_list folio_lru_list(
    struct folio *folio)
{
    if (folio_test_unevictable(folio))
        return LRU_UNEVICTABLE;
    if (folio_test_active(folio)) {
        if (folio_is_file_lru(folio))
            return LRU_ACTIVE_FILE;
        return LRU_ACTIVE_ANON;
    }
    if (folio_is_file_lru(folio))
        return LRU_INACTIVE_FILE;
    return LRU_INACTIVE_ANON;
}

페이지 플래그와 LRU 상태

각 페이지(folio)의 LRU 상태는 페이지 플래그 비트로 추적됩니다. 주요 플래그와 상태 전이를 이해하면 페이지 회수 동작을 정확히 파악할 수 있습니다.

// mm/swap.c -- folio_mark_accessed() 핵심 로직
void folio_mark_accessed(struct folio *folio)
{
    if (!folio_test_referenced(folio)) {
        /* 첫 번째 참조: referenced 플래그만 설정 */
        folio_set_referenced(folio);
    } else if (!folio_test_active(folio)) {
        /* 두 번째 참조: Inactive → Active 승격 */
        folio_activate(folio);
        folio_clear_referenced(folio);
        workingset_activation(folio);
    }
    /* Active + Referenced: 이미 Hot, 아무것도 하지 않음 */
}

Multi-Gen LRU (MGLRU)

Multi-Gen LRU는 Linux 6.1에서 도입된 차세대 페이지 회수 프레임워크입니다. 기존의 Active/Inactive 2-리스트 LRU를 여러 세대(generation)로 확장하여, 페이지 접근 패턴을 더 정밀하게 추적하고 회수 정확도를 크게 향상시킵니다.

세대 기반 에이징

MGLRU는 페이지를 여러 세대(generation)로 분류합니다. 가장 최근 세대(youngest)의 페이지가 가장 보호되고, 가장 오래된 세대(oldest)의 페이지가 우선 회수됩니다.

MGLRU 핵심 구조체

// include/linux/mmzone.h
#define MIN_NR_GENS     2     /* 최소 세대 수 */
#define MAX_NR_GENS     4     /* 최대 세대 수 (기본값) */

struct lru_gen_folio {
    /* youngest 세대의 시퀀스 번호 */
    unsigned long           max_seq;
    /* oldest 세대의 시퀀스 번호 */
    unsigned long           min_seq[ANON_AND_FILE];
    /* 세대별 페이지 수 */
    unsigned long           nr_pages[MAX_NR_GENS][ANON_AND_FILE]
                                                   [MAX_NR_ZONES];
    /* 세대별 LRU 리스트 (folios) */
    struct list_head        folios[MAX_NR_GENS][ANON_AND_FILE]
                                                  [MAX_NR_ZONES];
    /* 에이징을 위한 블룸 필터 */
    unsigned long           *filters[NR_BLOOM_FILTERS];
    /* 타임스탬프 (에이징 속도 제어) */
    unsigned long           timestamps[MAX_NR_GENS];
    /* 활성화 여부 */
    bool                    enabled;
};

에이징 메커니즘

MGLRU의 에이징은 lru_gen_aging()에서 수행됩니다. 새로운 세대를 생성하고(max_seq 증가), 가장 오래된 세대를 회수 대상으로 만듭니다. 이 과정에서 페이지 테이블(Page Table) 워크를 통해 PTE accessed 비트를 효율적으로 수집합니다.

// mm/vmscan.c -- MGLRU 에이징 핵심 흐름 (간략화)
static void inc_max_seq(struct lruvec *lruvec,
                        unsigned long max_seq,
                        bool can_swap)
{
    int type, zone;
    int prev = lru_gen_from_seq(max_seq - 1);
    int next = lru_gen_from_seq(max_seq);

    /* oldest 세대가 비어있지 않으면 회수 먼저 진행 */
    VM_WARN_ON_ONCE(!seq_is_valid(lruvec));

    /* 각 타입(anon/file)과 존에 대해 세대 교체 */
    for (type = 0; type < ANON_AND_FILE; type++) {
        for (zone = 0; zone < MAX_NR_ZONES; zone++) {
            /* 현재 세대 리스트가 비어있어야 함 */
            if (!list_empty(
                &lruvec->lrugen.folios[next][type][zone]))
                INIT_LIST_HEAD(
                    &lruvec->lrugen.folios[next][type][zone]);
        }
    }

    /* 시퀀스 번호 증가 → 새로운 youngest 세대 생성 */
    WRITE_ONCE(lruvec->lrugen.max_seq, max_seq + 1);
}

MGLRU sysfs 인터페이스

# MGLRU 활성화 상태 확인
cat /sys/kernel/mm/lru_gen/enabled
# 0x0007 (비트 마스크: core=1, mm_walk=2, nonleaf_young=4)

# MGLRU 세대 정보 확인
cat /sys/kernel/debug/lru_gen
# memcg  id  node  gen  anon  file
#   0     0    0    3   1234  5678

# MGLRU 활성화/비활성화
echo 7 | sudo tee /sys/kernel/mm/lru_gen/enabled   # 모든 기능 활성화
echo 0 | sudo tee /sys/kernel/mm/lru_gen/enabled   # 비활성화 (기존 LRU 사용)

# 최소 TTL 설정 (밀리초, 세대 최소 수명)
echo 1000 | sudo tee /sys/kernel/mm/lru_gen/min_ttl_ms

튜닝 파라미터

LRU 캐시 동작은 여러 sysctl 파라미터로 미세 조정할 수 있습니다. 워크로드에 따라 적절한 값을 설정하면 시스템 성능을 크게 개선할 수 있습니다.

모니터링 및 디버깅

# 페이지 캐시 현황 상세 조회
grep -E 'Active|Inactive|Unevictable|Slab|SReclaimable' /proc/meminfo
# Active(anon):    1234 kB
# Inactive(anon):  5678 kB
# Active(file):    9012 kB
# Inactive(file):  3456 kB
# Unevictable:     100 kB
# Slab:            2048 kB
# SReclaimable:    1500 kB

# NUMA 노드별 LRU 통계
for node in /sys/devices/system/node/node*/meminfo; do
    echo "=== $node ==="
    grep -E 'Active|Inactive' "$node"
done

# vmstat으로 실시간 회수 모니터링
vmstat 1
# si/so: swap in/out, bi/bo: block in/out

# Shrinker별 통계 확인 (Linux 6.0+)
cat /sys/kernel/debug/shrinker/*/count 2>/dev/null

# perf로 회수 경로 프로파일링
sudo perf record -g -e 'vmscan:mm_vmscan_lru_shrink_inactive' -- sleep 30
sudo perf report

워킹셋 감지와 Refault Distance

커널은 회수된 페이지가 다시 필요해지는 "refault" 현상을 추적하여 회수 정책을 동적으로 조정합니다. Refault distance가 메모리 크기보다 작으면 해당 페이지는 워킹셋에 속하므로 즉시 Active 리스트로 승격시킵니다.

// mm/workingset.c -- refault distance 기반 워킹셋 감지
void workingset_refault(struct folio *folio,
                        void *shadow)
{
    unsigned long refault_distance;
    unsigned long active_file;
    struct lruvec *lruvec;
    bool workingset;

    /* shadow entry에서 eviction 시점 정보 복원 */
    unpack_shadow(shadow, &refault_distance, &workingset);

    lruvec = folio_lruvec(folio);
    active_file = lruvec_page_state(lruvec, NR_ACTIVE_FILE);

    /* refault distance가 active 크기보다 작으면
       이 페이지는 워킹셋에 속함 → 즉시 Active로 승격 */
    if (refault_distance <= active_file) {
        folio_set_active(folio);
        folio_set_workingset(folio);
        atomic_long_inc(&lruvec->nonresident_age);
    }
}

메모리 Cgroup과 LRU

컨테이너 환경에서 각 cgroup은 독립적인 LRU 리스트(lruvec)를 갖습니다. 이를 통해 컨테이너별 메모리 격리와 공정한 회수가 가능합니다.

// include/linux/memcontrol.h
struct mem_cgroup_per_node {
    struct lruvec       lruvec;       /* cgroup별 LRU 벡터 */
    unsigned long       lru_zone_size[MAX_NR_ZONES][NR_LRU_LISTS];
};

/* folio가 속한 cgroup의 lruvec 가져오기 */
static inline struct lruvec *folio_lruvec(
    struct folio *folio)
{
    struct mem_cgroup *memcg = folio_memcg(folio);
    struct pglist_data *pgdat = folio_pgdat(folio);

    if (memcg)
        return &memcg->nodeinfo[pgdat->node_id]->lruvec;
    return &pgdat->__lruvec;  /* root cgroup */
}

# cgroup별 메모리/LRU 통계 확인
cat /sys/fs/cgroup/my-container/memory.stat
# anon 12345678
# file 98765432
# inactive_anon 1234
# active_anon 5678
# inactive_file 9012
# active_file 3456
# unevictable 100

# cgroup별 swappiness 설정 (cgroup v2)
echo 30 | sudo tee /sys/fs/cgroup/my-container/memory.swappiness 2>/dev/null

# 특정 cgroup의 회수 압박 강제 트리거
echo 1 | sudo tee /sys/fs/cgroup/my-container/memory.reclaim 2>/dev/null

LRU 알고리즘 비교

리눅스 커널에서 사용된 다양한 LRU 변형 알고리즘을 비교합니다. 각 알고리즘은 특정 문제를 해결하기 위해 도입되었습니다.

LRU 운영 플레이북

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

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

list_lru 내부 구조

list_lru API의 외부 인터페이스 아래에는 NUMA 토폴로지(Topology)와 memcg를 인식하는 정교한 내부 구조가 숨어 있습니다. 각 구조체의 역할과 배치를 정확히 이해해야 캐시라인 경합(Contention)이나 false sharing 문제를 피할 수 있습니다.

list_lru_one 구조체

// include/linux/list_lru.h
struct list_lru_one {
    struct list_head    list;       // LRU 이중 연결 리스트
    long                nr_items;   // 리스트 내 항목 수
};

list_lru_node 구조체

struct list_lru_node {
    spinlock_t              lock;   // 노드별 독립 락
    struct list_lru_one     lru;    // 기본(root memcg) LRU
    long                    nr_items;
} ____cacheline_aligned_in_smp;          // 캐시라인 정렬로 false sharing 방지

memcg 인식 list_lru

// memcg 인식 확장 구조
struct list_lru_memcg {
    struct rcu_head         rcu;
    struct list_lru_one     *mlrus[];  // memcg ID 인덱스 배열
};

struct list_lru {
    struct list_lru_node   *node;           // node[0..MAX_NUMNODES]
    struct list_head       list;            // 전역 list_lru 등록 체인
    int                    shrinker_id;     // 연결된 shrinker ID
    bool                   memcg_aware;     // memcg 분리 여부
    struct list_lru_memcg __rcu *memcg_lrus; // RCU 보호 memcg 배열
};

할당/등록 경로

// mm/list_lru.c - 초기화 핵심 경로
int __list_lru_init(struct list_lru *lru, bool memcg_aware,
                    struct lock_class_key *key,
                    struct shrinker *shrinker)
{
    // 1. NUMA 노드 수만큼 list_lru_node 배열 할당
    lru->node = kcalloc(nr_node_ids, sizeof(*lru->node), GFP_KERNEL);

    // 2. 각 노드 초기화
    for_each_node(i) {
        spin_lock_init(&lru->node[i].lock);
        INIT_LIST_HEAD(&lru->node[i].lru.list);
        lru->node[i].nr_items = 0;
    }

    // 3. memcg 인식이면 memcg_lrus 할당
    if (memcg_aware)
        memcg_init_list_lru(lru, memcg_aware);

    // 4. 전역 list_lrus 리스트에 등록 (shrinker 연동)
    list_add_tail(&lru->list, &list_lrus);
}

memcg 인식 LRU

CONFIG_MEMCG_KMEM 활성화 시 커널 슬랩 객체(dentry, inode 등)도 memcg별로 독립된 LRU 리스트에서 관리됩니다. 이를 통해 컨테이너 환경에서 메모리 제한이 정확히 동작하고, 한 cgroup의 캐시 폭증이 다른 cgroup에 영향을 주지 않습니다.

memcg LRU 동작 경로

// list_lru_add 의 memcg 경로 (mm/list_lru.c)
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;

    spin_lock(&nlru->lock);
    if (list_empty(item)) {
        // memcg별 list_lru_one 찾기
        l = list_lru_from_memcg_idx(lru, nid, memcg_kmem_id(memcg));
        list_add_tail(item, &l->list);
        l->nr_items++;
        nlru->nr_items++;
        set_shrinker_bit(memcg, nid, lru->shrinker_id);
        spin_unlock(&nlru->lock);
        return true;
    }
    spin_unlock(&nlru->lock);
    return false;
}

memcg 마이그레이션 시 LRU 이동

// cgroup 마이그레이션 시 LRU 재배치
void memcg_reparent_list_lrus(struct mem_cgroup *memcg,
                              struct mem_cgroup *parent)
{
    // 모든 등록된 list_lru에 대해
    list_for_each_entry(lru, &list_lrus, list) {
        for_each_node(nid) {
            // 자식 memcg의 리스트를 부모로 병합
            src = list_lru_from_memcg_idx(lru, nid, memcg_kmem_id(memcg));
            dst = list_lru_from_memcg_idx(lru, nid, memcg_kmem_id(parent));
            list_splice_init(&src->list, &dst->list);
            dst->nr_items += src->nr_items;
        }
    }
}

shrinker의 memcg별 스캔

워킹셋 감지 (Shadow Entries)

커널은 회수된 페이지의 "흔적"을 shadow entry로 남겨, 다시 접근될 때 즉시 Active 리스트로 승격시킬지 결정합니다. 이 메커니즘은 mm/workingset.c에 구현되어 있으며, thrashing을 감지하는 핵심 수단입니다.

shadow entry 개념

페이지가 회수될 때 XArray(페이지 캐시 인덱스)에서 실제 folio 포인터 대신 shadow entry를 저장합니다. shadow entry에는 회수 시점의 eviction counter 값이 인코딩되어 있어, 나중에 refault 발생 시 "얼마나 빨리 다시 접근되었는지"를 계산할 수 있습니다.

// include/linux/swap.h - shadow entry 인코딩
static inline void *pack_shadow(int memcgid,
    pg_data_t *pgdat, unsigned long eviction, bool workingset)
{
    eviction >>= bucket_order;
    eviction &= EVICTION_MASK;
    eviction = (eviction << MEMCGID_BITS) | memcgid;
    eviction = (eviction << NODES_SHIFT) | pgdat_to_nid(pgdat);
    eviction = (eviction << 1) | workingset;
    return xa_mk_value(eviction);
}

// shadow entry에 저장되는 정보:
// [eviction_counter | memcg_id | node_id | workingset_bit]

refault distance 계산

// mm/workingset.c
void workingset_refault(struct folio *folio, void *shadow)
{
    int memcgid;
    unsigned long eviction, refault_distance;
    struct lruvec *lruvec;

    // 1. shadow entry에서 eviction 시점 추출
    unpack_shadow(shadow, &memcgid, &pgdat, &eviction, &workingset);

    // 2. 현재 nonresident_age와의 차이 = refault distance
    refault_distance = atomic_long_read(&lruvec->nonresident_age)
                     - eviction;

    // 3. refault distance < inactive 리스트 크기이면 Active 승격
    if (refault_distance <= lruvec_lru_size(lruvec, LRU_INACTIVE_FILE, MAX_NR_ZONES)) {
        folio_set_active(folio);
        folio_set_workingset(folio);
        // Active 리스트에 바로 추가 → "second chance" 없이 즉시 보호
    }
}

thrashing 모니터링

# /proc/vmstat에서 워킹셋 관련 통계
grep workingset /proc/vmstat
# workingset_nodes        12345   ← shadow entry 수
# workingset_refault_anon  0      ← 익명 페이지 refault
# workingset_refault_file  5678   ← 파일 페이지 refault
# workingset_activate_anon 0      ← refault 후 Active 승격
# workingset_activate_file 4321   ← refault 후 Active 승격
# workingset_restore_anon  0      ← 복원된 워킹셋
# workingset_restore_file  2100   ← 복원된 워킹셋
# workingset_nodereclaim   100    ← shadow node 회수

# thrashing 비율 계산
# refault 비율 = workingset_refault_file / (pgpgout + pswpout)
# 비율이 높으면 → 메모리 부족으로 워킹셋이 반복 evict

MGLRU 내부 메커니즘

Multi-Gen LRU(MGLRU)는 기존 Active/Inactive 2단계를 다세대(multi-generation) 구조로 대체하여 더 정밀한 에이징과 회수를 수행합니다. 핵심 구조체와 내부 알고리즘을 상세히 분석합니다.

lru_gen_folio 구조체

// include/linux/mmzone.h
struct lru_gen_folio {
    unsigned long       max_seq;        // 최신 세대 번호
    unsigned long       min_seq[ANON_AND_FILE]; // 최고령 세대 (anon/file 별도)
    unsigned long       timestamps[MAX_NR_GENS]; // 세대별 생성 시각
    struct list_head    folios[MAX_NR_GENS][ANON_AND_FILE][MAX_NR_ZONES];
    unsigned long       sizes[MAX_NR_GENS][ANON_AND_FILE][MAX_NR_ZONES];
    unsigned long       avg_refaulted[ANON_AND_FILE][MAX_NR_TIERS];
    unsigned long       avg_total[ANON_AND_FILE][MAX_NR_TIERS];
    atomic_long_t       evicted[ANON_AND_FILE][MAX_NR_TIERS];
    atomic_long_t       refaulted[ANON_AND_FILE][MAX_NR_TIERS];
    bool                enabled;
};

에이징 (Aging): PTE Young Bit 검사

// mm/vmscan.c - 에이징 핵심 경로
static void inc_max_seq(struct lruvec *lruvec, unsigned long max_seq)
{
    // 1. 모든 mm_struct을 순회하며 PTE young bit 검사
    iterate_mm_list(lruvec, max_seq, &mm_list);

    // 2. young bit 설정된 folio → 최신 세대(max_seq+1)로 이동
    // 3. young bit 없는 folio → 현재 세대 유지 (나이 들어감)

    // 4. max_seq 증가
    WRITE_ONCE(lruvec->lrugen.max_seq, max_seq + 1);
}

Bloom Filter 최적화

MGLRU는 page table walk 비용을 줄이기 위해 bloom filter를 사용합니다. 이미 스캔한 PTE를 기록하여, 동일 세대 내 중복 워크를 방지합니다.

tier 시스템: 파일 페이지(File-backed Page) 다중 등급

// 파일 페이지의 tier 계산 (접근 횟수 기반)
// tier 0: 한 번 접근 (가장 차가움)
// tier 1: 두 번 접근
// tier 2: 세 번 이상 접근 (가장 뜨거움)
// → avg_refaulted[tier] / avg_total[tier] 비율로 회수 여부 결정
// refault 비율이 높은 tier는 회수 우선순위 낮음 (보호)

dentry 캐시 LRU

디렉터리 엔트리(dentry) 캐시는 파일 경로 탐색 성능의 핵심입니다. 참조 카운트가 0이 된 dentry는 즉시 해제되지 않고 LRU 리스트에 보관되어 재사용 가능성을 유지합니다.

d_lru 필드와 추가/제거

// include/linux/dcache.h
struct dentry {
    ...
    struct list_head    d_lru;      // LRU 리스트 엔트리
    struct list_head    d_child;    // 부모의 자식 리스트
    unsigned int        d_flags;    // DCACHE_LRU_LIST 등
    ...
};

// fs/dcache.c
static void d_lru_add(struct dentry *dentry)
{
    d_set_flag(dentry, DCACHE_LRU_LIST);
    this_cpu_inc(nr_dentry_unused);
    if (d_is_negative(dentry))
        this_cpu_inc(nr_dentry_negative);
    list_lru_add_obj(&dentry->d_sb->s_dentry_lru, &dentry->d_lru);
}

static void d_lru_del(struct dentry *dentry)
{
    d_clear_flag(dentry, DCACHE_LRU_LIST);
    this_cpu_dec(nr_dentry_unused);
    if (d_is_negative(dentry))
        this_cpu_dec(nr_dentry_negative);
    list_lru_del_obj(&dentry->d_sb->s_dentry_lru, &dentry->d_lru);
}

음성 dentry(negative dentry)

prune_dcache_sb: 슈퍼블록별 회수

// fs/dcache.c - dentry shrinker 콜백
static enum lru_status dentry_lru_isolate(
    struct list_head *item,
    struct list_lru_one *lru,
    spinlock_t *lru_lock,
    void *arg)
{
    struct dentry *dentry = container_of(item, struct dentry, d_lru);

    // 1. 참조 카운트 > 0이면 LRU에서 제거만
    if (dentry->d_lockref.count) {
        d_lru_isolate(lru, dentry);
        return LRU_REMOVED;
    }

    // 2. 최근 참조(DCACHE_REFERENCED)면 플래그 클리어 후 재배치
    if (dentry->d_flags & DCACHE_REFERENCED) {
        dentry->d_flags &= ~DCACHE_REFERENCED;
        return LRU_ROTATE;  // second chance
    }

    // 3. 회수 대상으로 격리
    d_lru_shrink_move(lru, dentry, freeable);
    return LRU_REMOVED;
}

inode 캐시 LRU

inode 캐시는 파일 메타데이터(소유자, 권한, 크기, 블록 맵핑 등)를 메모리에 유지합니다. 마지막 참조가 해제된 inode는 LRU 리스트로 이동하여 메모리 압박 시 회수 대상이 됩니다.

i_lru 필드와 상태

// include/linux/fs.h
struct inode {
    ...
    struct list_head    i_lru;      // LRU 리스트 엔트리
    unsigned long       i_state;    // I_DIRTY, I_FREEING 등
    atomic_t            i_count;    // 참조 카운트
    ...
};

// fs/inode.c
void inode_add_lru(struct inode *inode)
{
    if (!(inode->i_state & (I_DIRTY_ALL | I_SYNC |
                I_FREEING | I_WILL_FREE))) {
        if (list_lru_add_obj(&inode->i_sb->s_inode_lru,
                            &inode->i_lru))
            this_cpu_inc(nr_unused);
    }
}

void inode_lru_list_del(struct inode *inode)
{
    if (list_lru_del_obj(&inode->i_sb->s_inode_lru,
                        &inode->i_lru))
        this_cpu_dec(nr_unused);
}

inode eviction 순서

// fs/inode.c - 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);

    // 참조 중이면 LRU에서 제거만
    if (atomic_read(&inode->i_count))
        return LRU_REMOVED;

    // dirty이면 건너뛰기 (writeback 필요)
    if (inode->i_state & I_DIRTY_ALL)
        return LRU_ROTATE;

    // I_REFERENCED 면 second chance
    if (inode->i_state & I_REFERENCED) {
        inode->i_state &= ~I_REFERENCED;
        return LRU_ROTATE;
    }

    // 회수 대상으로 격리
    return LRU_REMOVED;
}

페이지 캐시 LRU 상세

페이지 캐시(file-backed 페이지)가 LRU 리스트에 추가되는 과정은 성능을 위해 per-CPU 배치(batch) 처리로 이루어집니다. lru_pvecs 구조를 통해 spinlock 경합을 최소화하는 메커니즘을 상세히 분석합니다.

folio_add_lru: 배치 LRU 추가

// mm/swap.c
void folio_add_lru(struct folio *folio)
{
    struct folio_batch *fbatch;

    folio_get(folio);            // 참조 카운트 증가
    local_lock(&cpu_fbatches.lock);
    fbatch = this_cpu_ptr(&cpu_fbatches.lru_add);
    folio_batch_add_and_move(fbatch, folio, lru_add_fn);
    local_unlock(&cpu_fbatches.lock);
}

// per-CPU batch가 가득 차면 (PAGEVEC_SIZE=31) 실제 LRU로 flush
static void lru_add_fn(struct lruvec *lruvec,
                       struct folio *folio)
{
    int was_unevictable = folio_test_unevictable(folio);
    enum lru_list lru = folio_lru_list(folio);

    folio_set_lru(folio);
    lruvec_add_folio(lruvec, folio);
}

folio_mark_accessed → folio_activate 경로

// mm/swap.c - 접근 패턴에 따른 LRU 승격
void folio_mark_accessed(struct folio *folio)
{
    if (!folio_test_referenced(folio)) {
        // 첫 번째 접근: PG_referenced 설정
        folio_set_referenced(folio);
    } else if (!folio_test_active(folio)) {
        // 두 번째 접근: Active로 승격
        folio_activate(folio);
        folio_clear_referenced(folio);
    }
    // 이미 Active이면 → folio_set_workingset()
    if (folio_test_idle(folio))
        folio_clear_idle(folio);
}

pagevec drain: lru_add_drain_all

// mm/swap.c - drain 시점
void lru_add_drain_all(void)
{
    // 모든 online CPU에 대해 IPI 또는 work queue로 drain 요청
    __lru_add_drain_all(false);
}

// drain이 필요한 주요 호출자:
// - migrate_pages()     : 페이지 마이그레이션 전
// - compact_zone()      : compaction 전
// - shrink_active_list(): LRU scan 전
// - munlock_folio()     : unevictable → evictable 전환

커스텀 LRU 패턴

커널 서브시스템에서 list_lru를 활용한 자체 캐시를 구현할 때 반복되는 설계 패턴과 흔한 실수를 정리합니다. 참조 카운팅, RCU, Shrinker를 올바르게 조합하는 것이 핵심입니다.

기본 구현 패턴

// 커스텀 LRU 캐시 뼈대
struct my_cache_entry {
    struct list_head    lru;        // list_lru 연결
    struct rcu_head     rcu;        // RCU 해제용
    refcount_t          ref;        // 참조 카운트
    unsigned long       key;
    void                *data;
};

static struct list_lru my_lru;
static struct shrinker *my_shrinker;

// 패턴 1: 참조 해제 시 LRU 추가
void my_cache_put(struct my_cache_entry *entry)
{
    if (refcount_dec_and_test(&entry->ref))
        list_lru_add(&my_lru, &entry->lru);
}

// 패턴 2: 조회 시 LRU에서 제거
struct my_cache_entry *my_cache_get(unsigned long key)
{
    struct my_cache_entry *entry;

    rcu_read_lock();
    entry = my_lookup(key);  // RCU 보호 조회
    if (entry && refcount_inc_not_zero(&entry->ref))
        list_lru_del(&my_lru, &entry->lru);
    else
        entry = NULL;
    rcu_read_unlock();
    return entry;
}

Shrinker 연동 패턴

// Shrinker 콜백 구현
static unsigned long my_count(struct shrinker *s,
    struct shrink_control *sc)
{
    return list_lru_shrink_count(&my_lru, sc);
}

static enum lru_status my_isolate(
    struct list_head *item,
    struct list_lru_one *list,
    spinlock_t *lock, void *arg)
{
    struct my_cache_entry *e =
        container_of(item, struct my_cache_entry, lru);

    // 참조 중이면 건너뛰기
    if (refcount_read(&e->ref) > 0)
        return LRU_SKIP;

    // 인덱스에서 제거 후 RCU 해제
    my_index_remove(e);
    list_lru_isolate(list, item);
    call_rcu(&e->rcu, my_free_rcu);
    return LRU_REMOVED;
}

static unsigned long my_scan(struct shrinker *s,
    struct shrink_control *sc)
{
    return list_lru_shrink_walk(&my_lru, sc,
                                my_isolate, NULL);
}

흔한 실수와 방지책

lru_cache 모듈: 해시+LRU 이중 구조

리눅스 커널에는 list_lru 외에도 lib/lru_cache.c에 구현된 독립적인 lru_cache 모듈이 존재합니다. 이 모듈은 DRBD(Distributed Replicated Block Device)에서 활동 로그(Activity Log) 캐싱을 위해 개발되었으며, 해시 테이블(Hash Table)을 통한 O(1) 조회와 이중 연결 리스트(Doubly-Linked List)를 통한 LRU 순서 관리를 하나의 자료구조에 결합합니다.

핵심 구조체

// include/linux/lru_cache.h

/* 캐시 원소 하나를 나타내는 기본 구조체 */
struct lc_element {
    struct hlist_node   colision;    // 해시 충돌 체인
    struct list_head    list;        // LRU 리스트 또는 free 리스트
    unsigned            lc_number;   // 논리 번호 (키)
    unsigned            lc_index;    // 슬롯 인덱스 (0..nr_elements-1)
    unsigned            refcnt;      // 참조 카운트
    unsigned            lc_new_number; // 트랜잭션 중 새 번호
};

/* lru_cache 전체 컨테이너 */
struct lru_cache {
    struct list_head    in_use;      // 사용 중인 원소 LRU 리스트
    struct list_head    lru;         // 해제 가능한 원소 LRU 리스트
    struct list_head    free;        // 미사용 원소 풀
    struct list_head    to_be_changed; // 트랜잭션 변경 대기열

    size_t              element_size;  // 원소 크기 (lc_element 포함 확장 구조체)
    unsigned int        nr_elements;   // 총 원소 수
    unsigned int        used;          // 현재 사용 중인 원소 수
    unsigned long       flags;         // LC_LOCKED, LC_DIRTY 등

    struct lc_element   **lc_slot;     // 인덱스별 원소 포인터 배열
    struct hlist_head   *lc_hash;      // 해시 테이블

    unsigned int        new_number;    // 현재 트랜잭션 대상 번호

    /* 통계 카운터 */
    unsigned long       hits, misses, starving, locked, changed;

    const char          *name;         // 디버그용 이름
};

lru_cache_alloc / lru_cache_free: 생명주기

// lib/lru_cache.c

/* lru_cache 할당 및 초기화
 * e_count: 원소 수, e_size: 원소 크기 (>= sizeof(struct lc_element)),
 * e_off: lc_element의 오프셋 (확장 구조체 내)
 */
struct lru_cache *lc_create(const char *name,
    struct kmem_cache *cache,
    unsigned max_pending_changes,
    unsigned e_count, size_t e_size, size_t e_off)
{
    struct lru_cache *lc;
    unsigned i;

    // 1. lru_cache 구조체 할당
    lc = kzalloc(sizeof(*lc), GFP_KERNEL);

    // 2. 해시 테이블 할당 (e_count 크기)
    lc->lc_hash = kcalloc(e_count, sizeof(struct hlist_head),
                          GFP_KERNEL);

    // 3. 인덱스별 슬롯 배열 할당
    lc->lc_slot = kcalloc(e_count, sizeof(struct lc_element *),
                          GFP_KERNEL);

    // 4. 리스트 헤드 초기화
    INIT_LIST_HEAD(&lc->in_use);
    INIT_LIST_HEAD(&lc->lru);
    INIT_LIST_HEAD(&lc->free);
    INIT_LIST_HEAD(&lc->to_be_changed);

    // 5. 모든 원소 사전 할당 → free 리스트에 추가
    for (i = 0; i < e_count; i++) {
        void *p = kmem_cache_alloc(cache, GFP_KERNEL);
        struct lc_element *e = p + e_off;
        e->lc_index = i;
        e->lc_number = LC_FREE;   // 미할당 상태
        e->refcnt = 0;
        lc->lc_slot[i] = e;
        list_add(&e->list, &lc->free);
    }

    lc->nr_elements = e_count;
    return lc;
}

/* lru_cache 해제 */
void lc_destroy(struct lru_cache *lc)
{
    kfree(lc->lc_hash);
    kfree(lc->lc_slot);
    kfree(lc);
}

lc_get / lc_put: 원소 접근과 참조 카운팅

// lib/lru_cache.c

/* 번호(키)로 원소 조회/할당
 * 캐시 히트: 참조 카운트 증가, LRU 순서 갱신
 * 캐시 미스: LRU 리스트에서 가장 오래된 원소 교체
 * 반환: lc_element 포인터, 실패 시 NULL
 */
struct lc_element *lc_get(struct lru_cache *lc, unsigned int enr)
{
    struct lc_element *e;

    // 1. 해시 테이블에서 조회
    e = __lc_find(lc, enr, 1);
    if (e) {
        // 캐시 히트: 참조 카운트 증가
        ++e->refcnt;
        ++lc->hits;
        if (e->refcnt == 1)
            lc->used++;
        // in_use 리스트 앞쪽(MRU)으로 이동
        list_move(&e->list, &lc->in_use);
        return e;
    }

    ++lc->misses;

    // 2. 캐시 미스: free 리스트에서 먼저 확인
    if (!list_empty(&lc->free)) {
        e = list_first_entry(&lc->free,
                            struct lc_element, list);
    } else if (!list_empty(&lc->lru)) {
        // 3. free 없으면 → lru 리스트 tail(가장 오래된 원소) 교체
        e = list_entry(lc->lru.prev,
                      struct lc_element, list);
        // 이전 해시 엔트리 제거
        hlist_del(&e->colision);
    } else {
        // 4. 모든 원소가 in_use: 할당 불가
        ++lc->starving;
        return NULL;
    }

    // 5. 새 번호 할당, 해시 테이블에 삽입
    e->lc_number = enr;
    e->refcnt = 1;
    lc->used++;
    hlist_add_head(&e->colision,
                   &lc->lc_hash[lc_hash_fn(lc, enr)]);
    list_move(&e->list, &lc->in_use);
    return e;
}

/* 원소 해제: 참조 카운트 감소
 * refcnt가 0이 되면 lru 리스트로 이동 (교체 후보)
 */
unsigned int lc_put(struct lru_cache *lc,
                     struct lc_element *e)
{
    WARN_ON(!e->refcnt);
    --e->refcnt;

    if (e->refcnt == 0) {
        // lru 리스트 앞쪽(MRU)으로 이동
        list_move(&e->list, &lc->lru);
        lc->used--;
    }
    return e->refcnt;
}

lc_try_lock / lc_unlock: 동시성 제어

// include/linux/lru_cache.h

/* 캐시 잠금 (비차단, 원자적) */
static inline int lc_try_lock(struct lru_cache *lc)
{
    return !test_and_set_bit(__LC_LOCKED, &lc->flags);
}

/* 캐시 잠금 해제 */
static inline void lc_unlock(struct lru_cache *lc)
{
    clear_bit_unlock(__LC_LOCKED, &lc->flags);
}

/* 잠금 상태 확인 */
static inline int lc_is_used(struct lru_cache *lc,
                              unsigned int enr)
{
    struct lc_element *e = lc_find(lc, enr);
    return e && e->refcnt;
}

lc_find / lc_element_by_index: 조회 경로

// lib/lru_cache.c

/* 해시 테이블 기반 O(1) 조회
 * 참조 카운트를 변경하지 않음 (읽기 전용 조회) */
struct lc_element *lc_find(struct lru_cache *lc,
                           unsigned int enr)
{
    struct lc_element *e;
    struct hlist_node *n;

    hlist_for_each_entry(e, n,
        &lc->lc_hash[lc_hash_fn(lc, enr)], colision) {
        if (e->lc_number != enr)
            continue;
        return e;
    }
    return NULL;
}

/* 인덱스 직접 접근 O(1)
 * 해시를 거치지 않고 슬롯 배열로 바로 접근 */
struct lc_element *lc_element_by_index(struct lru_cache *lc,
                                       unsigned int i)
{
    BUG_ON(i >= lc->nr_elements);
    BUG_ON(lc->lc_slot[i] == NULL);
    return lc->lc_slot[i];
}

DRBD 활동 로그 캐싱

lru_cache 모듈은 DRBD에서 활동 로그(Activity Log, AL)를 관리하기 위해 개발되었습니다. DRBD는 블록 디바이스를 네트워크를 통해 미러링하는 커널 모듈로, 노드 장애 시 어떤 영역을 재동기화해야 하는지 추적하기 위해 활동 로그를 사용합니다.

활동 로그(Activity Log) 개념

// drivers/block/drbd/drbd_int.h

/* DRBD 활동 로그 확장 구조체 */
struct lc_element;

/* DRBD 리소스 구조체의 활동 로그 필드 */
struct drbd_device {
    ...
    struct lru_cache   *act_log;        // 활동 로그 LRU 캐시
    struct lru_cache   *resync_lru;     // 재동기화 LRU 캐시
    unsigned int       al_nr_extents;   // 활동 로그 익스텐트 수
    ...
};

// 활동 로그 익스텐트 크기: 4MB (기본값)
// 활동 로그 슬롯 수: 127~65534 (기본 1237)
// → 최대 약 5GB의 동시 쓰기 영역 추적 가능

DRBD 쓰기 I/O 경로와 활동 로그

// drivers/block/drbd/drbd_req.c (간략화)

/* 쓰기 요청 처리 시 활동 로그 갱신 */
static int drbd_al_begin_io(struct drbd_device *device,
                            struct drbd_interval *i)
{
    struct lru_cache *al = device->act_log;
    struct lc_element *al_ext;
    unsigned int enr;

    // 1. 쓰기 대상 섹터(Sector) → 익스텐트 번호 변환
    enr = i->sector >> (AL_EXTENT_SHIFT - 9);

    // 2. 활동 로그 잠금
    wait_event(device->al_wait, lc_try_lock(al));

    // 3. 해당 익스텐트를 활동 로그에 등록
    al_ext = lc_get(al, enr);
    if (!al_ext) {
        // 모든 슬롯이 사용 중 → 대기
        lc_unlock(al);
        return -EBUSY;
    }

    // 4. 새 익스텐트(캐시 미스)면 메타데이터 기록
    if (al_ext->lc_number != al_ext->lc_new_number) {
        // 디스크에 활동 로그 트랜잭션 기록
        drbd_al_write_transaction(device);
    }

    lc_unlock(al);
    return 0;
}

/* 쓰기 완료 시 활동 로그 해제 */
void drbd_al_complete_io(struct drbd_device *device,
                         struct drbd_interval *i)
{
    unsigned int enr = i->sector >> (AL_EXTENT_SHIFT - 9);
    struct lc_element *al_ext;

    spin_lock_irq(&device->al_lock);
    al_ext = lc_find(device->act_log, enr);
    if (al_ext) {
        lc_put(device->act_log, al_ext);
        // refcnt→0 이면 lru 리스트로 이동 (나중에 재사용/교체 가능)
    }
    spin_unlock_irq(&device->al_lock);
    wake_up(&device->al_wait);
}

DRBD 활동 로그 튜닝

# DRBD 활동 로그 익스텐트 수 설정 (기본 1237)
drbdadm disk-options --al-extents=3389 r0

# 활동 로그 통계 확인
cat /proc/drbd
# ... al: used=45 hits=12345 misses=67 starving=0 ...

# 활동 로그 크기와 복구 시간의 트레이드오프:
# - 큰 AL: 동시 쓰기 영역 증가, 포화 감소 → 복구 시간 증가
# - 작은 AL: 복구 시간 단축 → 포화 빈번, I/O 대기 증가

범용 블록 레벨 캐싱 패턴

lru_cache 모듈은 DRBD 외에도 블록 디바이스 레벨의 범용 캐싱 패턴을 구현하는 데 활용할 수 있습니다. 고정 크기 원소 풀, 해시 기반 O(1) 조회, 자동 LRU 교체를 제공하므로, I/O 경로에서 할당 실패 없이 안전한 캐싱이 가능합니다.

블록 메타데이터 캐시 구현 예제

// 블록 디바이스 메타데이터를 lru_cache로 캐싱하는 예제
#include <linux/lru_cache.h>

/* 캐시 원소: lc_element을 내장하는 확장 구조체 */
struct block_meta_entry {
    struct lc_element   lce;           // lru_cache 연결
    sector_t            start_sector;  // 시작 섹터
    unsigned int        flags;         // DIRTY, VALID 등
    u8                  metadata[512]; // 메타데이터 버퍼
};

static struct kmem_cache *meta_slab;
static struct lru_cache *meta_cache;

/* 초기화 */
static int meta_cache_init(unsigned int nr_entries)
{
    meta_slab = kmem_cache_create("block_meta",
        sizeof(struct block_meta_entry), 0, 0, NULL);
    if (!meta_slab)
        return -ENOMEM;

    meta_cache = lc_create("block_meta_cache", meta_slab,
        0,           // max_pending_changes
        nr_entries,  // 원소 수 (예: 4096)
        sizeof(struct block_meta_entry),
        offsetof(struct block_meta_entry, lce));
    if (!meta_cache) {
        kmem_cache_destroy(meta_slab);
        return -ENOMEM;
    }
    return 0;
}

/* 메타데이터 읽기: 캐시 히트 시 즉시 반환, 미스 시 디스크에서 로드 */
static struct block_meta_entry *meta_cache_read(
    unsigned int block_nr)
{
    struct lc_element *e;
    struct block_meta_entry *entry;

    if (!lc_try_lock(meta_cache))
        return NULL;   // 잠금 실패, 재시도 필요

    e = lc_get(meta_cache, block_nr);
    if (!e) {
        lc_unlock(meta_cache);
        return NULL;   // 모든 슬롯 사용 중
    }

    entry = container_of(e, struct block_meta_entry, lce);

    if (!(entry->flags & META_VALID)) {
        // 캐시 미스: 디스크에서 메타데이터 로드
        load_metadata_from_disk(block_nr, entry->metadata);
        entry->start_sector = block_nr * SECTORS_PER_BLOCK;
        entry->flags |= META_VALID;
    }

    lc_unlock(meta_cache);
    return entry;
}

/* 메타데이터 해제: 참조 카운트 감소 */
static void meta_cache_release(
    struct block_meta_entry *entry)
{
    lc_put(meta_cache, &entry->lce);
}

/* 해제 */
static void meta_cache_destroy(void)
{
    lc_destroy(meta_cache);
    kmem_cache_destroy(meta_slab);
}

참고 자료

커널 소스 참조

• include/linux/lru_cache.h — lru_cache 모듈의 구조체(lc_element, lru_cache)와 API(lc_get, lc_put, lc_find) 선언입니다
• lib/lru_cache.c — lru_cache 모듈의 해시 테이블 기반 조회, LRU 교체, 참조 카운팅 구현입니다
• drivers/block/drbd/drbd_actlog.c — DRBD 활동 로그 관리 코드로, lru_cache의 대표적인 사용 사례입니다
• include/linux/list_lru.h — list_lru API 정의 및 NUMA 인식 LRU 리스트 구조체를 선언합니다
• mm/list_lru.c — list_lru_add(), list_lru_del(), list_lru_isolate() 등 LRU 리스트 연산의 핵심 구현입니다
• include/linux/mm_inline.h — folio_lru_list(), lru_to_page() 등 folio LRU 인라인 함수를 정의합니다
• mm/vmscan.c — 페이지 회수(Page Reclaim) 메인 로직, shrink_lruvec(), MGLRU 에이징/축출 구현을 포함합니다
• include/linux/shrinker.h — Shrinker 인터페이스 정의로, LRU 캐시와 메모리 회수 경로를 연결합니다
• include/linux/mmzone.h — lruvec, lru_gen_folio, lru_gen_mm_walk 구조체가 정의되어 있습니다
• mm/swap.c — folio_mark_accessed(), folio_activate() 등 LRU 리스트 간 이동 로직입니다
• mm/workingset.c — 워킹셋 감지, shadow entry 관리, refault distance 계산을 구현합니다
• fs/dcache.c — Dentry 캐시의 LRU 관리 및 dentry_lru_isolate() shrinker 콜백 구현입니다
• fs/inode.c — Inode 캐시의 LRU 관리 및 inode_lru_isolate() shrinker 콜백 구현입니다

외부 참고 문서

• Page Reclaim — The Linux Kernel documentation — 커널 공식 문서로 페이지 회수 메커니즘과 LRU 리스트 관리를 설명합니다
• Unevictable LRU Infrastructure — 커널 공식 문서로 mlock()된 페이지의 LRU 격리 메커니즘을 설명합니다
• Multi-Gen LRU — Kernel Admin Guide — MGLRU의 활성화 방법, 튜닝 파라미터, 성능 특성을 다루는 관리자 가이드입니다
• Multigen LRU: a new page reclaim framework (LWN, 2022) — MGLRU가 메인라인에 병합될 당시 아키텍처와 설계 철학을 상세히 분석합니다
• The multi-generational LRU (LWN, 2021) — Yu Zhao가 제안한 MGLRU의 초기 설계 개념과 기존 active/inactive 방식의 한계를 소개합니다
• Multigenerational LRU: the next generation (LWN, 2021) — MGLRU v2 패치 시리즈의 주요 변경 사항과 커뮤니티 피드백을 다룹니다
• Per-superblock LRU lists (LWN, 2013) — 파일시스템별 LRU 분리를 통한 list_lru 인프라 도입 배경을 설명합니다
• Better active/inactive list balancing (LWN, 2012) — active/inactive 리스트 간 균형 조정 알고리즘의 개선 과정을 분석합니다
• Page replacement for huge memory systems (LWN, 2008) — 대용량 메모리 시스템에서 기존 LRU 스캔의 확장성 문제를 논의합니다
• MGLRU patchset v15 (lore.kernel.org) — Yu Zhao의 MGLRU 최종 패치 시리즈로, 메인라인 병합에 사용된 버전입니다
• MGLRU performance data (LWN, 2022) — Chrome OS, Android, 서버 워크로드에서의 MGLRU 성능 벤치마크 결과를 제시합니다
• LPC 2022: Multi-Gen LRU — Yu Zhao — Linux Plumbers Conference 2022에서 Yu Zhao가 MGLRU의 설계와 성능을 발표한 영상입니다
• An overview of memory reclaim (LWN, 2018) — 리눅스 커널의 전체 메모리 회수 아키텍처를 개괄적으로 설명합니다
• Memory management notifiers and read-only mappings (LWN, 2007) — LRU와 연관된 페이지 에이징에서 accessed 비트 처리 방식을 다룹니다