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

PATCH In review Qu Wenruo 6 participants 15 messages Oct 8, 2018 – Dec 17, 2018 Btrfs file system

lore

Share & tools

lore

Qu Wenruo

author

2018-10-08 12:30 UTC #0 lore raw

v3 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.

Link https://www.spinics.net/lists/linux-btrfs/msg82370.html

Changelog:
v2:
Fix a bug in the 1st patch which makes lowmem mode never checks overlap dev extents.
Fix test case bug which never passes due to wrong script.
v3:
Add btrfs-image fixes to make test cases happy.

Qu Wenruo (6):
btrfs-progs: image: Use correct device size when restoring
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                           |  39 ++++++-
 image/main.c                                  |  48 +++++++-
 .../over_dev_boundary.img.xz                  | Bin 0 -> 1640 bytes
 tests/fsck-tests/036-bad-dev-extents/test.sh  |  20 ++++
 5 files changed, 207 insertions(+), 5 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.1

Qu Wenruo

author

2018-10-08 12:30 UTC #1 lore raw

PATCH v3 1/6 btrfs-progs: image: Use correct device size when restoring

When restoring btrfs image, the total_bytes of device item is not updated correctly. In fact total_bytes can be left 0 for restored image.

It doesn't trigger any error because btrfs check never checks total_bytes of dev item.
However this is going to change.

Fix it by populating total_bytes of device item with the end position of last dev extent to make later btrfs check happy.

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

---
 image/main.c | 48 +++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 45 insertions(+), 3 deletions(-)

image/main.c +45 -3

