Lock-free 자료구조

Lock-free 자료구조는 전통적인 뮤텍스(Mutex)/스핀락(Spinlock) 없이 원자적(atomic) 연산만으로 동시 접근 안전성을 보장하는 자료구조입니다. Linux 커널은 네트워킹, 블록 I/O, 스케줄링, 메모리 관리(Memory Management) 등 핵심 경로에서 llist, kfifo, ptr_ring, xarray, seqcount_latch, percpu_ref 등 다양한 lock-free/lockless 자료구조를 활용합니다. 이 문서에서는 CAS 패턴과 ABA 문제부터 각 자료구조의 내부 구현, RCU 기반 해시 테이블(Hash Table), 메모리 회수(Memory Reclaim) 전략, 아키텍처별 원자적 연산(Atomic Operation) 비용, LKMM 기반 검증까지 전 영역을 심층 분석합니다.

/* Lock-free 핵심 원자적 연산 — arch/x86/include/asm/cmpxchg.h */
/* CAS (Compare-And-Swap) */
old = cmpxchg(&ptr, expected, desired);
/* 성공하면 ptr = desired, old = expected 반환 */
/* 실패하면 ptr 변경 없음, old = 현재값 반환 → 재시도 */

/* 무조건 교환 */
old = xchg(&ptr, new_val);

/* Acquire/Release 의미론 — 컴파일러+CPU 배리어 */
smp_store_release(&shared, val);  /* 이전 쓰기 모두 완료 후 저장 */
val = smp_load_acquire(&shared);  /* 로드 후 이후 읽기/쓰기 수행 */

# Lock-free 관련 커널 소스 탐색
grep -rn "cmpxchg\|xchg" include/linux/llist.h | head -5
grep -rn "smp_store_release\|smp_load_acquire" include/linux/kfifo.h | head -5
grep -rn "WRITE_ONCE\|READ_ONCE" include/linux/ptr_ring.h | head -5

단계별 이해: Lock-free 자료구조 활용 흐름

단계 1: 동시성 패턴 식별

Lock-free 자료구조를 선택하기 전에, 해당 코드 경로의 생산자/소비자 수와 접근 패턴을 파악합니다. SPSC(단일 생산자-단일 소비자)는 가장 단순하고 효율적인 lock-free 설계가 가능합니다. MPSC(다중 생산자-단일 소비자)는 IRQ 핸들러(Handler)에서 프로세스 컨텍스트로 작업을 전달하는 전형적인 패턴입니다. MPMC(다중 생산자-다중 소비자)는 가장 복잡하며 대부분 lock 보조가 필요합니다.

단계 2: 적합한 자료구조 선택

패턴에 따라 커널이 제공하는 검증된 자료구조를 선택합니다. 커스텀 lock-free 자료구조는 최후의 수단이어야 합니다. 대부분의 사용 사례는 llist, kfifo, ptr_ring, xarray로 충분합니다.

단계 3: 메모리 순서 의미론 적용

smp_store_release()/smp_load_acquire() 쌍, 또는 smp_wmb()/smp_rmb() 쌍으로 데이터 의존성과 가시성을 보장합니다. x86은 TSO(Total Store Order) 모델이라 일부 배리어가 no-op이지만, ARM/POWER 등 약한 순서 아키텍처에서는 반드시 명시적 배리어가 필요합니다.

단계 4: LKMM 및 litmus test로 검증

Linux Kernel Memory Model(LKMM)의 herd7 도구로 설계의 정확성을 수학적으로 검증합니다. tools/memory-model/litmus-tests/에 실제 커널 패턴의 litmus test 예제가 포함되어 있습니다.

Lock-free 개요

진행 보장 수준 정의

비차단(non-blocking) 동기화는 진행 보장(progress guarantee) 수준에 따라 세 단계로 분류됩니다. Linux 커널의 lock-free 자료구조는 대부분 lock-free 수준을 목표로 하며, 특정 SPSC 경로(kfifo, ptr_ring)는 wait-free까지 달성합니다.

선형화 가능성(Linearizability)

선형화 가능성(Linearizability)은 lock-free 자료구조의 정확성(correctness)을 정의하는 핵심 개념입니다. 각 연산이 호출(invocation)과 응답(response) 사이의 특정 시점(linearization point)에서 원자적으로 실행된 것처럼 관찰 가능하다면, 그 실행은 선형화 가능합니다.

/* 선형화 가능성 예시: llist_add()의 선형화 지점 */
static inline bool llist_add(struct llist_node *new,
                             struct llist_head *head)
{
    struct llist_node *first;
    do {
        new->next = first = READ_ONCE(head->first);
    } while (cmpxchg(&head->first, first, new) != first);
    /*            ↑ 선형화 지점: 이 cmpxchg 성공 순간
     * 이 시점에서 new 노드가 리스트에 "원자적으로" 삽입된 것으로 관찰됨
     * cmpxchg 이전: new는 리스트에 없음
     * cmpxchg 이후: new는 리스트의 헤드
     */
    return !first;
}

/* 비-선형화 가능 연산 예시: 2단계 갱신 */
/* 아래 코드는 선형화 불가 — 중간 상태가 관찰될 수 있음 */
WRITE_ONCE(obj->field_a, new_a);  /* 1단계 */
/* ← 다른 CPU가 field_a=new, field_b=old 상태를 관찰 가능 */
WRITE_ONCE(obj->field_b, new_b);  /* 2단계 */
/* 해결: seqcount로 감싸서 일관된 스냅샷 보장 */

커널 Lock-free 도입 역사

Linux 커널의 lock-free 인프라는 15년에 걸쳐 점진적으로 성숙했습니다. 초기에는 개별 해킹에 가까운 lockless 패턴이 산재했으나, RCU의 본격 도입 이후 체계적인 lock-free API 생태계가 형성되었습니다.

Lock-free가 필요한 상황

다음 조건 중 하나라도 해당하면 lock-free 자료구조를 고려합니다:

• IRQ/NMI 컨텍스트: spinlock을 잡을 수 없거나 중첩 인터럽트(Interrupt)에서 데드락 위험이 있을 때
• 극도의 지연(Latency) 민감 경로: 네트워크 패킷(Packet) 포워딩, 실시간(Real-time) 오디오 등 마이크로초 단위 지연 요구
• 높은 경합(Contention): 수십~수백 CPU가 동시에 같은 자료구조에 접근하여 spinlock 경합이 병목(Bottleneck)인 경우
• 우선순위 역전(Priority Inversion) 방지: RT(Real-Time) 환경에서 저우선순위 태스크(Task)의 lock 보유가 고우선순위를 차단하는 경우

Lock-free vs Lockless vs Wait-free 용어 정리

커널 소스에서 “lockless”와 “lock-free”는 종종 혼용되지만, 학술적으로는 구분됩니다. “Lockless”는 mutex/spinlock을 사용하지 않는 넓은 의미이고, “lock-free”는 시스템 전체의 진행 보장이라는 엄격한 의미입니다. 커널 문서에서 “lockless”라고 표현된 코드가 반드시 lock-free 진행 보장을 하는 것은 아닙니다.

Linux 커널의 Lock-free 역사

Linux 커널의 lock-free 자료구조는 커널 발전과 함께 점진적으로 도입되었습니다:

• 2.6.12 (2005): RCU 본격 도입 — lock-free 읽기의 기반
• 2.6.33 (2010): kfifo 재설계 — lockless SPSC 링 버퍼 API 정비
• 3.0 (2011): llist 도입 — include/linux/llist.h, MPSC lock-free 스택
• 4.2 (2015): percpu_ref 안정화 — blk-mq, cgroup 등에서 활용
• 4.6 (2016): rhashtable 안정화 — 자동 리사이징 RCU 해시 테이블
• 4.20 (2018): xarray 도입 — radix tree 대체, 통합된 lock-free 읽기 API
• 5.0 (2019): ptr_ring 네트워킹 전면 채택 — page_pool 등
• 5.3 (2019): LKMM (Linux Kernel Memory Model) 공식 통합 — 형식 검증 도구
• 5.8 (2020): KCSAN 도입 — 런타임 데이터 레이스 감지

Linux 커널의 비차단 동기화 빌딩 블록

/* 1. Atomic read/write — 찢어짐(tearing) 방지 */
READ_ONCE(x);           /* 컴파일러 최적화 방지 단일 로드 */
WRITE_ONCE(x, val);     /* 컴파일러 최적화 방지 단일 스토어 */

/* 2. Atomic RMW (Read-Modify-Write) */
atomic_inc(&counter);                        /* 원자적 증가 */
old = atomic_cmpxchg(&v, expected, desired); /* CAS */
old = atomic_xchg(&v, new_val);              /* 무조건 교환 */
old = atomic_fetch_add(delta, &v);           /* fetch-and-add */

/* 3. Memory ordering */
smp_wmb();              /* 쓰기-쓰기 배리어 */
smp_rmb();              /* 읽기-읽기 배리어 */
smp_mb();               /* 완전 배리어 */
smp_store_release();    /* 릴리스 의미론 저장 */
smp_load_acquire();     /* 어콰이어 의미론 로드 */

/* 4. RCU — 읽기 측 lock-free */
rcu_read_lock();        /* preempt_disable (또는 no-op) */
p = rcu_dereference(gp);  /* 의존성 순서 로드 */
rcu_read_unlock();
synchronize_rcu();      /* 모든 읽기 측 완료 대기 */

CAS 패턴과 ABA 문제

CAS(Compare-And-Swap) 루프 패턴

CAS는 lock-free 프로그래밍의 핵심 원시 연산입니다. Linux 커널에서는 cmpxchg()로 구현되며, “현재 값이 예상과 같으면 새 값으로 교체하고, 다르면 실패”하는 원자적 연산입니다. 실패 시 현재 값을 읽어 재시도하는 루프 패턴이 lock-free 자료구조의 기본 골격입니다.

CAS 변형: cmpxchg, cmpxchg64, cmpxchg128, try_cmpxchg

Linux 커널은 다양한 크기와 의미론의 CAS 변형을 제공합니다. 특히 try_cmpxchg()는 조건 분기를 최적화하여 x86에서 더 효율적인 코드를 생성합니다.

/* try_cmpxchg: cmpxchg보다 효율적인 CAS 루프 패턴 */
/* 전통적 cmpxchg 루프 */
do {
    old = READ_ONCE(*ptr);
    new = old + 1;
} while (cmpxchg(ptr, old, new) != old);
/* → cmpxchg 반환값과 old를 비교하는 추가 연산 필요 */

/* try_cmpxchg 루프 — x86에서 ZF(Zero Flag) 직접 활용 */
old = READ_ONCE(*ptr);
do {
    new = old + 1;
} while (!try_cmpxchg(ptr, &old, new));
/* → 실패 시 old가 자동으로 현재 값으로 갱신됨
 * → 조건 분기가 CMPXCHG의 ZF를 직접 사용 → 비교 연산 제거
 * → 커널 5.x 이후 권장 패턴 */

/* cmpxchg128: 더블워드 CAS (ABA 방지에 유용) */
/* 포인터 + 세대 카운터를 원자적으로 교체 */
struct tagged_ptr {
    void *ptr;
    unsigned long gen;    /* 세대 번호 */
} __aligned(16);

/* 16바이트 원자적 교체 — x86_64의 CMPXCHG16B */
old.ptr = current_ptr;
old.gen = current_gen;
new.ptr = new_ptr;
new.gen = current_gen + 1;
cmpxchg128(&tagged, old, new);

ABA 문제 발생 시나리오 상세

ABA 문제는 lock-free 스택/큐에서 메모리 재사용이 일어날 때 가장 위험합니다. 특히 SLAB 할당자에서 해제된 객체가 같은 주소에 즉시 재할당되는 시나리오가 대표적입니다.

/* ABA가 실제로 발생하는 lock-free 스택 예시 (잘못된 구현) */
struct node {
    struct node *next;
    void *data;
};

static struct node *stack_head;

/* push: ABA 가능한 lock-free 스택 */
void push(struct node *n)
{
    do {
        n->next = READ_ONCE(stack_head);
    } while (cmpxchg(&stack_head, n->next, n) != n->next);
}

/* pop: ABA 위험! */
struct node *pop(void)
{
    struct node *old, *next;
    do {
        old = READ_ONCE(stack_head);
        if (!old)
            return NULL;
        next = READ_ONCE(old->next);  /* old가 이미 해제되었을 수 있음! */
    } while (cmpxchg(&stack_head, old, next) != old);
    /* ABA: old 주소가 재사용되면 next는 잘못된 포인터 */
    return old;
}

/* 해결: RCU 보호 추가 */
struct node *pop_safe(void)
{
    struct node *old, *next;
    rcu_read_lock();  /* old가 해제되지 않음을 보장 */
    do {
        old = rcu_dereference(stack_head);
        if (!old) {
            rcu_read_unlock();
            return NULL;
        }
        next = READ_ONCE(old->next);  /* RCU 보호 하에 안전 */
    } while (cmpxchg(&stack_head, old, next) != old);
    rcu_read_unlock();
    return old;
    /* old는 이후 kfree_rcu()로 지연 해제 */
}

ABA 해결책 상세

CAS 루프 패턴과 백오프 전략

CAS 루프가 고경합 환경에서 반복 실패하면 성능이 급격히 저하됩니다. 백오프(back-off) 전략은 실패 후 잠시 대기하여 경합을 완화합니다.

/* 백오프 전략 1: cpu_relax() — 가장 단순 */
do {
    old = READ_ONCE(*ptr);
    new = transform(old);
    if (try_cmpxchg(ptr, &old, new))
        break;
    cpu_relax();  /* 파이프라인 힌트, 전력 절약 */
} while (true);

/* 백오프 전략 2: 지수 백오프 (사용자 공간, 커널에서는 드묾) */
unsigned int backoff = 1;
do {
    old = READ_ONCE(*ptr);
    new = transform(old);
    if (try_cmpxchg(ptr, &old, new))
        break;
    for (unsigned int i = 0; i < backoff; i++)
        cpu_relax();
    if (backoff < MAX_BACKOFF)
        backoff <<= 1;
} while (true);

/* 커널의 실용적 접근: CAS 루프 대신 xchg + 배치 처리 */
/* llist_del_all()이 CAS 루프 대신 xchg를 사용하는 이유:
 * - xchg는 무조건 성공 (wait-free)
 * - 반환된 리스트를 순회하여 배치 처리
 * - 개별 CAS 반복보다 전체 처리량이 우수 */

/* 전형적인 CAS 루프 패턴 */
do {
    old = READ_ONCE(*ptr);
    new = transform(old);      /* old 기반으로 새 값 계산 */
} while (cmpxchg(ptr, old, new) != old);
/* cmpxchg 성공 시 루프 탈출, 실패 시 old 갱신 후 재시도 */

ABA 문제의 정의

ABA 문제는 CAS가 “값이 바뀌지 않았다”고 판단했지만, 실제로는 A → B → A로 변경된 후 다시 원래 값으로 돌아온 상황입니다. 특히 포인터 기반 lock-free 스택/큐에서 노드가 해제(free)되었다가 같은 주소에 재할당(realloc)될 때 발생합니다.

Linux 커널의 ABA 방지 전략

