Re: [PATCH v2] hfs: avoid reusing occupied CNIDs after deletion
From: Viacheslav Dubeyko
Date: Mon Nov 16 2026 - 20:02:19 EST
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.
>
> Fixes: a06ec283e125 ("hfs: add logic of correcting a next unused
> CNID")
> Cc: stable@xxxxxxxxxxxxxxx
> Suggested-by: Viacheslav Dubeyko <slava@xxxxxxxxxxx>
> Assisted-by: LLM
> Signed-off-by: Hengyu Liang <hengyul@xxxxxxxxxx>
> ---
> 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@xxxxxxxxxx
>
> 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);
This function is completely not clear. You try to read the hfs_cat_rec.
Simply read it and analyze the record. Now it looks like a dark magic.
> +}
> +
> +/* 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)
Is this insert argument used anywhere?
> +{
> + 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)
I would like to see some inline function with good name for this check.
> + return;
Please, add empty line here.
> + cnid = hfs_brec_cnid(node, off);
> + if (!cnid)
The #0 is reserved CNID. It's not good choice for such check.
> + return;
> +
> + for (;;) {
I assume that we limited by tree's height here. Could we used it
instead of infinite loop?
> + 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)
I dislike insert like a boolean value. Why do we need to inform this
function about insert? Why this function cannot make this decision
alone?
> + 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 */
> + }
Ad empty line.
> + nidx = node->parent;
> + hfs_bnode_put(node);
> +
> + if (done)
You don't need in done if you are limited by b-tree height.
> + return;
Add empty line.
> + if (!nidx)
> + break;
> + }
> +
> + /* a parent could not be reached */
> + hfs_btree_drop_max_cnid(tree);
> +}
I will continue the review tomorrow. I don't have more time today. :)
Thanks,
Slava.
> +
> +/*
> + * 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