Btrfs: make a source length of 0 imply EOF for dedupe

From: Omar Sandoval <[email protected]>

This just makes the following patch cleaner.

Signed-off-by Omar Sandoval <[email protected]>

---
 fs/btrfs/ioctl.c | 33 ++++++++++++---------------------
 1 file changed, 12 insertions(+), 21 deletions(-)

fs/btrfs/ioctl.c +12 -21

index 7acbd2c..e23f945 100644
@@ -3124,26 +3124,27 @@ static int btrfs_extent_same(struct inode *src, u64 loff, u64 olen,
 	int ret;
 	u64 len = olen;
 	struct cmp_pages cmp;
-	int same_inode = 0;
+	bool same_inode = (src == dst);
 	u64 same_lock_start = 0;
 	u64 same_lock_len = 0;
 
-	if (src == dst)
-		same_inode = 1;
-
 	if (len == 0)
 		return 0;
 
-	if (same_inode) {
+	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;
-		ret = extent_same_check_offsets(src, dst_loff, &len, olen);
-		if (ret)
-			goto out_unlock;
+	ret = extent_same_check_offsets(src, loff, &len, olen);
+	if (ret)
+		goto out_unlock;
 
+	ret = extent_same_check_offsets(dst, dst_loff, &len, olen);
+	if (ret)
+		goto out_unlock;
+
+	if (same_inode) {
 		/*
 		 * Single inode case wants the same checks, except we
 		 * don't want our length pushed out past i_size as

@@ -3171,16 +3172,6 @@ static int btrfs_extent_same(struct inode *src, u64 loff, u64 olen,
 
 		same_lock_start = min_t(u64, loff, dst_loff);
 		same_lock_len = max_t(u64, loff, dst_loff) + len - same_lock_start;
-	} else {
-		btrfs_double_inode_lock(src, dst);
-
-		ret = extent_same_check_offsets(src, loff, &len, olen);
-		if (ret)
-			goto out_unlock;
-
-		ret = extent_same_check_offsets(dst, dst_loff, &len, olen);
-		if (ret)
-			goto out_unlock;
 	}
 
 	/* don't make the dst file partly checksummed */

So now we have 3 options:

a) Apply these patches as-is.
b) Fix XFS to both return the actual bytes_deduped and cap the length for the EOF case. Do the same for Btrfs.
c) Make XFS consistent with the existing Btrfs behavior.

I'm starting to lean towards option c after writing this cover letter, but I might as well send these out and get a second opinion.

Quoted 7 lines · Omar Sandoval

So now we have 3 options:

a) Apply these patches as-is.
b) Fix XFS to both return the actual bytes_deduped and cap the length for the EOF case. Do the same for Btrfs.
c) Make XFS consistent with the existing Btrfs behavior.

Quoted 2 lines

I'm starting to lean towards option c after writing this cover letter, but I might as well send these out and get a second opinion.

I agree - btrfs was there first, and there is no fatal flaw in the ABI, so let's adjust XFS to it.

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

3. Both XFS and Btrfs cap each dedupe operation to 16MB, but the implicit EOF gets around this in the existing XFS implementation. I copied this for the Btrfs implementation.

Quoted 3 lines · Omar Sandoval

3. Both XFS and Btrfs cap each dedupe operation to 16MB, but the implicit EOF gets around this in the existing XFS implementation. I copied this for the Btrfs implementation.

Somewhat tangential to this patch, but on the dedup topic: Can we raise or drop that 16MB limit?

The maximum btrfs extent length is 128MB. Currently the btrfs dedup behavior for a 128MB extent is to generate 8x16MB shared extent references with different extent offsets to a single 128MB physical extent. These references no longer look like the original 128MB extent to a userspace dedup tool. That raises the difficulty level substantially for a userspace dedup tool when it tries to figure out which extents to keep and which to discard or rewrite.

XFS may not have this problem--I haven't checked. On btrfs it's definitely not as simple as "bang two inode/offset/length pairs together with dedup and disk space will be freed automagically." If dedup is done incorrectly on btrfs, it can end up just making the filesystem slow without freeing any space.