/* RCU로 ABA 방지하는 패턴 */
rcu_read_lock();
node = rcu_dereference(head);
/* 이 시점에서 node는 해제되지 않음이 보장됨 */
/* → ABA 불가: grace period가 끝나야 free 가능 */
val = node->data;
rcu_read_unlock();

/* 해제 측 */
old = rcu_dereference_protected(head, lockdep_is_held(&lock));
rcu_assign_pointer(head, new_node);
kfree_rcu(old, rcu_head);  /* grace period 후 해제 */

llist (Lock-free Linked List) API와 내부

개요

llist는 Linux 커널의 가장 단순하고 강력한 lock-free 자료구조입니다. MPSC(다중 생산자-단일 소비자) 패턴의 단방향 연결 리스트(스택)로, 추가(llist_add())는 cmpxchg() 기반 lock-free이고, 전체 삭제(llist_del_all())는 xchg()로 wait-free입니다. IRQ/NMI 컨텍스트에서도 안전하게 추가할 수 있어, 인터럽트에서 프로세스 컨텍스트로 작업을 전달하는 핵심 메커니즘입니다.

/* include/linux/llist.h */
struct llist_head {
    struct llist_node *first;
};

struct llist_node {
    struct llist_node *next;
};

/* 핵심 API */
bool llist_add(struct llist_node *new, struct llist_head *head);
struct llist_node *llist_del_all(struct llist_head *head);
struct llist_node *llist_del_first(struct llist_head *head);

/* 순회 매크로 */
llist_for_each(pos, first)
llist_for_each_entry(pos, first, member)
llist_for_each_entry_safe(pos, n, first, member)

llist_add() 내부 구현

/* include/linux/llist.h — 단순화 */
static inline bool llist_add(struct llist_node *new,
                             struct llist_head *head)
{
    struct llist_node *first;

    do {
        new->next = first = READ_ONCE(head->first);
    } while (cmpxchg(&head->first, first, new) != first);
    /*
     * 1. head->first를 읽어 new->next에 저장
     * 2. cmpxchg로 head->first를 new로 교체 시도
     * 3. 실패 시(다른 CPU가 먼저 추가) 재시도
     * → 항상 최소 하나의 CPU가 성공: lock-free
     */
    return !first; /* 리스트가 비어있었으면 true */
}

llist_del_all() — Wait-free 전체 삭제

/* include/linux/llist.h */
static inline struct llist_node *llist_del_all(struct llist_head *head)
{
    return xchg(&head->first, NULL);
    /*
     * xchg는 무조건 성공하므로 재시도 없음 → wait-free
     * 반환값: 이전 리스트의 첫 노드 (또는 NULL)
     * 소비자는 반환된 리스트를 안전하게 순회/처리
     */
}

커널 내 llist 사용 사례

llist API 상세: llist_add/llist_del_all/llist_for_each

/* llist_del_first() 내부 — cmpxchg 기반 */
static inline struct llist_node *llist_del_first(struct llist_head *head)
{
    struct llist_node *entry, *next;

    entry = smp_load_acquire(&head->first);
    do {
        if (entry == NULL)
            return NULL;
        next = READ_ONCE(entry->next);
    } while (!try_cmpxchg(&head->first, &entry, next));
    /*
     * 주의: 다중 소비자에서 사용하면 위험!
     * 두 소비자가 같은 entry를 보고 경합 → 하나는 이미 처리된 노드를 받음
     * → 반드시 단일 소비자만 호출해야 함
     */
    return entry;
}

/* llist_reverse_order() — O(n) 리스트 역전 */
static inline struct llist_node *llist_reverse_order(struct llist_node *head)
{
    struct llist_node *new_head = NULL;

    while (head) {
        struct llist_node *tmp = head;
        head = head->next;
        tmp->next = new_head;
        new_head = tmp;
    }
    return new_head;
    /* 주의: 분리된(del_all 이후) 리스트에서만 호출
     * 공유 리스트에서 호출하면 데이터 레이스 */
}

IRQ 컨텍스트 llist 사용 패턴

llist의 가장 중요한 사용 패턴은 IRQ 핸들러에서 프로세스 컨텍스트로 작업을 전달하는 것입니다. IRQ 컨텍스트에서는 spinlock도 위험하지만, llist_add()는 cmpxchg()만 사용하므로 NMI를 포함한 모든 인터럽트 컨텍스트에서 안전합니다.

/* 전형적인 IRQ→프로세스 컨텍스트 llist 패턴 */
struct my_work {
    struct llist_node node;
    void (*func)(struct my_work *);
    void *data;
};

static LLIST_HEAD(work_list);
static struct task_struct *worker_task;

/* IRQ 핸들러에서 (NMI에서도 안전) */
irqreturn_t my_irq_handler(int irq, void *dev_id)
{
    struct my_work *w = alloc_work_from_pool();
    w->func = process_data;
    w->data = read_device_register();

    /* llist_add: cmpxchg만 사용, lock 없음, NMI-safe */
    if (llist_add(&w->node, &work_list))
        wake_up_process(worker_task);
        /* llist_add 반환값: 리스트가 비어있었으면 true
         * → 워커를 깨워야 하는 시점 정확히 판단 */

    return IRQ_HANDLED;
}

/* 워커 스레드 (프로세스 컨텍스트) */
int worker_thread(void *data)
{
    while (!kthread_should_stop()) {
        struct llist_node *list;

        /* xchg로 전체 리스트를 원자적으로 가져옴 */
        list = llist_del_all(&work_list);
        if (!list) {
            set_current_state(TASK_INTERRUPTIBLE);
            if (llist_empty(&work_list))
                schedule();
            __set_current_state(TASK_RUNNING);
            continue;
        }

        /* FIFO 순서가 필요하면 역전 */
        list = llist_reverse_order(list);

        /* 안전하게 순회하며 처리 */
        struct my_work *w, *tmp;
        llist_for_each_entry_safe(w, tmp, list, node) {
            w->func(w);
            free_work_to_pool(w);
        }
    }
    return 0;
}

커널 내 llist 주요 사용 사례 상세

/* kernel/smp.c — generic_exec_single() 핵심 경로 (단순화) */
static int generic_exec_single(int cpu, struct __call_single_data *csd)
{
    /* csd를 대상 CPU의 콜 리스트에 추가 */
    if (llist_add(&csd->node.llist, &per_cpu(call_single_queue, cpu)))
        send_call_function_single_ipi(cpu);
        /* 리스트가 비어있었으면(처음 추가) IPI 전송 */
    return 0;
}

/* kernel/rcu/tree.c — RCU 콜백 큐잉 (단순화) */
void call_rcu(struct rcu_head *head, rcu_callback_t func)
{
    head->func = func;
    /* per-CPU 콜백 리스트에 lock-free 추가 */
    if (llist_add(&head->llist, &rdp->nocb_gp_head))
        wake_nocb_gp(rdp);
}

/* kernel/workqueue.c — work item 큐잉 (NO_POOL_CQ 경로) */
/* workqueue의 일부 경로에서 llist로 lock 없이 work item 전달 */

MPSC Queue (다중 생산자-단일 소비자)

MPSC 패턴의 특성

MPSC(Multiple Producer, Single Consumer) 패턴은 Linux 커널에서 가장 빈번하게 사용되는 lock-free 패턴입니다. 여러 CPU의 인터럽트 핸들러나 softirq가 작업을 생성하고, 단일 워커 스레드가 이를 소비하는 구조입니다. 소비자가 하나이므로 소비 측에서는 동기화가 불필요하고, 생산 측만 CAS로 조율하면 됩니다.

MPSC 큐 구현 패턴: llist + llist_reverse_order()

llist는 스택(LIFO)이므로 큐(FIFO) 동작이 필요하면 llist_del_all() 후 llist_reverse_order()로 순서를 뒤집어 사용합니다. 이 패턴은 kernel/smp.c의 IPI 콜백 처리에서 사용됩니다.

/* kernel/smp.c — IPI 콜백 FIFO 처리 패턴 (단순화) */
/* 생산자 (원격 CPU, IRQ 컨텍스트) */
llist_add(&csd->node, &per_cpu(call_single_queue, cpu));

/* 소비자 (대상 CPU) */
entry = llist_del_all(&per_cpu(call_single_queue, smp_processor_id()));
entry = llist_reverse_order(entry);  /* LIFO → FIFO 변환 */
llist_for_each_entry_safe(csd, csd_next, entry, node) {
    csd->func(csd->info);  /* 콜백 실행 */
}

MPSC 설계 원칙: 단일 소비자 보장

MPSC 패턴의 핵심 이점은 소비자가 하나이므로 소비 측에서 동기화가 불필요하다는 점입니다. 이 불변식(invariant)을 보장하는 커널의 메커니즘을 정리합니다.

IRQ-safe MPSC 패턴

/* IRQ-safe MPSC의 핵심: 생산자는 IRQ/NMI, 소비자는 프로세스 컨텍스트 */

/* 패턴 1: IRQ disable 불필요 (llist이 원자적) */
/* 생산자 (hardirq) */
void producer_irq(struct llist_head *head, struct llist_node *n)
{
    llist_add(n, head);  /* cmpxchg만 사용, IRQ disable 불필요 */
}

/* 패턴 2: softirq 생산자 + kthread 소비자 */
/* 생산자 (softirq, 여러 CPU) */
void producer_softirq(struct llist_head *head, struct work_item *item)
{
    if (llist_add(&item->lnode, head))
        wake_up_process(consumer_thread);
}

/* 소비자 (kthread, 단일) */
void consumer_loop(struct llist_head *head)
{
    struct llist_node *list = llist_del_all(head);
    /* 이 시점부터 list는 로컬 → 동기화 불필요 */
    struct work_item *item, *tmp;
    llist_for_each_entry_safe(item, tmp, list, lnode) {
        process_item(item);
    }
}

MPSC 배치 처리 최적화

MPSC 패턴에서 llist_del_all()의 배치 소비는 개별 llist_del_first() 반복보다 훨씬 효율적입니다. 이유는 두 가지입니다:

• 원자적 연산 횟수: del_all은 xchg 1회, del_first N번은 cmpxchg N회
• 캐시(Cache)라인 바운싱: del_all은 head->first 캐시라인을 1회만 수정, 이후 로컬 순회

/* 배치 vs 개별 성능 비교 (의사 벤치마크) */
/* 개별 소비: N개 항목 처리 시 */
for (int i = 0; i < N; i++) {
    node = llist_del_first(&head);  /* cmpxchg × N */
    process(node);
}
/* 총 원자적 연산: N × cmpxchg
 * head->first 캐시라인 접근: N회 */

/* 배치 소비: N개 항목 처리 시 */
list = llist_del_all(&head);       /* xchg × 1 */
llist_for_each_entry_safe(node, tmp, list, lnode) {
    process(node);                   /* 순수 메모리 접근 */
}
/* 총 원자적 연산: 1 × xchg
 * head->first 캐시라인 접근: 1회
 * → N이 클수록 배치 소비의 이점 극대화 */

kfifo: Lockless Ring Buffer

개요

kfifo는 Linux 커널의 범용 링 버퍼(circular buffer) 구현입니다. SPSC(단일 생산자-단일 소비자) 모드에서는 lock 없이 메모리 배리어만으로 동기화되며, MPSC/MPMC 모드에서는 생산자/소비자 측에 각각 spinlock을 보조로 사용합니다. 크기는 반드시 2의 거듭제곱이어야 하며, 비트 마스킹으로 인덱스 래핑을 수행합니다.

/* include/linux/kfifo.h — 핵심 구조 (단순화) */
struct __kfifo {
    unsigned int    in;     /* 쓰기 인덱스 (생산자만 수정) */
    unsigned int    out;    /* 읽기 인덱스 (소비자만 수정) */
    unsigned int    mask;   /* size - 1 (비트 마스킹용) */
    unsigned int    esize;  /* 요소 크기 */
    void            *data;  /* 링 버퍼 데이터 영역 */
};

/* 매크로 기반 타입-안전 인터페이스 */
DECLARE_KFIFO(name, type, size);
DEFINE_KFIFO(name, type, size);
kfifo_put(&fifo, val);          /* 단일 요소 삽입 */
kfifo_get(&fifo, &val);         /* 단일 요소 추출 */
kfifo_in(&fifo, buf, count);    /* 다중 요소 삽입 */
kfifo_out(&fifo, buf, count);   /* 다중 요소 추출 */
kfifo_len(&fifo);               /* 현재 저장된 요소 수 */
kfifo_is_empty(&fifo);
kfifo_is_full(&fifo);

SPSC kfifo: Lockless 동작 원리

SPSC kfifo의 lockless 동기화는 두 가지 핵심 원칙에 기반합니다: (1) in은 생산자만 수정하고 out은 소비자만 수정하는 소유권 분리, (2) smp_store_release()/smp_load_acquire()로 데이터와 인덱스의 가시성 순서를 보장합니다.

SPSC Lockless kfifo 동기화 분석

/* lib/kfifo.c — __kfifo_in() 단순화 */
static unsigned int __kfifo_in(struct __kfifo *fifo,
                               const void *buf, unsigned int len)
{
    unsigned int off;
    unsigned int l;

    l = kfifo_unused(fifo);      /* 가용 공간 계산: size - (in - out) */
    if (len > l)
        len = l;

    off = fifo->in & fifo->mask; /* 물리 오프셋 계산 */
    /* 래핑을 고려한 2단계 memcpy */
    l = min(len, fifo->mask + 1 - off);
    memcpy(fifo->data + off * fifo->esize, buf, l * fifo->esize);
    memcpy(fifo->data, buf + l * fifo->esize, (len - l) * fifo->esize);

    /* 배리어: 데이터가 먼저 기록된 후에 in이 갱신됨을 보장 */
    smp_store_release(&fifo->in, fifo->in + len);
    return len;
}

/* lib/kfifo.c — __kfifo_out() 단순화 */
static unsigned int __kfifo_out(struct __kfifo *fifo,
                                void *buf, unsigned int len)
{
    unsigned int off;
    unsigned int l;

    l = fifo->in - fifo->out;   /* smp_load_acquire는 kfifo_len에서 수행 */
    if (len > l)
        len = l;

    off = fifo->out & fifo->mask;
    l = min(len, fifo->mask + 1 - off);
    memcpy(buf, fifo->data + off * fifo->esize, l * fifo->esize);
    memcpy(buf + l * fifo->esize, fifo->data, (len - l) * fifo->esize);

    smp_store_release(&fifo->out, fifo->out + len);
    return len;
}

kfifo MPSC/MPMC 모드: spinlock 보조

/* MPSC 사용: 생산자 측에만 spinlock */
static DEFINE_KFIFO(my_fifo, struct event, 256);
static DEFINE_SPINLOCK(producer_lock);

/* 생산자 (여러 CPU에서 호출 가능) */
void produce_event(struct event *e)
{
    unsigned long flags;
    spin_lock_irqsave(&producer_lock, flags);
    kfifo_put(&my_fifo, *e);
    spin_unlock_irqrestore(&producer_lock, flags);
}

/* 소비자 (단일 스레드) — lock 불필요 */
void consume_events(void)
{
    struct event e;
    while (kfifo_get(&my_fifo, &e))
        process_event(&e);
}

