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