main.c 7.39 KB
Newer Older
1
// SPDX-License-Identifier: GPL-2.0
Matthew Wilcox's avatar
Matthew Wilcox committed
2 3 4 5 6
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>
#include <assert.h>
7
#include <limits.h>
Matthew Wilcox's avatar
Matthew Wilcox committed
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

#include <linux/slab.h>
#include <linux/radix-tree.h>

#include "test.h"
#include "regression.h"

void __gang_check(unsigned long middle, long down, long up, int chunk, int hop)
{
	long idx;
	RADIX_TREE(tree, GFP_KERNEL);

	middle = 1 << 30;

	for (idx = -down; idx < up; idx++)
		item_insert(&tree, middle + idx);

	item_check_absent(&tree, middle - down - 1);
	for (idx = -down; idx < up; idx++)
		item_check_present(&tree, middle + idx);
	item_check_absent(&tree, middle + up);

30 31 32 33 34
	if (chunk > 0) {
		item_gang_check_present(&tree, middle - down, up + down,
				chunk, hop);
		item_full_scan(&tree, middle - down, down + up, chunk);
	}
Matthew Wilcox's avatar
Matthew Wilcox committed
35 36 37 38 39
	item_kill_tree(&tree);
}

void gang_check(void)
{
40 41 42 43 44 45
	__gang_check(1UL << 30, 128, 128, 35, 2);
	__gang_check(1UL << 31, 128, 128, 32, 32);
	__gang_check(1UL << 31, 128, 128, 32, 100);
	__gang_check(1UL << 31, 128, 128, 17, 7);
	__gang_check(0xffff0000UL, 0, 65536, 17, 7);
	__gang_check(0xfffffffeUL, 1, 1, 17, 7);
Matthew Wilcox's avatar
Matthew Wilcox committed
46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
}

void __big_gang_check(void)
{
	unsigned long start;
	int wrapped = 0;

	start = 0;
	do {
		unsigned long old_start;

//		printf("0x%08lx\n", start);
		__gang_check(start, rand() % 113 + 1, rand() % 71,
				rand() % 157, rand() % 91 + 1);
		old_start = start;
		start += rand() % 1000000;
		start %= 1ULL << 33;
		if (start < old_start)
			wrapped = 1;
	} while (!wrapped);
}

68
void big_gang_check(bool long_run)
Matthew Wilcox's avatar
Matthew Wilcox committed
69 70 71
{
	int i;

72
	for (i = 0; i < (long_run ? 1000 : 3); i++) {
Matthew Wilcox's avatar
Matthew Wilcox committed
73
		__big_gang_check();
74
		printv(2, "%d ", i);
Matthew Wilcox's avatar
Matthew Wilcox committed
75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134
		fflush(stdout);
	}
}

void add_and_check(void)
{
	RADIX_TREE(tree, GFP_KERNEL);

	item_insert(&tree, 44);
	item_check_present(&tree, 44);
	item_check_absent(&tree, 43);
	item_kill_tree(&tree);
}

void dynamic_height_check(void)
{
	int i;
	RADIX_TREE(tree, GFP_KERNEL);
	tree_verify_min_height(&tree, 0);

	item_insert(&tree, 42);
	tree_verify_min_height(&tree, 42);

	item_insert(&tree, 1000000);
	tree_verify_min_height(&tree, 1000000);

	assert(item_delete(&tree, 1000000));
	tree_verify_min_height(&tree, 42);

	assert(item_delete(&tree, 42));
	tree_verify_min_height(&tree, 0);

	for (i = 0; i < 1000; i++) {
		item_insert(&tree, i);
		tree_verify_min_height(&tree, i);
	}

	i--;
	for (;;) {
		assert(item_delete(&tree, i));
		if (i == 0) {
			tree_verify_min_height(&tree, 0);
			break;
		}
		i--;
		tree_verify_min_height(&tree, i);
	}

	item_kill_tree(&tree);
}

void check_copied_tags(struct radix_tree_root *tree, unsigned long start, unsigned long end, unsigned long *idx, int count, int fromtag, int totag)
{
	int i;

	for (i = 0; i < count; i++) {
/*		if (i % 1000 == 0)
			putchar('.'); */
		if (idx[i] < start || idx[i] > end) {
			if (item_tag_get(tree, idx[i], totag)) {
135 136 137 138
				printv(2, "%lu-%lu: %lu, tags %d-%d\n", start,
				       end, idx[i], item_tag_get(tree, idx[i],
								 fromtag),
				       item_tag_get(tree, idx[i], totag));
Matthew Wilcox's avatar
Matthew Wilcox committed
139 140 141 142 143 144
			}
			assert(!item_tag_get(tree, idx[i], totag));
			continue;
		}
		if (item_tag_get(tree, idx[i], fromtag) ^
			item_tag_get(tree, idx[i], totag)) {
145 146 147
			printv(2, "%lu-%lu: %lu, tags %d-%d\n", start, end,
			       idx[i], item_tag_get(tree, idx[i], fromtag),
			       item_tag_get(tree, idx[i], totag));
Matthew Wilcox's avatar
Matthew Wilcox committed
148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216
		}
		assert(!(item_tag_get(tree, idx[i], fromtag) ^
			 item_tag_get(tree, idx[i], totag)));
	}
}

#define ITEMS 50000

