On Tue, Nov 29, 2022 at 12:27:08AM +0300, Kirill Martynov wrote:
> Hello Paul!
> First of all I want to say thank you for the amazing book "Is Parallel
> programming hard".
Glad you like it!
> Right now I'm reading your paper "Memory barriers: a hardware view for
> software hackers"
> and there is one moment that confuses me, on page 9 you wrote:
>
> 4. CPU 0 executes b=1. It already owns this cache
>
> line (in other words, the cache line is already in
>
> either the “modified” or the “exclusive” state),
>
> but there is a marked entry in the store buffer.
>
> Therefore, rather than store the new value of “b”
>
> in the cache line, it instead places it in the store
>
> buffer (but in an unmarked entry).
>
> 5. CPU 0 receives the “read” message, and transmits
>
> the cache line containing the original value
>
> of “b” to CPU 1. It also marks its own copy of
>
> this cache line as “shared”.
>
> 6. CPU 1 receives the cache line containing “b” and
>
> installs it in its cache.
>
> If CPU0 had cache line in M or E state, it means that content in this line
> differs from main memory. Then during the "read" message from CPU1 should
> it sync (write back) this cache line with main memory?
> Otherwise we will end up with CPU0 CPU1 having cache line in Shared state,
> and according to your previous explanations cache line in Shared state can
> be invalidated without writeback to main memory
Yes, you are right, that writeback is necessary within the confines of
strict MESI. I am not in a position to update that paper, but this
same issue is present in Appendix C.3.3 of "Is Parallel Programming
Hard...". I have updated it with your reported-by as shown below.
Good eyes, and thank you for letting me know!
(Adding the perfbook list on Cc.)
Thanx, Paul
------------------------------------------------------------------------
commit 5e6242b1bd3952817b24ccd6d477cc1dadd90639
Author: Paul E. McKenney <paulmck@xxxxxxxxxx>
Date: Mon Nov 28 13:52:58 2022 -0800
appendix/whymb: Note store to memory in SB/MB example
Reported-by: Kirill Martynov <kirill.v.martynov@xxxxxxxxx>
Signed-off-by: Paul E. McKenney <paulmck@xxxxxxxxxx>
diff --git a/appendix/whymb/whymemorybarriers.tex b/appendix/whymb/whymemorybarriers.tex
index 99c68eac..ee9f96f1 100644
--- a/appendix/whymb/whymemorybarriers.tex
+++ b/appendix/whymb/whymemorybarriers.tex
@@ -842,7 +842,10 @@ Then the sequence of operations might be as follows:
so it stores the new value of ``b'' in its cache line.
\item CPU~0 receives the ``read'' message, and transmits the
cache line containing the now-updated value of ``b''
- to CPU~1, also marking the line as ``shared'' in its own cache.
+ to CPU~1, also marking the line as ``shared'' in its own cache
+ (but only after writing back the line containing ``b'' to main
+ memory).
+ \label{seq:app:whymb:Store Buffers and Memory Barriers store}
\item CPU~1 receives the cache line containing ``b'' and installs
it in its cache.
\item CPU~1 can now finish executing \co{while (b == 0) continue},
@@ -874,6 +877,15 @@ Then the sequence of operations might be as follows:
a serious bug in the hardware.
}\EQuickQuizEnd
+\EQuickQuiz{
+ In \cref{seq:app:whymb:Store Buffers and Memory Barriers store}
+ above, don't systems avoid that store to memory?
+}\EQuickQuizAnswer{
+ Yes, they do.
+ But to do so, they add states beyond the MESI quadruple that
+ this example is working within.
+}\EQuickQuizEnd
+
\EQuickQuiz{
In \cref{seq:app:whymb:Store Buffers and Memory Barriers victim}
above, did \co{bar()} read a stale value from \co{a}, or did
