Skip to contentSkip to conversation

btrfs: rst: updates for RAID stripe tree

PATCH Superseded Johannes Thumshirn 3 participants 18 messages Jul 1, 2024 – Jul 3, 2024 Btrfs file system

v3 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

v3 cover btrfs: rst: updates for RAID stripe tree

Patch 1 replaces stripe extents in case we hit a EEXIST when inserting a stripe extent on a write. This can happen i.e. on device-replace.

Patch 2 splits a stripe extent on partial delete of a stripe.

Patch 3 adds selftests for the stripe-tree delete code, these selftests can and will be extended to cover insert and get as well.

Patch 4 fixes a deadlock between scrub and device replace when RST is used.

Patch 5 get's rid of the pointless tree dump in case we're not finding an RST entry.

Note: There still is a known bug triggering a crash on btrfs/06[01]. I'm working on it, but I've not yet root caused it.

---
Changes in v3:
- Drop on-disk format change as it's in for-next
- Add patches 4 & 5
- Link to v2: https://lore.kernel.org/r/[email protected]

Changes in v2:
- Added selftests for delete code
- Link to v1: https://lore.kernel.org/r/[email protected]

---
Johannes Thumshirn (5):
btrfs: replace stripe extents
btrfs: split RAID stripes on deletion
btrfs: stripe-tree: add selftests
btrfs: don't hold dev_replace rwsem over whole of btrfs_map_block
btrfs: rst: don't print tree dump in case lookup fails

 fs/btrfs/Makefile                       |   3 +-
 fs/btrfs/ctree.c                        |   1 +
 fs/btrfs/raid-stripe-tree.c             | 143 ++++++++++++++----
 fs/btrfs/raid-stripe-tree.h             |   5 +
 fs/btrfs/tests/btrfs-tests.c            |   3 +
 fs/btrfs/tests/btrfs-tests.h            |   1 +
 fs/btrfs/tests/raid-stripe-tree-tests.c | 258 ++++++++++++++++++++++++++++++++
 fs/btrfs/volumes.c                      |  28 ++--
 8 files changed, 401 insertions(+), 41 deletions(-)

---
base-commit: 9c681cca9c5f8e3bd5891f3944f7b9ce4d14f4ec
change-id: 20240610-b4-rst-updates-d0aa696b9d5a

Best regards,

Signature · 1 line
Johannes Thumshirn <[email protected]>
#1 lore raw

PATCH v3 1/5 btrfs: replace stripe extents

From: Johannes Thumshirn <[email protected]>

If we can't insert a stripe extent in the RAID stripe tree, because the key that points to the specific position in the stripe tree is already existing, we have to remove the item and then replace it by a new item.

This can happen for example on device replace operations.

---
 fs/btrfs/raid-stripe-tree.c | 34 ++++++++++++++++++++++++++++++++++
 1 file changed, 34 insertions(+)
fs/btrfs/raid-stripe-tree.c +34 -0
index e6f7a234b8f6..3020820dd6e2 100644
@@ -73,6 +73,37 @@ int btrfs_delete_raid_extent(struct btrfs_trans_handle *trans, u64 start, u64 le
 	return ret;
 }
 
