Skip to contentSkip to conversation

different kind of memory reordering clarification

DISCUSSION Yubin Ruan 2 participants 7 messages Apr 11, 2018 3 messages not in the archive

lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): 20180410121408.4fik54wftqvesk65@HP

A message that is not in the archive (sent off-list or not yet received): 20180410152024.rq6aynzvbgeyogma@HP

A message that is not in the archive (sent off-list or not yet received): [email protected]

Yubin Ruan

author
#3 lore raw
Quoted 2 lines · Paul E. McKenney
Quoted 1 line · Yubin Ruan

On Tue, Apr 10, 2018 at 08:14:08PM +0800, Yubin Ruan wrote:

[...]

Quoted 19 lines
Quoted 13 lines
Quoted 5 lines

Can you please provide me with some examples or references for different kinds of memory reordering in a SMP system? You know, there are different kinds of reordering:

Quoted 7 lines

- Loads reordered after loads
- Loads reordered after stores
- Stores reordered after stores
- Stores reordered after loads
- Atomic reordered with loads
- Atomic reordered with stores
- Dependent loads reordered (DEC alpha)

Quoted 3 lines

I remember there is open-std.org webpage containing comparision of C++'s memory model to those primitives used in the Linux kernel. But I just can't find that page.

Here you go!

Quoted 7 lines

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0124r4.html

There will be an update in a month or so, but the above is pretty close. Also, the Linux-kernel memory model was presented at ASPLOS and accepted into the Linux kernel itself:

https://paulmck.livejournal.com/49667.html

Many thanks. But I am currently confused about the relationship between terminologies used in the Linux kernel and those used in some programming languages (e.g., C++), i.e., the relationships between

    memory_order_release
    memory_order_relaxed
    memory_order_acquire
    memory_order_seq_cst
    ...

and those used in the kernel:

    READ_ONCE() / WRITE_ONCE()
    rmb() / wmb() / mb() / smp_mb()
    ...

Any materials for that?

Yubin

author
#4 lore raw
Quoted 41 lines · Yubin Ruan
Quoted 2 lines · Paul E. McKenney
Quoted 1 line · Yubin Ruan

On Tue, Apr 10, 2018 at 08:14:08PM +0800, Yubin Ruan wrote:

[...]

Quoted 19 lines
Quoted 13 lines
Quoted 5 lines

Can you please provide me with some examples or references for different kinds of memory reordering in a SMP system? You know, there are different kinds of reordering:

Quoted 7 lines

- Loads reordered after loads
- Loads reordered after stores
- Stores reordered after stores
- Stores reordered after loads
- Atomic reordered with loads
- Atomic reordered with stores
- Dependent loads reordered (DEC alpha)

Quoted 3 lines

I remember there is open-std.org webpage containing comparision of C++'s memory model to those primitives used in the Linux kernel. But I just can't find that page.

Here you go!

Quoted 7 lines

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0124r4.html

There will be an update in a month or so, but the above is pretty close. Also, the Linux-kernel memory model was presented at ASPLOS and accepted into the Linux kernel itself:

https://paulmck.livejournal.com/49667.html

Many thanks. But I am currently confused about the relationship between terminologies used in the Linux kernel and those used in some programming languages (e.g., C++), i.e., the relationships between

    memory_order_release
    memory_order_relaxed
    memory_order_acquire
    memory_order_seq_cst
    ...
Quoted 7 lines

and those used in the kernel:

    READ_ONCE() / WRITE_ONCE()
    rmb() / wmb() / mb() / smp_mb()
    ...

Any materials for that?

Hmm, to be more exact, what I want is something like this:

“These primitives can be expressed directly in terms of the upcoming C++0x standard. For the smp_mb() primitive this correspondence is not exact; our memory barriers are somewhat stronger than the standard’s atomic_thread_fence(memory_order_seq_cst). The LOAD_SHARED() primitive maps to x.load(memory_order_relaxed) and STORE_SHARED() to x.store(memory_order_relaxed). The barrier() primitive maps to atomic_signal_fence(memory_order_seq_cst). In addition, rcu_dereference() maps to x.load(memory_order_consume) and rcu_assign_pointer() maps to x.store(v, memory_order_release).”

