Skip to content

Commit 08295b3

Browse files
thomashvmwPeter Zijlstra
thomashvmw
and
Peter Zijlstra
committed
locking: Implement an algorithm choice for Wound-Wait mutexes
The current Wound-Wait mutex algorithm is actually not Wound-Wait but Wait-Die. Implement also Wound-Wait as a per-ww-class choice. Wound-Wait is, contrary to Wait-Die a preemptive algorithm and is known to generate fewer backoffs. Testing reveals that this is true if the number of simultaneous contending transactions is small. As the number of simultaneous contending threads increases, Wait-Wound becomes inferior to Wait-Die in terms of elapsed time. Possibly due to the larger number of held locks of sleeping transactions. Update documentation and callers. Timings using git://people.freedesktop.org/~thomash/ww_mutex_test tag patch-18-06-15 Each thread runs 100000 batches of lock / unlock 800 ww mutexes randomly chosen out of 100000. Four core Intel x86_64: Algorithm #threads Rollbacks time Wound-Wait 4 ~100 ~17s. Wait-Die 4 ~150000 ~19s. Wound-Wait 16 ~360000 ~109s. Wait-Die 16 ~450000 ~82s. Cc: Ingo Molnar <mingo@redhat.com> Cc: Jonathan Corbet <corbet@lwn.net> Cc: Gustavo Padovan <gustavo@padovan.org> Cc: Maarten Lankhorst <maarten.lankhorst@linux.intel.com> Cc: Sean Paul <seanpaul@chromium.org> Cc: David Airlie <airlied@linux.ie> Cc: Davidlohr Bueso <dave@stgolabs.net> Cc: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com> Cc: Josh Triplett <josh@joshtriplett.org> Cc: Thomas Gleixner <tglx@linutronix.de> Cc: Kate Stewart <kstewart@linuxfoundation.org> Cc: Philippe Ombredanne <pombredanne@nexb.com> Cc: Greg Kroah-Hartman <gregkh@linuxfoundation.org> Cc: linux-doc@vger.kernel.org Cc: linux-media@vger.kernel.org Cc: linaro-mm-sig@lists.linaro.org Co-authored-by: Peter Zijlstra <peterz@infradead.org> Signed-off-by: Thomas Hellstrom <thellstrom@vmware.com> Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org> Acked-by: Ingo Molnar <mingo@kernel.org>
1 parent 55f036c commit 08295b3

File tree

8 files changed

+213
-36
lines changed

8 files changed

+213
-36
lines changed

‎Documentation/locking/ww-mutex-design.txt

Lines changed: 46 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
Wait/Wound Deadlock-Proof Mutex Design
1+
Wound/Wait Deadlock-Proof Mutex Design
22
======================================
33

44
Please read mutex-design.txt first, as it applies to wait/wound mutexes too.
@@ -32,10 +32,26 @@ the oldest task) wins, and the one with the higher reservation id (i.e. the
3232
younger task) unlocks all of the buffers that it has already locked, and then
3333
tries again.
3434

35-
In the RDBMS literature this deadlock handling approach is called wait/die:
36-
The older tasks waits until it can acquire the contended lock. The younger tasks
37-
needs to back off and drop all the locks it is currently holding, i.e. the
38-
younger task dies.
35+
In the RDBMS literature, a reservation ticket is associated with a transaction.
36+
and the deadlock handling approach is called Wait-Die. The name is based on
37+
the actions of a locking thread when it encounters an already locked mutex.
38+
If the transaction holding the lock is younger, the locking transaction waits.
39+
If the transaction holding the lock is older, the locking transaction backs off
40+
and dies. Hence Wait-Die.
41+
There is also another algorithm called Wound-Wait:
42+
If the transaction holding the lock is younger, the locking transaction
43+
wounds the transaction holding the lock, requesting it to die.
44+
If the transaction holding the lock is older, it waits for the other
45+
transaction. Hence Wound-Wait.
46+
The two algorithms are both fair in that a transaction will eventually succeed.
47+
However, the Wound-Wait algorithm is typically stated to generate fewer backoffs
48+
compared to Wait-Die, but is, on the other hand, associated with more work than
49+
Wait-Die when recovering from a backoff. Wound-Wait is also a preemptive
50+
algorithm in that transactions are wounded by other transactions, and that
51+
requires a reliable way to pick up up the wounded condition and preempt the
52+
running transaction. Note that this is not the same as process preemption. A
53+
Wound-Wait transaction is considered preempted when it dies (returning
54+
-EDEADLK) following a wound.
3955

