maple_tree: Fix tests and search mess

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

mm/mmap: Linked list fallout

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

mm/mlock: Fix mas_for_each() loop limit

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

mm/memory: Fix free_pgtables loops and such

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

linked list mess

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

fs/proc/task_mmu: Fix mas_reset stuff

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

mm/mmap: Fix do_mas_align_munmap() last searching.

Probably linked list fallout?

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

fs/coredump: linked list fallout

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

mm/mmap: Linked list fallout

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

maple_tree: Drop commented out printks

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

mm: linked list many+2

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

mm/mmap: linked list work.. part many+2 of many

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

mm: linked list many+1

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

mm/mmap: linked list work.. part many of many

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

mm: WIP linked list process

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

maple_tree: Stop using linked list in most cases

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

mm/mmap: Only check next vma in brk within range.

Only check if the next vma is within a page + stack_guard_gap of the planned
end of newbrk

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

mm/mmap: Avoid clobbering other VMAs in brk()

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

maple_tree: mas_mab_cp() rework attempt 2

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

maple_tree: Make mas_max_gap() only set gaps when necessary

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

maple_tree: mas_leaf_max_gap() JIT setting of vars

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

maple_tree: mas_data_end() JIT setting of vars

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

maple_tree: Fix mas_destroy_rebalance() rework

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

Revert "maple_tree: Rework mas_mab_cp()"

This reverts commit 29e569389983582d6b6a007ca26d8eb568785648.

maple_tree: Reduce _mas_store() code a bit

Also, wth about that else in ma_root_ptr??

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

maple_tree: Optimize mas_prev_node()

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

maple_tree: Don't pass contents to expand_root()

it's not used

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

maple_tree: Optimize mas_next() and drop unused mas_first_entry() user.

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

maple_tree: Optimize mas_prev() path.

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

maple_tree: mas_store, mas_store_gfp, mas_nomem restructre

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

maple_tree: Formatting of arguments, noting interesting

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

maple_tree: Rework mas_destroy_rebalance()

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

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>