Linked List 심화 (Kernel Linked List In-Depth)

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 구조와 container_of

struct 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);

순회 매크로 (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도 없이 순회할 때 사용 */
}

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에서 로컬 리스트에 추가하고, 하나의 스레드가 수집합니다.

커널 내 실제 사용 사례 (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를 사용하는 것이 일반적입니다.

디버깅 (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

커널 핵심 자료구조와 알고리즘

Linux 커널은 범용 라이브러리를 사용할 수 없으므로 자체 자료구조 라이브러리를 갖추고 있습니다. 각 자료구조는 특정 사용 패턴에 최적화되어 있으며, 잘못된 선택은 성능 저하와 확장성 문제를 야기합니다.

Red-Black Tree (rbtree)

rbtree는 커널에서 가장 널리 사용되는 자가 균형 이진 탐색 트리입니다. CFS 스케줄러, 메모리 관리(VMA), ext4 extent, 타이머 등 O(log n) 검색/삽입/삭제가 필요한 곳에서 사용됩니다.

/* include/linux/rbtree.h — 기본 사용법 */
struct my_node {
    struct rb_node rb;
    unsigned long key;
    void *data;
};

struct rb_root my_tree = RB_ROOT;

/* 삽입 → rb_link_node() + rb_insert_color() */
/* 삭제 → rb_erase() */
/* 검색 → rb_entry()로 container 접근, 직접 비교 */
/* 순회 → rb_first() / rb_next() */

Hash Table (hashtable)

커널 해시테이블은 hlist(해시 리스트) 배열로 구현됩니다. 체이닝 방식으로 충돌을 처리하며, O(1) 평균 검색 시간을 제공합니다.

/* include/linux/hashtable.h */

/* 정적 해시테이블 선언 (2^bits 크기) */
DEFINE_HASHTABLE(my_htable, 8);  /* 256 버킷 (2^8) */

struct my_item {
    int id;
    char name[32];
    struct hlist_node hash;  /* 해시 체인 노드 */
};

/* 삽입 */
struct my_item *item = kzalloc(sizeof(*item), GFP_KERNEL);
item->id = 42;
hash_add(my_htable, &item->hash, item->id);  /* 키: item->id */

/* 검색 */
struct my_item *found;
hash_for_each_possible(my_htable, found, hash, target_id) {
    if (found->id == target_id)
        break;  /* 발견 */
}

/* 삭제 */
hash_del(&item->hash);

/* 전체 순회 */
struct my_item *cur;
int bkt;
hash_for_each(my_htable, bkt, cur, hash) {
    pr_info("item: %d %s\n", cur->id, cur->name);
}

/* RCU 보호 해시테이블 */
hash_add_rcu(my_htable, &item->hash, item->id);
hash_del_rcu(&item->hash);
hash_for_each_possible_rcu(my_htable, found, hash, key) { ... }

/* 해시 함수 (include/linux/hash.h) */
unsigned long h = hash_long(key, HASH_BITS(my_htable));
u32 h32 = hash_32(key32, bits);
u32 hstr = full_name_hash(NULL, name, strlen(name));

XArray (Radix Tree 대체)

XArray는 커널 5.0+에서 radix tree를 대체하는 자료구조입니다. 정수 키를 포인터 값에 매핑하며, 페이지 캐시, IDR(ID Radix tree), 파일 시스템 등에서 핵심적으로 사용됩니다.

/* include/linux/xarray.h — 기본 사용법 */
DEFINE_XARRAY(my_xa);

xa_store(&my_xa, index, ptr, GFP_KERNEL);  /* 저장 */
void *val = xa_load(&my_xa, index);         /* 로드 */
xa_erase(&my_xa, index);                    /* 삭제 */

/* 순회 */
unsigned long idx;
void *entry;
xa_for_each(&my_xa, idx, entry) { /* ... */ }

bitmap — 비트맵 연산

커널 비트맵은 CPU 마스크, IRQ 할당, 리소스 관리, 페이지 프레임 추적 등 커널 전반에서 사용되는 핵심 자료구조입니다. unsigned long 배열 기반으로 워드 단위 병렬 처리를 통해 높은 성능을 제공합니다.

내부 표현과 선언

/* include/linux/types.h */
#define DECLARE_BITMAP(name, bits) \
    unsigned long name[BITS_TO_LONGS(bits)]

/* BITS_TO_LONGS(bits) = DIV_ROUND_UP(bits, BITS_PER_LONG)
 * 64비트 시스템: BITS_PER_LONG = 64
 * DECLARE_BITMAP(my_bits, 256) → unsigned long my_bits[4]
 * DECLARE_BITMAP(flags, 100)   → unsigned long flags[2]  (128비트 할당, 100비트 사용) */

/* 스택/전역 선언 */
DECLARE_BITMAP(my_bits, 256);  /* 256비트 비트맵 */

/* 동적 할당 (include/linux/bitmap.h) */
unsigned long *dyn = bitmap_alloc(1024, GFP_KERNEL);   /* 1024비트 */
unsigned long *dyn = bitmap_zalloc(1024, GFP_KERNEL);  /* 0 초기화 */
bitmap_free(dyn);

/* 비트 레이아웃 (64비트 시스템, 리틀 엔디안)
 *
 *   word[0]                word[1]                word[2]    word[3]
 *  ┌─────────────────────┬─────────────────────┬──────────┬──────────┐
 *  │ bit 0 ... bit 63    │ bit 64 ... bit 127  │ 128..191 │ 192..255 │
 *  └─────────────────────┴─────────────────────┴──────────┴──────────┘
 *
 *  bit N → word index: N / BITS_PER_LONG
 *          bit offset: N % BITS_PER_LONG
 */

단일 비트 연산

/* include/asm-generic/bitops/ — 아키텍처별 최적화 제공 */

/* ── Atomic 비트 연산 (SMP 안전, 락 불필요) ── */
set_bit(42, my_bits);              /* 비트 42 설정 (LOCK prefix on x86) */
clear_bit(42, my_bits);            /* 비트 42 해제 */
change_bit(42, my_bits);           /* 비트 42 토글 */

/* ── Atomic test-and-modify (이전 값 반환) ── */
bool old = test_and_set_bit(42, my_bits);    /* 설정 후 이전 값 */
bool old = test_and_clear_bit(42, my_bits);  /* 해제 후 이전 값 */
bool old = test_and_change_bit(42, my_bits); /* 토글 후 이전 값 */

/* ── Non-atomic 비트 연산 (빠르지만 동시 접근 시 보호 필요) ── */
__set_bit(42, my_bits);            /* LOCK prefix 없음 */
__clear_bit(42, my_bits);
__change_bit(42, my_bits);
bool old = __test_and_set_bit(42, my_bits);

/* ── 읽기 전용 ── */
bool v = test_bit(42, my_bits);    /* 비트 42 검사 (항상 non-atomic) */

비트맵 전체 연산 (Bulk Operations)

/* include/linux/bitmap.h — 워드 단위로 동작하여 개별 비트 루프보다 훨씬 빠름 */

/* ── 초기화 ── */
bitmap_zero(dst, nbits);           /* 모든 비트 0 */
bitmap_fill(dst, nbits);           /* 모든 비트 1 */
bitmap_copy(dst, src, nbits);      /* src → dst 복사 */

/* ── 집합 연산 (논리 연산) ── */
bitmap_and(dst, a, b, nbits);      /* dst = a AND b (교집합) */
bitmap_or(dst, a, b, nbits);       /* dst = a OR b  (합집합) */
bitmap_xor(dst, a, b, nbits);      /* dst = a XOR b (대칭 차집합) */
bitmap_andnot(dst, a, b, nbits);   /* dst = a AND (NOT b) (차집합) */
bitmap_complement(dst, src, nbits);/* dst = NOT src (여집합) */

/* ── 시프트 ── */
bitmap_shift_left(dst, src, shift, nbits);  /* 왼쪽 시프트 */
bitmap_shift_right(dst, src, shift, nbits); /* 오른쪽 시프트 */

/* ── 비교/검사 ── */
bool eq   = bitmap_equal(a, b, nbits);      /* a == b ? */
bool mt   = bitmap_empty(bits, nbits);       /* 모든 비트 0? */
bool full = bitmap_full(bits, nbits);        /* 모든 비트 1? */
bool sub  = bitmap_subset(a, b, nbits);     /* a ⊆ b ? */
bool hit  = bitmap_intersects(a, b, nbits);  /* a ∩ b ≠ ∅ ? */

/* ── 카운팅 ── */
unsigned int w = bitmap_weight(bits, nbits); /* popcount: 1인 비트 수 */
/* 내부적으로 hweight_long() 사용 → x86: POPCNT 명령어 (SSE4.2+) */

비트 검색과 순회

/* include/linux/find.h */
unsigned long pos;

/* ── 첫 번째 비트 찾기 ── */
pos = find_first_bit(my_bits, 256);      /* 첫 번째 1 비트 (없으면 nbits 반환) */
pos = find_first_zero_bit(my_bits, 256); /* 첫 번째 0 비트 */
pos = find_last_bit(my_bits, 256);       /* 마지막 1 비트 */

/* ── offset부터 다음 비트 찾기 ── */
pos = find_next_bit(my_bits, 256, offset);      /* offset부터 다음 1 비트 */
pos = find_next_zero_bit(my_bits, 256, offset); /* offset부터 다음 0 비트 */
pos = find_next_and_bit(a, b, 256, offset);    /* a AND b에서 다음 1 비트 */

/* ── 순회 매크로 ── */
for_each_set_bit(pos, my_bits, 256) {
    /* 1인 모든 비트를 순서대로 방문 */
    pr_info("bit %lu is set\n", pos);
}

for_each_clear_bit(pos, my_bits, 256) {
    /* 0인 모든 비트를 순서대로 방문 */
}

for_each_set_bit_from(pos, my_bits, 256) {
    /* pos 위치부터 시작하여 1인 비트 순회 */
    /* pos는 호출 전에 시작 위치로 초기화해야 함 */
}

/* for_each_set_bit 내부 구현 원리:
 *   #define for_each_set_bit(bit, addr, size)             \
 *       for ((bit) = 0;                                    \
 *            (bit) = find_next_bit((addr), (size), (bit)), \
 *            (bit) < (size);                                \
 *            (bit)++)
 *
 * find_next_bit()는 워드 단위로 건너뛰므로
 * 0이 많은 희소 비트맵에서 매우 효율적 */

비트맵 문자열 파싱과 출력

/* sysfs, procfs 인터페이스에서 비트맵을 문자열로 교환 */

/* ── 리스트 형식: "0-3,8,12-15" ── */
DECLARE_BITMAP(mask, 256);
bitmap_parselist("0-3,8,12-15", mask, 256);
/* 결과: 비트 0,1,2,3,8,12,13,14,15가 설정됨 */

/* 사용자 공간에서 입력 */
bitmap_parselist_user(ubuf, ulen, mask, 256);

/* ── 16진수 형식: "ff0f" ── */
bitmap_parse("ff0f", 4, mask, 256);
/* 결과: 비트 0-3, 8-15 설정 (0x0ff0f → 이진수 1111111100001111) */

/* ── 출력 ── */
char buf[128];
bitmap_list_string(buf, sizeof(buf), mask, 256);
/* buf = "0-3,8-15" */

bitmap_string(buf, sizeof(buf), mask, 256);
/* buf = "0000ff0f" (16진수) */

/* printk에서 직접 출력 */
pr_info("mask: %*pbl\n", 256, mask);  /* 리스트 형식: "0-3,8-15" */
pr_info("mask: %*pb\n", 256, mask);   /* 16진수 형식 */

cpumask — CPU 비트맵 특수화

/* include/linux/cpumask.h
 * cpumask_t는 DECLARE_BITMAP(bits, NR_CPUS)를 감싸는 구조체
 * NR_CPUS: 커널 설정에서 지정하는 최대 CPU 수 (보통 4096) */

/* ── 시스템 전역 CPU 마스크 (읽기 전용) ── */
const struct cpumask *cpu_possible_mask;  /* 존재할 수 있는 모든 CPU */
const struct cpumask *cpu_present_mask;   /* 물리적으로 존재하는 CPU */
const struct cpumask *cpu_online_mask;    /* 현재 활성화된 CPU */
const struct cpumask *cpu_active_mask;    /* 스케줄러가 사용하는 CPU */

/* 관계: possible ⊇ present ⊇ online ⊇ active
 * CPU hotplug 시: present → online → active 순으로 전이 */

/* ── 개별 CPU 연산 ── */
struct cpumask mask;
cpumask_clear(&mask);                     /* 모든 비트 0 */
cpumask_set_cpu(0, &mask);               /* CPU 0 설정 */
cpumask_set_cpu(2, &mask);               /* CPU 2 설정 */
cpumask_clear_cpu(0, &mask);             /* CPU 0 해제 */
bool on = cpumask_test_cpu(2, &mask);   /* CPU 2 검사 */

/* ── 집합 연산 ── */
cpumask_and(&dst, &a, &b);               /* 교집합 */
cpumask_or(&dst, &a, &b);                /* 합집합 */
cpumask_andnot(&dst, &a, &b);            /* 차집합 */
bool hit = cpumask_intersects(&a, &b);   /* 교집합 비어있지 않은지 */
bool sub = cpumask_subset(&a, &b);       /* a ⊆ b? */

/* ── 카운팅과 선택 ── */
unsigned int n = cpumask_weight(&mask);   /* 설정된 CPU 수 */
bool empty = cpumask_empty(&mask);        /* CPU 없는지 */
unsigned int f = cpumask_first(&mask);    /* 첫 번째 CPU */
unsigned int nxt = cpumask_next(0, &mask);/* CPU 0 다음 CPU */
unsigned int any = cpumask_any(&mask);    /* 아무 CPU 하나 */
unsigned int local = cpumask_local_spread(0, node); /* NUMA 노드 고려 선택 */

/* ── 순회 ── */
int cpu;
for_each_cpu(cpu, &mask) { ... }         /* mask의 모든 CPU */
for_each_online_cpu(cpu) { ... }          /* 온라인 CPU 전체 */
for_each_possible_cpu(cpu) { ... }        /* 가능한 CPU 전체 */
for_each_present_cpu(cpu) { ... }         /* 존재하는 CPU 전체 */
for_each_cpu_and(cpu, &a, &b) { ... }    /* a ∩ b의 CPU */

nodemask — NUMA 노드 비트맵

/* include/linux/nodemask.h
 * nodemask_t: MAX_NUMNODES 크기의 비트맵
 * cpumask와 유사한 API, NUMA 메모리 정책에서 핵심 */

nodemask_t nodes = NODE_MASK_NONE;
node_set(0, nodes);                        /* 노드 0 설정 */
node_clear(0, nodes);                      /* 노드 0 해제 */
bool t = node_isset(0, nodes);             /* 노드 0 검사 */

nodes_and(dst, a, b);                      /* 교집합 */
nodes_or(dst, a, b);                       /* 합집합 */
int w = nodes_weight(nodes);                /* 설정된 노드 수 */

int nid;
for_each_node_mask(nid, nodes) { ... }     /* 마스크의 모든 노드 */
for_each_online_node(nid) { ... }          /* 온라인 노드 전체 */

실전 활용 예제

/* 예제 1: IRQ affinity 설정 — 특정 CPU에만 인터럽트 분배 */
static int setup_irq_affinity(struct pci_dev *pdev, int nvecs)
{
    int i, cpu;
    int node = dev_to_node(&pdev->dev);

    for (i = 0; i < nvecs; i++) {
        struct cpumask mask;
        cpumask_clear(&mask);

        /* 같은 NUMA 노드의 CPU를 라운드 로빈 할당 */
        cpu = cpumask_local_spread(i, node);
        cpumask_set_cpu(cpu, &mask);

        irq_set_affinity_hint(pci_irq_vector(pdev, i), &mask);
    }
    return 0;
}

/* 예제 2: 리소스 ID 할당 — 비트맵으로 사용 가능한 슬롯 관리 */
struct slot_allocator {
    DECLARE_BITMAP(used, 1024);  /* 최대 1024개 슬롯 */
    int max_slots;
    spinlock_t lock;
};

static int alloc_slot(struct slot_allocator *sa)
{
    int slot;
    spin_lock(&sa->lock);
    slot = find_first_zero_bit(sa->used, sa->max_slots);
    if (slot < sa->max_slots)
        __set_bit(slot, sa->used);  /* 락 보호 하에 non-atomic OK */
    else
        slot = -ENOSPC;
    spin_unlock(&sa->lock);
    return slot;
}

static void free_slot(struct slot_allocator *sa, int slot)
{
    spin_lock(&sa->lock);
    __clear_bit(slot, sa->used);
    spin_unlock(&sa->lock);
}

/* 예제 3: 비트 기반 플래그 락 (wait_on_bit 패턴) */
#define MY_FLAG_LOCKED  0
#define MY_FLAG_DIRTY   1
#define MY_FLAG_UPTODATE 2

struct my_object {
    unsigned long flags;   /* 비트 플래그 (atomic 연산 사용) */
    /* ... */
};

/* 페이지 캐시의 PG_locked와 동일한 패턴 */
static void lock_object(struct my_object *obj)
{
    while (test_and_set_bit(MY_FLAG_LOCKED, &obj->flags))
        cpu_relax();  /* 또는 wait_on_bit() 사용 */
}

static void unlock_object(struct my_object *obj)
{
    clear_bit(MY_FLAG_LOCKED, &obj->flags);
    smp_mb__after_atomic();  /* 메모리 배리어 */
    wake_up_bit(&obj->flags, MY_FLAG_LOCKED);
}

비트맵 API 요약 테이블

정렬과 검색 알고리즘

/* include/linux/sort.h */
/* 커널 내장 정렬: heapsort (not quicksort!) */
/* 이유: O(n log n) 최악 보장, 스택 사용량 일정, in-place */
sort(array, n_elements, element_size, cmp_func, swap_func);

static int my_cmp(const void *a, const void *b)
{
    const struct my_item *ia = a, *ib = b;
    if (ia->key < ib->key) return -1;
    if (ia->key > ib->key) return 1;
    return 0;
}
sort(items, count, sizeof(*items), my_cmp, NULL);
/* swap_func이 NULL이면 generic swap 사용 */

/* 이진 검색 */
/* include/linux/bsearch.h */
void *bsearch(const void *key, const void *base,
              size_t num, size_t size,
              cmp_func_t cmp);

struct my_item *found = bsearch(&target_key, items, count,
                                  sizeof(*items), my_cmp);

list_sort — 연결 리스트 정렬

/* include/linux/list_sort.h */
/* Bottom-up merge sort: 안정(stable), O(n log n), O(1) 추가 공간 */
list_sort(priv, &my_list, my_cmp);

static int my_cmp(void *priv,
                   const struct list_head *a,
                   const struct list_head *b)
{
    struct my_item *ia = list_entry(a, struct my_item, list);
    struct my_item *ib = list_entry(b, struct my_item, list);
    /* 음수: a < b, 0: a == b, 양수: a > b */
    return ia->priority - ib->priority;
}

kfifo — 커널 FIFO 링 버퍼

/* include/linux/kfifo.h */
/* Lock-free single producer / single consumer FIFO */

/* 정적 선언 (크기는 2의 거듭제곱이어야 함) */
DECLARE_KFIFO(my_fifo, struct my_event, 256);
INIT_KFIFO(my_fifo);

/* 동적 할당 */
struct kfifo fifo;
kfifo_alloc(&fifo, 4096, GFP_KERNEL);  /* 바이트 FIFO */

/* 넣기/빼기 */
kfifo_in(&my_fifo, &event, 1);     /* 하나 삽입, 반환: 삽입 수 */
kfifo_out(&my_fifo, &event, 1);    /* 하나 추출 */
kfifo_peek(&my_fifo, &event);      /* 꺼내지 않고 확인 */

/* 상태 확인 */
bool empty = kfifo_is_empty(&my_fifo);
bool full  = kfifo_is_full(&my_fifo);
unsigned int len = kfifo_len(&my_fifo);    /* 사용 중 */
unsigned int avail = kfifo_avail(&my_fifo); /* 여유 공간 */

/* 사용자 공간으로 직접 복사 */
kfifo_to_user(&my_fifo, buf, count, &copied);

/* 해제 */
kfifo_free(&fifo);

IDR / IDA — 정수 ID 할당

IDR(ID Radix tree)은 정수 ID와 포인터를 매핑하는 자료구조이고, IDA(ID Allocator)는 포인터 매핑 없이 고유 정수 ID만 할당합니다. 커널 4.20부터 내부적으로 XArray 기반으로 재구현되었으며, 파일 디스크립터, 디바이스 번호, 네트워크 인터페이스 인덱스 등 커널 전반에서 사용됩니다.

내부 구조

/* include/linux/idr.h */
struct idr {
    struct xarray  idr_rt;    /* 내부 XArray (radix tree) */
    unsigned int   idr_base;  /* ID 시작 오프셋 (기본 0) */
    unsigned int   idr_next;  /* 다음 할당 힌트 (cyclic용) */
};

/* XArray 기반 radix tree 구조:
 *
 *   IDR                    XArray (radix tree)
 *  ┌──────────┐           ┌─────────┐
 *  │ idr_rt ──┼──────────→│ xa_head │
 *  │ idr_base │           └────┬────┘
 *  │ idr_next │                │
 *  └──────────┘           ┌────▼────┐
 *                         │  node   │  ← 64개 슬롯 (BITS_PER_XA_VALUE)
 *                         │ [0..63] │
 *                         └─┬──┬──┬─┘
 *                    ┌──────┘  │  └──────┐
 *                    ▼         ▼         ▼
 *                 leaf/ptr  leaf/ptr  leaf/ptr
 *
 * ID → XArray 인덱스(id - idr_base)로 변환하여 포인터 저장/검색
 * 시간복잡도: O(log₆₄ n) ≈ 대부분 상수 시간 */

/* IDA는 비트맵 최적화 사용 — 포인터 저장 불필요하므로
 * XArray 리프 노드에 비트맵(1024비트)을 저장하여 공간 효율 극대화 */
struct ida {
    struct xarray  xa;
};

IDR — 정수 → 포인터 매핑

/* ── 선언과 초기화 ── */
DEFINE_IDR(my_idr);                   /* 정적 선언 + 초기화 */

struct idr my_idr;
idr_init(&my_idr);                    /* 동적 초기화 (base=0) */
idr_init_base(&my_idr, 1);            /* base=1: ID를 1부터 할당 */

/* ── ID 할당 ── */
int id;

/* 기본 할당: [min, max) 범위에서 가장 작은 빈 ID */
id = idr_alloc(&my_idr, ptr, 0, 0, GFP_KERNEL);
/* min=0, max=0 → [0, INT_MAX) 전체 범위
 * 반환: 할당된 ID (≥0) 또는 음수 에러 (-ENOMEM, -ENOSPC) */

id = idr_alloc(&my_idr, ptr, 100, 200, GFP_KERNEL);
/* [100, 200) 범위에서 할당 */

/* u32 ID 할당 (커널 5.x+, 큰 ID 범위 지원) */
u32 next_id = 0;
idr_alloc_u32(&my_idr, ptr, &next_id, 4095, GFP_KERNEL);
/* next_id에 할당된 ID 저장, max=4095 */

/* Cyclic 할당: 순차적으로 증가, 최대값 도달 시 처음부터 재사용 */
id = idr_alloc_cyclic(&my_idr, ptr, 0, 0, GFP_KERNEL);
/* POSIX PID 할당과 동일한 패턴:
 * 이전 할당 ID 다음부터 탐색 → ID 재사용 지연 → ABA 문제 완화
 * 내부적으로 idr->idr_next를 활용 */

/* ── 검색 ── */
void *ptr = idr_find(&my_idr, id);    /* ID → 포인터 (없으면 NULL) */

/* ── 교체 ── */
void *old = idr_replace(&my_idr, new_ptr, id);
/* ID는 유지, 포인터만 교체. 반환: 이전 포인터 또는 ERR_PTR */

/* ── 제거 ── */
void *removed = idr_remove(&my_idr, id);
/* ID 해제 + 연결된 포인터 반환 (포인터 자체의 메모리 해제는 호출자 책임) */

/* ── 정리 ── */
idr_destroy(&my_idr);
/* 내부 XArray 노드만 해제. 포인터가 가리키는 객체는 해제하지 않음!
 * 반드시 먼저 idr_for_each 등으로 개별 객체 정리 필요 */

IDR 순회

/* ── 콜백 기반 순회 ── */
static int my_callback(int id, void *ptr, void *data)
{
    struct my_obj *obj = ptr;
    pr_info("id=%d, obj=%p\n", id, obj);
    return 0;  /* 0: 계속, 비영: 중단 (반환값이 idr_for_each 반환값) */
}
idr_for_each(&my_idr, my_callback, context_data);

/* ── 매크로 기반 순회 (권장) ── */
struct my_obj *obj;
int id;

/* 모든 항목 순회 */
idr_for_each_entry(&my_idr, obj, id) {
    pr_info("id=%d name=%s\n", id, obj->name);
}

/* 특정 ID부터 순회 */
int start_id = 100;
idr_for_each_entry_continue(&my_idr, obj, start_id) {
    /* id=100 이후의 항목들 */
}

/* 가장 가까운 항목 찾기 */
void *ptr = idr_get_next(&my_idr, &next_id);
/* next_id 이상의 가장 작은 ID를 가진 항목 반환
 * next_id가 업데이트됨 → 반복 호출로 순회 가능 */

IDR 동기화와 RCU

/* IDR은 내부 락을 제공하지 않음 → 호출자가 동기화 책임
 *
 * 일반적인 패턴:
 * - 수정 (alloc/remove/replace): mutex 또는 spinlock 필요
 * - 읽기 (find): rcu_read_lock()으로 보호 가능 (락 없이!)
 */

struct my_subsystem {
    struct idr   object_idr;
    spinlock_t   idr_lock;     /* 수정 연산 보호 */
};

/* 할당 (수정 → 락 필요) */
static int register_object(struct my_subsystem *sys,
                           struct my_obj *obj)
{
    int id;
    spin_lock(&sys->idr_lock);
    id = idr_alloc(&sys->object_idr, obj, 0, 0, GFP_NOWAIT);
    spin_unlock(&sys->idr_lock);
    return id;
}

/* 검색 (읽기 → RCU만으로 충분) */
static struct my_obj *find_object(struct my_subsystem *sys,
                                    int id)
{
    struct my_obj *obj;
    rcu_read_lock();
    obj = idr_find(&sys->object_idr, id);
    if (obj && !kref_get_unless_zero(&obj->ref))
        obj = NULL;  /* 해제 중인 객체 */
    rcu_read_unlock();
    return obj;
}

/* 제거 (수정 → 락 필요, 객체는 RCU 지연 해제) */
static void unregister_object(struct my_subsystem *sys,
                               int id)
{
    struct my_obj *obj;
    spin_lock(&sys->idr_lock);
    obj = idr_remove(&sys->object_idr, id);
    spin_unlock(&sys->idr_lock);
    if (obj)
        kfree_rcu(obj, rcu);  /* RCU grace period 후 해제 */
}

IDR Preload — Atomic 컨텍스트 지원

/* spinlock 내에서 idr_alloc()을 안전하게 사용하는 패턴
 * idr_preload()가 미리 메모리를 할당 → 이후 alloc에서 할당 불필요 */

idr_preload(GFP_KERNEL);              /* ① preempt_disable() + 메모리 사전 할당 */
spin_lock(&my_lock);                  /* ② 락 획득 */

id = idr_alloc(&my_idr, obj, 0, 0, GFP_NOWAIT);
/* GFP_NOWAIT이지만 preload된 메모리 사용 → 실패 거의 없음 */

spin_unlock(&my_lock);                /* ③ 락 해제 */
idr_preload_end();                    /* ④ preempt_enable() */

/* 전형적 사용처: 파일 디스크립터 할당 (files_struct->fdt)
 * 인터럽트 핸들러 등록 (irq_desc 할당) */

IDA — 순수 ID 할당기

/* IDA: 포인터 매핑이 필요 없을 때 IDR보다 효율적
 * 내부적으로 XArray + 비트맵 사용 → 메모리 절약
 * IDR: ID당 ~포인터 1개 저장, IDA: 1024개 ID를 비트맵 1개로 관리 */

/* ── 선언과 초기화 ── */
DEFINE_IDA(my_ida);                   /* 정적 선언 */

struct ida my_ida;
ida_init(&my_ida);                    /* 동적 초기화 */

/* ── ID 할당 ── */
int id;
id = ida_alloc(&my_ida, GFP_KERNEL);
/* 0부터 가장 작은 빈 ID 할당. 반환: ID (≥0) 또는 -ENOMEM */

id = ida_alloc_min(&my_ida, 100, GFP_KERNEL);
/* 최소 100 이상의 ID */

id = ida_alloc_max(&my_ida, 4095, GFP_KERNEL);
/* 최대 4095 이하의 ID. 범위 초과 시 -ENOSPC */

id = ida_alloc_range(&my_ida, 100, 200, GFP_KERNEL);
/* [100, 200] 범위에서 할당 (양 끝 포함) */

/* ── ID 해제 ── */
ida_free(&my_ida, id);
/* 해당 ID를 반환하여 재사용 가능하게 함 */

/* ── 상태 확인 ── */
bool empty = ida_is_empty(&my_ida);   /* 할당된 ID가 없는지 */

/* ── 정리 ── */
ida_destroy(&my_ida);
/* 모든 내부 자원 해제. 미해제 ID가 있어도 안전하지만,
 * 논리적으로는 모든 ida_free()를 먼저 호출하는 것이 올바름 */

실전 활용 예제

/* 예제 1: 디바이스 드라이버의 인스턴스 관리 */
static DEFINE_IDR(mydev_idr);
static DEFINE_MUTEX(mydev_mutex);

struct mydev {
    int              id;
    struct device   *dev;
    struct cdev      cdev;
    /* ... */
};

static int mydev_probe(struct platform_device *pdev)
{
    struct mydev *md;
    int ret;

    md = devm_kzalloc(&pdev->dev, sizeof(*md), GFP_KERNEL);
    if (!md)
        return -ENOMEM;

    mutex_lock(&mydev_mutex);
    ret = idr_alloc(&mydev_idr, md, 0, 256, GFP_KERNEL);
    mutex_unlock(&mydev_mutex);
    if (ret < 0)
        return ret;

    md->id = ret;
    dev_info(&pdev->dev, "registered as mydev%d\n", md->id);
    return 0;
}

static int mydev_remove(struct platform_device *pdev)
{
    struct mydev *md = platform_get_drvdata(pdev);

    mutex_lock(&mydev_mutex);
    idr_remove(&mydev_idr, md->id);
    mutex_unlock(&mydev_mutex);
    return 0;
}

/* 예제 2: IDA로 minor 번호 관리 */
static DEFINE_IDA(mychar_ida);
#define MYCHAR_MAX_DEVS 64

static int mychar_alloc_minor(void)
{
    int minor = ida_alloc_max(&mychar_ida,
                               MYCHAR_MAX_DEVS - 1,
                               GFP_KERNEL);
    if (minor < 0)
        pr_err("no free minor numbers\n");
    return minor;
}

static void mychar_free_minor(int minor)
{
    ida_free(&mychar_ida, minor);
}

/* 예제 3: Cyclic ID로 세션 관리 (PID 스타일) */
static DEFINE_IDR(session_idr);
static DEFINE_SPINLOCK(session_lock);

static int create_session(struct session *sess)
{
    int id;

    idr_preload(GFP_KERNEL);
    spin_lock(&session_lock);

    id = idr_alloc_cyclic(&session_idr, sess,
                           1, 0, GFP_NOWAIT);
    /* min=1 (0은 예약), max=0 (INT_MAX)
     * cyclic: 1→2→3→...→재사용, 최근 해제 ID 재사용 지연 */

    spin_unlock(&session_lock);
    idr_preload_end();

    if (id < 0)
        return id;

    sess->id = id;
    return 0;
}

IDR vs IDA 비교

자료구조 선택 가이드