[PATCH RESEND V2 0/5] Fixes and cleanups to xarray

[PATCH RESEND V2 0/5] Fixes and cleanups to xarray

[Kemeng Shi]

resend:
-also cc linux-mm

v1->v2:
-Drop patch "Xarray: skip unneeded xas_store() and xas_clear_mark() in
__xa_alloc()"

This series contains some random fixes and cleanups to xarray. Patch 1-3
are fixes and patch 4-5 are cleanups. More details can be found in
respective patches. Thanks!

Kemeng Shi (5):
  Xarray: Do not return sibling entries from xas_find_marked()
  Xarray: distinguish large entries correctly in xas_split_alloc()
  Xarray: move forward index correctly in xas_pause()
  Xarray: remove repeat check in xas_squash_marks()
  Xarray: use xa_mark_t in xas_squash_marks() to keep code consistent

 lib/test_xarray.c                     | 35 +++++++++++++++++++++++++++
 lib/xarray.c                          | 26 +++++++++++---------
 tools/testing/radix-tree/multiorder.c |  4 +++
 3 files changed, 54 insertions(+), 11 deletions(-)

-- 
2.30.0

Re: [PATCH RESEND V2 0/5] Fixes and cleanups to xarray

[Andrew Morton]

On Tue, 12 Nov 2024 05:53:54 +0800 Kemeng Shi <shikemeng@huaweicloud.com> wrote:

> This series contains some random fixes and cleanups to xarray. Patch 1-3
> are fixes and patch 4-5 are cleanups. More details can be found in
> respective patches. 

As we're at -rc7 I'm looking to stash low-priority things away for
consideration after 6.13-r1.

But I don't know if all of these are low-priority things.  Because you
didn't tell me!

Please please always always describe the possible userspace-visible effects of
all fixes.  And all non-fixes, come to that.

So.  Please go through all of the patches in this series and redo the
changelogs, describing the impact each patch might have for our users.

If any of these patches should, in your opinion, be included in 6.12
and/or backported into -stable trees then it would be better to
separate them into a different patch series.  But a single patch series
is acceptable - I can figure this stuff out, if I'm given the necessary
information!  

Thanks.

Re: [PATCH RESEND V2 0/5] Fixes and cleanups to xarray

[Matthew Wilcox]

On Mon, Nov 11, 2024 at 01:28:16PM -0800, Andrew Morton wrote:
> On Tue, 12 Nov 2024 05:53:54 +0800 Kemeng Shi <shikemeng@huaweicloud.com> wrote:
> 
> > This series contains some random fixes and cleanups to xarray. Patch 1-3
> > are fixes and patch 4-5 are cleanups. More details can be found in
> > respective patches. 
> 
> As we're at -rc7 I'm looking to stash low-priority things away for
> consideration after 6.13-r1.
> 
> But I don't know if all of these are low-priority things.  Because you
> didn't tell me!

I don't think any of them fix any bugs that any code currently in the
kernel would stumble across.

Re: [PATCH RESEND V2 0/5] Fixes and cleanups to xarray

[Kemeng Shi]

on 11/12/2024 5:28 AM, Andrew Morton wrote:
> On Tue, 12 Nov 2024 05:53:54 +0800 Kemeng Shi <shikemeng@huaweicloud.com> wrote:
> 
>> This series contains some random fixes and cleanups to xarray. Patch 1-3
>> are fixes and patch 4-5 are cleanups. More details can be found in
>> respective patches. 
> 
> As we're at -rc7 I'm looking to stash low-priority things away for
> consideration after 6.13-r1.
> 
> But I don't know if all of these are low-priority things.  Because you
> didn't tell me!
> 
> Please please always always describe the possible userspace-visible effects of
> all fixes.  And all non-fixes, come to that.>
> So.  Please go through all of the patches in this series and redo the
> changelogs, describing the impact each patch might have for our users.
Sorry for missing these information, I will add detail of impact to userspace
in next version.
As there are a lot of users of xarray in kernel and I'm not familar to
most of them, I maybe not able to send new series with description of
userspace-visible effects in time. I'd like to describe effect to users
of xarray in kernel here to give some early inputs.

