random-test.c

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