Re: [MTASCsft PATCH WIP5 01/33] Multi Thread, Async Signal and Async Cancel safety documentation: intro

[Torvald Riegel <triegel at redhat dot com>]

On Sun, 2013-12-01 at 02:46 -0200, Alexandre Oliva wrote:
> On Nov 28, 2013, Torvald Riegel <triegel@redhat.com> wrote:
> 
> >> I'm not familiar with any hw memory model in which an unsynchronized
> >> single-word read could actually read garbage, rather than a value that
> >> may be outdated.
> 
> > First, this is about compilers too, not just the HW.  The only
> > counter-example that comes to my mind right now is self-modifying code
> > on x86.
> 
> You mean inconsistency between instruction and data caches?  Regardless,
> (and bearing in mind this is in no way related with the feof_unlocked
> discussion at hand) I'm curious as to how a single word load could read
> garbage rather than earlier or newer contents of the accessed memory
> location.  This claim just doesn't fit the hw memory models I'm familiar
> with.
> 
> >> > The compiler can reload from memory,
> 
> >> It can't.  It's only one access.
> 
> > It can.  Why could it not?
> 
> Because compilers don't go about making useless accesses to memory.

Now you argue that compilers are *unlikely* to add more accesses, which
would be my guess as well.  But this is different to what I said, namely
that they can; IOW, that they are allowed to.  Do you now agree that
compilers can reload?

> Given a function like:
> 
> extern int foo;
> bool  __attribute__((noinline))
> bar() {
>   return (foo&1);
> }
> 
> why would the compiler load more than once from the same memory
> location?

