IDR/IDA (ID Allocator)

Linux 커널의 정수 ID 할당 메커니즘인 IDR(ID Radix tree)과 IDA(ID Allocator)의 설계 원리, API 사용법, 파일 디스크립터/PID/디바이스 번호 할당 등 실제 활용 사례를 다룹니다. 현재는 XArray 기반으로 재구현되었지만 레거시 API가 광범위하게 사용됩니다.

개요 (Overview)

IDR(ID Radix tree)과 IDA(ID Allocator)는 정수 ID를 효율적으로 관리하는 자료구조입니다:

• IDR — ID와 포인터를 매핑합니다. 파일 디스크립터, IPC ID 등에 사용됩니다.
• IDA — ID만 할당합니다(포인터 저장 없음). 디바이스 번호, PID 등에 사용됩니다.

IDR 내부 구조

IDR은 현재 XArray를 기반으로 구현되어 있으며, ID를 인덱스로 사용하는 희소 배열입니다:

IDR API

기본 사용법

/* include/linux/idr.h */
struct idr {
    struct xarray idr_rt;
    unsigned int idr_base;
    unsigned int idr_next;
};

/* 초기화 */
DEFINE_IDR(my_idr);  /* 정적 */
void idr_init(struct idr *idr);  /* 동적 */

/* ID 할당 및 포인터 저장 */
int idr_alloc(struct idr *idr, void *ptr,
                int start, int end, gfp_t gfp);
/* 반환: 할당된 ID (음수는 에러) */
/* start: 최소 ID, end: 최대 ID (exclusive) */

/* ID로 포인터 찾기 */
void *idr_find(struct idr *idr, unsigned long id);

/* ID 제거 */
void *idr_remove(struct idr *idr, unsigned long id);

/* 전체 해제 */
void idr_destroy(struct idr *idr);

사용 예제

/* 간단한 IDR 사용 예 */
DEFINE_IDR(device_idr);

struct device {
    int id;
    char name[32];
};

/* 디바이스 등록 */
int register_device(struct device *dev)
{
    int id;

    /* ID 0-1000 범위에서 할당 */
    id = idr_alloc(&device_idr, dev, 0, 1000, GFP_KERNEL);
    if (id < 0)
        return id;

    dev->id = id;
    pr_info("Device registered with ID %d\n", id);
    return 0;
}

/* 디바이스 검색 */
struct device *find_device(int id)
{
    return idr_find(&device_idr, id);
}

/* 디바이스 제거 */
void unregister_device(int id)
{
    struct device *dev = idr_remove(&device_idr, id);
    if (dev) {
        pr_info("Device %d unregistered\n", id);
        kfree(dev);
    }
}

IDR 순회

/* 모든 엔트리 순회 */
int id;
struct device *dev;

idr_for_each_entry(&device_idr, dev, id) {
    pr_info("Device %d: %s\n", id, dev->name);
}

/* 특정 ID부터 순회 */
int start_id = 100;
idr_for_each_entry_continue(&device_idr, dev, start_id) {
    /* ... */
}

IDA API

IDA는 포인터 저장 없이 ID만 할당합니다. 메모리 효율적입니다:

/* include/linux/idr.h */
struct ida {
    struct xarray xa;
};

/* 초기화 */
DEFINE_IDA(my_ida);
void ida_init(struct ida *ida);

/* ID 할당 */
int ida_alloc(struct ida *ida, gfp_t gfp);
int ida_alloc_range(struct ida *ida, unsigned int min,
                       unsigned int max, gfp_t gfp);

/* ID 해제 */
void ida_free(struct ida *ida, unsigned int id);

/* 전체 해제 */
void ida_destroy(struct ida *ida);

/* 사용 예 */
DEFINE_IDA(minor_ida);

int alloc_minor(void)
{
    return ida_alloc_range(&minor_ida, 0, 255, GFP_KERNEL);
}

void free_minor(int minor)
{
    ida_free(&minor_ida, minor);
}

ID 할당/해제 과정

IDR에서 ID를 할당하고 해제할 때 내부 상태가 어떻게 변하는지 시각화:

실사용 사례

파일 디스크립터

파일 디스크립터 할당은 IDR의 가장 중요한 사용 사례입니다. 범위 제약이 있는 예제:

/* fs/file.c */
struct files_struct {
    struct fdtable __rcu *fdt;
    unsigned long open_fds_init[1];  /* 초기 비트맵 */
    struct file __rcu *fd_array[NR_OPEN_DEFAULT];
    /* ... */
};

