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>

mmap trace: Change maple tree mods to use px

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

mmap: Remove __vma_link in favour of calling vma_mt_store directly

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

mm: Remove vma_stre and __vma_link_rb from header

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

maple_tree: Don't initially set pivot in data_end.

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

maple_tree: Alias rcu check to mas_slot() and mas_slot_protected

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

maple_tree: Avoid case statements with ma_gaps and ma_pivots

Get the arrays and use them directly instead of switching on type every
time a value is needed.

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

maple_tree: Optimize mas_awalk

Search from the back of the node without finding the end of the data
first.

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

maple_tree: Rework mas_next

Attempt to optimize mas_next

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

mm/mmap: Fix accounting in count_vma_pages_range again

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

mm/mmap: Fix accounting in count_vma_pages_range

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

kernel/fork: Use mas_dup_store for quicker forking

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

maple_tree: Add mas_dup_store for quicker forking

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

maple_tree: cleanup

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

maple_tree: Don't check lockdep on things that may just be readers

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

maple_tree: Rework mas_prev_node

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

maple_tree: Rework mas_next_node again

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

maple_tree: Rewrite mas_next_node to be less complex.

Remove double while (1) loop, pull in parent slot lookup.

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

maple_tree: Update mas_next_node comments and break for end of node

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

maple_tree: use ma_get_slots() in mas_next_node loop

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

maple_tree: rework mas_prev_node loop

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

maple_tree: Change mas_get_slot to only rcu_dereference when necessary

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

maple_tree: Use get_slots for extend_null

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

maple_tree: Drop mte_get_slot(), _mte_get_slot(), ma_get_slot() and use
mas_get_slots most places.

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

maple_tree: Change mas_replace to use ma_get_slots

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

maple_tree: Change more to use ma_get_slots

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

maple_tree: Change adopt_Children to use ma_get_slots

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

maple_tree: use mte_slots for dup

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

maple_tree: Start using mte_slots more

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

maple_tree: Comments

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

maple_tree: Remove recursive call for ma_get_node_alloc_cnt, and rename function

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

maple_tree: Renames to remove _get and comments on some functions

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

maple_tree: Remove comment for range 16 node types in mte_set_parent

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

maple_tree: Add new lines where necessary

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

maple_tree: Remove unnecessary check from next_nentry

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

maple_tree: mas_data_end reduction #2

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

maple_tree: mas_data_end reduction.

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

maple_tree: Drop extra node types and mt_is_empty()

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

maple_tree: Rename functions and variables

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

maple_tree: Optimizations on mas_data_end and mas_rev_awalk

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

maple_tree: Fix endif comment

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

maple_tree: remove _mas_data_end, only used in a few places

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

mm and fork: Fix mtree_destroy path

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

maple_tree: Fix rcu flag again.

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

maple_tree: Lower efficiency of node use.

Split when there is a slot left to avoid overflow situation on a triple
split.  This is to avoid reworking the node estimate calculations prior
to actually removing the node estimate calculations in favour of
assuming no failures.

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

radix tree test suite: Fix compilation

Introducing local_lock broke compilation; fix it all up and move the
local_lock header to be included alphabetically.

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

maple_tree: Add newlines after functions

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