/* MPMC: 양쪽 모두 spinlock 필요 */
static DEFINE_SPINLOCK(consumer_lock);
void consume_mpmc(void)
{
    struct event e;
    spin_lock(&consumer_lock);
    while (kfifo_get(&my_fifo, &e))
        process_event(&e);
    spin_unlock(&consumer_lock);
}

kfifo 사용 패턴: 커널→사용자 공간 전달

/* kfifo_to_user: 커널 kfifo → 사용자 공간 버퍼 직접 복사 */
ssize_t my_read(struct file *filp, char __user *buf,
                size_t count, loff_t *ppos)
{
    unsigned int copied;
    int ret;

    if (kfifo_is_empty(&my_fifo)) {
        if (filp->f_flags & O_NONBLOCK)
            return -EAGAIN;
        /* 블로킹 모드: 데이터 대기 */
        ret = wait_event_interruptible(my_waitq,
                                       !kfifo_is_empty(&my_fifo));
        if (ret)
            return ret;
    }

    ret = kfifo_to_user(&my_fifo, buf, count, &copied);
    if (ret)
        return ret;

    return copied;
}

/* kfifo_from_user: 사용자 공간 → 커널 kfifo 직접 복사 */
ssize_t my_write(struct file *filp, const char __user *buf,
                 size_t count, loff_t *ppos)
{
    unsigned int copied;
    int ret;

    ret = kfifo_from_user(&my_fifo, buf, count, &copied);
    if (ret)
        return ret;

    wake_up_interruptible(&my_waitq);
    return copied;
}

kfifo record 모드: 가변 길이 레코드

kfifo는 고정 크기 요소 외에도 가변 길이 레코드를 지원합니다. DECLARE_KFIFO(name, type, size)에서 type에 struct { ... }를 사용하거나, kfifo_in()/kfifo_out()의 바이트 스트림 모드를 활용합니다.

/* kfifo record 모드: 가변 길이 메시지 큐 */
/* 레코드 kfifo: 각 레코드에 길이 헤더가 자동 추가됨 */
static DEFINE_KFIFO(msg_fifo, unsigned char, 4096);

/* 가변 길이 메시지 삽입 */
struct message {
    u16 type;
    u16 len;
    u8 data[];
};

void enqueue_message(struct message *msg, size_t total_len)
{
    /* kfifo_in: total_len 바이트를 링 버퍼에 복사 */
    unsigned int copied = kfifo_in(&msg_fifo, msg, total_len);
    if (copied != total_len)
        pr_warn("msg_fifo full, dropped %zu bytes\n",
                total_len - copied);
}

/* 가변 길이 메시지 추출 */
int dequeue_message(struct message *buf, size_t buf_size)
{
    unsigned int copied = kfifo_out(&msg_fifo, buf, buf_size);
    return copied;
}

/* kfifo_peek: 소비하지 않고 미리보기 */
unsigned int peeked = kfifo_out_peek(&msg_fifo, buf, buf_size);

/* kfifo_skip: 데이터를 복사하지 않고 건너뛰기 */
kfifo_skip(&msg_fifo);  /* 최신 레코드를 건너뜀 */

kfifo와 DMA scatter-gather

kfifo는 DMA 전송을 위한 scatter-gather 리스트 생성을 직접 지원합니다. 래핑(wrap-around) 구간에서 데이터가 물리적으로 두 조각으로 나뉘어도 kfifo_dma_in_prepare()/kfifo_dma_out_prepare()가 올바른 SG 엔트리를 생성합니다.

/* kfifo DMA scatter-gather 사용 패턴 */
#include <linux/kfifo.h>
#include <linux/scatterlist.h>

DEFINE_KFIFO(dma_fifo, u8, 4096);

/* DMA 쓰기 준비: 디바이스 → kfifo */
int prepare_dma_receive(struct scatterlist *sgl, int nents)
{
    return kfifo_dma_in_prepare(&dma_fifo, sgl, nents,
                                kfifo_avail(&dma_fifo));
    /* 반환값: SG 엔트리 수 (래핑 시 최대 2) */
}

/* DMA 완료 후: 인덱스 갱신 */
void dma_receive_complete(unsigned int len)
{
    kfifo_dma_in_finish(&dma_fifo, len);
    /* smp_store_release로 in 인덱스 갱신 */
}

/* DMA 읽기 준비: kfifo → 디바이스 */
int prepare_dma_transmit(struct scatterlist *sgl, int nents)
{
    return kfifo_dma_out_prepare(&dma_fifo, sgl, nents,
                                 kfifo_len(&dma_fifo));
}

커널 내 kfifo 사용 사례 상세

/* drivers/tty/serial/serial_core.c — UART 수신 버퍼 (단순화) */
struct uart_state {
    struct circ_buf xmit;           /* 전통적 원형 버퍼 (일부 드라이버) */
    /* 또는 */
    DECLARE_KFIFO(rx_fifo, u8, 256); /* kfifo 기반 수신 버퍼 */
};

/* UART IRQ 핸들러에서 수신 데이터 삽입 */
irqreturn_t uart_rx_irq(int irq, void *dev_id)
{
    struct uart_state *state = dev_id;
    u8 ch;

    while (uart_rx_ready(state)) {
        ch = uart_read_char(state);
        kfifo_put(&state->rx_fifo, ch);
        /* SPSC: IRQ(생산자) + tty_read(소비자) */
    }
    return IRQ_HANDLED;
}

/* drivers/iio/buffer/kfifo_buf.c — IIO 센서 kfifo 버퍼 */
/* IIO 서브시스템은 센서 데이터를 kfifo에 버퍼링하여
 * 사용자 공간의 read()로 전달합니다.
 * 트리거(생산자)와 사용자 공간 read(소비자)의 SPSC 패턴 */

ptr_ring: 포인터 링 버퍼

개요

ptr_ring은 포인터 크기의 요소만 저장하는 특화된 링 버퍼입니다. kfifo보다 더 단순하고 캐시 친화적이며, 네트워킹 서브시스템(page_pool, tun, vhost)에서 포인터 전달에 최적화되어 있습니다. 생산자와 소비자가 각각 별도의 spinlock을 사용하므로 경합이 최소화됩니다.

/* include/linux/ptr_ring.h */
struct ptr_ring {
    int             producer ____cacheline_aligned_in_smp;
    spinlock_t      producer_lock;
    int             consumer_head ____cacheline_aligned_in_smp;
    int             consumer_tail;
    spinlock_t      consumer_lock;
    int             size ____cacheline_aligned_in_smp;
    int             batch;
    void            **queue;
};

/* 핵심 API */
int ptr_ring_produce(struct ptr_ring *r, void *ptr);
void *ptr_ring_consume(struct ptr_ring *r);
int ptr_ring_produce_bh(struct ptr_ring *r, void *ptr);
void *ptr_ring_consume_bh(struct ptr_ring *r);

캐시라인 분리 최적화

ptr_ring의 핵심 설계 원칙은 ____cacheline_aligned_in_smp를 활용한 캐시라인 분리입니다. 생산자 인덱스(producer)와 소비자 인덱스(consumer_head)가 서로 다른 캐시라인에 위치하므로, 생산자와 소비자가 서로의 캐시라인을 무효화(Invalidation)하지 않습니다(false sharing 방지).

/* include/linux/ptr_ring.h — __ptr_ring_produce() 단순화 */
static inline int __ptr_ring_produce(struct ptr_ring *r, void *ptr)
{
    if (unlikely(!r->size) || r->queue[r->producer])
        return -ENOSPC;

    WRITE_ONCE(r->queue[r->producer], ptr);
    /* 배리어: 포인터 저장 후 인덱스 갱신 */
    if (unlikely(++r->producer >= r->size))
        r->producer = 0;
    return 0;
}

/* __ptr_ring_consume() — batch 소비 최적화 */
static inline void *__ptr_ring_consume(struct ptr_ring *r)
{
    void *ptr;

    ptr = r->queue[r->consumer_head];
    if (!ptr)
        return NULL;
    /* NULL 초기화로 "소비됨" 표시 */
    WRITE_ONCE(r->queue[r->consumer_head], NULL);
    if (unlikely(++r->consumer_head >= r->size))
        r->consumer_head = 0;
    return ptr;
}

page_pool에서의 ptr_ring 활용

/* net/core/page_pool.c — ptr_ring으로 페이지 재활용 */
struct page_pool {
    struct ptr_ring     ring;          /* 재활용 페이지 링 버퍼 */
    /* NAPI가 페이지를 소비하고, 네트워크 스택이 반환 */
    /* ... */
};

/* 페이지 할당: ptr_ring에서 재활용 페이지 가져오기 */
struct page *page_pool_alloc_pages(struct page_pool *pool, gfp_t gfp)
{
    struct page *page;

    /* fast-path: ptr_ring에서 재활용 */
    page = ptr_ring_consume_bh(&pool->ring);
    if (page) {
        /* 이전에 DMA 매핑된 페이지 재사용 → alloc+map 비용 절약 */
        return page;
    }

    /* slow-path: 새 페이지 할당 */
    page = __page_pool_alloc_pages_slow(pool, gfp);
    return page;
}

/* 페이지 반환: 사용 완료된 페이지를 ptr_ring에 삽입 */
void page_pool_put_defragged_page(struct page_pool *pool,
                                   struct page *page, ...)
{
    if (ptr_ring_produce_bh(&pool->ring, page) == 0)
        return;  /* 성공: 재활용 큐에 삽입 */
    /* 링 풀이면 해제 */
    page_pool_return_page(pool, page);
}

ptr_ring API 상세: produce/consume/peek/batch

/* ptr_ring의 batched consume 패턴 */
/* page_pool에서 여러 페이지를 한 번에 소비 */
int ptr_ring_consume_batched(struct ptr_ring *r,
                              void **array, int n)
{
    int ret;
    spin_lock(&r->consumer_lock);
    ret = __ptr_ring_consume_batched(r, array, n);
    spin_unlock(&r->consumer_lock);
    return ret;
}

/* 내부: 최대 n개 포인터를 array에 복사 */
static inline int __ptr_ring_consume_batched(struct ptr_ring *r,
                                              void **array, int n)
{
    int i;
    for (i = 0; i < n; i++) {
        array[i] = __ptr_ring_consume(r);
        if (!array[i])
            break;
    }
    return i;  /* 실제 소비된 수 */
}

page_pool과 ptr_ring 통합

page_pool은 네트워크 드라이버의 페이지 재활용 메커니즘으로, ptr_ring을 핵심 캐시로 사용합니다. NAPI poll 루프(소비자)가 ptr_ring에서 재활용 페이지를 가져오고, 네트워크 스택(Network Stack)이 사용 완료된 페이지를 반환(생산자)합니다.

ptr_ring vs kfifo 비교

ptr_ring 리사이징

/* ptr_ring 크기 동적 조정 */
int ptr_ring_resize(struct ptr_ring *r, int size, gfp_t gfp,
                    void (*destroy)(void *));
/* 새 큐 할당 → 기존 항목 복사 → 기존 큐 해제
 * 생산자/소비자 lock을 모두 잡고 수행 */

/* ptr_ring_resize_multiple: 여러 ptr_ring을 원자적으로 리사이징 */
int ptr_ring_resize_multiple(struct ptr_ring **rings, unsigned int nrings,
                             int size, gfp_t gfp, void (*destroy)(void *));
/* tun/tap 드라이버에서 큐 수 변경 시 사용 */

xarray Lock-free 경로

개요

xarray는 Linux 커널의 범용 기수 트리(radix tree)로, 페이지 캐시(address_space), IDR(ID Radix tree), 그리고 다양한 인덱스-to-포인터 매핑(Mapping)에 사용됩니다. RCU 기반 lock-free 읽기 경로를 제공하여, 읽기 측은 lock 없이 트리를 탐색할 수 있습니다. 쓰기 측은 xa_lock(spinlock)으로 보호됩니다.

/* include/linux/xarray.h */
struct xarray {
    spinlock_t      xa_lock;
    gfp_t           xa_flags;
    void __rcu      *xa_head;
};

/* Lock-free 읽기 API */
void *xa_load(struct xarray *xa, unsigned long index);
/* 내부적으로 rcu_read_lock() + rcu_dereference() 사용 */

/* Lock 기반 쓰기 API */
void *xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp);
void *xa_erase(struct xarray *xa, unsigned long index);

/* RCU 순회 */
xa_for_each(xa, index, entry) { ... }  /* RCU 보호 하에 순회 */

RCU 기반 Lock-free 읽기 내부

/* lib/xarray.c — xa_load() 내부 (단순화) */
void *xa_load(struct xarray *xa, unsigned long index)
{
    void *entry;

    rcu_read_lock();
    entry = xas_load(&xas);  /* RCU로 보호된 트리 탐색 */
    /* 각 레벨에서 rcu_dereference()로 자식 포인터 로드 */
    /* → 쓰기 측이 노드를 교체해도 읽기 측은 안전하게 이전 노드 참조 */
    rcu_read_unlock();
    return entry;
}

/* 쓰기 측: 노드 교체 시 */
rcu_assign_pointer(slot, new_node);  /* 새 노드 공개 */
/* 이전 노드는 grace period 후 해제 */

xa_load() RCU 보호 경로 상세

xa_load()는 내부적으로 XArray의 radix tree를 RCU 보호 하에 탐색합니다. 각 레벨에서 rcu_dereference()로 자식 포인터를 로드하며, 쓰기 측이 노드를 교체하더라도 읽기 측은 이전 노드를 안전하게 참조합니다.

/* lib/xarray.c — xas_load() 내부 (상세 단순화) */
static void *xas_load(struct xa_state *xas)
{
    void *entry = xas_start(xas);

    while (xa_is_node(entry)) {
        struct xa_node *node = xa_to_node(entry);
        /* 인덱스에서 현재 레벨의 오프셋 추출 */
        unsigned int offset = xas_offset(xas);

        /* RCU로 보호된 포인터 로드 */
        entry = rcu_dereference(node->slots[offset]);
        /*
         * 이 시점에서 쓰기 측이 node를 새 노드로 교체해도:
         * - 읽기 측은 이전 node를 계속 참조 (RCU 보호)
         * - 이전 node는 grace period 후에만 해제
         * → ABA 문제 없음, use-after-free 없음
         */
        xas->xa_node = node;
    }
    return entry;
}

XArray Marks와 Lock-free 순회

XArray의 마크(mark) 시스템은 포인터의 하위 비트를 활용하여 엔트리에 태그를 부여합니다. 마크된 엔트리만 선택적으로 순회하는 것도 lock-free(RCU 보호)로 수행됩니다.

/* XArray 마크 기반 lock-free 순회 */
/* dirty 페이지만 순회 — RCU 보호 */
void find_dirty_pages(struct address_space *mapping)
{
    struct folio *folio;
    unsigned long index = 0;

    rcu_read_lock();
    xa_for_each_marked(&mapping->i_pages, index, folio,
                        PAGECACHE_TAG_DIRTY) {
        /* folio는 RCU 보호 하에 유효 */
        /* folio_get()으로 참조 획득 후 처리 */
        if (folio_try_get_rcu(folio))
            process_dirty_folio(folio);
    }
    rcu_read_unlock();
}

/* 마크 설정/해제 — xa_lock 보호 하에 */
xa_set_mark(&xa, index, XA_MARK_0);   /* 마크 설정 */
xa_clear_mark(&xa, index, XA_MARK_0); /* 마크 해제 */

