From: Viacheslav Dubeyko <slava@dubeyko.com>
To: Hengyu Liang <hengyul@cs.unc.edu>
Cc: glaubitz@physik.fu-berlin.de, frank.li@vivo.com,
linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org,
stable@vger.kernel.org
Subject: Re: [PATCH v2] hfs: avoid reusing occupied CNIDs after deletion
Date: Mon, 16 Nov 2026 15:21:10 -0800 [thread overview]
Message-ID: <f59ea6b2a8c60594361ab596d92bdf98a217dd83.camel@dubeyko.com> (raw)
In-Reply-To: <20261113194103.3825961-1-hengyul@cs.unc.edu>
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
prev parent reply other threads:[~2026-11-16 23:21 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-11-12 11:01 Hengyu Liang
2026-11-12 22:34 ` Viacheslav Dubeyko
2026-11-13 19:14 ` Viacheslav Dubeyko
2026-11-13 19:41 ` Hengyu Liang
2026-11-16 23:21 ` Viacheslav Dubeyko [this message]
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=f59ea6b2a8c60594361ab596d92bdf98a217dd83.camel@dubeyko.com \
--to=slava@dubeyko.com \
--cc=frank.li@vivo.com \
--cc=glaubitz@physik.fu-berlin.de \
--cc=hengyul@cs.unc.edu \
--cc=linux-fsdevel@vger.kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=stable@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®