Received-SPF: pass (google.com: domain of linux-kernel+bounces-112725-linux.lists.archive=gmail.com@vger.kernel.org designates 147.75.48.161 as permitted sender) client-ip=147.75.48.161;
Date: Sun, 24 Mar 2024 11:22:41 -0400
From: Alan Stern <stern@rowland.harvard.edu>
To: comex <comexk@gmail.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>,
  Kent Overstreet <kent.overstreet@linux.dev>,
  Boqun Feng <boqun.feng@gmail.com>,
  rust-for-linux <rust-for-linux@vger.kernel.org>,
  linux-kernel@vger.kernel.org, linux-arch@vger.kernel.org,
  llvm@lists.linux.dev, Miguel Ojeda <ojeda@kernel.org>,
  Alex Gaynor <alex.gaynor@gmail.com>,
  Wedson Almeida Filho <wedsonaf@gmail.com>, Gary Guo <gary@garyguo.net>,
  =?iso-8859-1?Q?Bj=F6rn?= Roy Baron <bjorn3_gh@protonmail.com>,
  Benno Lossin <benno.lossin@proton.me>,
  Andreas Hindborg <a.hindborg@samsung.com>,
  Alice Ryhl <aliceryhl@google.com>, Andrea Parri <parri.andrea@gmail.com>,
  Will Deacon <will@kernel.org>, Peter Zijlstra <peterz@infradead.org>,
  Nicholas Piggin <npiggin@gmail.com>, David Howells <dhowells@redhat.com>,
  Jade Alglave <j.alglave@ucl.ac.uk>, Luc Maranget <luc.maranget@inria.fr>,
  "Paul E. McKenney" <paulmck@kernel.org>, Akira Yokosawa <akiyks@gmail.com>,
  Daniel Lustig <dlustig@nvidia.com>, Joel Fernandes <joel@joelfernandes.org>,
  Nathan Chancellor <nathan@kernel.org>,
  Nick Desaulniers <ndesaulniers@google.com>, kent.overstreet@gmail.com,
  Greg Kroah-Hartman <gregkh@linuxfoundation.org>, elver@google.com,
  Mark Rutland <mark.rutland@arm.com>, Thomas Gleixner <tglx@linutronix.de>,
  Ingo Molnar <mingo@redhat.com>, Borislav Petkov <bp@alien8.de>,
  Dave Hansen <dave.hansen@linux.intel.com>, x86@kernel.org,
  "H. Peter Anvin" <hpa@zytor.com>, Catalin Marinas <catalin.marinas@arm.com>,
  linux-arm-kernel@lists.infradead.org, linux-fsdevel@vger.kernel.org
Subject: Re: [WIP 0/3] Memory model and atomic API in Rust
Message-ID: <174272a1-e21f-4d85-94ab-f0457bd1c93b@rowland.harvard.edu>
References: <20240322233838.868874-1-boqun.feng@gmail.com>
 <s2jeqq22n5ef5jknaps37mfdjvuqrns4w7i22qp2r7r4bzjqs2@my3eyxoa3pl3>
 <CAHk-=whY5A=S=bLwCFL=043DoR0TTgSDUmfPDx2rXhkk3KANPQ@mail.gmail.com>
 <C85BE4F4-5847-45B4-A973-76B184B35EDE@gmail.com>
Precedence: bulk
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <C85BE4F4-5847-45B4-A973-76B184B35EDE@gmail.com>

On Sat, Mar 23, 2024 at 05:40:23PM -0400, comex wrote:
> That may be true, but the LLVM issue you cited isn’t a good example.  
> In that issue, the function being miscompiled doesn’t actually use any 
> barriers or atomics itself; only the scaffolding around it does.  The 
> same issue would happen even if the scaffolding used LKMM atomics.
> 
> For anyone curious: The problematic optimization involves an 
> allocation (‘p’) that is initially private to the function, but is 
> returned at the end of the function.  LLVM moves a non-atomic store to 
> that allocation across an external function call (to ‘foo’).  This 
> reordering would be blatantly invalid if any other code could observe 
> the contents of the allocation, but is valid if the allocation is 
> private to the function.  LLVM assumes the latter: after all, the 
> pointer to it hasn’t escaped.  Yet.  Except that in a weak memory 
> model, the escape can ‘time travel’...

It's hard to understand exactly what you mean, but consider the 
following example:

int *globalptr;
int x;

int *f() {
	int *p = kzalloc(sizeof(int));

	L1: *p = 1;
	L2: foo();
	return p;
}

void foo() {
	smp_store_release(&x, 2);
}

void thread0() {
	WRITE_ONCE(globalptr, f());
}

void thread1() {
	int m, n;
	int *q;

	m = smp_load_acquire(&x);
	q = READ_ONCE(globalptr);
	if (m && q)
		n = *q;
}

(If you like, pretend each of these function definitions lives in a 
different source file -- it doesn't matter.)

With no optimization, whenever thread1() reads *q it will always obtain 
1, thanks to the store-release in foo() and the load-acquire() in 
thread1().  But if the compiler swaps L1 and L2 in f() then this is not 
guaranteed.  On a weakly ordered architecture, thread1() could then get 
0 from *q.

I don't know if this is what you meant by "in a weak memory model, the 
escape can ‘time travel'".  Regardless, it seems very clear that any 
compiler which swaps L1 and L2 in f() has a genuine bug.

Alan Stern