linux-kernel - Re: [PATCH V2 2/2] rbtree_latch: don't need to check seq when it found a node

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>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <CANN689Hw7Z4ScsdXcnhAZTqePb8bx6UP-XAtQRcVKv79aKjXtw@mail.gmail.com>
Date:   Fri, 15 May 2020 22:03:02 -0700
From:   Michel Lespinasse <walken@...gle.com>
To:     Lai Jiangshan <jiangshanlai+lkml@...il.com>
Cc:     Lai Jiangshan <laijs@...ux.alibaba.com>,
        LKML <linux-kernel@...r.kernel.org>,
        "Paul E . McKenney" <paulmck@...nel.org>,
        Oleg Nesterov <oleg@...hat.com>,
        Andrea Arcangeli <aarcange@...hat.com>,
        Rik van Riel <riel@...hat.com>,
        Mathieu Desnoyers <mathieu.desnoyers@...icios.com>,
        Peter Zijlstra <peterz@...radead.org>
Subject: Re: [PATCH V2 2/2] rbtree_latch: don't need to check seq when it
 found a node

On Fri, May 15, 2020 at 9:52 PM Lai Jiangshan
<jiangshanlai+lkml@...il.com> wrote:
>
> On Sat, May 16, 2020 at 12:28 PM Michel Lespinasse <walken@...gle.com> wrote:
> >
> > On Fri, May 15, 2020 at 03:59:09PM +0000, Lai Jiangshan wrote:
> > > latch_tree_find() should be protected by caller via RCU or so.
> > > When it find a node in an attempt, the node must be a valid one
> > > in RCU's point's of view even the tree is (being) updated with a
> > > new node with the same key which is entirely subject to timing
> > > anyway.
> >
> > I'm not sure I buy this. Even if we get a valid node, is it the one we
> > were searching for ? I don't see how this could be guaranteed if the
> > read raced with a tree rebalancing.
>
> It is valid because ops->comp() returns 0 and it should be
> the one we were searching for unless ops->comp() is wrong.
> The searched one could be possible just deleted, but it is still
> a legitimate searched result in RCU's point's of view.
>
> A tree rebalancing can cause a searching fails to find
> an existing target. This is the job of read_seqcount_retry()
> to tell you to retry.

Ah, yes, this is correct. It wouldn't work if we wanted to return the
next higher key for example, but it does work for exact matches. Nice!

-- 
Michel "Walken" Lespinasse
A program is never fully debugged until the last user dies.