testing/radix-tree/idr-test.c

0001 // SPDX-License-Identifier: GPL-2.0-only
0002 /*
0003  * idr-test.c: Test the IDR API
0004  * Copyright (c) 2016 Matthew Wilcox <willy@infradead.org>
0005  */
0006 #include <linux/bitmap.h>
0007 #include <linux/idr.h>
0008 #include <linux/slab.h>
0009 #include <linux/kernel.h>
0010 #include <linux/errno.h>
0011
0012 #include "test.h"
0013
0014 #define DUMMY_PTR   ((void *)0x10)
0015
0016 int item_idr_free(int id, void *p, void *data)
0017 {
0018     struct item *item = p;
0019     assert(item->index == id);
0020     free(p);
0021
0022     return 0;
0023 }
0024
0025 void item_idr_remove(struct idr *idr, int id)
0026 {
0027     struct item *item = idr_find(idr, id);
0028     assert(item->index == id);
0029     idr_remove(idr, id);
0030     free(item);
0031 }
0032
0033 void idr_alloc_test(void)
0034 {
0035     unsigned long i;
0036     DEFINE_IDR(idr);
0037
0038     assert(idr_alloc_cyclic(&idr, DUMMY_PTR, 0, 0x4000, GFP_KERNEL) == 0);
0039     assert(idr_alloc_cyclic(&idr, DUMMY_PTR, 0x3ffd, 0x4000, GFP_KERNEL) == 0x3ffd);
0040     idr_remove(&idr, 0x3ffd);
0041     idr_remove(&idr, 0);
0042
0043     for (i = 0x3ffe; i < 0x4003; i++) {
0044         int id;
0045         struct item *item;
0046
0047         if (i < 0x4000)
0048             item = item_create(i, 0);
0049         else
0050             item = item_create(i - 0x3fff, 0);
0051
0052         id = idr_alloc_cyclic(&idr, item, 1, 0x4000, GFP_KERNEL);
0053         assert(id == item->index);
0054     }
0055
0056     idr_for_each(&idr, item_idr_free, &idr);
0057     idr_destroy(&idr);
0058 }
0059
0060 void idr_replace_test(void)
0061 {
0062     DEFINE_IDR(idr);
0063
0064     idr_alloc(&idr, (void *)-1, 10, 11, GFP_KERNEL);
0065     idr_replace(&idr, &idr, 10);
0066
0067     idr_destroy(&idr);
0068 }
0069
0070 /*
0071  * Unlike the radix tree, you can put a NULL pointer -- with care -- into
0072  * the IDR.  Some interfaces, like idr_find() do not distinguish between
0073  * "present, value is NULL" and "not present", but that's exactly what some
0074  * users want.
0075  */
0076 void idr_null_test(void)
0077 {
0078     int i;
0079     DEFINE_IDR(idr);
0080
0081     assert(idr_is_empty(&idr));
0082
0083     assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 0);
0084     assert(!idr_is_empty(&idr));
0085     idr_remove(&idr, 0);
0086     assert(idr_is_empty(&idr));
0087
0088     assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 0);
0089     assert(!idr_is_empty(&idr));
0090     idr_destroy(&idr);
0091     assert(idr_is_empty(&idr));
0092
0093     for (i = 0; i < 10; i++) {
0094         assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == i);
0095     }
0096
0097     assert(idr_replace(&idr, DUMMY_PTR, 3) == NULL);
0098     assert(idr_replace(&idr, DUMMY_PTR, 4) == NULL);
0099     assert(idr_replace(&idr, NULL, 4) == DUMMY_PTR);
0100     assert(idr_replace(&idr, DUMMY_PTR, 11) == ERR_PTR(-ENOENT));
0101     idr_remove(&idr, 5);
0102     assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 5);
0103     idr_remove(&idr, 5);
0104
0105     for (i = 0; i < 9; i++) {
0106         idr_remove(&idr, i);
0107         assert(!idr_is_empty(&idr));
0108     }
0109     idr_remove(&idr, 8);
0110     assert(!idr_is_empty(&idr));
0111     idr_remove(&idr, 9);
0112     assert(idr_is_empty(&idr));
0113
0114     assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 0);
0115     assert(idr_replace(&idr, DUMMY_PTR, 3) == ERR_PTR(-ENOENT));
0116     assert(idr_replace(&idr, DUMMY_PTR, 0) == NULL);
0117     assert(idr_replace(&idr, NULL, 0) == DUMMY_PTR);
0118
0119     idr_destroy(&idr);
0120     assert(idr_is_empty(&idr));
0121
0122     for (i = 1; i < 10; i++) {
0123         assert(idr_alloc(&idr, NULL, 1, 0, GFP_KERNEL) == i);
0124     }
0125
0126     idr_destroy(&idr);
0127     assert(idr_is_empty(&idr));
0128 }
0129
0130 void idr_nowait_test(void)
0131 {
0132     unsigned int i;
0133     DEFINE_IDR(idr);
0134
0135     idr_preload(GFP_KERNEL);
0136
0137     for (i = 0; i < 3; i++) {
0138         struct item *item = item_create(i, 0);
0139         assert(idr_alloc(&idr, item, i, i + 1, GFP_NOWAIT) == i);
0140     }
0141
0142     idr_preload_end();
0143
0144     idr_for_each(&idr, item_idr_free, &idr);
0145     idr_destroy(&idr);
0146 }
0147
0148 void idr_get_next_test(int base)
0149 {
0150     unsigned long i;
0151     int nextid;
0152     DEFINE_IDR(idr);
0153     idr_init_base(&idr, base);
0154
0155     int indices[] = {4, 7, 9, 15, 65, 128, 1000, 99999, 0};
0156
0157     for(i = 0; indices[i]; i++) {
0158         struct item *item = item_create(indices[i], 0);
0159         assert(idr_alloc(&idr, item, indices[i], indices[i+1],
0160                  GFP_KERNEL) == indices[i]);
0161     }
0162
0163     for(i = 0, nextid = 0; indices[i]; i++) {
0164         idr_get_next(&idr, &nextid);
0165         assert(nextid == indices[i]);
0166         nextid++;
0167     }
0168
0169     idr_for_each(&idr, item_idr_free, &idr);
0170     idr_destroy(&idr);
0171 }
0172
0173 int idr_u32_cb(int id, void *ptr, void *data)
0174 {
0175     BUG_ON(id < 0);
0176     BUG_ON(ptr != DUMMY_PTR);
0177     return 0;
0178 }
0179
0180 void idr_u32_test1(struct idr *idr, u32 handle)
0181 {
0182     static bool warned = false;
0183     u32 id = handle;
0184     int sid = 0;
0185     void *ptr;
0186
0187     BUG_ON(idr_alloc_u32(idr, DUMMY_PTR, &id, id, GFP_KERNEL));
0188     BUG_ON(id != handle);
0189     BUG_ON(idr_alloc_u32(idr, DUMMY_PTR, &id, id, GFP_KERNEL) != -ENOSPC);
0190     BUG_ON(id != handle);
0191     if (!warned && id > INT_MAX)
0192         printk("vvv Ignore these warnings\n");
0193     ptr = idr_get_next(idr, &sid);
0194     if (id > INT_MAX) {
0195         BUG_ON(ptr != NULL);
0196         BUG_ON(sid != 0);
0197     } else {
0198         BUG_ON(ptr != DUMMY_PTR);
0199         BUG_ON(sid != id);
0200     }
0201     idr_for_each(idr, idr_u32_cb, NULL);
0202     if (!warned && id > INT_MAX) {
0203         printk("^^^ Warnings over\n");
0204         warned = true;
0205     }
0206     BUG_ON(idr_remove(idr, id) != DUMMY_PTR);
0207     BUG_ON(!idr_is_empty(idr));
0208 }
0209
0210 void idr_u32_test(int base)
0211 {
0212     DEFINE_IDR(idr);
0213     idr_init_base(&idr, base);
0214     idr_u32_test1(&idr, 10);
0215     idr_u32_test1(&idr, 0x7fffffff);
0216     idr_u32_test1(&idr, 0x80000000);
0217     idr_u32_test1(&idr, 0x80000001);
0218     idr_u32_test1(&idr, 0xffe00000);
0219     idr_u32_test1(&idr, 0xffffffff);
0220 }
0221
0222 static void idr_align_test(struct idr *idr)
0223 {
0224     char name[] = "Motorola 68000";
0225     int i, id;
0226     void *entry;
0227
0228     for (i = 0; i < 9; i++) {
0229         BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != i);
0230         idr_for_each_entry(idr, entry, id);
0231     }
0232     idr_destroy(idr);
0233
0234     for (i = 1; i < 10; i++) {
0235         BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != i - 1);
0236         idr_for_each_entry(idr, entry, id);
0237     }
0238     idr_destroy(idr);
0239
0240     for (i = 2; i < 11; i++) {
0241         BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != i - 2);
0242         idr_for_each_entry(idr, entry, id);
0243     }
0244     idr_destroy(idr);
0245
0246     for (i = 3; i < 12; i++) {
0247         BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != i - 3);
0248         idr_for_each_entry(idr, entry, id);
0249     }
0250     idr_destroy(idr);
0251
0252     for (i = 0; i < 8; i++) {
0253         BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != 0);
0254         BUG_ON(idr_alloc(idr, &name[i + 1], 0, 0, GFP_KERNEL) != 1);
0255         idr_for_each_entry(idr, entry, id);
0256         idr_remove(idr, 1);
0257         idr_for_each_entry(idr, entry, id);
0258         idr_remove(idr, 0);
0259         BUG_ON(!idr_is_empty(idr));
0260     }
0261
0262     for (i = 0; i < 8; i++) {
0263         BUG_ON(idr_alloc(idr, NULL, 0, 0, GFP_KERNEL) != 0);
0264         idr_for_each_entry(idr, entry, id);
0265         idr_replace(idr, &name[i], 0);
0266         idr_for_each_entry(idr, entry, id);
0267         BUG_ON(idr_find(idr, 0) != &name[i]);
0268         idr_remove(idr, 0);
0269     }
0270
0271     for (i = 0; i < 8; i++) {
0272         BUG_ON(idr_alloc(idr, &name[i], 0, 0, GFP_KERNEL) != 0);
0273         BUG_ON(idr_alloc(idr, NULL, 0, 0, GFP_KERNEL) != 1);
0274         idr_remove(idr, 1);
0275         idr_for_each_entry(idr, entry, id);
0276         idr_replace(idr, &name[i + 1], 0);
0277         idr_for_each_entry(idr, entry, id);
0278         idr_remove(idr, 0);
0279     }
0280 }
0281
0282 DEFINE_IDR(find_idr);
0283
0284 static void *idr_throbber(void *arg)
0285 {
0286     time_t start = time(NULL);
0287     int id = *(int *)arg;
0288
0289     rcu_register_thread();
0290     do {
0291         idr_alloc(&find_idr, xa_mk_value(id), id, id + 1, GFP_KERNEL);
0292         idr_remove(&find_idr, id);
0293     } while (time(NULL) < start + 10);
0294     rcu_unregister_thread();
0295
0296     return NULL;
0297 }
0298
0299 /*
0300  * There are always either 1 or 2 objects in the IDR.  If we find nothing,
0301  * or we find something at an ID we didn't expect, that's a bug.
0302  */
0303 void idr_find_test_1(int anchor_id, int throbber_id)
0304 {
0305     pthread_t throbber;
0306     time_t start = time(NULL);
0307
0308     BUG_ON(idr_alloc(&find_idr, xa_mk_value(anchor_id), anchor_id,
0309                 anchor_id + 1, GFP_KERNEL) != anchor_id);
0310
0311     pthread_create(&throbber, NULL, idr_throbber, &throbber_id);
0312
0313     rcu_read_lock();
0314     do {
0315         int id = 0;
0316         void *entry = idr_get_next(&find_idr, &id);
0317         rcu_read_unlock();
0318         if ((id != anchor_id && id != throbber_id) ||
0319             entry != xa_mk_value(id)) {
0320             printf("%s(%d, %d): %p at %d\n", __func__, anchor_id,
0321                 throbber_id, entry, id);
0322             abort();
0323         }
0324         rcu_read_lock();
0325     } while (time(NULL) < start + 11);
0326     rcu_read_unlock();
0327
0328     pthread_join(throbber, NULL);
0329
0330     idr_remove(&find_idr, anchor_id);
0331     BUG_ON(!idr_is_empty(&find_idr));
0332 }
0333
0334 void idr_find_test(void)
0335 {
0336     idr_find_test_1(100000, 0);
0337     idr_find_test_1(0, 100000);
0338 }
0339
0340 void idr_checks(void)
0341 {
0342     unsigned long i;
0343     DEFINE_IDR(idr);
0344
0345     for (i = 0; i < 10000; i++) {
0346         struct item *item = item_create(i, 0);
0347         assert(idr_alloc(&idr, item, 0, 20000, GFP_KERNEL) == i);
0348     }
0349
0350     assert(idr_alloc(&idr, DUMMY_PTR, 5, 30, GFP_KERNEL) < 0);
0351
0352     for (i = 0; i < 5000; i++)
0353         item_idr_remove(&idr, i);
0354
0355     idr_remove(&idr, 3);
0356
0357     idr_for_each(&idr, item_idr_free, &idr);
0358     idr_destroy(&idr);
0359
0360     assert(idr_is_empty(&idr));
0361
0362     idr_remove(&idr, 3);
0363     idr_remove(&idr, 0);
0364
0365     assert(idr_alloc(&idr, DUMMY_PTR, 0, 0, GFP_KERNEL) == 0);
0366     idr_remove(&idr, 1);
0367     for (i = 1; i < RADIX_TREE_MAP_SIZE; i++)
0368         assert(idr_alloc(&idr, DUMMY_PTR, 0, 0, GFP_KERNEL) == i);
0369     idr_remove(&idr, 1 << 30);
0370     idr_destroy(&idr);
0371
0372     for (i = INT_MAX - 3UL; i < INT_MAX + 1UL; i++) {
0373         struct item *item = item_create(i, 0);
0374         assert(idr_alloc(&idr, item, i, i + 10, GFP_KERNEL) == i);
0375     }
0376     assert(idr_alloc(&idr, DUMMY_PTR, i - 2, i, GFP_KERNEL) == -ENOSPC);
0377     assert(idr_alloc(&idr, DUMMY_PTR, i - 2, i + 10, GFP_KERNEL) == -ENOSPC);
0378
0379     idr_for_each(&idr, item_idr_free, &idr);
0380     idr_destroy(&idr);
0381     idr_destroy(&idr);
0382
0383     assert(idr_is_empty(&idr));
0384
0385     idr_set_cursor(&idr, INT_MAX - 3UL);
0386     for (i = INT_MAX - 3UL; i < INT_MAX + 3UL; i++) {
0387         struct item *item;
0388         unsigned int id;
0389         if (i <= INT_MAX)
0390             item = item_create(i, 0);
0391         else
0392             item = item_create(i - INT_MAX - 1, 0);
0393
0394         id = idr_alloc_cyclic(&idr, item, 0, 0, GFP_KERNEL);
0395         assert(id == item->index);
0396     }
0397
0398     idr_for_each(&idr, item_idr_free, &idr);
0399     idr_destroy(&idr);
0400     assert(idr_is_empty(&idr));
0401
0402     for (i = 1; i < 10000; i++) {
0403         struct item *item = item_create(i, 0);
0404         assert(idr_alloc(&idr, item, 1, 20000, GFP_KERNEL) == i);
0405     }
0406
0407     idr_for_each(&idr, item_idr_free, &idr);
0408     idr_destroy(&idr);
0409
0410     idr_replace_test();
0411     idr_alloc_test();
0412     idr_null_test();
0413     idr_nowait_test();
0414     idr_get_next_test(0);
0415     idr_get_next_test(1);
0416     idr_get_next_test(4);
0417     idr_u32_test(4);
0418     idr_u32_test(1);
0419     idr_u32_test(0);
0420     idr_align_test(&idr);
0421     idr_find_test();
0422 }
0423
0424 #define module_init(x)
0425 #define module_exit(x)
0426 #define MODULE_AUTHOR(x)
0427 #define MODULE_LICENSE(x)
0428 #define dump_stack()    assert(0)
0429 void ida_dump(struct ida *);
0430
0431 #include "../../../lib/test_ida.c"
0432
0433 /*
0434  * Check that we get the correct error when we run out of memory doing
0435  * allocations.  In userspace, GFP_NOWAIT will always fail an allocation.
0436  * The first test is for not having a bitmap available, and the second test
0437  * is for not being able to allocate a level of the radix tree.
0438  */
0439 void ida_check_nomem(void)
0440 {
0441     DEFINE_IDA(ida);
0442     int id;
0443
0444     id = ida_alloc_min(&ida, 256, GFP_NOWAIT);
0445     IDA_BUG_ON(&ida, id != -ENOMEM);
0446     id = ida_alloc_min(&ida, 1UL << 30, GFP_NOWAIT);
0447     IDA_BUG_ON(&ida, id != -ENOMEM);
0448     IDA_BUG_ON(&ida, !ida_is_empty(&ida));
0449 }
0450
0451 /*
0452  * Check handling of conversions between exceptional entries and full bitmaps.
0453  */
0454 void ida_check_conv_user(void)
0455 {
0456     DEFINE_IDA(ida);
0457     unsigned long i;
0458
0459     for (i = 0; i < 1000000; i++) {
0460         int id = ida_alloc(&ida, GFP_NOWAIT);
0461         if (id == -ENOMEM) {
0462             IDA_BUG_ON(&ida, ((i % IDA_BITMAP_BITS) !=
0463                       BITS_PER_XA_VALUE) &&
0464                      ((i % IDA_BITMAP_BITS) != 0));
0465             id = ida_alloc(&ida, GFP_KERNEL);
0466         } else {
0467             IDA_BUG_ON(&ida, (i % IDA_BITMAP_BITS) ==
0468                     BITS_PER_XA_VALUE);
0469         }
0470         IDA_BUG_ON(&ida, id != i);
0471     }
0472     ida_destroy(&ida);
0473 }
0474
0475 void ida_check_random(void)
0476 {
0477     DEFINE_IDA(ida);
0478     DECLARE_BITMAP(bitmap, 2048);
0479     unsigned int i;
0480     time_t s = time(NULL);
0481
0482  repeat:
0483     memset(bitmap, 0, sizeof(bitmap));
0484     for (i = 0; i < 100000; i++) {
0485         int i = rand();
0486         int bit = i & 2047;
0487         if (test_bit(bit, bitmap)) {
0488             __clear_bit(bit, bitmap);
0489             ida_free(&ida, bit);
0490         } else {
0491             __set_bit(bit, bitmap);
0492             IDA_BUG_ON(&ida, ida_alloc_min(&ida, bit, GFP_KERNEL)
0493                     != bit);
0494         }
0495     }
0496     ida_destroy(&ida);
0497     if (time(NULL) < s + 10)
0498         goto repeat;
0499 }
0500
0501 void ida_simple_get_remove_test(void)
0502 {
0503     DEFINE_IDA(ida);
0504     unsigned long i;
0505
0506     for (i = 0; i < 10000; i++) {
0507         assert(ida_simple_get(&ida, 0, 20000, GFP_KERNEL) == i);
0508     }
0509     assert(ida_simple_get(&ida, 5, 30, GFP_KERNEL) < 0);
0510
0511     for (i = 0; i < 10000; i++) {
0512         ida_simple_remove(&ida, i);
0513     }
0514     assert(ida_is_empty(&ida));
0515
0516     ida_destroy(&ida);
0517 }
0518
0519 void user_ida_checks(void)
0520 {
0521     radix_tree_cpu_dead(1);
0522
0523     ida_check_nomem();
0524     ida_check_conv_user();
0525     ida_check_random();
0526     ida_simple_get_remove_test();
0527
0528     radix_tree_cpu_dead(1);
0529 }
0530
0531 static void *ida_random_fn(void *arg)
0532 {
0533     rcu_register_thread();
0534     ida_check_random();
0535     rcu_unregister_thread();
0536     return NULL;
0537 }
0538
0539 static void *ida_leak_fn(void *arg)
0540 {
0541     struct ida *ida = arg;
0542     time_t s = time(NULL);
0543     int i, ret;
0544
0545     rcu_register_thread();
0546
0547     do for (i = 0; i < 1000; i++) {
0548         ret = ida_alloc_range(ida, 128, 128, GFP_KERNEL);
0549         if (ret >= 0)
0550             ida_free(ida, 128);
0551     } while (time(NULL) < s + 2);
0552
0553     rcu_unregister_thread();
0554     return NULL;
0555 }
0556
0557 void ida_thread_tests(void)
0558 {
0559     DEFINE_IDA(ida);
0560     pthread_t threads[20];
0561     int i;
0562
0563     for (i = 0; i < ARRAY_SIZE(threads); i++)
0564         if (pthread_create(&threads[i], NULL, ida_random_fn, NULL)) {
0565             perror("creating ida thread");
0566             exit(1);
0567         }
0568
0569     while (i--)
0570         pthread_join(threads[i], NULL);
0571
0572     for (i = 0; i < ARRAY_SIZE(threads); i++)
0573         if (pthread_create(&threads[i], NULL, ida_leak_fn, &ida)) {
0574             perror("creating ida thread");
0575             exit(1);
0576         }
0577
0578     while (i--)
0579         pthread_join(threads[i], NULL);
0580     assert(ida_is_empty(&ida));
0581 }
0582
0583 void ida_tests(void)
0584 {
0585     user_ida_checks();
0586     ida_checks();
0587     ida_exit();
0588     ida_thread_tests();
0589 }
0590
0591 int __weak main(void)
0592 {
0593     rcu_register_thread();
0594     radix_tree_init();
0595     idr_checks();
0596     ida_tests();
0597     radix_tree_cpu_dead(1);
0598     rcu_barrier();
0599     if (nr_allocated)
0600         printf("nr_allocated = %d\n", nr_allocated);
0601     rcu_unregister_thread();
0602     return 0;
0603 }