Re: linux-6.16/fs/jffs2/readinode.c:189: loop can never finish

[David Woodhouse <dwmw2@infradead.org>]

[-- Attachment #1: Type: text/plain, Size: 2967 bytes --]

On Mon, 2025-08-04 at 09:30 +0200, David Oberhollenzer wrote:
> Hi,
> 
> On 8/4/25 9:10 AM, Zhihao Cheng wrote:
> > 
> > The 'next != NULL' is also a condition for the loop, this snippet
> > of code finds a leaf node in 'tn_root'.
> 
> Yes, this is a classic tree traversal. Assuming the tree isn't
> broken, the loop eventually terminates when it runs of a leaf.
> 
> The real issue with this code is that this is the *only* exit
> condition of the loop. The traversal loop always branches until
> it hits a leaf and the function then returns NULL. I'm pretty
> sure this might not be the intended behavior.

It's going back almost two decades now but...

This function is used only during the file system scan, when we scan
the whole medium and initially fill a big bucket of data nodes to be
subsequently processed and (mostly) eliminated due to overlap. It's
allows for early elimination of completely overlapped nodes, to reduce
memory usage. See https://git.kernel.org/torvalds/c/df8e96f39103a for
more details.

The jffs2_add_tn_to_tree() function calls jffs2_lookup_tn() to get a
*starting* point, and then it backs up with rb_prev() until it finds
the *first* node which is part of the overlapping set.

Then, jffs2_add_tn_to_tree() iterates forward from that node until it
has passed the end point of the node being added, looking for nodes
which have been completely obsoleted and can be discarded early.

If jffs2_lookup_tn() *did* always return NULL, that wouldn't actually
cause a correctness problem, as all this is only an optimisation
anyway. But I don't believe it does — it iterates until 'next' is NULL,
but then returns the 'tn' whose left or right child was that 'next'.

I think there might be a missed optimisation here though. Instead of
using only the *starting* offset of the newly-added node, I think the
jffs2_lookup_fn() function should also use the *end* offset of the
newly-added node. And should only follow the tree down tn->rb.rb_right
if the current tn->fn->ofs is lower than *that*.

Otherwise I think we miss out on immediately discarding a newly-
discovered node which is already completely obsoleted by a node that
starts *earlier* than it.

There's absolutely no good reason why this tmp_dnode code couldn't have
fairly comprehensive unit and torture tests, and I think I'd want to
have those before trying to do something like this to improve the
optimisation...

--- a/fs/jffs2/readinode.c
+++ b/fs/jffs2/readinode.c
@@ -184,7 +184,7 @@ static struct jffs2_tmp_dnode_info
*jffs2_lookup_tn(struct rb_root *tn_root, uin
        while (next) {
                tn = rb_entry(next, struct jffs2_tmp_dnode_info, rb);
 
-               if (tn->fn->ofs < offset)
+               if (tn->fn->ofs + tn->fn->size < offset)
                        next = tn->rb.rb_right;
                else if (tn->fn->ofs >= offset)
                        next = tn->rb.rb_left;


[-- Attachment #2: smime.p7s --]
[-- Type: application/pkcs7-signature, Size: 5069 bytes --]