mm/mmap: rework do_mas_munmap() and friends

Pull out alignmnet calculations for functions that have already aligned

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

mm/mmap: move populate calc in vm_brk_flags() ouside the mmap_write_unlock

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

mm/mmap: Fix do_brk_flags and do_brk_munmap locking.

Also use the knowledge of finding a mapping at newbrk to know that a munmap is
necessary.

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

test_maple_tree: Add tests for prev/next

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

test_maple_tree: Fix test harness for new next/prev interface

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

maple_tree: Fix mas_next() and mas_walk() setting index/last.

Ensure that the last/index is set regardless of if there is a value found.  This
is necessary to ensure prev/next work as expected.  Also update mas_find() to
this new functionality

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

maple_tree: Fix mas_prev() from skipping entries.

When searching backwards, if the node wasn't fully full then the pivot could
be zero and thus return there was no previous entry in the node.  Also set
mas.last/mas.index to ensure correct prev/next functions

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

maple_tree: Clean up mas_node_store() by using local var

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

mm/mmap: Rework brk() to take interval tree locks when necessary

interval tree locks are necessary for expand/contract of VMAs so use them.
This path is also rather slow and cannot be taken if the anon_vma_chain is
not a singular list

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

mm/mmap: Move __vma_adjust update of highest_vm_end

Move the highest_vm_end update to avoid checking if the end changed more than once.

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

mmap: mmap_region() Remove mas_reset() as it will happen if needed

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

test_maple_tree: Disable benchmarks

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

maple_tree: Optimize mas_reuse_node() loop

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

maple_tree: Optimize mas_node_walk() and standardize __mas_walk() a bit

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

test_maple_tree: tweak bench_walk()

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

test_maple_tree: Add bench_walk()

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

maple_tree: mas_node_walk() could never return false

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

mmap: make remove_vma_list() inline

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

mmap: Avoid modifying maple tree in __vma_adjust more than necessary

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

mmap: mmap_region() whitespace fix

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

mmap: mmap_region() whitespace fix

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

mmap: Remove __do_munmap() in favour of do_mas_munmap()

Export new interface and use it in all places necessary including mremap.

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

mmap: Don't reset mas until needed in mmap_region()

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

mmap: Use find_vma_intersection in do_mmap() for overlap

When detecting a conflict with MAP_FIXED_NOREPLACE, using the new interface avoids
the need for a temp variable

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

mmap: Update count_vma_pages_range() to only use one ma_state

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

mmap: Update mmap_region() to use do_mas_munmap()

Use the maple state to avoid multiple walks of the tree

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

mm/mmap: Add do_mas_munmap() and wraper for __do_munmap()

To avoid extra tree work, it is necessary to support passing in a maple state
to key functions.  Start this work with __do_munmap().

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/mmap: Change __do_munmap() to use a ma_state

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

mm/mmap: Fix mmap_region() potential issue

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

maple_tree: Drop mas_tree_gap & pass more through from _mas_store

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

mm/mmap: Whitespace fix

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

test_maple_tree: Move benchmarking defines and encapsulate functions

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

mm/mmap: Change __do_munmap() to avoid unnecessary lookups.

As there is no longer a vmacache, find_vma() is more expensive and so avoid doing them

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

maple_tree: Fix __mas_next() when the limit is hit

When a search limit is hit, restore the previous location so that
mas_next() works on that particular ma_state.

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

test_maple_tree: Fix defines

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

testing: radix-tree changes cleanup

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

maple_tree: Code clean up

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

mm: Clean up modifications

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

mm: Remove vmacache

The maple tree is able to find a VMA quick enough to no longer need the
vma cache.  Remove the vmacache to reduce work in keeping it up to date
and code complexity.

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

maple_tree: More efficient rev_awalk and mas_next()

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

mm/mmap: Change vma->vm_mm to mm

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

mm/mmap: Fix unlock range un do_munmap

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

maple_tree: Clean up mas_ascend() on root parent

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

maple_tree: reset mas->node to MAS_START in mas_next() if it's MAS_NONE

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

mm/mmap: Drop munmap_vma_range()

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

maple_tree: When mas_walk() is called in mas->node == MAS_NONE, reset to MAS_START

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

mm/mmap: Change mmap_region to use maple tree state

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

mm/mmap: Fix do_brk_munmap() multiple pages.

This is rare, so just use the slower __do_munmap()

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

mm/mmap: Call __do_munmap() on slow path of do_brk_munmap()

do_brk_munmap() would not handle the unmapping of multiple VMAs in the case of
mprotect'ed regions of a brk() so just use the full __do_munmap() in these
rare cases.

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

mm/mmap: Finish converting brk() to using a maple state

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

maple_tree: Add mas_store_gfp() and fix mas_prev() and mas_store()

When searching for the previous value, walk the node first.  Don't just assume we are looking for the
last entry if it's MAS_START.

