Re: [PATCH v5 1/2] hfsplus: refactor b-tree map page access and add node-type validation

[Viacheslav Dubeyko]

On Sat, 2026-02-28 at 17:53 +0530, Shardul Bankar wrote:
> In HFS+ b-trees, the node allocation bitmap is stored across multiple
> records. The first chunk resides in the b-tree Header Node at record
> index 2, while all subsequent chunks are stored in dedicated Map Nodes
> at record index 0.
> 
> This structural quirk forces callers like hfs_bmap_alloc() and
> hfs_bmap_free() to duplicate boilerplate code to validate offsets, correct
> lengths, and map the underlying pages via kmap_local_page(). There is
> also currently no strict node-type validation before reading these
> records, leaving the allocator vulnerable if a corrupted image points a
> map linkage to an Index or Leaf node.
> 
> Introduce a unified bit-level API to encapsulate the map record access:
> 1. A new 'struct hfs_bmap_ctx' to cleanly pass state and safely handle
>    page math across all architectures.
> 2. 'hfs_bmap_get_map_page()': Automatically validates node types
>    (HFS_NODE_HEADER vs HFS_NODE_MAP), infers the correct record index,
>    and handles page-boundary math for records that span multiple pages.
> 3. 'hfs_bmap_test_bit()' and 'hfs_bmap_clear_bit()': Clean wrappers that
>    internally handle page mapping/unmapping for single-bit operations.
> 
> Refactor hfs_bmap_alloc() and hfs_bmap_free() to utilize this new API.
> This deduplicates the allocator logic, hardens the map traversal against
> fuzzed images, and provides the exact abstractions needed for upcoming
> mount-time validation checks.
> 
> Signed-off-by: Shardul Bankar <shardul.b@xxxxxxxxxxxxxxxxxx>
> ---
>  fs/hfsplus/btree.c         | 186 +++++++++++++++++++++++++++----------
>  include/linux/hfs_common.h |   2 +
>  2 files changed, 141 insertions(+), 47 deletions(-)
> 
> diff --git a/fs/hfsplus/btree.c b/fs/hfsplus/btree.c
> index 1220a2f22737..87650e23cd65 100644
> --- a/fs/hfsplus/btree.c
> +++ b/fs/hfsplus/btree.c
> @@ -129,6 +129,116 @@ u32 hfsplus_calc_btree_clump_size(u32 block_size, u32 node_size,
>  	return clump_size;
>  }
>  
> +/* Context for iterating b-tree map pages */

If we have some comments here, then let's add the description of fields.

> +struct hfs_bmap_ctx {
> +	unsigned int page_idx;
> +	unsigned int off;
> +	u16 len;
> +};
> +
> +/*
> + * Maps the specific page containing the requested byte offset within the map
> + * record.
> + * Automatically handles the difference between header and map nodes.
> + * Returns the mapped data pointer, or an ERR_PTR on failure.
> + * Note: The caller is responsible for calling kunmap_local(data).
> + */
> +static u8 *hfs_bmap_get_map_page(struct hfs_bnode *node, struct hfs_bmap_ctx *ctx,
> +				u32 byte_offset)
> +{
> +	u16 rec_idx, off16;
> +	unsigned int page_off; /* 32-bit math prevents LKP overflow warnings */

Do we really need this comment?

> +
> +	if (node->this == HFSPLUS_TREE_HEAD) {
> +		if (node->type != HFS_NODE_HEADER) {
> +			pr_err("hfsplus: invalid btree header node\n");
> +			return ERR_PTR(-EIO);
> +		}
> +		rec_idx = HFSPLUS_BTREE_HDR_MAP_REC_INDEX;
> +	} else {
> +		if (node->type != HFS_NODE_MAP) {
> +			pr_err("hfsplus: invalid btree map node\n");
> +			return ERR_PTR(-EIO);
> +		}
> +		rec_idx = HFSPLUS_BTREE_MAP_NODE_REC_INDEX;
> +	}
> +
> +	ctx->len = hfs_brec_lenoff(node, rec_idx, &off16);
> +	if (!ctx->len)
> +		return ERR_PTR(-ENOENT);
> +
> +	if (!is_bnode_offset_valid(node, off16))
> +		return ERR_PTR(-EIO);
> +
> +	ctx->len = check_and_correct_requested_length(node, off16, ctx->len);
> +
> +	if (byte_offset >= ctx->len)
> +		return ERR_PTR(-EINVAL);
> +
> +	page_off = off16 + node->page_offset + byte_offset;
> +	ctx->page_idx = page_off >> PAGE_SHIFT;
> +	ctx->off = page_off & ~PAGE_MASK;
> +
> +	return kmap_local_page(node->page[ctx->page_idx]);

This pattern makes me really nervous. :) What if we can calculate the struct
hfs_bmap_ctx *ctx in this function only. And, then, caller will use
kmap_local_page()/kunmap_local() in one place.

