Re: Some question regarding Memory barrier

Re: Some question regarding Memory barrier

[Paul E. McKenney]

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@kernel.org>
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@gmail.com>
    Signed-off-by: Paul E. McKenney <paulmck@kernel.org>

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