Re: Thread-, Signal- and Cancellation-safety documentation

[Alexandre Oliva <aoliva at redhat dot com>]

On May 26, 2013, Torvald Riegel <triegel@redhat.com> wrote:

> It wouldn't need indirections through pointers in the internal
> representation, if that's what you're worrying about.

I was just going along with the context, where that need was stated.

> At least http://www.unix.org/whitepapers/reentrant.html states:

> In POSIX.1c, a "reentrant function" is defined as a "function whose
> effect, when called by two or more threads, is guaranteed to be as if
> the threads each executed the function one after another in an undefined
> order, even if the actual execution is interleaved" (ISO/IEC
> 9945:1-1996, Â2.2.2).

> That hints at some (total?) order.

Err...  Do I misread âundefined orderâ there? :-)

That's what I meant by âno ordering guaranteesâ.  It looks like we're
suffering out of differences in the meanings of terms.

To me, ordering requirements has to do establishing a happens-before
relationship.

Atomicity requirements to me are something else, more along the lines of
the âreentrant functionâ definition above.  However, I believe it may
have been discarded in favor of something more lax because many internal
implementation details that *do* introduce externally-visible effects
would expose the non-atomic nature of the implementations.  For example,
writing even a small string to a buffered stream may cause its buffer to
fill up, be flushed to the output file or pipe, and then start getting
filled again with the rest of the string.  If printf was required to be
atomic, such an implementation would not be permitted, because other
threads (e.g. reading from the other end of the pipe) could be able to
observe part of the output come out of the pipe and then note that the
output stream remains locked, thus proving printf is not atomic.

> There must be *some* ordering guarantees.  [...]  in the
> absence of actions by other threads, it should at least have the
> ordering guarantees of a sequential program.

Sure, local sequential ordering is implied.

I guess that was my distributed systems background speaking ;-)

Comparing with communication events, there aren't very many internal
events that are relevant enough to tick the virtual clock,

> having something in a local CPU cache would be fine because as soon as
> we synchronize with other CPUs, we'll get an update for the cache
> line; but caching in a separate thread-local variable would not

*nod*

> Second, we need to decide whether we want to give additional ordering
> guarantees when we produce a value and another thread consumes it.  For
> example, if we run operations A and B, both which produce a value or
> some other observable effect, and run B after A: is every other thread
> that observes B's results also guaranteed to observe A's result as well?
> There's no single right answer to this.  It's likely easier and less
> error-prone for programmers if A is always observed as well by the other
> thread, but it can require a bit more runtime overheads on some
> architectures.  But we need to be clear about what we guarantee, because
> depending on one's mindset, both options can be intuitive.

Understood and agreed.  These are properties that can be important to
guarantee for some applications, and not for others.  So, if there are
other means to make such guarantees that don't require the standard to
mandate it for everyone, even those who don't require it and would be
better off without the overhead, that's probably the way to go.

Second, is this really an issue of thread safety, or is it yet another
property?  If such guarantees were to be required for thread safety, and
given that posix mandates thread safety for nearly all functions, the
standard would be effectively imposing the additional runtime overhead.
Maybe it makes sense for it to do so, but I wouldn't throw that into the
âthread safetyâ property without evidence that this was understood,
assessed, considered worth the cost and agreed upon.

Say, it might be the case that observe-A-if-you-observed-B (transitive
observability?) is a prerequisite for properties that âthread safetyâ
intended to offer.  Then, it might even make sense to change the mandate
that (nearly) all functions be thread-safe, maintaining this requirement
where it is actually mandatory and useful, and explicitly relaxing it in
other cases.  Now, it might be that one of these two classes inherits
the term âthread safeâ, and the other gets another term to refer to it,
but I can't even guess which one should be which ;-)

> The fact that we are discussing what the standard actually means is an
> indication that the definition is not clear enough.

or that some people wish it covered more ground that it chose not to,
but didn't explicitly say so, because not saying it's covered should
suffice to imply it's not ;-)

But yeah, no dispute that there is some room for differences of
understanding, and that may be a problem.

> C++ is, based on the opinions of some committee members (meaning I don't
> know whether that's an agreed-upon decision), trying to typically give
> stronger ordering guarantees (like in the observe-A-if-you-observed-B
> example above).

It surely makes for a more intuitive programming model.  Heck, I believe
even under relativity, where two observers might disagree as to which of
two events happened first, if they both agree A happened before B and B
happened before C, they can't disagree that A happened before C.

>> In any case, since there isn't any ordering established in the
>> program itself (no operations that establish happens-before), any
>> such ordering would have to do with implementation details of the
>> hardware that would enable such an ordering to be established.

> I'm not quite sure I understand what you're saying, but the base
> shouldn't be a hardware's memory model, but a more general-purpose
> memory model such as C11's memory model.

I was saying hardware details would be the only possible source of
ordering for two events that are otherwise unordered.  I guess it's my
distributed systems background speaking again: in the absence of
communication between processes, events in different âprocessesâ are
effectively concurrent.  Only hardware implementation details (say cache
overflows) could provide communication between the processes (should I
say processors :-) so as to establish ordering.

> I would think it should have a memory model that is compatible with
> C11's.

Better than defining a memory model that might conflict with other
standards is to follow existing POSIX practice of deferring to the
underlying standards.  Many functions in POSIX are specified with the
explicit note that they intend to be equivalent to the C standard.

> It's fine to give just weak guarantees, but then you need to say this
> explicitly *and* clarify how users can achieve the stronger guarantees.

I don't buy the âhave to say this explicitlyâ.  Formally speaking,
unless some property is defined so as to encompass another, it should be
assumed that the other is not implied.

As for stronger guarantees, there are standardized means in POSIX for
inter-thread synchronization.  Does that not suffice?

>> IMHO, POSIX specifies operations that establish happens-before
>> relationships, and operations that are to be atomic, but those are the
>> exception, rather than the rule.  For everything else, no ordering
>> requirements exist, even for thread-safe functions, and IMHO that's how
>> it should be.

> I've argued above that we at least need some ordering guarantees. Do you
> mean "no ordering requirements" literally, or could you come up with a
> precise definition of the minimum set of ordering guarantees you want?

I mean no implied inter-thread happens-before.  Synchronization
primitives and externally observable properties provide for that.

> IMHO, it's always a trade-off between making stuff fast or easier to
> use.

*nod*

-- 
Alexandre Oliva, freedom fighter    http://FSFLA.org/~lxoliva/
You must be the change you wish to see in the world. -- Gandhi
Be Free! -- http://FSFLA.org/   FSF Latin America board member
Free Software Evangelist      Red Hat Brazil Compiler Engineer