Linux Tutorial #19 리눅스 커널 연결 리스트 (linked list)

문연수·2021년 6월 4일
Kernellinked listlinux
1

Linux Tutorial

목록 보기
20/25

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

1. 연결 리스트 구조

리눅스 커널의 연결 리스트는 위와 같은 구조를 가진다. 앞서 말했듯이 연결 리스트 구조체는 오직 양방향을 연결하는 멤버 변수 두 개만을 가진다.

위 코드는 include/linux/types.h 코드에 정의된 연결 리스트의 구조체 정의이다. 이 코드를 보면 보통 이런 생각을 하게 된다.

연결하는건 좋은데 정작 가장 중요한 연결된 데이터 는 어디에서 구하는거지?

리눅스 커널은 교묘한(tricky) 표현식으로 이 문제에 대한 답을 내린다.

2. offsetof 와 container_of

두 가지 매크로 함수, offsetof 와 containerof 는 1절 에서 제시된 문제를 해결해줄 마법같은 도구들이다. 복잡해보이지만 잘 들여다보면 쉽게 이해 가능하다.

offsetof : 멤버 변수의 오프셋을 구한다.

offsetof 는 특정 구조체에 속한 멤버 변수의 바이트 오프셋을 구한다. 얼핏 보기엔 불가능할 것 같지만 이를 해결해줄 마법같은 표현식이 존재한다.

위 코드는 include/linux/stddef.h 에 정의되어 있는 offsetof 매크로 함수의 코드이다. 여기서 눈여겨 살펴볼 표현식은...

((size_t)&((TYPE *)0)->MEMBER)

이다. (TYPE *) 0 로부터 MEMBER 를 접근한 뒤 이를 & 주소 연산자 받아내면 해당 구조체의 멤버 변수 오프셋이 나올 것이다.

+ 추가

깔끔한 표현식이지만, 다음 표현식에는 많은 문제점이 존재한다. 첫 번째, 0 그러니까, NULL 포인터에 대한 역참조(dereference) 는 확실하게 정의되지 않은 행동(Undefined Behavior)이다. 두 번째, TYPE * 자료형의 값을 size_t 로 캐스팅하는 것이 반드시 MEMBER 구조체의 오프셋을 나타내진 않는다. 두 가지 이유로 그러한데...

  1. (TYPE *) 0 이 반드시 0 을 나타내리라는 보장은 없다.
  2. 포인터를 정수로 변환하는 것은 Implementation-defined behavior 이다.

물론 stddef.h 는 C 구현의 한 부분이므로 크게 걱정할 필요는 없지만 다음 표현식이 표준이라고 생각해선 안될 것 같다. 필자도 확답을 못 하는 이유가 출처가 모두 인터넷이다. ISO/IEC 9899 표준 문서를 보고 왔다면 상관 없겠지만 그걸 다 찾아볼 시간이 없었다.
그러나 필자의 생각에도 위 행동은 UB 라고 보여진다. 일단 포인터를 정수로 변환하는 것 자체가 말이 안되고, NULL 포인터가 비트 패턴 0x00 을 나타내지 않을 수도 있다.

container_of : 포함하는 구조체를 반환한다.

container_of 매크로 함수는 아래와 같이 생겼다:

container_of 매크로 함수는 ptr 이 type 구조체의 member 변수를 가르키고 있다면 그 구조체의 주소를 반환해준다.

다음 삽화는 container_of 매크로 함수의 인자가 각각 무엇을 의미하는지 잘 나타내고 있다.

offsetof 와 container_of 를 제대로 이해했다면 1장에서 보여줬던 연결 리스트의 삽화를 어떤 식으로 사용할 수 있을지 감이 잡힐 것이다. 자세한 내용은 리눅스 커널에서 제공하는 연결 리스트 예제를 통해 살피겠다.

3. test_list_sort.c 코드 분석하기

커널에서 제공하는 lib/test_list_sort.c 예제를 분석해보겠다.

1. struct debug_el 구조체

struct debug_el 은 앞서 살펴 보았던 연결 리스트를 포함하는 구조체이다. poison1 과 poison2 는 데이터의 무결성을 검사하는 멤버이므로 무시하고 가장 중요한 멤버는 value 와 serial 이다. value 는 임의의 무작위 값이고 serial 은 처음 동적할당 되었을 때의 인덱스 값이다. 아래의 코드르 보면 serial 과 value 가 어떻게 쓰였는지 이해가 될 것이다.

