Re: [PATCH] hfsplus: validate B-tree record offset table

[Viacheslav Dubeyko]

On Wed, 2026-07-01 at 13:50 +0800, Jiaming Zhang wrote:
> A crafted HFS+ image can contain a corrupted B-tree node. The node
> descriptor
> may contain a record count that does not fit in the node, and record
> offsets may
> be unordered, unaligned, outside the node, or point into the offset
> table
> itself.
> 
> Several B-tree helpers consume these on-disk fields before validating
> them:
> hfs_bnode_dump() can walk past the offset table when num_recs is
> corrupted,
> hfs_brec_lenoff() can produce an underflowed length or a record range
> that
> overlaps the offset table. This can make the unlink/writeback path
> repeatedly
> call hfs_bnode_read_u16() with invalid offsets while holding the HFS+
> B-tree
> lock, producing a flood of "requested invalid offset" messages. Other
> writeback
> workers then block on tree->tree_lock and the system reports tasks
> hung in
> hfsplus_write_inode().
> 
> Reject corrupted B-tree metadata earlier: validate num_recs against
> the node
> size before walking the record offset table, reject record offsets
> that are
> unordered, unaligned, outside the node, or overlapping the offset
> table, stop
> B-tree record walkers on invalid records, and avoid decrementing an
> already-zero
> leaf_count.
> 
> Fixes: 1da177e4c3f4 ("Linux-2.6.12-rc2")
> Closes:
> https://lore.kernel.org/lkml/CANypQFb_2TqKGrztAXj5m0_v+QChxXDnQVeifzV8J25Vuju10Q@xxxxxxxxxxxxxx/
> Assisted-by: Codex:gpt-5.5-xhigh
> Signed-off-by: Jiaming Zhang <r772577952@xxxxxxxxx>
> ---
>  fs/hfsplus/bfind.c      | 12 +++++++++---
>  fs/hfsplus/bnode.c      | 15 +++++++++++++--
>  fs/hfsplus/brec.c       | 35 ++++++++++++++++++++++++++++++-----
>  fs/hfsplus/hfsplus_fs.h | 18 ++++++++++++++++++
>  4 files changed, 70 insertions(+), 10 deletions(-)
> 
> diff --git a/fs/hfsplus/bfind.c b/fs/hfsplus/bfind.c
> index 9a55fa6d5294..ace9ba027a9d 100644
> --- a/fs/hfsplus/bfind.c
> +++ b/fs/hfsplus/bfind.c
> @@ -112,11 +112,13 @@ int __hfs_brec_find(struct hfs_bnode *bnode,
> struct hfs_find_data *fd,
>  	b = 0;
>  	e = bnode->num_recs - 1;
>  	res = -ENOENT;
> +	if (!bnode->num_recs)

Do you mean bnode->num_recs == 0?

> +		return res;

In majority of cases, we check fd->record:

	__hfs_brec_find(parent, fd, hfs_find_rec_by_key);
	if (fd->record < 0)
		return -ENOENT;

So, this is not completely correct to simply return error because, we
do not check the returned error code.

>  	do {
>  		rec = (e + b) / 2;
>  		len = hfs_brec_lenoff(bnode, rec, &off);
>  		keylen = hfs_brec_keylen(bnode, rec);
> -		if (keylen == 0) {
> +		if (!keylen || keylen >= len) {

I really dislike this !keylen pattern is used not for pointer. Should
we expect that that keylen == len? Then, we could use keylen != len
here.

>  			res = -EINVAL;
>  			goto fail;
>  		}
> @@ -130,7 +132,7 @@ int __hfs_brec_find(struct hfs_bnode *bnode,
> struct hfs_find_data *fd,
>  	if (rec != e && e >= 0) {
>  		len = hfs_brec_lenoff(bnode, e, &off);
>  		keylen = hfs_brec_keylen(bnode, e);
> -		if (keylen == 0) {
> +		if (!keylen || keylen >= len) {

Ditto.

>  			res = -EINVAL;
>  			goto fail;
>  		}
> @@ -232,6 +234,10 @@ int hfs_brec_goto(struct hfs_find_data *fd, int
> cnt)
>  
>  	bnode = fd->bnode;
>  	tree = bnode->tree;
> +	if (!bnode->num_recs) {

I dislike this !bnode->num_recs.

> +		res = -ENOENT;
> +		goto out;
> +	}
>  
>  	if (cnt < 0) {
>  		cnt = -cnt;
> @@ -274,7 +280,7 @@ int hfs_brec_goto(struct hfs_find_data *fd, int
> cnt)
>  
>  	len = hfs_brec_lenoff(bnode, fd->record, &off);
>  	keylen = hfs_brec_keylen(bnode, fd->record);
> -	if (keylen == 0) {
> +	if (!keylen || keylen >= len) {

Ditto.

>  		res = -EINVAL;
>  		goto out;
>  	}
> diff --git a/fs/hfsplus/bnode.c b/fs/hfsplus/bnode.c
> index d088fb7eb0df..df406f75a5b3 100644
> --- a/fs/hfsplus/bnode.c
> +++ b/fs/hfsplus/bnode.c
> @@ -352,15 +352,22 @@ void hfs_bnode_dump(struct hfs_bnode *node)
>  	struct hfs_bnode_desc desc;
>  	__be32 cnid;
>  	int i, off, key_off;
> +	u16 num_recs;
>  
>  	hfs_dbg("node %d\n", node->this);
>  	hfs_bnode_read(node, &desc, 0, sizeof(desc));
> +	num_recs = be16_to_cpu(desc.num_recs);
>  	hfs_dbg("next %d, prev %d, type %d, height %d, num_recs
> %d\n",
>  		be32_to_cpu(desc.next), be32_to_cpu(desc.prev),
> -		desc.type, desc.height, be16_to_cpu(desc.num_recs));
> +		desc.type, desc.height, num_recs);
> +
> +	if (!hfs_bnode_num_recs_valid(node, num_recs)) {
> +		hfs_dbg("invalid num_recs %u\n", num_recs);
> +		return;
> +	}
>  
>  	off = node->tree->node_size - 2;
> -	for (i = be16_to_cpu(desc.num_recs); i >= 0; off -= 2, i--)
> {
> +	for (i = num_recs; i >= 0; off -= 2, i--) {
>  		key_off = hfs_bnode_read_u16(node, off);
>  		hfs_dbg(" key_off %d", key_off);
>  		if (i && node->type == HFS_NODE_INDEX) {
> @@ -579,6 +586,9 @@ struct hfs_bnode *hfs_bnode_find(struct hfs_btree
> *tree, u32 num)
>  		goto node_error;
>  	}
>  
> +	if (!hfs_bnode_num_recs_valid(node, node->num_recs))
> +		goto node_error;
> +
>  	rec_off = tree->node_size - 2;
>  	off = hfs_bnode_read_u16(node, rec_off);
>  	if (off != sizeof(struct hfs_bnode_desc))
> @@ -588,6 +598,7 @@ struct hfs_bnode *hfs_bnode_find(struct hfs_btree
> *tree, u32 num)
>  		next_off = hfs_bnode_read_u16(node, rec_off);
>  		if (next_off <= off ||
>  		    next_off > tree->node_size ||
> +		    next_off > rec_off ||
>  		    next_off & 1)
>  			goto node_error;
>  		entry_size = next_off - off;
> diff --git a/fs/hfsplus/brec.c b/fs/hfsplus/brec.c
> index e3df89284079..dce397be9151 100644
> --- a/fs/hfsplus/brec.c
> +++ b/fs/hfsplus/brec.c
> @@ -20,12 +20,27 @@ static int hfs_btree_inc_height(struct hfs_btree
> *);
>  u16 hfs_brec_lenoff(struct hfs_bnode *node, u16 rec, u16 *off)
>  {
>  	__be16 retval[2];
> -	u16 dataoff;
> +	u16 data_off;
> +	u16 next_off;
>  
> -	dataoff = node->tree->node_size - (rec + 2) * 2;
> -	hfs_bnode_read(node, retval, dataoff, 4);
> +	if (rec >= node->num_recs ||
> +		!hfs_bnode_num_recs_valid(node, node->num_recs)) {

Ditto. We need static inline function for such check that can be reused
in multiple places.

> +		*off = 0;
> +		return 0;
> +	}
> +
> +	data_off = node->tree->node_size - (rec + 2) * 2;
> +	hfs_bnode_read(node, retval, data_off, 4);
>  	*off = be16_to_cpu(retval[1]);
> -	return be16_to_cpu(retval[0]) - *off;
> +	next_off = be16_to_cpu(retval[0]);
> +	if (*off < sizeof(struct hfs_bnode_desc) ||
> +		*off & 1 ||
> +		next_off <= *off ||
> +		next_off > node->tree->node_size ||
> +		next_off > data_off ||
> +		next_off & 1)

It looks like a static inline function for the check. I dislike such
multi-line check logic.

> +		return 0;
> +	return next_off - *off;
>  }
>  
>  /* Get the length of the key from a keyed record */
> @@ -35,6 +50,9 @@ u16 hfs_brec_keylen(struct hfs_bnode *node, u16
> rec)
>  
>  	if (node->type != HFS_NODE_INDEX && node->type !=
> HFS_NODE_LEAF)
>  		return 0;
> +	if (rec >= node->num_recs ||
> +		!hfs_bnode_num_recs_valid(node, node->num_recs))

Ditto.

> +		return 0;
>  
>  	if ((node->type == HFS_NODE_INDEX) &&
>  	   !(node->tree->attributes & HFS_TREE_VARIDXKEYS) &&
> @@ -43,7 +61,7 @@ u16 hfs_brec_keylen(struct hfs_bnode *node, u16
> rec)
>  	} else {
>  		recoff = hfs_bnode_read_u16(node,
>  			node->tree->node_size - (rec + 1) * 2);
> -		if (!recoff)
> +		if (recoff < sizeof(struct hfs_bnode_desc) || recoff
> & 1)

I don't quite follow what this check means. Could we rework it somehow?

>  			return 0;
>  		if (recoff > node->tree->node_size - 2) {
>  			pr_err("recoff %d too large\n", recoff);
> @@ -185,10 +203,17 @@ int hfs_brec_remove(struct hfs_find_data *fd)
>  	tree = fd->tree;
>  	node = fd->bnode;
>  again:
> +	if (fd->record < 0 ||
> +		fd->record >= node->num_recs ||

I think it makes sense to call hfs_bnode_num_recs_valid() before
checking fd->record.

> +		!hfs_bnode_num_recs_valid(node, node->num_recs))

It looks like method of fd->record. I suggest to introduce static
inline method of fd->record. Could we reuse this method for another
cases?

> +		return -EIO;
> +
>  	rec_off = tree->node_size - (fd->record + 2) * 2;
>  	end_off = tree->node_size - (node->num_recs + 1) * 2;
>  
>  	if (node->type == HFS_NODE_LEAF) {
> +		if (!tree->leaf_count)

Ditto. I dislike this !tree->leaf_count pattern.

> +			return -EIO;
>  		tree->leaf_count--;
>  		mark_inode_dirty(tree->inode);
>  	}
> diff --git a/fs/hfsplus/hfsplus_fs.h b/fs/hfsplus/hfsplus_fs.h
> index ec04b82ad927..8b2f2041b8b9 100644
> --- a/fs/hfsplus/hfsplus_fs.h
> +++ b/fs/hfsplus/hfsplus_fs.h
> @@ -587,6 +587,24 @@ bool is_bnode_offset_valid(struct hfs_bnode
> *node, u32 off)
>  	return is_valid;
>  }
>  
> +static inline
> +bool hfs_bnode_num_recs_valid(struct hfs_bnode *node, u16 num_recs)

What the point to provide num_recs? You can access it by node-
>num_recs.

> +{
> +	u32 node_size;
> +	u32 offs_size;
> +
> +	if (!node || !node->tree)
> +		return false;
> +
> +	node_size = node->tree->node_size;
> +	if (node_size < sizeof(struct hfs_bnode_desc) +
> sizeof(__be16))

You use sizeof(__be16) several times. Also, nobody can follow why you
need to make this addition. So, you need to introduce the local
variable with good name.

> +		return false;
> +
> +	offs_size = ((u32)num_recs + 1) * sizeof(__be16);

Ditto.

> +
> +	return offs_size <= node_size - sizeof(struct
> hfs_bnode_desc);

It cannot cover all potential corruptions. Because, offs_size could be
smaller one but still to overlap with node's content.

Thanks,
Slava.

> +}
> +
>  static inline
>  u32 check_and_correct_requested_length(struct hfs_bnode *node, u32
> off, u32 len)
>  {