Greg Kroah-Hartman | b244131 | 2017-11-01 15:07:57 +0100 | [diff] [blame] | 1 | // SPDX-License-Identifier: GPL-2.0 |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 2 | /* |
George Spelvin | 22a241c | 2019-05-14 15:42:52 -0700 | [diff] [blame] | 3 | * A fast, small, non-recursive O(n log n) sort for the Linux kernel |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 4 | * |
George Spelvin | 22a241c | 2019-05-14 15:42:52 -0700 | [diff] [blame] | 5 | * This performs n*log2(n) + 0.37*n + o(n) comparisons on average, |
| 6 | * and 1.5*n*log2(n) + O(n) in the (very contrived) worst case. |
| 7 | * |
| 8 | * Glibc qsort() manages n*log2(n) - 1.26*n for random inputs (1.63*n |
| 9 | * better) at the expense of stack usage and much larger code to avoid |
| 10 | * quicksort's O(n^2) worst case. |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 11 | */ |
| 12 | |
Kostenzer Felix | c5adae9 | 2017-02-24 15:01:07 -0800 | [diff] [blame] | 13 | #define pr_fmt(fmt) KBUILD_MODNAME ": " fmt |
| 14 | |
Rasmus Villemoes | 42cf809 | 2015-02-12 15:02:35 -0800 | [diff] [blame] | 15 | #include <linux/types.h> |
| 16 | #include <linux/export.h> |
Adrian Bunk | ecec4cb | 2005-09-10 00:26:59 -0700 | [diff] [blame] | 17 | #include <linux/sort.h> |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 18 | |
George Spelvin | 37d0ec3 | 2019-05-14 15:42:49 -0700 | [diff] [blame] | 19 | /** |
| 20 | * is_aligned - is this pointer & size okay for word-wide copying? |
| 21 | * @base: pointer to data |
| 22 | * @size: size of each element |
George Spelvin | 22a241c | 2019-05-14 15:42:52 -0700 | [diff] [blame] | 23 | * @align: required alignment (typically 4 or 8) |
George Spelvin | 37d0ec3 | 2019-05-14 15:42:49 -0700 | [diff] [blame] | 24 | * |
| 25 | * Returns true if elements can be copied using word loads and stores. |
| 26 | * The size must be a multiple of the alignment, and the base address must |
| 27 | * be if we do not have CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS. |
| 28 | * |
| 29 | * For some reason, gcc doesn't know to optimize "if (a & mask || b & mask)" |
| 30 | * to "if ((a | b) & mask)", so we do that by hand. |
| 31 | */ |
| 32 | __attribute_const__ __always_inline |
| 33 | static bool is_aligned(const void *base, size_t size, unsigned char align) |
Daniel Wagner | ca96ab8 | 2015-06-25 15:02:14 -0700 | [diff] [blame] | 34 | { |
George Spelvin | 37d0ec3 | 2019-05-14 15:42:49 -0700 | [diff] [blame] | 35 | unsigned char lsbits = (unsigned char)size; |
| 36 | |
| 37 | (void)base; |
| 38 | #ifndef CONFIG_HAVE_EFFICIENT_UNALIGNED_ACCESS |
| 39 | lsbits |= (unsigned char)(uintptr_t)base; |
| 40 | #endif |
| 41 | return (lsbits & (align - 1)) == 0; |
Daniel Wagner | ca96ab8 | 2015-06-25 15:02:14 -0700 | [diff] [blame] | 42 | } |
| 43 | |
George Spelvin | 37d0ec3 | 2019-05-14 15:42:49 -0700 | [diff] [blame] | 44 | /** |
| 45 | * swap_words_32 - swap two elements in 32-bit chunks |
Randy Dunlap | aa52619 | 2019-05-31 22:30:00 -0700 | [diff] [blame] | 46 | * @a: pointer to the first element to swap |
| 47 | * @b: pointer to the second element to swap |
| 48 | * @n: element size (must be a multiple of 4) |
George Spelvin | 37d0ec3 | 2019-05-14 15:42:49 -0700 | [diff] [blame] | 49 | * |
| 50 | * Exchange the two objects in memory. This exploits base+index addressing, |
| 51 | * which basically all CPUs have, to minimize loop overhead computations. |
| 52 | * |
| 53 | * For some reason, on x86 gcc 7.3.0 adds a redundant test of n at the |
Zhen Lei | 9dbbc3b | 2021-07-07 18:07:31 -0700 | [diff] [blame] | 54 | * bottom of the loop, even though the zero flag is still valid from the |
George Spelvin | 37d0ec3 | 2019-05-14 15:42:49 -0700 | [diff] [blame] | 55 | * subtract (since the intervening mov instructions don't alter the flags). |
| 56 | * Gcc 8.1.0 doesn't have that problem. |
| 57 | */ |
George Spelvin | 8fb583c | 2019-05-14 15:42:55 -0700 | [diff] [blame] | 58 | static void swap_words_32(void *a, void *b, size_t n) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 59 | { |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 60 | do { |
George Spelvin | 37d0ec3 | 2019-05-14 15:42:49 -0700 | [diff] [blame] | 61 | u32 t = *(u32 *)(a + (n -= 4)); |
| 62 | *(u32 *)(a + n) = *(u32 *)(b + n); |
| 63 | *(u32 *)(b + n) = t; |
| 64 | } while (n); |
| 65 | } |
| 66 | |
| 67 | /** |
| 68 | * swap_words_64 - swap two elements in 64-bit chunks |
Randy Dunlap | aa52619 | 2019-05-31 22:30:00 -0700 | [diff] [blame] | 69 | * @a: pointer to the first element to swap |
| 70 | * @b: pointer to the second element to swap |
| 71 | * @n: element size (must be a multiple of 8) |
George Spelvin | 37d0ec3 | 2019-05-14 15:42:49 -0700 | [diff] [blame] | 72 | * |
| 73 | * Exchange the two objects in memory. This exploits base+index |
| 74 | * addressing, which basically all CPUs have, to minimize loop overhead |
| 75 | * computations. |
| 76 | * |
| 77 | * We'd like to use 64-bit loads if possible. If they're not, emulating |
| 78 | * one requires base+index+4 addressing which x86 has but most other |
| 79 | * processors do not. If CONFIG_64BIT, we definitely have 64-bit loads, |
| 80 | * but it's possible to have 64-bit loads without 64-bit pointers (e.g. |
| 81 | * x32 ABI). Are there any cases the kernel needs to worry about? |
| 82 | */ |
George Spelvin | 8fb583c | 2019-05-14 15:42:55 -0700 | [diff] [blame] | 83 | static void swap_words_64(void *a, void *b, size_t n) |
George Spelvin | 37d0ec3 | 2019-05-14 15:42:49 -0700 | [diff] [blame] | 84 | { |
George Spelvin | 37d0ec3 | 2019-05-14 15:42:49 -0700 | [diff] [blame] | 85 | do { |
| 86 | #ifdef CONFIG_64BIT |
| 87 | u64 t = *(u64 *)(a + (n -= 8)); |
| 88 | *(u64 *)(a + n) = *(u64 *)(b + n); |
| 89 | *(u64 *)(b + n) = t; |
| 90 | #else |
| 91 | /* Use two 32-bit transfers to avoid base+index+4 addressing */ |
| 92 | u32 t = *(u32 *)(a + (n -= 4)); |
| 93 | *(u32 *)(a + n) = *(u32 *)(b + n); |
| 94 | *(u32 *)(b + n) = t; |
| 95 | |
| 96 | t = *(u32 *)(a + (n -= 4)); |
| 97 | *(u32 *)(a + n) = *(u32 *)(b + n); |
| 98 | *(u32 *)(b + n) = t; |
| 99 | #endif |
| 100 | } while (n); |
| 101 | } |
| 102 | |
| 103 | /** |
| 104 | * swap_bytes - swap two elements a byte at a time |
Randy Dunlap | aa52619 | 2019-05-31 22:30:00 -0700 | [diff] [blame] | 105 | * @a: pointer to the first element to swap |
| 106 | * @b: pointer to the second element to swap |
| 107 | * @n: element size |
George Spelvin | 37d0ec3 | 2019-05-14 15:42:49 -0700 | [diff] [blame] | 108 | * |
| 109 | * This is the fallback if alignment doesn't allow using larger chunks. |
| 110 | */ |
George Spelvin | 8fb583c | 2019-05-14 15:42:55 -0700 | [diff] [blame] | 111 | static void swap_bytes(void *a, void *b, size_t n) |
George Spelvin | 37d0ec3 | 2019-05-14 15:42:49 -0700 | [diff] [blame] | 112 | { |
George Spelvin | 37d0ec3 | 2019-05-14 15:42:49 -0700 | [diff] [blame] | 113 | do { |
| 114 | char t = ((char *)a)[--n]; |
| 115 | ((char *)a)[n] = ((char *)b)[n]; |
| 116 | ((char *)b)[n] = t; |
| 117 | } while (n); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 118 | } |
| 119 | |
George Spelvin | 8fb583c | 2019-05-14 15:42:55 -0700 | [diff] [blame] | 120 | /* |
| 121 | * The values are arbitrary as long as they can't be confused with |
| 122 | * a pointer, but small integers make for the smallest compare |
| 123 | * instructions. |
| 124 | */ |
Jiri Olsa | a0019cd | 2022-03-16 13:24:07 +0100 | [diff] [blame] | 125 | #define SWAP_WORDS_64 (swap_r_func_t)0 |
| 126 | #define SWAP_WORDS_32 (swap_r_func_t)1 |
| 127 | #define SWAP_BYTES (swap_r_func_t)2 |
| 128 | #define SWAP_WRAPPER (swap_r_func_t)3 |
| 129 | |
| 130 | struct wrapper { |
| 131 | cmp_func_t cmp; |
| 132 | swap_func_t swap; |
| 133 | }; |
George Spelvin | 8fb583c | 2019-05-14 15:42:55 -0700 | [diff] [blame] | 134 | |
| 135 | /* |
| 136 | * The function pointer is last to make tail calls most efficient if the |
| 137 | * compiler decides not to inline this function. |
| 138 | */ |
Jiri Olsa | a0019cd | 2022-03-16 13:24:07 +0100 | [diff] [blame] | 139 | static void do_swap(void *a, void *b, size_t size, swap_r_func_t swap_func, const void *priv) |
George Spelvin | 8fb583c | 2019-05-14 15:42:55 -0700 | [diff] [blame] | 140 | { |
Jiri Olsa | a0019cd | 2022-03-16 13:24:07 +0100 | [diff] [blame] | 141 | if (swap_func == SWAP_WRAPPER) { |
| 142 | ((const struct wrapper *)priv)->swap(a, b, (int)size); |
| 143 | return; |
| 144 | } |
| 145 | |
George Spelvin | 8fb583c | 2019-05-14 15:42:55 -0700 | [diff] [blame] | 146 | if (swap_func == SWAP_WORDS_64) |
| 147 | swap_words_64(a, b, size); |
| 148 | else if (swap_func == SWAP_WORDS_32) |
| 149 | swap_words_32(a, b, size); |
| 150 | else if (swap_func == SWAP_BYTES) |
| 151 | swap_bytes(a, b, size); |
| 152 | else |
Jiri Olsa | a0019cd | 2022-03-16 13:24:07 +0100 | [diff] [blame] | 153 | swap_func(a, b, (int)size, priv); |
George Spelvin | 8fb583c | 2019-05-14 15:42:55 -0700 | [diff] [blame] | 154 | } |
| 155 | |
Rasmus Villemoes | 4333fb9 | 2019-08-16 13:01:22 -0300 | [diff] [blame] | 156 | #define _CMP_WRAPPER ((cmp_r_func_t)0L) |
| 157 | |
Andy Shevchenko | 52ae533 | 2019-10-07 16:56:54 +0300 | [diff] [blame] | 158 | static int do_cmp(const void *a, const void *b, cmp_r_func_t cmp, const void *priv) |
Rasmus Villemoes | 4333fb9 | 2019-08-16 13:01:22 -0300 | [diff] [blame] | 159 | { |
| 160 | if (cmp == _CMP_WRAPPER) |
Jiri Olsa | a0019cd | 2022-03-16 13:24:07 +0100 | [diff] [blame] | 161 | return ((const struct wrapper *)priv)->cmp(a, b); |
Rasmus Villemoes | 4333fb9 | 2019-08-16 13:01:22 -0300 | [diff] [blame] | 162 | return cmp(a, b, priv); |
| 163 | } |
| 164 | |
Robert P. J. Day | 72fd4a3 | 2007-02-10 01:45:59 -0800 | [diff] [blame] | 165 | /** |
George Spelvin | 22a241c | 2019-05-14 15:42:52 -0700 | [diff] [blame] | 166 | * parent - given the offset of the child, find the offset of the parent. |
| 167 | * @i: the offset of the heap element whose parent is sought. Non-zero. |
| 168 | * @lsbit: a precomputed 1-bit mask, equal to "size & -size" |
| 169 | * @size: size of each element |
| 170 | * |
| 171 | * In terms of array indexes, the parent of element j = @i/@size is simply |
| 172 | * (j-1)/2. But when working in byte offsets, we can't use implicit |
| 173 | * truncation of integer divides. |
| 174 | * |
| 175 | * Fortunately, we only need one bit of the quotient, not the full divide. |
| 176 | * @size has a least significant bit. That bit will be clear if @i is |
| 177 | * an even multiple of @size, and set if it's an odd multiple. |
| 178 | * |
| 179 | * Logically, we're doing "if (i & lsbit) i -= size;", but since the |
| 180 | * branch is unpredictable, it's done with a bit of clever branch-free |
| 181 | * code instead. |
| 182 | */ |
| 183 | __attribute_const__ __always_inline |
| 184 | static size_t parent(size_t i, unsigned int lsbit, size_t size) |
| 185 | { |
| 186 | i -= size; |
| 187 | i -= size & -(i & lsbit); |
| 188 | return i / 2; |
| 189 | } |
| 190 | |
| 191 | /** |
Rasmus Villemoes | 4333fb9 | 2019-08-16 13:01:22 -0300 | [diff] [blame] | 192 | * sort_r - sort an array of elements |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 193 | * @base: pointer to data to sort |
| 194 | * @num: number of elements |
| 195 | * @size: size of each element |
Wu Fengguang | b53907c | 2009-01-07 18:09:11 -0800 | [diff] [blame] | 196 | * @cmp_func: pointer to comparison function |
| 197 | * @swap_func: pointer to swap function or NULL |
Rasmus Villemoes | 4333fb9 | 2019-08-16 13:01:22 -0300 | [diff] [blame] | 198 | * @priv: third argument passed to comparison function |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 199 | * |
George Spelvin | 37d0ec3 | 2019-05-14 15:42:49 -0700 | [diff] [blame] | 200 | * This function does a heapsort on the given array. You may provide |
| 201 | * a swap_func function if you need to do something more than a memory |
| 202 | * copy (e.g. fix up pointers or auxiliary data), but the built-in swap |
George Spelvin | 8fb583c | 2019-05-14 15:42:55 -0700 | [diff] [blame] | 203 | * avoids a slow retpoline and so is significantly faster. |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 204 | * |
| 205 | * Sorting time is O(n log n) both on average and worst-case. While |
George Spelvin | 22a241c | 2019-05-14 15:42:52 -0700 | [diff] [blame] | 206 | * quicksort is slightly faster on average, it suffers from exploitable |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 207 | * O(n*n) worst-case behavior and extra memory requirements that make |
| 208 | * it less suitable for kernel use. |
| 209 | */ |
Rasmus Villemoes | 4333fb9 | 2019-08-16 13:01:22 -0300 | [diff] [blame] | 210 | void sort_r(void *base, size_t num, size_t size, |
Andy Shevchenko | 52ae533 | 2019-10-07 16:56:54 +0300 | [diff] [blame] | 211 | cmp_r_func_t cmp_func, |
Jiri Olsa | a0019cd | 2022-03-16 13:24:07 +0100 | [diff] [blame] | 212 | swap_r_func_t swap_func, |
Rasmus Villemoes | 4333fb9 | 2019-08-16 13:01:22 -0300 | [diff] [blame] | 213 | const void *priv) |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 214 | { |
| 215 | /* pre-scale counters for performance */ |
George Spelvin | 22a241c | 2019-05-14 15:42:52 -0700 | [diff] [blame] | 216 | size_t n = num * size, a = (num/2) * size; |
| 217 | const unsigned int lsbit = size & -size; /* Used to find parent */ |
| 218 | |
| 219 | if (!a) /* num < 2 || size == 0 */ |
| 220 | return; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 221 | |
Jiri Olsa | a0019cd | 2022-03-16 13:24:07 +0100 | [diff] [blame] | 222 | /* called from 'sort' without swap function, let's pick the default */ |
| 223 | if (swap_func == SWAP_WRAPPER && !((struct wrapper *)priv)->swap) |
| 224 | swap_func = NULL; |
| 225 | |
Daniel Wagner | ca96ab8 | 2015-06-25 15:02:14 -0700 | [diff] [blame] | 226 | if (!swap_func) { |
George Spelvin | 37d0ec3 | 2019-05-14 15:42:49 -0700 | [diff] [blame] | 227 | if (is_aligned(base, size, 8)) |
George Spelvin | 8fb583c | 2019-05-14 15:42:55 -0700 | [diff] [blame] | 228 | swap_func = SWAP_WORDS_64; |
George Spelvin | 37d0ec3 | 2019-05-14 15:42:49 -0700 | [diff] [blame] | 229 | else if (is_aligned(base, size, 4)) |
George Spelvin | 8fb583c | 2019-05-14 15:42:55 -0700 | [diff] [blame] | 230 | swap_func = SWAP_WORDS_32; |
Daniel Wagner | ca96ab8 | 2015-06-25 15:02:14 -0700 | [diff] [blame] | 231 | else |
George Spelvin | 8fb583c | 2019-05-14 15:42:55 -0700 | [diff] [blame] | 232 | swap_func = SWAP_BYTES; |
Daniel Wagner | ca96ab8 | 2015-06-25 15:02:14 -0700 | [diff] [blame] | 233 | } |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 234 | |
George Spelvin | 22a241c | 2019-05-14 15:42:52 -0700 | [diff] [blame] | 235 | /* |
| 236 | * Loop invariants: |
| 237 | * 1. elements [a,n) satisfy the heap property (compare greater than |
| 238 | * all of their children), |
| 239 | * 2. elements [n,num*size) are sorted, and |
| 240 | * 3. a <= b <= c <= d <= n (whenever they are valid). |
| 241 | */ |
| 242 | for (;;) { |
| 243 | size_t b, c, d; |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 244 | |
George Spelvin | 22a241c | 2019-05-14 15:42:52 -0700 | [diff] [blame] | 245 | if (a) /* Building heap: sift down --a */ |
| 246 | a -= size; |
| 247 | else if (n -= size) /* Sorting: Extract root to --n */ |
Jiri Olsa | a0019cd | 2022-03-16 13:24:07 +0100 | [diff] [blame] | 248 | do_swap(base, base + n, size, swap_func, priv); |
George Spelvin | 22a241c | 2019-05-14 15:42:52 -0700 | [diff] [blame] | 249 | else /* Sort complete */ |
| 250 | break; |
| 251 | |
| 252 | /* |
| 253 | * Sift element at "a" down into heap. This is the |
| 254 | * "bottom-up" variant, which significantly reduces |
| 255 | * calls to cmp_func(): we find the sift-down path all |
| 256 | * the way to the leaves (one compare per level), then |
| 257 | * backtrack to find where to insert the target element. |
| 258 | * |
| 259 | * Because elements tend to sift down close to the leaves, |
| 260 | * this uses fewer compares than doing two per level |
| 261 | * on the way down. (A bit more than half as many on |
| 262 | * average, 3/4 worst-case.) |
| 263 | */ |
| 264 | for (b = a; c = 2*b + size, (d = c + size) < n;) |
Rasmus Villemoes | 4333fb9 | 2019-08-16 13:01:22 -0300 | [diff] [blame] | 265 | b = do_cmp(base + c, base + d, cmp_func, priv) >= 0 ? c : d; |
George Spelvin | 22a241c | 2019-05-14 15:42:52 -0700 | [diff] [blame] | 266 | if (d == n) /* Special case last leaf with no sibling */ |
| 267 | b = c; |
| 268 | |
| 269 | /* Now backtrack from "b" to the correct location for "a" */ |
Rasmus Villemoes | 4333fb9 | 2019-08-16 13:01:22 -0300 | [diff] [blame] | 270 | while (b != a && do_cmp(base + a, base + b, cmp_func, priv) >= 0) |
George Spelvin | 22a241c | 2019-05-14 15:42:52 -0700 | [diff] [blame] | 271 | b = parent(b, lsbit, size); |
| 272 | c = b; /* Where "a" belongs */ |
| 273 | while (b != a) { /* Shift it into place */ |
| 274 | b = parent(b, lsbit, size); |
Jiri Olsa | a0019cd | 2022-03-16 13:24:07 +0100 | [diff] [blame] | 275 | do_swap(base + b, base + c, size, swap_func, priv); |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 276 | } |
| 277 | } |
| 278 | } |
Rasmus Villemoes | 4333fb9 | 2019-08-16 13:01:22 -0300 | [diff] [blame] | 279 | EXPORT_SYMBOL(sort_r); |
| 280 | |
| 281 | void sort(void *base, size_t num, size_t size, |
Andy Shevchenko | 52ae533 | 2019-10-07 16:56:54 +0300 | [diff] [blame] | 282 | cmp_func_t cmp_func, |
| 283 | swap_func_t swap_func) |
Rasmus Villemoes | 4333fb9 | 2019-08-16 13:01:22 -0300 | [diff] [blame] | 284 | { |
Jiri Olsa | a0019cd | 2022-03-16 13:24:07 +0100 | [diff] [blame] | 285 | struct wrapper w = { |
| 286 | .cmp = cmp_func, |
| 287 | .swap = swap_func, |
| 288 | }; |
| 289 | |
| 290 | return sort_r(base, num, size, _CMP_WRAPPER, SWAP_WRAPPER, &w); |
Rasmus Villemoes | 4333fb9 | 2019-08-16 13:01:22 -0300 | [diff] [blame] | 291 | } |
Linus Torvalds | 1da177e | 2005-04-16 15:20:36 -0700 | [diff] [blame] | 292 | EXPORT_SYMBOL(sort); |