~hc/RK356X_SDK_RELEASE.git

..	..	@@ -12,6 +12,8 @@
12	12	#include "transaction.h"
13	13	#include "print-tree.h"
14	14	#include "locking.h"
	15	+#include "volumes.h"
	16	+#include "qgroup.h"
15	17
16	18	static int split_node(struct btrfs_trans_handle *trans, struct btrfs_root
17	19	root, struct btrfs_path path, int level);
..	..	@@ -19,73 +21,61 @@
19	21	const struct btrfs_key ins_key, struct btrfs_path path,
20	22	int data_size, int extend);
21	23	static int push_node_left(struct btrfs_trans_handle *trans,
22		- struct btrfs_fs_info *fs_info,
23	24	struct extent_buffer *dst,
24	25	struct extent_buffer *src, int empty);
25	26	static int balance_node_right(struct btrfs_trans_handle *trans,
26		- struct btrfs_fs_info *fs_info,
27	27	struct extent_buffer *dst_buf,
28	28	struct extent_buffer *src_buf);
29	29	static void del_ptr(struct btrfs_root root, struct btrfs_path path,
30	30	int level, int slot);
31	31
	32	+static const struct btrfs_csums {
	33	+ u16 size;
	34	+ const char name[10];
	35	+ const char driver[12];
	36	+} btrfs_csums[] = {
	37	+ [BTRFS_CSUM_TYPE_CRC32] = { .size = 4, .name = "crc32c" },
	38	+ [BTRFS_CSUM_TYPE_XXHASH] = { .size = 8, .name = "xxhash64" },
	39	+ [BTRFS_CSUM_TYPE_SHA256] = { .size = 32, .name = "sha256" },
	40	+ [BTRFS_CSUM_TYPE_BLAKE2] = { .size = 32, .name = "blake2b",
	41	+ .driver = "blake2b-256" },
	42	+};
	43	+
	44	+int btrfs_super_csum_size(const struct btrfs_super_block *s)
	45	+{
	46	+ u16 t = btrfs_super_csum_type(s);
	47	+ /*
	48	+ * csum type is validated at mount time
	49	+ */
	50	+ return btrfs_csums[t].size;
	51	+}
	52	+
	53	+const char *btrfs_super_csum_name(u16 csum_type)
	54	+{
	55	+ /* csum type is validated at mount time */
	56	+ return btrfs_csums[csum_type].name;
	57	+}
	58	+
	59	+/*
	60	+ * Return driver name if defined, otherwise the name that's also a valid driver
	61	+ * name
	62	+ */
	63	+const char *btrfs_super_csum_driver(u16 csum_type)
	64	+{
	65	+ /* csum type is validated at mount time */
	66	+ return btrfs_csums[csum_type].driver[0] ?
	67	+ btrfs_csums[csum_type].driver :
	68	+ btrfs_csums[csum_type].name;
	69	+}
	70	+
	71	+size_t __attribute_const__ btrfs_get_num_csums(void)
	72	+{
	73	+ return ARRAY_SIZE(btrfs_csums);
	74	+}
	75	+
32	76	struct btrfs_path *btrfs_alloc_path(void)
33	77	{
34	78	return kmem_cache_zalloc(btrfs_path_cachep, GFP_NOFS);
35		-}
36		-
37		-/*
38		- * set all locked nodes in the path to blocking locks. This should
39		- * be done before scheduling
40		- */
41		-noinline void btrfs_set_path_blocking(struct btrfs_path *p)
42		-{
43		- int i;
44		- for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
45		- if (!p->nodes[i] \|\| !p->locks[i])
46		- continue;
47		- btrfs_set_lock_blocking_rw(p->nodes[i], p->locks[i]);
48		- if (p->locks[i] == BTRFS_READ_LOCK)
49		- p->locks[i] = BTRFS_READ_LOCK_BLOCKING;
50		- else if (p->locks[i] == BTRFS_WRITE_LOCK)
51		- p->locks[i] = BTRFS_WRITE_LOCK_BLOCKING;
52		- }
53		-}
54		-
55		-/*
56		- * reset all the locked nodes in the patch to spinning locks.
57		- *
58		- * held is used to keep lockdep happy, when lockdep is enabled
59		- * we set held to a blocking lock before we go around and
60		- * retake all the spinlocks in the path. You can safely use NULL
61		- * for held
62		- */
63		-noinline void btrfs_clear_path_blocking(struct btrfs_path *p,
64		- struct extent_buffer *held, int held_rw)
65		-{
66		- int i;
67		-
68		- if (held) {
69		- btrfs_set_lock_blocking_rw(held, held_rw);
70		- if (held_rw == BTRFS_WRITE_LOCK)
71		- held_rw = BTRFS_WRITE_LOCK_BLOCKING;
72		- else if (held_rw == BTRFS_READ_LOCK)
73		- held_rw = BTRFS_READ_LOCK_BLOCKING;
74		- }
75		- btrfs_set_path_blocking(p);
76		-
77		- for (i = BTRFS_MAX_LEVEL - 1; i >= 0; i--) {
78		- if (p->nodes[i] && p->locks[i]) {
79		- btrfs_clear_lock_blocking_rw(p->nodes[i], p->locks[i]);
80		- if (p->locks[i] == BTRFS_WRITE_LOCK_BLOCKING)
81		- p->locks[i] = BTRFS_WRITE_LOCK;
82		- else if (p->locks[i] == BTRFS_READ_LOCK_BLOCKING)
83		- p->locks[i] = BTRFS_READ_LOCK;
84		- }
85		- }
86		-
87		- if (held)
88		- btrfs_clear_lock_blocking_rw(held, held_rw);
89	79	}
90	80
91	81	/* this also releases the path */
..	..	@@ -154,47 +144,10 @@
154	144	return eb;
155	145	}
156	146
157		-/* loop around taking references on and locking the root node of the
158		- * tree until you end up with a lock on the root. A locked buffer
159		- * is returned, with a reference held.
160		- */
161		-struct extent_buffer btrfs_lock_root_node(struct btrfs_root root)
162		-{
163		- struct extent_buffer *eb;
164		-
165		- while (1) {
166		- eb = btrfs_root_node(root);
167		- btrfs_tree_lock(eb);
168		- if (eb == root->node)
169		- break;
170		- btrfs_tree_unlock(eb);
171		- free_extent_buffer(eb);
172		- }
173		- return eb;
174		-}
175		-
176		-/* loop around taking references on and locking the root node of the
177		- * tree until you end up with a lock on the root. A locked buffer
178		- * is returned, with a reference held.
179		- */
180		-struct extent_buffer btrfs_read_lock_root_node(struct btrfs_root root)
181		-{
182		- struct extent_buffer *eb;
183		-
184		- while (1) {
185		- eb = btrfs_root_node(root);
186		- btrfs_tree_read_lock(eb);
187		- if (eb == root->node)
188		- break;
189		- btrfs_tree_read_unlock(eb);
190		- free_extent_buffer(eb);
191		- }
192		- return eb;
193		-}
194		-
195		-/* cowonly root (everything not a reference counted cow subvolume), just get
196		- * put onto a simple dirty list. transaction.c walks this to make sure they
197		- * get properly updated on disk.
	147	+/*
	148	+ * Cowonly root (not-shareable trees, everything not subvolume or reloc roots),
	149	+ * just get put onto a simple dirty list. Transaction walks this list to make
	150	+ * sure they get properly updated on disk.
198	151	*/
199	152	static void add_root_to_dirty_list(struct btrfs_root *root)
200	153	{
..	..	@@ -207,7 +160,7 @@
207	160	spin_lock(&fs_info->trans_lock);
208	161	if (!test_and_set_bit(BTRFS_ROOT_DIRTY, &root->state)) {
209	162	/* Want the extent tree to be the last on the list */
210		- if (root->objectid == BTRFS_EXTENT_TREE_OBJECTID)
	163	+ if (root->root_key.objectid == BTRFS_EXTENT_TREE_OBJECTID)
211	164	list_move_tail(&root->dirty_list,
212	165	&fs_info->dirty_cowonly_roots);
213	166	else
..	..	@@ -233,9 +186,9 @@
233	186	int level;
234	187	struct btrfs_disk_key disk_key;
235	188
236		- WARN_ON(test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
	189	+ WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) &&
237	190	trans->transid != fs_info->running_transaction->transid);
238		- WARN_ON(test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
	191	+ WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) &&
239	192	trans->transid != root->last_trans);
240	193
241	194	level = btrfs_header_level(buf);
..	..	@@ -245,7 +198,8 @@
245	198	btrfs_node_key(buf, &disk_key, 0);
246	199
247	200	cow = btrfs_alloc_tree_block(trans, root, 0, new_root_objectid,
248		- &disk_key, level, buf->start, 0);
	201	+ &disk_key, level, buf->start, 0,
	202	+ BTRFS_NESTING_NEW_ROOT);
249	203	if (IS_ERR(cow))
250	204	return PTR_ERR(cow);
251	205
..	..	@@ -260,7 +214,7 @@
260	214	else
261	215	btrfs_set_header_owner(cow, new_root_objectid);
262	216
263		- write_extent_buffer_fsid(cow, fs_info->fsid);
	217	+ write_extent_buffer_fsid(cow, fs_info->fs_devices->metadata_uuid);
