[PATCH 0/3] btrfs: search_tree ioctl performance improvements and cleanups

[PATCH 0/3] btrfs: search_tree ioctl performance improvements and cleanups

[Sun YangKai]

This series optimizes the search_tree ioctl path used by tools like compsize
and cleans up related code:

Patch 1: Narrow loop variable scope

Patch 2: Early exit for out-of-range keys

    Replaces continue with early exit when keys exceed max_key

    Provides measurable performance improvements:
    Cold cache: 34.61s → 30.40s (about 12% improvement)
    Hot cache: 14.19s → 10.57s (about 25% improvement)

Patch 3: Simplify key range checking

    Replaces key_in_sk() helper with direct comparisons

    Adds WARN_ON for min_key validation (safe due to forward search)

    Maintains equivalent functionality with cleaner implementation

These changes optimize a critical path for filesystem analysis tools while
improving code maintainability. The performance gains are particularly
noticeable when scanning large filesystems.

Thanks,
Sun YangKai

Sun YangKai (3):
  btrfs: narrow loop variable scope in copy_to_sk()
  btrfs: early exit the searching process in search_tree ioctl
  btrfs: replace key_in_sk() with a simple btrfs_key compare

 fs/btrfs/ioctl.c | 55 +++++++++++++++++-------------------------------
 1 file changed, 19 insertions(+), 36 deletions(-)

-- 
2.49.0

[PATCH 1/3] btrfs: narrow loop variable scope in copy_to_sk()

[Sun YangKai]

The loop variable 'i' is only used in the for loop, so move its
declaration into the loop header to reduce its scope and improve
readability.

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

