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) 등 모든 타입에 대응합니다.

사용 빈도와 선택 기준

최근 메인라인 계열에서 두 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는 이중 연결 리스트를 위한 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 성능 고려사항

디렉터리에 파일이 많으면 정렬 비용이 체감됩니다.

대형 디렉터리는 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);

lib/sort.c 소스 코드 심층 분석

Linux 6.x의 lib/sort.c는 약 200줄의 간결한 코드로, George Spelvin(Andrey Abramov)이 2019년에 재작성한 bottom-up heapsort를 구현합니다. 이 섹션에서는 함수 전체를 워크스루하며 각 최적화 기법을 분석합니다.

swap 함수 자동 선택 로직

sort_r()의 첫 번째 작업은 최적의 swap 함수를 결정하는 것입니다. 호출자가 swap_func = NULL을 전달하면, 요소 크기와 메모리 정렬(alignment)을 검사하여 3단계로 분기합니다.

/* lib/sort.c — swap 함수 자동 선택 (Linux 6.x) */
static void sort_r(void *base, size_t num, size_t size,
                   cmp_r_func_t cmp_func,
                   swap_r_func_t swap_func,
                   const void *priv)
{
    /* swap 함수 자동 선택 */
    swap_func_t swap = swap_func;
    if (!swap) {
        if (is_aligned(base, size, 8))
            swap = SWAP_WORDS_64;       /* 8바이트 정렬 → u64 단위 */
        else if (is_aligned(base, size, 4))
            swap = SWAP_WORDS_32;       /* 4바이트 정렬 → u32 단위 */
        else
            swap = SWAP_BYTES;          /* 그 외 → 1바이트 단위 */
    }
    /* do_swap: 함수 포인터를 지역 변수에 캐싱 */
    void (*do_swap)(void *, void *, size_t) = swap;
    ...
}

parent/child 인덱스 계산

배열 기반 힙에서 인덱스 계산은 정수 산술(Integer Arithmetic)만으로 수행됩니다. 커널 구현은 0-based 인덱싱을 사용합니다.

/* lib/sort.c — 힙 인덱스 계산 */

/* 부모 인덱스: 정수 나눗셈으로 O(1) */
static inline size_t parent(size_t i)
{
    return (i - 1) / 2;
}

/* 왼쪽 자식: 비트 시프트 + OR로 계산 가능
 * 2*i + 1 == (i << 1) | 1 */
static inline size_t left_child(size_t i)
{
    return 2 * i + 1;
}

/* 오른쪽 자식 */
static inline size_t right_child(size_t i)
{
    return 2 * i + 2;
}

sift-down 루프 최적화

2019년 George Spelvin의 핵심 기여는 sift-down의 비교 횟수를 최소화한 것입니다. 기존 교과서 구현은 부모와 두 자식을 각각 비교하여 sift-down당 최대 2번의 비교를 수행했지만, 최적화 버전은 "빈 자리를 아래로 밀어내는" 전략으로 비교 횟수를 약 25% 줄였습니다.

/* lib/sort.c — 최적화된 sift-down (Linux 6.x, 간략화) */
static void sift_down(void *base, size_t i, size_t n,
                       size_t size, cmp_r_func_t cmp,
                       const void *priv,
                       swap_func_t do_swap)
{
    void *node = base + i * size;
    size_t child;

    /* Phase 1: 빈 자리를 리프까지 밀어내기
     * 비교 대상을 자식끼리만 비교 (부모-자식 비교 생략) */
    while ((child = 2 * i + 1) < n) {
        /* 두 자식 중 큰 쪽 선택 — 비교 1회 */
        if (child + 1 < n &&
            cmp(base + child * size,
                base + (child + 1) * size, priv) < 0)
            child++;
        /* 자식을 부모 위치로 이동 */
        do_swap(base + i * size, base + child * size, size);
        i = child;
    }

    /* Phase 2: 원래 노드의 올바른 위치 탐색 (sift-up)
     * 빈 자리에서 위로 올라가며 삽입 위치 결정 */
    while (i > 0) {
        size_t p = (i - 1) / 2;
        if (cmp(base + p * size, base + i * size, priv) >= 0)
            break;
        do_swap(base + i * size, base + p * size, size);
        i = p;
    }
}

sort_r() 전체 워크스루

전체 sort_r() 구현을 단계별로 추적합니다.

/* lib/sort.c — sort_r() 전체 구현 워크스루 (Linux 6.x) */
void sort_r(void *base, size_t num, size_t size,
            cmp_r_func_t cmp_func,
            swap_r_func_t swap_func,
            const void *priv)
{
    /* ① 조기 반환: 0개 또는 1개는 이미 정렬됨 */
    if (num <= 1)
        return;

    /* ② swap 전략 결정 (위에서 설명) */
    void (*do_swap)(...) = select_swap(base, size, swap_func);

    /* ③ Phase 1: Build max-heap
     * 마지막 비-리프 노드(num/2 - 1)부터 루트(0)까지
     * 역순으로 sift-down 수행 → O(n) 시간 */
    for (size_t i = num / 2; i--;)  /* i = num/2-1 ... 0 */
        sift_down(base, i, num, size, cmp_func, priv, do_swap);

    /* ④ Phase 2: Extract-max 반복
     * 루트(최댓값)를 배열 끝으로 이동,
     * 힙 크기를 1 줄이고 새 루트를 sift-down */
    for (size_t i = num - 1; i > 0; i--) {
        do_swap(base, base + i * size, size);
        sift_down(base, 0, i, size, cmp_func, priv, do_swap);
    }
    /* 결과: base[0] ≤ base[1] ≤ ... ≤ base[num-1] */
}

