[PATCH] btrfs: fix embarrassing bugs in find_next_dirty_byte()

[PATCH] btrfs: fix embarrassing bugs in find_next_dirty_byte()

[Qu Wenruo]

There are several bugs in find_next_dirty_byte():

- Wrong right shift
  int nbits = (orig_start - page_offset(page)) >> fs_info->sectorsize;

  This makes nbits to be always 0, thus find_next_dirty_byte() doesn't
  really check any range, but bit by bit check.

  This mask all other bugs in the same function.

- Wrong @first_bit_zero calculation
  The real @first_bit_zero we want should be after @first_bit_set.

All these bit dancing with tons of ASSERT() is really a waste of time.
The only reason I didn't go bitmap operations is they require unsigned
long.

But considering how many bugs there are just in this small function,
bitmap_next_set_region() should be the correct way to go.

Fix all these mess by using unsigned long for the local bitmap, and call
bitmap_next_set_region() to end all these stupid bugs.

Thankfully, this bug can be easily verify by any short fsstress/fsx run.

Please fold this fix into "btrfs: make __extent_writepage_io() only submit dirty range for subpage".

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 fs/btrfs/extent_io.c | 38 +++++++++-----------------------------
 1 file changed, 9 insertions(+), 29 deletions(-)

diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index d6a12f7e36d9..77b59ca93419 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -3877,11 +3877,12 @@ static void find_next_dirty_byte(struct btrfs_fs_info *fs_info,
 {
 	struct btrfs_subpage *subpage = (struct btrfs_subpage *)page->private;
 	u64 orig_start = *start;
-	u16 dirty_bitmap;
+	/* Declare as unsigned long so we can use bitmap ops */
+	unsigned long dirty_bitmap;
 	unsigned long flags;
-	int nbits = (orig_start - page_offset(page)) >> fs_info->sectorsize;
-	int first_bit_set;
-	int first_bit_zero;
+	int nbits = (orig_start - page_offset(page)) >> fs_info->sectorsize_bits;
+	int range_start_bit = nbits;
+	int range_end_bit;
 
 	/*
 	 * For regular sector size == page size case, since one page only
@@ -3898,31 +3899,10 @@ static void find_next_dirty_byte(struct btrfs_fs_info *fs_info,
 	dirty_bitmap = subpage->dirty_bitmap;
 	spin_unlock_irqrestore(&subpage->lock, flags);
 
-	/* Set bits lower than @nbits with 0 */
-	dirty_bitmap &= ~((1 << nbits) - 1);
-
-	first_bit_set = ffs(dirty_bitmap);
-	/* No dirty range found */
-	if (first_bit_set == 0) {
-		*start = page_offset(page) + PAGE_SIZE;
-		return;
-	}
-
-	ASSERT(first_bit_set > 0 && first_bit_set <= BTRFS_SUBPAGE_BITMAP_SIZE);
-	*start = page_offset(page) + (first_bit_set - 1) * fs_info->sectorsize;
-
-	/* Set all bits lower than @nbits to 1 for ffz() */
-	dirty_bitmap |= ((1 << nbits) - 1);
-
-	first_bit_zero = ffz(dirty_bitmap);
-	if (first_bit_zero == 0 || first_bit_zero > BTRFS_SUBPAGE_BITMAP_SIZE) {
-		*end = page_offset(page) + PAGE_SIZE;
-		return;
-	}
-	ASSERT(first_bit_zero > 0 &&
-	       first_bit_zero <= BTRFS_SUBPAGE_BITMAP_SIZE);
-	*end = page_offset(page) + first_bit_zero * fs_info->sectorsize;
-	ASSERT(*end > *start);
+	bitmap_next_set_region(&dirty_bitmap, &range_start_bit, &range_end_bit,
+			       BTRFS_SUBPAGE_BITMAP_SIZE);
+	*start = page_offset(page) + range_start_bit * fs_info->sectorsize;
+	*end = page_offset(page) + range_end_bit * fs_info->sectorsize;
 }
 
 /*
-- 
2.31.1

Re: [PATCH] btrfs: fix embarrassing bugs in find_next_dirty_byte()

[David Sterba]

On Sat, Jun 05, 2021 at 08:14:28AM +0800, Qu Wenruo wrote:
> There are several bugs in find_next_dirty_byte():
> 
> - Wrong right shift
>   int nbits = (orig_start - page_offset(page)) >> fs_info->sectorsize;
> 
>   This makes nbits to be always 0, thus find_next_dirty_byte() doesn't
>   really check any range, but bit by bit check.
> 
>   This mask all other bugs in the same function.
> 
> - Wrong @first_bit_zero calculation
>   The real @first_bit_zero we want should be after @first_bit_set.
> 
> All these bit dancing with tons of ASSERT() is really a waste of time.
> The only reason I didn't go bitmap operations is they require unsigned
> long.
> 
> But considering how many bugs there are just in this small function,
> bitmap_next_set_region() should be the correct way to go.
> 
> Fix all these mess by using unsigned long for the local bitmap, and call
> bitmap_next_set_region() to end all these stupid bugs.
> 
> Thankfully, this bug can be easily verify by any short fsstress/fsx run.
> 
> Please fold this fix into "btrfs: make __extent_writepage_io() only submit dirty range for subpage".
> 
> Signed-off-by: Qu Wenruo <wqu@suse.com>
> ---
>  fs/btrfs/extent_io.c | 38 +++++++++-----------------------------
>  1 file changed, 9 insertions(+), 29 deletions(-)
> 
> diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
> index d6a12f7e36d9..77b59ca93419 100644
> --- a/fs/btrfs/extent_io.c
> +++ b/fs/btrfs/extent_io.c
> @@ -3877,11 +3877,12 @@ static void find_next_dirty_byte(struct btrfs_fs_info *fs_info,
>  {
>  	struct btrfs_subpage *subpage = (struct btrfs_subpage *)page->private;
>  	u64 orig_start = *start;
> -	u16 dirty_bitmap;
> +	/* Declare as unsigned long so we can use bitmap ops */
> +	unsigned long dirty_bitmap;
>  	unsigned long flags;
> -	int nbits = (orig_start - page_offset(page)) >> fs_info->sectorsize;
> -	int first_bit_set;
> -	int first_bit_zero;
> +	int nbits = (orig_start - page_offset(page)) >> fs_info->sectorsize_bits;
> +	int range_start_bit = nbits;
> +	int range_end_bit;
>  
>  	/*
>  	 * For regular sector size == page size case, since one page only
> @@ -3898,31 +3899,10 @@ static void find_next_dirty_byte(struct btrfs_fs_info *fs_info,
>  	dirty_bitmap = subpage->dirty_bitmap;
>  	spin_unlock_irqrestore(&subpage->lock, flags);
>  
> -	/* Set bits lower than @nbits with 0 */
> -	dirty_bitmap &= ~((1 << nbits) - 1);
> -
> -	first_bit_set = ffs(dirty_bitmap);
> -	/* No dirty range found */
> -	if (first_bit_set == 0) {
> -		*start = page_offset(page) + PAGE_SIZE;
> -		return;
> -	}
> -
> -	ASSERT(first_bit_set > 0 && first_bit_set <= BTRFS_SUBPAGE_BITMAP_SIZE);
> -	*start = page_offset(page) + (first_bit_set - 1) * fs_info->sectorsize;
> -
> -	/* Set all bits lower than @nbits to 1 for ffz() */
> -	dirty_bitmap |= ((1 << nbits) - 1);
> -
> -	first_bit_zero = ffz(dirty_bitmap);
> -	if (first_bit_zero == 0 || first_bit_zero > BTRFS_SUBPAGE_BITMAP_SIZE) {
> -		*end = page_offset(page) + PAGE_SIZE;
> -		return;
> -	}
> -	ASSERT(first_bit_zero > 0 &&
> -	       first_bit_zero <= BTRFS_SUBPAGE_BITMAP_SIZE);
> -	*end = page_offset(page) + first_bit_zero * fs_info->sectorsize;
> -	ASSERT(*end > *start);
> +	bitmap_next_set_region(&dirty_bitmap, &range_start_bit, &range_end_bit,
> +			       BTRFS_SUBPAGE_BITMAP_SIZE);
> +	*start = page_offset(page) + range_start_bit * fs_info->sectorsize;
> +	*end = page_offset(page) + range_end_bit * fs_info->sectorsize;

Makes sense. We want the u16 for the storage but the more complex
calculations could be done using the bitmap helpers, and converted back
eventually.

Re: [PATCH] btrfs: fix embarrassing bugs in find_next_dirty_byte()

[Qu Wenruo]

On 2021/6/8 上午1:08, David Sterba wrote:
> On Sat, Jun 05, 2021 at 08:14:28AM +0800, Qu Wenruo wrote:
>> There are several bugs in find_next_dirty_byte():
>>
>> - Wrong right shift
>>    int nbits = (orig_start - page_offset(page)) >> fs_info->sectorsize;
>>
>>    This makes nbits to be always 0, thus find_next_dirty_byte() doesn't
>>    really check any range, but bit by bit check.
>>
>>    This mask all other bugs in the same function.
>>
>> - Wrong @first_bit_zero calculation
>>    The real @first_bit_zero we want should be after @first_bit_set.
>>
>> All these bit dancing with tons of ASSERT() is really a waste of time.
>> The only reason I didn't go bitmap operations is they require unsigned
>> long.
>>
>> But considering how many bugs there are just in this small function,
>> bitmap_next_set_region() should be the correct way to go.
>>
>> Fix all these mess by using unsigned long for the local bitmap, and call
>> bitmap_next_set_region() to end all these stupid bugs.
>>
>> Thankfully, this bug can be easily verify by any short fsstress/fsx run.
>>
>> Please fold this fix into "btrfs: make __extent_writepage_io() only submit dirty range for subpage".
>>
>> Signed-off-by: Qu Wenruo <wqu@suse.com>
>> ---
>>   fs/btrfs/extent_io.c | 38 +++++++++-----------------------------
>>   1 file changed, 9 insertions(+), 29 deletions(-)
>>
>> diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
>> index d6a12f7e36d9..77b59ca93419 100644
>> --- a/fs/btrfs/extent_io.c
>> +++ b/fs/btrfs/extent_io.c
>> @@ -3877,11 +3877,12 @@ static void find_next_dirty_byte(struct btrfs_fs_info *fs_info,
>>   {
>>   	struct btrfs_subpage *subpage = (struct btrfs_subpage *)page->private;
>>   	u64 orig_start = *start;
>> -	u16 dirty_bitmap;
>> +	/* Declare as unsigned long so we can use bitmap ops */
>> +	unsigned long dirty_bitmap;
>>   	unsigned long flags;
>> -	int nbits = (orig_start - page_offset(page)) >> fs_info->sectorsize;
>> -	int first_bit_set;
>> -	int first_bit_zero;
>> +	int nbits = (orig_start - page_offset(page)) >> fs_info->sectorsize_bits;
>> +	int range_start_bit = nbits;
>> +	int range_end_bit;
>>
>>   	/*
>>   	 * For regular sector size == page size case, since one page only
>> @@ -3898,31 +3899,10 @@ static void find_next_dirty_byte(struct btrfs_fs_info *fs_info,
>>   	dirty_bitmap = subpage->dirty_bitmap;
>>   	spin_unlock_irqrestore(&subpage->lock, flags);
>>
>> -	/* Set bits lower than @nbits with 0 */
>> -	dirty_bitmap &= ~((1 << nbits) - 1);
>> -
>> -	first_bit_set = ffs(dirty_bitmap);
>> -	/* No dirty range found */
>> -	if (first_bit_set == 0) {
>> -		*start = page_offset(page) + PAGE_SIZE;
>> -		return;
>> -	}
>> -
>> -	ASSERT(first_bit_set > 0 && first_bit_set <= BTRFS_SUBPAGE_BITMAP_SIZE);
>> -	*start = page_offset(page) + (first_bit_set - 1) * fs_info->sectorsize;
>> -
>> -	/* Set all bits lower than @nbits to 1 for ffz() */
>> -	dirty_bitmap |= ((1 << nbits) - 1);
>> -
>> -	first_bit_zero = ffz(dirty_bitmap);
>> -	if (first_bit_zero == 0 || first_bit_zero > BTRFS_SUBPAGE_BITMAP_SIZE) {
>> -		*end = page_offset(page) + PAGE_SIZE;
>> -		return;
>> -	}
>> -	ASSERT(first_bit_zero > 0 &&
>> -	       first_bit_zero <= BTRFS_SUBPAGE_BITMAP_SIZE);
>> -	*end = page_offset(page) + first_bit_zero * fs_info->sectorsize;
>> -	ASSERT(*end > *start);
>> +	bitmap_next_set_region(&dirty_bitmap, &range_start_bit, &range_end_bit,
>> +			       BTRFS_SUBPAGE_BITMAP_SIZE);
>> +	*start = page_offset(page) + range_start_bit * fs_info->sectorsize;
>> +	*end = page_offset(page) + range_end_bit * fs_info->sectorsize;
>
> Makes sense. We want the u16 for the storage but the more complex
> calculations could be done using the bitmap helpers, and converted back
> eventually.
>
Talking about bitmap, I think it's also a good time to consider the
future expansion.

- Extra sectorsize/page size support
   We want to support things like 16K page size, in that case we
   only needs 4 bits for each bitmap.

- Better support for nodesize >= page size case
   If we can ensure all of our metadata are nodesize aligned,
   we can fall back to existing metadata handler.
   This reduces memory usage, and can support 16K page size better.

   But the cost is, if chunk is not properly aligned, we will reject
   certain extent buffer read.

My current plan is to make btrfs_subpage bitmaps to be fitted into one
longer bitmap.
And in btrfs_info, introduce some structure to record which bit range
are for each subpage bitmap, the range will be calculated at mount time
using both sectorsize and page size.

E.g. For 4K sectorsize, 16K page size, uptodate bitmap will be at bits
range [0, 4), error bitmap will be at bits [4, 8).

Then we can make all subpage bitmap operations using real bitmap operators.

Those are all ideas though, as I'm still working on compression support
for now.

Any feedback will help.

Thanks,
Qu

Re: [PATCH] btrfs: fix embarrassing bugs in find_next_dirty_byte()

[David Sterba]

On Tue, Jun 08, 2021 at 10:02:34AM +0800, Qu Wenruo wrote:
> >> -		return;
> >> -	}
> >> -	ASSERT(first_bit_zero > 0 &&
> >> -	       first_bit_zero <= BTRFS_SUBPAGE_BITMAP_SIZE);
> >> -	*end = page_offset(page) + first_bit_zero * fs_info->sectorsize;
> >> -	ASSERT(*end > *start);
> >> +	bitmap_next_set_region(&dirty_bitmap, &range_start_bit, &range_end_bit,
> >> +			       BTRFS_SUBPAGE_BITMAP_SIZE);
> >> +	*start = page_offset(page) + range_start_bit * fs_info->sectorsize;
> >> +	*end = page_offset(page) + range_end_bit * fs_info->sectorsize;
> >
> > Makes sense. We want the u16 for the storage but the more complex
> > calculations could be done using the bitmap helpers, and converted back
> > eventually.
> >
> Talking about bitmap, I think it's also a good time to consider the
> future expansion.
> 
> - Extra sectorsize/page size support
>    We want to support things like 16K page size, in that case we
>    only needs 4 bits for each bitmap.
> 
> - Better support for nodesize >= page size case
>    If we can ensure all of our metadata are nodesize aligned,
>    we can fall back to existing metadata handler.
>    This reduces memory usage, and can support 16K page size better.
> 
>    But the cost is, if chunk is not properly aligned, we will reject
>    certain extent buffer read.
> 
> My current plan is to make btrfs_subpage bitmaps to be fitted into one
> longer bitmap.
> And in btrfs_info, introduce some structure to record which bit range
> are for each subpage bitmap, the range will be calculated at mount time
> using both sectorsize and page size.
> 
> E.g. For 4K sectorsize, 16K page size, uptodate bitmap will be at bits
> range [0, 4), error bitmap will be at bits [4, 8).
> 
> Then we can make all subpage bitmap operations using real bitmap operators.

Great, I had the same idea to merge all bitmaps into one value. For
clarity the first implementation has it all separated as we don't want
to hunt bugs in the bit manipulations.