28 May, 2015
1 commit
-
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.For 2) I have carefully audited the code and drawn every intermediate
link state and not found a loop.Cc: Mathieu Desnoyers
Cc: "Paul E. McKenney"
Cc: Oleg Nesterov
Cc: Andrea Arcangeli
Cc: David Woodhouse
Cc: Rik van Riel
Reviewed-by: Michel Lespinasse
Signed-off-by: Peter Zijlstra (Intel)
Signed-off-by: Rusty Russell
14 Oct, 2014
1 commit
-
The comment is copied from Documentation/rbtree.txt, but this comment is
so important that it should also be in the code.Signed-off-by: Lai Jiangshan
Acked-by: Michel Lespinasse
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
12 Jan, 2013
1 commit
-
lib/rbtree.c declared __rb_erase_color() as __always_inline void, and
then exported it with EXPORT_SYMBOL.This was because __rb_erase_color() must be exported for augmented
rbtree users, but it must also be inlined into rb_erase() so that the
dummy callback can get optimized out of that call site.(Actually with a modern compiler, none of the dummy callback functions
should even be generated as separate text functions).The above usage is legal C, but it was unusual enough for some compilers
to warn about it. This change makes things more explicit, with a static
__always_inline ____rb_erase_color function for use in rb_erase(), and a
separate non-inline __rb_erase_color function for use in
rb_erase_augmented call sites.Signed-off-by: Michel Lespinasse
Reported-by: Wu Fengguang
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
26 Oct, 2012
1 commit
-
rb_erase_augmented() is a static function annotated with
__always_inline. This causes a compile failure when attempting to use
the rbtree implementation as a library (e.g. kvm tool):rbtree_augmented.h:125:24: error: expected `=', `,', `;', `asm' or `__attribute__' before `void'
Include linux/compiler.h in rbtree_augmented.h so that the __always_inline
macro is resolved correctly.Signed-off-by: Will Deacon
Cc: Pekka Enberg
Reviewed-by: Michel Lespinasse
Cc: Ingo Molnar
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds
09 Oct, 2012
1 commit
-
Provide rb_insert_augmented() and rb_erase_augmented() through a new
rbtree_augmented.h include file. rb_erase_augmented() is defined there as
an __always_inline function, in order to allow inlining of augmented
rbtree callbacks into it. Since this generates a relatively large
function, each augmented rbtree user should make sure to have a single
call site.Signed-off-by: Michel Lespinasse
Cc: Rik van Riel
Cc: Hillf Danton
Cc: Peter Zijlstra
Cc: Catalin Marinas
Cc: Andrea Arcangeli
Cc: David Woodhouse
Signed-off-by: Andrew Morton
Signed-off-by: Linus Torvalds