maple_tree: Some clean up of comments and mte_set_pivot(), etc

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

whitespace

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

whitespace

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: Whitespace fix

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: Remove unused functions and rename mas_store_entry to mas_wr_store_entry

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: Move wr_mas offset_end setting to walk

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: Make mas_store_entry() take ma_wr_state

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: mas_store cleanup again..

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: Clean up mas_commit_b_node()

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: Add newlines after functions

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: Rename _mas_awalk() to mas_anode_descend() and fix potential error skip

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: Rename _mas_rev_awalk() to mas_rev_awalk()

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: Remove _mas_safe_pivot()

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: Don't record position in mas_split() and mas_spanning_reblance()

Just walk there in the end

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: Fix compile warning in mas_spanning_store()

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: mas_spanning_store() cleanup a bit

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: Reduce arguments to mas_store_b_node() by using ma_wr_state variables

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: Just use ma_wr_state for spanning write function arguments

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: Use ma_wr_state for left side of spanning store

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: Start using ma_wr_state for spanning_store

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: Small clean up for mas_spanning_store()

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: Whitespace fix

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: Move older walks to test code, implement with newer walks

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: Add mtree_range_walk() for quicker searching.

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: Optimize mas_node_walk() and mtree_load()

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: Add mt_lookup() with no state support for faster lookups

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: Use ma_data_end() where possible, drop some checks from mas_tree_walk()

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: Change _mas_walk() and __mas_walk() names

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: remove _mt_find() and add mt_find_after()

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: Remove _mas_find() and _mas_prev(), rename _mas_next() to mas_next_entry()

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: Drop mas_mat_free() bool flag and duplicate function for mas_mat_destroy uses

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

maple_tree: Remove _mas_store in favour of mas_store_entry() and mas_insert()

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

test fixes

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

mm/mmap: Drop range_has_overlap() function

Since there is no longer a linked list, the range_has_overlap() function
is identical to the find_vma_intersection() function.  There is only one
place that actually needs the previous vma, so just use vma_prev() in
that one case.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

mm: Remove the vma linked list

Replace any vm_next use with vma_next().

Update free_pgtables(), unmap_vmas(), and zap_page_range() to use the
maple tree.

Use the new free_pgtables() and unmap_vmas() in do_mas_align_munmap().
At the same time, alter the loop to be more compact.

Now that free_pgtables() and unmap_vmas() take a maple tree as an
argument, rearrange do_mas_align_munmap() to use the new table to hold
the lock

Remove __vma_link_list() and __vma_unlink_list() as they are exclusively
used to update the linked list

Rework validation of tree as it was depending on the linked list.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

nommu: Remove uses of VMA linked list

Use the maple tree or VMA iterator instead.  This is faster and will
allow us to shrink the VMA.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>

i915: Use the VMA iterator

Replace the O(n.log(n)) loop with an O(n) loop.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>

mm/swapfile: Use maple tree iterator instead of vma linked list

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

mm/pagewalk: Use vma_next() instead of vma linked list

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

mm/oom_kill: Use maple tree iterators instead of vma linked list

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

mm/msync: Use vma_next() instead of vma linked list

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

mm/mremap: Use vma_next() instead of vma linked list

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

mm/mprotect: Use maple tree navigation instead of vma linked list

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

mm/mlock: Use maple tree iterators instead of vma linked list

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

mm/mempolicy: Use maple tree iterators instead of vma linked list

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

mm/memcontrol: Stop using mm->highest_vm_end

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

mm/madvise: Use vma_next instead of vma linked list

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

mm/ksm: Use maple tree iterators instead of vma linked list

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

mm/khugepaged: Use maple tree iterators instead of vma linked list

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

mm/gup: Use maple tree navigation instead of linked list

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

bpf: Remove VMA linked list

Use vma_next() and remove reference to the start of the linked list

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

fork: Use VMA iterator

The VMA iterator is faster than the linked list and removing the linked
list will shrink the vm_area_struct.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

sched: Use maple tree iterator to walk VMAs

The linked list is slower than walking the VMAs using the maple tree.
We can't use the VMA iterator here because it doesn't support
moving to an earlier position.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

perf: Use VMA iterator

The VMA iterator is faster than the linked list and removing the linked
list will shrink the vm_area_struct.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

acct: Use VMA iterator instead of linked list

The VMA iterator is faster than the linked list.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

ipc/shm: Use VMA iterator instead of linked list

The VMA iterator is faster than the linked llist, and it can be walked
even when VMAs are being removed from the address space, so there's no
need to keep track of 'next'.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

userfaultfd: Use maple tree iterator to iterate VMAs

Don't use the mm_struct linked list or the vma->vm_next in prep for removal

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

fs/proc/task_mmu: Stop using linked list and highest_vm_end

Remove references to mm_struct linked list and highest_vm_end for when they are removed

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

fs/proc/base: Use maple tree iterators in place of linked list

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

exec: Use VMA iterator instead of linked list

Remove a use of the vm_next list by doing the initial lookup with the
VMA iterator and then using it to find the next entry.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

binfmt_elf: Take the mmap lock when walking the VMA list

