btrfs: Remove first key verification since it's causing false alerts

The original first key check is handled in btree_read_extent_buffer_pages(), which is good enough for level check, but to verify first key, we need at least read lock on the extent buffer, or we can hit some race and cause false alert.

Fix it by adding new verifcation function: btrfs_verify_first_key(), which will first check lock context of both parent and child extent buffer, and only when we have proper lock hold (write or read lock if

extent buffer is not in commit root) we will verify the first key.

Most of the verification happens in ctree.c after function call like read_tree_block(), read_node_slot() and read_block_for_search(), and only call btrfs_verify_first_key() after we acquire read/write lock.

Also, since first_key check is not as good as level and could easily trigger false alerts due to lock context, put it under CONFIG_BTRFS_FS_CHECK_INTEGRITY to avoid damage to end user.

Signed-off-by Qu Wenruo <[email protected]>

---
 fs/btrfs/ctree.c       | 69 ++++++++++++++++++++++++++++++++++++++++++
 fs/btrfs/ctree.h       | 58 +++++++++++++++++++++++++++++++++++
 fs/btrfs/extent-tree.c |  6 ++++
 fs/btrfs/qgroup.c      |  5 +++
 fs/btrfs/ref-verify.c  |  6 ++++
 fs/btrfs/relocation.c  | 13 ++++++++
 6 files changed, 157 insertions(+)

fs/btrfs/ctree.c +69 -0

index e044b51a2789..57721aead371 100644
@@ -1649,6 +1649,11 @@ int btrfs_realloc_node(struct btrfs_trans_handle *trans,
 
 		btrfs_tree_lock(cur);
 		btrfs_set_lock_blocking(cur);
+		if (btrfs_verify_first_key(cur, parent, i)) {
+			err = -EUCLEAN;
+			btrfs_tree_unlock(cur);
+			free_extent_buffer(cur);
+		}
 		err = __btrfs_cow_block(trans, root, cur, parent, i,
 					&cur, search_start,
 					min(16 * blocksize,

@@ -1863,6 +1868,12 @@ static noinline int balance_level(struct btrfs_trans_handle *trans,
 
 		btrfs_tree_lock(child);
 		btrfs_set_lock_blocking(child);
+		if (btrfs_verify_first_key(child, mid, 0)) {
+			ret = -EUCLEAN;
+			btrfs_tree_unlock(child);
+			free_extent_buffer(child);
+			goto enospc;
+		}
 		ret = btrfs_cow_block(trans, root, child, mid, 0, &child);
 		if (ret) {
 			btrfs_tree_unlock(child);

@@ -1901,6 +1912,10 @@ static noinline int balance_level(struct btrfs_trans_handle *trans,
 	if (left) {
 		btrfs_tree_lock(left);
 		btrfs_set_lock_blocking(left);
+		if (btrfs_verify_first_key(left, parent, pslot - 1)) {
+			ret = -EUCLEAN;
+			goto enospc;
+		}
 		wret = btrfs_cow_block(trans, root, left,
 				       parent, pslot - 1, &left);
 		if (wret) {

@@ -1916,6 +1931,10 @@ static noinline int balance_level(struct btrfs_trans_handle *trans,
 	if (right) {
 		btrfs_tree_lock(right);
 		btrfs_set_lock_blocking(right);
+		if (btrfs_verify_first_key(right, parent, pslot + 1)) {
+			ret = -EUCLEAN;
+			goto enospc;
+		}
 		wret = btrfs_cow_block(trans, root, right,
 				       parent, pslot + 1, &right);
 		if (wret) {

@@ -2079,6 +2098,8 @@ static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
 
 		btrfs_tree_lock(left);
 		btrfs_set_lock_blocking(left);
+		if (btrfs_verify_first_key(left, parent, pslot - 1))
+			goto left_out;
 
 		left_nr = btrfs_header_nritems(left);
 		if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 1) {

@@ -2119,6 +2140,7 @@ static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
 			}
 			return 0;
 		}
+left_out:
 		btrfs_tree_unlock(left);
 		free_extent_buffer(left);
 	}

@@ -2134,6 +2156,8 @@ static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
 
 		btrfs_tree_lock(right);
 		btrfs_set_lock_blocking(right);
+		if (btrfs_verify_first_key(right, parent, pslot + 1))
+			goto right_out;
 
 		right_nr = btrfs_header_nritems(right);
 		if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 1) {

@@ -2174,6 +2198,7 @@ static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
 			}
 			return 0;
 		}
+right_out:
 		btrfs_tree_unlock(right);
 		free_extent_buffer(right);
 	}

@@ -2868,6 +2893,11 @@ int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 					p->locks[level] = BTRFS_READ_LOCK;
 				}
 				p->nodes[level] = b;
+				if (btrfs_verify_first_key(b, p->nodes[level + 1],
+							   slot)) {
+					ret = -EUCLEAN;
+					goto done;
+				}
 			}
 		} else {
 			p->slots[level] = slot;

@@ -2981,6 +3011,12 @@ int btrfs_search_old_slot(struct btrfs_root *root, const struct btrfs_key *key,
 				goto done;
 			}
 
+			/*
+			 * NOTE: both parent and child go through
+			 * tree_mod_log_rewind(), first key check is no
+			 * longer consistent. So no btrfs_verify_first_key()
+			 * for this read_block_for_search().
+			 */
 			err = read_block_for_search(root, p, &b, level,
 						    slot, key);
 			if (err == -EAGAIN)

@@ -3753,6 +3789,8 @@ static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
 
 	btrfs_tree_lock(right);
 	btrfs_set_lock_blocking(right);
+	if (btrfs_verify_first_key(right, upper, slot + 1))
+		goto out_unlock;
 
 	free_space = btrfs_leaf_free_space(fs_info, right);
 	if (free_space < data_size)

@@ -3987,6 +4025,10 @@ static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
 
 	btrfs_tree_lock(left);
 	btrfs_set_lock_blocking(left);
+	if (btrfs_verify_first_key(left, path->nodes[1], slot - 1)) {
+		ret = 1;
+		goto out;
+	}
 
 	free_space = btrfs_leaf_free_space(fs_info, left);
 	if (free_space < data_size) {

@@ -5205,6 +5247,12 @@ int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key,
 		}
 
 		btrfs_tree_read_lock(cur);
+		if (btrfs_verify_first_key(cur, path->nodes[level], slot)) {
+			btrfs_tree_read_unlock(cur);
+			free_extent_buffer(cur);
+			ret = -EUCLEAN;
+			goto out;
+		}
 
 		path->locks[level - 1] = BTRFS_READ_LOCK;
 		path->nodes[level - 1] = cur;

@@ -5232,6 +5280,11 @@ static int tree_move_down(struct btrfs_fs_info *fs_info,
 	if (IS_ERR(eb))
 		return PTR_ERR(eb);
 
+	if (btrfs_verify_first_key(eb, path->nodes[*level],
+				   path->slots[*level])) {
+		free_extent_buffer(eb);
+		return -EUCLEAN;
+	}
 	path->nodes[*level - 1] = eb;
 	path->slots[*level - 1] = 0;
 	(*level)--;

@@ -5786,6 +5839,14 @@ int btrfs_next_old_leaf(struct btrfs_root *root, struct btrfs_path *path,
 							  BTRFS_READ_LOCK);
 			}
 			next_rw_lock = BTRFS_READ_LOCK;
+			if (btrfs_verify_first_key(next, path->nodes[level],
+						   slot)) {
+				ret = -EUCLEAN;
+				btrfs_tree_read_unlock(next);
+				free_extent_buffer(next);
+				btrfs_release_path(path);
+				goto done;
+			}
 		}
 		break;
 	}

@@ -5823,6 +5884,14 @@ int btrfs_next_old_leaf(struct btrfs_root *root, struct btrfs_path *path,
 							  BTRFS_READ_LOCK);
 			}
 			next_rw_lock = BTRFS_READ_LOCK;
