[PATCH 3/5] btrfs: tree-checker: reject keyed refs not matching the extent type

[Siddharth Mishra <smish149@asu.edu>]

[BACKGROUND]
When the refs of an extent do not fit into its extent item, the others
are stored as keyed ref items with the same objectid, right after the
extent item:

  TREE_BLOCK:  TREE_BLOCK_REF and SHARED_BLOCK_REF items
  DATA:        EXTENT_DATA_REF and SHARED_DATA_REF items

[CAUSE]
check_simple_keyed_refs() and check_extent_data_ref() only verify the
keyed ref itself.  Nothing checks that its type matches the extent it
belongs to, so a tree block ref for a data extent, or a data ref for a
tree block, passes the tree-checker.  For example this data extent is
followed by a keyed tree block ref:

	item 0 key (13631488 EXTENT_ITEM 32768) itemoff 3797 itemsize 198
		refs 41 gen 9 flags DATA
		(178 0xdea30debbf5f519) extent data backref root 256
		objectid 258 offset 0 count 1
		...
	item 1 key (13631488 TREE_BLOCK_REF 5) itemoff 3797 itemsize 0
	           ^^^^^^^^^^^^^^^^^^^^^^^^^^^
		tree block backref

The leaf is accepted.  When the extent is freed later, the refs do not
add up and the transaction aborts:

  WARNING: fs/btrfs/extent-tree.c:3418 at __btrfs_free_extent
  BTRFS error (device vda state A): Transaction 35 aborted (-EUCLEAN)
  BTRFS info (device vda state EA): forced readonly

[ENHANCEMENT]
Check each keyed ref against the item right before it.  Keyed refs sort
right after their extent item, so that item is either the extent item
or another keyed ref of the same extent, and both must be of the same
kind.  Reject a mismatch with -EUCLEAN, so the leaf is refused when it
is read:

  BTRFS critical (device vda): corrupt leaf: block=31678464 slot=1
  extent bytenr=13631488 len=4096 keyed ref type 176 does not match the
  extent type

This is the keyed counterpart of the inline ref check.

If the item before a keyed ref belongs to another extent, its extent
item is in another leaf and the keyed ref cannot be checked by the
tree-checker.

Signed-off-by: Siddharth Mishra <smish149@asu.edu>
---
 fs/btrfs/tree-checker.c | 48 +++++++++++++++++++++++++++++++++++++++--
 1 file changed, 46 insertions(+), 2 deletions(-)

diff --git a/fs/btrfs/tree-checker.c b/fs/btrfs/tree-checker.c
index db446c8af..d966243c9 100644
--- a/fs/btrfs/tree-checker.c
+++ b/fs/btrfs/tree-checker.c
@@ -1854,6 +1854,50 @@ static int check_extent_item(struct extent_buffer *leaf,
 	return 0;
 }
 
+static int check_keyed_ref_extent_type(const struct extent_buffer *leaf,
+				       const struct btrfs_key *key, int slot)
+{
+	const bool is_tree_block_ref = (key->type == BTRFS_TREE_BLOCK_REF_KEY ||
+					key->type == BTRFS_SHARED_BLOCK_REF_KEY);
+	struct btrfs_key prev_key;
+	bool prev_is_tree_block;
+
+	if (slot == 0)
+		return 0;
+	btrfs_item_key_to_cpu(leaf, &prev_key, slot - 1);
+	if (prev_key.objectid != key->objectid)
+		return 0;
+
+	switch (prev_key.type) {
+	case BTRFS_EXTENT_ITEM_KEY:
+	case BTRFS_METADATA_ITEM_KEY: {
+		struct btrfs_extent_item *ei;
+
+		ei = btrfs_item_ptr(leaf, slot - 1, struct btrfs_extent_item);
+		prev_is_tree_block = (btrfs_extent_flags(leaf, ei) &
+				      BTRFS_EXTENT_FLAG_TREE_BLOCK);
+		break;
+	}
+	case BTRFS_TREE_BLOCK_REF_KEY:
+	case BTRFS_SHARED_BLOCK_REF_KEY:
+		prev_is_tree_block = true;
+		break;
+	case BTRFS_EXTENT_DATA_REF_KEY:
+	case BTRFS_SHARED_DATA_REF_KEY:
+		prev_is_tree_block = false;
+		break;
+	default:
+		return 0;
+	}
+	if (unlikely(prev_is_tree_block != is_tree_block_ref)) {
+		extent_err(leaf, slot,
+			   "keyed ref type %u does not match the extent type",
+			   key->type);
+		return -EUCLEAN;
+	}
+	return 0;
+}
+
 static int check_simple_keyed_refs(struct extent_buffer *leaf,
 				   struct btrfs_key *key, int slot)
 {
@@ -1892,7 +1936,7 @@ static int check_simple_keyed_refs(struct extent_buffer *leaf,
 			   key->offset, leaf->fs_info->sectorsize);
 		return -EUCLEAN;
 	}
-	return 0;
+	return check_keyed_ref_extent_type(leaf, key, slot);
 }
 
 static int check_extent_data_ref(struct extent_buffer *leaf,
@@ -1953,7 +1997,7 @@ static int check_extent_data_ref(struct extent_buffer *leaf,
 			return -EUCLEAN;
 		}
 	}
-	return 0;
+	return check_keyed_ref_extent_type(leaf, key, slot);
 }
 
 #define inode_ref_err(eb, slot, fmt, args...)			\
-- 
2.54.0