1. Linked List

리눅스 커널은 리스트를 연결하는 포인터와 노드에 저장되는 데이터를 분리하는 독특한 구현 방식을 적용하여 Circular Linked List를 제공한다. 링크드 리스트의 공식 구현은 v2.1 커널 개발에서 도입되었다.

1.1. struct list_head

링크드 리스트의 각 노드는 v6.4.6 kernel 기준 /include/kernel/types.h에 정의된 list_head를 이용하여 다음 혹은 이전 노드를 가리킨다. 따라서 Doubly Circular Linked List로 이해해도 좋다.

따라서 fox라는 노드를 연결하는 링크드 리스트를 생성하기 위해서, fox에 list_head 필드를 추가하여 노드들이 서로 연결되도록 구현한다.

1.2. Initialization

1.2.1. Dynamic Allocation

위 코드는 kmalloc()을 이용해 노드를 동적 생성할 경우를 보인다. 이때 list_head 필드는 INIT_LIST_HEAD() 함수를 사용해 초기화한다.

1.2.2. Static Allocation

위 코드는 노드를 정적 생성하는 코드이다. 이때 LIST_HEAD_INIT 매크로가 사용되는데, 역할은 INIT_LIST_HEAD()함수와 동일하다.

1.3. List Head

리스트 헤드는 링크드 리스트의 시작 노드를 가리키는 포인터로 사용된다. 이 포인터의 타입 또한 struct list_head이고, LIST_HEAD 매크로를 이용하여 생성한다.

1.4. List Node

리스트를 구성하는 노드 구조체 내에는 struct list_head field가 존재하여 이것의 내부 포인터 prev, next가 주변 노드들의 내부에 있는 list_head를 가리킨다. 따라서 노드의 데이터에 접근하기 전에 먼저 그 노드의 list_head에 접근하게 되므로, 접근한 list_head를 field로 갖고 있는 노드에 접근해야만 노드의 데이터에 접근할 수 있다.

container_of 매크로는 member가 이름인 field를 갖고, 그 field가 ptr을 가리키는 type자료형의 구조체를 찾아 그 구조체의 포인터를 반환한다. 이 구현은 구조체 내 특정 field의 offset이 ABI 수준에서 고정됨을 이용한 것이다. 이 매크로를 호출하는 list_entry 매크로를 이용하여 특정 list_head 구조체를 field로 갖는 리스트 노드를 찾을 수 있다.

1.5. List Manipulation

링크드 리스트를 조작하는 함수는 모두 /include/linux/list.h에 인라인 함수로 정의되어 있으며, 인자로 struct list_head를 받는다. 시간복잡도는 O(1)이다.

1.5.1. list_add(), list_add_tail()

/include/linux/list.h에 구현되어 있는 list_add()함수는 head노드 다음에 new 노드를 추가한다.

반대로 list_add_tail()함수는 head노드 이전에 new 노드를 추가한다.

list_add(), list_add_tail() 모두 내부적으로 __list_add를 호출한다. 위 함수는 prev와 next 노드 사이에 new노드를 추가한다.
이전에 호출되는 __list_add_valid() 함수는 디버깅 용도로 사용되는데, build config에서 CONFIG_DEBUG_LIST가 비활성화되어 있다면 항상 true를 반환한다.

1.5.2 list_del(), list_del_init()

리스트에서 노드를 제거할 때는 list_del() 함수를 사용한다. 이 함수는 entry 노드를 포함된 리스트에서 제거한다. 그러나 해당 함수는 노드를 리스트에서 제거하는 동작만 수행할 뿐, 메모리를 해제하지 않는다.

해당 함수는 내부적으로 __list_del_entry()->__list_del()을 호출하는데, 이때 인자로 entry 노드의 prev와 next를 넘긴다. 이 두 노드를 받은 __list_del()함수는 prev와 next를 연결하는 동작을 수행한다.

만약 리스트에서 entry 노드를 제거하고 재사용이 필요한 경우, list_del_init()함수를 사용한다. 이 함수는 entry 노드를 리스트에서 제거할 뿐만 아니라 노드의 초기화 작업도 진행한다.