The 16MB limit doesn't seem to be useful in practice. The two useful effects of the limit seem to be DoS mitigation. There is no checking of the RAM usage that I can find (i.e. if you fire off 16 dedup threads, they want 256MB of RAM; put another way, if you want to tie up 16GB of kernel RAM, all you have to do is create 1024 dedup threads), so it's not an effective DoS mitigation feature. Internally dedup could verify blocks in batches of 16MB and check for signals/release and reacquire locks in between, so it wouldn't tie up the kernel or the two inodes for excessively long periods.

Even if we want to keep the 16MB limit, there's also no way to query the kernel from userspace to find out what the limit is, other than by trial and error. It's not even in a header file, userspace just has to *know*.

Quoted 16 lines · Zygo Blaxell

Quoted 3 lines · Omar Sandoval

3. Both XFS and Btrfs cap each dedupe operation to 16MB, but the implicit EOF gets around this in the existing XFS implementation. I copied this for the Btrfs implementation.

Somewhat tangential to this patch, but on the dedup topic: Can we raise or drop that 16MB limit?

The maximum btrfs extent length is 128MB. Currently the btrfs dedup behavior for a 128MB extent is to generate 8x16MB shared extent references with different extent offsets to a single 128MB physical extent. These references no longer look like the original 128MB extent to a userspace dedup tool. That raises the difficulty level substantially for a userspace dedup tool when it tries to figure out which extents to keep and which to discard or rewrite.

Quoted 5 lines

XFS may not have this problem--I haven't checked. On btrfs it's definitely not as simple as "bang two inode/offset/length pairs together with dedup and disk space will be freed automagically." If dedup is done incorrectly on btrfs, it can end up just making the filesystem slow without freeing any space.

I copied the 16M limit into xfs/ocfs2 because btrfs had it. :)

The VFS now limits the size of the incoming struct file_dedupe_range to whatever a page size is. On x86 that only allows us 126 dedupe candidates, which means that a single call can perform up to ~2GB of IO. Storage is getting faster, but 2GB is still a fair amount for a single call. Of course in XFS we do the dedupe one file and one page at a time to keep the memory footprint sane.

On ppc64 with its huge 64k pages that comes out to 32GB of IO.

One thing we (speaking for XFS, anyway) /could/ do is limit based on the theoretical IO count instead of clamping the length, e.g.

if ((u64)dest_count * len >= (1ULL << 31))

	return -E2BIG;

That way you /could/ specify a larger extent size if you pass in fewer file descriptors. OTOH XFS will merge all the records together, so even if you deduped the whole 128M in 4k chunks you'll still end up with a single block mapping record and a single backref.

Were I starting from scratch I'd probably just dump the existing dedupe interface in favor of a non-vectorized dedupe_range call taking the same parameters as clone_range:

int dedupe_range(src_fd, src_off, dest_fd, dest_off);

I'd also change the semantics to "Find and share all identical blocks in this subrange. Differing blocks are left alone." because it seems silly that duperemove can issue large requests but a single byte difference in the middle causes info->status to be set to FILE_DEDUPE_RANGE_DIFFERS and info->bytes_deduped only changes if the entire range was deduped.

Quoted 9 lines

The 16MB limit doesn't seem to be useful in practice. The two useful effects of the limit seem to be DoS mitigation. There is no checking of the RAM usage that I can find (i.e. if you fire off 16 dedup threads, they want 256MB of RAM; put another way, if you want to tie up 16GB of kernel RAM, all you have to do is create 1024 dedup threads), so it's not an effective DoS mitigation feature. Internally dedup could verify blocks in batches of 16MB and check for signals/release and reacquire locks in between, so it wouldn't tie up the kernel or the two inodes for excessively long periods.

(Does btrfs actually do the extent_same stuff in parallel??)

Quoted 3 lines

Even if we want to keep the 16MB limit, there's also no way to query the kernel from userspace to find out what the limit is, other than by trial and error. It's not even in a header file, userspace just has to *know*.

-E2BIG?

