해결해야 하는 흔한 문제 중 하나는, 일반적으로 무언가를 나타내는 작은 수인 식별자(ID) 를 할당하는 일이다. 이들은 파일 식별자(file descriptor), 프로세스 ID, 네트워크 프로토콜의 패킷 식별자, SCSI 태그들과 장치 객체 번호 등을 포함한다. IDR 과 IDA 는 그들의 독자적인 식별자 개발을 피하기 위한 문제에 대한 합리적인 해결책을 제시한다. IDR 은 포인터에 ID 를 매핑하는 능력을 제공한다. 반면 IDA 는 고유의 ID 할당을 제공하며, 결과적으로 이는 훨씬 더 메모리 효율적이다.

1. IDR (ID Radix)

위에서 설명했듯 IDR 은 ID 에 포인터 주소를 매핑한다. 이를 통해 ID 값에 객체를 매핑하여 사용할 수 있게 된다. 이름에서 알 수 있듯 IDR 은 radix tree 를 통해서 구현이 이뤄졌다. 그 구현을 살펴보면 radix tree 의 흔적을 많이 찾아볼 수 있다. IDR 은 DEFINE_IDR(name) 매크로를 통해 정의가 가능하며 매크로는 아래와 같이 정의되어 있다:

struct idr {
	struct radix_tree_root	idr_rt;
	unsigned int		idr_base;
	unsigned int		idr_next;
};

#define IDR_INIT_BASE(name, base) {					\
	.idr_rt = RADIX_TREE_INIT(name, IDR_RT_MARKER),			\
	.idr_base = (base),						\
	.idr_next = 0,							\
}

#define IDR_INIT(name)	IDR_INIT_BASE(name, 0)

#define DEFINE_IDR(name)	struct idr name = IDR_INIT(name)

위 내용은 include/linux/idr.h 에서 긁어온 내용이다. DEFINE_IDR(name) 은 최종적으로 IDR_INIT_BASE() 매크로로 확장되고 이는 RADIX_TREE_INIT 을 내부적으로 호출한다.

2. IDA (ID Allocator)

IDA 는 말 그대로 ID 를 할당해주는 할당기(allocator) 이다. IDA 의 정의 역시 include/linux/idr.h 파일에 정의되어 있다.

struct ida {
	struct xarray xa;
};

#define IDA_INIT(name)	{						\
	.xa = XARRAY_INIT(name, IDA_INIT_FLAGS)				\
}

#define DEFINE_IDA(name)	struct ida name = IDA_INIT(name)

3. IDR API

IDR 관련 API 함수들은 lib/idr.c 에 모두 정의되어 있다. 그 분량이 많아 모든 API 를 전부 소개하는 것을 어렵고 자주 사용되는 함수 위주로 설명하겠다.

1. IDR 할당: idr_alloc()

/**
 * idr_alloc() - ID 를 할당한다.
 * @idr: IDR 핸들.
 * @ptr: 새로운 ID 에 연관될 포인터.
 * @start: 최소 ID (합산적).
 * @end: 최대 ID (배타적).
 * @gfp: 메모리 할당 플래그.
 *
 * @start 와 @end 사이의 사용하지 않는 ID 를 할당한다.
 * 
 * Return: 새롭게 할당된 ID 를, 메모리 할당 실패 시 -ENOMEM 을, 자유 ID 를 찾는데 실패하면 -ENOSPC 을 반환한다.
 */
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;

	ret = idr_alloc_u32(idr, ptr, &id, end > 0 ? end - 1 : INT_MAX, gfp);
	if (ret)
		return ret;

	return id;
}

2. IDR 제거: idr_remove()

/**
 * idr_remove() - IDR 로부터 ID 를 제거한다.
 * @idr: IDR 핸들.
 * @id: 포인터 ID.
 *
 * IDR 로부터 ID 를 제거한다. 만일 ID 가 IDR 에 할당되어 있지 않았다면 NULL 을 반환한다.
 * Return: ID 와 연관되어 있었던 포인터를 반환한다.
 */
