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

[Alexandre Oliva <aoliva at redhat dot com>]

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

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

It's not so much that I don't like it, but that I don't quite see that
it's what's expected, or even possible to achieve.  See below.

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

Agreed.  Therefore, not what I meant ;-)

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

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

I don't see how things could work this way.  See, if the standard were
to say âall callers of function foo must pay the price of a globally
sequential execution modelâ, it would rule out [the possible gains out
of] the weaker guarantees to boot.

> "No ordering guarantees", taken literally, is too weak.

Since we've determined âordering guaranteesâ seems to mean different
things for each of us, how about using such terms as âatomicityâ,
âconsistencyâ, and âisolationâ?  (I guess we can do away with
âdurabilityâ from transactions' ACID)

> Thus, we need some atomicity guarantees,
                     ^^^^^^^^^
Glad you liked the idea! :-)

> 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

except that now we're both using âatomicityâ in a different sense from
the one in ACID; it's not all-or-nothing we've both spoke of (you above,
I in my previous message), but rather isolation, right?

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

It's harder than that, really.  First of all, we pretty much have to
give up atomicity (not having partial effects observable) given the
buffered printf example I gave in my previous email.

Further evidence that mt-safety is not about atomicity is that a
function can be mt-safe but not as-safe or ac-safe, and these two forms
of safety, although orthogonal, have far more to do with atomicity: a
function can only be safe to call from an async signal handler if data
structures it manipulates will always be found in a consistent state,
and it can only be safe to call in a thread that can be cancelled
asynchronously if it won't leave an inconsistent state behind.

AC-Safety requires (*) that (a) the function manipulates data structures
in such a way that each state change be atomic and advance from one
consistent state to another, so that, if its execution is canceled, the
state will be consistent, or (b) the function disables async
cancellation around any state changes that don't satisfy this property.

(*) I state a requirement, not necessarily sufficient condition for the
property to be met.

AS-Safety requires that *all* functions that manipulates the data
structures it uses do so such that (a) each state change is atomic,
advancing from one consistent state to another (so that the function, if
called from an async signal handler, doesn't encounter an inconsistent
state), and don't âcacheâ information from one transformation to another
in such a way that they'd conflict with state changes introduced by an
async call of the function; or (b) async signals are disabled around any
state changes that don't satisfy this property.

So, you see, although these have pretty stringent atomicity
requirements, even these can be relaxed by delaying asynchronous
interactions.  Thread safety, OTOH, doesn't require any such atomicity:
functions can be thread safe and yet have intermediate states observed
by other threads, but also (and more importantly) by asynchronous signal
handlers or when the thread running them is canceled.

Now, you see that consistency is a term I've used in requirements of
AC-Safety and AS-Safety; to me, they're just as essential for MT-Safety
too.  As for isolation, one might be tempted to say this is THE driving
requirement when it comes to thread-safety.

However, once you consider that many calls have multiple side effects
that may be observed externally before the function completes, you
realize isolation can't really be the point; IMHO, first and foremost,
consistency is.  I'm even inclined to narrow it to *internal*
consistency: internal, opaque objects must remain consistent, whereas
user-exposed objects need not.

Consider memset, for example.  (I hope) nobody would expect it to set
multiple bytes, words or cache lines atomically, or in ways that would
prevent other threads from observing partial changes.  But it ought to
set each of the bytes in the given range to the chosen value.  You can't
even assume that, when it finishes, all bytes will still hold that
value, but the expected behavior will have been exercised.  Say, another
thread may have run memset on an overlapping range, setting bytes to a
different value, and then you might end up with different values in
different bytes in the overlapping range.  If each one goes (for
whatever reason) in opposite directions, you could even end up with
results that shouldn't be possible if isolation (serializability) was
satisfied.  And yet, memset is MT-Safe under POSIX.

Now consider printf (also MT-Safe under POSIX), with an stream in
default (internal locking) mode: no matter how long the string to be
written to the output stream is, other operations with that stream are
not to be interspersed.  However, if you pass a format string to printf
that is modified by another thread while printf runs, well, you may get
surprising results.  Likewise, if you modify concurrently a string that
was to be printed with %s, nothing is required of printf WRT printing a
âconsistentâ version of that string, whatever that means.  So, again, it
seems to me that the driving requirement is not isolation, but rather
internal consistency: the stream object, opaque to users, is kept
consistent, whereas strings provided by the user may mess things up if
modified concurrently, even if modified using standard MT-Safe
interfaces such as strcpy or sprintf!

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

These bits seem to be the most relevant to answer your questions:

http://pubs.opengroup.org/onlinepubs/9699919799/xrat/V4_xsh_chap02.html#tag_22_02_09_08
http://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap03.html#tag_03_398
http://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap04.html#tag_04_11

What I get from it is that memory is shared but writes must not be
concurrent with other reads or writes, and the various synchronization
primitives are *the* means for memory synchronization (memory barriers).

Now, I don't see that functions that are not listed in the memory
synchronization section imply any kind of inter-thread memory
synchronization, so events in different threads remain âconcurrentâ (in
the distributed systems sense) in the absence of any of those memory
synchronization calls.  In a sense, they are the one sure source of
happens-before ordering.  Presumably, writing to a pipe and reading from
its other end introduces happens-before and hopefully *also* implies
memory synchronization, to get the written data to the other end of the
pipe, but this doesn't seem to be strictly stated.

Anyway, the specified âmemory synchronizationâ model appears to imply
something along the lines of âpush all local changes to global memory
and clear all local cachesâ, which, to me, implies (a) happens-before,
as introduced by memory synchronization primitives, is transitive, and
(ii) there's no limit to thread-local caching between memory
synchronization operations, but no requirement that there be any caching
either.

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

I meant going into an unnecessary amount of detail, which might end up
limiting alternate implementations.  It overlaps with overconstraining
somewhat, but by the latter I meant imposing too-strict requirements.  I
guess the distinction between what I meant by both terms has more to do
with internal implementation details vs externally visible interfaces.

> 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

Unless both possibilities are specified (think putc_unlocked vs putc).
If both are recognized as useful, they should both be available, either
as primitives, or as easy composition of primitives.  If only one of
them is, only that one should be standardized, and that one will be
neither over nor underconstraining, right?

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