[TOC]

lib/sort.c 通用的排序库(Generic Sorting Library) 为内核提供标准的、高效的排序功能

历史与背景

这项技术是为了解决什么特定问题而诞生的？

lib/sort.c 是为了解决一个在大型软件项目中普遍存在的问题——代码重复——而诞生的。在内核的各个子系统和驱动程序中，经常需要对一组数据进行排序。例如，根据优先级对任务进行排序、根据内存地址对设备资源进行排序等。

在lib/sort.c这个通用库出现之前，各个子系统可能会：

  • 实现自己的、简陋的排序算法（如冒泡排序、插入排序）。
  • 从其他地方复制粘贴一个更高效的排序算法（如快速排序）的实现。

这两种做法都导致了严重的问题：代码库中充满了功能相同但实现各异的排序代码，这不仅增加了内核的体积，也使得bug修复和性能优化变得极其困难。lib/sort.c的诞生，就是为了提供一个单一的、经过充分测试的、高性能的、通用的排序实现，供整个内核使用，从而消除代码重复，并保证排序操作的质量和效率。

它的发展经历了哪些重要的里程碑或版本迭代？

lib/sort.c的核心是提供一个与标准C库qsort()函数接口兼容的sort()函数。其发展主要体现在其底层排序算法的选择和优化上，以追求在各种数据模式下的稳定高性能：

  • 基于快速排序（Quicksort）：最初的实现和其接口的设计都深受快速排序的影响。快速排序在平均情况下的性能非常好（O(n log n)），实现也相对简单。
  • 引入内省排序（Introsort）：单纯的快速排序存在一个致命弱点：在最坏情况下（例如，对一个已经有序或逆序的数组进行排序），其性能会退化到O(n²)。为了解决这个问题，内核的sort()实现采用了内省排序策略。这是一种混合排序算法：
    1. 它以快速排序开始。
    2. 它会监控快速排序的递归深度。如果递归深度超过某个阈值（通常是2*log(n)），就意味着排序可能正在进入最坏情况。
    3. 此时，算法会切换到堆排序（Heapsort）。堆排序的最坏时间复杂度始终是O(n log n)，从而保证了整体性能不会退化。
    4. 当快速排序处理的分区变得非常小时（例如，少于16个元素），算法会切换到插入排序（Insertion Sort），因为对于小规模的数据，插入排序的开销更小，速度更快。

这种混合策略使得内核的sort()函数兼具了快速排序的平均性能和堆排序的最坏情况性能保证。

目前该技术的社区活跃度和主流应用情况如何？

lib/sort.c是内核中一个极其稳定和基础的库，已经完全融入到内核的日常开发中。它不是一个经常需要修改和添加新功能的组件，但它被内核中几乎所有需要对**连续内存数据块（数组）**进行排序的地方广泛使用。

  • 设备探测：在PCI或USB总线初始化时，可能会对扫描到的设备列表进行排序，以保证一个确定的探测顺序。
  • 内存管理：在打印系统内存映射（/proc/iomem）时，内核会使用sort()来根据资源的起始地址对内存区域进行排序。
  • 调试和追踪：一些调试工具在格式化输出前，会对其收集到的数据点进行排序。

核心原理与设计

它的核心工作原理是什么？

lib/sort.c的核心是一个名为sort()的函数，其接口设计如下：
void sort(void *base, size_t num, size_t size, int (*cmp)(const void *, const void *), void (*swap)(void *, void *, int size));

其工作原理是**泛型编程（Generic Programming）**思想的体现：

  1. 输入：它接受一个指向内存块起始位置的通用指针base，元素的数量num，以及每个元素的大小size。
  2. 比较逻辑的分离：sort()函数本身不知道如何比较两个元素的大小。它将这个任务委托给调用者提供的比较函数指针cmp。这个函数接收两个指向元素的指针，并返回一个负数、零或正数，分别表示第一个元素小于、等于还是大于第二个元素。
  3. 交换操作的分离：类似地，它使用一个swap函数指针来交换两个元素的位置。虽然库提供了一个默认的memmove-based交换函数，但允许调用者提供自定义的、可能更高效的交换实现。
  4. 算法执行：sort()的内部逻辑（如上所述的内省排序）完全基于cmp函数的结果来决定如何划分和移动元素，并通过swap函数来执行元素的移动。它通过指针算术（base + i * size）来定位到数组中的第i个元素。

通过这种方式，sort()可以对任何类型的、存储在连续内存中的数据结构进行排序，只要调用者能提供一个正确的比较函数。

