1 /* SPDX-License-Identifier: GPL-2.0-only */
9 __ww_waiter_first(struct mutex *lock)  in __ww_waiter_first()  argument
13 	w = list_first_entry(&lock->wait_list, struct mutex_waiter, list);  in __ww_waiter_first()
14 	if (list_entry_is_head(w, &lock->wait_list, list))  in __ww_waiter_first()
21 __ww_waiter_next(struct mutex *lock, struct mutex_waiter *w)  in __ww_waiter_next()  argument
24 	if (list_entry_is_head(w, &lock->wait_list, list))  in __ww_waiter_next()
31 __ww_waiter_prev(struct mutex *lock, struct mutex_waiter *w)  in __ww_waiter_prev()  argument
34 	if (list_entry_is_head(w, &lock->wait_list, list))  in __ww_waiter_prev()
41 __ww_waiter_last(struct mutex *lock)  in __ww_waiter_last()  argument
45 	w = list_last_entry(&lock->wait_list, struct mutex_waiter, list);  in __ww_waiter_last()
46 	if (list_entry_is_head(w, &lock->wait_list, list))  in __ww_waiter_last()
53 __ww_waiter_add(struct mutex *lock, struct mutex_waiter *waiter, struct mutex_waiter *pos)  in __ww_waiter_add()  argument
55 	struct list_head *p = &lock->wait_list;  in __ww_waiter_add()
57 		p = &pos->list;  in __ww_waiter_add()
58 	__mutex_add_waiter(lock, waiter, p);  in __ww_waiter_add()
62 __ww_mutex_owner(struct mutex *lock)  in __ww_mutex_owner()  argument
64 	return __mutex_owner(lock);  in __ww_mutex_owner()
68 __ww_mutex_has_waiters(struct mutex *lock)  in __ww_mutex_has_waiters()  argument
70 	return atomic_long_read(&lock->owner) & MUTEX_FLAG_WAITERS;  in __ww_mutex_has_waiters()
73 static inline void lock_wait_lock(struct mutex *lock, unsigned long *flags)  in lock_wait_lock()  argument
75 	raw_spin_lock_irqsave(&lock->wait_lock, *flags);  in lock_wait_lock()
78 static inline void unlock_wait_lock(struct mutex *lock, unsigned long *flags)  in unlock_wait_lock()  argument
80 	raw_spin_unlock_irqrestore(&lock->wait_lock, *flags);  in unlock_wait_lock()
83 static inline void lockdep_assert_wait_lock_held(struct mutex *lock)  in lockdep_assert_wait_lock_held()  argument
85 	lockdep_assert_held(&lock->wait_lock);  in lockdep_assert_wait_lock_held()
94 __ww_waiter_first(struct rt_mutex *lock)  in __ww_waiter_first()  argument
96 	struct rb_node *n = rb_first(&lock->rtmutex.waiters.rb_root);  in __ww_waiter_first()
103 __ww_waiter_next(struct rt_mutex *lock, struct rt_mutex_waiter *w)  in __ww_waiter_next()  argument
105 	struct rb_node *n = rb_next(&w->tree.entry);  in __ww_waiter_next()
112 __ww_waiter_prev(struct rt_mutex *lock, struct rt_mutex_waiter *w)  in __ww_waiter_prev()  argument
114 	struct rb_node *n = rb_prev(&w->tree.entry);  in __ww_waiter_prev()
121 __ww_waiter_last(struct rt_mutex *lock)  in __ww_waiter_last()  argument
123 	struct rb_node *n = rb_last(&lock->rtmutex.waiters.rb_root);  in __ww_waiter_last()
130 __ww_waiter_add(struct rt_mutex *lock, struct rt_mutex_waiter *waiter, struct rt_mutex_waiter *pos)  in __ww_waiter_add()  argument
136 __ww_mutex_owner(struct rt_mutex *lock)  in __ww_mutex_owner()  argument
138 	return rt_mutex_owner(&lock->rtmutex);  in __ww_mutex_owner()
142 __ww_mutex_has_waiters(struct rt_mutex *lock)  in __ww_mutex_has_waiters()  argument
144 	return rt_mutex_has_waiters(&lock->rtmutex);  in __ww_mutex_has_waiters()
147 static inline void lock_wait_lock(struct rt_mutex *lock, unsigned long *flags)  in lock_wait_lock()  argument
149 	raw_spin_lock_irqsave(&lock->rtmutex.wait_lock, *flags);  in lock_wait_lock()
152 static inline void unlock_wait_lock(struct rt_mutex *lock, unsigned long *flags)  in unlock_wait_lock()  argument
154 	raw_spin_unlock_irqrestore(&lock->rtmutex.wait_lock, *flags);  in unlock_wait_lock()
157 static inline void lockdep_assert_wait_lock_held(struct rt_mutex *lock)  in lockdep_assert_wait_lock_held()  argument
159 	lockdep_assert_held(&lock->rtmutex.wait_lock);  in lockdep_assert_wait_lock_held()
165  * Wait-Die:
167  *     It (the new transaction) makes a request for a lock being held
170  * Wound-Wait:
172  *     An older transaction makes a request for a lock being held by
190 	DEBUG_LOCKS_WARN_ON(ww->ctx);  in ww_mutex_lock_acquired()
195 	DEBUG_LOCKS_WARN_ON(ww_ctx->done_acquire);  in ww_mutex_lock_acquired()
197 	if (ww_ctx->contending_lock) {  in ww_mutex_lock_acquired()
199 		 * After -EDEADLK you tried to  in ww_mutex_lock_acquired()
202 		DEBUG_LOCKS_WARN_ON(ww_ctx->contending_lock != ww);  in ww_mutex_lock_acquired()
205 		 * You called ww_mutex_lock after receiving -EDEADLK,  in ww_mutex_lock_acquired()
208 		DEBUG_LOCKS_WARN_ON(ww_ctx->acquired > 0);  in ww_mutex_lock_acquired()
209 		ww_ctx->contending_lock = NULL;  in ww_mutex_lock_acquired()
215 	DEBUG_LOCKS_WARN_ON(ww_ctx->ww_class != ww->ww_class);  in ww_mutex_lock_acquired()
217 	ww_ctx->acquired++;  in ww_mutex_lock_acquired()
218 	ww->ctx = ww_ctx;  in ww_mutex_lock_acquired()
222  * Determine if @a is 'less' than @b. IOW, either @a is a lower priority task
231  * Can only do the RT prio for WW_RT, because task->prio isn't stable due to PI,  in __ww_ctx_less()
232  * so the wait_list ordering will go wobbly. rt_mutex re-queues the waiter and  in __ww_ctx_less()
236 	/* kernel prio; less is more */  in __ww_ctx_less()
237 	int a_prio = a->task->prio;  in __ww_ctx_less()
238 	int b_prio = b->task->prio;  in __ww_ctx_less()
251 			if (dl_time_before(b->task->dl.deadline,  in __ww_ctx_less()
252 					   a->task->dl.deadline))  in __ww_ctx_less()
255 			if (dl_time_before(a->task->dl.deadline,  in __ww_ctx_less()
256 					   b->task->dl.deadline))  in __ww_ctx_less()
264 	/* FIFO order tie break -- bigger is younger */  in __ww_ctx_less()
265 	return (signed long)(a->stamp - b->stamp) > 0;  in __ww_ctx_less()
269  * Wait-Die; wake a lesser waiter context (when locks held) such that it can
273  * already (ctx->acquired > 0), because __ww_mutex_add_waiter() and
277 __ww_mutex_die(struct MUTEX *lock, struct MUTEX_WAITER *waiter,  in __ww_mutex_die()  argument
280 	if (!ww_ctx->is_wait_die)  in __ww_mutex_die()
283 	if (waiter->ww_ctx->acquired > 0 && __ww_ctx_less(waiter->ww_ctx, ww_ctx)) {  in __ww_mutex_die()
285 		debug_mutex_wake_waiter(lock, waiter);  in __ww_mutex_die()
287 		wake_q_add(wake_q, waiter->task);  in __ww_mutex_die()
294  * Wound-Wait; wound a lesser @hold_ctx if it holds the lock.
296  * Wound the lock holder if there are waiters with more important transactions
297  * than the lock holders. Even if multiple waiters may wound the lock holder,
300 static bool __ww_mutex_wound(struct MUTEX *lock,  in __ww_mutex_wound()  argument
305 	struct task_struct *owner = __ww_mutex_owner(lock);  in __ww_mutex_wound()
307 	lockdep_assert_wait_lock_held(lock);  in __ww_mutex_wound()
325 	if (ww_ctx->acquired > 0 && __ww_ctx_less(hold_ctx, ww_ctx)) {  in __ww_mutex_wound()
326 		hold_ctx->wounded = 1;  in __ww_mutex_wound()
332 		 * wakeup pending to re-read the wounded state.  in __ww_mutex_wound()
344  * We just acquired @lock under @ww_ctx, if there are more important contexts
345  * waiting behind us on the wait-list, check if they need to die, or wound us.
347  * See __ww_mutex_add_waiter() for the list-order construction; basically the
350  * This relies on never mixing wait-die/wound-wait on the same wait-list;
356 __ww_mutex_check_waiters(struct MUTEX *lock, struct ww_acquire_ctx *ww_ctx,  in __ww_mutex_check_waiters()  argument
361 	lockdep_assert_wait_lock_held(lock);  in __ww_mutex_check_waiters()
363 	for (cur = __ww_waiter_first(lock); cur;  in __ww_mutex_check_waiters()
364 	     cur = __ww_waiter_next(lock, cur)) {  in __ww_mutex_check_waiters()
366 		if (!cur->ww_ctx)  in __ww_mutex_check_waiters()
369 		if (__ww_mutex_die(lock, cur, ww_ctx, wake_q) ||  in __ww_mutex_check_waiters()
370 		    __ww_mutex_wound(lock, cur->ww_ctx, ww_ctx, wake_q))  in __ww_mutex_check_waiters()
376  * After acquiring lock with fastpath, where we do not hold wait_lock, set ctx
380 ww_mutex_set_context_fastpath(struct ww_mutex *lock, struct ww_acquire_ctx *ctx)  in ww_mutex_set_context_fastpath()  argument
385 	ww_mutex_lock_acquired(lock, ctx);  in ww_mutex_set_context_fastpath()
388 	 * The lock->ctx update should be visible on all cores before  in ww_mutex_set_context_fastpath()
397 	 * [W] ww->ctx = ctx	    [W] MUTEX_FLAG_WAITERS  in ww_mutex_set_context_fastpath()
399 	 * [R] MUTEX_FLAG_WAITERS   [R] ww->ctx  in ww_mutex_set_context_fastpath()
402 	 * __ww_mutex_add_waiter() and makes sure we either observe ww->ctx  in ww_mutex_set_context_fastpath()
405 	if (likely(!__ww_mutex_has_waiters(&lock->base)))  in ww_mutex_set_context_fastpath()
412 	lock_wait_lock(&lock->base, &flags);  in ww_mutex_set_context_fastpath()
413 	__ww_mutex_check_waiters(&lock->base, ctx, &wake_q);  in ww_mutex_set_context_fastpath()
415 	unlock_wait_lock(&lock->base, &flags);  in ww_mutex_set_context_fastpath()
421 __ww_mutex_kill(struct MUTEX *lock, struct ww_acquire_ctx *ww_ctx)  in __ww_mutex_kill()  argument
423 	if (ww_ctx->acquired > 0) {  in __ww_mutex_kill()
427 		ww = container_of(lock, struct ww_mutex, base);  in __ww_mutex_kill()
428 		DEBUG_LOCKS_WARN_ON(ww_ctx->contending_lock);  in __ww_mutex_kill()
429 		ww_ctx->contending_lock = ww;  in __ww_mutex_kill()
431 		return -EDEADLK;  in __ww_mutex_kill()
438  * Check the wound condition for the current lock acquire.
440  * Wound-Wait: If we're wounded, kill ourself.
442  * Wait-Die: If we're trying to acquire a lock already held by an older
445  * Since __ww_mutex_add_waiter() orders the wait-list on stamp, we only have to
446  * look at waiters before us in the wait-list.
449 __ww_mutex_check_kill(struct MUTEX *lock, struct MUTEX_WAITER *waiter,  in __ww_mutex_check_kill()  argument
452 	struct ww_mutex *ww = container_of(lock, struct ww_mutex, base);  in __ww_mutex_check_kill()
453 	struct ww_acquire_ctx *hold_ctx = READ_ONCE(ww->ctx);  in __ww_mutex_check_kill()
456 	if (ctx->acquired == 0)  in __ww_mutex_check_kill()
459 	if (!ctx->is_wait_die) {  in __ww_mutex_check_kill()
460 		if (ctx->wounded)  in __ww_mutex_check_kill()
461 			return __ww_mutex_kill(lock, ctx);  in __ww_mutex_check_kill()
467 		return __ww_mutex_kill(lock, ctx);  in __ww_mutex_check_kill()
473 	for (cur = __ww_waiter_prev(lock, waiter); cur;  in __ww_mutex_check_kill()
474 	     cur = __ww_waiter_prev(lock, cur)) {  in __ww_mutex_check_kill()
476 		if (!cur->ww_ctx)  in __ww_mutex_check_kill()
479 		return __ww_mutex_kill(lock, ctx);  in __ww_mutex_check_kill()
486  * Add @waiter to the wait-list, keep the wait-list ordered by stamp, smallest
487  * first. Such that older contexts are preferred to acquire the lock over
492  * Furthermore, for Wait-Die kill ourself immediately when possible (there are
494  * Wound-Wait ensure we wound the owning context when it is younger.
498 		      struct MUTEX *lock,  in __ww_mutex_add_waiter()  argument
506 		__ww_waiter_add(lock, waiter, NULL);  in __ww_mutex_add_waiter()
510 	is_wait_die = ww_ctx->is_wait_die;  in __ww_mutex_add_waiter()
515 	 * them. Wait-Die waiters may die here. Wound-Wait waiters  in __ww_mutex_add_waiter()
517 	 * may wound the lock holder.  in __ww_mutex_add_waiter()
519 	for (cur = __ww_waiter_last(lock); cur;  in __ww_mutex_add_waiter()
520 	     cur = __ww_waiter_prev(lock, cur)) {  in __ww_mutex_add_waiter()
522 		if (!cur->ww_ctx)  in __ww_mutex_add_waiter()
525 		if (__ww_ctx_less(ww_ctx, cur->ww_ctx)) {  in __ww_mutex_add_waiter()
527 			 * Wait-Die: if we find an older context waiting, there  in __ww_mutex_add_waiter()
529 			 * die the moment it would acquire the lock.  in __ww_mutex_add_waiter()
532 				int ret = __ww_mutex_kill(lock, ww_ctx);  in __ww_mutex_add_waiter()
543 		/* Wait-Die: ensure younger waiters die. */  in __ww_mutex_add_waiter()
544 		__ww_mutex_die(lock, cur, ww_ctx, wake_q);  in __ww_mutex_add_waiter()
547 	__ww_waiter_add(lock, waiter, pos);  in __ww_mutex_add_waiter()
550 	 * Wound-Wait: if we're blocking on a mutex owned by a younger context,  in __ww_mutex_add_waiter()
554 		struct ww_mutex *ww = container_of(lock, struct ww_mutex, base);  in __ww_mutex_add_waiter()
558 		 * MUTEX_FLAG_WAITERS vs the ww->ctx load,  in __ww_mutex_add_waiter()
559 		 * such that either we or the fastpath will wound @ww->ctx.  in __ww_mutex_add_waiter()
562 		__ww_mutex_wound(lock, ww_ctx, ww->ctx, wake_q);  in __ww_mutex_add_waiter()
568 static inline void __ww_mutex_unlock(struct ww_mutex *lock)  in __ww_mutex_unlock()  argument
570 	if (lock->ctx) {  in __ww_mutex_unlock()
572 		DEBUG_LOCKS_WARN_ON(!lock->ctx->acquired);  in __ww_mutex_unlock()
574 		if (lock->ctx->acquired > 0)  in __ww_mutex_unlock()
575 			lock->ctx->acquired--;  in __ww_mutex_unlock()
576 		lock->ctx = NULL;  in __ww_mutex_unlock()