Messages in this thread |  | | Date | Mon, 13 Apr 2015 17:50:08 +0200 | From | Ingo Molnar <> | Subject | Re: [PATCH v5 04/10] rbtree: Make lockless searches non-fatal |
| |
* Peter Zijlstra <peterz@infradead.org> 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
|  |