2. 구조체 배열 elts 동적할당

모듈 삽입 시 가장 먼저 호출되는 list_sort_test 함수 먼저 살펴 보겠다.

list_sort_test 함수는 가장 먼저 kcalloc 함수를 호출하여 struct debug_el **elts 를 동적할당한다. elts 는 전역 변수로 선언되어 있다.

3. 구초제 배열 원소 el 동적 할당

위 코드는 struct debug_el *el 를 동적할당하여 value 에는 0 ~ 999 사이의 난수를 대입하고, serial 에는 순차적으로 0 ~ (TEST_LIST_LEN - 1) 의 값을 대입한다.
이후 초기화가 완료된 el 을 리스트에 삽입한다. 아래의 pr_info 구문은 필자가 디버깅을 위해 추가한 라인이다. 이후 모듈 삽입 시 journalctl 을 통해 그 결과를 확인해볼 것이다.

4. list_sort() 함수

최종적으로 연결 리스트는 serial 을 값을 기준으로 오름차순으로 연결되어 있는 상태이나, value 는 비순차적인 값을 가질 것이다.

list_sort(NULL, &head, cmp);

다음의 함수는 리스트를 comp 함수의 정렬 기준을 바탕으로 다시 연결한다.

cmp 함수는 위와 같이 정의되어 ela->value 에서 elb->value 를 뺀 값을 반환한다. 위 정렬 함수를 사용하면 list_sort 함수는 value 값을 기준으로 오름차순으로 연결리스트를 잇는다.

5. list_sort() 이후 결과 확인

list_sort() 함수 호출 후의 연결 리스트의 연결 상태를 확인하는 코드이다. container_of 매크로 함수를 주목하라. 연결 리스트의 포인터 주소로부터 struct debug_el 구조체의 주소를 받아온다. 연결 리스트의 value 와 serial 멤버 변수의 값을 잇따라 출력한다.

4. 실행 결과 확인

test_list_sort.c 코드를 빌드하여 모듈을 삽입하여 결과를 출력해보았다.

make all
sudo insmod test_list_sort.ko
sudo rmmod test_list_sort
journalctl

list_sort() 함수 호출 전

list_sort() 함수 호출 전의 serial 과 value 의 값이다. 보는 것처럼 serial 은 오름차순으로 출력 되었지만 value 는 무작위 값으로 출력된 것을 확인할 수 있다.

list_sort() 함수 호출 후

list_sort() 함수 호출 이후 반대로 serial 의 값은 무작위로 바뀌고 value 의 값이 오름차순으로 출력된 것을 확인할 수 있다.

5. test_list_sort.c 코드 전문

// SPDX-License-Identifier: GPL-2.0-only
#define pr_fmt(fmt) "list_sort_test: " fmt

#include <linux/kernel.h>
#include <linux/list_sort.h>
#include <linux/list.h>
#include <linux/module.h>
#include <linux/printk.h>
#include <linux/slab.h>
#include <linux/random.h>

/*
 * The pattern of set bits in the list length determines which cases
 * are hit in list_sort().
 */
#define TEST_LIST_LEN (20) /* not including head */

#define TEST_POISON1 0xDEADBEEF
#define TEST_POISON2 0xA324354C

struct debug_el {
	unsigned int poison1;
	struct list_head list;
	unsigned int poison2;
	int value;
	unsigned serial;
};

/* Array, containing pointers to all elements in the test list */
static struct debug_el **elts __initdata;

static int __init check(struct debug_el *ela, struct debug_el *elb)
{
	if (ela->serial >= TEST_LIST_LEN) {
		pr_err("error: incorrect serial %d\n", ela->serial);
		return -EINVAL;
	}
	if (elb->serial >= TEST_LIST_LEN) {
		pr_err("error: incorrect serial %d\n", elb->serial);
		return -EINVAL;
	}
	if (elts[ela->serial] != ela || elts[elb->serial] != elb) {
		pr_err("error: phantom element\n");
		return -EINVAL;
	}
	if (ela->poison1 != TEST_POISON1 || ela->poison2 != TEST_POISON2) {
		pr_err("error: bad poison: %#x/%#x\n",
			ela->poison1, ela->poison2);
		return -EINVAL;
	}
	if (elb->poison1 != TEST_POISON1 || elb->poison2 != TEST_POISON2) {
		pr_err("error: bad poison: %#x/%#x\n",
			elb->poison1, elb->poison2);
		return -EINVAL;
	}
	return 0;
}

