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

[Torvald Riegel <triegel at redhat dot com>]

On Thu, 2013-05-30 at 11:58 -0300, Alexandre Oliva wrote:
> 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, undefined order doesn't mean that there is no order.  What I
assumed it would mean is an unspecified order, so some or *a* order.
Also, it says that one function should virtually "happen after another",
which at least suggests a total order.  It could also mean just virtual
mutual exclusion (or atomicity), but that there's no total order.  I
believe it should be an order though, or otherwise a function could
happen-before itself, which would be counter-intuitive.

The fact that the order is unspecified up front isn't really a problem,
as long as, informally, it's consistent which the behavior of the
program.

> 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.

Agreed.  The standard should specify, if using concepts like atomicity,
where the boundaries of a particular atomicity guarantee are.  The
process' memory vs. memory and any I/O effects are an interesting
distinction, as you point out.  But to me, that doesn't mean you need to
generally not give out atomicity guarantees, you just have to be careful
to specify their boundaries.  Data race definitions do something similar
when they say that only a few combinations of features actually
synchronize with each other, and for everything else, all bets are off.

> > 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.

Agreed, but there are different ways to achieve not burdening one group
of users / use cases with two strong guarantees.  If it's easy and
efficient for clients/callers/... to get the stronger guarantee through
stuff they do on their own, then just giving the weak guaranteees is
fine.  But that's not the only way I believe.  If we assume that the
weaker guarantees are for the more optimized cases, then providing a
special case with weaker guarantees might make more sense.

> Second, is this really an issue of thread safety, or is it yet another
> property?

That depends on how we define thread safety! :)

To me, that falls in the overall category of how to reason about
concurrent programs, and whether you can assume that a function still
works "correctly" when used in a concurrent setting.

> 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.

We're not really in disagreement here :)  What I primarily want to see
is a proper definition of thread safety, or a set of (candidate)
criteria from which we end up one or several.  Which one(s) is then a
separate discussion, and I agree that this isn't a trivial decision.
But the status quo is, IMO, also not a reason to automatically pick the
weakest criterion, by default.

> Say, it might be the case that observe-A-if-you-observed-B (transitive
> observability?)

Note that we can have two things here, informally:
1) observe A if you observed B
2) observe A if you observed B and B observed A

Roughly, 1) is -- or is meant to mean :) -- sequential consistency, and
2) is more what you'd get from a normal acquire release.  Both can make
sense; 2) can give you the same effect but you need to know (or it needs
to be reasonable to know) whether B observed A.
(Apologies in advance if I'm not getting this 100% right; it's the end
of the day...)

> 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 ;-)

Yes.  Even further indication that "thread-safe" can be mean different
things to different people :)

> > 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.

Now I know what you meant, thanks. And I agree.

> > 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.

And I agree that one wants a standard to be minimal, and perhaps just
add remarks where deemed useful in a nonnormative note or similar -- but
if you then throw a vaguely defined thread-safety guarantee in the mix,
you better should be make it clear when it's supposed to only provide
weak safety :)

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

I wrote in my prior email:
The stronger guarantees aren't something that you can necessarily
enforce externally: You typically can if it's just about lacking memory
barriers, but if the implementation is caching internally (eg, in
thread-local vars), you can't enforce an update without the
implementation making this possible (by not caching).

In addition to that, if most reasonable implementations of a certain
thread-safe function would implicitly give the stronger guarantee (eg,
because they use locking), but they would only guarantee the weaker
guarantee, then this would force users that need the strong guarantee to
add unnecessary synchronization, slowing things down.

> >> 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.

Well, we're again back to the things I mentioned before:
1) Do you respect established inter-thread happens-before?
2) Do you establish additional inter-thread happens-before relations
that make sense for the abstract functionality that the particular
function offers?  Do you preserve transitivity of happens-before (I mean
C/C++ acquire/release vs. acquire/consume, for example)?

For example, imagine that what a thread-safe function produces, at the
abstract level, is like what a counter would produce.  Do you think it
makes sense to not give it any implied inter-thread happens-before?


Torvald