Linked List

Linux 커널의 핵심 자료구조인 struct list_head 기반 원형 이중 연결 리스트의 설계 철학, 사용법, 다양한 변형(hlist, llist), RCU 보호 리스트, 주의사항과 디버깅까지 종합적으로 다룹니다.

개요 (Overview)

C 언어에는 표준 컨테이너 라이브러리가 없습니다. 사용자 공간에서는 glib, uthash 등 외부 라이브러리를 사용하지만, 커널은 자체적인 침입형(intrusive) 연결 리스트를 <linux/list.h>에 구현합니다. 이 구현은 1996년부터 사용되어 온 커널에서 가장 널리 쓰이는 자료구조입니다.

커널이 자체 연결 리스트를 사용하는 이유:

• 침입형 설계 — 리스트 노드(list_head)를 데이터 구조체에 직접 임베드합니다. 별도의 래퍼 할당이 필요 없어 메모리 오버헤드가 최소화됩니다.
• 타입 독립적 — list_head는 어떤 구조체에든 포함될 수 있으며, container_of 매크로로 원본 구조체를 복원합니다.
• 원형 이중 연결 — head와 tail의 구분 없이 O(1)으로 양쪽 끝에 삽입/삭제가 가능합니다.
• 침입형 오버헤드 최소화 — 리스트 노드를 위한 별도 래퍼 할당은 필요 없습니다. 다만 엔트리 구조체 자체를 동적으로 생성하는 경우 kmalloc()은 여전히 필요할 수 있습니다.
• 다중 리스트 참여 — 하나의 구조체에 여러 list_head 필드를 두면 동시에 여러 리스트에 참여할 수 있습니다.

반대로 다음 조건에서는 list_head가 적합하지 않을 수 있습니다:

• 키 기반 점 조회가 핵심이면 hlist + hashtable이 일반적으로 더 낫습니다.
• 정렬 상태 유지나 범위 검색이 필요하면 rbtree가 유리합니다.
• 인덱스 접근이 많고 키가 정수라면 XArray가 더 단순하고 빠를 수 있습니다.

list_head 구조와 container_of

struct list_head의 정의는 놀라울 정도로 단순합니다:

/* 개념 예시: include/linux/types.h list_head 정의 */
/* include/linux/types.h */
struct list_head {
    struct list_head *next, *prev;
};

이 구조체는 데이터를 포함하지 않습니다. 대신, 데이터를 담은 구조체 안에 임베드됩니다:

struct my_item {
    int                 id;
    char                name[64];
    struct list_head    list;   /* 리스트 노드 임베드 */
    struct list_head    other;  /* 다른 리스트에도 참여 가능 */
};

원형 이중 연결 리스트의 구조를 다이어그램으로 살펴보겠습니다:

container_of 매크로 (container_of Macro)

리스트를 순회하면 list_head 포인터를 얻게 됩니다. 이 포인터로부터 실제 데이터 구조체를 복원하는 것이 container_of 매크로입니다:

/* include/linux/container_of.h */
#define container_of(ptr, type, member) ({               \
    void *__mptr = (void *)(ptr);                        \
    static_assert(__same_type(*(ptr), ((type *)0)->member) || \
                  __same_type(*(ptr), void),              \
                  "pointer type mismatch in container_of()"); \
    ((type *)(__mptr - offsetof(type, member))); })

동작 원리는 간단합니다: list_head 멤버의 주소에서 해당 멤버의 구조체 내 오프셋을 빼면 구조체의 시작 주소가 됩니다.

/* 사용 예: list_head 포인터에서 my_item 구조체 복원 */
struct list_head *pos;
struct my_item *item;

item = container_of(pos, struct my_item, list);
pr_info("item id=%d, name=%s\\n", item->id, item->name);

offsetof 매크로 (offsetof Macro)

container_of의 핵심은 offsetof입니다. 구조체 시작 주소로부터 특정 멤버까지의 바이트 오프셋을 컴파일 타임에 계산합니다:

/* include/linux/stddef.h */
#define offsetof(TYPE, MEMBER) __builtin_offsetof(TYPE, MEMBER)

/* GCC 내장 함수가 없을 경우의 전통적 구현 */
#define offsetof(TYPE, MEMBER) ((size_t)&((TYPE *)0)->MEMBER)

기본 연산 (Basic Operations)

초기화 (Initialization)

리스트 사용 전 반드시 초기화해야 합니다. 초기화된 리스트는 next와 prev가 자기 자신을 가리키는 "빈 원형 리스트"입니다:

/* 컴파일 타임 초기화 (전역/정적 변수) */
static LIST_HEAD(my_list);
/* 다음과 동일:
 * static struct list_head my_list = { &my_list, &my_list };
 */

/* 런타임 초기화 (함수 내) */
struct list_head dynamic_list;
INIT_LIST_HEAD(&dynamic_list);

/* 구조체 멤버 초기화 */
struct my_item *item = kmalloc(sizeof(*item), GFP_KERNEL);
INIT_LIST_HEAD(&item->list);

추가와 삭제 (Add & Delete)

/* 리스트 head 바로 뒤에 삽입 (스택 동작: LIFO) */
list_add(&item->list, &my_list);

/* 리스트 head 바로 앞에 삽입 (큐 동작: FIFO) */
list_add_tail(&item->list, &my_list);

/* 리스트에서 삭제 (next/prev를 LIST_POISON으로 설정) */
list_del(&item->list);

/* 삭제 후 재초기화 (다시 list_add 가능) */
list_del_init(&item->list);

/* 노드 교체: old 자리에 new를 삽입 */
list_replace(&old->list, &new->list);

/* 교체 + old 재초기화 */
list_replace_init(&old->list, &new->list);

이동과 합치기 (Move & Splice)

/* 노드를 다른 리스트의 head 뒤로 이동 */
list_move(&item->list, &other_list);

/* 노드를 다른 리스트의 tail로 이동 */
list_move_tail(&item->list, &other_list);

/* 리스트 전체를 다른 리스트 head 뒤에 합치기 */
list_splice(&source_list, &dest_list);

/* 합치기 + source 리스트 재초기화 */
list_splice_init(&source_list, &dest_list);

/* 합치기 (tail 쪽에) + source 재초기화 */
list_splice_tail_init(&source_list, &dest_list);

상태 확인 (Query)

/* 리스트가 비어있는가? */
if (list_empty(&my_list))
    pr_info("list is empty\\n");

/* 노드가 하나뿐인가? */
if (list_is_singular(&my_list))
    pr_info("only one element\\n");

/* 이 노드가 리스트의 마지막인가? */
if (list_is_last(&item->list, &my_list))
    pr_info("this is the last node\\n");

/* 첫 번째 / 마지막 엔트리 가져오기 */
struct my_item *first = list_first_entry(&my_list, struct my_item, list);
struct my_item *last  = list_last_entry(&my_list, struct my_item, list);

/* 빈 리스트일 수 있을 때 (NULL 반환) */
struct my_item *f = list_first_entry_or_null(&my_list, struct my_item, list);

권장 수명주기 패턴

실무에서 리스트 버그의 대부분은 API 자체보다 수명주기 순서에서 발생합니다. 아래 순서를 습관화하면 use-after-free와 이중 삭제를 크게 줄일 수 있습니다.