/* 마크 확인 — lock-free */
bool marked = xa_get_mark(&xa, index, XA_MARK_0);

xa_store/xa_erase 내부 Lock-free 경로

xa_store()와 xa_erase()는 xa_lock 보호 하에 수행되지만, 내부적으로 rcu_assign_pointer()를 사용하여 읽기 측에 안전하게 변경을 공개합니다.

/* xa_store 내부의 RCU 공개 메커니즘 (단순화) */
void *xa_store(struct xarray *xa, unsigned long index,
               void *entry, gfp_t gfp)
{
    void *old;

    xa_lock(xa);
    old = __xa_store(xa, index, entry, gfp);
    /* 내부: rcu_assign_pointer(slot, entry)
     *  → 쓰기 배리어 + 포인터 저장
     *  → 읽기 측(xa_load)이 새 entry를 즉시 볼 수 있음
     *  → 이전 entry는 grace period 후 해제 가능 */
    xa_unlock(xa);
    return old;
}

/* xa_cmpxchg: 조건부 교체 (lock 보호 하에 CAS 의미론) */
void *xa_cmpxchg(struct xarray *xa, unsigned long index,
                  void *old, void *entry, gfp_t gfp);
/* 현재 값이 old와 같을 때만 entry로 교체 */

Radix Tree와 RCU 기반 Lock-free 탐색

Radix Tree에서 xarray로의 전환

Linux 커널은 원래 radix_tree를 사용했으나, 4.20 커널부터 xarray로 점진적 전환이 이루어졌습니다. radix_tree는 내부적으로 xarray 위에 구현되며, 호환성 래퍼를 제공합니다. 두 자료구조 모두 RCU 기반 lock-free 읽기를 지원합니다.

/* include/linux/radix-tree.h — xarray 래퍼 */
#define RADIX_TREE(name, mask) \
    struct xarray name = XARRAY_INIT(name, mask)

/* RCU 기반 lock-free 조회 */
void *radix_tree_lookup(const struct radix_tree_root *root,
                        unsigned long index);
/* 내부: xa_load() → rcu_read_lock() + 트리 탐색 */

/* 태그 기반 조회 */
radix_tree_gang_lookup_tag(root, results, first_index,
                           max_items, tag);

RCU Lock-free 탐색의 핵심 원리

Radix tree / xarray의 lock-free 읽기는 다음 원칙에 기반합니다:

• publish-subscribe: 쓰기 측이 rcu_assign_pointer()로 새 노드를 공개하면, 읽기 측은 rcu_dereference()로 안전하게 읽음
• 노드 불변성: 기존 노드의 내용을 수정하지 않고, 새 노드로 교체(copy-on-write 변형)
• 지연 해제: 교체된 이전 노드는 call_rcu()로 grace period 후 해제하여 읽기 측 안전성 보장

seqcount_latch (이중 버퍼 패턴)

개요

seqcount_latch는 쓰기 중에도 읽기가 차단되지 않는 이중 버퍼 패턴입니다. 일반 seqcount는 쓰기 중 읽기가 재시도해야 하지만, seqcount_latch는 두 개의 데이터 복사본을 유지하여 읽기 측이 항상 일관된 스냅샷을 얻을 수 있습니다. timekeeping, ktime, sched_clock 등 시간 관련 핵심 경로에서 사용됩니다.

/* include/linux/seqlock.h — seqcount_latch 사용 패턴 */

/* 쓰기 측 (단일 쓰기자) */
void write_data(struct latch_data *ld, u64 new_val)
{
    raw_write_seqcount_latch(&ld->seq);
    /* seq가 홀수: 읽기 측은 data[1]을 사용 */
    ld->data[0] = new_val;

    raw_write_seqcount_latch(&ld->seq);
    /* seq가 짝수: 읽기 측은 data[0]을 사용 */
    ld->data[1] = new_val;
}

/* 읽기 측 (다수 읽기자, lock-free) */
u64 read_data(struct latch_data *ld)
{
    unsigned int seq;
    u64 val;

    do {
        seq = raw_read_seqcount_latch(&ld->seq);
        val = ld->data[seq & 1];  /* 홀수→[1], 짝수→[0] */
    } while (raw_read_seqcount_latch_retry(&ld->seq, seq));

    return val;
}

raw_write_seqcount_latch 프로토콜 상세

seqcount_latch의 쓰기 프로토콜은 엄격한 4단계로 구성됩니다. 각 단계에서 seq 카운터의 홀짝성이 읽기 측이 어떤 버퍼를 선택하는지 결정합니다.

/* seqcount_latch 쓰기 프로토콜 상세 분석 */
void write_latch(struct latch_data *ld, u64 new_val)
{
    /* 1단계: seq를 홀수로 (읽기 측은 data[1]을 선택) */
    raw_write_seqcount_latch(&ld->seq);
    /* 내부: WRITE_ONCE(seq->sequence, seq->sequence + 1);
     *       smp_wmb();  ← 쓰기 배리어 */

    /* 2단계: data[0] 갱신 (읽기 측은 data[1]을 보므로 안전) */
    WRITE_ONCE(ld->data[0], new_val);

    /* 3단계: seq를 짝수로 (읽기 측은 data[0]을 선택) */
    raw_write_seqcount_latch(&ld->seq);
    /* 내부: smp_wmb();
     *       WRITE_ONCE(seq->sequence, seq->sequence + 1); */

    /* 4단계: data[1] 갱신 (읽기 측은 data[0]을 보므로 안전) */
    WRITE_ONCE(ld->data[1], new_val);

    /* 결과: 두 버퍼 모두 new_val로 갱신 완료
     * 읽기 측은 어느 시점에서든 일관된 값을 읽음 */
}

/* 읽기 측 프로토콜 상세 */
u64 read_latch(struct latch_data *ld)
{
    unsigned int seq;
    u64 val;

    do {
        seq = raw_read_seqcount_latch(&ld->seq);
        /* 내부: READ_ONCE(seq->sequence) */
        /* smp_rmb() — seq 읽기 후 데이터 읽기 전 배리어 */

        val = READ_ONCE(ld->data[seq & 1]);
        /* seq 홀수 → data[1] (쓰기 중이 아닌 버퍼)
         * seq 짝수 → data[0] (최신 완료 버퍼) */

    } while (raw_read_seqcount_latch_retry(&ld->seq, seq));
    /* 내부: smp_rmb() 후 seq가 변경되었는지 확인
     * 변경됨 → 쓰기가 우리 버퍼를 수정 중 → 재시도
     * 변경 안 됨 → 일관된 스냅샷 */

    return val;
}

커널 timekeeping의 seqcount_latch 사용

ktime_get() 등 시간 관련 함수는 초당 수십만 번 호출될 수 있으며, seqcount_latch를 사용하여 틱 업데이트 중에도 lock 없이 시간을 읽습니다.

/* kernel/time/timekeeping.c — tk_fast_mono (단순화) */
struct tk_fast {
    seqcount_latch_t    seq;
    struct tk_read_base base[2];  /* 이중 버퍼 */
};

static struct tk_fast tk_fast_mono ____cacheline_aligned;

/* 쓰기 측: 틱 업데이트 (timer ISR에서) */
static void timekeeping_update_fast(struct timekeeper *tk)
{
    struct tk_read_base *base;
    unsigned int seq;

    /* 1. seq 홀수로 → 읽기는 base[1] 사용 */
    raw_write_seqcount_latch(&tk_fast_mono.seq);
    base = &tk_fast_mono.base[0];
    *base = tk->tkr_mono;  /* base[0] 갱신 */

    /* 2. seq 짝수로 → 읽기는 base[0] 사용 */
    raw_write_seqcount_latch(&tk_fast_mono.seq);
    base = &tk_fast_mono.base[1];
    *base = tk->tkr_mono;  /* base[1] 갱신 */
}

/* 읽기 측: ktime_get_mono_fast_ns() */
u64 ktime_get_mono_fast_ns(void)
{
    struct tk_read_base *tkr;
    unsigned int seq;
    u64 now;

    do {
        seq = raw_read_seqcount_latch(&tk_fast_mono.seq);
        tkr = &tk_fast_mono.base[seq & 1];
        now = ktime_to_ns(tkr->base) +
              timekeeping_delta_to_ns(tkr, ...);
    } while (raw_read_seqcount_latch_retry(&tk_fast_mono.seq, seq));

    return now;
    /* NMI에서도 안전! (NMI에서 spinlock 불가하므로) */
}

seqcount_latch vs seqlock 차이

seqcount_latch 커널 사용 사례

일반 seqcount vs seqcount_latch 비교

/* 일반 seqcount — 쓰기 중 읽기는 반드시 재시도 */
write_seqcount_begin(&seq);    /* seq 홀수 설정 */
shared_data = new_val;
write_seqcount_end(&seq);      /* seq 짝수 설정 */

/* 읽기 */
do {
    s = read_seqcount_begin(&seq);
    val = shared_data;
} while (read_seqcount_retry(&seq, s));
/* 쓰기 중이면 seq가 홀수 → retry 무한 재시도 가능 */

/* seqcount_latch — 쓰기 중에도 읽기 가능 */
/* 쓰기: 두 버퍼를 순차적으로 갱신 */
raw_write_seqcount_latch(&seq);  /* seq++ */
data[0] = new_val;               /* 읽기는 data[1] 사용 */
raw_write_seqcount_latch(&seq);  /* seq++ */
data[1] = new_val;               /* 읽기는 data[0] 사용 */
/* 읽기 측은 항상 "안전한" 버퍼를 읽으므로 재시도 최소화 */

SPSC 패턴 (relay, perf ring buffer)

SPSC 패턴의 특성

SPSC(Single Producer, Single Consumer)는 가장 단순한 lock-free 패턴입니다. 생산자와 소비자가 각각 하나이므로 CAS 루프조차 불필요하고, smp_store_release()/smp_load_acquire() 쌍만으로 동기화가 완료됩니다. 이는 wait-free 수준의 진행 보장을 제공합니다.

relay: 커널→사용자 공간 고속 데이터 전달

/* include/linux/relay.h */
struct rchan_buf {
    void            *start;         /* 매핑된 버퍼 시작 */
    void            *data;          /* 현재 쓰기 위치 */
    size_t          offset;         /* 현재 서브버퍼 내 오프셋 */
    size_t          subbufs_produced; /* 생산된 서브버퍼 수 */
    size_t          subbufs_consumed; /* 소비된 서브버퍼 수 (사용자) */
    /* ... */
};

/* 생산자 (커널): relay_write() */
/* 소비자 (사용자 공간): read() / mmap() + poll() */

relay channel 상세

/* relay: 대용량 커널→사용자 데이터 스트리밍 */
/* include/linux/relay.h */

/* relay 채널 생성 */
struct rchan *relay_open(const char *base_filename,
                          struct dentry *parent,
                          size_t subbuf_size,    /* 서브버퍼 크기 */
                          size_t n_subbufs,      /* 서브버퍼 수 */
                          struct rchan_callbacks *cb,
                          void *private_data);

/* 커널에서 데이터 쓰기 (SPSC: 해당 CPU에서만 쓰기) */
void relay_write(struct rchan *chan, const void *data, size_t length);
void __relay_write(struct rchan *chan, const void *data, size_t length);
/* __relay_write: preemption이 이미 비활성화된 경우 사용 */

/* 사용자 공간에서 읽기 */
/* debugfs 파일로 노출: /sys/kernel/debug/<base_filename>/cpu0 */
/* mmap() 또는 read()로 데이터 소비 */

/* relay의 SPSC 보장:
 * - 각 CPU에 별도의 per-CPU 버퍼
 * - 생산자: 해당 CPU의 커널 코드 (preempt_disable 하에)
 * - 소비자: 사용자 공간 프로세스 (read/mmap)
 * → CPU별 독립이므로 lock-free */

perf ring buffer 상세

io_uring SQ/CQ Ring

io_uring은 SQ(Submission Queue)와 CQ(Completion Queue) 두 개의 SPSC 링 버퍼를 사용합니다. SQ는 사용자(생산자)→커널(소비자), CQ는 커널(생산자)→사용자(소비자)로, 시스템 콜(System Call) 없이 mmap된 공유 메모리를 통해 비동기 I/O를 수행합니다.

/* io_uring SQ/CQ 링 버퍼 구조 */
struct io_rings {
    struct io_uring sq;     /* SQ 링: 사용자→커널 */
    struct io_uring cq;     /* CQ 링: 커널→사용자 */
    /* ... */
};

struct io_uring {
    u32 head;   /* 소비자가 갱신 */
    u32 tail;   /* 생산자가 갱신 */
};

/* 사용자 측 SQ 제출 (라이브러리, 커널 아닌 코드) */
void submit_sqe(struct io_uring *sq, struct io_uring_sqe *sqe)
{
    unsigned int tail = smp_load_acquire(&sq->tail);
    /* SQE 배열에 요청 기록 */
    sqes[tail & mask] = *sqe;
    smp_store_release(&sq->tail, tail + 1);
    /* → 커널이 새 SQE를 감지 */
}

/* 커널 측 CQ 완료 기록 */
void complete_cqe(struct io_rings *rings, struct io_uring_cqe *cqe)
{
    unsigned int tail = READ_ONCE(rings->cq.tail);
    cqes[tail & mask] = *cqe;
    smp_store_release(&rings->cq.tail, tail + 1);
    /* → 사용자가 새 CQE를 감지 */
}

BPF ring buffer

BPF ring buffer(BPF_MAP_TYPE_RINGBUF)는 eBPF 프로그램에서 사용자 공간으로 데이터를 전달하는 MPSC 링 버퍼입니다. 가변 길이 레코드를 지원하며, 여러 CPU의 BPF 프로그램이 동시에 쓸 수 있고 사용자 공간이 읽습니다.

/* BPF ring buffer 사용 (BPF 프로그램 측) */
struct {
    __uint(type, BPF_MAP_TYPE_RINGBUF);
    __uint(max_entries, 256 * 1024);  /* 256KB */
} events SEC(".maps");

/* BPF 프로그램에서 이벤트 전송 */
SEC("tp/sched/sched_process_exec")
int handle_exec(struct trace_event_raw_sched_process_exec *ctx)
{
    struct event *e;
    e = bpf_ringbuf_reserve(&events, sizeof(*e), 0);
    if (!e)
        return 0;

    e->pid = bpf_get_current_pid_tgid() >> 32;
    bpf_get_current_comm(&e->comm, sizeof(e->comm));

    bpf_ringbuf_submit(e, 0);
    /* 내부: smp_store_release로 레코드 공개 */
    return 0;
}

/* 사용자 공간에서 epoll + ring_buffer__poll()로 소비 */

perf ring buffer

perf_event 서브시스템의 링 버퍼는 SPSC lockless 패턴의 대표적 예입니다. 커널이 이벤트를 쓰고, 사용자 공간의 perf 도구가 mmap으로 직접 읽습니다. perf_event_mmap_page의 data_head/data_tail이 kfifo의 in/out과 동일한 역할을 합니다.

/* include/uapi/linux/perf_event.h */
struct perf_event_mmap_page {
    /* ... */
    __u64   data_head;  /* 쓰기 측(커널)이 갱신, smp_store_release */
    __u64   data_tail;  /* 읽기 측(사용자)이 갱신 */
    /* ... */
};

