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 Fri, 2013-05-31 at 18:41 -0300, Alexandre Oliva wrote:
> On May 30, 2013, Torvald Riegel <triegel@redhat.com> wrote:
> 
> > Also, it says that one function should virtually "happen after another",
> > which at least suggests a total order.
> 
> Which may well have been enough of a reason to drop that broken
> definition in favor of the current one.

It's not broken.  It's just a choice that can make sense, and is
definitely easier to deal with for programmers.  If you cut it down to
total orders per stream, for example, it's even less of a performance
issue.

> > What I primarily want to see
> > is a proper definition of thread safety,
> 
> Given that posix rules data races as undefined (as cited in the last of
> the messages I posted yesterday, a passage I wish I'd noted long ago,
> for it would have saved us all a lot of speculation in this conversation)

This is a data-race-freedom requirement *on applications*.

This doesn't necessarily affect what glibc can do internally; in
particular, while glibc shouldn't not introduce additional data races at
unrelated state (e.g., it shouldn't write to arbitrary addresses in the
application's state), it doesn't need to avoid things that would be
classified as data races in an application as long as it can contain any
bad effects.

> and it specifies the behavior of various functions, requiring them to be
> thread safe even if they are required to manipulate internal data
> structures that, in the absence of synchronization, would involve data
> races, it must follow that, when posix writes âsafe to callâ, one of the
> requirements must be that the implementations must ensure such data
> races are avoided while offering the specified functionality.

Not quite, see above.  For example, to actually implement the
synchronization mechanisms, you need to do things that would be
considered as data races on the application level.

> Can you derive any additional requirement from the standard?
> 
> Should there be any additional requirement?

This data-race-freedom on applications is required to make
synchronization and other thread-safe stuff actually feasible to
implement (and implement efficiently).  But you cannot derive a
correctness criterion just from data-race freedom.  It's easy to read
garbage in a data-race-free way, for example.  So yes, there must be
more requirements/guarantees.

> 
> >> 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.
> 
> Given that memory-synchronizing operations are defined as synchronizing
> with the global, shared memory, I understand it follows that such
> synchronizing operations are events that define a total order among
> themselves.

That's arguably too strict, as I also explained in another email.
Happens-before is a partial order; even the subset of synchronizing
operations should be a partial order, or you are forcing full membars on
everything.

> Therefore, it must follow that an event F that
> happened-before synchronization event G (F and G in the same thread)
> must be observable by event Q that happened-after synchronization event
> P (P and Q in the same thread) if G happened-before P (per the total
> ordering of synchronization operations).

Right, modulo this not being a total order (and ignoring C11/C++11
release-consume semantics).

> The total ordering of
> synchronization events makes the distinction irrelevant: it doesn't
> matter if someone in the middle observed something, there's a direct
> happens-before relationship between the synchronization operations that
> ensure observability across the synchronization events and, if there are
> no such synchronization events, then there's a data race that makes it
> undefined, i.e., the observability is possible but not certain.

But we don't have a total order :)  I agree that the standardese you
posted suggests a total order, but this is not how glibc is built, nor
do C11 and C++11 offer just sequentially consistent synchronization.  If
we had to provide a total order, we would have to add a full (ie,
sequentially consistent) memory barrier to every mutex release
operation, for example.

> > Yes.  Even further indication that "thread-safe" can be mean different
> > things to different people :)
> 
> There's no dispute about that.  The dispute is on whether these
> different interpretations are derived from the standard, or from
> assumptions that don't find support in it.

The standard has an arguably incomplete definition; if taking just the
data-race-freedom requiement literally as the definition of thread
safety, then this would be useless because it wouldn't give you
anything.  So there has to be more.  And I'd rather select the
properties that comprise "more" in a way that is actually helpful to
programmers, while still allowing for efficient implementations.

> > 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).
> 
> Caching in thread-local vars would apparently permitted only as long as
> the synchronization primitives defined in the standard synchronized them
> with global memory too.

That's exactly what my question below is about: Do the thread-safe
functions respect established happens-before?