void *idr_remove(struct idr *idr, unsigned long id)
{
	return radix_tree_delete_item(&idr->idr_rt, id - idr->idr_base, NULL);
}

3. IDR 탐색: idr_find()

/**
 * idr_find() - 주어진 ID 에 대한 포인터를 반환한다.
 * @idr: IDR 핸들.
 * @id: 포인터 ID.
 *
 * 전달된 ID 에 연관된 포인터를 탐색한다. NULL 포인터는 @id 가 할당되어있지 않았거나 혹은 ID 가 NULL 포인터에 연관되어 있다면 나타낼 수 있다. 
 *
 * Return: ID 에 연관된 포인터를 반환한다.
 */
void *idr_find(const struct idr *idr, unsigned long id)
{
	return radix_tree_lookup(&idr->idr_rt, id - idr->idr_base);
}

4. IDR 조사: idr_for_each

/**
 * idr_for_each() - 저장된 모든 포인터에 대해 반복.
 * @idr: IDR 핸들.
 * @fn: 각각에 포인터에 대해 호출될 함수.
 * @data: 콜백 함수로 전달되어질 데이터.
 *
 * 콜백 함수는 각각의 @idr 엔트리에 대해 호출되어질 것이며, ID 와, 엔트리 그리고 @data 가 전달된다.
 * 만일 @fn 이 0 이 아닌 무언가를 반환한다면, 반복은 중단되고 해당 값은 이 함수로부터 반환되어진다.
 */
int idr_for_each(const struct idr *idr,
		int (*fn)(int id, void *p, void *data), void *data)
{
	struct radix_tree_iter iter;
	void __rcu **slot;
	int base = idr->idr_base;

	radix_tree_for_each_slot(slot, &idr->idr_rt, &iter, 0) {
		int ret;
		unsigned long id = iter.index + base;

		if (WARN_ON_ONCE(id > INT_MAX))
			break;
		ret = fn(id, rcu_dereference_raw(*slot), data);
		if (ret)
			return ret;
	}

	return 0;
}

4. idr 테스트 모듈

위에서 소개한 API 들을 바탕으로 간단한 테스트 모듈을 작성해보겠다.

#include <linux/kernel.h>
#include <linux/idr.h>
#include <linux/module.h>
#include <linux/slab.h>
#include <linux/errno.h>

struct item {
	unsigned long index;
	unsigned int order;
};

struct item *item_create(unsigned long index, unsigned int order)
{
	struct item *item = kmalloc(sizeof(*item), GFP_KERNEL);

	item->index = index;
	item->order = order;

	return item;
}

void item_delete(struct item *to_destroy)
{
	kfree(to_destroy);
}

int item_idr_free(int id, void *p, void *data)
{
	struct item *item = p;

	BUG_ON(item->index != id);
	kfree(p);

	return 0;
}

static int __init idr_test_start(void)
{
	unsigned int i, id, order;
	DEFINE_IDR(idr);
	struct item *item;
	void *deleted;
	
	pr_info("start idr test");

	pr_info("idr_alloc()....................\n");
	for (i = 0; i < 10; i++) {
		order = i * 10;
		item = item_create(i, order);
		id = idr_alloc(&idr, item, 0, 0, GFP_KERNEL);
		pr_info("i = %u, id = %u\n", i, id);
	}

	pr_info("idr_for_each_entry()...........\n");
	idr_for_each_entry(&idr, item, id) {
		pr_info("id = %u, item->index = %lu, order = %u\n",
				id, item->index, item->order);
	}

	pr_info("idr_find().....................\n");
	id = 5;

	item = (struct item *) idr_find(&idr, id);
	if (item)
		pr_info("found id = %d, item->index = %lu, order = %u\n",
				id, item->index, item->order);
	else
		pr_info("Not found (id = %u) \n", id);

	pr_info("idr_remove()...................\n");
	deleted = idr_remove(&idr, id);
	item_delete(deleted);

	item = (struct item *) idr_find(&idr, id);
	if (item) {
		pr_info("found id = %d, item->index = %lu, order = %u\n",
				id, item->index, item->order);
	} else {
		pr_info("Not found (id = %u) \n", id);
	}

	pr_info("idr_destroy()..................\n");
	idr_for_each(&idr, item_idr_free, &idr);
	idr_destroy(&idr);

	if (idr_is_empty(&idr))
		pr_info("idr is empty.\n");
	else
		pr_info("idr is not empty.\n");

	return 0;
}