This is extracted from the paper "User-Level Implementations of Read-Copy Update" by M. Desnoyers and P. McKenney, A. S. Stern, M. R. Dagenais and J. Walpole[1]. And the LOAD_SHARED() and STORE_SHARED() above are READ_ONCE() and WRITE_ONCE(), respectively. (BTW, LOAD_SHARED/STORE_SHARED seem to be better names than READ_ONCE/WRITE_ONCE, which are a bit confusing. How come people adopted those name?)

(I find this after digging into a whole bunch of emails...hmm..email is a good thing)

[1]: https://www.efficios.com/pub/rcu/urcu-main-accepted.pdf

Yubin

#5 lore raw
Quoted 52 lines · Yubin Ruan
Quoted 41 lines · Yubin Ruan
Quoted 2 lines · Paul E. McKenney
Quoted 1 line · Yubin Ruan

On Tue, Apr 10, 2018 at 08:14:08PM +0800, Yubin Ruan wrote:

[...]

Quoted 19 lines
Quoted 13 lines
Quoted 5 lines

Can you please provide me with some examples or references for different kinds of memory reordering in a SMP system? You know, there are different kinds of reordering:

Quoted 7 lines

- Loads reordered after loads
- Loads reordered after stores
- Stores reordered after stores
- Stores reordered after loads
- Atomic reordered with loads
- Atomic reordered with stores
- Dependent loads reordered (DEC alpha)

Quoted 3 lines

I remember there is open-std.org webpage containing comparision of C++'s memory model to those primitives used in the Linux kernel. But I just can't find that page.

Here you go!

Quoted 7 lines

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0124r4.html

There will be an update in a month or so, but the above is pretty close. Also, the Linux-kernel memory model was presented at ASPLOS and accepted into the Linux kernel itself:

https://paulmck.livejournal.com/49667.html

Many thanks. But I am currently confused about the relationship between terminologies used in the Linux kernel and those used in some programming languages (e.g., C++), i.e., the relationships between

    memory_order_release
    memory_order_relaxed
    memory_order_acquire
    memory_order_seq_cst
    ...
Quoted 7 lines

and those used in the kernel:

    READ_ONCE() / WRITE_ONCE()
    rmb() / wmb() / mb() / smp_mb()
    ...

Any materials for that?

Hmm, to be more exact, what I want is something like this:

Quoted 9 lines

“These primitives can be expressed directly in terms of the upcoming C++0x standard. For the smp_mb() primitive this correspondence is not exact; our memory barriers are somewhat stronger than the standard’s atomic_thread_fence(memory_order_seq_cst). The LOAD_SHARED() primitive maps to x.load(memory_order_relaxed) and STORE_SHARED() to x.store(memory_order_relaxed). The barrier() primitive maps to atomic_signal_fence(memory_order_seq_cst). In addition, rcu_dereference() maps to x.load(memory_order_consume) and rcu_assign_pointer() maps to x.store(v, memory_order_release).”

Those are still valid. Again, the other paper from my earlier email has more mappings.

Quoted 6 lines

This is extracted from the paper "User-Level Implementations of Read-Copy Update" by M. Desnoyers and P. McKenney, A. S. Stern, M. R. Dagenais and J. Walpole[1]. And the LOAD_SHARED() and STORE_SHARED() above are READ_ONCE() and WRITE_ONCE(), respectively. (BTW, LOAD_SHARED/STORE_SHARED seem to be better names than READ_ONCE/WRITE_ONCE, which are a bit confusing. How come people adopted those name?)

They came from ACCESS_ONCE(). They are _ONCE() because they prevent the compiler from fusing and splitting accesses, which it can do with normal loads and stores. This Linux Weekly News article has some of this history:

	http://lwn.net/Articles/508991/
Quoted 2 lines

