IDR/IDA (ID Allocator)

IDR과 IDA는 커널에서 희소한 정수 ID를 다루는 공용 할당기입니다. IDR은 ID를 포인터에 연결하고, IDA는 ID 자체만 예약합니다. 공식 문서는 새 코드에서 XArray 직접 사용을 권장하지만, PID namespace처럼 기존 커널 경로에서는 IDR/IDA가 여전히 중요한 인터페이스입니다.

개요 (Overview)

IDR(ID Radix tree)과 IDA(ID Allocator)는 "작은 정수 식별자를 빈 슬롯에서 뽑아 재사용합니다"는 공통 문제를 푸는 커널 공용 도구입니다. 대표적인 문제 유형은 PID 번호, 네트워크 프로토콜의 식별자, 드라이버 인스턴스 번호, 서브시스템 내부 핸들처럼 희소한 정수 공간을 다루는 경우입니다.

IDR은 할당된 정수와 포인터를 함께 저장합니다. 반대로 IDA는 포인터를 저장하지 않고 "이 정수가 현재 사용 중인지"만 추적합니다. 그래서 IDA는 메모리 효율이 좋고, IDR은 조회 편의성이 좋습니다.

개념 구조와 커널 내부 경계

IDR을 이해할 때 가장 중요한 점은 "번호를 뽑는 규칙"과 "객체를 살아 있게 유지하는 규칙"이 분리되어 있는 점입니다. IDR은 ID를 고르고 포인터를 저장하는 데 도움을 주지만, 객체의 refcount, RCU 해제 시점, 상위 서브시스템 락 계층은 대신 설계해 주지 않습니다.

IDR API

공식 문서 기준으로 IDR 사용의 핵심은 세 가지입니다. 할당(idr_alloc, idr_alloc_cyclic, idr_alloc_u32), 조회(idr_find), 수정/해제(idr_replace, idr_remove)입니다. 나머지 iterator와 preload는 실전에서 빠지기 쉬운 보조 도구입니다.

기본 사용 표면

/* 정적/동적 초기화 */
DEFINE_IDR(session_idr);
struct idr dyn_idr;
idr_init(&dyn_idr);

/* 1 이상 ID를 잡고 포인터 저장 */
int id = idr_alloc(&session_idr, session, 1, 0, GFP_KERNEL);

/* 순환 재사용 */
int cyc = idr_alloc_cyclic(&session_idr, session, 1, 0, GFP_KERNEL);

/* u32 상한 지정. max는 inclusive */
u32 nextid = 1024;
idr_alloc_u32(&session_idr, session, &nextid, 65535, GFP_KERNEL);

/* 조회와 제거 */
session = idr_find(&session_idr, id);
old = idr_remove(&session_idr, id);

/* 슬롯 예약 후 publish */
id = idr_alloc(&session_idr, NULL, 1, 0, GFP_KERNEL);
idr_replace(&session_idr, session, id);

잠금 안쪽 할당과 preload 패턴

같은 IDR에 대한 writer 경합(Contention)을 막으려면 상위 락을 잡아야 합니다. 문제는 그 락을 잡은 상태에서 GFP_KERNEL 할당이 곤란할 수 있는 점입니다. 이때 공식 문서가 제시하는 안전한 습관이 idr_preload()입니다.

DEFINE_IDR(ctx_idr);
static DEFINE_SPINLOCK(ctx_lock);

int ctx_register(struct ctx *ctx)
{
    int id;

    idr_preload(GFP_KERNEL);
    spin_lock(&ctx_lock);
    id = idr_alloc(&ctx_idr, ctx, 1, 0, GFP_NOWAIT);
    spin_unlock(&ctx_lock);
    idr_preload_end();

    if (id < 0)
        return id;

    ctx->id = id;
    return 0;
}

idr_preload()는 "필요한 내부 노드 메모리를 미리 마련해 두고 락 안쪽에서는 가능한 한 비수면 경로로 넣습니다"는 의도입니다. 모든 락 경로에 무조건 필요한 것은 아니지만, spinlock 안에서 IDR을 건드리는 코드라면 거의 항상 검토해야 합니다.

RCU 조회와 안전한 객체 취득

IDR은 조회 함수만으로 객체 생명주기를 보장하지 않습니다. 따라서 lockless lookup이 필요하면 보통 다음과 같이 "RCU 조회 + refcount 확보 + 실패 시 버리기" 패턴을 씁니다.

struct ctx *ctx_lookup_get(int id)
{
    struct ctx *ctx;

    rcu_read_lock();
    ctx = idr_find(&ctx_idr, id);
    if (ctx && !refcount_inc_not_zero(&ctx->refs))
        ctx = NULL;
    rcu_read_unlock();

    return ctx;
}

이 패턴이 필요한 이유는 간단합니다. idr_find()는 포인터만 돌려주고, 그 포인터가 이미 제거 단계인지 아닌지까지 알 수 없기 때문입니다.

IDA API

IDA는 "번호만 필요하고 번호로 직접 포인터를 찾을 필요는 없습니다"는 경우를 위한 할당기입니다. 공식 문서와 헤더 모두 IDA가 자체 잠금을 처리한다고 설명합니다. 그래서 대부분의 경우 호출자 락 없이 ida_alloc()과 ida_free()를 부를 수 있습니다.

DEFINE_IDA(minor_ida);

/* 0..INT_MAX 범위 */
int a = ida_alloc(&minor_ida, GFP_KERNEL);

/* 하한만 지정 */
int b = ida_alloc_min(&minor_ida, 100, GFP_KERNEL);

/* 상한만 지정. max는 inclusive */
int c = ida_alloc_max(&minor_ida, 255, GFP_KERNEL);

/* 범위 지정. max는 inclusive */
int d = ida_alloc_range(&minor_ida, 32, 63, GFP_KERNEL);

ida_free(&minor_ida, d);
if (ida_is_empty(&minor_ida))
    pr_info("더 이상 예약된 번호가 없음\n");

ida_destroy(&minor_ida);

IDA 내부 비트맵(Bitmap)과 청크 구조

IDA는 포인터를 저장하지 않기 때문에, 내부적으로는 "어느 ID가 사용 중인지"를 비트 단위로 추적하는 쪽이 훨씬 효율적입니다. 현재 헤더 기준으로 IDA는 struct xarray를 감싸고, 각 chunk는 128바이트 bitmap을 사용합니다. 이는 64비트와 32비트 환경 모두에서 1024개 ID를 한 chunk가 표현하는 뜻입니다.

잠금, RCU, 생명주기

IDR/IDA 문서를 읽을 때 가장 많이 놓치는 부분은 "번호를 잘 뽑는 것"과 "조회한 객체를 안전하게 쓰는 것"이 같은 문제가 아니라는 점입니다. IDA는 잠금 책임이 비교적 단순하지만, IDR은 상위 서브시스템의 락 계층과 객체 생명주기 정책을 반드시 함께 설계해야 합니다.

실사용 사례

PID namespace의 IDR 사용

현재 커널에서 가장 대표적인 실사용 예시는 kernel/pid.c입니다. 각 pid_namespace는 자체 IDR을 가지고, PID 번호를 먼저 예약한 뒤 struct pid 초기화가 끝나면 idr_replace()로 publish합니다.

/* kernel/pid.c의 핵심 흐름을 축약한 예 */
struct pid_namespace {
    struct idr idr;
    /* ... */
};

idr_preload(GFP_KERNEL);
spin_lock(&pidmap_lock);

nr = idr_alloc_cyclic(&ns->idr, NULL, pid_min, pid_max, GFP_ATOMIC);
if (nr >= 0) {
    pid->numbers[0].nr = nr;
    /* partially initialized PID를 reader가 보지 않게 마지막에 publish */
    idr_replace(&ns->idr, pid, nr);
}

spin_unlock(&pidmap_lock);
idr_preload_end();

이 패턴의 핵심은 두 가지입니다. 첫째, 번호는 먼저 예약하되 객체 공개는 마지막에 합니다. 둘째, PID 조회 함수는 부분 초기화 객체를 보면 안 됩니다. 이 두 요구가 NULL 예약과 idr_replace() 조합으로 해결됩니다.

서브시스템 내부 핸들 테이블

IDR은 특정 커널 객체를 식별하는 내부 핸들 테이블에도 잘 맞습니다. 예를 들어 드라이버가 userspace에 "세션 ID" 같은 번호를 돌려주고 이후 ioctl이나 netlink 요청에서 그 번호로 객체를 찾아야 한다면, IDR은 여전히 읽기 좋은 선택지입니다.

struct session {
    int id;
    refcount_t refs;
    struct rcu_head rcu;
};

DEFINE_IDR(session_idr);
static DEFINE_MUTEX(session_lock);

int session_create(struct session *s)
{
    int id;

    idr_preload(GFP_KERNEL);
    mutex_lock(&session_lock);
    id = idr_alloc(&session_idr, s, 1, 0, GFP_NOWAIT);
    mutex_unlock(&session_lock);
    idr_preload_end();

    if (id < 0)
        return id;

    s->id = id;
    return 0;
}

IDA로 인스턴스 번호만 예약하는 예

반대로 객체 포인터는 해시(Hash)테이블, 배열, 리스트 등 다른 곳에 이미 있고 "중복 없는 번호만 필요"하다면 IDA가 더 적합합니다. 예를 들어 드라이버가 내부 instance 번호나 제한된 범위의 minor 후보를 잡아야 하는 경우입니다.

DEFINE_IDA(inst_ida);

int mydev_probe(struct platform_device *pdev)
{
    int inst;

    inst = ida_alloc_range(&inst_ida, 0, 255, GFP_KERNEL);
    if (inst < 0)
        return inst;

    /* pdev와 inst를 다른 자료구조에 저장 */
    return 0;
}

void mydev_remove(int inst)
{
    ida_free(&inst_ida, inst);
}

IDR vs IDA vs XArray

선택 기준 플로우차트

성능 특성

IDR/IDA 성능을 단순한 한 줄 수치로 말하는 것은 위험합니다. 실제 비용은 현재 살아 있는 엔트리 수, 가장 높은 사용 ID, 순차/순환 할당 패턴, 락 경합, cache locality에 따라 크게 달라집니다. 따라서 아래 표는 절대 수치가 아니라 설계 판단 기준으로 봐야 합니다.

XArray로 마이그레이션

공식 문서가 권장하는 방향은 명확합니다. 새 코드에서 IDR이 꼭 필요한 공개 ABI나 레거시 호출 체인이 없다면, XArray를 직접 사용하는 편이 기능 면에서도 더 직관적입니다. allocating XArray는 ID 할당 문제를 거의 동일하게 풀 수 있고, mark/iterator/advanced API까지 바로 확장할 수 있습니다.