diff --git a/fs/btrfs/ioctl.c b/fs/btrfs/ioctl.c
index 913acef3f0a9..10c243d32b34 100644
--- a/fs/btrfs/ioctl.c
+++ b/fs/btrfs/ioctl.c
@@ -1485,7 +1485,6 @@ static noinline int copy_to_sk(struct btrfs_path *path,
 	unsigned long item_off;
 	unsigned long item_len;
 	int nritems;
-	int i;
 	int slot;
 	int ret = 0;
 
@@ -1493,13 +1492,12 @@ static noinline int copy_to_sk(struct btrfs_path *path,
 	slot = path->slots[0];
 	nritems = btrfs_header_nritems(leaf);
 
-	if (btrfs_header_generation(leaf) > sk->max_transid) {
-		i = nritems;
+	if (btrfs_header_generation(leaf) > sk->max_transid)
 		goto advance_key;
-	}
+
 	found_transid = btrfs_header_generation(leaf);
 
-	for (i = slot; i < nritems; i++) {
+	for (int i = slot; i < nritems; i++) {
 		item_off = btrfs_item_ptr_offset(leaf, i);
 		item_len = btrfs_item_size(leaf, i);
 
-- 
2.49.0

[PATCH 2/3] btrfs: early exit the searching process in search_tree ioctl

[Sun YangKai]

With the following two assumptions(min_key and max_key here is the
related fields in search_key):

1. When `btrfs_search_forward` returns 0, the key will always greater
   than or equal to the provided key. So the function `copy_to_sk` will
   never be called with a key less than the min_key. So we will never get
   a key less than min_key during walking forward in the leaf.

2. When we got a key greater than max_key in current leaf, we will never
   get a key in search_key range any more. So we should stop searching
   further.

So we can safely replace the continue with early exiting. This will
improve the performance of the search_tree related ioctl syscalls, which
is the bottleneck of tools like compsize.

I've run compsize with and without this patch to compare the performance.

When cache is cold, it's
1.29user 21.02system 0:34.61elapsed 64%CPU without the patch, and
1.24user 17.34system 0:30.40elapsed 61%CPU with the patch.

When cache is hot, it's
1.21user 12.95system 0:14.19elapsed 99%CPU without the patch, and
1.18user 9.37system 0:10.57elapsed 99%CPU with the patch.

This is not a serious benchmark, but can reflect the performance
difference.

Signed-off-by: Sun YangKai <sunk67188@gmail.com>
---
 fs/btrfs/ioctl.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

diff --git a/fs/btrfs/ioctl.c b/fs/btrfs/ioctl.c
index 10c243d32b34..5e6202a417c4 100644
--- a/fs/btrfs/ioctl.c
+++ b/fs/btrfs/ioctl.c
@@ -1502,8 +1502,10 @@ static noinline int copy_to_sk(struct btrfs_path *path,
 		item_len = btrfs_item_size(leaf, i);
 
 		btrfs_item_key_to_cpu(leaf, key, i);
-		if (!key_in_sk(key, sk))
-			continue;
+		if (!key_in_sk(key, sk)) {
+			ret = 1;
+			goto out;
+		}
 
 		if (sizeof(sh) + item_len > *buf_size) {
 			if (*num_found) {
-- 
2.49.0

[PATCH 3/3] btrfs: replace key_in_sk() with a simple btrfs_key compare

[Sun YangKai]

The min-key guard is inherent to btrfs_search_forward().

The max-check logic is equivalent to the original.

Signed-off-by: Sun YangKai <sunk67188@gmail.com>
---
 fs/btrfs/ioctl.c | 43 +++++++++++++------------------------------
 1 file changed, 13 insertions(+), 30 deletions(-)

diff --git a/fs/btrfs/ioctl.c b/fs/btrfs/ioctl.c
index 5e6202a417c4..2bc99e603974 100644
--- a/fs/btrfs/ioctl.c
+++ b/fs/btrfs/ioctl.c
@@ -1446,30 +1446,6 @@ static noinline int btrfs_ioctl_subvol_setflags(struct file *file,
 	return ret;
 }
 
-static noinline bool key_in_sk(const struct btrfs_key *key,
-			       const struct btrfs_ioctl_search_key *sk)
-{
-	struct btrfs_key test;
-	int ret;
-
-	test.objectid = sk->min_objectid;
-	test.type = sk->min_type;
-	test.offset = sk->min_offset;
-
-	ret = btrfs_comp_cpu_keys(key, &test);
-	if (ret < 0)
-		return false;
-
-	test.objectid = sk->max_objectid;
-	test.type = sk->max_type;
-	test.offset = sk->max_offset;
-
-	ret = btrfs_comp_cpu_keys(key, &test);
-	if (ret > 0)
-		return false;
-	return true;
-}
-
 static noinline int copy_to_sk(struct btrfs_path *path,
 			       struct btrfs_key *key,
 			       const struct btrfs_ioctl_search_key *sk,
@@ -1481,7 +1457,8 @@ static noinline int copy_to_sk(struct btrfs_path *path,
 	u64 found_transid;
 	struct extent_buffer *leaf;
 	struct btrfs_ioctl_search_header sh;
-	struct btrfs_key test;
+	struct btrfs_key min_key;
+	struct btrfs_key max_key;
 	unsigned long item_off;
 	unsigned long item_len;
 	int nritems;
@@ -1492,17 +1469,26 @@ static noinline int copy_to_sk(struct btrfs_path *path,
 	slot = path->slots[0];
 	nritems = btrfs_header_nritems(leaf);
 
+	max_key.objectid = sk->max_objectid;
+	max_key.type = sk->max_type;
+	max_key.offset = sk->max_offset;
+
 	if (btrfs_header_generation(leaf) > sk->max_transid)
 		goto advance_key;
 
 	found_transid = btrfs_header_generation(leaf);
 
+	min_key.objectid = sk->min_objectid;
+	min_key.type = sk->min_type;
+	min_key.offset = sk->min_offset;
+
 	for (int i = slot; i < nritems; i++) {
 		item_off = btrfs_item_ptr_offset(leaf, i);
 		item_len = btrfs_item_size(leaf, i);
 
 		btrfs_item_key_to_cpu(leaf, key, i);
-		if (!key_in_sk(key, sk)) {
+		WARN_ON(btrfs_comp_cpu_keys(&min_key, key) > 0);
+		if (btrfs_comp_cpu_keys(key, &max_key) > 0) {
 			ret = 1;
 			goto out;
 		}
@@ -1574,10 +1560,7 @@ static noinline int copy_to_sk(struct btrfs_path *path,
 	}
 advance_key:
 	ret = 0;
-	test.objectid = sk->max_objectid;
-	test.type = sk->max_type;
-	test.offset = sk->max_offset;
-	if (btrfs_comp_cpu_keys(key, &test) >= 0)
+	if (btrfs_comp_cpu_keys(key, &max_key) >= 0)
 		ret = 1;
 	else if (key->offset < (u64)-1)
 		key->offset++;
-- 
2.49.0

Re: [PATCH 3/3] btrfs: replace key_in_sk() with a simple btrfs_key compare

[David Sterba]

On Thu, Jun 12, 2025 at 12:31:13PM +0800, Sun YangKai wrote:
> The min-key guard is inherent to btrfs_search_forward().
> 
> The max-check logic is equivalent to the original.
> 
> Signed-off-by: Sun YangKai <sunk67188@gmail.com>
> ---
>  fs/btrfs/ioctl.c | 43 +++++++++++++------------------------------
>  1 file changed, 13 insertions(+), 30 deletions(-)
> 
> diff --git a/fs/btrfs/ioctl.c b/fs/btrfs/ioctl.c
> index 5e6202a417c4..2bc99e603974 100644
> --- a/fs/btrfs/ioctl.c
> +++ b/fs/btrfs/ioctl.c
> @@ -1446,30 +1446,6 @@ static noinline int btrfs_ioctl_subvol_setflags(struct file *file,
>  	return ret;
>  }
>  
> -static noinline bool key_in_sk(const struct btrfs_key *key,
> -			       const struct btrfs_ioctl_search_key *sk)
> -{
> -	struct btrfs_key test;
> -	int ret;
> -
> -	test.objectid = sk->min_objectid;
> -	test.type = sk->min_type;
> -	test.offset = sk->min_offset;
> -
> -	ret = btrfs_comp_cpu_keys(key, &test);
> -	if (ret < 0)
> -		return false;
> -
> -	test.objectid = sk->max_objectid;
> -	test.type = sk->max_type;
> -	test.offset = sk->max_offset;
> -
> -	ret = btrfs_comp_cpu_keys(key, &test);
> -	if (ret > 0)
> -		return false;
> -	return true;
> -}
> -
>  static noinline int copy_to_sk(struct btrfs_path *path,
>  			       struct btrfs_key *key,
>  			       const struct btrfs_ioctl_search_key *sk,
> @@ -1481,7 +1457,8 @@ static noinline int copy_to_sk(struct btrfs_path *path,
>  	u64 found_transid;
>  	struct extent_buffer *leaf;
>  	struct btrfs_ioctl_search_header sh;
> -	struct btrfs_key test;
> +	struct btrfs_key min_key;
> +	struct btrfs_key max_key;
>  	unsigned long item_off;
>  	unsigned long item_len;
>  	int nritems;
> @@ -1492,17 +1469,26 @@ static noinline int copy_to_sk(struct btrfs_path *path,
>  	slot = path->slots[0];
>  	nritems = btrfs_header_nritems(leaf);
>  
> +	max_key.objectid = sk->max_objectid;
> +	max_key.type = sk->max_type;
> +	max_key.offset = sk->max_offset;
> +
>  	if (btrfs_header_generation(leaf) > sk->max_transid)
>  		goto advance_key;
>  
>  	found_transid = btrfs_header_generation(leaf);
>  
> +	min_key.objectid = sk->min_objectid;
> +	min_key.type = sk->min_type;
> +	min_key.offset = sk->min_offset;
> +
>  	for (int i = slot; i < nritems; i++) {
>  		item_off = btrfs_item_ptr_offset(leaf, i);
>  		item_len = btrfs_item_size(leaf, i);
>  
>  		btrfs_item_key_to_cpu(leaf, key, i);
> -		if (!key_in_sk(key, sk)) {
> +		WARN_ON(btrfs_comp_cpu_keys(&min_key, key) > 0);

I'd rather use a DEBUG_WARN or ASSERT here. If it's a runtime error that
can otherwise happen then it should be handled as and error.

One way or another it's good to have it here as we want to verify the
assumptions of btrfs_search_forward().

Re: [PATCH 0/3] btrfs: search_tree ioctl performance improvements and cleanups

[David Sterba]

On Thu, Jun 12, 2025 at 12:31:10PM +0800, Sun YangKai wrote:
> This series optimizes the search_tree ioctl path used by tools like compsize
> and cleans up related code:

IIRC there were proposals to have a ioctl for compression size but I
can't find the most recent version now. The SEARCH_TREE what compsize
does is a "temporary" workaround.

> Patch 1: Narrow loop variable scope
> 
> Patch 2: Early exit for out-of-range keys
> 
>     Replaces continue with early exit when keys exceed max_key
> 
>     Provides measurable performance improvements:
>     Cold cache: 34.61s → 30.40s (about 12% improvement)
>     Hot cache: 14.19s → 10.57s (about 25% improvement)
> 
> Patch 3: Simplify key range checking
> 
>     Replaces key_in_sk() helper with direct comparisons
> 
>     Adds WARN_ON for min_key validation (safe due to forward search)
> 
>     Maintains equivalent functionality with cleaner implementation
> 
> These changes optimize a critical path for filesystem analysis tools while
> improving code maintainability. The performance gains are particularly
> noticeable when scanning large filesystems.

Thanks. The changes look good to me, and with a measurable performance
improvement.

Re: [PATCH 3/3] btrfs: replace key_in_sk() with a simple btrfs_key compare

[Sun YangKai]

> I'd rather use a DEBUG_WARN or ASSERT here. If it's a runtime error that
> can otherwise happen then it should be handled as and error.
> 
> One way or another it's good to have it here as we want to verify the
> assumptions of btrfs_search_forward().

I've just done some tests on my laptop and the result shows we don't need to 
worry about performance here.

And I totally agree that ASSERT is better than WARN_ON.

So I think we can use ASSERT instead of WARN_ON here.

Thanks.

-----

Sorry. Resend with CC.

[PATCH v2 0/3] btrfs: search_tree ioctl performance improvements and cleanups

[Sun YangKai]

This series optimizes the search_tree ioctl path used by tools like
compsize and cleans up related code:

Patch 1: Narrow loop variable scope

Patch 2: Early exit for out-of-range keys

    Replace continue with early exit when keys exceed max_key

    Provide measurable performance improvements:
    Cold cache: 34.61s → 30.40s (about 12% improvement)
    Hot cache: 14.19s → 10.57s (about 25% improvement)

Patch 3: Simplify key range checking

    Replace key_in_sk() helper with direct comparisons

    Add ASSERT for min_key validation (safe due to forward search)

    Maintain equivalent functionality with cleaner implementation

These changes optimize a critical path for filesystem analysis tools while
improving code maintainability. The performance gains are particularly
noticeable when scanning large filesystems.

Thanks,
Sun YangKai

---

Changes since v1:

* Replace the WARN_ON with ASSERT, since the condition is a runtime error.
  Suggested by David Sterba.

---

Sun YangKai (3):
  btrfs: narrow loop variable scope in copy_to_sk()
  btrfs: early exit the searching process in search_tree ioctl
  btrfs: replace key_in_sk() with a simple btrfs_key compare

 fs/btrfs/ioctl.c | 55 +++++++++++++++++-------------------------------
 1 file changed, 19 insertions(+), 36 deletions(-)

-- 
2.50.0

[PATCH v2 1/3] btrfs: narrow loop variable scope in copy_to_sk()

[Sun YangKai]

The loop variable 'i' is only used in the for loop, so move its
declaration into the loop header to reduce its scope and improve
readability.

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

diff --git a/fs/btrfs/ioctl.c b/fs/btrfs/ioctl.c
index 8a60983a697c..9948a12fd5e3 100644
--- a/fs/btrfs/ioctl.c
+++ b/fs/btrfs/ioctl.c
@@ -1485,7 +1485,6 @@ static noinline int copy_to_sk(struct btrfs_path *path,
 	unsigned long item_off;
 	unsigned long item_len;
 	int nritems;
-	int i;
 	int slot;
 	int ret = 0;
 
@@ -1493,13 +1492,12 @@ static noinline int copy_to_sk(struct btrfs_path *path,
 	slot = path->slots[0];
 	nritems = btrfs_header_nritems(leaf);
 
-	if (btrfs_header_generation(leaf) > sk->max_transid) {
-		i = nritems;
+	if (btrfs_header_generation(leaf) > sk->max_transid)
 		goto advance_key;
-	}
+
 	found_transid = btrfs_header_generation(leaf);
 
-	for (i = slot; i < nritems; i++) {
+	for (int i = slot; i < nritems; i++) {
 		item_off = btrfs_item_ptr_offset(leaf, i);
 		item_len = btrfs_item_size(leaf, i);
 
-- 
2.50.0

[PATCH v2 2/3] btrfs: early exit the searching process in search_tree ioctl

[Sun YangKai]

With the following two assumptions(min_key and max_key here is the
related fields in search_key):

1. When `btrfs_search_forward` returns 0, the key will always greater
   than or equal to the provided key. So the function `copy_to_sk` will
   never be called with a key less than the min_key. So we will never get
   a key less than min_key during walking forward in the leaf.

2. When we got a key greater than max_key in current leaf, we will never
   get a key in search_key range any more. So we should stop searching
   further.

So we can safely replace the continue with early exiting. This will
improve the performance of the search_tree related ioctl syscalls, which
is the bottleneck of tools like compsize.

I've run compsize with and without this patch to compare the performance.

When cache is cold, it's
1.29user 21.02system 0:34.61elapsed 64%CPU without the patch, and
1.24user 17.34system 0:30.40elapsed 61%CPU with the patch.

When cache is hot, it's
1.21user 12.95system 0:14.19elapsed 99%CPU without the patch, and
1.18user 9.37system 0:10.57elapsed 99%CPU with the patch.

This is not a serious benchmark, but can reflect the performance
difference.

Signed-off-by: Sun YangKai <sunk67188@gmail.com>
---
 fs/btrfs/ioctl.c | 6 ++++--
 1 file changed, 4 insertions(+), 2 deletions(-)

diff --git a/fs/btrfs/ioctl.c b/fs/btrfs/ioctl.c
index 9948a12fd5e3..27c294e9d68d 100644
--- a/fs/btrfs/ioctl.c
+++ b/fs/btrfs/ioctl.c
@@ -1502,8 +1502,10 @@ static noinline int copy_to_sk(struct btrfs_path *path,
 		item_len = btrfs_item_size(leaf, i);
 
 		btrfs_item_key_to_cpu(leaf, key, i);
-		if (!key_in_sk(key, sk))
-			continue;
+		if (!key_in_sk(key, sk)) {
+			ret = 1;
+			goto out;
+		}
 
 		if (sizeof(sh) + item_len > *buf_size) {
 			if (*num_found) {
-- 
2.50.0

[PATCH v2 3/3] btrfs: replace key_in_sk() with a simple btrfs_key compare

[Sun YangKai]

- The min-key guard is inherent to btrfs_search_forward().
- The max-check logic is equivalent to the original.

Signed-off-by: Sun YangKai <sunk67188@gmail.com>
---
 fs/btrfs/ioctl.c | 43 +++++++++++++------------------------------
 1 file changed, 13 insertions(+), 30 deletions(-)

diff --git a/fs/btrfs/ioctl.c b/fs/btrfs/ioctl.c
index 27c294e9d68d..504c29af2f85 100644
--- a/fs/btrfs/ioctl.c
+++ b/fs/btrfs/ioctl.c
@@ -1446,30 +1446,6 @@ static noinline int btrfs_ioctl_subvol_setflags(struct file *file,
 	return ret;
 }
 
-static noinline bool key_in_sk(const struct btrfs_key *key,
-			       const struct btrfs_ioctl_search_key *sk)
-{
-	struct btrfs_key test;
-	int ret;
-
-	test.objectid = sk->min_objectid;
-	test.type = sk->min_type;
-	test.offset = sk->min_offset;
-
-	ret = btrfs_comp_cpu_keys(key, &test);
-	if (ret < 0)
-		return false;
-
-	test.objectid = sk->max_objectid;
-	test.type = sk->max_type;
-	test.offset = sk->max_offset;
-
-	ret = btrfs_comp_cpu_keys(key, &test);
-	if (ret > 0)
-		return false;
-	return true;
-}
-
 static noinline int copy_to_sk(struct btrfs_path *path,
 			       struct btrfs_key *key,
 			       const struct btrfs_ioctl_search_key *sk,
@@ -1481,7 +1457,8 @@ static noinline int copy_to_sk(struct btrfs_path *path,
 	u64 found_transid;
 	struct extent_buffer *leaf;
 	struct btrfs_ioctl_search_header sh;
-	struct btrfs_key test;
+	struct btrfs_key min_key;
+	struct btrfs_key max_key;
 	unsigned long item_off;
 	unsigned long item_len;
 	int nritems;
@@ -1492,17 +1469,26 @@ static noinline int copy_to_sk(struct btrfs_path *path,
 	slot = path->slots[0];
 	nritems = btrfs_header_nritems(leaf);
 
+	max_key.objectid = sk->max_objectid;
+	max_key.type = sk->max_type;
+	max_key.offset = sk->max_offset;
+
 	if (btrfs_header_generation(leaf) > sk->max_transid)
 		goto advance_key;
 
 	found_transid = btrfs_header_generation(leaf);
 
+	min_key.objectid = sk->min_objectid;
+	min_key.type = sk->min_type;
+	min_key.offset = sk->min_offset;
+
 	for (int i = slot; i < nritems; i++) {
 		item_off = btrfs_item_ptr_offset(leaf, i);
 		item_len = btrfs_item_size(leaf, i);
 
 		btrfs_item_key_to_cpu(leaf, key, i);
-		if (!key_in_sk(key, sk)) {
+		ASSERT(btrfs_comp_cpu_keys(&min_key, key) <= 0);
+		if (btrfs_comp_cpu_keys(key, &max_key) > 0) {
 			ret = 1;
 			goto out;
 		}
@@ -1574,10 +1560,7 @@ static noinline int copy_to_sk(struct btrfs_path *path,
 	}
 advance_key:
 	ret = 0;
-	test.objectid = sk->max_objectid;
-	test.type = sk->max_type;
-	test.offset = sk->max_offset;
-	if (btrfs_comp_cpu_keys(key, &test) >= 0)
+	if (btrfs_comp_cpu_keys(key, &max_key) >= 0)
 		ret = 1;
 	else if (key->offset < (u64)-1)
 		key->offset++;
-- 
2.50.0

Re: [PATCH v2 0/3] btrfs: search_tree ioctl performance improvements and cleanups

[Sun YangKai]

> This series optimizes the search_tree ioctl path used by tools like
> compsize and cleans up related code:
> 
> Patch 1: Narrow loop variable scope
> 
> Patch 2: Early exit for out-of-range keys
> 
>     Replace continue with early exit when keys exceed max_key
> 
>     Provide measurable performance improvements:
>     Cold cache: 34.61s → 30.40s (about 12% improvement)
>     Hot cache: 14.19s → 10.57s (about 25% improvement)
> 
> Patch 3: Simplify key range checking
> 
>     Replace key_in_sk() helper with direct comparisons
> 
>     Add ASSERT for min_key validation (safe due to forward search)
> 
>     Maintain equivalent functionality with cleaner implementation
> 
> These changes optimize a critical path for filesystem analysis tools while
> improving code maintainability. The performance gains are particularly
> noticeable when scanning large filesystems.
> 
> Thanks,
> Sun YangKai
> 
> ---
> 
> Changes since v1:
> 
> * Replace the WARN_ON with ASSERT, since the condition is a runtime error.
>   Suggested by David Sterba.
> 
> ---
> 
> Sun YangKai (3):
>   btrfs: narrow loop variable scope in copy_to_sk()
>   btrfs: early exit the searching process in search_tree ioctl
>   btrfs: replace key_in_sk() with a simple btrfs_key compare
> 
>  fs/btrfs/ioctl.c | 55 +++++++++++++++++-------------------------------
>  1 file changed, 19 insertions(+), 36 deletions(-)

Politely ping. Is there anything blocking this?