Add some XArray-based helper functions to replace the radix tree based
metaphors currently in use.  The biggest change is that converted code
doesn't see its own lock bit; get_unlocked_entry() always returns an
entry with the lock bit clear.  So we don't have to mess around loading
the current entry and clearing the lock bit; we can just store the
unlocked entry that we already have.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

Since the XArray is embedded in the struct address_space, its address
contains exactly as much entropy as the address of the mapping.  This
patch is purely preparatory for later patches which will simplify the
wait/wake interfaces.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

Remove mentions of 'radix' and 'radix tree'.  Simplify some names by
dropping the word 'mapping'.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

This is a straightforward conversion.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

This is close to a 1:1 replacement of radix tree APIs with their XArray
equivalents.  It would be possible to optimise nilfs_copy_back_pages(),
but that doesn't seem to be in the performance path.  Also, I think
it has a pre-existing bug, and I've added a note to that effect in the
source code.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

A couple of short loops.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

Mostly comment fixes, but one use of __xa_set_mark.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

Signed-off-by: NMatthew Wilcox <willy@infradead.org>
Acked-by: NDavid Sterba <dsterba@suse.com>

Remove the last mentions of radix tree from various comments.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

Switch to a batch-processing model like memfd_wait_for_pins() and
use the xa_state previously set up by memfd_wait_for_pins().
Signed-off-by: NMatthew Wilcox <willy@infradead.org>
Reviewed-by: NMike Kravetz <mike.kravetz@oracle.com>

Simplify the locking by taking the spinlock while we walk the tree on
the assumption that many acquires and releases of the lock will be worse
than holding the lock while we process an entire batch of pages.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>
Reviewed-by: NMike Kravetz <mike.kravetz@oracle.com>

Simpler code because the xarray takes care of things like the limit and
dereferencing the slot.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

Since we are conditionally storing NULL in the XArray, we do not need
to allocate memory and the GFP flags will be unused.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

xa_find() is a slightly easier API to use than
radix_tree_gang_lookup_slot() because it contains its own RCU locking.
This commit removes the last user of radix_tree_gang_lookup_slot()
so remove the function too.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

We can use xas_find_conflict() instead of radix_tree_gang_lookup_slot()
to find any conflicting entry and combine the three paths through this
function into one.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

This is a 1:1 conversion.  The major part of this patch is converting
the test framework from userspace to kernel space and mirroring the
algorithm now used in find_swap_entry().
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

xa_load has its own RCU locking, so we can eliminate it here.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

Rename shmem_radix_tree_replace() to shmem_replace_entry() and
convert it to use the XArray API.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

Removes sparse warnings.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

This is just a variable rename and comment change.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

Slightly shorter and easier to read code.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

I found another victim of the radix tree being hard to use.  Because
there was no call to radix_tree_preload(), khugepaged was allocating
radix_tree_nodes using GFP_ATOMIC.

I also converted a local_irq_save()/restore() pair to
disable()/enable().
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

Quite a straightforward conversion.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

Signed-off-by: NMatthew Wilcox <willy@infradead.org>

This one is trivial.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

Both callers of __delete_from_swap_cache have the swp_entry_t already,
so pass that in to make constructing the XA_STATE easier.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

Combine __add_to_swap_cache and add_to_swap_cache into one function
since there is no more need to preload.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

This is essentially xa_cmpxchg() with the locking handled above us,
and it doesn't have to handle replacing a NULL entry.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

We construct an XA_STATE and use it to delete the node with
xas_store() rather than adding a special function for this unique
use case.  Includes a test that simulates this usage for the
test suite.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

Includes moving mapping_tagged() to fs.h as a static inline, and
changing it to return bool.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

Instead of calling find_get_pages_range() and putting any reference,
use xas_find() to iterate over any entries in the range, skipping the
shadow/swap entries.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

Signed-off-by: NMatthew Wilcox <willy@infradead.org>

Rename the function from page_cache_tree_delete_batch to just
page_cache_delete_batch.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

Now the page cache lookup is using the XArray, let's convert this
regression test from the radix tree API to the XArray so it's testing
roughly the same thing it was testing before.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

Slight change of strategy here; if we have trouble getting hold of a
page for whatever reason (eg a compound page is split underneath us),
don't spin to stabilise the page, just continue the iteration, like we
would if we failed to trylock the page.  Since this is a speculative
optimisation, it feels like we should allow the process to take an extra
fault if it turns out to need this page instead of spending time to pin
down a page it may not need.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

Slightly shorter and simpler code.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

The 'end' parameter of the xas_for_each iterator avoids a useless
iteration at the end of the range.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

There's no direct replacement for radix_tree_for_each_contig()
in the XArray API as it's an unusual thing to do.  Instead,
open-code a loop using xas_next().  This removes the only user of
radix_tree_for_each_contig() so delete the iterator from the API and
the test suite code for it.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

The 'end' parameter of the xas_for_each iterator avoids a useless
iteration at the end of the range.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>

Slightly shorter and simpler code.
Signed-off-by: NMatthew Wilcox <willy@infradead.org>