/* 기존 IDR 스타일 */
DEFINE_IDR(obj_idr);
id = idr_alloc(&obj_idr, obj, 1, 0, GFP_KERNEL);
obj = idr_find(&obj_idr, id);
idr_remove(&obj_idr, id);

/* 새 코드의 XArray 스타일 */
DEFINE_XARRAY_ALLOC(obj_xa);
u32 id;

if (!xa_alloc(&obj_xa, &id, obj, XA_LIMIT(1, UINT_MAX), GFP_KERNEL))
    obj = xa_load(&obj_xa, id);

xa_erase(&obj_xa, id);

IDR/IDA 운영 루틴

ID 할당기는 겉으로는 단순해 보여도, 운영 사고는 대부분 해제 누락, 범위 오해, RCU 생명주기 누락에서 나옵니다. 코드 리뷰 때는 아래 항목을 기계적으로 확인하는 편이 낫습니다.

1. 범위 정의를 코드에 드러냈는가
   1..pid_max, 0..255 같은 정책 범위를 상수나 helper로 명시하고, inclusive/exclusive 의미를 주석으로 남깁니다.
2. writer 직렬화가 분명한가
   같은 IDR을 수정하는 모든 경로가 동일한 mutex/spinlock/irq-safe lock 규칙을 따르는지 확인합니다.
3. 조회 후 객체를 붙잡는 방법이 있는가
   RCU reader가 있다면 refcount, kref, 혹은 명시적 grace period를 통해 use-after-free를 막는 경로가 있어야 합니다.
4. 실패 코드가 구분되는가
   -ENOSPC는 범위 고갈, -ENOMEM은 메모리 부족입니다. 둘을 같은 메시지로 뭉개면 운영 분석이 어려워집니다.
5. destroy의 의미를 정확히 아는가
   idr_destroy(), ida_destroy()는 내부 자료구조 정리일 뿐, payload 객체 free까지 대신해 주지 않습니다.
6. deprecated helper가 남아 있지 않은가
   ida_simple_get(), ida_simple_remove()는 현대 코드 기준으로 교체 대상입니다.
7. NULL 예약 패턴의 의미를 팀이 공유하는가
   NULL이 "없음"인지 "예약됨"인지 애매하면 디버깅(Debugging)이 매우 어려워집니다.

IDR 레이어 구조

IDR은 겉으로는 단순한 "ID→포인터" 매핑이지만, 내부적으로는 XArray를 백엔드로 사용하는 radix tree 구조입니다. idr_alloc()가 빈 슬롯을 찾는 과정은 이 트리를 탐색하면서 "사용 중이지 않은 인덱스"를 검색하는 것과 같습니다.

XArray 백엔드 구조

현재 struct idr은 내부에 struct xarray를 감싸고 있습니다. idr_alloc()를 호출하면 실제로는 xa_alloc() 경로를 통해 XArray의 radix tree를 탐색합니다. 이 과정에서 XArray의 각 노드(struct xa_node)는 최대 64개(또는 16개, 아키텍처에 따라 다름)의 슬롯을 가지고, 빈 슬롯을 비트맵으로 추적합니다.

xa_node 구조와 트리 깊이

XArray의 각 노드(struct xa_node)는 아키텍처에 따라 XA_CHUNK_SIZE개의 슬롯을 가집니다. 64비트 시스템에서 XA_CHUNK_SHIFT는 6이므로, 각 노드는 2^6 = 64개 슬롯을 가집니다.

/* include/linux/xarray.h */
struct xa_node {
    unsigned char shift;      /* 이 노드의 비트 시프트 */
    unsigned char offset;     /* 부모에서의 슬롯 위치 */
    unsigned char count;      /* 사용 중인 슬롯 수 */
    unsigned char nr_values;  /* 값 엔트리 수 */
    struct xa_node *parent;  /* 부모 노드 */
    struct xarray *array;    /* 소속 XArray */
    union {
        struct list_head private_list;
        struct rcu_head rcu_head;
    };
    void __rcu *slots[XA_CHUNK_SIZE]; /* 64개 슬롯 */
    union {
        unsigned long tags[XA_MAX_MARKS][XA_MARK_LONGS];
        unsigned long marks[XA_MAX_MARKS][XA_MARK_LONGS];
    };
};

idr_alloc() 트리 탐색 과정

idr_alloc()가 빈 슬롯을 찾는 과정은 다음과 같습니다.

1. 범위 변환: start와 end에서 idr_base를 빼서 XArray 인덱스 공간으로 변환합니다.
2. XArray alloc 호출: xa_alloc()에 변환된 범위를 전달합니다.
3. 노드 탐색: XArray는 루트에서 시작하여 각 레벨의 xa_node를 내려가면서, 빈 슬롯이 있는 첫 번째 경로를 찾습니다.
4. 빈 슬롯 비트맵 확인: 각 xa_node는 어떤 슬롯이 비어 있는지를 marks 배열로 추적합니다. XA_FREE_MARK가 설정된 슬롯이 할당 후보입니다.
5. 노드 생성: 필요하면 새 xa_node를 할당합니다. 이때 GFP 플래그가 중요해집니다.
6. 포인터 저장: 빈 슬롯에 사용자 포인터를 저장하고, free mark를 해제합니다.

/* idr_alloc()의 핵심 흐름 (lib/idr.c 기반 축약) */
int idr_alloc(struct idr *idr, void *ptr,
              int start, int end, gfp_t gfp)
{
    u32 id = start;
    int ret;

    if (WARN_ON_ONCE(start < 0))
        return -EINVAL;

    /* end를 XArray의 max로 변환 */
    int max = end > 0 ? end - 1 : INT_MAX;

    /* XArray 내부 인덱스 공간으로 변환 */
    id -= idr->idr_base;
    max -= idr->idr_base;

    /* xa_alloc()이 실제 트리 탐색과 슬롯 배정을 수행 */
    ret = xa_alloc(&idr->idr_rt, &id, ptr,
                   XA_LIMIT(id, max), gfp);
    if (ret)
        return ret;

    return id + idr->idr_base;
}

idr_find() 구현 분석

idr_find()는 주어진 ID로 XArray를 조회하여 저장된 포인터를 반환합니다. 내부적으로 xa_load()를 호출하며, RCU 보호 하에서 락 없이 동작할 수 있습니다. 트리 깊이에 비례하는 O(log n) 조회이지만, 실제로는 대부분 2~3단계 이내에서 완료됩니다.

/* lib/idr.c 기반 축약 */
void *idr_find(const struct idr *idr, unsigned long id)
{
    /* idr_base 오프셋을 빼서 XArray 인덱스로 변환 */
    return xa_load(&idr->idr_rt, id - idr->idr_base);
}

/* xa_load()의 핵심 흐름 (lib/xarray.c 기반 축약) */
void *xa_load(struct xarray *xa, unsigned long index)
{
    XA_STATE(xas, xa, index);
    void *entry;

    rcu_read_lock();
    do {
        /* xa_head에서 시작하여 트리를 내려감 */
        entry = xas_load(&xas);
        /* retry 엔트리면 루트부터 재시도 */
    } while (xas_retry(&xas, entry));
    rcu_read_unlock();

    return entry;
}

xas_load()는 인덱스의 비트를 XA_CHUNK_SHIFT(보통 6비트)씩 쪼개어, 각 레벨의 xa_node에서 해당 슬롯을 따라 내려갑니다. 리프 노드의 슬롯에 도달하면 저장된 포인터(또는 NULL)를 반환합니다.

idr_remove() 구현 분석

idr_remove()는 IDR에서 지정한 ID의 엔트리를 제거하고 이전에 저장된 포인터를 반환합니다. 내부적으로 XArray의 xa_erase()를 호출합니다.

/* lib/idr.c 기반 축약 */
void *idr_remove(struct idr *idr, unsigned long id)
{
    return xa_erase(&idr->idr_rt, id - idr->idr_base);
}

/* xa_erase()의 핵심 흐름 */
void *xa_erase(struct xarray *xa, unsigned long index)
{
    void *entry;

    xa_lock(xa);
    entry = __xa_erase(xa, index);
    xa_unlock(xa);

    return entry;
}

/* __xa_erase() 내부 동작 */
void *__xa_erase(struct xarray *xa, unsigned long index)
{
    XA_STATE(xas, xa, index);
    return xas_result(&xas, xas_store(&xas, NULL));
    /* 1. 해당 슬롯을 NULL로 덮어씀 */
    /* 2. XA_FREE_MARK를 다시 설정 (할당 가능 표시) */
    /* 3. 비어버린 노드는 축소(shrink) 대상 */
}

제거 과정에서 중요한 세 가지 동작이 있습니다.

1. 슬롯 NULL화: 해당 인덱스의 슬롯을 NULL로 저장합니다. 이 변경은 rcu_assign_pointer() 시맨틱으로 이루어져, RCU reader에게 안전하게 보입니다.
2. XA_FREE_MARK 복원: 슬롯이 비었으므로 해당 위치와 상위 노드에 XA_FREE_MARK를 다시 설정합니다. 이후 idr_alloc()이 이 슬롯을 재할당 후보로 인식합니다.
3. 트리 축소(Shrink): 노드의 모든 슬롯이 비면 해당 노드를 RCU grace period 후에 해제합니다. 부모 노드도 비었으면 재귀적으로 축소합니다.

idr_replace() 구현 분석

idr_replace()는 기존 ID 슬롯의 포인터를 새 포인터로 원자적으로 교체합니다. "NULL 예약 → 초기화 → publish" 패턴의 마지막 단계에서 핵심적으로 사용됩니다.

/* lib/idr.c 기반 축약 */
void *idr_replace(struct idr *idr, void *ptr, unsigned long id)
{
    struct xa_state xas;
    void *entry;

    if (WARN_ON_ONCE(xa_is_internal(ptr)))
        return ERR_PTR(-EINVAL);

    xa_init_state(&xas, &idr->idr_rt, id - idr->idr_base);

    xa_lock(&idr->idr_rt);

    /* 기존 엔트리 확인 */
    entry = xas_load(&xas);
    if (xas_error(&xas) || !entry)
        goto out;

    /* 새 포인터로 교체 (RCU-safe 저장) */
    xas_store(&xas, ptr);

out:
    xa_unlock(&idr->idr_rt);

    if (xas_error(&xas))
        return ERR_PTR(xas_error(&xas));
    if (!entry)
        return ERR_PTR(-ENOENT);

    return entry;  /* 이전 포인터 반환 */
}