1. 할당/초기화: kmalloc() 후 payload를 채우고 INIT_LIST_HEAD(&obj->list) 실행
2. 공개(publish): lock 보호 하에 list_add() 또는 list_add_tail() 호출
3. 사용: 순회 시 컨텍스트 규칙(락 또는 RCU)을 엄격히 지킴
4. 제거(unlink): list_del_init() 또는 list_del_rcu()로 연결 해제
5. 해제(free): 일반 리스트는 즉시 kfree(), RCU 리스트는 grace period 뒤 해제

/* 실무 패턴: 수명주기와 에러 경로를 한 함수에서 정리 */
int my_item_publish(struct list_head *head, int id)
{
    struct my_item *obj;

    obj = kmalloc(sizeof(*obj), GFP_KERNEL);
    if (!obj)
        return -ENOMEM;

    obj->id = id;
    INIT_LIST_HEAD(&obj->list);

    spin_lock(&list_lock);
    list_add_tail(&obj->list, head);
    spin_unlock(&list_lock);
    return 0;
}

순회 매크로 (Traversal Macros)

커널의 리스트 순회 매크로는 for 루프를 감싸는 편의 매크로입니다. 가장 자주 사용되는 것은 list_for_each_entry입니다:

/* list_head 포인터 순회 (거의 사용 안 함) */
struct list_head *pos;
list_for_each(pos, &my_list) {
    struct my_item *item = container_of(pos, struct my_item, list);
    pr_info("id=%d\\n", item->id);
}

/* 엔트리(구조체) 직접 순회 (가장 권장) */
struct my_item *item;
list_for_each_entry(item, &my_list, list) {
    pr_info("id=%d, name=%s\\n", item->id, item->name);
}

/* 역순 순회 */
list_for_each_entry_reverse(item, &my_list, list) {
    pr_info("reverse: id=%d\\n", item->id);
}

엔트리 접근 매크로들:

/* 현재 엔트리로부터 리스트 포인터를 추출 */
struct my_item *entry = list_entry(pos, struct my_item, list);
/* list_entry는 container_of와 동일 */

/* 다음/이전 엔트리 */
struct my_item *next_item = list_next_entry(item, list);
struct my_item *prev_item = list_prev_entry(item, list);

#define list_for_each_entry(pos, head, member)                  \
    for (pos = list_first_entry(head, typeof(*pos), member); \
         &pos->member != (head);                                \
         pos = list_next_entry(pos, member))

안전한 순회 (Safe Traversal)

순회 중에 현재 노드를 삭제하면 next 포인터가 파괴되어 순회를 계속할 수 없습니다. 이 문제를 해결하기 위해 _safe 버전의 매크로가 제공됩니다:

/* 순회 중 안전하게 삭제 가능 (tmp에 next를 미리 저장) */
struct my_item *item, *tmp;
list_for_each_entry_safe(item, tmp, &my_list, list) {
    if (item->id == target_id) {
        list_del(&item->list);
        kfree(item);
        /* tmp 덕분에 순회가 안전하게 계속됨 */
    }
}

/* 역순 안전 순회 */
list_for_each_entry_safe_reverse(item, tmp, &my_list, list) {
    list_del(&item->list);
    kfree(item);
}

순회 패턴 선택 기준

RCU 보호 리스트 (RCU-Protected Lists)

RCU(Read-Copy-Update)를 사용하면 읽기 측에서 lock 없이 리스트를 순회할 수 있습니다. 쓰기 측만 lock을 잡으면 되므로, 읽기가 압도적으로 많은 경우 최적의 성능을 제공합니다.

/* RCU 보호 리스트 추가 (publish-subscribe 패턴) */
list_add_rcu(&item->list, &my_list);
/* 내부적으로 rcu_assign_pointer()를 사용하여 메모리 배리어 보장 */

/* RCU 보호 리스트 삭제 */
list_del_rcu(&item->list);
/* next 포인터를 유지하여 진행 중인 reader가 계속 순회 가능 */
synchronize_rcu();  /* 모든 reader가 빠져나올 때까지 대기 */
kfree(item);         /* grace period 후에 안전하게 해제 */

/* 또는 콜백 기반 비동기 해제 */
list_del_rcu(&item->list);
kfree_rcu(item, rcu);  /* struct에 rcu_head 멤버 필요 */

/* RCU 읽기 측: lock 없이 순회 */
rcu_read_lock();
list_for_each_entry_rcu(item, &my_list, list) {
    pr_info("id=%d\\n", item->id);
    /* 이 구간에서는 preemption 비활성화 (PREEMPT_RCU 제외) */
}
rcu_read_unlock();

/* lockless 순회 (KCSAN 경고 억제) */
list_for_each_entry_lockless(item, &my_list, list) {
    /* lock도 rcu_read_lock도 없이 순회할 때 사용 */
}

RCU 쓰기 측 권장 패턴

RCU는 "읽기 lock-free"가 핵심이지만, 쓰기 측은 보통 spinlock으로 직렬화합니다. 아래 패턴은 커널 서브시스템에서 가장 흔히 쓰이는 형태입니다.

/* writer: 갱신은 락으로 직렬화, 읽기는 RCU로 병렬화 */
void my_table_insert(struct my_item *new)
{
    spin_lock(&table_lock);
    list_add_rcu(&new->list, &my_list);
    spin_unlock(&table_lock);
}

void my_table_remove(struct my_item *obj)
{
    spin_lock(&table_lock);
    list_del_rcu(&obj->list);
    spin_unlock(&table_lock);

    /* reader 종료 이후 해제 */
    kfree_rcu(obj, rcu);
}

hlist (해시 리스트)

struct hlist_head는 해시 테이블의 버킷으로 최적화된 단방향 리스트입니다. list_head는 next와 prev 두 포인터(16바이트)를 사용하지만, hlist_head는 first 하나(8바이트)만 사용하여 해시 테이블의 메모리를 절반으로 줄입니다.

struct hlist_head {
    struct hlist_node *first;
};

struct hlist_node {
    struct hlist_node *next;
    struct hlist_node **pprev;  /* prev 노드의 next 포인터의 주소 */
};

pprev는 이전 노드의 next 포인터(또는 head의 first 포인터)를 가리키는 이중 포인터입니다. 이를 통해 O(1) 삭제를 구현합니다:

/* hlist 기본 사용 */
DEFINE_HASHTABLE(my_htable, 10);  /* 2^10 = 1024 buckets */

struct my_entry {
    int                  key;
    char                 value[32];
    struct hlist_node    node;
};

/* 삽입 */
struct my_entry *entry = kmalloc(sizeof(*entry), GFP_KERNEL);
entry->key = 42;
hash_add(my_htable, &entry->node, entry->key);

/* 검색 */
struct my_entry *cur;
hash_for_each_possible(my_htable, cur, node, 42) {
    if (cur->key == 42) {
        pr_info("found: %s\\n", cur->value);
        break;
    }
}

/* 삭제 */
hash_del(&entry->node);
kfree(entry);

llist (Lock-less 리스트)

llist (Lock-less Linked List)는 cmpxchg(Compare-And-Swap) 기반의 lock-free 스택입니다. 여러 CPU에서 동시에 lock 없이 노드를 추가할 수 있으며, 하나의 소비자가 전체 리스트를 원자적으로 꺼내갑니다.

struct llist_head {
    struct llist_node *first;
};

struct llist_node {
    struct llist_node *next;
};

