doc: Update memory-barriers.txt for read-to-write dependencies
Subsystems (2)
PATCH 1/1 doc: Update memory-barriers.txt for read-to-write dependencies
The memory-barriers.txt document contains an obsolete passage stating that smp_read_barrier_depends() is required to force ordering for read-to-write dependencies. We now know that this is not required, even for DEC Alpha. This commit therefore updates this passage to state that read-to-write dependencies are respected even without smp_read_barrier_depends().
Documentation/memory-barriers.txt +9 -6
@@ -594,7 +594,10 @@ between the address load and the data load: This enforces the occurrence of one of the two implications, and prevents the third possibility from arising. -A data-dependency barrier must also order against dependent writes: +A data-dependency barrier is not required to order dependent writes +because the CPUs that the Linux kernel supports don't do writes until +they are certain (1) that the write will actually happen, (2) of the +location of the write, and (3) of the value to be written. CPU 1 CPU 2 =============== ===============
@@ -603,19 +606,19 @@ A data-dependency barrier must also order against dependent writes: <write barrier> WRITE_ONCE(P, &B); Q = READ_ONCE(P); - <data dependency barrier> *Q = 5; -The data-dependency barrier must order the read into Q with the store -into *Q. This prohibits this outcome: +Therefore, no data-dependency barrier is required to order the read into +Q with the store into *Q. In other words, this outcome is prohibited, +even without a data-dependency barrier: (Q == &B) && (B == 4) Please note that this pattern should be rare. After all, the whole point of dependency ordering is to -prevent- writes to the data structure, along with the expensive cache misses associated with those writes. This pattern -can be used to record rare error conditions and the like, and the ordering -prevents such records from being lost. +can be used to record rare error conditions and the like, and the CPUs' +naturally occurring ordering prevents such records from being lost. [!] Note that this extremely counterintuitive situation arises most easily on
Hi Paul,
Quoted 22 lines · Paul E. McKenney
The memory-barriers.txt document contains an obsolete passage stating that
smp_read_barrier_depends()is required to force ordering for read-to-write dependencies. We now know that this is not required, even for DEC Alpha. This commit therefore updates this passage to state that read-to-write dependencies are respected even withoutsmp_read_barrier_depends().Reported-by Lance Roy <[email protected]>Signed-off-by Paul E. McKenney <[email protected]>Cc David Howells <[email protected]>Cc Will Deacon <[email protected]>Cc Peter Zijlstra <[email protected]>Cc Jonathan Corbet <[email protected]>Cc Alan Stern <[email protected]>Cc Andrea Parri <[email protected]>Cc Jade Alglave <[email protected]>Cc Luc Maranget <[email protected]>Documentation/memory-barriers.txt +0
-0
Documentation/memory-barriers.txt between the address load and the data load: · line 600
Quoted 8 lines
Documentation/memory-barriers.txt +4
-1@@ -594,7 +594,10 @@ between the address load and the data load: This enforces the occurrence of one of the two implications, and prevents the third possibility from arising. -A data-dependency barrier must also order against dependent writes: +A data-dependency barrier is not required to order dependent writes +because the CPUs that the Linux kernel supports don't do writes until +they are certain (1) that the write will actually happen, (2) of the +location of the write, and (3) of the value to be written.
Might be worth mentioning that you have to careful with the compiler here, and pointing to the section on "Control dependencies" so that people don't just take these three points as guarantees in isolation.
Documentation/memory-barriers.txt A data-dependency barrier must also order against dependent writes: · line 609
Quoted 9 lines
Documentation/memory-barriers.txt +0
-1CPU 1 CPU 2 =============== ===============@@ -603,19 +606,19 @@ A data-dependency barrier must also order against dependent writes: <write barrier> WRITE_ONCE(P, &B); Q = READ_ONCE(P); - <data dependency barrier> *Q = 5;
Do we want that write to Q to be a WRITE_ONCE? Again, the control dependencies section does call this out.
Will
Quoted 39 lines · Will Deacon
Hi Paul,
Quoted 22 lines · Paul E. McKenney
The memory-barriers.txt document contains an obsolete passage stating that
smp_read_barrier_depends()is required to force ordering for read-to-write dependencies. We now know that this is not required, even for DEC Alpha. This commit therefore updates this passage to state that read-to-write dependencies are respected even withoutsmp_read_barrier_depends().Reported-by Lance Roy <[email protected]>Signed-off-by Paul E. McKenney <[email protected]>Cc David Howells <[email protected]>Cc Will Deacon <[email protected]>Cc Peter Zijlstra <[email protected]>Cc Jonathan Corbet <[email protected]>Cc Alan Stern <[email protected]>Cc Andrea Parri <[email protected]>Cc Jade Alglave <[email protected]>Cc Luc Maranget <[email protected]>Documentation/memory-barriers.txt +0
-0Documentation/memory-barriers.txt between the address load and the data load: · line 600
Quoted 8 lines
Documentation/memory-barriers.txt +4
-1@@ -594,7 +594,10 @@ between the address load and the data load: This enforces the occurrence of one of the two implications, and prevents the third possibility from arising. -A data-dependency barrier must also order against dependent writes: +A data-dependency barrier is not required to order dependent writes +because the CPUs that the Linux kernel supports don't do writes until +they are certain (1) that the write will actually happen, (2) of the +location of the write, and (3) of the value to be written.Might be worth mentioning that you have to careful with the compiler here, and pointing to the section on "Control dependencies" so that people don't just take these three points as guarantees in isolation.
Quoted 1 line
Quoted 11 lines
Documentation/memory-barriers.txt A data-dependency barrier must also order against dependent writes: · line 609
Quoted 8 lines
Documentation/memory-barriers.txt +0
-1CPU 1 CPU 2 =============== ===============@@ -603,19 +606,19 @@ A data-dependency barrier must also order against dependent writes: <write barrier> WRITE_ONCE(P, &B); Q = READ_ONCE(P); - <data dependency barrier> *Q = 5;Do we want that write to Q to be a
WRITE_ONCE? Again, the control dependencies section does call this out.
Both good points! Like this?
Thanx, Paul
------------------------------------------------------------------------
commit 00269a0e23dbc50f1c4f101b23c8d74992eace05
Author: Paul E. McKenney <[email protected]> Date: Fri Jun 30 16:18:28 2017 -0700
doc: Update memory-barriers.txt for read-to-write dependencies
The memory-barriers.txt document contains an obsolete passage stating that smp_read_barrier_depends() is required to force ordering for read-to-write dependencies. We now know that this is not required, even for DEC Alpha. This commit therefore updates this passage to state that read-to-write dependencies are respected even without smp_read_barrier_depends().
[ paulmck: Reference control-dependencies sections and use WRITE_ONCE()
per Will Deacon. Correctly place split-cache paragraph while there. ]
Documentation/memory-barriers.txt +23 -17
@@ -594,7 +594,23 @@ between the address load and the data load: This enforces the occurrence of one of the two implications, and prevents the third possibility from arising. -A data-dependency barrier must also order against dependent writes: + +[!] Note that this extremely counterintuitive situation arises most easily on +machines with split caches, so that, for example, one cache bank processes +even-numbered cache lines and the other bank processes odd-numbered cache +lines. The pointer P might be stored in an odd-numbered cache line, and the +variable B might be stored in an even-numbered cache line. Then, if the +even-numbered bank of the reading CPU's cache is extremely busy while the +odd-numbered bank is idle, one can see the new value of the pointer P (&B), +but the old value of the variable B (2). + + +A data-dependency barrier is not required to order dependent writes +because the CPUs that the Linux kernel supports don't do writes until +they are certain (1) that the write will actually happen, (2) of the +location of the write, and (3) of the value to be written. But please +carefully read the "CONTROL DEPENDENCIES" section: The compiler can +and does break control dependencies in a great many situations. CPU 1 CPU 2 =============== ===============
@@ -603,29 +619,19 @@ A data-dependency barrier must also order against dependent writes: <write barrier> WRITE_ONCE(P, &B); Q = READ_ONCE(P); - <data dependency barrier> - *Q = 5; + WRITE_ONCE(*Q, 5); -The data-dependency barrier must order the read into Q with the store -into *Q. This prohibits this outcome: +Therefore, no data-dependency barrier is required to order the read into +Q with the store into *Q. In other words, this outcome is prohibited, +even without a data-dependency barrier: (Q == &B) && (B == 4) Please note that this pattern should be rare. After all, the whole point of dependency ordering is to -prevent- writes to the data structure, along with the expensive cache misses associated with those writes. This pattern -can be used to record rare error conditions and the like, and the ordering -prevents such records from being lost. - - -[!] Note that this extremely counterintuitive situation arises most easily on -machines with split caches, so that, for example, one cache bank processes -even-numbered cache lines and the other bank processes odd-numbered cache -lines. The pointer P might be stored in an odd-numbered cache line, and the -variable B might be stored in an even-numbered cache line. Then, if the -even-numbered bank of the reading CPU's cache is extremely busy while the -odd-numbered bank is idle, one can see the new value of the pointer P (&B), -but the old value of the variable B (2). +can be used to record rare error conditions and the like, and the CPUs' +naturally occurring ordering prevents such records from being lost. The data dependency barrier is very important to the RCU system,
Will Deacon
Acked-byHello, Paul,
Quoted 18 lines · Paul E. McKenney
Quoted 5 lines · Will Deacon
Might be worth mentioning that you have to careful with the compiler here, and pointing to the section on "Control dependencies" so that people don't just take these three points as guarantees in isolation.
Quoted 1 line
Quoted 11 lines
Documentation/memory-barriers.txt A data-dependency barrier must also order against dependent writes: · line 609
Quoted 8 lines
Documentation/memory-barriers.txt +0
-1CPU 1 CPU 2 =============== ===============@@ -603,19 +606,19 @@ A data-dependency barrier must also order against dependent writes: <write barrier> WRITE_ONCE(P, &B); Q = READ_ONCE(P); - <data dependency barrier> *Q = 5;Do we want that write to Q to be a
WRITE_ONCE? Again, the control dependencies section does call this out.
Quoted 1 line
Both good points! Like this?
More or less, yes! Just one wibble below:
Quoted 41 lines
commit
00269a0e23dbc50f1c4f101b23c8d74992eace05Author: Paul E. McKenney <[email protected]> Date: Fri Jun 30 16:18:28 2017 -0700doc: Update memory-barriers.txt for read-to-write dependencies
The memory-barriers.txt document contains an obsolete passage stating that
smp_read_barrier_depends()is required to force ordering for read-to-write dependencies. We now know that this is not required, even for DEC Alpha. This commit therefore updates this passage to state that read-to-write dependencies are respected even withoutsmp_read_barrier_depends().Reported-by Lance Roy <[email protected]>Signed-off-by Paul E. McKenney <[email protected]>Cc David Howells <[email protected]>Cc Will Deacon <[email protected]>Cc Peter Zijlstra <[email protected]>Cc Jonathan Corbet <[email protected]>Cc Alan Stern <[email protected]>Cc Andrea Parri <[email protected]>Cc Jade Alglave <[email protected]>Cc Luc Maranget <[email protected]>[ paulmck: Reference control-dependencies sections and use
WRITE_ONCE()
per Will Deacon. Correctly place split-cache paragraph while there. ]Documentation/memory-barriers.txt +7
-1@@ -594,7 +594,23 @@ between the address load and the data load: This enforces the occurrence of one of the two implications, and prevents the third possibility from arising. -A data-dependency barrier must also order against dependent writes: + +[!] Note that this extremely counterintuitive situation arises most easily on +machines with split caches, so that, for example, one cache bank processes +even-numbered cache lines and the other bank processes odd-numbered cache +lines. The pointer P might be stored in an odd-numbered cache line, and the +variable B might be stored in an even-numbered cache line. Then, if the +even-numbered bank of the reading CPU's cache is extremely busy while the
Documentation/memory-barriers.txt between the address load and the data load: · line 613
Quoted 10 lines
Documentation/memory-barriers.txt +10
-0+odd-numbered bank is idle, one can see the new value of the pointer P (&B), +but the old value of the variable B (2). + + +A data-dependency barrier is not required to order dependent writes +because the CPUs that the Linux kernel supports don't do writes until +they are certain (1) that the write will actually happen, (2) of the +location of the write, and (3) of the value to be written. But please +carefully read the "CONTROL DEPENDENCIES" section: The compiler can +and does break control dependencies in a great many situations.
This makes it sound like only control dependencies are susceptible to being broken by compiler optimisations, so I'd drop the "control" and just say "The compiler can and does break dependencies in a great many situations".
With that:
Cheers,
Will
Paul E. McKenney
Acked-by Will DeaconQuoted 82 lines · Will Deacon
Hello, Paul,
Quoted 18 lines · Paul E. McKenney
Quoted 5 lines · Will Deacon
Might be worth mentioning that you have to careful with the compiler here, and pointing to the section on "Control dependencies" so that people don't just take these three points as guarantees in isolation.
Quoted 1 line
Quoted 11 lines
Review A data-dependency barrier must also order against dependent writes: · line 609
Quoted 8 lines
(quoted diff) +0
-1CPU 1 CPU 2 =============== ===============@@ -603,19 +606,19 @@ A data-dependency barrier must also order against dependent writes: <write barrier> WRITE_ONCE(P, &B); Q = READ_ONCE(P); - <data dependency barrier> *Q = 5;Do we want that write to Q to be a
WRITE_ONCE? Again, the control dependencies section does call this out.Quoted 1 line
Both good points! Like this?
More or less, yes! Just one wibble below:
Quoted 41 lines
commit
00269a0e23dbc50f1c4f101b23c8d74992eace05Author: Paul E. McKenney <[email protected]> Date: Fri Jun 30 16:18:28 2017 -0700doc: Update memory-barriers.txt for read-to-write dependencies
The memory-barriers.txt document contains an obsolete passage stating that
smp_read_barrier_depends()is required to force ordering for read-to-write dependencies. We now know that this is not required, even for DEC Alpha. This commit therefore updates this passage to state that read-to-write dependencies are respected even withoutsmp_read_barrier_depends().Reported-by Lance Roy <[email protected]>Signed-off-by Paul E. McKenney <[email protected]>Cc David Howells <[email protected]>Cc Will Deacon <[email protected]>Cc Peter Zijlstra <[email protected]>Cc Jonathan Corbet <[email protected]>Cc Alan Stern <[email protected]>Cc Andrea Parri <[email protected]>Cc Jade Alglave <[email protected]>Cc Luc Maranget <[email protected]>[ paulmck: Reference control-dependencies sections and use
WRITE_ONCE()
per Will Deacon. Correctly place split-cache paragraph while there. ]Documentation/memory-barriers.txt +7
-1@@ -594,7 +594,23 @@ between the address load and the data load: This enforces the occurrence of one of the two implications, and prevents the third possibility from arising. -A data-dependency barrier must also order against dependent writes: + +[!] Note that this extremely counterintuitive situation arises most easily on +machines with split caches, so that, for example, one cache bank processes +even-numbered cache lines and the other bank processes odd-numbered cache +lines. The pointer P might be stored in an odd-numbered cache line, and the +variable B might be stored in an even-numbered cache line. Then, if the +even-numbered bank of the reading CPU's cache is extremely busy while theDocumentation/memory-barriers.txt between the address load and the data load: · line 613
Quoted 10 lines
Documentation/memory-barriers.txt +10
-0+odd-numbered bank is idle, one can see the new value of the pointer P (&B), +but the old value of the variable B (2). + + +A data-dependency barrier is not required to order dependent writes +because the CPUs that the Linux kernel supports don't do writes until +they are certain (1) that the write will actually happen, (2) of the +location of the write, and (3) of the value to be written. But please +carefully read the "CONTROL DEPENDENCIES" section: The compiler can +and does break control dependencies in a great many situations.This makes it sound like only control dependencies are susceptible to being broken by compiler optimisations, so I'd drop the "control" and just say "The compiler can and does break dependencies in a great many situations".
Quoted 3 lines
With that:
Acked-by Will Deacon <[email protected]>
Done! I also added a pointer to Documentation/RCU/rcu_dereference.txt, which lists some of the vandalism^Woptimizations that modern compilers can commit. Does the updated patch below capture it?
Thanx, Paul
------------------------------------------------------------------------
commit 3a2414a7991c579e7391968b382988f0300655e5
Author: Paul E. McKenney <[email protected]> Date: Fri Jun 30 16:18:28 2017 -0700
doc: Update memory-barriers.txt for read-to-write dependencies
The memory-barriers.txt document contains an obsolete passage stating that smp_read_barrier_depends() is required to force ordering for read-to-write dependencies. We now know that this is not required, even for DEC Alpha. This commit therefore updates this passage to state that read-to-write dependencies are respected even without smp_read_barrier_depends().
[ paulmck: Reference control-dependencies sections and use WRITE_ONCE()
per Will Deacon. Correctly place split-cache paragraph while there. ]
Documentation/memory-barriers.txt +24 -17
@@ -594,7 +594,24 @@ between the address load and the data load: This enforces the occurrence of one of the two implications, and prevents the third possibility from arising. -A data-dependency barrier must also order against dependent writes: + +[!] Note that this extremely counterintuitive situation arises most easily on +machines with split caches, so that, for example, one cache bank processes +even-numbered cache lines and the other bank processes odd-numbered cache +lines. The pointer P might be stored in an odd-numbered cache line, and the +variable B might be stored in an even-numbered cache line. Then, if the +even-numbered bank of the reading CPU's cache is extremely busy while the +odd-numbered bank is idle, one can see the new value of the pointer P (&B), +but the old value of the variable B (2). + + +A data-dependency barrier is not required to order dependent writes +because the CPUs that the Linux kernel supports don't do writes +until they are certain (1) that the write will actually happen, (2) +of the location of the write, and (3) of the value to be written. +But please carefully read the "CONTROL DEPENDENCIES" section and the +Documentation/RCU/rcu_dereference.txt file: The compiler can and does +break dependencies in a great many highly creative ways. CPU 1 CPU 2 =============== ===============
@@ -603,29 +620,19 @@ A data-dependency barrier must also order against dependent writes: <write barrier> WRITE_ONCE(P, &B); Q = READ_ONCE(P); - <data dependency barrier> - *Q = 5; + WRITE_ONCE(*Q, 5); -The data-dependency barrier must order the read into Q with the store -into *Q. This prohibits this outcome: +Therefore, no data-dependency barrier is required to order the read into +Q with the store into *Q. In other words, this outcome is prohibited, +even without a data-dependency barrier: (Q == &B) && (B == 4) Please note that this pattern should be rare. After all, the whole point of dependency ordering is to -prevent- writes to the data structure, along with the expensive cache misses associated with those writes. This pattern -can be used to record rare error conditions and the like, and the ordering -prevents such records from being lost. - - -[!] Note that this extremely counterintuitive situation arises most easily on -machines with split caches, so that, for example, one cache bank processes -even-numbered cache lines and the other bank processes odd-numbered cache -lines. The pointer P might be stored in an odd-numbered cache line, and the -variable B might be stored in an even-numbered cache line. Then, if the -even-numbered bank of the reading CPU's cache is extremely busy while the -odd-numbered bank is idle, one can see the new value of the pointer P (&B), -but the old value of the variable B (2). +can be used to record rare error conditions and the like, and the CPUs' +naturally occurring ordering prevents such records from being lost. The data dependency barrier is very important to the RCU system,
Quoted 34 lines · Paul E. McKenney
Quoted 33 lines · Will Deacon
Quoted 16 lines · Paul E. McKenney
Documentation/memory-barriers.txt +7
-1@@ -594,7 +594,23 @@ between the address load and the data load: This enforces the occurrence of one of the two implications, and prevents the third possibility from arising. -A data-dependency barrier must also order against dependent writes: + +[!] Note that this extremely counterintuitive situation arises most easily on +machines with split caches, so that, for example, one cache bank processes +even-numbered cache lines and the other bank processes odd-numbered cache +lines. The pointer P might be stored in an odd-numbered cache line, and the +variable B might be stored in an even-numbered cache line. Then, if the +even-numbered bank of the reading CPU's cache is extremely busy while theDocumentation/memory-barriers.txt between the address load and the data load: · line 613
Quoted 10 lines
Documentation/memory-barriers.txt +10
-0+odd-numbered bank is idle, one can see the new value of the pointer P (&B), +but the old value of the variable B (2). + + +A data-dependency barrier is not required to order dependent writes +because the CPUs that the Linux kernel supports don't do writes until +they are certain (1) that the write will actually happen, (2) of the +location of the write, and (3) of the value to be written. But please +carefully read the "CONTROL DEPENDENCIES" section: The compiler can +and does break control dependencies in a great many situations.This makes it sound like only control dependencies are susceptible to being broken by compiler optimisations, so I'd drop the "control" and just say "The compiler can and does break dependencies in a great many situations".
Quoted 7 lines
Quoted 3 lines
With that:
Acked-by Will Deacon <[email protected]>Done! I also added a pointer to
Documentation/RCU/rcu_dereference.txt, which lists some of the vandalism^Woptimizations that modern compilers can commit. Does the updated patch below capture it?
Yes, thanks Paul.
Will