* [PATCH 0/2] Radix tree retry bug fix & test case
@ 2016-02-05 3:40 Matthew Wilcox
2016-02-05 3:40 ` [PATCH 1/2] radix-tree tests: Add regression3 test Matthew Wilcox
` (2 more replies)
0 siblings, 3 replies; 4+ messages in thread
From: Matthew Wilcox @ 2016-02-05 3:40 UTC (permalink / raw)
To: Konstantin Khlebnikov, Andrew Morton
Cc: Matthew Wilcox, Hugh Dickins, linux-kernel, linux-fsdevel,
linux-mm
Konstantin pointed out my braino when using radix_tree_iter_retry(),
and then pointed out a second braino. I think we can fix both brainos
with one simple test (the advantage of having your braino pointed out
to you is that you know what you were expecting to happen, so you can
sometimes propose simlpy making happen what you expected to happen.
Konstantin doesn't have access to my though tprocesses.)
Kontantin wrote a really great test ... and then didn't add it to the
test suite. That made me sad, so I added it.
Andrew, can you drop radix-tree-fix-oops-after-radix_tree_iter_retry.patch
from your tree and add these two patches instead? If you prefer
Konstantin's fix to this one, I'll send you another patch to fix the
second problem Konstantin pointed out.
I was a bit unsure about the proper attribution here. The essentials
of the test-suite change from Konstantin are unchanged, but he didn't
have his own sign-off on it. So I made him 'From' and only added my
own sign-off.
Konstantin Khlebnikov (1):
radix-tree tests: Add regression3 test
Matthew Wilcox (1):
radix-tree: fix oops after radix_tree_iter_retry
include/linux/radix-tree.h | 3 ++
tools/testing/radix-tree/Makefile | 2 +-
tools/testing/radix-tree/linux/kernel.h | 1 +
tools/testing/radix-tree/main.c | 1 +
tools/testing/radix-tree/regression.h | 1 +
tools/testing/radix-tree/regression3.c | 86 +++++++++++++++++++++++++++++++++
6 files changed, 93 insertions(+), 1 deletion(-)
create mode 100644 tools/testing/radix-tree/regression3.c
--
2.7.0.rc3
^ permalink raw reply [flat|nested] 4+ messages in thread
* [PATCH 1/2] radix-tree tests: Add regression3 test
2016-02-05 3:40 [PATCH 0/2] Radix tree retry bug fix & test case Matthew Wilcox
@ 2016-02-05 3:40 ` Matthew Wilcox
2016-02-05 3:40 ` [PATCH 2/2] radix-tree: fix oops after radix_tree_iter_retry Matthew Wilcox
2016-02-05 4:56 ` [PATCH 0/2] Radix tree retry bug fix & test case Konstantin Khlebnikov
2 siblings, 0 replies; 4+ messages in thread
From: Matthew Wilcox @ 2016-02-05 3:40 UTC (permalink / raw)
To: Konstantin Khlebnikov, Andrew Morton
Cc: Hugh Dickins, linux-kernel, linux-fsdevel, linux-mm,
Matthew Wilcox
From: Konstantin Khlebnikov <koct9i@gmail.com>
After calling radix_tree_iter_retry(), 'slot' will be set to NULL.
This can cause radix_tree_next_slot() to dereference the NULL pointer.
Add Konstantin Khlebnikov's test to the regression framework.
Reported-by: Konstantin Khlebnikov <koct9i@gmail.com>
Signed-off-by: Matthew Wilcox <matthew.r.wilcox@intel.com>
---
tools/testing/radix-tree/Makefile | 2 +-
tools/testing/radix-tree/linux/kernel.h | 1 +
tools/testing/radix-tree/main.c | 1 +
tools/testing/radix-tree/regression.h | 1 +
tools/testing/radix-tree/regression3.c | 86 +++++++++++++++++++++++++++++++++
5 files changed, 90 insertions(+), 1 deletion(-)
create mode 100644 tools/testing/radix-tree/regression3.c
diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile
index 582c8c6..3698a1a 100644
--- a/tools/testing/radix-tree/Makefile
+++ b/tools/testing/radix-tree/Makefile
@@ -3,7 +3,7 @@ CFLAGS += -I. -g -Wall -D_LGPL_SOURCE
LDFLAGS += -lpthread -lurcu
TARGETS = main
OFILES = main.o radix-tree.o linux.o test.o tag_check.o find_next_bit.o \
- regression1.o regression2.o
+ regression1.o regression2.o regression3.o
targets: $(TARGETS)
diff --git a/tools/testing/radix-tree/linux/kernel.h b/tools/testing/radix-tree/linux/kernel.h
index 27d5fe4..ae013b0 100644
--- a/tools/testing/radix-tree/linux/kernel.h
+++ b/tools/testing/radix-tree/linux/kernel.h
@@ -13,6 +13,7 @@
#define BUG_ON(expr) assert(!(expr))
#define __init
+#define __must_check
#define panic(expr)
#define printk printf
#define __force
diff --git a/tools/testing/radix-tree/main.c b/tools/testing/radix-tree/main.c
index 6b8a412..0e83cad 100644
--- a/tools/testing/radix-tree/main.c
+++ b/tools/testing/radix-tree/main.c
@@ -261,6 +261,7 @@ int main(void)
regression1_test();
regression2_test();
+ regression3_test();
single_thread_tests();
sleep(1);
diff --git a/tools/testing/radix-tree/regression.h b/tools/testing/radix-tree/regression.h
index bb1c2ab..e018c48 100644
--- a/tools/testing/radix-tree/regression.h
+++ b/tools/testing/radix-tree/regression.h
@@ -3,5 +3,6 @@
void regression1_test(void);
void regression2_test(void);
+void regression3_test(void);
#endif
diff --git a/tools/testing/radix-tree/regression3.c b/tools/testing/radix-tree/regression3.c
new file mode 100644
index 0000000..17d3ba5
--- /dev/null
+++ b/tools/testing/radix-tree/regression3.c
@@ -0,0 +1,86 @@
+/*
+ * Regression3
+ * Description:
+ * Helper radix_tree_iter_retry resets next_index to the current index.
+ * In following radix_tree_next_slot current chunk size becomes zero.
+ * This isn't checked and it tries to dereference null pointer in slot.
+ *
+ * Running:
+ * This test should run to completion immediately. The above bug would
+ * cause it to segfault.
+ *
+ * Upstream commit:
+ * Not yet
+ */
+#include <linux/kernel.h>
+#include <linux/gfp.h>
+#include <linux/slab.h>
+#include <linux/radix-tree.h>
+#include <stdlib.h>
+#include <stdio.h>
+
+#include "regression.h"
+
+void regression3_test(void)
+{
+ RADIX_TREE(root, GFP_KERNEL);
+ void *ptr = (void *)4ul;
+ struct radix_tree_iter iter;
+ void **slot;
+ bool first;
+
+ printf("running regression test 3 (should take milliseconds)\n");
+
+ radix_tree_insert(&root, 0, ptr);
+ radix_tree_tag_set(&root, 0, 0);
+
+ first = true;
+ radix_tree_for_each_tagged(slot, &root, &iter, 0, 0) {
+// printk("tagged %ld %p\n", iter.index, *slot);
+ if (first) {
+ radix_tree_insert(&root, 1, ptr);
+ radix_tree_tag_set(&root, 1, 0);
+ first = false;
+ }
+ if (radix_tree_deref_retry(*slot)) {
+// printk("retry %ld\n", iter.index);
+ slot = radix_tree_iter_retry(&iter);
+ continue;
+ }
+ }
+ radix_tree_delete(&root, 1);
+
+ first = true;
+ radix_tree_for_each_slot(slot, &root, &iter, 0) {
+// printk("slot %ld %p\n", iter.index, *slot);
+ if (first) {
+ radix_tree_insert(&root, 1, ptr);
+ first = false;
+ }
+ if (radix_tree_deref_retry(*slot)) {
+// printk("retry %ld\n", iter.index);
+ slot = radix_tree_iter_retry(&iter);
+ continue;
+ }
+ }
+ radix_tree_delete(&root, 1);
+
+ first = true;
+ radix_tree_for_each_contig(slot, &root, &iter, 0) {
+// printk("contig %ld %p\n", iter.index, *slot);
+ if (first) {
+ radix_tree_insert(&root, 1, ptr);
+ first = false;
+ }
+ if (radix_tree_deref_retry(*slot)) {
+// printk("retry %ld\n", iter.index);
+ slot = radix_tree_iter_retry(&iter);
+ continue;
+ }
+ }
+
+ radix_tree_delete(&root, 0);
+ radix_tree_delete(&root, 1);
+
+ printf("regression test 3 passed\n");
+}
--
2.7.0.rc3
^ permalink raw reply related [flat|nested] 4+ messages in thread
* [PATCH 2/2] radix-tree: fix oops after radix_tree_iter_retry
2016-02-05 3:40 [PATCH 0/2] Radix tree retry bug fix & test case Matthew Wilcox
2016-02-05 3:40 ` [PATCH 1/2] radix-tree tests: Add regression3 test Matthew Wilcox
@ 2016-02-05 3:40 ` Matthew Wilcox
2016-02-05 4:56 ` [PATCH 0/2] Radix tree retry bug fix & test case Konstantin Khlebnikov
2 siblings, 0 replies; 4+ messages in thread
From: Matthew Wilcox @ 2016-02-05 3:40 UTC (permalink / raw)
To: Konstantin Khlebnikov, Andrew Morton
Cc: Matthew Wilcox, Hugh Dickins, linux-kernel, linux-fsdevel,
linux-mm
After calling radix_tree_iter_retry(), 'slot' will be set to NULL.
This can cause radix_tree_next_slot() to dereference the NULL pointer.
Check for a NULL pointer on entry to radix_tree_next_slot().
Reported-by: Konstantin Khlebnikov <koct9i@gmail.com>
Signed-off-by: Matthew Wilcox <matthew.r.wilcox@intel.com>
---
include/linux/radix-tree.h | 3 +++
1 file changed, 3 insertions(+)
diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
index 3e488e2..9aa3afe 100644
--- a/include/linux/radix-tree.h
+++ b/include/linux/radix-tree.h
@@ -447,6 +447,9 @@ radix_tree_chunk_size(struct radix_tree_iter *iter)
static __always_inline void **
radix_tree_next_slot(void **slot, struct radix_tree_iter *iter, unsigned flags)
{
+ if (!slot)
+ return NULL;
+
if (flags & RADIX_TREE_ITER_TAGGED) {
iter->tags >>= 1;
if (likely(iter->tags & 1ul)) {
--
2.7.0.rc3
^ permalink raw reply related [flat|nested] 4+ messages in thread
* Re: [PATCH 0/2] Radix tree retry bug fix & test case
2016-02-05 3:40 [PATCH 0/2] Radix tree retry bug fix & test case Matthew Wilcox
2016-02-05 3:40 ` [PATCH 1/2] radix-tree tests: Add regression3 test Matthew Wilcox
2016-02-05 3:40 ` [PATCH 2/2] radix-tree: fix oops after radix_tree_iter_retry Matthew Wilcox
@ 2016-02-05 4:56 ` Konstantin Khlebnikov
2 siblings, 0 replies; 4+ messages in thread
From: Konstantin Khlebnikov @ 2016-02-05 4:56 UTC (permalink / raw)
To: Matthew Wilcox
Cc: Andrew Morton, Hugh Dickins, Linux Kernel Mailing List,
linux-fsdevel, linux-mm@kvack.org
On Fri, Feb 5, 2016 at 6:40 AM, Matthew Wilcox
<matthew.r.wilcox@intel.com> wrote:
> Konstantin pointed out my braino when using radix_tree_iter_retry(),
> and then pointed out a second braino. I think we can fix both brainos
> with one simple test (the advantage of having your braino pointed out
> to you is that you know what you were expecting to happen, so you can
> sometimes propose simlpy making happen what you expected to happen.
> Konstantin doesn't have access to my though tprocesses.)
>
> Kontantin wrote a really great test ... and then didn't add it to the
> test suite. That made me sad, so I added it.
I haven't seen them, I wasn't in CC. And I prefer testing in vivo if possible.
>
> Andrew, can you drop radix-tree-fix-oops-after-radix_tree_iter_retry.patch
> from your tree and add these two patches instead? If you prefer
> Konstantin's fix to this one, I'll send you another patch to fix the
> second problem Konstantin pointed out.
Nak. Mine version generates better code. radix_tree_next_slot is a hot place.
Please fix second problem in your helper separately.
>
> I was a bit unsure about the proper attribution here. The essentials
> of the test-suite change from Konstantin are unchanged, but he didn't
> have his own sign-off on it. So I made him 'From' and only added my
> own sign-off.
>
> Konstantin Khlebnikov (1):
> radix-tree tests: Add regression3 test
>
> Matthew Wilcox (1):
> radix-tree: fix oops after radix_tree_iter_retry
>
> include/linux/radix-tree.h | 3 ++
> tools/testing/radix-tree/Makefile | 2 +-
> tools/testing/radix-tree/linux/kernel.h | 1 +
> tools/testing/radix-tree/main.c | 1 +
> tools/testing/radix-tree/regression.h | 1 +
> tools/testing/radix-tree/regression3.c | 86 +++++++++++++++++++++++++++++++++
> 6 files changed, 93 insertions(+), 1 deletion(-)
> create mode 100644 tools/testing/radix-tree/regression3.c
>
> --
> 2.7.0.rc3
>
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~2016-02-05 4:56 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2016-02-05 3:40 [PATCH 0/2] Radix tree retry bug fix & test case Matthew Wilcox
2016-02-05 3:40 ` [PATCH 1/2] radix-tree tests: Add regression3 test Matthew Wilcox
2016-02-05 3:40 ` [PATCH 2/2] radix-tree: fix oops after radix_tree_iter_retry Matthew Wilcox
2016-02-05 4:56 ` [PATCH 0/2] Radix tree retry bug fix & test case Konstantin Khlebnikov
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).