1  /* SPDX-License-Identifier: GPL-2.0 */
2  /*
3   * Wound/Wait Mutexes: blocking mutual exclusion locks with deadlock avoidance
4   *
5   * Original mutex implementation started by Ingo Molnar:
6   *
7   *  Copyright (C) 2004, 2005, 2006 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
8   *
9   * Wait/Die implementation:
10   *  Copyright (C) 2013 Canonical Ltd.
11   * Choice of algorithm:
12   *  Copyright (C) 2018 WMWare Inc.
13   *
14   * This file contains the main data structure and API definitions.
15   */
16  
17  #ifndef __LINUX_WW_MUTEX_H
18  #define __LINUX_WW_MUTEX_H
19  
20  #include <linux/mutex.h>
21  #include <linux/rtmutex.h>
22  
23  #if defined(CONFIG_DEBUG_MUTEXES) || \
24     (defined(CONFIG_PREEMPT_RT) && defined(CONFIG_DEBUG_RT_MUTEXES))
25  #define DEBUG_WW_MUTEXES
26  #endif
27  
28  #ifndef CONFIG_PREEMPT_RT
29  #define WW_MUTEX_BASE			mutex
30  #define ww_mutex_base_init(l,n,k)	__mutex_init(l,n,k)
31  #define ww_mutex_base_is_locked(b)	mutex_is_locked((b))
32  #else
33  #define WW_MUTEX_BASE			rt_mutex
34  #define ww_mutex_base_init(l,n,k)	__rt_mutex_init(l,n,k)
35  #define ww_mutex_base_is_locked(b)	rt_mutex_base_is_locked(&(b)->rtmutex)
36  #endif
37  
38  struct ww_class {
39  	atomic_long_t stamp;
40  	struct lock_class_key acquire_key;
41  	struct lock_class_key mutex_key;
42  	const char *acquire_name;
43  	const char *mutex_name;
44  	unsigned int is_wait_die;
45  };
46  
47  struct ww_mutex {
48  	struct WW_MUTEX_BASE base;
49  	struct ww_acquire_ctx *ctx;
50  #ifdef DEBUG_WW_MUTEXES
51  	struct ww_class *ww_class;
52  #endif
53  };
54  
55  struct ww_acquire_ctx {
56  	struct task_struct *task;
57  	unsigned long stamp;
58  	unsigned int acquired;
59  	unsigned short wounded;
60  	unsigned short is_wait_die;
61  #ifdef DEBUG_WW_MUTEXES
62  	unsigned int done_acquire;
63  	struct ww_class *ww_class;
64  	void *contending_lock;
65  #endif
66  #ifdef CONFIG_DEBUG_LOCK_ALLOC
67  	struct lockdep_map dep_map;
68  #endif
69  #ifdef CONFIG_DEBUG_WW_MUTEX_SLOWPATH
70  	unsigned int deadlock_inject_interval;
71  	unsigned int deadlock_inject_countdown;
72  #endif
73  };
74  
75  #define __WW_CLASS_INITIALIZER(ww_class, _is_wait_die)	    \
76  		{ .stamp = ATOMIC_LONG_INIT(0) \
77  		, .acquire_name = #ww_class "_acquire" \
78  		, .mutex_name = #ww_class "_mutex" \
79  		, .is_wait_die = _is_wait_die }
80  
81  #define DEFINE_WD_CLASS(classname) \
82  	struct ww_class classname = __WW_CLASS_INITIALIZER(classname, 1)
83  
84  #define DEFINE_WW_CLASS(classname) \
85  	struct ww_class classname = __WW_CLASS_INITIALIZER(classname, 0)
86  
87  /**
88   * ww_mutex_init - initialize the w/w mutex
89   * @lock: the mutex to be initialized
90   * @ww_class: the w/w class the mutex should belong to
91   *
92   * Initialize the w/w mutex to unlocked state and associate it with the given
93   * class. Static define macro for w/w mutex is not provided and this function
94   * is the only way to properly initialize the w/w mutex.
95   *
96   * It is not allowed to initialize an already locked mutex.
97   */
ww_mutex_init(struct ww_mutex * lock,struct ww_class * ww_class)98  static inline void ww_mutex_init(struct ww_mutex *lock,
99  				 struct ww_class *ww_class)
100  {
101  	ww_mutex_base_init(&lock->base, ww_class->mutex_name, &ww_class->mutex_key);
102  	lock->ctx = NULL;
103  #ifdef DEBUG_WW_MUTEXES
104  	lock->ww_class = ww_class;
105  #endif
106  }
107  
108  /**
109   * ww_acquire_init - initialize a w/w acquire context
110   * @ctx: w/w acquire context to initialize
111   * @ww_class: w/w class of the context
112   *
113   * Initializes an context to acquire multiple mutexes of the given w/w class.
114   *
115   * Context-based w/w mutex acquiring can be done in any order whatsoever within
116   * a given lock class. Deadlocks will be detected and handled with the
117   * wait/die logic.
118   *
119   * Mixing of context-based w/w mutex acquiring and single w/w mutex locking can
120   * result in undetected deadlocks and is so forbidden. Mixing different contexts
121   * for the same w/w class when acquiring mutexes can also result in undetected
122   * deadlocks, and is hence also forbidden. Both types of abuse will be caught by
123   * enabling CONFIG_PROVE_LOCKING.
124   *
125   * Nesting of acquire contexts for _different_ w/w classes is possible, subject
126   * to the usual locking rules between different lock classes.
127   *
128   * An acquire context must be released with ww_acquire_fini by the same task
129   * before the memory is freed. It is recommended to allocate the context itself
130   * on the stack.
131   */
ww_acquire_init(struct ww_acquire_ctx * ctx,struct ww_class * ww_class)132  static inline void ww_acquire_init(struct ww_acquire_ctx *ctx,
133  				   struct ww_class *ww_class)
134  {
135  	ctx->task = current;
136  	ctx->stamp = atomic_long_inc_return_relaxed(&ww_class->stamp);
137  	ctx->acquired = 0;
138  	ctx->wounded = false;
139  	ctx->is_wait_die = ww_class->is_wait_die;
140  #ifdef DEBUG_WW_MUTEXES
141  	ctx->ww_class = ww_class;
142  	ctx->done_acquire = 0;
143  	ctx->contending_lock = NULL;
144  #endif
145  #ifdef CONFIG_DEBUG_LOCK_ALLOC
146  	debug_check_no_locks_freed((void *)ctx, sizeof(*ctx));
147  	lockdep_init_map(&ctx->dep_map, ww_class->acquire_name,
148  			 &ww_class->acquire_key, 0);
149  	mutex_acquire(&ctx->dep_map, 0, 0, _RET_IP_);
150  #endif
151  #ifdef CONFIG_DEBUG_WW_MUTEX_SLOWPATH
152  	ctx->deadlock_inject_interval = 1;
153  	ctx->deadlock_inject_countdown = ctx->stamp & 0xf;
154  #endif
155  }
156  
157  /**
158   * ww_acquire_done - marks the end of the acquire phase
159   * @ctx: the acquire context
160   *
161   * Marks the end of the acquire phase, any further w/w mutex lock calls using
162   * this context are forbidden.
163   *
164   * Calling this function is optional, it is just useful to document w/w mutex
165   * code and clearly designated the acquire phase from actually using the locked
166   * data structures.
167   */
ww_acquire_done(struct ww_acquire_ctx * ctx)168  static inline void ww_acquire_done(struct ww_acquire_ctx *ctx)
169  {
170  #ifdef DEBUG_WW_MUTEXES
171  	lockdep_assert_held(ctx);
172  
173  	DEBUG_LOCKS_WARN_ON(ctx->done_acquire);
174  	ctx->done_acquire = 1;
175  #endif
176  }
177  
178  /**
179   * ww_acquire_fini - releases a w/w acquire context
180   * @ctx: the acquire context to free
181   *
182   * Releases a w/w acquire context. This must be called _after_ all acquired w/w
183   * mutexes have been released with ww_mutex_unlock.
184   */
ww_acquire_fini(struct ww_acquire_ctx * ctx)185  static inline void ww_acquire_fini(struct ww_acquire_ctx *ctx)
186  {
187  #ifdef CONFIG_DEBUG_LOCK_ALLOC
188  	mutex_release(&ctx->dep_map, _THIS_IP_);
189  #endif
190  #ifdef DEBUG_WW_MUTEXES
191  	DEBUG_LOCKS_WARN_ON(ctx->acquired);
192  	if (!IS_ENABLED(CONFIG_PROVE_LOCKING))
193  		/*
194  		 * lockdep will normally handle this,
195  		 * but fail without anyway
196  		 */
197  		ctx->done_acquire = 1;
198  
199  	if (!IS_ENABLED(CONFIG_DEBUG_LOCK_ALLOC))
200  		/* ensure ww_acquire_fini will still fail if called twice */
201  		ctx->acquired = ~0U;
202  #endif
203  }
204  
205  /**
206   * ww_mutex_lock - acquire the w/w mutex
207   * @lock: the mutex to be acquired
208   * @ctx: w/w acquire context, or NULL to acquire only a single lock.
209   *
210   * Lock the w/w mutex exclusively for this task.
211   *
212   * Deadlocks within a given w/w class of locks are detected and handled with the
213   * wait/die algorithm. If the lock isn't immediately available this function
214   * will either sleep until it is (wait case). Or it selects the current context
215   * for backing off by returning -EDEADLK (die case). Trying to acquire the
216   * same lock with the same context twice is also detected and signalled by
217   * returning -EALREADY. Returns 0 if the mutex was successfully acquired.
218   *
219   * In the die case the caller must release all currently held w/w mutexes for
220   * the given context and then wait for this contending lock to be available by
221   * calling ww_mutex_lock_slow. Alternatively callers can opt to not acquire this
222   * lock and proceed with trying to acquire further w/w mutexes (e.g. when
223   * scanning through lru lists trying to free resources).
224   *
225   * The mutex must later on be released by the same task that
226   * acquired it. The task may not exit without first unlocking the mutex. Also,
227   * kernel memory where the mutex resides must not be freed with the mutex still
228   * locked. The mutex must first be initialized (or statically defined) before it
229   * can be locked. memset()-ing the mutex to 0 is not allowed. The mutex must be
230   * of the same w/w lock class as was used to initialize the acquire context.
231   *
232   * A mutex acquired with this function must be released with ww_mutex_unlock.
233   */
234  extern int /* __must_check */ ww_mutex_lock(struct ww_mutex *lock, struct ww_acquire_ctx *ctx);
235  
236  /**
237   * ww_mutex_lock_interruptible - acquire the w/w mutex, interruptible
238   * @lock: the mutex to be acquired
239   * @ctx: w/w acquire context
240   *
241   * Lock the w/w mutex exclusively for this task.
242   *
243   * Deadlocks within a given w/w class of locks are detected and handled with the
244   * wait/die algorithm. If the lock isn't immediately available this function
245   * will either sleep until it is (wait case). Or it selects the current context
246   * for backing off by returning -EDEADLK (die case). Trying to acquire the
247   * same lock with the same context twice is also detected and signalled by
248   * returning -EALREADY. Returns 0 if the mutex was successfully acquired. If a
249   * signal arrives while waiting for the lock then this function returns -EINTR.
250   *
251   * In the die case the caller must release all currently held w/w mutexes for
252   * the given context and then wait for this contending lock to be available by
253   * calling ww_mutex_lock_slow_interruptible. Alternatively callers can opt to
254   * not acquire this lock and proceed with trying to acquire further w/w mutexes
255   * (e.g. when scanning through lru lists trying to free resources).
256   *
257   * The mutex must later on be released by the same task that
258   * acquired it. The task may not exit without first unlocking the mutex. Also,
259   * kernel memory where the mutex resides must not be freed with the mutex still
260   * locked. The mutex must first be initialized (or statically defined) before it
261   * can be locked. memset()-ing the mutex to 0 is not allowed. The mutex must be
262   * of the same w/w lock class as was used to initialize the acquire context.
263   *
264   * A mutex acquired with this function must be released with ww_mutex_unlock.
265   */
266  extern int __must_check ww_mutex_lock_interruptible(struct ww_mutex *lock,
267  						    struct ww_acquire_ctx *ctx);
268  
269  /**
270   * ww_mutex_lock_slow - slowpath acquiring of the w/w mutex
271   * @lock: the mutex to be acquired
272   * @ctx: w/w acquire context
273   *
274   * Acquires a w/w mutex with the given context after a die case. This function
275   * will sleep until the lock becomes available.
276   *
277   * The caller must have released all w/w mutexes already acquired with the
278   * context and then call this function on the contended lock.
279   *
280   * Afterwards the caller may continue to (re)acquire the other w/w mutexes it
281   * needs with ww_mutex_lock. Note that the -EALREADY return code from
282   * ww_mutex_lock can be used to avoid locking this contended mutex twice.
283   *
284   * It is forbidden to call this function with any other w/w mutexes associated
285   * with the context held. It is forbidden to call this on anything else than the
286   * contending mutex.
287   *
288   * Note that the slowpath lock acquiring can also be done by calling
289   * ww_mutex_lock directly. This function here is simply to help w/w mutex
290   * locking code readability by clearly denoting the slowpath.
291   */
292  static inline void
ww_mutex_lock_slow(struct ww_mutex * lock,struct ww_acquire_ctx * ctx)293  ww_mutex_lock_slow(struct ww_mutex *lock, struct ww_acquire_ctx *ctx)
294  {
295  	int ret;
296  #ifdef DEBUG_WW_MUTEXES
297  	DEBUG_LOCKS_WARN_ON(!ctx->contending_lock);
298  #endif
299  	ret = ww_mutex_lock(lock, ctx);
300  	(void)ret;
301  }
302  
303  /**
304   * ww_mutex_lock_slow_interruptible - slowpath acquiring of the w/w mutex, interruptible
305   * @lock: the mutex to be acquired
306   * @ctx: w/w acquire context
307   *
308   * Acquires a w/w mutex with the given context after a die case. This function
309   * will sleep until the lock becomes available and returns 0 when the lock has
310   * been acquired. If a signal arrives while waiting for the lock then this
311   * function returns -EINTR.
312   *
313   * The caller must have released all w/w mutexes already acquired with the
314   * context and then call this function on the contended lock.
315   *
316   * Afterwards the caller may continue to (re)acquire the other w/w mutexes it
317   * needs with ww_mutex_lock. Note that the -EALREADY return code from
318   * ww_mutex_lock can be used to avoid locking this contended mutex twice.
319   *
320   * It is forbidden to call this function with any other w/w mutexes associated
321   * with the given context held. It is forbidden to call this on anything else
322   * than the contending mutex.
323   *
324   * Note that the slowpath lock acquiring can also be done by calling
325   * ww_mutex_lock_interruptible directly. This function here is simply to help
326   * w/w mutex locking code readability by clearly denoting the slowpath.
327   */
328  static inline int __must_check
ww_mutex_lock_slow_interruptible(struct ww_mutex * lock,struct ww_acquire_ctx * ctx)329  ww_mutex_lock_slow_interruptible(struct ww_mutex *lock,
330  				 struct ww_acquire_ctx *ctx)
331  {
332  #ifdef DEBUG_WW_MUTEXES
333  	DEBUG_LOCKS_WARN_ON(!ctx->contending_lock);
334  #endif
335  	return ww_mutex_lock_interruptible(lock, ctx);
336  }
337  
338  extern void ww_mutex_unlock(struct ww_mutex *lock);
339  
340  extern int __must_check ww_mutex_trylock(struct ww_mutex *lock,
341  					 struct ww_acquire_ctx *ctx);
342  
343  /***
344   * ww_mutex_destroy - mark a w/w mutex unusable
345   * @lock: the mutex to be destroyed
346   *
347   * This function marks the mutex uninitialized, and any subsequent
348   * use of the mutex is forbidden. The mutex must not be locked when
349   * this function is called.
350   */
ww_mutex_destroy(struct ww_mutex * lock)351  static inline void ww_mutex_destroy(struct ww_mutex *lock)
352  {
353  #ifndef CONFIG_PREEMPT_RT
354  	mutex_destroy(&lock->base);
355  #endif
356  }
357  
358  /**
359   * ww_mutex_is_locked - is the w/w mutex locked
360   * @lock: the mutex to be queried
361   *
362   * Returns 1 if the mutex is locked, 0 if unlocked.
363   */
ww_mutex_is_locked(struct ww_mutex * lock)364  static inline bool ww_mutex_is_locked(struct ww_mutex *lock)
365  {
366  	return ww_mutex_base_is_locked(&lock->base);
367  }
368  
369  #endif
370