[PATCH v2 0/4] btrfs: some cleanups for two ctree functions

[PATCH v2 0/4] btrfs: some cleanups for two ctree functions

[Sun YangKai]

The first three patches is cleanups for btrfs_search_slot_for_read().
There're only two callers that set @return_any to 1 and both of them
is unnecessary. So @return_any and related logic could be removed.

The last patch is cleanup for btrfs_prev_leaf(). Callers expect a
valid p->slots[0] to read the item's key. So make sure btrfs_prev_leaf()
return a valid p->slots[0] and remove related checks in callers.

No functional changes.

Changelog:
V2:

- Add assertion in btrfs_search_slot_for_read() to prevent misuse
- Remove unnecessary call btrfs_prev_leaf in btrfs_search_slot_for_read()
- Add details about changes in patch 4

Sun YangKai (4):
  btrfs: don't set @return_any for btrfs_search_slot_for_read in
    btrfs_read_qgroup_config
  btrfs: don't set return_any @return_any for btrfs_search_slot_for_read
    in get_last_extent()
  btrfs: cleanup btrfs_search_slot_for_read()
  btrfs: ctree: cleanup btrfs_prev_leaf()

 fs/btrfs/ctree.c           | 143 +++++++------------------------------
 fs/btrfs/ctree.h           |   3 +-
 fs/btrfs/free-space-tree.c |   2 +-
 fs/btrfs/qgroup.c          |  10 +--
 fs/btrfs/send.c            |  22 +++---
 5 files changed, 42 insertions(+), 138 deletions(-)

-- 
2.51.2

[PATCH v2 1/4] btrfs: don't set @return_any for btrfs_search_slot_for_read in btrfs_read_qgroup_config

[Sun YangKai]

The call to `btrfs_search_slot_for_read` in `btrfs_read_qgroup_config` is
intended to find the very first item in the quota root tree to initiate
iteration.

The search key is set to all zeros: (0, 0, 0).

The current call uses `return_any=1`:
`btrfs_search_slot_for_read(..., find_higher=1, return_any=1)`

With `find_higher=1`, the function searches for an item greater than
(0, 0, 0). The `return_any=1` flag provides a fallback: if no higher item
is found, it attempts to return the next lower item instead.

Since the search key (0, 0, 0) represents the absolute floor of the btrfs
key space (u64 objectid), there can be no valid key lower than it. The
`return_any` fallback logic is therefore pointless and misleading in
this context.

Change `return_any` from `1` to `0` to correctly express the intention:
find the first item strictly higher than (0, 0, 0), and if no such item
exists, simply return 'not found' (1) without attempting an unnecessary
and impossible search for a lower key.

Signed-off-by: Sun YangKai <sunk67188@gmail.com>
---
 fs/btrfs/qgroup.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/fs/btrfs/qgroup.c b/fs/btrfs/qgroup.c
index 9e2b53e90dcb..d780980e6790 100644
--- a/fs/btrfs/qgroup.c
+++ b/fs/btrfs/qgroup.c
@@ -415,7 +415,7 @@ int btrfs_read_qgroup_config(struct btrfs_fs_info *fs_info)
 	key.objectid = 0;
 	key.type = 0;
 	key.offset = 0;
-	ret = btrfs_search_slot_for_read(quota_root, &key, path, 1, 1);
+	ret = btrfs_search_slot_for_read(quota_root, &key, path, 1, 0);
 	if (ret)
 		goto out;
 
-- 
2.51.2

[PATCH v2 2/4] btrfs: don't set return_any @return_any for btrfs_search_slot_for_read in get_last_extent()

[Sun YangKai]

There must be a previous item at least the inode_item. So setting
@return_any is not necessary.

Signed-off-by: Sun YangKai <sunk67188@gmail.com>
---
 fs/btrfs/send.c | 12 +++++-------
 1 file changed, 5 insertions(+), 7 deletions(-)

diff --git a/fs/btrfs/send.c b/fs/btrfs/send.c
index 2522faa97478..eae596b80ec0 100644
--- a/fs/btrfs/send.c
+++ b/fs/btrfs/send.c
@@ -6320,16 +6320,14 @@ static int get_last_extent(struct send_ctx *sctx, u64 offset)
 	key.objectid = sctx->cur_ino;
 	key.type = BTRFS_EXTENT_DATA_KEY;
 	key.offset = offset;
-	ret = btrfs_search_slot_for_read(root, &key, path, 0, 1);
+	ret = btrfs_search_slot_for_read(root, &key, path, 0, 0);
 	if (ret < 0)
 		return ret;
-	ret = 0;
+	ASSERT(ret == 0);
 	btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