It's unlikely efficient code would load more than once, yes.  But this
isn't a guarantee, and a correct compiler could do it.  Maybe there's
some optimization that went crazy and did stupid things?  It wouldn't be
a compiler bug (it's incorrect application code, remember...), so the
compiler could have all tests required to ensure that it produces
correct code, and those tests would still not catch this problem.

Can we agree that those things need a fix, eventually, because it's
incorrectly synchronizing code?

That is, if you encounter similar cases while reviewing the remaining
functions for MT-Safety (and async signal/cancel are related as well),
can you please make a note, so that we can replace those with atomic
accesses?  We can use relaxed memory order accesses for now, and revisit
the memory order questions later when we have a detailed MT-Safe
definition.

> Even if it did, it's still taking only one bit out of it, and
> that will necessarily be taken from only one of the loads, so any other
> load is not only excessive, it's useless and irrelevant.

Once LTO comes into the picture, this argument doesn't hold anymore.

> > If it can figure aliasing out and the assumed sequential code doesn't
> > write to the memory location between the load and the reload, it can
> > assume that nobody else modified it, so reload from memory.
> 
> So now you're talking of multiple calls of bar().

No, I'm talking in general about what the compiler is allowed to do.

> >> > It could decide to split a 64b load into two 32b loads.
> 
> >> It can't, it's a single word load.
> 
> > Why not (unless volatile/asm)?  The compiler only has to make sure that
> > the outcome is equivalent to what the abstract machine would do.  Sure
> > it can do the split if that's supported
> 
> Even if it does the pointless split, it would *still* get the correct
> answer, because it's only looking at one bit, and that one bit, even if
> possibly loaded multiple times, will only be used once out of these
> multiple times to compute the result of the bitmasking.
> 
> Even if another thread modifies the word, the absence of synchronization
> makes both the previous and the modified values suitable, because
> there's no predetermined happens-before relationship.  If there was some
> form of synchronization and exclusive access, then it would rule out one
> of the otherwise-acceptable results.

Whether there is ordering involved is still under discussion, BTW.  Your
answers to my setsid/getsid examples seemed to indicate that there is.
Let's just keep this as an open question.

> >> > There were GCC bugs in this area that were revealed by fuzz testing, so
> >> > I'm not making that up.
> 
> >> That would be a compiler bug.  Compiler bugs can cause misbehavior.
> 
> > Those bugs were cases in which the compiler did stuff that's perfectly
> > fine in sequential code.
> 
> Loading twice from a word accessed only once would still be a bug:
> there's no excuse for the compiler to generate such obviously wasteful
> code.

Performance problem?  Maybe.  Correctness bug?  No.

> >> >> sin() doesn't have synchronization either, and it's perfectly MT-Safe.
> >> >> Why should it synchronize with any other threads?
> >> 
> >> > Your argument is backwards.  You say that there can be MT-Safe functions
> >> > that don't need shared-memory synchronization because they don't access
> >> > shared memory.  Fine.  But how does that imply that functions that use
> >> > shared memory don't need shared-memory synchronization?
> >> 
> >> It doesn't.  A single counter-example is enough to disprove what
> >> purports to be a general statement.
> 
> > Exactly, it doesn't.  So *your* claim that generally, MT-Safe functions
> > don't need to synchronize is wrong.
> 
> I didn't make such a claim.

Fine enough, then I must have misread what you said.  Agreeing that some
MT-Safe functions will have to synchronize is fine for me (roughly,
those that provide something conceptually similar to some kind of shared
state).

> I claimed there was no requirement in POSIX that all functions perform
> synchronization.  That much is true.  If it weren't so, even functions
> that did not access shared memory would have to synchronize.  Such a
> wasteful requirement is not there.  The example I gave above is an
> obvious example in which no synchronization whatsoever is mandated,
> which is enough to disprove your implied claim that a function marked
> MT-Safe has synchronization, which is what I was responding to when I
> mentioned sin() above.

That is not what I said.  Not sure where you got the implication for the
general statement from.

> Here's the earlier passage in the thread:
> 
> >> >> > how should a user expect that feof doesn't have synchronization
> >> >> > [...]?  It's marked MT-Safe.

feof is not about shared state, or, not accessing shared state?

> 
> >> What begs proving is whether POSIX mandates synchronization for any
> >> case.  It offers synchronization operations and mutexes as examples of
> >> what an implementation might internally use to achieve safety, but the
> >> only interfaces for which synchronization is mandatory are the ones used
> >> for synchronization (mutexes, locks and condition variables)
> 
> > In the choices I outlined above, you can certainly make the choice that
> > once more than one thread accesses the same virtually shared state, they
> > essentially "fork" the shared state into per-thread state, and don't
> > synchronize on it ever more.
> 
> Or fully synchronize on the next synchronization operation, or partially
> at any point in time between the accesses and the full synchronization.

Sure, that's *one* of the choices.  But this choice is not obvious from
the definition nor implied by it (ie, that's is exactly this and not
some other equally reasonable choice), so it must be explicit.

> Anyway, if they ever diverged in any perceptible way, there must have
> been a data race => undefined behavior. That's the POSIX memory model
> in a nutshell for you.

I guess this due to trying to put this into a nutshell, but either this
statement isn't correct, or you're arguing for sequential consistency
for the shared state managed by MT-Safe functions that is (indirectly)
observable by users.

> I guess we could duplicate in our manual these facts that are so clearly
> stated in POSIX.

There are several people that disagree with that.  Maybe it's not as
"clearly stated" as it seems to you?

> But should we?  Should we duplicate from the C
> Standard the chapter about the various other ways to trigger undefined
> behavior?  How about the C*11 memory models,

As soon as POSIX starts referencing C11 or above instead of C99, that's
just a reference (or, implicitly included).  As long as this hasn't been
done, we could just cite the C11 memory model, yeah...

> or the memory models of the
> various kinds of hardware we target?

Not sure why you bring these up again and again.  I thought we agreed
that they don't matter for POSIX, because they're not exposed on the
POSIX level nor the programming-language level?

> >> You know what?  Maybe you're an expert in concurrency and memory models,
> >> and that twists your view of MT-Safe under the looks-like-a-nail
> >> principle.  This possibility appears to fit the obsevable behavior.
> 
> > You do know what memory models are built for, don't you?  They define
> > allowed behavior under multi-threaded executions.  Why would MT-Safe not
> > be a subset of this topic?
> 
> There's the nail again!  :-)
> 
> Why would it be a *subset*, rather than a vaguely related property that
> may be implemented/constructed on *top* of abstractions and
> generalizations of multiple different memory models, and exposed to its
> users as even simpler and perhaps even abstractions that are apparently
> unrelated to memory modules?

The "topic" (in what I wrote), is "defin[ing] allowed behavior under
multi-threaded executions".  Isn't that what MT-Safe does as well?
Thus, if it is, then it's a subset of this whole topic.

> What if it your view was upside-down, and the MT-Safe notion came first,
> and memory models compatible with it were specified years, even decates
> later?  Oh, wait! :-)

Yes, wait, because that's not the case.  And it wouldn't matter anyway
independently of whether the term memory model or MT-Safe where used
earlier.