static int __init cmp(void *priv, struct list_head *a, struct list_head *b)
{
	struct debug_el *ela, *elb;

	ela = container_of(a, struct debug_el, list);
	elb = container_of(b, struct debug_el, list);

	check(ela, elb);
	return ela->value - elb->value;
}

static int __init list_sort_test(void)
{
	int i, count = 1, err = -ENOMEM;
	struct debug_el *el;
	struct list_head *cur;
	LIST_HEAD(head);

	pr_info("start testing list_sort()");
	elts = kcalloc(TEST_LIST_LEN, sizeof(*elts), GFP_KERNEL);
	if (!elts)
		return err;

	pr_info("before list_sort(): ");
	for (i = 0; i < TEST_LIST_LEN; i++) {
		el = kmalloc(sizeof(*el), GFP_KERNEL);
		if (!el)
			goto exit;

		 /* force some equivalencies */
		el->value = prandom_u32() % 1000;
		el->serial = i;
		el->poison1 = TEST_POISON1;
		el->poison2 = TEST_POISON2;
		elts[i] = el;
		list_add_tail(&el->list, &head);

		pr_info("[%d:%d] ", el->serial, el->value);
	}

	list_sort(NULL, &head, cmp);

	pr_info("after list_sort(): ");
	err = -EINVAL;
	for (cur = head.next; cur->next != &head; cur = cur->next) {
		struct debug_el *el1;
		int cmp_result;

		if (cur->next->prev != cur) {
			pr_err("error: list is corrupted\n");
			goto exit;
		}

		cmp_result = cmp(NULL, cur, cur->next);
		if (cmp_result > 0) {
			pr_err("error: list is not sorted\n");
			goto exit;
		}

		el = container_of(cur, struct debug_el, list);
		el1 = container_of(cur->next, struct debug_el, list);
		if (cmp_result == 0 && el->serial >= el1->serial) {
			pr_err("error: order of equivalent elements not "
				"preserved\n");
			goto exit;
		}

		if (check(el, el1)) {
			pr_err("error: element check failed\n");
			goto exit;
		}

		pr_info("%d [%d:%d]", count - 1, el->serial, el->value);
		count++;
	}

	el = container_of(cur, struct debug_el, list);
	pr_info("%d [%d:%d]", count - 1, el->serial, el->value);

	pr_info("list_sort succeeded.\n");

	if (head.prev != cur) {
		pr_err("error: list is corrupted\n");
		goto exit;
	}


	if (count != TEST_LIST_LEN) {
		pr_err("error: bad list length %d", count);
		goto exit;
	}

	err = 0;
exit:
	for (i = 0; i < TEST_LIST_LEN; i++)
		kfree(elts[i]);
	kfree(elts);
	return err;
}
module_init(list_sort_test);
MODULE_LICENSE("GPL");

static void __exit exit_list_sort_test(void)
{
	pr_info("unloaded. \n");
}
module_exit(exit_list_sort_test);
MODULE_LICENSE("GPL");

출처

[이미지] https://stackoverflow.com/questions/52359598/whose-address-shall-the-node-of-a-linked-list-store-other-node-or-data-structu
[사이트] http://c-faq.com/struct/offsetof.html
[사이트] http://port70.net/~nsz/c/c11/n1570.html#6.6p9
[사이트] https://stackoverflow.com/questions/57342141/does-this-implementation-of-offsetof-invoke-undefined-behavior
[사이트] https://stackoverflow.com/questions/2597142/when-was-the-null-macro-not-0
[이미지] https://linuxwell.wordpress.com/2012/11/10/magical-container_of-macro/

profile
문연수
2000.11.30
이전 포스트

Linux Tutorial #18 user copy 테스트

다음 포스트

Linux Tutorial #20 리눅스 커널 레드-블랙 트리 (Red-black tree)

2개의 댓글

comment-user-thumbnail
TOT0Ro
2024년 9월 5일

커널은 최적화화 코드 재사용을 위해선 어떤 미친 짓거리라도 하는 것 같습니다. 지금은 메이플 트리로 대체된 RB트리의 경우 Parent node를 포인터로 저장하지 않고 long 타입으로 저장하는데, 그 이유가 4바이트로 align하면 주소 LSB 2비트가 00으로 정렬되니 그 2비트를 이용해서 Red/Black 데이터를 저장하더군요. ㅋㅋㅋㅋ

1개의 답글