--D
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Quoted 3 lines · Omar Sandoval

3. Both XFS and Btrfs cap each dedupe operation to 16MB, but the implicit EOF gets around this in the existing XFS implementation. I copied this for the Btrfs implementation.

Somewhat tangential to this patch, but on the dedup topic: Can we raise or drop that 16MB limit?

The maximum btrfs extent length is 128MB. Currently the btrfs dedup behavior for a 128MB extent is to generate 8x16MB shared extent references with different extent offsets to a single 128MB physical extent. These references no longer look like the original 128MB extent to a userspace dedup tool. That raises the difficulty level substantially for a userspace dedup tool when it tries to figure out which extents to keep and which to discard or rewrite.

XFS may not have this problem--I haven't checked.

Even if we want to keep the 16MB limit, there's also no way to query the kernel from userspace to find out what the limit is, other than by trial and error. It's not even in a header file, userspace just has to *know*.

Quoted 8 lines · Zygo Blaxell

Quoted 3 lines · Omar Sandoval

3. Both XFS and Btrfs cap each dedupe operation to 16MB, but the implicit EOF gets around this in the existing XFS implementation. I copied this for the Btrfs implementation.

Somewhat tangential to this patch, but on the dedup topic: Can we raise or drop that 16MB limit?

Quoted 7 lines

The maximum btrfs extent length is 128MB. Currently the btrfs dedup behavior for a 128MB extent is to generate 8x16MB shared extent references with different extent offsets to a single 128MB physical extent. These references no longer look like the original 128MB extent to a userspace dedup tool. That raises the difficulty level substantially for a userspace dedup tool when it tries to figure out which extents to keep and which to discard or rewrite.

That, IMO, is a btrfs design/implementation problem, not a problem with the API. Applications are always going to end up doing things that aren't perfectly aligned to extent boundaries or sizes regardless of the size limit that is placed on the dedupe ranges.

Quoted 1 line

XFS may not have this problem--I haven't checked.

It doesn't - it tracks shared blocks exactly and merges adjacent extent records whenever possible.

Quoted 3 lines

Even if we want to keep the 16MB limit, there's also no way to query the kernel from userspace to find out what the limit is, other than by trial and error. It's not even in a header file, userspace just has to *know*.

So add a define to the API to make it visible to applications and document it in the man page.

Cheers,

Dave.

Signature · 2 lines

Dave Chinner
[email protected]

Quoted 17 lines · Dave Chinner

Quoted 15 lines · Zygo Blaxell

Quoted 3 lines · Omar Sandoval

3. Both XFS and Btrfs cap each dedupe operation to 16MB, but the implicit EOF gets around this in the existing XFS implementation. I copied this for the Btrfs implementation.

Somewhat tangential to this patch, but on the dedup topic: Can we raise or drop that 16MB limit?

The maximum btrfs extent length is 128MB. Currently the btrfs dedup behavior for a 128MB extent is to generate 8x16MB shared extent references with different extent offsets to a single 128MB physical extent. These references no longer look like the original 128MB extent to a userspace dedup tool. That raises the difficulty level substantially for a userspace dedup tool when it tries to figure out which extents to keep and which to discard or rewrite.

Quoted 4 lines

That, IMO, is a btrfs design/implementation problem, not a problem with the API. Applications are always going to end up doing things that aren't perfectly aligned to extent boundaries or sizes regardless of the size limit that is placed on the dedupe ranges.

Given that XFS doesn't have all the problems btrfs does, why does XFS have the same aribitrary size limit? Especially since XFS demonstrably doesn't need it?

Quoted 23 lines · Zygo Blaxell

Quoted 21 lines · Dave Chinner

Quoted 8 lines · Zygo Blaxell

Quoted 3 lines · Omar Sandoval

3. Both XFS and Btrfs cap each dedupe operation to 16MB, but the implicit EOF gets around this in the existing XFS implementation. I copied this for the Btrfs implementation.

Somewhat tangential to this patch, but on the dedup topic: Can we raise or drop that 16MB limit?

Quoted 7 lines

