Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1733550 > unrolled thread

Memory-ordering recipes

Back to article view | Back to linux.kernel

Contents

  Memory-ordering recipes "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2017-09-18 01:10 +0200
    Re: Memory-ordering recipes Boqun Feng <boqun.feng@gmail.com> - 2017-09-18 10:00 +0200
      Re: Memory-ordering recipes "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2017-09-18 16:30 +0200
        Re: Memory-ordering recipes Boqun Feng <boqun.feng@gmail.com> - 2017-09-19 04:10 +0200
    Re: Memory-ordering recipes Peter Zijlstra <peterz@infradead.org> - 2017-09-21 14:50 +0200
      Re: Memory-ordering recipes "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2017-09-21 17:30 +0200
        Re: Memory-ordering recipes Peter Zijlstra <peterz@infradead.org> - 2017-09-21 18:20 +0200
          Re: Memory-ordering recipes "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2017-09-21 18:50 +0200
            Re: Memory-ordering recipes Peter Zijlstra <peterz@infradead.org> - 2017-09-22 11:30 +0200
              Re: Memory-ordering recipes "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> - 2017-09-22 23:10 +0200

#1733550 — Memory-ordering recipes

Hello!

The topic of memory-ordering recipes came up at the Linux Plumbers
Conference microconference on Friday, so I thought that I should summarize
what is currently "out there":

1.	memory-barriers.txt:  A bit rambling and diffuse for a recipes
	document.

2.	https://www.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/Examples.html
	Many of the examples are on-point, but this is aimed more
	at understanding the memory model than at an organized set
	of recipes.

3.	https://www.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/Examples.html
	Slides 15-20.  Again, some of the litmus tests are on-point,
	but the focus is more on understanding the memory model than on
	an organized set of recipes.

So what litmus tests are needed?  Here is my initial set:

1.	Release-acquire chains, AKA ISA2, Z6.2, LB, and 3.LB

	Lots of variety here, can in some cases substitute:
	
	a.	READ_ONCE() for smp_load_acquire()
	b.	WRITE_ONCE() for smp_store_release()
	c.	Dependencies for both smp_load_acquire() and
		smp_store_release().
	d.	smp_wmb() for smp_store_release() in first thread
		of ISA2 and Z6.2.
	e.	smp_rmb() for smp_load_acquire() in last thread of ISA2.

2.	MP (see test6.pdf for nickname translation)

	a.	smp_store_release() / smp_load_acquire()
	b.	rcu_assign_pointer() / rcu_dereference()
	c.	smp_wmb() / smp_rmb()
	d.	Replacing either of the above with smp_mb()

3.	SB

	a.	smp_mb(), as in lockless wait-wakeup coordination.
		And as in sys_membarrier()-scheduler coordination,
		for that matter.

Others?

							Thanx, Paul

[toc] | [next] | [standalone]

#1733714

[Multipart message — attachments visible in raw view] — view raw

On Sun, Sep 17, 2017 at 04:05:09PM -0700, Paul E. McKenney wrote:
> Hello!
> 

Hi Paul,

> The topic of memory-ordering recipes came up at the Linux Plumbers
> Conference microconference on Friday, so I thought that I should summarize
> what is currently "out there":
> 
> 1.	memory-barriers.txt:  A bit rambling and diffuse for a recipes
> 	document.
> 
> 2.	https://www.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/Examples.html
> 	Many of the examples are on-point, but this is aimed more
> 	at understanding the memory model than at an organized set
> 	of recipes.
> 
> 3.	https://www.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/Examples.html

Duplicate links ;-) This should a link to some slides?

