btrfs: tree-checker: Add checker for variable length item

Since tree-checker has verified leaf when reading from disk, we don't need the existing checker.

This cleanup reverts the following commits:
fbc326159a01 ("btrfs: Verify dir_item in iterate_object_props") 64c7b01446f4 ("btrfs: Check name_len before in btrfs_del_root_ref") 488d7c456653 ("btrfs: Check name_len before reading btrfs_get_name") 59b0a7f2c7c1 ("btrfs: Check name_len before read in iterate_dir_item") 3c1d41844896 ("btrfs: Check name_len in btrfs_check_ref_name_override") 8ee8c2d62d5f ("btrfs: Verify dir_item in replay_xattr_deletes") 26a836cec2ea ("btrfs: Check name_len on add_inode_ref call path") e79a33270d05 ("btrfs: Check name_len with boundary in verify dir_item") 19c6dcbfa746 ("btrfs: Introduce btrfs_is_name_len_valid to avoid reading beyond boundary")

Quoted 13 lines · Qu Wenruo

Since tree-checker has verified leaf when reading from disk, we don't need the existing checker.

This cleanup reverts the following commits:
fbc326159a01 ("btrfs: Verify dir_item in iterate_object_props") 64c7b01446f4 ("btrfs: Check name_len before in btrfs_del_root_ref") 488d7c456653 ("btrfs: Check name_len before reading btrfs_get_name") 59b0a7f2c7c1 ("btrfs: Check name_len before read in iterate_dir_item") 3c1d41844896 ("btrfs: Check name_len in btrfs_check_ref_name_override") 8ee8c2d62d5f ("btrfs: Verify dir_item in replay_xattr_deletes") 26a836cec2ea ("btrfs: Check name_len on add_inode_ref call path") e79a33270d05 ("btrfs: Check name_len with boundary in verify dir_item") 19c6dcbfa746 ("btrfs: Introduce btrfs_is_name_len_valid to avoid reading beyond boundary")

Oh well, there it goes, but I like the centralized tree checker more, so this is a small cost.

Reviewed-by David Sterba <[email protected]>

--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

For the following types, we have items with variable length:
(With BTRFS_ prefix and _KEY suffix snipped)

DIR_ITEM
DIR_INDEX
XATTR_ITEM
INODE_REF
INODE_EXTREF
ROOT_REF
ROOT_BACKREF

They all use @name_len to indicate their name length, and XATTR_ITEM has extra @data_len to indicate it data length.

Despite their variable length, it's also possible to have several such structure inside one item.

This patch will add checker to ensure:

1) No structure header and its data cross item boundary
2) Except XATTR_ITEM, no structure should have non-zero @data_len

This checker is especially useful to avoid possible access beyond boundary for fuzzed image.

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

---
 fs/btrfs/tree-checker.c | 123 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 123 insertions(+)

fs/btrfs/tree-checker.c +6 -0

index 114fc5f0ecc5..f26e86fcbd74 100644
@@ -222,6 +222,120 @@ static int check_csum_item(struct btrfs_root *root, struct extent_buffer *leaf,
 	return 0;
 }
 
+static u32 get_header_size(u8 type)
+{
+	switch (type) {
+	case BTRFS_DIR_ITEM_KEY:
+	case BTRFS_DIR_INDEX_KEY:
+	case BTRFS_XATTR_ITEM_KEY:

fs/btrfs/tree-checker.c +6 -0

+	unsigned long leaf_offset = header_offset + BTRFS_LEAF_DATA_OFFSET;
+
+	switch (type) {
+	case BTRFS_DIR_ITEM_KEY:
+	case BTRFS_DIR_INDEX_KEY:
+	case BTRFS_XATTR_ITEM_KEY:

fs/btrfs/tree-checker.c +31 -0

+	return 0;
+}
+
+static u16 get_header_datalen(struct extent_buffer *leaf, u8 type,
+			      unsigned long header_offset)
+{
+	/* Same as get_header_namelen */
+	unsigned long leaf_offset = header_offset + BTRFS_LEAF_DATA_OFFSET;
+
+	switch (type) {
+	case BTRFS_DIR_ITEM_KEY:
+	case BTRFS_DIR_INDEX_KEY:
+	case BTRFS_XATTR_ITEM_KEY:
+		return btrfs_dir_data_len(leaf, (void *)leaf_offset);
+	}
+	return 0;
+}
+
+/*
+ * For items with variable length, normally with namelen and tailing data.
+ * Like INODE_REF or XATTR
+ */
+static int check_variable_length_item(struct btrfs_root *root,
+				      struct extent_buffer *leaf,
+				      struct btrfs_key *key, int slot)
+{
+	u8 type = key->type;
+	u32 item_start = btrfs_item_offset_nr(leaf, slot);
+	u32 item_end = btrfs_item_end_nr(leaf, slot);
+	u32 header_size = get_header_size(type);
+	u32 total_size;

fs/btrfs/tree-checker.c +11 -0

+				cur + header_size, cur, item_end);
+			return -EUCLEAN;
+		}
+
+		namelen = get_header_namelen(leaf, type, cur);
+		datalen = get_header_datalen(leaf, type, cur);
+
+		/* Only XATTR can own data */
+		if (type != BTRFS_XATTR_ITEM_KEY && datalen) {
+			generic_err(root, leaf, slot,
+				"item has invalid data len, have %u expect 0",

fs/btrfs/tree-checker.c +11 -0

+				cur + total_size, cur + header_size, item_end);
+			return -EUCLEAN;
+		}
+
+		cur += total_size;
+	}
+	return 0;
+}
+
 /*
  * Common point to switch the item-specific validation.
  */

