btrfs-progs: check: Detect invalid dev extents and device items

PATCH Superseded Qu Wenruo 3 participants 9 messages Oct 8, 2018 Btrfs file system

lore

Share & tools

lore

Qu Wenruo

author

2018-10-08 07:00 UTC #0 lore raw

cover btrfs-progs: check: Detect invalid dev extents and device items

This patchset can be fetch from github:
https://github.com/adam900710/btrfs-progs/tree/dev_extents_check

Hans van Kranenburg reported a case where btrfs DUP chunk allocator could allocate invalid dev extents, either overlaps with existing dev extents or beyond device boundary.

This patchset enhances the btrfs-progs side to detect such problems. With hand crafted test image for it.

Qu Wenruo (5):
btrfs-progs: lowmem check: Add check for overlapping dev extents
btrfs-progs: original check: Add ability to detect bad dev extents
btrfs-progs: lowmem check: Add dev_item check for used bytes and total
bytes
btrfs-progs: original check: Add dev_item check for used bytes and
total bytes
btrfs-progs: fsck-tests: Add test image for dev extents beyond device
boundary

 check/main.c                                  | 105 ++++++++++++++++++
 check/mode-lowmem.c                           |  37 +++++-
 .../over_dev_boundary.img.xz                  | Bin 0 -> 1640 bytes
 tests/fsck-tests/036-bad-dev-extents/test.sh  |  19 ++++
 4 files changed, 159 insertions(+), 2 deletions(-)
 create mode 100644 tests/fsck-tests/036-bad-dev-extents/over_dev_boundary.img.xz
 create mode 100755 tests/fsck-tests/036-bad-dev-extents/test.sh

Signature · 1 line

2.19.0

Qu Wenruo

author

2018-10-08 07:00 UTC #1 lore raw

PATCH 1/5 btrfs-progs: lowmem check: Add check for overlapping dev extents

Add such check at check_dev_item(), since at that timing we're also iterating dev extents for dev item accounting.

Signed-off-by Qu Wenruo <[email protected]>

---
 check/mode-lowmem.c | 32 ++++++++++++++++++++++++++++++--
 1 file changed, 30 insertions(+), 2 deletions(-)

check/mode-lowmem.c +30 -2