> 	Slides 15-20.  Again, some of the litmus tests are on-point,
> 	but the focus is more on understanding the memory model than on
> 	an organized set of recipes.
> 
> So what litmus tests are needed?  Here is my initial set:
> 
> 1.	Release-acquire chains, AKA ISA2, Z6.2, LB, and 3.LB
> 
> 	Lots of variety here, can in some cases substitute:
> 	
> 	a.	READ_ONCE() for smp_load_acquire()
> 	b.	WRITE_ONCE() for smp_store_release()
> 	c.	Dependencies for both smp_load_acquire() and
> 		smp_store_release().
> 	d.	smp_wmb() for smp_store_release() in first thread
> 		of ISA2 and Z6.2.
> 	e.	smp_rmb() for smp_load_acquire() in last thread of ISA2.
> 
> 2.	MP (see test6.pdf for nickname translation)
> 
> 	a.	smp_store_release() / smp_load_acquire()
> 	b.	rcu_assign_pointer() / rcu_dereference()
> 	c.	smp_wmb() / smp_rmb()
> 	d.	Replacing either of the above with smp_mb()
> 
> 3.	SB
> 
> 	a.	smp_mb(), as in lockless wait-wakeup coordination.
> 		And as in sys_membarrier()-scheduler coordination,
> 		for that matter.

	b.	replace smp_mb() with smp_mb__before_atomic() followed
		by a _relaxed cmpchg? As in pv_kick_node():

		https://marc.info/?l=linux-kernel&m=150274124711012

Besides, do we also want to add Co* into the set? I think there may be
some people still confused to think per-loc SC is not held, and they may
add unnecessary barriers in their code. Those (Co*) recipes could serve
as a guide for state-machine style programming. Thoughts?

Regards,
Boqun

> 
> Others?
> 
> 							Thanx, Paul
> 

[toc] | [prev] | [next] | [standalone]

#1734178

On Mon, Sep 18, 2017 at 03:52:42PM +0800, Boqun Feng wrote:
> On Sun, Sep 17, 2017 at 04:05:09PM -0700, Paul E. McKenney wrote:
> > Hello!
> > 
> 
> Hi Paul,
> 
> > The topic of memory-ordering recipes came up at the Linux Plumbers
> > Conference microconference on Friday, so I thought that I should summarize
> > what is currently "out there":
> > 
> > 1.	memory-barriers.txt:  A bit rambling and diffuse for a recipes
> > 	document.
> > 
> > 2.	https://www.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/Examples.html
> > 	Many of the examples are on-point, but this is aimed more
> > 	at understanding the memory model than at an organized set
> > 	of recipes.
> > 
> > 3.	https://www.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/Examples.html
> 
> Duplicate links ;-) This should a link to some slides?

Indeed!  How about this one?

http://www.linuxplumbersconf.org/2017/ocw//system/presentations/4708/original/LKMM-overview.2017.09.15b.pdf

> > 	Slides 15-20.  Again, some of the litmus tests are on-point,
> > 	but the focus is more on understanding the memory model than on
> > 	an organized set of recipes.
> > 
> > So what litmus tests are needed?  Here is my initial set:
> > 
> > 1.	Release-acquire chains, AKA ISA2, Z6.2, LB, and 3.LB
> > 
> > 	Lots of variety here, can in some cases substitute:
> > 	
> > 	a.	READ_ONCE() for smp_load_acquire()
> > 	b.	WRITE_ONCE() for smp_store_release()
> > 	c.	Dependencies for both smp_load_acquire() and
> > 		smp_store_release().
> > 	d.	smp_wmb() for smp_store_release() in first thread
> > 		of ISA2 and Z6.2.
> > 	e.	smp_rmb() for smp_load_acquire() in last thread of ISA2.
> > 
> > 2.	MP (see test6.pdf for nickname translation)
> > 
> > 	a.	smp_store_release() / smp_load_acquire()
> > 	b.	rcu_assign_pointer() / rcu_dereference()
> > 	c.	smp_wmb() / smp_rmb()
> > 	d.	Replacing either of the above with smp_mb()
> > 
> > 3.	SB
> > 
> > 	a.	smp_mb(), as in lockless wait-wakeup coordination.
> > 		And as in sys_membarrier()-scheduler coordination,
> > 		for that matter.
> 
> 	b.	replace smp_mb() with smp_mb__before_atomic() followed
> 		by a _relaxed cmpchg? As in pv_kick_node():
> 
> 		https://marc.info/?l=linux-kernel&m=150274124711012
> 
> Besides, do we also want to add Co* into the set? I think there may be
> some people still confused to think per-loc SC is not held, and they may
> add unnecessary barriers in their code. Those (Co*) recipes could serve
> as a guide for state-machine style programming. Thoughts?

