Re: [PATCH] Linux: Implement membarrier function

[Alan Stern <stern at rowland dot harvard dot edu>]

On Thu, 13 Dec 2018, Paul E. McKenney wrote:

> > > I guess that I still haven't gotten over being a bit surprised that the
> > > RCU counting rule also applies to sys_membarrier().  ;-)
> > 
> > Why not?  They are both synchronization mechanisms with heavy-weight
> > write sides and light-weight read sides, and most importantly, they
> > provide the same Guarantee.
> 
> True, but I do feel the need to poke at it.
> 
> The zero-size sys_membarrier() read-side critical sections do make
> things act a bit differently, for example, interchanging the accesses
> in an RCU read-side critical section has no effect, while doing so in
> a sys_membarrier() reader can cause the result to be allowed.  One key
> point is that everything before the end of a read-side critical section
> of any type is ordered before any later grace period of that same type,
> and vice versa.
> 
> This is why reordering accesses matters for sys_membarrier() readers but
> not for RCU and SRCU readers -- in the case of RCU and SRCU readers,
> the accesses are inside the read-side critical section, while for
> sys_membarrier() readers, the read-side critical sections don't have
> an inside.  So yes, ordering also matters in the case of SRCU and
> RCU readers for accesses outside of the read-side critical sections.
> The reason sys_membarrier() seems surprising to me isn't because it is
> any different in theoretical structure, but rather because the practice
> is to put RCU and SRCU read-side accesses inside a read-side critical
> sections, which is impossible for sys_membarrier().

RCU and sys_membarrier are more similar than you might think at first.  
For one thing, if there were primitives for blocking and unblocking
reception of IPIs, those primitives would delimit critical sections for
sys_membarrier.  (Maybe such things do exist; I wouldn't know.)

For another, the way we model RCU isn't fully accurate for the Linux
kernel, as you know.  Since individual instructions cannot be
preempted, each instruction is a tiny read-side critical section.
Thus, litmus tests like this one:

	P0			P1
	Wa=1			Wb=1
	synchronize_rcu()	Ra=0
	Rb=0

actually are forbidden in the kernel (provided P1 isn't part of the
idle loop!), even though the LKMM allows them.  However, it wouldn't
be forbidden if the accesses in P1 were swapped -- just like with
sys_membarrier.

Put these two observations together and you see that sys_membarrier is
almost exactly the same as RCU without explicit read-side critical
sections. Perhaps this isn't surprising, given that the initial
implementation of sys_membarrier() was pretty much the same as
synchronize_rcu().

> The other thing that took some time to get used to is the possibility
> of long delays during sys_membarrier() execution, allowing significant
> execution and reordering between different CPUs' IPIs.  This was key
> to my understanding of the six-process example, and probably needs to
> be clearly called out, including in an example or two.

In all the examples I'm aware of, no more than one of the IPIs
generated by each sys_membarrier call really matters.  (Of course,
there's no way to know in advance which one it will be, so you have to
send an IPI to every CPU.)  The execution delays and reordering
between different CPUs' IPIs don't appear to be significant.

> The interleaving restrictions are straightforward for me, but the
> fixed-time approach does have some interesting cross-talk potential
> between sys_membarrier() and RCU read-side critical sections whose
> accesses have been reversed.  I don't believe that it is possible to
> leverage this "order the other guy's read-side critical sections" effect
> in the general case, but I could be missing something.

I regard the fixed-time approach as nothing more than a heuristic
aid.  It's not an accurate explaination of what's really going on.

> If you are claiming that I am worrying unnecessarily, you are probably
> right.  But if I didn't worry unnecessarily, RCU wouldn't work at all!  ;-)

Alan