Sorting (lib/sort & lib/list_sort)

리눅스 커널이 제공하는 두 가지 범용 정렬 API를 심층 분석합니다. lib/sort.c의 in-place heapsort는 배열을 O(n log n) 최악 보장으로 정렬하고, lib/list_sort.c의 bottom-up merge sort는 연결 리스트(Linked List)를 안정 정렬합니다. quicksort를 배제한 설계 이유, 비교자(comparator) 작성 패턴, swap 최적화 전략, 2:1 비율 병합의 수학적 근거, readdir/extent/slab/네트워크 등 커널 전반의 실제 호출 사례, 성능 벤치마크와 구현 역사까지 포괄합니다.

커널 정렬 개요

리눅스 커널은 사용자 공간의 qsort(3)와 달리, 두 가지 범용 정렬 함수를 제공합니다. 각각은 대상 자료구조에 최적화되어 있습니다.

두 함수는 모두 비교 함수(comparator)를 콜백(Callback)으로 받아 정렬 기준을 결정합니다. 정렬 로직 자체는 비교 독립적이므로, 하나의 구현으로 정수, 포인터, 구조체(Struct) 등 모든 타입에 대응합니다.

사용 빈도와 선택 기준

커널 6.x 기준으로 두 API의 사용 빈도를 분석하면:

왜 Quicksort가 아닌가

사용자 공간에서 가장 널리 쓰이는 quicksort가 커널에서 배제된 이유는 세 가지입니다.

introsort 대안 검토

introsort(quicksort + heapsort 하이브리드, C++ STL의 std::sort)도 검토 대상이었습니다:

커널에서 introsort를 선택하지 않은 이유: (1) 코드 복잡도 대비 성능 이득이 미미하고, (2) 커널의 정렬 대상은 대부분 수백~수천 개로 작아 평균 성능 차이가 미미하며, (3) 단순한 구현이 버그 위험을 줄입니다.

초기 커널(2.6.11 이전)에는 lib/qsort.c가 존재했지만, Matt Mackall이 2006년에 heapsort로 교체했습니다. 교체 커밋 메시지에는 다음과 같은 근거가 명시되었습니다:

/*
 * A fast, small, non-recursive O(nlog n) sort for the Linux kernel
 *
 * This performs a heapsort. Unlike the textbook version, it is
 * iterative rather than recursive, and uses a single heapify()
 * pass to build the initial heap.
 *
 * The comparison function should return negative/zero/positive
 * for less/equal/greater, like strcmp.
 */

Heapsort 알고리즘

lib/sort.c의 heapsort는 두 단계로 동작합니다:

1. Build-heap (heapify) — 배열을 max-heap으로 구성합니다. 하위 절반의 노드부터 역순으로 sift-down을 수행합니다.
2. Extract-max — 루트(최댓값)와 마지막 요소를 교환한 뒤, 힙 크기를 줄이고 루트에서 sift-down합니다. n-1회 반복하면 정렬 완료입니다.

커널 구현의 핵심 최적화는 sift-down에 있습니다. 교과서적 heapsort는 부모-자식을 매번 교환하지만, 커널은 "빈 자리"를 아래로 밀어내며 최종 위치에서 한 번만 기록합니다.

/* lib/sort.c — sift-down 핵심 (간략화) */
static void sift_down(void *base, size_t i, size_t n,
                       size_t size, cmp_func_t cmp, swap_func_t swap)
{
    size_t child;
    while (i * 2 + 1 < n) {
        child = i * 2 + 1;
        /* 오른쪽 자식이 더 크면 선택 */
        if (child + 1 < n &&
            cmp(base + (child + 1) * size,
                base + child * size) > 0)
            child++;
        /* 힙 속성 만족 시 종료 */
        if (cmp(base + i * size,
                base + child * size) >= 0)
            break;
        swap(base + i * size, base + child * size, size);
        i = child;
    }
}

전체 heapsort 흐름

/* lib/sort.c — sort_r() 전체 흐름 (간략화) */
void sort_r(void *base, size_t num, size_t size,
            cmp_r_func_t cmp_func, swap_func_t swap_func,
            const void *priv)
{
    /* swap 함수 자동 선택 */
    if (!swap_func) {
        if (is_aligned(base, size, sizeof(long)))
            swap_func = swap_words_32;  /* word swap */
        else
            swap_func = swap_bytes;     /* byte swap */
    }

    /* Phase 1: build max-heap (heapify)
     * n/2-1부터 0까지 역순으로 sift-down */
    for (int i = num / 2 - 1; i >= 0; i--)
        sift_down(base, i, num, size, cmp_func, priv, swap_func);

    /* Phase 2: extract-max 반복
     * 루트(최댓값)를 끝으로 이동, 힙 크기 감소, sift-down */
    for (int i = num - 1; i > 0; i--) {
        swap_func(base, base + i * size, size);
        sift_down(base, 0, i, size, cmp_func, priv, swap_func);
    }
}

힙 인덱스 계산

배열 기반 힙에서 인덱스 관계:

sort() API

sort()는 커널에서 가장 기본적인 배열 정렬 함수입니다.

/* include/linux/sort.h */
void sort(void *base, size_t num, size_t size,
          cmp_func_t cmp, swap_func_t swap);

sort() 동작 보장