Indeed, it would be good to have some single-variable-SC recipes.

And single-variable-SC holds only if you use READ_ONCE().  ;-)

							Thanx, Paul

[toc] | [prev] | [next] | [standalone]

#1734596

[Multipart message — attachments visible in raw view] — view raw

On Mon, Sep 18, 2017 at 07:25:48AM -0700, Paul E. McKenney wrote:
> On Mon, Sep 18, 2017 at 03:52:42PM +0800, Boqun Feng wrote:
> > On Sun, Sep 17, 2017 at 04:05:09PM -0700, Paul E. McKenney wrote:
> > > Hello!
> > > 
> > 
> > Hi Paul,
> > 
> > > The topic of memory-ordering recipes came up at the Linux Plumbers
> > > Conference microconference on Friday, so I thought that I should summarize
> > > what is currently "out there":
> > > 
> > > 1.	memory-barriers.txt:  A bit rambling and diffuse for a recipes
> > > 	document.
> > > 
> > > 2.	https://www.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/Examples.html
> > > 	Many of the examples are on-point, but this is aimed more
> > > 	at understanding the memory model than at an organized set
> > > 	of recipes.
> > > 
> > > 3.	https://www.kernel.org/pub/linux/kernel/people/paulmck/LWNLinuxMM/Examples.html
> > 
> > Duplicate links ;-) This should a link to some slides?
> 
> Indeed!  How about this one?
> 
> http://www.linuxplumbersconf.org/2017/ocw//system/presentations/4708/original/LKMM-overview.2017.09.15b.pdf
> 

Got it.

Thanks for the link ;-)

Regards,
Boqun

> > > 	Slides 15-20.  Again, some of the litmus tests are on-point,
> > > 	but the focus is more on understanding the memory model than on
> > > 	an organized set of recipes.
> > > 
> > > So what litmus tests are needed?  Here is my initial set:
> > > 
> > > 1.	Release-acquire chains, AKA ISA2, Z6.2, LB, and 3.LB
> > > 
> > > 	Lots of variety here, can in some cases substitute:
> > > 	
> > > 	a.	READ_ONCE() for smp_load_acquire()
> > > 	b.	WRITE_ONCE() for smp_store_release()
> > > 	c.	Dependencies for both smp_load_acquire() and
> > > 		smp_store_release().
> > > 	d.	smp_wmb() for smp_store_release() in first thread
> > > 		of ISA2 and Z6.2.
> > > 	e.	smp_rmb() for smp_load_acquire() in last thread of ISA2.
> > > 
> > > 2.	MP (see test6.pdf for nickname translation)
> > > 
> > > 	a.	smp_store_release() / smp_load_acquire()
> > > 	b.	rcu_assign_pointer() / rcu_dereference()
> > > 	c.	smp_wmb() / smp_rmb()
> > > 	d.	Replacing either of the above with smp_mb()
> > > 
> > > 3.	SB
> > > 
> > > 	a.	smp_mb(), as in lockless wait-wakeup coordination.
> > > 		And as in sys_membarrier()-scheduler coordination,
> > > 		for that matter.
> > 
> > 	b.	replace smp_mb() with smp_mb__before_atomic() followed
> > 		by a _relaxed cmpchg? As in pv_kick_node():
> > 
> > 		https://marc.info/?l=linux-kernel&m=150274124711012
> > 
> > Besides, do we also want to add Co* into the set? I think there may be
> > some people still confused to think per-loc SC is not held, and they may
> > add unnecessary barriers in their code. Those (Co*) recipes could serve
> > as a guide for state-machine style programming. Thoughts?
> 
> Indeed, it would be good to have some single-variable-SC recipes.
> 
> And single-variable-SC holds only if you use READ_ONCE().  ;-)
> 
> 							Thanx, Paul
> 

