xref: /openbmc/linux/tools/testing/radix-tree/main.c (revision 7e934cf5)
1 // SPDX-License-Identifier: GPL-2.0
2 #include <stdio.h>
3 #include <stdlib.h>
4 #include <unistd.h>
5 #include <time.h>
6 #include <assert.h>
7 #include <limits.h>
8 
9 #include <linux/slab.h>
10 #include <linux/radix-tree.h>
11 
12 #include "test.h"
13 #include "regression.h"
14 
__gang_check(unsigned long middle,long down,long up,int chunk,int hop)15 void __gang_check(unsigned long middle, long down, long up, int chunk, int hop)
16 {
17 	long idx;
18 	RADIX_TREE(tree, GFP_KERNEL);
19 
20 	middle = 1 << 30;
21 
22 	for (idx = -down; idx < up; idx++)
23 		item_insert(&tree, middle + idx);
24 
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);
29 
30 	if (chunk > 0) {
31 		item_gang_check_present(&tree, middle - down, up + down,
32 				chunk, hop);
33 		item_full_scan(&tree, middle - down, down + up, chunk);
34 	}
35 	item_kill_tree(&tree);
36 }
37 
gang_check(void)38 void gang_check(void)
39 {
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);
46 }
47 
__big_gang_check(void)48 void __big_gang_check(void)
49 {
50 	unsigned long start;
51 	int wrapped = 0;
52 
53 	start = 0;
54 	do {
55 		unsigned long old_start;
56 
57 //		printf("0x%08lx\n", start);
58 		__gang_check(start, rand() % 113 + 1, rand() % 71,
59 				rand() % 157, rand() % 91 + 1);
60 		old_start = start;
61 		start += rand() % 1000000;
62 		start %= 1ULL << 33;
63 		if (start < old_start)
64 			wrapped = 1;
65 	} while (!wrapped);
66 }
67 
big_gang_check(bool long_run)68 void big_gang_check(bool long_run)
69 {
70 	int i;
71 
72 	for (i = 0; i < (long_run ? 1000 : 3); i++) {
73 		__big_gang_check();
74 		printv(2, "%d ", i);
75 		fflush(stdout);
76 	}
77 }
78 
add_and_check(void)79 void add_and_check(void)
80 {
81 	RADIX_TREE(tree, GFP_KERNEL);
82 
83 	item_insert(&tree, 44);
84 	item_check_present(&tree, 44);
85 	item_check_absent(&tree, 43);
86 	item_kill_tree(&tree);
87 }
88 
dynamic_height_check(void)89 void dynamic_height_check(void)
90 {
91 	int i;
92 	RADIX_TREE(tree, GFP_KERNEL);
93 	tree_verify_min_height(&tree, 0);
94 
95 	item_insert(&tree, 42);
96 	tree_verify_min_height(&tree, 42);
97 
98 	item_insert(&tree, 1000000);
99 	tree_verify_min_height(&tree, 1000000);
100 
101 	assert(item_delete(&tree, 1000000));
102 	tree_verify_min_height(&tree, 42);
103 
104 	assert(item_delete(&tree, 42));
105 	tree_verify_min_height(&tree, 0);
106 
107 	for (i = 0; i < 1000; i++) {
108 		item_insert(&tree, i);
109 		tree_verify_min_height(&tree, i);
110 	}
111 
112 	i--;
113 	for (;;) {
114 		assert(item_delete(&tree, i));
115 		if (i == 0) {
116 			tree_verify_min_height(&tree, 0);
117 			break;
118 		}
119 		i--;
120 		tree_verify_min_height(&tree, i);
121 	}
122 
123 	item_kill_tree(&tree);
124 }
125 
check_copied_tags(struct radix_tree_root * tree,unsigned long start,unsigned long end,unsigned long * idx,int count,int fromtag,int totag)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)
127 {
128 	int i;
129 
130 	for (i = 0; i < count; i++) {
131 /*		if (i % 1000 == 0)
132 			putchar('.'); */
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],
137 								 fromtag),
138 				       item_tag_get(tree, idx[i], totag));
139 			}
140 			assert(!item_tag_get(tree, idx[i], totag));
141 			continue;
142 		}
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));
148 		}
149 		assert(!(item_tag_get(tree, idx[i], fromtag) ^
150 			 item_tag_get(tree, idx[i], totag)));
151 	}
152 }
153 
154 #define ITEMS 50000
155 
copy_tag_check(void)156 void copy_tag_check(void)
157 {
158 	RADIX_TREE(tree, GFP_KERNEL);
159 	unsigned long idx[ITEMS];
160 	unsigned long start, end, count = 0, tagged, cur, tmp;
161 	int i;
162 
163 //	printf("generating radix tree indices...\n");
164 	start = rand();
165 	end = rand();
166 	if (start > end && (rand() % 10)) {
167 		cur = start;
168 		start = end;
169 		end = cur;
170 	}
171 	/* Specifically create items around the start and the end of the range
172 	 * with high probability to check for off by one errors */
173 	cur = rand();
174 	if (cur & 1) {
175 		item_insert(&tree, start);
176 		if (cur & 2) {
177 			if (start <= end)
178 				count++;
179 			item_tag_set(&tree, start, 0);
180 		}
181 	}
182 	if (cur & 4) {
183 		item_insert(&tree, start-1);
184 		if (cur & 8)
185 			item_tag_set(&tree, start-1, 0);
186 	}
187 	if (cur & 16) {
188 		item_insert(&tree, end);
189 		if (cur & 32) {
190 			if (start <= end)
191 				count++;
192 			item_tag_set(&tree, end, 0);
193 		}
194 	}
195 	if (cur & 64) {
196 		item_insert(&tree, end+1);
197 		if (cur & 128)
198 			item_tag_set(&tree, end+1, 0);
199 	}
200 
201 	for (i = 0; i < ITEMS; i++) {
202 		do {
203 			idx[i] = rand();
204 		} while (item_lookup(&tree, idx[i]));
205 
206 		item_insert(&tree, idx[i]);
207 		if (rand() & 1) {
208 			item_tag_set(&tree, idx[i], 0);
209 			if (idx[i] >= start && idx[i] <= end)
210 				count++;
211 		}
212 /*		if (i % 1000 == 0)
213 			putchar('.'); */
214 	}
215 
216 //	printf("\ncopying tags...\n");
217 	tagged = tag_tagged_items(&tree, start, end, ITEMS, XA_MARK_0, XA_MARK_1);
218 
219 //	printf("checking copied tags\n");
220 	assert(tagged == count);
221 	check_copied_tags(&tree, start, end, idx, ITEMS, 0, 1);
222 
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);
228 
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);
235 //	printf("\n");
236 	item_kill_tree(&tree);
237 }
238 
single_thread_tests(bool long_run)239 static void single_thread_tests(bool long_run)
240 {
241 	int i;
242 
243 	printv(1, "starting single_thread_tests: %d allocated, preempt %d\n",
244 		nr_allocated, preempt_count);
245 	multiorder_checks();
246 	rcu_barrier();
247 	printv(2, "after multiorder_check: %d allocated, preempt %d\n",
248 		nr_allocated, preempt_count);
249 	tag_check();
250 	rcu_barrier();
251 	printv(2, "after tag_check: %d allocated, preempt %d\n",
252 		nr_allocated, preempt_count);
253 	gang_check();
254 	rcu_barrier();
255 	printv(2, "after gang_check: %d allocated, preempt %d\n",
256 		nr_allocated, preempt_count);
257 	add_and_check();
258 	rcu_barrier();
259 	printv(2, "after add_and_check: %d allocated, preempt %d\n",
260 		nr_allocated, preempt_count);
261 	dynamic_height_check();
262 	rcu_barrier();
263 	printv(2, "after dynamic_height_check: %d allocated, preempt %d\n",
264 		nr_allocated, preempt_count);
265 	idr_checks();
266 	ida_tests();
267 	rcu_barrier();
268 	printv(2, "after idr_checks: %d allocated, preempt %d\n",
269 		nr_allocated, preempt_count);
270 	big_gang_check(long_run);
271 	rcu_barrier();
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++) {
275 		copy_tag_check();
276 		printv(2, "%d ", i);
277 		fflush(stdout);
278 	}
279 	rcu_barrier();
280 	printv(2, "after copy_tag_check: %d allocated, preempt %d\n",
281 		nr_allocated, preempt_count);
282 }
283 
main(int argc,char ** argv)284 int main(int argc, char **argv)
285 {
286 	bool long_run = false;
287 	int opt;
288 	unsigned int seed = time(NULL);
289 
290 	while ((opt = getopt(argc, argv, "ls:v")) != -1) {
291 		if (opt == 'l')
292 			long_run = true;
293 		else if (opt == 's')
294 			seed = strtoul(optarg, NULL, 0);
295 		else if (opt == 'v')
296 			test_verbose++;
297 	}
298 
299 	printf("random seed %u\n", seed);
300 	srand(seed);
301 
302 	printf("running tests\n");
303 
304 	rcu_register_thread();
305 	radix_tree_init();
306 
307 	xarray_tests();
308 	regression1_test();
309 	regression2_test();
310 	regression3_test();
311 	regression4_test();
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);
316 
317 	/* Free any remaining preallocated nodes */
318 	radix_tree_cpu_dead(0);
319 
320 	benchmark();
321 
322 	rcu_barrier();
323 	printv(2, "after rcu_barrier: %d allocated, preempt %d\n",
324 		nr_allocated, preempt_count);
325 	rcu_unregister_thread();
326 
327 	printf("tests completed\n");
328 
329 	exit(0);
330 }
331