From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754975AbbCBTxk (ORCPT ); Mon, 2 Mar 2015 14:53:40 -0500 Received: from e34.co.us.ibm.com ([32.97.110.152]:51053 "EHLO e34.co.us.ibm.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1754025AbbCBTxi (ORCPT ); Mon, 2 Mar 2015 14:53:38 -0500 Date: Mon, 2 Mar 2015 11:53:32 -0800 From: "Paul E. McKenney" To: Peter Zijlstra Cc: mingo@kernel.org, rusty@rustcorp.com.au, mathieu.desnoyers@efficios.com, oleg@redhat.com, linux-kernel@vger.kernel.org, andi@firstfloor.org, rostedt@goodmis.org, tglx@linutronix.de, Michel Lespinasse , Andrea Arcangeli , David Woodhouse , Rik van Riel Subject: Re: [RFC][PATCH 7/9] rbtree: Implement generic latch_tree Message-ID: <20150302195331.GW15405@linux.vnet.ibm.com> Reply-To: paulmck@linux.vnet.ibm.com References: <20150228212447.381543289@infradead.org> <20150228213110.248177252@infradead.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20150228213110.248177252@infradead.org> User-Agent: Mutt/1.5.21 (2010-09-15) X-TM-AS-MML: disable X-Content-Scanned: Fidelis XPS MAILER x-cbid: 15030219-0017-0000-0000-000009288D6A Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Sat, Feb 28, 2015 at 10:24:54PM +0100, Peter Zijlstra wrote: > Implement a latched RB-tree in order to get RCU style lookups. > > Cc: Michel Lespinasse > Cc: Andrea Arcangeli > Cc: David Woodhouse > Cc: Rik van Riel > Cc: Mathieu Desnoyers > Cc: "Paul E. McKenney" > Cc: Oleg Nesterov > Signed-off-by: Peter Zijlstra (Intel) The caller of latch_tree_erase() is required to wait for a grace period before freeing the erased nodes? Or am I missing something subtle here? Thanx, Paul > --- > include/linux/rbtree_latch.h | 140 +++++++++++++++++++++++++++++++++++++++++++ > 1 file changed, 140 insertions(+) > > --- /dev/null > +++ b/include/linux/rbtree_latch.h > @@ -0,0 +1,140 @@ > +/* > + * Latched RB-trees > + * > + * Copyright (C) 2015 Intel Corp., Peter Zijlstra > + */ > + > +#ifndef RB_TREE_LATCH_H > +#define RB_TREE_LATCH_H > + > +#include > +#include > + > +/* > + * Since RB-trees have non atomic modifications they're not suited for > + * RCU/lockless queries. > + * > + * Employ the latch technique -- see @raw_write_seqcount_latch -- to implement > + * a latched RB-tree which does allow this by virtue of always having (at > + * least) one stable copy of the tree. > + * > + * However, while we have the guarantee that there is at all times one stable > + * copy, this does not guarantee an iteration will not observe modifications. > + * What might have been a stable copy at the start of the iteration, need not > + * remain so for the duration of the iteration. > + * > + * Therefore, this does require a lockless RB-tree iteration to be non-fatal in > + * all circumstances; see the comment in lib/rbtree.c. > + */ > + > +struct latch_tree_node { > + void *priv; > + struct rb_node node; > +}; > + > +struct latch_tree_nodes { > + struct latch_tree_node node[2]; > +}; > + > +struct latch_tree_root { > + seqcount_t seq; > + struct rb_root tree[2]; > +}; > + > +struct latch_tree_ops { > + bool (*less)(struct latch_tree_node *a, struct latch_tree_node *b); > + int (*comp)(void *key, struct latch_tree_node *b); > +}; > + > +static __always_inline void > +__lt_insert(struct latch_tree_node *ltn, struct rb_root *root, > + bool (*less)(struct latch_tree_node *a, struct latch_tree_node *b)) > +{ > + struct rb_node **link = &root->rb_node; > + struct rb_node *parent = NULL; > + struct latch_tree_node *ltp; > + > + while (*link) { > + parent = *link; > + ltp = container_of(parent, struct latch_tree_node, node); > + > + if (less(ltn, ltp)) > + link = &parent->rb_left; > + else > + link = &parent->rb_right; > + } > + > + rb_link_node_rcu(<n->node, parent, link); > + rb_insert_color(<n->node, root); > +} > + > +static __always_inline void > +__lt_erase(struct latch_tree_node *ltn, struct rb_root *root) > +{ > + rb_erase(<n->node, root); > +} > + > +static __always_inline struct latch_tree_node * > +__lt_find(void *key, struct rb_root *root, > + int (*comp)(void *key, struct latch_tree_node *ltn)) > +{ > + struct rb_node *n = rcu_dereference_raw(root->rb_node); > + struct latch_tree_node *ltn; > + int c; > + > + while (n) { > + ltn = container_of(n, struct latch_tree_node, node); > + c = comp(key, ltn); > + > + if (c < 0) > + n = rcu_dereference_raw(n->rb_left); > + else if (c > 0) > + n = rcu_dereference_raw(n->rb_right); > + else > + return ltn; > + } > + > + return NULL; > +} > + > +static __always_inline void > +latch_tree_insert(struct latch_tree_nodes *nodes, > + struct latch_tree_root *root, > + void *priv, > + const struct latch_tree_ops *ops) > +{ > + nodes->node[0].priv = nodes->node[1].priv = priv; > + > + raw_write_seqcount_latch(&root->seq); > + __lt_insert(&nodes->node[0], &root->tree[0], ops->less); > + raw_write_seqcount_latch(&root->seq); > + __lt_insert(&nodes->node[1], &root->tree[1], ops->less); > +} > + > +static __always_inline void > +latch_tree_erase(struct latch_tree_nodes *nodes, > + struct latch_tree_root *root, > + const struct latch_tree_ops *ops) > +{ > + raw_write_seqcount_latch(&root->seq); > + __lt_erase(&nodes->node[0], &root->tree[0]); > + raw_write_seqcount_latch(&root->seq); > + __lt_erase(&nodes->node[1], &root->tree[1]); > +} > + > +static __always_inline struct latch_tree_node * > +latch_tree_find(void *key, struct latch_tree_root *root, > + const struct latch_tree_ops *ops) > +{ > + struct latch_tree_node *node; > + unsigned int seq; > + > + do { > + seq = raw_read_seqcount(&root->seq); > + node = __lt_find(key, &root->tree[seq & 1], ops->comp); > + } while (read_seqcount_retry(&root->seq, seq)); > + > + return node; > +} > + > +#endif /* RB_TREE_LATCH_H */ > >