[toc] | [prev] | [next] | [standalone]

#1736639

On Sun, Sep 17, 2017 at 04:05:09PM -0700, Paul E. McKenney wrote:

> So what litmus tests are needed?  Here is my initial set:
> 
> 1.	Release-acquire chains, AKA ISA2, Z6.2, LB, and 3.LB
> 
> 	Lots of variety here, can in some cases substitute:
> 	
> 	a.	READ_ONCE() for smp_load_acquire()
> 	b.	WRITE_ONCE() for smp_store_release()
> 	c.	Dependencies for both smp_load_acquire() and
> 		smp_store_release().
> 	d.	smp_wmb() for smp_store_release() in first thread
> 		of ISA2 and Z6.2.
> 	e.	smp_rmb() for smp_load_acquire() in last thread of ISA2.
> 
> 2.	MP (see test6.pdf for nickname translation)
> 
> 	a.	smp_store_release() / smp_load_acquire()
> 	b.	rcu_assign_pointer() / rcu_dereference()
> 	c.	smp_wmb() / smp_rmb()
> 	d.	Replacing either of the above with smp_mb()
> 
> 3.	SB
> 
> 	a.	smp_mb(), as in lockless wait-wakeup coordination.
> 		And as in sys_membarrier()-scheduler coordination,
> 		for that matter.
> 
> Others?

