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: 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>

maple_tree: Refactor coalesce into a separate function.

Reworked logic to have a bit of a cleaner looking function.  Supports
full nodes now as well.

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

maple_tree: Avoid allocating a node in coalescing until necessary

When looping through a node, don't create a new node if there is no need
to do so.

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

maple_tree: Avoid coalescing on insert if it is not needed.

On insert, iterate over the pivots looking for matching ones to
determine if slots need to be coalesced.
Erase always needs to coalesce, so don't check there.

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

maple_tree: whitespace fix

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

test_maple_tree: Add new function to allow __GFP_DIRECT_RECLAIM gfp for
a given number of times.

Set a variable that allows reclaims to occur for a specific count for
testing.

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

maple_tree: Change ma_coalesce to return the number of slots removed.

Set ma->node to the new node, so save the previous node before calling
the function.  Also fix an off-by-one error in ma_coalesce.

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

Corrected typo

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

maple_tree: Add erase support.

Refactor replacing a node in a tree to its own function and use that
with the erase and insert functions.

Erase NULLs the range in which the index resides and coalesces adjacent
NULLs if allocation succeeds.

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

maple_tree: Fix several off-by-one errors.

When counting through the slots/pivots, the pivots overflow before the
slots which is an area of confusion sometimes.

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

maple_tree: Rework walking the tree to combine insert/walk/erase
functions.

This turned out to be a huge deal with many issues resolved for the
following of Thoughts:

1. Nodes can use the last 0x7F bits of the address, so clear them and
such.
2. Root needs to have bit 1 (0x2) set, so be safe around that.
3. mas->node should be encoded (except root needs to remove bit 1 to
avoid being seen as an error).
4. xa_is_node no longer works, so remove BUG_ONs.  Take care that we
know we have a value when we have a slot & an leaf node in mas->node.
5. Store slots in the same place as the alloc requests as their uses do
not overlap.
6. mas_start needs to return a safe root instead of making its own node.
7. Insert was basically rewritten
8. Verify that we are no inserting reserved values
9. Change testcases to not try to insert reserved values.

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

maple_tree: Fix potential race condition in _ma_insert

The pivots protect readers from reading invalid data.  Without a wmb
between overwriting the end pivot (of zero), there is a potential that
the writes could be reordered and a race condition would exist between
updating both values and a reader interleaving those writes.

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

maple_tree: Add insert/append operation.

Check for NULL runs by looking for duplicate pivots and coalesce them
into a single entry.  Append and insert into a new node, then replace
the old node and adopt the children.

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

maple_tree: Fix data_end calculation and root expansion.

Root expansion needs to set the pivot to the empty value if there is no
zero for the append to function correctly.

In append, we know the data end will always be at least 1, so take two
off the idx when checking the previous pivot value (since we also add 1
to the end for the new termination).

Append will need to be altered to cover off the overflow possibility in
the future.

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

maple_tree: clean up swithc statement and remove null parent assignment

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