[리눅스 커널] 커널 자료구조

reference : 리눅스 커널 심층 분석, 로버트 러브 지음, 황정동 옮김
6장 커널 자료구조

1. 연결 리스트
연결 리스트는 노드라고 부르는 가변적인 개수의 데이터를 저장하고 관리하는 기능을 제공한다. 정적 배열과 달리 연결 리스트는 동적으로 데이터를 새엇ㅇ해 리스트에 추가할 수 있다. 그러므로 컴파일 시점에 미리 개수를 알 수 없는 데이터를 관리할 수 있다. 데이터가 한꺼번에 동시에 만들어지지 않으므로, 이 데이터는 인접한 메모리 공간에 모여 있지 않을 수 있다.따라서 데이터를 서로 연결시키는 방법이 있어야 하므로 리스트의 각 데이터에는 다음 데이터의 위치를 가리키는 next 포인터가 들어 있다. 리스트에 데이터를 추가하거나 삭제할 때는 다음 노드를 가리키는 포인터를 조정하면 된다.

단일 연결리스트와 이중 연결 리스트

연결 리스트를 나타내는 가장 단순한 자료구조의 형태는 다음과 같다.

/* 연결 리스트의 데이터 항목 */
struct list_element {
    void *data;                     /* 항목에 담긴 데이터(payload) */
    struct list_element *next; /* 다음 항목을 가리키는 포인터 */
};

이중 연결 리스트를 나타내는 자료구조의 형태는 다음과 같다.

/* 연결 리스트의 데이터 항목 */
struct list_element {
    void *data;                     /* 항목에 담긴 데이터(payload) */
    struct list_element *next; /* 다음 항목을 가리키는 포인터 */
    struct list_element *prev; /* 이전 항목을 가리키는 포인터 */
};

리눅스 커널의 연결 리스트는 독특한 방식으로 구현되지만, 본질적으로는 환형 이중 연결 리스트라고 할 수 있다. 이런 연결 리스트 형식을 사용함으로써 유연성을 최대한 확보할 수 있다.

연결 리스트 내에서 이동

연결 리스트 내의 이동은 선형으로 일어난다. 한 항목을 참조하고, 다음 포인터를 따라가 다음 항목을 참조한다. 이 과정을 반복하면 된다. 전체 리스트를 차례대로 훑는 작업이나 항목을 동적으로 삽입하고 제거하는 작업이 필요한 경웨 연결 리스트를 사용한다.
연결 리스트 구현에서 리스트의 '시작'부분에 접근하기 쉽게 리스트의 첫 번째 항목을 head라고 부르는 특별한 포인터로 표시하는 경우가 많다.


리눅스 커널의 구현 방식

연결 리스트 구조체

2.1 커널 개발 과정에서 커널의 연결 리스트 공식 구현이 도입되었다. 이제 모든 연결 리스트는 이 공식 구현 방법을 사용한다.
연결 리스트 코드는 <linux/list.h> 헤더 파일에 정의되며, 자료구조는 아래와 같이 간단하다.

struct list_head {
    struct list_head *next;
    struct list_head *prev;
};

이러한 구현 방식의 실제 유용성은 list_head 구조체의 사용법에 있다.

struct fox {
    unsigned long tail_length;    /* 꼬리의 길이(cm) */
    unsigned long weight;         /* 무게(kg) */
    bool is_fantastic;               /* 멋있는 여우인가? */
    struct list_head list;             /* fox 구조체 리스트 */
};

이렇게 하면 fox 구조체의 list.next는 다음 항목을 가리키고, list.prev는 이전 항목을 가리키게 할 수 있다. 커널은 이런 연결 리스트를 조작하는 일군의 함수를 제공한다. 예를 들어, list_add()를 사용하면 기존 연결 리스트에 새로운노드를 추가할 수 있다. 게다가 이런 함수는 범용성을 갖추고 있다. list_head 구조체만을 대상으로 처리하기 때문이다. container_of() 매크로를 사용하면 특정 변수 항목을 가지고 있는 부모 구조체를 쉽게 찾아낼 수 있다. C에서는 구조체내 특정변수의 상대적인위치(offset)가 컴파일 시점에 ABI 수준에서 고정되기 때문이다.

#define container_of(ptr, type, member) ({
    const typeof( ((type *)0)->member ) *__mptr = (ptr);
    (type *) ( (char *) __mptr - offsetof(type, member) );})