264	218
265	219	WARN_ON(btrfs_header_generation(buf) > trans->transid);
266	220	if (new_root_objectid == BTRFS_TREE_RELOC_OBJECTID)
..	..	@@ -355,7 +309,6 @@
355	309	struct rb_root *tm_root;
356	310	struct rb_node *node;
357	311	struct rb_node *next;
358		- struct seq_list *cur_elem;
359	312	struct tree_mod_elem *tm;
360	313	u64 min_seq = (u64)-1;
361	314	u64 seq_putting = elem->seq;
..	..	@@ -367,18 +320,20 @@
367	320	list_del(&elem->list);
368	321	elem->seq = 0;
369	322
370		- list_for_each_entry(cur_elem, &fs_info->tree_mod_seq_list, list) {
371		- if (cur_elem->seq < min_seq) {
372		- if (seq_putting > cur_elem->seq) {
373		- /*
374		- * blocker with lower sequence number exists, we
375		- * cannot remove anything from the log
376		- */
377		- write_unlock(&fs_info->tree_mod_log_lock);
378		- return;
379		- }
380		- min_seq = cur_elem->seq;
	323	+ if (!list_empty(&fs_info->tree_mod_seq_list)) {
	324	+ struct seq_list *first;
	325	+
	326	+ first = list_first_entry(&fs_info->tree_mod_seq_list,
	327	+ struct seq_list, list);
	328	+ if (seq_putting > first->seq) {
	329	+ /*
	330	+ * Blocker with lower sequence number exists, we
	331	+ * cannot remove anything from the log.
	332	+ */
	333	+ write_unlock(&fs_info->tree_mod_log_lock);
	334	+ return;
381	335	}
	336	+ min_seq = first->seq;
382	337	}
383	338
384	339	/*
..	..	@@ -404,8 +359,6 @@
404	359	* The 'start address' is the logical address of the new root node
405	360	* for root replace operations, or the logical address of the affected
406	361	* block for all other operations.
407		- *
408		- * Note: must be called with write lock for fs_info::tree_mod_log_lock.
409	362	*/
410	363	static noinline int
411	364	__tree_mod_log_insert(struct btrfs_fs_info fs_info, struct tree_mod_elem tm)
..	..	@@ -414,6 +367,8 @@
414	367	struct rb_node **new;
415	368	struct rb_node *parent = NULL;
416	369	struct tree_mod_elem *cur;
	370	+
	371	+ lockdep_assert_held_write(&fs_info->tree_mod_log_lock);
417	372
418	373	tm->seq = btrfs_inc_tree_mod_seq(fs_info);
419	374
..	..	@@ -752,11 +707,11 @@
752	707	return __tree_mod_log_search(fs_info, start, min_seq, 0);
753	708	}
754	709
755		-static noinline int
756		-tree_mod_log_eb_copy(struct btrfs_fs_info fs_info, struct extent_buffer dst,
	710	+static noinline int tree_mod_log_eb_copy(struct extent_buffer *dst,
757	711	struct extent_buffer *src, unsigned long dst_offset,
758	712	unsigned long src_offset, int nr_items)
759	713	{
	714	+ struct btrfs_fs_info *fs_info = dst->fs_info;
760	715	int ret = 0;
761	716	struct tree_mod_elem **tm_list = NULL;
762	717	struct tree_mod_elem tm_list_add, tm_list_rem;
..	..	@@ -876,12 +831,11 @@
876	831	struct extent_buffer *buf)
877	832	{
878	833	/*
879		- * Tree blocks not in reference counted trees and tree roots
880		- * are never shared. If a block was allocated after the last
881		- * snapshot and the block was not allocated by tree relocation,
882		- * we know the block is not shared.
	834	+ * Tree blocks not in shareable trees and tree roots are never shared.
	835	+ * If a block was allocated after the last snapshot and the block was
	836	+ * not allocated by tree relocation, we know the block is not shared.
883	837	*/
884		- if (test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
	838	+ if (test_bit(BTRFS_ROOT_SHAREABLE, &root->state) &&
885	839	buf != root->node && buf != root->commit_root &&
886	840	(btrfs_header_generation(buf) <=
887	841	btrfs_root_last_snapshot(&root->root_item) \|\|
..	..	@@ -976,9 +930,7 @@
976	930	if (new_flags != 0) {
977	931	int level = btrfs_header_level(buf);
978	932
979		- ret = btrfs_set_disk_extent_flags(trans, fs_info,
980		- buf->start,
981		- buf->len,
	933	+ ret = btrfs_set_disk_extent_flags(trans, buf,
982	934	new_flags, level, 0);
983	935	if (ret)
984	936	return ret;
..	..	@@ -996,7 +948,7 @@
996	948	if (ret)
997	949	return ret;
998	950	}
999		- clean_tree_block(fs_info, buf);
	951	+ btrfs_clean_tree_block(buf);
1000	952	*last_ref = 1;
1001	953	}
1002	954	return 0;
..	..	@@ -1009,7 +961,8 @@
1009	961	const struct btrfs_disk_key *disk_key,
1010	962	int level,
1011	963	u64 hint,
1012		- u64 empty_size)
	964	+ u64 empty_size,
	965	+ enum btrfs_lock_nesting nest)
1013	966	{
1014	967	struct btrfs_fs_info *fs_info = root->fs_info;
1015	968	struct extent_buffer *ret;
..	..	@@ -1038,7 +991,7 @@
1038	991
1039	992	ret = btrfs_alloc_tree_block(trans, root, parent_start,
1040	993	root->root_key.objectid, disk_key, level,
1041		- hint, empty_size);
	994	+ hint, empty_size, nest);
1042	995	trans->can_flush_pending_bgs = true;
1043	996
1044	997	return ret;
..	..	@@ -1061,7 +1014,8 @@
1061	1014	struct extent_buffer *buf,
1062	1015	struct extent_buffer *parent, int parent_slot,
1063	1016	struct extent_buffer **cow_ret,
1064		- u64 search_start, u64 empty_size)
	1017	+ u64 search_start, u64 empty_size,
	1018	+ enum btrfs_lock_nesting nest)
1065	1019	{
1066	1020	struct btrfs_fs_info *fs_info = root->fs_info;
1067	1021	struct btrfs_disk_key disk_key;
..	..	@@ -1076,9 +1030,9 @@
1076	1030
1077	1031	btrfs_assert_tree_locked(buf);
1078	1032
1079		- WARN_ON(test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
	1033	+ WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) &&
1080	1034	trans->transid != fs_info->running_transaction->transid);
1081		- WARN_ON(test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
	1035	+ WARN_ON(test_bit(BTRFS_ROOT_SHAREABLE, &root->state) &&
1082	1036	trans->transid != root->last_trans);
1083	1037
1084	1038	level = btrfs_header_level(buf);
..	..	@@ -1092,7 +1046,7 @@
1092	1046	parent_start = parent->start;
1093	1047
1094	1048	cow = alloc_tree_block_no_bg_flush(trans, root, parent_start, &disk_key,
1095		- level, search_start, empty_size);
	1049	+ level, search_start, empty_size, nest);
1096	1050	if (IS_ERR(cow))
1097	1051	return PTR_ERR(cow);
1098	1052
..	..	@@ -1109,7 +1063,7 @@
1109	1063	else
1110	1064	btrfs_set_header_owner(cow, root->root_key.objectid);
1111	1065
1112		- write_extent_buffer_fsid(cow, fs_info->fsid);
	1066	+ write_extent_buffer_fsid(cow, fs_info->fs_devices->metadata_uuid);
1113	1067
1114	1068	ret = update_ref_for_cow(trans, root, buf, cow, &last_ref);
1115	1069	if (ret) {
..	..	@@ -1119,7 +1073,7 @@
1119	1073	return ret;
1120	1074	}
1121	1075
1122		- if (test_bit(BTRFS_ROOT_REF_COWS, &root->state)) {
	1076	+ if (test_bit(BTRFS_ROOT_SHAREABLE, &root->state)) {
1123	1077	ret = btrfs_reloc_cow_block(trans, root, buf, cow);
1124	1078	if (ret) {
1125	1079	btrfs_tree_unlock(cow);
..	..	@@ -1135,7 +1089,7 @@
1135	1089	btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
1136	1090	parent_start = buf->start;
1137	1091
1138		- extent_buffer_get(cow);
	1092	+ atomic_inc(&cow->refs);
1139	1093	ret = tree_mod_log_insert_root(root->node, cow, 1);
1140	1094	BUG_ON(ret < 0);
1141	1095	rcu_assign_pointer(root->node, cow);
..	..	@@ -1254,7 +1208,7 @@
1254	1208	switch (tm->op) {
1255	1209	case MOD_LOG_KEY_REMOVE_WHILE_FREEING:
1256	1210	BUG_ON(tm->slot < n);
1257		- /* Fallthrough */
	1211	+ fallthrough;
1258	1212	case MOD_LOG_KEY_REMOVE_WHILE_MOVING:
1259	1213	case MOD_LOG_KEY_REMOVE:
1260	1214	btrfs_set_node_key(eb, &tm->key, tm->slot);
..	..	@@ -1328,7 +1282,7 @@
1328	1282	return eb;
1329	1283
1330	1284	btrfs_set_path_blocking(path);
1331		- btrfs_set_lock_blocking_rw(eb, BTRFS_READ_LOCK);
	1285	+ btrfs_set_lock_blocking_read(eb);
1332	1286
1333	1287	if (tm->op == MOD_LOG_KEY_REMOVE_WHILE_FREEING) {
1334	1288	BUG_ON(tm->slot != 0);
..	..	@@ -1352,7 +1306,6 @@
1352	1306	}
1353	1307	}
1354	1308
1355		- btrfs_clear_path_blocking(path, NULL, BTRFS_READ_LOCK);
1356	1309	btrfs_tree_read_unlock_blocking(eb);
1357	1310	free_extent_buffer(eb);
1358	1311
..	..	@@ -1445,7 +1398,7 @@
1445	1398	free_extent_buffer(eb_root);
1446	1399	eb = alloc_dummy_extent_buffer(fs_info, logical);
1447	1400	} else {
1448		- btrfs_set_lock_blocking_rw(eb_root, BTRFS_READ_LOCK);
	1401	+ btrfs_set_lock_blocking_read(eb_root);
1449	1402	eb = btrfs_clone_extent_buffer(eb_root);
1450	1403	btrfs_tree_read_unlock_blocking(eb_root);
1451	1404	free_extent_buffer(eb_root);
..	..	@@ -1507,7 +1460,7 @@
1507	1460	*
1508	1461	* What is forced COW:
1509	1462	* when we create snapshot during committing the transaction,
1510		- * after we've finished coping src root, we must COW the shared
	1463	+ * after we've finished copying src root, we must COW the shared
1511	1464	* block to ensure the metadata consistency.
1512	1465	*/
1513	1466	if (btrfs_header_generation(buf) == trans->transid &&
..	..	@@ -1527,11 +1480,16 @@
1527	1480	noinline int btrfs_cow_block(struct btrfs_trans_handle *trans,
1528	1481	struct btrfs_root root, struct extent_buffer buf,
1529	1482	struct extent_buffer *parent, int parent_slot,
1530		- struct extent_buffer **cow_ret)
	1483	+ struct extent_buffer **cow_ret,
	1484	+ enum btrfs_lock_nesting nest)
1531	1485	{
1532	1486	struct btrfs_fs_info *fs_info = root->fs_info;
1533	1487	u64 search_start;
1534	1488	int ret;
	1489	+
	1490	+ if (test_bit(BTRFS_ROOT_DELETING, &root->state))
	1491	+ btrfs_err(fs_info,
	1492	+ "COW'ing blocks on a fs root that's being dropped");
1535	1493
1536	1494	if (trans->transaction != fs_info->running_transaction)
1537	1495	WARN(1, KERN_CRIT "trans %llu running %llu\n",
..	..	@@ -1551,11 +1509,18 @@
1551	1509	search_start = buf->start & ~((u64)SZ_1G - 1);
1552	1510
1553	1511	if (parent)
1554		- btrfs_set_lock_blocking(parent);
1555		- btrfs_set_lock_blocking(buf);
	1512	+ btrfs_set_lock_blocking_write(parent);
	1513	+ btrfs_set_lock_blocking_write(buf);
1556	1514
	1515	+ /*
	1516	+ * Before CoWing this block for later modification, check if it's
	1517	+ * the subtree root and do the delayed subtree trace if needed.
	1518	+ *
	1519	+ * Also We don't care about the error, as it's handled internally.
	1520	+ */
	1521	+ btrfs_qgroup_trace_subtree_after_cow(trans, root, buf);
1557	1522	ret = __btrfs_cow_block(trans, root, buf, parent,
1558		- parent_slot, cow_ret, search_start, 0);
	1523	+ parent_slot, cow_ret, search_start, 0, nest);
1559	1524
1560	1525	trace_btrfs_cow_block(root, buf, *cow_ret);
1561	1526
..	..	@@ -1575,6 +1540,22 @@
1575	1540	return 0;
1576	1541	}
1577	1542
	1543	+#ifdef __LITTLE_ENDIAN
	1544	+
	1545	+/*
	1546	+ * Compare two keys, on little-endian the disk order is same as CPU order and
	1547	+ * we can avoid the conversion.
	1548	+ */
	1549	+static int comp_keys(const struct btrfs_disk_key *disk_key,
	1550	+ const struct btrfs_key *k2)
	1551	+{
	1552	+ const struct btrfs_key k1 = (const struct btrfs_key )disk_key;
	1553	+
	1554	+ return btrfs_comp_cpu_keys(k1, k2);
	1555	+}
	1556	+
	1557	+#else
	1558	+
1578	1559	/*
1579	1560	* compare two keys in a memcmp fashion
1580	1561	*/
..	..	@@ -1587,11 +1568,12 @@
1587	1568
1588	1569	return btrfs_comp_cpu_keys(&k1, k2);
1589	1570	}
	1571	+#endif
1590	1572
1591	1573	/*
1592	1574	* same as comp_keys only with two btrfs_key's
1593	1575	*/
1594		-int btrfs_comp_cpu_keys(const struct btrfs_key k1, const struct btrfs_key k2)
	1576	+int __pure btrfs_comp_cpu_keys(const struct btrfs_key k1, const struct btrfs_key k2)
1595	1577	{
1596	1578	if (k1->objectid > k2->objectid)
1597	1579	return 1;
..	..	@@ -1647,7 +1629,7 @@
1647	1629	if (parent_nritems <= 1)
1648	1630	return 0;
1649	1631
1650		- btrfs_set_lock_blocking(parent);
	1632	+ btrfs_set_lock_blocking_write(parent);
1651	1633
1652	1634	for (i = start_slot; i <= end_slot; i++) {
1653	1635	struct btrfs_key first_key;
..	..	@@ -1706,11 +1688,12 @@
1706	1688	search_start = last_block;
1707	1689
1708	1690	btrfs_tree_lock(cur);
1709		- btrfs_set_lock_blocking(cur);
	1691	+ btrfs_set_lock_blocking_write(cur);
1710	1692	err = __btrfs_cow_block(trans, root, cur, parent, i,
1711	1693	&cur, search_start,
1712	1694	min(16 * blocksize,
1713		- (end_slot - i) * blocksize));
	1695	+ (end_slot - i) * blocksize),
	1696	+ BTRFS_NESTING_COW);
1714	1697	if (err) {
1715	1698	btrfs_tree_unlock(cur);
1716	1699	free_extent_buffer(cur);
..	..	@@ -1742,15 +1725,8 @@
1742	1725	{
1743	1726	int low = 0;
1744	1727	int high = max;
1745		- int mid;
1746	1728	int ret;
1747		- struct btrfs_disk_key *tmp = NULL;
1748		- struct btrfs_disk_key unaligned;
1749		- unsigned long offset;
1750		- char *kaddr = NULL;
1751		- unsigned long map_start = 0;
1752		- unsigned long map_len = 0;
1753		- int err;
	1729	+ const int key_size = sizeof(struct btrfs_disk_key);
1754	1730
1755	1731	if (low > high) {
1756	1732	btrfs_err(eb->fs_info,
..	..	@@ -1761,32 +1737,26 @@
1761	1737	}
1762	1738
1763	1739	while (low < high) {
	1740	+ unsigned long oip;
	1741	+ unsigned long offset;
	1742	+ struct btrfs_disk_key *tmp;
	1743	+ struct btrfs_disk_key unaligned;
	1744	+ int mid;
	1745	+
1764	1746	mid = (low + high) / 2;
1765	1747	offset = p + mid * item_size;
	1748	+ oip = offset_in_page(offset);
1766	1749
1767		- if (!kaddr \|\| offset < map_start \|\|
1768		- (offset + sizeof(struct btrfs_disk_key)) >
1769		- map_start + map_len) {
	1750	+ if (oip + key_size <= PAGE_SIZE) {
	1751	+ const unsigned long idx = offset >> PAGE_SHIFT;
	1752	+ char *kaddr = page_address(eb->pages[idx]);
1770	1753
1771		- err = map_private_extent_buffer(eb, offset,
1772		- sizeof(struct btrfs_disk_key),
1773		- &kaddr, &map_start, &map_len);
1774		-
1775		- if (!err) {
1776		- tmp = (struct btrfs_disk_key *)(kaddr + offset -
1777		- map_start);
1778		- } else if (err == 1) {
1779		- read_extent_buffer(eb, &unaligned,
1780		- offset, sizeof(unaligned));
1781		- tmp = &unaligned;
1782		- } else {
1783		- return err;
1784		- }
1785		-
	1754	+ tmp = (struct btrfs_disk_key *)(kaddr + oip);
1786	1755	} else {
1787		- tmp = (struct btrfs_disk_key *)(kaddr + offset -
1788		- map_start);
	1756	+ read_extent_buffer(eb, &unaligned, offset, key_size);
	1757	+ tmp = &unaligned;
1789	1758	}
	1759	+
1790	1760	ret = comp_keys(tmp, key);
1791	1761
1792	1762	if (ret < 0)
..	..	@@ -1807,9 +1777,9 @@
1807	1777	* leaves vs nodes
1808	1778	*/
1809	1779	int btrfs_bin_search(struct extent_buffer eb, const struct btrfs_key key,
1810		- int level, int *slot)
	1780	+ int *slot)
1811	1781	{
1812		- if (level == 0)
	1782	+ if (btrfs_header_level(eb) == 0)
1813	1783	return generic_bin_search(eb,
1814	1784	offsetof(struct btrfs_leaf, items),
1815	1785	sizeof(struct btrfs_item),
..	..	@@ -1842,9 +1812,8 @@
1842	1812	/* given a node and slot number, this reads the blocks it points to. The
1843	1813	* extent buffer is returned with a reference taken (but unlocked).
1844	1814	*/
1845		-static noinline struct extent_buffer *
1846		-read_node_slot(struct btrfs_fs_info fs_info, struct extent_buffer parent,
1847		- int slot)
	1815	+struct extent_buffer btrfs_read_node_slot(struct extent_buffer parent,
	1816	+ int slot)
1848	1817	{
1849	1818	int level = btrfs_header_level(parent);
1850	1819	struct extent_buffer *eb;
..	..	@@ -1856,7 +1825,7 @@
1856	1825	BUG_ON(level == 0);
1857	1826
1858	1827	btrfs_node_key_to_cpu(parent, &first_key, slot);
1859		- eb = read_tree_block(fs_info, btrfs_node_blockptr(parent, slot),
	1828	+ eb = read_tree_block(parent->fs_info, btrfs_node_blockptr(parent, slot),
1860	1829	btrfs_node_ptr_generation(parent, slot),
1861	1830	level - 1, &first_key);
1862	1831	if (!IS_ERR(eb) && !extent_buffer_uptodate(eb)) {
..	..	@@ -1887,8 +1856,7 @@
1887	1856	int orig_slot = path->slots[level];
1888	1857	u64 orig_ptr;
1889	1858
1890		- if (level == 0)
1891		- return 0;
	1859	+ ASSERT(level > 0);
1892	1860
1893	1861	mid = path->nodes[level];
1894	1862
..	..	@@ -1914,7 +1882,7 @@
1914	1882	return 0;
1915	1883
1916	1884	/* promote the child to a root */
1917		- child = read_node_slot(fs_info, mid, 0);
	1885	+ child = btrfs_read_node_slot(mid, 0);
1918	1886	if (IS_ERR(child)) {
1919	1887	ret = PTR_ERR(child);
1920	1888	btrfs_handle_fs_error(fs_info, ret, NULL);
..	..	@@ -1922,8 +1890,9 @@
1922	1890	}
1923	1891
1924	1892	btrfs_tree_lock(child);
1925		- btrfs_set_lock_blocking(child);
1926		- ret = btrfs_cow_block(trans, root, child, mid, 0, &child);
	1893	+ btrfs_set_lock_blocking_write(child);
	1894	+ ret = btrfs_cow_block(trans, root, child, mid, 0, &child,
	1895	+ BTRFS_NESTING_COW);
1927	1896	if (ret) {
1928	1897	btrfs_tree_unlock(child);
1929	1898	free_extent_buffer(child);
..	..	@@ -1939,7 +1908,7 @@
1939	1908
1940	1909	path->locks[level] = 0;
1941	1910	path->nodes[level] = NULL;
1942		- clean_tree_block(fs_info, mid);
	1911	+ btrfs_clean_tree_block(mid);
1943	1912	btrfs_tree_unlock(mid);
1944	1913	/* once for the path */
1945	1914	free_extent_buffer(mid);
..	..	@@ -1954,30 +1923,32 @@
1954	1923	BTRFS_NODEPTRS_PER_BLOCK(fs_info) / 4)
1955	1924	return 0;
1956	1925
1957		- left = read_node_slot(fs_info, parent, pslot - 1);
	1926	+ left = btrfs_read_node_slot(parent, pslot - 1);
1958	1927	if (IS_ERR(left))
1959	1928	left = NULL;
1960	1929
1961	1930	if (left) {
1962		- btrfs_tree_lock(left);
1963		- btrfs_set_lock_blocking(left);
	1931	+ __btrfs_tree_lock(left, BTRFS_NESTING_LEFT);
	1932	+ btrfs_set_lock_blocking_write(left);
1964	1933	wret = btrfs_cow_block(trans, root, left,
1965		- parent, pslot - 1, &left);
	1934	+ parent, pslot - 1, &left,
	1935	+ BTRFS_NESTING_LEFT_COW);
1966	1936	if (wret) {
1967	1937	ret = wret;
1968	1938	goto enospc;
1969	1939	}
1970	1940	}
1971	1941
1972		- right = read_node_slot(fs_info, parent, pslot + 1);
	1942	+ right = btrfs_read_node_slot(parent, pslot + 1);
1973	1943	if (IS_ERR(right))
1974	1944	right = NULL;
1975	1945
1976	1946	if (right) {
1977		- btrfs_tree_lock(right);
1978		- btrfs_set_lock_blocking(right);
	1947	+ __btrfs_tree_lock(right, BTRFS_NESTING_RIGHT);
	1948	+ btrfs_set_lock_blocking_write(right);
1979	1949	wret = btrfs_cow_block(trans, root, right,
1980		- parent, pslot + 1, &right);
	1950	+ parent, pslot + 1, &right,
	1951	+ BTRFS_NESTING_RIGHT_COW);
1981	1952	if (wret) {
1982	1953	ret = wret;
1983	1954	goto enospc;
..	..	@@ -1987,7 +1958,7 @@
1987	1958	/* first, try to make some room in the middle buffer */
1988	1959	if (left) {
1989	1960	orig_slot += btrfs_header_nritems(left);
1990		- wret = push_node_left(trans, fs_info, left, mid, 1);
	1961	+ wret = push_node_left(trans, left, mid, 1);
1991	1962	if (wret < 0)
1992	1963	ret = wret;
1993	1964	}
..	..	@@ -1996,11 +1967,11 @@
1996	1967	* then try to empty the right most buffer into the middle
1997	1968	*/
1998	1969	if (right) {
1999		- wret = push_node_left(trans, fs_info, mid, right, 1);
	1970	+ wret = push_node_left(trans, mid, right, 1);
2000	1971	if (wret < 0 && wret != -ENOSPC)
2001	1972	ret = wret;
2002	1973	if (btrfs_header_nritems(right) == 0) {
2003		- clean_tree_block(fs_info, right);
	1974	+ btrfs_clean_tree_block(right);
2004	1975	btrfs_tree_unlock(right);
2005	1976	del_ptr(root, path, level + 1, pslot + 1);
2006	1977	root_sub_used(root, right->len);
..	..	@@ -2032,20 +2003,20 @@
2032	2003	btrfs_handle_fs_error(fs_info, ret, NULL);
2033	2004	goto enospc;
2034	2005	}
2035		- wret = balance_node_right(trans, fs_info, mid, left);
	2006	+ wret = balance_node_right(trans, mid, left);
2036	2007	if (wret < 0) {
2037	2008	ret = wret;
2038	2009	goto enospc;
2039	2010	}
2040	2011	if (wret == 1) {
2041		- wret = push_node_left(trans, fs_info, left, mid, 1);
	2012	+ wret = push_node_left(trans, left, mid, 1);
2042	2013	if (wret < 0)
2043	2014	ret = wret;
2044	2015	}
2045	2016	BUG_ON(wret == 1);
2046	2017	}
2047	2018	if (btrfs_header_nritems(mid) == 0) {
2048		- clean_tree_block(fs_info, mid);
	2019	+ btrfs_clean_tree_block(mid);
2049	2020	btrfs_tree_unlock(mid);
2050	2021	del_ptr(root, path, level + 1, pslot);
2051	2022	root_sub_used(root, mid->len);
..	..	@@ -2066,7 +2037,7 @@
2066	2037	/* update the path */
2067	2038	if (left) {
2068	2039	if (btrfs_header_nritems(left) > orig_slot) {
2069		- extent_buffer_get(left);
	2040	+ atomic_inc(&left->refs);
2070	2041	/* left was locked after cow */
2071	2042	path->nodes[level] = left;
2072	2043	path->slots[level + 1] -= 1;
..	..	@@ -2129,7 +2100,7 @@
2129	2100	if (!parent)
2130	2101	return 1;
2131	2102
2132		- left = read_node_slot(fs_info, parent, pslot - 1);
	2103	+ left = btrfs_read_node_slot(parent, pslot - 1);
2133	2104	if (IS_ERR(left))
2134	2105	left = NULL;
2135	2106
..	..	@@ -2137,20 +2108,20 @@
2137	2108	if (left) {
2138	2109	u32 left_nr;
2139	2110
2140		- btrfs_tree_lock(left);
2141		- btrfs_set_lock_blocking(left);
	2111	+ __btrfs_tree_lock(left, BTRFS_NESTING_LEFT);
	2112	+ btrfs_set_lock_blocking_write(left);
2142	2113
2143	2114	left_nr = btrfs_header_nritems(left);
2144	2115	if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 1) {
2145	2116	wret = 1;
2146	2117	} else {
2147	2118	ret = btrfs_cow_block(trans, root, left, parent,
2148		- pslot - 1, &left);
	2119	+ pslot - 1, &left,
	2120	+ BTRFS_NESTING_LEFT_COW);
2149	2121	if (ret)
2150	2122	wret = 1;
2151	2123	else {
2152		- wret = push_node_left(trans, fs_info,
2153		- left, mid, 0);
	2124	+ wret = push_node_left(trans, left, mid, 0);
2154	2125	}
2155	2126	}
2156	2127	if (wret < 0)
..	..	@@ -2182,7 +2153,7 @@
2182	2153	btrfs_tree_unlock(left);
2183	2154	free_extent_buffer(left);
2184	2155	}
2185		- right = read_node_slot(fs_info, parent, pslot + 1);
	2156	+ right = btrfs_read_node_slot(parent, pslot + 1);
2186	2157	if (IS_ERR(right))
2187	2158	right = NULL;
2188	2159
..	..	@@ -2192,8 +2163,8 @@
2192	2163	if (right) {
2193	2164	u32 right_nr;
2194	2165
2195		- btrfs_tree_lock(right);
2196		- btrfs_set_lock_blocking(right);
	2166	+ __btrfs_tree_lock(right, BTRFS_NESTING_RIGHT);
	2167	+ btrfs_set_lock_blocking_write(right);
2197	2168
2198	2169	right_nr = btrfs_header_nritems(right);
2199	2170	if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 1) {
..	..	@@ -2201,12 +2172,11 @@
2201	2172	} else {
2202	2173	ret = btrfs_cow_block(trans, root, right,
2203	2174	parent, pslot + 1,
2204		- &right);
	2175	+ &right, BTRFS_NESTING_RIGHT_COW);
2205	2176	if (ret)
2206	2177	wret = 1;
2207	2178	else {
2208		- wret = balance_node_right(trans, fs_info,
2209		- right, mid);
	2179	+ wret = balance_node_right(trans, right, mid);
2210	2180	}
2211	2181	}
2212	2182	if (wret < 0)
..	..	@@ -2411,32 +2381,6 @@
2411	2381	}
2412	2382
2413	2383	/*
2414		- * This releases any locks held in the path starting at level and
2415		- * going all the way up to the root.
2416		- *
2417		- * btrfs_search_slot will keep the lock held on higher nodes in a few
2418		- * corner cases, such as COW of the block at slot zero in the node. This
2419		- * ignores those rules, and it should only be called when there are no
2420		- * more updates to be done higher up in the tree.
2421		- */
2422		-noinline void btrfs_unlock_up_safe(struct btrfs_path *path, int level)
2423		-{
2424		- int i;
2425		-
2426		- if (path->keep_locks)
2427		- return;
2428		-
2429		- for (i = level; i < BTRFS_MAX_LEVEL; i++) {
2430		- if (!path->nodes[i])
2431		- continue;
2432		- if (!path->locks[i])
2433		- continue;
2434		- btrfs_tree_unlock_rw(path->nodes[i], path->locks[i]);
2435		- path->locks[i] = 0;
2436		- }
2437		-}
2438		-
2439		-/*
2440	2384	* helper function for btrfs_search_slot. The goal is to find a block
2441	2385	* in cache without setting the path to blocking. If we find the block
2442	2386	* we return zero and the path is unchanged.
..	..	@@ -2452,16 +2396,15 @@
2452	2396	struct btrfs_fs_info *fs_info = root->fs_info;
2453	2397	u64 blocknr;
2454	2398	u64 gen;
2455		- struct extent_buffer b = eb_ret;
2456	2399	struct extent_buffer *tmp;
2457	2400	struct btrfs_key first_key;
2458	2401	int ret;
2459	2402	int parent_level;
2460	2403
2461		- blocknr = btrfs_node_blockptr(b, slot);
2462		- gen = btrfs_node_ptr_generation(b, slot);
2463		- parent_level = btrfs_header_level(b);
2464		- btrfs_node_key_to_cpu(b, &first_key, slot);
	2404	+ blocknr = btrfs_node_blockptr(*eb_ret, slot);
	2405	+ gen = btrfs_node_ptr_generation(*eb_ret, slot);
	2406	+ parent_level = btrfs_header_level(*eb_ret);
	2407	+ btrfs_node_key_to_cpu(*eb_ret, &first_key, slot);
2465	2408
2466	2409	tmp = find_extent_buffer(fs_info, blocknr);
2467	2410	if (tmp) {
..	..	@@ -2472,7 +2415,7 @@
2472	2415	* being cached, read from scrub, or have multiple
2473	2416	* parents (shared tree blocks).
2474	2417	*/
2475		- if (btrfs_verify_level_key(fs_info, tmp,
	2418	+ if (btrfs_verify_level_key(tmp,
2476	2419	parent_level - 1, &first_key, gen)) {
2477	2420	free_extent_buffer(tmp);
2478	2421	return -EUCLEAN;
..	..	@@ -2565,7 +2508,6 @@
2565	2508	btrfs_set_path_blocking(p);
2566	2509	reada_for_balance(fs_info, p, level);
2567	2510	sret = split_node(trans, root, p, level);
2568		- btrfs_clear_path_blocking(p, NULL, 0);
2569	2511
2570	2512	BUG_ON(sret > 0);
2571	2513	if (sret) {
..	..	@@ -2586,7 +2528,6 @@
2586	2528	btrfs_set_path_blocking(p);
2587	2529	reada_for_balance(fs_info, p, level);
2588	2530	sret = balance_level(trans, root, p, level);
2589		- btrfs_clear_path_blocking(p, NULL, 0);
2590	2531
2591	2532	if (sret) {
2592	2533	ret = sret;
..	..	@@ -2605,40 +2546,6 @@
2605	2546	ret = -EAGAIN;
2606	2547	done:
2607	2548	return ret;
2608		-}
2609		-
2610		-static void key_search_validate(struct extent_buffer *b,
2611		- const struct btrfs_key *key,
2612		- int level)
2613		-{
2614		-#ifdef CONFIG_BTRFS_ASSERT
2615		- struct btrfs_disk_key disk_key;
2616		-
2617		- btrfs_cpu_key_to_disk(&disk_key, key);
2618		-
2619		- if (level == 0)
2620		- ASSERT(!memcmp_extent_buffer(b, &disk_key,
2621		- offsetof(struct btrfs_leaf, items[0].key),
2622		- sizeof(disk_key)));
2623		- else
2624		- ASSERT(!memcmp_extent_buffer(b, &disk_key,
2625		- offsetof(struct btrfs_node, ptrs[0].key),
2626		- sizeof(disk_key)));
2627		-#endif
2628		-}
2629		-
2630		-static int key_search(struct extent_buffer b, const struct btrfs_key key,
2631		- int level, int prev_cmp, int slot)
2632		-{
2633		- if (*prev_cmp != 0) {
2634		- *prev_cmp = btrfs_bin_search(b, key, level, slot);
2635		- return *prev_cmp;
2636		- }
2637		-
2638		- key_search_validate(b, key, level);
2639		- *slot = 0;
2640		-
2641		- return 0;
2642	2549	}
2643	2550
2644	2551	int btrfs_find_item(struct btrfs_root fs_root, struct btrfs_path path,
..	..	@@ -2682,11 +2589,8 @@
2682	2589	{
2683	2590	struct btrfs_fs_info *fs_info = root->fs_info;
2684	2591	struct extent_buffer *b;
2685		- int root_lock;
	2592	+ int root_lock = 0;
2686	2593	int level = 0;
2687		-
2688		- /* We try very hard to do read locks on the root */
2689		- root_lock = BTRFS_READ_LOCK;
2690	2594
2691	2595	if (p->search_commit_root) {
2692	2596	/*
..	..	@@ -2707,7 +2611,7 @@
2707	2611
2708	2612	} else {
2709	2613	b = root->commit_root;
2710		- extent_buffer_get(b);
	2614	+ atomic_inc(&b->refs);
2711	2615	}
2712	2616	level = btrfs_header_level(b);
2713	2617	/*
..	..	@@ -2725,6 +2629,9 @@
2725	2629	goto out;
2726	2630	}
2727	2631
	2632	+ /* We try very hard to do read locks on the root */
	2633	+ root_lock = BTRFS_READ_LOCK;
	2634	+
2728	2635	/*
2729	2636	* If the level is set to maximum, we can skip trying to get the read
2730	2637	* lock.
..	..	@@ -2734,7 +2641,7 @@
2734	2641	* We don't know the level of the root node until we actually
2735	2642	* have it read locked
2736	2643	*/
2737		- b = btrfs_read_lock_root_node(root);
	2644	+ b = __btrfs_read_lock_root_node(root, p->recurse);
2738	2645	level = btrfs_header_level(b);
2739	2646	if (level > write_lock_level)
2740	2647	goto out;
..	..	@@ -2751,6 +2658,17 @@
2751	2658	level = btrfs_header_level(b);
2752	2659
2753	2660	out:
	2661	+ /*
	2662	+ * The root may have failed to write out at some point, and thus is no
	2663	+ * longer valid, return an error in this case.
	2664	+ */
	2665	+ if (!extent_buffer_uptodate(b)) {
	2666	+ if (root_lock)
	2667	+ btrfs_tree_unlock_rw(b, root_lock);
	2668	+ free_extent_buffer(b);
	2669	+ return ERR_PTR(-EIO);
	2670	+ }
	2671	+
2754	2672	p->nodes[level] = b;
2755	2673	if (!p->skip_locking)
2756	2674	p->locks[level] = root_lock;
..	..	@@ -2790,7 +2708,6 @@
2790	2708	const struct btrfs_key key, struct btrfs_path p,
2791	2709	int ins_len, int cow)
2792	2710	{
2793		- struct btrfs_fs_info *fs_info = root->fs_info;
2794	2711	struct extent_buffer *b;
2795	2712	int slot;
2796	2713	int ret;
..	..	@@ -2841,12 +2758,10 @@
2841	2758	}
2842	2759
2843	2760	while (b) {
	2761	+ int dec = 0;
	2762	+
2844	2763	level = btrfs_header_level(b);
2845	2764
2846		- /*
2847		- * setup the path here so we can release it under lock
2848		- * contention with the cow code
2849		- */
2850	2765	if (cow) {
2851	2766	bool last_level = (level == (BTRFS_MAX_LEVEL - 1));
2852	2767
..	..	@@ -2876,11 +2791,13 @@
2876	2791	btrfs_set_path_blocking(p);
2877	2792	if (last_level)
2878	2793	err = btrfs_cow_block(trans, root, b, NULL, 0,
2879		- &b);
	2794	+ &b,
	2795	+ BTRFS_NESTING_COW);
2880	2796	else
2881	2797	err = btrfs_cow_block(trans, root, b,
2882	2798	p->nodes[level + 1],
2883		- p->slots[level + 1], &b);
	2799	+ p->slots[level + 1], &b,
	2800	+ BTRFS_NESTING_COW);
2884	2801	if (err) {
2885	2802	ret = err;
2886	2803	goto done;
..	..	@@ -2888,7 +2805,10 @@
2888	2805	}
2889	2806	cow_done:
2890	2807	p->nodes[level] = b;
2891		- btrfs_clear_path_blocking(p, NULL, 0);
	2808	+ /*
	2809	+ * Leave path with blocking locks to avoid massive
	2810	+ * lock context switch, this is made on purpose.
	2811	+ */
2892	2812
2893	2813	/*
2894	2814	* we have a lock on b and as long as we aren't changing
..	..	@@ -2910,86 +2830,28 @@
2910	2830	}
2911	2831	}
2912	2832
2913		- ret = key_search(b, key, level, &prev_cmp, &slot);
2914		- if (ret < 0)
2915		- goto done;
2916		-
2917		- if (level != 0) {
2918		- int dec = 0;
2919		- if (ret && slot > 0) {
2920		- dec = 1;
2921		- slot -= 1;
2922		- }
2923		- p->slots[level] = slot;
2924		- err = setup_nodes_for_search(trans, root, p, b, level,
2925		- ins_len, &write_lock_level);
2926		- if (err == -EAGAIN)
2927		- goto again;
2928		- if (err) {
2929		- ret = err;
2930		- goto done;
2931		- }
2932		- b = p->nodes[level];
2933		- slot = p->slots[level];
2934		-
2935		- /*
2936		- * slot 0 is special, if we change the key
2937		- * we have to update the parent pointer
2938		- * which means we must have a write lock
2939		- * on the parent
2940		- */
2941		- if (slot == 0 && ins_len &&
2942		- write_lock_level < level + 1) {
2943		- write_lock_level = level + 1;
2944		- btrfs_release_path(p);
2945		- goto again;
2946		- }
2947		-
2948		- unlock_up(p, level, lowest_unlock,
2949		- min_write_lock_level, &write_lock_level);
2950		-
2951		- if (level == lowest_level) {
2952		- if (dec)
2953		- p->slots[level]++;
2954		- goto done;
2955		- }
2956		-
2957		- err = read_block_for_search(root, p, &b, level,
2958		- slot, key);
2959		- if (err == -EAGAIN)
2960		- goto again;
2961		- if (err) {
2962		- ret = err;
2963		- goto done;
2964		- }
2965		-
2966		- if (!p->skip_locking) {
2967		- level = btrfs_header_level(b);
2968		- if (level <= write_lock_level) {
2969		- err = btrfs_try_tree_write_lock(b);
2970		- if (!err) {
2971		- btrfs_set_path_blocking(p);
2972		- btrfs_tree_lock(b);
2973		- btrfs_clear_path_blocking(p, b,
2974		- BTRFS_WRITE_LOCK);
2975		- }
2976		- p->locks[level] = BTRFS_WRITE_LOCK;
2977		- } else {
2978		- err = btrfs_tree_read_lock_atomic(b);
2979		- if (!err) {
2980		- btrfs_set_path_blocking(p);
2981		- btrfs_tree_read_lock(b);
2982		- btrfs_clear_path_blocking(p, b,
2983		- BTRFS_READ_LOCK);
2984		- }
2985		- p->locks[level] = BTRFS_READ_LOCK;
2986		- }
2987		- p->nodes[level] = b;
2988		- }
	2833	+ /*
	2834	+ * If btrfs_bin_search returns an exact match (prev_cmp == 0)
	2835	+ * we can safely assume the target key will always be in slot 0
	2836	+ * on lower levels due to the invariants BTRFS' btree provides,
	2837	+ * namely that a btrfs_key_ptr entry always points to the
	2838	+ * lowest key in the child node, thus we can skip searching
	2839	+ * lower levels
	2840	+ */
	2841	+ if (prev_cmp == 0) {
	2842	+ slot = 0;
	2843	+ ret = 0;
2989	2844	} else {
	2845	+ ret = btrfs_bin_search(b, key, &slot);
	2846	+ prev_cmp = ret;
	2847	+ if (ret < 0)
	2848	+ goto done;
	2849	+ }
	2850	+
	2851	+ if (level == 0) {
2990	2852	p->slots[level] = slot;
2991	2853	if (ins_len > 0 &&
2992		- btrfs_leaf_free_space(fs_info, b) < ins_len) {
	2854	+ btrfs_leaf_free_space(b) < ins_len) {
2993	2855	if (write_lock_level < 1) {
2994	2856	write_lock_level = 1;
2995	2857	btrfs_release_path(p);
..	..	@@ -2999,7 +2861,6 @@
2999	2861	btrfs_set_path_blocking(p);
3000	2862	err = split_leaf(trans, root, key,
3001	2863	p, ins_len, ret == 0);
3002		- btrfs_clear_path_blocking(p, NULL, 0);
3003	2864
3004	2865	BUG_ON(err > 0);
3005	2866	if (err) {
..	..	@@ -3009,8 +2870,70 @@
3009	2870	}
3010	2871	if (!p->search_for_split)
3011	2872	unlock_up(p, level, lowest_unlock,
3012		- min_write_lock_level, &write_lock_level);
	2873	+ min_write_lock_level, NULL);
3013	2874	goto done;
	2875	+ }
	2876	+ if (ret && slot > 0) {
	2877	+ dec = 1;
	2878	+ slot--;
	2879	+ }
	2880	+ p->slots[level] = slot;
	2881	+ err = setup_nodes_for_search(trans, root, p, b, level, ins_len,
	2882	+ &write_lock_level);
	2883	+ if (err == -EAGAIN)
	2884	+ goto again;
	2885	+ if (err) {
	2886	+ ret = err;
	2887	+ goto done;
	2888	+ }
	2889	+ b = p->nodes[level];
	2890	+ slot = p->slots[level];
	2891	+
	2892	+ /*
	2893	+ * Slot 0 is special, if we change the key we have to update
	2894	+ * the parent pointer which means we must have a write lock on
	2895	+ * the parent
	2896	+ */
	2897	+ if (slot == 0 && ins_len && write_lock_level < level + 1) {
	2898	+ write_lock_level = level + 1;
	2899	+ btrfs_release_path(p);
	2900	+ goto again;
	2901	+ }
	2902	+
	2903	+ unlock_up(p, level, lowest_unlock, min_write_lock_level,
	2904	+ &write_lock_level);
	2905	+
	2906	+ if (level == lowest_level) {
	2907	+ if (dec)
	2908	+ p->slots[level]++;
	2909	+ goto done;
	2910	+ }
	2911	+
	2912	+ err = read_block_for_search(root, p, &b, level, slot, key);
	2913	+ if (err == -EAGAIN)
	2914	+ goto again;
	2915	+ if (err) {
	2916	+ ret = err;
	2917	+ goto done;
	2918	+ }
	2919	+
	2920	+ if (!p->skip_locking) {
	2921	+ level = btrfs_header_level(b);
	2922	+ if (level <= write_lock_level) {
	2923	+ if (!btrfs_try_tree_write_lock(b)) {
	2924	+ btrfs_set_path_blocking(p);
	2925	+ btrfs_tree_lock(b);
	2926	+ }
	2927	+ p->locks[level] = BTRFS_WRITE_LOCK;
	2928	+ } else {
	2929	+ if (!btrfs_tree_read_lock_atomic(b)) {
	2930	+ btrfs_set_path_blocking(p);
	2931	+ __btrfs_tree_read_lock(b, BTRFS_NESTING_NORMAL,
	2932	+ p->recurse);
	2933	+ }
	2934	+ p->locks[level] = BTRFS_READ_LOCK;
	2935	+ }
	2936	+ p->nodes[level] = b;
3014	2937	}
3015	2938	}
3016	2939	ret = 1;
..	..	@@ -3048,7 +2971,6 @@
3048	2971	int level;
3049	2972	int lowest_unlock = 1;
3050	2973	u8 lowest_level = 0;
3051		- int prev_cmp = -1;
3052	2974
3053	2975	lowest_level = p->lowest_level;
3054	2976	WARN_ON(p->nodes[0] != NULL);
..	..	@@ -3068,9 +2990,10 @@
3068	2990	p->locks[level] = BTRFS_READ_LOCK;
3069	2991
3070	2992	while (b) {
	2993	+ int dec = 0;
	2994	+
3071	2995	level = btrfs_header_level(b);
3072	2996	p->nodes[level] = b;
3073		- btrfs_clear_path_blocking(p, NULL, 0);
3074	2997
3075	2998	/*
3076	2999	* we have a lock on b and as long as we aren't changing
..	..	@@ -3080,57 +3003,49 @@
3080	3003	*/
3081	3004	btrfs_unlock_up_safe(p, level + 1);
3082	3005
3083		- /*
3084		- * Since we can unwind ebs we want to do a real search every
3085		- * time.
3086		- */
3087		- prev_cmp = -1;
3088		- ret = key_search(b, key, level, &prev_cmp, &slot);
	3006	+ ret = btrfs_bin_search(b, key, &slot);
	3007	+ if (ret < 0)
	3008	+ goto done;
3089	3009
3090		- if (level != 0) {
3091		- int dec = 0;
3092		- if (ret && slot > 0) {
3093		- dec = 1;
3094		- slot -= 1;
3095		- }
3096		- p->slots[level] = slot;
3097		- unlock_up(p, level, lowest_unlock, 0, NULL);
3098		-
3099		- if (level == lowest_level) {
3100		- if (dec)
3101		- p->slots[level]++;
3102		- goto done;
3103		- }
3104		-
3105		- err = read_block_for_search(root, p, &b, level,
3106		- slot, key);
3107		- if (err == -EAGAIN)
3108		- goto again;
3109		- if (err) {
3110		- ret = err;
3111		- goto done;
3112		- }
3113		-
3114		- level = btrfs_header_level(b);
3115		- err = btrfs_tree_read_lock_atomic(b);
3116		- if (!err) {
3117		- btrfs_set_path_blocking(p);
3118		- btrfs_tree_read_lock(b);
3119		- btrfs_clear_path_blocking(p, b,
3120		- BTRFS_READ_LOCK);
3121		- }
3122		- b = tree_mod_log_rewind(fs_info, p, b, time_seq);
3123		- if (!b) {
3124		- ret = -ENOMEM;
3125		- goto done;
3126		- }
3127		- p->locks[level] = BTRFS_READ_LOCK;
3128		- p->nodes[level] = b;
3129		- } else {
	3010	+ if (level == 0) {
3130	3011	p->slots[level] = slot;
3131	3012	unlock_up(p, level, lowest_unlock, 0, NULL);
3132	3013	goto done;
3133	3014	}
	3015	+
	3016	+ if (ret && slot > 0) {
	3017	+ dec = 1;
	3018	+ slot--;
	3019	+ }
	3020	+ p->slots[level] = slot;
	3021	+ unlock_up(p, level, lowest_unlock, 0, NULL);
	3022	+
	3023	+ if (level == lowest_level) {
	3024	+ if (dec)
	3025	+ p->slots[level]++;
	3026	+ goto done;
	3027	+ }
	3028	+
	3029	+ err = read_block_for_search(root, p, &b, level, slot, key);
	3030	+ if (err == -EAGAIN)
	3031	+ goto again;
	3032	+ if (err) {
	3033	+ ret = err;
	3034	+ goto done;
	3035	+ }
	3036	+
	3037	+ level = btrfs_header_level(b);
	3038	+ if (!btrfs_tree_read_lock_atomic(b)) {
	3039	+ btrfs_set_path_blocking(p);
	3040	+ btrfs_tree_read_lock(b);
	3041	+ }
	3042	+ b = tree_mod_log_rewind(fs_info, p, b, time_seq);
	3043	+ if (!b) {
	3044	+ ret = -ENOMEM;
	3045	+ goto done;
	3046	+ }
	3047	+ p->locks[level] = BTRFS_READ_LOCK;
	3048	+ p->nodes[level] = b;
3134	3049	}
3135	3050	ret = 1;
3136	3051	done:
..	..	@@ -3268,11 +3183,31 @@
3268	3183	slot = path->slots[0];
3269	3184	if (slot > 0) {
3270	3185	btrfs_item_key(eb, &disk_key, slot - 1);
3271		- BUG_ON(comp_keys(&disk_key, new_key) >= 0);
	3186	+ if (unlikely(comp_keys(&disk_key, new_key) >= 0)) {
	3187	+ btrfs_crit(fs_info,
	3188	+ "slot %u key (%llu %u %llu) new key (%llu %u %llu)",
	3189	+ slot, btrfs_disk_key_objectid(&disk_key),
	3190	+ btrfs_disk_key_type(&disk_key),
	3191	+ btrfs_disk_key_offset(&disk_key),
	3192	+ new_key->objectid, new_key->type,
	3193	+ new_key->offset);
	3194	+ btrfs_print_leaf(eb);
	3195	+ BUG();
	3196	+ }
3272	3197	}
3273	3198	if (slot < btrfs_header_nritems(eb) - 1) {
3274	3199	btrfs_item_key(eb, &disk_key, slot + 1);
3275		- BUG_ON(comp_keys(&disk_key, new_key) <= 0);
	3200	+ if (unlikely(comp_keys(&disk_key, new_key) <= 0)) {
	3201	+ btrfs_crit(fs_info,
	3202	+ "slot %u key (%llu %u %llu) new key (%llu %u %llu)",
	3203	+ slot, btrfs_disk_key_objectid(&disk_key),
	3204	+ btrfs_disk_key_type(&disk_key),
	3205	+ btrfs_disk_key_offset(&disk_key),
	3206	+ new_key->objectid, new_key->type,
	3207	+ new_key->offset);
	3208	+ btrfs_print_leaf(eb);
	3209	+ BUG();
	3210	+ }
3276	3211	}
3277	3212
3278	3213	btrfs_cpu_key_to_disk(&disk_key, new_key);
..	..	@@ -3283,6 +3218,58 @@
3283	3218	}
3284	3219
3285	3220	/*
	3221	+ * Check key order of two sibling extent buffers.
	3222	+ *
	3223	+ * Return true if something is wrong.
	3224	+ * Return false if everything is fine.
	3225	+ *
	3226	+ * Tree-checker only works inside one tree block, thus the following
	3227	+ * corruption can not be detected by tree-checker:
	3228	+ *
	3229	+ * Leaf @left \| Leaf @right
	3230	+ * --------------------------------------------------------------
	3231	+ * \| 1 \| 2 \| 3 \| 4 \| 5 \| f6 \| \| 7 \| 8 \|
	3232	+ *
	3233	+ * Key f6 in leaf @left itself is valid, but not valid when the next
	3234	+ * key in leaf @right is 7.
	3235	+ * This can only be checked at tree block merge time.
	3236	+ * And since tree checker has ensured all key order in each tree block
	3237	+ * is correct, we only need to bother the last key of @left and the first
	3238	+ * key of @right.
	3239	+ */
	3240	+static bool check_sibling_keys(struct extent_buffer *left,
	3241	+ struct extent_buffer *right)
	3242	+{
	3243	+ struct btrfs_key left_last;
	3244	+ struct btrfs_key right_first;
	3245	+ int level = btrfs_header_level(left);
	3246	+ int nr_left = btrfs_header_nritems(left);
	3247	+ int nr_right = btrfs_header_nritems(right);
	3248	+
	3249	+ /* No key to check in one of the tree blocks */
	3250	+ if (!nr_left \|\| !nr_right)
	3251	+ return false;
	3252	+
	3253	+ if (level) {
	3254	+ btrfs_node_key_to_cpu(left, &left_last, nr_left - 1);
	3255	+ btrfs_node_key_to_cpu(right, &right_first, 0);
	3256	+ } else {
	3257	+ btrfs_item_key_to_cpu(left, &left_last, nr_left - 1);
	3258	+ btrfs_item_key_to_cpu(right, &right_first, 0);
	3259	+ }
	3260	+
	3261	+ if (btrfs_comp_cpu_keys(&left_last, &right_first) >= 0) {
	3262	+ btrfs_crit(left->fs_info,
	3263	+"bad key order, sibling blocks, left last (%llu %u %llu) right first (%llu %u %llu)",
	3264	+ left_last.objectid, left_last.type,
	3265	+ left_last.offset, right_first.objectid,
	3266	+ right_first.type, right_first.offset);
	3267	+ return true;
	3268	+ }
	3269	+ return false;
	3270	+}
	3271	+
	3272	+/*
3286	3273	* try to push data from one node into the next node left in the
3287	3274	* tree.
3288	3275	*
..	..	@@ -3290,10 +3277,10 @@
3290	3277	* error, and > 0 if there was no room in the left hand block.
3291	3278	*/
3292	3279	static int push_node_left(struct btrfs_trans_handle *trans,
3293		- struct btrfs_fs_info *fs_info,
3294	3280	struct extent_buffer *dst,
3295	3281	struct extent_buffer *src, int empty)
3296	3282	{
	3283	+ struct btrfs_fs_info *fs_info = trans->fs_info;
3297	3284	int push_items = 0;
3298	3285	int src_nritems;
3299	3286	int dst_nritems;
..	..	@@ -3326,8 +3313,13 @@
3326	3313	} else
3327	3314	push_items = min(src_nritems - 8, push_items);
3328	3315
3329		- ret = tree_mod_log_eb_copy(fs_info, dst, src, dst_nritems, 0,
3330		- push_items);
	3316	+ /* dst is the left eb, src is the middle eb */
	3317	+ if (check_sibling_keys(dst, src)) {
	3318	+ ret = -EUCLEAN;
	3319	+ btrfs_abort_transaction(trans, ret);
	3320	+ return ret;
	3321	+ }
	3322	+ ret = tree_mod_log_eb_copy(dst, src, dst_nritems, 0, push_items);
3331	3323	if (ret) {
3332	3324	btrfs_abort_transaction(trans, ret);
3333	3325	return ret;
..	..	@@ -3365,10 +3357,10 @@
3365	3357	* this will only push up to 1/2 the contents of the left node over
3366	3358	*/
3367	3359	static int balance_node_right(struct btrfs_trans_handle *trans,
3368		- struct btrfs_fs_info *fs_info,
3369	3360	struct extent_buffer *dst,
3370	3361	struct extent_buffer *src)
3371	3362	{
	3363	+ struct btrfs_fs_info *fs_info = trans->fs_info;
3372	3364	int push_items = 0;
3373	3365	int max_push;
3374	3366	int src_nritems;
..	..	@@ -3395,6 +3387,12 @@
3395	3387	if (max_push < push_items)
3396	3388	push_items = max_push;
3397	3389
	3390	+ /* dst is the right eb, src is the middle eb */
	3391	+ if (check_sibling_keys(src, dst)) {
	3392	+ ret = -EUCLEAN;
	3393	+ btrfs_abort_transaction(trans, ret);
	3394	+ return ret;
	3395	+ }
3398	3396	ret = tree_mod_log_insert_move(dst, push_items, 0, dst_nritems);
3399	3397	BUG_ON(ret < 0);
3400	3398	memmove_extent_buffer(dst, btrfs_node_key_ptr_offset(push_items),
..	..	@@ -3402,8 +3400,8 @@
3402	3400	(dst_nritems) *
3403	3401	sizeof(struct btrfs_key_ptr));
3404	3402
3405		- ret = tree_mod_log_eb_copy(fs_info, dst, src, 0,
3406		- src_nritems - push_items, push_items);
	3403	+ ret = tree_mod_log_eb_copy(dst, src, 0, src_nritems - push_items,
	3404	+ push_items);
3407	3405	if (ret) {
3408	3406	btrfs_abort_transaction(trans, ret);
3409	3407	return ret;
..	..	@@ -3451,7 +3449,8 @@
3451	3449	btrfs_node_key(lower, &lower_key, 0);
3452	3450
3453	3451	c = alloc_tree_block_no_bg_flush(trans, root, 0, &lower_key, level,
3454		- root->node->start, 0);
	3452	+ root->node->start, 0,
	3453	+ BTRFS_NESTING_NEW_ROOT);
3455	3454	if (IS_ERR(c))
3456	3455	return PTR_ERR(c);
3457	3456
..	..	@@ -3476,7 +3475,7 @@
3476	3475	free_extent_buffer(old);
3477	3476
3478	3477	add_root_to_dirty_list(root);
3479		- extent_buffer_get(c);
	3478	+ atomic_inc(&c->refs);
3480	3479	path->nodes[level] = c;
3481	3480	path->locks[level] = BTRFS_WRITE_LOCK_BLOCKING;
3482	3481	path->slots[level] = 0;
..	..	@@ -3491,7 +3490,7 @@
3491	3490	* blocknr is the block the key points to.
3492	3491	*/
3493	3492	static void insert_ptr(struct btrfs_trans_handle *trans,
3494		- struct btrfs_fs_info fs_info, struct btrfs_path path,
	3493	+ struct btrfs_path *path,
3495	3494	struct btrfs_disk_key *key, u64 bytenr,
3496	3495	int slot, int level)
3497	3496	{
..	..	@@ -3504,7 +3503,7 @@
3504	3503	lower = path->nodes[level];
3505	3504	nritems = btrfs_header_nritems(lower);
3506	3505	BUG_ON(slot > nritems);
3507		- BUG_ON(nritems == BTRFS_NODEPTRS_PER_BLOCK(fs_info));
	3506	+ BUG_ON(nritems == BTRFS_NODEPTRS_PER_BLOCK(trans->fs_info));
3508	3507	if (slot != nritems) {
3509	3508	if (level) {
3510	3509	ret = tree_mod_log_insert_move(lower, slot + 1, slot,
..	..	@@ -3581,15 +3580,17 @@
3581	3580	btrfs_node_key(c, &disk_key, mid);
3582	3581
3583	3582	split = alloc_tree_block_no_bg_flush(trans, root, 0, &disk_key, level,
3584		- c->start, 0);
	3583	+ c->start, 0, BTRFS_NESTING_SPLIT);
3585	3584	if (IS_ERR(split))
3586	3585	return PTR_ERR(split);
3587	3586
3588	3587	root_add_used(root, fs_info->nodesize);
3589	3588	ASSERT(btrfs_header_level(c) == level);
3590	3589
3591		- ret = tree_mod_log_eb_copy(fs_info, split, c, 0, mid, c_nritems - mid);
	3590	+ ret = tree_mod_log_eb_copy(split, c, 0, mid, c_nritems - mid);
3592	3591	if (ret) {
	3592	+ btrfs_tree_unlock(split);
	3593	+ free_extent_buffer(split);
3593	3594	btrfs_abort_transaction(trans, ret);
3594	3595	return ret;
3595	3596	}
..	..	@@ -3604,7 +3605,7 @@
3604	3605	btrfs_mark_buffer_dirty(c);
3605	3606	btrfs_mark_buffer_dirty(split);
3606	3607
3607		- insert_ptr(trans, fs_info, path, &disk_key, split->start,
	3608	+ insert_ptr(trans, path, &disk_key, split->start,
3608	3609	path->slots[level + 1] + 1, level + 1);
3609	3610
3610	3611	if (path->slots[level] >= mid) {
..	..	@@ -3629,19 +3630,17 @@
3629	3630	{
3630	3631	struct btrfs_item *start_item;
3631	3632	struct btrfs_item *end_item;
3632		- struct btrfs_map_token token;
3633	3633	int data_len;
3634	3634	int nritems = btrfs_header_nritems(l);
3635	3635	int end = min(nritems, start + nr) - 1;
3636	3636
3637	3637	if (!nr)
3638	3638	return 0;
3639		- btrfs_init_map_token(&token);
3640	3639	start_item = btrfs_item_nr(start);
3641	3640	end_item = btrfs_item_nr(end);
3642		- data_len = btrfs_token_item_offset(l, start_item, &token) +
3643		- btrfs_token_item_size(l, start_item, &token);
3644		- data_len = data_len - btrfs_token_item_offset(l, end_item, &token);
	3641	+ data_len = btrfs_item_offset(l, start_item) +
	3642	+ btrfs_item_size(l, start_item);
	3643	+ data_len = data_len - btrfs_item_offset(l, end_item);
3645	3644	data_len += sizeof(struct btrfs_item) * nr;
3646	3645	WARN_ON(data_len < 0);
3647	3646	return data_len;
..	..	@@ -3652,9 +3651,9 @@
3652	3651	* the start of the leaf data. IOW, how much room
3653	3652	* the leaf has left for both items and data
3654	3653	*/
3655		-noinline int btrfs_leaf_free_space(struct btrfs_fs_info *fs_info,
3656		- struct extent_buffer *leaf)
	3654	+noinline int btrfs_leaf_free_space(struct extent_buffer *leaf)
3657	3655	{
	3656	+ struct btrfs_fs_info *fs_info = leaf->fs_info;
3658	3657	int nritems = btrfs_header_nritems(leaf);
3659	3658	int ret;
3660	3659
..	..	@@ -3673,13 +3672,13 @@
3673	3672	* min slot controls the lowest index we're willing to push to the
3674	3673	* right. We'll push up to and including min_slot, but no lower
3675	3674	*/
3676		-static noinline int __push_leaf_right(struct btrfs_fs_info *fs_info,
3677		- struct btrfs_path *path,
	3675	+static noinline int __push_leaf_right(struct btrfs_path *path,
3678	3676	int data_size, int empty,
3679	3677	struct extent_buffer *right,
3680	3678	int free_space, u32 left_nritems,
3681	3679	u32 min_slot)
3682	3680	{
	3681	+ struct btrfs_fs_info *fs_info = right->fs_info;
3683	3682	struct extent_buffer *left = path->nodes[0];
3684	3683	struct extent_buffer *upper = path->nodes[1];
3685	3684	struct btrfs_map_token token;
..	..	@@ -3693,8 +3692,6 @@
3693	3692	u32 right_nritems;
3694	3693	u32 data_end;
3695	3694	u32 this_item_size;
3696		-
3697		- btrfs_init_map_token(&token);
3698	3695
3699	3696	if (empty)
3700	3697	nr = 0;
..	..	@@ -3713,7 +3710,8 @@
3713	3710	if (path->slots[0] > i)
3714	3711	break;
3715	3712	if (path->slots[0] == i) {
3716		- int space = btrfs_leaf_free_space(fs_info, left);
	3713	+ int space = btrfs_leaf_free_space(left);
	3714	+
3717	3715	if (space + push_space * 2 > free_space)
3718	3716	break;
3719	3717	}
..	..	@@ -3742,10 +3740,10 @@
3742	3740	right_nritems = btrfs_header_nritems(right);
3743	3741
3744	3742	push_space = btrfs_item_end_nr(left, left_nritems - push_items);
3745		- push_space -= leaf_data_end(fs_info, left);
	3743	+ push_space -= leaf_data_end(left);
3746	3744
3747	3745	/* make room in the right data area */
3748		- data_end = leaf_data_end(fs_info, right);
	3746	+ data_end = leaf_data_end(right);
3749	3747	memmove_extent_buffer(right,
3750	3748	BTRFS_LEAF_DATA_OFFSET + data_end - push_space,
3751	3749	BTRFS_LEAF_DATA_OFFSET + data_end,
..	..	@@ -3754,7 +3752,7 @@
3754	3752	/* copy from the left data area */
3755	3753	copy_extent_buffer(right, left, BTRFS_LEAF_DATA_OFFSET +
3756	3754	BTRFS_LEAF_DATA_SIZE(fs_info) - push_space,
3757		- BTRFS_LEAF_DATA_OFFSET + leaf_data_end(fs_info, left),
	3755	+ BTRFS_LEAF_DATA_OFFSET + leaf_data_end(left),
3758	3756	push_space);
3759	3757
3760	3758	memmove_extent_buffer(right, btrfs_item_nr_offset(push_items),
..	..	@@ -3767,13 +3765,14 @@
3767	3765	push_items * sizeof(struct btrfs_item));
3768	3766
3769	3767	/* update the item pointers */
	3768	+ btrfs_init_map_token(&token, right);
3770	3769	right_nritems += push_items;
3771	3770	btrfs_set_header_nritems(right, right_nritems);
3772	3771	push_space = BTRFS_LEAF_DATA_SIZE(fs_info);
3773	3772	for (i = 0; i < right_nritems; i++) {
3774	3773	item = btrfs_item_nr(i);
3775		- push_space -= btrfs_token_item_size(right, item, &token);
3776		- btrfs_set_token_item_offset(right, item, push_space, &token);
	3774	+ push_space -= btrfs_token_item_size(&token, item);
	3775	+ btrfs_set_token_item_offset(&token, item, push_space);
3777	3776	}
3778	3777
3779	3778	left_nritems -= push_items;
..	..	@@ -3782,7 +3781,7 @@
3782	3781	if (left_nritems)
3783	3782	btrfs_mark_buffer_dirty(left);
3784	3783	else
3785		- clean_tree_block(fs_info, left);
	3784	+ btrfs_clean_tree_block(left);
3786	3785
3787	3786	btrfs_mark_buffer_dirty(right);
3788	3787
..	..	@@ -3794,7 +3793,7 @@
3794	3793	if (path->slots[0] >= left_nritems) {
3795	3794	path->slots[0] -= left_nritems;
3796	3795	if (btrfs_header_nritems(path->nodes[0]) == 0)
3797		- clean_tree_block(fs_info, path->nodes[0]);
	3796	+ btrfs_clean_tree_block(path->nodes[0]);
3798	3797	btrfs_tree_unlock(path->nodes[0]);
3799	3798	free_extent_buffer(path->nodes[0]);
3800	3799	path->nodes[0] = right;
..	..	@@ -3826,7 +3825,6 @@
3826	3825	int min_data_size, int data_size,
3827	3826	int empty, u32 min_slot)
3828	3827	{
3829		- struct btrfs_fs_info *fs_info = root->fs_info;
3830	3828	struct extent_buffer *left = path->nodes[0];
3831	3829	struct extent_buffer *right;
3832	3830	struct extent_buffer *upper;
..	..	@@ -3845,7 +3843,7 @@
3845	3843
3846	3844	btrfs_assert_tree_locked(path->nodes[1]);
3847	3845
3848		- right = read_node_slot(fs_info, upper, slot + 1);
	3846	+ right = btrfs_read_node_slot(upper, slot + 1);
3849	3847	/*
3850	3848	* slot + 1 is not valid or we fail to read the right node,
3851	3849	* no big deal, just return.
..	..	@@ -3853,20 +3851,20 @@
3853	3851	if (IS_ERR(right))
3854	3852	return 1;
3855	3853
3856		- btrfs_tree_lock(right);
3857		- btrfs_set_lock_blocking(right);
	3854	+ __btrfs_tree_lock(right, BTRFS_NESTING_RIGHT);
	3855	+ btrfs_set_lock_blocking_write(right);
3858	3856
3859		- free_space = btrfs_leaf_free_space(fs_info, right);
	3857	+ free_space = btrfs_leaf_free_space(right);
3860	3858	if (free_space < data_size)
3861	3859	goto out_unlock;
3862	3860
3863	3861	/* cow and double check */
3864	3862	ret = btrfs_cow_block(trans, root, right, upper,
3865		- slot + 1, &right);
	3863	+ slot + 1, &right, BTRFS_NESTING_RIGHT_COW);
3866	3864	if (ret)
3867	3865	goto out_unlock;
3868	3866
3869		- free_space = btrfs_leaf_free_space(fs_info, right);
	3867	+ free_space = btrfs_leaf_free_space(right);
3870	3868	if (free_space < data_size)
3871	3869	goto out_unlock;
3872	3870
..	..	@@ -3874,11 +3872,18 @@
3874	3872	if (left_nritems == 0)
3875	3873	goto out_unlock;
3876	3874
	3875	+ if (check_sibling_keys(left, right)) {
	3876	+ ret = -EUCLEAN;
	3877	+ btrfs_abort_transaction(trans, ret);
	3878	+ btrfs_tree_unlock(right);
	3879	+ free_extent_buffer(right);
	3880	+ return ret;
	3881	+ }
3877	3882	if (path->slots[0] == left_nritems && !empty) {
3878	3883	/* Key greater than all keys in the leaf, right neighbor has
3879	3884	* enough room for it and we're not emptying our leaf to delete
3880	3885	* it, therefore use right neighbor to insert the new item and
3881		- * no need to touch/dirty our left leaft. */
	3886	+ * no need to touch/dirty our left leaf. */
3882	3887	btrfs_tree_unlock(left);
3883	3888	free_extent_buffer(left);
3884	3889	path->nodes[0] = right;
..	..	@@ -3887,7 +3892,7 @@
3887	3892	return 0;
3888	3893	}
3889	3894
3890		- return __push_leaf_right(fs_info, path, min_data_size, empty,
	3895	+ return __push_leaf_right(path, min_data_size, empty,
3891	3896	right, free_space, left_nritems, min_slot);
3892	3897	out_unlock:
3893	3898	btrfs_tree_unlock(right);
..	..	@@ -3903,12 +3908,12 @@
3903	3908	* item at 'max_slot' won't be touched. Use (u32)-1 to make us do all the
3904	3909	* items
3905	3910	*/
3906		-static noinline int __push_leaf_left(struct btrfs_fs_info *fs_info,
3907		- struct btrfs_path *path, int data_size,
	3911	+static noinline int __push_leaf_left(struct btrfs_path *path, int data_size,
3908	3912	int empty, struct extent_buffer *left,
3909	3913	int free_space, u32 right_nritems,
3910	3914	u32 max_slot)
3911	3915	{
	3916	+ struct btrfs_fs_info *fs_info = left->fs_info;
3912	3917	struct btrfs_disk_key disk_key;
3913	3918	struct extent_buffer *right = path->nodes[0];
3914	3919	int i;
..	..	@@ -3922,8 +3927,6 @@
3922	3927	u32 old_left_item_size;
3923	3928	struct btrfs_map_token token;
3924	3929
3925		- btrfs_init_map_token(&token);
3926		-
3927	3930	if (empty)
3928	3931	nr = min(right_nritems, max_slot);
3929	3932	else
..	..	@@ -3936,7 +3939,8 @@
3936	3939	if (path->slots[0] < i)
3937	3940	break;
3938	3941	if (path->slots[0] == i) {
3939		- int space = btrfs_leaf_free_space(fs_info, right);
	3942	+ int space = btrfs_leaf_free_space(right);
	3943	+
3940	3944	if (space + push_space * 2 > free_space)
3941	3945	break;
3942	3946	}
..	..	@@ -3969,23 +3973,23 @@
3969	3973	btrfs_item_offset_nr(right, push_items - 1);
3970	3974
3971	3975	copy_extent_buffer(left, right, BTRFS_LEAF_DATA_OFFSET +
3972		- leaf_data_end(fs_info, left) - push_space,
	3976	+ leaf_data_end(left) - push_space,
3973	3977	BTRFS_LEAF_DATA_OFFSET +
3974	3978	btrfs_item_offset_nr(right, push_items - 1),
3975	3979	push_space);
3976	3980	old_left_nritems = btrfs_header_nritems(left);
3977	3981	BUG_ON(old_left_nritems <= 0);
3978	3982
	3983	+ btrfs_init_map_token(&token, left);
3979	3984	old_left_item_size = btrfs_item_offset_nr(left, old_left_nritems - 1);
3980	3985	for (i = old_left_nritems; i < old_left_nritems + push_items; i++) {
3981	3986	u32 ioff;
3982	3987
3983	3988	item = btrfs_item_nr(i);
3984	3989
3985		- ioff = btrfs_token_item_offset(left, item, &token);
3986		- btrfs_set_token_item_offset(left, item,
3987		- ioff - (BTRFS_LEAF_DATA_SIZE(fs_info) - old_left_item_size),
3988		- &token);
	3990	+ ioff = btrfs_token_item_offset(&token, item);
	3991	+ btrfs_set_token_item_offset(&token, item,
	3992	+ ioff - (BTRFS_LEAF_DATA_SIZE(fs_info) - old_left_item_size));
3989	3993	}
3990	3994	btrfs_set_header_nritems(left, old_left_nritems + push_items);
3991	3995
..	..	@@ -3996,33 +4000,34 @@
3996	4000
3997	4001	if (push_items < right_nritems) {
3998	4002	push_space = btrfs_item_offset_nr(right, push_items - 1) -
3999		- leaf_data_end(fs_info, right);
	4003	+ leaf_data_end(right);
4000	4004	memmove_extent_buffer(right, BTRFS_LEAF_DATA_OFFSET +
4001	4005	BTRFS_LEAF_DATA_SIZE(fs_info) - push_space,
4002	4006	BTRFS_LEAF_DATA_OFFSET +
4003		- leaf_data_end(fs_info, right), push_space);
	4007	+ leaf_data_end(right), push_space);
4004	4008
4005	4009	memmove_extent_buffer(right, btrfs_item_nr_offset(0),
4006	4010	btrfs_item_nr_offset(push_items),
4007	4011	(btrfs_header_nritems(right) - push_items) *
4008	4012	sizeof(struct btrfs_item));
4009	4013	}
	4014	+
	4015	+ btrfs_init_map_token(&token, right);
4010	4016	right_nritems -= push_items;
4011	4017	btrfs_set_header_nritems(right, right_nritems);
4012	4018	push_space = BTRFS_LEAF_DATA_SIZE(fs_info);
4013	4019	for (i = 0; i < right_nritems; i++) {
4014	4020	item = btrfs_item_nr(i);
4015	4021
4016		- push_space = push_space - btrfs_token_item_size(right,
4017		- item, &token);
4018		- btrfs_set_token_item_offset(right, item, push_space, &token);
	4022	+ push_space = push_space - btrfs_token_item_size(&token, item);
	4023	+ btrfs_set_token_item_offset(&token, item, push_space);
4019	4024	}
4020	4025
4021	4026	btrfs_mark_buffer_dirty(left);
4022	4027	if (right_nritems)
4023	4028	btrfs_mark_buffer_dirty(right);
4024	4029	else
4025		- clean_tree_block(fs_info, right);
	4030	+ btrfs_clean_tree_block(right);
4026	4031
4027	4032	btrfs_item_key(right, &disk_key, 0);
4028	4033	fixup_low_keys(path, &disk_key, 1);
..	..	@@ -4059,7 +4064,6 @@
4059	4064	root, struct btrfs_path path, int min_data_size,
4060	4065	int data_size, int empty, u32 max_slot)
4061	4066	{
4062		- struct btrfs_fs_info *fs_info = root->fs_info;
4063	4067	struct extent_buffer *right = path->nodes[0];
4064	4068	struct extent_buffer *left;
4065	4069	int slot;
..	..	@@ -4079,7 +4083,7 @@
4079	4083
4080	4084	btrfs_assert_tree_locked(path->nodes[1]);
4081	4085
4082		- left = read_node_slot(fs_info, path->nodes[1], slot - 1);
	4086	+ left = btrfs_read_node_slot(path->nodes[1], slot - 1);
4083	4087	/*
4084	4088	* slot - 1 is not valid or we fail to read the left node,
4085	4089	* no big deal, just return.
..	..	@@ -4087,10 +4091,10 @@
4087	4091	if (IS_ERR(left))
4088	4092	return 1;
4089	4093
4090		- btrfs_tree_lock(left);
4091		- btrfs_set_lock_blocking(left);
	4094	+ __btrfs_tree_lock(left, BTRFS_NESTING_LEFT);
	4095	+ btrfs_set_lock_blocking_write(left);
4092	4096
4093		- free_space = btrfs_leaf_free_space(fs_info, left);
	4097	+ free_space = btrfs_leaf_free_space(left);
4094	4098	if (free_space < data_size) {
4095	4099	ret = 1;
4096	4100	goto out;
..	..	@@ -4098,7 +4102,8 @@
4098	4102
4099	4103	/* cow and double check */
4100	4104	ret = btrfs_cow_block(trans, root, left,
4101		- path->nodes[1], slot - 1, &left);
	4105	+ path->nodes[1], slot - 1, &left,
	4106	+ BTRFS_NESTING_LEFT_COW);
4102	4107	if (ret) {
4103	4108	/* we hit -ENOSPC, but it isn't fatal here */
4104	4109	if (ret == -ENOSPC)
..	..	@@ -4106,13 +4111,18 @@
4106	4111	goto out;
4107	4112	}
4108	4113
4109		- free_space = btrfs_leaf_free_space(fs_info, left);
	4114	+ free_space = btrfs_leaf_free_space(left);
4110	4115	if (free_space < data_size) {
4111	4116	ret = 1;
4112	4117	goto out;
4113	4118	}
4114	4119
4115		- return __push_leaf_left(fs_info, path, min_data_size,
	4120	+ if (check_sibling_keys(left, right)) {
	4121	+ ret = -EUCLEAN;
	4122	+ btrfs_abort_transaction(trans, ret);
	4123	+ goto out;
	4124	+ }
	4125	+ return __push_leaf_left(path, min_data_size,
4116	4126	empty, left, free_space, right_nritems,
4117	4127	max_slot);
4118	4128	out:
..	..	@@ -4126,23 +4136,21 @@
4126	4136	* available for the resulting leaf level of the path.
4127	4137	*/
4128	4138	static noinline void copy_for_split(struct btrfs_trans_handle *trans,
4129		- struct btrfs_fs_info *fs_info,
4130	4139	struct btrfs_path *path,
4131	4140	struct extent_buffer *l,
4132	4141	struct extent_buffer *right,
4133	4142	int slot, int mid, int nritems)
4134	4143	{
	4144	+ struct btrfs_fs_info *fs_info = trans->fs_info;
4135	4145	int data_copy_size;
4136	4146	int rt_data_off;
4137	4147	int i;
4138	4148	struct btrfs_disk_key disk_key;
4139	4149	struct btrfs_map_token token;
4140	4150
4141		- btrfs_init_map_token(&token);
4142		-
4143	4151	nritems = nritems - mid;
4144	4152	btrfs_set_header_nritems(right, nritems);
4145		- data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(fs_info, l);
	4153	+ data_copy_size = btrfs_item_end_nr(l, mid) - leaf_data_end(l);
4146	4154
4147	4155	copy_extent_buffer(right, l, btrfs_item_nr_offset(0),
4148	4156	btrfs_item_nr_offset(mid),
..	..	@@ -4151,23 +4159,22 @@
4151	4159	copy_extent_buffer(right, l,
4152	4160	BTRFS_LEAF_DATA_OFFSET + BTRFS_LEAF_DATA_SIZE(fs_info) -
4153	4161	data_copy_size, BTRFS_LEAF_DATA_OFFSET +
4154		- leaf_data_end(fs_info, l), data_copy_size);
	4162	+ leaf_data_end(l), data_copy_size);
4155	4163
4156	4164	rt_data_off = BTRFS_LEAF_DATA_SIZE(fs_info) - btrfs_item_end_nr(l, mid);
4157	4165
	4166	+ btrfs_init_map_token(&token, right);
4158	4167	for (i = 0; i < nritems; i++) {
4159	4168	struct btrfs_item *item = btrfs_item_nr(i);
4160	4169	u32 ioff;
4161	4170
4162		- ioff = btrfs_token_item_offset(right, item, &token);
4163		- btrfs_set_token_item_offset(right, item,
4164		- ioff + rt_data_off, &token);
	4171	+ ioff = btrfs_token_item_offset(&token, item);
	4172	+ btrfs_set_token_item_offset(&token, item, ioff + rt_data_off);
4165	4173	}
4166	4174
4167	4175	btrfs_set_header_nritems(l, mid);
4168	4176	btrfs_item_key(right, &disk_key, 0);
4169		- insert_ptr(trans, fs_info, path, &disk_key, right->start,
4170		- path->slots[1] + 1, 1);
	4177	+ insert_ptr(trans, path, &disk_key, right->start, path->slots[1] + 1, 1);
4171	4178
4172	4179	btrfs_mark_buffer_dirty(right);
4173	4180	btrfs_mark_buffer_dirty(l);
..	..	@@ -4202,7 +4209,6 @@
4202	4209	struct btrfs_path *path,
4203	4210	int data_size)
4204	4211	{
4205		- struct btrfs_fs_info *fs_info = root->fs_info;
4206	4212	int ret;
4207	4213	int progress = 0;
4208	4214	int slot;
..	..	@@ -4211,7 +4217,7 @@
4211	4217
4212	4218	slot = path->slots[0];
4213	4219	if (slot < btrfs_header_nritems(path->nodes[0]))
4214		- space_needed -= btrfs_leaf_free_space(fs_info, path->nodes[0]);
	4220	+ space_needed -= btrfs_leaf_free_space(path->nodes[0]);
4215	4221
4216	4222	/*
4217	4223	* try to push all the items after our slot into the
..	..	@@ -4232,14 +4238,14 @@
4232	4238	if (path->slots[0] == 0 \|\| path->slots[0] == nritems)
4233	4239	return 0;
4234	4240
4235		- if (btrfs_leaf_free_space(fs_info, path->nodes[0]) >= data_size)
	4241	+ if (btrfs_leaf_free_space(path->nodes[0]) >= data_size)
4236	4242	return 0;
4237	4243
4238	4244	/* try to push all the items before our slot into the next leaf */
4239	4245	slot = path->slots[0];
4240	4246	space_needed = data_size;
4241	4247	if (slot > 0)
4242		- space_needed -= btrfs_leaf_free_space(fs_info, path->nodes[0]);
	4248	+ space_needed -= btrfs_leaf_free_space(path->nodes[0]);
4243	4249	ret = push_leaf_left(trans, root, path, 1, space_needed, 0, slot);
4244	4250	if (ret < 0)
4245	4251	return ret;
..	..	@@ -4288,7 +4294,7 @@
4288	4294	int space_needed = data_size;
4289	4295
4290	4296	if (slot < btrfs_header_nritems(l))
4291		- space_needed -= btrfs_leaf_free_space(fs_info, l);
	4297	+ space_needed -= btrfs_leaf_free_space(l);
4292	4298
4293	4299	wret = push_leaf_right(trans, root, path, space_needed,
4294	4300	space_needed, 0, 0);
..	..	@@ -4297,8 +4303,7 @@
4297	4303	if (wret) {
4298	4304	space_needed = data_size;
4299	4305	if (slot > 0)
4300		- space_needed -= btrfs_leaf_free_space(fs_info,
4301		- l);
	4306	+ space_needed -= btrfs_leaf_free_space(l);
4302	4307	wret = push_leaf_left(trans, root, path, space_needed,
4303	4308	space_needed, 0, (u32)-1);
4304	4309	if (wret < 0)
..	..	@@ -4307,7 +4312,7 @@
4307	4312	l = path->nodes[0];
4308	4313
4309	4314	/* did the pushes work? */
4310		- if (btrfs_leaf_free_space(fs_info, l) >= data_size)
	4315	+ if (btrfs_leaf_free_space(l) >= data_size)
4311	4316	return 0;
4312	4317	}
4313	4318
..	..	@@ -4365,8 +4370,18 @@
4365	4370	else
4366	4371	btrfs_item_key(l, &disk_key, mid);
4367	4372
	4373	+ /*
	4374	+ * We have to about BTRFS_NESTING_NEW_ROOT here if we've done a double
	4375	+ * split, because we're only allowed to have MAX_LOCKDEP_SUBCLASSES
	4376	+ * subclasses, which is 8 at the time of this patch, and we've maxed it
	4377	+ * out. In the future we could add a
	4378	+ * BTRFS_NESTING_SPLIT_THE_SPLITTENING if we need to, but for now just
	4379	+ * use BTRFS_NESTING_NEW_ROOT.
	4380	+ */
4368	4381	right = alloc_tree_block_no_bg_flush(trans, root, 0, &disk_key, 0,
4369		- l->start, 0);
	4382	+ l->start, 0, num_doubles ?
	4383	+ BTRFS_NESTING_NEW_ROOT :
	4384	+ BTRFS_NESTING_SPLIT);
4370	4385	if (IS_ERR(right))
4371	4386	return PTR_ERR(right);
4372	4387
..	..	@@ -4375,7 +4390,7 @@
4375	4390	if (split == 0) {
4376	4391	if (mid <= slot) {
4377	4392	btrfs_set_header_nritems(right, 0);
4378		- insert_ptr(trans, fs_info, path, &disk_key,
	4393	+ insert_ptr(trans, path, &disk_key,
4379	4394	right->start, path->slots[1] + 1, 1);
4380	4395	btrfs_tree_unlock(path->nodes[0]);
4381	4396	free_extent_buffer(path->nodes[0]);
..	..	@@ -4384,7 +4399,7 @@
4384	4399	path->slots[1] += 1;
4385	4400	} else {
4386	4401	btrfs_set_header_nritems(right, 0);
4387		- insert_ptr(trans, fs_info, path, &disk_key,
	4402	+ insert_ptr(trans, path, &disk_key,
4388	4403	right->start, path->slots[1], 1);
4389	4404	btrfs_tree_unlock(path->nodes[0]);
4390	4405	free_extent_buffer(path->nodes[0]);
..	..	@@ -4401,7 +4416,7 @@
4401	4416	return ret;
4402	4417	}
4403	4418
4404		- copy_for_split(trans, fs_info, path, l, right, slot, mid, nritems);
	4419	+ copy_for_split(trans, path, l, right, slot, mid, nritems);
4405	4420
4406	4421	if (split == 2) {
4407	4422	BUG_ON(num_doubles != 0);
..	..	@@ -4414,7 +4429,7 @@
4414	4429	push_for_double:
4415	4430	push_for_double_split(trans, root, path, data_size);
4416	4431	tried_avoid_double = 1;
4417		- if (btrfs_leaf_free_space(fs_info, path->nodes[0]) >= data_size)
	4432	+ if (btrfs_leaf_free_space(path->nodes[0]) >= data_size)
4418	4433	return 0;
4419	4434	goto again;
4420	4435	}
..	..	@@ -4423,7 +4438,6 @@
4423	4438	struct btrfs_root *root,
4424	4439	struct btrfs_path *path, int ins_len)
4425	4440	{
4426		- struct btrfs_fs_info *fs_info = root->fs_info;
4427	4441	struct btrfs_key key;
4428	4442	struct extent_buffer *leaf;
4429	4443	struct btrfs_file_extent_item *fi;
..	..	@@ -4437,7 +4451,7 @@
4437	4451	BUG_ON(key.type != BTRFS_EXTENT_DATA_KEY &&
4438	4452	key.type != BTRFS_EXTENT_CSUM_KEY);
4439	4453
4440		- if (btrfs_leaf_free_space(fs_info, leaf) >= ins_len)
	4454	+ if (btrfs_leaf_free_space(leaf) >= ins_len)
4441	4455	return 0;
4442	4456
4443	4457	item_size = btrfs_item_size_nr(leaf, path->slots[0]);
..	..	@@ -4464,7 +4478,7 @@
4464	4478	goto err;
4465	4479
4466	4480	/* the leaf has changed, it now has room. return now */
4467		- if (btrfs_leaf_free_space(fs_info, path->nodes[0]) >= ins_len)
	4481	+ if (btrfs_leaf_free_space(path->nodes[0]) >= ins_len)
4468	4482	goto err;
4469	4483
4470	4484	if (key.type == BTRFS_EXTENT_DATA_KEY) {
..	..	@@ -4487,8 +4501,7 @@
4487	4501	return ret;
4488	4502	}
4489	4503
4490		-static noinline int split_item(struct btrfs_fs_info *fs_info,
4491		- struct btrfs_path *path,
	4504	+static noinline int split_item(struct btrfs_path *path,
4492	4505	const struct btrfs_key *new_key,
4493	4506	unsigned long split_offset)
4494	4507	{
..	..	@@ -4503,7 +4516,7 @@
4503	4516	struct btrfs_disk_key disk_key;
4504	4517
4505	4518	leaf = path->nodes[0];
4506		- BUG_ON(btrfs_leaf_free_space(fs_info, leaf) < sizeof(struct btrfs_item));
	4519	+ BUG_ON(btrfs_leaf_free_space(leaf) < sizeof(struct btrfs_item));
4507	4520
4508	4521	btrfs_set_path_blocking(path);
4509	4522
..	..	@@ -4552,7 +4565,7 @@
4552	4565	item_size - split_offset);
4553	4566	btrfs_mark_buffer_dirty(leaf);
4554	4567
4555		- BUG_ON(btrfs_leaf_free_space(fs_info, leaf) < 0);
	4568	+ BUG_ON(btrfs_leaf_free_space(leaf) < 0);
4556	4569	kfree(buf);
4557	4570	return 0;
4558	4571	}
..	..	@@ -4584,7 +4597,7 @@
4584	4597	if (ret)
4585	4598	return ret;
4586	4599
4587		- ret = split_item(root->fs_info, path, new_key, split_offset);
	4600	+ ret = split_item(path, new_key, split_offset);
4588	4601	return ret;
4589	4602	}
4590	4603
..	..	@@ -4613,9 +4626,7 @@
4613	4626	return ret;
4614	4627
4615	4628	path->slots[0]++;
4616		- setup_items_for_insert(root, path, new_key, &item_size,
4617		- item_size, item_size +
4618		- sizeof(struct btrfs_item), 1);
	4629	+ setup_items_for_insert(root, path, new_key, &item_size, 1);
4619	4630	leaf = path->nodes[0];
4620	4631	memcpy_extent_buffer(leaf,
4621	4632	btrfs_item_ptr_offset(leaf, path->slots[0]),
..	..	@@ -4630,8 +4641,7 @@
4630	4641	* off the end of the item or if we shift the item to chop bytes off
4631	4642	* the front.
4632	4643	*/
4633		-void btrfs_truncate_item(struct btrfs_fs_info *fs_info,
4634		- struct btrfs_path *path, u32 new_size, int from_end)
	4644	+void btrfs_truncate_item(struct btrfs_path *path, u32 new_size, int from_end)
4635	4645	{
4636	4646	int slot;
4637	4647	struct extent_buffer *leaf;
..	..	@@ -4644,8 +4654,6 @@
4644	4654	int i;
4645	4655	struct btrfs_map_token token;
4646	4656
4647		- btrfs_init_map_token(&token);
4648		-
4649	4657	leaf = path->nodes[0];
4650	4658	slot = path->slots[0];
4651	4659
..	..	@@ -4654,7 +4662,7 @@
4654	4662	return;
4655	4663
4656	4664	nritems = btrfs_header_nritems(leaf);
4657		- data_end = leaf_data_end(fs_info, leaf);
	4665	+ data_end = leaf_data_end(leaf);
4658	4666
4659	4667	old_data_start = btrfs_item_offset_nr(leaf, slot);
4660	4668
..	..	@@ -4667,13 +4675,13 @@
4667	4675	* item0..itemN ... dataN.offset..dataN.size .. data0.size
4668	4676	*/
4669	4677	/* first correct the data pointers */
	4678	+ btrfs_init_map_token(&token, leaf);
4670	4679	for (i = slot; i < nritems; i++) {
4671	4680	u32 ioff;
4672	4681	item = btrfs_item_nr(i);
4673	4682
4674		- ioff = btrfs_token_item_offset(leaf, item, &token);
4675		- btrfs_set_token_item_offset(leaf, item,
4676		- ioff + size_diff, &token);
	4683	+ ioff = btrfs_token_item_offset(&token, item);
	4684	+ btrfs_set_token_item_offset(&token, item, ioff + size_diff);
4677	4685	}
4678	4686
4679	4687	/* shift the data */
..	..	@@ -4720,7 +4728,7 @@
4720	4728	btrfs_set_item_size(leaf, item, new_size);
4721	4729	btrfs_mark_buffer_dirty(leaf);
4722	4730
4723		- if (btrfs_leaf_free_space(fs_info, leaf) < 0) {
	4731	+ if (btrfs_leaf_free_space(leaf) < 0) {
4724	4732	btrfs_print_leaf(leaf);
4725	4733	BUG();
4726	4734	}
..	..	@@ -4729,8 +4737,7 @@
4729	4737	/*
4730	4738	* make the item pointed to by the path bigger, data_size is the added size.
4731	4739	*/
4732		-void btrfs_extend_item(struct btrfs_fs_info fs_info, struct btrfs_path path,
4733		- u32 data_size)
	4740	+void btrfs_extend_item(struct btrfs_path *path, u32 data_size)
4734	4741	{
4735	4742	int slot;
4736	4743	struct extent_buffer *leaf;
..	..	@@ -4742,14 +4749,12 @@
4742	4749	int i;
4743	4750	struct btrfs_map_token token;
4744	4751
4745		- btrfs_init_map_token(&token);
4746		-
4747	4752	leaf = path->nodes[0];
4748	4753
4749	4754	nritems = btrfs_header_nritems(leaf);
4750		- data_end = leaf_data_end(fs_info, leaf);
	4755	+ data_end = leaf_data_end(leaf);
4751	4756
4752		- if (btrfs_leaf_free_space(fs_info, leaf) < data_size) {
	4757	+ if (btrfs_leaf_free_space(leaf) < data_size) {
4753	4758	btrfs_print_leaf(leaf);
4754	4759	BUG();
4755	4760	}
..	..	@@ -4759,22 +4764,22 @@
4759	4764	BUG_ON(slot < 0);
4760	4765	if (slot >= nritems) {
4761	4766	btrfs_print_leaf(leaf);
4762		- btrfs_crit(fs_info, "slot %d too large, nritems %d",
	4767	+ btrfs_crit(leaf->fs_info, "slot %d too large, nritems %d",
4763	4768	slot, nritems);
4764		- BUG_ON(1);
	4769	+ BUG();
4765	4770	}
4766	4771
4767	4772	/*
4768	4773	* item0..itemN ... dataN.offset..dataN.size .. data0.size
4769	4774	*/
4770	4775	/* first correct the data pointers */
	4776	+ btrfs_init_map_token(&token, leaf);
4771	4777	for (i = slot; i < nritems; i++) {
4772	4778	u32 ioff;
4773	4779	item = btrfs_item_nr(i);
4774	4780
4775		- ioff = btrfs_token_item_offset(leaf, item, &token);
4776		- btrfs_set_token_item_offset(leaf, item,
4777		- ioff - data_size, &token);
	4781	+ ioff = btrfs_token_item_offset(&token, item);
	4782	+ btrfs_set_token_item_offset(&token, item, ioff - data_size);
4778	4783	}
4779	4784
4780	4785	/* shift the data */
..	..	@@ -4788,20 +4793,26 @@
4788	4793	btrfs_set_item_size(leaf, item, old_size + data_size);
4789	4794	btrfs_mark_buffer_dirty(leaf);
4790	4795
4791		- if (btrfs_leaf_free_space(fs_info, leaf) < 0) {
	4796	+ if (btrfs_leaf_free_space(leaf) < 0) {
4792	4797	btrfs_print_leaf(leaf);
4793	4798	BUG();
4794	4799	}
4795	4800	}
4796	4801
4797		-/*
4798		- * this is a helper for btrfs_insert_empty_items, the main goal here is
4799		- * to save stack depth by doing the bulk of the work in a function
4800		- * that doesn't call btrfs_search_slot
	4802	+/**
	4803	+ * setup_items_for_insert - Helper called before inserting one or more items
	4804	+ * to a leaf. Main purpose is to save stack depth by doing the bulk of the work
	4805	+ * in a function that doesn't call btrfs_search_slot
	4806	+ *
	4807	+ * @root: root we are inserting items to
	4808	+ * @path: points to the leaf/slot where we are going to insert new items
	4809	+ * @cpu_key: array of keys for items to be inserted
	4810	+ * @data_size: size of the body of each item we are going to insert
	4811	+ * @nr: size of @cpu_key/@data_size arrays
4801	4812	*/
4802	4813	void setup_items_for_insert(struct btrfs_root root, struct btrfs_path path,
4803	4814	const struct btrfs_key cpu_key, u32 data_size,
4804		- u32 total_data, u32 total_size, int nr)
	4815	+ int nr)
4805	4816	{
4806	4817	struct btrfs_fs_info *fs_info = root->fs_info;
4807	4818	struct btrfs_item *item;
..	..	@@ -4812,6 +4823,12 @@
4812	4823	struct extent_buffer *leaf;
4813	4824	int slot;
4814	4825	struct btrfs_map_token token;
	4826	+ u32 total_size;
	4827	+ u32 total_data = 0;
	4828	+
	4829	+ for (i = 0; i < nr; i++)
	4830	+ total_data += data_size[i];
	4831	+ total_size = total_data + (nr * sizeof(struct btrfs_item));
4815	4832
4816	4833	if (path->slots[0] == 0) {
4817	4834	btrfs_cpu_key_to_disk(&disk_key, cpu_key);
..	..	@@ -4819,29 +4836,29 @@
4819	4836	}
4820	4837	btrfs_unlock_up_safe(path, 1);
4821	4838
4822		- btrfs_init_map_token(&token);
4823		-
4824	4839	leaf = path->nodes[0];
4825	4840	slot = path->slots[0];
4826	4841
4827	4842	nritems = btrfs_header_nritems(leaf);
4828		- data_end = leaf_data_end(fs_info, leaf);
	4843	+ data_end = leaf_data_end(leaf);
4829	4844
4830		- if (btrfs_leaf_free_space(fs_info, leaf) < total_size) {
	4845	+ if (btrfs_leaf_free_space(leaf) < total_size) {
4831	4846	btrfs_print_leaf(leaf);
4832	4847	btrfs_crit(fs_info, "not enough freespace need %u have %d",
4833		- total_size, btrfs_leaf_free_space(fs_info, leaf));
	4848	+ total_size, btrfs_leaf_free_space(leaf));
4834	4849	BUG();
4835	4850	}
4836	4851
	4852	+ btrfs_init_map_token(&token, leaf);
4837	4853	if (slot != nritems) {
4838	4854	unsigned int old_data = btrfs_item_end_nr(leaf, slot);
4839	4855
4840	4856	if (old_data < data_end) {
4841	4857	btrfs_print_leaf(leaf);
4842		- btrfs_crit(fs_info, "slot %d old_data %d data_end %d",
	4858	+ btrfs_crit(fs_info,
	4859	+ "item at slot %d with data offset %u beyond data end of leaf %u",
4843	4860	slot, old_data, data_end);
4844		- BUG_ON(1);
	4861	+ BUG();
4845	4862	}
4846	4863	/*
4847	4864	* item0..itemN ... dataN.offset..dataN.size .. data0.size
..	..	@@ -4851,9 +4868,9 @@
4851	4868	u32 ioff;
4852	4869
4853	4870	item = btrfs_item_nr(i);
4854		- ioff = btrfs_token_item_offset(leaf, item, &token);
4855		- btrfs_set_token_item_offset(leaf, item,
4856		- ioff - total_data, &token);
	4871	+ ioff = btrfs_token_item_offset(&token, item);
	4872	+ btrfs_set_token_item_offset(&token, item,
	4873	+ ioff - total_data);
4857	4874	}
4858	4875	/* shift the items */
4859	4876	memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot + nr),
..	..	@@ -4872,16 +4889,15 @@
4872	4889	btrfs_cpu_key_to_disk(&disk_key, cpu_key + i);
4873	4890	btrfs_set_item_key(leaf, &disk_key, slot + i);
4874	4891	item = btrfs_item_nr(slot + i);
4875		- btrfs_set_token_item_offset(leaf, item,
4876		- data_end - data_size[i], &token);
4877	4892	data_end -= data_size[i];
4878		- btrfs_set_token_item_size(leaf, item, data_size[i], &token);
	4893	+ btrfs_set_token_item_offset(&token, item, data_end);
	4894	+ btrfs_set_token_item_size(&token, item, data_size[i]);
4879	4895	}
4880	4896
4881	4897	btrfs_set_header_nritems(leaf, nritems + nr);
4882	4898	btrfs_mark_buffer_dirty(leaf);
4883	4899
4884		- if (btrfs_leaf_free_space(fs_info, leaf) < 0) {
	4900	+ if (btrfs_leaf_free_space(leaf) < 0) {
4885	4901	btrfs_print_leaf(leaf);
4886	4902	BUG();
4887	4903	}
..	..	@@ -4916,8 +4932,7 @@
4916	4932	slot = path->slots[0];
4917	4933	BUG_ON(slot < 0);
4918	4934
4919		- setup_items_for_insert(root, path, cpu_key, data_size,
4920		- total_data, total_size, nr);
	4935	+ setup_items_for_insert(root, path, cpu_key, data_size, nr);
4921	4936	return 0;
4922	4937	}
4923	4938
..	..	@@ -5020,7 +5035,7 @@
5020	5035
5021	5036	root_sub_used(root, leaf->len);
5022	5037
5023		- extent_buffer_get(leaf);
	5038	+ atomic_inc(&leaf->refs);
5024	5039	btrfs_free_tree_block(trans, root, leaf, 0, 1);
5025	5040	free_extent_buffer_stale(leaf);
5026	5041	}
..	..	@@ -5040,9 +5055,6 @@
5040	5055	int wret;
5041	5056	int i;
5042	5057	u32 nritems;
5043		- struct btrfs_map_token token;
5044		-
5045		- btrfs_init_map_token(&token);
5046	5058
5047	5059	leaf = path->nodes[0];
5048	5060	last_off = btrfs_item_offset_nr(leaf, slot + nr - 1);
..	..	@@ -5053,20 +5065,21 @@
5053	5065	nritems = btrfs_header_nritems(leaf);
5054	5066
5055	5067	if (slot + nr != nritems) {
5056		- int data_end = leaf_data_end(fs_info, leaf);
	5068	+ int data_end = leaf_data_end(leaf);
	5069	+ struct btrfs_map_token token;
5057	5070
5058	5071	memmove_extent_buffer(leaf, BTRFS_LEAF_DATA_OFFSET +
5059	5072	data_end + dsize,
5060	5073	BTRFS_LEAF_DATA_OFFSET + data_end,
5061	5074	last_off - data_end);
5062	5075
	5076	+ btrfs_init_map_token(&token, leaf);
5063	5077	for (i = slot + nr; i < nritems; i++) {
5064	5078	u32 ioff;
5065	5079
5066	5080	item = btrfs_item_nr(i);
5067		- ioff = btrfs_token_item_offset(leaf, item, &token);
5068		- btrfs_set_token_item_offset(leaf, item,
5069		- ioff + dsize, &token);
	5081	+ ioff = btrfs_token_item_offset(&token, item);
	5082	+ btrfs_set_token_item_offset(&token, item, ioff + dsize);
5070	5083	}
5071	5084
5072	5085	memmove_extent_buffer(leaf, btrfs_item_nr_offset(slot),
..	..	@@ -5083,7 +5096,7 @@
5083	5096	btrfs_set_header_level(leaf, 0);
5084	5097	} else {
5085	5098	btrfs_set_path_blocking(path);
5086		- clean_tree_block(fs_info, leaf);
	5099	+ btrfs_clean_tree_block(leaf);
5087	5100	btrfs_del_leaf(trans, root, path, leaf);
5088	5101	}
5089	5102	} else {
..	..	@@ -5102,7 +5115,7 @@
5102	5115	* for possible call to del_ptr below
5103	5116	*/
5104	5117	slot = path->slots[1];
5105		- extent_buffer_get(leaf);
	5118	+ atomic_inc(&leaf->refs);
5106	5119
5107	5120	btrfs_set_path_blocking(path);
5108	5121	wret = push_leaf_left(trans, root, path, 1, 1,
..	..	@@ -5151,10 +5164,12 @@
5151	5164	int btrfs_prev_leaf(struct btrfs_root root, struct btrfs_path path)
5152	5165	{
5153	5166	struct btrfs_key key;
	5167	+ struct btrfs_key orig_key;
5154	5168	struct btrfs_disk_key found_key;
5155	5169	int ret;
5156	5170
5157	5171	btrfs_item_key_to_cpu(path->nodes[0], &key, 0);
	5172	+ orig_key = key;
5158	5173
5159	5174	if (key.offset > 0) {
5160	5175	key.offset--;
..	..	@@ -5171,8 +5186,36 @@
5171	5186
5172	5187	btrfs_release_path(path);
5173	5188	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
5174		- if (ret < 0)
	5189	+ if (ret <= 0)
5175	5190	return ret;
	5191	+
	5192	+ /*
	5193	+ * Previous key not found. Even if we were at slot 0 of the leaf we had
	5194	+ * before releasing the path and calling btrfs_search_slot(), we now may
	5195	+ * be in a slot pointing to the same original key - this can happen if
	5196	+ * after we released the path, one of more items were moved from a
	5197	+ * sibling leaf into the front of the leaf we had due to an insertion
	5198	+ * (see push_leaf_right()).
	5199	+ * If we hit this case and our slot is > 0 and just decrement the slot
	5200	+ * so that the caller does not process the same key again, which may or
	5201	+ * may not break the caller, depending on its logic.
	5202	+ */
	5203	+ if (path->slots[0] < btrfs_header_nritems(path->nodes[0])) {
	5204	+ btrfs_item_key(path->nodes[0], &found_key, path->slots[0]);
	5205	+ ret = comp_keys(&found_key, &orig_key);
	5206	+ if (ret == 0) {
	5207	+ if (path->slots[0] > 0) {
	5208	+ path->slots[0]--;
	5209	+ return 0;
	5210	+ }
	5211	+ /*
	5212	+ * At slot 0, same key as before, it means orig_key is
	5213	+ * the lowest, leftmost, key in the tree. We're done.
	5214	+ */
	5215	+ return 1;
	5216	+ }
	5217	+ }
	5218	+
5176	5219	btrfs_item_key(path->nodes[0], &found_key, 0);
5177	5220	ret = comp_keys(&found_key, &key);
5178	5221	/*
..	..	@@ -5213,7 +5256,6 @@
5213	5256	struct btrfs_path *path,
5214	5257	u64 min_trans)
5215	5258	{
5216		- struct btrfs_fs_info *fs_info = root->fs_info;
5217	5259	struct extent_buffer *cur;
5218	5260	struct btrfs_key found_key;
5219	5261	int slot;
..	..	@@ -5238,7 +5280,11 @@
5238	5280	while (1) {
5239	5281	nritems = btrfs_header_nritems(cur);
5240	5282	level = btrfs_header_level(cur);
5241		- sret = btrfs_bin_search(cur, min_key, level, &slot);
	5283	+ sret = btrfs_bin_search(cur, min_key, &slot);
	5284	+ if (sret < 0) {
	5285	+ ret = sret;
	5286	+ goto out;
	5287	+ }
5242	5288
5243	5289	/* at the lowest level, we're done, setup the path and exit */
5244	5290	if (level == path->lowest_level) {
..	..	@@ -5253,7 +5299,7 @@
5253	5299	slot--;
5254	5300	/*
5255	5301	* check this node pointer against the min_trans parameters.
5256		- * If it is too old, old, skip to the next one.
	5302	+ * If it is too old, skip to the next one.
5257	5303	*/
5258	5304	while (slot < nritems) {
5259	5305	u64 gen;
..	..	@@ -5290,7 +5336,7 @@
5290	5336	goto out;
5291	5337	}
5292	5338	btrfs_set_path_blocking(path);
5293		- cur = read_node_slot(fs_info, cur, slot);
	5339	+ cur = btrfs_read_node_slot(cur, slot);
5294	5340	if (IS_ERR(cur)) {
5295	5341	ret = PTR_ERR(cur);
5296	5342	goto out;
..	..	@@ -5301,7 +5347,6 @@
5301	5347	path->locks[level - 1] = BTRFS_READ_LOCK;
5302	5348	path->nodes[level - 1] = cur;
5303	5349	unlock_up(path, level, 1, 0, NULL);
5304		- btrfs_clear_path_blocking(path, NULL, 0);
5305	5350	}
5306	5351	out:
5307	5352	path->keep_locks = keep_locks;
..	..	@@ -5310,374 +5355,6 @@
5310	5355	btrfs_set_path_blocking(path);
5311	5356	memcpy(min_key, &found_key, sizeof(found_key));
5312	5357	}
5313		- return ret;
5314		-}
5315		-
5316		-static int tree_move_down(struct btrfs_fs_info *fs_info,
5317		- struct btrfs_path *path,
5318		- int *level)
5319		-{
5320		- struct extent_buffer *eb;
5321		-
5322		- BUG_ON(*level == 0);
5323		- eb = read_node_slot(fs_info, path->nodes[level], path->slots[level]);
5324		- if (IS_ERR(eb))
5325		- return PTR_ERR(eb);
5326		-
5327		- path->nodes[*level - 1] = eb;
5328		- path->slots[*level - 1] = 0;
5329		- (*level)--;
5330		- return 0;
5331		-}
5332		-
5333		-static int tree_move_next_or_upnext(struct btrfs_path *path,
5334		- int *level, int root_level)
5335		-{
5336		- int ret = 0;
5337		- int nritems;
5338		- nritems = btrfs_header_nritems(path->nodes[*level]);
5339		-
5340		- path->slots[*level]++;
5341		-
5342		- while (path->slots[*level] >= nritems) {
5343		- if (*level == root_level)
5344		- return -1;
5345		-
5346		- /* move upnext */
5347		- path->slots[*level] = 0;
5348		- free_extent_buffer(path->nodes[*level]);
5349		- path->nodes[*level] = NULL;
5350		- (*level)++;
5351		- path->slots[*level]++;
5352		-
5353		- nritems = btrfs_header_nritems(path->nodes[*level]);
5354		- ret = 1;
5355		- }
5356		- return ret;
5357		-}
5358		-
5359		-/*
5360		- * Returns 1 if it had to move up and next. 0 is returned if it moved only next
5361		- * or down.
5362		- */
5363		-static int tree_advance(struct btrfs_fs_info *fs_info,
5364		- struct btrfs_path *path,
5365		- int *level, int root_level,
5366		- int allow_down,
5367		- struct btrfs_key *key)
5368		-{
5369		- int ret;
5370		-
5371		- if (*level == 0 \|\| !allow_down) {
5372		- ret = tree_move_next_or_upnext(path, level, root_level);
5373		- } else {
5374		- ret = tree_move_down(fs_info, path, level);
5375		- }
5376		- if (ret >= 0) {
5377		- if (*level == 0)
5378		- btrfs_item_key_to_cpu(path->nodes[*level], key,
5379		- path->slots[*level]);
5380		- else
5381		- btrfs_node_key_to_cpu(path->nodes[*level], key,
5382		- path->slots[*level]);
5383		- }
5384		- return ret;
5385		-}
5386		-
5387		-static int tree_compare_item(struct btrfs_path *left_path,
5388		- struct btrfs_path *right_path,
5389		- char *tmp_buf)
5390		-{
5391		- int cmp;
5392		- int len1, len2;
5393		- unsigned long off1, off2;
5394		-
5395		- len1 = btrfs_item_size_nr(left_path->nodes[0], left_path->slots[0]);
5396		- len2 = btrfs_item_size_nr(right_path->nodes[0], right_path->slots[0]);
5397		- if (len1 != len2)
5398		- return 1;
5399		-
5400		- off1 = btrfs_item_ptr_offset(left_path->nodes[0], left_path->slots[0]);
5401		- off2 = btrfs_item_ptr_offset(right_path->nodes[0],
5402		- right_path->slots[0]);
5403		-
5404		- read_extent_buffer(left_path->nodes[0], tmp_buf, off1, len1);
5405		-
5406		- cmp = memcmp_extent_buffer(right_path->nodes[0], tmp_buf, off2, len1);
5407		- if (cmp)
5408		- return 1;
5409		- return 0;
5410		-}
5411		-
5412		-#define ADVANCE 1
5413		-#define ADVANCE_ONLY_NEXT -1
5414		-
5415		-/*
5416		- * This function compares two trees and calls the provided callback for
5417		- * every changed/new/deleted item it finds.
5418		- * If shared tree blocks are encountered, whole subtrees are skipped, making
5419		- * the compare pretty fast on snapshotted subvolumes.
5420		- *
5421		- * This currently works on commit roots only. As commit roots are read only,
5422		- * we don't do any locking. The commit roots are protected with transactions.
5423		- * Transactions are ended and rejoined when a commit is tried in between.
5424		- *
5425		- * This function checks for modifications done to the trees while comparing.
5426		- * If it detects a change, it aborts immediately.
5427		- */
5428		-int btrfs_compare_trees(struct btrfs_root *left_root,
5429		- struct btrfs_root *right_root,
5430		- btrfs_changed_cb_t changed_cb, void *ctx)
5431		-{
5432		- struct btrfs_fs_info *fs_info = left_root->fs_info;
5433		- int ret;
5434		- int cmp;
5435		- struct btrfs_path *left_path = NULL;
5436		- struct btrfs_path *right_path = NULL;
5437		- struct btrfs_key left_key;
5438		- struct btrfs_key right_key;
5439		- char *tmp_buf = NULL;
5440		- int left_root_level;
5441		- int right_root_level;
5442		- int left_level;
5443		- int right_level;
5444		- int left_end_reached;
5445		- int right_end_reached;
5446		- int advance_left;
5447		- int advance_right;
5448		- u64 left_blockptr;
5449		- u64 right_blockptr;
5450		- u64 left_gen;
5451		- u64 right_gen;
5452		-
5453		- left_path = btrfs_alloc_path();
5454		- if (!left_path) {
5455		- ret = -ENOMEM;
5456		- goto out;
5457		- }
5458		- right_path = btrfs_alloc_path();
5459		- if (!right_path) {
5460		- ret = -ENOMEM;
5461		- goto out;
5462		- }
5463		-
5464		- tmp_buf = kvmalloc(fs_info->nodesize, GFP_KERNEL);
5465		- if (!tmp_buf) {
5466		- ret = -ENOMEM;
5467		- goto out;
5468		- }
5469		-
5470		- left_path->search_commit_root = 1;
5471		- left_path->skip_locking = 1;
5472		- right_path->search_commit_root = 1;
5473		- right_path->skip_locking = 1;
5474		-
5475		- /*
5476		- * Strategy: Go to the first items of both trees. Then do
5477		- *
5478		- * If both trees are at level 0
5479		- * Compare keys of current items
5480		- * If left < right treat left item as new, advance left tree
5481		- * and repeat
5482		- * If left > right treat right item as deleted, advance right tree
5483		- * and repeat
5484		- * If left == right do deep compare of items, treat as changed if
5485		- * needed, advance both trees and repeat
5486		- * If both trees are at the same level but not at level 0
5487		- * Compare keys of current nodes/leafs
5488		- * If left < right advance left tree and repeat
5489		- * If left > right advance right tree and repeat
5490		- * If left == right compare blockptrs of the next nodes/leafs
5491		- * If they match advance both trees but stay at the same level
5492		- * and repeat
5493		- * If they don't match advance both trees while allowing to go
5494		- * deeper and repeat
5495		- * If tree levels are different
5496		- * Advance the tree that needs it and repeat
5497		- *
5498		- * Advancing a tree means:
5499		- * If we are at level 0, try to go to the next slot. If that's not
5500		- * possible, go one level up and repeat. Stop when we found a level
5501		- * where we could go to the next slot. We may at this point be on a
5502		- * node or a leaf.
5503		- *
5504		- * If we are not at level 0 and not on shared tree blocks, go one
5505		- * level deeper.
5506		- *
5507		- * If we are not at level 0 and on shared tree blocks, go one slot to
5508		- * the right if possible or go up and right.
5509		- */
5510		-
5511		- down_read(&fs_info->commit_root_sem);
5512		- left_level = btrfs_header_level(left_root->commit_root);
5513		- left_root_level = left_level;
5514		- left_path->nodes[left_level] =
5515		- btrfs_clone_extent_buffer(left_root->commit_root);
5516		- if (!left_path->nodes[left_level]) {
5517		- up_read(&fs_info->commit_root_sem);
5518		- ret = -ENOMEM;
5519		- goto out;
5520		- }
5521		- extent_buffer_get(left_path->nodes[left_level]);
5522		-
5523		- right_level = btrfs_header_level(right_root->commit_root);
5524		- right_root_level = right_level;
5525		- right_path->nodes[right_level] =
5526		- btrfs_clone_extent_buffer(right_root->commit_root);
5527		- if (!right_path->nodes[right_level]) {
5528		- up_read(&fs_info->commit_root_sem);
5529		- ret = -ENOMEM;
5530		- goto out;
5531		- }
5532		- extent_buffer_get(right_path->nodes[right_level]);
5533		- up_read(&fs_info->commit_root_sem);
5534		-
5535		- if (left_level == 0)
5536		- btrfs_item_key_to_cpu(left_path->nodes[left_level],
5537		- &left_key, left_path->slots[left_level]);
5538		- else
5539		- btrfs_node_key_to_cpu(left_path->nodes[left_level],
5540		- &left_key, left_path->slots[left_level]);
5541		- if (right_level == 0)
5542		- btrfs_item_key_to_cpu(right_path->nodes[right_level],
5543		- &right_key, right_path->slots[right_level]);
5544		- else
5545		- btrfs_node_key_to_cpu(right_path->nodes[right_level],
5546		- &right_key, right_path->slots[right_level]);
5547		-
5548		- left_end_reached = right_end_reached = 0;
5549		- advance_left = advance_right = 0;
5550		-
5551		- while (1) {
5552		- cond_resched();
5553		- if (advance_left && !left_end_reached) {
5554		- ret = tree_advance(fs_info, left_path, &left_level,
5555		- left_root_level,
5556		- advance_left != ADVANCE_ONLY_NEXT,
5557		- &left_key);
5558		- if (ret == -1)
5559		- left_end_reached = ADVANCE;
5560		- else if (ret < 0)
5561		- goto out;
5562		- advance_left = 0;
5563		- }
5564		- if (advance_right && !right_end_reached) {
5565		- ret = tree_advance(fs_info, right_path, &right_level,
5566		- right_root_level,
5567		- advance_right != ADVANCE_ONLY_NEXT,
5568		- &right_key);
5569		- if (ret == -1)
5570		- right_end_reached = ADVANCE;
5571		- else if (ret < 0)
5572		- goto out;
5573		- advance_right = 0;
5574		- }
5575		-
5576		- if (left_end_reached && right_end_reached) {
5577		- ret = 0;
5578		- goto out;
5579		- } else if (left_end_reached) {
5580		- if (right_level == 0) {
5581		- ret = changed_cb(left_path, right_path,
5582		- &right_key,
5583		- BTRFS_COMPARE_TREE_DELETED,
5584		- ctx);
5585		- if (ret < 0)
5586		- goto out;
5587		- }
5588		- advance_right = ADVANCE;
5589		- continue;
5590		- } else if (right_end_reached) {
5591		- if (left_level == 0) {
5592		- ret = changed_cb(left_path, right_path,
5593		- &left_key,
5594		- BTRFS_COMPARE_TREE_NEW,
5595		- ctx);
5596		- if (ret < 0)
5597		- goto out;
5598		- }
5599		- advance_left = ADVANCE;
5600		- continue;
5601		- }
5602		-
5603		- if (left_level == 0 && right_level == 0) {
5604		- cmp = btrfs_comp_cpu_keys(&left_key, &right_key);
5605		- if (cmp < 0) {
5606		- ret = changed_cb(left_path, right_path,
5607		- &left_key,
5608		- BTRFS_COMPARE_TREE_NEW,
5609		- ctx);
5610		- if (ret < 0)
5611		- goto out;
5612		- advance_left = ADVANCE;
5613		- } else if (cmp > 0) {
5614		- ret = changed_cb(left_path, right_path,
5615		- &right_key,
5616		- BTRFS_COMPARE_TREE_DELETED,
5617		- ctx);
5618		- if (ret < 0)
5619		- goto out;
5620		- advance_right = ADVANCE;
5621		- } else {
5622		- enum btrfs_compare_tree_result result;
5623		-
5624		- WARN_ON(!extent_buffer_uptodate(left_path->nodes[0]));
5625		- ret = tree_compare_item(left_path, right_path,
5626		- tmp_buf);
5627		- if (ret)
5628		- result = BTRFS_COMPARE_TREE_CHANGED;
5629		- else
5630		- result = BTRFS_COMPARE_TREE_SAME;
5631		- ret = changed_cb(left_path, right_path,
5632		- &left_key, result, ctx);
5633		- if (ret < 0)
5634		- goto out;
5635		- advance_left = ADVANCE;
5636		- advance_right = ADVANCE;
5637		- }
5638		- } else if (left_level == right_level) {
5639		- cmp = btrfs_comp_cpu_keys(&left_key, &right_key);
5640		- if (cmp < 0) {
5641		- advance_left = ADVANCE;
5642		- } else if (cmp > 0) {
5643		- advance_right = ADVANCE;
5644		- } else {
5645		- left_blockptr = btrfs_node_blockptr(
5646		- left_path->nodes[left_level],
5647		- left_path->slots[left_level]);
5648		- right_blockptr = btrfs_node_blockptr(
5649		- right_path->nodes[right_level],
5650		- right_path->slots[right_level]);
5651		- left_gen = btrfs_node_ptr_generation(
5652		- left_path->nodes[left_level],
5653		- left_path->slots[left_level]);
5654		- right_gen = btrfs_node_ptr_generation(
5655		- right_path->nodes[right_level],
5656		- right_path->slots[right_level]);
5657		- if (left_blockptr == right_blockptr &&
5658		- left_gen == right_gen) {
5659		- /*
5660		- * As we're on a shared block, don't
5661		- * allow to go deeper.
5662		- */
5663		- advance_left = ADVANCE_ONLY_NEXT;
5664		- advance_right = ADVANCE_ONLY_NEXT;
5665		- } else {
5666		- advance_left = ADVANCE;
5667		- advance_right = ADVANCE;
5668		- }
5669		- }
5670		- } else if (left_level < right_level) {
5671		- advance_right = ADVANCE;
5672		- } else {
5673		- advance_left = ADVANCE;
5674		- }
5675		- }
5676		-
5677		-out:
5678		- btrfs_free_path(left_path);
5679		- btrfs_free_path(right_path);
5680		- kvfree(tmp_buf);
5681	5358	return ret;
5682	5359	}
5683	5360
..	..	@@ -5698,7 +5375,7 @@
5698	5375	int slot;
5699	5376	struct extent_buffer *c;
5700	5377
5701		- WARN_ON(!path->keep_locks);
	5378	+ WARN_ON(!path->keep_locks && !path->skip_locking);
5702	5379	while (level < BTRFS_MAX_LEVEL) {
5703	5380	if (!path->nodes[level])
5704	5381	return 1;
..	..	@@ -5714,7 +5391,7 @@
5714	5391	!path->nodes[level + 1])
5715	5392	return 1;
5716	5393
5717		- if (path->locks[level + 1]) {
	5394	+ if (path->locks[level + 1] \|\| path->skip_locking) {
5718	5395	level++;
5719	5396	continue;
5720	5397	}
..	..	@@ -5886,9 +5563,9 @@
5886	5563	}
5887	5564	if (!ret) {
5888	5565	btrfs_set_path_blocking(path);
5889		- btrfs_tree_read_lock(next);
5890		- btrfs_clear_path_blocking(path, next,
5891		- BTRFS_READ_LOCK);
	5566	+ __btrfs_tree_read_lock(next,
	5567	+ BTRFS_NESTING_RIGHT,
	5568	+ path->recurse);
5892	5569	}
5893	5570	next_rw_lock = BTRFS_READ_LOCK;
5894	5571	}
..	..	@@ -5923,9 +5600,9 @@
5923	5600	ret = btrfs_try_tree_read_lock(next);
5924	5601	if (!ret) {
5925	5602	btrfs_set_path_blocking(path);
5926		- btrfs_tree_read_lock(next);
5927		- btrfs_clear_path_blocking(path, next,
5928		- BTRFS_READ_LOCK);
	5603	+ __btrfs_tree_read_lock(next,
	5604	+ BTRFS_NESTING_RIGHT,
	5605	+ path->recurse);
5929	5606	}
5930	5607	next_rw_lock = BTRFS_READ_LOCK;
5931	5608	}