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