[3기 대전 김재원] Linux Kernel - Data Structure (2)

안녕하세요! 대전멤버십 Elite Member 3기 김재원입니다.

지난번에 이어서 Linux Kernel에서 제공하고 있는 Data Structure에 대해 알아보도록 하겠습니다.

지난포스팅에서는 Linux Kernel에서 가장 많이 사용하고 있는 List에 대해 알아 보았고, 

이번 시간에는 Queue라고 할수 있는 FIFO와 RB_TREE에 대해서 알아 보도록 하겠습니다.

FIFO(Queue)

Linux Kernel에서는 kfifo라는 이름으로 Queue를 제공하고 있습니다.

kfifo와 관련된 헤더는 <linux/kfifo.h>에 정의 되어 있으며 구현은 kernel/kfifo.c 파일에 구현되어 있습니다. 

kfifo역시 List와 비슷하게 Macro와 함수가 섞여서 구현되어 있습니다.

예를 들어 kfifo_in을 호출하면 Macro를 통해 여러작업을 거친후 __kfifo_in 함수를 다시 호출 하게 됩니다. kfifo 구조체 역시 실제로는 __kfifo 구조체를 Macro를 통해 정의 해놓았습니다.

우선 kfifo 구조체를 살펴 보면 다음과 같습니다

struct kfifo

kfifo에는 시작과 끝의 위치, 크기, 데이터의 주소와 같은 정보들을 가지고 있습니다.

1. kfifo 생성 및 초기화

생성하는 방법에는 2가지가 있습니다.

● kfifo_alloc을 이용하는 방법

__kfifo_alloc 정의

kfifo_alloc()은 크기를 지정해주면 함수내부에서 kmalloc을 이용하여 메모리를 할당을 받아 kfifo를 구성하도록 되어 있습니다.

● kfifo_init을 이용하는 방법

__kfifo_init 정의

kfifo_init()의 경우 미리 할당된 메모리의 주소를 buffer에 넣어 kfifo를 구성하도록 되어 있습니다.

위와 두 방법으로 kfifo를 정의하고 초기화 할 수 있습니다.

kfifo의 size는 항상 2의 제곱 단위로 할당 하여야 합니다.

2. kfifo에 데이터 넣기 (EnQueue)

__kfifo_init 정의

3. kfifo에서 데이터 빼기 (DeQueue)

__kfifo_init 정의

4. 기타 Macro와 함수들

버퍼의  전체 크기를 알기위한 kfifo_size()

버퍼의 현재 사용한 크기를 알기위한 kfifo_len()

버퍼의 남은 크기를 알기위한 kfifo_avail()

등과같이 kfifo를 쉽게 사용할 수 있도록 많은 Macro와 함수들이 있습니다.

아래는 대표적인 것들을 정리해 보았습니다.

다양한 Macro와 함수들

예제를 통하여 결과를 확인해보도록 하겠습니다.

Kernel Module 제작

결과 확인

위에 예제는 Queue 1024 Byte를 할당하여 

0~9까지 int 10개를 EnQueue와 DeQueue를 하는 예제입니다.

RB_TREE(Red Black Tree)

Kernel에서 가장 많이 사용하는 탐색방법인 Red Black Tree에 대해서 알아보도록 하겠습니다.

우선 Red Black Tree에 대해서 간단히 소개하도록 하겠습니다.

이진트리는 비교적 빠른 속도를 보장하는 탐색방법입니다. 

하지만 일반적인 이진트리는 최적의 경우 O(logN)의 속도를 보장해 주지만 Node가 한쪽으로 쏠리게 되는 최악의 경우 O(N)의 성능이 되어 버립니다.

알고리즘에서는 최악의 조건까지 고려해야 합니다. 그래서 나온것들이 균형 이진 트리입니다.

이 균형이진 트리에는 AVL Tree, Red Black Tree와 같은 것들이 있습니다. AVLTree보다 Red Black Tree가 더 좋은 성능을 보이기 때무니에 Red Black Tree가 Kernel에서 많이 사용되고 있습니다.