1.5.3. list_move(), list_move_tail()

list_move()함수는 list 노드를 리스트에서 제거한 후, head노드 다음에 list 노드를 추가한다.

list_move_tail()함수는 마찬가지로 특정 리스트에서 list노드를 제거한 후, head 노드의 앞에 list노드를 추가한다.

1.5.4. list_empty()

list_empty() 함수는 head가 연결된 리스트가 비어 있는지 확인한 후 참이면 true를 반환한다. 확인 방식은 해당 리스트에서 head, 즉 리스트 헤드만 존재하는지를 확인한다.

1.5.5. list_splice(), list_splice_init()

list_splice()함수는 list노드가 연결된 리스트를 head와 연결된 리스트와 연결하는 함수이다.

list_splice()는 list노드가 연결된 링크드 리스트가 비어있지 않다면 __list_splice()를 호출한다. 이 함수는 list의 prev, next노드를 head, head->next노드에 연결한다.

list_splice_init()함수는 두 링크드 리스트를 병합할 뿐만 아니라, 병합 대상인 list 노드를 초기화한다.

이러한 함수들을 호출할 때, list의 prev, next 노드를 알고 있다면 __으로 시작하는 내부 함수를 직접 호출하는 것이 CPU cycle을 절약할 수 있다.

1.6. Traverse

리스트를 조작하는 함수의 시간 복잡도는 O(1)이지만, n개의 노드가 있는 리스트를 탐색하는 함수의 시간 복잡도는 O(n)이다.

1.6.1. list_for_arch(), list_for_each_entry(), list_for_each_entry_reverse()

list_for_each 매크로는 첫 번째 인자로 해당 매크로 함수의 호출자가 사용하는 임시 변수를, 두 번째 인자는 리스트 헤드를 전달받는다. 그리고 임시 변수가 circular list를 한 바퀴 돌아 리스트 헤드에 도달할 때까지 리스트의 각 노드들을 순회한다.

반복의 조건에서 사용되는 list_is_head()함수는 단순히 list노드가 head노드와 동일한지 확인한다.

위 코드에서 p는 struct list_head이므로, 데이터가 담긴 노드에 접근하기 위해서는 list_entry 매크로를 사용한다.

커널에서는 깔끔한 코드를 지향하므로 list_for_each_entry 매크로를 주로 사용한다. 이 매크로는 내부적으로 list_entry 매크로와 동일한 역할을 하는 list_first_entry, list_next_entry매크로를 사용하여, 바로 list_head를 포함하는 노드 포인터를 얻을 수 있다.
인자로 전달받는 pos는 list_head를 포함하는 노드 포인터, head는 리스트 헤드, member는 노드 내에 정의된 list_head field의 이름이다.

list_for_each_entry를 이용하여 위와 같이 코드를 재작성할 수 있다.

list_for_each_entry_reverse 매크로는 역방향으로 순회한다는 점만 제외하고 list_for_each_entry와 동일하다.

1.6.2. list_for_each_entry_safe(), list_for_each_entry_safe_reverse()

list_for_each_entry_safe매크로는 리스트를 탐색할 때 노드를 리스트에서 제거하는 동작이 가능하도록 한다. 새롭게 추가된 인자는 n으로, pos의 다음 노드를 저장한다. 기존의 list_for_each_entry에서 pos를 제거하면, 다음 노드를 탐색하기 위해 제거된 pos에 다시 접근하므로 버그가 발생한다. 그러나 다음 노드를 저장하는 n 변수가 존재하여 이 문제를 해결할 수 있다.

list_for_each_entry_safe_reverse 매크로는 역방향으로 순회한다는 점만 제외하고 list_for_each_entry_safe와 동일하다.

2. Queue (kfifo)

커널은 kfifo라는 이름으로 queue 자료구조를 구현하였고, enqueue와 dequeue 두 가지 기능을 제공한다. /include/linux/kfifo.h에 정의되어 있다.

