mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
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

      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®