xref: /openbmc/linux/tools/testing/radix-tree/test.c (revision 0edbfea5)
1 #include <stdlib.h>
2 #include <assert.h>
3 #include <stdio.h>
4 #include <linux/types.h>
5 #include <linux/kernel.h>
6 #include <linux/bitops.h>
7 
8 #include "test.h"
9 
10 struct item *
11 item_tag_set(struct radix_tree_root *root, unsigned long index, int tag)
12 {
13 	return radix_tree_tag_set(root, index, tag);
14 }
15 
16 struct item *
17 item_tag_clear(struct radix_tree_root *root, unsigned long index, int tag)
18 {
19 	return radix_tree_tag_clear(root, index, tag);
20 }
21 
22 int item_tag_get(struct radix_tree_root *root, unsigned long index, int tag)
23 {
24 	return radix_tree_tag_get(root, index, tag);
25 }
26 
27 int __item_insert(struct radix_tree_root *root, struct item *item,
28 			unsigned order)
29 {
30 	return __radix_tree_insert(root, item->index, order, item);
31 }
32 
33 int item_insert(struct radix_tree_root *root, unsigned long index)
34 {
35 	return __item_insert(root, item_create(index), 0);
36 }
37 
38 int item_insert_order(struct radix_tree_root *root, unsigned long index,
39 			unsigned order)
40 {
41 	return __item_insert(root, item_create(index), order);
42 }
43 
44 int item_delete(struct radix_tree_root *root, unsigned long index)
45 {
46 	struct item *item = radix_tree_delete(root, index);
47 
48 	if (item) {
49 		assert(item->index == index);
50 		free(item);
51 		return 1;
52 	}
53 	return 0;
54 }
55 
56 struct item *item_create(unsigned long index)
57 {
58 	struct item *ret = malloc(sizeof(*ret));
59 
60 	ret->index = index;
61 	return ret;
62 }
63 
64 void item_check_present(struct radix_tree_root *root, unsigned long index)
65 {
66 	struct item *item;
67 
68 	item = radix_tree_lookup(root, index);
69 	assert(item != 0);
70 	assert(item->index == index);
71 }
72 
73 struct item *item_lookup(struct radix_tree_root *root, unsigned long index)
74 {
75 	return radix_tree_lookup(root, index);
76 }
77 
78 void item_check_absent(struct radix_tree_root *root, unsigned long index)
79 {
80 	struct item *item;
81 
82 	item = radix_tree_lookup(root, index);
83 	assert(item == 0);
84 }
85 
86 /*
87  * Scan only the passed (start, start+nr] for present items
88  */
89 void item_gang_check_present(struct radix_tree_root *root,
90 			unsigned long start, unsigned long nr,
91 			int chunk, int hop)
92 {
93 	struct item *items[chunk];
94 	unsigned long into;
95 
96 	for (into = 0; into < nr; ) {
97 		int nfound;
98 		int nr_to_find = chunk;
99 		int i;
100 
101 		if (nr_to_find > (nr - into))
102 			nr_to_find = nr - into;
103 
104 		nfound = radix_tree_gang_lookup(root, (void **)items,
105 						start + into, nr_to_find);
106 		assert(nfound == nr_to_find);
107 		for (i = 0; i < nfound; i++)
108 			assert(items[i]->index == start + into + i);
109 		into += hop;
110 	}
111 }
112 
113 /*
114  * Scan the entire tree, only expecting present items (start, start+nr]
115  */
116 void item_full_scan(struct radix_tree_root *root, unsigned long start,
117 			unsigned long nr, int chunk)
118 {
119 	struct item *items[chunk];
120 	unsigned long into = 0;
121 	unsigned long this_index = start;
122 	int nfound;
123 	int i;
124 
125 //	printf("%s(0x%08lx, 0x%08lx, %d)\n", __FUNCTION__, start, nr, chunk);
126 
127 	while ((nfound = radix_tree_gang_lookup(root, (void **)items, into,
128 					chunk))) {
129 //		printf("At 0x%08lx, nfound=%d\n", into, nfound);
130 		for (i = 0; i < nfound; i++) {
131 			assert(items[i]->index == this_index);
132 			this_index++;
133 		}
134 //		printf("Found 0x%08lx->0x%08lx\n",
135 //			items[0]->index, items[nfound-1]->index);
136 		into = this_index;
137 	}
138 	if (chunk)
139 		assert(this_index == start + nr);
140 	nfound = radix_tree_gang_lookup(root, (void **)items,
141 					this_index, chunk);
142 	assert(nfound == 0);
143 }
144 
145 static int verify_node(struct radix_tree_node *slot, unsigned int tag,
146 			int tagged)
147 {
148 	int anyset = 0;
149 	int i;
150 	int j;
151 
152 	slot = entry_to_node(slot);
153 
154 	/* Verify consistency at this level */
155 	for (i = 0; i < RADIX_TREE_TAG_LONGS; i++) {
156 		if (slot->tags[tag][i]) {
157 			anyset = 1;
158 			break;
159 		}
160 	}
161 	if (tagged != anyset) {
162 		printf("tag: %u, shift %u, tagged: %d, anyset: %d\n",
163 			tag, slot->shift, tagged, anyset);
164 		for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) {
165 			printf("tag %d: ", j);
166 			for (i = 0; i < RADIX_TREE_TAG_LONGS; i++)
167 				printf("%016lx ", slot->tags[j][i]);
168 			printf("\n");
169 		}
170 		return 1;
171 	}
172 	assert(tagged == anyset);
173 
174 	/* Go for next level */
175 	if (slot->shift > 0) {
176 		for (i = 0; i < RADIX_TREE_MAP_SIZE; i++)
177 			if (slot->slots[i])
178 				if (verify_node(slot->slots[i], tag,
179 					    !!test_bit(i, slot->tags[tag]))) {
180 					printf("Failure at off %d\n", i);
181 					for (j = 0; j < RADIX_TREE_MAX_TAGS; j++) {
182 						printf("tag %d: ", j);
183 						for (i = 0; i < RADIX_TREE_TAG_LONGS; i++)
184 							printf("%016lx ", slot->tags[j][i]);
185 						printf("\n");
186 					}
187 					return 1;
188 				}
189 	}
190 	return 0;
191 }
192 
193 void verify_tag_consistency(struct radix_tree_root *root, unsigned int tag)
194 {
195 	struct radix_tree_node *node = root->rnode;
196 	if (!radix_tree_is_internal_node(node))
197 		return;
198 	verify_node(node, tag, !!root_tag_get(root, tag));
199 }
200 
201 void item_kill_tree(struct radix_tree_root *root)
202 {
203 	struct item *items[32];
204 	int nfound;
205 
206 	while ((nfound = radix_tree_gang_lookup(root, (void **)items, 0, 32))) {
207 		int i;
208 
209 		for (i = 0; i < nfound; i++) {
210 			void *ret;
211 
212 			ret = radix_tree_delete(root, items[i]->index);
213 			assert(ret == items[i]);
214 			free(items[i]);
215 		}
216 	}
217 	assert(radix_tree_gang_lookup(root, (void **)items, 0, 32) == 0);
218 	assert(root->rnode == NULL);
219 }
220 
221 void tree_verify_min_height(struct radix_tree_root *root, int maxindex)
222 {
223 	unsigned shift;
224 	struct radix_tree_node *node = root->rnode;
225 	if (!radix_tree_is_internal_node(node)) {
226 		assert(maxindex == 0);
227 		return;
228 	}
229 
230 	node = entry_to_node(node);
231 	assert(maxindex <= node_maxindex(node));
232 
233 	shift = node->shift;
234 	if (shift > 0)
235 		assert(maxindex > shift_maxindex(shift - RADIX_TREE_MAP_SHIFT));
236 	else
237 		assert(maxindex > 0);
238 }
239