-	if (key.objectid != sctx->cur_ino || key.type != BTRFS_EXTENT_DATA_KEY)
-		return ret;
-
-	sctx->cur_inode_last_extent = btrfs_file_extent_end(path);
-	return ret;
+	if (key.objectid == sctx->cur_ino && key.type == BTRFS_EXTENT_DATA_KEY)
+		sctx->cur_inode_last_extent = btrfs_file_extent_end(path);
+	return 0;
 }
 
 static int range_is_hole_in_parent(struct send_ctx *sctx,
-- 
2.51.2

[PATCH v2 3/4] btrfs: cleanup btrfs_search_slot_for_read()

[Sun YangKai]

- Now @return_any is not used by any caller, remove it and related logic.

- @for_read is used as boolean, so convert it from int to bool.

- This function is only meaningful when called with p->lowest_level == 0,
  add assertion for that.

No functional change.

Signed-off-by: Sun YangKai <sunk67188@gmail.com>
---
 fs/btrfs/ctree.c           | 48 +++++++-------------------------------
 fs/btrfs/ctree.h           |  3 +--
 fs/btrfs/free-space-tree.c |  2 +-
 fs/btrfs/qgroup.c          | 10 ++++----
 fs/btrfs/send.c            | 12 +++++-----
 5 files changed, 21 insertions(+), 54 deletions(-)

diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index a48b4befbee7..0a0157db0b0c 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -2450,22 +2450,15 @@ static int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
  * instead the next or previous item should be returned.
  * When find_higher is true, the next higher item is returned, the next lower
  * otherwise.
- * When return_any and find_higher are both true, and no higher item is found,
- * return the next lower instead.
- * When return_any is true and find_higher is false, and no lower item is found,
- * return the next higher instead.
- * It returns 0 if any item is found, 1 if none is found (tree empty), and
- * < 0 on error
+ * It returns 0 if any item is found, 1 if none is found and < 0 on error
  */
 int btrfs_search_slot_for_read(struct btrfs_root *root,
 			       const struct btrfs_key *key,
-			       struct btrfs_path *p, int find_higher,
-			       int return_any)
+			       struct btrfs_path *p, bool find_higher)
 {
 	int ret;
-	struct extent_buffer *leaf;
 
-again:
+	ASSERT(p->lowest_level == 0);
 	ret = btrfs_search_slot(NULL, root, key, p, 0, 0);
 	if (ret <= 0)
 		return ret;
@@ -2476,47 +2469,22 @@ int btrfs_search_slot_for_read(struct btrfs_root *root,
 	 * to the first free slot in the previous leaf, i.e. at an invalid
 	 * item.
 	 */
-	leaf = p->nodes[0];
-
 	if (find_higher) {
-		if (p->slots[0] >= btrfs_header_nritems(leaf)) {
-			ret = btrfs_next_leaf(root, p);
-			if (ret <= 0)
-				return ret;
-			if (!return_any)
-				return 1;
-			/*
-			 * no higher item found, return the next
-			 * lower instead
-			 */
-			return_any = 0;
-			find_higher = 0;
-			btrfs_release_path(p);
-			goto again;
-		}
+		if (p->slots[0] >= btrfs_header_nritems(p->nodes[0]))
+			return btrfs_next_leaf(root, p);
 	} else {
 		if (p->slots[0] == 0) {
 			ret = btrfs_prev_leaf(root, p);
 			if (ret < 0)
 				return ret;
 			if (!ret) {
-				leaf = p->nodes[0];
-				if (p->slots[0] == btrfs_header_nritems(leaf))
+				if (p->slots[0] == btrfs_header_nritems(p->nodes[0]))
 					p->slots[0]--;
 				return 0;
 			}
-			if (!return_any)
-				return 1;
-			/*
-			 * no lower item found, return the next
-			 * higher instead
-			 */
-			return_any = 0;
-			find_higher = 1;
-			btrfs_release_path(p);
-			goto again;
+			return 1;
 		} else {
-			--p->slots[0];
+			p->slots[0]--;
 		}
 	}
 	return 0;
diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 692370fc07b2..4b7b8ce7e211 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -595,8 +595,7 @@ int btrfs_search_old_slot(struct btrfs_root *root, const struct btrfs_key *key,
 			  struct btrfs_path *p, u64 time_seq);
 int btrfs_search_slot_for_read(struct btrfs_root *root,
 			       const struct btrfs_key *key,
-			       struct btrfs_path *p, int find_higher,
-			       int return_any);
+			       struct btrfs_path *p, bool find_higher);
 void btrfs_release_path(struct btrfs_path *p);
 struct btrfs_path *btrfs_alloc_path(void);
 void btrfs_free_path(struct btrfs_path *p);
diff --git a/fs/btrfs/free-space-tree.c b/fs/btrfs/free-space-tree.c
index 1ad2ad384b9e..88c46950f5d2 100644
--- a/fs/btrfs/free-space-tree.c
+++ b/fs/btrfs/free-space-tree.c
@@ -1089,7 +1089,7 @@ static int populate_free_space_tree(struct btrfs_trans_handle *trans,
 	key.offset = 0;
 
 	extent_root = btrfs_extent_root(trans->fs_info, key.objectid);
-	ret = btrfs_search_slot_for_read(extent_root, &key, path, 1, 0);
+	ret = btrfs_search_slot_for_read(extent_root, &key, path, true);
 	if (ret < 0)
 		goto out_locked;
 	/*
diff --git a/fs/btrfs/qgroup.c b/fs/btrfs/qgroup.c
index d780980e6790..bd458ba537ba 100644
--- a/fs/btrfs/qgroup.c
+++ b/fs/btrfs/qgroup.c
@@ -415,7 +415,7 @@ int btrfs_read_qgroup_config(struct btrfs_fs_info *fs_info)
 	key.objectid = 0;
 	key.type = 0;
 	key.offset = 0;
-	ret = btrfs_search_slot_for_read(quota_root, &key, path, 1, 0);
+	ret = btrfs_search_slot_for_read(quota_root, &key, path, true);
 	if (ret)
 		goto out;
 
@@ -530,7 +530,7 @@ int btrfs_read_qgroup_config(struct btrfs_fs_info *fs_info)
 	key.objectid = 0;
 	key.type = BTRFS_QGROUP_RELATION_KEY;
 	key.offset = 0;
-	ret = btrfs_search_slot_for_read(quota_root, &key, path, 1, 0);
+	ret = btrfs_search_slot_for_read(quota_root, &key, path, true);
 	if (ret)
 		goto out;
 	while (1) {
@@ -1088,7 +1088,7 @@ int btrfs_quota_enable(struct btrfs_fs_info *fs_info,
 	key.offset = 0;
 
 	btrfs_release_path(path);
-	ret = btrfs_search_slot_for_read(tree_root, &key, path, 1, 0);
+	ret = btrfs_search_slot_for_read(tree_root, &key, path, true);
 	if (ret > 0)
 		goto out_add_root;
 	if (unlikely(ret < 0)) {
@@ -1130,7 +1130,7 @@ int btrfs_quota_enable(struct btrfs_fs_info *fs_info,
 				goto out_free_path;
 			}
 			ret = btrfs_search_slot_for_read(tree_root, &found_key,
-							 path, 1, 0);
+							 path, true);
 			if (unlikely(ret < 0)) {
 				btrfs_abort_transaction(trans, ret);
 				goto out_free_path;
@@ -3692,7 +3692,7 @@ static int qgroup_rescan_leaf(struct btrfs_trans_handle *trans,
 				fs_info->qgroup_rescan_progress.objectid);
 	ret = btrfs_search_slot_for_read(extent_root,
 					 &fs_info->qgroup_rescan_progress,
-					 path, 1, 0);
+					 path, true);
 
 	btrfs_debug(fs_info,
 		    "current progress key " BTRFS_KEY_FMT ", search_slot ret %d",
diff --git a/fs/btrfs/send.c b/fs/btrfs/send.c
index eae596b80ec0..471e81a8e844 100644
--- a/fs/btrfs/send.c
+++ b/fs/btrfs/send.c
@@ -1234,7 +1234,7 @@ static int get_inode_path(struct btrfs_root *root,
 	key.type = BTRFS_INODE_REF_KEY;
 	key.offset = 0;
 
-	ret = btrfs_search_slot_for_read(root, &key, p, 1, 0);
+	ret = btrfs_search_slot_for_read(root, &key, p, true);
 	if (ret < 0)
 		return ret;
 	if (ret)
@@ -1979,7 +1979,7 @@ static int get_first_ref(struct btrfs_root *root, u64 ino,
 	key.type = BTRFS_INODE_REF_KEY;
 	key.offset = 0;
 
-	ret = btrfs_search_slot_for_read(root, &key, path, 1, 0);
+	ret = btrfs_search_slot_for_read(root, &key, path, true);
 	if (ret < 0)
 		return ret;
 	if (!ret)
@@ -2475,7 +2475,7 @@ static int send_subvol_begin(struct send_ctx *sctx)
 	key.offset = 0;
 
 	ret = btrfs_search_slot_for_read(send_root->fs_info->tree_root,
-				&key, path, 1, 0);
+				&key, path, true);
 	if (ret < 0)
 		return ret;
 	if (ret)
@@ -6195,7 +6195,7 @@ static int is_extent_unchanged(struct send_ctx *sctx,
 	key.objectid = ekey->objectid;
 	key.type = BTRFS_EXTENT_DATA_KEY;
 	key.offset = ekey->offset;
-	ret = btrfs_search_slot_for_read(sctx->parent_root, &key, path, 0, 0);
+	ret = btrfs_search_slot_for_read(sctx->parent_root, &key, path, false);
 	if (ret < 0)
 		return ret;
 	if (ret)
@@ -6320,7 +6320,7 @@ static int get_last_extent(struct send_ctx *sctx, u64 offset)
 	key.objectid = sctx->cur_ino;
 	key.type = BTRFS_EXTENT_DATA_KEY;
 	key.offset = offset;
-	ret = btrfs_search_slot_for_read(root, &key, path, 0, 0);
+	ret = btrfs_search_slot_for_read(root, &key, path, false);
 	if (ret < 0)
 		return ret;
 	ASSERT(ret == 0);
@@ -7288,7 +7288,7 @@ static int full_send_tree(struct send_ctx *sctx)
 	sctx->last_reloc_trans = fs_info->last_reloc_trans;
 	up_read(&fs_info->commit_root_sem);
 
-	ret = btrfs_search_slot_for_read(send_root, &key, path, 1, 0);
+	ret = btrfs_search_slot_for_read(send_root, &key, path, true);
 	if (ret < 0)
 		return ret;
 	if (ret)
-- 
2.51.2

[PATCH v2 4/4] btrfs: ctree: cleanup btrfs_prev_leaf()

[Sun YangKai]

There's a common parttern in callers of btrfs_prev_leaf:
p->slots[0]-- if p->slots[0] points to a slot with invalid item(nritem).

So just make btrfs_prev_leaf() ensure that path->slots[0] points to a
valid slot and cleanup its over complex logic.

And then remove the related logic and cleanup the callers.

This will make things much simpler.

No functional changes.

A. Details about changes in callers:

ASSERT(path->slots[0] < btrfs_header_nritems(path->nodes[0])) in callers
is enough to make sure that nritems != 0 and slots[0] points to a valid
btrfs_item.

And getting a `nritems==0` when btrfs_prev_leaf() returns 0 is a logic
error because btrfs_pref_leaf() should always

1. either find a non-empty leaf
2. or return 1

So we can use ASSERT safely here.

B. Details about cleanup of btrfs_prev_leaf().

The previous implementation works like this:

0) Get a previous key by "dec by 1" of the original key. Let's call it
   search key. It's obvious that search key is less than original key
   and there's no key between them.

1) Call btrfs_search_slot() with search key.

2) If we got an error or an exact match, early return.

3) If p->slots[0] points to the original item, p->slots[0]-- to make sure
   that we will not return the same item again. This may happen because
   there might be some tree balancing happened so the original item is no
   longer at slot 0.

4) Check if the key of the item at slot 0 is (less than the original key
   / less than or equal to search key) to verify if we got a previous leaf.

However, 3) and 4) are over complex. We only need to check if
p->slots[0] == 0 because:

3a) If p->slots[0] == 0, there's no key less than or equal to search key
    in the tree, which means the original key is lowest in the tree. In
    this case, there's no previous leaf, we should return 1.

3b) If p->slots[0] != 0, using p->slots[0]-- is enough to get a valid
    previous item neither missing anything nor return the original item
    again because:

    i) p->slots[0] == nritems, which means all keys in the leaf are less
       than search key so the leaf is a previous leaf. We only need to
       p->slots[0]-- to get a valid previous item.

    ii) p->slots[0] < nritems, p->slots[0] points to an item whose key
        is greater than search key(probably the original item if it was
        not deleted), and p->slots[0] - 1 points to an item whose key is
        less than search key. So use p->slots[0]-- to get the previous
        item and we will neigher miss anything nor return the original
        item again. This handles the case 3) in original implementation.

Signed-off-by: Sun YangKai <sunk67188@gmail.com>
---
 fs/btrfs/ctree.c | 99 ++++++++++--------------------------------------
 1 file changed, 19 insertions(+), 80 deletions(-)

diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
index 0a0157db0b0c..3026d956c7fb 100644
--- a/fs/btrfs/ctree.c
+++ b/fs/btrfs/ctree.c
@@ -2376,12 +2376,9 @@ int btrfs_search_old_slot(struct btrfs_root *root, const struct btrfs_key *key,
 static int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
 {
 	struct btrfs_key key;
-	struct btrfs_key orig_key;
-	struct btrfs_disk_key found_key;
 	int ret;
 
 	btrfs_item_key_to_cpu(path->nodes[0], &key, 0);
-	orig_key = key;
 
 	if (key.offset > 0) {
 		key.offset--;
@@ -2401,48 +2398,12 @@ static int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
 	if (ret <= 0)
 		return ret;
 
-	/*
-	 * Previous key not found. Even if we were at slot 0 of the leaf we had
-	 * before releasing the path and calling btrfs_search_slot(), we now may
-	 * be in a slot pointing to the same original key - this can happen if
-	 * after we released the path, one of more items were moved from a
-	 * sibling leaf into the front of the leaf we had due to an insertion
-	 * (see push_leaf_right()).
-	 * If we hit this case and our slot is > 0 and just decrement the slot
-	 * so that the caller does not process the same key again, which may or
-	 * may not break the caller, depending on its logic.
-	 */
-	if (path->slots[0] < btrfs_header_nritems(path->nodes[0])) {
-		btrfs_item_key(path->nodes[0], &found_key, path->slots[0]);
-		ret = btrfs_comp_keys(&found_key, &orig_key);
-		if (ret == 0) {
-			if (path->slots[0] > 0) {
-				path->slots[0]--;
-				return 0;
-			}
-			/*
-			 * At slot 0, same key as before, it means orig_key is
-			 * the lowest, leftmost, key in the tree. We're done.
-			 */
-			return 1;
-		}
-	}
+	/* There's no smaller keys in the whole tree. */
+	if (path->slots[0] == 0)
+		return 1;
 
-	btrfs_item_key(path->nodes[0], &found_key, 0);
-	ret = btrfs_comp_keys(&found_key, &key);
-	/*
-	 * We might have had an item with the previous key in the tree right
-	 * before we released our path. And after we released our path, that
-	 * item might have been pushed to the first slot (0) of the leaf we
-	 * were holding due to a tree balance. Alternatively, an item with the
-	 * previous key can exist as the only element of a leaf (big fat item).
-	 * Therefore account for these 2 cases, so that our callers (like
-	 * btrfs_previous_item) don't miss an existing item with a key matching
-	 * the previous key we computed above.
-	 */
-	if (ret <= 0)
-		return 0;
-	return 1;
+	path->slots[0]--;
+	return 0;
 }
 
 /*
@@ -2473,19 +2434,11 @@ int btrfs_search_slot_for_read(struct btrfs_root *root,
 		if (p->slots[0] >= btrfs_header_nritems(p->nodes[0]))
 			return btrfs_next_leaf(root, p);
 	} else {
-		if (p->slots[0] == 0) {
-			ret = btrfs_prev_leaf(root, p);
-			if (ret < 0)
-				return ret;
-			if (!ret) {
-				if (p->slots[0] == btrfs_header_nritems(p->nodes[0]))
-					p->slots[0]--;
-				return 0;
-			}
+		/* We have no lower key in the tree. */
+		if (p->slots[0] == 0)
 			return 1;
-		} else {
-			p->slots[0]--;
-		}
+
+		p->slots[0]--;
 	}
 	return 0;
 }
