From 955a923d2809803980ff574270f81510112be9cf Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Mon, 22 Apr 2024 16:33:49 -0400 Subject: maple_tree: fix mas_empty_area_rev() null pointer dereference Currently the code calls mas_start() followed by mas_data_end() if the maple state is MA_START, but mas_start() may return with the maple state node == NULL. This will lead to a null pointer dereference when checking information in the NULL node, which is done in mas_data_end(). Avoid setting the offset if there is no node by waiting until after the maple state is checked for an empty or single entry state. A user could trigger the events to cause a kernel oops by unmapping all vmas to produce an empty maple tree, then mapping a vma that would cause the scenario described above. Link: https://lkml.kernel.org/r/20240422203349.2418465-1-Liam.Howlett@oracle.com Fixes: 54a611b60590 ("Maple Tree: add new data structure") Signed-off-by: Liam R. Howlett Reported-by: Marius Fleischer Closes: https://lore.kernel.org/lkml/CAJg=8jyuSxDL6XvqEXY_66M20psRK2J53oBTP+fjV5xpW2-R6w@mail.gmail.com/ Link: https://lore.kernel.org/lkml/CAJg=8jyuSxDL6XvqEXY_66M20psRK2J53oBTP+fjV5xpW2-R6w@mail.gmail.com/ Tested-by: Marius Fleischer Tested-by: Sidhartha Kumar Cc: Signed-off-by: Andrew Morton --- lib/maple_tree.c | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) (limited to 'lib') diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 55e1b35bf877..2d7d27e6ae3c 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -5109,18 +5109,18 @@ int mas_empty_area_rev(struct ma_state *mas, unsigned long min, if (size == 0 || max - min < size - 1) return -EINVAL; - if (mas_is_start(mas)) { + if (mas_is_start(mas)) mas_start(mas); - mas->offset = mas_data_end(mas); - } else if (mas->offset >= 2) { - mas->offset -= 2; - } else if (!mas_rewind_node(mas)) { + else if ((mas->offset < 2) && (!mas_rewind_node(mas))) return -EBUSY; - } - /* Empty set. */ - if (mas_is_none(mas) || mas_is_ptr(mas)) + if (unlikely(mas_is_none(mas) || mas_is_ptr(mas))) return mas_sparse_area(mas, min, max, size, false); + else if (mas->offset >= 2) + mas->offset -= 2; + else + mas->offset = mas_data_end(mas); + /* The start of the window can only be within these values. */ mas->index = min; -- cgit v1.2.3 From 2aaba39e783a10fd1368626bce6f618a6a2a78b0 Mon Sep 17 00:00:00 2001 From: Luis Chamberlain Date: Tue, 23 Apr 2024 12:22:21 -0700 Subject: lib/test_xarray.c: fix error assumptions on check_xa_multi_store_adv_add() While testing lib/test_xarray in userspace I've noticed we can fail with: make -C tools/testing/radix-tree ./tools/testing/radix-tree/xarray BUG at check_xa_multi_store_adv_add:749 xarray: 0x55905fb21a00x head 0x55905fa1d8e0x flags 0 marks 0 0 0 0: 0x55905fa1d8e0x xarray: ../../../lib/test_xarray.c:749: check_xa_multi_store_adv_add: Assertion `0' failed. Aborted We get a failure with a BUG_ON(), and that is because we actually can fail due to -ENOMEM, the check in xas_nomem() will fix this for us so it makes no sense to expect no failure inside the loop. So modify the check and since this is also useful for instructional purposes clarify the situation. The check for XA_BUG_ON(xa, xa_load(xa, index) != p) is already done at the end of the loop so just remove the bogus on inside the loop. With this we now pass the test in both kernel and userspace: In userspace: ./tools/testing/radix-tree/xarray XArray: 149092856 of 149092856 tests passed In kernel space: XArray: 148257077 of 148257077 tests passed Link: https://lkml.kernel.org/r/20240423192221.301095-3-mcgrof@kernel.org Fixes: a60cc288a1a2 ("test_xarray: add tests for advanced multi-index use") Signed-off-by: Luis Chamberlain Cc: Daniel Gomez Cc: Darrick J. Wong Cc: Dave Chinner Cc: "Liam R. Howlett" Cc: Matthew Wilcox (Oracle) Cc: Pankaj Raghav Signed-off-by: Andrew Morton --- lib/test_xarray.c | 13 +++++++++---- 1 file changed, 9 insertions(+), 4 deletions(-) (limited to 'lib') diff --git a/lib/test_xarray.c b/lib/test_xarray.c index ebe2af2e072d..5ab35190aae3 100644 --- a/lib/test_xarray.c +++ b/lib/test_xarray.c @@ -744,15 +744,20 @@ static noinline void check_xa_multi_store_adv_add(struct xarray *xa, do { xas_lock_irq(&xas); - xas_store(&xas, p); - XA_BUG_ON(xa, xas_error(&xas)); - XA_BUG_ON(xa, xa_load(xa, index) != p); - xas_unlock_irq(&xas); + /* + * In our selftest case the only failure we can expect is for + * there not to be enough memory as we're not mimicking the + * entire page cache, so verify that's the only error we can run + * into here. The xas_nomem() which follows will ensure to fix + * that condition for us so to chug on on the loop. + */ + XA_BUG_ON(xa, xas_error(&xas) && xas_error(&xas) != -ENOMEM); } while (xas_nomem(&xas, GFP_KERNEL)); XA_BUG_ON(xa, xas_error(&xas)); + XA_BUG_ON(xa, xa_load(xa, index) != p); } /* mimics page_cache_delete() */ -- cgit v1.2.3 From 2a0774c2886d25f4d2987cd3e3813d16bf96f34f Mon Sep 17 00:00:00 2001 From: "Matthew Wilcox (Oracle)" Date: Wed, 1 May 2024 16:31:18 +0100 Subject: XArray: set the marks correctly when splitting an entry If we created a new node to replace an entry which had search marks set, we were setting the search mark on every entry in that node. That works fine when we're splitting to order 0, but when splitting to a larger order, we must not set the search marks on the sibling entries. Link: https://lkml.kernel.org/r/20240501153120.4094530-1-willy@infradead.org Fixes: c010d47f107f ("mm: thp: split huge page to any lower order pages") Signed-off-by: Matthew Wilcox (Oracle) Reported-by: Luis Chamberlain Link: https://lore.kernel.org/r/ZjFGCOYk3FK_zVy3@bombadil.infradead.org Tested-by: Luis Chamberlain Cc: Zi Yan Signed-off-by: Andrew Morton --- lib/test_xarray.c | 14 +++++++++++++- lib/xarray.c | 23 +++++++++++++++++++---- 2 files changed, 32 insertions(+), 5 deletions(-) (limited to 'lib') diff --git a/lib/test_xarray.c b/lib/test_xarray.c index 5ab35190aae3..928fc20337e6 100644 --- a/lib/test_xarray.c +++ b/lib/test_xarray.c @@ -1788,9 +1788,11 @@ static void check_split_1(struct xarray *xa, unsigned long index, unsigned int order, unsigned int new_order) { XA_STATE_ORDER(xas, xa, index, new_order); - unsigned int i; + unsigned int i, found; + void *entry; xa_store_order(xa, index, order, xa, GFP_KERNEL); + xa_set_mark(xa, index, XA_MARK_1); xas_split_alloc(&xas, xa, order, GFP_KERNEL); xas_lock(&xas); @@ -1807,6 +1809,16 @@ static void check_split_1(struct xarray *xa, unsigned long index, xa_set_mark(xa, index, XA_MARK_0); XA_BUG_ON(xa, !xa_get_mark(xa, index, XA_MARK_0)); + xas_set_order(&xas, index, 0); + found = 0; + rcu_read_lock(); + xas_for_each_marked(&xas, entry, ULONG_MAX, XA_MARK_1) { + found++; + XA_BUG_ON(xa, xa_is_internal(entry)); + } + rcu_read_unlock(); + XA_BUG_ON(xa, found != 1 << (order - new_order)); + xa_destroy(xa); } diff --git a/lib/xarray.c b/lib/xarray.c index 39f07bfc4dcc..5e7d6334d70d 100644 --- a/lib/xarray.c +++ b/lib/xarray.c @@ -969,8 +969,22 @@ static unsigned int node_get_marks(struct xa_node *node, unsigned int offset) return marks; } +static inline void node_mark_slots(struct xa_node *node, unsigned int sibs, + xa_mark_t mark) +{ + int i; + + if (sibs == 0) + node_mark_all(node, mark); + else { + for (i = 0; i < XA_CHUNK_SIZE; i += sibs + 1) + node_set_mark(node, i, mark); + } +} + static void node_set_marks(struct xa_node *node, unsigned int offset, - struct xa_node *child, unsigned int marks) + struct xa_node *child, unsigned int sibs, + unsigned int marks) { xa_mark_t mark = XA_MARK_0; @@ -978,7 +992,7 @@ static void node_set_marks(struct xa_node *node, unsigned int offset, if (marks & (1 << (__force unsigned int)mark)) { node_set_mark(node, offset, mark); if (child) - node_mark_all(child, mark); + node_mark_slots(child, sibs, mark); } if (mark == XA_MARK_MAX) break; @@ -1077,7 +1091,8 @@ void xas_split(struct xa_state *xas, void *entry, unsigned int order) child->nr_values = xa_is_value(entry) ? XA_CHUNK_SIZE : 0; RCU_INIT_POINTER(child->parent, node); - node_set_marks(node, offset, child, marks); + node_set_marks(node, offset, child, xas->xa_sibs, + marks); rcu_assign_pointer(node->slots[offset], xa_mk_node(child)); if (xa_is_value(curr)) @@ -1086,7 +1101,7 @@ void xas_split(struct xa_state *xas, void *entry, unsigned int order) } else { unsigned int canon = offset - xas->xa_sibs; - node_set_marks(node, canon, NULL, marks); + node_set_marks(node, canon, NULL, 0, marks); rcu_assign_pointer(node->slots[canon], entry); while (offset > canon) rcu_assign_pointer(node->slots[offset--], -- cgit v1.2.3