[PATCH v5] hfsplus: fix recursive tree_lock and validate b-tree fork extents at mount

[Nguyen Ngoc Thang]

hfs_bmap_reserve() calls hfsplus_file_extend() on tree->inode with
tree->tree_lock already held. For the extents overflow B-tree's own
inode, growing it can call hfsplus_ext_read_extent() -> hfs_find_init()
on that same tree, taking tree_lock a second time (lockdep: "possible
recursive locking ... &tree->tree_lock/1"). This happens two ways:

 - the fork already claims more blocks than its eight extents
   describe (a corrupted on-disk fork), so hfsplus_ext_read_extent()
   is called immediately to look up the rest; or
 - the fork's eight extents get exhausted during this call, and
   inserting a new overflow extent record for the file would need
   the same lookup.

Per the HFS+ format the extents overflow file is fully described by
its eight fork extents and can never legitimately have overflow
extents of its own, so both cases mean it cannot grow any further.

Add is_extents_btree() and use it at the one place that actually
re-enters hfs_find_init(), hfsplus_ext_read_extent(), to report
-ENOSPC instead of recursing.

For the second case, don't allocate blocks on the chance the fork
still has room and undo it if not: hfsplus_fork_full() tests the
fork first (its last extent is occupied). If it does have a free
slot, any free space works, same as before. If it's already full,
the only way to grow is a contiguous extension of the last extent,
so only search for free space starting exactly at the block right
after it, and fail with -ENOSPC immediately if that block isn't
free. A WARN_ON_ONCE() backstop stays at the insert_extent label:
the fork-full check below should make it unreachable for this
inode, so warn loudly if that invariant ever breaks instead of
recursing on tree_lock again.

To back that invariant, hfsplus_check_fork() now validates each
b-tree's fork extents at mount time, from hfs_btree_open(). It
catches:

 - block_count == 0 but start_block != 0: garbage left in a slot
   that should be blank (this is what the syzbot-reported image has
   in the extents overflow file's fork, slots 3 and 6);
 - start_block + block_count > sbi->total_blocks: an extent pointing
   past the end of the volume, or overflowing u32;
 - a non-zero extent following a zero one: a hole in the used range;
 - the sum of the used extents' block_count disagreeing with the
   fork's own declared total_blocks.

If the first extent itself fails these checks, the b-tree's location
on disk is unknown and there is nothing to recover, so hfs_btree_open()
fails as it already does for the other structural checks in that
function, and the mount fails.

If only a later extent is affected, the tree can still be opened (its
first extent, and hence its root node, is fine); mark it corrupt and
let the caller decide. hfsplus_fill_super() forces the volume
read-only in that case, and hfsplus_reconfigure() checks the same
per-tree flag on remount instead of re-deriving it, refusing to go
back to read-write. attr_tree may be NULL (volumes without an
attributes fork), so both checks guard for that. The corruption state
is tracked as a HFSPLUS_I_CORRUPT_TREE bit on the b-tree's own inode,
next to the existing per-tree HFSPLUS_I_*_DIRTY flags, since one inode
already maps to one tree.

This mount-time check is what makes the WARN_ON_ONCE() above
unreachable in practice: a fuzzed or damaged fork like the one in the
syzbot report is now caught here before any write ever reaches it.

Reported-by: syzbot+f8ce6c197125ab9d72ce@xxxxxxxxxxxxxxxxxxxxxxxxx
Signed-off-by: Nguyen Ngoc Thang <ngocthang2710.1999@xxxxxxxxx>
---
 fs/hfsplus/btree.c      | 13 +++++++
 fs/hfsplus/extents.c    | 83 +++++++++++++++++++++++++++++++++++++++--
 fs/hfsplus/hfsplus_fs.h |  6 +++
 fs/hfsplus/super.c      | 13 +++++++
 4 files changed, 111 insertions(+), 4 deletions(-)

diff --git a/fs/hfsplus/btree.c b/fs/hfsplus/btree.c
index 2ea8cd5658e1..7f922e424a36 100644
--- a/fs/hfsplus/btree.c
+++ b/fs/hfsplus/btree.c
@@ -274,6 +274,7 @@ struct hfs_btree *hfs_btree_open(struct super_block *sb, u32 id)
 	struct inode *inode;
 	struct page *page;
 	unsigned int size;
+	int res;
 
 	tree = kzalloc_obj(*tree);
 	if (!tree)
@@ -293,6 +294,18 @@ struct hfs_btree *hfs_btree_open(struct super_block *sb, u32 id)
 		goto free_inode;
 	}
 
+	res = hfsplus_check_fork(sb, HFSPLUS_I(tree->inode)->first_extents,
+				 HFSPLUS_I(tree->inode)->alloc_blocks);
+	if (res == -EIO) {
+		pr_err("%s (cnid 0x%x) fork's first extent is corrupt\n",
+		       hfs_btree_name(id), id);
+		goto free_inode;
+	} else if (res) {
+		pr_warn("%s (cnid 0x%x) fork has corrupt extents, forcing read-only.\n",
+			hfs_btree_name(id), id);
+		set_bit(HFSPLUS_I_CORRUPT_TREE, &HFSPLUS_I(tree->inode)->flags);
+	}
+
 	mapping = tree->inode->i_mapping;
 	page = read_mapping_page(mapping, 0, NULL);
 	if (IS_ERR(page))
diff --git a/fs/hfsplus/extents.c b/fs/hfsplus/extents.c
index eb7c11524d18..5b6839918eef 100644
--- a/fs/hfsplus/extents.c
+++ b/fs/hfsplus/extents.c
@@ -84,6 +84,54 @@ static u32 hfsplus_ext_lastblock(struct hfsplus_extent *ext)
 	return be32_to_cpu(ext->start_block) + be32_to_cpu(ext->block_count);
 }
 
