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

[Viacheslav Dubeyko <slava@dubeyko.com>]

On Thu, 2026-11-12 at 06:01 -0500, Hengyu Liang wrote:
> Commit a06ec283e125 ("hfs: add logic of correcting a next unused
> CNID")
> made hfs_correct_next_unused_CNID() lower the next CNID after the
> newest file or directory is deleted. It takes the CNID of the last
> file or directory record in the catalog as the largest CNID in use.
> 
> However, catalog records are sorted by parent ID and name, not by
> CNID, so the next CNID can be one that is still in use. As of now,
> creating a file after deleting the newest one can fail with EEXIST.
> Commit 6592287869bf ("hfs: fix incorrect inode ID assignment in
> hfs_new_inode()") exposed this issue.
> 
> The issue can be reproduced on a freshly formatted HFS volume with:
> 
>     mkdir z
>     touch a b
>     rm b
>     touch c
> 
> Without this change, the result is:
> 
>     touch: cannot touch 'c': File exists
> 
> With it, c is created.
> 
> Keep the largest CNID of the records in and below each catalog node
> in memory, in leaf nodes and in index nodes, so that the root node
> gives the largest CNID in use. Adding a record raises it in the nodes
> above, and removing the record with the largest CNID makes them
> compute it again.

I am still not sure that this approach could work. If we haven't the
thread records in the b-tree, then we sort records by parent CNID. But
folder can contain child with any CNID. So, if we keep the largest CNID
in use, then, technically speaking largest CNID - 1 can be located at
any node (it doesn't matter if it is used or not). Even if we found
node #1 with largest CNID, then it doesn't mean that largest CNID - 1
is located at the same node #1. And even if we cannot find the largest
CNID - 1 value, then it doesn't mean that this value hasn't been
allocated already as child CNID of some parent CNID (because records
are ordered by parent CNID). Are you sure that this approach will
finally work? This is why I started to guess that maybe we need to
think about Red-Black tree that can keep deleted CNIDs (however, it
could be not efficient way).

So, I would like to be convinced that this approach can definitely work
before taking a deeper code review. I suspect that we still is not good
shape yet. 

> 
> Fixes: a06ec283e125 ("hfs: add logic of correcting a next unused
> CNID")
> Cc: stable@vger.kernel.org
> Suggested-by: Viacheslav Dubeyko <slava@dubeyko.com>
> Assisted-by: LLM
> Signed-off-by: Hengyu Liang <hengyul@cs.unc.edu>
> ---
> Changes in v2:
> - Keep the largest CNID in memory in every catalog node, leaf and
>   index, as Viacheslav Dubeyko suggested. v1 walked the leaf nodes.
> - Rebase on hfs for-next.
> - v1:
> https://lore.kernel.org/r/20261015110114.1649059-1-hengyul@cs.unc.edu
> 
> Tested in KVM with KASAN on 34ee5f8c2198, without and with this
> patch.
> All fstests on HFS: 24 failures without the patch, 20 with it, no new
> failures. Deleting 8000 files:
> 
>                                 unpatched   patched
>     newest first                11 s        0.36 s
>     odd ones, then even ones
>     newest first                3.8 s       0.19 s
> 
> Creating the files (0.54 s and 0.55 s) and deleting them oldest first
> (0.37 s and 0.38 s) take about the same time.
> 
>  fs/hfs/brec.c    | 172
> +++++++++++++++++++++++++++++++++++++++++++++++
>  fs/hfs/btree.h   |   5 ++
>  fs/hfs/catalog.c |  96 +++-----------------------
>  3 files changed, 186 insertions(+), 87 deletions(-)
> 
> diff --git a/fs/hfs/brec.c b/fs/hfs/brec.c
> index 1ca1ee9f73ef..318bbee43529 100644
> --- a/fs/hfs/brec.c
> +++ b/fs/hfs/brec.c
> @@ -62,6 +62,174 @@ u16 hfs_brec_keylen(struct hfs_bnode *node, u16
> rec)
>  	return retval;
>  }
>  
> +/* Get the CNID of a file or directory record of the catalog tree */
> +static u32 hfs_brec_cnid(struct hfs_bnode *node, u32 off)
> +{
> +	__be32 cnid;
> +
> +	switch (hfs_bnode_read_u8(node, off)) {
> +	case HFS_CDR_DIR:
> +		off += offsetof(struct hfs_cat_dir, DirID);
> +		break;
> +	case HFS_CDR_FIL:
> +		off += offsetof(struct hfs_cat_file, FlNum);
> +		break;
> +	default:
> +		return 0;
> +	}
> +	hfs_bnode_read(node, &cnid, off, sizeof(cnid));
> +	return be32_to_cpu(cnid);
> +}
> +
> +/* Forget max_cnid of all nodes of the tree */
> +static void hfs_btree_drop_max_cnid(struct hfs_btree *tree)
> +{
> +	struct hfs_bnode *node;
> +	int i;
> +
> +	spin_lock(&tree->hash_lock);
> +	for (i = 0; i < NODE_HASH_SIZE; i++) {
> +		for (node = tree->node_hash[i]; node; node = node-
> >next_hash)
> +			clear_bit(HFS_BNODE_MAX_CNID, &node->flags);
> +	}
> +	spin_unlock(&tree->hash_lock);
> +}
> +
> +/*
> + * The record at @off has been added to the catalog leaf @node, or
> is about
> + * to be removed from it. Update max_cnid of the node and of its
> parents:
> + * a new CNID can only raise it, and after the largest CNID is gone
> it has
> + * to be computed again.
> + */
> +static void hfs_brec_update_max_cnid(struct hfs_bnode *node, u32
> off,
> +				     bool insert)
> +{
> +	struct hfs_btree *tree = node->tree;
> +	u32 nidx = node->this;
> +	u32 cnid;
> +	bool done;
> +
> +	if (tree->cnid != HFS_CAT_CNID || node->type !=
> HFS_NODE_LEAF)
> +		return;
> +	cnid = hfs_brec_cnid(node, off);
> +	if (!cnid)
> +		return;
> +
> +	for (;;) {
> +		node = hfs_bnode_find(tree, nidx);
> +		if (IS_ERR(node))
> +			break;
> +
> +		done = nidx == tree->root;
> +		if (test_bit(HFS_BNODE_MAX_CNID, &node->flags)) {
> +			if (insert && node->max_cnid < cnid)
> +				node->max_cnid = cnid;
> +			else if (!insert && node->max_cnid <= cnid)
> +				clear_bit(HFS_BNODE_MAX_CNID, &node-
> >flags);
> +			else
> +				done = true;	/* the parents do
> not change */
> +		}
> +		nidx = node->parent;
> +		hfs_bnode_put(node);
> +
> +		if (done)
> +			return;
> +		if (!nidx)
> +			break;
> +	}
> +
> +	/* a parent could not be reached */
> +	hfs_btree_drop_max_cnid(tree);
> +}
> +
> +/*
> + * Compute max_cnid of a catalog node: the largest CNID of the file
> and
> + * directory records of a leaf node, or the largest max_cnid of the
> children
> + * of an index node. If a child has no max_cnid yet, return the
> number of
> + * that child in @child instead.
> + */
> +static int hfs_brec_calc_max_cnid(struct hfs_bnode *node, u32
> *child)
> +{
> +	struct hfs_bnode *cnode;
> +	u32 max_cnid = 0;
> +	u16 off, len, keylen;
> +	__be32 data;
> +	int i;
> +
> +	for (i = 0; i < node->num_recs; i++) {
> +		len = hfs_brec_lenoff(node, i, &off);
> +		keylen = hfs_brec_keylen(node, i);
> +		if (!keylen || keylen + sizeof(data) > len)
> +			return -EIO;
> +		off += keylen;
> +
> +		if (node->type == HFS_NODE_LEAF) {
> +			max_cnid = max(max_cnid, hfs_brec_cnid(node,
> off));
> +			continue;
> +		}
> +
> +		hfs_bnode_read(node, &data, off, sizeof(data));
> +		cnode = hfs_bnode_find(node->tree,
> be32_to_cpu(data));
> +		if (IS_ERR(cnode))
> +			return PTR_ERR(cnode);
> +		if (cnode->height != node->height - 1) {
> +			hfs_bnode_put(cnode);
> +			return -EIO;
> +		}
> +		if (!test_bit(HFS_BNODE_MAX_CNID, &cnode->flags)) {
> +			cnode->parent = node->this;
> +			*child = cnode->this;
> +			hfs_bnode_put(cnode);
> +			return 0;
> +		}
> +		max_cnid = max(max_cnid, cnode->max_cnid);
> +		hfs_bnode_put(cnode);
> +	}
> +
> +	node->max_cnid = max_cnid;
> +	set_bit(HFS_BNODE_MAX_CNID, &node->flags);
> +	return 0;
> +}
> +
> +/*
> + * hfs_btree_max_cnid()
> + *
> + * Find the largest CNID of the file and directory records of the
> catalog
> + * tree. It is max_cnid of the root node. max_cnid is not stored on
> disk,
> + * so walk down to the nodes that do not have it and compute it from
> the
> + * bottom up.
> + */
> +int hfs_btree_max_cnid(struct hfs_btree *tree, u32 *max_cnid)
> +{
> +	struct hfs_bnode *node;
> +	u32 nidx = tree->root;
> +	u32 child;
> +	int res = 0;
> +
> +	*max_cnid = 0;
> +	while (nidx && !res) {
> +		node = hfs_bnode_find(tree, nidx);
> +		if (IS_ERR(node))
> +			return PTR_ERR(node);
> +
> +		child = 0;
> +		if (!test_bit(HFS_BNODE_MAX_CNID, &node->flags))
> +			res = hfs_brec_calc_max_cnid(node, &child);
> +
> +		if (res || child) {
> +			nidx = child;
> +		} else if (nidx == tree->root) {
> +			*max_cnid = node->max_cnid;
> +			nidx = 0;
> +		} else {
> +			/* a node that was read again has lost its
> parent */
> +			nidx = node->parent ? node->parent : tree-
> >root;
> +		}
> +		hfs_bnode_put(node);
> +	}
> +	return res;
> +}
> +
>  int hfs_brec_insert(struct hfs_find_data *fd, void *entry, u32
> entry_len)
>  {
>  	struct hfs_btree *tree;
> @@ -131,6 +299,7 @@ int hfs_brec_insert(struct hfs_find_data *fd,
> void *entry, u32 entry_len)
>  skip:
>  	hfs_bnode_write(node, fd->search_key, data_off, key_len);
>  	hfs_bnode_write(node, entry, data_off + key_len, entry_len);
> +	hfs_brec_update_max_cnid(node, data_off + key_len, true);
>  	hfs_bnode_dump(node);
>  
>  	/*
> @@ -183,6 +352,7 @@ int hfs_brec_remove(struct hfs_find_data *fd)
>  
>  	tree = fd->tree;
>  	node = fd->bnode;
> +	hfs_brec_update_max_cnid(node, fd->entryoffset, false);
>  again:
>  	rec_off = tree->node_size - (fd->record + 2) * 2;
>  	end_off = tree->node_size - (node->num_recs + 1) * 2;
> @@ -322,6 +492,8 @@ static struct hfs_bnode *hfs_bnode_split(struct
> hfs_find_data *fd)
>  	}
>  	new_node->num_recs = node->num_recs - num_recs;
>  	node->num_recs = num_recs;
> +	/* the records that move to the new node may hold the
> largest CNID */
> +	clear_bit(HFS_BNODE_MAX_CNID, &node->flags);
>  
>  	new_rec_off = tree->node_size - rec_size;
>  	new_off = node_desc_size;
> diff --git a/fs/hfs/btree.h b/fs/hfs/btree.h
> index 1f703f2c53d8..21f69cddc683 100644
> --- a/fs/hfs/btree.h
> +++ b/fs/hfs/btree.h
> @@ -62,6 +62,9 @@ struct hfs_bnode {
>  	u8 type;
>  	u8 height;
>  
> +	/* catalog tree: largest CNID in the records in and below
> the node */
> +	u32 max_cnid;
> +
>  	struct hfs_bnode *next_hash;
>  	unsigned long flags;
>  	wait_queue_head_t lock_wq;
> @@ -73,6 +76,7 @@ struct hfs_bnode {
>  #define HFS_BNODE_ERROR		0
>  #define HFS_BNODE_NEW		1
>  #define HFS_BNODE_DELETED	2
> +#define HFS_BNODE_MAX_CNID	3	/* max_cnid is valid */

Why do we need this flag? If node is created, then it should have valid
max_cnid.

Thanks,
Slava.

>  
>  struct hfs_find_data {
>  	btree_key *key;
> @@ -140,6 +144,7 @@ extern u16 hfs_brec_lenoff(struct hfs_bnode
> *node, u16 rec, u16 *off);
>  extern u16 hfs_brec_keylen(struct hfs_bnode *node, u16 rec);
>  extern int hfs_brec_insert(struct hfs_find_data *fd, void *entry,
> u32 entry_len);
>  extern int hfs_brec_remove(struct hfs_find_data *fd);
> +extern int hfs_btree_max_cnid(struct hfs_btree *tree, u32
> *max_cnid);
>  
>  /* bfind.c */
>  extern int hfs_find_init(struct hfs_btree *tree, struct
> hfs_find_data *fd);
> diff --git a/fs/hfs/catalog.c b/fs/hfs/catalog.c
> index 490c5e130da3..ead094e44c9a 100644
> --- a/fs/hfs/catalog.c
> +++ b/fs/hfs/catalog.c
> @@ -271,102 +271,24 @@ void hfs_set_next_unused_CNID(struct
> super_block *sb,
>  static
>  int hfs_correct_next_unused_CNID(struct super_block *sb, u32 cnid)
>  {
> -	struct hfs_btree *cat_tree;
> -	struct hfs_bnode *node;
> -	s64 leaf_head;
> -	s64 leaf_tail;
> -	s64 node_id;
> +	u32 max_cnid;
> +	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;
>  	}
>  
> -	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;
> -	}
> -
> -	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;
> -		}
> -
> -		hfs_dbg("node %lld, leaf_tail %lld, leaf_head
> %lld\n",
> -			node_id, leaf_tail, leaf_head);
> -
> -		hfs_bnode_dump(node);
> -
> -		for (i = node->num_recs - 1; i >= 0; i--) {
> -			hfs_cat_rec rec;
> -			u16 off, len, keylen;
> -			int entryoffset;
> -			int entrylength;
> -			u32 found_cnid;
> -
> -			len = hfs_brec_lenoff(node, i, &off);
> -			keylen = hfs_brec_keylen(node, i);
> -			if (keylen == 0) {
> -				pr_err("fail to get the keylen: "
> -					"node_id %lld, record index
> %d\n",
> -					node_id, i);
> -				return -EINVAL;
> -			}
> -
> -			entryoffset = off + keylen;
> -			entrylength = len - keylen;
> -
> -			if (entrylength > sizeof(rec)) {
> -				pr_err("unexpected record length: "
> -					"entrylength %d\n",
> -					entrylength);
> -				return -EINVAL;
> -			}
> -
> -			hfs_bnode_read(node, &rec, entryoffset,
> entrylength);
> -
> -			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;
> -			}
> -		}
> -
> -		node_id = node->prev;
> -		hfs_bnode_put(node);
> -
> -	} while (node_id >= leaf_head);
> +	res = hfs_btree_max_cnid(HFS_SB(sb)->cat_tree, &max_cnid);
> +	if (res)
> +		return res;
>  
> -	return -ENOENT;
> +	hfs_dbg("max_cnid %u\n", max_cnid);
> +	hfs_set_next_unused_CNID(sb, cnid, max_cnid);
> +	return 0;
>  }
>  
>  /*
> 
> base-commit: 34ee5f8c2198db9585da6c181c50869d2eb43c3a