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         btrfs_set_key_type(key, BTRFS_STRING_ITEM_KEY);
  22         key->offset = 0;
  23 again:
  24         ret = radix_tree_gang_lookup(root, (void **)res, num, 2);
  25         if (exists) {
  26                 if (ret == 0)
  27                         return -1;
  28                 num = res[0];
  29         } else if (ret != 0 && num == res[0]) {
  30                 num++;
  31                 if (ret > 1 && num == res[1]) {
  32                         num++;
  33                         goto again;
  34                 }
  35         }
  36         key->objectid = num;
  37         return 0;
  38 }
  39
  40 static int ins_one(struct btrfs_root *root, struct radix_tree_root *radix)
  41 {
  42         struct btrfs_path path;
  43         struct btrfs_key key;
  44         int ret;
  45         char buf[128];
  46         unsigned long oid;
  47         btrfs_init_path(&path);
  48         ret = setup_key(radix, &key, 0);
  49         sprintf(buf, "str-%Lu\n", key.objectid);
  50         ret = btrfs_insert_item(root, &key, buf, strlen(buf));
  51         if (ret)
  52                 goto error;
  53         oid = (unsigned long)key.objectid;
  54         radix_tree_preload(GFP_KERNEL);
  55         ret = radix_tree_insert(radix, oid, (void *)oid);
  56         radix_tree_preload_end();
  57         if (ret)
  58                 goto error;
  59         return ret;
  60 error:
  61         printf("failed to insert %Lu\n", key.objectid);
  62         return -1;
  63 }
  64
  65 static int insert_dup(struct btrfs_root *root, struct radix_tree_root *radix)
  66 {
  67         struct btrfs_path path;
  68         struct btrfs_key key;
  69         int ret;
  70         char buf[128];
  71         btrfs_init_path(&path);
  72         ret = setup_key(radix, &key, 1);
  73         if (ret < 0)
  74                 return 0;
  75         sprintf(buf, "str-%Lu\n", key.objectid);
  76         ret = btrfs_insert_item(root, &key, buf, strlen(buf));
  77         if (ret != -EEXIST) {
  78                 printf("insert on %Lu gave us %d\n", key.objectid, ret);
  79                 return 1;
  80         }
  81         return 0;
  82 }
  83
  84 static int del_one(struct btrfs_root *root, struct radix_tree_root *radix)
  85 {
  86         struct btrfs_path path;
  87         struct btrfs_key key;
  88         int ret;
  89         unsigned long *ptr;
  90         btrfs_init_path(&path);
  91         ret = setup_key(radix, &key, 1);
  92         if (ret < 0)
  93                 return 0;
  94         ret = btrfs_search_slot(root, &key, &path, -1, 1);
  95         if (ret)
  96                 goto error;
  97         ret = btrfs_del_item(root, &path);
  98         btrfs_release_path(root, &path);
  99         if (ret != 0)
 100                 goto error;
 101         ptr = radix_tree_delete(radix, key.objectid);
 102         if (!ptr)
 103                 goto error;
 104         return 0;
 105 error:
 106         printf("failed to delete %Lu\n", key.objectid);
 107         return -1;
 108 }
 109
 110 static int lookup_item(struct btrfs_root *root, struct radix_tree_root *radix)
 111 {
 112         struct btrfs_path path;
 113         struct btrfs_key key;
 114         int ret;
 115         btrfs_init_path(&path);
 116         ret = setup_key(radix, &key, 1);
 117         if (ret < 0)
 118                 return 0;
 119         ret = btrfs_search_slot(root, &key, &path, 0, 1);
 120         btrfs_release_path(root, &path);
 121         if (ret)
 122                 goto error;
 123         return 0;
 124 error:
 125         printf("unable to find key %Lu\n", key.objectid);
 126         return -1;
 127 }
 128
 129 static int lookup_enoent(struct btrfs_root *root, struct radix_tree_root *radix)
 130 {
 131         struct btrfs_path path;
 132         struct btrfs_key key;
 133         int ret;
 134         btrfs_init_path(&path);
 135         ret = setup_key(radix, &key, 0);
 136         if (ret < 0)
 137                 return ret;
 138         ret = btrfs_search_slot(root, &key, &path, 0, 0);
 139         btrfs_release_path(root, &path);
 140         if (ret <= 0)
 141                 goto error;
 142         return 0;
 143 error:
 144         printf("able to find key that should not exist %Lu\n", key.objectid);
 145         return -1;
 146 }
 147
 148 static int empty_tree(struct btrfs_root *root, struct radix_tree_root *radix,
 149                       int nr)
 150 {
 151         struct btrfs_path path;
 152         struct btrfs_key key;
 153         unsigned long found = 0;
 154         int ret;
 155         int slot;
 156         int *ptr;
 157         int count = 0;
 158
 159         key.offset = 0;
 160         key.flags = 0;
 161         btrfs_set_key_type(&key, BTRFS_STRING_ITEM_KEY);
 162         key.objectid = (unsigned long)-1;
 163         while(nr-- >= 0) {
 164                 btrfs_init_path(&path);
 165                 ret = btrfs_search_slot(root, &key, &path, -1, 1);
 166                 if (ret < 0) {
 167                         btrfs_release_path(root, &path);
 168                         return ret;
 169                 }
 170                 if (ret != 0) {
 171                         if (path.slots[0] == 0) {
 172                                 btrfs_release_path(root, &path);
 173                                 break;
 174                         }
 175                         path.slots[0] -= 1;
 176                 }
 177                 slot = path.slots[0];
 178                 found = btrfs_disk_key_objectid(
 179                                         &path.nodes[0]->leaf.items[slot].key);
 180                 ret = btrfs_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                 btrfs_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 btrfs_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 = btrfs_commit_transaction(root, &super);
 214                         if (ret) {
 215                                 fprintf(stderr, "fill commit failed\n");
 216                                 return ret;
 217                         }
 218                 }
 219                 if (i && 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 btrfs_root *root, struct radix_tree_root *radix)
 230 {
 231         int ret;
 232         int nr = rand() % 5000;
 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 btrfs_root *root, struct radix_tree_root *radix) =
 249         { ins_one, insert_dup, del_one, lookup_item,
 250           lookup_enoent, bulk_op };
 251
 252 static int fill_radix(struct btrfs_root *root, struct radix_tree_root *radix)
 253 {
 254         struct btrfs_path path;
 255         struct btrfs_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         btrfs_set_key_type(&key, BTRFS_STRING_ITEM_KEY);
 264         key.objectid = (unsigned long)-1;
 265         while(1) {
 266                 btrfs_init_path(&path);
 267                 ret = btrfs_search_slot(root, &key, &path, 0, 0);
 268                 if (ret < 0) {
 269                         btrfs_release_path(root, &path);
 270                         return ret;
 271                 }
 272                 slot = path.slots[0];
 273                 if (ret != 0) {
 274                         if (slot == 0) {
 275                                 btrfs_release_path(root, &path);
 276                                 break;
 277                         }
 278                         slot -= 1;
 279                 }
 280                 for (i = slot; i >= 0; i--) {
 281                         found = btrfs_disk_key_objectid(&path.nodes[0]->
 282                                                         leaf.items[i].key);
 283                         radix_tree_preload(GFP_KERNEL);
 284                         ret = radix_tree_insert(radix, found, (void *)found);
 285                         if (ret) {
 286                                 fprintf(stderr,
 287                                         "failed to insert %lu into radix\n",
 288                                         found);
 289                                 exit(1);
 290                         }
 291
 292                         radix_tree_preload_end();
 293                 }
 294                 btrfs_release_path(root, &path);
 295                 key.objectid = found - 1;
 296                 if (key.objectid > found)
 297                         break;
 298         }
 299         return 0;
 300 }
 301 void sigstopper(int ignored)
 302 {
 303         keep_running = 0;
 304         fprintf(stderr, "caught exit signal, stopping\n");
 305 }
 306
 307 int print_usage(void)
 308 {
 309         printf("usage: tester [-ih] [-c count] [-f count]\n");
 310         printf("\t -c count -- iteration count after filling\n");
 311         printf("\t -f count -- run this many random inserts before starting\n");
 312         printf("\t -i       -- only do initial fill\n");
 313         printf("\t -h       -- this help text\n");
 314         exit(1);
 315 }
 316 int main(int ac, char **av)
 317 {
 318         RADIX_TREE(radix, GFP_KERNEL);
 319         struct btrfs_root *root;
 320         int i;
 321         int ret;
 322         int count;
 323         int op;
 324         int iterations = 20000;
 325         int init_fill_count = 800000;
 326         int err = 0;
 327         int initial_only = 0;
 328         radix_tree_init();
 329         root = open_ctree("dbfile", &super);
 330         fill_radix(root, &radix);
 331
 332         signal(SIGTERM, sigstopper);
 333         signal(SIGINT, sigstopper);
 334
 335         for (i = 1 ; i < ac ; i++) {
 336                 if (strcmp(av[i], "-i") == 0) {
 337                         initial_only = 1;
 338                 } else if (strcmp(av[i], "-c") == 0) {
 339                         iterations = atoi(av[i+1]);
 340                         i++;
 341                 } else if (strcmp(av[i], "-f") == 0) {
 342                         init_fill_count = atoi(av[i+1]);
 343                         i++;
 344                 } else {
 345                         print_usage();
 346                 }
 347         }
 348         printf("initial fill\n");
 349         ret = fill_tree(root, &radix, init_fill_count);
 350         printf("starting run\n");
 351         if (ret) {
 352                 err = ret;
 353                 goto out;
 354         }
 355         if (initial_only == 1) {
 356                 goto out;
 357         }
 358         for (i = 0; i < iterations; i++) {
 359                 op = rand() % ARRAY_SIZE(ops);
 360                 count = rand() % 128;
 361                 if (i % 2000 == 0) {
 362                         printf("%d\n", i);
 363                         fflush(stdout);
 364                 }
 365                 if (i && i % 5000 == 0) {
 366                         printf("open & close, root level %d nritems %d\n",
 367                                 btrfs_header_level(&root->node->node.header),
 368                                 btrfs_header_nritems(&root->node->node.header));
 369                         close_ctree(root, &super);
 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                                 btrfs_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)
 384                                 break;
 385                         if (keep_running == 0) {
 386                                 err = 0;
 387                                 goto out;
 388                         }
 389                 }
 390         }
 391 out:
 392         close_ctree(root, &super);
 393         return err;
 394 }
 395