+static inline bool is_extents_btree(struct inode *inode)
+{
+	return inode->i_ino == HFSPLUS_EXT_CNID;
+}
+
+static bool hfsplus_extent_valid(struct hfsplus_extent *ext, u32 total_blocks)
+{
+	u32 start = be32_to_cpu(ext->start_block);
+	u32 count = be32_to_cpu(ext->block_count);
+
+	if (!count)
+		return start == 0;
+
+	return start + count > start && start + count <= total_blocks;
+}
+
+/*
+ * Returns 0 if the fork's extents are consistent, -EUCLEAN if only
+ * extents past the first are corrupt (safe to mount read-only), or
+ * -EIO if the first extent is corrupt or the fork has no used extent.
+ */
+int hfsplus_check_fork(struct super_block *sb, struct hfsplus_extent *ext,
+		       u32 total_blocks)
+{
+	struct hfsplus_sb_info *sbi = HFSPLUS_SB(sb);
+	bool seen_hole = false;
+	u32 used_blocks = 0;
+	int i;
+
+	for (i = 0; i < 8; i++, ext++) {
+		u32 count = be32_to_cpu(ext->block_count);
+
+		if (!hfsplus_extent_valid(ext, sbi->total_blocks) ||
+		    (seen_hole && count))
+			return i ? -EUCLEAN : -EIO;
+
+		if (count)
+			used_blocks += count;
+		else
+			seen_hole = true;
+	}
+
+	if (!used_blocks)
+		return -EIO;
+
+	return used_blocks == total_blocks ? 0 : -EUCLEAN;
+}
+
 static int __hfsplus_ext_write_extent(struct inode *inode,
 		struct hfs_find_data *fd)
 {
@@ -217,6 +265,9 @@ static int hfsplus_ext_read_extent(struct inode *inode, u32 block)
 	    block < hip->cached_start + hip->cached_blocks)
 		return 0;
 
+	if (is_extents_btree(inode))
+		return -ENOSPC;
+
 	res = hfs_find_init(HFSPLUS_SB(inode->i_sb)->ext_tree, &fd);
 	if (!res) {
 		res = __hfsplus_ext_cache_extent(&fd, inode, block);
@@ -392,6 +443,11 @@ static int hfsplus_free_extents(struct super_block *sb,
 	}
 }
 
+static bool hfsplus_fork_full(struct hfsplus_extent *ext)
+{
+	return ext[7].block_count != 0;
+}
+
 int hfsplus_free_fork(struct super_block *sb, u32 cnid,
 		struct hfsplus_fork_raw *fork, int type)
 {
@@ -465,13 +521,23 @@ int hfsplus_file_extend(struct inode *inode, bool zeroout)
 	}
 
 	len = hip->clump_blocks;
