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                 srand(time(0));
  71                 printf("%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                                 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));
 133                         }
 134                         assert(!item_tag_get(tree, idx[i], totag));
 135                         continue;
 136                 }
 137                 if (item_tag_get(tree, idx[i], fromtag) ^
 138                         item_tag_get(tree, idx[i], totag)) {
 139                         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));
 140                 }
 141                 assert(!(item_tag_get(tree, idx[i], fromtag) ^
 142                          item_tag_get(tree, idx[i], totag)));
 143         }
 144 }
 145
 146 #define ITEMS 50000
 147
 148 void copy_tag_check(void)
 149 {
 150         RADIX_TREE(tree, GFP_KERNEL);
 151         unsigned long idx[ITEMS];
 152         unsigned long start, end, count = 0, tagged, cur, tmp;
 153         int i;
 154
 155 //      printf("generating radix tree indices...\n");
 156         start = rand();
 157         end = rand();
 158         if (start > end && (rand() % 10)) {
 159                 cur = start;
 160                 start = end;
 161                 end = cur;
 162         }
 163         /* Specifically create items around the start and the end of the range
 164          * with high probability to check for off by one errors */
 165         cur = rand();
 166         if (cur & 1) {
 167                 item_insert(&tree, start);
 168                 if (cur & 2) {
 169                         if (start <= end)
 170                                 count++;
 171                         item_tag_set(&tree, start, 0);
 172                 }
 173         }
 174         if (cur & 4) {
 175                 item_insert(&tree, start-1);
 176                 if (cur & 8)
 177                         item_tag_set(&tree, start-1, 0);
 178         }
 179         if (cur & 16) {
 180                 item_insert(&tree, end);
 181                 if (cur & 32) {
 182                         if (start <= end)
 183                                 count++;
 184                         item_tag_set(&tree, end, 0);
 185                 }
 186         }
 187         if (cur & 64) {
 188                 item_insert(&tree, end+1);
 189                 if (cur & 128)
 190                         item_tag_set(&tree, end+1, 0);
 191         }
 192
 193         for (i = 0; i < ITEMS; i++) {
 194                 do {
 195                         idx[i] = rand();
 196                 } while (item_lookup(&tree, idx[i]));
 197
 198                 item_insert(&tree, idx[i]);
 199                 if (rand() & 1) {
 200                         item_tag_set(&tree, idx[i], 0);
 201                         if (idx[i] >= start && idx[i] <= end)
 202                                 count++;
 203                 }
 204 /*              if (i % 1000 == 0)
 205                         putchar('.'); */
 206         }
 207
 208 //      printf("\ncopying tags...\n");
 209         cur = start;
 210         tagged = radix_tree_range_tag_if_tagged(&tree, &cur, end, ITEMS, 0, 1);
 211
 212 //      printf("checking copied tags\n");
 213         assert(tagged == count);
 214         check_copied_tags(&tree, start, end, idx, ITEMS, 0, 1);
 215
 216         /* Copy tags in several rounds */
 217 //      printf("\ncopying tags...\n");
 218         cur = start;
 219         do {
 220                 tmp = rand() % (count/10+2);
 221                 tagged = radix_tree_range_tag_if_tagged(&tree, &cur, end, tmp, 0, 2);
 222         } while (tmp == tagged);
 223
 224 //      printf("%lu %lu %lu\n", tagged, tmp, count);
 225 //      printf("checking copied tags\n");
 226         check_copied_tags(&tree, start, end, idx, ITEMS, 0, 2);
 227         assert(tagged < tmp);
 228         verify_tag_consistency(&tree, 0);
 229         verify_tag_consistency(&tree, 1);
 230         verify_tag_consistency(&tree, 2);
 231 //      printf("\n");
 232         item_kill_tree(&tree);
 233 }
 234
 235 static void __locate_check(struct radix_tree_root *tree, unsigned long index,
 236                         unsigned order)
 237 {
 238         struct item *item;
 239         unsigned long index2;
 240
 241         item_insert_order(tree, index, order);
 242         item = item_lookup(tree, index);
 243         index2 = radix_tree_locate_item(tree, item);
 244         if (index != index2) {
 245                 printf("index %ld order %d inserted; found %ld\n",
 246                         index, order, index2);
 247                 abort();
 248         }
 249 }
 250
 251 static void __order_0_locate_check(void)
 252 {
 253         RADIX_TREE(tree, GFP_KERNEL);
 254         int i;
 255
 256         for (i = 0; i < 50; i++)
 257                 __locate_check(&tree, rand() % INT_MAX, 0);
 258
 259         item_kill_tree(&tree);
 260 }
 261
 262 static void locate_check(void)
 263 {
 264         RADIX_TREE(tree, GFP_KERNEL);
 265         unsigned order;
 266         unsigned long offset, index;
 267
 268         __order_0_locate_check();
 269
 270         for (order = 0; order < 20; order++) {
 271                 for (offset = 0; offset < (1 << (order + 3));
 272                      offset += (1UL << order)) {
 273                         for (index = 0; index < (1UL << (order + 5));
 274                              index += (1UL << order)) {
 275                                 __locate_check(&tree, index + offset, order);
 276                         }
 277                         if (radix_tree_locate_item(&tree, &tree) != -1)
 278                                 abort();
 279
 280                         item_kill_tree(&tree);
 281                 }
 282         }
 283
 284         if (radix_tree_locate_item(&tree, &tree) != -1)
 285                 abort();
 286         __locate_check(&tree, -1, 0);
 287         if (radix_tree_locate_item(&tree, &tree) != -1)
 288                 abort();
 289         item_kill_tree(&tree);
 290 }
 291
 292 static void single_thread_tests(bool long_run)
 293 {
 294         int i;
 295
 296         printf("starting single_thread_tests: %d allocated\n", nr_allocated);
 297         multiorder_checks();
 298         printf("after multiorder_check: %d allocated\n", nr_allocated);
 299         locate_check();
 300         printf("after locate_check: %d allocated\n", nr_allocated);
 301         tag_check();
 302         printf("after tag_check: %d allocated\n", nr_allocated);
 303         gang_check();
 304         printf("after gang_check: %d allocated\n", nr_allocated);
 305         add_and_check();
 306         printf("after add_and_check: %d allocated\n", nr_allocated);
 307         dynamic_height_check();
 308         printf("after dynamic_height_check: %d allocated\n", nr_allocated);
 309         big_gang_check(long_run);
 310         printf("after big_gang_check: %d allocated\n", nr_allocated);
 311         for (i = 0; i < (long_run ? 2000 : 3); i++) {
 312                 copy_tag_check();
 313                 printf("%d ", i);
 314                 fflush(stdout);
 315         }
 316         printf("after copy_tag_check: %d allocated\n", nr_allocated);
 317 }
 318
 319 int main(int argc, char **argv)
 320 {
 321         bool long_run = false;
 322         int opt;
 323
 324         while ((opt = getopt(argc, argv, "l")) != -1) {
 325                 if (opt == 'l')
 326                         long_run = true;
 327         }
 328
 329         rcu_register_thread();
 330         radix_tree_init();
 331
 332         regression1_test();
 333         regression2_test();
 334         regression3_test();
 335         single_thread_tests(long_run);
 336
 337         sleep(1);
 338         printf("after sleep(1): %d allocated\n", nr_allocated);
 339         rcu_unregister_thread();
 340
 341         exit(0);
 342 }