Egloos | Log-in
F/OSS study
F/OSS study
[Linux] IDR & IDA - integer ID 관리
linux: 2.6.31


IDR은 radix tree의 일종으로 정수 ID와 특정한 포인터 값을 연결시키는 역할을 해 준다.
원래는 POSIX timer 관련 시스템 콜 구현을 위해 작성된 것으로
특정한 timer 객체를 다룰 수 있는 ID를 생성해 주는 역할을 하였으나
현재는 각종 장치 드라이버나 VFS 레이어에서도 널리 사용된다.

일반적인 사용자 모드 라이브러리의 경우라면 객체의 포인터를 직접 반환하여 처리하는 것이
보다 빠르고 편리할 수도 있겠지만 이 timer 객체는 커널 주소 공간 내에 존재하므로
사용자 프로그램에서 직접 접근하도록 포인터를 넘길 수는 없다.

IDR은 주어진 포인터를 받아서 그에 대응하는 정수 ID를 만들어주며
해당 ID를 통해 빠르게 원래 포인터를 찾아낼 수 있다.

IDR에서 사용되는 자료 구조를 먼저 살펴보도록 한다.

struct idr {
    struct idr_layer *top;
    struct idr_layer *id_free;
    int          layers; /* only valid without concurrent changes */
    int          id_free_cnt;
    spinlock_t      lock;
};

idr 구조체는 IDR의 API에서 직접 사용되는 자료 구조로 IDR의 현재 상태에 대한 전반적인 정보를 제공한다.
실제 ID 정보는 아래에서 살펴볼 idr_layer 구조체에 tree 형식으로 저장되는데
top 필드는 IDR 레이어의 가장 윗단을 가리킨다. (tree의 root라고 생각하면 된다.)
layers 필드는 현재 idr 구조체가 포함하는 레이어의 수이다. (tree의 height에 해당한다.)
id_free 필드는 예비용으로 보관 중인 여유 레이어들의 리스트이다.
id_free_cnt 필드는 id_free 필드에 연결된 레이어의 개수이다.
마지막으로 lock 필드는 이 idr 구조체에 대한 접근을 보호하는 락이다.

struct idr_layer {
    unsigned long         bitmap; /* A zero bit means "space here" */
    struct idr_layer    *ary[1<<IDR_BITS];
    int             count;     /* When zero, we can release it */
    int             layer;     /* distance from leaf */
    struct rcu_head         rcu_head;
};

idr_layer 구조체는 실제 ID와 포인터 정보를 저장하는 자료 구조로 tree에서의 node에 해당하며
leaf node일 때와 아닐 때에 각 필드의 용도가 조금씩 다르다.
먼저 bitmap 필드는 현재 레이어 내에서 비어있는 공간이 있는지를 나타낸다.
leaf node인 경우 각 비트는 정수 ID에 매핑되며 비트값이 0이라면 해당 ID를 사용할 수 있다.
non-leaf node인 경우 각 비트는 대응하는 하위 레이어 내에 비어있는 공간이 있는지를 나타낸다.
ary 배열은 leaf node인 경우 bitmap의 비트에 해당하는 ID에 대응하는 포인터 값을 저장한다.
non-leaf node인 경우 하위 레이어에 대한 포인터를 저장한다.
IDR_BITS 값은 long 자료형이 저장할 수 있는 비트 수의 log 값으로 32비트에서는 5가 된다.
count 필드는 bitmap 필드에서 1로 설정된 비트의 수로
leaf node인 경우 현재 레이어에서 할당된 ID의 수를 나타내며
non-leaf node인 경우 할당된 하위 레이어의 수를 나타낸다.
layer 필드는 leaf node에서는 0이며 상위 레이어로 갈수록 1씩 증가된다.
rcu_head는 idr_layer를 RCU를 통해 제거할 때 사용된다.

아래의 그림은 2개의 레이어로 구성된 IDR 자료구조를 보여준다.


위의 그림은 0부터 33까지의 ID를 생성 후
중간을 건너뛰고 100번의 ID를 생성하도록 요청한 후의 모습이다.
처음 32개 (0부터 31까지)의 ID 생성 요청은 1 레이어에서 해결할 수 있지만
그 이후가 되면 상위 레이어를 하나 추가해야 하므로 총 레이어 수는 2가 되고
상위 레이어의 bitmap은 해당 하위 레이어가 모두 할당된 경우에만 1로 설정된다.

idr->top->ary[0]에 해당하는 첫번째 leaf node는 모든 비트가 할당되었으므로
ary 배열 전체는 해당하는 포인터 값으로 설정되어 있지만
idr->top->ary[1]과 ary[2]의 leaf node는 각각
ary[0], ary[1] 및 ary[8] 항목 만이 의미있는 값을 가진다.

만약 현재 레이어 내의 모든 비트맵이 할당되어 레이어가 증가해야 하는 경우에는
새로운 top 레이어가 할당되고 기존의 top 레이어는 idr->top->ary[0]으로 설정된다.
그리고 idr->top->ary[1]에서 시작하는 새로운 node들이 만들어지는데
이 때 idr 구조체의 id_free에 저장된 idr_layer 구조체들이 사용된다.
IDR에서는 모든 정보는 leaf node에 저장되므로
일반적으로 (순차적으로) ID가 커짐에 따라 레이어가 늘어나게되면
새로운 tree의 height 만큼의 구조체가 할당되어야 한다.