/* 커널 쓰기 측 — kernel/events/ring_buffer.c */
/* perf_output_put_handle():
 *   smp_store_release(&rb->user_page->data_head, head);
 */

/* 사용자 읽기 측 — tools/perf/util/mmap.c */
/* data_head를 읽어 새 데이터 확인
 * 처리 후 data_tail 갱신 */

percpu_ref: Lock-free 참조 카운팅

개요

percpu_ref는 고성능 lock-free 참조 카운팅 메커니즘입니다. 일반 atomic_t 기반 참조 카운팅은 모든 CPU가 같은 캐시라인을 경합하여 확장성이 떨어지지만, percpu_ref는 각 CPU가 로컬 카운터를 사용하므로 fast-path에서 캐시라인 바운싱이 없습니다. blk-mq, cgroup, io_uring, cgroupv2 등 핵심 서브시스템에서 사용됩니다.

/* include/linux/percpu-refcount.h */
struct percpu_ref {
    atomic_long_t           count;
    unsigned long           percpu_count_ptr; /* per-CPU 카운터 포인터 + 플래그 */
    percpu_ref_func_t       *release;
    percpu_ref_func_t       *confirm_switch;
    /* ... */
};

/* 핵심 API */
int percpu_ref_init(struct percpu_ref *ref,
                    percpu_ref_func_t *release, unsigned int flags,
                    gfp_t gfp);

/* fast-path: per-CPU 카운터 증감 → 캐시라인 경합 없음 */
void percpu_ref_get(struct percpu_ref *ref);
void percpu_ref_put(struct percpu_ref *ref);

/* kill: per-CPU → atomic 전환, 이후 0 도달 시 release 호출 */
void percpu_ref_kill(struct percpu_ref *ref);

상태 전이 상세: PERCPU → ATOMIC → DEAD

percpu_ref의 상태 전이는 RCU grace period를 활용한 정교한 프로토콜입니다. percpu_ref_kill() 호출 시 즉시 atomic 모드로 전환되는 것이 아니라, RCU grace period를 통해 모든 CPU가 atomic 모드를 인식한 후에 완료됩니다.

/* lib/percpu-refcount.c — percpu_ref_kill 내부 (단순화) */
void percpu_ref_kill_and_confirm(struct percpu_ref *ref,
                                  percpu_ref_func_t *confirm_kill)
{
    WARN_ONCE(ref->percpu_count_ptr & __PERCPU_REF_DEAD,
              "already killed");

    /* 1. DEAD 플래그 설정 — 새 get/put은 atomic 경로로 */
    ref->percpu_count_ptr |= __PERCPU_REF_DEAD;

    /* 2. confirm_switch 콜백 저장 */
    ref->confirm_switch = confirm_kill;

    /* 3. RCU 콜백 등록: GP 후 per-CPU → atomic 전환 완료 */
    call_rcu(&ref->data->rcu, percpu_ref_switch_to_atomic_rcu);
    /*
     * GP 완료 후:
     * - 모든 CPU의 per-CPU 카운터를 합산
     * - atomic_long에 합산값 저장
     * - per-CPU 카운터 해제
     * - confirm_kill 콜백 호출
     */
}

/* fast-path get/put — per-CPU 또는 atomic */
void percpu_ref_get(struct percpu_ref *ref)
{
    unsigned long __percpu *percpu_count;

    rcu_read_lock();
    if (likely(!(ref->percpu_count_ptr & __PERCPU_REF_DEAD))) {
        /* PERCPU 모드: per-CPU 카운터 증가 (초고속) */
        percpu_count = (unsigned long __percpu *)
                        ref->percpu_count_ptr;
        this_cpu_inc(*percpu_count);
    } else {
        /* ATOMIC 모드: 공유 atomic 카운터 증가 */
        atomic_long_inc(&ref->data->count);
    }
    rcu_read_unlock();
}

confirm_switch와 RCU grace period

percpu_ref_kill()의 confirm_kill 콜백은 per-CPU → atomic 전환이 완전히 완료된 후에 호출됩니다. 이 시점부터 percpu_ref_is_zero()의 결과가 정확해집니다.

커널 사용 사례 상세: blk-mq, cgroup, io_uring

/* block/blk-mq.c — request queue percpu_ref 사용 */
int blk_queue_enter(struct request_queue *q, blk_mq_req_flags_t flags)
{
    /* I/O 제출 시 queue 참조 획득 */
    if (!percpu_ref_tryget_live(&q->q_usage_counter)) {
        /* queue가 dying 상태 → I/O 거부 */
        if (flags & BLK_MQ_REQ_NOWAIT)
            return -EAGAIN;
        /* 또는 대기 */
        wait_event(q->mq_freeze_wq,
                   percpu_ref_tryget_live(&q->q_usage_counter));
    }
    return 0;
}

void blk_queue_exit(struct request_queue *q)
{
    /* I/O 완료 시 참조 반환 */
    percpu_ref_put(&q->q_usage_counter);
}

/* 디바이스 제거 시 */
void blk_freeze_queue(struct request_queue *q)
{
    percpu_ref_kill(&q->q_usage_counter);
    /* 모든 진행 중인 I/O가 완료(put)할 때까지 대기 */
    wait_event(q->mq_freeze_wq,
               percpu_ref_is_zero(&q->q_usage_counter));
    /* 이 시점에서 새 I/O 없고, 기존 I/O 모두 완료 → 안전하게 제거 */
}

커널 내 percpu_ref 사용 사례

Lock-free 해시 테이블 (RCU + 해시)

rhashtable: 자동 리사이징 RCU 해시 테이블

rhashtable은 Linux 커널의 범용 해시 테이블로, RCU 기반 lock-free 조회와 자동 리사이징(grow/shrink)을 지원합니다. 네트워크 소켓 관리, nftables 규칙, netlink, TIPC 등에서 사용됩니다. 버킷 단위 spinlock으로 삽입/삭제를 보호하되, 조회는 RCU만으로 lock-free입니다.

/* include/linux/rhashtable.h */
struct rhashtable {
    struct bucket_table __rcu   *tbl;
    unsigned int                key_len;
    unsigned int                max_elems;
    struct rhashtable_params    p;
    /* ... */
};

/* 핵심 API */
int rhashtable_init(struct rhashtable *ht, const struct rhashtable_params *params);
int rhashtable_insert_fast(struct rhashtable *ht, struct rhash_head *obj,
                           const struct rhashtable_params params);
void *rhashtable_lookup_fast(struct rhashtable *ht, const void *key,
                             const struct rhashtable_params params);
int rhashtable_remove_fast(struct rhashtable *ht, struct rhash_head *obj,
                           const struct rhashtable_params params);

rhashtable API 상세: init, insert, lookup, remove

/* rhashtable 사용 예: 간단한 키-값 저장소 */
struct my_entry {
    int key;
    char value[64];
    struct rhash_head node;    /* rhashtable 링크 */
    struct rcu_head rcu;       /* RCU 지연 해제용 */
};

static const struct rhashtable_params my_params = {
    .key_len     = sizeof(int),
    .key_offset  = offsetof(struct my_entry, key),
    .head_offset = offsetof(struct my_entry, node),
    .automatic_shrinking = true,
};

static struct rhashtable my_ht;

/* 초기화 */
int init_hashtable(void)
{
    return rhashtable_init(&my_ht, &my_params);
}

/* 삽입 — 버킷 lock 보호 */
int insert_entry(struct my_entry *e)
{
    return rhashtable_insert_fast(&my_ht, &e->node, my_params);
    /* 반환: 0 성공, -EEXIST 중복, -ENOMEM 메모리 부족 */
}

/* 조회 — RCU lock-free */
struct my_entry *lookup_entry(int key)
{
    return rhashtable_lookup_fast(&my_ht, &key, my_params);
    /* 내부: rcu_read_lock() + 해시 계산 + 체인 탐색 + rcu_read_unlock() */
}

/* 삭제 — 버킷 lock 보호 + RCU 지연 해제 */
int remove_entry(struct my_entry *e)
{
    int ret = rhashtable_remove_fast(&my_ht, &e->node, my_params);
    if (!ret)
        kfree_rcu(e, rcu);  /* grace period 후 해제 */
    return ret;
}

/* 정리 */
void cleanup_hashtable(void)
{
    rhashtable_destroy(&my_ht);
}

동적 리사이징과 RCU 마이그레이션

rhashtable의 자동 리사이징은 체인 길이가 임계값을 초과하면 트리거됩니다. 새 버킷 테이블을 할당하고, 기존 요소를 새 테이블로 재해시한 후, rcu_assign_pointer()로 새 테이블을 공개합니다.

rhashtable_walk_* 순회 API

/* rhashtable 안전한 순회 — rhashtable_walk API */
struct rhashtable_iter iter;

rhashtable_walk_enter(&my_ht, &iter);
rhashtable_walk_start(&iter);

while ((obj = rhashtable_walk_next(&iter)) != NULL) {
    if (IS_ERR(obj)) {
        if (PTR_ERR(obj) == -EAGAIN)
            continue;  /* 리사이징 중 — 재시도 */
        break;
    }
    process_entry(obj);
}

rhashtable_walk_stop(&iter);
rhashtable_walk_exit(&iter);

/* 주의사항:
 * - rhashtable_walk_next는 리사이징 중 -EAGAIN을 반환할 수 있음
 * - 순회 중 삽입/삭제가 발생할 수 있음 (일부 요소를 놓치거나 중복 볼 수 있음)
 * - 정확한 스냅샷이 필요하면 외부 lock 사용 */

rhashtable 설정 파라미터

/* include/linux/rhashtable-types.h */
struct rhashtable_params {
    u16                     nelem_hint;     /* 예상 요소 수 힌트 */
    u16                     key_len;        /* 키 길이 (바이트) */
    u16                     key_offset;     /* 구조체 내 키 오프셋 */
    u16                     head_offset;    /* 구조체 내 rhash_head 오프셋 */
    unsigned int            max_size;       /* 최대 버킷 수 */
    u16                     min_size;       /* 최소 버킷 수 */
    bool                    automatic_shrinking; /* 자동 축소 활성화 */
    rht_hashfn_t            hashfn;         /* 커스텀 해시 함수 */
    rht_obj_hashfn_t        obj_hashfn;     /* 객체 해시 함수 */
    rht_obj_cmpfn_t         obj_cmpfn;      /* 객체 비교 함수 */
};

/* 사용 예: nftables 규칙 해시 테이블 */
static const struct rhashtable_params nft_set_rhash_params = {
    .nelem_hint     = 256,
    .head_offset    = offsetof(struct nft_set_elem, node),
    .key_offset     = offsetof(struct nft_set_elem, key),
    .key_len        = sizeof(struct nft_set_key),
    .automatic_shrinking = true,
};

rhashtable 조회 성능 특성

커널 내 rhashtable 사용 사례

메모리 회수 전략 (RCU, Hazard Pointer 개념)

Lock-free의 핵심 과제: 안전한 메모리 회수

Lock-free 자료구조에서 가장 어려운 문제는 “언제 제거된 노드의 메모리를 안전하게 해제할 수 있는가”입니다. 노드를 자료구조에서 제거한 순간에도 다른 CPU가 여전히 해당 노드를 참조하고 있을 수 있기 때문입니다.

RCU 기반 회수 상세: call_rcu, kfree_rcu, SLAB_TYPESAFE_BY_RCU

refcount 기반 회수: percpu_ref와 kref

/* kref: 단순 참조 카운팅 (atomic_t 기반) */
#include <linux/kref.h>

struct my_object {
    struct kref ref;
    char name[64];
    /* ... */
};

void my_object_free(struct kref *ref)
{
    struct my_object *obj = container_of(ref, struct my_object, ref);
    kfree(obj);
}

/* 참조 획득 */
kref_get(&obj->ref);

/* 참조 해제 — 0이 되면 my_object_free 호출 */
kref_put(&obj->ref, my_object_free);

/* kref vs percpu_ref 선택 기준:
 * - 낮은 경합 (수십 CPU 이하): kref가 단순하고 충분
 * - 높은 경합 (수백 CPU, hot path): percpu_ref 필수
 * - hot-path get/put + cold-path kill: percpu_ref 설계에 최적 */

RCU 기반 메모리 회수 패턴

/* 전형적인 RCU 기반 노드 제거 + 지연 해제 */

/* 제거 측 (lock 보호 하에) */
spin_lock(&list_lock);
old = rcu_dereference_protected(head, lockdep_is_held(&list_lock));
rcu_assign_pointer(head, old->next);
spin_unlock(&list_lock);

/* 지연 해제 — 방법 1: synchronize_rcu + kfree */
synchronize_rcu();  /* 모든 RCU 읽기 측 완료 대기 (슬립 가능) */
kfree(old);

/* 지연 해제 — 방법 2: call_rcu (비동기) */
call_rcu(&old->rcu_head, my_free_callback);

/* 지연 해제 — 방법 3: kfree_rcu (가장 간편) */
kfree_rcu(old, rcu_head);  /* grace period 후 자동 kfree */

RCU grace period 내부 동작

RCU grace period는 “모든 CPU가 최소 한 번 퀴센트 상태(quiescent state)를 통과했음”을 감지합니다. 퀴센트 상태란 CPU가 RCU 읽기 측 임계 구역에 있지 않은 상태로, 컨텍스트 스위치, 사용자 공간 진입, idle 상태 진입 등이 해당합니다.

/* RCU grace period 타임라인 */
/*
 * CPU 0: rcu_read_lock() ... [데이터 참조 중] ... rcu_read_unlock()
 * CPU 1: rcu_read_lock() .............. rcu_read_unlock()
 * CPU 2: (idle)
 *
 * 제거 측: list_del_rcu(node) → call_rcu(&node->rcu, free_fn)
 *          |---- grace period ----|
 *          모든 CPU가 QS 통과 후 free_fn(node) 호출
 */

/* TREE RCU 계층 구조 (대규모 NUMA 시스템) */
struct rcu_state {
    struct rcu_node *level[RCU_NUM_LVLS]; /* 계층 트리 */
    /* 루트 노드에서 모든 CPU의 QS 통과를 추적 */
};

/* 각 CPU의 퀴센트 상태 보고 */
struct rcu_data {
    unsigned long   ticks_this_gp;    /* 이 GP 동안 경과한 틱 */
    bool            beenonline;       /* 온라인 상태 확인 */
    struct rcu_head *nxtlist;         /* 대기 중인 콜백 리스트 */
    /* ... */
};

Hazard Pointer 개념과 커널 적용 가능성

Hazard Pointer(Michael, 2004)는 사용자 공간 lock-free 프로그래밍에서 메모리 회수의 표준 기법입니다. Linux 커널에서는 RCU가 같은 역할을 하므로 Hazard Pointer를 사용하지 않지만, 개념 이해는 RCU의 설계 철학을 더 깊이 이해하는 데 도움이 됩니다.

Hazard Pointer 알고리즘 상세 (사용자 공간 비교)

