From 2d6f45b802af7a15a0e455bcfad4009aa5e7b66b Mon Sep 17 00:00:00 2001 From: Konstantin Khlebnikov Date: Thu, 17 Mar 2016 14:22:08 -0700 Subject: radix-tree tests: add regression3 test 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. Signed-off-by: Matthew Wilcox Reported-by: Konstantin Khlebnikov Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- tools/testing/radix-tree/regression3.c | 86 ++++++++++++++++++++++++++++++++++ 1 file changed, 86 insertions(+) create mode 100644 tools/testing/radix-tree/regression3.c (limited to 'tools/testing/radix-tree/regression3.c') diff --git a/tools/testing/radix-tree/regression3.c b/tools/testing/radix-tree/regression3.c new file mode 100644 index 000000000000..17d3ba5f4a0a --- /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 +#include +#include +#include +#include +#include + +#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"); +} -- cgit v1.2.3 From 7475851f340f0c100773b554659bfea50026feda Mon Sep 17 00:00:00 2001 From: Konstantin Khlebnikov Date: Thu, 17 Mar 2016 14:22:11 -0700 Subject: radix-tree tests: add test for radix_tree_iter_next Without fix test crashes inside tagged iteration. Signed-off-by: Konstantin Khlebnikov Cc: Matthew Wilcox Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- tools/testing/radix-tree/regression3.c | 47 ++++++++++++++++++++++++++++------ 1 file changed, 39 insertions(+), 8 deletions(-) (limited to 'tools/testing/radix-tree/regression3.c') diff --git a/tools/testing/radix-tree/regression3.c b/tools/testing/radix-tree/regression3.c index 17d3ba5f4a0a..1f06ed73d0a8 100644 --- a/tools/testing/radix-tree/regression3.c +++ b/tools/testing/radix-tree/regression3.c @@ -5,6 +5,10 @@ * In following radix_tree_next_slot current chunk size becomes zero. * This isn't checked and it tries to dereference null pointer in slot. * + * Helper radix_tree_iter_next reset slot to NULL and next_index to index + 1, + * for tagger iteraction it also must reset cached tags in iterator to abort + * next radix_tree_next_slot and go to slow-path into radix_tree_next_chunk. + * * Running: * This test should run to completion immediately. The above bug would * cause it to segfault. @@ -24,26 +28,27 @@ void regression3_test(void) { RADIX_TREE(root, GFP_KERNEL); - void *ptr = (void *)4ul; + void *ptr0 = (void *)4ul; + void *ptr = (void *)8ul; 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_insert(&root, 0, ptr0); 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); + printf("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); + printf("retry at %ld\n", iter.index); slot = radix_tree_iter_retry(&iter); continue; } @@ -52,13 +57,13 @@ void regression3_test(void) first = true; radix_tree_for_each_slot(slot, &root, &iter, 0) { -// printk("slot %ld %p\n", iter.index, *slot); + printf("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); + printk("retry at %ld\n", iter.index); slot = radix_tree_iter_retry(&iter); continue; } @@ -67,18 +72,44 @@ void regression3_test(void) first = true; radix_tree_for_each_contig(slot, &root, &iter, 0) { -// printk("contig %ld %p\n", iter.index, *slot); + 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); + printk("retry at %ld\n", iter.index); slot = radix_tree_iter_retry(&iter); continue; } } + radix_tree_for_each_slot(slot, &root, &iter, 0) { + printf("slot %ld %p\n", iter.index, *slot); + if (!iter.index) { + printf("next at %ld\n", iter.index); + slot = radix_tree_iter_next(&iter); + } + } + + radix_tree_for_each_contig(slot, &root, &iter, 0) { + printf("contig %ld %p\n", iter.index, *slot); + if (!iter.index) { + printf("next at %ld\n", iter.index); + slot = radix_tree_iter_next(&iter); + } + } + + radix_tree_tag_set(&root, 0, 0); + radix_tree_tag_set(&root, 1, 0); + radix_tree_for_each_tagged(slot, &root, &iter, 0, 0) { + printf("tagged %ld %p\n", iter.index, *slot); + if (!iter.index) { + printf("next at %ld\n", iter.index); + slot = radix_tree_iter_next(&iter); + } + } + radix_tree_delete(&root, 0); radix_tree_delete(&root, 1); -- cgit v1.2.3