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 	void **slot;
128 	struct item *item2 = item_create(min);
129 	RADIX_TREE(tree, GFP_KERNEL);
130 
131 	printf("Multiorder index %ld, order %d\n", index, order);
132 
133 	assert(item_insert_order(&tree, index, order) == 0);
134 
135 	for (i = min; i < max; i++) {
136 		struct item *item = item_lookup(&tree, i);
137 		assert(item != 0);
138 		assert(item->index == index);
139 	}
140 	for (i = 0; i < min; i++)
141 		item_check_absent(&tree, i);
142 	for (i = max; i < 2*max; i++)
143 		item_check_absent(&tree, i);
144 	for (i = min; i < max; i++)
145 		assert(radix_tree_insert(&tree, i, item2) == -EEXIST);
146 
147 	slot = radix_tree_lookup_slot(&tree, index);
148 	free(*slot);
149 	radix_tree_replace_slot(&tree, slot, item2);
150 	for (i = min; i < max; i++) {
151 		struct item *item = item_lookup(&tree, i);
152 		assert(item != 0);
153 		assert(item->index == min);
154 	}
155 
156 	assert(item_delete(&tree, min) != 0);
157 
158 	for (i = 0; i < 2*max; i++)
159 		item_check_absent(&tree, i);
160 }
161 
162 static void multiorder_shrink(unsigned long index, int order)
163 {
164 	unsigned long i;
165 	unsigned long max = 1 << order;
166 	RADIX_TREE(tree, GFP_KERNEL);
167 	struct radix_tree_node *node;
168 
169 	printf("Multiorder shrink index %ld, order %d\n", index, order);
170 
171 	assert(item_insert_order(&tree, 0, order) == 0);
172 
173 	node = tree.rnode;
174 
175 	assert(item_insert(&tree, index) == 0);
176 	assert(node != tree.rnode);
177 
178 	assert(item_delete(&tree, index) != 0);
179 	assert(node == tree.rnode);
180 
181 	for (i = 0; i < max; i++) {
182 		struct item *item = item_lookup(&tree, i);
183 		assert(item != 0);
184 		assert(item->index == 0);
185 	}
186 	for (i = max; i < 2*max; i++)
187 		item_check_absent(&tree, i);
188 
189 	if (!item_delete(&tree, 0)) {
190 		printf("failed to delete index %ld (order %d)\n", index, order);		abort();
191 	}
192 
193 	for (i = 0; i < 2*max; i++)
194 		item_check_absent(&tree, i);
195 }
196 
197 static void multiorder_insert_bug(void)
198 {
199 	RADIX_TREE(tree, GFP_KERNEL);
200 
201 	item_insert(&tree, 0);
202 	radix_tree_tag_set(&tree, 0, 0);
203 	item_insert_order(&tree, 3 << 6, 6);
204 
205 	item_kill_tree(&tree);
206 }
207 
208 void multiorder_iteration(void)
209 {
210 	RADIX_TREE(tree, GFP_KERNEL);
211 	struct radix_tree_iter iter;
212 	void **slot;
213 	int i, j, err;
214 
215 	printf("Multiorder iteration test\n");
216 
217 #define NUM_ENTRIES 11
218 	int index[NUM_ENTRIES] = {0, 2, 4, 8, 16, 32, 34, 36, 64, 72, 128};
219 	int order[NUM_ENTRIES] = {1, 1, 2, 3,  4,  1,  0,  1,  3,  0, 7};
220 
221 	for (i = 0; i < NUM_ENTRIES; i++) {
222 		err = item_insert_order(&tree, index[i], order[i]);
223 		assert(!err);
224 	}
225 
226 	for (j = 0; j < 256; j++) {
227 		for (i = 0; i < NUM_ENTRIES; i++)
228 			if (j <= (index[i] | ((1 << order[i]) - 1)))
229 				break;
230 
231 		radix_tree_for_each_slot(slot, &tree, &iter, j) {
232 			int height = order[i] / RADIX_TREE_MAP_SHIFT;
233 			int shift = height * RADIX_TREE_MAP_SHIFT;
234 			int mask = (1 << order[i]) - 1;
235 
236 			assert(iter.index >= (index[i] &~ mask));
237 			assert(iter.index <= (index[i] | mask));
238 			assert(iter.shift == shift);
239 			i++;
240 		}
241 	}
242 
243 	item_kill_tree(&tree);
244 }
245 
246 void multiorder_tagged_iteration(void)
247 {
248 	RADIX_TREE(tree, GFP_KERNEL);
249 	struct radix_tree_iter iter;
250 	void **slot;
251 	unsigned long first = 0;
252 	int i, j;
253 
254 	printf("Multiorder tagged iteration test\n");
255 
256 #define MT_NUM_ENTRIES 9
257 	int index[MT_NUM_ENTRIES] = {0, 2, 4, 16, 32, 40, 64, 72, 128};
258 	int order[MT_NUM_ENTRIES] = {1, 0, 2, 4,  3,  1,  3,  0,   7};
259 
260 #define TAG_ENTRIES 7
261 	int tag_index[TAG_ENTRIES] = {0, 4, 16, 40, 64, 72, 128};
262 
263 	for (i = 0; i < MT_NUM_ENTRIES; i++)
264 		assert(!item_insert_order(&tree, index[i], order[i]));
265 
266 	assert(!radix_tree_tagged(&tree, 1));
267 
268 	for (i = 0; i < TAG_ENTRIES; i++)
269 		assert(radix_tree_tag_set(&tree, tag_index[i], 1));
270 
271 	for (j = 0; j < 256; j++) {
272 		int mask, k;
273 
274 		for (i = 0; i < TAG_ENTRIES; i++) {
275 			for (k = i; index[k] < tag_index[i]; k++)
276 				;
277 			if (j <= (index[k] | ((1 << order[k]) - 1)))
278 				break;
279 		}
280 
281 		radix_tree_for_each_tagged(slot, &tree, &iter, j, 1) {
282 			for (k = i; index[k] < tag_index[i]; k++)
283 				;
284 			mask = (1 << order[k]) - 1;
285 
286 			assert(iter.index >= (tag_index[i] &~ mask));
287 			assert(iter.index <= (tag_index[i] | mask));
288 			i++;
289 		}
290 	}
291 
292 	radix_tree_range_tag_if_tagged(&tree, &first, ~0UL,
293 					MT_NUM_ENTRIES, 1, 2);
294 
295 	for (j = 0; j < 256; j++) {
296 		int mask, k;
297 
298 		for (i = 0; i < TAG_ENTRIES; i++) {
299 			for (k = i; index[k] < tag_index[i]; k++)
300 				;
301 			if (j <= (index[k] | ((1 << order[k]) - 1)))
302 				break;
303 		}
304 
305 		radix_tree_for_each_tagged(slot, &tree, &iter, j, 2) {
306 			for (k = i; index[k] < tag_index[i]; k++)
307 				;
308 			mask = (1 << order[k]) - 1;
309 
310 			assert(iter.index >= (tag_index[i] &~ mask));
311 			assert(iter.index <= (tag_index[i] | mask));
312 			i++;
313 		}
314 	}
315 
316 	first = 1;
317 	radix_tree_range_tag_if_tagged(&tree, &first, ~0UL,
318 					MT_NUM_ENTRIES, 1, 0);
319 	i = 0;
320 	radix_tree_for_each_tagged(slot, &tree, &iter, 0, 0) {
321 		assert(iter.index == tag_index[i]);
322 		i++;
323 	}
324 
325 	item_kill_tree(&tree);
326 }
327 
328 void multiorder_checks(void)
329 {
330 	int i;
331 
332 	for (i = 0; i < 20; i++) {
333 		multiorder_check(200, i);
334 		multiorder_check(0, i);
335 		multiorder_check((1UL << i) + 1, i);
336 	}
337 
338 	for (i = 0; i < 15; i++)
339 		multiorder_shrink((1UL << (i + RADIX_TREE_MAP_SHIFT)), i);
340 
341 	multiorder_insert_bug();
342 	multiorder_tag_tests();
343 	multiorder_iteration();
344 	multiorder_tagged_iteration();
345 }
346