lib/list_sort.c 소스 코드 심층 분석

lib/list_sort.c는 George Spelvin이 2019년에 재작성한 bottom-up merge sort입니다. 핵심 아이디어는 정렬된 서브리스트(run)를 pending 스택에 쌓아두고, 2:1 비율 규칙에 따라 병합하는 것입니다.

2:1 balanced merge 전략의 수학적 근거

list_sort()의 병합 시점 결정은 count 변수의 비트 패턴으로 제어됩니다. 이 전략은 Timsort의 merge 정책과 유사하지만, 더 단순한 비트 연산으로 구현됩니다.

/* lib/list_sort.c — 2:1 병합 결정 로직 */
do {
    size_t bits;
    struct list_head **tail = &pending;

    /* 새 노드를 pending 스택의 맨 앞에 추가 */
    list->prev = pending;
    pending = list;
    list = list->next;
    pending->next = NULL;
    count++;

    /* 핵심: count의 하위 비트 패턴으로 병합 결정
     * count의 최하위 연속 1-bit 개수만큼 pending에서 건너뛴 후,
     * 그 위치의 두 리스트를 병합
     *
     * 예: count = 0b...1011 (11)
     *   bits = 11: 11 & 1 = 1 → tail을 한 칸 전진, bits >>= 1 → 5
     *   bits = 5:   5 & 1 = 1 → tail을 한 칸 전진, bits >>= 1 → 2
     *   bits = 2:   2 & 1 = 0 → 루프 종료
     *   bits != 0 → *tail 위치에서 병합 수행 */
    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;  /* 병합 결과의 prev = 다음 pending */
        *tail = a;
    }
} while (list);

merge() 함수: 안정 정렬 보장

merge()는 두 정렬된 단일 연결 리스트를 병합합니다. 안정성(stability)을 보장하기 위해 동일 키에서 앞쪽 리스트(a)의 원소를 우선합니다.

/* 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 (;;) {
        /* 안정 정렬 핵심: cmp <= 0이면 a를 선택
         * 동일 키(cmp == 0)에서 a가 먼저 → 원래 순서 유지 */
        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 스택 연결에 임시 사용되었습니다. merge_final()은 최종 병합과 동시에 prev 포인터를 복원하여 올바른 이중 연결 리스트를 만듭니다.

/* 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;
    u8 count = 0;

    for (;;) {
        /* merge()와 동일한 안정 병합 + prev 포인터 복원 */
        if (cmp(priv, a, b) <= 0) {
            tail->next = a;
            a->prev = tail;   /* ← prev 복원 */
            tail = a;
            a = a->next;
            if (!a) break;
        } else {
            tail->next = b;
            b->prev = tail;   /* ← prev 복원 */
            tail = b;
            b = b->next;
            if (!b) {
                b = a;
                break;
            }
        }
    }
    /* 나머지 연결 + prev 복원 */
    while (b) {
        tail->next = b;
        b->prev = tail;
        tail = b;
        b = b->next;
    }
    /* 순환 리스트 완성: tail ↔ head */
    tail->next = head;
    head->prev = tail;
}

min_heapify_all 연동

lib/sort.c의 heapsort와 include/linux/min_heap.h의 min-heap은 동일한 heap 원리를 공유하지만, 목적이 다릅니다. sort()는 배열을 정렬하고, min-heap은 동적으로 최솟값을 추출합니다.

lib/min_heap.h 구조

/* include/linux/min_heap.h — min-heap 자료구조 */
struct min_heap {
    void *data;        /* 힙 배열 */
    int nr;             /* 현재 요소 수 */
    int size;           /* 최대 용량 */
};

struct min_heap_callbacks {
    int elem_size;
    bool (*less)(const void *lhs, const void *rhs);
    void (*swp)(void *lhs, void *rhs);
};

/* 전체 배열을 min-heap으로 변환 — O(n) */
static inline void min_heapify_all(struct min_heap *heap,
    const struct min_heap_callbacks *funcs)
{
    int i;
    /* sort()의 build-heap과 동일한 O(n) 알고리즘 */
    for (i = heap->nr / 2 - 1; i >= 0; i--)
        min_heapify(heap, i, funcs);
}

정렬 → 힙 변환 체인

일부 커널 서브시스템은 데이터를 먼저 sort()로 정렬한 후, 동적 운영을 위해 힙으로 변환합니다. 이 패턴은 초기 구성 비용을 최소화합니다.

/* perf에서의 sort → heapify 체인 사용 사례 (간략화) */

/* 1단계: 이벤트 배열을 우선순위 기준으로 정렬 */
sort(events, nr_events, sizeof(struct perf_event *),
     perf_event_cmp, NULL);

/* 2단계: 정렬된 배열로 min-heap 초기화
 * 이미 정렬되어 있으므로 heapify 비용이 줄어듦
 * (정렬된 입력에 대한 heapify는 비교만 수행, swap 거의 없음) */
struct min_heap event_heap = {
    .data = events,
    .nr   = nr_events,
    .size = max_events,
};
min_heapify_all(&event_heap, &perf_heap_cbs);

/* 3단계: 이후 동적으로 최솟값 추출/삽입 */
while (event_heap.nr > 0) {
    struct perf_event *min = min_heap_peek(&event_heap);
    process_event(min);
    min_heap_pop(&event_heap, &perf_heap_cbs);
}

커널 정렬 실전 패턴

커널의 다양한 서브시스템이 sort()와 list_sort()를 활용하는 구체적인 패턴을 분석합니다. 각 사용 사례는 고유한 제약 조건과 최적화 전략을 가집니다.

ext4 extent 정렬