• 시간 — O(n log n) 최악/평균/최선, 어떤 입력이든 동일
• 공간 — O(1) 추가 메모리 (in-place)
• 안정성 — 불안정 (동일 키 원소의 순서 비보장)
• 중단 안전 — 정렬 중 인터럽트/선점(Preemption)은 안전하지만, 비교 함수 내에서 슬립(Sleep)하면 안됨 (atomic 컨텍스트 가능)
• 재진입 — 같은 배열에 대해 재진입 호출 불가 (동일 데이터 동시 정렬 금지)

사용 예시:

static int cmp_u32(const void *a, const void *b)
{
    u32 va = *(const u32 *)a;
    u32 vb = *(const u32 *)b;
    if (va < vb) return -1;
    if (va > vb) return 1;
    return 0;
}

u32 arr[1024];
/* ... 배열 채우기 ... */
sort(arr, 1024, sizeof(u32), cmp_u32, NULL);

에러 핸들링

sort()는 반환값이 void이며 실패하지 않습니다. 이는 동적 메모리 할당을 수행하지 않기 때문입니다. 비교 함수가 잘못되면 정렬 결과가 부정확하지만, 함수 자체는 항상 반환합니다.

/* 안전한 사용 패턴 */
if (n > 1) {
    sort(array, n, elem_size, my_cmp, NULL);
    /* 디버그 빌드에서 결과 검증 */
    #ifdef CONFIG_DEBUG_SORT
    for (size_t i = 0; i < n - 1; i++)
        WARN_ON(my_cmp(array + i * elem_size,
                        array + (i+1) * elem_size) > 0);
    #endif
}

sort_r() API

sort_r()은 비교 함수에 추가 컨텍스트(priv)를 전달할 수 있는 확장 버전입니다.

/* include/linux/sort.h */
void sort_r(void *base, size_t num, size_t size,
            cmp_r_func_t cmp, swap_func_t swap,
            const void *priv);

/* cmp_r_func_t 시그니처 */
typedef int (*cmp_r_func_t)(const void *a, const void *b,
                              const void *priv);

priv 포인터는 비교 함수가 외부 상태(예: 정렬 방향, 참조 테이블)를 참조해야 할 때 사용합니다. POSIX qsort_r(3)의 커널 대응입니다.

struct sort_ctx {
    bool descending;
};

static int cmp_with_ctx(const void *a, const void *b,
                          const void *priv)
{
    const struct sort_ctx *ctx = priv;
    int result = cmp_u32(a, b);
    return ctx->descending ? -result : result;
}

struct sort_ctx ctx = { .descending = true };
sort_r(arr, n, sizeof(u32), cmp_with_ctx, NULL, &ctx);

sort_r() 실전 사용 사례

/* perf 이벤트 정렬 — 그룹 리더 기준 정렬 */
struct perf_sort_ctx {
    struct perf_event *group_leader;
    bool sort_by_cpu;
};

static int perf_cmp_event(const void *a, const void *b,
                            const void *priv)
{
    const struct perf_sort_ctx *ctx = priv;
    const struct perf_event *ea = *(void **)a;
    const struct perf_event *eb = *(void **)b;

    if (ctx->sort_by_cpu) {
        if (ea->cpu != eb->cpu)
            return ea->cpu - eb->cpu;
    }
    /* 그룹 리더와의 거리 기준 2차 정렬 */
    return ea->group_index - eb->group_index;
}

sort()와 sort_r()의 관계

/* include/linux/sort.h — sort()는 sort_r()의 래퍼 */
static inline void sort(void *base, size_t num, size_t size,
                         cmp_func_t cmp_func,
                         swap_func_t swap_func)
{
    return sort_r(base, num, size,
                   _cmp_wrapper, swap_func, cmp_func);
}

/* 내부 래퍼: cmp_func_t → cmp_r_func_t 변환 */
static int _cmp_wrapper(const void *a, const void *b,
                         const void *priv)
{
    cmp_func_t cmp = priv;
    return cmp(a, b);
}

비교자 패턴

올바른 비교 함수는 커널 정렬의 핵심입니다. 잘못된 비교자는 무한 루프, 데이터 손상, 미정의 동작을 초래합니다.

cmp_func_t 시그니처

typedef int (*cmp_func_t)(const void *, const void *);

반환값 규약:

• 음수 — a < b
• 0 — a == b
• 양수 — a > b

타입 안전 래퍼 패턴

/* 구조체 배열 정렬 예시 */
struct extent_info {
    u64 start_block;
    u32 length;
    u16 flags;
};

static int cmp_extent(const void *a, const void *b)
{
    const struct extent_info *ea = a;
    const struct extent_info *eb = b;
    /* u64 뺄셈은 오버플로우 위험 → 비교 연산 사용 */
    if (ea->start_block < eb->start_block) return -1;
    if (ea->start_block > eb->start_block) return  1;
    return 0;
}

다중 키 정렬

static int cmp_multi_key(const void *a, const void *b)
{
    const struct entry *ea = a, *eb = b;
    /* 1차 키: priority (내림차순) */
    if (ea->priority != eb->priority)
        return eb->priority - ea->priority;
    /* 2차 키: timestamp (오름차순) */
    if (ea->timestamp < eb->timestamp) return -1;
    if (ea->timestamp > eb->timestamp) return  1;
    return 0;
}

커널 내 실제 비교자 예시

커널 소스에서 자주 등장하는 비교자 패턴들:

