Proposal for new memory_order_consume definition

Proposal for new memory_order_consume definition

[Paul E. McKenney]

Hello!

As requested at the October 2015 C++ Standards Committee Meeting, I have
created a single proposal for memory_order_consume in C++:

http://www2.rdrop.com/users/paulmck/submission/consume.2016.01.11b.pdf

This contains an informal description of the proposal, rough-draft
wording changes, and a number of litmus tests demonstrating how the
proposal works.

The required changes to compilers appears to be extremely small,
however, I would like to get more compiler writers' thoughts on the
pointer_cmp_eq_dep(), pointer_cmp_ne_dep(), pointer_cmp_gt_dep(),
pointer_cmp_ge_dep(), pointer_cmp_lt_dep(), and pointer_cmp_le_dep()
intrinsics that do pointer comparisons without breaking dependencies on
their first argument.  Figures 25 and 26 on page 16 demonstrate their use.
These intrinsics were suggested at the October meeting, but it would be
good to get wider feedback on them.

Note that last I checked, the Linux kernel actually does not depend
on pointer comparisons not breaking dependency chains, because all
comparisons are against NULL or a list-head structure, in which case
the pointer is not going to be dereferenced after an equals comparison.
But I do believe that some past versions of the Linux kernel have depended
on this.

Thoughts?

							Thanx, Paul

PS.  For more background information, please see:

	http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0098r0.pdf

Re: Proposal for new memory_order_consume definition

[Paul E. McKenney]

[-- Attachment #1: Type: text/plain, Size: 1587 bytes --]

On Mon, Jan 11, 2016 at 03:11:42PM -0800, Paul E. McKenney wrote:
> Hello!
> 
> As requested at the October 2015 C++ Standards Committee Meeting, I have
> created a single proposal for memory_order_consume in C++:
> 
> http://www2.rdrop.com/users/paulmck/submission/consume.2016.01.11b.pdf
> 
> This contains an informal description of the proposal, rough-draft
> wording changes, and a number of litmus tests demonstrating how the
> proposal works.
> 
> The required changes to compilers appears to be extremely small,
> however, I would like to get more compiler writers' thoughts on the
> pointer_cmp_eq_dep(), pointer_cmp_ne_dep(), pointer_cmp_gt_dep(),
> pointer_cmp_ge_dep(), pointer_cmp_lt_dep(), and pointer_cmp_le_dep()
> intrinsics that do pointer comparisons without breaking dependencies on
> their first argument.  Figures 25 and 26 on page 16 demonstrate their use.
> These intrinsics were suggested at the October meeting, but it would be
> good to get wider feedback on them.
> 
> Note that last I checked, the Linux kernel actually does not depend
> on pointer comparisons not breaking dependency chains, because all
> comparisons are against NULL or a list-head structure, in which case
> the pointer is not going to be dereferenced after an equals comparison.
> But I do believe that some past versions of the Linux kernel have depended
> on this.

And an update based on considerable off-list feedback.

More thoughts?

 							Thanx, Paul

> PS.  For more background information, please see:
> 
> 	http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/p0098r0.pdf

[-- Attachment #2: consume.2016.01.19a.pdf --]
[-- Type: application/pdf, Size: 288461 bytes --]

Proposal for new memory_order_consume definition

[Paul E. McKenney]

Hello!

A proposal (quaintly identified as P0190R0) for a new memory_order_consume
definition may be found here:

	http://www2.rdrop.com/users/paulmck/submission/consume.2016.02.10b.pdf

As requested at the October C++ Standards Committee meeting, this
is a follow-on to P0098R1 that picks one alternative and describes
it in detail.  This approach focuses on existing practice, with the
goal of supporting existing code with existing compilers.  In the last
clang/LLVM patch I saw for basic support of this change, you could count
the changed lines and still have lots of fingers and toes left over.
Those who have been following this story will recognize that this is
a very happy contrast to work that would be required to implement the
definition in the current standard.

I expect that P0190R0 will be discussed at the upcoming C++ Standards
Committee meeting taking place the week of February 29th.  Points of
discussion are likely to include:

o	May memory_order_consume dependency ordering be used in
	unannotated code?  I believe that this must be the case,
	especially given that this is our experience base.  P0190R0
	therefore recommends this approach.

o	If memory_order_consume dependency ordering can be used in
	unannotated code, must implementations support annotation?
	I believe that annotation support should be required, at the very
	least for formal verification, which can be quite difficult to
	carry out on unannotated code.  In addition, it seems likely
	that annotations can enable much better diagnostics.  P0190R0
	therefore recommends this approach.

o	If implementations must support annotation, what form should that
	annotation take?  P0190R0 recommends the [[carries_dependency]]
	attribute, but I am not picky as long as it can be (1) applied
	to all relevant pointer-like objects and (2) used in C as well
	as C++.  ;-)

o	If memory_order_consume dependency ordering can be used in
	unannotated code, how best to define the situations where
	the compiler can determine the exact value of the pointer in
	question?  (In current defacto implementations, this can
	defeat dependency ordering.  Interestingly enough, this case
	is not present in the Linux kernel, but still needs to be
	defined.)

	Options include:
	
	o	Provide new intrinsics that carry out the
		comparisons, but guarantee to preserve dependencies,
		as recommended by P0190R0 (std::pointer_cmp_eq_dep(),
		std::pointer_cmp_ne_dep(), std::pointer_cmp_gt_dep(),
		std::pointer_cmp_ge_dep(), std::pointer_cmp_lt_dep(),
		and std::pointer_cmp_le_dep()).

	o	State that -any- comparison involving an unannotated
		pointer loses the dependency.

o	How is the common idiom of marking pointers by setting low-order
	bits to be supported when those pointers carry dependencies?
	At the moment, I believe that setting bits in pointers results in
	undefined behavior even without dependency ordering, so P0190R0
	kicks this particular can down the road.  One option that
	has been suggested is to provide intrinsics for this purpose.
	(Sorry, but I forget who suggested this.)

Thoughts?

							Thanx, Paul