[PATCH 0/4] Further FITRIM improvements

[PATCH 0/4] Further FITRIM improvements

[Nikolay Borisov]

Qu reported beyond EOD (end of device) access with latest FITRIM improvements 
that were merged. Further testing also showed that if ranged FITRIM request is 
sent it's possible to cause u64 overflow which in turn cause calculations to 
go off rail in btrfs_issue_discard (because it's called with start and len 
as (u64)-1) and trim used data. 

This patchset aims to rectify this by: 

1. Documenting the internal __etree_search since due to the rather high 
number of output parameters it can be a bit confusing as to what the invariants 
are. Due to this I got initially confused about possible return values on 
boundary conditions. (Patch 1)

2. Remove ranged support in btrfs_trim_free_extents - having range support in 
btrfs_trim_free_extent is problematic because it's interpreted in device physical 
space whilst range values from userspace should always be interpreted in 
logical space. (Patch 2)

3. Change slightly the semantics of find_first_clear_extent_bit to return the 
range that contains the passed address or in case no such range exists the 
next one, document the function and finally add tests (Patch 3 preps 
btrfs_trim_free_extents to handle the change semantics and Patch 4 change 
the semantics). 

This has been fully tested with xfstest and no regressions were found. 

Nikolay Borisov (4):
  btrfs: Document __etree_search
  btrfs: Always trim all unallocated space in btrfs_trim_free_extents
  btrfs: Skip first megabyte on device when trimming
  btrfs: Don't trim returned range based on input value in
    find_first_clear_extent_bit

 fs/btrfs/extent-tree.c           | 32 +++---------
 fs/btrfs/extent_io.c             | 67 +++++++++++++++++++++---
 fs/btrfs/tests/extent-io-tests.c | 89 ++++++++++++++++++++++++++++++++
 3 files changed, 157 insertions(+), 31 deletions(-)

-- 
2.17.1

[PATCH 1/4] btrfs: Document __etree_search

[Nikolay Borisov]

The function has a lot of return values and specific conventions making
it cumbersome to understand what's returned. Have a go at documenting
its parameters and return values.

Signed-off-by: Nikolay Borisov <nborisov@suse.com>
---
 fs/btrfs/extent_io.c | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)

diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index e56afb826517..d5979558c96f 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -359,6 +359,22 @@ static struct rb_node *tree_insert(struct rb_root *root,
 	return NULL;
 }
 
