Messages in this thread | | | Date | Mon, 2 Mar 2015 11:53:32 -0800 | From | "Paul E. McKenney" <> | Subject | Re: [RFC][PATCH 7/9] rbtree: Implement generic latch_tree |
| |
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 <walken@google.com> > Cc: Andrea Arcangeli <aarcange@redhat.com> > Cc: David Woodhouse <David.Woodhouse@intel.com> > Cc: Rik van Riel <riel@redhat.com> > Cc: Mathieu Desnoyers <mathieu.desnoyers@efficios.com> > Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> > Cc: Oleg Nesterov <oleg@redhat.com> > Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
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 <peterz@infradead.org> > + */ > + > +#ifndef RB_TREE_LATCH_H > +#define RB_TREE_LATCH_H > + > +#include <linux/rbtree.h> > +#include <linux/seqlock.h> > + > +/* > + * 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 */ > >
| |