[PATCH v7] hfsplus: fix recursive tree_lock and validate b-tree fork extents

[Nguyen Ngoc Thang]

Fix a self-deadlock in the extents-overflow B-tree and validate b-tree
fork extents at mount time to catch on-disk corruption early.

hfs_bmap_reserve() can call hfsplus_file_extend() on tree->inode while
tree->tree_lock is already held. When the tree is the extents overflow
B-tree itself and its fork already claims more blocks than its eight
direct extents describe, hfsplus_file_extend() calls
hfsplus_ext_read_extent() -> hfs_find_init() on that same tree, taking
tree_lock a second time. Per the HFS+ format the extents overflow file
can never have overflow extents of its own, so this state only arises
from a corrupted image; refuse to grow the file in that case instead
of re-entering the lock.

Separately, validate each system b-tree's fork (extents, total_blocks,
total_size, clump_size) once at mount time in hfs_btree_open(), and
mount read-only if a fork is corrupt but still usable, or fail the
mount if the first extent itself is corrupt.

Thanks to Viacheslav Dubeyko for the thorough v6 review that caught
the missing lock fix and the other issues below.

v7:
 - Restore the tree_lock fix that was mistakenly dropped in v6 (I
   rebased off the wrong base and lost it; sorry for the noise).
 - Move HFSPLUS_EXTENT_LAST_IDX into hfsplus_fs.h.
 - Move fork validation out of hfsplus_inode_read_fork() and into
   hfs_btree_open(), where the error is actually checked and acted on.
 - Only set SB_RDONLY from hfsplus_fill_super()/hfsplus_reconfigure(),
   never from the fork checker itself.
 - Also validate total_size against the fork's block count, and
   reject a clump_size larger than the volume.

Reported-by: syzbot+f8ce6c197125ab9d72ce@xxxxxxxxxxxxxxxxxxxxxxxxx
Signed-off-by: Nguyen Ngoc Thang <ngocthang2710.1999@xxxxxxxxx>

Co-Authored-By: Claude Sonnet 5 <noreply@xxxxxxxxxxxxx>
---
 fs/hfsplus/btree.c      |  21 +++++++
 fs/hfsplus/extents.c    | 122 ++++++++++++++++++++++++++++++++++++++--
 fs/hfsplus/hfsplus_fs.h |  10 ++++
 fs/hfsplus/super.c      |  13 +++++
 4 files changed, 160 insertions(+), 6 deletions(-)

