[Linux Kernel 5] Linked List

리눅스 커널은 다양한 자료구조들을 일반적으로 사용할 수 있도록 제공한다.

연결 리스트, 큐, RB 트리, B+ 트리 등을 템플릿이나 제너릭 타입이 아닌 무려 포인터를 이용하여 일반화한다.

이번 포스트에서는 어떻게 포인터로 일반적인 자료구조를 구현하는지와 커널에서 제공하는 연결 리스트를 알아본다.

 

 

 

1. 매직 매크로

 

커널에서는 다양한 마법같은 매크로들을 제공한다.

이들을 통칭하여 매직 매크로라고 부르지는 않는다.

그냥 되게 유용하고 신기한 매크로들을 소개하려는데 마땅한 부제가 생각나지 않아서 매직 매크로라고 칭했다.

그 중 자료 구조들을 구현하는데 있어 중요한 두 매크로를 먼저 알아보도록 한다.

 

#ifdef __compiler_offsetof
#define offsetof(TYPE, MEMBER)	__compiler_offsetof(TYPE, MEMBER)
#else
#define offsetof(TYPE, MEMBER)	((size_t)&((TYPE *)0)->MEMBER)
#endif
 
/**
 * container_of - cast a member of a structure out to the containing structure
 * @ptr:	the pointer to the member.
 * @type:	the type of the container struct this is embedded in.
 * @member:	the name of the member within the struct.
 *
 */
#define container_of(ptr, type, member) ({				\
	void *__mptr = (void *)(ptr);					\
	BUILD_BUG_ON_MSG(!__same_type(*(ptr), ((type *)0)->member) &&	\
			 !__same_type(*(ptr), void),			\
			 "pointer type mismatch in container_of()");	\
	((type *)(__mptr - offsetof(type, member))); })
 

offsetof와 container_of 매크로인데 처음보면 대체 이게 뭔가 싶을거다.

 

우선 offsetof는 다음과 같이 사용한다.

struct T {
	int a;
	int b;
};
 
size_t offset = offsetof(struct T, b);

TYPE에 구조체 타입을 적고, MEMBER에 오프셋을 구하고 싶은 멤버의 이름을 적으면 구조체 내에서의 멤버의 오프셋 값을 반환해준다.

즉, 위의 경우엔 struct T와 그 멤버 b의 주소 값 차이를 구한다. 따라서 int가 4 byte인 시스템에서 위의 값은 4이다.

위 코드의 매크로를 직접 나열해보면 다음과 같다.

size_t offset = ((size_t)&((struct T *)0)->b);

0을 포인터형으로 캐스팅하여 구조체 멤버 접근(dereference)을 하는게 너무 생소할 것이다.

0 대신 struct T t; 의 주소인 &t를 대입해보자.

t의 주소를 struct T 형으로 해석하여 멤버 b에 접근하고, 이 b의 주소값을 계산하여 size_t 형으로 캐스팅한다.

즉, 복잡해보여도 간단히하면 &t.b의 값을 size_t로 캐스팅한 것이다.

만약 &t가 100이었다면, &t.a는 100이고 &t.b는 104이다.

그렇다면 여기서 t의 주소를 0이라고 해보자.

&t.a는 0이고 &t.b는 4이다. 마법같이 멤버의 주소 오프셋이 나온다.

offsetof는 이렇게 0을 TYPE *형으로 캐스팅하여 멤버의 주소 오프셋을 구하는 매크로이다.

 

그렇다면 반대로 offsetof 매크로를 이용하여 멤버로부터 구조체의 주소를 구해보자.

struct T *p = (struct T *)((char *)&t.b - offsetof(struct T, b));

t.b의 주소에서 멤버 b의 오프셋을 빼면 t의 주소값이 나온다.

char *형으로 캐스팅한건 포인터 빼기 연산 상 오차를 없애기 위해서다.

(int *p = 100; 에서 p - 1은 99가 아닌 96이기 때문이다.)

 

다음으로 container_of 매크로는 위의 멤버로부터 구조체를 구하는 매크로로, 다음처럼 사용한다.

struct T *p = container_of(&t.b, struct T, b);

ptr에는 멤버의 포인터를, type에는 구조체 타입을, member에는 구조체의 해당 멤버 이름을 넣어준다.

복잡해 보이는 container_of의 내용도 결국 위의 예를 대입하고 디버깅용 코드를 빼서 풀면 다음과 같다.

struct T *p;
void *__mptr = (void *)&t.b;
p = (struct T*)(__mptr - offsetof(struct T, b));

