Skip to contentSkip to conversation

btrfs: tree-checker: Add checks to detect missing INODE_ITEM

PATCH In review Qu Wenruo 4 participants 8 messages Aug 26, 2019 – Sep 23, 2019 Btrfs file system

lore
Share & tools
lore

Qu Wenruo

author
#0 lore raw

cover btrfs: tree-checker: Add checks to detect missing INODE_ITEM

For the following items, key->objectid is inode number:
- DIR_ITEM
- DIR_INDEX
- XATTR_ITEM
- EXTENT_DATA
- INODE_REF

So in btrfs btree, such items must have its previous item shares the same objectid, e.g.:
(257 INODE_ITEM 0)
(257 DIR_INDEX xxx)
(257 DIR_ITEM xxx)
(258 INODE_ITEM 0)
(258 INODE_REF 0)
(258 XATTR_ITEM 0)
(258 EXTENT_DATA 0)

But if we have the following sequence, then there is definitely something wrong, normally some INODE_ITEM is missing, like:
(257 INODE_ITEM 0)
(257 DIR_INDEX xxx)
(257 DIR_ITEM xxx)
(258 XATTR_ITEM 0) <<< objecitd suddenly changed to 258 (258 EXTENT_DATA 0)

So just by checking the previous key for above inode based key types, we can detect missing inode item.

In this patchset, we will enhance existing check_dir_item() and check_extent_data_item() to detect missing INODE_ITEM first, then add INODE_REF checker.

So now we can cover the INODE_ITEM missing case in tree-checker without much cost, but achieve the check which is normally done by btrfs-check. (I'm already a little concerned about the fact that kernel tree-checker is getting stronger and stronger while btrfs-progs can't fix all problems)

Of course, there is still a limitation that the first key of a leaf can't be verified, but we have already cover all the rest keys, which is way better than "good enough"(TM).

Qu Wenruo (2):
btrfs: tree-checker: Try to detect missing INODE_ITEM
btrfs: tree-checker: Add check for INODE_REF

 fs/btrfs/tree-checker.c | 78 +++++++++++++++++++++++++++++++++++++++--
 1 file changed, 76 insertions(+), 2 deletions(-)
Signature · 1 line
2.23.0
author
#1 lore raw

PATCH 1/2 btrfs: tree-checker: Try to detect missing INODE_ITEM

For the following items, key->objectid is inode number:
- DIR_ITEM
- DIR_INDEX
- XATTR_ITEM
- EXTENT_DATA
- INODE_REF

So in btrfs btree, such items must have its previous item shares the same objectid, e.g.:
(257 INODE_ITEM 0)
(257 DIR_INDEX xxx)
(257 DIR_ITEM xxx)
(258 INODE_ITEM 0)
(258 INODE_REF 0)
(258 XATTR_ITEM 0)
(258 EXTENT_DATA 0)

But if we have the following sequence, then there is definitely something wrong, normally some INODE_ITEM is missing, like:
(257 INODE_ITEM 0)
(257 DIR_INDEX xxx)
(257 DIR_ITEM xxx)
(258 XATTR_ITEM 0) <<< objecitd suddenly changed to 258 (258 EXTENT_DATA 0)

So just by checking the previous key for above inode based key types, we can detect missing inode item.

For INODE_REF key type, the check will be added along with INODE_REF checker.

---
 fs/btrfs/tree-checker.c | 25 +++++++++++++++++++++++--
 1 file changed, 23 insertions(+), 2 deletions(-)
fs/btrfs/tree-checker.c +23 -2
index ccd5706199d7..636ce1b4566e 100644
@@ -141,6 +141,19 @@ static int check_extent_data_item(struct extent_buffer *leaf,
 		return -EUCLEAN;
 	}
 