index 351c5a256938..d5b89bc3149f 100644
@@ -2082,15 +2082,17 @@ static void remap_overlapping_chunks(struct mdrestore_struct *mdres)
 }
 
 static int fixup_devices(struct btrfs_fs_info *fs_info,
-			 struct mdrestore_struct *mdres, off_t dev_size)
+			 struct mdrestore_struct *mdres, int out_fd)
 {
 	struct btrfs_trans_handle *trans;
 	struct btrfs_dev_item *dev_item;
+	struct btrfs_dev_extent *dev_ext;
 	struct btrfs_path path;
 	struct extent_buffer *leaf;
 	struct btrfs_root *root = fs_info->chunk_root;
 	struct btrfs_key key;
 	u64 devid, cur_devid;
+	u64 dev_size; /* Get from last dev extents */
 	int ret;
 
 	trans = btrfs_start_transaction(fs_info->tree_root, 1);

@@ -2101,16 +2103,56 @@ static int fixup_devices(struct btrfs_fs_info *fs_info,
 
 	dev_item = &fs_info->super_copy->dev_item;
 
+	btrfs_init_path(&path);
 	devid = btrfs_stack_device_id(dev_item);
 
+	key.objectid = devid;
+	key.type = BTRFS_DEV_EXTENT_KEY;
+	key.offset = (u64)-1;
+
+	ret = btrfs_search_slot(NULL, fs_info->dev_root, &key, &path, 0, 0);
+	if (ret < 0) {
+		error("failed to locate last dev extent of devid %llu: %s",
+			devid, strerror(-ret));
+		btrfs_release_path(&path);
+		return ret;
+	}
+	if (ret == 0) {
+		error("found invalid dev extent devid %llu offset -1",
+			devid);
+		btrfs_release_path(&path);
+		return -EUCLEAN;
+	}
+	ret = btrfs_previous_item(fs_info->dev_root, &path, devid,
+				  BTRFS_DEV_EXTENT_KEY);
+	if (ret > 0)
+		ret = -ENOENT;
+	if (ret < 0) {
+		error("failed to locate last dev extent of devid %llu: %s",
+			devid, strerror(-ret));
+		btrfs_release_path(&path);
+		return ret;
+	}
+
+	btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
+	dev_ext = btrfs_item_ptr(path.nodes[0], path.slots[0],
+				 struct btrfs_dev_extent);
+	dev_size = key.offset + btrfs_dev_extent_length(path.nodes[0], dev_ext);
+	btrfs_release_path(&path);
+
 	btrfs_set_stack_device_total_bytes(dev_item, dev_size);
 	btrfs_set_stack_device_bytes_used(dev_item, mdres->alloced_chunks);
+	/* Don't forget to enlarge the real file */
+	ret = ftruncate64(out_fd, dev_size);
+	if (ret < 0) {
+		error("failed to enlarge result image: %s", strerror(errno));
+		return -errno;
+	}
 
 	key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
 	key.type = BTRFS_DEV_ITEM_KEY;
 	key.offset = 0;
 
-	btrfs_init_path(&path);
 
 again:
 	ret = btrfs_search_slot(trans, root, &key, &path, -1, 1);

@@ -2275,7 +2317,7 @@ static int restore_metadump(const char *input, FILE *out, int old_restore,
 			return 1;
 		}
 
-		ret = fixup_devices(info, &mdrestore, st.st_size);
+		ret = fixup_devices(info, &mdrestore, fileno(out));
 		close_ctree(info->chunk_root);
 		if (ret)
 			goto out;

Signature · 1 line

2.19.1

Nikolay Borisov

Reviewed-by on v3 1/6

2018-10-11 12:07 UTC #2 lore raw

Re: [PATCH v3 1/6] btrfs-progs: image: Use correct device size when restoring

Quoted 9 lines · Qu Wenruo

When restoring btrfs image, the total_bytes of device item is not updated correctly. In fact total_bytes can be left 0 for restored image.
It doesn't trigger any error because btrfs check never checks total_bytes of dev item.
However this is going to change.
Fix it by populating total_bytes of device item with the end position of last dev extent to make later btrfs check happy.

'Setting it to the end position' really means "setting the total device size to the allocated space on the device". Is it more clear if stated as the second way ?

In any case:

Reviewed-by Nikolay Borisov <[email protected]>

Quoted 38 lines

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

---
 image/main.c | 48 +++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 45 insertions(+), 3 deletions(-)

image/main.c +6 -1

index 351c5a256938..d5b89bc3149f 100644
@@ -2082,15 +2082,17 @@ static void remap_overlapping_chunks(struct mdrestore_struct *mdres)
 }
 
 static int fixup_devices(struct btrfs_fs_info *fs_info,
-			 struct mdrestore_struct *mdres, off_t dev_size)
+			 struct mdrestore_struct *mdres, int out_fd)
 {
 	struct btrfs_trans_handle *trans;
 	struct btrfs_dev_item *dev_item;
+	struct btrfs_dev_extent *dev_ext;
 	struct btrfs_path path;
 	struct extent_buffer *leaf;
 	struct btrfs_root *root = fs_info->chunk_root;
 	struct btrfs_key key;
 	u64 devid, cur_devid;
+	u64 dev_size; /* Get from last dev extents */
 	int ret;
 
 	trans = btrfs_start_transaction(fs_info->tree_root, 1);

@@ -2101,16 +2103,56 @@ static int fixup_devices(struct btrfs_fs_info *fs_info,
 
 	dev_item = &fs_info->super_copy->dev_item;
 
+	btrfs_init_path(&path);
 	devid = btrfs_stack_device_id(dev_item);
 
+	key.objectid = devid;
+	key.type = BTRFS_DEV_EXTENT_KEY;

image/main.c static int fixup_devices(struct btrfs_fs_info *fs_info, · line 2120

Quoted 10 lines

image/main.c +10 -0

+	key.offset = (u64)-1;
+
+	ret = btrfs_search_slot(NULL, fs_info->dev_root, &key, &path, 0, 0);
+	if (ret < 0) {
+		error("failed to locate last dev extent of devid %llu: %s",
+			devid, strerror(-ret));
+		btrfs_release_path(&path);
+		return ret;
+	}
+	if (ret == 0) {

nit: I'd prefer if this is an else if since it emphasizes the fact that the if/elseif construct works on a single value.

image/main.c static int fixup_devices(struct btrfs_fs_info *fs_info, · line 2130

Quoted 10 lines

image/main.c +10 -0

+		error("found invalid dev extent devid %llu offset -1",
+			devid);
+		btrfs_release_path(&path);
+		return -EUCLEAN;
+	}
+	ret = btrfs_previous_item(fs_info->dev_root, &path, devid,
+				  BTRFS_DEV_EXTENT_KEY);
+	if (ret > 0)
+		ret = -ENOENT;
+	if (ret < 0) {

ditto

Quoted 39 lines

image/main.c +19 -2

+		error("failed to locate last dev extent of devid %llu: %s",
+			devid, strerror(-ret));
+		btrfs_release_path(&path);
+		return ret;
+	}
+
+	btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
+	dev_ext = btrfs_item_ptr(path.nodes[0], path.slots[0],
+				 struct btrfs_dev_extent);
+	dev_size = key.offset + btrfs_dev_extent_length(path.nodes[0], dev_ext);
+	btrfs_release_path(&path);
+
 	btrfs_set_stack_device_total_bytes(dev_item, dev_size);
 	btrfs_set_stack_device_bytes_used(dev_item, mdres->alloced_chunks);
+	/* Don't forget to enlarge the real file */
+	ret = ftruncate64(out_fd, dev_size);
+	if (ret < 0) {
+		error("failed to enlarge result image: %s", strerror(errno));
+		return -errno;
+	}
 
 	key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
 	key.type = BTRFS_DEV_ITEM_KEY;
 	key.offset = 0;
 
-	btrfs_init_path(&path);
 
 again:
 	ret = btrfs_search_slot(trans, root, &key, &path, -1, 1);

@@ -2275,7 +2317,7 @@ static int restore_metadump(const char *input, FILE *out, int old_restore,
 			return 1;
 		}
 
-		ret = fixup_devices(info, &mdrestore, st.st_size);
+		ret = fixup_devices(info, &mdrestore, fileno(out));
 		close_ctree(info->chunk_root);
 		if (ret)
 			goto out;

Qu Wenruo

2018-10-12 05:21 UTC #3 lore raw

Re: [PATCH v3 1/6] btrfs-progs: image: Use correct device size when restoring

Quoted 10 lines · Nikolay Borisov

Quoted 7 lines · Qu Wenruo
When restoring btrfs image, the total_bytes of device item is not updated correctly. In fact total_bytes can be left 0 for restored image.
It doesn't trigger any error because btrfs check never checks total_bytes of dev item.
However this is going to change.

Quoted 6 lines

Quoted 2 lines
Fix it by populating total_bytes of device item with the end position of last dev extent to make later btrfs check happy.
'Setting it to the end position' really means "setting the total device size to the allocated space on the device". Is it more clear if stated as the second way ?

Not exactly.

Don't forget that we have 0~1M reserved, and it's possible to have dev extent holes.
So it's not "allocated space" but really "the end position of the last dev extent"

Thanks,
Qu

Quoted 109 lines

In any case:

Reviewed-by Nikolay Borisov <[email protected]>

Quoted 38 lines

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

---
 image/main.c | 48 +++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 45 insertions(+), 3 deletions(-)

image/main.c +6 -1

index 351c5a256938..d5b89bc3149f 100644
@@ -2082,15 +2082,17 @@ static void remap_overlapping_chunks(struct mdrestore_struct *mdres)
 }
 
 static int fixup_devices(struct btrfs_fs_info *fs_info,
-			 struct mdrestore_struct *mdres, off_t dev_size)
+			 struct mdrestore_struct *mdres, int out_fd)
 {
 	struct btrfs_trans_handle *trans;
 	struct btrfs_dev_item *dev_item;
+	struct btrfs_dev_extent *dev_ext;
 	struct btrfs_path path;
 	struct extent_buffer *leaf;
 	struct btrfs_root *root = fs_info->chunk_root;
 	struct btrfs_key key;
 	u64 devid, cur_devid;
+	u64 dev_size; /* Get from last dev extents */
 	int ret;
 
 	trans = btrfs_start_transaction(fs_info->tree_root, 1);

@@ -2101,16 +2103,56 @@ static int fixup_devices(struct btrfs_fs_info *fs_info,
 
 	dev_item = &fs_info->super_copy->dev_item;
 
+	btrfs_init_path(&path);
 	devid = btrfs_stack_device_id(dev_item);
 
+	key.objectid = devid;
+	key.type = BTRFS_DEV_EXTENT_KEY;

image/main.c static int fixup_devices(struct btrfs_fs_info *fs_info, · line 2120

Quoted 10 lines

image/main.c +10 -0

+	key.offset = (u64)-1;
+
+	ret = btrfs_search_slot(NULL, fs_info->dev_root, &key, &path, 0, 0);
+	if (ret < 0) {
+		error("failed to locate last dev extent of devid %llu: %s",
+			devid, strerror(-ret));
+		btrfs_release_path(&path);
+		return ret;
+	}
+	if (ret == 0) {

nit: I'd prefer if this is an else if since it emphasizes the fact that the if/elseif construct works on a single value.

image/main.c static int fixup_devices(struct btrfs_fs_info *fs_info, · line 2130

Quoted 10 lines

image/main.c +10 -0

+		error("found invalid dev extent devid %llu offset -1",
+			devid);
+		btrfs_release_path(&path);
+		return -EUCLEAN;
+	}
+	ret = btrfs_previous_item(fs_info->dev_root, &path, devid,
+				  BTRFS_DEV_EXTENT_KEY);
+	if (ret > 0)
+		ret = -ENOENT;
+	if (ret < 0) {

ditto

Quoted 39 lines

image/main.c +19 -2

+		error("failed to locate last dev extent of devid %llu: %s",
+			devid, strerror(-ret));
+		btrfs_release_path(&path);
+		return ret;
+	}
+
+	btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
+	dev_ext = btrfs_item_ptr(path.nodes[0], path.slots[0],
+				 struct btrfs_dev_extent);
+	dev_size = key.offset + btrfs_dev_extent_length(path.nodes[0], dev_ext);
+	btrfs_release_path(&path);
+
 	btrfs_set_stack_device_total_bytes(dev_item, dev_size);
 	btrfs_set_stack_device_bytes_used(dev_item, mdres->alloced_chunks);
+	/* Don't forget to enlarge the real file */
+	ret = ftruncate64(out_fd, dev_size);
+	if (ret < 0) {
+		error("failed to enlarge result image: %s", strerror(errno));
+		return -errno;
+	}
 
 	key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
 	key.type = BTRFS_DEV_ITEM_KEY;
 	key.offset = 0;
 
-	btrfs_init_path(&path);
 
 again:
 	ret = btrfs_search_slot(trans, root, &key, &path, -1, 1);

@@ -2275,7 +2317,7 @@ static int restore_metadump(const char *input, FILE *out, int old_restore,
 			return 1;
 		}
 
-		ret = fixup_devices(info, &mdrestore, st.st_size);
+		ret = fixup_devices(info, &mdrestore, fileno(out));
 		close_ctree(info->chunk_root);
 		if (ret)
 			goto out;

Qu Wenruo

author

2018-10-08 12:30 UTC #4 lore raw

PATCH v3 2/6 btrfs-progs: lowmem check: Add check for overlapping dev extents

In reply to 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 | 34 ++++++++++++++++++++++++++++++++--
 1 file changed, 32 insertions(+), 2 deletions(-)

check/mode-lowmem.c +32 -2

index 1bce44f5658a..07c03cad77af 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,27 @@ 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;
+		}
+		prev_devid = devid;
+		prev_dev_ext_end = physical_offset + physical_len;
+		total += physical_len;
 next:
 		ret = btrfs_next_item(dev_root, &path);
 		if (ret)

Signature · 1 line

2.19.1

Su Yue

Reviewed-by on v3 2/6

2018-10-09 01:39 UTC #5 lore raw

Re: [PATCH v3 2/6] btrfs-progs: lowmem check: Add check for overlapping dev extents

Quoted 4 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]>

LGTM.

Reviewed-by Su Yue <[email protected]>

Quoted 65 lines

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

check/mode-lowmem.c +32 -2

index 1bce44f5658a..07c03cad77af 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,27 @@ 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;
+		}
+		prev_devid = devid;
+		prev_dev_ext_end = physical_offset + physical_len;
+		total += physical_len;
  next:
  		ret = btrfs_next_item(dev_root, &path);
  		if (ret)

Qu Wenruo

author

2018-10-08 12:30 UTC #6 lore raw

PATCH v3 3/6 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.1

Su Yue

Reviewed-by on v3 3/6

2018-10-09 01:54 UTC #7 lore raw

Re: [PATCH v3 3/6] btrfs-progs: original check: Add ability to detect bad dev extents

Quoted 8 lines · 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]>

Reviewed-by Su Yue <[email protected]>

Quoted 122 lines

---
  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) {

Qu Wenruo

author

2018-10-08 12:31 UTC #8 lore raw

PATCH v3 4/6 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 07c03cad77af..1173b963b8f3 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.1

Hans van Kranenburg

2018-10-08 22:20 UTC #9 lore raw

Re: [PATCH v3 4/6] btrfs-progs: lowmem check: Add dev_item check for used bytes and total bytes

Quoted 12 lines · 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 +0 -0
index 07c03cad77af..1173b963b8f3 100644

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

Quoted 7 lines

check/mode-lowmem.c +4 -0

@@ -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;

The message and return code point at an error in accounting logic.

However, if you have a fully allocated device and a DUP chunk ending beyond device, then having used > total_bytes is expected...

So maybe there's two possibilities... There's an error in the accounting logic, or there's an "over-allocation", which is another type of issue which produces used > total with correct accounting logic.

Quoted 5 lines

check/mode-lowmem.c +1 -0

+	}
 	key.objectid = dev_id;
 	key.type = BTRFS_DEV_EXTENT_KEY;
 	key.offset = 0;

Signature · 1 line

Hans van Kranenburg

Qu Wenruo

2018-10-09 01:14 UTC #10 lore raw

Re: [PATCH v3 4/6] btrfs-progs: lowmem check: Add dev_item check for used bytes and total bytes

Quoted 16 lines · Hans van Kranenburg

Quoted 15 lines · 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 +0 -0
index 07c03cad77af..1173b963b8f3 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);
 