Patch 1 fixes the issue that xas_find_marked() will return a sibling entry
to users when there is a race to replace old entry with small range with
a new entry with bigger range. The kernel will crash if users use returned
sibling entry as a valid entry.
For example, find_get_entry() will crash if it gets a sibling entry from
xas_find_marked() when trying to search a writeback folios.

Patch 2 fixes the issue that xas_split_alloc() doesn't distinguish large
entries whose order is == xas->xa_shift + 2 * XA_CHUNK_SHIFT in whice case
the splited entries have bigger order than expected. Then afterward
xas_store will assign stored entry with bigger range than expected and we
will get wrong entry from slot after actual range of stored entry. Not
sure if we will split large entry with order == xas->xa_shift + 2 *
XA_CHUNK_SHIFT.

Patch 3 fixes the issue that xas_pause() may skip some entry unepxectedly
after xas_load()(may be called in xas_for_each for first entry) loads a
large entry with index point at mid of the entry. So we may miss to writeback
some dirty page and lost user data.

> 
> If any of these patches should, in your opinion, be included in 6.12
> and/or backported into -stable trees then it would be better to
> separate them into a different patch series.  But a single patch series
> is acceptable - I can figure this stuff out, if I'm given the necessary
> information!  
As impact descripted above, patch 1-3 should be include in 6.12 and backported
into -stable trees. But we need to confirm if the trigger condition exists
in users(filemap, shmem and so on) of xarray in real world. Will include more
information in next version.

Thanks.
> 
> Thanks.
> 

Re: [PATCH RESEND V2 0/5] Fixes and cleanups to xarray

[Matthew Wilcox]

On Tue, Nov 12, 2024 at 03:05:51PM +0800, Kemeng Shi wrote:
> Patch 1 fixes the issue that xas_find_marked() will return a sibling entry
> to users when there is a race to replace old entry with small range with
> a new entry with bigger range. The kernel will crash if users use returned
> sibling entry as a valid entry.
> For example, find_get_entry() will crash if it gets a sibling entry from
> xas_find_marked() when trying to search a writeback folios.

You _think_ this can happen, or you've observed a crash where it _has_
happened?  I don't think it can happen due to the various locks we
have.  I'm not opposed to including this patch, but I don't think it
can happen today.

> Patch 3 fixes the issue that xas_pause() may skip some entry unepxectedly
> after xas_load()(may be called in xas_for_each for first entry) loads a
> large entry with index point at mid of the entry. So we may miss to writeback
> some dirty page and lost user data.

How do we lose user data?  The inode will still contain dirty pages.
We might skip some pages we should not have skipped, but they'll be
caught by a subsequent pass, no?

Re: [PATCH RESEND V2 0/5] Fixes and cleanups to xarray

[Kemeng Shi]

on 11/12/2024 11:48 PM, Matthew Wilcox wrote:
> On Tue, Nov 12, 2024 at 03:05:51PM +0800, Kemeng Shi wrote:
>> Patch 1 fixes the issue that xas_find_marked() will return a sibling entry
>> to users when there is a race to replace old entry with small range with
>> a new entry with bigger range. The kernel will crash if users use returned
>> sibling entry as a valid entry.
>> For example, find_get_entry() will crash if it gets a sibling entry from
>> xas_find_marked() when trying to search a writeback folios.
> 
> You _think_ this can happen, or you've observed a crash where it _has_
> happened?  I don't think it can happen due to the various locks we
> have.  I'm not opposed to including this patch, but I don't think it
> can happen today.Sorry for confusion. As I mentioned at last email, we need to confirm if
the trigger condition exists in real world of all three potential bug. Here,
I want to describe the potential impact if the potential bug happens for
some early input.
> 
>> Patch 3 fixes the issue that xas_pause() may skip some entry unepxectedly
>> after xas_load()(may be called in xas_for_each for first entry) loads a
>> large entry with index point at mid of the entry. So we may miss to writeback
>> some dirty page and lost user data.
> 
> How do we lose user data?  The inode will still contain dirty pages.
> We might skip some pages we should not have skipped, but they'll be
> caught by a subsequent pass, no?
> 
After flush, users may expect dirty pages are in storage and are persistent. But
if we miss to writeback some dirty pages and kernel is reboot after flush, then
the data in un-written pages are last to users. I'm not sure if I miss something
are. But again, we need to confirm if the trigger condition exists in real world.