Hazard Pointer는 사용자 공간 lock-free 프로그래밍에서 메모리 회수에 사용되는 기법으로, 각 스레드가 현재 참조 중인 포인터를 글로벌 배열에 공개합니다. 해제 측은 이 배열을 스캔하여 어떤 스레드도 참조하지 않는 포인터만 해제합니다. Linux 커널에서는 RCU가 이를 대체하므로 Hazard Pointer를 사용하지 않지만, 개념 이해는 lock-free 메모리 회수 전반을 이해하는 데 도움이 됩니다.

/* Hazard Pointer 개념 (의사 코드, 커널에서는 미사용) */
/* 읽기 측 */
retry:
    hp[tid] = READ(head);           /* 내가 참조 중인 포인터 공개 */
    if (hp[tid] != READ(head))      /* 공개 후 변경 확인 */
        goto retry;
    /* 이제 hp[tid]가 가리키는 노드는 해제되지 않음 */
    use(hp[tid]);
    hp[tid] = NULL;                 /* 참조 해제 */

/* 해제 측 */
    retired_list.add(old_node);
    if (retired_list.size() > threshold) {
        scan(hp[]);                 /* 모든 스레드의 HP 스캔 */
        for (node in retired_list)
            if (node not in any hp[])
                free(node);         /* 안전하게 해제 */
    }

SLAB_TYPESAFE_BY_RCU: 특수 메모리 회수

SLAB_TYPESAFE_BY_RCU 플래그로 생성된 slab 캐시는 객체가 해제되어도 해당 메모리 페이지가 grace period 동안 다른 slab으로 재할당되지 않습니다. 이를 통해 lock-free 코드에서 객체의 타입 안전성을 보장하면서 메모리를 재활용할 수 있습니다. 네트워크 소켓(struct sock), 파일 시스템 inode 등에서 사용됩니다.

/* SLAB_TYPESAFE_BY_RCU 사용 예 */
static struct kmem_cache *my_cache;

my_cache = kmem_cache_create("my_objects",
                             sizeof(struct my_obj),
                             0, SLAB_TYPESAFE_BY_RCU,
                             NULL);

/* 조회 패턴 — RCU 보호 하에 객체 검증 */
rcu_read_lock();
obj = find_in_hashtable(key);     /* RCU로 보호된 조회 */
if (obj) {
    /* 객체가 해제+재할당되었을 수 있으므로 키 재검증 필수 */
    if (obj->key != key) {
        obj = NULL;               /* 다른 객체로 재할당됨 */
    }
}
rcu_read_unlock();

Lock-free vs Fine-grained Locking 트레이드오프

언제 lock-free를 사용해야 하는가?

Lock-free 자료구조는 만능이 아닙니다. 특정 조건에서만 lock 기반 대비 이점이 있으며, 잘못된 상황에서의 lock-free 사용은 복잡성만 증가시키고 성능 이점은 미미합니다.

Lock-free를 선택해야 할 때

Fine-grained Locking이 나은 경우

다음 상황에서는 lock-free보다 fine-grained locking이 더 적합합니다:

• 복잡한 다단계 갱신: 여러 필드를 원자적으로 갱신해야 할 때 (lock이 트랜잭션(Transaction) 경계를 명확히 정의)
• 낮은 경합: CPU 수가 적거나 접근 빈도가 낮으면 spinlock 비용이 무시 가능
• 디버깅 우선: lockdep으로 교착 상태(Deadlock)를 자동 감지할 수 있어 유지보수가 용이
• 역방향 호환성: 기존 lock 기반 코드와 상호작용이 필요한 경우

/* Fine-grained locking 예: per-bucket hash table lock */
struct my_hashtable {
    struct hlist_head    *buckets;
    spinlock_t           *locks;     /* per-bucket lock */
    unsigned int         size;
};

/* 조회: 해당 버킷만 lock → 다른 버킷과 병렬 처리 가능 */
struct my_entry *lookup(struct my_hashtable *ht, u32 key)
{
    unsigned int idx = hash_32(key, ilog2(ht->size));
    struct my_entry *e;

    spin_lock(&ht->locks[idx]);
    hlist_for_each_entry(e, &ht->buckets[idx], node) {
        if (e->key == key) {
            spin_unlock(&ht->locks[idx]);
            return e;
        }
    }
    spin_unlock(&ht->locks[idx]);
    return NULL;
    /* 버킷 수가 충분하면 경합이 거의 없어 lock-free와 성능 유사 */
}

복잡도와 유지보수 비용 분석

성능 분석과 캐시라인 고려사항

캐시라인 바운싱 문제

Lock-free 자료구조의 성능을 결정하는 가장 중요한 요소는 캐시라인 바운싱(cache-line bouncing)입니다. 여러 CPU가 같은 캐시라인의 데이터를 원자적으로 수정하면, 해당 캐시라인이 CPU 간에 반복적으로 전송(MESI 프로토콜의 Invalidate/Transfer)되어 성능이 급격히 저하됩니다.

False Sharing 문제와 해결

False sharing은 서로 다른 CPU가 다른 변수를 접근하지만, 해당 변수들이 같은 캐시라인에 위치하여 불필요한 캐시라인 무효화가 발생하는 현상입니다. Lock-free 자료구조에서 생산자/소비자 인덱스가 같은 캐시라인에 있으면 심각한 성능 저하를 유발합니다.

____cacheline_aligned_in_smp 상세

/* include/linux/cache.h */
#ifdef CONFIG_SMP
#define ____cacheline_aligned_in_smp ____cacheline_aligned
/* ____cacheline_aligned: __attribute__((aligned(L1_CACHE_BYTES)))
 * L1_CACHE_BYTES: x86=64, ARM64=64 또는 128 */
#else
#define ____cacheline_aligned_in_smp
/* UP 시스템에서는 정렬 불필요 → 메모리 절약 */
#endif

/* 사용 예: ptr_ring의 캐시라인 분리 */
struct ptr_ring {
    int producer ____cacheline_aligned_in_smp;
    spinlock_t producer_lock;
    /* — 캐시라인 경계 — */
    int consumer_head ____cacheline_aligned_in_smp;
    int consumer_tail;
    spinlock_t consumer_lock;
    /* — 캐시라인 경계 — */
    int size ____cacheline_aligned_in_smp;
    int batch;
    void **queue;
    /* size, batch, queue는 거의 변경되지 않는 읽기 전용 데이터 */
};

/* ____cacheline_aligned 사용 시 구조체 크기 증가 주의 */
/* ptr_ring: 최소 3 × 64 = 192 bytes (캐시라인 정렬 패딩) */
/* 정렬 없으면: ~48 bytes */
/* → 메모리 4배 증가, 성능 수십 배 향상 (고경합 시) */

prefetch 힌트와 Lock-free 구조

/* prefetch: CPU 캐시에 데이터를 미리 로드하는 힌트 */
#include <linux/prefetch.h>

/* lock-free 연결 리스트 순회 시 prefetch 활용 */
llist_for_each_entry(item, list, node) {
    prefetch(item->node.next);  /* 다음 노드를 미리 캐시에 로드 */
    process(item);
    /* 다음 반복에서 캐시 미스 없이 node.next 접근 가능 */
}

/* rhashtable 체인 순회 시 */
rht_for_each_entry_rcu(entry, pos, tbl, hash, node) {
    prefetch(pos->next);
    if (entry->key == search_key)
        return entry;
}

/* prefetch_write: 쓰기 의도 prefetch
 * — 해당 캐시라인을 Exclusive 상태로 가져옴
 * — 이후 쓰기 시 Invalidate 전송 불필요 */
prefetchw(&next_node->data);  /* 쓰기 전 prefetch */

캐시라인 정렬 기법

/* ____cacheline_aligned_in_smp: SMP에서만 캐시라인 정렬 */
struct hot_data {
    atomic_long_t   read_counter ____cacheline_aligned_in_smp;
    /* 읽기 전용 경로에서 접근하는 필드 */

    spinlock_t      write_lock ____cacheline_aligned_in_smp;
    /* 쓰기 경로에서 접근하는 필드 */
};

/* __read_mostly: 읽기 전용 섹션에 배치 */
static int config_value __read_mostly = DEFAULT_VALUE;

/* per-CPU 변수로 false sharing 완전 제거 */
static DEFINE_PER_CPU(unsigned long, my_counter);

아키텍처별 원자적 연산 비용

아키텍처별 메모리 모델과 CAS 구현

원자적 연산의 비용은 아키텍처마다 크게 다릅니다. x86은 TSO(Total Store Order) 모델로 대부분의 배리어가 no-op이지만 LOCK 접두사 비용이 있습니다. ARM은 약한 순서 모델이지만 ARMv8.1에서 LSE(Large System Extension) 원자 명령을 도입하여 LL/SC 루프 대비 성능이 크게 향상되었습니다.

x86 원자적 연산 비용: LOCK prefix와 MESI

x86에서 원자적 RMW 연산은 LOCK 접두사로 구현됩니다. LOCK은 해당 캐시라인에 배타적(Exclusive) 소유권을 획득하고, 연산 완료까지 다른 CPU의 접근을 차단합니다. 최신 x86 프로세서는 캐시라인이 이미 Exclusive/Modified 상태이면 버스(Bus) 락 없이 캐시 락만으로 처리합니다.

/* x86 LOCK 접두사의 실제 비용 분석 */
/* 시나리오 1: 비경합 (캐시라인이 이미 Exclusive) */
LOCK CMPXCHG [mem], reg  /* ~15-30 사이클 */
/* 캐시 락만 사용: 버스 트래픽 없음 */

/* 시나리오 2: 경합 (캐시라인이 다른 CPU의 Modified) */
LOCK CMPXCHG [mem], reg  /* ~40-200+ 사이클 */
/* MESI 프로토콜:
 * 1. 현재 CPU가 Invalidate 요청 전송
 * 2. 소유자 CPU가 캐시라인 플러시 + 전송
 * 3. 현재 CPU가 Exclusive 획득 후 연산
 * → NUMA 노드 간: 200+ 사이클 (QPI/UPI 레이턴시) */

/* 시나리오 3: TSO 모델의 암묵적 배리어 */
smp_wmb();  /* x86: no-op (TSO가 store-store 순서 보장) */
smp_rmb();  /* x86: no-op (TSO가 load-load 순서 보장) */
smp_mb();   /* x86: MFENCE 또는 LOCK ADD [rsp], 0 */
/* → x86에서 lock-free 코드가 ARM보다 단순한 이유 */

ARM64: LL/SC vs LSE (CASP)

ARM64는 ARMv8.0까지 LL/SC(Load-Linked/Store-Conditional) 기반 원자 연산을 사용했으나, ARMv8.1의 LSE(Large System Extension)에서 단일 원자 명령(CAS, SWP, LDADD 등)을 도입했습니다. 서버 워크로드에서 LSE는 LL/SC 대비 최대 10배 성능을 제공합니다.

/* ARM64 커널의 LL/SC → LSE 자동 전환 메커니즘 */
/* arch/arm64/include/asm/atomic_lse.h */

/* 커널 빌드 시 대체 명령 생성 (alternative patching) */
/* 부팅 시 CPU가 LSE를 지원하면 LL/SC를 LSE로 패치 */

/* CONFIG_ARM64_LSE_ATOMICS 설정 시 동작:
 * 1. 빌드: LL/SC 코드 + LSE 대안 코드 모두 포함
 * 2. 부팅: cpufeature 검출 → LSE 지원 시 코드 패치
 * 3. 런타임: LSE 단일 명령 실행 */

/* CASP: 더블 CAS (16바이트 원자적 교체) */
/* ARMv8.1 LSE CASP 예: tagged pointer ABA 방지 */
/* CASP Xs, Xt, Xn, Xm, [Xp]
 * Xs:Xt = expected pair
 * Xn:Xm = desired pair
 * [Xp] = memory location (16-byte aligned) */

RISC-V: LR/SC, Zacas, Zabha

RISC-V는 기본적으로 LR/SC(Load-Reserved/Store-Conditional)와 AMO(Atomic Memory Operations)를 제공합니다. 최신 확장인 Zacas(Compare-and-Swap)와 Zabha(Byte/Half-word AMO)는 더 효율적인 원자 연산을 지원합니다.

/* RISC-V LR/SC 기반 cmpxchg (현재 커널 구현) */
/* arch/riscv/include/asm/cmpxchg.h (단순화) */
#define __cmpxchg(ptr, old, new, size)              \
({                                                   \
    __typeof__(ptr) __ptr = (ptr);                   \
    __typeof__(old) __old = (old);                   \
    __typeof__(new) __new = (new);                   \
    __typeof__(*(ptr)) __ret;                        \
    switch (size) {                                  \
    case 8:                                          \
        __asm__ __volatile__(                        \
            "1: lr.d %0, %2\n"        /* Load-Reserved */  \
            "   bne  %0, %z3, 2f\n"   /* 비교 */          \
            "   sc.d %1, %z4, %2\n"    /* Store-Conditional */ \
            "   bnez %1, 1b\n"         /* SC 실패 → 재시도 */ \
            "2:"                                     \
            : "=&r"(__ret), "=&r"(tmp), "+A"(*__ptr) \
            : "rJ"(__old), "rJ"(__new));             \
        break;                                       \
    }                                                \
    __ret;                                           \
})

/* Zacas 확장이 있으면 단일 명령으로 대체 가능:
 * AMOCAS.D rd, rs2, (rs1)  → CAS 단일 명령
 * → LR/SC 루프 제거, 라이브락 방지 */

LL/SC vs 단일 원자 명령

/* ARM64 pre-LSE: cmpxchg LL/SC 루프 */
__cmpxchg_case_##name:
1:  ldxr    x0, [x2]           /* Load-Exclusive */
    cmp     x0, x3             /* 비교 */
    b.ne    2f
    stxr    w1, x4, [x2]       /* Store-Exclusive */
    cbnz    w1, 1b             /* 실패 시 재시도 */
2:  ret

/* ARM64 LSE: 단일 CAS 명령 */
__cmpxchg_case_##name:
    cas     x3, x4, [x2]       /* 단일 원자 명령, 재시도 불필요 */
    mov     x0, x3
    ret

/* LL/SC의 문제: 경합이 높으면 STXR 실패율 급증
 * → 라이브락(livelock) 가능성
 * LSE CAS는 하드웨어가 원자성 보장 → 라이브락 없음 */

커널 서브시스템별 활용 사례

네트워킹

네트워킹은 Linux 커널에서 lock-free 자료구조를 가장 많이 사용하는 서브시스템입니다. 패킷 처리는 마이크로초 단위 지연이 요구되며, softirq 컨텍스트에서 수행되므로 lock 비용을 최소화해야 합니다.

네트워킹 Lock-free 경로 상세

/* 네트워킹 패킷 수신 fast path — lock-free 연쇄 */
/*
 * 1. NIC IRQ → NAPI 스케줄: per-CPU, lock 없음
 * 2. NAPI poll → page_pool: ptr_ring에서 페이지 소비 (lock-free)
 * 3. skb 할당: SLUB fast-path cmpxchg (lock-free)
 * 4. 소켓 해시 조회: rhashtable RCU (lock-free)
 * 5. 소켓 큐 삽입: per-socket spinlock (유일한 lock)
 *
 * 5단계 중 4단계가 lock-free → 패킷 처리 대부분 무대기
 */

