[PATCH V3 0/3] Btrfs: btrfs_dedupe_file_range() ioctl, remove 16MiB restriction

[PATCH V3 0/3] Btrfs: btrfs_dedupe_file_range() ioctl, remove 16MiB restriction

[Timofey Titovets]

At now btrfs_dedupe_file_range() restricted to 16MiB range for
limit locking time and memory requirement for dedup ioctl()

For too big input range code silently set range to 16MiB

Let's remove that restriction by do iterating over dedup range.
That's backward compatible and will not change anything for request
less then 16MiB.

Changes:
  v1 -> v2:
    - Refactor btrfs_cmp_data_prepare and btrfs_extent_same
    - Store memory of pages array between iterations
    - Lock inodes once, not on each iteration
    - Small inplace cleanups
  v2 -> v3:
    - Split to several patches

Timofey Titovets (3):
  Btrfs: split btrfs_extent_same() for simplification
  Btrfs: btrfs_dedupe_file_range() ioctl, remove 16MiB restriction
  Btrfs: btrfs_extent_same() reuse cmp workspace

 fs/btrfs/ioctl.c | 161 ++++++++++++++++++++++++++---------------------
 1 file changed, 91 insertions(+), 70 deletions(-)

-- 
2.17.0

[PATCH V3 1/3] Btrfs: split btrfs_extent_same() for simplification

[Timofey Titovets]

Split btrfs_extent_same() for simplification and preparation
for call several times over target files

Move most logic to __btrfs_extent_same()
And leave in btrfs_extent_same() things which must happens only once

Changes:
  v3:
    - Splited from one to 3 patches

Signed-off-by: Timofey Titovets <nefelim4ag@gmail.com>
---
 fs/btrfs/ioctl.c | 64 ++++++++++++++++++++++++++----------------------
 1 file changed, 35 insertions(+), 29 deletions(-)

diff --git a/fs/btrfs/ioctl.c b/fs/btrfs/ioctl.c
index f0e62e4f8fe7..fb8beedb0359 100644
--- a/fs/btrfs/ioctl.c
+++ b/fs/btrfs/ioctl.c
@@ -2882,8 +2882,8 @@ static int extent_same_check_offsets(struct inode *inode, u64 off, u64 *plen,
 	return 0;
 }
 