/* 초기화 */
static LLIST_HEAD(my_llist);

/* Lock-free 추가 (여러 CPU에서 동시 호출 가능) */
struct my_work {
    struct llist_node node;
    int data;
};

struct my_work *w = kmalloc(sizeof(*w), GFP_ATOMIC);
w->data = 42;
llist_add(&w->node, &my_llist);

/* 전체 리스트를 원자적으로 꺼내기 (단일 소비자) */
struct llist_node *batch = llist_del_all(&my_llist);

/* 꺼낸 리스트 순회 */
struct llist_node *pos;
llist_for_each(pos, batch) {
    struct my_work *w = container_of(pos, struct my_work, node);
    process_work(w);
    kfree(w);
}

llist의 대표적인 사용 시나리오:

• IRQ → 스레드 워크 전달: 인터럽트 핸들러에서 lock 없이 작업을 큐잉하고, 워커 스레드가 일괄 처리합니다.
• RCU 콜백 큐잉: call_rcu() 내부에서 사용됩니다.
• per-CPU → 글로벌 집계: 각 CPU에서 로컬 리스트에 추가하고, 하나의 스레드가 수집합니다.

설계 체크리스트 (Design Checklist)

아래 체크리스트를 먼저 채우고 구현에 들어가면 자료구조 재작업 비용을 크게 줄일 수 있습니다.

커널 내 실제 사용 사례 (Real-World Usage in Kernel)

커널의 핵심 자료구조에서 list_head가 어떻게 사용되는지 살펴봅니다:

/* include/linux/sched.h - task_struct의 리스트들 */
struct task_struct {
    /* ... */
    struct list_head    tasks;       /* 모든 프로세스 리스트 (init_task.tasks가 head) */
    struct list_head    children;    /* 자식 프로세스 리스트 head */
    struct list_head    sibling;     /* 형제 프로세스 리스트 (parent->children에 연결) */
    struct list_head    thread_group;/* 같은 스레드 그룹 */
    /* ... */
};

/* 모든 프로세스 순회 예: init_task에서 시작 */
struct task_struct *task;
for_each_process(task) {
    pr_info("PID %d: %s\\n", task->pid, task->comm);
}
/* for_each_process는 list_for_each_entry의 래퍼:
 * #define for_each_process(p) \
 *     list_for_each_entry(p, &init_task.tasks, tasks)
 */

주의사항과 함정 (Pitfalls & Common Mistakes)

1. 초기화 누락

/* 잘못된 코드: 초기화 없이 사용 */
struct list_head my_list;
list_add(&item->list, &my_list);  /* BUG! next/prev가 쓰레기 값 */

/* 올바른 코드 */
struct list_head my_list;
INIT_LIST_HEAD(&my_list);
list_add(&item->list, &my_list);  /* OK */

2. 이중 삭제

/* BUG: list_del 후 다시 list_del */
list_del(&item->list);
/* ... 나중에 ... */
list_del(&item->list);  /* LIST_POISON 접근 → OOPS */

/* 해결: list_del_init 사용 */
list_del_init(&item->list);
/* 이제 list_empty(&item->list)로 삭제 여부 확인 가능 */

3. 동시성 보호 누락

/* 위험: lock 없이 공유 리스트 접근 */
list_add(&item->list, &shared_list);  /* 경합! */

/* 올바른 패턴 */
spin_lock(&list_lock);
list_add(&item->list, &shared_list);
spin_unlock(&list_lock);

/* 또는 RCU 패턴 */
spin_lock(&list_lock);
list_add_rcu(&item->list, &shared_list);
spin_unlock(&list_lock);

4. list_for_each_entry_safe의 한계

/* list_for_each_entry_safe는 다음 노드(tmp)를 미리 저장하지만,
 * 만약 다른 CPU가 tmp 노드를 삭제하면 여전히 위험합니다.
 *
 * safe 버전은 "나 자신을 삭제해도 순회가 안전하다"는 뜻이지,
 * "다른 CPU의 수정으로부터 안전하다"는 뜻이 아닙니다!
 */

/* 동시 수정이 있을 때의 올바른 패턴 */
spin_lock(&list_lock);
list_for_each_entry_safe(item, tmp, &my_list, list) {
    list_del(&item->list);
    kfree(item);
}
spin_unlock(&list_lock);

5. Iterator 변수 스코프 (커널 6.x 변경)

/* 커널 6.x부터: 순회 매크로의 iterator 변수가
 * 루프 종료 후 유효한 엔트리를 가리키지 않을 수 있습니다.
 *
 * 기존 잘못된 패턴: */
struct my_item *item;
list_for_each_entry(item, &my_list, list) {
    if (item->id == target)
        break;
}
/* item을 루프 밖에서 사용 → 6.x에서 위험! */

/* 올바른 패턴: 별도 변수에 저장 */
struct my_item *item, *found = NULL;
list_for_each_entry(item, &my_list, list) {
    if (item->id == target) {
        found = item;
        break;
    }
}
if (found)
    pr_info("found id=%d\\n", found->id);

성능 고려사항 (Performance Considerations)

list_head는 만능 자료구조가 아닙니다. 사용 패턴에 따라 더 적합한 자료구조를 선택해야 합니다:

캐시 성능 관련 고려사항:

• list_head 배치: 자주 순회하는 리스트의 list_head는 구조체 앞쪽에 배치하면 캐시 라인 활용이 좋아집니다.
• 연결 리스트의 약점: 노드가 메모리에 흩어져 있으면 캐시 미스가 빈번합니다. 대량 순차 접근이 필요하면 배열 기반 자료구조를 고려하세요.
• 리스트 길이: O(n) 검색이 병목이 되면 rbtree나 hashtable로 전환하세요. 커널에서는 수십~수백 개 이하의 리스트에 list_head를 사용하는 것이 일반적입니다.

성능 수치 예시

아래 표는 자료구조 선택 감각을 잡기 위한 예시 수치입니다. 절대값은 하드웨어, 락 경합, 키 분포, 버킷 수, NUMA 배치에 따라 크게 달라집니다.

캐시 미스율 비교 (perf stat 측정):

디버깅 (Debugging)

리스트 corruption은 커널에서 가장 흔한 버그 중 하나입니다. 다행히 커널은 강력한 디버깅 도구를 제공합니다.

CONFIG_DEBUG_LIST

이 옵션을 활성화하면 모든 리스트 연산에 무결성 검사가 추가됩니다:

/* CONFIG_DEBUG_LIST 활성화 시 list_add()가 다음을 검증: */
/* 1. next->prev == head (리스트 연결 무결성) */
/* 2. prev->next == head (리스트 연결 무결성) */
/* 3. new != LIST_POISON1 (이미 삭제된 노드 재삽입 방지) */

/* 위반 시 커널 경고 메시지: */
/* list_add corruption. next->prev should be <addr1>, but was <addr2>. */
/* list_del corruption. prev->next should be <addr1>, but was <addr2>. */

# .config에서 활성화
CONFIG_DEBUG_LIST=y

# 또는 menuconfig에서
# Kernel hacking → Memory Debugging → Debug linked list manipulation

LIST_POISON 탐지

/* include/linux/poison.h */
#define LIST_POISON1  ((void *) 0x100 + POISON_POINTER_DELTA)
#define LIST_POISON2  ((void *) 0x122 + POISON_POINTER_DELTA)