+			if (btrfs_verify_first_key(next, path->nodes[level],
+						   0)) {
+				ret = -EUCLEAN;
+				btrfs_tree_read_unlock(next);
+				free_extent_buffer(next);
+				btrfs_release_path(path);
+				goto done;
+			}
 		}
 	}
 	ret = 0;

fs/btrfs/ctree.h +58 -0

index 0eb55825862a..033d8ae027c3 100644
@@ -44,6 +44,7 @@
 #include "extent_io.h"
 #include "extent_map.h"
 #include "async-thread.h"
+#include "print-tree.h"
 
 struct btrfs_trans_handle;
 struct btrfs_transaction;

@@ -3752,4 +3753,61 @@ static inline int btrfs_is_testing(struct btrfs_fs_info *fs_info)
 #endif
 	return 0;
 }
+
+/*
+ * Verify the first key of an extent buffer matches with its parent pointer.
+ *
+ * For tree blocks in current transaction, caller should hold at least read lock
+ * for both @eb and @parent to avoid race.
+ * While for tree blocks in commit root, no such requirement.
+ */
+static inline int btrfs_verify_first_key(struct extent_buffer *eb,
+					 struct extent_buffer *parent, int slot)
+{
+#ifdef CONFIG_BTRFS_FS_CHECK_INTEGRITY
+	struct btrfs_key parent_key;
+	struct btrfs_key found_key;
+	struct btrfs_fs_info *fs_info;
+	u64 transid = 0;
+	int ret;
+
+	if (!parent || !eb)
+		return 0;
+	fs_info = parent->fs_info;
+	transid = fs_info->last_trans_committed;
+	/*
+	 * For first_key check, we need to ensure we have proper lock hold,
+	 * or the content may change and cause false alert.
+	 */
+	if (btrfs_header_generation(eb) > transid &&
+	    !atomic_read(&eb->read_locks) && !atomic_read(&eb->write_locks)) {
+		WARN_ON(1);
+		return 0;
+	}
+	if (btrfs_header_generation(parent) > transid &&
+	    !atomic_read(&parent->read_locks) &&
+	    !atomic_read(&parent->write_locks)) {
+		WARN_ON(1);
+		return 0;
+	}
+	btrfs_node_key_to_cpu(parent, &parent_key, slot);
+	if (btrfs_header_level(eb))
+		btrfs_node_key_to_cpu(eb, &found_key, 0);
+	else
+		btrfs_item_key_to_cpu(eb, &found_key, 0);
+	ret =  btrfs_comp_cpu_keys(&found_key, &parent_key);
+	if (ret) {
+		WARN_ON(ret);
+		btrfs_err(fs_info,
+"tree first key mismatch detected, bytenr=%llu key expected=(%llu, %u, %llu) has=(%llu, %u, %llu)",
+			  eb->start, parent_key.objectid, parent_key.type,
+			  parent_key.offset, found_key.objectid,
+			  found_key.type, found_key.offset);
+	}
+	return ret;
+#else
+	return 0;
+#endif /* CONFIG_BTRFS_FS_CHECK_INTEGRITY */
+}
+
 #endif

fs/btrfs/extent-tree.c +6 -0

index f080834e4dd0..17bd22a54281 100644
@@ -8807,6 +8807,12 @@ static noinline int do_walk_down(struct btrfs_trans_handle *trans,
 		}
 		btrfs_tree_lock(next);
 		btrfs_set_lock_blocking(next);
+		if (btrfs_verify_first_key(next, path->nodes[level],
+					   path->slots[level])) {
+			btrfs_tree_unlock(next);
+			free_extent_buffer(next);
+			goto out_unlock;
+		}
 	}
 
 	level--;

fs/btrfs/qgroup.c +5 -0

