/* * 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 * *  See Documentation/locking/rt-mutex-design.txt for details. */#include <linux/spinlock.h>#include <linux/export.h>#include <linux/sched.h>#include <linux/sched/rt.h>#include <linux/sched/deadline.h>#include <linux/timer.h> #include "rtmutex_common.h" /* * 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 voidrt_mutex_set_owner(struct rt_mutex *lock, struct task_struct *owner){	unsigned long val = (unsigned long)owner; 	if (rt_mutex_has_waiters(lock))		val |= RT_MUTEX_HAS_WAITERS; 	lock->owner = (struct task_struct *)val;} static inline void clear_rt_mutex_waiters(struct rt_mutex *lock){	lock->owner = (struct task_struct *)			((unsigned long)lock->owner & ~RT_MUTEX_HAS_WAITERS);} static void fixup_rt_mutex_waiters(struct rt_mutex *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)		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_MUTEXES# define rt_mutex_cmpxchg_relaxed(l,c,n) (cmpxchg_relaxed(&l->owner, c, n) == c)# define rt_mutex_cmpxchg_acquire(l,c,n) (cmpxchg_acquire(&l->owner, c, n) == c)# define rt_mutex_cmpxchg_release(l,c,n) (cmpxchg_release(&l->owner, c, n) == c) /* * 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 inline void mark_rt_mutex_waiters(struct rt_mutex *lock){	unsigned long owner, *p = (unsigned long *) &lock->owner; 	do {		owner = *p;	} while (cmpxchg_relaxed(p, owner,				 owner | RT_MUTEX_HAS_WAITERS) != owner);} /* * Safe fastpath aware unlock: * 1) Clear the waiters bit * 2) Drop lock->wait_lock * 3) Try to unlock the lock with cmpxchg */static inline bool unlock_rt_mutex_safe(struct rt_mutex *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);} #else# define rt_mutex_cmpxchg_relaxed(l,c,n)	(0)# define rt_mutex_cmpxchg_acquire(l,c,n)	(0)# define rt_mutex_cmpxchg_release(l,c,n)	(0) static inline void mark_rt_mutex_waiters(struct rt_mutex *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 inline bool unlock_rt_mutex_safe(struct rt_mutex *lock,					unsigned long flags)	__releases(lock->wait_lock){	lock->owner = NULL;	raw_spin_unlock_irqrestore(&lock->wait_lock, flags);	return true;}#endif static inline intrt_mutex_waiter_less(struct rt_mutex_waiter *left,		     struct rt_mutex_waiter *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->task->dl.deadline,				      right->task->dl.deadline); 	return 0;} static voidrt_mutex_enqueue(struct rt_mutex *lock, struct rt_mutex_waiter *waiter){	struct rb_node **link = &lock->waiters.rb_node;	struct rb_node *parent = NULL;	struct rt_mutex_waiter *entry;	int leftmost = 1; 	while (*link) {		parent = *link;		entry = rb_entry(parent, struct rt_mutex_waiter, tree_entry);		if (rt_mutex_waiter_less(waiter, entry)) {			link = &parent->rb_left;		} else {			link = &parent->rb_right;			leftmost = 0;		}	} 	if (leftmost)		lock->waiters_leftmost = &waiter->tree_entry; 	rb_link_node(&waiter->tree_entry, parent, link);	rb_insert_color(&waiter->tree_entry, &lock->waiters);} static voidrt_mutex_dequeue(struct rt_mutex *lock, struct rt_mutex_waiter *waiter){	if (RB_EMPTY_NODE(&waiter->tree_entry))		return; 	if (lock->waiters_leftmost == &waiter->tree_entry)		lock->waiters_leftmost = rb_next(&waiter->tree_entry); 	rb_erase(&waiter->tree_entry, &lock->waiters);	RB_CLEAR_NODE(&waiter->tree_entry);} static voidrt_mutex_enqueue_pi(struct task_struct *task, struct rt_mutex_waiter *waiter){	struct rb_node **link = &task->pi_waiters.rb_node;	struct rb_node *parent = NULL;	struct rt_mutex_waiter *entry;	int leftmost = 1; 	while (*link) {		parent = *link;		entry = rb_entry(parent, struct rt_mutex_waiter, pi_tree_entry);		if (rt_mutex_waiter_less(waiter, entry)) {			link = &parent->rb_left;		} else {			link = &parent->rb_right;			leftmost = 0;		}	} 	if (leftmost)		task->pi_waiters_leftmost = &waiter->pi_tree_entry; 	rb_link_node(&waiter->pi_tree_entry, parent, link);	rb_insert_color(&waiter->pi_tree_entry, &task->pi_waiters);} static voidrt_mutex_dequeue_pi(struct task_struct *task, struct rt_mutex_waiter *waiter){	if (RB_EMPTY_NODE(&waiter->pi_tree_entry))		return; 	if (task->pi_waiters_leftmost == &waiter->pi_tree_entry)		task->pi_waiters_leftmost = rb_next(&waiter->pi_tree_entry); 	rb_erase(&waiter->pi_tree_entry, &task->pi_waiters);	RB_CLEAR_NODE(&waiter->pi_tree_entry);} /* * Calculate task priority from the waiter tree priority * * Return task->normal_prio when the waiter tree is empty or when * the waiter is not allowed to do priority boosting */int rt_mutex_getprio(struct task_struct *task){	if (likely(!task_has_pi_waiters(task)))		return task->normal_prio; 	return min(task_top_pi_waiter(task)->prio,		   task->normal_prio);} struct task_struct *rt_mutex_get_top_task(struct task_struct *task){	if (likely(!task_has_pi_waiters(task)))		return NULL; 	return task_top_pi_waiter(task)->task;} /* * Called by sched_setscheduler() to get the priority which will be * effective after the change. */int rt_mutex_get_effective_prio(struct task_struct *task, int newprio){	if (!task_has_pi_waiters(task))		return newprio; 	if (task_top_pi_waiter(task)->task->prio <= newprio)		return task_top_pi_waiter(task)->task->prio;	return newprio;} /* * Adjust the priority of a task, after its pi_waiters got modified. * * This can be both boosting and unboosting. task->pi_lock must be held. */static void __rt_mutex_adjust_prio(struct task_struct *task){	int prio = rt_mutex_getprio(task); 	if (task->prio != prio || dl_prio(prio))		rt_mutex_setprio(task, prio);} /* * Adjust task priority (undo boosting). Called from the exit path of * rt_mutex_slowunlock() and rt_mutex_slowlock(). * * (Note: We do this outside of the protection of lock->wait_lock to * allow the lock to be taken while or before we readjust the priority * of task. We do not use the spin_xx_mutex() variants here as we are * outside of the debug path.) */void rt_mutex_adjust_prio(struct task_struct *task){	unsigned long flags; 	raw_spin_lock_irqsave(&task->pi_lock, flags);	__rt_mutex_adjust_prio(task);	raw_spin_unlock_irqrestore(&task->pi_lock, flags);} /* * Deadlock detection is conditional: * * If CONFIG_DEBUG_RT_MUTEXES=n, deadlock detection is only conducted * if the detect argument is == RT_MUTEX_FULL_CHAINWALK. * * If CONFIG_DEBUG_RT_MUTEXES=y, deadlock detection is always * conducted independent of the detect argument. * * If the waiter argument is NULL this indicates the deboost path and * deadlock detection is disabled independent of the detect argument * and the config settings. */static bool rt_mutex_cond_detect_deadlock(struct rt_mutex_waiter *waiter,					  enum rtmutex_chainwalk chwalk){	/*	 * This is just a wrapper function for the following call,	 * because debug_rt_mutex_detect_deadlock() smells like a magic	 * debug feature and I wanted to keep the cond function in the	 * main source file along with the comments instead of having	 * two of the same in the headers.	 */	return debug_rt_mutex_detect_deadlock(waiter, chwalk);} /* * Max number of times we'll walk the boosting chain: */int max_lock_depth = 1024; static inline struct rt_mutex *task_blocked_on_lock(struct task_struct *p){	return p->pi_blocked_on ? p->pi_blocked_on->lock : NULL;} /* * Adjust the priority chain. Also used for deadlock detection. * Decreases task's usage by one - may thus free the task. * * @task:	the task owning the mutex (owner) for which a chain walk is *		probably needed * @chwalk:	do we have to carry out deadlock detection? * @orig_lock:	the mutex (can be NULL if we are walking the chain to recheck *		things for a task that has just got its priority adjusted, and *		is waiting on a mutex) * @next_lock:	the mutex on which the owner of @orig_lock was blocked before *		we dropped its pi_lock. Is never dereferenced, only used for *		comparison to detect lock chain changes. * @orig_waiter: rt_mutex_waiter struct for the task that has just donated *		its priority to the mutex owner (can be NULL in the case *		depicted above or if the top waiter is gone away and we are *		actually deboosting the owner) * @top_task:	the current top waiter * * Returns 0 or -EDEADLK. * * Chain walk basics and protection scope * * [R] refcount on task * [P] task->pi_lock held * [L] rtmutex->wait_lock held * * Step	Description				Protected by *	function arguments: *	@task					[R] *	@orig_lock if != NULL			@top_task is blocked on it *	@next_lock				Unprotected. Cannot be *						dereferenced. Only used for *						comparison. *	@orig_waiter if != NULL			@top_task is blocked on it *	@top_task				current, or in case of proxy *						locking protected by calling *						code *	again: *	  loop_sanity_check(); *	retry: * [1]	  lock(task->pi_lock);			[R] acquire [P] * [2]	  waiter = task->pi_blocked_on;		[P] * [3]	  check_exit_conditions_1();		[P] * [4]	  lock = waiter->lock;			[P] * [5]	  if (!try_lock(lock->wait_lock)) {	[P] try to acquire [L] *	    unlock(task->pi_lock);		release [P] *	    goto retry; *	  } * [6]	  check_exit_conditions_2();		[P] + [L] * [7]	  requeue_lock_waiter(lock, waiter);	[P] + [L] * [8]	  unlock(task->pi_lock);		release [P] *	  put_task_struct(task);		release [R] * [9]	  check_exit_conditions_3();		[L] * [10]	  task = owner(lock);			[L] *	  get_task_struct(task);		[L] acquire [R] *	  lock(task->pi_lock);			[L] acquire [P] * [11]	  requeue_pi_waiter(tsk, waiters(lock));[P] + [L] * [12]	  check_exit_conditions_4();		[P] + [L] * [13]	  unlock(task->pi_lock);		release [P] *	  unlock(lock->wait_lock);		release [L] *	  goto again; */static int rt_mutex_adjust_prio_chain(struct task_struct *task,				      enum rtmutex_chainwalk chwalk,				      struct rt_mutex *orig_lock,				      struct rt_mutex *next_lock,				      struct rt_mutex_waiter *orig_waiter,				      struct task_struct *top_task){	struct rt_mutex_waiter *waiter, *top_waiter = orig_waiter;	struct rt_mutex_waiter *prerequeue_top_waiter;	int ret = 0, depth = 0;	struct rt_mutex *lock;

Lines 1–500 of 1763. Load more