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

[Viacheslav Dubeyko <slava@dubeyko.com>]

On Fri, 2026-10-23 at 13:32 -0400, Hengyu Liang wrote:
> Hi Slava,
> 
> On Thu, 2026-10-22 at 15:40 -0700, Viacheslav Dubeyko wrote:
> > (1) Check that deleted CNID is the previous to the next CNID. If it
> > is
> > not, then do nothing.
> > (2) Oppositely, we need to execute standard b-tree search in the
> > loop
> > by decrementing the CNID.
> 
> I tried this loop in KVM on a804c5742bff. It fixes the first two
> cases
> from my last mail, but not the third one. There a (CNID 17) has no
> thread, so the search for 17 fails, next_id goes back to 17, and the
> next file c gets CNID 17 too. a and c then share one inode, and
> fsck.hfs -fn reports nothing:
> 
>     echo AAA > a; rm b; echo CCC > c
> 
>                           unpatched or loop    patch
>     CNIDs of a and c      17, 17               17, 18
>     cat a, cat c          CCC, CCC             AAA, CCC
> 
> A search by CNID only finds threads, so it can show that a CNID is in
> use, but not that it is free. A file without a thread has its CNID
> only in its file record, which is keyed by parent and name. That is
> why the patch walks the leaf records when cnid - 1 is not found. Its
> first check, do nothing unless the deleted CNID is next_id - 1, is
> your step (1).
> 
> > Potentially, we can consider to have a small bitmap of allocated
> > CNID
> > in every b-tree's node. Any other optimization ideas?
> 
> A bitmap in the nodes would change the on-disk format.
> 
> Deleting 8000 files (KASAN kernel):
> 
>                                    unpatched   loop     patch
>     newest first                   13.1 s      0.40 s   0.44 s
>     odd ones, then even ones
>     newest first                   3.6 s       0.26 s   9.3 s
> 
> The patch is slow in the second case, because cnid - 1 is free on
> every delete there and each delete walks the catalog. One idea:
> next_id only has to stay above all CNIDs in use, and fsck.hfs accepts
> drNxtCNID up to 4096 above the largest CNID. So a delete could leave
> next_id alone when cnid - 1 is not found, and the walk could run once
> at unmount.
> 
> Would you prefer that, or the walk on delete as in the patch?
> 
> 

I am not suggesting to change the on-disk format. All modifications
should be in-core metadata structures only. The algorithm only solution
will be inefficient and it can hide bugs, anyway. I am thinking about
adding to the struct hfs_bnode (b-tree node) a special field: u32
max_cnid. Every time when we need to add or delete the record in the
node, we need to update the max_cnid field. For the case of add record
operation, we simply need to check that current max_cnid is
smaller/bigger/equal than adding one and change or not change the field
accordingly. For the case of delete: (1) we need to check all records
in the b-tree node (where we delete the record) and to find the biggest
one CNID in the b-tree node after the delete operation; (2) pass all
leaf nodes and to find the biggest one CNID for the b-tree. What do you
think? Does it make sense for you?

If you believe that this approach will not work, please, explain your
vision of solution in details.

Thanks,
Slava.