[PATCH] hfs: avoid reusing occupied CNIDs after deletion

[PATCH] hfs: avoid reusing occupied CNIDs after deletion

[Hengyu Liang]

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.

Fixes: a06ec283e125 ("hfs: add logic of correcting a next unused CNID")
Cc: stable@vger.kernel.org
Assisted-by: LLM
Signed-off-by: Hengyu Liang <hengyul@cs.unc.edu>
---
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;
 
-- 
2.53.0

Re: [PATCH] hfs: avoid reusing occupied CNIDs after deletion

[Viacheslav Dubeyko]

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@vger.kernel.org
> Assisted-by: LLM
> Signed-off-by: Hengyu Liang <hengyul@cs.unc.edu>
> ---
> 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;
>  

Re: [PATCH] hfs: avoid reusing occupied CNIDs after deletion

[Hengyu Liang]

Hi Slava,

On Thu, Oct 15, 2026 at 12:58:14PM -0700, Viacheslav Dubeyko wrote:
> (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?

Thanks for pointing this out. I have now run the additional checks on
v7.3-rc6 with this patch, using fsck.hfs 540.1-Linux:

- All 14 normal-volume images from the original tests passed
  fsck.hfs -fn after unmount. This includes the reproducer, CNID holes,
  missing optional file threads, concurrent operations, and reordered
  leaf node numbers. The checker did not modify the images.

> (2) Have you run xfstests (especially, generic/736) with your fix?
> Because, the patch had goal to fix the generic/736 failure:

- On a freshly formatted 64 MiB HFS volume, I ran:

    ./check -i 10 generic/736

  All 10 iterations passed, including the filesystem checks after each
  iteration, with FSCK_OPTIONS="-fn". A separate fsck.hfs -fn after
  the run also passed. There was no "invalid MDB drNxtCNID" error.
  The unpatched v7.3-rc6 kernel also passed these 10 iterations.

- I repeated the minimal reproducer on a separate fresh volume. The
  first creation of c failed with EEXIST without the patch and succeeded
  with it. The surviving file's CNID and contents were unchanged, and
  the patched volume passed fsck.hfs -fn after unmount.

For completeness, I initially ran generic/736 on a 256 MiB HFS volume.
The test body completed, but the final fsck reported:

    Invalid map node linkage
    (4, 2048)

I reproduced the same failure on unpatched v7.3-rc6 with the same volume
size and tools. The catalog had 6129 nodes, while its header map and
single map node covered only 5984 nodes. I then used fresh 64 MiB volumes
for the runs above; their filesystem checks passed without repair.

No KASAN report or kernel BUG/WARNING was observed during these runs.

Thanks,
Hengyu

Re: [PATCH] hfs: avoid reusing occupied CNIDs after deletion

[Viacheslav Dubeyko]

Hi Hengyu,

On Thu, 2026-10-15 at 22:31 -0400, Hengyu Liang wrote:
> Hi Slava,
> 
> On Thu, Oct 15, 2026 at 12:58:14PM -0700, Viacheslav Dubeyko wrote:
> > (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?
> 
> Thanks for pointing this out. I have now run the additional checks on
> v7.3-rc6 with this patch, using fsck.hfs 540.1-Linux:
> 
> - All 14 normal-volume images from the original tests passed
>   fsck.hfs -fn after unmount. This includes the reproducer, CNID
> holes,
>   missing optional file threads, concurrent operations, and reordered
>   leaf node numbers. The checker did not modify the images.
> 
> > (2) Have you run xfstests (especially, generic/736) with your fix?
> > Because, the patch had goal to fix the generic/736 failure:
> 
> - On a freshly formatted 64 MiB HFS volume, I ran:
> 
>     ./check -i 10 generic/736
> 
>   All 10 iterations passed, including the filesystem checks after
> each
>   iteration, with FSCK_OPTIONS="-fn". A separate fsck.hfs -fn after
>   the run also passed. There was no "invalid MDB drNxtCNID" error.
>   The unpatched v7.3-rc6 kernel also passed these 10 iterations.
> 
> - I repeated the minimal reproducer on a separate fresh volume. The
>   first creation of c failed with EEXIST without the patch and
> succeeded
>   with it. The surviving file's CNID and contents were unchanged, and
>   the patched volume passed fsck.hfs -fn after unmount.

Sounds great! Let me take a look into the code.

> 
> For completeness, I initially ran generic/736 on a 256 MiB HFS
> volume.
> The test body completed, but the final fsck reported:
> 
>     Invalid map node linkage
>     (4, 2048)
> 
> I reproduced the same failure on unpatched v7.3-rc6 with the same
> volume
> size and tools. The catalog had 6129 nodes, while its header map and
> single map node covered only 5984 nodes. I then used fresh 64 MiB
> volumes
> for the runs above; their filesystem checks passed without repair.

It looks that we have enough issues yet for the fix.

Thanks,
Slava.

> 
> No KASAN report or kernel BUG/WARNING was observed during these runs.
> 
> Thanks,
> Hengyu

Re: [PATCH] hfs: avoid reusing occupied CNIDs after deletion

[Viacheslav Dubeyko]

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.

Frankly speaking, I don't see how your modification can fix anything.
From my point of view, the current logic is correct. Probably, the call
of this method is not in the proper place.

> 
> 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.
> 
> Fixes: a06ec283e125 ("hfs: add logic of correcting a next unused
> CNID")
> Cc: stable@vger.kernel.org
> Assisted-by: LLM
> Signed-off-by: Hengyu Liang <hengyul@cs.unc.edu>
> ---
> 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)) {

I don't quite follow why do we need to change this check? If cnid + 1
is smaller than the maximum one, then cnid + 1 is in use yet. We don't
need to execute any additional logic. What am I missing here?

>  		/* 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);

Why do we need to check something for previous one? If the bigger cnid
is in use, then we don't need to do anything here.

This patch doesn't make sense to me. I don't see how it can fix
anything. Could you please explain more clearly the problem and the
fix?

Thanks,
Slava.

> +	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;
>  

Re: [PATCH] hfs: avoid reusing occupied CNIDs after deletion

[Hengyu Liang]

Hi Slava,

On Mon, Oct 19, 2026 at 04:29:16PM -0700, Viacheslav Dubeyko wrote:
> Frankly speaking, I don't see how your modification can fix anything.
> From my point of view, the current logic is correct. Probably, the
> call of this method is not in the proper place.

Sorry, my description was not clear enough. Here is the reproducer
with the actual CNIDs, on a freshly formatted volume:

    operation    allocated CNID    next_id afterwards
    mkdir z            16                 17
    create a           17                 18
    create b           18                 19

rm b calls hfs_correct_next_unused_CNID() with cnid 18 and next_id 19,
after b's file and thread records have been removed. The catalog leaf
records are then, in key order:

    key                type           CNID
    (1, "untitled")    dir              2
    (2, "")            dir thread
    (2, "a")           file            17
    (2, "z")           dir             16
    (16, "")           dir thread
    (17, "")           file thread

The backward scan skips the two thread records at the end and stops at
z, so it changes next_id from 19 to 17, although a still uses 17. The
next create gets CNID 17, hfs_cat_create() finds a's thread record and
returns -EEXIST. The correct value is 18.

So the call site is not the problem: the records are already gone when
the correction runs, and calling it earlier or later would not change
the result, because z still sorts last. The problem is that file and
directory records are ordered by (parent ID, name), not by their own
CNID, so the last one need not hold the largest remaining CNID. The
patch keeps the call where it is, so the drNxtCNID correction that
generic/736 needs stays, and only makes the scan take the maximum over
all of them.

The unpatched run in my previous mail matches this: the first create
of c failed, and the retry got CNID 18, so the failed attempt had been
given 17.

> I don't quite follow why do we need to change this check? If cnid + 1
> is smaller than the maximum one, then cnid + 1 is in use yet. We
> don't need to execute any additional logic. What am I missing here?

Nothing; both checks return early in that case. != additionally
returns early when cnid + 1 > next_id, where the cmpxchg in
hfs_set_next_unused_CNID() cannot succeed anyway. It is not needed for
the fix (in the example both checks go on to the correction), and I
can drop it in v2.

> Why do we need to check something for previous one? If the bigger
> cnid is in use, then we don't need to do anything here.

The lookup only runs when cnid + 1 == next_id, i.e. the deleted CNID
was the largest one allocated, so no bigger CNID is in use. If
cnid - 1 still exists, it is the largest remaining CNID, and next_id
can be set to cnid without walking the catalog: in the example,
deleting 18 finds 17 and sets next_id to 18. Because the fallback now
walks the whole catalog instead of stopping at the first record, this
keeps the common case cheap. Only if the lookup returns -ENOENT does
the patch scan all records, which also covers files without the
optional thread record.

Thanks,
Hengyu

Re: [PATCH] hfs: avoid reusing occupied CNIDs after deletion

[Viacheslav Dubeyko]

On Wed, 2026-10-21 at 11:31 -0400, Hengyu Liang wrote:
> Hi Slava,
> 
> On Mon, Oct 19, 2026 at 04:29:16PM -0700, Viacheslav Dubeyko wrote:
> > Frankly speaking, I don't see how your modification can fix
> > anything.
> > From my point of view, the current logic is correct. Probably, the
> > call of this method is not in the proper place.
> 
> Sorry, my description was not clear enough. Here is the reproducer
> with the actual CNIDs, on a freshly formatted volume:
> 
>     operation    allocated CNID    next_id afterwards
>     mkdir z            16                 17
>     create a           17                 18
>     create b           18                 19
> 
> rm b calls hfs_correct_next_unused_CNID() with cnid 18 and next_id
> 19,
> after b's file and thread records have been removed. The catalog leaf
> records are then, in key order:
> 
>     key                type           CNID
>     (1, "untitled")    dir              2
>     (2, "")            dir thread
>     (2, "a")           file            17
>     (2, "z")           dir             16
>     (16, "")           dir thread
>     (17, "")           file thread
> 

I think I see your point. So, I think that fix is much simpler. We need
to add the thread records processing here [1]:

			if (rec.type == HFS_CDR_DIR) {
				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;
			} else if (rec.type == HFS_CDR_FIL) {
				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;
			}

#define HFS_CDR_DIR		0x01	/* folder (directory) */
#define HFS_CDR_FIL		0x02	/* file */
#define HFS_CDR_THD		0x03	/* folder (directory) thread
*/
#define HFS_CDR_FTH		0x04	/* file thread */

The current logic simply misses the HFS_CDR_THD and HFS_CDR_FTH cases
processing.

Thanks,
Slava.

> The backward scan skips the two thread records at the end and stops
> at
> z, so it changes next_id from 19 to 17, although a still uses 17. The
> next create gets CNID 17, hfs_cat_create() finds a's thread record
> and
> returns -EEXIST. The correct value is 18.
> 
> So the call site is not the problem: the records are already gone
> when
> the correction runs, and calling it earlier or later would not change
> the result, because z still sorts last. The problem is that file and
> directory records are ordered by (parent ID, name), not by their own
> CNID, so the last one need not hold the largest remaining CNID. The
> patch keeps the call where it is, so the drNxtCNID correction that
> generic/736 needs stays, and only makes the scan take the maximum
> over
> all of them.
> 
> The unpatched run in my previous mail matches this: the first create
> of c failed, and the retry got CNID 18, so the failed attempt had
> been
> given 17.
> 
> > I don't quite follow why do we need to change this check? If cnid +
> > 1
> > is smaller than the maximum one, then cnid + 1 is in use yet. We
> > don't need to execute any additional logic. What am I missing here?
> 
> Nothing; both checks return early in that case. != additionally
> returns early when cnid + 1 > next_id, where the cmpxchg in
> hfs_set_next_unused_CNID() cannot succeed anyway. It is not needed
> for
> the fix (in the example both checks go on to the correction), and I
> can drop it in v2.
> 
> > Why do we need to check something for previous one? If the bigger
> > cnid is in use, then we don't need to do anything here.
> 
> The lookup only runs when cnid + 1 == next_id, i.e. the deleted CNID
> was the largest one allocated, so no bigger CNID is in use. If
> cnid - 1 still exists, it is the largest remaining CNID, and next_id
> can be set to cnid without walking the catalog: in the example,
> deleting 18 finds 17 and sets next_id to 18. Because the fallback now
> walks the whole catalog instead of stopping at the first record, this
> keeps the common case cheap. Only if the lookup returns -ENOENT does
> the patch scan all records, which also covers files without the
> optional thread record.
> 
> Thanks,
> Hengyu

[1] https://elixir.bootlin.com/linux/v7.3/source/fs/hfs/catalog.c#L349

Re: [PATCH] hfs: avoid reusing occupied CNIDs after deletion

[Hengyu Liang]

Hi Slava,

On Wed, Oct 21, 2026 at 03:26:10PM -0700, Viacheslav Dubeyko wrote:
> I think I see your point. So, I think that fix is much simpler. We need
> to add the thread records processing here [1]:
[...]
> The current logic simply misses the HFS_CDR_THD and HFS_CDR_FTH cases
> processing.

Thanks. I tried this in KVM on a804c5742bff. It fixes the example from
my last mail only in part, for two reasons.

First, a thread record's own CNID is in its key. rec.thread.ParID is
the CNID of the parent. In the example, a's thread is (17, "") with
ParID 2, so taking rec.thread.ParID sets next_id to 16, and the next
create fails with -EEXIST on z. Taking the CNID from the key gives 18,
which is right.

Second, even with the key, the scan still stops at the first record it
finds, and the last record need not hold the largest CNID:

    operation    allocated CNID
    create a          16
    mkdir y           17
    create b          18
    mv a y/
    rm b

The last records are now (17, "") for y's thread and (17, "a") for a's
file record, with CNID 16. The scan stops at (17, "a") and sets next_id
to 17, which y still uses, so the next create fails with -EEXIST.

File threads are also optional (HFS_FIL_THD; hfs_cat_move() already
handles files without one). If a (CNID 17) in the example has no
thread, the next create gets CNID 17 as well, without an error, because
hfs_cat_create() only checks for an existing thread.

Result of creating the next file in each case:

                        unpatched   thread ParID   thread key   patch
    example (z, a, b)   -EEXIST     -EEXIST        18           18
    mv a into y         -EEXIST     -EEXIST        -EEXIST      18
    a without thread    17 (dup)    -EEXIST        17 (dup)     18

So the scan needs the largest CNID over all records, not the first one
it finds. This is what the patch does; the cnid - 1 lookup only avoids
the full scan in the common case.

If this looks right to you, I will send v2 without the != change.

Thanks,
Hengyu

Re: [PATCH] hfs: avoid reusing occupied CNIDs after deletion

[Viacheslav Dubeyko]

On Thu, 2026-10-22 at 08:06 -0400, Hengyu Liang wrote:
> Hi Slava,
> 
> On Wed, Oct 21, 2026 at 03:26:10PM -0700, Viacheslav Dubeyko wrote:
> > I think I see your point. So, I think that fix is much simpler. We
> > need
> > to add the thread records processing here [1]:
> [...]
> > The current logic simply misses the HFS_CDR_THD and HFS_CDR_FTH
> > cases
> > processing.
> 
> Thanks. I tried this in KVM on a804c5742bff. It fixes the example
> from
> my last mail only in part, for two reasons.
> 
> First, a thread record's own CNID is in its key. rec.thread.ParID is
> the CNID of the parent. In the example, a's thread is (17, "") with
> ParID 2, so taking rec.thread.ParID sets next_id to 16, and the next
> create fails with -EEXIST on z. Taking the CNID from the key gives
> 18,
> which is right.
> 
> Second, even with the key, the scan still stops at the first record
> it
> finds, and the last record need not hold the largest CNID:
> 
>     operation    allocated CNID
>     create a          16
>     mkdir y           17
>     create b          18
>     mv a y/
>     rm b
> 
> The last records are now (17, "") for y's thread and (17, "a") for
> a's
> file record, with CNID 16. The scan stops at (17, "a") and sets
> next_id
> to 17, which y still uses, so the next create fails with -EEXIST.
> 
> File threads are also optional (HFS_FIL_THD; hfs_cat_move() already
> handles files without one). If a (CNID 17) in the example has no
> thread, the next create gets CNID 17 as well, without an error,
> because
> hfs_cat_create() only checks for an existing thread.
> 
> Result of creating the next file in each case:
> 
>                         unpatched   thread ParID   thread key   patch
>     example (z, a, b)   -EEXIST     -EEXIST        18           18
>     mv a into y         -EEXIST     -EEXIST        -EEXIST      18
>     a without thread    17 (dup)    -EEXIST        17 (dup)     18
> 
> So the scan needs the largest CNID over all records, not the first
> one
> it finds. This is what the patch does; the cnid - 1 lookup only
> avoids
> the full scan in the common case.
> 
> If this looks right to you, I will send v2 without the != change.
> 
> 

I have refreshed my memory related to HFS's Catalog b-tree mechanics.
And I see that my confusion was related to expectations that threads
records should present. As far as I can see, folder threads are
mandatory, but file threads are optional. As a result, we cannot play
the "dirty" tricks and, currently, we can only rely on existing search
functionality in the b-tree. And I mean here that after every delete
operation we need:
(1) Check that deleted CNID is the previous to the next CNID. If it is
not, then do nothing.
(2) Oppositely, we need to execute standard b-tree search in the loop
by decrementing the CNID.

This approach could be not very efficient if we deleted a lot of
records in the between. So, what can be the more optimal approach?
Potentially, we can consider to have a small bitmap of allocated CNID
in every b-tree's node. Any other optimization ideas?

So, let's discuss the proper solution at first. If you still believe
that your patch approach is still correct, please, convince me by clean
explanation of the approach.

Thanks,
Slava.