ext4 파일시스템은 extent(연속 블록 범위)를 논리 블록 번호(logical block number) 순으로 정렬하여 검색 효율을 높입니다.

/* fs/ext4/extents_status.c — extent 상태 트리 삽입 */
static int ext4_es_cmp(const void *a, const void *b)
{
    const struct extent_status *ea = a;
    const struct extent_status *eb = b;

    /* 논리 블록 번호 기준 오름차순
     * es_lblk는 ext4_lblk_t (u32) */
    if (ea->es_lblk < eb->es_lblk) return -1;
    if (ea->es_lblk > eb->es_lblk) return  1;
    return 0;
}

/* extent 배열을 정렬하여 이진 검색 가능하게 만듦 */
sort(es_array, nr_extents, sizeof(struct extent_status),
     ext4_es_cmp, NULL);
/* 이후 bsearch()로 O(log n) 검색 가능 */

slab freelist 셔플링

CONFIG_SLAB_FREELIST_RANDOM이 활성화되면, slab 할당자는 freelist 순서를 무작위화하여 힙 메모리 레이아웃 예측을 방지합니다.

/* mm/slub.c — freelist 순서 셔플링 (간략화) */

/* Fisher-Yates 셔플을 위한 비교자가 아닌,
 * 미리 생성된 무작위 순서 배열을 sort()로 정렬 */
static void init_freelist_randomization(struct kmem_cache *s)
{
    unsigned int *order;
    int count = oo_objects(s->oo);

    order = kmalloc_array(count, sizeof(*order), GFP_KERNEL);

    /* 0 ~ count-1 인덱스를 무작위 순서로 배열 */
    for (int i = 0; i < count; i++)
        order[i] = i;

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

/* 새 slab 페이지 할당 시 random_seq 순서로 freelist 구성 */
static void shuffle_freelist(struct kmem_cache *s,
                             struct slab *slab)
{
    void *cur, *next;
    unsigned int *order = s->random_seq;
    /* random_seq에 따라 freelist 연결 순서를 재배치 */
    for (int i = 0; i < slab->objects - 1; i++) {
        cur = fixup_red_left(s, slab_address(slab) + order[i] * s->size);
        next = fixup_red_left(s, slab_address(slab) + order[i+1] * s->size);
        set_freepointer(s, cur, next);
    }
}

readdir 결과 정렬

일부 파일시스템은 디렉토리 엔트리(dentry)를 이름 순서로 정렬하여 readdir 결과의 일관성을 보장합니다.

/* fs/readdir.c — 디렉토리 엔트리 정렬 패턴 */

/* 파일시스템별 비교자 예시: 이름 기준 정렬 */
static int dcache_name_cmp(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);
}

/* 디렉토리 내 하위 엔트리를 이름순으로 정렬 */
list_sort(NULL, &parent->d_subdirs, dcache_name_cmp);

네트워크: FIB 규칙 우선순위 정렬

FIB(Forwarding Information Base) 규칙은 우선순위 값에 따라 정렬되어, 라우팅(Routing) 결정 시 순서대로 매칭됩니다.

/* net/core/fib_rules.c — FIB 규칙 우선순위 정렬 */
static int fib_rule_cmp(void *priv,
    const struct list_head *a,
    const struct list_head *b)
{
    struct fib_rule *ra = list_entry(a, struct fib_rule, list);
    struct fib_rule *rb = list_entry(b, struct fib_rule, list);

    /* 낮은 pref 값 = 높은 우선순위 */
    if (ra->pref < rb->pref) return -1;
    if (ra->pref > rb->pref) return  1;
    return 0;
}

/* 규칙 추가 후 전체 리스트 재정렬
 * list_sort()의 안정성이 중요: 같은 우선순위의 규칙은
 * 추가된 순서를 유지해야 함 */
list_sort(NULL, &ops->rules_list, fib_rule_cmp);

보안: LSM 후크(Hook) 정렬

LSM(Linux Security Module) 프레임워크는 등록된 보안 모듈의 후크 함수를 우선순위에 따라 정렬합니다.

/* security/security.c — LSM 후크 정렬 (간략화) */

/* 보안 모듈 후크 우선순위 정렬
 * 우선순위가 높은 모듈의 후크가 먼저 호출됨 */
static int lsm_hook_cmp(const void *a, const void *b)
{
    const struct security_hook_list *ha = a;
    const struct security_hook_list *hb = b;

    /* 커널 내장 LSM이 외부 모듈보다 먼저 */
    if (ha->lsm->order < hb->lsm->order) return -1;
    if (ha->lsm->order > hb->lsm->order) return  1;
    return 0;
}

/* 호출 체인 초기화 시 정렬
 * SELinux → AppArmor → SMACK 순서 등을 보장 */
sort(hook_heads, nr_hooks,
     sizeof(struct security_hook_list),
     lsm_hook_cmp, NULL);

정렬 안정성과 비교자 설계

정렬 안정성(stability)은 동일 키를 가진 원소들의 상대적 순서가 정렬 전후에 보존되는지를 결정합니다. 커널의 두 정렬 API는 이 특성이 다르며, 비교자 설계에 직접적인 영향을 줍니다.

list_sort()의 안정성 보장 메커니즘

list_sort()의 안정성은 merge() 함수의 단 하나의 비교 연산자에 의해 결정됩니다.

/* 안정성의 핵심: <= 비교 */
if (cmp(priv, a, b) <= 0) {
    /* a를 선택 → 동일 키에서 앞쪽 원소가 먼저 출력 */
    *tail = a;
    ...
}

/* 만약 < 만 사용하면 (불안정):
 * cmp == 0일 때 b가 선택될 수 있어 순서가 뒤집힘 */

