Skip to contentSkip to conversation

Memory model, using ISO C++11 atomic ops

Ksummit-discuss David Howells 10 participants 15 messages Jul 22, 2016 – Aug 3, 2016

lore
Share & tools
lore
#0 lore raw

Earlier this year we had a discussion of the possibilities of using ISO C++11 atomic operations inside the kernel to implement kernel atomic ops of sorts various, posted here:

	Subject: [RFC PATCH 00/15] Provide atomics and bitops implemented with ISO C++11 atomics
	Date: Wed, 18 May 2016 16:10:37 +0100

Is it worth getting together to discuss these in person in one of the tech slots - especially if there are some gcc or llvm people available at plumbers who could join in?

Further, Paul McKenney and others are assembling a memory model description. Do we want to consider loosening up the kernel memory model?

Currently, for example, locks imply semi-permeable barriers that are not tied to the lock variable - but, as I understand it, this may not hold true on all arches, and on those arches an extra memory barrier would be required. For example, { LOCK(A), UNLOCK(A), LOCK(B), UNLOCK(B) } would not imply a full memory barrier in the middle.

Also, we have read and write memory barrier constructs - but not all CPUs have such things, some instead have acquire and release. Would it be worth having higher level constructs that encapsulate what you're trying to do and select the most appropriate barrier from the available choices? For instance, we have a fair few circular buffers, with linux/circ_buf.h providing some useful bits. Should we provide circular buffering barrier constructs?

If we do this, Will Deacon, Peter Zijlstra and Paul McKenney should definitely be there. I would suggest Jakub Jelinek and Ramana Radhakrishnan as gcc representatives. I don't know anyone from LLVM.

David

#1 lore raw
Quoted 7 lines · David Howells

Earlier this year we had a discussion of the possibilities of using ISO C++11 atomic operations inside the kernel to implement kernel atomic ops of sorts various, posted here:

	Subject: [RFC PATCH 00/15] Provide atomics and bitops implemented with ISO C++11 atomics
	Date: Wed, 18 May 2016 16:10:37 +0100
Quoted 6 lines

Is it worth getting together to discuss these in person in one of the tech slots - especially if there are some gcc or llvm people available at plumbers who could join in?

Further, Paul McKenney and others are assembling a memory model description.

We are attempting to automate memory-barriers.txt, so that you could provide fragments of C code, and the tool would tell you whether a given outcome happens always, sometimes, or never. The current prototype handles memory accesses, memory barriers, and RCU, but not yet locking or read-modify-write atomics (though there is some vestigal support for RMW atomics). We are currently playing whack-a-mole with odd corner cases of various architectures' memory models. We are therefore also working on ways of handling the resulting uncertainty. Good clean fun! ;-)

Quoted 7 lines

Do we want to consider loosening up the kernel memory model?

Currently, for example, locks imply semi-permeable barriers that are not tied to the lock variable - but, as I understand it, this may not hold true on all arches, and on those arches an extra memory barrier would be required. For example, { LOCK(A), UNLOCK(A), LOCK(B), UNLOCK(B) } would not imply a full memory barrier in the middle.

Agreed, the current version of memory-barriers.txt documents the fact that an unlock/lock sequence does not imply a full memory barrier:

Similarly, the reverse case of a RELEASE followed by an ACQUIRE does not imply a full memory barrier.

If we are going to talk about changing this, we should most definitely include a powerpc arch maintainer.

Quoted 11 lines

Also, we have read and write memory barrier constructs - but not all CPUs have such things, some instead have acquire and release. Would it be worth having higher level constructs that encapsulate what you're trying to do and select the most appropriate barrier from the available choices? For instance, we have a fair few circular buffers, with linux/circ_buf.h providing some useful bits. Should we provide circular buffering barrier constructs?

If we do this, Will Deacon, Peter Zijlstra and Paul McKenney should definitely be there. I would suggest Jakub Jelinek and Ramana Radhakrishnan as gcc representatives. I don't know anyone from LLVM.

Alan Stern should be included, as he is the author of the most recent version of the prototype formalized memory model (including the current extremely nice formal model of RCU!), Luc Maranget as the author of the previous version, Jade Alglave as author of the first version and founder of this project, and Andrea Parri for his many contributions to recent models.

Shouldn't we also include experts on other SMP architectures?

Thanx, Paul

#2 lore raw
Quoted 15 lines · Paul E. McKenney
Quoted 7 lines · David Howells

