[PATCH v3 0/2] btrfs: defrag: better handling for extents which can not be merged with adjacent ones

[PATCH v3 0/2] btrfs: defrag: better handling for extents which can not be merged with adjacent ones

[Qu Wenruo]

[CHANGELOG]
v3:
- Use div_u64() for percentage usage_ratio calculation
  v1 uses "/ 65536" which compiler just optimized to right shift, and
  avoided u64 division.

v2:
- Remove the "lone" naming
  Now the two new members would be named "usage_ratio" and
  "wasted_bytes".
  
- Make "usage_ratio" to be in range [0, 100]
  This should be much easier to understand.

When a file extent which can not be merged with any adjacent ones (e.g.
created by truncating a large file extent) is involved, it would haven no
chance to be touched by defrag.

This would mean that, if we have some truncated extents with very low
utilization ratio, or defragging it can free up a lot of space, defrag
would not touch them no matter what.

This is not ideal for some situations, e.g.:

  # mkfs.btrfs -f $dev
  # mount $dev $mnt
  # xfs_io -f -c "pwrite 0 128M" $mnt/foobar
  # sync
  # truncate -s 4k $mnt/foobar
  # btrfs filesystem defrag $mnt/foobar
  # sync

In above case, if defrag touches the 4k extent, it would free up the
whole 128M extent, which should be a good win.

This patchset would address the problem by introducing a special
entrance for such file extents.
Those file extents meeting either usage ratio or wasted bytes threshold
would be considered as a defrag target, allowing end uesrs to address
above situation.

This change requires progs support (or direct ioctl() calling), by
default they would be disabled.

And my personal recommendation for the ratio would be 5%, and 16MiB.


Qu Wenruo (2):
  btrfs: defrag: add under utilized extent to defrag target list
  btrfs: defrag: allow fine-tuning defrag behavior based on file extent
    usage

 fs/btrfs/defrag.c          | 46 +++++++++++++++++++++++++++++++++++---
 fs/btrfs/ioctl.c           |  6 +++++
 include/uapi/linux/btrfs.h | 40 ++++++++++++++++++++++++++++-----
 3 files changed, 84 insertions(+), 8 deletions(-)

-- 
2.44.0

[PATCH v3 1/2] btrfs: defrag: add under utilized extent to defrag target list

[Qu Wenruo]

[BUG]
The following script can lead to a very under utilized extent and we
have no way to use defrag to properly reclaim its wasted space:

  # mkfs.btrfs -f $dev
  # mount $dev $mnt
  # xfs_io -f -c "pwrite 0 128M" $mnt/foobar
  # sync
  # truncate -s 4k $mnt/foobar
  # btrfs filesystem defrag $mnt/foobar
  # sync

After the above operations, the file "foobar" is still utilizing the
whole 128M:

        item 4 key (257 INODE_ITEM 0) itemoff 15883 itemsize 160
                generation 7 transid 8 size 4096 nbytes 4096
                block group 0 mode 100600 links 1 uid 0 gid 0 rdev 0
                sequence 32770 flags 0x0(none)
        item 5 key (257 INODE_REF 256) itemoff 15869 itemsize 14
                index 2 namelen 4 name: file
        item 6 key (257 EXTENT_DATA 0) itemoff 15816 itemsize 53
                generation 7 type 1 (regular)
                extent data disk byte 298844160 nr 134217728 <<<
                extent data offset 0 nr 4096 ram 134217728
                extent compression 0 (none)

This is the common btrfs bookend behavior, that 128M extent would only
be freed if the last referencer of the extent is freed.

The problem is, normally we would go defrag to free that 128M extent,
but defrag would not touch the extent at all.

[CAUSE]
The file extent has no adjacent extent at all, thus all existing defrag
code consider it a perfectly good file extent, even if it's only
utilizing a very tiny amount of space.

[FIX]
For a file extent without any adjacent file extent, we should still
consider to defrag such under utilized extent, base on the following
conditions:

- utilization ratio
  If the extent is utilizing less than 1/16 of the on-disk extent size,
  then it would be a defrag target.

- wasted space
  If we defrag the extent and can free at least 16MiB, then it would be
  a defrag target.

