linux-kernel - Re: [PATCH 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: <20200515130439.GW2957@hirez.programming.kicks-ass.net>
Date:   Fri, 15 May 2020 15:04:39 +0200
From:   Peter Zijlstra <peterz@...radead.org>
To:     Lai Jiangshan <laijs@...ux.alibaba.com>
Cc:     linux-kernel@...r.kernel.org,
        "Paul E . McKenney" <paulmck@...nel.org>,
        Oleg Nesterov <oleg@...hat.com>,
        Michel Lespinasse <walken@...gle.com>,
        Andrea Arcangeli <aarcange@...hat.com>,
        David Woodhouse <David.Woodhouse@...el.com>,
        Rik van Riel <riel@...hat.com>,
        Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
Subject: Re: [PATCH 2/2] rbtree_latch: don't need to check seq when it found
 a node

On Fri, May 15, 2020 at 12:47:07PM +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.
> 
> Cc: Peter Zijlstra <peterz@...radead.org>
> Cc: Paul E. McKenney <paulmck@...nel.org>
> Cc: Oleg Nesterov <oleg@...hat.com>
> Cc: Michel Lespinasse <walken@...gle.com>
> Cc: Andrea Arcangeli <aarcange@...hat.com>
> Cc: David Woodhouse <David.Woodhouse@...el.com>
> Cc: Rik van Riel <riel@...hat.com>
> Cc: Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
> Signed-off-by: Lai Jiangshan <laijs@...ux.alibaba.com>
> ---
>  include/linux/rbtree_latch.h | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/include/linux/rbtree_latch.h b/include/linux/rbtree_latch.h
> index b012bd95eabf..09a3c05d1c5b 100644
> --- a/include/linux/rbtree_latch.h
> +++ b/include/linux/rbtree_latch.h
> @@ -208,7 +208,7 @@ latch_tree_find(void *key, struct latch_tree_root *root,
>  	do {
>  		seq = raw_read_seqcount_latch(&root->seq);
>  		node = __lt_find(key, root, seq & 1, ops->comp);
> -	} while (read_seqcount_retry(&root->seq, seq));
> +	} while (!node && read_seqcount_retry(&root->seq, seq));

So in the case where we search for key=N and race with { erase(N);
insert(N) }, we can now return the old N, as opposed to the new N.

But given that is entirely subject to timing anyway, that is irrelevant.
We change the boundary case in the timing.

Acked-by: Peter Zijlstra (Intel) <peterz@...radead.org>