fs/btrfs/tree-log.c

   1 /*
   2  * Copyright (C) 2008 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 <linux/sched.h>
  20 #include "ctree.h"
  21 #include "transaction.h"
  22 #include "disk-io.h"
  23 #include "locking.h"
  24 #include "print-tree.h"
  25 #include "compat.h"
  26 #include "tree-log.h"
  27
  28 /* magic values for the inode_only field in btrfs_log_inode:
  29  *
  30  * LOG_INODE_ALL means to log everything
  31  * LOG_INODE_EXISTS means to log just enough to recreate the inode
  32  * during log replay
  33  */
  34 #define LOG_INODE_ALL 0
  35 #define LOG_INODE_EXISTS 1
  36
  37 /*
  38  * directory trouble cases
  39  *
  40  * 1) on rename or unlink, if the inode being unlinked isn't in the fsync
  41  * log, we must force a full commit before doing an fsync of the directory
  42  * where the unlink was done.
  43  * ---> record transid of last unlink/rename per directory
  44  *
  45  * mkdir foo/some_dir
  46  * normal commit
  47  * rename foo/some_dir foo2/some_dir
  48  * mkdir foo/some_dir
  49  * fsync foo/some_dir/some_file
  50  *
  51  * The fsync above will unlink the original some_dir without recording
  52  * it in its new location (foo2).  After a crash, some_dir will be gone
  53  * unless the fsync of some_file forces a full commit
  54  *
  55  * 2) we must log any new names for any file or dir that is in the fsync
  56  * log. ---> check inode while renaming/linking.
  57  *
  58  * 2a) we must log any new names for any file or dir during rename
  59  * when the directory they are being removed from was logged.
  60  * ---> check inode and old parent dir during rename
  61  *
  62  *  2a is actually the more important variant.  With the extra logging
  63  *  a crash might unlink the old name without recreating the new one
  64  *
  65  * 3) after a crash, we must go through any directories with a link count
  66  * of zero and redo the rm -rf
  67  *
  68  * mkdir f1/foo
  69  * normal commit
  70  * rm -rf f1/foo
  71  * fsync(f1)
  72  *
  73  * The directory f1 was fully removed from the FS, but fsync was never
  74  * called on f1, only its parent dir.  After a crash the rm -rf must
  75  * be replayed.  This must be able to recurse down the entire
  76  * directory tree.  The inode link count fixup code takes care of the
  77  * ugly details.
  78  */
  79
  80 /*
  81  * stages for the tree walking.  The first
  82  * stage (0) is to only pin down the blocks we find
  83  * the second stage (1) is to make sure that all the inodes
  84  * we find in the log are created in the subvolume.
  85  *
  86  * The last stage is to deal with directories and links and extents
  87  * and all the other fun semantics
  88  */
  89 #define LOG_WALK_PIN_ONLY 0
  90 #define LOG_WALK_REPLAY_INODES 1
  91 #define LOG_WALK_REPLAY_ALL 2
  92
  93 static int btrfs_log_inode(struct btrfs_trans_handle *trans,
  94                              struct btrfs_root *root, struct inode *inode,
  95                              int inode_only);
  96 static int link_to_fixup_dir(struct btrfs_trans_handle *trans,
  97                              struct btrfs_root *root,
  98                              struct btrfs_path *path, u64 objectid);
  99 static noinline int replay_dir_deletes(struct btrfs_trans_handle *trans,
 100                                        struct btrfs_root *root,
 101                                        struct btrfs_root *log,
 102                                        struct btrfs_path *path,
 103                                        u64 dirid, int del_all);
 104
 105 /*
 106  * tree logging is a special write ahead log used to make sure that
 107  * fsyncs and O_SYNCs can happen without doing full tree commits.
 108  *
 109  * Full tree commits are expensive because they require commonly
 110  * modified blocks to be recowed, creating many dirty pages in the
 111  * extent tree an 4x-6x higher write load than ext3.
 112  *
 113  * Instead of doing a tree commit on every fsync, we use the
 114  * key ranges and transaction ids to find items for a given file or directory
 115  * that have changed in this transaction.  Those items are copied into
 116  * a special tree (one per subvolume root), that tree is written to disk
 117  * and then the fsync is considered complete.
 118  *
 119  * After a crash, items are copied out of the log-tree back into the
 120  * subvolume tree.  Any file data extents found are recorded in the extent
 121  * allocation tree, and the log-tree freed.
 122  *
 123  * The log tree is read three times, once to pin down all the extents it is
 124  * using in ram and once, once to create all the inodes logged in the tree
 125  * and once to do all the other items.
 126  */
 127
 128 /*
 129  * start a sub transaction and setup the log tree
 130  * this increments the log tree writer count to make the people
 131  * syncing the tree wait for us to finish
 132  */
 133 static int start_log_trans(struct btrfs_trans_handle *trans,
 134                            struct btrfs_root *root)
 135 {
 136         int ret;
 137
 138         mutex_lock(&root->log_mutex);
 139         if (root->log_root) {
 140                 if (!root->log_start_pid) {
 141                         root->log_start_pid = current->pid;
 142                         root->log_multiple_pids = false;
 143                 } else if (root->log_start_pid != current->pid) {
 144                         root->log_multiple_pids = true;
 145                 }
 146
 147                 root->log_batch++;
 148                 atomic_inc(&root->log_writers);
 149                 mutex_unlock(&root->log_mutex);
 150                 return 0;
 151         }
 152         root->log_multiple_pids = false;
 153         root->log_start_pid = current->pid;
 154         mutex_lock(&root->fs_info->tree_log_mutex);
 155         if (!root->fs_info->log_root_tree) {
 156                 ret = btrfs_init_log_root_tree(trans, root->fs_info);
 157                 BUG_ON(ret);
 158         }
 159         if (!root->log_root) {
 160                 ret = btrfs_add_log_tree(trans, root);
 161                 BUG_ON(ret);
 162         }
 163         mutex_unlock(&root->fs_info->tree_log_mutex);
 164         root->log_batch++;
 165         atomic_inc(&root->log_writers);
 166         mutex_unlock(&root->log_mutex);
 167         return 0;
 168 }
 169
 170 /*
 171  * returns 0 if there was a log transaction running and we were able
 172  * to join, or returns -ENOENT if there were not transactions
 173  * in progress
 174  */
 175 static int join_running_log_trans(struct btrfs_root *root)
 176 {
 177         int ret = -ENOENT;
 178
 179         smp_mb();
 180         if (!root->log_root)
 181                 return -ENOENT;
 182
 183         mutex_lock(&root->log_mutex);
 184         if (root->log_root) {
 185                 ret = 0;
 186                 atomic_inc(&root->log_writers);
 187         }
 188         mutex_unlock(&root->log_mutex);
 189         return ret;
 190 }
 191
 192 /*
 193  * This either makes the current running log transaction wait
 194  * until you call btrfs_end_log_trans() or it makes any future
 195  * log transactions wait until you call btrfs_end_log_trans()
 196  */
 197 int btrfs_pin_log_trans(struct btrfs_root *root)
 198 {
 199         int ret = -ENOENT;
 200
 201         mutex_lock(&root->log_mutex);
 202         atomic_inc(&root->log_writers);
 203         mutex_unlock(&root->log_mutex);
 204         return ret;
 205 }
 206
 207 /*
 208  * indicate we're done making changes to the log tree
 209  * and wake up anyone waiting to do a sync
 210  */
 211 int btrfs_end_log_trans(struct btrfs_root *root)
 212 {
 213         if (atomic_dec_and_test(&root->log_writers)) {
 214                 smp_mb();
 215                 if (waitqueue_active(&root->log_writer_wait))
 216                         wake_up(&root->log_writer_wait);
 217         }
 218         return 0;
 219 }
 220
 221
 222 /*
 223  * the walk control struct is used to pass state down the chain when
 224  * processing the log tree.  The stage field tells us which part
 225  * of the log tree processing we are currently doing.  The others
 226  * are state fields used for that specific part
 227  */
 228 struct walk_control {
 229         /* should we free the extent on disk when done?  This is used
 230          * at transaction commit time while freeing a log tree
 231          */
 232         int free;
 233
 234         /* should we write out the extent buffer?  This is used
 235          * while flushing the log tree to disk during a sync
 236          */
 237         int write;
 238
 239         /* should we wait for the extent buffer io to finish?  Also used
 240          * while flushing the log tree to disk for a sync
 241          */
 242         int wait;
 243
 244         /* pin only walk, we record which extents on disk belong to the
 245          * log trees
 246          */
 247         int pin;
 248
 249         /* what stage of the replay code we're currently in */
 250         int stage;
 251
 252         /* the root we are currently replaying */
 253         struct btrfs_root *replay_dest;
 254
 255         /* the trans handle for the current replay */
 256         struct btrfs_trans_handle *trans;
 257
 258         /* the function that gets used to process blocks we find in the
 259          * tree.  Note the extent_buffer might not be up to date when it is
 260          * passed in, and it must be checked or read if you need the data
 261          * inside it
 262          */
 263         int (*process_func)(struct btrfs_root *log, struct extent_buffer *eb,
 264                             struct walk_control *wc, u64 gen);
 265 };
 266
 267 /*
 268  * process_func used to pin down extents, write them or wait on them
 269  */
 270 static int process_one_buffer(struct btrfs_root *log,
 271                               struct extent_buffer *eb,
 272                               struct walk_control *wc, u64 gen)
 273 {
 274         if (wc->pin)
 275                 btrfs_pin_extent(log->fs_info->extent_root,
 276                                  eb->start, eb->len, 0);
 277
 278         if (btrfs_buffer_uptodate(eb, gen)) {
 279                 if (wc->write)
 280                         btrfs_write_tree_block(eb);
 281                 if (wc->wait)
 282                         btrfs_wait_tree_block_writeback(eb);
 283         }
 284         return 0;
 285 }
 286
 287 /*
 288  * Item overwrite used by replay and tree logging.  eb, slot and key all refer
 289  * to the src data we are copying out.
 290  *
 291  * root is the tree we are copying into, and path is a scratch
 292  * path for use in this function (it should be released on entry and
 293  * will be released on exit).
 294  *
 295  * If the key is already in the destination tree the existing item is
 296  * overwritten.  If the existing item isn't big enough, it is extended.
 297  * If it is too large, it is truncated.
 298  *
 299  * If the key isn't in the destination yet, a new item is inserted.
 300  */
 301 static noinline int overwrite_item(struct btrfs_trans_handle *trans,
 302                                    struct btrfs_root *root,
 303                                    struct btrfs_path *path,
 304                                    struct extent_buffer *eb, int slot,
 305                                    struct btrfs_key *key)
 306 {
 307         int ret;
 308         u32 item_size;
 309         u64 saved_i_size = 0;
 310         int save_old_i_size = 0;
 311         unsigned long src_ptr;
 312         unsigned long dst_ptr;
 313         int overwrite_root = 0;
 314
 315         if (root->root_key.objectid != BTRFS_TREE_LOG_OBJECTID)
 316                 overwrite_root = 1;
 317
 318         item_size = btrfs_item_size_nr(eb, slot);
 319         src_ptr = btrfs_item_ptr_offset(eb, slot);
 320
 321         /* look for the key in the destination tree */
 322         ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
 323         if (ret == 0) {
 324                 char *src_copy;
 325                 char *dst_copy;
 326                 u32 dst_size = btrfs_item_size_nr(path->nodes[0],
 327                                                   path->slots[0]);
 328                 if (dst_size != item_size)
 329                         goto insert;
 330
 331                 if (item_size == 0) {
 332                         btrfs_release_path(root, path);
 333                         return 0;
 334                 }
 335                 dst_copy = kmalloc(item_size, GFP_NOFS);
 336                 src_copy = kmalloc(item_size, GFP_NOFS);
 337
 338                 read_extent_buffer(eb, src_copy, src_ptr, item_size);
 339
 340                 dst_ptr = btrfs_item_ptr_offset(path->nodes[0], path->slots[0]);
 341                 read_extent_buffer(path->nodes[0], dst_copy, dst_ptr,
 342                                    item_size);
 343                 ret = memcmp(dst_copy, src_copy, item_size);
 344
 345                 kfree(dst_copy);
 346                 kfree(src_copy);
 347                 /*
 348                  * they have the same contents, just return, this saves
 349                  * us from cowing blocks in the destination tree and doing
 350                  * extra writes that may not have been done by a previous
 351                  * sync
 352                  */
 353                 if (ret == 0) {
 354                         btrfs_release_path(root, path);
 355                         return 0;
 356                 }
 357
 358         }
 359 insert:
 360         btrfs_release_path(root, path);
 361         /* try to insert the key into the destination tree */
 362         ret = btrfs_insert_empty_item(trans, root, path,
 363                                       key, item_size);
 364
 365         /* make sure any existing item is the correct size */
 366         if (ret == -EEXIST) {
 367                 u32 found_size;
 368                 found_size = btrfs_item_size_nr(path->nodes[0],
 369                                                 path->slots[0]);
 370                 if (found_size > item_size) {
 371                         btrfs_truncate_item(trans, root, path, item_size, 1);
 372                 } else if (found_size < item_size) {
 373                         ret = btrfs_extend_item(trans, root, path,
 374                                                 item_size - found_size);
 375                         BUG_ON(ret);
 376                 }
 377         } else if (ret) {
 378                 BUG();
 379         }
 380         dst_ptr = btrfs_item_ptr_offset(path->nodes[0],
 381                                         path->slots[0]);
 382
 383         /* don't overwrite an existing inode if the generation number
 384          * was logged as zero.  This is done when the tree logging code
 385          * is just logging an inode to make sure it exists after recovery.
 386          *
 387          * Also, don't overwrite i_size on directories during replay.
 388          * log replay inserts and removes directory items based on the
 389          * state of the tree found in the subvolume, and i_size is modified
 390          * as it goes
 391          */
 392         if (key->type == BTRFS_INODE_ITEM_KEY && ret == -EEXIST) {
 393                 struct btrfs_inode_item *src_item;
 394                 struct btrfs_inode_item *dst_item;
 395
 396                 src_item = (struct btrfs_inode_item *)src_ptr;
 397                 dst_item = (struct btrfs_inode_item *)dst_ptr;
 398
 399                 if (btrfs_inode_generation(eb, src_item) == 0)
 400                         goto no_copy;
 401
 402                 if (overwrite_root &&
 403                     S_ISDIR(btrfs_inode_mode(eb, src_item)) &&
 404                     S_ISDIR(btrfs_inode_mode(path->nodes[0], dst_item))) {
 405                         save_old_i_size = 1;
 406                         saved_i_size = btrfs_inode_size(path->nodes[0],
 407                                                         dst_item);
 408                 }
 409         }
 410
 411         copy_extent_buffer(path->nodes[0], eb, dst_ptr,
 412                            src_ptr, item_size);
 413
 414         if (save_old_i_size) {
 415                 struct btrfs_inode_item *dst_item;
 416                 dst_item = (struct btrfs_inode_item *)dst_ptr;
 417                 btrfs_set_inode_size(path->nodes[0], dst_item, saved_i_size);
 418         }
 419
 420         /* make sure the generation is filled in */
 421         if (key->type == BTRFS_INODE_ITEM_KEY) {
 422                 struct btrfs_inode_item *dst_item;
 423                 dst_item = (struct btrfs_inode_item *)dst_ptr;
 424                 if (btrfs_inode_generation(path->nodes[0], dst_item) == 0) {
 425                         btrfs_set_inode_generation(path->nodes[0], dst_item,
 426                                                    trans->transid);
 427                 }
 428         }
 429 no_copy:
 430         btrfs_mark_buffer_dirty(path->nodes[0]);
 431         btrfs_release_path(root, path);
 432         return 0;
 433 }
 434
 435 /*
 436  * simple helper to read an inode off the disk from a given root
 437  * This can only be called for subvolume roots and not for the log
 438  */
 439 static noinline struct inode *read_one_inode(struct btrfs_root *root,
 440                                              u64 objectid)
 441 {
 442         struct btrfs_key key;
 443         struct inode *inode;
 444
 445         key.objectid = objectid;
 446         key.type = BTRFS_INODE_ITEM_KEY;
 447         key.offset = 0;
 448         inode = btrfs_iget(root->fs_info->sb, &key, root);
 449         if (IS_ERR(inode)) {
 450                 inode = NULL;
 451         } else if (is_bad_inode(inode)) {
 452                 iput(inode);
 453                 inode = NULL;
 454         }
 455         return inode;
 456 }
 457
 458 /* replays a single extent in 'eb' at 'slot' with 'key' into the
 459  * subvolume 'root'.  path is released on entry and should be released
 460  * on exit.
 461  *
 462  * extents in the log tree have not been allocated out of the extent
 463  * tree yet.  So, this completes the allocation, taking a reference
 464  * as required if the extent already exists or creating a new extent
 465  * if it isn't in the extent allocation tree yet.
 466  *
 467  * The extent is inserted into the file, dropping any existing extents
 468  * from the file that overlap the new one.
 469  */
 470 static noinline int replay_one_extent(struct btrfs_trans_handle *trans,
 471                                       struct btrfs_root *root,
 472                                       struct btrfs_path *path,
 473                                       struct extent_buffer *eb, int slot,
 474                                       struct btrfs_key *key)
 475 {
 476         int found_type;
 477         u64 mask = root->sectorsize - 1;
 478         u64 extent_end;
 479         u64 alloc_hint;
 480         u64 start = key->offset;
 481         u64 saved_nbytes;
 482         struct btrfs_file_extent_item *item;
 483         struct inode *inode = NULL;
 484         unsigned long size;
 485         int ret = 0;
 486
 487         item = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
 488         found_type = btrfs_file_extent_type(eb, item);
 489
 490         if (found_type == BTRFS_FILE_EXTENT_REG ||
 491             found_type == BTRFS_FILE_EXTENT_PREALLOC)
 492                 extent_end = start + btrfs_file_extent_num_bytes(eb, item);
 493         else if (found_type == BTRFS_FILE_EXTENT_INLINE) {
 494                 size = btrfs_file_extent_inline_len(eb, item);
 495                 extent_end = (start + size + mask) & ~mask;
 496         } else {
 497                 ret = 0;
 498                 goto out;
 499         }
 500
 501         inode = read_one_inode(root, key->objectid);
 502         if (!inode) {
 503                 ret = -EIO;
 504                 goto out;
 505         }
 506
 507         /*
 508          * first check to see if we already have this extent in the
 509          * file.  This must be done before the btrfs_drop_extents run
 510          * so we don't try to drop this extent.
 511          */
 512         ret = btrfs_lookup_file_extent(trans, root, path, inode->i_ino,
 513                                        start, 0);
 514
 515         if (ret == 0 &&
 516             (found_type == BTRFS_FILE_EXTENT_REG ||
 517              found_type == BTRFS_FILE_EXTENT_PREALLOC)) {
 518                 struct btrfs_file_extent_item cmp1;
 519                 struct btrfs_file_extent_item cmp2;
 520                 struct btrfs_file_extent_item *existing;
 521                 struct extent_buffer *leaf;
 522
 523                 leaf = path->nodes[0];
 524                 existing = btrfs_item_ptr(leaf, path->slots[0],
 525                                           struct btrfs_file_extent_item);
 526
 527                 read_extent_buffer(eb, &cmp1, (unsigned long)item,
 528                                    sizeof(cmp1));
 529                 read_extent_buffer(leaf, &cmp2, (unsigned long)existing,
 530                                    sizeof(cmp2));
 531
 532                 /*
 533                  * we already have a pointer to this exact extent,
 534                  * we don't have to do anything
 535                  */
 536                 if (memcmp(&cmp1, &cmp2, sizeof(cmp1)) == 0) {
 537                         btrfs_release_path(root, path);
 538                         goto out;
 539                 }
 540         }
 541         btrfs_release_path(root, path);
 542
 543         saved_nbytes = inode_get_bytes(inode);
 544         /* drop any overlapping extents */
 545         ret = btrfs_drop_extents(trans, root, inode,
 546                          start, extent_end, extent_end, start, &alloc_hint, 1);
 547         BUG_ON(ret);
 548
 549         if (found_type == BTRFS_FILE_EXTENT_REG ||
 550             found_type == BTRFS_FILE_EXTENT_PREALLOC) {
 551                 u64 offset;
 552                 unsigned long dest_offset;
 553                 struct btrfs_key ins;
 554
 555                 ret = btrfs_insert_empty_item(trans, root, path, key,
 556                                               sizeof(*item));
 557                 BUG_ON(ret);
 558                 dest_offset = btrfs_item_ptr_offset(path->nodes[0],
 559                                                     path->slots[0]);
 560                 copy_extent_buffer(path->nodes[0], eb, dest_offset,
 561                                 (unsigned long)item,  sizeof(*item));
 562
 563                 ins.objectid = btrfs_file_extent_disk_bytenr(eb, item);
 564                 ins.offset = btrfs_file_extent_disk_num_bytes(eb, item);
 565                 ins.type = BTRFS_EXTENT_ITEM_KEY;
 566                 offset = key->offset - btrfs_file_extent_offset(eb, item);
 567
 568                 if (ins.objectid > 0) {
 569                         u64 csum_start;
 570                         u64 csum_end;
 571                         LIST_HEAD(ordered_sums);
 572                         /*
 573                          * is this extent already allocated in the extent
 574                          * allocation tree?  If so, just add a reference
 575                          */
 576                         ret = btrfs_lookup_extent(root, ins.objectid,
 577                                                 ins.offset);
 578                         if (ret == 0) {
 579                                 ret = btrfs_inc_extent_ref(trans, root,
 580                                                 ins.objectid, ins.offset,
 581                                                 0, root->root_key.objectid,
 582                                                 key->objectid, offset);
 583                         } else {
 584                                 /*
 585                                  * insert the extent pointer in the extent
 586                                  * allocation tree
 587                                  */
 588                                 ret = btrfs_alloc_logged_file_extent(trans,
 589                                                 root, root->root_key.objectid,
 590                                                 key->objectid, offset, &ins);
 591                                 BUG_ON(ret);
 592                         }
 593                         btrfs_release_path(root, path);
 594
 595                         if (btrfs_file_extent_compression(eb, item)) {
 596                                 csum_start = ins.objectid;
 597                                 csum_end = csum_start + ins.offset;
 598                         } else {
 599                                 csum_start = ins.objectid +
 600                                         btrfs_file_extent_offset(eb, item);
 601                                 csum_end = csum_start +
 602                                         btrfs_file_extent_num_bytes(eb, item);
 603                         }
 604
 605                         ret = btrfs_lookup_csums_range(root->log_root,
 606                                                 csum_start, csum_end - 1,
 607                                                 &ordered_sums);
 608                         BUG_ON(ret);
 609                         while (!list_empty(&ordered_sums)) {
 610                                 struct btrfs_ordered_sum *sums;
 611                                 sums = list_entry(ordered_sums.next,
 612                                                 struct btrfs_ordered_sum,
 613                                                 list);
 614                                 ret = btrfs_csum_file_blocks(trans,
 615                                                 root->fs_info->csum_root,
 616                                                 sums);
 617                                 BUG_ON(ret);
 618                                 list_del(&sums->list);
 619                                 kfree(sums);
 620                         }
 621                 } else {
 622                         btrfs_release_path(root, path);
 623                 }
 624         } else if (found_type == BTRFS_FILE_EXTENT_INLINE) {
 625                 /* inline extents are easy, we just overwrite them */
 626                 ret = overwrite_item(trans, root, path, eb, slot, key);
 627                 BUG_ON(ret);
 628         }
 629
 630         inode_set_bytes(inode, saved_nbytes);
 631         btrfs_update_inode(trans, root, inode);
 632 out:
 633         if (inode)
 634                 iput(inode);
 635         return ret;
 636 }
 637
 638 /*
 639  * when cleaning up conflicts between the directory names in the
 640  * subvolume, directory names in the log and directory names in the
 641  * inode back references, we may have to unlink inodes from directories.
 642  *
 643  * This is a helper function to do the unlink of a specific directory
 644  * item
 645  */
 646 static noinline int drop_one_dir_item(struct btrfs_trans_handle *trans,
 647                                       struct btrfs_root *root,
 648                                       struct btrfs_path *path,
 649                                       struct inode *dir,
 650                                       struct btrfs_dir_item *di)
 651 {
 652         struct inode *inode;
 653         char *name;
 654         int name_len;
 655         struct extent_buffer *leaf;
 656         struct btrfs_key location;
 657         int ret;
 658
 659         leaf = path->nodes[0];
 660
 661         btrfs_dir_item_key_to_cpu(leaf, di, &location);
 662         name_len = btrfs_dir_name_len(leaf, di);
 663         name = kmalloc(name_len, GFP_NOFS);
 664         read_extent_buffer(leaf, name, (unsigned long)(di + 1), name_len);
 665         btrfs_release_path(root, path);
 666
 667         inode = read_one_inode(root, location.objectid);
 668         BUG_ON(!inode);
 669
 670         ret = link_to_fixup_dir(trans, root, path, location.objectid);
 671         BUG_ON(ret);
 672
 673         ret = btrfs_unlink_inode(trans, root, dir, inode, name, name_len);
 674         BUG_ON(ret);
 675         kfree(name);
 676
 677         iput(inode);
 678         return ret;
 679 }
 680
 681 /*
 682  * helper function to see if a given name and sequence number found
 683  * in an inode back reference are already in a directory and correctly
 684  * point to this inode
 685  */
 686 static noinline int inode_in_dir(struct btrfs_root *root,
 687                                  struct btrfs_path *path,
 688                                  u64 dirid, u64 objectid, u64 index,
 689                                  const char *name, int name_len)
 690 {
 691         struct btrfs_dir_item *di;
 692         struct btrfs_key location;
 693         int match = 0;
 694
 695         di = btrfs_lookup_dir_index_item(NULL, root, path, dirid,
 696                                          index, name, name_len, 0);
 697         if (di && !IS_ERR(di)) {
 698                 btrfs_dir_item_key_to_cpu(path->nodes[0], di, &location);
 699                 if (location.objectid != objectid)
 700                         goto out;
 701         } else
 702                 goto out;
 703         btrfs_release_path(root, path);
 704
 705         di = btrfs_lookup_dir_item(NULL, root, path, dirid, name, name_len, 0);
 706         if (di && !IS_ERR(di)) {
 707                 btrfs_dir_item_key_to_cpu(path->nodes[0], di, &location);
 708                 if (location.objectid != objectid)
 709                         goto out;
 710         } else
 711                 goto out;
 712         match = 1;
 713 out:
 714         btrfs_release_path(root, path);
 715         return match;
 716 }
 717
 718 /*
 719  * helper function to check a log tree for a named back reference in
 720  * an inode.  This is used to decide if a back reference that is
 721  * found in the subvolume conflicts with what we find in the log.
 722  *
 723  * inode backreferences may have multiple refs in a single item,
 724  * during replay we process one reference at a time, and we don't
 725  * want to delete valid links to a file from the subvolume if that
 726  * link is also in the log.
 727  */
 728 static noinline int backref_in_log(struct btrfs_root *log,
 729                                    struct btrfs_key *key,
 730                                    char *name, int namelen)
 731 {
 732         struct btrfs_path *path;
 733         struct btrfs_inode_ref *ref;
 734         unsigned long ptr;
 735         unsigned long ptr_end;
 736         unsigned long name_ptr;
 737         int found_name_len;
 738         int item_size;
 739         int ret;
 740         int match = 0;
 741
 742         path = btrfs_alloc_path();
 743         ret = btrfs_search_slot(NULL, log, key, path, 0, 0);
 744         if (ret != 0)
 745                 goto out;
 746
 747         item_size = btrfs_item_size_nr(path->nodes[0], path->slots[0]);
 748         ptr = btrfs_item_ptr_offset(path->nodes[0], path->slots[0]);
 749         ptr_end = ptr + item_size;
 750         while (ptr < ptr_end) {
 751                 ref = (struct btrfs_inode_ref *)ptr;
 752                 found_name_len = btrfs_inode_ref_name_len(path->nodes[0], ref);
 753                 if (found_name_len == namelen) {
 754                         name_ptr = (unsigned long)(ref + 1);
 755                         ret = memcmp_extent_buffer(path->nodes[0], name,
 756                                                    name_ptr, namelen);
 757                         if (ret == 0) {
 758                                 match = 1;
 759                                 goto out;
 760                         }
 761                 }
 762                 ptr = (unsigned long)(ref + 1) + found_name_len;
 763         }
 764 out:
 765         btrfs_free_path(path);
 766         return match;
 767 }
 768
 769
 770 /*
 771  * replay one inode back reference item found in the log tree.
 772  * eb, slot and key refer to the buffer and key found in the log tree.
 773  * root is the destination we are replaying into, and path is for temp
 774  * use by this function.  (it should be released on return).
 775  */
 776 static noinline int add_inode_ref(struct btrfs_trans_handle *trans,
 777                                   struct btrfs_root *root,
 778                                   struct btrfs_root *log,
 779                                   struct btrfs_path *path,
 780                                   struct extent_buffer *eb, int slot,
 781                                   struct btrfs_key *key)
 782 {
 783         struct inode *dir;
 784         int ret;
 785         struct btrfs_key location;
 786         struct btrfs_inode_ref *ref;
 787         struct btrfs_dir_item *di;
 788         struct inode *inode;
 789         char *name;
 790         int namelen;
 791         unsigned long ref_ptr;
 792         unsigned long ref_end;
 793
 794         location.objectid = key->objectid;
 795         location.type = BTRFS_INODE_ITEM_KEY;
 796         location.offset = 0;
 797
 798         /*
 799          * it is possible that we didn't log all the parent directories
 800          * for a given inode.  If we don't find the dir, just don't
 801          * copy the back ref in.  The link count fixup code will take
 802          * care of the rest
 803          */
 804         dir = read_one_inode(root, key->offset);
 805         if (!dir)
 806                 return -ENOENT;
 807
 808         inode = read_one_inode(root, key->objectid);
 809         BUG_ON(!inode);
 810
 811         ref_ptr = btrfs_item_ptr_offset(eb, slot);
 812         ref_end = ref_ptr + btrfs_item_size_nr(eb, slot);
 813
 814 again:
 815         ref = (struct btrfs_inode_ref *)ref_ptr;
 816
 817         namelen = btrfs_inode_ref_name_len(eb, ref);
 818         name = kmalloc(namelen, GFP_NOFS);
 819         BUG_ON(!name);
 820
 821         read_extent_buffer(eb, name, (unsigned long)(ref + 1), namelen);
 822
 823         /* if we already have a perfect match, we're done */
 824         if (inode_in_dir(root, path, dir->i_ino, inode->i_ino,
 825                          btrfs_inode_ref_index(eb, ref),
 826                          name, namelen)) {
 827                 goto out;
 828         }
 829
 830         /*
 831          * look for a conflicting back reference in the metadata.
 832          * if we find one we have to unlink that name of the file
 833          * before we add our new link.  Later on, we overwrite any
 834          * existing back reference, and we don't want to create
 835          * dangling pointers in the directory.
 836          */
 837 conflict_again:
 838         ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
 839         if (ret == 0) {
 840                 char *victim_name;
 841                 int victim_name_len;
 842                 struct btrfs_inode_ref *victim_ref;
 843                 unsigned long ptr;
 844                 unsigned long ptr_end;
 845                 struct extent_buffer *leaf = path->nodes[0];
 846
 847                 /* are we trying to overwrite a back ref for the root directory
 848                  * if so, just jump out, we're done
 849                  */
 850                 if (key->objectid == key->offset)
 851                         goto out_nowrite;
 852
 853                 /* check all the names in this back reference to see
 854                  * if they are in the log.  if so, we allow them to stay
 855                  * otherwise they must be unlinked as a conflict
 856                  */
 857                 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
 858                 ptr_end = ptr + btrfs_item_size_nr(leaf, path->slots[0]);
 859                 while (ptr < ptr_end) {
 860                         victim_ref = (struct btrfs_inode_ref *)ptr;
 861                         victim_name_len = btrfs_inode_ref_name_len(leaf,
 862                                                                    victim_ref);
 863                         victim_name = kmalloc(victim_name_len, GFP_NOFS);
 864                         BUG_ON(!victim_name);
 865
 866                         read_extent_buffer(leaf, victim_name,
 867                                            (unsigned long)(victim_ref + 1),
 868                                            victim_name_len);
 869
 870                         if (!backref_in_log(log, key, victim_name,
 871                                             victim_name_len)) {
 872                                 btrfs_inc_nlink(inode);
 873                                 btrfs_release_path(root, path);
 874
 875                                 ret = btrfs_unlink_inode(trans, root, dir,
 876                                                          inode, victim_name,
 877                                                          victim_name_len);
 878                                 kfree(victim_name);
 879                                 btrfs_release_path(root, path);
 880                                 goto conflict_again;
 881                         }
 882                         kfree(victim_name);
 883                         ptr = (unsigned long)(victim_ref + 1) + victim_name_len;
 884                 }
 885                 BUG_ON(ret);
 886         }
 887         btrfs_release_path(root, path);
 888
 889         /* look for a conflicting sequence number */
 890         di = btrfs_lookup_dir_index_item(trans, root, path, dir->i_ino,
 891                                          btrfs_inode_ref_index(eb, ref),
 892                                          name, namelen, 0);
 893         if (di && !IS_ERR(di)) {
 894                 ret = drop_one_dir_item(trans, root, path, dir, di);
 895                 BUG_ON(ret);
 896         }
 897         btrfs_release_path(root, path);
 898
 899
 900         /* look for a conflicting name */
 901         di = btrfs_lookup_dir_item(trans, root, path, dir->i_ino,
 902                                    name, namelen, 0);
 903         if (di && !IS_ERR(di)) {
 904                 ret = drop_one_dir_item(trans, root, path, dir, di);
 905                 BUG_ON(ret);
 906         }
 907         btrfs_release_path(root, path);
 908
 909         /* insert our name */
 910         ret = btrfs_add_link(trans, dir, inode, name, namelen, 0,
 911                              btrfs_inode_ref_index(eb, ref));
 912         BUG_ON(ret);
 913
 914         btrfs_update_inode(trans, root, inode);
 915
 916 out:
 917         ref_ptr = (unsigned long)(ref + 1) + namelen;
 918         kfree(name);
 919         if (ref_ptr < ref_end)
 920                 goto again;
 921
 922         /* finally write the back reference in the inode */
 923         ret = overwrite_item(trans, root, path, eb, slot, key);
 924         BUG_ON(ret);
 925
 926 out_nowrite:
 927         btrfs_release_path(root, path);
 928         iput(dir);
 929         iput(inode);
 930         return 0;
 931 }
 932
 933 /*
 934  * There are a few corners where the link count of the file can't
 935  * be properly maintained during replay.  So, instead of adding
 936  * lots of complexity to the log code, we just scan the backrefs
 937  * for any file that has been through replay.
 938  *
 939  * The scan will update the link count on the inode to reflect the
 940  * number of back refs found.  If it goes down to zero, the iput
 941  * will free the inode.
 942  */
 943 static noinline int fixup_inode_link_count(struct btrfs_trans_handle *trans,
 944                                            struct btrfs_root *root,
 945                                            struct inode *inode)
 946 {
 947         struct btrfs_path *path;
 948         int ret;
 949         struct btrfs_key key;
 950         u64 nlink = 0;
 951         unsigned long ptr;
 952         unsigned long ptr_end;
 953         int name_len;
 954
 955         key.objectid = inode->i_ino;
 956         key.type = BTRFS_INODE_REF_KEY;
 957         key.offset = (u64)-1;
 958
 959         path = btrfs_alloc_path();
 960
 961         while (1) {
 962                 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 963                 if (ret < 0)
 964                         break;
 965                 if (ret > 0) {
 966                         if (path->slots[0] == 0)
 967                                 break;
 968                         path->slots[0]--;
 969                 }
 970                 btrfs_item_key_to_cpu(path->nodes[0], &key,
 971                                       path->slots[0]);
 972                 if (key.objectid != inode->i_ino ||
 973                     key.type != BTRFS_INODE_REF_KEY)
 974                         break;
 975                 ptr = btrfs_item_ptr_offset(path->nodes[0], path->slots[0]);
 976                 ptr_end = ptr + btrfs_item_size_nr(path->nodes[0],
 977                                                    path->slots[0]);
 978                 while (ptr < ptr_end) {
 979                         struct btrfs_inode_ref *ref;
 980
 981                         ref = (struct btrfs_inode_ref *)ptr;
 982                         name_len = btrfs_inode_ref_name_len(path->nodes[0],
 983                                                             ref);
 984                         ptr = (unsigned long)(ref + 1) + name_len;
 985                         nlink++;
 986                 }
 987
 988                 if (key.offset == 0)
 989                         break;
 990                 key.offset--;
 991                 btrfs_release_path(root, path);
 992         }
 993         btrfs_release_path(root, path);
 994         if (nlink != inode->i_nlink) {
 995                 inode->i_nlink = nlink;
 996                 btrfs_update_inode(trans, root, inode);
 997         }
 998         BTRFS_I(inode)->index_cnt = (u64)-1;
 999
1000         if (inode->i_nlink == 0 && S_ISDIR(inode->i_mode)) {
1001                 ret = replay_dir_deletes(trans, root, NULL, path,
1002                                          inode->i_ino, 1);
1003                 BUG_ON(ret);
1004         }
1005         btrfs_free_path(path);
1006
1007         return 0;
1008 }
1009
1010 static noinline int fixup_inode_link_counts(struct btrfs_trans_handle *trans,
1011                                             struct btrfs_root *root,
1012                                             struct btrfs_path *path)
1013 {
1014         int ret;
1015         struct btrfs_key key;
1016         struct inode *inode;
1017
1018         key.objectid = BTRFS_TREE_LOG_FIXUP_OBJECTID;
1019         key.type = BTRFS_ORPHAN_ITEM_KEY;
1020         key.offset = (u64)-1;
1021         while (1) {
1022                 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
1023                 if (ret < 0)
1024                         break;
1025
1026                 if (ret == 1) {
1027                         if (path->slots[0] == 0)
1028                                 break;
1029                         path->slots[0]--;
1030                 }
1031
1032                 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1033                 if (key.objectid != BTRFS_TREE_LOG_FIXUP_OBJECTID ||
1034                     key.type != BTRFS_ORPHAN_ITEM_KEY)
1035                         break;
1036
1037                 ret = btrfs_del_item(trans, root, path);
1038                 BUG_ON(ret);
1039
1040                 btrfs_release_path(root, path);
1041                 inode = read_one_inode(root, key.offset);
1042                 BUG_ON(!inode);
1043
1044                 ret = fixup_inode_link_count(trans, root, inode);
1045                 BUG_ON(ret);
1046
1047                 iput(inode);
1048
1049                 /*
1050                  * fixup on a directory may create new entries,
1051                  * make sure we always look for the highset possible
1052                  * offset
1053                  */
1054                 key.offset = (u64)-1;
1055         }
1056         btrfs_release_path(root, path);
1057         return 0;
1058 }
1059
1060
1061 /*
1062  * record a given inode in the fixup dir so we can check its link
1063  * count when replay is done.  The link count is incremented here
1064  * so the inode won't go away until we check it
1065  */
1066 static noinline int link_to_fixup_dir(struct btrfs_trans_handle *trans,
1067                                       struct btrfs_root *root,
1068                                       struct btrfs_path *path,
1069                                       u64 objectid)
1070 {
1071         struct btrfs_key key;
1072         int ret = 0;
1073         struct inode *inode;
1074
1075         inode = read_one_inode(root, objectid);
1076         BUG_ON(!inode);
1077
1078         key.objectid = BTRFS_TREE_LOG_FIXUP_OBJECTID;
1079         btrfs_set_key_type(&key, BTRFS_ORPHAN_ITEM_KEY);
1080         key.offset = objectid;
1081
1082         ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
1083
1084         btrfs_release_path(root, path);
1085         if (ret == 0) {
1086                 btrfs_inc_nlink(inode);
1087                 btrfs_update_inode(trans, root, inode);
1088         } else if (ret == -EEXIST) {
1089                 ret = 0;
1090         } else {
1091                 BUG();
1092         }
1093         iput(inode);
1094
1095         return ret;
1096 }
1097
1098 /*
1099  * when replaying the log for a directory, we only insert names
1100  * for inodes that actually exist.  This means an fsync on a directory
1101  * does not implicitly fsync all the new files in it
1102  */
1103 static noinline int insert_one_name(struct btrfs_trans_handle *trans,
1104                                     struct btrfs_root *root,
1105                                     struct btrfs_path *path,
1106                                     u64 dirid, u64 index,
1107                                     char *name, int name_len, u8 type,
1108                                     struct btrfs_key *location)
1109 {
1110         struct inode *inode;
1111         struct inode *dir;
1112         int ret;
1113
1114         inode = read_one_inode(root, location->objectid);
1115         if (!inode)
1116                 return -ENOENT;
1117
1118         dir = read_one_inode(root, dirid);
1119         if (!dir) {
1120                 iput(inode);
1121                 return -EIO;
1122         }
1123         ret = btrfs_add_link(trans, dir, inode, name, name_len, 1, index);
1124
1125         /* FIXME, put inode into FIXUP list */
1126
1127         iput(inode);
1128         iput(dir);
1129         return ret;
1130 }
1131
1132 /*
1133  * take a single entry in a log directory item and replay it into
1134  * the subvolume.
1135  *
1136  * if a conflicting item exists in the subdirectory already,
1137  * the inode it points to is unlinked and put into the link count
1138  * fix up tree.
1139  *
1140  * If a name from the log points to a file or directory that does
1141  * not exist in the FS, it is skipped.  fsyncs on directories
1142  * do not force down inodes inside that directory, just changes to the
1143  * names or unlinks in a directory.
1144  */
1145 static noinline int replay_one_name(struct btrfs_trans_handle *trans,
1146                                     struct btrfs_root *root,
1147                                     struct btrfs_path *path,
1148                                     struct extent_buffer *eb,
1149                                     struct btrfs_dir_item *di,
1150                                     struct btrfs_key *key)
1151 {
1152         char *name;
1153         int name_len;
1154         struct btrfs_dir_item *dst_di;
1155         struct btrfs_key found_key;
1156         struct btrfs_key log_key;
1157         struct inode *dir;
1158         u8 log_type;
1159         int exists;
1160         int ret;
1161
1162         dir = read_one_inode(root, key->objectid);
1163         BUG_ON(!dir);
1164
1165         name_len = btrfs_dir_name_len(eb, di);
1166         name = kmalloc(name_len, GFP_NOFS);
1167         log_type = btrfs_dir_type(eb, di);
1168         read_extent_buffer(eb, name, (unsigned long)(di + 1),
1169                    name_len);
1170
1171         btrfs_dir_item_key_to_cpu(eb, di, &log_key);
1172         exists = btrfs_lookup_inode(trans, root, path, &log_key, 0);
1173         if (exists == 0)
1174                 exists = 1;
1175         else
1176                 exists = 0;
1177         btrfs_release_path(root, path);
1178
1179         if (key->type == BTRFS_DIR_ITEM_KEY) {
1180                 dst_di = btrfs_lookup_dir_item(trans, root, path, key->objectid,
1181                                        name, name_len, 1);
1182         } else if (key->type == BTRFS_DIR_INDEX_KEY) {
1183                 dst_di = btrfs_lookup_dir_index_item(trans, root, path,
1184                                                      key->objectid,
1185                                                      key->offset, name,
1186                                                      name_len, 1);
1187         } else {
1188                 BUG();
1189         }
1190         if (!dst_di || IS_ERR(dst_di)) {
1191                 /* we need a sequence number to insert, so we only
1192                  * do inserts for the BTRFS_DIR_INDEX_KEY types
1193                  */
1194                 if (key->type != BTRFS_DIR_INDEX_KEY)
1195                         goto out;
1196                 goto insert;
1197         }
1198
1199         btrfs_dir_item_key_to_cpu(path->nodes[0], dst_di, &found_key);
1200         /* the existing item matches the logged item */
1201         if (found_key.objectid == log_key.objectid &&
1202             found_key.type == log_key.type &&
1203             found_key.offset == log_key.offset &&
1204             btrfs_dir_type(path->nodes[0], dst_di) == log_type) {
1205                 goto out;
1206         }
1207
1208         /*
1209          * don't drop the conflicting directory entry if the inode
1210          * for the new entry doesn't exist
1211          */
1212         if (!exists)
1213                 goto out;
1214
1215         ret = drop_one_dir_item(trans, root, path, dir, dst_di);
1216         BUG_ON(ret);
1217
1218         if (key->type == BTRFS_DIR_INDEX_KEY)
1219                 goto insert;
1220 out:
1221         btrfs_release_path(root, path);
1222         kfree(name);
1223         iput(dir);
1224         return 0;
1225
1226 insert:
1227         btrfs_release_path(root, path);
1228         ret = insert_one_name(trans, root, path, key->objectid, key->offset,
1229                               name, name_len, log_type, &log_key);
1230
1231         BUG_ON(ret && ret != -ENOENT);
1232         goto out;
1233 }
1234
1235 /*
1236  * find all the names in a directory item and reconcile them into
1237  * the subvolume.  Only BTRFS_DIR_ITEM_KEY types will have more than
1238  * one name in a directory item, but the same code gets used for
1239  * both directory index types
1240  */
1241 static noinline int replay_one_dir_item(struct btrfs_trans_handle *trans,
1242                                         struct btrfs_root *root,
1243                                         struct btrfs_path *path,
1244                                         struct extent_buffer *eb, int slot,
1245                                         struct btrfs_key *key)
1246 {
1247         int ret;
1248         u32 item_size = btrfs_item_size_nr(eb, slot);
1249         struct btrfs_dir_item *di;
1250         int name_len;
1251         unsigned long ptr;
1252         unsigned long ptr_end;
1253
1254         ptr = btrfs_item_ptr_offset(eb, slot);
1255         ptr_end = ptr + item_size;
1256         while (ptr < ptr_end) {
1257                 di = (struct btrfs_dir_item *)ptr;
1258                 name_len = btrfs_dir_name_len(eb, di);
1259                 ret = replay_one_name(trans, root, path, eb, di, key);
1260                 BUG_ON(ret);
1261                 ptr = (unsigned long)(di + 1);
1262                 ptr += name_len;
1263         }
1264         return 0;
1265 }
1266
1267 /*
1268  * directory replay has two parts.  There are the standard directory
1269  * items in the log copied from the subvolume, and range items
1270  * created in the log while the subvolume was logged.
1271  *
1272  * The range items tell us which parts of the key space the log
1273  * is authoritative for.  During replay, if a key in the subvolume
1274  * directory is in a logged range item, but not actually in the log
1275  * that means it was deleted from the directory before the fsync
1276  * and should be removed.
1277  */
1278 static noinline int find_dir_range(struct btrfs_root *root,
1279                                    struct btrfs_path *path,
1280                                    u64 dirid, int key_type,
1281                                    u64 *start_ret, u64 *end_ret)
1282 {
1283         struct btrfs_key key;
1284         u64 found_end;
1285         struct btrfs_dir_log_item *item;
1286         int ret;
1287         int nritems;
1288
1289         if (*start_ret == (u64)-1)
1290                 return 1;
1291
1292         key.objectid = dirid;
1293         key.type = key_type;
1294         key.offset = *start_ret;
1295
1296         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
1297         if (ret < 0)
1298                 goto out;
1299         if (ret > 0) {
1300                 if (path->slots[0] == 0)
1301                         goto out;
1302                 path->slots[0]--;
1303         }
1304         if (ret != 0)
1305                 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1306
1307         if (key.type != key_type || key.objectid != dirid) {
1308                 ret = 1;
1309                 goto next;
1310         }
1311         item = btrfs_item_ptr(path->nodes[0], path->slots[0],
1312                               struct btrfs_dir_log_item);
1313         found_end = btrfs_dir_log_end(path->nodes[0], item);
1314
1315         if (*start_ret >= key.offset && *start_ret <= found_end) {
1316                 ret = 0;
1317                 *start_ret = key.offset;
1318                 *end_ret = found_end;
1319                 goto out;
1320         }
1321         ret = 1;
1322 next:
1323         /* check the next slot in the tree to see if it is a valid item */
1324         nritems = btrfs_header_nritems(path->nodes[0]);
1325         if (path->slots[0] >= nritems) {
1326                 ret = btrfs_next_leaf(root, path);
1327                 if (ret)
1328                         goto out;
1329         } else {
1330                 path->slots[0]++;
1331         }
1332
1333         btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1334
1335         if (key.type != key_type || key.objectid != dirid) {
1336                 ret = 1;
1337                 goto out;
1338         }
1339         item = btrfs_item_ptr(path->nodes[0], path->slots[0],
1340                               struct btrfs_dir_log_item);
1341         found_end = btrfs_dir_log_end(path->nodes[0], item);
1342         *start_ret = key.offset;
1343         *end_ret = found_end;
1344         ret = 0;
1345 out:
1346         btrfs_release_path(root, path);
1347         return ret;
1348 }
1349
1350 /*
1351  * this looks for a given directory item in the log.  If the directory
1352  * item is not in the log, the item is removed and the inode it points
1353  * to is unlinked
1354  */
1355 static noinline int check_item_in_log(struct btrfs_trans_handle *trans,
1356                                       struct btrfs_root *root,
1357                                       struct btrfs_root *log,
1358                                       struct btrfs_path *path,
1359                                       struct btrfs_path *log_path,
1360                                       struct inode *dir,
1361                                       struct btrfs_key *dir_key)
1362 {
1363         int ret;
1364         struct extent_buffer *eb;
1365         int slot;
1366         u32 item_size;
1367         struct btrfs_dir_item *di;
1368         struct btrfs_dir_item *log_di;
1369         int name_len;
1370         unsigned long ptr;
1371         unsigned long ptr_end;
1372         char *name;
1373         struct inode *inode;
1374         struct btrfs_key location;
1375
1376 again:
1377         eb = path->nodes[0];
1378         slot = path->slots[0];
1379         item_size = btrfs_item_size_nr(eb, slot);
1380         ptr = btrfs_item_ptr_offset(eb, slot);
1381         ptr_end = ptr + item_size;
1382         while (ptr < ptr_end) {
1383                 di = (struct btrfs_dir_item *)ptr;
1384                 name_len = btrfs_dir_name_len(eb, di);
1385                 name = kmalloc(name_len, GFP_NOFS);
1386                 if (!name) {
1387                         ret = -ENOMEM;
1388                         goto out;
1389                 }
1390                 read_extent_buffer(eb, name, (unsigned long)(di + 1),
1391                                   name_len);
1392                 log_di = NULL;
1393                 if (log && dir_key->type == BTRFS_DIR_ITEM_KEY) {
1394                         log_di = btrfs_lookup_dir_item(trans, log, log_path,
1395                                                        dir_key->objectid,
1396                                                        name, name_len, 0);
1397                 } else if (log && dir_key->type == BTRFS_DIR_INDEX_KEY) {
1398                         log_di = btrfs_lookup_dir_index_item(trans, log,
1399                                                      log_path,
1400                                                      dir_key->objectid,
1401                                                      dir_key->offset,
1402                                                      name, name_len, 0);
1403                 }
1404                 if (!log_di || IS_ERR(log_di)) {
1405                         btrfs_dir_item_key_to_cpu(eb, di, &location);
1406                         btrfs_release_path(root, path);
1407                         btrfs_release_path(log, log_path);
1408                         inode = read_one_inode(root, location.objectid);
1409                         BUG_ON(!inode);
1410
1411                         ret = link_to_fixup_dir(trans, root,
1412                                                 path, location.objectid);
1413                         BUG_ON(ret);
1414                         btrfs_inc_nlink(inode);
1415                         ret = btrfs_unlink_inode(trans, root, dir, inode,
1416                                                  name, name_len);
1417                         BUG_ON(ret);
1418                         kfree(name);
1419                         iput(inode);
1420
1421                         /* there might still be more names under this key
1422                          * check and repeat if required
1423                          */
1424                         ret = btrfs_search_slot(NULL, root, dir_key, path,
1425                                                 0, 0);
1426                         if (ret == 0)
1427                                 goto again;
1428                         ret = 0;
1429                         goto out;
1430                 }
1431                 btrfs_release_path(log, log_path);
1432                 kfree(name);
1433
1434                 ptr = (unsigned long)(di + 1);
1435                 ptr += name_len;
1436         }
1437         ret = 0;
1438 out:
1439         btrfs_release_path(root, path);
1440         btrfs_release_path(log, log_path);
1441         return ret;
1442 }
1443
1444 /*
1445  * deletion replay happens before we copy any new directory items
1446  * out of the log or out of backreferences from inodes.  It
1447  * scans the log to find ranges of keys that log is authoritative for,
1448  * and then scans the directory to find items in those ranges that are
1449  * not present in the log.
1450  *
1451  * Anything we don't find in the log is unlinked and removed from the
1452  * directory.
1453  */
1454 static noinline int replay_dir_deletes(struct btrfs_trans_handle *trans,
1455                                        struct btrfs_root *root,
1456                                        struct btrfs_root *log,
1457                                        struct btrfs_path *path,
1458                                        u64 dirid, int del_all)
1459 {
1460         u64 range_start;
1461         u64 range_end;
1462         int key_type = BTRFS_DIR_LOG_ITEM_KEY;
1463         int ret = 0;
1464         struct btrfs_key dir_key;
1465         struct btrfs_key found_key;
1466         struct btrfs_path *log_path;
1467         struct inode *dir;
1468
1469         dir_key.objectid = dirid;
1470         dir_key.type = BTRFS_DIR_ITEM_KEY;
1471         log_path = btrfs_alloc_path();
1472         if (!log_path)
1473                 return -ENOMEM;
1474
1475         dir = read_one_inode(root, dirid);
1476         /* it isn't an error if the inode isn't there, that can happen
1477          * because we replay the deletes before we copy in the inode item
1478          * from the log
1479          */
1480         if (!dir) {
1481                 btrfs_free_path(log_path);
1482                 return 0;
1483         }
1484 again:
1485         range_start = 0;
1486         range_end = 0;
1487         while (1) {
1488                 if (del_all)
1489                         range_end = (u64)-1;
1490                 else {
1491                         ret = find_dir_range(log, path, dirid, key_type,
1492                                              &range_start, &range_end);
1493                         if (ret != 0)
1494                                 break;
1495                 }
1496
1497                 dir_key.offset = range_start;
1498                 while (1) {
1499                         int nritems;
1500                         ret = btrfs_search_slot(NULL, root, &dir_key, path,
1501                                                 0, 0);
1502                         if (ret < 0)
1503                                 goto out;
1504
1505                         nritems = btrfs_header_nritems(path->nodes[0]);
1506                         if (path->slots[0] >= nritems) {
1507                                 ret = btrfs_next_leaf(root, path);
1508                                 if (ret)
1509                                         break;
1510                         }
1511                         btrfs_item_key_to_cpu(path->nodes[0], &found_key,
1512                                               path->slots[0]);
1513                         if (found_key.objectid != dirid ||
1514                             found_key.type != dir_key.type)
1515                                 goto next_type;
1516
1517                         if (found_key.offset > range_end)
1518                                 break;
1519
1520                         ret = check_item_in_log(trans, root, log, path,
1521                                                 log_path, dir,
1522                                                 &found_key);
1523                         BUG_ON(ret);
1524                         if (found_key.offset == (u64)-1)
1525                                 break;
1526                         dir_key.offset = found_key.offset + 1;
1527                 }
1528                 btrfs_release_path(root, path);
1529                 if (range_end == (u64)-1)
1530                         break;
1531                 range_start = range_end + 1;
1532         }
1533
1534 next_type:
1535         ret = 0;
1536         if (key_type == BTRFS_DIR_LOG_ITEM_KEY) {
1537                 key_type = BTRFS_DIR_LOG_INDEX_KEY;
1538                 dir_key.type = BTRFS_DIR_INDEX_KEY;
1539                 btrfs_release_path(root, path);
1540                 goto again;
1541         }
1542 out:
1543         btrfs_release_path(root, path);
1544         btrfs_free_path(log_path);
1545         iput(dir);
1546         return ret;
1547 }
1548
1549 /*
1550  * the process_func used to replay items from the log tree.  This
1551  * gets called in two different stages.  The first stage just looks
1552  * for inodes and makes sure they are all copied into the subvolume.
1553  *
1554  * The second stage copies all the other item types from the log into
1555  * the subvolume.  The two stage approach is slower, but gets rid of
1556  * lots of complexity around inodes referencing other inodes that exist
1557  * only in the log (references come from either directory items or inode
1558  * back refs).
1559  */
1560 static int replay_one_buffer(struct btrfs_root *log, struct extent_buffer *eb,
1561                              struct walk_control *wc, u64 gen)
1562 {
1563         int nritems;
1564         struct btrfs_path *path;
1565         struct btrfs_root *root = wc->replay_dest;
1566         struct btrfs_key key;
1567         u32 item_size;
1568         int level;
1569         int i;
1570         int ret;
1571
1572         btrfs_read_buffer(eb, gen);
1573
1574         level = btrfs_header_level(eb);
1575
1576         if (level != 0)
1577                 return 0;
1578
1579         path = btrfs_alloc_path();
1580         BUG_ON(!path);
1581
1582         nritems = btrfs_header_nritems(eb);
1583         for (i = 0; i < nritems; i++) {
1584                 btrfs_item_key_to_cpu(eb, &key, i);
1585                 item_size = btrfs_item_size_nr(eb, i);
1586
1587                 /* inode keys are done during the first stage */
1588                 if (key.type == BTRFS_INODE_ITEM_KEY &&
1589                     wc->stage == LOG_WALK_REPLAY_INODES) {
1590                         struct inode *inode;
1591                         struct btrfs_inode_item *inode_item;
1592                         u32 mode;
1593
1594                         inode_item = btrfs_item_ptr(eb, i,
1595                                             struct btrfs_inode_item);
1596                         mode = btrfs_inode_mode(eb, inode_item);
1597                         if (S_ISDIR(mode)) {
1598                                 ret = replay_dir_deletes(wc->trans,
1599                                          root, log, path, key.objectid, 0);
1600                                 BUG_ON(ret);
1601                         }
1602                         ret = overwrite_item(wc->trans, root, path,
1603                                              eb, i, &key);
1604                         BUG_ON(ret);
1605
1606                         /* for regular files, truncate away
1607                          * extents past the new EOF
1608                          */
1609                         if (S_ISREG(mode)) {
1610                                 inode = read_one_inode(root,
1611                                                        key.objectid);
1612                                 BUG_ON(!inode);
1613
1614                                 ret = btrfs_truncate_inode_items(wc->trans,
1615                                         root, inode, inode->i_size,
1616                                         BTRFS_EXTENT_DATA_KEY);
1617                                 BUG_ON(ret);
1618
1619                                 /* if the nlink count is zero here, the iput
1620                                  * will free the inode.  We bump it to make
1621                                  * sure it doesn't get freed until the link
1622                                  * count fixup is done
1623                                  */
1624                                 if (inode->i_nlink == 0) {
1625                                         btrfs_inc_nlink(inode);
1626                                         btrfs_update_inode(wc->trans,
1627                                                            root, inode);
1628                                 }
1629                                 iput(inode);
1630                         }
1631                         ret = link_to_fixup_dir(wc->trans, root,
1632                                                 path, key.objectid);
1633                         BUG_ON(ret);
1634                 }
1635                 if (wc->stage < LOG_WALK_REPLAY_ALL)
1636                         continue;
1637
1638                 /* these keys are simply copied */
1639                 if (key.type == BTRFS_XATTR_ITEM_KEY) {
1640                         ret = overwrite_item(wc->trans, root, path,
1641                                              eb, i, &key);
1642                         BUG_ON(ret);
1643                 } else if (key.type == BTRFS_INODE_REF_KEY) {
1644                         ret = add_inode_ref(wc->trans, root, log, path,
1645                                             eb, i, &key);
1646                         BUG_ON(ret && ret != -ENOENT);
1647                 } else if (key.type == BTRFS_EXTENT_DATA_KEY) {
1648                         ret = replay_one_extent(wc->trans, root, path,
1649                                                 eb, i, &key);
1650                         BUG_ON(ret);
1651                 } else if (key.type == BTRFS_DIR_ITEM_KEY ||
1652                            key.type == BTRFS_DIR_INDEX_KEY) {
1653                         ret = replay_one_dir_item(wc->trans, root, path,
1654                                                   eb, i, &key);
1655                         BUG_ON(ret);
1656                 }
1657         }
1658         btrfs_free_path(path);
1659         return 0;
1660 }
1661
1662 static noinline int walk_down_log_tree(struct btrfs_trans_handle *trans,
1663                                    struct btrfs_root *root,
1664                                    struct btrfs_path *path, int *level,
1665                                    struct walk_control *wc)
1666 {
1667         u64 root_owner;
1668         u64 root_gen;
1669         u64 bytenr;
1670         u64 ptr_gen;
1671         struct extent_buffer *next;
1672         struct extent_buffer *cur;
1673         struct extent_buffer *parent;
1674         u32 blocksize;
1675         int ret = 0;
1676
1677         WARN_ON(*level < 0);
1678         WARN_ON(*level >= BTRFS_MAX_LEVEL);
1679
1680         while (*level > 0) {
1681                 WARN_ON(*level < 0);
1682                 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1683                 cur = path->nodes[*level];
1684
1685                 if (btrfs_header_level(cur) != *level)
1686                         WARN_ON(1);
1687
1688                 if (path->slots[*level] >=
1689                     btrfs_header_nritems(cur))
1690                         break;
1691
1692                 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
1693                 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
1694                 blocksize = btrfs_level_size(root, *level - 1);
1695
1696                 parent = path->nodes[*level];
1697                 root_owner = btrfs_header_owner(parent);
1698                 root_gen = btrfs_header_generation(parent);
1699
1700                 next = btrfs_find_create_tree_block(root, bytenr, blocksize);
1701
1702                 wc->process_func(root, next, wc, ptr_gen);
1703
1704                 if (*level == 1) {
1705                         path->slots[*level]++;
1706                         if (wc->free) {
1707                                 btrfs_read_buffer(next, ptr_gen);
1708
1709                                 btrfs_tree_lock(next);
1710                                 clean_tree_block(trans, root, next);
1711                                 btrfs_set_lock_blocking(next);
1712                                 btrfs_wait_tree_block_writeback(next);
1713                                 btrfs_tree_unlock(next);
1714
1715                                 WARN_ON(root_owner !=
1716                                         BTRFS_TREE_LOG_OBJECTID);
1717                                 ret = btrfs_free_reserved_extent(root,
1718                                                          bytenr, blocksize);
1719                                 BUG_ON(ret);
1720                         }
1721                         free_extent_buffer(next);
1722                         continue;
1723                 }
1724                 btrfs_read_buffer(next, ptr_gen);
1725
1726                 WARN_ON(*level <= 0);
1727                 if (path->nodes[*level-1])
1728                         free_extent_buffer(path->nodes[*level-1]);
1729                 path->nodes[*level-1] = next;
1730                 *level = btrfs_header_level(next);
1731                 path->slots[*level] = 0;
1732                 cond_resched();
1733         }
1734         WARN_ON(*level < 0);
1735         WARN_ON(*level >= BTRFS_MAX_LEVEL);
1736
1737         if (path->nodes[*level] == root->node)
1738                 parent = path->nodes[*level];
1739         else
1740                 parent = path->nodes[*level + 1];
1741
1742         bytenr = path->nodes[*level]->start;
1743
1744         blocksize = btrfs_level_size(root, *level);
1745         root_owner = btrfs_header_owner(parent);
1746         root_gen = btrfs_header_generation(parent);
1747
1748         wc->process_func(root, path->nodes[*level], wc,
1749                          btrfs_header_generation(path->nodes[*level]));
1750
1751         if (wc->free) {
1752                 next = path->nodes[*level];
1753                 btrfs_tree_lock(next);
1754                 clean_tree_block(trans, root, next);
1755                 btrfs_set_lock_blocking(next);
1756                 btrfs_wait_tree_block_writeback(next);
1757                 btrfs_tree_unlock(next);
1758
1759                 WARN_ON(root_owner != BTRFS_TREE_LOG_OBJECTID);
1760                 ret = btrfs_free_reserved_extent(root, bytenr, blocksize);
1761                 BUG_ON(ret);
1762         }
1763         free_extent_buffer(path->nodes[*level]);
1764         path->nodes[*level] = NULL;
1765         *level += 1;
1766
1767         cond_resched();
1768         return 0;
1769 }
1770
1771 static noinline int walk_up_log_tree(struct btrfs_trans_handle *trans,
1772                                  struct btrfs_root *root,
1773                                  struct btrfs_path *path, int *level,
1774                                  struct walk_control *wc)
1775 {
1776         u64 root_owner;
1777         u64 root_gen;
1778         int i;
1779         int slot;
1780         int ret;
1781
1782         for (i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
1783                 slot = path->slots[i];
1784                 if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
1785                         struct extent_buffer *node;
1786                         node = path->nodes[i];
1787                         path->slots[i]++;
1788                         *level = i;
1789                         WARN_ON(*level == 0);
1790                         return 0;
1791                 } else {
1792                         struct extent_buffer *parent;
1793                         if (path->nodes[*level] == root->node)
1794                                 parent = path->nodes[*level];
1795                         else
1796                                 parent = path->nodes[*level + 1];
1797
1798                         root_owner = btrfs_header_owner(parent);
1799                         root_gen = btrfs_header_generation(parent);
1800                         wc->process_func(root, path->nodes[*level], wc,
1801                                  btrfs_header_generation(path->nodes[*level]));
1802                         if (wc->free) {
1803                                 struct extent_buffer *next;
1804
1805                                 next = path->nodes[*level];
1806
1807                                 btrfs_tree_lock(next);
1808                                 clean_tree_block(trans, root, next);
1809                                 btrfs_set_lock_blocking(next);
1810                                 btrfs_wait_tree_block_writeback(next);
1811                                 btrfs_tree_unlock(next);
1812
1813                                 WARN_ON(root_owner != BTRFS_TREE_LOG_OBJECTID);
1814                                 ret = btrfs_free_reserved_extent(root,
1815                                                 path->nodes[*level]->start,
1816                                                 path->nodes[*level]->len);
1817                                 BUG_ON(ret);
1818                         }
1819                         free_extent_buffer(path->nodes[*level]);
1820                         path->nodes[*level] = NULL;
1821                         *level = i + 1;
1822                 }
1823         }
1824         return 1;
1825 }
1826
1827 /*
1828  * drop the reference count on the tree rooted at 'snap'.  This traverses
1829  * the tree freeing any blocks that have a ref count of zero after being
1830  * decremented.
1831  */
1832 static int walk_log_tree(struct btrfs_trans_handle *trans,
1833                          struct btrfs_root *log, struct walk_control *wc)
1834 {
1835         int ret = 0;
1836         int wret;
1837         int level;
1838         struct btrfs_path *path;
1839         int i;
1840         int orig_level;
1841
1842         path = btrfs_alloc_path();
1843         BUG_ON(!path);
1844
1845         level = btrfs_header_level(log->node);
1846         orig_level = level;
1847         path->nodes[level] = log->node;
1848         extent_buffer_get(log->node);
1849         path->slots[level] = 0;
1850
1851         while (1) {
1852                 wret = walk_down_log_tree(trans, log, path, &level, wc);
1853                 if (wret > 0)
1854                         break;
1855                 if (wret < 0)
1856                         ret = wret;
1857
1858                 wret = walk_up_log_tree(trans, log, path, &level, wc);
1859                 if (wret > 0)
1860                         break;
1861                 if (wret < 0)
1862                         ret = wret;
1863         }
1864
1865         /* was the root node processed? if not, catch it here */
1866         if (path->nodes[orig_level]) {
1867                 wc->process_func(log, path->nodes[orig_level], wc,
1868                          btrfs_header_generation(path->nodes[orig_level]));
1869                 if (wc->free) {
1870                         struct extent_buffer *next;
1871
1872                         next = path->nodes[orig_level];
1873
1874                         btrfs_tree_lock(next);
1875                         clean_tree_block(trans, log, next);
1876                         btrfs_set_lock_blocking(next);
1877                         btrfs_wait_tree_block_writeback(next);
1878                         btrfs_tree_unlock(next);
1879
1880                         WARN_ON(log->root_key.objectid !=
1881                                 BTRFS_TREE_LOG_OBJECTID);
1882                         ret = btrfs_free_reserved_extent(log, next->start,
1883                                                          next->len);
1884                         BUG_ON(ret);
1885                 }
1886         }
1887
1888         for (i = 0; i <= orig_level; i++) {
1889                 if (path->nodes[i]) {
1890                         free_extent_buffer(path->nodes[i]);
1891                         path->nodes[i] = NULL;
1892                 }
1893         }
1894         btrfs_free_path(path);
1895         return ret;
1896 }
1897
1898 /*
1899  * helper function to update the item for a given subvolumes log root
1900  * in the tree of log roots
1901  */
1902 static int update_log_root(struct btrfs_trans_handle *trans,
1903                            struct btrfs_root *log)
1904 {
1905         int ret;
1906
1907         if (log->log_transid == 1) {
1908                 /* insert root item on the first sync */
1909                 ret = btrfs_insert_root(trans, log->fs_info->log_root_tree,
1910                                 &log->root_key, &log->root_item);
1911         } else {
1912                 ret = btrfs_update_root(trans, log->fs_info->log_root_tree,
1913                                 &log->root_key, &log->root_item);
1914         }
1915         return ret;
1916 }
1917
1918 static int wait_log_commit(struct btrfs_trans_handle *trans,
1919                            struct btrfs_root *root, unsigned long transid)
1920 {
1921         DEFINE_WAIT(wait);
1922         int index = transid % 2;
1923
1924         /*
1925          * we only allow two pending log transactions at a time,
1926          * so we know that if ours is more than 2 older than the
1927          * current transaction, we're done
1928          */
1929         do {
1930                 prepare_to_wait(&root->log_commit_wait[index],
1931                                 &wait, TASK_UNINTERRUPTIBLE);
1932                 mutex_unlock(&root->log_mutex);
1933
1934                 if (root->fs_info->last_trans_log_full_commit !=
1935                     trans->transid && root->log_transid < transid + 2 &&
1936                     atomic_read(&root->log_commit[index]))
1937                         schedule();
1938
1939                 finish_wait(&root->log_commit_wait[index], &wait);
1940                 mutex_lock(&root->log_mutex);
1941         } while (root->log_transid < transid + 2 &&
1942                  atomic_read(&root->log_commit[index]));
1943         return 0;
1944 }
1945
1946 static int wait_for_writer(struct btrfs_trans_handle *trans,
1947                            struct btrfs_root *root)
1948 {
1949         DEFINE_WAIT(wait);
1950         while (atomic_read(&root->log_writers)) {
1951                 prepare_to_wait(&root->log_writer_wait,
1952                                 &wait, TASK_UNINTERRUPTIBLE);
1953                 mutex_unlock(&root->log_mutex);
1954                 if (root->fs_info->last_trans_log_full_commit !=
1955                     trans->transid && atomic_read(&root->log_writers))
1956                         schedule();
1957                 mutex_lock(&root->log_mutex);
1958                 finish_wait(&root->log_writer_wait, &wait);
1959         }
1960         return 0;
1961 }
1962
1963 /*
1964  * btrfs_sync_log does sends a given tree log down to the disk and
1965  * updates the super blocks to record it.  When this call is done,
1966  * you know that any inodes previously logged are safely on disk only
1967  * if it returns 0.
1968  *
1969  * Any other return value means you need to call btrfs_commit_transaction.
1970  * Some of the edge cases for fsyncing directories that have had unlinks
1971  * or renames done in the past mean that sometimes the only safe
1972  * fsync is to commit the whole FS.  When btrfs_sync_log returns -EAGAIN,
1973  * that has happened.
1974  */
1975 int btrfs_sync_log(struct btrfs_trans_handle *trans,
1976                    struct btrfs_root *root)
1977 {
1978         int index1;
1979         int index2;
1980         int ret;
1981         struct btrfs_root *log = root->log_root;
1982         struct btrfs_root *log_root_tree = root->fs_info->log_root_tree;
1983
1984         mutex_lock(&root->log_mutex);
1985         index1 = root->log_transid % 2;
1986         if (atomic_read(&root->log_commit[index1])) {
1987                 wait_log_commit(trans, root, root->log_transid);
1988                 mutex_unlock(&root->log_mutex);
1989                 return 0;
1990         }
1991         atomic_set(&root->log_commit[index1], 1);
1992
1993         /* wait for previous tree log sync to complete */
1994         if (atomic_read(&root->log_commit[(index1 + 1) % 2]))
1995                 wait_log_commit(trans, root, root->log_transid - 1);
1996
1997         while (root->log_multiple_pids) {
1998                 unsigned long batch = root->log_batch;
1999                 mutex_unlock(&root->log_mutex);
2000                 schedule_timeout_uninterruptible(1);
2001                 mutex_lock(&root->log_mutex);
2002
2003                 wait_for_writer(trans, root);
2004                 if (batch == root->log_batch)
2005                         break;
2006         }
2007
2008         /* bail out if we need to do a full commit */
2009         if (root->fs_info->last_trans_log_full_commit == trans->transid) {
2010                 ret = -EAGAIN;
2011                 mutex_unlock(&root->log_mutex);
2012                 goto out;
2013         }
2014
2015         ret = btrfs_write_and_wait_marked_extents(log, &log->dirty_log_pages);
2016         BUG_ON(ret);
2017
2018         btrfs_set_root_node(&log->root_item, log->node);
2019
2020         root->log_batch = 0;
2021         root->log_transid++;
2022         log->log_transid = root->log_transid;
2023         root->log_start_pid = 0;
2024         smp_mb();
2025         /*
2026          * log tree has been flushed to disk, new modifications of
2027          * the log will be written to new positions. so it's safe to
2028          * allow log writers to go in.
2029          */
2030         mutex_unlock(&root->log_mutex);
2031
2032         mutex_lock(&log_root_tree->log_mutex);
2033         log_root_tree->log_batch++;
2034         atomic_inc(&log_root_tree->log_writers);
2035         mutex_unlock(&log_root_tree->log_mutex);
2036
2037         ret = update_log_root(trans, log);
2038         BUG_ON(ret);
2039
2040         mutex_lock(&log_root_tree->log_mutex);
2041         if (atomic_dec_and_test(&log_root_tree->log_writers)) {
2042                 smp_mb();
2043                 if (waitqueue_active(&log_root_tree->log_writer_wait))
2044                         wake_up(&log_root_tree->log_writer_wait);
2045         }
2046
2047         index2 = log_root_tree->log_transid % 2;
2048         if (atomic_read(&log_root_tree->log_commit[index2])) {
2049                 wait_log_commit(trans, log_root_tree,
2050                                 log_root_tree->log_transid);
2051                 mutex_unlock(&log_root_tree->log_mutex);
2052                 goto out;
2053         }
2054         atomic_set(&log_root_tree->log_commit[index2], 1);
2055
2056         if (atomic_read(&log_root_tree->log_commit[(index2 + 1) % 2])) {
2057                 wait_log_commit(trans, log_root_tree,
2058                                 log_root_tree->log_transid - 1);
2059         }
2060
2061         wait_for_writer(trans, log_root_tree);
2062
2063         /*
2064          * now that we've moved on to the tree of log tree roots,
2065          * check the full commit flag again
2066          */
2067         if (root->fs_info->last_trans_log_full_commit == trans->transid) {
2068                 mutex_unlock(&log_root_tree->log_mutex);
2069                 ret = -EAGAIN;
2070                 goto out_wake_log_root;
2071         }
2072
2073         ret = btrfs_write_and_wait_marked_extents(log_root_tree,
2074                                 &log_root_tree->dirty_log_pages);
2075         BUG_ON(ret);
2076
2077         btrfs_set_super_log_root(&root->fs_info->super_for_commit,
2078                                 log_root_tree->node->start);
2079         btrfs_set_super_log_root_level(&root->fs_info->super_for_commit,
2080                                 btrfs_header_level(log_root_tree->node));
2081
2082         log_root_tree->log_batch = 0;
2083         log_root_tree->log_transid++;
2084         smp_mb();
2085
2086         mutex_unlock(&log_root_tree->log_mutex);
2087
2088         /*
2089          * nobody else is going to jump in and write the the ctree
2090          * super here because the log_commit atomic below is protecting
2091          * us.  We must be called with a transaction handle pinning
2092          * the running transaction open, so a full commit can't hop
2093          * in and cause problems either.
2094          */
2095         write_ctree_super(trans, root->fs_info->tree_root, 2);
2096         ret = 0;
2097
2098 out_wake_log_root:
2099         atomic_set(&log_root_tree->log_commit[index2], 0);
2100         smp_mb();
2101         if (waitqueue_active(&log_root_tree->log_commit_wait[index2]))
2102                 wake_up(&log_root_tree->log_commit_wait[index2]);
2103 out:
2104         atomic_set(&root->log_commit[index1], 0);
2105         smp_mb();
2106         if (waitqueue_active(&root->log_commit_wait[index1]))
2107                 wake_up(&root->log_commit_wait[index1]);
2108         return 0;
2109 }
2110
2111 /*
2112  * free all the extents used by the tree log.  This should be called
2113  * at commit time of the full transaction
2114  */
2115 int btrfs_free_log(struct btrfs_trans_handle *trans, struct btrfs_root *root)
2116 {
2117         int ret;
2118         struct btrfs_root *log;
2119         struct key;
2120         u64 start;
2121         u64 end;
2122         struct walk_control wc = {
2123                 .free = 1,
2124                 .process_func = process_one_buffer
2125         };
2126
2127         if (!root->log_root || root->fs_info->log_root_recovering)
2128                 return 0;
2129
2130         log = root->log_root;
2131         ret = walk_log_tree(trans, log, &wc);
2132         BUG_ON(ret);
2133
2134         while (1) {
2135                 ret = find_first_extent_bit(&log->dirty_log_pages,
2136                                     0, &start, &end, EXTENT_DIRTY);
2137                 if (ret)
2138                         break;
2139
2140                 clear_extent_dirty(&log->dirty_log_pages,
2141                                    start, end, GFP_NOFS);
2142         }
2143
2144         if (log->log_transid > 0) {
2145                 ret = btrfs_del_root(trans, root->fs_info->log_root_tree,
2146                                      &log->root_key);
2147                 BUG_ON(ret);
2148         }
2149         root->log_root = NULL;
2150         free_extent_buffer(log->node);
2151         kfree(log);
2152         return 0;
2153 }
2154
2155 /*
2156  * If both a file and directory are logged, and unlinks or renames are
2157  * mixed in, we have a few interesting corners:
2158  *
2159  * create file X in dir Y
2160  * link file X to X.link in dir Y
2161  * fsync file X
2162  * unlink file X but leave X.link
2163  * fsync dir Y
2164  *
2165  * After a crash we would expect only X.link to exist.  But file X
2166  * didn't get fsync'd again so the log has back refs for X and X.link.
2167  *
2168  * We solve this by removing directory entries and inode backrefs from the
2169  * log when a file that was logged in the current transaction is
2170  * unlinked.  Any later fsync will include the updated log entries, and
2171  * we'll be able to reconstruct the proper directory items from backrefs.
2172  *
2173  * This optimizations allows us to avoid relogging the entire inode
2174  * or the entire directory.
2175  */
2176 int btrfs_del_dir_entries_in_log(struct btrfs_trans_handle *trans,
2177                                  struct btrfs_root *root,
2178                                  const char *name, int name_len,
2179                                  struct inode *dir, u64 index)
2180 {
2181         struct btrfs_root *log;
2182         struct btrfs_dir_item *di;
2183         struct btrfs_path *path;
2184         int ret;
2185         int bytes_del = 0;
2186
2187         if (BTRFS_I(dir)->logged_trans < trans->transid)
2188                 return 0;
2189
2190         ret = join_running_log_trans(root);
2191         if (ret)
2192                 return 0;
2193
2194         mutex_lock(&BTRFS_I(dir)->log_mutex);
2195
2196         log = root->log_root;
2197         path = btrfs_alloc_path();
2198         di = btrfs_lookup_dir_item(trans, log, path, dir->i_ino,
2199                                    name, name_len, -1);
2200         if (di && !IS_ERR(di)) {
2201                 ret = btrfs_delete_one_dir_name(trans, log, path, di);
2202                 bytes_del += name_len;
2203                 BUG_ON(ret);
2204         }
2205         btrfs_release_path(log, path);
2206         di = btrfs_lookup_dir_index_item(trans, log, path, dir->i_ino,
2207                                          index, name, name_len, -1);
2208         if (di && !IS_ERR(di)) {
2209                 ret = btrfs_delete_one_dir_name(trans, log, path, di);
2210                 bytes_del += name_len;
2211                 BUG_ON(ret);
2212         }
2213
2214         /* update the directory size in the log to reflect the names
2215          * we have removed
2216          */
2217         if (bytes_del) {
2218                 struct btrfs_key key;
2219
2220                 key.objectid = dir->i_ino;
2221                 key.offset = 0;
2222                 key.type = BTRFS_INODE_ITEM_KEY;
2223                 btrfs_release_path(log, path);
2224
2225                 ret = btrfs_search_slot(trans, log, &key, path, 0, 1);
2226                 if (ret == 0) {
2227                         struct btrfs_inode_item *item;
2228                         u64 i_size;
2229
2230                         item = btrfs_item_ptr(path->nodes[0], path->slots[0],
2231                                               struct btrfs_inode_item);
2232                         i_size = btrfs_inode_size(path->nodes[0], item);
2233                         if (i_size > bytes_del)
2234                                 i_size -= bytes_del;
2235                         else
2236                                 i_size = 0;
2237                         btrfs_set_inode_size(path->nodes[0], item, i_size);
2238                         btrfs_mark_buffer_dirty(path->nodes[0]);
2239                 } else
2240                         ret = 0;
2241                 btrfs_release_path(log, path);
2242         }
2243
2244         btrfs_free_path(path);
2245         mutex_unlock(&BTRFS_I(dir)->log_mutex);
2246         btrfs_end_log_trans(root);
2247
2248         return 0;
2249 }
2250
2251 /* see comments for btrfs_del_dir_entries_in_log */
2252 int btrfs_del_inode_ref_in_log(struct btrfs_trans_handle *trans,
2253                                struct btrfs_root *root,
2254                                const char *name, int name_len,
2255                                struct inode *inode, u64 dirid)
2256 {
2257         struct btrfs_root *log;
2258         u64 index;
2259         int ret;
2260
2261         if (BTRFS_I(inode)->logged_trans < trans->transid)
2262                 return 0;
2263
2264         ret = join_running_log_trans(root);
2265         if (ret)
2266                 return 0;
2267         log = root->log_root;
2268         mutex_lock(&BTRFS_I(inode)->log_mutex);
2269
2270         ret = btrfs_del_inode_ref(trans, log, name, name_len, inode->i_ino,
2271                                   dirid, &index);
2272         mutex_unlock(&BTRFS_I(inode)->log_mutex);
2273         btrfs_end_log_trans(root);
2274
2275         return ret;
2276 }
2277
2278 /*
2279  * creates a range item in the log for 'dirid'.  first_offset and
2280  * last_offset tell us which parts of the key space the log should
2281  * be considered authoritative for.
2282  */
2283 static noinline int insert_dir_log_key(struct btrfs_trans_handle *trans,
2284                                        struct btrfs_root *log,
2285                                        struct btrfs_path *path,
2286                                        int key_type, u64 dirid,
2287                                        u64 first_offset, u64 last_offset)
2288 {
2289         int ret;
2290         struct btrfs_key key;
2291         struct btrfs_dir_log_item *item;
2292
2293         key.objectid = dirid;
2294         key.offset = first_offset;
2295         if (key_type == BTRFS_DIR_ITEM_KEY)
2296                 key.type = BTRFS_DIR_LOG_ITEM_KEY;
2297         else
2298                 key.type = BTRFS_DIR_LOG_INDEX_KEY;
2299         ret = btrfs_insert_empty_item(trans, log, path, &key, sizeof(*item));
2300         BUG_ON(ret);
2301
2302         item = btrfs_item_ptr(path->nodes[0], path->slots[0],
2303                               struct btrfs_dir_log_item);
2304         btrfs_set_dir_log_end(path->nodes[0], item, last_offset);
2305         btrfs_mark_buffer_dirty(path->nodes[0]);
2306         btrfs_release_path(log, path);
2307         return 0;
2308 }
2309
2310 /*
2311  * log all the items included in the current transaction for a given
2312  * directory.  This also creates the range items in the log tree required
2313  * to replay anything deleted before the fsync
2314  */
2315 static noinline int log_dir_items(struct btrfs_trans_handle *trans,
2316                           struct btrfs_root *root, struct inode *inode,
2317                           struct btrfs_path *path,
2318                           struct btrfs_path *dst_path, int key_type,
2319                           u64 min_offset, u64 *last_offset_ret)
2320 {
2321         struct btrfs_key min_key;
2322         struct btrfs_key max_key;
2323         struct btrfs_root *log = root->log_root;
2324         struct extent_buffer *src;
2325         int ret;
2326         int i;
2327         int nritems;
2328         u64 first_offset = min_offset;
2329         u64 last_offset = (u64)-1;
2330
2331         log = root->log_root;
2332         max_key.objectid = inode->i_ino;
2333         max_key.offset = (u64)-1;
2334         max_key.type = key_type;
2335
2336         min_key.objectid = inode->i_ino;
2337         min_key.type = key_type;
2338         min_key.offset = min_offset;
2339
2340         path->keep_locks = 1;
2341
2342         ret = btrfs_search_forward(root, &min_key, &max_key,
2343                                    path, 0, trans->transid);
2344
2345         /*
2346          * we didn't find anything from this transaction, see if there
2347          * is anything at all
2348          */
2349         if (ret != 0 || min_key.objectid != inode->i_ino ||
2350             min_key.type != key_type) {
2351                 min_key.objectid = inode->i_ino;
2352                 min_key.type = key_type;
2353                 min_key.offset = (u64)-1;
2354                 btrfs_release_path(root, path);
2355                 ret = btrfs_search_slot(NULL, root, &min_key, path, 0, 0);
2356                 if (ret < 0) {
2357                         btrfs_release_path(root, path);
2358                         return ret;
2359                 }
2360                 ret = btrfs_previous_item(root, path, inode->i_ino, key_type);
2361
2362                 /* if ret == 0 there are items for this type,
2363                  * create a range to tell us the last key of this type.
2364                  * otherwise, there are no items in this directory after
2365                  * *min_offset, and we create a range to indicate that.
2366                  */
2367                 if (ret == 0) {
2368                         struct btrfs_key tmp;
2369                         btrfs_item_key_to_cpu(path->nodes[0], &tmp,
2370                                               path->slots[0]);
2371                         if (key_type == tmp.type)
2372                                 first_offset = max(min_offset, tmp.offset) + 1;
2373                 }
2374                 goto done;
2375         }
2376
2377         /* go backward to find any previous key */
2378         ret = btrfs_previous_item(root, path, inode->i_ino, key_type);
2379         if (ret == 0) {
2380                 struct btrfs_key tmp;
2381                 btrfs_item_key_to_cpu(path->nodes[0], &tmp, path->slots[0]);
2382                 if (key_type == tmp.type) {
2383                         first_offset = tmp.offset;
2384                         ret = overwrite_item(trans, log, dst_path,
2385                                              path->nodes[0], path->slots[0],
2386                                              &tmp);
2387                 }
2388         }
2389         btrfs_release_path(root, path);
2390
2391         /* find the first key from this transaction again */
2392         ret = btrfs_search_slot(NULL, root, &min_key, path, 0, 0);
2393         if (ret != 0) {
2394                 WARN_ON(1);
2395                 goto done;
2396         }
2397
2398         /*
2399          * we have a block from this transaction, log every item in it
2400          * from our directory
2401          */
2402         while (1) {
2403                 struct btrfs_key tmp;
2404                 src = path->nodes[0];
2405                 nritems = btrfs_header_nritems(src);
2406                 for (i = path->slots[0]; i < nritems; i++) {
2407                         btrfs_item_key_to_cpu(src, &min_key, i);
2408
2409                         if (min_key.objectid != inode->i_ino ||
2410                             min_key.type != key_type)
2411                                 goto done;
2412                         ret = overwrite_item(trans, log, dst_path, src, i,
2413                                              &min_key);
2414                         BUG_ON(ret);
2415                 }
2416                 path->slots[0] = nritems;
2417
2418                 /*
2419                  * look ahead to the next item and see if it is also
2420                  * from this directory and from this transaction
2421                  */
2422                 ret = btrfs_next_leaf(root, path);
2423                 if (ret == 1) {
2424                         last_offset = (u64)-1;
2425                         goto done;
2426                 }
2427                 btrfs_item_key_to_cpu(path->nodes[0], &tmp, path->slots[0]);
2428                 if (tmp.objectid != inode->i_ino || tmp.type != key_type) {
2429                         last_offset = (u64)-1;
2430                         goto done;
2431                 }
2432                 if (btrfs_header_generation(path->nodes[0]) != trans->transid) {
2433                         ret = overwrite_item(trans, log, dst_path,
2434                                              path->nodes[0], path->slots[0],
2435                                              &tmp);
2436
2437                         BUG_ON(ret);
2438                         last_offset = tmp.offset;
2439                         goto done;
2440                 }
2441         }
2442 done:
2443         *last_offset_ret = last_offset;
2444         btrfs_release_path(root, path);
2445         btrfs_release_path(log, dst_path);
2446
2447         /* insert the log range keys to indicate where the log is valid */
2448         ret = insert_dir_log_key(trans, log, path, key_type, inode->i_ino,
2449                                  first_offset, last_offset);
2450         BUG_ON(ret);
2451         return 0;
2452 }
2453
2454 /*
2455  * logging directories is very similar to logging inodes, We find all the items
2456  * from the current transaction and write them to the log.
2457  *
2458  * The recovery code scans the directory in the subvolume, and if it finds a
2459  * key in the range logged that is not present in the log tree, then it means
2460  * that dir entry was unlinked during the transaction.
2461  *
2462  * In order for that scan to work, we must include one key smaller than
2463  * the smallest logged by this transaction and one key larger than the largest
2464  * key logged by this transaction.
2465  */
2466 static noinline int log_directory_changes(struct btrfs_trans_handle *trans,
2467                           struct btrfs_root *root, struct inode *inode,
2468                           struct btrfs_path *path,
2469                           struct btrfs_path *dst_path)
2470 {
2471         u64 min_key;
2472         u64 max_key;
2473         int ret;
2474         int key_type = BTRFS_DIR_ITEM_KEY;
2475
2476 again:
2477         min_key = 0;
2478         max_key = 0;
2479         while (1) {
2480                 ret = log_dir_items(trans, root, inode, path,
2481                                     dst_path, key_type, min_key,
2482                                     &max_key);
2483                 BUG_ON(ret);
2484                 if (max_key == (u64)-1)
2485                         break;
2486                 min_key = max_key + 1;
2487         }
2488
2489         if (key_type == BTRFS_DIR_ITEM_KEY) {
2490                 key_type = BTRFS_DIR_INDEX_KEY;
2491                 goto again;
2492         }
2493         return 0;
2494 }
2495
2496 /*
2497  * a helper function to drop items from the log before we relog an
2498  * inode.  max_key_type indicates the highest item type to remove.
2499  * This cannot be run for file data extents because it does not
2500  * free the extents they point to.
2501  */
2502 static int drop_objectid_items(struct btrfs_trans_handle *trans,
2503                                   struct btrfs_root *log,
2504                                   struct btrfs_path *path,
2505                                   u64 objectid, int max_key_type)
2506 {
2507         int ret;
2508         struct btrfs_key key;
2509         struct btrfs_key found_key;
2510
2511         key.objectid = objectid;
2512         key.type = max_key_type;
2513         key.offset = (u64)-1;
2514
2515         while (1) {
2516                 ret = btrfs_search_slot(trans, log, &key, path, -1, 1);
2517
2518                 if (ret != 1)
2519                         break;
2520
2521                 if (path->slots[0] == 0)
2522                         break;
2523
2524                 path->slots[0]--;
2525                 btrfs_item_key_to_cpu(path->nodes[0], &found_key,
2526                                       path->slots[0]);
2527
2528                 if (found_key.objectid != objectid)
2529                         break;
2530
2531                 ret = btrfs_del_item(trans, log, path);
2532                 BUG_ON(ret);
2533                 btrfs_release_path(log, path);
2534         }
2535         btrfs_release_path(log, path);
2536         return 0;
2537 }
2538
2539 static noinline int copy_items(struct btrfs_trans_handle *trans,
2540                                struct btrfs_root *log,
2541                                struct btrfs_path *dst_path,
2542                                struct extent_buffer *src,
2543                                int start_slot, int nr, int inode_only)
2544 {
2545         unsigned long src_offset;
2546         unsigned long dst_offset;
2547         struct btrfs_file_extent_item *extent;
2548         struct btrfs_inode_item *inode_item;
2549         int ret;
2550         struct btrfs_key *ins_keys;
2551         u32 *ins_sizes;
2552         char *ins_data;
2553         int i;
2554         struct list_head ordered_sums;
2555
2556         INIT_LIST_HEAD(&ordered_sums);
2557
2558         ins_data = kmalloc(nr * sizeof(struct btrfs_key) +
2559                            nr * sizeof(u32), GFP_NOFS);
2560         ins_sizes = (u32 *)ins_data;
2561         ins_keys = (struct btrfs_key *)(ins_data + nr * sizeof(u32));
2562
2563         for (i = 0; i < nr; i++) {
2564                 ins_sizes[i] = btrfs_item_size_nr(src, i + start_slot);
2565                 btrfs_item_key_to_cpu(src, ins_keys + i, i + start_slot);
2566         }
2567         ret = btrfs_insert_empty_items(trans, log, dst_path,
2568                                        ins_keys, ins_sizes, nr);
2569         BUG_ON(ret);
2570
2571         for (i = 0; i < nr; i++, dst_path->slots[0]++) {
2572                 dst_offset = btrfs_item_ptr_offset(dst_path->nodes[0],
2573                                                    dst_path->slots[0]);
2574
2575                 src_offset = btrfs_item_ptr_offset(src, start_slot + i);
2576
2577                 copy_extent_buffer(dst_path->nodes[0], src, dst_offset,
2578                                    src_offset, ins_sizes[i]);
2579
2580                 if (inode_only == LOG_INODE_EXISTS &&
2581                     ins_keys[i].type == BTRFS_INODE_ITEM_KEY) {
2582                         inode_item = btrfs_item_ptr(dst_path->nodes[0],
2583                                                     dst_path->slots[0],
2584                                                     struct btrfs_inode_item);
2585                         btrfs_set_inode_size(dst_path->nodes[0], inode_item, 0);
2586
2587                         /* set the generation to zero so the recover code
2588                          * can tell the difference between an logging
2589                          * just to say 'this inode exists' and a logging
2590                          * to say 'update this inode with these values'
2591                          */
2592                         btrfs_set_inode_generation(dst_path->nodes[0],
2593                                                    inode_item, 0);
2594                 }
2595                 /* take a reference on file data extents so that truncates
2596                  * or deletes of this inode don't have to relog the inode
2597                  * again
2598                  */
2599                 if (btrfs_key_type(ins_keys + i) == BTRFS_EXTENT_DATA_KEY) {
2600                         int found_type;
2601                         extent = btrfs_item_ptr(src, start_slot + i,
2602                                                 struct btrfs_file_extent_item);
2603
2604                         found_type = btrfs_file_extent_type(src, extent);
2605                         if (found_type == BTRFS_FILE_EXTENT_REG ||
2606                             found_type == BTRFS_FILE_EXTENT_PREALLOC) {
2607                                 u64 ds, dl, cs, cl;
2608                                 ds = btrfs_file_extent_disk_bytenr(src,
2609                                                                 extent);
2610                                 /* ds == 0 is a hole */
2611                                 if (ds == 0)
2612                                         continue;
2613
2614                                 dl = btrfs_file_extent_disk_num_bytes(src,
2615                                                                 extent);
2616                                 cs = btrfs_file_extent_offset(src, extent);
2617                                 cl = btrfs_file_extent_num_bytes(src,
2618                                                                 extent);
2619                                 if (btrfs_file_extent_compression(src,
2620                                                                   extent)) {
2621                                         cs = 0;
2622                                         cl = dl;
2623                                 }
2624
2625                                 ret = btrfs_lookup_csums_range(
2626                                                 log->fs_info->csum_root,
2627                                                 ds + cs, ds + cs + cl - 1,
2628                                                 &ordered_sums);
2629                                 BUG_ON(ret);
2630                         }
2631                 }
2632         }
2633
2634         btrfs_mark_buffer_dirty(dst_path->nodes[0]);
2635         btrfs_release_path(log, dst_path);
2636         kfree(ins_data);
2637
2638         /*
2639          * we have to do this after the loop above to avoid changing the
2640          * log tree while trying to change the log tree.
2641          */
2642         while (!list_empty(&ordered_sums)) {
2643                 struct btrfs_ordered_sum *sums = list_entry(ordered_sums.next,
2644                                                    struct btrfs_ordered_sum,
2645                                                    list);
2646                 ret = btrfs_csum_file_blocks(trans, log, sums);
2647                 BUG_ON(ret);
2648                 list_del(&sums->list);
2649                 kfree(sums);
2650         }
2651         return 0;
2652 }
2653
2654 /* log a single inode in the tree log.
2655  * At least one parent directory for this inode must exist in the tree
2656  * or be logged already.
2657  *
2658  * Any items from this inode changed by the current transaction are copied
2659  * to the log tree.  An extra reference is taken on any extents in this
2660  * file, allowing us to avoid a whole pile of corner cases around logging
2661  * blocks that have been removed from the tree.
2662  *
2663  * See LOG_INODE_ALL and related defines for a description of what inode_only
2664  * does.
2665  *
2666  * This handles both files and directories.
2667  */
2668 static int btrfs_log_inode(struct btrfs_trans_handle *trans,
2669                              struct btrfs_root *root, struct inode *inode,
2670                              int inode_only)
2671 {
2672         struct btrfs_path *path;
2673         struct btrfs_path *dst_path;
2674         struct btrfs_key min_key;
2675         struct btrfs_key max_key;
2676         struct btrfs_root *log = root->log_root;
2677         struct extent_buffer *src = NULL;
2678         u32 size;
2679         int ret;
2680         int nritems;
2681         int ins_start_slot = 0;
2682         int ins_nr;
2683
2684         log = root->log_root;
2685
2686         path = btrfs_alloc_path();
2687         dst_path = btrfs_alloc_path();
2688
2689         min_key.objectid = inode->i_ino;
2690         min_key.type = BTRFS_INODE_ITEM_KEY;
2691         min_key.offset = 0;
2692
2693         max_key.objectid = inode->i_ino;
2694
2695         /* today the code can only do partial logging of directories */
2696         if (!S_ISDIR(inode->i_mode))
2697             inode_only = LOG_INODE_ALL;
2698
2699         if (inode_only == LOG_INODE_EXISTS || S_ISDIR(inode->i_mode))
2700                 max_key.type = BTRFS_XATTR_ITEM_KEY;
2701         else
2702                 max_key.type = (u8)-1;
2703         max_key.offset = (u64)-1;
2704
2705         mutex_lock(&BTRFS_I(inode)->log_mutex);
2706
2707         /*
2708          * a brute force approach to making sure we get the most uptodate
2709          * copies of everything.
2710          */
2711         if (S_ISDIR(inode->i_mode)) {
2712                 int max_key_type = BTRFS_DIR_LOG_INDEX_KEY;
2713
2714                 if (inode_only == LOG_INODE_EXISTS)
2715                         max_key_type = BTRFS_XATTR_ITEM_KEY;
2716                 ret = drop_objectid_items(trans, log, path,
2717                                           inode->i_ino, max_key_type);
2718         } else {
2719                 ret = btrfs_truncate_inode_items(trans, log, inode, 0, 0);
2720         }
2721         BUG_ON(ret);
2722         path->keep_locks = 1;
2723
2724         while (1) {
2725                 ins_nr = 0;
2726                 ret = btrfs_search_forward(root, &min_key, &max_key,
2727                                            path, 0, trans->transid);
2728                 if (ret != 0)
2729                         break;
2730 again:
2731                 /* note, ins_nr might be > 0 here, cleanup outside the loop */
2732                 if (min_key.objectid != inode->i_ino)
2733                         break;
2734                 if (min_key.type > max_key.type)
2735                         break;
2736
2737                 src = path->nodes[0];
2738                 size = btrfs_item_size_nr(src, path->slots[0]);
2739                 if (ins_nr && ins_start_slot + ins_nr == path->slots[0]) {
2740                         ins_nr++;
2741                         goto next_slot;
2742                 } else if (!ins_nr) {
2743                         ins_start_slot = path->slots[0];
2744                         ins_nr = 1;
2745                         goto next_slot;
2746                 }
2747
2748                 ret = copy_items(trans, log, dst_path, src, ins_start_slot,
2749                                  ins_nr, inode_only);
2750                 BUG_ON(ret);
2751                 ins_nr = 1;
2752                 ins_start_slot = path->slots[0];
2753 next_slot:
2754
2755                 nritems = btrfs_header_nritems(path->nodes[0]);
2756                 path->slots[0]++;
2757                 if (path->slots[0] < nritems) {
2758                         btrfs_item_key_to_cpu(path->nodes[0], &min_key,
2759                                               path->slots[0]);
2760                         goto again;
2761                 }
2762                 if (ins_nr) {
2763                         ret = copy_items(trans, log, dst_path, src,
2764                                          ins_start_slot,
2765                                          ins_nr, inode_only);
2766                         BUG_ON(ret);
2767                         ins_nr = 0;
2768                 }
2769                 btrfs_release_path(root, path);
2770
2771                 if (min_key.offset < (u64)-1)
2772                         min_key.offset++;
2773                 else if (min_key.type < (u8)-1)
2774                         min_key.type++;
2775                 else if (min_key.objectid < (u64)-1)
2776                         min_key.objectid++;
2777                 else
2778                         break;
2779         }
2780         if (ins_nr) {
2781                 ret = copy_items(trans, log, dst_path, src,
2782                                  ins_start_slot,
2783                                  ins_nr, inode_only);
2784                 BUG_ON(ret);
2785                 ins_nr = 0;
2786         }
2787         WARN_ON(ins_nr);
2788         if (inode_only == LOG_INODE_ALL && S_ISDIR(inode->i_mode)) {
2789                 btrfs_release_path(root, path);
2790                 btrfs_release_path(log, dst_path);
2791                 ret = log_directory_changes(trans, root, inode, path, dst_path);
2792                 BUG_ON(ret);
2793         }
2794         BTRFS_I(inode)->logged_trans = trans->transid;
2795         mutex_unlock(&BTRFS_I(inode)->log_mutex);
2796
2797         btrfs_free_path(path);
2798         btrfs_free_path(dst_path);
2799         return 0;
2800 }
2801
2802 /*
2803  * follow the dentry parent pointers up the chain and see if any
2804  * of the directories in it require a full commit before they can
2805  * be logged.  Returns zero if nothing special needs to be done or 1 if
2806  * a full commit is required.
2807  */
2808 static noinline int check_parent_dirs_for_sync(struct btrfs_trans_handle *trans,
2809                                                struct inode *inode,
2810                                                struct dentry *parent,
2811                                                struct super_block *sb,
2812                                                u64 last_committed)
2813 {
2814         int ret = 0;
2815         struct btrfs_root *root;
2816
2817         /*
2818          * for regular files, if its inode is already on disk, we don't
2819          * have to worry about the parents at all.  This is because
2820          * we can use the last_unlink_trans field to record renames
2821          * and other fun in this file.
2822          */
2823         if (S_ISREG(inode->i_mode) &&
2824             BTRFS_I(inode)->generation <= last_committed &&
2825             BTRFS_I(inode)->last_unlink_trans <= last_committed)
2826                         goto out;
2827
2828         if (!S_ISDIR(inode->i_mode)) {
2829                 if (!parent || !parent->d_inode || sb != parent->d_inode->i_sb)
2830                         goto out;
2831                 inode = parent->d_inode;
2832         }
2833
2834         while (1) {
2835                 BTRFS_I(inode)->logged_trans = trans->transid;
2836                 smp_mb();
2837
2838                 if (BTRFS_I(inode)->last_unlink_trans > last_committed) {
2839                         root = BTRFS_I(inode)->root;
2840
2841                         /*
2842                          * make sure any commits to the log are forced
2843                          * to be full commits
2844                          */
2845                         root->fs_info->last_trans_log_full_commit =
2846                                 trans->transid;
2847                         ret = 1;
2848                         break;
2849                 }
2850
2851                 if (!parent || !parent->d_inode || sb != parent->d_inode->i_sb)
2852                         break;
2853
2854                 if (IS_ROOT(parent))
2855                         break;
2856
2857                 parent = parent->d_parent;
2858                 inode = parent->d_inode;
2859
2860         }
2861 out:
2862         return ret;
2863 }
2864
2865 /*
2866  * helper function around btrfs_log_inode to make sure newly created
2867  * parent directories also end up in the log.  A minimal inode and backref
2868  * only logging is done of any parent directories that are older than
2869  * the last committed transaction
2870  */
2871 int btrfs_log_inode_parent(struct btrfs_trans_handle *trans,
2872                     struct btrfs_root *root, struct inode *inode,
2873                     struct dentry *parent, int exists_only)
2874 {
2875         int inode_only = exists_only ? LOG_INODE_EXISTS : LOG_INODE_ALL;
2876         struct super_block *sb;
2877         int ret = 0;
2878         u64 last_committed = root->fs_info->last_trans_committed;
2879
2880         sb = inode->i_sb;
2881
2882         if (btrfs_test_opt(root, NOTREELOG)) {
2883                 ret = 1;
2884                 goto end_no_trans;
2885         }
2886
2887         if (root->fs_info->last_trans_log_full_commit >
2888             root->fs_info->last_trans_committed) {
2889                 ret = 1;
2890                 goto end_no_trans;
2891         }
2892
2893         if (root != BTRFS_I(inode)->root ||
2894             btrfs_root_refs(&root->root_item) == 0) {
2895                 ret = 1;
2896                 goto end_no_trans;
2897         }
2898
2899         ret = check_parent_dirs_for_sync(trans, inode, parent,
2900                                          sb, last_committed);
2901         if (ret)
2902                 goto end_no_trans;
2903
2904         start_log_trans(trans, root);
2905
2906         ret = btrfs_log_inode(trans, root, inode, inode_only);
2907         BUG_ON(ret);
2908
2909         /*
2910          * for regular files, if its inode is already on disk, we don't
2911          * have to worry about the parents at all.  This is because
2912          * we can use the last_unlink_trans field to record renames
2913          * and other fun in this file.
2914          */
2915         if (S_ISREG(inode->i_mode) &&
2916             BTRFS_I(inode)->generation <= last_committed &&
2917             BTRFS_I(inode)->last_unlink_trans <= last_committed)
2918                         goto no_parent;
2919
2920         inode_only = LOG_INODE_EXISTS;
2921         while (1) {
2922                 if (!parent || !parent->d_inode || sb != parent->d_inode->i_sb)
2923                         break;
2924
2925                 inode = parent->d_inode;
2926                 if (root != BTRFS_I(inode)->root)
2927                         break;
2928
2929                 if (BTRFS_I(inode)->generation >
2930                     root->fs_info->last_trans_committed) {
2931                         ret = btrfs_log_inode(trans, root, inode, inode_only);
2932                         BUG_ON(ret);
2933                 }
2934                 if (IS_ROOT(parent))
2935                         break;
2936
2937                 parent = parent->d_parent;
2938         }
2939 no_parent:
2940         ret = 0;
2941         btrfs_end_log_trans(root);
2942 end_no_trans:
2943         return ret;
2944 }
2945
2946 /*
2947  * it is not safe to log dentry if the chunk root has added new
2948  * chunks.  This returns 0 if the dentry was logged, and 1 otherwise.
2949  * If this returns 1, you must commit the transaction to safely get your
2950  * data on disk.
2951  */
2952 int btrfs_log_dentry_safe(struct btrfs_trans_handle *trans,
2953                           struct btrfs_root *root, struct dentry *dentry)
2954 {
2955         return btrfs_log_inode_parent(trans, root, dentry->d_inode,
2956                                       dentry->d_parent, 0);
2957 }
2958
2959 /*
2960  * should be called during mount to recover any replay any log trees
2961  * from the FS
2962  */
2963 int btrfs_recover_log_trees(struct btrfs_root *log_root_tree)
2964 {
2965         int ret;
2966         struct btrfs_path *path;
2967         struct btrfs_trans_handle *trans;
2968         struct btrfs_key key;
2969         struct btrfs_key found_key;
2970         struct btrfs_key tmp_key;
2971         struct btrfs_root *log;
2972         struct btrfs_fs_info *fs_info = log_root_tree->fs_info;
2973         struct walk_control wc = {
2974                 .process_func = process_one_buffer,
2975                 .stage = 0,
2976         };
2977
2978         fs_info->log_root_recovering = 1;
2979         path = btrfs_alloc_path();
2980         BUG_ON(!path);
2981
2982         trans = btrfs_start_transaction(fs_info->tree_root, 1);
2983
2984         wc.trans = trans;
2985         wc.pin = 1;
2986
2987         walk_log_tree(trans, log_root_tree, &wc);
2988
2989 again:
2990         key.objectid = BTRFS_TREE_LOG_OBJECTID;
2991         key.offset = (u64)-1;
2992         btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY);
2993
2994         while (1) {
2995                 ret = btrfs_search_slot(NULL, log_root_tree, &key, path, 0, 0);
2996                 if (ret < 0)
2997                         break;
2998                 if (ret > 0) {
2999                         if (path->slots[0] == 0)
3000                                 break;
3001                         path->slots[0]--;
3002                 }
3003                 btrfs_item_key_to_cpu(path->nodes[0], &found_key,
3004                                       path->slots[0]);
3005                 btrfs_release_path(log_root_tree, path);
3006                 if (found_key.objectid != BTRFS_TREE_LOG_OBJECTID)
3007                         break;
3008
3009                 log = btrfs_read_fs_root_no_radix(log_root_tree,
3010                                                   &found_key);
3011                 BUG_ON(!log);
3012
3013
3014                 tmp_key.objectid = found_key.offset;
3015                 tmp_key.type = BTRFS_ROOT_ITEM_KEY;
3016                 tmp_key.offset = (u64)-1;
3017
3018                 wc.replay_dest = btrfs_read_fs_root_no_name(fs_info, &tmp_key);
3019                 BUG_ON(!wc.replay_dest);
3020
3021                 wc.replay_dest->log_root = log;
3022                 btrfs_record_root_in_trans(trans, wc.replay_dest);
3023                 ret = walk_log_tree(trans, log, &wc);
3024                 BUG_ON(ret);
3025
3026                 if (wc.stage == LOG_WALK_REPLAY_ALL) {
3027                         ret = fixup_inode_link_counts(trans, wc.replay_dest,
3028                                                       path);
3029                         BUG_ON(ret);
3030                 }
3031
3032                 key.offset = found_key.offset - 1;
3033                 wc.replay_dest->log_root = NULL;
3034                 free_extent_buffer(log->node);
3035                 free_extent_buffer(log->commit_root);
3036                 kfree(log);
3037
3038                 if (found_key.offset == 0)
3039                         break;
3040         }
3041         btrfs_release_path(log_root_tree, path);
3042
3043         /* step one is to pin it all, step two is to replay just inodes */
3044         if (wc.pin) {
3045                 wc.pin = 0;
3046                 wc.process_func = replay_one_buffer;
3047                 wc.stage = LOG_WALK_REPLAY_INODES;
3048                 goto again;
3049         }
3050         /* step three is to replay everything */
3051         if (wc.stage < LOG_WALK_REPLAY_ALL) {
3052                 wc.stage++;
3053                 goto again;
3054         }
3055
3056         btrfs_free_path(path);
3057
3058         free_extent_buffer(log_root_tree->node);
3059         log_root_tree->log_root = NULL;
3060         fs_info->log_root_recovering = 0;
3061
3062         /* step 4: commit the transaction, which also unpins the blocks */
3063         btrfs_commit_transaction(trans, fs_info->tree_root);
3064
3065         kfree(log_root_tree);
3066         return 0;
3067 }
3068
3069 /*
3070  * there are some corner cases where we want to force a full
3071  * commit instead of allowing a directory to be logged.
3072  *
3073  * They revolve around files there were unlinked from the directory, and
3074  * this function updates the parent directory so that a full commit is
3075  * properly done if it is fsync'd later after the unlinks are done.
3076  */
3077 void btrfs_record_unlink_dir(struct btrfs_trans_handle *trans,
3078                              struct inode *dir, struct inode *inode,
3079                              int for_rename)
3080 {
3081         /*
3082          * when we're logging a file, if it hasn't been renamed
3083          * or unlinked, and its inode is fully committed on disk,
3084          * we don't have to worry about walking up the directory chain
3085          * to log its parents.
3086          *
3087          * So, we use the last_unlink_trans field to put this transid
3088          * into the file.  When the file is logged we check it and
3089          * don't log the parents if the file is fully on disk.
3090          */
3091         if (S_ISREG(inode->i_mode))
3092                 BTRFS_I(inode)->last_unlink_trans = trans->transid;
3093
3094         /*
3095          * if this directory was already logged any new
3096          * names for this file/dir will get recorded
3097          */
3098         smp_mb();
3099         if (BTRFS_I(dir)->logged_trans == trans->transid)
3100                 return;
3101
3102         /*
3103          * if the inode we're about to unlink was logged,
3104          * the log will be properly updated for any new names
3105          */
3106         if (BTRFS_I(inode)->logged_trans == trans->transid)
3107                 return;
3108
3109         /*
3110          * when renaming files across directories, if the directory
3111          * there we're unlinking from gets fsync'd later on, there's
3112          * no way to find the destination directory later and fsync it
3113          * properly.  So, we have to be conservative and force commits
3114          * so the new name gets discovered.
3115          */
3116         if (for_rename)
3117                 goto record;
3118
3119         /* we can safely do the unlink without any special recording */
3120         return;
3121
3122 record:
3123         BTRFS_I(dir)->last_unlink_trans = trans->transid;
3124 }
3125
3126 /*
3127  * Call this after adding a new name for a file and it will properly
3128  * update the log to reflect the new name.
3129  *
3130  * It will return zero if all goes well, and it will return 1 if a
3131  * full transaction commit is required.
3132  */
3133 int btrfs_log_new_name(struct btrfs_trans_handle *trans,
3134                         struct inode *inode, struct inode *old_dir,
3135                         struct dentry *parent)
3136 {
3137         struct btrfs_root * root = BTRFS_I(inode)->root;
3138
3139         /*
3140          * this will force the logging code to walk the dentry chain
3141          * up for the file
3142          */
3143         if (S_ISREG(inode->i_mode))
3144                 BTRFS_I(inode)->last_unlink_trans = trans->transid;
3145
3146         /*
3147          * if this inode hasn't been logged and directory we're renaming it
3148          * from hasn't been logged, we don't need to log it
3149          */
3150         if (BTRFS_I(inode)->logged_trans <=
3151             root->fs_info->last_trans_committed &&
3152             (!old_dir || BTRFS_I(old_dir)->logged_trans <=
3153                     root->fs_info->last_trans_committed))
3154                 return 0;
3155
3156         return btrfs_log_inode_parent(trans, root, inode, parent, 1);
3157 }
3158