Is there a function similar to qsort() to be used in kernel space?

Question

I'm writing a loadable kernel module and I need to use the function qsort() which apparently cannot be used in kernel space.

Is there a function that I can use that has a similar functionality ?

(Kernel version 3.5.0)

Answer 1

The linux kernel includes an implementation of heapsort which performs similar to quicksort. The kernel developers recommend heapsort over quicksort (within the kernel) and give the following rationale:

Sorting time [of heapsort] is O(n log n) both on average and worst-case. While qsort is about 20% faster on average, it suffers from exploitable O(n*n) worst-case behavior and extra memory requirements that make it less suitable for kernel use.

Header

#include <linux/sort.h>

Prototype

void sort(
    void *base, size_t num, size_t size,
    int (*cmp_func)(const void *, const void *),
    void (*swap_func)(void *, void *, int size));

Usage

static int compare(const void *lhs, const void *rhs) {
    int lhs_integer = *(const int *)(lhs);
    int rhs_integer = *(const int *)(rhs);

    if (lhs_integer < rhs_integer) return -1;
    if (lhs_integer > rhs_integer) return 1;
    return 0;
}

void example() {
    int values[1024] = {...};
    sort(values, 1024, sizeof(int), &compare, NULL);
}

Answer 2

That's a good question. The functionsort() in lib/sort.c does the job, but it's a heap sort, you can learn more about this choice in lib/sort.c