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 
73 	radix_tree_for_each_slot(slot, &root, &iter, 0) {
74 		printv(2, "slot %ld %p\n", iter.index, *slot);
75 		if (!iter.index) {
76 			printv(2, "next at %ld\n", iter.index);
77 			slot = radix_tree_iter_resume(slot, &iter);
78 		}
79 	}
80 
81 	radix_tree_tag_set(&root, 0, 0);
82 	radix_tree_tag_set(&root, 1, 0);
83 	radix_tree_for_each_tagged(slot, &root, &iter, 0, 0) {
84 		printv(2, "tagged %ld %p\n", iter.index, *slot);
85 		if (!iter.index) {
86 			printv(2, "next at %ld\n", iter.index);
87 			slot = radix_tree_iter_resume(slot, &iter);
88 		}
89 	}
90 
91 	radix_tree_delete(&root, 0);
92 	radix_tree_delete(&root, 1);
93 
94 	printv(1, "regression test 3 passed\n");
95 }
96