* Paul E. McKenney:
quoted
quoted
Yes, I know, we for sure have conflicting constraints on "reasonable"
on copy on this email. What else is new? ;-)
I could imagine a tag of some sort on the load and store, linking the
operations that needed to be ordered. You would also want that same
tag on any conditional operators along the way? Or would the presence
of the tags on the load and store suffice?
If the load is assigned to a local variable whose address is not taken
and which is only assigned this once, it could be used to label the
store. Then the compiler checks if all paths from the load to the
store feature a condition that depends on the local variable (where
qualifying conditions probably depend on the architecture). If it
can't prove that is the case, it emits a fake no-op condition that
triggers the hardware barrier. This formulation has the advantage
that it does not add side effects to operators like <. It even
generalizes to different barrier-implying instructions besides
conditional branches.
So something like this?
tagvar = READ_ONCE(a);
if (tagvar)
WRITE_ONCE_COND(b, 1, tagvar);
Yes, something like that. The syntax only makes sense if tagvar is
assigned only once (statically).
(This seems to me to be an eminently reasonable syntax.)
Or did I miss a turn in there somewhere?
The important bit is that the compiler emits the extra condition when
necessary, and the information in the snippet above seems to provide
enough information to optimize it away in principle, when it's safe.
This assumes that we can actually come up with a concrete model what
triggers the hardware barrier, of course. For example, if tagvar is
spilled to the stack, is it still possible to apply an effective
condition to it after it is loaded from the stack? If not, then the
compiler would have to put in a barrier before spilling tagvar if it
is used in any WRITE_ONCE_COND statement.
On Thu, Oct 14, 2021 at 08:19:54PM +0200, Florian Weimer wrote:
* Paul E. McKenney:
quoted
quoted
quoted
Yes, I know, we for sure have conflicting constraints on "reasonable"
on copy on this email. What else is new? ;-)
I could imagine a tag of some sort on the load and store, linking the
operations that needed to be ordered. You would also want that same
tag on any conditional operators along the way? Or would the presence
of the tags on the load and store suffice?
If the load is assigned to a local variable whose address is not taken
and which is only assigned this once, it could be used to label the
store. Then the compiler checks if all paths from the load to the
store feature a condition that depends on the local variable (where
qualifying conditions probably depend on the architecture). If it
can't prove that is the case, it emits a fake no-op condition that
triggers the hardware barrier. This formulation has the advantage
that it does not add side effects to operators like <. It even
generalizes to different barrier-implying instructions besides
conditional branches.
So something like this?
tagvar = READ_ONCE(a);
if (tagvar)
WRITE_ONCE_COND(b, 1, tagvar);
Yes, something like that. The syntax only makes sense if tagvar is
assigned only once (statically).
quoted
(This seems to me to be an eminently reasonable syntax.)
Or did I miss a turn in there somewhere?
The important bit is that the compiler emits the extra condition when
necessary, and the information in the snippet above seems to provide
enough information to optimize it away in principle, when it's safe.
This assumes that we can actually come up with a concrete model what
triggers the hardware barrier, of course. For example, if tagvar is
spilled to the stack, is it still possible to apply an effective
condition to it after it is loaded from the stack? If not, then the
compiler would have to put in a barrier before spilling tagvar if it
is used in any WRITE_ONCE_COND statement.
In all the weakly ordered architectures I am aware of, spilling to
the stack and reloading preserves the ordering. The ordering from
the initial load to the spill is an assembly-language data dependency,
the ordering from the spill to the reload is single-variable SC, and
the ordering beyond that is the original control dependency.
Thanx, Paul
On Thu, Oct 14, 2021 at 5:10 PM Paul E. McKenney [off-list ref] wrote:
In all the weakly ordered architectures I am aware of, spilling to
the stack and reloading preserves the ordering. The ordering from
the initial load to the spill is an assembly-language data dependency,
the ordering from the spill to the reload is single-variable SC, and
the ordering beyond that is the original control dependency.
I think the thing about a control dependency is that any way to
optimize it differently only strengthens it.
That was very different from the problems we had with describing the
RCU dependencies - they were data dependencies, and if they could ever
be turned into control dependencies, they would have been weakened.
But the only way to really weaken a control dependency and the write
behind it is to get rid of it entirely.
So turning it into a data dependency (by turning the conditional into
a 'select' instruction, for example) only makes it stronger. And no
amount of register spilling or data movement any other way makes any
difference.
That's why all the examples of what could go wrong were about same
code on both sides of the conditional, which allowed removing the
conditional entirely (or at least moving parts of the "protected" code
to before it.
(The other way to remove the conditional is to just optimize away the
conditional itself, but that's defeated by "READ_ONCE()" being part of
the source of the conditional, and any data or control dependency from
that fundamental "the compiler cannot remove this logic" is always
sufficient).
So I really don't think this is even about "any weakly ordered
architecture". I think this is fundamentally about causality. You
simply cannot make a conditional write visible before the condition
has been resolved, and resolving the condition requires the read to
have happened.
This is not open to "speculation". Not by hardware, not by compilers.
There are only two ways you can break this fundamental construct:
- outright bugs
- a perfect oracle
And honestly, if you have a perfect oracle, you're better off making
money playing the lotto than you would ever be doing hardware or
software development, so that second option isn't really even
interesting.
Linus