sort()의 불안정성과 대응 방법

heapsort 기반의 sort()는 본질적으로 불안정합니다. extract-max 단계에서 동일 키 원소의 위치가 예측 불가능하게 재배치됩니다. 안정 정렬이 필요한 경우 다음 패턴을 사용합니다.

/* 안정 정렬이 필요할 때: 원래 인덱스를 2차 키로 사용 */
struct stable_entry {
    struct original_data data;
    unsigned int orig_index;  /* 원래 위치 기록 */
};

/* 정렬 전: 원래 인덱스 저장 */
for (int i = 0; i < n; i++)
    entries[i].orig_index = i;

/* 비교자: 1차 키 동일 시 원래 인덱스로 결정 */
static int stable_cmp(const void *a, const void *b)
{
    const struct stable_entry *sa = a, *sb = b;
    int r = primary_cmp(&sa->data, &sb->data);
    if (r) return r;
    /* 2차 키: 원래 인덱스 (작은 것이 앞으로) */
    if (sa->orig_index < sb->orig_index) return -1;
    return 1;
}

sort(entries, n, sizeof(struct stable_entry),
     stable_cmp, NULL);

엄격한 약순서(Strict Weak Ordering)

비교 함수는 반드시 엄격한 약순서(strict weak ordering) 관계를 만족해야 합니다. 이를 위반하면 정렬 결과가 정의되지 않거나 무한 루프에 빠질 수 있습니다.

잘못된 비교자로 인한 커널 버그 사례

/* 버그 사례 1: 부동소수점 유사 비교 (커널에서는 드물지만 교훈적)
 * NaN 처리 없이 비교하면 추이성 위반 */
static int bad_float_cmp(const void *a, const void *b)
{
    /* 잘못됨: NaN과의 비교는 항상 false
     * NaN < x == false, NaN > x == false, NaN == x == false
     * → 추이성 위반! */
    return (*(float *)a > *(float *)b) - (*(float *)a < *(float *)b);
}

/* 버그 사례 2: 오버플로우로 인한 비대칭성 위반 */
static int overflow_cmp(const void *a, const void *b)
{
    /* 잘못됨: INT_MAX - INT_MIN = 오버플로우!
     * cmp(INT_MAX, INT_MIN) = 음수 (올바르지 않음)
     * → a > b인데 음수를 반환 → 비대칭성 위반 */
    return *(int *)a - *(int *)b;
}

/* 올바른 버전 */
static int correct_cmp(const void *a, const void *b)
{
    int va = *(const int *)a;
    int vb = *(const int *)b;
    /* 비교 연산으로 오버플로우 방지 */
    if (va < vb) return -1;
    if (va > vb) return  1;
    return 0;
}

벤치마크와 선택 가이드

커널의 두 정렬 API는 각각 최적의 사용 시나리오가 있습니다. 이 섹션에서는 데이터 크기, 캐시 효율, 안정성 요구사항에 따른 선택 기준을 제시합니다.

sort() vs list_sort() 선택 기준

데이터 크기별 성능 특성

정렬 API 성능 비교입니다 (x86-64, 커널 6.x, 1000회 평균).

sort()가 전반적으로 30~40% 빠릅니다 (캐시 효과). 단, 리스트에서 배열로의 변환 비용을 포함하면 list_sort()가 유리합니다.

캐시 효율 분석

sort()와 list_sort()의 성능 차이는 대부분 캐시 효율에서 비롯됩니다.

인라인 정렬(insertion sort) 임계값

매우 작은 배열(n < 16)에서는 sort() 호출의 함수 호출 오버헤드가 정렬 작업 자체보다 클 수 있습니다. 이 경우 인라인 삽입 정렬이 더 효율적입니다.

