Skip to contentSkip to conversation

hfs: port HFS+ b-tree bitmap corruption check

PATCH Superseded Aditya Srivastava 2 participants 4 messages Jun 23 – Jul 2

Subsystems (2)

v1 of 6 Superseded Latest is v6 →

lore
Share & tools
lore
#0 lore raw

PATCH 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, which was highlighted by the maintainer.

Port this check to HFS:
1. Implement hfs_bmap_test_bit() in fs/hfs/btree.c (which safely traverses the b-tree map nodes to inspect the desired bit, identical to HFS+).
2. Invoke hfs_bmap_test_bit() for node 0 at the end of hfs_btree_open(), warning and forcing read-only if corruption is detected.

---
 fs/hfs/btree.c | 52 ++++++++++++++++++++++++++++++++++++++++++++++++++
 fs/hfs/btree.h |  1 +
 2 files changed, 53 insertions(+)
fs/hfs/btree.c +52 -0
index 2eb37a2f64e8..4293399d377e 100644
@@ -155,6 +155,14 @@ struct hfs_btree *hfs_btree_open(struct super_block *sb, u32 id, btree_keycmp ke
 	kunmap_local(head);
 	folio_unlock(folio);
 	folio_put(folio);
+
+	if (!hfs_bmap_test_bit(tree, 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;
+	}
+
 	return tree;
 
 fail_folio:
@@ -356,6 +364,50 @@ struct hfs_bnode *hfs_bmap_alloc(struct hfs_btree *tree)
 	}
 }
 
