Skip to contentSkip to conversation

hfs: port HFS+ b-tree bitmap corruption check

PATCH Superseded Aditya Srivastava 2 participants 2 messages Jul 3 – Jul 6

Subsystems (2)

v2 of 6 Superseded Latest is v6 →

lore
Share & tools
lore
#0 lore raw

PATCH v2 1/1 hfs: port HFS+ b-tree bitmap corruption check

From: Aditya Prakash Srivastava <[email protected]>

In HFS+ filesystems, during b-tree open (hfs_btree_open()), the code verifies that the allocation map bit for the tree header (node 0) is set. If not, it indicates a corrupted map record/bitmap and mounts the volume as read-only (SB_RDONLY) to prevent further damage.

HFS filesystems share the same b-tree structure but currently lack this corruption detection check.

Port this check to HFS, aligning its implementation with HFS+ to maintain consistent b-tree logic across both filesystems:
1. Define struct hfs_bmap_ctx and the relevant map record indices.
2. Port hfs_bmap_get_map_page() and the necessary offset and length validation helpers.
3. Implement hfs_bmap_test_bit() to inspect the B-tree bitmap using the new get_map_page helper.
4. In hfs_btree_open(), retrieve the header node via hfs_bnode_find(), test its allocation bit with hfs_bmap_test_bit(), and release it using hfs_bnode_put().

---
Changes in v2:
- Port struct hfs_bmap_ctx and hfs_bmap_get_map_page() helpers to fs/hfs/btree.c, keeping HFS and HFS+ logic unified and easy to library-ize.
- Re-implement hfs_bmap_test_bit() to take struct hfs_bnode and node_bit_idx, matching HFS+ perfectly.
- In hfs_btree_open(), use hfs_bnode_find() to retrieve the header node and put it safely after the bitwise verification check.

 fs/hfs/btree.c | 96 ++++++++++++++++++++++++++++++++++++++++++++++++++
 fs/hfs/btree.h |  2 ++
 2 files changed, 98 insertions(+)
fs/hfs/btree.c +96 -0
index 2eb37a2f64e8..36dc8735d01a 100644
@@ -23,6 +23,7 @@ struct hfs_btree *hfs_btree_open(struct super_block *sb, u32 id, btree_keycmp ke
 	struct address_space *mapping;
 	struct folio *folio;
 	struct buffer_head *bh;
+	struct hfs_bnode *node;
 	unsigned int size;
 	u16 dblock;
 	sector_t start_block;
@@ -155,6 +156,20 @@ struct hfs_btree *hfs_btree_open(struct super_block *sb, u32 id, btree_keycmp ke
 	kunmap_local(head);
 	folio_unlock(folio);
 	folio_put(folio);
+
+	node = hfs_bnode_find(tree, 0);
+	if (IS_ERR(node))
+		goto free_inode;
+
+	if (!hfs_bmap_test_bit(node, 0)) {
+		pr_warn("(%s): %s (cnid 0x%x) map record invalid or bitmap corruption detected, forcing read-only.\n",
+			sb->s_id, id == HFS_EXT_CNID ? "extents" : "catalog", id);
+		pr_warn("Run fsck.hfs to repair.\n");
+		sb->s_flags |= SB_RDONLY;
+	}
+
+	hfs_bnode_put(node);
+
 	return tree;
 
 fail_folio:
@@ -356,6 +371,87 @@ struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree)
 	}
 }
 
+struct hfs_bmap_ctx {
+	unsigned int page_idx;
+	unsigned int off;
+	u16 len;
+};
+
+#define HFS_BTREE_HDR_MAP_REC_INDEX	2
+#define HFS_BTREE_MAP_NODE_REC_INDEX	0
+
+static inline bool is_bnode_offset_valid(struct hfs_bnode *node, u32 off)
+{
+	return off < node->tree->node_size;
+}
+
+static inline u32 check_and_correct_requested_length(struct hfs_bnode *node, u32 off, u32 len)
+{
+	if (off >= node->tree->node_size)
+		return 0;
+	if ((u64)off + len > node->tree->node_size)
+		return node->tree->node_size - off;
+	return len;
+}
+
+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 == 0) {
+		if (node->type != HFS_NODE_HEADER) {
+			pr_err("hfs: invalid btree header node\n");
+			return ERR_PTR(-EIO);
+		}
+		rec_idx = HFS_BTREE_HDR_MAP_REC_INDEX;
+	} else {
+		if (node->type != HFS_NODE_MAP) {
+			pr_err("hfs: invalid btree map node\n");
+			return ERR_PTR(-EIO);
+		}
+		rec_idx = HFS_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];
+}
+
+bool hfs_bmap_test_bit(struct hfs_bnode *node, u32 node_bit_idx)
+{
+	struct hfs_bmap_ctx ctx;
+	struct page *page;
+	u8 *bmap, byte, mask;
+
+	page = hfs_bmap_get_map_page(node, &ctx, node_bit_idx / BITS_PER_BYTE);
+	if (IS_ERR(page))
+		return false;
+
+	bmap = kmap_local_page(page);
+	byte = bmap[ctx.off];
+	kunmap_local(bmap);
+
+	mask = 1 << (7 - (node_bit_idx % BITS_PER_BYTE));
+	return (byte & mask) != 0;
+}
+
 void hfs_bmap_free(struct hfs_bnode *node)
 {
 	struct hfs_btree *tree;
fs/hfs/btree.h +2 -0
index 99be858b2446..86036e18095f 100644
@@ -93,6 +93,8 @@ extern void hfs_btree_write(struct hfs_btree *tree);
 extern int hfs_bmap_reserve(struct hfs_btree *tree, u32 rsvd_nodes);
 extern struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree);
 extern void hfs_bmap_free(struct hfs_bnode *node);
