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

[Hengyu Liang <hengyul@cs.unc.edu>]

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

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

Which do you prefer? I can turn either into the next version.

Thanks,
Hengyu