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