[deliverable/linux.git] / tools / testing / radix-tree / main.c

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <time.h>
#include <assert.h>

#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);

	item_gang_check_present(&tree, middle - down,
			up + down, chunk, hop);
	item_full_scan(&tree, middle - down, down + up, chunk);
	item_kill_tree(&tree);
}

void gang_check(void)
{
	__gang_check(1 << 30, 128, 128, 35, 2);
	__gang_check(1 << 31, 128, 128, 32, 32);
	__gang_check(1 << 31, 128, 128, 32, 100);
	__gang_check(1 << 31, 128, 128, 17, 7);
	__gang_check(0xffff0000, 0, 65536, 17, 7);
	__gang_check(0xfffffffe, 1, 1, 17, 7);
}

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);
}

void big_gang_check(bool long_run)
{
	int i;

	for (i = 0; i < (long_run ? 1000 : 3); i++) {
		__big_gang_check();
		srand(time(0));
		printf("%d ", i);
		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)) {
				printf("%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));
			}
			assert(!item_tag_get(tree, idx[i], totag));
			continue;
		}
		if (item_tag_get(tree, idx[i], fromtag) ^
			item_tag_get(tree, idx[i], totag)) {
			printf("%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));
		}
		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");
	cur = start;
	tagged = radix_tree_range_tag_if_tagged(&tree, &cur, end, ITEMS, 0, 1);

//	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");
	cur = start;
	do {
		tmp = rand() % (count/10+2);
		tagged = radix_tree_range_tag_if_tagged(&tree, &cur, end, tmp, 0, 2);
	} while (tmp == tagged);

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

static void __locate_check(struct radix_tree_root *tree, unsigned long index,
			unsigned order)
{
	struct item *item;
	unsigned long index2;

	item_insert_order(tree, index, order);
	item = item_lookup(tree, index);
	index2 = radix_tree_locate_item(tree, item);
	if (index != index2) {
		printf("index %ld order %d inserted; found %ld\n",
			index, order, index2);
		abort();
	}
}

static void __order_0_locate_check(void)
{
	RADIX_TREE(tree, GFP_KERNEL);
	int i;

	for (i = 0; i < 50; i++)
		__locate_check(&tree, rand() % INT_MAX, 0);

	item_kill_tree(&tree);
}

static void locate_check(void)
{
	RADIX_TREE(tree, GFP_KERNEL);
	unsigned order;
	unsigned long offset, index;

	__order_0_locate_check();

	for (order = 0; order < 20; order++) {
		for (offset = 0; offset < (1 << (order + 3));
		     offset += (1UL << order)) {
			for (index = 0; index < (1UL << (order + 5));
			     index += (1UL << order)) {
				__locate_check(&tree, index + offset, order);
			}
			if (radix_tree_locate_item(&tree, &tree) != -1)
				abort();

			item_kill_tree(&tree);
		}
	}

	if (radix_tree_locate_item(&tree, &tree) != -1)
		abort();
	__locate_check(&tree, -1, 0);
	if (radix_tree_locate_item(&tree, &tree) != -1)
		abort();
	item_kill_tree(&tree);
}

static void single_thread_tests(bool long_run)
{
	int i;

	printf("starting single_thread_tests: %d allocated\n", nr_allocated);
	multiorder_checks();
	printf("after multiorder_check: %d allocated\n", nr_allocated);
	locate_check();
	printf("after locate_check: %d allocated\n", nr_allocated);
	tag_check();
	printf("after tag_check: %d allocated\n", nr_allocated);
	gang_check();
	printf("after gang_check: %d allocated\n", nr_allocated);
	add_and_check();
	printf("after add_and_check: %d allocated\n", nr_allocated);
	dynamic_height_check();
	printf("after dynamic_height_check: %d allocated\n", nr_allocated);
	big_gang_check(long_run);
	printf("after big_gang_check: %d allocated\n", nr_allocated);
	for (i = 0; i < (long_run ? 2000 : 3); i++) {
		copy_tag_check();
		printf("%d ", i);
		fflush(stdout);
	}
	printf("after copy_tag_check: %d allocated\n", nr_allocated);
}

int main(int argc, char **argv)
{
	bool long_run = false;
	int opt;

	while ((opt = getopt(argc, argv, "l")) != -1) {
		if (opt == 'l')
			long_run = true;
	}

	rcu_register_thread();
	radix_tree_init();

	regression1_test();
	regression2_test();
	regression3_test();
	iteration_test();
	single_thread_tests(long_run);

	sleep(1);
	printf("after sleep(1): %d allocated\n", nr_allocated);
	rcu_unregister_thread();

	exit(0);
}
Commit	Line	Data
1366c37e MW	1	#include <stdio.h>
	2	#include <stdlib.h>
	3	#include <unistd.h>
	4	#include <time.h>
	5	#include <assert.h>
	6
	7	#include <linux/slab.h>
	8	#include <linux/radix-tree.h>
	9
	10	#include "test.h"
	11	#include "regression.h"
	12
	13	void __gang_check(unsigned long middle, long down, long up, int chunk, int hop)
	14	{
	15	long idx;
	16	RADIX_TREE(tree, GFP_KERNEL);
	17
	18	middle = 1 << 30;
	19
	20	for (idx = -down; idx < up; idx++)
	21	item_insert(&tree, middle + idx);
	22
	23	item_check_absent(&tree, middle - down - 1);
	24	for (idx = -down; idx < up; idx++)
	25	item_check_present(&tree, middle + idx);
	26	item_check_absent(&tree, middle + up);
	27
	28	item_gang_check_present(&tree, middle - down,
	29	up + down, chunk, hop);
	30	item_full_scan(&tree, middle - down, down + up, chunk);
	31	item_kill_tree(&tree);
	32	}
	33
	34	void gang_check(void)
	35	{
	36	__gang_check(1 << 30, 128, 128, 35, 2);
	37	__gang_check(1 << 31, 128, 128, 32, 32);
	38	__gang_check(1 << 31, 128, 128, 32, 100);
	39	__gang_check(1 << 31, 128, 128, 17, 7);
	40	__gang_check(0xffff0000, 0, 65536, 17, 7);
	41	__gang_check(0xfffffffe, 1, 1, 17, 7);
	42	}
	43
	44	void __big_gang_check(void)
	45	{
	46	unsigned long start;
	47	int wrapped = 0;
	48
	49	start = 0;
	50	do {
	51	unsigned long old_start;
	52
	53	// printf("0x%08lx\n", start);
	54	__gang_check(start, rand() % 113 + 1, rand() % 71,
	55	rand() % 157, rand() % 91 + 1);
	56	old_start = start;
	57	start += rand() % 1000000;
	58	start %= 1ULL << 33;
	59	if (start < old_start)
	60	wrapped = 1;
	61	} while (!wrapped);
	62	}
	63
aa1d62d8	64	void big_gang_check(bool long_run)
1366c37e MW	65	{
	66	int i;
	67
aa1d62d8	68	for (i = 0; i < (long_run ? 1000 : 3); i++) {
1366c37e MW	69	__big_gang_check();
	70	srand(time(0));
	71	printf("%d ", i);
	72	fflush(stdout);
	73	}
	74	}
	75
	76	void add_and_check(void)
	77	{
	78	RADIX_TREE(tree, GFP_KERNEL);
	79
	80	item_insert(&tree, 44);
	81	item_check_present(&tree, 44);
	82	item_check_absent(&tree, 43);
	83	item_kill_tree(&tree);
	84	}
	85
	86	void dynamic_height_check(void)
	87	{
	88	int i;
	89	RADIX_TREE(tree, GFP_KERNEL);
	90	tree_verify_min_height(&tree, 0);
	91
	92	item_insert(&tree, 42);
	93	tree_verify_min_height(&tree, 42);
	94
	95	item_insert(&tree, 1000000);
	96	tree_verify_min_height(&tree, 1000000);
	97
	98	assert(item_delete(&tree, 1000000));
	99	tree_verify_min_height(&tree, 42);
	100
	101	assert(item_delete(&tree, 42));
	102	tree_verify_min_height(&tree, 0);
	103
	104	for (i = 0; i < 1000; i++) {
	105	item_insert(&tree, i);
	106	tree_verify_min_height(&tree, i);
	107	}
	108
	109	i--;
	110	for (;;) {
	111	assert(item_delete(&tree, i));
	112	if (i == 0) {
	113	tree_verify_min_height(&tree, 0);
	114	break;
	115	}
	116	i--;
	117	tree_verify_min_height(&tree, i);
	118	}
	119
	120	item_kill_tree(&tree);
	121	}
	122
	123	void check_copied_tags(struct radix_tree_root tree, unsigned long start, unsigned long end, unsigned long idx, int count, int fromtag, int totag)
	124	{
	125	int i;
	126
	127	for (i = 0; i < count; i++) {
	128	/* if (i % 1000 == 0)
	129	putchar('.'); */
	130	if (idx[i] < start \|\| idx[i] > end) {
	131	if (item_tag_get(tree, idx[i], totag)) {
	132	printf("%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));
133	}
134	assert(!item_tag_get(tree, idx[i], totag));
135	continue;
136	}
137	if (item_tag_get(tree, idx[i], fromtag) ^
138	item_tag_get(tree, idx[i], totag)) {
139	printf("%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));
140	}
141	assert(!(item_tag_get(tree, idx[i], fromtag) ^
142	item_tag_get(tree, idx[i], totag)));
143	}
144	}
145
146	#define ITEMS 50000
147
148	void copy_tag_check(void)
149	{
150	RADIX_TREE(tree, GFP_KERNEL);
151	unsigned long idx[ITEMS];
152	unsigned long start, end, count = 0, tagged, cur, tmp;
153	int i;
154
155	// printf("generating radix tree indices...\n");
156	start = rand();
157	end = rand();
158	if (start > end && (rand() % 10)) {
159	cur = start;
160	start = end;
161	end = cur;
162	}
163	/* Specifically create items around the start and the end of the range
164	* with high probability to check for off by one errors */
165	cur = rand();
166	if (cur & 1) {
167	item_insert(&tree, start);
168	if (cur & 2) {
169	if (start <= end)
170	count++;
171	item_tag_set(&tree, start, 0);
172	}
173	}
174	if (cur & 4) {
175	item_insert(&tree, start-1);
176	if (cur & 8)
177	item_tag_set(&tree, start-1, 0);
178	}
179	if (cur & 16) {
180	item_insert(&tree, end);
181	if (cur & 32) {
182	if (start <= end)
183	count++;
184	item_tag_set(&tree, end, 0);
185	}
186	}
187	if (cur & 64) {
188	item_insert(&tree, end+1);
189	if (cur & 128)
190	item_tag_set(&tree, end+1, 0);
191	}
192
193	for (i = 0; i < ITEMS; i++) {
194	do {
195	idx[i] = rand();
196	} while (item_lookup(&tree, idx[i]));
197
198	item_insert(&tree, idx[i]);
199	if (rand() & 1) {
200	item_tag_set(&tree, idx[i], 0);
201	if (idx[i] >= start && idx[i] <= end)
202	count++;
203	}
204	/* if (i % 1000 == 0)
205	putchar('.'); */
206	}
207
208	// printf("\ncopying tags...\n");
209	cur = start;
210	tagged = radix_tree_range_tag_if_tagged(&tree, &cur, end, ITEMS, 0, 1);
211
212	// printf("checking copied tags\n");
213	assert(tagged == count);
214	check_copied_tags(&tree, start, end, idx, ITEMS, 0, 1);
215
216	/* Copy tags in several rounds */
217	// printf("\ncopying tags...\n");
218	cur = start;
219	do {
220	tmp = rand() % (count/10+2);
221	tagged = radix_tree_range_tag_if_tagged(&tree, &cur, end, tmp, 0, 2);
222	} while (tmp == tagged);
223
224	// printf("%lu %lu %lu\n", tagged, tmp, count);
225	// printf("checking copied tags\n");
226	check_copied_tags(&tree, start, end, idx, ITEMS, 0, 2);
227	assert(tagged < tmp);
228	verify_tag_consistency(&tree, 0);
229	verify_tag_consistency(&tree, 1);
230	verify_tag_consistency(&tree, 2);
231	// printf("\n");
232	item_kill_tree(&tree);
233	}
234
eb73f7f3	235	static void __locate_check(struct radix_tree_root *tree, unsigned long index,
0a2efc6c	236	unsigned order)
d42cb1a9 MW	237	{
	238	struct item *item;
	239	unsigned long index2;
	240
0a2efc6c	241	item_insert_order(tree, index, order);
d42cb1a9 MW	242	item = item_lookup(tree, index);
	243	index2 = radix_tree_locate_item(tree, item);
	244	if (index != index2) {
0a2efc6c MW	245	printf("index %ld order %d inserted; found %ld\n",
0a2efc6c MW	246	index, order, index2);
d42cb1a9 MW	247	abort();
	248	}
	249	}
	250
eb73f7f3 RZ	251	static void __order_0_locate_check(void)
	252	{
	253	RADIX_TREE(tree, GFP_KERNEL);
	254	int i;
	255
	256	for (i = 0; i < 50; i++)
	257	__locate_check(&tree, rand() % INT_MAX, 0);
	258
	259	item_kill_tree(&tree);
	260	}
	261
d42cb1a9 MW	262	static void locate_check(void)
	263	{
	264	RADIX_TREE(tree, GFP_KERNEL);
0a2efc6c	265	unsigned order;
d42cb1a9 MW	266	unsigned long offset, index;
d42cb1a9 MW	267
eb73f7f3 RZ	268	__order_0_locate_check();
eb73f7f3 RZ	269
0a2efc6c MW	270	for (order = 0; order < 20; order++) {
	271	for (offset = 0; offset < (1 << (order + 3));
	272	offset += (1UL << order)) {
	273	for (index = 0; index < (1UL << (order + 5));
	274	index += (1UL << order)) {
	275	__locate_check(&tree, index + offset, order);
	276	}
	277	if (radix_tree_locate_item(&tree, &tree) != -1)
	278	abort();
d42cb1a9	279
0a2efc6c MW	280	item_kill_tree(&tree);
0a2efc6c MW	281	}
d42cb1a9 MW	282	}
	283
	284	if (radix_tree_locate_item(&tree, &tree) != -1)
	285	abort();
0a2efc6c	286	__locate_check(&tree, -1, 0);
d42cb1a9 MW	287	if (radix_tree_locate_item(&tree, &tree) != -1)
	288	abort();
	289	item_kill_tree(&tree);
	290	}
	291
aa1d62d8	292	static void single_thread_tests(bool long_run)
1366c37e MW	293	{
	294	int i;
	295
d42cb1a9	296	printf("starting single_thread_tests: %d allocated\n", nr_allocated);
4f3755d1 MW	297	multiorder_checks();
4f3755d1 MW	298	printf("after multiorder_check: %d allocated\n", nr_allocated);
d42cb1a9 MW	299	locate_check();
d42cb1a9 MW	300	printf("after locate_check: %d allocated\n", nr_allocated);
1366c37e MW	301	tag_check();
	302	printf("after tag_check: %d allocated\n", nr_allocated);
	303	gang_check();
	304	printf("after gang_check: %d allocated\n", nr_allocated);
	305	add_and_check();
	306	printf("after add_and_check: %d allocated\n", nr_allocated);
	307	dynamic_height_check();
	308	printf("after dynamic_height_check: %d allocated\n", nr_allocated);
aa1d62d8	309	big_gang_check(long_run);
1366c37e	310	printf("after big_gang_check: %d allocated\n", nr_allocated);
aa1d62d8	311	for (i = 0; i < (long_run ? 2000 : 3); i++) {
1366c37e MW	312	copy_tag_check();
	313	printf("%d ", i);
	314	fflush(stdout);
	315	}
	316	printf("after copy_tag_check: %d allocated\n", nr_allocated);
	317	}
	318
aa1d62d8	319	int main(int argc, char **argv)
1366c37e	320	{
aa1d62d8 RZ	321	bool long_run = false;
	322	int opt;
	323
	324	while ((opt = getopt(argc, argv, "l")) != -1) {
	325	if (opt == 'l')
	326	long_run = true;
	327	}
	328
1366c37e MW	329	rcu_register_thread();
	330	radix_tree_init();
	331
	332	regression1_test();
	333	regression2_test();
2d6f45b8	334	regression3_test();
5ac62190	335	iteration_test();
aa1d62d8	336	single_thread_tests(long_run);
1366c37e MW	337
	338	sleep(1);
	339	printf("after sleep(1): %d allocated\n", nr_allocated);
	340	rcu_unregister_thread();
	341
	342	exit(0);
	343	}