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