移去rt

hc

2023-12-08 01573e231f18eb2d99162747186f59511f56b64d

 kernel/lib/list_sort.c
..
..
@@ -7,33 +7,41 @@
7
7
 #include <linux/list_sort.h>
8
8
 #include <linux/list.h>
9
9
 
10
-#define MAX_LIST_LENGTH_BITS 20
10
+typedef int __attribute__((nonnull(2,3))) (*cmp_func)(void *,
11
+		struct list_head *, struct list_head *);
11
12
 
12
13
 /*
13
14
  * Returns a list organized in an intermediate format suited
14
15
  * to chaining of merge() calls: null-terminated, no reserved or
15
16
  * sentinel head node, "prev" links not maintained.
16
17
  */
17
-static struct list_head *merge(void *priv,
18
-				int (*cmp)(void *priv, struct list_head *a,
19
-					struct list_head *b),
18
+__attribute__((nonnull(2,3,4)))
19
+static struct list_head *merge(void *priv, cmp_func cmp,
20
20
 				struct list_head *a, struct list_head *b)
21
21
 {
22
-	struct list_head head, *tail = &head;
22
+	struct list_head *head, **tail = &head;
23
23
 
24
-	while (a && b) {
24
+	for (;;) {
25
25
 		/* if equal, take 'a' -- important for sort stability */
26
-		if ((*cmp)(priv, a, b) <= 0) {
27
-			tail->next = a;
26
+		if (cmp(priv, a, b) <= 0) {
27
+			*tail = a;
28
+			tail = &a->next;
28
29
 			a = a->next;
30
+			if (!a) {
31
+				*tail = b;
32
+				break;
33
+			}
29
34
 		} else {
30
-			tail->next = b;
35
+			*tail = b;
36
+			tail = &b->next;
31
37
 			b = b->next;
38
+			if (!b) {
39
+				*tail = a;
40
+				break;
41
+			}
32
42
 		}
33
-		tail = tail->next;
34
43
 	}
35
-	tail->next = a?:b;
36
-	return head.next;
44
+	return head;
37
45
 }
38
46
 
39
47
 /*
..
..
@@ -43,44 +51,52 @@
43
51
  * prev-link restoration pass, or maintaining the prev links
44
52
  * throughout.
45
53
  */
46
-static void merge_and_restore_back_links(void *priv,
47
-				int (*cmp)(void *priv, struct list_head *a,
48
-					struct list_head *b),
49
-				struct list_head *head,
50
-				struct list_head *a, struct list_head *b)
54
+__attribute__((nonnull(2,3,4,5)))
55
+static void merge_final(void *priv, cmp_func cmp, struct list_head *head,
56
+			struct list_head *a, struct list_head *b)
51
57
 {
52
58
 	struct list_head *tail = head;
53
59
 	u8 count = 0;
54
60
 
55
-	while (a && b) {
61
+	for (;;) {
56
62
 		/* if equal, take 'a' -- important for sort stability */
57
-		if ((*cmp)(priv, a, b) <= 0) {
63
+		if (cmp(priv, a, b) <= 0) {
58
64
 			tail->next = a;
59
65
 			a->prev = tail;
66
+			tail = a;
60
67
 			a = a->next;
68
+			if (!a)
69
+				break;
61
70
 		} else {
62
71
 			tail->next = b;
63
72
 			b->prev = tail;
73
+			tail = b;
64
74
 			b = b->next;
75
+			if (!b) {
76
+				b = a;
77
+				break;
78
+			}
65
79
 		}
66
-		tail = tail->next;
67
80
 	}
68
-	tail->next = a ? : b;
69
81
 
82
+	/* Finish linking remainder of list b on to tail */
83
+	tail->next = b;
70
84
 	do {
71
85
 		/*
72
-		 * In worst cases this loop may run many iterations.
86
+		 * If the merge is highly unbalanced (e.g. the input is
87
+		 * already sorted), this loop may run many iterations.
73
88
 		 * Continue callbacks to the client even though no
74
89
 		 * element comparison is needed, so the client's cmp()
75
90
 		 * routine can invoke cond_resched() periodically.
76
91
 		 */
77
-		if (unlikely(!(++count)))
78
-			(*cmp)(priv, tail->next, tail->next);
92
+		if (unlikely(!++count))
93
+			cmp(priv, b, b);
94
+		b->prev = tail;
95
+		tail = b;
96
+		b = b->next;
97
+	} while (b);
79
98
 
80
-		tail->next->prev = tail;
81
-		tail = tail->next;
82
-	} while (tail->next);
83
-
99
+	/* And the final links to make a circular doubly-linked list */
84
100
 	tail->next = head;
85
101
 	head->prev = tail;
86
102
 }
..
..
@@ -91,55 +107,152 @@
91
107
  * @head: the list to sort
92
108
  * @cmp: the elements comparison function
93
109
  *
94
- * This function implements "merge sort", which has O(nlog(n))
95
- * complexity.
110
+ * The comparison funtion @cmp must return > 0 if @a should sort after
111
+ * @b ("@a > @b" if you want an ascending sort), and <= 0 if @a should
112
+ * sort before @b *or* their original order should be preserved.  It is
113
+ * always called with the element that came first in the input in @a,
114
+ * and list_sort is a stable sort, so it is not necessary to distinguish
115
+ * the @a < @b and @a == @b cases.
96
116
  *
97
- * The comparison function @cmp must return a negative value if @a
98
- * should sort before @b, and a positive value if @a should sort after
99
- * @b. If @a and @b are equivalent, and their original relative
100
- * ordering is to be preserved, @cmp must return 0.
117
+ * This is compatible with two styles of @cmp function:
118
+ * - The traditional style which returns <0 / =0 / >0, or
119
+ * - Returning a boolean 0/1.
120
+ * The latter offers a chance to save a few cycles in the comparison
121
+ * (which is used by e.g. plug_ctx_cmp() in block/blk-mq.c).
122
+ *
123
+ * A good way to write a multi-word comparison is::
124
+ *
125
+ *	if (a->high != b->high)
126
+ *		return a->high > b->high;
127
+ *	if (a->middle != b->middle)
128
+ *		return a->middle > b->middle;
129
+ *	return a->low > b->low;
130
+ *
131
+ *
132
+ * This mergesort is as eager as possible while always performing at least
133
+ * 2:1 balanced merges.  Given two pending sublists of size 2^k, they are
134
+ * merged to a size-2^(k+1) list as soon as we have 2^k following elements.
135
+ *
136
+ * Thus, it will avoid cache thrashing as long as 3*2^k elements can
137
+ * fit into the cache.  Not quite as good as a fully-eager bottom-up
138
+ * mergesort, but it does use 0.2*n fewer comparisons, so is faster in
139
+ * the common case that everything fits into L1.
140
+ *
141
+ *
142
+ * The merging is controlled by "count", the number of elements in the
143
+ * pending lists.  This is beautiully simple code, but rather subtle.
144
+ *
145
+ * Each time we increment "count", we set one bit (bit k) and clear
146
+ * bits k-1 .. 0.  Each time this happens (except the very first time
147
+ * for each bit, when count increments to 2^k), we merge two lists of
148
+ * size 2^k into one list of size 2^(k+1).
149
+ *
150
+ * This merge happens exactly when the count reaches an odd multiple of
151
+ * 2^k, which is when we have 2^k elements pending in smaller lists,
152
+ * so it's safe to merge away two lists of size 2^k.
153
+ *
154
+ * After this happens twice, we have created two lists of size 2^(k+1),
155
+ * which will be merged into a list of size 2^(k+2) before we create
156
+ * a third list of size 2^(k+1), so there are never more than two pending.
157
+ *
158
+ * The number of pending lists of size 2^k is determined by the
159
+ * state of bit k of "count" plus two extra pieces of information:
160
+ *
161
+ * - The state of bit k-1 (when k == 0, consider bit -1 always set), and
162
+ * - Whether the higher-order bits are zero or non-zero (i.e.
163
+ *   is count >= 2^(k+1)).
164
+ *
165
+ * There are six states we distinguish.  "x" represents some arbitrary
166
+ * bits, and "y" represents some arbitrary non-zero bits:
167
+ * 0:  00x: 0 pending of size 2^k;           x pending of sizes < 2^k
168
+ * 1:  01x: 0 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
169
+ * 2: x10x: 0 pending of size 2^k; 2^k     + x pending of sizes < 2^k
170
+ * 3: x11x: 1 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
171
+ * 4: y00x: 1 pending of size 2^k; 2^k     + x pending of sizes < 2^k
172
+ * 5: y01x: 2 pending of size 2^k; 2^(k-1) + x pending of sizes < 2^k
173
+ * (merge and loop back to state 2)
174
+ *
175
+ * We gain lists of size 2^k in the 2->3 and 4->5 transitions (because
176
+ * bit k-1 is set while the more significant bits are non-zero) and
177
+ * merge them away in the 5->2 transition.  Note in particular that just
178
+ * before the 5->2 transition, all lower-order bits are 11 (state 3),
179
+ * so there is one list of each smaller size.
180
+ *
181
+ * When we reach the end of the input, we merge all the pending
182
+ * lists, from smallest to largest.  If you work through cases 2 to
183
+ * 5 above, you can see that the number of elements we merge with a list
184
+ * of size 2^k varies from 2^(k-1) (cases 3 and 5 when x == 0) to
185
+ * 2^(k+1) - 1 (second merge of case 5 when x == 2^(k-1) - 1).
101
186
  */
187
+__attribute__((nonnull(2,3)))
102
188
 void list_sort(void *priv, struct list_head *head,
103
189
 		int (*cmp)(void *priv, struct list_head *a,
104
190
 			struct list_head *b))
105
191
 {
106
-	struct list_head *part[MAX_LIST_LENGTH_BITS+1]; /* sorted partial lists
107
-						-- last slot is a sentinel */
108
-	int lev;  /* index into part[] */
109
-	int max_lev = 0;
110
-	struct list_head *list;
192
+	struct list_head *list = head->next, *pending = NULL;
193
+	size_t count = 0;	/* Count of pending */
111
194
 
112
-	if (list_empty(head))
195
+	if (list == head->prev)	/* Zero or one elements */
113
196
 		return;
114
197
 
115
-	memset(part, 0, sizeof(part));
116
-
198
+	/* Convert to a null-terminated singly-linked list. */
117
199
 	head->prev->next = NULL;
118
-	list = head->next;
119
200
 
120
-	while (list) {
121
-		struct list_head *cur = list;
201
+	/*
202
+	 * Data structure invariants:
203
+	 * - All lists are singly linked and null-terminated; prev
204
+	 *   pointers are not maintained.
205
+	 * - pending is a prev-linked "list of lists" of sorted
206
+	 *   sublists awaiting further merging.
207
+	 * - Each of the sorted sublists is power-of-two in size.
208
+	 * - Sublists are sorted by size and age, smallest & newest at front.
209
+	 * - There are zero to two sublists of each size.
210
+	 * - A pair of pending sublists are merged as soon as the number
211
+	 *   of following pending elements equals their size (i.e.
212
+	 *   each time count reaches an odd multiple of that size).
213
+	 *   That ensures each later final merge will be at worst 2:1.
214
+	 * - Each round consists of:
215
+	 *   - Merging the two sublists selected by the highest bit
216
+	 *     which flips when count is incremented, and
217
+	 *   - Adding an element from the input as a size-1 sublist.
218
+	 */
219
+	do {
220
+		size_t bits;
221
+		struct list_head **tail = &pending;
222
+
223
+		/* Find the least-significant clear bit in count */
224
+		for (bits = count; bits & 1; bits >>= 1)
225
+			tail = &(*tail)->prev;
226
+		/* Do the indicated merge */
227
+		if (likely(bits)) {
228
+			struct list_head *a = *tail, *b = a->prev;
229
+
230
+			a = merge(priv, cmp, b, a);
231
+			/* Install the merged result in place of the inputs */
232
+			a->prev = b->prev;
233
+			*tail = a;
234
+		}
235
+
236
+		/* Move one element from input list to pending */
237
+		list->prev = pending;
238
+		pending = list;
122
239
 		list = list->next;
123
-		cur->next = NULL;
240
+		pending->next = NULL;
241
+		count++;
242
+	} while (list);
124
243
 
125
-		for (lev = 0; part[lev]; lev++) {
126
-			cur = merge(priv, cmp, part[lev], cur);
127
-			part[lev] = NULL;
128
-		}
129
-		if (lev > max_lev) {
130
-			if (unlikely(lev >= ARRAY_SIZE(part)-1)) {
131
-				printk_once(KERN_DEBUG "list too long for efficiency\n");
132
-				lev--;
133
-			}
134
-			max_lev = lev;
135
-		}
136
-		part[lev] = cur;
244
+	/* End of input; merge together all the pending lists. */
245
+	list = pending;
246
+	pending = pending->prev;
247
+	for (;;) {
248
+		struct list_head *next = pending->prev;
249
+
250
+		if (!next)
251
+			break;
252
+		list = merge(priv, cmp, pending, list);
253
+		pending = next;
137
254
 	}
138
-
139
-	for (lev = 0; lev < max_lev; lev++)
140
-		if (part[lev])
141
-			list = merge(priv, cmp, part[lev], list);
142
-
143
-	merge_and_restore_back_links(priv, cmp, head, part[max_lev], list);
255
+	/* The final merge, rebuilding prev links */
256
+	merge_final(priv, cmp, head, pending, list);
144
257
 }
145
258
 EXPORT_SYMBOL(list_sort);