the-tree/lib/test_ida.c

0001 // SPDX-License-Identifier: GPL-2.0+
0002 /*
0003  * test_ida.c: Test the IDA API
0004  * Copyright (c) 2016-2018 Microsoft Corporation
0005  * Copyright (c) 2018 Oracle Corporation
0006  * Author: Matthew Wilcox <willy@infradead.org>
0007  */
0008
0009 #include <linux/idr.h>
0010 #include <linux/module.h>
0011
0012 static unsigned int tests_run;
0013 static unsigned int tests_passed;
0014
0015 #ifdef __KERNEL__
0016 void ida_dump(struct ida *ida) { }
0017 #endif
0018 #define IDA_BUG_ON(ida, x) do {                     \
0019     tests_run++;                            \
0020     if (x) {                            \
0021         ida_dump(ida);                      \
0022         dump_stack();                       \
0023     } else {                            \
0024         tests_passed++;                     \
0025     }                               \
0026 } while (0)
0027
0028 /*
0029  * Straightforward checks that allocating and freeing IDs work.
0030  */
0031 static void ida_check_alloc(struct ida *ida)
0032 {
0033     int i, id;
0034
0035     for (i = 0; i < 10000; i++)
0036         IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != i);
0037
0038     ida_free(ida, 20);
0039     ida_free(ida, 21);
0040     for (i = 0; i < 3; i++) {
0041         id = ida_alloc(ida, GFP_KERNEL);
0042         IDA_BUG_ON(ida, id < 0);
0043         if (i == 2)
0044             IDA_BUG_ON(ida, id != 10000);
0045     }
0046
0047     for (i = 0; i < 5000; i++)
0048         ida_free(ida, i);
0049
0050     IDA_BUG_ON(ida, ida_alloc_min(ida, 5000, GFP_KERNEL) != 10001);
0051     ida_destroy(ida);
0052
0053     IDA_BUG_ON(ida, !ida_is_empty(ida));
0054 }
0055
0056 /* Destroy an IDA with a single entry at @base */
0057 static void ida_check_destroy_1(struct ida *ida, unsigned int base)
0058 {
0059     IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) != base);
0060     IDA_BUG_ON(ida, ida_is_empty(ida));
0061     ida_destroy(ida);
0062     IDA_BUG_ON(ida, !ida_is_empty(ida));
0063 }
0064
0065 /* Check that ida_destroy and ida_is_empty work */
0066 static void ida_check_destroy(struct ida *ida)
0067 {
0068     /* Destroy an already-empty IDA */
0069     IDA_BUG_ON(ida, !ida_is_empty(ida));
0070     ida_destroy(ida);
0071     IDA_BUG_ON(ida, !ida_is_empty(ida));
0072
0073     ida_check_destroy_1(ida, 0);
0074     ida_check_destroy_1(ida, 1);
0075     ida_check_destroy_1(ida, 1023);
0076     ida_check_destroy_1(ida, 1024);
0077     ida_check_destroy_1(ida, 12345678);
0078 }
0079
0080 /*
0081  * Check what happens when we fill a leaf and then delete it.  This may
0082  * discover mishandling of IDR_FREE.
0083  */
0084 static void ida_check_leaf(struct ida *ida, unsigned int base)
0085 {
0086     unsigned long i;
0087
0088     for (i = 0; i < IDA_BITMAP_BITS; i++) {
0089         IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) !=
0090                 base + i);
0091     }
0092
0093     ida_destroy(ida);
0094     IDA_BUG_ON(ida, !ida_is_empty(ida));
0095
0096     IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != 0);
0097     IDA_BUG_ON(ida, ida_is_empty(ida));
0098     ida_free(ida, 0);
0099     IDA_BUG_ON(ida, !ida_is_empty(ida));
0100 }
0101
0102 /*
0103  * Check allocations up to and slightly above the maximum allowed (2^31-1) ID.
0104  * Allocating up to 2^31-1 should succeed, and then allocating the next one
0105  * should fail.
0106  */
0107 static void ida_check_max(struct ida *ida)
0108 {
0109     unsigned long i, j;
0110
0111     for (j = 1; j < 65537; j *= 2) {
0112         unsigned long base = (1UL << 31) - j;
0113         for (i = 0; i < j; i++) {
0114             IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) !=
0115                     base + i);
0116         }
0117         IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) !=
0118                 -ENOSPC);
0119         ida_destroy(ida);
0120         IDA_BUG_ON(ida, !ida_is_empty(ida));
0121     }
0122 }
0123
0124 /*
0125  * Check handling of conversions between exceptional entries and full bitmaps.
0126  */
0127 static void ida_check_conv(struct ida *ida)
0128 {
0129     unsigned long i;
0130
0131     for (i = 0; i < IDA_BITMAP_BITS * 2; i += IDA_BITMAP_BITS) {
0132         IDA_BUG_ON(ida, ida_alloc_min(ida, i + 1, GFP_KERNEL) != i + 1);
0133         IDA_BUG_ON(ida, ida_alloc_min(ida, i + BITS_PER_LONG,
0134                     GFP_KERNEL) != i + BITS_PER_LONG);
0135         ida_free(ida, i + 1);
0136         ida_free(ida, i + BITS_PER_LONG);
0137         IDA_BUG_ON(ida, !ida_is_empty(ida));
0138     }
0139
0140     for (i = 0; i < IDA_BITMAP_BITS * 2; i++)
0141         IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != i);
0142     for (i = IDA_BITMAP_BITS * 2; i > 0; i--)
0143         ida_free(ida, i - 1);
0144     IDA_BUG_ON(ida, !ida_is_empty(ida));
0145
0146     for (i = 0; i < IDA_BITMAP_BITS + BITS_PER_LONG - 4; i++)
0147         IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != i);
0148     for (i = IDA_BITMAP_BITS + BITS_PER_LONG - 4; i > 0; i--)
0149         ida_free(ida, i - 1);
0150     IDA_BUG_ON(ida, !ida_is_empty(ida));
0151 }
0152
0153 static DEFINE_IDA(ida);
0154
0155 static int ida_checks(void)
0156 {
0157     IDA_BUG_ON(&ida, !ida_is_empty(&ida));
0158     ida_check_alloc(&ida);
0159     ida_check_destroy(&ida);
0160     ida_check_leaf(&ida, 0);
0161     ida_check_leaf(&ida, 1024);
0162     ida_check_leaf(&ida, 1024 * 64);
0163     ida_check_max(&ida);
0164     ida_check_conv(&ida);
0165
0166     printk("IDA: %u of %u tests passed\n", tests_passed, tests_run);
0167     return (tests_run != tests_passed) ? 0 : -EINVAL;
0168 }
0169
0170 static void ida_exit(void)
0171 {
0172 }
0173
0174 module_init(ida_checks);
0175 module_exit(ida_exit);
0176 MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>");
0177 MODULE_LICENSE("GPL");