maple_tree: Fix mas_first_entry return value.

This was returning the wrong pivot value which resulted in skipping
tree entries in mas_for_each loops.

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

maple_tree: Fix empty pivot when appending to a perfect fit.

When appending data to the end of a node which fits perfectly in the
range, it may be that the pivot is 0 but the implied pivot is mas->max.
This would result in a walk operation not finding the value.

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

maple_tree:   Continue fixing fallout from mas_data_end changes.

Rewrite mas_node_push and mas_next_alloc and add test cases to stress
test.

Fix mas_split calculations to use correct pivots.

Reuse null at the end of a node to avoid splitting

Fix mas_next_slot on root node running off the end of the node.

Fix _mas_awalk when there are deleted entries which caused a step over
the end.

Set slot to 0 on descend in __mas_awalk.

Only use 4 for node calculations on mas_replace_tree.

Fix testcase inserting 0 to use xa_mk_value to avoid coalescing NULL
entries.

Add set 4 to check_erase_testcase2 from KVM testing.

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

maple_tree: Rewrite mas_data_end to return slot not occupied count.

Rewrite mas_data_end to return slot, not occupied count and fix coalesce
calculation for a run of NULLs, etc

Move MT_BUG_ON for use in verification functions.

Add mas_mn for easier mas->node enode to node conversion.

Drop __mte_get_rcu_slot as the dead_node detect doesn't work right.

Make sure hard_data doesn't return a negative.

Fix ma_state on calls to mas_update_gaps

Fix end pivots on the right side of a split.

Fix number of slots being occupied calculation when _mas_add is using
the last slot and the new range doesn't run to mas->max.

Fix mas_rebalance when right node is empty and fix mas_data_end uses.

Rewrite mas_coalesce for new mas_data_end uses.

Fix mt_find overflow of index when there is a valuse at ULONG_MAX.

Add a testcase for mt_find overflow.

Fix mas_rev_awalk to check for errors prior to trying to walk.

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

maple_tree: Drop mas.last setting in mt_find and add tests.

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

maple_tree: Fix mt_find, mas_find, add with deleted slot, __mas_next

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

maple_tree: Fix compile warnings during kernel build

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

maple_tree: Add mas_get_unmapped_area and mas_get_unmapped_area_rev

This adds an interface which was missing for the drop-in replacement for
the mmap code.

It also fixes two issues:

1. Range checking for the upper bounds during a forward allocation walk
in _awalk
2. Checking if the ma_state is in error state during the loop in awalk
prior to calling _awalk.  The order was incorrect and could have caused
issues.

I've exposed mas_prev, and mtree_store_range for the mmap code in this
commit as well.

I've renamed a few missed ma_state functions to mas_ instead of ma_.
I've also reorder the header a bit.

Along with the new mas_get_unmapped_area{_rev}, I've added testcases for
them.

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

Thoughts: Add retry and rebalance/rebuild nodes.

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

maple_tree: Fix mas_prev to wrap on mas->node == MAS_START

When passed MAS_START and calling mas_prev, return the last entry.

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

maple_tree: Fix maple state max/min issues

When adding the validations, a number of concerns were raised on the
updating of the state information for max/min.  These have been
addressed and mas_next tests have been added.

mas_find and mt_find have been rewritten with the new mas_next.

Two new range functions have been added: mas_range_load() and
_mas_range_walk().  Both are able to return the range in which a given
index falls.

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

test_maple_tree: Update gap tests to use correct calculated size.

Update the oversize test to ensure there is not sufficient room since
the size is correctly one larger now.

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

maple_tree: Add validation functions and rework gap calculations

Add validation functions to verify gaps and limits.  This exposed places
where limits were not set correctly, so fix them.  Fixing the limits
exposed some other issues which resulted in rewriting the mas_next logic
and mas_find to better detect dead nodes.

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

maple_tree: Fix circular dependencies that will be created when mmap is
modified.

This also required moving mas_retry from .h to .c to avoid xarray
include loop.