+struct hfs_bmap_ctx;
+extern bool hfs_bmap_test_bit(struct hfs_bnode *node, u32 node_bit_idx);
 
 /* bnode.c */
 extern void hfs_bnode_read(struct hfs_bnode *node, void *buf, u32 off, u32 len);
Signature · 1 line
2.47.3
#1 lore raw
Quoted 60 lines · Aditya Srivastava

From: Aditya Prakash Srivastava <[email protected]>

In HFS+ filesystems, during b-tree open (hfs_btree_open()), the code verifies that the allocation map bit for the tree header (node 0) is set. If not, it indicates a corrupted map record/bitmap and mounts the volume as read-only (SB_RDONLY) to prevent further damage.

HFS filesystems share the same b-tree structure but currently lack this corruption detection check.

Port this check to HFS, aligning its implementation with HFS+ to maintain consistent b-tree logic across both filesystems:
1. Define struct hfs_bmap_ctx and the relevant map record indices.
2. Port hfs_bmap_get_map_page() and the necessary offset and length validation helpers.
3. Implement hfs_bmap_test_bit() to inspect the B-tree bitmap using the
   new get_map_page helper.
4. In hfs_btree_open(), retrieve the header node via hfs_bnode_find(),
   test its allocation bit with hfs_bmap_test_bit(), and release it using hfs_bnode_put().

Link:
https://lore.kernel.org/all/[email protected]/T/#r446d0fed2a2900bd805534bbcb799d86619ae2ea

---
Changes in v2:
- Port struct hfs_bmap_ctx and hfs_bmap_get_map_page() helpers to fs/hfs/btree.c, keeping HFS and HFS+ logic unified and easy to library-ize.
- Re-implement hfs_bmap_test_bit() to take struct hfs_bnode and node_bit_idx, matching HFS+ perfectly.
- In hfs_btree_open(), use hfs_bnode_find() to retrieve the header node and put it safely after the bitwise verification check.

 fs/hfs/btree.c | 96
++++++++++++++++++++++++++++++++++++++++++++++++++
 fs/hfs/btree.h |  2 ++

 2 files changed, 98 insertions(+)
fs/hfs/btree.c renamed from fs/hfs/btree. +1 -0
index 2eb37a2f64e8..36dc8735d01a 100644
@@ -23,6 +23,7 @@ struct hfs_btree *hfs_btree_open(struct super_block
 *sb, u32 id, btree_keycmp ke
  	struct address_space *mapping;
  	struct folio *folio;
  	struct buffer_head *bh;
+	struct hfs_bnode *node;
  	unsigned int size;
  	u16 dblock;

  sector_t start_block;

fs/hfs/btree.c renamed from fs/hfs/btree. +0 -0
@@ -155,6 +156,20 @@ struct hfs_btree *hfs_btree_open(struct

super_block *sb, u32 id, btree_keycmp ke
  kunmap_local(head);
  folio_unlock(folio);
  folio_put(folio);

fs/hfs/btree.c struct hfs_btree *hfs_btree_open(struct super_block *sb, u32 id, btree_keycmp ke · line 160

Quoted 2 lines
fs/hfs/btree.c renamed from fs/hfs/btree. +2 -0
+
+	node = hfs_bnode_find(tree, 0);

Probably, we need to have a specially named constant for this node ID.

fs/hfs/btree.c struct hfs_btree *hfs_btree_open(struct super_block *sb, u32 id, btree_keycmp ke · line 164

Quoted 4 lines
fs/hfs/btree.c renamed from fs/hfs/btree. +4 -0
+	if (IS_ERR(node))
+		goto free_inode;
+
+	if (!hfs_bmap_test_bit(node, 0)) {

Ditto.

Quoted 18 lines
fs/hfs/btree.c renamed from fs/hfs/btree. +1 -0
+		pr_warn("(%s): %s (cnid 0x%x) map record invalid or

bitmap corruption detected, forcing read-only.\n",

fs/hfs/btree.c renamed from fs/hfs/btree. +1 -0
+			sb->s_id, id == HFS_EXT_CNID ? "extents" :

"catalog", id);

fs/hfs/btree.c renamed from fs/hfs/btree. +6 -0
+		pr_warn("Run fsck.hfs to repair.\n");
+		sb->s_flags |= SB_RDONLY;
+	}
+
+	hfs_bnode_put(node);
+

  return tree;

 fail_folio:

fs/hfs/btree.c renamed from fs/hfs/btree. +0 -0
@@ -356,6 +371,87 @@ struct hfs_bnode *hfs_bmap_alloc(struct
 hfs_btree *tree)
  	}
  }

fs/hfs/btree.c struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree) · line 378

Quoted 5 lines
fs/hfs/btree.c renamed from fs/hfs/btree. +5 -0
+struct hfs_bmap_ctx {
+	unsigned int page_idx;
+	unsigned int off;
+	u16 len;
+};

I prefer to have comments for this structure likewise HFS+ has.

fs/hfs/btree.c struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree) · line 381