이미 위에서 보인 offsetof 매크로를 이용하여 멤버로부터 구조체의 주소를 구하는 것과 다름이 없다.

 

그 외에도 커널에는 다음과 같은 매크로들이 수없이 존재한다.

우선은 연결 리스트를 구현하는데 중요했던 위 두 매크로를 학습하고 넘어간다.

 

 

 

2. 연결 리스트 인터페이스

 

커널이 제공하는 연결 리스트는 다중 환형 연결 리스트다.

엔트리 간 next와 prev를 모두 접근할 수 있으며, tail node의 next는 head로 돌아온다.

 

이 리스트를 사용하기 위해서는 linux/list.h 파일을 삽입해야한다.

https://github.com/torvalds/linux/blob/master/include/linux/list.h

torvalds/linux

해당 파일을 보면 다양한 인터페이스를 제공하는걸 볼 수 있다.

 

이 중 대표적으로 초기화, 엔트리 추가, 엔트리 제거, 엔트리 순환 인터페이스를 알아보자.

 

우선 초기화는 다음과 같이 한다.

struct T {
	int a;
	int b;
	struct list_head list;
};
 
LIST_HEAD(my_list);

연결 리스트로 만들고 싶은 구조체의 멤버에 struct list_head를 추가하고,

LIST_HEAD(name); 으로 리스트를 선언 및 초기화한다. (해당 매크로가 리스트의 선언문까지 포함한다.)

 

그리고 list_add(struct list_head *new, struct list_head *head)로 다음과 같이 엔트리를 추가한다.

list_add(&t1.list, &my_list);
list_add(&t2.list, &my_list);

이러면 리스트에 t1과 t2가 추가된 것이다. (물론 t1과 t2는 따로 선언해야 한다.)

 

제거 시에는 list_del(struct list_head *entry)를 다음과 같이 사용한다.

list_del(&t1.list);

이러면 리스트에서 t1이 제거된 것이다.

 

리스트의 실제 엔트리를 구하고 싶으면 list_entry 매크로를 다음과 같이 사용한다.

struct T *p1 = list_entry(&my_list->next, struct T, list);
struct T *p2 = list_entry(&p1->list.next, struct T, list);

 

리스트 내의 엔트리를 순환(iterate)하고 싶다면 list_for_each_entry(pos, head, member) 매크로를 다음과 같이 사용한다.

struct T *p;
list_for_each_entry(p, &my_list, list) {
	printk("%d %d\n", p->a, p->b);
}

list_add로 엔트리를 추가하고 위와 같이 head의 next부터 엔트리를 구하면 LIFO 형식으로 엔트리를 다루게 된다.

 

이 외 tail add, replace, swap, cut, splice나 reverse iterate, safe interate 등의 인터페이스가 있으니 위 list 헤더 파일을 참고하기 바란다.

 

 

 

3. 연결 리스트 구현

 

커널이 어떻게 연결 리스트를 구현했는지 알아보자.

우선 리스트의 head와 초기화 매크로는 다음과 같이 구현되어있다.

struct list_head {
	struct list_head *next, *prev;
};
 
#define LIST_HEAD_INIT(name) { &(name), &(name) }
 
#define LIST_HEAD(name) \
	struct list_head name = LIST_HEAD_INIT(name)
 

구조체 list_head는 struct list_head *로 next와 prev를 정의하여 양방향 탐색을 지원한다.

LIST_HEAD 매크로는 list_head 구조체를 선언하고, next와 prev를 자기 자신으로 초기화한다.

 

그러면 이제 리스트로 만들고 싶은 구조체의 멤버로 struct list_head를 추가하면 next와 prev를 이용하여 해당 구조체를 리스트로 관리할 수 있다.

즉, 리스트 자체는 구조체의 멤버인 list_head로 관리하고, 실제 엔트리는 위에서 공부한 list_entry로 접근하는 것이다.

/**
 * list_entry - get the struct for this entry
 * @ptr:	the &struct list_head pointer.
 * @type:	the type of the struct this is embedded in.
 * @member:	the name of the list_head within the struct.
 */
#define list_entry(ptr, type, member) \
	container_of(ptr, type, member)

list_entry는 1번에서 공부한 container_of의 래퍼이다.

container_of 매크로는 멤버의 포인터를 이용해서 해당 멤버를 포함하고 있는 구조체의 포인터를 구했다.

