lib/test_ida.c

   1 // SPDX-License-Identifier: GPL-2.0+
   2 /*
   3  * test_ida.c: Test the IDA API
   4  * Copyright (c) 2016-2018 Microsoft Corporation
   5  * Copyright (c) 2018 Oracle Corporation
   6  * Author: Matthew Wilcox <willy@infradead.org>
   7  */
   8
   9 #include <linux/idr.h>
  10 #include <linux/module.h>
  11
  12 static unsigned int tests_run;
  13 static unsigned int tests_passed;
  14
  15 #ifdef __KERNEL__
  16 static void ida_dump(struct ida *ida) { }
  17 #endif
  18 #define IDA_BUG_ON(ida, x) do {                                         \
  19         tests_run++;                                                    \
  20         if (x) {                                                        \
  21                 ida_dump(ida);                                          \
  22                 dump_stack();                                           \
  23         } else {                                                        \
  24                 tests_passed++;                                         \
  25         }                                                               \
  26 } while (0)
  27
  28 /*
  29  * Straightforward checks that allocating and freeing IDs work.
  30  */
  31 static void ida_check_alloc(struct ida *ida)
  32 {
  33         int i, id;
  34
  35         for (i = 0; i < 10000; i++)
  36                 IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != i);
  37
  38         ida_free(ida, 20);
  39         ida_free(ida, 21);
  40         for (i = 0; i < 3; i++) {
  41                 id = ida_alloc(ida, GFP_KERNEL);
  42                 IDA_BUG_ON(ida, id < 0);
  43                 if (i == 2)
  44                         IDA_BUG_ON(ida, id != 10000);
  45         }
  46
  47         for (i = 0; i < 5000; i++)
  48                 ida_free(ida, i);
  49
  50         IDA_BUG_ON(ida, ida_alloc_min(ida, 5000, GFP_KERNEL) != 10001);
  51         ida_destroy(ida);
  52
  53         IDA_BUG_ON(ida, !ida_is_empty(ida));
  54 }
  55
  56 /* Destroy an IDA with a single entry at @base */
  57 static void ida_check_destroy_1(struct ida *ida, unsigned int base)
  58 {
  59         IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) != base);
  60         IDA_BUG_ON(ida, ida_is_empty(ida));
  61         ida_destroy(ida);
  62         IDA_BUG_ON(ida, !ida_is_empty(ida));
  63 }
  64
  65 /* Check that ida_destroy and ida_is_empty work */
  66 static void ida_check_destroy(struct ida *ida)
  67 {
  68         /* Destroy an already-empty IDA */
  69         IDA_BUG_ON(ida, !ida_is_empty(ida));
  70         ida_destroy(ida);
  71         IDA_BUG_ON(ida, !ida_is_empty(ida));
  72
  73         ida_check_destroy_1(ida, 0);
  74         ida_check_destroy_1(ida, 1);
  75         ida_check_destroy_1(ida, 1023);
  76         ida_check_destroy_1(ida, 1024);
  77         ida_check_destroy_1(ida, 12345678);
  78 }
  79
  80 /*
  81  * Check what happens when we fill a leaf and then delete it.  This may
  82  * discover mishandling of IDR_FREE.
  83  */
  84 static void ida_check_leaf(struct ida *ida, unsigned int base)
  85 {
  86         unsigned long i;
  87
  88         for (i = 0; i < IDA_BITMAP_BITS; i++) {
  89                 IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) !=
  90                                 base + i);
  91         }
  92
  93         ida_destroy(ida);
  94         IDA_BUG_ON(ida, !ida_is_empty(ida));
  95
  96         IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != 0);
  97         IDA_BUG_ON(ida, ida_is_empty(ida));
  98         ida_free(ida, 0);
  99         IDA_BUG_ON(ida, !ida_is_empty(ida));
 100 }
 101
 102 /*
 103  * Check allocations up to and slightly above the maximum allowed (2^31-1) ID.
 104  * Allocating up to 2^31-1 should succeed, and then allocating the next one
 105  * should fail.
 106  */
 107 static void ida_check_max(struct ida *ida)
 108 {
 109         unsigned long i, j;
 110
 111         for (j = 1; j < 65537; j *= 2) {
 112                 unsigned long base = (1UL << 31) - j;
 113                 for (i = 0; i < j; i++) {
 114                         IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) !=
 115                                         base + i);
 116                 }
 117                 IDA_BUG_ON(ida, ida_alloc_min(ida, base, GFP_KERNEL) !=
 118                                 -ENOSPC);
 119                 ida_destroy(ida);
 120                 IDA_BUG_ON(ida, !ida_is_empty(ida));
 121         }
 122 }
 123
 124 /*
 125  * Check handling of conversions between exceptional entries and full bitmaps.
 126  */
 127 static void ida_check_conv(struct ida *ida)
 128 {
 129         unsigned long i;
 130
 131         for (i = 0; i < IDA_BITMAP_BITS * 2; i += IDA_BITMAP_BITS) {
 132                 IDA_BUG_ON(ida, ida_alloc_min(ida, i + 1, GFP_KERNEL) != i + 1);
 133                 IDA_BUG_ON(ida, ida_alloc_min(ida, i + BITS_PER_LONG,
 134                                         GFP_KERNEL) != i + BITS_PER_LONG);
 135                 ida_free(ida, i + 1);
 136                 ida_free(ida, i + BITS_PER_LONG);
 137                 IDA_BUG_ON(ida, !ida_is_empty(ida));
 138         }
 139
 140         for (i = 0; i < IDA_BITMAP_BITS * 2; i++)
 141                 IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != i);
 142         for (i = IDA_BITMAP_BITS * 2; i > 0; i--)
 143                 ida_free(ida, i - 1);
 144         IDA_BUG_ON(ida, !ida_is_empty(ida));
 145
 146         for (i = 0; i < IDA_BITMAP_BITS + BITS_PER_LONG - 4; i++)
 147                 IDA_BUG_ON(ida, ida_alloc(ida, GFP_KERNEL) != i);
 148         for (i = IDA_BITMAP_BITS + BITS_PER_LONG - 4; i > 0; i--)
 149                 ida_free(ida, i - 1);
 150         IDA_BUG_ON(ida, !ida_is_empty(ida));
 151 }
 152
 153 /*
 154  * Check various situations where we attempt to free an ID we don't own.
 155  */
 156 static void ida_check_bad_free(struct ida *ida)
 157 {
 158         unsigned long i;
 159
 160         printk("vvv Ignore \"not allocated\" warnings\n");
 161         /* IDA is empty; all of these will fail */
 162         ida_free(ida, 0);
 163         for (i = 0; i < 31; i++)
 164                 ida_free(ida, 1 << i);
 165
 166         /* IDA contains a single value entry */
 167         IDA_BUG_ON(ida, ida_alloc_min(ida, 3, GFP_KERNEL) != 3);
 168         ida_free(ida, 0);
 169         for (i = 0; i < 31; i++)
 170                 ida_free(ida, 1 << i);
 171
 172         /* IDA contains a single bitmap */
 173         IDA_BUG_ON(ida, ida_alloc_min(ida, 1023, GFP_KERNEL) != 1023);
 174         ida_free(ida, 0);
 175         for (i = 0; i < 31; i++)
 176                 ida_free(ida, 1 << i);
 177
 178         /* IDA contains a tree */
 179         IDA_BUG_ON(ida, ida_alloc_min(ida, (1 << 20) - 1, GFP_KERNEL) != (1 << 20) - 1);
 180         ida_free(ida, 0);
 181         for (i = 0; i < 31; i++)
 182                 ida_free(ida, 1 << i);
 183         printk("^^^ \"not allocated\" warnings over\n");
 184
 185         ida_free(ida, 3);
 186         ida_free(ida, 1023);
 187         ida_free(ida, (1 << 20) - 1);
 188
 189         IDA_BUG_ON(ida, !ida_is_empty(ida));
 190 }
 191
 192 static DEFINE_IDA(ida);
 193
 194 static int ida_checks(void)
 195 {
 196         IDA_BUG_ON(&ida, !ida_is_empty(&ida));
 197         ida_check_alloc(&ida);
 198         ida_check_destroy(&ida);
 199         ida_check_leaf(&ida, 0);
 200         ida_check_leaf(&ida, 1024);
 201         ida_check_leaf(&ida, 1024 * 64);
 202         ida_check_max(&ida);
 203         ida_check_conv(&ida);
 204         ida_check_bad_free(&ida);
 205
 206         printk("IDA: %u of %u tests passed\n", tests_passed, tests_run);
 207         return (tests_run != tests_passed) ? 0 : -EINVAL;
 208 }
 209
 210 static void ida_exit(void)
 211 {
 212 }
 213
 214 module_init(ida_checks);
 215 module_exit(ida_exit);
 216 MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>");
 217 MODULE_LICENSE("GPL");