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>

MAINTAINERS: Add maple tree

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

maple_tree: Add support for combining gaps.

When gaps touch but are not in the same node, move them to the right
node.  This allows for searches to find the desired gap.

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

extra debug

maple_tree: Fix RCU reads to use rcu_dereference_check and writes to use
rcu_assign_pointer

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

maple_tree: Fix placement of data during add operation during certain
conditions.

When partially overwriting the sources end slot and coalescing data
during the copy operation, there was a potential for an overflow during
a store operation.  Avoid the overflow by using the new node end instead
of the slot passed in as the destination.

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

mm: Get rid of maple tree whitespace changes

Nothing here makes any difference to the generated code.

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

maple_tree: Clean up debug infrastructure

making tests_run & tests_passed static means there's one copy of them in
every file that includes maple_tree.h.  Make them extern, prefix them
with maple_tree_, move them to maple_tree.c and export them so that
test_maple_tree can be built as a module.

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

maple_tree: Move xa_get_alloc_size

... into ma_xa_benchmark.

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

mm/mmap: Remove maple tree erase call in __vma_unlink_common

__vma_unlink_common is used when overwriting the next vma entry.  Maple
tree overwrites these entries on the store of the vma itself.

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

mm/mmap: Maple tree update for validate_mm_mt and comments

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

mmap: Write changes to next to the maple tree.

When mprotect case 4 is hit (expand next back over vma), you have to
write the changes to the maple tree or there will be a missing mapping.

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

maple_tree: Initial documentation straw man.

Just add the file and some headers.  Details need to come from Thoughts.

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

Renumber XA.*ENTRY constants

Entries below 256 are reserved for siblings, so renumber the RETRY
entry back to 256.  Entries which are ZERO and higher are allowed to
be inserted into the XArray, so renumber ZERO to 259, and slot SKIP and
DELETED in at 257 and 258.

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

Revert "maple_tree: Rework node split calculation for better non-leaf node split"

Efficient splitting is causing issues in certain scenarios with regards
to allocation trees.  Revisit later.

This reverts commit 4a0a2dd623fae22f2823a0711193aafef3479e71.

maple_tree: Fix off by one on mas_prev when going to previous node.

mas_prev_nentry decrements the slot prior to checking for an entry, so
don't decrement the slot in mas_prev loop on new nodes.

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

mm/mmap: Don't adjust next for maple tree operations.

As maple tree store operation will alter the start location of the next
node if it they overlap, there is no need to erase and store the same
VMA.  In fact, since the start location is now occupied by the current
VMA, the erase operation will remove the wrong entry.

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

maple_tree: Set slot in mas_prev_slot to get the pivot

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

maple_tree: Rework node split calculation for better non-leaf node split
usage.

When calculating where to split non-leaf nodes, assume the minimum span
is 8 in each entry, so 8*8.  This still needs work as we could figure
out the level from a leaf and keep going up in the minimum span to
better utilize more levels of the tree.

There is also the issue of the right-most entry (ULONG_MAX) which ends
up wasting a slot in the linear allocation case.

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

maple_tree: Always split regardless of spanning node boundaries or not.

Spanning node boundaries are now considered when calculating the number
of elements in a node, so if the count is larger than what the node will
hold, the node needs to be split.

set20 in test_maple_tree caught this issue.

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

maple_tree: Fix mas_prev issue with parent slot & loop at root.

parent slots were not being set correctly for the first ascend.  This
caused data to be skipped.

There was also an infinite loop if this was the first entry in a deep
tree.

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

maple_tree: Fix finding the end of a node when the node ends in a NULL.
Also fix the limit calculation on gaps when searches backwards goes into
adjacent nodes during the search.

Ignoring the end null may cause gaps to be skipped when searching
backwards.

Adjacent nodes caused the max limit to be reset to the parent but never
set if the very next entry also had a potential gap that would work.

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

maple_tree: Fix limit updating when rewinding nodes during reverse
walks.

When walking backwards in a node that sat in slot 0 of the parent, the
limit would not be set correctly.  The fix is not to set the limits
until descending into the node.

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

mm/mmap and mm/mprotect: Alter mmap erase method.

Can't call erase every time the rbtree erases as the maple tree doesn't
allow overlaps, so it's not necessary.

mprotect was too noisy.

mmap also had debug altered and verify changed in this commit.

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

maple_tree: Fix off-by-one on append_entry

When appending an entry, ensure that the previous pivot is one less than
the desired range.

Don't subtraction coalesce from the slot calculation as that is now
taken into account within  _mas_add_slot_cnt itself.

Fix testing to kick out if mas_for_each is in a retry loop.

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

test_maple_tree: Standardize tests on using what was stored into the
maple tree

Use [x,y], not [x,y).

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

maple_tree: Fix u64 => unsigned long

Incorrect types fixed.  This will need to be revisited for different
arch and also u16/u32 one day.

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

maple_tree: Fix append_entry for NULL appending, fix append for retry
entries, fix split appending on coalesce.

Add some testcases for the above fixes.

Also fix an off-by-one error in spanning_add.

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

mm/mmap and maple_tree: Fix mt_for_each interface, get_unmapped_area_rev

mt_for_each interface simplification for external users.

get_unampped_area_rev was not getting the right answer.  Fix it and
clean up the condensed and unused interface internal to the maple tree.

Fix associated tests as well.

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

mmap/fork/mm.h: Add maple tree support.

When forking, init the maple tree and add entries.

mmap: Clean up prints.

mm: Export vma_store for adding things to mt in fork.

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

maple_tree: Thoughts, fix whitespace, fix compile issue

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