+	/*
+	 * Previous key must have the same key->objectid (ino).
+	 * It can be XATTR_ITEM, INODE_ITEM or just another EXTENT_DATA.
+	 * But if objectids mismatch, it means we have a missing
+	 * INODE_ITEM.
+	 */
+	if (slot > 0 && prev_key->objectid != key->objectid) {
+		file_extent_err(leaf, slot,
+		"invalid previous key objectid, have %llu expect %llu",
+				prev_key->objectid, key->objectid);
+		return -EUCLEAN;
+	}
+
 	fi = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item);
 
 	if (btrfs_file_extent_type(leaf, fi) > BTRFS_FILE_EXTENT_TYPES) {
@@ -299,13 +312,21 @@ static void dir_item_err(const struct extent_buffer *eb, int slot,
 }
 
 static int check_dir_item(struct extent_buffer *leaf,
-			  struct btrfs_key *key, int slot)
+			  struct btrfs_key *key, struct btrfs_key *prev_key,
+			  int slot)
 {
 	struct btrfs_fs_info *fs_info = leaf->fs_info;
 	struct btrfs_dir_item *di;
 	u32 item_size = btrfs_item_size_nr(leaf, slot);
 	u32 cur = 0;
 
+	/* Same check as in check_extent_data_item() */
+	if (slot > 0 && prev_key->objectid != key->objectid) {
+		dir_item_err(leaf, slot,
+		"invalid previous key objectid, have %llu expect %llu",
+			     prev_key->objectid, key->objectid);
+		return -EUCLEAN;
+	}
 	di = btrfs_item_ptr(leaf, slot, struct btrfs_dir_item);
 	while (cur < item_size) {
 		u32 name_len;
@@ -841,7 +862,7 @@ static int check_leaf_item(struct extent_buffer *leaf,
 	case BTRFS_DIR_ITEM_KEY:
 	case BTRFS_DIR_INDEX_KEY:
 	case BTRFS_XATTR_ITEM_KEY:
-		ret = check_dir_item(leaf, key, slot);
+		ret = check_dir_item(leaf, key, prev_key, slot);
 		break;
 	case BTRFS_BLOCK_GROUP_ITEM_KEY:
 		ret = check_block_group_item(leaf, key, slot);
Signature · 1 line
2.23.0
Reviewed-by on v1 1/2
#2 lore raw

Re: [PATCH 1/2] btrfs: tree-checker: Try to detect missing INODE_ITEM

Quoted 25 lines · Qu Wenruo

For the following items, key->objectid is inode number:
- DIR_ITEM
- DIR_INDEX
- XATTR_ITEM
- EXTENT_DATA
- INODE_REF

So in btrfs btree, such items must have its previous item shares the same objectid, e.g.:
(257 INODE_ITEM 0)
(257 DIR_INDEX xxx)
(257 DIR_ITEM xxx)
(258 INODE_ITEM 0)
(258 INODE_REF 0)
(258 XATTR_ITEM 0)
(258 EXTENT_DATA 0)

But if we have the following sequence, then there is definitely something wrong, normally some INODE_ITEM is missing, like:
(257 INODE_ITEM 0)
(257 DIR_INDEX xxx)
(257 DIR_ITEM xxx)
(258 XATTR_ITEM 0) <<< objecitd suddenly changed to 258 (258 EXTENT_DATA 0)

Quoted 7 lines

So just by checking the previous key for above inode based key types, we can detect missing inode item.

For INODE_REF key type, the check will be added along with INODE_REF checker.

Quoted 61 lines
---
 fs/btrfs/tree-checker.c | 25 +++++++++++++++++++++++--
 1 file changed, 23 insertions(+), 2 deletions(-)
fs/btrfs/tree-checker.c +23 -2
index ccd5706199d7..636ce1b4566e 100644
@@ -141,6 +141,19 @@ static int check_extent_data_item(struct extent_buffer *leaf,
 		return -EUCLEAN;
 	}
 
+	/*
+	 * Previous key must have the same key->objectid (ino).
+	 * It can be XATTR_ITEM, INODE_ITEM or just another EXTENT_DATA.
+	 * But if objectids mismatch, it means we have a missing
+	 * INODE_ITEM.
+	 */
+	if (slot > 0 && prev_key->objectid != key->objectid) {
+		file_extent_err(leaf, slot,
+		"invalid previous key objectid, have %llu expect %llu",
+				prev_key->objectid, key->objectid);
+		return -EUCLEAN;
+	}
+
 	fi = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item);
 
 	if (btrfs_file_extent_type(leaf, fi) > BTRFS_FILE_EXTENT_TYPES) {
@@ -299,13 +312,21 @@ static void dir_item_err(const struct extent_buffer *eb, int slot,
 }
 
 static int check_dir_item(struct extent_buffer *leaf,
-			  struct btrfs_key *key, int slot)
+			  struct btrfs_key *key, struct btrfs_key *prev_key,
+			  int slot)
 {
 	struct btrfs_fs_info *fs_info = leaf->fs_info;
 	struct btrfs_dir_item *di;
 	u32 item_size = btrfs_item_size_nr(leaf, slot);
 	u32 cur = 0;
 
+	/* Same check as in check_extent_data_item() */
+	if (slot > 0 && prev_key->objectid != key->objectid) {
+		dir_item_err(leaf, slot,
+		"invalid previous key objectid, have %llu expect %llu",
+			     prev_key->objectid, key->objectid);
+		return -EUCLEAN;
+	}
 	di = btrfs_item_ptr(leaf, slot, struct btrfs_dir_item);
 	while (cur < item_size) {
 		u32 name_len;
@@ -841,7 +862,7 @@ static int check_leaf_item(struct extent_buffer *leaf,
 	case BTRFS_DIR_ITEM_KEY:
 	case BTRFS_DIR_INDEX_KEY:
 	case BTRFS_XATTR_ITEM_KEY:
-		ret = check_dir_item(leaf, key, slot);
+		ret = check_dir_item(leaf, key, prev_key, slot);
 		break;
 	case BTRFS_BLOCK_GROUP_ITEM_KEY:
 		ret = check_block_group_item(leaf, key, slot);
author
#3 lore raw

PATCH 2/2 btrfs: tree-checker: Add check for INODE_REF

In reply to Qu Wenruo

For INODE_REF we will check:
- Objectid (ino) against previous key
To detect missing INODE_ITEM.

- No overflow/padding in the data payload Much like DIR_ITEM, but with less members to check.

---
 fs/btrfs/tree-checker.c | 53 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 53 insertions(+)
fs/btrfs/tree-checker.c +53 -0
index 636ce1b4566e..3ce447eb591c 100644
@@ -842,6 +842,56 @@ static int check_inode_item(struct extent_buffer *leaf,
 	return 0;
 }
 
+#define inode_ref_err(fs_info, eb, slot, fmt, ...)		\
+	inode_item_err(fs_info, eb, slot, fmt, __VA_ARGS__)
+static int check_inode_ref(struct extent_buffer *leaf,
+			   struct btrfs_key *key, struct btrfs_key *prev_key,
+			   int slot)
+{
+	struct btrfs_inode_ref *iref;
+	unsigned long ptr;
+	unsigned long end;
+
+	/* namelen can't be 0, so item_size == sizeof() is also invalid */
+	if (btrfs_item_size_nr(leaf, slot) <= sizeof(*iref)) {
+		inode_ref_err(fs_info, leaf, slot,
+		"invalid item size, have %u expect (%zu, %u)",
+			btrfs_item_size_nr(leaf, slot),
+			sizeof(*iref), BTRFS_LEAF_DATA_SIZE(leaf->fs_info));
+		return -EUCLEAN;
+	}
+
+	ptr = btrfs_item_ptr_offset(leaf, slot);
+	end = ptr + btrfs_item_size_nr(leaf, slot);
+	while (ptr < end) {
+		u16 namelen;
+
+		if (ptr + sizeof(iref) > end) {
+			inode_ref_err(fs_info, leaf, slot,
+		"inode ref overflow, ptr %lu end %lu inode_ref_size %zu",
+				ptr, end, sizeof(iref));
+			return -EUCLEAN;
+		}
+
+		iref = (struct btrfs_inode_ref *)ptr;
+		namelen = btrfs_inode_ref_name_len(leaf, iref);
+		if (ptr + sizeof(*iref) + namelen > end) {
+			inode_ref_err(fs_info, leaf, slot,
+		"inode ref overflow, ptr %lu end %lu namelen %u",
+				ptr, end, namelen);
+			return -EUCLEAN;
+		}
+
+		/*
+		 * NOTE: In theory we should record all found index number
+		 * to find any duplicated index. But that will be too time
+		 * consuming for inodes with too many hard links.
+		 */
+		ptr += sizeof(*iref) + namelen;
+	}
+	return 0;
+}
+
 /*
  * Common point to switch the item-specific validation.
  */
@@ -864,6 +914,9 @@ static int check_leaf_item(struct extent_buffer *leaf,
 	case BTRFS_XATTR_ITEM_KEY:
 		ret = check_dir_item(leaf, key, prev_key, slot);
 		break;
+	case BTRFS_INODE_REF_KEY:
+		ret = check_inode_ref(leaf, key, prev_key, slot);
+		break;
 	case BTRFS_BLOCK_GROUP_ITEM_KEY:
 		ret = check_block_group_item(leaf, key, slot);
 		break;
Signature · 1 line
2.23.0
#4 lore raw

Re: [PATCH 2/2] btrfs: tree-checker: Add check for INODE_REF

Quoted 17 lines · Qu Wenruo

For INODE_REF we will check:
- Objectid (ino) against previous key
To detect missing INODE_ITEM.

- No overflow/padding in the data payload Much like DIR_ITEM, but with less members to check.

---
 fs/btrfs/tree-checker.c | 53 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 53 insertions(+)
fs/btrfs/tree-checker.c +0 -0
index 636ce1b4566e..3ce447eb591c 100644

fs/btrfs/tree-checker.c static int check_inode_item(struct extent_buffer *leaf, · line 846

Quoted 5 lines
fs/btrfs/tree-checker.c +2 -0
@@ -842,6 +842,56 @@ static int check_inode_item(struct extent_buffer *leaf,
 	return 0;
 }
 
+#define inode_ref_err(fs_info, eb, slot, fmt, ...)		\
+	inode_item_err(fs_info, eb, slot, fmt, __VA_ARGS__)

This define doesn't bring anything, just opencode the call to inode_item_err directly.

Quoted 62 lines
fs/btrfs/tree-checker.c +51 -0
+static int check_inode_ref(struct extent_buffer *leaf,
+			   struct btrfs_key *key, struct btrfs_key *prev_key,
+			   int slot)
+{
+	struct btrfs_inode_ref *iref;
+	unsigned long ptr;
+	unsigned long end;
+
+	/* namelen can't be 0, so item_size == sizeof() is also invalid */
+	if (btrfs_item_size_nr(leaf, slot) <= sizeof(*iref)) {
+		inode_ref_err(fs_info, leaf, slot,
+		"invalid item size, have %u expect (%zu, %u)",
+			btrfs_item_size_nr(leaf, slot),
+			sizeof(*iref), BTRFS_LEAF_DATA_SIZE(leaf->fs_info));
+		return -EUCLEAN;
+	}
+
+	ptr = btrfs_item_ptr_offset(leaf, slot);
+	end = ptr + btrfs_item_size_nr(leaf, slot);
+	while (ptr < end) {
+		u16 namelen;
+
+		if (ptr + sizeof(iref) > end) {
+			inode_ref_err(fs_info, leaf, slot,
+		"inode ref overflow, ptr %lu end %lu inode_ref_size %zu",
+				ptr, end, sizeof(iref));
+			return -EUCLEAN;
+		}
+
+		iref = (struct btrfs_inode_ref *)ptr;
+		namelen = btrfs_inode_ref_name_len(leaf, iref);
+		if (ptr + sizeof(*iref) + namelen > end) {
+			inode_ref_err(fs_info, leaf, slot,
+		"inode ref overflow, ptr %lu end %lu namelen %u",
+				ptr, end, namelen);
+			return -EUCLEAN;
+		}
+
+		/*
+		 * NOTE: In theory we should record all found index number
+		 * to find any duplicated index. But that will be too time
+		 * consuming for inodes with too many hard links.
+		 */
+		ptr += sizeof(*iref) + namelen;
+	}
+	return 0;
+}
+
 /*
  * Common point to switch the item-specific validation.
  */
@@ -864,6 +914,9 @@ static int check_leaf_item(struct extent_buffer *leaf,
 	case BTRFS_XATTR_ITEM_KEY:
 		ret = check_dir_item(leaf, key, prev_key, slot);
 		break;
+	case BTRFS_INODE_REF_KEY:
+		ret = check_inode_ref(leaf, key, prev_key, slot);
+		break;
 	case BTRFS_BLOCK_GROUP_ITEM_KEY:
 		ret = check_block_group_item(leaf, key, slot);
 		break;
#5 lore raw

Re: [PATCH 2/2] btrfs: tree-checker: Add check for INODE_REF

Quoted 23 lines · Nikolay Borisov
Quoted 20 lines · Qu Wenruo

For INODE_REF we will check:
- Objectid (ino) against previous key
To detect missing INODE_ITEM.

- No overflow/padding in the data payload Much like DIR_ITEM, but with less members to check.

---
 fs/btrfs/tree-checker.c | 53 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 53 insertions(+)
fs/btrfs/tree-checker.c +0 -0
index 636ce1b4566e..3ce447eb591c 100644
@@ -842,6 +842,56 @@ static int check_inode_item(struct extent_buffer *leaf,
 	return 0;
 }
 
Quoted 5 lines

fs/btrfs/tree-checker.c static int check_inode_item(struct extent_buffer *leaf, · line 846

Quoted 2 lines
fs/btrfs/tree-checker.c +2 -0
+#define inode_ref_err(fs_info, eb, slot, fmt, ...)		\
+	inode_item_err(fs_info, eb, slot, fmt, __VA_ARGS__)

This define doesn't bring anything, just opencode the call to inode_item_err directly.

I could argue we that in an inode ref context, using a inode_item_err() doesn't look right.

And since it's doesn't do any hurt, I prefer to make the error message parse to match the context.

Thanks,
Qu

Quoted 63 lines
Quoted 63 lines
fs/btrfs/tree-checker.c +51 -0
+static int check_inode_ref(struct extent_buffer *leaf,
+			   struct btrfs_key *key, struct btrfs_key *prev_key,
+			   int slot)
+{
+	struct btrfs_inode_ref *iref;
+	unsigned long ptr;
+	unsigned long end;
+
+	/* namelen can't be 0, so item_size == sizeof() is also invalid */
+	if (btrfs_item_size_nr(leaf, slot) <= sizeof(*iref)) {
+		inode_ref_err(fs_info, leaf, slot,
+		"invalid item size, have %u expect (%zu, %u)",
+			btrfs_item_size_nr(leaf, slot),
+			sizeof(*iref), BTRFS_LEAF_DATA_SIZE(leaf->fs_info));
+		return -EUCLEAN;
+	}
+
+	ptr = btrfs_item_ptr_offset(leaf, slot);
+	end = ptr + btrfs_item_size_nr(leaf, slot);
+	while (ptr < end) {
+		u16 namelen;
+
+		if (ptr + sizeof(iref) > end) {
+			inode_ref_err(fs_info, leaf, slot,
+		"inode ref overflow, ptr %lu end %lu inode_ref_size %zu",
+				ptr, end, sizeof(iref));
+			return -EUCLEAN;
+		}
+
+		iref = (struct btrfs_inode_ref *)ptr;
+		namelen = btrfs_inode_ref_name_len(leaf, iref);
+		if (ptr + sizeof(*iref) + namelen > end) {
+			inode_ref_err(fs_info, leaf, slot,
+		"inode ref overflow, ptr %lu end %lu namelen %u",
+				ptr, end, namelen);
+			return -EUCLEAN;
+		}
+
+		/*
+		 * NOTE: In theory we should record all found index number
+		 * to find any duplicated index. But that will be too time
+		 * consuming for inodes with too many hard links.
+		 */
+		ptr += sizeof(*iref) + namelen;
+	}
+	return 0;
+}
+
 /*
  * Common point to switch the item-specific validation.
  */
@@ -864,6 +914,9 @@ static int check_leaf_item(struct extent_buffer *leaf,
 	case BTRFS_XATTR_ITEM_KEY:
 		ret = check_dir_item(leaf, key, prev_key, slot);
 		break;
+	case BTRFS_INODE_REF_KEY:
+		ret = check_inode_ref(leaf, key, prev_key, slot);
+		break;
 	case BTRFS_BLOCK_GROUP_ITEM_KEY:
 		ret = check_block_group_item(leaf, key, slot);
 		break;
#6 lore raw

Re: [PATCH 2/2] btrfs: tree-checker: Add check for INODE_REF

Quoted 32 lines · Qu Wenruo
Quoted 23 lines · Nikolay Borisov
Quoted 20 lines · Qu Wenruo

For INODE_REF we will check:
- Objectid (ino) against previous key
To detect missing INODE_ITEM.

- No overflow/padding in the data payload Much like DIR_ITEM, but with less members to check.

---
 fs/btrfs/tree-checker.c | 53 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 53 insertions(+)
fs/btrfs/tree-checker.c +0 -0
index 636ce1b4566e..3ce447eb591c 100644
@@ -842,6 +842,56 @@ static int check_inode_item(struct extent_buffer *leaf,
 	return 0;
 }
 
Quoted 5 lines

fs/btrfs/tree-checker.c static int check_inode_item(struct extent_buffer *leaf, · line 846

Quoted 2 lines
fs/btrfs/tree-checker.c +2 -0
+#define inode_ref_err(fs_info, eb, slot, fmt, ...)		\
+	inode_item_err(fs_info, eb, slot, fmt, __VA_ARGS__)

This define doesn't bring anything, just opencode the call to inode_item_err directly.

Quoted 5 lines

I could argue we that in an inode ref context, using a inode_item_err() doesn't look right.

And since it's doesn't do any hurt, I prefer to make the error message parse to match the context.

I agree the alias inode_ref_err does not hurt, there's no penatly in the code so for sake of readability let's do it.

#7 lore raw

Re: [PATCH 2/2] btrfs: tree-checker: Add check for INODE_REF

In reply to Qu Wenruo
Quoted 17 lines · Qu Wenruo

For INODE_REF we will check:
- Objectid (ino) against previous key
To detect missing INODE_ITEM.

- No overflow/padding in the data payload Much like DIR_ITEM, but with less members to check.

---
 fs/btrfs/tree-checker.c | 53 +++++++++++++++++++++++++++++++++++++++++
 1 file changed, 53 insertions(+)
fs/btrfs/tree-checker.c +0 -0
index 636ce1b4566e..3ce447eb591c 100644

fs/btrfs/tree-checker.c static int check_inode_item(struct extent_buffer *leaf, · line 846

Quoted 5 lines
fs/btrfs/tree-checker.c +2 -0
@@ -842,6 +842,56 @@ static int check_inode_item(struct extent_buffer *leaf,
 	return 0;
 }
 
+#define inode_ref_err(fs_info, eb, slot, fmt, ...)		\
+	inode_item_err(fs_info, eb, slot, fmt, __VA_ARGS__)

I've changed that to

#define inode_ref_err(fs_info, eb, slot, fmt, args...) \
inode_item_err(fs_info, eb, slot, fmt, ##args)

as this is the common style for the variable macro args used in btrfs.