Earlier this year we had a discussion of the possibilities of using ISO C++11 atomic operations inside the kernel to implement kernel atomic ops of sorts various, posted here:

	Subject: [RFC PATCH 00/15] Provide atomics and bitops implemented with ISO C++11 atomics
	Date: Wed, 18 May 2016 16:10:37 +0100
Quoted 6 lines

Is it worth getting together to discuss these in person in one of the tech slots - especially if there are some gcc or llvm people available at plumbers who could join in?

Further, Paul McKenney and others are assembling a memory model description.

Quoted 8 lines

We are attempting to automate memory-barriers.txt, so that you could provide fragments of C code, and the tool would tell you whether a given outcome happens always, sometimes, or never. The current prototype handles memory accesses, memory barriers, and RCU, but not yet locking or read-modify-write atomics (though there is some vestigal support for RMW atomics). We are currently playing whack-a-mole with odd corner cases of various architectures' memory models. We are therefore also working on ways of handling the resulting uncertainty. Good clean fun! ;-)

Consider me interested in this discussion, patches, etc.

Luis

#3 lore raw
Quoted 25 lines · Luis R. Rodriguez
Quoted 15 lines · Paul E. McKenney
Quoted 7 lines · David Howells

Earlier this year we had a discussion of the possibilities of using ISO C++11 atomic operations inside the kernel to implement kernel atomic ops of sorts various, posted here:

	Subject: [RFC PATCH 00/15] Provide atomics and bitops implemented with ISO C++11 atomics
	Date: Wed, 18 May 2016 16:10:37 +0100
Quoted 6 lines

Is it worth getting together to discuss these in person in one of the tech slots - especially if there are some gcc or llvm people available at plumbers who could join in?

Further, Paul McKenney and others are assembling a memory model description.

Quoted 8 lines

We are attempting to automate memory-barriers.txt, so that you could provide fragments of C code, and the tool would tell you whether a given outcome happens always, sometimes, or never. The current prototype handles memory accesses, memory barriers, and RCU, but not yet locking or read-modify-write atomics (though there is some vestigal support for RMW atomics). We are currently playing whack-a-mole with odd corner cases of various architectures' memory models. We are therefore also working on ways of handling the resulting uncertainty. Good clean fun! ;-)

Quoted 2 lines

Consider me interested in this discussion, patches, etc.

Same here.
I have been playing around with RCUs and memory barriers quite a lot recently, and found some really 'odd' use-cases in the kernel which would benefit from improvements here.

Cheers,

Hannes

Signature · 5 lines
Dr. Hannes Reinecke		               zSeries & Storage
[email protected]			               +49 911 74053 688
SUSE LINUX GmbH, Maxfeldstr. 5, 90409 Nürnberg
GF: F. Imendörffer, J. Smithard, D. Upmanyu, G. Norton
HRB 21284 (AG Nürnberg)
#4 lore raw
Quoted 3 lines · Hannes Reinecke

I have been playing around with RCUs and memory barriers quite a lot recently, and found some really 'odd' use-cases in the kernel which would benefit from improvements here.

Could you post one or two examples? It would be interesting to see what they involve.

Alan Stern

#5 lore raw
Quoted 8 lines · Alan Stern
Quoted 3 lines · Hannes Reinecke

I have been playing around with RCUs and memory barriers quite a lot recently, and found some really 'odd' use-cases in the kernel which would benefit from improvements here.

Could you post one or two examples? It would be interesting to see what they involve.

I would be intersted as well!

Thanx, Paul

#6 lore raw
Quoted 12 lines · On Tue, 26 Jul 2016 06:35:51 -0700 "Paul E. McKenney"…
Quoted 8 lines · Alan Stern
Quoted 3 lines · Hannes Reinecke

I have been playing around with RCUs and memory barriers quite a lot recently, and found some really 'odd' use-cases in the kernel which would benefit from improvements here.

Could you post one or two examples? It would be interesting to see what they involve.

I would be intersted as well!

Me too, as tracing plays a bit of magic with memory models as well.

-- Steve

#7 lore raw
In reply to Alan Stern
Quoted 9 lines · Alan Stern
Quoted 3 lines · Hannes Reinecke

I have been playing around with RCUs and memory barriers quite a lot recently, and found some really 'odd' use-cases in the kernel which would benefit from improvements here.

Could you post one or two examples? It would be interesting to see what they involve.

I have been working on a performance regression when calling 'dm_suspend/dm_resume' repeatedly for several (hundreds) devices. That boiled down to the patch introducing srcu in the device mapper core
with commit 83d5e5b0af907 (dm: optimize use SRCU and RCU).
Looking at it the code they do things like:

	set_bit(DMF_BLOCK_IO_FOR_SUSPEND, &md->flags);
	if (map)
		synchronize_srcu(&md->io_barrier);

