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

[Viacheslav Dubeyko <slava@dubeyko.com>]

On Thu, 2026-10-22 at 08:06 -0400, Hengyu Liang wrote:
> Hi Slava,
> 
> On Wed, Oct 21, 2026 at 03:26:10PM -0700, Viacheslav Dubeyko wrote:
> > I think I see your point. So, I think that fix is much simpler. We
> > need
> > to add the thread records processing here [1]:
> [...]
> > The current logic simply misses the HFS_CDR_THD and HFS_CDR_FTH
> > cases
> > processing.
> 
> Thanks. I tried this in KVM on a804c5742bff. It fixes the example
> from
> my last mail only in part, for two reasons.
> 
> First, a thread record's own CNID is in its key. rec.thread.ParID is
> the CNID of the parent. In the example, a's thread is (17, "") with
> ParID 2, so taking rec.thread.ParID sets next_id to 16, and the next
> create fails with -EEXIST on z. Taking the CNID from the key gives
> 18,
> which is right.
> 
> Second, even with the key, the scan still stops at the first record
> it
> finds, and the last record need not hold the largest CNID:
> 
>     operation    allocated CNID
>     create a          16
>     mkdir y           17
>     create b          18
>     mv a y/
>     rm b
> 
> The last records are now (17, "") for y's thread and (17, "a") for
> a's
> file record, with CNID 16. The scan stops at (17, "a") and sets
> next_id
> to 17, which y still uses, so the next create fails with -EEXIST.
> 
> File threads are also optional (HFS_FIL_THD; hfs_cat_move() already
> handles files without one). If a (CNID 17) in the example has no
> thread, the next create gets CNID 17 as well, without an error,
> because
> hfs_cat_create() only checks for an existing thread.
> 
> Result of creating the next file in each case:
> 
>                         unpatched   thread ParID   thread key   patch
>     example (z, a, b)   -EEXIST     -EEXIST        18           18
>     mv a into y         -EEXIST     -EEXIST        -EEXIST      18
>     a without thread    17 (dup)    -EEXIST        17 (dup)     18
> 
> So the scan needs the largest CNID over all records, not the first
> one
> it finds. This is what the patch does; the cnid - 1 lookup only
> avoids
> the full scan in the common case.
> 
> If this looks right to you, I will send v2 without the != change.
> 
> 

I have refreshed my memory related to HFS's Catalog b-tree mechanics.
And I see that my confusion was related to expectations that threads
records should present. As far as I can see, folder threads are
mandatory, but file threads are optional. As a result, we cannot play
the "dirty" tricks and, currently, we can only rely on existing search
functionality in the b-tree. And I mean here that after every delete
operation we need:
(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.

This approach could be not very efficient if we deleted a lot of
records in the between. So, what can be the more optimal approach?
Potentially, we can consider to have a small bitmap of allocated CNID
in every b-tree's node. Any other optimization ideas?

So, let's discuss the proper solution at first. If you still believe
that your patch approach is still correct, please, convince me by clean
explanation of the approach.

Thanks,
Slava.