-static int btrfs_extent_same(struct inode *src, u64 loff, u64 olen,
-			     struct inode *dst, u64 dst_loff)
+static int __btrfs_extent_same(struct inode *src, u64 loff, u64 olen,
+			       struct inode *dst, u64 dst_loff)
 {
 	int ret;
 	u64 len = olen;
@@ -2892,21 +2892,13 @@ static int btrfs_extent_same(struct inode *src, u64 loff, u64 olen,
 	u64 same_lock_start = 0;
 	u64 same_lock_len = 0;
 
-	if (len == 0)
-		return 0;
-
-	if (same_inode)
-		inode_lock(src);
-	else
-		btrfs_double_inode_lock(src, dst);
-
 	ret = extent_same_check_offsets(src, loff, &len, olen);
 	if (ret)
-		goto out_unlock;
+		return ret;
 
 	ret = extent_same_check_offsets(dst, dst_loff, &len, olen);
 	if (ret)
-		goto out_unlock;
+		return ret;
 
 	if (same_inode) {
 		/*
@@ -2923,32 +2915,21 @@ static int btrfs_extent_same(struct inode *src, u64 loff, u64 olen,
 		 * allow an unaligned length so long as it ends at
 		 * i_size.
 		 */
-		if (len != olen) {
-			ret = -EINVAL;
-			goto out_unlock;
-		}
+		if (len != olen)
+			return -EINVAL;
 
 		/* Check for overlapping ranges */
-		if (dst_loff + len > loff && dst_loff < loff + len) {
-			ret = -EINVAL;
-			goto out_unlock;
-		}
+		if (dst_loff + len > loff && dst_loff < loff + len)
+			return -EINVAL;
 
 		same_lock_start = min_t(u64, loff, dst_loff);
 		same_lock_len = max_t(u64, loff, dst_loff) + len - same_lock_start;
 	}
 
-	/* don't make the dst file partly checksummed */
-	if ((BTRFS_I(src)->flags & BTRFS_INODE_NODATASUM) !=
-	    (BTRFS_I(dst)->flags & BTRFS_INODE_NODATASUM)) {
-		ret = -EINVAL;
-		goto out_unlock;
-	}
-
 again:
 	ret = btrfs_cmp_data_prepare(src, loff, dst, dst_loff, olen, &cmp);
 	if (ret)
-		goto out_unlock;
+		return ret;
 
 	if (same_inode)
 		ret = lock_extent_range(src, same_lock_start, same_lock_len,
@@ -2998,7 +2979,32 @@ static int btrfs_extent_same(struct inode *src, u64 loff, u64 olen,
 		btrfs_double_extent_unlock(src, loff, dst, dst_loff, len);
 
 	btrfs_cmp_data_free(&cmp);
-out_unlock:
+
+	return ret;
+}
+
+static int btrfs_extent_same(struct inode *src, u64 loff, u64 olen,
+			     struct inode *dst, u64 dst_loff)
+{
+	int ret;
+	bool same_inode = (src == dst);
+
+	if (olen == 0)
+		return 0;
+
+	/* don't make the dst file partly checksummed */
+	if ((BTRFS_I(src)->flags & BTRFS_INODE_NODATASUM) !=
+	    (BTRFS_I(dst)->flags & BTRFS_INODE_NODATASUM)) {
+		return -EINVAL;
+	}
+
+	if (same_inode)
+		inode_lock(src);
+	else
+		btrfs_double_inode_lock(src, dst);
+
+	ret = __btrfs_extent_same(src, loff, olen, dst, dst_loff);
+
 	if (same_inode)
 		inode_unlock(src);
 	else
-- 
2.17.0

[PATCH V3 2/3] Btrfs: btrfs_dedupe_file_range() ioctl, remove 16MiB restriction

[Timofey Titovets]

At now btrfs_dedupe_file_range() restricted to 16MiB range for
limit locking time and memory requirement for dedup ioctl()

For too big input range code silently set range to 16MiB

Let's remove that restriction by do iterating over dedup range.
That's backward compatible and will not change anything for request
less then 16MiB.

Changes:
  v3:
    - Splited from one to 3 patches

Signed-off-by: Timofey Titovets <nefelim4ag@gmail.com>
---
 fs/btrfs/ioctl.c | 25 +++++++++++++++++++------
 1 file changed, 19 insertions(+), 6 deletions(-)

diff --git a/fs/btrfs/ioctl.c b/fs/btrfs/ioctl.c
index fb8beedb0359..38ce990e9b4c 100644
--- a/fs/btrfs/ioctl.c
+++ b/fs/btrfs/ioctl.c
@@ -2983,11 +2983,14 @@ static int __btrfs_extent_same(struct inode *src, u64 loff, u64 olen,
 	return ret;
 }
 
+#define BTRFS_MAX_DEDUPE_LEN	SZ_16M
+
 static int btrfs_extent_same(struct inode *src, u64 loff, u64 olen,
 			     struct inode *dst, u64 dst_loff)
 {
 	int ret;
 	bool same_inode = (src == dst);
+	u64 i, tail_len, chunk_count;
 
 	if (olen == 0)
 		return 0;
@@ -2998,13 +3001,28 @@ static int btrfs_extent_same(struct inode *src, u64 loff, u64 olen,
 		return -EINVAL;
 	}
 
+	tail_len = olen % BTRFS_MAX_DEDUPE_LEN;
+	chunk_count = div_u64(olen, BTRFS_MAX_DEDUPE_LEN);
+
 	if (same_inode)
 		inode_lock(src);
 	else
 		btrfs_double_inode_lock(src, dst);
 
-	ret = __btrfs_extent_same(src, loff, olen, dst, dst_loff);
+	for (i = 0; i < chunk_count; i++) {
+		ret = __btrfs_extent_same(src, loff, BTRFS_MAX_DEDUPE_LEN,
+					  dst, dst_loff);
+		if (ret)
+			goto out;
+
+		loff += BTRFS_MAX_DEDUPE_LEN;
+		dst_loff += BTRFS_MAX_DEDUPE_LEN;
+	}
+
+	if (tail_len > 0)
+		ret = __btrfs_extent_same(src, loff, tail_len, dst, dst_loff);
 
+out:
 	if (same_inode)
 		inode_unlock(src);
 	else
@@ -3013,8 +3031,6 @@ static int btrfs_extent_same(struct inode *src, u64 loff, u64 olen,
 	return ret;
 }
 
-#define BTRFS_MAX_DEDUPE_LEN	SZ_16M
-
 ssize_t btrfs_dedupe_file_range(struct file *src_file, u64 loff, u64 olen,
 				struct file *dst_file, u64 dst_loff)
 {
@@ -3023,9 +3039,6 @@ ssize_t btrfs_dedupe_file_range(struct file *src_file, u64 loff, u64 olen,
 	u64 bs = BTRFS_I(src)->root->fs_info->sb->s_blocksize;
 	ssize_t res;
 
-	if (olen > BTRFS_MAX_DEDUPE_LEN)
-		olen = BTRFS_MAX_DEDUPE_LEN;
-
 	if (WARN_ON_ONCE(bs < PAGE_SIZE)) {
 		/*
 		 * Btrfs does not support blocksize < page_size. As a
-- 
2.17.0

[PATCH V3 3/3] Btrfs: btrfs_extent_same() reuse cmp workspace

[Timofey Titovets]

We support big dedup requests by split range to several smaller,
and call dedup logic over each of them.

Instead of alloc/dealloc on each, let's reuse allocated memory.

Changes:
  v3:
    - Splited from one to 3 patches

Signed-off-by: Timofey Titovets <nefelim4ag@gmail.com>
---
 fs/btrfs/ioctl.c | 80 +++++++++++++++++++++++++-----------------------
 1 file changed, 41 insertions(+), 39 deletions(-)

diff --git a/fs/btrfs/ioctl.c b/fs/btrfs/ioctl.c
index 38ce990e9b4c..f2521bc0b069 100644
--- a/fs/btrfs/ioctl.c
+++ b/fs/btrfs/ioctl.c
@@ -2769,8 +2769,6 @@ static void btrfs_cmp_data_free(struct cmp_pages *cmp)
 			put_page(pg);
 		}
 	}
-	kfree(cmp->src_pages);
-	kfree(cmp->dst_pages);
 }
 
 static int btrfs_cmp_data_prepare(struct inode *src, u64 loff,
@@ -2779,40 +2777,14 @@ static int btrfs_cmp_data_prepare(struct inode *src, u64 loff,
 {
 	int ret;
 	int num_pages = PAGE_ALIGN(len) >> PAGE_SHIFT;
-	struct page **src_pgarr, **dst_pgarr;
 
-	/*
-	 * We must gather up all the pages before we initiate our
-	 * extent locking. We use an array for the page pointers. Size
-	 * of the array is bounded by len, which is in turn bounded by
-	 * BTRFS_MAX_DEDUPE_LEN.
-	 */
-	src_pgarr = kcalloc(num_pages, sizeof(struct page *), GFP_KERNEL);
-	dst_pgarr = kcalloc(num_pages, sizeof(struct page *), GFP_KERNEL);
-	if (!src_pgarr || !dst_pgarr) {
-		kfree(src_pgarr);
-		kfree(dst_pgarr);
-		return -ENOMEM;
-	}
 	cmp->num_pages = num_pages;
-	cmp->src_pages = src_pgarr;
-	cmp->dst_pages = dst_pgarr;
 
-	/*
-	 * If deduping ranges in the same inode, locking rules make it mandatory
-	 * to always lock pages in ascending order to avoid deadlocks with
-	 * concurrent tasks (such as starting writeback/delalloc).
-	 */
-	if (src == dst && dst_loff < loff) {
-		swap(src_pgarr, dst_pgarr);
-		swap(loff, dst_loff);
-	}
-
-	ret = gather_extent_pages(src, src_pgarr, cmp->num_pages, loff);
+	ret = gather_extent_pages(src, cmp->src_pages, num_pages, loff);
 	if (ret)
 		goto out;
 
-	ret = gather_extent_pages(dst, dst_pgarr, cmp->num_pages, dst_loff);
+	ret = gather_extent_pages(dst, cmp->dst_pages, num_pages, dst_loff);
 
 out:
 	if (ret)
@@ -2883,11 +2855,11 @@ static int extent_same_check_offsets(struct inode *inode, u64 off, u64 *plen,
 }
 
 static int __btrfs_extent_same(struct inode *src, u64 loff, u64 olen,
-			       struct inode *dst, u64 dst_loff)
+			       struct inode *dst, u64 dst_loff,
+			       struct cmp_pages *cmp)
 {
 	int ret;
 	u64 len = olen;
-	struct cmp_pages cmp;
 	bool same_inode = (src == dst);
 	u64 same_lock_start = 0;
 	u64 same_lock_len = 0;
@@ -2927,7 +2899,7 @@ static int __btrfs_extent_same(struct inode *src, u64 loff, u64 olen,
 	}
 
 again:
-	ret = btrfs_cmp_data_prepare(src, loff, dst, dst_loff, olen, &cmp);
+	ret = btrfs_cmp_data_prepare(src, loff, dst, dst_loff, olen, cmp);
 	if (ret)
 		return ret;
 
@@ -2950,7 +2922,7 @@ static int __btrfs_extent_same(struct inode *src, u64 loff, u64 olen,
 		 * Ranges in the io trees already unlocked. Now unlock all
 		 * pages before waiting for all IO to complete.
 		 */
-		btrfs_cmp_data_free(&cmp);
+		btrfs_cmp_data_free(cmp);
 		if (same_inode) {
 			btrfs_wait_ordered_range(src, same_lock_start,
 						 same_lock_len);
@@ -2963,12 +2935,12 @@ static int __btrfs_extent_same(struct inode *src, u64 loff, u64 olen,
 	ASSERT(ret == 0);
 	if (WARN_ON(ret)) {
 		/* ranges in the io trees already unlocked */
-		btrfs_cmp_data_free(&cmp);
+		btrfs_cmp_data_free(cmp);
 		return ret;
 	}
 
 	/* pass original length for comparison so we stay within i_size */
-	ret = btrfs_cmp_data(olen, &cmp);
+	ret = btrfs_cmp_data(olen, cmp);
 	if (ret == 0)
 		ret = btrfs_clone(src, dst, loff, olen, len, dst_loff, 1);
 
@@ -2978,7 +2950,7 @@ static int __btrfs_extent_same(struct inode *src, u64 loff, u64 olen,
 	else
 		btrfs_double_extent_unlock(src, loff, dst, dst_loff, len);
 
-	btrfs_cmp_data_free(&cmp);
+	btrfs_cmp_data_free(cmp);
 
 	return ret;
 }
@@ -2989,6 +2961,8 @@ static int btrfs_extent_same(struct inode *src, u64 loff, u64 olen,
 			     struct inode *dst, u64 dst_loff)
 {
 	int ret;
+	struct cmp_pages cmp;
+	int num_pages = PAGE_ALIGN(BTRFS_MAX_DEDUPE_LEN) >> PAGE_SHIFT;
 	bool same_inode = (src == dst);
 	u64 i, tail_len, chunk_count;
 
@@ -3003,6 +2977,30 @@ static int btrfs_extent_same(struct inode *src, u64 loff, u64 olen,
 
 	tail_len = olen % BTRFS_MAX_DEDUPE_LEN;
 	chunk_count = div_u64(olen, BTRFS_MAX_DEDUPE_LEN);
+	if (chunk_count == 0)
+		num_pages = PAGE_ALIGN(tail_len) >> PAGE_SHIFT;
+
+	/*
+	 * If deduping ranges in the same inode, locking rules make it mandatory
+	 * to always lock pages in ascending order to avoid deadlocks with
+	 * concurrent tasks (such as starting writeback/delalloc).
+	 */
+	if (same_inode && dst_loff < loff)
+		swap(loff, dst_loff);
+
+	/*
+	 * We must gather up all the pages before we initiate our
+	 * extent locking. We use an array for the page pointers. Size
+	 * of the array is bounded by len, which is in turn bounded by
+	 * BTRFS_MAX_DEDUPE_LEN.
+	 */
+	cmp.src_pages = kcalloc(num_pages, sizeof(struct page *), GFP_KERNEL);
+	cmp.dst_pages = kcalloc(num_pages, sizeof(struct page *), GFP_KERNEL);
+	if (!cmp.src_pages || !cmp.dst_pages) {
+		kfree(cmp.src_pages);
+		kfree(cmp.dst_pages);
+		return -ENOMEM;
+	}
 
 	if (same_inode)
 		inode_lock(src);
@@ -3011,7 +3009,7 @@ static int btrfs_extent_same(struct inode *src, u64 loff, u64 olen,
 
 	for (i = 0; i < chunk_count; i++) {
 		ret = __btrfs_extent_same(src, loff, BTRFS_MAX_DEDUPE_LEN,
-					  dst, dst_loff);
+					  dst, dst_loff, &cmp);
 		if (ret)
 			goto out;
 
@@ -3020,7 +3018,8 @@ static int btrfs_extent_same(struct inode *src, u64 loff, u64 olen,
 	}
 
 	if (tail_len > 0)
-		ret = __btrfs_extent_same(src, loff, tail_len, dst, dst_loff);
+		ret = __btrfs_extent_same(src, loff, tail_len,
+					  dst, dst_loff, &cmp);
 
 out:
 	if (same_inode)
@@ -3028,6 +3027,9 @@ static int btrfs_extent_same(struct inode *src, u64 loff, u64 olen,
 	else
 		btrfs_double_inode_unlock(src, dst);
 
+	kfree(cmp.src_pages);
+	kfree(cmp.dst_pages);
+
 	return ret;
 }
 
-- 
2.17.0

Re: [PATCH V3 0/3] Btrfs: btrfs_dedupe_file_range() ioctl, remove 16MiB restriction

[David Sterba]

On Wed, May 02, 2018 at 08:15:35AM +0300, Timofey Titovets wrote:
> At now btrfs_dedupe_file_range() restricted to 16MiB range for
> limit locking time and memory requirement for dedup ioctl()
> 
> For too big input range code silently set range to 16MiB
> 
> Let's remove that restriction by do iterating over dedup range.
> That's backward compatible and will not change anything for request
> less then 16MiB.
> 
> Changes:
>   v1 -> v2:
>     - Refactor btrfs_cmp_data_prepare and btrfs_extent_same
>     - Store memory of pages array between iterations
>     - Lock inodes once, not on each iteration
>     - Small inplace cleanups
>   v2 -> v3:
>     - Split to several patches
> 
> Timofey Titovets (3):
>   Btrfs: split btrfs_extent_same() for simplification
>   Btrfs: btrfs_dedupe_file_range() ioctl, remove 16MiB restriction
>   Btrfs: btrfs_extent_same() reuse cmp workspace

Looks good to me, thanks. I'll edit the changlogs a bit and add the
patches to 4.18 queue.

In the original code there's kcalloc for the array holding the page
pointers. This can grow up to 32kb if the full 16MiB range is used so
I'll add a patch that'll use kvmalloc (the vmalloc fallback) in case
there's no 32kib of contiguous memory.

IIRC the 16M limit is mentioned in manual pages, so this would need to
be fixed and documented how this is going to behave.

Re: [PATCH V3 0/3] Btrfs: btrfs_dedupe_file_range() ioctl, remove 16MiB restriction

[David Sterba]

On Fri, May 11, 2018 at 05:22:58PM +0200, David Sterba wrote:
> On Wed, May 02, 2018 at 08:15:35AM +0300, Timofey Titovets wrote:
> > At now btrfs_dedupe_file_range() restricted to 16MiB range for
> > limit locking time and memory requirement for dedup ioctl()
> > 
> > For too big input range code silently set range to 16MiB
> > 
> > Let's remove that restriction by do iterating over dedup range.
> > That's backward compatible and will not change anything for request
> > less then 16MiB.
> > 
> > Changes:
> >   v1 -> v2:
> >     - Refactor btrfs_cmp_data_prepare and btrfs_extent_same
> >     - Store memory of pages array between iterations
> >     - Lock inodes once, not on each iteration
> >     - Small inplace cleanups
> >   v2 -> v3:
> >     - Split to several patches
> > 
> > Timofey Titovets (3):
> >   Btrfs: split btrfs_extent_same() for simplification
> >   Btrfs: btrfs_dedupe_file_range() ioctl, remove 16MiB restriction
> >   Btrfs: btrfs_extent_same() reuse cmp workspace
> 
> Looks good to me, thanks. I'll edit the changlogs a bit and add the
> patches to 4.18 queue.

Patchset added to misc-next, so it's on the way to 4.18, thanks.