index c7f129356966..4c53954297d8 100644
@@ -1744,6 +1744,11 @@ int btrfs_qgroup_trace_subtree(struct btrfs_trans_handle *trans,
 
 			btrfs_tree_read_lock(eb);
 			btrfs_set_lock_blocking_rw(eb, BTRFS_READ_LOCK);
+			if (btrfs_verify_first_key(eb, path->nodes[level + 1],
+						   parent_slot)) {
+				ret = -EUCLEAN;
+				goto out;
+			}
 			path->locks[level] = BTRFS_READ_LOCK_BLOCKING;
 
 			ret = btrfs_qgroup_trace_extent(trans, fs_info,

fs/btrfs/ref-verify.c +6 -0

index 6d856eabf34a..b996ca1fd9dc 100644
@@ -593,6 +593,12 @@ static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
 			}
 			btrfs_tree_read_lock(eb);
 			btrfs_set_lock_blocking_rw(eb, BTRFS_READ_LOCK);
+			if (btrfs_verify_first_key(eb, path->nodes[level],
+			    path->slots[level])) {
+				btrfs_tree_read_unlock_blocking(eb);
+				free_extent_buffer(eb);
+				return -EUCLEAN;
+			}
 			path->nodes[level-1] = eb;
 			path->slots[level-1] = 0;
 			path->locks[level-1] = BTRFS_READ_LOCK_BLOCKING;

fs/btrfs/relocation.c +13 -0

index 74db4694d776..74a088fbdac4 100644
@@ -1888,6 +1888,13 @@ int replace_path(struct btrfs_trans_handle *trans,
 				break;
 			}
 			btrfs_tree_lock(eb);
+			if (btrfs_verify_first_key(eb, parent, slot)) {
+				btrfs_tree_unlock(eb);
+				free_extent_buffer(eb);
+				ret = -EUCLEAN;
+				break;
+			}
+
 			if (cow) {
 				ret = btrfs_cow_block(trans, dest, eb, parent,
 						      slot, &eb);

@@ -2793,6 +2800,12 @@ static int do_relocation(struct btrfs_trans_handle *trans,
 		}
 		btrfs_tree_lock(eb);
 		btrfs_set_lock_blocking(eb);
+		if (btrfs_verify_first_key(eb, upper->eb, slot)) {
+			btrfs_tree_unlock(eb);
+			free_extent_buffer(eb);
+			err = -EUCLEAN;
+			goto next;
+		}
 
 		if (!node->eb) {
 			ret = btrfs_cow_block(trans, root, eb, upper->eb,

Quoted 5 lines · Qu Wenruo

The original first key check is handled in btree_read_extent_buffer_pages(), which is good enough for level check, but to verify first key, we need at least read lock on the extent buffer, or we can hit some race and cause false alert.

Quoted 3 lines

Fix it by adding new verifcation function: btrfs_verify_first_key(), which will first check lock context of both parent and child extent buffer, and only when we have proper lock hold (write or read lock if

So if the extent buffer is not in commit root, i.e it's active buffer in current transaction (am I right?)

then we need write lock? It's not entirely clearly from that sentence.

Quoted 7 lines

extent buffer is not in commit root) we will verify the first key.

Most of the verification happens in ctree.c after function call like read_tree_block(), read_node_slot() and read_block_for_search(), and only call btrfs_verify_first_key() after we acquire read/write lock.

Quoted 3 lines

Also, since first_key check is not as good as level and could easily trigger false alerts due to lock context, put it under CONFIG_BTRFS_FS_CHECK_INTEGRITY to avoid damage to end user.

Why is first_key check not as good as level

and why could it trigger
false alert, given this patch allegedly implements it under proper lock context, thus eliminating false positives.

Quoted 343 lines

Signed-off-by Qu Wenruo <[email protected]>

---
 fs/btrfs/ctree.c       | 69 ++++++++++++++++++++++++++++++++++++++++++
 fs/btrfs/ctree.h       | 58 +++++++++++++++++++++++++++++++++++
 fs/btrfs/extent-tree.c |  6 ++++
 fs/btrfs/qgroup.c      |  5 +++
 fs/btrfs/ref-verify.c  |  6 ++++
 fs/btrfs/relocation.c  | 13 ++++++++
 6 files changed, 157 insertions(+)

fs/btrfs/ctree.c +69 -0

index e044b51a2789..57721aead371 100644
@@ -1649,6 +1649,11 @@ int btrfs_realloc_node(struct btrfs_trans_handle *trans,
 
 		btrfs_tree_lock(cur);
 		btrfs_set_lock_blocking(cur);
+		if (btrfs_verify_first_key(cur, parent, i)) {
+			err = -EUCLEAN;
+			btrfs_tree_unlock(cur);
+			free_extent_buffer(cur);
+		}
 		err = __btrfs_cow_block(trans, root, cur, parent, i,
 					&cur, search_start,
 					min(16 * blocksize,

@@ -1863,6 +1868,12 @@ static noinline int balance_level(struct btrfs_trans_handle *trans,
 
 		btrfs_tree_lock(child);
 		btrfs_set_lock_blocking(child);
+		if (btrfs_verify_first_key(child, mid, 0)) {
+			ret = -EUCLEAN;
+			btrfs_tree_unlock(child);
+			free_extent_buffer(child);
+			goto enospc;
+		}
 		ret = btrfs_cow_block(trans, root, child, mid, 0, &child);
 		if (ret) {
 			btrfs_tree_unlock(child);

@@ -1901,6 +1912,10 @@ static noinline int balance_level(struct btrfs_trans_handle *trans,
 	if (left) {
 		btrfs_tree_lock(left);
 		btrfs_set_lock_blocking(left);
+		if (btrfs_verify_first_key(left, parent, pslot - 1)) {
+			ret = -EUCLEAN;
+			goto enospc;
+		}
 		wret = btrfs_cow_block(trans, root, left,
 				       parent, pslot - 1, &left);
 		if (wret) {

@@ -1916,6 +1931,10 @@ static noinline int balance_level(struct btrfs_trans_handle *trans,
 	if (right) {
 		btrfs_tree_lock(right);
 		btrfs_set_lock_blocking(right);
+		if (btrfs_verify_first_key(right, parent, pslot + 1)) {
+			ret = -EUCLEAN;
+			goto enospc;
+		}
 		wret = btrfs_cow_block(trans, root, right,
 				       parent, pslot + 1, &right);
 		if (wret) {

@@ -2079,6 +2098,8 @@ static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
 
 		btrfs_tree_lock(left);
 		btrfs_set_lock_blocking(left);
+		if (btrfs_verify_first_key(left, parent, pslot - 1))
+			goto left_out;
 
 		left_nr = btrfs_header_nritems(left);
 		if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 1) {

@@ -2119,6 +2140,7 @@ static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
 			}
 			return 0;
 		}
+left_out:
 		btrfs_tree_unlock(left);
 		free_extent_buffer(left);
 	}

@@ -2134,6 +2156,8 @@ static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
 
 		btrfs_tree_lock(right);
 		btrfs_set_lock_blocking(right);
+		if (btrfs_verify_first_key(right, parent, pslot + 1))
+			goto right_out;
 
 		right_nr = btrfs_header_nritems(right);
 		if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 1) {

@@ -2174,6 +2198,7 @@ static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
 			}
 			return 0;
 		}
+right_out:
 		btrfs_tree_unlock(right);
 		free_extent_buffer(right);
 	}

@@ -2868,6 +2893,11 @@ int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 					p->locks[level] = BTRFS_READ_LOCK;
 				}
 				p->nodes[level] = b;
+				if (btrfs_verify_first_key(b, p->nodes[level + 1],
+							   slot)) {
+					ret = -EUCLEAN;
+					goto done;
+				}
 			}
 		} else {
 			p->slots[level] = slot;

@@ -2981,6 +3011,12 @@ int btrfs_search_old_slot(struct btrfs_root *root, const struct btrfs_key *key,
 				goto done;
 			}
 
+			/*
+			 * NOTE: both parent and child go through
+			 * tree_mod_log_rewind(), first key check is no
+			 * longer consistent. So no btrfs_verify_first_key()
+			 * for this read_block_for_search().
+			 */
 			err = read_block_for_search(root, p, &b, level,
 						    slot, key);
 			if (err == -EAGAIN)

@@ -3753,6 +3789,8 @@ static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
 
 	btrfs_tree_lock(right);
 	btrfs_set_lock_blocking(right);
+	if (btrfs_verify_first_key(right, upper, slot + 1))
+		goto out_unlock;
 
 	free_space = btrfs_leaf_free_space(fs_info, right);
 	if (free_space < data_size)

@@ -3987,6 +4025,10 @@ static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
 
 	btrfs_tree_lock(left);
 	btrfs_set_lock_blocking(left);
+	if (btrfs_verify_first_key(left, path->nodes[1], slot - 1)) {
+		ret = 1;
+		goto out;
+	}
 
 	free_space = btrfs_leaf_free_space(fs_info, left);
 	if (free_space < data_size) {

@@ -5205,6 +5247,12 @@ int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key,
 		}
 
 		btrfs_tree_read_lock(cur);
+		if (btrfs_verify_first_key(cur, path->nodes[level], slot)) {
+			btrfs_tree_read_unlock(cur);
+			free_extent_buffer(cur);
+			ret = -EUCLEAN;
+			goto out;
+		}
 
 		path->locks[level - 1] = BTRFS_READ_LOCK;
 		path->nodes[level - 1] = cur;

@@ -5232,6 +5280,11 @@ static int tree_move_down(struct btrfs_fs_info *fs_info,
 	if (IS_ERR(eb))
 		return PTR_ERR(eb);
 
+	if (btrfs_verify_first_key(eb, path->nodes[*level],
+				   path->slots[*level])) {
+		free_extent_buffer(eb);
+		return -EUCLEAN;
+	}
 	path->nodes[*level - 1] = eb;
 	path->slots[*level - 1] = 0;
 	(*level)--;

@@ -5786,6 +5839,14 @@ int btrfs_next_old_leaf(struct btrfs_root *root, struct btrfs_path *path,
 							  BTRFS_READ_LOCK);
 			}
 			next_rw_lock = BTRFS_READ_LOCK;
+			if (btrfs_verify_first_key(next, path->nodes[level],
+						   slot)) {
+				ret = -EUCLEAN;
+				btrfs_tree_read_unlock(next);
+				free_extent_buffer(next);
+				btrfs_release_path(path);
+				goto done;
+			}
 		}
 		break;
 	}

@@ -5823,6 +5884,14 @@ int btrfs_next_old_leaf(struct btrfs_root *root, struct btrfs_path *path,
 							  BTRFS_READ_LOCK);
 			}
 			next_rw_lock = BTRFS_READ_LOCK;
+			if (btrfs_verify_first_key(next, path->nodes[level],
+						   0)) {
+				ret = -EUCLEAN;
+				btrfs_tree_read_unlock(next);
+				free_extent_buffer(next);
+				btrfs_release_path(path);
+				goto done;
+			}
 		}
 	}
 	ret = 0;

fs/btrfs/ctree.h +58 -0

index 0eb55825862a..033d8ae027c3 100644
@@ -44,6 +44,7 @@
 #include "extent_io.h"
 #include "extent_map.h"
 #include "async-thread.h"
+#include "print-tree.h"
 
 struct btrfs_trans_handle;
 struct btrfs_transaction;

@@ -3752,4 +3753,61 @@ static inline int btrfs_is_testing(struct btrfs_fs_info *fs_info)
 #endif
 	return 0;
 }
+
+/*
+ * Verify the first key of an extent buffer matches with its parent pointer.
+ *
+ * For tree blocks in current transaction, caller should hold at least read lock
+ * for both @eb and @parent to avoid race.
+ * While for tree blocks in commit root, no such requirement.
+ */
+static inline int btrfs_verify_first_key(struct extent_buffer *eb,
+					 struct extent_buffer *parent, int slot)
+{
+#ifdef CONFIG_BTRFS_FS_CHECK_INTEGRITY
+	struct btrfs_key parent_key;
+	struct btrfs_key found_key;
+	struct btrfs_fs_info *fs_info;
+	u64 transid = 0;
+	int ret;
+
+	if (!parent || !eb)
+		return 0;
+	fs_info = parent->fs_info;
+	transid = fs_info->last_trans_committed;
+	/*
+	 * For first_key check, we need to ensure we have proper lock hold,
+	 * or the content may change and cause false alert.
+	 */
+	if (btrfs_header_generation(eb) > transid &&
+	    !atomic_read(&eb->read_locks) && !atomic_read(&eb->write_locks)) {
+		WARN_ON(1);
+		return 0;
+	}
+	if (btrfs_header_generation(parent) > transid &&
+	    !atomic_read(&parent->read_locks) &&
+	    !atomic_read(&parent->write_locks)) {
+		WARN_ON(1);
+		return 0;
+	}
+	btrfs_node_key_to_cpu(parent, &parent_key, slot);
+	if (btrfs_header_level(eb))
+		btrfs_node_key_to_cpu(eb, &found_key, 0);
+	else
+		btrfs_item_key_to_cpu(eb, &found_key, 0);
+	ret =  btrfs_comp_cpu_keys(&found_key, &parent_key);
+	if (ret) {
+		WARN_ON(ret);
+		btrfs_err(fs_info,
+"tree first key mismatch detected, bytenr=%llu key expected=(%llu, %u, %llu) has=(%llu, %u, %llu)",
+			  eb->start, parent_key.objectid, parent_key.type,
+			  parent_key.offset, found_key.objectid,
+			  found_key.type, found_key.offset);
+	}
+	return ret;
+#else
+	return 0;
+#endif /* CONFIG_BTRFS_FS_CHECK_INTEGRITY */
+}
+
 #endif

fs/btrfs/extent-tree.c +6 -0

index f080834e4dd0..17bd22a54281 100644
@@ -8807,6 +8807,12 @@ static noinline int do_walk_down(struct btrfs_trans_handle *trans,
 		}
 		btrfs_tree_lock(next);
 		btrfs_set_lock_blocking(next);
+		if (btrfs_verify_first_key(next, path->nodes[level],
+					   path->slots[level])) {
+			btrfs_tree_unlock(next);
+			free_extent_buffer(next);
+			goto out_unlock;
+		}
 	}
 
 	level--;

