mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
From: Viacheslav Dubeyko <slava@dubeyko.com>
To: glaubitz@physik.fu-berlin.de, frank.li@vivo.com
Cc: linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org,
	vdubeyko@coreweave.com, Viacheslav Dubeyko <slava@dubeyko.com>,
	Zheng Zheng <fengaojigui88@gmail.com>,
	stable@vger.kernel.org
Subject: [PATCH 2/5] hfsplus: map the allocation file without the extents B-tree
Date: Thu, 19 Nov 2026 15:41:09 -0800	[thread overview]
Message-ID: <20261119234112.720963-3-slava@dubeyko.com> (raw)
In-Reply-To: <20261119234112.720963-1-slava@dubeyko.com>

hfsplus_block_allocate() and hfsplus_block_free() read the allocation
bitmap through the allocation file with sbi->alloc_mutex held. When the
bitmap page is not cached and lies beyond the allocation file's extents
in the volume header, hfsplus_get_block() takes the allocation file's
extents_lock and looks the block up in the extents B-tree under its
tree_lock.

Growing the extents B-tree does the opposite: hfs_bmap_reserve() is
called with the B-tree's tree_lock held and extends the B-tree file,
which allocates blocks under alloc_mutex. If the bitmap page needed
there is not cached and is mapped by an extent record of the
allocation file, the task tries to take the tree_lock it already holds
and deadlocks:

  WARNING: possible recursive locking detected
  dd/1404 is trying to acquire lock:
  (&tree->tree_lock/1){+.+.}-{4:4}, at: hfsplus_find_init
  but task is already holding lock:
  (&tree->tree_lock/1){+.+.}-{4:4}, at: hfsplus_find_init
  ...
   hfsplus_find_init
   hfsplus_ext_read_extent
   hfsplus_get_block
   block_read_full_folio
   ...
   read_cache_page
   hfsplus_block_allocate
   hfsplus_file_extend
   hfsplus_bmap_reserve
   __hfsplus_ext_write_extent
   hfsplus_ext_read_extent
   hfsplus_file_extend
   hfsplus_get_block
   ...
   hfsplus_write_begin

The writer, the flusher and the superblock commit work then hang. Two
tasks can also deadlock on the same pair of locks taken in opposite
order.

The same lookup is behind the lockdep report from syzkaller in which
truncating an unlinked file takes the allocation file's extents_lock
inside its own (hfsplus_file_truncate() -> hfsplus_free_extents() ->
hfsplus_block_free() -> read_cache_page() -> hfsplus_get_block()).
Syzkaller reached it with a corrupted image, which the previous patch
rejects at mount.

The allocation file cannot grow or shrink while the volume is mounted.
Read its extent records from the extents B-tree once at mount time and
map its blocks beyond the volume header's extents from them, so that
reading the bitmap takes neither the allocation file's extents_lock nor
the extents B-tree's tree_lock. The extents read are kept in the new
struct hfsplus_overflow_extents, which sbi->alloc_file now holds
together with the allocation file's inode as struct hfsplus_alloc_file.
A missing or inconsistent extent record now fails the mount instead of
failing the bitmap reads later.

Tested on a KASAN and lockdep kernel: the reproducer completes without
a lockdep report and fsck.hfsplus reports the volume as OK, also after
allocating blocks whose bitmap page is mapped by the extent record; a
volume whose extent record of the allocation file starts at the wrong
block is rejected at mount; generic/001, 002, 013, 075 and 112 pass,
generic/091 fails as it does without this change.

Fixes: 1da177e4c3f4 ("Linux-2.6.12-rc2")
Reported-by: Zheng Zheng <fengaojigui88@gmail.com>
Closes: https://lore.kernel.org/linux-fsdevel/CAO-4RZ1a46EoJY7x6euiS+7aTOb-T9X62E9nGyToRcyvKU+eHg@mail.gmail.com/
Cc: stable@vger.kernel.org
cc: John Paul Adrian Glaubitz <glaubitz@physik.fu-berlin.de>
cc: Yangtao Li <frank.li@vivo.com>
cc: linux-fsdevel@vger.kernel.org
Signed-off-by: Viacheslav Dubeyko <slava@dubeyko.com>
---
 fs/hfsplus/bitmap.c     |   4 +-
 fs/hfsplus/extents.c    | 136 ++++++++++++++++++++++++++++++++++++----
 fs/hfsplus/hfsplus_fs.h |  14 ++++-
 fs/hfsplus/inode.c      |   4 +-
 fs/hfsplus/super.c      |  18 ++++--
 5 files changed, 153 insertions(+), 23 deletions(-)