(I find this after digging into a whole bunch of emails...hmm..email is a good thing)

;-) ;-) ;-)

Thanx, Paul

Quoted 4 lines

[1]: https://www.efficios.com/pub/rcu/urcu-main-accepted.pdf

Yubin

author
#6 lore raw
Quoted 63 lines · Paul E. McKenney
Quoted 52 lines · Yubin Ruan
Quoted 41 lines · Yubin Ruan
Quoted 2 lines · Paul E. McKenney
Quoted 1 line · Yubin Ruan

On Tue, Apr 10, 2018 at 08:14:08PM +0800, Yubin Ruan wrote:

[...]

Quoted 19 lines
Quoted 13 lines
Quoted 5 lines

Can you please provide me with some examples or references for different kinds of memory reordering in a SMP system? You know, there are different kinds of reordering:

Quoted 7 lines

- Loads reordered after loads
- Loads reordered after stores
- Stores reordered after stores
- Stores reordered after loads
- Atomic reordered with loads
- Atomic reordered with stores
- Dependent loads reordered (DEC alpha)

Quoted 3 lines

I remember there is open-std.org webpage containing comparision of C++'s memory model to those primitives used in the Linux kernel. But I just can't find that page.

Here you go!

Quoted 7 lines

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0124r4.html

There will be an update in a month or so, but the above is pretty close. Also, the Linux-kernel memory model was presented at ASPLOS and accepted into the Linux kernel itself:

https://paulmck.livejournal.com/49667.html

Many thanks. But I am currently confused about the relationship between terminologies used in the Linux kernel and those used in some programming languages (e.g., C++), i.e., the relationships between

    memory_order_release
    memory_order_relaxed
    memory_order_acquire
    memory_order_seq_cst
    ...
Quoted 7 lines

and those used in the kernel:

    READ_ONCE() / WRITE_ONCE()
    rmb() / wmb() / mb() / smp_mb()
    ...

Any materials for that?

Hmm, to be more exact, what I want is something like this:

Quoted 9 lines

“These primitives can be expressed directly in terms of the upcoming C++0x standard. For the smp_mb() primitive this correspondence is not exact; our memory barriers are somewhat stronger than the standard’s atomic_thread_fence(memory_order_seq_cst). The LOAD_SHARED() primitive maps to x.load(memory_order_relaxed) and STORE_SHARED() to x.store(memory_order_relaxed). The barrier() primitive maps to atomic_signal_fence(memory_order_seq_cst). In addition, rcu_dereference() maps to x.load(memory_order_consume) and rcu_assign_pointer() maps to x.store(v, memory_order_release).”

Quoted 2 lines

Those are still valid. Again, the other paper from my earlier email has more mappings.

Sorry I missed that! (trying to read too much all at once)

I read about atomic_ops here

    https://www.kernel.org/doc/html/v4.14/core-api/atomic_ops.html

and find that many "atomic" operations such as atomic_set/atomic_read/atomic_write does not require volatile semantic, nor does it require alignment constraints that force the CPU to do load/store "at once". In this situation, both the compiler and the processor are all allowed to tear apart a read/write atomic operation. How can it be "atomic" in this case?

Yubin

author
#7 lore raw
Quoted 71 lines · Yubin Ruan
Quoted 63 lines · Paul E. McKenney
Quoted 52 lines · Yubin Ruan
Quoted 41 lines · Yubin Ruan
Quoted 2 lines · Paul E. McKenney
Quoted 1 line · Yubin Ruan

On Tue, Apr 10, 2018 at 08:14:08PM +0800, Yubin Ruan wrote:

[...]

Quoted 19 lines
Quoted 13 lines
Quoted 5 lines

Can you please provide me with some examples or references for different kinds of memory reordering in a SMP system? You know, there are different kinds of reordering:

Quoted 7 lines

- Loads reordered after loads
- Loads reordered after stores
- Stores reordered after stores
- Stores reordered after loads
- Atomic reordered with loads
- Atomic reordered with stores
- Dependent loads reordered (DEC alpha)