> +}
> +
> +/**
> + * hfs_bmap_test_bit - test a bit in the b-tree map
> + * @node: the b-tree node containing the map record
> + * @bit_idx: the bit index relative to the start of the map record

This sounds slightly confusing. Is it bit starting from the whole map or from
particular map's portion?

> + *
> + * Returns 1 if set, 0 if clear, or a negative error code on failure.
> + */
> +static int hfs_bmap_test_bit(struct hfs_bnode *node, u32 bit_idx)
> +{
> +	struct hfs_bmap_ctx ctx;
> +	u8 *data, byte, m;

I think we can use bmap instead of data. The bmap name can show the nature of
data here. Do you agree?

I can follow what byte name means. Frankly speaking, I don't know why m name is
used. :)

> +	int res;

I am not sure that you are really need this variable.

> +
> +	data = hfs_bmap_get_map_page(node, &ctx, bit_idx / 8);

What's about BITS_PER_BYTE instead of hardcoded 8?

> +	if (IS_ERR(data))
> +		return PTR_ERR(data);
> +
> +	byte = data[ctx.off];
> +	kunmap_local(data);
> +
> +	/* In HFS+ bitmaps, bit 0 is the MSB (0x80) */
> +	m = 1 << (~bit_idx & 7);

I am not sure that this calculation is correct. Because bit_idx is absolute
index in the whole map but this operation is inside of particular portion of the
map. Are you sure that this logic will be correct if we have b-tree map in
several nodes?

> +	res = (byte & m) ? 1 : 0;

You can simply return this statement.

> +
> +	return res;
> +}
> +
> +/**
> + * hfs_bmap_clear_bit - clear a bit in the b-tree map
> + * @node: the b-tree node containing the map record
> + * @bit_idx: the bit index relative to the start of the map record
> + *
> + * Returns 0 on success, -EALREADY if already clear, or negative error code.
> + */
> +static int hfs_bmap_clear_bit(struct hfs_bnode *node, u32 bit_idx)

I have the same remarks and concerns for this method too. Please, see my remarks
above.