/* list_del()은 next를 LIST_POISON1로, prev를 LIST_POISON2로 설정합니다.
 * 이 값에 접근하면 즉시 page fault가 발생하여 버그를 빨리 발견할 수 있습니다. */

KASAN과의 연계

# KASAN (Kernel Address Sanitizer) 활성화
CONFIG_KASAN=y

# Use-after-free 탐지: kfree 후 list 접근 시
# BUG: KASAN: use-after-free in list_del+0x20/0x50
# Read of size 8 at addr ffff888012345678
# Freed by task xyz at: kfree+0x...

실전 디버깅 체크리스트:

• CONFIG_DEBUG_LIST=y로 빌드하여 리스트 corruption 조기 탐지
• CONFIG_KASAN=y로 use-after-free, out-of-bounds 접근 탐지
• list_del() 후 즉시 kfree()하기 전에 모든 참조가 제거되었는지 확인
• list_empty()로 빈 리스트에서 list_first_entry() 호출을 방지
• 순회 중 삭제는 반드시 _safe 버전 사용
• 공유 리스트에는 항상 적절한 lock 사용

crash> list task_struct.tasks -s task_struct.comm,pid -H init_task.tasks

실습 예제 (Hands-On Example)

이론을 넘어 실제 동작하는 커널 모듈을 통해 list_head 사용법을 익혀봅니다. 아래 예제는 간단한 학생 정보 관리 시스템으로, 삽입/순회/삭제/검색을 모두 다룹니다.

완전한 커널 모듈 예제

/* student_list.c - 실습용 list_head 모듈 */
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/init.h>
#include <linux/list.h>
#include <linux/slab.h>

/* 학생 정보 구조체 */
struct student {
    unsigned int        id;
    char                name[32];
    unsigned int        score;
    struct list_head    list;    /* 리스트 노드 */
};

/* 학생 리스트 head (전역) */
static LIST_HEAD(student_list);

/* 학생 추가 함수 */
static struct student *add_student(unsigned int id, const char *name, unsigned int score)
{
    struct student *s;

    s = kmalloc(sizeof(*s), GFP_KERNEL);
    if (!s)
        return NULL;

    s->id = id;
    strncpy(s->name, name, sizeof(s->name) - 1);
    s->name[sizeof(s->name) - 1] = '\0';
    s->score = score;

    /* 리스트 끝에 추가 (FIFO) */
    list_add_tail(&s->list, &student_list);

    pr_info("Added: ID=%u, Name=%s, Score=%u\n", id, name, score);
    return s;
}

/* ID로 학생 검색 */
static struct student *find_student(unsigned int id)
{
    struct student *s;

    list_for_each_entry(s, &student_list, list) {
        if (s->id == id)
            return s;
    }
    return NULL;
}

/* 학생 삭제 (ID 기준) */
static bool remove_student(unsigned int id)
{
    struct student *s;

    s = find_student(id);
    if (!s) {
        pr_warn("Student ID=%u not found\n", id);
        return false;
    }

    pr_info("Removing: ID=%u, Name=%s\n", s->id, s->name);
    list_del(&s->list);
    kfree(s);
    return true;
}

/* 전체 학생 목록 출력 */
static void print_all_students(void)
{
    struct student *s;
    int count = 0;

    pr_info("=== Student List ===\n");
    list_for_each_entry(s, &student_list, list) {
        pr_info("  [%d] ID=%u, Name=%-20s, Score=%u\n",
                ++count, s->id, s->name, s->score);
    }
    pr_info("Total: %d students\n", count);
}

/* 조건부 삭제: 점수가 60 미만인 학생 제거 */
static void remove_failing_students(void)
{
    struct student *s, *tmp;
    int removed = 0;

    /* 순회 중 삭제: _safe 버전 필수 */
    list_for_each_entry_safe(s, tmp, &student_list, list) {
        if (s->score < 60) {
            pr_info("Removing failing student: %s (score=%u)\n",
                    s->name, s->score);
            list_del(&s->list);
            kfree(s);
            removed++;
        }
    }
    pr_info("Removed %d failing students\n", removed);
}

/* 모듈 초기화 */
static int __init student_list_init(void)
{
    pr_info("Student List Module: Initializing\n");

    /* 테스트 데이터 추가 */
    add_student(1001, "Alice", 95);
    add_student(1002, "Bob", 58);
    add_student(1003, "Charlie", 72);
    add_student(1004, "Diana", 88);
    add_student(1005, "Eve", 45);

    /* 초기 목록 출력 */
    print_all_students();

    /* 특정 학생 검색 */
    struct student *found = find_student(1003);
    if (found)
        pr_info("Found student: %s (score=%u)\n", found->name, found->score);

    /* 낙제생 제거 */
    remove_failing_students();

    /* 최종 목록 출력 */
    print_all_students();

    return 0;
}

/* 모듈 종료 - 메모리 정리 */
static void __exit student_list_exit(void)
{
    struct student *s, *tmp;

    pr_info("Student List Module: Cleaning up\n");

    /* 남은 모든 학생 제거 */
    list_for_each_entry_safe(s, tmp, &student_list, list) {
        pr_info("Freeing: %s\n", s->name);
        list_del(&s->list);
        kfree(s);
    }

    pr_info("All students freed\n");
}

