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