Reported-by: Christoph Anton Mitterer <calestyo@scientia.org>
Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 fs/btrfs/defrag.c | 42 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 42 insertions(+)

diff --git a/fs/btrfs/defrag.c b/fs/btrfs/defrag.c
index f015fa1b6301..42f59d1456f9 100644
--- a/fs/btrfs/defrag.c
+++ b/fs/btrfs/defrag.c
@@ -950,6 +950,38 @@ struct defrag_target_range {
 	u64 len;
 };
 
+/*
+ * Special entry for extents that do not have any adjacent extents.
+ *
+ * This is for cases like the only and truncated extent of a file.
+ * Normally they won't be defraged at all (as they won't be merged with
+ * any adjacent ones), but we may still want to defrag them, to free up
+ * some space if possible.
+ */
+static bool should_defrag_under_utilized(struct extent_map *em)
+{
+	/*
+	 * Ratio based check.
+	 *
+	 * If the current extent is only utilizing 1/16 of its on-disk size,
+	 * it's definitely under-utilized, and defragging it may free up
+	 * the whole extent.
+	 */
+	if (em->len < em->orig_block_len / 16)
+		return true;
+
+	/*
+	 * Wasted space based check.
+	 *
+	 * If we can free up at least 16MiB, then it may be a good idea
+	 * to defrag.
+	 */
+	if (em->len < em->orig_block_len &&
+	    em->orig_block_len - em->len > SZ_16M)
+		return true;
+	return false;
+}
+
 /*
  * Collect all valid target extents.
  *
@@ -1070,6 +1102,16 @@ static int defrag_collect_targets(struct btrfs_inode *inode,
 		if (!next_mergeable) {
 			struct defrag_target_range *last;
 
+			/*
+			 * This is a single extent without any chance to merge
+			 * with any adjacent extent.
+			 *
+			 * But if we may free up some space, it is still worth
+			 * defragging.
+			 */
+			if (should_defrag_under_utilized(em))
+				goto add;
+
 			/* Empty target list, no way to merge with last entry */
 			if (list_empty(target_list))
 				goto next;
-- 
2.44.0

[PATCH v3 2/2] btrfs: defrag: allow fine-tuning defrag behavior based on file extent usage

[Qu Wenruo]

Previously we're using a fixed usage ratio and wasted bytes for file
extents which can not be merged with any adjacent ones, but may still
free up some space.

This patch would enhance the behavior by allowing fine-tuning using some
extra members inside btrfs_ioctl_defrag_range_args.

This would introduce two flags and two new members:

- BTRFS_DEFRAG_RANGE_USAGE_RATIO and BTRFS_DEFRAG_RANGE_WASTED_BYTES
  With these flags set, defrag would consider file extents with their
  usage ratio and wasted bytes as a defrag condition.

- usage_ratio
  This is a u32 value, but only [0, 100] is allowed.
  0 means disable usage ratio detection, aka no extra file extents
  would be defragged based on their usage ratio at all.

  1 means file extents which refer less than 1% of the on-disk extent
  size would be defragged.

- wasted_bytes
  This is a u32 value.
  The "wasted" bytes are just the difference between file extent size
  against on-disk extent size. (That's if the file extent size is
  smaller than the on-disk extent size).

  This "wasted" calculation doesn't take other file extents into
  consideration, thus it's not ensured to free up space.

Signed-off-by: Qu Wenruo <wqu@suse.com>
---
 fs/btrfs/defrag.c          | 38 +++++++++++++++++-------------------
 fs/btrfs/ioctl.c           |  6 ++++++
 include/uapi/linux/btrfs.h | 40 +++++++++++++++++++++++++++++++++-----
 3 files changed, 59 insertions(+), 25 deletions(-)

diff --git a/fs/btrfs/defrag.c b/fs/btrfs/defrag.c
index 42f59d1456f9..d7fdecaeafb6 100644
--- a/fs/btrfs/defrag.c
+++ b/fs/btrfs/defrag.c
@@ -958,26 +958,16 @@ struct defrag_target_range {
  * any adjacent ones), but we may still want to defrag them, to free up
  * some space if possible.
  */
