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

[Qu Wenruo <wqu@suse.com>]

在 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;
>