I'm not sure if the VMA list can change under us, but dump_vma_snapshot()
is very careful to take the mmap_lock in write mode.  We only need to
take it in read mode here as we do not care if the size of the stack
VMA changes underneath us.

If it can be changed underneath us, this is a potential use-after-free
for a multithreaded process which is dumping core.

Fixes: 2aa362c49c31 ("coredump: extend core dump note section to contain file names of mapped files")
Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>

coredump: Remove vma linked list walk

Use the Maple Tree iterator instead.  This is too complicated for the
VMA iterator to handle, so let's open-code it for now.  If this turns
out to be a common pattern, we can migrate it to common code.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>

binfmt_elf: Remove vma linked list walk

Use the VMA iterator instead.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

um: Remove vma linked list walk

Use the VMA iterator instead.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

optee: Remove vma linked list walk

Use the VMA iterator instead.  Change the calling convention of
__check_mem_type() to pass in the mm instead of the first vma in the
range.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

cxl: Remove vma linked list walk

Use the VMA iterator instead.  This requires a little restructuring
of the surrounding code to hoist the mm to the caller.  That turns
cxl_prefault_one() into a trivial function, so call cxl_fault_segment()
directly.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

xtensa: Remove vma linked list walks

Use the VMA iterator instead.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

x86: Remove vma linked list walks

Use the VMA iterator instead.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

s390: Remove vma linked list walks

Use the VMA iterator instead.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

powerpc: Remove mmap linked list walks

Use the VMA iterator instead.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

parisc: Remove mmap linked list from cache handling

Use the VMA iterator instead.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

arm64: Remove mmap linked list from vdso

Use the VMA iterator instead.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

mm/mmap: Change do_brk_munmap() to use do_mas_align_munmap()

do_brk_munmap() has already aligned the address and has a maple tree
state to be used.  Use the new do_mas_align_munmap() to avoid
unnecessary alignment and error checks.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

mm/mmap: Reorganize munmap to use maple states

Remove __do_munmap() in favour of do_munmap(), do_mas_munmap(), and
do_mas_align_munmap().

do_munmap() is a wrapper to create a maple state for any callers that
have not been converted to the maple tree.

do_mas_munmap() takes a maple state to mumap a range.  This is just a
small function which checks for error conditions and aligns the end of
the range.

do_mas_align_munmap() uses the aligned range to mumap a range.
do_mas_align_munmap() starts with the first VMA in the range, then finds
the last VMA in the range.  Both start and end are split if necessary.
Then the VMAs are unlocked and removed from the linked list at the same
time.  Followed by a single tree operation of overwriting the area in
with a NULL.  Finally, the detached list is unmapped and freed.

By reorganizing the munmap calls as outlined, it is now possible to
avoid extra work of aligning pre-aligned callers which are known to be
safe, avoid extra VMA lookups or tree walks for modifications.

detach_vmas_to_be_unmapped() is no longer used, so drop this code.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

mm/mmap: Move mmap_region() below do_munmap()

Relocation of code for the next commit.  There should be no changes
here.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

mm: Remove vmacache

By using the maple tree and the maple tree state, the vmacache is no
longer beneficial and is complicating the VMA code.  Remove the vmacache
to reduce the work in keeping it up to date and code complexity.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

mm/mmap: Use advanced maple tree API for mmap_region()

Changing mmap_region() to use the maple tree state and the advanced
maple tree interface allows for a lot less tree walking.

This change removes the last caller of munmap_vma_range(), so drop this
unused function.

Add vma_expand() to expand a VMA if possible by doing the necessary
hugepage check, uprobe_munmap of files, dcache flush, modifications then
undoing the detaches, etc.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

mm: Use maple tree operations for find_vma_intersection() and find_vma()

Move find_vma_intersection() to mmap.c and change implementation to
maple tree.

When searching for a vma within a range, it is easier to use the maple
tree interface.  This means the find_vma() call changes to a special
case of the find_vma_intersection().

Exported for kvm module.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

mm/mmap: Change do_brk_flags() to expand existing VMA and add
do_brk_munmap()

Avoid allocating a new VMA when it a vma modification can occur.  When a
brk() can expand or contract a VMA, then the single store operation will
only modify one index of the maple tree instead of causing a node to
split or coalesce.  This avoids unnecessary allocations/frees of maple
tree nodes and VMAs.

Use the advanced API for the maple tree to avoid unnecessary walks of
the tree.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

mm/khugepaged: Optimize collapse_pte_mapped_thp() by using vma_lookup()

vma_lookup() will walk the vma tree once and not continue to look for
the next vma.  Since the exact vma is checked below, this is a more
optimal way of searching.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

mm: Optimize find_exact_vma() to use vma_lookup()

Use vma_lookup() to walk the tree to the start value requested.  If
the vma at the start does not match, then the answer is NULL and there
is no need to look at the next vma the way that find_vma() would.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

xen: Use vma_lookup() in privcmd_ioctl_mmap()

vma_lookup() walks the VMA tree for a specific value, find_vma() will
search the tree after walking to a specific value.  It is more efficient
to only walk to the requested value as this case requires the address to
equal the vm_start.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

