]>
git.proxmox.com Git - mirror_ubuntu-bionic-kernel.git/blob - tools/testing/radix-tree/idr-test.c
2 * idr-test.c: Test the IDR API
3 * Copyright (c) 2016 Matthew Wilcox <willy@infradead.org>
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.
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
14 #include <linux/bitmap.h>
15 #include <linux/idr.h>
16 #include <linux/slab.h>
17 #include <linux/kernel.h>
18 #include <linux/errno.h>
22 #define DUMMY_PTR ((void *)0x12)
24 int item_idr_free(int id
, void *p
, void *data
)
26 struct item
*item
= p
;
27 assert(item
->index
== id
);
33 void item_idr_remove(struct idr
*idr
, int id
)
35 struct item
*item
= idr_find(idr
, id
);
36 assert(item
->index
== id
);
41 void idr_alloc_test(void)
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);
51 for (i
= 0x3ffe; i
< 0x4003; i
++) {
56 item
= item_create(i
, 0);
58 item
= item_create(i
- 0x3fff, 0);
60 id
= idr_alloc_cyclic(&idr
, item
, 1, 0x4000, GFP_KERNEL
);
61 assert(id
== item
->index
);
64 idr_for_each(&idr
, item_idr_free
, &idr
);
68 void idr_replace_test(void)
72 idr_alloc(&idr
, (void *)-1, 10, 11, GFP_KERNEL
);
73 idr_replace(&idr
, &idr
, 10);
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
84 void idr_null_test(void)
89 assert(idr_is_empty(&idr
));
91 assert(idr_alloc(&idr
, NULL
, 0, 0, GFP_KERNEL
) == 0);
92 assert(!idr_is_empty(&idr
));
94 assert(idr_is_empty(&idr
));
96 assert(idr_alloc(&idr
, NULL
, 0, 0, GFP_KERNEL
) == 0);
97 assert(!idr_is_empty(&idr
));
99 assert(idr_is_empty(&idr
));
101 for (i
= 0; i
< 10; i
++) {
102 assert(idr_alloc(&idr
, NULL
, 0, 0, GFP_KERNEL
) == i
);
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
));
110 assert(idr_alloc(&idr
, NULL
, 0, 0, GFP_KERNEL
) == 5);
113 for (i
= 0; i
< 9; i
++) {
115 assert(!idr_is_empty(&idr
));
118 assert(!idr_is_empty(&idr
));
120 assert(idr_is_empty(&idr
));
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
);
128 assert(idr_is_empty(&idr
));
130 for (i
= 1; i
< 10; i
++) {
131 assert(idr_alloc(&idr
, NULL
, 1, 0, GFP_KERNEL
) == i
);
135 assert(idr_is_empty(&idr
));
138 void idr_nowait_test(void)
143 idr_preload(GFP_KERNEL
);
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
);
152 idr_for_each(&idr
, item_idr_free
, &idr
);
156 void idr_get_next_test(void)
162 int indices
[] = {4, 7, 9, 15, 65, 128, 1000, 99999, 0};
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
]);
170 for(i
= 0, nextid
= 0; indices
[i
]; i
++) {
171 idr_get_next(&idr
, &nextid
);
172 assert(nextid
== indices
[i
]);
176 idr_for_each(&idr
, item_idr_free
, &idr
);
180 void idr_checks(void)
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
);
190 assert(idr_alloc(&idr
, DUMMY_PTR
, 5, 30, GFP_KERNEL
) < 0);
192 for (i
= 0; i
< 5000; i
++)
193 item_idr_remove(&idr
, i
);
197 idr_for_each(&idr
, item_idr_free
, &idr
);
200 assert(idr_is_empty(&idr
));
205 assert(idr_alloc(&idr
, DUMMY_PTR
, 0, 0, GFP_KERNEL
) == 0);
207 for (i
= 1; i
< RADIX_TREE_MAP_SIZE
; i
++)
208 assert(idr_alloc(&idr
, DUMMY_PTR
, 0, 0, GFP_KERNEL
) == i
);
209 idr_remove(&idr
, 1 << 30);
212 for (i
= INT_MAX
- 3UL; i
< INT_MAX
+ 1UL; i
++) {
213 struct item
*item
= item_create(i
, 0);
214 assert(idr_alloc(&idr
, item
, i
, i
+ 10, GFP_KERNEL
) == i
);
216 assert(idr_alloc(&idr
, DUMMY_PTR
, i
- 2, i
, GFP_KERNEL
) == -ENOSPC
);
218 idr_for_each(&idr
, item_idr_free
, &idr
);
222 assert(idr_is_empty(&idr
));
224 for (i
= 1; i
< 10000; i
++) {
225 struct item
*item
= item_create(i
, 0);
226 assert(idr_alloc(&idr
, item
, 1, 20000, GFP_KERNEL
) == i
);
229 idr_for_each(&idr
, item_idr_free
, &idr
);
240 * Check that we get the correct error when we run out of memory doing
241 * allocations. To ensure we run out of memory, just "forget" to preload.
242 * The first test is for not having a bitmap available, and the second test
243 * is for not being able to allocate a level of the radix tree.
245 void ida_check_nomem(void)
250 err
= ida_get_new_above(&ida
, 256, &id
);
251 assert(err
== -EAGAIN
);
252 err
= ida_get_new_above(&ida
, 1UL << 30, &id
);
253 assert(err
== -EAGAIN
);
257 * Check what happens when we fill a leaf and then delete it. This may
258 * discover mishandling of IDR_FREE.
260 void ida_check_leaf(void)
266 for (i
= 0; i
< IDA_BITMAP_BITS
; i
++) {
267 assert(ida_pre_get(&ida
, GFP_KERNEL
));
268 assert(!ida_get_new(&ida
, &id
));
273 assert(ida_is_empty(&ida
));
275 assert(ida_pre_get(&ida
, GFP_KERNEL
));
276 assert(!ida_get_new(&ida
, &id
));
279 assert(ida_is_empty(&ida
));
283 * Check handling of conversions between exceptional entries and full bitmaps.
285 void ida_check_conv(void)
291 for (i
= 0; i
< IDA_BITMAP_BITS
* 2; i
+= IDA_BITMAP_BITS
) {
292 assert(ida_pre_get(&ida
, GFP_KERNEL
));
293 assert(!ida_get_new_above(&ida
, i
+ 1, &id
));
295 assert(!ida_get_new_above(&ida
, i
+ BITS_PER_LONG
, &id
));
296 assert(id
== i
+ BITS_PER_LONG
);
297 ida_remove(&ida
, i
+ 1);
298 ida_remove(&ida
, i
+ BITS_PER_LONG
);
299 assert(ida_is_empty(&ida
));
302 assert(ida_pre_get(&ida
, GFP_KERNEL
));
304 for (i
= 0; i
< IDA_BITMAP_BITS
* 2; i
++) {
305 assert(ida_pre_get(&ida
, GFP_KERNEL
));
306 assert(!ida_get_new(&ida
, &id
));
310 for (i
= IDA_BITMAP_BITS
* 2; i
> 0; i
--) {
311 ida_remove(&ida
, i
- 1);
313 assert(ida_is_empty(&ida
));
315 for (i
= 0; i
< IDA_BITMAP_BITS
+ BITS_PER_LONG
- 4; i
++) {
316 assert(ida_pre_get(&ida
, GFP_KERNEL
));
317 assert(!ida_get_new(&ida
, &id
));
321 for (i
= IDA_BITMAP_BITS
+ BITS_PER_LONG
- 4; i
> 0; i
--) {
322 ida_remove(&ida
, i
- 1);
324 assert(ida_is_empty(&ida
));
326 radix_tree_cpu_dead(1);
327 for (i
= 0; i
< 1000000; i
++) {
328 int err
= ida_get_new(&ida
, &id
);
329 if (err
== -EAGAIN
) {
330 assert((i
% IDA_BITMAP_BITS
) == (BITS_PER_LONG
- 2));
331 assert(ida_pre_get(&ida
, GFP_KERNEL
));
332 err
= ida_get_new(&ida
, &id
);
334 assert((i
% IDA_BITMAP_BITS
) != (BITS_PER_LONG
- 2));
343 * Check allocations up to and slightly above the maximum allowed (2^31-1) ID.
344 * Allocating up to 2^31-1 should succeed, and then allocating the next one
347 void ida_check_max(void)
353 for (j
= 1; j
< 65537; j
*= 2) {
354 unsigned long base
= (1UL << 31) - j
;
355 for (i
= 0; i
< j
; i
++) {
356 assert(ida_pre_get(&ida
, GFP_KERNEL
));
357 assert(!ida_get_new_above(&ida
, base
, &id
));
358 assert(id
== base
+ i
);
360 assert(ida_pre_get(&ida
, GFP_KERNEL
));
361 err
= ida_get_new_above(&ida
, base
, &id
);
362 assert(err
== -ENOSPC
);
364 assert(ida_is_empty(&ida
));
369 void ida_check_random(void)
372 DECLARE_BITMAP(bitmap
, 2048);
375 time_t s
= time(NULL
);
378 memset(bitmap
, 0, sizeof(bitmap
));
379 for (i
= 0; i
< 100000; i
++) {
382 if (test_bit(bit
, bitmap
)) {
383 __clear_bit(bit
, bitmap
);
384 ida_remove(&ida
, bit
);
386 __set_bit(bit
, bitmap
);
388 ida_pre_get(&ida
, GFP_KERNEL
);
389 err
= ida_get_new_above(&ida
, bit
, &id
);
390 } while (err
== -ENOMEM
);
396 if (time(NULL
) < s
+ 10)
400 void ida_simple_get_remove_test(void)
405 for (i
= 0; i
< 10000; i
++) {
406 assert(ida_simple_get(&ida
, 0, 20000, GFP_KERNEL
) == i
);
408 assert(ida_simple_get(&ida
, 5, 30, GFP_KERNEL
) < 0);
410 for (i
= 0; i
< 10000; i
++) {
411 ida_simple_remove(&ida
, i
);
413 assert(ida_is_empty(&ida
));
418 void ida_checks(void)
424 radix_tree_cpu_dead(1);
427 for (i
= 0; i
< 10000; i
++) {
428 assert(ida_pre_get(&ida
, GFP_KERNEL
));
429 assert(!ida_get_new(&ida
, &id
));
433 ida_remove(&ida
, 20);
434 ida_remove(&ida
, 21);
435 for (i
= 0; i
< 3; i
++) {
436 assert(ida_pre_get(&ida
, GFP_KERNEL
));
437 assert(!ida_get_new(&ida
, &id
));
442 for (i
= 0; i
< 5000; i
++)
445 assert(ida_pre_get(&ida
, GFP_KERNEL
));
446 assert(!ida_get_new_above(&ida
, 5000, &id
));
451 assert(ida_is_empty(&ida
));
453 assert(ida_pre_get(&ida
, GFP_KERNEL
));
454 assert(!ida_get_new_above(&ida
, 1, &id
));
457 ida_remove(&ida
, id
);
458 assert(ida_is_empty(&ida
));
460 assert(ida_is_empty(&ida
));
462 assert(ida_pre_get(&ida
, GFP_KERNEL
));
463 assert(!ida_get_new_above(&ida
, 1, &id
));
465 assert(ida_is_empty(&ida
));
467 assert(ida_pre_get(&ida
, GFP_KERNEL
));
468 assert(!ida_get_new_above(&ida
, 1, &id
));
470 assert(ida_pre_get(&ida
, GFP_KERNEL
));
471 assert(!ida_get_new_above(&ida
, 1025, &id
));
473 assert(ida_pre_get(&ida
, GFP_KERNEL
));
474 assert(!ida_get_new_above(&ida
, 10000, &id
));
476 ida_remove(&ida
, 1025);
478 assert(ida_is_empty(&ida
));
484 ida_simple_get_remove_test();
486 radix_tree_cpu_dead(1);
489 static void *ida_random_fn(void *arg
)
491 rcu_register_thread();
493 rcu_unregister_thread();
497 void ida_thread_tests(void)
499 pthread_t threads
[10];
502 for (i
= 0; i
< ARRAY_SIZE(threads
); i
++)
503 if (pthread_create(&threads
[i
], NULL
, ida_random_fn
, NULL
)) {
504 perror("creating ida thread");
509 pthread_join(threads
[i
], NULL
);
512 int __weak
main(void)
518 radix_tree_cpu_dead(1);
521 printf("nr_allocated = %d\n", nr_allocated
);