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

[Viacheslav Dubeyko <slava@dubeyko.com>]

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