module_init(student_list_init);
module_exit(student_list_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("MINZKN");
MODULE_DESCRIPTION("list_head practice module");

Makefile

# Makefile for student_list module
obj-m += student_list.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 student_list.ko

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

# 예상 출력:
# [ 1234.567890] Student List Module: Initializing
# [ 1234.567891] Added: ID=1001, Name=Alice, Score=95
# [ 1234.567892] Added: ID=1002, Name=Bob, Score=58
# [ 1234.567893] Added: ID=1003, Name=Charlie, Score=72
# [ 1234.567894] Added: ID=1004, Name=Diana, Score=88
# [ 1234.567895] Added: ID=1005, Name=Eve, Score=45
# [ 1234.567896] === Student List ===
# [ 1234.567897]   [1] ID=1001, Name=Alice               , Score=95
# [ 1234.567898]   [2] ID=1002, Name=Bob                 , Score=58
# [ 1234.567899]   [3] ID=1003, Name=Charlie            , Score=72
# [ 1234.567900]   [4] ID=1004, Name=Diana              , Score=88
# [ 1234.567901]   [5] ID=1005, Name=Eve                , Score=45
# [ 1234.567902] Total: 5 students
# [ 1234.567903] Found student: Charlie (score=72)
# [ 1234.567904] Removing failing student: Bob (score=58)
# [ 1234.567905] Removing failing student: Eve (score=45)
# [ 1234.567906] Removed 2 failing students
# [ 1234.567907] === Student List ===
# [ 1234.567908]   [1] ID=1001, Name=Alice               , Score=95
# [ 1234.567909]   [2] ID=1003, Name=Charlie            , Score=72
# [ 1234.567910]   [3] ID=1004, Name=Diana              , Score=88
# [ 1234.567911] Total: 3 students

# 모듈 언로드
sudo rmmod student_list

# 정리 확인
dmesg | tail -5
# [ 1245.678901] Student List Module: Cleaning up
# [ 1245.678902] Freeing: Alice
# [ 1245.678903] Freeing: Charlie
# [ 1245.678904] Freeing: Diana
# [ 1245.678905] All students freed

연습 과제

부록: 인접 자료구조 선택 가이드

Linked List 문서의 핵심은 list_head, hlist, llist, RCU 리스트의 동작입니다. 아래 내용은 본문 흐름을 보조하는 빠른 선택 가이드이며, 상세 구현은 각 전용 문서에서 다룹니다.

자료구조 선택 요약

실무 운영 체크리스트

연결 리스트 코드는 단순해 보여도 수명주기와 동시성에서 문제가 자주 발생합니다. 아래 항목을 릴리스 전 점검하면 장애 확률을 크게 줄일 수 있습니다.

hlist 레이아웃 심화

앞서 hlist 섹션에서 기본 구조를 살펴보았습니다. 이 섹션에서는 hlist_node의 pprev가 왜 이중 포인터(**pprev)인지, 그리고 이 설계가 해시 테이블 버킷에서 어떤 이점을 제공하는지 깊이 분석합니다.

hlist 메모리 레이아웃 상세

pprev가 이중 포인터인 이유를 코드로 확인해보겠습니다:

/* include/linux/list.h — hlist_del() 핵심 로직 */
static inline void __hlist_del(struct hlist_node *n)
{
    struct hlist_node *next = n->next;
    struct hlist_node **pprev = n->pprev;

    /* pprev가 가리키는 곳(이전 노드의 next 또는 head의 first)을
     * 현재 노드의 next로 덮어쓴다 */
    WRITE_ONCE(*pprev, next);

    /* 다음 노드가 있으면 그 pprev를 현재 노드의 pprev로 업데이트 */
    if (next)
        WRITE_ONCE(next->pprev, pprev);
}

/* 만약 pprev 대신 단순 prev 포인터였다면:
 * - 첫 번째 노드 삭제 시 head->first를 수정해야 함
 * - head 포인터를 별도로 전달받아야 함
 * - pprev 이중 포인터 덕분에 head와 node의 구분 없이 통일된 삭제 가능 */

해시 테이블 버킷에서의 hlist 활용

커널의 DEFINE_HASHTABLE 매크로는 내부적으로 hlist_head 배열을 생성합니다. 1024개 버킷이면 list_head 사용 시 16KB이지만, hlist_head는 8KB만 사용합니다.

/* include/linux/hashtable.h */
#define DEFINE_HASHTABLE(name, bits) \
    struct hlist_head name[1 << (bits)] = \
        { [0 ... ((1 << (bits)) - 1)] = HLIST_HEAD_INIT }

/* 실제 사용 예: PID 해시 테이블 */
static struct hlist_head *pid_hash;
static unsigned int pidhash_shift;

/* kernel/pid.c — PID 검색 */
struct pid *find_pid_ns(int nr, struct pid_namespace *ns)
{
    struct hlist_node *node;
    struct upid *pnr;

    hlist_for_each_entry_rcu(pnr, &pid_hash[pid_hashfn(nr, ns)], pid_chain) {
        if (pnr->nr == nr && pnr->ns == ns)
            return container_of(pnr, struct pid,
                                numbers[ns->level]);
    }
    return NULL;
}

/* hlist RCU 버전 — 해시 테이블에서 RCU 보호 검색 */
rcu_read_lock();
hlist_for_each_entry_rcu(entry, &my_htable[bucket], node) {
    if (entry->key == search_key) {
        result = entry;
        break;
    }
}
rcu_read_unlock();

/* hlist RCU 삽입 */
spin_lock(&htable_lock);
hlist_add_head_rcu(&new_entry->node, &my_htable[bucket]);
spin_unlock(&htable_lock);

/* hlist RCU 삭제 */
spin_lock(&htable_lock);
hlist_del_rcu(&entry->node);
spin_unlock(&htable_lock);
kfree_rcu(entry, rcu);

RCU 리스트 순회 상태 머신

RCU 보호 리스트 섹션에서 기본 API를 살펴보았습니다. 이 섹션에서는 RCU 리스트의 읽기/쓰기 경로가 어떤 상태를 거치며 동작하는지 상태 머신 관점에서 분석합니다.

list_for_each_entry_rcu vs list_for_each_entry 비교

/* 일반 리스트 순회 — 락 보호 필요 */
spin_lock(&my_lock);
list_for_each_entry(item, &my_list, list) {
    /* next 포인터를 직접 역참조 */
    process(item);
}
spin_unlock(&my_lock);

/* RCU 리스트 순회 — lock-free */
rcu_read_lock();
list_for_each_entry_rcu(item, &my_list, list) {
    /* rcu_dereference()로 next를 읽음
     * → 컴파일러 최적화 방지 + 메모리 배리어 */
    process(item);
}
rcu_read_unlock();

/* 핵심 차이: list_for_each_entry_rcu 매크로 내부 */
#define list_for_each_entry_rcu(pos, head, member)         \
    for (pos = list_entry_rcu((head)->next,               \
                    typeof(*pos), member);                \
         &pos->member != (head);                              \
         pos = list_entry_rcu(pos->member.next,              \
                    typeof(*pos), member))

/* list_entry_rcu는 rcu_dereference_raw()를 사용하여
 * DATA_RACE 어노테이션과 READ_ONCE 시맨틱을 보장 */

list_add_rcu/list_del_rcu의 메모리 순서

/* list_add_rcu — rcu_assign_pointer()로 publish */
static inline void list_add_rcu(struct list_head *new,
                                  struct list_head *head)
{
    __list_add_rcu(new, head, head->next);
}

static inline void __list_add_rcu(struct list_head *new,
                                     struct list_head *prev,
                                     struct list_head *next)
{
    /* 신규 노드의 포인터를 먼저 설정 */
    new->next = next;
    new->prev = prev;

    /* rcu_assign_pointer: store-release 시맨틱
     * → 신규 노드의 내용이 reader에게 보이기 전에
     *   포인터 연결이 완료되도록 보장 */
    rcu_assign_pointer(list_next_rcu(prev), new);
    next->prev = new;
}

/* list_del_rcu — next 포인터 유지 */
static inline void list_del_rcu(struct list_head *entry)
{
    __list_del_entry(entry);
    /* 일반 list_del()은 next를 LIST_POISON1로 설정하지만,
     * list_del_rcu()는 next를 그대로 유지!
     * → 진행 중인 reader가 계속 다음 노드로 순회 가능 */
    entry->prev = LIST_POISON2;
}

올바른 Reader/Writer 패턴

/* 올바른 RCU 리스트 사용 패턴 (전체 구조) */
struct my_data {
    int                 value;
    struct list_head    list;
    struct rcu_head     rcu;   /* kfree_rcu 사용 시 필요 */
};

static LIST_HEAD(data_list);
static DEFINE_SPINLOCK(data_lock);

/* Reader: lock 없이 순회 */
int find_value(int target)
{
    struct my_data *d;
    int ret = -ENOENT;

    rcu_read_lock();
    list_for_each_entry_rcu(d, &data_list, list) {
        if (d->value == target) {
            ret = 0;
            break;
        }
    }
    rcu_read_unlock();
    return ret;
}

/* Writer: 삽입 */
int add_data(int value)
{
    struct my_data *d = kmalloc(sizeof(*d), GFP_KERNEL);
    if (!d)
        return -ENOMEM;
    d->value = value;

    spin_lock(&data_lock);
    list_add_rcu(&d->list, &data_list);
    spin_unlock(&data_lock);
    return 0;
}

/* Writer: 삭제 */
void remove_data(struct my_data *d)
{
    spin_lock(&data_lock);
    list_del_rcu(&d->list);
    spin_unlock(&data_lock);

    /* grace period 이후 자동 해제 */
    kfree_rcu(d, rcu);
}

/* Writer: 요소 갱신 (copy-and-replace 패턴) */
void update_data(struct my_data *old, int new_value)
{
    struct my_data *new = kmalloc(sizeof(*new), GFP_KERNEL);
    if (!new)
        return;
    new->value = new_value;

    spin_lock(&data_lock);
    list_replace_rcu(&old->list, &new->list);
    spin_unlock(&data_lock);

    kfree_rcu(old, rcu);
}

list_lru 프레임워크

list_lru는 커널의 메모리 회수(reclaim) 경로에서 사용되는 LRU 리스트 프레임워크입니다. dentry 캐시와 inode 캐시의 축소(shrinking)를 효율적으로 처리하기 위해 설계되었으며, NUMA 노드별/memcg별로 분리된 리스트를 관리합니다.

list_lru 핵심 API

/* include/linux/list_lru.h */

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

/* 항목 추가: LRU tail에 추가 (가장 오래된 위치) */
bool list_lru_add(struct list_lru *lru, struct list_head *item);

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

/* 항목 수 조회 (NUMA 노드별) */
unsigned long list_lru_count_node(struct list_lru *lru, int nid);

/* 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);

/* 콜백 반환값 */
enum lru_status {
    LRU_REMOVED,      /* 항목을 리스트에서 제거함 */
    LRU_REMOVED_RETRY,/* 제거 + 락 재획득 후 재시도 */
    LRU_ROTATE,       /* 항목을 tail로 이동 (유지) */
    LRU_SKIP,         /* 건너뜀 */
    LRU_RETRY,        /* 락 재획득 후 재시도 */
};

dentry 캐시에서의 list_lru 사용

/* fs/dcache.c — dentry LRU 리스트 사용 */
static struct list_lru dentry_lru;

/* dentry가 참조 카운트 0이 되면 LRU에 추가 */
static void d_lru_add(struct dentry *dentry)
{
    list_lru_add(&dentry->d_sb->s_dentry_lru, &dentry->d_lru);
    dentry->d_flags |= DCACHE_LRU_LIST;
}

/* 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);

    /* 참조 카운트 확인 */
    if (dentry->d_lockref.count) {
        /* 사용 중 → LRU에서 제거만 */
        d_lru_shrink_move(lru, dentry);
        return LRU_REMOVED;
    }

    /* 최근 사용됨 → 한 번 더 기회를 줌 (rotate) */
    if (dentry->d_flags & DCACHE_REFERENCED) {
        dentry->d_flags &= ~DCACHE_REFERENCED;
        return LRU_ROTATE;
    }

    /* 회수 대상 → 격리 */
    return LRU_REMOVED;
}

