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() to duplicate
boilerplate code to validate offsets, correct lengths, and map the
underlying pages via kmap_local_page() for both the initial header node
and the subsequent map nodes in the chain.
Introduce a generic helper, hfs_bmap_get_map_page(), to encapsulate
the map record access. This helper:
1. Automatically validates the node->type against HFS_NODE_HEADER and
HFS_NODE_MAP to prevent misinterpreting corrupted nodes.
2. Infers the correct record index (2 or 0) based on the node type.
3. Handles the offset calculation, length validation, and page mapping.
Refactor hfs_bmap_alloc() to utilize this helper, stripping out the
redundant setup blocks. As part of this cleanup, the double pointer
iterator (struct page **pagep) is replaced with a simpler unsigned int
index (page_idx) for cleaner page boundary crossing.
This deduplicates the allocator logic, hardens the map traversal against
fuzzed/corrupted images, and provides a generic map-access abstraction
that will be utilized by upcoming mount-time validation checks.
Signed-off-by: Shardul Bankar <shardul.b@mpiricsoftware.com>
---
fs/hfsplus/btree.c | 78 +++++++++++++++++++++++++++-----------
include/linux/hfs_common.h | 3 ++
2 files changed, 59 insertions(+), 22 deletions(-)
diff --git a/fs/hfsplus/btree.c b/fs/hfsplus/btree.c
index 1220a2f22737..22efd6517ef4 100644
--- a/fs/hfsplus/btree.c
+++ b/fs/hfsplus/btree.c
@@ -129,6 +129,47 @@ u32 hfsplus_calc_btree_clump_size(u32 block_size, u32 node_size,
return clump_size;
}
+/*
+ * Maps the page containing the b-tree map record and calculates offsets.
+ * 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, u16 *off, u16 *len,
+ unsigned int *page_idx)
+{
+ u16 rec_idx, off16;
+
+ 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;
+ }
+
+ *len = hfs_brec_lenoff(node, rec_idx, &off16);
+ if (!*len)
+ return ERR_PTR(-ENOENT);
+
+ if (!is_bnode_offset_valid(node, off16))
+ return ERR_PTR(-EIO);
+
+ *len = check_and_correct_requested_length(node, off16, *len);
+
+ off16 += node->page_offset;
+ *page_idx = off16 >> PAGE_SHIFT;
+ *off = off16 & ~PAGE_MASK;
+
+ return kmap_local_page(node->page[*page_idx]);
+}
+
/* 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,10 +415,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;
+ unsigned int page_idx;
u32 nidx, idx;
- unsigned off;
- u16 off16;
+ u16 off;
u16 len;
u8 *data, byte, m;
int i, res;
@@ -390,30 +430,24 @@ 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, &off, &len, &page_idx);
+ 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];
if (byte != 0xff) {
- for (m = 0x80, i = 0; i < 8; m >>= 1, i++) {
+ for (m = HFSPLUS_BTREE_NODE0_BIT, i = 0; i < 8; m >>= 1, i++) {
if (!(byte & m)) {
idx += i;
data[off] |= m;
- set_page_dirty(*pagep);
+ set_page_dirty(node->page[page_idx]);
kunmap_local(data);
tree->free_nodes--;
mark_inode_dirty(tree->inode);
@@ -425,7 +459,7 @@ struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree)
}
if (++off >= PAGE_SIZE) {
kunmap_local(data);
- data = kmap_local_page(*++pagep);
+ data = kmap_local_page(node->page[++page_idx]);
off = 0;
}
idx += 8;
@@ -443,12 +477,12 @@ 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, &off, &len, &page_idx);
+ if (IS_ERR(data)) {
+ res = PTR_ERR(data);
+ hfs_bnode_put(node);
+ return ERR_PTR(res);
+ }
}
}
diff --git a/include/linux/hfs_common.h b/include/linux/hfs_common.h
index dadb5e0aa8a3..8238f55dd1d3 100644
--- a/include/linux/hfs_common.h
+++ b/include/linux/hfs_common.h
@@ -510,7 +510,10 @@ 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
+#define HFSPLUS_BTREE_NODE0_BIT (1 << 7)
/* btree key type */
#define HFSPLUS_KEY_CASEFOLDING 0xCF /* case-insensitive */
--
2.34.1On Thu, 2026-02-26 at 14:42 +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() to duplicate
> boilerplate code to validate offsets, correct lengths, and map the
> underlying pages via kmap_local_page() for both the initial header node
> and the subsequent map nodes in the chain.
>
> Introduce a generic helper, hfs_bmap_get_map_page(), to encapsulate
> the map record access. This helper:
> 1. Automatically validates the node->type against HFS_NODE_HEADER and
> HFS_NODE_MAP to prevent misinterpreting corrupted nodes.
> 2. Infers the correct record index (2 or 0) based on the node type.
> 3. Handles the offset calculation, length validation, and page mapping.
>
> Refactor hfs_bmap_alloc() to utilize this helper, stripping out the
> redundant setup blocks. As part of this cleanup, the double pointer
> iterator (struct page **pagep) is replaced with a simpler unsigned int
> index (page_idx) for cleaner page boundary crossing.
>
> This deduplicates the allocator logic, hardens the map traversal against
> fuzzed/corrupted images, and provides a generic map-access abstraction
> that will be utilized by upcoming mount-time validation checks.
>
> Signed-off-by: Shardul Bankar <shardul.b@mpiricsoftware.com>
> ---
> fs/hfsplus/btree.c | 78 +++++++++++++++++++++++++++-----------
> include/linux/hfs_common.h | 3 ++
> 2 files changed, 59 insertions(+), 22 deletions(-)
>
> diff --git a/fs/hfsplus/btree.c b/fs/hfsplus/btree.c
> index 1220a2f22737..22efd6517ef4 100644
> --- a/fs/hfsplus/btree.c
> +++ b/fs/hfsplus/btree.c
> @@ -129,6 +129,47 @@ u32 hfsplus_calc_btree_clump_size(u32 block_size, u32 node_size,
> return clump_size;
> }
>
> +/*
> + * Maps the page containing the b-tree map record and calculates offsets.
> + * 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, u16 *off, u16 *len,
> + unsigned int *page_idx)
I think we don't need in off, len, page_idx arguments here. I suggest slightly
different interface:
u8 hfs_bmap_get_map_byte(struct hfs_bnode *node, u32 bit_index);
int hfs_bmap_set_map_byte(struct hfs_bnode *node, u32 bit_index, u8 byte);
In this case memory operations will be atomic ones and all
kmap_local()/kunmap_local() will be hidden inside these methods. However, I am
slightly worried that I don't see any locking mechanisms in hfs_bmap_alloc(). At
minimum, I believe we can use lock_page()/unlock_page() here. However, it will
be not enough. It is good for accessing only one page. But we need some lock for
the whole bitmap. Maybe, I am missing something. But if I am not, then we have a
huge room for race conditions in b-tree operations.
Probably, you could need something like hfs_bmap_get_map_page(). But you don't
need all of these arguments (off, len, page_idx) with suggested interface.
Because, bit_index should be enough to identify the proper memory page/folio and
get/set bytes there.
> +{
> + u16 rec_idx, off16;
> +
> + 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;
> + }
> +
> + *len = hfs_brec_lenoff(node, rec_idx, &off16);
> + if (!*len)
> + return ERR_PTR(-ENOENT);
> +
> + if (!is_bnode_offset_valid(node, off16))
> + return ERR_PTR(-EIO);
> +
> + *len = check_and_correct_requested_length(node, off16, *len);
> +
> + off16 += node->page_offset;
> + *page_idx = off16 >> PAGE_SHIFT;
> + *off = off16 & ~PAGE_MASK;
> +
> + return kmap_local_page(node->page[*page_idx]);
> +}
> +
> /* 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,10 +415,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;
> + unsigned int page_idx;
> u32 nidx, idx;
> - unsigned off;
> - u16 off16;
> + u16 off;
> u16 len;
> u8 *data, byte, m;
> int i, res;
> @@ -390,30 +430,24 @@ 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, &off, &len, &page_idx);
> + 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];
> if (byte != 0xff) {
> - for (m = 0x80, i = 0; i < 8; m >>= 1, i++) {
> + for (m = HFSPLUS_BTREE_NODE0_BIT, i = 0; i < 8; m >>= 1, i++) {
You are not right here. The 0x80 is simply pattern and it's not
HFSPLUS_BTREE_NODE0_BIT. Because, it could be any byte of the map.
Thanks,
Slava.
> if (!(byte & m)) {
> idx += i;
> data[off] |= m;
> - set_page_dirty(*pagep);
> + set_page_dirty(node->page[page_idx]);
> kunmap_local(data);
> tree->free_nodes--;
> mark_inode_dirty(tree->inode);
> @@ -425,7 +459,7 @@ struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree)
> }
> if (++off >= PAGE_SIZE) {
> kunmap_local(data);
> - data = kmap_local_page(*++pagep);
> + data = kmap_local_page(node->page[++page_idx]);
> off = 0;
> }
> idx += 8;
> @@ -443,12 +477,12 @@ 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, &off, &len, &page_idx);
> + if (IS_ERR(data)) {
> + res = PTR_ERR(data);
> + hfs_bnode_put(node);
> + return ERR_PTR(res);
> + }
> }
> }
>
> diff --git a/include/linux/hfs_common.h b/include/linux/hfs_common.h
> index dadb5e0aa8a3..8238f55dd1d3 100644
> --- a/include/linux/hfs_common.h
> +++ b/include/linux/hfs_common.h
> @@ -510,7 +510,10 @@ 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
> +#define HFSPLUS_BTREE_NODE0_BIT (1 << 7)
>
> /* btree key type */
> #define HFSPLUS_KEY_CASEFOLDING 0xCF /* case-insensitive */
On Thu, 2026-02-26 at 23:50 +0000, Viacheslav Dubeyko wrote:
> On Thu, 2026-02-26 at 14:42 +0530, Shardul Bankar wrote:
> >
> > +/*
> > + * Maps the page containing the b-tree map record and calculates
> > offsets.
> > + * 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, u16 *off,
> > u16 *len,
> > + unsigned int *page_idx)
>
> I think we don't need in off, len, page_idx arguments here. I suggest
> slightly
> different interface:
>
> u8 hfs_bmap_get_map_byte(struct hfs_bnode *node, u32 bit_index);
> int hfs_bmap_set_map_byte(struct hfs_bnode *node, u32 bit_index, u8
> byte);
>
> In this case memory operations will be atomic ones and all
> kmap_local()/kunmap_local() will be hidden inside these methods.
Hi Slava,
Regarding the get_map_byte/set_map_byte interface: there would be a
severe performance regression if we force
kmap_local_page()/kunmap_local() on a per-byte basis inside the
hfs_bmap_alloc() linear scan. I am providing a detailed breakdown of
this overhead and a proposed alternative in my reply to your review on
Patch 2/2.
> However, I am
> slightly worried that I don't see any locking mechanisms in
> hfs_bmap_alloc(). At
> minimum, I believe we can use lock_page()/unlock_page() here.
> However, it will
> be not enough. It is good for accessing only one page. But we need
> some lock for
> the whole bitmap. Maybe, I am missing something. But if I am not,
> then we have a
> huge room for race conditions in b-tree operations.
Regarding the locking, concurrent access to the allocator is already
prevented by the per-tree tree->tree_lock mutex. Operations that reach
hfs_bmap_alloc() (e.g., node splits via hfs_brec_insert) are executed
within a search context initialized by hfs_find_init(), which holds
mutex_lock(&tree->tree_lock). Therefore, the map nodes are safely
serialized without needing individual lock_page() calls during the
scan.
>
> > for (;;) {
> > while (len) {
> > byte = data[off];
> > if (byte != 0xff) {
> > - for (m = 0x80, i = 0; i < 8; m >>=
> > 1, i++) {
> > + for (m = HFSPLUS_BTREE_NODE0_BIT, i
> > = 0; i < 8; m >>= 1, i++) {
>
> You are not right here. The 0x80 is simply pattern and it's not
> HFSPLUS_BTREE_NODE0_BIT. Because, it could be any byte of the map.
>
Ack'ed. Good catch, I will retain the original 0x80 pattern in the
allocation loop.
Thanks,
Shardul
© 2016 - 2026 Red Hat, Inc.