void copy_tag_check(void)
{
	RADIX_TREE(tree, GFP_KERNEL);
	unsigned long idx[ITEMS];
	unsigned long start, end, count = 0, tagged, cur, tmp;
	int i;

//	printf("generating radix tree indices...\n");
	start = rand();
	end = rand();
	if (start > end && (rand() % 10)) {
		cur = start;
		start = end;
		end = cur;
	}
	/* Specifically create items around the start and the end of the range
	 * with high probability to check for off by one errors */
	cur = rand();
	if (cur & 1) {
		item_insert(&tree, start);
		if (cur & 2) {
			if (start <= end)
				count++;
			item_tag_set(&tree, start, 0);
		}
	}
	if (cur & 4) {
		item_insert(&tree, start-1);
		if (cur & 8)
			item_tag_set(&tree, start-1, 0);
	}
	if (cur & 16) {
		item_insert(&tree, end);
		if (cur & 32) {
			if (start <= end)
				count++;
			item_tag_set(&tree, end, 0);
		}
	}
	if (cur & 64) {
		item_insert(&tree, end+1);
		if (cur & 128)
			item_tag_set(&tree, end+1, 0);
	}

	for (i = 0; i < ITEMS; i++) {
		do {
			idx[i] = rand();
		} while (item_lookup(&tree, idx[i]));

		item_insert(&tree, idx[i]);
		if (rand() & 1) {
			item_tag_set(&tree, idx[i], 0);
			if (idx[i] >= start && idx[i] <= end)
				count++;
		}
/*		if (i % 1000 == 0)
			putchar('.'); */
	}

//	printf("\ncopying tags...\n");
217
	tagged = tag_tagged_items(&tree, start, end, ITEMS, XA_MARK_0, XA_MARK_1);
Matthew Wilcox's avatar
Matthew Wilcox committed
218 219 220 221 222 223 224

//	printf("checking copied tags\n");
	assert(tagged == count);
	check_copied_tags(&tree, start, end, idx, ITEMS, 0, 1);

	/* Copy tags in several rounds */
//	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);
Matthew Wilcox's avatar
Matthew Wilcox committed
228 229 230 231 232 233 234 235 236 237 238

//	printf("%lu %lu %lu\n", tagged, tmp, count);
//	printf("checking copied tags\n");
	check_copied_tags(&tree, start, end, idx, ITEMS, 0, 2);
	verify_tag_consistency(&tree, 0);
	verify_tag_consistency(&tree, 1);
	verify_tag_consistency(&tree, 2);
//	printf("\n");
	item_kill_tree(&tree);
}

239
static void single_thread_tests(bool long_run)
Matthew Wilcox's avatar
Matthew Wilcox committed
240 241 242
{
	int i;

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);
Matthew Wilcox's avatar
Matthew Wilcox committed
249
	tag_check();
250
	rcu_barrier();
251
	printv(2, "after tag_check: %d allocated, preempt %d\n",
252
		nr_allocated, preempt_count);
Matthew Wilcox's avatar
Matthew Wilcox committed
253
	gang_check();
254
	rcu_barrier();
255
	printv(2, "after gang_check: %d allocated, preempt %d\n",
256
		nr_allocated, preempt_count);
Matthew Wilcox's avatar
Matthew Wilcox committed
257
	add_and_check();
258
	rcu_barrier();
259
	printv(2, "after add_and_check: %d allocated, preempt %d\n",
260
		nr_allocated, preempt_count);
Matthew Wilcox's avatar
Matthew Wilcox committed
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++) {
Matthew Wilcox's avatar
Matthew Wilcox committed
275
		copy_tag_check();
276
		printv(2, "%d ", i);
Matthew Wilcox's avatar
Matthew Wilcox committed
277 278
		fflush(stdout);
	}
279
	rcu_barrier();
280
	printv(2, "after copy_tag_check: %d allocated, preempt %d\n",
281
		nr_allocated, preempt_count);
Matthew Wilcox's avatar
Matthew Wilcox committed
282 283
}

284
int main(int argc, char **argv)
Matthew Wilcox's avatar
Matthew Wilcox committed
285
{
286 287
	bool long_run = false;
	int opt;
288
	unsigned int seed = time(NULL);
289

290
	while ((opt = getopt(argc, argv, "ls:v")) != -1) {
291 292
		if (opt == 'l')
			long_run = true;
293 294
		else if (opt == 's')
			seed = strtoul(optarg, NULL, 0);
295 296
		else if (opt == 'v')
			test_verbose++;
297 298
	}

299 300 301
	printf("random seed %u\n", seed);
	srand(seed);

302 303
	printf("running tests\n");

Matthew Wilcox's avatar
Matthew Wilcox committed
304 305 306
	rcu_register_thread();
	radix_tree_init();

307
	xarray_tests();
Matthew Wilcox's avatar
Matthew Wilcox committed
308 309
	regression1_test();
	regression2_test();
310
	regression3_test();
311
	regression4_test();
312 313
	iteration_test(0, 10 + 90 * long_run);
	iteration_test(7, 10 + 90 * long_run);
314
	single_thread_tests(long_run);
Matthew Wilcox's avatar
Matthew Wilcox committed
315

316 317 318
	/* Free any remaining preallocated nodes */
	radix_tree_cpu_dead(0);

319 320
	benchmark();

321
	rcu_barrier();
322
	printv(2, "after rcu_barrier: %d allocated, preempt %d\n",
323
		nr_allocated, preempt_count);
Matthew Wilcox's avatar
Matthew Wilcox committed
324 325
	rcu_unregister_thread();

326 327
	printf("tests completed\n");

Matthew Wilcox's avatar
Matthew Wilcox committed
328 329
	exit(0);
}