리스트 정렬 (list_sort)

커널은 lib/list_sort.c에 연결 리스트 전용 정렬 함수 list_sort()를 제공합니다. 이 구현은 bottom-up 합병 정렬(merge sort)을 사용하며, 안정 정렬(stable sort)이고 O(n log n) 시간 복잡도를 보장합니다.

list_sort API와 사용법

/* include/linux/list_sort.h */
typedef int (*list_cmp_func_t)(void *priv,
    const struct list_head *a,
    const struct list_head *b);

void list_sort(void *priv, struct list_head *head,
              list_cmp_func_t cmp);

/* 사용 예: 학생 점수순 정렬 */
static int student_cmp(void *priv,
    const struct list_head *a,
    const struct list_head *b)
{
    struct student *sa = list_entry(a, struct student, list);
    struct student *sb = list_entry(b, struct student, list);

    /* 오름차순: sa < sb이면 음수 반환 */
    if (sa->score < sb->score)
        return -1;
    if (sa->score > sb->score)
        return 1;
    return 0;
}

/* 정렬 실행 */
list_sort(NULL, &student_list, student_cmp);

list_sort 내부 구현 핵심

/* lib/list_sort.c — 핵심 알고리즘 (단순화) */

/* merge: 두 정렬된 리스트를 하나로 합병 */
static struct list_head *merge(
    void *priv, list_cmp_func_t cmp,
    struct list_head *a, struct list_head *b)
{
    struct list_head *head, **tail = &head;

    for (;;) {
        /* cmp <= 0 이면 a를 선택 (안정 정렬 보장) */
        if (cmp(priv, a, b) <= 0) {
            *tail = a;
            tail = &a->next;
            a = a->next;
            if (!a) { *tail = b; break; }
        } else {
            *tail = b;
            tail = &b->next;
            b = b->next;
            if (!b) { *tail = a; break; }
        }
    }
    return head;
}

/* list_sort 본체:
 * 1. 원형 리스트를 단방향으로 변환
 * 2. bottom-up으로 점점 큰 블록을 합병
 *    - pending 리스트에 2의 거듭제곱 크기로 누적
 *    - 같은 크기의 블록이 2개 모이면 합병
 * 3. 최종 합병 후 다시 원형 이중 연결 리스트로 복원 */

Lockless 리스트 패턴

앞서 llist 섹션에서 기본 개념을 다루었습니다. 이 섹션에서는 llist_add()의 cmpxchg 기반 구현과, 실제 커널에서의 활용 패턴을 심층적으로 분석합니다.

llist_add 구현 분석

/* include/linux/llist.h */
static inline bool llist_add(struct llist_node *new,
                               struct llist_head *head)
{
    return llist_add_batch(new, new, head);
}

static inline bool llist_add_batch(
    struct llist_node *new_first,
    struct llist_node *new_last,
    struct llist_head *head)
{
    struct llist_node *first;

    do {
        new_last->next = first = READ_ONCE(head->first);
    } while (cmpxchg(&head->first, first, new_first) != first);
    /* cmpxchg 실패 = 다른 CPU가 head->first를 변경함
     * → first를 다시 읽고 new_last->next를 갱신 후 재시도 */

    return !first; /* 이전에 비어있었으면 true */
}

/* 전체 리스트 원자적 회수 */
static inline struct llist_node *llist_del_all(
    struct llist_head *head)
{
    return xchg(&head->first, NULL);
    /* xchg: head->first를 NULL로 설정하고 이전 값 반환
     * → 전체 체인을 한 번에 분리 */
}

커널 내 llist 활용 패턴

/* 패턴 1: IRQ → 스레드 워크 전달 */
struct irq_work {
    struct llist_node    llnode;
    void                (*func)(struct irq_work *);
};

/* IRQ 핸들러 내부 (lock 불가 컨텍스트) */
void irq_work_queue(struct irq_work *work)
{
    /* lock 없이 per-CPU llist에 추가 */
    if (llist_add(&work->llnode, this_cpu_ptr(&raised_list)))
        arch_irq_work_raise();  /* IPI로 워커 깨우기 */
}

/* 패턴 2: per-CPU 객체 해제 일괄 처리 */
static DEFINE_PER_CPU(struct llist_head, dead_objects);

void defer_free(struct my_object *obj)
{
    /* 인터럽트 컨텍스트에서도 안전 */
    llist_add(&obj->lnode, this_cpu_ptr(&dead_objects));
}

