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

[Viacheslav Dubeyko <slava@dubeyko.com>]

On Mon, 2026-11-02 at 15:49 -0800, Viacheslav Dubeyko wrote:
> On Tue, 2026-10-27 at 23:59 -0400, Hengyu Liang wrote:
> > Hi Slava,
> > 
> > On Mon, 2026-10-26 at 10:20 -0700, Viacheslav Dubeyko wrote:
> > > I am not suggesting to change the on-disk format. All
> > > modifications
> > > should be in-core metadata structures only.
> > 
> > Sorry, I misread that.
> > 
> > > The algorithm only solution will be inefficient and it can hide
> > > bugs,
> > > anyway.
> > 
> > The table below is about efficiency. On bugs: in both variants
> > below,
> > a lookup or walk error leaves next_id unchanged, so it can only
> > stay
> > too high, never fall onto a CNID in use. Which bugs did you have in
> > mind?
> > 
> > > I am thinking about adding to the struct hfs_bnode (b-tree node)
> > > a
> > > special field: u32 max_cnid. [...] What do you think? Does it
> > > make
> > > sense for you?
> > 
> > Yes, it makes sense, and it works. I wrote a prototype (max_cnid
> > rebuilt when a node is read, raised on insert, rescanned on remove
> > and
> > after a split) and compared it with the unmount walk I suggested
> > last
> > time. Deleting 8000 files in KVM on v7.3 (KASAN):
> > 
> >                                 unpatched  max_cnid  unmount walk
> >     newest first                14 s       7.0 s     0.4 s
> >     odd ones, then even ones
> >     newest first                4.1 s      3.0 s     0.2 s
> > 
> > Both are correct: no duplicate CNID in any run, including the
> > threadless case from my last mail.
> > 
> > > If you believe that this approach will not work, please, explain
> > > your
> > > vision of solution in details.
> > 
> > The unmount walk, on a delete:
> > (1) do nothing unless cnid == next_id - 1 (your step (1));
> > (2) if cnid - 1 has a thread, set next_id = cnid;
> > (3) otherwise keep next_id, which is still above all CNIDs in use,
> > and
> >     set a flag.
> > At unmount, if the flag is set, hfs_mdb_close() walks the leaf
> > nodes
> > once and writes max + 1 to drNxtCNID. The walk cannot run in
> > sync_fs:
> > hfs_new_inode() takes a CNID before the catalog records are
> > inserted,
> > so a walk there could miss that CNID and lower next_id onto it.
> > 
> > Your max_cnid
> >   Pros:
> >   - next_id was exact after every delete in every run, so drNxtCNID
> >     on disk is right even after a crash or remount ro.
> >   - Nothing to do at unmount.
> >   Cons:
> >   - A delete of next_id - 1 still visits every leaf node (about
> > 3000
> >     here); the per-node max only saves parsing their records.
> >     Checking the thread of cnid - 1 first brings the first row to
> >     0.4 s, but not the second.
> 
> 
> I think we need to reuse the b-tree mechanics here. Let's use the
> index
> nodes for the search of biggest CNID. The b-tree has this exact goal
> to
> speed-up the search. So, we need to keep the max CNID not only in
> leaf
> nodes but in index nodes too. Do you follow my point?

Maybe, we need to consider a Red-Black tree here?

Thanks,
Slava.

> 
> >   - max_cnid must stay right on insert, remove, split and node read
> >     (hooks in bnode.c and brec.c). A missed update would let
> > next_id
> >     fall onto a CNID in use.
> 
> We should keep the max_cnid always valid. And b-tree operations can
> guarantee it for us.
> 
> > 
> > Unmount walk
> >   Pros:
> >   - A delete never walks the catalog; the one walk at unmount costs
> >     17 ms here (cold cache).
> >   - Only catalog.c and mdb.c change, not the b-tree code.
> 
> It's not about small change. It's about correct and efficient
> solution.
> 
> >   Cons:
> >   - next_id is not lowered during a mount: after deleting all 8000
> >     files oldest first, the next file gets CNID 8016, not 16.
> >   - After a crash or remount ro the high value stays on disk. In my
> >     8000-file crash test drNxtCNID stayed at 8015 on the empty
> > volume,
> >     more than 4096 above the largest CNID, and fsck.hfs -fn asked
> > for
> >     a minor MDB repair.
> 
> We cannot leave file system in corrupted state. We should prevent it
> by
> any cost.
> 
> > 
> > Which do you prefer? I can turn either into the next version.
> 
> I prefer to elaborate an approach that will be correct solution. I
> think we need to re-use the b-tree mechanics to improve the
> efficiency
> and to deliver the correct solution.
> 
> Thanks,
> Slava.