-static bool should_defrag_under_utilized(struct extent_map *em)
+static bool should_defrag_under_utilized(struct extent_map *em,
+					 u32 usage_ratio, u32 wasted_bytes)
 {
-	/*
-	 * Ratio based check.
-	 *
-	 * If the current extent is only utilizing 1/16 of its on-disk size,
-	 * it's definitely under-utilized, and defragging it may free up
-	 * the whole extent.
-	 */
-	if (em->len < em->orig_block_len / 16)
+	/* Ratio based check. */
+	if (em->len < div_u64(em->orig_block_len * usage_ratio, 100))
 		return true;
 
-	/*
-	 * Wasted space based check.
-	 *
-	 * If we can free up at least 16MiB, then it may be a good idea
-	 * to defrag.
-	 */
+	/* Wasted space based check. */
 	if (em->len < em->orig_block_len &&
-	    em->orig_block_len - em->len > SZ_16M)
+	    em->orig_block_len - em->len > wasted_bytes)
 		return true;
 	return false;
 }
@@ -999,6 +989,7 @@ static bool should_defrag_under_utilized(struct extent_map *em)
 static int defrag_collect_targets(struct btrfs_inode *inode,
 				  u64 start, u64 len, u32 extent_thresh,
 				  u64 newer_than, bool do_compress,
+				  u32 usage_ratio, u32 wasted_bytes,
 				  bool locked, struct list_head *target_list,
 				  u64 *last_scanned_ret)
 {
@@ -1109,7 +1100,8 @@ static int defrag_collect_targets(struct btrfs_inode *inode,
 			 * But if we may free up some space, it is still worth
 			 * defragging.
 			 */
-			if (should_defrag_under_utilized(em))
+			if (should_defrag_under_utilized(em, usage_ratio,
+							 wasted_bytes))
 				goto add;
 
 			/* Empty target list, no way to merge with last entry */
@@ -1241,6 +1233,7 @@ static int defrag_one_locked_target(struct btrfs_inode *inode,
 
 static int defrag_one_range(struct btrfs_inode *inode, u64 start, u32 len,
 			    u32 extent_thresh, u64 newer_than, bool do_compress,
+			    u32 usage_ratio, u32 wasted_bytes,
 			    u64 *last_scanned_ret)
 {
 	struct extent_state *cached_state = NULL;
@@ -1286,7 +1279,8 @@ static int defrag_one_range(struct btrfs_inode *inode, u64 start, u32 len,
 	 * so that we won't relock the extent range and cause deadlock.
 	 */
 	ret = defrag_collect_targets(inode, start, len, extent_thresh,
-				     newer_than, do_compress, true,
+				     newer_than, do_compress, usage_ratio,
+				     wasted_bytes, true,
 				     &target_list, last_scanned_ret);
 	if (ret < 0)
 		goto unlock_extent;
@@ -1319,6 +1313,7 @@ static int defrag_one_cluster(struct btrfs_inode *inode,
 			      struct file_ra_state *ra,
 			      u64 start, u32 len, u32 extent_thresh,
 			      u64 newer_than, bool do_compress,
+			      u32 usage_ratio, u32 wasted_bytes,
 			      unsigned long *sectors_defragged,
 			      unsigned long max_sectors,
 			      u64 *last_scanned_ret)
@@ -1330,7 +1325,8 @@ static int defrag_one_cluster(struct btrfs_inode *inode,
 	int ret;
 
 	ret = defrag_collect_targets(inode, start, len, extent_thresh,
-				     newer_than, do_compress, false,
+				     newer_than, do_compress, usage_ratio,
+				     wasted_bytes, false,
 				     &target_list, NULL);
 	if (ret < 0)
 		goto out;
@@ -1370,6 +1366,7 @@ static int defrag_one_cluster(struct btrfs_inode *inode,
 		 */
 		ret = defrag_one_range(inode, entry->start, range_len,
 				       extent_thresh, newer_than, do_compress,
+				       usage_ratio, wasted_bytes,
 				       last_scanned_ret);
 		if (ret < 0)
 			break;
@@ -1495,7 +1492,8 @@ int btrfs_defrag_file(struct inode *inode, struct file_ra_state *ra,
 			BTRFS_I(inode)->defrag_compress = compress_type;
 		ret = defrag_one_cluster(BTRFS_I(inode), ra, cur,
 				cluster_end + 1 - cur, extent_thresh,
-				newer_than, do_compress, &sectors_defragged,
+				newer_than, do_compress, range->usage_ratio,
+				range->wasted_bytes, &sectors_defragged,
 				max_to_defrag, &last_scanned);
 
 		if (sectors_defragged > prev_sectors_defragged)
diff --git a/fs/btrfs/ioctl.c b/fs/btrfs/ioctl.c
index 38459a89b27c..b6d1844b5bbe 100644
--- a/fs/btrfs/ioctl.c
+++ b/fs/btrfs/ioctl.c
@@ -2635,6 +2635,12 @@ static int btrfs_ioctl_defrag(struct file *file, void __user *argp)
 				range.flags |= BTRFS_DEFRAG_RANGE_START_IO;
 				range.extent_thresh = (u32)-1;
 			}
+
+			if (range.flags & BTRFS_DEFRAG_RANGE_LONE_RATIO &&
+			    range.usage_ratio > 100) {
+				ret = -EINVAL;
+				goto out;
+			}
 		} else {
 			/* the rest are all set to zero by kzalloc */
 			range.len = (u64)-1;
diff --git a/include/uapi/linux/btrfs.h b/include/uapi/linux/btrfs.h
index cdf6ad872149..6c9d9cfa5b8a 100644
--- a/include/uapi/linux/btrfs.h
+++ b/include/uapi/linux/btrfs.h
@@ -613,10 +613,14 @@ struct btrfs_ioctl_clone_range_args {
  * Used by:
  * struct btrfs_ioctl_defrag_range_args.flags
  */
-#define BTRFS_DEFRAG_RANGE_COMPRESS 1
-#define BTRFS_DEFRAG_RANGE_START_IO 2
-#define BTRFS_DEFRAG_RANGE_FLAGS_SUPP	(BTRFS_DEFRAG_RANGE_COMPRESS |		\
-					 BTRFS_DEFRAG_RANGE_START_IO)
+#define BTRFS_DEFRAG_RANGE_COMPRESS		(1ULL << 0)
+#define BTRFS_DEFRAG_RANGE_START_IO		(1ULL << 1)
+#define BTRFS_DEFRAG_RANGE_LONE_RATIO		(1ULL << 2)
+#define BTRFS_DEFRAG_RANGE_LONE_WASTED_BYTES	(1ULL << 3)
+#define BTRFS_DEFRAG_RANGE_FLAGS_SUPP	(BTRFS_DEFRAG_RANGE_COMPRESS |	\
+					 BTRFS_DEFRAG_RANGE_START_IO |	\
+					 BTRFS_DEFRAG_RANGE_LONE_RATIO |\
+					 BTRFS_DEFRAG_RANGE_LONE_WASTED_BYTES)
 
 struct btrfs_ioctl_defrag_range_args {
 	/* start of the defrag operation */
@@ -645,8 +649,34 @@ struct btrfs_ioctl_defrag_range_args {
 	 */
 	__u32 compress_type;
 
+	/*
+	 * File extents which has lower usage ratio than this would be defragged.
+	 *
+	 * Valid values are [0, 100].
+	 *
+	 * 0 means no check based on usage ratio.
+	 * 1 means one file extent would be defragged if its referred size
+	 * (file extent num bytes) is smaller than 1% of its on-disk extent size.
+	 * 100 means one file extent would be defragged if its referred size
+	 * (file extent num bytes) is smaller than 100% of its on-disk extent size.
+	 */
+	__u32 usage_ratio;
+
+	/*
+	 * File extents which has more "wasted" bytes than this would be
+	 * defragged.
+	 *
+	 * "Wasted" bytes just means the difference between the file extent size
+	 * (file extent num bytes) against the on-disk extent size
+	 * (file extent disk num bytes).
+	 *
+	 * Valid values are [0, U32_MAX], but values larger than
+	 * BTRFS_MAX_EXTENT_SIZE would not make much sense.
+	 */
+	__u32 wasted_bytes;
+
 	/* spare for later */
-	__u32 unused[4];
+	__u32 unused[2];
 };
 
 
-- 
2.44.0