void flush_dead_objects(void)
{
    struct llist_node *batch, *pos, *next;

    batch = llist_del_all(this_cpu_ptr(&dead_objects));
    llist_for_each_safe(pos, next, batch) {
        struct my_object *obj = llist_entry(pos,
                                    struct my_object, lnode);
        kfree(obj);
    }
}

/* 패턴 3: RCU 콜백 큐잉 (kernel/rcu/tree.c) */
/* call_rcu() 내부에서 llist를 사용하여
 * grace period 이후 실행할 콜백을 lock-free로 큐잉 */

리스트 접합 연산

리스트 접합(splice)은 두 개의 리스트를 효율적으로 합치는 O(1) 연산입니다. 개별 노드를 하나씩 옮기는 대신, 포인터 4개만 수정하여 전체 리스트를 즉시 연결합니다. 배치 처리, 큐 드레인(drain), 작업 분배 등에서 핵심적으로 사용됩니다.

접합 연산 구현과 사용 패턴

/* include/linux/list.h — list_splice 핵심 구현 */
static inline void __list_splice(
    const struct list_head *list,
    struct list_head *prev,
    struct list_head *next)
{
    struct list_head *first = list->next;
    struct list_head *last = list->prev;

    /* 포인터 4개만 수정 → O(1) */
    first->prev = prev;
    prev->next = first;
    last->next = next;
    next->prev = last;
}

/* 안전한 버전: 빈 리스트 체크 + source 재초기화 */
static inline void list_splice_init(
    struct list_head *list,
    struct list_head *head)
{
    if (!list_empty(list)) {
        __list_splice(list, head, head->next);
        INIT_LIST_HEAD(list);
    }
}

/* 배치 처리 패턴: 락 구간 최소화 */
void process_pending_work(void)
{
    LIST_HEAD(local_list);

    /* 락을 짧게 잡고 전체 리스트를 로컬로 이동 */
    spin_lock(&work_lock);
    list_splice_init(&pending_work, &local_list);
    spin_unlock(&work_lock);

    /* 락 없이 로컬에서 처리 */
    struct work_item *item, *tmp;
    list_for_each_entry_safe(item, tmp, &local_list, list) {
        do_work(item);
        list_del(&item->list);
        kfree(item);
    }
}

/* RCU 안전 접합 패턴 */
void rcu_safe_splice(struct list_head *src,
                      struct list_head *dst)
{
    /* list_splice_init_rcu는 synchronize_rcu 콜백을 받아
     * reader가 src를 순회 중이 아님을 보장한 후 합침 */
    list_splice_init_rcu(src, dst, synchronize_rcu);
}

리스트 디버깅

기본 디버깅 섹션에서 CONFIG_DEBUG_LIST와 KASAN을 소개했습니다. 이 섹션에서는 list_del() vs list_del_init()의 안전성 차이, POISON 값의 작동 원리, 그리고 ftrace/bpftrace를 활용한 실시간 리스트 연산 추적 방법을 다룹니다.

list_del() vs list_del_init() 안전성 비교

/* list_del(): next/prev를 POISON 값으로 설정 */
static inline void list_del(struct list_head *entry)
{
    __list_del_entry(entry);
    entry->next = LIST_POISON1;  /* 0x100 + delta */
    entry->prev = LIST_POISON2;  /* 0x122 + delta */
}
/* → 이후 접근 시 page fault 발생 → 즉시 버그 감지
 * → 하지만 list_empty() 체크 불가 (자기 자신을 가리키지 않으므로)
 * → 재삽입 시도 시 CONFIG_DEBUG_LIST가 경고 */

/* list_del_init(): next/prev를 자기 자신으로 재초기화 */
static inline void list_del_init(struct list_head *entry)
{
    __list_del_entry(entry);
    INIT_LIST_HEAD(entry);
}
/* → list_empty() = true (안전한 상태 확인 가능)
 * → 즉시 list_add()로 다른 리스트에 재삽입 가능
 * → 이중 삭제에도 안전 (빈 리스트에서 삭제는 무해) */

LIST_POISON 값의 동작 원리

/* include/linux/poison.h */
#ifdef CONFIG_ILLEGAL_POINTER_VALUE
#define POISON_POINTER_DELTA _AC(CONFIG_ILLEGAL_POINTER_VALUE, UL)
#else
#define POISON_POINTER_DELTA 0
#endif

#define LIST_POISON1  ((void *) 0x100 + POISON_POINTER_DELTA)
#define LIST_POISON2  ((void *) 0x122 + POISON_POINTER_DELTA)

/* x86_64에서 POISON_POINTER_DELTA = 0
 * → LIST_POISON1 = 0x100, LIST_POISON2 = 0x122
 * → 사용자 공간 주소 범위의 유효하지 않은 주소
 * → 접근 시 즉시 page fault (OOPS/BUG) 발생
 *
 * 디버깅 메시지 예:
 * BUG: unable to handle page fault for address: 0x0000000000000100
 * → 주소가 0x100이면 list_del() 후 next 접근 → LIST_POISON1
 * → 주소가 0x122이면 list_del() 후 prev 접근 → LIST_POISON2 */

ftrace/bpftrace로 리스트 연산 추적

# ftrace: list 관련 함수 추적
# CONFIG_DEBUG_LIST=y 시 list 연산이 outline 함수로 노출됨

# 1. list corruption 이벤트 모니터링
echo 1 > /sys/kernel/tracing/events/list/list_add_corruption/enable
echo 1 > /sys/kernel/tracing/events/list/list_del_corruption/enable
cat /sys/kernel/tracing/trace_pipe

# 2. kprobe로 특정 리스트 연산 추적
echo 'p:my_list_add __list_add new=%di prev=%si next=%dx' > \
    /sys/kernel/tracing/kprobe_events
echo 1 > /sys/kernel/tracing/events/kprobes/my_list_add/enable

# bpftrace: list_del 호출 추적 (호출 스택 포함)
bpftrace -e '
kprobe:__list_del_entry {
    printf("list_del from %s (pid=%d)\n",
           comm, pid);
    print(kstack(5));
}'

# bpftrace: list corruption 감지 시 상세 정보
bpftrace -e '
kprobe:__list_add_valid {
    $next = (struct list_head *)arg1;
    $prev = (struct list_head *)arg2;

    if ($next->prev != $prev) {
        printf("CORRUPTION: next->prev mismatch!\n");
        printf("  next=%p, prev=%p, next->prev=%p\n",
               $next, $prev, $next->prev);
        print(kstack);
    }
}'

서브시스템별 활용 분석

커널 내 실제 사용 사례에서 주요 서브시스템의 list_head 사용을 개괄적으로 살펴보았습니다. 이 섹션에서는 wait_queue, workqueue, 타이머 등의 핵심 서브시스템에서 리스트가 어떤 역할을 하는지 구조적으로 분석합니다.

wait_queue의 리스트 사용

/* include/linux/wait.h */
struct wait_queue_head {
    spinlock_t          lock;
    struct list_head    head;  /* 대기 중인 태스크 리스트 */
};

struct wait_queue_entry {
    unsigned int        flags;
    void                *private;   /* task_struct */
    wait_queue_func_t   func;      /* 깨우기 콜백 */
    struct list_head    entry;     /* wait_queue_head.head에 연결 */
};

