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 /*
 193  * Check ida_find_first_range() and varriants.
 194  */
 195 static void ida_check_find_first(struct ida *ida)
 196 {
 197         /* IDA is empty; all of the below should be not exist */
 198         IDA_BUG_ON(ida, ida_exists(ida, 0));
 199         IDA_BUG_ON(ida, ida_exists(ida, 3));
 200         IDA_BUG_ON(ida, ida_exists(ida, 63));
 201         IDA_BUG_ON(ida, ida_exists(ida, 1023));
 202         IDA_BUG_ON(ida, ida_exists(ida, (1 << 20) - 1));
 203
 204         /* IDA contains a single value entry */
 205         IDA_BUG_ON(ida, ida_alloc_min(ida, 3, GFP_KERNEL) != 3);
 206         IDA_BUG_ON(ida, ida_exists(ida, 0));
 207         IDA_BUG_ON(ida, !ida_exists(ida, 3));
 208         IDA_BUG_ON(ida, ida_exists(ida, 63));
 209         IDA_BUG_ON(ida, ida_exists(ida, 1023));
 210         IDA_BUG_ON(ida, ida_exists(ida, (1 << 20) - 1));
 211
 212         IDA_BUG_ON(ida, ida_alloc_min(ida, 63, GFP_KERNEL) != 63);
 213         IDA_BUG_ON(ida, ida_exists(ida, 0));
 214         IDA_BUG_ON(ida, !ida_exists(ida, 3));
 215         IDA_BUG_ON(ida, !ida_exists(ida, 63));
 216         IDA_BUG_ON(ida, ida_exists(ida, 1023));
 217         IDA_BUG_ON(ida, ida_exists(ida, (1 << 20) - 1));
 218
 219         /* IDA contains a single bitmap */
 220         IDA_BUG_ON(ida, ida_alloc_min(ida, 1023, GFP_KERNEL) != 1023);
 221         IDA_BUG_ON(ida, ida_exists(ida, 0));
 222         IDA_BUG_ON(ida, !ida_exists(ida, 3));
 223         IDA_BUG_ON(ida, !ida_exists(ida, 63));
 224         IDA_BUG_ON(ida, !ida_exists(ida, 1023));
 225         IDA_BUG_ON(ida, ida_exists(ida, (1 << 20) - 1));
 226
 227         /* IDA contains a tree */
 228         IDA_BUG_ON(ida, ida_alloc_min(ida, (1 << 20) - 1, GFP_KERNEL) != (1 << 20) - 1);
 229         IDA_BUG_ON(ida, ida_exists(ida, 0));
 230         IDA_BUG_ON(ida, !ida_exists(ida, 3));
 231         IDA_BUG_ON(ida, !ida_exists(ida, 63));
 232         IDA_BUG_ON(ida, !ida_exists(ida, 1023));
 233         IDA_BUG_ON(ida, !ida_exists(ida, (1 << 20) - 1));
 234
 235         /* Now try to find first */
 236         IDA_BUG_ON(ida, ida_find_first(ida) != 3);
 237         IDA_BUG_ON(ida, ida_find_first_range(ida, -1, 2) != -EINVAL);
 238         IDA_BUG_ON(ida, ida_find_first_range(ida, 0, 2) != -ENOENT); // no used ID
 239         IDA_BUG_ON(ida, ida_find_first_range(ida, 0, 3) != 3);
 240         IDA_BUG_ON(ida, ida_find_first_range(ida, 1, 3) != 3);
 241         IDA_BUG_ON(ida, ida_find_first_range(ida, 3, 3) != 3);
 242         IDA_BUG_ON(ida, ida_find_first_range(ida, 2, 4) != 3);
 243         IDA_BUG_ON(ida, ida_find_first_range(ida, 4, 3) != -ENOENT); // min > max, fail
 244         IDA_BUG_ON(ida, ida_find_first_range(ida, 4, 60) != -ENOENT); // no used ID
 245         IDA_BUG_ON(ida, ida_find_first_range(ida, 4, 64) != 63);
 246         IDA_BUG_ON(ida, ida_find_first_range(ida, 63, 63) != 63);
 247         IDA_BUG_ON(ida, ida_find_first_range(ida, 64, 1026) != 1023);
 248         IDA_BUG_ON(ida, ida_find_first_range(ida, 1023, 1023) != 1023);
 249         IDA_BUG_ON(ida, ida_find_first_range(ida, 1023, (1 << 20) - 1) != 1023);
 250         IDA_BUG_ON(ida, ida_find_first_range(ida, 1024, (1 << 20) - 1) != (1 << 20) - 1);
 251         IDA_BUG_ON(ida, ida_find_first_range(ida, (1 << 20), INT_MAX) != -ENOENT);
 252
 253         ida_free(ida, 3);
 254         ida_free(ida, 63);
 255         ida_free(ida, 1023);
 256         ida_free(ida, (1 << 20) - 1);
 257
 258         IDA_BUG_ON(ida, !ida_is_empty(ida));
 259 }
 260
 261 static DEFINE_IDA(ida);
 262
 263 static int ida_checks(void)
 264 {
 265         IDA_BUG_ON(&ida, !ida_is_empty(&ida));
 266         ida_check_alloc(&ida);
 267         ida_check_destroy(&ida);
 268         ida_check_leaf(&ida, 0);
 269         ida_check_leaf(&ida, 1024);
 270         ida_check_leaf(&ida, 1024 * 64);
 271         ida_check_max(&ida);
 272         ida_check_conv(&ida);
 273         ida_check_bad_free(&ida);
 274         ida_check_find_first(&ida);
 275
 276         printk("IDA: %u of %u tests passed\n", tests_passed, tests_run);
 277         return (tests_run != tests_passed) ? 0 : -EINVAL;
 278 }
 279
 280 static void ida_exit(void)
 281 {
 282 }
 283
 284 module_init(ida_checks);
 285 module_exit(ida_exit);
 286 MODULE_AUTHOR("Matthew Wilcox <willy@infradead.org>");
 287 MODULE_DESCRIPTION("Test the IDA API");
 288 MODULE_LICENSE("GPL");