[PATCH 0/4] Fix incorrect splitting logic in btrfs_drop_extent_map_range

[PATCH 0/4] Fix incorrect splitting logic in btrfs_drop_extent_map_range

[Josef Bacik]

We have been hitting a fair number of warnings in btrfs_drop_extent_map_range
and in unpin_extent_map in production.  Upon investigation I discovered we were
splitting improperly when we call btrfs_drop_extent_map_range with skip_pinned.
This results in invalid extent_maps in the inode's io_tree, which in turn wreaks
all sorts of havoc, mostly in the form of these WARN_ON()'s.  This took me a
while to spot so I have a bunch of self-tests that test various functionality of
btrfs_drop_extent_map_range and btrfs_add_extent_mapping, with one test that
actual exercises the bug.

This has been broken for a while, and thankfully is only triggered in certain
cases with relocation on.  Our environment uses auto relocation heavily which is
why we hit this reliably, but the incident rate is still relatively low.  The
bug was introduced over 10 years ago, it probably could be limited to being
backported to the most recent kernels, basically anytime after Filipe's cleaning
up of this code.  Thanks,

Josef

Josef Bacik (4):
  btrfs: fix incorrect splitting in btrfs_drop_extent_map_range
  btrfs: add extent_map tests for dropping with odd layouts
  btrfs: add a self test for btrfs_add_extent_mapping
  btrfs: test invalid splitting when skipping pinned drop extent_map

 fs/btrfs/extent_map.c             |   6 +-
 fs/btrfs/tests/extent-map-tests.c | 414 ++++++++++++++++++++++++++++++
 2 files changed, 416 insertions(+), 4 deletions(-)

-- 
2.26.3

[PATCH 1/4] btrfs: fix incorrect splitting in btrfs_drop_extent_map_range

[Josef Bacik]

In production we were seeing a variety of WARN_ON()'s in the extent_map
code, specifically in btrfs_drop_extent_map_range() when we have to call
add_extent_mapping() for our second split.

Consider the following extent map layout

PINNED
[0 16K)  [32K, 48K)

and then we call btrfs_drop_extent_map_range for [0, 36K), with
skip_pinned == true.  The initial loop will have

start = 0
end = 36K
len = 36K

we will find the [0, 16k) extent, but since we are pinned we will skip
it, which has this cod

	start = em_end;
	if (end != (u64)-1)
		len = start + len - em_end;

em_end here is 16K, so now the values are

start = 16K
len = 16K + 36K - 16K = 36K

len should instead be 20K.  This is a problem when we find the next
extent at [32K, 48K), we need to split this extent to leave [36K, 48k),
however the code for the split looks like this

	split->start = start + len;
	split->len = em_end - (start + len);

In this case we have

em_end = 48K
split->start = 16K + 36K //this should be 16K + 20K
split->len = 48K - (16K + 36K) // this overflows as 16K + 36K is 52K

and now we have an invalid extent_map in the tree that potentially
overlaps other entries in the extent map.  Even in the non-overlapping
case we will have split->start set improperly, which will cause problems
with any block related calculations.

We don't actually need len in this loop, we can simply use end as our
end point, and only adjust start up when we find a pinned extent we need
to skip.

Adjust the logic to do this, which keeps us from inserting an invalid
extent map.

We only skip_pinned in the relocation case, so this is relatively rare,
except in the case where you are running relocation a lot, which can
happen with auto relocation on.

Fixes: 55ef68990029 ("Btrfs: Fix btrfs_drop_extent_cache for skip pinned case")
Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 fs/btrfs/extent_map.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)

