linux-toradex.git/include/linux/radix-tree.h, branch v4.13-rc4

radix-tree: Fix __rcu annotations

2017-02-14T02:44:09+00:00

Many places were missing __rcu annotations.  A few places needed a few
lines of explanation about why it was safe to not use RCU accessors.
Add a custom CFLAGS setting to the Makefile to ensure that new patches
don't miss RCU annotations.

Signed-off-by: Matthew Wilcox

radix-tree: Add rcu_dereference and rcu_assign_pointer calls

2017-02-14T02:44:09+00:00

Some of these have been missing for many years.  Others were recently
introduced by me.  Fortunately, we have tools that help us find such
things.

Signed-off-by: Matthew Wilcox

radix-tree: Store a pointer to the root in each node

2017-02-14T02:44:05+00:00

Instead of having this mysterious private_data in each radix_tree_node,
store a pointer to the root, which can be useful for debugging.  This also
relieves the mm code from the duty of updating it.

Acked-by: Johannes Weiner 
Signed-off-by: Matthew Wilcox

Reimplement IDR and IDA using the radix tree

2017-02-14T02:44:01+00:00

The IDR is very similar to the radix tree.  It has some functionality that
the radix tree did not have (alloc next free, cyclic allocation, a
callback-based for_each, destroy tree), which is readily implementable on
top of the radix tree.  A few small changes were needed in order to use a
tag to represent nodes with free space below them.  More extensive
changes were needed to support storing NULL as a valid entry in an IDR.
Plain radix trees still interpret NULL as a not-present entry.

The IDA is reimplemented as a client of the newly enhanced radix tree.  As
in the current implementation, it uses a bitmap at the last level of the
tree.

Signed-off-by: Matthew Wilcox 
Signed-off-by: Matthew Wilcox 
Tested-by: Kirill A. Shutemov 
Cc: Konstantin Khlebnikov 
Cc: Ross Zwisler 
Cc: Tejun Heo 
Signed-off-by: Andrew Morton

radix-tree: Add radix_tree_iter_delete

2017-02-13T21:09:55+00:00

Factor the deletion code out into __radix_tree_delete() and provide a
nice iterator-based wrapper around it.  If we free the node, advance
the iterator to avoid reading from freed memory.

Signed-off-by: Matthew Wilcox

radix-tree: Add radix_tree_iter_tag_clear()

2017-02-13T21:09:44+00:00

The counterpart to radix_tree_iter_tag_set(), used by the IDR code

Signed-off-by: Matthew Wilcox 
Reviewed-by: Rehas Sachdeva

radix tree: constify some pointers

2017-01-28T02:29:38+00:00

If we're just getting the value of a tag, or looking up an entry,
we won't modify the radix tree, so we can declare these functions as
taking a const pointer.  Mostly for documentation purposes, though it
might help code generation.

Signed-off-by: Matthew Wilcox

radix tree: Add some implicit includes

2017-01-28T02:29:38+00:00

We were using spinlock_t and INIT_LIST_HEAD without including spinlock.h
or list.h.  They were being implicitly included through some other header
file, but that's fragile.

Signed-off-by: Matthew Wilcox

mm: workingset: fix use-after-free in shadow node shrinker

2017-01-08T02:22:40+00:00

Several people report seeing warnings about inconsistent radix tree
nodes followed by crashes in the workingset code, which all looked like
use-after-free access from the shadow node shrinker.

Dave Jones managed to reproduce the issue with a debug patch applied,
which confirmed that the radix tree shrinking indeed frees shadow nodes
while they are still linked to the shadow LRU:

  WARNING: CPU: 2 PID: 53 at lib/radix-tree.c:643 delete_node+0x1e4/0x200
  CPU: 2 PID: 53 Comm: kswapd0 Not tainted 4.10.0-rc2-think+ #3
  Call Trace:
     delete_node+0x1e4/0x200
     __radix_tree_delete_node+0xd/0x10
     shadow_lru_isolate+0xe6/0x220
     __list_lru_walk_one.isra.4+0x9b/0x190
     list_lru_walk_one+0x23/0x30
     scan_shadow_nodes+0x2e/0x40
     shrink_slab.part.44+0x23d/0x5d0
     shrink_node+0x22c/0x330
     kswapd+0x392/0x8f0

This is the WARN_ON_ONCE(!list_empty(&node->private_list)) placed in the
inlined radix_tree_shrink().

The problem is with 14b468791fa9 ("mm: workingset: move shadow entry
tracking to radix tree exceptional tracking"), which passes an update
callback into the radix tree to link and unlink shadow leaf nodes when
tree entries change, but forgot to pass the callback when reclaiming a
shadow node.

While the reclaimed shadow node itself is unlinked by the shrinker, its
deletion from the tree can cause the left-most leaf node in the tree to
be shrunk.  If that happens to be a shadow node as well, we don't unlink
it from the LRU as we should.

Consider this tree, where the s are shadow entries:

       root->rnode
            |
       [0       n]
        |       |
     [s    ] [sssss]

Now the shadow node shrinker reclaims the rightmost leaf node through
the shadow node LRU:

       root->rnode
            |
       [0        ]
        |
    [s     ]

Because the parent of the deleted node is the first level below the
root and has only one child in the left-most slot, the intermediate
level is shrunk and the node containing the single shadow is put in
its place:

       root->rnode
            |
       [s        ]

The shrinker again sees a single left-most slot in a first level node
and thus decides to store the shadow in root->rnode directly and free
the node - which is a leaf node on the shadow node LRU.

  root->rnode
       |
       s

Without the update callback, the freed node remains on the shadow LRU,
where it causes later shrinker runs to crash.

Pass the node updater callback into __radix_tree_delete_node() in case
the deletion causes the left-most branch in the tree to collapse too.

Also add warnings when linked nodes are freed right away, rather than
wait for the use-after-free when the list is scanned much later.

Fixes: 14b468791fa9 ("mm: workingset: move shadow entry tracking to radix tree exceptional tracking")
Reported-by: Dave Chinner 
Reported-by: Hugh Dickins 
Reported-by: Andrea Arcangeli 
Reported-and-tested-by: Dave Jones 
Signed-off-by: Johannes Weiner 
Cc: Christoph Hellwig 
Cc: Chris Leech 
Cc: Lee Duncan 
Cc: Jan Kara 
Cc: Kirill A. Shutemov 
Cc: Matthew Wilcox 
Cc: Andrew Morton 
Signed-off-by: Linus Torvalds

radix-tree: add radix_tree_split_preload()

2016-12-15T00:04:10+00:00

Calculate how many nodes we need to allocate to split an old_order entry
into multiple entries, each of size new_order.  The test suite checks
that we allocated exactly the right number of nodes; neither too many
(checked by rtp->nr == 0), nor too few (checked by comparing
nr_allocated before and after the call to radix_tree_split()).

Link: http://lkml.kernel.org/r/1480369871-5271-60-git-send-email-mawilcox@linuxonhyperv.com
Signed-off-by: Matthew Wilcox 
Tested-by: Kirill A. Shutemov 
Cc: Konstantin Khlebnikov 
Cc: Ross Zwisler 
Cc: Matthew Wilcox 
Signed-off-by: Andrew Morton 
Signed-off-by: Linus Torvalds