idr_replace()의 핵심 특성은 다음과 같습니다.

/* NULL 예약 → 초기화 → publish 패턴 전체 흐름 */
struct my_obj *obj = kzalloc(sizeof(*obj), GFP_KERNEL);
if (!obj)
    return -ENOMEM;

/* 1단계: NULL로 ID 예약 (아직 reader에게 보이지 않음) */
spin_lock(&my_lock);
int id = idr_alloc(&my_idr, NULL, 1, 0, GFP_NOWAIT);
spin_unlock(&my_lock);
if (id < 0) {
    kfree(obj);
    return id;
}

/* 2단계: 객체 완전 초기화 (시간이 걸릴 수 있음) */
obj->id = id;
refcount_set(&obj->refs, 1);
init_completion(&obj->done);
/* ... 추가 초기화 ... */

/* 3단계: 완전한 객체를 publish (이제 reader가 볼 수 있음) */
spin_lock(&my_lock);
void *old = idr_replace(&my_idr, obj, id);
spin_unlock(&my_lock);
WARN_ON(!IS_ERR(old) && old != NULL);
/* old는 NULL이어야 정상 (예약 시 NULL을 넣었으므로) */

idr_for_each() 순회 구현 분석

IDR의 전체 엔트리를 순회하는 API는 두 가지입니다. idr_for_each()는 콜백 함수를 사용하고, idr_for_each_entry()는 매크로 기반 반복문입니다. 둘 다 내부적으로 XArray의 xa_for_each()를 사용합니다.

/* include/linux/idr.h 기반 */

/* 콜백 기반 순회 */
int idr_for_each(const struct idr *idr,
                  int (*fn)(int id, void *p, void *data),
                  void *data)
{
    struct xa_state xas;
    void *entry;
    int ret;

    xa_for_each(&idr->idr_rt, xas, entry) {
        ret = fn(xas.xa_index + idr->idr_base, entry, data);
        if (ret)
            return ret;  /* 콜백이 non-zero 반환 시 즉시 중단 */
    }
    return 0;
}

/* 매크로 기반 순회 */
#define idr_for_each_entry(idr, entry, id)               \
    for (id = 0;                                          \
         ((entry) = idr_get_next((idr), &(id))) != NULL;  \
         ++(id))

/* idr_get_next(): 현재 ID 이상의 다음 엔트리를 찾음 */
void *idr_get_next(struct idr *idr, int *nextidp)
{
    struct xa_state xas;
    void *entry;

    /* *nextidp부터 시작하여 NULL이 아닌 첫 엔트리 탐색 */
    entry = xas_find(&xas, ULONG_MAX);
    if (entry)
        *nextidp = xas.xa_index + idr->idr_base;
    return entry;
}

순회 API의 실전 사용 패턴은 주로 두 가지입니다.

/* 패턴 1: 전체 정리 (모듈 언로드, 파일 닫기 등) */
int id;
struct my_obj *obj;

idr_for_each_entry(&my_idr, obj, id) {
    idr_remove(&my_idr, id);
    kfree_rcu(obj, rcu);
}
idr_destroy(&my_idr);

/* 패턴 2: 조건부 탐색 (상태 dump, 디버깅) */
rcu_read_lock();
idr_for_each_entry(&my_idr, obj, id) {
    if (obj->state == STATE_ERROR)
        pr_warn("obj %d in error state\n", id);
}
rcu_read_unlock();

/* 패턴 3: idr_for_each() 콜백으로 일괄 처리 */
static int release_cb(int id, void *p, void *data)
{
    struct my_obj *obj = p;
    my_obj_put(obj);  /* refcount 감소 */
    return 0;
}

idr_for_each(&my_idr, release_cb, NULL);
idr_destroy(&my_idr);

idr_destroy() 구현 분석

idr_destroy()는 IDR의 내부 XArray 노드를 모두 해제합니다. 중요한 점은 저장된 payload 포인터는 해제하지 않습니다는 것입니다.

/* lib/idr.c 기반 축약 */
void idr_destroy(struct idr *idr)
{
    xa_destroy(&idr->idr_rt);
}

/* xa_destroy() 내부 동작 */
void xa_destroy(struct xarray *xa)
{
    XA_STATE(xas, xa, 0);
    struct xa_node *node;
    void *entry;
    unsigned long flags;

    xa_lock_irqsave(xa, flags);

    /* 루트에서 시작하여 모든 내부 xa_node를 해제 */
    entry = xa_head_locked(xa);
    RCU_INIT_POINTER(xa->xa_head, NULL);
    xas_init_marks(&xas);
    if (xa_is_node(entry))
        xas_free_nodes(&xas, xa_to_node(entry));

    xa_unlock_irqrestore(xa, flags);
}

/* xas_free_nodes(): 트리의 모든 내부 노드를 재귀적으로 해제 */
static void xas_free_nodes(struct xa_state *xas,
                             struct xa_node *top)
{
    /* DFS로 리프까지 내려가면서 모든 xa_node를 해제 */
    /* 슬롯에 저장된 사용자 포인터(payload)는 건드리지 않음 */
    /* 노드 해제는 RCU 콜백을 통해 지연될 수 있음 */
}

idr_destroy() 호출 전에 반드시 payload 객체를 먼저 정리해야 합니다. 정리하지 않으면 메모리 누수가 발생합니다.

/* 올바른 IDR 정리 순서 */
static void cleanup_all(void)
{
    int id;
    struct my_obj *obj;

    /* 1단계: 모든 payload 해제 (RCU reader 없는 상태에서) */
    mutex_lock(&my_lock);
    idr_for_each_entry(&my_idr, obj, id) {
        idr_remove(&my_idr, id);
        kfree(obj);  /* 모듈 언로드라 reader 없음 */
    }
    mutex_unlock(&my_lock);

    /* 2단계: 내부 노드 정리 */
    idr_destroy(&my_idr);
}

/* 잘못된 사용: payload 정리 없이 destroy */
/* idr_destroy(&my_idr);  ← 메모리 누수! */

IDA 비트맵 내부 구조

IDA는 포인터를 저장하지 않으므로, 각 ID의 사용 여부를 1비트로 추적합니다. 내부적으로 XArray의 각 슬롯이 struct ida_bitmap을 가리키고, 각 비트맵은 1024개의 ID를 관리합니다. 이 2단계 구조 덕분에 희소한 ID 공간에서도 메모리 효율이 매우 좋습니다.

ida_bitmap 구조체(Struct) 레이아웃

커널 헤더(include/linux/idr.h)에 정의된 struct ida_bitmap은 다음과 같습니다.

/* include/linux/idr.h */
#define IDA_BITMAP_LONGS  (1024 / 8 / sizeof(long))
/* 64비트: 1024/8/8 = 16 longs = 128 bytes */
/* 32비트: 1024/8/4 = 32 longs = 128 bytes */

struct ida_bitmap {
    unsigned long bitmap[IDA_BITMAP_LONGS];
};

IDA 메모리 효율 분석

IDA의 2단계 비트맵 구조가 실제로 얼마나 메모리 효율적인지 비교합니다.

ida_alloc_range() 내부 동작

ida_alloc_range()가 빈 ID를 찾는 과정은 다음과 같습니다.

/* lib/idr.c 기반 축약 */
int ida_alloc_range(struct ida *ida,
                     unsigned int min, unsigned int max,
                     gfp_t gfp)
{
    XA_STATE(xas, &ida->xa, min / IDA_BITMAP_BITS);
    unsigned bit = min % IDA_BITMAP_BITS;
    struct ida_bitmap *bitmap;
    unsigned long flags;

    xa_lock_irqsave(&ida->xa, flags);
retry:
    bitmap = xas_find_marked(&xas, max / IDA_BITMAP_BITS,
                              XA_FREE_MARK);
    if (xas_error(&xas))
        goto err;

    if (bitmap) {
        /* 기존 비트맵에서 빈 비트 탐색 */
        bit = find_next_zero_bit(bitmap->bitmap,
                                  IDA_BITMAP_BITS, bit);
        if (bit < IDA_BITMAP_BITS) {
            __set_bit(bit, bitmap->bitmap);
            /* 비트맵이 가득 차면 FREE_MARK 해제 */
            if (bitmap_full(bitmap->bitmap, IDA_BITMAP_BITS))
                xas_clear_mark(&xas, XA_FREE_MARK);
            goto out;
        }
    }
    /* 비트맵이 없거나 가득 찼으면 다음 슬롯으로 */
    bit = 0;
    goto retry;

out:
    xa_unlock_irqrestore(&ida->xa, flags);
    return xas.xa_index * IDA_BITMAP_BITS + bit;
}

ida_free() 내부 동작

ida_free()는 이전에 할당한 ID를 해제하여 재사용 가능하게 만듭니다. 내부적으로 해당 비트맵의 비트를 클리어하고, XA_FREE_MARK를 복원합니다.

/* lib/idr.c 기반 축약 */
void ida_free(struct ida *ida, unsigned int id)
{
    XA_STATE(xas, &ida->xa, id / IDA_BITMAP_BITS);
    unsigned bit = id % IDA_BITMAP_BITS;
    struct ida_bitmap *bitmap;
    unsigned long flags;

    BUG_ON((int)id < 0);

    xa_lock_irqsave(&ida->xa, flags);

    bitmap = xas_load(&xas);

    if (xa_is_value(bitmap)) {
        /* 작은 ID 최적화: XArray 엔트리에 인라인 비트 */
        unsigned long v = xa_to_value(bitmap);
        if (bit < XA_CHUNK_SIZE) {
            v &= ~(1UL << bit);
            if (v)
                xas_store(&xas, xa_mk_value(v));
            else
                xas_store(&xas, NULL);
        }
    } else if (bitmap) {
        /* 일반 경로: ida_bitmap에서 비트 클리어 */
        __clear_bit(bit, bitmap->bitmap);

        /* 비트맵이 완전히 비었으면 해제 */
        if (bitmap_empty(bitmap->bitmap, IDA_BITMAP_BITS)) {
            kfree(bitmap);
            xas_store(&xas, NULL);
        }

        /* FREE_MARK 복원 → 이후 ida_alloc()이 후보로 인식 */
        xas_set_mark(&xas, XA_FREE_MARK);
    }

    xa_unlock_irqrestore(&ida->xa, flags);
}

ida_free()의 핵심 동작을 정리하면 다음과 같습니다.

