Liam R. Howlett [Fri, 13 Dec 2019 21:13:55 +0000 (16:13 -0500)]
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>
Liam R. Howlett [Tue, 26 Nov 2019 18:54:29 +0000 (13:54 -0500)]
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>
Liam R. Howlett [Fri, 8 Nov 2019 16:50:55 +0000 (11:50 -0500)]
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>
Liam R. Howlett [Mon, 4 Nov 2019 21:00:27 +0000 (16:00 -0500)]
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>
Liam R. Howlett [Thu, 31 Oct 2019 14:42:09 +0000 (10:42 -0400)]
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>
Matthew Wilcox (Oracle) [Wed, 16 Oct 2019 20:03:18 +0000 (16:03 -0400)]
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>
Liam R. Howlett [Wed, 16 Oct 2019 19:31:37 +0000 (15:31 -0400)]
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>
Liam R. Howlett [Tue, 15 Oct 2019 18:40:48 +0000 (14:40 -0400)]
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>
Liam R. Howlett [Tue, 15 Oct 2019 18:38:45 +0000 (14:38 -0400)]
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>
Liam R. Howlett [Tue, 15 Oct 2019 02:40:35 +0000 (22:40 -0400)]
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>
Matthew Wilcox (Oracle) [Sun, 13 Oct 2019 03:23:46 +0000 (23:23 -0400)]
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>
Liam R. Howlett [Tue, 8 Oct 2019 01:34:08 +0000 (21:34 -0400)]
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>
Liam R. Howlett [Fri, 15 Mar 2019 20:01:22 +0000 (16:01 -0400)]
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>
Liam R. Howlett [Wed, 13 Feb 2019 16:12:02 +0000 (11:12 -0500)]
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>
Liam R. Howlett [Thu, 7 Feb 2019 19:34:49 +0000 (14:34 -0500)]
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>
projects / users / jedix / linux-maple.git / log