maple_tree: Optimizer mas_node_walk() by removing special case.

Check if offset is set is no longer necessary in the loop as it is done before.
Also, check after checing index <= max.

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

maple_tree: Optimize _mas_store() slow path

When entering the slow path, only zero what is necessary after the data is set.
Also, don't calculate things twice when not necessary

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

maple_tree: Use a variable for b_node->b_end

Makes cleaner code and less dereferences

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

maple_tree: Change mas_descend_adopt() to not set offset.

Instead, reset the offset in mas_new_child() as the data is already being accessed.

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

maple_tree: mas_first_entry() optimization

Remove loop in favour of checking pivot 0 or 1 as one mus have a value.

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

maple_tree: Remove BUG_ON() debug

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

maple_tree: Change __mas_walk and mas_wr_walk to directly use type.

The node type is known, so don't look it up again

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

maple_tree: Set max only when needed in mas_is_span_wr()

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

maple_tree: Add append operation

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

maple_tree: Code cleanup.

remove unnecessary braces, space, and add an unlikely to __mas_walk()

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

maple_tree: Change mab_split_calc() to do bulk calc first.

Do the bulk calc first if necessary.

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

test_maple_tree: Increase bench_forking() nr_fork.

Time was getting too low

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

maple_tree: Speed up reverse allocation walks.

Rewrite loops to be quicker by removing special cases.
Also skip the next slot if a leaf has a gap that is not large enough.

Benchmarks of BENCK_AWALK below:

Old:
./maple  13.57s user 0.00s system 99% cpu 13.596 total

New:
./maple  11.87s user 0.01s system 99% cpu 11.936 total

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

maple_tree: Optimize mas_get_empty_area{_rev}() etc

Take advantage of locality of reference by not dereferencing in some functions.

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

test_maple_tree: Increase bench_awalk() count

Speedups have dropped this testcase below 10s, so increase it.

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

test_maple_tree: Fix mtree_alloc_rrange to search for exclusive end

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

mm/mmap: Convert unmapped_area_topdown() search to be inclusive search.

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

maple_tree: stop _mas_get_empty_area() from converting to inclusive search.

This should be done in the mm code

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

maple_tree: optimize mas_rev_awalk and mas_awalk a bit

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

maple_tree: optimize some more

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

maple_tree: Make some common functions faster.

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

maple_tree: Optimize mas_leaf_max_gap() by skipping slots after a gap.

Two gaps cannot happen in a row, so don't bother checking the next slot if there exists a gap.
Also, remove slot[0], slot[1], and slot[max] by checking them first.  This allows for a more
optimal loop

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

mm/mmap: Change do_brk_munmap() to use do_mas_align_munmap()

do_brk_munmap() already has aligned addresses.

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

mm/mmap: Don't mas_set in mma_region() to avoid a mas_reset()

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

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>