Re: [RFC] Lock elision implementation guidelines

[Torvald Riegel <triegel at redhat dot com>]

On Tue, 2013-02-19 at 20:23 -0500, Rich Felker wrote:
> On Tue, Feb 19, 2013 at 09:52:28PM +0100, Torvald Riegel wrote:
> > > > > No. You cannot ignore any requirements. That's why they're called
> > > > > requirements and not recommendations.
> > > > 
> > > > Usually, I wouldn't reconsider any requirements.  But this case is
> > > > special enough to warrant thinking about this.
> > > 
> > > Everybody's pet feature is "special enough" to warrant breaking the
> > > requirements -- to them. The problem is that this doesn't scale. You
> > > end up breaking all the requirements because everybody wants to break
> > > a different one.
> > 
> > Just a quick comment because this seems to be off-topic: The
> > requirements themselves don't come out of thin air either;  Some
> > features are considered to be more important than others when deciding
> > on the requirements too.  So there is a way to scale such decisions, and
> > lock elision has enough potential to be quite a bit more than a pet
> > feature.
> 
> At present, this feature is only interesting to less than 1% of glibc
> users. I doubt that will increase significantly even if the hardware
> becomes widespread, simply because locking already costs virtually
> nothing for most normal usage cases.

While it's true that the lock acquisition latency for locks that are
already in the cache has been substantially decreased in the past, once
you use the same locks concurrently with other threads, you get cache
misses, and these are costly.  Typically, when you use locks, you use
them because you need to synchronize and there can be concurrent actions
by other threads.  You can hope that those other threads are not too far
away from yourself in terms of the memory hierarchy (i.e., hope for
locality), but that's not simple.  But we won't get less concurrency.

And there is the trade-off of fine-granular vs. coarse-granular locking.
I'm not sure what you see as the normal use case for locking, but I'd
say it rather comes with coarse-granular than fine-granular locks.  So
if you can make the coarse-granular ones scale better with lock elision,
that's a win to me.

> > > If the number of threads that
> > > deadlock in a program is bounded, it's not even a resource "leak".
> > > This is a very different class of "bug" from what would happen if the
> > > thread wrongfully continued execution when it should have deadlocked!
> > > The latter would almost certainly lead to undefined behavior, with
> > > likely results including data corruption or security compromise.
> > > 
> > > With that said, I can think of at least several scenarios where the
> > > deadlock behavior could be used constructively:
> > > 
> > > 1. For a permanent thread that does nothing but handle signals using
> > > async-signal-safe functions, pthread_mutex_lock(&m);
> > > pthread_mutex_lock(&m); is just as valid as for(;;)pause();
> > 
> > That's a good counter example -- I hadn't thought about signal handling.
> > 
> > However, is a deadlocked thread actually *required* by POSIX to make
> > progress handling signals?
> 
> This is a good question -- I'll have to research it. I believe the
> general forward progress requirements cover this case: for example if
> a signal has been sent to thread A, and thread B is waiting for an
> event that would happen from the signal handler running in thread A,
> and no other threads exist, then I believe it's required that the
> signal handler run. However I can look into this in more detail.

Thanks.

Both C11 and C++11 give very limited progress guarantees, so I wouldn't
be surprised if POSIX doesn't guarantee much either.

> > The same question also applies to program exit: Is a program with a
> > deadlock required to exit successfully, or can it deadlock?  I'm
> 
> Yes, it can and must exit successfully provided no lock prevents it
> from doing so. If _exit is called, there's no question. If exit is
> called, then unless the deadlocked thread is holding a lock on a stdio
> stream, or unless an atexit handler enters an infinite loop, exit must
> eventually terminate the program.

Is there some wording in the standard that requires this, or specifies
this in more detail?

> > wondering about this not because I would think that implementations
> > should try to deadlock in this case; instead, I'm thinking about whether
> > POSIX actually gives sufficient forward progress guarantees in such
> > cases to allow the program to depend on them in the scenarios you
> > mentioned.
> 
> There have actually been some recent discussions on the Austin Group
> tracker regarding conditions under which locks (especially stdio
> locks) can delay/deadlock exit(). You might want to check them. My
> feel is that if you posed a question about whether deadlocked threads
> can block exit in other cases, you'd get a clear no from the
> committee.

I will have a look.


Torvald