So I have no idea what you're proposing here. The above is just a bunch
of words without meaning :-(

[toc] | [prev] | [next] | [standalone]

#1736772

On Thu, Sep 21, 2017 at 02:45:31PM +0200, Peter Zijlstra wrote:
> On Sun, Sep 17, 2017 at 04:05:09PM -0700, Paul E. McKenney wrote:
> 
> > So what litmus tests are needed?  Here is my initial set:
> > 
> > 1.	Release-acquire chains, AKA ISA2, Z6.2, LB, and 3.LB

I grouped the expansions of all of these names at the end.

> > 	Lots of variety here, can in some cases substitute:
> > 	
> > 	a.	READ_ONCE() for smp_load_acquire()
> > 	b.	WRITE_ONCE() for smp_store_release()
> > 	c.	Dependencies for both smp_load_acquire() and
> > 		smp_store_release().
> > 	d.	smp_wmb() for smp_store_release() in first thread
> > 		of ISA2 and Z6.2.
> > 	e.	smp_rmb() for smp_load_acquire() in last thread of ISA2.

The key point of these is to illustrate patterns that require only
the lightest ordering.

> > 2.	MP (see test6.pdf for nickname translation)
> > 
> > 	a.	smp_store_release() / smp_load_acquire()
> > 	b.	rcu_assign_pointer() / rcu_dereference()
> > 	c.	smp_wmb() / smp_rmb()
> > 	d.	Replacing either of the above with smp_mb()

This one is a workhorse, used very frequently.

> > 3.	SB
> > 
> > 	a.	smp_mb(), as in lockless wait-wakeup coordination.
> > 		And as in sys_membarrier()-scheduler coordination,
> > 		for that matter.

This is also used frequently, for example, in lockless wait-wakeup
situations.

> > Others?

Someone (quite rightly) suggested adding some single-variable SC
examples, which I will do.

> So I have no idea what you're proposing here. The above is just a bunch
> of words without meaning :-(

As Boqun said on IRC, this URL is your friend:

	https://www.cl.cam.ac.uk/~pes20/ppc-supplemental/test6.pdf

Many of the names seem quite arbitrary, but the abbreviation can be useful.

ISA2 is the first one on page 2, and has this pattern of reads and
writes:

	CPU 0			CPU 1			CPU 2

	WRITE_ONCE(x, 1);	r1 = READ_ONCE(y);	r2 = READ_ONCE(z);
	WRITE_ONCE(y, 1);	WRITE_ONCE(z, 1);	r3 = READ_ONCE(x);

	BUG_ON(r1 == 1 && r2 == 1 && r3 == 0);

Arbitrary ordering can be added to all of these litmus-test patterns,
for example, the writes to y and z might become smp_store_release()
and the read from z might become smp_load_acquire().  Or, alternatively,
smp_mb() might be placed between accesses on all thread CPUs.  The key
point is that "ISA2" identifies not a specific litmus test, but instead a
family of them with the same pattern of reads, writes and RMW operations,
but with different ordering properties.

Z6.3 is the second one on page 2:

	CPU 0			CPU 1			CPU 2

	WRITE_ONCE(x, 2);	r1 = READ_ONCE(y);	r2 = READ_ONCE(z);
	WRITE_ONCE(y, 1);	WRITE_ONCE(z, 1);	WRITE_ONCE(x, 1);

	BUG_ON(r1 == 1 && r2 == 1 && x == 2);

LB is the last on on the extreme left of page 1.  "LB" stands for
"load buffering", and each CPU's first access is a load and last
access is a store:

	CPU 0			CPU 1

	r1 = READ_ONCE(x);	r2 = READ_ONCE(y);
	WRITE_ONCE(y, 1);	WRITE_ONCE(x, 1);

	BUG_ON(r1 == 1 && r2 == 1);

3.LB is simply a three-CPU extension of LB, and "LB" by itself is
sometimes used to cover an arbitrary number of CPUs:

	CPU 0			CPU 1			CPU 2

	r1 = READ_ONCE(x);	r2 = READ_ONCE(y);	r3 = READ_ONCE(z);
	WRITE_ONCE(y, 1);	WRITE_ONCE(z, 1);	WRITE_ONCE(x, 1);

	BUG_ON(r1 == 1 && r2 == 1 && r3 == 1);

MP is the second on the extreme left of page 1.  "MP" stands for "message
passing", and is used very heavily.  The idea is that "x" is the message
(sent by CPU 0), and "y" is a flag saying that the message is ready to
be received (by CPU 1).

	CPU 0			CPU 1

	WRITE_ONCE(x, 1);	r1 = READ_ONCE(y);
	WRITE_ONCE(y, 1);	r1 = READ_ONCE(x);

	BUG_ON(r1 == 1 && r2 == 0);

SB is the fourth on the extreme left of page 1.  "SB" stands for "store
buffering" because systems without store buffers won't reorder this one.

	CPU 0			CPU 1

	WRITE_ONCE(x, 1);	WRITE_ONCE(y, 1);
	r1 = READ_ONCE(y);	r2 = READ_ONCE(x);

	BUG_ON(r1 == 0 && r2 == 0);

Does that help?

Oh, and the actual recipes would include ordering as indicated by
the sub-bullets.

							Thanx, Paul

[toc] | [prev] | [next] | [standalone]

#1736823

On Thu, Sep 21, 2017 at 08:26:42AM -0700, Paul E. McKenney wrote:
> ISA2 is the first one on page 2, and has this pattern of reads and
> writes:
> 
> 	CPU 0			CPU 1			CPU 2
> 
> 	WRITE_ONCE(x, 1);	r1 = READ_ONCE(y);	r2 = READ_ONCE(z);
> 	WRITE_ONCE(y, 1);	WRITE_ONCE(z, 1);	r3 = READ_ONCE(x);
> 
> 	BUG_ON(r1 == 1 && r2 == 1 && r3 == 0);
> 
> Arbitrary ordering can be added to all of these litmus-test patterns,
> for example, the writes to y and z might become smp_store_release()
> and the read from z might become smp_load_acquire().  Or, alternatively,
> smp_mb() might be placed between accesses on all thread CPUs.  The key
> point is that "ISA2" identifies not a specific litmus test, but instead a
> family of them with the same pattern of reads, writes and RMW operations,
> but with different ordering properties.
> 
> Z6.3 is the second one on page 2:
> 
> 	CPU 0			CPU 1			CPU 2
> 
> 	WRITE_ONCE(x, 2);	r1 = READ_ONCE(y);	r2 = READ_ONCE(z);
> 	WRITE_ONCE(y, 1);	WRITE_ONCE(z, 1);	WRITE_ONCE(x, 1);
> 
> 	BUG_ON(r1 == 1 && r2 == 1 && x == 2);

But why are these useful to include in a recipes list? I would imagine
those should cover the simple 2 threads stuff. Once you go fancy and
need 3 CPUs I feel people had better know wth they're on about.

> LB is the last on on the extreme left of page 1.  "LB" stands for
> "load buffering", and each CPU's first access is a load and last
> access is a store:
> 
> 	CPU 0			CPU 1
> 
> 	r1 = READ_ONCE(x);	r2 = READ_ONCE(y);
> 	WRITE_ONCE(y, 1);	WRITE_ONCE(x, 1);
> 
> 	BUG_ON(r1 == 1 && r2 == 1);

> MP is the second on the extreme left of page 1.  "MP" stands for "message
> passing", and is used very heavily.  The idea is that "x" is the message
> (sent by CPU 0), and "y" is a flag saying that the message is ready to
> be received (by CPU 1).
> 
> 	CPU 0			CPU 1
> 
> 	WRITE_ONCE(x, 1);	r1 = READ_ONCE(y);
> 	WRITE_ONCE(y, 1);	r1 = READ_ONCE(x);
> 
> 	BUG_ON(r1 == 1 && r2 == 0);

Right, these two are fairly common patterns.

> SB is the fourth on the extreme left of page 1.  "SB" stands for "store
> buffering" because systems without store buffers won't reorder this one.
> 
> 	CPU 0			CPU 1
> 
> 	WRITE_ONCE(x, 1);	WRITE_ONCE(y, 1);
> 	r1 = READ_ONCE(y);	r2 = READ_ONCE(x);
> 
> 	BUG_ON(r1 == 0 && r2 == 0);
> 
> Does that help?
> 
> Oh, and the actual recipes would include ordering as indicated by
> the sub-bullets.

Which just generates a terrible lot of noise. Why would people be
interested in these permutations? Why not the minimal set that makes the
guarantee?

Also, none of these cover 'simple' stuff like a ring-buffer.

So I have to ask, what is the purpose of this recipes list?

[toc] | [prev] | [next] | [standalone]

#1736842

On Thu, Sep 21, 2017 at 06:15:47PM +0200, Peter Zijlstra wrote:
> On Thu, Sep 21, 2017 at 08:26:42AM -0700, Paul E. McKenney wrote:
> > ISA2 is the first one on page 2, and has this pattern of reads and
> > writes:
> > 
> > 	CPU 0			CPU 1			CPU 2
> > 
> > 	WRITE_ONCE(x, 1);	r1 = READ_ONCE(y);	r2 = READ_ONCE(z);
> > 	WRITE_ONCE(y, 1);	WRITE_ONCE(z, 1);	r3 = READ_ONCE(x);
> > 
> > 	BUG_ON(r1 == 1 && r2 == 1 && r3 == 0);
> > 
> > Arbitrary ordering can be added to all of these litmus-test patterns,
> > for example, the writes to y and z might become smp_store_release()
> > and the read from z might become smp_load_acquire().  Or, alternatively,
> > smp_mb() might be placed between accesses on all thread CPUs.  The key
> > point is that "ISA2" identifies not a specific litmus test, but instead a
> > family of them with the same pattern of reads, writes and RMW operations,
> > but with different ordering properties.
> > 
> > Z6.3 is the second one on page 2:
> > 
> > 	CPU 0			CPU 1			CPU 2
> > 
> > 	WRITE_ONCE(x, 2);	r1 = READ_ONCE(y);	r2 = READ_ONCE(z);
> > 	WRITE_ONCE(y, 1);	WRITE_ONCE(z, 1);	WRITE_ONCE(x, 1);
> > 
> > 	BUG_ON(r1 == 1 && r2 == 1 && x == 2);
> 
> But why are these useful to include in a recipes list? I would imagine
> those should cover the simple 2 threads stuff. Once you go fancy and
> need 3 CPUs I feel people had better know wth they're on about.

Release-acquire chains are good material for beginners, and they are
one of the few memory-ordering patterns that extend nicely to more than
two CPUs, hence the three-CPU examples.

> > LB is the last on on the extreme left of page 1.  "LB" stands for
> > "load buffering", and each CPU's first access is a load and last
> > access is a store:
> > 
> > 	CPU 0			CPU 1
> > 
> > 	r1 = READ_ONCE(x);	r2 = READ_ONCE(y);
> > 	WRITE_ONCE(y, 1);	WRITE_ONCE(x, 1);
> > 
> > 	BUG_ON(r1 == 1 && r2 == 1);
> 
> > MP is the second on the extreme left of page 1.  "MP" stands for "message
> > passing", and is used very heavily.  The idea is that "x" is the message
> > (sent by CPU 0), and "y" is a flag saying that the message is ready to
> > be received (by CPU 1).
> > 
> > 	CPU 0			CPU 1
> > 
> > 	WRITE_ONCE(x, 1);	r1 = READ_ONCE(y);
> > 	WRITE_ONCE(y, 1);	r1 = READ_ONCE(x);
> > 
> > 	BUG_ON(r1 == 1 && r2 == 0);
> 
> Right, these two are fairly common patterns.
> 
> > SB is the fourth on the extreme left of page 1.  "SB" stands for "store
> > buffering" because systems without store buffers won't reorder this one.
> > 
> > 	CPU 0			CPU 1
> > 
> > 	WRITE_ONCE(x, 1);	WRITE_ONCE(y, 1);
> > 	r1 = READ_ONCE(y);	r2 = READ_ONCE(x);
> > 
> > 	BUG_ON(r1 == 0 && r2 == 0);
> > 
> > Does that help?
> > 
> > Oh, and the actual recipes would include ordering as indicated by
> > the sub-bullets.
> 
> Which just generates a terrible lot of noise. Why would people be
> interested in these permutations? Why not the minimal set that makes the
> guarantee?

Hmmm...  Exactly what do you consider this minimal set to be?
Exactly which of the above scenarios would you leave out?  Are there
other scenarios that you would want to include?

> Also, none of these cover 'simple' stuff like a ring-buffer.

Control dependencies are now 'simple'?  ;-)

> So I have to ask, what is the purpose of this recipes list?

To give people common usage patterns to commit to memory, as an
alternative to running the tool every time they turn around.  For the
people who generate code quickly, frequently running the tool would be
a huge productivity hit.  But it is a probabilities game.  If a given
usage pattern is rare enough, it is better to leave it to the tool.

Also, to guide code style, urging people to use straightforward designs
instead of the much more strange ones that they might otherwise
gravitate to.

							Thanx, Paul

[toc] | [prev] | [next] | [standalone]

#1737328

On Thu, Sep 21, 2017 at 09:40:46AM -0700, Paul E. McKenney wrote:
> > Also, none of these cover 'simple' stuff like a ring-buffer.
> 
> Control dependencies are now 'simple'?  ;-)

