linux-kernel - Re: 答复: [PATCH] rbtree: stop iteration early in rb_find

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [day] [month] [year] [list]

Message-ID: <20210825171850.GD17784@worktop.programming.kicks-ass.net>
Date:   Wed, 25 Aug 2021 19:18:50 +0200
From:   Peter Zijlstra <peterz@...radead.org>
To:     "Li,Rongqing" <lirongqing@...du.com>
Cc:     Michel Lespinasse <michel@...pinasse.org>,
        "dbueso@...e.de" <dbueso@...e.de>,
        "mingo@...nel.org" <mingo@...nel.org>,
        "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>
Subject: Re: 答复: [PATCH] rbtree: stop
 iteration early in rb_find_first

On Wed, Aug 25, 2021 at 04:01:53PM +0000, Li,Rongqing wrote:
> 
> >>
> >>
> >>                         10
> >>                       /
> >>                      5
> >>                       \
> >>                        10
> >>
> >> The search would stop after visiting node 5, and miss the leaf which
> >> is the expected node to be returned.
> 
> thanks for explanation.
> 
> >Just to clarify; the current code *does* work here. The proposed patch
> >breaks it.
> 
> 
> true, my patch is wrong.
> 
> but rb_find_first seems have other issue.  when the key is equal, we should search right leaf, not left leaf

That again breaks the above case.