Re: mutex vs turnstile

On Thu, Jan 18, 2018 at 10:38:02AM +0000, Nick Hudson wrote:
> On 01/09/18 03:30, Mateusz Guzik wrote:
> > Some time ago I wrote about performance problems when doing high -j
> > build.sh and made few remarks about mutex implementation.
> >
> > TL;DR for that one was mostly that cas returns the found value, so
> > explicit re-reads can be avoided. There are also avoidable explicit
> > barriers (yes, I know about the old Opteron errata).
> >
> > I had another look and have a remark definitely worth looking at (and
> > easy to fix). Unfortunately I lost my test jig so can't benchmark.
> >
> > That said, here it is:
> >
> > After it is is concluded that lock owner sleeps:
>
> itym... after it is concluded that the thread should sleep as the lock is
> owned (by another lwp) and the owner is not on cpu.

I don't think this distinction makes a difference here.

>
> >
> >          ts = turnstile_lookup(mtx);
> >          /*
> >           * Once we have the turnstile chain interlock, mark the
> >           * mutex has having waiters. If that fails, spin again:
> >           * chances are that the mutex has been released.
> >           */
> >          if (!MUTEX_SET_WAITERS(mtx, owner)) {
> >                  turnstile_exit(mtx);
> >                  owner = mtx->mtx_owner;
> >                  continue;
> >          }
> >
> > Note that the lock apart from being free, can be:
> > 1. owned by the same owner, which is now running
> >
> > In this case the bit is set spuriously and triggers slow path
> > unlock.
>
> Recursive locks aren't allowed so I don't follow what you mean here.
>
>     544         if (__predict_false(MUTEX_OWNER(owner) == curthread)) {
>     545             MUTEX_ABORT(mtx, "locking against myself");
>     546
>
> > 2. owned by a different owner, which is NOT running
>
> Is this still a possibility given the above?
>

This is not about recursive locking. I explicitely noted 2 scenarios
which are handled suboptimaly:

Lock owner is remembered across turnstile_lookup.

MUTEX_SET_WAITERS does:
        rv = MUTEX_CAS(&mtx->mtx_owner, owner, owner | MUTEX_BIT_WAITERS

If the lock owner is the same and sleeps, it's fine.

If the lock owner is the same but does not sleep, the bit is set for no
reason.

If there is a different owner (or the lock is free), cas fails and
turnstile_exit is called.

If the lock is free or said different owner does not sleep, it's fine.

If said different owner sleeps, turnstile_exit is called for no good
reason and the code circles back.

Mateusz Guzik <mjguzik gmail.com>