Re: [PATCH] hfs: avoid reusing occupied CNIDs after deletion
From: Viacheslav Dubeyko
Date: Thu Oct 15 2026 - 15:58:25 EST
On Thu, 2026-10-15 at 07:01 -0400, Hengyu Liang wrote:
> Commit a06ec283e125 ("hfs: add logic of correcting a next unused
> CNID")
> made hfs_correct_next_unused_CNID() use the CNID of the last file or
> directory record in catalog key order to lower next_id after
> deletion.
>
> However, catalog keys are sorted by parent directory ID and name,
> not by the record's own CNID. The resulting next_id can still be in
> use, so hfs_cat_create() finds an existing thread and returns EEXIST.
> Commit 6592287869bf ("hfs: fix incorrect inode ID assignment in
> hfs_new_inode()") exposed this issue by correcting the inode ID.
>
> On a freshly formatted and mounted HFS volume, run:
>
> mkdir z
> : > a
> : > b
> rm b
> : > c
>
> Without this fix, creating c fails with EEXIST, although c does not
> exist. With the fix, it succeeds on the first attempt.
>
> First look up the preceding CNID: if it exists, it must be the
> largest
> remaining ID. Otherwise, scan all file and directory records for the
> maximum, including files without optional thread records. Follow the
> leaf links regardless of node numbers, bound the walk by the total
> node count, and acquire a reference on every visit so malformed
> cycles
> cannot loop indefinitely or reuse a released node.
Before diving in the deeper review, I have some questions:
(1) The goal of hfs_correct_next_unused_CNID() was to fix the volume
corruption issue. Have you run hfs.fsck tool to check that volume is
valid (not corrupted) after your fix?
(2) Have you run xfstests (especially, generic/736) with your fix?
Because, the patch had goal to fix the generic/736 failure:
generic/736 [03:18:33][ 3.510255] run fstests generic/736 at 2025-
05-05 03:18:33
_check_generic_filesystem: filesystem on /dev/vdb is inconsistent
(see /results/hfs/results-default/generic/736.full for details)
Ran: generic/736
Failures: generic/736
Failed 1 of 1 tests
The HFS volume becomes corrupted after the test run:
sudo fsck.hfs -d /dev/loop50
** /dev/loop50
Using cacheBlockSize=32K cacheTotalBlock=1024 cacheSize=32768K.
Executing fsck_hfs (version 540.1-Linux).
** Checking HFS volume.
The volume name is untitled
** Checking extents overflow file.
** Checking catalog file.
** Checking catalog hierarchy.
** Checking volume bitmap.
** Checking volume information.
invalid MDB drNxtCNID
Master Directory Block needs minor repair
(1, 0)
Verify Status: VIStat = 0x8000, ABTStat = 0x0000 EBTStat = 0x0000
CBTStat = 0x0000 CatStat = 0x00000000
** Repairing volume.
** Rechecking volume.
** Checking HFS volume.
The volume name is untitled
** Checking extents overflow file.
** Checking catalog file.
** Checking catalog hierarchy.
** Checking volume bitmap.
** Checking volume information.
** The volume untitled was repaired successfully.
Thanks,
Slava.
>
> Fixes: a06ec283e125 ("hfs: add logic of correcting a next unused
> CNID")
> Cc: stable@xxxxxxxxxxxxxxx
> Assisted-by: LLM
> Signed-off-by: Hengyu Liang <hengyul@xxxxxxxxxx>
> ---
> The fallback follows leaf sibling links independently of node
> numbers.
> Bound its iterations by the tree's total node count and acquire a
> fresh
> node reference on every visit, including when a cycle returns to the
> tail.
> The budget check runs before acquisition; exhaustion returns EIO
> without
> using the partial maximum to update next_id.
>
> Tested on v7.3-rc6 with GCC 10.5 and the unchanged KASAN
> configuration:
> 14 normal-volume cases passed, including predecessor lookup, ID
> holes,
> missing file threads, concurrency and reordered leaf node numbers.
> Three malformed prev chains (tail self-loop, a loop returning to the
> tail,
> and a loop excluding the tail) each returned EIO after exactly
> node_count
> visits. The on-disk next CNID was unchanged; no KASAN or BUG was
> observed.
>
> fs/hfs/catalog.c | 80 +++++++++++++++++++++++++++++-----------------
> --
> 1 file changed, 48 insertions(+), 32 deletions(-)
>
> diff --git a/fs/hfs/catalog.c b/fs/hfs/catalog.c
> index 490c5e130da3..2d90f1857781 100644
> --- a/fs/hfs/catalog.c
> +++ b/fs/hfs/catalog.c
> @@ -269,48 +269,54 @@ void hfs_set_next_unused_CNID(struct
> super_block *sb,
> * Correct the next unused CNID of Catalog Tree.
> */
> static
> -int hfs_correct_next_unused_CNID(struct super_block *sb, u32 cnid)
> +int hfs_correct_next_unused_CNID(struct super_block *sb,
> + struct hfs_find_data *fd, u32 cnid)
> {
> struct hfs_btree *cat_tree;
> struct hfs_bnode *node;
> + u32 max_cnid = 0;
> + u32 remaining;
> s64 leaf_head;
> s64 leaf_tail;
> s64 node_id;
> + int res;
>
> hfs_dbg("cnid %u, next_id %lld\n",
> cnid, atomic64_read(&HFS_SB(sb)->next_id));
>
> - if ((cnid + 1) < atomic64_read(&HFS_SB(sb)->next_id)) {
> + if ((cnid + 1) != atomic64_read(&HFS_SB(sb)->next_id)) {
> /* next ID should be unchanged */
> return 0;
> }
>
> + /* If the previous CNID is still in use, it must be the
> maximum. */
> + res = hfs_cat_find_brec(sb, cnid - 1, fd);
> + if (!res) {
> + hfs_set_next_unused_CNID(sb, cnid, cnid - 1);
> + return 0;
> + }
> + if (res != -ENOENT)
> + return res;
> +
> cat_tree = HFS_SB(sb)->cat_tree;
> leaf_head = cat_tree->leaf_head;
> leaf_tail = cat_tree->leaf_tail;
> -
> - if (leaf_head > leaf_tail) {
> - pr_err("node is corrupted: leaf_head %lld, leaf_tail
> %lld\n",
> - leaf_head, leaf_tail);
> - return -ERANGE;
> - }
> -
> - node = hfs_bnode_find(cat_tree, leaf_tail);
> - if (IS_ERR(node)) {
> - pr_err("fail to find leaf node: node ID %lld\n",
> - leaf_tail);
> - return -ENOENT;
> - }
> -
> + remaining = cat_tree->node_count;
> node_id = leaf_tail;
>
> do {
> int i;
>
> - if (node_id != leaf_tail) {
> - node = hfs_bnode_find(cat_tree, node_id);
> - if (IS_ERR(node))
> - return -ENOENT;
> + /* A valid leaf chain cannot visit more nodes than
> the tree. */
> + if (!remaining)
> + return -EIO;
> + remaining--;
> +
> + node = hfs_bnode_find(cat_tree, node_id);
> + if (IS_ERR(node)) {
> + pr_err("fail to find leaf node: node ID
> %lld\n",
> + node_id);
> + return PTR_ERR(node);
> }
>
> hfs_dbg("node %lld, leaf_tail %lld, leaf_head
> %lld\n",
> @@ -331,42 +337,52 @@ int hfs_correct_next_unused_CNID(struct
> super_block *sb, u32 cnid)
> pr_err("fail to get the keylen: "
> "node_id %lld, record index
> %d\n",
> node_id, i);
> - return -EINVAL;
> + res = -EINVAL;
> + goto out;
> }
>
> entryoffset = off + keylen;
> entrylength = len - keylen;
>
> - if (entrylength > sizeof(rec)) {
> + if (entrylength <= 0 || entrylength >
> sizeof(rec)) {
> pr_err("unexpected record length: "
> "entrylength %d\n",
> entrylength);
> - return -EINVAL;
> + res = -EINVAL;
> + goto out;
> }
>
> hfs_bnode_read(node, &rec, entryoffset,
> entrylength);
>
> if (rec.type == HFS_CDR_DIR) {
> + if (entrylength != sizeof(struct
> hfs_cat_dir)) {
> + res = -EIO;
> + goto out;
> + }
> found_cnid =
> be32_to_cpu(rec.dir.DirID);
> hfs_dbg("found_cnid %u\n",
> found_cnid);
> - hfs_set_next_unused_CNID(sb, cnid,
> found_cnid);
> - hfs_bnode_put(node);
> - return 0;
> + max_cnid = max(max_cnid,
> found_cnid);
> } else if (rec.type == HFS_CDR_FIL) {
> + if (entrylength != sizeof(struct
> hfs_cat_file)) {
> + res = -EIO;
> + goto out;
> + }
> found_cnid =
> be32_to_cpu(rec.file.FlNum);
> hfs_dbg("found_cnid %u\n",
> found_cnid);
> - hfs_set_next_unused_CNID(sb, cnid,
> found_cnid);
> - hfs_bnode_put(node);
> - return 0;
> + max_cnid = max(max_cnid,
> found_cnid);
> }
> }
>
> node_id = node->prev;
> hfs_bnode_put(node);
>
> - } while (node_id >= leaf_head);
> + } while (node_id);
>
> - return -ENOENT;
> + hfs_set_next_unused_CNID(sb, cnid, max_cnid);
> + return 0;
> +out:
> + hfs_bnode_put(node);
> + return res;
> }
>
> /*
> @@ -420,7 +436,7 @@ int hfs_cat_delete(u32 cnid, struct inode *dir,
> const struct qstr *str)
> inode_set_mtime_to_ts(dir, inode_set_ctime_current(dir));
> mark_inode_dirty(dir);
>
> - res = hfs_correct_next_unused_CNID(sb, cnid);
> + res = hfs_correct_next_unused_CNID(sb, &fd, cnid);
> if (res)
> goto out;
>