1	// SPDX-License-Identifier: GPL-2.0
2	/*
3	* Copyright (C) 2007,2008 Oracle. All rights reserved.
4	*/
5
6	#include <linux/sched.h>
7	#include <linux/slab.h>
8	#include <linux/rbtree.h>
9	#include <linux/mm.h>
10	#include <linux/error-injection.h>
11	#include "messages.h"
12	#include "ctree.h"
13	#include "disk-io.h"
14	#include "transaction.h"
15	#include "print-tree.h"
16	#include "locking.h"
17	#include "volumes.h"
18	#include "qgroup.h"
19	#include "tree-mod-log.h"
20	#include "tree-checker.h"
21	#include "fs.h"
22	#include "accessors.h"
23	#include "extent-tree.h"
24	#include "relocation.h"
25	#include "file-item.h"
26
27	static struct kmem_cache *btrfs_path_cachep;
28
29	static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
30	*root, struct btrfs_path *path, int level);
31	static int split_leaf(struct btrfs_trans_handle *trans, struct btrfs_root *root,
32	const struct btrfs_key *ins_key, struct btrfs_path *path,
33	int data_size, bool extend);
34	static int push_node_left(struct btrfs_trans_handle *trans,
35	struct extent_buffer *dst,
36	struct extent_buffer *src, bool empty);
37	static int balance_node_right(struct btrfs_trans_handle *trans,
38	struct extent_buffer *dst_buf,
39	struct extent_buffer *src_buf);
40	/*
41	* The leaf data grows from end-to-front in the node. this returns the address
42	* of the start of the last item, which is the stop of the leaf data stack.
43	*/
44	static unsigned int leaf_data_end(const struct extent_buffer *leaf)
45	{
46	u32 nr = btrfs_header_nritems(eb: leaf);
47
48	if (nr == 0)
49	return BTRFS_LEAF_DATA_SIZE(info: leaf->fs_info);
50	return btrfs_item_offset(eb: leaf, slot: nr - 1);
51	}
52
53	/*
54	* Move data in a @leaf (using memmove, safe for overlapping ranges).
55	*
56	* @leaf: leaf that we're doing a memmove on
57	* @dst_offset: item data offset we're moving to
58	* @src_offset: item data offset were' moving from
59	* @len: length of the data we're moving
60	*
61	* Wrapper around memmove_extent_buffer() that takes into account the header on
62	* the leaf. The btrfs_item offset's start directly after the header, so we
63	* have to adjust any offsets to account for the header in the leaf. This
64	* handles that math to simplify the callers.
65	*/
66	static inline void memmove_leaf_data(const struct extent_buffer *leaf,
67	unsigned long dst_offset,
68	unsigned long src_offset,
69	unsigned long len)
70	{
71	memmove_extent_buffer(dst: leaf, dst_offset: btrfs_item_nr_offset(eb: leaf, nr: 0) + dst_offset,
72	src_offset: btrfs_item_nr_offset(eb: leaf, nr: 0) + src_offset, len);
73	}
74
75	/*
76	* Copy item data from @src into @dst at the given @offset.
77	*
78	* @dst: destination leaf that we're copying into
79	* @src: source leaf that we're copying from
80	* @dst_offset: item data offset we're copying to
81	* @src_offset: item data offset were' copying from
82	* @len: length of the data we're copying
83	*
84	* Wrapper around copy_extent_buffer() that takes into account the header on
85	* the leaf. The btrfs_item offset's start directly after the header, so we
86	* have to adjust any offsets to account for the header in the leaf. This
87	* handles that math to simplify the callers.
88	*/
89	static inline void copy_leaf_data(const struct extent_buffer *dst,
90	const struct extent_buffer *src,
91	unsigned long dst_offset,
92	unsigned long src_offset, unsigned long len)
93	{
94	copy_extent_buffer(dst, src, dst_offset: btrfs_item_nr_offset(eb: dst, nr: 0) + dst_offset,
95	src_offset: btrfs_item_nr_offset(eb: src, nr: 0) + src_offset, len);
96	}
97
98	/*
99	* Move items in a @leaf (using memmove).
100	*
101	* @dst: destination leaf for the items
102	* @dst_item: the item nr we're copying into
103	* @src_item: the item nr we're copying from
104	* @nr_items: the number of items to copy
105	*
106	* Wrapper around memmove_extent_buffer() that does the math to get the
107	* appropriate offsets into the leaf from the item numbers.
108	*/
109	static inline void memmove_leaf_items(const struct extent_buffer *leaf,
110	int dst_item, int src_item, int nr_items)
111	{
112	memmove_extent_buffer(dst: leaf, dst_offset: btrfs_item_nr_offset(eb: leaf, nr: dst_item),
113	src_offset: btrfs_item_nr_offset(eb: leaf, nr: src_item),
114	len: nr_items * sizeof(struct btrfs_item));
115	}
116
117	/*
118	* Copy items from @src into @dst at the given @offset.
119	*
120	* @dst: destination leaf for the items
121	* @src: source leaf for the items
122	* @dst_item: the item nr we're copying into
123	* @src_item: the item nr we're copying from
124	* @nr_items: the number of items to copy
125	*
126	* Wrapper around copy_extent_buffer() that does the math to get the
127	* appropriate offsets into the leaf from the item numbers.
128	*/
129	static inline void copy_leaf_items(const struct extent_buffer *dst,
130	const struct extent_buffer *src,
131	int dst_item, int src_item, int nr_items)
132	{
133	copy_extent_buffer(dst, src, dst_offset: btrfs_item_nr_offset(eb: dst, nr: dst_item),
134	src_offset: btrfs_item_nr_offset(eb: src, nr: src_item),
135	len: nr_items * sizeof(struct btrfs_item));
136	}
137
138	struct btrfs_path *btrfs_alloc_path(void)
139	{
140	might_sleep();
141
142	return kmem_cache_zalloc(btrfs_path_cachep, GFP_NOFS);
143	}
144
145	/* this also releases the path */
146	void btrfs_free_path(struct btrfs_path *p)
147	{
148	if (!p)
149	return;
150	btrfs_release_path(p);
151	kmem_cache_free(s: btrfs_path_cachep, objp: p);
152	}
153
154	/*
155	* path release drops references on the extent buffers in the path
156	* and it drops any locks held by this path
157	*
158	* It is safe to call this on paths that no locks or extent buffers held.
159	*/
160	noinline void btrfs_release_path(struct btrfs_path *p)
161	{
162	int i;
163
164	for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
165	p->slots[i] = 0;
166	if (!p->nodes[i])
167	continue;
168	if (p->locks[i]) {
169	btrfs_tree_unlock_rw(eb: p->nodes[i], rw: p->locks[i]);
170	p->locks[i] = 0;
171	}
172	free_extent_buffer(eb: p->nodes[i]);
173	p->nodes[i] = NULL;
174	}
175	}
176
177	/*
178	* safely gets a reference on the root node of a tree. A lock
179	* is not taken, so a concurrent writer may put a different node
180	* at the root of the tree. See btrfs_lock_root_node for the
181	* looping required.
182	*
183	* The extent buffer returned by this has a reference taken, so
184	* it won't disappear. It may stop being the root of the tree
185	* at any time because there are no locks held.
186	*/
187	struct extent_buffer *btrfs_root_node(struct btrfs_root *root)
188	{
189	struct extent_buffer *eb;
190
191	while (1) {
192	rcu_read_lock();
193	eb = rcu_dereference(root->node);
194
195	/*
196	* RCU really hurts here, we could free up the root node because
197	* it was COWed but we may not get the new root node yet so do
198	* the inc_not_zero dance and if it doesn't work then
199	* synchronize_rcu and try again.
200	*/
201	if (refcount_inc_not_zero(r: &eb->refs)) {
202	rcu_read_unlock();
203	break;
204	}
205	rcu_read_unlock();
206	synchronize_rcu();
207	}
208	return eb;
209	}
210
211	/*
212	* Cowonly root (not-shareable trees, everything not subvolume or reloc roots),
213	* just get put onto a simple dirty list. Transaction walks this list to make
214	* sure they get properly updated on disk.
215	*/
216	static void add_root_to_dirty_list(struct btrfs_root *root)
217	{
218	struct btrfs_fs_info *fs_info = root->fs_info;
219
220	if (test_bit(BTRFS_ROOT_DIRTY, &root->state) ||
221	!test_bit(BTRFS_ROOT_TRACK_DIRTY, &root->state))
222	return;
223
224	spin_lock(lock: &fs_info->trans_lock);
225	if (!test_and_set_bit(nr: BTRFS_ROOT_DIRTY, addr: &root->state)) {
226	/* Want the extent tree to be the last on the list */
227	if (btrfs_root_id(root) == BTRFS_EXTENT_TREE_OBJECTID)
228	list_move_tail(list: &root->dirty_list,
229	head: &fs_info->dirty_cowonly_roots);
230	else
231	list_move(list: &root->dirty_list,
232	head: &fs_info->dirty_cowonly_roots);
233	}
234	spin_unlock(lock: &fs_info->trans_lock);
235	}
236
237	/*
238	* used by snapshot creation to make a copy of a root for a tree with
239	* a given objectid. The buffer with the new root node is returned in
240	* cow_ret, and this func returns zero on success or a negative error code.
241	*/
242	int btrfs_copy_root(struct btrfs_trans_handle *trans,
243	struct btrfs_root *root,
244	struct extent_buffer *buf,
245	struct extent_buffer **cow_ret, u64 new_root_objectid)
246	{
247	struct btrfs_fs_info *fs_info = root->fs_info;
248	struct extent_buffer *cow;
249	int ret = 0;
250	int level;
251	struct btrfs_disk_key disk_key;
252	u64 reloc_src_root = 0;
253
254	WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) &&
255	trans->transid != fs_info->running_transaction->transid);
256	WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) &&
257	trans->transid != btrfs_get_root_last_trans(root));
258
259	level = btrfs_header_level(eb: buf);
260	if (level == 0)
261	btrfs_item_key(eb: buf, disk_key: &disk_key, nr: 0);
262	else
263	btrfs_node_key(eb: buf, disk_key: &disk_key, nr: 0);
264
265	if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
266	reloc_src_root = btrfs_header_owner(eb: buf);
267	cow = btrfs_alloc_tree_block(trans, root, parent: 0, root_objectid: new_root_objectid,
268	key: &disk_key, level, hint: buf->start, empty_size: 0,
269	reloc_src_root, nest: BTRFS_NESTING_NEW_ROOT);
270	if (IS_ERR(ptr: cow))
271	return PTR_ERR(ptr: cow);
272
273	copy_extent_buffer_full(dst: cow, src: buf);
274	btrfs_set_header_bytenr(eb: cow, val: cow->start);
275	btrfs_set_header_generation(eb: cow, val: trans->transid);
276	btrfs_set_header_backref_rev(eb: cow, BTRFS_MIXED_BACKREF_REV);
277	btrfs_clear_header_flag(eb: cow, BTRFS_HEADER_FLAG_WRITTEN |
278	BTRFS_HEADER_FLAG_RELOC);
279	if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
280	btrfs_set_header_flag(eb: cow, BTRFS_HEADER_FLAG_RELOC);
281	else
282	btrfs_set_header_owner(eb: cow, val: new_root_objectid);
283
284	write_extent_buffer_fsid(eb: cow, fsid: fs_info->fs_devices->metadata_uuid);
285
286	if (unlikely(btrfs_header_generation(buf) > trans->transid)) {
287	btrfs_tree_unlock(eb: cow);
288	free_extent_buffer(eb: cow);
289	ret = -EUCLEAN;
290	btrfs_abort_transaction(trans, ret);
291	return ret;
292	}
293
294	if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID) {
295	ret = btrfs_inc_ref(trans, root, buf: cow, full_backref: 1);
296	if (unlikely(ret))
297	btrfs_abort_transaction(trans, ret);
298	} else {
299	ret = btrfs_inc_ref(trans, root, buf: cow, full_backref: 0);
300	if (unlikely(ret))
301	btrfs_abort_transaction(trans, ret);
302	}
303	if (ret) {
304	btrfs_tree_unlock(eb: cow);
305	free_extent_buffer(eb: cow);
306	return ret;
307	}
308
309	btrfs_mark_buffer_dirty(trans, buf: cow);
310	*cow_ret = cow;
311	return 0;
312	}
313
314	/*
315	* check if the tree block can be shared by multiple trees
316	*/
317	bool btrfs_block_can_be_shared(const struct btrfs_trans_handle *trans,
318	const struct btrfs_root *root,
319	const struct extent_buffer *buf)
320	{
321	const u64 buf_gen = btrfs_header_generation(eb: buf);
322
323	/*
324	* Tree blocks not in shareable trees and tree roots are never shared.
325	* If a block was allocated after the last snapshot and the block was
326	* not allocated by tree relocation, we know the block is not shared.
327	*/
328
329	if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state))
330	return false;
331
332	if (buf == root->node)
333	return false;
334
335	if (buf_gen > btrfs_root_last_snapshot(s: &root->root_item) &&
336	!btrfs_header_flag(eb: buf, BTRFS_HEADER_FLAG_RELOC))
337	return false;
338
339	if (buf != root->commit_root)
340	return true;
341
342	/*
343	* An extent buffer that used to be the commit root may still be shared
344	* because the tree height may have increased and it became a child of a
345	* higher level root. This can happen when snapshotting a subvolume
346	* created in the current transaction.
347	*/
348	if (buf_gen == trans->transid)
349	return true;
350
351	return false;
352	}
353
354	static noinline int update_ref_for_cow(struct btrfs_trans_handle *trans,
355	struct btrfs_root *root,
356	struct extent_buffer *buf,
357	struct extent_buffer *cow,
358	int *last_ref)
359	{
360	struct btrfs_fs_info *fs_info = root->fs_info;
361	u64 refs;
362	u64 owner;
363	u64 flags;
364	int ret;
365
366	/*
367	* Backrefs update rules:
368	*
369	* Always use full backrefs for extent pointers in tree block
370	* allocated by tree relocation.
371	*
372	* If a shared tree block is no longer referenced by its owner
373	* tree (btrfs_header_owner(buf) == root->root_key.objectid),
374	* use full backrefs for extent pointers in tree block.
375	*
376	* If a tree block is been relocating
377	* (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID),
378	* use full backrefs for extent pointers in tree block.
379	* The reason for this is some operations (such as drop tree)
380	* are only allowed for blocks use full backrefs.
381	*/
382
383	if (btrfs_block_can_be_shared(trans, root, buf)) {
384	ret = btrfs_lookup_extent_info(trans, fs_info, bytenr: buf->start,
385	offset: btrfs_header_level(eb: buf), metadata: 1,
386	refs: &refs, flags: &flags, NULL);
387	if (ret)
388	return ret;
389	if (unlikely(refs == 0)) {
390	btrfs_crit(fs_info,
391	"found 0 references for tree block at bytenr %llu level %d root %llu",
392	buf->start, btrfs_header_level(buf),
393	btrfs_root_id(root));
394	ret = -EUCLEAN;
395	btrfs_abort_transaction(trans, ret);
396	return ret;
397	}
398	} else {
399	refs = 1;
400	if (btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID ||
401	btrfs_header_backref_rev(eb: buf) < BTRFS_MIXED_BACKREF_REV)
402	flags = BTRFS_BLOCK_FLAG_FULL_BACKREF;
403	else
404	flags = 0;
405	}
406
407	owner = btrfs_header_owner(eb: buf);
408	if (unlikely(owner == BTRFS_TREE_RELOC_OBJECTID &&
409	!(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF))) {
410	btrfs_crit(fs_info,
411	"found tree block at bytenr %llu level %d root %llu refs %llu flags %llx without full backref flag set",
412	buf->start, btrfs_header_level(buf),
413	btrfs_root_id(root), refs, flags);
414	ret = -EUCLEAN;
415	btrfs_abort_transaction(trans, ret);
416	return ret;
417	}
418
419	if (refs > 1) {
420	if ((owner == btrfs_root_id(root) ||
421	btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID) &&
422	!(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)) {
423	ret = btrfs_inc_ref(trans, root, buf, full_backref: 1);
424	if (ret)
425	return ret;
426
427	if (btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID) {
428	ret = btrfs_dec_ref(trans, root, buf, full_backref: 0);
429	if (ret)
430	return ret;
431	ret = btrfs_inc_ref(trans, root, buf: cow, full_backref: 1);
432	if (ret)
433	return ret;
434	}
435	ret = btrfs_set_disk_extent_flags(trans, eb: buf,
436	BTRFS_BLOCK_FLAG_FULL_BACKREF);
437	if (ret)
438	return ret;
439	} else {
440
441	if (btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID)
442	ret = btrfs_inc_ref(trans, root, buf: cow, full_backref: 1);
443	else
444	ret = btrfs_inc_ref(trans, root, buf: cow, full_backref: 0);
445	if (ret)
446	return ret;
447	}
448	} else {
449	if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
450	if (btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID)
451	ret = btrfs_inc_ref(trans, root, buf: cow, full_backref: 1);
452	else
453	ret = btrfs_inc_ref(trans, root, buf: cow, full_backref: 0);
454	if (ret)
455	return ret;
456	ret = btrfs_dec_ref(trans, root, buf, full_backref: 1);
457	if (ret)
458	return ret;
459	}
460	btrfs_clear_buffer_dirty(trans, buf);
461	*last_ref = 1;
462	}
463	return 0;
464	}
465
466	/*
467	* does the dirty work in cow of a single block. The parent block (if
468	* supplied) is updated to point to the new cow copy. The new buffer is marked
469	* dirty and returned locked. If you modify the block it needs to be marked
470	* dirty again.
471	*
472	* search_start -- an allocation hint for the new block
473	*
474	* empty_size -- a hint that you plan on doing more cow. This is the size in
475	* bytes the allocator should try to find free next to the block it returns.
476	* This is just a hint and may be ignored by the allocator.
477	*/
478	int btrfs_force_cow_block(struct btrfs_trans_handle *trans,
479	struct btrfs_root *root,
480	struct extent_buffer *buf,
481	struct extent_buffer *parent, int parent_slot,
482	struct extent_buffer **cow_ret,
483	u64 search_start, u64 empty_size,
484	enum btrfs_lock_nesting nest)
485	{
486	struct btrfs_fs_info *fs_info = root->fs_info;
487	struct btrfs_disk_key disk_key;
488	struct extent_buffer *cow;
489	int level, ret;
490	int last_ref = 0;
491	int unlock_orig = 0;
492	u64 parent_start = 0;
493	u64 reloc_src_root = 0;
494
495	if (*cow_ret == buf)
496	unlock_orig = 1;
497
498	btrfs_assert_tree_write_locked(eb: buf);
499
500	WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) &&
501	trans->transid != fs_info->running_transaction->transid);
502	WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) &&
503	trans->transid != btrfs_get_root_last_trans(root));
504
505	level = btrfs_header_level(eb: buf);
506
507	if (level == 0)
508	btrfs_item_key(eb: buf, disk_key: &disk_key, nr: 0);
509	else
510	btrfs_node_key(eb: buf, disk_key: &disk_key, nr: 0);
511
512	if (btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID) {
513	if (parent)
514	parent_start = parent->start;
515	reloc_src_root = btrfs_header_owner(eb: buf);
516	}
517	cow = btrfs_alloc_tree_block(trans, root, parent: parent_start,
518	root_objectid: btrfs_root_id(root), key: &disk_key, level,
519	hint: search_start, empty_size, reloc_src_root, nest);
520	if (IS_ERR(ptr: cow))
521	return PTR_ERR(ptr: cow);
522
523	/* cow is set to blocking by btrfs_init_new_buffer */
524
525	copy_extent_buffer_full(dst: cow, src: buf);
526	btrfs_set_header_bytenr(eb: cow, val: cow->start);
527	btrfs_set_header_generation(eb: cow, val: trans->transid);
528	btrfs_set_header_backref_rev(eb: cow, BTRFS_MIXED_BACKREF_REV);
529	btrfs_clear_header_flag(eb: cow, BTRFS_HEADER_FLAG_WRITTEN |
530	BTRFS_HEADER_FLAG_RELOC);
531	if (btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID)
532	btrfs_set_header_flag(eb: cow, BTRFS_HEADER_FLAG_RELOC);
533	else
534	btrfs_set_header_owner(eb: cow, val: btrfs_root_id(root));
535
536	write_extent_buffer_fsid(eb: cow, fsid: fs_info->fs_devices->metadata_uuid);
537
538	ret = update_ref_for_cow(trans, root, buf, cow, last_ref: &last_ref);
539	if (unlikely(ret)) {
540	btrfs_abort_transaction(trans, ret);
541	goto error_unlock_cow;
542	}
543
544	if (test_bit(BTRFS_ROOT_SHAREABLE, &root->state)) {
545	ret = btrfs_reloc_cow_block(trans, root, buf, cow);
546	if (unlikely(ret)) {
547	btrfs_abort_transaction(trans, ret);
548	goto error_unlock_cow;
549	}
550	}
551
552	if (buf == root->node) {
553	WARN_ON(parent && parent != buf);
554	if (btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID ||
555	btrfs_header_backref_rev(eb: buf) < BTRFS_MIXED_BACKREF_REV)
556	parent_start = buf->start;
557
558	ret = btrfs_tree_mod_log_insert_root(old_root: root->node, new_root: cow, log_removal: true);
559	if (unlikely(ret < 0)) {
560	btrfs_abort_transaction(trans, ret);
561	goto error_unlock_cow;
562	}
563	refcount_inc(r: &cow->refs);
564	rcu_assign_pointer(root->node, cow);
565
566	ret = btrfs_free_tree_block(trans, root_id: btrfs_root_id(root), buf,
567	parent: parent_start, last_ref);
568	free_extent_buffer(eb: buf);
569	add_root_to_dirty_list(root);
570	if (unlikely(ret < 0)) {
571	btrfs_abort_transaction(trans, ret);
572	goto error_unlock_cow;
573	}
574	} else {
575	WARN_ON(trans->transid != btrfs_header_generation(parent));
576	ret = btrfs_tree_mod_log_insert_key(eb: parent, slot: parent_slot,
577	op: BTRFS_MOD_LOG_KEY_REPLACE);
578	if (unlikely(ret)) {
579	btrfs_abort_transaction(trans, ret);
580	goto error_unlock_cow;
581	}
582	btrfs_set_node_blockptr(eb: parent, nr: parent_slot,
583	val: cow->start);
584	btrfs_set_node_ptr_generation(eb: parent, nr: parent_slot,
585	val: trans->transid);
586	btrfs_mark_buffer_dirty(trans, buf: parent);
587	if (last_ref) {
588	ret = btrfs_tree_mod_log_free_eb(eb: buf);
589	if (unlikely(ret)) {
590	btrfs_abort_transaction(trans, ret);
591	goto error_unlock_cow;
592	}
593	}
594	ret = btrfs_free_tree_block(trans, root_id: btrfs_root_id(root), buf,
595	parent: parent_start, last_ref);
596	if (unlikely(ret < 0)) {
597	btrfs_abort_transaction(trans, ret);
598	goto error_unlock_cow;
599	}
600	}
601
602	trace_btrfs_cow_block(root, buf, cow);
603	if (unlock_orig)
604	btrfs_tree_unlock(eb: buf);
605	free_extent_buffer_stale(eb: buf);
606	btrfs_mark_buffer_dirty(trans, buf: cow);
607	*cow_ret = cow;
608	return 0;
609
610	error_unlock_cow:
611	btrfs_tree_unlock(eb: cow);
612	free_extent_buffer(eb: cow);
613	return ret;
614	}
615
616	static inline bool should_cow_block(const struct btrfs_trans_handle *trans,
617	const struct btrfs_root *root,
618	const struct extent_buffer *buf)
619	{
620	if (btrfs_is_testing(fs_info: root->fs_info))
621	return false;
622
623	/*
624	* We do not need to cow a block if
625	* 1) this block is not created or changed in this transaction;
626	* 2) this block does not belong to TREE_RELOC tree;
627	* 3) the root is not forced COW.
628	*
629	* What is forced COW:
630	* when we create snapshot during committing the transaction,
631	* after we've finished copying src root, we must COW the shared
632	* block to ensure the metadata consistency.
633	*/
634
635	if (btrfs_header_generation(eb: buf) != trans->transid)
636	return true;
637
638	if (btrfs_header_flag(eb: buf, BTRFS_HEADER_FLAG_WRITTEN))
639	return true;
640
641	/* Ensure we can see the FORCE_COW bit. */
642	smp_mb__before_atomic();
643	if (test_bit(BTRFS_ROOT_FORCE_COW, &root->state))
644	return true;
645
646	if (btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID)
647	return false;
648
649	if (btrfs_header_flag(eb: buf, BTRFS_HEADER_FLAG_RELOC))
650	return true;
651
652	return false;
653	}
654
655	/*
656	* COWs a single block, see btrfs_force_cow_block() for the real work.
657	* This version of it has extra checks so that a block isn't COWed more than
658	* once per transaction, as long as it hasn't been written yet
659	*/
660	int btrfs_cow_block(struct btrfs_trans_handle *trans,
661	struct btrfs_root *root, struct extent_buffer *buf,
662	struct extent_buffer *parent, int parent_slot,
663	struct extent_buffer **cow_ret,
664	enum btrfs_lock_nesting nest)
665	{
666	struct btrfs_fs_info *fs_info = root->fs_info;
667	u64 search_start;
668
669	if (unlikely(test_bit(BTRFS_ROOT_DELETING, &root->state))) {
670	btrfs_abort_transaction(trans, -EUCLEAN);
671	btrfs_crit(fs_info,
672	"attempt to COW block %llu on root %llu that is being deleted",
673	buf->start, btrfs_root_id(root));
674	return -EUCLEAN;
675	}
676
677	/*
678	* COWing must happen through a running transaction, which always
679	* matches the current fs generation (it's a transaction with a state
680	* less than TRANS_STATE_UNBLOCKED). If it doesn't, then turn the fs
681	* into error state to prevent the commit of any transaction.
682	*/
683	if (unlikely(trans->transaction != fs_info->running_transaction ||
684	trans->transid != fs_info->generation)) {
685	btrfs_abort_transaction(trans, -EUCLEAN);
686	btrfs_crit(fs_info,
687	"unexpected transaction when attempting to COW block %llu on root %llu, transaction %llu running transaction %llu fs generation %llu",
688	buf->start, btrfs_root_id(root), trans->transid,
689	fs_info->running_transaction->transid,
690	fs_info->generation);
691	return -EUCLEAN;
692	}
693
694	if (!should_cow_block(trans, root, buf)) {
695	*cow_ret = buf;
696	return 0;
697	}
698
699	search_start = round_down(buf->start, SZ_1G);
700
701	/*
702	* Before CoWing this block for later modification, check if it's
703	* the subtree root and do the delayed subtree trace if needed.
704	*
705	* Also We don't care about the error, as it's handled internally.
706	*/
707	btrfs_qgroup_trace_subtree_after_cow(trans, root, eb: buf);
708	return btrfs_force_cow_block(trans, root, buf, parent, parent_slot,
709	cow_ret, search_start, empty_size: 0, nest);
710	}
711	ALLOW_ERROR_INJECTION(btrfs_cow_block, ERRNO);
712
713	/*
714	* same as comp_keys only with two btrfs_key's
715	*/
716	int __pure btrfs_comp_cpu_keys(const struct btrfs_key *k1, const struct btrfs_key *k2)
717	{
718	if (k1->objectid > k2->objectid)
719	return 1;
720	if (k1->objectid < k2->objectid)
721	return -1;
722	if (k1->type > k2->type)
723	return 1;
724	if (k1->type < k2->type)
725	return -1;
726	if (k1->offset > k2->offset)
727	return 1;
728	if (k1->offset < k2->offset)
729	return -1;
730	return 0;
731	}
732
733	/*
734	* Search for a key in the given extent_buffer.
735	*
736	* The lower boundary for the search is specified by the slot number @first_slot.
737	* Use a value of 0 to search over the whole extent buffer. Works for both
738	* leaves and nodes.
739	*
740	* The slot in the extent buffer is returned via @slot. If the key exists in the
741	* extent buffer, then @slot will point to the slot where the key is, otherwise
742	* it points to the slot where you would insert the key.
743	*
744	* Slot may point to the total number of items (i.e. one position beyond the last
745	* key) if the key is bigger than the last key in the extent buffer.
746	*/
747	int btrfs_bin_search(const struct extent_buffer *eb, int first_slot,
748	const struct btrfs_key *key, int *slot)
749	{
750	unsigned long p;
751	int item_size;
752	/*
753	* Use unsigned types for the low and high slots, so that we get a more
754	* efficient division in the search loop below.
755	*/
756	u32 low = first_slot;
757	u32 high = btrfs_header_nritems(eb);
758	int ret;
759	const int key_size = sizeof(struct btrfs_disk_key);
760
761	if (unlikely(low > high)) {
762	btrfs_err(eb->fs_info,
763	"%s: low (%u) > high (%u) eb %llu owner %llu level %d",
764	__func__, low, high, eb->start,
765	btrfs_header_owner(eb), btrfs_header_level(eb));
766	return -EINVAL;
767	}
768
769	if (btrfs_header_level(eb) == 0) {
770	p = offsetof(struct btrfs_leaf, items);
771	item_size = sizeof(struct btrfs_item);
772	} else {
773	p = offsetof(struct btrfs_node, ptrs);
774	item_size = sizeof(struct btrfs_key_ptr);
775	}
776
777	while (low < high) {
778	const int unit_size = eb->folio_size;
779	unsigned long oil;
780	unsigned long offset;
781	struct btrfs_disk_key *tmp;
782	struct btrfs_disk_key unaligned;
783	int mid;
784
785	mid = (low + high) / 2;
786	offset = p + mid * item_size;
787	oil = get_eb_offset_in_folio(eb, offset);
788
789	if (oil + key_size <= unit_size) {
790	const unsigned long idx = get_eb_folio_index(eb, offset);
791	char *kaddr = folio_address(folio: eb->folios[idx]);
792
793	oil = get_eb_offset_in_folio(eb, offset);
794	tmp = (struct btrfs_disk_key *)(kaddr + oil);
795	} else {
796	read_extent_buffer(eb, dst: &unaligned, start: offset, len: key_size);
797	tmp = &unaligned;
798	}
799
800	ret = btrfs_comp_keys(disk_key: tmp, k2: key);
801
802	if (ret < 0)
803	low = mid + 1;
804	else if (ret > 0)
805	high = mid;
806	else {
807	*slot = mid;
808	return 0;
809	}
810	}
811	*slot = low;
812	return 1;
813	}
814
815	static void root_add_used_bytes(struct btrfs_root *root)
816	{
817	spin_lock(lock: &root->accounting_lock);
818	btrfs_set_root_used(s: &root->root_item,
819	val: btrfs_root_used(s: &root->root_item) + root->fs_info->nodesize);
820	spin_unlock(lock: &root->accounting_lock);
821	}
822
823	static void root_sub_used_bytes(struct btrfs_root *root)
824	{
825	spin_lock(lock: &root->accounting_lock);
826	btrfs_set_root_used(s: &root->root_item,
827	val: btrfs_root_used(s: &root->root_item) - root->fs_info->nodesize);
828	spin_unlock(lock: &root->accounting_lock);
829	}
830
831	/* given a node and slot number, this reads the blocks it points to. The
832	* extent buffer is returned with a reference taken (but unlocked).
833	*/
834	struct extent_buffer *btrfs_read_node_slot(struct extent_buffer *parent,
835	int slot)
836	{
837	int level = btrfs_header_level(eb: parent);
838	struct btrfs_tree_parent_check check = { 0 };
839	struct extent_buffer *eb;
840
841	if (slot < 0 || slot >= btrfs_header_nritems(eb: parent))
842	return ERR_PTR(error: -ENOENT);
843
844	ASSERT(level);
845
846	check.level = level - 1;
847	check.transid = btrfs_node_ptr_generation(eb: parent, nr: slot);
848	check.owner_root = btrfs_header_owner(eb: parent);
849	check.has_first_key = true;
850	btrfs_node_key_to_cpu(eb: parent, cpu_key: &check.first_key, nr: slot);
851
852	eb = read_tree_block(fs_info: parent->fs_info, bytenr: btrfs_node_blockptr(eb: parent, nr: slot),
853	check: &check);
854	if (IS_ERR(ptr: eb))
855	return eb;
856	if (unlikely(!extent_buffer_uptodate(eb))) {
857	free_extent_buffer(eb);
858	return ERR_PTR(error: -EIO);
859	}
860
861	return eb;
862	}
863
864	/*
865	* Promote a child node to become the new tree root.
866	*
867	* @trans: Transaction handle
868	* @root: Tree root structure to update
869	* @path: Path holding nodes and locks
870	* @level: Level of the parent (old root)
871	* @parent: The parent (old root) with exactly one item
872	*
873	* This helper is called during rebalancing when the root node contains only
874	* a single item (nritems == 1). We can reduce the tree height by promoting
875	* that child to become the new root and freeing the old root node. The path
876	* locks and references are updated accordingly.
877	*
878	* Return: 0 on success, negative errno on failure. The transaction is aborted
879	* on critical errors.
880	*/
881	static int promote_child_to_root(struct btrfs_trans_handle *trans,
882	struct btrfs_root *root, struct btrfs_path *path,
883	int level, struct extent_buffer *parent)
884	{
885	struct extent_buffer *child;
886	int ret;
887
888	ASSERT(btrfs_header_nritems(parent) == 1);
889
890	child = btrfs_read_node_slot(parent, slot: 0);
891	if (IS_ERR(ptr: child))
892	return PTR_ERR(ptr: child);
893
894	btrfs_tree_lock(eb: child);
895	ret = btrfs_cow_block(trans, root, buf: child, parent, parent_slot: 0, cow_ret: &child, nest: BTRFS_NESTING_COW);
896	if (ret) {
897	btrfs_tree_unlock(eb: child);
898	free_extent_buffer(eb: child);
899	return ret;
900	}
901
902	ret = btrfs_tree_mod_log_insert_root(old_root: root->node, new_root: child, log_removal: true);
903	if (unlikely(ret < 0)) {
904	btrfs_tree_unlock(eb: child);
905	free_extent_buffer(eb: child);
906	btrfs_abort_transaction(trans, ret);
907	return ret;
908	}
909	rcu_assign_pointer(root->node, child);
910
911	add_root_to_dirty_list(root);
912	btrfs_tree_unlock(eb: child);
913
914	path->locks[level] = 0;
915	path->nodes[level] = NULL;
916	btrfs_clear_buffer_dirty(trans, buf: parent);
917	btrfs_tree_unlock(eb: parent);
918	/* Once for the path. */
919	free_extent_buffer(eb: parent);
920
921	root_sub_used_bytes(root);
922	ret = btrfs_free_tree_block(trans, root_id: btrfs_root_id(root), buf: parent, parent: 0, last_ref: 1);
923	/* Once for the root ptr. */
924	free_extent_buffer_stale(eb: parent);
925	if (unlikely(ret < 0)) {
926	btrfs_abort_transaction(trans, ret);
927	return ret;
928	}
929
930	return 0;
931	}
932
933	/*
934	* node level balancing, used to make sure nodes are in proper order for
935	* item deletion. We balance from the top down, so we have to make sure
936	* that a deletion won't leave an node completely empty later on.
937	*/
938	static noinline int balance_level(struct btrfs_trans_handle *trans,
939	struct btrfs_root *root,
940	struct btrfs_path *path, int level)
941	{
942	struct btrfs_fs_info *fs_info = root->fs_info;
943	struct extent_buffer *right = NULL;
944	struct extent_buffer *mid;
945	struct extent_buffer *left = NULL;
946	struct extent_buffer *parent = NULL;
947	int ret = 0;
948	int wret;
949	int pslot;
950	int orig_slot = path->slots[level];
951	u64 orig_ptr;
952
953	ASSERT(level > 0);
954
955	mid = path->nodes[level];
956
957	WARN_ON(path->locks[level] != BTRFS_WRITE_LOCK);
958	WARN_ON(btrfs_header_generation(mid) != trans->transid);
959
960	orig_ptr = btrfs_node_blockptr(eb: mid, nr: orig_slot);
961
962	if (level < BTRFS_MAX_LEVEL - 1) {
963	parent = path->nodes[level + 1];
964	pslot = path->slots[level + 1];
965	}
966
967	/*
968	* deal with the case where there is only one pointer in the root
969	* by promoting the node below to a root
970	*/
971	if (!parent) {
972	if (btrfs_header_nritems(eb: mid) != 1)
973	return 0;
974
975	return promote_child_to_root(trans, root, path, level, parent: mid);
976	}
977	if (btrfs_header_nritems(eb: mid) >
978	BTRFS_NODEPTRS_PER_BLOCK(info: fs_info) / 4)
979	return 0;
980
981	if (pslot) {
982	left = btrfs_read_node_slot(parent, slot: pslot - 1);
983	if (IS_ERR(ptr: left)) {
984	ret = PTR_ERR(ptr: left);
985	left = NULL;
986	goto out;
987	}
988
989	btrfs_tree_lock_nested(eb: left, nest: BTRFS_NESTING_LEFT);
990	wret = btrfs_cow_block(trans, root, buf: left,
991	parent, parent_slot: pslot - 1, cow_ret: &left,
992	nest: BTRFS_NESTING_LEFT_COW);
993	if (wret) {
994	ret = wret;
995	goto out;
996	}
997	}
998
999	if (pslot + 1 < btrfs_header_nritems(eb: parent)) {
1000	right = btrfs_read_node_slot(parent, slot: pslot + 1);
1001	if (IS_ERR(ptr: right)) {
1002	ret = PTR_ERR(ptr: right);
1003	right = NULL;
1004	goto out;
1005	}
1006
1007	btrfs_tree_lock_nested(eb: right, nest: BTRFS_NESTING_RIGHT);
1008	wret = btrfs_cow_block(trans, root, buf: right,
1009	parent, parent_slot: pslot + 1, cow_ret: &right,
1010	nest: BTRFS_NESTING_RIGHT_COW);
1011	if (wret) {
1012	ret = wret;
1013	goto out;
1014	}
1015	}
1016
1017	/* first, try to make some room in the middle buffer */
1018	if (left) {
1019	orig_slot += btrfs_header_nritems(eb: left);
1020	wret = push_node_left(trans, dst: left, src: mid, empty: 1);
1021	if (wret < 0)
1022	ret = wret;
1023	}
1024
1025	/*
1026	* then try to empty the right most buffer into the middle
1027	*/
1028	if (right) {
1029	wret = push_node_left(trans, dst: mid, src: right, empty: 1);
1030	if (wret < 0 && wret != -ENOSPC)
1031	ret = wret;
1032	if (btrfs_header_nritems(eb: right) == 0) {
1033	btrfs_clear_buffer_dirty(trans, buf: right);
1034	btrfs_tree_unlock(eb: right);
1035	ret = btrfs_del_ptr(trans, root, path, level: level + 1, slot: pslot + 1);
1036	if (ret < 0) {
1037	free_extent_buffer_stale(eb: right);
1038	right = NULL;
1039	goto out;
1040	}
1041	root_sub_used_bytes(root);
1042	ret = btrfs_free_tree_block(trans, root_id: btrfs_root_id(root),
1043	buf: right, parent: 0, last_ref: 1);
1044	free_extent_buffer_stale(eb: right);
1045	right = NULL;
1046	if (unlikely(ret < 0)) {
1047	btrfs_abort_transaction(trans, ret);
1048	goto out;
1049	}
1050	} else {
1051	struct btrfs_disk_key right_key;
1052	btrfs_node_key(eb: right, disk_key: &right_key, nr: 0);
1053	ret = btrfs_tree_mod_log_insert_key(eb: parent, slot: pslot + 1,
1054	op: BTRFS_MOD_LOG_KEY_REPLACE);
1055	if (unlikely(ret < 0)) {
1056	btrfs_abort_transaction(trans, ret);
1057	goto out;
1058	}
1059	btrfs_set_node_key(eb: parent, disk_key: &right_key, nr: pslot + 1);
1060	btrfs_mark_buffer_dirty(trans, buf: parent);
1061	}
1062	}
1063	if (btrfs_header_nritems(eb: mid) == 1) {
1064	/*
1065	* we're not allowed to leave a node with one item in the
1066	* tree during a delete. A deletion from lower in the tree
1067	* could try to delete the only pointer in this node.
1068	* So, pull some keys from the left.
1069	* There has to be a left pointer at this point because
1070	* otherwise we would have pulled some pointers from the
1071	* right
1072	*/
1073	if (unlikely(!left)) {
1074	btrfs_crit(fs_info,
1075	"missing left child when middle child only has 1 item, parent bytenr %llu level %d mid bytenr %llu root %llu",
1076	parent->start, btrfs_header_level(parent),
1077	mid->start, btrfs_root_id(root));
1078	ret = -EUCLEAN;
1079	btrfs_abort_transaction(trans, ret);
1080	goto out;
1081	}
1082	wret = balance_node_right(trans, dst_buf: mid, src_buf: left);
1083	if (wret < 0) {
1084	ret = wret;
1085	goto out;
1086	}
1087	if (wret == 1) {
1088	wret = push_node_left(trans, dst: left, src: mid, empty: 1);
1089	if (wret < 0)
1090	ret = wret;
1091	}
1092	BUG_ON(wret == 1);
1093	}
1094	if (btrfs_header_nritems(eb: mid) == 0) {
1095	btrfs_clear_buffer_dirty(trans, buf: mid);
1096	btrfs_tree_unlock(eb: mid);
1097	ret = btrfs_del_ptr(trans, root, path, level: level + 1, slot: pslot);
1098	if (ret < 0) {
1099	free_extent_buffer_stale(eb: mid);
1100	mid = NULL;
1101	goto out;
1102	}
1103	root_sub_used_bytes(root);
1104	ret = btrfs_free_tree_block(trans, root_id: btrfs_root_id(root), buf: mid, parent: 0, last_ref: 1);
1105	free_extent_buffer_stale(eb: mid);
1106	mid = NULL;
1107	if (unlikely(ret < 0)) {
1108	btrfs_abort_transaction(trans, ret);
1109	goto out;
1110	}
1111	} else {
1112	/* update the parent key to reflect our changes */
1113	struct btrfs_disk_key mid_key;
1114	btrfs_node_key(eb: mid, disk_key: &mid_key, nr: 0);
1115	ret = btrfs_tree_mod_log_insert_key(eb: parent, slot: pslot,
1116	op: BTRFS_MOD_LOG_KEY_REPLACE);
1117	if (unlikely(ret < 0)) {
1118	btrfs_abort_transaction(trans, ret);
1119	goto out;
1120	}
1121	btrfs_set_node_key(eb: parent, disk_key: &mid_key, nr: pslot);
1122	btrfs_mark_buffer_dirty(trans, buf: parent);
1123	}
1124
1125	/* update the path */
1126	if (left) {
1127	if (btrfs_header_nritems(eb: left) > orig_slot) {
1128	/* left was locked after cow */
1129	path->nodes[level] = left;
1130	path->slots[level + 1] -= 1;
1131	path->slots[level] = orig_slot;
1132	/* Left is now owned by path. */
1133	left = NULL;
1134	if (mid) {
1135	btrfs_tree_unlock(eb: mid);
1136	free_extent_buffer(eb: mid);
1137	}
1138	} else {
1139	orig_slot -= btrfs_header_nritems(eb: left);
1140	path->slots[level] = orig_slot;
1141	}
1142	}
1143	/* double check we haven't messed things up */
1144	if (orig_ptr !=
1145	btrfs_node_blockptr(eb: path->nodes[level], nr: path->slots[level]))
1146	BUG();
1147	out:
1148	if (right) {
1149	btrfs_tree_unlock(eb: right);
1150	free_extent_buffer(eb: right);
1151	}
1152	if (left) {
1153	btrfs_tree_unlock(eb: left);
1154	free_extent_buffer(eb: left);
1155	}
1156	return ret;
1157	}
1158
1159	/* Node balancing for insertion. Here we only split or push nodes around
1160	* when they are completely full. This is also done top down, so we
1161	* have to be pessimistic.
1162	*/
1163	static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
1164	struct btrfs_root *root,
1165	struct btrfs_path *path, int level)
1166	{
1167	struct btrfs_fs_info *fs_info = root->fs_info;
1168	struct extent_buffer *right = NULL;
1169	struct extent_buffer *mid;
1170	struct extent_buffer *left = NULL;
1171	struct extent_buffer *parent = NULL;
1172	int ret = 0;
1173	int wret;
1174	int pslot;
1175	int orig_slot = path->slots[level];
1176
1177	if (level == 0)
1178	return 1;
1179
1180	mid = path->nodes[level];
1181	WARN_ON(btrfs_header_generation(mid) != trans->transid);
1182
1183	if (level < BTRFS_MAX_LEVEL - 1) {
1184	parent = path->nodes[level + 1];
1185	pslot = path->slots[level + 1];
1186	}
1187
1188	if (!parent)
1189	return 1;
1190
1191	/* first, try to make some room in the middle buffer */
1192	if (pslot) {
1193	u32 left_nr;
1194
1195	left = btrfs_read_node_slot(parent, slot: pslot - 1);
1196	if (IS_ERR(ptr: left))
1197	return PTR_ERR(ptr: left);
1198
1199	btrfs_tree_lock_nested(eb: left, nest: BTRFS_NESTING_LEFT);
1200
1201	left_nr = btrfs_header_nritems(eb: left);
1202	if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(info: fs_info) - 1) {
1203	wret = 1;
1204	} else {
1205	ret = btrfs_cow_block(trans, root, buf: left, parent,
1206	parent_slot: pslot - 1, cow_ret: &left,
1207	nest: BTRFS_NESTING_LEFT_COW);
1208	if (ret)
1209	wret = 1;
1210	else {
1211	wret = push_node_left(trans, dst: left, src: mid, empty: 0);
1212	}
1213	}
1214	if (wret < 0)
1215	ret = wret;
1216	if (wret == 0) {
1217	struct btrfs_disk_key disk_key;
1218	orig_slot += left_nr;
1219	btrfs_node_key(eb: mid, disk_key: &disk_key, nr: 0);
1220	ret = btrfs_tree_mod_log_insert_key(eb: parent, slot: pslot,
1221	op: BTRFS_MOD_LOG_KEY_REPLACE);
1222	if (unlikely(ret < 0)) {
1223	btrfs_tree_unlock(eb: left);
1224	free_extent_buffer(eb: left);
1225	btrfs_abort_transaction(trans, ret);
1226	return ret;
1227	}
1228	btrfs_set_node_key(eb: parent, disk_key: &disk_key, nr: pslot);
1229	btrfs_mark_buffer_dirty(trans, buf: parent);
1230	if (btrfs_header_nritems(eb: left) > orig_slot) {
1231	path->nodes[level] = left;
1232	path->slots[level + 1] -= 1;
1233	path->slots[level] = orig_slot;
1234	btrfs_tree_unlock(eb: mid);
1235	free_extent_buffer(eb: mid);
1236	} else {
1237	orig_slot -=
1238	btrfs_header_nritems(eb: left);
1239	path->slots[level] = orig_slot;
1240	btrfs_tree_unlock(eb: left);
1241	free_extent_buffer(eb: left);
1242	}
1243	return 0;
1244	}
1245	btrfs_tree_unlock(eb: left);
1246	free_extent_buffer(eb: left);
1247	}
1248
1249	/*
1250	* then try to empty the right most buffer into the middle
1251	*/
1252	if (pslot + 1 < btrfs_header_nritems(eb: parent)) {
1253	u32 right_nr;
1254
1255	right = btrfs_read_node_slot(parent, slot: pslot + 1);
1256	if (IS_ERR(ptr: right))
1257	return PTR_ERR(ptr: right);
1258
1259	btrfs_tree_lock_nested(eb: right, nest: BTRFS_NESTING_RIGHT);
1260
1261	right_nr = btrfs_header_nritems(eb: right);
1262	if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(info: fs_info) - 1) {
1263	wret = 1;
1264	} else {
1265	ret = btrfs_cow_block(trans, root, buf: right,
1266	parent, parent_slot: pslot + 1,
1267	cow_ret: &right, nest: BTRFS_NESTING_RIGHT_COW);
1268	if (ret)
1269	wret = 1;
1270	else {
1271	wret = balance_node_right(trans, dst_buf: right, src_buf: mid);
1272	}
1273	}
1274	if (wret < 0)
1275	ret = wret;
1276	if (wret == 0) {
1277	struct btrfs_disk_key disk_key;
1278
1279	btrfs_node_key(eb: right, disk_key: &disk_key, nr: 0);
1280	ret = btrfs_tree_mod_log_insert_key(eb: parent, slot: pslot + 1,
1281	op: BTRFS_MOD_LOG_KEY_REPLACE);
1282	if (unlikely(ret < 0)) {
1283	btrfs_tree_unlock(eb: right);
1284	free_extent_buffer(eb: right);
1285	btrfs_abort_transaction(trans, ret);
1286	return ret;
1287	}
1288	btrfs_set_node_key(eb: parent, disk_key: &disk_key, nr: pslot + 1);
1289	btrfs_mark_buffer_dirty(trans, buf: parent);
1290
1291	if (btrfs_header_nritems(eb: mid) <= orig_slot) {
1292	path->nodes[level] = right;
1293	path->slots[level + 1] += 1;
1294	path->slots[level] = orig_slot -
1295	btrfs_header_nritems(eb: mid);
1296	btrfs_tree_unlock(eb: mid);
1297	free_extent_buffer(eb: mid);
1298	} else {
1299	btrfs_tree_unlock(eb: right);
1300	free_extent_buffer(eb: right);
1301	}
1302	return 0;
1303	}
1304	btrfs_tree_unlock(eb: right);
1305	free_extent_buffer(eb: right);
1306	}
1307	return 1;
1308	}
1309
1310	/*
1311	* readahead one full node of leaves, finding things that are close
1312	* to the block in 'slot', and triggering ra on them.
1313	*/
1314	static void reada_for_search(struct btrfs_fs_info *fs_info,
1315	const struct btrfs_path *path,
1316	int level, int slot, u64 objectid)
1317	{
1318	struct extent_buffer *node;
1319	struct btrfs_disk_key disk_key;
1320	u32 nritems;
1321	u64 search;
1322	u64 target;
1323	u64 nread = 0;
1324	u64 nread_max;
1325	u32 nr;
1326	u32 blocksize;
1327	u32 nscan = 0;
1328
1329	if (level != 1 && path->reada != READA_FORWARD_ALWAYS)
1330	return;
1331
1332	if (!path->nodes[level])
1333	return;
1334
1335	node = path->nodes[level];
1336
1337	/*
1338	* Since the time between visiting leaves is much shorter than the time
1339	* between visiting nodes, limit read ahead of nodes to 1, to avoid too
1340	* much IO at once (possibly random).
1341	*/
1342	if (path->reada == READA_FORWARD_ALWAYS) {
1343	if (level > 1)
1344	nread_max = node->fs_info->nodesize;
1345	else
1346	nread_max = SZ_128K;
1347	} else {
1348	nread_max = SZ_64K;
1349	}
1350
1351	search = btrfs_node_blockptr(eb: node, nr: slot);
1352	blocksize = fs_info->nodesize;
1353	if (path->reada != READA_FORWARD_ALWAYS) {
1354	struct extent_buffer *eb;
1355
1356	eb = find_extent_buffer(fs_info, start: search);
1357	if (eb) {
1358	free_extent_buffer(eb);
1359	return;
1360	}
1361	}
1362
1363	target = search;
1364
1365	nritems = btrfs_header_nritems(eb: node);
1366	nr = slot;
1367
1368	while (1) {
1369	if (path->reada == READA_BACK) {
1370	if (nr == 0)
1371	break;
1372	nr--;
1373	} else if (path->reada == READA_FORWARD ||
1374	path->reada == READA_FORWARD_ALWAYS) {
1375	nr++;
1376	if (nr >= nritems)
1377	break;
1378	}
1379	if (path->reada == READA_BACK && objectid) {
1380	btrfs_node_key(eb: node, disk_key: &disk_key, nr);
1381	if (btrfs_disk_key_objectid(s: &disk_key) != objectid)
1382	break;
1383	}
1384	search = btrfs_node_blockptr(eb: node, nr);
1385	if (path->reada == READA_FORWARD_ALWAYS ||
1386	(search <= target && target - search <= 65536) ||
1387	(search > target && search - target <= 65536)) {
1388	btrfs_readahead_node_child(node, slot: nr);
1389	nread += blocksize;
1390	}
1391	nscan++;
1392	if (nread > nread_max || nscan > 32)
1393	break;
1394	}
1395	}
1396
1397	static noinline void reada_for_balance(const struct btrfs_path *path, int level)
1398	{
1399	struct extent_buffer *parent;
1400	int slot;
1401	int nritems;
1402
1403	parent = path->nodes[level + 1];
1404	if (!parent)
1405	return;
1406
1407	nritems = btrfs_header_nritems(eb: parent);
1408	slot = path->slots[level + 1];
1409
1410	if (slot > 0)
1411	btrfs_readahead_node_child(node: parent, slot: slot - 1);
1412	if (slot + 1 < nritems)
1413	btrfs_readahead_node_child(node: parent, slot: slot + 1);
1414	}
1415
1416
1417	/*
1418	* when we walk down the tree, it is usually safe to unlock the higher layers
1419	* in the tree. The exceptions are when our path goes through slot 0, because
1420	* operations on the tree might require changing key pointers higher up in the
1421	* tree.
1422	*
1423	* callers might also have set path->keep_locks, which tells this code to keep
1424	* the lock if the path points to the last slot in the block. This is part of
1425	* walking through the tree, and selecting the next slot in the higher block.
1426	*
1427	* lowest_unlock sets the lowest level in the tree we're allowed to unlock. so
1428	* if lowest_unlock is 1, level 0 won't be unlocked
1429	*/
1430	static noinline void unlock_up(struct btrfs_path *path, int level,
1431	int lowest_unlock, int min_write_lock_level,
1432	int *write_lock_level)
1433	{
1434	int i;
1435	int skip_level = level;
1436	bool check_skip = true;
1437
1438	for (i = level; i < BTRFS_MAX_LEVEL; i++) {
1439	if (!path->nodes[i])
1440	break;
1441	if (!path->locks[i])
1442	break;
1443
1444	if (check_skip) {
1445	if (path->slots[i] == 0) {
1446	skip_level = i + 1;
1447	continue;
1448	}
1449
1450	if (path->keep_locks) {
1451	u32 nritems;
1452
1453	nritems = btrfs_header_nritems(eb: path->nodes[i]);
1454	if (nritems < 1 || path->slots[i] >= nritems - 1) {
1455	skip_level = i + 1;
1456	continue;
1457	}
1458	}
1459	}
1460
1461	if (i >= lowest_unlock && i > skip_level) {
1462	btrfs_tree_unlock_rw(eb: path->nodes[i], rw: path->locks[i]);
1463	check_skip = false;
1464	path->locks[i] = 0;
1465	if (write_lock_level &&
1466	i > min_write_lock_level &&
1467	i <= *write_lock_level) {
1468	*write_lock_level = i - 1;
1469	}
1470	}
1471	}
1472	}
1473
1474	/*
1475	* Helper function for btrfs_search_slot() and other functions that do a search
1476	* on a btree. The goal is to find a tree block in the cache (the radix tree at
1477	* fs_info->buffer_radix), but if we can't find it, or it's not up to date, read
1478	* its pages from disk.
1479	*
1480	* Returns -EAGAIN, with the path unlocked, if the caller needs to repeat the
1481	* whole btree search, starting again from the current root node.
1482	*/
1483	static int
1484	read_block_for_search(struct btrfs_root *root, struct btrfs_path *p,
1485	struct extent_buffer **eb_ret, int slot,
1486	const struct btrfs_key *key)
1487	{
1488	struct btrfs_fs_info *fs_info = root->fs_info;
1489	struct btrfs_tree_parent_check check = { 0 };
1490	u64 blocknr;
1491	struct extent_buffer *tmp = NULL;
1492	int ret = 0;
1493	int ret2;
1494	int parent_level;
1495	bool read_tmp = false;
1496	bool tmp_locked = false;
1497	bool path_released = false;
1498
1499	blocknr = btrfs_node_blockptr(eb: *eb_ret, nr: slot);
1500	parent_level = btrfs_header_level(eb: *eb_ret);
1501	btrfs_node_key_to_cpu(eb: *eb_ret, cpu_key: &check.first_key, nr: slot);
1502	check.has_first_key = true;
1503	check.level = parent_level - 1;
1504	check.transid = btrfs_node_ptr_generation(eb: *eb_ret, nr: slot);
1505	check.owner_root = btrfs_root_id(root);
1506
1507	/*
1508	* If we need to read an extent buffer from disk and we are holding locks
1509	* on upper level nodes, we unlock all the upper nodes before reading the
1510	* extent buffer, and then return -EAGAIN to the caller as it needs to
1511	* restart the search. We don't release the lock on the current level
1512	* because we need to walk this node to figure out which blocks to read.
1513	*/
1514	tmp = find_extent_buffer(fs_info, start: blocknr);
1515	if (tmp) {
1516	if (p->reada == READA_FORWARD_ALWAYS)
1517	reada_for_search(fs_info, path: p, level: parent_level, slot, objectid: key->objectid);
1518
1519	/* first we do an atomic uptodate check */
1520	if (btrfs_buffer_uptodate(buf: tmp, parent_transid: check.transid, atomic: true) > 0) {
1521	/*
1522	* Do extra check for first_key, eb can be stale due to
1523	* being cached, read from scrub, or have multiple
1524	* parents (shared tree blocks).
1525	*/
1526	if (unlikely(btrfs_verify_level_key(tmp, &check))) {
1527	ret = -EUCLEAN;
1528	goto out;
1529	}
1530	*eb_ret = tmp;
1531	tmp = NULL;
1532	ret = 0;
1533	goto out;
1534	}
1535
1536	if (p->nowait) {
1537	ret = -EAGAIN;
1538	goto out;
1539	}
1540
1541	if (!p->skip_locking) {
1542	btrfs_unlock_up_safe(path: p, level: parent_level + 1);
1543	btrfs_maybe_reset_lockdep_class(root, eb: tmp);
1544	tmp_locked = true;
1545	btrfs_tree_read_lock(eb: tmp);
1546	btrfs_release_path(p);
1547	ret = -EAGAIN;
1548	path_released = true;
1549	}
1550
1551	/* Now we're allowed to do a blocking uptodate check. */
1552	ret2 = btrfs_read_extent_buffer(buf: tmp, check: &check);
1553	if (ret2) {
1554	ret = ret2;
1555	goto out;
1556	}
1557
1558	if (ret == 0) {
1559	ASSERT(!tmp_locked);
1560	*eb_ret = tmp;
1561	tmp = NULL;
1562	}
1563	goto out;
1564	} else if (p->nowait) {
1565	ret = -EAGAIN;
1566	goto out;
1567	}
1568
1569	if (!p->skip_locking) {
1570	btrfs_unlock_up_safe(path: p, level: parent_level + 1);
1571	ret = -EAGAIN;
1572	}
1573
1574	if (p->reada != READA_NONE)
1575	reada_for_search(fs_info, path: p, level: parent_level, slot, objectid: key->objectid);
1576
1577	tmp = btrfs_find_create_tree_block(fs_info, bytenr: blocknr, owner_root: check.owner_root, level: check.level);
1578	if (IS_ERR(ptr: tmp)) {
1579	ret = PTR_ERR(ptr: tmp);
1580	tmp = NULL;
1581	goto out;
1582	}
1583	read_tmp = true;
1584
1585	if (!p->skip_locking) {
1586	ASSERT(ret == -EAGAIN);
1587	btrfs_maybe_reset_lockdep_class(root, eb: tmp);
1588	tmp_locked = true;
1589	btrfs_tree_read_lock(eb: tmp);
1590	btrfs_release_path(p);
1591	path_released = true;
1592	}
1593
1594	/* Now we're allowed to do a blocking uptodate check. */
1595	ret2 = btrfs_read_extent_buffer(buf: tmp, check: &check);
1596	if (ret2) {
1597	ret = ret2;
1598	goto out;
1599	}
1600
1601	/*
1602	* If the read above didn't mark this buffer up to date,
1603	* it will never end up being up to date. Set ret to EIO now
1604	* and give up so that our caller doesn't loop forever
1605	* on our EAGAINs.
1606	*/
1607	if (unlikely(!extent_buffer_uptodate(tmp))) {
1608	ret = -EIO;
1609	goto out;
1610	}
1611
1612	if (ret == 0) {
1613	ASSERT(!tmp_locked);
1614	*eb_ret = tmp;
1615	tmp = NULL;
1616	}
1617	out:
1618	if (tmp) {
1619	if (tmp_locked)
1620	btrfs_tree_read_unlock(eb: tmp);
1621	if (read_tmp && ret && ret != -EAGAIN)
1622	free_extent_buffer_stale(eb: tmp);
1623	else
1624	free_extent_buffer(eb: tmp);
1625	}
1626	if (ret && !path_released)
1627	btrfs_release_path(p);
1628
1629	return ret;
1630	}
1631
1632	/*
1633	* helper function for btrfs_search_slot. This does all of the checks
1634	* for node-level blocks and does any balancing required based on
1635	* the ins_len.
1636	*
1637	* If no extra work was required, zero is returned. If we had to
1638	* drop the path, -EAGAIN is returned and btrfs_search_slot must
1639	* start over
1640	*/
1641	static int
1642	setup_nodes_for_search(struct btrfs_trans_handle *trans,
1643	struct btrfs_root *root, struct btrfs_path *p,
1644	struct extent_buffer *b, int level, int ins_len,
1645	int *write_lock_level)
1646	{
1647	struct btrfs_fs_info *fs_info = root->fs_info;
1648	int ret = 0;
1649
1650	if ((p->search_for_split || ins_len > 0) && btrfs_header_nritems(eb: b) >=
1651	BTRFS_NODEPTRS_PER_BLOCK(info: fs_info) - 3) {
1652
1653	if (*write_lock_level < level + 1) {
1654	*write_lock_level = level + 1;
1655	btrfs_release_path(p);
1656	return -EAGAIN;
1657	}
1658
1659	reada_for_balance(path: p, level);
1660	ret = split_node(trans, root, path: p, level);
1661
1662	b = p->nodes[level];
1663	} else if (ins_len < 0 && btrfs_header_nritems(eb: b) <
1664	BTRFS_NODEPTRS_PER_BLOCK(info: fs_info) / 2) {
1665
1666	if (*write_lock_level < level + 1) {
1667	*write_lock_level = level + 1;
1668	btrfs_release_path(p);
1669	return -EAGAIN;
1670	}
1671
1672	reada_for_balance(path: p, level);
1673	ret = balance_level(trans, root, path: p, level);
1674	if (ret)
1675	return ret;
1676
1677	b = p->nodes[level];
1678	if (!b) {
1679	btrfs_release_path(p);
1680	return -EAGAIN;
1681	}
1682	BUG_ON(btrfs_header_nritems(b) == 1);
1683	}
1684	return ret;
1685	}
1686
1687	int btrfs_find_item(struct btrfs_root *fs_root, struct btrfs_path *path,
1688	u64 iobjectid, u64 ioff, u8 key_type,
1689	struct btrfs_key *found_key)
1690	{
1691	int ret;
1692	struct btrfs_key key;
1693	struct extent_buffer *eb;
1694
1695	ASSERT(path);
1696	ASSERT(found_key);
1697
1698	key.type = key_type;
1699	key.objectid = iobjectid;
1700	key.offset = ioff;
1701
1702	ret = btrfs_search_slot(NULL, root: fs_root, key: &key, p: path, ins_len: 0, cow: 0);
1703	if (ret < 0)
1704	return ret;
1705
1706	eb = path->nodes[0];
1707	if (ret && path->slots[0] >= btrfs_header_nritems(eb)) {
1708	ret = btrfs_next_leaf(root: fs_root, path);
1709	if (ret)
1710	return ret;
1711	eb = path->nodes[0];
1712	}
1713
1714	btrfs_item_key_to_cpu(eb, cpu_key: found_key, nr: path->slots[0]);
1715	if (found_key->type != key.type ||
1716	found_key->objectid != key.objectid)
1717	return 1;
1718
1719	return 0;
1720	}
1721
1722	static struct extent_buffer *btrfs_search_slot_get_root(struct btrfs_root *root,
1723	struct btrfs_path *p,
1724	int write_lock_level)
1725	{
1726	struct extent_buffer *b;
1727	int root_lock = 0;
1728	int level = 0;
1729
1730	if (p->search_commit_root) {
1731	b = root->commit_root;
1732	refcount_inc(r: &b->refs);
1733	level = btrfs_header_level(eb: b);
1734	/*
1735	* Ensure that all callers have set skip_locking when
1736	* p->search_commit_root is true.
1737	*/
1738	ASSERT(p->skip_locking);
1739
1740	goto out;
1741	}
1742
1743	if (p->skip_locking) {
1744	b = btrfs_root_node(root);
1745	level = btrfs_header_level(eb: b);
1746	goto out;
1747	}
1748
1749	/* We try very hard to do read locks on the root */
1750	root_lock = BTRFS_READ_LOCK;
1751
1752	/*
1753	* If the level is set to maximum, we can skip trying to get the read
1754	* lock.
1755	*/
1756	if (write_lock_level < BTRFS_MAX_LEVEL) {
1757	/*
1758	* We don't know the level of the root node until we actually
1759	* have it read locked
1760	*/
1761	if (p->nowait) {
1762	b = btrfs_try_read_lock_root_node(root);
1763	if (IS_ERR(ptr: b))
1764	return b;
1765	} else {
1766	b = btrfs_read_lock_root_node(root);
1767	}
1768	level = btrfs_header_level(eb: b);
1769	if (level > write_lock_level)
1770	goto out;
1771
1772	/* Whoops, must trade for write lock */
1773	btrfs_tree_read_unlock(eb: b);
1774	free_extent_buffer(eb: b);
1775	}
1776
1777	b = btrfs_lock_root_node(root);
1778	root_lock = BTRFS_WRITE_LOCK;
1779
1780	/* The level might have changed, check again */
1781	level = btrfs_header_level(eb: b);
1782
1783	out:
1784	/*
1785	* The root may have failed to write out at some point, and thus is no
1786	* longer valid, return an error in this case.
1787	*/
1788	if (unlikely(!extent_buffer_uptodate(b))) {
1789	if (root_lock)
1790	btrfs_tree_unlock_rw(eb: b, rw: root_lock);
1791	free_extent_buffer(eb: b);
1792	return ERR_PTR(error: -EIO);
1793	}
1794
1795	p->nodes[level] = b;
1796	if (!p->skip_locking)
1797	p->locks[level] = root_lock;
1798	/*
1799	* Callers are responsible for dropping b's references.
1800	*/
1801	return b;
1802	}
1803
1804	/*
1805	* Replace the extent buffer at the lowest level of the path with a cloned
1806	* version. The purpose is to be able to use it safely, after releasing the
1807	* commit root semaphore, even if relocation is happening in parallel, the
1808	* transaction used for relocation is committed and the extent buffer is
1809	* reallocated in the next transaction.
1810	*
1811	* This is used in a context where the caller does not prevent transaction
1812	* commits from happening, either by holding a transaction handle or holding
1813	* some lock, while it's doing searches through a commit root.
1814	* At the moment it's only used for send operations.
1815	*/
1816	static int finish_need_commit_sem_search(struct btrfs_path *path)
1817	{
1818	const int i = path->lowest_level;
1819	const int slot = path->slots[i];
1820	struct extent_buffer *lowest = path->nodes[i];
1821	struct extent_buffer *clone;
1822
1823	ASSERT(path->need_commit_sem);
1824
1825	if (!lowest)
1826	return 0;
1827
1828	lockdep_assert_held_read(&lowest->fs_info->commit_root_sem);
1829
1830	clone = btrfs_clone_extent_buffer(src: lowest);
1831	if (!clone)
1832	return -ENOMEM;
1833
1834	btrfs_release_path(p: path);
1835	path->nodes[i] = clone;
1836	path->slots[i] = slot;
1837
1838	return 0;
1839	}
1840
1841	static inline int search_for_key_slot(const struct extent_buffer *eb,
1842	int search_low_slot,
1843	const struct btrfs_key *key,
1844	int prev_cmp,
1845	int *slot)
1846	{
1847	/*
1848	* If a previous call to btrfs_bin_search() on a parent node returned an
1849	* exact match (prev_cmp == 0), we can safely assume the target key will
1850	* always be at slot 0 on lower levels, since each key pointer
1851	* (struct btrfs_key_ptr) refers to the lowest key accessible from the
1852	* subtree it points to. Thus we can skip searching lower levels.
1853	*/
1854	if (prev_cmp == 0) {
1855	*slot = 0;
1856	return 0;
1857	}
1858
1859	return btrfs_bin_search(eb, first_slot: search_low_slot, key, slot);
1860	}
1861
1862	static int search_leaf(struct btrfs_trans_handle *trans,
1863	struct btrfs_root *root,
1864	const struct btrfs_key *key,
1865	struct btrfs_path *path,
1866	int ins_len,
1867	int prev_cmp)
1868	{
1869	struct extent_buffer *leaf = path->nodes[0];
1870	int leaf_free_space = -1;
1871	int search_low_slot = 0;
1872	int ret;
1873	bool do_bin_search = true;
1874
1875	/*
1876	* If we are doing an insertion, the leaf has enough free space and the
1877	* destination slot for the key is not slot 0, then we can unlock our
1878	* write lock on the parent, and any other upper nodes, before doing the
1879	* binary search on the leaf (with search_for_key_slot()), allowing other
1880	* tasks to lock the parent and any other upper nodes.
1881	*/
1882	if (ins_len > 0) {
1883	/*
1884	* Cache the leaf free space, since we will need it later and it
1885	* will not change until then.
1886	*/
1887	leaf_free_space = btrfs_leaf_free_space(leaf);
1888
1889	/*
1890	* !path->locks[1] means we have a single node tree, the leaf is
1891	* the root of the tree.
1892	*/
1893	if (path->locks[1] && leaf_free_space >= ins_len) {
1894	struct btrfs_disk_key first_key;
1895
1896	ASSERT(btrfs_header_nritems(leaf) > 0);
1897	btrfs_item_key(eb: leaf, disk_key: &first_key, nr: 0);
1898
1899	/*
1900	* Doing the extra comparison with the first key is cheap,
1901	* taking into account that the first key is very likely
1902	* already in a cache line because it immediately follows
1903	* the extent buffer's header and we have recently accessed
1904	* the header's level field.
1905	*/
1906	ret = btrfs_comp_keys(disk_key: &first_key, k2: key);
1907	if (ret < 0) {
1908	/*
1909	* The first key is smaller than the key we want
1910	* to insert, so we are safe to unlock all upper
1911	* nodes and we have to do the binary search.
1912	*
1913	* We do use btrfs_unlock_up_safe() and not
1914	* unlock_up() because the later does not unlock
1915	* nodes with a slot of 0 - we can safely unlock
1916	* any node even if its slot is 0 since in this
1917	* case the key does not end up at slot 0 of the
1918	* leaf and there's no need to split the leaf.
1919	*/
1920	btrfs_unlock_up_safe(path, level: 1);
1921	search_low_slot = 1;
1922	} else {
1923	/*
1924	* The first key is >= then the key we want to
1925	* insert, so we can skip the binary search as
1926	* the target key will be at slot 0.
1927	*
1928	* We can not unlock upper nodes when the key is
1929	* less than the first key, because we will need
1930	* to update the key at slot 0 of the parent node
1931	* and possibly of other upper nodes too.
1932	* If the key matches the first key, then we can
1933	* unlock all the upper nodes, using
1934	* btrfs_unlock_up_safe() instead of unlock_up()
1935	* as stated above.
1936	*/
1937	if (ret == 0)
1938	btrfs_unlock_up_safe(path, level: 1);
1939	/*
1940	* ret is already 0 or 1, matching the result of
1941	* a btrfs_bin_search() call, so there is no need
1942	* to adjust it.
1943	*/
1944	do_bin_search = false;
1945	path->slots[0] = 0;
1946	}
1947	}
1948	}
1949
1950	if (do_bin_search) {
1951	ret = search_for_key_slot(eb: leaf, search_low_slot, key,
1952	prev_cmp, slot: &path->slots[0]);
1953	if (ret < 0)
1954	return ret;
1955	}
1956
1957	if (ins_len > 0) {
1958	/*
1959	* Item key already exists. In this case, if we are allowed to
1960	* insert the item (for example, in dir_item case, item key
1961	* collision is allowed), it will be merged with the original
1962	* item. Only the item size grows, no new btrfs item will be
1963	* added. If search_for_extension is not set, ins_len already
1964	* accounts the size btrfs_item, deduct it here so leaf space
1965	* check will be correct.
1966	*/
1967	if (ret == 0 && !path->search_for_extension) {
1968	ASSERT(ins_len >= sizeof(struct btrfs_item));
1969	ins_len -= sizeof(struct btrfs_item);
1970	}
1971
1972	ASSERT(leaf_free_space >= 0);
1973
1974	if (leaf_free_space < ins_len) {
1975	int ret2;
1976
1977	ret2 = split_leaf(trans, root, ins_key: key, path, data_size: ins_len, extend: (ret == 0));
1978	ASSERT(ret2 <= 0);
1979	if (WARN_ON(ret2 > 0))
1980	ret2 = -EUCLEAN;
1981	if (ret2)
1982	ret = ret2;
1983	}
1984	}
1985
1986	return ret;
1987	}
1988
1989	/*
1990	* Look for a key in a tree and perform necessary modifications to preserve
1991	* tree invariants.
1992	*
1993	* @trans: Handle of transaction, used when modifying the tree
1994	* @p: Holds all btree nodes along the search path
1995	* @root: The root node of the tree
1996	* @key: The key we are looking for
1997	* @ins_len: Indicates purpose of search:
1998	* >0 for inserts it's size of item inserted (*)
1999	* <0 for deletions
2000	* 0 for plain searches, not modifying the tree
2001	*
2002	* (*) If size of item inserted doesn't include
2003	* sizeof(struct btrfs_item), then p->search_for_extension must
2004	* be set.
2005	* @cow: boolean should CoW operations be performed. Must always be 1
2006	* when modifying the tree.
2007	*
2008	* If @ins_len > 0, nodes and leaves will be split as we walk down the tree.
2009	* If @ins_len < 0, nodes will be merged as we walk down the tree (if possible)
2010	*
2011	* If @key is found, 0 is returned and you can find the item in the leaf level
2012	* of the path (level 0)
2013	*
2014	* If @key isn't found, 1 is returned and the leaf level of the path (level 0)
2015	* points to the slot where it should be inserted
2016	*
2017	* If an error is encountered while searching the tree a negative error number
2018	* is returned
2019	*/
2020	int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2021	const struct btrfs_key *key, struct btrfs_path *p,
2022	int ins_len, int cow)
2023	{
2024	struct btrfs_fs_info *fs_info;
2025	struct extent_buffer *b;
2026	int slot;
2027	int ret;
2028	int level;
2029	int lowest_unlock = 1;
2030	/* everything at write_lock_level or lower must be write locked */
2031	int write_lock_level = 0;
2032	u8 lowest_level = 0;
2033	int min_write_lock_level;
2034	int prev_cmp;
2035
2036	if (!root)
2037	return -EINVAL;
2038
2039	fs_info = root->fs_info;
2040	might_sleep();
2041
2042	lowest_level = p->lowest_level;
2043	WARN_ON(lowest_level && ins_len > 0);
2044	WARN_ON(p->nodes[0] != NULL);
2045	BUG_ON(!cow && ins_len);
2046
2047	/*
2048	* For now only allow nowait for read only operations. There's no
2049	* strict reason why we can't, we just only need it for reads so it's
2050	* only implemented for reads.
2051	*/
2052	ASSERT(!p->nowait || !cow);
2053
2054	if (ins_len < 0) {
2055	lowest_unlock = 2;
2056
2057	/* when we are removing items, we might have to go up to level
2058	* two as we update tree pointers Make sure we keep write
2059	* for those levels as well
2060	*/
2061	write_lock_level = 2;
2062	} else if (ins_len > 0) {
2063	/*
2064	* for inserting items, make sure we have a write lock on
2065	* level 1 so we can update keys
2066	*/
2067	write_lock_level = 1;
2068	}
2069
2070	if (!cow)
2071	write_lock_level = -1;
2072
2073	if (cow && (p->keep_locks || p->lowest_level))
2074	write_lock_level = BTRFS_MAX_LEVEL;
2075
2076	min_write_lock_level = write_lock_level;
2077
2078	if (p->need_commit_sem) {
2079	ASSERT(p->search_commit_root);
2080	if (p->nowait) {
2081	if (!down_read_trylock(sem: &fs_info->commit_root_sem))
2082	return -EAGAIN;
2083	} else {
2084	down_read(sem: &fs_info->commit_root_sem);
2085	}
2086	}
2087
2088	again:
2089	prev_cmp = -1;
2090	b = btrfs_search_slot_get_root(root, p, write_lock_level);
2091	if (IS_ERR(ptr: b)) {
2092	ret = PTR_ERR(ptr: b);
2093	goto done;
2094	}
2095
2096	while (b) {
2097	int dec = 0;
2098	int ret2;
2099
2100	level = btrfs_header_level(eb: b);
2101
2102	if (cow) {
2103	bool last_level = (level == (BTRFS_MAX_LEVEL - 1));
2104
2105	/*
2106	* if we don't really need to cow this block
2107	* then we don't want to set the path blocking,
2108	* so we test it here
2109	*/
2110	if (!should_cow_block(trans, root, buf: b))
2111	goto cow_done;
2112
2113	/*
2114	* must have write locks on this node and the
2115	* parent
2116	*/
2117	if (level > write_lock_level ||
2118	(level + 1 > write_lock_level &&
2119	level + 1 < BTRFS_MAX_LEVEL &&
2120	p->nodes[level + 1])) {
2121	write_lock_level = level + 1;
2122	btrfs_release_path(p);
2123	goto again;
2124	}
2125
2126	if (last_level)
2127	ret2 = btrfs_cow_block(trans, root, buf: b, NULL, parent_slot: 0,
2128	cow_ret: &b, nest: BTRFS_NESTING_COW);
2129	else
2130	ret2 = btrfs_cow_block(trans, root, buf: b,
2131	parent: p->nodes[level + 1],
2132	parent_slot: p->slots[level + 1], cow_ret: &b,
2133	nest: BTRFS_NESTING_COW);
2134	if (ret2) {
2135	ret = ret2;
2136	goto done;
2137	}
2138	}
2139	cow_done:
2140	p->nodes[level] = b;
2141
2142	/*
2143	* we have a lock on b and as long as we aren't changing
2144	* the tree, there is no way to for the items in b to change.
2145	* It is safe to drop the lock on our parent before we
2146	* go through the expensive btree search on b.
2147	*
2148	* If we're inserting or deleting (ins_len != 0), then we might
2149	* be changing slot zero, which may require changing the parent.
2150	* So, we can't drop the lock until after we know which slot
2151	* we're operating on.
2152	*/
2153	if (!ins_len && !p->keep_locks) {
2154	int u = level + 1;
2155
2156	if (u < BTRFS_MAX_LEVEL && p->locks[u]) {
2157	btrfs_tree_unlock_rw(eb: p->nodes[u], rw: p->locks[u]);
2158	p->locks[u] = 0;
2159	}
2160	}
2161
2162	if (level == 0) {
2163	if (ins_len > 0)
2164	ASSERT(write_lock_level >= 1);
2165
2166	ret = search_leaf(trans, root, key, path: p, ins_len, prev_cmp);
2167	if (!p->search_for_split)
2168	unlock_up(path: p, level, lowest_unlock,
2169	min_write_lock_level, NULL);
2170	goto done;
2171	}
2172
2173	ret = search_for_key_slot(eb: b, search_low_slot: 0, key, prev_cmp, slot: &slot);
2174	if (ret < 0)
2175	goto done;
2176	prev_cmp = ret;
2177
2178	if (ret && slot > 0) {
2179	dec = 1;
2180	slot--;
2181	}
2182	p->slots[level] = slot;
2183	ret2 = setup_nodes_for_search(trans, root, p, b, level, ins_len,
2184	write_lock_level: &write_lock_level);
2185	if (ret2 == -EAGAIN)
2186	goto again;
2187	if (ret2) {
2188	ret = ret2;
2189	goto done;
2190	}
2191	b = p->nodes[level];
2192	slot = p->slots[level];
2193
2194	/*
2195	* Slot 0 is special, if we change the key we have to update
2196	* the parent pointer which means we must have a write lock on
2197	* the parent
2198	*/
2199	if (slot == 0 && ins_len && write_lock_level < level + 1) {
2200	write_lock_level = level + 1;
2201	btrfs_release_path(p);
2202	goto again;
2203	}
2204
2205	unlock_up(path: p, level, lowest_unlock, min_write_lock_level,
2206	write_lock_level: &write_lock_level);
2207
2208	if (level == lowest_level) {
2209	if (dec)
2210	p->slots[level]++;
2211	goto done;
2212	}
2213
2214	ret2 = read_block_for_search(root, p, eb_ret: &b, slot, key);
2215	if (ret2 == -EAGAIN && !p->nowait)
2216	goto again;
2217	if (ret2) {
2218	ret = ret2;
2219	goto done;
2220	}
2221
2222	if (!p->skip_locking) {
2223	level = btrfs_header_level(eb: b);
2224
2225	btrfs_maybe_reset_lockdep_class(root, eb: b);
2226
2227	if (level <= write_lock_level) {
2228	btrfs_tree_lock(eb: b);
2229	p->locks[level] = BTRFS_WRITE_LOCK;
2230	} else {
2231	if (p->nowait) {
2232	if (!btrfs_try_tree_read_lock(eb: b)) {
2233	free_extent_buffer(eb: b);
2234	ret = -EAGAIN;
2235	goto done;
2236	}
2237	} else {
2238	btrfs_tree_read_lock(eb: b);
2239	}
2240	p->locks[level] = BTRFS_READ_LOCK;
2241	}
2242	p->nodes[level] = b;
2243	}
2244	}
2245	ret = 1;
2246	done:
2247	if (ret < 0 && !p->skip_release_on_error)
2248	btrfs_release_path(p);
2249
2250	if (p->need_commit_sem) {
2251	int ret2;
2252
2253	ret2 = finish_need_commit_sem_search(path: p);
2254	up_read(sem: &fs_info->commit_root_sem);
2255	if (ret2)
2256	ret = ret2;
2257	}
2258
2259	return ret;
2260	}
2261	ALLOW_ERROR_INJECTION(btrfs_search_slot, ERRNO);
2262
2263	/*
2264	* Like btrfs_search_slot, this looks for a key in the given tree. It uses the
2265	* current state of the tree together with the operations recorded in the tree
2266	* modification log to search for the key in a previous version of this tree, as
2267	* denoted by the time_seq parameter.
2268	*
2269	* Naturally, there is no support for insert, delete or cow operations.
2270	*
2271	* The resulting path and return value will be set up as if we called
2272	* btrfs_search_slot at that point in time with ins_len and cow both set to 0.
2273	*/
2274	int btrfs_search_old_slot(struct btrfs_root *root, const struct btrfs_key *key,
2275	struct btrfs_path *p, u64 time_seq)
2276	{
2277	struct btrfs_fs_info *fs_info = root->fs_info;
2278	struct extent_buffer *b;
2279	int slot;
2280	int ret;
2281	int level;
2282	int lowest_unlock = 1;
2283	u8 lowest_level = 0;
2284
2285	lowest_level = p->lowest_level;
2286	WARN_ON(p->nodes[0] != NULL);
2287	ASSERT(!p->nowait);
2288
2289	if (p->search_commit_root) {
2290	BUG_ON(time_seq);
2291	return btrfs_search_slot(NULL, root, key, p, ins_len: 0, cow: 0);
2292	}
2293
2294	again:
2295	b = btrfs_get_old_root(root, time_seq);
2296	if (unlikely(!b)) {
2297	ret = -EIO;
2298	goto done;
2299	}
2300	level = btrfs_header_level(eb: b);
2301	p->locks[level] = BTRFS_READ_LOCK;
2302
2303	while (b) {
2304	int dec = 0;
2305	int ret2;
2306
2307	level = btrfs_header_level(eb: b);
2308	p->nodes[level] = b;
2309
2310	/*
2311	* we have a lock on b and as long as we aren't changing
2312	* the tree, there is no way to for the items in b to change.
2313	* It is safe to drop the lock on our parent before we
2314	* go through the expensive btree search on b.
2315	*/
2316	btrfs_unlock_up_safe(path: p, level: level + 1);
2317
2318	ret = btrfs_bin_search(eb: b, first_slot: 0, key, slot: &slot);
2319	if (ret < 0)
2320	goto done;
2321
2322	if (level == 0) {
2323	p->slots[level] = slot;
2324	unlock_up(path: p, level, lowest_unlock, min_write_lock_level: 0, NULL);
2325	goto done;
2326	}
2327
2328	if (ret && slot > 0) {
2329	dec = 1;
2330	slot--;
2331	}
2332	p->slots[level] = slot;
2333	unlock_up(path: p, level, lowest_unlock, min_write_lock_level: 0, NULL);
2334
2335	if (level == lowest_level) {
2336	if (dec)
2337	p->slots[level]++;
2338	goto done;
2339	}
2340
2341	ret2 = read_block_for_search(root, p, eb_ret: &b, slot, key);
2342	if (ret2 == -EAGAIN && !p->nowait)
2343	goto again;
2344	if (ret2) {
2345	ret = ret2;
2346	goto done;
2347	}
2348
2349	level = btrfs_header_level(eb: b);
2350	btrfs_tree_read_lock(eb: b);
2351	b = btrfs_tree_mod_log_rewind(fs_info, eb: b, time_seq);
2352	if (!b) {
2353	ret = -ENOMEM;
2354	goto done;
2355	}
2356	p->locks[level] = BTRFS_READ_LOCK;
2357	p->nodes[level] = b;
2358	}
2359	ret = 1;
2360	done:
2361	if (ret < 0)
2362	btrfs_release_path(p);
2363
2364	return ret;
2365	}
2366
2367	/*
2368	* Search the tree again to find a leaf with smaller keys.
2369	* Returns 0 if it found something.
2370	* Returns 1 if there are no smaller keys.
2371	* Returns < 0 on error.
2372	*
2373	* This may release the path, and so you may lose any locks held at the
2374	* time you call it.
2375	*/
2376	static int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
2377	{
2378	struct btrfs_key key;
2379	struct btrfs_key orig_key;
2380	struct btrfs_disk_key found_key;
2381	int ret;
2382
2383	btrfs_item_key_to_cpu(eb: path->nodes[0], cpu_key: &key, nr: 0);
2384	orig_key = key;
2385
2386	if (key.offset > 0) {
2387	key.offset--;
2388	} else if (key.type > 0) {
2389	key.type--;
2390	key.offset = (u64)-1;
2391	} else if (key.objectid > 0) {
2392	key.objectid--;
2393	key.type = (u8)-1;
2394	key.offset = (u64)-1;
2395	} else {
2396	return 1;
2397	}
2398
2399	btrfs_release_path(p: path);
2400	ret = btrfs_search_slot(NULL, root, key: &key, p: path, ins_len: 0, cow: 0);
2401	if (ret <= 0)
2402	return ret;
2403
2404	/*
2405	* Previous key not found. Even if we were at slot 0 of the leaf we had
2406	* before releasing the path and calling btrfs_search_slot(), we now may
2407	* be in a slot pointing to the same original key - this can happen if
2408	* after we released the path, one of more items were moved from a
2409	* sibling leaf into the front of the leaf we had due to an insertion
2410	* (see push_leaf_right()).
2411	* If we hit this case and our slot is > 0 and just decrement the slot
2412	* so that the caller does not process the same key again, which may or
2413	* may not break the caller, depending on its logic.
2414	*/
2415	if (path->slots[0] < btrfs_header_nritems(eb: path->nodes[0])) {
2416	btrfs_item_key(eb: path->nodes[0], disk_key: &found_key, nr: path->slots[0]);
2417	ret = btrfs_comp_keys(disk_key: &found_key, k2: &orig_key);
2418	if (ret == 0) {
2419	if (path->slots[0] > 0) {
2420	path->slots[0]--;
2421	return 0;
2422	}
2423	/*
2424	* At slot 0, same key as before, it means orig_key is
2425	* the lowest, leftmost, key in the tree. We're done.
2426	*/
2427	return 1;
2428	}
2429	}
2430
2431	btrfs_item_key(eb: path->nodes[0], disk_key: &found_key, nr: 0);
2432	ret = btrfs_comp_keys(disk_key: &found_key, k2: &key);
2433	/*
2434	* We might have had an item with the previous key in the tree right
2435	* before we released our path. And after we released our path, that
2436	* item might have been pushed to the first slot (0) of the leaf we
2437	* were holding due to a tree balance. Alternatively, an item with the
2438	* previous key can exist as the only element of a leaf (big fat item).
2439	* Therefore account for these 2 cases, so that our callers (like
2440	* btrfs_previous_item) don't miss an existing item with a key matching
2441	* the previous key we computed above.
2442	*/
2443	if (ret <= 0)
2444	return 0;
2445	return 1;
2446	}
2447
2448	/*
2449	* helper to use instead of search slot if no exact match is needed but
2450	* instead the next or previous item should be returned.
2451	* When find_higher is true, the next higher item is returned, the next lower
2452	* otherwise.
2453	* When return_any and find_higher are both true, and no higher item is found,
2454	* return the next lower instead.
2455	* When return_any is true and find_higher is false, and no lower item is found,
2456	* return the next higher instead.
2457	* It returns 0 if any item is found, 1 if none is found (tree empty), and
2458	* < 0 on error
2459	*/
2460	int btrfs_search_slot_for_read(struct btrfs_root *root,
2461	const struct btrfs_key *key,
2462	struct btrfs_path *p, int find_higher,
2463	int return_any)
2464	{
2465	int ret;
2466	struct extent_buffer *leaf;
2467
2468	again:
2469	ret = btrfs_search_slot(NULL, root, key, p, ins_len: 0, cow: 0);
2470	if (ret <= 0)
2471	return ret;
2472	/*
2473	* a return value of 1 means the path is at the position where the
2474	* item should be inserted. Normally this is the next bigger item,
2475	* but in case the previous item is the last in a leaf, path points
2476	* to the first free slot in the previous leaf, i.e. at an invalid
2477	* item.
2478	*/
2479	leaf = p->nodes[0];
2480
2481	if (find_higher) {
2482	if (p->slots[0] >= btrfs_header_nritems(eb: leaf)) {
2483	ret = btrfs_next_leaf(root, path: p);
2484	if (ret <= 0)
2485	return ret;
2486	if (!return_any)
2487	return 1;
2488	/*
2489	* no higher item found, return the next
2490	* lower instead
2491	*/
2492	return_any = 0;
2493	find_higher = 0;
2494	btrfs_release_path(p);
2495	goto again;
2496	}
2497	} else {
2498	if (p->slots[0] == 0) {
2499	ret = btrfs_prev_leaf(root, path: p);
2500	if (ret < 0)
2501	return ret;
2502	if (!ret) {
2503	leaf = p->nodes[0];
2504	if (p->slots[0] == btrfs_header_nritems(eb: leaf))
2505	p->slots[0]--;
2506	return 0;
2507	}
2508	if (!return_any)
2509	return 1;
2510	/*
2511	* no lower item found, return the next
2512	* higher instead
2513	*/
2514	return_any = 0;
2515	find_higher = 1;
2516	btrfs_release_path(p);
2517	goto again;
2518	} else {
2519	--p->slots[0];
2520	}
2521	}
2522	return 0;
2523	}
2524
2525	/*
2526	* Execute search and call btrfs_previous_item to traverse backwards if the item
2527	* was not found.
2528	*
2529	* Return 0 if found, 1 if not found and < 0 if error.
2530	*/
2531	int btrfs_search_backwards(struct btrfs_root *root, struct btrfs_key *key,
2532	struct btrfs_path *path)
2533	{
2534	int ret;
2535
2536	ret = btrfs_search_slot(NULL, root, key, p: path, ins_len: 0, cow: 0);
2537	if (ret > 0)
2538	ret = btrfs_previous_item(root, path, min_objectid: key->objectid, type: key->type);
2539
2540	if (ret == 0)
2541	btrfs_item_key_to_cpu(eb: path->nodes[0], cpu_key: key, nr: path->slots[0]);
2542
2543	return ret;
2544	}
2545
2546	/*
2547	* Search for a valid slot for the given path.
2548	*
2549	* @root: The root node of the tree.
2550	* @key: Will contain a valid item if found.
2551	* @path: The starting point to validate the slot.
2552	*
2553	* Return: 0 if the item is valid
2554	* 1 if not found
2555	* <0 if error.
2556	*/
2557	int btrfs_get_next_valid_item(struct btrfs_root *root, struct btrfs_key *key,
2558	struct btrfs_path *path)
2559	{
2560	if (path->slots[0] >= btrfs_header_nritems(eb: path->nodes[0])) {
2561	int ret;
2562
2563	ret = btrfs_next_leaf(root, path);
2564	if (ret)
2565	return ret;
2566	}
2567
2568	btrfs_item_key_to_cpu(eb: path->nodes[0], cpu_key: key, nr: path->slots[0]);
2569	return 0;
2570	}
2571
2572	/*
2573	* adjust the pointers going up the tree, starting at level
2574	* making sure the right key of each node is points to 'key'.
2575	* This is used after shifting pointers to the left, so it stops
2576	* fixing up pointers when a given leaf/node is not in slot 0 of the
2577	* higher levels
2578	*
2579	*/
2580	static void fixup_low_keys(struct btrfs_trans_handle *trans,
2581	const struct btrfs_path *path,
2582	const struct btrfs_disk_key *key, int level)
2583	{
2584	int i;
2585	struct extent_buffer *t;
2586	int ret;
2587
2588	for (i = level; i < BTRFS_MAX_LEVEL; i++) {
2589	int tslot = path->slots[i];
2590
2591	if (!path->nodes[i])
2592	break;
2593	t = path->nodes[i];
2594	ret = btrfs_tree_mod_log_insert_key(eb: t, slot: tslot,
2595	op: BTRFS_MOD_LOG_KEY_REPLACE);
2596	BUG_ON(ret < 0);
2597	btrfs_set_node_key(eb: t, disk_key: key, nr: tslot);
2598	btrfs_mark_buffer_dirty(trans, buf: path->nodes[i]);
2599	if (tslot != 0)
2600	break;
2601	}
2602	}
2603
2604	/*
2605	* update item key.
2606	*
2607	* This function isn't completely safe. It's the caller's responsibility
2608	* that the new key won't break the order
2609	*/
2610	void btrfs_set_item_key_safe(struct btrfs_trans_handle *trans,
2611	const struct btrfs_path *path,
2612	const struct btrfs_key *new_key)
2613	{
2614	struct btrfs_fs_info *fs_info = trans->fs_info;
2615	struct btrfs_disk_key disk_key;
2616	struct extent_buffer *eb;
2617	int slot;
2618
2619	eb = path->nodes[0];
2620	slot = path->slots[0];
2621	if (slot > 0) {
2622	btrfs_item_key(eb, disk_key: &disk_key, nr: slot - 1);
2623	if (unlikely(btrfs_comp_keys(&disk_key, new_key) >= 0)) {
2624	btrfs_print_leaf(l: eb);
2625	btrfs_crit(fs_info,
2626	"slot %u key " BTRFS_KEY_FMT " new key " BTRFS_KEY_FMT,
2627	slot, btrfs_disk_key_objectid(&disk_key),
2628	btrfs_disk_key_type(&disk_key),
2629	btrfs_disk_key_offset(&disk_key),
2630	BTRFS_KEY_FMT_VALUE(new_key));
2631	BUG();
2632	}
2633	}
2634	if (slot < btrfs_header_nritems(eb) - 1) {
2635	btrfs_item_key(eb, disk_key: &disk_key, nr: slot + 1);
2636	if (unlikely(btrfs_comp_keys(&disk_key, new_key) <= 0)) {
2637	btrfs_print_leaf(l: eb);
2638	btrfs_crit(fs_info,
2639	"slot %u key " BTRFS_KEY_FMT " new key " BTRFS_KEY_FMT,
2640	slot, btrfs_disk_key_objectid(&disk_key),
2641	btrfs_disk_key_type(&disk_key),
2642	btrfs_disk_key_offset(&disk_key),
2643	BTRFS_KEY_FMT_VALUE(new_key));
2644	BUG();
2645	}
2646	}
2647
2648	btrfs_cpu_key_to_disk(disk_key: &disk_key, cpu_key: new_key);
2649	btrfs_set_item_key(eb, disk_key: &disk_key, nr: slot);
2650	btrfs_mark_buffer_dirty(trans, buf: eb);
2651	if (slot == 0)
2652	fixup_low_keys(trans, path, key: &disk_key, level: 1);
2653	}
2654
2655	/*
2656	* Check key order of two sibling extent buffers.
2657	*
2658	* Return true if something is wrong.
2659	* Return false if everything is fine.
2660	*
2661	* Tree-checker only works inside one tree block, thus the following
2662	* corruption can not be detected by tree-checker:
2663	*
2664	* Leaf @left | Leaf @right
2665	* --------------------------------------------------------------
2666	* | 1 | 2 | 3 | 4 | 5 | f6 | | 7 | 8 |
2667	*
2668	* Key f6 in leaf @left itself is valid, but not valid when the next
2669	* key in leaf @right is 7.
2670	* This can only be checked at tree block merge time.
2671	* And since tree checker has ensured all key order in each tree block
2672	* is correct, we only need to bother the last key of @left and the first
2673	* key of @right.
2674	*/
2675	static bool check_sibling_keys(const struct extent_buffer *left,
2676	const struct extent_buffer *right)
2677	{
2678	struct btrfs_key left_last;
2679	struct btrfs_key right_first;
2680	int level = btrfs_header_level(eb: left);
2681	int nr_left = btrfs_header_nritems(eb: left);
2682	int nr_right = btrfs_header_nritems(eb: right);
2683
2684	/* No key to check in one of the tree blocks */
2685	if (!nr_left || !nr_right)
2686	return false;
2687
2688	if (level) {
2689	btrfs_node_key_to_cpu(eb: left, cpu_key: &left_last, nr: nr_left - 1);
2690	btrfs_node_key_to_cpu(eb: right, cpu_key: &right_first, nr: 0);
2691	} else {
2692	btrfs_item_key_to_cpu(eb: left, cpu_key: &left_last, nr: nr_left - 1);
2693	btrfs_item_key_to_cpu(eb: right, cpu_key: &right_first, nr: 0);
2694	}
2695
2696	if (unlikely(btrfs_comp_cpu_keys(&left_last, &right_first) >= 0)) {
2697	btrfs_crit(left->fs_info, "left extent buffer:");
2698	btrfs_print_tree(c: left, follow: false);
2699	btrfs_crit(left->fs_info, "right extent buffer:");
2700	btrfs_print_tree(c: right, follow: false);
2701	btrfs_crit(left->fs_info,
2702	"bad key order, sibling blocks, left last " BTRFS_KEY_FMT " right first " BTRFS_KEY_FMT,
2703	BTRFS_KEY_FMT_VALUE(&left_last),
2704	BTRFS_KEY_FMT_VALUE(&right_first));
2705	return true;
2706	}
2707	return false;
2708	}
2709
2710	/*
2711	* try to push data from one node into the next node left in the
2712	* tree.
2713	*
2714	* returns 0 if some ptrs were pushed left, < 0 if there was some horrible
2715	* error, and > 0 if there was no room in the left hand block.
2716	*/
2717	static int push_node_left(struct btrfs_trans_handle *trans,
2718	struct extent_buffer *dst,
2719	struct extent_buffer *src, bool empty)
2720	{
2721	struct btrfs_fs_info *fs_info = trans->fs_info;
2722	int push_items = 0;
2723	int src_nritems;
2724	int dst_nritems;
2725	int ret = 0;
2726
2727	src_nritems = btrfs_header_nritems(eb: src);
2728	dst_nritems = btrfs_header_nritems(eb: dst);
2729	push_items = BTRFS_NODEPTRS_PER_BLOCK(info: fs_info) - dst_nritems;
2730	WARN_ON(btrfs_header_generation(src) != trans->transid);
2731	WARN_ON(btrfs_header_generation(dst) != trans->transid);
2732
2733	if (!empty && src_nritems <= 8)
2734	return 1;
2735
2736	if (push_items <= 0)
2737	return 1;
2738
2739	if (empty) {
2740	push_items = min(src_nritems, push_items);
2741	if (push_items < src_nritems) {
2742	/* leave at least 8 pointers in the node if
2743	* we aren't going to empty it
2744	*/
2745	if (src_nritems - push_items < 8) {
2746	if (push_items <= 8)
2747	return 1;
2748	push_items -= 8;
2749	}
2750	}
2751	} else
2752	push_items = min(src_nritems - 8, push_items);
2753
2754	/* dst is the left eb, src is the middle eb */
2755	if (unlikely(check_sibling_keys(dst, src))) {
2756	ret = -EUCLEAN;
2757	btrfs_abort_transaction(trans, ret);
2758	return ret;
2759	}
2760	ret = btrfs_tree_mod_log_eb_copy(dst, src, dst_offset: dst_nritems, src_offset: 0, nr_items: push_items);
2761	if (unlikely(ret)) {
2762	btrfs_abort_transaction(trans, ret);
2763	return ret;
2764	}
2765	copy_extent_buffer(dst, src,
2766	dst_offset: btrfs_node_key_ptr_offset(eb: dst, nr: dst_nritems),
2767	src_offset: btrfs_node_key_ptr_offset(eb: src, nr: 0),
2768	len: push_items * sizeof(struct btrfs_key_ptr));
2769
2770	if (push_items < src_nritems) {
2771	/*
2772	* btrfs_tree_mod_log_eb_copy handles logging the move, so we
2773	* don't need to do an explicit tree mod log operation for it.
2774	*/
2775	memmove_extent_buffer(dst: src, dst_offset: btrfs_node_key_ptr_offset(eb: src, nr: 0),
2776	src_offset: btrfs_node_key_ptr_offset(eb: src, nr: push_items),
2777	len: (src_nritems - push_items) *
2778	sizeof(struct btrfs_key_ptr));
2779	}
2780	btrfs_set_header_nritems(eb: src, val: src_nritems - push_items);
2781	btrfs_set_header_nritems(eb: dst, val: dst_nritems + push_items);
2782	btrfs_mark_buffer_dirty(trans, buf: src);
2783	btrfs_mark_buffer_dirty(trans, buf: dst);
2784
2785	return ret;
2786	}
2787
2788	/*
2789	* try to push data from one node into the next node right in the
2790	* tree.
2791	*
2792	* returns 0 if some ptrs were pushed, < 0 if there was some horrible
2793	* error, and > 0 if there was no room in the right hand block.
2794	*
2795	* this will only push up to 1/2 the contents of the left node over
2796	*/
2797	static int balance_node_right(struct btrfs_trans_handle *trans,
2798	struct extent_buffer *dst,
2799	struct extent_buffer *src)
2800	{
2801	struct btrfs_fs_info *fs_info = trans->fs_info;
2802	int push_items = 0;
2803	int max_push;
2804	int src_nritems;
2805	int dst_nritems;
2806	int ret = 0;
2807
2808	WARN_ON(btrfs_header_generation(src) != trans->transid);
2809	WARN_ON(btrfs_header_generation(dst) != trans->transid);
2810
2811	src_nritems = btrfs_header_nritems(eb: src);
2812	dst_nritems = btrfs_header_nritems(eb: dst);
2813	push_items = BTRFS_NODEPTRS_PER_BLOCK(info: fs_info) - dst_nritems;
2814	if (push_items <= 0)
2815	return 1;
2816
2817	if (src_nritems < 4)
2818	return 1;
2819
2820	max_push = src_nritems / 2 + 1;
2821	/* don't try to empty the node */
2822	if (max_push >= src_nritems)
2823	return 1;
2824
2825	if (max_push < push_items)
2826	push_items = max_push;
2827
2828	/* dst is the right eb, src is the middle eb */
2829	if (unlikely(check_sibling_keys(src, dst))) {
2830	ret = -EUCLEAN;
2831	btrfs_abort_transaction(trans, ret);
2832	return ret;
2833	}
2834
2835	/*
2836	* btrfs_tree_mod_log_eb_copy handles logging the move, so we don't
2837	* need to do an explicit tree mod log operation for it.
2838	*/
2839	memmove_extent_buffer(dst, dst_offset: btrfs_node_key_ptr_offset(eb: dst, nr: push_items),
2840	src_offset: btrfs_node_key_ptr_offset(eb: dst, nr: 0),
2841	len: (dst_nritems) *
2842	sizeof(struct btrfs_key_ptr));
2843
2844	ret = btrfs_tree_mod_log_eb_copy(dst, src, dst_offset: 0, src_offset: src_nritems - push_items,
2845	nr_items: push_items);
2846	if (unlikely(ret)) {
2847	btrfs_abort_transaction(trans, ret);
2848	return ret;
2849	}
2850	copy_extent_buffer(dst, src,
2851	dst_offset: btrfs_node_key_ptr_offset(eb: dst, nr: 0),
2852	src_offset: btrfs_node_key_ptr_offset(eb: src, nr: src_nritems - push_items),
2853	len: push_items * sizeof(struct btrfs_key_ptr));
2854
2855	btrfs_set_header_nritems(eb: src, val: src_nritems - push_items);
2856	btrfs_set_header_nritems(eb: dst, val: dst_nritems + push_items);
2857
2858	btrfs_mark_buffer_dirty(trans, buf: src);
2859	btrfs_mark_buffer_dirty(trans, buf: dst);
2860
2861	return ret;
2862	}
2863
2864	/*
2865	* helper function to insert a new root level in the tree.
2866	* A new node is allocated, and a single item is inserted to
2867	* point to the existing root
2868	*
2869	* returns zero on success or < 0 on failure.
2870	*/
2871	static noinline int insert_new_root(struct btrfs_trans_handle *trans,
2872	struct btrfs_root *root,
2873	struct btrfs_path *path, int level)
2874	{
2875	u64 lower_gen;
2876	struct extent_buffer *lower;
2877	struct extent_buffer *c;
2878	struct extent_buffer *old;
2879	struct btrfs_disk_key lower_key;
2880	int ret;
2881
2882	BUG_ON(path->nodes[level]);
2883	BUG_ON(path->nodes[level-1] != root->node);
2884
2885	lower = path->nodes[level-1];
2886	if (level == 1)
2887	btrfs_item_key(eb: lower, disk_key: &lower_key, nr: 0);
2888	else
2889	btrfs_node_key(eb: lower, disk_key: &lower_key, nr: 0);
2890
2891	c = btrfs_alloc_tree_block(trans, root, parent: 0, root_objectid: btrfs_root_id(root),
2892	key: &lower_key, level, hint: root->node->start, empty_size: 0,
2893	reloc_src_root: 0, nest: BTRFS_NESTING_NEW_ROOT);
2894	if (IS_ERR(ptr: c))
2895	return PTR_ERR(ptr: c);
2896
2897	root_add_used_bytes(root);
2898
2899	btrfs_set_header_nritems(eb: c, val: 1);
2900	btrfs_set_node_key(eb: c, disk_key: &lower_key, nr: 0);
2901	btrfs_set_node_blockptr(eb: c, nr: 0, val: lower->start);
2902	lower_gen = btrfs_header_generation(eb: lower);
2903	WARN_ON(lower_gen != trans->transid);
2904
2905	btrfs_set_node_ptr_generation(eb: c, nr: 0, val: lower_gen);
2906
2907	btrfs_mark_buffer_dirty(trans, buf: c);
2908
2909	old = root->node;
2910	ret = btrfs_tree_mod_log_insert_root(old_root: root->node, new_root: c, log_removal: false);
2911	if (ret < 0) {
2912	int ret2;
2913
2914	btrfs_clear_buffer_dirty(trans, buf: c);
2915	ret2 = btrfs_free_tree_block(trans, root_id: btrfs_root_id(root), buf: c, parent: 0, last_ref: 1);
2916	if (unlikely(ret2 < 0))
2917	btrfs_abort_transaction(trans, ret2);
2918	btrfs_tree_unlock(eb: c);
2919	free_extent_buffer(eb: c);
2920	return ret;
2921	}
2922	rcu_assign_pointer(root->node, c);
2923
2924	/* the super has an extra ref to root->node */
2925	free_extent_buffer(eb: old);
2926
2927	add_root_to_dirty_list(root);
2928	refcount_inc(r: &c->refs);
2929	path->nodes[level] = c;
2930	path->locks[level] = BTRFS_WRITE_LOCK;
2931	path->slots[level] = 0;
2932	return 0;
2933	}
2934
2935	/*
2936	* worker function to insert a single pointer in a node.
2937	* the node should have enough room for the pointer already
2938	*
2939	* slot and level indicate where you want the key to go, and
2940	* blocknr is the block the key points to.
2941	*/
2942	static int insert_ptr(struct btrfs_trans_handle *trans,
2943	const struct btrfs_path *path,
2944	const struct btrfs_disk_key *key, u64 bytenr,
2945	int slot, int level)
2946	{
2947	struct extent_buffer *lower;
2948	int nritems;
2949	int ret;
2950
2951	BUG_ON(!path->nodes[level]);
2952	btrfs_assert_tree_write_locked(eb: path->nodes[level]);
2953	lower = path->nodes[level];
2954	nritems = btrfs_header_nritems(eb: lower);
2955	BUG_ON(slot > nritems);
2956	BUG_ON(nritems == BTRFS_NODEPTRS_PER_BLOCK(trans->fs_info));
2957	if (slot != nritems) {
2958	if (level) {
2959	ret = btrfs_tree_mod_log_insert_move(eb: lower, dst_slot: slot + 1,
2960	src_slot: slot, nr_items: nritems - slot);
2961	if (unlikely(ret < 0)) {
2962	btrfs_abort_transaction(trans, ret);
2963	return ret;
2964	}
2965	}
2966	memmove_extent_buffer(dst: lower,
2967	dst_offset: btrfs_node_key_ptr_offset(eb: lower, nr: slot + 1),
2968	src_offset: btrfs_node_key_ptr_offset(eb: lower, nr: slot),
2969	len: (nritems - slot) * sizeof(struct btrfs_key_ptr));
2970	}
2971	if (level) {
2972	ret = btrfs_tree_mod_log_insert_key(eb: lower, slot,
2973	op: BTRFS_MOD_LOG_KEY_ADD);
2974	if (unlikely(ret < 0)) {
2975	btrfs_abort_transaction(trans, ret);
2976	return ret;
2977	}
2978	}
2979	btrfs_set_node_key(eb: lower, disk_key: key, nr: slot);
2980	btrfs_set_node_blockptr(eb: lower, nr: slot, val: bytenr);
2981	WARN_ON(trans->transid == 0);
2982	btrfs_set_node_ptr_generation(eb: lower, nr: slot, val: trans->transid);
2983	btrfs_set_header_nritems(eb: lower, val: nritems + 1);
2984	btrfs_mark_buffer_dirty(trans, buf: lower);
2985
2986	return 0;
2987	}
2988
2989	/*
2990	* split the node at the specified level in path in two.
2991	* The path is corrected to point to the appropriate node after the split
2992	*
2993	* Before splitting this tries to make some room in the node by pushing
2994	* left and right, if either one works, it returns right away.
2995	*
2996	* returns 0 on success and < 0 on failure
2997	*/
2998	static noinline int split_node(struct btrfs_trans_handle *trans,
2999	struct btrfs_root *root,
3000	struct btrfs_path *path, int level)
3001	{
3002	struct btrfs_fs_info *fs_info = root->fs_info;
3003	struct extent_buffer *c;
3004	struct extent_buffer *split;
3005	struct btrfs_disk_key disk_key;
3006	int mid;
3007	int ret;
3008	u32 c_nritems;
3009
3010	c = path->nodes[level];
3011	WARN_ON(btrfs_header_generation(c) != trans->transid);
3012	if (c == root->node) {
3013	/*
3014	* trying to split the root, lets make a new one
3015	*
3016	* tree mod log: We don't log_removal old root in
3017	* insert_new_root, because that root buffer will be kept as a
3018	* normal node. We are going to log removal of half of the
3019	* elements below with btrfs_tree_mod_log_eb_copy(). We're
3020	* holding a tree lock on the buffer, which is why we cannot
3021	* race with other tree_mod_log users.
3022	*/
3023	ret = insert_new_root(trans, root, path, level: level + 1);
3024	if (ret)
3025	return ret;
3026	} else {
3027	ret = push_nodes_for_insert(trans, root, path, level);
3028	c = path->nodes[level];
3029	if (!ret && btrfs_header_nritems(eb: c) <
3030	BTRFS_NODEPTRS_PER_BLOCK(info: fs_info) - 3)
3031	return 0;
3032	if (ret < 0)
3033	return ret;
3034	}
3035
3036	c_nritems = btrfs_header_nritems(eb: c);
3037	mid = (c_nritems + 1) / 2;
3038	btrfs_node_key(eb: c, disk_key: &disk_key, nr: mid);
3039
3040	split = btrfs_alloc_tree_block(trans, root, parent: 0, root_objectid: btrfs_root_id(root),
3041	key: &disk_key, level, hint: c->start, empty_size: 0,
3042	reloc_src_root: 0, nest: BTRFS_NESTING_SPLIT);
3043	if (IS_ERR(ptr: split))
3044	return PTR_ERR(ptr: split);
3045
3046	root_add_used_bytes(root);
3047	ASSERT(btrfs_header_level(c) == level);
3048
3049	ret = btrfs_tree_mod_log_eb_copy(dst: split, src: c, dst_offset: 0, src_offset: mid, nr_items: c_nritems - mid);
3050	if (unlikely(ret)) {
3051	btrfs_tree_unlock(eb: split);
3052	free_extent_buffer(eb: split);
3053	btrfs_abort_transaction(trans, ret);
3054	return ret;
3055	}
3056	copy_extent_buffer(dst: split, src: c,
3057	dst_offset: btrfs_node_key_ptr_offset(eb: split, nr: 0),
3058	src_offset: btrfs_node_key_ptr_offset(eb: c, nr: mid),
3059	len: (c_nritems - mid) * sizeof(struct btrfs_key_ptr));
3060	btrfs_set_header_nritems(eb: split, val: c_nritems - mid);
3061	btrfs_set_header_nritems(eb: c, val: mid);
3062
3063	btrfs_mark_buffer_dirty(trans, buf: c);
3064	btrfs_mark_buffer_dirty(trans, buf: split);
3065
3066	ret = insert_ptr(trans, path, key: &disk_key, bytenr: split->start,
3067	slot: path->slots[level + 1] + 1, level: level + 1);
3068	if (ret < 0) {
3069	btrfs_tree_unlock(eb: split);
3070	free_extent_buffer(eb: split);
3071	return ret;
3072	}
3073
3074	if (path->slots[level] >= mid) {
3075	path->slots[level] -= mid;
3076	btrfs_tree_unlock(eb: c);
3077	free_extent_buffer(eb: c);
3078	path->nodes[level] = split;
3079	path->slots[level + 1] += 1;
3080	} else {
3081	btrfs_tree_unlock(eb: split);
3082	free_extent_buffer(eb: split);
3083	}
3084	return 0;
3085	}
3086
3087	/*
3088	* how many bytes are required to store the items in a leaf. start
3089	* and nr indicate which items in the leaf to check. This totals up the
3090	* space used both by the item structs and the item data
3091	*/
3092	static int leaf_space_used(const struct extent_buffer *l, int start, int nr)
3093	{
3094	int data_len;
3095	int nritems = btrfs_header_nritems(eb: l);
3096	int end = min(nritems, start + nr) - 1;
3097
3098	if (!nr)
3099	return 0;
3100	data_len = btrfs_item_offset(eb: l, slot: start) + btrfs_item_size(eb: l, slot: start);
3101	data_len = data_len - btrfs_item_offset(eb: l, slot: end);
3102	data_len += sizeof(struct btrfs_item) * nr;
3103	WARN_ON(data_len < 0);
3104	return data_len;
3105	}
3106
3107	/*
3108	* The space between the end of the leaf items and
3109	* the start of the leaf data. IOW, how much room
3110	* the leaf has left for both items and data
3111	*/
3112	int btrfs_leaf_free_space(const struct extent_buffer *leaf)
3113	{
3114	struct btrfs_fs_info *fs_info = leaf->fs_info;
3115	int nritems = btrfs_header_nritems(eb: leaf);
3116	int ret;
3117
3118	ret = BTRFS_LEAF_DATA_SIZE(info: fs_info) - leaf_space_used(l: leaf, start: 0, nr: nritems);
3119	if (unlikely(ret < 0)) {
3120	btrfs_crit(fs_info,
3121	"leaf free space ret %d, leaf data size %lu, used %d nritems %d",
3122	ret,
3123	(unsigned long) BTRFS_LEAF_DATA_SIZE(fs_info),
3124	leaf_space_used(leaf, 0, nritems), nritems);
3125	}
3126	return ret;
3127	}
3128
3129	/*
3130	* min slot controls the lowest index we're willing to push to the
3131	* right. We'll push up to and including min_slot, but no lower
3132	*/
3133	static noinline int __push_leaf_right(struct btrfs_trans_handle *trans,
3134	struct btrfs_path *path,
3135	int data_size, bool empty,
3136	struct extent_buffer *right,
3137	int free_space, u32 left_nritems,
3138	u32 min_slot)
3139	{
3140	struct btrfs_fs_info *fs_info = right->fs_info;
3141	struct extent_buffer *left = path->nodes[0];
3142	struct extent_buffer *upper = path->nodes[1];
3143	struct btrfs_disk_key disk_key;
3144	int slot;
3145	u32 i;
3146	int push_space = 0;
3147	int push_items = 0;
3148	u32 nr;
3149	u32 right_nritems;
3150	u32 data_end;
3151	u32 this_item_size;
3152
3153	if (empty)
3154	nr = 0;
3155	else
3156	nr = max_t(u32, 1, min_slot);
3157
3158	if (path->slots[0] >= left_nritems)
3159	push_space += data_size;
3160
3161	slot = path->slots[1];
3162	i = left_nritems - 1;
3163	while (i >= nr) {
3164	if (!empty && push_items > 0) {
3165	if (path->slots[0] > i)
3166	break;
3167	if (path->slots[0] == i) {
3168	int space = btrfs_leaf_free_space(leaf: left);
3169
3170	if (space + push_space * 2 > free_space)
3171	break;
3172	}
3173	}
3174
3175	if (path->slots[0] == i)
3176	push_space += data_size;
3177
3178	this_item_size = btrfs_item_size(eb: left, slot: i);
3179	if (this_item_size + sizeof(struct btrfs_item) +
3180	push_space > free_space)
3181	break;
3182
3183	push_items++;
3184	push_space += this_item_size + sizeof(struct btrfs_item);
3185	if (i == 0)
3186	break;
3187	i--;
3188	}
3189
3190	if (push_items == 0)
3191	goto out_unlock;
3192
3193	WARN_ON(!empty && push_items == left_nritems);
3194
3195	/* push left to right */
3196	right_nritems = btrfs_header_nritems(eb: right);
3197
3198	push_space = btrfs_item_data_end(eb: left, nr: left_nritems - push_items);
3199	push_space -= leaf_data_end(leaf: left);
3200
3201	/* make room in the right data area */
3202	data_end = leaf_data_end(leaf: right);
3203	memmove_leaf_data(leaf: right, dst_offset: data_end - push_space, src_offset: data_end,
3204	len: BTRFS_LEAF_DATA_SIZE(info: fs_info) - data_end);
3205
3206	/* copy from the left data area */
3207	copy_leaf_data(dst: right, src: left, dst_offset: BTRFS_LEAF_DATA_SIZE(info: fs_info) - push_space,
3208	src_offset: leaf_data_end(leaf: left), len: push_space);
3209
3210	memmove_leaf_items(leaf: right, dst_item: push_items, src_item: 0, nr_items: right_nritems);
3211
3212	/* copy the items from left to right */
3213	copy_leaf_items(dst: right, src: left, dst_item: 0, src_item: left_nritems - push_items, nr_items: push_items);
3214
3215	/* update the item pointers */
3216	right_nritems += push_items;
3217	btrfs_set_header_nritems(eb: right, val: right_nritems);
3218	push_space = BTRFS_LEAF_DATA_SIZE(info: fs_info);
3219	for (i = 0; i < right_nritems; i++) {
3220	push_space -= btrfs_item_size(eb: right, slot: i);
3221	btrfs_set_item_offset(eb: right, slot: i, val: push_space);
3222	}
3223
3224	left_nritems -= push_items;
3225	btrfs_set_header_nritems(eb: left, val: left_nritems);
3226
3227	if (left_nritems)
3228	btrfs_mark_buffer_dirty(trans, buf: left);
3229	else
3230	btrfs_clear_buffer_dirty(trans, buf: left);
3231
3232	btrfs_mark_buffer_dirty(trans, buf: right);
3233
3234	btrfs_item_key(eb: right, disk_key: &disk_key, nr: 0);
3235	btrfs_set_node_key(eb: upper, disk_key: &disk_key, nr: slot + 1);
3236	btrfs_mark_buffer_dirty(trans, buf: upper);
3237
3238	/* then fixup the leaf pointer in the path */
3239	if (path->slots[0] >= left_nritems) {
3240	path->slots[0] -= left_nritems;
3241	btrfs_tree_unlock(eb: left);
3242	free_extent_buffer(eb: left);
3243	path->nodes[0] = right;
3244	path->slots[1] += 1;
3245	} else {
3246	btrfs_tree_unlock(eb: right);
3247	free_extent_buffer(eb: right);
3248	}
3249	return 0;
3250
3251	out_unlock:
3252	btrfs_tree_unlock(eb: right);
3253	free_extent_buffer(eb: right);
3254	return 1;
3255	}
3256
3257	/*
3258	* push some data in the path leaf to the right, trying to free up at
3259	* least data_size bytes. returns zero if the push worked, nonzero otherwise
3260	*
3261	* returns 1 if the push failed because the other node didn't have enough
3262	* room, 0 if everything worked out and < 0 if there were major errors.
3263	*
3264	* this will push starting from min_slot to the end of the leaf. It won't
3265	* push any slot lower than min_slot
3266	*/
3267	static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
3268	*root, struct btrfs_path *path,
3269	int min_data_size, int data_size,
3270	bool empty, u32 min_slot)
3271	{
3272	struct extent_buffer *left = path->nodes[0];
3273	struct extent_buffer *right;
3274	struct extent_buffer *upper;
3275	int slot;
3276	int free_space;
3277	u32 left_nritems;
3278	int ret;
3279
3280	if (!path->nodes[1])
3281	return 1;
3282
3283	slot = path->slots[1];
3284	upper = path->nodes[1];
3285	if (slot >= btrfs_header_nritems(eb: upper) - 1)
3286	return 1;
3287
3288	btrfs_assert_tree_write_locked(eb: path->nodes[1]);
3289
3290	right = btrfs_read_node_slot(parent: upper, slot: slot + 1);
3291	if (IS_ERR(ptr: right))
3292	return PTR_ERR(ptr: right);
3293
3294	btrfs_tree_lock_nested(eb: right, nest: BTRFS_NESTING_RIGHT);
3295
3296	free_space = btrfs_leaf_free_space(leaf: right);
3297	if (free_space < data_size)
3298	goto out_unlock;
3299
3300	ret = btrfs_cow_block(trans, root, buf: right, parent: upper,
3301	parent_slot: slot + 1, cow_ret: &right, nest: BTRFS_NESTING_RIGHT_COW);
3302	if (ret)
3303	goto out_unlock;
3304
3305	left_nritems = btrfs_header_nritems(eb: left);
3306	if (left_nritems == 0)
3307	goto out_unlock;
3308
3309	if (unlikely(check_sibling_keys(left, right))) {
3310	ret = -EUCLEAN;
3311	btrfs_abort_transaction(trans, ret);
3312	btrfs_tree_unlock(eb: right);
3313	free_extent_buffer(eb: right);
3314	return ret;
3315	}
3316	if (path->slots[0] == left_nritems && !empty) {
3317	/* Key greater than all keys in the leaf, right neighbor has
3318	* enough room for it and we're not emptying our leaf to delete
3319	* it, therefore use right neighbor to insert the new item and
3320	* no need to touch/dirty our left leaf. */
3321	btrfs_tree_unlock(eb: left);
3322	free_extent_buffer(eb: left);
3323	path->nodes[0] = right;
3324	path->slots[0] = 0;
3325	path->slots[1]++;
3326	return 0;
3327	}
3328
3329	return __push_leaf_right(trans, path, data_size: min_data_size, empty, right,
3330	free_space, left_nritems, min_slot);
3331	out_unlock:
3332	btrfs_tree_unlock(eb: right);
3333	free_extent_buffer(eb: right);
3334	return 1;
3335	}
3336
3337	/*
3338	* push some data in the path leaf to the left, trying to free up at
3339	* least data_size bytes. returns zero if the push worked, nonzero otherwise
3340	*
3341	* max_slot can put a limit on how far into the leaf we'll push items. The
3342	* item at 'max_slot' won't be touched. Use (u32)-1 to make us do all the
3343	* items
3344	*/
3345	static noinline int __push_leaf_left(struct btrfs_trans_handle *trans,
3346	struct btrfs_path *path, int data_size,
3347	bool empty, struct extent_buffer *left,
3348	int free_space, u32 right_nritems,
3349	u32 max_slot)
3350	{
3351	struct btrfs_fs_info *fs_info = left->fs_info;
3352	struct btrfs_disk_key disk_key;
3353	struct extent_buffer *right = path->nodes[0];
3354	int i;
3355	int push_space = 0;
3356	int push_items = 0;
3357	u32 old_left_nritems;
3358	u32 nr;
3359	int ret = 0;
3360	u32 this_item_size;
3361	u32 old_left_item_size;
3362
3363	if (empty)
3364	nr = min(right_nritems, max_slot);
3365	else
3366	nr = min(right_nritems - 1, max_slot);
3367
3368	for (i = 0; i < nr; i++) {
3369	if (!empty && push_items > 0) {
3370	if (path->slots[0] < i)
3371	break;
3372	if (path->slots[0] == i) {
3373	int space = btrfs_leaf_free_space(leaf: right);
3374
3375	if (space + push_space * 2 > free_space)
3376	break;
3377	}
3378	}
3379
3380	if (path->slots[0] == i)
3381	push_space += data_size;
3382
3383	this_item_size = btrfs_item_size(eb: right, slot: i);
3384	if (this_item_size + sizeof(struct btrfs_item) + push_space >
3385	free_space)
3386	break;
3387
3388	push_items++;
3389	push_space += this_item_size + sizeof(struct btrfs_item);
3390	}
3391
3392	if (push_items == 0) {
3393	ret = 1;
3394	goto out;
3395	}
3396	WARN_ON(!empty && push_items == btrfs_header_nritems(right));
3397
3398	/* push data from right to left */
3399	copy_leaf_items(dst: left, src: right, dst_item: btrfs_header_nritems(eb: left), src_item: 0, nr_items: push_items);
3400
3401	push_space = BTRFS_LEAF_DATA_SIZE(info: fs_info) -
3402	btrfs_item_offset(eb: right, slot: push_items - 1);
3403
3404	copy_leaf_data(dst: left, src: right, dst_offset: leaf_data_end(leaf: left) - push_space,
3405	src_offset: btrfs_item_offset(eb: right, slot: push_items - 1), len: push_space);
3406	old_left_nritems = btrfs_header_nritems(eb: left);
3407	BUG_ON(old_left_nritems <= 0);
3408
3409	old_left_item_size = btrfs_item_offset(eb: left, slot: old_left_nritems - 1);
3410	for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
3411	u32 ioff;
3412
3413	ioff = btrfs_item_offset(eb: left, slot: i);
3414	btrfs_set_item_offset(eb: left, slot: i,
3415	val: ioff - (BTRFS_LEAF_DATA_SIZE(info: fs_info) - old_left_item_size));
3416	}
3417	btrfs_set_header_nritems(eb: left, val: old_left_nritems + push_items);
3418
3419	/* fixup right node */
3420	if (unlikely(push_items > right_nritems)) {
3421	ret = -EUCLEAN;
3422	btrfs_abort_transaction(trans, ret);
3423	btrfs_crit(fs_info, "push items (%d) > right leaf items (%u)",
3424	push_items, right_nritems);
3425	goto out;
3426	}
3427
3428	if (push_items < right_nritems) {
3429	push_space = btrfs_item_offset(eb: right, slot: push_items - 1) -
3430	leaf_data_end(leaf: right);
3431	memmove_leaf_data(leaf: right,
3432	dst_offset: BTRFS_LEAF_DATA_SIZE(info: fs_info) - push_space,
3433	src_offset: leaf_data_end(leaf: right), len: push_space);
3434
3435	memmove_leaf_items(leaf: right, dst_item: 0, src_item: push_items,
3436	nr_items: btrfs_header_nritems(eb: right) - push_items);
3437	}
3438
3439	right_nritems -= push_items;
3440	btrfs_set_header_nritems(eb: right, val: right_nritems);
3441	push_space = BTRFS_LEAF_DATA_SIZE(info: fs_info);
3442	for (i = 0; i < right_nritems; i++) {
3443	push_space = push_space - btrfs_item_size(eb: right, slot: i);
3444	btrfs_set_item_offset(eb: right, slot: i, val: push_space);
3445	}
3446
3447	btrfs_mark_buffer_dirty(trans, buf: left);
3448	if (right_nritems)
3449	btrfs_mark_buffer_dirty(trans, buf: right);
3450	else
3451	btrfs_clear_buffer_dirty(trans, buf: right);
3452
3453	btrfs_item_key(eb: right, disk_key: &disk_key, nr: 0);
3454	fixup_low_keys(trans, path, key: &disk_key, level: 1);
3455
3456	/* then fixup the leaf pointer in the path */
3457	if (path->slots[0] < push_items) {
3458	path->slots[0] += old_left_nritems;
3459	btrfs_tree_unlock(eb: right);
3460	free_extent_buffer(eb: right);
3461	path->nodes[0] = left;
3462	path->slots[1] -= 1;
3463	} else {
3464	btrfs_tree_unlock(eb: left);
3465	free_extent_buffer(eb: left);
3466	path->slots[0] -= push_items;
3467	}
3468	BUG_ON(path->slots[0] < 0);
3469	return ret;
3470	out:
3471	btrfs_tree_unlock(eb: left);
3472	free_extent_buffer(eb: left);
3473	return ret;
3474	}
3475
3476	/*
3477	* push some data in the path leaf to the left, trying to free up at
3478	* least data_size bytes. returns zero if the push worked, nonzero otherwise
3479	*
3480	* max_slot can put a limit on how far into the leaf we'll push items. The
3481	* item at 'max_slot' won't be touched. Use (u32)-1 to make us push all the
3482	* items
3483	*/
3484	static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
3485	*root, struct btrfs_path *path, int min_data_size,
3486	int data_size, int empty, u32 max_slot)
3487	{
3488	struct extent_buffer *right = path->nodes[0];
3489	struct extent_buffer *left;
3490	int slot;
3491	int free_space;
3492	u32 right_nritems;
3493	int ret = 0;
3494
3495	slot = path->slots[1];
3496	if (slot == 0)
3497	return 1;
3498	if (!path->nodes[1])
3499	return 1;
3500
3501	right_nritems = btrfs_header_nritems(eb: right);
3502	if (right_nritems == 0)
3503	return 1;
3504
3505	btrfs_assert_tree_write_locked(eb: path->nodes[1]);
3506
3507	left = btrfs_read_node_slot(parent: path->nodes[1], slot: slot - 1);
3508	if (IS_ERR(ptr: left))
3509	return PTR_ERR(ptr: left);
3510
3511	btrfs_tree_lock_nested(eb: left, nest: BTRFS_NESTING_LEFT);
3512
3513	free_space = btrfs_leaf_free_space(leaf: left);
3514	if (free_space < data_size) {
3515	ret = 1;
3516	goto out;
3517	}
3518
3519	ret = btrfs_cow_block(trans, root, buf: left,
3520	parent: path->nodes[1], parent_slot: slot - 1, cow_ret: &left,
3521	nest: BTRFS_NESTING_LEFT_COW);
3522	if (ret) {
3523	/* we hit -ENOSPC, but it isn't fatal here */
3524	if (ret == -ENOSPC)
3525	ret = 1;
3526	goto out;
3527	}
3528
3529	if (unlikely(check_sibling_keys(left, right))) {
3530	ret = -EUCLEAN;
3531	btrfs_abort_transaction(trans, ret);
3532	goto out;
3533	}
3534	return __push_leaf_left(trans, path, data_size: min_data_size, empty, left,
3535	free_space, right_nritems, max_slot);
3536	out:
3537	btrfs_tree_unlock(eb: left);
3538	free_extent_buffer(eb: left);
3539	return ret;
3540	}
3541
3542	/*
3543	* split the path's leaf in two, making sure there is at least data_size
3544	* available for the resulting leaf level of the path.
3545	*/
3546	static noinline int copy_for_split(struct btrfs_trans_handle *trans,
3547	struct btrfs_path *path,
3548	struct extent_buffer *l,
3549	struct extent_buffer *right,
3550	int slot, int mid, int nritems)
3551	{
3552	struct btrfs_fs_info *fs_info = trans->fs_info;
3553	int data_copy_size;
3554	int rt_data_off;
3555	int i;
3556	int ret;
3557	struct btrfs_disk_key disk_key;
3558
3559	nritems = nritems - mid;
3560	btrfs_set_header_nritems(eb: right, val: nritems);
3561	data_copy_size = btrfs_item_data_end(eb: l, nr: mid) - leaf_data_end(leaf: l);
3562
3563	copy_leaf_items(dst: right, src: l, dst_item: 0, src_item: mid, nr_items: nritems);
3564
3565	copy_leaf_data(dst: right, src: l, dst_offset: BTRFS_LEAF_DATA_SIZE(info: fs_info) - data_copy_size,
3566	src_offset: leaf_data_end(leaf: l), len: data_copy_size);
3567
3568	rt_data_off = BTRFS_LEAF_DATA_SIZE(info: fs_info) - btrfs_item_data_end(eb: l, nr: mid);
3569
3570	for (i = 0; i < nritems; i++) {
3571	u32 ioff;
3572
3573	ioff = btrfs_item_offset(eb: right, slot: i);
3574	btrfs_set_item_offset(eb: right, slot: i, val: ioff + rt_data_off);
3575	}
3576
3577	btrfs_set_header_nritems(eb: l, val: mid);
3578	btrfs_item_key(eb: right, disk_key: &disk_key, nr: 0);
3579	ret = insert_ptr(trans, path, key: &disk_key, bytenr: right->start, slot: path->slots[1] + 1, level: 1);
3580	if (ret < 0)
3581	return ret;
3582
3583	btrfs_mark_buffer_dirty(trans, buf: right);
3584	btrfs_mark_buffer_dirty(trans, buf: l);
3585	BUG_ON(path->slots[0] != slot);
3586
3587	if (mid <= slot) {
3588	btrfs_tree_unlock(eb: path->nodes[0]);
3589	free_extent_buffer(eb: path->nodes[0]);
3590	path->nodes[0] = right;
3591	path->slots[0] -= mid;
3592	path->slots[1] += 1;
3593	} else {
3594	btrfs_tree_unlock(eb: right);
3595	free_extent_buffer(eb: right);
3596	}
3597
3598	BUG_ON(path->slots[0] < 0);
3599
3600	return 0;
3601	}
3602
3603	/*
3604	* double splits happen when we need to insert a big item in the middle
3605	* of a leaf. A double split can leave us with 3 mostly empty leaves:
3606	* leaf: [ slots 0 - N] [ our target ] [ N + 1 - total in leaf ]
3607	* A B C
3608	*
3609	* We avoid this by trying to push the items on either side of our target
3610	* into the adjacent leaves. If all goes well we can avoid the double split
3611	* completely.
3612	*/
3613	static noinline int push_for_double_split(struct btrfs_trans_handle *trans,
3614	struct btrfs_root *root,
3615	struct btrfs_path *path,
3616	int data_size)
3617	{
3618	int ret;
3619	int progress = 0;
3620	int slot;
3621	u32 nritems;
3622	int space_needed = data_size;
3623
3624	slot = path->slots[0];
3625	if (slot < btrfs_header_nritems(eb: path->nodes[0]))
3626	space_needed -= btrfs_leaf_free_space(leaf: path->nodes[0]);
3627
3628	/*
3629	* try to push all the items after our slot into the
3630	* right leaf
3631	*/
3632	ret = push_leaf_right(trans, root, path, min_data_size: 1, data_size: space_needed, empty: 0, min_slot: slot);
3633	if (ret < 0)
3634	return ret;
3635
3636	if (ret == 0)
3637	progress++;
3638
3639	nritems = btrfs_header_nritems(eb: path->nodes[0]);
3640	/*
3641	* our goal is to get our slot at the start or end of a leaf. If
3642	* we've done so we're done
3643	*/
3644	if (path->slots[0] == 0 || path->slots[0] == nritems)
3645	return 0;
3646
3647	if (btrfs_leaf_free_space(leaf: path->nodes[0]) >= data_size)
3648	return 0;
3649
3650	/* try to push all the items before our slot into the next leaf */
3651	slot = path->slots[0];
3652	space_needed = data_size;
3653	if (slot > 0)
3654	space_needed -= btrfs_leaf_free_space(leaf: path->nodes[0]);
3655	ret = push_leaf_left(trans, root, path, min_data_size: 1, data_size: space_needed, empty: 0, max_slot: slot);
3656	if (ret < 0)
3657	return ret;
3658
3659	if (ret == 0)
3660	progress++;
3661
3662	if (progress)
3663	return 0;
3664	return 1;
3665	}
3666
3667	/*
3668	* split the path's leaf in two, making sure there is at least data_size
3669	* available for the resulting leaf level of the path.
3670	*
3671	* returns 0 if all went well and < 0 on failure.
3672	*/
3673	static noinline int split_leaf(struct btrfs_trans_handle *trans,
3674	struct btrfs_root *root,
3675	const struct btrfs_key *ins_key,
3676	struct btrfs_path *path, int data_size,
3677	bool extend)
3678	{
3679	struct btrfs_disk_key disk_key;
3680	struct extent_buffer *l;
3681	u32 nritems;
3682	int mid;
3683	int slot;
3684	struct extent_buffer *right;
3685	struct btrfs_fs_info *fs_info = root->fs_info;
3686	int ret = 0;
3687	int wret;
3688	int split;
3689	int num_doubles = 0;
3690	int tried_avoid_double = 0;
3691
3692	l = path->nodes[0];
3693	slot = path->slots[0];
3694	if (extend && data_size + btrfs_item_size(eb: l, slot) +
3695	sizeof(struct btrfs_item) > BTRFS_LEAF_DATA_SIZE(info: fs_info))
3696	return -EOVERFLOW;
3697
3698	/* first try to make some room by pushing left and right */
3699	if (data_size && path->nodes[1]) {
3700	int space_needed = data_size;
3701
3702	if (slot < btrfs_header_nritems(eb: l))
3703	space_needed -= btrfs_leaf_free_space(leaf: l);
3704
3705	wret = push_leaf_right(trans, root, path, min_data_size: space_needed,
3706	data_size: space_needed, empty: 0, min_slot: 0);
3707	if (wret < 0)
3708	return wret;
3709	if (wret) {
3710	space_needed = data_size;
3711	if (slot > 0)
3712	space_needed -= btrfs_leaf_free_space(leaf: l);
3713	wret = push_leaf_left(trans, root, path, min_data_size: space_needed,
3714	data_size: space_needed, empty: 0, max_slot: (u32)-1);
3715	if (wret < 0)
3716	return wret;
3717	}
3718	l = path->nodes[0];
3719
3720	/* did the pushes work? */
3721	if (btrfs_leaf_free_space(leaf: l) >= data_size)
3722	return 0;
3723	}
3724
3725	if (!path->nodes[1]) {
3726	ret = insert_new_root(trans, root, path, level: 1);
3727	if (ret)
3728	return ret;
3729	}
3730	again:
3731	split = 1;
3732	l = path->nodes[0];
3733	slot = path->slots[0];
3734	nritems = btrfs_header_nritems(eb: l);
3735	mid = (nritems + 1) / 2;
3736
3737	if (mid <= slot) {
3738	if (nritems == 1 ||
3739	leaf_space_used(l, start: mid, nr: nritems - mid) + data_size >
3740	BTRFS_LEAF_DATA_SIZE(info: fs_info)) {
3741	if (slot >= nritems) {
3742	split = 0;
3743	} else {
3744	mid = slot;
3745	if (mid != nritems &&
3746	leaf_space_used(l, start: mid, nr: nritems - mid) +
3747	data_size > BTRFS_LEAF_DATA_SIZE(info: fs_info)) {
3748	if (data_size && !tried_avoid_double)
3749	goto push_for_double;
3750	split = 2;
3751	}
3752	}
3753	}
3754	} else {
3755	if (leaf_space_used(l, start: 0, nr: mid) + data_size >
3756	BTRFS_LEAF_DATA_SIZE(info: fs_info)) {
3757	if (!extend && data_size && slot == 0) {
3758	split = 0;
3759	} else if ((extend || !data_size) && slot == 0) {
3760	mid = 1;
3761	} else {
3762	mid = slot;
3763	if (mid != nritems &&
3764	leaf_space_used(l, start: mid, nr: nritems - mid) +
3765	data_size > BTRFS_LEAF_DATA_SIZE(info: fs_info)) {
3766	if (data_size && !tried_avoid_double)
3767	goto push_for_double;
3768	split = 2;
3769	}
3770	}
3771	}
3772	}
3773
3774	if (split == 0)
3775	btrfs_cpu_key_to_disk(disk_key: &disk_key, cpu_key: ins_key);
3776	else
3777	btrfs_item_key(eb: l, disk_key: &disk_key, nr: mid);
3778
3779	/*
3780	* We have to about BTRFS_NESTING_NEW_ROOT here if we've done a double
3781	* split, because we're only allowed to have MAX_LOCKDEP_SUBCLASSES
3782	* subclasses, which is 8 at the time of this patch, and we've maxed it
3783	* out. In the future we could add a
3784	* BTRFS_NESTING_SPLIT_THE_SPLITTENING if we need to, but for now just
3785	* use BTRFS_NESTING_NEW_ROOT.
3786	*/
3787	right = btrfs_alloc_tree_block(trans, root, parent: 0, root_objectid: btrfs_root_id(root),
3788	key: &disk_key, level: 0, hint: l->start, empty_size: 0, reloc_src_root: 0,
3789	nest: num_doubles ? BTRFS_NESTING_NEW_ROOT :
3790	BTRFS_NESTING_SPLIT);
3791	if (IS_ERR(ptr: right))
3792	return PTR_ERR(ptr: right);
3793
3794	root_add_used_bytes(root);
3795
3796	if (split == 0) {
3797	if (mid <= slot) {
3798	btrfs_set_header_nritems(eb: right, val: 0);
3799	ret = insert_ptr(trans, path, key: &disk_key,
3800	bytenr: right->start, slot: path->slots[1] + 1, level: 1);
3801	if (ret < 0) {
3802	btrfs_tree_unlock(eb: right);
3803	free_extent_buffer(eb: right);
3804	return ret;
3805	}
3806	btrfs_tree_unlock(eb: path->nodes[0]);
3807	free_extent_buffer(eb: path->nodes[0]);
3808	path->nodes[0] = right;
3809	path->slots[0] = 0;
3810	path->slots[1] += 1;
3811	} else {
3812	btrfs_set_header_nritems(eb: right, val: 0);
3813	ret = insert_ptr(trans, path, key: &disk_key,
3814	bytenr: right->start, slot: path->slots[1], level: 1);
3815	if (ret < 0) {
3816	btrfs_tree_unlock(eb: right);
3817	free_extent_buffer(eb: right);
3818	return ret;
3819	}
3820	btrfs_tree_unlock(eb: path->nodes[0]);
3821	free_extent_buffer(eb: path->nodes[0]);
3822	path->nodes[0] = right;
3823	path->slots[0] = 0;
3824	if (path->slots[1] == 0)
3825	fixup_low_keys(trans, path, key: &disk_key, level: 1);
3826	}
3827	/*
3828	* We create a new leaf 'right' for the required ins_len and
3829	* we'll do btrfs_mark_buffer_dirty() on this leaf after copying
3830	* the content of ins_len to 'right'.
3831	*/
3832	return ret;
3833	}
3834
3835	ret = copy_for_split(trans, path, l, right, slot, mid, nritems);
3836	if (ret < 0) {
3837	btrfs_tree_unlock(eb: right);
3838	free_extent_buffer(eb: right);
3839	return ret;
3840	}
3841
3842	if (split == 2) {
3843	BUG_ON(num_doubles != 0);
3844	num_doubles++;
3845	goto again;
3846	}
3847
3848	return 0;
3849
3850	push_for_double:
3851	push_for_double_split(trans, root, path, data_size);
3852	tried_avoid_double = 1;
3853	if (btrfs_leaf_free_space(leaf: path->nodes[0]) >= data_size)
3854	return 0;
3855	goto again;
3856	}
3857
3858	static noinline int setup_leaf_for_split(struct btrfs_trans_handle *trans,
3859	struct btrfs_root *root,
3860	struct btrfs_path *path, int ins_len)
3861	{
3862	struct btrfs_key key;
3863	struct extent_buffer *leaf;
3864	struct btrfs_file_extent_item *fi;
3865	u64 extent_len = 0;
3866	u32 item_size;
3867	int ret;
3868
3869	leaf = path->nodes[0];
3870	btrfs_item_key_to_cpu(eb: leaf, cpu_key: &key, nr: path->slots[0]);
3871
3872	BUG_ON(key.type != BTRFS_EXTENT_DATA_KEY &&
3873	key.type != BTRFS_RAID_STRIPE_KEY &&
3874	key.type != BTRFS_EXTENT_CSUM_KEY);
3875
3876	if (btrfs_leaf_free_space(leaf) >= ins_len)
3877	return 0;
3878
3879	item_size = btrfs_item_size(eb: leaf, slot: path->slots[0]);
3880	if (key.type == BTRFS_EXTENT_DATA_KEY) {
3881	fi = btrfs_item_ptr(leaf, path->slots[0],
3882	struct btrfs_file_extent_item);
3883	extent_len = btrfs_file_extent_num_bytes(eb: leaf, s: fi);
3884	}
3885	btrfs_release_path(p: path);
3886
3887	path->keep_locks = true;
3888	path->search_for_split = true;
3889	ret = btrfs_search_slot(trans, root, key: &key, p: path, ins_len: 0, cow: 1);
3890	path->search_for_split = false;
3891	if (ret > 0)
3892	ret = -EAGAIN;
3893	if (ret < 0)
3894	goto err;
3895
3896	ret = -EAGAIN;
3897	leaf = path->nodes[0];
3898	/* if our item isn't there, return now */
3899	if (item_size != btrfs_item_size(eb: leaf, slot: path->slots[0]))
3900	goto err;
3901
3902	/* the leaf has changed, it now has room. return now */
3903	if (btrfs_leaf_free_space(leaf: path->nodes[0]) >= ins_len)
3904	goto err;
3905
3906	if (key.type == BTRFS_EXTENT_DATA_KEY) {
3907	fi = btrfs_item_ptr(leaf, path->slots[0],
3908	struct btrfs_file_extent_item);
3909	if (extent_len != btrfs_file_extent_num_bytes(eb: leaf, s: fi))
3910	goto err;
3911	}
3912
3913	ret = split_leaf(trans, root, ins_key: &key, path, data_size: ins_len, extend: 1);
3914	if (ret)
3915	goto err;
3916
3917	path->keep_locks = false;
3918	btrfs_unlock_up_safe(path, level: 1);
3919	return 0;
3920	err:
3921	path->keep_locks = false;
3922	return ret;
3923	}
3924
3925	static noinline int split_item(struct btrfs_trans_handle *trans,
3926	struct btrfs_path *path,
3927	const struct btrfs_key *new_key,
3928	unsigned long split_offset)
3929	{
3930	struct extent_buffer *leaf;
3931	int orig_slot, slot;
3932	char *buf;
3933	u32 nritems;
3934	u32 item_size;
3935	u32 orig_offset;
3936	struct btrfs_disk_key disk_key;
3937
3938	leaf = path->nodes[0];
3939	/*
3940	* Shouldn't happen because the caller must have previously called
3941	* setup_leaf_for_split() to make room for the new item in the leaf.
3942	*/
3943	if (WARN_ON(btrfs_leaf_free_space(leaf) < sizeof(struct btrfs_item)))
3944	return -ENOSPC;
3945
3946	orig_slot = path->slots[0];
3947	orig_offset = btrfs_item_offset(eb: leaf, slot: path->slots[0]);
3948	item_size = btrfs_item_size(eb: leaf, slot: path->slots[0]);
3949
3950	buf = kmalloc(item_size, GFP_NOFS);
3951	if (!buf)
3952	return -ENOMEM;
3953
3954	read_extent_buffer(eb: leaf, dst: buf, btrfs_item_ptr_offset(leaf,
3955	path->slots[0]), len: item_size);
3956
3957	slot = path->slots[0] + 1;
3958	nritems = btrfs_header_nritems(eb: leaf);
3959	if (slot != nritems) {
3960	/* shift the items */
3961	memmove_leaf_items(leaf, dst_item: slot + 1, src_item: slot, nr_items: nritems - slot);
3962	}
3963
3964	btrfs_cpu_key_to_disk(disk_key: &disk_key, cpu_key: new_key);
3965	btrfs_set_item_key(eb: leaf, disk_key: &disk_key, nr: slot);
3966
3967	btrfs_set_item_offset(eb: leaf, slot, val: orig_offset);
3968	btrfs_set_item_size(eb: leaf, slot, val: item_size - split_offset);
3969
3970	btrfs_set_item_offset(eb: leaf, slot: orig_slot,
3971	val: orig_offset + item_size - split_offset);
3972	btrfs_set_item_size(eb: leaf, slot: orig_slot, val: split_offset);
3973
3974	btrfs_set_header_nritems(eb: leaf, val: nritems + 1);
3975
3976	/* write the data for the start of the original item */
3977	write_extent_buffer(eb: leaf, src: buf,
3978	btrfs_item_ptr_offset(leaf, path->slots[0]),
3979	len: split_offset);
3980
3981	/* write the data for the new item */
3982	write_extent_buffer(eb: leaf, src: buf + split_offset,
3983	btrfs_item_ptr_offset(leaf, slot),
3984	len: item_size - split_offset);
3985	btrfs_mark_buffer_dirty(trans, buf: leaf);
3986
3987	BUG_ON(btrfs_leaf_free_space(leaf) < 0);
3988	kfree(objp: buf);
3989	return 0;
3990	}
3991
3992	/*
3993	* This function splits a single item into two items,
3994	* giving 'new_key' to the new item and splitting the
3995	* old one at split_offset (from the start of the item).
3996	*
3997	* The path may be released by this operation. After
3998	* the split, the path is pointing to the old item. The
3999	* new item is going to be in the same node as the old one.
4000	*
4001	* Note, the item being split must be smaller enough to live alone on
4002	* a tree block with room for one extra struct btrfs_item
4003	*
4004	* This allows us to split the item in place, keeping a lock on the
4005	* leaf the entire time.
4006	*/
4007	int btrfs_split_item(struct btrfs_trans_handle *trans,
4008	struct btrfs_root *root,
4009	struct btrfs_path *path,
4010	const struct btrfs_key *new_key,
4011	unsigned long split_offset)
4012	{
4013	int ret;
4014	ret = setup_leaf_for_split(trans, root, path,
4015	ins_len: sizeof(struct btrfs_item));
4016	if (ret)
4017	return ret;
4018
4019	ret = split_item(trans, path, new_key, split_offset);
4020	return ret;
4021	}
4022
4023	/*
4024	* make the item pointed to by the path smaller. new_size indicates
4025	* how small to make it, and from_end tells us if we just chop bytes
4026	* off the end of the item or if we shift the item to chop bytes off
4027	* the front.
4028	*/
4029	void btrfs_truncate_item(struct btrfs_trans_handle *trans,
4030	const struct btrfs_path *path, u32 new_size, int from_end)
4031	{
4032	int slot;
4033	struct extent_buffer *leaf;
4034	u32 nritems;
4035	unsigned int data_end;
4036	unsigned int old_data_start;
4037	unsigned int old_size;
4038	unsigned int size_diff;
4039	int i;
4040
4041	leaf = path->nodes[0];
4042	slot = path->slots[0];
4043
4044	old_size = btrfs_item_size(eb: leaf, slot);
4045	if (old_size == new_size)
4046	return;
4047
4048	nritems = btrfs_header_nritems(eb: leaf);
4049	data_end = leaf_data_end(leaf);
4050
4051	old_data_start = btrfs_item_offset(eb: leaf, slot);
4052
4053	size_diff = old_size - new_size;
4054
4055	BUG_ON(slot < 0);
4056	BUG_ON(slot >= nritems);
4057
4058	/*
4059	* item0..itemN ... dataN.offset..dataN.size .. data0.size
4060	*/
4061	/* first correct the data pointers */
4062	for (i = slot; i < nritems; i++) {
4063	u32 ioff;
4064
4065	ioff = btrfs_item_offset(eb: leaf, slot: i);
4066	btrfs_set_item_offset(eb: leaf, slot: i, val: ioff + size_diff);
4067	}
4068
4069	/* shift the data */
4070	if (from_end) {
4071	memmove_leaf_data(leaf, dst_offset: data_end + size_diff, src_offset: data_end,
4072	len: old_data_start + new_size - data_end);
4073	} else {
4074	struct btrfs_disk_key disk_key;
4075	u64 offset;
4076
4077	btrfs_item_key(eb: leaf, disk_key: &disk_key, nr: slot);
4078
4079	if (btrfs_disk_key_type(s: &disk_key) == BTRFS_EXTENT_DATA_KEY) {
4080	unsigned long ptr;
4081	struct btrfs_file_extent_item *fi;
4082
4083	fi = btrfs_item_ptr(leaf, slot,
4084	struct btrfs_file_extent_item);
4085	fi = (struct btrfs_file_extent_item *)(
4086	(unsigned long)fi - size_diff);
4087
4088	if (btrfs_file_extent_type(eb: leaf, s: fi) ==
4089	BTRFS_FILE_EXTENT_INLINE) {
4090	ptr = btrfs_item_ptr_offset(leaf, slot);
4091	memmove_extent_buffer(dst: leaf, dst_offset: ptr,
4092	src_offset: (unsigned long)fi,
4093	BTRFS_FILE_EXTENT_INLINE_DATA_START);
4094	}
4095	}
4096
4097	memmove_leaf_data(leaf, dst_offset: data_end + size_diff, src_offset: data_end,
4098	len: old_data_start - data_end);
4099
4100	offset = btrfs_disk_key_offset(s: &disk_key);
4101	btrfs_set_disk_key_offset(s: &disk_key, val: offset + size_diff);
4102	btrfs_set_item_key(eb: leaf, disk_key: &disk_key, nr: slot);
4103	if (slot == 0)
4104	fixup_low_keys(trans, path, key: &disk_key, level: 1);
4105	}
4106
4107	btrfs_set_item_size(eb: leaf, slot, val: new_size);
4108	btrfs_mark_buffer_dirty(trans, buf: leaf);
4109
4110	if (unlikely(btrfs_leaf_free_space(leaf) < 0)) {
4111	btrfs_print_leaf(l: leaf);
4112	BUG();
4113	}
4114	}
4115
4116	/*
4117	* make the item pointed to by the path bigger, data_size is the added size.
4118	*/
4119	void btrfs_extend_item(struct btrfs_trans_handle *trans,
4120	const struct btrfs_path *path, u32 data_size)
4121	{
4122	int slot;
4123	struct extent_buffer *leaf;
4124	u32 nritems;
4125	unsigned int data_end;
4126	unsigned int old_data;
4127	unsigned int old_size;
4128	int i;
4129
4130	leaf = path->nodes[0];
4131
4132	nritems = btrfs_header_nritems(eb: leaf);
4133	data_end = leaf_data_end(leaf);
4134
4135	if (unlikely(btrfs_leaf_free_space(leaf) < data_size)) {
4136	btrfs_print_leaf(l: leaf);
4137	BUG();
4138	}
4139	slot = path->slots[0];
4140	old_data = btrfs_item_data_end(eb: leaf, nr: slot);
4141
4142	BUG_ON(slot < 0);
4143	if (unlikely(slot >= nritems)) {
4144	btrfs_print_leaf(l: leaf);
4145	btrfs_crit(leaf->fs_info, "slot %d too large, nritems %d",
4146	slot, nritems);
4147	BUG();
4148	}
4149
4150	/*
4151	* item0..itemN ... dataN.offset..dataN.size .. data0.size
4152	*/
4153	/* first correct the data pointers */
4154	for (i = slot; i < nritems; i++) {
4155	u32 ioff;
4156
4157	ioff = btrfs_item_offset(eb: leaf, slot: i);
4158	btrfs_set_item_offset(eb: leaf, slot: i, val: ioff - data_size);
4159	}
4160
4161	/* shift the data */
4162	memmove_leaf_data(leaf, dst_offset: data_end - data_size, src_offset: data_end,
4163	len: old_data - data_end);
4164
4165	old_size = btrfs_item_size(eb: leaf, slot);
4166	btrfs_set_item_size(eb: leaf, slot, val: old_size + data_size);
4167	btrfs_mark_buffer_dirty(trans, buf: leaf);
4168
4169	if (unlikely(btrfs_leaf_free_space(leaf) < 0)) {
4170	btrfs_print_leaf(l: leaf);
4171	BUG();
4172	}
4173	}
4174
4175	/*
4176	* Make space in the node before inserting one or more items.
4177	*
4178	* @trans: transaction handle
4179	* @root: root we are inserting items to
4180	* @path: points to the leaf/slot where we are going to insert new items
4181	* @batch: information about the batch of items to insert
4182	*
4183	* Main purpose is to save stack depth by doing the bulk of the work in a
4184	* function that doesn't call btrfs_search_slot
4185	*/
4186	static void setup_items_for_insert(struct btrfs_trans_handle *trans,
4187	struct btrfs_root *root, struct btrfs_path *path,
4188	const struct btrfs_item_batch *batch)
4189	{
4190	struct btrfs_fs_info *fs_info = root->fs_info;
4191	int i;
4192	u32 nritems;
4193	unsigned int data_end;
4194	struct btrfs_disk_key disk_key;
4195	struct extent_buffer *leaf;
4196	int slot;
4197	u32 total_size;
4198
4199	/*
4200	* Before anything else, update keys in the parent and other ancestors
4201	* if needed, then release the write locks on them, so that other tasks
4202	* can use them while we modify the leaf.
4203	*/
4204	if (path->slots[0] == 0) {
4205	btrfs_cpu_key_to_disk(disk_key: &disk_key, cpu_key: &batch->keys[0]);
4206	fixup_low_keys(trans, path, key: &disk_key, level: 1);
4207	}
4208	btrfs_unlock_up_safe(path, level: 1);
4209
4210	leaf = path->nodes[0];
4211	slot = path->slots[0];
4212
4213	nritems = btrfs_header_nritems(eb: leaf);
4214	data_end = leaf_data_end(leaf);
4215	total_size = batch->total_data_size + (batch->nr * sizeof(struct btrfs_item));
4216
4217	if (unlikely(btrfs_leaf_free_space(leaf) < total_size)) {
4218	btrfs_print_leaf(l: leaf);
4219	btrfs_crit(fs_info, "not enough freespace need %u have %d",
4220	total_size, btrfs_leaf_free_space(leaf));
4221	BUG();
4222	}
4223
4224	if (slot != nritems) {
4225	unsigned int old_data = btrfs_item_data_end(eb: leaf, nr: slot);
4226
4227	if (unlikely(old_data < data_end)) {
4228	btrfs_print_leaf(l: leaf);
4229	btrfs_crit(fs_info,
4230	"item at slot %d with data offset %u beyond data end of leaf %u",
4231	slot, old_data, data_end);
4232	BUG();
4233	}
4234	/*
4235	* item0..itemN ... dataN.offset..dataN.size .. data0.size
4236	*/
4237	/* first correct the data pointers */
4238	for (i = slot; i < nritems; i++) {
4239	u32 ioff;
4240
4241	ioff = btrfs_item_offset(eb: leaf, slot: i);
4242	btrfs_set_item_offset(eb: leaf, slot: i,
4243	val: ioff - batch->total_data_size);
4244	}
4245	/* shift the items */
4246	memmove_leaf_items(leaf, dst_item: slot + batch->nr, src_item: slot, nr_items: nritems - slot);
4247
4248	/* shift the data */
4249	memmove_leaf_data(leaf, dst_offset: data_end - batch->total_data_size,
4250	src_offset: data_end, len: old_data - data_end);
4251	data_end = old_data;
4252	}
4253
4254	/* setup the item for the new data */
4255	for (i = 0; i < batch->nr; i++) {
4256	btrfs_cpu_key_to_disk(disk_key: &disk_key, cpu_key: &batch->keys[i]);
4257	btrfs_set_item_key(eb: leaf, disk_key: &disk_key, nr: slot + i);
4258	data_end -= batch->data_sizes[i];
4259	btrfs_set_item_offset(eb: leaf, slot: slot + i, val: data_end);
4260	btrfs_set_item_size(eb: leaf, slot: slot + i, val: batch->data_sizes[i]);
4261	}
4262
4263	btrfs_set_header_nritems(eb: leaf, val: nritems + batch->nr);
4264	btrfs_mark_buffer_dirty(trans, buf: leaf);
4265
4266	if (unlikely(btrfs_leaf_free_space(leaf) < 0)) {
4267	btrfs_print_leaf(l: leaf);
4268	BUG();
4269	}
4270	}
4271
4272	/*
4273	* Insert a new item into a leaf.
4274	*
4275	* @trans: Transaction handle.
4276	* @root: The root of the btree.
4277	* @path: A path pointing to the target leaf and slot.
4278	* @key: The key of the new item.
4279	* @data_size: The size of the data associated with the new key.
4280	*/
4281	void btrfs_setup_item_for_insert(struct btrfs_trans_handle *trans,
4282	struct btrfs_root *root,
4283	struct btrfs_path *path,
4284	const struct btrfs_key *key,
4285	u32 data_size)
4286	{
4287	struct btrfs_item_batch batch;
4288
4289	batch.keys = key;
4290	batch.data_sizes = &data_size;
4291	batch.total_data_size = data_size;
4292	batch.nr = 1;
4293
4294	setup_items_for_insert(trans, root, path, batch: &batch);
4295	}
4296
4297	/*
4298	* Given a key and some data, insert items into the tree.
4299	* This does all the path init required, making room in the tree if needed.
4300	*
4301	* Returns: 0 on success
4302	* -EEXIST if the first key already exists
4303	* < 0 on other errors
4304	*/
4305	int btrfs_insert_empty_items(struct btrfs_trans_handle *trans,
4306	struct btrfs_root *root,
4307	struct btrfs_path *path,
4308	const struct btrfs_item_batch *batch)
4309	{
4310	int ret = 0;
4311	int slot;
4312	u32 total_size;
4313
4314	total_size = batch->total_data_size + (batch->nr * sizeof(struct btrfs_item));
4315	ret = btrfs_search_slot(trans, root, key: &batch->keys[0], p: path, ins_len: total_size, cow: 1);
4316	if (ret == 0)
4317	return -EEXIST;
4318	if (ret < 0)
4319	return ret;
4320
4321	slot = path->slots[0];
4322	BUG_ON(slot < 0);
4323
4324	setup_items_for_insert(trans, root, path, batch);
4325	return 0;
4326	}
4327
4328	/*
4329	* Given a key and some data, insert an item into the tree.
4330	* This does all the path init required, making room in the tree if needed.
4331	*/
4332	int btrfs_insert_item(struct btrfs_trans_handle *trans, struct btrfs_root *root,
4333	const struct btrfs_key *cpu_key, void *data,
4334	u32 data_size)
4335	{
4336	int ret = 0;
4337	BTRFS_PATH_AUTO_FREE(path);
4338	struct extent_buffer *leaf;
4339	unsigned long ptr;
4340
4341	path = btrfs_alloc_path();
4342	if (!path)
4343	return -ENOMEM;
4344	ret = btrfs_insert_empty_item(trans, root, path, key: cpu_key, data_size);
4345	if (!ret) {
4346	leaf = path->nodes[0];
4347	ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
4348	write_extent_buffer(eb: leaf, src: data, start: ptr, len: data_size);
4349	btrfs_mark_buffer_dirty(trans, buf: leaf);
4350	}
4351	return ret;
4352	}
4353
4354	/*
4355	* This function duplicates an item, giving 'new_key' to the new item.
4356	* It guarantees both items live in the same tree leaf and the new item is
4357	* contiguous with the original item.
4358	*
4359	* This allows us to split a file extent in place, keeping a lock on the leaf
4360	* the entire time.
4361	*/
4362	int btrfs_duplicate_item(struct btrfs_trans_handle *trans,
4363	struct btrfs_root *root,
4364	struct btrfs_path *path,
4365	const struct btrfs_key *new_key)
4366	{
4367	struct extent_buffer *leaf;
4368	int ret;
4369	u32 item_size;
4370
4371	leaf = path->nodes[0];
4372	item_size = btrfs_item_size(eb: leaf, slot: path->slots[0]);
4373	ret = setup_leaf_for_split(trans, root, path,
4374	ins_len: item_size + sizeof(struct btrfs_item));
4375	if (ret)
4376	return ret;
4377
4378	path->slots[0]++;
4379	btrfs_setup_item_for_insert(trans, root, path, key: new_key, data_size: item_size);
4380	leaf = path->nodes[0];
4381	memcpy_extent_buffer(dst: leaf,
4382	btrfs_item_ptr_offset(leaf, path->slots[0]),
4383	btrfs_item_ptr_offset(leaf, path->slots[0] - 1),
4384	len: item_size);
4385	return 0;
4386	}
4387
4388	/*
4389	* delete the pointer from a given node.
4390	*
4391	* the tree should have been previously balanced so the deletion does not
4392	* empty a node.
4393	*
4394	* This is exported for use inside btrfs-progs, don't un-export it.
4395	*/
4396	int btrfs_del_ptr(struct btrfs_trans_handle *trans, struct btrfs_root *root,
4397	struct btrfs_path *path, int level, int slot)
4398	{
4399	struct extent_buffer *parent = path->nodes[level];
4400	u32 nritems;
4401	int ret;
4402
4403	nritems = btrfs_header_nritems(eb: parent);
4404	if (slot != nritems - 1) {
4405	if (level) {
4406	ret = btrfs_tree_mod_log_insert_move(eb: parent, dst_slot: slot,
4407	src_slot: slot + 1, nr_items: nritems - slot - 1);
4408	if (unlikely(ret < 0)) {
4409	btrfs_abort_transaction(trans, ret);
4410	return ret;
4411	}
4412	}
4413	memmove_extent_buffer(dst: parent,
4414	dst_offset: btrfs_node_key_ptr_offset(eb: parent, nr: slot),
4415	src_offset: btrfs_node_key_ptr_offset(eb: parent, nr: slot + 1),
4416	len: sizeof(struct btrfs_key_ptr) *
4417	(nritems - slot - 1));
4418	} else if (level) {
4419	ret = btrfs_tree_mod_log_insert_key(eb: parent, slot,
4420	op: BTRFS_MOD_LOG_KEY_REMOVE);
4421	if (unlikely(ret < 0)) {
4422	btrfs_abort_transaction(trans, ret);
4423	return ret;
4424	}
4425	}
4426
4427	nritems--;
4428	btrfs_set_header_nritems(eb: parent, val: nritems);
4429	if (nritems == 0 && parent == root->node) {
4430	BUG_ON(btrfs_header_level(root->node) != 1);
4431	/* just turn the root into a leaf and break */
4432	btrfs_set_header_level(eb: root->node, val: 0);
4433	} else if (slot == 0) {
4434	struct btrfs_disk_key disk_key;
4435
4436	btrfs_node_key(eb: parent, disk_key: &disk_key, nr: 0);
4437	fixup_low_keys(trans, path, key: &disk_key, level: level + 1);
4438	}
4439	btrfs_mark_buffer_dirty(trans, buf: parent);
4440	return 0;
4441	}
4442
4443	/*
4444	* a helper function to delete the leaf pointed to by path->slots[1] and
4445	* path->nodes[1].
4446	*
4447	* This deletes the pointer in path->nodes[1] and frees the leaf
4448	* block extent. zero is returned if it all worked out, < 0 otherwise.
4449	*
4450	* The path must have already been setup for deleting the leaf, including
4451	* all the proper balancing. path->nodes[1] must be locked.
4452	*/
4453	static noinline int btrfs_del_leaf(struct btrfs_trans_handle *trans,
4454	struct btrfs_root *root,
4455	struct btrfs_path *path,
4456	struct extent_buffer *leaf)
4457	{
4458	int ret;
4459
4460	WARN_ON(btrfs_header_generation(leaf) != trans->transid);
4461	ret = btrfs_del_ptr(trans, root, path, level: 1, slot: path->slots[1]);
4462	if (ret < 0)
4463	return ret;
4464
4465	/*
4466	* btrfs_free_extent is expensive, we want to make sure we
4467	* aren't holding any locks when we call it
4468	*/
4469	btrfs_unlock_up_safe(path, level: 0);
4470
4471	root_sub_used_bytes(root);
4472
4473	refcount_inc(r: &leaf->refs);
4474	ret = btrfs_free_tree_block(trans, root_id: btrfs_root_id(root), buf: leaf, parent: 0, last_ref: 1);
4475	free_extent_buffer_stale(eb: leaf);
4476	if (ret < 0)
4477	btrfs_abort_transaction(trans, ret);
4478
4479	return ret;
4480	}
4481	/*
4482	* delete the item at the leaf level in path. If that empties
4483	* the leaf, remove it from the tree
4484	*/
4485	int btrfs_del_items(struct btrfs_trans_handle *trans, struct btrfs_root *root,
4486	struct btrfs_path *path, int slot, int nr)
4487	{
4488	struct btrfs_fs_info *fs_info = root->fs_info;
4489	struct extent_buffer *leaf;
4490	int ret = 0;
4491	int wret;
4492	u32 nritems;
4493
4494	leaf = path->nodes[0];
4495	nritems = btrfs_header_nritems(eb: leaf);
4496
4497	if (slot + nr != nritems) {
4498	const u32 last_off = btrfs_item_offset(eb: leaf, slot: slot + nr - 1);
4499	const int data_end = leaf_data_end(leaf);
4500	u32 dsize = 0;
4501	int i;
4502
4503	for (i = 0; i < nr; i++)
4504	dsize += btrfs_item_size(eb: leaf, slot: slot + i);
4505
4506	memmove_leaf_data(leaf, dst_offset: data_end + dsize, src_offset: data_end,
4507	len: last_off - data_end);
4508
4509	for (i = slot + nr; i < nritems; i++) {
4510	u32 ioff;
4511
4512	ioff = btrfs_item_offset(eb: leaf, slot: i);
4513	btrfs_set_item_offset(eb: leaf, slot: i, val: ioff + dsize);
4514	}
4515
4516	memmove_leaf_items(leaf, dst_item: slot, src_item: slot + nr, nr_items: nritems - slot - nr);
4517	}
4518	btrfs_set_header_nritems(eb: leaf, val: nritems - nr);
4519	nritems -= nr;
4520
4521	/* delete the leaf if we've emptied it */
4522	if (nritems == 0) {
4523	if (leaf != root->node) {
4524	btrfs_clear_buffer_dirty(trans, buf: leaf);
4525	ret = btrfs_del_leaf(trans, root, path, leaf);
4526	if (ret < 0)
4527	return ret;
4528	}
4529	} else {
4530	int used = leaf_space_used(l: leaf, start: 0, nr: nritems);
4531	if (slot == 0) {
4532	struct btrfs_disk_key disk_key;
4533
4534	btrfs_item_key(eb: leaf, disk_key: &disk_key, nr: 0);
4535	fixup_low_keys(trans, path, key: &disk_key, level: 1);
4536	}
4537
4538	/*
4539	* Try to delete the leaf if it is mostly empty. We do this by
4540	* trying to move all its items into its left and right neighbours.
4541	* If we can't move all the items, then we don't delete it - it's
4542	* not ideal, but future insertions might fill the leaf with more
4543	* items, or items from other leaves might be moved later into our
4544	* leaf due to deletions on those leaves.
4545	*/
4546	if (used < BTRFS_LEAF_DATA_SIZE(info: fs_info) / 3) {
4547	u32 min_push_space;
4548
4549	/* push_leaf_left fixes the path.
4550	* make sure the path still points to our leaf
4551	* for possible call to btrfs_del_ptr below
4552	*/
4553	slot = path->slots[1];
4554	refcount_inc(r: &leaf->refs);
4555	/*
4556	* We want to be able to at least push one item to the
4557	* left neighbour leaf, and that's the first item.
4558	*/
4559	min_push_space = sizeof(struct btrfs_item) +
4560	btrfs_item_size(eb: leaf, slot: 0);
4561	wret = push_leaf_left(trans, root, path, min_data_size: 0,
4562	data_size: min_push_space, empty: 1, max_slot: (u32)-1);
4563	if (wret < 0 && wret != -ENOSPC)
4564	ret = wret;
4565
4566	if (path->nodes[0] == leaf &&
4567	btrfs_header_nritems(eb: leaf)) {
4568	/*
4569	* If we were not able to push all items from our
4570	* leaf to its left neighbour, then attempt to
4571	* either push all the remaining items to the
4572	* right neighbour or none. There's no advantage
4573	* in pushing only some items, instead of all, as
4574	* it's pointless to end up with a leaf having
4575	* too few items while the neighbours can be full
4576	* or nearly full.
4577	*/
4578	nritems = btrfs_header_nritems(eb: leaf);
4579	min_push_space = leaf_space_used(l: leaf, start: 0, nr: nritems);
4580	wret = push_leaf_right(trans, root, path, min_data_size: 0,
4581	data_size: min_push_space, empty: 1, min_slot: 0);
4582	if (wret < 0 && wret != -ENOSPC)
4583	ret = wret;
4584	}
4585
4586	if (btrfs_header_nritems(eb: leaf) == 0) {
4587	path->slots[1] = slot;
4588	ret = btrfs_del_leaf(trans, root, path, leaf);
4589	free_extent_buffer(eb: leaf);
4590	if (ret < 0)
4591	return ret;
4592	} else {
4593	/* if we're still in the path, make sure
4594	* we're dirty. Otherwise, one of the
4595	* push_leaf functions must have already
4596	* dirtied this buffer
4597	*/
4598	if (path->nodes[0] == leaf)
4599	btrfs_mark_buffer_dirty(trans, buf: leaf);
4600	free_extent_buffer(eb: leaf);
4601	}
4602	} else {
4603	btrfs_mark_buffer_dirty(trans, buf: leaf);
4604	}
4605	}
4606	return ret;
4607	}
4608
4609	/*
4610	* A helper function to walk down the tree starting at min_key, and looking
4611	* for leaves that have a minimum transaction id.
4612	* This is used by the btree defrag code, and tree logging
4613	*
4614	* This does not cow, but it does stuff the starting key it finds back
4615	* into min_key, so you can call btrfs_search_slot with cow=1 on the
4616	* key and get a writable path.
4617	*
4618	* min_trans indicates the oldest transaction that you are interested
4619	* in walking through. Any nodes or leaves older than min_trans are
4620	* skipped over (without reading them).
4621	*
4622	* returns zero if something useful was found, < 0 on error and 1 if there
4623	* was nothing in the tree that matched the search criteria.
4624	*/
4625	int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key,
4626	struct btrfs_path *path,
4627	u64 min_trans)
4628	{
4629	struct extent_buffer *cur;
4630	int slot;
4631	int sret;
4632	u32 nritems;
4633	int level;
4634	int ret = 1;
4635	const bool keep_locks = path->keep_locks;
4636
4637	ASSERT(!path->nowait);
4638	ASSERT(path->lowest_level == 0);
4639	path->keep_locks = true;
4640	again:
4641	cur = btrfs_read_lock_root_node(root);
4642	level = btrfs_header_level(eb: cur);
4643	WARN_ON(path->nodes[level]);
4644	path->nodes[level] = cur;
4645	path->locks[level] = BTRFS_READ_LOCK;
4646
4647	if (btrfs_header_generation(eb: cur) < min_trans) {
4648	ret = 1;
4649	goto out;
4650	}
4651	while (1) {
4652	nritems = btrfs_header_nritems(eb: cur);
4653	level = btrfs_header_level(eb: cur);
4654	sret = btrfs_bin_search(eb: cur, first_slot: 0, key: min_key, slot: &slot);
4655	if (sret < 0) {
4656	ret = sret;
4657	goto out;
4658	}
4659
4660	/* At level 0 we're done, setup the path and exit. */
4661	if (level == 0) {
4662	if (slot >= nritems)
4663	goto find_next_key;
4664	ret = 0;
4665	path->slots[level] = slot;
4666	/* Save our key for returning back. */
4667	btrfs_item_key_to_cpu(eb: cur, cpu_key: min_key, nr: slot);
4668	goto out;
4669	}
4670	if (sret && slot > 0)
4671	slot--;
4672	/*
4673	* check this node pointer against the min_trans parameters.
4674	* If it is too old, skip to the next one.
4675	*/
4676	while (slot < nritems) {
4677	u64 gen;
4678
4679	gen = btrfs_node_ptr_generation(eb: cur, nr: slot);
4680	if (gen < min_trans) {
4681	slot++;
4682	continue;
4683	}
4684	break;
4685	}
4686	find_next_key:
4687	/*
4688	* we didn't find a candidate key in this node, walk forward
4689	* and find another one
4690	*/
4691	path->slots[level] = slot;
4692	if (slot >= nritems) {
4693	sret = btrfs_find_next_key(root, path, key: min_key, lowest_level: level,
4694	min_trans);
4695	if (sret == 0) {
4696	btrfs_release_path(p: path);
4697	goto again;
4698	} else {
4699	goto out;
4700	}
4701	}
4702	cur = btrfs_read_node_slot(parent: cur, slot);
4703	if (IS_ERR(ptr: cur)) {
4704	ret = PTR_ERR(ptr: cur);
4705	goto out;
4706	}
4707
4708	btrfs_tree_read_lock(eb: cur);
4709
4710	path->locks[level - 1] = BTRFS_READ_LOCK;
4711	path->nodes[level - 1] = cur;
4712	unlock_up(path, level, lowest_unlock: 1, min_write_lock_level: 0, NULL);
4713	}
4714	out:
4715	path->keep_locks = keep_locks;
4716	if (ret == 0)
4717	btrfs_unlock_up_safe(path, level: 1);
4718	return ret;
4719	}
4720
4721	/*
4722	* this is similar to btrfs_next_leaf, but does not try to preserve
4723	* and fixup the path. It looks for and returns the next key in the
4724	* tree based on the current path and the min_trans parameters.
4725	*
4726	* 0 is returned if another key is found, < 0 if there are any errors
4727	* and 1 is returned if there are no higher keys in the tree
4728	*
4729	* path->keep_locks should be set to true on the search made before
4730	* calling this function.
4731	*/
4732	int btrfs_find_next_key(struct btrfs_root *root, struct btrfs_path *path,
4733	struct btrfs_key *key, int level, u64 min_trans)
4734	{
4735	int slot;
4736	struct extent_buffer *c;
4737
4738	WARN_ON(!path->keep_locks && !path->skip_locking);
4739	while (level < BTRFS_MAX_LEVEL) {
4740	if (!path->nodes[level])
4741	return 1;
4742
4743	slot = path->slots[level] + 1;
4744	c = path->nodes[level];
4745	next:
4746	if (slot >= btrfs_header_nritems(eb: c)) {
4747	int ret;
4748	int orig_lowest;
4749	struct btrfs_key cur_key;
4750	if (level + 1 >= BTRFS_MAX_LEVEL ||
4751	!path->nodes[level + 1])
4752	return 1;
4753
4754	if (path->locks[level + 1] || path->skip_locking) {
4755	level++;
4756	continue;
4757	}
4758
4759	slot = btrfs_header_nritems(eb: c) - 1;
4760	if (level == 0)
4761	btrfs_item_key_to_cpu(eb: c, cpu_key: &cur_key, nr: slot);
4762	else
4763	btrfs_node_key_to_cpu(eb: c, cpu_key: &cur_key, nr: slot);
4764
4765	orig_lowest = path->lowest_level;
4766	btrfs_release_path(p: path);
4767	path->lowest_level = level;
4768	ret = btrfs_search_slot(NULL, root, key: &cur_key, p: path,
4769	ins_len: 0, cow: 0);
4770	path->lowest_level = orig_lowest;
4771	if (ret < 0)
4772	return ret;
4773
4774	c = path->nodes[level];
4775	slot = path->slots[level];
4776	if (ret == 0)
4777	slot++;
4778	goto next;
4779	}
4780
4781	if (level == 0)
4782	btrfs_item_key_to_cpu(eb: c, cpu_key: key, nr: slot);
4783	else {
4784	u64 gen = btrfs_node_ptr_generation(eb: c, nr: slot);
4785
4786	if (gen < min_trans) {
4787	slot++;
4788	goto next;
4789	}
4790	btrfs_node_key_to_cpu(eb: c, cpu_key: key, nr: slot);
4791	}
4792	return 0;
4793	}
4794	return 1;
4795	}
4796
4797	int btrfs_next_old_leaf(struct btrfs_root *root, struct btrfs_path *path,
4798	u64 time_seq)
4799	{
4800	int slot;
4801	int level;
4802	struct extent_buffer *c;
4803	struct extent_buffer *next;
4804	struct btrfs_fs_info *fs_info = root->fs_info;
4805	struct btrfs_key key;
4806	bool need_commit_sem = false;
4807	u32 nritems;
4808	int ret;
4809	int i;
4810
4811	/*
4812	* The nowait semantics are used only for write paths, where we don't
4813	* use the tree mod log and sequence numbers.
4814	*/
4815	if (time_seq)
4816	ASSERT(!path->nowait);
4817
4818	nritems = btrfs_header_nritems(eb: path->nodes[0]);
4819	if (nritems == 0)
4820	return 1;
4821
4822	btrfs_item_key_to_cpu(eb: path->nodes[0], cpu_key: &key, nr: nritems - 1);
4823	again:
4824	level = 1;
4825	next = NULL;
4826	btrfs_release_path(p: path);
4827
4828	path->keep_locks = true;
4829
4830	if (time_seq) {
4831	ret = btrfs_search_old_slot(root, key: &key, p: path, time_seq);
4832	} else {
4833	if (path->need_commit_sem) {
4834	path->need_commit_sem = false;
4835	need_commit_sem = true;
4836	if (path->nowait) {
4837	if (!down_read_trylock(sem: &fs_info->commit_root_sem)) {
4838	ret = -EAGAIN;
4839	goto done;
4840	}
4841	} else {
4842	down_read(sem: &fs_info->commit_root_sem);
4843	}
4844	}
4845	ret = btrfs_search_slot(NULL, root, key: &key, p: path, ins_len: 0, cow: 0);
4846	}
4847	path->keep_locks = false;
4848
4849	if (ret < 0)
4850	goto done;
4851
4852	nritems = btrfs_header_nritems(eb: path->nodes[0]);
4853	/*
4854	* By releasing the path above we dropped all our locks. A balance
4855	* could have happened and
4856	*
4857	* 1. added more items after the previous last item
4858	* 2. deleted the previous last item
4859	*
4860	* So, check again here and advance the path if there are now more
4861	* items available.
4862	*/
4863	if (nritems > 0 && path->slots[0] <= nritems - 1) {
4864	if (ret == 0 && path->slots[0] != nritems - 1) {
4865	path->slots[0]++;
4866	goto done;
4867	} else if (ret > 0) {
4868	ret = 0;
4869	goto done;
4870	}
4871	}
4872
4873	while (level < BTRFS_MAX_LEVEL) {
4874	if (!path->nodes[level]) {
4875	ret = 1;
4876	goto done;
4877	}
4878
4879	slot = path->slots[level] + 1;
4880	c = path->nodes[level];
4881	if (slot >= btrfs_header_nritems(eb: c)) {
4882	level++;
4883	if (level == BTRFS_MAX_LEVEL) {
4884	ret = 1;
4885	goto done;
4886	}
4887	continue;
4888	}
4889
4890
4891	/*
4892	* Our current level is where we're going to start from, and to
4893	* make sure lockdep doesn't complain we need to drop our locks
4894	* and nodes from 0 to our current level.
4895	*/
4896	for (i = 0; i < level; i++) {
4897	if (path->locks[level]) {
4898	btrfs_tree_read_unlock(eb: path->nodes[i]);
4899	path->locks[i] = 0;
4900	}
4901	free_extent_buffer(eb: path->nodes[i]);
4902	path->nodes[i] = NULL;
4903	}
4904
4905	next = c;
4906	ret = read_block_for_search(root, p: path, eb_ret: &next, slot, key: &key);
4907	if (ret == -EAGAIN && !path->nowait)
4908	goto again;
4909
4910	if (ret < 0) {
4911	btrfs_release_path(p: path);
4912	goto done;
4913	}
4914
4915	if (!path->skip_locking) {
4916	ret = btrfs_try_tree_read_lock(eb: next);
4917	if (!ret && path->nowait) {
4918	ret = -EAGAIN;
4919	goto done;
4920	}
4921	if (!ret && time_seq) {
4922	/*
4923	* If we don't get the lock, we may be racing
4924	* with push_leaf_left, holding that lock while
4925	* itself waiting for the leaf we've currently
4926	* locked. To solve this situation, we give up
4927	* on our lock and cycle.
4928	*/
4929	free_extent_buffer(eb: next);
4930	btrfs_release_path(p: path);
4931	cond_resched();
4932	goto again;
4933	}
4934	if (!ret)
4935	btrfs_tree_read_lock(eb: next);
4936	}
4937	break;
4938	}
4939	path->slots[level] = slot;
4940	while (1) {
4941	level--;
4942	path->nodes[level] = next;
4943	path->slots[level] = 0;
4944	if (!path->skip_locking)
4945	path->locks[level] = BTRFS_READ_LOCK;
4946	if (!level)
4947	break;
4948
4949	ret = read_block_for_search(root, p: path, eb_ret: &next, slot: 0, key: &key);
4950	if (ret == -EAGAIN && !path->nowait)
4951	goto again;
4952
4953	if (ret < 0) {
4954	btrfs_release_path(p: path);
4955	goto done;
4956	}
4957
4958	if (!path->skip_locking) {
4959	if (path->nowait) {
4960	if (!btrfs_try_tree_read_lock(eb: next)) {
4961	ret = -EAGAIN;
4962	goto done;
4963	}
4964	} else {
4965	btrfs_tree_read_lock(eb: next);
4966	}
4967	}
4968	}
4969	ret = 0;
4970	done:
4971	unlock_up(path, level: 0, lowest_unlock: 1, min_write_lock_level: 0, NULL);
4972	if (need_commit_sem) {
4973	int ret2;
4974
4975	path->need_commit_sem = true;
4976	ret2 = finish_need_commit_sem_search(path);
4977	up_read(sem: &fs_info->commit_root_sem);
4978	if (ret2)
4979	ret = ret2;
4980	}
4981
4982	return ret;
4983	}
4984
4985	int btrfs_next_old_item(struct btrfs_root *root, struct btrfs_path *path, u64 time_seq)
4986	{
4987	path->slots[0]++;
4988	if (path->slots[0] >= btrfs_header_nritems(eb: path->nodes[0]))
4989	return btrfs_next_old_leaf(root, path, time_seq);
4990	return 0;
4991	}
4992
4993	/*
4994	* this uses btrfs_prev_leaf to walk backwards in the tree, and keeps
4995	* searching until it gets past min_objectid or finds an item of 'type'
4996	*
4997	* returns 0 if something is found, 1 if nothing was found and < 0 on error
4998	*/
4999	int btrfs_previous_item(struct btrfs_root *root,
5000	struct btrfs_path *path, u64 min_objectid,
5001	int type)
5002	{
5003	struct btrfs_key found_key;
5004	struct extent_buffer *leaf;
5005	u32 nritems;
5006	int ret;
5007
5008	while (1) {
5009	if (path->slots[0] == 0) {
5010	ret = btrfs_prev_leaf(root, path);
5011	if (ret != 0)
5012	return ret;
5013	} else {
5014	path->slots[0]--;
5015	}
5016	leaf = path->nodes[0];
5017	nritems = btrfs_header_nritems(eb: leaf);
5018	if (nritems == 0)
5019	return 1;
5020	if (path->slots[0] == nritems)
5021	path->slots[0]--;
5022
5023	btrfs_item_key_to_cpu(eb: leaf, cpu_key: &found_key, nr: path->slots[0]);
5024	if (found_key.objectid < min_objectid)
5025	break;
5026	if (found_key.type == type)
5027	return 0;
5028	if (found_key.objectid == min_objectid &&
5029	found_key.type < type)
5030	break;
5031	}
5032	return 1;
5033	}
5034
5035	/*
5036	* search in extent tree to find a previous Metadata/Data extent item with
5037	* min objecitd.
5038	*
5039	* returns 0 if something is found, 1 if nothing was found and < 0 on error
5040	*/
5041	int btrfs_previous_extent_item(struct btrfs_root *root,
5042	struct btrfs_path *path, u64 min_objectid)
5043	{
5044	struct btrfs_key found_key;
5045	struct extent_buffer *leaf;
5046	u32 nritems;
5047	int ret;
5048
5049	while (1) {
5050	if (path->slots[0] == 0) {
5051	ret = btrfs_prev_leaf(root, path);
5052	if (ret != 0)
5053	return ret;
5054	} else {
5055	path->slots[0]--;
5056	}
5057	leaf = path->nodes[0];
5058	nritems = btrfs_header_nritems(eb: leaf);
5059	if (nritems == 0)
5060	return 1;
5061	if (path->slots[0] == nritems)
5062	path->slots[0]--;
5063
5064	btrfs_item_key_to_cpu(eb: leaf, cpu_key: &found_key, nr: path->slots[0]);
5065	if (found_key.objectid < min_objectid)
5066	break;
5067	if (found_key.type == BTRFS_EXTENT_ITEM_KEY ||
5068	found_key.type == BTRFS_METADATA_ITEM_KEY)
5069	return 0;
5070	if (found_key.objectid == min_objectid &&
5071	found_key.type < BTRFS_EXTENT_ITEM_KEY)
5072	break;
5073	}
5074	return 1;
5075	}
5076
5077	int __init btrfs_ctree_init(void)
5078	{
5079	btrfs_path_cachep = KMEM_CACHE(btrfs_path, 0);
5080	if (!btrfs_path_cachep)
5081	return -ENOMEM;
5082	return 0;
5083	}
5084
5085	void __cold btrfs_ctree_exit(void)
5086	{
5087	kmem_cache_destroy(s: btrfs_path_cachep);
5088	}
5089