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

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 <redacted>
---
 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

On Sat, Jun 05, 2021 at 08:14:28AM +0800, Qu Wenruo wrote:

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.

On 2021/6/8 上午1:08, David Sterba wrote:

On Sat, Jun 05, 2021 at 08:14:28AM +0800, Qu Wenruo wrote:

quoted

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 <redacted>
---
  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

On Tue, Jun 08, 2021 at 10:02:34AM +0800, Qu Wenruo wrote:

quoted

quoted

-		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.