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

[Shardul Bankar]

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 */
+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 */
+
+	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]);
+}
+
+/**
+ * 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
+ *
+ * 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;
+	int res;
+
+	data = hfs_bmap_get_map_page(node, &ctx, bit_idx / 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);
+	res = (byte & m) ? 1 : 0;
+
+	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)
+{
+	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;
+	}
+
+	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 */
-- 
2.34.1