Wip: broken, vma_expand

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>

maple_tree: Optimize gap calcs

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

maple_tree: Drop if 0 code

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

maple_tree: Fix resetting depth to preserve depth for external mas calls

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

maple_tree: Add mas_node_cnt() to allocate enough nodes in a mas

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

maple_tree: wip for fast path

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

maple_tree: Add validation for nulls in non-leaves

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

maple_tree: Add CONFIG_MAPLE_RCU_DISABLED, drop full_cnt, optimize _mas_store

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

maple_tree: mas_parent_gap no longer updates limits

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

maple_tree: mas_max_gap() breaks out of loop on 0 pivot

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

maple_tree: mas_leaf_max_gap optimizations for ma_pivots

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

maple_tree: mas_data_end starts at offset mt_min_slots now

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

maple_tree: Optimize mab_mas_cp to use ma_pivots and ma_slots

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

mm/mmap: Introduce unlock_range() for code cleanup

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

mm: Change mmap do_brk_flags() to populate the existing VMA

do_brk_flags has already located the modified VMA, so just populate the
region.  Add mm_populate_vma() to mm/gup.c and call the new function
which ignores errors.

Benckmarks in KVM before:
$ ./mmtests/work/sources/wis-0-installed/brk1_threads
testcase:brk increase/decrease of one page
warmup
min:886150 max:886150 total:886150
min:901488 max:901488 total:901488
min:897594 max:897594 total:897594
min:897422 max:897422 total:897422
min:900700 max:900700 total:900700
min:900714 max:900714 total:900714
measurement
min:903016 max:903016 total:903016
min:901224 max:901224 total:901224
min:902626 max:902626 total:902626
min:900518 max:900518 total:900518

Benchmark in KVM after change:
/mmtests/work/sources/wis-0-installed/brk1_threads
testcase:brk increase/decrease of one page
warmup
min:895650 max:895650 total:895650
min:904936 max:904936 total:904936
min:904776 max:904776 total:904776
min:905358 max:905358 total:905358
min:908792 max:908792 total:908792
min:907648 max:907648 total:907648
measurement
min:904368 max:904368 total:904368
min:903936 max:903936 total:903936
min:904720 max:904720 total:904720
min:906626 max:906626 total:906626

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

mm/mmap: Change do_brk_flags() to expand existing VMA when possible.

Avoid allocating a new VMA when it is not necessary.  Expand the
existing VMA instead.  This avoids unnecessary tree manipulations.

kvm benchmark before
$ ./mmtests/work/sources/wis-0-installed/brk1_threads
testcase:brk increase/decrease of one page
warmup
min:561754 max:561754 total:561754
min:578322 max:578322 total:578322
min:581282 max:581282 total:581282
min:572182 max:572182 total:572182
min:572572 max:572572 total:572572
min:580408 max:580408 total:580408
measurement
min:578786 max:578786 total:578786
min:574780 max:574780 total:574780
min:577166 max:577166 total:577166
min:581240 max:581240 total:581240
min:580700 max:580700 total:580700
min:584612 max:584612 total:584612

benchmark after
$ ./mmtests/work/sources/wis-0-installed/brk1_threads
testcase:brk increase/decrease of one page
warmup
min:886150 max:886150 total:886150
min:901488 max:901488 total:901488
min:897594 max:897594 total:897594
min:897422 max:897422 total:897422
min:900700 max:900700 total:900700
min:900714 max:900714 total:900714
measurement
min:903016 max:903016 total:903016
min:901224 max:901224 total:901224
min:902626 max:902626 total:902626
min:900518 max:900518 total:900518
min:900630 max:900630 total:900630
min:901432 max:901432 total:901432

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

maple_tree: Fix formatting of extend null

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

maple_tree: Restore maple tree node fullness.

Rework mas_is_span_wr, mas_node_walk.

Add dup null check

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

maple_tree: Add extra trace events to test code

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

kernel/fork: Drop vma_store entirely

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

maple_tree tracepoints: Add trace for span_wr, store_range, erase, load

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