1. 슬롯 위치 계산: id / IDA_BITMAP_BITS로 XArray 슬롯, id % IDA_BITMAP_BITS로 비트맵 내 오프셋을 결정합니다.
2. 인라인 비트 처리: 작은 ID(0~62)는 XArray 값 엔트리에 직접 비트를 저장합니다. 모든 비트가 0이 되면 엔트리를 NULL로 만듭니다.
3. 비트맵 비트 클리어: 큰 ID는 ida_bitmap에서 해당 비트를 __clear_bit()으로 해제합니다.
4. 빈 비트맵 해제: 비트맵의 모든 비트가 0이면 ida_bitmap 자체를 kfree()하여 메모리를 회수합니다.
5. FREE_MARK 복원: 해당 XArray 슬롯에 XA_FREE_MARK를 다시 설정하여, 이후 ida_alloc()이 이 범위에서 빈 ID를 찾을 수 있게 합니다.

Cyclic 할당 메커니즘

일반 idr_alloc()는 항상 가장 낮은 빈 ID를 반환합니다. 하지만 네트워크 프로토콜 식별자나 트랜잭션(Transaction) ID처럼 최근에 사용된 ID를 빠르게 재사용하면 안 되는 경우가 있습니다. 이때 idr_alloc_cyclic()은 마지막으로 할당한 위치의 다음부터 검색을 시작합니다.

idr_alloc_cyclic() 구현 분석

idr_alloc_cyclic()의 핵심은 idr_next 커서입니다. 이 커서는 마지막 할당 위치를 기억하고, 다음 할당 시 그 위치부터 검색을 시작합니다.

/* lib/idr.c 기반 축약 */
int idr_alloc_cyclic(struct idr *idr, void *ptr,
                      int start, int end, gfp_t gfp)
{
    u32 id = idr->idr_next;   /* 이전 할당 위치 + 1 */
    int err, max = end > 0 ? end - 1 : INT_MAX;

    /* 1. cursor 위치부터 max까지 시도 */
    if ((int)id < start)
        id = start;

    err = idr_alloc_u32(idr, ptr, &id, max, gfp);
    if ((err == -ENOSPC) && (id > start)) {
        /* 2. 끝까지 갔으면 start부터 다시 (wraparound) */
        id = start;
        err = idr_alloc_u32(idr, ptr, &id, max, gfp);
    }

    if (!err)
        idr->idr_next = id + 1;  /* 커서 갱신 */

    return err ? err : id;
}

Cyclic 할당 실사용 사례

커널에서 idr_alloc_cyclic()을 사용하는 대표적인 서브시스템들을 정리합니다.

/* ipc/util.c - System V IPC의 cyclic ID 할당 예 */
int ipc_addid(struct ipc_ids *ids,
              struct kern_ipc_perm *new, int limit)
{
    int idx;

    /* cyclic 할당으로 ID 재사용 지연 */
    idx = idr_alloc_cyclic(&ids->ipcs_idr, new,
                            0, limit, GFP_NOWAIT);
    if (idx >= 0) {
        new->id = SEQ_MULTIPLIER * ids->seq + idx;
        new->seq = ids->seq;
        ids->in_use++;
    }

    return idx;
}

Stale ID 방지와 설계 고려사항

Cyclic 할당이 중요한 이유는 stale ID 참조 문제 때문입니다. ID를 해제한 직후 같은 번호가 새로운 객체에 재할당되면, 오래된 참조를 가진 코드가 잘못된 객체에 접근할 수 있습니다.

DRM 핸들 관리

DRM(Direct Rendering Manager) 서브시스템은 GPU 메모리 객체(GEM)를 userspace에 노출할 때 IDR을 사용하여 핸들 번호를 관리합니다. 각 DRM 파일(struct drm_file)은 자체 IDR을 가지고, userspace의 ioctl 호출에서 핸들 번호로 GEM 객체를 찾습니다.

핸들 생명주기와 참조 카운팅

DRM 핸들의 생명주기를 이해하려면 GEM 객체의 참조 카운팅 모델을 알아야 합니다. 하나의 GEM 객체가 여러 핸들에서 참조될 수 있고(flink나 prime fd를 통해), 핸들 삭제 시 참조 카운트(Reference Count)만 감소시킵니다.

drm_gem_handle_create() 코드 분석

drivers/gpu/drm/drm_gem.c의 핵심 흐름을 축약하면 다음과 같습니다.

/* drivers/gpu/drm/drm_gem.c 기반 축약 */
int drm_gem_handle_create(struct drm_file *file_priv,
                          struct drm_gem_object *obj,
                          u32 *handlep)
{
    int ret;

    /* 1. 핸들 할당 (IDR 사용) */
    mutex_lock(&file_priv->table_lock);
    ret = idr_alloc(&file_priv->object_idr, obj,
                     1, 0, GFP_KERNEL);
    mutex_unlock(&file_priv->table_lock);

    if (ret < 0)
        return ret;

    *handlep = ret;

    /* 2. GEM 객체 참조 카운트 증가 */
    drm_gem_object_get(obj);

    /* 3. 드라이버별 open 콜백 */
    if (obj->funcs->open) {
        ret = obj->funcs->open(obj, file_priv);
        if (ret) {
            drm_gem_handle_delete(file_priv, *handlep);
            return ret;
        }
    }

    return 0;
}

/* 핸들로 GEM 객체 조회 */
struct drm_gem_object *drm_gem_object_lookup(
    struct drm_file *filp, u32 handle)
{
    struct drm_gem_object *obj;

    spin_lock(&filp->table_lock);
    obj = idr_find(&filp->object_idr, handle);
    if (obj)
        drm_gem_object_get(obj);  /* refcount 증가 */
    spin_unlock(&filp->table_lock);

    return obj;
}

PID Namespace IDR 활용

PID namespace는 커널에서 IDR을 가장 대표적으로 활용하는 서브시스템입니다. 각 PID namespace는 자체 IDR을 가지고, alloc_pid()가 idr_alloc_cyclic()으로 PID 번호를 할당합니다. namespace가 중첩되면 같은 프로세스가 각 namespace 레벨마다 서로 다른 PID 번호를 가질 수 있습니다.

alloc_pid() 코드 분석

kernel/pid.c의 alloc_pid()는 namespace 계층을 따라 각 레벨에서 PID 번호를 할당합니다.

/* kernel/pid.c 기반 축약 */
struct pid *alloc_pid(struct pid_namespace *ns,
                       pid_t *set_tid, size_t set_tid_size)
{
    struct pid *pid;
    int i, nr;
    struct pid_namespace *tmp;

    pid = kmem_cache_alloc(ns->pid_cachep, GFP_KERNEL);

    /* 각 namespace 레벨에서 PID 번호 할당 */
    tmp = ns;
    pid->level = ns->level;

    for (i = ns->level; i >= 0; i--) {
        idr_preload(GFP_KERNEL);
        spin_lock_irq(&pidmap_lock);

        if (set_tid_size) {
            /* 사용자 지정 PID (clone3 + CLONE_SET_TID) */
            nr = idr_alloc(&tmp->idr, NULL,
                            set_tid[...], set_tid[...] + 1,
                            GFP_ATOMIC);
        } else {
            /* 일반 cyclic 할당 */
            int pid_min = 1;
            if (i == 0 && idr_get_cursor(&tmp->idr) <
                RESERVED_PIDS)
                pid_min = RESERVED_PIDS;  /* 300 */

            nr = idr_alloc_cyclic(&tmp->idr, NULL,
                                   pid_min,
                                   pid_max,
                                   GFP_ATOMIC);
        }

        spin_unlock_irq(&pidmap_lock);
        idr_preload_end();

        if (nr < 0)
            goto out_free;

        pid->numbers[i].nr = nr;
        pid->numbers[i].ns = tmp;
        tmp = tmp->parent;
    }

    /* 초기화 완료 후 각 namespace IDR에 publish */
    spin_lock_irq(&pidmap_lock);
    for (i = ns->level; i >= 0; i--)
        idr_replace(&pid->numbers[i].ns->idr,
                    pid, pid->numbers[i].nr);
    spin_unlock_irq(&pidmap_lock);

    return pid;
}

PID 재활용(Recycling)과 namespace 변환

PID가 해제되면 idr_remove()로 IDR에서 제거되고, 해당 번호는 cyclic 커서가 다시 그 위치를 지날 때 재사용됩니다. namespace 간 PID 변환은 struct pid의 numbers 배열로 처리됩니다.

preload 메커니즘

IDR에서 idr_alloc()를 호출하면 내부적으로 XArray 노드를 할당해야 할 수 있습니다. 문제는 이 할당이 spinlock 안쪽에서 일어날 때입니다. spinlock을 잡은 상태에서는 GFP_KERNEL(수면 가능 할당)을 사용할 수 없으므로, GFP_NOWAIT이나 GFP_ATOMIC을 써야 합니다. 이러면 메모리 압박 시 할당 실패 확률이 높아집니다.

idr_preload()는 이 문제를 해결합니다. 락을 잡기 전에 GFP_KERNEL으로 필요한 노드를 미리 확보해 두고, 실제 idr_alloc() 호출 시에는 미리 확보한 메모리를 사용합니다.

preload 사용 시 주의사항

RCU 생명주기 관리

IDR에서 RCU를 올바르게 사용하는 것은 가장 실수가 많은 영역입니다. 핵심 문제는 idr_remove()와 실제 객체 해제 사이의 시간 간격입니다. IDR에서 엔트리를 제거한 순간에도, 이미 진행 중인 RCU reader는 그 포인터를 여전히 보고 있을 수 있습니다.

올바른 RCU 패턴

IDR에서 RCU를 안전하게 사용하려면, 조회(lookup)와 제거(removal) 양쪽 경로에서 생명주기를 정확하게 관리해야 합니다.

/* 올바른 패턴 1: 조회 측 — refcount 확보 */
struct my_obj *obj_lookup(int id)
{
    struct my_obj *obj;

    rcu_read_lock();
    obj = idr_find(&my_idr, id);
    if (obj && !refcount_inc_not_zero(&obj->refs))
        obj = NULL;  /* 이미 제거 중 */
    rcu_read_unlock();

    return obj;  /* NULL이면 사용 불가 */
}

/* 올바른 패턴 2: 제거 측 — RCU 해제 */
void obj_destroy(int id)
{
    struct my_obj *obj;

    spin_lock(&my_lock);
    obj = idr_remove(&my_idr, id);
    spin_unlock(&my_lock);

    if (obj) {
        /* 마지막 참조 드롭 — refcount 0이면 RCU 해제 */
        if (refcount_dec_and_test(&obj->refs))
            kfree_rcu(obj, rcu);
    }
}