/* 1. 단순 정수 비교 — drivers/acpi/acpica/nsaccess.c */
static int cmp_resource(const void *a, const void *b)
{
    const struct resource *ra = a, *rb = b;
    if (ra->start < rb->start) return -1;
    if (ra->start > rb->start) return  1;
    return 0;
}

/* 2. 문자열 비교 — fs/proc/base.c */
static int proc_cmp_name(void *priv,
    const struct list_head *a,
    const struct list_head *b)
{
    const struct proc_entry *pa = list_entry(a, struct proc_entry, list);
    const struct proc_entry *pb = list_entry(b, struct proc_entry, list);
    return strcmp(pa->name, pb->name);
}

/* 3. 복합 키 비교 — drivers/gpu/drm/drm_modes.c */
static int drm_mode_compare(void *priv,
    const struct list_head *a,
    const struct list_head *b)
{
    struct drm_display_mode *ma = list_entry(a, struct drm_display_mode, head);
    struct drm_display_mode *mb = list_entry(b, struct drm_display_mode, head);
    /* 1차: 해상도 (큰 것 우선) */
    int diff = mb->hdisplay * mb->vdisplay
             - ma->hdisplay * ma->vdisplay;
    if (diff) return diff;
    /* 2차: refresh rate (높은 것 우선) */
    diff = drm_mode_vrefresh(mb) - drm_mode_vrefresh(ma);
    if (diff) return diff;
    /* 3차: preferred 모드 우선 */
    diff = (mb->type & DRM_MODE_TYPE_PREFERRED)
         - (ma->type & DRM_MODE_TYPE_PREFERRED);
    return diff;
}

비교자 작성 체크리스트

Swap 최적화

lib/sort.c의 성능은 swap 전략에 크게 의존합니다. 커널은 요소 크기와 정렬(alignment)에 따라 세 가지 swap 전략을 자동 선택합니다.

word swap 구현:

/* lib/sort.c — word-at-a-time swap */
static void swap_words(void *a, void *b, size_t size)
{
    do {
        unsigned long t = *(unsigned long *)a;
        *(unsigned long *)a = *(unsigned long *)b;
        *(unsigned long *)b = t;
        a += sizeof(unsigned long);
        b += sizeof(unsigned long);
        size -= sizeof(unsigned long);
    } while (size);
}

/* byte 단위 폴백 */
static void swap_bytes(void *a, void *b, size_t size)
{
    do {
        char t = *(char *)a;
        *(char *)a++ = *(char *)b;
        *(char *)b++ = t;
    } while (--size);
}

커스텀 swap이 필요한 경우

요소가 자기참조 포인터를 가질 때는 커스텀 swap이 필수입니다. 단순 메모리 복사로는 내부 포인터가 깨집니다.

/* 자기참조 구조체의 커스텀 swap 예시 */
struct self_ref {
    int key;
    struct self_ref *self;  /* 자기 자신을 가리킴 */
    char data[64];
};

static void swap_self_ref(void *a, void *b, size_t size)
{
    struct self_ref tmp;
    memcpy(&tmp, a, size);
    memcpy(a, b, size);
    memcpy(b, &tmp, size);
    /* 자기참조 포인터 복원 */
    ((struct self_ref *)a)->self = a;
    ((struct self_ref *)b)->self = b;
}

swap 성능 비교

List Sort 알고리즘

lib/list_sort.c는 이중 연결 리스트(struct list_head)를 위한 bottom-up merge sort를 구현합니다. 2009년 Don Mullis가 초기 버전을 작성하고, 2019년 George Spelvin(Andrey Abramov)이 현재의 최적화된 버전으로 재작성했습니다.

알고리즘의 핵심 루프 (간략화):

/* lib/list_sort.c — bottom-up merge sort 핵심 */
void list_sort(void *priv, struct list_head *head,
               list_cmp_func_t cmp)
{
    struct list_head *list = head->next, *pending = NULL;
    int count = 0;

    /* 리스트를 head에서 분리 → 단일 연결 리스트로 */
    head->prev->next = NULL;

    do {
        size_t bits;
        struct list_head **tail = &pending;

        /* 노드 1개를 pending에 추가 */
        list->prev = pending;
        pending = list;
        list = list->next;
        pending->next = NULL;
        count++;

        /* 2:1 비율 규칙에 따라 병합 */
        for (bits = count; bits & 1; bits >>= 1)
            tail = &(*tail)->prev;
        if (bits) {
            struct list_head *a = *tail, *b = a->prev;
            a = merge(priv, cmp, b, a);
            a->prev = b->prev;
            *tail = a;
        }
    } while (list);

    /* 남은 pending 리스트 최종 병합 */
    list = pending;
    pending = pending->prev;
    for (;;) {
        struct list_head *next = pending->prev;
        list = merge(priv, cmp, pending, list);
        pending = next;
        if (!next) break;
    }
    /* 단일→이중 연결 리스트 복원 */
    merge_final(priv, cmp, head, pending, list);
}

merge() 함수 상세

두 정렬된 단일 연결 리스트를 하나로 병합하는 핵심 함수입니다.

/* lib/list_sort.c — merge() 전체 (간략화) */
static struct list_head *merge(void *priv,
    list_cmp_func_t cmp,
    struct list_head *a, struct list_head *b)
{
    struct list_head *head, **tail = &head;

