Skip to contentSkip to conversation

btrfs: tree-checker: enhanced fst extent/bitmap checks

PATCH In review Qu Wenruo 2 participants 5 messages May 11 – May 15 Btrfs file system

lore
Share & tools
lore

Qu Wenruo

author
#0 lore raw

cover btrfs: tree-checker: enhanced fst extent/bitmap checks

The first patch is a small cleanup to share more code and remove duplications.

The second one is to avoid u64 overflow for the extent/bitmap/space info, mostly to catch obviously corruptedd size.

The last one is the main part, introducing cross-key checks.

If the previous key is FREE_SPACE_INFO, make sure the current key is inside the bg range, and matches the type the free space info is using.

If the previous key is FREE_SPACE_EXTENT/BITMAP, make sure the current key doesn't overlap with the previous one, and type matches the previous one. This will allow tree-checker to catch most (but not all) bad key type flipping.

Qu Wenruo (3):
btrfs: tree-checker: extract the shared key check for free space
entries
btrfs: tree-checker: ensure free space tree entries won't overflow
btrfs: tree-checker: add more cross checks for free space tree

 fs/btrfs/tree-checker.c | 119 +++++++++++++++++++++++++++++++---------
 1 file changed, 93 insertions(+), 26 deletions(-)
Signature · 1 line
2.54.0
author
#2 lore raw

PATCH 2/3 btrfs: tree-checker: ensure free space tree entries won't overflow

Add an extra check to ensure the free space extent/bitmap and space info keys won't overflow.

---
 fs/btrfs/tree-checker.c | 14 ++++++++++++++
 1 file changed, 14 insertions(+)
