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
15void __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
38void 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
48void __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
68void 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
79void 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
89void 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
126void 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
156void 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
239static 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
284int 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