它的主要优势体现在哪些方面？

  • 高性能：内省排序保证了在平均和最坏情况下的时间复杂度都是O(n log n)。
  • 通用性：可以对任何数据类型的数组进行排序。
  • 代码复用：提供了一个标准的、集中的实现，避免了代码冗余。
  • 健壮性：作为一个被广泛使用的核心库，其实现的正确性和稳定性得到了充分的验证。

它存在哪些已知的劣势、局限性或在特定场景下的不适用性？

  • 非稳定排序（Unstable Sort）：这是sort()最重要的一个特性。它不保证两个比较结果相等的元素的原始相对顺序。如果需要保持相等元素的顺序，那么这个函数不适用。
  • 只适用于连续内存（数组）：它的设计是基于可以随机访问的数组。对于链表等非连续的数据结构，使用sort()会非常低效甚至不可行。
  • 递归开销：由于其核心是快速排序，它会消耗一定的内核栈空间。对于在栈空间极其受限的上下文中对海量数据进行排序的极端情况，需要特别注意。
  • 同步操作：sort()是一个同步的、阻塞的函数。它会占用CPU直到排序完成。它不能在原子上下文中对大量数据进行排序。

使用场景

在哪些具体的业务或技术场景下，它是首选解决方案？

当内核代码需要对一个数组（或任何形式的连续内存块）中的元素进行就地（in-place）排序，并且不关心排序的稳定性时，lib/sort.c的sort()函数是首选解决方案。

  • 例一：驱动初始化
    一个多功能设备驱动在初始化时，发现该设备提供了多个功能块。驱动将这些功能块的信息读入一个结构体数组。为了按功能ID的顺序来初始化它们，驱动可以定义一个比较函数来比较两个结构体的ID字段，然后调用sort()对这个数组进行排序。
  • 例二：准备数据输出
    一个内核子系统需要通过debugfs向用户空间导出一组无序的统计信息。为了让输出更具可读性，它可以将统计信息放入一个数组，然后调用sort()根据名称或值进行排序，最后再格式化输出。

是否有不推荐使用该技术的场景？为什么？

  • 需要稳定排序：当相等元素的相对顺序很重要时（例如，按主键排序后，希望保持原始的次序），不应使用sort()。
  • 对链表进行排序：如果你的数据结构是通过struct list_head组织的链表，那么应该使用专门为链表设计的list_sort()。list_sort()位于lib/list_sort.c，它实现了归并排序，是稳定的，并且对链表操作更高效。

对比分析

请将其 与 其他相似技术 进行详细对比。

特性 lib/sort.c (sort) lib/list_sort.c (list_sort)
核心功能 对**连续内存（数组）**进行排序。 对**struct list_head链表**进行排序。
数据结构 void *base (指向数组头部) struct list_head *head (指向链表头部)
排序算法 内省排序 (快速排序/堆排序/插入排序的混合)。 归并排序 (Mergesort)。
稳定性 (Stability) 不稳定 (Unstable) 稳定 (Stable)
内存开销 就地排序，除了递归栈之外，几乎没有额外的内存开销。 归并排序需要将链表拆分和合并，有少量临时的指针开销，但不会分配新的链表节点。
性能 时间复杂度为O(n log n)。对于数组，缓存局部性更好。 时间复杂度为O(n log n)。对于链表，避免了大量的数据移动，只需修改指针。
典型用途 对结构体数组、指针数组等进行排序。 对内核中通过list_head管理的各种对象列表进行排序。
关键区别 处理数组，不稳定 处理链表，稳定

lib/sort.c

  • 采用堆排序

  • sort_nonatomic: 无原子性的排序

  • sort_r_nonatomic: 无原子性的排序,但是允许传入额外的上下文信息.如下方的priv参数传入

    1
    swap_func(a, b, (int)size, priv);

  • sort:原子性排序

  • sort_r:原子性排序,但是允许传入额外的上下文信息.如下方的priv参数传入

    1
    swap_func(a, b, (int)size, priv);

