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 <linux/slab.h>
  21 #include <linux/blkdev.h>
  22 #include <linux/list_sort.h>
  23 #include "tree-log.h"
  24 #include "disk-io.h"
  25 #include "locking.h"
  26 #include "print-tree.h"
  27 #include "backref.h"
  28 #include "hash.h"
  29 #include "inode-map.h"
  30
  31 /* magic values for the inode_only field in btrfs_log_inode:
  32  *
  33  * LOG_INODE_ALL means to log everything
  34  * LOG_INODE_EXISTS means to log just enough to recreate the inode
  35  * during log replay
  36  */
  37 #define LOG_INODE_ALL 0
  38 #define LOG_INODE_EXISTS 1
  39
  40 /*
  41  * directory trouble cases
  42  *
  43  * 1) on rename or unlink, if the inode being unlinked isn't in the fsync
  44  * log, we must force a full commit before doing an fsync of the directory
  45  * where the unlink was done.
  46  * ---> record transid of last unlink/rename per directory
  47  *
  48  * mkdir foo/some_dir
  49  * normal commit
  50  * rename foo/some_dir foo2/some_dir
  51  * mkdir foo/some_dir
  52  * fsync foo/some_dir/some_file
  53  *
  54  * The fsync above will unlink the original some_dir without recording
  55  * it in its new location (foo2).  After a crash, some_dir will be gone
  56  * unless the fsync of some_file forces a full commit
  57  *
  58  * 2) we must log any new names for any file or dir that is in the fsync
  59  * log. ---> check inode while renaming/linking.
  60  *
  61  * 2a) we must log any new names for any file or dir during rename
  62  * when the directory they are being removed from was logged.
  63  * ---> check inode and old parent dir during rename
  64  *
  65  *  2a is actually the more important variant.  With the extra logging
  66  *  a crash might unlink the old name without recreating the new one
  67  *
  68  * 3) after a crash, we must go through any directories with a link count
  69  * of zero and redo the rm -rf
  70  *
  71  * mkdir f1/foo
  72  * normal commit
  73  * rm -rf f1/foo
  74  * fsync(f1)
  75  *
  76  * The directory f1 was fully removed from the FS, but fsync was never
  77  * called on f1, only its parent dir.  After a crash the rm -rf must
  78  * be replayed.  This must be able to recurse down the entire
  79  * directory tree.  The inode link count fixup code takes care of the
  80  * ugly details.
  81  */
  82
  83 /*
  84  * stages for the tree walking.  The first
  85  * stage (0) is to only pin down the blocks we find
  86  * the second stage (1) is to make sure that all the inodes
  87  * we find in the log are created in the subvolume.
  88  *
  89  * The last stage is to deal with directories and links and extents
  90  * and all the other fun semantics
  91  */
  92 #define LOG_WALK_PIN_ONLY 0
  93 #define LOG_WALK_REPLAY_INODES 1
  94 #define LOG_WALK_REPLAY_DIR_INDEX 2
  95 #define LOG_WALK_REPLAY_ALL 3
  96
  97 static int btrfs_log_inode(struct btrfs_trans_handle *trans,
  98                            struct btrfs_root *root, struct inode *inode,
  99                            int inode_only,
 100                            const loff_t start,
 101                            const loff_t end,
 102                            struct btrfs_log_ctx *ctx);
 103 static int link_to_fixup_dir(struct btrfs_trans_handle *trans,
 104                              struct btrfs_root *root,
 105                              struct btrfs_path *path, u64 objectid);
 106 static noinline int replay_dir_deletes(struct btrfs_trans_handle *trans,
 107                                        struct btrfs_root *root,
 108                                        struct btrfs_root *log,
 109                                        struct btrfs_path *path,
 110                                        u64 dirid, int del_all);
 111
 112 /*
 113  * tree logging is a special write ahead log used to make sure that
 114  * fsyncs and O_SYNCs can happen without doing full tree commits.
 115  *
 116  * Full tree commits are expensive because they require commonly
 117  * modified blocks to be recowed, creating many dirty pages in the
 118  * extent tree an 4x-6x higher write load than ext3.
 119  *
 120  * Instead of doing a tree commit on every fsync, we use the
 121  * key ranges and transaction ids to find items for a given file or directory
 122  * that have changed in this transaction.  Those items are copied into
 123  * a special tree (one per subvolume root), that tree is written to disk
 124  * and then the fsync is considered complete.
 125  *
 126  * After a crash, items are copied out of the log-tree back into the
 127  * subvolume tree.  Any file data extents found are recorded in the extent
 128  * allocation tree, and the log-tree freed.
 129  *
 130  * The log tree is read three times, once to pin down all the extents it is
 131  * using in ram and once, once to create all the inodes logged in the tree
 132  * and once to do all the other items.
 133  */
 134
 135 /*
 136  * start a sub transaction and setup the log tree
 137  * this increments the log tree writer count to make the people
 138  * syncing the tree wait for us to finish
 139  */
 140 static int start_log_trans(struct btrfs_trans_handle *trans,
 141                            struct btrfs_root *root,
 142                            struct btrfs_log_ctx *ctx)
 143 {
 144         int ret = 0;
 145
 146         mutex_lock(&root->log_mutex);
 147
 148         if (root->log_root) {
 149                 if (btrfs_need_log_full_commit(root->fs_info, trans)) {
 150                         ret = -EAGAIN;
 151                         goto out;
 152                 }
 153
 154                 if (!root->log_start_pid) {
 155                         clear_bit(BTRFS_ROOT_MULTI_LOG_TASKS, &root->state);
 156                         root->log_start_pid = current->pid;
 157                 } else if (root->log_start_pid != current->pid) {
 158                         set_bit(BTRFS_ROOT_MULTI_LOG_TASKS, &root->state);
 159                 }
 160         } else {
 161                 mutex_lock(&root->fs_info->tree_log_mutex);
 162                 if (!root->fs_info->log_root_tree)
 163                         ret = btrfs_init_log_root_tree(trans, root->fs_info);
 164                 mutex_unlock(&root->fs_info->tree_log_mutex);
 165                 if (ret)
 166                         goto out;
 167
 168                 ret = btrfs_add_log_tree(trans, root);
 169                 if (ret)
 170                         goto out;
 171
 172                 clear_bit(BTRFS_ROOT_MULTI_LOG_TASKS, &root->state);
 173                 root->log_start_pid = current->pid;
 174         }
 175
 176         atomic_inc(&root->log_batch);
 177         atomic_inc(&root->log_writers);
 178         if (ctx) {
 179                 int index = root->log_transid % 2;
 180                 list_add_tail(&ctx->list, &root->log_ctxs[index]);
 181                 ctx->log_transid = root->log_transid;
 182         }
 183
 184 out:
 185         mutex_unlock(&root->log_mutex);
 186         return ret;
 187 }
 188
 189 /*
 190  * returns 0 if there was a log transaction running and we were able
 191  * to join, or returns -ENOENT if there were not transactions
 192  * in progress
 193  */
 194 static int join_running_log_trans(struct btrfs_root *root)
 195 {
 196         int ret = -ENOENT;
 197
 198         smp_mb();
 199         if (!root->log_root)
 200                 return -ENOENT;
 201
 202         mutex_lock(&root->log_mutex);
 203         if (root->log_root) {
 204                 ret = 0;
 205                 atomic_inc(&root->log_writers);
 206         }
 207         mutex_unlock(&root->log_mutex);
 208         return ret;
 209 }
 210
 211 /*
 212  * This either makes the current running log transaction wait
 213  * until you call btrfs_end_log_trans() or it makes any future
 214  * log transactions wait until you call btrfs_end_log_trans()
 215  */
 216 int btrfs_pin_log_trans(struct btrfs_root *root)
 217 {
 218         int ret = -ENOENT;
 219
 220         mutex_lock(&root->log_mutex);
 221         atomic_inc(&root->log_writers);
 222         mutex_unlock(&root->log_mutex);
 223         return ret;
 224 }
 225
 226 /*
 227  * indicate we're done making changes to the log tree
 228  * and wake up anyone waiting to do a sync
 229  */
 230 void btrfs_end_log_trans(struct btrfs_root *root)
 231 {
 232         if (atomic_dec_and_test(&root->log_writers)) {
 233                 /*
 234                  * Implicit memory barrier after atomic_dec_and_test
 235                  */
 236                 if (waitqueue_active(&root->log_writer_wait))
 237                         wake_up(&root->log_writer_wait);
 238         }
 239 }
 240
 241
 242 /*
 243  * the walk control struct is used to pass state down the chain when
 244  * processing the log tree.  The stage field tells us which part
 245  * of the log tree processing we are currently doing.  The others
 246  * are state fields used for that specific part
 247  */
 248 struct walk_control {
 249         /* should we free the extent on disk when done?  This is used
 250          * at transaction commit time while freeing a log tree
 251          */
 252         int free;
 253
 254         /* should we write out the extent buffer?  This is used
 255          * while flushing the log tree to disk during a sync
 256          */
 257         int write;
 258
 259         /* should we wait for the extent buffer io to finish?  Also used
 260          * while flushing the log tree to disk for a sync
 261          */
 262         int wait;
 263
 264         /* pin only walk, we record which extents on disk belong to the
 265          * log trees
 266          */
 267         int pin;
 268
 269         /* what stage of the replay code we're currently in */
 270         int stage;
 271
 272         /* the root we are currently replaying */
 273         struct btrfs_root *replay_dest;
 274
 275         /* the trans handle for the current replay */
 276         struct btrfs_trans_handle *trans;
 277
 278         /* the function that gets used to process blocks we find in the
 279          * tree.  Note the extent_buffer might not be up to date when it is
 280          * passed in, and it must be checked or read if you need the data
 281          * inside it
 282          */
 283         int (*process_func)(struct btrfs_root *log, struct extent_buffer *eb,
 284                             struct walk_control *wc, u64 gen);
 285 };
 286
 287 /*
 288  * process_func used to pin down extents, write them or wait on them
 289  */
 290 static int process_one_buffer(struct btrfs_root *log,
 291                               struct extent_buffer *eb,
 292                               struct walk_control *wc, u64 gen)
 293 {
 294         int ret = 0;
 295
 296         /*
 297          * If this fs is mixed then we need to be able to process the leaves to
 298          * pin down any logged extents, so we have to read the block.
 299          */
 300         if (btrfs_fs_incompat(log->fs_info, MIXED_GROUPS)) {
 301                 ret = btrfs_read_buffer(eb, gen);
 302                 if (ret)
 303                         return ret;
 304         }
 305
 306         if (wc->pin)
 307                 ret = btrfs_pin_extent_for_log_replay(log->fs_info->extent_root,
 308                                                       eb->start, eb->len);
 309
 310         if (!ret && btrfs_buffer_uptodate(eb, gen, 0)) {
 311                 if (wc->pin && btrfs_header_level(eb) == 0)
 312                         ret = btrfs_exclude_logged_extents(log, eb);
 313                 if (wc->write)
 314                         btrfs_write_tree_block(eb);
 315                 if (wc->wait)
 316                         btrfs_wait_tree_block_writeback(eb);
 317         }
 318         return ret;
 319 }
 320
 321 /*
 322  * Item overwrite used by replay and tree logging.  eb, slot and key all refer
 323  * to the src data we are copying out.
 324  *
 325  * root is the tree we are copying into, and path is a scratch
 326  * path for use in this function (it should be released on entry and
 327  * will be released on exit).
 328  *
 329  * If the key is already in the destination tree the existing item is
 330  * overwritten.  If the existing item isn't big enough, it is extended.
 331  * If it is too large, it is truncated.
 332  *
 333  * If the key isn't in the destination yet, a new item is inserted.
 334  */
 335 static noinline int overwrite_item(struct btrfs_trans_handle *trans,
 336                                    struct btrfs_root *root,
 337                                    struct btrfs_path *path,
 338                                    struct extent_buffer *eb, int slot,
 339                                    struct btrfs_key *key)
 340 {
 341         int ret;
 342         u32 item_size;
 343         u64 saved_i_size = 0;
 344         int save_old_i_size = 0;
 345         unsigned long src_ptr;
 346         unsigned long dst_ptr;
 347         int overwrite_root = 0;
 348         bool inode_item = key->type == BTRFS_INODE_ITEM_KEY;
 349
 350         if (root->root_key.objectid != BTRFS_TREE_LOG_OBJECTID)
 351                 overwrite_root = 1;
 352
 353         item_size = btrfs_item_size_nr(eb, slot);
 354         src_ptr = btrfs_item_ptr_offset(eb, slot);
 355
 356         /* look for the key in the destination tree */
 357         ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
 358         if (ret < 0)
 359                 return ret;
 360
 361         if (ret == 0) {
 362                 char *src_copy;
 363                 char *dst_copy;
 364                 u32 dst_size = btrfs_item_size_nr(path->nodes[0],
 365                                                   path->slots[0]);
 366                 if (dst_size != item_size)
 367                         goto insert;
 368
 369                 if (item_size == 0) {
 370                         btrfs_release_path(path);
 371                         return 0;
 372                 }
 373                 dst_copy = kmalloc(item_size, GFP_NOFS);
 374                 src_copy = kmalloc(item_size, GFP_NOFS);
 375                 if (!dst_copy || !src_copy) {
 376                         btrfs_release_path(path);
 377                         kfree(dst_copy);
 378                         kfree(src_copy);
 379                         return -ENOMEM;
 380                 }
 381
 382                 read_extent_buffer(eb, src_copy, src_ptr, item_size);
 383
 384                 dst_ptr = btrfs_item_ptr_offset(path->nodes[0], path->slots[0]);
 385                 read_extent_buffer(path->nodes[0], dst_copy, dst_ptr,
 386                                    item_size);
 387                 ret = memcmp(dst_copy, src_copy, item_size);
 388
 389                 kfree(dst_copy);
 390                 kfree(src_copy);
 391                 /*
 392                  * they have the same contents, just return, this saves
 393                  * us from cowing blocks in the destination tree and doing
 394                  * extra writes that may not have been done by a previous
 395                  * sync
 396                  */
 397                 if (ret == 0) {
 398                         btrfs_release_path(path);
 399                         return 0;
 400                 }
 401
 402                 /*
 403                  * We need to load the old nbytes into the inode so when we
 404                  * replay the extents we've logged we get the right nbytes.
 405                  */
 406                 if (inode_item) {
 407                         struct btrfs_inode_item *item;
 408                         u64 nbytes;
 409                         u32 mode;
 410
 411                         item = btrfs_item_ptr(path->nodes[0], path->slots[0],
 412                                               struct btrfs_inode_item);
 413                         nbytes = btrfs_inode_nbytes(path->nodes[0], item);
 414                         item = btrfs_item_ptr(eb, slot,
 415                                               struct btrfs_inode_item);
 416                         btrfs_set_inode_nbytes(eb, item, nbytes);
 417
 418                         /*
 419                          * If this is a directory we need to reset the i_size to
 420                          * 0 so that we can set it up properly when replaying
 421                          * the rest of the items in this log.
 422                          */
 423                         mode = btrfs_inode_mode(eb, item);
 424                         if (S_ISDIR(mode))
 425                                 btrfs_set_inode_size(eb, item, 0);
 426                 }
 427         } else if (inode_item) {
 428                 struct btrfs_inode_item *item;
 429                 u32 mode;
 430
 431                 /*
 432                  * New inode, set nbytes to 0 so that the nbytes comes out
 433                  * properly when we replay the extents.
 434                  */
 435                 item = btrfs_item_ptr(eb, slot, struct btrfs_inode_item);
 436                 btrfs_set_inode_nbytes(eb, item, 0);
 437
 438                 /*
 439                  * If this is a directory we need to reset the i_size to 0 so
 440                  * that we can set it up properly when replaying the rest of
 441                  * the items in this log.
 442                  */
 443                 mode = btrfs_inode_mode(eb, item);
 444                 if (S_ISDIR(mode))
 445                         btrfs_set_inode_size(eb, item, 0);
 446         }
 447 insert:
 448         btrfs_release_path(path);
 449         /* try to insert the key into the destination tree */
 450         path->skip_release_on_error = 1;
 451         ret = btrfs_insert_empty_item(trans, root, path,
 452                                       key, item_size);
 453         path->skip_release_on_error = 0;
 454
 455         /* make sure any existing item is the correct size */
 456         if (ret == -EEXIST || ret == -EOVERFLOW) {
 457                 u32 found_size;
 458                 found_size = btrfs_item_size_nr(path->nodes[0],
 459                                                 path->slots[0]);
 460                 if (found_size > item_size)
 461                         btrfs_truncate_item(root, path, item_size, 1);
 462                 else if (found_size < item_size)
 463                         btrfs_extend_item(root, path,
 464                                           item_size - found_size);
 465         } else if (ret) {
 466                 return ret;
 467         }
 468         dst_ptr = btrfs_item_ptr_offset(path->nodes[0],
 469                                         path->slots[0]);
 470
 471         /* don't overwrite an existing inode if the generation number
 472          * was logged as zero.  This is done when the tree logging code
 473          * is just logging an inode to make sure it exists after recovery.
 474          *
 475          * Also, don't overwrite i_size on directories during replay.
 476          * log replay inserts and removes directory items based on the
 477          * state of the tree found in the subvolume, and i_size is modified
 478          * as it goes
 479          */
 480         if (key->type == BTRFS_INODE_ITEM_KEY && ret == -EEXIST) {
 481                 struct btrfs_inode_item *src_item;
 482                 struct btrfs_inode_item *dst_item;
 483
 484                 src_item = (struct btrfs_inode_item *)src_ptr;
 485                 dst_item = (struct btrfs_inode_item *)dst_ptr;
 486
 487                 if (btrfs_inode_generation(eb, src_item) == 0) {
 488                         struct extent_buffer *dst_eb = path->nodes[0];
 489                         const u64 ino_size = btrfs_inode_size(eb, src_item);
 490
 491                         /*
 492                          * For regular files an ino_size == 0 is used only when
 493                          * logging that an inode exists, as part of a directory
 494                          * fsync, and the inode wasn't fsynced before. In this
 495                          * case don't set the size of the inode in the fs/subvol
 496                          * tree, otherwise we would be throwing valid data away.
 497                          */
 498                         if (S_ISREG(btrfs_inode_mode(eb, src_item)) &&
 499                             S_ISREG(btrfs_inode_mode(dst_eb, dst_item)) &&
 500                             ino_size != 0) {
 501                                 struct btrfs_map_token token;
 502
 503                                 btrfs_init_map_token(&token);
 504                                 btrfs_set_token_inode_size(dst_eb, dst_item,
 505                                                            ino_size, &token);
 506                         }
 507                         goto no_copy;
 508                 }
 509
 510                 if (overwrite_root &&
 511                     S_ISDIR(btrfs_inode_mode(eb, src_item)) &&
 512                     S_ISDIR(btrfs_inode_mode(path->nodes[0], dst_item))) {
 513                         save_old_i_size = 1;
 514                         saved_i_size = btrfs_inode_size(path->nodes[0],
 515                                                         dst_item);
 516                 }
 517         }
 518
 519         copy_extent_buffer(path->nodes[0], eb, dst_ptr,
 520                            src_ptr, item_size);
 521
 522         if (save_old_i_size) {
 523                 struct btrfs_inode_item *dst_item;
 524                 dst_item = (struct btrfs_inode_item *)dst_ptr;
 525                 btrfs_set_inode_size(path->nodes[0], dst_item, saved_i_size);
 526         }
 527
 528         /* make sure the generation is filled in */
 529         if (key->type == BTRFS_INODE_ITEM_KEY) {
 530                 struct btrfs_inode_item *dst_item;
 531                 dst_item = (struct btrfs_inode_item *)dst_ptr;
 532                 if (btrfs_inode_generation(path->nodes[0], dst_item) == 0) {
 533                         btrfs_set_inode_generation(path->nodes[0], dst_item,
 534                                                    trans->transid);
 535                 }
 536         }
 537 no_copy:
 538         btrfs_mark_buffer_dirty(path->nodes[0]);
 539         btrfs_release_path(path);
 540         return 0;
 541 }
 542
 543 /*
 544  * simple helper to read an inode off the disk from a given root
 545  * This can only be called for subvolume roots and not for the log
 546  */
 547 static noinline struct inode *read_one_inode(struct btrfs_root *root,
 548                                              u64 objectid)
 549 {
 550         struct btrfs_key key;
 551         struct inode *inode;
 552
 553         key.objectid = objectid;
 554         key.type = BTRFS_INODE_ITEM_KEY;
 555         key.offset = 0;
 556         inode = btrfs_iget(root->fs_info->sb, &key, root, NULL);
 557         if (IS_ERR(inode)) {
 558                 inode = NULL;
 559         } else if (is_bad_inode(inode)) {
 560                 iput(inode);
 561                 inode = NULL;
 562         }
 563         return inode;
 564 }
 565
 566 /* replays a single extent in 'eb' at 'slot' with 'key' into the
 567  * subvolume 'root'.  path is released on entry and should be released
 568  * on exit.
 569  *
 570  * extents in the log tree have not been allocated out of the extent
 571  * tree yet.  So, this completes the allocation, taking a reference
 572  * as required if the extent already exists or creating a new extent
 573  * if it isn't in the extent allocation tree yet.
 574  *
 575  * The extent is inserted into the file, dropping any existing extents
 576  * from the file that overlap the new one.
 577  */
 578 static noinline int replay_one_extent(struct btrfs_trans_handle *trans,
 579                                       struct btrfs_root *root,
 580                                       struct btrfs_path *path,
 581                                       struct extent_buffer *eb, int slot,
 582                                       struct btrfs_key *key)
 583 {
 584         int found_type;
 585         u64 extent_end;
 586         u64 start = key->offset;
 587         u64 nbytes = 0;
 588         struct btrfs_file_extent_item *item;
 589         struct inode *inode = NULL;
 590         unsigned long size;
 591         int ret = 0;
 592
 593         item = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
 594         found_type = btrfs_file_extent_type(eb, item);
 595
 596         if (found_type == BTRFS_FILE_EXTENT_REG ||
 597             found_type == BTRFS_FILE_EXTENT_PREALLOC) {
 598                 nbytes = btrfs_file_extent_num_bytes(eb, item);
 599                 extent_end = start + nbytes;
 600
 601                 /*
 602                  * We don't add to the inodes nbytes if we are prealloc or a
 603                  * hole.
 604                  */
 605                 if (btrfs_file_extent_disk_bytenr(eb, item) == 0)
 606                         nbytes = 0;
 607         } else if (found_type == BTRFS_FILE_EXTENT_INLINE) {
 608                 size = btrfs_file_extent_inline_len(eb, slot, item);
 609                 nbytes = btrfs_file_extent_ram_bytes(eb, item);
 610                 extent_end = ALIGN(start + size, root->sectorsize);
 611         } else {
 612                 ret = 0;
 613                 goto out;
 614         }
 615
 616         inode = read_one_inode(root, key->objectid);
 617         if (!inode) {
 618                 ret = -EIO;
 619                 goto out;
 620         }
 621
 622         /*
 623          * first check to see if we already have this extent in the
 624          * file.  This must be done before the btrfs_drop_extents run
 625          * so we don't try to drop this extent.
 626          */
 627         ret = btrfs_lookup_file_extent(trans, root, path, btrfs_ino(inode),
 628                                        start, 0);
 629
 630         if (ret == 0 &&
 631             (found_type == BTRFS_FILE_EXTENT_REG ||
 632              found_type == BTRFS_FILE_EXTENT_PREALLOC)) {
 633                 struct btrfs_file_extent_item cmp1;
 634                 struct btrfs_file_extent_item cmp2;
 635                 struct btrfs_file_extent_item *existing;
 636                 struct extent_buffer *leaf;
 637
 638                 leaf = path->nodes[0];
 639                 existing = btrfs_item_ptr(leaf, path->slots[0],
 640                                           struct btrfs_file_extent_item);
 641
 642                 read_extent_buffer(eb, &cmp1, (unsigned long)item,
 643                                    sizeof(cmp1));
 644                 read_extent_buffer(leaf, &cmp2, (unsigned long)existing,
 645                                    sizeof(cmp2));
 646
 647                 /*
 648                  * we already have a pointer to this exact extent,
 649                  * we don't have to do anything
 650                  */
 651                 if (memcmp(&cmp1, &cmp2, sizeof(cmp1)) == 0) {
 652                         btrfs_release_path(path);
 653                         goto out;
 654                 }
 655         }
 656         btrfs_release_path(path);
 657
 658         /* drop any overlapping extents */
 659         ret = btrfs_drop_extents(trans, root, inode, start, extent_end, 1);
 660         if (ret)
 661                 goto out;
 662
 663         if (found_type == BTRFS_FILE_EXTENT_REG ||
 664             found_type == BTRFS_FILE_EXTENT_PREALLOC) {
 665                 u64 offset;
 666                 unsigned long dest_offset;
 667                 struct btrfs_key ins;
 668
 669                 ret = btrfs_insert_empty_item(trans, root, path, key,
 670                                               sizeof(*item));
 671                 if (ret)
 672                         goto out;
 673                 dest_offset = btrfs_item_ptr_offset(path->nodes[0],
 674                                                     path->slots[0]);
 675                 copy_extent_buffer(path->nodes[0], eb, dest_offset,
 676                                 (unsigned long)item,  sizeof(*item));
 677
 678                 ins.objectid = btrfs_file_extent_disk_bytenr(eb, item);
 679                 ins.offset = btrfs_file_extent_disk_num_bytes(eb, item);
 680                 ins.type = BTRFS_EXTENT_ITEM_KEY;
 681                 offset = key->offset - btrfs_file_extent_offset(eb, item);
 682
 683                 if (ins.objectid > 0) {
 684                         u64 csum_start;
 685                         u64 csum_end;
 686                         LIST_HEAD(ordered_sums);
 687                         /*
 688                          * is this extent already allocated in the extent
 689                          * allocation tree?  If so, just add a reference
 690                          */
 691                         ret = btrfs_lookup_data_extent(root, ins.objectid,
 692                                                 ins.offset);
 693                         if (ret == 0) {
 694                                 ret = btrfs_inc_extent_ref(trans, root,
 695                                                 ins.objectid, ins.offset,
 696                                                 0, root->root_key.objectid,
 697                                                 key->objectid, offset);
 698                                 if (ret)
 699                                         goto out;
 700                         } else {
 701                                 /*
 702                                  * insert the extent pointer in the extent
 703                                  * allocation tree
 704                                  */
 705                                 ret = btrfs_alloc_logged_file_extent(trans,
 706                                                 root, root->root_key.objectid,
 707                                                 key->objectid, offset, &ins);
 708                                 if (ret)
 709                                         goto out;
 710                         }
 711                         btrfs_release_path(path);
 712
 713                         if (btrfs_file_extent_compression(eb, item)) {
 714                                 csum_start = ins.objectid;
 715                                 csum_end = csum_start + ins.offset;
 716                         } else {
 717                                 csum_start = ins.objectid +
 718                                         btrfs_file_extent_offset(eb, item);
 719                                 csum_end = csum_start +
 720                                         btrfs_file_extent_num_bytes(eb, item);
 721                         }
 722
 723                         ret = btrfs_lookup_csums_range(root->log_root,
 724                                                 csum_start, csum_end - 1,
 725                                                 &ordered_sums, 0);
 726                         if (ret)
 727                                 goto out;
 728                         /*
 729                          * Now delete all existing cums in the csum root that
 730                          * cover our range. We do this because we can have an
 731                          * extent that is completely referenced by one file
 732                          * extent item and partially referenced by another
 733                          * file extent item (like after using the clone or
 734                          * extent_same ioctls). In this case if we end up doing
 735                          * the replay of the one that partially references the
 736                          * extent first, and we do not do the csum deletion
 737                          * below, we can get 2 csum items in the csum tree that
 738                          * overlap each other. For example, imagine our log has
 739                          * the two following file extent items:
 740                          *
 741                          * key (257 EXTENT_DATA 409600)
 742                          *     extent data disk byte 12845056 nr 102400
 743                          *     extent data offset 20480 nr 20480 ram 102400
 744                          *
 745                          * key (257 EXTENT_DATA 819200)
 746                          *     extent data disk byte 12845056 nr 102400
 747                          *     extent data offset 0 nr 102400 ram 102400
 748                          *
 749                          * Where the second one fully references the 100K extent
 750                          * that starts at disk byte 12845056, and the log tree
 751                          * has a single csum item that covers the entire range
 752                          * of the extent:
 753                          *
 754                          * key (EXTENT_CSUM EXTENT_CSUM 12845056) itemsize 100
 755                          *
 756                          * After the first file extent item is replayed, the
 757                          * csum tree gets the following csum item:
 758                          *
 759                          * key (EXTENT_CSUM EXTENT_CSUM 12865536) itemsize 20
 760                          *
 761                          * Which covers the 20K sub-range starting at offset 20K
 762                          * of our extent. Now when we replay the second file
 763                          * extent item, if we do not delete existing csum items
 764                          * that cover any of its blocks, we end up getting two
 765                          * csum items in our csum tree that overlap each other:
 766                          *
 767                          * key (EXTENT_CSUM EXTENT_CSUM 12845056) itemsize 100
 768                          * key (EXTENT_CSUM EXTENT_CSUM 12865536) itemsize 20
 769                          *
 770                          * Which is a problem, because after this anyone trying
 771                          * to lookup up for the checksum of any block of our
 772                          * extent starting at an offset of 40K or higher, will
 773                          * end up looking at the second csum item only, which
 774                          * does not contain the checksum for any block starting
 775                          * at offset 40K or higher of our extent.
 776                          */
 777                         while (!list_empty(&ordered_sums)) {
 778                                 struct btrfs_ordered_sum *sums;
 779                                 sums = list_entry(ordered_sums.next,
 780                                                 struct btrfs_ordered_sum,
 781                                                 list);
 782                                 if (!ret)
 783                                         ret = btrfs_del_csums(trans,
 784                                                       root->fs_info->csum_root,
 785                                                       sums->bytenr,
 786                                                       sums->len);
 787                                 if (!ret)
 788                                         ret = btrfs_csum_file_blocks(trans,
 789                                                 root->fs_info->csum_root,
 790                                                 sums);
 791                                 list_del(&sums->list);
 792                                 kfree(sums);
 793                         }
 794                         if (ret)
 795                                 goto out;
 796                 } else {
 797                         btrfs_release_path(path);
 798                 }
 799         } else if (found_type == BTRFS_FILE_EXTENT_INLINE) {
 800                 /* inline extents are easy, we just overwrite them */
 801                 ret = overwrite_item(trans, root, path, eb, slot, key);
 802                 if (ret)
 803                         goto out;
 804         }
 805
 806         inode_add_bytes(inode, nbytes);
 807         ret = btrfs_update_inode(trans, root, inode);
 808 out:
 809         if (inode)
 810                 iput(inode);
 811         return ret;
 812 }
 813
 814 /*
 815  * when cleaning up conflicts between the directory names in the
 816  * subvolume, directory names in the log and directory names in the
 817  * inode back references, we may have to unlink inodes from directories.
 818  *
 819  * This is a helper function to do the unlink of a specific directory
 820  * item
 821  */
 822 static noinline int drop_one_dir_item(struct btrfs_trans_handle *trans,
 823                                       struct btrfs_root *root,
 824                                       struct btrfs_path *path,
 825                                       struct inode *dir,
 826                                       struct btrfs_dir_item *di)
 827 {
 828         struct inode *inode;
 829         char *name;
 830         int name_len;
 831         struct extent_buffer *leaf;
 832         struct btrfs_key location;
 833         int ret;
 834
 835         leaf = path->nodes[0];
 836
 837         btrfs_dir_item_key_to_cpu(leaf, di, &location);
 838         name_len = btrfs_dir_name_len(leaf, di);
 839         name = kmalloc(name_len, GFP_NOFS);
 840         if (!name)
 841                 return -ENOMEM;
 842
 843         read_extent_buffer(leaf, name, (unsigned long)(di + 1), name_len);
 844         btrfs_release_path(path);
 845
 846         inode = read_one_inode(root, location.objectid);
 847         if (!inode) {
 848                 ret = -EIO;
 849                 goto out;
 850         }
 851
 852         ret = link_to_fixup_dir(trans, root, path, location.objectid);
 853         if (ret)
 854                 goto out;
 855
 856         ret = btrfs_unlink_inode(trans, root, dir, inode, name, name_len);
 857         if (ret)
 858                 goto out;
 859         else
 860                 ret = btrfs_run_delayed_items(trans, root);
 861 out:
 862         kfree(name);
 863         iput(inode);
 864         return ret;
 865 }
 866
 867 /*
 868  * helper function to see if a given name and sequence number found
 869  * in an inode back reference are already in a directory and correctly
 870  * point to this inode
 871  */
 872 static noinline int inode_in_dir(struct btrfs_root *root,
 873                                  struct btrfs_path *path,
 874                                  u64 dirid, u64 objectid, u64 index,
 875                                  const char *name, int name_len)
 876 {
 877         struct btrfs_dir_item *di;
 878         struct btrfs_key location;
 879         int match = 0;
 880
 881         di = btrfs_lookup_dir_index_item(NULL, root, path, dirid,
 882                                          index, name, name_len, 0);
 883         if (di && !IS_ERR(di)) {
 884                 btrfs_dir_item_key_to_cpu(path->nodes[0], di, &location);
 885                 if (location.objectid != objectid)
 886                         goto out;
 887         } else
 888                 goto out;
 889         btrfs_release_path(path);
 890
 891         di = btrfs_lookup_dir_item(NULL, root, path, dirid, name, name_len, 0);
 892         if (di && !IS_ERR(di)) {
 893                 btrfs_dir_item_key_to_cpu(path->nodes[0], di, &location);
 894                 if (location.objectid != objectid)
 895                         goto out;
 896         } else
 897                 goto out;
 898         match = 1;
 899 out:
 900         btrfs_release_path(path);
 901         return match;
 902 }
 903
 904 /*
 905  * helper function to check a log tree for a named back reference in
 906  * an inode.  This is used to decide if a back reference that is
 907  * found in the subvolume conflicts with what we find in the log.
 908  *
 909  * inode backreferences may have multiple refs in a single item,
 910  * during replay we process one reference at a time, and we don't
 911  * want to delete valid links to a file from the subvolume if that
 912  * link is also in the log.
 913  */
 914 static noinline int backref_in_log(struct btrfs_root *log,
 915                                    struct btrfs_key *key,
 916                                    u64 ref_objectid,
 917                                    const char *name, int namelen)
 918 {
 919         struct btrfs_path *path;
 920         struct btrfs_inode_ref *ref;
 921         unsigned long ptr;
 922         unsigned long ptr_end;
 923         unsigned long name_ptr;
 924         int found_name_len;
 925         int item_size;
 926         int ret;
 927         int match = 0;
 928
 929         path = btrfs_alloc_path();
 930         if (!path)
 931                 return -ENOMEM;
 932
 933         ret = btrfs_search_slot(NULL, log, key, path, 0, 0);
 934         if (ret != 0)
 935                 goto out;
 936
 937         ptr = btrfs_item_ptr_offset(path->nodes[0], path->slots[0]);
 938
 939         if (key->type == BTRFS_INODE_EXTREF_KEY) {
 940                 if (btrfs_find_name_in_ext_backref(path, ref_objectid,
 941                                                    name, namelen, NULL))
 942                         match = 1;
 943
 944                 goto out;
 945         }
 946
 947         item_size = btrfs_item_size_nr(path->nodes[0], path->slots[0]);
 948         ptr_end = ptr + item_size;
 949         while (ptr < ptr_end) {
 950                 ref = (struct btrfs_inode_ref *)ptr;
 951                 found_name_len = btrfs_inode_ref_name_len(path->nodes[0], ref);
 952                 if (found_name_len == namelen) {
 953                         name_ptr = (unsigned long)(ref + 1);
 954                         ret = memcmp_extent_buffer(path->nodes[0], name,
 955                                                    name_ptr, namelen);
 956                         if (ret == 0) {
 957                                 match = 1;
 958                                 goto out;
 959                         }
 960                 }
 961                 ptr = (unsigned long)(ref + 1) + found_name_len;
 962         }
 963 out:
 964         btrfs_free_path(path);
 965         return match;
 966 }
 967
 968 static inline int __add_inode_ref(struct btrfs_trans_handle *trans,
 969                                   struct btrfs_root *root,
 970                                   struct btrfs_path *path,
 971                                   struct btrfs_root *log_root,
 972                                   struct inode *dir, struct inode *inode,
 973                                   struct extent_buffer *eb,
 974                                   u64 inode_objectid, u64 parent_objectid,
 975                                   u64 ref_index, char *name, int namelen,
 976                                   int *search_done)
 977 {
 978         int ret;
 979         char *victim_name;
 980         int victim_name_len;
 981         struct extent_buffer *leaf;
 982         struct btrfs_dir_item *di;
 983         struct btrfs_key search_key;
 984         struct btrfs_inode_extref *extref;
 985
 986 again:
 987         /* Search old style refs */
 988         search_key.objectid = inode_objectid;
 989         search_key.type = BTRFS_INODE_REF_KEY;
 990         search_key.offset = parent_objectid;
 991         ret = btrfs_search_slot(NULL, root, &search_key, path, 0, 0);
 992         if (ret == 0) {
 993                 struct btrfs_inode_ref *victim_ref;
 994                 unsigned long ptr;
 995                 unsigned long ptr_end;
 996
 997                 leaf = path->nodes[0];
 998
 999                 /* are we trying to overwrite a back ref for the root directory
1000                  * if so, just jump out, we're done
1001                  */
1002                 if (search_key.objectid == search_key.offset)
1003                         return 1;
1004
1005                 /* check all the names in this back reference to see
1006                  * if they are in the log.  if so, we allow them to stay
1007                  * otherwise they must be unlinked as a conflict
1008                  */
1009                 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
1010                 ptr_end = ptr + btrfs_item_size_nr(leaf, path->slots[0]);
1011                 while (ptr < ptr_end) {
1012                         victim_ref = (struct btrfs_inode_ref *)ptr;
1013                         victim_name_len = btrfs_inode_ref_name_len(leaf,
1014                                                                    victim_ref);
1015                         victim_name = kmalloc(victim_name_len, GFP_NOFS);
1016                         if (!victim_name)
1017                                 return -ENOMEM;
1018
1019                         read_extent_buffer(leaf, victim_name,
1020                                            (unsigned long)(victim_ref + 1),
1021                                            victim_name_len);
1022
1023                         if (!backref_in_log(log_root, &search_key,
1024                                             parent_objectid,
1025                                             victim_name,
1026                                             victim_name_len)) {
1027                                 inc_nlink(inode);
1028                                 btrfs_release_path(path);
1029
1030                                 ret = btrfs_unlink_inode(trans, root, dir,
1031                                                          inode, victim_name,
1032                                                          victim_name_len);
1033                                 kfree(victim_name);
1034                                 if (ret)
1035                                         return ret;
1036                                 ret = btrfs_run_delayed_items(trans, root);
1037                                 if (ret)
1038                                         return ret;
1039                                 *search_done = 1;
1040                                 goto again;
1041                         }
1042                         kfree(victim_name);
1043
1044                         ptr = (unsigned long)(victim_ref + 1) + victim_name_len;
1045                 }
1046
1047                 /*
1048                  * NOTE: we have searched root tree and checked the
1049                  * coresponding ref, it does not need to check again.
1050                  */
1051                 *search_done = 1;
1052         }
1053         btrfs_release_path(path);
1054
1055         /* Same search but for extended refs */
1056         extref = btrfs_lookup_inode_extref(NULL, root, path, name, namelen,
1057                                            inode_objectid, parent_objectid, 0,
1058                                            0);
1059         if (!IS_ERR_OR_NULL(extref)) {
1060                 u32 item_size;
1061                 u32 cur_offset = 0;
1062                 unsigned long base;
1063                 struct inode *victim_parent;
1064
1065                 leaf = path->nodes[0];
1066
1067                 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1068                 base = btrfs_item_ptr_offset(leaf, path->slots[0]);
1069
1070                 while (cur_offset < item_size) {
1071                         extref = (struct btrfs_inode_extref *)(base + cur_offset);
1072
1073                         victim_name_len = btrfs_inode_extref_name_len(leaf, extref);
1074
1075                         if (btrfs_inode_extref_parent(leaf, extref) != parent_objectid)
1076                                 goto next;
1077
1078                         victim_name = kmalloc(victim_name_len, GFP_NOFS);
1079                         if (!victim_name)
1080                                 return -ENOMEM;
1081                         read_extent_buffer(leaf, victim_name, (unsigned long)&extref->name,
1082                                            victim_name_len);
1083
1084                         search_key.objectid = inode_objectid;
1085                         search_key.type = BTRFS_INODE_EXTREF_KEY;
1086                         search_key.offset = btrfs_extref_hash(parent_objectid,
1087                                                               victim_name,
1088                                                               victim_name_len);
1089                         ret = 0;
1090                         if (!backref_in_log(log_root, &search_key,
1091                                             parent_objectid, victim_name,
1092                                             victim_name_len)) {
1093                                 ret = -ENOENT;
1094                                 victim_parent = read_one_inode(root,
1095                                                                parent_objectid);
1096                                 if (victim_parent) {
1097                                         inc_nlink(inode);
1098                                         btrfs_release_path(path);
1099
1100                                         ret = btrfs_unlink_inode(trans, root,
1101                                                                  victim_parent,
1102                                                                  inode,
1103                                                                  victim_name,
1104                                                                  victim_name_len);
1105                                         if (!ret)
1106                                                 ret = btrfs_run_delayed_items(
1107                                                                   trans, root);
1108                                 }
1109                                 iput(victim_parent);
1110                                 kfree(victim_name);
1111                                 if (ret)
1112                                         return ret;
1113                                 *search_done = 1;
1114                                 goto again;
1115                         }
1116                         kfree(victim_name);
1117                         if (ret)
1118                                 return ret;
1119 next:
1120                         cur_offset += victim_name_len + sizeof(*extref);
1121                 }
1122                 *search_done = 1;
1123         }
1124         btrfs_release_path(path);
1125
1126         /* look for a conflicting sequence number */
1127         di = btrfs_lookup_dir_index_item(trans, root, path, btrfs_ino(dir),
1128                                          ref_index, name, namelen, 0);
1129         if (di && !IS_ERR(di)) {
1130                 ret = drop_one_dir_item(trans, root, path, dir, di);
1131                 if (ret)
1132                         return ret;
1133         }
1134         btrfs_release_path(path);
1135
1136         /* look for a conflicing name */
1137         di = btrfs_lookup_dir_item(trans, root, path, btrfs_ino(dir),
1138                                    name, namelen, 0);
1139         if (di && !IS_ERR(di)) {
1140                 ret = drop_one_dir_item(trans, root, path, dir, di);
1141                 if (ret)
1142                         return ret;
1143         }
1144         btrfs_release_path(path);
1145
1146         return 0;
1147 }
1148
1149 static int extref_get_fields(struct extent_buffer *eb, unsigned long ref_ptr,
1150                              u32 *namelen, char **name, u64 *index,
1151                              u64 *parent_objectid)
1152 {
1153         struct btrfs_inode_extref *extref;
1154
1155         extref = (struct btrfs_inode_extref *)ref_ptr;
1156
1157         *namelen = btrfs_inode_extref_name_len(eb, extref);
1158         *name = kmalloc(*namelen, GFP_NOFS);
1159         if (*name == NULL)
1160                 return -ENOMEM;
1161
1162         read_extent_buffer(eb, *name, (unsigned long)&extref->name,
1163                            *namelen);
1164
1165         *index = btrfs_inode_extref_index(eb, extref);
1166         if (parent_objectid)
1167                 *parent_objectid = btrfs_inode_extref_parent(eb, extref);
1168
1169         return 0;
1170 }
1171
1172 static int ref_get_fields(struct extent_buffer *eb, unsigned long ref_ptr,
1173                           u32 *namelen, char **name, u64 *index)
1174 {
1175         struct btrfs_inode_ref *ref;
1176
1177         ref = (struct btrfs_inode_ref *)ref_ptr;
1178
1179         *namelen = btrfs_inode_ref_name_len(eb, ref);
1180         *name = kmalloc(*namelen, GFP_NOFS);
1181         if (*name == NULL)
1182                 return -ENOMEM;
1183
1184         read_extent_buffer(eb, *name, (unsigned long)(ref + 1), *namelen);
1185
1186         *index = btrfs_inode_ref_index(eb, ref);
1187
1188         return 0;
1189 }
1190
1191 /*
1192  * replay one inode back reference item found in the log tree.
1193  * eb, slot and key refer to the buffer and key found in the log tree.
1194  * root is the destination we are replaying into, and path is for temp
1195  * use by this function.  (it should be released on return).
1196  */
1197 static noinline int add_inode_ref(struct btrfs_trans_handle *trans,
1198                                   struct btrfs_root *root,
1199                                   struct btrfs_root *log,
1200                                   struct btrfs_path *path,
1201                                   struct extent_buffer *eb, int slot,
1202                                   struct btrfs_key *key)
1203 {
1204         struct inode *dir = NULL;
1205         struct inode *inode = NULL;
1206         unsigned long ref_ptr;
1207         unsigned long ref_end;
1208         char *name = NULL;
1209         int namelen;
1210         int ret;
1211         int search_done = 0;
1212         int log_ref_ver = 0;
1213         u64 parent_objectid;
1214         u64 inode_objectid;
1215         u64 ref_index = 0;
1216         int ref_struct_size;
1217
1218         ref_ptr = btrfs_item_ptr_offset(eb, slot);
1219         ref_end = ref_ptr + btrfs_item_size_nr(eb, slot);
1220
1221         if (key->type == BTRFS_INODE_EXTREF_KEY) {
1222                 struct btrfs_inode_extref *r;
1223
1224                 ref_struct_size = sizeof(struct btrfs_inode_extref);
1225                 log_ref_ver = 1;
1226                 r = (struct btrfs_inode_extref *)ref_ptr;
1227                 parent_objectid = btrfs_inode_extref_parent(eb, r);
1228         } else {
1229                 ref_struct_size = sizeof(struct btrfs_inode_ref);
1230                 parent_objectid = key->offset;
1231         }
1232         inode_objectid = key->objectid;
1233
1234         /*
1235          * it is possible that we didn't log all the parent directories
1236          * for a given inode.  If we don't find the dir, just don't
1237          * copy the back ref in.  The link count fixup code will take
1238          * care of the rest
1239          */
1240         dir = read_one_inode(root, parent_objectid);
1241         if (!dir) {
1242                 ret = -ENOENT;
1243                 goto out;
1244         }
1245
1246         inode = read_one_inode(root, inode_objectid);
1247         if (!inode) {
1248                 ret = -EIO;
1249                 goto out;
1250         }
1251
1252         while (ref_ptr < ref_end) {
1253                 if (log_ref_ver) {
1254                         ret = extref_get_fields(eb, ref_ptr, &namelen, &name,
1255                                                 &ref_index, &parent_objectid);
1256                         /*
1257                          * parent object can change from one array
1258                          * item to another.
1259                          */
1260                         if (!dir)
1261                                 dir = read_one_inode(root, parent_objectid);
1262                         if (!dir) {
1263                                 ret = -ENOENT;
1264                                 goto out;
1265                         }
1266                 } else {
1267                         ret = ref_get_fields(eb, ref_ptr, &namelen, &name,
1268                                              &ref_index);
1269                 }
1270                 if (ret)
1271                         goto out;
1272
1273                 /* if we already have a perfect match, we're done */
1274                 if (!inode_in_dir(root, path, btrfs_ino(dir), btrfs_ino(inode),
1275                                   ref_index, name, namelen)) {
1276                         /*
1277                          * look for a conflicting back reference in the
1278                          * metadata. if we find one we have to unlink that name
1279                          * of the file before we add our new link.  Later on, we
1280                          * overwrite any existing back reference, and we don't
1281                          * want to create dangling pointers in the directory.
1282                          */
1283
1284                         if (!search_done) {
1285                                 ret = __add_inode_ref(trans, root, path, log,
1286                                                       dir, inode, eb,
1287                                                       inode_objectid,
1288                                                       parent_objectid,
1289                                                       ref_index, name, namelen,
1290                                                       &search_done);
1291                                 if (ret) {
1292                                         if (ret == 1)
1293                                                 ret = 0;
1294                                         goto out;
1295                                 }
1296                         }
1297
1298                         /* insert our name */
1299                         ret = btrfs_add_link(trans, dir, inode, name, namelen,
1300                                              0, ref_index);
1301                         if (ret)
1302                                 goto out;
1303
1304                         btrfs_update_inode(trans, root, inode);
1305                 }
1306
1307                 ref_ptr = (unsigned long)(ref_ptr + ref_struct_size) + namelen;
1308                 kfree(name);
1309                 name = NULL;
1310                 if (log_ref_ver) {
1311                         iput(dir);
1312                         dir = NULL;
1313                 }
1314         }
1315
1316         /* finally write the back reference in the inode */
1317         ret = overwrite_item(trans, root, path, eb, slot, key);
1318 out:
1319         btrfs_release_path(path);
1320         kfree(name);
1321         iput(dir);
1322         iput(inode);
1323         return ret;
1324 }
1325
1326 static int insert_orphan_item(struct btrfs_trans_handle *trans,
1327                               struct btrfs_root *root, u64 ino)
1328 {
1329         int ret;
1330
1331         ret = btrfs_insert_orphan_item(trans, root, ino);
1332         if (ret == -EEXIST)
1333                 ret = 0;
1334
1335         return ret;
1336 }
1337
1338 static int count_inode_extrefs(struct btrfs_root *root,
1339                                struct inode *inode, struct btrfs_path *path)
1340 {
1341         int ret = 0;
1342         int name_len;
1343         unsigned int nlink = 0;
1344         u32 item_size;
1345         u32 cur_offset = 0;
1346         u64 inode_objectid = btrfs_ino(inode);
1347         u64 offset = 0;
1348         unsigned long ptr;
1349         struct btrfs_inode_extref *extref;
1350         struct extent_buffer *leaf;
1351
1352         while (1) {
1353                 ret = btrfs_find_one_extref(root, inode_objectid, offset, path,
1354                                             &extref, &offset);
1355                 if (ret)
1356                         break;
1357
1358                 leaf = path->nodes[0];
1359                 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1360                 ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
1361                 cur_offset = 0;
1362
1363                 while (cur_offset < item_size) {
1364                         extref = (struct btrfs_inode_extref *) (ptr + cur_offset);
1365                         name_len = btrfs_inode_extref_name_len(leaf, extref);
1366
1367                         nlink++;
1368
1369                         cur_offset += name_len + sizeof(*extref);
1370                 }
1371
1372                 offset++;
1373                 btrfs_release_path(path);
1374         }
1375         btrfs_release_path(path);
1376
1377         if (ret < 0 && ret != -ENOENT)
1378                 return ret;
1379         return nlink;
1380 }
1381
1382 static int count_inode_refs(struct btrfs_root *root,
1383                                struct inode *inode, struct btrfs_path *path)
1384 {
1385         int ret;
1386         struct btrfs_key key;
1387         unsigned int nlink = 0;
1388         unsigned long ptr;
1389         unsigned long ptr_end;
1390         int name_len;
1391         u64 ino = btrfs_ino(inode);
1392
1393         key.objectid = ino;
1394         key.type = BTRFS_INODE_REF_KEY;
1395         key.offset = (u64)-1;
1396
1397         while (1) {
1398                 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
1399                 if (ret < 0)
1400                         break;
1401                 if (ret > 0) {
1402                         if (path->slots[0] == 0)
1403                                 break;
1404                         path->slots[0]--;
1405                 }
1406 process_slot:
1407                 btrfs_item_key_to_cpu(path->nodes[0], &key,
1408                                       path->slots[0]);
1409                 if (key.objectid != ino ||
1410                     key.type != BTRFS_INODE_REF_KEY)
1411                         break;
1412                 ptr = btrfs_item_ptr_offset(path->nodes[0], path->slots[0]);
1413                 ptr_end = ptr + btrfs_item_size_nr(path->nodes[0],
1414                                                    path->slots[0]);
1415                 while (ptr < ptr_end) {
1416                         struct btrfs_inode_ref *ref;
1417
1418                         ref = (struct btrfs_inode_ref *)ptr;
1419                         name_len = btrfs_inode_ref_name_len(path->nodes[0],
1420                                                             ref);
1421                         ptr = (unsigned long)(ref + 1) + name_len;
1422                         nlink++;
1423                 }
1424
1425                 if (key.offset == 0)
1426                         break;
1427                 if (path->slots[0] > 0) {
1428                         path->slots[0]--;
1429                         goto process_slot;
1430                 }
1431                 key.offset--;
1432                 btrfs_release_path(path);
1433         }
1434         btrfs_release_path(path);
1435
1436         return nlink;
1437 }
1438
1439 /*
1440  * There are a few corners where the link count of the file can't
1441  * be properly maintained during replay.  So, instead of adding
1442  * lots of complexity to the log code, we just scan the backrefs
1443  * for any file that has been through replay.
1444  *
1445  * The scan will update the link count on the inode to reflect the
1446  * number of back refs found.  If it goes down to zero, the iput
1447  * will free the inode.
1448  */
1449 static noinline int fixup_inode_link_count(struct btrfs_trans_handle *trans,
1450                                            struct btrfs_root *root,
1451                                            struct inode *inode)
1452 {
1453         struct btrfs_path *path;
1454         int ret;
1455         u64 nlink = 0;
1456         u64 ino = btrfs_ino(inode);
1457
1458         path = btrfs_alloc_path();
1459         if (!path)
1460                 return -ENOMEM;
1461
1462         ret = count_inode_refs(root, inode, path);
1463         if (ret < 0)
1464                 goto out;
1465
1466         nlink = ret;
1467
1468         ret = count_inode_extrefs(root, inode, path);
1469         if (ret < 0)
1470                 goto out;
1471
1472         nlink += ret;
1473
1474         ret = 0;
1475
1476         if (nlink != inode->i_nlink) {
1477                 set_nlink(inode, nlink);
1478                 btrfs_update_inode(trans, root, inode);
1479         }
1480         BTRFS_I(inode)->index_cnt = (u64)-1;
1481
1482         if (inode->i_nlink == 0) {
1483                 if (S_ISDIR(inode->i_mode)) {
1484                         ret = replay_dir_deletes(trans, root, NULL, path,
1485                                                  ino, 1);
1486                         if (ret)
1487                                 goto out;
1488                 }
1489                 ret = insert_orphan_item(trans, root, ino);
1490         }
1491
1492 out:
1493         btrfs_free_path(path);
1494         return ret;
1495 }
1496
1497 static noinline int fixup_inode_link_counts(struct btrfs_trans_handle *trans,
1498                                             struct btrfs_root *root,
1499                                             struct btrfs_path *path)
1500 {
1501         int ret;
1502         struct btrfs_key key;
1503         struct inode *inode;
1504
1505         key.objectid = BTRFS_TREE_LOG_FIXUP_OBJECTID;
1506         key.type = BTRFS_ORPHAN_ITEM_KEY;
1507         key.offset = (u64)-1;
1508         while (1) {
1509                 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
1510                 if (ret < 0)
1511                         break;
1512
1513                 if (ret == 1) {
1514                         if (path->slots[0] == 0)
1515                                 break;
1516                         path->slots[0]--;
1517                 }
1518
1519                 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1520                 if (key.objectid != BTRFS_TREE_LOG_FIXUP_OBJECTID ||
1521                     key.type != BTRFS_ORPHAN_ITEM_KEY)
1522                         break;
1523
1524                 ret = btrfs_del_item(trans, root, path);
1525                 if (ret)
1526                         goto out;
1527
1528                 btrfs_release_path(path);
1529                 inode = read_one_inode(root, key.offset);
1530                 if (!inode)
1531                         return -EIO;
1532
1533                 ret = fixup_inode_link_count(trans, root, inode);
1534                 iput(inode);
1535                 if (ret)
1536                         goto out;
1537
1538                 /*
1539                  * fixup on a directory may create new entries,
1540                  * make sure we always look for the highset possible
1541                  * offset
1542                  */
1543                 key.offset = (u64)-1;
1544         }
1545         ret = 0;
1546 out:
1547         btrfs_release_path(path);
1548         return ret;
1549 }
1550
1551
1552 /*
1553  * record a given inode in the fixup dir so we can check its link
1554  * count when replay is done.  The link count is incremented here
1555  * so the inode won't go away until we check it
1556  */
1557 static noinline int link_to_fixup_dir(struct btrfs_trans_handle *trans,
1558                                       struct btrfs_root *root,
1559                                       struct btrfs_path *path,
1560                                       u64 objectid)
1561 {
1562         struct btrfs_key key;
1563         int ret = 0;
1564         struct inode *inode;
1565
1566         inode = read_one_inode(root, objectid);
1567         if (!inode)
1568                 return -EIO;
1569
1570         key.objectid = BTRFS_TREE_LOG_FIXUP_OBJECTID;
1571         key.type = BTRFS_ORPHAN_ITEM_KEY;
1572         key.offset = objectid;
1573
1574         ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
1575
1576         btrfs_release_path(path);
1577         if (ret == 0) {
1578                 if (!inode->i_nlink)
1579                         set_nlink(inode, 1);
1580                 else
1581                         inc_nlink(inode);
1582                 ret = btrfs_update_inode(trans, root, inode);
1583         } else if (ret == -EEXIST) {
1584                 ret = 0;
1585         } else {
1586                 BUG(); /* Logic Error */
1587         }
1588         iput(inode);
1589
1590         return ret;
1591 }
1592
1593 /*
1594  * when replaying the log for a directory, we only insert names
1595  * for inodes that actually exist.  This means an fsync on a directory
1596  * does not implicitly fsync all the new files in it
1597  */
1598 static noinline int insert_one_name(struct btrfs_trans_handle *trans,
1599                                     struct btrfs_root *root,
1600                                     u64 dirid, u64 index,
1601                                     char *name, int name_len,
1602                                     struct btrfs_key *location)
1603 {
1604         struct inode *inode;
1605         struct inode *dir;
1606         int ret;
1607
1608         inode = read_one_inode(root, location->objectid);
1609         if (!inode)
1610                 return -ENOENT;
1611
1612         dir = read_one_inode(root, dirid);
1613         if (!dir) {
1614                 iput(inode);
1615                 return -EIO;
1616         }
1617
1618         ret = btrfs_add_link(trans, dir, inode, name, name_len, 1, index);
1619
1620         /* FIXME, put inode into FIXUP list */
1621
1622         iput(inode);
1623         iput(dir);
1624         return ret;
1625 }
1626
1627 /*
1628  * Return true if an inode reference exists in the log for the given name,
1629  * inode and parent inode.
1630  */
1631 static bool name_in_log_ref(struct btrfs_root *log_root,
1632                             const char *name, const int name_len,
1633                             const u64 dirid, const u64 ino)
1634 {
1635         struct btrfs_key search_key;
1636
1637         search_key.objectid = ino;
1638         search_key.type = BTRFS_INODE_REF_KEY;
1639         search_key.offset = dirid;
1640         if (backref_in_log(log_root, &search_key, dirid, name, name_len))
1641                 return true;
1642
1643         search_key.type = BTRFS_INODE_EXTREF_KEY;
1644         search_key.offset = btrfs_extref_hash(dirid, name, name_len);
1645         if (backref_in_log(log_root, &search_key, dirid, name, name_len))
1646                 return true;
1647
1648         return false;
1649 }
1650
1651 /*
1652  * take a single entry in a log directory item and replay it into
1653  * the subvolume.
1654  *
1655  * if a conflicting item exists in the subdirectory already,
1656  * the inode it points to is unlinked and put into the link count
1657  * fix up tree.
1658  *
1659  * If a name from the log points to a file or directory that does
1660  * not exist in the FS, it is skipped.  fsyncs on directories
1661  * do not force down inodes inside that directory, just changes to the
1662  * names or unlinks in a directory.
1663  *
1664  * Returns < 0 on error, 0 if the name wasn't replayed (dentry points to a
1665  * non-existing inode) and 1 if the name was replayed.
1666  */
1667 static noinline int replay_one_name(struct btrfs_trans_handle *trans,
1668                                     struct btrfs_root *root,
1669                                     struct btrfs_path *path,
1670                                     struct extent_buffer *eb,
1671                                     struct btrfs_dir_item *di,
1672                                     struct btrfs_key *key)
1673 {
1674         char *name;
1675         int name_len;
1676         struct btrfs_dir_item *dst_di;
1677         struct btrfs_key found_key;
1678         struct btrfs_key log_key;
1679         struct inode *dir;
1680         u8 log_type;
1681         int exists;
1682         int ret = 0;
1683         bool update_size = (key->type == BTRFS_DIR_INDEX_KEY);
1684         bool name_added = false;
1685
1686         dir = read_one_inode(root, key->objectid);
1687         if (!dir)
1688                 return -EIO;
1689
1690         name_len = btrfs_dir_name_len(eb, di);
1691         name = kmalloc(name_len, GFP_NOFS);
1692         if (!name) {
1693                 ret = -ENOMEM;
1694                 goto out;
1695         }
1696
1697         log_type = btrfs_dir_type(eb, di);
1698         read_extent_buffer(eb, name, (unsigned long)(di + 1),
1699                    name_len);
1700
1701         btrfs_dir_item_key_to_cpu(eb, di, &log_key);
1702         exists = btrfs_lookup_inode(trans, root, path, &log_key, 0);
1703         if (exists == 0)
1704                 exists = 1;
1705         else
1706                 exists = 0;
1707         btrfs_release_path(path);
1708
1709         if (key->type == BTRFS_DIR_ITEM_KEY) {
1710                 dst_di = btrfs_lookup_dir_item(trans, root, path, key->objectid,
1711                                        name, name_len, 1);
1712         } else if (key->type == BTRFS_DIR_INDEX_KEY) {
1713                 dst_di = btrfs_lookup_dir_index_item(trans, root, path,
1714                                                      key->objectid,
1715                                                      key->offset, name,
1716                                                      name_len, 1);
1717         } else {
1718                 /* Corruption */
1719                 ret = -EINVAL;
1720                 goto out;
1721         }
1722         if (IS_ERR_OR_NULL(dst_di)) {
1723                 /* we need a sequence number to insert, so we only
1724                  * do inserts for the BTRFS_DIR_INDEX_KEY types
1725                  */
1726                 if (key->type != BTRFS_DIR_INDEX_KEY)
1727                         goto out;
1728                 goto insert;
1729         }
1730
1731         btrfs_dir_item_key_to_cpu(path->nodes[0], dst_di, &found_key);
1732         /* the existing item matches the logged item */
1733         if (found_key.objectid == log_key.objectid &&
1734             found_key.type == log_key.type &&
1735             found_key.offset == log_key.offset &&
1736             btrfs_dir_type(path->nodes[0], dst_di) == log_type) {
1737                 update_size = false;
1738                 goto out;
1739         }
1740
1741         /*
1742          * don't drop the conflicting directory entry if the inode
1743          * for the new entry doesn't exist
1744          */
1745         if (!exists)
1746                 goto out;
1747
1748         ret = drop_one_dir_item(trans, root, path, dir, dst_di);
1749         if (ret)
1750                 goto out;
1751
1752         if (key->type == BTRFS_DIR_INDEX_KEY)
1753                 goto insert;
1754 out:
1755         btrfs_release_path(path);
1756         if (!ret && update_size) {
1757                 btrfs_i_size_write(dir, dir->i_size + name_len * 2);
1758                 ret = btrfs_update_inode(trans, root, dir);
1759         }
1760         kfree(name);
1761         iput(dir);
1762         if (!ret && name_added)
1763                 ret = 1;
1764         return ret;
1765
1766 insert:
1767         if (name_in_log_ref(root->log_root, name, name_len,
1768                             key->objectid, log_key.objectid)) {
1769                 /* The dentry will be added later. */
1770                 ret = 0;
1771                 update_size = false;
1772                 goto out;
1773         }
1774         btrfs_release_path(path);
1775         ret = insert_one_name(trans, root, key->objectid, key->offset,
1776                               name, name_len, &log_key);
1777         if (ret && ret != -ENOENT && ret != -EEXIST)
1778                 goto out;
1779         if (!ret)
1780                 name_added = true;
1781         update_size = false;
1782         ret = 0;
1783         goto out;
1784 }
1785
1786 /*
1787  * find all the names in a directory item and reconcile them into
1788  * the subvolume.  Only BTRFS_DIR_ITEM_KEY types will have more than
1789  * one name in a directory item, but the same code gets used for
1790  * both directory index types
1791  */
1792 static noinline int replay_one_dir_item(struct btrfs_trans_handle *trans,
1793                                         struct btrfs_root *root,
1794                                         struct btrfs_path *path,
1795                                         struct extent_buffer *eb, int slot,
1796                                         struct btrfs_key *key)
1797 {
1798         int ret = 0;
1799         u32 item_size = btrfs_item_size_nr(eb, slot);
1800         struct btrfs_dir_item *di;
1801         int name_len;
1802         unsigned long ptr;
1803         unsigned long ptr_end;
1804         struct btrfs_path *fixup_path = NULL;
1805
1806         ptr = btrfs_item_ptr_offset(eb, slot);
1807         ptr_end = ptr + item_size;
1808         while (ptr < ptr_end) {
1809                 di = (struct btrfs_dir_item *)ptr;
1810                 if (verify_dir_item(root, eb, di))
1811                         return -EIO;
1812                 name_len = btrfs_dir_name_len(eb, di);
1813                 ret = replay_one_name(trans, root, path, eb, di, key);
1814                 if (ret < 0)
1815                         break;
1816                 ptr = (unsigned long)(di + 1);
1817                 ptr += name_len;
1818
1819                 /*
1820                  * If this entry refers to a non-directory (directories can not
1821                  * have a link count > 1) and it was added in the transaction
1822                  * that was not committed, make sure we fixup the link count of
1823                  * the inode it the entry points to. Otherwise something like
1824                  * the following would result in a directory pointing to an
1825                  * inode with a wrong link that does not account for this dir
1826                  * entry:
1827                  *
1828                  * mkdir testdir
1829                  * touch testdir/foo
1830                  * touch testdir/bar
1831                  * sync
1832                  *
1833                  * ln testdir/bar testdir/bar_link
1834                  * ln testdir/foo testdir/foo_link
1835                  * xfs_io -c "fsync" testdir/bar
1836                  *
1837                  * <power failure>
1838                  *
1839                  * mount fs, log replay happens
1840                  *
1841                  * File foo would remain with a link count of 1 when it has two
1842                  * entries pointing to it in the directory testdir. This would
1843                  * make it impossible to ever delete the parent directory has
1844                  * it would result in stale dentries that can never be deleted.
1845                  */
1846                 if (ret == 1 && btrfs_dir_type(eb, di) != BTRFS_FT_DIR) {
1847                         struct btrfs_key di_key;
1848
1849                         if (!fixup_path) {
1850                                 fixup_path = btrfs_alloc_path();
1851                                 if (!fixup_path) {
1852                                         ret = -ENOMEM;
1853                                         break;
1854                                 }
1855                         }
1856
1857                         btrfs_dir_item_key_to_cpu(eb, di, &di_key);
1858                         ret = link_to_fixup_dir(trans, root, fixup_path,
1859                                                 di_key.objectid);
1860                         if (ret)
1861                                 break;
1862                 }
1863                 ret = 0;
1864         }
1865         btrfs_free_path(fixup_path);
1866         return ret;
1867 }
1868
1869 /*
1870  * directory replay has two parts.  There are the standard directory
1871  * items in the log copied from the subvolume, and range items
1872  * created in the log while the subvolume was logged.
1873  *
1874  * The range items tell us which parts of the key space the log
1875  * is authoritative for.  During replay, if a key in the subvolume
1876  * directory is in a logged range item, but not actually in the log
1877  * that means it was deleted from the directory before the fsync
1878  * and should be removed.
1879  */
1880 static noinline int find_dir_range(struct btrfs_root *root,
1881                                    struct btrfs_path *path,
1882                                    u64 dirid, int key_type,
1883                                    u64 *start_ret, u64 *end_ret)
1884 {
1885         struct btrfs_key key;
1886         u64 found_end;
1887         struct btrfs_dir_log_item *item;
1888         int ret;
1889         int nritems;
1890
1891         if (*start_ret == (u64)-1)
1892                 return 1;
1893
1894         key.objectid = dirid;
1895         key.type = key_type;
1896         key.offset = *start_ret;
1897
1898         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
1899         if (ret < 0)
1900                 goto out;
1901         if (ret > 0) {
1902                 if (path->slots[0] == 0)
1903                         goto out;
1904                 path->slots[0]--;
1905         }
1906         if (ret != 0)
1907                 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1908
1909         if (key.type != key_type || key.objectid != dirid) {
1910                 ret = 1;
1911                 goto next;
1912         }
1913         item = btrfs_item_ptr(path->nodes[0], path->slots[0],
1914                               struct btrfs_dir_log_item);
1915         found_end = btrfs_dir_log_end(path->nodes[0], item);
1916
1917         if (*start_ret >= key.offset && *start_ret <= found_end) {
1918                 ret = 0;
1919                 *start_ret = key.offset;
1920                 *end_ret = found_end;
1921                 goto out;
1922         }
1923         ret = 1;
1924 next:
1925         /* check the next slot in the tree to see if it is a valid item */
1926         nritems = btrfs_header_nritems(path->nodes[0]);
1927         path->slots[0]++;
1928         if (path->slots[0] >= nritems) {
1929                 ret = btrfs_next_leaf(root, path);
1930                 if (ret)
1931                         goto out;
1932         }
1933
1934         btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1935
1936         if (key.type != key_type || key.objectid != dirid) {
1937                 ret = 1;
1938                 goto out;
1939         }
1940         item = btrfs_item_ptr(path->nodes[0], path->slots[0],
1941                               struct btrfs_dir_log_item);
1942         found_end = btrfs_dir_log_end(path->nodes[0], item);
1943         *start_ret = key.offset;
1944         *end_ret = found_end;
1945         ret = 0;
1946 out:
1947         btrfs_release_path(path);
1948         return ret;
1949 }
1950
1951 /*
1952  * this looks for a given directory item in the log.  If the directory
1953  * item is not in the log, the item is removed and the inode it points
1954  * to is unlinked
1955  */
1956 static noinline int check_item_in_log(struct btrfs_trans_handle *trans,
1957                                       struct btrfs_root *root,
1958                                       struct btrfs_root *log,
1959                                       struct btrfs_path *path,
1960                                       struct btrfs_path *log_path,
1961                                       struct inode *dir,
1962                                       struct btrfs_key *dir_key)
1963 {
1964         int ret;
1965         struct extent_buffer *eb;
1966         int slot;
1967         u32 item_size;
1968         struct btrfs_dir_item *di;
1969         struct btrfs_dir_item *log_di;
1970         int name_len;
1971         unsigned long ptr;
1972         unsigned long ptr_end;
1973         char *name;
1974         struct inode *inode;
1975         struct btrfs_key location;
1976
1977 again:
1978         eb = path->nodes[0];
1979         slot = path->slots[0];
1980         item_size = btrfs_item_size_nr(eb, slot);
1981         ptr = btrfs_item_ptr_offset(eb, slot);
1982         ptr_end = ptr + item_size;
1983         while (ptr < ptr_end) {
1984                 di = (struct btrfs_dir_item *)ptr;
1985                 if (verify_dir_item(root, eb, di)) {
1986                         ret = -EIO;
1987                         goto out;
1988                 }
1989
1990                 name_len = btrfs_dir_name_len(eb, di);
1991                 name = kmalloc(name_len, GFP_NOFS);
1992                 if (!name) {
1993                         ret = -ENOMEM;
1994                         goto out;
1995                 }
1996                 read_extent_buffer(eb, name, (unsigned long)(di + 1),
1997                                   name_len);
1998                 log_di = NULL;
1999                 if (log && dir_key->type == BTRFS_DIR_ITEM_KEY) {
2000                         log_di = btrfs_lookup_dir_item(trans, log, log_path,
2001                                                        dir_key->objectid,
2002                                                        name, name_len, 0);
2003                 } else if (log && dir_key->type == BTRFS_DIR_INDEX_KEY) {
2004                         log_di = btrfs_lookup_dir_index_item(trans, log,
2005                                                      log_path,
2006                                                      dir_key->objectid,
2007                                                      dir_key->offset,
2008                                                      name, name_len, 0);
2009                 }
2010                 if (!log_di || (IS_ERR(log_di) && PTR_ERR(log_di) == -ENOENT)) {
2011                         btrfs_dir_item_key_to_cpu(eb, di, &location);
2012                         btrfs_release_path(path);
2013                         btrfs_release_path(log_path);
2014                         inode = read_one_inode(root, location.objectid);
2015                         if (!inode) {
2016                                 kfree(name);
2017                                 return -EIO;
2018                         }
2019
2020                         ret = link_to_fixup_dir(trans, root,
2021                                                 path, location.objectid);
2022                         if (ret) {
2023                                 kfree(name);
2024                                 iput(inode);
2025                                 goto out;
2026                         }
2027
2028                         inc_nlink(inode);
2029                         ret = btrfs_unlink_inode(trans, root, dir, inode,
2030                                                  name, name_len);
2031                         if (!ret)
2032                                 ret = btrfs_run_delayed_items(trans, root);
2033                         kfree(name);
2034                         iput(inode);
2035                         if (ret)
2036                                 goto out;
2037
2038                         /* there might still be more names under this key
2039                          * check and repeat if required
2040                          */
2041                         ret = btrfs_search_slot(NULL, root, dir_key, path,
2042                                                 0, 0);
2043                         if (ret == 0)
2044                                 goto again;
2045                         ret = 0;
2046                         goto out;
2047                 } else if (IS_ERR(log_di)) {
2048                         kfree(name);
2049                         return PTR_ERR(log_di);
2050                 }
2051                 btrfs_release_path(log_path);
2052                 kfree(name);
2053
2054                 ptr = (unsigned long)(di + 1);
2055                 ptr += name_len;
2056         }
2057         ret = 0;
2058 out:
2059         btrfs_release_path(path);
2060         btrfs_release_path(log_path);
2061         return ret;
2062 }
2063
2064 static int replay_xattr_deletes(struct btrfs_trans_handle *trans,
2065                               struct btrfs_root *root,
2066                               struct btrfs_root *log,
2067                               struct btrfs_path *path,
2068                               const u64 ino)
2069 {
2070         struct btrfs_key search_key;
2071         struct btrfs_path *log_path;
2072         int i;
2073         int nritems;
2074         int ret;
2075
2076         log_path = btrfs_alloc_path();
2077         if (!log_path)
2078                 return -ENOMEM;
2079
2080         search_key.objectid = ino;
2081         search_key.type = BTRFS_XATTR_ITEM_KEY;
2082         search_key.offset = 0;
2083 again:
2084         ret = btrfs_search_slot(NULL, root, &search_key, path, 0, 0);
2085         if (ret < 0)
2086                 goto out;
2087 process_leaf:
2088         nritems = btrfs_header_nritems(path->nodes[0]);
2089         for (i = path->slots[0]; i < nritems; i++) {
2090                 struct btrfs_key key;
2091                 struct btrfs_dir_item *di;
2092                 struct btrfs_dir_item *log_di;
2093                 u32 total_size;
2094                 u32 cur;
2095
2096                 btrfs_item_key_to_cpu(path->nodes[0], &key, i);
2097                 if (key.objectid != ino || key.type != BTRFS_XATTR_ITEM_KEY) {
2098                         ret = 0;
2099                         goto out;
2100                 }
2101
2102                 di = btrfs_item_ptr(path->nodes[0], i, struct btrfs_dir_item);
2103                 total_size = btrfs_item_size_nr(path->nodes[0], i);
2104                 cur = 0;
2105                 while (cur < total_size) {
2106                         u16 name_len = btrfs_dir_name_len(path->nodes[0], di);
2107                         u16 data_len = btrfs_dir_data_len(path->nodes[0], di);
2108                         u32 this_len = sizeof(*di) + name_len + data_len;
2109                         char *name;
2110
2111                         name = kmalloc(name_len, GFP_NOFS);
2112                         if (!name) {
2113                                 ret = -ENOMEM;
2114                                 goto out;
2115                         }
2116                         read_extent_buffer(path->nodes[0], name,
2117                                            (unsigned long)(di + 1), name_len);
2118
2119                         log_di = btrfs_lookup_xattr(NULL, log, log_path, ino,
2120                                                     name, name_len, 0);
2121                         btrfs_release_path(log_path);
2122                         if (!log_di) {
2123                                 /* Doesn't exist in log tree, so delete it. */
2124                                 btrfs_release_path(path);
2125                                 di = btrfs_lookup_xattr(trans, root, path, ino,
2126                                                         name, name_len, -1);
2127                                 kfree(name);
2128                                 if (IS_ERR(di)) {
2129                                         ret = PTR_ERR(di);
2130                                         goto out;
2131                                 }
2132                                 ASSERT(di);
2133                                 ret = btrfs_delete_one_dir_name(trans, root,
2134                                                                 path, di);
2135                                 if (ret)
2136                                         goto out;
2137                                 btrfs_release_path(path);
2138                                 search_key = key;
2139                                 goto again;
2140                         }
2141                         kfree(name);
2142                         if (IS_ERR(log_di)) {
2143                                 ret = PTR_ERR(log_di);
2144                                 goto out;
2145                         }
2146                         cur += this_len;
2147                         di = (struct btrfs_dir_item *)((char *)di + this_len);
2148                 }
2149         }
2150         ret = btrfs_next_leaf(root, path);
2151         if (ret > 0)
2152                 ret = 0;
2153         else if (ret == 0)
2154                 goto process_leaf;
2155 out:
2156         btrfs_free_path(log_path);
2157         btrfs_release_path(path);
2158         return ret;
2159 }
2160
2161
2162 /*
2163  * deletion replay happens before we copy any new directory items
2164  * out of the log or out of backreferences from inodes.  It
2165  * scans the log to find ranges of keys that log is authoritative for,
2166  * and then scans the directory to find items in those ranges that are
2167  * not present in the log.
2168  *
2169  * Anything we don't find in the log is unlinked and removed from the
2170  * directory.
2171  */
2172 static noinline int replay_dir_deletes(struct btrfs_trans_handle *trans,
2173                                        struct btrfs_root *root,
2174                                        struct btrfs_root *log,
2175                                        struct btrfs_path *path,
2176                                        u64 dirid, int del_all)
2177 {
2178         u64 range_start;
2179         u64 range_end;
2180         int key_type = BTRFS_DIR_LOG_ITEM_KEY;
2181         int ret = 0;
2182         struct btrfs_key dir_key;
2183         struct btrfs_key found_key;
2184         struct btrfs_path *log_path;
2185         struct inode *dir;
2186
2187         dir_key.objectid = dirid;
2188         dir_key.type = BTRFS_DIR_ITEM_KEY;
2189         log_path = btrfs_alloc_path();
2190         if (!log_path)
2191                 return -ENOMEM;
2192
2193         dir = read_one_inode(root, dirid);
2194         /* it isn't an error if the inode isn't there, that can happen
2195          * because we replay the deletes before we copy in the inode item
2196          * from the log
2197          */
2198         if (!dir) {
2199                 btrfs_free_path(log_path);
2200                 return 0;
2201         }
2202 again:
2203         range_start = 0;
2204         range_end = 0;
2205         while (1) {
2206                 if (del_all)
2207                         range_end = (u64)-1;
2208                 else {
2209                         ret = find_dir_range(log, path, dirid, key_type,
2210                                              &range_start, &range_end);
2211                         if (ret != 0)
2212                                 break;
2213                 }
2214
2215                 dir_key.offset = range_start;
2216                 while (1) {
2217                         int nritems;
2218                         ret = btrfs_search_slot(NULL, root, &dir_key, path,
2219                                                 0, 0);
2220                         if (ret < 0)
2221                                 goto out;
2222
2223                         nritems = btrfs_header_nritems(path->nodes[0]);
2224                         if (path->slots[0] >= nritems) {
2225                                 ret = btrfs_next_leaf(root, path);
2226                                 if (ret == 1)
2227                                         break;
2228                                 else if (ret < 0)
2229                                         goto out;
2230                         }
2231                         btrfs_item_key_to_cpu(path->nodes[0], &found_key,
2232                                               path->slots[0]);
2233                         if (found_key.objectid != dirid ||
2234                             found_key.type != dir_key.type)
2235                                 goto next_type;
2236
2237                         if (found_key.offset > range_end)
2238                                 break;
2239
2240                         ret = check_item_in_log(trans, root, log, path,
2241                                                 log_path, dir,
2242                                                 &found_key);
2243                         if (ret)
2244                                 goto out;
2245                         if (found_key.offset == (u64)-1)
2246                                 break;
2247                         dir_key.offset = found_key.offset + 1;
2248                 }
2249                 btrfs_release_path(path);
2250                 if (range_end == (u64)-1)
2251                         break;
2252                 range_start = range_end + 1;
2253         }
2254
2255 next_type:
2256         ret = 0;
2257         if (key_type == BTRFS_DIR_LOG_ITEM_KEY) {
2258                 key_type = BTRFS_DIR_LOG_INDEX_KEY;
2259                 dir_key.type = BTRFS_DIR_INDEX_KEY;
2260                 btrfs_release_path(path);
2261                 goto again;
2262         }
2263 out:
2264         btrfs_release_path(path);
2265         btrfs_free_path(log_path);
2266         iput(dir);
2267         return ret;
2268 }
2269
2270 /*
2271  * the process_func used to replay items from the log tree.  This
2272  * gets called in two different stages.  The first stage just looks
2273  * for inodes and makes sure they are all copied into the subvolume.
2274  *
2275  * The second stage copies all the other item types from the log into
2276  * the subvolume.  The two stage approach is slower, but gets rid of
2277  * lots of complexity around inodes referencing other inodes that exist
2278  * only in the log (references come from either directory items or inode
2279  * back refs).
2280  */
2281 static int replay_one_buffer(struct btrfs_root *log, struct extent_buffer *eb,
2282                              struct walk_control *wc, u64 gen)
2283 {
2284         int nritems;
2285         struct btrfs_path *path;
2286         struct btrfs_root *root = wc->replay_dest;
2287         struct btrfs_key key;
2288         int level;
2289         int i;
2290         int ret;
2291
2292         ret = btrfs_read_buffer(eb, gen);
2293         if (ret)
2294                 return ret;
2295
2296         level = btrfs_header_level(eb);
2297
2298         if (level != 0)
2299                 return 0;
2300
2301         path = btrfs_alloc_path();
2302         if (!path)
2303                 return -ENOMEM;
2304
2305         nritems = btrfs_header_nritems(eb);
2306         for (i = 0; i < nritems; i++) {
2307                 btrfs_item_key_to_cpu(eb, &key, i);
2308
2309                 /* inode keys are done during the first stage */
2310                 if (key.type == BTRFS_INODE_ITEM_KEY &&
2311                     wc->stage == LOG_WALK_REPLAY_INODES) {
2312                         struct btrfs_inode_item *inode_item;
2313                         u32 mode;
2314
2315                         inode_item = btrfs_item_ptr(eb, i,
2316                                             struct btrfs_inode_item);
2317                         ret = replay_xattr_deletes(wc->trans, root, log,
2318                                                    path, key.objectid);
2319                         if (ret)
2320                                 break;
2321                         mode = btrfs_inode_mode(eb, inode_item);
2322                         if (S_ISDIR(mode)) {
2323                                 ret = replay_dir_deletes(wc->trans,
2324                                          root, log, path, key.objectid, 0);
2325                                 if (ret)
2326                                         break;
2327                         }
2328                         ret = overwrite_item(wc->trans, root, path,
2329                                              eb, i, &key);
2330                         if (ret)
2331                                 break;
2332
2333                         /* for regular files, make sure corresponding
2334                          * orhpan item exist. extents past the new EOF
2335                          * will be truncated later by orphan cleanup.
2336                          */
2337                         if (S_ISREG(mode)) {
2338                                 ret = insert_orphan_item(wc->trans, root,
2339                                                          key.objectid);
2340                                 if (ret)
2341                                         break;
2342                         }
2343
2344                         ret = link_to_fixup_dir(wc->trans, root,
2345                                                 path, key.objectid);
2346                         if (ret)
2347                                 break;
2348                 }
2349
2350                 if (key.type == BTRFS_DIR_INDEX_KEY &&
2351                     wc->stage == LOG_WALK_REPLAY_DIR_INDEX) {
2352                         ret = replay_one_dir_item(wc->trans, root, path,
2353                                                   eb, i, &key);
2354                         if (ret)
2355                                 break;
2356                 }
2357
2358                 if (wc->stage < LOG_WALK_REPLAY_ALL)
2359                         continue;
2360
2361                 /* these keys are simply copied */
2362                 if (key.type == BTRFS_XATTR_ITEM_KEY) {
2363                         ret = overwrite_item(wc->trans, root, path,
2364                                              eb, i, &key);
2365                         if (ret)
2366                                 break;
2367                 } else if (key.type == BTRFS_INODE_REF_KEY ||
2368                            key.type == BTRFS_INODE_EXTREF_KEY) {
2369                         ret = add_inode_ref(wc->trans, root, log, path,
2370                                             eb, i, &key);
2371                         if (ret && ret != -ENOENT)
2372                                 break;
2373                         ret = 0;
2374                 } else if (key.type == BTRFS_EXTENT_DATA_KEY) {
2375                         ret = replay_one_extent(wc->trans, root, path,
2376                                                 eb, i, &key);
2377                         if (ret)
2378                                 break;
2379                 } else if (key.type == BTRFS_DIR_ITEM_KEY) {
2380                         ret = replay_one_dir_item(wc->trans, root, path,
2381                                                   eb, i, &key);
2382                         if (ret)
2383                                 break;
2384                 }
2385         }
2386         btrfs_free_path(path);
2387         return ret;
2388 }
2389
2390 static noinline int walk_down_log_tree(struct btrfs_trans_handle *trans,
2391                                    struct btrfs_root *root,
2392                                    struct btrfs_path *path, int *level,
2393                                    struct walk_control *wc)
2394 {
2395         u64 root_owner;
2396         u64 bytenr;
2397         u64 ptr_gen;
2398         struct extent_buffer *next;
2399         struct extent_buffer *cur;
2400         struct extent_buffer *parent;
2401         u32 blocksize;
2402         int ret = 0;
2403
2404         WARN_ON(*level < 0);
2405         WARN_ON(*level >= BTRFS_MAX_LEVEL);
2406
2407         while (*level > 0) {
2408                 WARN_ON(*level < 0);
2409                 WARN_ON(*level >= BTRFS_MAX_LEVEL);
2410                 cur = path->nodes[*level];
2411
2412                 WARN_ON(btrfs_header_level(cur) != *level);
2413
2414                 if (path->slots[*level] >=
2415                     btrfs_header_nritems(cur))
2416                         break;
2417
2418                 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
2419                 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
2420                 blocksize = root->nodesize;
2421
2422                 parent = path->nodes[*level];
2423                 root_owner = btrfs_header_owner(parent);
2424
2425                 next = btrfs_find_create_tree_block(root, bytenr);
2426                 if (!next)
2427                         return -ENOMEM;
2428
2429                 if (*level == 1) {
2430                         ret = wc->process_func(root, next, wc, ptr_gen);
2431                         if (ret) {
2432                                 free_extent_buffer(next);
2433                                 return ret;
2434                         }
2435
2436                         path->slots[*level]++;
2437                         if (wc->free) {
2438                                 ret = btrfs_read_buffer(next, ptr_gen);
2439                                 if (ret) {
2440                                         free_extent_buffer(next);
2441                                         return ret;
2442                                 }
2443
2444                                 if (trans) {
2445                                         btrfs_tree_lock(next);
2446                                         btrfs_set_lock_blocking(next);
2447                                         clean_tree_block(trans, root->fs_info,
2448                                                         next);
2449                                         btrfs_wait_tree_block_writeback(next);
2450                                         btrfs_tree_unlock(next);
2451                                 } else {
2452                                         if (test_and_clear_bit(EXTENT_BUFFER_DIRTY, &next->bflags))
2453                                                 clear_extent_buffer_dirty(next);
2454                                 }
2455
2456                                 WARN_ON(root_owner !=
2457                                         BTRFS_TREE_LOG_OBJECTID);
2458                                 ret = btrfs_free_and_pin_reserved_extent(root,
2459                                                          bytenr, blocksize);
2460                                 if (ret) {
2461                                         free_extent_buffer(next);
2462                                         return ret;
2463                                 }
2464                         }
2465                         free_extent_buffer(next);
2466                         continue;
2467                 }
2468                 ret = btrfs_read_buffer(next, ptr_gen);
2469                 if (ret) {
2470                         free_extent_buffer(next);
2471                         return ret;
2472                 }
2473
2474                 WARN_ON(*level <= 0);
2475                 if (path->nodes[*level-1])
2476                         free_extent_buffer(path->nodes[*level-1]);
2477                 path->nodes[*level-1] = next;
2478                 *level = btrfs_header_level(next);
2479                 path->slots[*level] = 0;
2480                 cond_resched();
2481         }
2482         WARN_ON(*level < 0);
2483         WARN_ON(*level >= BTRFS_MAX_LEVEL);
2484
2485         path->slots[*level] = btrfs_header_nritems(path->nodes[*level]);
2486
2487         cond_resched();
2488         return 0;
2489 }
2490
2491 static noinline int walk_up_log_tree(struct btrfs_trans_handle *trans,
2492                                  struct btrfs_root *root,
2493                                  struct btrfs_path *path, int *level,
2494                                  struct walk_control *wc)
2495 {
2496         u64 root_owner;
2497         int i;
2498         int slot;
2499         int ret;
2500
2501         for (i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
2502                 slot = path->slots[i];
2503                 if (slot + 1 < btrfs_header_nritems(path->nodes[i])) {
2504                         path->slots[i]++;
2505                         *level = i;
2506                         WARN_ON(*level == 0);
2507                         return 0;
2508                 } else {
2509                         struct extent_buffer *parent;
2510                         if (path->nodes[*level] == root->node)
2511                                 parent = path->nodes[*level];
2512                         else
2513                                 parent = path->nodes[*level + 1];
2514
2515                         root_owner = btrfs_header_owner(parent);
2516                         ret = wc->process_func(root, path->nodes[*level], wc,
2517                                  btrfs_header_generation(path->nodes[*level]));
2518                         if (ret)
2519                                 return ret;
2520
2521                         if (wc->free) {
2522                                 struct extent_buffer *next;
2523
2524                                 next = path->nodes[*level];
2525
2526                                 if (trans) {
2527                                         btrfs_tree_lock(next);
2528                                         btrfs_set_lock_blocking(next);
2529                                         clean_tree_block(trans, root->fs_info,
2530                                                         next);
2531                                         btrfs_wait_tree_block_writeback(next);
2532                                         btrfs_tree_unlock(next);
2533                                 } else {
2534                                         if (test_and_clear_bit(EXTENT_BUFFER_DIRTY, &next->bflags))
2535                                                 clear_extent_buffer_dirty(next);
2536                                 }
2537
2538                                 WARN_ON(root_owner != BTRFS_TREE_LOG_OBJECTID);
2539                                 ret = btrfs_free_and_pin_reserved_extent(root,
2540                                                 path->nodes[*level]->start,
2541                                                 path->nodes[*level]->len);
2542                                 if (ret)
2543                                         return ret;
2544                         }
2545                         free_extent_buffer(path->nodes[*level]);
2546                         path->nodes[*level] = NULL;
2547                         *level = i + 1;
2548                 }
2549         }
2550         return 1;
2551 }
2552
2553 /*
2554  * drop the reference count on the tree rooted at 'snap'.  This traverses
2555  * the tree freeing any blocks that have a ref count of zero after being
2556  * decremented.
2557  */
2558 static int walk_log_tree(struct btrfs_trans_handle *trans,
2559                          struct btrfs_root *log, struct walk_control *wc)
2560 {
2561         int ret = 0;
2562         int wret;
2563         int level;
2564         struct btrfs_path *path;
2565         int orig_level;
2566
2567         path = btrfs_alloc_path();
2568         if (!path)
2569                 return -ENOMEM;
2570
2571         level = btrfs_header_level(log->node);
2572         orig_level = level;
2573         path->nodes[level] = log->node;
2574         extent_buffer_get(log->node);
2575         path->slots[level] = 0;
2576
2577         while (1) {
2578                 wret = walk_down_log_tree(trans, log, path, &level, wc);
2579                 if (wret > 0)
2580                         break;
2581                 if (wret < 0) {
2582                         ret = wret;
2583                         goto out;
2584                 }
2585
2586                 wret = walk_up_log_tree(trans, log, path, &level, wc);
2587                 if (wret > 0)
2588                         break;
2589                 if (wret < 0) {
2590                         ret = wret;
2591                         goto out;
2592                 }
2593         }
2594
2595         /* was the root node processed? if not, catch it here */
2596         if (path->nodes[orig_level]) {
2597                 ret = wc->process_func(log, path->nodes[orig_level], wc,
2598                          btrfs_header_generation(path->nodes[orig_level]));
2599                 if (ret)
2600                         goto out;
2601                 if (wc->free) {
2602                         struct extent_buffer *next;
2603
2604                         next = path->nodes[orig_level];
2605
2606                         if (trans) {
2607                                 btrfs_tree_lock(next);
2608                                 btrfs_set_lock_blocking(next);
2609                                 clean_tree_block(trans, log->fs_info, next);
2610                                 btrfs_wait_tree_block_writeback(next);
2611                                 btrfs_tree_unlock(next);
2612                         } else {
2613                                 if (test_and_clear_bit(EXTENT_BUFFER_DIRTY, &next->bflags))
2614                                         clear_extent_buffer_dirty(next);
2615                         }
2616
2617                         WARN_ON(log->root_key.objectid !=
2618                                 BTRFS_TREE_LOG_OBJECTID);
2619                         ret = btrfs_free_and_pin_reserved_extent(log, next->start,
2620                                                          next->len);
2621                         if (ret)
2622                                 goto out;
2623                 }
2624         }
2625
2626 out:
2627         btrfs_free_path(path);
2628         return ret;
2629 }
2630
2631 /*
2632  * helper function to update the item for a given subvolumes log root
2633  * in the tree of log roots
2634  */
2635 static int update_log_root(struct btrfs_trans_handle *trans,
2636                            struct btrfs_root *log)
2637 {
2638         int ret;
2639
2640         if (log->log_transid == 1) {
2641                 /* insert root item on the first sync */
2642                 ret = btrfs_insert_root(trans, log->fs_info->log_root_tree,
2643                                 &log->root_key, &log->root_item);
2644         } else {
2645                 ret = btrfs_update_root(trans, log->fs_info->log_root_tree,
2646                                 &log->root_key, &log->root_item);
2647         }
2648         return ret;
2649 }
2650
2651 static void wait_log_commit(struct btrfs_root *root, int transid)
2652 {
2653         DEFINE_WAIT(wait);
2654         int index = transid % 2;
2655
2656         /*
2657          * we only allow two pending log transactions at a time,
2658          * so we know that if ours is more than 2 older than the
2659          * current transaction, we're done
2660          */
2661         do {
2662                 prepare_to_wait(&root->log_commit_wait[index],
2663                                 &wait, TASK_UNINTERRUPTIBLE);
2664                 mutex_unlock(&root->log_mutex);
2665
2666                 if (root->log_transid_committed < transid &&
2667                     atomic_read(&root->log_commit[index]))
2668                         schedule();
2669
2670                 finish_wait(&root->log_commit_wait[index], &wait);
2671                 mutex_lock(&root->log_mutex);
2672         } while (root->log_transid_committed < transid &&
2673                  atomic_read(&root->log_commit[index]));
2674 }
2675
2676 static void wait_for_writer(struct btrfs_root *root)
2677 {
2678         DEFINE_WAIT(wait);
2679
2680         while (atomic_read(&root->log_writers)) {
2681                 prepare_to_wait(&root->log_writer_wait,
2682                                 &wait, TASK_UNINTERRUPTIBLE);
2683                 mutex_unlock(&root->log_mutex);
2684                 if (atomic_read(&root->log_writers))
2685                         schedule();
2686                 finish_wait(&root->log_writer_wait, &wait);
2687                 mutex_lock(&root->log_mutex);
2688         }
2689 }
2690
2691 static inline void btrfs_remove_log_ctx(struct btrfs_root *root,
2692                                         struct btrfs_log_ctx *ctx)
2693 {
2694         if (!ctx)
2695                 return;
2696
2697         mutex_lock(&root->log_mutex);
2698         list_del_init(&ctx->list);
2699         mutex_unlock(&root->log_mutex);
2700 }
2701
2702 /*
2703  * Invoked in log mutex context, or be sure there is no other task which
2704  * can access the list.
2705  */
2706 static inline void btrfs_remove_all_log_ctxs(struct btrfs_root *root,
2707                                              int index, int error)
2708 {
2709         struct btrfs_log_ctx *ctx;
2710         struct btrfs_log_ctx *safe;
2711
2712         list_for_each_entry_safe(ctx, safe, &root->log_ctxs[index], list) {
2713                 list_del_init(&ctx->list);
2714                 ctx->log_ret = error;
2715         }
2716
2717         INIT_LIST_HEAD(&root->log_ctxs[index]);
2718 }
2719
2720 /*
2721  * btrfs_sync_log does sends a given tree log down to the disk and
2722  * updates the super blocks to record it.  When this call is done,
2723  * you know that any inodes previously logged are safely on disk only
2724  * if it returns 0.
2725  *
2726  * Any other return value means you need to call btrfs_commit_transaction.
2727  * Some of the edge cases for fsyncing directories that have had unlinks
2728  * or renames done in the past mean that sometimes the only safe
2729  * fsync is to commit the whole FS.  When btrfs_sync_log returns -EAGAIN,
2730  * that has happened.
2731  */
2732 int btrfs_sync_log(struct btrfs_trans_handle *trans,
2733                    struct btrfs_root *root, struct btrfs_log_ctx *ctx)
2734 {
2735         int index1;
2736         int index2;
2737         int mark;
2738         int ret;
2739         struct btrfs_root *log = root->log_root;
2740         struct btrfs_root *log_root_tree = root->fs_info->log_root_tree;
2741         int log_transid = 0;
2742         struct btrfs_log_ctx root_log_ctx;
2743         struct blk_plug plug;
2744
2745         mutex_lock(&root->log_mutex);
2746         log_transid = ctx->log_transid;
2747         if (root->log_transid_committed >= log_transid) {
2748                 mutex_unlock(&root->log_mutex);
2749                 return ctx->log_ret;
2750         }
2751
2752         index1 = log_transid % 2;
2753         if (atomic_read(&root->log_commit[index1])) {
2754                 wait_log_commit(root, log_transid);
2755                 mutex_unlock(&root->log_mutex);
2756                 return ctx->log_ret;
2757         }
2758         ASSERT(log_transid == root->log_transid);
2759         atomic_set(&root->log_commit[index1], 1);
2760
2761         /* wait for previous tree log sync to complete */
2762         if (atomic_read(&root->log_commit[(index1 + 1) % 2]))
2763                 wait_log_commit(root, log_transid - 1);
2764
2765         while (1) {
2766                 int batch = atomic_read(&root->log_batch);
2767                 /* when we're on an ssd, just kick the log commit out */
2768                 if (!btrfs_test_opt(root, SSD) &&
2769                     test_bit(BTRFS_ROOT_MULTI_LOG_TASKS, &root->state)) {
2770                         mutex_unlock(&root->log_mutex);
2771                         schedule_timeout_uninterruptible(1);
2772                         mutex_lock(&root->log_mutex);
2773                 }
2774                 wait_for_writer(root);
2775                 if (batch == atomic_read(&root->log_batch))
2776                         break;
2777         }
2778
2779         /* bail out if we need to do a full commit */
2780         if (btrfs_need_log_full_commit(root->fs_info, trans)) {
2781                 ret = -EAGAIN;
2782                 btrfs_free_logged_extents(log, log_transid);
2783                 mutex_unlock(&root->log_mutex);
2784                 goto out;
2785         }
2786
2787         if (log_transid % 2 == 0)
2788                 mark = EXTENT_DIRTY;
2789         else
2790                 mark = EXTENT_NEW;
2791
2792         /* we start IO on  all the marked extents here, but we don't actually
2793          * wait for them until later.
2794          */
2795         blk_start_plug(&plug);
2796         ret = btrfs_write_marked_extents(log, &log->dirty_log_pages, mark);
2797         if (ret) {
2798                 blk_finish_plug(&plug);
2799                 btrfs_abort_transaction(trans, root, ret);
2800                 btrfs_free_logged_extents(log, log_transid);
2801                 btrfs_set_log_full_commit(root->fs_info, trans);
2802                 mutex_unlock(&root->log_mutex);
2803                 goto out;
2804         }
2805
2806         btrfs_set_root_node(&log->root_item, log->node);
2807
2808         root->log_transid++;
2809         log->log_transid = root->log_transid;
2810         root->log_start_pid = 0;
2811         /*
2812          * IO has been started, blocks of the log tree have WRITTEN flag set
2813          * in their headers. new modifications of the log will be written to
2814          * new positions. so it's safe to allow log writers to go in.
2815          */
2816         mutex_unlock(&root->log_mutex);
2817
2818         btrfs_init_log_ctx(&root_log_ctx);
2819
2820         mutex_lock(&log_root_tree->log_mutex);
2821         atomic_inc(&log_root_tree->log_batch);
2822         atomic_inc(&log_root_tree->log_writers);
2823
2824         index2 = log_root_tree->log_transid % 2;
2825         list_add_tail(&root_log_ctx.list, &log_root_tree->log_ctxs[index2]);
2826         root_log_ctx.log_transid = log_root_tree->log_transid;
2827
2828         mutex_unlock(&log_root_tree->log_mutex);
2829
2830         ret = update_log_root(trans, log);
2831
2832         mutex_lock(&log_root_tree->log_mutex);
2833         if (atomic_dec_and_test(&log_root_tree->log_writers)) {
2834                 /*
2835                  * Implicit memory barrier after atomic_dec_and_test
2836                  */
2837                 if (waitqueue_active(&log_root_tree->log_writer_wait))
2838                         wake_up(&log_root_tree->log_writer_wait);
2839         }
2840
2841         if (ret) {
2842                 if (!list_empty(&root_log_ctx.list))
2843                         list_del_init(&root_log_ctx.list);
2844
2845                 blk_finish_plug(&plug);
2846                 btrfs_set_log_full_commit(root->fs_info, trans);
2847
2848                 if (ret != -ENOSPC) {
2849                         btrfs_abort_transaction(trans, root, ret);
2850                         mutex_unlock(&log_root_tree->log_mutex);
2851                         goto out;
2852                 }
2853                 btrfs_wait_marked_extents(log, &log->dirty_log_pages, mark);
2854                 btrfs_free_logged_extents(log, log_transid);
2855                 mutex_unlock(&log_root_tree->log_mutex);
2856                 ret = -EAGAIN;
2857                 goto out;
2858         }
2859
2860         if (log_root_tree->log_transid_committed >= root_log_ctx.log_transid) {
2861                 blk_finish_plug(&plug);
2862                 list_del_init(&root_log_ctx.list);
2863                 mutex_unlock(&log_root_tree->log_mutex);
2864                 ret = root_log_ctx.log_ret;
2865                 goto out;
2866         }
2867
2868         index2 = root_log_ctx.log_transid % 2;
2869         if (atomic_read(&log_root_tree->log_commit[index2])) {
2870                 blk_finish_plug(&plug);
2871                 ret = btrfs_wait_marked_extents(log, &log->dirty_log_pages,
2872                                                 mark);
2873                 btrfs_wait_logged_extents(trans, log, log_transid);
2874                 wait_log_commit(log_root_tree,
2875                                 root_log_ctx.log_transid);
2876                 mutex_unlock(&log_root_tree->log_mutex);
2877                 if (!ret)
2878                         ret = root_log_ctx.log_ret;
2879                 goto out;
2880         }
2881         ASSERT(root_log_ctx.log_transid == log_root_tree->log_transid);
2882         atomic_set(&log_root_tree->log_commit[index2], 1);
2883
2884         if (atomic_read(&log_root_tree->log_commit[(index2 + 1) % 2])) {
2885                 wait_log_commit(log_root_tree,
2886                                 root_log_ctx.log_transid - 1);
2887         }
2888
2889         wait_for_writer(log_root_tree);
2890
2891         /*
2892          * now that we've moved on to the tree of log tree roots,
2893          * check the full commit flag again
2894          */
2895         if (btrfs_need_log_full_commit(root->fs_info, trans)) {
2896                 blk_finish_plug(&plug);
2897                 btrfs_wait_marked_extents(log, &log->dirty_log_pages, mark);
2898                 btrfs_free_logged_extents(log, log_transid);
2899                 mutex_unlock(&log_root_tree->log_mutex);
2900                 ret = -EAGAIN;
2901                 goto out_wake_log_root;
2902         }
2903
2904         ret = btrfs_write_marked_extents(log_root_tree,
2905                                          &log_root_tree->dirty_log_pages,
2906                                          EXTENT_DIRTY | EXTENT_NEW);
2907         blk_finish_plug(&plug);
2908         if (ret) {
2909                 btrfs_set_log_full_commit(root->fs_info, trans);
2910                 btrfs_abort_transaction(trans, root, ret);
2911                 btrfs_free_logged_extents(log, log_transid);
2912                 mutex_unlock(&log_root_tree->log_mutex);
2913                 goto out_wake_log_root;
2914         }
2915         ret = btrfs_wait_marked_extents(log, &log->dirty_log_pages, mark);
2916         if (!ret)
2917                 ret = btrfs_wait_marked_extents(log_root_tree,
2918                                                 &log_root_tree->dirty_log_pages,
2919                                                 EXTENT_NEW | EXTENT_DIRTY);
2920         if (ret) {
2921                 btrfs_set_log_full_commit(root->fs_info, trans);
2922                 btrfs_free_logged_extents(log, log_transid);
2923                 mutex_unlock(&log_root_tree->log_mutex);
2924                 goto out_wake_log_root;
2925         }
2926         btrfs_wait_logged_extents(trans, log, log_transid);
2927
2928         btrfs_set_super_log_root(root->fs_info->super_for_commit,
2929                                 log_root_tree->node->start);
2930         btrfs_set_super_log_root_level(root->fs_info->super_for_commit,
2931                                 btrfs_header_level(log_root_tree->node));
2932
2933         log_root_tree->log_transid++;
2934         mutex_unlock(&log_root_tree->log_mutex);
2935
2936         /*
2937          * nobody else is going to jump in and write the the ctree
2938          * super here because the log_commit atomic below is protecting
2939          * us.  We must be called with a transaction handle pinning
2940          * the running transaction open, so a full commit can't hop
2941          * in and cause problems either.
2942          */
2943         ret = write_ctree_super(trans, root->fs_info->tree_root, 1);
2944         if (ret) {
2945                 btrfs_set_log_full_commit(root->fs_info, trans);
2946                 btrfs_abort_transaction(trans, root, ret);
2947                 goto out_wake_log_root;
2948         }
2949
2950         mutex_lock(&root->log_mutex);
2951         if (root->last_log_commit < log_transid)
2952                 root->last_log_commit = log_transid;
2953         mutex_unlock(&root->log_mutex);
2954
2955 out_wake_log_root:
2956         mutex_lock(&log_root_tree->log_mutex);
2957         btrfs_remove_all_log_ctxs(log_root_tree, index2, ret);
2958
2959         log_root_tree->log_transid_committed++;
2960         atomic_set(&log_root_tree->log_commit[index2], 0);
2961         mutex_unlock(&log_root_tree->log_mutex);
2962
2963         /*
2964          * The barrier before waitqueue_active is implied by mutex_unlock
2965          */
2966         if (waitqueue_active(&log_root_tree->log_commit_wait[index2]))
2967                 wake_up(&log_root_tree->log_commit_wait[index2]);
2968 out:
2969         mutex_lock(&root->log_mutex);
2970         btrfs_remove_all_log_ctxs(root, index1, ret);
2971         root->log_transid_committed++;
2972         atomic_set(&root->log_commit[index1], 0);
2973         mutex_unlock(&root->log_mutex);
2974
2975         /*
2976          * The barrier before waitqueue_active is implied by mutex_unlock
2977          */
2978         if (waitqueue_active(&root->log_commit_wait[index1]))
2979                 wake_up(&root->log_commit_wait[index1]);
2980         return ret;
2981 }
2982
2983 static void free_log_tree(struct btrfs_trans_handle *trans,
2984                           struct btrfs_root *log)
2985 {
2986         int ret;
2987         u64 start;
2988         u64 end;
2989         struct walk_control wc = {
2990                 .free = 1,
2991                 .process_func = process_one_buffer
2992         };
2993
2994         ret = walk_log_tree(trans, log, &wc);
2995         /* I don't think this can happen but just in case */
2996         if (ret)
2997                 btrfs_abort_transaction(trans, log, ret);
2998
2999         while (1) {
3000                 ret = find_first_extent_bit(&log->dirty_log_pages,
3001                                 0, &start, &end, EXTENT_DIRTY | EXTENT_NEW,
3002                                 NULL);
3003                 if (ret)
3004                         break;
3005
3006                 clear_extent_bits(&log->dirty_log_pages, start, end,
3007                                   EXTENT_DIRTY | EXTENT_NEW, GFP_NOFS);
3008         }
3009
3010         /*
3011          * We may have short-circuited the log tree with the full commit logic
3012          * and left ordered extents on our list, so clear these out to keep us
3013          * from leaking inodes and memory.
3014          */
3015         btrfs_free_logged_extents(log, 0);
3016         btrfs_free_logged_extents(log, 1);
3017
3018         free_extent_buffer(log->node);
3019         kfree(log);
3020 }
3021
3022 /*
3023  * free all the extents used by the tree log.  This should be called
3024  * at commit time of the full transaction
3025  */
3026 int btrfs_free_log(struct btrfs_trans_handle *trans, struct btrfs_root *root)
3027 {
3028         if (root->log_root) {
3029                 free_log_tree(trans, root->log_root);
3030                 root->log_root = NULL;
3031         }
3032         return 0;
3033 }
3034
3035 int btrfs_free_log_root_tree(struct btrfs_trans_handle *trans,
3036                              struct btrfs_fs_info *fs_info)
3037 {
3038         if (fs_info->log_root_tree) {
3039                 free_log_tree(trans, fs_info->log_root_tree);
3040                 fs_info->log_root_tree = NULL;
3041         }
3042         return 0;
3043 }
3044
3045 /*
3046  * If both a file and directory are logged, and unlinks or renames are
3047  * mixed in, we have a few interesting corners:
3048  *
3049  * create file X in dir Y
3050  * link file X to X.link in dir Y
3051  * fsync file X
3052  * unlink file X but leave X.link
3053  * fsync dir Y
3054  *
3055  * After a crash we would expect only X.link to exist.  But file X
3056  * didn't get fsync'd again so the log has back refs for X and X.link.
3057  *
3058  * We solve this by removing directory entries and inode backrefs from the
3059  * log when a file that was logged in the current transaction is
3060  * unlinked.  Any later fsync will include the updated log entries, and
3061  * we'll be able to reconstruct the proper directory items from backrefs.
3062  *
3063  * This optimizations allows us to avoid relogging the entire inode
3064  * or the entire directory.
3065  */
3066 int btrfs_del_dir_entries_in_log(struct btrfs_trans_handle *trans,
3067                                  struct btrfs_root *root,
3068                                  const char *name, int name_len,
3069                                  struct inode *dir, u64 index)
3070 {
3071         struct btrfs_root *log;
3072         struct btrfs_dir_item *di;
3073         struct btrfs_path *path;
3074         int ret;
3075         int err = 0;
3076         int bytes_del = 0;
3077         u64 dir_ino = btrfs_ino(dir);
3078
3079         if (BTRFS_I(dir)->logged_trans < trans->transid)
3080                 return 0;
3081
3082         ret = join_running_log_trans(root);
3083         if (ret)
3084                 return 0;
3085
3086         mutex_lock(&BTRFS_I(dir)->log_mutex);
3087
3088         log = root->log_root;
3089         path = btrfs_alloc_path();
3090         if (!path) {
3091                 err = -ENOMEM;
3092                 goto out_unlock;
3093         }
3094
3095         di = btrfs_lookup_dir_item(trans, log, path, dir_ino,
3096                                    name, name_len, -1);
3097         if (IS_ERR(di)) {
3098                 err = PTR_ERR(di);
3099                 goto fail;
3100         }
3101         if (di) {
3102                 ret = btrfs_delete_one_dir_name(trans, log, path, di);
3103                 bytes_del += name_len;
3104                 if (ret) {
3105                         err = ret;
3106                         goto fail;
3107                 }
3108         }
3109         btrfs_release_path(path);
3110         di = btrfs_lookup_dir_index_item(trans, log, path, dir_ino,
3111                                          index, name, name_len, -1);
3112         if (IS_ERR(di)) {
3113                 err = PTR_ERR(di);
3114                 goto fail;
3115         }
3116         if (di) {
3117                 ret = btrfs_delete_one_dir_name(trans, log, path, di);
3118                 bytes_del += name_len;
3119                 if (ret) {
3120                         err = ret;
3121                         goto fail;
3122                 }
3123         }
3124
3125         /* update the directory size in the log to reflect the names
3126          * we have removed
3127          */
3128         if (bytes_del) {
3129                 struct btrfs_key key;
3130
3131                 key.objectid = dir_ino;
3132                 key.offset = 0;
3133                 key.type = BTRFS_INODE_ITEM_KEY;
3134                 btrfs_release_path(path);
3135
3136                 ret = btrfs_search_slot(trans, log, &key, path, 0, 1);
3137                 if (ret < 0) {
3138                         err = ret;
3139                         goto fail;
3140                 }
3141                 if (ret == 0) {
3142                         struct btrfs_inode_item *item;
3143                         u64 i_size;
3144
3145                         item = btrfs_item_ptr(path->nodes[0], path->slots[0],
3146                                               struct btrfs_inode_item);
3147                         i_size = btrfs_inode_size(path->nodes[0], item);
3148                         if (i_size > bytes_del)
3149                                 i_size -= bytes_del;
3150                         else
3151                                 i_size = 0;
3152                         btrfs_set_inode_size(path->nodes[0], item, i_size);
3153                         btrfs_mark_buffer_dirty(path->nodes[0]);
3154                 } else
3155                         ret = 0;
3156                 btrfs_release_path(path);
3157         }
3158 fail:
3159         btrfs_free_path(path);
3160 out_unlock:
3161         mutex_unlock(&BTRFS_I(dir)->log_mutex);
3162         if (ret == -ENOSPC) {
3163                 btrfs_set_log_full_commit(root->fs_info, trans);
3164                 ret = 0;
3165         } else if (ret < 0)
3166                 btrfs_abort_transaction(trans, root, ret);
3167
3168         btrfs_end_log_trans(root);
3169
3170         return err;
3171 }
3172
3173 /* see comments for btrfs_del_dir_entries_in_log */
3174 int btrfs_del_inode_ref_in_log(struct btrfs_trans_handle *trans,
3175                                struct btrfs_root *root,
3176                                const char *name, int name_len,
3177                                struct inode *inode, u64 dirid)
3178 {
3179         struct btrfs_root *log;
3180         u64 index;
3181         int ret;
3182
3183         if (BTRFS_I(inode)->logged_trans < trans->transid)
3184                 return 0;
3185
3186         ret = join_running_log_trans(root);
3187         if (ret)
3188                 return 0;
3189         log = root->log_root;
3190         mutex_lock(&BTRFS_I(inode)->log_mutex);
3191
3192         ret = btrfs_del_inode_ref(trans, log, name, name_len, btrfs_ino(inode),
3193                                   dirid, &index);
3194         mutex_unlock(&BTRFS_I(inode)->log_mutex);
3195         if (ret == -ENOSPC) {
3196                 btrfs_set_log_full_commit(root->fs_info, trans);
3197                 ret = 0;
3198         } else if (ret < 0 && ret != -ENOENT)
3199                 btrfs_abort_transaction(trans, root, ret);
3200         btrfs_end_log_trans(root);
3201
3202         return ret;
3203 }
3204
3205 /*
3206  * creates a range item in the log for 'dirid'.  first_offset and
3207  * last_offset tell us which parts of the key space the log should
3208  * be considered authoritative for.
3209  */
3210 static noinline int insert_dir_log_key(struct btrfs_trans_handle *trans,
3211                                        struct btrfs_root *log,
3212                                        struct btrfs_path *path,
3213                                        int key_type, u64 dirid,
3214                                        u64 first_offset, u64 last_offset)
3215 {
3216         int ret;
3217         struct btrfs_key key;
3218         struct btrfs_dir_log_item *item;
3219
3220         key.objectid = dirid;
3221         key.offset = first_offset;
3222         if (key_type == BTRFS_DIR_ITEM_KEY)
3223                 key.type = BTRFS_DIR_LOG_ITEM_KEY;
3224         else
3225                 key.type = BTRFS_DIR_LOG_INDEX_KEY;
3226         ret = btrfs_insert_empty_item(trans, log, path, &key, sizeof(*item));
3227         if (ret)
3228                 return ret;
3229
3230         item = btrfs_item_ptr(path->nodes[0], path->slots[0],
3231                               struct btrfs_dir_log_item);
3232         btrfs_set_dir_log_end(path->nodes[0], item, last_offset);
3233         btrfs_mark_buffer_dirty(path->nodes[0]);
3234         btrfs_release_path(path);
3235         return 0;
3236 }
3237
3238 /*
3239  * log all the items included in the current transaction for a given
3240  * directory.  This also creates the range items in the log tree required
3241  * to replay anything deleted before the fsync
3242  */
3243 static noinline int log_dir_items(struct btrfs_trans_handle *trans,
3244                           struct btrfs_root *root, struct inode *inode,
3245                           struct btrfs_path *path,
3246                           struct btrfs_path *dst_path, int key_type,
3247                           struct btrfs_log_ctx *ctx,
3248                           u64 min_offset, u64 *last_offset_ret)
3249 {
3250         struct btrfs_key min_key;
3251         struct btrfs_root *log = root->log_root;
3252         struct extent_buffer *src;
3253         int err = 0;
3254         int ret;
3255         int i;
3256         int nritems;
3257         u64 first_offset = min_offset;
3258         u64 last_offset = (u64)-1;
3259         u64 ino = btrfs_ino(inode);
3260
3261         log = root->log_root;
3262
3263         min_key.objectid = ino;
3264         min_key.type = key_type;
3265         min_key.offset = min_offset;
3266
3267         ret = btrfs_search_forward(root, &min_key, path, trans->transid);
3268
3269         /*
3270          * we didn't find anything from this transaction, see if there
3271          * is anything at all
3272          */
3273         if (ret != 0 || min_key.objectid != ino || min_key.type != key_type) {
3274                 min_key.objectid = ino;
3275                 min_key.type = key_type;
3276                 min_key.offset = (u64)-1;
3277                 btrfs_release_path(path);
3278                 ret = btrfs_search_slot(NULL, root, &min_key, path, 0, 0);
3279                 if (ret < 0) {
3280                         btrfs_release_path(path);
3281                         return ret;
3282                 }
3283                 ret = btrfs_previous_item(root, path, ino, key_type);
3284
3285                 /* if ret == 0 there are items for this type,
3286                  * create a range to tell us the last key of this type.
3287                  * otherwise, there are no items in this directory after
3288                  * *min_offset, and we create a range to indicate that.
3289                  */
3290                 if (ret == 0) {
3291                         struct btrfs_key tmp;
3292                         btrfs_item_key_to_cpu(path->nodes[0], &tmp,
3293                                               path->slots[0]);
3294                         if (key_type == tmp.type)
3295                                 first_offset = max(min_offset, tmp.offset) + 1;
3296                 }
3297                 goto done;
3298         }
3299
3300         /* go backward to find any previous key */
3301         ret = btrfs_previous_item(root, path, ino, key_type);
3302         if (ret == 0) {
3303                 struct btrfs_key tmp;
3304                 btrfs_item_key_to_cpu(path->nodes[0], &tmp, path->slots[0]);
3305                 if (key_type == tmp.type) {
3306                         first_offset = tmp.offset;
3307                         ret = overwrite_item(trans, log, dst_path,
3308                                              path->nodes[0], path->slots[0],
3309                                              &tmp);
3310                         if (ret) {
3311                                 err = ret;
3312                                 goto done;
3313                         }
3314                 }
3315         }
3316         btrfs_release_path(path);
3317
3318         /* find the first key from this transaction again */
3319         ret = btrfs_search_slot(NULL, root, &min_key, path, 0, 0);
3320         if (WARN_ON(ret != 0))
3321                 goto done;
3322
3323         /*
3324          * we have a block from this transaction, log every item in it
3325          * from our directory
3326          */
3327         while (1) {
3328                 struct btrfs_key tmp;
3329                 src = path->nodes[0];
3330                 nritems = btrfs_header_nritems(src);
3331                 for (i = path->slots[0]; i < nritems; i++) {
3332                         struct btrfs_dir_item *di;
3333
3334                         btrfs_item_key_to_cpu(src, &min_key, i);
3335
3336                         if (min_key.objectid != ino || min_key.type != key_type)
3337                                 goto done;
3338                         ret = overwrite_item(trans, log, dst_path, src, i,
3339                                              &min_key);
3340                         if (ret) {
3341                                 err = ret;
3342                                 goto done;
3343                         }
3344
3345                         /*
3346                          * We must make sure that when we log a directory entry,
3347                          * the corresponding inode, after log replay, has a
3348                          * matching link count. For example:
3349                          *
3350                          * touch foo
3351                          * mkdir mydir
3352                          * sync
3353                          * ln foo mydir/bar
3354                          * xfs_io -c "fsync" mydir
3355                          * <crash>
3356                          * <mount fs and log replay>
3357                          *
3358                          * Would result in a fsync log that when replayed, our
3359                          * file inode would have a link count of 1, but we get
3360                          * two directory entries pointing to the same inode.
3361                          * After removing one of the names, it would not be
3362                          * possible to remove the other name, which resulted
3363                          * always in stale file handle errors, and would not
3364                          * be possible to rmdir the parent directory, since
3365                          * its i_size could never decrement to the value
3366                          * BTRFS_EMPTY_DIR_SIZE, resulting in -ENOTEMPTY errors.
3367                          */
3368                         di = btrfs_item_ptr(src, i, struct btrfs_dir_item);
3369                         btrfs_dir_item_key_to_cpu(src, di, &tmp);
3370                         if (ctx &&
3371                             (btrfs_dir_transid(src, di) == trans->transid ||
3372                              btrfs_dir_type(src, di) == BTRFS_FT_DIR) &&
3373                             tmp.type != BTRFS_ROOT_ITEM_KEY)
3374                                 ctx->log_new_dentries = true;
3375                 }
3376                 path->slots[0] = nritems;
3377
3378                 /*
3379                  * look ahead to the next item and see if it is also
3380                  * from this directory and from this transaction
3381                  */
3382                 ret = btrfs_next_leaf(root, path);
3383                 if (ret) {
3384                         if (ret == 1)
3385                                 last_offset = (u64)-1;
3386                         else
3387                                 err = ret;
3388                         goto done;
3389                 }
3390                 btrfs_item_key_to_cpu(path->nodes[0], &tmp, path->slots[0]);
3391                 if (tmp.objectid != ino || tmp.type != key_type) {
3392                         last_offset = (u64)-1;
3393                         goto done;
3394                 }
3395                 if (btrfs_header_generation(path->nodes[0]) != trans->transid) {
3396                         ret = overwrite_item(trans, log, dst_path,
3397                                              path->nodes[0], path->slots[0],
3398                                              &tmp);
3399                         if (ret)
3400                                 err = ret;
3401                         else
3402                                 last_offset = tmp.offset;
3403                         goto done;
3404                 }
3405         }
3406 done:
3407         btrfs_release_path(path);
3408         btrfs_release_path(dst_path);
3409
3410         if (err == 0) {
3411                 *last_offset_ret = last_offset;
3412                 /*
3413                  * insert the log range keys to indicate where the log
3414                  * is valid
3415                  */
3416                 ret = insert_dir_log_key(trans, log, path, key_type,
3417                                          ino, first_offset, last_offset);
3418                 if (ret)
3419                         err = ret;
3420         }
3421         return err;
3422 }
3423
3424 /*
3425  * logging directories is very similar to logging inodes, We find all the items
3426  * from the current transaction and write them to the log.
3427  *
3428  * The recovery code scans the directory in the subvolume, and if it finds a
3429  * key in the range logged that is not present in the log tree, then it means
3430  * that dir entry was unlinked during the transaction.
3431  *
3432  * In order for that scan to work, we must include one key smaller than
3433  * the smallest logged by this transaction and one key larger than the largest
3434  * key logged by this transaction.
3435  */
3436 static noinline int log_directory_changes(struct btrfs_trans_handle *trans,
3437                           struct btrfs_root *root, struct inode *inode,
3438                           struct btrfs_path *path,
3439                           struct btrfs_path *dst_path,
3440                           struct btrfs_log_ctx *ctx)
3441 {
3442         u64 min_key;
3443         u64 max_key;
3444         int ret;
3445         int key_type = BTRFS_DIR_ITEM_KEY;
3446
3447 again:
3448         min_key = 0;
3449         max_key = 0;
3450         while (1) {
3451                 ret = log_dir_items(trans, root, inode, path,
3452                                     dst_path, key_type, ctx, min_key,
3453                                     &max_key);
3454                 if (ret)
3455                         return ret;
3456                 if (max_key == (u64)-1)
3457                         break;
3458                 min_key = max_key + 1;
3459         }
3460
3461         if (key_type == BTRFS_DIR_ITEM_KEY) {
3462                 key_type = BTRFS_DIR_INDEX_KEY;
3463                 goto again;
3464         }
3465         return 0;
3466 }
3467
3468 /*
3469  * a helper function to drop items from the log before we relog an
3470  * inode.  max_key_type indicates the highest item type to remove.
3471  * This cannot be run for file data extents because it does not
3472  * free the extents they point to.
3473  */
3474 static int drop_objectid_items(struct btrfs_trans_handle *trans,
3475                                   struct btrfs_root *log,
3476                                   struct btrfs_path *path,
3477                                   u64 objectid, int max_key_type)
3478 {
3479         int ret;
3480         struct btrfs_key key;
3481         struct btrfs_key found_key;
3482         int start_slot;
3483
3484         key.objectid = objectid;
3485         key.type = max_key_type;
3486         key.offset = (u64)-1;
3487
3488         while (1) {
3489                 ret = btrfs_search_slot(trans, log, &key, path, -1, 1);
3490                 BUG_ON(ret == 0); /* Logic error */
3491                 if (ret < 0)
3492                         break;
3493
3494                 if (path->slots[0] == 0)
3495                         break;
3496
3497                 path->slots[0]--;
3498                 btrfs_item_key_to_cpu(path->nodes[0], &found_key,
3499                                       path->slots[0]);
3500
3501                 if (found_key.objectid != objectid)
3502                         break;
3503
3504                 found_key.offset = 0;
3505                 found_key.type = 0;
3506                 ret = btrfs_bin_search(path->nodes[0], &found_key, 0,
3507                                        &start_slot);
3508
3509                 ret = btrfs_del_items(trans, log, path, start_slot,
3510                                       path->slots[0] - start_slot + 1);
3511                 /*
3512                  * If start slot isn't 0 then we don't need to re-search, we've
3513                  * found the last guy with the objectid in this tree.
3514                  */
3515                 if (ret || start_slot != 0)
3516                         break;
3517                 btrfs_release_path(path);
3518         }
3519         btrfs_release_path(path);
3520         if (ret > 0)
3521                 ret = 0;
3522         return ret;
3523 }
3524
3525 static void fill_inode_item(struct btrfs_trans_handle *trans,
3526                             struct extent_buffer *leaf,
3527                             struct btrfs_inode_item *item,
3528                             struct inode *inode, int log_inode_only,
3529                             u64 logged_isize)
3530 {
3531         struct btrfs_map_token token;
3532
3533         btrfs_init_map_token(&token);
3534
3535         if (log_inode_only) {
3536                 /* set the generation to zero so the recover code
3537                  * can tell the difference between an logging
3538                  * just to say 'this inode exists' and a logging
3539                  * to say 'update this inode with these values'
3540                  */
3541                 btrfs_set_token_inode_generation(leaf, item, 0, &token);
3542                 btrfs_set_token_inode_size(leaf, item, logged_isize, &token);
3543         } else {
3544                 btrfs_set_token_inode_generation(leaf, item,
3545                                                  BTRFS_I(inode)->generation,
3546                                                  &token);
3547                 btrfs_set_token_inode_size(leaf, item, inode->i_size, &token);
3548         }
3549
3550         btrfs_set_token_inode_uid(leaf, item, i_uid_read(inode), &token);
3551         btrfs_set_token_inode_gid(leaf, item, i_gid_read(inode), &token);
3552         btrfs_set_token_inode_mode(leaf, item, inode->i_mode, &token);
3553         btrfs_set_token_inode_nlink(leaf, item, inode->i_nlink, &token);
3554
3555         btrfs_set_token_timespec_sec(leaf, &item->atime,
3556                                      inode->i_atime.tv_sec, &token);
3557         btrfs_set_token_timespec_nsec(leaf, &item->atime,
3558                                       inode->i_atime.tv_nsec, &token);
3559
3560         btrfs_set_token_timespec_sec(leaf, &item->mtime,
3561                                      inode->i_mtime.tv_sec, &token);
3562         btrfs_set_token_timespec_nsec(leaf, &item->mtime,
3563                                       inode->i_mtime.tv_nsec, &token);
3564
3565         btrfs_set_token_timespec_sec(leaf, &item->ctime,
3566                                      inode->i_ctime.tv_sec, &token);
3567         btrfs_set_token_timespec_nsec(leaf, &item->ctime,
3568                                       inode->i_ctime.tv_nsec, &token);
3569
3570         btrfs_set_token_inode_nbytes(leaf, item, inode_get_bytes(inode),
3571                                      &token);
3572
3573         btrfs_set_token_inode_sequence(leaf, item, inode->i_version, &token);
3574         btrfs_set_token_inode_transid(leaf, item, trans->transid, &token);
3575         btrfs_set_token_inode_rdev(leaf, item, inode->i_rdev, &token);
3576         btrfs_set_token_inode_flags(leaf, item, BTRFS_I(inode)->flags, &token);
3577         btrfs_set_token_inode_block_group(leaf, item, 0, &token);
3578 }
3579
3580 static int log_inode_item(struct btrfs_trans_handle *trans,
3581                           struct btrfs_root *log, struct btrfs_path *path,
3582                           struct inode *inode)
3583 {
3584         struct btrfs_inode_item *inode_item;
3585         int ret;
3586
3587         ret = btrfs_insert_empty_item(trans, log, path,
3588                                       &BTRFS_I(inode)->location,
3589                                       sizeof(*inode_item));
3590         if (ret && ret != -EEXIST)
3591                 return ret;
3592         inode_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
3593                                     struct btrfs_inode_item);
3594         fill_inode_item(trans, path->nodes[0], inode_item, inode, 0, 0);
3595         btrfs_release_path(path);
3596         return 0;
3597 }
3598
3599 static noinline int copy_items(struct btrfs_trans_handle *trans,
3600                                struct inode *inode,
3601                                struct btrfs_path *dst_path,
3602                                struct btrfs_path *src_path, u64 *last_extent,
3603                                int start_slot, int nr, int inode_only,
3604                                u64 logged_isize)
3605 {
3606         unsigned long src_offset;
3607         unsigned long dst_offset;
3608         struct btrfs_root *log = BTRFS_I(inode)->root->log_root;
3609         struct btrfs_file_extent_item *extent;
3610         struct btrfs_inode_item *inode_item;
3611         struct extent_buffer *src = src_path->nodes[0];
3612         struct btrfs_key first_key, last_key, key;
3613         int ret;
3614         struct btrfs_key *ins_keys;
3615         u32 *ins_sizes;
3616         char *ins_data;
3617         int i;
3618         struct list_head ordered_sums;
3619         int skip_csum = BTRFS_I(inode)->flags & BTRFS_INODE_NODATASUM;
3620         bool has_extents = false;
3621         bool need_find_last_extent = true;
3622         bool done = false;
3623
3624         INIT_LIST_HEAD(&ordered_sums);
3625
3626         ins_data = kmalloc(nr * sizeof(struct btrfs_key) +
3627                            nr * sizeof(u32), GFP_NOFS);
3628         if (!ins_data)
3629                 return -ENOMEM;
3630
3631         first_key.objectid = (u64)-1;
3632
3633         ins_sizes = (u32 *)ins_data;
3634         ins_keys = (struct btrfs_key *)(ins_data + nr * sizeof(u32));
3635
3636         for (i = 0; i < nr; i++) {
3637                 ins_sizes[i] = btrfs_item_size_nr(src, i + start_slot);
3638                 btrfs_item_key_to_cpu(src, ins_keys + i, i + start_slot);
3639         }
3640         ret = btrfs_insert_empty_items(trans, log, dst_path,
3641                                        ins_keys, ins_sizes, nr);
3642         if (ret) {
3643                 kfree(ins_data);
3644                 return ret;
3645         }
3646
3647         for (i = 0; i < nr; i++, dst_path->slots[0]++) {
3648                 dst_offset = btrfs_item_ptr_offset(dst_path->nodes[0],
3649                                                    dst_path->slots[0]);
3650
3651                 src_offset = btrfs_item_ptr_offset(src, start_slot + i);
3652
3653                 if ((i == (nr - 1)))
3654                         last_key = ins_keys[i];
3655
3656                 if (ins_keys[i].type == BTRFS_INODE_ITEM_KEY) {
3657                         inode_item = btrfs_item_ptr(dst_path->nodes[0],
3658                                                     dst_path->slots[0],
3659                                                     struct btrfs_inode_item);
3660                         fill_inode_item(trans, dst_path->nodes[0], inode_item,
3661                                         inode, inode_only == LOG_INODE_EXISTS,
3662                                         logged_isize);
3663                 } else {
3664                         copy_extent_buffer(dst_path->nodes[0], src, dst_offset,
3665                                            src_offset, ins_sizes[i]);
3666                 }
3667
3668                 /*
3669                  * We set need_find_last_extent here in case we know we were
3670                  * processing other items and then walk into the first extent in
3671                  * the inode.  If we don't hit an extent then nothing changes,
3672                  * we'll do the last search the next time around.
3673                  */
3674                 if (ins_keys[i].type == BTRFS_EXTENT_DATA_KEY) {
3675                         has_extents = true;
3676                         if (first_key.objectid == (u64)-1)
3677                                 first_key = ins_keys[i];
3678                 } else {
3679                         need_find_last_extent = false;
3680                 }
3681
3682                 /* take a reference on file data extents so that truncates
3683                  * or deletes of this inode don't have to relog the inode
3684                  * again
3685                  */
3686                 if (ins_keys[i].type == BTRFS_EXTENT_DATA_KEY &&
3687                     !skip_csum) {
3688                         int found_type;
3689                         extent = btrfs_item_ptr(src, start_slot + i,
3690                                                 struct btrfs_file_extent_item);
3691
3692                         if (btrfs_file_extent_generation(src, extent) < trans->transid)
3693                                 continue;
3694
3695                         found_type = btrfs_file_extent_type(src, extent);
3696                         if (found_type == BTRFS_FILE_EXTENT_REG) {
3697                                 u64 ds, dl, cs, cl;
3698                                 ds = btrfs_file_extent_disk_bytenr(src,
3699                                                                 extent);
3700                                 /* ds == 0 is a hole */
3701                                 if (ds == 0)
3702                                         continue;
3703
3704                                 dl = btrfs_file_extent_disk_num_bytes(src,
3705                                                                 extent);
3706                                 cs = btrfs_file_extent_offset(src, extent);
3707                                 cl = btrfs_file_extent_num_bytes(src,
3708                                                                 extent);
3709                                 if (btrfs_file_extent_compression(src,
3710                                                                   extent)) {
3711                                         cs = 0;
3712                                         cl = dl;
3713                                 }
3714
3715                                 ret = btrfs_lookup_csums_range(
3716                                                 log->fs_info->csum_root,
3717                                                 ds + cs, ds + cs + cl - 1,
3718                                                 &ordered_sums, 0);
3719                                 if (ret) {
3720                                         btrfs_release_path(dst_path);
3721                                         kfree(ins_data);
3722                                         return ret;
3723                                 }
3724                         }
3725                 }
3726         }
3727
3728         btrfs_mark_buffer_dirty(dst_path->nodes[0]);
3729         btrfs_release_path(dst_path);
3730         kfree(ins_data);
3731
3732         /*
3733          * we have to do this after the loop above to avoid changing the
3734          * log tree while trying to change the log tree.
3735          */
3736         ret = 0;
3737         while (!list_empty(&ordered_sums)) {
3738                 struct btrfs_ordered_sum *sums = list_entry(ordered_sums.next,
3739                                                    struct btrfs_ordered_sum,
3740                                                    list);
3741                 if (!ret)
3742                         ret = btrfs_csum_file_blocks(trans, log, sums);
3743                 list_del(&sums->list);
3744                 kfree(sums);
3745         }
3746
3747         if (!has_extents)
3748                 return ret;
3749
3750         if (need_find_last_extent && *last_extent == first_key.offset) {
3751                 /*
3752                  * We don't have any leafs between our current one and the one
3753                  * we processed before that can have file extent items for our
3754                  * inode (and have a generation number smaller than our current
3755                  * transaction id).
3756                  */
3757                 need_find_last_extent = false;
3758         }
3759
3760         /*
3761          * Because we use btrfs_search_forward we could skip leaves that were
3762          * not modified and then assume *last_extent is valid when it really
3763          * isn't.  So back up to the previous leaf and read the end of the last
3764          * extent before we go and fill in holes.
3765          */
3766         if (need_find_last_extent) {
3767                 u64 len;
3768
3769                 ret = btrfs_prev_leaf(BTRFS_I(inode)->root, src_path);
3770                 if (ret < 0)
3771                         return ret;
3772                 if (ret)
3773                         goto fill_holes;
3774                 if (src_path->slots[0])
3775                         src_path->slots[0]--;
3776                 src = src_path->nodes[0];
3777                 btrfs_item_key_to_cpu(src, &key, src_path->slots[0]);
3778                 if (key.objectid != btrfs_ino(inode) ||
3779                     key.type != BTRFS_EXTENT_DATA_KEY)
3780                         goto fill_holes;
3781                 extent = btrfs_item_ptr(src, src_path->slots[0],
3782                                         struct btrfs_file_extent_item);
3783                 if (btrfs_file_extent_type(src, extent) ==
3784                     BTRFS_FILE_EXTENT_INLINE) {
3785                         len = btrfs_file_extent_inline_len(src,
3786                                                            src_path->slots[0],
3787                                                            extent);
3788                         *last_extent = ALIGN(key.offset + len,
3789                                              log->sectorsize);
3790                 } else {
3791                         len = btrfs_file_extent_num_bytes(src, extent);
3792                         *last_extent = key.offset + len;
3793                 }
3794         }
3795 fill_holes:
3796         /* So we did prev_leaf, now we need to move to the next leaf, but a few
3797          * things could have happened
3798          *
3799          * 1) A merge could have happened, so we could currently be on a leaf
3800          * that holds what we were copying in the first place.
3801          * 2) A split could have happened, and now not all of the items we want
3802          * are on the same leaf.
3803          *
3804          * So we need to adjust how we search for holes, we need to drop the
3805          * path and re-search for the first extent key we found, and then walk
3806          * forward until we hit the last one we copied.
3807          */
3808         if (need_find_last_extent) {
3809                 /* btrfs_prev_leaf could return 1 without releasing the path */
3810                 btrfs_release_path(src_path);
3811                 ret = btrfs_search_slot(NULL, BTRFS_I(inode)->root, &first_key,
3812                                         src_path, 0, 0);
3813                 if (ret < 0)
3814                         return ret;
3815                 ASSERT(ret == 0);
3816                 src = src_path->nodes[0];
3817                 i = src_path->slots[0];
3818         } else {
3819                 i = start_slot;
3820         }
3821
3822         /*
3823          * Ok so here we need to go through and fill in any holes we may have
3824          * to make sure that holes are punched for those areas in case they had
3825          * extents previously.
3826          */
3827         while (!done) {
3828                 u64 offset, len;
3829                 u64 extent_end;
3830
3831                 if (i >= btrfs_header_nritems(src_path->nodes[0])) {
3832                         ret = btrfs_next_leaf(BTRFS_I(inode)->root, src_path);
3833                         if (ret < 0)
3834                                 return ret;
3835                         ASSERT(ret == 0);
3836                         src = src_path->nodes[0];
3837                         i = 0;
3838                         need_find_last_extent = true;
3839                 }
3840
3841                 btrfs_item_key_to_cpu(src, &key, i);
3842                 if (!btrfs_comp_cpu_keys(&key, &last_key))
3843                         done = true;
3844                 if (key.objectid != btrfs_ino(inode) ||
3845                     key.type != BTRFS_EXTENT_DATA_KEY) {
3846                         i++;
3847                         continue;
3848                 }
3849                 extent = btrfs_item_ptr(src, i, struct btrfs_file_extent_item);
3850                 if (btrfs_file_extent_type(src, extent) ==
3851                     BTRFS_FILE_EXTENT_INLINE) {
3852                         len = btrfs_file_extent_inline_len(src, i, extent);
3853                         extent_end = ALIGN(key.offset + len, log->sectorsize);
3854                 } else {
3855                         len = btrfs_file_extent_num_bytes(src, extent);
3856                         extent_end = key.offset + len;
3857                 }
3858                 i++;
3859
3860                 if (*last_extent == key.offset) {
3861                         *last_extent = extent_end;
3862                         continue;
3863                 }
3864                 offset = *last_extent;
3865                 len = key.offset - *last_extent;
3866                 ret = btrfs_insert_file_extent(trans, log, btrfs_ino(inode),
3867                                                offset, 0, 0, len, 0, len, 0,
3868                                                0, 0);
3869                 if (ret)
3870                         break;
3871                 *last_extent = extent_end;
3872         }
3873         /*
3874          * Need to let the callers know we dropped the path so they should
3875          * re-search.
3876          */
3877         if (!ret && need_find_last_extent)
3878                 ret = 1;
3879         return ret;
3880 }
3881
3882 static int extent_cmp(void *priv, struct list_head *a, struct list_head *b)
3883 {
3884         struct extent_map *em1, *em2;
3885
3886         em1 = list_entry(a, struct extent_map, list);
3887         em2 = list_entry(b, struct extent_map, list);
3888
3889         if (em1->start < em2->start)
3890                 return -1;
3891         else if (em1->start > em2->start)
3892                 return 1;
3893         return 0;
3894 }
3895
3896 static int wait_ordered_extents(struct btrfs_trans_handle *trans,
3897                                 struct inode *inode,
3898                                 struct btrfs_root *root,
3899                                 const struct extent_map *em,
3900                                 const struct list_head *logged_list,
3901                                 bool *ordered_io_error)
3902 {
3903         struct btrfs_ordered_extent *ordered;
3904         struct btrfs_root *log = root->log_root;
3905         u64 mod_start = em->mod_start;
3906         u64 mod_len = em->mod_len;
3907         const bool skip_csum = BTRFS_I(inode)->flags & BTRFS_INODE_NODATASUM;
3908         u64 csum_offset;
3909         u64 csum_len;
3910         LIST_HEAD(ordered_sums);
3911         int ret = 0;
3912
3913         *ordered_io_error = false;
3914
3915         if (test_bit(EXTENT_FLAG_PREALLOC, &em->flags) ||
3916             em->block_start == EXTENT_MAP_HOLE)
3917                 return 0;
3918
3919         /*
3920          * Wait far any ordered extent that covers our extent map. If it
3921          * finishes without an error, first check and see if our csums are on
3922          * our outstanding ordered extents.
3923          */
3924         list_for_each_entry(ordered, logged_list, log_list) {
3925                 struct btrfs_ordered_sum *sum;
3926
3927                 if (!mod_len)
3928                         break;
3929
3930                 if (ordered->file_offset + ordered->len <= mod_start ||
3931                     mod_start + mod_len <= ordered->file_offset)
3932                         continue;
3933
3934                 if (!test_bit(BTRFS_ORDERED_IO_DONE, &ordered->flags) &&
3935                     !test_bit(BTRFS_ORDERED_IOERR, &ordered->flags) &&
3936                     !test_bit(BTRFS_ORDERED_DIRECT, &ordered->flags)) {
3937                         const u64 start = ordered->file_offset;
3938                         const u64 end = ordered->file_offset + ordered->len - 1;
3939
3940                         WARN_ON(ordered->inode != inode);
3941                         filemap_fdatawrite_range(inode->i_mapping, start, end);
3942                 }
3943
3944                 wait_event(ordered->wait,
3945                            (test_bit(BTRFS_ORDERED_IO_DONE, &ordered->flags) ||
3946                             test_bit(BTRFS_ORDERED_IOERR, &ordered->flags)));
3947
3948                 if (test_bit(BTRFS_ORDERED_IOERR, &ordered->flags)) {
3949                         /*
3950                          * Clear the AS_EIO/AS_ENOSPC flags from the inode's
3951                          * i_mapping flags, so that the next fsync won't get
3952                          * an outdated io error too.
3953                          */
3954                         btrfs_inode_check_errors(inode);
3955                         *ordered_io_error = true;
3956                         break;
3957                 }
3958                 /*
3959                  * We are going to copy all the csums on this ordered extent, so
3960                  * go ahead and adjust mod_start and mod_len in case this
3961                  * ordered extent has already been logged.
3962                  */
3963                 if (ordered->file_offset > mod_start) {
3964                         if (ordered->file_offset + ordered->len >=
3965                             mod_start + mod_len)
3966                                 mod_len = ordered->file_offset - mod_start;
3967                         /*
3968                          * If we have this case
3969                          *
3970                          * |--------- logged extent ---------|
3971                          *       |----- ordered extent ----|
3972                          *
3973                          * Just don't mess with mod_start and mod_len, we'll
3974                          * just end up logging more csums than we need and it
3975                          * will be ok.
3976                          */
3977                 } else {
3978                         if (ordered->file_offset + ordered->len <
3979                             mod_start + mod_len) {
3980                                 mod_len = (mod_start + mod_len) -
3981                                         (ordered->file_offset + ordered->len);
3982                                 mod_start = ordered->file_offset +
3983                                         ordered->len;
3984                         } else {
3985                                 mod_len = 0;
3986                         }
3987                 }
3988
3989                 if (skip_csum)
3990                         continue;
3991
3992                 /*
3993                  * To keep us from looping for the above case of an ordered
3994                  * extent that falls inside of the logged extent.
3995                  */
3996                 if (test_and_set_bit(BTRFS_ORDERED_LOGGED_CSUM,
3997                                      &ordered->flags))
3998                         continue;
3999
4000                 list_for_each_entry(sum, &ordered->list, list) {
4001                         ret = btrfs_csum_file_blocks(trans, log, sum);
4002                         if (ret)
4003                                 break;
4004                 }
4005         }
4006
4007         if (*ordered_io_error || !mod_len || ret || skip_csum)
4008                 return ret;
4009
4010         if (em->compress_type) {
4011                 csum_offset = 0;
4012                 csum_len = max(em->block_len, em->orig_block_len);
4013         } else {
4014                 csum_offset = mod_start - em->start;
4015                 csum_len = mod_len;
4016         }
4017
4018         /* block start is already adjusted for the file extent offset. */
4019         ret = btrfs_lookup_csums_range(log->fs_info->csum_root,
4020                                        em->block_start + csum_offset,
4021                                        em->block_start + csum_offset +
4022                                        csum_len - 1, &ordered_sums, 0);
4023         if (ret)
4024                 return ret;
4025
4026         while (!list_empty(&ordered_sums)) {
4027                 struct btrfs_ordered_sum *sums = list_entry(ordered_sums.next,
4028                                                    struct btrfs_ordered_sum,
4029                                                    list);
4030                 if (!ret)
4031                         ret = btrfs_csum_file_blocks(trans, log, sums);
4032                 list_del(&sums->list);
4033                 kfree(sums);
4034         }
4035
4036         return ret;
4037 }
4038
4039 static int log_one_extent(struct btrfs_trans_handle *trans,
4040                           struct inode *inode, struct btrfs_root *root,
4041                           const struct extent_map *em,
4042                           struct btrfs_path *path,
4043                           const struct list_head *logged_list,
4044                           struct btrfs_log_ctx *ctx)
4045 {
4046         struct btrfs_root *log = root->log_root;
4047         struct btrfs_file_extent_item *fi;
4048         struct extent_buffer *leaf;
4049         struct btrfs_map_token token;
4050         struct btrfs_key key;
4051         u64 extent_offset = em->start - em->orig_start;
4052         u64 block_len;
4053         int ret;
4054         int extent_inserted = 0;
4055         bool ordered_io_err = false;
4056
4057         ret = wait_ordered_extents(trans, inode, root, em, logged_list,
4058                                    &ordered_io_err);
4059         if (ret)
4060                 return ret;
4061
4062         if (ordered_io_err) {
4063                 ctx->io_err = -EIO;
4064                 return 0;
4065         }
4066
4067         btrfs_init_map_token(&token);
4068
4069         ret = __btrfs_drop_extents(trans, log, inode, path, em->start,
4070                                    em->start + em->len, NULL, 0, 1,
4071                                    sizeof(*fi), &extent_inserted);
4072         if (ret)
4073                 return ret;
4074
4075         if (!extent_inserted) {
4076                 key.objectid = btrfs_ino(inode);
4077                 key.type = BTRFS_EXTENT_DATA_KEY;
4078                 key.offset = em->start;
4079
4080                 ret = btrfs_insert_empty_item(trans, log, path, &key,
4081                                               sizeof(*fi));
4082                 if (ret)
4083                         return ret;
4084         }
4085         leaf = path->nodes[0];
4086         fi = btrfs_item_ptr(leaf, path->slots[0],
4087                             struct btrfs_file_extent_item);
4088
4089         btrfs_set_token_file_extent_generation(leaf, fi, trans->transid,
4090                                                &token);
4091         if (test_bit(EXTENT_FLAG_PREALLOC, &em->flags))
4092                 btrfs_set_token_file_extent_type(leaf, fi,
4093                                                  BTRFS_FILE_EXTENT_PREALLOC,
4094                                                  &token);
4095         else
4096                 btrfs_set_token_file_extent_type(leaf, fi,
4097                                                  BTRFS_FILE_EXTENT_REG,
4098                                                  &token);
4099
4100         block_len = max(em->block_len, em->orig_block_len);
4101         if (em->compress_type != BTRFS_COMPRESS_NONE) {
4102                 btrfs_set_token_file_extent_disk_bytenr(leaf, fi,
4103                                                         em->block_start,
4104                                                         &token);
4105                 btrfs_set_token_file_extent_disk_num_bytes(leaf, fi, block_len,
4106                                                            &token);
4107         } else if (em->block_start < EXTENT_MAP_LAST_BYTE) {
4108                 btrfs_set_token_file_extent_disk_bytenr(leaf, fi,
4109                                                         em->block_start -
4110                                                         extent_offset, &token);
4111                 btrfs_set_token_file_extent_disk_num_bytes(leaf, fi, block_len,
4112                                                            &token);
4113         } else {
4114                 btrfs_set_token_file_extent_disk_bytenr(leaf, fi, 0, &token);
4115                 btrfs_set_token_file_extent_disk_num_bytes(leaf, fi, 0,
4116                                                            &token);
4117         }
4118
4119         btrfs_set_token_file_extent_offset(leaf, fi, extent_offset, &token);
4120         btrfs_set_token_file_extent_num_bytes(leaf, fi, em->len, &token);
4121         btrfs_set_token_file_extent_ram_bytes(leaf, fi, em->ram_bytes, &token);
4122         btrfs_set_token_file_extent_compression(leaf, fi, em->compress_type,
4123                                                 &token);
4124         btrfs_set_token_file_extent_encryption(leaf, fi, 0, &token);
4125         btrfs_set_token_file_extent_other_encoding(leaf, fi, 0, &token);
4126         btrfs_mark_buffer_dirty(leaf);
4127
4128         btrfs_release_path(path);
4129
4130         return ret;
4131 }
4132
4133 static int btrfs_log_changed_extents(struct btrfs_trans_handle *trans,
4134                                      struct btrfs_root *root,
4135                                      struct inode *inode,
4136                                      struct btrfs_path *path,
4137                                      struct list_head *logged_list,
4138                                      struct btrfs_log_ctx *ctx)
4139 {
4140         struct extent_map *em, *n;
4141         struct list_head extents;
4142         struct extent_map_tree *tree = &BTRFS_I(inode)->extent_tree;
4143         u64 test_gen;
4144         int ret = 0;
4145         int num = 0;
4146
4147         INIT_LIST_HEAD(&extents);
4148
4149         write_lock(&tree->lock);
4150         test_gen = root->fs_info->last_trans_committed;
4151
4152         list_for_each_entry_safe(em, n, &tree->modified_extents, list) {
4153                 list_del_init(&em->list);
4154
4155                 /*
4156                  * Just an arbitrary number, this can be really CPU intensive
4157                  * once we start getting a lot of extents, and really once we
4158                  * have a bunch of extents we just want to commit since it will
4159                  * be faster.
4160                  */
4161                 if (++num > 32768) {
4162                         list_del_init(&tree->modified_extents);
4163                         ret = -EFBIG;
4164                         goto process;
4165                 }
4166
4167                 if (em->generation <= test_gen)
4168                         continue;
4169                 /* Need a ref to keep it from getting evicted from cache */
4170                 atomic_inc(&em->refs);
4171                 set_bit(EXTENT_FLAG_LOGGING, &em->flags);
4172                 list_add_tail(&em->list, &extents);
4173                 num++;
4174         }
4175
4176         list_sort(NULL, &extents, extent_cmp);
4177
4178 process:
4179         while (!list_empty(&extents)) {
4180                 em = list_entry(extents.next, struct extent_map, list);
4181
4182                 list_del_init(&em->list);
4183
4184                 /*
4185                  * If we had an error we just need to delete everybody from our
4186                  * private list.
4187                  */
4188                 if (ret) {
4189                         clear_em_logging(tree, em);
4190                         free_extent_map(em);
4191                         continue;
4192                 }
4193
4194                 write_unlock(&tree->lock);
4195
4196                 ret = log_one_extent(trans, inode, root, em, path, logged_list,
4197                                      ctx);
4198                 write_lock(&tree->lock);
4199                 clear_em_logging(tree, em);
4200                 free_extent_map(em);
4201         }
4202         WARN_ON(!list_empty(&extents));
4203         write_unlock(&tree->lock);
4204
4205         btrfs_release_path(path);
4206         return ret;
4207 }
4208
4209 static int logged_inode_size(struct btrfs_root *log, struct inode *inode,
4210                              struct btrfs_path *path, u64 *size_ret)
4211 {
4212         struct btrfs_key key;
4213         int ret;
4214
4215         key.objectid = btrfs_ino(inode);
4216         key.type = BTRFS_INODE_ITEM_KEY;
4217         key.offset = 0;
4218
4219         ret = btrfs_search_slot(NULL, log, &key, path, 0, 0);
4220         if (ret < 0) {
4221                 return ret;
4222         } else if (ret > 0) {
4223                 *size_ret = 0;
4224         } else {
4225                 struct btrfs_inode_item *item;
4226
4227                 item = btrfs_item_ptr(path->nodes[0], path->slots[0],
4228                                       struct btrfs_inode_item);
4229                 *size_ret = btrfs_inode_size(path->nodes[0], item);
4230         }
4231
4232         btrfs_release_path(path);
4233         return 0;
4234 }
4235
4236 /*
4237  * At the moment we always log all xattrs. This is to figure out at log replay
4238  * time which xattrs must have their deletion replayed. If a xattr is missing
4239  * in the log tree and exists in the fs/subvol tree, we delete it. This is
4240  * because if a xattr is deleted, the inode is fsynced and a power failure
4241  * happens, causing the log to be replayed the next time the fs is mounted,
4242  * we want the xattr to not exist anymore (same behaviour as other filesystems
4243  * with a journal, ext3/4, xfs, f2fs, etc).
4244  */
4245 static int btrfs_log_all_xattrs(struct btrfs_trans_handle *trans,
4246                                 struct btrfs_root *root,
4247                                 struct inode *inode,
4248                                 struct btrfs_path *path,
4249                                 struct btrfs_path *dst_path)
4250 {
4251         int ret;
4252         struct btrfs_key key;
4253         const u64 ino = btrfs_ino(inode);
4254         int ins_nr = 0;
4255         int start_slot = 0;
4256
4257         key.objectid = ino;
4258         key.type = BTRFS_XATTR_ITEM_KEY;
4259         key.offset = 0;
4260
4261         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
4262         if (ret < 0)
4263                 return ret;
4264
4265         while (true) {
4266                 int slot = path->slots[0];
4267                 struct extent_buffer *leaf = path->nodes[0];
4268                 int nritems = btrfs_header_nritems(leaf);
4269
4270                 if (slot >= nritems) {
4271                         if (ins_nr > 0) {
4272                                 u64 last_extent = 0;
4273
4274                                 ret = copy_items(trans, inode, dst_path, path,
4275                                                  &last_extent, start_slot,
4276                                                  ins_nr, 1, 0);
4277                                 /* can't be 1, extent items aren't processed */
4278                                 ASSERT(ret <= 0);
4279                                 if (ret < 0)
4280                                         return ret;
4281                                 ins_nr = 0;
4282                         }
4283                         ret = btrfs_next_leaf(root, path);
4284                         if (ret < 0)
4285                                 return ret;
4286                         else if (ret > 0)
4287                                 break;
4288                         continue;
4289                 }
4290
4291                 btrfs_item_key_to_cpu(leaf, &key, slot);
4292                 if (key.objectid != ino || key.type != BTRFS_XATTR_ITEM_KEY)
4293                         break;
4294
4295                 if (ins_nr == 0)
4296                         start_slot = slot;
4297                 ins_nr++;
4298                 path->slots[0]++;
4299                 cond_resched();
4300         }
4301         if (ins_nr > 0) {
4302                 u64 last_extent = 0;
4303
4304                 ret = copy_items(trans, inode, dst_path, path,
4305                                  &last_extent, start_slot,
4306                                  ins_nr, 1, 0);
4307                 /* can't be 1, extent items aren't processed */
4308                 ASSERT(ret <= 0);
4309                 if (ret < 0)
4310                         return ret;
4311         }
4312
4313         return 0;
4314 }
4315
4316 /*
4317  * If the no holes feature is enabled we need to make sure any hole between the
4318  * last extent and the i_size of our inode is explicitly marked in the log. This
4319  * is to make sure that doing something like:
4320  *
4321  *      1) create file with 128Kb of data
4322  *      2) truncate file to 64Kb
4323  *      3) truncate file to 256Kb
4324  *      4) fsync file
4325  *      5) <crash/power failure>
4326  *      6) mount fs and trigger log replay
4327  *
4328  * Will give us a file with a size of 256Kb, the first 64Kb of data match what
4329  * the file had in its first 64Kb of data at step 1 and the last 192Kb of the
4330  * file correspond to a hole. The presence of explicit holes in a log tree is
4331  * what guarantees that log replay will remove/adjust file extent items in the
4332  * fs/subvol tree.
4333  *
4334  * Here we do not need to care about holes between extents, that is already done
4335  * by copy_items(). We also only need to do this in the full sync path, where we
4336  * lookup for extents from the fs/subvol tree only. In the fast path case, we
4337  * lookup the list of modified extent maps and if any represents a hole, we
4338  * insert a corresponding extent representing a hole in the log tree.
4339  */
4340 static int btrfs_log_trailing_hole(struct btrfs_trans_handle *trans,
4341                                    struct btrfs_root *root,
4342                                    struct inode *inode,
4343                                    struct btrfs_path *path)
4344 {
4345         int ret;
4346         struct btrfs_key key;
4347         u64 hole_start;
4348         u64 hole_size;
4349         struct extent_buffer *leaf;
4350         struct btrfs_root *log = root->log_root;
4351         const u64 ino = btrfs_ino(inode);
4352         const u64 i_size = i_size_read(inode);
4353
4354         if (!btrfs_fs_incompat(root->fs_info, NO_HOLES))
4355                 return 0;
4356
4357         key.objectid = ino;
4358         key.type = BTRFS_EXTENT_DATA_KEY;
4359         key.offset = (u64)-1;
4360
4361         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
4362         ASSERT(ret != 0);
4363         if (ret < 0)
4364                 return ret;
4365
4366         ASSERT(path->slots[0] > 0);
4367         path->slots[0]--;
4368         leaf = path->nodes[0];
4369         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
4370
4371         if (key.objectid != ino || key.type != BTRFS_EXTENT_DATA_KEY) {
4372                 /* inode does not have any extents */
4373                 hole_start = 0;
4374                 hole_size = i_size;
4375         } else {
4376                 struct btrfs_file_extent_item *extent;
4377                 u64 len;
4378
4379                 /*
4380                  * If there's an extent beyond i_size, an explicit hole was
4381                  * already inserted by copy_items().
4382                  */
4383                 if (key.offset >= i_size)
4384                         return 0;
4385
4386                 extent = btrfs_item_ptr(leaf, path->slots[0],
4387                                         struct btrfs_file_extent_item);
4388
4389                 if (btrfs_file_extent_type(leaf, extent) ==
4390                     BTRFS_FILE_EXTENT_INLINE) {
4391                         len = btrfs_file_extent_inline_len(leaf,
4392                                                            path->slots[0],
4393                                                            extent);
4394                         ASSERT(len == i_size);
4395                         return 0;
4396                 }
4397
4398                 len = btrfs_file_extent_num_bytes(leaf, extent);
4399                 /* Last extent goes beyond i_size, no need to log a hole. */
4400                 if (key.offset + len > i_size)
4401                         return 0;
4402                 hole_start = key.offset + len;
4403                 hole_size = i_size - hole_start;
4404         }
4405         btrfs_release_path(path);
4406
4407         /* Last extent ends at i_size. */
4408         if (hole_size == 0)
4409                 return 0;
4410
4411         hole_size = ALIGN(hole_size, root->sectorsize);
4412         ret = btrfs_insert_file_extent(trans, log, ino, hole_start, 0, 0,
4413                                        hole_size, 0, hole_size, 0, 0, 0);
4414         return ret;
4415 }
4416
4417 /*
4418  * When we are logging a new inode X, check if it doesn't have a reference that
4419  * matches the reference from some other inode Y created in a past transaction
4420  * and that was renamed in the current transaction. If we don't do this, then at
4421  * log replay time we can lose inode Y (and all its files if it's a directory):
4422  *
4423  * mkdir /mnt/x
4424  * echo "hello world" > /mnt/x/foobar
4425  * sync
4426  * mv /mnt/x /mnt/y
4427  * mkdir /mnt/x                 # or touch /mnt/x
4428  * xfs_io -c fsync /mnt/x
4429  * <power fail>
4430  * mount fs, trigger log replay
4431  *
4432  * After the log replay procedure, we would lose the first directory and all its
4433  * files (file foobar).
4434  * For the case where inode Y is not a directory we simply end up losing it:
4435  *
4436  * echo "123" > /mnt/foo
4437  * sync
4438  * mv /mnt/foo /mnt/bar
4439  * echo "abc" > /mnt/foo
4440  * xfs_io -c fsync /mnt/foo
4441  * <power fail>
4442  *
4443  * We also need this for cases where a snapshot entry is replaced by some other
4444  * entry (file or directory) otherwise we end up with an unreplayable log due to
4445  * attempts to delete the snapshot entry (entry of type BTRFS_ROOT_ITEM_KEY) as
4446  * if it were a regular entry:
4447  *
4448  * mkdir /mnt/x
4449  * btrfs subvolume snapshot /mnt /mnt/x/snap
4450  * btrfs subvolume delete /mnt/x/snap
4451  * rmdir /mnt/x
4452  * mkdir /mnt/x
4453  * fsync /mnt/x or fsync some new file inside it
4454  * <power fail>
4455  *
4456  * The snapshot delete, rmdir of x, mkdir of a new x and the fsync all happen in
4457  * the same transaction.
4458  */
4459 static int btrfs_check_ref_name_override(struct extent_buffer *eb,
4460                                          const int slot,
4461                                          const struct btrfs_key *key,
4462                                          struct inode *inode)
4463 {
4464         int ret;
4465         struct btrfs_path *search_path;
4466         char *name = NULL;
4467         u32 name_len = 0;
4468         u32 item_size = btrfs_item_size_nr(eb, slot);
4469         u32 cur_offset = 0;
4470         unsigned long ptr = btrfs_item_ptr_offset(eb, slot);
4471
4472         search_path = btrfs_alloc_path();
4473         if (!search_path)
4474                 return -ENOMEM;
4475         search_path->search_commit_root = 1;
4476         search_path->skip_locking = 1;
4477
4478         while (cur_offset < item_size) {
4479                 u64 parent;
4480                 u32 this_name_len;
4481                 u32 this_len;
4482                 unsigned long name_ptr;
4483                 struct btrfs_dir_item *di;
4484
4485                 if (key->type == BTRFS_INODE_REF_KEY) {
4486                         struct btrfs_inode_ref *iref;
4487
4488                         iref = (struct btrfs_inode_ref *)(ptr + cur_offset);
4489                         parent = key->offset;
4490                         this_name_len = btrfs_inode_ref_name_len(eb, iref);
4491                         name_ptr = (unsigned long)(iref + 1);
4492                         this_len = sizeof(*iref) + this_name_len;
4493                 } else {
4494                         struct btrfs_inode_extref *extref;
4495
4496                         extref = (struct btrfs_inode_extref *)(ptr +
4497                                                                cur_offset);
4498                         parent = btrfs_inode_extref_parent(eb, extref);
4499                         this_name_len = btrfs_inode_extref_name_len(eb, extref);
4500                         name_ptr = (unsigned long)&extref->name;
4501                         this_len = sizeof(*extref) + this_name_len;
4502                 }
4503
4504                 if (this_name_len > name_len) {
4505                         char *new_name;
4506
4507                         new_name = krealloc(name, this_name_len, GFP_NOFS);
4508                         if (!new_name) {
4509                                 ret = -ENOMEM;
4510                                 goto out;
4511                         }
4512                         name_len = this_name_len;
4513                         name = new_name;
4514                 }
4515
4516                 read_extent_buffer(eb, name, name_ptr, this_name_len);
4517                 di = btrfs_lookup_dir_item(NULL, BTRFS_I(inode)->root,
4518                                            search_path, parent,
4519                                            name, this_name_len, 0);
4520                 if (di && !IS_ERR(di)) {
4521                         ret = 1;
4522                         goto out;
4523                 } else if (IS_ERR(di)) {
4524                         ret = PTR_ERR(di);
4525                         goto out;
4526                 }
4527                 btrfs_release_path(search_path);
4528
4529                 cur_offset += this_len;
4530         }
4531         ret = 0;
4532 out:
4533         btrfs_free_path(search_path);
4534         kfree(name);
4535         return ret;
4536 }
4537
4538 /* log a single inode in the tree log.
4539  * At least one parent directory for this inode must exist in the tree
4540  * or be logged already.
4541  *
4542  * Any items from this inode changed by the current transaction are copied
4543  * to the log tree.  An extra reference is taken on any extents in this
4544  * file, allowing us to avoid a whole pile of corner cases around logging
4545  * blocks that have been removed from the tree.
4546  *
4547  * See LOG_INODE_ALL and related defines for a description of what inode_only
4548  * does.
4549  *
4550  * This handles both files and directories.
4551  */
4552 static int btrfs_log_inode(struct btrfs_trans_handle *trans,
4553                            struct btrfs_root *root, struct inode *inode,
4554                            int inode_only,
4555                            const loff_t start,
4556                            const loff_t end,
4557                            struct btrfs_log_ctx *ctx)
4558 {
4559         struct btrfs_path *path;
4560         struct btrfs_path *dst_path;
4561         struct btrfs_key min_key;
4562         struct btrfs_key max_key;
4563         struct btrfs_root *log = root->log_root;
4564         struct extent_buffer *src = NULL;
4565         LIST_HEAD(logged_list);
4566         u64 last_extent = 0;
4567         int err = 0;
4568         int ret;
4569         int nritems;
4570         int ins_start_slot = 0;
4571         int ins_nr;
4572         bool fast_search = false;
4573         u64 ino = btrfs_ino(inode);
4574         struct extent_map_tree *em_tree = &BTRFS_I(inode)->extent_tree;
4575         u64 logged_isize = 0;
4576         bool need_log_inode_item = true;
4577         bool xattrs_logged = false;
4578
4579         path = btrfs_alloc_path();
4580         if (!path)
4581                 return -ENOMEM;
4582         dst_path = btrfs_alloc_path();
4583         if (!dst_path) {
4584                 btrfs_free_path(path);
4585                 return -ENOMEM;
4586         }
4587
4588         min_key.objectid = ino;
4589         min_key.type = BTRFS_INODE_ITEM_KEY;
4590         min_key.offset = 0;
4591
4592         max_key.objectid = ino;
4593
4594
4595         /* today the code can only do partial logging of directories */
4596         if (S_ISDIR(inode->i_mode) ||
4597             (!test_bit(BTRFS_INODE_NEEDS_FULL_SYNC,
4598                        &BTRFS_I(inode)->runtime_flags) &&
4599              inode_only == LOG_INODE_EXISTS))
4600                 max_key.type = BTRFS_XATTR_ITEM_KEY;
4601         else
4602                 max_key.type = (u8)-1;
4603         max_key.offset = (u64)-1;
4604
4605         /*
4606          * Only run delayed items if we are a dir or a new file.
4607          * Otherwise commit the delayed inode only, which is needed in
4608          * order for the log replay code to mark inodes for link count
4609          * fixup (create temporary BTRFS_TREE_LOG_FIXUP_OBJECTID items).
4610          */
4611         if (S_ISDIR(inode->i_mode) ||
4612             BTRFS_I(inode)->generation > root->fs_info->last_trans_committed)
4613                 ret = btrfs_commit_inode_delayed_items(trans, inode);
4614         else
4615                 ret = btrfs_commit_inode_delayed_inode(inode);
4616
4617         if (ret) {
4618                 btrfs_free_path(path);
4619                 btrfs_free_path(dst_path);
4620                 return ret;
4621         }
4622
4623         mutex_lock(&BTRFS_I(inode)->log_mutex);
4624
4625         btrfs_get_logged_extents(inode, &logged_list, start, end);
4626
4627         /*
4628          * a brute force approach to making sure we get the most uptodate
4629          * copies of everything.
4630          */
4631         if (S_ISDIR(inode->i_mode)) {
4632                 int max_key_type = BTRFS_DIR_LOG_INDEX_KEY;
4633
4634                 if (inode_only == LOG_INODE_EXISTS)
4635                         max_key_type = BTRFS_XATTR_ITEM_KEY;
4636                 ret = drop_objectid_items(trans, log, path, ino, max_key_type);
4637         } else {
4638                 if (inode_only == LOG_INODE_EXISTS) {
4639                         /*
4640                          * Make sure the new inode item we write to the log has
4641                          * the same isize as the current one (if it exists).
4642                          * This is necessary to prevent data loss after log
4643                          * replay, and also to prevent doing a wrong expanding
4644                          * truncate - for e.g. create file, write 4K into offset
4645                          * 0, fsync, write 4K into offset 4096, add hard link,
4646                          * fsync some other file (to sync log), power fail - if
4647                          * we use the inode's current i_size, after log replay
4648                          * we get a 8Kb file, with the last 4Kb extent as a hole
4649                          * (zeroes), as if an expanding truncate happened,
4650                          * instead of getting a file of 4Kb only.
4651                          */
4652                         err = logged_inode_size(log, inode, path,
4653                                                 &logged_isize);
4654                         if (err)
4655                                 goto out_unlock;
4656                 }
4657                 if (test_bit(BTRFS_INODE_NEEDS_FULL_SYNC,
4658                              &BTRFS_I(inode)->runtime_flags)) {
4659                         if (inode_only == LOG_INODE_EXISTS) {
4660                                 max_key.type = BTRFS_XATTR_ITEM_KEY;
4661                                 ret = drop_objectid_items(trans, log, path, ino,
4662                                                           max_key.type);
4663                         } else {
4664                                 clear_bit(BTRFS_INODE_NEEDS_FULL_SYNC,
4665                                           &BTRFS_I(inode)->runtime_flags);
4666                                 clear_bit(BTRFS_INODE_COPY_EVERYTHING,
4667                                           &BTRFS_I(inode)->runtime_flags);
4668                                 while(1) {
4669                                         ret = btrfs_truncate_inode_items(trans,
4670                                                          log, inode, 0, 0);
4671                                         if (ret != -EAGAIN)
4672                                                 break;
4673                                 }
4674                         }
4675                 } else if (test_and_clear_bit(BTRFS_INODE_COPY_EVERYTHING,
4676                                               &BTRFS_I(inode)->runtime_flags) ||
4677                            inode_only == LOG_INODE_EXISTS) {
4678                         if (inode_only == LOG_INODE_ALL)
4679                                 fast_search = true;
4680                         max_key.type = BTRFS_XATTR_ITEM_KEY;
4681                         ret = drop_objectid_items(trans, log, path, ino,
4682                                                   max_key.type);
4683                 } else {
4684                         if (inode_only == LOG_INODE_ALL)
4685                                 fast_search = true;
4686                         goto log_extents;
4687                 }
4688
4689         }
4690         if (ret) {
4691                 err = ret;
4692                 goto out_unlock;
4693         }
4694
4695         while (1) {
4696                 ins_nr = 0;
4697                 ret = btrfs_search_forward(root, &min_key,
4698                                            path, trans->transid);
4699                 if (ret != 0)
4700                         break;
4701 again:
4702                 /* note, ins_nr might be > 0 here, cleanup outside the loop */
4703                 if (min_key.objectid != ino)
4704                         break;
4705                 if (min_key.type > max_key.type)
4706                         break;
4707
4708                 if (min_key.type == BTRFS_INODE_ITEM_KEY)
4709                         need_log_inode_item = false;
4710
4711                 if ((min_key.type == BTRFS_INODE_REF_KEY ||
4712                      min_key.type == BTRFS_INODE_EXTREF_KEY) &&
4713                     BTRFS_I(inode)->generation == trans->transid) {
4714                         ret = btrfs_check_ref_name_override(path->nodes[0],
4715                                                             path->slots[0],
4716                                                             &min_key, inode);
4717                         if (ret < 0) {
4718                                 err = ret;
4719                                 goto out_unlock;
4720                         } else if (ret > 0) {
4721                                 err = 1;
4722                                 btrfs_set_log_full_commit(root->fs_info, trans);
4723                                 goto out_unlock;
4724                         }
4725                 }
4726
4727                 /* Skip xattrs, we log them later with btrfs_log_all_xattrs() */
4728                 if (min_key.type == BTRFS_XATTR_ITEM_KEY) {
4729                         if (ins_nr == 0)
4730                                 goto next_slot;
4731                         ret = copy_items(trans, inode, dst_path, path,
4732                                          &last_extent, ins_start_slot,
4733                                          ins_nr, inode_only, logged_isize);
4734                         if (ret < 0) {
4735                                 err = ret;
4736                                 goto out_unlock;
4737                         }
4738                         ins_nr = 0;
4739                         if (ret) {
4740                                 btrfs_release_path(path);
4741                                 continue;
4742                         }
4743                         goto next_slot;
4744                 }
4745
4746                 src = path->nodes[0];
4747                 if (ins_nr && ins_start_slot + ins_nr == path->slots[0]) {
4748                         ins_nr++;
4749                         goto next_slot;
4750                 } else if (!ins_nr) {
4751                         ins_start_slot = path->slots[0];
4752                         ins_nr = 1;
4753                         goto next_slot;
4754                 }
4755
4756                 ret = copy_items(trans, inode, dst_path, path, &last_extent,
4757                                  ins_start_slot, ins_nr, inode_only,
4758                                  logged_isize);
4759                 if (ret < 0) {
4760                         err = ret;
4761                         goto out_unlock;
4762                 }
4763                 if (ret) {
4764                         ins_nr = 0;
4765                         btrfs_release_path(path);
4766                         continue;
4767                 }
4768                 ins_nr = 1;
4769                 ins_start_slot = path->slots[0];
4770 next_slot:
4771
4772                 nritems = btrfs_header_nritems(path->nodes[0]);
4773                 path->slots[0]++;
4774                 if (path->slots[0] < nritems) {
4775                         btrfs_item_key_to_cpu(path->nodes[0], &min_key,
4776                                               path->slots[0]);
4777                         goto again;
4778                 }
4779                 if (ins_nr) {
4780                         ret = copy_items(trans, inode, dst_path, path,
4781                                          &last_extent, ins_start_slot,
4782                                          ins_nr, inode_only, logged_isize);
4783                         if (ret < 0) {
4784                                 err = ret;
4785                                 goto out_unlock;
4786                         }
4787                         ret = 0;
4788                         ins_nr = 0;
4789                 }
4790                 btrfs_release_path(path);
4791
4792                 if (min_key.offset < (u64)-1) {
4793                         min_key.offset++;
4794                 } else if (min_key.type < max_key.type) {
4795                         min_key.type++;
4796                         min_key.offset = 0;
4797                 } else {
4798                         break;
4799                 }
4800         }
4801         if (ins_nr) {
4802                 ret = copy_items(trans, inode, dst_path, path, &last_extent,
4803                                  ins_start_slot, ins_nr, inode_only,
4804                                  logged_isize);
4805                 if (ret < 0) {
4806                         err = ret;
4807                         goto out_unlock;
4808                 }
4809                 ret = 0;
4810                 ins_nr = 0;
4811         }
4812
4813         btrfs_release_path(path);
4814         btrfs_release_path(dst_path);
4815         err = btrfs_log_all_xattrs(trans, root, inode, path, dst_path);
4816         if (err)
4817                 goto out_unlock;
4818         xattrs_logged = true;
4819         if (max_key.type >= BTRFS_EXTENT_DATA_KEY && !fast_search) {
4820                 btrfs_release_path(path);
4821                 btrfs_release_path(dst_path);
4822                 err = btrfs_log_trailing_hole(trans, root, inode, path);
4823                 if (err)
4824                         goto out_unlock;
4825         }
4826 log_extents:
4827         btrfs_release_path(path);
4828         btrfs_release_path(dst_path);
4829         if (need_log_inode_item) {
4830                 err = log_inode_item(trans, log, dst_path, inode);
4831                 if (!err && !xattrs_logged) {
4832                         err = btrfs_log_all_xattrs(trans, root, inode, path,
4833                                                    dst_path);
4834                         btrfs_release_path(path);
4835                 }
4836                 if (err)
4837                         goto out_unlock;
4838         }
4839         if (fast_search) {
4840                 /*
4841                  * Some ordered extents started by fsync might have completed
4842                  * before we collected the ordered extents in logged_list, which
4843                  * means they're gone, not in our logged_list nor in the inode's
4844                  * ordered tree. We want the application/user space to know an
4845                  * error happened while attempting to persist file data so that
4846                  * it can take proper action. If such error happened, we leave
4847                  * without writing to the log tree and the fsync must report the
4848                  * file data write error and not commit the current transaction.
4849                  */
4850                 err = btrfs_inode_check_errors(inode);
4851                 if (err) {
4852                         ctx->io_err = err;
4853                         goto out_unlock;
4854                 }
4855                 ret = btrfs_log_changed_extents(trans, root, inode, dst_path,
4856                                                 &logged_list, ctx);
4857                 if (ret) {
4858                         err = ret;
4859                         goto out_unlock;
4860                 }
4861         } else if (inode_only == LOG_INODE_ALL) {
4862                 struct extent_map *em, *n;
4863
4864                 write_lock(&em_tree->lock);
4865                 /*
4866                  * We can't just remove every em if we're called for a ranged
4867                  * fsync - that is, one that doesn't cover the whole possible
4868                  * file range (0 to LLONG_MAX). This is because we can have
4869                  * em's that fall outside the range we're logging and therefore
4870                  * their ordered operations haven't completed yet
4871                  * (btrfs_finish_ordered_io() not invoked yet). This means we
4872                  * didn't get their respective file extent item in the fs/subvol
4873                  * tree yet, and need to let the next fast fsync (one which
4874                  * consults the list of modified extent maps) find the em so
4875                  * that it logs a matching file extent item and waits for the
4876                  * respective ordered operation to complete (if it's still
4877                  * running).
4878                  *
4879                  * Removing every em outside the range we're logging would make
4880                  * the next fast fsync not log their matching file extent items,
4881                  * therefore making us lose data after a log replay.
4882                  */
4883                 list_for_each_entry_safe(em, n, &em_tree->modified_extents,
4884                                          list) {
4885                         const u64 mod_end = em->mod_start + em->mod_len - 1;
4886
4887                         if (em->mod_start >= start && mod_end <= end)
4888                                 list_del_init(&em->list);
4889                 }
4890                 write_unlock(&em_tree->lock);
4891         }
4892
4893         if (inode_only == LOG_INODE_ALL && S_ISDIR(inode->i_mode)) {
4894                 ret = log_directory_changes(trans, root, inode, path, dst_path,
4895                                             ctx);
4896                 if (ret) {
4897                         err = ret;
4898                         goto out_unlock;
4899                 }
4900         }
4901
4902         spin_lock(&BTRFS_I(inode)->lock);
4903         BTRFS_I(inode)->logged_trans = trans->transid;
4904         BTRFS_I(inode)->last_log_commit = BTRFS_I(inode)->last_sub_trans;
4905         spin_unlock(&BTRFS_I(inode)->lock);
4906 out_unlock:
4907         if (unlikely(err))
4908                 btrfs_put_logged_extents(&logged_list);
4909         else
4910                 btrfs_submit_logged_extents(&logged_list, log);
4911         mutex_unlock(&BTRFS_I(inode)->log_mutex);
4912
4913         btrfs_free_path(path);
4914         btrfs_free_path(dst_path);
4915         return err;
4916 }
4917
4918 /*
4919  * follow the dentry parent pointers up the chain and see if any
4920  * of the directories in it require a full commit before they can
4921  * be logged.  Returns zero if nothing special needs to be done or 1 if
4922  * a full commit is required.
4923  */
4924 static noinline int check_parent_dirs_for_sync(struct btrfs_trans_handle *trans,
4925                                                struct inode *inode,
4926                                                struct dentry *parent,
4927                                                struct super_block *sb,
4928                                                u64 last_committed)
4929 {
4930         int ret = 0;
4931         struct btrfs_root *root;
4932         struct dentry *old_parent = NULL;
4933         struct inode *orig_inode = inode;
4934
4935         /*
4936          * for regular files, if its inode is already on disk, we don't
4937          * have to worry about the parents at all.  This is because
4938          * we can use the last_unlink_trans field to record renames
4939          * and other fun in this file.
4940          */
4941         if (S_ISREG(inode->i_mode) &&
4942             BTRFS_I(inode)->generation <= last_committed &&
4943             BTRFS_I(inode)->last_unlink_trans <= last_committed)
4944                         goto out;
4945
4946         if (!S_ISDIR(inode->i_mode)) {
4947                 if (!parent || d_really_is_negative(parent) || sb != d_inode(parent)->i_sb)
4948                         goto out;
4949                 inode = d_inode(parent);
4950         }
4951
4952         while (1) {
4953                 /*
4954                  * If we are logging a directory then we start with our inode,
4955                  * not our parents inode, so we need to skipp setting the
4956                  * logged_trans so that further down in the log code we don't
4957                  * think this inode has already been logged.
4958                  */
4959                 if (inode != orig_inode)
4960                         BTRFS_I(inode)->logged_trans = trans->transid;
4961                 smp_mb();
4962
4963                 if (BTRFS_I(inode)->last_unlink_trans > last_committed) {
4964                         root = BTRFS_I(inode)->root;
4965
4966                         /*
4967                          * make sure any commits to the log are forced
4968                          * to be full commits
4969                          */
4970                         btrfs_set_log_full_commit(root->fs_info, trans);
4971                         ret = 1;
4972                         break;
4973                 }
4974
4975                 if (!parent || d_really_is_negative(parent) || sb != d_inode(parent)->i_sb)
4976                         break;
4977
4978                 if (IS_ROOT(parent))
4979                         break;
4980
4981                 parent = dget_parent(parent);
4982                 dput(old_parent);
4983                 old_parent = parent;
4984                 inode = d_inode(parent);
4985
4986         }
4987         dput(old_parent);
4988 out:
4989         return ret;
4990 }
4991
4992 struct btrfs_dir_list {
4993         u64 ino;
4994         struct list_head list;
4995 };
4996
4997 /*
4998  * Log the inodes of the new dentries of a directory. See log_dir_items() for
4999  * details about the why it is needed.
5000  * This is a recursive operation - if an existing dentry corresponds to a
5001  * directory, that directory's new entries are logged too (same behaviour as
5002  * ext3/4, xfs, f2fs, reiserfs, nilfs2). Note that when logging the inodes
5003  * the dentries point to we do not lock their i_mutex, otherwise lockdep
5004  * complains about the following circular lock dependency / possible deadlock:
5005  *
5006  *        CPU0                                        CPU1
5007  *        ----                                        ----
5008  * lock(&type->i_mutex_dir_key#3/2);
5009  *                                            lock(sb_internal#2);
5010  *                                            lock(&type->i_mutex_dir_key#3/2);
5011  * lock(&sb->s_type->i_mutex_key#14);
5012  *
5013  * Where sb_internal is the lock (a counter that works as a lock) acquired by
5014  * sb_start_intwrite() in btrfs_start_transaction().
5015  * Not locking i_mutex of the inodes is still safe because:
5016  *
5017  * 1) For regular files we log with a mode of LOG_INODE_EXISTS. It's possible
5018  *    that while logging the inode new references (names) are added or removed
5019  *    from the inode, leaving the logged inode item with a link count that does
5020  *    not match the number of logged inode reference items. This is fine because
5021  *    at log replay time we compute the real number of links and correct the
5022  *    link count in the inode item (see replay_one_buffer() and
5023  *    link_to_fixup_dir());
5024  *
5025  * 2) For directories we log with a mode of LOG_INODE_ALL. It's possible that
5026  *    while logging the inode's items new items with keys BTRFS_DIR_ITEM_KEY and
5027  *    BTRFS_DIR_INDEX_KEY are added to fs/subvol tree and the logged inode item
5028  *    has a size that doesn't match the sum of the lengths of all the logged
5029  *    names. This does not result in a problem because if a dir_item key is
5030  *    logged but its matching dir_index key is not logged, at log replay time we
5031  *    don't use it to replay the respective name (see replay_one_name()). On the
5032  *    other hand if only the dir_index key ends up being logged, the respective
5033  *    name is added to the fs/subvol tree with both the dir_item and dir_index
5034  *    keys created (see replay_one_name()).
5035  *    The directory's inode item with a wrong i_size is not a problem as well,
5036  *    since we don't use it at log replay time to set the i_size in the inode
5037  *    item of the fs/subvol tree (see overwrite_item()).
5038  */
5039 static int log_new_dir_dentries(struct btrfs_trans_handle *trans,
5040                                 struct btrfs_root *root,
5041                                 struct inode *start_inode,
5042                                 struct btrfs_log_ctx *ctx)
5043 {
5044         struct btrfs_root *log = root->log_root;
5045         struct btrfs_path *path;
5046         LIST_HEAD(dir_list);
5047         struct btrfs_dir_list *dir_elem;
5048         int ret = 0;
5049
5050         path = btrfs_alloc_path();
5051         if (!path)
5052                 return -ENOMEM;
5053
5054         dir_elem = kmalloc(sizeof(*dir_elem), GFP_NOFS);
5055         if (!dir_elem) {
5056                 btrfs_free_path(path);
5057                 return -ENOMEM;
5058         }
5059         dir_elem->ino = btrfs_ino(start_inode);
5060         list_add_tail(&dir_elem->list, &dir_list);
5061
5062         while (!list_empty(&dir_list)) {
5063                 struct extent_buffer *leaf;
5064                 struct btrfs_key min_key;
5065                 int nritems;
5066                 int i;
5067
5068                 dir_elem = list_first_entry(&dir_list, struct btrfs_dir_list,
5069                                             list);
5070                 if (ret)
5071                         goto next_dir_inode;
5072
5073                 min_key.objectid = dir_elem->ino;
5074                 min_key.type = BTRFS_DIR_ITEM_KEY;
5075                 min_key.offset = 0;
5076 again:
5077                 btrfs_release_path(path);
5078                 ret = btrfs_search_forward(log, &min_key, path, trans->transid);
5079                 if (ret < 0) {
5080                         goto next_dir_inode;
5081                 } else if (ret > 0) {
5082                         ret = 0;
5083                         goto next_dir_inode;
5084                 }
5085
5086 process_leaf:
5087                 leaf = path->nodes[0];
5088                 nritems = btrfs_header_nritems(leaf);
5089                 for (i = path->slots[0]; i < nritems; i++) {
5090                         struct btrfs_dir_item *di;
5091                         struct btrfs_key di_key;
5092                         struct inode *di_inode;
5093                         struct btrfs_dir_list *new_dir_elem;
5094                         int log_mode = LOG_INODE_EXISTS;
5095                         int type;
5096
5097                         btrfs_item_key_to_cpu(leaf, &min_key, i);
5098                         if (min_key.objectid != dir_elem->ino ||
5099                             min_key.type != BTRFS_DIR_ITEM_KEY)
5100                                 goto next_dir_inode;
5101
5102                         di = btrfs_item_ptr(leaf, i, struct btrfs_dir_item);
5103                         type = btrfs_dir_type(leaf, di);
5104                         if (btrfs_dir_transid(leaf, di) < trans->transid &&
5105                             type != BTRFS_FT_DIR)
5106                                 continue;
5107                         btrfs_dir_item_key_to_cpu(leaf, di, &di_key);
5108                         if (di_key.type == BTRFS_ROOT_ITEM_KEY)
5109                                 continue;
5110
5111                         di_inode = btrfs_iget(root->fs_info->sb, &di_key,
5112                                               root, NULL);
5113                         if (IS_ERR(di_inode)) {
5114                                 ret = PTR_ERR(di_inode);
5115                                 goto next_dir_inode;
5116                         }
5117
5118                         if (btrfs_inode_in_log(di_inode, trans->transid)) {
5119                                 iput(di_inode);
5120                                 continue;
5121                         }
5122
5123                         ctx->log_new_dentries = false;
5124                         if (type == BTRFS_FT_DIR)
5125                                 log_mode = LOG_INODE_ALL;
5126                         btrfs_release_path(path);
5127                         ret = btrfs_log_inode(trans, root, di_inode,
5128                                               log_mode, 0, LLONG_MAX, ctx);
5129                         iput(di_inode);
5130                         if (ret)
5131                                 goto next_dir_inode;
5132                         if (ctx->log_new_dentries) {
5133                                 new_dir_elem = kmalloc(sizeof(*new_dir_elem),
5134                                                        GFP_NOFS);
5135                                 if (!new_dir_elem) {
5136                                         ret = -ENOMEM;
5137                                         goto next_dir_inode;
5138                                 }
5139                                 new_dir_elem->ino = di_key.objectid;
5140                                 list_add_tail(&new_dir_elem->list, &dir_list);
5141                         }
5142                         break;
5143                 }
5144                 if (i == nritems) {
5145                         ret = btrfs_next_leaf(log, path);
5146                         if (ret < 0) {
5147                                 goto next_dir_inode;
5148                         } else if (ret > 0) {
5149                                 ret = 0;
5150                                 goto next_dir_inode;
5151                         }
5152                         goto process_leaf;
5153                 }
5154                 if (min_key.offset < (u64)-1) {
5155                         min_key.offset++;
5156                         goto again;
5157                 }
5158 next_dir_inode:
5159                 list_del(&dir_elem->list);
5160                 kfree(dir_elem);
5161         }
5162
5163         btrfs_free_path(path);
5164         return ret;
5165 }
5166
5167 static int btrfs_log_all_parents(struct btrfs_trans_handle *trans,
5168                                  struct inode *inode,
5169                                  struct btrfs_log_ctx *ctx)
5170 {
5171         int ret;
5172         struct btrfs_path *path;
5173         struct btrfs_key key;
5174         struct btrfs_root *root = BTRFS_I(inode)->root;
5175         const u64 ino = btrfs_ino(inode);
5176
5177         path = btrfs_alloc_path();
5178         if (!path)
5179                 return -ENOMEM;
5180         path->skip_locking = 1;
5181         path->search_commit_root = 1;
5182
5183         key.objectid = ino;
5184         key.type = BTRFS_INODE_REF_KEY;
5185         key.offset = 0;
5186         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
5187         if (ret < 0)
5188                 goto out;
5189
5190         while (true) {
5191                 struct extent_buffer *leaf = path->nodes[0];
5192                 int slot = path->slots[0];
5193                 u32 cur_offset = 0;
5194                 u32 item_size;
5195                 unsigned long ptr;
5196
5197                 if (slot >= btrfs_header_nritems(leaf)) {
5198                         ret = btrfs_next_leaf(root, path);
5199                         if (ret < 0)
5200                                 goto out;
5201                         else if (ret > 0)
5202                                 break;
5203                         continue;
5204                 }
5205
5206                 btrfs_item_key_to_cpu(leaf, &key, slot);
5207                 /* BTRFS_INODE_EXTREF_KEY is BTRFS_INODE_REF_KEY + 1 */
5208                 if (key.objectid != ino || key.type > BTRFS_INODE_EXTREF_KEY)
5209                         break;
5210
5211                 item_size = btrfs_item_size_nr(leaf, slot);
5212                 ptr = btrfs_item_ptr_offset(leaf, slot);
5213                 while (cur_offset < item_size) {
5214                         struct btrfs_key inode_key;
5215                         struct inode *dir_inode;
5216
5217                         inode_key.type = BTRFS_INODE_ITEM_KEY;
5218                         inode_key.offset = 0;
5219
5220                         if (key.type == BTRFS_INODE_EXTREF_KEY) {
5221                                 struct btrfs_inode_extref *extref;
5222
5223                                 extref = (struct btrfs_inode_extref *)
5224                                         (ptr + cur_offset);
5225                                 inode_key.objectid = btrfs_inode_extref_parent(
5226                                         leaf, extref);
5227                                 cur_offset += sizeof(*extref);
5228                                 cur_offset += btrfs_inode_extref_name_len(leaf,
5229                                         extref);
5230                         } else {
5231                                 inode_key.objectid = key.offset;
5232                                 cur_offset = item_size;
5233                         }
5234
5235                         dir_inode = btrfs_iget(root->fs_info->sb, &inode_key,
5236                                                root, NULL);
5237                         /* If parent inode was deleted, skip it. */
5238                         if (IS_ERR(dir_inode))
5239                                 continue;
5240
5241                         ret = btrfs_log_inode(trans, root, dir_inode,
5242                                               LOG_INODE_ALL, 0, LLONG_MAX, ctx);
5243                         iput(dir_inode);
5244                         if (ret)
5245                                 goto out;
5246                 }
5247                 path->slots[0]++;
5248         }
5249         ret = 0;
5250 out:
5251         btrfs_free_path(path);
5252         return ret;
5253 }
5254
5255 /*
5256  * helper function around btrfs_log_inode to make sure newly created
5257  * parent directories also end up in the log.  A minimal inode and backref
5258  * only logging is done of any parent directories that are older than
5259  * the last committed transaction
5260  */
5261 static int btrfs_log_inode_parent(struct btrfs_trans_handle *trans,
5262                                   struct btrfs_root *root, struct inode *inode,
5263                                   struct dentry *parent,
5264                                   const loff_t start,
5265                                   const loff_t end,
5266                                   int exists_only,
5267                                   struct btrfs_log_ctx *ctx)
5268 {
5269         int inode_only = exists_only ? LOG_INODE_EXISTS : LOG_INODE_ALL;
5270         struct super_block *sb;
5271         struct dentry *old_parent = NULL;
5272         int ret = 0;
5273         u64 last_committed = root->fs_info->last_trans_committed;
5274         bool log_dentries = false;
5275         struct inode *orig_inode = inode;
5276
5277         sb = inode->i_sb;
5278
5279         if (btrfs_test_opt(root, NOTREELOG)) {
5280                 ret = 1;
5281                 goto end_no_trans;
5282         }
5283
5284         /*
5285          * The prev transaction commit doesn't complete, we need do
5286          * full commit by ourselves.
5287          */
5288         if (root->fs_info->last_trans_log_full_commit >
5289             root->fs_info->last_trans_committed) {
5290                 ret = 1;
5291                 goto end_no_trans;
5292         }
5293
5294         if (root != BTRFS_I(inode)->root ||
5295             btrfs_root_refs(&root->root_item) == 0) {
5296                 ret = 1;
5297                 goto end_no_trans;
5298         }
5299
5300         ret = check_parent_dirs_for_sync(trans, inode, parent,
5301                                          sb, last_committed);
5302         if (ret)
5303                 goto end_no_trans;
5304
5305         if (btrfs_inode_in_log(inode, trans->transid)) {
5306                 ret = BTRFS_NO_LOG_SYNC;
5307                 goto end_no_trans;
5308         }
5309
5310         ret = start_log_trans(trans, root, ctx);
5311         if (ret)
5312                 goto end_no_trans;
5313
5314         ret = btrfs_log_inode(trans, root, inode, inode_only, start, end, ctx);
5315         if (ret)
5316                 goto end_trans;
5317
5318         /*
5319          * for regular files, if its inode is already on disk, we don't
5320          * have to worry about the parents at all.  This is because
5321          * we can use the last_unlink_trans field to record renames
5322          * and other fun in this file.
5323          */
5324         if (S_ISREG(inode->i_mode) &&
5325             BTRFS_I(inode)->generation <= last_committed &&
5326             BTRFS_I(inode)->last_unlink_trans <= last_committed) {
5327                 ret = 0;
5328                 goto end_trans;
5329         }
5330
5331         if (S_ISDIR(inode->i_mode) && ctx && ctx->log_new_dentries)
5332                 log_dentries = true;
5333
5334         /*
5335          * On unlink we must make sure all our current and old parent directores
5336          * inodes are fully logged. This is to prevent leaving dangling
5337          * directory index entries in directories that were our parents but are
5338          * not anymore. Not doing this results in old parent directory being
5339          * impossible to delete after log replay (rmdir will always fail with
5340          * error -ENOTEMPTY).
5341          *
5342          * Example 1:
5343          *
5344          * mkdir testdir
5345          * touch testdir/foo
5346          * ln testdir/foo testdir/bar
5347          * sync
5348          * unlink testdir/bar
5349          * xfs_io -c fsync testdir/foo
5350          * <power failure>
5351          * mount fs, triggers log replay
5352          *
5353          * If we don't log the parent directory (testdir), after log replay the
5354          * directory still has an entry pointing to the file inode using the bar
5355          * name, but a matching BTRFS_INODE_[REF|EXTREF]_KEY does not exist and
5356          * the file inode has a link count of 1.
5357          *
5358          * Example 2:
5359          *
5360          * mkdir testdir
5361          * touch foo
5362          * ln foo testdir/foo2
5363          * ln foo testdir/foo3
5364          * sync
5365          * unlink testdir/foo3
5366          * xfs_io -c fsync foo
5367          * <power failure>
5368          * mount fs, triggers log replay
5369          *
5370          * Similar as the first example, after log replay the parent directory
5371          * testdir still has an entry pointing to the inode file with name foo3
5372          * but the file inode does not have a matching BTRFS_INODE_REF_KEY item
5373          * and has a link count of 2.
5374          */
5375         if (BTRFS_I(inode)->last_unlink_trans > last_committed) {
5376                 ret = btrfs_log_all_parents(trans, orig_inode, ctx);
5377                 if (ret)
5378                         goto end_trans;
5379         }
5380
5381         while (1) {
5382                 if (!parent || d_really_is_negative(parent) || sb != d_inode(parent)->i_sb)
5383                         break;
5384
5385                 inode = d_inode(parent);
5386                 if (root != BTRFS_I(inode)->root)
5387                         break;
5388
5389                 if (BTRFS_I(inode)->generation > last_committed) {
5390                         ret = btrfs_log_inode(trans, root, inode,
5391                                               LOG_INODE_EXISTS,
5392                                               0, LLONG_MAX, ctx);
5393                         if (ret)
5394                                 goto end_trans;
5395                 }
5396                 if (IS_ROOT(parent))
5397                         break;
5398
5399                 parent = dget_parent(parent);
5400                 dput(old_parent);
5401                 old_parent = parent;
5402         }
5403         if (log_dentries)
5404                 ret = log_new_dir_dentries(trans, root, orig_inode, ctx);
5405         else
5406                 ret = 0;
5407 end_trans:
5408         dput(old_parent);
5409         if (ret < 0) {
5410                 btrfs_set_log_full_commit(root->fs_info, trans);
5411                 ret = 1;
5412         }
5413
5414         if (ret)
5415                 btrfs_remove_log_ctx(root, ctx);
5416         btrfs_end_log_trans(root);
5417 end_no_trans:
5418         return ret;
5419 }
5420
5421 /*
5422  * it is not safe to log dentry if the chunk root has added new
5423  * chunks.  This returns 0 if the dentry was logged, and 1 otherwise.
5424  * If this returns 1, you must commit the transaction to safely get your
5425  * data on disk.
5426  */
5427 int btrfs_log_dentry_safe(struct btrfs_trans_handle *trans,
5428                           struct btrfs_root *root, struct dentry *dentry,
5429                           const loff_t start,
5430                           const loff_t end,
5431                           struct btrfs_log_ctx *ctx)
5432 {
5433         struct dentry *parent = dget_parent(dentry);
5434         int ret;
5435
5436         ret = btrfs_log_inode_parent(trans, root, d_inode(dentry), parent,
5437                                      start, end, 0, ctx);
5438         dput(parent);
5439
5440         return ret;
5441 }
5442
5443 /*
5444  * should be called during mount to recover any replay any log trees
5445  * from the FS
5446  */
5447 int btrfs_recover_log_trees(struct btrfs_root *log_root_tree)
5448 {
5449         int ret;
5450         struct btrfs_path *path;
5451         struct btrfs_trans_handle *trans;
5452         struct btrfs_key key;
5453         struct btrfs_key found_key;
5454         struct btrfs_key tmp_key;
5455         struct btrfs_root *log;
5456         struct btrfs_fs_info *fs_info = log_root_tree->fs_info;
5457         struct walk_control wc = {
5458                 .process_func = process_one_buffer,
5459                 .stage = 0,
5460         };
5461
5462         path = btrfs_alloc_path();
5463         if (!path)
5464                 return -ENOMEM;
5465
5466         fs_info->log_root_recovering = 1;
5467
5468         trans = btrfs_start_transaction(fs_info->tree_root, 0);
5469         if (IS_ERR(trans)) {
5470                 ret = PTR_ERR(trans);
5471                 goto error;
5472         }
5473
5474         wc.trans = trans;
5475         wc.pin = 1;
5476
5477         ret = walk_log_tree(trans, log_root_tree, &wc);
5478         if (ret) {
5479                 btrfs_std_error(fs_info, ret, "Failed to pin buffers while "
5480                             "recovering log root tree.");
5481                 goto error;
5482         }
5483
5484 again:
5485         key.objectid = BTRFS_TREE_LOG_OBJECTID;
5486         key.offset = (u64)-1;
5487         key.type = BTRFS_ROOT_ITEM_KEY;
5488
5489         while (1) {
5490                 ret = btrfs_search_slot(NULL, log_root_tree, &key, path, 0, 0);
5491
5492                 if (ret < 0) {
5493                         btrfs_std_error(fs_info, ret,
5494                                     "Couldn't find tree log root.");
5495                         goto error;
5496                 }
5497                 if (ret > 0) {
5498                         if (path->slots[0] == 0)
5499                                 break;
5500                         path->slots[0]--;
5501                 }
5502                 btrfs_item_key_to_cpu(path->nodes[0], &found_key,
5503                                       path->slots[0]);
5504                 btrfs_release_path(path);
5505                 if (found_key.objectid != BTRFS_TREE_LOG_OBJECTID)
5506                         break;
5507
5508                 log = btrfs_read_fs_root(log_root_tree, &found_key);
5509                 if (IS_ERR(log)) {
5510                         ret = PTR_ERR(log);
5511                         btrfs_std_error(fs_info, ret,
5512                                     "Couldn't read tree log root.");
5513                         goto error;
5514                 }
5515
5516                 tmp_key.objectid = found_key.offset;
5517                 tmp_key.type = BTRFS_ROOT_ITEM_KEY;
5518                 tmp_key.offset = (u64)-1;
5519
5520                 wc.replay_dest = btrfs_read_fs_root_no_name(fs_info, &tmp_key);
5521                 if (IS_ERR(wc.replay_dest)) {
5522                         ret = PTR_ERR(wc.replay_dest);
5523                         free_extent_buffer(log->node);
5524                         free_extent_buffer(log->commit_root);
5525                         kfree(log);
5526                         btrfs_std_error(fs_info, ret, "Couldn't read target root "
5527                                     "for tree log recovery.");
5528                         goto error;
5529                 }
5530
5531                 wc.replay_dest->log_root = log;
5532                 btrfs_record_root_in_trans(trans, wc.replay_dest);
5533                 ret = walk_log_tree(trans, log, &wc);
5534
5535                 if (!ret && wc.stage == LOG_WALK_REPLAY_ALL) {
5536                         ret = fixup_inode_link_counts(trans, wc.replay_dest,
5537                                                       path);
5538                 }
5539
5540                 if (!ret && wc.stage == LOG_WALK_REPLAY_ALL) {
5541                         struct btrfs_root *root = wc.replay_dest;
5542
5543                         btrfs_release_path(path);
5544
5545                         /*
5546                          * We have just replayed everything, and the highest
5547                          * objectid of fs roots probably has changed in case
5548                          * some inode_item's got replayed.
5549                          *
5550                          * root->objectid_mutex is not acquired as log replay
5551                          * could only happen during mount.
5552                          */
5553                         ret = btrfs_find_highest_objectid(root,
5554                                                   &root->highest_objectid);
5555                 }
5556
5557                 key.offset = found_key.offset - 1;
5558                 wc.replay_dest->log_root = NULL;
5559                 free_extent_buffer(log->node);
5560                 free_extent_buffer(log->commit_root);
5561                 kfree(log);
5562
5563                 if (ret)
5564                         goto error;
5565
5566                 if (found_key.offset == 0)
5567                         break;
5568         }
5569         btrfs_release_path(path);
5570
5571         /* step one is to pin it all, step two is to replay just inodes */
5572         if (wc.pin) {
5573                 wc.pin = 0;
5574                 wc.process_func = replay_one_buffer;
5575                 wc.stage = LOG_WALK_REPLAY_INODES;
5576                 goto again;
5577         }
5578         /* step three is to replay everything */
5579         if (wc.stage < LOG_WALK_REPLAY_ALL) {
5580                 wc.stage++;
5581                 goto again;
5582         }
5583
5584         btrfs_free_path(path);
5585
5586         /* step 4: commit the transaction, which also unpins the blocks */
5587         ret = btrfs_commit_transaction(trans, fs_info->tree_root);
5588         if (ret)
5589                 return ret;
5590
5591         free_extent_buffer(log_root_tree->node);
5592         log_root_tree->log_root = NULL;
5593         fs_info->log_root_recovering = 0;
5594         kfree(log_root_tree);
5595
5596         return 0;
5597 error:
5598         if (wc.trans)
5599                 btrfs_end_transaction(wc.trans, fs_info->tree_root);
5600         btrfs_free_path(path);
5601         return ret;
5602 }
5603
5604 /*
5605  * there are some corner cases where we want to force a full
5606  * commit instead of allowing a directory to be logged.
5607  *
5608  * They revolve around files there were unlinked from the directory, and
5609  * this function updates the parent directory so that a full commit is
5610  * properly done if it is fsync'd later after the unlinks are done.
5611  */
5612 void btrfs_record_unlink_dir(struct btrfs_trans_handle *trans,
5613                              struct inode *dir, struct inode *inode,
5614                              int for_rename)
5615 {
5616         /*
5617          * when we're logging a file, if it hasn't been renamed
5618          * or unlinked, and its inode is fully committed on disk,
5619          * we don't have to worry about walking up the directory chain
5620          * to log its parents.
5621          *
5622          * So, we use the last_unlink_trans field to put this transid
5623          * into the file.  When the file is logged we check it and
5624          * don't log the parents if the file is fully on disk.
5625          */
5626         if (S_ISREG(inode->i_mode))
5627                 BTRFS_I(inode)->last_unlink_trans = trans->transid;
5628
5629         /*
5630          * if this directory was already logged any new
5631          * names for this file/dir will get recorded
5632          */
5633         smp_mb();
5634         if (BTRFS_I(dir)->logged_trans == trans->transid)
5635                 return;
5636
5637         /*
5638          * if the inode we're about to unlink was logged,
5639          * the log will be properly updated for any new names
5640          */
5641         if (BTRFS_I(inode)->logged_trans == trans->transid)
5642                 return;
5643
5644         /*
5645          * when renaming files across directories, if the directory
5646          * there we're unlinking from gets fsync'd later on, there's
5647          * no way to find the destination directory later and fsync it
5648          * properly.  So, we have to be conservative and force commits
5649          * so the new name gets discovered.
5650          */
5651         if (for_rename)
5652                 goto record;
5653
5654         /* we can safely do the unlink without any special recording */
5655         return;
5656
5657 record:
5658         BTRFS_I(dir)->last_unlink_trans = trans->transid;
5659 }
5660
5661 /*
5662  * Call this after adding a new name for a file and it will properly
5663  * update the log to reflect the new name.
5664  *
5665  * It will return zero if all goes well, and it will return 1 if a
5666  * full transaction commit is required.
5667  */
5668 int btrfs_log_new_name(struct btrfs_trans_handle *trans,
5669                         struct inode *inode, struct inode *old_dir,
5670                         struct dentry *parent)
5671 {
5672         struct btrfs_root * root = BTRFS_I(inode)->root;
5673
5674         /*
5675          * this will force the logging code to walk the dentry chain
5676          * up for the file
5677          */
5678         if (S_ISREG(inode->i_mode))
5679                 BTRFS_I(inode)->last_unlink_trans = trans->transid;
5680
5681         /*
5682          * if this inode hasn't been logged and directory we're renaming it
5683          * from hasn't been logged, we don't need to log it
5684          */
5685         if (BTRFS_I(inode)->logged_trans <=
5686             root->fs_info->last_trans_committed &&
5687             (!old_dir || BTRFS_I(old_dir)->logged_trans <=
5688                     root->fs_info->last_trans_committed))
5689                 return 0;
5690
5691         return btrfs_log_inode_parent(trans, root, inode, parent, 0,
5692                                       LLONG_MAX, 1, NULL);
5693 }
5694