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>

maple_tree: awalk is still massive

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

maple_tree: drop mas_next_slot and mas_prev_slot - unused

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

maple_tree: mas_prev_slot change

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

maple_tree: Cleaning

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

maple_tree: Cleaning

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

maple_tree: Cleaning

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

maple_tree: Drop deleted/retry/skip logic

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

maple_tree: Drop deleted/retry/skip logic

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: Comments, and also mab_mas_cp always uses 0 for the node start

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

maple_tree: Comments comments comments.

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

maple_tree: Remove mte_update_rcu_slot and add comments

mte_update_rcu_slot is the same as mte_set_rcu_slot, so drop it

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

cleanup mast_new_root

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

maple_tree: Drop unnecessary reset

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

maple_tree: mas_split cleanup

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

maple_tree: not much

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

maple_tree: combine_separate reduction with copy out to nodes

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

maple_tree: combine_separate reduction with parents and cp_left/cp_right

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

maple_tree: Cleaner check in combine_separate

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

maple_tree: Cleaner check in combine_separate

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

maple_tree: reduce line count

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

maple_tree: mas_mab_cp sets b_end now

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

maple_tree: Attempt to reduce split function size

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

maple_tree: wip, try the maple_subtree_state for smaller functions

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

maple_tree: wip, add maple_subtree_state

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

maple_tree: wip, add maple_subtree_state

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

maple_tree: Code cleanup, mostly in split

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

maple_tree: Start using b_node->b_end in mas_split

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

maple_tree: Remove fixed array size from mas_split and use ma_topiary instead.

Also, move common smp_wmb() from split and combine_separate function into a helper.

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

maple_tree: Code reduction

also move __mas_walk, mas_rewind_node, move mas_skip_node

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

maple_tree: mas_combine_separate changes.

Fix the calculation of node splitting when needing 3 nodes.

Change allocation count, spanning store may cause more allocations if
rebalancing across nodes occurs.

Remove free/destroy lists and use a linked list.

Weight reduction of the function.

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

mm/mmap: Change debug for maple tree

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: Add freeing of nodes.

Node freeing is tracked by what was consumed in the previous step and
freed along with what was overwritten in the spanning store that must be
destroyed.

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

maple_tree: wip, fix underrun on root expand when range starts at zero but ends elsewhere

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

maple_tree: wip, fix splitting into 3, fix range of combine_separate, fix test for gap_combining.

Splitting into 3 was not functioning due to an error in setting the parent and the split calc.

combine_separate was not copying the contents of the mas state over to orig_l_mas which became a problem with the limit checking the end of data.

gap_combining tests were rendered broken due to splitting changes with a NULL ending.

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

maple_tree: wip.  Combine mas_extend_null in mas_store and
mas_spanning_store.

Pass: 13130626 Run:13130627

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

wip, maple_tree: Pass 824089 - rebalance and spanning store using most of the same code now

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

wip, maple_tree: Pass 850785 - added check for min node size.  need to rebalance spanning store

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