]>
Commit | Line | Data |
---|---|---|
0a835c4f MW |
1 | /* |
2 | * idr-test.c: Test the IDR API | |
3 | * Copyright (c) 2016 Matthew Wilcox <willy@infradead.org> | |
4 | * | |
5 | * This program is free software; you can redistribute it and/or modify it | |
6 | * under the terms and conditions of the GNU General Public License, | |
7 | * version 2, as published by the Free Software Foundation. | |
8 | * | |
9 | * This program is distributed in the hope it will be useful, but WITHOUT | |
10 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
11 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for | |
12 | * more details. | |
13 | */ | |
d37cacc5 | 14 | #include <linux/bitmap.h> |
0a835c4f MW |
15 | #include <linux/idr.h> |
16 | #include <linux/slab.h> | |
17 | #include <linux/kernel.h> | |
18 | #include <linux/errno.h> | |
19 | ||
20 | #include "test.h" | |
21 | ||
22 | #define DUMMY_PTR ((void *)0x12) | |
23 | ||
24 | int item_idr_free(int id, void *p, void *data) | |
25 | { | |
26 | struct item *item = p; | |
27 | assert(item->index == id); | |
28 | free(p); | |
29 | ||
30 | return 0; | |
31 | } | |
32 | ||
33 | void item_idr_remove(struct idr *idr, int id) | |
34 | { | |
35 | struct item *item = idr_find(idr, id); | |
36 | assert(item->index == id); | |
37 | idr_remove(idr, id); | |
38 | free(item); | |
39 | } | |
40 | ||
41 | void idr_alloc_test(void) | |
42 | { | |
43 | unsigned long i; | |
44 | DEFINE_IDR(idr); | |
45 | ||
46 | assert(idr_alloc_cyclic(&idr, DUMMY_PTR, 0, 0x4000, GFP_KERNEL) == 0); | |
47 | assert(idr_alloc_cyclic(&idr, DUMMY_PTR, 0x3ffd, 0x4000, GFP_KERNEL) == 0x3ffd); | |
48 | idr_remove(&idr, 0x3ffd); | |
49 | idr_remove(&idr, 0); | |
50 | ||
51 | for (i = 0x3ffe; i < 0x4003; i++) { | |
52 | int id; | |
53 | struct item *item; | |
54 | ||
55 | if (i < 0x4000) | |
56 | item = item_create(i, 0); | |
57 | else | |
58 | item = item_create(i - 0x3fff, 0); | |
59 | ||
60 | id = idr_alloc_cyclic(&idr, item, 1, 0x4000, GFP_KERNEL); | |
61 | assert(id == item->index); | |
62 | } | |
63 | ||
64 | idr_for_each(&idr, item_idr_free, &idr); | |
65 | idr_destroy(&idr); | |
66 | } | |
67 | ||
68 | void idr_replace_test(void) | |
69 | { | |
70 | DEFINE_IDR(idr); | |
71 | ||
72 | idr_alloc(&idr, (void *)-1, 10, 11, GFP_KERNEL); | |
73 | idr_replace(&idr, &idr, 10); | |
74 | ||
75 | idr_destroy(&idr); | |
76 | } | |
77 | ||
78 | /* | |
79 | * Unlike the radix tree, you can put a NULL pointer -- with care -- into | |
80 | * the IDR. Some interfaces, like idr_find() do not distinguish between | |
81 | * "present, value is NULL" and "not present", but that's exactly what some | |
82 | * users want. | |
83 | */ | |
84 | void idr_null_test(void) | |
85 | { | |
86 | int i; | |
87 | DEFINE_IDR(idr); | |
88 | ||
89 | assert(idr_is_empty(&idr)); | |
90 | ||
91 | assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 0); | |
92 | assert(!idr_is_empty(&idr)); | |
93 | idr_remove(&idr, 0); | |
94 | assert(idr_is_empty(&idr)); | |
95 | ||
96 | assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 0); | |
97 | assert(!idr_is_empty(&idr)); | |
98 | idr_destroy(&idr); | |
99 | assert(idr_is_empty(&idr)); | |
100 | ||
101 | for (i = 0; i < 10; i++) { | |
102 | assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == i); | |
103 | } | |
104 | ||
105 | assert(idr_replace(&idr, DUMMY_PTR, 3) == NULL); | |
106 | assert(idr_replace(&idr, DUMMY_PTR, 4) == NULL); | |
107 | assert(idr_replace(&idr, NULL, 4) == DUMMY_PTR); | |
108 | assert(idr_replace(&idr, DUMMY_PTR, 11) == ERR_PTR(-ENOENT)); | |
109 | idr_remove(&idr, 5); | |
110 | assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 5); | |
111 | idr_remove(&idr, 5); | |
112 | ||
113 | for (i = 0; i < 9; i++) { | |
114 | idr_remove(&idr, i); | |
115 | assert(!idr_is_empty(&idr)); | |
116 | } | |
117 | idr_remove(&idr, 8); | |
118 | assert(!idr_is_empty(&idr)); | |
119 | idr_remove(&idr, 9); | |
120 | assert(idr_is_empty(&idr)); | |
121 | ||
122 | assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 0); | |
123 | assert(idr_replace(&idr, DUMMY_PTR, 3) == ERR_PTR(-ENOENT)); | |
124 | assert(idr_replace(&idr, DUMMY_PTR, 0) == NULL); | |
125 | assert(idr_replace(&idr, NULL, 0) == DUMMY_PTR); | |
126 | ||
127 | idr_destroy(&idr); | |
128 | assert(idr_is_empty(&idr)); | |
129 | ||
130 | for (i = 1; i < 10; i++) { | |
131 | assert(idr_alloc(&idr, NULL, 1, 0, GFP_KERNEL) == i); | |
132 | } | |
133 | ||
134 | idr_destroy(&idr); | |
135 | assert(idr_is_empty(&idr)); | |
136 | } | |
137 | ||
138 | void idr_nowait_test(void) | |
139 | { | |
140 | unsigned int i; | |
141 | DEFINE_IDR(idr); | |
142 | ||
143 | idr_preload(GFP_KERNEL); | |
144 | ||
145 | for (i = 0; i < 3; i++) { | |
146 | struct item *item = item_create(i, 0); | |
147 | assert(idr_alloc(&idr, item, i, i + 1, GFP_NOWAIT) == i); | |
148 | } | |
149 | ||
150 | idr_preload_end(); | |
151 | ||
152 | idr_for_each(&idr, item_idr_free, &idr); | |
153 | idr_destroy(&idr); | |
154 | } | |
155 | ||
2eacc79c RS |
156 | void idr_get_next_test(void) |
157 | { | |
158 | unsigned long i; | |
159 | int nextid; | |
160 | DEFINE_IDR(idr); | |
161 | ||
162 | int indices[] = {4, 7, 9, 15, 65, 128, 1000, 99999, 0}; | |
163 | ||
164 | for(i = 0; indices[i]; i++) { | |
165 | struct item *item = item_create(indices[i], 0); | |
166 | assert(idr_alloc(&idr, item, indices[i], indices[i+1], | |
167 | GFP_KERNEL) == indices[i]); | |
168 | } | |
169 | ||
170 | for(i = 0, nextid = 0; indices[i]; i++) { | |
171 | idr_get_next(&idr, &nextid); | |
172 | assert(nextid == indices[i]); | |
173 | nextid++; | |
174 | } | |
175 | ||
176 | idr_for_each(&idr, item_idr_free, &idr); | |
177 | idr_destroy(&idr); | |
178 | } | |
179 | ||
0a835c4f MW |
180 | void idr_checks(void) |
181 | { | |
182 | unsigned long i; | |
183 | DEFINE_IDR(idr); | |
184 | ||
185 | for (i = 0; i < 10000; i++) { | |
186 | struct item *item = item_create(i, 0); | |
187 | assert(idr_alloc(&idr, item, 0, 20000, GFP_KERNEL) == i); | |
188 | } | |
189 | ||
190 | assert(idr_alloc(&idr, DUMMY_PTR, 5, 30, GFP_KERNEL) < 0); | |
191 | ||
192 | for (i = 0; i < 5000; i++) | |
193 | item_idr_remove(&idr, i); | |
194 | ||
195 | idr_remove(&idr, 3); | |
196 | ||
197 | idr_for_each(&idr, item_idr_free, &idr); | |
198 | idr_destroy(&idr); | |
199 | ||
200 | assert(idr_is_empty(&idr)); | |
201 | ||
202 | idr_remove(&idr, 3); | |
203 | idr_remove(&idr, 0); | |
204 | ||
205 | for (i = INT_MAX - 3UL; i < INT_MAX + 1UL; i++) { | |
206 | struct item *item = item_create(i, 0); | |
207 | assert(idr_alloc(&idr, item, i, i + 10, GFP_KERNEL) == i); | |
208 | } | |
209 | assert(idr_alloc(&idr, DUMMY_PTR, i - 2, i, GFP_KERNEL) == -ENOSPC); | |
210 | ||
211 | idr_for_each(&idr, item_idr_free, &idr); | |
212 | idr_destroy(&idr); | |
213 | idr_destroy(&idr); | |
214 | ||
215 | assert(idr_is_empty(&idr)); | |
216 | ||
217 | for (i = 1; i < 10000; i++) { | |
218 | struct item *item = item_create(i, 0); | |
219 | assert(idr_alloc(&idr, item, 1, 20000, GFP_KERNEL) == i); | |
220 | } | |
221 | ||
222 | idr_for_each(&idr, item_idr_free, &idr); | |
223 | idr_destroy(&idr); | |
224 | ||
225 | idr_replace_test(); | |
226 | idr_alloc_test(); | |
227 | idr_null_test(); | |
228 | idr_nowait_test(); | |
2eacc79c | 229 | idr_get_next_test(); |
0a835c4f MW |
230 | } |
231 | ||
232 | /* | |
233 | * Check that we get the correct error when we run out of memory doing | |
234 | * allocations. To ensure we run out of memory, just "forget" to preload. | |
235 | * The first test is for not having a bitmap available, and the second test | |
236 | * is for not being able to allocate a level of the radix tree. | |
237 | */ | |
238 | void ida_check_nomem(void) | |
239 | { | |
240 | DEFINE_IDA(ida); | |
241 | int id, err; | |
242 | ||
d37cacc5 | 243 | err = ida_get_new_above(&ida, 256, &id); |
0a835c4f MW |
244 | assert(err == -EAGAIN); |
245 | err = ida_get_new_above(&ida, 1UL << 30, &id); | |
246 | assert(err == -EAGAIN); | |
247 | } | |
248 | ||
249 | /* | |
250 | * Check what happens when we fill a leaf and then delete it. This may | |
251 | * discover mishandling of IDR_FREE. | |
252 | */ | |
253 | void ida_check_leaf(void) | |
254 | { | |
255 | DEFINE_IDA(ida); | |
256 | int id; | |
257 | unsigned long i; | |
258 | ||
259 | for (i = 0; i < IDA_BITMAP_BITS; i++) { | |
260 | assert(ida_pre_get(&ida, GFP_KERNEL)); | |
261 | assert(!ida_get_new(&ida, &id)); | |
262 | assert(id == i); | |
263 | } | |
264 | ||
265 | ida_destroy(&ida); | |
266 | assert(ida_is_empty(&ida)); | |
267 | ||
268 | assert(ida_pre_get(&ida, GFP_KERNEL)); | |
269 | assert(!ida_get_new(&ida, &id)); | |
270 | assert(id == 0); | |
271 | ida_destroy(&ida); | |
272 | assert(ida_is_empty(&ida)); | |
273 | } | |
274 | ||
d37cacc5 MW |
275 | /* |
276 | * Check handling of conversions between exceptional entries and full bitmaps. | |
277 | */ | |
278 | void ida_check_conv(void) | |
279 | { | |
280 | DEFINE_IDA(ida); | |
281 | int id; | |
282 | unsigned long i; | |
283 | ||
284 | for (i = 0; i < IDA_BITMAP_BITS * 2; i += IDA_BITMAP_BITS) { | |
285 | assert(ida_pre_get(&ida, GFP_KERNEL)); | |
286 | assert(!ida_get_new_above(&ida, i + 1, &id)); | |
287 | assert(id == i + 1); | |
288 | assert(!ida_get_new_above(&ida, i + BITS_PER_LONG, &id)); | |
289 | assert(id == i + BITS_PER_LONG); | |
290 | ida_remove(&ida, i + 1); | |
291 | ida_remove(&ida, i + BITS_PER_LONG); | |
292 | assert(ida_is_empty(&ida)); | |
293 | } | |
294 | ||
295 | assert(ida_pre_get(&ida, GFP_KERNEL)); | |
296 | ||
297 | for (i = 0; i < IDA_BITMAP_BITS * 2; i++) { | |
298 | assert(ida_pre_get(&ida, GFP_KERNEL)); | |
299 | assert(!ida_get_new(&ida, &id)); | |
300 | assert(id == i); | |
301 | } | |
302 | ||
303 | for (i = IDA_BITMAP_BITS * 2; i > 0; i--) { | |
304 | ida_remove(&ida, i - 1); | |
305 | } | |
306 | assert(ida_is_empty(&ida)); | |
307 | ||
308 | for (i = 0; i < IDA_BITMAP_BITS + BITS_PER_LONG - 4; i++) { | |
309 | assert(ida_pre_get(&ida, GFP_KERNEL)); | |
310 | assert(!ida_get_new(&ida, &id)); | |
311 | assert(id == i); | |
312 | } | |
313 | ||
314 | for (i = IDA_BITMAP_BITS + BITS_PER_LONG - 4; i > 0; i--) { | |
315 | ida_remove(&ida, i - 1); | |
316 | } | |
317 | assert(ida_is_empty(&ida)); | |
318 | ||
319 | radix_tree_cpu_dead(1); | |
320 | for (i = 0; i < 1000000; i++) { | |
321 | int err = ida_get_new(&ida, &id); | |
322 | if (err == -EAGAIN) { | |
323 | assert((i % IDA_BITMAP_BITS) == (BITS_PER_LONG - 2)); | |
324 | assert(ida_pre_get(&ida, GFP_KERNEL)); | |
325 | err = ida_get_new(&ida, &id); | |
326 | } else { | |
327 | assert((i % IDA_BITMAP_BITS) != (BITS_PER_LONG - 2)); | |
328 | } | |
329 | assert(!err); | |
330 | assert(id == i); | |
331 | } | |
332 | ida_destroy(&ida); | |
333 | } | |
334 | ||
0a835c4f MW |
335 | /* |
336 | * Check allocations up to and slightly above the maximum allowed (2^31-1) ID. | |
337 | * Allocating up to 2^31-1 should succeed, and then allocating the next one | |
338 | * should fail. | |
339 | */ | |
340 | void ida_check_max(void) | |
341 | { | |
342 | DEFINE_IDA(ida); | |
343 | int id, err; | |
344 | unsigned long i, j; | |
345 | ||
346 | for (j = 1; j < 65537; j *= 2) { | |
347 | unsigned long base = (1UL << 31) - j; | |
348 | for (i = 0; i < j; i++) { | |
349 | assert(ida_pre_get(&ida, GFP_KERNEL)); | |
350 | assert(!ida_get_new_above(&ida, base, &id)); | |
351 | assert(id == base + i); | |
352 | } | |
353 | assert(ida_pre_get(&ida, GFP_KERNEL)); | |
354 | err = ida_get_new_above(&ida, base, &id); | |
355 | assert(err == -ENOSPC); | |
356 | ida_destroy(&ida); | |
357 | assert(ida_is_empty(&ida)); | |
358 | rcu_barrier(); | |
359 | } | |
360 | } | |
361 | ||
d37cacc5 MW |
362 | void ida_check_random(void) |
363 | { | |
364 | DEFINE_IDA(ida); | |
365 | DECLARE_BITMAP(bitmap, 2048); | |
4ecd9542 | 366 | int id, err; |
d37cacc5 MW |
367 | unsigned int i; |
368 | time_t s = time(NULL); | |
369 | ||
370 | repeat: | |
371 | memset(bitmap, 0, sizeof(bitmap)); | |
372 | for (i = 0; i < 100000; i++) { | |
373 | int i = rand(); | |
374 | int bit = i & 2047; | |
375 | if (test_bit(bit, bitmap)) { | |
376 | __clear_bit(bit, bitmap); | |
377 | ida_remove(&ida, bit); | |
378 | } else { | |
379 | __set_bit(bit, bitmap); | |
4ecd9542 MW |
380 | do { |
381 | ida_pre_get(&ida, GFP_KERNEL); | |
382 | err = ida_get_new_above(&ida, bit, &id); | |
383 | } while (err == -ENOMEM); | |
384 | assert(!err); | |
d37cacc5 MW |
385 | assert(id == bit); |
386 | } | |
387 | } | |
388 | ida_destroy(&ida); | |
389 | if (time(NULL) < s + 10) | |
390 | goto repeat; | |
391 | } | |
392 | ||
166bb1f5 RS |
393 | void ida_simple_get_remove_test(void) |
394 | { | |
395 | DEFINE_IDA(ida); | |
396 | unsigned long i; | |
397 | ||
398 | for (i = 0; i < 10000; i++) { | |
399 | assert(ida_simple_get(&ida, 0, 20000, GFP_KERNEL) == i); | |
400 | } | |
401 | assert(ida_simple_get(&ida, 5, 30, GFP_KERNEL) < 0); | |
402 | ||
403 | for (i = 0; i < 10000; i++) { | |
404 | ida_simple_remove(&ida, i); | |
405 | } | |
406 | assert(ida_is_empty(&ida)); | |
407 | ||
408 | ida_destroy(&ida); | |
409 | } | |
410 | ||
0a835c4f MW |
411 | void ida_checks(void) |
412 | { | |
413 | DEFINE_IDA(ida); | |
414 | int id; | |
415 | unsigned long i; | |
416 | ||
417 | radix_tree_cpu_dead(1); | |
418 | ida_check_nomem(); | |
419 | ||
420 | for (i = 0; i < 10000; i++) { | |
421 | assert(ida_pre_get(&ida, GFP_KERNEL)); | |
422 | assert(!ida_get_new(&ida, &id)); | |
423 | assert(id == i); | |
424 | } | |
425 | ||
426 | ida_remove(&ida, 20); | |
427 | ida_remove(&ida, 21); | |
428 | for (i = 0; i < 3; i++) { | |
429 | assert(ida_pre_get(&ida, GFP_KERNEL)); | |
430 | assert(!ida_get_new(&ida, &id)); | |
431 | if (i == 2) | |
432 | assert(id == 10000); | |
433 | } | |
434 | ||
435 | for (i = 0; i < 5000; i++) | |
436 | ida_remove(&ida, i); | |
437 | ||
438 | assert(ida_pre_get(&ida, GFP_KERNEL)); | |
439 | assert(!ida_get_new_above(&ida, 5000, &id)); | |
440 | assert(id == 10001); | |
441 | ||
442 | ida_destroy(&ida); | |
443 | ||
444 | assert(ida_is_empty(&ida)); | |
445 | ||
446 | assert(ida_pre_get(&ida, GFP_KERNEL)); | |
447 | assert(!ida_get_new_above(&ida, 1, &id)); | |
448 | assert(id == 1); | |
449 | ||
450 | ida_remove(&ida, id); | |
451 | assert(ida_is_empty(&ida)); | |
452 | ida_destroy(&ida); | |
453 | assert(ida_is_empty(&ida)); | |
454 | ||
455 | assert(ida_pre_get(&ida, GFP_KERNEL)); | |
456 | assert(!ida_get_new_above(&ida, 1, &id)); | |
457 | ida_destroy(&ida); | |
458 | assert(ida_is_empty(&ida)); | |
459 | ||
460 | assert(ida_pre_get(&ida, GFP_KERNEL)); | |
461 | assert(!ida_get_new_above(&ida, 1, &id)); | |
462 | assert(id == 1); | |
463 | assert(ida_pre_get(&ida, GFP_KERNEL)); | |
464 | assert(!ida_get_new_above(&ida, 1025, &id)); | |
465 | assert(id == 1025); | |
466 | assert(ida_pre_get(&ida, GFP_KERNEL)); | |
467 | assert(!ida_get_new_above(&ida, 10000, &id)); | |
468 | assert(id == 10000); | |
469 | ida_remove(&ida, 1025); | |
470 | ida_destroy(&ida); | |
471 | assert(ida_is_empty(&ida)); | |
472 | ||
473 | ida_check_leaf(); | |
474 | ida_check_max(); | |
d37cacc5 MW |
475 | ida_check_conv(); |
476 | ida_check_random(); | |
166bb1f5 | 477 | ida_simple_get_remove_test(); |
0a835c4f MW |
478 | |
479 | radix_tree_cpu_dead(1); | |
480 | } | |
8ac04868 | 481 | |
4ecd9542 MW |
482 | static void *ida_random_fn(void *arg) |
483 | { | |
484 | rcu_register_thread(); | |
485 | ida_check_random(); | |
486 | rcu_unregister_thread(); | |
487 | return NULL; | |
488 | } | |
489 | ||
490 | void ida_thread_tests(void) | |
491 | { | |
492 | pthread_t threads[10]; | |
493 | int i; | |
494 | ||
495 | for (i = 0; i < ARRAY_SIZE(threads); i++) | |
496 | if (pthread_create(&threads[i], NULL, ida_random_fn, NULL)) { | |
497 | perror("creating ida thread"); | |
498 | exit(1); | |
499 | } | |
500 | ||
501 | while (i--) | |
502 | pthread_join(threads[i], NULL); | |
503 | } | |
504 | ||
8ac04868 MW |
505 | int __weak main(void) |
506 | { | |
507 | radix_tree_init(); | |
508 | idr_checks(); | |
509 | ida_checks(); | |
4ecd9542 MW |
510 | ida_thread_tests(); |
511 | radix_tree_cpu_dead(1); | |
8ac04868 MW |
512 | rcu_barrier(); |
513 | if (nr_allocated) | |
514 | printf("nr_allocated = %d\n", nr_allocated); | |
515 | return 0; | |
516 | } |