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>

mm/mmap: Move VM_BUG_ON inside other check for maple tree

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

maple_tree: Fix skip entries on spanning adds and issue in split data

When spanning adds hit a skip entry, they were not updated and thus
future events may use the incorrect minimum from the previous
not-updated pivot.  Fix these pivots when writing spanning adds.

There was also an issue with using the incorrect ranges in the split
code path in mas_append_split_data() which could cause data to be
skipped.  This is now fixed and there are testcases to test for the
discovered event.

The spanning add issue was tested with set25 in check_erase2_testset.

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

maple_tree: Fix off-by-one error on mas->min when calling mas_prev.

When using a non-zero slot, the mas->min was set incorrectly for
mas_prev causing the gap calculation to be off-by-one and verification
to fail.

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

test_maple_tree: Add test which discovered the retry limit issues.

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

maple_tree: Fix gap on skip entries caused by relocated data.

The gap should be zero for skip entries.

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

maple_tree: Fix overrunning end of node into RETRY entries.

When entries are moved and replaced with a RETRY, the node will end
prior to hitting a 0 pivot or the end of the node.  Fix this scenario by
detecting the pivot > mas->max and handle these cases correctly.

This also fixes the validation code to avoid checking the range on RETRY
entries.

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

maple_tree: Fix limits check with retry entries

When entries are relocated, the retry entry may not fall within the
limits of this node as it has been relocated to the next node.

Also, add define U8_MAX UCHAR_MAX in test code.

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

test_maple_tree: Don't count retry entries during entry counting.

retries are skipped, so don't count them so the test framework will come
up with the correct count.

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

maple_tree: Support freeing empty nodes on gap relocation.

When a gap is created during a low memory situation, coalesce may not be
able to group the gap together.  This can be handled by moving the right
node to the left & using a SKIP entry.  Note that this situation should
not arise unless in a low-memory situation, so a SKIP entry is useful as
it indicates the tree may need to be rebuilt after memory pressure
subsides.

When an empty node is found,

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

maple_tree: Zero pivots of gaps that have been moved.

This doesn't seem totally correct and should really use a new node.
A solution for low mem is needed too.

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

maple_tree: Combine gaps with retry entries.

When a retry entry is hit, combine it into the gap as it was relocated
to where the gap exists now.

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

maple_tree: Clean up mas_data_end interface.

Some places don't care about coalesce and the last pivot, so provide a
cleaner way to get just the end to clean up that code.

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

maple_tree: whitespace fix.

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

maple_tree: Fix rcu_dereference usages

Enabling CONFIG_PROVE_LOCKING reveals some compilation errors and
running it shows that loading the root pointer needs to be done with
rcu_dereference_protected() (which will permit the load if the lock is
held) instead of a plain rcu_dereference() (which permits the load if
the rcu read lock is held).

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>

maple_tree: no need to rcu_dereference in mtree_empty()

Since we're only comparing the value of the pointer to NULL, we
don't need to use rcu_dereference().  This is explicitly documented
in Documentation/RCU/rcu_dereference.rst.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>

mm: Fix compilation warnings

Nothing terribly interesting here.

Signed-off-by: Matthew Wilcox (Oracle) <willy@infradead.org>

maple_tree: Fix lock_dep calls to use pointers.

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

mm/mmap: Move variable declaring prior to code.

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

maple_tree: Fix overwritten slot in mas during __mas_add

Overwriting the slot in the ma state caused issues later on.  Restore
the value and fix the code in mas_may_move_gap to also detect such
scenarios.

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

maple_tree: Small code cleanup, white spaces etc.

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