/* * 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/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){	if (!rt_mutex_has_waiters(lock))		clear_rt_mutex_waiters(lock);} /* * We can speed up the acquire/release, if the architecture * supports cmpxchg and if there's no debugging state to be set up */#if defined(__HAVE_ARCH_CMPXCHG) && !defined(CONFIG_DEBUG_RT_MUTEXES)# define rt_mutex_cmpxchg(l,c,n)	(cmpxchg(&l->owner, c, n) == c)static inline void mark_rt_mutex_waiters(struct rt_mutex *lock){	unsigned long owner, *p = (unsigned long *) &lock->owner; 	do {		owner = *p;	} while (cmpxchg(p, owner, owner | RT_MUTEX_HAS_WAITERS) != owner);}#else# define rt_mutex_cmpxchg(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);}#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 (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;} /* * 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.) */static 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);} /* * Max number of times we'll walk the boosting chain: */int max_lock_depth = 1024; /* * 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 * @deadlock_detect: 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) * @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. */static int rt_mutex_adjust_prio_chain(struct task_struct *task,				      int deadlock_detect,				      struct rt_mutex *orig_lock,				      struct rt_mutex_waiter *orig_waiter,				      struct task_struct *top_task){	struct rt_mutex *lock;	struct rt_mutex_waiter *waiter, *top_waiter = orig_waiter;	int detect_deadlock, ret = 0, depth = 0;	unsigned long flags; 	detect_deadlock = debug_rt_mutex_detect_deadlock(orig_waiter,							 deadlock_detect); 	/*	 * The (de)boosting is a step by step approach with a lot of	 * pitfalls. We want this to be preemptible and we want hold a	 * maximum of two locks per step. So we have to check	 * carefully whether things change under us.	 */ again:	if (++depth > max_lock_depth) {		static int prev_max; 		/*		 * Print this only once. If the admin changes the limit,		 * print a new message when reaching the limit again.		 */		if (prev_max != max_lock_depth) {			prev_max = max_lock_depth;			printk(KERN_WARNING "Maximum lock depth %d reached "			       "task: %s (%d)\n", max_lock_depth,			       top_task->comm, task_pid_nr(top_task));		}		put_task_struct(task); 		return deadlock_detect ? -EDEADLK : 0;	} retry:	/*	 * Task can not go away as we did a get_task() before !	 */	raw_spin_lock_irqsave(&task->pi_lock, flags); 	waiter = task->pi_blocked_on;	/*	 * Check whether the end of the boosting chain has been	 * reached or the state of the chain has changed while we	 * dropped the locks.	 */	if (!waiter)		goto out_unlock_pi; 	/*	 * Check the orig_waiter state. After we dropped the locks,	 * the previous owner of the lock might have released the lock.	 */	if (orig_waiter && !rt_mutex_owner(orig_lock))		goto out_unlock_pi; 	/*	 * Drop out, when the task has no waiters. Note,	 * top_waiter can be NULL, when we are in the deboosting	 * mode!	 */	if (top_waiter && (!task_has_pi_waiters(task) ||			   top_waiter != task_top_pi_waiter(task)))		goto out_unlock_pi; 	/*	 * When deadlock detection is off then we check, if further	 * priority adjustment is necessary.	 */	if (!detect_deadlock && waiter->prio == task->prio)		goto out_unlock_pi; 	lock = waiter->lock;	if (!raw_spin_trylock(&lock->wait_lock)) {		raw_spin_unlock_irqrestore(&task->pi_lock, flags);		cpu_relax();		goto retry;	} 	/* Deadlock detection */	if (lock == orig_lock || rt_mutex_owner(lock) == top_task) {		debug_rt_mutex_deadlock(deadlock_detect, orig_waiter, lock);		raw_spin_unlock(&lock->wait_lock);		ret = deadlock_detect ? -EDEADLK : 0;		goto out_unlock_pi;	} 	top_waiter = rt_mutex_top_waiter(lock); 	/* Requeue the waiter */	rt_mutex_dequeue(lock, waiter);	waiter->prio = task->prio;	rt_mutex_enqueue(lock, waiter); 	/* Release the task */	raw_spin_unlock_irqrestore(&task->pi_lock, flags);	if (!rt_mutex_owner(lock)) {		/*		 * If the requeue above changed the top waiter, then we need		 * to wake the new top waiter up to try to get the lock.		 */ 		if (top_waiter != rt_mutex_top_waiter(lock))			wake_up_process(rt_mutex_top_waiter(lock)->task);		raw_spin_unlock(&lock->wait_lock);		goto out_put_task;	}	put_task_struct(task); 	/* Grab the next task */	task = rt_mutex_owner(lock);	get_task_struct(task);	raw_spin_lock_irqsave(&task->pi_lock, flags); 	if (waiter == rt_mutex_top_waiter(lock)) {		/* Boost the owner */		rt_mutex_dequeue_pi(task, top_waiter);		rt_mutex_enqueue_pi(task, waiter);		__rt_mutex_adjust_prio(task); 	} else if (top_waiter == waiter) {		/* Deboost the owner */		rt_mutex_dequeue_pi(task, waiter);		waiter = rt_mutex_top_waiter(lock);		rt_mutex_enqueue_pi(task, waiter);		__rt_mutex_adjust_prio(task);	} 	raw_spin_unlock_irqrestore(&task->pi_lock, flags); 	top_waiter = rt_mutex_top_waiter(lock);	raw_spin_unlock(&lock->wait_lock); 	if (!detect_deadlock && waiter != top_waiter)		goto out_put_task; 	goto again;  out_unlock_pi:	raw_spin_unlock_irqrestore(&task->pi_lock, flags); out_put_task:	put_task_struct(task); 	return ret;} /* * Try to take an rt-mutex * * Must be called with lock->wait_lock held. * * @lock:   the lock to be acquired. * @task:   the task which wants to acquire the lock * @waiter: the waiter that is queued to the lock's wait list. (could be NULL) */static int try_to_take_rt_mutex(struct rt_mutex *lock, struct task_struct *task,		struct rt_mutex_waiter *waiter){	/*	 * We have to be careful here if the atomic speedups are	 * enabled, such that, when	 *  - no other waiter is on the lock	 *  - the lock has been released since we did the cmpxchg	 * the lock can be released or taken while we are doing the	 * checks and marking the lock with RT_MUTEX_HAS_WAITERS.	 *	 * The atomic acquire/release aware variant of	 * mark_rt_mutex_waiters uses a cmpxchg loop. After setting	 * the WAITERS bit, the atomic release / acquire can not	 * happen anymore and lock->wait_lock protects us from the	 * non-atomic case.	 *	 * Note, that this might set lock->owner =	 * RT_MUTEX_HAS_WAITERS in the case the lock is not contended	 * any more. This is fixed up when we take the ownership.	 * This is the transitional state explained at the top of this file.	 */	mark_rt_mutex_waiters(lock); 	if (rt_mutex_owner(lock))		return 0; 	/*	 * It will get the lock because of one of these conditions:	 * 1) there is no waiter	 * 2) higher priority than waiters	 * 3) it is top waiter	 */	if (rt_mutex_has_waiters(lock)) {		if (task->prio >= rt_mutex_top_waiter(lock)->prio) {			if (!waiter || waiter != rt_mutex_top_waiter(lock))				return 0;		}	} 	if (waiter || rt_mutex_has_waiters(lock)) {		unsigned long flags;		struct rt_mutex_waiter *top; 		raw_spin_lock_irqsave(&task->pi_lock, flags); 		/* remove the queued waiter. */		if (waiter) {			rt_mutex_dequeue(lock, waiter);			task->pi_blocked_on = NULL;		} 		/*		 * We have to enqueue the top waiter(if it exists) into		 * task->pi_waiters list.		 */		if (rt_mutex_has_waiters(lock)) {			top = rt_mutex_top_waiter(lock);			rt_mutex_enqueue_pi(task, top);		}		raw_spin_unlock_irqrestore(&task->pi_lock, flags);	} 	/* We got the lock. */	debug_rt_mutex_lock(lock); 	rt_mutex_set_owner(lock, task); 	rt_mutex_deadlock_account_lock(lock, task); 	return 1;} 

Lines 1–500 of 1164. Load more