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

[Torvald Riegel <triegel at redhat dot com>]

On Sun, 2013-05-19 at 04:31 -0300, Alexandre Oliva wrote:
> On May 17, 2013, Torvald Riegel <triegel@redhat.com> wrote:
> 
> > * There's no clear definition of whether "thread-safe" is about...
> 
> There's a clear definition of the specified behavior for each function,
> so âfunction F is safe to callâ ought to mean âF behaves as specifiedâ.

The functions have sequential specifications, right?  So, if you call F
in program state A, after the function returns you have program state
A', plus some external side effects.  Thus, if you extend this to "F
behaves as specified in the presence of other threads", then you can
understand this as ending up with sequentially consistent behavior;
informally, this does what it would do in a sequential program, but now
several threads are running operations.  That would be the strong
guarantee that you don't like (but which, IMO, would often make sense,
at least as default).

One could also understand "behaves as specified" as saying that the
sequential specification is just for sequential behavior, so no
concurrency.  But then "thread-safe" doesn't make sense.

> What other constrains *need* to be set forth in the standard so as to
> allow for a broad past, present and future diversity of implementations,
> while still giving enough guarantees to users for the standard to be
> usable?

There's more about this in my other recent email reply to you, but I'll
try to give a short list here.

So, let's assume atomic and sequentially consistent is the strongest
guarantee, but we also want to allow for weaker guarantees where
necessary.

First, we need a base memory model, to actually understand how the
effects on memory relate to whatever else the program is doing with
memory.  One could try to not integrate both the programming language's
model and POSIX, but that just makes it hard to mix and match, for
example, pthread mutexes with C11 atomics.  Thus, adopting the C11 model
would likely be a good option, perhaps with something additional for
external side effects (eg, for file I/O, where it can't be *modeled* as
normal memory locations).

"No ordering guarantees", taken literally, is too weak.  Otherwise, we
wouldn't even have to guarantee that the sequential ordering guarantees
hold if a single thread uses something when no concurrent threads use
the same thing.  So, we could say "ordering guarantees like in
sequential code in the absence of concurrent operations by other
threads".  But that's not helpful either: what actually happens when
there are concurrent operations?

Thus, we need some atomicity guarantees, or we don't know whether we can
reason about concurrent calls of thread-safe functions as atomic units
or as something that interleaves in some unspecified way; in the latter
case, how could we understand the base sequential specifications of the
functions?  In cases where we don't want to have full atomicity, we need
to break down the functions into conceptual sub-parts, and specify their
interaction.

Once we know about which atomic units we want to reason about, we can
then look at the ordering guarantees again.  IOW, we can now build a
happens-before graph of our operations in the program, and now apply the
sequential specifications of our atomic operations on each vertex of the
graph.

We basically have two aspects to think about, as I wrote previously:
1) Does the thread-safe function respect ordering guarantees for memory
established elsewhere in the program and between different threads
(e.g., that affects how much thread-local caching is allowed, for
example).  IOW, are there constraints for where in the graph we can put
the operation?
2) Does the thread-safe function establish ordering guarantees for other
parts of the program (eg, other thread-safe functions)?  For example, if
something in the current thread happens after another thing, is this
ordering established also as a constraint for other threads that
communicate with the current thread?

> I've already argued in the other message I just posted that there's a
> downside to overspecifying and overconstraining implementations of a
> standard.

I don't quite know what you mean by "overspecifying"; are you referring
to making the specification not minimal in the sense of saying more than
necessary to precisely state the same thing?  If so, the only downside I
see is some redundancy.  But applied properly, some amount of redundancy
can make standards easier to read and understand.

Overconstraining in the sense of allowing very narrow behavior can be a
problem, I agree.  But underconstraining is risky too, because if users
need the narrower behavior, they have to always enforce it -- even if
it's not really necessary, and then you can end up with synchronizing
twice.  So besides the risk of creating something unusable if
underconstrained, you can also create something that's actually slower.

> Now it remains to be shown that the current amount of
> constraining in the relevant standards is insufficient, or that it would
> be beneficial overall to add more ordering and/or atomicity constraints.

First of all, the definition isn't precise, so it's not really clear
what the constraint actually is.  As I argued at the top of this email,
the weakest understanding of the constraint isn't useful, so we can't
take this as the base.
Once we know what the actual (weak) guarantees are, we can argue whether
they are too weak.  But we can also start the other way around: We can
argue where the strong guarantees are too costly, and either adapt the
garantees, or provide additional variants of the operations with weaker
guarantees.  The latter is how C++ atomic operations work, for example.

Torvald