[PATCH] btrfs: speed up steal_from_bitmap_to_front() with a backward word scan

[PATCH] btrfs: speed up steal_from_bitmap_to_front() with a backward word scan

[Elias Jernberg]

steal_from_bitmap_to_front() looks for the last clear bit below the new
extent entry by walking every clear bit of the bitmap from bit 0 with
for_each_clear_bit_from(). In a bitmap that is mostly allocated that is
one find_next_zero_bit() call per allocated sector below the entry, and
it is done for every free space entry added next to a bitmap.

With 16K pages a bitmap has 131072 bits. On an arm64 machine with 16K
pages (Apple M5, 4K sectorsize, discard=async, compression on),
deleting a 4 GiB file of about one million 4K extents, after scattered
4K rewrites had put the block group's free space into bitmaps, made the
next fsync take 29 to 36 seconds of CPU. Three sysrq-l samples taken
during the stall all showed:

  _find_next_zero_bit
  __btrfs_add_free_space
  unpin_extent_range
  btrfs_finish_extent_commit
  btrfs_commit_transaction
  btrfs_sync_file

A buffered 4 GiB write with end_fsync right after the delete ran at
119-147 MB/s instead of about 4.7 GB/s.

Scan backwards from the bit below the entry one word at a time instead,
so the cost follows the run of free sectors that ends there and not the
number of allocated sectors below it. The result is the same for every
index: a userspace copy of both versions agreed in about 11 million
cases (bitmaps of 256, 32768 and 131072 bits, empty, full, random and
long runs, word boundaries and the last bit). The index is still
limited to BITS_PER_BITMAP - 1, as the old loop was.

With the change the same sequence ran the buffered write in 0.8-0.9 s
(4613 and 5238 MB/s).

Fixes: 200055239604 ("Btrfs: improve free space cache management and space allocation")
Signed-off-by: Elias Jernberg <eliasjernberg@gmail.com>
---

