* [PATCH Fix 0/2] Underflow in mas_spanning_rebalance() and test
@ 2022-06-25 0:39 Liam Howlett
2022-06-25 0:39 ` [PATCH Fix 1/2] maple_tree: Fix underflow in mas_spanning_rebalance() Liam Howlett
2022-06-25 0:39 ` [PATCH Fix 2/2] test_maple_tree: Add test for spanning store of entire range Liam Howlett
0 siblings, 2 replies; 3+ messages in thread
From: Liam Howlett @ 2022-06-25 0:39 UTC (permalink / raw)
To: maple-tree, linux-mm, linux-kernel, Andrew Morton, Yu Zhao
Fixes the bug found by Yu Zhao running stress-ng on a large system
(512gb of ram).
Patches against mm-unstable.
Liam R. Howlett (2):
maple_tree: Fix underflow in mas_spanning_rebalance()
test_maple_tree: Add test for spanning store of entire range.
lib/maple_tree.c | 6 ++++--
lib/test_maple_tree.c | 13 +++++++++++++
2 files changed, 17 insertions(+), 2 deletions(-)
--
2.35.1
^ permalink raw reply [flat|nested] 3+ messages in thread
* [PATCH Fix 1/2] maple_tree: Fix underflow in mas_spanning_rebalance()
2022-06-25 0:39 [PATCH Fix 0/2] Underflow in mas_spanning_rebalance() and test Liam Howlett
@ 2022-06-25 0:39 ` Liam Howlett
2022-06-25 0:39 ` [PATCH Fix 2/2] test_maple_tree: Add test for spanning store of entire range Liam Howlett
1 sibling, 0 replies; 3+ messages in thread
From: Liam Howlett @ 2022-06-25 0:39 UTC (permalink / raw)
To: maple-tree, linux-mm, linux-kernel, Andrew Morton, Yu Zhao
When rebalancing a spanning store that spans the entire address space,
the big node end is not expanded the extra position that
mas_spanning_rebalance() expects. Fix this by expanding on such cases.
Also change mab_mas_cp() from assuming there are at least two entries to
ensure the correct metadata is written.
Fixes: f8acc5e9581e (Maple Tree: add new data structure)
Reported-by: Yu Zhao <yuzhao@google.com>
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
lib/maple_tree.c | 6 ++++--
1 file changed, 4 insertions(+), 2 deletions(-)
diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index a968948b3e3e..d8457122ca5d 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -1977,7 +1977,6 @@ static inline void mab_mas_cp(struct maple_big_node *b_node,
slots[mt_pivots[mt]] = NULL;
i = mab_start;
- pivots[j++] = b_node->pivot[i++];
do {
pivots[j++] = b_node->pivot[i++];
} while (i <= mab_end && likely(b_node->pivot[i]));
@@ -2970,7 +2969,7 @@ static int mas_spanning_rebalance(struct ma_state *mas,
mast->free = &free;
mast->destroy = &destroy;
l_mas.node = r_mas.node = m_mas.node = MAS_NONE;
- if (!mas_is_root_limits(mast->orig_l) &&
+ if (!(mast->orig_l->min && mast->orig_r->max == ULONG_MAX) &&
unlikely(mast->bn->b_end <= mt_min_slots[mast->bn->type]))
mast_spanning_rebalance(mast);
@@ -4004,6 +4003,9 @@ static inline int mas_wr_spanning_store(struct ma_wr_state *wr_mas)
if (r_mas.offset <= r_wr_mas.node_end)
mas_mab_cp(&r_mas, r_mas.offset, r_wr_mas.node_end,
&b_node, b_node.b_end + 1);
+ else
+ b_node.b_end++;
+
/* Stop spanning searches by searching for just index. */
l_mas.index = l_mas.last = mas->index;
--
2.35.1
^ permalink raw reply related [flat|nested] 3+ messages in thread
* [PATCH Fix 2/2] test_maple_tree: Add test for spanning store of entire range.
2022-06-25 0:39 [PATCH Fix 0/2] Underflow in mas_spanning_rebalance() and test Liam Howlett
2022-06-25 0:39 ` [PATCH Fix 1/2] maple_tree: Fix underflow in mas_spanning_rebalance() Liam Howlett
@ 2022-06-25 0:39 ` Liam Howlett
1 sibling, 0 replies; 3+ messages in thread
From: Liam Howlett @ 2022-06-25 0:39 UTC (permalink / raw)
To: maple-tree, linux-mm, linux-kernel, Andrew Morton, Yu Zhao
Entire range store over an existing tree would cause an underflow in
mas_spanning_store() when the tree is multiple levels. Add a testcase
to ensure it doesn't happen again.
Fixes: 51282228cdd4 (lib/test_maple_tree: add testing for maple tree)
Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com>
---
lib/test_maple_tree.c | 13 +++++++++++++
1 file changed, 13 insertions(+)
diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
index 9fc0618f4ae7..8de5705b7b9b 100644
--- a/lib/test_maple_tree.c
+++ b/lib/test_maple_tree.c
@@ -35676,6 +35676,19 @@ static noinline void check_spanning_write(struct maple_tree *mt)
mtree_unlock(mt);
mtree_destroy(mt);
+ for (i = 1; i <= max; i++)
+ mtree_test_store_range(mt, i * 10, i * 10 + 5, &i);
+
+ mtree_lock(mt);
+ mas_set_range(&mas, 9, 50006); /* Will expand to 0 - ULONG_MAX */
+ mas_store_gfp(&mas, NULL, GFP_KERNEL);
+ mas_set(&mas, 1205);
+ MT_BUG_ON(mt, mas_walk(&mas) != NULL);
+ mtree_unlock(mt);
+ mt_dump(mt);
+ mt_validate(mt);
+ mtree_destroy(mt);
+
/* Test spanning store that requires a right cousin rebalance */
mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE);
for (i = 0; i <= max; i++)
--
2.35.1
^ permalink raw reply related [flat|nested] 3+ messages in thread
end of thread, other threads:[~2022-06-25 0:39 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-06-25 0:39 [PATCH Fix 0/2] Underflow in mas_spanning_rebalance() and test Liam Howlett
2022-06-25 0:39 ` [PATCH Fix 1/2] maple_tree: Fix underflow in mas_spanning_rebalance() Liam Howlett
2022-06-25 0:39 ` [PATCH Fix 2/2] test_maple_tree: Add test for spanning store of entire range Liam Howlett
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).