Commit | Line | Data |
---|---|---|
1366c37e MW |
1 | #include <stdio.h> |
2 | #include <stdlib.h> | |
3 | #include <unistd.h> | |
4 | #include <time.h> | |
5 | #include <assert.h> | |
6 | ||
7 | #include <linux/slab.h> | |
8 | #include <linux/radix-tree.h> | |
9 | ||
10 | #include "test.h" | |
11 | #include "regression.h" | |
12 | ||
13 | void __gang_check(unsigned long middle, long down, long up, int chunk, int hop) | |
14 | { | |
15 | long idx; | |
16 | RADIX_TREE(tree, GFP_KERNEL); | |
17 | ||
18 | middle = 1 << 30; | |
19 | ||
20 | for (idx = -down; idx < up; idx++) | |
21 | item_insert(&tree, middle + idx); | |
22 | ||
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); | |
27 | ||
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); | |
32 | } | |
33 | ||
34 | void gang_check(void) | |
35 | { | |
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); | |
42 | } | |
43 | ||
44 | void __big_gang_check(void) | |
45 | { | |
46 | unsigned long start; | |
47 | int wrapped = 0; | |
48 | ||
49 | start = 0; | |
50 | do { | |
51 | unsigned long old_start; | |
52 | ||
53 | // printf("0x%08lx\n", start); | |
54 | __gang_check(start, rand() % 113 + 1, rand() % 71, | |
55 | rand() % 157, rand() % 91 + 1); | |
56 | old_start = start; | |
57 | start += rand() % 1000000; | |
58 | start %= 1ULL << 33; | |
59 | if (start < old_start) | |
60 | wrapped = 1; | |
61 | } while (!wrapped); | |
62 | } | |
63 | ||
aa1d62d8 | 64 | void big_gang_check(bool long_run) |
1366c37e MW |
65 | { |
66 | int i; | |
67 | ||
aa1d62d8 | 68 | for (i = 0; i < (long_run ? 1000 : 3); i++) { |
1366c37e MW |
69 | __big_gang_check(); |
70 | srand(time(0)); | |
71 | printf("%d ", i); | |
72 | fflush(stdout); | |
73 | } | |
74 | } | |
75 | ||
76 | void add_and_check(void) | |
77 | { | |
78 | RADIX_TREE(tree, GFP_KERNEL); | |
79 | ||
80 | item_insert(&tree, 44); | |
81 | item_check_present(&tree, 44); | |
82 | item_check_absent(&tree, 43); | |
83 | item_kill_tree(&tree); | |
84 | } | |
85 | ||
86 | void dynamic_height_check(void) | |
87 | { | |
88 | int i; | |
89 | RADIX_TREE(tree, GFP_KERNEL); | |
90 | tree_verify_min_height(&tree, 0); | |
91 | ||
92 | item_insert(&tree, 42); | |
93 | tree_verify_min_height(&tree, 42); | |
94 | ||
95 | item_insert(&tree, 1000000); | |
96 | tree_verify_min_height(&tree, 1000000); | |
97 | ||
98 | assert(item_delete(&tree, 1000000)); | |
99 | tree_verify_min_height(&tree, 42); | |
100 | ||
101 | assert(item_delete(&tree, 42)); | |
102 | tree_verify_min_height(&tree, 0); | |
103 | ||
104 | for (i = 0; i < 1000; i++) { | |
105 | item_insert(&tree, i); | |
106 | tree_verify_min_height(&tree, i); | |
107 | } | |
108 | ||
109 | i--; | |
110 | for (;;) { | |
111 | assert(item_delete(&tree, i)); | |
112 | if (i == 0) { | |
113 | tree_verify_min_height(&tree, 0); | |
114 | break; | |
115 | } | |
116 | i--; | |
117 | tree_verify_min_height(&tree, i); | |
118 | } | |
119 | ||
120 | item_kill_tree(&tree); | |
121 | } | |
122 | ||
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) | |
124 | { | |
125 | int i; | |
126 | ||
127 | for (i = 0; i < count; i++) { | |
128 | /* if (i % 1000 == 0) | |
129 | putchar('.'); */ | |
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)); | |
133 | } | |
134 | assert(!item_tag_get(tree, idx[i], totag)); | |
135 | continue; | |
136 | } | |
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)); | |
140 | } | |
141 | assert(!(item_tag_get(tree, idx[i], fromtag) ^ | |
142 | item_tag_get(tree, idx[i], totag))); | |
143 | } | |
144 | } | |
145 | ||
146 | #define ITEMS 50000 | |
147 | ||
148 | void copy_tag_check(void) | |
149 | { | |
150 | RADIX_TREE(tree, GFP_KERNEL); | |
151 | unsigned long idx[ITEMS]; | |
152 | unsigned long start, end, count = 0, tagged, cur, tmp; | |
153 | int i; | |
154 | ||
155 | // printf("generating radix tree indices...\n"); | |
156 | start = rand(); | |
157 | end = rand(); | |
158 | if (start > end && (rand() % 10)) { | |
159 | cur = start; | |
160 | start = end; | |
161 | end = cur; | |
162 | } | |
163 | /* Specifically create items around the start and the end of the range | |
164 | * with high probability to check for off by one errors */ | |
165 | cur = rand(); | |
166 | if (cur & 1) { | |
167 | item_insert(&tree, start); | |
168 | if (cur & 2) { | |
169 | if (start <= end) | |
170 | count++; | |
171 | item_tag_set(&tree, start, 0); | |
172 | } | |
173 | } | |
174 | if (cur & 4) { | |
175 | item_insert(&tree, start-1); | |
176 | if (cur & 8) | |
177 | item_tag_set(&tree, start-1, 0); | |
178 | } | |
179 | if (cur & 16) { | |
180 | item_insert(&tree, end); | |
181 | if (cur & 32) { | |
182 | if (start <= end) | |
183 | count++; | |
184 | item_tag_set(&tree, end, 0); | |
185 | } | |
186 | } | |
187 | if (cur & 64) { | |
188 | item_insert(&tree, end+1); | |
189 | if (cur & 128) | |
190 | item_tag_set(&tree, end+1, 0); | |
191 | } | |
192 | ||
193 | for (i = 0; i < ITEMS; i++) { | |
194 | do { | |
195 | idx[i] = rand(); | |
196 | } while (item_lookup(&tree, idx[i])); | |
197 | ||
198 | item_insert(&tree, idx[i]); | |
199 | if (rand() & 1) { | |
200 | item_tag_set(&tree, idx[i], 0); | |
201 | if (idx[i] >= start && idx[i] <= end) | |
202 | count++; | |
203 | } | |
204 | /* if (i % 1000 == 0) | |
205 | putchar('.'); */ | |
206 | } | |
207 | ||
208 | // printf("\ncopying tags...\n"); | |
209 | cur = start; | |
210 | tagged = radix_tree_range_tag_if_tagged(&tree, &cur, end, ITEMS, 0, 1); | |
211 | ||
212 | // printf("checking copied tags\n"); | |
213 | assert(tagged == count); | |
214 | check_copied_tags(&tree, start, end, idx, ITEMS, 0, 1); | |
215 | ||
216 | /* Copy tags in several rounds */ | |
217 | // printf("\ncopying tags...\n"); | |
218 | cur = start; | |
219 | do { | |
220 | tmp = rand() % (count/10+2); | |
221 | tagged = radix_tree_range_tag_if_tagged(&tree, &cur, end, tmp, 0, 2); | |
222 | } while (tmp == tagged); | |
223 | ||
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); | |
231 | // printf("\n"); | |
232 | item_kill_tree(&tree); | |
233 | } | |
234 | ||
eb73f7f3 | 235 | static void __locate_check(struct radix_tree_root *tree, unsigned long index, |
0a2efc6c | 236 | unsigned order) |
d42cb1a9 MW |
237 | { |
238 | struct item *item; | |
239 | unsigned long index2; | |
240 | ||
0a2efc6c | 241 | item_insert_order(tree, index, order); |
d42cb1a9 MW |
242 | item = item_lookup(tree, index); |
243 | index2 = radix_tree_locate_item(tree, item); | |
244 | if (index != index2) { | |
0a2efc6c MW |
245 | printf("index %ld order %d inserted; found %ld\n", |
246 | index, order, index2); | |
d42cb1a9 MW |
247 | abort(); |
248 | } | |
249 | } | |
250 | ||
eb73f7f3 RZ |
251 | static void __order_0_locate_check(void) |
252 | { | |
253 | RADIX_TREE(tree, GFP_KERNEL); | |
254 | int i; | |
255 | ||
256 | for (i = 0; i < 50; i++) | |
257 | __locate_check(&tree, rand() % INT_MAX, 0); | |
258 | ||
259 | item_kill_tree(&tree); | |
260 | } | |
261 | ||
d42cb1a9 MW |
262 | static void locate_check(void) |
263 | { | |
264 | RADIX_TREE(tree, GFP_KERNEL); | |
0a2efc6c | 265 | unsigned order; |
d42cb1a9 MW |
266 | unsigned long offset, index; |
267 | ||
eb73f7f3 RZ |
268 | __order_0_locate_check(); |
269 | ||
0a2efc6c MW |
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); | |
276 | } | |
277 | if (radix_tree_locate_item(&tree, &tree) != -1) | |
278 | abort(); | |
d42cb1a9 | 279 | |
0a2efc6c MW |
280 | item_kill_tree(&tree); |
281 | } | |
d42cb1a9 MW |
282 | } |
283 | ||
284 | if (radix_tree_locate_item(&tree, &tree) != -1) | |
285 | abort(); | |
0a2efc6c | 286 | __locate_check(&tree, -1, 0); |
d42cb1a9 MW |
287 | if (radix_tree_locate_item(&tree, &tree) != -1) |
288 | abort(); | |
289 | item_kill_tree(&tree); | |
290 | } | |
291 | ||
aa1d62d8 | 292 | static void single_thread_tests(bool long_run) |
1366c37e MW |
293 | { |
294 | int i; | |
295 | ||
d42cb1a9 | 296 | printf("starting single_thread_tests: %d allocated\n", nr_allocated); |
4f3755d1 MW |
297 | multiorder_checks(); |
298 | printf("after multiorder_check: %d allocated\n", nr_allocated); | |
d42cb1a9 MW |
299 | locate_check(); |
300 | printf("after locate_check: %d allocated\n", nr_allocated); | |
1366c37e MW |
301 | tag_check(); |
302 | printf("after tag_check: %d allocated\n", nr_allocated); | |
303 | gang_check(); | |
304 | printf("after gang_check: %d allocated\n", nr_allocated); | |
305 | add_and_check(); | |
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); | |
aa1d62d8 | 309 | big_gang_check(long_run); |
1366c37e | 310 | printf("after big_gang_check: %d allocated\n", nr_allocated); |
aa1d62d8 | 311 | for (i = 0; i < (long_run ? 2000 : 3); i++) { |
1366c37e MW |
312 | copy_tag_check(); |
313 | printf("%d ", i); | |
314 | fflush(stdout); | |
315 | } | |
316 | printf("after copy_tag_check: %d allocated\n", nr_allocated); | |
317 | } | |
318 | ||
aa1d62d8 | 319 | int main(int argc, char **argv) |
1366c37e | 320 | { |
aa1d62d8 RZ |
321 | bool long_run = false; |
322 | int opt; | |
323 | ||
324 | while ((opt = getopt(argc, argv, "l")) != -1) { | |
325 | if (opt == 'l') | |
326 | long_run = true; | |
327 | } | |
328 | ||
1366c37e MW |
329 | rcu_register_thread(); |
330 | radix_tree_init(); | |
331 | ||
332 | regression1_test(); | |
333 | regression2_test(); | |
2d6f45b8 | 334 | regression3_test(); |
aa1d62d8 | 335 | single_thread_tests(long_run); |
1366c37e MW |
336 | |
337 | sleep(1); | |
338 | printf("after sleep(1): %d allocated\n", nr_allocated); | |
339 | rcu_unregister_thread(); | |
340 | ||
341 | exit(0); | |
342 | } |