They're not particularly harder than any other barrier I find.

But again, this comes back to the purpose of this recipes thing. I'm
thinking its meant to be how-to crib sheet for people who really don't
want to understand this stuff.

So it should include common, robust patterns and leave it at that. And
explain them through the code, not through litmus tests -- because those
are a royal friggin pain to learn to read in any case ;-)

So, 'how do I do a lockless ring-buffer' is a simple enough question
with a fairly straight forward answer. The how do I prove that answer is
correct is a whole other thing, but one I suspect most people really
don't care about.

So, once again, what is the intended purpose of his document? A gentle
introduction to memory ordering, or a crib sheet for the working code
monkey?

Because if people _want_ to understand this stuff, memory-barriers.txt
should be their document. If its become too hard to read, we should look
at fixing that, but adding another document doesn't seem like a solution
to that problem.

For the people who really don't care and just want to get their thing
done; we could have a document explaining common patterns.. maybe.

So once again, what's the purpose of this new document?

[toc] | [prev] | [next] | [standalone]

#1737861

On Fri, Sep 22, 2017 at 11:29:18AM +0200, Peter Zijlstra wrote:
> On Thu, Sep 21, 2017 at 09:40:46AM -0700, Paul E. McKenney wrote:
> > > Also, none of these cover 'simple' stuff like a ring-buffer.
> > 
> > Control dependencies are now 'simple'?  ;-)
> 
> They're not particularly harder than any other barrier I find.

