* [PATCH 0/3] btrfs: tree-checker: Add extent items check
@ 2019-07-29 7:43 Qu Wenruo
2019-07-29 7:43 ` [PATCH 1/3] btrfs: tree-checker: Add EXTENT_ITEM and METADATA_ITEM check Qu Wenruo
` (2 more replies)
0 siblings, 3 replies; 6+ messages in thread
From: Qu Wenruo @ 2019-07-29 7:43 UTC (permalink / raw)
To: linux-btrfs
Finally, we are going to add tree-checker support for extent items,
which includes:
- EXTENT_ITEM/METADATA_ITEM
Which futher contains inline backrefs of:
* TREE_BLOCK_REF
* SHARED_BLOCK_REF
* EXETNT_DATA_REF
* SHARED_DATA_REF
- TREE_BLOCK_REF
- SHARED_BLOCK_REF
- EXTENT_DATA_REF
- SHARED_DATA_REF
Keyed version of the above types
The complexity of the on-disk format can be found in the first patch,
which contains a basic introduction as comment.
Hidden pitfalls are everywhere, e.g. inlined EXTENT_DATA_REF don't use
iref->offset, but put its own data at iref->offset.
But SHARED_DATA_REF uses iref->offset, and put extra data after iref.
Such on-disk layout makes sense, but definitely a mess to read.
Thankfully we at least have print-tree code from btrfs-progs as a
reference.
Qu Wenruo (3):
btrfs: tree-checker: Add EXTENT_ITEM and METADATA_ITEM check
btrfs: tree-checker: Add simple keyed refs check
btrfs: tree-checker: Add EXTENT_DATA_REF check
fs/btrfs/ctree.h | 1 +
fs/btrfs/extent-tree.c | 2 +-
fs/btrfs/tree-checker.c | 335 ++++++++++++++++++++++++++++++++++++++++
3 files changed, 337 insertions(+), 1 deletion(-)
--
2.22.0
^ permalink raw reply [flat|nested] 6+ messages in thread
* [PATCH 1/3] btrfs: tree-checker: Add EXTENT_ITEM and METADATA_ITEM check
2019-07-29 7:43 [PATCH 0/3] btrfs: tree-checker: Add extent items check Qu Wenruo
@ 2019-07-29 7:43 ` Qu Wenruo
2019-07-29 13:42 ` Nikolay Borisov
2019-07-29 7:43 ` [PATCH 2/3] btrfs: tree-checker: Add simple keyed refs check Qu Wenruo
2019-07-29 7:43 ` [PATCH 3/3] btrfs: tree-checker: Add EXTENT_DATA_REF check Qu Wenruo
2 siblings, 1 reply; 6+ messages in thread
From: Qu Wenruo @ 2019-07-29 7:43 UTC (permalink / raw)
To: linux-btrfs
This patch introduces the ability to check extent items.
This check involves:
- key->objectid check
Basic alignment check.
- key->type check
Against btrfs_extent_item::type and SKINNY_METADATA feature.
- key->offset alignment check for EXTENT_ITEM
- key->offset check for METADATA_ITEM
- item size check
Both against minimal size and stepping check.
- btrfs_extent_item check
Checks its flags and generation.
- btrfs_extent_inline_ref checks
Against 4 types inline ref.
Checks bytenr alignment and tree level.
- btrfs_extent_item::refs check
Check against total refs found in inline refs.
This check would be the most complex single item check due to its nature
of inlined items.
Signed-off-by: Qu Wenruo <wqu@suse.com>
---
fs/btrfs/tree-checker.c | 249 ++++++++++++++++++++++++++++++++++++++++
1 file changed, 249 insertions(+)
diff --git a/fs/btrfs/tree-checker.c b/fs/btrfs/tree-checker.c
index 71bbbce3076d..1e97bb127893 100644
--- a/fs/btrfs/tree-checker.c
+++ b/fs/btrfs/tree-checker.c
@@ -899,6 +899,251 @@ static int check_root_item(struct extent_buffer *leaf, struct btrfs_key *key,
return 0;
}
+__printf(3,4)
+__cold
+static void extent_err(const struct extent_buffer *eb, int slot,
+ const char *fmt, ...)
+{
+ struct btrfs_key key;
+ struct va_format vaf;
+ va_list args;
+ u64 bytenr;
+ u64 len;
+
+ btrfs_item_key_to_cpu(eb, &key, slot);
+ bytenr = key.objectid;
+ if (key.type == BTRFS_METADATA_ITEM_KEY)
+ len = eb->fs_info->nodesize;
+ else
+ len = key.offset;
+ va_start(args, fmt);
+
+ vaf.fmt = fmt;
+ vaf.va = &args;
+
+ btrfs_crit(eb->fs_info,
+ "corrupt %s: block=%llu slot=%d extent bytenr=%llu len=%llu %pV",
+ btrfs_header_level(eb) == 0 ? "leaf" : "node",
+ eb->start, slot, bytenr, len, &vaf);
+ va_end(args);
+}
+
+static int check_extent_item(struct extent_buffer *leaf,
+ struct btrfs_key *key, int slot)
+{
+ struct btrfs_fs_info *fs_info = leaf->fs_info;
+ struct btrfs_extent_item *ei;
+ bool is_tree_block = false;
+ u64 ptr; /* Current pointer inside inline refs */
+ u64 end; /* Extent item end */
+ u32 item_size = btrfs_item_size_nr(leaf, slot);
+ u64 flags;
+ u64 generation;
+ u64 total_refs; /* Total refs in btrfs_extent_item */
+ u64 inline_refs = 0; /* found total inline refs */
+
+ if (key->type == BTRFS_METADATA_ITEM_KEY &&
+ !btrfs_fs_incompat(fs_info, SKINNY_METADATA)) {
+ generic_err(leaf, slot,
+"invalid key type, METADATA_ITEM type invalid when SKINNY_METADATA feature disabled");
+ return -EUCLEAN;
+ }
+ /* key->objectid is the bytenr for both key types */
+ if (!IS_ALIGNED(key->objectid, fs_info->sectorsize)) {
+ generic_err(leaf, slot,
+"invalid key objectid, have %llu expect to be aligned to %u",
+ key->objectid, fs_info->sectorsize);
+ return -EUCLEAN;
+ }
+
+ /* key->offset is tree level for METADATA_ITEM_KEY */
+ if (key->type == BTRFS_METADATA_ITEM_KEY) {
+ if (key->offset >= BTRFS_MAX_LEVEL) {
+ extent_err(leaf, slot,
+ "invalid tree level, have %llu expect [0, %u]",
+ key->offset, BTRFS_MAX_LEVEL - 1);
+ return -EUCLEAN;
+ }
+ }
+
+ /*
+ * EXTENT/METADATA_ITEM is consistent of:
+ * 1) One btrfs_extent_item
+ * Records the total refs, type and generation of the extent.
+ *
+ * 2) One btrfs_tree_block_info (for EXTENT_ITEM and tree backref only)
+ * Records the first key and level of the tree block.
+ *
+ * 2) *Zero* or more btrfs_extent_inline_ref(s)
+ * Each inline ref has one btrfs_extent_inline_ref shows:
+ * 2.1) The ref type, one of the 4
+ * TREE_BLOCK_REF Tree block only
+ * SHARED_BLOCK_REF Tree block only
+ * EXTENT_DATA_REF Data only
+ * SHARED_DATA_REF Data only
+ * 2.2) Ref type specific data
+ * Either using btrfs_extent_inline_ref::offset, or specific
+ * data structure.
+ */
+ if (item_size < sizeof(*ei)) {
+ extent_err(leaf, slot,
+ "invalid item size, have %u expect >= %lu",
+ item_size, sizeof(*ei));
+ return -EUCLEAN;
+ }
+ end = item_size + btrfs_item_ptr_offset(leaf, slot);
+
+ /* Checks against extent_item */
+ ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
+ flags = btrfs_extent_flags(leaf, ei);
+ total_refs = btrfs_extent_refs(leaf, ei);
+ generation = btrfs_extent_generation(leaf, ei);
+ if (generation > btrfs_super_generation(fs_info->super_copy) + 1) {
+ extent_err(leaf, slot,
+ "invalid generation, have %llu expect <= %llu",
+ generation,
+ btrfs_super_generation(fs_info->super_copy) + 1);
+ return -EUCLEAN;
+ }
+ if (!is_power_of_2(flags & (BTRFS_EXTENT_FLAG_DATA |
+ BTRFS_EXTENT_FLAG_TREE_BLOCK))) {
+ extent_err(leaf, slot,
+ "invalid extent flag, have 0x%llx expect 1 bit set in 0x%llx",
+ flags, BTRFS_EXTENT_FLAG_DATA |
+ BTRFS_EXTENT_FLAG_TREE_BLOCK);
+ return -EUCLEAN;
+ }
+ is_tree_block = !!(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK);
+ if (is_tree_block && key->type == BTRFS_EXTENT_ITEM_KEY &&
+ key->offset != fs_info->nodesize) {
+ extent_err(leaf, slot,
+ "invalid extent length, have %llu expect %u",
+ key->offset, fs_info->nodesize);
+ return -EUCLEAN;
+ }
+ if (!is_tree_block) {
+ if (key->type != BTRFS_EXTENT_ITEM_KEY) {
+ extent_err(leaf, slot,
+ "invalid key type, have %u expect %u for data backref",
+ key->type, BTRFS_EXTENT_ITEM_KEY);
+ return -EUCLEAN;
+ }
+ if (!IS_ALIGNED(key->offset, fs_info->sectorsize)) {
+ extent_err(leaf, slot,
+ "invalid extent length, have %llu expect aliged to %u",
+ key->offset, fs_info->sectorsize);
+ return -EUCLEAN;
+ }
+ }
+ ptr = (u64)(struct btrfs_extent_item *)(ei + 1);
+
+ /* Check the special case of btrfs_tree_block_info */
+ if (is_tree_block && key->type != BTRFS_METADATA_ITEM_KEY) {
+ struct btrfs_tree_block_info *info;
+
+ info = (struct btrfs_tree_block_info *)ptr;
+ if (btrfs_tree_block_level(leaf, info) >= BTRFS_MAX_LEVEL) {
+ extent_err(leaf, slot,
+ "invalid tree block info level, have %u expect [0, %u)",
+ btrfs_tree_block_level(leaf, info),
+ BTRFS_MAX_LEVEL - 1);
+ return -EUCLEAN;
+ }
+ ptr = (u64)(struct btrfs_tree_block_info *)(info + 1);
+ }
+
+ /* Check inline refs */
+ while (ptr < end) {
+ struct btrfs_extent_inline_ref *iref;
+ struct btrfs_extent_data_ref *dref;
+ struct btrfs_shared_data_ref *sref;
+ u64 dref_offset;
+ u64 inline_offset;
+ u8 inline_type;
+
+ if (ptr + sizeof(*iref) > end) {
+ extent_err(leaf, slot,
+ "invalid item size, size too small, ptr %llu end %llu",
+ ptr, end);
+ goto err;
+ }
+ iref = (struct btrfs_extent_inline_ref *)ptr;
+ inline_type = btrfs_extent_inline_ref_type(leaf, iref);
+ inline_offset = btrfs_extent_inline_ref_offset(leaf, iref);
+ if (ptr + btrfs_extent_inline_ref_size(inline_type) > end) {
+ extent_err(leaf, slot,
+ "invalid item size, size too small, ptr %llu end %llu",
+ ptr, end);
+ goto err;
+ }
+
+ switch (inline_type) {
+ /* inline_offset is subvolid of the owner, no need to check */
+ case BTRFS_TREE_BLOCK_REF_KEY:
+ inline_refs++;
+ break;
+ /* contains parent bytenr */
+ case BTRFS_SHARED_BLOCK_REF_KEY:
+ if (!IS_ALIGNED(inline_offset, fs_info->sectorsize)) {
+ extent_err(leaf, slot,
+ "invalid tree parent bytenr, have %llu expect aligned to %u",
+ inline_offset, fs_info->sectorsize);
+ goto err;
+ }
+ inline_refs++;
+ break;
+ /*
+ * contains owner subvolid, owner key objectid, adjusted offset.
+ * the only obvious corruption can happen in that offset.
+ */
+ case BTRFS_EXTENT_DATA_REF_KEY:
+ dref = (struct btrfs_extent_data_ref *)(&iref->offset);
+ dref_offset = btrfs_extent_data_ref_offset(leaf, dref);
+ if (!IS_ALIGNED(dref_offset, fs_info->sectorsize)) {
+ extent_err(leaf, slot,
+ "invalid data ref offset, have %llu expect aligned to %u",
+ dref_offset, fs_info->sectorsize);
+ goto err;
+ }
+ inline_refs += btrfs_extent_data_ref_count(leaf, dref);
+ break;
+ /* contains parent bytenr and ref count */
+ case BTRFS_SHARED_DATA_REF_KEY:
+ sref = (struct btrfs_shared_data_ref *)(iref + 1);
+ if (!IS_ALIGNED(inline_offset, fs_info->sectorsize)) {
+ extent_err(leaf, slot,
+ "invalid data parent bytenr, have %llu expect aligned to %u",
+ inline_offset, fs_info->sectorsize);
+ goto err;
+ }
+ inline_refs += btrfs_shared_data_ref_count(leaf, sref);
+ break;
+ default:
+ extent_err(leaf, slot, "unknown inline ref type: %u",
+ inline_type);
+ goto err;
+ }
+ ptr += btrfs_extent_inline_ref_size(inline_type);
+ }
+ /* No padding is allowed */
+ if (ptr != end) {
+ extent_err(leaf, slot,
+ "invalid extent item size, padding bytes found");
+ goto err;
+ }
+
+ /* Finally, check the inline refs against total refs */
+ if (total_refs < inline_refs) {
+ extent_err(leaf, slot,
+ "invalid extent refs, have %llu expect >= %llu",
+ total_refs, inline_refs);
+ goto err;
+ }
+ return 0;
+err:
+ return -EUCLEAN;
+}
+
/*
* Common point to switch the item-specific validation.
*/
@@ -937,6 +1182,10 @@ static int check_leaf_item(struct extent_buffer *leaf,
case BTRFS_ROOT_ITEM_KEY:
ret = check_root_item(leaf, key, slot);
break;
+ case BTRFS_EXTENT_ITEM_KEY:
+ case BTRFS_METADATA_ITEM_KEY:
+ ret = check_extent_item(leaf, key, slot);
+ break;
}
return ret;
}
--
2.22.0
^ permalink raw reply related [flat|nested] 6+ messages in thread
* [PATCH 2/3] btrfs: tree-checker: Add simple keyed refs check
2019-07-29 7:43 [PATCH 0/3] btrfs: tree-checker: Add extent items check Qu Wenruo
2019-07-29 7:43 ` [PATCH 1/3] btrfs: tree-checker: Add EXTENT_ITEM and METADATA_ITEM check Qu Wenruo
@ 2019-07-29 7:43 ` Qu Wenruo
2019-07-29 7:43 ` [PATCH 3/3] btrfs: tree-checker: Add EXTENT_DATA_REF check Qu Wenruo
2 siblings, 0 replies; 6+ messages in thread
From: Qu Wenruo @ 2019-07-29 7:43 UTC (permalink / raw)
To: linux-btrfs
For TREE_BLOCK_REF, SHARED_DATA_REF and SHARED_BLOCK_REF we need to
check:
| TREE_BLOCK_REF | SHARED_BLOCK_REF | SHARED_BLOCK_REF
--------------+----------------+-----------------+------------------
key->objectid | Alignment | Alignment | Alignment
key->offset | Any value | Alignment | Alignment
item_size | 0 | 0 | sizeof(le32) (*)
*: sizeof(struct btrfs_shared_data_ref)
So introduce a check to check all these 3 key types together.
Signed-off-by: Qu Wenruo <wqu@suse.com>
---
fs/btrfs/tree-checker.c | 40 +++++++++++++++++++++++++++++++++++++++-
1 file changed, 39 insertions(+), 1 deletion(-)
diff --git a/fs/btrfs/tree-checker.c b/fs/btrfs/tree-checker.c
index 1e97bb127893..6ef174c7fb05 100644
--- a/fs/btrfs/tree-checker.c
+++ b/fs/btrfs/tree-checker.c
@@ -912,7 +912,9 @@ static void extent_err(const struct extent_buffer *eb, int slot,
btrfs_item_key_to_cpu(eb, &key, slot);
bytenr = key.objectid;
- if (key.type == BTRFS_METADATA_ITEM_KEY)
+ if (key.type == BTRFS_METADATA_ITEM_KEY ||
+ key.type == BTRFS_TREE_BLOCK_REF_KEY ||
+ key.type == BTRFS_SHARED_BLOCK_REF_KEY)
len = eb->fs_info->nodesize;
else
len = key.offset;
@@ -1144,6 +1146,37 @@ static int check_extent_item(struct extent_buffer *leaf,
return -EUCLEAN;
}
+static int check_simple_keyed_refs(struct extent_buffer *leaf,
+ struct btrfs_key *key, int slot)
+{
+ u32 expect_item_size = 0;
+
+ if (key->type == BTRFS_SHARED_DATA_REF_KEY)
+ expect_item_size = sizeof(struct btrfs_shared_data_ref);
+
+ if (btrfs_item_size_nr(leaf, slot) != expect_item_size) {
+ generic_err(leaf, slot,
+ "invalid item size, have %u expect %u for key type %u",
+ btrfs_item_size_nr(leaf, slot),
+ expect_item_size, key->type);
+ return -EUCLEAN;
+ }
+ if (!IS_ALIGNED(key->objectid, leaf->fs_info->sectorsize)) {
+ generic_err(leaf, slot,
+"invalid key objectid for shared block ref, have %llu expect aligned to %u",
+ key->objectid, leaf->fs_info->sectorsize);
+ return -EUCLEAN;
+ }
+ if (key->type != BTRFS_TREE_BLOCK_REF_KEY &&
+ !IS_ALIGNED(key->offset, leaf->fs_info->sectorsize)) {
+ extent_err(leaf, slot,
+ "invalid tree parent bytenr, have %llu expect aligned to %u",
+ key->offset, leaf->fs_info->sectorsize);
+ return -EUCLEAN;
+ }
+ return 0;
+}
+
/*
* Common point to switch the item-specific validation.
*/
@@ -1186,6 +1219,11 @@ static int check_leaf_item(struct extent_buffer *leaf,
case BTRFS_METADATA_ITEM_KEY:
ret = check_extent_item(leaf, key, slot);
break;
+ case BTRFS_TREE_BLOCK_REF_KEY:
+ case BTRFS_SHARED_DATA_REF_KEY:
+ case BTRFS_SHARED_BLOCK_REF_KEY:
+ ret = check_simple_keyed_refs(leaf, key, slot);
+ break;
}
return ret;
}
--
2.22.0
^ permalink raw reply related [flat|nested] 6+ messages in thread
* [PATCH 3/3] btrfs: tree-checker: Add EXTENT_DATA_REF check
2019-07-29 7:43 [PATCH 0/3] btrfs: tree-checker: Add extent items check Qu Wenruo
2019-07-29 7:43 ` [PATCH 1/3] btrfs: tree-checker: Add EXTENT_ITEM and METADATA_ITEM check Qu Wenruo
2019-07-29 7:43 ` [PATCH 2/3] btrfs: tree-checker: Add simple keyed refs check Qu Wenruo
@ 2019-07-29 7:43 ` Qu Wenruo
2 siblings, 0 replies; 6+ messages in thread
From: Qu Wenruo @ 2019-07-29 7:43 UTC (permalink / raw)
To: linux-btrfs
EXTENT_DATA_REF is a little like DIR_ITEM which contains hash in its
key->offset.
This patch will check the following contents:
- Key->objectid
Basic alignment check.
- Hash
Hash of each extent_data_ref item must match key->offset.
- Offset
Basic alignment check.
Signed-off-by: Qu Wenruo <wqu@suse.com>
---
fs/btrfs/ctree.h | 1 +
fs/btrfs/extent-tree.c | 2 +-
fs/btrfs/tree-checker.c | 48 +++++++++++++++++++++++++++++++++++++++++
3 files changed, 50 insertions(+), 1 deletion(-)
diff --git a/fs/btrfs/ctree.h b/fs/btrfs/ctree.h
index 0a61dff27f57..710ea3a6608c 100644
--- a/fs/btrfs/ctree.h
+++ b/fs/btrfs/ctree.h
@@ -2679,6 +2679,7 @@ enum btrfs_inline_ref_type {
int btrfs_get_extent_inline_ref_type(const struct extent_buffer *eb,
struct btrfs_extent_inline_ref *iref,
enum btrfs_inline_ref_type is_data);
+u64 hash_extent_data_ref(u64 root_objectid, u64 owner, u64 offset);
u64 btrfs_csum_bytes_to_leaves(struct btrfs_fs_info *fs_info, u64 csum_bytes);
diff --git a/fs/btrfs/extent-tree.c b/fs/btrfs/extent-tree.c
index b4e9e36b65f1..c0888ed503df 100644
--- a/fs/btrfs/extent-tree.c
+++ b/fs/btrfs/extent-tree.c
@@ -1114,7 +1114,7 @@ int btrfs_get_extent_inline_ref_type(const struct extent_buffer *eb,
return BTRFS_REF_TYPE_INVALID;
}
-static u64 hash_extent_data_ref(u64 root_objectid, u64 owner, u64 offset)
+u64 hash_extent_data_ref(u64 root_objectid, u64 owner, u64 offset)
{
u32 high_crc = ~(u32)0;
u32 low_crc = ~(u32)0;
diff --git a/fs/btrfs/tree-checker.c b/fs/btrfs/tree-checker.c
index 6ef174c7fb05..115725f742c2 100644
--- a/fs/btrfs/tree-checker.c
+++ b/fs/btrfs/tree-checker.c
@@ -1177,6 +1177,51 @@ static int check_simple_keyed_refs(struct extent_buffer *leaf,
return 0;
}
+static int check_extent_data_ref(struct extent_buffer *leaf,
+ struct btrfs_key *key, int slot)
+{
+ struct btrfs_extent_data_ref *dref;
+ u64 ptr = btrfs_item_ptr_offset(leaf, slot);
+ u64 end = ptr + btrfs_item_size_nr(leaf, slot);
+
+ if (btrfs_item_size_nr(leaf, slot) % sizeof(*dref) != 0) {
+ generic_err(leaf, slot,
+ "invalid item size, have %u expect aligned to %lu for key type %u",
+ btrfs_item_size_nr(leaf, slot),
+ sizeof(*dref), key->type);
+ }
+ if (!IS_ALIGNED(key->objectid, leaf->fs_info->sectorsize)) {
+ generic_err(leaf, slot,
+"invalid key objectid for shared block ref, have %llu expect aligned to %u",
+ key->objectid, leaf->fs_info->sectorsize);
+ return -EUCLEAN;
+ }
+ for (; ptr < end; ptr += sizeof(*dref)) {
+ u64 root_objectid;
+ u64 owner;
+ u64 offset;
+ u64 hash;
+
+ dref = (struct btrfs_extent_data_ref *)ptr;
+ root_objectid = btrfs_extent_data_ref_root(leaf, dref);
+ owner = btrfs_extent_data_ref_objectid(leaf, dref);
+ offset = btrfs_extent_data_ref_offset(leaf, dref);
+ hash = hash_extent_data_ref(root_objectid, owner, offset);
+ if (hash != key->offset) {
+ extent_err(leaf, slot,
+ "invalid extent data ref hash, item have 0x%016llx key have 0x%016llx",
+ hash, key->offset);
+ return -EUCLEAN;
+ }
+ if (!IS_ALIGNED(offset, leaf->fs_info->sectorsize)) {
+ extent_err(leaf, slot,
+ "invalid extent data backref offset, have %llu expect aligned to %u",
+ offset, leaf->fs_info->sectorsize);
+ }
+ }
+ return 0;
+}
+
/*
* Common point to switch the item-specific validation.
*/
@@ -1224,6 +1269,9 @@ static int check_leaf_item(struct extent_buffer *leaf,
case BTRFS_SHARED_BLOCK_REF_KEY:
ret = check_simple_keyed_refs(leaf, key, slot);
break;
+ case BTRFS_EXTENT_DATA_REF_KEY:
+ ret = check_extent_data_ref(leaf, key, slot);
+ break;
}
return ret;
}
--
2.22.0
^ permalink raw reply related [flat|nested] 6+ messages in thread
* Re: [PATCH 1/3] btrfs: tree-checker: Add EXTENT_ITEM and METADATA_ITEM check
2019-07-29 7:43 ` [PATCH 1/3] btrfs: tree-checker: Add EXTENT_ITEM and METADATA_ITEM check Qu Wenruo
@ 2019-07-29 13:42 ` Nikolay Borisov
2019-07-29 13:53 ` Qu Wenruo
0 siblings, 1 reply; 6+ messages in thread
From: Nikolay Borisov @ 2019-07-29 13:42 UTC (permalink / raw)
To: Qu Wenruo, linux-btrfs
On 29.07.19 г. 10:43 ч., Qu Wenruo wrote:
> This patch introduces the ability to check extent items.
>
> This check involves:
> - key->objectid check
> Basic alignment check.
>
> - key->type check
> Against btrfs_extent_item::type and SKINNY_METADATA feature.
>
> - key->offset alignment check for EXTENT_ITEM
>
> - key->offset check for METADATA_ITEM
>
> - item size check
> Both against minimal size and stepping check.
>
> - btrfs_extent_item check
> Checks its flags and generation.
>
> - btrfs_extent_inline_ref checks
> Against 4 types inline ref.
> Checks bytenr alignment and tree level.
>
> - btrfs_extent_item::refs check
> Check against total refs found in inline refs.
>
> This check would be the most complex single item check due to its nature
> of inlined items.
>
> Signed-off-by: Qu Wenruo <wqu@suse.com>
> ---
> fs/btrfs/tree-checker.c | 249 ++++++++++++++++++++++++++++++++++++++++
> 1 file changed, 249 insertions(+)
>
> diff --git a/fs/btrfs/tree-checker.c b/fs/btrfs/tree-checker.c
> index 71bbbce3076d..1e97bb127893 100644
> --- a/fs/btrfs/tree-checker.c
> +++ b/fs/btrfs/tree-checker.c
> @@ -899,6 +899,251 @@ static int check_root_item(struct extent_buffer *leaf, struct btrfs_key *key,
> return 0;
> }
>
> +__printf(3,4)
> +__cold
> +static void extent_err(const struct extent_buffer *eb, int slot,
> + const char *fmt, ...)
> +{
> + struct btrfs_key key;
> + struct va_format vaf;
> + va_list args;
> + u64 bytenr;
> + u64 len;
> +
> + btrfs_item_key_to_cpu(eb, &key, slot);
> + bytenr = key.objectid;
> + if (key.type == BTRFS_METADATA_ITEM_KEY)
> + len = eb->fs_info->nodesize;
> + else
> + len = key.offset;
> + va_start(args, fmt);
> +
> + vaf.fmt = fmt;
> + vaf.va = &args;
> +
> + btrfs_crit(eb->fs_info,
> + "corrupt %s: block=%llu slot=%d extent bytenr=%llu len=%llu %pV",
> + btrfs_header_level(eb) == 0 ? "leaf" : "node",
> + eb->start, slot, bytenr, len, &vaf);
> + va_end(args);
> +}
> +
> +static int check_extent_item(struct extent_buffer *leaf,
> + struct btrfs_key *key, int slot)
> +{
> + struct btrfs_fs_info *fs_info = leaf->fs_info;
> + struct btrfs_extent_item *ei;
> + bool is_tree_block = false;
> + u64 ptr; /* Current pointer inside inline refs */
> + u64 end; /* Extent item end */
> + u32 item_size = btrfs_item_size_nr(leaf, slot);
> + u64 flags;
> + u64 generation;
> + u64 total_refs; /* Total refs in btrfs_extent_item */
> + u64 inline_refs = 0; /* found total inline refs */
> +
> + if (key->type == BTRFS_METADATA_ITEM_KEY &&
> + !btrfs_fs_incompat(fs_info, SKINNY_METADATA)) {
> + generic_err(leaf, slot,
> +"invalid key type, METADATA_ITEM type invalid when SKINNY_METADATA feature disabled");
> + return -EUCLEAN;
> + }
> + /* key->objectid is the bytenr for both key types */
> + if (!IS_ALIGNED(key->objectid, fs_info->sectorsize)) {
> + generic_err(leaf, slot,
> +"invalid key objectid, have %llu expect to be aligned to %u",
> + key->objectid, fs_info->sectorsize);
> + return -EUCLEAN;
> + }
> +
> + /* key->offset is tree level for METADATA_ITEM_KEY */
> + if (key->type == BTRFS_METADATA_ITEM_KEY) {
> + if (key->offset >= BTRFS_MAX_LEVEL) {
make it a compound statement:
if key->type && key->offset. The extra if doesn't bring anything...
> + extent_err(leaf, slot,
> + "invalid tree level, have %llu expect [0, %u]",
> + key->offset, BTRFS_MAX_LEVEL - 1);
> + return -EUCLEAN;
> + }
> + }
> +
> + /*
> + * EXTENT/METADATA_ITEM is consistent of:
> + * 1) One btrfs_extent_item
> + * Records the total refs, type and generation of the extent.
> + *
> + * 2) One btrfs_tree_block_info (for EXTENT_ITEM and tree backref only)
> + * Records the first key and level of the tree block.
> + *
> + * 2) *Zero* or more btrfs_extent_inline_ref(s)
> + * Each inline ref has one btrfs_extent_inline_ref shows:
> + * 2.1) The ref type, one of the 4
> + * TREE_BLOCK_REF Tree block only
> + * SHARED_BLOCK_REF Tree block only
> + * EXTENT_DATA_REF Data only
> + * SHARED_DATA_REF Data only
> + * 2.2) Ref type specific data
> + * Either using btrfs_extent_inline_ref::offset, or specific
> + * data structure.
> + */
> + if (item_size < sizeof(*ei)) {
> + extent_err(leaf, slot,
> + "invalid item size, have %u expect >= %lu",
> + item_size, sizeof(*ei));
> + return -EUCLEAN;
> + }
> + end = item_size + btrfs_item_ptr_offset(leaf, slot);
> +
> + /* Checks against extent_item */
> + ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
> + flags = btrfs_extent_flags(leaf, ei);
> + total_refs = btrfs_extent_refs(leaf, ei);
> + generation = btrfs_extent_generation(leaf, ei);
> + if (generation > btrfs_super_generation(fs_info->super_copy) + 1) {
> + extent_err(leaf, slot,
> + "invalid generation, have %llu expect <= %llu",
nit: I find the '<= [number]' somewhat confusing, wouldn't it be better
if it's spelled our e.g 'expecting less than or equal than [number]'.
Might be just me.
> + generation,
> + btrfs_super_generation(fs_info->super_copy) + 1);
> + return -EUCLEAN;
> + }
> + if (!is_power_of_2(flags & (BTRFS_EXTENT_FLAG_DATA |
> + BTRFS_EXTENT_FLAG_TREE_BLOCK))) {
> + extent_err(leaf, slot,
> + "invalid extent flag, have 0x%llx expect 1 bit set in 0x%llx",
> + flags, BTRFS_EXTENT_FLAG_DATA |
> + BTRFS_EXTENT_FLAG_TREE_BLOCK);
> + return -EUCLEAN;
> + }
> + is_tree_block = !!(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK);
> + if (is_tree_block && key->type == BTRFS_EXTENT_ITEM_KEY &&
> + key->offset != fs_info->nodesize) {
> + extent_err(leaf, slot,
> + "invalid extent length, have %llu expect %u",
> + key->offset, fs_info->nodesize);
> + return -EUCLEAN;
> + }
> + if (!is_tree_block) {
> + if (key->type != BTRFS_EXTENT_ITEM_KEY) {
> + extent_err(leaf, slot,
> + "invalid key type, have %u expect %u for data backref",
> + key->type, BTRFS_EXTENT_ITEM_KEY);
> + return -EUCLEAN;
> + }
> + if (!IS_ALIGNED(key->offset, fs_info->sectorsize)) {
> + extent_err(leaf, slot,
> + "invalid extent length, have %llu expect aliged to %u",
> + key->offset, fs_info->sectorsize);
> + return -EUCLEAN;
> + }
> + }
unify the two is_tree_block/!is_tree_block either in:
if (is_tree_block) {
if (keypt->type = EXTENT_ITEM_KEY && offset != nodesize {
foo;
}
} else {
bar;
}
or
if (is_tree_block && key->type == BTRFS_EXTENT_ITEM_KEY ..) {
} else if (!is_tree_block) {
bar
}
> + ptr = (u64)(struct btrfs_extent_item *)(ei + 1);
> +
> + /* Check the special case of btrfs_tree_block_info */
> + if (is_tree_block && key->type != BTRFS_METADATA_ITEM_KEY) {
> + struct btrfs_tree_block_info *info;
> +
> + info = (struct btrfs_tree_block_info *)ptr;
> + if (btrfs_tree_block_level(leaf, info) >= BTRFS_MAX_LEVEL) {
> + extent_err(leaf, slot,
> + "invalid tree block info level, have %u expect [0, %u)",
nit: Strictly speaking using [0, 7) is wrong, because ')' already
implies an open interval. Since we have 8 levels 0/7 inclusive this
means the correct way to print it would be [0, 7] or [0, 8).
> + btrfs_tree_block_level(leaf, info),
> + BTRFS_MAX_LEVEL - 1);
> + return -EUCLEAN;
> + }
> + ptr = (u64)(struct btrfs_tree_block_info *)(info + 1);
> + }
> +
> + /* Check inline refs */
> + while (ptr < end) {
> + struct btrfs_extent_inline_ref *iref;
> + struct btrfs_extent_data_ref *dref;
> + struct btrfs_shared_data_ref *sref;
> + u64 dref_offset;
> + u64 inline_offset;
> + u8 inline_type;
> +
> + if (ptr + sizeof(*iref) > end) {
> + extent_err(leaf, slot,
> + "invalid item size, size too small, ptr %llu end %llu",
> + ptr, end);
> + goto err;
> + }
> + iref = (struct btrfs_extent_inline_ref *)ptr;
> + inline_type = btrfs_extent_inline_ref_type(leaf, iref);
> + inline_offset = btrfs_extent_inline_ref_offset(leaf, iref);
> + if (ptr + btrfs_extent_inline_ref_size(inline_type) > end) {
> + extent_err(leaf, slot,
> + "invalid item size, size too small, ptr %llu end %llu",
Make that text explicit:
"inline ref item overflows extent item" or some such.
> + ptr, end);
> + goto err;
> + }
> +
> + switch (inline_type) {
> + /* inline_offset is subvolid of the owner, no need to check */
> + case BTRFS_TREE_BLOCK_REF_KEY:
> + inline_refs++;
> + break;
> + /* contains parent bytenr */
> + case BTRFS_SHARED_BLOCK_REF_KEY:
> + if (!IS_ALIGNED(inline_offset, fs_info->sectorsize)) {
> + extent_err(leaf, slot,
> + "invalid tree parent bytenr, have %llu expect aligned to %u",
> + inline_offset, fs_info->sectorsize);
> + goto err;
> + }
> + inline_refs++;
> + break;
> + /*
> + * contains owner subvolid, owner key objectid, adjusted offset.
> + * the only obvious corruption can happen in that offset.
> + */
> + case BTRFS_EXTENT_DATA_REF_KEY:
> + dref = (struct btrfs_extent_data_ref *)(&iref->offset);
> + dref_offset = btrfs_extent_data_ref_offset(leaf, dref);
> + if (!IS_ALIGNED(dref_offset, fs_info->sectorsize)) {
> + extent_err(leaf, slot,
> + "invalid data ref offset, have %llu expect aligned to %u",
> + dref_offset, fs_info->sectorsize);
> + goto err;
> + }
> + inline_refs += btrfs_extent_data_ref_count(leaf, dref);
> + break;
> + /* contains parent bytenr and ref count */
> + case BTRFS_SHARED_DATA_REF_KEY:
> + sref = (struct btrfs_shared_data_ref *)(iref + 1);
> + if (!IS_ALIGNED(inline_offset, fs_info->sectorsize)) {
> + extent_err(leaf, slot,
> + "invalid data parent bytenr, have %llu expect aligned to %u",
> + inline_offset, fs_info->sectorsize);
> + goto err;
> + }
> + inline_refs += btrfs_shared_data_ref_count(leaf, sref);
> + break;
> + default:
> + extent_err(leaf, slot, "unknown inline ref type: %u",
> + inline_type);
> + goto err;
> + }
> + ptr += btrfs_extent_inline_ref_size(inline_type);
> + }
> + /* No padding is allowed */
> + if (ptr != end) {
> + extent_err(leaf, slot,
> + "invalid extent item size, padding bytes found");
> + goto err;
> + }
> +
> + /* Finally, check the inline refs against total refs */
> + if (total_refs < inline_refs) {
nit: if (inline_refs > total_refs) {} looks saner to me.
> + extent_err(leaf, slot,
> + "invalid extent refs, have %llu expect >= %llu",
> + total_refs, inline_refs);
> + goto err;
> + }
> + return 0;
> +err:
> + return -EUCLEAN;
> +}
> +
> /*
> * Common point to switch the item-specific validation.
> */
> @@ -937,6 +1182,10 @@ static int check_leaf_item(struct extent_buffer *leaf,
> case BTRFS_ROOT_ITEM_KEY:
> ret = check_root_item(leaf, key, slot);
> break;
> + case BTRFS_EXTENT_ITEM_KEY:
> + case BTRFS_METADATA_ITEM_KEY:
> + ret = check_extent_item(leaf, key, slot);
> + break;
> }
> return ret;
> }
>
^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH 1/3] btrfs: tree-checker: Add EXTENT_ITEM and METADATA_ITEM check
2019-07-29 13:42 ` Nikolay Borisov
@ 2019-07-29 13:53 ` Qu Wenruo
0 siblings, 0 replies; 6+ messages in thread
From: Qu Wenruo @ 2019-07-29 13:53 UTC (permalink / raw)
To: Nikolay Borisov, Qu Wenruo, linux-btrfs
On 2019/7/29 下午9:42, Nikolay Borisov wrote:
[...]
>> +
>> + /* key->offset is tree level for METADATA_ITEM_KEY */
>> + if (key->type == BTRFS_METADATA_ITEM_KEY) {
>> + if (key->offset >= BTRFS_MAX_LEVEL) {
>
> make it a compound statement:
>
> if key->type && key->offset. The extra if doesn't bring anything...
Right, that's the case.
I though there would be more checks, but turns out there is only one check.
>
>> + extent_err(leaf, slot,
>> + "invalid tree level, have %llu expect [0, %u]",
>> + key->offset, BTRFS_MAX_LEVEL - 1);
>> + return -EUCLEAN;
>> + }
>> + }
>> +
>> + /*
>> + * EXTENT/METADATA_ITEM is consistent of:
>> + * 1) One btrfs_extent_item
>> + * Records the total refs, type and generation of the extent.
>> + *
>> + * 2) One btrfs_tree_block_info (for EXTENT_ITEM and tree backref only)
>> + * Records the first key and level of the tree block.
>> + *
>> + * 2) *Zero* or more btrfs_extent_inline_ref(s)
>> + * Each inline ref has one btrfs_extent_inline_ref shows:
>> + * 2.1) The ref type, one of the 4
>> + * TREE_BLOCK_REF Tree block only
>> + * SHARED_BLOCK_REF Tree block only
>> + * EXTENT_DATA_REF Data only
>> + * SHARED_DATA_REF Data only
>> + * 2.2) Ref type specific data
>> + * Either using btrfs_extent_inline_ref::offset, or specific
>> + * data structure.
>> + */
>> + if (item_size < sizeof(*ei)) {
>> + extent_err(leaf, slot,
>> + "invalid item size, have %u expect >= %lu",
>> + item_size, sizeof(*ei));
>> + return -EUCLEAN;
>> + }
>> + end = item_size + btrfs_item_ptr_offset(leaf, slot);
>> +
>> + /* Checks against extent_item */
>> + ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
>> + flags = btrfs_extent_flags(leaf, ei);
>> + total_refs = btrfs_extent_refs(leaf, ei);
>> + generation = btrfs_extent_generation(leaf, ei);
>> + if (generation > btrfs_super_generation(fs_info->super_copy) + 1) {
>> + extent_err(leaf, slot,
>> + "invalid generation, have %llu expect <= %llu",
>
> nit: I find the '<= [number]' somewhat confusing, wouldn't it be better
> if it's spelled our e.g 'expecting less than or equal than [number]'.
> Might be just me.
I normally prefer the "[start, end]" notion, but sometimes even myself
can't always keep the format the same.
Furthermore, I can't find a minimal value to use [start, end] notion.
Maybe (0, end] would be more suitable here?
>
>> + generation,
>> + btrfs_super_generation(fs_info->super_copy) + 1);
>> + return -EUCLEAN;
>> + }
>> + if (!is_power_of_2(flags & (BTRFS_EXTENT_FLAG_DATA |
>> + BTRFS_EXTENT_FLAG_TREE_BLOCK))) {
>> + extent_err(leaf, slot,
>> + "invalid extent flag, have 0x%llx expect 1 bit set in 0x%llx",
>> + flags, BTRFS_EXTENT_FLAG_DATA |
>> + BTRFS_EXTENT_FLAG_TREE_BLOCK);
>> + return -EUCLEAN;
>> + }
>> + is_tree_block = !!(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK);
>> + if (is_tree_block && key->type == BTRFS_EXTENT_ITEM_KEY &&
>> + key->offset != fs_info->nodesize) {
>> + extent_err(leaf, slot,
>> + "invalid extent length, have %llu expect %u",
>> + key->offset, fs_info->nodesize);
>> + return -EUCLEAN;
>> + }
>> + if (!is_tree_block) {
>> + if (key->type != BTRFS_EXTENT_ITEM_KEY) {
>> + extent_err(leaf, slot,
>> + "invalid key type, have %u expect %u for data backref",
>> + key->type, BTRFS_EXTENT_ITEM_KEY);
>> + return -EUCLEAN;
>> + }
>> + if (!IS_ALIGNED(key->offset, fs_info->sectorsize)) {
>> + extent_err(leaf, slot,
>> + "invalid extent length, have %llu expect aliged to %u",
>> + key->offset, fs_info->sectorsize);
>> + return -EUCLEAN;
>> + }
>> + }
>
> unify the two is_tree_block/!is_tree_block either in:
>
> if (is_tree_block) {
> if (keypt->type = EXTENT_ITEM_KEY && offset != nodesize {
> foo;
> }
> } else {
> bar;
> }
>
Right, that's better.
> or
>
> if (is_tree_block && key->type == BTRFS_EXTENT_ITEM_KEY ..) {
>
> } else if (!is_tree_block) {
> bar
> }
>
>> + ptr = (u64)(struct btrfs_extent_item *)(ei + 1);
>> +
>> + /* Check the special case of btrfs_tree_block_info */
>> + if (is_tree_block && key->type != BTRFS_METADATA_ITEM_KEY) {
>> + struct btrfs_tree_block_info *info;
>> +
>> + info = (struct btrfs_tree_block_info *)ptr;
>> + if (btrfs_tree_block_level(leaf, info) >= BTRFS_MAX_LEVEL) {
>> + extent_err(leaf, slot,
>> + "invalid tree block info level, have %u expect [0, %u)",
>
> nit: Strictly speaking using [0, 7) is wrong, because ')' already
> implies an open interval. Since we have 8 levels 0/7 inclusive this
> means the correct way to print it would be [0, 7] or [0, 8).
It's not that rare I misuses such notion. [0, 7] would be the case.
>
>
>> + btrfs_tree_block_level(leaf, info),
>> + BTRFS_MAX_LEVEL - 1);
>> + return -EUCLEAN;
>> + }
>> + ptr = (u64)(struct btrfs_tree_block_info *)(info + 1);
>> + }
>> +
>> + /* Check inline refs */
>> + while (ptr < end) {
>> + struct btrfs_extent_inline_ref *iref;
>> + struct btrfs_extent_data_ref *dref;
>> + struct btrfs_shared_data_ref *sref;
>> + u64 dref_offset;
>> + u64 inline_offset;
>> + u8 inline_type;
>> +
>> + if (ptr + sizeof(*iref) > end) {
>> + extent_err(leaf, slot,
>> + "invalid item size, size too small, ptr %llu end %llu",
>> + ptr, end);
>> + goto err;
>> + }
>> + iref = (struct btrfs_extent_inline_ref *)ptr;
>> + inline_type = btrfs_extent_inline_ref_type(leaf, iref);
>> + inline_offset = btrfs_extent_inline_ref_offset(leaf, iref);
>> + if (ptr + btrfs_extent_inline_ref_size(inline_type) > end) {
>> + extent_err(leaf, slot,
>> + "invalid item size, size too small, ptr %llu end %llu",
>
> Make that text explicit:
>
> "inline ref item overflows extent item" or some such.
OK, I'll use this expression.
Thanks,
Qu
[...]
>> +
>> + /* Finally, check the inline refs against total refs */
>> + if (total_refs < inline_refs) {
>
> nit: if (inline_refs > total_refs) {} looks saner to me.
>
>
>
>> + extent_err(leaf, slot,
>> + "invalid extent refs, have %llu expect >= %llu",
>> + total_refs, inline_refs);
>> + goto err;
>> + }
>> + return 0;
>> +err:
>> + return -EUCLEAN;
>> +}
>> +
>> /*
>> * Common point to switch the item-specific validation.
>> */
>> @@ -937,6 +1182,10 @@ static int check_leaf_item(struct extent_buffer *leaf,
>> case BTRFS_ROOT_ITEM_KEY:
>> ret = check_root_item(leaf, key, slot);
>> break;
>> + case BTRFS_EXTENT_ITEM_KEY:
>> + case BTRFS_METADATA_ITEM_KEY:
>> + ret = check_extent_item(leaf, key, slot);
>> + break;
>> }
>> return ret;
>> }
>>
^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2019-07-29 13:53 UTC | newest]
Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-07-29 7:43 [PATCH 0/3] btrfs: tree-checker: Add extent items check Qu Wenruo
2019-07-29 7:43 ` [PATCH 1/3] btrfs: tree-checker: Add EXTENT_ITEM and METADATA_ITEM check Qu Wenruo
2019-07-29 13:42 ` Nikolay Borisov
2019-07-29 13:53 ` Qu Wenruo
2019-07-29 7:43 ` [PATCH 2/3] btrfs: tree-checker: Add simple keyed refs check Qu Wenruo
2019-07-29 7:43 ` [PATCH 3/3] btrfs: tree-checker: Add EXTENT_DATA_REF check Qu Wenruo
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).