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

[Hengyu Liang]

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

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