Other than keeping the compiler from breaking them, I suppose.  ;-)

> But again, this comes back to the purpose of this recipes thing. I'm
> thinking its meant to be how-to crib sheet for people who really don't
> want to understand this stuff.

Other use cases include learning about memory ordering to begin with,
a convenient repository of the most common cases, and helping guide
people to the more maintainable concurrency designs.

> So it should include common, robust patterns and leave it at that. And
> explain them through the code, not through litmus tests -- because those
> are a royal friggin pain to learn to read in any case ;-)

Litmus tests are no harder to learn than is kernel code, and we do need
to allow people starting from scratch.  Plus the big advantage of the
litmus-test code is that you can check it with the tool, which is not yet
feasible for general kernel code.  Though I believe we will get there,
just not in the next 5 years.

But I agree that pointing to examples in the kernel is a good thing,
though left to myself, I would include the kernel version and not sign
up to change the examples as the kernel changes.

> So, 'how do I do a lockless ring-buffer' is a simple enough question
> with a fairly straight forward answer. The how do I prove that answer is
> correct is a whole other thing, but one I suspect most people really
> don't care about.

At least some of us had jolly better care about showing that it is
correct!  But yes, most people are going to cargo-cult known-good
patterns.  And these people are an important audience for the
recipes document.

And "how do I do a lockless ring buffer" might have a straightforward
answer now, but that code had at least its share of bugs along the way.
On the other hand, if your point is that the memory model would cover
more cases if it handled arrays, no argument here.  I would prioritize
efficiently handling locking higher, but arrays would be good.