static void __exit idr_test_end(void)
{
	pr_info("idr test end");
}

module_init(idr_test_start)
module_exit(idr_test_end)

MODULE_LICENSE("GPL");
MODULE_AUTHOR("Yeounsu Moon <yyyynoom@gmail.com>");
MODULE_DESCRIPTION("IDR test");

위 코드는 10 개의 id 를 idr 에 할당한 후 각 id 를 idr_for_each_entry() 를 통해 조회한다. 여기에서 idr_for_each_entry() 는 각 엔트리를 조회하는 for 반복문을 간소화한 매크로이다. 해당 코드는 include/linux/idr.h 에서 확인 가능하다.
그 다음으로 idr_find 를 통해 5 번 id 를 검색하고 해당 엔트리의 존재 유무(존재함)를 출력한다. 그 다음으로 앞서 idr_find 로 조회한 id 를 삭제하고 다시 그 엔트리의 존재 유무(존재하지 않음)를 출력한다.
마지막으로 idr_for_each 를 통해 idr 에 할당된 모든 엔트리를 제거하고 idr_is_empty() 함수의 결과를 출력한다. 실행 결과는 아래와 같다:

5. ida API

앞서 확인해본 idr 과 크게 다르지 않다. 앞서 설명했든 ida 는 유일한 id 만을 할당한다. 어떤 API 함수가 존재하는지 살펴보자.

1. id 할당: ida_alloc()

/**
 * ida_alloc() - 사용하지 않는 ID 를 할당한다.
 * @ida: IDA 핸들.
 * @gfp: 메모리 할당 플래그.
 *
 * 0 과 INT_MAX 사이의 값을 합산적으로 할당한다.
 *
 * Return: 할당된 ID, 혹은 메모리 할당 실패 시 -ENOMEM 을, 혹은 자유 ID 가 없을 시 -ENOSPC 을 반환한다.
 */
static inline int ida_alloc(struct ida *ida, gfp_t gfp)
{
	return ida_alloc_range(ida, 0, ~0, gfp);
}

2. id 할당 (최솟값): ida_alloc_min()

/**
 * ida_alloc_min() - 사용하지 않는 ID 를 할당한다.
 * @ida: IDA 핸들.
 * @min: 할당한 ID 의 최소값.
 * @gfp: 메모리 할당 플래그.
 *
 * @min 과 INT_MAX 사이의 ID 를 합산적으로 할당한다.
 *
 * Return: 할당된 ID, 혹은 메모리 할당 실패 시 -ENOMEM 을, 혹은 자유 ID 가 없을 시 -ENOSPC 을 반환한다.
 */
static inline int ida_alloc_min(struct ida *ida, unsigned int min, gfp_t gfp)
{
	return ida_alloc_range(ida, min, ~0, gfp);
}

3. id 할당 (최댓값): ida_alloc_max()

/**
 * ida_alloc_max() - 사용하지 않는 ID 를 할당한다.
 * @ida: IDA 핸들.
 * @max: 할당한 ID 의 최대값.
 * @gfp: 메모리 할당 플래그.
 *
 * 0 과 @max 사이의 ID 를 합산적으로 할당한다.
 *
 * Return: 할당된 ID, 혹은 메모리 할당 실패 시 -ENOMEM 을, 혹은 자유 ID 가 없을 시 -ENOSPC 을 반환한다.
 */