mmap: Change zeroing of maple tree in __vma_adjust

Only write to the maple tree if we are not inserting or the insert isn't
going to overwrite the area to clear.  This avoids spanning writes and
node coealescing when unnecessary.

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>

mm: Remove rb tree.

Remove the RB tree and start using the maple tree for vm_area_struct
tracking.

Drop validate_mm() calls in expand_upwards() and expand_downwards() as
the lock is not held.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

mm: Convert vma_lookup() to use the Maple Tree

Unlike the rbtree, the Maple Tree will return a NULL if there's
nothing at a particular address.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>

proc: Remove VMA rbtree use from nommu

These users of the rbtree should probably have been walks of the
linked list, but convert them to use walks of the maple tree.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>

damon: Convert __damon_va_three_regions to use the VMA iterator

This rather specialised walk can use the VMA iterator.  If this proves
to be too slow, we can write a custom routine to find the two largest
gaps, but it will be somewhat complicated, so let's see if we need it
first.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>

kernel/fork: Use maple tree for dup_mmap() during forking

The maple tree was already tracking VMAs in this function by an earlier
commit, but the rbtree iterator was being used to iterate the list.
Change the iterator to use a maple tree native iterator and switch to
the maple tree advanced API to avoid multiple walks of the tree during
insert operations.  Unexport the now-unused vma_store() function.

We track whether we need to free the VMAs and tree nodes through RCU
(ie whether there have been multiple threads that can see the mm_struct
simultaneously; by pthread(), ptrace() or looking at /proc/$pid/maps).
This setting is sticky because it's too tricky to decide when it's safe
to exit RCU mode.

For performance reasons we bulk allocate the maple tree nodes.  The node
calculations are done internally to the tree and use the VMA count and
assume the worst-case node requirements.  The VM_DONT_COPY flag does
not allow for the most efficient copy method of the tree and so a bulk
loading algorithm is used.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>

mm/mmap: Use maple tree for unmapped_area{_topdown}

The maple tree code was added to find the unmapped area in a previous
commit and was checked against what the rbtree returned, but the actual
result was never used.  Start using the maple tree implementation and
remove the rbtree code.

Add kernel documentation comment for these functions.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

mm/mmap: Use the maple tree for find_vma_prev() instead of the rbtree

Use the maple tree's advanced API and a maple state to walk the tree
for the entry at the address of the next vma, then use the maple state
to walk back one entry to find the previous entry.

Add kernel documentation comments for this API.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>

mm/mmap: Use the maple tree in find_vma() instead of the rbtree.

Using the maple tree interface mt_find() will handle the RCU locking and
will start searching at the address up to the limit, ULONG_MAX in this
case.

Add kernel documentation to this API.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

mmap: Use the VMA iterator in count_vma_pages_range()

This simplifies the implementation and is faster than using the linked
list.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>

mm: Add VMA iterator

This thin layer of abstraction over the maple tree state is for
iterating over VMAs.  You can go forwards, go backwards or ask where
the iterator is.  Rename the existing vma_next() to __vma_next() --
it will be removed by the end of this series.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>

mm: Start tracking VMAs with maple tree

Start tracking the VMAs with the new maple tree structure in parallel
with the rb_tree.  Add debug and trace events for maple tree operations
and duplicate the rb_tree that is created on forks into the maple tree.

The maple tree is added to the mm_struct including the mm_init struct,
added support in required mm/mmap functions, added tracking in
kernel/fork for process forking, and used to find the unmapped_area and
checked against what the rbtree finds.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>

Maple Tree: Add new data structure

The maple tree is an RCU-safe range based B-tree designed to use modern
processor cache efficiently.  There are a number of places in the kernel
that a non-overlapping range-based tree would be beneficial, especially
one with a simple interface.  The first user that is covered in this
patch set is the vm_area_struct, where three data structures are
replaced by the maple tree: the augmented rbtree, the vma cache, and the
linked list of VMAs in the mm_struct.  The long term goal is to reduce
or remove the mmap_sem contention.

The tree has a branching factor of 10 for non-leaf nodes and 16 for leaf
nodes.  With the increased branching factor, it is significantly shorter than
the rbtree so it has fewer cache misses.  The removal of the linked list
between subsequent entries also reduces the cache misses and the need to pull
in the previous and next VMA during many tree alterations.

Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>

radix tree test suite: Add support for slab bulk APIs

Add support for kmem_cache_free_bulk() and kmem_cache_alloc_bulk() to
the radix tree test suite.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

radix tree test suite: Add allocation counts and size to kmem_cache

Add functions to get the number of allocations, and total allocations
from a kmem_cache.  Also add a function to get the allocated size and a
way to zero the total allocations.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

radix tree test suite: Add kmem_cache_set_non_kernel()

kmem_cache_set_non_kernel() is a mechanism to allow a certain number of
kmem_cache_alloc requests to succeed even when GFP_KERNEL is not set in
the flags.  This functionality allows for testing different paths though
the code.

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>

radix tree test suite: Add pr_err define

define pr_err to printk

Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

Linux 5.15-rc3