/* 올바른 패턴 3: synchronize_rcu() 사용 */
void obj_destroy_sync(int id)
{
    struct my_obj *obj;

    spin_lock(&my_lock);
    obj = idr_remove(&my_idr, id);
    spin_unlock(&my_lock);

    if (obj) {
        synchronize_rcu();  /* 모든 reader 종료 대기 */
        kfree(obj);         /* 이제 안전하게 해제 */
    }
}

RCU vs 비-RCU 조회 경로 비교

ftrace/perf 디버깅 실습

IDR 관련 문제를 디버깅할 때 가장 효과적인 도구는 커널의 ftrace와 bpftrace입니다. ID 누수, 할당 실패, 비정상 패턴을 추적하는 방법을 실습합니다.

ftrace로 IDR 함수 추적

ftrace의 function_graph 트레이서를 사용하면 idr_alloc, idr_find, idr_remove 호출을 실시간(Real-time)으로 관찰할 수 있습니다.

# 1. IDR 관련 함수 필터 설정
cd /sys/kernel/tracing

# idr_ 접두사 함수만 추적
echo 'idr_alloc*' > set_ftrace_filter
echo 'idr_find' >> set_ftrace_filter
echo 'idr_remove' >> set_ftrace_filter

# function_graph 트레이서 활성화
echo function_graph > current_tracer
echo 1 > tracing_on

# 일정 시간 후 추적 결과 확인
cat trace

# 출력 예시:
# CPU  DURATION   FUNCTION CALLS
#  0)   1.234 us | idr_alloc();
#  0)   0.456 us | idr_find();
#  2)   0.789 us | idr_remove();

bpftrace로 ID 할당 빈도 분석

# idr_alloc 호출 빈도를 프로세스별로 집계
bpftrace -e '
kprobe:idr_alloc {
    @allocs[comm] = count();
}

kprobe:idr_remove {
    @removes[comm] = count();
}

interval:s:10 {
    print(@allocs);
    print(@removes);
    clear(@allocs);
    clear(@removes);
}'

# ID 할당 범위 분포 히스토그램
bpftrace -e '
kretprobe:idr_alloc /retval >= 0/ {
    @id_distribution = hist(retval);
}

interval:s:30 {
    print(@id_distribution);
    clear(@id_distribution);
}'

bpftrace로 ID 누수 탐지

ID 누수는 idr_alloc()과 idr_remove()의 짝이 맞지 않을 때 발생합니다. bpftrace로 이를 추적할 수 있습니다.

# alloc/remove 짝을 추적하여 누수 탐지
bpftrace -e '
kretprobe:idr_alloc /retval >= 0/ {
    @active[retval] = nsecs;
    @alloc_stack[retval] = kstack;
}

kprobe:idr_remove {
    $id = arg1;
    delete(@active[$id]);
    delete(@alloc_stack[$id]);
}

interval:s:60 {
    printf("\n--- 60초 이상 해제되지 않은 ID ---\n");
    print(@active);
}

END {
    printf("\n--- 미해제 ID의 할당 스택 ---\n");
    print(@alloc_stack);
}'

perf probe로 할당 지연 측정

# idr_alloc 진입/종료 probe 등록
perf probe --add 'idr_alloc_entry=idr_alloc'
perf probe --add 'idr_alloc_exit=idr_alloc%return ret=$retval'

# 10초간 기록
perf record -e 'probe:idr_alloc_entry' \
            -e 'probe:idr_alloc_exit' \
            -a -- sleep 10

# 결과 분석
perf script | head -50

# 정리
perf probe --del 'idr_alloc_entry'
perf probe --del 'idr_alloc_exit'

실전 디버깅 시나리오: ID 고갈 추적

시스템에서 "Cannot allocate ID" 오류가 발생했을 때, 어떤 경로에서 ID를 할당하고 어떤 경로에서 해제가 누락되었는지 추적하는 실전 시나리오입니다.

# 1단계: 현재 IDR 할당 상태 확인
# /proc이나 /sys를 통해 서브시스템별 ID 사용량 확인
cat /proc/sys/kernel/pid_max
cat /proc/sys/kernel/threads-max
ls /proc/ | grep -E '^[0-9]+$' | wc -l  # 현재 PID 수

# 2단계: 특정 서브시스템의 alloc/remove 비율 추적
bpftrace -e '
kretprobe:idr_alloc /retval >= 0/ {
    @allocs = count();
}
kretprobe:idr_alloc /retval < 0/ {
    @failures = count();
    @fail_errno = hist(- retval);
}
kprobe:idr_remove {
    @removes = count();
}
interval:s:5 {
    printf("allocs=%d removes=%d failures=%d\n",
           @allocs, @removes, @failures);
}
'

# 3단계: 할당 실패의 호출 스택 확인
bpftrace -e '
kretprobe:idr_alloc /retval == -28/ {  # -ENOSPC
    printf("ID exhaustion at:\n");
    print(kstack);
}
'

성능 분석과 최적화

IDR/IDA의 성능 특성은 내부 XArray radix tree의 구조에서 비롯됩니다. 각 연산의 시간 복잡도와 메모리 비용을 이해하면 적절한 도구를 선택하는 데 도움이 됩니다.

캐시 동작과 메모리 오버헤드

최적화 가이드라인

1. ID 범위를 최소화: 불필요하게 넓은 범위(0~INT_MAX)를 사용하면 트리 깊이가 깊어집니다. 실제 필요한 범위만 지정하세요.
2. 배치 할당 고려: 여러 ID를 연속 할당해야 하면 XArray의 xa_alloc()을 반복하는 것보다 별도의 범위 관리가 나을 수 있습니다.
3. 읽기 경로 최적화: idr_find()가 hot path이면 RCU 기반 lockless lookup을 적극 활용하세요.
4. preload 오버헤드: preload는 per-CPU 캐시를 사용하므로 매번 할당/해제하는 것보다 효율적이지만, preemption disabled 구간이 길어지면 latency에 영향을 줍니다.
5. IDA 선택: 포인터 저장이 필요 없다면 IDA가 IDR보다 메모리와 CPU 모두에서 효율적입니다.
6. cyclic 할당의 비용 인식: idr_alloc_cyclic()은 stale ID 방지에 유리하지만, ID 공간이 거의 가득 찬 상태에서는 탐색 비용이 크게 증가합니다. 사용률이 80%를 넘으면 범위 확장을 고려하세요.
7. idr_destroy() 전 payload 정리: idr_destroy()는 내부 노드만 해제합니다. 저장된 포인터가 가리키는 객체는 먼저 idr_for_each()로 정리해야 메모리 누수가 없습니다.

벤치마크 설정 예

IDR 성능을 커널 모듈(Kernel Module)에서 측정하는 기본 틀입니다. 실제 벤치마크 시에는 CPU 수, 락 경합, ID 분포를 반드시 명시해야 합니다.

/* 커널 모듈 벤치마크 예시 (축약) */
DEFINE_IDR(bench_idr);
static DEFINE_MUTEX(bench_lock);

static void bench_alloc_find_remove(int count)
{
    ktime_t start, alloc_end, find_end, remove_end;
    int *ids;
    int i;

    ids = kmalloc_array(count, sizeof(int), GFP_KERNEL);

    /* 1. 할당 벤치마크 */
    start = ktime_get();
    for (i = 0; i < count; i++) {
        mutex_lock(&bench_lock);
        ids[i] = idr_alloc(&bench_idr, &ids[i],
                             1, 0, GFP_KERNEL);
        mutex_unlock(&bench_lock);
    }
    alloc_end = ktime_get();

    /* 2. 조회 벤치마크 */
    for (i = 0; i < count; i++)
        idr_find(&bench_idr, ids[i]);
    find_end = ktime_get();

    /* 3. 제거 벤치마크 */
    for (i = 0; i < count; i++) {
        mutex_lock(&bench_lock);
        idr_remove(&bench_idr, ids[i]);
        mutex_unlock(&bench_lock);
    }
    remove_end = ktime_get();

    pr_info("count=%d alloc=%lldns find=%lldns remove=%lldns\n",
            count,
            ktime_to_ns(ktime_sub(alloc_end, start)) / count,
            ktime_to_ns(ktime_sub(find_end, alloc_end)) / count,
            ktime_to_ns(ktime_sub(remove_end, find_end)) / count);

    kfree(ids);
}

네트워크 디바이스 IDR 활용

네트워크 서브시스템에서 각 네트워크 인터페이스(struct net_device)는 고유한 ifindex(interface index)를 가집니다. 이 번호는 net/core/dev.c에서 IDR을 사용하여 할당됩니다. 또한 net namespace마다 독립된 IDR을 유지하여, 컨테이너 간 인터페이스 번호가 겹치지 않도록 합니다.

dev_new_index()와 인터페이스 등록 코드

/* net/core/dev.c 기반 축약 */
static int dev_new_index(struct net *net)
{
    int ifindex = net->ifindex;

    for (;;) {
        if (++ifindex <= 0)
            ifindex = 1;  /* 오버플로우 시 1부터 */

        if (!__dev_get_by_index(net, ifindex))
            return net->ifindex = ifindex;
    }
}

/* 인터페이스 등록 시 ifindex 배정 */
int register_netdevice(struct net_device *dev)
{
    struct net *net = dev_net(dev);

    /* ifindex 할당 */
    dev->ifindex = dev_new_index(net);
    if (dev->ifindex < 0)
        goto err;

    /* 해시 테이블에 등록 */
    list_netdevice(dev);

    return 0;
}

TC 필터와 네트워크 서브시스템의 IDR 활용

ifindex 자체는 순차 카운터를 사용하지만, 네트워크 서브시스템의 여러 부분에서 IDR을 직접 활용합니다.

/* net/sched/cls_api.c 기반 축약 — TC 필터 핸들 할당 */
static u32 gen_new_kid(struct tcf_proto *tp,
                        u32 *idx_gen)
{
    u32 i = 0x80000000;  /* 자동 생성 핸들 범위 */

    /* IDR에서 사용 가능한 핸들 검색 */
    if (idr_alloc_u32(&tp->handle_idr, NULL,
                       &i, i + 0x7FFFFFFF,
                       GFP_KERNEL) == 0) {
        *idx_gen = i;
    }
    return i;
}

net namespace와 인터페이스 격리(Isolation)

네트워크 namespace는 PID namespace와 마찬가지로, 각 namespace가 독립된 네트워크 스택(Network Stack)을 가집니다. 따라서 호스트의 ifindex 1(lo)과 컨테이너의 ifindex 1(lo)은 서로 다른 인터페이스입니다.

네트워크 코드에서 배우는 IDR 설계 패턴

