Commit | Line | Data |
---|---|---|
4f3755d1 MW |
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> | |
fd8f58c4 | 19 | #include <pthread.h> |
4f3755d1 MW |
20 | |
21 | #include "test.h" | |
22 | ||
0fc9b8ca RZ |
23 | #define for_each_index(i, base, order) \ |
24 | for (i = base; i < base + (1 << order); i++) | |
25 | ||
26 | static void __multiorder_tag_test(int index, int order) | |
27 | { | |
28 | RADIX_TREE(tree, GFP_KERNEL); | |
29 | int base, err, i; | |
30 | ||
31 | /* our canonical entry */ | |
32 | base = index & ~((1 << order) - 1); | |
33 | ||
73bc029b | 34 | printv(2, "Multiorder tag test with index %d, canonical entry %d\n", |
0fc9b8ca RZ |
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 | ||
268f42de | 63 | assert(tag_tagged_items(&tree, NULL, 0, ~0UL, 10, 0, 1) == 1); |
0fc9b8ca RZ |
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)); | |
070c5ac2 | 68 | assert(radix_tree_tag_get(&tree, i, 1)); |
0fc9b8ca RZ |
69 | } |
70 | ||
070c5ac2 MW |
71 | assert(radix_tree_tag_clear(&tree, index, 1)); |
72 | ||
0fc9b8ca RZ |
73 | assert(!radix_tree_tagged(&tree, 0)); |
74 | assert(!radix_tree_tagged(&tree, 1)); | |
75 | ||
76 | item_kill_tree(&tree); | |
77 | } | |
78 | ||
3e3cdc68 MW |
79 | static void __multiorder_tag_test2(unsigned order, unsigned long index2) |
80 | { | |
81 | RADIX_TREE(tree, GFP_KERNEL); | |
82 | unsigned long index = (1 << order); | |
83 | index2 += index; | |
84 | ||
85 | assert(item_insert_order(&tree, 0, order) == 0); | |
86 | assert(item_insert(&tree, index2) == 0); | |
87 | ||
88 | assert(radix_tree_tag_set(&tree, 0, 0)); | |
89 | assert(radix_tree_tag_set(&tree, index2, 0)); | |
90 | ||
91 | assert(tag_tagged_items(&tree, NULL, 0, ~0UL, 10, 0, 1) == 2); | |
92 | ||
93 | item_kill_tree(&tree); | |
94 | } | |
95 | ||
0fc9b8ca RZ |
96 | static void multiorder_tag_tests(void) |
97 | { | |
3e3cdc68 MW |
98 | int i, j; |
99 | ||
0fc9b8ca RZ |
100 | /* test multi-order entry for indices 0-7 with no sibling pointers */ |
101 | __multiorder_tag_test(0, 3); | |
102 | __multiorder_tag_test(5, 3); | |
103 | ||
104 | /* test multi-order entry for indices 8-15 with no sibling pointers */ | |
105 | __multiorder_tag_test(8, 3); | |
106 | __multiorder_tag_test(15, 3); | |
107 | ||
108 | /* | |
109 | * Our order 5 entry covers indices 0-31 in a tree with height=2. | |
110 | * This is broken up as follows: | |
111 | * 0-7: canonical entry | |
112 | * 8-15: sibling 1 | |
113 | * 16-23: sibling 2 | |
114 | * 24-31: sibling 3 | |
115 | */ | |
116 | __multiorder_tag_test(0, 5); | |
117 | __multiorder_tag_test(29, 5); | |
118 | ||
119 | /* same test, but with indices 32-63 */ | |
120 | __multiorder_tag_test(32, 5); | |
121 | __multiorder_tag_test(44, 5); | |
122 | ||
123 | /* | |
124 | * Our order 8 entry covers indices 0-255 in a tree with height=3. | |
125 | * This is broken up as follows: | |
126 | * 0-63: canonical entry | |
127 | * 64-127: sibling 1 | |
128 | * 128-191: sibling 2 | |
129 | * 192-255: sibling 3 | |
130 | */ | |
131 | __multiorder_tag_test(0, 8); | |
132 | __multiorder_tag_test(190, 8); | |
133 | ||
134 | /* same test, but with indices 256-511 */ | |
135 | __multiorder_tag_test(256, 8); | |
136 | __multiorder_tag_test(300, 8); | |
137 | ||
138 | __multiorder_tag_test(0x12345678UL, 8); | |
3e3cdc68 MW |
139 | |
140 | for (i = 1; i < 10; i++) | |
141 | for (j = 0; j < (10 << i); j++) | |
142 | __multiorder_tag_test2(i, j); | |
0fc9b8ca RZ |
143 | } |
144 | ||
4f3755d1 MW |
145 | static void multiorder_check(unsigned long index, int order) |
146 | { | |
147 | unsigned long i; | |
148 | unsigned long min = index & ~((1UL << order) - 1); | |
149 | unsigned long max = min + (1UL << order); | |
62fd5258 | 150 | void **slot; |
101d9607 | 151 | struct item *item2 = item_create(min, order); |
4f3755d1 MW |
152 | RADIX_TREE(tree, GFP_KERNEL); |
153 | ||
73bc029b | 154 | printv(2, "Multiorder index %ld, order %d\n", index, order); |
4f3755d1 MW |
155 | |
156 | assert(item_insert_order(&tree, index, order) == 0); | |
157 | ||
158 | for (i = min; i < max; i++) { | |
159 | struct item *item = item_lookup(&tree, i); | |
160 | assert(item != 0); | |
161 | assert(item->index == index); | |
162 | } | |
163 | for (i = 0; i < min; i++) | |
164 | item_check_absent(&tree, i); | |
165 | for (i = max; i < 2*max; i++) | |
166 | item_check_absent(&tree, i); | |
62fd5258 MW |
167 | for (i = min; i < max; i++) |
168 | assert(radix_tree_insert(&tree, i, item2) == -EEXIST); | |
169 | ||
170 | slot = radix_tree_lookup_slot(&tree, index); | |
171 | free(*slot); | |
6d75f366 | 172 | radix_tree_replace_slot(&tree, slot, item2); |
8a14f4d8 | 173 | for (i = min; i < max; i++) { |
62fd5258 MW |
174 | struct item *item = item_lookup(&tree, i); |
175 | assert(item != 0); | |
176 | assert(item->index == min); | |
8a14f4d8 | 177 | } |
4f3755d1 | 178 | |
62fd5258 | 179 | assert(item_delete(&tree, min) != 0); |
4f3755d1 MW |
180 | |
181 | for (i = 0; i < 2*max; i++) | |
182 | item_check_absent(&tree, i); | |
183 | } | |
184 | ||
afe0e395 MW |
185 | static void multiorder_shrink(unsigned long index, int order) |
186 | { | |
187 | unsigned long i; | |
188 | unsigned long max = 1 << order; | |
189 | RADIX_TREE(tree, GFP_KERNEL); | |
190 | struct radix_tree_node *node; | |
191 | ||
73bc029b | 192 | printv(2, "Multiorder shrink index %ld, order %d\n", index, order); |
afe0e395 MW |
193 | |
194 | assert(item_insert_order(&tree, 0, order) == 0); | |
195 | ||
196 | node = tree.rnode; | |
197 | ||
198 | assert(item_insert(&tree, index) == 0); | |
199 | assert(node != tree.rnode); | |
200 | ||
201 | assert(item_delete(&tree, index) != 0); | |
202 | assert(node == tree.rnode); | |
203 | ||
204 | for (i = 0; i < max; i++) { | |
205 | struct item *item = item_lookup(&tree, i); | |
206 | assert(item != 0); | |
207 | assert(item->index == 0); | |
208 | } | |
209 | for (i = max; i < 2*max; i++) | |
210 | item_check_absent(&tree, i); | |
211 | ||
212 | if (!item_delete(&tree, 0)) { | |
73bc029b RS |
213 | printv(2, "failed to delete index %ld (order %d)\n", index, order); |
214 | abort(); | |
afe0e395 MW |
215 | } |
216 | ||
217 | for (i = 0; i < 2*max; i++) | |
218 | item_check_absent(&tree, i); | |
219 | } | |
220 | ||
7b60e9ad MW |
221 | static void multiorder_insert_bug(void) |
222 | { | |
223 | RADIX_TREE(tree, GFP_KERNEL); | |
224 | ||
225 | item_insert(&tree, 0); | |
226 | radix_tree_tag_set(&tree, 0, 0); | |
227 | item_insert_order(&tree, 3 << 6, 6); | |
228 | ||
229 | item_kill_tree(&tree); | |
230 | } | |
231 | ||
643b57d0 RZ |
232 | void multiorder_iteration(void) |
233 | { | |
234 | RADIX_TREE(tree, GFP_KERNEL); | |
235 | struct radix_tree_iter iter; | |
236 | void **slot; | |
8c1244de | 237 | int i, j, err; |
643b57d0 | 238 | |
73bc029b | 239 | printv(1, "Multiorder iteration test\n"); |
643b57d0 RZ |
240 | |
241 | #define NUM_ENTRIES 11 | |
242 | int index[NUM_ENTRIES] = {0, 2, 4, 8, 16, 32, 34, 36, 64, 72, 128}; | |
243 | int order[NUM_ENTRIES] = {1, 1, 2, 3, 4, 1, 0, 1, 3, 0, 7}; | |
244 | ||
245 | for (i = 0; i < NUM_ENTRIES; i++) { | |
246 | err = item_insert_order(&tree, index[i], order[i]); | |
247 | assert(!err); | |
248 | } | |
249 | ||
8c1244de MW |
250 | for (j = 0; j < 256; j++) { |
251 | for (i = 0; i < NUM_ENTRIES; i++) | |
252 | if (j <= (index[i] | ((1 << order[i]) - 1))) | |
253 | break; | |
254 | ||
255 | radix_tree_for_each_slot(slot, &tree, &iter, j) { | |
256 | int height = order[i] / RADIX_TREE_MAP_SHIFT; | |
257 | int shift = height * RADIX_TREE_MAP_SHIFT; | |
148deab2 MW |
258 | unsigned long mask = (1UL << order[i]) - 1; |
259 | struct item *item = *slot; | |
8c1244de | 260 | |
148deab2 | 261 | assert((iter.index | mask) == (index[i] | mask)); |
8c1244de | 262 | assert(iter.shift == shift); |
148deab2 MW |
263 | assert(!radix_tree_is_internal_node(item)); |
264 | assert((item->index | mask) == (index[i] | mask)); | |
265 | assert(item->order == order[i]); | |
8c1244de MW |
266 | i++; |
267 | } | |
643b57d0 RZ |
268 | } |
269 | ||
270 | item_kill_tree(&tree); | |
271 | } | |
272 | ||
273 | void multiorder_tagged_iteration(void) | |
274 | { | |
275 | RADIX_TREE(tree, GFP_KERNEL); | |
276 | struct radix_tree_iter iter; | |
277 | void **slot; | |
8c1244de | 278 | int i, j; |
643b57d0 | 279 | |
73bc029b | 280 | printv(1, "Multiorder tagged iteration test\n"); |
643b57d0 RZ |
281 | |
282 | #define MT_NUM_ENTRIES 9 | |
283 | int index[MT_NUM_ENTRIES] = {0, 2, 4, 16, 32, 40, 64, 72, 128}; | |
284 | int order[MT_NUM_ENTRIES] = {1, 0, 2, 4, 3, 1, 3, 0, 7}; | |
285 | ||
286 | #define TAG_ENTRIES 7 | |
287 | int tag_index[TAG_ENTRIES] = {0, 4, 16, 40, 64, 72, 128}; | |
288 | ||
289 | for (i = 0; i < MT_NUM_ENTRIES; i++) | |
290 | assert(!item_insert_order(&tree, index[i], order[i])); | |
291 | ||
292 | assert(!radix_tree_tagged(&tree, 1)); | |
293 | ||
294 | for (i = 0; i < TAG_ENTRIES; i++) | |
295 | assert(radix_tree_tag_set(&tree, tag_index[i], 1)); | |
296 | ||
8c1244de | 297 | for (j = 0; j < 256; j++) { |
148deab2 | 298 | int k; |
8c1244de MW |
299 | |
300 | for (i = 0; i < TAG_ENTRIES; i++) { | |
301 | for (k = i; index[k] < tag_index[i]; k++) | |
302 | ; | |
303 | if (j <= (index[k] | ((1 << order[k]) - 1))) | |
304 | break; | |
305 | } | |
306 | ||
307 | radix_tree_for_each_tagged(slot, &tree, &iter, j, 1) { | |
148deab2 MW |
308 | unsigned long mask; |
309 | struct item *item = *slot; | |
8c1244de MW |
310 | for (k = i; index[k] < tag_index[i]; k++) |
311 | ; | |
148deab2 | 312 | mask = (1UL << order[k]) - 1; |
8c1244de | 313 | |
148deab2 MW |
314 | assert((iter.index | mask) == (tag_index[i] | mask)); |
315 | assert(!radix_tree_is_internal_node(item)); | |
316 | assert((item->index | mask) == (tag_index[i] | mask)); | |
317 | assert(item->order == order[k]); | |
8c1244de MW |
318 | i++; |
319 | } | |
643b57d0 RZ |
320 | } |
321 | ||
268f42de MW |
322 | assert(tag_tagged_items(&tree, NULL, 0, ~0UL, TAG_ENTRIES, 1, 2) == |
323 | TAG_ENTRIES); | |
070c5ac2 | 324 | |
8c1244de MW |
325 | for (j = 0; j < 256; j++) { |
326 | int mask, k; | |
327 | ||
328 | for (i = 0; i < TAG_ENTRIES; i++) { | |
329 | for (k = i; index[k] < tag_index[i]; k++) | |
330 | ; | |
331 | if (j <= (index[k] | ((1 << order[k]) - 1))) | |
332 | break; | |
333 | } | |
334 | ||
335 | radix_tree_for_each_tagged(slot, &tree, &iter, j, 2) { | |
148deab2 | 336 | struct item *item = *slot; |
8c1244de MW |
337 | for (k = i; index[k] < tag_index[i]; k++) |
338 | ; | |
339 | mask = (1 << order[k]) - 1; | |
340 | ||
148deab2 MW |
341 | assert((iter.index | mask) == (tag_index[i] | mask)); |
342 | assert(!radix_tree_is_internal_node(item)); | |
343 | assert((item->index | mask) == (tag_index[i] | mask)); | |
344 | assert(item->order == order[k]); | |
8c1244de MW |
345 | i++; |
346 | } | |
070c5ac2 MW |
347 | } |
348 | ||
268f42de MW |
349 | assert(tag_tagged_items(&tree, NULL, 1, ~0UL, MT_NUM_ENTRIES * 2, 1, 0) |
350 | == TAG_ENTRIES); | |
070c5ac2 MW |
351 | i = 0; |
352 | radix_tree_for_each_tagged(slot, &tree, &iter, 0, 0) { | |
353 | assert(iter.index == tag_index[i]); | |
354 | i++; | |
355 | } | |
356 | ||
643b57d0 RZ |
357 | item_kill_tree(&tree); |
358 | } | |
359 | ||
3b7869c3 MW |
360 | /* |
361 | * Basic join checks: make sure we can't find an entry in the tree after | |
362 | * a larger entry has replaced it | |
363 | */ | |
e8de4340 | 364 | static void multiorder_join1(unsigned long index, |
175542f5 MW |
365 | unsigned order1, unsigned order2) |
366 | { | |
367 | unsigned long loc; | |
368 | void *item, *item2 = item_create(index + 1, order1); | |
369 | RADIX_TREE(tree, GFP_KERNEL); | |
370 | ||
371 | item_insert_order(&tree, index, order2); | |
372 | item = radix_tree_lookup(&tree, index); | |
373 | radix_tree_join(&tree, index + 1, order1, item2); | |
374 | loc = find_item(&tree, item); | |
375 | if (loc == -1) | |
376 | free(item); | |
377 | item = radix_tree_lookup(&tree, index + 1); | |
378 | assert(item == item2); | |
379 | item_kill_tree(&tree); | |
380 | } | |
381 | ||
3b7869c3 MW |
382 | /* |
383 | * Check that the accounting of exceptional entries is handled correctly | |
384 | * by joining an exceptional entry to a normal pointer. | |
385 | */ | |
e8de4340 | 386 | static void multiorder_join2(unsigned order1, unsigned order2) |
175542f5 MW |
387 | { |
388 | RADIX_TREE(tree, GFP_KERNEL); | |
389 | struct radix_tree_node *node; | |
390 | void *item1 = item_create(0, order1); | |
391 | void *item2; | |
392 | ||
393 | item_insert_order(&tree, 0, order2); | |
394 | radix_tree_insert(&tree, 1 << order2, (void *)0x12UL); | |
395 | item2 = __radix_tree_lookup(&tree, 1 << order2, &node, NULL); | |
396 | assert(item2 == (void *)0x12UL); | |
397 | assert(node->exceptional == 1); | |
398 | ||
3b7869c3 MW |
399 | item2 = radix_tree_lookup(&tree, 0); |
400 | free(item2); | |
401 | ||
175542f5 MW |
402 | radix_tree_join(&tree, 0, order1, item1); |
403 | item2 = __radix_tree_lookup(&tree, 1 << order2, &node, NULL); | |
404 | assert(item2 == item1); | |
405 | assert(node->exceptional == 0); | |
406 | item_kill_tree(&tree); | |
407 | } | |
408 | ||
e8de4340 MW |
409 | /* |
410 | * This test revealed an accounting bug for exceptional entries at one point. | |
411 | * Nodes were being freed back into the pool with an elevated exception count | |
412 | * by radix_tree_join() and then radix_tree_split() was failing to zero the | |
413 | * count of exceptional entries. | |
414 | */ | |
415 | static void multiorder_join3(unsigned int order) | |
416 | { | |
417 | RADIX_TREE(tree, GFP_KERNEL); | |
418 | struct radix_tree_node *node; | |
419 | void **slot; | |
420 | struct radix_tree_iter iter; | |
421 | unsigned long i; | |
422 | ||
423 | for (i = 0; i < (1 << order); i++) { | |
424 | radix_tree_insert(&tree, i, (void *)0x12UL); | |
425 | } | |
426 | ||
427 | radix_tree_join(&tree, 0, order, (void *)0x16UL); | |
428 | rcu_barrier(); | |
429 | ||
430 | radix_tree_split(&tree, 0, 0); | |
431 | ||
432 | radix_tree_for_each_slot(slot, &tree, &iter, 0) { | |
433 | radix_tree_iter_replace(&tree, &iter, slot, (void *)0x12UL); | |
434 | } | |
435 | ||
436 | __radix_tree_lookup(&tree, 0, &node, NULL); | |
437 | assert(node->exceptional == node->count); | |
438 | ||
439 | item_kill_tree(&tree); | |
440 | } | |
441 | ||
175542f5 MW |
442 | static void multiorder_join(void) |
443 | { | |
444 | int i, j, idx; | |
445 | ||
446 | for (idx = 0; idx < 1024; idx = idx * 2 + 3) { | |
447 | for (i = 1; i < 15; i++) { | |
448 | for (j = 0; j < i; j++) { | |
e8de4340 | 449 | multiorder_join1(idx, i, j); |
175542f5 MW |
450 | } |
451 | } | |
452 | } | |
453 | ||
454 | for (i = 1; i < 15; i++) { | |
455 | for (j = 0; j < i; j++) { | |
e8de4340 | 456 | multiorder_join2(i, j); |
175542f5 MW |
457 | } |
458 | } | |
e8de4340 MW |
459 | |
460 | for (i = 3; i < 10; i++) { | |
461 | multiorder_join3(i); | |
462 | } | |
175542f5 MW |
463 | } |
464 | ||
2791653a MW |
465 | static void check_mem(unsigned old_order, unsigned new_order, unsigned alloc) |
466 | { | |
467 | struct radix_tree_preload *rtp = &radix_tree_preloads; | |
468 | if (rtp->nr != 0) | |
73bc029b | 469 | printv(2, "split(%u %u) remaining %u\n", old_order, new_order, |
2791653a MW |
470 | rtp->nr); |
471 | /* | |
472 | * Can't check for equality here as some nodes may have been | |
473 | * RCU-freed while we ran. But we should never finish with more | |
474 | * nodes allocated since they should have all been preloaded. | |
475 | */ | |
476 | if (nr_allocated > alloc) | |
73bc029b | 477 | printv(2, "split(%u %u) allocated %u %u\n", old_order, new_order, |
2791653a MW |
478 | alloc, nr_allocated); |
479 | } | |
480 | ||
e157b555 MW |
481 | static void __multiorder_split(int old_order, int new_order) |
482 | { | |
2791653a | 483 | RADIX_TREE(tree, GFP_ATOMIC); |
e157b555 MW |
484 | void **slot; |
485 | struct radix_tree_iter iter; | |
2791653a | 486 | unsigned alloc; |
3b7869c3 | 487 | struct item *item; |
2791653a MW |
488 | |
489 | radix_tree_preload(GFP_KERNEL); | |
490 | assert(item_insert_order(&tree, 0, old_order) == 0); | |
491 | radix_tree_preload_end(); | |
492 | ||
493 | /* Wipe out the preloaded cache or it'll confuse check_mem() */ | |
494 | radix_tree_cpu_dead(0); | |
e157b555 | 495 | |
3b7869c3 | 496 | item = radix_tree_tag_set(&tree, 0, 2); |
2791653a MW |
497 | |
498 | radix_tree_split_preload(old_order, new_order, GFP_KERNEL); | |
499 | alloc = nr_allocated; | |
e157b555 | 500 | radix_tree_split(&tree, 0, new_order); |
2791653a | 501 | check_mem(old_order, new_order, alloc); |
e157b555 MW |
502 | radix_tree_for_each_slot(slot, &tree, &iter, 0) { |
503 | radix_tree_iter_replace(&tree, &iter, slot, | |
504 | item_create(iter.index, new_order)); | |
505 | } | |
2791653a | 506 | radix_tree_preload_end(); |
e157b555 MW |
507 | |
508 | item_kill_tree(&tree); | |
3b7869c3 | 509 | free(item); |
a90eb3a2 MW |
510 | } |
511 | ||
512 | static void __multiorder_split2(int old_order, int new_order) | |
513 | { | |
514 | RADIX_TREE(tree, GFP_KERNEL); | |
515 | void **slot; | |
516 | struct radix_tree_iter iter; | |
517 | struct radix_tree_node *node; | |
518 | void *item; | |
e157b555 MW |
519 | |
520 | __radix_tree_insert(&tree, 0, old_order, (void *)0x12); | |
521 | ||
522 | item = __radix_tree_lookup(&tree, 0, &node, NULL); | |
523 | assert(item == (void *)0x12); | |
524 | assert(node->exceptional > 0); | |
525 | ||
526 | radix_tree_split(&tree, 0, new_order); | |
527 | radix_tree_for_each_slot(slot, &tree, &iter, 0) { | |
528 | radix_tree_iter_replace(&tree, &iter, slot, | |
529 | item_create(iter.index, new_order)); | |
530 | } | |
531 | ||
532 | item = __radix_tree_lookup(&tree, 0, &node, NULL); | |
533 | assert(item != (void *)0x12); | |
534 | assert(node->exceptional == 0); | |
535 | ||
536 | item_kill_tree(&tree); | |
a90eb3a2 MW |
537 | } |
538 | ||
539 | static void __multiorder_split3(int old_order, int new_order) | |
540 | { | |
541 | RADIX_TREE(tree, GFP_KERNEL); | |
542 | void **slot; | |
543 | struct radix_tree_iter iter; | |
544 | struct radix_tree_node *node; | |
545 | void *item; | |
e157b555 MW |
546 | |
547 | __radix_tree_insert(&tree, 0, old_order, (void *)0x12); | |
548 | ||
549 | item = __radix_tree_lookup(&tree, 0, &node, NULL); | |
550 | assert(item == (void *)0x12); | |
551 | assert(node->exceptional > 0); | |
552 | ||
553 | radix_tree_split(&tree, 0, new_order); | |
554 | radix_tree_for_each_slot(slot, &tree, &iter, 0) { | |
555 | radix_tree_iter_replace(&tree, &iter, slot, (void *)0x16); | |
556 | } | |
557 | ||
558 | item = __radix_tree_lookup(&tree, 0, &node, NULL); | |
559 | assert(item == (void *)0x16); | |
560 | assert(node->exceptional > 0); | |
561 | ||
562 | item_kill_tree(&tree); | |
a90eb3a2 MW |
563 | |
564 | __radix_tree_insert(&tree, 0, old_order, (void *)0x12); | |
565 | ||
566 | item = __radix_tree_lookup(&tree, 0, &node, NULL); | |
567 | assert(item == (void *)0x12); | |
568 | assert(node->exceptional > 0); | |
569 | ||
570 | radix_tree_split(&tree, 0, new_order); | |
571 | radix_tree_for_each_slot(slot, &tree, &iter, 0) { | |
572 | if (iter.index == (1 << new_order)) | |
573 | radix_tree_iter_replace(&tree, &iter, slot, | |
574 | (void *)0x16); | |
575 | else | |
576 | radix_tree_iter_replace(&tree, &iter, slot, NULL); | |
577 | } | |
578 | ||
579 | item = __radix_tree_lookup(&tree, 1 << new_order, &node, NULL); | |
580 | assert(item == (void *)0x16); | |
581 | assert(node->count == node->exceptional); | |
582 | do { | |
583 | node = node->parent; | |
584 | if (!node) | |
585 | break; | |
586 | assert(node->count == 1); | |
587 | assert(node->exceptional == 0); | |
588 | } while (1); | |
589 | ||
590 | item_kill_tree(&tree); | |
e157b555 MW |
591 | } |
592 | ||
593 | static void multiorder_split(void) | |
594 | { | |
595 | int i, j; | |
596 | ||
a90eb3a2 MW |
597 | for (i = 3; i < 11; i++) |
598 | for (j = 0; j < i; j++) { | |
e157b555 | 599 | __multiorder_split(i, j); |
a90eb3a2 MW |
600 | __multiorder_split2(i, j); |
601 | __multiorder_split3(i, j); | |
602 | } | |
603 | } | |
604 | ||
605 | static void multiorder_account(void) | |
606 | { | |
607 | RADIX_TREE(tree, GFP_KERNEL); | |
608 | struct radix_tree_node *node; | |
609 | void **slot; | |
610 | ||
611 | item_insert_order(&tree, 0, 5); | |
612 | ||
613 | __radix_tree_insert(&tree, 1 << 5, 5, (void *)0x12); | |
614 | __radix_tree_lookup(&tree, 0, &node, NULL); | |
615 | assert(node->count == node->exceptional * 2); | |
616 | radix_tree_delete(&tree, 1 << 5); | |
617 | assert(node->exceptional == 0); | |
618 | ||
619 | __radix_tree_insert(&tree, 1 << 5, 5, (void *)0x12); | |
620 | __radix_tree_lookup(&tree, 1 << 5, &node, &slot); | |
621 | assert(node->count == node->exceptional * 2); | |
c7df8ad2 | 622 | __radix_tree_replace(&tree, node, slot, NULL, NULL); |
a90eb3a2 MW |
623 | assert(node->exceptional == 0); |
624 | ||
625 | item_kill_tree(&tree); | |
e157b555 MW |
626 | } |
627 | ||
fd8f58c4 RZ |
628 | bool stop_iteration = false; |
629 | ||
630 | static void *creator_func(void *ptr) | |
631 | { | |
632 | /* 'order' is set up to ensure we have sibling entries */ | |
633 | unsigned int order = RADIX_TREE_MAP_SHIFT - 1; | |
634 | struct radix_tree_root *tree = ptr; | |
635 | int i; | |
636 | ||
637 | for (i = 0; i < 10000; i++) { | |
638 | item_insert_order(tree, 0, order); | |
639 | item_delete_rcu(tree, 0); | |
640 | } | |
641 | ||
642 | stop_iteration = true; | |
643 | return NULL; | |
644 | } | |
645 | ||
646 | static void *iterator_func(void *ptr) | |
647 | { | |
648 | struct radix_tree_root *tree = ptr; | |
649 | struct radix_tree_iter iter; | |
650 | struct item *item; | |
651 | void **slot; | |
652 | ||
653 | while (!stop_iteration) { | |
654 | rcu_read_lock(); | |
655 | radix_tree_for_each_slot(slot, tree, &iter, 0) { | |
656 | item = radix_tree_deref_slot(slot); | |
657 | ||
658 | if (!item) | |
659 | continue; | |
660 | if (radix_tree_deref_retry(item)) { | |
661 | slot = radix_tree_iter_retry(&iter); | |
662 | continue; | |
663 | } | |
664 | ||
665 | item_sanity(item, iter.index); | |
666 | } | |
667 | rcu_read_unlock(); | |
668 | } | |
669 | return NULL; | |
670 | } | |
671 | ||
672 | static void multiorder_iteration_race(void) | |
673 | { | |
674 | const int num_threads = sysconf(_SC_NPROCESSORS_ONLN); | |
675 | pthread_t worker_thread[num_threads]; | |
676 | RADIX_TREE(tree, GFP_KERNEL); | |
677 | int i; | |
678 | ||
679 | pthread_create(&worker_thread[0], NULL, &creator_func, &tree); | |
680 | for (i = 1; i < num_threads; i++) | |
681 | pthread_create(&worker_thread[i], NULL, &iterator_func, &tree); | |
682 | ||
683 | for (i = 0; i < num_threads; i++) | |
684 | pthread_join(worker_thread[i], NULL); | |
685 | ||
686 | item_kill_tree(&tree); | |
687 | } | |
688 | ||
4f3755d1 MW |
689 | void multiorder_checks(void) |
690 | { | |
691 | int i; | |
692 | ||
693 | for (i = 0; i < 20; i++) { | |
694 | multiorder_check(200, i); | |
695 | multiorder_check(0, i); | |
696 | multiorder_check((1UL << i) + 1, i); | |
697 | } | |
afe0e395 MW |
698 | |
699 | for (i = 0; i < 15; i++) | |
700 | multiorder_shrink((1UL << (i + RADIX_TREE_MAP_SHIFT)), i); | |
701 | ||
7b60e9ad | 702 | multiorder_insert_bug(); |
0fc9b8ca | 703 | multiorder_tag_tests(); |
643b57d0 RZ |
704 | multiorder_iteration(); |
705 | multiorder_tagged_iteration(); | |
175542f5 | 706 | multiorder_join(); |
e157b555 | 707 | multiorder_split(); |
a90eb3a2 | 708 | multiorder_account(); |
fd8f58c4 | 709 | multiorder_iteration_race(); |
2791653a MW |
710 | |
711 | radix_tree_cpu_dead(0); | |
4f3755d1 | 712 | } |
8ac04868 MW |
713 | |
714 | int __weak main(void) | |
715 | { | |
716 | radix_tree_init(); | |
717 | multiorder_checks(); | |
718 | return 0; | |
719 | } |