-	start = hfsplus_block_allocate(sb, sbi->total_blocks, goal, &len);
-	if (start >= sbi->total_blocks) {
-		start = hfsplus_block_allocate(sb, goal, 0, &len);
-		if (start >= goal) {
+	if (is_extents_btree(inode) && hip->alloc_blocks == hip->first_blocks &&
+	    hfsplus_fork_full(hip->first_extents)) {
+		/* Full fork, no overflow extent possible: goal or nothing */
+		start = hfsplus_block_allocate(sb, goal + len, goal, &len);
+		if (start != goal) {
 			res = -ENOSPC;
 			goto out;
 		}
+	} else {
+		start = hfsplus_block_allocate(sb, sbi->total_blocks, goal, &len);
+		if (start >= sbi->total_blocks) {
+			start = hfsplus_block_allocate(sb, goal, 0, &len);
+			if (start >= goal) {
+				res = -ENOSPC;
+				goto out;
+			}
+		}
 	}
 
 	if (zeroout) {
@@ -526,6 +592,15 @@ int hfsplus_file_extend(struct inode *inode, bool zeroout)
 	return res;
 
 insert_extent:
+	/* Can't happen: the fork-full check above rules this out */
+	if (WARN_ON_ONCE(is_extents_btree(inode))) {
+		if (hfsplus_block_free(sb, start, len))
+			pr_err("can't free extent: start %u, count %u\n",
+			       start, len);
+		res = -ENOSPC;
+		goto out;
+	}
+
 	hfs_dbg("insert new extent\n");
 	res = hfsplus_ext_write_extent_locked(inode);
 	if (res)
diff --git a/fs/hfsplus/hfsplus_fs.h b/fs/hfsplus/hfsplus_fs.h
index 1e5b58e6a13f..af36f2faf286 100644
--- a/fs/hfsplus/hfsplus_fs.h
+++ b/fs/hfsplus/hfsplus_fs.h
@@ -227,10 +227,14 @@ struct hfsplus_inode_info {
 #define HFSPLUS_I_EXT_DIRTY	2	/* has changes in the extent tree */
 #define HFSPLUS_I_ALLOC_DIRTY	3	/* has changes in the allocation file */
 #define HFSPLUS_I_ATTR_DIRTY	4	/* has changes in the attributes tree */
+#define HFSPLUS_I_CORRUPT_TREE	5	/* tree's fork had corrupt extents at open time */
 
 #define HFSPLUS_IS_RSRC(inode) \
 	test_bit(HFSPLUS_I_RSRC, &HFSPLUS_I(inode)->flags)
 
+#define HFSPLUS_TREE_IS_CORRUPT(tree) \
+	test_bit(HFSPLUS_I_CORRUPT_TREE, &HFSPLUS_I((tree)->inode)->flags)
+
 static inline struct hfsplus_inode_info *HFSPLUS_I(struct inode *inode)
 {
 	return container_of(inode, struct hfsplus_inode_info, vfs_inode);
@@ -440,6 +444,8 @@ int hfsplus_free_fork(struct super_block *sb, u32 cnid,
 		      struct hfsplus_fork_raw *fork, int type);
 int hfsplus_file_extend(struct inode *inode, bool zeroout);
 void hfsplus_file_truncate(struct inode *inode);
+int hfsplus_check_fork(struct super_block *sb, struct hfsplus_extent *ext,
+		       u32 total_blocks);
 
 /* inode.c */
 extern const struct address_space_operations hfsplus_aops;
diff --git a/fs/hfsplus/super.c b/fs/hfsplus/super.c
index ff7d6b3336a6..b6a85c153cf3 100644
--- a/fs/hfsplus/super.c
+++ b/fs/hfsplus/super.c
@@ -400,6 +400,14 @@ static int hfsplus_reconfigure(struct fs_context *fc)
 			pr_warn("filesystem is marked journaled, leaving read-only.\n");
 			sb->s_flags |= SB_RDONLY;
 			fc->sb_flags |= SB_RDONLY;
+		} else if (HFSPLUS_TREE_IS_CORRUPT(sbi->ext_tree) ||
+				HFSPLUS_TREE_IS_CORRUPT(sbi->cat_tree) ||
+				(sbi->attr_tree &&
+				 HFSPLUS_TREE_IS_CORRUPT(sbi->attr_tree))) {
+			/* Corruption is only ever detected at mount, in hfs_btree_open() */
+			pr_warn("a b-tree fork was corrupt at mount time, leaving read-only.\n");
+			sb->s_flags |= SB_RDONLY;
+			fc->sb_flags |= SB_RDONLY;
 		}
 	}
 	return 0;
@@ -564,6 +572,11 @@ static int hfsplus_fill_super(struct super_block *sb, struct fs_context *fc)
 	}
 	sb->s_xattr = hfsplus_xattr_handlers;
 
+	if (HFSPLUS_TREE_IS_CORRUPT(sbi->ext_tree) ||
+	    HFSPLUS_TREE_IS_CORRUPT(sbi->cat_tree) ||
+	    (sbi->attr_tree && HFSPLUS_TREE_IS_CORRUPT(sbi->attr_tree)))
+		sb->s_flags |= SB_RDONLY;
+
 	inode = hfsplus_iget(sb, HFSPLUS_ALLOC_CNID);
 	if (IS_ERR(inode)) {
 		pr_err("failed to load allocation file\n");
-- 
2.43.0