네트워크 서브시스템의 IDR 사용 사례에서 공통적으로 나타나는 설계 패턴을 정리합니다. 이 패턴들은 다른 서브시스템에서도 동일하게 적용할 수 있습니다.

1. per-namespace IDR: 격리가 필요한 자원마다 독립 IDR을 유지합니다. PID namespace와 net namespace 모두 이 패턴을 씁니다.
2. 순차 증가 + 중복 확인: ifindex처럼 완전한 랜덤이 아니라 순차 증가 카운터에 중복 확인을 결합합니다. 단순하지만 효과적입니다.
3. 정리 경로의 일괄 처리: namespace 파괴 시 idr_for_each()로 남은 엔트리를 모두 정리합니다. 개별 해제 누락에 대한 안전망 역할을 합니다.
4. 핫 패스 최적화: 조회가 빈번한 경로(패킷(Packet) 수신 등)에서는 해시 테이블을 병행하여 O(1) 조회를 보장합니다.

커널 모듈 구현 예시: IDR 기반 세션 관리

IDR을 사용하여 userspace에 세션 핸들을 제공하는 커널 모듈의 완전한 예시입니다. RCU 조회, preload, refcount 관리, 정리 경로를 모두 포함합니다.

/* idr_session.c — IDR 기반 세션 관리 커널 모듈 */
#include <linux/module.h>
#include <linux/idr.h>
#include <linux/slab.h>
#include <linux/refcount.h>
#include <linux/rcupdate.h>
#include <linux/spinlock.h>

struct session {
    int           id;
    refcount_t    refs;
    struct rcu_head rcu;
    char          name[32];
    unsigned long created_jiffies;
    bool          closing;  /* 제거 진행 중 표시 */
};

static DEFINE_IDR(session_idr);
static DEFINE_SPINLOCK(session_lock);

/* ─── 생성: preload + spinlock 패턴 ─── */
static struct session *session_create(const char *name)
{
    struct session *s;
    int id;

    s = kzalloc(sizeof(*s), GFP_KERNEL);
    if (!s)
        return ERR_PTR(-ENOMEM);

    /* 1. 락 바깥에서 메모리 미리 확보 */
    idr_preload(GFP_KERNEL);
    spin_lock(&session_lock);

    /* 2. NULL로 ID 예약 (부분 초기화 객체 노출 방지) */
    id = idr_alloc(&session_idr, NULL, 1, 0, GFP_NOWAIT);

    spin_unlock(&session_lock);
    idr_preload_end();

    if (id < 0) {
        kfree(s);
        return ERR_PTR(id);
    }

    /* 3. 객체 완전 초기화 */
    s->id = id;
    refcount_set(&s->refs, 1);
    s->closing = false;
    s->created_jiffies = jiffies;
    strscpy(s->name, name, sizeof(s->name));

    /* 4. 완전한 객체를 publish */
    spin_lock(&session_lock);
    idr_replace(&session_idr, s, id);
    spin_unlock(&session_lock);

    pr_info("session %d '%s' created\n", id, name);
    return s;
}

/* ─── RCU 조회: refcount 확보 패턴 ─── */
static struct session *session_get(int id)
{
    struct session *s;

    rcu_read_lock();
    s = idr_find(&session_idr, id);
    if (s) {
        /* 제거 진행 중이면 사용 불가 */
        if (s->closing || !refcount_inc_not_zero(&s->refs))
            s = NULL;
    }
    rcu_read_unlock();

    return s;
}

/* ─── refcount 감소: 0이면 RCU 해제 ─── */
static void session_put(struct session *s)
{
    if (refcount_dec_and_test(&s->refs))
        kfree_rcu(s, rcu);
}

/* ─── 제거: IDR에서 빼고 refcount 드롭 ─── */
static int session_destroy(int id)
{
    struct session *s;

    spin_lock(&session_lock);
    s = idr_find(&session_idr, id);
    if (s) {
        s->closing = true;      /* 새 refcount 획득 차단 */
        idr_remove(&session_idr, id);
    }
    spin_unlock(&session_lock);

    if (!s)
        return -ENOENT;

    pr_info("session %d '%s' removed\n", id, s->name);
    session_put(s);  /* 마지막 참조면 RCU 후 해제 */
    return 0;
}

/* ─── 순회: 전체 세션 dump ─── */
static void session_dump_all(void)
{
    int id;
    struct session *s;

    rcu_read_lock();
    idr_for_each_entry(&session_idr, s, id) {
        pr_info("  [%d] name='%s' refs=%u age=%lu ms\n",
                id, s->name,
                refcount_read(&s->refs),
                jiffies_to_msecs(jiffies - s->created_jiffies));
    }
    rcu_read_unlock();
}

/* ─── 전체 정리: 모듈 언로드 ─── */
static void session_cleanup_all(void)
{
    int id;
    struct session *s;

    spin_lock(&session_lock);
    idr_for_each_entry(&session_idr, s, id) {
        s->closing = true;
        idr_remove(&session_idr, id);
        session_put(s);
    }
    spin_unlock(&session_lock);

    /* reader 모두 빠져나간 뒤 내부 노드 정리 */
    synchronize_rcu();
    idr_destroy(&session_idr);
}

/* ─── 모듈 초기화/종료 ─── */
static int __init idr_demo_init(void)
{
    struct session *s1, *s2, *s3, *lookup;

    pr_info("=== IDR session demo start ===\n");

    /* 세션 생성 */
    s1 = session_create("alpha");
    s2 = session_create("beta");
    s3 = session_create("gamma");

    if (IS_ERR(s1) || IS_ERR(s2) || IS_ERR(s3)) {
        pr_err("session creation failed\n");
        return -ENOMEM;
    }

    /* RCU 조회 테스트 */
    lookup = session_get(s2->id);
    if (lookup) {
        pr_info("looked up session %d: '%s'\n",
                lookup->id, lookup->name);
        session_put(lookup);
    }

    /* 전체 dump */
    session_dump_all();

    /* 중간 세션 제거 */
    session_destroy(s2->id);

    /* 제거 후 조회 확인 */
    lookup = session_get(s2->id);
    pr_info("after remove, session %d lookup: %s\n",
            s2->id, lookup ? "found" : "NULL");

    pr_info("=== IDR session demo loaded ===\n");
    return 0;
}

static void __exit idr_demo_exit(void)
{
    session_cleanup_all();
    pr_info("=== IDR session demo unloaded ===\n");
}

module_init(idr_demo_init);
module_exit(idr_demo_exit);
MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("IDR session management demo");

커널 모듈 구현 예시: IDA 기반 디바이스 번호 관리

IDA를 사용하여 캐릭터 디바이스의 minor 번호를 관리하는 커널 모듈 예시입니다. IDA는 번호만 예약하므로 IDR보다 코드가 단순합니다.

/* ida_minor.c — IDA 기반 minor 번호 관리 커널 모듈 */
#include <linux/module.h>
#include <linux/idr.h>
#include <linux/slab.h>
#include <linux/list.h>

#define MYDEV_MINOR_MAX  255

static DEFINE_IDA(mydev_ida);

struct mydev {
    int              minor;
    char             name[16];
    struct list_head list;
};

static LIST_HEAD(mydev_list);
static DEFINE_MUTEX(mydev_lock);

/* ─── 디바이스 등록: IDA로 minor 번호 할당 ─── */
static struct mydev *mydev_register(const char *name)
{
    struct mydev *dev;
    int minor;

    /* IDA는 자체 잠금 처리 — 외부 락 불필요 */
    minor = ida_alloc_max(&mydev_ida, MYDEV_MINOR_MAX, GFP_KERNEL);
    if (minor < 0)
        return ERR_PTR(minor);  /* -ENOSPC 또는 -ENOMEM */

    dev = kzalloc(sizeof(*dev), GFP_KERNEL);
    if (!dev) {
        ida_free(&mydev_ida, minor);  /* 오류 경로: 반드시 해제 */
        return ERR_PTR(-ENOMEM);
    }

    dev->minor = minor;
    snprintf(dev->name, sizeof(dev->name), "%s%d", name, minor);
    INIT_LIST_HEAD(&dev->list);

    mutex_lock(&mydev_lock);
    list_add_tail(&dev->list, &mydev_list);
    mutex_unlock(&mydev_lock);

    pr_info("mydev: registered '%s' (minor %d)\n",
            dev->name, dev->minor);
    return dev;
}

/* ─── 디바이스 해제: minor 번호 반환 ─── */
static void mydev_unregister(struct mydev *dev)
{
    pr_info("mydev: unregistering '%s' (minor %d)\n",
            dev->name, dev->minor);

    mutex_lock(&mydev_lock);
    list_del(&dev->list);
    mutex_unlock(&mydev_lock);

    ida_free(&mydev_ida, dev->minor);  /* 번호 반환 */
    kfree(dev);
}

/* ─── 전체 정리 ─── */
static void mydev_cleanup_all(void)
{
    struct mydev *dev, *tmp;

    mutex_lock(&mydev_lock);
    list_for_each_entry_safe(dev, tmp, &mydev_list, list) {
        list_del(&dev->list);
        ida_free(&mydev_ida, dev->minor);
        kfree(dev);
    }
    mutex_unlock(&mydev_lock);

    ida_destroy(&mydev_ida);
}

/* ─── 모듈 초기화/종료 ─── */
static int __init ida_demo_init(void)
{
    struct mydev *d1, *d2, *d3, *d4;

    pr_info("=== IDA minor demo start ===\n");

    d1 = mydev_register("tty");    /* minor 0 */
    d2 = mydev_register("tty");    /* minor 1 */
    d3 = mydev_register("tty");    /* minor 2 */

    if (IS_ERR(d1) || IS_ERR(d2) || IS_ERR(d3))
        return -ENOMEM;

    /* minor 1 해제 후 재할당 → minor 1이 다시 나옴 */
    mydev_unregister(d2);
    d4 = mydev_register("tty");    /* minor 1 (재사용) */

    pr_info("reused minor: %d (expected 1)\n",
            IS_ERR(d4) ? -1 : d4->minor);

    /* ida_is_empty() 확인 */
    pr_info("ida empty: %s\n",
            ida_is_empty(&mydev_ida) ? "yes" : "no");

    pr_info("=== IDA minor demo loaded ===\n");
    return 0;
}

static void __exit ida_demo_exit(void)
{
    mydev_cleanup_all();
    pr_info("=== IDA minor demo unloaded ===\n");
}

module_init(ida_demo_init);
module_exit(ida_demo_exit);
MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("IDA minor number management demo");

커널 모듈 구현 예시: IDR 에러 처리와 경계값 테스트

