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