This is the mail archive of the libc-alpha@sourceware.org mailing list for the glibc project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


On Thu, 2013-05-30 at 16:57 -0300, Alexandre Oliva wrote:
> 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.

Why?  You could still have functions with more relaxed guarantees.

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

Atomicity doesn't refer to quite the same thing in the database and
shared-memory synchronization literature.  For databases, it's more
all-or-nothing in the presence of all kinds of failures, whereas for
shared-mem sync it's rather "do all those ops as one (virtually)
indivisible step".

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

Not quite.  I'm referring to the shared-mem sync atomicity...

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

Yes, as indivisible steps.

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

That's fine too.  It could be atomic if you use the stream functions and
not atomic at all if reading from a file descriptor that the stream
sends its output to.  Or it could say that the latter is just undefined
from a thread safety POV.

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

That's one implementation consideration, but I believe the effect can
still be described as whether things are still atomic in faces of async
signals.  It's just that it isn't quite like just another thread.  But I
don't see a principle conflict here.

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

That's more like the database-style atomicity.  There's something about
the shared-mem sync atomicity too because it's asynchronous
cancellation, but at the code this is more about handling a failure.

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

To be precise, that's one possible implementation possibility?  It could
also be the case that the function can do what it wants because all the
observers of it's effects could make sense of the cancelled garbage.

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

That sounds close to an atomicity constraint, or at least an ordering
constraint on the parts comprising the function.

> So, you see, although these have pretty stringent atomicity
> requirements, even these can be relaxed by delaying asynchronous
> interactions.

That doesn't conflict with atomicity.  If we introduce blocking behavior
(e.g., delaying async stuff), then we change progress guarantees, but it
doesn't change the atomicity guarantee (which is a safety guarantee).

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

You can't just argue that thread safety doesn't need atomicity on the
basis of you believing that it shouldn't :)  Remember, we're still
discussing what thread safety should be defined to guarantee...

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

I don't think it makes sense to try to derive everything from ACI(D) in
this case.  ACID is nice to remember what a transaction is about
informally; but if you look at the actual definitions of the different
serializability criteria, even those are defined in terms of allowed
reorderings, for example.

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

For consistency, we're back to what I said previously.  We're basing
everything on sequential specifications, so if we want to apply them,
then we need to look at the state before and after an execution, and in
some way select which those states should be in a concurrent execution.
In turn, this leads us to having to think about interleavings.

> I'm even inclined to narrow it to *internal*
> consistency: internal, opaque objects must remain consistent, whereas
> user-exposed objects need not.

That's a too vague definition for me to really understand what you're
thinking about.

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

What's the point of the example?  I agree that we don't want memset to
try to update the bytes atomically -- yet it's marked MT-Safe.  But do
we want to derive from this fact that MT-Safe means the same weak thing
for every other function?  If so, we could say that all other MT-Safe
functions can produce garbage as long as they themselves don't crash.
Is that a beneficial for programmers?  To me, this just points out that
the definition of MT-Safe is imprecise.

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

That should be classified as a data race.

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

Same here.

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

Let's assume that we require programs to be data-race-free (like C11 and
C++11 do).  Then we don't have to deal with the concurrent modifications
of string (parameter) buffers, yet we can still discuss atomicity of
those operations.  Remember that you still need to define consistency --
and all we have are sequential specifications, so we need to base
something on top of them.  Alternatively, you need to define which other
states would be consistent.

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

The last one is a data-race-freedom requirement, essentially.  There are
no atomics, so everything else is racing.

> , and the various synchronization
> primitives are *the* means for memory synchronization (memory barriers).

The text reads "the following functions synchronize".  This does not
specify whether these are the only ones that do synchronize, nor are
guaranteed to synchronize in some way.

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

Right, those issues fall in the second category that I mentioned, that
is whether additional synchronization is implied in certain cases (e.g.,
your example, or if always read all of the effects of a function if you
read a part of it (when using MT-Safe functions)).

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

Well, sort of.  What you describe would be a full memory barrier
essentially (ie, you could do Dekker-style synchronization with it).
But in practice, you want to have weaker barriers for locks, for example
(just acquire / release); certain combinations of those do ensure a
happens-before relation, but others don't (e.g., to releases of
different locks).

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

Right.  The case I had in mind was that we have just one, but don't
quite know how strong it's guarantees should be.  Then, when making a
choice, we face this problem.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]