이번 장에서는 커널 라이브러리 함수인 sort 를 사용해서 데이터를 정렬해보겠다. 리눅스 커널 소스트리 lib/sort.c 에 가면 그 내용을 확인할 수 있다.

리눅스 커널에서 사용하는 정렬은 heap 정렬 이다. 주석의 설명처럼 힙 정렬은 퀵 정렬에 비해 평균 속도가 더 낮지만, 더 안정적으로 동작(추가적인 메모리를 필요로 하지 않고, 최악의 경우에도 O(n log n) 을 보장)하기에 리눅스 커널에선 힙 정렬을 사용한다. 이제 sort 함수를 사용해서 배열의 원소를 정렬하고 그 결과를 확인하는 코드를 작성해보겠다.

1. sort() 함수 테스트

test/lib/test_sort.c

/**
	M: Yeounsu Moon <yyyynoom@gmail.com>
	W: https://velog.io/@mythos
	F: lib/test_sort.c
	This program is free software; you can redistribute it and/or
	modify it under the terms of the GNU General Public License
*/
#include <linux/init.h>
#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/sort.h>		// sort()
#include <linux/slab.h>		// kmalloc_array(), kfree()

#define TEST_LEN 10

int cmpint(const void *a, const void *b)
{
	if (*(const int *)a < *(const int *)b)
		return -1;
	else if (*(const int *)a > *(const int *)b)
		return 1;
	else
		return 0;
}

static int __init test_sort_init(void)
{
	int *a;
	int i;
	int r;
	int err;

	printk("test_sort: test_sort_init(): starting...\n");

	err = -ENOMEM;
	a = kmalloc_array(TEST_LEN, sizeof(*a), GFP_KERNEL);
	if (!a)
		return err;

	pr_info("sort before data[%d]: ", TEST_LEN);
	for (i = 0; i < TEST_LEN; i++) {
		r = (r * 725861) % 6599;
		a[i] = r;

		pr_info("%d ", a[i]);
	}

	sort(a, TEST_LEN, sizeof(*a), cmpint, NULL);

	for (i = 0; i < TEST_LEN - 1; i++) {
		if (a[i] > a[i + 1]) {
			pr_err("test has failed\n");
			
			err = -EINVAL;
			goto exit;
		}
	}

	pr_info("test passed\n");

	err = 0;
exit:
	kfree(a);
	return 0;

}

static void __exit test_sort_exit(void) 
{
	printk("linux-modules: lib/test_sort.c: test_sort_exit().\n");
}

module_init(test_sort_init);
module_exit(test_sort_exit);

MODULE_LICENSE("GPL");
MODULE_AUTHOR("Yeounsu Moon");
MODULE_DESCRIPTION("Test sort function.");
MODULE_VERSION("0.1.0");

코드가 좀 길지만 어려운 내용은 전혀 없다. 리눅스 커널 코딩 스타일을 환기하면서 천천히 코드를 읽어보면 이해가 될 것이다. 전체적인 코드의 흐름은 아래와 같다:

1. kmalloc_array 함수를 사용해서 메모리를 동적으로 할당
2. 초기화하지 않은 변수 r 을 통해 난수를 생성, 동적할당된 배열에 저장
3. sort() 함수를 호출하여 오름차순(cmpint) 정렬
4. 반복문을 통해 제대로 정렬 됐는지 확인

2. Makefile

Makefile 은 다음과 같이 작성 되었다.

obj-m += test_sort.o

KDIR := /lib/modules/$(shell uname -r)/build

test_sort:
	make -C $(KDIR) M=$(PWD) modules

clean:
	make -C $(KDIR) M=$(PWD) clean

이전 Makefile 과 다르지 않으므로 따로 설명하지 않겠다.

3. 실행 결과

배열의 각 원소는 임의로 생성된 값임을 알 수 있다. test passed 메세지가 나왔으므로 정렬에 성공한건데 궁금하다면 직접 배열의 각 원소를 출력해봐도 좋을 것이다. 이후의 예제도 모두 이런 식으로 테스트할 예정이므로 잘 숙지하기를 바란다.

출처

[책] 리눅스 커널 소스 해설: 기초 입문 (정재준 저)