kfifo 객체는 두 가지 offset 정보를 갖고 있는데, 다음에 enqueue될 위치를 저장하는 in offset과, 다음에 dequeue될 위치를 저장하는 out offset이 있다. 두 offset은 각각 enqueue하거나 dequeue한 만큼의 값이 더해진다.

2.1. Initialization

kfifo를 사용하기 전에 먼저 동적 또는 정적으로 kfifo를 생성하고 초기화해야 한다. 주로 동적 할당하여 사용하며, 이 작업을 진행하는 매크로는 kfifo_alloc이다.

이 매크로는 내부적으로 __kfifo_alloc()함수를 호출하는데, 해당 함수 내에서 동적 할당을 진행한다.

만약 직접 버퍼를 할당하여 사용하고 싶다면 kfifo_init 매크로를 사용하도록 한다.

이 매크로도 마찬가지로 내부 함수 __kfifo_init()을 호출하는데, kfifo의 data field를 buffer로 설정한다.

2.2. Enqueue

kfifo에 데이터를 넣으려면 kfifo_in 매크로 함수를 호출하면 된다. 이 함수는 buf가 가리키는 위치에서 n만큼의 데이터를 enqueue하고, enqueue한 바이트 수를 반환한다. 이때 kfifo의 빈 공간이 n보다 작으면 반환 값은 n보다 작거나 0이 될 수도 있다.

2.3. Dequeue

kfifo에 데이터를 빼려면 kfifo_out 매크로 함수를 호출한다. 이 함수는 buf가 가리키는 위치에서 n의 데이터를 dequeue하고, dequeue한 바이트 수를 반환한다. 이때 kfifo에 있는 데이터 크기가 n보다 작으면 반환 값 또한 n보다 작거나 0이 된다.

2.4. Get Size

kfifo_size 매크로는 kfifo에 데이터를 저장하기 위해 사용되는 버퍼의 크기를 반환한다.

kfifo_len매크로는 kfifo에 넣은 데이터의 바이트 수를 계산한다.

kfifo_avail은 kfifo의 여분 공간의 크기를 반환한다.

kfifo_is_empty, kfifo_is_full은 kfifo가 비어있는지, 또는 차 있는지 확인하는 매크로이다.

2.5. Reset & Destroy

kfifo 내에 저장된 데이터를 지우고 초기화하기 위해서는 kfifo_reset 매크로 함수를 사용한다.

kfifo_alloc으로 할당된 kfifo를 삭제하기 위해서는 kfifo_free 매크로 함수를 사용한다. 다만 kfifo_init으로 버퍼를 직접 할당했을 경우, 할당된 버퍼는 따로 할당 해제해야 한다.

4. Red-Black Tree (rbtree)

rbtree는 리눅스에서 사용하는 자료구조로, 최적화까지 구현한 red-black tree이다. 루트 노드는 struct rb_root를, 나머지 노드들은 struct rb_node로 정의된다.

한편 트리에서 가장 작은 값의 노드를 찾기 위해, 캐시를 사용하는 트리의 루트 노드인 rb_root_cache도 정의한다.

Red-Black Tree: https://code-lab1.tistory.com/62

4.1. Tree Initialization

트리를 새로 생성하기 위해, 먼저 루트 노드인 rb_root를 새로 할당한 후 RB_ROOT 매크로로 초기화한다.

rb_root_cached의 초기화를 위한 매크로도 존재한다.

4.2. Searching

rbtree에서는 탐색, 삽입 기능을 제공하지 않고, 이 자료구조를 활용하는 개발자가 직접 구현해야 한다. 먼저 탐색의 구현은 이진 탐색 트리와 동일하다.

4.3. Insertion

삽입도 탐색과 마찬가지로 개발자가 직접 구현해야 한다.

먼저 추가하고자 하는 데이터의 키 값을 루트 노드부터 비교하여 새로 추가될 노드의 자리를 찾는다. 그리고 필요한 경우 recoloring을 한다. 위 코드에서 rb_link_node()함수는 인자로 넘겨진 위치에 노드를 추가하고, rb_insert_color()는 트리 균형을 맞추는 함수이다.