diff --git a/fs/hfsplus/btree.c b/fs/hfsplus/btree.c
index 2ea8cd5658e1..a07ca8a477f7 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,26 @@ 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,
+				 tree->inode->i_size);
+	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);
+	} else if (HFSPLUS_I(tree->inode)->clump_blocks > HFSPLUS_SB(sb)->total_blocks) {
+		/* clump_size is only ever a growth hint, but a value this
+		 * large can only come from a corrupt fork
+		 */
+		pr_warn("%s (cnid 0x%x) fork has bogus clump size, 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..925bbc3b36dc 100644
--- a/fs/hfsplus/extents.c
+++ b/fs/hfsplus/extents.c
@@ -77,13 +77,68 @@ static u32 hfsplus_ext_lastblock(struct hfsplus_extent *ext)
 {
 	int i;
 
-	ext += 7;
-	for (i = 0; i < 7; ext--, i++)
+	ext += HFSPLUS_EXTENT_LAST_IDX;
+	for (i = 0; i < HFSPLUS_EXTENT_LAST_IDX; ext--, i++)
 		if (ext->block_count)
 			break;
 	return be32_to_cpu(ext->start_block) + be32_to_cpu(ext->block_count);
 }
 
+/* True for the extents overflow file's own inode */
+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 volume_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 <= volume_blocks;
+}
+
+/* 0 if the fork is consistent, -EUCLEAN if fixable, -EIO if unusable */
+int hfsplus_check_fork(struct super_block *sb, struct hfsplus_extent *ext,
+		       u32 fork_blocks, u64 fork_size)
+{
+	struct hfsplus_sb_info *sbi = HFSPLUS_SB(sb);
+	bool seen_hole = false;
+	u32 used_blocks = 0;
+	loff_t max_size, min_size;
+	int i;
+
+	for (i = 0; i < HFSPLUS_EXTENT_COUNT; 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;
+
+	if (used_blocks != fork_blocks)
+		return -EUCLEAN;
+
+	/* fork_size must need exactly fork_blocks allocation blocks */
+	max_size = (loff_t)fork_blocks << sbi->alloc_blksz_shift;
+	min_size = max_size - (1 << sbi->alloc_blksz_shift);
+	if (fork_size <= min_size || fork_size > max_size)
+		return -EUCLEAN;
+
+	return 0;
+}
+
 static int __hfsplus_ext_write_extent(struct inode *inode,
 		struct hfs_find_data *fd)
 {
@@ -217,6 +272,10 @@ static int hfsplus_ext_read_extent(struct inode *inode, u32 block)
 	    block < hip->cached_start + hip->cached_blocks)
 		return 0;
 
+	/* The extents overflow file can't have overflow extents of its own */
+	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 +451,35 @@ static int hfsplus_free_extents(struct super_block *sb,
 	}
 }
 
+/* True when all extents of a fork are in use (no free slot left) */
+static bool hfsplus_ext_fork_full(struct hfsplus_extent *ext)
+{
+	int i;
+
+	for (i = 0; i < HFSPLUS_EXTENT_COUNT; ext++, i++)
+		if (!ext->block_count)
+			return false;
+	return true;
+}
+
+/* True when the extents overflow file's fork has no free slot left */
+static bool hfsplus_ext_file_needs_contig_grow(struct inode *inode,
+					       struct hfsplus_inode_info *hip)
+{
+	return is_extents_btree(inode) &&
+	       hip->alloc_blocks == hip->first_blocks &&
+	       hfsplus_ext_fork_full(hip->first_extents);
+}
+
+/*
+ * Fork is full: only a contiguous extension of the last extent works.
+ * Search for up to *len free blocks starting exactly at goal.
+ */
+static u32 hfsplus_ext_file_grow(struct super_block *sb, u32 goal, u32 *len)
+{
+	return hfsplus_block_allocate(sb, goal + *len, goal, len);
+}
+
 int hfsplus_free_fork(struct super_block *sb, u32 cnid,
 		struct hfsplus_fork_raw *fork, int type)
 {
@@ -458,6 +546,11 @@ int hfsplus_file_extend(struct inode *inode, bool zeroout)
 	if (hip->alloc_blocks == hip->first_blocks)
 		goal = hfsplus_ext_lastblock(hip->first_extents);
 	else {
+		/* Would re-enter ext_tree->tree_lock; corrupt fork */
+		if (is_extents_btree(inode)) {
+			res = -EIO;
+			goto out;
+		}
 		res = hfsplus_ext_read_extent(inode, hip->alloc_blocks);
 		if (res)
 			goto out;
@@ -465,13 +558,21 @@ 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 (hfsplus_ext_file_needs_contig_grow(inode, hip)) {
+		start = hfsplus_ext_file_grow(sb, 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 +627,15 @@ int hfsplus_file_extend(struct inode *inode, bool zeroout)
 	return res;
 
 insert_extent:
+	/* Can't happen: the fork-full branch 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..df636f2dbf1d 100644
--- a/fs/hfsplus/hfsplus_fs.h
+++ b/fs/hfsplus/hfsplus_fs.h
@@ -222,15 +222,23 @@ struct hfsplus_inode_info {
 #define HFSPLUS_EXT_DIRTY	0x0001
 #define HFSPLUS_EXT_NEW		0x0002
 
+/* Number of extent slots in a fork's hfsplus_extent_rec (hfs_common.h) */
+#define HFSPLUS_EXTENT_COUNT		8
+#define HFSPLUS_EXTENT_LAST_IDX	(HFSPLUS_EXTENT_COUNT - 1)
+
 #define HFSPLUS_I_RSRC		0	/* represents a resource fork */
 #define HFSPLUS_I_CAT_DIRTY	1	/* has changes in the catalog tree */
 #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 +448,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 fork_blocks, u64 fork_size);
 
 /* 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