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

[Viacheslav Dubeyko <slava@dubeyko.com>]

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.