1 files changed, 271 insertions, 0 deletions
diff --git a/tools/testing/radix-tree/main.c b/tools/testing/radix-tree/main.c
new file mode 100644
index 000000000000..6b8a412c6a11
--- /dev/null
+++ b/tools/testing/radix-tree/main.c
@@ -0,0 +1,271 @@
+#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(void)
+{
+        int i;
+        for (i = 0; i < 1000; 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 single_thread_tests(void)
+{
+        int i;
+        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();
+        printf("after big_gang_check: %d allocated\n", nr_allocated);
+        for (i = 0; i < 2000; i++) {
+                copy_tag_check();
+                printf("%d ", i);
+                fflush(stdout);
+        }
+        printf("after copy_tag_check: %d allocated\n", nr_allocated);
+}
+int main(void)
+{
+        rcu_register_thread();
+        radix_tree_init();
+        regression1_test();
+        regression2_test();
+        single_thread_tests();
+        sleep(1);
+        printf("after sleep(1): %d allocated\n", nr_allocated);
+        rcu_unregister_thread();
+        exit(0);
+}

diff --git a/tools/testing/radix-tree/main.c b/tools/testing/radix-tree/main.c new file mode 100644 index 000000000000..6b8a412c6a11 --- /dev/null +++ b/tools/testing/radix-tree/main.c
@@ -0,0 +1,271 @@
	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
	64	void big_gang_check(void)
	65	{
	66	int i;
	67
	68	for (i = 0; i < 1000; i++) {
	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
	235	static void single_thread_tests(void)
	236	{
	237	int i;
	238
	239	tag_check();
	240	printf("after tag_check: %d allocated\n", nr_allocated);
	241	gang_check();
	242	printf("after gang_check: %d allocated\n", nr_allocated);
	243	add_and_check();
	244	printf("after add_and_check: %d allocated\n", nr_allocated);
	245	dynamic_height_check();
	246	printf("after dynamic_height_check: %d allocated\n", nr_allocated);
	247	big_gang_check();
	248	printf("after big_gang_check: %d allocated\n", nr_allocated);
	249	for (i = 0; i < 2000; i++) {
	250	copy_tag_check();
	251	printf("%d ", i);
	252	fflush(stdout);
	253	}
	254	printf("after copy_tag_check: %d allocated\n", nr_allocated);
	255	}
	256
	257	int main(void)
	258	{
	259	rcu_register_thread();
	260	radix_tree_init();
	261
	262	regression1_test();
	263	regression2_test();
	264	single_thread_tests();
	265
	266	sleep(1);
	267	printf("after sleep(1): %d allocated\n", nr_allocated);
	268	rcu_unregister_thread();
	269
	270	exit(0);
	271	}