Will two READ_ONCE()s in a row execute in order

Will two READ_ONCE()s in a row execute in order

[Zhang Zeren]

[-- Attachment #1.1: Type: text/plain, Size: 1772 bytes --]

Hi, I read an example in the Documentation/memory-barriers.txt, which says
>
>  (*) On any given CPU, dependent memory accesses will be issued in order, with
>      respect to itself.  This means that for:
>
> 	Q = READ_ONCE(P); D = READ_ONCE(*Q);
>
>      the CPU will issue the following memory operations:
>
> 	Q = LOAD P, D = LOAD *Q
>
>      and always in that order.  However, on DEC Alpha, READ_ONCE() also
>      emits a memory-barrier instruction, so that a DEC Alpha CPU will
>      instead issue the following memory operations:
>
> 	Q = LOAD P, MEMORY_BARRIER, D = LOAD *Q, MEMORY_BARRIER
>
> As far as  I understand it, linux kernel memory model (LKMM) guarantee two
read operations execute in order. And if the CPU architecture offer an
looser memory ordering (like Alpha), then the compiler must help to add a
memory barrier after the load instruction to fufill the LKMM's standard.

However i did a test using klitmus like this

> P0(int *x, int *y)
> {
>         WRITE_ONCE(*x, 1);
>         smp_wmb();
>         WRITE_ONCE(*y, 1);
> }
>
> P1(int *x, int *y)
> {
>         int r0;
>         int r1;
>
>         r0 = READ_ONCE(*y);
>         r1 = READ_ONCE(*x);
> }
>
> exists (1:r0=1 /\ 1:r1=0)
>

I run this test in an aarch64 machine, and get the result

> Histogram (4 states)
> 1292209 :>1:r0=0; 1:r1=0;
> 1585    *>1:r0=1; 1:r1=0;
> 221437  :>1:r0=0; 1:r1=1;
> 484769  :>1:r0=1; 1:r1=1;
> Ok
>
> Witnesses
> Positive: 1585, Negative: 1998415
>

It seems that these two READ_ONCE()s can be executed in any order. But if I
run this test in a x86 machine, which has a more strict memory model,
result 1:r0=1; 1:r1=0; disappears. So the order depends on the memory model
provided by the CPU architecture? Isn't this contradicted with
memory-barrier.txt?

[-- Attachment #1.2: Type: text/html, Size: 2402 bytes --]

[-- Attachment #2: Type: text/plain, Size: 170 bytes --]

_______________________________________________
Kernelnewbies mailing list
Kernelnewbies@kernelnewbies.org
https://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies

Re: Will two READ_ONCE()s in a row execute in order

[Valentin Vidić]

On Mon, Oct 25, 2021 at 04:32:41PM +0800, Zhang Zeren wrote:
> It seems that these two READ_ONCE()s can be executed in any order. But if I
> run this test in a x86 machine, which has a more strict memory model,
> result 1:r0=1; 1:r1=0; disappears. So the order depends on the memory model
> provided by the CPU architecture? Isn't this contradicted with
> memory-barrier.txt?

The documentation example has two memory acceses where the second uses
the value from the first one, so they are order dependent:

Q = READ_ONCE(P);
D = READ_ONCE(*Q);

In your example there seems to be no dependency between x and y so they
could be reordered?

-- 
Valentin

_______________________________________________
Kernelnewbies mailing list
Kernelnewbies@kernelnewbies.org
https://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies

Re: Will two READ_ONCE()s in a row execute in order

[FMDF]

On Mon, Oct 25, 2021 at 10:33 AM Zhang Zeren <zhangzr23@gmail.com> wrote:
>
> Hi, I read an example in the Documentation/memory-barriers.txt, which says
>>
>>  (*) On any given CPU, dependent memory accesses will be issued in order, with
>>      respect to itself.  This means that for:

"dependent" _is_ the key to understanding this topic. As Valentin
Vidić wrote, your loads are _not_ dependent and / or related in any
way.

> As far as  I understand it, linux kernel memory model (LKMM) guarantee two read operations
> execute in order. And if the CPU architecture offer an looser memory ordering (like Alpha), then
> the compiler must help to add a memory barrier after the load instruction to fufill the LKMM's
> standard.

No, adding a memory barrier is not a compiler job, instead it is up to
the kernel code.
For instance, please take a look at the implementation of
__READ_ONCE() for Alpha in arch/alpha/include/asm/rwonce.h (note that
__READ_ONCE() is used by READ_ONCE()).

Regards,

Fabio M. De Francesco

_______________________________________________
Kernelnewbies mailing list
Kernelnewbies@kernelnewbies.org
https://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies

Re: Will two READ_ONCE()s in a row execute in order

[Zhang Zeren]

[-- Attachment #1.1: Type: text/plain, Size: 1573 bytes --]

Thanks for your reply! I should have read more carefully... Besides, do you
know where can I find the specific rules of LKMM? Now it seems that two
irrelevant READ_ONCE()s can execute out of order, what about two
WRITE_ONCE()? or a READ_ONCE() followed by a WRITE_ONCE()? etc... Intel
gave several examples in it's manual (Volume 3, 8.2.3). Does LKMM provide
similar examples?

FMDF <fmdefrancesco@gmail.com> 于2021年10月25日周一 下午7:33写道：

> On Mon, Oct 25, 2021 at 10:33 AM Zhang Zeren <zhangzr23@gmail.com> wrote:
> >
> > Hi, I read an example in the Documentation/memory-barriers.txt, which
> says
> >>
> >>  (*) On any given CPU, dependent memory accesses will be issued in
> order, with
> >>      respect to itself.  This means that for:
>
> "dependent" _is_ the key to understanding this topic. As Valentin
> Vidić wrote, your loads are _not_ dependent and / or related in any
> way.
>
> > As far as  I understand it, linux kernel memory model (LKMM) guarantee
> two read operations
> > execute in order. And if the CPU architecture offer an looser memory
> ordering (like Alpha), then
> > the compiler must help to add a memory barrier after the load
> instruction to fufill the LKMM's
> > standard.
>
> No, adding a memory barrier is not a compiler job, instead it is up to
> the kernel code.
> For instance, please take a look at the implementation of
> __READ_ONCE() for Alpha in arch/alpha/include/asm/rwonce.h (note that
> __READ_ONCE() is used by READ_ONCE()).
>
> Regards,
>
> Fabio M. De Francesco
>

[-- Attachment #1.2: Type: text/html, Size: 2008 bytes --]

[-- Attachment #2: Type: text/plain, Size: 170 bytes --]

_______________________________________________
Kernelnewbies mailing list
Kernelnewbies@kernelnewbies.org
https://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies

Re: Will two READ_ONCE()s in a row execute in order

[FMDF]

[-- Attachment #1.1: Type: text/plain, Size: 760 bytes --]

On Mon, 25 Oct 2021, 14:17 Zhang Zeren, <zhangzr23@gmail.com> wrote:

> Thanks for your reply! I should have read more carefully... Besides, do
> you know where can I find the specific rules of LKMM?
>

Once people used to say that this subject is good for "scaring little kids"
(or something like that)...

Introductory material can be found in the Linux kernel under the
tools/memory-model/Documentation directory. For now, you'd better skip the
files that are one level higher in tools/memory-model.

IMO, best sources related to concurrency, ordering and memory model that
I've ever read are Paul McKenney's papers and book (please use the Google
search engine, Paul provides freely downloadable resources at his website).

Regards,

Fabio M. De Francesco

[-- Attachment #1.2: Type: text/html, Size: 1400 bytes --]

[-- Attachment #2: Type: text/plain, Size: 170 bytes --]

_______________________________________________
Kernelnewbies mailing list
Kernelnewbies@kernelnewbies.org
https://lists.kernelnewbies.org/mailman/listinfo/kernelnewbies