index 1bce44f5658a..d387423639e6 100644
@@ -4065,6 +4065,8 @@ static int check_dev_item(struct btrfs_fs_info *fs_info,
 	u64 dev_id;
 	u64 used;
 	u64 total = 0;
+	u64 prev_devid = 0;
+	u64 prev_dev_ext_end = 0;
 	int ret;
 
 	dev_item = btrfs_item_ptr(eb, slot, struct btrfs_dev_item);

@@ -4086,8 +4088,16 @@ static int check_dev_item(struct btrfs_fs_info *fs_info,
 		return REFERENCER_MISSING;
 	}
 
-	/* Iterate dev_extents to calculate the used space of a device */
+	/*
+	 * Iterate dev_extents to calculate the used space of a device
+	 *
+	 * Also make sure no dev extents overlap and end beyond device boundary
+	 */
 	while (1) {
+		u64 devid;
+		u64 physical_offset;
+		u64 physical_len;
+
 		if (path.slots[0] >= btrfs_header_nritems(path.nodes[0]))
 			goto next;

@@ -4099,7 +4109,25 @@ static int check_dev_item(struct btrfs_fs_info *fs_info,
 
 		ptr = btrfs_item_ptr(path.nodes[0], path.slots[0],
 				     struct btrfs_dev_extent);
-		total += btrfs_dev_extent_length(path.nodes[0], ptr);
+		devid = key.objectid;
+		physical_offset = key.offset;
+		physical_len = btrfs_dev_extent_length(path.nodes[0], ptr);
+
+		if (prev_devid == devid && physical_offset < prev_dev_ext_end) {
+			error(
+"dev extent devid %llu offset %llu len %llu overlap with previous dev extent end %llu",
+			      devid, physical_offset, physical_len,
+			      prev_dev_ext_end);
+			return ACCOUNTING_MISMATCH;
+		}
+		if (physical_offset + physical_len > total_bytes) {
+			error(
+"dev extent devid %llu offset %llu len %llu is beyond device boundary %llu",
+			      devid, physical_offset, physical_len,
+			      total_bytes);
+			return ACCOUNTING_MISMATCH;
+		}
+		total += physical_len;
 next:
 		ret = btrfs_next_item(dev_root, &path);
 		if (ret)

Signature · 1 line

2.19.0

Su Yue

2018-10-08 09:21 UTC #2 lore raw

Re: [PATCH 1/5] btrfs-progs: lowmem check: Add check for overlapping dev extents

Quoted 13 lines · Qu Wenruo

Add such check at check_dev_item(), since at that timing we're also iterating dev extents for dev item accounting.
Signed-off-by Qu Wenruo <[email protected]>
---
  check/mode-lowmem.c | 32 ++++++++++++++++++++++++++++++--
  1 file changed, 30 insertions(+), 2 deletions(-)
check/mode-lowmem.c +0 -0
index 1bce44f5658a..d387423639e6 100644

check/mode-lowmem.c static int check_dev_item(struct btrfs_fs_info *fs_info, · line 4069

Quoted 5 lines

check/mode-lowmem.c +2 -0

@@ -4065,6 +4065,8 @@ static int check_dev_item(struct btrfs_fs_info *fs_info,
  	u64 dev_id;
  	u64 used;
  	u64 total = 0;
+	u64 prev_devid = 0;
+	u64 prev_dev_ext_end = 0;

Those two new variables aren't assigned anymore in the patch...

Thanks,
Su

Quoted 49 lines

check/mode-lowmem.c +28 -2

  	int ret;
 
  	dev_item = btrfs_item_ptr(eb, slot, struct btrfs_dev_item);

@@ -4086,8 +4088,16 @@ static int check_dev_item(struct btrfs_fs_info *fs_info,
  		return REFERENCER_MISSING;
  	}
 
-	/* Iterate dev_extents to calculate the used space of a device */
+	/*
+	 * Iterate dev_extents to calculate the used space of a device
+	 *
+	 * Also make sure no dev extents overlap and end beyond device boundary
+	 */
  	while (1) {
+		u64 devid;
+		u64 physical_offset;
+		u64 physical_len;
+
  		if (path.slots[0] >= btrfs_header_nritems(path.nodes[0]))
  			goto next;

@@ -4099,7 +4109,25 @@ static int check_dev_item(struct btrfs_fs_info *fs_info,
 
  		ptr = btrfs_item_ptr(path.nodes[0], path.slots[0],
  				     struct btrfs_dev_extent);
-		total += btrfs_dev_extent_length(path.nodes[0], ptr);
+		devid = key.objectid;
+		physical_offset = key.offset;
+		physical_len = btrfs_dev_extent_length(path.nodes[0], ptr);
+
+		if (prev_devid == devid && physical_offset < prev_dev_ext_end) {
+			error(
+"dev extent devid %llu offset %llu len %llu overlap with previous dev extent end %llu",
+			      devid, physical_offset, physical_len,
+			      prev_dev_ext_end);
+			return ACCOUNTING_MISMATCH;
+		}
+		if (physical_offset + physical_len > total_bytes) {
+			error(
+"dev extent devid %llu offset %llu len %llu is beyond device boundary %llu",
+			      devid, physical_offset, physical_len,
+			      total_bytes);
+			return ACCOUNTING_MISMATCH;
+		}
+		total += physical_len;
  next:
  		ret = btrfs_next_item(dev_root, &path);
  		if (ret)

Qu Wenruo

2018-10-08 10:13 UTC #3 lore raw

Re: [PATCH 1/5] btrfs-progs: lowmem check: Add check for overlapping dev extents

Quoted 11 lines · Su Yue

Quoted 8 lines · Qu Wenruo
Add such check at check_dev_item(), since at that timing we're also iterating dev extents for dev item accounting.
Signed-off-by Qu Wenruo <[email protected]>
---
check/mode-lowmem.c | 32 ++++++++++++++++++++++++++++++--
  1 file changed, 30 insertions(+), 2 deletions(-)

Quoted 13 lines

check/mode-lowmem.c static int check_dev_item(struct btrfs_fs_info · line 4070
Quoted 11 lines
check/mode-lowmem.c +2 -0
index 1bce44f5658a..d387423639e6 100644
@@ -4065,6 +4065,8 @@ static int check_dev_item(struct btrfs_fs_info
 *fs_info,
       u64 dev_id;
       u64 used;
       u64 total = 0;
+    u64 prev_devid = 0;
+    u64 prev_dev_ext_end = 0;
Those two new variables aren't assigned anymore in the patch...

Oh, what I'm doing... (palm face

I'll fix this with the test case bug.

Thanks for reviewing,
Qu

Quoted 55 lines

Thanks,
Su
Quoted 50 lines
check/mode-lowmem.c +0 -0
       int ret;
         dev_item = btrfs_item_ptr(eb, slot, struct btrfs_dev_item);
@@ -4086,8 +4088,16 @@ static int check_dev_item(struct btrfs_fs_info
 *fs_info,
           return REFERENCER_MISSING;
       }
-    /* Iterate dev_extents to calculate the used space of a device */ +    /*
+     * Iterate dev_extents to calculate the used space of a device +     *
+     * Also make sure no dev extents overlap and end beyond device boundary
+     */
      while (1) {
+        u64 devid;
+        u64 physical_offset;
+        u64 physical_len;
+
          if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) goto next;
@@ -4099,7 +4109,25 @@ static int check_dev_item(struct btrfs_fs_info *fs_info,
          ptr = btrfs_item_ptr(path.nodes[0], path.slots[0], struct btrfs_dev_extent);
-        total += btrfs_dev_extent_length(path.nodes[0], ptr); +        devid = key.objectid;
+        physical_offset = key.offset;
+        physical_len = btrfs_dev_extent_length(path.nodes[0], ptr); +
+        if (prev_devid == devid && physical_offset < prev_dev_ext_end) { +            error(
+"dev extent devid %llu offset %llu len %llu overlap with previous dev extent end %llu",
+                  devid, physical_offset, physical_len,
+                  prev_dev_ext_end);
+            return ACCOUNTING_MISMATCH;
+        }
+        if (physical_offset + physical_len > total_bytes) { +            error(
+"dev extent devid %llu offset %llu len %llu is beyond device boundary %llu",
+                  devid, physical_offset, physical_len,
+                  total_bytes);
+            return ACCOUNTING_MISMATCH;
+        }
+        total += physical_len;
next:
          ret = btrfs_next_item(dev_root, &path);
          if (ret)

Qu Wenruo

author

2018-10-08 07:00 UTC #4 lore raw

PATCH 2/5 btrfs-progs: original check: Add ability to detect bad dev extents

In reply to Qu Wenruo

Unlike lowmem mode check, we don't have good place for original mode to check overlap dev extents.

So this patch introduces a new function, btrfs_check_dev_extents(), to handle possible bad dev extents.

Reported-by Hans van Kranenburg <[email protected]>

Signed-off-by Qu Wenruo <[email protected]>

---
 check/main.c | 99 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 99 insertions(+)

check/main.c +99 -0

index bc2ee22f7943..ff9a785ce555 100644
@@ -8224,6 +8224,99 @@ out:
 	return ret;
 }
 
+/*
+ * Check if all dev extents are valid (not overlap nor beyond device
+ * boundary).
+ *
+ * Dev extents <-> chunk cross checking is already done in check_chunks().
+ */
+static int check_dev_extents(struct btrfs_fs_info *fs_info)
+{
+	struct btrfs_path path;
+	struct btrfs_key key;
+	struct btrfs_root *dev_root = fs_info->dev_root;
+	int ret;
+	u64 prev_devid = 0;
+	u64 prev_dev_ext_end = 0;
+
+	btrfs_init_path(&path);
+
+	key.objectid = 1;
+	key.type = BTRFS_DEV_EXTENT_KEY;
+	key.offset = 0;
+
+	ret = btrfs_search_slot(NULL, dev_root, &key, &path, 0, 0);
+	if (ret < 0) {
+		error("failed to search device tree: %s", strerror(-ret));
+		goto out;
+	}
+	if (path.slots[0] >= btrfs_header_nritems(path.nodes[0])) {
+		ret = btrfs_next_leaf(dev_root, &path);
+		if (ret < 0) {
+			error("failed to find next leaf: %s", strerror(-ret));
+			goto out;
+		}
+		if (ret > 0) {
+			ret = 0;
+			goto out;
+		}
+	}
+
+	while (1) {
+		struct btrfs_dev_extent *dev_ext;
+		struct btrfs_device *dev;
+		u64 devid;
+		u64 physical_offset;
+		u64 physical_len;
+
+		btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
+		if (key.type != BTRFS_DEV_EXTENT_KEY)
+			break;
+		dev_ext = btrfs_item_ptr(path.nodes[0], path.slots[0],
+					 struct btrfs_dev_extent);
+		devid = key.objectid;
+		physical_offset = key.offset;
+		physical_len = btrfs_dev_extent_length(path.nodes[0], dev_ext);
+
+		dev = btrfs_find_device(fs_info, devid, NULL, NULL);
+		if (!dev) {
+			error("failed to find device with devid %llu", devid);
+			ret = -EUCLEAN;
+			goto out;
+		}
+		if (prev_devid == devid && prev_dev_ext_end > physical_offset) {
+			error(
+"dev extent devid %llu physical offset %llu overlap with previous dev extent end %llu",
+			      devid, physical_offset, prev_dev_ext_end);
+			ret = -EUCLEAN;
+			goto out;
+		}
+		if (physical_offset + physical_len > dev->total_bytes) {
+			error(
+"dev extent devid %llu physical offset %llu len %llu is beyond device boudnary %llu",
+			      devid, physical_offset, physical_len,
+			      dev->total_bytes);
+			ret = -EUCLEAN;
+			goto out;
+		}
+		prev_devid = devid;
+		prev_dev_ext_end = physical_offset + physical_len;
+
+		ret = btrfs_next_item(dev_root, &path);
+		if (ret < 0) {
+			error("failed to find next leaf: %s", strerror(-ret));
+			goto out;
+		}
+		if (ret > 0) {
+			ret = 0;
+			break;
+		}
+	}
+out:
+	btrfs_release_path(&path);
+	return ret;
+}
+
 static int check_chunks_and_extents(struct btrfs_fs_info *fs_info)
 {
 	struct rb_root dev_cache;

@@ -8318,6 +8411,12 @@ again:
 		goto out;
 	}
 
+	ret = check_dev_extents(fs_info);
+	if (ret < 0) {
+		err = ret;
+		goto out;
+	}
+
 	ret = check_chunks(&chunk_cache, &block_group_cache,
 			   &dev_extent_cache, NULL, NULL, NULL, 0);
 	if (ret) {

Signature · 1 line

2.19.0

Qu Wenruo

author

2018-10-08 07:00 UTC #5 lore raw

PATCH 3/5 btrfs-progs: lowmem check: Add dev_item check for used bytes and total bytes

In reply to Qu Wenruo

Obviously, used bytes can't be larger than total bytes.

Signed-off-by Qu Wenruo <[email protected]>

---
 check/mode-lowmem.c | 5 +++++
 1 file changed, 5 insertions(+)

check/mode-lowmem.c +5 -0

index d387423639e6..c50e34236ac8 100644
@@ -4074,6 +4074,11 @@ static int check_dev_item(struct btrfs_fs_info *fs_info,
 	used = btrfs_device_bytes_used(eb, dev_item);
 	total_bytes = btrfs_device_total_bytes(eb, dev_item);
 
+	if (used > total_bytes) {
+		error("device %llu has incorrect used bytes %llu > total bytes %llu",
+			dev_id, used, total_bytes);
+		return ACCOUNTING_MISMATCH;
+	}
 	key.objectid = dev_id;
 	key.type = BTRFS_DEV_EXTENT_KEY;
 	key.offset = 0;

Signature · 1 line

2.19.0

Qu Wenruo

author

2018-10-08 07:00 UTC #6 lore raw

PATCH 4/5 btrfs-progs: original check: Add dev_item check for used bytes and total bytes

In reply to Qu Wenruo

Signed-off-by Qu Wenruo <[email protected]>

---
 check/main.c | 6 ++++++
 1 file changed, 6 insertions(+)

check/main.c +6 -0

index ff9a785ce555..12f12e18a83f 100644
@@ -7938,6 +7938,12 @@ static int check_device_used(struct device_record *dev_rec,
 	struct device_extent_record *dev_extent_rec;
 	u64 total_byte = 0;
 
+	if (dev_rec->byte_used > dev_rec->total_byte) {
+		error("device %llu has incorrect used bytes %llu > total bytes %llu",
+		      dev_rec->devid, dev_rec->byte_used, dev_rec->total_byte);
+		return -EUCLEAN;
+	}
+
 	cache = search_cache_extent2(&dext_cache->tree, dev_rec->devid, 0);
 	while (cache) {
 		dev_extent_rec = container_of(cache,

Signature · 1 line

2.19.0

Qu Wenruo

author

2018-10-08 07:00 UTC #7 lore raw

PATCH 5/5 btrfs-progs: fsck-tests: Add test image for dev extents beyond device boundary

In reply to Qu Wenruo

Now two locations can detect such problem, either by device item used/total bytes check, or by early dev extents check against device boundary.

The image is hand-crafted image which uses DATA SINGLE chunk to feed btrfs check.
As expected, as long as block group item, chunk item, device used bytes matches, older btrfs check can't detect such problem.

Signed-off-by Qu Wenruo <[email protected]>

---
 .../over_dev_boundary.img.xz                  | Bin 0 -> 1640 bytes
 tests/fsck-tests/036-bad-dev-extents/test.sh  |  19 ++++++++++++++++++
 2 files changed, 19 insertions(+)
 create mode 100644 tests/fsck-tests/036-bad-dev-extents/over_dev_boundary.img.xz
 create mode 100755 tests/fsck-tests/036-bad-dev-extents/test.sh

tests/fsck-tests/036-bad-dev-extents/over_dev_boundary.img.xz new file binary +0 -0

new file mode 100644
index 0000000000000000000000000000000000000000..47cb2a707b0097e369dc088ed0549f847995f136
GIT binary patch

tests/fsck-tests/036-bad-dev-extents/test.sh new file +19 -0

new file mode 100755
index 000000000000..d2a82a65f631
@@ -0,0 +1,19 @@
+#!/bin/bash
+#
+# Due to DUP chunk allocator bugs, we could allocate DUP chunks while its dev
+# extents could exist beyond device boundary.
+# And since all related items (block group, chunk, device used bytes) are all
+# valid, btrfs check won't report any error.
+#
+# This test case contain hand crafted minimal image, to test if btrfs check can
+# detect and report such error.
+
+source "$TEST_TOP/common"
+
+check_prereq btrfs
+
+check_image() {
+	run_check "$TOP/btrfs" check "$1"
+}
+
+check_all_images

Signature · 1 line

2.19.0

Su Yue

2018-10-08 09:18 UTC #8 lore raw

Re: [PATCH 5/5] btrfs-progs: fsck-tests: Add test image for dev extents beyond device boundary

Quoted 70 lines · Qu Wenruo

Now two locations can detect such problem, either by device item used/total bytes check, or by early dev extents check against device boundary.
The image is hand-crafted image which uses DATA SINGLE chunk to feed btrfs check.
As expected, as long as block group item, chunk item, device used bytes matches, older btrfs check can't detect such problem.
Signed-off-by Qu Wenruo <[email protected]>
---
  .../over_dev_boundary.img.xz                  | Bin 0 -> 1640 bytes
  tests/fsck-tests/036-bad-dev-extents/test.sh  |  19 ++++++++++++++++++
  2 files changed, 19 insertions(+)
create mode 100644 tests/fsck-tests/036-bad-dev-extents/over_dev_boundary.img.xz create mode 100755 tests/fsck-tests/036-bad-dev-extents/test.sh
tests/fsck-tests/036-bad-dev-extents/over_dev_boundary.img.xz new file binary +0 -0
new file mode 100644
index 0000000000000000000000000000000000000000..47cb2a707b0097e369dc088ed0549f847995f136
GIT binary patch
tests/fsck-tests/036-bad-dev-extents/test.sh new file +6 -0
new file mode 100755
index 000000000000..d2a82a65f631
@@ -0,0 +1,19 @@
+#!/bin/bash
+#
+# Due to DUP chunk allocator bugs, we could allocate DUP chunks while its dev
+# extents could exist beyond device boundary.
+# And since all related items (block group, chunk, device used bytes) are all
+# valid, btrfs check won't report any error.

tests/fsck-tests/036-bad-dev-extents/test.sh line 16

Quoted 10 lines

tests/fsck-tests/036-bad-dev-extents/test.sh new file +10 -0

+#
+# This test case contain hand crafted minimal image, to test if btrfs check can
+# detect and report such error.
+
+source "$TEST_TOP/common"
+
+check_prereq btrfs
+
+check_image() {
+	run_check "$TOP/btrfs" check "$1"

I checked to your branch and ran test but failed.
Should it be run_must_fail instead?

Quoted 4 lines

tests/fsck-tests/036-bad-dev-extents/test.sh new file +3 -0
+}
+
+check_all_images