    for (;;) {
        /* a ≤ b이면 a 선택 (안정성 보장: ≤ not <) */
        if (cmp(priv, a, b) <= 0) {
            *tail = a;
            tail = &a->next;
            a = a->next;
            if (!a) {
                *tail = b;
                break;
            }
        } else {
            *tail = b;
            tail = &b->next;
            b = b->next;
            if (!b) {
                *tail = a;
                break;
            }
        }
    }
    return head;
}

merge_final() — 이중 연결 리스트 복원

정렬 과정에서 prev 포인터를 임시로 용도 변경(pending 스택 포인터)했으므로, 최종 병합 후 이중 연결 리스트를 복원해야 합니다.

/* lib/list_sort.c — merge_final() (간략화) */
static void merge_final(void *priv, list_cmp_func_t cmp,
    struct list_head *head,
    struct list_head *a, struct list_head *b)
{
    struct list_head *tail = head;

    for (;;) {
        if (cmp(priv, a, b) <= 0) {
            tail->next = a;
            a->prev = tail;
            tail = a;
            a = a->next;
            if (!a) break;
        } else {
            tail->next = b;
            b->prev = tail;
            tail = b;
            b = b->next;
            if (!b) {
                b = a; break;
            }
        }
    }
    /* 나머지 요소 연결 + 원형 리스트 복원 */
    while (b) {
        tail->next = b;
        b->prev = tail;
        tail = b;
        b = b->next;
    }
    tail->next = head;
    head->prev = tail;
}

list_sort() API

/* include/linux/list_sort.h */
typedef int (*list_cmp_func_t)(void *priv,
    const struct list_head *a,
    const struct list_head *b);

void list_sort(void *priv, struct list_head *head,
               list_cmp_func_t cmp);

struct dentry_info {
    char name[256];
    ino_t ino;
    struct list_head list;
};

static int cmp_dentry(void *priv,
                       const struct list_head *a,
                       const struct list_head *b)
{
    const struct dentry_info *da = list_entry(a, struct dentry_info, list);
    const struct dentry_info *db = list_entry(b, struct dentry_info, list);
    return strcmp(da->name, db->name);
}

/* 사용 */
LIST_HEAD(dentry_list);
/* ... 리스트에 요소 추가 ... */
list_sort(NULL, &dentry_list, cmp_dentry);

안정성 분석

안정 정렬(stable sort)은 동일 키 값을 가진 요소들의 상대적 순서를 보존합니다. 이 속성이 커널에서 중요한 경우가 있습니다.

merge 함수에서 안정성을 보장하는 핵심 코드:

/* lib/list_sort.c — merge() 내부 */
if (cmp(priv, a, b) <= 0) {
    /* a ≤ b → a를 결과에 먼저 연결 (안정성 보장) */
    *tail = a;
    tail = &a->next;
    a = a->next;
} else {
    *tail = b;
    tail = &b->next;
    b = b->next;
}

안정성 실험

/* 안정성 차이 실험 */
struct pair {
    int key;
    int original_index;
};

struct pair data[] = {
    {3, 0}, {1, 1}, {3, 2}, {2, 3}, {3, 4}
};

/* sort() 결과 (불안정):
 * {1,1}, {2,3}, {3,4}, {3,0}, {3,2}  ← key=3인 원소 순서 변경됨
 *
 * list_sort() 결과 (안정):
 * {1,1}, {2,3}, {3,0}, {3,2}, {3,4}  ← key=3인 원소 원래 순서 유지
 */

병합 패턴: 2:1 비율

list_sort()의 가장 독특한 설계는 2:1 비율 병합 규칙입니다. 이는 Timsort의 "nearly-optimal" 병합 정책에서 영감을 받았지만, 커널에 맞게 단순화되었습니다.

2:1 비율의 수학적 근거는 비교 횟수 최소화입니다. 크기가 비슷한 두 서브리스트를 병합할 때 비교 횟수가 최적에 가깝습니다. count의 이진 표현에서 연속된 1-비트를 추적하는 것은 이 비율을 O(1) 시간에 유지하는 간결한 방법입니다.

비트 카운터 동작 상세

/* 비트 카운터로 병합 시점 결정하는 핵심 코드 */
for (bits = count; bits & 1; bits >>= 1)
    tail = &(*tail)->prev;

/* count별 동작:
 * count=1 (0b1):   bits&1=1 → tail 1번 이동 → 병합 불필요 (if(bits)=0)
 * count=2 (0b10):  bits&1=0 → 이동 없음   → 병합 불필요
 * count=3 (0b11):  bits&1=1 → tail 1번 이동, bits=1, bits&1=1 → 1번 더 → 병합!
 * count=4 (0b100): bits&1=0 → 이동 없음   → 병합 불필요
 * count=5 (0b101): bits&1=1 → tail 1번 이동 → bits=10, 0&1=0 → 병합!
 * count=6 (0b110): bits&1=0 → 이동 없음   → 병합 불필요
 * count=7 (0b111): 3번 이동 → 3개 서브리스트 연쇄 병합!
 */

이 패턴은 이진수 덧셈의 올림(carry)과 동일합니다. count에 1을 더할 때 올림이 발생하는 자릿수만큼 병합이 연쇄됩니다. 결과적으로 pending 스택의 서브리스트 크기가 2의 거듭제곱에 가까운 분포를 유지합니다.

pending 스택의 최대 깊이

pending 스택의 최대 깊이는 ⌈log2(n)⌉입니다. 이는 count의 이진 표현 비트 수와 동일합니다.