4056
Concepts
4157
--------
@@ -47,10 +63,12 @@ Acquire context: To ensure eventual forward progress it is important the a task
4763
trying to acquire locks doesn't grab a new reservation id, but keeps the one it
4864
acquired when starting the lock acquisition. This ticket is stored in the
4965
acquire context. Furthermore the acquire context keeps track of debugging state
50-
to catch w/w mutex interface abuse.
66+
to catch w/w mutex interface abuse. An acquire context is representing a
67+
transaction.
5168

5269
W/w class: In contrast to normal mutexes the lock class needs to be explicit for
53-
w/w mutexes, since it is required to initialize the acquire context.
70+
w/w mutexes, since it is required to initialize the acquire context. The lock
71+
class also specifies what algorithm to use, Wound-Wait or Wait-Die.
5472

5573
Furthermore there are three different class of w/w lock acquire functions:
5674

@@ -90,6 +108,12 @@ provided.
90108
Usage
91109
-----
92110

111+
The algorithm (Wait-Die vs Wound-Wait) is chosen by using either
112+
DEFINE_WW_CLASS() (Wound-Wait) or DEFINE_WD_CLASS() (Wait-Die)
113+
As a rough rule of thumb, use Wound-Wait iff you
114+
expect the number of simultaneous competing transactions to be typically small,
115+
and you want to reduce the number of rollbacks.
116+
93117
Three different ways to acquire locks within the same w/w class. Common
94118
definitions for methods #1 and #2:
95119

@@ -312,12 +336,23 @@ Design:
312336
We maintain the following invariants for the wait list:
313337
(1) Waiters with an acquire context are sorted by stamp order; waiters
314338
without an acquire context are interspersed in FIFO order.
315-
(2) Among waiters with contexts, only the first one can have other locks
316-
acquired already (ctx->acquired > 0). Note that this waiter may come
317-
after other waiters without contexts in the list.
339+
(2) For Wait-Die, among waiters with contexts, only the first one can have
340+
other locks acquired already (ctx->acquired > 0). Note that this waiter
341+
may come after other waiters without contexts in the list.
342+
343+
The Wound-Wait preemption is implemented with a lazy-preemption scheme:
344+
The wounded status of the transaction is checked only when there is
345+
contention for a new lock and hence a true chance of deadlock. In that
346+
situation, if the transaction is wounded, it backs off, clears the
347+
wounded status and retries. A great benefit of implementing preemption in
348+
this way is that the wounded transaction can identify a contending lock to
349+
wait for before restarting the transaction. Just blindly restarting the
350+
transaction would likely make the transaction end up in a situation where
351+
it would have to back off again.
318352

319353
In general, not much contention is expected. The locks are typically used to
320-
serialize access to resources for devices.
354+
serialize access to resources for devices, and optimization focus should
355+
therefore be directed towards the uncontended cases.
321356

322357
Lockdep:
323358
Special care has been taken to warn for as many cases of api abuse

‎drivers/dma-buf/reservation.c

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -46,7 +46,7 @@
4646
* write-side updates.
4747
*/
4848

49-
DEFINE_WW_CLASS(reservation_ww_class);
49+
DEFINE_WD_CLASS(reservation_ww_class);
5050
EXPORT_SYMBOL(reservation_ww_class);
5151

5252
struct lock_class_key reservation_seqcount_class;

‎drivers/gpu/drm/drm_modeset_lock.c

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -70,7 +70,7 @@
7070
* lists and lookup data structures.
7171
*/
7272

