maple_tree: Rework mas_mab_cp()

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

maple_tree: Only zero request_count in mas_pop_node() if needed

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

maple_tree: Rework mas_ascend()

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

maple_tree: Rework mas_next_nentry

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

maple_tree: A bunch of optimizations

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

maple_tree: Use memset in mas_reuse_node on arrays

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

maple_tree: Retrun boolean from mas_rebalance()

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

maple_tree: Optimize mast_sibling_rebalance_right()

Only set the data when needed

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

maple_tree: Save maple_type in mast_topiary()

It is used more than once

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

maple_tree: Use mas_data_end in mas_next_sibling()

This should be faster for allocation ranges.

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

maple_tree: Rework mas_first_entry() for leaf case

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

maple_tree: Save node to avoid duplicate calls

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

maple_tree: Remove unnecessary call in mas_ascend()

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

maple_tree: Change some larger functions to not be inline

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

maple_tree: Remove BUG_ON for meta setting

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

maple_tree: Remove slot shift calculations.

Slot shift is always 3 now, so don't calculate it.

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

maple_tree: Change check on mas_prev() loop.

Don't check if it is searchable as the only possibility is mas_is_none()

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

maple_tree: Move all searching to common debug area

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

maple_tree: Remove unnecessary check for mas_next_nentry().

Don't need to check if r_start is out of range of node.

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

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>