pending 스택은 리스트 노드의 prev 포인터를 재활용(Recycling)하므로, 추가 메모리 할당이 전혀 없습니다. 이것이 list_sort()의 O(1) 공간 복잡도를 보장하는 핵심입니다.

복잡도 분석

heapsort의 비교 횟수 유도:

• Build-heap: 최대 2n 비교 (sift-down × n/2 노드)
• Extract 단계: 최대 2⌊log₂ n⌋ 비교 × (n-1)회
• 총 비교: ≤ 2n log₂ n + O(n)

merge sort의 비교 횟수:

• 각 병합 단계에서 n개 원소를 이동하며 최대 n-1회 비교
• log₂ n 단계 → 총 ≤ n log₂ n
• 실제로는 2:1 비율 병합으로 이론적 최솟값(n log₂ n - n + 1)에 근접

실측 비교 횟수

lib/test_sort.c와 lib/test_list_sort.c의 카운터를 활성화하면 실측 비교 횟수를 확인할 수 있습니다:

이론적 비교 횟수 최적성

비교 기반 정렬의 이론적 하한은 ⌈log2(n!)⌉ ≈ n log2 n - 1.443n입니다. 각 알고리즘의 비교 횟수를 비교합니다:

readdir 정렬

파일시스템의 readdir은 list_sort()의 대표적 호출자입니다. 디렉터리 엔트리를 정렬하여 사용자에게 일관된 순서를 제공합니다.

/* fs/libfs.c — dcache_readdir에서 사용 */
static int cmp_dentry_name(void *priv,
    const struct list_head *a,
    const struct list_head *b)
{
    const struct dentry *da = list_entry(a, struct dentry, d_child);
    const struct dentry *db = list_entry(b, struct dentry, d_child);
    return strcmp(da->d_name.name, db->d_name.name);
}

tmpfs, debugfs, sysfs 등 메모리 기반 파일시스템에서 dcache_readdir()은 디렉터리 엔트리를 d_child 리스트에서 직접 읽으므로, 정렬된 출력을 위해 list_sort()를 활용합니다.

readdir 성능 고려사항

/* 디렉터리에 파일이 많으면 정렬 비용이 체감됨 */
/*
 * 파일 수    정렬 시간 (tmpfs, 대략적)
 * 100       ~10 μs
 * 1,000     ~150 μs
 * 10,000    ~2 ms
 * 100,000   ~30 ms  ← ls 명령이 느려짐
 */

/* 대형 디렉터리는 htree (ext4) 또는 B-tree (btrfs)로
 * 디스크 레벨에서 이미 정렬되어 있어 별도 정렬 불필요 */

readdir 정렬이 필요한 파일시스템

Extent 정렬

ext4와 btrfs는 디스크 블록 할당 최적화를 위해 extent를 정렬합니다.

/* fs/ext4/extents.c — extent 정렬 예시 (개념적) */
static int ext4_cmp_extent(const void *a, const void *b)
{
    const struct ext4_extent *ea = a;
    const struct ext4_extent *eb = b;
    /* 논리 블록 번호 기준 오름차순 */
    if (le32_to_cpu(ea->ee_block) < le32_to_cpu(eb->ee_block))
        return -1;
    if (le32_to_cpu(ea->ee_block) > le32_to_cpu(eb->ee_block))
        return  1;
    return 0;
}

extent 정렬 최적화 효과

extent를 논리 블록 순으로 정렬하면 다음과 같은 I/O 최적화가 가능합니다:

• 연속 읽기 병합 — 인접 extent를 하나의 큰 I/O 요청으로 합침 (bio merging)
• 엘리베이터 최적화 — 블록 번호 순 정렬로 디스크 시크 최소화
• 프리페치 효율 — 순차 접근 패턴을 생성하여 HW 프리페치 활성화
• delalloc 할당 — 정렬된 extent 목록에서 연속 블록 그룹을 효율적으로 할당

/* fs/btrfs/volumes.c — 디바이스 정렬 예시 */
static int btrfs_cmp_device_info(const void *a, const void *b)
{
    const struct btrfs_device_info *di_a = a;
    const struct btrfs_device_info *di_b = b;
    /* 사용 가능 공간이 큰 디바이스 우선 (내림차순) */
    if (di_a->total_avail > di_b->total_avail)
        return -1;
    if (di_a->total_avail < di_b->total_avail)
        return 1;
    return 0;
}

/* 디바이스 할당 전 정렬 — 가장 여유 있는 디바이스부터 사용 */
sort(devices_info, ndevs, sizeof(struct btrfs_device_info),
     btrfs_cmp_device_info, NULL);

Slab Freelist 정렬

SLUB 할당자는 보안 강화를 위해 freelist를 랜덤화하는데, 이 과정에서 sort()가 관여합니다.

/* mm/slub.c — freelist 셔플 (개념적) */
static void shuffle_freelist(struct kmem_cache *s,
                              struct slab *slab)
{
    unsigned int *order;
    int i;

    order = kmalloc_array(slab->objects, sizeof(int), GFP_KERNEL);
    for (i = 0; i < slab->objects; i++)
        order[i] = i;

    /* Fisher-Yates 셔플 */
    for (i = slab->objects - 1; i > 0; i--) {
        unsigned int j = get_random_u32_below(i + 1);
        swap(order[i], order[j]);
    }

