Liam R. Howlett [Thu, 7 May 2020 01:12:28 +0000 (21:12 -0400)]
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>
Liam R. Howlett [Wed, 6 May 2020 01:15:23 +0000 (21:15 -0400)]
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 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>
Liam R. Howlett [Fri, 6 Mar 2020 18:45:54 +0000 (13:45 -0500)]
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>
Matthew Wilcox (Oracle) [Mon, 2 Mar 2020 21:16:00 +0000 (16:16 -0500)]
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>
Matthew Wilcox (Oracle) [Mon, 2 Mar 2020 21:09:00 +0000 (16:09 -0500)]
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>
Liam R. Howlett [Mon, 2 Mar 2020 15:43:00 +0000 (10:43 -0500)]
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>
Matthew Wilcox (Oracle) [Thu, 27 Feb 2020 15:47:07 +0000 (10:47 -0500)]
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>
Matthew Wilcox (Oracle) [Wed, 26 Feb 2020 19:00:43 +0000 (14:00 -0500)]
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>
Liam R. Howlett [Tue, 25 Feb 2020 02:36:03 +0000 (21:36 -0500)]
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>
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>
Liam R. Howlett [Mon, 24 Feb 2020 15:11:39 +0000 (10:11 -0500)]
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>
Liam R. Howlett [Sat, 22 Feb 2020 02:49:55 +0000 (21:49 -0500)]
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>
Liam R. Howlett [Fri, 21 Feb 2020 18:19:21 +0000 (13:19 -0500)]
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>
Liam R. Howlett [Tue, 11 Feb 2020 02:35:09 +0000 (21:35 -0500)]
maple_tree: Reduce recursion and fix set10 testcase.
1. Remove ma_cp/mas_copy in favour of mas_append and friends.
It turns out it is cleaner to append nodes together than to try and
copy parts and glue them together as initially designed.
2. Clean up debug/test code and BUG_ON statements.
3. Add *mte_get_rcu_sanitized() to return NULL if it will be coalesced.
4. mas_set_safe_pivot is no longer recursive.
5. mas_data_end has been altered numerous times.
6. Add mas_get_range() - get the range of a given slot.
7. Drop mas_ma_update_gap/mas_ma_cp in favour of the above mentioned
appending operations.
8. mas_parent_gap() is no longer recursive.
9. mas_update_gap() has been updated to use new mas_parent_gap.
10. mas_split() uses mas_append and friends.
11. __mas_add_slot_cnt() is used to calculate the slots needed when
adding a value - much reliable than mas_data_end for this usecase.
12. mas_rebalance() is no longer recursive.
13. Added validation code for parent slot
14. Doubled testcases and fixed a missing mas_destroy() call.
Signed-off-by: Liam R. Howlett <Liam.Howlett@Oracle.com>
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>
projects / users / jedix / linux-maple.git / log