Also fix mas_restart to reset mas ranges.

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

maple_tree: Remove mas_walk in favour of mas_load.

mas_walk was called in a single place for loading the value.  Rename the
function and clean it up.  Add retry on dead node detection and retry
entries.  Note that this can return the zero entry.

Also fix comments for _mas_walk

Also update limits on _mas_walk so that the maple state can be used for
checking the range limit of a search result.

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

maple_tree: Convert old ms arguemnt to mas.

Change the name of the maple state variable to mas.

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

maple_tree: Fix mas_find search.

There was a bug when a null occurred in a non-leaf node.  This commit
addresses that issue as well as trying to fix dead node detection.

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

maple tree test: Iterate over a partially deleted tree

Move mas_reset() to the header file and add mas_retry() to mirror
xas_retry().  Fix a few minor typos too.  Each time we delete an
entry from the tree, iterate over the tree to be sure we can still
do that correctly.  It fails once we've deleted the first node.

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

maple_tree: Fix coalesce/rebalance when erasing from the front of the
tree.

mas_coalesce_pivots added to set all null entries to the same pivot.
mas_coalesce_empty added to coalesce pivots after setting the entry to
NULL.
mas_rebalance reworked to free empty & coalesce_pivots on allocation
failure.  Parent nodes are then checked.
coalesce_root has a special case for when end == coalesce for handling
allocation failures.
mas_coalesce reworked to better perform when checking parent nodes &
works when allocations fail.
Gaps are now pushed to the right to avoid pulling the 0 pivot to the
left.

Also included:
Add check for dense nodes.
Fix mas_prev_slot called with root node.
typo fix for rebalance comment

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

maple tree tests: Erase entries individually

This should result in the tree being empty.  Right now, it doesn't --
the nodes full of deleted entries are not themselves deleted.

Also fix the lack of locking around the mas iteration.

maple_tree: Convert mtree_erase to match xarray interface

Return erased value instead of number of freed slots.  This required a
bit of a rework of the test cases.

Also removed two test cases to verify new nodes were used as they were
not necessary when the deleted range is an exact match for the insert.

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

maple_tree: Rename ms_root_expand to mas_root_expand to align with naming convention

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

maple_tree: Update mas_start to return the entry on a single pointer
tree.

mas_start returns:
  If mas->node is an error or MAS_START, return NULL
  If it's an empty tree:     NULL & mas->node == MAS_NONE
  If it's a single entry:    The entry & mas->node == MAS_ROOT
  If it's a tree:            NULL & mas->node == safe root node.

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

maple_tree: Change mas_start to return the entry in a single pointer
tree.

There are now three cases of the mas_start return:
 If it's an empty tree:     NULL & mas->node == MAS_NONE
 If it's a single entry:    The entry & mas->node == MAS_ROOT
 If it's a tree:            NULL & mas->node == safe root node.

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

maple_tree: Fix check_find_2 testcase.

The check_find_2 exposed issues when the tree was a simple pointer.  The
pointer case was not being handled correctly in mas_start, or _mas_walk.
Fixing these two functions also required fixing calling functions to
check for MAS_ROOT (a root pointer).

There was also a bug in mas_next_entry where the next node was checked -
which is not possible if it's the root node.

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

more thoughts

maple_tree: New check_find2 test

This is supposed to test various different conditions, but it currently
falls over trying to iterate a tree with no entries in it.

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

maple_tree: Fix test check_find

Lock the tree before beginning the iteration and unlock it after we've
finished.  Also destroy the tree so subsequent users of the tree aren't
confused by the detritus from this test.

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

maple_tree: Fix mas_dead_node for a trivial tree

For a tree with no entries, or an entry only at 0, mas_dead_node()
can be called with a mas->node of NULL.  This node is, by definition,
not dead.

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

maple_tree: Use mas_lock/unlock

If we've got a maple state, use the convenience wrappers instead of
open-coding it.

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

maple_tree: Random whitespace fixes