73-
static DEFINE_WW_CLASS(crtc_ww_class);
73+
static DEFINE_WD_CLASS(crtc_ww_class);
7474

7575
/**
7676
* drm_modeset_lock_all - take all modeset locks

‎include/linux/ww_mutex.h

Lines changed: 14 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,8 @@
88
*
99
* Wait/Die implementation:
1010
* Copyright (C) 2013 Canonical Ltd.
11+
* Choice of algorithm:
12+
* Copyright (C) 2018 WMWare Inc.
1113
*
1214
* This file contains the main data structure and API definitions.
1315
*/
@@ -23,12 +25,15 @@ struct ww_class {
2325
struct lock_class_key mutex_key;
2426
const char *acquire_name;
2527
const char *mutex_name;
28+
unsigned int is_wait_die;
2629
};
2730

2831
struct ww_acquire_ctx {
2932
struct task_struct *task;
3033
unsigned long stamp;
3134
unsigned int acquired;
35+
unsigned short wounded;
36+
unsigned short is_wait_die;
3237
#ifdef CONFIG_DEBUG_MUTEXES
3338
unsigned int done_acquire;
3439
struct ww_class *ww_class;
@@ -58,17 +63,21 @@ struct ww_mutex {
5863
# define __WW_CLASS_MUTEX_INITIALIZER(lockname, class)
5964
#endif
6065

61-
#define __WW_CLASS_INITIALIZER(ww_class) \
66+
#define __WW_CLASS_INITIALIZER(ww_class, _is_wait_die) \
6267
{ .stamp = ATOMIC_LONG_INIT(0) \
6368
, .acquire_name = #ww_class "_acquire" \
64-
, .mutex_name = #ww_class "_mutex" }
69+
, .mutex_name = #ww_class "_mutex" \
70+
, .is_wait_die = _is_wait_die }
6571

6672
#define __WW_MUTEX_INITIALIZER(lockname, class) \
6773
{ .base = __MUTEX_INITIALIZER(lockname.base) \
6874
__WW_CLASS_MUTEX_INITIALIZER(lockname, class) }
6975

76+
#define DEFINE_WD_CLASS(classname) \
77+
struct ww_class classname = __WW_CLASS_INITIALIZER(classname, 1)
78+
7079
#define DEFINE_WW_CLASS(classname) \
71-
struct ww_class classname = __WW_CLASS_INITIALIZER(classname)
80+
struct ww_class classname = __WW_CLASS_INITIALIZER(classname, 0)
7281

7382
#define DEFINE_WW_MUTEX(mutexname, ww_class) \
7483
struct ww_mutex mutexname = __WW_MUTEX_INITIALIZER(mutexname, ww_class)
@@ -123,6 +132,8 @@ static inline void ww_acquire_init(struct ww_acquire_ctx *ctx,
123132
ctx->task = current;
124133
ctx->stamp = atomic_long_inc_return_relaxed(&ww_class->stamp);
125134
ctx->acquired = 0;
135+
ctx->wounded = false;
136+
ctx->is_wait_die = ww_class->is_wait_die;
126137
#ifdef CONFIG_DEBUG_MUTEXES
127138
ctx->ww_class = ww_class;
128139
ctx->done_acquire = 0;

‎kernel/locking/locktorture.c

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -365,7 +365,7 @@ static struct lock_torture_ops mutex_lock_ops = {
365365
};
366366

367367
#include <linux/ww_mutex.h>
368-
static DEFINE_WW_CLASS(torture_ww_class);
368+
static DEFINE_WD_CLASS(torture_ww_class);
369369
static DEFINE_WW_MUTEX(torture_ww_mutex_0, &torture_ww_class);
370370
static DEFINE_WW_MUTEX(torture_ww_mutex_1, &torture_ww_class);
371371
static DEFINE_WW_MUTEX(torture_ww_mutex_2, &torture_ww_class);

0 commit comments

Comments
 (0)