    /* 셔플된 순서로 freelist 재구성 */
    build_freelist(s, slab, order);
    kfree(order);
}

freelist 보안 강화 역사

CONFIG_SLAB_FREELIST_RANDOM이 활성화되면, 새 slab 페이지(Page) 초기화 시 셔플된 인덱스 배열을 생성합니다. 이 셔플은 Fisher-Yates 알고리즘을 사용하며, 초기 인덱스 배열의 생성에 정렬이 관여할 수 있습니다.

SLUB freelist 포인터 하드닝

/* mm/slub.c — freelist 포인터 난독화
 * CONFIG_SLAB_FREELIST_HARDENED 활성화 시 */

/* 저장: XOR 인코딩 */
static inline void *freelist_ptr_encode(
    const struct kmem_cache *s,
    void *ptr, unsigned long ptr_addr)
{
    return (void *)((unsigned long)ptr ^
                    s->random ^ ptr_addr);
}

/* 읽기: XOR 디코딩 */
static inline void *freelist_ptr_decode(
    const struct kmem_cache *s,
    void *ptr, unsigned long ptr_addr)
{
    return (void *)((unsigned long)ptr ^
                    s->random ^ ptr_addr);
}

/* 해커가 freelist 포인터를 조작하면
 * XOR 검증에서 잘못된 주소가 나와 감지됨 */

네트워크 정렬

네트워크 서브시스템에서도 정렬은 다양한 곳에서 활용됩니다.

/* net/sched/sch_prio.c — TC prio qdisc 개념적 사용 */
static int prio_cmp_band(void *priv,
    const struct list_head *a,
    const struct list_head *b)
{
    struct sk_buff *skb_a = list_entry(a, struct sk_buff, list);
    struct sk_buff *skb_b = list_entry(b, struct sk_buff, list);
    /* 낮은 priority = 높은 우선순위 */
    return skb_a->priority - skb_b->priority;
}

Netfilter hook 정렬

/* net/netfilter/core.c — hook 우선순위 정렬 */
static int nf_hook_cmp(const void *a, const void *b)
{
    const struct nf_hook_ops *ha = a, *hb = b;
    /* 낮은 priority 값 = 먼저 실행 */
    if (ha->priority < hb->priority) return -1;
    if (ha->priority > hb->priority) return  1;
    return 0;
}

GRO 패킷(Packet) 정렬

GRO(Generic Receive Offload)에서 병합 대상 패킷을 timestamp 순으로 정렬하여, TCP 스트림 재조립의 정확성을 보장합니다.

/* net/core/gro.c — GRO 리스트 정렬 (개념적) */
static int gro_cmp_skb(void *priv,
    const struct list_head *a,
    const struct list_head *b)
{
    struct sk_buff *sa = list_entry(a, struct sk_buff, list);
    struct sk_buff *sb = list_entry(b, struct sk_buff, list);
    /* flow hash로 그룹화, 같은 flow 내에서 sequence 순 */
    if (sa->hash != sb->hash)
        return sa->hash < sb->hash ? -1 : 1;
    return before(TCP_SKB_CB(sa)->seq,
                  TCP_SKB_CB(sb)->seq) ? -1 : 1;
}

주요 호출자 분석

커널 소스 트리에서 sort()와 list_sort()의 호출 사이트를 분류하면, 정렬이 커널 전반에 얼마나 광범위하게 사용되는지 알 수 있습니다.

성능 벤치마크

커널 자체 테스트(lib/test_sort.c, lib/test_list_sort.c)와 실측 데이터를 기반으로 성능을 분석합니다.

/* lib/test_sort.c — 커널 자체 테스트 */
static int __init test_sort_init(void)
{
    int *a, i, r = 1;

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

    for (i = 0; i < TEST_LEN; i++) {
        r = (r * 725861) % 6599;
        a[i] = r;
    }

    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 sort failed at %d\n", i);
            goto exit;
        }
    pr_info("test sort passed\n");
exit:
    kfree(a);
    return 0;
}

캐시 효과 상세

정렬 성능에서 캐시 효과는 지배적 요소입니다.

/* 간접 정렬(indirect sort) 패턴 */
struct sort_key {
    u64 key;
    int original_index;
};

static int cmp_key(const void *a, const void *b)
{
    const struct sort_key *ka = a, *kb = b;
    if (ka->key < kb->key) return -1;
    if (ka->key > kb->key) return  1;
    return 0;
}

/* 1단계: 키만 추출 (16B 구조체) */
struct sort_key keys[n];
for (int i = 0; i < n; i++) {
    keys[i].key = large_structs[i].sort_field;
    keys[i].original_index = i;
}

/* 2단계: 작은 키 배열 정렬 (캐시 친화적) */
sort(keys, n, sizeof(struct sort_key), cmp_key, NULL);

/* 3단계: 원본 배열 재배치 */
for (int i = 0; i < n; i++)
    result[i] = large_structs[keys[i].original_index];

커널 자체 테스트 결과 분석

# lib/test_sort.c 테스트 출력 예시 (dmesg)
[    3.125] test_sort: Testing sort() with 4096 elements... passed (1247 us)
[    3.128] test_sort: Testing sort_r() with 4096 elements... passed (1289 us)
[    3.130] test_sort: Comparisons: 45123, swaps: 31876

