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 경합을 막으려면 상위 락을 잡아야 합니다. 문제는 그 락을 잡은 상태에서 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 내부 비트맵과 청크 구조

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로 인스턴스 번호만 예약하는 예

반대로 객체 포인터는 해시테이블, 배열, 리스트 등 다른 곳에 이미 있고 "중복 없는 번호만 필요"하다면 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이 "없음"인지 "예약됨"인지 애매하면 디버깅이 매우 어려워집니다.

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;
}

IDA 비트맵 내부 구조

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

ida_bitmap 구조체 레이아웃

커널 헤더(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;
}

Cyclic 할당 메커니즘

일반 idr_alloc()는 항상 가장 낮은 빈 ID를 반환합니다. 하지만 네트워크 프로토콜 식별자나 트랜잭션 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를 통해), 핸들 삭제 시 참조 카운트만 감소시킵니다.

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 재활용과 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 호출을 실시간으로 관찰할 수 있습니다.

# 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 성능을 커널 모듈에서 측정하는 기본 틀입니다. 실제 벤치마크 시에는 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와 인터페이스 격리

네트워크 namespace는 PID namespace와 마찬가지로, 각 namespace가 독립된 네트워크 스택을 가집니다. 따라서 호스트의 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. 핫 패스 최적화: 조회가 빈번한 경로(패킷 수신 등)에서는 해시 테이블을 병행하여 O(1) 조회를 보장합니다.

관련 문서

• 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 번호 관리 경로임을 확인할 수 있는 소스