Quoted 6 lines

check/mode-lowmem.c static int check_dev_item(struct btrfs_fs_info *fs_info, · line 4080
Quoted 4 lines
check/mode-lowmem.c +4 -0
+	if (used > total_bytes) {
+		error("device %llu has incorrect used bytes %llu > total bytes %llu",
+			dev_id, used, total_bytes);
+		return ACCOUNTING_MISMATCH;
The message and return code point at an error in accounting logic.

One of the biggest problem in lowmem is we don't always have the error code we really want.

And that's the case for this error message.
It's indeed not an accounting error, as in that case (just like that test case image) the used bytes is correct accounted.

The good news is, the return value is never really used to classify the error.
So as long as the error message makes sense, it's not a big problem.

Thanks,
Qu

Quoted 15 lines

However, if you have a fully allocated device and a DUP chunk ending beyond device, then having used > total_bytes is expected...
So maybe there's two possibilities... There's an error in the accounting logic, or there's an "over-allocation", which is another type of issue which produces used > total with correct accounting logic.
Quoted 5 lines
check/mode-lowmem.c +1 -0
+	}
 	key.objectid = dev_id;
 	key.type = BTRFS_DEV_EXTENT_KEY;
 	key.offset = 0;

Hans van Kranenburg

2018-10-09 20:21 UTC #11 lore raw

Re: [PATCH v3 4/6] btrfs-progs: lowmem check: Add dev_item check for used bytes and total bytes

Quoted 29 lines · Qu Wenruo

Quoted 16 lines · Hans van Kranenburg
Quoted 15 lines · 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 +0 -0
index 07c03cad77af..1173b963b8f3 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);
 
