aboutsummaryrefslogtreecommitdiffstats
path: root/tools/lib/rbtree.c
diff options
context:
space:
mode:
authorDavidlohr Bueso <dave@stgolabs.net>2018-12-06 14:18:13 -0500
committerArnaldo Carvalho de Melo <acme@redhat.com>2019-01-25 09:12:09 -0500
commit3aef2cad5d51ee66d2a614dd2f70cb34c74caf77 (patch)
treeb52f1d67040ec37a2268f91061d33fa6e38e20c6 /tools/lib/rbtree.c
parent95420d338e2d802ea0dce4d770d3292beb587f71 (diff)
tools: Update rbtree implementation
There have been a number of changes in the kernel's rbrtee implementation, including loose lockless searching guarantees and rb_root_cached, which later patches will use as an optimization. Signed-off-by: Davidlohr Bueso <dbueso@suse.de> Tested-by: Arnaldo Carvalho de Melo <acme@redhat.com> Cc: Jiri Olsa <jolsa@kernel.org> Cc: Namhyung Kim <namhyung@kernel.org> Link: http://lkml.kernel.org/r/20181206191819.30182-2-dave@stgolabs.net Signed-off-by: Arnaldo Carvalho de Melo <acme@redhat.com>
Diffstat (limited to 'tools/lib/rbtree.c')
-rw-r--r--tools/lib/rbtree.c178
1 files changed, 135 insertions, 43 deletions
diff --git a/tools/lib/rbtree.c b/tools/lib/rbtree.c
index 17c2b596f043..904adb70a4f0 100644
--- a/tools/lib/rbtree.c
+++ b/tools/lib/rbtree.c
@@ -22,6 +22,7 @@
22*/ 22*/
23 23
24#include <linux/rbtree_augmented.h> 24#include <linux/rbtree_augmented.h>
25#include <linux/export.h>
25 26
26/* 27/*
27 * red-black trees properties: http://en.wikipedia.org/wiki/Rbtree 28 * red-black trees properties: http://en.wikipedia.org/wiki/Rbtree
@@ -43,6 +44,30 @@
43 * parentheses and have some accompanying text comment. 44 * parentheses and have some accompanying text comment.
44 */ 45 */
45 46
47/*
48 * Notes on lockless lookups:
49 *
50 * All stores to the tree structure (rb_left and rb_right) must be done using
51 * WRITE_ONCE(). And we must not inadvertently cause (temporary) loops in the
52 * tree structure as seen in program order.
53 *
54 * These two requirements will allow lockless iteration of the tree -- not
55 * correct iteration mind you, tree rotations are not atomic so a lookup might
56 * miss entire subtrees.
57 *
58 * But they do guarantee that any such traversal will only see valid elements
59 * and that it will indeed complete -- does not get stuck in a loop.
60 *
61 * It also guarantees that if the lookup returns an element it is the 'correct'
62 * one. But not returning an element does _NOT_ mean it's not present.
63 *
64 * NOTE:
65 *
66 * Stores to __rb_parent_color are not important for simple lookups so those
67 * are left undone as of now. Nor did I check for loops involving parent
68 * pointers.
69 */
70
46static inline void rb_set_black(struct rb_node *rb) 71static inline void rb_set_black(struct rb_node *rb)
47{ 72{
48 rb->__rb_parent_color |= RB_BLACK; 73 rb->__rb_parent_color |= RB_BLACK;
@@ -70,22 +95,35 @@ __rb_rotate_set_parents(struct rb_node *old, struct rb_node *new,
70 95
71static __always_inline void 96static __always_inline void
72__rb_insert(struct rb_node *node, struct rb_root *root, 97__rb_insert(struct rb_node *node, struct rb_root *root,
98 bool newleft, struct rb_node **leftmost,
73 void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) 99 void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
74{ 100{
75 struct rb_node *parent = rb_red_parent(node), *gparent, *tmp; 101 struct rb_node *parent = rb_red_parent(node), *gparent, *tmp;
76 102
103 if (newleft)
104 *leftmost = node;
105
77 while (true) { 106 while (true) {
78 /* 107 /*
79 * Loop invariant: node is red 108 * 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.
84 */ 109 */
85 if (!parent) { 110 if (unlikely(!parent)) {
111 /*
112 * The inserted node is root. Either this is the
113 * first node, or we recursed at Case 1 below and
114 * are no longer violating 4).
115 */
86 rb_set_parent_color(node, NULL, RB_BLACK); 116 rb_set_parent_color(node, NULL, RB_BLACK);
87 break; 117 break;
88 } else if (rb_is_black(parent)) 118 }
119
120 /*
121 * If there is a black parent, we are done.
122 * Otherwise, take some corrective action as,
123 * per 4), we don't want a red root or two
124 * consecutive red nodes.
125 */
126 if(rb_is_black(parent))
89 break; 127 break;
90 128
91 gparent = rb_red_parent(parent); 129 gparent = rb_red_parent(parent);
@@ -94,7 +132,7 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
94 if (parent != tmp) { /* parent == gparent->rb_left */ 132 if (parent != tmp) { /* parent == gparent->rb_left */
95 if (tmp && rb_is_red(tmp)) { 133 if (tmp && rb_is_red(tmp)) {
96 /* 134 /*
97 * Case 1 - color flips 135 * Case 1 - node's uncle is red (color flips).
98 * 136 *
99 * G g 137 * G g
100 * / \ / \ 138 * / \ / \
@@ -117,7 +155,8 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
117 tmp = parent->rb_right; 155 tmp = parent->rb_right;
118 if (node == tmp) { 156 if (node == tmp) {
119 /* 157 /*
120 * Case 2 - left rotate at parent 158 * Case 2 - node's uncle is black and node is
159 * the parent's right child (left rotate at parent).
121 * 160 *
122 * G G 161 * G G
123 * / \ / \ 162 * / \ / \
@@ -128,8 +167,9 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
128 * This still leaves us in violation of 4), the 167 * This still leaves us in violation of 4), the
129 * continuation into Case 3 will fix that. 168 * continuation into Case 3 will fix that.
130 */ 169 */
131 parent->rb_right = tmp = node->rb_left; 170 tmp = node->rb_left;
132 node->rb_left = parent; 171 WRITE_ONCE(parent->rb_right, tmp);
172 WRITE_ONCE(node->rb_left, parent);
133 if (tmp) 173 if (tmp)
134 rb_set_parent_color(tmp, parent, 174 rb_set_parent_color(tmp, parent,
135 RB_BLACK); 175 RB_BLACK);
@@ -140,7 +180,8 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
140 } 180 }
141 181
142 /* 182 /*
143 * Case 3 - right rotate at gparent 183 * Case 3 - node's uncle is black and node is
184 * the parent's left child (right rotate at gparent).
144 * 185 *
145 * G P 186 * G P
146 * / \ / \ 187 * / \ / \
@@ -148,8 +189,8 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
148 * / \ 189 * / \
149 * n U 190 * n U
150 */ 191 */
151 gparent->rb_left = tmp; /* == parent->rb_right */ 192 WRITE_ONCE(gparent->rb_left, tmp); /* == parent->rb_right */
152 parent->rb_right = gparent; 193 WRITE_ONCE(parent->rb_right, gparent);
153 if (tmp) 194 if (tmp)
154 rb_set_parent_color(tmp, gparent, RB_BLACK); 195 rb_set_parent_color(tmp, gparent, RB_BLACK);
155 __rb_rotate_set_parents(gparent, parent, root, RB_RED); 196 __rb_rotate_set_parents(gparent, parent, root, RB_RED);
@@ -170,8 +211,9 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
170 tmp = parent->rb_left; 211 tmp = parent->rb_left;
171 if (node == tmp) { 212 if (node == tmp) {
172 /* Case 2 - right rotate at parent */ 213 /* Case 2 - right rotate at parent */
173 parent->rb_left = tmp = node->rb_right; 214 tmp = node->rb_right;
174 node->rb_right = parent; 215 WRITE_ONCE(parent->rb_left, tmp);
216 WRITE_ONCE(node->rb_right, parent);
175 if (tmp) 217 if (tmp)
176 rb_set_parent_color(tmp, parent, 218 rb_set_parent_color(tmp, parent,
177 RB_BLACK); 219 RB_BLACK);
@@ -182,8 +224,8 @@ __rb_insert(struct rb_node *node, struct rb_root *root,
182 } 224 }
183 225
184 /* Case 3 - left rotate at gparent */ 226 /* Case 3 - left rotate at gparent */
185 gparent->rb_right = tmp; /* == parent->rb_left */ 227 WRITE_ONCE(gparent->rb_right, tmp); /* == parent->rb_left */
186 parent->rb_left = gparent; 228 WRITE_ONCE(parent->rb_left, gparent);
187 if (tmp) 229 if (tmp)
188 rb_set_parent_color(tmp, gparent, RB_BLACK); 230 rb_set_parent_color(tmp, gparent, RB_BLACK);
189 __rb_rotate_set_parents(gparent, parent, root, RB_RED); 231 __rb_rotate_set_parents(gparent, parent, root, RB_RED);
@@ -223,8 +265,9 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
223 * / \ / \ 265 * / \ / \
224 * Sl Sr N Sl 266 * Sl Sr N Sl
225 */ 267 */
226 parent->rb_right = tmp1 = sibling->rb_left; 268 tmp1 = sibling->rb_left;
227 sibling->rb_left = parent; 269 WRITE_ONCE(parent->rb_right, tmp1);
270 WRITE_ONCE(sibling->rb_left, parent);
228 rb_set_parent_color(tmp1, parent, RB_BLACK); 271 rb_set_parent_color(tmp1, parent, RB_BLACK);
229 __rb_rotate_set_parents(parent, sibling, root, 272 __rb_rotate_set_parents(parent, sibling, root,
230 RB_RED); 273 RB_RED);
@@ -268,15 +311,31 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
268 * 311 *
269 * (p) (p) 312 * (p) (p)
270 * / \ / \ 313 * / \ / \
271 * N S --> N Sl 314 * N S --> N sl
272 * / \ \ 315 * / \ \
273 * sl Sr s 316 * sl Sr S
274 * \ 317 * \
275 * Sr 318 * Sr
319 *
320 * Note: p might be red, and then both
321 * p and sl are red after rotation(which
322 * breaks property 4). This is fixed in
323 * Case 4 (in __rb_rotate_set_parents()
324 * which set sl the color of p
325 * and set p RB_BLACK)
326 *
327 * (p) (sl)
328 * / \ / \
329 * N sl --> P S
330 * \ / \
331 * S N Sr
332 * \
333 * Sr
276 */ 334 */
277 sibling->rb_left = tmp1 = tmp2->rb_right; 335 tmp1 = tmp2->rb_right;
278 tmp2->rb_right = sibling; 336 WRITE_ONCE(sibling->rb_left, tmp1);
279 parent->rb_right = tmp2; 337 WRITE_ONCE(tmp2->rb_right, sibling);
338 WRITE_ONCE(parent->rb_right, tmp2);
280 if (tmp1) 339 if (tmp1)
281 rb_set_parent_color(tmp1, sibling, 340 rb_set_parent_color(tmp1, sibling,
282 RB_BLACK); 341 RB_BLACK);
@@ -296,8 +355,9 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
296 * / \ / \ 355 * / \ / \
297 * (sl) sr N (sl) 356 * (sl) sr N (sl)
298 */ 357 */
299 parent->rb_right = tmp2 = sibling->rb_left; 358 tmp2 = sibling->rb_left;
300 sibling->rb_left = parent; 359 WRITE_ONCE(parent->rb_right, tmp2);
360 WRITE_ONCE(sibling->rb_left, parent);
301 rb_set_parent_color(tmp1, sibling, RB_BLACK); 361 rb_set_parent_color(tmp1, sibling, RB_BLACK);
302 if (tmp2) 362 if (tmp2)
303 rb_set_parent(tmp2, parent); 363 rb_set_parent(tmp2, parent);
@@ -309,8 +369,9 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
309 sibling = parent->rb_left; 369 sibling = parent->rb_left;
310 if (rb_is_red(sibling)) { 370 if (rb_is_red(sibling)) {
311 /* Case 1 - right rotate at parent */ 371 /* Case 1 - right rotate at parent */
312 parent->rb_left = tmp1 = sibling->rb_right; 372 tmp1 = sibling->rb_right;
313 sibling->rb_right = parent; 373 WRITE_ONCE(parent->rb_left, tmp1);
374 WRITE_ONCE(sibling->rb_right, parent);
314 rb_set_parent_color(tmp1, parent, RB_BLACK); 375 rb_set_parent_color(tmp1, parent, RB_BLACK);
315 __rb_rotate_set_parents(parent, sibling, root, 376 __rb_rotate_set_parents(parent, sibling, root,
316 RB_RED); 377 RB_RED);
@@ -334,10 +395,11 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
334 } 395 }
335 break; 396 break;
336 } 397 }
337 /* Case 3 - right rotate at sibling */ 398 /* Case 3 - left rotate at sibling */
338 sibling->rb_right = tmp1 = tmp2->rb_left; 399 tmp1 = tmp2->rb_left;
339 tmp2->rb_left = sibling; 400 WRITE_ONCE(sibling->rb_right, tmp1);
340 parent->rb_left = tmp2; 401 WRITE_ONCE(tmp2->rb_left, sibling);
402 WRITE_ONCE(parent->rb_left, tmp2);
341 if (tmp1) 403 if (tmp1)
342 rb_set_parent_color(tmp1, sibling, 404 rb_set_parent_color(tmp1, sibling,
343 RB_BLACK); 405 RB_BLACK);
@@ -345,9 +407,10 @@ ____rb_erase_color(struct rb_node *parent, struct rb_root *root,
345 tmp1 = sibling; 407 tmp1 = sibling;
346 sibling = tmp2; 408 sibling = tmp2;
347 } 409 }
348 /* Case 4 - left rotate at parent + color flips */ 410 /* Case 4 - right rotate at parent + color flips */
349 parent->rb_left = tmp2 = sibling->rb_right; 411 tmp2 = sibling->rb_right;
350 sibling->rb_right = parent; 412 WRITE_ONCE(parent->rb_left, tmp2);
413 WRITE_ONCE(sibling->rb_right, parent);
351 rb_set_parent_color(tmp1, sibling, RB_BLACK); 414 rb_set_parent_color(tmp1, sibling, RB_BLACK);
352 if (tmp2) 415 if (tmp2)
353 rb_set_parent(tmp2, parent); 416 rb_set_parent(tmp2, parent);
@@ -378,22 +441,41 @@ static inline void dummy_copy(struct rb_node *old, struct rb_node *new) {}
378static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {} 441static inline void dummy_rotate(struct rb_node *old, struct rb_node *new) {}
379 442
380static const struct rb_augment_callbacks dummy_callbacks = { 443static const struct rb_augment_callbacks dummy_callbacks = {
381 dummy_propagate, dummy_copy, dummy_rotate 444 .propagate = dummy_propagate,
445 .copy = dummy_copy,
446 .rotate = dummy_rotate
382}; 447};
383 448
384void rb_insert_color(struct rb_node *node, struct rb_root *root) 449void rb_insert_color(struct rb_node *node, struct rb_root *root)
385{ 450{
386 __rb_insert(node, root, dummy_rotate); 451 __rb_insert(node, root, false, NULL, dummy_rotate);
387} 452}
388 453
389void rb_erase(struct rb_node *node, struct rb_root *root) 454void rb_erase(struct rb_node *node, struct rb_root *root)
390{ 455{
391 struct rb_node *rebalance; 456 struct rb_node *rebalance;
392 rebalance = __rb_erase_augmented(node, root, &dummy_callbacks); 457 rebalance = __rb_erase_augmented(node, root,
458 NULL, &dummy_callbacks);
393 if (rebalance) 459 if (rebalance)
394 ____rb_erase_color(rebalance, root, dummy_rotate); 460 ____rb_erase_color(rebalance, root, dummy_rotate);
395} 461}
396 462
463void rb_insert_color_cached(struct rb_node *node,
464 struct rb_root_cached *root, bool leftmost)
465{
466 __rb_insert(node, &root->rb_root, leftmost,
467 &root->rb_leftmost, dummy_rotate);
468}
469
470void rb_erase_cached(struct rb_node *node, struct rb_root_cached *root)
471{
472 struct rb_node *rebalance;
473 rebalance = __rb_erase_augmented(node, &root->rb_root,
474 &root->rb_leftmost, &dummy_callbacks);
475 if (rebalance)
476 ____rb_erase_color(rebalance, &root->rb_root, dummy_rotate);
477}
478
397/* 479/*
398 * Augmented rbtree manipulation functions. 480 * Augmented rbtree manipulation functions.
399 * 481 *
@@ -402,9 +484,10 @@ void rb_erase(struct rb_node *node, struct rb_root *root)
402 */ 484 */
403 485
404void __rb_insert_augmented(struct rb_node *node, struct rb_root *root, 486void __rb_insert_augmented(struct rb_node *node, struct rb_root *root,
487 bool newleft, struct rb_node **leftmost,
405 void (*augment_rotate)(struct rb_node *old, struct rb_node *new)) 488 void (*augment_rotate)(struct rb_node *old, struct rb_node *new))
406{ 489{
407 __rb_insert(node, root, augment_rotate); 490 __rb_insert(node, root, newleft, leftmost, augment_rotate);
408} 491}
409 492
410/* 493/*
@@ -498,15 +581,24 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new,
498{ 581{
499 struct rb_node *parent = rb_parent(victim); 582 struct rb_node *parent = rb_parent(victim);
500 583
584 /* Copy the pointers/colour from the victim to the replacement */
585 *new = *victim;
586
501 /* Set the surrounding nodes to point to the replacement */ 587 /* Set the surrounding nodes to point to the replacement */
502 __rb_change_child(victim, new, parent, root);
503 if (victim->rb_left) 588 if (victim->rb_left)
504 rb_set_parent(victim->rb_left, new); 589 rb_set_parent(victim->rb_left, new);
505 if (victim->rb_right) 590 if (victim->rb_right)
506 rb_set_parent(victim->rb_right, new); 591 rb_set_parent(victim->rb_right, new);
592 __rb_change_child(victim, new, parent, root);
593}
507 594
508 /* Copy the pointers/colour from the victim to the replacement */ 595void rb_replace_node_cached(struct rb_node *victim, struct rb_node *new,
509 *new = *victim; 596 struct rb_root_cached *root)
597{
598 rb_replace_node(victim, new, &root->rb_root);
599
600 if (root->rb_leftmost == victim)
601 root->rb_leftmost = new;
510} 602}
511 603
512static struct rb_node *rb_left_deepest_node(const struct rb_node *node) 604static struct rb_node *rb_left_deepest_node(const struct rb_node *node)
generated by cgit v1.2.2 (git 2.25.0) at 2025-08-13 13:28:07 -0400