5/31 Kernel Linked List

JK·2023년 5월 31일

Kernel Linked List

리눅스 커널에서 취급하는 대부분의 자료형은 연결 리스트(linked list) 로 연결되어 사용됩니다. 리눅스 커널의 연결 리스트는 그 구현이 매우 간단하다. 오직 양방향으로 연결된 prev 포인터와 next 포인터만으로 모든 것을 표현합니다.

연결 리스트 구조

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

next: 다음 노드를 가리키는 포인터입니다. 연결 리스트의 노드들은 순차적으로 연결되어 있으므로, next 포인터를 통해 다음 노드로 이동할 수 있습니다. 마지막 노드의 next 포인터는 첫 번째 노드를 가리키도록 구성됩니다.
prev: 이전 노드를 가리키는 포인터입니다. 이중 연결 리스트의 경우에만 사용되며, 각 노드는 이전 노드를 가리키는 포인터를 가지고 있습니다

struct list_head를 사용하여 데이터 구조를 연결 리스트로 구성할 수 있습니다. 예를 들어, 다음과 같은 구조체를 연결 리스트의 노드로 사용할 수 있습니다

struct my_struct {
    int data;
    struct list_head list;
};

이 경우, struct my_struct는 연결 리스트의 각 노드를 나타내며, data 필드는 해당 노드에 저장되는 데이터를 나타냅니다. list 필드는 struct list_head 구조체를 포함하고 있으며, 이를 통해 노드들을 연결합니다.

리눅스 커널에서는 struct list_head를 다루기 위한 다양한 함수들을 제공합니다. 이러한 함수들을 사용하여 연결 리스트의 노드를 추가, 삭제, 탐색하는 등의 작업을 수행할 수 있습니다. 몇 가지 주요한 함수들은 다음과 같습니다

연결 리스트의 함수

INIT_LIST_HEAD(struct list_head *head)
struct list_head를 초기화하는 함수로, 연결 리스트의 헤드를 초기화합니다.
list_add(struct list_head new, struct list_head head)
새로운 노드를 연결 리스트의 특정 위치에 추가합니다.
list_del(struct list_head *entry)
특정 노드를 연결 리스트에서 삭제합니다.
list_for_each(struct list_head pos, struct list_head head)
연결 리스트를 순회하면서 각 노드에 대한 작업을 수행합니다
list_empty(const struct list_head *head): 연결 리스트가 비어있는지 확인하는 함수입니다. 만약 head 포인터가 가리키는 연결 리스트가 비어있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.
list_entry(const struct list_head *ptr, const type, member): struct list_head를 포함하는 구조체의 주소를 계산하는 매크로입니다. ptr 포인터가 가리키는 struct list_head의 주소에서 type 구조체의 member 필드의 오프셋을 빼면 type 구조체의 주소를 얻을 수 있습니다.
list_for_each(struct list_head pos, const struct list_head head): 연결 리스트를 순회하면서 각 노드에 대한 작업을 수행하는 매크로입니다. pos 포인터를 사용하여 각 노드에 접근할 수 있습니다.
list_for_each_safe(struct list_head pos, struct list_head n, const struct list_head *head): 연결 리스트를 순회하면서 안전한 방식으로 각 노드에 대한 작업을 수행하는 매크로입니다. 삭제 작업을 수행하면서도 올바른 순회를 보장합니다.

이와 같은 함수들을 사용하여 연결 리스트를 효율적으로 관리할 수 있습니다. 또한, 연결 리스트를 사용하는 모듈에서는 자체적으로 필요한 연결 리스트 관련 함수들을 정의할 수도 있습니다

초기화

struct my_data {
    int value;
    struct list_head list;
};

int main() {
    // 연결 리스트 헤드 초기화
    LIST_HEAD(my_list);
    ...
}

my_data라는 구조체를 정의합니다. 이 구조체는 연결 리스트에 저장될 데이터를 나타냅니다. value는 데이터의 값이고, list는 연결 리스트에서 사용될 링크를 나타냅니다.

LIST_HEAD(my_list)는 연결 리스트의 헤드를 초기화하는 매크로입니다. my_list라는 이름의 연결 리스트를 생성하고 초기화합니다.

데이터 삽입

struct my_data *temp = NULL;
unsigned int i;

INIT_LIST_HEAD(&my_list.list);

for (i = 0; i < 5; i++) {
    temp = (struct my_data *) kmalloc(sizeof(struct my_data), GFP_KERNEL);
    temp->value = i;
    printk("Data insertion: add to list [%d]\n", temp->value);

    list_add(&temp->list, &my_list.list);
}

위의 코드는 0부터 4까지의 값을 가지는 my_data 구조체 타입의 노드를 동적으로 생성하여 연결 리스트에 삽입하는 과정을 반복합니다. 각 데이터의 value 값을 출력하여 삽입 과정을 확인할 수 있습니다

데이터 순회

struct my_data *current;
list_for_each_entry(current, &my_list, list) {
    printf("Value: %d\n", current->value);
}

list_for_each_entry 매크로를 사용하여 연결 리스트를 순회합니다. current라는 포인터를 선언하고, &my_list는 순회할 연결 리스트의 헤드를 전달합니다. current 포인터는 각 노드에 대한 작업을 수행하는 데 사용됩니다.

위의 예시에서는 각 데이터의 value 값을 출력하고 있습니다. current->value로 현재 노드의 데이터에 접근할 수 있습니다.

순회가 끝나면 모든 데이터를 출력한 후에는 메모리를 해제하는 과정을 추가하여 할당된 메모리를 해제할 수 있습니다

데이터 삭제

struct my_data *temp = NULL;
struct list_head *pos = NULL;
struct list_head *q = NULL;
unsigned int i = 0;

list_for_each_safe(pos, q, &my_list.list) {
    temp = list_entry(pos, struct my_data, list);
    printk("Data traversal: free pos[%d] => value=%d", i, temp->value);
    list_del(pos);
    kfree(temp);

    i++;
}

위의 코드는 연결 리스트를 순회하면서 각 데이터를 삭제하는 과정을 반복합니다. 순회 중인 데이터의 값과 해당 노드의 위치를 출력하고, 해당 노드를 삭제하고 데이터를 해제합니다.

이를 통해 연결 리스트의 데이터를 순회하고 삭제할 수 있습니다

이전에 Red Black Tree에 관해 공부할 때 링크드 리스트에 관해 공부 했었는데, PintOS에 관해 공부하다가 리눅스 커널의 연결리스트를 조금 더 공부해야겠다는 생각이 들어서 한 번 더 공부해봤습니다