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

[PATCH v2] 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() 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.

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 */
 
 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
-- 
2.53.0

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

[Viacheslav Dubeyko]

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

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

[Viacheslav Dubeyko]

Hi Hengyu,

On Thu, 2026-11-12 at 14:34 -0800, Viacheslav Dubeyko wrote:
> 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. 
> 
> > 

I've spent more time considering this patch. Probably, my worries could
be wrong. But the main issue of the commit message that it contains not
enough details about the problem and how implemented approach is
solving the problem. Could you explain it in more details? It could
help anyone to understand the correctness of solution.

Thanks,
Slava.

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

[Hengyu Liang]

Hi Slava,

On Thu, 2026-11-12 at 14:34 -0800, Viacheslav Dubeyko wrote:
> 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?

Yes. The patch never searches for a CNID, neither the largest one nor
largest - 1. It only needs the maximum of the CNIDs of all file and
directory records, and a maximum does not depend on the order of the
records:

- max_cnid of a leaf node is the largest DirID / FlNum of its file and
  directory records. The CNID is read from the record data, not from
  the key, so the parent ID and the thread records do not matter.
- max_cnid of an index node is the largest max_cnid of its children.

So the root holds the largest CNID in use, wherever the records are.
When the record with the largest CNID is removed, only the nodes on the
path from its leaf to the root are computed again; every other node
keeps its value. For example:

              root: 20
             /        \
     leaf A: 19      leaf B: 20
     (16, 19, 17)    (20, 18)

  rm 20: leaf B -> 18, root = max(19, 18) = 19, next_id = 20
  rm 19: leaf A -> 17, root = max(17, 18) = 18, next_id = 19

Both times largest - 1 was in the other leaf, and it was counted because
that leaf keeps its own maximum.

next_id is then set to max + 1. Every CNID in use is <= max, so max + 1
is free. Deleted CNIDs below max are never reused, so we never need to
know which CNIDs are free. A red-black tree of deleted CNIDs would only
be needed to reuse those holes.

To check it, a debug build compared every cached max_cnid with the
value computed from the records after each catalog insert and remove:
about 88,000 full-tree checks on 2,000 files with random operations and
4 writers, plus a run under memory pressure that freed 55,630 nodes and
read them again. There was no mismatch.

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

max_cnid is not on disk, so a node that hfs_bnode_find() has just read
does not have it. For a leaf node it could be computed from that node
alone, but for an index node it needs every node below it. Computing it
at read time would read the whole catalog at mount, and again for an
index node that hfs_release_folio() freed and that is read again later.

The flag means "max_cnid of this node has been computed".
hfs_btree_max_cnid() computes only the nodes without it, and only when
the newest file or directory is deleted. The first such delete after
mount still reads the whole catalog once; later ones only recompute the
nodes on the path of the removed record. The flag is also cleared when
the largest CNID of a node is removed, and on a split, because records
move to the new node.

Thanks,
Hengyu