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>

Merge remote-tracking branch 'willy/maple2' into maple2

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>

maple_tree: Small cleanup of code and comments

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

maple_tree: Fix error in splitting on the right side

When splitting on the right side, there were a number of logical
errors:
1. Finding the parents type needed the parent to be encoded, so move the
logic to a location better suited to use the encoded node.
2. ma_copy had an incorrect range (off by one).
3. mt_replace was not using the encoded node to find the parent's slot.
This would always return zero.
4. ma_link had a potential overflow in the pivot.
5. The ma_state's min/max was not being updated and so the pivots were
not always correct when using the min/max.
6. The data end detection needed to be updated to also check for
ULONG_MAX.

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

test_maple_tree: port nomem thread race test.

Test to see that allocations work when two threads are racing.

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

maple_tree: Change return type of ma_insert.

ma_insert was returning a pointer in the old API.  This is no longer
needed.

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

test_maple_tree: Re-implement old allocation tests for new API.

Rewrite the allocation tests for maple2 rewrite.

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

testing: Fix bug in allocation tests for radix-tree linux.

When initializing kmem_cache for testing, ensure non_kernel is
initialized to zero.

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

test_maple_tree: Fix compile warning

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

maple_tree: Clean up erase function.

The node type is set during the partial copy of data operation now.

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

maple_tree: Remove enc_full and just use mas->node.

No need for this variable in mas_split.

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

maple_tree: Load safe root to mas->node in encoded_parent

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

maple_tree: Code clean up.

Drop unused variables & a fuction left from development of split

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

maple_tree: Fix dump debug code when the last slot is null.

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

maple_node: Fix comments

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

maple_tree: Split support

Initial split support.  Walks up the tree splitting as necessary to
support the addition of a node.

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

maple_tree: Rearrange _ma_insert for appends.

Reorder and make _ma_insert append safe and prepare for split.

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