Quoted 3 lines

I remember there is open-std.org webpage containing comparision of C++'s memory model to those primitives used in the Linux kernel. But I just can't find that page.

Here you go!

Quoted 7 lines

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0124r4.html

There will be an update in a month or so, but the above is pretty close. Also, the Linux-kernel memory model was presented at ASPLOS and accepted into the Linux kernel itself:

https://paulmck.livejournal.com/49667.html

Many thanks. But I am currently confused about the relationship between terminologies used in the Linux kernel and those used in some programming languages (e.g., C++), i.e., the relationships between

    memory_order_release
    memory_order_relaxed
    memory_order_acquire
    memory_order_seq_cst
    ...
Quoted 7 lines

and those used in the kernel:

    READ_ONCE() / WRITE_ONCE()
    rmb() / wmb() / mb() / smp_mb()
    ...

Any materials for that?

Hmm, to be more exact, what I want is something like this:

Quoted 9 lines

“These primitives can be expressed directly in terms of the upcoming C++0x standard. For the smp_mb() primitive this correspondence is not exact; our memory barriers are somewhat stronger than the standard’s atomic_thread_fence(memory_order_seq_cst). The LOAD_SHARED() primitive maps to x.load(memory_order_relaxed) and STORE_SHARED() to x.store(memory_order_relaxed). The barrier() primitive maps to atomic_signal_fence(memory_order_seq_cst). In addition, rcu_dereference() maps to x.load(memory_order_consume) and rcu_assign_pointer() maps to x.store(v, memory_order_release).”

Quoted 2 lines

Those are still valid. Again, the other paper from my earlier email has more mappings.

Sorry I missed that! (trying to read too much all at once)

I read about atomic_ops here

Quoted 8 lines
    https://www.kernel.org/doc/html/v4.14/core-api/atomic_ops.html

and find that many "atomic" operations such as atomic_set/atomic_read/atomic_write does not require volatile semantic, nor does it require alignment constraints that force the CPU to do load/store "at once". In this situation, both the compiler and the processor are all allowed to tear apart a read/write atomic operation. How can it be "atomic" in this case?

Hmm... Reading more source code confirms that there are READ_ONCE/WRITE_ONCE used in atomic_set/atomic_read/atomic_write. But these does not prevent the processor from tearing apart the reads/write. Can the definition

    typedef struct { int counter; } atomic_t;

guarantee necessary alignment constraints required by the processor to perform atomic operations?

Yubin

#8 lore raw
Quoted 81 lines · Yubin Ruan
Quoted 71 lines · Yubin Ruan
Quoted 63 lines · Paul E. McKenney
Quoted 52 lines · Yubin Ruan
Quoted 41 lines · Yubin Ruan
Quoted 2 lines · Paul E. McKenney
Quoted 1 line · Yubin Ruan

On Tue, Apr 10, 2018 at 08:14:08PM +0800, Yubin Ruan wrote:

[...]

Quoted 19 lines
Quoted 13 lines
Quoted 5 lines

Can you please provide me with some examples or references for different kinds of memory reordering in a SMP system? You know, there are different kinds of reordering:

Quoted 7 lines

- Loads reordered after loads
- Loads reordered after stores
- Stores reordered after stores
- Stores reordered after loads
- Atomic reordered with loads
- Atomic reordered with stores
- Dependent loads reordered (DEC alpha)

Quoted 3 lines

I remember there is open-std.org webpage containing comparision of C++'s memory model to those primitives used in the Linux kernel. But I just can't find that page.

Here you go!

Quoted 7 lines

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0124r4.html

There will be an update in a month or so, but the above is pretty close. Also, the Linux-kernel memory model was presented at ASPLOS and accepted into the Linux kernel itself:

https://paulmck.livejournal.com/49667.html

Many thanks. But I am currently confused about the relationship between terminologies used in the Linux kernel and those used in some programming languages (e.g., C++), i.e., the relationships between

    memory_order_release
    memory_order_relaxed
    memory_order_acquire
    memory_order_seq_cst
    ...