fs/btrfs/qgroup.c +5 -0

index c7f129356966..4c53954297d8 100644
@@ -1744,6 +1744,11 @@ int btrfs_qgroup_trace_subtree(struct btrfs_trans_handle *trans,
 
 			btrfs_tree_read_lock(eb);
 			btrfs_set_lock_blocking_rw(eb, BTRFS_READ_LOCK);
+			if (btrfs_verify_first_key(eb, path->nodes[level + 1],
+						   parent_slot)) {
+				ret = -EUCLEAN;
+				goto out;
+			}
 			path->locks[level] = BTRFS_READ_LOCK_BLOCKING;
 
 			ret = btrfs_qgroup_trace_extent(trans, fs_info,

fs/btrfs/ref-verify.c +6 -0

index 6d856eabf34a..b996ca1fd9dc 100644
@@ -593,6 +593,12 @@ static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
 			}
 			btrfs_tree_read_lock(eb);
 			btrfs_set_lock_blocking_rw(eb, BTRFS_READ_LOCK);
+			if (btrfs_verify_first_key(eb, path->nodes[level],
+			    path->slots[level])) {
+				btrfs_tree_read_unlock_blocking(eb);
+				free_extent_buffer(eb);
+				return -EUCLEAN;
+			}
 			path->nodes[level-1] = eb;
 			path->slots[level-1] = 0;
 			path->locks[level-1] = BTRFS_READ_LOCK_BLOCKING;

fs/btrfs/relocation.c +7 -0

index 74db4694d776..74a088fbdac4 100644
@@ -1888,6 +1888,13 @@ int replace_path(struct btrfs_trans_handle *trans,
 				break;
 			}
 			btrfs_tree_lock(eb);
+			if (btrfs_verify_first_key(eb, parent, slot)) {
+				btrfs_tree_unlock(eb);
+				free_extent_buffer(eb);
+				ret = -EUCLEAN;
+				break;
+			}
+
 			if (cow) {
 				ret = btrfs_cow_block(trans, dest, eb, parent,
 						      slot, &eb);

@@ -2793,6 +2800,12 @@ static int do_relocation(struct btrfs_trans_handle *trans,
 		}
 		btrfs_tree_lock(eb);

fs/btrfs/relocation.c static int do_relocation(struct btrfs_trans_handle *trans, · line 2811

Quoted 10 lines

fs/btrfs/relocation.c +6 -0

 		btrfs_set_lock_blocking(eb);
+		if (btrfs_verify_first_key(eb, upper->eb, slot)) {
+			btrfs_tree_unlock(eb);
+			free_extent_buffer(eb);
+			err = -EUCLEAN;
+			goto next;
+		}
 
 		if (!node->eb) {
 			ret = btrfs_cow_block(trans, root, eb, upper->eb,

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Quoted 8 lines · Nikolay Borisov

Quoted 5 lines · Qu Wenruo

The original first key check is handled in btree_read_extent_buffer_pages(), which is good enough for level check, but to verify first key, we need at least read lock on the extent buffer, or we can hit some race and cause false alert.

Quoted 5 lines

Quoted 3 lines

Fix it by adding new verifcation function: btrfs_verify_first_key(), which will first check lock context of both parent and child extent buffer, and only when we have proper lock hold (write or read lock if

So if the extent buffer is not in commit root, i.e it's active buffer in current transaction (am I right?)

That's right.

Quoted 1 line

then we need write lock? It's not entirely clearly from that sentence.

Not really write lock. Either read or write (both spinning and blocking) is OK here.

Quoted 7 lines

Quoted 7 lines

extent buffer is not in commit root) we will verify the first key.

Most of the verification happens in ctree.c after function call like read_tree_block(), read_node_slot() and read_block_for_search(), and only call btrfs_verify_first_key() after we acquire read/write lock.

Quoted 5 lines

Quoted 3 lines

Also, since first_key check is not as good as level and could easily trigger false alerts due to lock context, put it under CONFIG_BTRFS_FS_CHECK_INTEGRITY to avoid damage to end user.

Why is first_key check not as good as level

Several reasons.

1) Level tree check can prevent loop/nodes underflow caused by level mismatch, but first_key can't
One problem we're trying to solve is, when level 1 node points to another level 1 tree, we can still try to read next level tree block. Which could underflow level.
first_key check can't really handle it.

2) first_key needs extra lock to read out needed info, while level check doesn't (hence easier and harder to cause false alert) For a given tree block, its level won't change either for active eb (modified in current trans) or committed eb.
But for first_key, we need proper lock to avoid race.

For short, first key check needs a lot of carefully reviewed check timing and error handlers, while most problem could be exposed by level check far before it hits first_key check.

Quoted 3 lines

and why could it trigger
false alert, given this patch allegedly implements it under proper lock context, thus eliminating false positives.

I mean the old and merged first_key check patch.

Thanks,
Qu

Quoted 358 lines

Quoted 343 lines

Signed-off-by Qu Wenruo <[email protected]>

---
 fs/btrfs/ctree.c       | 69 ++++++++++++++++++++++++++++++++++++++++++
 fs/btrfs/ctree.h       | 58 +++++++++++++++++++++++++++++++++++
 fs/btrfs/extent-tree.c |  6 ++++
 fs/btrfs/qgroup.c      |  5 +++
 fs/btrfs/ref-verify.c  |  6 ++++
 fs/btrfs/relocation.c  | 13 ++++++++
 6 files changed, 157 insertions(+)

fs/btrfs/ctree.c +69 -0

index e044b51a2789..57721aead371 100644
@@ -1649,6 +1649,11 @@ int btrfs_realloc_node(struct btrfs_trans_handle *trans,
 
 		btrfs_tree_lock(cur);
 		btrfs_set_lock_blocking(cur);
+		if (btrfs_verify_first_key(cur, parent, i)) {
+			err = -EUCLEAN;
+			btrfs_tree_unlock(cur);
+			free_extent_buffer(cur);
+		}
 		err = __btrfs_cow_block(trans, root, cur, parent, i,
 					&cur, search_start,
 					min(16 * blocksize,

@@ -1863,6 +1868,12 @@ static noinline int balance_level(struct btrfs_trans_handle *trans,
 
 		btrfs_tree_lock(child);
 		btrfs_set_lock_blocking(child);
+		if (btrfs_verify_first_key(child, mid, 0)) {
+			ret = -EUCLEAN;
+			btrfs_tree_unlock(child);
+			free_extent_buffer(child);
+			goto enospc;
+		}
 		ret = btrfs_cow_block(trans, root, child, mid, 0, &child);
 		if (ret) {
 			btrfs_tree_unlock(child);

@@ -1901,6 +1912,10 @@ static noinline int balance_level(struct btrfs_trans_handle *trans,
 	if (left) {
 		btrfs_tree_lock(left);
 		btrfs_set_lock_blocking(left);
+		if (btrfs_verify_first_key(left, parent, pslot - 1)) {
+			ret = -EUCLEAN;
+			goto enospc;
+		}
 		wret = btrfs_cow_block(trans, root, left,
 				       parent, pslot - 1, &left);
 		if (wret) {

@@ -1916,6 +1931,10 @@ static noinline int balance_level(struct btrfs_trans_handle *trans,
 	if (right) {
 		btrfs_tree_lock(right);
 		btrfs_set_lock_blocking(right);
+		if (btrfs_verify_first_key(right, parent, pslot + 1)) {
+			ret = -EUCLEAN;
+			goto enospc;
+		}
 		wret = btrfs_cow_block(trans, root, right,
 				       parent, pslot + 1, &right);
 		if (wret) {

@@ -2079,6 +2098,8 @@ static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
 
 		btrfs_tree_lock(left);
 		btrfs_set_lock_blocking(left);
+		if (btrfs_verify_first_key(left, parent, pslot - 1))
+			goto left_out;
 
 		left_nr = btrfs_header_nritems(left);
 		if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 1) {

@@ -2119,6 +2140,7 @@ static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
 			}
 			return 0;
 		}
+left_out:
 		btrfs_tree_unlock(left);
 		free_extent_buffer(left);
 	}

@@ -2134,6 +2156,8 @@ static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
 
 		btrfs_tree_lock(right);
 		btrfs_set_lock_blocking(right);
+		if (btrfs_verify_first_key(right, parent, pslot + 1))
+			goto right_out;
 
 		right_nr = btrfs_header_nritems(right);
 		if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 1) {

@@ -2174,6 +2198,7 @@ static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
 			}
 			return 0;
 		}
+right_out:
 		btrfs_tree_unlock(right);
 		free_extent_buffer(right);
 	}

@@ -2868,6 +2893,11 @@ int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 					p->locks[level] = BTRFS_READ_LOCK;
 				}
 				p->nodes[level] = b;
+				if (btrfs_verify_first_key(b, p->nodes[level + 1],
+							   slot)) {
+					ret = -EUCLEAN;
+					goto done;
+				}
 			}
 		} else {
 			p->slots[level] = slot;

@@ -2981,6 +3011,12 @@ int btrfs_search_old_slot(struct btrfs_root *root, const struct btrfs_key *key,
 				goto done;
 			}
 
+			/*
+			 * NOTE: both parent and child go through
+			 * tree_mod_log_rewind(), first key check is no
+			 * longer consistent. So no btrfs_verify_first_key()
+			 * for this read_block_for_search().
+			 */
 			err = read_block_for_search(root, p, &b, level,
 						    slot, key);
 			if (err == -EAGAIN)

@@ -3753,6 +3789,8 @@ static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
 
 	btrfs_tree_lock(right);
 	btrfs_set_lock_blocking(right);
+	if (btrfs_verify_first_key(right, upper, slot + 1))
+		goto out_unlock;
 
 	free_space = btrfs_leaf_free_space(fs_info, right);
 	if (free_space < data_size)

@@ -3987,6 +4025,10 @@ static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
 
 	btrfs_tree_lock(left);
 	btrfs_set_lock_blocking(left);
+	if (btrfs_verify_first_key(left, path->nodes[1], slot - 1)) {
+		ret = 1;
+		goto out;
+	}
 
 	free_space = btrfs_leaf_free_space(fs_info, left);
 	if (free_space < data_size) {

@@ -5205,6 +5247,12 @@ int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key,
 		}
 
 		btrfs_tree_read_lock(cur);
+		if (btrfs_verify_first_key(cur, path->nodes[level], slot)) {
+			btrfs_tree_read_unlock(cur);
+			free_extent_buffer(cur);
+			ret = -EUCLEAN;
+			goto out;
+		}
 
 		path->locks[level - 1] = BTRFS_READ_LOCK;
 		path->nodes[level - 1] = cur;

@@ -5232,6 +5280,11 @@ static int tree_move_down(struct btrfs_fs_info *fs_info,
 	if (IS_ERR(eb))
 		return PTR_ERR(eb);
 
+	if (btrfs_verify_first_key(eb, path->nodes[*level],
+				   path->slots[*level])) {
+		free_extent_buffer(eb);
+		return -EUCLEAN;
+	}
 	path->nodes[*level - 1] = eb;
 	path->slots[*level - 1] = 0;
 	(*level)--;

@@ -5786,6 +5839,14 @@ int btrfs_next_old_leaf(struct btrfs_root *root, struct btrfs_path *path,
 							  BTRFS_READ_LOCK);
 			}
 			next_rw_lock = BTRFS_READ_LOCK;
+			if (btrfs_verify_first_key(next, path->nodes[level],
+						   slot)) {
+				ret = -EUCLEAN;
+				btrfs_tree_read_unlock(next);
+				free_extent_buffer(next);
+				btrfs_release_path(path);
+				goto done;
+			}
 		}
 		break;
 	}

@@ -5823,6 +5884,14 @@ int btrfs_next_old_leaf(struct btrfs_root *root, struct btrfs_path *path,
 							  BTRFS_READ_LOCK);
 			}
 			next_rw_lock = BTRFS_READ_LOCK;
+			if (btrfs_verify_first_key(next, path->nodes[level],
+						   0)) {
+				ret = -EUCLEAN;
+				btrfs_tree_read_unlock(next);
+				free_extent_buffer(next);
+				btrfs_release_path(path);
+				goto done;
+			}
 		}
 	}
 	ret = 0;

fs/btrfs/ctree.h +58 -0

index 0eb55825862a..033d8ae027c3 100644
@@ -44,6 +44,7 @@
 #include "extent_io.h"
 #include "extent_map.h"
 #include "async-thread.h"
+#include "print-tree.h"
 
 struct btrfs_trans_handle;
 struct btrfs_transaction;

@@ -3752,4 +3753,61 @@ static inline int btrfs_is_testing(struct btrfs_fs_info *fs_info)
 #endif
 	return 0;
 }
