1 /*
2  * multiorder.c: Multi-order radix tree entry testing
3  * Copyright (c) 2016 Intel Corporation
4  * Author: Ross Zwisler <ross.zwisler@linux.intel.com>
5  * Author: Matthew Wilcox <matthew.r.wilcox@intel.com>
6  *
7  * This program is free software; you can redistribute it and/or modify it
8  * under the terms and conditions of the GNU General Public License,
9  * version 2, as published by the Free Software Foundation.
10  *
11  * This program is distributed in the hope it will be useful, but WITHOUT
12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
14  * more details.
15  */
16 #include <linux/radix-tree.h>
17 #include <linux/slab.h>
18 #include <linux/errno.h>
19 
20 #include "test.h"
21 
22 #define for_each_index(i, base, order) \
23 	for (i = base; i < base + (1 << order); i++)
24 
25 static void __multiorder_tag_test(int index, int order)
26 {
27 	RADIX_TREE(tree, GFP_KERNEL);
28 	int base, err, i;
29 	unsigned long first = 0;
30 
31 	/* our canonical entry */
32 	base = index & ~((1 << order) - 1);
33 
34 	printf("Multiorder tag test with index %d, canonical entry %d\n",
35 			index, base);
36 
37 	err = item_insert_order(&tree, index, order);
38 	assert(!err);
39 
40 	/*
41 	 * Verify we get collisions for covered indices.  We try and fail to
42 	 * insert an exceptional entry so we don't leak memory via
43 	 * item_insert_order().
44 	 */
45 	for_each_index(i, base, order) {
46 		err = __radix_tree_insert(&tree, i, order,
47 				(void *)(0xA0 | RADIX_TREE_EXCEPTIONAL_ENTRY));
48 		assert(err == -EEXIST);
49 	}
50 
51 	for_each_index(i, base, order) {
52 		assert(!radix_tree_tag_get(&tree, i, 0));
53 		assert(!radix_tree_tag_get(&tree, i, 1));
54 	}
55 
56 	assert(radix_tree_tag_set(&tree, index, 0));
57 
58 	for_each_index(i, base, order) {
59 		assert(radix_tree_tag_get(&tree, i, 0));
60 		assert(!radix_tree_tag_get(&tree, i, 1));
61 	}
62 
63 	assert(radix_tree_range_tag_if_tagged(&tree, &first, ~0UL, 10, 0, 1) == 1);
64 	assert(radix_tree_tag_clear(&tree, index, 0));
65 
66 	for_each_index(i, base, order) {
67 		assert(!radix_tree_tag_get(&tree, i, 0));
68 		assert(radix_tree_tag_get(&tree, i, 1));
69 	}
70 
71 	assert(radix_tree_tag_clear(&tree, index, 1));
72 
73 	assert(!radix_tree_tagged(&tree, 0));
74 	assert(!radix_tree_tagged(&tree, 1));
75 
76 	item_kill_tree(&tree);
77 }
78 
79 static void multiorder_tag_tests(void)
80 {
81 	/* test multi-order entry for indices 0-7 with no sibling pointers */
82 	__multiorder_tag_test(0, 3);
83 	__multiorder_tag_test(5, 3);
84 
85 	/* test multi-order entry for indices 8-15 with no sibling pointers */
86 	__multiorder_tag_test(8, 3);
87 	__multiorder_tag_test(15, 3);
88 
89 	/*
90 	 * Our order 5 entry covers indices 0-31 in a tree with height=2.
91 	 * This is broken up as follows:
92 	 * 0-7:		canonical entry
93 	 * 8-15:	sibling 1
94 	 * 16-23:	sibling 2
95 	 * 24-31:	sibling 3
96 	 */
97 	__multiorder_tag_test(0, 5);
98 	__multiorder_tag_test(29, 5);
99 
100 	/* same test, but with indices 32-63 */
101 	__multiorder_tag_test(32, 5);
102 	__multiorder_tag_test(44, 5);
103 
104 	/*
105 	 * Our order 8 entry covers indices 0-255 in a tree with height=3.
106 	 * This is broken up as follows:
107 	 * 0-63:	canonical entry
108 	 * 64-127:	sibling 1
109 	 * 128-191:	sibling 2
110 	 * 192-255:	sibling 3
111 	 */
112 	__multiorder_tag_test(0, 8);
113 	__multiorder_tag_test(190, 8);
114 
115 	/* same test, but with indices 256-511 */
116 	__multiorder_tag_test(256, 8);
117 	__multiorder_tag_test(300, 8);
118 
119 	__multiorder_tag_test(0x12345678UL, 8);
120 }
121 
122 static void multiorder_check(unsigned long index, int order)
123 {
124 	unsigned long i;
125 	unsigned long min = index & ~((1UL << order) - 1);
126 	unsigned long max = min + (1UL << order);
127 	RADIX_TREE(tree, GFP_KERNEL);
128 
129 	printf("Multiorder index %ld, order %d\n", index, order);
130 
131 	assert(item_insert_order(&tree, index, order) == 0);
132 
133 	for (i = min; i < max; i++) {
134 		struct item *item = item_lookup(&tree, i);
135 		assert(item != 0);
136 		assert(item->index == index);
137 	}
138 	for (i = 0; i < min; i++)
139 		item_check_absent(&tree, i);
140 	for (i = max; i < 2*max; i++)
141 		item_check_absent(&tree, i);
142 	for (i = min; i < max; i++) {
143 		static void *entry = (void *)
144 					(0xA0 | RADIX_TREE_EXCEPTIONAL_ENTRY);
145 		assert(radix_tree_insert(&tree, i, entry) == -EEXIST);
146 	}
147 
148 	assert(item_delete(&tree, index) != 0);
149 
150 	for (i = 0; i < 2*max; i++)
151 		item_check_absent(&tree, i);
152 }
153 
154 static void multiorder_shrink(unsigned long index, int order)
155 {
156 	unsigned long i;
157 	unsigned long max = 1 << order;
158 	RADIX_TREE(tree, GFP_KERNEL);
159 	struct radix_tree_node *node;
160 
161 	printf("Multiorder shrink index %ld, order %d\n", index, order);
162 
163 	assert(item_insert_order(&tree, 0, order) == 0);
164 
165 	node = tree.rnode;
166 
167 	assert(item_insert(&tree, index) == 0);
168 	assert(node != tree.rnode);
169 
170 	assert(item_delete(&tree, index) != 0);
171 	assert(node == tree.rnode);
172 
173 	for (i = 0; i < max; i++) {
174 		struct item *item = item_lookup(&tree, i);
175 		assert(item != 0);
176 		assert(item->index == 0);
177 	}
178 	for (i = max; i < 2*max; i++)
179 		item_check_absent(&tree, i);
180 
181 	if (!item_delete(&tree, 0)) {
182 		printf("failed to delete index %ld (order %d)\n", index, order);		abort();
183 	}
184 
185 	for (i = 0; i < 2*max; i++)
186 		item_check_absent(&tree, i);
187 }
188 
189 static void multiorder_insert_bug(void)
190 {
191 	RADIX_TREE(tree, GFP_KERNEL);
192 
193 	item_insert(&tree, 0);
194 	radix_tree_tag_set(&tree, 0, 0);
195 	item_insert_order(&tree, 3 << 6, 6);
196 
197 	item_kill_tree(&tree);
198 }
199 
200 void multiorder_iteration(void)
201 {
202 	RADIX_TREE(tree, GFP_KERNEL);
203 	struct radix_tree_iter iter;
204 	void **slot;
205 	int i, j, err;
206 
207 	printf("Multiorder iteration test\n");
208 
209 #define NUM_ENTRIES 11
210 	int index[NUM_ENTRIES] = {0, 2, 4, 8, 16, 32, 34, 36, 64, 72, 128};
211 	int order[NUM_ENTRIES] = {1, 1, 2, 3,  4,  1,  0,  1,  3,  0, 7};
212 
213 	for (i = 0; i < NUM_ENTRIES; i++) {
214 		err = item_insert_order(&tree, index[i], order[i]);
215 		assert(!err);
216 	}
217 
218 	for (j = 0; j < 256; j++) {
219 		for (i = 0; i < NUM_ENTRIES; i++)
220 			if (j <= (index[i] | ((1 << order[i]) - 1)))
221 				break;
222 
223 		radix_tree_for_each_slot(slot, &tree, &iter, j) {
224 			int height = order[i] / RADIX_TREE_MAP_SHIFT;
225 			int shift = height * RADIX_TREE_MAP_SHIFT;
226 			int mask = (1 << order[i]) - 1;
227 
228 			assert(iter.index >= (index[i] &~ mask));
229 			assert(iter.index <= (index[i] | mask));
230 			assert(iter.shift == shift);
231 			i++;
232 		}
233 	}
234 
235 	item_kill_tree(&tree);
236 }
237 
238 void multiorder_tagged_iteration(void)
239 {
240 	RADIX_TREE(tree, GFP_KERNEL);
241 	struct radix_tree_iter iter;
242 	void **slot;
243 	unsigned long first = 0;
244 	int i, j;
245 
246 	printf("Multiorder tagged iteration test\n");
247 
248 #define MT_NUM_ENTRIES 9
249 	int index[MT_NUM_ENTRIES] = {0, 2, 4, 16, 32, 40, 64, 72, 128};
250 	int order[MT_NUM_ENTRIES] = {1, 0, 2, 4,  3,  1,  3,  0,   7};
251 
252 #define TAG_ENTRIES 7
253 	int tag_index[TAG_ENTRIES] = {0, 4, 16, 40, 64, 72, 128};
254 
255 	for (i = 0; i < MT_NUM_ENTRIES; i++)
256 		assert(!item_insert_order(&tree, index[i], order[i]));
257 
258 	assert(!radix_tree_tagged(&tree, 1));
259 
260 	for (i = 0; i < TAG_ENTRIES; i++)
261 		assert(radix_tree_tag_set(&tree, tag_index[i], 1));
262 
263 	for (j = 0; j < 256; j++) {
264 		int mask, k;
265 
266 		for (i = 0; i < TAG_ENTRIES; i++) {
267 			for (k = i; index[k] < tag_index[i]; k++)
268 				;
269 			if (j <= (index[k] | ((1 << order[k]) - 1)))
270 				break;
271 		}
272 
273 		radix_tree_for_each_tagged(slot, &tree, &iter, j, 1) {
274 			for (k = i; index[k] < tag_index[i]; k++)
275 				;
276 			mask = (1 << order[k]) - 1;
277 
278 			assert(iter.index >= (tag_index[i] &~ mask));
279 			assert(iter.index <= (tag_index[i] | mask));
280 			i++;
281 		}
282 	}
283 
284 	radix_tree_range_tag_if_tagged(&tree, &first, ~0UL,
285 					MT_NUM_ENTRIES, 1, 2);
286 
287 	for (j = 0; j < 256; j++) {
288 		int mask, k;
289 
290 		for (i = 0; i < TAG_ENTRIES; i++) {
291 			for (k = i; index[k] < tag_index[i]; k++)
292 				;
293 			if (j <= (index[k] | ((1 << order[k]) - 1)))
294 				break;
295 		}
296 
297 		radix_tree_for_each_tagged(slot, &tree, &iter, j, 2) {
298 			for (k = i; index[k] < tag_index[i]; k++)
299 				;
300 			mask = (1 << order[k]) - 1;
301 
302 			assert(iter.index >= (tag_index[i] &~ mask));
303 			assert(iter.index <= (tag_index[i] | mask));
304 			i++;
305 		}
306 	}
307 
308 	first = 1;
309 	radix_tree_range_tag_if_tagged(&tree, &first, ~0UL,
310 					MT_NUM_ENTRIES, 1, 0);
311 	i = 0;
312 	radix_tree_for_each_tagged(slot, &tree, &iter, 0, 0) {
313 		assert(iter.index == tag_index[i]);
314 		i++;
315 	}
316 
317 	item_kill_tree(&tree);
318 }
319 
320 void multiorder_checks(void)
321 {
322 	int i;
323 
324 	for (i = 0; i < 20; i++) {
325 		multiorder_check(200, i);
326 		multiorder_check(0, i);
327 		multiorder_check((1UL << i) + 1, i);
328 	}
329 
330 	for (i = 0; i < 15; i++)
331 		multiorder_shrink((1UL << (i + RADIX_TREE_MAP_SHIFT)), i);
332 
333 	multiorder_insert_bug();
334 	multiorder_tag_tests();
335 	multiorder_iteration();
336 	multiorder_tagged_iteration();
337 }
338