container_of() 매크로를 사용하면 list_head가 들어 있는 부모 구조체를 반환하는 함수를 간단하게 정의할 수 있다.

#define list_entry(ptr, type, member) container_of(ptr, type, member)

커널은 list_entry()를 비롯한 연결 리스트 생성, 조작 등의 관리 함수를 제공하며, 이런 함수는 list_head가 들어 있는 구조체에 상관없이 동작한다.


리스트 헤드

일반적으로 리스트 노드가 아닌 연결 리스트 자체를 가리키는 데 사용하는 특별한 포인터가 필요한 경우가 있다. 재미있게도 기본 list_head 구조체가 이 특별한 노드 역할을 할 수 있다.

static LIST_HEAD(fox_list);

이렇게 하면 fox_list라는 이름의 list_head 구조체를 초기화한다. 연결리스트와 관련된 다수의 함수는 하나 또는 두 개의 인자를 받는다. 헤드 노드 하나를 받거나 헤드 노드와 실제 리스트 노드를 받는다.


연결 리스트 조작

커널은 연결 리스트를 조작하는 일군의 함수를 제공한다. 모든 함수는 C 인라인 함수로 구현되어 있으며, <linux/list.h> 파일에 들어 있다.
이런 함수는 모두 O(1)이다. 즉 리스트나 다른 입력의 크기에 상관없이 일정한 시간 안에 실행된다.

연결 리스트에 노드 추가

연결 리스트에 노드를 추가하려면 다음 함수를 사용한다.

list_add(struct list_head *new, struct list_head *head)

이 함수는 head 노드 바로 뒤에 new 노드를 추가한다. 일반적으로 환형 리스트에는 첫 번째나 마지막 노드라는 개념이 없으므로 head에 어떤 항목을 지정해도 상관없다. '마지막' 항목을 전달한다면, 이 함수로 stack을 구현할 수 있다.
// 뒤에 추가하면서 뒤에서 빼면 스택 구현 가능
fox 리스트의 예로 돌아와서 fox_list 리스트에 새로운 struct fox를 추가해야 한다면 다음과 같이 한다.

list_add(&f->list, &fox_list);
// struct fox f; 인듯
// 연산자 우선순위 "->" > "&" 이므로 f->list 에 접근(포인터를 통해 요소 선택)하여 list의 주소(&)를 전달

연결 리스트의 마지막에 노드를 추가하려면 다음 함수를 사용한다.

list_add_tail(struct list_head *new, struct list_head *head)

이 함수는 head 노드 바로 앞에 new 노드를 추가한다. list_add()와 마찬가지로 환형 리스트이므로 head에 어떤 항목을 지정해도 상관없다. '첫 번째' 항목을 전달한다면, 이 함수로 큐를 구현할 수 있다.
// 뒤에 추가하면서 앞에서 빼면 큐 구현 가능

연결 리스트에서 노드 제거

연결 리스트에 노드를 추가하는 것 다음으로 리스트에서 노드를 제거하는 것이 가장 중요한 동작일 것이다. 연결 리스트에서 노드를 제거하려면 list_del() 함수를 사용한다.

list_del(struct list_head *entry)

이 함수는 리스트에서 entry 항목을 제거한다. 이 함수는 entry나 entry가 들어 있는 구조체가 차지하고 있던 메모리를 해제하지는 않는다. 보통 이 함수를 호출한 다음 list_head와 list_head가 들어 있는 자료구조의 메모리를 해제해야 한다.
예시

list_del(&f->list);

함수의 입력에 fox_list가 없다는 점에 주목하자. 이 함수는 특정 노드만을 입력으로 받아 해당 노드의 이전 및 다음 노드의 포인터를 조정해 해당 노드를 리스트에서 제거한다. 구현 내용을 보면 이해가 쉬울 것이다.

static inline void __list_del(struct list_head *prev, struct list_head *next)
{
    next->prev = prev;
    prev->next = next;
}

static inline void list_del(struct list_head *entry)
{
    __list_del(entry->prev, entry->next);
}

연결 리스트에서 노드를 제거하고 다시 초기화할 때를 위해 커널은 list_del_init() 함수를 제공한다.

list_del_init(struct list_head *entry)

이 함수는 주어진 list_head를 초기화한다는 점만 제외하면 list_del() 함수와 같다. 해당 항목을 리스트에서 제거해야 하지만 자료구조 자체는 재사용이 필요한 경우에 이 함수를 사용한다. ( ??? )