Quoted 3 lines
fs/hfs/btree.c renamed from fs/hfs/btree. +3 -0
+
+#define HFS_BTREE_HDR_MAP_REC_INDEX	2
+#define HFS_BTREE_MAP_NODE_REC_INDEX	0

I believe that this should be declared in some proper header.

Quoted 3 lines
fs/hfs/btree.c renamed from fs/hfs/btree. +2 -0
+
+static inline bool is_bnode_offset_valid(struct hfs_bnode *node, u32

off)

Probably, it makes sense to have this function in some proper header.

fs/hfs/btree.c struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree) · line 385

Quoted 2 lines
fs/hfs/btree.c renamed from fs/hfs/btree. +2 -0
+{
+	return off < node->tree->node_size;

Are you sure that pointers on node and tree will be always valid?

fs/hfs/btree.c

Quoted 6 lines
fs/hfs/btree.c renamed from fs/hfs/btree. +3 -0
+}
+
+static inline u32 check_and_correct_requested_length(struct

hfs_bnode *node, u32 off, u32 len)

fs/hfs/btree.c renamed from fs/hfs/btree. +2 -0
+{
+	if (off >= node->tree->node_size)

Ditto. Are you sure that pointers on node and tree will be always valid?

Quoted 4 lines
fs/hfs/btree.c renamed from fs/hfs/btree. +4 -0
+		return 0;
+	if ((u64)off + len > node->tree->node_size)
+		return node->tree->node_size - off;
+	return len;

fs/hfs/btree.c struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree) · line 404

Quoted 10 lines
fs/hfs/btree.c renamed from fs/hfs/btree. +10 -0
+}
+
+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 == 0) {

It will be good to have named constant for this node ID.

Thanks,
Slava.

Quoted 71 lines
fs/hfs/btree.c renamed from fs/hfs/btree. +21 -0
+		if (node->type != HFS_NODE_HEADER) {
+			pr_err("hfs: invalid btree header node\n");
+			return ERR_PTR(-EIO);
+		}
+		rec_idx = HFS_BTREE_HDR_MAP_REC_INDEX;
+	} else {
+		if (node->type != HFS_NODE_MAP) {
+			pr_err("hfs: invalid btree map node\n");
+			return ERR_PTR(-EIO);
+		}
+		rec_idx = HFS_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);

fs/hfs/btree.c renamed from fs/hfs/btree. +18 -0
+
+	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];
+}
+
+bool hfs_bmap_test_bit(struct hfs_bnode *node, u32 node_bit_idx)
+{
+	struct hfs_bmap_ctx ctx;
+	struct page *page;
+	u8 *bmap, byte, mask;
+
+	page = hfs_bmap_get_map_page(node, &ctx, node_bit_idx /

BITS_PER_BYTE);

fs/hfs/btree.c renamed from fs/hfs/btree. +11 -0
+	if (IS_ERR(page))
+		return false;
+
+	bmap = kmap_local_page(page);
+	byte = bmap[ctx.off];
+	kunmap_local(bmap);
+
+	mask = 1 << (7 - (node_bit_idx % BITS_PER_BYTE));
+	return (byte & mask) != 0;
+}
+

 void hfs_bmap_free(struct hfs_bnode *node)
 {
  struct hfs_btree *tree;

fs/hfs/btree.h +2 -0
index 99be858b2446..86036e18095f 100644
@@ -93,6 +93,8 @@ extern void hfs_btree_write(struct hfs_btree
 *tree);
  extern int hfs_bmap_reserve(struct hfs_btree *tree, u32 rsvd_nodes);
  extern struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree);
  extern void hfs_bmap_free(struct hfs_bnode *node);
+struct hfs_bmap_ctx;
+extern bool hfs_bmap_test_bit(struct hfs_bnode *node, u32
 node_bit_idx);


 /* bnode.c */
 extern void hfs_bnode_read(struct hfs_bnode *node, void *buf, u32 off, u32 len);