@@ -238,6 +352,15 @@ static int check_leaf_item(struct btrfs_root *root,
 	case BTRFS_EXTENT_CSUM_KEY:
 		ret = check_csum_item(root, leaf, key, slot);
 		break;
+	case BTRFS_DIR_ITEM_KEY:
+	case BTRFS_XATTR_ITEM_KEY:

Quoted 53 lines · Qu Wenruo

For the following types, we have items with variable length:
(With BTRFS_ prefix and _KEY suffix snipped)

DIR_ITEM
DIR_INDEX
XATTR_ITEM
INODE_REF
INODE_EXTREF
ROOT_REF
ROOT_BACKREF

They all use @name_len to indicate their name length, and XATTR_ITEM has extra @data_len to indicate it data length.

Despite their variable length, it's also possible to have several such structure inside one item.

This patch will add checker to ensure:

1) No structure header and its data cross item boundary
2) Except XATTR_ITEM, no structure should have non-zero @data_len

This checker is especially useful to avoid possible access beyond boundary for fuzzed image.

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

---
 fs/btrfs/tree-checker.c | 123 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 123 insertions(+)

fs/btrfs/tree-checker.c +15 -0

index 114fc5f0ecc5..f26e86fcbd74 100644
@@ -222,6 +222,120 @@ static int check_csum_item(struct btrfs_root *root, struct extent_buffer *leaf,
 	return 0;
 }
 
