1 // SPDX-License-Identifier: GPL-2.0
9 #include <linux/slab.h>
10 #include <linux/radix-tree.h>
13 #include "regression.h"
15 void __gang_check(unsigned long middle, long down, long up, int chunk, int hop)
18 RADIX_TREE(tree, GFP_KERNEL);
22 for (idx = -down; idx < up; idx++)
23 item_insert(&tree, middle + idx);
25 item_check_absent(&tree, middle - down - 1);
26 for (idx = -down; idx < up; idx++)
27 item_check_present(&tree, middle + idx);
28 item_check_absent(&tree, middle + up);
31 item_gang_check_present(&tree, middle - down, up + down,
33 item_full_scan(&tree, middle - down, down + up, chunk);
35 item_kill_tree(&tree);
40 __gang_check(1UL << 30, 128, 128, 35, 2);
41 __gang_check(1UL << 31, 128, 128, 32, 32);
42 __gang_check(1UL << 31, 128, 128, 32, 100);
43 __gang_check(1UL << 31, 128, 128, 17, 7);
44 __gang_check(0xffff0000UL, 0, 65536, 17, 7);
45 __gang_check(0xfffffffeUL, 1, 1, 17, 7);
48 void __big_gang_check(void)
55 unsigned long old_start;
57 // printf("0x%08lx\n", start);
58 __gang_check(start, rand() % 113 + 1, rand() % 71,
59 rand() % 157, rand() % 91 + 1);
61 start += rand() % 1000000;
63 if (start < old_start)
68 void big_gang_check(bool long_run)
72 for (i = 0; i < (long_run ? 1000 : 3); i++) {
79 void add_and_check(void)
81 RADIX_TREE(tree, GFP_KERNEL);
83 item_insert(&tree, 44);
84 item_check_present(&tree, 44);
85 item_check_absent(&tree, 43);
86 item_kill_tree(&tree);
89 void dynamic_height_check(void)
92 RADIX_TREE(tree, GFP_KERNEL);
93 tree_verify_min_height(&tree, 0);
95 item_insert(&tree, 42);
96 tree_verify_min_height(&tree, 42);
98 item_insert(&tree, 1000000);
99 tree_verify_min_height(&tree, 1000000);
101 assert(item_delete(&tree, 1000000));
102 tree_verify_min_height(&tree, 42);
104 assert(item_delete(&tree, 42));
105 tree_verify_min_height(&tree, 0);
107 for (i = 0; i < 1000; i++) {
108 item_insert(&tree, i);
109 tree_verify_min_height(&tree, i);
114 assert(item_delete(&tree, i));
116 tree_verify_min_height(&tree, 0);
120 tree_verify_min_height(&tree, i);
123 item_kill_tree(&tree);
126 void check_copied_tags(struct radix_tree_root *tree, unsigned long start, unsigned long end, unsigned long *idx, int count, int fromtag, int totag)
130 for (i = 0; i < count; i++) {
131 /* if (i % 1000 == 0)
133 if (idx[i] < start || idx[i] > end) {
134 if (item_tag_get(tree, idx[i], totag)) {
135 printv(2, "%lu-%lu: %lu, tags %d-%d\n", start,
136 end, idx[i], item_tag_get(tree, idx[i],
138 item_tag_get(tree, idx[i], totag));
140 assert(!item_tag_get(tree, idx[i], totag));
143 if (item_tag_get(tree, idx[i], fromtag) ^
144 item_tag_get(tree, idx[i], totag)) {
145 printv(2, "%lu-%lu: %lu, tags %d-%d\n", start, end,
146 idx[i], item_tag_get(tree, idx[i], fromtag),
147 item_tag_get(tree, idx[i], totag));
149 assert(!(item_tag_get(tree, idx[i], fromtag) ^
150 item_tag_get(tree, idx[i], totag)));
156 void copy_tag_check(void)
158 RADIX_TREE(tree, GFP_KERNEL);
159 unsigned long idx[ITEMS];
160 unsigned long start, end, count = 0, tagged, cur, tmp;
163 // printf("generating radix tree indices...\n");
166 if (start > end && (rand() % 10)) {
171 /* Specifically create items around the start and the end of the range
172 * with high probability to check for off by one errors */
175 item_insert(&tree, start);
179 item_tag_set(&tree, start, 0);
183 item_insert(&tree, start-1);
185 item_tag_set(&tree, start-1, 0);
188 item_insert(&tree, end);
192 item_tag_set(&tree, end, 0);
196 item_insert(&tree, end+1);
198 item_tag_set(&tree, end+1, 0);
201 for (i = 0; i < ITEMS; i++) {
204 } while (item_lookup(&tree, idx[i]));
206 item_insert(&tree, idx[i]);
208 item_tag_set(&tree, idx[i], 0);
209 if (idx[i] >= start && idx[i] <= end)
212 /* if (i % 1000 == 0)
216 // printf("\ncopying tags...\n");
217 tagged = tag_tagged_items(&tree, start, end, ITEMS, XA_MARK_0, XA_MARK_1);
219 // printf("checking copied tags\n");
220 assert(tagged == count);
221 check_copied_tags(&tree, start, end, idx, ITEMS, 0, 1);
223 /* Copy tags in several rounds */
224 // printf("\ncopying tags...\n");
225 tmp = rand() % (count / 10 + 2);
226 tagged = tag_tagged_items(&tree, start, end, tmp, XA_MARK_0, XA_MARK_2);
227 assert(tagged == count);
229 // printf("%lu %lu %lu\n", tagged, tmp, count);
230 // printf("checking copied tags\n");
231 check_copied_tags(&tree, start, end, idx, ITEMS, 0, 2);
232 verify_tag_consistency(&tree, 0);
233 verify_tag_consistency(&tree, 1);
234 verify_tag_consistency(&tree, 2);
236 item_kill_tree(&tree);
239 static void single_thread_tests(bool long_run)
243 printv(1, "starting single_thread_tests: %d allocated, preempt %d\n",
244 nr_allocated, preempt_count);
247 printv(2, "after multiorder_check: %d allocated, preempt %d\n",
248 nr_allocated, preempt_count);
251 printv(2, "after tag_check: %d allocated, preempt %d\n",
252 nr_allocated, preempt_count);
255 printv(2, "after gang_check: %d allocated, preempt %d\n",
256 nr_allocated, preempt_count);
259 printv(2, "after add_and_check: %d allocated, preempt %d\n",
260 nr_allocated, preempt_count);
261 dynamic_height_check();
263 printv(2, "after dynamic_height_check: %d allocated, preempt %d\n",
264 nr_allocated, preempt_count);
268 printv(2, "after idr_checks: %d allocated, preempt %d\n",
269 nr_allocated, preempt_count);
270 big_gang_check(long_run);
272 printv(2, "after big_gang_check: %d allocated, preempt %d\n",
273 nr_allocated, preempt_count);
274 for (i = 0; i < (long_run ? 2000 : 3); i++) {
280 printv(2, "after copy_tag_check: %d allocated, preempt %d\n",
281 nr_allocated, preempt_count);
284 int main(int argc, char **argv)
286 bool long_run = false;
288 unsigned int seed = time(NULL);
290 while ((opt = getopt(argc, argv, "ls:v")) != -1) {
294 seed = strtoul(optarg, NULL, 0);
299 printf("random seed %u\n", seed);
302 printf("running tests\n");
304 rcu_register_thread();
312 iteration_test(0, 10 + 90 * long_run);
313 iteration_test(7, 10 + 90 * long_run);
314 iteration_test2(10 + 90 * long_run);
315 single_thread_tests(long_run);
317 /* Free any remaining preallocated nodes */
318 radix_tree_cpu_dead(0);
323 printv(2, "after rcu_barrier: %d allocated, preempt %d\n",
324 nr_allocated, preempt_count);
325 rcu_unregister_thread();
327 printf("tests completed\n");