From: Matthew Wilcox willy@infradead.org
mainline inclusion from mainline-v4.20-rc7 commit eff3860bbfedbac6edac57fb0d7f3a60e860c1c3 category: bugfix bugzilla: CVE: NA
Reference: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?i... -------------------------------------------
Commit 66ee620f06f9 ("idr: Permit any valid kernel pointer to be stored") changed the radix tree lookup so that it stops when reaching the bottom of the tree. However, the condition was added in the wrong place, making it possible to return retry entries to the caller. Reorder the tests to check for the retry entry before checking whether we're at the bottom of the tree. The retry entry should never be found in the tree root, so it's safe to defer the check until the end of the loop.
Add a regression test to the test-suite to be sure this doesn't come back.
Fixes: 66ee620f06f9 ("idr: Permit any valid kernel pointer to be stored") Reported-by: Greg Kurz groug@kaod.org Signed-off-by: Matthew Wilcox willy@infradead.org
Conflict: tools/testing/radix-tree/Makefile
Signed-off-by: Ye Weihua yeweihua4@huawei.com --- lib/radix-tree.c | 4 +- tools/testing/radix-tree/Makefile | 1 + tools/testing/radix-tree/main.c | 1 + tools/testing/radix-tree/regression.h | 1 + tools/testing/radix-tree/regression4.c | 79 ++++++++++++++++++++++++++ 5 files changed, 84 insertions(+), 2 deletions(-) create mode 100644 tools/testing/radix-tree/regression4.c
diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 0a417b4f173f..e4888dc5bd30 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -1052,11 +1052,11 @@ void *__radix_tree_lookup(const struct radix_tree_root *root, while (radix_tree_is_internal_node(node)) { unsigned offset;
- if (node == RADIX_TREE_RETRY) - goto restart; parent = entry_to_node(node); offset = radix_tree_descend(parent, &node, index); slot = parent->slots + offset; + if (node == RADIX_TREE_RETRY) + goto restart; if (parent->shift == 0) break; } diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile index 37baecc3766f..4bb4ddffb6b7 100644 --- a/tools/testing/radix-tree/Makefile +++ b/tools/testing/radix-tree/Makefile @@ -7,6 +7,7 @@ LDLIBS+= -lpthread -lurcu TARGETS = main idr-test multiorder CORE_OFILES := radix-tree.o idr.o linux.o test.o find_bit.o OFILES = main.o $(CORE_OFILES) regression1.o regression2.o regression3.o \ + regression4.o \ tag_check.o multiorder.o idr-test.o iteration_check.o benchmark.o
ifndef SHIFT diff --git a/tools/testing/radix-tree/main.c b/tools/testing/radix-tree/main.c index b741686e53d6..b96d469b8693 100644 --- a/tools/testing/radix-tree/main.c +++ b/tools/testing/radix-tree/main.c @@ -368,6 +368,7 @@ int main(int argc, char **argv) regression1_test(); regression2_test(); regression3_test(); + regression4_test(); iteration_test(0, 10 + 90 * long_run); iteration_test(7, 10 + 90 * long_run); single_thread_tests(long_run); diff --git a/tools/testing/radix-tree/regression.h b/tools/testing/radix-tree/regression.h index 3c8a1584e9ee..135145af18b7 100644 --- a/tools/testing/radix-tree/regression.h +++ b/tools/testing/radix-tree/regression.h @@ -5,5 +5,6 @@ void regression1_test(void); void regression2_test(void); void regression3_test(void); +void regression4_test(void);
#endif diff --git a/tools/testing/radix-tree/regression4.c b/tools/testing/radix-tree/regression4.c new file mode 100644 index 000000000000..cf4e5aba6b08 --- /dev/null +++ b/tools/testing/radix-tree/regression4.c @@ -0,0 +1,79 @@ +// SPDX-License-Identifier: GPL-2.0 +#include <linux/kernel.h> +#include <linux/gfp.h> +#include <linux/slab.h> +#include <linux/radix-tree.h> +#include <linux/rcupdate.h> +#include <stdlib.h> +#include <pthread.h> +#include <stdio.h> +#include <assert.h> + +#include "regression.h" + +static pthread_barrier_t worker_barrier; +static int obj0, obj1; +static RADIX_TREE(mt_tree, GFP_KERNEL); + +static void *reader_fn(void *arg) +{ + int i; + void *entry; + + rcu_register_thread(); + pthread_barrier_wait(&worker_barrier); + + for (i = 0; i < 1000000; i++) { + rcu_read_lock(); + entry = radix_tree_lookup(&mt_tree, 0); + rcu_read_unlock(); + if (entry != &obj0) { + printf("iteration %d bad entry = %p\n", i, entry); + abort(); + } + } + + rcu_unregister_thread(); + + return NULL; +} + +static void *writer_fn(void *arg) +{ + int i; + + rcu_register_thread(); + pthread_barrier_wait(&worker_barrier); + + for (i = 0; i < 1000000; i++) { + radix_tree_insert(&mt_tree, 1, &obj1); + radix_tree_delete(&mt_tree, 1); + } + + rcu_unregister_thread(); + + return NULL; +} + +void regression4_test(void) +{ + pthread_t reader, writer; + + printv(1, "regression test 4 starting\n"); + + radix_tree_insert(&mt_tree, 0, &obj0); + pthread_barrier_init(&worker_barrier, NULL, 2); + + if (pthread_create(&reader, NULL, reader_fn, NULL) || + pthread_create(&writer, NULL, writer_fn, NULL)) { + perror("pthread_create"); + exit(1); + } + + if (pthread_join(reader, NULL) || pthread_join(writer, NULL)) { + perror("pthread_join"); + exit(1); + } + + printv(1, "regression test 4 passed\n"); +}