+
+/*
+ * Verify the first key of an extent buffer matches with its parent pointer.
+ *
+ * For tree blocks in current transaction, caller should hold at least read lock
+ * for both @eb and @parent to avoid race.
+ * While for tree blocks in commit root, no such requirement.
+ */
+static inline int btrfs_verify_first_key(struct extent_buffer *eb,
+					 struct extent_buffer *parent, int slot)
+{
+#ifdef CONFIG_BTRFS_FS_CHECK_INTEGRITY
+	struct btrfs_key parent_key;
+	struct btrfs_key found_key;
+	struct btrfs_fs_info *fs_info;
+	u64 transid = 0;
+	int ret;
+
+	if (!parent || !eb)
+		return 0;
+	fs_info = parent->fs_info;
+	transid = fs_info->last_trans_committed;
+	/*
+	 * For first_key check, we need to ensure we have proper lock hold,
+	 * or the content may change and cause false alert.
+	 */
+	if (btrfs_header_generation(eb) > transid &&
+	    !atomic_read(&eb->read_locks) && !atomic_read(&eb->write_locks)) {
+		WARN_ON(1);
+		return 0;
+	}
+	if (btrfs_header_generation(parent) > transid &&
+	    !atomic_read(&parent->read_locks) &&
+	    !atomic_read(&parent->write_locks)) {
+		WARN_ON(1);
+		return 0;
+	}
+	btrfs_node_key_to_cpu(parent, &parent_key, slot);
+	if (btrfs_header_level(eb))
+		btrfs_node_key_to_cpu(eb, &found_key, 0);
+	else
+		btrfs_item_key_to_cpu(eb, &found_key, 0);
+	ret =  btrfs_comp_cpu_keys(&found_key, &parent_key);
+	if (ret) {
+		WARN_ON(ret);
+		btrfs_err(fs_info,
+"tree first key mismatch detected, bytenr=%llu key expected=(%llu, %u, %llu) has=(%llu, %u, %llu)",
+			  eb->start, parent_key.objectid, parent_key.type,
+			  parent_key.offset, found_key.objectid,
+			  found_key.type, found_key.offset);
+	}
+	return ret;
+#else
+	return 0;
+#endif /* CONFIG_BTRFS_FS_CHECK_INTEGRITY */
+}
+
 #endif