/* net/core/dev.c — NAPI 스케줄링 (lock-free) */
void napi_schedule(struct napi_struct *n)
{
    /* test_and_set_bit: 원자적 비트 연산 (lock-free) */
    if (!test_and_set_bit(NAPI_STATE_SCHED, &n->state))
        __napi_schedule(n);
}

/* net/ipv4/udp.c — UDP 소켓 조회 (RCU lock-free) */
struct sock *__udp4_lib_lookup(struct net *net, __be32 saddr,
                                __be16 sport, __be32 daddr,
                                __be16 dport, ...)
{
    struct udp_hslot *hslot;
    struct sock *sk;

    /* RCU 보호 하에 rhashtable에서 소켓 조회 */
    hslot = udp_hashslot(udptable, net, hnum);
    sk_for_each_rcu(sk, &hslot->head) {
        if (udp_match(sk, saddr, sport, daddr, dport))
            return sk;
    }
    return NULL;
    /* lock 없이 소켓 조회 완료! */
}

블록 I/O

/* block/blk-mq.c — 완료 경로에서 llist 사용 */
/* IRQ 핸들러에서 완료된 요청을 llist에 추가 */
static void blk_mq_raise_softirq(struct request *rq)
{
    struct blk_mq_ctx *ctx = rq->mq_ctx;
    /* llist_add: lock-free, IRQ-safe */
    if (llist_add(&rq->ipi_list, &ctx->llist))
        raise_softirq_irqoff(BLOCK_SOFTIRQ);
}

/* blk-mq에서 percpu_ref 사용 */
struct request_queue {
    struct percpu_ref       q_usage_counter;
    /* request queue 수명 관리 */
};

스케줄러

CFS 스케줄러는 직접적인 lock-free 자료구조보다는 per-CPU runqueue + spinlock 패턴을 사용하지만, load balancing 통계 수집에서 seqcount를 활용합니다.

/* kernel/sched/core.c — per-CPU runqueue */
struct rq {
    raw_spinlock_t          __lock;
    unsigned int            nr_running;
    struct cfs_rq           cfs;
    /* ... */
};
/* 각 CPU가 자기 rq만 수정 → 사실상 lock-free 접근 */
/* 다른 CPU의 rq를 읽을 때 seqcount로 일관성 보장 */

io_uring Lock-free 설계 상세

/* io_uring: 사용자-커널 공유 SPSC 링 버퍼 */
/* Submission Queue (SQ): 사용자 생산 → 커널 소비 */
/* Completion Queue (CQ): 커널 생산 → 사용자 소비 */
/* 동기화: smp_store_release/smp_load_acquire 쌍 */
/* → 시스템 콜 오버헤드 없는 비동기 I/O */

/* io_uring의 lock-free 기법 조합:
 *
 * 1. SQ/CQ 링 버퍼: SPSC lockless (kfifo 패턴)
 * 2. io_kiocb 할당: percpu 캐시 + slab (lock-free fast path)
 * 3. 파일 테이블 조회: RCU (lock-free)
 * 4. io_uring 컨텍스트 수명: percpu_ref (lock-free)
 * 5. 취소 요청 해시: xarray (RCU lock-free 읽기)
 */

/* io_uring SQ 제출 경로 (커널 측, 단순화) */
static int io_submit_sqes(struct io_ring_ctx *ctx, unsigned int nr)
{
    unsigned int head;

    /* SQ ring에서 SQE 인덱스 읽기 */
    head = READ_ONCE(ctx->sq_ring->head);
    /* smp_load_acquire: 사용자가 쓴 SQE 데이터가 보이는지 확인 */

    for (int i = 0; i < nr; i++) {
        unsigned int idx = ctx->sq_array[head & ctx->sq_mask];
        struct io_uring_sqe *sqe = &ctx->sq_sqes[idx];

        /* SQE 처리 ... */
        head++;
    }

    /* 소비 완료 알림 */
    smp_store_release(&ctx->sq_ring->head, head);
    return nr;
}

메모리 관리 (mm)

메모리 관리 서브시스템은 lock-free 기법을 광범위하게 활용합니다. 특히 페이지 할당자(Page Allocator)의 per-CPU 프리리스트, SLUB 할당자의 fast-path, 그리고 페이지 캐시의 xarray 조회가 대표적입니다.

/* mm/slub.c — SLUB 할당자 fast-path (lock-free) */
/* kmalloc fast-path: per-CPU 프리리스트에서 cmpxchg로 할당 */
static __always_inline void *__slab_alloc_node(struct kmem_cache *s,
                                                gfp_t gfpflags, int node)
{
    void *object;
    struct kmem_cache_cpu *c;

    c = raw_cpu_ptr(s->cpu_slab);
redo:
    object = c->freelist;
    if (unlikely(!object)) {
        /* slow-path: 새 slab 필요 */
        return __slab_alloc(s, gfpflags, node, addr, c);
    }
    /* cmpxchg 기반 lock-free 할당 */
    if (unlikely(!this_cpu_cmpxchg_double(
            s->cpu_slab->freelist, s->cpu_slab->tid,
            object, tid,
            get_freepointer(s, object), next_tid(tid))))
        goto redo;

    return object;
}

/* mm/page_alloc.c — per-CPU 페이지 할당자 */
/* 각 CPU가 로컬 pcp (per_cpu_pages) 리스트에서 페이지 할당
 * → spinlock 없이 로컬 리스트 접근 (preempt_disable만) */
struct per_cpu_pages {
    spinlock_t lock;        /* drain 시에만 사용 */
    int count;              /* 현재 페이지 수 */
    int high;               /* high watermark */
    int batch;              /* 배치 크기 */
    short free_factor;
    struct list_head lists[NR_PCP_LISTS];
};

파일 시스템

/* fs/dcache.c — dentry 캐시 RCU-walk 경로명 조회 */
/* RCU-walk: lock 없이 경로를 탐색하는 optimistic 방식 */
static int lookup_fast(struct nameidata *nd, ...)
{
    struct dentry *dentry, *parent = nd->path.dentry;
    /* RCU 보호 하에 d_lookup_rcu() */
    dentry = __d_lookup_rcu(parent, &nd->last, &seq);
    if (!dentry) {
        /* 실패 시 ref-walk (lock 기반)로 폴백 */
        return -ECHILD;
    }
    /* seqcount로 dentry 일관성 검증 */
    if (read_seqcount_retry(&dentry->d_seq, seq))
        return -ECHILD;
    /* 성공: lock 없이 dentry 찾음 */
    return 0;
}
/* RCU-walk 성공률: 일반 워크로드에서 95% 이상
 * → 대부분의 경로명 조회가 lock-free로 완료 */

메모리 관리 Lock-free 기법

/* SLUB 할당자의 Lock-free fast path 상세 */
/* mm/slub.c — kmalloc fast path (단순화) */
static __always_inline void *slab_alloc_node(struct kmem_cache *s,
                                              struct list_lru *lru,
                                              gfp_t gfpflags, int node,
                                              unsigned long addr, size_t orig_size)
{
    void *object;
    struct kmem_cache_cpu *c;
    unsigned long tid;

    /* per-CPU 슬랩에서 lock-free 할당 시도 */
redo:
    c = raw_cpu_ptr(s->cpu_slab);
    tid = READ_ONCE(c->tid);
    barrier();

    object = c->freelist;
    if (unlikely(!object || !node_match(c, node)))
        return __slab_alloc(s, gfpflags, node, addr, c, orig_size);

    /*
     * cmpxchg_double: freelist와 tid를 동시에 원자적으로 교체
     * - freelist를 다음 free 객체로 전진
     * - tid를 증가시켜 ABA 방지
     * - 하나의 원자적 연산으로 두 값을 교체
     */
    void *next_object = get_freepointer_safe(s, object);
    if (unlikely(!this_cpu_cmpxchg_double(
            s->cpu_slab->freelist, s->cpu_slab->tid,
            object, tid,
            next_object, next_tid(tid))))
        goto redo;
    /* cmpxchg_double 실패 = 다른 컨텍스트가 끼어듦 → 재시도
     * 성공 = lock 없이 객체 할당 완료! */

    return object;
}

/* 핵심: cmpxchg_double은 freelist + tid 16바이트를 원자적으로 교체
 * → tid가 세대 카운터 역할 → 같은 freelist 주소라도 tid가 다르면 실패
 * → ABA 문제 방지 without RCU */

트레이싱 (ftrace, perf)

/* kernel/trace/ring_buffer.c — ftrace 링 버퍼 */
/* per-CPU SPSC 링 버퍼: 커널 트레이스 이벤트 기록 */
struct ring_buffer_per_cpu {
    struct ring_buffer  *buffer;
    raw_spinlock_t      reader_lock;  /* 읽기 측만 사용 */
    unsigned long       head_page;    /* 읽기 헤드 */
    unsigned long       tail_page;    /* 쓰기 테일 */
    local_t             entries;      /* per-CPU 로컬 카운터 */
    local_t             overrun;
    /* ... */
};

/* 쓰기 측: local_add() — per-CPU 원자적, 캐시라인 경합 없음 */
/* 페이지 전환 시에만 cmpxchg 사용 */
/* 읽기 측: reader_lock으로 단일 읽기자 보장 → SPSC */

Lock-free 자료구조 검증 (LKMM, litmus test)

Linux Kernel Memory Model (LKMM)

LKMM은 Linux 커널의 메모리 순서 의미론을 수학적으로 정의한 형식 모델입니다. herd7 도구와 함께 사용하여 lock-free 코드의 정확성을 기계적으로 검증할 수 있습니다. LKMM은 커널 소스 트리의 tools/memory-model/에 포함되어 있습니다.

LKMM 모델 상세: cat files와 herd7

LKMM은 .cat 형식의 axiom 파일로 정의되며, herd7 도구가 이를 해석합니다. 커널의 메모리 접근 원시 연산(READ_ONCE, WRITE_ONCE, smp_store_release 등)의 의미론을 수학적 관계(po, rf, co, fr)로 정의합니다.

/* LKMM의 핵심 관계 (tools/memory-model/linux-kernel.cat 기반) */
/*
 * po (program-order): 같은 스레드 내 명령 순서
 * rf (reads-from): 어떤 쓰기가 어떤 읽기에 값을 제공
 * co (coherence-order): 같은 위치에 대한 쓰기의 총 순서
 * fr (from-reads): 읽기가 관찰한 쓰기 이후의 쓰기
 *
 * 파생 관계:
 * hb (happens-before): 전통적 인과 순서
 * pb (propagation-before): 전파 순서
 * ppo (preserved program order): 보존된 프로그램 순서
 *
 * LKMM이 금지하는 사이클:
 * - hb 사이클 → 인과성 위반
 * - pb 사이클 → 전파 순서 위반
 */

litmus test 작성법

litmus test는 두 개 이상의 스레드가 공유 변수에 접근하는 시나리오를 정의하고, 특정 결과가 관찰 가능한지(exists)를 검증합니다.

/* litmus test 구조 */
C TEST_NAME           /* 언어: C (Linux 커널 의미론) */

{                     /* 초기 상태 */
  x = 0;              /* 공유 변수 초기값 */
  y = 0;
}

P0(int *x, int *y)    /* 스레드 0 */
{
    /* 메모리 접근 시퀀스 */
    WRITE_ONCE(*x, 1);
    smp_store_release(y, 1);
}

P1(int *x, int *y)    /* 스레드 1 */
{
    int r0;
    int r1;
    r0 = smp_load_acquire(y);
    r1 = READ_ONCE(*x);
}

exists (1:r0=1 /\ 1:r1=0)
/* 조건: P1이 y=1을 보면서 x=0을 볼 수 있는가?
 * Never → release/acquire가 올바르게 순서 보장
 * Sometimes → 배리어 부족 또는 모델 위반 */

/* 사용 가능한 커널 원시 연산:
 * READ_ONCE, WRITE_ONCE
 * smp_load_acquire, smp_store_release
 * smp_rmb, smp_wmb, smp_mb
 * xchg, xchg_acquire, xchg_release
 * cmpxchg, cmpxchg_acquire, cmpxchg_release
 * spin_lock, spin_unlock
 * rcu_read_lock, rcu_read_unlock, synchronize_rcu
 * rcu_dereference, rcu_assign_pointer
 */

KCSAN으로 Lock-free 코드 검증

KCSAN(Kernel Concurrency Sanitizer)은 컴파일 시점에 메모리 접근에 계측(instrumentation)을 삽입하여, 런타임에 READ_ONCE()/WRITE_ONCE()가 없는 병렬 접근(data race)을 감지합니다. Lock-free 코드에서 실수로 plain access를 사용한 경우를 잡아냅니다.

/* KCSAN이 감지하는 전형적인 lock-free 버그 */

/* 버그 1: WRITE_ONCE 누락 */
/* 쓰기 측 */
shared_var = new_val;        /* ← KCSAN 경고: data-race! */
/* 수정: WRITE_ONCE(shared_var, new_val); */

/* 버그 2: READ_ONCE 누락 */
/* 읽기 측 */
val = shared_var;            /* ← KCSAN 경고: data-race! */
/* 수정: val = READ_ONCE(shared_var); */

/* 버그 3: 컴파일러가 plain 접근을 합치는 문제 */
if (shared_flag)             /* 컴파일러가 두 번 로드할 수 있음 */
    use(shared_data);        /* TOCTOU 레이스! */
/* 수정: if (READ_ONCE(shared_flag)) ... */

/* KCSAN 의도적 무시 (정당한 데이터 레이스) */
/* data_race() 매크로로 감싸기 */
val = data_race(shared_counter);  /* 통계 카운터 등 */
/* → "이 레이스는 의도적이며 무해함"을 표시 */

litmus test 작성과 실행

/* tools/memory-model/litmus-tests/MP+pooncerelease+poacquireonce.litmus */
C MP+pooncerelease+poacquireonce

{} /* 초기 상태: x=0, y=0 */

P0(int *x, int *y)
{
    WRITE_ONCE(*x, 1);
    smp_store_release(y, 1);
}

P1(int *x, int *y)
{
    int r0;
    int r1;

    r0 = smp_load_acquire(y);
    r1 = READ_ONCE(*x);
}

exists (1:r0=1 /\ 1:r1=0)
/* 결과: Never — release/acquire 쌍이 순서 보장 */

# herd7으로 litmus test 실행
cd tools/memory-model/
herd7 -conf linux-kernel.cfg litmus-tests/MP+pooncerelease+poacquireonce.litmus

# 결과 예시:
# Test MP+pooncerelease+poacquireonce Allowed
# States 3
# 1:r0=0; 1:r1=0;
# 1:r0=0; 1:r1=1;
# 1:r0=1; 1:r1=1;
# No
# Witnesses
# Positive: 0 Negative: 3
# Condition exists (1:r0=1 /\ 1:r1=0)
# Observation MP+pooncerelease+poacquireonce Never 0 3

lockdep와 lock-free 코드의 관계

lockdep은 lock 기반 동기화의 정확성을 검증하지만, lock-free 코드에는 직접 적용되지 않습니다. 그러나 RCU 기반 lock-free 코드에서 rcu_dereference_protected()의 lockdep_is_held() 어서션을 활용하여 쓰기 측의 lock 보호를 검증할 수 있습니다.

/* lockdep으로 RCU 쓰기 측 보호 검증 */
/* 읽기 측 (lock-free) */
node = rcu_dereference(head);  /* RCU 읽기 보호 */

