/* * 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);} /* * 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) __releases(lock->wait_lock){ struct task_struct *owner = rt_mutex_owner(lock); clear_rt_mutex_waiters(lock); raw_spin_unlock(&lock->wait_lock); /* * 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(lock, owner, NULL);} #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);} /* * Simple slow path only version: lock->owner is protected by lock->wait_lock. */static inline bool unlock_rt_mutex_safe(struct rt_mutex *lock) __releases(lock->wait_lock){ lock->owner = NULL; raw_spin_unlock(&lock->wait_lock); 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 (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 check whether the priority change * is overruled by a possible priority boosting. */int rt_mutex_check_prio(struct task_struct *task, int newprio){ if (!task_has_pi_waiters(task)) return 0; return task_top_pi_waiter(task)->task->prio <= 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.) */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; 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 * @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) * @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. */static int rt_mutex_adjust_prio_chain(struct task_struct *task, int deadlock_detect, struct rt_mutex *orig_lock, struct rt_mutex *next_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 -EDEADLK; } 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; /* * We dropped all locks after taking a refcount on @task, so * the task might have moved on in the lock chain or even left * the chain completely and blocks now on an unrelated lock or * on @orig_lock. * * We stored the lock on which @task was blocked in @next_lock, * so we can detect the chain change. */ if (next_lock != waiter->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) { if (!task_has_pi_waiters(task)) goto out_unlock_pi; /* * If deadlock detection is off, we stop here if we * are not the top pi waiter of the task. */ if (!detect_deadlock && 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 the lock is the same as the original * lock which caused us to walk the lock chain or if the * current lock is owned by the task which initiated the chain * walk, we detected a deadlock. */ 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 = -EDEADLK; 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); } /* * Check whether the task which owns the current lock is pi * blocked itself. If yes we store a pointer to the lock forLines 1–500 of 1373. Load more
/* * 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 void rt_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); } /* * 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) __releases(lock->wait_lock) { struct task_struct *owner = rt_mutex_owner(lock); clear_rt_mutex_waiters(lock); raw_spin_unlock(&lock->wait_lock); /* * 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(lock, owner, NULL); } #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); } /* * Simple slow path only version: lock->owner is protected by lock->wait_lock. */ static inline bool unlock_rt_mutex_safe(struct rt_mutex *lock) __releases(lock->wait_lock) { lock->owner = NULL; raw_spin_unlock(&lock->wait_lock); return true; } #endif static inline int rt_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 void rt_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 void rt_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 void rt_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 void rt_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 check whether the priority change * is overruled by a possible priority boosting. */ int rt_mutex_check_prio(struct task_struct *task, int newprio) { if (!task_has_pi_waiters(task)) return 0; return task_top_pi_waiter(task)->task->prio <= 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.) */ 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; 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 * @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) * @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. */ static int rt_mutex_adjust_prio_chain(struct task_struct *task, int deadlock_detect, struct rt_mutex *orig_lock, struct rt_mutex *next_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 -EDEADLK; } 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; /* * We dropped all locks after taking a refcount on @task, so * the task might have moved on in the lock chain or even left * the chain completely and blocks now on an unrelated lock or * on @orig_lock. * * We stored the lock on which @task was blocked in @next_lock, * so we can detect the chain change. */ if (next_lock != waiter->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) { if (!task_has_pi_waiters(task)) goto out_unlock_pi; /* * If deadlock detection is off, we stop here if we * are not the top pi waiter of the task. */ if (!detect_deadlock && 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 the lock is the same as the original * lock which caused us to walk the lock chain or if the * current lock is owned by the task which initiated the chain * walk, we detected a deadlock. */ 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 = -EDEADLK; 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); } /* * Check whether the task which owns the current lock is pi * blocked itself. If yes we store a pointer to the lock for