Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1531281

[PATCH 00/11] locking/ww_mutex: Keep sorted wait list to avoid stampedes

Show all headers | View raw

It turns out that the deadlock that I found last week was already implicitly
fixed during the lock->owner redesign, by checking the WAITERS bit in the
w/w lock fast path. However, since I had already started looking into
sorting the wait list, here goes.

The basic idea is to make sure that:

1. All waiters that have a ww_ctx appear in stamp order in the wait list.
Waiters without a ww_ctx are still supported and appear in FIFO order as
before.

2. At most one of the waiters can be in a state where it has to check for
back off (i.e., ww_ctx->acquire > 0). Technically, there are short time
windows in which more than one such waiter can be on the list, but all
but the first one are running. This happens when a new waiter with
ww_ctx->acquire > 0 adds itself at the front of the list and wakes up the
previous head of the list, and of course multiple such chained cases can
be in-flight simultaneously.

Then we only ever have to wake up one task at a time. This is _not_ always
the head of the wait list, since there may be waiters without a context. But
among waiters with a context, we only ever have to wake the first one.

To achieve all this, the series adds a new field to mutex_waiter which is
only used for the w/w lock case. As a consequence, calling mutex_lock
directly on w/w locks is now definitely incorrect. That was likely the
intention previously anyway, but grepping through the source I did find one
place that had slipped through.

I've included timings taken from a contention-heavy stress test to some of
the patches. The stress test performs actual GPU operations which take a
good chunk of the wall time, but even so, the series still manages to
improve the wall time quite a bit.

Cheers,
Nicolai

Back to linux.kernel | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

[PATCH 00/11] locking/ww_mutex: Keep sorted wait list to avoid stampedes Nicolai Hähnle <nhaehnle@gmail.com> - 2016-11-28 13:30 +0100
  [PATCH 2/4] locking: Add kselftests for ww_mutex AA deadlock detection Chris Wilson <chris@chris-wilson.co.uk> - 2016-11-30 01:40 +0100
  [PATCH 4/4] locking: Add kselftests for ww_mutex stress Chris Wilson <chris@chris-wilson.co.uk> - 2016-11-30 01:40 +0100
    Re: [PATCH 4/4] locking: Add kselftests for ww_mutex stress Maarten Lankhorst <dev@mblankhorst.nl> - 2016-11-30 13:30 +0100
      Re: [PATCH 4/4] locking: Add kselftests for ww_mutex stress Chris Wilson <chris@chris-wilson.co.uk> - 2016-11-30 14:00 +0100
  [PATCH 1/4] locking: Begin kselftests for ww_mutex Chris Wilson <chris@chris-wilson.co.uk> - 2016-11-30 01:40 +0100
    [PATCH 3/4] locking: Add kselftests for ww_mutex ABBA deadlock detection Chris Wilson <chris@chris-wilson.co.uk> - 2016-11-30 01:40 +0100
    Re: [PATCH 1/4] locking: Begin kselftests for ww_mutex Nicolai Hähnle <nhaehnle@gmail.com> - 2016-11-30 09:10 +0100
  Re: [PATCH 00/11] locking/ww_mutex: Keep sorted wait list to avoid  stampedes Chris Wilson <chris@chris-wilson.co.uk> - 2016-11-30 10:50 +0100
    Re: [PATCH 00/11] locking/ww_mutex: Keep sorted wait list to avoid  stampedes Nicolai Hähnle <nhaehnle@gmail.com> - 2016-11-30 13:10 +0100
      Re: [PATCH 00/11] locking/ww_mutex: Keep sorted wait list to avoid  stampedes Chris Wilson <chris@chris-wilson.co.uk> - 2016-11-30 13:30 +0100
        Re: [PATCH 00/11] locking/ww_mutex: Keep sorted wait list to avoid  stampedes Nicolai Hähnle <nhaehnle@gmail.com> - 2016-11-30 14:50 +0100

csiph-web