/* 쓰기 측 (lock 보호 확인) */
node = rcu_dereference_protected(head,
    lockdep_is_held(&my_lock));
/* my_lock을 잡지 않고 호출하면 lockdep 경고 */

/* RCU sparse 검증 — __rcu 어노테이션 */
void __rcu *ptr;  /* sparse 도구가 RCU 접근 규칙 위반 감지 */

litmus test 고급 패턴

/* Store Buffering (SB) 패턴 — 전형적인 위험한 패턴 */
C SB+fencembonceonces

{}

P0(int *x, int *y)
{
    WRITE_ONCE(*x, 1);
    smp_mb();              /* 완전 배리어 필요 */
    r0 = READ_ONCE(*y);
}

P1(int *x, int *y)
{
    WRITE_ONCE(*y, 1);
    smp_mb();              /* 완전 배리어 필요 */
    r1 = READ_ONCE(*x);
}

exists (0:r0=0 /\ 1:r1=0)
/* smp_mb()가 없으면: Sometimes (x86에서도 발생 가능!)
 * smp_mb()가 있으면: Never */

/* Load Buffering (LB) — 데이터 의존성 */
C LB+poacquireonce+pooncerelease

{}

P0(int *x, int *y)
{
    r0 = smp_load_acquire(x);
    WRITE_ONCE(*y, 1);
}

P1(int *x, int *y)
{
    r1 = smp_load_acquire(y);
    smp_store_release(x, 1);
}

exists (0:r0=1 /\ 1:r1=1)
/* Never — acquire/release 순서 보장 */

# litmus test 배치 실행
cd tools/memory-model/
make -f Makefile.litmus run   # 모든 litmus test 실행

# 특정 패턴 검증
herd7 -conf linux-kernel.cfg \
  litmus-tests/SB+fencembonceonces.litmus

# klitmus: 실제 하드웨어에서 litmus test 실행
klitmus7 litmus-tests/MP+pooncerelease+poacquireonce.litmus
# → C 소스 생성 → 컴파일 → 커널 모듈로 로드 → 실제 CPU에서 테스트

실전 패턴: 커스텀 Lock-free 구조 설계

설계 원칙

기존 커널 API(llist, kfifo, ptr_ring, xarray)로 해결할 수 없는 경우에만 커스텀 lock-free 자료구조를 설계합니다. 다음 원칙을 반드시 따르세요:

1. 소유권 규칙 명확화: 각 데이터 필드의 “누가 읽고 누가 쓰는가”를 문서화합니다.
2. 최소 동기화 원칙: 필요한 최소한의 배리어만 사용합니다. 과도한 smp_mb()는 성능 저하를 유발합니다.
3. WRITE_ONCE/READ_ONCE 필수: 공유 데이터의 모든 접근에 사용하여 컴파일러 최적화(Compiler Optimization)로 인한 데이터 레이스를 방지합니다.
4. LKMM 검증: litmus test를 작성하여 메모리 순서 정확성을 기계적으로 검증합니다.
5. KCSAN 테스트: 런타임 데이터 레이스 감지기로 실제 하드웨어에서 검증합니다.

예시: 커스텀 SPSC 통계 카운터

/* 커스텀 SPSC 통계 카운터 — 하나의 CPU가 쓰고, 다른 CPU가 읽는 패턴 */
struct spsc_stat {
    unsigned long   packets ____cacheline_aligned_in_smp;
    unsigned long   bytes;
    unsigned long   errors;
    /* 하나의 캐시라인에 모든 통계 배치 */
};

/* 쓰기 측 (단일 CPU, softirq) */
static void update_stats(struct spsc_stat *s, unsigned long pkt_bytes)
{
    /* WRITE_ONCE: 다른 CPU의 읽기와 데이터 레이스 방지 */
    WRITE_ONCE(s->packets, s->packets + 1);
    WRITE_ONCE(s->bytes, s->bytes + pkt_bytes);
    /* 배리어 불필요: 읽기 측은 "대략적" 값을 허용 */
}

/* 읽기 측 (다른 CPU, procfs) */
static void read_stats(struct spsc_stat *s, struct stats_snapshot *snap)
{
    /* READ_ONCE: 일관성은 보장하지 않지만 찢어진 읽기 방지 */
    snap->packets = READ_ONCE(s->packets);
    snap->bytes = READ_ONCE(s->bytes);
    snap->errors = READ_ONCE(s->errors);
    /* 엄밀한 일관성이 필요하면 seqcount 사용 */
}

예시: seqcount로 일관된 스냅샷 보장

/* seqcount 기반 일관된 통계 스냅샷 */
struct consistent_stat {
    seqcount_t      seq;
    unsigned long   packets;
    unsigned long   bytes;
};

/* 쓰기 측 */
static void update_consistent(struct consistent_stat *s,
                               unsigned long pkt_bytes)
{
    write_seqcount_begin(&s->seq);
    s->packets++;
    s->bytes += pkt_bytes;
    write_seqcount_end(&s->seq);
}

/* 읽기 측 (lock-free, 재시도 가능) */
static void read_consistent(struct consistent_stat *s,
                             struct stats_snapshot *snap)
{
    unsigned int seq;
    do {
        seq = read_seqcount_begin(&s->seq);
        snap->packets = s->packets;
        snap->bytes = s->bytes;
    } while (read_seqcount_retry(&s->seq, seq));
    /* 쓰기 중이었다면 재시도 → 항상 일관된 스냅샷 */
}

Lock-free 프로그래밍의 흔한 실수 모음

/* 실수 예시: TOCTOU (Time-of-Check-to-Time-of-Use) */
/* 잘못된 코드 */
if (READ_ONCE(shared_ptr) != NULL) {
    /* ← 여기서 다른 CPU가 shared_ptr = NULL로 변경! */
    val = READ_ONCE(shared_ptr)->data;  /* NULL 역참조 크래시! */
}

/* 올바른 코드: 로컬 변수에 한 번만 로드 */
struct my_obj *p = READ_ONCE(shared_ptr);
if (p) {
    val = READ_ONCE(p->data);  /* p는 로컬이므로 안전 */
    /* 단, p가 가리키는 객체가 해제될 수 있으므로 RCU 필요 */
}

/* 더 안전한 코드: RCU 보호 */
rcu_read_lock();
p = rcu_dereference(shared_ptr);
if (p) {
    val = p->data;  /* RCU 보호 하에 p는 해제되지 않음 */
}
rcu_read_unlock();

Lock-free 코드 디버깅 기법

Lock-free 코드의 버그는 재현이 어렵고, 특정 아키텍처/타이밍에서만 발생합니다. 다음 도구와 기법을 체계적으로 활용하세요.

# Lock-free 코드 검증 워크플로우
# 1. 설계 시: LKMM litmus test
cd tools/memory-model/
herd7 -conf linux-kernel.cfg my_test.litmus

# 2. 빌드 시: sparse로 RCU 어노테이션 검사
make C=1 drivers/my_module.o

# 3. 런타임: KCSAN + KASAN 활성화 커널로 테스트
# .config:
# CONFIG_KCSAN=y
# CONFIG_KASAN=y
# CONFIG_PROVE_RCU=y

# 4. 스트레스 테스트: rcutorture
modprobe rcutorture nreaders=8 nfakewriters=4 torture_type=rcu

# 5. 아키텍처 교차 테스트: QEMU + ARM64
qemu-system-aarch64 -kernel Image -M virt -cpu cortex-a72 ...

패턴 카탈로그: 자주 사용되는 lock-free 관용구

패턴 1: 상태 머신 전이 (atomic cmpxchg)

/* 원자적 상태 전이: IDLE → RUNNING → COMPLETED */
enum my_state { IDLE = 0, RUNNING = 1, COMPLETED = 2 };

static bool try_start(atomic_t *state)
{
    return atomic_cmpxchg(state, IDLE, RUNNING) == IDLE;
    /* IDLE일 때만 RUNNING으로 전이, 다른 상태면 실패 */
}

static void complete(atomic_t *state)
{
    WARN_ON(atomic_cmpxchg(state, RUNNING, COMPLETED) != RUNNING);
}

패턴 2: 플래그 기반 one-shot 실행

/* 여러 CPU 중 정확히 하나만 작업을 실행 */
static atomic_t done_flag = ATOMIC_INIT(0);

void try_do_once(void)
{
    if (atomic_cmpxchg(&done_flag, 0, 1) == 0) {
        /* 이 코드는 정확히 한 번만 실행됨 */
        do_initialization();
        smp_store_release(&init_complete, 1);
    } else {
        /* 다른 CPU가 이미 실행 중/완료 */
        while (!smp_load_acquire(&init_complete))
            cpu_relax();
    }
}

패턴 3: Publish-Subscribe (RCU)

/* 전형적인 RCU publish-subscribe 패턴 */
struct config {
    int param_a;
    int param_b;
    struct rcu_head rcu;
};

static struct config __rcu *global_config;

/* 쓰기 측: 새 설정 발행 */
void update_config(int a, int b)
{
    struct config *new = kmalloc(sizeof(*new), GFP_KERNEL);
    struct config *old;

    new->param_a = a;
    new->param_b = b;

    spin_lock(&config_lock);
    old = rcu_dereference_protected(global_config,
                                     lockdep_is_held(&config_lock));
    rcu_assign_pointer(global_config, new);  /* 발행(publish) */
    spin_unlock(&config_lock);

    kfree_rcu(old, rcu);  /* 이전 설정 안전하게 해제 */
}

/* 읽기 측: 구독(subscribe), lock-free */
int read_param_a(void)
{
    struct config *cfg;
    int val;

    rcu_read_lock();
    cfg = rcu_dereference(global_config);  /* 구독 */
    val = cfg->param_a;
    rcu_read_unlock();
    return val;
}

패턴 4: Double-Checked Initialization

/* Lock-free 초기화 체크 + lock 보호 초기화 */
static void *shared_resource;

void *get_resource(void)
{
    void *p = smp_load_acquire(&shared_resource);  /* 1차 체크 */
    if (p)
        return p;

    mutex_lock(&init_mutex);
    p = smp_load_acquire(&shared_resource);        /* 2차 체크 */
    if (!p) {
        p = allocate_and_init();
        smp_store_release(&shared_resource, p);    /* 공개 */
    }
    mutex_unlock(&init_mutex);
    return p;
}
/* 대부분의 호출: lock 없이 1차 체크에서 반환 (fast-path)
 * 초기화 시에만 mutex 진입 (slow-path) */

패턴 5: Lock-free 통계 집계 (per-CPU + seqcount)

/* 네트워크 디바이스 통계 집계 — 실제 커널 패턴 */
struct net_device_stats {
    unsigned long   rx_packets;
    unsigned long   rx_bytes;
    unsigned long   tx_packets;
    unsigned long   tx_bytes;
    /* ... */
};

/* per-CPU 통계 (각 CPU가 lock 없이 갱신) */
struct pcpu_sw_netstats {
    u64_stats_sync  syncp;    /* seqcount 기반 동기화 */
    u64             rx_packets;
    u64             rx_bytes;
    u64             tx_packets;
    u64             tx_bytes;
};

/* 쓰기 측 (softirq, 해당 CPU만) */
void record_rx(struct pcpu_sw_netstats __percpu *stats,
               unsigned int len)
{
    struct pcpu_sw_netstats *s = this_cpu_ptr(stats);
    u64_stats_update_begin(&s->syncp);
    s->rx_packets++;
    s->rx_bytes += len;
    u64_stats_update_end(&s->syncp);
}

/* 읽기 측 (다른 CPU, ethtool/procfs) */
void collect_stats(struct pcpu_sw_netstats __percpu *stats,
                   struct rtnl_link_stats64 *total)
{
    int cpu;
    for_each_possible_cpu(cpu) {
        struct pcpu_sw_netstats *s = per_cpu_ptr(stats, cpu);
        unsigned int start;
        u64 rx_packets, rx_bytes;

        do {
            start = u64_stats_fetch_begin(&s->syncp);
            rx_packets = s->rx_packets;
            rx_bytes = s->rx_bytes;
        } while (u64_stats_fetch_retry(&s->syncp, start));

        total->rx_packets += rx_packets;
        total->rx_bytes += rx_bytes;
    }
}

커스텀 lock-free 구조 체크리스트

참고 자료

커널 공식 문서

• memory-barriers.txt — lock-free 코드에 필수적인 메모리 순서 보장 가이드
• atomic_t — Pair Ordering and Semantics — lock-free의 기본 빌딩 블록인 원자적 연산
• Circular Buffers — kfifo 등 커널 링 버퍼의 lock-free 설계
• RCU concepts — lock-free 읽기 + 안전한 메모리 회수
• Linux Kernel Memory Model — LKMM으로 lock-free 코드 검증

LWN.net 심층 기사

• Lockless patterns: an introduction to compare-and-swap (2014) — CAS 기반 lock-free 패턴 입문 (필독)
• Lockless patterns: more read-modify-write operations (2021) — 고급 RMW 연산 패턴
• Lockless patterns: relaxed access and partial memory barriers (2020) — relaxed atomic과 부분 배리어
• What is RCU, Fundamentally? (2007) — RCU: 가장 널리 쓰이는 lock-free 메커니즘
• A formal kernel memory-ordering model (part 1) (2017) — LKMM으로 lock-free 코드 정형 검증

학술 자료 및 외부 참고

• Michael & Scott — "Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms" (PODC 1996) — lock-free 큐 원본 논문
• Treiber — "Systems Programming: Coping with Parallelism" (IBM, 1986) — Treiber stack 원본
• Herlihy — "A Methodology for Implementing Highly Concurrent Data Objects" (ACM TOPLAS, 1993) — lock-free 알고리즘 분류 체계
• Paul McKenney — "Is Parallel Programming Hard?" — Chapter 14: Advanced Synchronization
• 커널 소스: include/linux/llist.h (lock-free linked list), include/linux/kfifo.h (SPSC 링 버퍼)
• LKMM 도구: tools/memory-model/litmus-tests/ — lock-free 패턴 litmus test 모음

관련 문서

추가 학습 리소스

커널 소스 참고 경로

# Lock-free 자료구조 소스 위치
include/linux/llist.h           # llist API
lib/llist.c                     # llist 구현
include/linux/kfifo.h           # kfifo 매크로/인라인
lib/kfifo.c                     # kfifo 구현
include/linux/ptr_ring.h        # ptr_ring (전체 인라인)
include/linux/xarray.h          # xarray API
lib/xarray.c                    # xarray 구현
include/linux/seqlock.h         # seqcount, seqcount_latch
include/linux/percpu-refcount.h # percpu_ref
lib/percpu-refcount.c           # percpu_ref 구현
include/linux/rhashtable.h      # rhashtable API
lib/rhashtable.c                # rhashtable 구현

# LKMM (Linux Kernel Memory Model)
tools/memory-model/             # 메모리 모델 정의
tools/memory-model/linux-kernel.cat  # CAT 모델 파일
tools/memory-model/litmus-tests/     # 리트머스 테스트 모음

# Documentation
Documentation/RCU/              # RCU 문서
Documentation/memory-barriers.txt   # 메모리 배리어 문서
Documentation/locking/          # 락킹 문서