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

From: Viacheslav Dubeyko

Date: Mon Nov 16 2026 - 18:21:23 EST


On Fri, 2026-11-13 at 14:41 -0500, Hengyu Liang wrote:
> Hi Slava,
>
> On Thu, 2026-11-12 at 14:34 -0800, Viacheslav Dubeyko wrote:
> > I am still not sure that this approach could work. If we haven't
> > the
> > thread records in the b-tree, then we sort records by parent CNID.
> > But
> > folder can contain child with any CNID. So, if we keep the largest
> > CNID
> > in use, then, technically speaking largest CNID - 1 can be located
> > at
> > any node (it doesn't matter if it is used or not). Even if we found
> > node #1 with largest CNID, then it doesn't mean that largest CNID -
> > 1
> > is located at the same node #1. And even if we cannot find the
> > largest
> > CNID - 1 value, then it doesn't mean that this value hasn't been
> > allocated already as child CNID of some parent CNID (because
> > records
> > are ordered by parent CNID). Are you sure that this approach will
> > finally work?
>
> Yes. The patch never searches for a CNID, neither the largest one nor
> largest - 1. It only needs the maximum of the CNIDs of all file and
> directory records, and a maximum does not depend on the order of the
> records:
>
> - max_cnid of a leaf node is the largest DirID / FlNum of its file
> and
>   directory records. The CNID is read from the record data, not from
>   the key, so the parent ID and the thread records do not matter.
> - max_cnid of an index node is the largest max_cnid of its children.
>
> So the root holds the largest CNID in use, wherever the records are.
> When the record with the largest CNID is removed, only the nodes on
> the
> path from its leaf to the root are computed again; every other node
> keeps its value. For example:
>
>               root: 20
>              /        \
>      leaf A: 19      leaf B: 20
>      (16, 19, 17)    (20, 18)
>
>   rm 20: leaf B -> 18, root = max(19, 18) = 19, next_id = 20
>   rm 19: leaf A -> 17, root = max(17, 18) = 18, next_id = 19

You explained a simple case. :) My worry was about the case when we
could delete some number of items between [16, 20]. For example, we
delete 17, 18, and 19 at first. And now we delete item with #20. So,
leaf A should have 16 as a maximum CNID. And we can use 17 as a
next_id. Correct?

Let me double check it and I need to take another look to the patch.

Thanks,
Slava.

>
> Both times largest - 1 was in the other leaf, and it was counted
> because
> that leaf keeps its own maximum.
>
> next_id is then set to max + 1. Every CNID in use is <= max, so max +
> 1
> is free. Deleted CNIDs below max are never reused, so we never need
> to
> know which CNIDs are free. A red-black tree of deleted CNIDs would
> only
> be needed to reuse those holes.
>
> To check it, a debug build compared every cached max_cnid with the
> value computed from the records after each catalog insert and remove:
> about 88,000 full-tree checks on 2,000 files with random operations
> and
> 4 writers, plus a run under memory pressure that freed 55,630 nodes
> and
> read them again. There was no mismatch.
>
> > Why do we need this flag? If node is created, then it should have
> > valid
> > max_cnid.
>
> max_cnid is not on disk, so a node that hfs_bnode_find() has just
> read
> does not have it. For a leaf node it could be computed from that node
> alone, but for an index node it needs every node below it. Computing
> it
> at read time would read the whole catalog at mount, and again for an
> index node that hfs_release_folio() freed and that is read again
> later.
>
> The flag means "max_cnid of this node has been computed".
> hfs_btree_max_cnid() computes only the nodes without it, and only
> when
> the newest file or directory is deleted. The first such delete after
> mount still reads the whole catalog once; later ones only recompute
> the
> nodes on the path of the removed record. The flag is also cleared
> when
> the largest CNID of a node is removed, and on a split, because
> records
> move to the new node.
>
> Thanks,
> Hengyu