From 82a22311b7a68a78709699dc8c098953b70e4fd2 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox (Oracle) Date: Thu, 7 Nov 2019 22:49:11 -0500 Subject: XArray: Fix xas_pause at ULONG_MAX If we were unlucky enough to call xas_pause() when the index was at ULONG_MAX (or a multi-slot entry which ends at ULONG_MAX), we would wrap the index back around to 0 and restart the iteration from the beginning. Use the XAS_BOUNDS state to indicate that we should just stop the iteration. Signed-off-by: Matthew Wilcox (Oracle) --- lib/test_xarray.c | 22 ++++++++++++++++++++++ lib/xarray.c | 8 +++++--- 2 files changed, 27 insertions(+), 3 deletions(-) (limited to 'lib') diff --git a/lib/test_xarray.c b/lib/test_xarray.c index 7df4f7f395bf..c477f22a95cd 100644 --- a/lib/test_xarray.c +++ b/lib/test_xarray.c @@ -1132,6 +1132,27 @@ static noinline void check_move_tiny(struct xarray *xa) XA_BUG_ON(xa, !xa_empty(xa)); } +static noinline void check_move_max(struct xarray *xa) +{ + XA_STATE(xas, xa, 0); + + xa_store_index(xa, ULONG_MAX, GFP_KERNEL); + rcu_read_lock(); + XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != xa_mk_index(ULONG_MAX)); + XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != NULL); + rcu_read_unlock(); + + xas_set(&xas, 0); + rcu_read_lock(); + XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != xa_mk_index(ULONG_MAX)); + xas_pause(&xas); + XA_BUG_ON(xa, xas_find(&xas, ULONG_MAX) != NULL); + rcu_read_unlock(); + + xa_erase_index(xa, ULONG_MAX); + XA_BUG_ON(xa, !xa_empty(xa)); +} + static noinline void check_move_small(struct xarray *xa, unsigned long idx) { XA_STATE(xas, xa, 0); @@ -1240,6 +1261,7 @@ static noinline void check_move(struct xarray *xa) xa_destroy(xa); check_move_tiny(xa); + check_move_max(xa); for (i = 0; i < 16; i++) check_move_small(xa, 1UL << i); diff --git a/lib/xarray.c b/lib/xarray.c index 1237c213f52b..bfaaa2c1f3fe 100644 --- a/lib/xarray.c +++ b/lib/xarray.c @@ -967,6 +967,7 @@ void xas_pause(struct xa_state *xas) if (xas_invalid(xas)) return; + xas->xa_node = XAS_RESTART; if (node) { unsigned int offset = xas->xa_offset; while (++offset < XA_CHUNK_SIZE) { @@ -974,10 +975,11 @@ void xas_pause(struct xa_state *xas) break; } xas->xa_index += (offset - xas->xa_offset) << node->shift; + if (xas->xa_index == 0) + xas->xa_node = XAS_BOUNDS; } else { xas->xa_index++; } - xas->xa_node = XAS_RESTART; } EXPORT_SYMBOL_GPL(xas_pause); @@ -1079,13 +1081,13 @@ void *xas_find(struct xa_state *xas, unsigned long max) { void *entry; - if (xas_error(xas)) + if (xas_error(xas) || xas->xa_node == XAS_BOUNDS) return NULL; if (!xas->xa_node) { xas->xa_index = 1; return set_bounds(xas); - } else if (xas_top(xas->xa_node)) { + } else if (xas->xa_node == XAS_RESTART) { entry = xas_load(xas); if (entry || xas_not_node(xas->xa_node)) return entry; -- cgit v1.2.3 From 430f24f94c8a174d411a550d7b5529301922e67a Mon Sep 17 00:00:00 2001 From: Matthew Wilcox (Oracle) Date: Fri, 17 Jan 2020 17:45:12 -0500 Subject: XArray: Fix infinite loop with entry at ULONG_MAX If there is an entry at ULONG_MAX, xa_for_each() will overflow the 'index + 1' in xa_find_after() and wrap around to 0. Catch this case and terminate the loop by returning NULL. Signed-off-by: Matthew Wilcox (Oracle) Cc: stable@vger.kernel.org --- lib/test_xarray.c | 17 +++++++++++++++++ lib/xarray.c | 3 +++ 2 files changed, 20 insertions(+) (limited to 'lib') diff --git a/lib/test_xarray.c b/lib/test_xarray.c index c477f22a95cd..90584c63ca39 100644 --- a/lib/test_xarray.c +++ b/lib/test_xarray.c @@ -1046,11 +1046,28 @@ static noinline void check_find_3(struct xarray *xa) xa_destroy(xa); } +static noinline void check_find_4(struct xarray *xa) +{ + unsigned long index = 0; + void *entry; + + xa_store_index(xa, ULONG_MAX, GFP_KERNEL); + + entry = xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT); + XA_BUG_ON(xa, entry != xa_mk_index(ULONG_MAX)); + + entry = xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT); + XA_BUG_ON(xa, entry); + + xa_erase_index(xa, ULONG_MAX); +} + static noinline void check_find(struct xarray *xa) { check_find_1(xa); check_find_2(xa); check_find_3(xa); + check_find_4(xa); check_multi_find(xa); check_multi_find_2(xa); } diff --git a/lib/xarray.c b/lib/xarray.c index bfaaa2c1f3fe..6ecf35c2e1da 100644 --- a/lib/xarray.c +++ b/lib/xarray.c @@ -1849,6 +1849,9 @@ void *xa_find_after(struct xarray *xa, unsigned long *indexp, XA_STATE(xas, xa, *indexp + 1); void *entry; + if (xas.xa_index == 0) + return NULL; + rcu_read_lock(); for (;;) { if ((__force unsigned int)filter < XA_MAX_MARKS) -- cgit v1.2.3 From 19c30f4dd0923ef191f35c652ee4058e91e89056 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox (Oracle) Date: Fri, 17 Jan 2020 22:00:41 -0500 Subject: XArray: Fix xa_find_after with multi-index entries If the entry is of an order which is a multiple of XA_CHUNK_SIZE, the current detection of sibling entries does not work. Factor out an xas_sibling() function to make xa_find_after() a little more understandable, and write a new implementation that doesn't suffer from the same bug. Signed-off-by: Matthew Wilcox (Oracle) Cc: stable@vger.kernel.org --- lib/test_xarray.c | 32 +++++++++++++++++++------------- lib/xarray.c | 20 +++++++++++++------- 2 files changed, 32 insertions(+), 20 deletions(-) (limited to 'lib') diff --git a/lib/test_xarray.c b/lib/test_xarray.c index 90584c63ca39..c8cc97ded0fa 100644 --- a/lib/test_xarray.c +++ b/lib/test_xarray.c @@ -902,28 +902,30 @@ static noinline void check_store_iter(struct xarray *xa) XA_BUG_ON(xa, !xa_empty(xa)); } -static noinline void check_multi_find(struct xarray *xa) +static noinline void check_multi_find_1(struct xarray *xa, unsigned order) { #ifdef CONFIG_XARRAY_MULTI + unsigned long multi = 3 << order; + unsigned long next = 4 << order; unsigned long index; - xa_store_order(xa, 12, 2, xa_mk_value(12), GFP_KERNEL); - XA_BUG_ON(xa, xa_store_index(xa, 16, GFP_KERNEL) != NULL); + xa_store_order(xa, multi, order, xa_mk_value(multi), GFP_KERNEL); + XA_BUG_ON(xa, xa_store_index(xa, next, GFP_KERNEL) != NULL); index = 0; XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) != - xa_mk_value(12)); - XA_BUG_ON(xa, index != 12); - index = 13; + xa_mk_value(multi)); + XA_BUG_ON(xa, index != multi); + index = multi + 1; XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) != - xa_mk_value(12)); - XA_BUG_ON(xa, (index < 12) || (index >= 16)); + xa_mk_value(multi)); + XA_BUG_ON(xa, (index < multi) || (index >= next)); XA_BUG_ON(xa, xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT) != - xa_mk_value(16)); - XA_BUG_ON(xa, index != 16); + xa_mk_value(next)); + XA_BUG_ON(xa, index != next); - xa_erase_index(xa, 12); - xa_erase_index(xa, 16); + xa_erase_index(xa, multi); + xa_erase_index(xa, next); XA_BUG_ON(xa, !xa_empty(xa)); #endif } @@ -1064,11 +1066,15 @@ static noinline void check_find_4(struct xarray *xa) static noinline void check_find(struct xarray *xa) { + unsigned i; + check_find_1(xa); check_find_2(xa); check_find_3(xa); check_find_4(xa); - check_multi_find(xa); + + for (i = 2; i < 10; i++) + check_multi_find_1(xa, i); check_multi_find_2(xa); } diff --git a/lib/xarray.c b/lib/xarray.c index 6ecf35c2e1da..03300a0d6425 100644 --- a/lib/xarray.c +++ b/lib/xarray.c @@ -1826,6 +1826,17 @@ void *xa_find(struct xarray *xa, unsigned long *indexp, } EXPORT_SYMBOL(xa_find); +static bool xas_sibling(struct xa_state *xas) +{ + struct xa_node *node = xas->xa_node; + unsigned long mask; + + if (!node) + return false; + mask = (XA_CHUNK_SIZE << node->shift) - 1; + return (xas->xa_index & mask) > (xas->xa_offset << node->shift); +} + /** * xa_find_after() - Search the XArray for a present entry. * @xa: XArray. @@ -1860,13 +1871,8 @@ void *xa_find_after(struct xarray *xa, unsigned long *indexp, entry = xas_find(&xas, max); if (xas.xa_node == XAS_BOUNDS) break; - if (xas.xa_shift) { - if (xas.xa_index & ((1UL << xas.xa_shift) - 1)) - continue; - } else { - if (xas.xa_offset < (xas.xa_index & XA_CHUNK_MASK)) - continue; - } + if (xas_sibling(&xas)) + continue; if (!xas_retry(&xas, entry)) break; } -- cgit v1.2.3 From c44aa5e8ab58b5f4cf473970ec784c3333496a2e Mon Sep 17 00:00:00 2001 From: Matthew Wilcox (Oracle) Date: Fri, 17 Jan 2020 22:13:21 -0500 Subject: XArray: Fix xas_find returning too many entries If you call xas_find() with the initial index > max, it should have returned NULL but was returning the entry at index. Signed-off-by: Matthew Wilcox (Oracle) Cc: stable@vger.kernel.org --- lib/test_xarray.c | 5 +++++ lib/xarray.c | 10 ++++++++-- 2 files changed, 13 insertions(+), 2 deletions(-) (limited to 'lib') diff --git a/lib/test_xarray.c b/lib/test_xarray.c index c8cc97ded0fa..55c14e8c8859 100644 --- a/lib/test_xarray.c +++ b/lib/test_xarray.c @@ -2,6 +2,7 @@ /* * test_xarray.c: Test the XArray API * Copyright (c) 2017-2018 Microsoft Corporation + * Copyright (c) 2019-2020 Oracle * Author: Matthew Wilcox */ @@ -911,6 +912,7 @@ static noinline void check_multi_find_1(struct xarray *xa, unsigned order) xa_store_order(xa, multi, order, xa_mk_value(multi), GFP_KERNEL); XA_BUG_ON(xa, xa_store_index(xa, next, GFP_KERNEL) != NULL); + XA_BUG_ON(xa, xa_store_index(xa, next + 1, GFP_KERNEL) != NULL); index = 0; XA_BUG_ON(xa, xa_find(xa, &index, ULONG_MAX, XA_PRESENT) != @@ -923,9 +925,12 @@ static noinline void check_multi_find_1(struct xarray *xa, unsigned order) XA_BUG_ON(xa, xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT) != xa_mk_value(next)); XA_BUG_ON(xa, index != next); + XA_BUG_ON(xa, xa_find_after(xa, &index, next, XA_PRESENT) != NULL); + XA_BUG_ON(xa, index != next); xa_erase_index(xa, multi); xa_erase_index(xa, next); + xa_erase_index(xa, next + 1); XA_BUG_ON(xa, !xa_empty(xa)); #endif } diff --git a/lib/xarray.c b/lib/xarray.c index 03300a0d6425..1d9fab7db8da 100644 --- a/lib/xarray.c +++ b/lib/xarray.c @@ -1,7 +1,8 @@ // SPDX-License-Identifier: GPL-2.0+ /* * XArray implementation - * Copyright (c) 2017 Microsoft Corporation + * Copyright (c) 2017-2018 Microsoft Corporation + * Copyright (c) 2018-2020 Oracle * Author: Matthew Wilcox */ @@ -1083,6 +1084,8 @@ void *xas_find(struct xa_state *xas, unsigned long max) if (xas_error(xas) || xas->xa_node == XAS_BOUNDS) return NULL; + if (xas->xa_index > max) + return set_bounds(xas); if (!xas->xa_node) { xas->xa_index = 1; @@ -1152,6 +1155,8 @@ void *xas_find_marked(struct xa_state *xas, unsigned long max, xa_mark_t mark) if (xas_error(xas)) return NULL; + if (xas->xa_index > max) + goto max; if (!xas->xa_node) { xas->xa_index = 1; @@ -1869,7 +1874,8 @@ void *xa_find_after(struct xarray *xa, unsigned long *indexp, entry = xas_find_marked(&xas, max, filter); else entry = xas_find(&xas, max); - if (xas.xa_node == XAS_BOUNDS) + + if (xas_invalid(&xas)) break; if (xas_sibling(&xas)) continue; -- cgit v1.2.3