sort_r 对元素数组进行排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * sort_r - 对元素数组进行排序
 * @base：指向要排序的数据的指针
 * @num：元素数量
 * @size：每个元素的大小
 * @cmp_func：指向比较函数的指针
 * @swap_func：指向 swap 函数的指针或 NULL
 * @priv：传递给比较函数的第三个参数
 *
 * 此函数对给定的数组执行堆排序。 如果您需要做更多的事情（例如修复指针或辅助数据），您可以提供 swap_func 函数，但内置 swap 避免了慢速 retpoline，因此明显更快。
 *
 * 比较函数必须遵守特定的数学属性，以确保正确和稳定的排序：
 * - 反对称性：cmp_func（a， b） 必须返回 cmp_func（b， a） 的相反符号。
 * - 传递性：如果 cmp_func（a， b） <= 0 且 cmp_func（b， c） <= 0，则 cmp_func（a， c） <= 0。
 *
 * 平均和最坏情况下的排序时间为 O（n log n）。虽然快速排序平均速度略快，但它存在可利用的 O（n*n） 最坏情况行为和额外的内存要求，这使得它不太适合内核使用。
 */
  • 如果用户提供了自定义的 swap_func,每次调用都会通过间接分支跳转到用户定义的函数。这种间接调用会触发 Retpoline 的缓解机制，从而导致性能下降。
  • 为了避免这种开销，代码提供了内置的交换函数（如 swap_words_32、swap_words_64 和 swap_bytes）。这些内置函数是直接调用的，不涉及间接分支，因此不会触发 Retpoline 的机制，性能明显更高。

堆排序被选为内核中的排序算法，而不是快速排序

时间复杂度对比

  1. 堆排序：

    • 平均时间复杂度：O(n log n)。
    • 最坏时间复杂度：O(n log n)。
    • 堆排序的时间复杂度在所有情况下都保持一致，无论输入数据的分布如何。

  2. 快速排序：

    • 平均时间复杂度：O(n log n)。
    • 最坏时间复杂度：O(n^2)。
    • 快速排序的性能依赖于输入数据的分布。在某些特殊情况下（如输入数据接近有序），可能会退化为 O(n^2)。

快速排序的缺点

  1. 最坏情况行为：

    • 快速排序在最坏情况下的时间复杂度为 O(n^2)，这在内核中可能导致不可接受的性能问题。
    • 内核需要在所有情况下都能保证稳定的性能，因此快速排序的最坏情况行为使其不适合内核使用。

  2. 额外的内存需求：

    • 快速排序通常需要额外的栈空间来处理递归调用。
    • 在内核中，栈空间非常有限（通常只有几 KB），递归调用可能导致栈溢出，从而引发系统崩溃。

堆排序的优势

  1. 稳定的时间复杂度：

    • 堆排序的时间复杂度在平均和最坏情况下都为 O(n log n)，性能更加稳定。
    • 这种一致性非常适合内核中对实时性和可靠性的要求。

  2. 原地排序：

    • 堆排序是一种原地排序算法，除了输入数组本身外，不需要额外的内存空间。
    • 这对于内核中有限的内存资源来说是一个重要的优势。

  3. 非递归实现：

    • 堆排序可以通过循环实现，而不需要递归调用，从而避免了栈溢出的风险。

总结

虽然快速排序在平均情况下略快，但其最坏情况的性能退化和额外的内存需求使其不适合内核使用。相比之下，堆排序以其稳定的时间复杂度、低内存需求和非递归实现成为内核中排序算法的首选。这种设计选择体现了内核对性能稳定性和资源效率的高度重视。

parent 给定子项的偏移量，找到父项的偏移量

  • 在堆排序中，父节点和子节点的关系通常通过数组索引计算：如果子节点的索引是 j，则父节点的索引是 (j-1)/2。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * parent - 给定子项的偏移量，找到父项的偏移量。
 * @i：查找其父级的 heap 元素的偏移量。 非零。
 * @lsbit：一个预先计算的1位掩码，等于“size & -size”
 * @size：每个元素的大小
 *
 * 就数组索引而言，元素 j = @i/@size 的父级就是 （j-1）/2。 但是当使用 byte offsets 时，我们不能使用整数除法的隐式截断。
 *
 * 幸运的是，我们只需要一点商，而不是全部除法。@size 具有最低有效位。 如果 @i 是 @size 的偶数倍，则该位将很清楚，如果它是奇数倍数，则设置该位。
 *
 * 从逻辑上讲，我们正在做“if （i & lsbit） i -= size;”，但由于分支是不可预测的，所以它用了一些巧妙的无分支代码来完成。
 */
__attribute_const__ __always_inline
static size_t parent(size_t i, unsigned int lsbit, size_t size)
{
	//首先从子节点的偏移量 i 中减去一个元素的大小 size，这是因为在堆中，子节点的偏移量总是比父节点大至少一个元素的大小。
	i -= size;
	//i & lsbit：检查 i 是否是 size 的奇数倍。如果结果为 0，表示 i 是偶数倍；否则是奇数倍
	//-(i & lsbit)：将结果转换为掩码。如果 i & lsbit 为 0，则结果为 0；否则结果为全 1。
	//size & -(i & lsbit)：如果 i 是奇数倍，则减去 size；否则不减
	i -= size & -(i & lsbit);
	return i / 2;
}

