linux-toradex.git/include/linux/rbtree.h, branch v4.8-rc6

Introduce rb_replace_node_rcu()

2016-07-06T09:51:14+00:00

Implement an RCU-safe variant of rb_replace_node() and rearrange
rb_replace_node() to do things in the same order.

Signed-off-by: David Howells 
Acked-by: Peter Zijlstra (Intel)

rbtree: use READ_ONCE in RB_EMPTY_ROOT

2016-01-21T01:09:18+00:00

With commit d72da4a4d97 ("rbtree: Make lockless searches non-fatal") our
rbtrees provide weak guarantees that allows us to do lockless (and very
speculative) reads of the tree.  Such readers cannot see partial stores
on nodes, ie left/right as well as root.  As such, similar to the
WRITE_ONCE semantics when doing rotations, use READ_ONCE when checking
the root node in RB_EMPTY_ROOT.

Signed-off-by: Davidlohr Bueso 
Acked-by: Peter Zijlstra (Intel) 
Cc: Michel Lespinasse 
Cc: Rusty Russell 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

rbtree: clarify documentation of rbtree_postorder_for_each_entry_safe()

2015-11-07T01:50:42+00:00

I noticed that commit a20135ffbc44 ("writeback: don't drain
bdi_writeback_congested on bdi destruction") added a usage of
rbtree_postorder_for_each_entry_safe() in mm/backing-dev.c which appears
to try to rb_erase() elements from an rbtree while iterating over it using
rbtree_postorder_for_each_entry_safe().

Doing this will cause random nodes to be missed by the iteration because
rb_erase() may rebalance the tree, changing the ordering that we're trying
to iterate over.

The previous documentation for rbtree_postorder_for_each_entry_safe()
wasn't clear that this wasn't allowed, it was taken from the docs for
list_for_each_entry_safe(), where erasing isn't a problem due to
list_del() not reordering.

Explicitly warn developers about this potential pit-fall.

Note that I haven't fixed the actual issue that (it appears) the commit
referenced above introduced (not familiar enough with that code).

In general (and in this case), the patterns to follow are:
 - switch to rb_first() + rb_erase(), don't use
   rbtree_postorder_for_each_entry_safe().
 - keep the postorder iteration and don't rb_erase() at all. Instead
   just clear the fields of rb_node & cgwb_congested_tree as required by
   other users of those structures.

[akpm@linux-foundation.org: tweak comments]
Signed-off-by: Cody P Schafer 
Cc: John de la Garza 
Cc: Michel Lespinasse 
Cc: Peter Zijlstra 
Cc: Rusty Russell 
Cc: Tejun Heo 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

rbtree: Make lockless searches non-fatal

2015-05-28T02:02:04+00:00

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

lib/rbtree.c: fix typo in comment

2015-02-17T22:34:52+00:00

Signed-off-by: John de la Garza 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

rbtree: fix rbtree_postorder_for_each_entry_safe() iterator

2013-11-13T03:09:33+00:00

The iterator rbtree_postorder_for_each_entry_safe() relies on pointer
underflow behavior when testing for loop termination.  In particular it
expects that

  &rb_entry(NULL, type, field)->field

is NULL.  But the result of this expression is not defined by a C standard
and some gcc versions (e.g.  4.3.4) assume the above expression can never
be equal to NULL.  The net result is an oops because the iteration is not
properly terminated.

Fix the problem by modifying the iterator to avoid pointer underflows.

Signed-off-by: Jan Kara 
Signed-off-by: Cody P Schafer 
Cc: Michel Lespinasse 
Cc: "David S. Miller" 
Cc: Adrian Hunter 
Cc: Artem Bityutskiy 
Cc: David Woodhouse 
Cc: Jozsef Kadlecsik 
Cc: Pablo Neira Ayuso 
Cc: Patrick McHardy 
Cc: Paul Mundt 
Cc: Theodore Ts'o 
Cc: 		[3.12.x]
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

rbtree: add rbtree_postorder_for_each_entry_safe() helper

2013-09-11T22:59:20+00:00

Because deletion (of the entire tree) is a relatively common use of the
rbtree_postorder iteration, and because doing it safely means fiddling
with temporary storage, provide a helper to simplify postorder rbtree
iteration.

Signed-off-by: Cody P Schafer 
Reviewed-by: Seth Jennings 
Cc: David Woodhouse 
Cc: Rik van Riel 
Cc: Michel Lespinasse 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

rbtree: add postorder iteration functions

2013-09-11T22:59:19+00:00

Postorder iteration yields all of a node's children prior to yielding the
node itself, and this particular implementation also avoids examining the
leaf links in a node after that node has been yielded.

In what I expect will be its most common usage, postorder iteration allows
the deletion of every node in an rbtree without modifying the rbtree nodes
(no _requirement_ that they be nulled) while avoiding referencing child
nodes after they have been "deleted" (most commonly, freed).

I have only updated zswap to use this functionality at this point, but
numerous bits of code (most notably in the filesystem drivers) use a hand
rolled postorder iteration that NULLs child links as it traverses the
tree.  Each of those instances could be replaced with this common
implementation.

1 & 2 add rbtree postorder iteration functions.
3 adds testing of the iteration to the rbtree runtime tests
4 allows building the rbtree runtime tests as builtins
5 updates zswap.

This patch:

Add postorder iteration functions for rbtree.  These are useful for safely
freeing an entire rbtree without modifying the tree at all.

Signed-off-by: Cody P Schafer 
Reviewed-by: Seth Jennings 
Cc: David Woodhouse 
Cc: Rik van Riel 
Cc: Michel Lespinasse 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds

rbtree: move augmented rbtree functionality to rbtree_augmented.h

2012-10-09T07:22:40+00:00

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

rbtree: add RB_DECLARE_CALLBACKS() macro

2012-10-09T07:22:38+00:00

As proposed by Peter Zijlstra, this makes it easier to define the augmented
rbtree callbacks.

Signed-off-by: Michel Lespinasse 
Cc: Rik van Riel 
Cc: Peter Zijlstra 
Cc: Andrea Arcangeli 
Cc: David Woodhouse 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds