[cpp-threads] D2335 (sequential consistency proof) revision

[Lawrence Crowl]

Boehm, Hans <hans.boehm at hp.com> wrote:
> Consider the following (variant of a well-known) example, where x is
> atomic (initially zero, SC ops only) and l1 is initially unlocked:
>
> Thread 1:
>         x.store(1);
>         l1.lock();
>
> Thread 2:
>         r2 = trylock();  // fails
>         r3 = x.load();   // yields 0
>
> Note that lock and trylock are both only acquire operations,
> even though the trylock reads the value written by the lock.
>
> Since there are no synchronizes-with relationships and hence no
> happens-before relationships across threads, the current plan is
> to insist on a total order only among SC atomics, not locks,

Herb Sutter <hsutter at microsoft.com> wrote:
> I didn't realize that. I don't agree, because atomics and locks
> (and, sigh, fences) should be interchangeable for synchronization
> purposes. They all express (parts of) critical sections, and we
> shouldn't have multiple types of critical sections that have odd
> interactions. Besides, then programs wouldn't be SC, right? And
> I thought the goal of having SC atomics (esp. as the default) was
> so that programs that use just locks (correctly, meaning not the
> trylock trick) and SC atomics are SC.

More importantly, one needs to be able to replace locks in the
implementation a library with atomics and still retain sequentially
consistency with clients.

Lawrence Crowl <Lawrence at crowl.org> wrote:
> That is, without decoration [locks] are SC, not just acquire
> or release.

Herb Sutter <hsutter at microsoft.com> wrote:
> Why should taking a lock be a full fence? The only use case I know
> of for making a lock operation a full fence is the anti-idiom of
> abusing a trylock or timed lock to detect a lock taken by another
> thread, as Hans noted below.
>
> I thought that taking a lock enters a critical section, which only
> needs to be an acquire.

The reasoning is that if SC is a strong goal, then we need to provide
the mechanisms to make it achievable.  An alternate approach is to
disallow this use of the trylock.

Paraphrasing Boehm, Hans <hans.boehm at hp.com>:
> Option 1: Race free defined via "simultaneous execution of
> conflicting actions".  Successful lock has release semantics.
> Option 2: Race free defined via happens-before.  Successful trylock
> has acquire semantics.
> Option 3: Leave the current version alone and accepting that
> trylock/timedlock get you out of the SC domain, unless you follow
> some rules.
>
> I think I advocate either option (2) or (3).

I'm okay with (2).  I'm also okay with programmers getting (3)
by annotating the trylock/timed lock with no-acquire.  My concern
is that trylock and timedlock will be common enough (particularly
if necessary to handle cancellation) that adding extra programming
rules around their simple form is going to be a persistent source
of mistakes.

-- 
Lawrence Crowl