@@ -4969,26 +4922,19 @@ int btrfs_previous_item(struct btrfs_root *root,
 			int type)
 {
 	struct btrfs_key found_key;
-	struct extent_buffer *leaf;
-	u32 nritems;
 	int ret;
 
 	while (1) {
 		if (path->slots[0] == 0) {
 			ret = btrfs_prev_leaf(root, path);
-			if (ret != 0)
+			if (ret)
 				return ret;
-		} else {
-			path->slots[0]--;
-		}
-		leaf = path->nodes[0];
-		nritems = btrfs_header_nritems(leaf);
-		if (nritems == 0)
-			return 1;
-		if (path->slots[0] == nritems)
+		} else
 			path->slots[0]--;
 
-		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
+		ASSERT(path->slots[0] < btrfs_header_nritems(path->nodes[0]));
+
+		btrfs_item_key_to_cpu(path->nodes[0], &found_key, path->slots[0]);
 		if (found_key.objectid < min_objectid)
 			break;
 		if (found_key.type == type)
@@ -5010,26 +4956,19 @@ int btrfs_previous_extent_item(struct btrfs_root *root,
 			struct btrfs_path *path, u64 min_objectid)
 {
 	struct btrfs_key found_key;
-	struct extent_buffer *leaf;
-	u32 nritems;
 	int ret;
 
 	while (1) {
 		if (path->slots[0] == 0) {
 			ret = btrfs_prev_leaf(root, path);
-			if (ret != 0)
+			if (ret)
 				return ret;
-		} else {
-			path->slots[0]--;
-		}
-		leaf = path->nodes[0];
-		nritems = btrfs_header_nritems(leaf);
-		if (nritems == 0)
-			return 1;
-		if (path->slots[0] == nritems)
+		} else
 			path->slots[0]--;
 
-		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
+		ASSERT(path->slots[0] < btrfs_header_nritems(path->nodes[0]));
+
+		btrfs_item_key_to_cpu(path->nodes[0], &found_key, path->slots[0]);
 		if (found_key.objectid < min_objectid)
 			break;
 		if (found_key.type == BTRFS_EXTENT_ITEM_KEY ||
-- 
2.51.2

Re: [PATCH v2 4/4] btrfs: ctree: cleanup btrfs_prev_leaf()

[Qu Wenruo]

在 2025/12/11 17:52, Sun YangKai 写道:
> There's a common parttern in callers of btrfs_prev_leaf:
> p->slots[0]-- if p->slots[0] points to a slot with invalid item(nritem).
> 
> So just make btrfs_prev_leaf() ensure that path->slots[0] points to a
> valid slot and cleanup its over complex logic.
> 
> And then remove the related logic and cleanup the callers.
> 
> This will make things much simpler.
> 
> No functional changes.
> 
> A. Details about changes in callers:
> 
> ASSERT(path->slots[0] < btrfs_header_nritems(path->nodes[0])) in callers
> is enough to make sure that nritems != 0 and slots[0] points to a valid
> btrfs_item.

I don't think the change is safe.

There are callers doing proper checks for empty trees, e.g. 
btrfs_previous_extent_item() and btrfs_previous_item(), now you will 
just ignore that for kernels without CONFIG_BTRFS_ASSERT, or crash the 
kernel if CONFIG_BTRFS_ASSERT is selected.

If you're just cleaning up btrfs_prev_leaf(), then you should keep the 
callers the same without changing their behaviors.

I think there may be some corner case races when tree deleting and some 
other work are happening at the same time.

> 
> And getting a `nritems==0` when btrfs_prev_leaf() returns 0 is a logic
> error because btrfs_pref_leaf() should always
> 
> 1. either find a non-empty leaf

Nope, there is no such guarantee in the first place.
btrfs_prev_leaf() will unlock the path, thus all kinds of modification 
can happen between btrfs_release_path() and btrfs_search_slot().

This assumption is just wrong.

> 2. or return 1
> 
> So we can use ASSERT safely here.
> 
> B. Details about cleanup of btrfs_prev_leaf().
> 
> The previous implementation works like this:
> 
> 0) Get a previous key by "dec by 1" of the original key. Let's call it
>     search key. It's obvious that search key is less than original key
>     and there's no key between them.
> 
> 1) Call btrfs_search_slot() with search key.
> 
> 2) If we got an error or an exact match, early return.
> 
> 3) If p->slots[0] points to the original item, p->slots[0]-- to make sure
>     that we will not return the same item again. This may happen because
>     there might be some tree balancing happened so the original item is no
>     longer at slot 0.
> 
> 4) Check if the key of the item at slot 0 is (less than the original key
>     / less than or equal to search key) to verify if we got a previous leaf.
> 
> However, 3) and 4) are over complex. We only need to check if
> p->slots[0] == 0 because:
> 
> 3a) If p->slots[0] == 0, there's no key less than or equal to search key
>      in the tree, which means the original key is lowest in the tree. In
>      this case, there's no previous leaf, we should return 1.
> 
> 3b) If p->slots[0] != 0, using p->slots[0]-- is enough to get a valid
>      previous item neither missing anything nor return the original item
>      again because:
> 
>      i) p->slots[0] == nritems, which means all keys in the leaf are less
>         than search key so the leaf is a previous leaf. We only need to
>         p->slots[0]-- to get a valid previous item.
> 
>      ii) p->slots[0] < nritems, p->slots[0] points to an item whose key
>          is greater than search key(probably the original item if it was
>          not deleted), and p->slots[0] - 1 points to an item whose key is
>          less than search key. So use p->slots[0]-- to get the previous
>          item and we will neigher miss anything nor return the original
>          item again. This handles the case 3) in original implementation.
> 
> Signed-off-by: Sun YangKai <sunk67188@gmail.com>
> ---
>   fs/btrfs/ctree.c | 99 ++++++++++--------------------------------------
>   1 file changed, 19 insertions(+), 80 deletions(-)
> 
> diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
> index 0a0157db0b0c..3026d956c7fb 100644
> --- a/fs/btrfs/ctree.c
> +++ b/fs/btrfs/ctree.c
> @@ -2376,12 +2376,9 @@ int btrfs_search_old_slot(struct btrfs_root *root, const struct btrfs_key *key,
>   static int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
>   {
>   	struct btrfs_key key;
> -	struct btrfs_key orig_key;
> -	struct btrfs_disk_key found_key;
>   	int ret;
>   
>   	btrfs_item_key_to_cpu(path->nodes[0], &key, 0);
> -	orig_key = key;
>   
>   	if (key.offset > 0) {
>   		key.offset--;
> @@ -2401,48 +2398,12 @@ static int btrfs_prev_leaf(struct btrfs_root *root, struct btrfs_path *path)
>   	if (ret <= 0)
>   		return ret;
>   
> -	/*
> -	 * Previous key not found. Even if we were at slot 0 of the leaf we had
> -	 * before releasing the path and calling btrfs_search_slot(), we now may
> -	 * be in a slot pointing to the same original key - this can happen if
> -	 * after we released the path, one of more items were moved from a
> -	 * sibling leaf into the front of the leaf we had due to an insertion
> -	 * (see push_leaf_right()).
> -	 * If we hit this case and our slot is > 0 and just decrement the slot
> -	 * so that the caller does not process the same key again, which may or
> -	 * may not break the caller, depending on its logic.
> -	 */

Although the change is mostly fine, if you want to keep the existing 
behavior, you should return 0 for empty tree to keep the old behavior.

Furthermore, you have to explain why it's safe not only in the commit 
message, but also comments.

This not a small change, and very low-level. Just doing black magic is 
not acceptable.

And you need something better than your commit message as comments.

In short, you should:

- Not change the callers

- Better comments

> -	if (path->slots[0] < btrfs_header_nritems(path->nodes[0])) {
> -		btrfs_item_key(path->nodes[0], &found_key, path->slots[0]);
> -		ret = btrfs_comp_keys(&found_key, &orig_key);
> -		if (ret == 0) {
> -			if (path->slots[0] > 0) {
> -				path->slots[0]--;
> -				return 0;
> -			}
> -			/*
> -			 * At slot 0, same key as before, it means orig_key is
> -			 * the lowest, leftmost, key in the tree. We're done.
> -			 */
> -			return 1;
> -		}
> -	}
> +	/* There's no smaller keys in the whole tree. */
> +	if (path->slots[0] == 0)
> +		return 1;
>   
> -	btrfs_item_key(path->nodes[0], &found_key, 0);
> -	ret = btrfs_comp_keys(&found_key, &key);
> -	/*
> -	 * We might have had an item with the previous key in the tree right
> -	 * before we released our path. And after we released our path, that
> -	 * item might have been pushed to the first slot (0) of the leaf we
> -	 * were holding due to a tree balance. Alternatively, an item with the
> -	 * previous key can exist as the only element of a leaf (big fat item).
> -	 * Therefore account for these 2 cases, so that our callers (like
> -	 * btrfs_previous_item) don't miss an existing item with a key matching
> -	 * the previous key we computed above.
> -	 */
> -	if (ret <= 0)
> -		return 0;
> -	return 1;
> +	path->slots[0]--;
> +	return 0;
>   }
>   
>   /*
> @@ -2473,19 +2434,11 @@ int btrfs_search_slot_for_read(struct btrfs_root *root,
>   		if (p->slots[0] >= btrfs_header_nritems(p->nodes[0]))
>   			return btrfs_next_leaf(root, p);
>   	} else {
> -		if (p->slots[0] == 0) {
> -			ret = btrfs_prev_leaf(root, p);
> -			if (ret < 0)
> -				return ret;
> -			if (!ret) {
> -				if (p->slots[0] == btrfs_header_nritems(p->nodes[0]))
> -					p->slots[0]--;
> -				return 0;
> -			}
> +		/* We have no lower key in the tree. */
> +		if (p->slots[0] == 0)
>   			return 1;
> -		} else {
> -			p->slots[0]--;
> -		}
> +
> +		p->slots[0]--;
>   	}
>   	return 0;
>   }
> @@ -4969,26 +4922,19 @@ int btrfs_previous_item(struct btrfs_root *root,
>   			int type)
>   {
>   	struct btrfs_key found_key;
> -	struct extent_buffer *leaf;
> -	u32 nritems;
>   	int ret;
>   
>   	while (1) {
>   		if (path->slots[0] == 0) {
>   			ret = btrfs_prev_leaf(root, path);
> -			if (ret != 0)
> +			if (ret)
>   				return ret;
> -		} else {
> -			path->slots[0]--;
> -		}
> -		leaf = path->nodes[0];
> -		nritems = btrfs_header_nritems(leaf);
> -		if (nritems == 0)
> -			return 1;
> -		if (path->slots[0] == nritems)
> +		} else
>   			path->slots[0]--;
>   
> -		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
> +		ASSERT(path->slots[0] < btrfs_header_nritems(path->nodes[0]));
> +
> +		btrfs_item_key_to_cpu(path->nodes[0], &found_key, path->slots[0]);
>   		if (found_key.objectid < min_objectid)
>   			break;
>   		if (found_key.type == type)
> @@ -5010,26 +4956,19 @@ int btrfs_previous_extent_item(struct btrfs_root *root,
>   			struct btrfs_path *path, u64 min_objectid)
>   {
>   	struct btrfs_key found_key;
> -	struct extent_buffer *leaf;
> -	u32 nritems;
>   	int ret;
>   
>   	while (1) {
>   		if (path->slots[0] == 0) {
>   			ret = btrfs_prev_leaf(root, path);
> -			if (ret != 0)
> +			if (ret)
>   				return ret;
> -		} else {
> -			path->slots[0]--;
> -		}
> -		leaf = path->nodes[0];
> -		nritems = btrfs_header_nritems(leaf);
> -		if (nritems == 0)
> -			return 1;
> -		if (path->slots[0] == nritems)
> +		} else
>   			path->slots[0]--;
>   
> -		btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
> +		ASSERT(path->slots[0] < btrfs_header_nritems(path->nodes[0]));
> +
> +		btrfs_item_key_to_cpu(path->nodes[0], &found_key, path->slots[0]);
>   		if (found_key.objectid < min_objectid)
>   			break;
>   		if (found_key.type == BTRFS_EXTENT_ITEM_KEY ||

Re: [PATCH v2 4/4] btrfs: ctree: cleanup btrfs_prev_leaf()

[Sun YangKai]

On 2026/2/8 07:09, Qu Wenruo wrote:
> 
> 
> 在 2025/12/11 17:52, Sun YangKai 写道:
>> There's a common parttern in callers of btrfs_prev_leaf:
>> p->slots[0]-- if p->slots[0] points to a slot with invalid item(nritem).
>>
>> So just make btrfs_prev_leaf() ensure that path->slots[0] points to a
>> valid slot and cleanup its over complex logic.
>>
>> And then remove the related logic and cleanup the callers.
>>
>> This will make things much simpler.
>>
>> No functional changes.
>>
>> A. Details about changes in callers:
>>
>> ASSERT(path->slots[0] < btrfs_header_nritems(path->nodes[0])) in callers
>> is enough to make sure that nritems != 0 and slots[0] points to a valid
>> btrfs_item.
> 
> I don't think the change is safe.
> 
> There are callers doing proper checks for empty trees, e.g. 
> btrfs_previous_extent_item() and btrfs_previous_item(), now you will 
> just ignore that for kernels without CONFIG_BTRFS_ASSERT, or crash the 
> kernel if CONFIG_BTRFS_ASSERT is selected.
> 
> If you're just cleaning up btrfs_prev_leaf(), then you should keep the 
> callers the same without changing their behaviors.

Thanks a lot for your code review and it makes a lot of sense. I'll not 
touch the callers in the next version.

> I think there may be some corner case races when tree deleting and some 
> other work are happening at the same time.
> 
>>
>> And getting a `nritems==0` when btrfs_prev_leaf() returns 0 is a logic
>> error because btrfs_pref_leaf() should always
>>
>> 1. either find a non-empty leaf
> 
> Nope, there is no such guarantee in the first place.
> btrfs_prev_leaf() will unlock the path, thus all kinds of modification 
> can happen between btrfs_release_path() and btrfs_search_slot().
> 
> This assumption is just wrong.

Sorry, I got a little confused here. When btrfs_search_slot() returns an 
empty leaf, path->slots[0] will be 0 and btrfs_prev_leaf() will return 
1. Therefore, if btrfs_prev_leaf() returns 0, the leaf we get should 
always be non-empty. Which part of this reasoning is incorrect? Or maybe 
I don't get what you want to say.

>> 2. or return 1
>>
>> So we can use ASSERT safely here.
>>
>> B. Details about cleanup of btrfs_prev_leaf().
>>
>> The previous implementation works like this:
>>
>> 0) Get a previous key by "dec by 1" of the original key. Let's call it
>>     search key. It's obvious that search key is less than original key
>>     and there's no key between them.
>>
>> 1) Call btrfs_search_slot() with search key.
>>
>> 2) If we got an error or an exact match, early return.
>>
>> 3) If p->slots[0] points to the original item, p->slots[0]-- to make sure
>>     that we will not return the same item again. This may happen because
>>     there might be some tree balancing happened so the original item 
>> is no
>>     longer at slot 0.
>>
>> 4) Check if the key of the item at slot 0 is (less than the original key
>>     / less than or equal to search key) to verify if we got a previous 
>> leaf.
>>
>> However, 3) and 4) are over complex. We only need to check if
>> p->slots[0] == 0 because:
>>
>> 3a) If p->slots[0] == 0, there's no key less than or equal to search key
>>      in the tree, which means the original key is lowest in the tree. In
>>      this case, there's no previous leaf, we should return 1.
>>
>> 3b) If p->slots[0] != 0, using p->slots[0]-- is enough to get a valid
>>      previous item neither missing anything nor return the original item
>>      again because:
>>
>>      i) p->slots[0] == nritems, which means all keys in the leaf are less
>>         than search key so the leaf is a previous leaf. We only need to
>>         p->slots[0]-- to get a valid previous item.
>>
>>      ii) p->slots[0] < nritems, p->slots[0] points to an item whose key
>>          is greater than search key(probably the original item if it was
>>          not deleted), and p->slots[0] - 1 points to an item whose key is
>>          less than search key. So use p->slots[0]-- to get the previous
>>          item and we will neigher miss anything nor return the original
>>          item again. This handles the case 3) in original implementation.
>>
>> Signed-off-by: Sun YangKai <sunk67188@gmail.com>
>> ---
>>   fs/btrfs/ctree.c | 99 ++++++++++--------------------------------------
>>   1 file changed, 19 insertions(+), 80 deletions(-)
>>
>> diff --git a/fs/btrfs/ctree.c b/fs/btrfs/ctree.c
>> index 0a0157db0b0c..3026d956c7fb 100644
>> --- a/fs/btrfs/ctree.c
>> +++ b/fs/btrfs/ctree.c
>> @@ -2376,12 +2376,9 @@ int btrfs_search_old_slot(struct btrfs_root 
>> *root, const struct btrfs_key *key,
>>   static int btrfs_prev_leaf(struct btrfs_root *root, struct 
>> btrfs_path *path)
>>   {
>>       struct btrfs_key key;
>> -    struct btrfs_key orig_key;
>> -    struct btrfs_disk_key found_key;
>>       int ret;
>>       btrfs_item_key_to_cpu(path->nodes[0], &key, 0);
>> -    orig_key = key;
>>       if (key.offset > 0) {
>>           key.offset--;
>> @@ -2401,48 +2398,12 @@ static int btrfs_prev_leaf(struct btrfs_root 
>> *root, struct btrfs_path *path)
>>       if (ret <= 0)
>>           return ret;
>> -    /*
>> -     * Previous key not found. Even if we were at slot 0 of the leaf 
>> we had
>> -     * before releasing the path and calling btrfs_search_slot(), we 
>> now may
>> -     * be in a slot pointing to the same original key - this can 
>> happen if
>> -     * after we released the path, one of more items were moved from a
>> -     * sibling leaf into the front of the leaf we had due to an 
>> insertion
>> -     * (see push_leaf_right()).
>> -     * If we hit this case and our slot is > 0 and just decrement the 
>> slot
>> -     * so that the caller does not process the same key again, which 
>> may or
>> -     * may not break the caller, depending on its logic.
>> -     */
> 
> Although the change is mostly fine, if you want to keep the existing 
> behavior, you should return 0 for empty tree to keep the old behavior.

I've not thought about the empty tree case before. But I think the 
previous behavior in empty tree case is not proper and I don't want to 
keep the old behavior in this case. All callers is doing
path->slots[0]-- if btrfs_prev_leaf() returns 0 and it will cause an 
unexpected underflow although they'll check if nritems is 0 later. So I 
will mention this behavior change in commit message and comments in the 
next version.

> Furthermore, you have to explain why it's safe not only in the commit 
> message, but also comments.
> 
> This not a small change, and very low-level. Just doing black magic is 
> not acceptable.
> 
> And you need something better than your commit message as comments.
> 
> In short, you should:
> 
> - Not change the callers
> 
> - Better comments

Thanks. Very helpful for me. And wish you have a good weekend :)

> 
>> -    if (path->slots[0] < btrfs_header_nritems(path->nodes[0])) {
>> -        btrfs_item_key(path->nodes[0], &found_key, path->slots[0]);
>> -        ret = btrfs_comp_keys(&found_key, &orig_key);
>> -        if (ret == 0) {
>> -            if (path->slots[0] > 0) {
>> -                path->slots[0]--;
>> -                return 0;
>> -            }
>> -            /*
>> -             * At slot 0, same key as before, it means orig_key is
>> -             * the lowest, leftmost, key in the tree. We're done.
>> -             */
>> -            return 1;
>> -        }
>> -    }
>> +    /* There's no smaller keys in the whole tree. */
>> +    if (path->slots[0] == 0)
>> +        return 1;
>> -    btrfs_item_key(path->nodes[0], &found_key, 0);
>> -    ret = btrfs_comp_keys(&found_key, &key);
>> -    /*
>> -     * We might have had an item with the previous key in the tree right
>> -     * before we released our path. And after we released our path, that
>> -     * item might have been pushed to the first slot (0) of the leaf we
>> -     * were holding due to a tree balance. Alternatively, an item 
>> with the
>> -     * previous key can exist as the only element of a leaf (big fat 
>> item).
>> -     * Therefore account for these 2 cases, so that our callers (like
>> -     * btrfs_previous_item) don't miss an existing item with a key 
>> matching
>> -     * the previous key we computed above.
>> -     */
>> -    if (ret <= 0)
>> -        return 0;
>> -    return 1;
>> +    path->slots[0]--;
>> +    return 0;
>>   }
>>   /*
>> @@ -2473,19 +2434,11 @@ int btrfs_search_slot_for_read(struct 
>> btrfs_root *root,
>>           if (p->slots[0] >= btrfs_header_nritems(p->nodes[0]))
>>               return btrfs_next_leaf(root, p);
>>       } else {
>> -        if (p->slots[0] == 0) {
>> -            ret = btrfs_prev_leaf(root, p);
>> -            if (ret < 0)
>> -                return ret;
>> -            if (!ret) {
>> -                if (p->slots[0] == btrfs_header_nritems(p->nodes[0]))
>> -                    p->slots[0]--;
>> -                return 0;
>> -            }
>> +        /* We have no lower key in the tree. */
>> +        if (p->slots[0] == 0)
>>               return 1;
>> -        } else {
>> -            p->slots[0]--;
>> -        }
>> +
>> +        p->slots[0]--;
>>       }
>>       return 0;
>>   }
>> @@ -4969,26 +4922,19 @@ int btrfs_previous_item(struct btrfs_root *root,
>>               int type)
>>   {
>>       struct btrfs_key found_key;
>> -    struct extent_buffer *leaf;
>> -    u32 nritems;
>>       int ret;
>>       while (1) {
>>           if (path->slots[0] == 0) {
>>               ret = btrfs_prev_leaf(root, path);
>> -            if (ret != 0)
>> +            if (ret)
>>                   return ret;
>> -        } else {
>> -            path->slots[0]--;
>> -        }
>> -        leaf = path->nodes[0];
>> -        nritems = btrfs_header_nritems(leaf);
>> -        if (nritems == 0)
>> -            return 1;
>> -        if (path->slots[0] == nritems)
>> +        } else
>>               path->slots[0]--;
>> -        btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
>> +        ASSERT(path->slots[0] < btrfs_header_nritems(path->nodes[0]));
>> +
>> +        btrfs_item_key_to_cpu(path->nodes[0], &found_key, path- 
>> >slots[0]);
>>           if (found_key.objectid < min_objectid)
>>               break;
>>           if (found_key.type == type)
>> @@ -5010,26 +4956,19 @@ int btrfs_previous_extent_item(struct 
>> btrfs_root *root,
>>               struct btrfs_path *path, u64 min_objectid)
>>   {
>>       struct btrfs_key found_key;
>> -    struct extent_buffer *leaf;
>> -    u32 nritems;
>>       int ret;
>>       while (1) {
>>           if (path->slots[0] == 0) {
>>               ret = btrfs_prev_leaf(root, path);
>> -            if (ret != 0)
>> +            if (ret)
>>                   return ret;
>> -        } else {
>> -            path->slots[0]--;
>> -        }
>> -        leaf = path->nodes[0];
>> -        nritems = btrfs_header_nritems(leaf);
>> -        if (nritems == 0)
>> -            return 1;
>> -        if (path->slots[0] == nritems)
>> +        } else
>>               path->slots[0]--;
>> -        btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
>> +        ASSERT(path->slots[0] < btrfs_header_nritems(path->nodes[0]));
>> +
>> +        btrfs_item_key_to_cpu(path->nodes[0], &found_key, path- 
>> >slots[0]);
>>           if (found_key.objectid < min_objectid)
>>               break;
>>           if (found_key.type == BTRFS_EXTENT_ITEM_KEY ||
> 

Re: [PATCH v2 4/4] btrfs: ctree: cleanup btrfs_prev_leaf()

[Qu Wenruo]

在 2026/2/8 13:12, Sun YangKai 写道:

> 
> Sorry, I got a little confused here. When btrfs_search_slot() returns an 
> empty leaf, path->slots[0] will be 0 and btrfs_prev_leaf() will return 
> 1. Therefore, if btrfs_prev_leaf() returns 0, the leaf we get should 
> always be non-empty. Which part of this reasoning is incorrect? Or maybe 
> I don't get what you want to say.

Because the old btrfs_prev_leaf() can return 0 if the tree got emptied 
before btrfs_search_slot() call, if you're doing a cleanup, just don't 
change that behavior.

If you think this behavior is not correct, do it in another patch and 
explain it correctly.

>>
>> Although the change is mostly fine, if you want to keep the existing 
>> behavior, you should return 0 for empty tree to keep the old behavior.
> 
> I've not thought about the empty tree case before. But I think the 
> previous behavior in empty tree case is not proper and I don't want to 
> keep the old behavior in this case.

Then it's no longer a cleanup, and you're mixing a cleanup with a 
behavior change.

> All callers is doing
> path->slots[0]-- if btrfs_prev_leaf() returns 0 and it will cause an 
> unexpected underflow although they'll check if nritems is 0 later.

They all have proper nritems check or the tree will never be empty.

For extent tree it will never be empty, at least without extent-tree-v2 
feature.
So btrfs_previous_extent_item() should never hit an empty tree.

For btrfs_search_slot_for_read() the qgroup callers are never blindly 
decreasing slots[0], for send callers the subvolume tree will never be 
empty.

Thus all your underflow argument makes no sense.

If you don't like this behavior, again change it in a dedicated patch, 
not mixing it into the so called "cleanup" patch.