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

[Viacheslav Dubeyko]

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?

>   - 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.