The maximum btrfs extent length is 128MB. Currently the btrfs dedup behavior for a 128MB extent is to generate 8x16MB shared extent references with different extent offsets to a single 128MB physical extent. These references no longer look like the original 128MB extent to a userspace dedup tool. That raises the difficulty level substantially for a userspace dedup tool when it tries to figure out which extents to keep and which to discard or rewrite.

That, IMO, is a btrfs design/implementation problem, not a problem with the API. Applications are always going to end up doing things that aren't perfectly aligned to extent boundaries or sizes regardless of the size limit that is placed on the dedupe ranges.

Quoted 3 lines

Given that XFS doesn't have all the problems btrfs does, why does XFS have the same aribitrary size limit? Especially since XFS demonstrably doesn't need it?

Creating a new-but-slightly-incompatible jsut for XFS makes no sense - we have multiple filesystems that support this functionality and so they all should use the same APIs and present (as far as is possible) the same behaviour to userspace.

IOWs it's more important to use existing APIs than to invent a new one that does almost the same thing. This way userspace applications don't need to be changed to support new XFS functionality and we make life easier for everyone.

A shiny new API without warts would
be nice, but we've already got to support the existing one forever, it does the job we need and so it's less burden on everyone if we just use it as is.

Cheers,

Dave.

Signature · 2 lines

Dave Chinner
[email protected]

Quoted 28 lines · Dave Chinner

Quoted 26 lines · Zygo Blaxell

Quoted 17 lines · Dave Chinner

Quoted 8 lines · Zygo Blaxell

Quoted 3 lines · Omar Sandoval

3. Both XFS and Btrfs cap each dedupe operation to 16MB, but the implicit EOF gets around this in the existing XFS implementation. I copied this for the Btrfs implementation.

Somewhat tangential to this patch, but on the dedup topic: Can we raise or drop that 16MB limit?

Quoted 7 lines

The maximum btrfs extent length is 128MB. Currently the btrfs dedup behavior for a 128MB extent is to generate 8x16MB shared extent references with different extent offsets to a single 128MB physical extent. These references no longer look like the original 128MB extent to a userspace dedup tool. That raises the difficulty level substantially for a userspace dedup tool when it tries to figure out which extents to keep and which to discard or rewrite.

Quoted 4 lines

That, IMO, is a btrfs design/implementation problem, not a problem with the API. Applications are always going to end up doing things that aren't perfectly aligned to extent boundaries or sizes regardless of the size limit that is placed on the dedupe ranges.

Given that XFS doesn't have all the problems btrfs does, why does XFS have the same aribitrary size limit? Especially since XFS demonstrably doesn't need it?

Quoted 4 lines

Creating a new-but-slightly-incompatible jsut for XFS makes no sense - we have multiple filesystems that support this functionality and so they all should use the same APIs and present (as far as is possible) the same behaviour to userspace.

OK. Let's just remove the limit on all the filesystems then. XFS doesn't need it, and btrfs can be fixed.

Quoted 4 lines

IOWs it's more important to use existing APIs than to invent a new one that does almost the same thing. This way userspace applications don't need to be changed to support new XFS functionality and we make life easier for everyone.

Except removing the limit doesn't work that way. An application that didn't impose an undocumented limit on itself wouldn't break when moved to a filesystem that imposed no such limit, i.e. if XFS had no limit, an application that moved from btrfs to XFS would just work.

Quoted 34 lines · Zygo Blaxell

Quoted 32 lines · Dave Chinner

Quoted 18 lines · Zygo Blaxell

Quoted 17 lines · Dave Chinner

Quoted 15 lines · Zygo Blaxell

Quoted 3 lines · Omar Sandoval

3. Both XFS and Btrfs cap each dedupe operation to 16MB, but the implicit EOF gets around this in the existing XFS implementation. I copied this for the Btrfs implementation.

Somewhat tangential to this patch, but on the dedup topic: Can we raise or drop that 16MB limit?