IDR/IDA를 사용할 때 자주 발생하는 에러 상황과 경계값을 테스트하는 커널 모듈입니다. 코드 리뷰와 디버깅의 기준점으로 활용할 수 있습니다.

/* idr_edge_cases.c — IDR/IDA 경계값과 에러 처리 테스트 */
#include <linux/module.h>
#include <linux/idr.h>
#include <linux/slab.h>

/* ─── 테스트 1: end 파라미터의 배타적 의미 확인 ─── */
static void test_exclusive_end(void)
{
    DEFINE_IDR(idr);
    int id;
    int dummy = 42;

    pr_info("--- test: exclusive end ---\n");

    /* end=5이면 할당 범위는 0..4 (end는 배타적) */
    for (int i = 0; i < 6; i++) {
        id = idr_alloc(&idr, &dummy, 0, 5, GFP_KERNEL);
        if (id < 0)
            pr_info("  alloc %d: error %d (expected at i=5)\n",
                    i, id);
        else
            pr_info("  alloc %d: got ID %d\n", i, id);
    }
    /* i=5에서 -ENOSPC가 나와야 정상 */

    idr_destroy(&idr);
}

/* ─── 테스트 2: idr_alloc_u32()의 포괄적 max 확인 ─── */
static void test_inclusive_max(void)
{
    DEFINE_IDR(idr);
    int dummy = 42;
    u32 nextid;
    int ret;

    pr_info("--- test: inclusive max ---\n");

    /* max=4이면 할당 범위는 0..4 (max는 포괄적) */
    for (int i = 0; i < 6; i++) {
        nextid = 0;
        ret = idr_alloc_u32(&idr, &dummy, &nextid, 4, GFP_KERNEL);
        if (ret < 0)
            pr_info("  alloc_u32 %d: error %d\n", i, ret);
        else
            pr_info("  alloc_u32 %d: got ID %u\n", i, nextid);
    }
    /* i=5에서 -ENOSPC: 0,1,2,3,4 모두 사용됨 */

    idr_destroy(&idr);
}

/* ─── 테스트 3: end=0의 특수 의미 ─── */
static void test_end_zero(void)
{
    DEFINE_IDR(idr);
    int dummy = 42;
    int id;

    pr_info("--- test: end=0 means INT_MAX+1 ---\n");

    /* end=0이면 INT_MAX까지 허용 (사실상 무제한) */
    id = idr_alloc(&idr, &dummy, 1000000, 0, GFP_KERNEL);
    pr_info("  high start with end=0: got ID %d\n", id);
    /* 1000000이 반환되어야 함 */

    idr_remove(&idr, id);
    idr_destroy(&idr);
}

/* ─── 테스트 4: 존재하지 않는 ID 제거 ─── */
static void test_remove_nonexistent(void)
{
    DEFINE_IDR(idr);
    void *old;

    pr_info("--- test: remove nonexistent ---\n");

    old = idr_remove(&idr, 42);
    pr_info("  remove(42) on empty IDR: %p (expected NULL)\n", old);

    idr_destroy(&idr);
}

/* ─── 테스트 5: replace 에러 조건 ─── */
static void test_replace_errors(void)
{
    DEFINE_IDR(idr);
    int a = 1, b = 2;
    void *old;
    int id;

    pr_info("--- test: replace errors ---\n");

    /* 빈 IDR에서 replace → ERR_PTR(-ENOENT) */
    old = idr_replace(&idr, &a, 99);
    pr_info("  replace on empty: err=%ld (expected -2/ENOENT)\n",
            PTR_ERR(old));

    /* 정상 replace */
    id = idr_alloc(&idr, &a, 1, 0, GFP_KERNEL);
    old = idr_replace(&idr, &b, id);
    pr_info("  replace success: old=%p (&a=%p)\n", old, &a);

    idr_remove(&idr, id);
    idr_destroy(&idr);
}

/* ─── 테스트 6: IDA 범위 고갈 ─── */
static void test_ida_exhaustion(void)
{
    DEFINE_IDA(ida);
    int ids[8];
    int i, extra;

    pr_info("--- test: IDA range exhaustion ---\n");

    /* 범위 0..7을 모두 할당 */
    for (i = 0; i < 8; i++) {
        ids[i] = ida_alloc_range(&ida, 0, 7, GFP_KERNEL);
        pr_info("  ida_alloc[%d]: %d\n", i, ids[i]);
    }

    /* 8번째 → -ENOSPC */
    extra = ida_alloc_range(&ida, 0, 7, GFP_KERNEL);
    pr_info("  exhausted: %d (expected -28/ENOSPC)\n", extra);

    /* 하나 해제 후 재할당 */
    ida_free(&ida, ids[3]);
    extra = ida_alloc_range(&ida, 0, 7, GFP_KERNEL);
    pr_info("  after free(3), realloc: %d (expected 3)\n", extra);

    /* 정리 */
    for (i = 0; i < 8; i++) {
        if (i != 3)
            ida_free(&ida, ids[i]);
    }
    if (extra >= 0)
        ida_free(&ida, extra);

    ida_destroy(&ida);
}

/* ─── 테스트 7: cyclic 할당 동작 확인 ─── */
static void test_cyclic_allocation(void)
{
    DEFINE_IDR(idr);
    int dummy = 42;
    int id1, id2, id3;

    pr_info("--- test: cyclic allocation ---\n");

    /* 순차 할당 */
    id1 = idr_alloc_cyclic(&idr, &dummy, 1, 100, GFP_KERNEL);
    id2 = idr_alloc_cyclic(&idr, &dummy, 1, 100, GFP_KERNEL);
    pr_info("  cyclic 1st: %d, 2nd: %d\n", id1, id2);

    /* id1 제거 후 재할당 → id1이 아닌 id2+1부터 탐색 */
    idr_remove(&idr, id1);
    id3 = idr_alloc_cyclic(&idr, &dummy, 1, 100, GFP_KERNEL);
    pr_info("  after remove(%d), cyclic: %d (not %d)\n",
            id1, id3, id1);
    /* cyclic은 cursor 이후부터 찾으므로 id1을 건너뜀 */

    idr_remove(&idr, id2);
    idr_remove(&idr, id3);
    idr_destroy(&idr);
}

static int __init edge_test_init(void)
{
    pr_info("=== IDR/IDA edge case tests ===\n");

    test_exclusive_end();
    test_inclusive_max();
    test_end_zero();
    test_remove_nonexistent();
    test_replace_errors();
    test_ida_exhaustion();
    test_cyclic_allocation();

    pr_info("=== all edge case tests done ===\n");
    return 0;
}

static void __exit edge_test_exit(void)
{
    pr_info("=== IDR/IDA edge case module unloaded ===\n");
}

module_init(edge_test_init);
module_exit(edge_test_exit);
MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("IDR/IDA edge case and boundary tests");

XArray 마이그레이션: 옛 Radix Tree IDR vs 새 XArray IDR

현재 IDR의 내부 구현은 XArray 위의 얇은 래퍼(Wrapper)이지만, 커널 4.20 이전의 IDR은 자체 radix tree(struct idr_layer)를 가지고 있었습니다. 이 전환의 역사와 구조 차이를 이해하면, 기존 코드와 새 코드를 읽을 때 혼란을 줄일 수 있습니다.

옛 IDR 구조 (커널 4.19 이전)

커널 4.19까지의 struct idr은 자체 radix tree를 가지고 있었습니다. struct idr_layer는 각 노드를 나타내고, idr_layer->ary[] 배열이 자식 노드 또는 사용자 포인터를 저장했습니다.

/* 커널 4.19 이전의 옛 IDR 구조 (include/linux/idr.h) */
#define IDR_BITS       8   /* 노드당 256 슬롯 */
#define IDR_SIZE       (1 << IDR_BITS)
#define IDR_MASK       (IDR_SIZE - 1)
#define MAX_IDR_SHIFT  (sizeof(int) * 8 - 1)

struct idr_layer {
    int                   prefix;   /* 이 노드의 키 접두사 */
    int                   layer;    /* 트리 깊이 (0=리프) */
    struct idr_layer __rcu *ary[IDR_SIZE];  /* 256개 슬롯 */
    int                   count;    /* 사용 중인 슬롯 수 */
    unsigned long         bitmap;   /* 빈 슬롯 추적 */
    struct rcu_head       rcu_head;
};

struct idr {
    struct idr_layer __rcu *hint;  /* 마지막 조회 캐시 */
    struct idr_layer __rcu *top;   /* 트리 루트 */
    int                    layers;  /* 현재 트리 깊이 */
    int                    cur;     /* cyclic 커서 */
    struct idr_layer       *id_free;
    int                    id_free_cnt;
};

새 IDR 구조 (커널 4.20 이후)

XArray 도입 후, struct idr은 struct xarray를 감싸는 단순한 구조로 변경되었습니다.

/* 커널 4.20 이후의 현재 IDR 구조 (include/linux/idr.h) */
struct idr {
    struct xarray   idr_rt;    /* XArray가 실제 저장소 */
    unsigned int    idr_base;  /* ID 오프셋 (기본 0) */
    unsigned int    idr_next;  /* cyclic 커서 */
};

/* idr_init_base()로 초기화 */
static inline void idr_init_base(struct idr *idr,
                                   int base)
{
    INIT_RADIX_TREE(&idr->idr_rt, IDR_RT_MARKER);
    idr->idr_base = base;
    idr->idr_next = 0;
}

/* 모든 IDR API가 내부적으로 xa_*() 호출로 변환됨 */
/* idr_alloc()  → xa_alloc()  */
/* idr_find()   → xa_load()   */
/* idr_remove() → xa_erase()  */

핵심 구조 차이 비교

/* 옛 idr_find() — 자체 트리 탐색 (커널 4.19 이전) */
void *idr_find(struct idr *idp, int id)
{
    struct idr_layer *p;
    int n;

    /* hint 캐시 확인 — 직전 조회와 같은 prefix면 바로 사용 */
    p = rcu_dereference(idp->hint);
    if (p && (id & ~IDR_MASK) == p->prefix)
        return rcu_dereference(p->ary[id & IDR_MASK]);

    /* 루트에서 내려가면서 탐색 */
    p = rcu_dereference(idp->top);
    if (!p || id > idr_max(p->layer + 1))
        return NULL;

    n = (p->layer + 1) * IDR_BITS;
    while (p && n > 0) {
        n -= IDR_BITS;
        p = rcu_dereference(p->ary[(id >> n) & IDR_MASK]);
    }
    return (void *)p;
}

