dir-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 <sys/types.h>
  23 #include <sys/stat.h>
  24 #include <unistd.h>
  25 #include "kerncompat.h"
  26 #include "radix-tree.h"
  27 #include "ctree.h"
  28 #include "disk-io.h"
  29 #include "print-tree.h"
  30 #include "hash.h"
  31 #include "transaction.h"
  32
  33 int keep_running = 1;
  34 struct btrfs_super_block super;
  35 static u64 dir_oid = 0;
  36 static u64 file_oid = 33778;
  37
  38 static int find_num(struct radix_tree_root *root, unsigned long *num_ret,
  39                      int exists)
  40 {
  41         unsigned long num = rand();
  42         unsigned long res[2];
  43         int ret;
  44
  45 again:
  46         ret = radix_tree_gang_lookup(root, (void **)res, num, 2);
  47         if (exists) {
  48                 if (ret == 0)
  49                         return -1;
  50                 num = res[0];
  51         } else if (ret != 0 && num == res[0]) {
  52                 num++;
  53                 if (ret > 1 && num == res[1]) {
  54                         num++;
  55                         goto again;
  56                 }
  57         }
  58         *num_ret = num;
  59         return 0;
  60 }
  61
  62 static void initial_inode_init(struct btrfs_root *root,
  63                                struct btrfs_inode_item *inode_item)
  64 {
  65         memset(inode_item, 0, sizeof(*inode_item));
  66         btrfs_set_inode_generation(inode_item, root->fs_info->generation);
  67         btrfs_set_inode_mode(inode_item, S_IFREG | 0700);
  68 }
  69
  70 static int ins_one(struct btrfs_trans_handle *trans, struct btrfs_root *root,
  71                    struct radix_tree_root *radix)
  72 {
  73         int ret;
  74         char buf[128];
  75         unsigned long oid;
  76         u64 objectid;
  77         struct btrfs_path path;
  78         struct btrfs_key inode_map;
  79         struct btrfs_inode_item inode_item;
  80
  81         find_num(radix, &oid, 0);
  82         sprintf(buf, "str-%lu", oid);
  83
  84         ret = btrfs_find_free_objectid(trans, root, dir_oid + 1, &objectid);
  85         if (ret)
  86                 goto error;
  87
  88         inode_map.objectid = objectid;
  89         inode_map.flags = 0;
  90         btrfs_set_key_type(&inode_map, BTRFS_INODE_ITEM_KEY);
  91         inode_map.offset = 0;
  92
  93         initial_inode_init(root, &inode_item);
  94         ret = btrfs_insert_inode(trans, root, objectid, &inode_item);
  95         if (ret)
  96                 goto error;
  97         ret = btrfs_insert_dir_item(trans, root, buf, strlen(buf), dir_oid,
  98                                     &inode_map, BTRFS_FT_UNKNOWN);
  99         if (ret)
 100                 goto error;
 101
 102         radix_tree_preload(GFP_KERNEL);
 103         ret = radix_tree_insert(radix, oid, (void *)oid);
 104         radix_tree_preload_end();
 105         if (ret)
 106                 goto error;
 107         return ret;
 108 error:
 109         if (ret != -EEXIST)
 110                 goto fatal;
 111
 112         /*
 113          * if we got an EEXIST, it may be due to hash collision, double
 114          * check
 115          */
 116         btrfs_init_path(&path);
 117         ret = btrfs_lookup_dir_item(trans, root, &path, dir_oid, buf,
 118                                     strlen(buf), 0);
 119         if (ret)
 120                 goto fatal_release;
 121         if (!btrfs_match_dir_item_name(root, &path, buf, strlen(buf))) {
 122                 struct btrfs_dir_item *di;
 123                 char *found;
 124                 u32 found_len;
 125                 u64 myhash;
 126                 u64 foundhash;
 127
 128                 di = btrfs_item_ptr(&path.nodes[0]->leaf, path.slots[0],
 129                                     struct btrfs_dir_item);
 130                 found = (char *)(di + 1);
 131                 found_len = btrfs_dir_name_len(di);
 132                 myhash = btrfs_name_hash(buf, strlen(buf));
 133                 foundhash = btrfs_name_hash(found, found_len);
 134                 if (myhash != foundhash)
 135                         goto fatal_release;
 136                 btrfs_release_path(root, &path);
 137                 return 0;
 138         }
 139 fatal_release:
 140         btrfs_release_path(root, &path);
 141 fatal:
 142         printf("failed to insert %lu ret %d\n", oid, ret);
 143         return -1;
 144 }
 145
 146 static int insert_dup(struct btrfs_trans_handle *trans, struct btrfs_root
 147                       *root, struct radix_tree_root *radix)
 148 {
 149         int ret;
 150         char buf[128];
 151         unsigned long oid;
 152         struct btrfs_key key;
 153
 154         ret = find_num(radix, &oid, 1);
 155         if (ret < 0)
 156                 return 0;
 157         sprintf(buf, "str-%lu", oid);
 158
 159         key.objectid = file_oid;
 160         key.flags = 0;
 161         btrfs_set_key_type(&key, BTRFS_INODE_ITEM_KEY);
 162         key.offset = 0;
 163         ret = btrfs_insert_dir_item(trans, root, buf, strlen(buf), dir_oid,
 164                                     &key, BTRFS_FT_UNKNOWN);
 165         if (ret != -EEXIST) {
 166                 printf("insert on %s gave us %d\n", buf, ret);
 167                 return 1;
 168         }
 169         return 0;
 170 }
 171
 172 static int del_dir_item(struct btrfs_trans_handle *trans,
 173                         struct btrfs_root *root,
 174                         struct radix_tree_root *radix,
 175                         unsigned long radix_index,
 176                         struct btrfs_path *path)
 177 {
 178         int ret;
 179         unsigned long *ptr;
 180         u64 file_objectid;
 181         struct btrfs_dir_item *di;
 182
 183         /* find the inode number of the file */
 184         di = btrfs_item_ptr(&path->nodes[0]->leaf, path->slots[0],
 185                             struct btrfs_dir_item);
 186         file_objectid = btrfs_disk_key_objectid(&di->location);
 187
 188         /* delete the directory item */
 189         ret = btrfs_del_item(trans, root, path);
 190         if (ret)
 191                 goto out_release;
 192         btrfs_release_path(root, path);
 193
 194         /* delete the inode */
 195         btrfs_init_path(path);
 196         ret = btrfs_lookup_inode(trans, root, path, file_objectid, -1);
 197         if (ret)
 198                 goto out_release;
 199         ret = btrfs_del_item(trans, root, path);
 200         if (ret)
 201                 goto out_release;
 202         btrfs_release_path(root, path);
 203
 204         if (root->fs_info->last_inode_alloc > file_objectid)
 205                 root->fs_info->last_inode_alloc = file_objectid;
 206         ptr = radix_tree_delete(radix, radix_index);
 207         if (!ptr) {
 208                 ret = -5555;
 209                 goto out;
 210         }
 211         return 0;
 212 out_release:
 213         btrfs_release_path(root, path);
 214 out:
 215         printf("failed to delete %lu %d\n", radix_index, ret);
 216         return -1;
 217 }
 218
 219 static int del_one(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 220                    struct radix_tree_root *radix)
 221 {
 222         int ret;
 223         char buf[128];
 224         unsigned long oid;
 225         struct btrfs_path path;
 226
 227         ret = find_num(radix, &oid, 1);
 228         if (ret < 0)
 229                 return 0;
 230         sprintf(buf, "str-%lu", oid);
 231         btrfs_init_path(&path);
 232         ret = btrfs_lookup_dir_item(trans, root, &path, dir_oid, buf,
 233                                     strlen(buf), -1);
 234         if (ret)
 235                 goto out_release;
 236
 237         ret = del_dir_item(trans, root, radix, oid, &path);
 238         if (ret)
 239                 goto out_release;
 240         return ret;
 241 out_release:
 242         btrfs_release_path(root, &path);
 243         printf("failed to delete %lu %d\n", oid, ret);
 244         return -1;
 245 }
 246
 247 static int lookup_item(struct btrfs_trans_handle *trans, struct btrfs_root
 248                        *root, struct radix_tree_root *radix)
 249 {
 250         struct btrfs_path path;
 251         char buf[128];
 252         int ret;
 253         unsigned long oid;
 254         u64 objectid;
 255         struct btrfs_dir_item *di;
 256
 257         ret = find_num(radix, &oid, 1);
 258         if (ret < 0)
 259                 return 0;
 260         sprintf(buf, "str-%lu", oid);
 261         btrfs_init_path(&path);
 262         ret = btrfs_lookup_dir_item(trans, root, &path, dir_oid, buf,
 263                                     strlen(buf), 0);
 264         if (!ret) {
 265                 di = btrfs_item_ptr(&path.nodes[0]->leaf, path.slots[0],
 266                                     struct btrfs_dir_item);
 267                 objectid = btrfs_disk_key_objectid(&di->location);
 268         }
 269         btrfs_release_path(root, &path);
 270         if (ret) {
 271                 printf("unable to find key %lu\n", oid);
 272                 return -1;
 273         }
 274         return 0;
 275 }
 276
 277 static int lookup_enoent(struct btrfs_trans_handle *trans, struct btrfs_root
 278                          *root, struct radix_tree_root *radix)
 279 {
 280         struct btrfs_path path;
 281         char buf[128];
 282         int ret;
 283         unsigned long oid;
 284
 285         ret = find_num(radix, &oid, 0);
 286         if (ret < 0)
 287                 return 0;
 288         sprintf(buf, "str-%lu", oid);
 289         btrfs_init_path(&path);
 290         ret = btrfs_lookup_dir_item(trans, root, &path, dir_oid, buf,
 291                                     strlen(buf), 0);
 292         btrfs_release_path(root, &path);
 293         if (!ret) {
 294                 printf("able to find key that should not exist %lu\n", oid);
 295                 return -1;
 296         }
 297         return 0;
 298 }
 299
 300 static int empty_tree(struct btrfs_trans_handle *trans, struct btrfs_root
 301                       *root, struct radix_tree_root *radix, int nr)
 302 {
 303         struct btrfs_path path;
 304         struct btrfs_key key;
 305         unsigned long found = 0;
 306         u32 found_len;
 307         int ret;
 308         int slot;
 309         int count = 0;
 310         char buf[128];
 311         struct btrfs_dir_item *di;
 312
 313         key.offset = (u64)-1;
 314         key.flags = 0;
 315         btrfs_set_key_type(&key, BTRFS_DIR_ITEM_KEY);
 316         key.objectid = dir_oid;
 317         while(nr-- >= 0) {
 318                 btrfs_init_path(&path);
 319                 ret = btrfs_search_slot(trans, root, &key, &path, -1, 1);
 320                 if (ret < 0) {
 321                         btrfs_release_path(root, &path);
 322                         return ret;
 323                 }
 324                 if (ret != 0) {
 325                         if (path.slots[0] == 0) {
 326                                 btrfs_release_path(root, &path);
 327                                 break;
 328                         }
 329                         path.slots[0] -= 1;
 330                 }
 331                 slot = path.slots[0];
 332                 di = btrfs_item_ptr(&path.nodes[0]->leaf, slot,
 333                                     struct btrfs_dir_item);
 334                 found_len = btrfs_dir_name_len(di);
 335                 memcpy(buf, (char *)(di + 1), found_len);
 336                 BUG_ON(found_len > 128);
 337                 buf[found_len] = '\0';
 338                 found = atoi(buf + 4);
 339                 ret = del_dir_item(trans, root, radix, found, &path);
 340                 count++;
 341                 if (ret) {
 342                         fprintf(stderr,
 343                                 "failed to remove %lu from tree\n",
 344                                 found);
 345                         return -1;
 346                 }
 347                 if (!keep_running)
 348                         break;
 349         }
 350         return 0;
 351         fprintf(stderr, "failed to delete from the radix %lu\n", found);
 352         return -1;
 353 }
 354
 355 static int fill_tree(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 356                      struct radix_tree_root *radix, int count)
 357 {
 358         int i;
 359         int ret = 0;
 360         for (i = 0; i < count; i++) {
 361                 ret = ins_one(trans, root, radix);
 362                 if (ret) {
 363                         fprintf(stderr, "fill failed\n");
 364                         goto out;
 365                 }
 366                 if (i % 1000 == 0) {
 367                         ret = btrfs_commit_transaction(trans, root, &super);
 368                         if (ret) {
 369                                 fprintf(stderr, "fill commit failed\n");
 370                                 return ret;
 371                         }
 372                 }
 373                 if (i && i % 10000 == 0) {
 374                         printf("bigfill %d\n", i);
 375                 }
 376                 if (!keep_running)
 377                         break;
 378         }
 379 out:
 380         return ret;
 381 }
 382
 383 static int bulk_op(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 384                    struct radix_tree_root *radix)
 385 {
 386         int ret;
 387         int nr = rand() % 5000;
 388         static int run_nr = 0;
 389
 390         /* do the bulk op much less frequently */
 391         if (run_nr++ % 100)
 392                 return 0;
 393         ret = empty_tree(trans, root, radix, nr);
 394         if (ret)
 395                 return ret;
 396         ret = fill_tree(trans, root, radix, nr);
 397         if (ret)
 398                 return ret;
 399         return 0;
 400 }
 401
 402
 403 int (*ops[])(struct btrfs_trans_handle *trans, struct btrfs_root *root, struct
 404              radix_tree_root *radix) =
 405         { ins_one, insert_dup, del_one, lookup_item,
 406           lookup_enoent, bulk_op };
 407
 408 void sigstopper(int ignored)
 409 {
 410         keep_running = 0;
 411         fprintf(stderr, "caught exit signal, stopping\n");
 412 }
 413
 414 int print_usage(void)
 415 {
 416         printf("usage: tester [-ih] [-c count] [-f count]\n");
 417         printf("\t -c count -- iteration count after filling\n");
 418         printf("\t -f count -- run this many random inserts before starting\n");
 419         printf("\t -i       -- only do initial fill\n");
 420         printf("\t -h       -- this help text\n");
 421         exit(1);
 422 }
 423 int main(int ac, char **av)
 424 {
 425         RADIX_TREE(radix, GFP_KERNEL);
 426         struct btrfs_root *root;
 427         int i;
 428         int ret;
 429         int count;
 430         int op;
 431         int iterations = 20000;
 432         int init_fill_count = 800000;
 433         int err = 0;
 434         int initial_only = 0;
 435         struct btrfs_trans_handle *trans;
 436         radix_tree_init();
 437
 438         root = open_ctree(av[ac-1], &super, 0);
 439
 440         if (!root) {
 441                 fprintf(stderr, "Open ctree failed\n");
 442                 return 1;
 443         }
 444
 445         trans = btrfs_start_transaction(root, 1);
 446
 447         dir_oid = btrfs_super_root_dir(&super);
 448
 449         signal(SIGTERM, sigstopper);
 450         signal(SIGINT, sigstopper);
 451
 452         for (i = 1 ; i < ac - 1; i++) {
 453                 if (strcmp(av[i], "-i") == 0) {
 454                         initial_only = 1;
 455                 } else if (strcmp(av[i], "-c") == 0) {
 456                         iterations = atoi(av[i+1]);
 457                         i++;
 458                 } else if (strcmp(av[i], "-f") == 0) {
 459                         init_fill_count = atoi(av[i+1]);
 460                         i++;
 461                 } else {
 462                         print_usage();
 463                 }
 464         }
 465         printf("initial fill\n");
 466         ret = fill_tree(trans, root, &radix, init_fill_count);
 467         printf("starting run\n");
 468         if (ret) {
 469                 err = ret;
 470                 goto out;
 471         }
 472         if (initial_only == 1) {
 473                 goto out;
 474         }
 475         for (i = 0; i < iterations; i++) {
 476                 op = rand() % ARRAY_SIZE(ops);
 477                 count = rand() % 128;
 478                 if (i % 2000 == 0) {
 479                         printf("%d\n", i);
 480                         fflush(stdout);
 481                 }
 482                 if (i && i % 5000 == 0) {
 483                         printf("open & close, root level %d nritems %d\n",
 484                                 btrfs_header_level(&root->node->node.header),
 485                                 btrfs_header_nritems(&root->node->node.header));
 486                         close_ctree(root, &super);
 487                         root = open_ctree("dbfile", &super, 0);
 488
 489                         if (!root) {
 490                                 fprintf(stderr, "Open ctree failed\n");
 491                                 return 1;
 492                         }
 493                 }
 494                 while(count--) {
 495                         ret = ops[op](trans, root, &radix);
 496                         if (ret) {
 497                                 fprintf(stderr, "op %d failed %d:%d\n",
 498                                         op, i, iterations);
 499                                 btrfs_print_tree(root, root->node, 1);
 500                                 fprintf(stderr, "op %d failed %d:%d\n",
 501                                         op, i, iterations);
 502                                 err = ret;
 503                                 goto out;
 504                         }
 505                         if (ops[op] == bulk_op)
 506                                 break;
 507                         if (keep_running == 0) {
 508                                 err = 0;
 509                                 goto out;
 510                         }
 511                 }
 512         }
 513 out:
 514         close_ctree(root, &super);
 515         return err;
 516 }
 517