> So, once again, what is the intended purpose of his document? A gentle
> introduction to memory ordering, or a crib sheet for the working code
> monkey?

Those are definitely two of the use cases.

> Because if people _want_ to understand this stuff, memory-barriers.txt
> should be their document. If its become too hard to read, we should look
> at fixing that, but adding another document doesn't seem like a solution
> to that problem.

There is no denying that memory-barriers.txt exceeded critical mass some
years ago (https://lwn.net/Articles/575835/), and that was before the
_acquire, _release, and _relaxed variants of atomic RMW operations,
among other things.  Plus it is incomplete, as it is essentially a
compendium of answers to specific questions that have come up over
the years.  For example, right now if you want to know how some
specific memory-ordering mechanism interacts with RCU, too bad, it
is not documented at all.  I suspect that most people do understand at
some level that synchronize_rcu() acts like a full memory barrier, and
there are the comment headers for the various grace-period functions,
but how does all this interact with (say) an atomic_add_return_acquire()
in the middle of some random RCU read-side critical section?  This sort
of thing transforms memory-barriers.txt into "Combinatorial Explosion
Я Us", hence the formal model.

This whole memory-model effort is in fact the way we are looking to fix
this.  From what I can see, memory-barriers.txt (or a document derived
from it) would have some explanation of what the hardware gets up to,
discussion of I/O barriers, care and feeding of control dependencies,
and perhaps a few other things.

> For the people who really don't care and just want to get their thing
> done; we could have a document explaining common patterns.. maybe.

And that is another use case for this recipes document.

> So once again, what's the purpose of this new document?

Let's see...

1.	By-example introduction to the most common memory-ordering
	patterns for people starting out.

2.	Repository of common cases for easy reference.

3.	Repository of good examples for "don't make up some strange
	thing if these common cases work for you" purposes.

4.	Source of cargo-culting for people who just want to get their
	job done and get on with their lives, without necessarily
	understanding the full glory of memory ordering.

This document is not expected to stand alone.  More complex cases, up
to a point, can be handled by the memory model.  And comments in the
source code are very good things as well.

Does that help, or am I missing your point?

							Thanx, Paul

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web