> +{
> +	struct hfs_bmap_ctx ctx;
> +	u8 *data, m;
> +
> +	data = hfs_bmap_get_map_page(node, &ctx, bit_idx / 8);
> +	if (IS_ERR(data))
> +		return PTR_ERR(data);
> +
> +	m = 1 << (~bit_idx & 7);
> +
> +	if (!(data[ctx.off] & m)) {
> +		kunmap_local(data);
> +		return -EALREADY;

I am not sure about this error code:

#define	EALREADY	114	/* Operation already in progress */

It sounds more like -EINVAL.

Thanks,
Slava.

> +	}
> +
> +	data[ctx.off] &= ~m;
> +	set_page_dirty(node->page[ctx.page_idx]);
> +	kunmap_local(data);
> +
> +	return 0;
> +}
> +
>  /* Get a reference to a B*Tree and do some initial checks */
>  struct hfs_btree *hfs_btree_open(struct super_block *sb, u32 id)
>  {
> @@ -374,11 +484,8 @@ int hfs_bmap_reserve(struct hfs_btree *tree, u32 rsvd_nodes)
>  struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree)
>  {
>  	struct hfs_bnode *node, *next_node;
> -	struct page **pagep;
> +	struct hfs_bmap_ctx ctx;
>  	u32 nidx, idx;
> -	unsigned off;
> -	u16 off16;
> -	u16 len;
>  	u8 *data, byte, m;
>  	int i, res;
>  
> @@ -390,30 +497,25 @@ struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree)
>  	node = hfs_bnode_find(tree, nidx);
>  	if (IS_ERR(node))
>  		return node;
> -	len = hfs_brec_lenoff(node, 2, &off16);
> -	off = off16;
>  
> -	if (!is_bnode_offset_valid(node, off)) {
> +	data = hfs_bmap_get_map_page(node, &ctx, 0);
> +	if (IS_ERR(data)) {
> +		res = PTR_ERR(data);
>  		hfs_bnode_put(node);
> -		return ERR_PTR(-EIO);
> +		return ERR_PTR(res);
>  	}
> -	len = check_and_correct_requested_length(node, off, len);
>  
> -	off += node->page_offset;
> -	pagep = node->page + (off >> PAGE_SHIFT);
> -	data = kmap_local_page(*pagep);
> -	off &= ~PAGE_MASK;
>  	idx = 0;
>  
>  	for (;;) {
> -		while (len) {
> -			byte = data[off];
> +		while (ctx.len) {
> +			byte = data[ctx.off];
>  			if (byte != 0xff) {
>  				for (m = 0x80, i = 0; i < 8; m >>= 1, i++) {
>  					if (!(byte & m)) {
>  						idx += i;
> -						data[off] |= m;
> -						set_page_dirty(*pagep);
> +						data[ctx.off] |= m;
> +						set_page_dirty(node->page[ctx.page_idx]);
>  						kunmap_local(data);
>  						tree->free_nodes--;
>  						mark_inode_dirty(tree->inode);
> @@ -423,13 +525,13 @@ struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree)
>  					}
>  				}
>  			}
> -			if (++off >= PAGE_SIZE) {
> +			if (++ctx.off >= PAGE_SIZE) {
>  				kunmap_local(data);
> -				data = kmap_local_page(*++pagep);
> -				off = 0;
> +				data = kmap_local_page(node->page[++ctx.page_idx]);
> +				ctx.off = 0;
>  			}
>  			idx += 8;
> -			len--;
> +			ctx.len--;
>  		}
>  		kunmap_local(data);
>  		nidx = node->next;
> @@ -443,22 +545,21 @@ struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree)
>  			return next_node;
>  		node = next_node;
>  
> -		len = hfs_brec_lenoff(node, 0, &off16);
> -		off = off16;
> -		off += node->page_offset;
> -		pagep = node->page + (off >> PAGE_SHIFT);
> -		data = kmap_local_page(*pagep);
> -		off &= ~PAGE_MASK;
> +		data = hfs_bmap_get_map_page(node, &ctx, 0);
> +		if (IS_ERR(data)) {
> +			res = PTR_ERR(data);
> +			hfs_bnode_put(node);
> +			return ERR_PTR(res);
> +		}
>  	}
>  }
>  
>  void hfs_bmap_free(struct hfs_bnode *node)
>  {
>  	struct hfs_btree *tree;
> -	struct page *page;
>  	u16 off, len;
>  	u32 nidx;
> -	u8 *data, byte, m;
> +	int res;
>  
>  	hfs_dbg("node %u\n", node->this);
>  	BUG_ON(!node->this);
> @@ -495,24 +596,15 @@ void hfs_bmap_free(struct hfs_bnode *node)
>  		}
>  		len = hfs_brec_lenoff(node, 0, &off);
>  	}
> -	off += node->page_offset + nidx / 8;
> -	page = node->page[off >> PAGE_SHIFT];
> -	data = kmap_local_page(page);
> -	off &= ~PAGE_MASK;
> -	m = 1 << (~nidx & 7);
> -	byte = data[off];
> -	if (!(byte & m)) {
> -		pr_crit("trying to free free bnode "
> -				"%u(%d)\n",
> -			node->this, node->type);
> -		kunmap_local(data);
> -		hfs_bnode_put(node);
> -		return;
> +
> +	res = hfs_bmap_clear_bit(node, nidx);
> +	if (res == -EALREADY) {
> +		pr_crit("trying to free free bnode %u(%d)\n",
> +				node->this, node->type);
> +	} else if (!res) {
> +		tree->free_nodes++;
> +		mark_inode_dirty(tree->inode);
>  	}
> -	data[off] = byte & ~m;
> -	set_page_dirty(page);
> -	kunmap_local(data);
> +
>  	hfs_bnode_put(node);
> -	tree->free_nodes++;
> -	mark_inode_dirty(tree->inode);
>  }
> diff --git a/include/linux/hfs_common.h b/include/linux/hfs_common.h
> index dadb5e0aa8a3..be24c687858e 100644
> --- a/include/linux/hfs_common.h
> +++ b/include/linux/hfs_common.h
> @@ -510,6 +510,8 @@ struct hfs_btree_header_rec {
>  #define HFSPLUS_NODE_MXSZ			32768
>  #define HFSPLUS_ATTR_TREE_NODE_SIZE		8192
>  #define HFSPLUS_BTREE_HDR_NODE_RECS_COUNT	3
> +#define HFSPLUS_BTREE_HDR_MAP_REC_INDEX		2	/* Map (bitmap) record in Header node */
> +#define HFSPLUS_BTREE_MAP_NODE_REC_INDEX	0	/* Map record in Map Node */
>  #define HFSPLUS_BTREE_HDR_USER_BYTES		128
>  
>  /* btree key type */