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>

maple_tree: Fix up after rebase v5.9-rc1 and history.

Rebased maple/mainline_verbose to v5.9-rc1 then to maple3, then
overwrote maple3.

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

maple_tree: Fix spanning_store testcases and then the code

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

maple_tree: Revert __mas_next change.

Thsi needs to be looked into, it seems mas_next reutrns null until the end of the node
instead of kicking out earlier

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

maple_tree: Fix spanning_rebalance across many nodes with a new root.

When spanning many nodes and creating a new root at a different level,
the spanning rebalance was not correctly installing the root node.

Also, rework test framework to test the above scenario correctly and add
a test (set41) to do so.

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

maple_tree: Fix rcu flag, ma_flags on dup of tree

Also move mas_cnt_positive up and use it elsewhere, set bn->type when spanning_balance has a new root

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

sched/mm and kernel/fork: Add maple tree rcu enable/disable

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

maple_tree: Add in_rcu flag support

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

maple_tree: Rename flags defines

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

maple_tree; rename mas_get/set_slot to mas_offset

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

maple_tree: Compress ma_height into ma_flags

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

maple_tree_test: Add verification of 1000 entry tree node count with rev alloc (top-down)

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

maple_tree: Add push right, use memmove for b_node shifting.

Also fix an error on the split calc discovered due to the push right.

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

maple_tree: Fix range calc on slot 0 and clean up empty_alloc. add rev_seq test

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

maple_tree: bulk free fixes

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

maple_tree: Fix test from dumping crap

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

maple_tree: Fix direct destroy

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

mmap stuff

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

linux.c stuff

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

maple_tree: Add non-rcu destroy_walk, rename ma_free to ma_free_rcu

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

radix-tree testing framework: Add kmem_cache_free_bulk

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

maple_tree: Alloc at most 1 page of nodes during fork.

Also fix a corner case of root + children being 17 and thus failing out during a fork

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