From 12efebab09e383bf366bec323bd296b7d90e1c43 Mon Sep 17 00:00:00 2001 From: "Matthew Wilcox (Oracle)" Date: Sat, 10 Oct 2020 11:17:44 -0400 Subject: XArray: Fix split documentation I wrote the documentation backwards; the new order of the entry is stored in the xas and the caller passes the old entry. Reported-by: Zi Yan Signed-off-by: Matthew Wilcox (Oracle) --- lib/xarray.c | 7 ++++--- 1 file changed, 4 insertions(+), 3 deletions(-) diff --git a/lib/xarray.c b/lib/xarray.c index 5fa51614802a..fb3a0ccebb7e 100644 --- a/lib/xarray.c +++ b/lib/xarray.c @@ -987,7 +987,7 @@ static void node_set_marks(struct xa_node *node, unsigned int offset, * xas_split_alloc() - Allocate memory for splitting an entry. * @xas: XArray operation state. * @entry: New entry which will be stored in the array. - * @order: New entry order. + * @order: Current entry order. * @gfp: Memory allocation flags. * * This function should be called before calling xas_split(). @@ -1041,9 +1041,10 @@ EXPORT_SYMBOL_GPL(xas_split_alloc); * xas_split() - Split a multi-index entry into smaller entries. * @xas: XArray operation state. * @entry: New entry to store in the array. - * @order: New entry order. + * @order: Current entry order. * - * The value in the entry is copied to all the replacement entries. + * The size of the new entries is set in @xas. The value in @entry is + * copied to all the replacement entries. * * Context: Any context. The caller should hold the xa_lock. */ -- cgit v1.2.3 From 3012110d71f41410932924e1d188f9eb57f1f824 Mon Sep 17 00:00:00 2001 From: "Matthew Wilcox (Oracle)" Date: Thu, 19 Nov 2020 08:32:31 -0500 Subject: XArray: Fix splitting to non-zero orders Splitting an order-4 entry into order-2 entries would leave the array containing pointers to 000040008000c000 instead of 000044448888cccc. This is a one-character fix, but enhance the test suite to check this case. Reported-by: Zi Yan Signed-off-by: Matthew Wilcox (Oracle) --- lib/test_xarray.c | 26 ++++++++++++++------------ lib/xarray.c | 4 ++-- 2 files changed, 16 insertions(+), 14 deletions(-) diff --git a/lib/test_xarray.c b/lib/test_xarray.c index 8294f43f4981..8b1c318189ce 100644 --- a/lib/test_xarray.c +++ b/lib/test_xarray.c @@ -1530,24 +1530,24 @@ static noinline void check_store_range(struct xarray *xa) #ifdef CONFIG_XARRAY_MULTI static void check_split_1(struct xarray *xa, unsigned long index, - unsigned int order) + unsigned int order, unsigned int new_order) { - XA_STATE(xas, xa, index); - void *entry; - unsigned int i = 0; + XA_STATE_ORDER(xas, xa, index, new_order); + unsigned int i; xa_store_order(xa, index, order, xa, GFP_KERNEL); xas_split_alloc(&xas, xa, order, GFP_KERNEL); xas_lock(&xas); xas_split(&xas, xa, order); + for (i = 0; i < (1 << order); i += (1 << new_order)) + __xa_store(xa, index + i, xa_mk_index(index + i), 0); xas_unlock(&xas); - xa_for_each(xa, index, entry) { - XA_BUG_ON(xa, entry != xa); - i++; + for (i = 0; i < (1 << order); i++) { + unsigned int val = index + (i & ~((1 << new_order) - 1)); + XA_BUG_ON(xa, xa_load(xa, index + i) != xa_mk_index(val)); } - XA_BUG_ON(xa, i != 1 << order); xa_set_mark(xa, index, XA_MARK_0); XA_BUG_ON(xa, !xa_get_mark(xa, index, XA_MARK_0)); @@ -1557,14 +1557,16 @@ static void check_split_1(struct xarray *xa, unsigned long index, static noinline void check_split(struct xarray *xa) { - unsigned int order; + unsigned int order, new_order; XA_BUG_ON(xa, !xa_empty(xa)); for (order = 1; order < 2 * XA_CHUNK_SHIFT; order++) { - check_split_1(xa, 0, order); - check_split_1(xa, 1UL << order, order); - check_split_1(xa, 3UL << order, order); + for (new_order = 0; new_order < order; new_order++) { + check_split_1(xa, 0, order, new_order); + check_split_1(xa, 1UL << order, order, new_order); + check_split_1(xa, 3UL << order, order, new_order); + } } } #else diff --git a/lib/xarray.c b/lib/xarray.c index fb3a0ccebb7e..f5d8f54907b4 100644 --- a/lib/xarray.c +++ b/lib/xarray.c @@ -1011,7 +1011,7 @@ void xas_split_alloc(struct xa_state *xas, void *entry, unsigned int order, do { unsigned int i; - void *sibling; + void *sibling = NULL; struct xa_node *node; node = kmem_cache_alloc(radix_tree_node_cachep, gfp); @@ -1021,7 +1021,7 @@ void xas_split_alloc(struct xa_state *xas, void *entry, unsigned int order, for (i = 0; i < XA_CHUNK_SIZE; i++) { if ((i & mask) == 0) { RCU_INIT_POINTER(node->slots[i], entry); - sibling = xa_mk_sibling(0); + sibling = xa_mk_sibling(i); } else { RCU_INIT_POINTER(node->slots[i], sibling); } -- cgit v1.2.3 From df59d0a461bc5935232bf56a279e4d7a71c566a5 Mon Sep 17 00:00:00 2001 From: "Matthew Wilcox (Oracle)" Date: Tue, 30 Mar 2021 13:40:27 -0400 Subject: XArray: Add xa_limit_16b A 16-bit limit is a more common limit than I had realised. Make it generally available. Signed-off-by: Matthew Wilcox (Oracle) --- include/linux/xarray.h | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-) diff --git a/include/linux/xarray.h b/include/linux/xarray.h index 92c0160b3352..a91e3d90df8a 100644 --- a/include/linux/xarray.h +++ b/include/linux/xarray.h @@ -229,9 +229,10 @@ static inline int xa_err(void *entry) * * This structure is used either directly or via the XA_LIMIT() macro * to communicate the range of IDs that are valid for allocation. - * Two common ranges are predefined for you: + * Three common ranges are predefined for you: * * xa_limit_32b - [0 - UINT_MAX] * * xa_limit_31b - [0 - INT_MAX] + * * xa_limit_16b - [0 - USHRT_MAX] */ struct xa_limit { u32 max; @@ -242,6 +243,7 @@ struct xa_limit { #define xa_limit_32b XA_LIMIT(0, UINT_MAX) #define xa_limit_31b XA_LIMIT(0, INT_MAX) +#define xa_limit_16b XA_LIMIT(0, USHRT_MAX) typedef unsigned __bitwise xa_mark_t; #define XA_MARK_0 ((__force xa_mark_t)0U) -- cgit v1.2.3 From 7487de534dcbe143e6f41da751dd3ffcf93b00ee Mon Sep 17 00:00:00 2001 From: "Matthew Wilcox (Oracle)" Date: Tue, 30 Mar 2021 13:44:35 -0400 Subject: radix tree test suite: Fix compilation Commit 4bba4c4bb09a added tools/include/linux/compiler_types.h which includes linux/compiler-gcc.h. Unfortunately, we had our own (empty) compiler_types.h which overrode the one added by that commit, and so we lost the definition of __must_be_array(). Removing our empty compiler_types.h fixes the problem and reduces our divergence from the rest of the tools. Signed-off-by: Matthew Wilcox (Oracle) --- tools/testing/radix-tree/linux/compiler_types.h | 0 1 file changed, 0 insertions(+), 0 deletions(-) delete mode 100644 tools/testing/radix-tree/linux/compiler_types.h diff --git a/tools/testing/radix-tree/linux/compiler_types.h b/tools/testing/radix-tree/linux/compiler_types.h deleted file mode 100644 index e69de29bb2d1..000000000000 -- cgit v1.2.3 From 1bb4bd266cf39fd2fa711f2d265c558b92df1119 Mon Sep 17 00:00:00 2001 From: "Matthew Wilcox (Oracle)" Date: Wed, 31 Mar 2021 14:59:19 -0400 Subject: radix tree test suite: Register the main thread with the RCU library Several test runners register individual worker threads with the RCU library, but neglect to register the main thread, which can lead to objects being freed while the main thread is in what appears to be an RCU critical section. Reported-by: Chris von Recklinghausen Signed-off-by: Matthew Wilcox (Oracle) --- tools/testing/radix-tree/idr-test.c | 2 ++ tools/testing/radix-tree/multiorder.c | 2 ++ tools/testing/radix-tree/xarray.c | 2 ++ 3 files changed, 6 insertions(+) diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c index 3b796dd5e577..44ceff95a9b3 100644 --- a/tools/testing/radix-tree/idr-test.c +++ b/tools/testing/radix-tree/idr-test.c @@ -577,6 +577,7 @@ void ida_tests(void) int __weak main(void) { + rcu_register_thread(); radix_tree_init(); idr_checks(); ida_tests(); @@ -584,5 +585,6 @@ int __weak main(void) rcu_barrier(); if (nr_allocated) printf("nr_allocated = %d\n", nr_allocated); + rcu_unregister_thread(); return 0; } diff --git a/tools/testing/radix-tree/multiorder.c b/tools/testing/radix-tree/multiorder.c index 9eae0fb5a67d..e00520cc6349 100644 --- a/tools/testing/radix-tree/multiorder.c +++ b/tools/testing/radix-tree/multiorder.c @@ -224,7 +224,9 @@ void multiorder_checks(void) int __weak main(void) { + rcu_register_thread(); radix_tree_init(); multiorder_checks(); + rcu_unregister_thread(); return 0; } diff --git a/tools/testing/radix-tree/xarray.c b/tools/testing/radix-tree/xarray.c index e61e43efe463..f20e12cbbfd4 100644 --- a/tools/testing/radix-tree/xarray.c +++ b/tools/testing/radix-tree/xarray.c @@ -25,11 +25,13 @@ void xarray_tests(void) int __weak main(void) { + rcu_register_thread(); radix_tree_init(); xarray_tests(); radix_tree_cpu_dead(1); rcu_barrier(); if (nr_allocated) printf("nr_allocated = %d\n", nr_allocated); + rcu_unregister_thread(); return 0; } -- cgit v1.2.3 From 703586410da69eb40062e64d413ca33bd735917a Mon Sep 17 00:00:00 2001 From: "Matthew Wilcox (Oracle)" Date: Thu, 1 Apr 2021 07:44:48 -0400 Subject: idr test suite: Take RCU read lock in idr_find_test_1 When run on a single CPU, this test would frequently access already-freed memory. Due to timing, this bug never showed up on multi-CPU tests. Reported-by: Chris von Recklinghausen Signed-off-by: Matthew Wilcox (Oracle) --- tools/testing/radix-tree/idr-test.c | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c index 44ceff95a9b3..4a9b451b7ba0 100644 --- a/tools/testing/radix-tree/idr-test.c +++ b/tools/testing/radix-tree/idr-test.c @@ -306,11 +306,15 @@ void idr_find_test_1(int anchor_id, int throbber_id) BUG_ON(idr_alloc(&find_idr, xa_mk_value(anchor_id), anchor_id, anchor_id + 1, GFP_KERNEL) != anchor_id); + rcu_read_lock(); do { int id = 0; void *entry = idr_get_next(&find_idr, &id); + rcu_read_unlock(); BUG_ON(entry != xa_mk_value(id)); + rcu_read_lock(); } while (time(NULL) < start + 11); + rcu_read_unlock(); pthread_join(throbber, NULL); -- cgit v1.2.3 From 094ffbd1d8eaa27ed426feb8530cb1456348b018 Mon Sep 17 00:00:00 2001 From: "Matthew Wilcox (Oracle)" Date: Thu, 1 Apr 2021 07:46:49 -0400 Subject: idr test suite: Create anchor before launching throbber The throbber could race with creation of the anchor entry and cause the IDR to have zero entries in it, which would cause the test to fail. Signed-off-by: Matthew Wilcox (Oracle) --- tools/testing/radix-tree/idr-test.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c index 4a9b451b7ba0..6ce7460f3c7a 100644 --- a/tools/testing/radix-tree/idr-test.c +++ b/tools/testing/radix-tree/idr-test.c @@ -301,11 +301,11 @@ void idr_find_test_1(int anchor_id, int throbber_id) pthread_t throbber; time_t start = time(NULL); - pthread_create(&throbber, NULL, idr_throbber, &throbber_id); - BUG_ON(idr_alloc(&find_idr, xa_mk_value(anchor_id), anchor_id, anchor_id + 1, GFP_KERNEL) != anchor_id); + pthread_create(&throbber, NULL, idr_throbber, &throbber_id); + rcu_read_lock(); do { int id = 0; -- cgit v1.2.3 From 2c7e57a02708a69d0194f9ef2a7b7e54f5a0484a Mon Sep 17 00:00:00 2001 From: "Matthew Wilcox (Oracle)" Date: Thu, 1 Apr 2021 07:50:42 -0400 Subject: idr test suite: Improve reporting from idr_find_test_1 Instead of just reporting an assertion failure, report enough information that we can start diagnosing exactly went wrong. Signed-off-by: Matthew Wilcox (Oracle) --- tools/testing/radix-tree/idr-test.c | 11 ++++++++++- 1 file changed, 10 insertions(+), 1 deletion(-) diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c index 6ce7460f3c7a..ca24f6839d50 100644 --- a/tools/testing/radix-tree/idr-test.c +++ b/tools/testing/radix-tree/idr-test.c @@ -296,6 +296,10 @@ static void *idr_throbber(void *arg) return NULL; } +/* + * There are always either 1 or 2 objects in the IDR. If we find nothing, + * or we find something at an ID we didn't expect, that's a bug. + */ void idr_find_test_1(int anchor_id, int throbber_id) { pthread_t throbber; @@ -311,7 +315,12 @@ void idr_find_test_1(int anchor_id, int throbber_id) int id = 0; void *entry = idr_get_next(&find_idr, &id); rcu_read_unlock(); - BUG_ON(entry != xa_mk_value(id)); + if ((id != anchor_id && id != throbber_id) || + entry != xa_mk_value(id)) { + printf("%s(%d, %d): %p at %d\n", __func__, anchor_id, + throbber_id, entry, id); + abort(); + } rcu_read_lock(); } while (time(NULL) < start + 11); rcu_read_unlock(); -- cgit v1.2.3