# lib/test_list_sort.c 테스트 출력 예시
[    3.135] test_list_sort: Testing list_sort() with 4096 elements... passed (1567 us)
[    3.137] test_list_sort: Comparisons: 39812 (optimal: 39456)
[    3.139] test_list_sort: Stability check: passed

구현 역사

커널 정렬 API의 진화는 성능과 안전성의 균형을 찾는 과정이었습니다.

list_sort 2019년 재작성 상세

George Spelvin의 재작성은 커밋 043b3f7b6377에서 이루어졌으며, 다음 변경을 포함합니다:

• top-down → bottom-up — 재귀 분할 대신, 요소를 하나씩 읽어 pending 스택에 쌓는 방식
• 자연 병합 제거 — 이전 버전은 정렬된 구간(run)을 탐지했으나, 오버헤드가 이득보다 커서 제거
• 비트 카운터 도입 — count의 이진 표현으로 병합 시점을 O(1)에 결정
• merge_final 최적화 — 마지막 병합에서 prev 포인터 복원을 동시에 수행

/* George Spelvin의 커밋 메시지에서 발췌:
 *
 * This patch renames the original bottom-up implementation
 * and replaces it with a substantially reworked version.
 * The key insight is that the number of pending sublists
 * needed is limited to ceil(log2(n)), and the merge pattern
 * can be determined by the binary representation of the
 * count of items processed so far.
 */

sort.c 2019년 최적화 (Rasmus Villemoes)

같은 시기에 lib/sort.c도 다음과 같이 최적화되었습니다:

• swap 타입 감지 — 요소 크기와 정렬을 보고 word/byte swap 자동 선택
• parent_to_children 접근 — 부모에서 자식으로의 sift-down을 최적화하여 비교 횟수 감소
• sort_r() 도입 — 비교 함수에 컨텍스트를 전달하는 qsort_r(3) 대응

초기 qsort 문제점

/* 초기 lib/qsort.c (제거됨) — 문제가 된 재귀 구현 */
static void qsort_r(void *base, size_t n, size_t es, ...)
{
    /* ... */
    qsort_r(base, n_left, es, ...);  /* ← 재귀! */
    qsort_r(right, n_right, es, ...); /* ← 재귀! */
    /* 최악: O(n) 재귀 깊이 → 스택 오버플로우 */
}

Kconfig 관련 옵션

sort()와 list_sort()는 별도의 Kconfig 옵션 없이 항상 커널에 포함됩니다. lib/sort.o와 lib/list_sort.o는 obj-y로 빌드되므로 모듈이 아닌 커널 이미지에 직접 링크됩니다. EXPORT_SYMBOL로 모듈에서도 사용할 수 있습니다.

/* lib/sort.c */
EXPORT_SYMBOL(sort_r);
EXPORT_SYMBOL(sort);

/* lib/list_sort.c */
EXPORT_SYMBOL(list_sort);

커널 버전별 주요 변경 요약

# lib/Makefile
obj-y += sort.o
obj-y += list_sort.o

# 테스트 모듈
obj-$(CONFIG_TEST_SORT) += test_sort.o
obj-$(CONFIG_TEST_LIST_SORT) += test_list_sort.o

디버깅(Debugging) 가이드

정렬 관련 버그는 발견이 어렵고 재현이 불안정합니다. 주요 오류 패턴과 진단 방법을 정리합니다.

비교자 오류 패턴

비교자 오류 실제 CVE/버그 사례

비교자 버그는 실제 커널 버그 리포트에서 발견된 적이 있습니다:

/* CVE 사례: 정수 오버플로우로 인한 잘못된 정렬
 * 공격자가 조작된 파일시스템 이미지를 마운트하면,
 * extent 정렬 결과가 부정확해져 데이터 손상 가능 */

/* 취약한 비교자 (실제 버그 패턴) */
static int vulnerable_cmp(const void *a, const void *b)
{
    return ((struct entry *)a)->offset -
           ((struct entry *)b)->offset;
    /* offset이 u64이면 뺄셈 결과가 int로 잘림!
     * 0x100000000 - 0x1 = 0xFFFFFFFF → int로 -1 (올바름)
     * 0xFFFFFFFF00000000 - 0x1 = overflow → 잘못된 부호 */
}

/* 수정된 비교자 */
static int fixed_cmp(const void *a, const void *b)
{
    u64 oa = ((struct entry *)a)->offset;
    u64 ob = ((struct entry *)b)->offset;
    if (oa < ob) return -1;
    if (oa > ob) return  1;
    return 0;
}

list_head 손상 디버깅

list_sort()에 손상된 리스트를 전달하면 커널 OOPS가 발생합니다. 일반적인 손상 원인:

/* CONFIG_DEBUG_LIST=y 활성화 시 자동 검증 */
/* 다음과 같은 WARNING이 출력됨: */

/* list_add corruption. prev->next should be next (ffffffff82345678),
 * but was           (dead000000000100).
 * (prev=ffff888012345678). */

/* 디버그 힌트:
 * dead000000000100 = LIST_POISON1 → 이미 삭제된 노드
 * 0000000000000000 = NULL → 초기화되지 않은 노드 */

비교자 전순서 검증 코드

