// SPDX-License-Identifier: GPL-2.0-only/* * RT-Mutexes: simple blocking mutual exclusion locks with PI support * * started by Ingo Molnar and Thomas Gleixner. * *  Copyright (C) 2004-2006 Red Hat, Inc., Ingo Molnar <mingo@redhat.com> *  Copyright (C) 2005-2006 Timesys Corp., Thomas Gleixner <tglx@timesys.com> *  Copyright (C) 2005 Kihon Technologies Inc., Steven Rostedt *  Copyright (C) 2006 Esben Nielsen * Adaptive Spinlocks: *  Copyright (C) 2008 Novell, Inc., Gregory Haskins, Sven Dietrich, *				     and Peter Morreale, * Adaptive Spinlocks simplification: *  Copyright (C) 2008 Red Hat, Inc., Steven Rostedt <srostedt@redhat.com> * *  See Documentation/locking/rt-mutex-design.rst for details. */#include <linux/sched.h>#include <linux/sched/debug.h>#include <linux/sched/deadline.h>#include <linux/sched/signal.h>#include <linux/sched/rt.h>#include <linux/sched/wake_q.h>#include <linux/ww_mutex.h> #include <trace/events/lock.h> #include "rtmutex_common.h"#include "lock_events.h" #ifndef WW_RT# define build_ww_mutex()	(false)# define ww_container_of(rtm)	NULL static inline int __ww_mutex_add_waiter(struct rt_mutex_waiter *waiter,					struct rt_mutex *lock,					struct ww_acquire_ctx *ww_ctx,					struct wake_q_head *wake_q){	return 0;} static inline void __ww_mutex_check_waiters(struct rt_mutex *lock,					    struct ww_acquire_ctx *ww_ctx,					    struct wake_q_head *wake_q){} static inline void ww_mutex_lock_acquired(struct ww_mutex *lock,					  struct ww_acquire_ctx *ww_ctx){} static inline int __ww_mutex_check_kill(struct rt_mutex *lock,					struct rt_mutex_waiter *waiter,					struct ww_acquire_ctx *ww_ctx){	return 0;} #else# define build_ww_mutex()	(true)# define ww_container_of(rtm)	container_of(rtm, struct ww_mutex, base)# include "ww_mutex.h"#endif /* * lock->owner state tracking: * * lock->owner holds the task_struct pointer of the owner. Bit 0 * is used to keep track of the "lock has waiters" state. * * owner	bit0 * NULL		0	lock is free (fast acquire possible) * NULL		1	lock is free and has waiters and the top waiter *				is going to take the lock* * taskpointer	0	lock is held (fast release possible) * taskpointer	1	lock is held and has waiters** * * The fast atomic compare exchange based acquire and release is only * possible when bit 0 of lock->owner is 0. * * (*) It also can be a transitional state when grabbing the lock * with ->wait_lock is held. To prevent any fast path cmpxchg to the lock, * we need to set the bit0 before looking at the lock, and the owner may be * NULL in this small time, hence this can be a transitional state. * * (**) There is a small time when bit 0 is set but there are no * waiters. This can happen when grabbing the lock in the slow path. * To prevent a cmpxchg of the owner releasing the lock, we need to * set this bit before looking at the lock. */ static __always_inline struct task_struct *rt_mutex_owner_encode(struct rt_mutex_base *lock, struct task_struct *owner)	__must_hold(&lock->wait_lock){	unsigned long val = (unsigned long)owner; 	if (rt_mutex_has_waiters(lock))		val |= RT_MUTEX_HAS_WAITERS; 	return (struct task_struct *)val;} static __always_inline voidrt_mutex_set_owner(struct rt_mutex_base *lock, struct task_struct *owner)	__must_hold(&lock->wait_lock){	/*	 * lock->wait_lock is held but explicit acquire semantics are needed	 * for a new lock owner so WRITE_ONCE is insufficient.	 */	xchg_acquire(&lock->owner, rt_mutex_owner_encode(lock, owner));} static __always_inline void rt_mutex_clear_owner(struct rt_mutex_base *lock)	__must_hold(&lock->wait_lock){	/* lock->wait_lock is held so the unlock provides release semantics. */	WRITE_ONCE(lock->owner, rt_mutex_owner_encode(lock, NULL));} static __always_inline void clear_rt_mutex_waiters(struct rt_mutex_base *lock)	__must_hold(&lock->wait_lock){	lock->owner = (struct task_struct *)			((unsigned long)lock->owner & ~RT_MUTEX_HAS_WAITERS);} static __always_inline voidfixup_rt_mutex_waiters(struct rt_mutex_base *lock, bool acquire_lock)	__must_hold(&lock->wait_lock){	unsigned long owner, *p = (unsigned long *) &lock->owner; 	if (rt_mutex_has_waiters(lock))		return; 	/*	 * The rbtree has no waiters enqueued, now make sure that the	 * lock->owner still has the waiters bit set, otherwise the	 * following can happen:	 *	 * CPU 0	CPU 1		CPU2	 * l->owner=T1	 *		rt_mutex_lock(l)	 *		lock(l->lock)	 *		l->owner = T1 | HAS_WAITERS;	 *		enqueue(T2)	 *		boost()	 *		  unlock(l->lock)	 *		block()	 *	 *				rt_mutex_lock(l)	 *				lock(l->lock)	 *				l->owner = T1 | HAS_WAITERS;	 *				enqueue(T3)	 *				boost()	 *				  unlock(l->lock)	 *				block()	 *		signal(->T2)	signal(->T3)	 *		lock(l->lock)	 *		dequeue(T2)	 *		deboost()	 *		  unlock(l->lock)	 *				lock(l->lock)	 *				dequeue(T3)	 *				 ==> wait list is empty	 *				deboost()	 *				 unlock(l->lock)	 *		lock(l->lock)	 *		fixup_rt_mutex_waiters()	 *		  if (wait_list_empty(l) {	 *		    l->owner = owner	 *		    owner = l->owner & ~HAS_WAITERS;	 *		      ==> l->owner = T1	 *		  }	 *				lock(l->lock)	 * rt_mutex_unlock(l)		fixup_rt_mutex_waiters()	 *				  if (wait_list_empty(l) {	 *				    owner = l->owner & ~HAS_WAITERS;	 * cmpxchg(l->owner, T1, NULL)	 *  ===> Success (l->owner = NULL)	 *	 *				    l->owner = owner	 *				      ==> l->owner = T1	 *				  }	 *	 * With the check for the waiter bit in place T3 on CPU2 will not	 * overwrite. All tasks fiddling with the waiters bit are	 * serialized by l->lock, so nothing else can modify the waiters	 * bit. If the bit is set then nothing can change l->owner either	 * so the simple RMW is safe. The cmpxchg() will simply fail if it	 * happens in the middle of the RMW because the waiters bit is	 * still set.	 */	owner = READ_ONCE(*p);	if (owner & RT_MUTEX_HAS_WAITERS) {		/*		 * See rt_mutex_set_owner() and rt_mutex_clear_owner() on		 * why xchg_acquire() is used for updating owner for		 * locking and WRITE_ONCE() for unlocking.		 *		 * WRITE_ONCE() would work for the acquire case too, but		 * in case that the lock acquisition failed it might		 * force other lockers into the slow path unnecessarily.		 */		if (acquire_lock)			xchg_acquire(p, owner & ~RT_MUTEX_HAS_WAITERS);		else			WRITE_ONCE(*p, owner & ~RT_MUTEX_HAS_WAITERS);	}} /* * We can speed up the acquire/release, if there's no debugging state to be * set up. */#ifndef CONFIG_DEBUG_RT_MUTEXESstatic __always_inline bool rt_mutex_cmpxchg_acquire(struct rt_mutex_base *lock,						     struct task_struct *old,						     struct task_struct *new){	return try_cmpxchg_acquire(&lock->owner, &old, new);} static __always_inline bool rt_mutex_try_acquire(struct rt_mutex_base *lock){	return rt_mutex_cmpxchg_acquire(lock, NULL, current);} static __always_inline bool rt_mutex_cmpxchg_release(struct rt_mutex_base *lock,						     struct task_struct *old,						     struct task_struct *new){	return try_cmpxchg_release(&lock->owner, &old, new);} /* * Callers must hold the ->wait_lock -- which is the whole purpose as we force * all future threads that attempt to [Rmw] the lock to the slowpath. As such * relaxed semantics suffice. */static __always_inline void mark_rt_mutex_waiters(struct rt_mutex_base *lock){	unsigned long *p = (unsigned long *) &lock->owner;	unsigned long owner, new; 	owner = READ_ONCE(*p);	do {		new = owner | RT_MUTEX_HAS_WAITERS;	} while (!try_cmpxchg_relaxed(p, &owner, new)); 	/*	 * The cmpxchg loop above is relaxed to avoid back-to-back ACQUIRE	 * operations in the event of contention. Ensure the successful	 * cmpxchg is visible.	 */	smp_mb__after_atomic();} /* * Safe fastpath aware unlock: * 1) Clear the waiters bit * 2) Drop lock->wait_lock * 3) Try to unlock the lock with cmpxchg */static __always_inline bool unlock_rt_mutex_safe(struct rt_mutex_base *lock,						 unsigned long flags)	__releases(lock->wait_lock){	struct task_struct *owner = rt_mutex_owner(lock); 	clear_rt_mutex_waiters(lock);	raw_spin_unlock_irqrestore(&lock->wait_lock, flags);	/*	 * If a new waiter comes in between the unlock and the cmpxchg	 * we have two situations:	 *	 * unlock(wait_lock);	 *					lock(wait_lock);	 * cmpxchg(p, owner, 0) == owner	 *					mark_rt_mutex_waiters(lock);	 *					acquire(lock);	 * or:	 *	 * unlock(wait_lock);	 *					lock(wait_lock);	 *					mark_rt_mutex_waiters(lock);	 *	 * cmpxchg(p, owner, 0) != owner	 *					enqueue_waiter();	 *					unlock(wait_lock);	 * lock(wait_lock);	 * wake waiter();	 * unlock(wait_lock);	 *					lock(wait_lock);	 *					acquire(lock);	 */	return rt_mutex_cmpxchg_release(lock, owner, NULL);} #elsestatic __always_inline bool rt_mutex_cmpxchg_acquire(struct rt_mutex_base *lock,						     struct task_struct *old,						     struct task_struct *new){	return false; } static int __sched rt_mutex_slowtrylock(struct rt_mutex_base *lock); static __always_inline bool rt_mutex_try_acquire(struct rt_mutex_base *lock){	/*	 * With debug enabled rt_mutex_cmpxchg trylock() will always fail.	 *	 * Avoid unconditionally taking the slow path by using	 * rt_mutex_slow_trylock() which is covered by the debug code and can	 * acquire a non-contended rtmutex.	 */	return rt_mutex_slowtrylock(lock);} static __always_inline bool rt_mutex_cmpxchg_release(struct rt_mutex_base *lock,						     struct task_struct *old,						     struct task_struct *new){	return false;} static __always_inline void mark_rt_mutex_waiters(struct rt_mutex_base *lock)	__must_hold(&lock->wait_lock){	lock->owner = (struct task_struct *)			((unsigned long)lock->owner | RT_MUTEX_HAS_WAITERS);} /* * Simple slow path only version: lock->owner is protected by lock->wait_lock. */static __always_inline bool unlock_rt_mutex_safe(struct rt_mutex_base *lock,						 unsigned long flags)	__releases(lock->wait_lock){	lock->owner = NULL;	raw_spin_unlock_irqrestore(&lock->wait_lock, flags);	return true;}#endif static __always_inline int __waiter_prio(struct task_struct *task){	int prio = task->prio; 	if (!rt_or_dl_prio(prio))		return DEFAULT_PRIO; 	return prio;} /* * Update the waiter->tree copy of the sort keys. */static __always_inline voidwaiter_update_prio(struct rt_mutex_waiter *waiter, struct task_struct *task){	lockdep_assert_held(&waiter->lock->wait_lock);	lockdep_assert(RB_EMPTY_NODE(&waiter->tree.entry)); 	waiter->tree.prio = __waiter_prio(task);	waiter->tree.deadline = task->dl.deadline;} /* * Update the waiter->pi_tree copy of the sort keys (from the tree copy). */static __always_inline voidwaiter_clone_prio(struct rt_mutex_waiter *waiter, struct task_struct *task){	lockdep_assert_held(&waiter->lock->wait_lock);	lockdep_assert_held(&task->pi_lock);	lockdep_assert(RB_EMPTY_NODE(&waiter->pi_tree.entry)); 	waiter->pi_tree.prio = waiter->tree.prio;	waiter->pi_tree.deadline = waiter->tree.deadline;} /* * Only use with rt_waiter_node_{less,equal}() */#define task_to_waiter_node(p)	\	&(struct rt_waiter_node){ .prio = __waiter_prio(p), .deadline = (p)->dl.deadline }#define task_to_waiter(p)	\	&(struct rt_mutex_waiter){ .tree = *task_to_waiter_node(p) } static __always_inline int rt_waiter_node_less(struct rt_waiter_node *left,					       struct rt_waiter_node *right){	if (left->prio < right->prio)		return 1; 	/*	 * If both waiters have dl_prio(), we check the deadlines of the	 * associated tasks.	 * If left waiter has a dl_prio(), and we didn't return 1 above,	 * then right waiter has a dl_prio() too.	 */	if (dl_prio(left->prio))		return dl_time_before(left->deadline, right->deadline); 	return 0;} static __always_inline int rt_waiter_node_equal(struct rt_waiter_node *left,						 struct rt_waiter_node *right){	if (left->prio != right->prio)		return 0; 	/*	 * If both waiters have dl_prio(), we check the deadlines of the	 * associated tasks.	 * If left waiter has a dl_prio(), and we didn't return 0 above,	 * then right waiter has a dl_prio() too.	 */	if (dl_prio(left->prio))		return left->deadline == right->deadline; 	return 1;} static inline bool rt_mutex_steal(struct rt_mutex_waiter *waiter,				  struct rt_mutex_waiter *top_waiter){	if (rt_waiter_node_less(&waiter->tree, &top_waiter->tree))		return true; #ifdef RT_MUTEX_BUILD_SPINLOCKS	/*	 * Note that RT tasks are excluded from same priority (lateral)	 * steals to prevent the introduction of an unbounded latency.	 */	if (rt_or_dl_prio(waiter->tree.prio))		return false; 	return rt_waiter_node_equal(&waiter->tree, &top_waiter->tree);#else	return false;#endif} #define __node_2_waiter(node) \	rb_entry((node), struct rt_mutex_waiter, tree.entry) static __always_inline bool __waiter_less(struct rb_node *a, const struct rb_node *b){	struct rt_mutex_waiter *aw = __node_2_waiter(a);	struct rt_mutex_waiter *bw = __node_2_waiter(b); 	if (rt_waiter_node_less(&aw->tree, &bw->tree))		return 1; 	if (!build_ww_mutex())		return 0; 	if (rt_waiter_node_less(&bw->tree, &aw->tree))		return 0; 	/* NOTE: relies on waiter->ww_ctx being set before insertion */	if (aw->ww_ctx) {		if (!bw->ww_ctx)			return 1; 		return (signed long)(aw->ww_ctx->stamp -				     bw->ww_ctx->stamp) < 0;	} 	return 0;} static __always_inline voidrt_mutex_enqueue(struct rt_mutex_base *lock, struct rt_mutex_waiter *waiter){	lockdep_assert_held(&lock->wait_lock); 	rb_add_cached(&waiter->tree.entry, &lock->waiters, __waiter_less);} static __always_inline voidrt_mutex_dequeue(struct rt_mutex_base *lock, struct rt_mutex_waiter *waiter){	lockdep_assert_held(&lock->wait_lock); 	if (RB_EMPTY_NODE(&waiter->tree.entry))		return; 

Lines 1–500 of 1921. Load more