Received: by 2002:a05:6a10:5bc5:0:0:0:0 with SMTP id os5csp4578072pxb; Tue, 2 Nov 2021 12:03:22 -0700 (PDT) X-Google-Smtp-Source: ABdhPJwNAvMezGFZNrfEWPkapt0joi3YlAdlCJQCdN50lQ1X98mdUXqh8NH++GGa4xsPAG1Z1yK1 X-Received: by 2002:a92:360c:: with SMTP id d12mr22411854ila.172.1635879801767; Tue, 02 Nov 2021 12:03:21 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1635879801; cv=none; d=google.com; s=arc-20160816; b=w/eMygR1kyXnUFf/mqhmXjiUxqOXvKjSitNXMRhwuORtnZ6HwpSsFVdovlNZpKXwtW HBmsxKn56EhrQksqJo23zLiYT6kfKr+rPtcE0ibm0Q9IxVh4tkXDAk27//zoMOIi3DQV SquUu/YH0y++/tdebU+0HJYcODEUw5GB72XccuLmVGXbgKSzHWI+WJ1IGPtSEK52dWtM JZ5nh6iTlPp9WaoWZOHAb46sfjq2jaaIYQcxrl+3NkXEwiTlhqTR/vrGjuLCyDqSBcRa M0HshJ7z5eigD3J7ci5jIanG7ID3LISoP7nzhJFbxDH1/HYoXD2MlQWnkk5EcH1zKWZ6 FBDQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:user-agent:in-reply-to:content-transfer-encoding :content-disposition:mime-version:references:message-id:subject:cc :to:from:date; bh=2lh5dsZjjfbud4LRAH7j2tB+frCJCgFG7QE26igvYuo=; b=r+OIN9sgC3/As5RaF537Tx457qcrsFa1T9IB16+kyzi87xjJhOWDiDdqfMY4ownb/v xhgSsP85pUIDNvgs1BVqfHxtdAv9O1MSWBwHGqmbu8rUBS1FXxIoUfxcq+rfA4AAXWYI fjsi2m5CyZ46UdnBQIqiq6htjy/KkDy/D5urlvsKy0T53h3gbvAzSfYYsLPz0RAkV+09 aGY3NQdIW4AsxZex33kbbvaVAN+zUzx6aSUd4NtOidotnetVq7nK+r2EpC9Pft3fONOy IBFgSyTHfP/EOxfzAvVP31uO8jefIDPfAlxI8b7mnOQ574ydJNsSBZn+0l05KrdayWyl fEcA== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Return-Path: Received: from vger.kernel.org (vger.kernel.org. [23.128.96.18]) by mx.google.com with ESMTP id z10si29034249ilu.34.2021.11.02.12.03.05; Tue, 02 Nov 2021 12:03:21 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18; Authentication-Results: mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230331AbhKBTEO (ORCPT + 99 others); Tue, 2 Nov 2021 15:04:14 -0400 Received: from netrider.rowland.org ([192.131.102.5]:58477 "HELO netrider.rowland.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with SMTP id S229530AbhKBTEO (ORCPT ); Tue, 2 Nov 2021 15:04:14 -0400 Received: (qmail 1498121 invoked by uid 1000); 2 Nov 2021 15:01:38 -0400 Date: Tue, 2 Nov 2021 15:01:38 -0400 From: Alan Stern To: Paul =?iso-8859-1?Q?Heidekr=FCger?= Cc: paulmck@kernel.org, will@kernel.org, peterz@infradead.org, boqun.feng@gmail.com, parri.andrea@gmail.com, linux-kernel@vger.kernel.org, llvm@lists.linux.dev, elver@google.com, charalampos.mainas@gmail.com, pramod.bhatotia@in.tum.de Subject: Re: Potentially Broken Address Dependency via test_bit() When Compiling With Clang Message-ID: <20211102190138.GA1497378@rowland.harvard.edu> References: <20211027142720.GB1319606@rowland.harvard.edu> <20211028143446.GA1351384@rowland.harvard.edu> MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: User-Agent: Mutt/1.10.1 (2018-07-13) Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Tue, Nov 02, 2021 at 07:35:57PM +0100, Paul Heidekr?ger wrote: > On Thu, Oct 28, 2021 at 10:34:46AM -0400, Alan Stern wrote: > > On Thu, Oct 28, 2021 at 02:37:47PM +0200, Paul Heidekr?ger wrote: > > > On Wed, Oct 27, 2021 at 10:27:20AM -0400, Alan Stern wrote: > > > > On Wed, Oct 27, 2021 at 12:19:48PM +0200, Paul Heidekr?ger wrote: > > > > > > > Address dependency in source code, lines 373 - 375 in fs/afs/addr_list.c: > > > > > > > > > > > [...] > > > > > > index = READ_ONCE(ac->alist->preferred); > > > > > > if (test_bit(index, &set)) > > > > > > goto selected; > > > > > > [...] > > > > > > > > > > where test_bit() expands to the following in > > > > > include/asm-generic/bitops/non-atomic.h, lines 115 - 122: > > > > > > > > > > > static __always_inline int > > > > > > arch_test_bit(unsigned int nr, const volatile unsigned long *addr) > > > > > > { > > > > > > return 1UL & (addr[BIT_WORD(nr)] >> (nr & (BITS_PER_LONG-1))); > > > > > > } > > > > > > #define test_bit arch_test_bit > > > > > > However, I can't follow the IR code. Can you please explain in ordinary > > > > English how the LLVM compiler manages to lose track of this dependency? > > > > > > > > Alan Stern > > > > > > Here's what we think might be going on: > > > - In 'arch_test_bit()', 'addr[BIT_WORD(nr)]' expands to 'addr[(nr) / 64]'. > > > - Since 'addr' points to an 'unsigned long', any other result than '0' for > > > '(nr) / 64' would be out of bounds and therefore undefined. > > > - We assume LLVM is able to figure this out and use it to get rid of the > > > address computation all together. > > > > Ah, that explains it. Yes, when set is a single unsigned long (or an > > array of length 1), the address dependency is only syntactic, not > > semantic. As a result, we should expect that compilers will sometimes > > not preserve it. > > In LKMM's explanation.txt, lines 450 - 453 state: > > > A read event and another memory access event are linked by an address > > dependency if the value obtained by the read affects the location > > accessed by the other event. > > If we understand correctly, the ambiguity you're pointing out is that by > looking at 'addr[BIT_WORD(nr)]', one could deduce an address dependency by > seeing an array subscript operator, using a value which can be traced back to a > 'READ_ONCE()' (syntactic). Exactly. The syntax of the expression apparently indicates that the address to be dereferenced depends on the value of nr. > However, since 'addr' points to an 'unsigned long', the 'READ_ONCE()' never > affects the location accessed in 'arch_test_bit()' as the offset computed in > the subscript operator can only be, as clang identified, '0' (semantic). Again correct. Although the address to be dereferenced may seem to depend on nr, in fact it doesn't because in any valid execution nr must not contain any value other than 0 (and the compiler knows this). > > The danger, of course, is that people relying on an ordering prescribed > > by the LKMM may get fooled because (unbeknownst to them) the dependency > > in question is not semantic. > > Do you think this would warrant a change to LKMM's explanation.txt to make this > more explicit? It wouldn't hurt. Note that explanation.txt does already include a section talking about address dependencies from marked loads to plain reads (line 2260 et seq). It also talks about the possibility of the compiler undermining the memory model in this regard (line 2308). However, it doesn't mention the difference between syntactic and semantic dependencies. If you would like to submit a patch adding an explicit description of this, please feel free to do so. > > It would be great if a static checker > > could detect such things -- but this would require some way for us to > > inform the checker about when the code does rely on a dependency > > ordering. > > The compiler passes we're working on will hopefully be able to do exactly that, > not taking into account the programmer's intent of course. Good luck! Alan