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