/* 새 idr_find() — XArray 래퍼 (커널 4.20 이후) */
void *idr_find(const struct idr *idr, unsigned long id)
{
    return xa_load(&idr->idr_rt, id - idr->idr_base);
    /* 한 줄로 축약됨 — 모든 트리 탐색은 xa_load()가 처리 */
}

파일 디스크립터 할당과 IDR 비교

파일 디스크립터(File Descriptor, fd) 할당은 "정수 ID를 빈 슬롯에서 뽑습니다"는 점에서 IDR과 같은 문제를 풀지만, IDR을 사용하지 않습니다. 커널은 fdtable + 고정 비트맵 방식으로 fd를 관리합니다. 이 차이를 이해하면 "언제 IDR이 적합하고 언제 다른 구조가 나은지"를 판단하는 기준이 됩니다.

fdtable 구조와 fd 할당 경로

/* include/linux/fdtable.h 기반 축약 */
struct fdtable {
    unsigned int          max_fds;       /* 현재 테이블 크기 */
    struct file __rcu     **fd;          /* fd → struct file 포인터 배열 */
    unsigned long         *close_on_exec; /* 비트맵 */
    unsigned long         *open_fds;     /* 사용 중인 fd 비트맵 */
    unsigned long         *full_fds_bits; /* open_fds 요약 비트맵 */
    struct rcu_head       rcu;
};

struct files_struct {
    atomic_t              count;
    struct fdtable __rcu  *fdt;    /* 현재 활성 fdtable */
    struct fdtable        fdtab;   /* 초기 인라인 fdtable */
    spinlock_t            file_lock;
    unsigned int          next_fd; /* 다음 할당 후보 위치 */
    struct embedded_fd_set close_on_exec_init;
    struct embedded_fd_set open_fds_init;
    struct embedded_fd_set full_fds_bits_init;
    struct file __rcu     *fd_array[NR_OPEN_DEFAULT];
};

/* fs/file.c — fd 할당 핵심 흐름 (축약) */
static int alloc_fd(unsigned start, unsigned end,
                     unsigned flags)
{
    struct files_struct *files = current->files;
    unsigned int fd;

    spin_lock(&files->file_lock);

    /* 1. next_fd 힌트부터 빈 비트 탐색 */
    fd = start;
    if (fd < files->next_fd)
        fd = files->next_fd;

    /* 2. open_fds 비트맵에서 빈 비트 찾기 */
    /*    full_fds_bits로 이미 가득 찬 구간을 건너뜀 */
    fd = find_next_fd(fdt, fd);

    /* 3. 테이블이 작으면 확장 (grow) */
    if (fd >= fdt->max_fds) {
        expand_files(files, fd);
        /* RCU로 새 fdtable publish */
    }

    /* 4. 비트맵에 fd 표시 */
    __set_open_fd(fd, fdt);
    if (flags & O_CLOEXEC)
        __set_close_on_exec(fd, fdt);

    /* 5. next_fd 힌트 갱신 */
    if (fd == files->next_fd)
        files->next_fd = fd + 1;

    spin_unlock(&files->file_lock);
    return fd;
}

fd가 IDR을 쓰지 않는 이유

문자 디바이스 Minor 번호 할당

문자 디바이스(Character Device)의 major/minor 번호 할당은 또 다른 "정수 ID 관리" 사례입니다. alloc_chrdev_region()은 IDR이 아닌 별도의 문자 디바이스 번호 관리 체계를 사용합니다. 하지만 개별 드라이버가 인스턴스별 minor 번호를 관리할 때는 IDA를 사용하는 것이 일반적인 패턴입니다.

alloc_chrdev_region() 코드 분석

/* fs/char_dev.c 기반 축약 */
static struct char_device_struct {
    struct char_device_struct *next;
    unsigned int              major;
    unsigned int              baseminor;
    int                       minorct;
    char                      name[64];
    struct cdev               *cdev;
} *chrdevs[CHRDEV_MAJOR_HASH_SIZE];

/* 동적 major 번호 할당 */
int alloc_chrdev_region(dev_t *dev,
                         unsigned baseminor,
                         unsigned count,
                         const char *name)
{
    struct char_device_struct *cd;

    /* major=0이면 동적 할당 */
    cd = __register_chrdev_region(0, baseminor, count, name);
    if (IS_ERR(cd))
        return PTR_ERR(cd);

    *dev = MKDEV(cd->major, cd->baseminor);
    return 0;
}

/* __register_chrdev_region() 핵심 흐름 */
static struct char_device_struct *
__register_chrdev_region(unsigned int major,
                          unsigned int baseminor,
                          int minorct,
                          const char *name)
{
    struct char_device_struct *cd, *curr, *prev;
    int ret, i;

    cd = kzalloc(sizeof(*cd), GFP_KERNEL);

    mutex_lock(&chrdevs_lock);

    if (major == 0) {
        /* 동적 major 할당: 빈 major 번호 탐색 */
        ret = find_dynamic_major();
        if (ret < 0)
            goto out;
        major = ret;
    }

    cd->major = major;
    cd->baseminor = baseminor;
    cd->minorct = minorct;
    strscpy(cd->name, name, sizeof(cd->name));

    /* 해시 테이블에 삽입 (major 기반 해시) */
    i = major_to_index(major);
    /* ... 충돌 검사 후 연결 리스트에 삽입 ... */

    mutex_unlock(&chrdevs_lock);
    return cd;
}

드라이버별 IDA minor 관리 패턴

alloc_chrdev_region()이 major 번호를 잡아주면, 각 드라이버는 자체 IDA로 인스턴스별 minor 번호를 관리하는 것이 일반적입니다. 커널에서 이 패턴을 사용하는 대표적인 드라이버를 정리합니다.

/* 실제 커널 드라이버의 IDA minor 패턴 (drivers/misc 계열 축약) */
static dev_t mydrv_devt;           /* major:baseminor */
static DEFINE_IDA(mydrv_minor_ida);
static struct class *mydrv_class;

int mydrv_probe(struct platform_device *pdev)
{
    struct mydrv_data *data;
    int minor;

    /* 1. IDA로 minor 번호 할당 */
    minor = ida_alloc_max(&mydrv_minor_ida, MYDRV_MAX_DEVS - 1,
                           GFP_KERNEL);
    if (minor < 0)
        return minor;

    data = devm_kzalloc(&pdev->dev, sizeof(*data), GFP_KERNEL);
    if (!data) {
        ida_free(&mydrv_minor_ida, minor);  /* 오류 경로 정리 */
        return -ENOMEM;
    }

    data->minor = minor;
    data->devt = MKDEV(MAJOR(mydrv_devt), minor);

    /* 2. cdev 등록 */
    cdev_init(&data->cdev, &mydrv_fops);
    cdev_add(&data->cdev, data->devt, 1);

    /* 3. /dev 노드 생성 */
    data->device = device_create(mydrv_class, &pdev->dev,
                                  data->devt, data,
                                  "mydrv%d", minor);

    platform_set_drvdata(pdev, data);
    return 0;
}

void mydrv_remove(struct platform_device *pdev)
{
    struct mydrv_data *data = platform_get_drvdata(pdev);

    device_destroy(mydrv_class, data->devt);
    cdev_del(&data->cdev);
    ida_free(&mydrv_minor_ida, data->minor);
}

/* 모듈 초기화: major 번호 할당 + IDA 준비 */
static int __init mydrv_init(void)
{
    int ret;

    ret = alloc_chrdev_region(&mydrv_devt, 0,
                               MYDRV_MAX_DEVS, "mydrv");
    if (ret)
        return ret;

    mydrv_class = class_create("mydrv");
    if (IS_ERR(mydrv_class)) {
        unregister_chrdev_region(mydrv_devt, MYDRV_MAX_DEVS);
        return PTR_ERR(mydrv_class);
    }

    return platform_driver_register(&mydrv_driver);
}

/* 모듈 종료: 전체 정리 */
static void __exit mydrv_exit(void)
{
    platform_driver_unregister(&mydrv_driver);
    class_destroy(mydrv_class);
    unregister_chrdev_region(mydrv_devt, MYDRV_MAX_DEVS);
    ida_destroy(&mydrv_minor_ida);
}

관련 문서

• XArray — 새 코드에서 기본 선택이 되는 인덱스 기반 저장소
• Radix Tree — IDR의 역사와 helper 계층을 이해하는 배경
• Bitmap — IDA의 비트 단위 예약 모델을 이해하는 데 유용
• 프로세스 관리 — PID namespace와 PID 할당 흐름의 큰 그림
• 공식 IDR/IDA 문서 — API 의미, deprecated 상태, preload와 RCU 규칙
• 공식 XArray 문서 — allocating XArray, locking, iterator, migration 기준
• kernel/pid.c — 현재 커널의 대표적인 IDR 실사용 예시
• fs/file.c — 파일 디스크립터가 IDR이 아닌 fdtable + bitmap임을 확인할 수 있는 소스
• fs/char_dev.c — alloc_chrdev_region()이 별도 char-device 번호 관리 경로임을 확인할 수 있는 소스

참고 자료

• include/linux/idr.h — Bootlin Elixir — IDR/IDA 공개 API와 인라인 헬퍼 함수의 정의를 확인할 수 있습니다.
• lib/idr.c — Bootlin Elixir — IDR/IDA 핵심 구현체의 소스 코드입니다. XArray 기반 내부 동작을 확인할 수 있습니다.
• IDR/IDA — Kernel Documentation — 공식 커널 문서로, API 시맨틱, preload 규칙, RCU 보호 조건을 설명합니다.
• The IDR tree (LWN, 2006) — IDR 자료구조의 초기 설계 의도와 내부 트리 구조를 설명하는 LWN 기사입니다.
• The XArray (LWN, 2018) — radix tree와 IDR을 대체하기 위해 XArray가 도입된 배경과 설계 철학을 다룹니다.
• IDR improvements (LWN, 2013) — IDR API 개선 작업과 idr_alloc() 도입 과정을 설명합니다.
• Replacing the IDR (LWN, 2018) — IDR 내부를 XArray 기반으로 전환한 과정과 마이그레이션 전략을 다룹니다.
• IDR — Kernel Newbies — IDR 사용법을 초보자 관점에서 간결하게 정리한 위키 문서입니다.
• lib/test_ida.c — Bootlin Elixir — IDA 자체 테스트 코드로, 할당·해제·경계 조건 등의 사용 패턴을 참고할 수 있습니다.
• kernel/pid.c — Bootlin Elixir — PID 할당에서 IDR을 실제로 활용하는 대표적인 커널 코드입니다.
• Documentation/core-api/idr.rst — Bootlin Elixir — IDR/IDA 커널 문서의 reStructuredText 원본 소스입니다.