From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752593AbcGAHQZ (ORCPT ); Fri, 1 Jul 2016 03:16:25 -0400 Received: from mx1.redhat.com ([209.132.183.28]:53889 "EHLO mx1.redhat.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752080AbcGAHQY convert rfc822-to-8bit (ORCPT ); Fri, 1 Jul 2016 03:16:24 -0400 Organization: Red Hat UK Ltd. Registered Address: Red Hat UK Ltd, Amberley Place, 107-111 Peascod Street, Windsor, Berkshire, SI4 1TE, United Kingdom. Registered in England and Wales under Company Registration No. 3798903 From: David Howells To: Peter Zijlstra cc: dhowells@redhat.com, linux-afs@lists.infradead.org, linux-kernel@vger.kernel.org Subject: [PATCH] Introduce rb_replace_node_rcu() MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-ID: <1411.1467356887.1@warthog.procyon.org.uk> Content-Transfer-Encoding: 8BIT Date: Fri, 01 Jul 2016 08:08:07 +0100 Message-ID: <1412.1467356887@warthog.procyon.org.uk> X-Greylist: Sender IP whitelisted, not delayed by milter-greylist-4.5.16 (mx1.redhat.com [10.5.110.38]); Fri, 01 Jul 2016 07:08:09 +0000 (UTC) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org 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 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 cc: Peter Zijlstra 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 (;;) {