+static int replace_raid_extent_item(struct btrfs_trans_handle *trans,
+				    struct btrfs_key *key,
+				    struct btrfs_stripe_extent *stripe_extent,
+				    const size_t item_size)
+{
+	struct btrfs_fs_info *fs_info = trans->fs_info;
+	struct btrfs_root *stripe_root = fs_info->stripe_root;
+	struct btrfs_path *path;
+	int ret;
+
+	path = btrfs_alloc_path();
+	if (!path)
+		return -ENOMEM;
+
+	ret = btrfs_search_slot(trans, stripe_root, key, path, -1, 1);
+	if (ret)
+		goto err;
+
+	ret = btrfs_del_item(trans, stripe_root, path);
+	if (ret)
+		goto err;
+
+	btrfs_free_path(path);
+
+	return btrfs_insert_item(trans, stripe_root, key, stripe_extent,
+				 item_size);
+ err:
+	btrfs_free_path(path);
+	return ret;
+}
+
 static int btrfs_insert_one_raid_extent(struct btrfs_trans_handle *trans,
 					struct btrfs_io_context *bioc)
 {
@@ -112,6 +143,9 @@ static int btrfs_insert_one_raid_extent(struct btrfs_trans_handle *trans,
 
 	ret = btrfs_insert_item(trans, stripe_root, &stripe_key, stripe_extent,
 				item_size);
+	if (ret == -EEXIST)
+		ret = replace_raid_extent_item(trans, &stripe_key,
+					       stripe_extent, item_size);
 	if (ret)
 		btrfs_abort_transaction(trans, ret);
 
Signature · 1 line
2.43.0
#2 lore raw

Re: [PATCH v3 1/5] btrfs: replace stripe extents

Quoted 29 lines · Johannes Thumshirn

From: Johannes Thumshirn <[email protected]>

If we can't insert a stripe extent in the RAID stripe tree, because the key that points to the specific position in the stripe tree is already existing, we have to remove the item and then replace it by a new item.

This can happen for example on device replace operations.

---
 fs/btrfs/raid-stripe-tree.c | 34 ++++++++++++++++++++++++++++++++++
 1 file changed, 34 insertions(+)
fs/btrfs/raid-stripe-tree.c +7 -0
index e6f7a234b8f6..3020820dd6e2 100644
@@ -73,6 +73,37 @@ int btrfs_delete_raid_extent(struct btrfs_trans_handle *trans, u64 start, u64 le
 	return ret;
 }
 
+static int replace_raid_extent_item(struct btrfs_trans_handle *trans,
+				    struct btrfs_key *key,
+				    struct btrfs_stripe_extent *stripe_extent,
+				    const size_t item_size)
+{
+	struct btrfs_fs_info *fs_info = trans->fs_info;
+	struct btrfs_root *stripe_root = fs_info->stripe_root;

fs/btrfs/raid-stripe-tree.c int btrfs_delete_raid_extent(struct btrfs_trans_handle *trans, u64 start, u64 le · line 92

Quoted 10 lines
fs/btrfs/raid-stripe-tree.c +10 -0
+	struct btrfs_path *path;
+	int ret;
+
+	path = btrfs_alloc_path();
+	if (!path)
+		return -ENOMEM;
+
+	ret = btrfs_search_slot(trans, stripe_root, key, path, -1, 1);
+	if (ret)
+		goto err;

This will leak 1 and we'll get an awkward btrfs_abort_transaction() call. This should be

if (ret) {
	ret = (ret == 1) ? -ENOENT : ret;
	goto err;
}

or whatever. Thanks,

Josef

#3 lore raw

Re: [PATCH v3 1/5] btrfs: replace stripe extents

Quoted 44 lines · Josef Bacik
Quoted 29 lines · Johannes Thumshirn

From: Johannes Thumshirn <[email protected]>

If we can't insert a stripe extent in the RAID stripe tree, because the key that points to the specific position in the stripe tree is already existing, we have to remove the item and then replace it by a new item.

This can happen for example on device replace operations.

---
  fs/btrfs/raid-stripe-tree.c | 34 ++++++++++++++++++++++++++++++++++
  1 file changed, 34 insertions(+)
fs/btrfs/raid-stripe-tree.c +7 -0
index e6f7a234b8f6..3020820dd6e2 100644
@@ -73,6 +73,37 @@ int btrfs_delete_raid_extent(struct btrfs_trans_handle *trans, u64 start, u64 le
  	return ret;
  }
 
+static int replace_raid_extent_item(struct btrfs_trans_handle *trans,
+				    struct btrfs_key *key,
+				    struct btrfs_stripe_extent *stripe_extent,
+				    const size_t item_size)
+{
+	struct btrfs_fs_info *fs_info = trans->fs_info;
+	struct btrfs_root *stripe_root = fs_info->stripe_root;

fs/btrfs/raid-stripe-tree.c int btrfs_delete_raid_extent(struct btrfs_trans_handle *trans, u64 start, u64 le · line 92

Quoted 10 lines
fs/btrfs/raid-stripe-tree.c +10 -0
+	struct btrfs_path *path;
+	int ret;
+
+	path = btrfs_alloc_path();
+	if (!path)
+		return -ENOMEM;
+
+	ret = btrfs_search_slot(trans, stripe_root, key, path, -1, 1);
+	if (ret)
+		goto err;

This will leak 1 and we'll get an awkward btrfs_abort_transaction() call. This should be

Quoted 6 lines
if (ret) {
	ret = (ret == 1) ? -ENOENT : ret;
	goto err;
}

or whatever. Thanks,

I wonder why I've never seen this in my testing. Could it be, that due to the fact that btrfs_insert_item() returns -EEXIST on the same key.objectid, we're more or less guaranteed it'll exist.

#4 lore raw

Re: [PATCH v3 1/5] btrfs: replace stripe extents

Quoted 50 lines · Johannes Thumshirn
Quoted 49 lines · Josef Bacik
Quoted 29 lines · Johannes Thumshirn

From: Johannes Thumshirn <[email protected]>

If we can't insert a stripe extent in the RAID stripe tree, because the key that points to the specific position in the stripe tree is already existing, we have to remove the item and then replace it by a new item.

This can happen for example on device replace operations.

---
  fs/btrfs/raid-stripe-tree.c | 34 ++++++++++++++++++++++++++++++++++
  1 file changed, 34 insertions(+)
fs/btrfs/raid-stripe-tree.c +7 -0
index e6f7a234b8f6..3020820dd6e2 100644
@@ -73,6 +73,37 @@ int btrfs_delete_raid_extent(struct btrfs_trans_handle *trans, u64 start, u64 le
  	return ret;
  }
 
+static int replace_raid_extent_item(struct btrfs_trans_handle *trans,
+				    struct btrfs_key *key,
+				    struct btrfs_stripe_extent *stripe_extent,
+				    const size_t item_size)
+{
+	struct btrfs_fs_info *fs_info = trans->fs_info;
+	struct btrfs_root *stripe_root = fs_info->stripe_root;

fs/btrfs/raid-stripe-tree.c int btrfs_delete_raid_extent(struct btrfs_trans_handle *trans, u64 start, u64 le · line 92

Quoted 10 lines
fs/btrfs/raid-stripe-tree.c +10 -0
+	struct btrfs_path *path;
+	int ret;
+
+	path = btrfs_alloc_path();
+	if (!path)
+		return -ENOMEM;
+
+	ret = btrfs_search_slot(trans, stripe_root, key, path, -1, 1);
+	if (ret)
+		goto err;

This will leak 1 and we'll get an awkward btrfs_abort_transaction() call. This should be

if (ret) {
	ret = (ret == 1) ? -ENOENT : ret;
	goto err;
}
Quoted 5 lines
Quoted 1 line

or whatever. Thanks,

I wonder why I've never seen this in my testing. Could it be, that due to the fact that btrfs_insert_item() returns -EEXIST on the same key.objectid, we're more or less guaranteed it'll exist.

Yeah it's fine in the way it is currently, but if anything changes in the future we're going to figure it out and be super sad we didn't just handle it right in the first place. Thanks,

Josef

#5 lore raw

Re: [PATCH v3 1/5] btrfs: replace stripe extents

In reply to Johannes Thumshirn
Quoted 57 lines · Johannes Thumshirn

From: Johannes Thumshirn <[email protected]>

If we can't insert a stripe extent in the RAID stripe tree, because the key that points to the specific position in the stripe tree is already existing, we have to remove the item and then replace it by a new item.

This can happen for example on device replace operations.

---
 fs/btrfs/raid-stripe-tree.c | 34 ++++++++++++++++++++++++++++++++++
 1 file changed, 34 insertions(+)
fs/btrfs/raid-stripe-tree.c +31 -0
index e6f7a234b8f6..3020820dd6e2 100644
@@ -73,6 +73,37 @@ int btrfs_delete_raid_extent(struct btrfs_trans_handle *trans, u64 start, u64 le
 	return ret;
 }
 
+static int replace_raid_extent_item(struct btrfs_trans_handle *trans,
+				    struct btrfs_key *key,
+				    struct btrfs_stripe_extent *stripe_extent,
+				    const size_t item_size)
+{
+	struct btrfs_fs_info *fs_info = trans->fs_info;
+	struct btrfs_root *stripe_root = fs_info->stripe_root;
+	struct btrfs_path *path;
+	int ret;
+
+	path = btrfs_alloc_path();
+	if (!path)
+		return -ENOMEM;
+
+	ret = btrfs_search_slot(trans, stripe_root, key, path, -1, 1);
+	if (ret)
+		goto err;
+
+	ret = btrfs_del_item(trans, stripe_root, path);
+	if (ret)
+		goto err;
+
+	btrfs_free_path(path);
+
+	return btrfs_insert_item(trans, stripe_root, key, stripe_extent,
+				 item_size);
+ err:
+	btrfs_free_path(path);
+	return ret;
+}
+
 static int btrfs_insert_one_raid_extent(struct btrfs_trans_handle *trans,
 					struct btrfs_io_context *bioc)
 {

fs/btrfs/raid-stripe-tree.c static int btrfs_insert_one_raid_extent(struct btrfs_trans_handle *trans, · line 148

Quoted 6 lines
fs/btrfs/raid-stripe-tree.c +3 -0
@@ -112,6 +143,9 @@ static int btrfs_insert_one_raid_extent(struct btrfs_trans_handle *trans,
 
 	ret = btrfs_insert_item(trans, stripe_root, &stripe_key, stripe_extent,
 				item_size);
+	if (ret == -EEXIST)
+		ret = replace_raid_extent_item(trans, &stripe_key,
+					       stripe_extent, item_size);

I had another thought, how often is this particular thing happening? Bec ause we're doing 3 path allocations here in the worst case. If it happens more than say 10% of the time then we need to allocate a path once in btrfs_insert_one_raid_extent(), do the insert, and if it fails re-use that path to do the delete and insert the new one. Thanks,

Josef

#6 lore raw

Re: [PATCH v3 1/5] btrfs: replace stripe extents

Quoted 9 lines · Josef Bacik

fs/btrfs/raid-stripe-tree.c static int btrfs_insert_one_raid_extent(struct btrfs_trans_handle *trans, · line 148

Quoted 3 lines
fs/btrfs/raid-stripe-tree.c +3 -0
+	if (ret == -EEXIST)
+		ret = replace_raid_extent_item(trans, &stripe_key,
+					       stripe_extent, item_size);

I had another thought, how often is this particular thing happening? Bec ause we're doing 3 path allocations here in the worst case. If it happens more than say 10% of the time then we need to allocate a path once in btrfs_insert_one_raid_extent(), do the insert, and if it fails re-use that path to do the delete and insert the new one. Thanks,

That indeed is a good question. I'll add some tracepoints to see how often this is getting called.

#7 lore raw

PATCH v3 2/5 btrfs: split RAID stripes on deletion

In reply to Johannes Thumshirn

From: Johannes Thumshirn <[email protected]>

The current RAID stripe code assumes, that we will always remove a whole stripe entry.

But if we're only removing a part of a RAID stripe we're hitting the ASSERT()ion checking for this condition.

Instead of assuming the complete deletion of a RAID stripe, split the stripe if we need to.

---
 fs/btrfs/ctree.c            |   1 +
 fs/btrfs/raid-stripe-tree.c | 100 +++++++++++++++++++++++++++++++++-----------
 2 files changed, 77 insertions(+), 24 deletions(-)
fs/btrfs/ctree.c +1 -0
index e33f9f5a228d..16f9cf6360a4 100644
@@ -3863,6 +3863,7 @@ static noinline int setup_leaf_for_split(struct btrfs_trans_handle *trans,
 	btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 
 	BUG_ON(key.type != BTRFS_EXTENT_DATA_KEY &&
+	       key.type != BTRFS_RAID_STRIPE_KEY &&
 	       key.type != BTRFS_EXTENT_CSUM_KEY);
 
 	if (btrfs_leaf_free_space(leaf) >= ins_len)
fs/btrfs/raid-stripe-tree.c +76 -24

118 lines not on this page · raw message

Signature · 1 line
2.43.0
#8 lore raw

Re: [PATCH v3 2/5] btrfs: split RAID stripes on deletion

Quoted 126 lines · Johannes Thumshirn

From: Johannes Thumshirn <[email protected]>

The current RAID stripe code assumes, that we will always remove a whole stripe entry.

But if we're only removing a part of a RAID stripe we're hitting the ASSERT()ion checking for this condition.

Instead of assuming the complete deletion of a RAID stripe, split the stripe if we need to.

---
 fs/btrfs/ctree.c            |   1 +
 fs/btrfs/raid-stripe-tree.c | 100 +++++++++++++++++++++++++++++++++-----------
 2 files changed, 77 insertions(+), 24 deletions(-)
fs/btrfs/ctree.c +1 -0
index e33f9f5a228d..16f9cf6360a4 100644
@@ -3863,6 +3863,7 @@ static noinline int setup_leaf_for_split(struct btrfs_trans_handle *trans,
 	btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 
 	BUG_ON(key.type != BTRFS_EXTENT_DATA_KEY &&
+	       key.type != BTRFS_RAID_STRIPE_KEY &&
 	       key.type != BTRFS_EXTENT_CSUM_KEY);
 
 	if (btrfs_leaf_free_space(leaf) >= ins_len)
fs/btrfs/raid-stripe-tree.c +64 -19
index 3020820dd6e2..64e36b46cbab 100644
@@ -33,42 +33,94 @@ int btrfs_delete_raid_extent(struct btrfs_trans_handle *trans, u64 start, u64 le
 	if (!path)
 		return -ENOMEM;
 
-	while (1) {
-		key.objectid = start;
-		key.type = BTRFS_RAID_STRIPE_KEY;
-		key.offset = length;
+again:
+	key.objectid = start;
+	key.type = BTRFS_RAID_STRIPE_KEY;
+	key.offset = length;
 
-		ret = btrfs_search_slot(trans, stripe_root, &key, path, -1, 1);
-		if (ret < 0)
-			break;
-		if (ret > 0) {
-			ret = 0;
-			if (path->slots[0] == 0)
-				break;
-			path->slots[0]--;
-		}
+	ret = btrfs_search_slot(trans, stripe_root, &key, path, -1, 1);
+	if (ret < 0)
+		goto out;
+	if (ret > 0) {
+		ret = 0;
+		if (path->slots[0] == 0)
+			goto out;
+		path->slots[0]--;
+	}
+
+	leaf = path->nodes[0];
+	slot = path->slots[0];
+	btrfs_item_key_to_cpu(leaf, &key, slot);
+	found_start = key.objectid;
+	found_end = found_start + key.offset;
+
+	/* That stripe ends before we start, we're done. */
+	if (found_end <= start)
+		goto out;
+
+	trace_btrfs_raid_extent_delete(fs_info, start, end,
+				       found_start, found_end);
+
+	if (found_start < start) {
+		u64 diff = start - found_start;
+		struct btrfs_key new_key;
+		int num_stripes;
+		struct btrfs_stripe_extent *stripe_extent;
+
+		new_key.objectid = start;
+		new_key.type = BTRFS_RAID_STRIPE_KEY;
+		new_key.offset = length - diff;
+
+		ret = btrfs_duplicate_item(trans, stripe_root, path,
+					   &new_key);
+		if (ret)
+			goto out;
 
 		leaf = path->nodes[0];
 		slot = path->slots[0];
-		btrfs_item_key_to_cpu(leaf, &key, slot);
-		found_start = key.objectid;
-		found_end = found_start + key.offset;
 
-		/* That stripe ends before we start, we're done. */
-		if (found_end <= start)
-			break;
+		num_stripes =
+			btrfs_num_raid_stripes(btrfs_item_size(leaf, slot));
+		stripe_extent =
+			btrfs_item_ptr(leaf, slot, struct btrfs_stripe_extent);
+
+		for (int i = 0; i < num_stripes; i++) {
+			struct btrfs_raid_stride *raid_stride =
+				&stripe_extent->strides[i];
+			u64 physical =
+				btrfs_raid_stride_physical(leaf, raid_stride);
+
+			btrfs_set_raid_stride_physical(leaf, raid_stride,
+							     physical + diff);
+		}
+
+		btrfs_mark_buffer_dirty(trans, leaf);
+		btrfs_release_path(path);
+		goto again;
+	}
+
+	if (found_end > end) {
+		u64 diff = found_end - end;
+		struct btrfs_key new_key;
 

fs/btrfs/raid-stripe-tree.c int btrfs_delete_raid_extent(struct btrfs_trans_handle *trans, u64 start, u64 le · line 111

Quoted 10 lines
fs/btrfs/raid-stripe-tree.c +5 -4
-		trace_btrfs_raid_extent_delete(fs_info, start, end,
-					       found_start, found_end);
+		new_key.objectid = found_start;
+		new_key.type = BTRFS_RAID_STRIPE_KEY;
+		new_key.offset = length - diff;
 
-		ASSERT(found_start >= start && found_end <= end);
-		ret = btrfs_del_item(trans, stripe_root, path);
+		ret = btrfs_duplicate_item(trans, stripe_root, path,
+					   &new_key);

This seems incorrect to me. If we have [0, 1MiB) and we're deleting [0,512KiB) then the tree at this point is

[0, BTRFS_RAID_STRIPE_KEY, 512KiB]
[0, BTRFS_RAID_STRIPE_KEY, 1MiB]

which is valid as far as key ordering goes, but is a violation of the raid stripe tree design correct? And then you do goto again, and then you'll delete

[0, BTRFS_RAID_STRIPE_KEY, 512KiB]

but leave the old one in place, correct? Thanks,

Josef

#9 lore raw

Re: [PATCH v3 2/5] btrfs: split RAID stripes on deletion

Quoted 144 lines · Josef Bacik
Quoted 126 lines · Johannes Thumshirn

From: Johannes Thumshirn <[email protected]>

The current RAID stripe code assumes, that we will always remove a whole stripe entry.

But if we're only removing a part of a RAID stripe we're hitting the ASSERT()ion checking for this condition.

Instead of assuming the complete deletion of a RAID stripe, split the stripe if we need to.

---
  fs/btrfs/ctree.c            |   1 +
  fs/btrfs/raid-stripe-tree.c | 100 +++++++++++++++++++++++++++++++++-----------
  2 files changed, 77 insertions(+), 24 deletions(-)
fs/btrfs/ctree.c +1 -0
index e33f9f5a228d..16f9cf6360a4 100644
@@ -3863,6 +3863,7 @@ static noinline int setup_leaf_for_split(struct btrfs_trans_handle *trans,
  	btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 
  	BUG_ON(key.type != BTRFS_EXTENT_DATA_KEY &&
+	       key.type != BTRFS_RAID_STRIPE_KEY &&
  	       key.type != BTRFS_EXTENT_CSUM_KEY);
 
  	if (btrfs_leaf_free_space(leaf) >= ins_len)
fs/btrfs/raid-stripe-tree.c +64 -19
index 3020820dd6e2..64e36b46cbab 100644
@@ -33,42 +33,94 @@ int btrfs_delete_raid_extent(struct btrfs_trans_handle *trans, u64 start, u64 le
  	if (!path)
  		return -ENOMEM;
 
-	while (1) {
-		key.objectid = start;
-		key.type = BTRFS_RAID_STRIPE_KEY;
-		key.offset = length;
+again:
+	key.objectid = start;
+	key.type = BTRFS_RAID_STRIPE_KEY;
+	key.offset = length;
 
-		ret = btrfs_search_slot(trans, stripe_root, &key, path, -1, 1);
-		if (ret < 0)
-			break;
-		if (ret > 0) {
-			ret = 0;
-			if (path->slots[0] == 0)
-				break;
-			path->slots[0]--;
-		}
+	ret = btrfs_search_slot(trans, stripe_root, &key, path, -1, 1);
+	if (ret < 0)
+		goto out;
+	if (ret > 0) {
+		ret = 0;
+		if (path->slots[0] == 0)
+			goto out;
+		path->slots[0]--;
+	}
+
+	leaf = path->nodes[0];
+	slot = path->slots[0];
+	btrfs_item_key_to_cpu(leaf, &key, slot);
+	found_start = key.objectid;
+	found_end = found_start + key.offset;
+
+	/* That stripe ends before we start, we're done. */
+	if (found_end <= start)
+		goto out;
+
+	trace_btrfs_raid_extent_delete(fs_info, start, end,
+				       found_start, found_end);
+
+	if (found_start < start) {
+		u64 diff = start - found_start;
+		struct btrfs_key new_key;
+		int num_stripes;
+		struct btrfs_stripe_extent *stripe_extent;
+
+		new_key.objectid = start;
+		new_key.type = BTRFS_RAID_STRIPE_KEY;
+		new_key.offset = length - diff;
+
+		ret = btrfs_duplicate_item(trans, stripe_root, path,
+					   &new_key);
+		if (ret)
+			goto out;
 
  		leaf = path->nodes[0];
  		slot = path->slots[0];
-		btrfs_item_key_to_cpu(leaf, &key, slot);
-		found_start = key.objectid;
-		found_end = found_start + key.offset;
 
-		/* That stripe ends before we start, we're done. */
-		if (found_end <= start)
-			break;
+		num_stripes =
+			btrfs_num_raid_stripes(btrfs_item_size(leaf, slot));
+		stripe_extent =
+			btrfs_item_ptr(leaf, slot, struct btrfs_stripe_extent);
+
+		for (int i = 0; i < num_stripes; i++) {
+			struct btrfs_raid_stride *raid_stride =
+				&stripe_extent->strides[i];
+			u64 physical =
+				btrfs_raid_stride_physical(leaf, raid_stride);
+
+			btrfs_set_raid_stride_physical(leaf, raid_stride,
+							     physical + diff);
+		}
+
+		btrfs_mark_buffer_dirty(trans, leaf);
+		btrfs_release_path(path);
+		goto again;
+	}
+
+	if (found_end > end) {
+		u64 diff = found_end - end;
+		struct btrfs_key new_key;
 

fs/btrfs/raid-stripe-tree.c int btrfs_delete_raid_extent(struct btrfs_trans_handle *trans, u64 start, u64 le · line 111

Quoted 10 lines
fs/btrfs/raid-stripe-tree.c +5 -4
-		trace_btrfs_raid_extent_delete(fs_info, start, end,
-					       found_start, found_end);
+		new_key.objectid = found_start;
+		new_key.type = BTRFS_RAID_STRIPE_KEY;
+		new_key.offset = length - diff;
 
-		ASSERT(found_start >= start && found_end <= end);
-		ret = btrfs_del_item(trans, stripe_root, path);
+		ret = btrfs_duplicate_item(trans, stripe_root, path,
+					   &new_key);

This seems incorrect to me. If we have [0, 1MiB) and we're deleting [0,512KiB) then the tree at this point is

[0, BTRFS_RAID_STRIPE_KEY, 512KiB]
[0, BTRFS_RAID_STRIPE_KEY, 1MiB]

Quoted 6 lines

which is valid as far as key ordering goes, but is a violation of the raid stripe tree design correct? And then you do goto again, and then you'll delete

[0, BTRFS_RAID_STRIPE_KEY, 512KiB]

but leave the old one in place, correct? Thanks,

Oh right, jumping back to again removes the wrong one :/

#10 lore raw

PATCH v3 3/5 btrfs: stripe-tree: add selftests

In reply to Johannes Thumshirn

From: Johannes Thumshirn <[email protected]>

Add self-tests for the RAID stripe tree code.

---
 fs/btrfs/Makefile                       |   3 +-
 fs/btrfs/raid-stripe-tree.c             |   3 +-
 fs/btrfs/raid-stripe-tree.h             |   5 +
 fs/btrfs/tests/btrfs-tests.c            |   3 +
 fs/btrfs/tests/btrfs-tests.h            |   1 +
 fs/btrfs/tests/raid-stripe-tree-tests.c | 258 ++++++++++++++++++++++++++++++++
 6 files changed, 271 insertions(+), 2 deletions(-)
fs/btrfs/Makefile +2 -1
index 87617f2968bc..3cfc440c636c 100644
@@ -43,4 +43,5 @@ btrfs-$(CONFIG_FS_VERITY) += verity.o
 btrfs-$(CONFIG_BTRFS_FS_RUN_SANITY_TESTS) += tests/free-space-tests.o \
 	tests/extent-buffer-tests.o tests/btrfs-tests.o \
 	tests/extent-io-tests.o tests/inode-tests.o tests/qgroup-tests.o \
-	tests/free-space-tree-tests.o tests/extent-map-tests.o
+	tests/free-space-tree-tests.o tests/extent-map-tests.o \
+	tests/raid-stripe-tree-tests.o
fs/btrfs/raid-stripe-tree.c +2 -1
index 64e36b46cbab..c5c2f19387ff 100644
@@ -156,7 +156,8 @@ static int replace_raid_extent_item(struct btrfs_trans_handle *trans,
 	return ret;
 }
 
-static int btrfs_insert_one_raid_extent(struct btrfs_trans_handle *trans,
+EXPORT_FOR_TESTS
+int btrfs_insert_one_raid_extent(struct btrfs_trans_handle *trans,
 					struct btrfs_io_context *bioc)
 {
 	struct btrfs_fs_info *fs_info = trans->fs_info;
fs/btrfs/raid-stripe-tree.h +5 -0
index 1ac1c21aac2f..541836421778 100644
@@ -28,6 +28,11 @@ int btrfs_get_raid_extent_offset(struct btrfs_fs_info *fs_info,
 int btrfs_insert_raid_extent(struct btrfs_trans_handle *trans,
 			     struct btrfs_ordered_extent *ordered_extent);
 
+#ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
+int btrfs_insert_one_raid_extent(struct btrfs_trans_handle *trans,
+				 struct btrfs_io_context *bioc);
+#endif
+
 static inline bool btrfs_need_stripe_tree_update(struct btrfs_fs_info *fs_info,
 						 u64 map_type)
 {
fs/btrfs/tests/btrfs-tests.c +3 -0
index ce50847e1e01..18e1ab4a0914 100644
@@ -291,6 +291,9 @@ int btrfs_run_sanity_tests(void)
 			ret = btrfs_test_free_space_tree(sectorsize, nodesize);
 			if (ret)
 				goto out;
+			ret = btrfs_test_raid_stripe_tree(sectorsize, nodesize);
+			if (ret)
+				goto out;
 		}
 	}
 	ret = btrfs_test_extent_map();
fs/btrfs/tests/btrfs-tests.h +1 -0
index dc2f2ab15fa5..61bcadaf2036 100644
@@ -37,6 +37,7 @@ int btrfs_test_extent_io(u32 sectorsize, u32 nodesize);
 int btrfs_test_inodes(u32 sectorsize, u32 nodesize);
 int btrfs_test_qgroups(u32 sectorsize, u32 nodesize);
 int btrfs_test_free_space_tree(u32 sectorsize, u32 nodesize);
+int btrfs_test_raid_stripe_tree(u32 sectorsize, u32 nodesize);
 int btrfs_test_extent_map(void);
 struct inode *btrfs_new_test_inode(void);
 struct btrfs_fs_info *btrfs_alloc_dummy_fs_info(u32 nodesize, u32 sectorsize);
fs/btrfs/tests/raid-stripe-tree-tests.c new file +258 -0

258 lines not on this page · raw message

Signature · 1 line
2.43.0
#11 lore raw

Re: [PATCH v3 3/5] btrfs: stripe-tree: add selftests

Quoted 5 lines · Johannes Thumshirn

From: Johannes Thumshirn <[email protected]>

Add self-tests for the RAID stripe tree code.

These tests run the code, but don't validate that the end result is what we expect, that should be added. Thanks,

Josef

#12 lore raw

Re: [PATCH v3 3/5] btrfs: stripe-tree: add selftests

Quoted 9 lines · Josef Bacik
Quoted 5 lines · Johannes Thumshirn

From: Johannes Thumshirn <[email protected]>

Add self-tests for the RAID stripe tree code.

These tests run the code, but don't validate that the end result is what we expect, that should be added. Thanks,

Right, and with the patch that doesn't pollute the console when a RST search returns -ENOENT we can actually do this correctly.

#13 lore raw

PATCH v3 4/5 btrfs: don't hold dev_replace rwsem over whole of btrfs_map_block

In reply to Johannes Thumshirn

From: Johannes Thumshirn <[email protected]>

Don't hold the dev_replace rwsem for the entirety of btrfs_map_block().

It is only needed to protect
a) calls to find_live_mirror() and
b) calling into handle_ops_on_dev_replace().

But there is no need to hold the rwsem for any kind of set_io_stripe() calls.

So relax taking the dev_replace rwsem to only protect both cases and check if the device replace status has changed in the meantime, for which we have to re-do the find_live_mirror() calls.

This fixes a deadlock on raid-stripe-tree where device replace performs a scrub operation, which in turn calls into btrfs_map_block() to find the physical location of the block.

---
 fs/btrfs/volumes.c | 28 +++++++++++++++++-----------
 1 file changed, 17 insertions(+), 11 deletions(-)
fs/btrfs/volumes.c +17 -11
index fcedc43ef291..4209419244a1 100644
@@ -6650,14 +6650,9 @@ int btrfs_map_block(struct btrfs_fs_info *fs_info, enum btrfs_map_op op,
 	max_len = btrfs_max_io_len(map, map_offset, &io_geom);
 	*length = min_t(u64, map->chunk_len - map_offset, max_len);
 
+again:
 	down_read(&dev_replace->rwsem);
 	dev_replace_is_ongoing = btrfs_dev_replace_is_ongoing(dev_replace);
-	/*
-	 * Hold the semaphore for read during the whole operation, write is
-	 * requested at commit time but must wait.
-	 */
-	if (!dev_replace_is_ongoing)
-		up_read(&dev_replace->rwsem);
 
 	switch (map->type & BTRFS_BLOCK_GROUP_PROFILE_MASK) {
 	case BTRFS_BLOCK_GROUP_RAID0:
@@ -6695,6 +6690,7 @@ int btrfs_map_block(struct btrfs_fs_info *fs_info, enum btrfs_map_op op,
 			   "stripe index math went horribly wrong, got stripe_index=%u, num_stripes=%u",
 			   io_geom.stripe_index, map->num_stripes);
 		ret = -EINVAL;
+		up_read(&dev_replace->rwsem);
 		goto out;
 	}
 
@@ -6710,6 +6706,8 @@ int btrfs_map_block(struct btrfs_fs_info *fs_info, enum btrfs_map_op op,
 		 */
 		num_alloc_stripes += 2;
 
+	up_read(&dev_replace->rwsem);
+
 	/*
 	 * If this I/O maps to a single device, try to return the device and
 	 * physical block information on the stack instead of allocating an
@@ -6782,6 +6780,18 @@ int btrfs_map_block(struct btrfs_fs_info *fs_info, enum btrfs_map_op op,
 		goto out;
 	}
 
+	/*
+	 * Check if something changed the dev_replace state since
+	 * we've checked it for the last time and if redo the whole
+	 * mapping operation.
+	 */
+	down_read(&dev_replace->rwsem);
+	if (dev_replace_is_ongoing !=
+	    btrfs_dev_replace_is_ongoing(dev_replace)) {
+		up_read(&dev_replace->rwsem);
+		goto again;
+	}
+
 	if (op != BTRFS_MAP_READ)
 		io_geom.max_errors = btrfs_chunk_max_errors(map);
 
@@ -6789,6 +6799,7 @@ int btrfs_map_block(struct btrfs_fs_info *fs_info, enum btrfs_map_op op,
 	    op != BTRFS_MAP_READ) {
 		handle_ops_on_dev_replace(bioc, dev_replace, logical, &io_geom);
 	}
+	up_read(&dev_replace->rwsem);
 
 	*bioc_ret = bioc;
 	bioc->num_stripes = io_geom.num_stripes;
@@ -6796,11 +6807,6 @@ int btrfs_map_block(struct btrfs_fs_info *fs_info, enum btrfs_map_op op,
 	bioc->mirror_num = io_geom.mirror_num;
 
 out:
-	if (dev_replace_is_ongoing) {
-		lockdep_assert_held(&dev_replace->rwsem);
-		/* Unlock and let waiting writers proceed */
-		up_read(&dev_replace->rwsem);
-	}
 	btrfs_free_chunk_map(map);
 	return ret;
 }
Signature · 1 line
2.43.0
Reviewed-by on v3 4/5
#14 lore raw

Re: [PATCH v3 4/5] btrfs: don't hold dev_replace rwsem over whole of btrfs_map_block

Quoted 15 lines · Johannes Thumshirn

From: Johannes Thumshirn <[email protected]>

Don't hold the dev_replace rwsem for the entirety of btrfs_map_block().

It is only needed to protect
a) calls to find_live_mirror() and
b) calling into handle_ops_on_dev_replace().

But there is no need to hold the rwsem for any kind of set_io_stripe() calls.

So relax taking the dev_replace rwsem to only protect both cases and check if the device replace status has changed in the meantime, for which we have to re-do the find_live_mirror() calls.

Quoted 5 lines

This fixes a deadlock on raid-stripe-tree where device replace performs a scrub operation, which in turn calls into btrfs_map_block() to find the physical location of the block.

Thanks,

Josef

#15 lore raw

PATCH v3 5/5 btrfs: rst: don't print tree dump in case lookup fails

In reply to Johannes Thumshirn

From: Johannes Thumshirn <[email protected]>

Don't print tree dump in case a raid-stripe-tree lookup fails.

Dumping the stripe tree in case of a lookup failure was originally intended to be a debug feature, but it turned out to be a problem, in case of i.e. readahead.

---
 fs/btrfs/raid-stripe-tree.c | 6 ++----
 1 file changed, 2 insertions(+), 4 deletions(-)
fs/btrfs/raid-stripe-tree.c +2 -4
index c5c2f19387ff..20be7d0c52e6 100644
@@ -332,10 +332,8 @@ int btrfs_get_raid_extent_offset(struct btrfs_fs_info *fs_info,
 out:
 	if (ret > 0)
 		ret = -ENOENT;
-	if (ret && ret != -EIO && !stripe->is_scrub) {
-		if (IS_ENABLED(CONFIG_BTRFS_DEBUG))
-			btrfs_print_tree(leaf, 1);
-		btrfs_err(fs_info,
+	if (ret && ret != -EIO) {
+		btrfs_debug(fs_info,
 		"cannot find raid-stripe for logical [%llu, %llu] devid %llu, profile %s",
 			  logical, logical + *length, stripe->dev->devid,
 			  btrfs_bg_type_to_raid_name(map_type));
Signature · 1 line
2.43.0
#16 lore raw

Re: [PATCH v3 5/5] btrfs: rst: don't print tree dump in case lookup fails

Quoted 8 lines · Johannes Thumshirn

From: Johannes Thumshirn <[email protected]>

Don't print tree dump in case a raid-stripe-tree lookup fails.

Dumping the stripe tree in case of a lookup failure was originally intended to be a debug feature, but it turned out to be a problem, in case of i.e. readahead.

I have no objection to the change but I'm curious how readahead triggered this? Is there a problem here, or is it just when there is a problem readahead makes it particularly noisy? Thanks,

Josef

#17 lore raw

Re: [PATCH v3 5/5] btrfs: rst: don't print tree dump in case lookup fails

Quoted 5 lines · Josef Bacik
Quoted 4 lines · Johannes Thumshirn

From: Johannes Thumshirn <[email protected]>

Don't print tree dump in case a raid-stripe-tree lookup fails.

Quoted 8 lines
Quoted 4 lines

Dumping the stripe tree in case of a lookup failure was originally intended to be a debug feature, but it turned out to be a problem, in case of i.e. readahead.

I have no objection to the change but I'm curious how readahead triggered this? Is there a problem here, or is it just when there is a problem readahead makes it particularly noisy? Thanks,

There still is a bug in conjunction with RST and relocation's readahead. But as I've stated in the cover letter, it is know, trivial to trigger, but I haven't fully root caused it yet.

All I can say is, that we're doing a use-after-free triggered by:

relocate_data_extent()
`-> relocate_file_extent_cluster()
`-> relocate_one_folio()
`-> page_cache_sync_readahead()

    `-> read_pages()

This most likely comes due to readahead requesting a l2p mapping that RST is unaware of, then splits the read bio (that I can see in my debugging) and the endio handler frees the original bio because of an error while the lower layer block driver still uses it.