where the srcu is used to ensure the code has left the critical sections. However, if the memory pointed to by the srcu isn't actually freed why we could easily drop the 'synchronize_srcu' call. But that would require that
a) the set_bit() above is indeed atomic
and
b) there's no need to call 'synchronize_rcu' if you're not actually freeing memory but rather fiddle pointers.
Both are somewhat shady areas where the documentation nor usage reveals some obvious insights.

On another example I've been doing performance patches to the lpfc driver (cf my talk at VAULT this year), where I've replaced most spinlocks with atomics and bitops. Which should work as well, only that it's still a bit unclear to me
if an when you need barriers in addition to atomic resp bitops.
And if you need barriers, which variant would be most appropriate?
The __before or the __after variant?
Also, what happens to bitops on bitfields longer than an unsigned long?
Are they still atomic?

Cheers,

Hannes

Signature · 5 lines
Dr. Hannes Reinecke		               zSeries & Storage
[email protected]			               +49 911 74053 688
SUSE LINUX GmbH, Maxfeldstr. 5, 90409 Nürnberg
GF: F. Imendörffer, J. Smithard, D. Upmanyu, G. Norton
HRB 21284 (AG Nürnberg)
#8 lore raw
Quoted 20 lines · Hannes Reinecke
Quoted 9 lines · Alan Stern
Quoted 3 lines · Hannes Reinecke

I have been playing around with RCUs and memory barriers quite a lot recently, and found some really 'odd' use-cases in the kernel which would benefit from improvements here.

Could you post one or two examples? It would be interesting to see what they involve.

I have been working on a performance regression when calling 'dm_suspend/dm_resume' repeatedly for several (hundreds) devices. That boiled down to the patch introducing srcu in the device mapper core with commit 83d5e5b0af907 (dm: optimize use SRCU and RCU). Looking at it the code they do things like:

	set_bit(DMF_BLOCK_IO_FOR_SUSPEND, &md->flags);
	if (map)
		synchronize_srcu(&md->io_barrier);
Quoted 10 lines

where the srcu is used to ensure the code has left the critical sections. However, if the memory pointed to by the srcu isn't actually freed why we could easily drop the 'synchronize_srcu' call. But that would require that
a) the set_bit() above is indeed atomic
and
b) there's no need to call 'synchronize_rcu' if you're not actually freeing memory but rather fiddle pointers.
Both are somewhat shady areas where the documentation nor usage reveals some obvious insights.

The set_bit() function is guaranteed to execute atomically, but it does not guarantee any ordering against prior accesses. The synchronize_rcu() does provide ordering against the set_bit(), to subsequent accesses are covered, but only in the case where "map" is non-zero.

For RCU, it does depend on the use case. For example, there are some rare but real cases where synchronize_rcu() is required even if you are not freeing memory:

https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf

Quoted 5 lines

On another example I've been doing performance patches to the lpfc driver (cf my talk at VAULT this year), where I've replaced most spinlocks with atomics and bitops.
Which should work as well, only that it's still a bit unclear to me if an when you need barriers in addition to atomic resp bitops.

If the bitop returns a value, you don't need additional barriers. Otherwise ...
... you need smp_mb__before_atomic() to order prior accesses
against the bitop and smp_mb__after_atomic() to order subsequent accesses against the bitop. If you need the bitop to be ordered against both prior and subsequent accesses, then you need both smp_mb__before_atomic() and smp_mb__after_atomic().

Quoted 2 lines

And if you need barriers, which variant would be most appropriate? The __before or the __after variant?

... you need smp_mb__before_atomic() to order prior accesses
against the bitop and smp_mb__after_atomic() to order subsequent accesses against the bitop. If you need the bitop to be ordered against both prior and subsequent accesses, then you need both smp_mb__before_atomic() and smp_mb__after_atomic().

Quoted 4 lines

Also, what happens to bitops on bitfields longer than an unsigned long? Are they still atomic?

From what I can see, yes, sort of. The "sort of" part is due to the fact

that bitops on widely separated bits would be would avoid interfering with each other, but on the other hand, there would be no cause-and-effect relationship between them, either. Furthermore, processes reading the bits set might disagree on the order in which they were set.

All that aside, please note that the initial memory model is limited to memory reference, barriers, and RCU. We do not yet have locking or read-modify-write atomic operations. We have to start somewhere!

Thanx, Paul

