/* * 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){ 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);} /* * 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; bool detect_deadlock; unsigned long flags; bool requeue = true; detect_deadlock = rt_mutex_cond_detect_deadlock(orig_waiter, chwalk); /* * 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: /* * We limit the lock chain length for each invocation. */ 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; } /* * We are fully preemptible here and only hold the refcount on * @task. So everything can have changed under us since the * caller or our own code below (goto retry/again) dropped all * locks. */ retry: /* * [1] Task cannot go away as we did a get_task() before ! */ raw_spin_lock_irqsave(&task->pi_lock, flags); /* * [2] Get the waiter on which @task is blocked on. */ waiter = task->pi_blocked_on; /* * [3] check_exit_conditions_1() protected by task->pi_lock. */ /* * 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;Lines 1–500 of 1646. 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/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 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); } /* * 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; bool detect_deadlock; unsigned long flags; bool requeue = true; detect_deadlock = rt_mutex_cond_detect_deadlock(orig_waiter, chwalk); /* * 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: /* * We limit the lock chain length for each invocation. */ 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; } /* * We are fully preemptible here and only hold the refcount on * @task. So everything can have changed under us since the * caller or our own code below (goto retry/again) dropped all * locks. */ retry: /* * [1] Task cannot go away as we did a get_task() before ! */ raw_spin_lock_irqsave(&task->pi_lock, flags); /* * [2] Get the waiter on which @task is blocked on. */ waiter = task->pi_blocked_on; /* * [3] check_exit_conditions_1() protected by task->pi_lock. */ /* * 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;