/* 소규모 배열 최적화: 인라인 삽입 정렬 */
static inline void small_sort(int *arr, int n)
{
    /* n < 16일 때 sort()보다 효율적
     * 이유: (1) 함수 호출 오버헤드 없음
     *       (2) 적은 원소에서 삽입 정렬의 O(n²)이
     *           heapsort의 O(n log n)보다 빠름
     *       (3) 거의 정렬된 입력에 적응적 */
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

/* 실전 사용 패턴 */
if (count < 16)
    small_sort(array, count);
else
    sort(array, count, sizeof(int), cmp_int, NULL);

선택 의사결정 트리

Sift-down 단계별 동작 시각화

커널의 lib/sort.c가 사용하는 최적화된 sift-down은 두 단계로 동작합니다. Phase 1에서 빈 자리를 리프까지 밀어내고, Phase 2에서 정확한 위치를 찾아 올라갑니다. 아래 다이어그램은 루트 노드 값 2를 7개 원소 max-heap에서 sift-down하는 전체 과정을 보여줍니다.

list_sort() 병합 과정 시각화

lib/list_sort.c의 bottom-up merge sort는 입력 리스트의 노드를 하나씩 읽어 pending 스택에 누적하며, 비트 카운터 규칙에 따라 인접 서브리스트를 병합합니다. 아래 다이어그램은 6개 원소 리스트 [4, 2, 6, 1, 5, 3]의 전체 병합 과정을 단계별로 추적합니다.

swap_func 최적화 결정 트리

lib/sort.c의 성능을 결정하는 핵심 요소 중 하나는 swap 전략입니다. 호출자가 swap_func = NULL을 전달하면, 커널은 요소의 메모리 정렬(alignment)과 크기에 따라 최적의 swap 함수를 자동 선택합니다. 이 과정은 sort_r() 진입 시 한 번만 수행되어 루프 내 분기 오버헤드가 없습니다.

/* lib/sort.c — is_aligned 매크로 (간략화) */
static inline bool is_aligned(const void *base,
                               size_t size, size_t align)
{
    /* base 주소와 size 모두 align의 배수인지 확인
     * 비트 AND로 O(1) 판정 — 나눗셈 없음 */
    return !((unsigned long)base | size) & (align - 1);
}

/* 커스텀 swap이 필요한 대표적 경우 */
struct hlist_node_entry {
    struct hlist_node node;  /* pprev 포인터가 자기참조 */
    u64 key;
    char data[48];
};

/* hlist_node의 pprev는 자기 자신의 주소를 참조하므로
 * 단순 메모리 복사 후 pprev를 수정해야 합니다 */
static void swap_hlist_entry(void *a, void *b, size_t size)
{
    struct hlist_node_entry tmp;
    memcpy(&tmp, a, size);
    memcpy(a, b, size);
    memcpy(b, &tmp, size);
    /* pprev 포인터 복원 */
    if (((struct hlist_node_entry *)a)->node.pprev)
        *((struct hlist_node_entry *)a)->node.pprev =
            &((struct hlist_node_entry *)a)->node;
    if (((struct hlist_node_entry *)b)->node.pprev)
        *((struct hlist_node_entry *)b)->node.pprev =
            &((struct hlist_node_entry *)b)->node;
}

실전 구현 예제

커널 모듈(Kernel Module)에서 정렬 API를 실제로 활용하는 패턴을 구체적인 예제와 함께 설명합니다.

예제 1: 구조체 배열 정렬 — 디바이스 우선순위

디바이스 드라이버에서 여러 디바이스를 우선순위 기준으로 정렬하는 실전 패턴입니다. sort()를 사용하고, 커스텀 비교자로 다중 키 정렬을 수행합니다.

#include <linux/sort.h>
#include <linux/slab.h>

/* 디바이스 초기화 순서 정렬 예제 */
struct device_init_entry {
    const char *name;
    int priority;          /* 낮을수록 먼저 초기화 */
    int dependency_depth;  /* 의존성 깊이 (2차 키) */
    void (*init_fn)(void);
};

/* 다중 키 비교자: priority 오름차순 → dependency_depth 오름차순 */
static int cmp_device_init(const void *a, const void *b)
{
    const struct device_init_entry *da = a;
    const struct device_init_entry *db = b;

    /* 1차 키: priority (오름차순) */
    if (da->priority < db->priority)
        return -1;
    if (da->priority > db->priority)
        return 1;

    /* 2차 키: dependency_depth (오름차순)
     * 같은 priority이면 의존성이 적은 것부터 */
    if (da->dependency_depth < db->dependency_depth)
        return -1;
    if (da->dependency_depth > db->dependency_depth)
        return 1;

    return 0;
}

/* 사용 예시 */
static void init_devices_sorted(struct device_init_entry *devs,
                                 int nr_devs)
{
    /* 우선순위 기준 정렬 — swap=NULL로 자동 최적화 */
    sort(devs, nr_devs,
         sizeof(struct device_init_entry),
         cmp_device_init, NULL);

    /* 정렬된 순서대로 디바이스 초기화 */
    for (int i = 0; i < nr_devs; i++) {
        pr_info("init: %s (prio=%d, depth=%d)\n",
                devs[i].name,
                devs[i].priority,
                devs[i].dependency_depth);
        devs[i].init_fn();
    }
}

예제 2: list_sort()를 사용한 우선순위 재정렬

작업 큐(Workqueue)(Work Queue)에서 대기 중인 작업들을 우선순위와 마감 시간에 따라 재정렬하는 패턴입니다. list_sort()의 안정성을 활용하여 동일 우선순위 작업의 삽입 순서를 보존합니다.

#include <linux/list_sort.h>
#include <linux/list.h>

struct work_item {
    struct list_head list;
    int priority;        /* 0=최고, 255=최저 */
    ktime_t deadline;    /* 마감 시간 */
    void (*work_fn)(struct work_item *);
    char desc[32];
};

/* 비교자: priority 오름차순 → deadline 오름차순
 * list_sort()가 안정 정렬이므로, 같은 priority+deadline의
 * 작업은 리스트에 추가된 순서를 유지합니다 */
static int cmp_work_item(void *priv,
                          const struct list_head *a,
                          const struct list_head *b)
{
    const struct work_item *wa =
        list_entry(a, struct work_item, list);
    const struct work_item *wb =
        list_entry(b, struct work_item, list);

    /* 1차 키: priority (낮은 값 = 높은 우선순위) */
    if (wa->priority != wb->priority)
        return wa->priority - wb->priority;

    /* 2차 키: deadline (이른 마감이 먼저) */
    if (ktime_before(wa->deadline, wb->deadline))
        return -1;
    if (ktime_after(wa->deadline, wb->deadline))
        return 1;

    /* 동일 priority+deadline → 안정 정렬로 삽입 순서 유지 */
    return 0;
}

/* 큐 재정렬 함수 */
static void reorder_work_queue(struct list_head *queue,
                                spinlock_t *lock)
{
    spin_lock(lock);
    /* list_sort()는 내부적으로 락을 잡지 않으므로
     * 호출자가 동기화를 보장해야 합니다 */
    list_sort(NULL, queue, cmp_work_item);
    spin_unlock(lock);
}

/* 사용 예시: 높은 우선순위 작업 삽입 후 재정렬 */
static void submit_urgent_work(struct list_head *queue,
                                struct work_item *item,
                                spinlock_t *lock)
{
    spin_lock(lock);
    list_add_tail(&item->list, queue);
    spin_unlock(lock);

    /* 긴급 작업이 추가되었으므로 큐 재정렬
     * 안정 정렬이므로 기존 작업의 상대적 순서는 유지됨 */
    reorder_work_queue(queue, lock);
}

예제 3: sort_r()로 컨텍스트 기반 정렬

sort_r()의 priv 파라미터를 활용하여, 동일한 배열을 다른 기준으로 정렬하는 패턴입니다. 전역 변수 없이 정렬 기준을 동적으로 변경할 수 있습니다.

#include <linux/sort.h>

struct event_record {
    u64 timestamp;
    u32 cpu;
    u32 event_type;
    u32 data;
};

/* 정렬 컨텍스트: 어떤 필드를 기준으로 정렬할지 결정 */
enum sort_key {
    SORT_BY_TIME,
    SORT_BY_CPU,
    SORT_BY_TYPE,
};

struct event_sort_ctx {
    enum sort_key key;
    bool descending;
};

/* 범용 비교자: priv로 전달된 컨텍스트에 따라 정렬 기준 변경 */
static int cmp_event(const void *a, const void *b,
                      const void *priv)
{
    const struct event_record *ea = a;
    const struct event_record *eb = b;
    const struct event_sort_ctx *ctx = priv;
    int result;

    switch (ctx->key) {
    case SORT_BY_TIME:
        if (ea->timestamp < eb->timestamp)
            result = -1;
        else if (ea->timestamp > eb->timestamp)
            result = 1;
        else
            result = 0;
        break;
    case SORT_BY_CPU:
        result = (int)ea->cpu - (int)eb->cpu;
        break;
    case SORT_BY_TYPE:
        result = (int)ea->event_type - (int)eb->event_type;
        break;
    default:
        result = 0;
    }

    return ctx->descending ? -result : result;
}

/* 사용: 같은 배열을 다른 기준으로 정렬 */
static void analyze_events(struct event_record *events,
                           int nr_events)
{
    struct event_sort_ctx ctx;

    /* 시간순 정렬 → 시계열 분석 */
    ctx = (struct event_sort_ctx){
        .key = SORT_BY_TIME, .descending = false
    };
    sort_r(events, nr_events,
           sizeof(struct event_record),
           cmp_event, NULL, &ctx);
    print_timeline(events, nr_events);

    /* CPU별 정렬 → per-CPU 분석 */
    ctx = (struct event_sort_ctx){
        .key = SORT_BY_CPU, .descending = false
    };
    sort_r(events, nr_events,
           sizeof(struct event_record),
           cmp_event, NULL, &ctx);
    print_per_cpu_summary(events, nr_events);
}

예제 4: 성능 비교 시나리오

동일한 데이터를 sort()(배열)와 list_sort()(리스트)로 정렬할 때의 성능 차이를 측정하는 벤치마크 패턴입니다.

#include <linux/sort.h>
#include <linux/list_sort.h>
#include <linux/ktime.h>

#define BENCH_SIZE  10000

struct bench_elem {
    u64 key;
    char payload[56];       /* 총 64B — 캐시라인 크기 */
    struct list_head list;  /* list_sort용 */
};

static int cmp_bench_array(const void *a, const void *b)
{
    const struct bench_elem *ea = a;
    const struct bench_elem *eb = b;
    if (ea->key < eb->key) return -1;
    if (ea->key > eb->key) return  1;
    return 0;
}

static int cmp_bench_list(void *priv,
    const struct list_head *a,
    const struct list_head *b)
{
    const struct bench_elem *ea =
        list_entry(a, struct bench_elem, list);
    const struct bench_elem *eb =
        list_entry(b, struct bench_elem, list);
    if (ea->key < eb->key) return -1;
    if (ea->key > eb->key) return  1;
    return 0;
}

static void run_sort_benchmark(void)
{
    struct bench_elem *arr;
    LIST_HEAD(bench_list);
    ktime_t t1, t2;
    s64 arr_ns, list_ns;

    arr = kvmalloc_array(BENCH_SIZE,
                          sizeof(struct bench_elem),
                          GFP_KERNEL);

    /* 랜덤 데이터 생성 */
    for (int i = 0; i < BENCH_SIZE; i++) {
        arr[i].key = get_random_u64();
        list_add_tail(&arr[i].list, &bench_list);
    }

    /* 배열 정렬 벤치마크 */
    t1 = ktime_get();
    sort(arr, BENCH_SIZE,
         sizeof(struct bench_elem),
         cmp_bench_array, NULL);
    t2 = ktime_get();
    arr_ns = ktime_to_ns(ktime_sub(t2, t1));

    /* 리스트 재구축 후 리스트 정렬 벤치마크 */
    INIT_LIST_HEAD(&bench_list);
    for (int i = 0; i < BENCH_SIZE; i++)
        list_add_tail(&arr[i].list, &bench_list);

    t1 = ktime_get();
    list_sort(NULL, &bench_list, cmp_bench_list);
    t2 = ktime_get();
    list_ns = ktime_to_ns(ktime_sub(t2, t1));

    pr_info("sort benchmark: n=%d\n", BENCH_SIZE);
    pr_info("  sort():      %lld ns\n", arr_ns);
    pr_info("  list_sort(): %lld ns\n", list_ns);
    pr_info("  ratio: sort()/list_sort() = %lld%%\n",
            arr_ns * 100 / list_ns);

    kvfree(arr);
}

예제 5: 정렬된 리스트에 단일 원소 삽입

이미 정렬된 리스트에 새 원소를 하나 추가할 때는 list_sort() 대신 O(n) 삽입 정렬이 더 효율적입니다.

/* 정렬된 리스트에 단일 원소 삽입 — O(n) */
static void sorted_list_insert(struct list_head *head,
                                struct work_item *new_item,
                                list_cmp_func_t cmp)
{
    struct list_head *pos;

    /* 삽입 위치 탐색: cmp(new, pos) <= 0인 첫 위치 */
    list_for_each(pos, head) {
        if (cmp(NULL, &new_item->list, pos) <= 0)
            break;
    }
    /* pos 앞에 삽입 → 정렬 순서 유지 */
    list_add_tail(&new_item->list, pos);
}

/* 선택 기준:
 * - 단일 삽입 → sorted_list_insert()   O(n)
 * - 다수 삽입 후 정렬 → list_sort()     O(n log n)
 * - 임계점: ~log₂(n)개 이상 삽입 시 list_sort()가 유리
 *   (n=1000이면 ~10개 이상 동시 삽입 시 list_sort 선택) */

Linux 6.12 ~ 6.19 Sorting 동향

lib/sort.c는 2024~2026년 구간에 6.12의 *_nonatomic 변종 도입을 제외하면 거의 변경이 없습니다. __sort_r에 may_schedule 플래그가 추가되어 장시간 정렬 도중 cond_resched()가 허용되며, 인접한 min_heap 유틸리티 쪽이 더 활발하게 확장되었습니다. 6.18, 6.19에서도 lib/sort.c 알고리즘 본체는 안정 상태를 유지하고 있습니다.

관련 문서

• 연결 리스트 — 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 — 인덱스 기반 정렬 컨테이너

요약 비교 테이블

Heapsort 단계별 시각화

커널의 lib/sort.c가 사용하는 bottom-up heapsort는 두 단계로 구성됩니다. 먼저 입력 배열을 max-heap으로 변환(heapify)한 뒤, 루트(최대값)를 반복 추출하여 정렬된 영역을 확장합니다. 아래 다이어그램은 8개 원소 [5, 3, 8, 1, 7, 2, 6, 4]에 대한 전체 과정을 단계별로 보여줍니다.

heapify 과정의 커널 구현

커널의 heapify는 배열의 마지막 비-리프(non-leaf) 노드부터 인덱스 0까지 역순으로 sift-down을 수행합니다. n/2 - 1부터 시작하므로 리프 노드(전체의 약 절반)는 건너뜁니다.

/* lib/sort.c — heapify: O(n) 시간에 max-heap 구축 */
for (size_t i = num / 2 - 1; i >= 0; i--) {
    /* bottom-up sift: 리프까지 최대 자식 추적 후 역추적 */
    size_t child;
    for (child = 2 * i + 1; child + 1 < num; child = 2 * child + 1) {
        if (cmp_func(base + child * size, base + (child + 1) * size, priv) < 0)
            child++;  /* 오른쪽 자식이 더 크면 선택 */
    }
    /* child가 리프 → 역추적하며 삽입 위치 탐색 */
    while (child > i && cmp_func(base + i * size, base + child * size, priv) > 0)
        child = (child - 1) / 2;
    /* 실제 이동: child 위치에 원소 배치 후 경로상 shift */
}

extract-max 루프의 커널 구현

heapify 완료 후, 루트(최대값)와 마지막 원소를 swap하고 힙 크기를 1 줄인 뒤 sift-down을 반복합니다. 이 과정이 n-1번 반복되어 오름차순 정렬이 완성됩니다.

/* lib/sort.c — extract-max 루프: O(n log n) */
for (size_t i = num - 1; i > 0; i--) {
    /* 루트(최대)와 마지막 미정렬 원소 교환 */
    do_swap(base, base + i * size, size);

    /* 힙 크기를 i로 줄이고 루트에서 sift-down */
    size_t child, root = 0;
    for (child = 1; child < i; ) {
        if (child + 1 < i &&
            cmp_func(base + child * size, base + (child + 1) * size, priv) < 0)
            child++;
        child = 2 * child + 1;  /* bottom-up: 리프까지 추적 */
    }
    /* 역추적 후 원소 이동 */
}

list_sort 병합 시각화

lib/list_sort.c의 bottom-up 병합 정렬은 timsort와 유사한 pending 리스트 방식을 사용합니다. 입력 리스트를 하나씩 떼어내며 pending 스택에 push하고, 인접 서브리스트의 크기 비율이 2:1을 넘으면 병합합니다. 이 섹션에서는 6개 노드 리스트 [D→B→F→A→E→C]의 병합 과정을 추적합니다.

pending 리스트의 내부 표현

커널 구현에서 pending 리스트는 struct list_head의 prev 포인터만 사용하여 단방향 연결 리스트를 구성합니다. 이 기법은 정렬 중 next 포인터가 불필요하므로 메모리 쓰기를 절반으로 줄입니다.

/* lib/list_sort.c — pending 리스트 관리 */
struct list_head *pending = NULL;
int count = 0;

list_for_each_safe(cur, tmp, head) {
    /* 현재 노드를 분리하여 크기 1인 서브리스트로 만듦 */
    cur->prev = pending;      /* pending 스택에 push */
    pending = cur;
    count++;

    /* count의 하위 비트를 검사하여 병합 결정 */
    for (int bits = count; !(bits & 1); bits >>= 1) {
        /* pending 스택의 상위 두 서브리스트를 병합 */
        pending = merge(priv, cmp, pending->prev, pending);
    }
}
/* 입력 소진 후 남은 pending을 모두 병합 */
merge_final(priv, cmp, head, pending);

merge_final의 리스트 복원

merge_final()은 마지막 병합과 동시에 단방향 pending 체인을 완전한 이중 원형 리스트(list_head)로 복원합니다. 이 과정에서 별도 메모리 할당 없이 기존 노드의 포인터만 재연결합니다.

/* 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;

    while (a && b) {
        if (cmp(priv, a, b) <= 0) {  /* <= 로 안정성 보장 */
            tail->next = a;
            a->prev = tail;
            a = a->next;
        } else {
            tail->next = b;
            b->prev = tail;
            b = b->next;
        }
        tail = tail->next;
    }
    /* 나머지 연결 및 원형 리스트 완성 */
    tail->next = a ? a : b;
    /* ... prev 포인터 복원 + head->prev = tail 설정 ... */
}

