tools/testing/radix-tree/main.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include <unistd.h>
   5 #include <time.h>
   6 #include <assert.h>
   7 #include <limits.h>
   8
   9 #include <linux/slab.h>
  10 #include <linux/radix-tree.h>
  11
  12 #include "test.h"
  13 #include "regression.h"
  14
  15 void __gang_check(unsigned long middle, long down, long up, int chunk, int hop)
  16 {
  17         long idx;
  18         RADIX_TREE(tree, GFP_KERNEL);
  19
  20         middle = 1 << 30;
  21
  22         for (idx = -down; idx < up; idx++)
  23                 item_insert(&tree, middle + idx);
  24
  25         item_check_absent(&tree, middle - down - 1);
  26         for (idx = -down; idx < up; idx++)
  27                 item_check_present(&tree, middle + idx);
  28         item_check_absent(&tree, middle + up);
  29
  30         if (chunk > 0) {
  31                 item_gang_check_present(&tree, middle - down, up + down,
  32                                 chunk, hop);
  33                 item_full_scan(&tree, middle - down, down + up, chunk);
  34         }
  35         item_kill_tree(&tree);
  36 }
  37
  38 void gang_check(void)
  39 {
  40         __gang_check(1UL << 30, 128, 128, 35, 2);
  41         __gang_check(1UL << 31, 128, 128, 32, 32);
  42         __gang_check(1UL << 31, 128, 128, 32, 100);
  43         __gang_check(1UL << 31, 128, 128, 17, 7);
  44         __gang_check(0xffff0000UL, 0, 65536, 17, 7);
  45         __gang_check(0xfffffffeUL, 1, 1, 17, 7);
  46 }
  47
  48 void __big_gang_check(void)
  49 {
  50         unsigned long start;
  51         int wrapped = 0;
  52
  53         start = 0;
  54         do {
  55                 unsigned long old_start;
  56
  57 //              printf("0x%08lx\n", start);
  58                 __gang_check(start, rand() % 113 + 1, rand() % 71,
  59                                 rand() % 157, rand() % 91 + 1);
  60                 old_start = start;
  61                 start += rand() % 1000000;
  62                 start %= 1ULL << 33;
  63                 if (start < old_start)
  64                         wrapped = 1;
  65         } while (!wrapped);
  66 }
  67
  68 void big_gang_check(bool long_run)
  69 {
  70         int i;
  71
  72         for (i = 0; i < (long_run ? 1000 : 3); i++) {
  73                 __big_gang_check();
  74                 printv(2, "%d ", i);
  75                 fflush(stdout);
  76         }
  77 }
  78
  79 void add_and_check(void)
  80 {
  81         RADIX_TREE(tree, GFP_KERNEL);
  82
  83         item_insert(&tree, 44);
  84         item_check_present(&tree, 44);
  85         item_check_absent(&tree, 43);
  86         item_kill_tree(&tree);
  87 }
  88
  89 void dynamic_height_check(void)
  90 {
  91         int i;
  92         RADIX_TREE(tree, GFP_KERNEL);
  93         tree_verify_min_height(&tree, 0);
  94
  95         item_insert(&tree, 42);
  96         tree_verify_min_height(&tree, 42);
  97
  98         item_insert(&tree, 1000000);
  99         tree_verify_min_height(&tree, 1000000);
 100
 101         assert(item_delete(&tree, 1000000));
 102         tree_verify_min_height(&tree, 42);
 103
 104         assert(item_delete(&tree, 42));
 105         tree_verify_min_height(&tree, 0);
 106
 107         for (i = 0; i < 1000; i++) {
 108                 item_insert(&tree, i);
 109                 tree_verify_min_height(&tree, i);
 110         }
 111
 112         i--;
 113         for (;;) {
 114                 assert(item_delete(&tree, i));
 115                 if (i == 0) {
 116                         tree_verify_min_height(&tree, 0);
 117                         break;
 118                 }
 119                 i--;
 120                 tree_verify_min_height(&tree, i);
 121         }
 122
 123         item_kill_tree(&tree);
 124 }
 125
 126 void check_copied_tags(struct radix_tree_root *tree, unsigned long start, unsigned long end, unsigned long *idx, int count, int fromtag, int totag)
 127 {
 128         int i;
 129
 130         for (i = 0; i < count; i++) {
 131 /*              if (i % 1000 == 0)
 132                         putchar('.'); */
 133                 if (idx[i] < start || idx[i] > end) {
 134                         if (item_tag_get(tree, idx[i], totag)) {
 135                                 printv(2, "%lu-%lu: %lu, tags %d-%d\n", start,
 136                                        end, idx[i], item_tag_get(tree, idx[i],
 137                                                                  fromtag),
 138                                        item_tag_get(tree, idx[i], totag));
 139                         }
 140                         assert(!item_tag_get(tree, idx[i], totag));
 141                         continue;
 142                 }
 143                 if (item_tag_get(tree, idx[i], fromtag) ^
 144                         item_tag_get(tree, idx[i], totag)) {
 145                         printv(2, "%lu-%lu: %lu, tags %d-%d\n", start, end,
 146                                idx[i], item_tag_get(tree, idx[i], fromtag),
 147                                item_tag_get(tree, idx[i], totag));
 148                 }
 149                 assert(!(item_tag_get(tree, idx[i], fromtag) ^
 150                          item_tag_get(tree, idx[i], totag)));
 151         }
 152 }
 153
 154 #define ITEMS 50000
 155
 156 void copy_tag_check(void)
 157 {
 158         RADIX_TREE(tree, GFP_KERNEL);
 159         unsigned long idx[ITEMS];
 160         unsigned long start, end, count = 0, tagged, cur, tmp;
 161         int i;
 162
 163 //      printf("generating radix tree indices...\n");
 164         start = rand();
 165         end = rand();
 166         if (start > end && (rand() % 10)) {
 167                 cur = start;
 168                 start = end;
 169                 end = cur;
 170         }
 171         /* Specifically create items around the start and the end of the range
 172          * with high probability to check for off by one errors */
 173         cur = rand();
 174         if (cur & 1) {
 175                 item_insert(&tree, start);
 176                 if (cur & 2) {
 177                         if (start <= end)
 178                                 count++;
 179                         item_tag_set(&tree, start, 0);
 180                 }
 181         }
 182         if (cur & 4) {
 183                 item_insert(&tree, start-1);
 184                 if (cur & 8)
 185                         item_tag_set(&tree, start-1, 0);
 186         }
 187         if (cur & 16) {
 188                 item_insert(&tree, end);
 189                 if (cur & 32) {
 190                         if (start <= end)
 191                                 count++;
 192                         item_tag_set(&tree, end, 0);
 193                 }
 194         }
 195         if (cur & 64) {
 196                 item_insert(&tree, end+1);
 197                 if (cur & 128)
 198                         item_tag_set(&tree, end+1, 0);
 199         }
 200
 201         for (i = 0; i < ITEMS; i++) {
 202                 do {
 203                         idx[i] = rand();
 204                 } while (item_lookup(&tree, idx[i]));
 205
 206                 item_insert(&tree, idx[i]);
 207                 if (rand() & 1) {
 208                         item_tag_set(&tree, idx[i], 0);
 209                         if (idx[i] >= start && idx[i] <= end)
 210                                 count++;
 211                 }
 212 /*              if (i % 1000 == 0)
 213                         putchar('.'); */
 214         }
 215
 216 //      printf("\ncopying tags...\n");
 217         tagged = tag_tagged_items(&tree, NULL, start, end, ITEMS, 0, 1);
 218
 219 //      printf("checking copied tags\n");
 220         assert(tagged == count);
 221         check_copied_tags(&tree, start, end, idx, ITEMS, 0, 1);
 222
 223         /* Copy tags in several rounds */
 224 //      printf("\ncopying tags...\n");
 225         tmp = rand() % (count / 10 + 2);
 226         tagged = tag_tagged_items(&tree, NULL, start, end, tmp, 0, 2);
 227         assert(tagged == count);
 228
 229 //      printf("%lu %lu %lu\n", tagged, tmp, count);
 230 //      printf("checking copied tags\n");
 231         check_copied_tags(&tree, start, end, idx, ITEMS, 0, 2);
 232         verify_tag_consistency(&tree, 0);
 233         verify_tag_consistency(&tree, 1);
 234         verify_tag_consistency(&tree, 2);
 235 //      printf("\n");
 236         item_kill_tree(&tree);
 237 }
 238
 239 static void __locate_check(struct radix_tree_root *tree, unsigned long index,
 240                         unsigned order)
 241 {
 242         struct item *item;
 243         unsigned long index2;
 244
 245         item_insert_order(tree, index, order);
 246         item = item_lookup(tree, index);
 247         index2 = find_item(tree, item);
 248         if (index != index2) {
 249                 printv(2, "index %ld order %d inserted; found %ld\n",
 250                         index, order, index2);
 251                 abort();
 252         }
 253 }
 254
 255 static void __order_0_locate_check(void)
 256 {
 257         RADIX_TREE(tree, GFP_KERNEL);
 258         int i;
 259
 260         for (i = 0; i < 50; i++)
 261                 __locate_check(&tree, rand() % INT_MAX, 0);
 262
 263         item_kill_tree(&tree);
 264 }
 265
 266 static void locate_check(void)
 267 {
 268         RADIX_TREE(tree, GFP_KERNEL);
 269         unsigned order;
 270         unsigned long offset, index;
 271
 272         __order_0_locate_check();
 273
 274         for (order = 0; order < 20; order++) {
 275                 for (offset = 0; offset < (1 << (order + 3));
 276                      offset += (1UL << order)) {
 277                         for (index = 0; index < (1UL << (order + 5));
 278                              index += (1UL << order)) {
 279                                 __locate_check(&tree, index + offset, order);
 280                         }
 281                         if (find_item(&tree, &tree) != -1)
 282                                 abort();
 283
 284                         item_kill_tree(&tree);
 285                 }
 286         }
 287
 288         if (find_item(&tree, &tree) != -1)
 289                 abort();
 290         __locate_check(&tree, -1, 0);
 291         if (find_item(&tree, &tree) != -1)
 292                 abort();
 293         item_kill_tree(&tree);
 294 }
 295
 296 static void single_thread_tests(bool long_run)
 297 {
 298         int i;
 299
 300         printv(1, "starting single_thread_tests: %d allocated, preempt %d\n",
 301                 nr_allocated, preempt_count);
 302         multiorder_checks();
 303         rcu_barrier();
 304         printv(2, "after multiorder_check: %d allocated, preempt %d\n",
 305                 nr_allocated, preempt_count);
 306         locate_check();
 307         rcu_barrier();
 308         printv(2, "after locate_check: %d allocated, preempt %d\n",
 309                 nr_allocated, preempt_count);
 310         tag_check();
 311         rcu_barrier();
 312         printv(2, "after tag_check: %d allocated, preempt %d\n",
 313                 nr_allocated, preempt_count);
 314         gang_check();
 315         rcu_barrier();
 316         printv(2, "after gang_check: %d allocated, preempt %d\n",
 317                 nr_allocated, preempt_count);
 318         add_and_check();
 319         rcu_barrier();
 320         printv(2, "after add_and_check: %d allocated, preempt %d\n",
 321                 nr_allocated, preempt_count);
 322         dynamic_height_check();
 323         rcu_barrier();
 324         printv(2, "after dynamic_height_check: %d allocated, preempt %d\n",
 325                 nr_allocated, preempt_count);
 326         idr_checks();
 327         ida_checks();
 328         rcu_barrier();
 329         printv(2, "after idr_checks: %d allocated, preempt %d\n",
 330                 nr_allocated, preempt_count);
 331         big_gang_check(long_run);
 332         rcu_barrier();
 333         printv(2, "after big_gang_check: %d allocated, preempt %d\n",
 334                 nr_allocated, preempt_count);
 335         for (i = 0; i < (long_run ? 2000 : 3); i++) {
 336                 copy_tag_check();
 337                 printv(2, "%d ", i);
 338                 fflush(stdout);
 339         }
 340         rcu_barrier();
 341         printv(2, "after copy_tag_check: %d allocated, preempt %d\n",
 342                 nr_allocated, preempt_count);
 343 }
 344
 345 int main(int argc, char **argv)
 346 {
 347         bool long_run = false;
 348         int opt;
 349         unsigned int seed = time(NULL);
 350
 351         while ((opt = getopt(argc, argv, "ls:v")) != -1) {
 352                 if (opt == 'l')
 353                         long_run = true;
 354                 else if (opt == 's')
 355                         seed = strtoul(optarg, NULL, 0);
 356                 else if (opt == 'v')
 357                         test_verbose++;
 358         }
 359
 360         printf("random seed %u\n", seed);
 361         srand(seed);
 362
 363         printf("running tests\n");
 364
 365         rcu_register_thread();
 366         radix_tree_init();
 367
 368         regression1_test();
 369         regression2_test();
 370         regression3_test();
 371         iteration_test(0, 10 + 90 * long_run);
 372         iteration_test(7, 10 + 90 * long_run);
 373         single_thread_tests(long_run);
 374         ida_thread_tests();
 375
 376         /* Free any remaining preallocated nodes */
 377         radix_tree_cpu_dead(0);
 378
 379         benchmark();
 380
 381         rcu_barrier();
 382         printv(2, "after rcu_barrier: %d allocated, preempt %d\n",
 383                 nr_allocated, preempt_count);
 384         rcu_unregister_thread();
 385
 386         printf("tests completed\n");
 387
 388         exit(0);
 389 }