mas_store() and mas_destroy() now workk better with MAS_START as well.

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

maple_tree: Optimizations and whitespace.  nothing interesting

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

maple_tree: whitespace

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

test_maple_tree: Make bench_slot_store() more realistic

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

maple_tree: Optimize __mas_next a bit, I hope

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

maple_tree: Add metadata to arange nodes.

Add a metadata into the arange64 nodes to tell the end and the largest gap slot.

This is used to speed up various activities on the node, especially finding the
end of the data and updating the gap.

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

mm_types: Drop more rb tree from vm_area

Note: Need to fix NOMMU code
Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>

mm/mmap: Fux mm->map reference to mm->mmap after rebase

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

mmm/mmap: Fix differences after rebase

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

maple_tree: Rework MA_STATE_BULK and MA_STATE_REBALANCE

Set MA_STATE_BULK when setting the expected number of store events.

Only rebalance the end node when it is deficient.

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

test_maple_tree: Add bench_slot_store()

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

maple_tree: Drop 128B node support

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

maple_tree: Fix _mas_store() expand null

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

maple_tree: Rename MA_STATE_ defines

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

maple_tree: Don't use mas_extend_null in _mas_store()

mas_extend_null() is too heavy when the nulls are contained within a single node.

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

test_maple_tree: Drop dump in check_ranges()

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

maple_tree: Reduce variables by using mas->offset directly.. more.

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

maple_tree: Reduce variables by using mas->offset directly

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

maple_tree: Remove mas_offset() and mas_set_offset() now that offset is in ma_state directly

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

mm/mmap: Fix vma locking on brk

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

maple_tree: Some optimizations, I hope

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

maple_tree: Fix _mas_store() rmin expansion on null.

When the offset changes on expanding null, ensure the min slot value changes
as well.  This avoids a fall-through to the slow path and uses the
mas_node_store() instead.

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

kernel/fork: Update maple tree interface.

Start using the number of entries directly, and mas_destroy().

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

maple_tree: Implement optimized fork splitting.

When using mas_for_each with pre-allocations, split so that there are
more slots available to the left.  If this results in an insufficient
node to the left, then rebalance on mas_destroy().

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

maple_tree: Fix mas_alloc_push() overflow

mas_alloc_push() was overflowing and writing the next node.  Add #define to
clean up the alloc slot calculations

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

test_maple_tree: Add more allocation checks around overflow

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

maple_tree: Fix allocation issues

Ensure no overflow on mas_alloc_nodes()
Use allocated instead of calling mas_allocated() multiple times
Fix mas_set_alloc_req() to set the value and not add it.

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

test_maple_tree: Test poping all pushed nodes to ensure mas_allocated is set correctly

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

maple_tree: Add better allocation testing and relax push_left to avoid jitters

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

test_maple_tree: Add check_forking()

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

maple_tree: clean up a few small things

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

maple_tree: Fix mas_for_each limits on index when searching for first entry in node

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

mm/mmap: Fix unnecessary locking of anon_vma on expanding of a vma.

When expanding the end of a vma, it is unnecessary to loc the anon_vma tree for writing
because the spinlock on the vma tree ensures that there are no concurrent vma expansions

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

maple_tree_test: Fix compile warnings

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

maple_tree: Fix mas_alloc_nodes() off by one in bulk alloc

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

maple_tree: Switch to kmem_cache_alloc_bulk() instead of single node allocations

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

tools/testing/radix-tree: Add keme_cache_alloc_bulk() support

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

maple_tree: Add mas_node_store() and fix issue with mas_slot_store()

Add mas_node_store when alterations can be contained within a single node.

Rename mas_fast_store to mas_slot_store.
Fix issue with mas_fast_store getting the wrong range when expanding nulls back.  The range
max was not being updated.

Add testcases for benchmarking and fix forking benchmark

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

test_maple_tree: change cnt to count

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

maple_tree: cnt => count

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

maple_tree: Add mas_free to push unused nodes

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

mm/mmap: Fix memory leak by maple tree

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

maple_tree: Export mas_empty_alloc() for mas_for_each pre-allocations

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

maple_tree: Fix ltp shmt09 by checking if vma->vm_anon before locking in vma_mt_brk()

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

mm/mmap: brk fix

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

mm/mmap: Change vm_brk_flags() to use mm_populate_vma()

Skip searching for the vma to populate after creating it by passing in a pointer.

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

mm/mmap: Change do_brk_munmap/do_brk_flags().

do_brk_munmap needs to call vma_adjust_trans_huge() when altering the
vma size.

do_brk_munmap needs to support userfaults on umap.

do_brk_flags needs to take a pointer as it could return a new value that
needs to be populated.

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

maple_tree: Fix find_vma_intersction() cache update with possible incorrect addr

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

mm/mmap: Fix vma_adjust in tracking maple tree

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