Quoted 6 lines
check/mode-lowmem.c static int check_dev_item(struct btrfs_fs_info *fs_info, · line 4080
Quoted 4 lines
check/mode-lowmem.c +4 -0
+	if (used > total_bytes) {
+		error("device %llu has incorrect used bytes %llu > total bytes %llu",
+			dev_id, used, total_bytes);
+		return ACCOUNTING_MISMATCH;
The message and return code point at an error in accounting logic.
One of the biggest problem in lowmem is we don't always have the error code we really want.

Quoted 7 lines

And that's the case for this error message.
It's indeed not an accounting error, as in that case (just like that test case image) the used bytes is correct accounted.
The good news is, the return value is never really used to classify the error.
So as long as the error message makes sense, it's not a big problem.

Aha. Clear, thanks for explaining.

Quoted 20 lines

Thanks,
Qu
Quoted 15 lines
However, if you have a fully allocated device and a DUP chunk ending beyond device, then having used > total_bytes is expected...
So maybe there's two possibilities... There's an error in the accounting logic, or there's an "over-allocation", which is another type of issue which produces used > total with correct accounting logic.
Quoted 5 lines
check/mode-lowmem.c +1 -0
+	}
 	key.objectid = dev_id;
 	key.type = BTRFS_DEV_EXTENT_KEY;
 	key.offset = 0;

Signature · 1 line

Hans van Kranenburg

Qu Wenruo

author

2018-10-08 12:31 UTC #12 lore raw

PATCH v3 5/6 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.1

Qu Wenruo

author

2018-10-08 12:31 UTC #13 lore raw

PATCH v3 6/6 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  |  20 ++++++++++++++++++
 2 files changed, 20 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 +20 -0

new file mode 100755
index 000000000000..fe2d05673bbe
@@ -0,0 +1,20 @@
+#!/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_mustfail "btrfs check failed to detect invalid dev extents" \
+		"$TOP/btrfs" check "$1"
+}
+
+check_all_images

Signature · 1 line

2.19.1

David Sterba

2018-12-17 18:55 UTC #14 lore raw

In reply to Qu Wenruo

Quoted 20 lines · Qu Wenruo

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.
Link https://www.spinics.net/lists/linux-btrfs/msg82370.html
Changelog:
v2:
Fix a bug in the 1st patch which makes lowmem mode never checks overlap dev extents.
Fix test case bug which never passes due to wrong script.
v3:
Add btrfs-image fixes to make test cases happy.

Quoted 10 lines

Qu Wenruo (6):
btrfs-progs: image: Use correct device size when restoring
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

Added to devel with some fixups, thanks.