+/**
+ * __etree_search - searches @tree for an entry that contains @offset. Such
+ * entry would have entry->start <= offset && entry->end >= offset.
+ *
+ * @offset - offset that should fall within an entry in @tree
+ * @next_ret - pointer to the first entry whose range ends after @offset
+ * @prev - pointer to the first entry whose range begins before @offset
+ * @p_ret - pointer where new node should be anchored (used when inserting an
+ *	    entry in the tree)
+ * @parent_ret - points to entry which would have been the parent of the entry,
+ * containing @offset
+ *
+ * This function returns a pointer to the entry that contains @offset byte
+ * address. If no such entry exists, then NULL is returned and the other
+ * pointer arguments to the function are filled.
+ */
 static struct rb_node *__etree_search(struct extent_io_tree *tree, u64 offset,
 				      struct rb_node **next_ret,
 				      struct rb_node **prev_ret,
-- 
2.17.1

Re: [PATCH 1/4] btrfs: Document __etree_search

[Johannes Thumshirn]

On Mon, Jun 03, 2019 at 01:05:59PM +0300, Nikolay Borisov wrote:
> The function has a lot of return values and specific conventions making
> it cumbersome to understand what's returned. Have a go at documenting
> its parameters and return values.
> 
> Signed-off-by: Nikolay Borisov <nborisov@suse.com>
> ---
>  fs/btrfs/extent_io.c | 16 ++++++++++++++++
>  1 file changed, 16 insertions(+)
> 
> diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
> index e56afb826517..d5979558c96f 100644
> --- a/fs/btrfs/extent_io.c
> +++ b/fs/btrfs/extent_io.c
> @@ -359,6 +359,22 @@ static struct rb_node *tree_insert(struct rb_root *root,
>  	return NULL;
>  }
>  
> +/**
> + * __etree_search - searches @tree for an entry that contains @offset. Such
> + * entry would have entry->start <= offset && entry->end >= offset.
> + *

This is missing @tree, make W=1 should warn about this.

> + * @offset - offset that should fall within an entry in @tree
> + * @next_ret - pointer to the first entry whose range ends after @offset
> + * @prev - pointer to the first entry whose range begins before @offset
> + * @p_ret - pointer where new node should be anchored (used when inserting an
> + *	    entry in the tree)
> + * @parent_ret - points to entry which would have been the parent of the entry,
> + * containing @offset
> + *
> + * This function returns a pointer to the entry that contains @offset byte
> + * address. If no such entry exists, then NULL is returned and the other
> + * pointer arguments to the function are filled.
> + */
>  static struct rb_node *__etree_search(struct extent_io_tree *tree, u64 offset,
>  				      struct rb_node **next_ret,
>  				      struct rb_node **prev_ret,
> -- 
> 2.17.1
> 

-- 
Johannes Thumshirn                            SUSE Labs Filesystems
jthumshirn@suse.de                                +49 911 74053 689
SUSE LINUX GmbH, Maxfeldstr. 5, 90409 Nürnberg
GF: Felix Imendörffer, Mary Higgins, Sri Rasiah
HRB 21284 (AG Nürnberg)
Key fingerprint = EC38 9CAB C2C4 F25D 8600 D0D0 0393 969D 2D76 0850

Re: [PATCH 1/4] btrfs: Document __etree_search

[Qu Wenruo]

On 2019/6/3 下午6:05, Nikolay Borisov wrote:
> The function has a lot of return values and specific conventions making
> it cumbersome to understand what's returned. Have a go at documenting
> its parameters and return values.
>
> Signed-off-by: Nikolay Borisov <nborisov@suse.com>

The idea is pretty good, will help later readers.

Reviewed-by: Qu Wenruo <wqu@suse.com>

Just a small nitpick inlined below.

> ---
>  fs/btrfs/extent_io.c | 16 ++++++++++++++++
>  1 file changed, 16 insertions(+)
>
> diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
> index e56afb826517..d5979558c96f 100644
> --- a/fs/btrfs/extent_io.c
> +++ b/fs/btrfs/extent_io.c
> @@ -359,6 +359,22 @@ static struct rb_node *tree_insert(struct rb_root *root,
>  	return NULL;
>  }
>
> +/**
> + * __etree_search - searches @tree for an entry that contains @offset. Such
> + * entry would have entry->start <= offset && entry->end >= offset.
> + *
> + * @offset - offset that should fall within an entry in @tree
> + * @next_ret - pointer to the first entry whose range ends after @offset
> + * @prev - pointer to the first entry whose range begins before @offset
> + * @p_ret - pointer where new node should be anchored (used when inserting an
> + *	    entry in the tree)
> + * @parent_ret - points to entry which would have been the parent of the entry,
> + * containing @offset
> + *
> + * This function returns a pointer to the entry that contains @offset byte
> + * address.

it would be better to mention when found, the remaining pointers are
untouched.

> If no such entry exists, then NULL is returned and the other
> + * pointer arguments to the function are filled.
> + */
>  static struct rb_node *__etree_search(struct extent_io_tree *tree, u64 offset,
>  				      struct rb_node **next_ret,
>  				      struct rb_node **prev_ret,
>

[PATCH v2] btrfs: Document __etree_search

[Nikolay Borisov]

The function has a lot of return values and specific conventions making
it cumbersome to understand what's returned. Have a go at documenting
its parameters and return values.

Signed-off-by: Nikolay Borisov <nborisov@suse.com>
---

* Document 'tree' argument to silence error (Johaness)
* Document that if a range is found then none of the input pointers is 
touched (Qu)
 fs/btrfs/extent_io.c | 18 ++++++++++++++++++
 1 file changed, 18 insertions(+)

diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index e56afb826517..d7913f42327c 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -359,6 +359,24 @@ static struct rb_node *tree_insert(struct rb_root *root,
 	return NULL;
 }
 
+/**
+ * __etree_search - searches @tree for an entry that contains @offset. Such
+ * entry would have entry->start <= offset && entry->end >= offset.
+ *
+ * @tree - the tree to search
+ * @offset - offset that should fall within an entry in @tree
+ * @next_ret - pointer to the first entry whose range ends after @offset
+ * @prev - pointer to the first entry whose range begins before @offset
+ * @p_ret - pointer where new node should be anchored (used when inserting an
+ *	    entry in the tree)
+ * @parent_ret - points to entry which would have been the parent of the entry,
+ * containing @offset
+ *
+ * This function returns a pointer to the entry that contains @offset byte
+ * address. If no such entry exists, then NULL is returned and the other
+ * pointer arguments to the function are filled, otherwise the found entry is
+ * return and other pointers are left untouched.
+ */
 static struct rb_node *__etree_search(struct extent_io_tree *tree, u64 offset,
 				      struct rb_node **next_ret,
 				      struct rb_node **prev_ret,
-- 
2.17.1

Re: [PATCH v2] btrfs: Document __etree_search

[Johannes Thumshirn]

Looks good,
Reviewed-by: Johannes Thumshirn <jthumshirn@suse.de>
-- 
Johannes Thumshirn                            SUSE Labs Filesystems
jthumshirn@suse.de                                +49 911 74053 689
SUSE LINUX GmbH, Maxfeldstr. 5, 90409 Nürnberg
GF: Felix Imendörffer, Mary Higgins, Sri Rasiah
HRB 21284 (AG Nürnberg)
Key fingerprint = EC38 9CAB C2C4 F25D 8600 D0D0 0393 969D 2D76 0850

[PATCH 2/4] btrfs: Always trim all unallocated space in btrfs_trim_free_extents

[Nikolay Borisov]

This patch removes support for range parameters of FITRIM ioctl when
trimming unallocated space on devices. This is necessary since ranges
passed from user space are generally interpreted as logical addresses,
whereas btrfs_trim_free_extents used to interpret them as device
physical extents. This could result in counter-intuitive behavior for
users so it's best to remove that support altogether.

Additionally, the existing range support had a bug where if an offset
was passed to FITRIM which overflows u64 e.g. -1 (parsed as u64
18446744073709551615) then wrong data was fed into btrfs_issue_discard,
which in turn leads to wrap-around when aligning the passed range and
results in wrong regions being discarded which leads to data corruption.

Signed-off-by: Nikolay Borisov <nborisov@suse.com>
---
 fs/btrfs/extent-tree.c | 28 +++-------------------------
 1 file changed, 3 insertions(+), 25 deletions(-)

diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index 96628eb4b389..d8c5febf7636 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -11145,13 +11145,11 @@ int btrfs_error_unpin_extent_range(struct btrfs_fs_info *fs_info,
  * it while performing the free space search since we have already
  * held back allocations.
  */
-static int btrfs_trim_free_extents(struct btrfs_device *device,
-				   struct fstrim_range *range, u64 *trimmed)
+static int btrfs_trim_free_extents(struct btrfs_device *device, u64 *trimmed)
 {
-	u64 start, len = 0, end = 0;
+	u64 start = SZ_1M, len = 0, end = 0;
 	int ret;
 
-	start = max_t(u64, range->start, SZ_1M);
 	*trimmed = 0;
 
 	/* Discard not supported = nothing to do. */
@@ -11194,22 +11192,6 @@ static int btrfs_trim_free_extents(struct btrfs_device *device,
 			break;
 		}
 
-		/* Keep going until we satisfy minlen or reach end of space */
-		if (len < range->minlen) {
-			mutex_unlock(&fs_info->chunk_mutex);
-			start += len;
-			continue;
-		}
-
-		/* If we are out of the passed range break */
-		if (start > range->start + range->len - 1) {
-			mutex_unlock(&fs_info->chunk_mutex);
-			break;
-		}
-
-		start = max(range->start, start);
-		len = min(range->len, len);
-
 		ret = btrfs_issue_discard(device->bdev, start, len,
 					  &bytes);
 		if (!ret)
@@ -11224,10 +11206,6 @@ static int btrfs_trim_free_extents(struct btrfs_device *device,
 		start += len;
 		*trimmed += bytes;
 
-		/* We've trimmed enough */
-		if (*trimmed >= range->len)
-			break;
-
 		if (fatal_signal_pending(current)) {
 			ret = -ERESTARTSYS;
 			break;
@@ -11311,7 +11289,7 @@ int btrfs_trim_fs(struct btrfs_fs_info *fs_info, struct fstrim_range *range)
 	mutex_lock(&fs_info->fs_devices->device_list_mutex);
 	devices = &fs_info->fs_devices->devices;
 	list_for_each_entry(device, devices, dev_list) {
-		ret = btrfs_trim_free_extents(device, range, &group_trimmed);
+		ret = btrfs_trim_free_extents(device, &group_trimmed);
 		if (ret) {
 			dev_failed++;
 			dev_ret = ret;
-- 
2.17.1

Re: [PATCH 2/4] btrfs: Always trim all unallocated space in btrfs_trim_free_extents

[Qu Wenruo]

On 2019/6/3 下午6:06, Nikolay Borisov wrote:
> This patch removes support for range parameters of FITRIM ioctl when
> trimming unallocated space on devices. This is necessary since ranges
> passed from user space are generally interpreted as logical addresses,
> whereas btrfs_trim_free_extents used to interpret them as device
> physical extents. This could result in counter-intuitive behavior for
> users so it's best to remove that support altogether.
>
> Additionally, the existing range support had a bug where if an offset
> was passed to FITRIM which overflows u64 e.g. -1 (parsed as u64
> 18446744073709551615) then wrong data was fed into btrfs_issue_discard,
> which in turn leads to wrap-around when aligning the passed range and
> results in wrong regions being discarded which leads to data corruption.
>
> Signed-off-by: Nikolay Borisov <nborisov@suse.com>

Reveiwed-by: Qu Wenruo <wqu@suse.com>

Thanks,
Qu

> ---
>  fs/btrfs/extent-tree.c | 28 +++-------------------------
>  1 file changed, 3 insertions(+), 25 deletions(-)
>
> diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
> index 96628eb4b389..d8c5febf7636 100644
> --- a/fs/btrfs/extent-tree.c
> +++ b/fs/btrfs/extent-tree.c
> @@ -11145,13 +11145,11 @@ int btrfs_error_unpin_extent_range(struct btrfs_fs_info *fs_info,
>   * it while performing the free space search since we have already
>   * held back allocations.
>   */
> -static int btrfs_trim_free_extents(struct btrfs_device *device,
> -				   struct fstrim_range *range, u64 *trimmed)
> +static int btrfs_trim_free_extents(struct btrfs_device *device, u64 *trimmed)
>  {
> -	u64 start, len = 0, end = 0;
> +	u64 start = SZ_1M, len = 0, end = 0;
>  	int ret;
>
> -	start = max_t(u64, range->start, SZ_1M);
>  	*trimmed = 0;
>
>  	/* Discard not supported = nothing to do. */
> @@ -11194,22 +11192,6 @@ static int btrfs_trim_free_extents(struct btrfs_device *device,
>  			break;
>  		}
>
> -		/* Keep going until we satisfy minlen or reach end of space */
> -		if (len < range->minlen) {
> -			mutex_unlock(&fs_info->chunk_mutex);
> -			start += len;
> -			continue;
> -		}
> -
> -		/* If we are out of the passed range break */
> -		if (start > range->start + range->len - 1) {
> -			mutex_unlock(&fs_info->chunk_mutex);
> -			break;
> -		}
> -
> -		start = max(range->start, start);
> -		len = min(range->len, len);
> -
>  		ret = btrfs_issue_discard(device->bdev, start, len,
>  					  &bytes);
>  		if (!ret)
> @@ -11224,10 +11206,6 @@ static int btrfs_trim_free_extents(struct btrfs_device *device,
>  		start += len;
>  		*trimmed += bytes;
>
> -		/* We've trimmed enough */
> -		if (*trimmed >= range->len)
> -			break;
> -
>  		if (fatal_signal_pending(current)) {
>  			ret = -ERESTARTSYS;
>  			break;
> @@ -11311,7 +11289,7 @@ int btrfs_trim_fs(struct btrfs_fs_info *fs_info, struct fstrim_range *range)
>  	mutex_lock(&fs_info->fs_devices->device_list_mutex);
>  	devices = &fs_info->fs_devices->devices;
>  	list_for_each_entry(device, devices, dev_list) {
> -		ret = btrfs_trim_free_extents(device, range, &group_trimmed);
> +		ret = btrfs_trim_free_extents(device, &group_trimmed);
>  		if (ret) {
>  			dev_failed++;
>  			dev_ret = ret;
>

[PATCH 3/4] btrfs: Skip first megabyte on device when trimming

[Nikolay Borisov]

Currently the first megabyte on a device housing a btrfs filesystem is
exempt from allocation and trimming. Currently this is not a problem
since 'start' is set to 1m at the beginning of btrfs_trim_free_extents
and find_first_clear_extent_bit always returns a range that is >= start.
However, in a follow up patch find_first_clear_extent_bit will be
changed such that it will return a range containing 'start' and this
range may very well be 0...>=1M so 'start'.

Future proof the sole user of find_first_clear_extent_bit by setting
'start' after the function is called. No functional changes.

Signed-off-by: Nikolay Borisov <nborisov@suse.com>
---
 fs/btrfs/extent-tree.c | 4 ++++
 1 file changed, 4 insertions(+)

diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index d8c5febf7636..5a11e4988243 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -11183,6 +11183,10 @@ static int btrfs_trim_free_extents(struct btrfs_device *device, u64 *trimmed)
 		 * to the caller to trim the value to the size of the device.
 		 */
 		end = min(end, device->total_bytes - 1);
+
+		/* Ensure we skip first mb in case we have a bootloader there */
+		start = max_t(u64, start, SZ_1M);
+
 		len = end - start + 1;
 
 		/* We didn't find any extents */
-- 
2.17.1

Re: [PATCH 3/4] btrfs: Skip first megabyte on device when trimming

[Johannes Thumshirn]

Looks good,
Reviewed-by: Johannes Thumshirn <jthumshirn@suse.de>
-- 
Johannes Thumshirn                            SUSE Labs Filesystems
jthumshirn@suse.de                                +49 911 74053 689
SUSE LINUX GmbH, Maxfeldstr. 5, 90409 Nürnberg
GF: Felix Imendörffer, Mary Higgins, Sri Rasiah
HRB 21284 (AG Nürnberg)
Key fingerprint = EC38 9CAB C2C4 F25D 8600 D0D0 0393 969D 2D76 0850

Re: [PATCH 3/4] btrfs: Skip first megabyte on device when trimming

[Qu Wenruo]

On 2019/6/3 下午6:06, Nikolay Borisov wrote:
> Currently the first megabyte on a device housing a btrfs filesystem is
> exempt from allocation and trimming. Currently this is not a problem
> since 'start' is set to 1m at the beginning of btrfs_trim_free_extents
> and find_first_clear_extent_bit always returns a range that is >= start.
> However, in a follow up patch find_first_clear_extent_bit will be
> changed such that it will return a range containing 'start' and this
> range may very well be 0...>=1M so 'start'.
>
> Future proof the sole user of find_first_clear_extent_bit by setting
> 'start' after the function is called. No functional changes.
>
> Signed-off-by: Nikolay Borisov <nborisov@suse.com>

Doesn't that previous patch already address this by:

+	u64 start = SZ_1M, len = 0, end = 0;

Thanks,
Qu


> ---
>  fs/btrfs/extent-tree.c | 4 ++++
>  1 file changed, 4 insertions(+)
>
> diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
> index d8c5febf7636..5a11e4988243 100644
> --- a/fs/btrfs/extent-tree.c
> +++ b/fs/btrfs/extent-tree.c
> @@ -11183,6 +11183,10 @@ static int btrfs_trim_free_extents(struct btrfs_device *device, u64 *trimmed)
>  		 * to the caller to trim the value to the size of the device.
>  		 */
>  		end = min(end, device->total_bytes - 1);
> +
> +		/* Ensure we skip first mb in case we have a bootloader there */
> +		start = max_t(u64, start, SZ_1M);
> +
>  		len = end - start + 1;
>
>  		/* We didn't find any extents */
>

Re: [PATCH 3/4] btrfs: Skip first megabyte on device when trimming

[Nikolay Borisov]

On 5.06.19 г. 12:14 ч., Qu Wenruo wrote:
> 
> 
> On 2019/6/3 下午6:06, Nikolay Borisov wrote:
>> Currently the first megabyte on a device housing a btrfs filesystem is
>> exempt from allocation and trimming. Currently this is not a problem
>> since 'start' is set to 1m at the beginning of btrfs_trim_free_extents
>> and find_first_clear_extent_bit always returns a range that is >= start.
>> However, in a follow up patch find_first_clear_extent_bit will be
>> changed such that it will return a range containing 'start' and this
>> range may very well be 0...>=1M so 'start'.
>>
>> Future proof the sole user of find_first_clear_extent_bit by setting
>> 'start' after the function is called. No functional changes.
>>
>> Signed-off-by: Nikolay Borisov <nborisov@suse.com>
> 
> Doesn't that previous patch already address this by:
> 
> +	u64 start = SZ_1M, len = 0, end = 0;

No, because with the changes introduced in the next patch start can
actually be made to point to 0 for example. One of the self-test cases
covers this, e.g. :

find_first_clear_extent_bit(&tree, SZ_512K, &start, &end,
+				    CHUNK_TRIMMED | CHUNK_ALLOCATED);

> 
> Thanks,
> Qu
> 
> 
>> ---
>>  fs/btrfs/extent-tree.c | 4 ++++
>>  1 file changed, 4 insertions(+)
>>
>> diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
>> index d8c5febf7636..5a11e4988243 100644
>> --- a/fs/btrfs/extent-tree.c
>> +++ b/fs/btrfs/extent-tree.c
>> @@ -11183,6 +11183,10 @@ static int btrfs_trim_free_extents(struct btrfs_device *device, u64 *trimmed)
>>  		 * to the caller to trim the value to the size of the device.
>>  		 */
>>  		end = min(end, device->total_bytes - 1);
>> +
>> +		/* Ensure we skip first mb in case we have a bootloader there */
>> +		start = max_t(u64, start, SZ_1M);
>> +
>>  		len = end - start + 1;
>>
>>  		/* We didn't find any extents */
>>
> 

[PATCH 4/4] btrfs: Don't trim returned range based on input value in find_first_clear_extent_bit

[Nikolay Borisov]

Currently find_first_clear_extent_bit always returns a range whose
starting value is >= passed 'start'. This implicit trimming behavior is
somewhat subtle and an implementation detail. Instead, this patch
modifies the function such that now it always returns the range which
contains passed 'start' and has the given bits unset. This range could
either be due to presence of existing records which contains 'start'
but have the bits unset or because there are no records that contain
the given starting offset.

This patch also adds test cases which cover find_first_clear_extent_bit
since they were missing up until now.

Signed-off-by: Nikolay Borisov <nborisov@suse.com>
---
 fs/btrfs/extent_io.c             | 51 +++++++++++++++---
 fs/btrfs/tests/extent-io-tests.c | 89 ++++++++++++++++++++++++++++++++
 2 files changed, 134 insertions(+), 6 deletions(-)

diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index d5979558c96f..1dd900cfb7ea 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -1553,8 +1553,8 @@ int find_first_extent_bit(struct extent_io_tree *tree, u64 start,
 }
 
 /**
- * find_first_clear_extent_bit - finds the first range that has @bits not set
- * and that starts after @start
+ * find_first_clear_extent_bit - finds the first range that has @bits not set.
+ * This range could start before @start.
  *
  * @tree - the tree to search
  * @start - the offset at/after which the found extent should start
@@ -1594,12 +1594,51 @@ void find_first_clear_extent_bit(struct extent_io_tree *tree, u64 start,
 				goto out;
 			}
 		}
+		/*
+		 * At this point 'node' either contains 'start' or start is
+		 * before 'node'
+		 */
 		state = rb_entry(node, struct extent_state, rb_node);
-		if (in_range(start, state->start, state->end - state->start + 1) &&
-			(state->state & bits)) {
-			start = state->end + 1;
+
+		if (in_range(start, state->start, state->end - state->start + 1)) {
+			if (state->state & bits) {
+				/*
+				 * |--range with bits sets--|
+				 *    |
+				 *    start
+				 */
+				start = state->end + 1;
+			} else {
+				/*
+				 * 'start' falls within a range that doesn't
+				 * have the bits set, so take its start as
+				 * the beginning of the desire range
+				 *
+				 * |--range with bits cleared----|
+				 *      |
+				 *      start
+				 */
+				*start_ret = state->start;
+				break;
+			}
 		} else {
-			*start_ret = start;
+			/*
+			 * |---prev range---|---hole/unset---|---node range---|
+			 *                          |
+			 *                        start
+			 *
+			 *                        or
+			 *
+			 * |---hole/unset--||--first node--|
+			 * 0   |
+			 *    start
+			 */
+			if (prev) {
+				state = rb_entry(prev, struct extent_state, rb_node);
+				*start_ret = state->end + 1;
+			} else {
+				*start_ret = 0;
+			}
 			break;
 		}
 	}
diff --git a/fs/btrfs/tests/extent-io-tests.c b/fs/btrfs/tests/extent-io-tests.c
index 7bf4d5734dbe..36fe720fc823 100644
--- a/fs/btrfs/tests/extent-io-tests.c
+++ b/fs/btrfs/tests/extent-io-tests.c
@@ -432,6 +432,91 @@ static int test_eb_bitmaps(u32 sectorsize, u32 nodesize)
 	return ret;
 }
 
+static int test_find_first_clear_extent_bit(void)
+{
+
+	struct extent_io_tree tree;
+	u64 start, end;
+
+	test_msg("Running find_first_clear_extent_bit test");
+	extent_io_tree_init(NULL, &tree, IO_TREE_SELFTEST, NULL);
+
+	/*
+	 * Set 1m-4m alloc/discard and 32m-64m thus leaving a hole
+	 * between 4m-32m
+	 */
+	set_extent_bits(&tree, SZ_1M, SZ_4M - 1,
+			CHUNK_TRIMMED | CHUNK_ALLOCATED);
+
+
+	find_first_clear_extent_bit(&tree, SZ_512K, &start, &end,
+				    CHUNK_TRIMMED | CHUNK_ALLOCATED);
+
+	if (start != 0 || end != SZ_1M -1)
+		test_err("Error finding beginning range: start: %llu end: %llu\n",
+			 start, end);
+
+	/* Now add 32m-64m so that we have a hole between 4m-32m */
+	set_extent_bits(&tree, SZ_32M, SZ_64M - 1,
+			CHUNK_TRIMMED | CHUNK_ALLOCATED);
+
+	/*
+	 * Request first hole starting at 12m, we should get 4m-32m
+	 */
+	find_first_clear_extent_bit(&tree, 12 * SZ_1M, &start, &end,
+				    CHUNK_TRIMMED | CHUNK_ALLOCATED);
+
+	if (start != SZ_4M || end != SZ_32M - 1)
+		test_err("Error finding trimmed range: start: %llu end: %llu",
+			 start, end);
+
+	/*
+	 * Search in the middle of allocated range, should get next available,
+	 * which happens to be unallocated -> 4m-32m
+	 */
+	find_first_clear_extent_bit(&tree, SZ_2M, &start, &end,
+				    CHUNK_TRIMMED | CHUNK_ALLOCATED);
+
+	if (start != SZ_4M || end != SZ_32M -1)
+		test_err("Error finding next unalloc range: start: %llu end: %llu",
+			 start, end);
+
+	/*
+	 * Set 64M-72M with CHUNK_ALLOC flag, then search for CHUNK_TRIMMED flag
+	 * being unset in this range, we should get the entry in range 64m-72M
+	 */
+	set_extent_bits(&tree, SZ_64M, SZ_64M + SZ_8M - 1, CHUNK_ALLOCATED);
+	find_first_clear_extent_bit(&tree, SZ_64M + SZ_1M, &start, &end,
+				    CHUNK_TRIMMED);
+
+	if (start != SZ_64M || end != SZ_64M + SZ_8M - 1)
+		test_err("Error finding exact range: start: %llu end: %llu",
+			 start, end);
+
+	find_first_clear_extent_bit(&tree, SZ_64M - SZ_8M, &start, &end,
+				    CHUNK_TRIMMED);
+
+	/*
+	 * Search in the middle of set range whose immediate neighbour doesn't
+	 * have the bits set so it must be returned
+	 */
+	if (start != SZ_64M || end != SZ_64M + SZ_8M - 1)
+		test_err("Error finding next alloc range: start: %llu end: %llu",
+			 start, end);
+
+	/*
+	 * Search beyond any known range, shall return after last known range
+	 * and end should be -1
+	 */
+	find_first_clear_extent_bit(&tree, -1, &start, &end, CHUNK_TRIMMED);
+	if (start != SZ_64M+SZ_8M || end != -1)
+		test_err("Error handling beyond end of range search: start: %llu"
+			 " end: %llu\n", start, end);
+
+	return 0;
+
+}
+
 int btrfs_test_extent_io(u32 sectorsize, u32 nodesize)
 {
 	int ret;
@@ -442,6 +527,10 @@ int btrfs_test_extent_io(u32 sectorsize, u32 nodesize)
 	if (ret)
 		goto out;
 
+	ret = test_find_first_clear_extent_bit();
+	if (ret)
+		goto out;
+
 	ret = test_eb_bitmaps(sectorsize, nodesize);
 out:
 	return ret;
-- 
2.17.1

Re: [PATCH 4/4] btrfs: Don't trim returned range based on input value in find_first_clear_extent_bit

[Qu Wenruo]

On 2019/6/3 下午6:06, Nikolay Borisov wrote:
> Currently find_first_clear_extent_bit always returns a range whose
> starting value is >= passed 'start'. This implicit trimming behavior is
> somewhat subtle and an implementation detail. Instead, this patch
> modifies the function such that now it always returns the range which
> contains passed 'start' and has the given bits unset. This range could
> either be due to presence of existing records which contains 'start'
> but have the bits unset or because there are no records that contain
> the given starting offset.
>
> This patch also adds test cases which cover find_first_clear_extent_bit
> since they were missing up until now.
>
> Signed-off-by: Nikolay Borisov <nborisov@suse.com>
> ---
>  fs/btrfs/extent_io.c             | 51 +++++++++++++++---
>  fs/btrfs/tests/extent-io-tests.c | 89 ++++++++++++++++++++++++++++++++
>  2 files changed, 134 insertions(+), 6 deletions(-)
>
> diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
> index d5979558c96f..1dd900cfb7ea 100644
> --- a/fs/btrfs/extent_io.c
> +++ b/fs/btrfs/extent_io.c
> @@ -1553,8 +1553,8 @@ int find_first_extent_bit(struct extent_io_tree *tree, u64 start,
>  }
>
>  /**
> - * find_first_clear_extent_bit - finds the first range that has @bits not set
> - * and that starts after @start
> + * find_first_clear_extent_bit - finds the first range that has @bits not set.
> + * This range could start before @start.

What about using the same expression of previous patches? E.g.
Such range would have range->start <= start  && range->start +
range->len > start.

Despite that, I think the ascii chart is pretty good, along with
selftest case it should be OK.

Reviewed-by: Qu Wenruo <wqu@suse.com>

Thanks,
Qu

>   *
>   * @tree - the tree to search
>   * @start - the offset at/after which the found extent should start
> @@ -1594,12 +1594,51 @@ void find_first_clear_extent_bit(struct extent_io_tree *tree, u64 start,
>  				goto out;
>  			}
>  		}
> +		/*
> +		 * At this point 'node' either contains 'start' or start is
> +		 * before 'node'
> +		 */
>  		state = rb_entry(node, struct extent_state, rb_node);
> -		if (in_range(start, state->start, state->end - state->start + 1) &&
> -			(state->state & bits)) {
> -			start = state->end + 1;
> +
> +		if (in_range(start, state->start, state->end - state->start + 1)) {
> +			if (state->state & bits) {
> +				/*
> +				 * |--range with bits sets--|
> +				 *    |
> +				 *    start
> +				 */
> +				start = state->end + 1;
> +			} else {
> +				/*
> +				 * 'start' falls within a range that doesn't
> +				 * have the bits set, so take its start as
> +				 * the beginning of the desire range
> +				 *
> +				 * |--range with bits cleared----|
> +				 *      |
> +				 *      start
> +				 */
> +				*start_ret = state->start;
> +				break;
> +			}
>  		} else {
> -			*start_ret = start;
> +			/*
> +			 * |---prev range---|---hole/unset---|---node range---|
> +			 *                          |
> +			 *                        start
> +			 *
> +			 *                        or
> +			 *
> +			 * |---hole/unset--||--first node--|
> +			 * 0   |
> +			 *    start
> +			 */
> +			if (prev) {
> +				state = rb_entry(prev, struct extent_state, rb_node);
> +				*start_ret = state->end + 1;
> +			} else {
> +				*start_ret = 0;
> +			}
>  			break;
>  		}
>  	}
> diff --git a/fs/btrfs/tests/extent-io-tests.c b/fs/btrfs/tests/extent-io-tests.c
> index 7bf4d5734dbe..36fe720fc823 100644
> --- a/fs/btrfs/tests/extent-io-tests.c
> +++ b/fs/btrfs/tests/extent-io-tests.c
> @@ -432,6 +432,91 @@ static int test_eb_bitmaps(u32 sectorsize, u32 nodesize)
>  	return ret;
>  }
>
> +static int test_find_first_clear_extent_bit(void)
> +{
> +
> +	struct extent_io_tree tree;
> +	u64 start, end;
> +
> +	test_msg("Running find_first_clear_extent_bit test");
> +	extent_io_tree_init(NULL, &tree, IO_TREE_SELFTEST, NULL);
> +
> +	/*
> +	 * Set 1m-4m alloc/discard and 32m-64m thus leaving a hole
> +	 * between 4m-32m
> +	 */
> +	set_extent_bits(&tree, SZ_1M, SZ_4M - 1,
> +			CHUNK_TRIMMED | CHUNK_ALLOCATED);
> +
> +
> +	find_first_clear_extent_bit(&tree, SZ_512K, &start, &end,
> +				    CHUNK_TRIMMED | CHUNK_ALLOCATED);
> +
> +	if (start != 0 || end != SZ_1M -1)
> +		test_err("Error finding beginning range: start: %llu end: %llu\n",
> +			 start, end);
> +
> +	/* Now add 32m-64m so that we have a hole between 4m-32m */
> +	set_extent_bits(&tree, SZ_32M, SZ_64M - 1,
> +			CHUNK_TRIMMED | CHUNK_ALLOCATED);
> +
> +	/*
> +	 * Request first hole starting at 12m, we should get 4m-32m
> +	 */
> +	find_first_clear_extent_bit(&tree, 12 * SZ_1M, &start, &end,
> +				    CHUNK_TRIMMED | CHUNK_ALLOCATED);
> +
> +	if (start != SZ_4M || end != SZ_32M - 1)
> +		test_err("Error finding trimmed range: start: %llu end: %llu",
> +			 start, end);
> +
> +	/*
> +	 * Search in the middle of allocated range, should get next available,
> +	 * which happens to be unallocated -> 4m-32m
> +	 */
> +	find_first_clear_extent_bit(&tree, SZ_2M, &start, &end,
> +				    CHUNK_TRIMMED | CHUNK_ALLOCATED);
> +
> +	if (start != SZ_4M || end != SZ_32M -1)
> +		test_err("Error finding next unalloc range: start: %llu end: %llu",
> +			 start, end);
> +
> +	/*
> +	 * Set 64M-72M with CHUNK_ALLOC flag, then search for CHUNK_TRIMMED flag
> +	 * being unset in this range, we should get the entry in range 64m-72M
> +	 */
> +	set_extent_bits(&tree, SZ_64M, SZ_64M + SZ_8M - 1, CHUNK_ALLOCATED);
> +	find_first_clear_extent_bit(&tree, SZ_64M + SZ_1M, &start, &end,
> +				    CHUNK_TRIMMED);
> +
> +	if (start != SZ_64M || end != SZ_64M + SZ_8M - 1)
> +		test_err("Error finding exact range: start: %llu end: %llu",
> +			 start, end);
> +
> +	find_first_clear_extent_bit(&tree, SZ_64M - SZ_8M, &start, &end,
> +				    CHUNK_TRIMMED);
> +
> +	/*
> +	 * Search in the middle of set range whose immediate neighbour doesn't
> +	 * have the bits set so it must be returned
> +	 */
> +	if (start != SZ_64M || end != SZ_64M + SZ_8M - 1)
> +		test_err("Error finding next alloc range: start: %llu end: %llu",
> +			 start, end);
> +
> +	/*
> +	 * Search beyond any known range, shall return after last known range
> +	 * and end should be -1
> +	 */
> +	find_first_clear_extent_bit(&tree, -1, &start, &end, CHUNK_TRIMMED);
> +	if (start != SZ_64M+SZ_8M || end != -1)
> +		test_err("Error handling beyond end of range search: start: %llu"
> +			 " end: %llu\n", start, end);
> +
> +	return 0;
> +
> +}
> +
>  int btrfs_test_extent_io(u32 sectorsize, u32 nodesize)
>  {
>  	int ret;
> @@ -442,6 +527,10 @@ int btrfs_test_extent_io(u32 sectorsize, u32 nodesize)
>  	if (ret)
>  		goto out;
>
> +	ret = test_find_first_clear_extent_bit();
> +	if (ret)
> +		goto out;
> +
>  	ret = test_eb_bitmaps(sectorsize, nodesize);
>  out:
>  	return ret;
>

Re: [PATCH 0/4] Further FITRIM improvements

[David Sterba]

On Mon, Jun 03, 2019 at 01:05:58PM +0300, Nikolay Borisov wrote:
> Qu reported beyond EOD (end of device) access with latest FITRIM improvements 
> that were merged. Further testing also showed that if ranged FITRIM request is 
> sent it's possible to cause u64 overflow which in turn cause calculations to 
> go off rail in btrfs_issue_discard (because it's called with start and len 
> as (u64)-1) and trim used data. 
> 
> This patchset aims to rectify this by: 
> 
> 1. Documenting the internal __etree_search since due to the rather high 
> number of output parameters it can be a bit confusing as to what the invariants 
> are. Due to this I got initially confused about possible return values on 
> boundary conditions. (Patch 1)
> 
> 2. Remove ranged support in btrfs_trim_free_extents - having range support in 
> btrfs_trim_free_extent is problematic because it's interpreted in device physical 
> space whilst range values from userspace should always be interpreted in 
> logical space. (Patch 2)
> 
> 3. Change slightly the semantics of find_first_clear_extent_bit to return the 
> range that contains the passed address or in case no such range exists the 
> next one, document the function and finally add tests (Patch 3 preps 
> btrfs_trim_free_extents to handle the change semantics and Patch 4 change 
> the semantics). 
> 
> This has been fully tested with xfstest and no regressions were found. 
> 
> Nikolay Borisov (4):
>   btrfs: Document __etree_search
>   btrfs: Always trim all unallocated space in btrfs_trim_free_extents
>   btrfs: Skip first megabyte on device when trimming
>   btrfs: Don't trim returned range based on input value in
>     find_first_clear_extent_bit

Added to misc-next, with some adjustments and 2/4 will go to the next
5.2-rc. Thanks.