+bool hfs_bmap_test_bit(struct hfs_btree *tree, u32 nidx)
+{
+	struct hfs_bnode *node;
+	struct page *page;
+	u16 off, len;
+	u8 *data, byte, m;
+	bool res = false;
+
+	node = hfs_bnode_find(tree, 0);
+	if (IS_ERR(node))
+		return false;
+
+	len = hfs_brec_lenoff(node, 2, &off);
+	while (nidx >= len * 8) {
+		u32 i;
+
+		nidx -= len * 8;
+		i = node->next;
+		if (!i) {
+			hfs_bnode_put(node);
+			return false;
+		}
+		hfs_bnode_put(node);
+		node = hfs_bnode_find(tree, i);
+		if (IS_ERR(node))
+			return false;
+		if (node->type != HFS_NODE_MAP) {
+			hfs_bnode_put(node);
+			return false;
+		}
+		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];
+	res = (byte & m) != 0;
+	kunmap_local(data);
+	hfs_bnode_put(node);
+	return res;
+}
+
 void hfs_bmap_free(struct hfs_bnode *node)
 {
 	struct hfs_btree *tree;
fs/hfs/btree.h +1 -0
index 99be858b2446..efe88f66c856 100644
@@ -93,6 +93,7 @@ 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);
+extern bool hfs_bmap_test_bit(struct hfs_btree *tree, u32 nidx);
 
 /* 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 116 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, which was highlighted by the maintainer.

Port this check to HFS:
1. Implement hfs_bmap_test_bit() in fs/hfs/btree.c (which safely traverses
   the b-tree map nodes to inspect the desired bit, identical to HFS+).
2. Invoke hfs_bmap_test_bit() for node 0 at the end of hfs_btree_open(),
   warning and forcing read-only if corruption is detected.

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

---
 fs/hfs/btree.c | 52
++++++++++++++++++++++++++++++++++++++++++++++++++
 fs/hfs/btree.h |  1 +

 2 files changed, 53 insertions(+)
fs/hfs/btree.c +0 -0
index 2eb37a2f64e8..4293399d377e 100644
@@ -155,6 +155,14 @@ 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 +3 -0
+
+	if (!hfs_bmap_test_bit(tree, 0)) {
+		pr_warn("(%s): %s (cnid 0x%x) map record invalid or

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

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

"catalog", id);

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

  return tree;

 fail_folio:

fs/hfs/btree.c +0 -0
@@ -356,6 +364,50 @@ struct hfs_bnode *hfs_bmap_alloc(struct
 hfs_btree *tree)
  	}
  }

fs/hfs/btree.c +44 -0
+bool hfs_bmap_test_bit(struct hfs_btree *tree, u32 nidx)
+{
+	struct hfs_bnode *node;
+	struct page *page;
+	u16 off, len;
+	u8 *data, byte, m;
+	bool res = false;
+
+	node = hfs_bnode_find(tree, 0);
+	if (IS_ERR(node))
+		return false;
+
+	len = hfs_brec_lenoff(node, 2, &off);
+	while (nidx >= len * 8) {
+		u32 i;
+
+		nidx -= len * 8;
+		i = node->next;
+		if (!i) {
+			hfs_bnode_put(node);
+			return false;
+		}
+		hfs_bnode_put(node);
+		node = hfs_bnode_find(tree, i);
+		if (IS_ERR(node))
+			return false;
+		if (node->type != HFS_NODE_MAP) {
+			hfs_bnode_put(node);
+			return false;
+		}
+		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];
+	res = (byte & m) != 0;
+	kunmap_local(data);
+	hfs_bnode_put(node);
+	return res;
+}
+

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

fs/hfs/btree.h +1 -0
index 99be858b2446..efe88f66c856 100644
@@ -93,6 +93,7 @@ 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);
+extern bool hfs_bmap_test_bit(struct hfs_btree *tree, u32 nidx);
Quoted 4 lines


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

I am still in personal trip and I am on the move until the end of this week. I'll be able to review the patch around this Sunday or Monday. Please, ping me if I am keeping silence too long.

Meanwhile, have you tried to run xfstests for current state of HFS code? Please, be ready that we still have multiple test-case failures for the case of HFS file system. The point of my request is to check that number of failed test-cases is not growing by applying this patch.

Thanks,
Slava.

#2 lore raw
In reply to Aditya Srivastava
Quoted 92 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, which was highlighted by the maintainer.

Port this check to HFS:
1. Implement hfs_bmap_test_bit() in fs/hfs/btree.c (which safely traverses
   the b-tree map nodes to inspect the desired bit, identical to HFS+).
2. Invoke hfs_bmap_test_bit() for node 0 at the end of hfs_btree_open(),
   warning and forcing read-only if corruption is detected.

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

---
 fs/hfs/btree.c | 52
++++++++++++++++++++++++++++++++++++++++++++++++++
 fs/hfs/btree.h |  1 +

 2 files changed, 53 insertions(+)
fs/hfs/btree.c +0 -0
index 2eb37a2f64e8..4293399d377e 100644
@@ -155,6 +155,14 @@ 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 +3 -0
+
+	if (!hfs_bmap_test_bit(tree, 0)) {
+		pr_warn("(%s): %s (cnid 0x%x) map record invalid or

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

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

"catalog", id);

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

  return tree;

 fail_folio:

fs/hfs/btree.c +0 -0
@@ -356,6 +364,50 @@ struct hfs_bnode *hfs_bmap_alloc(struct
 hfs_btree *tree)
  	}
  }

fs/hfs/btree.c +33 -0
+bool hfs_bmap_test_bit(struct hfs_btree *tree, u32 nidx)
+{
+	struct hfs_bnode *node;
+	struct page *page;
+	u16 off, len;
+	u8 *data, byte, m;
+	bool res = false;
+
+	node = hfs_bnode_find(tree, 0);
+	if (IS_ERR(node))
+		return false;
+
+	len = hfs_brec_lenoff(node, 2, &off);
+	while (nidx >= len * 8) {
+		u32 i;
+
+		nidx -= len * 8;
+		i = node->next;
+		if (!i) {
+			hfs_bnode_put(node);
+			return false;
+		}
+		hfs_bnode_put(node);
+		node = hfs_bnode_find(tree, i);
+		if (IS_ERR(node))
+			return false;
+		if (node->type != HFS_NODE_MAP) {
+			hfs_bnode_put(node);
+			return false;
+		}
+		len = hfs_brec_lenoff(node, 0, &off);
+	}
+	off += node->page_offset + nidx / 8;

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

Quoted 10 lines
fs/hfs/btree.c +10 -0
+	page = node->page[off >> PAGE_SHIFT];
+	data = kmap_local_page(page);
+	off &= ~PAGE_MASK;
+	m = 1 << (~nidx & 7);
+	byte = data[off];
+	res = (byte & m) != 0;
+	kunmap_local(data);
+	hfs_bnode_put(node);
+	return res;
+}

Why we cannot follow to the approach is implemented in HFS+?

static 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;
}

Currently implemented function looks slightly complicated. Also, I would like to have similar logic in HFS and HFS+ with the goal to make b-tree logic something like library that HFS and HFS+ code can use.

Thanks,
Slava.

Quoted 18 lines

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

fs/hfs/btree.h +1 -0
index 99be858b2446..efe88f66c856 100644
@@ -93,6 +93,7 @@ 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);
+extern bool hfs_bmap_test_bit(struct hfs_btree *tree, u32 nidx);


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

#3 lore raw

Hi Slava,

Thanks for the suggestion.

You're right. The initial implementation ended up a bit more complex because HFS lacks the struct hfs_bmap_ctx and hfs_bmap_get_map_page() helpers that HFS+ already has.

Porting those helpers to HFS is straightforward since both filesystems use the same b-tree map layout (record index 2 for the header node map and record index 0 for map nodes). Doing so also lets hfs_bmap_test_bit() follow the same implementation as HFS+, which is much cleaner.

I'll update this in v2 by:

adding struct hfs_bmap_ctx to fs/hfs/btree.c;
porting hfs_bmap_get_map_page();
simplifying hfs_bmap_test_bit() to match the HFS+
implementation; and
updating hfs_btree_open() to call
hfs_bmap_test_bit(node, 0) accordingly.

I'll send a v2 with these changes.

Thanks,
Aditya

Quoted 151 lines · Viacheslav Dubeyko
Quoted 92 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, which was highlighted by the maintainer.

Port this check to HFS:
1. Implement hfs_bmap_test_bit() in fs/hfs/btree.c (which safely traverses
the b-tree map nodes to inspect the desired bit, identical to
HFS+).
2. Invoke hfs_bmap_test_bit() for node 0 at the end of hfs_btree_open(),
warning and forcing read-only if corruption is detected.

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

---
 fs/hfs/btree.c | 52
++++++++++++++++++++++++++++++++++++++++++++++++++
 fs/hfs/btree.h |  1 +
 2 files changed, 53 insertions(+)
fs/hfs/btree.c +0 -0
index 2eb37a2f64e8..4293399d377e 100644
@@ -155,6 +155,14 @@ 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 +3 -0
+
+     if (!hfs_bmap_test_bit(tree, 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);

fs/hfs/btree.c +37 -0
+             pr_warn("Run fsck.hfs to repair.\n");
+             sb->s_flags |= SB_RDONLY;
+     }
+
      return tree;
 
 fail_folio:
@@ -356,6 +364,50 @@ struct hfs_bnode *hfs_bmap_alloc(struct
 hfs_btree *tree)
      }
 }
 
+bool hfs_bmap_test_bit(struct hfs_btree *tree, u32 nidx)
+{
+     struct hfs_bnode *node;
+     struct page *page;
+     u16 off, len;
+     u8 *data, byte, m;
+     bool res = false;
+
+     node = hfs_bnode_find(tree, 0);
+     if (IS_ERR(node))
+             return false;
+
+     len = hfs_brec_lenoff(node, 2, &off);
+     while (nidx >= len * 8) {
+             u32 i;
+
+             nidx -= len * 8;
+             i = node->next;
+             if (!i) {
+                     hfs_bnode_put(node);
+                     return false;
+             }
+             hfs_bnode_put(node);
+             node = hfs_bnode_find(tree, i);
+             if (IS_ERR(node))
+                     return false;
+             if (node->type != HFS_NODE_MAP) {
+                     hfs_bnode_put(node);
+                     return false;
+             }
+             len = hfs_brec_lenoff(node, 0, &off);
+     }
+     off += node->page_offset + nidx / 8;

fs/hfs/btree.c struct hfs_bnode *hfs_bmap_alloc(struct · line 410

Quoted 10 lines
fs/hfs/btree.c +10 -0
+     page = node->page[off >> PAGE_SHIFT];
+     data = kmap_local_page(page);
+     off &= ~PAGE_MASK;
+     m = 1 << (~nidx & 7);
+     byte = data[off];
+     res = (byte & m) != 0;
+     kunmap_local(data);
+     hfs_bnode_put(node);
+     return res;
+}

Why we cannot follow to the approach is implemented in HFS+?

static 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;
}

Currently implemented function looks slightly complicated. Also, I would like to have similar logic in HFS and HFS+ with the goal to make b-tree logic something like library that HFS and HFS+ code can use.

Thanks,
Slava.

Quoted 18 lines
fs/hfs/btree.c +1 -0
+
 void hfs_bmap_free(struct hfs_bnode *node)
 {
      struct hfs_btree *tree;
fs/hfs/btree.h +1 -0
index 99be858b2446..efe88f66c856 100644
@@ -93,6 +93,7 @@ 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);
+extern bool hfs_bmap_test_bit(struct hfs_btree *tree, u32 nidx);
 
 /* bnode.c */

extern void hfs_bnode_read(struct hfs_bnode *node, void *buf, u32
off, u32 len);