Also add some missing EXPORT_SYMBOLs

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

maple_tree: Add mas_set() and mas_set_range()

The equivalent of xas_set()

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

maple_tree: Fix mas_load issues

Previous commit included incomplete work of mas_load by accident.  This
fixes the build failure and successfully runs all tests.

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

maple_tree: Move iterators to the header

This is part of the api, so expose it through the header.

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

maple_tree: Standardize names of functions

anything that takes a struct ma_state as the first argument is named
mas_
anything that takes a struct maple_enode as the first argument is name
mte_

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

maple_tree: Add coalesce support.

Coalesce is done in two stages:
  1. Set all adjacent coalesce pivots to the highest value.
  2. rebalance if there is not enough data in the node.

Rebalance is done as follows:
  1. Take data from the right (4 or everything)
  2. if there is no right, rebalance the node to the left.
  3. if there is no left, rebalance the parent.
  4. if there is no parent, remove a level from the tree.

More testing is needed.  The test infrastructure needs to be reworked to
use more knowledge of the tree layout to test when split/erase occurs
and to ensure the testcases fail if they become invalid (ie: dense
support re-enabled).

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

maple_tree: Add layout comments to header.

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

maple_tree: Remove unnecessary coalescing.

Coalescing is only needed between nodes now.  Skip any identical entries when copying the node data in ma_add

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

maple_tree: More erase checking.

Ensure erase coalesces XA_RETRY_ENTRY on copy, and don't split if data can be coalesced

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

maple_tree: Convert another pivot fetch to safe_pivot

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

maple_tree: Restore slot in ma_coalesce and additional erase testcases

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

maple_tree: Clean up ma_copy and mas_coalesce

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

maple_tree: Fix coalesce to skip duplicate pivots and to run on leaves

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

test_maple_tree: Quiet down output

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

maple_tree: Add some comments to ma_rev_alloc and ma_alloc

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

maple_tree: Store XA_RETRY_ENTRY on erase

Avoid using slots again until an RCU freeing cycle is complete by storing XA_RETRY_ENTRY

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

maple_tree: Add mas_pause for pausing iterator.

Also add testcases for the pause function.

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

maple_tree: checkpatch fixes

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

maple_tree: Add restarts for interaters on dead nodes.

also fix the testcase for the iterators for the zero entry test.

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

maple_tree: mt_for_each implementation

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

maple_tree: Add check for mas_for_each loop.

Also change the ams_start to reset min/max

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

mas_find implementation

Fixes for prev/next node as well

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

maple_tree: mas_next_node/mas_prev_node restarts added on dead node detection.

Also required reordering some functions.

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

maple_tree: Add basic store support.

This store operation builds a new tree.  This was done to avoid creating
an invalid b-tree (not the same height from all leaves to head).

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

maple_tree: Change erase return to 0 on success.

Count isn't used, so return 0 for success.

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

maple_tree: Add reverse walk.

Search for a hole of a given size at the highest address.

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

maple_tree: Fix range checking on skip_node

When skipping a node, it is only valid to break out of the loop if slot
+ 1 is valid.

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

maple_tree: Fix forward searching for gaps.

There was an off-by-one issue with the gap calculation as it is
exclusive - inclusive.

Fix the ascend search in maple_awalk using the wrong parent slot.

Return -EBUSY correctly when a failure occurs.

Fix node splitting when there is no such thing as dense.

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

maple_dump: Pad better

I think this works out better visually than the previous effort.

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

maple_dump: Pad to indicate depth

Not entirely sure if this is the best way to indicate depth; let's
try it for a bit and see how confused we get.

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

maple_tree: Disable dense nodes.

Disable dense nodes to avoid split issues.

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

maple_tree: messy test output

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

maple_tree: Remove early exit on tests

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

maple_tree: Add awalk for walking allocation trees for gaps.

Adds mtree_alloc_range to allocate a range.  Some basic tests.

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

maple_tree: Add maple_tree alloc support for gaps.

