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,
handles page-boundary math, and returns the unmapped `struct page *`
directly to the caller to avoid asymmetric mappings.
3. `hfs_bmap_clear_bit()`: A clean wrapper that internally handles 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@mpiricsoftware.com>
---
fs/hfsplus/btree.c | 169 ++++++++++++++++++++++++++-----------
include/linux/hfs_common.h | 2 +
2 files changed, 124 insertions(+), 47 deletions(-)
diff --git a/fs/hfsplus/btree.c b/fs/hfsplus/btree.c
index 1220a2f22737..64d168347b4b 100644
--- a/fs/hfsplus/btree.c
+++ b/fs/hfsplus/btree.c
@@ -129,6 +129,95 @@ u32 hfsplus_calc_btree_clump_size(u32 block_size, u32 node_size,
return clump_size;
}
+/* Context for iterating b-tree map pages
+ * @page_idx: The index of the page within the b-node's page array
+ * @off: The byte offset within the mapped page
+ * @len: The remaining length of the map record
+ */
+struct hfs_bmap_ctx {
+ unsigned int page_idx;
+ unsigned int off;
+ u16 len;
+};
+
+/*
+ * Finds the specific page containing the requested byte offset within the map
+ * record. Automatically handles the difference between header and map nodes.
+ * Returns the struct page pointer, or an ERR_PTR on failure.
+ * Note: The caller is responsible for mapping/unmapping the returned page.
+ */
+static struct page *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;
+
+ 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 = (u32)off16 + node->page_offset + byte_offset;
+ ctx->page_idx = page_off >> PAGE_SHIFT;
+ ctx->off = page_off & ~PAGE_MASK;
+
+ return node->page[ctx->page_idx];
+}
+
+/**
+ * hfs_bmap_clear_bit - clear a bit in the b-tree map
+ * @node: the b-tree node containing the map record
+ * @node_bit_idx: the relative bit index within the node's map record
+ *
+ * Returns 0 on success, -EINVAL if already clear, or negative error code.
+ */
+static int hfs_bmap_clear_bit(struct hfs_bnode *node, u32 node_bit_idx)
+{
+ struct hfs_bmap_ctx ctx;
+ struct page *page;
+ u8 *bmap, mask;
+
+ page = hfs_bmap_get_map_page(node, &ctx, node_bit_idx / BITS_PER_BYTE);
+ if (IS_ERR(page))
+ return PTR_ERR(page);
+
+ bmap = kmap_local_page(page);
+
+ mask = 1 << (7 - (node_bit_idx % BITS_PER_BYTE));
+
+ if (!(bmap[ctx.off] & mask)) {
+ kunmap_local(bmap);
+ return -EINVAL;
+ }
+
+ bmap[ctx.off] &= ~mask;
+ set_page_dirty(page);
+ kunmap_local(bmap);
+
+ 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 +463,9 @@ 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;
+ struct page *page;
u32 nidx, idx;
- unsigned off;
- u16 off16;
- u16 len;
u8 *data, byte, m;
int i, res;
@@ -390,30 +477,26 @@ 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)) {
+ page = hfs_bmap_get_map_page(node, &ctx, 0);
+ if (IS_ERR(page)) {
+ res = PTR_ERR(page);
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;
+ data = kmap_local_page(page);
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(page);
kunmap_local(data);
tree->free_nodes--;
mark_inode_dirty(tree->inode);
@@ -423,13 +506,14 @@ 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;
+ page = node->page[++ctx.page_idx];
+ data = kmap_local_page(page);
+ ctx.off = 0;
}
idx += 8;
- len--;
+ ctx.len--;
}
kunmap_local(data);
nidx = node->next;
@@ -443,22 +527,22 @@ 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;
+ page = hfs_bmap_get_map_page(node, &ctx, 0);
+ if (IS_ERR(page)) {
+ res = PTR_ERR(page);
+ hfs_bnode_put(node);
+ return ERR_PTR(res);
+ }
+ data = kmap_local_page(page);
}
}
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 +579,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 == -EINVAL) {
+ 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.1On Wed, 2026-03-18 at 13:08 +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,
> handles page-boundary math, and returns the unmapped `struct page
> *`
> directly to the caller to avoid asymmetric mappings.
> 3. `hfs_bmap_clear_bit()`: A clean wrapper that internally handles
> 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@mpiricsoftware.com>
> ---
> fs/hfsplus/btree.c | 169 ++++++++++++++++++++++++++---------
> --
> include/linux/hfs_common.h | 2 +
> 2 files changed, 124 insertions(+), 47 deletions(-)
>
> diff --git a/fs/hfsplus/btree.c b/fs/hfsplus/btree.c
> index 1220a2f22737..64d168347b4b 100644
> --- a/fs/hfsplus/btree.c
> +++ b/fs/hfsplus/btree.c
> @@ -129,6 +129,95 @@ u32 hfsplus_calc_btree_clump_size(u32
> block_size, u32 node_size,
> return clump_size;
> }
>
> +/* Context for iterating b-tree map pages
> + * @page_idx: The index of the page within the b-node's page array
> + * @off: The byte offset within the mapped page
> + * @len: The remaining length of the map record
> + */
> +struct hfs_bmap_ctx {
> + unsigned int page_idx;
> + unsigned int off;
> + u16 len;
> +};
> +
> +/*
> + * Finds the specific page containing the requested byte offset
> within the map
> + * record. Automatically handles the difference between header and
> map nodes.
> + * Returns the struct page pointer, or an ERR_PTR on failure.
> + * Note: The caller is responsible for mapping/unmapping the
> returned page.
> + */
> +static struct page *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;
> +
> + 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 = (u32)off16 + node->page_offset + byte_offset;
> + ctx->page_idx = page_off >> PAGE_SHIFT;
> + ctx->off = page_off & ~PAGE_MASK;
> +
> + return node->page[ctx->page_idx];
> +}
> +
> +/**
> + * hfs_bmap_clear_bit - clear a bit in the b-tree map
> + * @node: the b-tree node containing the map record
> + * @node_bit_idx: the relative bit index within the node's map
> record
> + *
> + * Returns 0 on success, -EINVAL if already clear, or negative error
> code.
> + */
> +static int hfs_bmap_clear_bit(struct hfs_bnode *node, u32
> node_bit_idx)
> +{
> + struct hfs_bmap_ctx ctx;
> + struct page *page;
> + u8 *bmap, mask;
> +
> + page = hfs_bmap_get_map_page(node, &ctx, node_bit_idx /
> BITS_PER_BYTE);
> + if (IS_ERR(page))
> + return PTR_ERR(page);
> +
> + bmap = kmap_local_page(page);
> +
> + mask = 1 << (7 - (node_bit_idx % BITS_PER_BYTE));
> +
> + if (!(bmap[ctx.off] & mask)) {
> + kunmap_local(bmap);
> + return -EINVAL;
> + }
> +
> + bmap[ctx.off] &= ~mask;
> + set_page_dirty(page);
> + kunmap_local(bmap);
> +
> + 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 +463,9 @@ 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;
> + struct page *page;
> u32 nidx, idx;
> - unsigned off;
> - u16 off16;
> - u16 len;
> u8 *data, byte, m;
> int i, res;
>
> @@ -390,30 +477,26 @@ 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)) {
> + page = hfs_bmap_get_map_page(node, &ctx, 0);
> + if (IS_ERR(page)) {
> + res = PTR_ERR(page);
> 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;
> + data = kmap_local_page(page);
> 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(page)
> ;
> kunmap_local(data);
> tree->free_nodes--;
> mark_inode_dirty(tre
> e->inode);
> @@ -423,13 +506,14 @@ 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;
> + page = node->page[++ctx.page_idx];
> + data = kmap_local_page(page);
> + ctx.off = 0;
> }
> idx += 8;
> - len--;
> + ctx.len--;
> }
> kunmap_local(data);
> nidx = node->next;
> @@ -443,22 +527,22 @@ 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;
> + page = hfs_bmap_get_map_page(node, &ctx, 0);
> + if (IS_ERR(page)) {
> + res = PTR_ERR(page);
> + hfs_bnode_put(node);
> + return ERR_PTR(res);
> + }
> + data = kmap_local_page(page);
> }
> }
>
> 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 +579,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 == -EINVAL) {
> + 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 */
Looks good.
Reviewed-by: Viacheslav Dubeyko <slava@dubeyko.com>
The xfstests run hasn't revealed any new issues.
Tested-by: Viacheslav Dubeyko <slava@dubeyko.com>
Thanks,
Slava.
© 2016 - 2026 Red Hat, Inc.