Notes:
    - The numbers above come from a 7.3-based tree (aurora-silicon/linux,
      Apple M5 MacBook Pro, 16K pages) carrying this change in an
      equivalent form. This version was build-tested on btrfs for-next
      (3aefd67f08f8) as x86_64 UML with W=1, no new warnings, and the btrfs
      self-tests pass (CONFIG_BTRFS_FS_RUN_SANITY_TESTS, including the
      bitmap stealing tests).
    - On x86_64 with 4K pages I could not reproduce a clear stall with the
      similar fragmenting workload (sync after the delete took 0.4-1.9 s), so the
      effect looks tied to the larger bitmaps of 16K and 64K pages.
    - Reproducer (fio, run on the btrfs filesystem under test):
        fio --name=a --filename=f --rw=write --bs=1M --direct=1 --size=4G --end_fsync=1
        fio --name=r --filename=f --rw=randwrite --bs=4k --ioengine=libaio --iodepth=32 \
            --direct=1 --size=4G --time_based --runtime=15 --end_fsync=1
        fio --name=s --filename=f --rw=write --bs=4k --direct=1 --size=4G \
            --time_based --runtime=15 --fsync=1
        rm f
        fio --name=b --filename=f --rw=write --bs=1M --size=4G --end_fsync=1
      The last job takes 29-36 s without this patch and under 1 s with it.
    - Prior art: Yun Levi suggested replacing this loop in December 2020 on
      LKML, as a user of a proposed find_prev_zero_bit()
      (https://www.mail-archive.com/linux-kernel@vger.kernel.org/msg2402457.html).
      That helper was never added and the loop is unchanged in for-next.
      This version keeps the backward scan local to free-space-cache.c.
    - Tool use: the stall was profiled, the fix written and the changelog
      drafted with an LLM coding assistant (Claude). I have reviewed the
      change; the equivalence test and the measurements were run on my
      machine.

 fs/btrfs/free-space-cache.c | 30 ++++++++++++++++++++++--------
 1 file changed, 22 insertions(+), 8 deletions(-)

diff --git a/fs/btrfs/free-space-cache.c b/fs/btrfs/free-space-cache.c
index bff6e5b372d6..c599a8f25821 100644
--- a/fs/btrfs/free-space-cache.c
+++ b/fs/btrfs/free-space-cache.c
@@ -1269,6 +1269,26 @@ static bool steal_from_bitmap_to_end(struct btrfs_free_space_ctl *ctl,
 	return true;
 }
 
+/*
+ * Return the index of the last clear bit at or below @bit, or ULONG_MAX if
+ * bits 0 to @bit are all set.  Scan backwards a word at a time, so the cost
+ * follows the length of the run of set bits that ends at @bit rather than the
+ * number of clear bits below it.
+ */
+static unsigned long find_last_clear_bit_upto(const unsigned long *bitmap,
+					      unsigned long bit)
+{
+	unsigned long idx = BIT_WORD(bit);
+	unsigned long word = ~bitmap[idx] & BITMAP_LAST_WORD_MASK(bit + 1);
+
+	while (!word) {
+		if (idx == 0)
+			return ULONG_MAX;
+		word = ~bitmap[--idx];
+	}
+	return idx * BITS_PER_LONG + __fls(word);
+}
+
 static bool steal_from_bitmap_to_front(struct btrfs_free_space_ctl *ctl,
 				       struct btrfs_free_space *info,
 				       bool update_stat)
@@ -1277,7 +1297,6 @@ static bool steal_from_bitmap_to_front(struct btrfs_free_space_ctl *ctl,
 	struct btrfs_free_space *bitmap;
 	u64 bitmap_offset;
 	unsigned long i;
-	unsigned long j;
 	unsigned long prev_j;
 	u64 bytes;
 
@@ -1294,13 +1313,8 @@ static bool steal_from_bitmap_to_front(struct btrfs_free_space_ctl *ctl,
 		return false;
 
 	i = offset_to_bit(bitmap->offset, unit, info->offset) - 1;
-	j = 0;
-	prev_j = (unsigned long)-1;
-	for_each_clear_bit_from(j, bitmap->bitmap, BITS_PER_BITMAP) {
-		if (j > i)
-			break;
-		prev_j = j;
-	}
+	prev_j = find_last_clear_bit_upto(bitmap->bitmap,
+					  min(i, BITS_PER_BITMAP - 1));
 	if (prev_j == i)
 		return false;
 
-- 
2.56.1

Re: [PATCH] btrfs: speed up steal_from_bitmap_to_front() with a backward word scan

[Qu Wenruo]

在 2026/11/14 10:32, Elias Jernberg 写道:
[...]
> 
> Fixes: 200055239604 ("Btrfs: improve free space cache management and space allocation")
> Signed-off-by: Elias Jernberg <eliasjernberg@gmail.com>
> ---
> 
> Notes:
>      - The numbers above come from a 7.3-based tree (aurora-silicon/linux,
>        Apple M5 MacBook Pro, 16K pages) carrying this change in an
>        equivalent form. This version was build-tested on btrfs for-next
>        (3aefd67f08f8) as x86_64 UML with W=1, no new warnings, and the btrfs
>        self-tests pass (CONFIG_BTRFS_FS_RUN_SANITY_TESTS, including the
>        bitmap stealing tests).
>      - On x86_64 with 4K pages I could not reproduce a clear stall with the
>        similar fragmenting workload (sync after the delete took 0.4-1.9 s), so the
>        effect looks tied to the larger bitmaps of 16K and 64K pages.

I'm more interested on the page size bounding part.

As btrfs_free_space_bitmap_cachep is using fixed PAGE_SIZE for the 
allocation, it's causing the behavior difference in the first place.

I'm wondering if we should make the bitmap size not bounded to 
PAGE_SIZE, but the sectorsize of each filesystem.

Have you tried 16K page size with 16K sector size? (along with changed 
blocksize in the fio)
Did that can reproduce the same latency?

Thanks,
Qu

>      - Reproducer (fio, run on the btrfs filesystem under test):
>          fio --name=a --filename=f --rw=write --bs=1M --direct=1 --size=4G --end_fsync=1
>          fio --name=r --filename=f --rw=randwrite --bs=4k --ioengine=libaio --iodepth=32 \
>              --direct=1 --size=4G --time_based --runtime=15 --end_fsync=1
>          fio --name=s --filename=f --rw=write --bs=4k --direct=1 --size=4G \
>              --time_based --runtime=15 --fsync=1
>          rm f
>          fio --name=b --filename=f --rw=write --bs=1M --size=4G --end_fsync=1
>        The last job takes 29-36 s without this patch and under 1 s with it.
>      - Prior art: Yun Levi suggested replacing this loop in December 2020 on
>        LKML, as a user of a proposed find_prev_zero_bit()
>        (https://www.mail-archive.com/linux-kernel@vger.kernel.org/msg2402457.html).
>        That helper was never added and the loop is unchanged in for-next.
>        This version keeps the backward scan local to free-space-cache.c.
>      - Tool use: the stall was profiled, the fix written and the changelog
>        drafted with an LLM coding assistant (Claude). I have reviewed the
>        change; the equivalence test and the measurements were run on my
>        machine.
> 
>   fs/btrfs/free-space-cache.c | 30 ++++++++++++++++++++++--------
>   1 file changed, 22 insertions(+), 8 deletions(-)
> 
> diff --git a/fs/btrfs/free-space-cache.c b/fs/btrfs/free-space-cache.c
> index bff6e5b372d6..c599a8f25821 100644
> --- a/fs/btrfs/free-space-cache.c
> +++ b/fs/btrfs/free-space-cache.c
> @@ -1269,6 +1269,26 @@ static bool steal_from_bitmap_to_end(struct btrfs_free_space_ctl *ctl,
>   	return true;
>   }
>   
> +/*
> + * Return the index of the last clear bit at or below @bit, or ULONG_MAX if
> + * bits 0 to @bit are all set.  Scan backwards a word at a time, so the cost
> + * follows the length of the run of set bits that ends at @bit rather than the
> + * number of clear bits below it.
> + */
> +static unsigned long find_last_clear_bit_upto(const unsigned long *bitmap,
> +					      unsigned long bit)
> +{
> +	unsigned long idx = BIT_WORD(bit);
> +	unsigned long word = ~bitmap[idx] & BITMAP_LAST_WORD_MASK(bit + 1);
> +
> +	while (!word) {
> +		if (idx == 0)
> +			return ULONG_MAX;
> +		word = ~bitmap[--idx];
> +	}
> +	return idx * BITS_PER_LONG + __fls(word);
> +}
> +
>   static bool steal_from_bitmap_to_front(struct btrfs_free_space_ctl *ctl,
>   				       struct btrfs_free_space *info,
>   				       bool update_stat)
> @@ -1277,7 +1297,6 @@ static bool steal_from_bitmap_to_front(struct btrfs_free_space_ctl *ctl,
>   	struct btrfs_free_space *bitmap;
>   	u64 bitmap_offset;
>   	unsigned long i;
> -	unsigned long j;
>   	unsigned long prev_j;
>   	u64 bytes;
>   
> @@ -1294,13 +1313,8 @@ static bool steal_from_bitmap_to_front(struct btrfs_free_space_ctl *ctl,
>   		return false;
>   
>   	i = offset_to_bit(bitmap->offset, unit, info->offset) - 1;
> -	j = 0;
> -	prev_j = (unsigned long)-1;
> -	for_each_clear_bit_from(j, bitmap->bitmap, BITS_PER_BITMAP) {
> -		if (j > i)
> -			break;
> -		prev_j = j;
> -	}
> +	prev_j = find_last_clear_bit_upto(bitmap->bitmap,
> +					  min(i, BITS_PER_BITMAP - 1));
>   	if (prev_j == i)
>   		return false;
>   

Re: [PATCH] btrfs: speed up steal_from_bitmap_to_front() with a backward word scan

[Qu Wenruo]

在 2026/11/14 10:55, Qu Wenruo 写道:
> 
> 
> 在 2026/11/14 10:32, Elias Jernberg 写道:
> [...]
>>
>> Fixes: 200055239604 ("Btrfs: improve free space cache management and 
>> space allocation")
>> Signed-off-by: Elias Jernberg <eliasjernberg@gmail.com>
>> ---
>>
>> Notes:
>>      - The numbers above come from a 7.3-based tree (aurora-silicon/ 
>> linux,
>>        Apple M5 MacBook Pro, 16K pages) carrying this change in an
>>        equivalent form. This version was build-tested on btrfs for-next
>>        (3aefd67f08f8) as x86_64 UML with W=1, no new warnings, and the 
>> btrfs
>>        self-tests pass (CONFIG_BTRFS_FS_RUN_SANITY_TESTS, including the
>>        bitmap stealing tests).
>>      - On x86_64 with 4K pages I could not reproduce a clear stall 
>> with the
>>        similar fragmenting workload (sync after the delete took 
>> 0.4-1.9 s), so the
>>        effect looks tied to the larger bitmaps of 16K and 64K pages.
> 
> I'm more interested on the page size bounding part.
> 
> As btrfs_free_space_bitmap_cachep is using fixed PAGE_SIZE for the 
> allocation, it's causing the behavior difference in the first place.
> 
> I'm wondering if we should make the bitmap size not bounded to 
> PAGE_SIZE, but the sectorsize of each filesystem.
> 
> Have you tried 16K page size with 16K sector size? (along with changed 
> blocksize in the fio)
> Did that can reproduce the same latency?

My bad, that won't change the bitmap size.

Instead what about the following change? Would it resolve the latency 
problem on 16K page sized systems?

diff --git a/fs/btrfs/free-space-cache.c b/fs/btrfs/free-space-cache.c
index bff6e5b372d6..4250792a3b9c 100644
--- a/fs/btrfs/free-space-cache.c
+++ b/fs/btrfs/free-space-cache.c
@@ -29,7 +29,7 @@
  #include "super.h"
  #include "relocation.h"

-#define BITS_PER_BITMAP                (PAGE_SIZE * 8UL)
+#define BITS_PER_BITMAP                (SZ_4K * 8UL)
  #define MAX_CACHE_BYTES_PER_GIG        SZ_64K
  #define FORCE_EXTENT_THRESHOLD SZ_1M

@@ -279,7 +279,7 @@ static void recalculate_thresholds(struct 
btrfs_free_space_ctl *ctl)
         else
                 max_bytes = MAX_CACHE_BYTES_PER_GIG * div_u64(size, SZ_1G);

-       bitmap_bytes = ctl->total_bitmaps * unit;
+       bitmap_bytes = ctl->total_bitmaps * SZ_4K;

         /*
          * we want the extent entry threshold to always be at most 1/2 
the max
@@ -2910,7 +2910,7 @@ int __init btrfs_free_space_init(void)
                 return -ENOMEM;

         btrfs_free_space_bitmap_cachep = 
kmem_cache_create("btrfs_free_space_bitmap",
-                                                       PAGE_SIZE, 
PAGE_SIZE,
+                                                       SZ_4K, SZ_4K,
                                                         0, NULL);
         if (!btrfs_free_space_bitmap_cachep) {
                 kmem_cache_destroy(btrfs_free_space_cachep);

> 
> Thanks,
> Qu
> 
>>      - Reproducer (fio, run on the btrfs filesystem under test):
>>          fio --name=a --filename=f --rw=write --bs=1M --direct=1 -- 
>> size=4G --end_fsync=1
>>          fio --name=r --filename=f --rw=randwrite --bs=4k -- 
>> ioengine=libaio --iodepth=32 \
>>              --direct=1 --size=4G --time_based --runtime=15 --end_fsync=1
>>          fio --name=s --filename=f --rw=write --bs=4k --direct=1 -- 
>> size=4G \
>>              --time_based --runtime=15 --fsync=1
>>          rm f
>>          fio --name=b --filename=f --rw=write --bs=1M --size=4G -- 
>> end_fsync=1
>>        The last job takes 29-36 s without this patch and under 1 s 
>> with it.
>>      - Prior art: Yun Levi suggested replacing this loop in December 
>> 2020 on
>>        LKML, as a user of a proposed find_prev_zero_bit()
>>        (https://www.mail-archive.com/linux-kernel@vger.kernel.org/ 
>> msg2402457.html).
>>        That helper was never added and the loop is unchanged in for-next.
>>        This version keeps the backward scan local to free-space-cache.c.
>>      - Tool use: the stall was profiled, the fix written and the 
>> changelog
>>        drafted with an LLM coding assistant (Claude). I have reviewed the
>>        change; the equivalence test and the measurements were run on my
>>        machine.
>>
>>   fs/btrfs/free-space-cache.c | 30 ++++++++++++++++++++++--------
>>   1 file changed, 22 insertions(+), 8 deletions(-)
>>
>> diff --git a/fs/btrfs/free-space-cache.c b/fs/btrfs/free-space-cache.c
>> index bff6e5b372d6..c599a8f25821 100644
>> --- a/fs/btrfs/free-space-cache.c
>> +++ b/fs/btrfs/free-space-cache.c
>> @@ -1269,6 +1269,26 @@ static bool steal_from_bitmap_to_end(struct 
>> btrfs_free_space_ctl *ctl,
>>       return true;
>>   }
>> +/*
>> + * Return the index of the last clear bit at or below @bit, or 
>> ULONG_MAX if
>> + * bits 0 to @bit are all set.  Scan backwards a word at a time, so 
>> the cost
>> + * follows the length of the run of set bits that ends at @bit rather 
>> than the
>> + * number of clear bits below it.
>> + */
>> +static unsigned long find_last_clear_bit_upto(const unsigned long 
>> *bitmap,
>> +                          unsigned long bit)
>> +{
>> +    unsigned long idx = BIT_WORD(bit);
>> +    unsigned long word = ~bitmap[idx] & BITMAP_LAST_WORD_MASK(bit + 1);
>> +
>> +    while (!word) {
>> +        if (idx == 0)
>> +            return ULONG_MAX;
>> +        word = ~bitmap[--idx];
>> +    }
>> +    return idx * BITS_PER_LONG + __fls(word);
>> +}
>> +
>>   static bool steal_from_bitmap_to_front(struct btrfs_free_space_ctl 
>> *ctl,
>>                          struct btrfs_free_space *info,
>>                          bool update_stat)
>> @@ -1277,7 +1297,6 @@ static bool steal_from_bitmap_to_front(struct 
>> btrfs_free_space_ctl *ctl,
>>       struct btrfs_free_space *bitmap;
>>       u64 bitmap_offset;
>>       unsigned long i;
>> -    unsigned long j;
>>       unsigned long prev_j;
>>       u64 bytes;
>> @@ -1294,13 +1313,8 @@ static bool steal_from_bitmap_to_front(struct 
>> btrfs_free_space_ctl *ctl,
>>           return false;
>>       i = offset_to_bit(bitmap->offset, unit, info->offset) - 1;
>> -    j = 0;
>> -    prev_j = (unsigned long)-1;
>> -    for_each_clear_bit_from(j, bitmap->bitmap, BITS_PER_BITMAP) {
>> -        if (j > i)
>> -            break;
>> -        prev_j = j;
>> -    }
>> +    prev_j = find_last_clear_bit_upto(bitmap->bitmap,
>> +                      min(i, BITS_PER_BITMAP - 1));
>>       if (prev_j == i)
>>           return false;
> 

Re: [PATCH] btrfs: speed up steal_from_bitmap_to_front() with a backward word scan

[Elias Jernberg]

(Resent to the list in plain text; my first copy was rejected as
HTML. Qu, David, Filipe and Chris already have it, sorry for the
duplicate.)

On 2026/11/14 11:11, Qu Wenruo wrote:
> Would it resolve the latency problem on 16K page sized systems?

It helps a lot, but not fully, and on top of my patch it adds nothing
measurable in this test.

I measured on an Apple M5 MacBook Pro (16K pages) running a 7.3 based
Asahi style tree, btrfs with 4K sectorsize, space_cache=v2,
compress=zstd:3, discard=async. The test writes a 4 GiB file into a
fragmented free space (about 1.05M extents), removes it, then times a
buffered 4 GiB write plus fsync. Two runs per kernel:

  kernel                      time (s)            MB/s
  neither (older base)        36.1 / 33.6 / 29.3  119 / 128 / 147
  your diff only              4.47 / 3.20         1106 / 1578
  my patch only               1.28 / 1.23         5107 / 4881
  your diff + my patch        1.40 / 1.34         4308 / 4559

The "neither" numbers are from an earlier measurement on an older base
of the same tree; I did not build a third kernel on the current base
without both changes. The other three share the same base and config.

A sysrq-l sample on the "your diff only" kernel still lands in
_find_next_zero_bit() called from steal_from_bitmap(), so the bit by bit
walk is still the hot spot, now over 32768 bits instead of 131072.

So with 4K bitmaps alone it is about 10x better here, but still 3 to
4 times slower than the backward word scan. On top of the word scan
I see no gain from the smaller bitmaps in this test (slightly lower,
within the noise of two runs). I have not measured other workloads,
64K pages, or anything where the extra bitmap count could matter.

Two notes on your diff:

1) fs/btrfs/tests/free-space-tests.c has its own
   #define BITS_PER_BITMAP (PAGE_SIZE * 8UL), which would need the same
   change. I did not run the sanity tests with your diff.

2) The tree I tested on is 7.3 based and still has the v1 cache
   load/write path, where io_ctl_add_bitmap() and io_ctl_read_bitmap()
   use copy_page(). With 4K bitmaps on a 16K page kernel that copies
   past the 4K slab object, so for the test kernels I replaced it with
   a memcpy() of BITS_PER_BITMAP / BITS_PER_BYTE (not exercised, the
   filesystem uses space_cache=v2). for-next has removed that path,
   so this only matters for a backport.

My reading of the numbers is that the word scan is the part that
fixes the latency on large page systems, and the 4K bitmaps are an
independent change on top of it.

Thanks,
Elias