Quoted 7 lines

and those used in the kernel:

    READ_ONCE() / WRITE_ONCE()
    rmb() / wmb() / mb() / smp_mb()
    ...

Any materials for that?

Hmm, to be more exact, what I want is something like this:

Quoted 9 lines

“These primitives can be expressed directly in terms of the upcoming C++0x standard. For the smp_mb() primitive this correspondence is not exact; our memory barriers are somewhat stronger than the standard’s atomic_thread_fence(memory_order_seq_cst). The LOAD_SHARED() primitive maps to x.load(memory_order_relaxed) and STORE_SHARED() to x.store(memory_order_relaxed). The barrier() primitive maps to atomic_signal_fence(memory_order_seq_cst). In addition, rcu_dereference() maps to x.load(memory_order_consume) and rcu_assign_pointer() maps to x.store(v, memory_order_release).”

Quoted 2 lines

Those are still valid. Again, the other paper from my earlier email has more mappings.

Sorry I missed that! (trying to read too much all at once)

I read about atomic_ops here

Quoted 8 lines
    https://www.kernel.org/doc/html/v4.14/core-api/atomic_ops.html

and find that many "atomic" operations such as atomic_set/atomic_read/atomic_write does not require volatile semantic, nor does it require alignment constraints that force the CPU to do load/store "at once". In this situation, both the compiler and the processor are all allowed to tear apart a read/write atomic operation. How can it be "atomic" in this case?

Quoted 3 lines

Hmm... Reading more source code confirms that there are READ_ONCE/WRITE_ONCE used in atomic_set/atomic_read/atomic_write. But these does not prevent the processor from tearing apart the reads/write.

But it does prevent the compiler from doing so if the variable is small enough to be accessed with a single load/store instruction. And if the variable is aligned, the processor won't split a single load/store instruction. And if the processor doesn't have (say) a load-byte instruction, the current C-language standard requires it to use an atomic read-modify-write sequence, which also avoids the tearing apart.

Quoted 6 lines

Can the definition

typedef struct { int counter; } atomic_t;

guarantee necessary alignment constraints required by the processor to perform atomic operations?

Yes, the compiler aligns machine types (including int). Unless you use "packed" or some such, but if you do that, you get what you deserve. ;-)

Thanx, Paul

#9 lore raw
In reply to Yubin Ruan
Quoted 41 lines · Yubin Ruan
Quoted 2 lines · Paul E. McKenney
Quoted 1 line · Yubin Ruan

On Tue, Apr 10, 2018 at 08:14:08PM +0800, Yubin Ruan wrote:

[...]

Quoted 19 lines
Quoted 13 lines
Quoted 5 lines

Can you please provide me with some examples or references for different kinds of memory reordering in a SMP system? You know, there are different kinds of reordering:

Quoted 7 lines

- Loads reordered after loads
- Loads reordered after stores
- Stores reordered after stores
- Stores reordered after loads
- Atomic reordered with loads
- Atomic reordered with stores
- Dependent loads reordered (DEC alpha)

Quoted 3 lines

I remember there is open-std.org webpage containing comparision of C++'s memory model to those primitives used in the Linux kernel. But I just can't find that page.

Here you go!

Quoted 7 lines

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0124r4.html

There will be an update in a month or so, but the above is pretty close. Also, the Linux-kernel memory model was presented at ASPLOS and accepted into the Linux kernel itself:

https://paulmck.livejournal.com/49667.html

Many thanks. But I am currently confused about the relationship between terminologies used in the Linux kernel and those used in some programming languages (e.g., C++), i.e., the relationships between

    memory_order_release
    memory_order_relaxed
    memory_order_acquire
    memory_order_seq_cst
    ...
Quoted 7 lines

and those used in the kernel:

    READ_ONCE() / WRITE_ONCE()
    rmb() / wmb() / mb() / smp_mb()
    ...

Any materials for that?

The URL I posted above:

http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0124r4.html

Thanx, Paul