#9 lore raw
In reply to David Howells
Quoted 3 lines · David Howells

If we do this, Will Deacon, Peter Zijlstra and Paul McKenney should definitely be there.  I would suggest Jakub Jelinek and Ramana Radhakrishnan as gcc representatives.  I don't know anyone from LLVM.

I'd like to be there too.

Cheers,
Ben.

#10 lore raw
In reply to David Howells
Quoted 2 lines · David Howells

Further, Paul McKenney and others are assembling a memory model description. Do we want to consider loosening up the kernel memory model?

It's not clear that 'loosening up' is what we're after.

In Seoul last year, weren't we looking at things like readl_relaxed() and lamenting the fact that they do actually still have strong enough requirements that they can't *really* be very relaxed on Power and ARM64 at all, because they're basically being used with the assumption of Intel-like semantics.

The cheap answer is "well, it sucks to be on POWER or ARM64 because then readl_relaxed() has to be as slow as readl() is".

But it would be good to follow up on that properly, and maybe introduce a variant which *can* be implemented across more architectures.

Is that what Paul is working on, that you mention above?

Signature · 1 line
dwmw2
#11 lore raw
Quoted 5 lines · David Woodhouse

In Seoul last year, weren't we looking at things like readl_relaxed() and lamenting the fact that they do actually still have strong enough requirements that they can't *really* be very relaxed on Power and ARM64 at all, because they're basically being used with the assumption of Intel-like semantics.

I don't recall that. Possibly that was a track I wasn't in.

Quoted 2 lines

The cheap answer is "well, it sucks to be on POWER or ARM64 because then readl_relaxed() has to be as slow as readl() is".

Does the memory model for CPU/device interactions have to be the same as that for CPU/CPU interactions? I guess with respect to locks, it does so that two processors who both want to access a device don't trample over each other.

Quoted 1 line

Is that what Paul is working on, that you mention above?

Paul is working on a general overall description.

David

#12 lore raw
In reply to David Woodhouse
Quoted 6 lines · David Woodhouse
Quoted 2 lines · David Howells

Further, Paul McKenney and others are assembling a memory model description. Do we want to consider loosening up the kernel memory model?

It's not clear that 'loosening up' is what we're after.

Quoted 8 lines

In Seoul last year, weren't we looking at things like readl_relaxed() and lamenting the fact that they do actually still have strong enough requirements that they can't *really* be very relaxed on Power and ARM64 at all, because they're basically being used with the assumption of Intel-like semantics.

The cheap answer is "well, it sucks to be on POWER or ARM64 because then readl_relaxed() has to be as slow as readl() is".

I wasn't in Seoul, but I think some people got the wrong end of the stick about the relaxed accessors and I'd be interested in trying to address some of that, at least from the arm64 point-of-view. Paul has been busy writing something up a summary for lwn, but I don't think it's quite ready yet.

Having said that, the memory model work that I'm aware of focusses completely on SMP synchronisation and I don't think it's particularly helpful to throw I/O into the mix just yet.

Will

#13 lore raw
In reply to David Woodhouse
Quoted 5 lines · David Woodhouse
Quoted 2 lines · David Howells

Further, Paul McKenney and others are assembling a memory model description. Do we want to consider loosening up the kernel memory model?

It's not clear that 'loosening up' is what we're after.

Linus (who should also very much be present for this) always argues against relaxing ordering.

#14 lore raw
Quoted 9 lines · Peter Zijlstra
Quoted 5 lines · David Woodhouse
Quoted 2 lines · David Howells

Further, Paul McKenney and others are assembling a memory model description. Do we want to consider loosening up the kernel memory model?

It's not clear that 'loosening up' is what we're after.

Linus (who should also very much be present for this) always argues against relaxing ordering.

Even if he had an inexplicable change in heart, how on Earth do you go about validating the existing codebase against a new memory model? It's one thing to show that the relaxation is strictly a relaxation (and therefore the existing backend implementations remain sound), but quite another to show that locking implementations don't fall apart, or the guarantees that no longer hold aren't relied upon someplace.

One might consider adding more atomic operations. For example, the release/acquire stuff we grew recently is "weaker" than full fences but, unlike the C11 atomics, the release/acquire primitives complement full fences. Conversely, having two sets of fences (C11 and kernel) or two sets of release/acquire, each with subtly different semantics sounds like an awful maintainance burden and not somewhere we should be going.

That's why I'd be interested in building kernel-compatible operations using C11 atomics (relaxed accesses and fences) for asm/generic, but not more than that, at least outside of arch/*.

Will