+static u32 get_header_size(u8 type)
+{
+	switch (type) {
+	case BTRFS_DIR_ITEM_KEY:
+	case BTRFS_DIR_INDEX_KEY:
+	case BTRFS_XATTR_ITEM_KEY:
+		return sizeof(struct btrfs_dir_item);
+	case BTRFS_INODE_REF_KEY:
+		return sizeof(struct btrfs_inode_ref);
+	case BTRFS_INODE_EXTREF_KEY:
+		return sizeof(struct btrfs_inode_extref);
+	case BTRFS_ROOT_REF_KEY:
+	case BTRFS_ROOT_BACKREF_KEY:
+		return sizeof(struct btrfs_root_ref);
+	}

fs/btrfs/tree-checker.c static int check_csum_item(struct btrfs_root *root, struct extent_buffer *leaf, · line 240

Quoted 1 line

fs/btrfs/tree-checker.c +1 -0

+	WARN_ON(1);

The helper name suggests is generic so this warning is there to catch new use, possibly without the matching validation function? If it is so, I'd rather use ASSERT. If you really want a warning, then please replace it with a message. The stacktrace from WARN_ON would not be very useful because we know exactly how we get here, the callchaning starts in the endio handlers.

fs/btrfs/tree-checker.c static int check_csum_item(struct btrfs_root *root, struct extent_buffer *leaf, · line 251

Quoted 12 lines

fs/btrfs/tree-checker.c +11 -0

+	return 0;
+}
+
+static u16 get_header_namelen(struct extent_buffer *leaf, u8 type,
+			      u32 header_offset)
+{
+	/*
+	 * @header_offset is offset starts after leaf header, while the
+	 * accessors expects offset starts from leaf header.
+	 * Sowe need to adds LEAF_DATA_OFFSET here
+	 */

Can you please rephrase the text? (and fix the typos)

Quoted 6 lines

fs/btrfs/tree-checker.c +6 -0

+	unsigned long leaf_offset = header_offset + BTRFS_LEAF_DATA_OFFSET;
+
+	switch (type) {
+	case BTRFS_DIR_ITEM_KEY:
+	case BTRFS_DIR_INDEX_KEY:
+	case BTRFS_XATTR_ITEM_KEY:

fs/btrfs/tree-checker.c static int check_csum_item(struct btrfs_root *root, struct extent_buffer *leaf, · line 267

Quoted 10 lines

fs/btrfs/tree-checker.c +10 -0

+		return btrfs_dir_name_len(leaf, (void *)leaf_offset);
+	case BTRFS_INODE_REF_KEY:
+		return btrfs_inode_ref_name_len(leaf, (void *)leaf_offset);
+	case BTRFS_INODE_EXTREF_KEY:
+		return btrfs_inode_extref_name_len(leaf, (void *)leaf_offset);
+	case BTRFS_ROOT_REF_KEY:
+	case BTRFS_ROOT_BACKREF_KEY:
+		return btrfs_root_ref_name_len(leaf, (void *)leaf_offset);
+	}
+	WARN_ON(1);

Similar comment as to the warning above, a message would be more helpful to say which type is unexpected.

Quoted 31 lines

fs/btrfs/tree-checker.c +31 -0

+	return 0;
+}
+
+static u16 get_header_datalen(struct extent_buffer *leaf, u8 type,
+			      unsigned long header_offset)
+{
+	/* Same as get_header_namelen */
+	unsigned long leaf_offset = header_offset + BTRFS_LEAF_DATA_OFFSET;
+
+	switch (type) {
+	case BTRFS_DIR_ITEM_KEY:
+	case BTRFS_DIR_INDEX_KEY:
+	case BTRFS_XATTR_ITEM_KEY:
+		return btrfs_dir_data_len(leaf, (void *)leaf_offset);
+	}
+	return 0;
+}
+
+/*
+ * For items with variable length, normally with namelen and tailing data.
+ * Like INODE_REF or XATTR
+ */
+static int check_variable_length_item(struct btrfs_root *root,
+				      struct extent_buffer *leaf,
+				      struct btrfs_key *key, int slot)
+{
+	u8 type = key->type;
+	u32 item_start = btrfs_item_offset_nr(leaf, slot);
+	u32 item_end = btrfs_item_end_nr(leaf, slot);
+	u32 header_size = get_header_size(type);
+	u32 total_size;

fs/btrfs/tree-checker.c static int check_csum_item(struct btrfs_root *root, struct extent_buffer *leaf, · line 308

Quoted 10 lines

fs/btrfs/tree-checker.c +10 -0

+	u32 cur = item_start;
+
+	while (cur < item_end) {
+		u32 namelen;
+		u32 datalen;
+
+		/* header itself should not cross item boundary */
+		if (cur + header_size > item_end) {
+			generic_err(root, leaf, slot,
+				"structure header crosses item boundary, have %u expect (%u, %u]",

Un-indent please. I'm slightly confused by the "(%u, %u]" notation, this reads as an open interval from the left but I don't understand it in this context.

Quoted 11 lines

fs/btrfs/tree-checker.c +11 -0

+				cur + header_size, cur, item_end);
+			return -EUCLEAN;
+		}
+
+		namelen = get_header_namelen(leaf, type, cur);
+		datalen = get_header_datalen(leaf, type, cur);
+
+		/* Only XATTR can own data */
+		if (type != BTRFS_XATTR_ITEM_KEY && datalen) {
+			generic_err(root, leaf, slot,
+				"item has invalid data len, have %u expect 0",

fs/btrfs/tree-checker.c static int check_csum_item(struct btrfs_root *root, struct extent_buffer *leaf, · line 329

Quoted 10 lines

fs/btrfs/tree-checker.c +10 -0

+				datalen);
+			return -EUCLEAN;
+		}
+
+		total_size = header_size + namelen + datalen;
+
+		/* header and name/data should not cross item boundary */
+		if (cur + total_size > item_end) {
+			generic_err(root, leaf, slot,
+				"structure data crosses item boundary, have %u expect (%u, %u]",

Same.

Quoted 18 lines

fs/btrfs/tree-checker.c +11 -0

+				cur + total_size, cur + header_size, item_end);
+			return -EUCLEAN;
+		}
+
+		cur += total_size;
+	}
+	return 0;
+}
+
 /*
  * Common point to switch the item-specific validation.
  */

@@ -238,6 +352,15 @@ static int check_leaf_item(struct btrfs_root *root,
 	case BTRFS_EXTENT_CSUM_KEY:
 		ret = check_csum_item(root, leaf, key, slot);
 		break;
+	case BTRFS_DIR_ITEM_KEY:
+	case BTRFS_XATTR_ITEM_KEY:

fs/btrfs/tree-checker.c static int check_leaf_item(struct btrfs_root *root, · line 366

Quoted 10 lines

fs/btrfs/tree-checker.c +7 -0

+	case BTRFS_DIR_INDEX_KEY:
+	case BTRFS_INODE_REF_KEY:
+	case BTRFS_INODE_EXTREF_KEY:
+	case BTRFS_ROOT_REF_KEY:
+	case BTRFS_ROOT_BACKREF_KEY:
+		ret = check_variable_length_item(root, leaf, key, slot);
+		break;
 	}
 	return ret;
 }

Otherwise ok.
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html

Quoted 54 lines · David Sterba

Quoted 53 lines · Qu Wenruo

For the following types, we have items with variable length:
(With BTRFS_ prefix and _KEY suffix snipped)

DIR_ITEM
DIR_INDEX
XATTR_ITEM
INODE_REF
INODE_EXTREF
ROOT_REF
ROOT_BACKREF

They all use @name_len to indicate their name length, and XATTR_ITEM has extra @data_len to indicate it data length.

Despite their variable length, it's also possible to have several such structure inside one item.

This patch will add checker to ensure:

1) No structure header and its data cross item boundary
2) Except XATTR_ITEM, no structure should have non-zero @data_len

This checker is especially useful to avoid possible access beyond boundary for fuzzed image.

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

---
 fs/btrfs/tree-checker.c | 123 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 123 insertions(+)

fs/btrfs/tree-checker.c +15 -0

index 114fc5f0ecc5..f26e86fcbd74 100644
@@ -222,6 +222,120 @@ static int check_csum_item(struct btrfs_root *root, struct extent_buffer *leaf,
 	return 0;
 }
 
+static u32 get_header_size(u8 type)
+{
+	switch (type) {
+	case BTRFS_DIR_ITEM_KEY:
+	case BTRFS_DIR_INDEX_KEY:
+	case BTRFS_XATTR_ITEM_KEY:
+		return sizeof(struct btrfs_dir_item);
+	case BTRFS_INODE_REF_KEY:
+		return sizeof(struct btrfs_inode_ref);
+	case BTRFS_INODE_EXTREF_KEY:
+		return sizeof(struct btrfs_inode_extref);
+	case BTRFS_ROOT_REF_KEY:
+	case BTRFS_ROOT_BACKREF_KEY:
+		return sizeof(struct btrfs_root_ref);
+	}

Quoted 8 lines

fs/btrfs/tree-checker.c static int check_csum_item(struct btrfs_root *root, struct extent_buffer *leaf, · line 240

Quoted 1 line

fs/btrfs/tree-checker.c +1 -0

+	WARN_ON(1);

The helper name suggests is generic so this warning is there to catch new use, possibly without the matching validation function? If it is so, I'd rather use ASSERT. If you really want a warning, then please replace it with a message. The stacktrace from WARN_ON would not be very useful because we know exactly how we get here, the callchaning starts in the endio handlers.

Please ignore this patch, as there is v2 patch which doesn't use such centralized check.

Thanks,
Qu

Quoted 140 lines

fs/btrfs/tree-checker.c static int check_csum_item(struct btrfs_root *root, struct extent_buffer *leaf, · line 251

Quoted 12 lines

fs/btrfs/tree-checker.c +11 -0

+	return 0;
+}
+
+static u16 get_header_namelen(struct extent_buffer *leaf, u8 type,
+			      u32 header_offset)
+{
+	/*
+	 * @header_offset is offset starts after leaf header, while the
+	 * accessors expects offset starts from leaf header.
+	 * Sowe need to adds LEAF_DATA_OFFSET here
+	 */

Can you please rephrase the text? (and fix the typos)

Quoted 6 lines

fs/btrfs/tree-checker.c +6 -0

+	unsigned long leaf_offset = header_offset + BTRFS_LEAF_DATA_OFFSET;
+
+	switch (type) {
+	case BTRFS_DIR_ITEM_KEY:
+	case BTRFS_DIR_INDEX_KEY:
+	case BTRFS_XATTR_ITEM_KEY:

fs/btrfs/tree-checker.c static int check_csum_item(struct btrfs_root *root, struct extent_buffer *leaf, · line 267

Quoted 10 lines

fs/btrfs/tree-checker.c +10 -0

+		return btrfs_dir_name_len(leaf, (void *)leaf_offset);
+	case BTRFS_INODE_REF_KEY:
+		return btrfs_inode_ref_name_len(leaf, (void *)leaf_offset);
+	case BTRFS_INODE_EXTREF_KEY:
+		return btrfs_inode_extref_name_len(leaf, (void *)leaf_offset);
+	case BTRFS_ROOT_REF_KEY:
+	case BTRFS_ROOT_BACKREF_KEY:
+		return btrfs_root_ref_name_len(leaf, (void *)leaf_offset);
+	}
+	WARN_ON(1);

Similar comment as to the warning above, a message would be more helpful to say which type is unexpected.

Quoted 31 lines

fs/btrfs/tree-checker.c +31 -0

+	return 0;
+}
+
+static u16 get_header_datalen(struct extent_buffer *leaf, u8 type,
+			      unsigned long header_offset)
+{
+	/* Same as get_header_namelen */
+	unsigned long leaf_offset = header_offset + BTRFS_LEAF_DATA_OFFSET;
+
+	switch (type) {
+	case BTRFS_DIR_ITEM_KEY:
+	case BTRFS_DIR_INDEX_KEY:
+	case BTRFS_XATTR_ITEM_KEY:
+		return btrfs_dir_data_len(leaf, (void *)leaf_offset);
+	}
+	return 0;
+}
+
+/*
+ * For items with variable length, normally with namelen and tailing data.
+ * Like INODE_REF or XATTR
+ */
+static int check_variable_length_item(struct btrfs_root *root,
+				      struct extent_buffer *leaf,
+				      struct btrfs_key *key, int slot)
+{
+	u8 type = key->type;
+	u32 item_start = btrfs_item_offset_nr(leaf, slot);
+	u32 item_end = btrfs_item_end_nr(leaf, slot);
+	u32 header_size = get_header_size(type);
+	u32 total_size;

fs/btrfs/tree-checker.c static int check_csum_item(struct btrfs_root *root, struct extent_buffer *leaf, · line 308

Quoted 10 lines

fs/btrfs/tree-checker.c +10 -0

+	u32 cur = item_start;
+
+	while (cur < item_end) {
+		u32 namelen;
+		u32 datalen;
+
+		/* header itself should not cross item boundary */
+		if (cur + header_size > item_end) {
+			generic_err(root, leaf, slot,
+				"structure header crosses item boundary, have %u expect (%u, %u]",

Un-indent please. I'm slightly confused by the "(%u, %u]" notation, this reads as an open interval from the left but I don't understand it in this context.

Quoted 11 lines

fs/btrfs/tree-checker.c +11 -0

+				cur + header_size, cur, item_end);
+			return -EUCLEAN;
+		}
+
+		namelen = get_header_namelen(leaf, type, cur);
+		datalen = get_header_datalen(leaf, type, cur);
+
+		/* Only XATTR can own data */
+		if (type != BTRFS_XATTR_ITEM_KEY && datalen) {
+			generic_err(root, leaf, slot,
+				"item has invalid data len, have %u expect 0",

fs/btrfs/tree-checker.c static int check_csum_item(struct btrfs_root *root, struct extent_buffer *leaf, · line 329

Quoted 10 lines

fs/btrfs/tree-checker.c +10 -0

+				datalen);
+			return -EUCLEAN;
+		}
+
+		total_size = header_size + namelen + datalen;
+
+		/* header and name/data should not cross item boundary */
+		if (cur + total_size > item_end) {
+			generic_err(root, leaf, slot,
+				"structure data crosses item boundary, have %u expect (%u, %u]",

Same.

Quoted 18 lines

fs/btrfs/tree-checker.c +11 -0

+				cur + total_size, cur + header_size, item_end);
+			return -EUCLEAN;
+		}
+
+		cur += total_size;
+	}
+	return 0;
+}
+
 /*
  * Common point to switch the item-specific validation.
  */

@@ -238,6 +352,15 @@ static int check_leaf_item(struct btrfs_root *root,
 	case BTRFS_EXTENT_CSUM_KEY:
 		ret = check_csum_item(root, leaf, key, slot);
 		break;
+	case BTRFS_DIR_ITEM_KEY:
+	case BTRFS_XATTR_ITEM_KEY:

fs/btrfs/tree-checker.c static int check_leaf_item(struct btrfs_root *root, · line 366

Quoted 10 lines

fs/btrfs/tree-checker.c +7 -0

+	case BTRFS_DIR_INDEX_KEY:
+	case BTRFS_INODE_REF_KEY:
+	case BTRFS_INODE_EXTREF_KEY:
+	case BTRFS_ROOT_REF_KEY:
+	case BTRFS_ROOT_BACKREF_KEY:
+		ret = check_variable_length_item(root, leaf, key, slot);
+		break;
 	}
 	return ret;
 }

Otherwise ok.
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html