fs/btrfs/tree-checker.c +14 -0
index 4d6dde876c6d..ca9bb695f826 100644
@@ -2071,6 +2071,7 @@ static int check_free_space_info(struct extent_buffer *leaf, struct btrfs_key *k
 	struct btrfs_fs_info *fs_info = leaf->fs_info;
 	struct btrfs_free_space_info *fsi;
 	const u32 blocksize = fs_info->sectorsize;
+	u64 end;
 	u32 flags;
 
 	if (unlikely(!IS_ALIGNED(key->objectid, blocksize))) {
@@ -2085,6 +2086,12 @@ static int check_free_space_info(struct extent_buffer *leaf, struct btrfs_key *k
 			    blocksize, BTRFS_KEY_FMT_VALUE(key));
 		return -EUCLEAN;
 	}
+	if (unlikely(check_add_overflow(key->objectid, key->offset, &end))) {
+		generic_err(leaf, slot,
+			    "free space info key overflows, has " BTRFS_KEY_FMT,
+			    BTRFS_KEY_FMT_VALUE(key));
+		return -EUCLEAN;
+	}
 	if (unlikely(btrfs_item_size(leaf, slot) !=
 		     sizeof(struct btrfs_free_space_info))) {
 		generic_err(leaf, slot,
@@ -2117,6 +2124,7 @@ static int check_free_space_common_key(struct extent_buffer *leaf, struct btrfs_
 	struct btrfs_fs_info *fs_info = leaf->fs_info;
 	const u32 blocksize = fs_info->sectorsize;
 	const char *type_str = (key->type == BTRFS_FREE_SPACE_EXTENT_KEY) ? "extent" : "bitmap";
+	u64 end;
 
 	if (unlikely(!IS_ALIGNED(key->objectid, blocksize))) {
 		generic_err(leaf, slot,
@@ -2134,6 +2142,12 @@ static int check_free_space_common_key(struct extent_buffer *leaf, struct btrfs_
 		generic_err(leaf, slot, "free space %s length is 0", type_str);
 		return -EUCLEAN;
 	}
+	if (unlikely(check_add_overflow(key->objectid, key->offset, &end))) {
+		generic_err(leaf, slot,
+			    "free space %s end overflow, have objectid %llu offset %llu",
+			    type_str, key->objectid, key->offset);
+		return -EUCLEAN;
+	}
 	return 0;
 }
 
Signature · 1 line
2.54.0
author
#1 lore raw

PATCH 1/3 btrfs: tree-checker: extract the shared key check for free space entries

In reply to Qu Wenruo

Currently both check_free_space_extent() and check_free_space_bitmap() share a very common validation on the keys.

Extract them into a helper, check_free_space_common_key(), and change the output string ("extent" or "bitmap") depending on the key type.

---
 fs/btrfs/tree-checker.c | 46 ++++++++++++++++++++---------------------
 1 file changed, 23 insertions(+), 23 deletions(-)
fs/btrfs/tree-checker.c +23 -23
index ec24ffb6641d..4d6dde876c6d 100644
@@ -2112,27 +2112,39 @@ static int check_free_space_info(struct extent_buffer *leaf, struct btrfs_key *k
 	return 0;
 }
 
-static int check_free_space_extent(struct extent_buffer *leaf, struct btrfs_key *key, int slot)
+static int check_free_space_common_key(struct extent_buffer *leaf, struct btrfs_key *key, int slot)
 {
 	struct btrfs_fs_info *fs_info = leaf->fs_info;
 	const u32 blocksize = fs_info->sectorsize;
+	const char *type_str = (key->type == BTRFS_FREE_SPACE_EXTENT_KEY) ? "extent" : "bitmap";
 
 	if (unlikely(!IS_ALIGNED(key->objectid, blocksize))) {
 		generic_err(leaf, slot,
-		"free space extent key objectid is not aligned to %u, has " BTRFS_KEY_FMT,
-			    blocksize, BTRFS_KEY_FMT_VALUE(key));
+		"free space %s key objectid is not aligned to %u, has " BTRFS_KEY_FMT,
+			    type_str, blocksize, BTRFS_KEY_FMT_VALUE(key));
 		return -EUCLEAN;
 	}
 	if (unlikely(!IS_ALIGNED(key->offset, blocksize))) {
 		generic_err(leaf, slot,
-		"free space extent key offset is not aligned to %u, has " BTRFS_KEY_FMT,
-			    blocksize, BTRFS_KEY_FMT_VALUE(key));
+		"free space %s key offset is not aligned to %u, has " BTRFS_KEY_FMT,
+			    type_str, blocksize, BTRFS_KEY_FMT_VALUE(key));
 		return -EUCLEAN;
 	}
 	if (unlikely(key->offset == 0)) {
-		generic_err(leaf, slot, "free space extent length is 0");
+		generic_err(leaf, slot, "free space %s length is 0", type_str);
 		return -EUCLEAN;
 	}
+	return 0;
+}
+
+static int check_free_space_extent(struct extent_buffer *leaf, struct btrfs_key *key, int slot)
+{
+	int ret;
+
+	ret = check_free_space_common_key(leaf, key, slot);
+	if (unlikely(ret < 0))
+		return ret;
+
 	if (unlikely(btrfs_item_size(leaf, slot) != 0)) {
 		generic_err(leaf, slot,
 			    "invalid item size for free space info, has %u expect 0",
@@ -2146,25 +2158,13 @@ static int check_free_space_bitmap(struct extent_buffer *leaf,
 				   struct btrfs_key *key, int slot)
 {
 	struct btrfs_fs_info *fs_info = leaf->fs_info;
-	const u32 blocksize = fs_info->sectorsize;
 	u32 expected_item_size;
+	int ret;
+
+	ret = check_free_space_common_key(leaf, key, slot);
+	if (unlikely(ret < 0))
+		return ret;
 
-	if (unlikely(!IS_ALIGNED(key->objectid, blocksize))) {
-		generic_err(leaf, slot,
-		"free space bitmap key objectid is not aligned to %u, has " BTRFS_KEY_FMT,
-			    blocksize, BTRFS_KEY_FMT_VALUE(key));
-		return -EUCLEAN;
-	}
-	if (unlikely(!IS_ALIGNED(key->offset, blocksize))) {
-		generic_err(leaf, slot,
-		"free space bitmap key offset is not aligned to %u, has " BTRFS_KEY_FMT,
-			    blocksize, BTRFS_KEY_FMT_VALUE(key));
-		return -EUCLEAN;
-	}
-	if (unlikely(key->offset == 0)) {
-		generic_err(leaf, slot, "free space bitmap length is 0");
-		return -EUCLEAN;
-	}
 	/*
 	 * The item must hold exactly the right number of bitmap bytes for the
 	 * range described by key->offset.  A mismatch means the item was
Signature · 1 line
2.54.0
author
#3 lore raw

PATCH 3/3 btrfs: tree-checker: add more cross checks for free space tree

In reply to Qu Wenruo

This introduces extra checks using the previous key.

If there is a previous key, we can do extra validations:

- The previous key is FREE_SPACE_INFO
This means the current extent/bitmap should be inside the free space info key range.

And matches the type of the free space info.

- The previous key is FREE_SPACE_EXTENT or FREE_SPACE_BITMAP In that case both the current and previous key should belong to the same block group.

Thus the key type must match, and no overlap between the two keys.

These extra checks are inspired by the recently added type checks during free space tree loading.

The new tree-checker checks will allow earlier detection, but the loading time checks are still needed, as the tree-checker checks are still inside the same leaf, not matching per-bg level checks.

---
 fs/btrfs/tree-checker.c | 67 ++++++++++++++++++++++++++++++++++++-----
 1 file changed, 60 insertions(+), 7 deletions(-)
fs/btrfs/tree-checker.c +60 -7
index ca9bb695f826..e965c4bfe0c2 100644
@@ -2119,7 +2119,8 @@ static int check_free_space_info(struct extent_buffer *leaf, struct btrfs_key *k
 	return 0;
 }
 
-static int check_free_space_common_key(struct extent_buffer *leaf, struct btrfs_key *key, int slot)
+static int check_free_space_common_key(struct extent_buffer *leaf, struct btrfs_key *key, int slot,
+				       struct btrfs_key *prev_key)
 {
 	struct btrfs_fs_info *fs_info = leaf->fs_info;
 	const u32 blocksize = fs_info->sectorsize;
@@ -2148,14 +2149,65 @@ static int check_free_space_common_key(struct extent_buffer *leaf, struct btrfs_
 			    type_str, key->objectid, key->offset);
 		return -EUCLEAN;
 	}
+	if (slot == 0)
+		return 0;
+
+	/*
+	 * Make sure the current key is inside the block group, and matching
+	 * the expected info type.
+	 */
+	if (prev_key->type == BTRFS_FREE_SPACE_INFO_KEY) {
+		struct btrfs_free_space_info *fsi;
+		u32 info_flags;
+
+		if (unlikely(key->objectid < prev_key->objectid ||
+			     key->objectid + key->offset > prev_key->objectid + prev_key->offset)) {
+			generic_err(leaf, slot,
+"free space %s is not inside the space info, prev key " BTRFS_KEY_FMT " current key " BTRFS_KEY_FMT,
+				    type_str, BTRFS_KEY_FMT_VALUE(prev_key),
+				    BTRFS_KEY_FMT_VALUE(key));
+			return -EUCLEAN;
+		}
+		fsi = btrfs_item_ptr(leaf, slot - 1, struct btrfs_free_space_info);
+		info_flags = btrfs_free_space_flags(leaf, fsi);
+		if (unlikely((info_flags == BTRFS_FREE_SPACE_USING_BITMAPS &&
+			      key->type == BTRFS_FREE_SPACE_EXTENT_KEY) ||
+			     (info_flags != BTRFS_FREE_SPACE_USING_BITMAPS &&
+			      key->type == BTRFS_FREE_SPACE_BITMAP_KEY))) {
+			generic_err(leaf, slot,
+"free space %s key type is not matching the type of space info, key type %u space info flags %u",
+				    type_str, key->type, info_flags);
+			return -EUCLEAN;
+		}
+		return 0;
+	}
+	/*
+	 * Previous key should be either FREE_SPACE_EXTENT or FREE_SPACE_BITMAP.
+	 * Inside the same block group the key type should match each other, and
+	 * no overlaps.
+	 */
+	if (unlikely(key->type != prev_key->type)) {
+		generic_err(leaf, slot,
+"free space %s key type is not matching the type of previous key, key type %u prev key type %u",
+			    type_str, key->type, prev_key->type);
+		return -EUCLEAN;
+	}
+	if (unlikely(prev_key->objectid + prev_key->offset > key->objectid)) {
+		generic_err(leaf, slot,
+"free space %s key overlaps previous key, prev key " BTRFS_KEY_FMT " current key " BTRFS_KEY_FMT,
+			    type_str, BTRFS_KEY_FMT_VALUE(prev_key),
+			    BTRFS_KEY_FMT_VALUE(key));
+		return -EUCLEAN;
+	}
 	return 0;
 }
 
-static int check_free_space_extent(struct extent_buffer *leaf, struct btrfs_key *key, int slot)
+static int check_free_space_extent(struct extent_buffer *leaf, struct btrfs_key *key, int slot,
+				   struct btrfs_key *prev_key)
 {
 	int ret;
 
-	ret = check_free_space_common_key(leaf, key, slot);
+	ret = check_free_space_common_key(leaf, key, slot, prev_key);
 	if (unlikely(ret < 0))
 		return ret;
 
@@ -2169,13 +2221,14 @@ static int check_free_space_extent(struct extent_buffer *leaf, struct btrfs_key
 }
 
 static int check_free_space_bitmap(struct extent_buffer *leaf,
-				   struct btrfs_key *key, int slot)
+				   struct btrfs_key *key, int slot,
+				   struct btrfs_key *prev_key)
 {
 	struct btrfs_fs_info *fs_info = leaf->fs_info;
 	u32 expected_item_size;
 	int ret;
 
-	ret = check_free_space_common_key(leaf, key, slot);
+	ret = check_free_space_common_key(leaf, key, slot, prev_key);
 	if (unlikely(ret < 0))
 		return ret;
 
@@ -2263,10 +2316,10 @@ static enum btrfs_tree_block_status check_leaf_item(struct extent_buffer *leaf,
 		ret = check_free_space_info(leaf, key, slot);
 		break;
 	case BTRFS_FREE_SPACE_EXTENT_KEY:
-		ret = check_free_space_extent(leaf, key, slot);
+		ret = check_free_space_extent(leaf, key, slot, prev_key);
 		break;
 	case BTRFS_FREE_SPACE_BITMAP_KEY:
-		ret = check_free_space_bitmap(leaf, key, slot);
+		ret = check_free_space_bitmap(leaf, key, slot, prev_key);
 		break;
 	case BTRFS_IDENTITY_REMAP_KEY:
 	case BTRFS_REMAP_KEY:
Signature · 1 line
2.54.0
Reviewed-by on the v1 series
#4 lore raw
In reply to Qu Wenruo
Quoted 16 lines · Qu Wenruo

The first patch is a small cleanup to share more code and remove duplications.

The second one is to avoid u64 overflow for the extent/bitmap/space info, mostly to catch obviously corruptedd size.

The last one is the main part, introducing cross-key checks.

If the previous key is FREE_SPACE_INFO, make sure the current key is inside the bg range, and matches the type the free space info is using.

If the previous key is FREE_SPACE_EXTENT/BITMAP, make sure the current key doesn't overlap with the previous one, and type matches the previous one. This will allow tree-checker to catch most (but not all) bad key type flipping.

Quoted 5 lines

Qu Wenruo (3):
btrfs: tree-checker: extract the shared key check for free space
entries
btrfs: tree-checker: ensure free space tree entries won't overflow
btrfs: tree-checker: add more cross checks for free space tree