__sort_r

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/*
 * 只要它们不能与指针混淆，这些值就是任意的，但小整数是最小的比较指令。
 */
#define SWAP_WORDS_64 (swap_r_func_t)0
#define SWAP_WORDS_32 (swap_r_func_t)1
#define SWAP_BYTES    (swap_r_func_t)2
#define SWAP_WRAPPER  (swap_r_func_t)3

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,
		     bool may_schedule)
{
	/* 用于性能的预缩放计数器 */
	size_t n = num * size, a = (num/2) * size;
	//最低有效位
	const unsigned int lsbit = size & -size;  /* 用于查找父级*/
	size_t shift = 0;

	if (!a)		/* num < 2 || size == 0 */
		return;

	/* 从 'sort' 调用，不带 swap 函数，让我们选择默认的 */
	if (swap_func == SWAP_WRAPPER && !((struct wrapper *)priv)->swap)
		swap_func = NULL;

	if (!swap_func) {
		if (is_aligned(base, size, 8))
			swap_func = SWAP_WORDS_64;
		else if (is_aligned(base, size, 4))
			swap_func = SWAP_WORDS_32;
		else
			swap_func = SWAP_BYTES;
	}

	/*
	 * 循环不变量：
	 * 1.元素 [a，n） 满足 heap 属性（比较大于它们的所有子项），
	 * 2.元素 [n，num*size） 进行排序，并且
	 * 3.a <= b <= c <= d <= n（只要它们有效）。
	 */
	for (;;) {
		size_t b, c, d;

		if (a)  //如果 a 不为零，表示当前需要调整堆的结构
			a -= size << shift;     //通过位移操作调整堆的范围，逐步向上筛选元素以维护堆的性质。
		else if (n > 3 * size) {    // 表示堆中还有足够的元素可以提取
			n -= size;
			do_swap(base, base + n, size, swap_func, priv); //将堆的最后一个元素（最大值）与当前范围的最后一个元素交换
			shift = do_cmp(base + size, base + 2 * size, cmp_func, priv) <= 0;  //通过比较（do_cmp）确定下一个需要调整的堆范围
			a = size << shift;
			n -= size;
			do_swap(base + a, base + n, size, swap_func, priv); //再次交换元素，将次大的元素放到正确的位置
		} else {		/* 排序完成 */
			break;
		}

		/*
		 * 将 “a” 处的元素筛选到堆中。 这是 “bottom-up” 变体，它大大减少了对 cmp_func（） 的调用：我们找到一直到叶子的筛选路径（每个级别一个比较），然后回溯以找到插入目标元素的位置。
		 *
		 * 因为元素倾向于在靠近叶子的地方向下筛选，所以这比在向下的过程中每层进行两次比较要少。 （平均数量略多于一半，最坏情况下为 3/4。
		 */
		//b 是当前正在筛选的节点，c 和 d 分别是其左子节点和右子节点的位置
		for (b = a; c = 2*b + size, (d = c + size) < n;)
		//使用 do_cmp() 比较左右子节点的值，选择较大的子节点作为下一步筛选的目标。
			b = do_cmp(base + c, base + d, cmp_func, priv) > 0 ? c : d;
		if (d == n)	/*特殊情况 只有左子节点*/
			b = c;

		/* 现在从 “b” 回溯到 “a” 的正确位置 */
		while (b != a && do_cmp(base + a, base + b, cmp_func, priv) >= 0)
			b = parent(b, lsbit, size);	//计算当前节点的父节点位置
		c = b;			//右子节点
		//调整b的值为c的右节点
		while (b != a) {	/* 将其移动到位 */
			b = parent(b, lsbit, size);
			do_swap(base + b, base + c, size, swap_func, priv);
		}

		if (may_schedule)
			cond_resched();
	}
	//将堆的范围缩小一个元素，表示当前堆的最后一个元素已经被移出堆。
	n -= size;
	//将堆的根节点（最大值）与堆的最后一个元素交换位置。这样，最大值被移到了堆的末尾，成为已排序部分的一部分。
	do_swap(base, base + n, size, swap_func, priv);
	//当堆中只剩下两个元素时，特殊处理是必要的，因为此时堆的性质已经无法通过正常的堆调整逻辑维护
	if (n == size * 2 && do_cmp(base, base + size, cmp_func, priv) > 0)	
		do_swap(base, base + size, size, swap_func, priv);	//如果根节点的值大于其子节点的值，则交换它们的位置。
}