/* 프로세스별 파일 디스크립터 제한 */
int get_unused_fd_flags(unsigned flags)
{
    return __alloc_fd(current->files, 0, rlimit(RLIMIT_NOFILE), flags);
}

/* __alloc_fd의 간소화된 구현 */
int __alloc_fd(struct files_struct *files,
               unsigned start, unsigned end, unsigned flags)
{
    unsigned int fd;
    struct fdtable *fdt;

    fdt = files_fdtable(files);

    /* start부터 end 범위에서 빈 fd 검색 */
    fd = start;
    while (fd < end) {
        if (!test_bit(fd, fdt->open_fds))
            break;
        fd++;
    }

    if (fd >= end)
        return -EMFILE;  /* 파일 디스크립터 고갈 */

    __set_open_fd(fd, fdt);
    return fd;
}

범위 지정 실전 예제

/* 특정 범위에서 fd 할당 예제 */

/* 예제 1: 100-200 범위에서 할당 */
int fd = __alloc_fd(current->files, 100, 200, 0);
if (fd < 0) {
    pr_err("범위 100-200에서 fd 할당 실패\n");
} else {
    pr_info("할당된 fd: %d\n", fd);
}

/* 예제 2: 0부터 시스템 제한까지 */
int fd = get_unused_fd_flags(O_CLOEXEC);
/* O_CLOEXEC: exec 시 자동으로 닫힘 */

/* 예제 3: dup2()로 특정 fd 강제 할당 */
int new_fd = 10;
if (dup2(old_fd, new_fd) < 0) {
    perror("dup2");
}

디바이스 번호

/* drivers/base/devtmpfs.c */
static DEFINE_IDA(devtmpfs_ida);

int alloc_chrdev_region(dev_t *dev, unsigned baseminor,
                        unsigned count, const char *name)
{
    int ret = ida_alloc_range(&devtmpfs_ida, baseminor,
                                 baseminor + count - 1, GFP_KERNEL);
    if (ret < 0)
        return ret;

    *dev = MKDEV(ret, baseminor);
    return 0;
}

PID 할당

/* kernel/pid.c */
struct pid_namespace {
    struct idr idr;
    /* ... */
};

struct pid *alloc_pid(struct pid_namespace *ns)
{
    struct pid *pid;
    int nr;

    pid = kmem_cache_alloc(pid_cachep, GFP_KERNEL);
    if (!pid)
        return NULL;

    nr = idr_alloc(&ns->idr, pid, 1, pid_max, GFP_KERNEL);
    if (nr < 0) {
        kmem_cache_free(pid_cachep, pid);
        return NULL;
    }

    pid->numbers[0].nr = nr;
    return pid;
}

IDR vs IDA 비교

선택 기준 플로우차트

IDR과 IDA 중 어떤 것을 사용할지 결정하는 플로우차트:

성능 특성

XArray로 마이그레이션

새로운 코드에서는 IDR 대신 XArray를 직접 사용하는 것이 권장됩니다:

/* 기존 IDR 코드 */
DEFINE_IDR(my_idr);
int id = idr_alloc(&my_idr, ptr, 0, INT_MAX, GFP_KERNEL);
void *ptr = idr_find(&my_idr, id);
idr_remove(&my_idr, id);

/* XArray로 변환 */
DEFINE_XARRAY_ALLOC(my_xarray);
int id;
xa_alloc(&my_xarray, &id, ptr, XA_LIMIT(0, INT_MAX), GFP_KERNEL);
void *ptr = xa_load(&my_xarray, id);
xa_erase(&my_xarray, id);

IDR/IDA 운영 루틴

ID 할당기는 누수와 중복 할당이 가장 큰 리스크입니다. 할당/조회/해제의 대칭성을 코드 리뷰 기준으로 고정해야 합니다.

1. 할당 실패 처리: idr_alloc/ida_alloc 반환값 검사
2. 해제 대칭성: 모든 성공 경로에 대응하는 idr_remove/ida_free 확인
3. 범위 정책: 최소/최대 ID 범위를 시스템 정책과 일치시킴
4. 마이그레이션 판단: 신규 경로는 가능하면 XArray 직접 사용 고려

관련 문서

• XArray — IDR의 후속 자료구조
• Radix Tree — IDR의 이전 구현
• Bitmap — IDA 내부 구조
• 프로세스 관리 — PID 할당