Re: [PATCH 05/14] Add lock elision to rwlocks

[Torvald Riegel <triegel at redhat dot com>]

On Tue, 2013-07-02 at 09:55 +0200, Dominik Vogt wrote:
> On Mon, Jul 01, 2013 at 03:38:06PM +0200, Torvald Riegel wrote:
> > On Fri, 2013-06-28 at 03:34 -0400, Carlos O'Donell wrote:
> > > I need some consensus on this issue.
> > > 
> > > In POSIX Issue 7:
> > > http://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_rwlock_trywrlock.html
> > > 
> > > The language for pthread_rlock_wrlock and pthread_rwlock_trywrlock says
> > > that it "may" deadlock, or it "may" also return EDEADLK.
> > 
> > Yes, it may deadlock or may return EDEADLK.  But the standard doesn't
> > say that it may do anything else.
> 
> > With elision, we cannot know whether  we already acquired the
> > lock (with elision) previously,
> 
> Please note that this way of speaking about elision is incorrect
> and has already lead to wrong results in your analysis:
> 
> You either acquire the lock _or_ elide it.

At the level of the user program, we always (virtually) acquire the
lock.  If a program sticks to what's defined by the respective
standards, a program cannot detect whether elision was used during a
lock acquisition or not.  Given that we've been talking about semantics
required by the standard in this thread, I think reasoning on the level
of the user program is the right thing to do.  POSIX models mutual
exclusion based on lock acquisition/release, so it makes sense to stick
to this terminology.

The lock implementation may choose to use lock elision internally.  And
it could do all kinds of other things to implement mutual exclusion,
including stuff that doesn't look like a traditional lock acquisition.

> You cannot have both at
> the same time.  This is important because transactions serialize
> side effects that occur at the same time.  If two threads use the
> same mutex or lock at the same time, neither is required to block
> nor to indicate an error to the caller because their code is
> executed speculatively.  If there is a conflict, one of the thread
> aborts and is "warped back" in time and will never have effectively
> called the ...lock() function at all.  You could say that the POSIX
> semantics are guaranteed by "time travel" if need be.

You described why lock elision works, in the sense of leading to
executions that are -- from the point of view of the program --
equivalent to acquiring locks without using elision.

> > so we are neither able to deadlock nor to return EDEADLK.
> 
> "We" neither need to dealock nor to return EDEADLK.

>From the point of the user program and the semantic guarantees it can
expect, we need to do this.  All of this discussion is about what's
visible to the program.  It doesn't mean we have to implement it exactly
like this; we can implement it differently provided this isn't visible
to the program.

> It suffices
> to abort the current transaction if the same lock is currently
> being elided by this thread.

Yes, you could abort.  But from the perspective of the user program, you
still need to deadlock or return EDEADLK, eventually, and anything else
you do must not be visible to the program.  So if you abort, you can
either do busy waiting by aborting constantly, or eventually fall back
to the non-elision code paths that will deadlock (i.e., not continue to
execute the bits of the program that follow after the respective lock()
call) or return EDEADLK.

Nonetheless, we still can't detect precisely whether we already
virtually acquired the lock using elision (with the assumptions we made
earlier, see below).

> (Note that it is impossible to
> deadlock inside a transaction as every transaction eventually
> aborts if it does not complete, and it does not matter whether the
> thread deadlocks or not because after the abort it will appear as
> if the thread had not called the locking function in the first
> place.)
> 
> If you really want to, it is possible to detect whether the same
> thread is already eliding the same lock (e.g. by writing a
> complete list of currently elided locks into tls) although it may
> not be efficient to do so.

Right, it's not efficient, and this is something we have discussed
months ago.  This implementation possibility is also hinted at in the
guidelines.

> (That is, it is possible to elide NORMAL mutexes and wrlocks in
> write mode.)

We ruled out the option of explicitly keeping track of which mutexes a
thread has acquired because we thought the overheads were too high.  At
least Andi, Carlos, and I were of this opinion.  Thus, the discussion is
based on this assumption.  Sorry if that wasn't clear after reading the
guidelines; if you haven't read them, please do.
If you think that the overheads of keeping track of lock acquisitions
wouldn't be prohibitive, please try it and report back any findings.

> > If we just blindly use elision, programs will be able to acquire
> > the write lock twice, or hold a write and a read lock.
> 
> That is not true.  The code still guarantees that only one thread
> can acquire the lock (write)

No, it doesn't.  It doesn't keep track of whether we have virtually
acquired a lock using elision, so it can't detect this.  It also doesn't
always abort any existing transaction (as Andi's most recent patch
version does for mutex trylock), so there could be an enclosing
transaction that has been started for elision of the same lock.

> and only while no other thread has
> acquired it (read or write).  It also guarantees that as soon one
> thread acquires the lock (read or write) all other threads abort
> their transactions on that lock (because the futex is in their read
> set).  It is irrelevant whether one or more threads elide a lock
> (read or write) in parallel to another thread that elides a lock
> (write) because the transactions are either serialized or aborted.

The details we have been discussing are about cases where *one* thread
tries to acquire the write lock twice, or acquired both a read and a
write lock (on the same rwlock).  This isn't about other threads at all.


Torvald