Re: [RFC][PATCH 7/9] rbtree: Implement generic latch_tree

[Paul E. McKenney]

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@xxxxxxxxxx>
> Cc: Andrea Arcangeli <aarcange@xxxxxxxxxx>
> Cc: David Woodhouse <David.Woodhouse@xxxxxxxxx>
> Cc: Rik van Riel <riel@xxxxxxxxxx>
> Cc: Mathieu Desnoyers <mathieu.desnoyers@xxxxxxxxxxxx>
> Cc: "Paul E. McKenney" <paulmck@xxxxxxxxxxxxxxxxxx>
> Cc: Oleg Nesterov <oleg@xxxxxxxxxx>
> Signed-off-by: Peter Zijlstra (Intel) <peterz@xxxxxxxxxxxxx>

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@xxxxxxxxxxxxx>
> + */
> +
> +#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(&ltn->node, parent, link);
> +	rb_insert_color(&ltn->node, root);
> +}
> +
> +static __always_inline void
> +__lt_erase(struct latch_tree_node *ltn, struct rb_root *root)
> +{
> +	rb_erase(&ltn->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 */
> 
> 

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/