swap 최적화 심층

lib/sort.c의 swap 서브시스템은 원소 크기와 메모리 정렬에 따라 3가지 전략을 자동 선택합니다. 이 최적화는 캐시 라인 활용률을 극대화하고 불필요한 바이트 복사를 최소화합니다. 특히 64비트 시스템에서 SWAP_WORDS_64는 8바이트 단위로 교환하여 32바이트 구조체도 4회 반복으로 완료합니다.

SWAP_WORDS_64 내부 구현

SWAP_WORDS_64는 8바이트 단위로 메모리를 교환합니다. 임시 변수 하나(u64 t)만 사용하므로 레지스터(Register)에 완전히 들어갑니다. 컴파일러는 이 패턴을 인식하여 xchg 명령어나 SIMD 교환으로 최적화할 수 있습니다.

/* lib/sort.c — SWAP_WORDS_64 구현 */
static void swap_words_64(void *a, void *b, size_t size)
{
    u64 *ia = (u64 *)a;
    u64 *ib = (u64 *)b;

    do {
        u64 t = *ia;
        *ia++ = *ib;
        *ib++ = t;
    } while ((size -= 8) > 0);
}

SWAP_BYTES의 fallback 전략

정렬 요건을 충족하지 못하는 구조체에 대해 SWAP_BYTES가 사용됩니다. 1바이트 단위 교환은 느리지만, 패킹된(__packed) 구조체나 가변 크기 원소를 안전하게 처리합니다.

