Lock elision problems in glibc-2.18

[Dominik Vogt]

On Tue, Sep 17, 2013 at 12:58:05PM +0200, Torvald Riegel wrote:
> On Tue, 2013-09-17 at 12:43 +0200, Dominik Vogt wrote:
> > On Mon, Sep 16, 2013 at 05:06:26PM +0200, Torvald Riegel wrote:
> > > On Mon, 2013-09-16 at 12:25 +0200, Dominik Vogt wrote:
> > > > On Mon, Sep 16, 2013 at 10:58:06AM +0200, Torvald Riegel wrote:
> > > > > On Fri, 2013-09-13 at 23:23 -0700, Andi Kleen wrote:
> > > > > > Torvald Riegel <triegel@redhat.com> writes:
> > > > > > 
> > > > > > >  We need to do this, and if the app
> > > > > > > misinterprets and *always* keeps retrying, it will hang.
> > > > > > 
> > > > > > The app is broken then. Retrying forever is simply not allowed.
> > > > > > I don't think it makes sense to complicate glibc for this.
> > 
> > Anyway, even if the application does not retry forever, this is no
> > guarantee that the glibc abort handler is ever called.
> 
> If it does not retry forever, it eventually will execute
> nontransactionally.

That does not mean that it will execute the same code
non-transactionally.  The user code might do something completely
different that does not use pthread_mutex_lock at all.

>  Once it does, we've "peeled off" this layer of the
> problem.  Thus, eventually, glibc's elision will constitute the
> outermost transaction, so its abort handlers will be executed if
> necessary.

> > The
> > fallback code might use other mechanisms but pthread_mutex_lock
> > for protection and thus the mutexes that aborted might not be used
> > at all.
> 
> Right, but if pthread mutexes aren't used in the fallback, why do its
> abort handlers need to be called?  IOW, in such a case the caller
> effectively turns off elision.

The current implementation of lock elision expects that its abort
handler will eventually be called to do the tuning.  I showed a
scenario where this will not happen, so the tuning is effectively
disabled in that scenario.  Let's think about the consequences if
this happens.

The initial design idea of the tuning was (at least as far as I
understood it) that it should automatically adapat and show
"sensible" behaviour after a while that at least makes sure that
there isn't a big performance loss.  Now we have a case where the
tuning code is never even executed.  This is a contradiction to the
design idea, so either the design or the implementation needs to be
fixed (or my idea of what the design is).

Perhaps we should start with writing down the requirements for
the tuning algorithm.  Just some bullets that come to my mind:

 * The ultimate goal is to use elision where it helps and to not
   use it where it harms.
 * A (possible recurring) training phase where the algorithm
   performs badly is acceptable.
 * After a training phase, a certain minimum or average
   performance must be guaranteed in all cases.  If not, what are
   the exceptions, and how do we deal with them (e.g. argue that
   they are irrelevant (reasons), easy to avoid etc.).
 * If lock elision is ever to be enabled by default, the tuning
   algorithm must make sure that no (relevant?) software shows
   a significant (unacceptable) performance loss.
 * If lock elision is _not_ going to be enabled by default, the
   performance requirements could be much less strict.

I think the implementation of lock elision is more or less fixed
regarding the use of transactions (on a specific platform).  The
real freedom lies in the tuning algorithm that decides whether to
try a transaction or not.

> > Thus, the glibc code must not rely on its abort handlers
> > ever being called.
> 
> I think that's not quite a precise characterization.  It can rely on the
> abort handlers being called it started the outermost transaction.

Granted.  The current code does not check whether it is going to
start an outermost transaction.  This can be implemented (Xtest
for Tsx, Etnd for z), but it does not come for free.

> It
> can also expect that callers with enclosing transactions will eventually
> fall back to nontransactional execution.

Let's rather say:  Expect that the caller will eventually take
measures to ensure forward progress.  This includes mechanisms like
the aforementioned constrained transactions.

> It is true that we cannot expect that abort handlers are always called,
> so if you'd try to use the abort handlers for precise monitoring of
> aborts caused by critical sections that use elision, then this wouldn't
> work.  But from a correctness point of view, the pthread mutexes will
> eventually do what they are supposed to.

Yes, I think a lot of the discussion is that we all have different
ideas of what "is supposed to" means exactly.  See above.

Ciao

Dominik ^_^  ^_^

-- 

Dominik Vogt
IBM Germany