diff --git a/fs/hfsplus/bitmap.c b/fs/hfsplus/bitmap.c
index 30178ea47362..62c39849e381 100644
--- a/fs/hfsplus/bitmap.c
+++ b/fs/hfsplus/bitmap.c
@@ -33,7 +33,7 @@ int hfsplus_block_allocate(struct super_block *sb, u32 size,
 
 	hfs_dbg("size %u, offset %u, len %u\n", size, offset, len);
 	mutex_lock(&sbi->alloc_mutex);
-	mapping = sbi->alloc_file->i_mapping;
+	mapping = sbi->alloc_file.inode->i_mapping;
 	page = read_mapping_page(mapping, offset / PAGE_CACHE_BITS, NULL);
 	if (IS_ERR(page)) {
 		start = size;
@@ -192,7 +192,7 @@ int hfsplus_block_free(struct super_block *sb, u32 offset, u32 count)
 		return -ENOENT;
 
 	mutex_lock(&sbi->alloc_mutex);
-	mapping = sbi->alloc_file->i_mapping;
+	mapping = sbi->alloc_file.inode->i_mapping;
 	pnr = offset / PAGE_CACHE_BITS;
 	page = read_mapping_page(mapping, pnr, NULL);
 	if (IS_ERR(page))
diff --git a/fs/hfsplus/extents.c b/fs/hfsplus/extents.c
index 924941440066..da6ab85a64ae 100644
--- a/fs/hfsplus/extents.c
+++ b/fs/hfsplus/extents.c
@@ -53,7 +53,7 @@ static u32 hfsplus_ext_find_block(struct hfsplus_extent *ext, u32 off)
 	int i;
 	u32 count;
 
-	for (i = 0; i < 8; ext++, i++) {
+	for (i = 0; i < HFSPLUS_FORK_EXTENT_COUNT; ext++, i++) {
 		count = be32_to_cpu(ext->block_count);
 		if (off < count)
 			return be32_to_cpu(ext->start_block) + off;
@@ -68,17 +68,18 @@ static int hfsplus_ext_block_count(struct hfsplus_extent *ext)
 	int i;
 	u32 count = 0;
 
-	for (i = 0; i < 8; ext++, i++)
+	for (i = 0; i < HFSPLUS_FORK_EXTENT_COUNT; ext++, i++)
 		count += be32_to_cpu(ext->block_count);
 	return count;
 }
 
 static u32 hfsplus_ext_lastblock(struct hfsplus_extent *ext)
 {
+	int last_index = HFSPLUS_FORK_EXTENT_COUNT - 1;
 	int i;
 
-	ext += 7;
-	for (i = 0; i < 7; ext--, i++)
+	ext += last_index;
+	for (i = 0; i < last_index; ext--, i++)
 		if (ext->block_count)
 			break;
 	return be32_to_cpu(ext->start_block) + be32_to_cpu(ext->block_count);
@@ -225,6 +226,102 @@ static int hfsplus_ext_read_extent(struct inode *inode, u32 block)
 	return res;
 }
 
+/*
+ * The allocation bitmap is read through the allocation file with
+ * sbi->alloc_mutex held, sometimes by a task that holds the extents
+ * B-tree's tree_lock because it is growing the B-tree. So mapping a
+ * block of the allocation file must not search the extents B-tree.
+ *
+ * The allocation file is not resized while the volume is mounted, so
+ * read the extents of it that are not in the volume header once, at
+ * mount time, and map its blocks from them.
+ */
+int hfsplus_ext_load_alloc_file(struct super_block *sb)
+{
+	struct hfsplus_sb_info *sbi = HFSPLUS_SB(sb);
+	struct hfsplus_alloc_file *alloc_file = &sbi->alloc_file;
+	struct inode *inode = alloc_file->inode;
+	struct hfsplus_inode_info *hip = HFSPLUS_I(inode);
+	struct hfsplus_extent *ext = NULL, *new;
+	struct hfs_find_data fd;
+	u32 block = hip->first_blocks;
+	u32 nr = 0;
+	int res;
+
+	if (block >= hip->alloc_blocks)
+		return 0;
+
+	res = hfs_find_init(sbi->ext_tree, &fd);
+	if (res)
+		return res;
+
+	while (block < hip->alloc_blocks) {
+		hfsplus_extent_rec rec;
+		u32 start_block, count;
+		u32 rest_blocks;
+
+		res = __hfsplus_ext_read_extent(&fd, rec, inode->i_ino, block,
+						HFSPLUS_TYPE_DATA);
+		if (res)
+			goto fail;
+
+		start_block = be32_to_cpu(fd.key->ext.start_block);
+		count = hfsplus_ext_block_count(rec);
+		rest_blocks = hip->alloc_blocks - block;
+
+		if (start_block != block || count == 0 || count > rest_blocks) {
+			res = -EIO;
+			goto fail;
+		}
+
+		new = krealloc_array(ext, nr + ARRAY_SIZE(rec), sizeof(*ext),
+				     GFP_KERNEL);
+		if (!new) {
+			res = -ENOMEM;
+			goto fail;
+		}
+
+		ext = new;
+		memcpy(ext + nr, rec, sizeof(rec));
+		nr += ARRAY_SIZE(rec);
+		block += count;
+	}
+
+	hfs_find_exit(&fd);
+	alloc_file->overflow.extents = ext;
+	alloc_file->overflow.count = nr;
+	return 0;
+
+fail:
+	hfs_find_exit(&fd);
+	kfree(ext);
+	pr_err("can't read the allocation file extents at block %u: %d\n",
+	       block, res);
+	return res == -ENOENT ? -EIO : res;
+}
+
+/*
+ * Map @ablock of the allocation file, which lies beyond its extents in
+ * the volume header. Returns 0 if it is not allocated.
+ */
+static u32 hfsplus_ext_alloc_file_block(struct super_block *sb, u32 ablock)
+{
+	struct hfsplus_alloc_file *alloc_file = &HFSPLUS_SB(sb)->alloc_file;
+	struct hfsplus_overflow_extents *overflow = &alloc_file->overflow;
+	u32 off = ablock - HFSPLUS_I(alloc_file->inode)->first_blocks;
+	u32 start_block, count;
+	u32 i;
+
+	for (i = 0; i < overflow->count; i++) {
+		start_block = be32_to_cpu(overflow->extents[i].start_block);
+		count = be32_to_cpu(overflow->extents[i].block_count);
+		if (off < count)
+			return start_block + off;
+		off -= count;
+	}
+	return 0;
+}
+
 /* Get a block at iblock for inode, possibly allocating if create */
 int hfsplus_get_block(struct inode *inode, sector_t iblock,
 		      struct buffer_head *bh_result, int create)
@@ -258,9 +355,22 @@ int hfsplus_get_block(struct inode *inode, sector_t iblock,
 		goto done;
 	}
 
-	if (inode->i_ino == HFSPLUS_EXT_CNID)
+	switch (inode->i_ino) {
+	case HFSPLUS_EXT_CNID:
 		return -EIO;
 
+	case HFSPLUS_ALLOC_CNID:
+		dblock = hfsplus_ext_alloc_file_block(sb, ablock);
+		if (!dblock)
+			return -EIO;
+		else
+			goto done;
+
+	default:
+		/* continue logic */
+		break;
+	}
+
 	mutex_lock(&hip->extents_lock);
 
 	/*
@@ -303,7 +413,7 @@ static void hfsplus_dump_extent(struct hfsplus_extent *extent)
 	int i;
 
 	hfs_dbg("extent   ");
-	for (i = 0; i < 8; i++)
+	for (i = 0; i < HFSPLUS_FORK_EXTENT_COUNT; i++)
 		hfs_dbg(" start_block %u, block_count %u",
 			be32_to_cpu(extent[i].start_block),
 			be32_to_cpu(extent[i].block_count));
@@ -317,7 +427,7 @@ static int hfsplus_add_extent(struct hfsplus_extent *extent, u32 offset,
 	int i;
 
 	hfsplus_dump_extent(extent);
-	for (i = 0; i < 8; extent++, i++) {
+	for (i = 0; i < HFSPLUS_FORK_EXTENT_COUNT; extent++, i++) {
 		count = be32_to_cpu(extent->block_count);
 		if (offset == count) {
 			start = be32_to_cpu(extent->start_block);
@@ -347,7 +457,7 @@ static int hfsplus_free_extents(struct super_block *sb,
 	int err = 0;
 
 	hfsplus_dump_extent(extent);
-	for (i = 0; i < 8; extent++, i++) {
+	for (i = 0; i < HFSPLUS_FORK_EXTENT_COUNT; extent++, i++) {
 		count = be32_to_cpu(extent->block_count);
 		if (offset == count)
 			goto found;
@@ -405,7 +515,7 @@ int hfsplus_free_fork(struct super_block *sb, u32 cnid,
 		return 0;
 
 	blocks = 0;
-	for (i = 0; i < 8; i++)
+	for (i = 0; i < HFSPLUS_FORK_EXTENT_COUNT; i++)
 		blocks += be32_to_cpu(fork->extents[i].block_count);
 
 	res = hfsplus_free_extents(sb, fork->extents, blocks, blocks);
@@ -445,11 +555,11 @@ int hfsplus_file_extend(struct inode *inode, bool zeroout)
 	u32 start, len, goal;
 	int res;
 
-	if (sbi->alloc_file->i_size * 8 <
+	if (sbi->alloc_file.inode->i_size * 8 <
 	    sbi->total_blocks - sbi->free_blocks + 8) {
 		/* extend alloc file */
 		pr_err_ratelimited("extend alloc file! (%llu,%u,%u)\n",
-				   sbi->alloc_file->i_size * 8,
+				   sbi->alloc_file.inode->i_size * 8,
 				   sbi->total_blocks, sbi->free_blocks);
 		return -ENOSPC;
 	}
@@ -517,7 +627,7 @@ int hfsplus_file_extend(struct inode *inode, bool zeroout)
 	if (!res) {
 		hip->alloc_blocks += len;
 		mutex_unlock(&hip->extents_lock);
-		hfsplus_mark_inode_dirty(HFSPLUS_SB(sb)->alloc_file,
+		hfsplus_mark_inode_dirty(HFSPLUS_SB(sb)->alloc_file.inode,
 					 HFSPLUS_I_ALLOC_DIRTY);
 		hfsplus_mark_inode_dirty(inode, HFSPLUS_I_ALLOC_DIRTY);
 		return 0;
@@ -637,7 +747,7 @@ void hfsplus_file_truncate(struct inode *inode)
 	hip->fs_blocks = (inode->i_size + sb->s_blocksize - 1) >>
 		sb->s_blocksize_bits;
 	inode_set_bytes(inode, hip->fs_blocks << sb->s_blocksize_bits);
-	hfsplus_mark_inode_dirty(HFSPLUS_SB(sb)->alloc_file,
+	hfsplus_mark_inode_dirty(HFSPLUS_SB(sb)->alloc_file.inode,
 				 HFSPLUS_I_ALLOC_DIRTY);
 	hfsplus_mark_inode_dirty(inode, HFSPLUS_I_ALLOC_DIRTY);
 }
diff --git a/fs/hfsplus/hfsplus_fs.h b/fs/hfsplus/hfsplus_fs.h
index dd88053cc9b3..9a304d946297 100644
--- a/fs/hfsplus/hfsplus_fs.h
+++ b/fs/hfsplus/hfsplus_fs.h
@@ -109,6 +109,17 @@ struct hfs_bnode {
 struct hfsplus_vh;
 struct hfs_btree;
 
+/* Extents of a special file that are not in the volume header */
+struct hfsplus_overflow_extents {
+	struct hfsplus_extent *extents;
+	u32 count;
+};
+
+struct hfsplus_alloc_file {
+	struct inode *inode;
+	struct hfsplus_overflow_extents overflow;
+};
+
 struct hfsplus_sb_info {
 	void *s_vhdr_buf;
 	struct hfsplus_vh *s_vhdr;
@@ -118,7 +129,7 @@ struct hfsplus_sb_info {
 	struct hfs_btree *cat_tree;
 	struct hfs_btree *attr_tree;
 	atomic_t attr_tree_state;
-	struct inode *alloc_file;
+	struct hfsplus_alloc_file alloc_file;
 	struct inode *hidden_dir;
 	struct nls_table *nls;
 
@@ -440,6 +451,7 @@ extern const struct file_operations hfsplus_dir_operations;
 int hfsplus_ext_cmp_key(const hfsplus_btree_key *k1,
 			const hfsplus_btree_key *k2);
 int hfsplus_ext_write_extent(struct inode *inode);
+int hfsplus_ext_load_alloc_file(struct super_block *sb);
 int hfsplus_get_block(struct inode *inode, sector_t iblock,
 		      struct buffer_head *bh_result, int create);
 int hfsplus_free_fork(struct super_block *sb, u32 cnid,
diff --git a/fs/hfsplus/inode.c b/fs/hfsplus/inode.c
index 8073fb99217d..e231da2d8a2b 100644
--- a/fs/hfsplus/inode.c
+++ b/fs/hfsplus/inode.c
@@ -410,9 +410,9 @@ int hfsplus_file_fsync(struct file *file, loff_t start, loff_t end,
 	}
 
 	if (test_and_clear_bit(HFSPLUS_I_ALLOC_DIRTY,
-				&HFSPLUS_I(sbi->alloc_file)->flags)) {
+				&HFSPLUS_I(sbi->alloc_file.inode)->flags)) {
 		clear_bit(HFSPLUS_I_ALLOC_DIRTY, &hip->flags);
-		error2 = filemap_write_and_wait(sbi->alloc_file->i_mapping);
+		error2 = filemap_write_and_wait(sbi->alloc_file.inode->i_mapping);
 		if (!error)
 			error = error2;
 	}
diff --git a/fs/hfsplus/super.c b/fs/hfsplus/super.c
index 33594e1f8367..e568a5508b5e 100644
--- a/fs/hfsplus/super.c
+++ b/fs/hfsplus/super.c
@@ -298,7 +298,7 @@ static int hfsplus_sync_fs(struct super_block *sb, int wait)
 		if (!error)
 			error = error2;
 	}
-	error2 = filemap_write_and_wait(sbi->alloc_file->i_mapping);
+	error2 = filemap_write_and_wait(sbi->alloc_file.inode->i_mapping);
 	if (!error)
 		error = error2;
 
@@ -325,7 +325,7 @@ static void delayed_sync_fs(struct work_struct *work)
 	sbi->work_queued = 0;
 	spin_unlock(&sbi->work_lock);
 
-	err = hfsplus_sync_fs(sbi->alloc_file->i_sb, 1);
+	err = hfsplus_sync_fs(sbi->alloc_file.inode->i_sb, 1);
 	if (err)
 		pr_err("delayed sync fs err %d\n", err);
 }
@@ -399,7 +399,8 @@ static void hfsplus_put_super(struct super_block *sb)
 	if (!sb_rdonly(sb) && sbi->s_vhdr)
 		hfsplus_commit_clean_volume_header(sb);
 
-	iput(sbi->alloc_file);
+	iput(sbi->alloc_file.inode);
+	kfree(sbi->alloc_file.overflow.extents);
 	iput(sbi->hidden_dir);
 	hfs_btree_close(sbi->attr_tree);
 	hfs_btree_close(sbi->cat_tree);
@@ -754,7 +755,11 @@ static int hfsplus_fill_super(struct super_block *sb, struct fs_context *fc)
 		err = PTR_ERR(inode);
 		goto out_close_attr_tree;
 	}
-	sbi->alloc_file = inode;
+	sbi->alloc_file.inode = inode;
+
+	err = hfsplus_ext_load_alloc_file(sb);
+	if (err)
+		goto out_put_alloc_file;
 
 	/* Load the root directory */
 	root = hfsplus_iget(sb, HFSPLUS_ROOT_CNID);
@@ -816,7 +821,10 @@ static int hfsplus_fill_super(struct super_block *sb, struct fs_context *fc)
 	dput(sb->s_root);
 	sb->s_root = NULL;
 out_put_alloc_file:
-	iput(sbi->alloc_file);
+	iput(sbi->alloc_file.inode);
+	kfree(sbi->alloc_file.overflow.extents);
+	sbi->alloc_file.overflow.extents = NULL;
+	sbi->alloc_file.overflow.count = 0;
 out_close_attr_tree:
 	hfs_btree_close(sbi->attr_tree);
 out_close_cat_tree:
-- 
2.53.0


  parent reply	other threads:[~2026-11-19 23:41 UTC|newest]

Thread overview: 6+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2026-11-19 23:41 [PATCH 0/5] hfsplus: fix locking and validation of the special files Viacheslav Dubeyko
2026-11-19 23:41 ` [PATCH 1/5] hfsplus: reject special files larger than their allocation at mount Viacheslav Dubeyko
2026-11-19 23:41 ` Viacheslav Dubeyko [this message]
2026-11-19 23:41 ` [PATCH 3/5] hfsplus: give the special files their own extents_lock lockdep class Viacheslav Dubeyko
2026-11-19 23:41 ` [PATCH 4/5] hfsplus: reject an allocation bitmap that does not cover the volume Viacheslav Dubeyko
2026-11-19 23:41 ` [PATCH 5/5] hfsplus: name the constants of the allocation bitmap check Viacheslav Dubeyko

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20261119234112.720963-3-slava@dubeyko.com \
    --to=slava@dubeyko.com \
    --cc=fengaojigui88@gmail.com \
    --cc=frank.li@vivo.com \
    --cc=glaubitz@physik.fu-berlin.de \
    --cc=linux-fsdevel@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=stable@vger.kernel.org \
    --cc=vdubeyko@coreweave.com \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox

all inboxes | Powered by JetHome®