Re: [PATCH] hfs: avoid reusing occupied CNIDs after deletion
From: Hengyu Liang
Date: Fri Oct 23 2026 - 13:33:51 EST
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?
Thanks,
Hengyu