random-test.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <signal.h>
   4 #include "kerncompat.h"
   5 #include "radix-tree.h"
   6 #include "ctree.h"
   7 #include "disk-io.h"
   8 #include "print-tree.h"
   9
  10 int keep_running = 1;
  11 struct ctree_super_block super;
  12
  13 static int setup_key(struct radix_tree_root *root, struct key *key, int exists)
  14 {
  15         int num = rand();
  16         unsigned long res[2];
  17         int ret;
  18
  19         key->flags = 0;
  20         key->offset = 0;
  21 again:
  22         ret = radix_tree_gang_lookup(root, (void **)res, num, 2);
  23         if (exists) {
  24                 if (ret == 0)
  25                         return -1;
  26                 num = res[0];
  27         } else if (ret != 0 && num == res[0]) {
  28                 num++;
  29                 if (ret > 1 && num == res[1]) {
  30                         num++;
  31                         goto again;
  32                 }
  33         }
  34         key->objectid = num;
  35         return 0;
  36 }
  37
  38 static int ins_one(struct ctree_root *root, struct radix_tree_root *radix)
  39 {
  40         struct ctree_path path;
  41         struct key key;
  42         int ret;
  43         char buf[128];
  44         unsigned long oid;
  45         init_path(&path);
  46         ret = setup_key(radix, &key, 0);
  47         sprintf(buf, "str-%Lu\n", key.objectid);
  48         ret = insert_item(root, &key, buf, strlen(buf));
  49         if (ret)
  50                 goto error;
  51         oid = (unsigned long)key.objectid;
  52         radix_tree_preload(GFP_KERNEL);
  53         ret = radix_tree_insert(radix, oid, (void *)oid);
  54         radix_tree_preload_end();
  55         if (ret)
  56                 goto error;
  57         return ret;
  58 error:
  59         printf("failed to insert %Lu\n", key.objectid);
  60         return -1;
  61 }
  62
  63 static int insert_dup(struct ctree_root *root, struct radix_tree_root *radix)
  64 {
  65         struct ctree_path path;
  66         struct key key;
  67         int ret;
  68         char buf[128];
  69         init_path(&path);
  70         ret = setup_key(radix, &key, 1);
  71         if (ret < 0)
  72                 return 0;
  73         sprintf(buf, "str-%Lu\n", key.objectid);
  74         ret = insert_item(root, &key, buf, strlen(buf));
  75         if (ret != -EEXIST) {
  76                 printf("insert on %Lu gave us %d\n", key.objectid, ret);
  77                 return 1;
  78         }
  79         return 0;
  80 }
  81
  82 static int del_one(struct ctree_root *root, struct radix_tree_root *radix)
  83 {
  84         struct ctree_path path;
  85         struct key key;
  86         int ret;
  87         unsigned long *ptr;
  88         init_path(&path);
  89         ret = setup_key(radix, &key, 1);
  90         if (ret < 0)
  91                 return 0;
  92         ret = search_slot(root, &key, &path, -1, 1);
  93         if (ret)
  94                 goto error;
  95         ret = del_item(root, &path);
  96         release_path(root, &path);
  97         if (ret != 0)
  98                 goto error;
  99         ptr = radix_tree_delete(radix, key.objectid);
 100         if (!ptr)
 101                 goto error;
 102         return 0;
 103 error:
 104         printf("failed to delete %Lu\n", key.objectid);
 105         return -1;
 106 }
 107
 108 static int lookup_item(struct ctree_root *root, struct radix_tree_root *radix)
 109 {
 110         struct ctree_path path;
 111         struct key key;
 112         int ret;
 113         init_path(&path);
 114         ret = setup_key(radix, &key, 1);
 115         if (ret < 0)
 116                 return 0;
 117         ret = search_slot(root, &key, &path, 0, 1);
 118         release_path(root, &path);
 119         if (ret)
 120                 goto error;
 121         return 0;
 122 error:
 123         printf("unable to find key %Lu\n", key.objectid);
 124         return -1;
 125 }
 126
 127 static int lookup_enoent(struct ctree_root *root, struct radix_tree_root *radix)
 128 {
 129         struct ctree_path path;
 130         struct key key;
 131         int ret;
 132         init_path(&path);
 133         ret = setup_key(radix, &key, 0);
 134         if (ret < 0)
 135                 return ret;
 136         ret = search_slot(root, &key, &path, 0, 0);
 137         release_path(root, &path);
 138         if (ret <= 0)
 139                 goto error;
 140         return 0;
 141 error:
 142         printf("able to find key that should not exist %Lu\n", key.objectid);
 143         return -1;
 144 }
 145
 146 static int empty_tree(struct ctree_root *root, struct radix_tree_root *radix,
 147                       int nr)
 148 {
 149         struct ctree_path path;
 150         struct key key;
 151         unsigned long found = 0;
 152         int ret;
 153         int slot;
 154         int *ptr;
 155         int count = 0;
 156
 157         key.offset = 0;
 158         key.flags = 0;
 159         key.objectid = (unsigned long)-1;
 160         while(nr-- >= 0) {
 161                 init_path(&path);
 162                 ret = search_slot(root, &key, &path, -1, 1);
 163                 if (ret < 0) {
 164                         release_path(root, &path);
 165                         return ret;
 166                 }
 167                 if (ret != 0) {
 168                         if (path.slots[0] == 0) {
 169                                 release_path(root, &path);
 170                                 break;
 171                         }
 172                         path.slots[0] -= 1;
 173                 }
 174                 slot = path.slots[0];
 175                 found = path.nodes[0]->leaf.items[slot].key.objectid;
 176                 ret = del_item(root, &path);
 177                 count++;
 178                 if (ret) {
 179                         fprintf(stderr,
 180                                 "failed to remove %lu from tree\n",
 181                                 found);
 182                         return -1;
 183                 }
 184                 release_path(root, &path);
 185                 ptr = radix_tree_delete(radix, found);
 186                 if (!ptr)
 187                         goto error;
 188                 if (!keep_running)
 189                         break;
 190         }
 191         return 0;
 192 error:
 193         fprintf(stderr, "failed to delete from the radix %lu\n", found);
 194         return -1;
 195 }
 196
 197 static int fill_tree(struct ctree_root *root, struct radix_tree_root *radix,
 198                      int count)
 199 {
 200         int i;
 201         int ret = 0;
 202         for (i = 0; i < count; i++) {
 203                 ret = ins_one(root, radix);
 204                 if (ret) {
 205                         fprintf(stderr, "fill failed\n");
 206                         goto out;
 207                 }
 208                 if (i % 1000 == 0) {
 209                         ret = commit_transaction(root, &super);
 210                         if (ret) {
 211                                 fprintf(stderr, "fill commit failed\n");
 212                                 return ret;
 213                         }
 214                 }
 215                 if (i && i % 10000 == 0) {
 216                         printf("bigfill %d\n", i);
 217                 }
 218                 if (!keep_running)
 219                         break;
 220         }
 221 out:
 222         return ret;
 223 }
 224
 225 static int bulk_op(struct ctree_root *root, struct radix_tree_root *radix)
 226 {
 227         int ret;
 228         int nr = rand() % 5000;
 229         static int run_nr = 0;
 230
 231         /* do the bulk op much less frequently */
 232         if (run_nr++ % 100)
 233                 return 0;
 234         ret = empty_tree(root, radix, nr);
 235         if (ret)
 236                 return ret;
 237         ret = fill_tree(root, radix, nr);
 238         if (ret)
 239                 return ret;
 240         return 0;
 241 }
 242
 243
 244 int (*ops[])(struct ctree_root *root, struct radix_tree_root *radix) =
 245         { ins_one, insert_dup, del_one, lookup_item,
 246           lookup_enoent, bulk_op };
 247
 248 static int fill_radix(struct ctree_root *root, struct radix_tree_root *radix)
 249 {
 250         struct ctree_path path;
 251         struct key key;
 252         unsigned long found;
 253         int ret;
 254         int slot;
 255         int i;
 256
 257         key.offset = 0;
 258         key.flags = 0;
 259         key.objectid = (unsigned long)-1;
 260         while(1) {
 261                 init_path(&path);
 262                 ret = search_slot(root, &key, &path, 0, 0);
 263                 if (ret < 0) {
 264                         release_path(root, &path);
 265                         return ret;
 266                 }
 267                 slot = path.slots[0];
 268                 if (ret != 0) {
 269                         if (slot == 0) {
 270                                 release_path(root, &path);
 271                                 break;
 272                         }
 273                         slot -= 1;
 274                 }
 275                 for (i = slot; i >= 0; i--) {
 276                         found = path.nodes[0]->leaf.items[i].key.objectid;
 277                         radix_tree_preload(GFP_KERNEL);
 278                         ret = radix_tree_insert(radix, found, (void *)found);
 279                         if (ret) {
 280                                 fprintf(stderr,
 281                                         "failed to insert %lu into radix\n",
 282                                         found);
 283                                 exit(1);
 284                         }
 285
 286                         radix_tree_preload_end();
 287                 }
 288                 release_path(root, &path);
 289                 key.objectid = found - 1;
 290                 if (key.objectid > found)
 291                         break;
 292         }
 293         return 0;
 294 }
 295 void sigstopper(int ignored)
 296 {
 297         keep_running = 0;
 298         fprintf(stderr, "caught exit signal, stopping\n");
 299 }
 300
 301 int print_usage(void)
 302 {
 303         printf("usage: tester [-ih] [-c count] [-f count]\n");
 304         printf("\t -c count -- iteration count after filling\n");
 305         printf("\t -f count -- run this many random inserts before starting\n");
 306         printf("\t -i       -- only do initial fill\n");
 307         printf("\t -h       -- this help text\n");
 308         exit(1);
 309 }
 310 int main(int ac, char **av)
 311 {
 312         RADIX_TREE(radix, GFP_KERNEL);
 313         struct ctree_root *root;
 314         int i;
 315         int ret;
 316         int count;
 317         int op;
 318         int iterations = 20000;
 319         int init_fill_count = 800000;
 320         int err = 0;
 321         int initial_only = 0;
 322         radix_tree_init();
 323         root = open_ctree("dbfile", &super);
 324         fill_radix(root, &radix);
 325
 326         signal(SIGTERM, sigstopper);
 327         signal(SIGINT, sigstopper);
 328
 329         for (i = 1 ; i < ac ; i++) {
 330                 if (strcmp(av[i], "-i") == 0) {
 331                         initial_only = 1;
 332                 } else if (strcmp(av[i], "-c") == 0) {
 333                         iterations = atoi(av[i+1]);
 334                         i++;
 335                 } else if (strcmp(av[i], "-f") == 0) {
 336                         init_fill_count = atoi(av[i+1]);
 337                         i++;
 338                 } else {
 339                         print_usage();
 340                 }
 341         }
 342         printf("initial fill\n");
 343         ret = fill_tree(root, &radix, init_fill_count);
 344         printf("starting run\n");
 345         if (ret) {
 346                 err = ret;
 347                 goto out;
 348         }
 349         if (initial_only == 1) {
 350                 goto out;
 351         }
 352         for (i = 0; i < iterations; i++) {
 353                 op = rand() % ARRAY_SIZE(ops);
 354                 count = rand() % 128;
 355                 if (i % 2000 == 0) {
 356                         printf("%d\n", i);
 357                         fflush(stdout);
 358                 }
 359                 if (i && i % 5000 == 0) {
 360                         printf("open & close, root level %d nritems %d\n",
 361                                 node_level(root->node->node.header.flags),
 362                                 root->node->node.header.nritems);
 363                         close_ctree(root, &super);
 364                         root = open_ctree("dbfile", &super);
 365                 }
 366                 while(count--) {
 367                         ret = ops[op](root, &radix);
 368                         if (ret) {
 369                                 fprintf(stderr, "op %d failed %d:%d\n",
 370                                         op, i, iterations);
 371                                 print_tree(root, root->node);
 372                                 fprintf(stderr, "op %d failed %d:%d\n",
 373                                         op, i, iterations);
 374                                 err = ret;
 375                                 goto out;
 376                         }
 377                         if (ops[op] == bulk_op)
 378                                 break;
 379                         if (keep_running == 0) {
 380                                 err = 0;
 381                                 goto out;
 382                         }
 383                 }
 384         }
 385 out:
 386         close_ctree(root, &super);
 387         return err;
 388 }
 389