Messages in this thread Patch in this message | | | From | David Howells <> | Subject | [PATCH] Introduce rb_replace_node_rcu() | Date | Fri, 01 Jul 2016 08:08:07 +0100 |
| |
Hi Peter,
How about the attached patch? Should I also reorder rb_replace_node() whilst I'm at it so that the new node is initialised first (it shouldn't make a difference, I know)?
David --- commit 812667d2a82a6a8fe35a44e951e8b1515b04696a Author: David Howells <dhowells@redhat.com> Date: Fri Jul 1 07:53:51 2016 +0100
Introduce rb_replace_node_rcu() Implement an RCU-safe variant of rb_replace_node(). Signed-off-by: David Howells <dhowells@redhat.com> cc: Peter Zijlstra <peterz@infradead.org>
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h index b6900099ea81..e585018498d5 100644 --- a/include/linux/rbtree.h +++ b/include/linux/rbtree.h @@ -76,6 +76,8 @@ extern struct rb_node *rb_next_postorder(const struct rb_node *); /* Fast replacement of a single node without remove/rebalance/add/rebalance */ extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, struct rb_root *root); +extern void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new, + struct rb_root *root); static inline void rb_link_node(struct rb_node *node, struct rb_node *parent, struct rb_node **rb_link) diff --git a/include/linux/rbtree_augmented.h b/include/linux/rbtree_augmented.h index 14d7b831b63a..d076183e49be 100644 --- a/include/linux/rbtree_augmented.h +++ b/include/linux/rbtree_augmented.h @@ -130,6 +130,19 @@ __rb_change_child(struct rb_node *old, struct rb_node *new, WRITE_ONCE(root->rb_node, new); } +static inline void +__rb_change_child_rcu(struct rb_node *old, struct rb_node *new, + struct rb_node *parent, struct rb_root *root) +{ + if (parent) { + if (parent->rb_left == old) + rcu_assign_pointer(parent->rb_left, new); + else + rcu_assign_pointer(parent->rb_right, new); + } else + rcu_assign_pointer(root->rb_node, new); +} + extern void __rb_erase_color(struct rb_node *parent, struct rb_root *root, void (*augment_rotate)(struct rb_node *old, struct rb_node *new)); diff --git a/lib/rbtree.c b/lib/rbtree.c index 1356454e36de..59eb906c6c3b 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -551,6 +551,25 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new, } EXPORT_SYMBOL(rb_replace_node); +void rb_replace_node_rcu(struct rb_node *victim, struct rb_node *new, + struct rb_root *root) +{ + struct rb_node *parent = rb_parent(victim); + + /* Copy the pointers/colour from the victim to the replacement */ + *new = *victim; + + /* Set the surrounding nodes to point to the replacement */ + if (victim->rb_left) + rb_set_parent(victim->rb_left, new); + if (victim->rb_right) + rb_set_parent(victim->rb_right, new); + + /* Set the onward pointer last with an RCU barrier */ + __rb_change_child_rcu(victim, new, parent, root); +} +EXPORT_SYMBOL(rb_replace_node_rcu); + static struct rb_node *rb_left_deepest_node(const struct rb_node *node) { for (;;) {
| |