Re: [PATCH v5 04/10] rbtree: Make lockless searches non-fatal

[Ingo Molnar]

* Peter Zijlstra <peterz@xxxxxxxxxxxxx> wrote:

> Change the insert and erase code such that lockless searches are
> non-fatal.
> 
> In and of itself an rbtree cannot be correctly searched while
> in-modification, we can however provide weaker guarantees that will
> allow the rbtree to be used in conjunction with other techniques, such
> as latches; see 9b0fd802e8c0 ("seqcount: Add raw_write_seqcount_latch()").
> 
> For this to work we need the following guarantees from the rbtree
> code:
> 
>  1) a lockless reader must not see partial stores, this would allow it
>     to observe nodes that are invalid memory.
> 
>  2) there must not be (temporary) loops in the tree structure in the
>     modifier's program order, this would cause a lookup which
>     interrupts the modifier to get stuck indefinitely.
> 
> For 1) we must use WRITE_ONCE() for all updates to the tree structure;
> in particular this patch only does rb_{left,right} as those are the
> only element required for simple searches.
> 
> It generates slightly worse code, probably because volatile. But in
> pointer chasing heavy code a few instructions more should not matter.

So I had a look at code generation on x86/64-defconfig, it adds 2 more 
instructions, out of 900+ instructions total:

   text    data     bss     dec     hex filename
   3299       0       0    3299     ce3 rbtree.o.before
   3308       0       0    3308     cec rbtree.o.after

One of the instructions is a MOV, the other AFAICS is a NOP due to 
changed jump target alignment.

Interestingly, when compiled with -Os then your patch actually 
_shrinks_ the code:

   text    data     bss     dec     hex filename
   2524       0       0    2524     9dc rbtree.o.before
   2440       0       0    2440     988 rbtree.o.after

and rather significantly so. This is with GCC 4.9. Possibly your patch 
unconfused GCC somehow.

So just for kicks I applied my patch-set that fixes up jump target 
alignments, and the numbers with the regular -O2 became:

   text    data     bss     dec     hex filename
   2995       0       0    2995     bb3 rbtree.o.before
   2981       0       0    2981     ba5 rbtree.o.after

so your patch shrinks rbtree.o even without -Os, so it's probably a 
speedup and doesn't generate worse code once GCC's alignment sillies 
are righted!

>  	*rb_link = node;
>  }
>  
> +static inline void rb_link_node_rcu(struct rb_node * node, struct rb_node * parent,
> +				    struct rb_node ** rb_link)

Minor stylistic nit, the standard pattern I suspect has spaces fewer 
by three:

static inline void rb_link_node_rcu(struct rb_node *node, struct rb_node *parent,
				    struct rb_node **rb_link)

> +/*
> + * Notes on lockless lookups:
> + *
> + * All stores to the tree structure (rb_left and rb_right) must be done using
> + * WRITE_ONCE(). And we must not inadvertently cause (temporary) loops in the
> + * tree structure as seen in program order.
> + *
> + * These two requirements will allow lockless iteration of the tree -- not
> + * correct iteration mind you, tree rotations are not atomic so a lookup might
> + * miss entire subtrees.
> + *
> + * But they do guarantee that any such traversal will only see valid elements
> + * and that it will indeed complete -- does not get stuck in a loop.
> + *
> + * It also guarantees that if the lookup returns an element it is the 'correct'
> + * one. But not returning an element does _NOT_ mean its not present.

s/its/it's

Thanks,

	Ingo
--
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/