Linux Tutorial #23 IDR(ID Radix), IDA(ID Allocator)
해결해야 하는 흔한 문제 중 하나는, 일반적으로 무언가를 나타내는 작은 수인 식별자(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 <[email protected]>");
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 <[email protected]>");
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/
Author And Source
이 문제에 관하여(Linux Tutorial #23 IDR(ID Radix), IDA(ID Allocator)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@mythos/Linux-Tutorial-23-IDRID-Radix-IDAID-Allocator저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
좋은 웹페이지 즐겨찾기