Thanks.

[PATCH RESEND V2 1/5] Xarray: Do not return sibling entries from xas_find_marked()

[Kemeng Shi]

Similar to issue fixed in commit cbc02854331ed ("XArray: Do not return
sibling entries from xa_load()"), we may return sibling entries from
xas_find_marked as following:
    Thread A:               Thread B:
                            xa_store_range(xa, entry, 6, 7, gfp);
			    xa_set_mark(xa, 6, mark)
    XA_STATE(xas, xa, 6);
    xas_find_marked(&xas, 7, mark);
    offset = xas_find_chunk(xas, advance, mark);
    [offset is 6 which points to a valid entry]
                            xa_store_range(xa, entry, 4, 7, gfp);
    entry = xa_entry(xa, node, 6);
    [entry is a sibling of 4]
    if (!xa_is_node(entry))
        return entry;

Skip sibling entry like xas_find() does to protect caller from seeing
sibling entry from xas_find_marked().

Besides, load_race() test is modified to catch mentioned issue and modified
load_race() only passes after this fix is merged.

Signed-off-by: Kemeng Shi <shikemeng@huaweicloud.com>
---
 lib/xarray.c                          | 2 ++
 tools/testing/radix-tree/multiorder.c | 4 ++++
 2 files changed, 6 insertions(+)

diff --git a/lib/xarray.c b/lib/xarray.c
index 32d4bac8c94c..fa87949719a0 100644
--- a/lib/xarray.c
+++ b/lib/xarray.c
@@ -1382,6 +1382,8 @@ void *xas_find_marked(struct xa_state *xas, unsigned long max, xa_mark_t mark)
 		entry = xa_entry(xas->xa, xas->xa_node, xas->xa_offset);
 		if (!entry && !(xa_track_free(xas->xa) && mark == XA_FREE_MARK))
 			continue;
+		if (xa_is_sibling(entry))
+			continue;
 		if (!xa_is_node(entry))
 			return entry;
 		xas->xa_node = xa_to_node(entry);
diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c
index cffaf2245d4f..eaff1b036989 100644
--- a/tools/testing/radix-tree/multiorder.c
+++ b/tools/testing/radix-tree/multiorder.c
@@ -227,6 +227,7 @@ static void *load_creator(void *ptr)
 			unsigned long index = (3 << RADIX_TREE_MAP_SHIFT) -
 						(1 << order);
 			item_insert_order(tree, index, order);
+			xa_set_mark(tree, index, XA_MARK_1);
 			item_delete_rcu(tree, index);
 		}
 	}
@@ -242,8 +243,11 @@ static void *load_worker(void *ptr)
 
 	rcu_register_thread();
 	while (!stop_iteration) {
+		unsigned long find_index = (2 << RADIX_TREE_MAP_SHIFT) + 1;
 		struct item *item = xa_load(ptr, index);
 		assert(!xa_is_internal(item));
+		item = xa_find(ptr, &find_index, index, XA_MARK_1);
+		assert(!xa_is_internal(item));
 	}
 	rcu_unregister_thread();
 
-- 
2.30.0

[PATCH RESEND V2 2/5] Xarray: distinguish large entries correctly in xas_split_alloc()

[Kemeng Shi]

