tools/testing/radix-tree/main.c

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