fs/btrfs/extent-tree.c +6 -0

index f080834e4dd0..17bd22a54281 100644
@@ -8807,6 +8807,12 @@ static noinline int do_walk_down(struct btrfs_trans_handle *trans,
 		}
 		btrfs_tree_lock(next);
 		btrfs_set_lock_blocking(next);
+		if (btrfs_verify_first_key(next, path->nodes[level],
+					   path->slots[level])) {
+			btrfs_tree_unlock(next);
+			free_extent_buffer(next);
+			goto out_unlock;
+		}
 	}
 
 	level--;

fs/btrfs/qgroup.c +5 -0

index c7f129356966..4c53954297d8 100644
@@ -1744,6 +1744,11 @@ int btrfs_qgroup_trace_subtree(struct btrfs_trans_handle *trans,
 
 			btrfs_tree_read_lock(eb);
 			btrfs_set_lock_blocking_rw(eb, BTRFS_READ_LOCK);
+			if (btrfs_verify_first_key(eb, path->nodes[level + 1],
+						   parent_slot)) {
+				ret = -EUCLEAN;
+				goto out;
+			}
 			path->locks[level] = BTRFS_READ_LOCK_BLOCKING;
 
 			ret = btrfs_qgroup_trace_extent(trans, fs_info,

fs/btrfs/ref-verify.c +6 -0

index 6d856eabf34a..b996ca1fd9dc 100644
@@ -593,6 +593,12 @@ static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
 			}
 			btrfs_tree_read_lock(eb);
 			btrfs_set_lock_blocking_rw(eb, BTRFS_READ_LOCK);
+			if (btrfs_verify_first_key(eb, path->nodes[level],
+			    path->slots[level])) {
+				btrfs_tree_read_unlock_blocking(eb);
+				free_extent_buffer(eb);
+				return -EUCLEAN;
+			}
 			path->nodes[level-1] = eb;
 			path->slots[level-1] = 0;
 			path->locks[level-1] = BTRFS_READ_LOCK_BLOCKING;

fs/btrfs/relocation.c +7 -0

index 74db4694d776..74a088fbdac4 100644
@@ -1888,6 +1888,13 @@ int replace_path(struct btrfs_trans_handle *trans,
 				break;
 			}
 			btrfs_tree_lock(eb);
+			if (btrfs_verify_first_key(eb, parent, slot)) {
+				btrfs_tree_unlock(eb);
+				free_extent_buffer(eb);
+				ret = -EUCLEAN;
+				break;
+			}
+
 			if (cow) {
 				ret = btrfs_cow_block(trans, dest, eb, parent,
 						      slot, &eb);

@@ -2793,6 +2800,12 @@ static int do_relocation(struct btrfs_trans_handle *trans,
 		}
 		btrfs_tree_lock(eb);

fs/btrfs/relocation.c static int do_relocation(struct btrfs_trans_handle *trans, · line 2811

Quoted 10 lines

fs/btrfs/relocation.c +6 -0

 		btrfs_set_lock_blocking(eb);
+		if (btrfs_verify_first_key(eb, upper->eb, slot)) {
+			btrfs_tree_unlock(eb);
+			free_extent_buffer(eb);
+			err = -EUCLEAN;
+			goto next;
+		}
 
 		if (!node->eb) {
 			ret = btrfs_cow_block(trans, root, eb, upper->eb,

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

The original first key check is handled in btree_read_extent_buffer_pages(), which is good enough for level check, but to verify first key, we need at least read lock on the extent buffer, or we can hit some race and cause false alert.

Fix it by adding new verifcation function: btrfs_verify_first_key(), which will first check lock context of both parent and child extent buffer, and only when we have proper lock hold (write or read lock if extent buffer is not in commit root) we will verify the first key.

Most of the verification happens in ctree.c after function call like read_tree_block(), read_node_slot() and read_block_for_search(), and only call btrfs_verify_first_key() after we acquire read/write lock.

Also, since first_key check is not as good as level and could easily trigger false alerts due to lock context, put it under CONFIG_BTRFS_FS_CHECK_INTEGRITY to avoid damage to end user.

Signed-off-by Qu Wenruo <[email protected]>

---
 fs/btrfs/ctree.c       | 69 ++++++++++++++++++++++++++++++++++++++++++
 fs/btrfs/ctree.h       | 58 +++++++++++++++++++++++++++++++++++
 fs/btrfs/extent-tree.c |  6 ++++
 fs/btrfs/qgroup.c      |  5 +++
 fs/btrfs/ref-verify.c  |  6 ++++
 fs/btrfs/relocation.c  | 13 ++++++++
 6 files changed, 157 insertions(+)

fs/btrfs/ctree.c +69 -0

index e044b51a2789..57721aead371 100644
@@ -1649,6 +1649,11 @@ int btrfs_realloc_node(struct btrfs_trans_handle *trans,
 
 		btrfs_tree_lock(cur);
 		btrfs_set_lock_blocking(cur);
+		if (btrfs_verify_first_key(cur, parent, i)) {
+			err = -EUCLEAN;
+			btrfs_tree_unlock(cur);
+			free_extent_buffer(cur);
+		}
 		err = __btrfs_cow_block(trans, root, cur, parent, i,
 					&cur, search_start,
 					min(16 * blocksize,

@@ -1863,6 +1868,12 @@ static noinline int balance_level(struct btrfs_trans_handle *trans,
 
 		btrfs_tree_lock(child);
 		btrfs_set_lock_blocking(child);
+		if (btrfs_verify_first_key(child, mid, 0)) {
+			ret = -EUCLEAN;
+			btrfs_tree_unlock(child);
+			free_extent_buffer(child);
+			goto enospc;
+		}
 		ret = btrfs_cow_block(trans, root, child, mid, 0, &child);
 		if (ret) {
 			btrfs_tree_unlock(child);

@@ -1901,6 +1912,10 @@ static noinline int balance_level(struct btrfs_trans_handle *trans,
 	if (left) {
 		btrfs_tree_lock(left);
 		btrfs_set_lock_blocking(left);
+		if (btrfs_verify_first_key(left, parent, pslot - 1)) {
+			ret = -EUCLEAN;
+			goto enospc;
+		}
 		wret = btrfs_cow_block(trans, root, left,
 				       parent, pslot - 1, &left);
 		if (wret) {

@@ -1916,6 +1931,10 @@ static noinline int balance_level(struct btrfs_trans_handle *trans,
 	if (right) {
 		btrfs_tree_lock(right);
 		btrfs_set_lock_blocking(right);
+		if (btrfs_verify_first_key(right, parent, pslot + 1)) {
+			ret = -EUCLEAN;
+			goto enospc;
+		}
 		wret = btrfs_cow_block(trans, root, right,
 				       parent, pslot + 1, &right);
 		if (wret) {

@@ -2079,6 +2098,8 @@ static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
 
 		btrfs_tree_lock(left);
 		btrfs_set_lock_blocking(left);
+		if (btrfs_verify_first_key(left, parent, pslot - 1))
+			goto left_out;
 
 		left_nr = btrfs_header_nritems(left);
 		if (left_nr >= BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 1) {

@@ -2119,6 +2140,7 @@ static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
 			}
 			return 0;
 		}
+left_out:
 		btrfs_tree_unlock(left);
 		free_extent_buffer(left);
 	}

@@ -2134,6 +2156,8 @@ static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
 
 		btrfs_tree_lock(right);
 		btrfs_set_lock_blocking(right);
+		if (btrfs_verify_first_key(right, parent, pslot + 1))
+			goto right_out;
 
 		right_nr = btrfs_header_nritems(right);
 		if (right_nr >= BTRFS_NODEPTRS_PER_BLOCK(fs_info) - 1) {

@@ -2174,6 +2198,7 @@ static noinline int push_nodes_for_insert(struct btrfs_trans_handle *trans,
 			}
 			return 0;
 		}
+right_out:
 		btrfs_tree_unlock(right);
 		free_extent_buffer(right);
 	}

@@ -2868,6 +2893,11 @@ int btrfs_search_slot(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 					p->locks[level] = BTRFS_READ_LOCK;
 				}
 				p->nodes[level] = b;
+				if (btrfs_verify_first_key(b, p->nodes[level + 1],
+							   slot)) {
+					ret = -EUCLEAN;
+					goto done;
+				}
 			}
 		} else {
 			p->slots[level] = slot;

@@ -2981,6 +3011,12 @@ int btrfs_search_old_slot(struct btrfs_root *root, const struct btrfs_key *key,
 				goto done;
 			}
 
+			/*
+			 * NOTE: both parent and child go through
+			 * tree_mod_log_rewind(), first key check is no
+			 * longer consistent. So no btrfs_verify_first_key()
+			 * for this read_block_for_search().
+			 */
 			err = read_block_for_search(root, p, &b, level,
 						    slot, key);
 			if (err == -EAGAIN)

@@ -3753,6 +3789,8 @@ static int push_leaf_right(struct btrfs_trans_handle *trans, struct btrfs_root
 
 	btrfs_tree_lock(right);
 	btrfs_set_lock_blocking(right);
+	if (btrfs_verify_first_key(right, upper, slot + 1))
+		goto out_unlock;
 
 	free_space = btrfs_leaf_free_space(fs_info, right);
 	if (free_space < data_size)

@@ -3987,6 +4025,10 @@ static int push_leaf_left(struct btrfs_trans_handle *trans, struct btrfs_root
 
 	btrfs_tree_lock(left);
 	btrfs_set_lock_blocking(left);
+	if (btrfs_verify_first_key(left, path->nodes[1], slot - 1)) {
+		ret = 1;
+		goto out;
+	}
 
 	free_space = btrfs_leaf_free_space(fs_info, left);
 	if (free_space < data_size) {

@@ -5205,6 +5247,12 @@ int btrfs_search_forward(struct btrfs_root *root, struct btrfs_key *min_key,
 		}
 
 		btrfs_tree_read_lock(cur);
+		if (btrfs_verify_first_key(cur, path->nodes[level], slot)) {
+			btrfs_tree_read_unlock(cur);
+			free_extent_buffer(cur);
+			ret = -EUCLEAN;
+			goto out;
+		}
 
 		path->locks[level - 1] = BTRFS_READ_LOCK;
 		path->nodes[level - 1] = cur;

@@ -5232,6 +5280,11 @@ static int tree_move_down(struct btrfs_fs_info *fs_info,
 	if (IS_ERR(eb))
 		return PTR_ERR(eb);
 
+	if (btrfs_verify_first_key(eb, path->nodes[*level],
+				   path->slots[*level])) {
+		free_extent_buffer(eb);
+		return -EUCLEAN;
+	}
 	path->nodes[*level - 1] = eb;
 	path->slots[*level - 1] = 0;
 	(*level)--;

@@ -5786,6 +5839,14 @@ int btrfs_next_old_leaf(struct btrfs_root *root, struct btrfs_path *path,
 							  BTRFS_READ_LOCK);
 			}
 			next_rw_lock = BTRFS_READ_LOCK;
+			if (btrfs_verify_first_key(next, path->nodes[level],
+						   slot)) {
+				ret = -EUCLEAN;
+				btrfs_tree_read_unlock(next);
+				free_extent_buffer(next);
+				btrfs_release_path(path);
+				goto done;
+			}
 		}
 		break;
 	}

@@ -5823,6 +5884,14 @@ int btrfs_next_old_leaf(struct btrfs_root *root, struct btrfs_path *path,
 							  BTRFS_READ_LOCK);
 			}
 			next_rw_lock = BTRFS_READ_LOCK;
+			if (btrfs_verify_first_key(next, path->nodes[level],
+						   0)) {
+				ret = -EUCLEAN;
+				btrfs_tree_read_unlock(next);
+				free_extent_buffer(next);
+				btrfs_release_path(path);
+				goto done;
+			}
 		}
 	}
 	ret = 0;

fs/btrfs/ctree.h +1 -0

index 0eb55825862a..033d8ae027c3 100644
@@ -44,6 +44,7 @@
 #include "extent_io.h"
 #include "extent_map.h"
 #include "async-thread.h"
+#include "print-tree.h"
 
 struct btrfs_trans_handle;
 struct btrfs_transaction;

@@ -3752,4 +3753,61 @@ static inline int btrfs_is_testing(struct btrfs_fs_info *fs_info)
 #endif
 	return 0;

When looping btrfs/074 with many cpus (>= 8), it's possible to trigger kernel warning due to first key verification:

[ 4239.523446] WARNING: CPU: 5 PID: 2381 at fs/btrfs/disk-io.c:460 btree_read_extent_buffer_pages+0x1ad/0x210
[ 4239.523830] Modules linked in:
[ 4239.524630] RIP: 0010:btree_read_extent_buffer_pages+0x1ad/0x210
[ 4239.527101] Call Trace:
[ 4239.527251]  read_tree_block+0x42/0x70
[ 4239.527434]  read_node_slot+0xd2/0x110
[ 4239.527632]  push_leaf_right+0xad/0x1b0
[ 4239.527809]  split_leaf+0x4ea/0x700
[ 4239.527988]  ? leaf_space_used+0xbc/0xe0
[ 4239.528192]  ? btrfs_set_lock_blocking_rw+0x99/0xb0
[ 4239.528416]  btrfs_search_slot+0x8cc/0xa40
[ 4239.528605]  btrfs_insert_empty_items+0x71/0xc0
[ 4239.528798]  __btrfs_run_delayed_refs+0xa98/0x1680
[ 4239.529013]  btrfs_run_delayed_refs+0x10b/0x1b0
[ 4239.529205]  btrfs_commit_transaction+0x33/0xaf0
[ 4239.529445]  ? start_transaction+0xa8/0x4f0
[ 4239.529630]  btrfs_alloc_data_chunk_ondemand+0x1b0/0x4e0
[ 4239.529833]  btrfs_check_data_free_space+0x54/0xa0
[ 4239.530045]  btrfs_delalloc_reserve_space+0x25/0x70
[ 4239.531907]  btrfs_direct_IO+0x233/0x3d0
[ 4239.532098]  generic_file_direct_write+0xcb/0x170
[ 4239.532296]  btrfs_file_write_iter+0x2bb/0x5f4
[ 4239.532491]  aio_write+0xe2/0x180
[ 4239.532669]  ? lock_acquire+0xac/0x1e0
[ 4239.532839]  ? __might_fault+0x3e/0x90
[ 4239.533032]  do_io_submit+0x594/0x860
[ 4239.533223]  ? do_io_submit+0x594/0x860
[ 4239.533398]  SyS_io_submit+0x10/0x20
[ 4239.533560]  ? SyS_io_submit+0x10/0x20
[ 4239.533729]  do_syscall_64+0x75/0x1d0
[ 4239.533979]  entry_SYSCALL_64_after_hwframe+0x42/0xb7
[ 4239.534182] RIP: 0033:0x7f8519741697

The possibility is low, around 4~7/128 runs with 8 cores. The problem here is, at btree_read_extent_buffer_pages() we don't have acquired read/write lock on that extent buffer, only basic info like level/bytenr is reliable.

To get correct first key, we must require at least read lock for that extent buffer, which can't be done in btree_read_extent_buffer_pages(), but deep into core btree operation code.

This patch will remove the unreliable first key check to avoid false alerts, and allow later patch to re-implement first key check correctly.

Quoted 45 lines · Qu Wenruo

When looping btrfs/074 with many cpus (>= 8), it's possible to trigger kernel warning due to first key verification:

[ 4239.523446] WARNING: CPU: 5 PID: 2381 at fs/btrfs/disk-io.c:460 btree_read_extent_buffer_pages+0x1ad/0x210
[ 4239.523830] Modules linked in:
[ 4239.524630] RIP: 0010:btree_read_extent_buffer_pages+0x1ad/0x210
[ 4239.527101] Call Trace:
[ 4239.527251]  read_tree_block+0x42/0x70
[ 4239.527434]  read_node_slot+0xd2/0x110
[ 4239.527632]  push_leaf_right+0xad/0x1b0
[ 4239.527809]  split_leaf+0x4ea/0x700
[ 4239.527988]  ? leaf_space_used+0xbc/0xe0
[ 4239.528192]  ? btrfs_set_lock_blocking_rw+0x99/0xb0
[ 4239.528416]  btrfs_search_slot+0x8cc/0xa40
[ 4239.528605]  btrfs_insert_empty_items+0x71/0xc0
[ 4239.528798]  __btrfs_run_delayed_refs+0xa98/0x1680
[ 4239.529013]  btrfs_run_delayed_refs+0x10b/0x1b0
[ 4239.529205]  btrfs_commit_transaction+0x33/0xaf0
[ 4239.529445]  ? start_transaction+0xa8/0x4f0
[ 4239.529630]  btrfs_alloc_data_chunk_ondemand+0x1b0/0x4e0
[ 4239.529833]  btrfs_check_data_free_space+0x54/0xa0
[ 4239.530045]  btrfs_delalloc_reserve_space+0x25/0x70
[ 4239.531907]  btrfs_direct_IO+0x233/0x3d0
[ 4239.532098]  generic_file_direct_write+0xcb/0x170
[ 4239.532296]  btrfs_file_write_iter+0x2bb/0x5f4
[ 4239.532491]  aio_write+0xe2/0x180
[ 4239.532669]  ? lock_acquire+0xac/0x1e0
[ 4239.532839]  ? __might_fault+0x3e/0x90
[ 4239.533032]  do_io_submit+0x594/0x860
[ 4239.533223]  ? do_io_submit+0x594/0x860
[ 4239.533398]  SyS_io_submit+0x10/0x20
[ 4239.533560]  ? SyS_io_submit+0x10/0x20
[ 4239.533729]  do_syscall_64+0x75/0x1d0
[ 4239.533979]  entry_SYSCALL_64_after_hwframe+0x42/0xb7
[ 4239.534182] RIP: 0033:0x7f8519741697

The possibility is low, around 4~7/128 runs with 8 cores. The problem here is, at btree_read_extent_buffer_pages() we don't have acquired read/write lock on that extent buffer, only basic info like level/bytenr is reliable.

To get correct first key, we must require at least read lock for that extent buffer, which can't be done in btree_read_extent_buffer_pages(), but deep into core btree operation code.

Quoted 2 lines

This patch will remove the unreliable first key check to avoid false alerts, and allow later patch to re-implement first key check correctly.

We'll have to disable the first key check in a less intrusive way, eg. taking a shortcut in verify_level_key.

The patch has was added in
recent pull, I'm not going to do full a revert now.

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html