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>

maple_tree: Fix dup tree walk up and add more testcases.

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

fork: Now with dup tree

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

maple_tree: Add dup function and testing

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

maple_tree: remove extra mt_dump calls from test code

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

maple_tree: Fix append to work with allocation tree.

Append wasn't happening with allocation tree due to the ZERO entry being
added.  Stop addign the zero entry, it should be in the mm code anyways.

Also, add gap support when appending.

Also, fix parent pointer assignment on push_left operations.

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

maple_tree: remove debug

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

maple_tree: Fix mas_awalk gap issues

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

maple_tree: compress to left

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

maple_tree: refactor mas_split data splitting

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

maple_tree: start pushing left for leaves

Also, remove dup code

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

maple_tree: Add 256Byte nodes and make them default.

This code adds a define to decide which node size: 128 or 256.  Defaults
to 256.

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

maple_tree: Make allocations node size agnostic

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

maple_tree: Fix trace test code

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

maple_tree: Fix compile warning

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

maple_tree: Fix trace header

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

maple_tree: Fix tracing order

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

mmap: Rework tracing

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

tboot remove rb

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

tboot add mt

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

maple: Fix tracepoints

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

radix tree: enhancements for maple_tree tracepoints

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

maple_tree: Change ordering of pivots and slots, as well as gaps in one
case.

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

mm/mmap.c: Fix includes for tracepoints

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

maple_tree: Add tracepoints, remove SLAB_RECLAIM

Also reorder setting of slot in mas_Descend_adopt and fix comment for smp_wmb

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

maple_tree: Clean up splitting name and add exception to validate

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

maple_tree: Fix splitting causing deficient nodes.

When splitting a node, ensure a deficient node is not created when a
NULL in encountered at the split.  Also adjust the checking of the limit
when incrementing to ensure both the min and the number on the right are
zero based.

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

maple_tree: Fix overflow on store and 3 way splits

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

mm/mmap: Zero maple tree area in a single set when detatching

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

fork: Whitespace

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

mm/mmap: Drop mas.node check.

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

maple_tree: Remove possibility of having mas->node null

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

mmap: rename unmapped to empty, change comemnts

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

mm: Remove rb tree.

Remove the RB tree and start using the maple tree for vm_area_struct
tracking.

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

kernel/fork: Convert dup_mmap to use maple tree

Use the maple tree iterator to duplicate the mm_struct trees.

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

mm/mmap: Change unmapped_area and unmapped_area_topdown to use maple
tree

Use the new maple tree data structure to find an unmapped area.

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

mm/mmap: Change find_vma_prev() to use maple tree

Change the implementation of find_vma_prev to use the new maple tree
data structure.

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

mm/mmap: Change find_vma() to use the maple tree

Start using the maple tree to find VMA entries in an mm_struct.

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

mm: Start tracking VMAs with maple tree

Start tracking the VMAs with the new maple tree structure in parallel
with the rb_tree.  Add debug and trace events for maple tree operations
and duplicate the rb_tree that is created on forks into the maple tree.

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

maple_tree: Fix crash on spanning rebalance all the way to root.

It is possible to have a spanning rebalance that causes 3 new nodes per
level and a new level added in a new root node.  This means that
allocations need to be 3 * height + 1, and this situation needs to be
detected so that dead root isn't attempted to ascend looking for more
data to merge in.

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

radix tree test suite: Add support for fallthrough attribute

Add support for fallthrough on case statements.  Note this does *NOT*
check for missing fallthrough, but does allow compiling of code with
fallthrough in case statements.

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

maple_tree: Update unmapped area name, remove mas->node == NULL
possibility, 3 way split fixes, overflow slot fix, calc split fix,
altered descend adopt algorithm.

Many changes.

1. unmapped area => empty area
2. mas->node can no longer be null
3. splitting into 3 nodes can occur at non-leaf nodes.
4. calc split could potentially create an overflow or a deficient node.
5. drop Private from comments
6. comment fixes
7. rename combine_separate to mas_spanning_rebalance

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

test_maple_tree: Re-enable failed test from allocation issue

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

mm/mmap: Disable maple_tree_verbose and remove mas_retry

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

maple_tree: rework mas_awalk

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

maple_tree: rev_awalk i->slot and this_gap -> gap

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

maple_tree: change rev_awalk to more common code

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

maple_tree: change rev_awalk since there are no delete or skips, etc

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

maple_tree: Add helper for lower bound

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

maple_tree: awalk reduce again.

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