The maximum btrfs extent length is 128MB. Currently the btrfs dedup behavior for a 128MB extent is to generate 8x16MB shared extent references with different extent offsets to a single 128MB physical extent. These references no longer look like the original 128MB extent to a userspace dedup tool. That raises the difficulty level substantially for a userspace dedup tool when it tries to figure out which extents to keep and which to discard or rewrite.

Quoted 8 lines

Quoted 4 lines

That, IMO, is a btrfs design/implementation problem, not a problem with the API. Applications are always going to end up doing things that aren't perfectly aligned to extent boundaries or sizes regardless of the size limit that is placed on the dedupe ranges.

Given that XFS doesn't have all the problems btrfs does, why does XFS have the same aribitrary size limit? Especially since XFS demonstrably doesn't need it?

Creating a new-but-slightly-incompatible jsut for XFS makes no sense - we have multiple filesystems that support this functionality and so they all should use the same APIs and present (as far as is possible) the same behaviour to userspace.

Quoted 2 lines

OK. Let's just remove the limit on all the filesystems then. XFS doesn't need it, and btrfs can be fixed.

Yet applications still have to support kernel versions where btrfs has a limit. IOWs, we can remove the limit for future improvement, but that doesn't mean userspace is free from having to know about the existing limit constraints.

That is, once a behaviour has been exposed to userspace through an API, we can't just change it and act like it was always that way - apps still have to support kernels that expose the old behaviour. i.e. the old behaviour is there forever, and this why designing userspace APIs is /hard/. It's also why it's better to use an existing, slightly less than ideal API than invent a new one that will simply have different problems exposed in future...

Quoted 9 lines

Quoted 4 lines

IOWs it's more important to use existing APIs than to invent a new one that does almost the same thing. This way userspace applications don't need to be changed to support new XFS functionality and we make life easier for everyone.

Except removing the limit doesn't work that way. An application that didn't impose an undocumented limit on itself wouldn't break when moved to a filesystem that imposed no such limit, i.e. if XFS had no limit, an application that moved from btrfs to XFS would just work.

It goes /both ways/ though. Write an app on XFS that does not care about limits and it won't work on btrfs because it gets unexpected errors.

Cheers,

Dave.

Signature · 2 lines

Dave Chinner
[email protected]

Keep in mind that the number of bytes deduped is returned to userspace via file_dedupe_range.info[x].bytes_deduped, so a properly functioning userspace program actually /can/ detect that its 128MB request got cut down to only 16MB and re-issue the request with the offsets moved up by 16MB. The dedupe client in xfs_io (see dedupe_ioctl() in io/reflink.c) implements this strategy. duperemove (the only other user I know of) also does this.

So it's really no big deal to increase the limit beyond 16MB, eliminate it entirely, or even change it to cap the total request size while dropping the per-item IO limit.

As I mentioned in my other reply, the only hesitation I have for not killing XFS_MAX_DEDUPE_LEN is that I feel that 2GB is enough IO for a single ioctl call.

On Wed, Nov 23, 2016 at 05:26:18PM -0800, Darrick J. Wong wrote:
[...]

Quoted 8 lines

Keep in mind that the number of bytes deduped is returned to userspace via file_dedupe_range.info[x].bytes_deduped, so a properly functioning userspace program actually /can/ detect that its 128MB request got cut down to only 16MB and re-issue the request with the offsets moved up by 16MB. The dedupe client in xfs_io (see dedupe_ioctl() in io/reflink.c) implements this strategy. duperemove (the only other user I know of) also does this.

Quoted 7 lines

So it's really no big deal to increase the limit beyond 16MB, eliminate it entirely, or even change it to cap the total request size while dropping the per-item IO limit.

As I mentioned in my other reply, the only hesitation I have for not killing XFS_MAX_DEDUPE_LEN is that I feel that 2GB is enough IO for a single ioctl call.

Everything's relative. btrfs has ioctls that will do hundreds of terabytes of IO and take months to run. 2GB of data is nothing.

Deduping entire 100TB files with a single ioctl call makes as much sense to me as reflink copying them with a single ioctl call. The only reason I see to keep the limit is to work around something wrong with the implementation.