tools/testing/radix-tree/idr-test.c

   1 /*
   2  * idr-test.c: Test the IDR API
   3  * Copyright (c) 2016 Matthew Wilcox <willy@infradead.org>
   4  *
   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.
   8  *
   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
  12  * more details.
  13  */
  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>
  19
  20 #include "test.h"
  21
  22 #define DUMMY_PTR       ((void *)0x12)
  23
  24 int item_idr_free(int id, void *p, void *data)
  25 {
  26         struct item *item = p;
  27         assert(item->index == id);
  28         free(p);
  29
  30         return 0;
  31 }
  32
  33 void item_idr_remove(struct idr *idr, int id)
  34 {
  35         struct item *item = idr_find(idr, id);
  36         assert(item->index == id);
  37         idr_remove(idr, id);
  38         free(item);
  39 }
  40
  41 void idr_alloc_test(void)
  42 {
  43         unsigned long i;
  44         DEFINE_IDR(idr);
  45
  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);
  49         idr_remove(&idr, 0);
  50
  51         for (i = 0x3ffe; i < 0x4003; i++) {
  52                 int id;
  53                 struct item *item;
  54
  55                 if (i < 0x4000)
  56                         item = item_create(i, 0);
  57                 else
  58                         item = item_create(i - 0x3fff, 0);
  59
  60                 id = idr_alloc_cyclic(&idr, item, 1, 0x4000, GFP_KERNEL);
  61                 assert(id == item->index);
  62         }
  63
  64         idr_for_each(&idr, item_idr_free, &idr);
  65         idr_destroy(&idr);
  66 }
  67
  68 void idr_replace_test(void)
  69 {
  70         DEFINE_IDR(idr);
  71
  72         idr_alloc(&idr, (void *)-1, 10, 11, GFP_KERNEL);
  73         idr_replace(&idr, &idr, 10);
  74
  75         idr_destroy(&idr);
  76 }
  77
  78 /*
  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
  82  * users want.
  83  */
  84 void idr_null_test(void)
  85 {
  86         int i;
  87         DEFINE_IDR(idr);
  88
  89         assert(idr_is_empty(&idr));
  90
  91         assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 0);
  92         assert(!idr_is_empty(&idr));
  93         idr_remove(&idr, 0);
  94         assert(idr_is_empty(&idr));
  95
  96         assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 0);
  97         assert(!idr_is_empty(&idr));
  98         idr_destroy(&idr);
  99         assert(idr_is_empty(&idr));
 100
 101         for (i = 0; i < 10; i++) {
 102                 assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == i);
 103         }
 104
 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));
 109         idr_remove(&idr, 5);
 110         assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == 5);
 111         idr_remove(&idr, 5);
 112
 113         for (i = 0; i < 9; i++) {
 114                 idr_remove(&idr, i);
 115                 assert(!idr_is_empty(&idr));
 116         }
 117         idr_remove(&idr, 8);
 118         assert(!idr_is_empty(&idr));
 119         idr_remove(&idr, 9);
 120         assert(idr_is_empty(&idr));
 121
 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);
 126
 127         idr_destroy(&idr);
 128         assert(idr_is_empty(&idr));
 129
 130         for (i = 1; i < 10; i++) {
 131                 assert(idr_alloc(&idr, NULL, 1, 0, GFP_KERNEL) == i);
 132         }
 133
 134         idr_destroy(&idr);
 135         assert(idr_is_empty(&idr));
 136 }
 137
 138 void idr_nowait_test(void)
 139 {
 140         unsigned int i;
 141         DEFINE_IDR(idr);
 142
 143         idr_preload(GFP_KERNEL);
 144
 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);
 148         }
 149
 150         idr_preload_end();
 151
 152         idr_for_each(&idr, item_idr_free, &idr);
 153         idr_destroy(&idr);
 154 }
 155
 156 void idr_checks(void)
 157 {
 158         unsigned long i;
 159         DEFINE_IDR(idr);
 160
 161         for (i = 0; i < 10000; i++) {
 162                 struct item *item = item_create(i, 0);
 163                 assert(idr_alloc(&idr, item, 0, 20000, GFP_KERNEL) == i);
 164         }
 165
 166         assert(idr_alloc(&idr, DUMMY_PTR, 5, 30, GFP_KERNEL) < 0);
 167
 168         for (i = 0; i < 5000; i++)
 169                 item_idr_remove(&idr, i);
 170
 171         idr_remove(&idr, 3);
 172
 173         idr_for_each(&idr, item_idr_free, &idr);
 174         idr_destroy(&idr);
 175
 176         assert(idr_is_empty(&idr));
 177
 178         idr_remove(&idr, 3);
 179         idr_remove(&idr, 0);
 180
 181         for (i = INT_MAX - 3UL; i < INT_MAX + 1UL; i++) {
 182                 struct item *item = item_create(i, 0);
 183                 assert(idr_alloc(&idr, item, i, i + 10, GFP_KERNEL) == i);
 184         }
 185         assert(idr_alloc(&idr, DUMMY_PTR, i - 2, i, GFP_KERNEL) == -ENOSPC);
 186
 187         idr_for_each(&idr, item_idr_free, &idr);
 188         idr_destroy(&idr);
 189         idr_destroy(&idr);
 190
 191         assert(idr_is_empty(&idr));
 192
 193         for (i = 1; i < 10000; i++) {
 194                 struct item *item = item_create(i, 0);
 195                 assert(idr_alloc(&idr, item, 1, 20000, GFP_KERNEL) == i);
 196         }
 197
 198         idr_for_each(&idr, item_idr_free, &idr);
 199         idr_destroy(&idr);
 200
 201         idr_replace_test();
 202         idr_alloc_test();
 203         idr_null_test();
 204         idr_nowait_test();
 205 }
 206
 207 /*
 208  * Check that we get the correct error when we run out of memory doing
 209  * allocations.  To ensure we run out of memory, just "forget" to preload.
 210  * The first test is for not having a bitmap available, and the second test
 211  * is for not being able to allocate a level of the radix tree.
 212  */
 213 void ida_check_nomem(void)
 214 {
 215         DEFINE_IDA(ida);
 216         int id, err;
 217
 218         err = ida_get_new_above(&ida, 256, &id);
 219         assert(err == -EAGAIN);
 220         err = ida_get_new_above(&ida, 1UL << 30, &id);
 221         assert(err == -EAGAIN);
 222 }
 223
 224 /*
 225  * Check what happens when we fill a leaf and then delete it.  This may
 226  * discover mishandling of IDR_FREE.
 227  */
 228 void ida_check_leaf(void)
 229 {
 230         DEFINE_IDA(ida);
 231         int id;
 232         unsigned long i;
 233
 234         for (i = 0; i < IDA_BITMAP_BITS; i++) {
 235                 assert(ida_pre_get(&ida, GFP_KERNEL));
 236                 assert(!ida_get_new(&ida, &id));
 237                 assert(id == i);
 238         }
 239
 240         ida_destroy(&ida);
 241         assert(ida_is_empty(&ida));
 242
 243         assert(ida_pre_get(&ida, GFP_KERNEL));
 244         assert(!ida_get_new(&ida, &id));
 245         assert(id == 0);
 246         ida_destroy(&ida);
 247         assert(ida_is_empty(&ida));
 248 }
 249
 250 /*
 251  * Check handling of conversions between exceptional entries and full bitmaps.
 252  */
 253 void ida_check_conv(void)
 254 {
 255         DEFINE_IDA(ida);
 256         int id;
 257         unsigned long i;
 258
 259         for (i = 0; i < IDA_BITMAP_BITS * 2; i += IDA_BITMAP_BITS) {
 260                 assert(ida_pre_get(&ida, GFP_KERNEL));
 261                 assert(!ida_get_new_above(&ida, i + 1, &id));
 262                 assert(id == i + 1);
 263                 assert(!ida_get_new_above(&ida, i + BITS_PER_LONG, &id));
 264                 assert(id == i + BITS_PER_LONG);
 265                 ida_remove(&ida, i + 1);
 266                 ida_remove(&ida, i + BITS_PER_LONG);
 267                 assert(ida_is_empty(&ida));
 268         }
 269
 270         assert(ida_pre_get(&ida, GFP_KERNEL));
 271
 272         for (i = 0; i < IDA_BITMAP_BITS * 2; i++) {
 273                 assert(ida_pre_get(&ida, GFP_KERNEL));
 274                 assert(!ida_get_new(&ida, &id));
 275                 assert(id == i);
 276         }
 277
 278         for (i = IDA_BITMAP_BITS * 2; i > 0; i--) {
 279                 ida_remove(&ida, i - 1);
 280         }
 281         assert(ida_is_empty(&ida));
 282
 283         for (i = 0; i < IDA_BITMAP_BITS + BITS_PER_LONG - 4; i++) {
 284                 assert(ida_pre_get(&ida, GFP_KERNEL));
 285                 assert(!ida_get_new(&ida, &id));
 286                 assert(id == i);
 287         }
 288
 289         for (i = IDA_BITMAP_BITS + BITS_PER_LONG - 4; i > 0; i--) {
 290                 ida_remove(&ida, i - 1);
 291         }
 292         assert(ida_is_empty(&ida));
 293
 294         radix_tree_cpu_dead(1);
 295         for (i = 0; i < 1000000; i++) {
 296                 int err = ida_get_new(&ida, &id);
 297                 if (err == -EAGAIN) {
 298                         assert((i % IDA_BITMAP_BITS) == (BITS_PER_LONG - 2));
 299                         assert(ida_pre_get(&ida, GFP_KERNEL));
 300                         err = ida_get_new(&ida, &id);
 301                 } else {
 302                         assert((i % IDA_BITMAP_BITS) != (BITS_PER_LONG - 2));
 303                 }
 304                 assert(!err);
 305                 assert(id == i);
 306         }
 307         ida_destroy(&ida);
 308 }
 309
 310 /*
 311  * Check allocations up to and slightly above the maximum allowed (2^31-1) ID.
 312  * Allocating up to 2^31-1 should succeed, and then allocating the next one
 313  * should fail.
 314  */
 315 void ida_check_max(void)
 316 {
 317         DEFINE_IDA(ida);
 318         int id, err;
 319         unsigned long i, j;
 320
 321         for (j = 1; j < 65537; j *= 2) {
 322                 unsigned long base = (1UL << 31) - j;
 323                 for (i = 0; i < j; i++) {
 324                         assert(ida_pre_get(&ida, GFP_KERNEL));
 325                         assert(!ida_get_new_above(&ida, base, &id));
 326                         assert(id == base + i);
 327                 }
 328                 assert(ida_pre_get(&ida, GFP_KERNEL));
 329                 err = ida_get_new_above(&ida, base, &id);
 330                 assert(err == -ENOSPC);
 331                 ida_destroy(&ida);
 332                 assert(ida_is_empty(&ida));
 333                 rcu_barrier();
 334         }
 335 }
 336
 337 void ida_check_random(void)
 338 {
 339         DEFINE_IDA(ida);
 340         DECLARE_BITMAP(bitmap, 2048);
 341         int id;
 342         unsigned int i;
 343         time_t s = time(NULL);
 344
 345  repeat:
 346         memset(bitmap, 0, sizeof(bitmap));
 347         for (i = 0; i < 100000; i++) {
 348                 int i = rand();
 349                 int bit = i & 2047;
 350                 if (test_bit(bit, bitmap)) {
 351                         __clear_bit(bit, bitmap);
 352                         ida_remove(&ida, bit);
 353                 } else {
 354                         __set_bit(bit, bitmap);
 355                         ida_pre_get(&ida, GFP_KERNEL);
 356                         assert(!ida_get_new_above(&ida, bit, &id));
 357                         assert(id == bit);
 358                 }
 359         }
 360         ida_destroy(&ida);
 361         if (time(NULL) < s + 10)
 362                 goto repeat;
 363 }
 364
 365 void ida_checks(void)
 366 {
 367         DEFINE_IDA(ida);
 368         int id;
 369         unsigned long i;
 370
 371         radix_tree_cpu_dead(1);
 372         ida_check_nomem();
 373
 374         for (i = 0; i < 10000; i++) {
 375                 assert(ida_pre_get(&ida, GFP_KERNEL));
 376                 assert(!ida_get_new(&ida, &id));
 377                 assert(id == i);
 378         }
 379
 380         ida_remove(&ida, 20);
 381         ida_remove(&ida, 21);
 382         for (i = 0; i < 3; i++) {
 383                 assert(ida_pre_get(&ida, GFP_KERNEL));
 384                 assert(!ida_get_new(&ida, &id));
 385                 if (i == 2)
 386                         assert(id == 10000);
 387         }
 388
 389         for (i = 0; i < 5000; i++)
 390                 ida_remove(&ida, i);
 391
 392         assert(ida_pre_get(&ida, GFP_KERNEL));
 393         assert(!ida_get_new_above(&ida, 5000, &id));
 394         assert(id == 10001);
 395
 396         ida_destroy(&ida);
 397
 398         assert(ida_is_empty(&ida));
 399
 400         assert(ida_pre_get(&ida, GFP_KERNEL));
 401         assert(!ida_get_new_above(&ida, 1, &id));
 402         assert(id == 1);
 403
 404         ida_remove(&ida, id);
 405         assert(ida_is_empty(&ida));
 406         ida_destroy(&ida);
 407         assert(ida_is_empty(&ida));
 408
 409         assert(ida_pre_get(&ida, GFP_KERNEL));
 410         assert(!ida_get_new_above(&ida, 1, &id));
 411         ida_destroy(&ida);
 412         assert(ida_is_empty(&ida));
 413
 414         assert(ida_pre_get(&ida, GFP_KERNEL));
 415         assert(!ida_get_new_above(&ida, 1, &id));
 416         assert(id == 1);
 417         assert(ida_pre_get(&ida, GFP_KERNEL));
 418         assert(!ida_get_new_above(&ida, 1025, &id));
 419         assert(id == 1025);
 420         assert(ida_pre_get(&ida, GFP_KERNEL));
 421         assert(!ida_get_new_above(&ida, 10000, &id));
 422         assert(id == 10000);
 423         ida_remove(&ida, 1025);
 424         ida_destroy(&ida);
 425         assert(ida_is_empty(&ida));
 426
 427         ida_check_leaf();
 428         ida_check_max();
 429         ida_check_conv();
 430         ida_check_random();
 431
 432         radix_tree_cpu_dead(1);
 433 }
 434
 435 int __weak main(void)
 436 {
 437         radix_tree_init();
 438         idr_checks();
 439         ida_checks();
 440         rcu_barrier();
 441         if (nr_allocated)
 442                 printf("nr_allocated = %d\n", nr_allocated);
 443         return 0;
 444 }