diff options
| author | David Howells <dhowells@redhat.com> | 2016-07-01 08:53:51 +0200 |
|---|---|---|
| committer | David Howells <dhowells@redhat.com> | 2016-07-06 11:51:14 +0200 |
| commit | c1adf20052d80f776849fa2c1acb472cdeb7786c (patch) | |
| tree | e73407fdc52ab77e9666ae7798c8b38b6da1ed09 /lib/rbtree.c | |
| parent | rxrpc: Move data_ready peer lookup into rxrpc_find_connection() (diff) | |
| download | linux-c1adf20052d80f776849fa2c1acb472cdeb7786c.tar.xz linux-c1adf20052d80f776849fa2c1acb472cdeb7786c.zip | |
Introduce rb_replace_node_rcu()
Implement an RCU-safe variant of rb_replace_node() and rearrange
rb_replace_node() to do things in the same order.
Signed-off-by: David Howells <dhowells@redhat.com>
Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Diffstat (limited to '')
| -rw-r--r-- | lib/rbtree.c | 26 |
1 files changed, 24 insertions, 2 deletions
diff --git a/lib/rbtree.c b/lib/rbtree.c index 1356454e36de..eb8a19fee110 100644 --- a/lib/rbtree.c +++ b/lib/rbtree.c @@ -539,17 +539,39 @@ void rb_replace_node(struct rb_node *victim, struct rb_node *new, { 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 */ - __rb_change_child(victim, new, parent, root); if (victim->rb_left) rb_set_parent(victim->rb_left, new); if (victim->rb_right) rb_set_parent(victim->rb_right, new); + __rb_change_child(victim, new, parent, root); +} +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 parent's pointer to the new node last after an RCU barrier + * so that the pointers onwards are seen to be set correctly when doing + * an RCU walk over the tree. + */ + __rb_change_child_rcu(victim, new, parent, root); } -EXPORT_SYMBOL(rb_replace_node); +EXPORT_SYMBOL(rb_replace_node_rcu); static struct rb_node *rb_left_deepest_node(const struct rb_node *node) { |