Re: ctermid: return string literal, document MT-Safety pitfall

[Torvald Riegel <triegel at redhat dot com>]

On Tue, 2014-11-18 at 20:23 -0200, Alexandre Oliva wrote:
> On Nov 17, 2014, Torvald Riegel <triegel@redhat.com> wrote:
> 
> > On Fri, 2014-11-14 at 14:53 -0200, Alexandre Oliva wrote:
> >> On Nov 14, 2014, Torvald Riegel <triegel@redhat.com> wrote:
> >> 
> >> > AFAICT memset_s is still a sequentially-specified function.
> >> 
> >> How can you tell?  It's not like the standard explicitly says so, is it?
> >> It can't be the as-if rule if intermediate results can be observed in
> >> ways that are not ruled out by the standard.
> 
> > If we're talking about C11, which Florian cited, then the by-default
> > data-race freedom requirement applies, and memset_s doesn't say anything
> > about atomicity or ordering, so if you would observe intermediate
> > states, you'd have a race condition.  You wouldn't have a race condition
> > if you'd have an observer that happens-before the memset_s or have the
> > memset_s happens-before the observer.  IOW, you're not allowed to look
> > at the intermediate states.
> 
> I'm not asking specifically about memset or strcpy, I'm asking how do
> you tell in general.

For C11 specifically, what I wrote above applies. If the function is
doing something, for example a store, and the function does not specify
what it does internally and which inter-thread happens-before relations
this creates, then there's nothing specified that makes this not a data
race if you try to look at an intermediate state from another thread.
So if you actually look at an intermediate state, there's a data race.

Data-race-freedom is the default.  5.1.2.3p10 gives an example of an
allowed implementation that just guarantees equality of non-volatiles to
the abstract machine at function boundaries; IOW, the implementation is
allowed to just satisfy a post-condition (as long as it doesn't violate
other invariants, introduced data races on its own, etc.). 

> You've long ago, and again recently, claimed that
> such functions as qsort and bsearch have sequential specifications, even
> though they have callbacks that must necessarily observe and compute
> based on intermediate states.

Well, the comparison callbacks can't just look at will at every piece of
intermediate state.  They get called with specific arguments, and the
memory locations that they have to compare are exactly specified.  So, I
agree that these *specific* memory locations are intermediate states,
but the comparison functions are not guaranteed to be able to look at
other elements of the arrays and find sensible information in those.

The promise that a function such as qsort makes is still that after it
has finished, the array will be sorted.  Yes it can call other functions
while doing that, and it will do those calls in a way that satisfies the
preconditions of those other functions (e.g., don't have garbage in the
elements that a comparison function needs to compare); but that doesn't
mean that it guarantees anything beyond that in terms of it's promise.

> I'm just trying to figure out what the
> heck you mean by âsequential functionâ, and by âsequential
> specificationâ.

What I mean is that they are not concurrent specifications that make
guarantees about states of an unfinished execution as visible to
concurrent observers.  They only make guarantees about the state after a
function has finished executing.  (Sorry if I'm using shared-memory
synchronization terminology here, but given that we want to distinguish
between concurrent and non-concurrent, that seems to make sense.)

> I had understood the latter had to do with
> specifications limited to pre- and post-conditions, but the standards
> we've been talking about do not limit function specifications to that.

Why do you think that is the case?  The callback, or composition of
functions in general, is one thing you mentioned, and I hope was able to
convince you that this doesn't give guarantees about the caller (e.g.,
qsort) to the callee (e.g., comparison function), except when those
guarantees overlap with preconditions for the callee.

> So, something is clearly amiss.
> 
> As for observing intermediate results, we seem to have ruled out as
> undefined accesses from other threads, and from interrupting signal
> handlers.

Good.

> This covers almost all possibilities, but how about
> cancelling the thread that's running memcpy or strcpy, if it has
> asynchronous cancellation enabled?  If you do that, and then
> pthread_join completes, you have set a clear happens-before
> relationship.

Well, that's what I would guess too.  I definitely agree that the
cancellation happens-before the return of pthread_join, but which
effects then actually happen-before depends on the definition of
AC-Safe.  Which you seem to point out next:

> Sure enough, POSIX doesn't require such functions as
> memcpy or strcpy to be AC-Safe, but our manual claims our current
> implementations are.

That is a good question, and really is up to the definition of AC-Safe.
The one I see is (please correct me or cite further parts of the spec
that may apply):
"A function that may be safely invoked by an application while the
asynchronous form of cancellation is enabled."

That doesn't really tell me a lot :)  I can interpret "safely invoked"
to at least mean that the mere act of cancellation will not break
anything.  But it doesn't tell me which state one can expect after
cancellation.

I think we can distinguish between three kinds of functions here:
1) Functions like memset that (IMO) don't specify intermediate states.
2) Functions like memset_s, that to some extent do specify intermediate
states (e.g., in this case, it's equivalence to steps the abstract
machine would do when storing one character at a time, starting at the
beginning).
3) Those with an already concurrent specification, which clearly
designate atomic parts (i.e., indivisible steps, even wrt.
cancellation).

One way to define safety would be to say that a cancelled function
should either take effect or not, but never partially take effect.  IOW,
it's either just the precondition or the postcondition that holds.

Another option would be to allow specified intermediate steps to take
effect.  For 2), we could say that cancellation happens anywhere between
the steps the abstract machine would do, but not within a step.  This
would be satisfied under the requirement you assumed for memset and
strcpy implementations, I believe.
For 3), it could be cancellation between any of the atomic steps, unless
otherwise specified.  For condvar wait, for example, this could be one
of the three parts: lock release, wakeup, lock acquisition.  However,
that may not be really useful, so more needs to be specified (as
condvars do, IIRC).  If a concurrent function is supposed to be just one
atomic step, safety could mean either pre- or postcondition.

For 3), we can probably assume safety to be that the function was
cancelled somewhere between the atomic steps it does make.

> Does this mean it is safe to access the variables
> that were partially modified by the interrupted memcpy/strcpy/whatever,
> and that this provides means to safely inspect intermediate states?

For normal memcpy, strcpy, and other functions in group 1), the
intermediate states aren't defined, so unless we want to define safety
as just being cancellable (and leaving the affected memory in an
unspecified state), we can't do much.

> Or
> does it mean our manual should not claim these functions to be AC-Safe,
> just so that we can claim a program that attempts to inspect
> intermediate states of strcpy is undefined behavior?

I guess not claiming AC-Safety makes most sense for group 1).
Cancellation could be useful in scenarios where you actually don't need
to look at the state at all -- but then AC Safety must clarify the
definition that you shouldn't look at state.  I'm not sure whether we
want this as default though.

> Or could we resort
> to any other argument to make it undefined?

I'm not aware of one.  I believe clarifying (our interpretation of) the
definition of AC-Safety is a good way forward.  Or checking back with
POSIX.  If there is indeed an agreed upon, clear definition, we should
just adapt to it I suppose.