We don't support large entries which expand two more level xa_node in
split. For case "xas->xa_shift + 2 * XA_CHUNK_SHIFT == order", we also
need two level of xa_node to expand. Distinguish entry as large entry in
case "xas->xa_shift + 2 * XA_CHUNK_SHIFT == order".

Signed-off-by: Kemeng Shi <shikemeng@huaweicloud.com>
---
 lib/xarray.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/lib/xarray.c b/lib/xarray.c
index fa87949719a0..b9fd321a02ad 100644
--- a/lib/xarray.c
+++ b/lib/xarray.c
@@ -1022,7 +1022,7 @@ void xas_split_alloc(struct xa_state *xas, void *entry, unsigned int order,
 	unsigned int mask = xas->xa_sibs;
 
 	/* XXX: no support for splitting really large entries yet */
-	if (WARN_ON(xas->xa_shift + 2 * XA_CHUNK_SHIFT < order))
+	if (WARN_ON(xas->xa_shift + 2 * XA_CHUNK_SHIFT <= order))
 		goto nomem;
 	if (xas->xa_shift + XA_CHUNK_SHIFT > order)
 		return;
-- 
2.30.0

[PATCH RESEND V2 3/5] Xarray: move forward index correctly in xas_pause()

[Kemeng Shi]

After xas_load(), xas->index could point to mid of found multi-index entry
and xas->index's bits under node->shift maybe non-zero. The afterward
xas_pause() will move forward xas->index with xa->node->shift with bits
under node->shift un-masked and thus skip some index unexpectedly.

Consider following case:
Assume XA_CHUNK_SHIFT is 4.
xa_store_range(xa, 16, 31, ...)
xa_store(xa, 32, ...)
XA_STATE(xas, xa, 17);
xas_for_each(&xas,...)
xas_load(&xas)
/* xas->index = 17, xas->xa_offset = 1, xas->xa_node->xa_shift = 4 */
xas_pause()
/* xas->index = 33, xas->xa_offset = 2, xas->xa_node->xa_shift = 4 */
As we can see, index of 32 is skipped unexpectedly.

Fix this by mask bit under node->xa_shift when move forward index in
xas_pause().

Signed-off-by: Kemeng Shi <shikemeng@huaweicloud.com>
---
 lib/test_xarray.c | 35 +++++++++++++++++++++++++++++++++++
 lib/xarray.c      |  1 +
 2 files changed, 36 insertions(+)

diff --git a/lib/test_xarray.c b/lib/test_xarray.c
index d5c5cbba33ed..6932a26f4927 100644
--- a/lib/test_xarray.c
+++ b/lib/test_xarray.c
@@ -1448,6 +1448,41 @@ static noinline void check_pause(struct xarray *xa)
 	XA_BUG_ON(xa, count != order_limit);
 
 	xa_destroy(xa);
+
+	index = 0;
+	for (order = XA_CHUNK_SHIFT; order > 0; order--) {
+		XA_BUG_ON(xa, xa_store_order(xa, index, order,
+					xa_mk_index(index), GFP_KERNEL));
+		index += 1UL << order;
+	}
+
+	index = 0;
+	count = 0;
+	xas_set(&xas, 0);
+	rcu_read_lock();
+	xas_for_each(&xas, entry, ULONG_MAX) {
+		XA_BUG_ON(xa, entry != xa_mk_index(index));
+		index += 1UL << (XA_CHUNK_SHIFT - count);
+		count++;
+	}
+	rcu_read_unlock();
+	XA_BUG_ON(xa, count != XA_CHUNK_SHIFT);
+
+	index = 0;
+	count = 0;
+	xas_set(&xas, XA_CHUNK_SIZE / 2 + 1);
+	rcu_read_lock();
+	xas_for_each(&xas, entry, ULONG_MAX) {
+		XA_BUG_ON(xa, entry != xa_mk_index(index));
+		index += 1UL << (XA_CHUNK_SHIFT - count);
+		count++;
+		xas_pause(&xas);
+	}
+	rcu_read_unlock();
+	XA_BUG_ON(xa, count != XA_CHUNK_SHIFT);
+
+	xa_destroy(xa);
+
 }
 
 static noinline void check_move_tiny(struct xarray *xa)
