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>

wip: maple_tree: factor out descend and node adoption

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

wip: maple_tree: factor out descend and node adoption

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

wip: pass 747201.  Rework some gap stuff.

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

wip: pass 747114 - fix r_mas.max when there is no r_mas.max for skipping data

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

wip: Add height reset to destroy and debug output.

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

wip: pass 678642 tc

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

maple_tree: wip, initial rebalance on regular commit, fixes for spanning store, adoption, gaps..

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

wip: spanning store & signed full_cnt

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

maple_tree: WIP, start passing big data through for all stores

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

maple_tree: WIP, diet

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

maple_tree: WIP, partial spanning store code.

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

maple_tree: 3 wip

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

wip, broken and abandoning this plan for no retry

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

maple_tree: Remove mt_is_advanced in favor of xa_is_advanced.

The two functions are now the same so just use the xa_ version.

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

xarray: Change range of xa_is_advanced

XA_ZERO_ENTRY is the is largest advanced internal entry.
Return true if an internal entry is less than the XA_ZERO_ENTRY.

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

maple_tree: Fix gap issues and combining issue

Incorrect gap calculation caused by mas_prev not setting the ma_state
limits correctly.

Gap relocation failed due to fully empty node (deleted)

Gap relocation issues when hitting a retry entry

Missing data due to combining nodes incorrectly when the right node has
a retry at the start.

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

maple_tree and mm/mmap: Try to stop tracepoints on BUG_ON

Restore printk's until we know it happens.

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

trace/events/mm_mt.h: Fix prototype for __vma_mt_szero

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

trace/events/mm_mt: Add maple tree mm tracepoints.

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

trace/events/mm rename to mm_mt

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

mm/mmap: Fix unmapped_area_topdown with align_offset

align_offset should be aligned to align_mask.. apparently.

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

mm/mmap: Move maple tree logging to tracepoints

Able to toggle at runtime? Count me in.

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

mm/mmap: Fix maple tree calculation for topdown with alignment mask.

When using alignment mask, calculate the address correctly.

Found by LTP futex_wake04

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

maple_tree: Add test for reverse search with mask.

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

mm/mmap: Add call to maple_destroy

When tearing down a vma, destroy the maple tree as well.

Also clean up some old print debugs.

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

maple_tree: Fix mas_append of extra null.

When attempting to append to a node, it is possible that the source
contains multiple NULL entries that will be coalesced together and thus
will not overflow even though it may appear that was on initial
inspection.

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

maple_tree: Skip multiple deletes in split calculation.

When splitting, do not split within consecutive NULL entries.  Doing so
would cause separated gaps.

Also reset mas->node before walking in two other places which could
potentially cause issue.

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

maple_tree: Reset mas location before walking in mas_rebalance_gaps.

After rebalancing, the mas node may not be in the correct location to
find the mas->index, so reset to MAS_START prior to starting the walk.

Added test case for this issue as well.

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