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

[Dominik Vogt <vogt at linux dot vnet dot ibm dot com>]

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.  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.

> so we are neither able to deadlock nor to return EDEADLK.

"We" neither need to dealock nor to return EDEADLK.  It suffices
to abort the current transaction if the same lock is currently
being elided by this thread.  (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.

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

> 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) 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.

Ciao

Dominik ^_^  ^_^

-- 

Dominik Vogt
IBM Germany