7 #include <linux/slab.h>
8 #include <linux/radix-tree.h>
11 #include "regression.h"
13 void __gang_check(unsigned long middle, long down, long up, int chunk, int hop)
16 RADIX_TREE(tree, GFP_KERNEL);
20 for (idx = -down; idx < up; idx++)
21 item_insert(&tree, middle + idx);
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);
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);
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);
44 void __big_gang_check(void)
51 unsigned long old_start;
53 // printf("0x%08lx\n", start);
54 __gang_check(start, rand() % 113 + 1, rand() % 71,
55 rand() % 157, rand() % 91 + 1);
57 start += rand() % 1000000;
59 if (start < old_start)
64 void big_gang_check(bool long_run)
68 for (i = 0; i < (long_run ? 1000 : 3); i++) {
76 void add_and_check(void)
78 RADIX_TREE(tree, GFP_KERNEL);
80 item_insert(&tree, 44);
81 item_check_present(&tree, 44);
82 item_check_absent(&tree, 43);
83 item_kill_tree(&tree);
86 void dynamic_height_check(void)
89 RADIX_TREE(tree, GFP_KERNEL);
90 tree_verify_min_height(&tree, 0);
92 item_insert(&tree, 42);
93 tree_verify_min_height(&tree, 42);
95 item_insert(&tree, 1000000);
96 tree_verify_min_height(&tree, 1000000);
98 assert(item_delete(&tree, 1000000));
99 tree_verify_min_height(&tree, 42);
101 assert(item_delete(&tree, 42));
102 tree_verify_min_height(&tree, 0);
104 for (i = 0; i < 1000; i++) {
105 item_insert(&tree, i);
106 tree_verify_min_height(&tree, i);
111 assert(item_delete(&tree, i));
113 tree_verify_min_height(&tree, 0);
117 tree_verify_min_height(&tree, i);
120 item_kill_tree(&tree);
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)
127 for (i = 0; i < count; i++) {
128 /* if (i % 1000 == 0)
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));
134 assert(!item_tag_get(tree, idx[i], totag));
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));
141 assert(!(item_tag_get(tree, idx[i], fromtag) ^
142 item_tag_get(tree, idx[i], totag)));
148 void copy_tag_check(void)
150 RADIX_TREE(tree, GFP_KERNEL);
151 unsigned long idx[ITEMS];
152 unsigned long start, end, count = 0, tagged, cur, tmp;
155 // printf("generating radix tree indices...\n");
158 if (start > end && (rand() % 10)) {
163 /* Specifically create items around the start and the end of the range
164 * with high probability to check for off by one errors */
167 item_insert(&tree, start);
171 item_tag_set(&tree, start, 0);
175 item_insert(&tree, start-1);
177 item_tag_set(&tree, start-1, 0);
180 item_insert(&tree, end);
184 item_tag_set(&tree, end, 0);
188 item_insert(&tree, end+1);
190 item_tag_set(&tree, end+1, 0);
193 for (i = 0; i < ITEMS; i++) {
196 } while (item_lookup(&tree, idx[i]));
198 item_insert(&tree, idx[i]);
200 item_tag_set(&tree, idx[i], 0);
201 if (idx[i] >= start && idx[i] <= end)
204 /* if (i % 1000 == 0)
208 // printf("\ncopying tags...\n");
210 tagged = radix_tree_range_tag_if_tagged(&tree, &cur, end, ITEMS, 0, 1);
212 // printf("checking copied tags\n");
213 assert(tagged == count);
214 check_copied_tags(&tree, start, end, idx, ITEMS, 0, 1);
216 /* Copy tags in several rounds */
217 // printf("\ncopying tags...\n");
220 tmp = rand() % (count/10+2);
221 tagged = radix_tree_range_tag_if_tagged(&tree, &cur, end, tmp, 0, 2);
222 } while (tmp == tagged);
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);
232 item_kill_tree(&tree);
235 static void __locate_check(struct radix_tree_root *tree, unsigned long index,
239 unsigned long index2;
241 item_insert_order(tree, index, order);
242 item = item_lookup(tree, index);
243 index2 = radix_tree_locate_item(tree, item);
244 if (index != index2) {
245 printf("index %ld order %d inserted; found %ld\n",
246 index, order, index2);
251 static void __order_0_locate_check(void)
253 RADIX_TREE(tree, GFP_KERNEL);
256 for (i = 0; i < 50; i++)
257 __locate_check(&tree, rand() % INT_MAX, 0);
259 item_kill_tree(&tree);
262 static void locate_check(void)
264 RADIX_TREE(tree, GFP_KERNEL);
266 unsigned long offset, index;
268 __order_0_locate_check();
270 for (order = 0; order < 20; order++) {
271 for (offset = 0; offset < (1 << (order + 3));
272 offset += (1UL << order)) {
273 for (index = 0; index < (1UL << (order + 5));
274 index += (1UL << order)) {
275 __locate_check(&tree, index + offset, order);
277 if (radix_tree_locate_item(&tree, &tree) != -1)
280 item_kill_tree(&tree);
284 if (radix_tree_locate_item(&tree, &tree) != -1)
286 __locate_check(&tree, -1, 0);
287 if (radix_tree_locate_item(&tree, &tree) != -1)
289 item_kill_tree(&tree);
292 static void single_thread_tests(bool long_run)
296 printf("starting single_thread_tests: %d allocated\n", nr_allocated);
298 printf("after multiorder_check: %d allocated\n", nr_allocated);
300 printf("after locate_check: %d allocated\n", nr_allocated);
302 printf("after tag_check: %d allocated\n", nr_allocated);
304 printf("after gang_check: %d allocated\n", nr_allocated);
306 printf("after add_and_check: %d allocated\n", nr_allocated);
307 dynamic_height_check();
308 printf("after dynamic_height_check: %d allocated\n", nr_allocated);
309 big_gang_check(long_run);
310 printf("after big_gang_check: %d allocated\n", nr_allocated);
311 for (i = 0; i < (long_run ? 2000 : 3); i++) {
316 printf("after copy_tag_check: %d allocated\n", nr_allocated);
319 int main(int argc, char **argv)
321 bool long_run = false;
324 while ((opt = getopt(argc, argv, "l")) != -1) {
329 rcu_register_thread();
336 single_thread_tests(long_run);
339 printf("after sleep(1): %d allocated\n", nr_allocated);
340 rcu_unregister_thread();