xref: /linux/tools/testing/radix-tree/regression3.c (revision e5c86679d5e864947a52fb31e45a425dea3e7fa9)
1 /*
2  * Regression3
3  * Description:
4  * Helper radix_tree_iter_retry resets next_index to the current index.
5  * In following radix_tree_next_slot current chunk size becomes zero.
6  * This isn't checked and it tries to dereference null pointer in slot.
7  *
8  * Helper radix_tree_iter_resume reset slot to NULL and next_index to index + 1,
9  * for tagger iteraction it also must reset cached tags in iterator to abort
10  * next radix_tree_next_slot and go to slow-path into radix_tree_next_chunk.
11  *
12  * Running:
13  * This test should run to completion immediately. The above bug would
14  * cause it to segfault.
15  *
16  * Upstream commit:
17  * Not yet
18  */
19 #include <linux/kernel.h>
20 #include <linux/gfp.h>
21 #include <linux/slab.h>
22 #include <linux/radix-tree.h>
23 #include <stdlib.h>
24 #include <stdio.h>
25 
26 #include "regression.h"
27 
28 void regression3_test(void)
29 {
30 	RADIX_TREE(root, GFP_KERNEL);
31 	void *ptr0 = (void *)4ul;
32 	void *ptr = (void *)8ul;
33 	struct radix_tree_iter iter;
34 	void **slot;
35 	bool first;
36 
37 	printv(1, "running regression test 3 (should take milliseconds)\n");
38 
39 	radix_tree_insert(&root, 0, ptr0);
40 	radix_tree_tag_set(&root, 0, 0);
41 
42 	first = true;
43 	radix_tree_for_each_tagged(slot, &root, &iter, 0, 0) {
44 		printv(2, "tagged %ld %p\n", iter.index, *slot);
45 		if (first) {
46 			radix_tree_insert(&root, 1, ptr);
47 			radix_tree_tag_set(&root, 1, 0);
48 			first = false;
49 		}
50 		if (radix_tree_deref_retry(*slot)) {
51 			printv(2, "retry at %ld\n", iter.index);
52 			slot = radix_tree_iter_retry(&iter);
53 			continue;
54 		}
55 	}
56 	radix_tree_delete(&root, 1);
57 
58 	first = true;
59 	radix_tree_for_each_slot(slot, &root, &iter, 0) {
60 		printv(2, "slot %ld %p\n", iter.index, *slot);
61 		if (first) {
62 			radix_tree_insert(&root, 1, ptr);
63 			first = false;
64 		}
65 		if (radix_tree_deref_retry(*slot)) {
66 			printv(2, "retry at %ld\n", iter.index);
67 			slot = radix_tree_iter_retry(&iter);
68 			continue;
69 		}
70 	}
71 	radix_tree_delete(&root, 1);
72 
73 	first = true;
74 	radix_tree_for_each_contig(slot, &root, &iter, 0) {
75 		printv(2, "contig %ld %p\n", iter.index, *slot);
76 		if (first) {
77 			radix_tree_insert(&root, 1, ptr);
78 			first = false;
79 		}
80 		if (radix_tree_deref_retry(*slot)) {
81 			printv(2, "retry at %ld\n", iter.index);
82 			slot = radix_tree_iter_retry(&iter);
83 			continue;
84 		}
85 	}
86 
87 	radix_tree_for_each_slot(slot, &root, &iter, 0) {
88 		printv(2, "slot %ld %p\n", iter.index, *slot);
89 		if (!iter.index) {
90 			printv(2, "next at %ld\n", iter.index);
91 			slot = radix_tree_iter_resume(slot, &iter);
92 		}
93 	}
94 
95 	radix_tree_for_each_contig(slot, &root, &iter, 0) {
96 		printv(2, "contig %ld %p\n", iter.index, *slot);
97 		if (!iter.index) {
98 			printv(2, "next at %ld\n", iter.index);
99 			slot = radix_tree_iter_resume(slot, &iter);
100 		}
101 	}
102 
103 	radix_tree_tag_set(&root, 0, 0);
104 	radix_tree_tag_set(&root, 1, 0);
105 	radix_tree_for_each_tagged(slot, &root, &iter, 0, 0) {
106 		printv(2, "tagged %ld %p\n", iter.index, *slot);
107 		if (!iter.index) {
108 			printv(2, "next at %ld\n", iter.index);
109 			slot = radix_tree_iter_resume(slot, &iter);
110 		}
111 	}
112 
113 	radix_tree_delete(&root, 0);
114 	radix_tree_delete(&root, 1);
115 
116 	printv(1, "regression test 3 passed\n");
117 }
118