이번 장에서는 리눅스 커널의 또 하나의 자료구조, 레드-블랙 트리(red-black tree
) 에 대해서 살펴 보도록 하겠다. 레드-블랙 트리는 그 자체로 두-세개 이상의 글을 할애해야 할 정도로 그 내용이 많기에, 알고리즘을 직접적으로 설명하진 않고 커널에서 어떻게 이를 다루는지에 초점을 맞춰 진행하겠다.
시간이 된다면 레드 블랙 트리에 대한 글은 따로 작성토록 하겠다.
레드 블랙 트리는 이진 탐색 트리에서 좀 더 발전된 자가 균형 이진 탐색 트리(Self‑balancing binary search tree
)이다. 일반적인 이진 탐색 트리는 삽입 순서에 따라 최악의 경우 n
개의 원소에 대해 n
번의 탐색을 시도해야 할 수도 있다. 반대로 레드 블랙 트리는 각 원소를 적절하게 좌우로 삽입하여 불균형을 완화하고 개략적(roughly
) 으로 균형을 잡는다.
이진 탐색 트리는 탐색에 대한 인 반면 레드 블랙 트리는 탐색에 대한 효율이 이다. 그래서 리눅스 커널은 보통 데이터의 양이 적을 때에는 상대적으로 간단한 구조의 연결 리스트를 사용하고 데이터의 양이 많아지면 탐색 효율을 위해 레드 블랙 트리를 사용한다.
get_cycles()
이번 장에서는 리눅스 커널의 레드 블랙 트리 성능을 분석할 예정이다. 따라서 성능 분석에 사용할 도구인 get_cycles()
함수에 대해 먼저 간단하게 설명하고 시작하겠다.
get_cycles()
함수는 CPU
의 사이클 함수를 반환하는 함수로 아키텍처에 독립적인 함수이다. CPU
사이클을 반환하는 함수이므로 아키텍쳐의 종속적인 것이 아닐까? 생각할 수 있다. 맞다, 실제로 get_cycles()
함수는 아키텍처의 의존적인 rdtsc()
함수를 래핑하여 만든 함수이다. 필자는 x86
을 사용하고 rdtsc()
함수는 다음과 같이 정의되어 있다.
arch/x86/include/asm/msr.h
에서 그 내용을 확인할 수 있다.
get_cycles()
함수는 arch/x86/include/asm/tsc.h
에 위와 같이 정의되어 있다.
get_cycles()
함수를 테스트하기 위한 간단한 모듈을 작성해보았다:
#include <linux/kernel.h>
#include <linux/module.h>
static void busy_loop(u64 iters)
{
volatile int sink;
do {
sink = 32;
sink += 1;
sink /= 4;
} while (--iters > 0);
(void) sink;
}
#define LOOPS_CNT (1024 * 1024 * 100)
static int __init test_cycles_init(void)
{
u64 time1, time2, time3;
u64 cycles = 0;
printk("test_cycles_init() start...\n");
for (int i = 0; i < 10; i++) {
time1 = get_cycles();
busy_loop(LOOPS_CNT);
time2 = get_cycles();
time3 = time2 - time1;
cycles += time3;
printk("loop_rdtsc %02d: run_cycles = %llu, one call: %llu cycles\n",
i + 1, time3, div_u64(time3, LOOPS_CNT));
}
time1 = div_u64(cycles, LOOPS_CNT * 10);
printk("loop_rdtsc average: one call = %llu cycles\n", time1);
printk("test_cycles_init() end.\n");
return 0;
}
static void __exit test_cycles_exit(void)
{
printk("test_cycles_exit().\n");
}
module_init(test_cycles_init);
module_exit(test_cycles_exit);
MODULE_LICENSE("GPL v2");
위 코드는 대입, 덧셈, 나눗셈, 뺄셈을 수행하는 코드를 1024 * 1024 * 100
번 수행하는 busy_loop
함수를 호출하여 걸리는 시간을 측정하는 코드이다. 함수 한번의 호출에 걸리는 사이클과 한번의 반복에 걸리는 사이클을 출력한다.
결과는 위와 같았다. 네 개의 연산(대입, 덧셈, 나눗셈, 뺄셈)을 수행하는데 오직 세 사이클만이 소요되었다.
리눅스 커널은 reb-black tree
테스트를 위한 예제 코드를 제공한다. 해당 소스를 통해 red-black tree
의 노드 삽입, 삭제, 탐색에 대한 성능 테스트를 진행해보겠다.
해당 소스는 lib/rbtree_test.c
에 있으므로 이를 확인하겠다.
rbtree
구조체 메모리 할당 및 초기화 가장 먼저 모듈이 삽입되었을 때 실행되는 함수는 rbtree_test_init()
이다.
static int __init rbtree_test_init(void)
{
int i, j;
cycles_t time1, time2, time;
struct rb_node *node;
// nnodes = 100, pref_loops = 1000
nodes = kmalloc_array(nnodes, sizeof(*nodes), GFP_KERNEL);
if (!nodes)
return -ENOMEM;
printk(KERN_ALERT "rbtree testing");
prandom_seed_state(&rnd, 3141592653589793238ULL);
init();
가장 먼저 레드 블랙 트리의 노드를 동적할당한 이후 init()
함수를 호출하여 각 노드의 value
와 key
값을 임의의 난수로 초기화한다. 초기화하는 대상은 node
가 아닌 nodes
이고 이는 아래와 같이 정의되어 있다:
struct test_node {
u32 key;
struct rb_node rb;
/* following fields used for testing augmented rbtree functionality */
u32 val;
u32 augmented;
};
static struct rb_root_cached root = RB_ROOT_CACHED;
static struct test_node *nodes = NULL;
time1 = get_cycles();
for (i = 0; i < perf_loops; i++) {
for (j = 0; j < nnodes; j++)
insert(nodes + j, &root);
for (j = 0; j < nnodes; j++)
erase(nodes + j, &root);
}
time2 = get_cycles();
time = time2 - time1;
time = div_u64(time, perf_loops);
printk(" -> test 1 (latency of nnodes insert+delete): %llu cycles\n",
(unsigned long long)time);
가장 먼저 time1
을 get_cycles()
함수의 반환값으로 초기화(현재 사이클을 저장)한다. 이후 perf_loops
만큼 nnodes
개의 노드를 삽입하고 삭제하는 작업을 반복한다. 실행이 끝나면 time2
에 다시 현재 사이클을 저장하여 그 차이(수행에 걸린 사이클)를 출력한다.
테스트 2 는 insert
와 erase
가 insert_cached
와 erase_cached
로 바뀌었을 뿐 테스트 1 과 큰 차이는 없다.
inorder
) time1 = get_cycles();
for (i = 0; i < perf_loops; i++) {
for (node = rb_first(&root.rb_root); node; node = rb_next(node))
;
}
time2 = get_cycles();
time = time2 - time1;
time = div_u64(time, perf_loops);
printk(" -> test 3 (latency of inorder traversal): %llu cycles\n",
(unsigned long long)time);
테스트 3 은 rb_first()
를 호출하고 이후 rb_next()
함수를 반복적으로 호출하여, 트리를 inorder
(중위순회) 방식으로 방문하는데 걸리는 시간을 출력한다.
leftmost
) time1 = get_cycles();
for (i = 0; i < perf_loops; i++)
node = rb_first(&root.rb_root);
time2 = get_cycles();
time = time2 - time1;
time = div_u64(time, perf_loops);
printk(" -> test 4 (latency to fetch first node)\n");
printk(" non-cached: %llu cycles\n", (unsigned long long)time);
time1 = get_cycles();
for (i = 0; i < perf_loops; i++)
node = rb_first_cached(&root);
time2 = get_cycles();
time = time2 - time1;
time = div_u64(time, perf_loops);
printk(" cached: %llu cycles\n", (unsigned long long)time);
테스트 4 는 rb_first
그리고 rb_first_cached
함수를 반복적으로 호출하여 걸리는 시간을 출력한다. rb_first
는 가장 왼쪽(leftmost
)의 원소를 찾기 위해 트리를 따라 내려가는 반면 cached
는 미리 가장 왼쪽의 노드를 저장해두었다가 반환한다.
실행 결과는 매우 직관적이다. 각 테스트에 걸린 사이클 수를 출력하는데 테스트 4 의 경우 cached
에 0 사이클이 소요되었다. 이는 rb-tree
가 leftmost
노드의 위치를 기억해두었다가 반환하기 때문이다. augmented rbtree
는 위에서 소개하지 않은 내용인데 rbtree
에 추가적인 정보(단일 키가 아닌 범위에 해당하는)를 더 저장한다. 자세한 내용은 출처를 참조하길 바란다.
[그래프] https://www.desmos.com/calculator
[책] 리눅스 커널 소스 해설: 기초 입문 (정재준 저)
[이미지] https://ko.wikipedia.org/wiki/레드-블랙_트리
[사이트] https://www.kernel.org/doc/Documentation/rbtree.txt