/* 대기 → 깨우기 흐름:
 * 1. prepare_to_wait(): entry를 head에 list_add_tail()
 * 2. schedule(): 현재 태스크 슬립
 * 3. wake_up(): head의 리스트를 순회하며 콜백 호출
 * 4. finish_wait(): entry를 list_del_init()으로 제거 */

workqueue의 리스트 사용

/* kernel/workqueue.c — 워크큐 내부 리스트 구조 */
struct pool_workqueue {
    struct list_head    pwqs_node;     /* workqueue_struct에 연결 */
    struct list_head    inactive_works;/* 비활성 작업 리스트 */
    /* ... */
};

struct worker_pool {
    struct list_head    worklist;  /* 대기 중인 work 리스트 */
    struct list_head    idle_list; /* 유휴 worker 리스트 */
    struct list_head    workers;   /* 모든 worker 리스트 */
    /* ... */
};

/* work 제출 흐름:
 * queue_work() → list_add_tail(&work->entry, &pool->worklist)
 * worker_thread() → list_first_entry(&pool->worklist, ...)로 꺼내기 */

서브시스템별 리스트 유형 비교표

성능 분석

성능 고려사항 섹션에서 기본적인 복잡도와 벤치마크를 다루었습니다. 이 섹션에서는 캐시 동작, 메모리 오버헤드, 실제 접근 패턴에 따른 자료구조 선택 가이드를 보다 깊이 분석합니다.

캐시 동작 분석

연결 리스트의 가장 큰 성능 약점은 캐시 비친화성입니다. 노드가 메모리에 흩어져 있으면 순회 시 캐시 미스가 빈번하게 발생합니다.

/* 캐시 친화적 배치 전략 */

/* 전략 1: slab 할당으로 노드 밀집 배치 */
static struct kmem_cache *item_cache;

/* 모듈 초기화 시 */
item_cache = kmem_cache_create("my_item_cache",
    sizeof(struct my_item),
    0,                         /* align: 기본 */
    SLAB_HWCACHE_ALIGN,        /* 캐시 라인 정렬 */
    NULL);

/* 할당: 같은 slab 페이지에 밀집 → 캐시 친화적 */
struct my_item *item = kmem_cache_alloc(item_cache, GFP_KERNEL);

/* 전략 2: list_head를 구조체 앞에 배치 */
struct my_item_optimized {
    struct list_head    list;   /* 오프셋 0: 순회 시 첫 캐시 라인 */
    int                 key;    /* 자주 비교하는 필드도 앞에 */
    /* ... 나머지 필드 ... */
    char                data[256]; /* 드물게 접근하는 필드는 뒤로 */
};

메모리 오버헤드 분석

자료구조 전환 시점

아래 가이드라인은 절대적인 기준이 아니라 경험적 판단 기준입니다. 실제 성능은 반드시 측정으로 확인하세요.

소스 코드 워크스루

이 섹션에서는 include/linux/list.h의 핵심 인라인 함수들이 어떻게 구현되어 있고, 서로 어떤 호출 관계를 갖는지 분석합니다. container_of 매크로의 깊은 동작 원리도 함께 다룹니다.

__list_add() 인라인 구현

/* include/linux/list.h — 모든 삽입의 기반 */
static inline void __list_add(
    struct list_head *new,
    struct list_head *prev,
    struct list_head *next)
{
    /* CONFIG_DEBUG_LIST 시: __list_add_valid() 검증 추가 */
    if (!__list_add_valid(new, prev, next))
        return;

    next->prev = new;    /* 1. next의 prev를 new로 */
    new->next = next;     /* 2. new의 next를 next로 */
    new->prev = prev;     /* 3. new의 prev를 prev로 */
    WRITE_ONCE(prev->next, new); /* 4. prev의 next를 new로
                                  * WRITE_ONCE: 컴파일러가 이 쓰기를
                                  * 분할하거나 재배치하지 못하게 */
}

/* list_add(new, head) = __list_add(new, head, head->next)
 * → head 뒤에 삽입 (LIFO / 스택 동작)
 *
 * list_add_tail(new, head) = __list_add(new, head->prev, head)
 * → head 앞에 삽입 (FIFO / 큐 동작)
 *
 * 같은 헬퍼, 다른 인자 → 코드 중복 제거 */

__list_del() 인라인 구현

/* 삭제의 기반: 이전과 다음을 직접 연결 */
static inline void __list_del(
    struct list_head *prev,
    struct list_head *next)
{
    next->prev = prev;
    WRITE_ONCE(prev->next, next);
}

/* __list_del_entry: 노드에서 prev/next를 추출 후 __list_del 호출 */
static inline void __list_del_entry(struct list_head *entry)
{
    if (!__list_del_entry_valid(entry))
        return;
    __list_del(entry->prev, entry->next);
}

/* __list_del_entry_valid (CONFIG_DEBUG_LIST 시):
 * - entry->prev->next == entry 확인
 * - entry->next->prev == entry 확인
 * - entry != LIST_POISON1 확인
 * → 위반 시 WARN + false 반환 → 삭제 중단 → 손상 확대 방지 */

container_of 매크로 심층 분석

/* include/linux/container_of.h — 전체 구현 */
#define container_of(ptr, type, member) ({                \
    void *__mptr = (void *)(ptr);                          \
    static_assert(                                         \
        __same_type(*(ptr), ((type *)0)->member) ||        \
        __same_type(*(ptr), void),                          \
        "pointer type mismatch in container_of()");         \
    ((type *)(__mptr - offsetof(type, member)));            \
})

/* 분해:
 *
 * 1. void *__mptr = (void *)(ptr)
 *    → const/volatile 제거, 임시 변수에 저장
 *    → ptr을 여러 번 평가하지 않도록 방지 (매크로 안전성)
 *
 * 2. static_assert(__same_type(...))
 *    → ptr의 타입이 type.member의 타입과 일치하는지 컴파일 타임 검증
 *    → 잘못된 member 이름 사용 시 컴파일 에러
 *    → void 타입은 허용 (범용 포인터)
 *
 * 3. (type *)(__mptr - offsetof(type, member))
 *    → member의 주소에서 구조체 내 오프셋을 빼면 구조체 시작 주소
 *    → 결과를 type*로 캐스팅
 *
 * 컴파일러 최적화:
 *    → offsetof는 컴파일 타임 상수
 *    → 뺄셈은 단일 SUB 명령어로 컴파일
 *    → inline 확장 시 오버헤드 제로 */

/* container_of_safe: NULL 안전 버전 (일부 코드에서 사용) */
#define container_of_safe(ptr, type, member) ({            \
    void *__mptr = (void *)(ptr);                          \
    static_assert(                                         \
        __same_type(*(ptr), ((type *)0)->member) ||        \
        __same_type(*(ptr), void),                          \
        "pointer type mismatch");                           \
    IS_ERR_OR_NULL(__mptr) ? NULL :                        \
        ((type *)(__mptr - offsetof(type, member)));        \
})

관련 문서

Linked List와 관련된 다른 주제를 더 깊이 이해하고 싶다면 다음 문서를 참고하세요.

• Red-Black Tree — 트리 자료구조
• Hash Table — 해시 테이블
• XArray — 배열 기반 자료구조
• kfifo — 원형 버퍼 (FIFO 큐)
• 프로세스 스케줄러 — 스케줄러의 리스트 사용