즉, 멤버인 struct list_head의 포인터로 list_head를 포함하고 있는 구조체 엔트리의 포인터를 구하는 것이다.

 

list_add와 list_del의 구현은 다음과 같이 일반적인 연결 리스트 자료구조 구현과 다름이 없다.

/*
 * Insert a new entry between two known consecutive entries.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
static inline void __list_add(struct list_head *new,
			      struct list_head *prev,
			      struct list_head *next)
{
	if (!__list_add_valid(new, prev, next))
		return;
 
	next->prev = new;
	new->next = next;
	new->prev = prev;
	WRITE_ONCE(prev->next, new);
}
 
/**
 * list_add - add a new entry
 * @new: new entry to be added
 * @head: list head to add it after
 *
 * Insert a new entry after the specified head.
 * This is good for implementing stacks.
 */
static inline void list_add(struct list_head *new, struct list_head *head)
{
	__list_add(new, head, head->next);
}
 
 
/**
 * list_add_tail - add a new entry
 * @new: new entry to be added
 * @head: list head to add it before
 *
 * Insert a new entry before the specified head.
 * This is useful for implementing queues.
 */
static inline void list_add_tail(struct list_head *new, struct list_head *head)
{
	__list_add(new, head->prev, head);
}
 
/*
 * Delete a list entry by making the prev/next entries
 * point to each other.
 *
 * This is only for internal list manipulation where we know
 * the prev/next entries already!
 */
static inline void __list_del(struct list_head * prev, struct list_head * next)
{
	next->prev = prev;
	WRITE_ONCE(prev->next, next);
}
 
/*
 * Delete a list entry and clear the 'prev' pointer.
 *
 * This is a special-purpose list clearing method used in the networking code
 * for lists allocated as per-cpu, where we don't want to incur the extra
 * WRITE_ONCE() overhead of a regular list_del_init(). The code that uses this
 * needs to check the node 'prev' pointer instead of calling list_empty().
 */
static inline void __list_del_clearprev(struct list_head *entry)
{
	__list_del(entry->prev, entry->next);
	entry->prev = NULL;
}
 
static inline void __list_del_entry(struct list_head *entry)
{
	if (!__list_del_entry_valid(entry))
		return;
 
	__list_del(entry->prev, entry->next);
}
 
/**
 * list_del - deletes entry from list.
 * @entry: the element to delete from the list.
 * Note: list_empty() on entry does not return true after this, the entry is
 * in an undefined state.
 */
static inline void list_del(struct list_head *entry)
{
	__list_del_entry(entry);
	entry->next = LIST_POISON1;
	entry->prev = LIST_POISON2;
}

 

연결 리스트를 위와 같이 직접 구현하여 유저 프로세스 예제를 작성해보면 좋은 공부가 될 것이다.

 

 

 

4. 리스트 모듈 예제 소스

 

#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/list.h>
 
struct item {
	int number;
	struct list_head list;
};
 
// declare list
LIST_HEAD(my_list);
 
static struct item item1, item2, item3;
 
static int __init list_init(void)
{
	struct item *cur;
 
	item1.number = 10;
	item2.number = 20;
	item3.number = 30;
 
	INIT_LIST_HEAD(&my_list);
 
	list_add(&item1.list, &my_list);
	list_add(&item2.list, &my_list);
	list_add_tail(&item3.list, &my_list);
	// head -> 20 -> 10 -> 30
 
	printk("=========== First Phase ==========\n");
	list_for_each_entry(cur, &my_list, list) {
		printk("%d ", cur->number);
	}
	printk("\n");
 
	list_del(&item1.list);
	// head -> 20 -> 30
 
	printk("=========== Second Phase ==========\n");
	list_for_each_entry(cur, &my_list, list) {
		printk("%d ", cur->number);
	}
	printk("\n");
 
	return 0;
}
 
static void __exit list_exit(void)
{
	list_del_init(&my_list);
}
 
module_init(list_init);
module_exit(list_exit);
MODULE_LICENSE("GPL");

 

 

 

5. 실행 결과

 

dmesg 결과

정상 작동하는 것을 볼 수 있다.

 

 

이 전 proc 포스트 예제에서 리스트를 먼저 사용했었다.

이 후 메모리 관리 포스트에서 리스트를 자주 사용하고 보게 될 것이라 이번에 다뤄보았다.

사실 리눅스 커널 소스에서 연결 리스트는 눈 한번 감았다가 뜨면 볼 정도로 흔하기 때문에,

커널 공부를 하려면 굉장히 잘 숙지하고 있어야 한다.