static inline int ida_alloc_max(struct ida *ida, unsigned int max, gfp_t gfp)
{
	return ida_alloc_range(ida, 0, max, gfp);
}

4. id 해제: ida_free()

/**
 * ida_free() - 할당된 ID 를 해제한다.
 * @ida: IDA handle.
 * @id: 이전에 할당되었던 ID.
 */
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);

	xas_lock_irqsave(&xas, flags);
	bitmap = xas_load(&xas);

	if (xa_is_value(bitmap)) {
		unsigned long v = xa_to_value(bitmap);
		if (bit >= BITS_PER_XA_VALUE)
			goto err;
		if (!(v & (1UL << bit)))
			goto err;
		v &= ~(1UL << bit);
		if (!v)
			goto delete;
		xas_store(&xas, xa_mk_value(v));
	} else {
		if (!test_bit(bit, bitmap->bitmap))
			goto err;
		__clear_bit(bit, bitmap->bitmap);
		xas_set_mark(&xas, XA_FREE_MARK);
		if (bitmap_empty(bitmap->bitmap, IDA_BITMAP_BITS)) {
			kfree(bitmap);
delete:
			xas_store(&xas, NULL);
		}
	}
	xas_unlock_irqrestore(&xas, flags);
	return;
 err:
	xas_unlock_irqrestore(&xas, flags);
	WARN(1, "ida_free called for id=%d which is not allocated.\n", id);
}

5. ida 가 비어있는가?: ida_is_empty()

static inline bool ida_is_empty(const struct ida *ida)
{
	return xa_empty(&ida->xa);
}

6. ida 테스트 모듈

위에서 살펴본 ida 의 API 를 사용해서 간단한 테스트 모듈을 작성해볼 것이다. 위에서 작성했던 idr 과 크게 다를바 없다.

#include <linux/kernel.h>
#include <linux/idr.h>
#include <linux/module.h>
#include <linux/slab.h>
#include <linux/errno.h>

static int __init ida_test_start(void)
{
	int i, id;
	DEFINE_IDA(ida);

	pr_info("start ida test");

	pr_info("ida_alloc()....................\n");

	for (i = 0; i < 10; i++) {
		id = ida_alloc(&ida, GFP_KERNEL);
		pr_info("id = %d\n", id);
	}

	pr_info("ida_free().....................\n");

	ida_free(&ida, 3);
	ida_free(&ida, 5);

	for (i = 0; i < 5; i++) {
		id = ida_alloc(&ida, GFP_KERNEL);
		pr_info("id = %d\n", id);
	}

	pr_info("ida_destroy()..................\n");
	ida_destroy(&ida);

	if (ida_is_empty(&ida))
		pr_info("ida is empty.\n");
	else
		pr_info("ida is not empty.\n");

	return 0;
}

static void __exit ida_test_end(void)
{
	pr_info("ida test end");
}

module_init(ida_test_start)
module_exit(ida_test_end)

MODULE_LICENSE("GPL");
MODULE_AUTHOR("Yeounsu Moon <yyyynoom@gmail.com>");
MODULE_DESCRIPTION("IDA test");

id 를 ida 에 10 개 할당하고 이 중 id 3번과 5번을 해제한다. 이후 다시 다시 id 를 5개 더 할당한다.

주목해서 봐야 할 부분은 id 의 할당이 앞서 해제했던 3번과 5번부터 다시 할당된다는 점이다.

출처

[책] 리눅스 커널 소스 해설: 기초 입문 (정재준 저)
[사이트] https://www.kernel.org/doc/html/latest/core-api/idr.html
[사이트] https://titanwolf.org/Network/Articles/Article?AID=efa69f12-c4ec-4f76-8a18-91603ca47c72
[사이트] https://lwn.net/Articles/103209/