diff --git a/lib/xarray.c b/lib/xarray.c
index b9fd321a02ad..3fac3f2cea9d 100644
--- a/lib/xarray.c
+++ b/lib/xarray.c
@@ -1147,6 +1147,7 @@ void xas_pause(struct xa_state *xas)
 			if (!xa_is_sibling(xa_entry(xas->xa, node, offset)))
 				break;
 		}
+		xas->xa_index &= ~0UL << node->shift;
 		xas->xa_index += (offset - xas->xa_offset) << node->shift;
 		if (xas->xa_index == 0)
 			xas->xa_node = XAS_BOUNDS;
-- 
2.30.0

[PATCH RESEND V2 4/5] Xarray: remove repeat check in xas_squash_marks()

[Kemeng Shi]

Caller of xas_squash_marks() has ensured xas->xa_sibs is non-zero. Just
remove repeat check of xas->xa_sibs in xas_squash_marks().

Signed-off-by: Kemeng Shi <shikemeng@huaweicloud.com>
---
 lib/xarray.c | 3 ---
 1 file changed, 3 deletions(-)

diff --git a/lib/xarray.c b/lib/xarray.c
index 3fac3f2cea9d..4231af284bd8 100644
--- a/lib/xarray.c
+++ b/lib/xarray.c
@@ -128,9 +128,6 @@ static void xas_squash_marks(const struct xa_state *xas)
 	unsigned int mark = 0;
 	unsigned int limit = xas->xa_offset + xas->xa_sibs + 1;
 
-	if (!xas->xa_sibs)
-		return;
-
 	do {
 		unsigned long *marks = xas->xa_node->marks[mark];
 		if (find_next_bit(marks, limit, xas->xa_offset + 1) == limit)
-- 
2.30.0

[PATCH RESEND V2 5/5] Xarray: use xa_mark_t in xas_squash_marks() to keep code consistent

[Kemeng Shi]

Besides xas_squash_marks(), all functions use xa_mark_t type to iterate
all possible marks. Use xa_mark_t in xas_squash_marks() to keep code
consistent.

Signed-off-by: Kemeng Shi <shikemeng@huaweicloud.com>
---
 lib/xarray.c | 20 ++++++++++++--------
 1 file changed, 12 insertions(+), 8 deletions(-)

diff --git a/lib/xarray.c b/lib/xarray.c
index 4231af284bd8..a74795911f1c 100644
--- a/lib/xarray.c
+++ b/lib/xarray.c
@@ -125,16 +125,20 @@ static inline void node_mark_all(struct xa_node *node, xa_mark_t mark)
  */
 static void xas_squash_marks(const struct xa_state *xas)
 {
-	unsigned int mark = 0;
+	xa_mark_t mark = 0;
 	unsigned int limit = xas->xa_offset + xas->xa_sibs + 1;
 
-	do {
-		unsigned long *marks = xas->xa_node->marks[mark];
-		if (find_next_bit(marks, limit, xas->xa_offset + 1) == limit)
-			continue;
-		__set_bit(xas->xa_offset, marks);
-		bitmap_clear(marks, xas->xa_offset + 1, xas->xa_sibs);
-	} while (mark++ != (__force unsigned)XA_MARK_MAX);
+	for (;;) {
+		unsigned long *marks = node_marks(xas->xa_node, mark);
+
+		if (find_next_bit(marks, limit, xas->xa_offset + 1) != limit) {
+			__set_bit(xas->xa_offset, marks);
+			bitmap_clear(marks, xas->xa_offset + 1, xas->xa_sibs);
+		}
+		if (mark == XA_MARK_MAX)
+			break;
+		mark_inc(mark);
+	}
 }
 
 /* extracts the offset within this node from the index */
-- 
2.30.0