I'm glad that you're agreeing that they should, not just because this is
actually an ordering guarantee :) and you couldn't derive this
requirement from just data-race-freedom :)

> I'm even getting the idea that the standard is defined such that it
> would be valid to buffer all memory writes (not just those inside the
> library implementation) in an infinite thread-local cache, that would be
> flushed and cleared upon user-initiated synchronization operations.  In
> distributed systems speak, it's as if each process (thread) made changes
> to memory only locally, and communicated with the global memory to flush
> local changes and pull updates at the synchronization primitives.

I don't think the mental model of global memory as one component in a
distributed systems serving requests in FIFO order is very useful (for
this discussion).  In particular, this doesn't allow for synchronization
operations forming just a partial order.

If you haven't yet, I'd suggest looking at the Batty et al.
formalization of the C++11 memory model.  It gives a good overview of
how the C11/C++11 models work (e.g., how a program's control flow and
candidate executions are combined to form the set of allowed executions,
and how data-race-freedom gives leeway to implementations).

> It
> doesn't, however, rule out asynchronous messages from being send or
> received, which is why additional care needs to be taken to avoid races.

The data-race-freedom requirement isn't really tied to asynchronous
messages.

> > 1) Do you respect established inter-thread happens-before?
> 
> Who, me? :-D
> 
> I believe the standard requires the model I described above, in which
> the synchronization primitives defined in the standard define a total
> happens-before order.
> 
> I'm not convinced, however, that this respect has anything to do with
> thread safety.  It's different levels of abstraction we're talking
> about.  A âsafe to callâ requirement should mean it's safe to call
> regardless of the underlying memory model; the implementation should
> ensure it behaves as mandated by the specification

That's a sequential specification, so we need make sense of this despite
being in a concurrent setting.  That clearly can't be done without the
memory model.

> as long as all
> threads behave within the defined constraints (i.e., not exercising
> undefined behavior or calling unsafe functions).

The data-race-freedom requirement is part of the memory model.

> > 2) Do you establish additional inter-thread happens-before relations
> > that make sense for the abstract functionality that the particular
> > function offers?
> 
> Only where the standard specifies that such a relation is established.

I think we need to accept that the specification in the standard is
incomplete.  If we don't even have a well-defined thread safety spec, I
believe it's not too unlikely that the more subtle aspects have just not
been specified in the detail in which they should have been specified,
or perhaps haven't even been considered.

> > Do you preserve transitivity of happens-before (I mean
> > C/C++ acquire/release vs. acquire/consume, for example)?
> 
> I believe the total order established by synchronization primitives does
> that.  I don't see that the standard requires any other specified
> primitive to do so.
> 
> > 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?
> 
> I'm afraid I don't understand the question.  What does a counter
> produce, is it a frequency, a period, the value it holds when you look
> at it?
> 
> As in, do you mean something like { static int i; return i++; }?

Yes, a shared integer counter, every thread incrementing the counter
(eg, through a give_me_an_id() function) gets a unique value back,
increasing the counter monotonically.  And perhaps you can read the
counters value, too.

>  A
> global clock that advances regardless of calls, so that the function
> returns its current value?  Something else?  Anyway, for both cases I
> mentioned, my answer would be âit might make sense or it might not,
> depending on its purposeâ

And it's okay to make that distinction; nonetheless, we need to consider
what's useful for users here.  For a counter as specified above, there
must be synchronization anyway to implement this functionality; so
performance-wise, it would be bad if programs where required to add
additional synchronization (e.g., wrap the counter in a lock or use
barriers) just because we don't want to give the guarantee in the first
place.  Should it establish happens-before relations that the callers
can rely on?

It doesn't have to be a counter.  What we need to consider is examples
where one thread creates or sets a value using a thread-safe function,
and another thread can observe this value through a thread-safe
function.  In this case, the second call's result implies a certain
ordering.  This leads to two questions:
1) Should this ordering be consistent with the orderings implied by the
results of other thread-safe calls?  For example, can we can get results
out of thin air that wouldn't be possible in some sequential execution?
2) Should programs be allowed to rely on this ordering also being
reflected in happens-before in some way (it doesn't need to be a total
order!)?


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