Start populating gaps with values
Remove the maple_aleaf_64 type and use regular maple_leaf_64.
Rework pivot calculations to be more straight forward.
Don't use dense nodes in the root node to avoid having a dense node as
the right-most node.

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

maple_tree: typedef maple_enode for encoded node.

Use the compiler to check if an encoded node or a regular node is used

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

maple_tree: typedef parent node to maple_pnode

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

maple_tree: Use encoded node for getting rcu slot in ma_encoded_parent

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

maple_tree: Add initial maple_arange_64 node support.

maple_arange_64 is for allocation ranges which need to track gaps in
subtrees.  This commit does not address tracking the gaps.

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

test_maple_tree: Fix range checking.

Checking a range was not using the correct number range.

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

maple_tree: Fix range add to empty tree.

When adding to an empty tree, use the encoded node to set the pivot.

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

maple_tree: Rework internal walk.

Reduce possible calls to get an rcu entry.

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

ma_xa_benchmark: Update time calculations

Time calculations were prone to overflow because seconds were not
included.

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

maple_tree: Fix double free error.

There was a double free which raced with the rcu free so it was not
detected all the time.

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

maple: Fix _mas_walk return & clean up ma_insert root expand logic

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

maple: Fix off by one error when walking.

When going to the next slot, the minimum value is actually pivot + 1 and
not just the pivot value.

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

maple_tree: Optimize _mas_walk

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

maple_tree: Rework walk.

Make walk more efficient by avoiding duplicate fetches of slot and pivots.

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

maple_tree: Make walk faster.

Avoid looking up duplicate information.

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

ma_xa_benchmark: Fix percentage calculation for time.

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

maple_tree: Efficiencies

Remove unneeded code.
Fix splitting from the back of a node.

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

maple_tree: Dense node support & nulls in tree.

Support dense node types.  The reduces the space required for sequential
indexes a lot.
Splitting now decides between usign the parent type and the dense node
type for left/right independently.
Fixes had to be made to pivot lookups.
A few static inline additions to speed things up.

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

maple_tree:  Performance enhancements.

Start using slot 0 on splits.
Fix missing breaks on set of slots.
Calc node type only once during certain loops

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

maple_tree: Make functions node-type generic.

Move mt_max outside of debug and add mt_slots
Create mt_slots for enum to slot size mapping.
Rename ma_cp_data_64 to ma_split_data
Drop extra calls in split.
Create calls to get/set pivots & slots.
Rework all functions to use generic calls.

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

ma_xa_benchmark: Use user time. add rcu barrier before size calc.

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

ma_xa_benchmark: Initial push

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

maple_tree: remove duplicate function.

When adding a check for reserved entries, I hadn't noticed it already
existed.

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

test_maple_tree: Fix comments & add more tests.

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

maple_tree: Fix split & insert to use last slot.

The last slot was revealed to be NULL always.  Fix this by changing the
the end calculations and to ensure it is okay to use the final slot.

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

maple_tree: Drop depth from split operation.

It is not used.

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

maple_tree: Fix root bit & parent type.

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

maple_tree: fix goto lables in ma_insert

Fix the order of goto labels and set the error correct if using exists.

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

maple_tree: Add root expand to node if the single entry ends in 10.

As requested by page cache.

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

maple_tree: Change mask calc for mt_parent_type

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

maple_tree: Remove depth from ma_split.

the depth is no longer use, so drop it.

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

Thoughts: Add table of bits in the parent.

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

maple_tree: Fix parent definitions & fallout from ULONG_MAX ending.

coalesce needed to be updated for ULONG_MAX endings.
ma_copy needed to check for ULONG_MAX ending.
ma_encoded_parent no longer updates the ma_state limits.
adopt_children needed the encoded node passed in for the node type to
encode in the parent of the children.

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

test_maple_tree: Add seqential test for adding 1000 entries

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

maple_tree: Add comment about encode parent.

function name seems to lack description

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

maple_tree: Move mas_update_limits

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