mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
From: Viacheslav Dubeyko <slava@dubeyko.com>
To: Hengyu Liang <hengyul@cs.unc.edu>
Cc: glaubitz@physik.fu-berlin.de, frank.li@vivo.com,
	 linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org,
	 stable@vger.kernel.org
Subject: Re: [PATCH v2] hfs: avoid reusing occupied CNIDs after deletion
Date: Tue, 17 Nov 2026 16:20:04 -0800	[thread overview]
Message-ID: <aad484f0a78493723cfe379df5916e9f7f2a2bb4.camel@dubeyko.com> (raw)
In-Reply-To: <138ca05e57377469c0e44126314c98d008629229.camel@dubeyko.com>

On Mon, 2026-11-16 at 17:02 -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.
> > 
> > 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);
> 
> 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)

Do you mean that we return CNID? I don't quite follow. We always have
any CNID in the node that will be maximum one for node. How is it
possible "If a child has no max_cnid yet, return the number of that
child in @child instead."?

> > +{
> > +	struct hfs_bnode *cnode;
> > +	u32 max_cnid = 0;

The max CNID cannot be lower that HFS_FIRSTUSER_CNID.

> > +	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) {

If it is the index node, then we don't need to traverse the items. No?

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

Please, add enough empty lines. I will share as many remarks as many
empty lines need to be in place.

> > +		if (cnode->height != node->height - 1) {
> > +			hfs_bnode_put(cnode);
> > +			return -EIO;

It looks like internal error but not I/O error.

> > +		}
> > +		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))

I still don't see a necessity in HFS_BNODE_MAX_CNID flag.

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

I don't understand the role of this boolean value. If doesn't matter if
we add, update, or delete the record, then we need to update the max
CNID. And only logic can detect if we really need to change anything
for this particular node.

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

We need to have comments at one place for the whole structure. Here it
looks not good at all.

> > +	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)) {

I still don't see the point why should we change anything here?

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

The max_cnid or max_cnid + 1?

Thanks,
Slava.

> > +	return 0;
> >  }
> >  
> >  /*
> > 
> > base-commit: 34ee5f8c2198db9585da6c181c50869d2eb43c3a

      reply	other threads:[~2026-11-18  0:20 UTC|newest]

Thread overview: 7+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2026-11-12 11:01 Hengyu Liang
2026-11-12 22:34 ` Viacheslav Dubeyko
2026-11-13 19:14   ` Viacheslav Dubeyko
2026-11-13 19:41   ` Hengyu Liang
2026-11-16 23:21     ` Viacheslav Dubeyko
2026-11-17  1:02 ` Viacheslav Dubeyko
2026-11-18  0:20   ` Viacheslav Dubeyko [this message]

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=aad484f0a78493723cfe379df5916e9f7f2a2bb4.camel@dubeyko.com \
    --to=slava@dubeyko.com \
    --cc=frank.li@vivo.com \
    --cc=glaubitz@physik.fu-berlin.de \
    --cc=hengyul@cs.unc.edu \
    --cc=linux-fsdevel@vger.kernel.org \
    --cc=linux-kernel@vger.kernel.org \
    --cc=stable@vger.kernel.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox

all inboxes | Powered by JetHome®