idr을 사용할 때는 다음과 같은 API를 이용해야 한다.
(단 IDR의 초기화는 마친 상태라고 가정한다.)

struct idr *idp;
int new_id;
int error;
spinlock_t lock;
...

restart:
if (idr_pre_get(idp, GFP_KERNEL) == 0)
   /* error */

spin_lock(&lock);
error = idr_get_new(idp, some_pointer, &new_id);
spin_unlock(&lock);
if (error) {
   if (error == -EAGAIN)
      goto restart;
   /* error */
}

idr_get_new()보다 idr_pre_get()을 먼저 실행하는 이유는
idr_get_new() 시에 레이어가 늘어나야하는 경우 해당 시점에서 메모리를 할당하지 않고
idr_pre_get()에서 미리 할당해 둔 여유 레이어 객체를 사용하기 위함이다.
따라서 할당 시에는 sleep하지 않는다는 것을 보장할 수 있으며
때문에 idr_get_new는 atomic한 환경에서도 사용할 수 있다. (확인 필요..)

idr_get_new() 호출 시마다 매번 idr_pre_get()을 호출할 필요는 없지만
idr_pre_get()을 호출하지 않고 idr_get_new()를 반복적으로 호출하다보면
결국 -EAGAIN 오류를 반환할 것이다.

idr_pre_get()은 최대 레이어 수의 2배 만큼의 메모리를 확보하는데
최악의 경우 1단계의 레이어 만 가지고 있을 때 가장 큰 수의 ID 요청을 받는 경우
중간 단계의 레이어들을 생성하기 위한 것으로 보인다.
참고로 특정한 수 이상의 ID를 요청하려면 idr_get_new() 대신 idr_get_new_above()을 사용하면 된다.

주어진 ID를 가지고 원래의 (객체) 포인터를 찾기 위해서는 idr_find()를 사용할 수 있다.
또한 이미 할당한 ID를 해제하려면 idr_remove()를 사용한다.
idr_remove()를 통해 중간의 ID가 해제되면 상위 레이어부터 leaf node에 이르기까지
해당 비트가 모두 clear되므로 IDR은 이를 쉽게 알아낼 수 있고
따라서 해당 ID를 곧바로 재사용할 수 있다.

IDA는 IDR의 구조를 이용하는 ID 할당자로써
포인터를 저장할 필요없이 단순히 ID 만을 생성하는 목적으로 사용한다.
(ID 할당을 위해 단순한 카운터 변수를 이용하는 것을 생각할 수 있겠지만
ID가 자주 생성/제거되는 상황이라면 효율성이 떨어질 수 있다.)

IDA는 IDR의 레이어 구조를 이용하지만
leaf node의 경우 idr_layer 내의 bitmap 필드를 이용하지 않고
독자적인 ida_bitmap 구조체를 ary 배열에 할당하여 사용한다.
레이어의 단계를 낮추기 위해 IDA에서는 128 바이트로 이루어진 비트맵을 이용한다.
(idr.h에서 IDA_CHUNKSIZE는 128로 정의되어 있지만 long 타입 크기 계산 시 1이 감소되어
실제로는 124 바이트 (= 992 비트)가 사용된다???)

IDA의 사용법은 IDR과 거의 유사하며 인자로 전달하던 포인터 변수 만 제거하면 된다.
ida_get_new()는 0부터 시작하는 ida_get_new_above()으로 구현되며
ida_get_new_above() 내부적으로 idr 레이어의 인덱스를 맞추기 위해
주어진 시작 ID 값을 IDA에서 사용하는 비트맵 크기로 나누어 IDR API를 호출한다.

아래는 IDA를 이용하여 ID를 할당받는 간단한 예제이다.

struct ida *idp;
int new_id;
int error;
spinlock_t lock;
...

restart:
if (ida_pre_get(idp, GFP_KERNEL) == 0)
   /* error */

spin_lock(&lock);
error = ida_get_new(idp, &new_id);
spin_unlock(&lock);
if (error) {
   if (error == -EAGAIN)
      goto restart;
   /* error */
}


=== 참고 문서 ===
by namhyung | 2009/12/03 20:20 | Kernel | 트랙백(1) | 덧글(1)
트랙백 주소 : http://studyfoss.egloos.com/tb/5187192
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
Tracked from at 2014/03/11 00:27

제목 : garcinia cambogia products
line4...more

Commented by 박주병 at 2015/03/09 04:40
리눅스 소스보다가 ldr궁금해서 검색해보니 여기에 있었네요.. 감사합니다.
본문 내용 퍼가기도 하였습니다. 출처랑은 전부다 명시 하였습니다.

:         :

:

비공개 덧글

◀ 이전 페이지 다음 페이지 ▶

카테고리
General
Application
System
Kernel
Book
Tips
태그
compiler linux emacs computer-architecture perf git scm binutils vcs documentation x86 build awk gcc blktrace block-layer SMP sed script patch kernel CARM bash memory glibc C CAaQA3 synchronization elf algorithm
전체보기
이글루 파인더

최근 등록된 덧글
informsi yang bagus dan b..
by agen qnc at 06/22
informasi yang bagus dan b..
by agen qnc at 06/22
informasi yang bagus dan b..
by agen qnc at 06/22
최근 등록된 트랙백
Tod's Ferrari Homme
by Tods Pas Cher,Kodak did ..
Mocassin Femme
by Mocassins Homme, I got so..
natural garcinia cambogia
by
rss

skin by jiinny


X