/* 디버그용: 비교자 전순서 속성 검증 */
static void verify_total_order(void *base, size_t n,
    size_t size, cmp_func_t cmp)
{
    size_t i, j;
    for (i = 0; i < n && i < 100; i++) {
        void *a = base + i * size;
        /* 반사성: cmp(a, a) == 0 */
        WARN_ON(cmp(a, a) != 0);
        for (j = i + 1; j < n && j < 100; j++) {
            void *b = base + j * size;
            int ab = cmp(a, b);
            int ba = cmp(b, a);
            /* 반대칭: sign(cmp(a,b)) == -sign(cmp(b,a)) */
            WARN_ON((ab > 0) != (ba < 0));
            WARN_ON((ab < 0) != (ba > 0));
            WARN_ON((ab == 0) != (ba == 0));
        }
    }
}

성능 프로파일링(Profiling)

# ftrace로 sort() 호출 추적
echo sort > /sys/kernel/debug/tracing/set_ftrace_filter
echo function > /sys/kernel/debug/tracing/current_tracer
echo 1 > /sys/kernel/debug/tracing/tracing_on
# ... 작업 수행 ...
cat /sys/kernel/debug/tracing/trace

# perf로 정렬 비교 함수 핫스팟 분석
perf record -g -a -- sleep 10
perf report --symbol-filter=sort

정렬 알고리즘 선택 가이드

자체 테스트 모듈 활용

# sort 자체 테스트 실행 (커널 빌드 시 CONFIG_TEST_SORT=m)
modprobe test_sort
dmesg | tail -5
# 출력: test_sort: sort() passed

# list_sort 자체 테스트 실행 (CONFIG_TEST_LIST_SORT=m)
modprobe test_list_sort
dmesg | tail -5
# 출력: test_list_sort: list_sort() passed

KASAN으로 메모리 오류 탐지

/* CONFIG_KASAN=y로 빌드하면
 * sort() 중 buffer overrun 자동 탐지 */

/* 흔한 버그: 비교 함수에서 잘못된 오프셋 접근 */
static int buggy_cmp(const void *a, const void *b)
{
    /* 구조체 크기를 초과하는 오프셋 접근 */
    const int *pa = a + 128;  /* ← KASAN 감지! */
    return *pa - *(const int *)(b + 128);
}

lockdep과 정렬

정렬 중 비교 함수 내에서 락을 잡으면 lockdep 경고가 발생할 수 있습니다:

/* 안티패턴: 비교 함수 내 락 획득 */
static int bad_cmp(const void *a, const void *b)
{
    spin_lock(&some_lock);   /* ← 위험! */
    int result = ...;
    spin_unlock(&some_lock);
    return result;
}

/* 해결: 정렬 전에 필요한 데이터를 미리 복사 */
spin_lock(&some_lock);
memcpy(local_copy, shared_data, n * size);
spin_unlock(&some_lock);
sort(local_copy, n, size, simple_cmp, NULL);

관련 문서

• 연결 리스트 (list_head) — list_sort()의 기반 자료구조, 순회/조작 매크로
• Min-Heap / Red-Black Tree — lib/min_heap.h 힙 기반 우선순위 큐, 자기 균형 이진 탐색 트리
• XArray — 인덱스 기반 정렬 컨테이너(Container)
• 메모리 관리(Memory Management) — slab 할당자, freelist 구조
• VFS — readdir, dcache 동작 원리
• ext4 — extent 정렬, 블록 할당
• 동기화 기법 — 정렬 중 동시 접근 보호
• 메모리 관리 (Slab) — SLUB freelist 랜덤화, 보안 강화
• NAPI — 네트워크 패킷 수신 처리, GRO 정렬
• XArray — 인덱스 기반 정렬 컨테이너

요약 비교 테이블

참고 자료

• lib/sort.c — Bootlin Elixir — 배열 정렬(Heapsort) 구현 소스 코드입니다
• include/linux/sort.h — Bootlin Elixir — sort(), sort_r() 함수 선언 및 비교자 타입 정의입니다
• lib/list_sort.c — Bootlin Elixir — 연결 리스트 병합 정렬(Merge Sort) 구현 소스 코드입니다
• include/linux/list_sort.h — Bootlin Elixir — list_sort() 함수 선언 및 비교자 타입 정의입니다
• lib/test_sort.c — Bootlin Elixir — sort() 자체 테스트 모듈 소스 코드입니다
• lib/test_list_sort.c — Bootlin Elixir — list_sort() 자체 테스트 모듈 소스 코드입니다
• LWN: A new sort implementation for the kernel (2020) — George Spelvin의 bottom-up heapsort 최적화 패치 분석 기사입니다
• LWN: Reworking sort() and list_sort() (2019) — sort()와 list_sort()의 비교 횟수 최적화 리워크 과정을 다룹니다
• George Spelvin의 sort/list_sort 최적화 패치 시리즈 — 비교 횟수 25% 감소, bottom-up heapsort 도입 등 핵심 패치입니다
• Kernel API — Sorting (kernel.org) — 커널 공식 문서의 정렬 API 레퍼런스입니다
• Wikipedia: Heapsort — sort()가 채택한 힙 정렬 알고리즘의 이론적 배경입니다
• Wikipedia: Merge sort — Bottom-up list implementation — list_sort()가 채택한 연결 리스트 병합 정렬의 학술적 기반입니다
• Knuth, D. — Sorting and Searching (TAOCP Vol. 3) — 정렬 알고리즘 전반의 학술적 기초 참고 문헌입니다
• Huang & Langston (1988) — Practical In-Place Merging — O(1) 추가 메모리 병합 정렬의 학술적 배경입니다