tools/testing/radix-tree/multiorder.c

   1 /*
   2  * multiorder.c: Multi-order radix tree entry testing
   3  * Copyright (c) 2016 Intel Corporation
   4  * Author: Ross Zwisler <ross.zwisler@linux.intel.com>
   5  * Author: Matthew Wilcox <matthew.r.wilcox@intel.com>
   6  *
   7  * This program is free software; you can redistribute it and/or modify it
   8  * under the terms and conditions of the GNU General Public License,
   9  * version 2, as published by the Free Software Foundation.
  10  *
  11  * This program is distributed in the hope it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
  14  * more details.
  15  */
  16 #include <linux/radix-tree.h>
  17 #include <linux/slab.h>
  18 #include <linux/errno.h>
  19 #include <pthread.h>
  20
  21 #include "test.h"
  22
  23 #define for_each_index(i, base, order) \
  24         for (i = base; i < base + (1 << order); i++)
  25
  26 static void __multiorder_tag_test(int index, int order)
  27 {
  28         RADIX_TREE(tree, GFP_KERNEL);
  29         int base, err, i;
  30
  31         /* our canonical entry */
  32         base = index & ~((1 << order) - 1);
  33
  34         printv(2, "Multiorder tag test with index %d, canonical entry %d\n",
  35                         index, base);
  36
  37         err = item_insert_order(&tree, index, order);
  38         assert(!err);
  39
  40         /*
  41          * Verify we get collisions for covered indices.  We try and fail to
  42          * insert an exceptional entry so we don't leak memory via
  43          * item_insert_order().
  44          */
  45         for_each_index(i, base, order) {
  46                 err = __radix_tree_insert(&tree, i, order,
  47                                 (void *)(0xA0 | RADIX_TREE_EXCEPTIONAL_ENTRY));
  48                 assert(err == -EEXIST);
  49         }
  50
  51         for_each_index(i, base, order) {
  52                 assert(!radix_tree_tag_get(&tree, i, 0));
  53                 assert(!radix_tree_tag_get(&tree, i, 1));
  54         }
  55
  56         assert(radix_tree_tag_set(&tree, index, 0));
  57
  58         for_each_index(i, base, order) {
  59                 assert(radix_tree_tag_get(&tree, i, 0));
  60                 assert(!radix_tree_tag_get(&tree, i, 1));
  61         }
  62
  63         assert(tag_tagged_items(&tree, NULL, 0, ~0UL, 10, 0, 1) == 1);
  64         assert(radix_tree_tag_clear(&tree, index, 0));
  65
  66         for_each_index(i, base, order) {
  67                 assert(!radix_tree_tag_get(&tree, i, 0));
  68                 assert(radix_tree_tag_get(&tree, i, 1));
  69         }
  70
  71         assert(radix_tree_tag_clear(&tree, index, 1));
  72
  73         assert(!radix_tree_tagged(&tree, 0));
  74         assert(!radix_tree_tagged(&tree, 1));
  75
  76         item_kill_tree(&tree);
  77 }
  78
  79 static void __multiorder_tag_test2(unsigned order, unsigned long index2)
  80 {
  81         RADIX_TREE(tree, GFP_KERNEL);
  82         unsigned long index = (1 << order);
  83         index2 += index;
  84
  85         assert(item_insert_order(&tree, 0, order) == 0);
  86         assert(item_insert(&tree, index2) == 0);
  87
  88         assert(radix_tree_tag_set(&tree, 0, 0));
  89         assert(radix_tree_tag_set(&tree, index2, 0));
  90
  91         assert(tag_tagged_items(&tree, NULL, 0, ~0UL, 10, 0, 1) == 2);
  92
  93         item_kill_tree(&tree);
  94 }
  95
  96 static void multiorder_tag_tests(void)
  97 {
  98         int i, j;
  99
 100         /* test multi-order entry for indices 0-7 with no sibling pointers */
 101         __multiorder_tag_test(0, 3);
 102         __multiorder_tag_test(5, 3);
 103
 104         /* test multi-order entry for indices 8-15 with no sibling pointers */
 105         __multiorder_tag_test(8, 3);
 106         __multiorder_tag_test(15, 3);
 107
 108         /*
 109          * Our order 5 entry covers indices 0-31 in a tree with height=2.
 110          * This is broken up as follows:
 111          * 0-7:         canonical entry
 112          * 8-15:        sibling 1
 113          * 16-23:       sibling 2
 114          * 24-31:       sibling 3
 115          */
 116         __multiorder_tag_test(0, 5);
 117         __multiorder_tag_test(29, 5);
 118
 119         /* same test, but with indices 32-63 */
 120         __multiorder_tag_test(32, 5);
 121         __multiorder_tag_test(44, 5);
 122
 123         /*
 124          * Our order 8 entry covers indices 0-255 in a tree with height=3.
 125          * This is broken up as follows:
 126          * 0-63:        canonical entry
 127          * 64-127:      sibling 1
 128          * 128-191:     sibling 2
 129          * 192-255:     sibling 3
 130          */
 131         __multiorder_tag_test(0, 8);
 132         __multiorder_tag_test(190, 8);
 133
 134         /* same test, but with indices 256-511 */
 135         __multiorder_tag_test(256, 8);
 136         __multiorder_tag_test(300, 8);
 137
 138         __multiorder_tag_test(0x12345678UL, 8);
 139
 140         for (i = 1; i < 10; i++)
 141                 for (j = 0; j < (10 << i); j++)
 142                         __multiorder_tag_test2(i, j);
 143 }
 144
 145 static void multiorder_check(unsigned long index, int order)
 146 {
 147         unsigned long i;
 148         unsigned long min = index & ~((1UL << order) - 1);
 149         unsigned long max = min + (1UL << order);
 150         void **slot;
 151         struct item *item2 = item_create(min, order);
 152         RADIX_TREE(tree, GFP_KERNEL);
 153
 154         printv(2, "Multiorder index %ld, order %d\n", index, order);
 155
 156         assert(item_insert_order(&tree, index, order) == 0);
 157
 158         for (i = min; i < max; i++) {
 159                 struct item *item = item_lookup(&tree, i);
 160                 assert(item != 0);
 161                 assert(item->index == index);
 162         }
 163         for (i = 0; i < min; i++)
 164                 item_check_absent(&tree, i);
 165         for (i = max; i < 2*max; i++)
 166                 item_check_absent(&tree, i);
 167         for (i = min; i < max; i++)
 168                 assert(radix_tree_insert(&tree, i, item2) == -EEXIST);
 169
 170         slot = radix_tree_lookup_slot(&tree, index);
 171         free(*slot);
 172         radix_tree_replace_slot(&tree, slot, item2);
 173         for (i = min; i < max; i++) {
 174                 struct item *item = item_lookup(&tree, i);
 175                 assert(item != 0);
 176                 assert(item->index == min);
 177         }
 178
 179         assert(item_delete(&tree, min) != 0);
 180
 181         for (i = 0; i < 2*max; i++)
 182                 item_check_absent(&tree, i);
 183 }
 184
 185 static void multiorder_shrink(unsigned long index, int order)
 186 {
 187         unsigned long i;
 188         unsigned long max = 1 << order;
 189         RADIX_TREE(tree, GFP_KERNEL);
 190         struct radix_tree_node *node;
 191
 192         printv(2, "Multiorder shrink index %ld, order %d\n", index, order);
 193
 194         assert(item_insert_order(&tree, 0, order) == 0);
 195
 196         node = tree.rnode;
 197
 198         assert(item_insert(&tree, index) == 0);
 199         assert(node != tree.rnode);
 200
 201         assert(item_delete(&tree, index) != 0);
 202         assert(node == tree.rnode);
 203
 204         for (i = 0; i < max; i++) {
 205                 struct item *item = item_lookup(&tree, i);
 206                 assert(item != 0);
 207                 assert(item->index == 0);
 208         }
 209         for (i = max; i < 2*max; i++)
 210                 item_check_absent(&tree, i);
 211
 212         if (!item_delete(&tree, 0)) {
 213                 printv(2, "failed to delete index %ld (order %d)\n", index, order);
 214                 abort();
 215         }
 216
 217         for (i = 0; i < 2*max; i++)
 218                 item_check_absent(&tree, i);
 219 }
 220
 221 static void multiorder_insert_bug(void)
 222 {
 223         RADIX_TREE(tree, GFP_KERNEL);
 224
 225         item_insert(&tree, 0);
 226         radix_tree_tag_set(&tree, 0, 0);
 227         item_insert_order(&tree, 3 << 6, 6);
 228
 229         item_kill_tree(&tree);
 230 }
 231
 232 void multiorder_iteration(void)
 233 {
 234         RADIX_TREE(tree, GFP_KERNEL);
 235         struct radix_tree_iter iter;
 236         void **slot;
 237         int i, j, err;
 238
 239         printv(1, "Multiorder iteration test\n");
 240
 241 #define NUM_ENTRIES 11
 242         int index[NUM_ENTRIES] = {0, 2, 4, 8, 16, 32, 34, 36, 64, 72, 128};
 243         int order[NUM_ENTRIES] = {1, 1, 2, 3,  4,  1,  0,  1,  3,  0, 7};
 244
 245         for (i = 0; i < NUM_ENTRIES; i++) {
 246                 err = item_insert_order(&tree, index[i], order[i]);
 247                 assert(!err);
 248         }
 249
 250         for (j = 0; j < 256; j++) {
 251                 for (i = 0; i < NUM_ENTRIES; i++)
 252                         if (j <= (index[i] | ((1 << order[i]) - 1)))
 253                                 break;
 254
 255                 radix_tree_for_each_slot(slot, &tree, &iter, j) {
 256                         int height = order[i] / RADIX_TREE_MAP_SHIFT;
 257                         int shift = height * RADIX_TREE_MAP_SHIFT;
 258                         unsigned long mask = (1UL << order[i]) - 1;
 259                         struct item *item = *slot;
 260
 261                         assert((iter.index | mask) == (index[i] | mask));
 262                         assert(iter.shift == shift);
 263                         assert(!radix_tree_is_internal_node(item));
 264                         assert((item->index | mask) == (index[i] | mask));
 265                         assert(item->order == order[i]);
 266                         i++;
 267                 }
 268         }
 269
 270         item_kill_tree(&tree);
 271 }
 272
 273 void multiorder_tagged_iteration(void)
 274 {
 275         RADIX_TREE(tree, GFP_KERNEL);
 276         struct radix_tree_iter iter;
 277         void **slot;
 278         int i, j;
 279
 280         printv(1, "Multiorder tagged iteration test\n");
 281
 282 #define MT_NUM_ENTRIES 9
 283         int index[MT_NUM_ENTRIES] = {0, 2, 4, 16, 32, 40, 64, 72, 128};
 284         int order[MT_NUM_ENTRIES] = {1, 0, 2, 4,  3,  1,  3,  0,   7};
 285
 286 #define TAG_ENTRIES 7
 287         int tag_index[TAG_ENTRIES] = {0, 4, 16, 40, 64, 72, 128};
 288
 289         for (i = 0; i < MT_NUM_ENTRIES; i++)
 290                 assert(!item_insert_order(&tree, index[i], order[i]));
 291
 292         assert(!radix_tree_tagged(&tree, 1));
 293
 294         for (i = 0; i < TAG_ENTRIES; i++)
 295                 assert(radix_tree_tag_set(&tree, tag_index[i], 1));
 296
 297         for (j = 0; j < 256; j++) {
 298                 int k;
 299
 300                 for (i = 0; i < TAG_ENTRIES; i++) {
 301                         for (k = i; index[k] < tag_index[i]; k++)
 302                                 ;
 303                         if (j <= (index[k] | ((1 << order[k]) - 1)))
 304                                 break;
 305                 }
 306
 307                 radix_tree_for_each_tagged(slot, &tree, &iter, j, 1) {
 308                         unsigned long mask;
 309                         struct item *item = *slot;
 310                         for (k = i; index[k] < tag_index[i]; k++)
 311                                 ;
 312                         mask = (1UL << order[k]) - 1;
 313
 314                         assert((iter.index | mask) == (tag_index[i] | mask));
 315                         assert(!radix_tree_is_internal_node(item));
 316                         assert((item->index | mask) == (tag_index[i] | mask));
 317                         assert(item->order == order[k]);
 318                         i++;
 319                 }
 320         }
 321
 322         assert(tag_tagged_items(&tree, NULL, 0, ~0UL, TAG_ENTRIES, 1, 2) ==
 323                                 TAG_ENTRIES);
 324
 325         for (j = 0; j < 256; j++) {
 326                 int mask, k;
 327
 328                 for (i = 0; i < TAG_ENTRIES; i++) {
 329                         for (k = i; index[k] < tag_index[i]; k++)
 330                                 ;
 331                         if (j <= (index[k] | ((1 << order[k]) - 1)))
 332                                 break;
 333                 }
 334
 335                 radix_tree_for_each_tagged(slot, &tree, &iter, j, 2) {
 336                         struct item *item = *slot;
 337                         for (k = i; index[k] < tag_index[i]; k++)
 338                                 ;
 339                         mask = (1 << order[k]) - 1;
 340
 341                         assert((iter.index | mask) == (tag_index[i] | mask));
 342                         assert(!radix_tree_is_internal_node(item));
 343                         assert((item->index | mask) == (tag_index[i] | mask));
 344                         assert(item->order == order[k]);
 345                         i++;
 346                 }
 347         }
 348
 349         assert(tag_tagged_items(&tree, NULL, 1, ~0UL, MT_NUM_ENTRIES * 2, 1, 0)
 350                         == TAG_ENTRIES);
 351         i = 0;
 352         radix_tree_for_each_tagged(slot, &tree, &iter, 0, 0) {
 353                 assert(iter.index == tag_index[i]);
 354                 i++;
 355         }
 356
 357         item_kill_tree(&tree);
 358 }
 359
 360 /*
 361  * Basic join checks: make sure we can't find an entry in the tree after
 362  * a larger entry has replaced it
 363  */
 364 static void multiorder_join1(unsigned long index,
 365                                 unsigned order1, unsigned order2)
 366 {
 367         unsigned long loc;
 368         void *item, *item2 = item_create(index + 1, order1);
 369         RADIX_TREE(tree, GFP_KERNEL);
 370
 371         item_insert_order(&tree, index, order2);
 372         item = radix_tree_lookup(&tree, index);
 373         radix_tree_join(&tree, index + 1, order1, item2);
 374         loc = find_item(&tree, item);
 375         if (loc == -1)
 376                 free(item);
 377         item = radix_tree_lookup(&tree, index + 1);
 378         assert(item == item2);
 379         item_kill_tree(&tree);
 380 }
 381
 382 /*
 383  * Check that the accounting of exceptional entries is handled correctly
 384  * by joining an exceptional entry to a normal pointer.
 385  */
 386 static void multiorder_join2(unsigned order1, unsigned order2)
 387 {
 388         RADIX_TREE(tree, GFP_KERNEL);
 389         struct radix_tree_node *node;
 390         void *item1 = item_create(0, order1);
 391         void *item2;
 392
 393         item_insert_order(&tree, 0, order2);
 394         radix_tree_insert(&tree, 1 << order2, (void *)0x12UL);
 395         item2 = __radix_tree_lookup(&tree, 1 << order2, &node, NULL);
 396         assert(item2 == (void *)0x12UL);
 397         assert(node->exceptional == 1);
 398
 399         item2 = radix_tree_lookup(&tree, 0);
 400         free(item2);
 401
 402         radix_tree_join(&tree, 0, order1, item1);
 403         item2 = __radix_tree_lookup(&tree, 1 << order2, &node, NULL);
 404         assert(item2 == item1);
 405         assert(node->exceptional == 0);
 406         item_kill_tree(&tree);
 407 }
 408
 409 /*
 410  * This test revealed an accounting bug for exceptional entries at one point.
 411  * Nodes were being freed back into the pool with an elevated exception count
 412  * by radix_tree_join() and then radix_tree_split() was failing to zero the
 413  * count of exceptional entries.
 414  */
 415 static void multiorder_join3(unsigned int order)
 416 {
 417         RADIX_TREE(tree, GFP_KERNEL);
 418         struct radix_tree_node *node;
 419         void **slot;
 420         struct radix_tree_iter iter;
 421         unsigned long i;
 422
 423         for (i = 0; i < (1 << order); i++) {
 424                 radix_tree_insert(&tree, i, (void *)0x12UL);
 425         }
 426
 427         radix_tree_join(&tree, 0, order, (void *)0x16UL);
 428         rcu_barrier();
 429
 430         radix_tree_split(&tree, 0, 0);
 431
 432         radix_tree_for_each_slot(slot, &tree, &iter, 0) {
 433                 radix_tree_iter_replace(&tree, &iter, slot, (void *)0x12UL);
 434         }
 435
 436         __radix_tree_lookup(&tree, 0, &node, NULL);
 437         assert(node->exceptional == node->count);
 438
 439         item_kill_tree(&tree);
 440 }
 441
 442 static void multiorder_join(void)
 443 {
 444         int i, j, idx;
 445
 446         for (idx = 0; idx < 1024; idx = idx * 2 + 3) {
 447                 for (i = 1; i < 15; i++) {
 448                         for (j = 0; j < i; j++) {
 449                                 multiorder_join1(idx, i, j);
 450                         }
 451                 }
 452         }
 453
 454         for (i = 1; i < 15; i++) {
 455                 for (j = 0; j < i; j++) {
 456                         multiorder_join2(i, j);
 457                 }
 458         }
 459
 460         for (i = 3; i < 10; i++) {
 461                 multiorder_join3(i);
 462         }
 463 }
 464
 465 static void check_mem(unsigned old_order, unsigned new_order, unsigned alloc)
 466 {
 467         struct radix_tree_preload *rtp = &radix_tree_preloads;
 468         if (rtp->nr != 0)
 469                 printv(2, "split(%u %u) remaining %u\n", old_order, new_order,
 470                                                         rtp->nr);
 471         /*
 472          * Can't check for equality here as some nodes may have been
 473          * RCU-freed while we ran.  But we should never finish with more
 474          * nodes allocated since they should have all been preloaded.
 475          */
 476         if (nr_allocated > alloc)
 477                 printv(2, "split(%u %u) allocated %u %u\n", old_order, new_order,
 478                                                         alloc, nr_allocated);
 479 }
 480
 481 static void __multiorder_split(int old_order, int new_order)
 482 {
 483         RADIX_TREE(tree, GFP_ATOMIC);
 484         void **slot;
 485         struct radix_tree_iter iter;
 486         unsigned alloc;
 487         struct item *item;
 488
 489         radix_tree_preload(GFP_KERNEL);
 490         assert(item_insert_order(&tree, 0, old_order) == 0);
 491         radix_tree_preload_end();
 492
 493         /* Wipe out the preloaded cache or it'll confuse check_mem() */
 494         radix_tree_cpu_dead(0);
 495
 496         item = radix_tree_tag_set(&tree, 0, 2);
 497
 498         radix_tree_split_preload(old_order, new_order, GFP_KERNEL);
 499         alloc = nr_allocated;
 500         radix_tree_split(&tree, 0, new_order);
 501         check_mem(old_order, new_order, alloc);
 502         radix_tree_for_each_slot(slot, &tree, &iter, 0) {
 503                 radix_tree_iter_replace(&tree, &iter, slot,
 504                                         item_create(iter.index, new_order));
 505         }
 506         radix_tree_preload_end();
 507
 508         item_kill_tree(&tree);
 509         free(item);
 510 }
 511
 512 static void __multiorder_split2(int old_order, int new_order)
 513 {
 514         RADIX_TREE(tree, GFP_KERNEL);
 515         void **slot;
 516         struct radix_tree_iter iter;
 517         struct radix_tree_node *node;
 518         void *item;
 519
 520         __radix_tree_insert(&tree, 0, old_order, (void *)0x12);
 521
 522         item = __radix_tree_lookup(&tree, 0, &node, NULL);
 523         assert(item == (void *)0x12);
 524         assert(node->exceptional > 0);
 525
 526         radix_tree_split(&tree, 0, new_order);
 527         radix_tree_for_each_slot(slot, &tree, &iter, 0) {
 528                 radix_tree_iter_replace(&tree, &iter, slot,
 529                                         item_create(iter.index, new_order));
 530         }
 531
 532         item = __radix_tree_lookup(&tree, 0, &node, NULL);
 533         assert(item != (void *)0x12);
 534         assert(node->exceptional == 0);
 535
 536         item_kill_tree(&tree);
 537 }
 538
 539 static void __multiorder_split3(int old_order, int new_order)
 540 {
 541         RADIX_TREE(tree, GFP_KERNEL);
 542         void **slot;
 543         struct radix_tree_iter iter;
 544         struct radix_tree_node *node;
 545         void *item;
 546
 547         __radix_tree_insert(&tree, 0, old_order, (void *)0x12);
 548
 549         item = __radix_tree_lookup(&tree, 0, &node, NULL);
 550         assert(item == (void *)0x12);
 551         assert(node->exceptional > 0);
 552
 553         radix_tree_split(&tree, 0, new_order);
 554         radix_tree_for_each_slot(slot, &tree, &iter, 0) {
 555                 radix_tree_iter_replace(&tree, &iter, slot, (void *)0x16);
 556         }
 557
 558         item = __radix_tree_lookup(&tree, 0, &node, NULL);
 559         assert(item == (void *)0x16);
 560         assert(node->exceptional > 0);
 561
 562         item_kill_tree(&tree);
 563
 564         __radix_tree_insert(&tree, 0, old_order, (void *)0x12);
 565
 566         item = __radix_tree_lookup(&tree, 0, &node, NULL);
 567         assert(item == (void *)0x12);
 568         assert(node->exceptional > 0);
 569
 570         radix_tree_split(&tree, 0, new_order);
 571         radix_tree_for_each_slot(slot, &tree, &iter, 0) {
 572                 if (iter.index == (1 << new_order))
 573                         radix_tree_iter_replace(&tree, &iter, slot,
 574                                                 (void *)0x16);
 575                 else
 576                         radix_tree_iter_replace(&tree, &iter, slot, NULL);
 577         }
 578
 579         item = __radix_tree_lookup(&tree, 1 << new_order, &node, NULL);
 580         assert(item == (void *)0x16);
 581         assert(node->count == node->exceptional);
 582         do {
 583                 node = node->parent;
 584                 if (!node)
 585                         break;
 586                 assert(node->count == 1);
 587                 assert(node->exceptional == 0);
 588         } while (1);
 589
 590         item_kill_tree(&tree);
 591 }
 592
 593 static void multiorder_split(void)
 594 {
 595         int i, j;
 596
 597         for (i = 3; i < 11; i++)
 598                 for (j = 0; j < i; j++) {
 599                         __multiorder_split(i, j);
 600                         __multiorder_split2(i, j);
 601                         __multiorder_split3(i, j);
 602                 }
 603 }
 604
 605 static void multiorder_account(void)
 606 {
 607         RADIX_TREE(tree, GFP_KERNEL);
 608         struct radix_tree_node *node;
 609         void **slot;
 610
 611         item_insert_order(&tree, 0, 5);
 612
 613         __radix_tree_insert(&tree, 1 << 5, 5, (void *)0x12);
 614         __radix_tree_lookup(&tree, 0, &node, NULL);
 615         assert(node->count == node->exceptional * 2);
 616         radix_tree_delete(&tree, 1 << 5);
 617         assert(node->exceptional == 0);
 618
 619         __radix_tree_insert(&tree, 1 << 5, 5, (void *)0x12);
 620         __radix_tree_lookup(&tree, 1 << 5, &node, &slot);
 621         assert(node->count == node->exceptional * 2);
 622         __radix_tree_replace(&tree, node, slot, NULL, NULL);
 623         assert(node->exceptional == 0);
 624
 625         item_kill_tree(&tree);
 626 }
 627
 628 bool stop_iteration = false;
 629
 630 static void *creator_func(void *ptr)
 631 {
 632         /* 'order' is set up to ensure we have sibling entries */
 633         unsigned int order = RADIX_TREE_MAP_SHIFT - 1;
 634         struct radix_tree_root *tree = ptr;
 635         int i;
 636
 637         for (i = 0; i < 10000; i++) {
 638                 item_insert_order(tree, 0, order);
 639                 item_delete_rcu(tree, 0);
 640         }
 641
 642         stop_iteration = true;
 643         return NULL;
 644 }
 645
 646 static void *iterator_func(void *ptr)
 647 {
 648         struct radix_tree_root *tree = ptr;
 649         struct radix_tree_iter iter;
 650         struct item *item;
 651         void **slot;
 652
 653         while (!stop_iteration) {
 654                 rcu_read_lock();
 655                 radix_tree_for_each_slot(slot, tree, &iter, 0) {
 656                         item = radix_tree_deref_slot(slot);
 657
 658                         if (!item)
 659                                 continue;
 660                         if (radix_tree_deref_retry(item)) {
 661                                 slot = radix_tree_iter_retry(&iter);
 662                                 continue;
 663                         }
 664
 665                         item_sanity(item, iter.index);
 666                 }
 667                 rcu_read_unlock();
 668         }
 669         return NULL;
 670 }
 671
 672 static void multiorder_iteration_race(void)
 673 {
 674         const int num_threads = sysconf(_SC_NPROCESSORS_ONLN);
 675         pthread_t worker_thread[num_threads];
 676         RADIX_TREE(tree, GFP_KERNEL);
 677         int i;
 678
 679         pthread_create(&worker_thread[0], NULL, &creator_func, &tree);
 680         for (i = 1; i < num_threads; i++)
 681                 pthread_create(&worker_thread[i], NULL, &iterator_func, &tree);
 682
 683         for (i = 0; i < num_threads; i++)
 684                 pthread_join(worker_thread[i], NULL);
 685
 686         item_kill_tree(&tree);
 687 }
 688
 689 void multiorder_checks(void)
 690 {
 691         int i;
 692
 693         for (i = 0; i < 20; i++) {
 694                 multiorder_check(200, i);
 695                 multiorder_check(0, i);
 696                 multiorder_check((1UL << i) + 1, i);
 697         }
 698
 699         for (i = 0; i < 15; i++)
 700                 multiorder_shrink((1UL << (i + RADIX_TREE_MAP_SHIFT)), i);
 701
 702         multiorder_insert_bug();
 703         multiorder_tag_tests();
 704         multiorder_iteration();
 705         multiorder_tagged_iteration();
 706         multiorder_join();
 707         multiorder_split();
 708         multiorder_account();
 709         multiorder_iteration_race();
 710
 711         radix_tree_cpu_dead(0);
 712 }
 713
 714 int __weak main(void)
 715 {
 716         radix_tree_init();
 717         multiorder_checks();
 718         return 0;
 719 }