On Mon, Aug 01, 2022 at 12:20:35PM -0700, Paul E. McKenney wrote:
> On Mon, Aug 01, 2022 at 04:41:09PM +0100, Will Deacon wrote:
> > Apologies for the slow response here; believe it or not, I was attending
> > a workshop about memory ordering.
>
> Nice!!! Anything that I can/should know from that gathering? ;-)
Oh come off it, you know this stuff already ;)
> > On Sun, Jul 31, 2022 at 10:30:11AM -0700, Paul E. McKenney wrote:
> > > On Sun, Jul 31, 2022 at 09:51:47AM -0700, Linus Torvalds wrote:
> > > > Even alpha is specified to be locally ordered wrt *one* memory
> > > > location, including for reads (See table 5-1: "Processor issue order",
> > > > and also 5.6.2.2: "Litmus test 2"). So if a previous read has seen a
> > > > new value, a subsequent read is not allowed to see an older one - even
> > > > without a memory barrier.
> > > >
> > > > Will, Paul? Maybe that's only for overlapping loads/stores, not for
> > > > loads/loads. Because maybe alpha for once isn't the weakest possible
> > > > ordering.
> > >
> > > The "bad boy" in this case is Itanium, which can do some VLIW reordering
> > > of accesses. Or could, I am not sure that newer Itanium hardware
> > > does this. But this is why Itanium compilers made volatile loads use
> > > the ld,acq instruction.
> > >
> > > Which means that aligned same-sized marked accesses to a single location
> > > really do execute consistently with some global ordering, even on Itanium.
> >
> > Although this is true, there's a really subtle issue which crops up if you
> > try to compose this read-after-read ordering with dependencies in the case
> > where the two reads read the same value (which is encapsulated by the
> > unusual RSW litmus test that I've tried to convert to C below):
>
> RSW from the infamous test6.pdf, correct?
That's the badger. I've no doubt that you're aware of it already, but I
thought it was a useful exercise to transcribe it to C and have it on the
mailing list for folks to look at.
> > /* Global definitions; assume everything zero-initialised */
> > struct foo {
> > int *x;
> > };
> >
> > int x;
> > struct foo foo;
> > struct foo *ptr;
> >
> >
> > /* CPU 0 */
> > WRITE_ONCE(x, 1);
>
> Your x is RSW's z?
Yes.
> > WRITE_ONCE(foo.x, &x);
>
> And your foo.x is RSW's x? If so, the above WRITE_ONCE() could happen at
> compile time, correct? Or in the initialization clause of a litmus test?
Yes, although I think it's a tiny bit more like real code to have it done
here, although it means that the "surprising" outcome relies on this being
reordered before the store to x.
> > /*
> > * Release ordering to ensure that somebody following a non-NULL ptr will
> > * see a fully-initialised 'foo'. smp_[w]mb() would work as well.
> > */
> > smp_store_release(&ptr, &foo);
>
> Your ptr is RSW's y, correct?
Yes.
> > /* CPU 1 */
> > int *xp1, *xp2, val;
> > struct foo *foop;
> >
> > /* Load the global pointer and check that it's not NULL. */
> > foop = READ_ONCE(ptr);
> > if (!foop)
> > return;
>
> A litmus tests can do this via the filter clause.
Indeed, but I was trying to make this look like C code for non-litmus
speakers!
> > /*
> > * Load 'foo.x' via the pointer we just loaded. This is ordered after the
> > * previous READ_ONCE() because of the address dependency.
> > */
> > xp1 = READ_ONCE(foop->x);
> >
> > /*
> > * Load 'foo.x' directly via the global 'foo'.
> > * _This is loading the same address as the previous READ_ONCE() and
> > * therefore cannot return a stale (NULL) value!_
> > */
> > xp2 = READ_ONCE(foo.x);
>
> OK, same location, but RSW calls only for po, not addr from the initial
> read to this read, got it. (My first attempt left out this nuance,
> in case you were wondering.)
Right, there is only po from the initial read to this read. If there was an
address dependency, then we'd have a chain of address dependencies from the
first read to the last read on this CPU and the result (of x == 0) would be
forbidden.
> > /*
> > * Load 'x' via the pointer we just loaded.
> > * _We may see zero here!_
> > */
> > val = READ_ONCE(*xp2);
>
> And herd7/LKMM agree with this, at least assuming I got the litmus
> test right. (I used RSW's variables as a cross-check.)
That's promising, but see below...
> C rsw
>
> {
> a=0;
> x=z;
> y=a;
> z=0;
> }
>
> P0(int *x, int **y, int *z)
> {
> WRITE_ONCE(*z, 1);
> WRITE_ONCE(*y, x);
> }
Ah wait, you need a barrier between these two writes, don't you? I used
an smp_store_release() but smp[w]_mb() should do too.
Will
