[PATCH 0/3] Introduce comprehensive sanity check framework and

[PATCH 0/3] Introduce comprehensive sanity check framework and

[Qu Wenruo]

The patchset introduce a new framework to do more comprehensive (if not
the most) sanity check when reading out a leaf.

The new sanity checker will include:

1) Key order
   Existing code

2) Item boundary
   Existing code with enhanced checker to ensure item pointer doesn't
   overlap with item itself.

3) Key type based sanity checker
   Only EXTENT_DATA checker is implemented yet.
   As each checker should go through review and tests, or it can easily
   make a valid btrfs failed to be mounted.
   So only one checker is implemented as an example.

   Existing checker like INODE_REF checker can be moved to this
   framework easily, and we can centralize all existing checkers, make
   the rest of codes more clean.

Performance wise, it's just iterating a leaf.
And it will only get triggered when read out a leaf, cached leaf will
not go through such checker.
So it won't be a performance breaker.

I tested with the patchset applied on v4.13-rc6 with fstests, no
regression is detected.

Qu Wenruo (3):
  btrfs: Refactor check_leaf function for later expansion.
  btrfs: Check if item pointer overlap with item itself
  btrfs: Add sanity check for EXTENT_DATA when reading out leaf

 fs/btrfs/disk-io.c              | 137 ++++++++++++++++++++++++++++++++++------
 include/uapi/linux/btrfs_tree.h |   1 +
 2 files changed, 119 insertions(+), 19 deletions(-)

-- 
2.14.1

[PATCH 1/3] btrfs: Refactor check_leaf function for later expansion.

[Qu Wenruo]

Current check_leaf() function does a good job checking key orders and
item offset/size.

However it only checks from slot 0 to the last but one slot, this is
good but makes later expansion hard.

So this refactoring iterates from slot 0 to the last slot.
For key comparison, it uses a key with all 0 as initial key, so all
valid key should be larger than it.

And for item size/offset check, it compares current item end with
previous item offset.
For slot 0, use leaf end as special case.

This makes later item/key offset check and item size check easier to be
implemented.

Signed-off-by: Qu Wenruo <quwenruo.btrfs@gmx.com>
---
 fs/btrfs/disk-io.c | 42 +++++++++++++++++++++++-------------------
 1 file changed, 23 insertions(+), 19 deletions(-)

diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index 080e2ebb8aa0..919ddd4b774c 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -553,8 +553,9 @@ static noinline int check_leaf(struct btrfs_root *root,
 			       struct extent_buffer *leaf)
 {
 	struct btrfs_fs_info *fs_info = root->fs_info;
+	/* No valid key type is 0, so all key should be larger than this key */
+	struct btrfs_key prev_key = {0, 0, 0};
 	struct btrfs_key key;
-	struct btrfs_key leaf_key;
 	u32 nritems = btrfs_header_nritems(leaf);
 	int slot;
 
@@ -597,26 +598,21 @@ static noinline int check_leaf(struct btrfs_root *root,
 	if (nritems == 0)
 		return 0;
 
-	/* Check the 0 item */
-	if (btrfs_item_offset_nr(leaf, 0) + btrfs_item_size_nr(leaf, 0) !=
-	    BTRFS_LEAF_DATA_SIZE(fs_info)) {
-		CORRUPT("invalid item offset size pair", leaf, root, 0);
-		return -EIO;
-	}
-
 	/*
-	 * Check to make sure each items keys are in the correct order and their
-	 * offsets make sense.  We only have to loop through nritems-1 because
-	 * we check the current slot against the next slot, which verifies the
-	 * next slot's offset+size makes sense and that the current's slot
-	 * offset is correct.
+	 * Check the following things to make sure this is a good leaf, and
+	 * leaf users won't need to bother similar sanity check:
+	 *
+	 * 1) key order
+	 * 2) item offset and size
+	 *    No overlap, no hole, all inside the leaf.
 	 */
-	for (slot = 0; slot < nritems - 1; slot++) {
-		btrfs_item_key_to_cpu(leaf, &leaf_key, slot);
-		btrfs_item_key_to_cpu(leaf, &key, slot + 1);
+	for (slot = 0; slot < nritems; slot++) {
+		u32 item_end_expected;
+
+		btrfs_item_key_to_cpu(leaf, &key, slot);
 
 		/* Make sure the keys are in the right order */
-		if (btrfs_comp_cpu_keys(&leaf_key, &key) >= 0) {
+		if (btrfs_comp_cpu_keys(&prev_key, &key) >= 0) {
 			CORRUPT("bad key order", leaf, root, slot);
 			return -EIO;
 		}
@@ -626,8 +622,12 @@ static noinline int check_leaf(struct btrfs_root *root,
 		 * item data starts at the end of the leaf and grows towards the
 		 * front.
 		 */
-		if (btrfs_item_offset_nr(leaf, slot) !=
-			btrfs_item_end_nr(leaf, slot + 1)) {
+		if (slot == 0)
+			item_end_expected = BTRFS_LEAF_DATA_SIZE(fs_info);
+		else
+			item_end_expected = btrfs_item_offset_nr(leaf,
+								 slot - 1);
+		if (btrfs_item_end_nr(leaf, slot) != item_end_expected) {
 			CORRUPT("slot offset bad", leaf, root, slot);
 			return -EIO;
 		}
@@ -642,6 +642,10 @@ static noinline int check_leaf(struct btrfs_root *root,
 			CORRUPT("slot end outside of leaf", leaf, root, slot);
 			return -EIO;
 		}
+
+		prev_key.objectid = key.objectid;
+		prev_key.type = key.type;
+		prev_key.offset = key.offset;
 	}
 
 	return 0;
-- 
2.14.1

[PATCH 2/3] btrfs: Check if item pointer overlap with item itself

[Qu Wenruo]

Function check_leaf() checks if any item pointer points outside of the
leaf, but it doesn't check if the pointer overlap with the item itself.

Normally only the last item may be the victim, but add such check is
never a bad idea anyway.

Signed-off-by: Qu Wenruo <quwenruo.btrfs@gmx.com>
---
 fs/btrfs/disk-io.c | 7 +++++++
 1 file changed, 7 insertions(+)

diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index 919ddd4b774c..59ee7b959bf0 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -643,6 +643,13 @@ static noinline int check_leaf(struct btrfs_root *root,
 			return -EIO;
 		}
 
+		/* Also check if the item pointer overlaps with btrfs item. */
+		if (btrfs_item_nr_offset(slot) + sizeof(struct btrfs_item) >
+		    btrfs_item_ptr_offset(leaf, slot)) {
+			CORRUPT("slot overlap with its data", leaf, root, slot);
+			return -EIO;
+		}
+
 		prev_key.objectid = key.objectid;
 		prev_key.type = key.type;
 		prev_key.offset = key.offset;
-- 
2.14.1

[PATCH 3/3] btrfs: Add sanity check for EXTENT_DATA when reading out leaf

[Qu Wenruo]

Add extra checker for item with EXTENT_DATA type.
This checks the following thing:
1) Item size
   Plain text inline file extent size must match item size.
   (compressed inline file extent has no info about its on-disk size)
   Regular/preallocated file extent size must be a fixed value.

2) Every member of regular file extent item
   Including alignment for bytenr and offset, possible value for
   compression/encryption/type.

3) Type/compression/encode must be one of the valid values.

This should be the most comprehensive and restrict check in the context
of btrfs_item for EXTENT_DATA.

Signed-off-by: Qu Wenruo <quwenruo.btrfs@gmx.com>
---
 fs/btrfs/disk-io.c              | 88 +++++++++++++++++++++++++++++++++++++++++
 include/uapi/linux/btrfs_tree.h |  1 +
 2 files changed, 89 insertions(+)

diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
index 59ee7b959bf0..557f9a520e2a 100644
--- a/fs/btrfs/disk-io.c
+++ b/fs/btrfs/disk-io.c
@@ -549,6 +549,83 @@ static int check_tree_block_fsid(struct btrfs_fs_info *fs_info,
 		   btrfs_header_level(eb) == 0 ? "leaf" : "node",	\
 		   reason, btrfs_header_bytenr(eb), root->objectid, slot)
 
+static int check_extent_data_item(struct btrfs_root *root,
+				  struct extent_buffer *leaf, int slot)
+{
+	struct btrfs_file_extent_item *fi;
+	u32 sectorsize = root->fs_info->sectorsize;
+	u32 item_size = btrfs_item_size_nr(leaf, slot);
+
+	fi = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item);
+
+	if (btrfs_file_extent_type(leaf, fi) >= BTRFS_FILE_EXTENT_LAST_TYPE) {
+		CORRUPT("invalid file extent type", leaf, root, slot);
+		return -EIO;
+	}
+	if (btrfs_file_extent_compression(leaf, fi) >= BTRFS_COMPRESS_LAST) {
+		CORRUPT("invalid file extent compression", leaf, root, slot);
+		return -EIO;
+	}
+	if (btrfs_file_extent_encryption(leaf, fi)) {
+		CORRUPT("invalid file extent encryption", leaf, root, slot);
+		return -EIO;
+	}
+	if (btrfs_file_extent_type(leaf, fi) == BTRFS_FILE_EXTENT_INLINE) {
+		if (btrfs_file_extent_compression(leaf, fi) !=
+		    BTRFS_COMPRESS_NONE)
+			return 0;
+		/* Plaintext inline extent size must match item size */
+		if (item_size != BTRFS_FILE_EXTENT_INLINE_DATA_START +
+		    btrfs_file_extent_ram_bytes(leaf, fi)) {
+			CORRUPT("plaintext inline extent has invalid size",
+				leaf, root, slot);
+			return -EIO;
+		}
+		return 0;
+	}
+
+
+	/* regular or preallocated extent has fixed item size */
+	if (item_size != sizeof(*fi)) {
+		CORRUPT(
+		"regluar or preallocated extent data item size is invalid",
+			leaf, root, slot);
+		return -EIO;
+	}
+	if (!IS_ALIGNED(btrfs_file_extent_ram_bytes(leaf, fi), sectorsize) ||
+	    !IS_ALIGNED(btrfs_file_extent_disk_bytenr(leaf, fi), sectorsize) ||
+	    !IS_ALIGNED(btrfs_file_extent_disk_num_bytes(leaf, fi),
+			sectorsize) ||
+	    !IS_ALIGNED(btrfs_file_extent_offset(leaf, fi), sectorsize) ||
+	    !IS_ALIGNED(btrfs_file_extent_num_bytes(leaf, fi), sectorsize)) {
+		CORRUPT(
+		"regular or preallocated extent data item has unaligned value",
+			leaf, root, slot);
+		return -EIO;
+	}
+
+	return 0;
+}
+
+static int check_leaf_item(struct btrfs_root *root,
+			   struct extent_buffer *leaf, int slot)
+{
+	struct btrfs_key key;
+	int ret = 0;
+
+	btrfs_item_key_to_cpu(leaf, &key, slot);
+	/*
+	 * Considering how overcrowded the code will be inside the switch,
+	 * complex verification is better to moved its own function.
+	 */
+	switch (key.type) {
+	case BTRFS_EXTENT_DATA_KEY:
+		ret = check_extent_data_item(root, leaf, slot);
+		break;
+	}
+	return ret;
+}
+
 static noinline int check_leaf(struct btrfs_root *root,
 			       struct extent_buffer *leaf)
 {
@@ -605,9 +682,13 @@ static noinline int check_leaf(struct btrfs_root *root,
 	 * 1) key order
 	 * 2) item offset and size
 	 *    No overlap, no hole, all inside the leaf.
+	 * 3) item content
+	 *    If possible, do comprehensive sanity check.
+	 *    NOTE: All check must only rely on the item data itself.
 	 */
 	for (slot = 0; slot < nritems; slot++) {
 		u32 item_end_expected;
+		int ret;
 
 		btrfs_item_key_to_cpu(leaf, &key, slot);
 
@@ -650,6 +731,13 @@ static noinline int check_leaf(struct btrfs_root *root,
 			return -EIO;
 		}
 
+		/*
+		 * Check if the item size and content meets other limitation
+		 */
+		ret = check_leaf_item(root, leaf, slot);
+		if (ret < 0)
+			return ret;
+
 		prev_key.objectid = key.objectid;
 		prev_key.type = key.type;
 		prev_key.offset = key.offset;
diff --git a/include/uapi/linux/btrfs_tree.h b/include/uapi/linux/btrfs_tree.h
index 10689e1fdf11..3aadbb74a024 100644
--- a/include/uapi/linux/btrfs_tree.h
+++ b/include/uapi/linux/btrfs_tree.h
@@ -732,6 +732,7 @@ struct btrfs_balance_item {
 #define BTRFS_FILE_EXTENT_INLINE 0
 #define BTRFS_FILE_EXTENT_REG 1
 #define BTRFS_FILE_EXTENT_PREALLOC 2
+#define BTRFS_FILE_EXTENT_LAST_TYPE	3
 
 struct btrfs_file_extent_item {
 	/*
-- 
2.14.1

Re: [PATCH 3/3] btrfs: Add sanity check for EXTENT_DATA when reading out leaf

[Nikolay Borisov]

On 22.08.2017 10:37, Qu Wenruo wrote:
> Add extra checker for item with EXTENT_DATA type.
> This checks the following thing:
> 1) Item size
>    Plain text inline file extent size must match item size.
>    (compressed inline file extent has no info about its on-disk size)
>    Regular/preallocated file extent size must be a fixed value.
> 
> 2) Every member of regular file extent item
>    Including alignment for bytenr and offset, possible value for
>    compression/encryption/type.
> 
> 3) Type/compression/encode must be one of the valid values.
> 
> This should be the most comprehensive and restrict check in the context
> of btrfs_item for EXTENT_DATA.
> 
> Signed-off-by: Qu Wenruo <quwenruo.btrfs@gmx.com>
> ---
>  fs/btrfs/disk-io.c              | 88 +++++++++++++++++++++++++++++++++++++++++
>  include/uapi/linux/btrfs_tree.h |  1 +
>  2 files changed, 89 insertions(+)
> 
> diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
> index 59ee7b959bf0..557f9a520e2a 100644
> --- a/fs/btrfs/disk-io.c
> +++ b/fs/btrfs/disk-io.c
> @@ -549,6 +549,83 @@ static int check_tree_block_fsid(struct btrfs_fs_info *fs_info,
>  		   btrfs_header_level(eb) == 0 ? "leaf" : "node",	\
>  		   reason, btrfs_header_bytenr(eb), root->objectid, slot)
>  
> +static int check_extent_data_item(struct btrfs_root *root,
> +				  struct extent_buffer *leaf, int slot)
> +{
> +	struct btrfs_file_extent_item *fi;
> +	u32 sectorsize = root->fs_info->sectorsize;
> +	u32 item_size = btrfs_item_size_nr(leaf, slot);
> +
> +	fi = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item);
> +
> +	if (btrfs_file_extent_type(leaf, fi) >= BTRFS_FILE_EXTENT_LAST_TYPE) {
> +		CORRUPT("invalid file extent type", leaf, root, slot);
> +		return -EIO;
> +	}
> +	if (btrfs_file_extent_compression(leaf, fi) >= BTRFS_COMPRESS_LAST) {
> +		CORRUPT("invalid file extent compression", leaf, root, slot);
> +		return -EIO;
> +	}
> +	if (btrfs_file_extent_encryption(leaf, fi)) {
> +		CORRUPT("invalid file extent encryption", leaf, root, slot);
> +		return -EIO;
> +	}
> +	if (btrfs_file_extent_type(leaf, fi) == BTRFS_FILE_EXTENT_INLINE) {
> +		if (btrfs_file_extent_compression(leaf, fi) !=
> +		    BTRFS_COMPRESS_NONE)
> +			return 0;
> +		/* Plaintext inline extent size must match item size */
> +		if (item_size != BTRFS_FILE_EXTENT_INLINE_DATA_START +
> +		    btrfs_file_extent_ram_bytes(leaf, fi)) {
> +			CORRUPT("plaintext inline extent has invalid size",
> +				leaf, root, slot);
> +			return -EIO;
> +		}
> +		return 0;
> +	}
> +
> +
> +	/* regular or preallocated extent has fixed item size */
> +	if (item_size != sizeof(*fi)) {
> +		CORRUPT(
> +		"regluar or preallocated extent data item size is invalid",
> +			leaf, root, slot);
> +		return -EIO;
> +	}
> +	if (!IS_ALIGNED(btrfs_file_extent_ram_bytes(leaf, fi), sectorsize) ||
> +	    !IS_ALIGNED(btrfs_file_extent_disk_bytenr(leaf, fi), sectorsize) ||
> +	    !IS_ALIGNED(btrfs_file_extent_disk_num_bytes(leaf, fi),
> +			sectorsize) ||
> +	    !IS_ALIGNED(btrfs_file_extent_offset(leaf, fi), sectorsize) ||
> +	    !IS_ALIGNED(btrfs_file_extent_num_bytes(leaf, fi), sectorsize)) {
> +		CORRUPT(
> +		"regular or preallocated extent data item has unaligned value",
> +			leaf, root, slot);
> +		return -EIO;
> +	}
> +
> +	return 0;
> +}
> +
> +static int check_leaf_item(struct btrfs_root *root,
> +			   struct extent_buffer *leaf, int slot)
> +{
> +	struct btrfs_key key;
> +	int ret = 0;
> +
> +	btrfs_item_key_to_cpu(leaf, &key, slot);

nit: We already have the key in the proper format in the caller of this
function. Why not just pass in the type as an argument and save a
redundant call for every item in a leaf? Perhaps it's a
microoptimisation but for very densely populated trees the miniature
cost might build up.

> +	/*
> +	 * Considering how overcrowded the code will be inside the switch,
> +	 * complex verification is better to moved its own function.
> +	 */
> +	switch (key.type) {
> +	case BTRFS_EXTENT_DATA_KEY:
> +		ret = check_extent_data_item(root, leaf, slot);
> +		break;
> +	}
> +	return ret;
> +}
> +
>  static noinline int check_leaf(struct btrfs_root *root,
>  			       struct extent_buffer *leaf)
>  {
> @@ -605,9 +682,13 @@ static noinline int check_leaf(struct btrfs_root *root,
>  	 * 1) key order
>  	 * 2) item offset and size
>  	 *    No overlap, no hole, all inside the leaf.
> +	 * 3) item content
> +	 *    If possible, do comprehensive sanity check.
> +	 *    NOTE: All check must only rely on the item data itself.
>  	 */
>  	for (slot = 0; slot < nritems; slot++) {
>  		u32 item_end_expected;
> +		int ret;
>  
>  		btrfs_item_key_to_cpu(leaf, &key, slot);
>  
> @@ -650,6 +731,13 @@ static noinline int check_leaf(struct btrfs_root *root,
>  			return -EIO;
>  		}
>  
> +		/*
> +		 * Check if the item size and content meets other limitation
> +		 */
> +		ret = check_leaf_item(root, leaf, slot);
> +		if (ret < 0)
> +			return ret;
> +
>  		prev_key.objectid = key.objectid;
>  		prev_key.type = key.type;
>  		prev_key.offset = key.offset;
> diff --git a/include/uapi/linux/btrfs_tree.h b/include/uapi/linux/btrfs_tree.h
> index 10689e1fdf11..3aadbb74a024 100644
> --- a/include/uapi/linux/btrfs_tree.h
> +++ b/include/uapi/linux/btrfs_tree.h
> @@ -732,6 +732,7 @@ struct btrfs_balance_item {
>  #define BTRFS_FILE_EXTENT_INLINE 0
>  #define BTRFS_FILE_EXTENT_REG 1
>  #define BTRFS_FILE_EXTENT_PREALLOC 2
> +#define BTRFS_FILE_EXTENT_LAST_TYPE	3
>  
>  struct btrfs_file_extent_item {
>  	/*
> 

Re: [PATCH 3/3] btrfs: Add sanity check for EXTENT_DATA when reading out leaf

[Nikolay Borisov]

On 22.08.2017 13:57, Nikolay Borisov wrote:
> 
> 
> On 22.08.2017 10:37, Qu Wenruo wrote:
>> Add extra checker for item with EXTENT_DATA type.
>> This checks the following thing:
>> 1) Item size
>>    Plain text inline file extent size must match item size.
>>    (compressed inline file extent has no info about its on-disk size)
>>    Regular/preallocated file extent size must be a fixed value.
>>
>> 2) Every member of regular file extent item
>>    Including alignment for bytenr and offset, possible value for
>>    compression/encryption/type.
>>
>> 3) Type/compression/encode must be one of the valid values.
>>
>> This should be the most comprehensive and restrict check in the context
>> of btrfs_item for EXTENT_DATA.
>>
>> Signed-off-by: Qu Wenruo <quwenruo.btrfs@gmx.com>
>> ---
>>  fs/btrfs/disk-io.c              | 88 +++++++++++++++++++++++++++++++++++++++++
>>  include/uapi/linux/btrfs_tree.h |  1 +
>>  2 files changed, 89 insertions(+)
>>
>> diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
>> index 59ee7b959bf0..557f9a520e2a 100644
>> --- a/fs/btrfs/disk-io.c
>> +++ b/fs/btrfs/disk-io.c
>> @@ -549,6 +549,83 @@ static int check_tree_block_fsid(struct btrfs_fs_info *fs_info,
>>  		   btrfs_header_level(eb) == 0 ? "leaf" : "node",	\
>>  		   reason, btrfs_header_bytenr(eb), root->objectid, slot)
>>  
>> +static int check_extent_data_item(struct btrfs_root *root,
>> +				  struct extent_buffer *leaf, int slot)
>> +{
>> +	struct btrfs_file_extent_item *fi;
>> +	u32 sectorsize = root->fs_info->sectorsize;
>> +	u32 item_size = btrfs_item_size_nr(leaf, slot);
>> +
>> +	fi = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item);
>> +
>> +	if (btrfs_file_extent_type(leaf, fi) >= BTRFS_FILE_EXTENT_LAST_TYPE) {
>> +		CORRUPT("invalid file extent type", leaf, root, slot);
>> +		return -EIO;
>> +	}
>> +	if (btrfs_file_extent_compression(leaf, fi) >= BTRFS_COMPRESS_LAST) {
>> +		CORRUPT("invalid file extent compression", leaf, root, slot);
>> +		return -EIO;
>> +	}
>> +	if (btrfs_file_extent_encryption(leaf, fi)) {
>> +		CORRUPT("invalid file extent encryption", leaf, root, slot);
>> +		return -EIO;
>> +	}
>> +	if (btrfs_file_extent_type(leaf, fi) == BTRFS_FILE_EXTENT_INLINE) {
>> +		if (btrfs_file_extent_compression(leaf, fi) !=
>> +		    BTRFS_COMPRESS_NONE)
>> +			return 0;
>> +		/* Plaintext inline extent size must match item size */
>> +		if (item_size != BTRFS_FILE_EXTENT_INLINE_DATA_START +
>> +		    btrfs_file_extent_ram_bytes(leaf, fi)) {
>> +			CORRUPT("plaintext inline extent has invalid size",
>> +				leaf, root, slot);
>> +			return -EIO;
>> +		}
>> +		return 0;
>> +	}

One more thing - don't we really want to use -EUCLEAN rather than -EIO?


>> +
>> +
>> +	/* regular or preallocated extent has fixed item size */
>> +	if (item_size != sizeof(*fi)) {
>> +		CORRUPT(
>> +		"regluar or preallocated extent data item size is invalid",
>> +			leaf, root, slot);
>> +		return -EIO;
>> +	}
>> +	if (!IS_ALIGNED(btrfs_file_extent_ram_bytes(leaf, fi), sectorsize) ||
>> +	    !IS_ALIGNED(btrfs_file_extent_disk_bytenr(leaf, fi), sectorsize) ||
>> +	    !IS_ALIGNED(btrfs_file_extent_disk_num_bytes(leaf, fi),
>> +			sectorsize) ||
>> +	    !IS_ALIGNED(btrfs_file_extent_offset(leaf, fi), sectorsize) ||
>> +	    !IS_ALIGNED(btrfs_file_extent_num_bytes(leaf, fi), sectorsize)) {
>> +		CORRUPT(
>> +		"regular or preallocated extent data item has unaligned value",
>> +			leaf, root, slot);
>> +		return -EIO;
>> +	}
>> +
>> +	return 0;
>> +}
>> +
>> +static int check_leaf_item(struct btrfs_root *root,
>> +			   struct extent_buffer *leaf, int slot)
>> +{
>> +	struct btrfs_key key;
>> +	int ret = 0;
>> +
>> +	btrfs_item_key_to_cpu(leaf, &key, slot);
> 
> nit: We already have the key in the proper format in the caller of this
> function. Why not just pass in the type as an argument and save a
> redundant call for every item in a leaf? Perhaps it's a
> microoptimisation but for very densely populated trees the miniature
> cost might build up.
> 
>> +	/*
>> +	 * Considering how overcrowded the code will be inside the switch,
>> +	 * complex verification is better to moved its own function.
>> +	 */
>> +	switch (key.type) {
>> +	case BTRFS_EXTENT_DATA_KEY:
>> +		ret = check_extent_data_item(root, leaf, slot);
>> +		break;
>> +	}
>> +	return ret;
>> +}
>> +
>>  static noinline int check_leaf(struct btrfs_root *root,
>>  			       struct extent_buffer *leaf)
>>  {
>> @@ -605,9 +682,13 @@ static noinline int check_leaf(struct btrfs_root *root,
>>  	 * 1) key order
>>  	 * 2) item offset and size
>>  	 *    No overlap, no hole, all inside the leaf.
>> +	 * 3) item content
>> +	 *    If possible, do comprehensive sanity check.
>> +	 *    NOTE: All check must only rely on the item data itself.
>>  	 */
>>  	for (slot = 0; slot < nritems; slot++) {
>>  		u32 item_end_expected;
>> +		int ret;
>>  
>>  		btrfs_item_key_to_cpu(leaf, &key, slot);
>>  
>> @@ -650,6 +731,13 @@ static noinline int check_leaf(struct btrfs_root *root,
>>  			return -EIO;
>>  		}
>>  
>> +		/*
>> +		 * Check if the item size and content meets other limitation
>> +		 */
>> +		ret = check_leaf_item(root, leaf, slot);
>> +		if (ret < 0)
>> +			return ret;
>> +
>>  		prev_key.objectid = key.objectid;
>>  		prev_key.type = key.type;
>>  		prev_key.offset = key.offset;
>> diff --git a/include/uapi/linux/btrfs_tree.h b/include/uapi/linux/btrfs_tree.h
>> index 10689e1fdf11..3aadbb74a024 100644
>> --- a/include/uapi/linux/btrfs_tree.h
>> +++ b/include/uapi/linux/btrfs_tree.h
>> @@ -732,6 +732,7 @@ struct btrfs_balance_item {
>>  #define BTRFS_FILE_EXTENT_INLINE 0
>>  #define BTRFS_FILE_EXTENT_REG 1
>>  #define BTRFS_FILE_EXTENT_PREALLOC 2
>> +#define BTRFS_FILE_EXTENT_LAST_TYPE	3
>>  
>>  struct btrfs_file_extent_item {
>>  	/*
>>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 

Re: [PATCH 3/3] btrfs: Add sanity check for EXTENT_DATA when reading out leaf

[Qu Wenruo]

On 2017年08月22日 19:00, Nikolay Borisov wrote:
> 
> 
> On 22.08.2017 13:57, Nikolay Borisov wrote:
>>
>>
>> On 22.08.2017 10:37, Qu Wenruo wrote:
>>> Add extra checker for item with EXTENT_DATA type.
>>> This checks the following thing:
>>> 1) Item size
>>>     Plain text inline file extent size must match item size.
>>>     (compressed inline file extent has no info about its on-disk size)
>>>     Regular/preallocated file extent size must be a fixed value.
>>>
>>> 2) Every member of regular file extent item
>>>     Including alignment for bytenr and offset, possible value for
>>>     compression/encryption/type.
>>>
>>> 3) Type/compression/encode must be one of the valid values.
>>>
>>> This should be the most comprehensive and restrict check in the context
>>> of btrfs_item for EXTENT_DATA.
>>>
>>> Signed-off-by: Qu Wenruo <quwenruo.btrfs@gmx.com>
>>> ---
>>>   fs/btrfs/disk-io.c              | 88 +++++++++++++++++++++++++++++++++++++++++
>>>   include/uapi/linux/btrfs_tree.h |  1 +
>>>   2 files changed, 89 insertions(+)
>>>
>>> diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
>>> index 59ee7b959bf0..557f9a520e2a 100644
>>> --- a/fs/btrfs/disk-io.c
>>> +++ b/fs/btrfs/disk-io.c
>>> @@ -549,6 +549,83 @@ static int check_tree_block_fsid(struct btrfs_fs_info *fs_info,
>>>   		   btrfs_header_level(eb) == 0 ? "leaf" : "node",	\
>>>   		   reason, btrfs_header_bytenr(eb), root->objectid, slot)
>>>   
>>> +static int check_extent_data_item(struct btrfs_root *root,
>>> +				  struct extent_buffer *leaf, int slot)
>>> +{
>>> +	struct btrfs_file_extent_item *fi;
>>> +	u32 sectorsize = root->fs_info->sectorsize;
>>> +	u32 item_size = btrfs_item_size_nr(leaf, slot);
>>> +
>>> +	fi = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item);
>>> +
>>> +	if (btrfs_file_extent_type(leaf, fi) >= BTRFS_FILE_EXTENT_LAST_TYPE) {
>>> +		CORRUPT("invalid file extent type", leaf, root, slot);
>>> +		return -EIO;
>>> +	}
>>> +	if (btrfs_file_extent_compression(leaf, fi) >= BTRFS_COMPRESS_LAST) {
>>> +		CORRUPT("invalid file extent compression", leaf, root, slot);
>>> +		return -EIO;
>>> +	}
>>> +	if (btrfs_file_extent_encryption(leaf, fi)) {
>>> +		CORRUPT("invalid file extent encryption", leaf, root, slot);
>>> +		return -EIO;
>>> +	}
>>> +	if (btrfs_file_extent_type(leaf, fi) == BTRFS_FILE_EXTENT_INLINE) {
>>> +		if (btrfs_file_extent_compression(leaf, fi) !=
>>> +		    BTRFS_COMPRESS_NONE)
>>> +			return 0;
>>> +		/* Plaintext inline extent size must match item size */
>>> +		if (item_size != BTRFS_FILE_EXTENT_INLINE_DATA_START +
>>> +		    btrfs_file_extent_ram_bytes(leaf, fi)) {
>>> +			CORRUPT("plaintext inline extent has invalid size",
>>> +				leaf, root, slot);
>>> +			return -EIO;
>>> +		}
>>> +		return 0;
>>> +	}
> 
> One more thing - don't we really want to use -EUCLEAN rather than -EIO?

Nice suggestion.
Since it's not really something wrong with IO routine, EUCLEAN is better.

> 
> 
>>> +
>>> +
>>> +	/* regular or preallocated extent has fixed item size */
>>> +	if (item_size != sizeof(*fi)) {
>>> +		CORRUPT(
>>> +		"regluar or preallocated extent data item size is invalid",
>>> +			leaf, root, slot);
>>> +		return -EIO;
>>> +	}
>>> +	if (!IS_ALIGNED(btrfs_file_extent_ram_bytes(leaf, fi), sectorsize) ||
>>> +	    !IS_ALIGNED(btrfs_file_extent_disk_bytenr(leaf, fi), sectorsize) ||
>>> +	    !IS_ALIGNED(btrfs_file_extent_disk_num_bytes(leaf, fi),
>>> +			sectorsize) ||
>>> +	    !IS_ALIGNED(btrfs_file_extent_offset(leaf, fi), sectorsize) ||
>>> +	    !IS_ALIGNED(btrfs_file_extent_num_bytes(leaf, fi), sectorsize)) {
>>> +		CORRUPT(
>>> +		"regular or preallocated extent data item has unaligned value",
>>> +			leaf, root, slot);
>>> +		return -EIO;
>>> +	}
>>> +
>>> +	return 0;
>>> +}
>>> +
>>> +static int check_leaf_item(struct btrfs_root *root,
>>> +			   struct extent_buffer *leaf, int slot)
>>> +{
>>> +	struct btrfs_key key;
>>> +	int ret = 0;
>>> +
>>> +	btrfs_item_key_to_cpu(leaf, &key, slot);
>>
>> nit: We already have the key in the proper format in the caller of this
>> function. Why not just pass in the type as an argument and save a
>> redundant call for every item in a leaf? Perhaps it's a
>> microoptimisation but for very densely populated trees the miniature
>> cost might build up.

Sounds valid. Considering how many times this item_key_to_cpu() get 
called in a large leaf,
micro-optimization counts.

I'll update this in next revision.

Thanks for your review,
Qu

>>
>>> +	/*
>>> +	 * Considering how overcrowded the code will be inside the switch,
>>> +	 * complex verification is better to moved its own function.
>>> +	 */
>>> +	switch (key.type) {
>>> +	case BTRFS_EXTENT_DATA_KEY:
>>> +		ret = check_extent_data_item(root, leaf, slot);
>>> +		break;
>>> +	}
>>> +	return ret;
>>> +}
>>> +
>>>   static noinline int check_leaf(struct btrfs_root *root,
>>>   			       struct extent_buffer *leaf)
>>>   {
>>> @@ -605,9 +682,13 @@ static noinline int check_leaf(struct btrfs_root *root,
>>>   	 * 1) key order
>>>   	 * 2) item offset and size
>>>   	 *    No overlap, no hole, all inside the leaf.
>>> +	 * 3) item content
>>> +	 *    If possible, do comprehensive sanity check.
>>> +	 *    NOTE: All check must only rely on the item data itself.
>>>   	 */
>>>   	for (slot = 0; slot < nritems; slot++) {
>>>   		u32 item_end_expected;
>>> +		int ret;
>>>   
>>>   		btrfs_item_key_to_cpu(leaf, &key, slot);
>>>   
>>> @@ -650,6 +731,13 @@ static noinline int check_leaf(struct btrfs_root *root,
>>>   			return -EIO;
>>>   		}
>>>   
>>> +		/*
>>> +		 * Check if the item size and content meets other limitation
>>> +		 */
>>> +		ret = check_leaf_item(root, leaf, slot);
>>> +		if (ret < 0)
>>> +			return ret;
>>> +
>>>   		prev_key.objectid = key.objectid;
>>>   		prev_key.type = key.type;
>>>   		prev_key.offset = key.offset;
>>> diff --git a/include/uapi/linux/btrfs_tree.h b/include/uapi/linux/btrfs_tree.h
>>> index 10689e1fdf11..3aadbb74a024 100644
>>> --- a/include/uapi/linux/btrfs_tree.h
>>> +++ b/include/uapi/linux/btrfs_tree.h
>>> @@ -732,6 +732,7 @@ struct btrfs_balance_item {
>>>   #define BTRFS_FILE_EXTENT_INLINE 0
>>>   #define BTRFS_FILE_EXTENT_REG 1
>>>   #define BTRFS_FILE_EXTENT_PREALLOC 2
>>> +#define BTRFS_FILE_EXTENT_LAST_TYPE	3
>>>   
>>>   struct btrfs_file_extent_item {
>>>   	/*
>>>
>> --
>> To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
>> the body of a message to majordomo@vger.kernel.org
>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 

Re: [PATCH 3/3] btrfs: Add sanity check for EXTENT_DATA when reading out leaf

[Nikolay Borisov]

On 22.08.2017 14:23, Qu Wenruo wrote:
> 
> 
> On 2017年08月22日 19:00, Nikolay Borisov wrote:
>>
>>
>> On 22.08.2017 13:57, Nikolay Borisov wrote:
>>>
>>>
>>> On 22.08.2017 10:37, Qu Wenruo wrote:
>>>> Add extra checker for item with EXTENT_DATA type.
>>>> This checks the following thing:
>>>> 1) Item size
>>>>     Plain text inline file extent size must match item size.
>>>>     (compressed inline file extent has no info about its on-disk size)
>>>>     Regular/preallocated file extent size must be a fixed value.
>>>>
>>>> 2) Every member of regular file extent item
>>>>     Including alignment for bytenr and offset, possible value for
>>>>     compression/encryption/type.
>>>>
>>>> 3) Type/compression/encode must be one of the valid values.
>>>>
>>>> This should be the most comprehensive and restrict check in the context
>>>> of btrfs_item for EXTENT_DATA.
>>>>
>>>> Signed-off-by: Qu Wenruo <quwenruo.btrfs@gmx.com>
>>>> ---
>>>>   fs/btrfs/disk-io.c              | 88
>>>> +++++++++++++++++++++++++++++++++++++++++
>>>>   include/uapi/linux/btrfs_tree.h |  1 +
>>>>   2 files changed, 89 insertions(+)
>>>>
>>>> diff --git a/fs/btrfs/disk-io.c b/fs/btrfs/disk-io.c
>>>> index 59ee7b959bf0..557f9a520e2a 100644
>>>> --- a/fs/btrfs/disk-io.c
>>>> +++ b/fs/btrfs/disk-io.c
>>>> @@ -549,6 +549,83 @@ static int check_tree_block_fsid(struct
>>>> btrfs_fs_info *fs_info,
>>>>              btrfs_header_level(eb) == 0 ? "leaf" : "node",    \
>>>>              reason, btrfs_header_bytenr(eb), root->objectid, slot)
>>>>   +static int check_extent_data_item(struct btrfs_root *root,
>>>> +                  struct extent_buffer *leaf, int slot)
>>>> +{
>>>> +    struct btrfs_file_extent_item *fi;
>>>> +    u32 sectorsize = root->fs_info->sectorsize;
>>>> +    u32 item_size = btrfs_item_size_nr(leaf, slot);
>>>> +
>>>> +    fi = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item);
>>>> +
>>>> +    if (btrfs_file_extent_type(leaf, fi) >=
>>>> BTRFS_FILE_EXTENT_LAST_TYPE) {
>>>> +        CORRUPT("invalid file extent type", leaf, root, slot);
>>>> +        return -EIO;
>>>> +    }
>>>> +    if (btrfs_file_extent_compression(leaf, fi) >=
>>>> BTRFS_COMPRESS_LAST) {
>>>> +        CORRUPT("invalid file extent compression", leaf, root, slot);
>>>> +        return -EIO;
>>>> +    }
>>>> +    if (btrfs_file_extent_encryption(leaf, fi)) {
>>>> +        CORRUPT("invalid file extent encryption", leaf, root, slot);
>>>> +        return -EIO;
>>>> +    }
>>>> +    if (btrfs_file_extent_type(leaf, fi) ==
>>>> BTRFS_FILE_EXTENT_INLINE) {
>>>> +        if (btrfs_file_extent_compression(leaf, fi) !=
>>>> +            BTRFS_COMPRESS_NONE)
>>>> +            return 0;
>>>> +        /* Plaintext inline extent size must match item size */
>>>> +        if (item_size != BTRFS_FILE_EXTENT_INLINE_DATA_START +
>>>> +            btrfs_file_extent_ram_bytes(leaf, fi)) {
>>>> +            CORRUPT("plaintext inline extent has invalid size",
>>>> +                leaf, root, slot);
>>>> +            return -EIO;
>>>> +        }
>>>> +        return 0;
>>>> +    }
>>
>> One more thing - don't we really want to use -EUCLEAN rather than -EIO?
> 
> Nice suggestion.
> Since it's not really something wrong with IO routine, EUCLEAN is better.

Yeah, I'm not saying it's wrong. But my mental model for -EIO vs
-EUCLEAN should be the following:

- When we write data in case something goes wrong e should return -EIO (
we basically cover this, since we always used -EIO).

- When we read data but while performing validity checks on it (as is
the case with your patch) we should return -EUCLEAN.

Basically the FS needs to ensure that it's always feeding valid data to
disk and the only error could be -EIO. But if this same data is read
some time later and our internal checks show that the data is
inconsistent we should say so and not just -EIO.

I've mentioned this before and as a result David created the following
wiki entry:

https://btrfs.wiki.kernel.org/index.php/Project_ideas#Distinguish_EIO_and_EUCLEAN_types_of_errors

I guess we should start from somewhere :)
> 
>>
>>
>>>> +
>>>> +
>>>> +    /* regular or preallocated extent has fixed item size */
>>>> +    if (item_size != sizeof(*fi)) {
>>>> +        CORRUPT(
>>>> +        "regluar or preallocated extent data item size is invalid",
>>>> +            leaf, root, slot);
>>>> +        return -EIO;
>>>> +    }
>>>> +    if (!IS_ALIGNED(btrfs_file_extent_ram_bytes(leaf, fi),
>>>> sectorsize) ||
>>>> +        !IS_ALIGNED(btrfs_file_extent_disk_bytenr(leaf, fi),
>>>> sectorsize) ||
>>>> +        !IS_ALIGNED(btrfs_file_extent_disk_num_bytes(leaf, fi),
>>>> +            sectorsize) ||
>>>> +        !IS_ALIGNED(btrfs_file_extent_offset(leaf, fi), sectorsize) ||
>>>> +        !IS_ALIGNED(btrfs_file_extent_num_bytes(leaf, fi),
>>>> sectorsize)) {
>>>> +        CORRUPT(
>>>> +        "regular or preallocated extent data item has unaligned
>>>> value",
>>>> +            leaf, root, slot);
>>>> +        return -EIO;
>>>> +    }
>>>> +
>>>> +    return 0;
>>>> +}
>>>> +
>>>> +static int check_leaf_item(struct btrfs_root *root,
>>>> +               struct extent_buffer *leaf, int slot)
>>>> +{
>>>> +    struct btrfs_key key;
>>>> +    int ret = 0;
>>>> +
>>>> +    btrfs_item_key_to_cpu(leaf, &key, slot);
>>>
>>> nit: We already have the key in the proper format in the caller of this
>>> function. Why not just pass in the type as an argument and save a
>>> redundant call for every item in a leaf? Perhaps it's a
>>> microoptimisation but for very densely populated trees the miniature
>>> cost might build up.
> 
> Sounds valid. Considering how many times this item_key_to_cpu() get
> called in a large leaf,
> micro-optimization counts.
> 
> I'll update this in next revision.
> 
> Thanks for your review,
> Qu
> 
>>>
>>>> +    /*
>>>> +     * Considering how overcrowded the code will be inside the switch,
>>>> +     * complex verification is better to moved its own function.
>>>> +     */
>>>> +    switch (key.type) {
>>>> +    case BTRFS_EXTENT_DATA_KEY:
>>>> +        ret = check_extent_data_item(root, leaf, slot);
>>>> +        break;
>>>> +    }
>>>> +    return ret;
>>>> +}
>>>> +
>>>>   static noinline int check_leaf(struct btrfs_root *root,
>>>>                      struct extent_buffer *leaf)
>>>>   {
>>>> @@ -605,9 +682,13 @@ static noinline int check_leaf(struct
>>>> btrfs_root *root,
>>>>        * 1) key order
>>>>        * 2) item offset and size
>>>>        *    No overlap, no hole, all inside the leaf.
>>>> +     * 3) item content
>>>> +     *    If possible, do comprehensive sanity check.
>>>> +     *    NOTE: All check must only rely on the item data itself.
>>>>        */
>>>>       for (slot = 0; slot < nritems; slot++) {
>>>>           u32 item_end_expected;
>>>> +        int ret;
>>>>             btrfs_item_key_to_cpu(leaf, &key, slot);
>>>>   @@ -650,6 +731,13 @@ static noinline int check_leaf(struct
>>>> btrfs_root *root,
>>>>               return -EIO;
>>>>           }
>>>>   +        /*
>>>> +         * Check if the item size and content meets other limitation
>>>> +         */
>>>> +        ret = check_leaf_item(root, leaf, slot);
>>>> +        if (ret < 0)
>>>> +            return ret;
>>>> +
>>>>           prev_key.objectid = key.objectid;
>>>>           prev_key.type = key.type;
>>>>           prev_key.offset = key.offset;
>>>> diff --git a/include/uapi/linux/btrfs_tree.h
>>>> b/include/uapi/linux/btrfs_tree.h
>>>> index 10689e1fdf11..3aadbb74a024 100644
>>>> --- a/include/uapi/linux/btrfs_tree.h
>>>> +++ b/include/uapi/linux/btrfs_tree.h
>>>> @@ -732,6 +732,7 @@ struct btrfs_balance_item {
>>>>   #define BTRFS_FILE_EXTENT_INLINE 0
>>>>   #define BTRFS_FILE_EXTENT_REG 1
>>>>   #define BTRFS_FILE_EXTENT_PREALLOC 2
>>>> +#define BTRFS_FILE_EXTENT_LAST_TYPE    3
>>>>     struct btrfs_file_extent_item {
>>>>       /*
>>>>
>>> -- 
>>> To unsubscribe from this list: send the line "unsubscribe
>>> linux-btrfs" in
>>> the body of a message to majordomo@vger.kernel.org
>>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>>>
>> -- 
>> To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
>> the body of a message to majordomo@vger.kernel.org
>> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>>
> -- 
> To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 

Re: [PATCH 0/3] Introduce comprehensive sanity check framework and

[Nikolay Borisov]

On 22.08.2017 10:37, Qu Wenruo wrote:
> The patchset introduce a new framework to do more comprehensive (if not
> the most) sanity check when reading out a leaf.
> 
> The new sanity checker will include:
> 
> 1) Key order
>    Existing code
> 
> 2) Item boundary
>    Existing code with enhanced checker to ensure item pointer doesn't
>    overlap with item itself.
> 
> 3) Key type based sanity checker
>    Only EXTENT_DATA checker is implemented yet.
>    As each checker should go through review and tests, or it can easily
>    make a valid btrfs failed to be mounted.
>    So only one checker is implemented as an example.
> 
>    Existing checker like INODE_REF checker can be moved to this
>    framework easily, and we can centralize all existing checkers, make
>    the rest of codes more clean.
> 
> Performance wise, it's just iterating a leaf.
> And it will only get triggered when read out a leaf, cached leaf will
> not go through such checker.
> So it won't be a performance breaker.
> 
> I tested with the patchset applied on v4.13-rc6 with fstests, no
> regression is detected.
> 
> Qu Wenruo (3):
>   btrfs: Refactor check_leaf function for later expansion.
>   btrfs: Check if item pointer overlap with item itself
>   btrfs: Add sanity check for EXTENT_DATA when reading out leaf

I have one minor comment on 3/3 which I've sent separately but otherwise
this series looks good and I like the direction it's steering future
code into.

For the whole series:

Reviewed-by: Nikolay Borisov <nborisov@suse.com>

> 
>  fs/btrfs/disk-io.c              | 137 ++++++++++++++++++++++++++++++++++------
>  include/uapi/linux/btrfs_tree.h |   1 +
>  2 files changed, 119 insertions(+), 19 deletions(-)
>