diff --git a/fs/btrfs/extent_map.c b/fs/btrfs/extent_map.c
index 0cdb3e86f29b..a6d8368ed0ed 100644
--- a/fs/btrfs/extent_map.c
+++ b/fs/btrfs/extent_map.c
@@ -760,8 +760,6 @@ void btrfs_drop_extent_map_range(struct btrfs_inode *inode, u64 start, u64 end,
 
 		if (skip_pinned && test_bit(EXTENT_FLAG_PINNED, &em->flags)) {
 			start = em_end;
-			if (end != (u64)-1)
-				len = start + len - em_end;
 			goto next;
 		}
 
@@ -829,8 +827,8 @@ void btrfs_drop_extent_map_range(struct btrfs_inode *inode, u64 start, u64 end,
 				if (!split)
 					goto remove_em;
 			}
-			split->start = start + len;
-			split->len = em_end - (start + len);
+			split->start = end;
+			split->len = em_end - end;
 			split->block_start = em->block_start;
 			split->flags = flags;
 			split->compress_type = em->compress_type;
-- 
2.26.3

[PATCH 2/4] btrfs: add extent_map tests for dropping with odd layouts

[Josef Bacik]

While investigating weird problems with the extent_map I wrote a self
test testing the various edge cases of btrfs_drop_extent_map_range.
This can split in different ways and behaves different in each case, so
test the various edge cases to make sure everything is functioning
properly.

Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 fs/btrfs/tests/extent-map-tests.c | 219 ++++++++++++++++++++++++++++++
 1 file changed, 219 insertions(+)

diff --git a/fs/btrfs/tests/extent-map-tests.c b/fs/btrfs/tests/extent-map-tests.c
index ed0f36ae5346..d5f5e48ab55c 100644
--- a/fs/btrfs/tests/extent-map-tests.c
+++ b/fs/btrfs/tests/extent-map-tests.c
@@ -6,6 +6,7 @@
 #include <linux/types.h>
 #include "btrfs-tests.h"
 #include "../ctree.h"
+#include "../btrfs_inode.h"
 #include "../volumes.h"
 #include "../disk-io.h"
 #include "../block-group.h"
@@ -442,6 +443,219 @@ static int test_case_4(struct btrfs_fs_info *fs_info,
 	return ret;
 }
 
+static int add_compressed_extent(struct extent_map_tree *em_tree,
+				 const u64 start, const u64 len,
+				 const u64 block_start)
+{
+	struct extent_map *em;
+	int ret;
+
+	em = alloc_extent_map();
+	if (!em) {
+		test_std_err(TEST_ALLOC_EXTENT_MAP);
+		return -ENOMEM;
+	}
+
+	em->start = start;
+	em->len = len;
+	em->block_start = block_start;
+	em->block_len = SZ_4K;
+	set_bit(EXTENT_FLAG_COMPRESSED, &em->flags);
+	write_lock(&em_tree->lock);
+	ret = add_extent_mapping(em_tree, em, 0);
+	write_unlock(&em_tree->lock);
+	free_extent_map(em);
+	if (ret < 0) {
+		test_err("cannot add extent map [%llu, %llu)", start,
+			 start + len);
+		return ret;
+	}
+
+	return 0;
+}
+
+struct extent_range {
+	u64 start;
+	u64 len;
+};
+
+/* The valid states of the tree after every drop, as described below. */
+struct extent_range valid_ranges[][7] = {
+	{
+	  { .start = 0,			.len = SZ_8K },		/* [0, 8K) */
+	  { .start = SZ_4K * 3,		.len = SZ_4K * 3},	/* [12k, 24k) */
+	  { .start = SZ_4K * 6,		.len = SZ_4K * 3},	/* [24k, 36k) */
+	  { .start = SZ_32K + SZ_4K,	.len = SZ_4K},		/* [36k, 40k) */
+	  { .start = SZ_4K * 10,	.len = SZ_4K * 6},	/* [40k, 64k) */
+	},
+	{
+	  { .start = 0,			.len = SZ_8K },		/* [0, 8K) */
+	  { .start = SZ_4K * 5,		.len = SZ_4K},		/* [20k, 24k) */
+	  { .start = SZ_4K * 6,		.len = SZ_4K * 3},	/* [24k, 36k) */
+	  { .start = SZ_32K + SZ_4K,	.len = SZ_4K},		/* [36k, 40k) */
+	  { .start = SZ_4K * 10,	.len = SZ_4K * 6},	/* [40k, 64k) */
+	},
+	{
+	  { .start = 0,			.len = SZ_8K },		/* [0, 8K) */
+	  { .start = SZ_4K * 5,		.len = SZ_4K},		/* [20k, 24k) */
+	  { .start = SZ_4K * 6,		.len = SZ_4K},		/* [24k, 28k) */
+	  { .start = SZ_32K,		.len = SZ_4K},		/* [32k, 36k) */
+	  { .start = SZ_32K + SZ_4K,	.len = SZ_4K},		/* [36k, 40k) */
+	  { .start = SZ_4K * 10,	.len = SZ_4K * 6},	/* [40k, 64k) */
+	},
+	{
+	  { .start = 0,			.len = SZ_8K},		/* [0, 8K) */
+	  { .start = SZ_4K * 5,		.len = SZ_4K},		/* [20k, 24k) */
+	  { .start = SZ_4K * 6,		.len = SZ_4K},		/* [24k, 28k) */
+	}
+};
+
+static int validate_range(struct extent_map_tree *em_tree, int index)
+{
+	struct rb_node *n;
+	int i;
+
+	for (i = 0, n = rb_first_cached(&em_tree->map);
+	     valid_ranges[index][i].len && n; i++, n = rb_next(n)) {
+		struct extent_map *entry = rb_entry(n, struct extent_map, rb_node);
+
+		if (entry->start != valid_ranges[index][i].start) {
+			test_err("mapping has start %llu expected %llu",
+				 entry->start, valid_ranges[index][i].start);
+			return -EINVAL;
+		}
+
+		if (entry->len != valid_ranges[index][i].len) {
+			test_err("mapping has len %llu expected %llu",
+				 entry->len, valid_ranges[index][i].len);
+			return -EINVAL;
+		}
+	}
+
+	/*
+	 * We exited because we don't have any more entries in the extent_map
+	 * but we still expect more valid entries.
+	 */
+	if (valid_ranges[index][i].len) {
+		test_err("missing an entry");
+		return -EINVAL;
+	}
+
+	/* We exited the loop but still have entries in the extent map. */
+	if (n) {
+		test_err("we have a left over entry in the extent map we didn't expect");
+		return -EINVAL;
+	}
+
+	return 0;
+}
+
+/*
+ * Test scenario:
+ *
+ * Test the various edge cases of btrfs_drop_extent_map_range, create the
+ * following ranges
+ *
+ * [0, 12k)[12k, 24k)[24k, 36k)[36k, 40k)[40k,64k)
+ *
+ * And then we'll drop:
+ *
+ * [8k, 12k) - test the single front split
+ * [12k, 20k) - test the single back split
+ * [28k, 32k) - test the double split
+ * [32k, 64k) - test whole em dropping
+ *
+ * They'll have the EXTENT_FLAG_COMPRESSED flag set to keep the em tree from
+ * merging the em's.
+ */
+static int test_case_5(void)
+{
+	struct extent_map_tree *em_tree;
+	struct inode *inode = NULL;
+	u64 start, end;
+	int ret;
+
+	test_msg("Running btrfs_drop_extent_map_range tests");
+
+	inode = btrfs_new_test_inode();
+	if (!inode) {
+		test_std_err(TEST_ALLOC_INODE);
+		return -ENOMEM;
+	}
+
+	em_tree = &BTRFS_I(inode)->extent_tree;
+
+	/* [0, 12k) */
+	ret = add_compressed_extent(em_tree, 0, SZ_4K * 3, 0);
+	if (ret) {
+		test_err("cannot add extent range [0, 12K)");
+		goto out;
+	}
+
+	/* [12k, 24k) */
+	ret = add_compressed_extent(em_tree, SZ_4K * 3, SZ_4K * 3, SZ_4K);
+	if (ret) {
+		test_err("cannot add extent range [12k, 24k)");
+		goto out;
+	}
+
+	/* [24k, 36k) */
+	ret = add_compressed_extent(em_tree, SZ_4K * 6, SZ_4K * 3, SZ_8K);
+	if (ret) {
+		test_err("cannot add extent range [12k, 24k)");
+		goto out;
+	}
+
+	/* [36k, 40k) */
+	ret = add_compressed_extent(em_tree, SZ_32K + SZ_4K, SZ_4K, SZ_4K * 3);
+	if (ret) {
+		test_err("cannot add extent range [12k, 24k)");
+		goto out;
+	}
+
+	/* [40k, 64k) */
+	ret = add_compressed_extent(em_tree, SZ_4K * 10, SZ_4K * 6, SZ_16K);
+	if (ret) {
+		test_err("cannot add extent range [12k, 24k)");
+		goto out;
+	}
+
+	/* Drop [8k, 12k) */
+	start = SZ_8K;
+	end = (3 * SZ_4K) - 1;
+	btrfs_drop_extent_map_range(BTRFS_I(inode), start, end, false);
+	ret = validate_range(&BTRFS_I(inode)->extent_tree, 0);
+	if (ret)
+		goto out;
+
+	/* Drop [12k, 20k) */
+	start = SZ_4K * 3;
+	end = SZ_16K + SZ_4K - 1;
+	btrfs_drop_extent_map_range(BTRFS_I(inode), start, end, false);
+	ret = validate_range(&BTRFS_I(inode)->extent_tree, 1);
+	if (ret)
+		goto out;
+
+	/* Drop [28k, 32k) */
+	start = SZ_32K - SZ_4K;
+	end = SZ_32K - 1;
+	btrfs_drop_extent_map_range(BTRFS_I(inode), start, end, false);
+	ret = validate_range(&BTRFS_I(inode)->extent_tree, 2);
+	if (ret)
+		goto out;
+
+	/* Drop [32k, 64k) */
+	start = SZ_32K;
+	end = SZ_64K - 1;
+	btrfs_drop_extent_map_range(BTRFS_I(inode), start, end, false);
+	ret = validate_range(&BTRFS_I(inode)->extent_tree, 3);
+	if (ret)
+		goto out;
+out:
+	iput(inode);
+	return ret;
+}
+
 struct rmap_test_vector {
 	u64 raid_type;
 	u64 physical_start;
@@ -619,6 +833,11 @@ int btrfs_test_extent_map(void)
 	if (ret)
 		goto out;
 	ret = test_case_4(fs_info, em_tree);
+	if (ret)
+		goto out;
+	ret = test_case_5();
+	if (ret)
+		goto out;
 
 	test_msg("running rmap tests");
 	for (i = 0; i < ARRAY_SIZE(rmap_tests); i++) {
-- 
2.26.3

[PATCH 3/4] btrfs: add a self test for btrfs_add_extent_mapping

[Josef Bacik]

This helper is different from the normal add_extent_mapping in that it
will stuff an em into a gap that exists between overlapping em's in the
tree.  It appeared there was a bug so I wrote a self test to validate it
did the correct thing when it worked with two side by side ems.
Thankfully it is correct, but more testing is better.

Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 fs/btrfs/tests/extent-map-tests.c | 57 +++++++++++++++++++++++++++++++
 1 file changed, 57 insertions(+)

diff --git a/fs/btrfs/tests/extent-map-tests.c b/fs/btrfs/tests/extent-map-tests.c
index d5f5e48ab55c..18ab03f0d029 100644
--- a/fs/btrfs/tests/extent-map-tests.c
+++ b/fs/btrfs/tests/extent-map-tests.c
@@ -656,6 +656,60 @@ static int test_case_5(void)
 	return ret;
 }
 
+/*
+ * Test the btrfs_add_extent_mapping helper which will attempt to create an em
+ * for areas between two existing ems.  Validate it doesn't do this when there
+ * are two unmerged em's side by side.
+ */
+static int test_case_6(struct btrfs_fs_info *fs_info,
+		       struct extent_map_tree *em_tree)
+{
+	struct extent_map *em = NULL;
+	int ret;
+
+	ret = add_compressed_extent(em_tree, 0, SZ_4K, 0);
+	if (ret)
+		goto out;
+
+	ret = add_compressed_extent(em_tree, SZ_4K, SZ_4K, 0);
+	if (ret)
+		goto out;
+
+	em = alloc_extent_map();
+	if (!em) {
+		test_std_err(TEST_ALLOC_EXTENT_MAP);
+		return -ENOMEM;
+	}
+
+	em->start = SZ_4K;
+	em->len = SZ_4K;
+	em->block_start = SZ_16K;
+	em->block_len = SZ_16K;
+	write_lock(&em_tree->lock);
+	ret = btrfs_add_extent_mapping(fs_info, em_tree, &em, 0, SZ_8K);
+	write_unlock(&em_tree->lock);
+
+	if (ret != 0) {
+		test_err("got an error when adding our em: %d", ret);
+		goto out;
+	}
+
+	ret = -EINVAL;
+	if (em->start != 0) {
+		test_err("unexpected em->start at %llu, wanted 0", em->start);
+		goto out;
+	}
+	if (em->len != SZ_4K) {
+		test_err("unexpected em->len %llu, expected 4K", em->len);
+		goto out;
+	}
+	ret = 0;
+out:
+	free_extent_map(em);
+	free_extent_map_tree(em_tree);
+	return ret;
+}
+
 struct rmap_test_vector {
 	u64 raid_type;
 	u64 physical_start;
@@ -836,6 +890,9 @@ int btrfs_test_extent_map(void)
 	if (ret)
 		goto out;
 	ret = test_case_5();
+	if (ret)
+		goto out;
+	ret = test_case_6(fs_info, em_tree);
 	if (ret)
 		goto out;
 
-- 
2.26.3

[PATCH 4/4] btrfs: test invalid splitting when skipping pinned drop extent_map

[Josef Bacik]

This reproduces the bug fixed by "btrfs: fix incorrect splitting in
btrfs_drop_extent_map_range", we were improperly calculating the range
for the split extent.  Add a test that exercises this scenario and
validates that we get the correct resulting extent_maps in our tree.

Signed-off-by: Josef Bacik <josef@toxicpanda.com>
---
 fs/btrfs/tests/extent-map-tests.c | 138 ++++++++++++++++++++++++++++++
 1 file changed, 138 insertions(+)

diff --git a/fs/btrfs/tests/extent-map-tests.c b/fs/btrfs/tests/extent-map-tests.c
index 18ab03f0d029..06820a8b4d1f 100644
--- a/fs/btrfs/tests/extent-map-tests.c
+++ b/fs/btrfs/tests/extent-map-tests.c
@@ -710,6 +710,141 @@ static int test_case_6(struct btrfs_fs_info *fs_info,
 	return ret;
 }
 
+/*
+ * Regression test for btrfs_drop_extent_map_range.  Calling with skip_pinned ==
+ * true would mess up the start/end calculations and subsequent splits would be
+ * incorrect.
+ */
+static int test_case_7(void)
+{
+	struct extent_map_tree *em_tree;
+	struct extent_map *em = NULL;
+	struct inode *inode = NULL;
+	int ret;
+
+	test_msg("Running btrfs_drop_extent_cache with pinned");
+
+	inode = btrfs_new_test_inode();
+	if (!inode) {
+		test_std_err(TEST_ALLOC_INODE);
+		return -ENOMEM;
+	}
+
+	em_tree = &BTRFS_I(inode)->extent_tree;
+
+	em = alloc_extent_map();
+	if (!em) {
+		test_std_err(TEST_ALLOC_EXTENT_MAP);
+		ret = -ENOMEM;
+		goto out;
+	}
+
+	/* [0, 16K), pinned */
+	em->start = 0;
+	em->len = SZ_16K;
+	em->block_start = 0;
+	em->block_len = SZ_4K;
+	set_bit(EXTENT_FLAG_PINNED, &em->flags);
+	write_lock(&em_tree->lock);
+	ret = add_extent_mapping(em_tree, em, 0);
+	write_unlock(&em_tree->lock);
+	if (ret < 0) {
+		test_err("couldn't add extent map");
+		goto out;
+	}
+	free_extent_map(em);
+
+	em = alloc_extent_map();
+	if (!em) {
+		test_std_err(TEST_ALLOC_EXTENT_MAP);
+		ret = -ENOMEM;
+		goto out;
+	}
+
+	/* [32K, 48K), not pinned */
+	em->start = SZ_32K;
+	em->len = SZ_16K;
+	em->block_start = SZ_32K;
+	em->block_len = SZ_16K;
+	write_lock(&em_tree->lock);
+	ret = add_extent_mapping(em_tree, em, 0);
+	write_unlock(&em_tree->lock);
+	if (ret < 0) {
+		test_err("couldn't add extent map");
+		goto out;
+	}
+	free_extent_map(em);
+
+	/*
+	 * Drop [0, 36K) This should skip the [0, 4K) extent and then split the
+	 * [32K, 48K) extent.
+	 */
+	btrfs_drop_extent_map_range(BTRFS_I(inode), 0, (36 * SZ_1K) - 1, true);
+
+	/* Make sure our extent maps look sane. */
+	ret = -EINVAL;
+
+	em = lookup_extent_mapping(em_tree, 0, SZ_16K);
+	if (!em) {
+		test_err("didn't find an em at 0 as expected");
+		goto out;
+	}
+
+	if (em->start != 0) {
+		test_err("em->start is %llu, expected 0", em->start);
+		goto out;
+	}
+
+	if (em->len != SZ_16K) {
+		test_err("em->len is %llu, expected 16K", em->len);
+		goto out;
+	}
+
+	free_extent_map(em);
+
+	read_lock(&em_tree->lock);
+	em = lookup_extent_mapping(em_tree, SZ_16K, SZ_16K);
+	read_unlock(&em_tree->lock);
+	if (em) {
+		test_err("found an em when we weren't expecting one");
+		goto out;
+	}
+
+	read_lock(&em_tree->lock);
+	em = lookup_extent_mapping(em_tree, SZ_32K, SZ_16K);
+	read_unlock(&em_tree->lock);
+	if (!em) {
+		test_err("didn't find an em at 32K as expected");
+		goto out;
+	}
+
+	if (em->start != (36 * SZ_1K)) {
+		test_err("em->start is %llu, expected 36K", em->start);
+		goto out;
+	}
+
+	if (em->len != (12 * SZ_1K)) {
+		test_err("em->len is %llu, expected 12K", em->len);
+		goto out;
+	}
+
+	free_extent_map(em);
+
+	read_lock(&em_tree->lock);
+	em = lookup_extent_mapping(em_tree, 48 * SZ_1K, (u64)-1);
+	read_unlock(&em_tree->lock);
+	if (em) {
+		test_err("found an unexpected em above 48K");
+		goto out;
+	}
+
+	ret = 0;
+out:
+	free_extent_map(em);
+	iput(inode);
+	return ret;
+}
+
 struct rmap_test_vector {
 	u64 raid_type;
 	u64 physical_start;
@@ -893,6 +1028,9 @@ int btrfs_test_extent_map(void)
 	if (ret)
 		goto out;
 	ret = test_case_6(fs_info, em_tree);
+	if (ret)
+		goto out;
+	ret = test_case_7();
 	if (ret)
 		goto out;
 
-- 
2.26.3

Re: [PATCH 0/4] Fix incorrect splitting logic in btrfs_drop_extent_map_range

[David Sterba]

On Thu, Aug 17, 2023 at 04:57:29PM -0400, Josef Bacik wrote:
> We have been hitting a fair number of warnings in btrfs_drop_extent_map_range
> and in unpin_extent_map in production.  Upon investigation I discovered we were
> splitting improperly when we call btrfs_drop_extent_map_range with skip_pinned.
> This results in invalid extent_maps in the inode's io_tree, which in turn wreaks
> all sorts of havoc, mostly in the form of these WARN_ON()'s.  This took me a
> while to spot so I have a bunch of self-tests that test various functionality of
> btrfs_drop_extent_map_range and btrfs_add_extent_mapping, with one test that
> actual exercises the bug.
> 
> This has been broken for a while, and thankfully is only triggered in certain
> cases with relocation on.  Our environment uses auto relocation heavily which is
> why we hit this reliably, but the incident rate is still relatively low.  The
> bug was introduced over 10 years ago, it probably could be limited to being
> backported to the most recent kernels, basically anytime after Filipe's cleaning
> up of this code.  Thanks,
> 
> Josef
> 
> Josef Bacik (4):
>   btrfs: fix incorrect splitting in btrfs_drop_extent_map_range
>   btrfs: add extent_map tests for dropping with odd layouts
>   btrfs: add a self test for btrfs_add_extent_mapping
>   btrfs: test invalid splitting when skipping pinned drop extent_map

Nice, we have a new record holder, thanks for tracking it down and for
adding the tests. I'll add the patches to misc-next but review is still open.

Re: [PATCH 1/4] btrfs: fix incorrect splitting in btrfs_drop_extent_map_range

[Filipe Manana]

On Thu, Aug 17, 2023 at 04:57:30PM -0400, Josef Bacik wrote:
> In production we were seeing a variety of WARN_ON()'s in the extent_map
> code, specifically in btrfs_drop_extent_map_range() when we have to call
> add_extent_mapping() for our second split.
> 
> Consider the following extent map layout
> 
> PINNED
> [0 16K)  [32K, 48K)
> 
> and then we call btrfs_drop_extent_map_range for [0, 36K), with
> skip_pinned == true.  The initial loop will have
> 
> start = 0
> end = 36K
> len = 36K
> 
> we will find the [0, 16k) extent, but since we are pinned we will skip
> it, which has this cod
> 
> 	start = em_end;
> 	if (end != (u64)-1)
> 		len = start + len - em_end;
> 
> em_end here is 16K, so now the values are
> 
> start = 16K
> len = 16K + 36K - 16K = 36K
> 
> len should instead be 20K.  This is a problem when we find the next
> extent at [32K, 48K), we need to split this extent to leave [36K, 48k),
> however the code for the split looks like this
> 
> 	split->start = start + len;
> 	split->len = em_end - (start + len);
> 
> In this case we have
> 
> em_end = 48K
> split->start = 16K + 36K //this should be 16K + 20K
> split->len = 48K - (16K + 36K) // this overflows as 16K + 36K is 52K
> 
> and now we have an invalid extent_map in the tree that potentially
> overlaps other entries in the extent map.  Even in the non-overlapping
> case we will have split->start set improperly, which will cause problems
> with any block related calculations.
> 
> We don't actually need len in this loop, we can simply use end as our
> end point, and only adjust start up when we find a pinned extent we need
> to skip.
> 
> Adjust the logic to do this, which keeps us from inserting an invalid
> extent map.
> 
> We only skip_pinned in the relocation case, so this is relatively rare,
> except in the case where you are running relocation a lot, which can
> happen with auto relocation on.
> 
> Fixes: 55ef68990029 ("Btrfs: Fix btrfs_drop_extent_cache for skip pinned case")
> Signed-off-by: Josef Bacik <josef@toxicpanda.com>

Reviewed-by: Filipe Manana <fdmanana@suse.com>

Looks good, thanks.

> ---
>  fs/btrfs/extent_map.c | 6 ++----
>  1 file changed, 2 insertions(+), 4 deletions(-)
> 
> diff --git a/fs/btrfs/extent_map.c b/fs/btrfs/extent_map.c
> index 0cdb3e86f29b..a6d8368ed0ed 100644
> --- a/fs/btrfs/extent_map.c
> +++ b/fs/btrfs/extent_map.c
> @@ -760,8 +760,6 @@ void btrfs_drop_extent_map_range(struct btrfs_inode *inode, u64 start, u64 end,
>  
>  		if (skip_pinned && test_bit(EXTENT_FLAG_PINNED, &em->flags)) {
>  			start = em_end;
> -			if (end != (u64)-1)
> -				len = start + len - em_end;
>  			goto next;
>  		}
>  
> @@ -829,8 +827,8 @@ void btrfs_drop_extent_map_range(struct btrfs_inode *inode, u64 start, u64 end,
>  				if (!split)
>  					goto remove_em;
>  			}
> -			split->start = start + len;
> -			split->len = em_end - (start + len);
> +			split->start = end;
> +			split->len = em_end - end;
>  			split->block_start = em->block_start;
>  			split->flags = flags;
>  			split->compress_type = em->compress_type;
> -- 
> 2.26.3
> 

Re: [PATCH 2/4] btrfs: add extent_map tests for dropping with odd layouts

[Filipe Manana]

On Thu, Aug 17, 2023 at 04:57:31PM -0400, Josef Bacik wrote:
> While investigating weird problems with the extent_map I wrote a self
> test testing the various edge cases of btrfs_drop_extent_map_range.
> This can split in different ways and behaves different in each case, so
> test the various edge cases to make sure everything is functioning
> properly.
> 
> Signed-off-by: Josef Bacik <josef@toxicpanda.com>

Reviewed-by: Filipe Manana <fdmanana@suse.com>

Looks good, just some minor comment below.

> ---
>  fs/btrfs/tests/extent-map-tests.c | 219 ++++++++++++++++++++++++++++++
>  1 file changed, 219 insertions(+)
> 
> diff --git a/fs/btrfs/tests/extent-map-tests.c b/fs/btrfs/tests/extent-map-tests.c
> index ed0f36ae5346..d5f5e48ab55c 100644
> --- a/fs/btrfs/tests/extent-map-tests.c
> +++ b/fs/btrfs/tests/extent-map-tests.c
> @@ -6,6 +6,7 @@
>  #include <linux/types.h>
>  #include "btrfs-tests.h"
>  #include "../ctree.h"
> +#include "../btrfs_inode.h"
>  #include "../volumes.h"
>  #include "../disk-io.h"
>  #include "../block-group.h"
> @@ -442,6 +443,219 @@ static int test_case_4(struct btrfs_fs_info *fs_info,
>  	return ret;
>  }
>  
> +static int add_compressed_extent(struct extent_map_tree *em_tree,
> +				 const u64 start, const u64 len,
> +				 const u64 block_start)
> +{
> +	struct extent_map *em;
> +	int ret;
> +
> +	em = alloc_extent_map();
> +	if (!em) {
> +		test_std_err(TEST_ALLOC_EXTENT_MAP);
> +		return -ENOMEM;
> +	}
> +
> +	em->start = start;
> +	em->len = len;
> +	em->block_start = block_start;
> +	em->block_len = SZ_4K;
> +	set_bit(EXTENT_FLAG_COMPRESSED, &em->flags);
> +	write_lock(&em_tree->lock);
> +	ret = add_extent_mapping(em_tree, em, 0);
> +	write_unlock(&em_tree->lock);
> +	free_extent_map(em);
> +	if (ret < 0) {
> +		test_err("cannot add extent map [%llu, %llu)", start,
> +			 start + len);
> +		return ret;
> +	}
> +
> +	return 0;
> +}
> +
> +struct extent_range {
> +	u64 start;
> +	u64 len;
> +};
> +
> +/* The valid states of the tree after every drop, as described below. */
> +struct extent_range valid_ranges[][7] = {
> +	{
> +	  { .start = 0,			.len = SZ_8K },		/* [0, 8K) */
> +	  { .start = SZ_4K * 3,		.len = SZ_4K * 3},	/* [12k, 24k) */
> +	  { .start = SZ_4K * 6,		.len = SZ_4K * 3},	/* [24k, 36k) */
> +	  { .start = SZ_32K + SZ_4K,	.len = SZ_4K},		/* [36k, 40k) */
> +	  { .start = SZ_4K * 10,	.len = SZ_4K * 6},	/* [40k, 64k) */
> +	},
> +	{
> +	  { .start = 0,			.len = SZ_8K },		/* [0, 8K) */
> +	  { .start = SZ_4K * 5,		.len = SZ_4K},		/* [20k, 24k) */
> +	  { .start = SZ_4K * 6,		.len = SZ_4K * 3},	/* [24k, 36k) */
> +	  { .start = SZ_32K + SZ_4K,	.len = SZ_4K},		/* [36k, 40k) */
> +	  { .start = SZ_4K * 10,	.len = SZ_4K * 6},	/* [40k, 64k) */
> +	},
> +	{
> +	  { .start = 0,			.len = SZ_8K },		/* [0, 8K) */
> +	  { .start = SZ_4K * 5,		.len = SZ_4K},		/* [20k, 24k) */
> +	  { .start = SZ_4K * 6,		.len = SZ_4K},		/* [24k, 28k) */
> +	  { .start = SZ_32K,		.len = SZ_4K},		/* [32k, 36k) */
> +	  { .start = SZ_32K + SZ_4K,	.len = SZ_4K},		/* [36k, 40k) */
> +	  { .start = SZ_4K * 10,	.len = SZ_4K * 6},	/* [40k, 64k) */
> +	},
> +	{
> +	  { .start = 0,			.len = SZ_8K},		/* [0, 8K) */
> +	  { .start = SZ_4K * 5,		.len = SZ_4K},		/* [20k, 24k) */
> +	  { .start = SZ_4K * 6,		.len = SZ_4K},		/* [24k, 28k) */
> +	}
> +};
> +
> +static int validate_range(struct extent_map_tree *em_tree, int index)
> +{
> +	struct rb_node *n;
> +	int i;
> +
> +	for (i = 0, n = rb_first_cached(&em_tree->map);
> +	     valid_ranges[index][i].len && n; i++, n = rb_next(n)) {
> +		struct extent_map *entry = rb_entry(n, struct extent_map, rb_node);
> +
> +		if (entry->start != valid_ranges[index][i].start) {
> +			test_err("mapping has start %llu expected %llu",
> +				 entry->start, valid_ranges[index][i].start);
> +			return -EINVAL;
> +		}
> +
> +		if (entry->len != valid_ranges[index][i].len) {
> +			test_err("mapping has len %llu expected %llu",
> +				 entry->len, valid_ranges[index][i].len);
> +			return -EINVAL;
> +		}
> +	}
> +
> +	/*
> +	 * We exited because we don't have any more entries in the extent_map
> +	 * but we still expect more valid entries.
> +	 */
> +	if (valid_ranges[index][i].len) {
> +		test_err("missing an entry");
> +		return -EINVAL;
> +	}
> +
> +	/* We exited the loop but still have entries in the extent map. */
> +	if (n) {
> +		test_err("we have a left over entry in the extent map we didn't expect");
> +		return -EINVAL;
> +	}
> +
> +	return 0;
> +}
> +
> +/*
> + * Test scenario:
> + *
> + * Test the various edge cases of btrfs_drop_extent_map_range, create the
> + * following ranges
> + *
> + * [0, 12k)[12k, 24k)[24k, 36k)[36k, 40k)[40k,64k)
> + *
> + * And then we'll drop:
> + *
> + * [8k, 12k) - test the single front split
> + * [12k, 20k) - test the single back split
> + * [28k, 32k) - test the double split
> + * [32k, 64k) - test whole em dropping
> + *
> + * They'll have the EXTENT_FLAG_COMPRESSED flag set to keep the em tree from
> + * merging the em's.
> + */
> +static int test_case_5(void)
> +{
> +	struct extent_map_tree *em_tree;
> +	struct inode *inode = NULL;

This initialization is not needed.

> +	u64 start, end;
> +	int ret;
> +
> +	test_msg("Running btrfs_drop_extent_map_range tests");
> +
> +	inode = btrfs_new_test_inode();
> +	if (!inode) {
> +		test_std_err(TEST_ALLOC_INODE);
> +		return -ENOMEM;
> +	}
> +
> +	em_tree = &BTRFS_I(inode)->extent_tree;
> +
> +	/* [0, 12k) */
> +	ret = add_compressed_extent(em_tree, 0, SZ_4K * 3, 0);
> +	if (ret) {
> +		test_err("cannot add extent range [0, 12K)");
> +		goto out;
> +	}
> +
> +	/* [12k, 24k) */
> +	ret = add_compressed_extent(em_tree, SZ_4K * 3, SZ_4K * 3, SZ_4K);
> +	if (ret) {
> +		test_err("cannot add extent range [12k, 24k)");
> +		goto out;
> +	}
> +
> +	/* [24k, 36k) */
> +	ret = add_compressed_extent(em_tree, SZ_4K * 6, SZ_4K * 3, SZ_8K);
> +	if (ret) {
> +		test_err("cannot add extent range [12k, 24k)");
> +		goto out;
> +	}
> +
> +	/* [36k, 40k) */
> +	ret = add_compressed_extent(em_tree, SZ_32K + SZ_4K, SZ_4K, SZ_4K * 3);
> +	if (ret) {
> +		test_err("cannot add extent range [12k, 24k)");
> +		goto out;
> +	}
> +
> +	/* [40k, 64k) */
> +	ret = add_compressed_extent(em_tree, SZ_4K * 10, SZ_4K * 6, SZ_16K);
> +	if (ret) {
> +		test_err("cannot add extent range [12k, 24k)");
> +		goto out;
> +	}
> +
> +	/* Drop [8k, 12k) */
> +	start = SZ_8K;
> +	end = (3 * SZ_4K) - 1;
> +	btrfs_drop_extent_map_range(BTRFS_I(inode), start, end, false);
> +	ret = validate_range(&BTRFS_I(inode)->extent_tree, 0);
> +	if (ret)
> +		goto out;
> +
> +	/* Drop [12k, 20k) */
> +	start = SZ_4K * 3;
> +	end = SZ_16K + SZ_4K - 1;
> +	btrfs_drop_extent_map_range(BTRFS_I(inode), start, end, false);
> +	ret = validate_range(&BTRFS_I(inode)->extent_tree, 1);
> +	if (ret)
> +		goto out;
> +
> +	/* Drop [28k, 32k) */
> +	start = SZ_32K - SZ_4K;
> +	end = SZ_32K - 1;
> +	btrfs_drop_extent_map_range(BTRFS_I(inode), start, end, false);
> +	ret = validate_range(&BTRFS_I(inode)->extent_tree, 2);
> +	if (ret)
> +		goto out;
> +
> +	/* Drop [32k, 64k) */
> +	start = SZ_32K;
> +	end = SZ_64K - 1;
> +	btrfs_drop_extent_map_range(BTRFS_I(inode), start, end, false);
> +	ret = validate_range(&BTRFS_I(inode)->extent_tree, 3);
> +	if (ret)
> +		goto out;
> +out:
> +	iput(inode);
> +	return ret;
> +}
> +
>  struct rmap_test_vector {
>  	u64 raid_type;
>  	u64 physical_start;
> @@ -619,6 +833,11 @@ int btrfs_test_extent_map(void)
>  	if (ret)
>  		goto out;
>  	ret = test_case_4(fs_info, em_tree);
> +	if (ret)
> +		goto out;
> +	ret = test_case_5();
> +	if (ret)
> +		goto out;
>  
>  	test_msg("running rmap tests");
>  	for (i = 0; i < ARRAY_SIZE(rmap_tests); i++) {
> -- 
> 2.26.3
> 

Re: [PATCH 3/4] btrfs: add a self test for btrfs_add_extent_mapping

[Filipe Manana]

On Thu, Aug 17, 2023 at 04:57:32PM -0400, Josef Bacik wrote:
> This helper is different from the normal add_extent_mapping in that it
> will stuff an em into a gap that exists between overlapping em's in the
> tree.  It appeared there was a bug so I wrote a self test to validate it
> did the correct thing when it worked with two side by side ems.
> Thankfully it is correct, but more testing is better.
> 
> Signed-off-by: Josef Bacik <josef@toxicpanda.com>

Reviewed-by: Filipe Manana <fdmanana@suse.com>

Looks good, thanks.

> ---
>  fs/btrfs/tests/extent-map-tests.c | 57 +++++++++++++++++++++++++++++++
>  1 file changed, 57 insertions(+)
> 
> diff --git a/fs/btrfs/tests/extent-map-tests.c b/fs/btrfs/tests/extent-map-tests.c
> index d5f5e48ab55c..18ab03f0d029 100644
> --- a/fs/btrfs/tests/extent-map-tests.c
> +++ b/fs/btrfs/tests/extent-map-tests.c
> @@ -656,6 +656,60 @@ static int test_case_5(void)
>  	return ret;
>  }
>  
> +/*
> + * Test the btrfs_add_extent_mapping helper which will attempt to create an em
> + * for areas between two existing ems.  Validate it doesn't do this when there
> + * are two unmerged em's side by side.
> + */
> +static int test_case_6(struct btrfs_fs_info *fs_info,
> +		       struct extent_map_tree *em_tree)
> +{
> +	struct extent_map *em = NULL;
> +	int ret;
> +
> +	ret = add_compressed_extent(em_tree, 0, SZ_4K, 0);
> +	if (ret)
> +		goto out;
> +
> +	ret = add_compressed_extent(em_tree, SZ_4K, SZ_4K, 0);
> +	if (ret)
> +		goto out;
> +
> +	em = alloc_extent_map();
> +	if (!em) {
> +		test_std_err(TEST_ALLOC_EXTENT_MAP);
> +		return -ENOMEM;
> +	}
> +
> +	em->start = SZ_4K;
> +	em->len = SZ_4K;
> +	em->block_start = SZ_16K;
> +	em->block_len = SZ_16K;
> +	write_lock(&em_tree->lock);
> +	ret = btrfs_add_extent_mapping(fs_info, em_tree, &em, 0, SZ_8K);
> +	write_unlock(&em_tree->lock);
> +
> +	if (ret != 0) {
> +		test_err("got an error when adding our em: %d", ret);
> +		goto out;
> +	}
> +
> +	ret = -EINVAL;
> +	if (em->start != 0) {
> +		test_err("unexpected em->start at %llu, wanted 0", em->start);
> +		goto out;
> +	}
> +	if (em->len != SZ_4K) {
> +		test_err("unexpected em->len %llu, expected 4K", em->len);
> +		goto out;
> +	}
> +	ret = 0;
> +out:
> +	free_extent_map(em);
> +	free_extent_map_tree(em_tree);
> +	return ret;
> +}
> +
>  struct rmap_test_vector {
>  	u64 raid_type;
>  	u64 physical_start;
> @@ -836,6 +890,9 @@ int btrfs_test_extent_map(void)
>  	if (ret)
>  		goto out;
>  	ret = test_case_5();
> +	if (ret)
> +		goto out;
> +	ret = test_case_6(fs_info, em_tree);
>  	if (ret)
>  		goto out;
>  
> -- 
> 2.26.3
> 

Re: [PATCH 4/4] btrfs: test invalid splitting when skipping pinned drop extent_map

[Filipe Manana]

On Thu, Aug 17, 2023 at 04:57:33PM -0400, Josef Bacik wrote:
> This reproduces the bug fixed by "btrfs: fix incorrect splitting in
> btrfs_drop_extent_map_range", we were improperly calculating the range
> for the split extent.  Add a test that exercises this scenario and
> validates that we get the correct resulting extent_maps in our tree.
> 
> Signed-off-by: Josef Bacik <josef@toxicpanda.com>

Reviewed-by: Filipe Manana <fdmanana@suse.com>

Looks good, just a minor comment below.

> ---
>  fs/btrfs/tests/extent-map-tests.c | 138 ++++++++++++++++++++++++++++++
>  1 file changed, 138 insertions(+)
> 
> diff --git a/fs/btrfs/tests/extent-map-tests.c b/fs/btrfs/tests/extent-map-tests.c
> index 18ab03f0d029..06820a8b4d1f 100644
> --- a/fs/btrfs/tests/extent-map-tests.c
> +++ b/fs/btrfs/tests/extent-map-tests.c
> @@ -710,6 +710,141 @@ static int test_case_6(struct btrfs_fs_info *fs_info,
>  	return ret;
>  }
>  
> +/*
> + * Regression test for btrfs_drop_extent_map_range.  Calling with skip_pinned ==
> + * true would mess up the start/end calculations and subsequent splits would be
> + * incorrect.
> + */
> +static int test_case_7(void)
> +{
> +	struct extent_map_tree *em_tree;
> +	struct extent_map *em = NULL;
> +	struct inode *inode = NULL;

These two initializations to NULL are not needed.

> +	int ret;
> +
> +	test_msg("Running btrfs_drop_extent_cache with pinned");
> +
> +	inode = btrfs_new_test_inode();
> +	if (!inode) {
> +		test_std_err(TEST_ALLOC_INODE);
> +		return -ENOMEM;
> +	}
> +
> +	em_tree = &BTRFS_I(inode)->extent_tree;
> +
> +	em = alloc_extent_map();
> +	if (!em) {
> +		test_std_err(TEST_ALLOC_EXTENT_MAP);
> +		ret = -ENOMEM;
> +		goto out;
> +	}
> +
> +	/* [0, 16K), pinned */
> +	em->start = 0;
> +	em->len = SZ_16K;
> +	em->block_start = 0;
> +	em->block_len = SZ_4K;
> +	set_bit(EXTENT_FLAG_PINNED, &em->flags);
> +	write_lock(&em_tree->lock);
> +	ret = add_extent_mapping(em_tree, em, 0);
> +	write_unlock(&em_tree->lock);
> +	if (ret < 0) {
> +		test_err("couldn't add extent map");
> +		goto out;
> +	}
> +	free_extent_map(em);
> +
> +	em = alloc_extent_map();
> +	if (!em) {
> +		test_std_err(TEST_ALLOC_EXTENT_MAP);
> +		ret = -ENOMEM;
> +		goto out;
> +	}
> +
> +	/* [32K, 48K), not pinned */
> +	em->start = SZ_32K;
> +	em->len = SZ_16K;
> +	em->block_start = SZ_32K;
> +	em->block_len = SZ_16K;
> +	write_lock(&em_tree->lock);
> +	ret = add_extent_mapping(em_tree, em, 0);
> +	write_unlock(&em_tree->lock);
> +	if (ret < 0) {
> +		test_err("couldn't add extent map");
> +		goto out;
> +	}
> +	free_extent_map(em);
> +
> +	/*
> +	 * Drop [0, 36K) This should skip the [0, 4K) extent and then split the
> +	 * [32K, 48K) extent.
> +	 */
> +	btrfs_drop_extent_map_range(BTRFS_I(inode), 0, (36 * SZ_1K) - 1, true);
> +
> +	/* Make sure our extent maps look sane. */
> +	ret = -EINVAL;
> +
> +	em = lookup_extent_mapping(em_tree, 0, SZ_16K);
> +	if (!em) {
> +		test_err("didn't find an em at 0 as expected");
> +		goto out;
> +	}
> +
> +	if (em->start != 0) {
> +		test_err("em->start is %llu, expected 0", em->start);
> +		goto out;
> +	}
> +
> +	if (em->len != SZ_16K) {
> +		test_err("em->len is %llu, expected 16K", em->len);
> +		goto out;
> +	}
> +
> +	free_extent_map(em);
> +
> +	read_lock(&em_tree->lock);
> +	em = lookup_extent_mapping(em_tree, SZ_16K, SZ_16K);
> +	read_unlock(&em_tree->lock);
> +	if (em) {
> +		test_err("found an em when we weren't expecting one");
> +		goto out;
> +	}
> +
> +	read_lock(&em_tree->lock);
> +	em = lookup_extent_mapping(em_tree, SZ_32K, SZ_16K);
> +	read_unlock(&em_tree->lock);
> +	if (!em) {
> +		test_err("didn't find an em at 32K as expected");
> +		goto out;
> +	}
> +
> +	if (em->start != (36 * SZ_1K)) {
> +		test_err("em->start is %llu, expected 36K", em->start);
> +		goto out;
> +	}
> +
> +	if (em->len != (12 * SZ_1K)) {
> +		test_err("em->len is %llu, expected 12K", em->len);
> +		goto out;
> +	}
> +
> +	free_extent_map(em);
> +
> +	read_lock(&em_tree->lock);
> +	em = lookup_extent_mapping(em_tree, 48 * SZ_1K, (u64)-1);
> +	read_unlock(&em_tree->lock);
> +	if (em) {
> +		test_err("found an unexpected em above 48K");
> +		goto out;
> +	}
> +
> +	ret = 0;
> +out:
> +	free_extent_map(em);
> +	iput(inode);
> +	return ret;
> +}
> +
>  struct rmap_test_vector {
>  	u64 raid_type;
>  	u64 physical_start;
> @@ -893,6 +1028,9 @@ int btrfs_test_extent_map(void)
>  	if (ret)
>  		goto out;
>  	ret = test_case_6(fs_info, em_tree);
> +	if (ret)
> +		goto out;
> +	ret = test_case_7();
>  	if (ret)
>  		goto out;
>  
> -- 
> 2.26.3
>