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