From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S932400AbbDMQnV (ORCPT ); Mon, 13 Apr 2015 12:43:21 -0400 Received: from mail-wi0-f175.google.com ([209.85.212.175]:38513 "EHLO mail-wi0-f175.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S932119AbbDMQnU (ORCPT ); Mon, 13 Apr 2015 12:43:20 -0400 Date: Mon, 13 Apr 2015 18:43:15 +0200 From: Ingo Molnar To: Peter Zijlstra Cc: rusty@rustcorp.com.au, mathieu.desnoyers@efficios.com, oleg@redhat.com, paulmck@linux.vnet.ibm.com, torvalds@linux-foundation.org, linux-kernel@vger.kernel.org, andi@firstfloor.org, rostedt@goodmis.org, tglx@linutronix.de, laijs@cn.fujitsu.com, linux@horizon.com, Michel Lespinasse , Andrea Arcangeli , David Woodhouse , Rik van Riel Subject: Re: [PATCH v5 06/10] rbtree: Implement generic latch_tree Message-ID: <20150413164315.GE6040@gmail.com> References: <20150413141126.756350256@infradead.org> <20150413141213.552474463@infradead.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <20150413141213.552474463@infradead.org> User-Agent: Mutt/1.5.23 (2014-03-12) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org * Peter Zijlstra wrote: > Implement a latched RB-tree in order to get unconditional RCU/lockless > lookups. > > Cc: Oleg Nesterov > Cc: Michel Lespinasse > Cc: Andrea Arcangeli > Cc: David Woodhouse > Cc: Rik van Riel > Cc: Mathieu Desnoyers > Cc: "Paul E. McKenney" > Signed-off-by: Peter Zijlstra (Intel) > --- > include/linux/rbtree_latch.h | 212 +++++++++++++++++++++++++++++++++++++++++++ > 1 file changed, 212 insertions(+) > > --- /dev/null > +++ b/include/linux/rbtree_latch.h > @@ -0,0 +1,212 @@ > +/* > + * Latched RB-trees > + * > + * Copyright (C) 2015 Intel Corp., Peter Zijlstra > + * > + * Since RB-trees have non atomic modifications they're not immediately suited > + * for RCU/lockless queries. Even though we made RB tree lookups non-fatal for > + * lockless lookups; we cannot guarantee they return a correct result. > + * > + * The simplest solution is a seqlock + rb-tree, this will allow lockless > + * lookups; but has the constraint (inherent to the seqlock) that read sides > + * cannot nest in write sides. > + * > + * If we need to allow unconditional lookups (say as required for NMI context > + * usage) we need a more complex setup; this data structure provides this by > + * employing the latch technique -- see @raw_write_seqcount_latch -- to > + * implement a latched RB-tree which does allow for unconditional lookups by > + * virtue of always having (at least) one stable copy of the tree. > + * > + * However, while we have the guarantee that there is at all times one stable > + * copy, this does not guarantee an iteration will not observe modifications. > + * What might have been a stable copy at the start of the iteration, need not > + * remain so for the duration of the iteration. > + * > + * Therefore, this does require a lockless RB-tree iteration to be non-fatal; > + * see the comment in lib/rbtree.c. Note however that we only require the first > + * condition -- not seeing partial stores -- because the latch thing isolates > + * us from loops. If we were to interrupt a modification the lookup would be > + * pointed at the stable tree and complete while the modification was halted. Minor nit: so this text has 3 variants to spell RB-trees: RB-tree RB tree rb-tree I suggest we pick one! :-) Thanks, Ingo