/* lib/sort.c — SWAP_BYTES 구현 (fallback) */
static void swap_bytes(void *a, void *b, size_t size)
{
    u8 *ia = (u8 *)a;
    u8 *ib = (u8 *)b;

    do {
        u8 t = *ia;
        *ia++ = *ib;
        *ib++ = t;
    } while (--size > 0);
}

커널 정렬 호출자 맵

Linux 커널에서 sort(), sort_r(), list_sort()를 호출하는 서브시스템은 광범위합니다. 아래 다이어그램은 주요 호출자를 기능 영역별로 분류하고, 각 호출의 목적과 정렬 대상을 요약합니다.

서브시스템별 정렬 특성

각 서브시스템이 정렬을 사용하는 목적은 크게 세 가지로 나뉩니다.

검색 최적화

kallsyms

이진 탐색을 위한 심볼 주소 정렬

extable

예외 테이블을 이진 탐색 O(log n)으로 검색합니다

module

모듈 심볼을 이름순 이진 탐색으로 검색합니다

ftrace

함수 주소를 이진 탐색으로 식별합니다

병합/중복 제거

ext4 extent

인접 extent 병합으로 디스크 단편화(Fragmentation)를 감소시킵니다

block I/O

인접 섹터 요청 병합으로 디스크 시크를 최소화합니다

