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 btrfs_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 btrfs_root *root, struct radix_tree_root *radix)
  40 {
  41         struct btrfs_path path;
  42         struct btrfs_key key;
  43         int ret;
  44         char buf[128];
  45         unsigned long oid;
  46         btrfs_init_path(&path);
  47         ret = setup_key(radix, &key, 0);
  48         sprintf(buf, "str-%Lu\n", key.objectid);
  49         ret = btrfs_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 btrfs_root *root, struct radix_tree_root *radix)
  65 {
  66         struct btrfs_path path;
  67         struct btrfs_key key;
  68         int ret;
  69         char buf[128];
  70         btrfs_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 = btrfs_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 btrfs_root *root, struct radix_tree_root *radix)
  84 {
  85         struct btrfs_path path;
  86         struct btrfs_key key;
  87         int ret;
  88         unsigned long *ptr;
  89         btrfs_init_path(&path);
  90         ret = setup_key(radix, &key, 1);
  91         if (ret < 0)
  92                 return 0;
  93         ret = btrfs_search_slot(root, &key, &path, -1, 1);
  94         if (ret)
  95                 goto error;
  96         ret = btrfs_del_item(root, &path);
  97         btrfs_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 btrfs_root *root, struct radix_tree_root *radix)
 110 {
 111         struct btrfs_path path;
 112         struct btrfs_key key;
 113         int ret;
 114         btrfs_init_path(&path);
 115         ret = setup_key(radix, &key, 1);
 116         if (ret < 0)
 117                 return 0;
 118         ret = btrfs_search_slot(root, &key, &path, 0, 1);
 119         btrfs_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 btrfs_root *root, struct radix_tree_root *radix)
 129 {
 130         struct btrfs_path path;
 131         struct btrfs_key key;
 132         int ret;
 133         btrfs_init_path(&path);
 134         ret = setup_key(radix, &key, 0);
 135         if (ret < 0)
 136                 return ret;
 137         ret = btrfs_search_slot(root, &key, &path, 0, 0);
 138         btrfs_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 btrfs_root *root, struct radix_tree_root *radix,
 148                       int nr)
 149 {
 150         struct btrfs_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                 btrfs_init_path(&path);
 163                 ret = btrfs_search_slot(root, &key, &path, -1, 1);
 164                 if (ret < 0) {
 165                         btrfs_release_path(root, &path);
 166                         return ret;
 167                 }
 168                 if (ret != 0) {
 169                         if (path.slots[0] == 0) {
 170                                 btrfs_release_path(root, &path);
 171                                 break;
 172                         }
 173                         path.slots[0] -= 1;
 174                 }
 175                 slot = path.slots[0];
 176                 found=btrfs_key_objectid(&path.nodes[0]->leaf.items[slot].key);
 177                 ret = btrfs_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                 btrfs_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 btrfs_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 = btrfs_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 btrfs_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 btrfs_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 btrfs_root *root, struct radix_tree_root *radix)
 250 {
 251         struct btrfs_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                 btrfs_init_path(&path);
 263                 ret = btrfs_search_slot(root, &key, &path, 0, 0);
 264                 if (ret < 0) {
 265                         btrfs_release_path(root, &path);
 266                         return ret;
 267                 }
 268                 slot = path.slots[0];
 269                 if (ret != 0) {
 270                         if (slot == 0) {
 271                                 btrfs_release_path(root, &path);
 272                                 break;
 273                         }
 274                         slot -= 1;
 275                 }
 276                 for (i = slot; i >= 0; i--) {
 277                         found = btrfs_key_objectid(&path.nodes[0]->
 278                                                    leaf.items[i].key);
 279                         radix_tree_preload(GFP_KERNEL);
 280                         ret = radix_tree_insert(radix, found, (void *)found);
 281                         if (ret) {
 282                                 fprintf(stderr,
 283                                         "failed to insert %lu into radix\n",
 284                                         found);
 285                                 exit(1);
 286                         }
 287
 288                         radix_tree_preload_end();
 289                 }
 290                 btrfs_release_path(root, &path);
 291                 key.objectid = found - 1;
 292                 if (key.objectid > found)
 293                         break;
 294         }
 295         return 0;
 296 }
 297 void sigstopper(int ignored)
 298 {
 299         keep_running = 0;
 300         fprintf(stderr, "caught exit signal, stopping\n");
 301 }
 302
 303 int print_usage(void)
 304 {
 305         printf("usage: tester [-ih] [-c count] [-f count]\n");
 306         printf("\t -c count -- iteration count after filling\n");
 307         printf("\t -f count -- run this many random inserts before starting\n");
 308         printf("\t -i       -- only do initial fill\n");
 309         printf("\t -h       -- this help text\n");
 310         exit(1);
 311 }
 312 int main(int ac, char **av)
 313 {
 314         RADIX_TREE(radix, GFP_KERNEL);
 315         struct btrfs_root *root;
 316         int i;
 317         int ret;
 318         int count;
 319         int op;
 320         int iterations = 20000;
 321         int init_fill_count = 800000;
 322         int err = 0;
 323         int initial_only = 0;
 324         radix_tree_init();
 325         root = open_ctree("dbfile", &super);
 326         fill_radix(root, &radix);
 327
 328         signal(SIGTERM, sigstopper);
 329         signal(SIGINT, sigstopper);
 330
 331         for (i = 1 ; i < ac ; i++) {
 332                 if (strcmp(av[i], "-i") == 0) {
 333                         initial_only = 1;
 334                 } else if (strcmp(av[i], "-c") == 0) {
 335                         iterations = atoi(av[i+1]);
 336                         i++;
 337                 } else if (strcmp(av[i], "-f") == 0) {
 338                         init_fill_count = atoi(av[i+1]);
 339                         i++;
 340                 } else {
 341                         print_usage();
 342                 }
 343         }
 344         printf("initial fill\n");
 345         ret = fill_tree(root, &radix, init_fill_count);
 346         printf("starting run\n");
 347         if (ret) {
 348                 err = ret;
 349                 goto out;
 350         }
 351         if (initial_only == 1) {
 352                 goto out;
 353         }
 354         for (i = 0; i < iterations; i++) {
 355                 op = rand() % ARRAY_SIZE(ops);
 356                 count = rand() % 128;
 357                 if (i % 2000 == 0) {
 358                         printf("%d\n", i);
 359                         fflush(stdout);
 360                 }
 361                 if (i && i % 5000 == 0) {
 362                         printf("open & close, root level %d nritems %d\n",
 363                                 btrfs_header_level(&root->node->node.header),
 364                                 btrfs_header_nritems(&root->node->node.header));
 365                         close_ctree(root, &super);
 366                         root = open_ctree("dbfile", &super);
 367                 }
 368                 while(count--) {
 369                         ret = ops[op](root, &radix);
 370                         if (ret) {
 371                                 fprintf(stderr, "op %d failed %d:%d\n",
 372                                         op, i, iterations);
 373                                 btrfs_print_tree(root, root->node);
 374                                 fprintf(stderr, "op %d failed %d:%d\n",
 375                                         op, i, iterations);
 376                                 err = ret;
 377                                 goto out;
 378                         }
 379                         if (ops[op] == bulk_op)
 380                                 break;
 381                         if (keep_running == 0) {
 382                                 err = 0;
 383                                 goto out;
 384                         }
 385                 }
 386         }
 387 out:
 388         close_ctree(root, &super);
 389         return err;
 390 }
 391