Red Black Tree는 최악의 조건에서도 O(logN)의 성능을 보여 줄수 있습니다.

Red Black Tree의 자세한 설명은 학교 수업시간에 공부를 하셨을 것이라고 생각하고! Kernel에서 제공하는 함수들을 이용하여 구현을 해보도록 하겠습니다.

Red Black Tree는 <linux/rbtree.h>에 정의가 되어 있으며 "lib/rbtree.c"에 구현되어 있습니다. 

Red Black Tree에 관해 모든것이 구현되어 있다면 사용이 매우 제한적을 것입니다. 이러한 제한적인 것을 없애기 위해서 자신의 Data를 넣을 수 있는 Node를 만들고 이 Node안에 rb_node를 통해 연결이 되어있습니다.

이전 시간에 했던 List와 비슷한 구조를 보이고 있습니다.

Red Black Tree 구조

가장 중요한 점은!!

검색이나 삽입 기능은 사용자가 직접 구현하여야 합니다.

복잡할 것이라 생각이 되지만!! Kernel에서 구현을 위한 기본 함수와 Macro들은 제공하고 있습니다.

차곡차곡 Red Black Tree에 대해 살펴보도록 하겠습니다.

Kernel에서는 rb_node와 rb_root 구조체를 가지고 있습니다.

rb_node 구조체

rb_root 구조체

rb_node 구조체를 보면 부모에 대한 정보, 색, 자식 노드에 대한 정보를 가지고 있으며

rb_root 구조체는 root인 rb_node의 주소만 가지고 있습니다.

이러한 구조체를 이용하여 kernel에서 어떠한 함수와 Macro들이 있는지 살펴보겠습니다.

Kernel에서 제공하는 Red Black Tree 관련 함수와 Macro

Macro와 함수를 통해서 부모에 관한 정보, 색에 관한 정보, 전체 Node에 관한 정보들을 뽑을 수있도록 제공해 주고 있습니다. 

검색과 삽입에 관한 기능들은 직접 구현해야 되기 때문에 예제를 통해 Red Black Tree를 설명 하도록 하겠습니다.

Kernel Module 제작

결과 확인

예제는 10~90의 숫자를 삽입하며 Tree의 모양을 출력해보는 것입니다.

위의 결과와 같이 균형을 잘 맞추며 노드가 삽입 된것을 볼 수 있습니다.

예제 소스에 대해 설명을 하자면

전체 노드에 대한 구조체 Type_node가 rb_node 구조체와 Data에 해당하는 num을 가지고 있습니다.

그리고 rb_root 구조체는 RB_ROOT Macro에 의해 초기화를 하였습니다.

rbnode_search()는 Red Black Tree에서 검색을 위한 함수를 구현한것이고

rb_entry의 경우 Type_node의 주소를 알아내기 위한 Macro 입니다 rb_entry는 'container of' Macro를 호출하게 되는데 'container of'는 지난번 List에서 다루었으니 패스 하겠습니다.

rbnode_insert()는 Red Black Tree에서 삽입을 위한 함수 입니다.

rb_link_node()는 node들 간의 연결을 해주기 위한 함수이며

rb_insert_color()함수가 중요합니다!! 이 함수에서 삽입후 Tree의 reblance를 해주는 함수 입니다.

create_rbnode()는 Type_node를 생성해주는 함수를 직접 구현 하였습니다.

rb_print()함수는 원래는 필요 하지 않지만 Red Black Tree가 잘 구현이 되었는지 출력해 보기 위해 제작을 하였습니다. 

---

이번 포스팅에서는 Linux Kernel에서 제공하는 Data Structure인 kfifo와 Red Black Tree를 사용하는 방법에 대해 알아 보았습니다.

조금더 심도있게 공부하고자 하시는 분은 Linux Kernel 소스에 있는 자료들을 참고하시면 좋습니다.

Linux Kernel은 Documentation이 매우 잘되어 있어 공부하고자 하시는 분은 Kernel 소스의 Documentation 폴더와 sample 폴더의 자료를 공부하시면 많은 도움이 될것이라 생각 됩니다.