compaction

연속 빈 페이지 병합으로 고차 할당 성공률을 향상시킵니다

btrfs

delayed ref 병합으로 트랜잭션(Transaction) 커밋을 최적화합니다

순서/우선순위 결정

netfilter

규칙 우선순위 순서를 보장합니다

PCI BAR

리소스 주소 순서로 충돌 없는 할당을 수행합니다

thermal

온도 임계값 순서로 올바른 쿨링 단계를 결정합니다

정렬 진화사

Linux 커널의 정렬 구현은 2002년 첫 도입 이후 여러 차례의 최적화와 재설계를 거쳤습니다. 아래 타임라인은 주요 변경점과 그 배경을 정리합니다.

주요 변경 커밋과 패치(Patch) 시리즈

커널 정렬의 진화 과정에서 가장 중요한 패치들의 목록입니다. 각 패치는 구체적인 성능 개선 수치와 함께 커밋되었습니다.

2002: 최초 도입

Matt Mackall이 lib/sort.c를 추가했습니다. userspace qsort()를 커널에 안전한 heapsort로 대체하여, O(n²) 최악 시간 복잡도를 O(n log n) 보장으로 개선하고 재귀를 제거했습니다.

2009: list_sort 도입

Don Mullis가 lib/list_sort.c를 추가했습니다. 연결 리스트 전용 안정 정렬을 제공하며, 배열 변환 없이 O(1) 공간으로 안정 정렬을 보장합니다.

2019: Spelvin 대개편

주요 커밋: 0b067d8c012a ("lib/sort: make swap functions more generic"), 6a91d41cd8c6 ("lib/sort: use bottom-up heapsort variant"), 043b3f7b6388 ("lib/list_sort: simplify and remove MAX_LIST_LENGTH_BITS"). 비교 횟수 최적화와 swap 전략 자동 선택을 통해 sort() 비교 횟수를 25% 감소시키고, list_sort()를 이론 최적에 근접시켰습니다.

2022+: min_heap 통합

min_heap.h 매크로 API를 도입하여 힙 기반 우선순위 큐를 커널 전역에서 재사용할 수 있게 했습니다. timer, perf, kprobes에서 중복 힙 구현을 제거했습니다.

참고자료

• 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) 추가 메모리 병합 정렬의 학술적 배경입니다