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