forked from ~ljy/RK356X_SDK_RELEASE

blame | history | patch | commit | commitdiff
hc
2024-01-05 071106ecf68c401173c58808b1cf5f68cc50d390 
 kernel/tools/lib/rbtree.c
....@@ -1,30 +1,19 @@
1
+// SPDX-License-Identifier: GPL-2.0-or-later
12 /*
23   Red Black Trees
34   (C) 1999  Andrea Arcangeli <andrea@suse.de>
45   (C) 2002  David Woodhouse <dwmw2@infradead.org>
56   (C) 2012  Michel Lespinasse <walken@google.com>
67 
7
-  This program is free software; you can redistribute it and/or modify
8
-  it under the terms of the GNU General Public License as published by
9
-  the Free Software Foundation; either version 2 of the License, or
10
-  (at your option) any later version.
11
-
12
-  This program is distributed in the hope that it will be useful,
13
-  but WITHOUT ANY WARRANTY; without even the implied warranty of
14
-  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15
-  GNU General Public License for more details.
16
-
17
-  You should have received a copy of the GNU General Public License
18
-  along with this program; if not, write to the Free Software
19
-  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
208 
219   linux/lib/rbtree.c
2210 */
2311 
2412 #include <linux/rbtree_augmented.h>
13
+#include <linux/export.h>
2514 
2615 /*
27
- * red-black trees properties:  http://en.wikipedia.org/wiki/Rbtree
16
+ * red-black trees properties:  https://en.wikipedia.org/wiki/Rbtree
2817  *
2918  *  1) A node is either red or black
3019  *  2) The root is black
....@@ -41,6 +30,30 @@
4130  *  We shall indicate color with case, where black nodes are uppercase and red
4231  *  nodes will be lowercase. Unknown color nodes shall be drawn as red within
4332  *  parentheses and have some accompanying text comment.
33
+ */
34
+
35
+/*
36
+ * Notes on lockless lookups:
37
+ *
38
+ * All stores to the tree structure (rb_left and rb_right) must be done using
39
+ * WRITE_ONCE(). And we must not inadvertently cause (temporary) loops in the
40
+ * tree structure as seen in program order.
41
+ *
42
+ * These two requirements will allow lockless iteration of the tree -- not
43
+ * correct iteration mind you, tree rotations are not atomic so a lookup might
44
+ * miss entire subtrees.
45
+ *
46
+ * But they do guarantee that any such traversal will only see valid elements
47
+ * and that it will indeed complete -- does not get stuck in a loop.
48
+ *
49
+ * It also guarantees that if the lookup returns an element it is the 'correct'
50
+ * one. But not returning an element does _NOT_ mean it's not present.
51
+ *
52
+ * NOTE:
53
+ *
54
+ * Stores to __rb_parent_color are not important for simple lookups so those
55
+ * are left undone as of now. Nor did I check for loops involving parent
56
+ * pointers.
4457  */
4558 
4659 static inline void rb_set_black(struct rb_node *rb)
....@@ -76,16 +89,25 @@
7689 
7790 	while (true) {
7891 		/*
79
-		 * Loop invariant: node is red
80
-		 *
81
-		 * If there is a black parent, we are done.
82
-		 * Otherwise, take some corrective action as we don't
83
-		 * want a red root or two consecutive red nodes.
92
+		 * Loop invariant: node is red.
8493 		 */
85
-		if (!parent) {
94
+		if (unlikely(!parent)) {
95
+			/*
96
+			 * The inserted node is root. Either this is the
97
+			 * first node, or we recursed at Case 1 below and
98
+			 * are no longer violating 4).
99
+			 */
86100 			rb_set_parent_color(node, NULL, RB_BLACK);
87101 			break;
88
-		} else if (rb_is_black(parent))
102
+		}
103
+
104
+		/*
105
+		 * If there is a black parent, we are done.
106
+		 * Otherwise, take some corrective action as,
107
+		 * per 4), we don't want a red root or two
108
+		 * consecutive red nodes.
109
+		 */
110
+		if(rb_is_black(parent))
89111 			break;
90112 
91113 		gparent = rb_red_parent(parent);
....@@ -94,7 +116,7 @@
94116 		if (parent != tmp) {	/* parent == gparent->rb_left */
95117 			if (tmp && rb_is_red(tmp)) {
96118 				/*
97
-				 * Case 1 - color flips
119
+				 * Case 1 - node's uncle is red (color flips).
98120 				 *
99121 				 *       G            g
100122 				 *      / \          / \
....@@ -117,7 +139,8 @@
117139 			tmp = parent->rb_right;
118140 			if (node == tmp) {
119141 				/*
120
-				 * Case 2 - left rotate at parent
142
+				 * Case 2 - node's uncle is black and node is
143
+				 * the parent's right child (left rotate at parent).
121144 				 *
122145 				 *      G             G
123146 				 *     / \           / \
....@@ -128,8 +151,9 @@
128151 				 * This still leaves us in violation of 4), the
129152 				 * continuation into Case 3 will fix that.
130153 				 */
131
-				parent->rb_right = tmp = node->rb_left;
132
-				node->rb_left = parent;
154
+				tmp = node->rb_left;
155
+				WRITE_ONCE(parent->rb_right, tmp);
156
+				WRITE_ONCE(node->rb_left, parent);
133157 				if (tmp)
134158 					rb_set_parent_color(tmp, parent,
135159 							    RB_BLACK);
....@@ -140,7 +164,8 @@
140164 			}
141165 
142166 			/*
143
-			 * Case 3 - right rotate at gparent
167
+			 * Case 3 - node's uncle is black and node is
168
+			 * the parent's left child (right rotate at gparent).
144169 			 *
145170 			 *        G           P
146171 			 *       / \         / \
....@@ -148,8 +173,8 @@
148173 			 *     /                 \
149174 			 *    n                   U
150175 			 */
151
-			gparent->rb_left = tmp;  /* == parent->rb_right */
152
-			parent->rb_right = gparent;
176
+			WRITE_ONCE(gparent->rb_left, tmp); /* == parent->rb_right */
177
+			WRITE_ONCE(parent->rb_right, gparent);
153178 			if (tmp)
154179 				rb_set_parent_color(tmp, gparent, RB_BLACK);
155180 			__rb_rotate_set_parents(gparent, parent, root, RB_RED);
....@@ -170,8 +195,9 @@
170195 			tmp = parent->rb_left;
171196 			if (node == tmp) {
172197 				/* Case 2 - right rotate at parent */
173
-				parent->rb_left = tmp = node->rb_right;
174
-				node->rb_right = parent;
198
+				tmp = node->rb_right;
199
+				WRITE_ONCE(parent->rb_left, tmp);
200
+				WRITE_ONCE(node->rb_right, parent);
175201 				if (tmp)
176202 					rb_set_parent_color(tmp, parent,
177203 							    RB_BLACK);
....@@ -182,8 +208,8 @@
182208 			}
183209 
184210 			/* Case 3 - left rotate at gparent */
185
-			gparent->rb_right = tmp;  /* == parent->rb_left */
186
-			parent->rb_left = gparent;
211
+			WRITE_ONCE(gparent->rb_right, tmp); /* == parent->rb_left */
212
+			WRITE_ONCE(parent->rb_left, gparent);
187213 			if (tmp)
188214 				rb_set_parent_color(tmp, gparent, RB_BLACK);
189215 			__rb_rotate_set_parents(gparent, parent, root, RB_RED);
....@@ -223,8 +249,9 @@
223249 				 *      / \         / \
224250 				 *     Sl  Sr      N   Sl
225251 				 */
226
-				parent->rb_right = tmp1 = sibling->rb_left;
227
-				sibling->rb_left = parent;
252
+				tmp1 = sibling->rb_left;
253
+				WRITE_ONCE(parent->rb_right, tmp1);
254
+				WRITE_ONCE(sibling->rb_left, parent);
228255 				rb_set_parent_color(tmp1, parent, RB_BLACK);
229256 				__rb_rotate_set_parents(parent, sibling, root,
230257 							RB_RED);
....@@ -268,15 +295,31 @@
268295 				 *
269296 				 *   (p)           (p)
270297 				 *   / \           / \
271
-				 *  N   S    -->  N   Sl
298
+				 *  N   S    -->  N   sl
272299 				 *     / \             \
273
-				 *    sl  Sr            s
300
+				 *    sl  Sr            S
274301 				 *                       \
275302 				 *                        Sr
303
+				 *
304
+				 * Note: p might be red, and then both
305
+				 * p and sl are red after rotation(which
306
+				 * breaks property 4). This is fixed in
307
+				 * Case 4 (in __rb_rotate_set_parents()
308
+				 *         which set sl the color of p
309
+				 *         and set p RB_BLACK)
310
+				 *
311
+				 *   (p)            (sl)
312
+				 *   / \            /  \
313
+				 *  N   sl   -->   P    S
314
+				 *       \        /      \
315
+				 *        S      N        Sr
316
+				 *         \
317
+				 *          Sr
276318 				 */
277
-				sibling->rb_left = tmp1 = tmp2->rb_right;
278
-				tmp2->rb_right = sibling;
279
-				parent->rb_right = tmp2;
319
+				tmp1 = tmp2->rb_right;
320
+				WRITE_ONCE(sibling->rb_left, tmp1);
321
+				WRITE_ONCE(tmp2->rb_right, sibling);
322
+				WRITE_ONCE(parent->rb_right, tmp2);
280323 				if (tmp1)
281324 					rb_set_parent_color(tmp1, sibling,
282325 							    RB_BLACK);
....@@ -296,8 +339,9 @@
296339 			 *        / \         / \
297340 			 *      (sl) sr      N  (sl)
298341 			 */
299
-			parent->rb_right = tmp2 = sibling->rb_left;
300
-			sibling->rb_left = parent;
342
+			tmp2 = sibling->rb_left;
343
+			WRITE_ONCE(parent->rb_right, tmp2);
344
+			WRITE_ONCE(sibling->rb_left, parent);
301345 			rb_set_parent_color(tmp1, sibling, RB_BLACK);
302346 			if (tmp2)
303347 				rb_set_parent(tmp2, parent);
....@@ -309,8 +353,9 @@
309353 			sibling = parent->rb_left;
310354 			if (rb_is_red(sibling)) {
311355 				/* Case 1 - right rotate at parent */
312
-				parent->rb_left = tmp1 = sibling->rb_right;
313
-				sibling->rb_right = parent;
356
+				tmp1 = sibling->rb_right;
357
+				WRITE_ONCE(parent->rb_left, tmp1);
358
+				WRITE_ONCE(sibling->rb_right, parent);
314359 				rb_set_parent_color(tmp1, parent, RB_BLACK);
315360 				__rb_rotate_set_parents(parent, sibling, root,
316361 							RB_RED);
....@@ -334,10 +379,11 @@
334379 					}
335380 					break;
336381 				}
337
-				/* Case 3 - right rotate at sibling */
338
-				sibling->rb_right = tmp1 = tmp2->rb_left;
339
-				tmp2->rb_left = sibling;
340
-				parent->rb_left = tmp2;
382
+				/* Case 3 - left rotate at sibling */
383
+				tmp1 = tmp2->rb_left;
384
+				WRITE_ONCE(sibling->rb_right, tmp1);
385
+				WRITE_ONCE(tmp2->rb_left, sibling);
386
+				WRITE_ONCE(parent->rb_left, tmp2);
341387 				if (tmp1)
342388 					rb_set_parent_color(tmp1, sibling,
343389 							    RB_BLACK);
....@@ -345,9 +391,10 @@
345391 				tmp1 = sibling;
346392 				sibling = tmp2;
347393 			}
348
-			/* Case 4 - left rotate at parent + color flips */
349
-			parent->rb_left = tmp2 = sibling->rb_right;
350
-			sibling->rb_right = parent;
394
+			/* Case 4 - right rotate at parent + color flips */
395
+			tmp2 = sibling->rb_right;
396
+			WRITE_ONCE(parent->rb_left, tmp2);
397
+			WRITE_ONCE(sibling->rb_right, parent);
351398 			rb_set_parent_color(tmp1, sibling, RB_BLACK);
352399 			if (tmp2)
353400 				rb_set_parent(tmp2, parent);
....@@ -378,7 +425,9 @@
378425 static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {}
379426 
380427 static const struct rb_augment_callbacks dummy_callbacks = {
381
-	dummy_propagate, dummy_copy, dummy_rotate
428
+	.propagate = dummy_propagate,
429
+	.copy = dummy_copy,
430
+	.rotate = dummy_rotate
382431 };
383432 
384433 void rb_insert_color(struct rb_node *node, struct rb_root *root)
....@@ -448,7 +497,7 @@
448497 	if (node->rb_right) {
449498 		node = node->rb_right;
450499 		while (node->rb_left)
451
-			node=node->rb_left;
500
+			node = node->rb_left;
452501 		return (struct rb_node *)node;
453502 	}
454503 
....@@ -479,7 +528,7 @@
479528 	if (node->rb_left) {
480529 		node = node->rb_left;
481530 		while (node->rb_right)
482
-			node=node->rb_right;
531
+			node = node->rb_right;
483532 		return (struct rb_node *)node;
484533 	}
485534 
....@@ -498,15 +547,15 @@
498547 {
499548 	struct rb_node *parent = rb_parent(victim);
500549 
550
+	/* Copy the pointers/colour from the victim to the replacement */
551
+	*new = *victim;
552
+
501553 	/* Set the surrounding nodes to point to the replacement */
502
-	__rb_change_child(victim, new, parent, root);
503554 	if (victim->rb_left)
504555 		rb_set_parent(victim->rb_left, new);
505556 	if (victim->rb_right)
506557 		rb_set_parent(victim->rb_right, new);
507
-
508
-	/* Copy the pointers/colour from the victim to the replacement */
509
-	*new = *victim;
558
+	__rb_change_child(victim, new, parent, root);
510559 }
511560 
512561 static struct rb_node *rb_left_deepest_node(const struct rb_node *node)