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