mm: WIP, trying to avoid splitting is a mess.

If you split this VMA, then it is inserted into the tree.  Instead, we
try to create a dummy VMA and pass that along to handle freeing.  Unfortunately,
the hugetlb cases seem to require the file handle to be correctly processed
in the unmap_single_vma() call path.  There may be memory leaks in the cases
where we are not a hugetlb page, but I didn't see that.

The unfornate part is that we have to insert ourselves into the interval tree
when we try to do more with the VMA.

For now, let's just go back to something that is less of a mess

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

mm/mmap: Fix vm_pgoff in vma_shorten()

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

mm/mmap: Fix vma_shorten() to correctly set vm_pgoff and vm_flags

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

mm/mmap: __do_munmap() Add maple state support.

Adding ma_state support means costly walks through the tree can be
avoided most of the time.  The write operation can simply store the
value at the location previously searched.

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

mm/mmap.c: whitespace and brace fixes

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

mm/mmap: Rewrite __do_munmap() to be more maple tree friendly

Before going full-blown ma_state on __do_munmap(), do better on splits
by avoiding cloning a tmp VMA and just allocate one on the stack to be
discarded.  In the case of a double-adjust of the start and end vma,
then a duplication is unavoidable and handled in the slow path as
before.

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>

kernel/fork: Adjust maple calls

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

mas_entry_cnt() rename and cleanup

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

maple_tree: Return NULL on unlikely not found case.

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

maple_tree: Set offset out of range on mas_is_ptr in _mas_walk()

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

maple_tree: Return false if _mas_walk is a ptr and mas->index != 0

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

maple_tree: Drop span_enode to get ma_state to one cacheline

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

maple_tree: Change hard-coded 127 to MAPLE_NODE_MASK

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

mm/mmap: Clean up brk modifications

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

mm/mmap: Fix exit_mmap() call to unlock_range()

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

kernel/fork: Don't take spinlock of maple tree.

You cannot take the spinlock of the maple tree and then allocate VMAs.

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

maple_tree: Fix mte_destroy_walk() overwriting slots when spinlock debug is enabled.

When spinlock debug is enabled, the size fo the spinlock expands and causes the anon union
in maple_node to overwrite slots.  Fix this by only passing through the maple flags.

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

mm/mmap: Export find_vma_intersection to fix unresolved symbols in
modules

kvm was complaining that the static function has become an extern.

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

maple_tree: Fix double null

Google reported a double null in Android.  The captured reproducer is in
set42.  Issue was a store spanning offsets, so the entry before the
start offset and the entry after the end offset needs to be checked
instead of assuming the entry being added would write to a single
offset.

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

maple_tree: Fix mas_parent_gap() propigation upwards

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

maple_tree: Add missing mas_walk() which is part of the interface

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

maple_tree: Use ma_slots() instead of mas_get_slot() in _mas_awalk()

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

maple_tree: Rename range_walk to _walk, clean up mas_node_walk

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

maple_tree: optimize root expand

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

maple_tree: Drop dup_tree()

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

mm/mmap: Alter brk to be more maple tree efficient.

Alter the brk, do_brk_flags() calls and add do_brk_munmap() to be more
efficient when using the maple tree.

kvm Benchmark on 8 core laptop:
./mmtests/work/sources/wis-0-installed/brk1_threads

rb_tree v5.9-rc1:
min:3633758 max:3633758 total:3633758
min:3604892 max:3604892 total:3604892
min:3589182 max:3589182 total:3589182
min:3581230 max:3581230 total:3581230

maple tree with this patch:
min:3673408 max:3673408 total:3673408
min:3659268 max:3659268 total:3659268
min:3624968 max:3624968 total:3624968
min:3613576 max:3613576 total:3613576

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

mm: 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()

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

kernel/fork: Stop using dup tree and pre-allocate the nodes needed.

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

maple_tree: Export mas_entry_cnt to setup external mas.

When the number of elements are know, this can pre-allocate the set
number.

maple_tree: Fix validate on empty tree and some compile issue. crap.

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

maple_tree: Fix bug in mas_next_node and optimize _mas_next slightly

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

maple_tree: Add mas_root_locked() and mas_root(), rename protected() to locked()

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

maple_tree: Fix state for external mas

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