]>
git.proxmox.com Git - mirror_ubuntu-artful-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 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
);
209 assert(idr_alloc(&idr
, DUMMY_PTR
, i
- 2, i
, GFP_KERNEL
) == -ENOSPC
);
211 idr_for_each(&idr
, item_idr_free
, &idr
);
215 assert(idr_is_empty(&idr
));
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
);
222 idr_for_each(&idr
, item_idr_free
, &idr
);
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.
238 void ida_check_nomem(void)
243 err
= ida_get_new_above(&ida
, 256, &id
);
244 assert(err
== -EAGAIN
);
245 err
= ida_get_new_above(&ida
, 1UL << 30, &id
);
246 assert(err
== -EAGAIN
);
250 * Check what happens when we fill a leaf and then delete it. This may
251 * discover mishandling of IDR_FREE.
253 void ida_check_leaf(void)
259 for (i
= 0; i
< IDA_BITMAP_BITS
; i
++) {
260 assert(ida_pre_get(&ida
, GFP_KERNEL
));
261 assert(!ida_get_new(&ida
, &id
));
266 assert(ida_is_empty(&ida
));
268 assert(ida_pre_get(&ida
, GFP_KERNEL
));
269 assert(!ida_get_new(&ida
, &id
));
272 assert(ida_is_empty(&ida
));
276 * Check handling of conversions between exceptional entries and full bitmaps.
278 void ida_check_conv(void)
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
));
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
));
295 assert(ida_pre_get(&ida
, GFP_KERNEL
));
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
));
303 for (i
= IDA_BITMAP_BITS
* 2; i
> 0; i
--) {
304 ida_remove(&ida
, i
- 1);
306 assert(ida_is_empty(&ida
));
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
));
314 for (i
= IDA_BITMAP_BITS
+ BITS_PER_LONG
- 4; i
> 0; i
--) {
315 ida_remove(&ida
, i
- 1);
317 assert(ida_is_empty(&ida
));
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
);
327 assert((i
% IDA_BITMAP_BITS
) != (BITS_PER_LONG
- 2));
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
340 void ida_check_max(void)
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
);
353 assert(ida_pre_get(&ida
, GFP_KERNEL
));
354 err
= ida_get_new_above(&ida
, base
, &id
);
355 assert(err
== -ENOSPC
);
357 assert(ida_is_empty(&ida
));
362 void ida_check_random(void)
365 DECLARE_BITMAP(bitmap
, 2048);
368 time_t s
= time(NULL
);
371 memset(bitmap
, 0, sizeof(bitmap
));
372 for (i
= 0; i
< 100000; i
++) {
375 if (test_bit(bit
, bitmap
)) {
376 __clear_bit(bit
, bitmap
);
377 ida_remove(&ida
, bit
);
379 __set_bit(bit
, bitmap
);
381 ida_pre_get(&ida
, GFP_KERNEL
);
382 err
= ida_get_new_above(&ida
, bit
, &id
);
383 } while (err
== -ENOMEM
);
389 if (time(NULL
) < s
+ 10)
393 void ida_simple_get_remove_test(void)
398 for (i
= 0; i
< 10000; i
++) {
399 assert(ida_simple_get(&ida
, 0, 20000, GFP_KERNEL
) == i
);
401 assert(ida_simple_get(&ida
, 5, 30, GFP_KERNEL
) < 0);
403 for (i
= 0; i
< 10000; i
++) {
404 ida_simple_remove(&ida
, i
);
406 assert(ida_is_empty(&ida
));
411 void ida_checks(void)
417 radix_tree_cpu_dead(1);
420 for (i
= 0; i
< 10000; i
++) {
421 assert(ida_pre_get(&ida
, GFP_KERNEL
));
422 assert(!ida_get_new(&ida
, &id
));
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
));
435 for (i
= 0; i
< 5000; i
++)
438 assert(ida_pre_get(&ida
, GFP_KERNEL
));
439 assert(!ida_get_new_above(&ida
, 5000, &id
));
444 assert(ida_is_empty(&ida
));
446 assert(ida_pre_get(&ida
, GFP_KERNEL
));
447 assert(!ida_get_new_above(&ida
, 1, &id
));
450 ida_remove(&ida
, id
);
451 assert(ida_is_empty(&ida
));
453 assert(ida_is_empty(&ida
));
455 assert(ida_pre_get(&ida
, GFP_KERNEL
));
456 assert(!ida_get_new_above(&ida
, 1, &id
));
458 assert(ida_is_empty(&ida
));
460 assert(ida_pre_get(&ida
, GFP_KERNEL
));
461 assert(!ida_get_new_above(&ida
, 1, &id
));
463 assert(ida_pre_get(&ida
, GFP_KERNEL
));
464 assert(!ida_get_new_above(&ida
, 1025, &id
));
466 assert(ida_pre_get(&ida
, GFP_KERNEL
));
467 assert(!ida_get_new_above(&ida
, 10000, &id
));
469 ida_remove(&ida
, 1025);
471 assert(ida_is_empty(&ida
));
477 ida_simple_get_remove_test();
479 radix_tree_cpu_dead(1);
482 static void *ida_random_fn(void *arg
)
484 rcu_register_thread();
486 rcu_unregister_thread();
490 void ida_thread_tests(void)
492 pthread_t threads
[10];
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");
502 pthread_join(threads
[i
], NULL
);
505 int __weak
main(void)
511 radix_tree_cpu_dead(1);
514 printf("nr_allocated = %d\n", nr_allocated
);