11696a8beSPeter Zijlstra /* 21696a8beSPeter Zijlstra * RT-Mutexes: simple blocking mutual exclusion locks with PI support 31696a8beSPeter Zijlstra * 41696a8beSPeter Zijlstra * started by Ingo Molnar and Thomas Gleixner. 51696a8beSPeter Zijlstra * 61696a8beSPeter Zijlstra * Copyright (C) 2004-2006 Red Hat, Inc., Ingo Molnar <mingo@redhat.com> 71696a8beSPeter Zijlstra * Copyright (C) 2005-2006 Timesys Corp., Thomas Gleixner <tglx@timesys.com> 81696a8beSPeter Zijlstra * Copyright (C) 2005 Kihon Technologies Inc., Steven Rostedt 91696a8beSPeter Zijlstra * Copyright (C) 2006 Esben Nielsen 101696a8beSPeter Zijlstra * 11214e0aedSDavidlohr Bueso * See Documentation/locking/rt-mutex-design.txt for details. 121696a8beSPeter Zijlstra */ 131696a8beSPeter Zijlstra #include <linux/spinlock.h> 141696a8beSPeter Zijlstra #include <linux/export.h> 15*174cd4b1SIngo Molnar #include <linux/sched/signal.h> 161696a8beSPeter Zijlstra #include <linux/sched/rt.h> 17fb00aca4SPeter Zijlstra #include <linux/sched/deadline.h> 1884f001e1SIngo Molnar #include <linux/sched/wake_q.h> 191696a8beSPeter Zijlstra #include <linux/timer.h> 201696a8beSPeter Zijlstra 211696a8beSPeter Zijlstra #include "rtmutex_common.h" 221696a8beSPeter Zijlstra 231696a8beSPeter Zijlstra /* 241696a8beSPeter Zijlstra * lock->owner state tracking: 251696a8beSPeter Zijlstra * 261696a8beSPeter Zijlstra * lock->owner holds the task_struct pointer of the owner. Bit 0 271696a8beSPeter Zijlstra * is used to keep track of the "lock has waiters" state. 281696a8beSPeter Zijlstra * 291696a8beSPeter Zijlstra * owner bit0 301696a8beSPeter Zijlstra * NULL 0 lock is free (fast acquire possible) 311696a8beSPeter Zijlstra * NULL 1 lock is free and has waiters and the top waiter 321696a8beSPeter Zijlstra * is going to take the lock* 331696a8beSPeter Zijlstra * taskpointer 0 lock is held (fast release possible) 341696a8beSPeter Zijlstra * taskpointer 1 lock is held and has waiters** 351696a8beSPeter Zijlstra * 361696a8beSPeter Zijlstra * The fast atomic compare exchange based acquire and release is only 371696a8beSPeter Zijlstra * possible when bit 0 of lock->owner is 0. 381696a8beSPeter Zijlstra * 391696a8beSPeter Zijlstra * (*) It also can be a transitional state when grabbing the lock 401696a8beSPeter Zijlstra * with ->wait_lock is held. To prevent any fast path cmpxchg to the lock, 411696a8beSPeter Zijlstra * we need to set the bit0 before looking at the lock, and the owner may be 421696a8beSPeter Zijlstra * NULL in this small time, hence this can be a transitional state. 431696a8beSPeter Zijlstra * 441696a8beSPeter Zijlstra * (**) There is a small time when bit 0 is set but there are no 451696a8beSPeter Zijlstra * waiters. This can happen when grabbing the lock in the slow path. 461696a8beSPeter Zijlstra * To prevent a cmpxchg of the owner releasing the lock, we need to 471696a8beSPeter Zijlstra * set this bit before looking at the lock. 481696a8beSPeter Zijlstra */ 491696a8beSPeter Zijlstra 501696a8beSPeter Zijlstra static void 511696a8beSPeter Zijlstra rt_mutex_set_owner(struct rt_mutex *lock, struct task_struct *owner) 521696a8beSPeter Zijlstra { 531696a8beSPeter Zijlstra unsigned long val = (unsigned long)owner; 541696a8beSPeter Zijlstra 551696a8beSPeter Zijlstra if (rt_mutex_has_waiters(lock)) 561696a8beSPeter Zijlstra val |= RT_MUTEX_HAS_WAITERS; 571696a8beSPeter Zijlstra 581696a8beSPeter Zijlstra lock->owner = (struct task_struct *)val; 591696a8beSPeter Zijlstra } 601696a8beSPeter Zijlstra 611696a8beSPeter Zijlstra static inline void clear_rt_mutex_waiters(struct rt_mutex *lock) 621696a8beSPeter Zijlstra { 631696a8beSPeter Zijlstra lock->owner = (struct task_struct *) 641696a8beSPeter Zijlstra ((unsigned long)lock->owner & ~RT_MUTEX_HAS_WAITERS); 651696a8beSPeter Zijlstra } 661696a8beSPeter Zijlstra 671696a8beSPeter Zijlstra static void fixup_rt_mutex_waiters(struct rt_mutex *lock) 681696a8beSPeter Zijlstra { 69dbb26055SThomas Gleixner unsigned long owner, *p = (unsigned long *) &lock->owner; 70dbb26055SThomas Gleixner 71dbb26055SThomas Gleixner if (rt_mutex_has_waiters(lock)) 72dbb26055SThomas Gleixner return; 73dbb26055SThomas Gleixner 74dbb26055SThomas Gleixner /* 75dbb26055SThomas Gleixner * The rbtree has no waiters enqueued, now make sure that the 76dbb26055SThomas Gleixner * lock->owner still has the waiters bit set, otherwise the 77dbb26055SThomas Gleixner * following can happen: 78dbb26055SThomas Gleixner * 79dbb26055SThomas Gleixner * CPU 0 CPU 1 CPU2 80dbb26055SThomas Gleixner * l->owner=T1 81dbb26055SThomas Gleixner * rt_mutex_lock(l) 82dbb26055SThomas Gleixner * lock(l->lock) 83dbb26055SThomas Gleixner * l->owner = T1 | HAS_WAITERS; 84dbb26055SThomas Gleixner * enqueue(T2) 85dbb26055SThomas Gleixner * boost() 86dbb26055SThomas Gleixner * unlock(l->lock) 87dbb26055SThomas Gleixner * block() 88dbb26055SThomas Gleixner * 89dbb26055SThomas Gleixner * rt_mutex_lock(l) 90dbb26055SThomas Gleixner * lock(l->lock) 91dbb26055SThomas Gleixner * l->owner = T1 | HAS_WAITERS; 92dbb26055SThomas Gleixner * enqueue(T3) 93dbb26055SThomas Gleixner * boost() 94dbb26055SThomas Gleixner * unlock(l->lock) 95dbb26055SThomas Gleixner * block() 96dbb26055SThomas Gleixner * signal(->T2) signal(->T3) 97dbb26055SThomas Gleixner * lock(l->lock) 98dbb26055SThomas Gleixner * dequeue(T2) 99dbb26055SThomas Gleixner * deboost() 100dbb26055SThomas Gleixner * unlock(l->lock) 101dbb26055SThomas Gleixner * lock(l->lock) 102dbb26055SThomas Gleixner * dequeue(T3) 103dbb26055SThomas Gleixner * ==> wait list is empty 104dbb26055SThomas Gleixner * deboost() 105dbb26055SThomas Gleixner * unlock(l->lock) 106dbb26055SThomas Gleixner * lock(l->lock) 107dbb26055SThomas Gleixner * fixup_rt_mutex_waiters() 108dbb26055SThomas Gleixner * if (wait_list_empty(l) { 109dbb26055SThomas Gleixner * l->owner = owner 110dbb26055SThomas Gleixner * owner = l->owner & ~HAS_WAITERS; 111dbb26055SThomas Gleixner * ==> l->owner = T1 112dbb26055SThomas Gleixner * } 113dbb26055SThomas Gleixner * lock(l->lock) 114dbb26055SThomas Gleixner * rt_mutex_unlock(l) fixup_rt_mutex_waiters() 115dbb26055SThomas Gleixner * if (wait_list_empty(l) { 116dbb26055SThomas Gleixner * owner = l->owner & ~HAS_WAITERS; 117dbb26055SThomas Gleixner * cmpxchg(l->owner, T1, NULL) 118dbb26055SThomas Gleixner * ===> Success (l->owner = NULL) 119dbb26055SThomas Gleixner * 120dbb26055SThomas Gleixner * l->owner = owner 121dbb26055SThomas Gleixner * ==> l->owner = T1 122dbb26055SThomas Gleixner * } 123dbb26055SThomas Gleixner * 124dbb26055SThomas Gleixner * With the check for the waiter bit in place T3 on CPU2 will not 125dbb26055SThomas Gleixner * overwrite. All tasks fiddling with the waiters bit are 126dbb26055SThomas Gleixner * serialized by l->lock, so nothing else can modify the waiters 127dbb26055SThomas Gleixner * bit. If the bit is set then nothing can change l->owner either 128dbb26055SThomas Gleixner * so the simple RMW is safe. The cmpxchg() will simply fail if it 129dbb26055SThomas Gleixner * happens in the middle of the RMW because the waiters bit is 130dbb26055SThomas Gleixner * still set. 131dbb26055SThomas Gleixner */ 132dbb26055SThomas Gleixner owner = READ_ONCE(*p); 133dbb26055SThomas Gleixner if (owner & RT_MUTEX_HAS_WAITERS) 134dbb26055SThomas Gleixner WRITE_ONCE(*p, owner & ~RT_MUTEX_HAS_WAITERS); 1351696a8beSPeter Zijlstra } 1361696a8beSPeter Zijlstra 1371696a8beSPeter Zijlstra /* 138cede8841SSebastian Andrzej Siewior * We can speed up the acquire/release, if there's no debugging state to be 139cede8841SSebastian Andrzej Siewior * set up. 1401696a8beSPeter Zijlstra */ 141cede8841SSebastian Andrzej Siewior #ifndef CONFIG_DEBUG_RT_MUTEXES 142700318d1SDavidlohr Bueso # define rt_mutex_cmpxchg_relaxed(l,c,n) (cmpxchg_relaxed(&l->owner, c, n) == c) 143700318d1SDavidlohr Bueso # define rt_mutex_cmpxchg_acquire(l,c,n) (cmpxchg_acquire(&l->owner, c, n) == c) 144700318d1SDavidlohr Bueso # define rt_mutex_cmpxchg_release(l,c,n) (cmpxchg_release(&l->owner, c, n) == c) 145700318d1SDavidlohr Bueso 146700318d1SDavidlohr Bueso /* 147700318d1SDavidlohr Bueso * Callers must hold the ->wait_lock -- which is the whole purpose as we force 148700318d1SDavidlohr Bueso * all future threads that attempt to [Rmw] the lock to the slowpath. As such 149700318d1SDavidlohr Bueso * relaxed semantics suffice. 150700318d1SDavidlohr Bueso */ 1511696a8beSPeter Zijlstra static inline void mark_rt_mutex_waiters(struct rt_mutex *lock) 1521696a8beSPeter Zijlstra { 1531696a8beSPeter Zijlstra unsigned long owner, *p = (unsigned long *) &lock->owner; 1541696a8beSPeter Zijlstra 1551696a8beSPeter Zijlstra do { 1561696a8beSPeter Zijlstra owner = *p; 157700318d1SDavidlohr Bueso } while (cmpxchg_relaxed(p, owner, 158700318d1SDavidlohr Bueso owner | RT_MUTEX_HAS_WAITERS) != owner); 1591696a8beSPeter Zijlstra } 16027e35715SThomas Gleixner 16127e35715SThomas Gleixner /* 16227e35715SThomas Gleixner * Safe fastpath aware unlock: 16327e35715SThomas Gleixner * 1) Clear the waiters bit 16427e35715SThomas Gleixner * 2) Drop lock->wait_lock 16527e35715SThomas Gleixner * 3) Try to unlock the lock with cmpxchg 16627e35715SThomas Gleixner */ 167b4abf910SThomas Gleixner static inline bool unlock_rt_mutex_safe(struct rt_mutex *lock, 168b4abf910SThomas Gleixner unsigned long flags) 16927e35715SThomas Gleixner __releases(lock->wait_lock) 17027e35715SThomas Gleixner { 17127e35715SThomas Gleixner struct task_struct *owner = rt_mutex_owner(lock); 17227e35715SThomas Gleixner 17327e35715SThomas Gleixner clear_rt_mutex_waiters(lock); 174b4abf910SThomas Gleixner raw_spin_unlock_irqrestore(&lock->wait_lock, flags); 17527e35715SThomas Gleixner /* 17627e35715SThomas Gleixner * If a new waiter comes in between the unlock and the cmpxchg 17727e35715SThomas Gleixner * we have two situations: 17827e35715SThomas Gleixner * 17927e35715SThomas Gleixner * unlock(wait_lock); 18027e35715SThomas Gleixner * lock(wait_lock); 18127e35715SThomas Gleixner * cmpxchg(p, owner, 0) == owner 18227e35715SThomas Gleixner * mark_rt_mutex_waiters(lock); 18327e35715SThomas Gleixner * acquire(lock); 18427e35715SThomas Gleixner * or: 18527e35715SThomas Gleixner * 18627e35715SThomas Gleixner * unlock(wait_lock); 18727e35715SThomas Gleixner * lock(wait_lock); 18827e35715SThomas Gleixner * mark_rt_mutex_waiters(lock); 18927e35715SThomas Gleixner * 19027e35715SThomas Gleixner * cmpxchg(p, owner, 0) != owner 19127e35715SThomas Gleixner * enqueue_waiter(); 19227e35715SThomas Gleixner * unlock(wait_lock); 19327e35715SThomas Gleixner * lock(wait_lock); 19427e35715SThomas Gleixner * wake waiter(); 19527e35715SThomas Gleixner * unlock(wait_lock); 19627e35715SThomas Gleixner * lock(wait_lock); 19727e35715SThomas Gleixner * acquire(lock); 19827e35715SThomas Gleixner */ 199700318d1SDavidlohr Bueso return rt_mutex_cmpxchg_release(lock, owner, NULL); 20027e35715SThomas Gleixner } 20127e35715SThomas Gleixner 2021696a8beSPeter Zijlstra #else 203700318d1SDavidlohr Bueso # define rt_mutex_cmpxchg_relaxed(l,c,n) (0) 204700318d1SDavidlohr Bueso # define rt_mutex_cmpxchg_acquire(l,c,n) (0) 205700318d1SDavidlohr Bueso # define rt_mutex_cmpxchg_release(l,c,n) (0) 206700318d1SDavidlohr Bueso 2071696a8beSPeter Zijlstra static inline void mark_rt_mutex_waiters(struct rt_mutex *lock) 2081696a8beSPeter Zijlstra { 2091696a8beSPeter Zijlstra lock->owner = (struct task_struct *) 2101696a8beSPeter Zijlstra ((unsigned long)lock->owner | RT_MUTEX_HAS_WAITERS); 2111696a8beSPeter Zijlstra } 21227e35715SThomas Gleixner 21327e35715SThomas Gleixner /* 21427e35715SThomas Gleixner * Simple slow path only version: lock->owner is protected by lock->wait_lock. 21527e35715SThomas Gleixner */ 216b4abf910SThomas Gleixner static inline bool unlock_rt_mutex_safe(struct rt_mutex *lock, 217b4abf910SThomas Gleixner unsigned long flags) 21827e35715SThomas Gleixner __releases(lock->wait_lock) 21927e35715SThomas Gleixner { 22027e35715SThomas Gleixner lock->owner = NULL; 221b4abf910SThomas Gleixner raw_spin_unlock_irqrestore(&lock->wait_lock, flags); 22227e35715SThomas Gleixner return true; 22327e35715SThomas Gleixner } 2241696a8beSPeter Zijlstra #endif 2251696a8beSPeter Zijlstra 226fb00aca4SPeter Zijlstra static inline int 227fb00aca4SPeter Zijlstra rt_mutex_waiter_less(struct rt_mutex_waiter *left, 228fb00aca4SPeter Zijlstra struct rt_mutex_waiter *right) 229fb00aca4SPeter Zijlstra { 2302d3d891dSDario Faggioli if (left->prio < right->prio) 231fb00aca4SPeter Zijlstra return 1; 232fb00aca4SPeter Zijlstra 2331696a8beSPeter Zijlstra /* 2342d3d891dSDario Faggioli * If both waiters have dl_prio(), we check the deadlines of the 2352d3d891dSDario Faggioli * associated tasks. 2362d3d891dSDario Faggioli * If left waiter has a dl_prio(), and we didn't return 1 above, 2372d3d891dSDario Faggioli * then right waiter has a dl_prio() too. 238fb00aca4SPeter Zijlstra */ 2392d3d891dSDario Faggioli if (dl_prio(left->prio)) 240f5240575SJuri Lelli return dl_time_before(left->task->dl.deadline, 241f5240575SJuri Lelli right->task->dl.deadline); 242fb00aca4SPeter Zijlstra 243fb00aca4SPeter Zijlstra return 0; 244fb00aca4SPeter Zijlstra } 245fb00aca4SPeter Zijlstra 246fb00aca4SPeter Zijlstra static void 247fb00aca4SPeter Zijlstra rt_mutex_enqueue(struct rt_mutex *lock, struct rt_mutex_waiter *waiter) 248fb00aca4SPeter Zijlstra { 249fb00aca4SPeter Zijlstra struct rb_node **link = &lock->waiters.rb_node; 250fb00aca4SPeter Zijlstra struct rb_node *parent = NULL; 251fb00aca4SPeter Zijlstra struct rt_mutex_waiter *entry; 252fb00aca4SPeter Zijlstra int leftmost = 1; 253fb00aca4SPeter Zijlstra 254fb00aca4SPeter Zijlstra while (*link) { 255fb00aca4SPeter Zijlstra parent = *link; 256fb00aca4SPeter Zijlstra entry = rb_entry(parent, struct rt_mutex_waiter, tree_entry); 257fb00aca4SPeter Zijlstra if (rt_mutex_waiter_less(waiter, entry)) { 258fb00aca4SPeter Zijlstra link = &parent->rb_left; 259fb00aca4SPeter Zijlstra } else { 260fb00aca4SPeter Zijlstra link = &parent->rb_right; 261fb00aca4SPeter Zijlstra leftmost = 0; 262fb00aca4SPeter Zijlstra } 263fb00aca4SPeter Zijlstra } 264fb00aca4SPeter Zijlstra 265fb00aca4SPeter Zijlstra if (leftmost) 266fb00aca4SPeter Zijlstra lock->waiters_leftmost = &waiter->tree_entry; 267fb00aca4SPeter Zijlstra 268fb00aca4SPeter Zijlstra rb_link_node(&waiter->tree_entry, parent, link); 269fb00aca4SPeter Zijlstra rb_insert_color(&waiter->tree_entry, &lock->waiters); 270fb00aca4SPeter Zijlstra } 271fb00aca4SPeter Zijlstra 272fb00aca4SPeter Zijlstra static void 273fb00aca4SPeter Zijlstra rt_mutex_dequeue(struct rt_mutex *lock, struct rt_mutex_waiter *waiter) 274fb00aca4SPeter Zijlstra { 275fb00aca4SPeter Zijlstra if (RB_EMPTY_NODE(&waiter->tree_entry)) 276fb00aca4SPeter Zijlstra return; 277fb00aca4SPeter Zijlstra 278fb00aca4SPeter Zijlstra if (lock->waiters_leftmost == &waiter->tree_entry) 279fb00aca4SPeter Zijlstra lock->waiters_leftmost = rb_next(&waiter->tree_entry); 280fb00aca4SPeter Zijlstra 281fb00aca4SPeter Zijlstra rb_erase(&waiter->tree_entry, &lock->waiters); 282fb00aca4SPeter Zijlstra RB_CLEAR_NODE(&waiter->tree_entry); 283fb00aca4SPeter Zijlstra } 284fb00aca4SPeter Zijlstra 285fb00aca4SPeter Zijlstra static void 286fb00aca4SPeter Zijlstra rt_mutex_enqueue_pi(struct task_struct *task, struct rt_mutex_waiter *waiter) 287fb00aca4SPeter Zijlstra { 288fb00aca4SPeter Zijlstra struct rb_node **link = &task->pi_waiters.rb_node; 289fb00aca4SPeter Zijlstra struct rb_node *parent = NULL; 290fb00aca4SPeter Zijlstra struct rt_mutex_waiter *entry; 291fb00aca4SPeter Zijlstra int leftmost = 1; 292fb00aca4SPeter Zijlstra 293fb00aca4SPeter Zijlstra while (*link) { 294fb00aca4SPeter Zijlstra parent = *link; 295fb00aca4SPeter Zijlstra entry = rb_entry(parent, struct rt_mutex_waiter, pi_tree_entry); 296fb00aca4SPeter Zijlstra if (rt_mutex_waiter_less(waiter, entry)) { 297fb00aca4SPeter Zijlstra link = &parent->rb_left; 298fb00aca4SPeter Zijlstra } else { 299fb00aca4SPeter Zijlstra link = &parent->rb_right; 300fb00aca4SPeter Zijlstra leftmost = 0; 301fb00aca4SPeter Zijlstra } 302fb00aca4SPeter Zijlstra } 303fb00aca4SPeter Zijlstra 304fb00aca4SPeter Zijlstra if (leftmost) 305fb00aca4SPeter Zijlstra task->pi_waiters_leftmost = &waiter->pi_tree_entry; 306fb00aca4SPeter Zijlstra 307fb00aca4SPeter Zijlstra rb_link_node(&waiter->pi_tree_entry, parent, link); 308fb00aca4SPeter Zijlstra rb_insert_color(&waiter->pi_tree_entry, &task->pi_waiters); 309fb00aca4SPeter Zijlstra } 310fb00aca4SPeter Zijlstra 311fb00aca4SPeter Zijlstra static void 312fb00aca4SPeter Zijlstra rt_mutex_dequeue_pi(struct task_struct *task, struct rt_mutex_waiter *waiter) 313fb00aca4SPeter Zijlstra { 314fb00aca4SPeter Zijlstra if (RB_EMPTY_NODE(&waiter->pi_tree_entry)) 315fb00aca4SPeter Zijlstra return; 316fb00aca4SPeter Zijlstra 317fb00aca4SPeter Zijlstra if (task->pi_waiters_leftmost == &waiter->pi_tree_entry) 318fb00aca4SPeter Zijlstra task->pi_waiters_leftmost = rb_next(&waiter->pi_tree_entry); 319fb00aca4SPeter Zijlstra 320fb00aca4SPeter Zijlstra rb_erase(&waiter->pi_tree_entry, &task->pi_waiters); 321fb00aca4SPeter Zijlstra RB_CLEAR_NODE(&waiter->pi_tree_entry); 322fb00aca4SPeter Zijlstra } 323fb00aca4SPeter Zijlstra 324fb00aca4SPeter Zijlstra /* 325fb00aca4SPeter Zijlstra * Calculate task priority from the waiter tree priority 3261696a8beSPeter Zijlstra * 327fb00aca4SPeter Zijlstra * Return task->normal_prio when the waiter tree is empty or when 3281696a8beSPeter Zijlstra * the waiter is not allowed to do priority boosting 3291696a8beSPeter Zijlstra */ 3301696a8beSPeter Zijlstra int rt_mutex_getprio(struct task_struct *task) 3311696a8beSPeter Zijlstra { 3321696a8beSPeter Zijlstra if (likely(!task_has_pi_waiters(task))) 3331696a8beSPeter Zijlstra return task->normal_prio; 3341696a8beSPeter Zijlstra 3352d3d891dSDario Faggioli return min(task_top_pi_waiter(task)->prio, 3361696a8beSPeter Zijlstra task->normal_prio); 3371696a8beSPeter Zijlstra } 3381696a8beSPeter Zijlstra 3392d3d891dSDario Faggioli struct task_struct *rt_mutex_get_top_task(struct task_struct *task) 3402d3d891dSDario Faggioli { 3412d3d891dSDario Faggioli if (likely(!task_has_pi_waiters(task))) 3422d3d891dSDario Faggioli return NULL; 3432d3d891dSDario Faggioli 3442d3d891dSDario Faggioli return task_top_pi_waiter(task)->task; 3452d3d891dSDario Faggioli } 3462d3d891dSDario Faggioli 3471696a8beSPeter Zijlstra /* 3480782e63bSThomas Gleixner * Called by sched_setscheduler() to get the priority which will be 3490782e63bSThomas Gleixner * effective after the change. 350c365c292SThomas Gleixner */ 3510782e63bSThomas Gleixner int rt_mutex_get_effective_prio(struct task_struct *task, int newprio) 352c365c292SThomas Gleixner { 353c365c292SThomas Gleixner if (!task_has_pi_waiters(task)) 3540782e63bSThomas Gleixner return newprio; 355c365c292SThomas Gleixner 3560782e63bSThomas Gleixner if (task_top_pi_waiter(task)->task->prio <= newprio) 3570782e63bSThomas Gleixner return task_top_pi_waiter(task)->task->prio; 3580782e63bSThomas Gleixner return newprio; 359c365c292SThomas Gleixner } 360c365c292SThomas Gleixner 361c365c292SThomas Gleixner /* 3621696a8beSPeter Zijlstra * Adjust the priority of a task, after its pi_waiters got modified. 3631696a8beSPeter Zijlstra * 3641696a8beSPeter Zijlstra * This can be both boosting and unboosting. task->pi_lock must be held. 3651696a8beSPeter Zijlstra */ 3661696a8beSPeter Zijlstra static void __rt_mutex_adjust_prio(struct task_struct *task) 3671696a8beSPeter Zijlstra { 3681696a8beSPeter Zijlstra int prio = rt_mutex_getprio(task); 3691696a8beSPeter Zijlstra 3702d3d891dSDario Faggioli if (task->prio != prio || dl_prio(prio)) 3711696a8beSPeter Zijlstra rt_mutex_setprio(task, prio); 3721696a8beSPeter Zijlstra } 3731696a8beSPeter Zijlstra 3741696a8beSPeter Zijlstra /* 3751696a8beSPeter Zijlstra * Adjust task priority (undo boosting). Called from the exit path of 3761696a8beSPeter Zijlstra * rt_mutex_slowunlock() and rt_mutex_slowlock(). 3771696a8beSPeter Zijlstra * 3781696a8beSPeter Zijlstra * (Note: We do this outside of the protection of lock->wait_lock to 3791696a8beSPeter Zijlstra * allow the lock to be taken while or before we readjust the priority 3801696a8beSPeter Zijlstra * of task. We do not use the spin_xx_mutex() variants here as we are 3811696a8beSPeter Zijlstra * outside of the debug path.) 3821696a8beSPeter Zijlstra */ 383802ab58dSSebastian Andrzej Siewior void rt_mutex_adjust_prio(struct task_struct *task) 3841696a8beSPeter Zijlstra { 3851696a8beSPeter Zijlstra unsigned long flags; 3861696a8beSPeter Zijlstra 3871696a8beSPeter Zijlstra raw_spin_lock_irqsave(&task->pi_lock, flags); 3881696a8beSPeter Zijlstra __rt_mutex_adjust_prio(task); 3891696a8beSPeter Zijlstra raw_spin_unlock_irqrestore(&task->pi_lock, flags); 3901696a8beSPeter Zijlstra } 3911696a8beSPeter Zijlstra 3921696a8beSPeter Zijlstra /* 3938930ed80SThomas Gleixner * Deadlock detection is conditional: 3948930ed80SThomas Gleixner * 3958930ed80SThomas Gleixner * If CONFIG_DEBUG_RT_MUTEXES=n, deadlock detection is only conducted 3968930ed80SThomas Gleixner * if the detect argument is == RT_MUTEX_FULL_CHAINWALK. 3978930ed80SThomas Gleixner * 3988930ed80SThomas Gleixner * If CONFIG_DEBUG_RT_MUTEXES=y, deadlock detection is always 3998930ed80SThomas Gleixner * conducted independent of the detect argument. 4008930ed80SThomas Gleixner * 4018930ed80SThomas Gleixner * If the waiter argument is NULL this indicates the deboost path and 4028930ed80SThomas Gleixner * deadlock detection is disabled independent of the detect argument 4038930ed80SThomas Gleixner * and the config settings. 4048930ed80SThomas Gleixner */ 4058930ed80SThomas Gleixner static bool rt_mutex_cond_detect_deadlock(struct rt_mutex_waiter *waiter, 4068930ed80SThomas Gleixner enum rtmutex_chainwalk chwalk) 4078930ed80SThomas Gleixner { 4088930ed80SThomas Gleixner /* 4098930ed80SThomas Gleixner * This is just a wrapper function for the following call, 4108930ed80SThomas Gleixner * because debug_rt_mutex_detect_deadlock() smells like a magic 4118930ed80SThomas Gleixner * debug feature and I wanted to keep the cond function in the 4128930ed80SThomas Gleixner * main source file along with the comments instead of having 4138930ed80SThomas Gleixner * two of the same in the headers. 4148930ed80SThomas Gleixner */ 4158930ed80SThomas Gleixner return debug_rt_mutex_detect_deadlock(waiter, chwalk); 4168930ed80SThomas Gleixner } 4178930ed80SThomas Gleixner 4188930ed80SThomas Gleixner /* 4191696a8beSPeter Zijlstra * Max number of times we'll walk the boosting chain: 4201696a8beSPeter Zijlstra */ 4211696a8beSPeter Zijlstra int max_lock_depth = 1024; 4221696a8beSPeter Zijlstra 42382084984SThomas Gleixner static inline struct rt_mutex *task_blocked_on_lock(struct task_struct *p) 42482084984SThomas Gleixner { 42582084984SThomas Gleixner return p->pi_blocked_on ? p->pi_blocked_on->lock : NULL; 42682084984SThomas Gleixner } 42782084984SThomas Gleixner 4281696a8beSPeter Zijlstra /* 4291696a8beSPeter Zijlstra * Adjust the priority chain. Also used for deadlock detection. 4301696a8beSPeter Zijlstra * Decreases task's usage by one - may thus free the task. 4311696a8beSPeter Zijlstra * 43282084984SThomas Gleixner * @task: the task owning the mutex (owner) for which a chain walk is 43382084984SThomas Gleixner * probably needed 434e6beaa36STom(JeHyeon) Yeon * @chwalk: do we have to carry out deadlock detection? 4351696a8beSPeter Zijlstra * @orig_lock: the mutex (can be NULL if we are walking the chain to recheck 4361696a8beSPeter Zijlstra * things for a task that has just got its priority adjusted, and 4371696a8beSPeter Zijlstra * is waiting on a mutex) 43882084984SThomas Gleixner * @next_lock: the mutex on which the owner of @orig_lock was blocked before 43982084984SThomas Gleixner * we dropped its pi_lock. Is never dereferenced, only used for 44082084984SThomas Gleixner * comparison to detect lock chain changes. 4411696a8beSPeter Zijlstra * @orig_waiter: rt_mutex_waiter struct for the task that has just donated 4421696a8beSPeter Zijlstra * its priority to the mutex owner (can be NULL in the case 4431696a8beSPeter Zijlstra * depicted above or if the top waiter is gone away and we are 4441696a8beSPeter Zijlstra * actually deboosting the owner) 4451696a8beSPeter Zijlstra * @top_task: the current top waiter 4461696a8beSPeter Zijlstra * 4471696a8beSPeter Zijlstra * Returns 0 or -EDEADLK. 4483eb65aeaSThomas Gleixner * 4493eb65aeaSThomas Gleixner * Chain walk basics and protection scope 4503eb65aeaSThomas Gleixner * 4513eb65aeaSThomas Gleixner * [R] refcount on task 4523eb65aeaSThomas Gleixner * [P] task->pi_lock held 4533eb65aeaSThomas Gleixner * [L] rtmutex->wait_lock held 4543eb65aeaSThomas Gleixner * 4553eb65aeaSThomas Gleixner * Step Description Protected by 4563eb65aeaSThomas Gleixner * function arguments: 4573eb65aeaSThomas Gleixner * @task [R] 4583eb65aeaSThomas Gleixner * @orig_lock if != NULL @top_task is blocked on it 4593eb65aeaSThomas Gleixner * @next_lock Unprotected. Cannot be 4603eb65aeaSThomas Gleixner * dereferenced. Only used for 4613eb65aeaSThomas Gleixner * comparison. 4623eb65aeaSThomas Gleixner * @orig_waiter if != NULL @top_task is blocked on it 4633eb65aeaSThomas Gleixner * @top_task current, or in case of proxy 4643eb65aeaSThomas Gleixner * locking protected by calling 4653eb65aeaSThomas Gleixner * code 4663eb65aeaSThomas Gleixner * again: 4673eb65aeaSThomas Gleixner * loop_sanity_check(); 4683eb65aeaSThomas Gleixner * retry: 4693eb65aeaSThomas Gleixner * [1] lock(task->pi_lock); [R] acquire [P] 4703eb65aeaSThomas Gleixner * [2] waiter = task->pi_blocked_on; [P] 4713eb65aeaSThomas Gleixner * [3] check_exit_conditions_1(); [P] 4723eb65aeaSThomas Gleixner * [4] lock = waiter->lock; [P] 4733eb65aeaSThomas Gleixner * [5] if (!try_lock(lock->wait_lock)) { [P] try to acquire [L] 4743eb65aeaSThomas Gleixner * unlock(task->pi_lock); release [P] 4753eb65aeaSThomas Gleixner * goto retry; 4763eb65aeaSThomas Gleixner * } 4773eb65aeaSThomas Gleixner * [6] check_exit_conditions_2(); [P] + [L] 4783eb65aeaSThomas Gleixner * [7] requeue_lock_waiter(lock, waiter); [P] + [L] 4793eb65aeaSThomas Gleixner * [8] unlock(task->pi_lock); release [P] 4803eb65aeaSThomas Gleixner * put_task_struct(task); release [R] 4813eb65aeaSThomas Gleixner * [9] check_exit_conditions_3(); [L] 4823eb65aeaSThomas Gleixner * [10] task = owner(lock); [L] 4833eb65aeaSThomas Gleixner * get_task_struct(task); [L] acquire [R] 4843eb65aeaSThomas Gleixner * lock(task->pi_lock); [L] acquire [P] 4853eb65aeaSThomas Gleixner * [11] requeue_pi_waiter(tsk, waiters(lock));[P] + [L] 4863eb65aeaSThomas Gleixner * [12] check_exit_conditions_4(); [P] + [L] 4873eb65aeaSThomas Gleixner * [13] unlock(task->pi_lock); release [P] 4883eb65aeaSThomas Gleixner * unlock(lock->wait_lock); release [L] 4893eb65aeaSThomas Gleixner * goto again; 4901696a8beSPeter Zijlstra */ 4911696a8beSPeter Zijlstra static int rt_mutex_adjust_prio_chain(struct task_struct *task, 4928930ed80SThomas Gleixner enum rtmutex_chainwalk chwalk, 4931696a8beSPeter Zijlstra struct rt_mutex *orig_lock, 49482084984SThomas Gleixner struct rt_mutex *next_lock, 4951696a8beSPeter Zijlstra struct rt_mutex_waiter *orig_waiter, 4961696a8beSPeter Zijlstra struct task_struct *top_task) 4971696a8beSPeter Zijlstra { 4981696a8beSPeter Zijlstra struct rt_mutex_waiter *waiter, *top_waiter = orig_waiter; 499a57594a1SThomas Gleixner struct rt_mutex_waiter *prerequeue_top_waiter; 5008930ed80SThomas Gleixner int ret = 0, depth = 0; 501a57594a1SThomas Gleixner struct rt_mutex *lock; 5028930ed80SThomas Gleixner bool detect_deadlock; 50367792e2cSThomas Gleixner bool requeue = true; 5041696a8beSPeter Zijlstra 5058930ed80SThomas Gleixner detect_deadlock = rt_mutex_cond_detect_deadlock(orig_waiter, chwalk); 5061696a8beSPeter Zijlstra 5071696a8beSPeter Zijlstra /* 5081696a8beSPeter Zijlstra * The (de)boosting is a step by step approach with a lot of 5091696a8beSPeter Zijlstra * pitfalls. We want this to be preemptible and we want hold a 5101696a8beSPeter Zijlstra * maximum of two locks per step. So we have to check 5111696a8beSPeter Zijlstra * carefully whether things change under us. 5121696a8beSPeter Zijlstra */ 5131696a8beSPeter Zijlstra again: 5143eb65aeaSThomas Gleixner /* 5153eb65aeaSThomas Gleixner * We limit the lock chain length for each invocation. 5163eb65aeaSThomas Gleixner */ 5171696a8beSPeter Zijlstra if (++depth > max_lock_depth) { 5181696a8beSPeter Zijlstra static int prev_max; 5191696a8beSPeter Zijlstra 5201696a8beSPeter Zijlstra /* 5211696a8beSPeter Zijlstra * Print this only once. If the admin changes the limit, 5221696a8beSPeter Zijlstra * print a new message when reaching the limit again. 5231696a8beSPeter Zijlstra */ 5241696a8beSPeter Zijlstra if (prev_max != max_lock_depth) { 5251696a8beSPeter Zijlstra prev_max = max_lock_depth; 5261696a8beSPeter Zijlstra printk(KERN_WARNING "Maximum lock depth %d reached " 5271696a8beSPeter Zijlstra "task: %s (%d)\n", max_lock_depth, 5281696a8beSPeter Zijlstra top_task->comm, task_pid_nr(top_task)); 5291696a8beSPeter Zijlstra } 5301696a8beSPeter Zijlstra put_task_struct(task); 5311696a8beSPeter Zijlstra 5323d5c9340SThomas Gleixner return -EDEADLK; 5331696a8beSPeter Zijlstra } 5343eb65aeaSThomas Gleixner 5353eb65aeaSThomas Gleixner /* 5363eb65aeaSThomas Gleixner * We are fully preemptible here and only hold the refcount on 5373eb65aeaSThomas Gleixner * @task. So everything can have changed under us since the 5383eb65aeaSThomas Gleixner * caller or our own code below (goto retry/again) dropped all 5393eb65aeaSThomas Gleixner * locks. 5403eb65aeaSThomas Gleixner */ 5411696a8beSPeter Zijlstra retry: 5421696a8beSPeter Zijlstra /* 5433eb65aeaSThomas Gleixner * [1] Task cannot go away as we did a get_task() before ! 5441696a8beSPeter Zijlstra */ 545b4abf910SThomas Gleixner raw_spin_lock_irq(&task->pi_lock); 5461696a8beSPeter Zijlstra 5473eb65aeaSThomas Gleixner /* 5483eb65aeaSThomas Gleixner * [2] Get the waiter on which @task is blocked on. 5493eb65aeaSThomas Gleixner */ 5501696a8beSPeter Zijlstra waiter = task->pi_blocked_on; 5513eb65aeaSThomas Gleixner 5523eb65aeaSThomas Gleixner /* 5533eb65aeaSThomas Gleixner * [3] check_exit_conditions_1() protected by task->pi_lock. 5543eb65aeaSThomas Gleixner */ 5553eb65aeaSThomas Gleixner 5561696a8beSPeter Zijlstra /* 5571696a8beSPeter Zijlstra * Check whether the end of the boosting chain has been 5581696a8beSPeter Zijlstra * reached or the state of the chain has changed while we 5591696a8beSPeter Zijlstra * dropped the locks. 5601696a8beSPeter Zijlstra */ 5611696a8beSPeter Zijlstra if (!waiter) 5621696a8beSPeter Zijlstra goto out_unlock_pi; 5631696a8beSPeter Zijlstra 5641696a8beSPeter Zijlstra /* 5651696a8beSPeter Zijlstra * Check the orig_waiter state. After we dropped the locks, 5661696a8beSPeter Zijlstra * the previous owner of the lock might have released the lock. 5671696a8beSPeter Zijlstra */ 5681696a8beSPeter Zijlstra if (orig_waiter && !rt_mutex_owner(orig_lock)) 5691696a8beSPeter Zijlstra goto out_unlock_pi; 5701696a8beSPeter Zijlstra 5711696a8beSPeter Zijlstra /* 57282084984SThomas Gleixner * We dropped all locks after taking a refcount on @task, so 57382084984SThomas Gleixner * the task might have moved on in the lock chain or even left 57482084984SThomas Gleixner * the chain completely and blocks now on an unrelated lock or 57582084984SThomas Gleixner * on @orig_lock. 57682084984SThomas Gleixner * 57782084984SThomas Gleixner * We stored the lock on which @task was blocked in @next_lock, 57882084984SThomas Gleixner * so we can detect the chain change. 57982084984SThomas Gleixner */ 58082084984SThomas Gleixner if (next_lock != waiter->lock) 58182084984SThomas Gleixner goto out_unlock_pi; 58282084984SThomas Gleixner 58382084984SThomas Gleixner /* 5841696a8beSPeter Zijlstra * Drop out, when the task has no waiters. Note, 5851696a8beSPeter Zijlstra * top_waiter can be NULL, when we are in the deboosting 5861696a8beSPeter Zijlstra * mode! 5871696a8beSPeter Zijlstra */ 588397335f0SThomas Gleixner if (top_waiter) { 589397335f0SThomas Gleixner if (!task_has_pi_waiters(task)) 5901696a8beSPeter Zijlstra goto out_unlock_pi; 591397335f0SThomas Gleixner /* 592397335f0SThomas Gleixner * If deadlock detection is off, we stop here if we 59367792e2cSThomas Gleixner * are not the top pi waiter of the task. If deadlock 59467792e2cSThomas Gleixner * detection is enabled we continue, but stop the 59567792e2cSThomas Gleixner * requeueing in the chain walk. 596397335f0SThomas Gleixner */ 59767792e2cSThomas Gleixner if (top_waiter != task_top_pi_waiter(task)) { 59867792e2cSThomas Gleixner if (!detect_deadlock) 599397335f0SThomas Gleixner goto out_unlock_pi; 60067792e2cSThomas Gleixner else 60167792e2cSThomas Gleixner requeue = false; 60267792e2cSThomas Gleixner } 603397335f0SThomas Gleixner } 6041696a8beSPeter Zijlstra 6051696a8beSPeter Zijlstra /* 60667792e2cSThomas Gleixner * If the waiter priority is the same as the task priority 60767792e2cSThomas Gleixner * then there is no further priority adjustment necessary. If 60867792e2cSThomas Gleixner * deadlock detection is off, we stop the chain walk. If its 60967792e2cSThomas Gleixner * enabled we continue, but stop the requeueing in the chain 61067792e2cSThomas Gleixner * walk. 6111696a8beSPeter Zijlstra */ 61267792e2cSThomas Gleixner if (waiter->prio == task->prio) { 61367792e2cSThomas Gleixner if (!detect_deadlock) 6141696a8beSPeter Zijlstra goto out_unlock_pi; 61567792e2cSThomas Gleixner else 61667792e2cSThomas Gleixner requeue = false; 61767792e2cSThomas Gleixner } 6181696a8beSPeter Zijlstra 6193eb65aeaSThomas Gleixner /* 6203eb65aeaSThomas Gleixner * [4] Get the next lock 6213eb65aeaSThomas Gleixner */ 6221696a8beSPeter Zijlstra lock = waiter->lock; 6233eb65aeaSThomas Gleixner /* 6243eb65aeaSThomas Gleixner * [5] We need to trylock here as we are holding task->pi_lock, 6253eb65aeaSThomas Gleixner * which is the reverse lock order versus the other rtmutex 6263eb65aeaSThomas Gleixner * operations. 6273eb65aeaSThomas Gleixner */ 6281696a8beSPeter Zijlstra if (!raw_spin_trylock(&lock->wait_lock)) { 629b4abf910SThomas Gleixner raw_spin_unlock_irq(&task->pi_lock); 6301696a8beSPeter Zijlstra cpu_relax(); 6311696a8beSPeter Zijlstra goto retry; 6321696a8beSPeter Zijlstra } 6331696a8beSPeter Zijlstra 634397335f0SThomas Gleixner /* 6353eb65aeaSThomas Gleixner * [6] check_exit_conditions_2() protected by task->pi_lock and 6363eb65aeaSThomas Gleixner * lock->wait_lock. 6373eb65aeaSThomas Gleixner * 638397335f0SThomas Gleixner * Deadlock detection. If the lock is the same as the original 639397335f0SThomas Gleixner * lock which caused us to walk the lock chain or if the 640397335f0SThomas Gleixner * current lock is owned by the task which initiated the chain 641397335f0SThomas Gleixner * walk, we detected a deadlock. 642397335f0SThomas Gleixner */ 6431696a8beSPeter Zijlstra if (lock == orig_lock || rt_mutex_owner(lock) == top_task) { 6448930ed80SThomas Gleixner debug_rt_mutex_deadlock(chwalk, orig_waiter, lock); 6451696a8beSPeter Zijlstra raw_spin_unlock(&lock->wait_lock); 6463d5c9340SThomas Gleixner ret = -EDEADLK; 6471696a8beSPeter Zijlstra goto out_unlock_pi; 6481696a8beSPeter Zijlstra } 6491696a8beSPeter Zijlstra 650a57594a1SThomas Gleixner /* 65167792e2cSThomas Gleixner * If we just follow the lock chain for deadlock detection, no 65267792e2cSThomas Gleixner * need to do all the requeue operations. To avoid a truckload 65367792e2cSThomas Gleixner * of conditionals around the various places below, just do the 65467792e2cSThomas Gleixner * minimum chain walk checks. 65567792e2cSThomas Gleixner */ 65667792e2cSThomas Gleixner if (!requeue) { 65767792e2cSThomas Gleixner /* 65867792e2cSThomas Gleixner * No requeue[7] here. Just release @task [8] 65967792e2cSThomas Gleixner */ 660b4abf910SThomas Gleixner raw_spin_unlock(&task->pi_lock); 66167792e2cSThomas Gleixner put_task_struct(task); 66267792e2cSThomas Gleixner 66367792e2cSThomas Gleixner /* 66467792e2cSThomas Gleixner * [9] check_exit_conditions_3 protected by lock->wait_lock. 66567792e2cSThomas Gleixner * If there is no owner of the lock, end of chain. 66667792e2cSThomas Gleixner */ 66767792e2cSThomas Gleixner if (!rt_mutex_owner(lock)) { 668b4abf910SThomas Gleixner raw_spin_unlock_irq(&lock->wait_lock); 66967792e2cSThomas Gleixner return 0; 67067792e2cSThomas Gleixner } 67167792e2cSThomas Gleixner 67267792e2cSThomas Gleixner /* [10] Grab the next task, i.e. owner of @lock */ 67367792e2cSThomas Gleixner task = rt_mutex_owner(lock); 67467792e2cSThomas Gleixner get_task_struct(task); 675b4abf910SThomas Gleixner raw_spin_lock(&task->pi_lock); 67667792e2cSThomas Gleixner 67767792e2cSThomas Gleixner /* 67867792e2cSThomas Gleixner * No requeue [11] here. We just do deadlock detection. 67967792e2cSThomas Gleixner * 68067792e2cSThomas Gleixner * [12] Store whether owner is blocked 68167792e2cSThomas Gleixner * itself. Decision is made after dropping the locks 68267792e2cSThomas Gleixner */ 68367792e2cSThomas Gleixner next_lock = task_blocked_on_lock(task); 68467792e2cSThomas Gleixner /* 68567792e2cSThomas Gleixner * Get the top waiter for the next iteration 68667792e2cSThomas Gleixner */ 68767792e2cSThomas Gleixner top_waiter = rt_mutex_top_waiter(lock); 68867792e2cSThomas Gleixner 68967792e2cSThomas Gleixner /* [13] Drop locks */ 690b4abf910SThomas Gleixner raw_spin_unlock(&task->pi_lock); 691b4abf910SThomas Gleixner raw_spin_unlock_irq(&lock->wait_lock); 69267792e2cSThomas Gleixner 69367792e2cSThomas Gleixner /* If owner is not blocked, end of chain. */ 69467792e2cSThomas Gleixner if (!next_lock) 69567792e2cSThomas Gleixner goto out_put_task; 69667792e2cSThomas Gleixner goto again; 69767792e2cSThomas Gleixner } 69867792e2cSThomas Gleixner 69967792e2cSThomas Gleixner /* 700a57594a1SThomas Gleixner * Store the current top waiter before doing the requeue 701a57594a1SThomas Gleixner * operation on @lock. We need it for the boost/deboost 702a57594a1SThomas Gleixner * decision below. 703a57594a1SThomas Gleixner */ 704a57594a1SThomas Gleixner prerequeue_top_waiter = rt_mutex_top_waiter(lock); 7051696a8beSPeter Zijlstra 7069f40a51aSDavidlohr Bueso /* [7] Requeue the waiter in the lock waiter tree. */ 707fb00aca4SPeter Zijlstra rt_mutex_dequeue(lock, waiter); 7082d3d891dSDario Faggioli waiter->prio = task->prio; 709fb00aca4SPeter Zijlstra rt_mutex_enqueue(lock, waiter); 7101696a8beSPeter Zijlstra 7113eb65aeaSThomas Gleixner /* [8] Release the task */ 712b4abf910SThomas Gleixner raw_spin_unlock(&task->pi_lock); 7132ffa5a5cSThomas Gleixner put_task_struct(task); 7142ffa5a5cSThomas Gleixner 715a57594a1SThomas Gleixner /* 7163eb65aeaSThomas Gleixner * [9] check_exit_conditions_3 protected by lock->wait_lock. 7173eb65aeaSThomas Gleixner * 718a57594a1SThomas Gleixner * We must abort the chain walk if there is no lock owner even 719a57594a1SThomas Gleixner * in the dead lock detection case, as we have nothing to 720a57594a1SThomas Gleixner * follow here. This is the end of the chain we are walking. 721a57594a1SThomas Gleixner */ 7221696a8beSPeter Zijlstra if (!rt_mutex_owner(lock)) { 7231696a8beSPeter Zijlstra /* 7243eb65aeaSThomas Gleixner * If the requeue [7] above changed the top waiter, 7253eb65aeaSThomas Gleixner * then we need to wake the new top waiter up to try 7263eb65aeaSThomas Gleixner * to get the lock. 7271696a8beSPeter Zijlstra */ 728a57594a1SThomas Gleixner if (prerequeue_top_waiter != rt_mutex_top_waiter(lock)) 7291696a8beSPeter Zijlstra wake_up_process(rt_mutex_top_waiter(lock)->task); 730b4abf910SThomas Gleixner raw_spin_unlock_irq(&lock->wait_lock); 7312ffa5a5cSThomas Gleixner return 0; 7321696a8beSPeter Zijlstra } 7331696a8beSPeter Zijlstra 7343eb65aeaSThomas Gleixner /* [10] Grab the next task, i.e. the owner of @lock */ 7351696a8beSPeter Zijlstra task = rt_mutex_owner(lock); 7361696a8beSPeter Zijlstra get_task_struct(task); 737b4abf910SThomas Gleixner raw_spin_lock(&task->pi_lock); 7381696a8beSPeter Zijlstra 7393eb65aeaSThomas Gleixner /* [11] requeue the pi waiters if necessary */ 7401696a8beSPeter Zijlstra if (waiter == rt_mutex_top_waiter(lock)) { 741a57594a1SThomas Gleixner /* 742a57594a1SThomas Gleixner * The waiter became the new top (highest priority) 743a57594a1SThomas Gleixner * waiter on the lock. Replace the previous top waiter 7449f40a51aSDavidlohr Bueso * in the owner tasks pi waiters tree with this waiter 745a57594a1SThomas Gleixner * and adjust the priority of the owner. 746a57594a1SThomas Gleixner */ 747a57594a1SThomas Gleixner rt_mutex_dequeue_pi(task, prerequeue_top_waiter); 748fb00aca4SPeter Zijlstra rt_mutex_enqueue_pi(task, waiter); 7491696a8beSPeter Zijlstra __rt_mutex_adjust_prio(task); 7501696a8beSPeter Zijlstra 751a57594a1SThomas Gleixner } else if (prerequeue_top_waiter == waiter) { 752a57594a1SThomas Gleixner /* 753a57594a1SThomas Gleixner * The waiter was the top waiter on the lock, but is 754a57594a1SThomas Gleixner * no longer the top prority waiter. Replace waiter in 7559f40a51aSDavidlohr Bueso * the owner tasks pi waiters tree with the new top 756a57594a1SThomas Gleixner * (highest priority) waiter and adjust the priority 757a57594a1SThomas Gleixner * of the owner. 758a57594a1SThomas Gleixner * The new top waiter is stored in @waiter so that 759a57594a1SThomas Gleixner * @waiter == @top_waiter evaluates to true below and 760a57594a1SThomas Gleixner * we continue to deboost the rest of the chain. 761a57594a1SThomas Gleixner */ 762fb00aca4SPeter Zijlstra rt_mutex_dequeue_pi(task, waiter); 7631696a8beSPeter Zijlstra waiter = rt_mutex_top_waiter(lock); 764fb00aca4SPeter Zijlstra rt_mutex_enqueue_pi(task, waiter); 7651696a8beSPeter Zijlstra __rt_mutex_adjust_prio(task); 766a57594a1SThomas Gleixner } else { 767a57594a1SThomas Gleixner /* 768a57594a1SThomas Gleixner * Nothing changed. No need to do any priority 769a57594a1SThomas Gleixner * adjustment. 770a57594a1SThomas Gleixner */ 7711696a8beSPeter Zijlstra } 7721696a8beSPeter Zijlstra 77382084984SThomas Gleixner /* 7743eb65aeaSThomas Gleixner * [12] check_exit_conditions_4() protected by task->pi_lock 7753eb65aeaSThomas Gleixner * and lock->wait_lock. The actual decisions are made after we 7763eb65aeaSThomas Gleixner * dropped the locks. 7773eb65aeaSThomas Gleixner * 77882084984SThomas Gleixner * Check whether the task which owns the current lock is pi 77982084984SThomas Gleixner * blocked itself. If yes we store a pointer to the lock for 78082084984SThomas Gleixner * the lock chain change detection above. After we dropped 78182084984SThomas Gleixner * task->pi_lock next_lock cannot be dereferenced anymore. 78282084984SThomas Gleixner */ 78382084984SThomas Gleixner next_lock = task_blocked_on_lock(task); 784a57594a1SThomas Gleixner /* 785a57594a1SThomas Gleixner * Store the top waiter of @lock for the end of chain walk 786a57594a1SThomas Gleixner * decision below. 787a57594a1SThomas Gleixner */ 7881696a8beSPeter Zijlstra top_waiter = rt_mutex_top_waiter(lock); 7893eb65aeaSThomas Gleixner 7903eb65aeaSThomas Gleixner /* [13] Drop the locks */ 791b4abf910SThomas Gleixner raw_spin_unlock(&task->pi_lock); 792b4abf910SThomas Gleixner raw_spin_unlock_irq(&lock->wait_lock); 7931696a8beSPeter Zijlstra 79482084984SThomas Gleixner /* 7953eb65aeaSThomas Gleixner * Make the actual exit decisions [12], based on the stored 7963eb65aeaSThomas Gleixner * values. 7973eb65aeaSThomas Gleixner * 79882084984SThomas Gleixner * We reached the end of the lock chain. Stop right here. No 79982084984SThomas Gleixner * point to go back just to figure that out. 80082084984SThomas Gleixner */ 80182084984SThomas Gleixner if (!next_lock) 80282084984SThomas Gleixner goto out_put_task; 80382084984SThomas Gleixner 804a57594a1SThomas Gleixner /* 805a57594a1SThomas Gleixner * If the current waiter is not the top waiter on the lock, 806a57594a1SThomas Gleixner * then we can stop the chain walk here if we are not in full 807a57594a1SThomas Gleixner * deadlock detection mode. 808a57594a1SThomas Gleixner */ 8091696a8beSPeter Zijlstra if (!detect_deadlock && waiter != top_waiter) 8101696a8beSPeter Zijlstra goto out_put_task; 8111696a8beSPeter Zijlstra 8121696a8beSPeter Zijlstra goto again; 8131696a8beSPeter Zijlstra 8141696a8beSPeter Zijlstra out_unlock_pi: 815b4abf910SThomas Gleixner raw_spin_unlock_irq(&task->pi_lock); 8161696a8beSPeter Zijlstra out_put_task: 8171696a8beSPeter Zijlstra put_task_struct(task); 8181696a8beSPeter Zijlstra 8191696a8beSPeter Zijlstra return ret; 8201696a8beSPeter Zijlstra } 8211696a8beSPeter Zijlstra 8221696a8beSPeter Zijlstra /* 8231696a8beSPeter Zijlstra * Try to take an rt-mutex 8241696a8beSPeter Zijlstra * 825b4abf910SThomas Gleixner * Must be called with lock->wait_lock held and interrupts disabled 8261696a8beSPeter Zijlstra * 827358c331fSThomas Gleixner * @lock: The lock to be acquired. 828358c331fSThomas Gleixner * @task: The task which wants to acquire the lock 8299f40a51aSDavidlohr Bueso * @waiter: The waiter that is queued to the lock's wait tree if the 830358c331fSThomas Gleixner * callsite called task_blocked_on_lock(), otherwise NULL 8311696a8beSPeter Zijlstra */ 8321696a8beSPeter Zijlstra static int try_to_take_rt_mutex(struct rt_mutex *lock, struct task_struct *task, 8331696a8beSPeter Zijlstra struct rt_mutex_waiter *waiter) 8341696a8beSPeter Zijlstra { 8351696a8beSPeter Zijlstra /* 836358c331fSThomas Gleixner * Before testing whether we can acquire @lock, we set the 837358c331fSThomas Gleixner * RT_MUTEX_HAS_WAITERS bit in @lock->owner. This forces all 838358c331fSThomas Gleixner * other tasks which try to modify @lock into the slow path 839358c331fSThomas Gleixner * and they serialize on @lock->wait_lock. 8401696a8beSPeter Zijlstra * 841358c331fSThomas Gleixner * The RT_MUTEX_HAS_WAITERS bit can have a transitional state 842358c331fSThomas Gleixner * as explained at the top of this file if and only if: 8431696a8beSPeter Zijlstra * 844358c331fSThomas Gleixner * - There is a lock owner. The caller must fixup the 845358c331fSThomas Gleixner * transient state if it does a trylock or leaves the lock 846358c331fSThomas Gleixner * function due to a signal or timeout. 847358c331fSThomas Gleixner * 848358c331fSThomas Gleixner * - @task acquires the lock and there are no other 849358c331fSThomas Gleixner * waiters. This is undone in rt_mutex_set_owner(@task) at 850358c331fSThomas Gleixner * the end of this function. 8511696a8beSPeter Zijlstra */ 8521696a8beSPeter Zijlstra mark_rt_mutex_waiters(lock); 8531696a8beSPeter Zijlstra 854358c331fSThomas Gleixner /* 855358c331fSThomas Gleixner * If @lock has an owner, give up. 856358c331fSThomas Gleixner */ 8571696a8beSPeter Zijlstra if (rt_mutex_owner(lock)) 8581696a8beSPeter Zijlstra return 0; 8591696a8beSPeter Zijlstra 8601696a8beSPeter Zijlstra /* 861358c331fSThomas Gleixner * If @waiter != NULL, @task has already enqueued the waiter 8629f40a51aSDavidlohr Bueso * into @lock waiter tree. If @waiter == NULL then this is a 863358c331fSThomas Gleixner * trylock attempt. 864358c331fSThomas Gleixner */ 865358c331fSThomas Gleixner if (waiter) { 866358c331fSThomas Gleixner /* 867358c331fSThomas Gleixner * If waiter is not the highest priority waiter of 868358c331fSThomas Gleixner * @lock, give up. 869358c331fSThomas Gleixner */ 870358c331fSThomas Gleixner if (waiter != rt_mutex_top_waiter(lock)) 871358c331fSThomas Gleixner return 0; 872358c331fSThomas Gleixner 873358c331fSThomas Gleixner /* 874358c331fSThomas Gleixner * We can acquire the lock. Remove the waiter from the 8759f40a51aSDavidlohr Bueso * lock waiters tree. 876358c331fSThomas Gleixner */ 877358c331fSThomas Gleixner rt_mutex_dequeue(lock, waiter); 878358c331fSThomas Gleixner 879358c331fSThomas Gleixner } else { 880358c331fSThomas Gleixner /* 881358c331fSThomas Gleixner * If the lock has waiters already we check whether @task is 882358c331fSThomas Gleixner * eligible to take over the lock. 883358c331fSThomas Gleixner * 884358c331fSThomas Gleixner * If there are no other waiters, @task can acquire 885358c331fSThomas Gleixner * the lock. @task->pi_blocked_on is NULL, so it does 886358c331fSThomas Gleixner * not need to be dequeued. 8871696a8beSPeter Zijlstra */ 8881696a8beSPeter Zijlstra if (rt_mutex_has_waiters(lock)) { 889358c331fSThomas Gleixner /* 890358c331fSThomas Gleixner * If @task->prio is greater than or equal to 891358c331fSThomas Gleixner * the top waiter priority (kernel view), 892358c331fSThomas Gleixner * @task lost. 893358c331fSThomas Gleixner */ 894358c331fSThomas Gleixner if (task->prio >= rt_mutex_top_waiter(lock)->prio) 8951696a8beSPeter Zijlstra return 0; 896358c331fSThomas Gleixner 897358c331fSThomas Gleixner /* 898358c331fSThomas Gleixner * The current top waiter stays enqueued. We 899358c331fSThomas Gleixner * don't have to change anything in the lock 900358c331fSThomas Gleixner * waiters order. 901358c331fSThomas Gleixner */ 902358c331fSThomas Gleixner } else { 903358c331fSThomas Gleixner /* 904358c331fSThomas Gleixner * No waiters. Take the lock without the 905358c331fSThomas Gleixner * pi_lock dance.@task->pi_blocked_on is NULL 906358c331fSThomas Gleixner * and we have no waiters to enqueue in @task 9079f40a51aSDavidlohr Bueso * pi waiters tree. 908358c331fSThomas Gleixner */ 909358c331fSThomas Gleixner goto takeit; 9101696a8beSPeter Zijlstra } 9111696a8beSPeter Zijlstra } 9121696a8beSPeter Zijlstra 9131696a8beSPeter Zijlstra /* 914358c331fSThomas Gleixner * Clear @task->pi_blocked_on. Requires protection by 915358c331fSThomas Gleixner * @task->pi_lock. Redundant operation for the @waiter == NULL 916358c331fSThomas Gleixner * case, but conditionals are more expensive than a redundant 917358c331fSThomas Gleixner * store. 9181696a8beSPeter Zijlstra */ 919b4abf910SThomas Gleixner raw_spin_lock(&task->pi_lock); 920358c331fSThomas Gleixner task->pi_blocked_on = NULL; 921358c331fSThomas Gleixner /* 922358c331fSThomas Gleixner * Finish the lock acquisition. @task is the new owner. If 923358c331fSThomas Gleixner * other waiters exist we have to insert the highest priority 9249f40a51aSDavidlohr Bueso * waiter into @task->pi_waiters tree. 925358c331fSThomas Gleixner */ 926358c331fSThomas Gleixner if (rt_mutex_has_waiters(lock)) 927358c331fSThomas Gleixner rt_mutex_enqueue_pi(task, rt_mutex_top_waiter(lock)); 928b4abf910SThomas Gleixner raw_spin_unlock(&task->pi_lock); 9291696a8beSPeter Zijlstra 930358c331fSThomas Gleixner takeit: 9311696a8beSPeter Zijlstra /* We got the lock. */ 9321696a8beSPeter Zijlstra debug_rt_mutex_lock(lock); 9331696a8beSPeter Zijlstra 934358c331fSThomas Gleixner /* 935358c331fSThomas Gleixner * This either preserves the RT_MUTEX_HAS_WAITERS bit if there 936358c331fSThomas Gleixner * are still waiters or clears it. 937358c331fSThomas Gleixner */ 9381696a8beSPeter Zijlstra rt_mutex_set_owner(lock, task); 9391696a8beSPeter Zijlstra 9401696a8beSPeter Zijlstra rt_mutex_deadlock_account_lock(lock, task); 9411696a8beSPeter Zijlstra 9421696a8beSPeter Zijlstra return 1; 9431696a8beSPeter Zijlstra } 9441696a8beSPeter Zijlstra 9451696a8beSPeter Zijlstra /* 9461696a8beSPeter Zijlstra * Task blocks on lock. 9471696a8beSPeter Zijlstra * 9481696a8beSPeter Zijlstra * Prepare waiter and propagate pi chain 9491696a8beSPeter Zijlstra * 950b4abf910SThomas Gleixner * This must be called with lock->wait_lock held and interrupts disabled 9511696a8beSPeter Zijlstra */ 9521696a8beSPeter Zijlstra static int task_blocks_on_rt_mutex(struct rt_mutex *lock, 9531696a8beSPeter Zijlstra struct rt_mutex_waiter *waiter, 9541696a8beSPeter Zijlstra struct task_struct *task, 9558930ed80SThomas Gleixner enum rtmutex_chainwalk chwalk) 9561696a8beSPeter Zijlstra { 9571696a8beSPeter Zijlstra struct task_struct *owner = rt_mutex_owner(lock); 9581696a8beSPeter Zijlstra struct rt_mutex_waiter *top_waiter = waiter; 95982084984SThomas Gleixner struct rt_mutex *next_lock; 9601696a8beSPeter Zijlstra int chain_walk = 0, res; 9611696a8beSPeter Zijlstra 962397335f0SThomas Gleixner /* 963397335f0SThomas Gleixner * Early deadlock detection. We really don't want the task to 964397335f0SThomas Gleixner * enqueue on itself just to untangle the mess later. It's not 965397335f0SThomas Gleixner * only an optimization. We drop the locks, so another waiter 966397335f0SThomas Gleixner * can come in before the chain walk detects the deadlock. So 967397335f0SThomas Gleixner * the other will detect the deadlock and return -EDEADLOCK, 968397335f0SThomas Gleixner * which is wrong, as the other waiter is not in a deadlock 969397335f0SThomas Gleixner * situation. 970397335f0SThomas Gleixner */ 9713d5c9340SThomas Gleixner if (owner == task) 972397335f0SThomas Gleixner return -EDEADLK; 973397335f0SThomas Gleixner 974b4abf910SThomas Gleixner raw_spin_lock(&task->pi_lock); 9751696a8beSPeter Zijlstra __rt_mutex_adjust_prio(task); 9761696a8beSPeter Zijlstra waiter->task = task; 9771696a8beSPeter Zijlstra waiter->lock = lock; 9782d3d891dSDario Faggioli waiter->prio = task->prio; 9791696a8beSPeter Zijlstra 9801696a8beSPeter Zijlstra /* Get the top priority waiter on the lock */ 9811696a8beSPeter Zijlstra if (rt_mutex_has_waiters(lock)) 9821696a8beSPeter Zijlstra top_waiter = rt_mutex_top_waiter(lock); 983fb00aca4SPeter Zijlstra rt_mutex_enqueue(lock, waiter); 9841696a8beSPeter Zijlstra 9851696a8beSPeter Zijlstra task->pi_blocked_on = waiter; 9861696a8beSPeter Zijlstra 987b4abf910SThomas Gleixner raw_spin_unlock(&task->pi_lock); 9881696a8beSPeter Zijlstra 9891696a8beSPeter Zijlstra if (!owner) 9901696a8beSPeter Zijlstra return 0; 9911696a8beSPeter Zijlstra 992b4abf910SThomas Gleixner raw_spin_lock(&owner->pi_lock); 99382084984SThomas Gleixner if (waiter == rt_mutex_top_waiter(lock)) { 994fb00aca4SPeter Zijlstra rt_mutex_dequeue_pi(owner, top_waiter); 995fb00aca4SPeter Zijlstra rt_mutex_enqueue_pi(owner, waiter); 9961696a8beSPeter Zijlstra 9971696a8beSPeter Zijlstra __rt_mutex_adjust_prio(owner); 9981696a8beSPeter Zijlstra if (owner->pi_blocked_on) 9991696a8beSPeter Zijlstra chain_walk = 1; 10008930ed80SThomas Gleixner } else if (rt_mutex_cond_detect_deadlock(waiter, chwalk)) { 10011696a8beSPeter Zijlstra chain_walk = 1; 100282084984SThomas Gleixner } 10031696a8beSPeter Zijlstra 100482084984SThomas Gleixner /* Store the lock on which owner is blocked or NULL */ 100582084984SThomas Gleixner next_lock = task_blocked_on_lock(owner); 100682084984SThomas Gleixner 1007b4abf910SThomas Gleixner raw_spin_unlock(&owner->pi_lock); 100882084984SThomas Gleixner /* 100982084984SThomas Gleixner * Even if full deadlock detection is on, if the owner is not 101082084984SThomas Gleixner * blocked itself, we can avoid finding this out in the chain 101182084984SThomas Gleixner * walk. 101282084984SThomas Gleixner */ 101382084984SThomas Gleixner if (!chain_walk || !next_lock) 10141696a8beSPeter Zijlstra return 0; 10151696a8beSPeter Zijlstra 10161696a8beSPeter Zijlstra /* 10171696a8beSPeter Zijlstra * The owner can't disappear while holding a lock, 10181696a8beSPeter Zijlstra * so the owner struct is protected by wait_lock. 10191696a8beSPeter Zijlstra * Gets dropped in rt_mutex_adjust_prio_chain()! 10201696a8beSPeter Zijlstra */ 10211696a8beSPeter Zijlstra get_task_struct(owner); 10221696a8beSPeter Zijlstra 1023b4abf910SThomas Gleixner raw_spin_unlock_irq(&lock->wait_lock); 10241696a8beSPeter Zijlstra 10258930ed80SThomas Gleixner res = rt_mutex_adjust_prio_chain(owner, chwalk, lock, 102682084984SThomas Gleixner next_lock, waiter, task); 10271696a8beSPeter Zijlstra 1028b4abf910SThomas Gleixner raw_spin_lock_irq(&lock->wait_lock); 10291696a8beSPeter Zijlstra 10301696a8beSPeter Zijlstra return res; 10311696a8beSPeter Zijlstra } 10321696a8beSPeter Zijlstra 10331696a8beSPeter Zijlstra /* 10349f40a51aSDavidlohr Bueso * Remove the top waiter from the current tasks pi waiter tree and 103545ab4effSDavidlohr Bueso * queue it up. 10361696a8beSPeter Zijlstra * 1037b4abf910SThomas Gleixner * Called with lock->wait_lock held and interrupts disabled. 10381696a8beSPeter Zijlstra */ 103945ab4effSDavidlohr Bueso static void mark_wakeup_next_waiter(struct wake_q_head *wake_q, 104045ab4effSDavidlohr Bueso struct rt_mutex *lock) 10411696a8beSPeter Zijlstra { 10421696a8beSPeter Zijlstra struct rt_mutex_waiter *waiter; 10431696a8beSPeter Zijlstra 1044b4abf910SThomas Gleixner raw_spin_lock(¤t->pi_lock); 10451696a8beSPeter Zijlstra 10461696a8beSPeter Zijlstra waiter = rt_mutex_top_waiter(lock); 10471696a8beSPeter Zijlstra 10481696a8beSPeter Zijlstra /* 10491696a8beSPeter Zijlstra * Remove it from current->pi_waiters. We do not adjust a 10501696a8beSPeter Zijlstra * possible priority boost right now. We execute wakeup in the 10511696a8beSPeter Zijlstra * boosted mode and go back to normal after releasing 10521696a8beSPeter Zijlstra * lock->wait_lock. 10531696a8beSPeter Zijlstra */ 1054fb00aca4SPeter Zijlstra rt_mutex_dequeue_pi(current, waiter); 10551696a8beSPeter Zijlstra 105627e35715SThomas Gleixner /* 105727e35715SThomas Gleixner * As we are waking up the top waiter, and the waiter stays 105827e35715SThomas Gleixner * queued on the lock until it gets the lock, this lock 105927e35715SThomas Gleixner * obviously has waiters. Just set the bit here and this has 106027e35715SThomas Gleixner * the added benefit of forcing all new tasks into the 106127e35715SThomas Gleixner * slow path making sure no task of lower priority than 106227e35715SThomas Gleixner * the top waiter can steal this lock. 106327e35715SThomas Gleixner */ 106427e35715SThomas Gleixner lock->owner = (void *) RT_MUTEX_HAS_WAITERS; 10651696a8beSPeter Zijlstra 1066b4abf910SThomas Gleixner raw_spin_unlock(¤t->pi_lock); 10671696a8beSPeter Zijlstra 106845ab4effSDavidlohr Bueso wake_q_add(wake_q, waiter->task); 10691696a8beSPeter Zijlstra } 10701696a8beSPeter Zijlstra 10711696a8beSPeter Zijlstra /* 10721696a8beSPeter Zijlstra * Remove a waiter from a lock and give up 10731696a8beSPeter Zijlstra * 1074b4abf910SThomas Gleixner * Must be called with lock->wait_lock held and interrupts disabled. I must 10751696a8beSPeter Zijlstra * have just failed to try_to_take_rt_mutex(). 10761696a8beSPeter Zijlstra */ 10771696a8beSPeter Zijlstra static void remove_waiter(struct rt_mutex *lock, 10781696a8beSPeter Zijlstra struct rt_mutex_waiter *waiter) 10791696a8beSPeter Zijlstra { 10801ca7b860SThomas Gleixner bool is_top_waiter = (waiter == rt_mutex_top_waiter(lock)); 10811696a8beSPeter Zijlstra struct task_struct *owner = rt_mutex_owner(lock); 10821ca7b860SThomas Gleixner struct rt_mutex *next_lock; 10831696a8beSPeter Zijlstra 1084b4abf910SThomas Gleixner raw_spin_lock(¤t->pi_lock); 1085fb00aca4SPeter Zijlstra rt_mutex_dequeue(lock, waiter); 10861696a8beSPeter Zijlstra current->pi_blocked_on = NULL; 1087b4abf910SThomas Gleixner raw_spin_unlock(¤t->pi_lock); 10881696a8beSPeter Zijlstra 10891ca7b860SThomas Gleixner /* 10901ca7b860SThomas Gleixner * Only update priority if the waiter was the highest priority 10911ca7b860SThomas Gleixner * waiter of the lock and there is an owner to update. 10921ca7b860SThomas Gleixner */ 10931ca7b860SThomas Gleixner if (!owner || !is_top_waiter) 10941696a8beSPeter Zijlstra return; 10951696a8beSPeter Zijlstra 1096b4abf910SThomas Gleixner raw_spin_lock(&owner->pi_lock); 10971696a8beSPeter Zijlstra 1098fb00aca4SPeter Zijlstra rt_mutex_dequeue_pi(owner, waiter); 10991696a8beSPeter Zijlstra 11001ca7b860SThomas Gleixner if (rt_mutex_has_waiters(lock)) 11011ca7b860SThomas Gleixner rt_mutex_enqueue_pi(owner, rt_mutex_top_waiter(lock)); 11021696a8beSPeter Zijlstra 11031696a8beSPeter Zijlstra __rt_mutex_adjust_prio(owner); 11041696a8beSPeter Zijlstra 110582084984SThomas Gleixner /* Store the lock on which owner is blocked or NULL */ 110682084984SThomas Gleixner next_lock = task_blocked_on_lock(owner); 11071696a8beSPeter Zijlstra 1108b4abf910SThomas Gleixner raw_spin_unlock(&owner->pi_lock); 11091696a8beSPeter Zijlstra 11101ca7b860SThomas Gleixner /* 11111ca7b860SThomas Gleixner * Don't walk the chain, if the owner task is not blocked 11121ca7b860SThomas Gleixner * itself. 11131ca7b860SThomas Gleixner */ 111482084984SThomas Gleixner if (!next_lock) 11151696a8beSPeter Zijlstra return; 11161696a8beSPeter Zijlstra 11171696a8beSPeter Zijlstra /* gets dropped in rt_mutex_adjust_prio_chain()! */ 11181696a8beSPeter Zijlstra get_task_struct(owner); 11191696a8beSPeter Zijlstra 1120b4abf910SThomas Gleixner raw_spin_unlock_irq(&lock->wait_lock); 11211696a8beSPeter Zijlstra 11228930ed80SThomas Gleixner rt_mutex_adjust_prio_chain(owner, RT_MUTEX_MIN_CHAINWALK, lock, 11238930ed80SThomas Gleixner next_lock, NULL, current); 11241696a8beSPeter Zijlstra 1125b4abf910SThomas Gleixner raw_spin_lock_irq(&lock->wait_lock); 11261696a8beSPeter Zijlstra } 11271696a8beSPeter Zijlstra 11281696a8beSPeter Zijlstra /* 11291696a8beSPeter Zijlstra * Recheck the pi chain, in case we got a priority setting 11301696a8beSPeter Zijlstra * 11311696a8beSPeter Zijlstra * Called from sched_setscheduler 11321696a8beSPeter Zijlstra */ 11331696a8beSPeter Zijlstra void rt_mutex_adjust_pi(struct task_struct *task) 11341696a8beSPeter Zijlstra { 11351696a8beSPeter Zijlstra struct rt_mutex_waiter *waiter; 113682084984SThomas Gleixner struct rt_mutex *next_lock; 11371696a8beSPeter Zijlstra unsigned long flags; 11381696a8beSPeter Zijlstra 11391696a8beSPeter Zijlstra raw_spin_lock_irqsave(&task->pi_lock, flags); 11401696a8beSPeter Zijlstra 11411696a8beSPeter Zijlstra waiter = task->pi_blocked_on; 11422d3d891dSDario Faggioli if (!waiter || (waiter->prio == task->prio && 11432d3d891dSDario Faggioli !dl_prio(task->prio))) { 11441696a8beSPeter Zijlstra raw_spin_unlock_irqrestore(&task->pi_lock, flags); 11451696a8beSPeter Zijlstra return; 11461696a8beSPeter Zijlstra } 114782084984SThomas Gleixner next_lock = waiter->lock; 11481696a8beSPeter Zijlstra raw_spin_unlock_irqrestore(&task->pi_lock, flags); 11491696a8beSPeter Zijlstra 11501696a8beSPeter Zijlstra /* gets dropped in rt_mutex_adjust_prio_chain()! */ 11511696a8beSPeter Zijlstra get_task_struct(task); 115282084984SThomas Gleixner 11538930ed80SThomas Gleixner rt_mutex_adjust_prio_chain(task, RT_MUTEX_MIN_CHAINWALK, NULL, 11548930ed80SThomas Gleixner next_lock, NULL, task); 11551696a8beSPeter Zijlstra } 11561696a8beSPeter Zijlstra 11571696a8beSPeter Zijlstra /** 11581696a8beSPeter Zijlstra * __rt_mutex_slowlock() - Perform the wait-wake-try-to-take loop 11591696a8beSPeter Zijlstra * @lock: the rt_mutex to take 11601696a8beSPeter Zijlstra * @state: the state the task should block in (TASK_INTERRUPTIBLE 11611696a8beSPeter Zijlstra * or TASK_UNINTERRUPTIBLE) 11621696a8beSPeter Zijlstra * @timeout: the pre-initialized and started timer, or NULL for none 11631696a8beSPeter Zijlstra * @waiter: the pre-initialized rt_mutex_waiter 11641696a8beSPeter Zijlstra * 1165b4abf910SThomas Gleixner * Must be called with lock->wait_lock held and interrupts disabled 11661696a8beSPeter Zijlstra */ 11671696a8beSPeter Zijlstra static int __sched 11681696a8beSPeter Zijlstra __rt_mutex_slowlock(struct rt_mutex *lock, int state, 11691696a8beSPeter Zijlstra struct hrtimer_sleeper *timeout, 11701696a8beSPeter Zijlstra struct rt_mutex_waiter *waiter) 11711696a8beSPeter Zijlstra { 11721696a8beSPeter Zijlstra int ret = 0; 11731696a8beSPeter Zijlstra 11741696a8beSPeter Zijlstra for (;;) { 11751696a8beSPeter Zijlstra /* Try to acquire the lock: */ 11761696a8beSPeter Zijlstra if (try_to_take_rt_mutex(lock, current, waiter)) 11771696a8beSPeter Zijlstra break; 11781696a8beSPeter Zijlstra 11791696a8beSPeter Zijlstra /* 11801696a8beSPeter Zijlstra * TASK_INTERRUPTIBLE checks for signals and 11811696a8beSPeter Zijlstra * timeout. Ignored otherwise. 11821696a8beSPeter Zijlstra */ 11834009f4b3SSteven Rostedt (VMware) if (likely(state == TASK_INTERRUPTIBLE)) { 11841696a8beSPeter Zijlstra /* Signal pending? */ 11851696a8beSPeter Zijlstra if (signal_pending(current)) 11861696a8beSPeter Zijlstra ret = -EINTR; 11871696a8beSPeter Zijlstra if (timeout && !timeout->task) 11881696a8beSPeter Zijlstra ret = -ETIMEDOUT; 11891696a8beSPeter Zijlstra if (ret) 11901696a8beSPeter Zijlstra break; 11911696a8beSPeter Zijlstra } 11921696a8beSPeter Zijlstra 1193b4abf910SThomas Gleixner raw_spin_unlock_irq(&lock->wait_lock); 11941696a8beSPeter Zijlstra 11951696a8beSPeter Zijlstra debug_rt_mutex_print_deadlock(waiter); 11961696a8beSPeter Zijlstra 11971b0b7c17SDavidlohr Bueso schedule(); 11981696a8beSPeter Zijlstra 1199b4abf910SThomas Gleixner raw_spin_lock_irq(&lock->wait_lock); 12001696a8beSPeter Zijlstra set_current_state(state); 12011696a8beSPeter Zijlstra } 12021696a8beSPeter Zijlstra 1203afffc6c1SDavidlohr Bueso __set_current_state(TASK_RUNNING); 12041696a8beSPeter Zijlstra return ret; 12051696a8beSPeter Zijlstra } 12061696a8beSPeter Zijlstra 12073d5c9340SThomas Gleixner static void rt_mutex_handle_deadlock(int res, int detect_deadlock, 12083d5c9340SThomas Gleixner struct rt_mutex_waiter *w) 12093d5c9340SThomas Gleixner { 12103d5c9340SThomas Gleixner /* 12113d5c9340SThomas Gleixner * If the result is not -EDEADLOCK or the caller requested 12123d5c9340SThomas Gleixner * deadlock detection, nothing to do here. 12133d5c9340SThomas Gleixner */ 12143d5c9340SThomas Gleixner if (res != -EDEADLOCK || detect_deadlock) 12153d5c9340SThomas Gleixner return; 12163d5c9340SThomas Gleixner 12173d5c9340SThomas Gleixner /* 12183d5c9340SThomas Gleixner * Yell lowdly and stop the task right here. 12193d5c9340SThomas Gleixner */ 12203d5c9340SThomas Gleixner rt_mutex_print_deadlock(w); 12213d5c9340SThomas Gleixner while (1) { 12223d5c9340SThomas Gleixner set_current_state(TASK_INTERRUPTIBLE); 12233d5c9340SThomas Gleixner schedule(); 12243d5c9340SThomas Gleixner } 12253d5c9340SThomas Gleixner } 12263d5c9340SThomas Gleixner 12271696a8beSPeter Zijlstra /* 12281696a8beSPeter Zijlstra * Slow path lock function: 12291696a8beSPeter Zijlstra */ 12301696a8beSPeter Zijlstra static int __sched 12311696a8beSPeter Zijlstra rt_mutex_slowlock(struct rt_mutex *lock, int state, 12321696a8beSPeter Zijlstra struct hrtimer_sleeper *timeout, 12338930ed80SThomas Gleixner enum rtmutex_chainwalk chwalk) 12341696a8beSPeter Zijlstra { 12351696a8beSPeter Zijlstra struct rt_mutex_waiter waiter; 1236b4abf910SThomas Gleixner unsigned long flags; 12371696a8beSPeter Zijlstra int ret = 0; 12381696a8beSPeter Zijlstra 12391696a8beSPeter Zijlstra debug_rt_mutex_init_waiter(&waiter); 1240fb00aca4SPeter Zijlstra RB_CLEAR_NODE(&waiter.pi_tree_entry); 1241fb00aca4SPeter Zijlstra RB_CLEAR_NODE(&waiter.tree_entry); 12421696a8beSPeter Zijlstra 1243b4abf910SThomas Gleixner /* 1244b4abf910SThomas Gleixner * Technically we could use raw_spin_[un]lock_irq() here, but this can 1245b4abf910SThomas Gleixner * be called in early boot if the cmpxchg() fast path is disabled 1246b4abf910SThomas Gleixner * (debug, no architecture support). In this case we will acquire the 1247b4abf910SThomas Gleixner * rtmutex with lock->wait_lock held. But we cannot unconditionally 1248b4abf910SThomas Gleixner * enable interrupts in that early boot case. So we need to use the 1249b4abf910SThomas Gleixner * irqsave/restore variants. 1250b4abf910SThomas Gleixner */ 1251b4abf910SThomas Gleixner raw_spin_lock_irqsave(&lock->wait_lock, flags); 12521696a8beSPeter Zijlstra 12531696a8beSPeter Zijlstra /* Try to acquire the lock again: */ 12541696a8beSPeter Zijlstra if (try_to_take_rt_mutex(lock, current, NULL)) { 1255b4abf910SThomas Gleixner raw_spin_unlock_irqrestore(&lock->wait_lock, flags); 12561696a8beSPeter Zijlstra return 0; 12571696a8beSPeter Zijlstra } 12581696a8beSPeter Zijlstra 12591696a8beSPeter Zijlstra set_current_state(state); 12601696a8beSPeter Zijlstra 12611696a8beSPeter Zijlstra /* Setup the timer, when timeout != NULL */ 1262ccdd92c1SThomas Gleixner if (unlikely(timeout)) 12631696a8beSPeter Zijlstra hrtimer_start_expires(&timeout->timer, HRTIMER_MODE_ABS); 12641696a8beSPeter Zijlstra 12658930ed80SThomas Gleixner ret = task_blocks_on_rt_mutex(lock, &waiter, current, chwalk); 12661696a8beSPeter Zijlstra 12671696a8beSPeter Zijlstra if (likely(!ret)) 1268afffc6c1SDavidlohr Bueso /* sleep on the mutex */ 12691696a8beSPeter Zijlstra ret = __rt_mutex_slowlock(lock, state, timeout, &waiter); 12701696a8beSPeter Zijlstra 12713d5c9340SThomas Gleixner if (unlikely(ret)) { 12729d3e2d02SSebastian Andrzej Siewior __set_current_state(TASK_RUNNING); 12738d1e5a1aSSebastian Andrzej Siewior if (rt_mutex_has_waiters(lock)) 12741696a8beSPeter Zijlstra remove_waiter(lock, &waiter); 12758930ed80SThomas Gleixner rt_mutex_handle_deadlock(ret, chwalk, &waiter); 12763d5c9340SThomas Gleixner } 12771696a8beSPeter Zijlstra 12781696a8beSPeter Zijlstra /* 12791696a8beSPeter Zijlstra * try_to_take_rt_mutex() sets the waiter bit 12801696a8beSPeter Zijlstra * unconditionally. We might have to fix that up. 12811696a8beSPeter Zijlstra */ 12821696a8beSPeter Zijlstra fixup_rt_mutex_waiters(lock); 12831696a8beSPeter Zijlstra 1284b4abf910SThomas Gleixner raw_spin_unlock_irqrestore(&lock->wait_lock, flags); 12851696a8beSPeter Zijlstra 12861696a8beSPeter Zijlstra /* Remove pending timer: */ 12871696a8beSPeter Zijlstra if (unlikely(timeout)) 12881696a8beSPeter Zijlstra hrtimer_cancel(&timeout->timer); 12891696a8beSPeter Zijlstra 12901696a8beSPeter Zijlstra debug_rt_mutex_free_waiter(&waiter); 12911696a8beSPeter Zijlstra 12921696a8beSPeter Zijlstra return ret; 12931696a8beSPeter Zijlstra } 12941696a8beSPeter Zijlstra 12951696a8beSPeter Zijlstra /* 12961696a8beSPeter Zijlstra * Slow path try-lock function: 12971696a8beSPeter Zijlstra */ 129888f2b4c1SThomas Gleixner static inline int rt_mutex_slowtrylock(struct rt_mutex *lock) 12991696a8beSPeter Zijlstra { 1300b4abf910SThomas Gleixner unsigned long flags; 130188f2b4c1SThomas Gleixner int ret; 13021696a8beSPeter Zijlstra 130388f2b4c1SThomas Gleixner /* 130488f2b4c1SThomas Gleixner * If the lock already has an owner we fail to get the lock. 130588f2b4c1SThomas Gleixner * This can be done without taking the @lock->wait_lock as 130688f2b4c1SThomas Gleixner * it is only being read, and this is a trylock anyway. 130788f2b4c1SThomas Gleixner */ 130888f2b4c1SThomas Gleixner if (rt_mutex_owner(lock)) 130988f2b4c1SThomas Gleixner return 0; 131088f2b4c1SThomas Gleixner 131188f2b4c1SThomas Gleixner /* 1312b4abf910SThomas Gleixner * The mutex has currently no owner. Lock the wait lock and try to 1313b4abf910SThomas Gleixner * acquire the lock. We use irqsave here to support early boot calls. 131488f2b4c1SThomas Gleixner */ 1315b4abf910SThomas Gleixner raw_spin_lock_irqsave(&lock->wait_lock, flags); 13161696a8beSPeter Zijlstra 13171696a8beSPeter Zijlstra ret = try_to_take_rt_mutex(lock, current, NULL); 131888f2b4c1SThomas Gleixner 13191696a8beSPeter Zijlstra /* 132088f2b4c1SThomas Gleixner * try_to_take_rt_mutex() sets the lock waiters bit 132188f2b4c1SThomas Gleixner * unconditionally. Clean this up. 13221696a8beSPeter Zijlstra */ 13231696a8beSPeter Zijlstra fixup_rt_mutex_waiters(lock); 13241696a8beSPeter Zijlstra 1325b4abf910SThomas Gleixner raw_spin_unlock_irqrestore(&lock->wait_lock, flags); 13261696a8beSPeter Zijlstra 13271696a8beSPeter Zijlstra return ret; 13281696a8beSPeter Zijlstra } 13291696a8beSPeter Zijlstra 13301696a8beSPeter Zijlstra /* 1331802ab58dSSebastian Andrzej Siewior * Slow path to release a rt-mutex. 1332802ab58dSSebastian Andrzej Siewior * Return whether the current task needs to undo a potential priority boosting. 13331696a8beSPeter Zijlstra */ 1334802ab58dSSebastian Andrzej Siewior static bool __sched rt_mutex_slowunlock(struct rt_mutex *lock, 1335802ab58dSSebastian Andrzej Siewior struct wake_q_head *wake_q) 13361696a8beSPeter Zijlstra { 1337b4abf910SThomas Gleixner unsigned long flags; 1338b4abf910SThomas Gleixner 1339b4abf910SThomas Gleixner /* irqsave required to support early boot calls */ 1340b4abf910SThomas Gleixner raw_spin_lock_irqsave(&lock->wait_lock, flags); 13411696a8beSPeter Zijlstra 13421696a8beSPeter Zijlstra debug_rt_mutex_unlock(lock); 13431696a8beSPeter Zijlstra 13441696a8beSPeter Zijlstra rt_mutex_deadlock_account_unlock(current); 13451696a8beSPeter Zijlstra 134627e35715SThomas Gleixner /* 134727e35715SThomas Gleixner * We must be careful here if the fast path is enabled. If we 134827e35715SThomas Gleixner * have no waiters queued we cannot set owner to NULL here 134927e35715SThomas Gleixner * because of: 135027e35715SThomas Gleixner * 135127e35715SThomas Gleixner * foo->lock->owner = NULL; 135227e35715SThomas Gleixner * rtmutex_lock(foo->lock); <- fast path 135327e35715SThomas Gleixner * free = atomic_dec_and_test(foo->refcnt); 135427e35715SThomas Gleixner * rtmutex_unlock(foo->lock); <- fast path 135527e35715SThomas Gleixner * if (free) 135627e35715SThomas Gleixner * kfree(foo); 135727e35715SThomas Gleixner * raw_spin_unlock(foo->lock->wait_lock); 135827e35715SThomas Gleixner * 135927e35715SThomas Gleixner * So for the fastpath enabled kernel: 136027e35715SThomas Gleixner * 136127e35715SThomas Gleixner * Nothing can set the waiters bit as long as we hold 136227e35715SThomas Gleixner * lock->wait_lock. So we do the following sequence: 136327e35715SThomas Gleixner * 136427e35715SThomas Gleixner * owner = rt_mutex_owner(lock); 136527e35715SThomas Gleixner * clear_rt_mutex_waiters(lock); 136627e35715SThomas Gleixner * raw_spin_unlock(&lock->wait_lock); 136727e35715SThomas Gleixner * if (cmpxchg(&lock->owner, owner, 0) == owner) 136827e35715SThomas Gleixner * return; 136927e35715SThomas Gleixner * goto retry; 137027e35715SThomas Gleixner * 137127e35715SThomas Gleixner * The fastpath disabled variant is simple as all access to 137227e35715SThomas Gleixner * lock->owner is serialized by lock->wait_lock: 137327e35715SThomas Gleixner * 137427e35715SThomas Gleixner * lock->owner = NULL; 137527e35715SThomas Gleixner * raw_spin_unlock(&lock->wait_lock); 137627e35715SThomas Gleixner */ 137727e35715SThomas Gleixner while (!rt_mutex_has_waiters(lock)) { 137827e35715SThomas Gleixner /* Drops lock->wait_lock ! */ 1379b4abf910SThomas Gleixner if (unlock_rt_mutex_safe(lock, flags) == true) 1380802ab58dSSebastian Andrzej Siewior return false; 138127e35715SThomas Gleixner /* Relock the rtmutex and try again */ 1382b4abf910SThomas Gleixner raw_spin_lock_irqsave(&lock->wait_lock, flags); 13831696a8beSPeter Zijlstra } 13841696a8beSPeter Zijlstra 138527e35715SThomas Gleixner /* 138627e35715SThomas Gleixner * The wakeup next waiter path does not suffer from the above 138727e35715SThomas Gleixner * race. See the comments there. 138845ab4effSDavidlohr Bueso * 138945ab4effSDavidlohr Bueso * Queue the next waiter for wakeup once we release the wait_lock. 139027e35715SThomas Gleixner */ 1391802ab58dSSebastian Andrzej Siewior mark_wakeup_next_waiter(wake_q, lock); 13921696a8beSPeter Zijlstra 1393b4abf910SThomas Gleixner raw_spin_unlock_irqrestore(&lock->wait_lock, flags); 13941696a8beSPeter Zijlstra 1395802ab58dSSebastian Andrzej Siewior /* check PI boosting */ 1396802ab58dSSebastian Andrzej Siewior return true; 13971696a8beSPeter Zijlstra } 13981696a8beSPeter Zijlstra 13991696a8beSPeter Zijlstra /* 14001696a8beSPeter Zijlstra * debug aware fast / slowpath lock,trylock,unlock 14011696a8beSPeter Zijlstra * 14021696a8beSPeter Zijlstra * The atomic acquire/release ops are compiled away, when either the 14031696a8beSPeter Zijlstra * architecture does not support cmpxchg or when debugging is enabled. 14041696a8beSPeter Zijlstra */ 14051696a8beSPeter Zijlstra static inline int 14061696a8beSPeter Zijlstra rt_mutex_fastlock(struct rt_mutex *lock, int state, 14071696a8beSPeter Zijlstra int (*slowfn)(struct rt_mutex *lock, int state, 14081696a8beSPeter Zijlstra struct hrtimer_sleeper *timeout, 14098930ed80SThomas Gleixner enum rtmutex_chainwalk chwalk)) 14101696a8beSPeter Zijlstra { 1411700318d1SDavidlohr Bueso if (likely(rt_mutex_cmpxchg_acquire(lock, NULL, current))) { 14121696a8beSPeter Zijlstra rt_mutex_deadlock_account_lock(lock, current); 14131696a8beSPeter Zijlstra return 0; 14141696a8beSPeter Zijlstra } else 14158930ed80SThomas Gleixner return slowfn(lock, state, NULL, RT_MUTEX_MIN_CHAINWALK); 14161696a8beSPeter Zijlstra } 14171696a8beSPeter Zijlstra 14181696a8beSPeter Zijlstra static inline int 14191696a8beSPeter Zijlstra rt_mutex_timed_fastlock(struct rt_mutex *lock, int state, 14208930ed80SThomas Gleixner struct hrtimer_sleeper *timeout, 14218930ed80SThomas Gleixner enum rtmutex_chainwalk chwalk, 14221696a8beSPeter Zijlstra int (*slowfn)(struct rt_mutex *lock, int state, 14231696a8beSPeter Zijlstra struct hrtimer_sleeper *timeout, 14248930ed80SThomas Gleixner enum rtmutex_chainwalk chwalk)) 14251696a8beSPeter Zijlstra { 14268930ed80SThomas Gleixner if (chwalk == RT_MUTEX_MIN_CHAINWALK && 1427700318d1SDavidlohr Bueso likely(rt_mutex_cmpxchg_acquire(lock, NULL, current))) { 14281696a8beSPeter Zijlstra rt_mutex_deadlock_account_lock(lock, current); 14291696a8beSPeter Zijlstra return 0; 14301696a8beSPeter Zijlstra } else 14318930ed80SThomas Gleixner return slowfn(lock, state, timeout, chwalk); 14321696a8beSPeter Zijlstra } 14331696a8beSPeter Zijlstra 14341696a8beSPeter Zijlstra static inline int 14351696a8beSPeter Zijlstra rt_mutex_fasttrylock(struct rt_mutex *lock, 14361696a8beSPeter Zijlstra int (*slowfn)(struct rt_mutex *lock)) 14371696a8beSPeter Zijlstra { 1438700318d1SDavidlohr Bueso if (likely(rt_mutex_cmpxchg_acquire(lock, NULL, current))) { 14391696a8beSPeter Zijlstra rt_mutex_deadlock_account_lock(lock, current); 14401696a8beSPeter Zijlstra return 1; 14411696a8beSPeter Zijlstra } 14421696a8beSPeter Zijlstra return slowfn(lock); 14431696a8beSPeter Zijlstra } 14441696a8beSPeter Zijlstra 14451696a8beSPeter Zijlstra static inline void 14461696a8beSPeter Zijlstra rt_mutex_fastunlock(struct rt_mutex *lock, 1447802ab58dSSebastian Andrzej Siewior bool (*slowfn)(struct rt_mutex *lock, 1448802ab58dSSebastian Andrzej Siewior struct wake_q_head *wqh)) 14491696a8beSPeter Zijlstra { 1450194a6b5bSWaiman Long DEFINE_WAKE_Q(wake_q); 1451802ab58dSSebastian Andrzej Siewior 1452700318d1SDavidlohr Bueso if (likely(rt_mutex_cmpxchg_release(lock, current, NULL))) { 14531696a8beSPeter Zijlstra rt_mutex_deadlock_account_unlock(current); 1454802ab58dSSebastian Andrzej Siewior 1455802ab58dSSebastian Andrzej Siewior } else { 1456802ab58dSSebastian Andrzej Siewior bool deboost = slowfn(lock, &wake_q); 1457802ab58dSSebastian Andrzej Siewior 1458802ab58dSSebastian Andrzej Siewior wake_up_q(&wake_q); 1459802ab58dSSebastian Andrzej Siewior 1460802ab58dSSebastian Andrzej Siewior /* Undo pi boosting if necessary: */ 1461802ab58dSSebastian Andrzej Siewior if (deboost) 1462802ab58dSSebastian Andrzej Siewior rt_mutex_adjust_prio(current); 1463802ab58dSSebastian Andrzej Siewior } 14641696a8beSPeter Zijlstra } 14651696a8beSPeter Zijlstra 14661696a8beSPeter Zijlstra /** 14671696a8beSPeter Zijlstra * rt_mutex_lock - lock a rt_mutex 14681696a8beSPeter Zijlstra * 14691696a8beSPeter Zijlstra * @lock: the rt_mutex to be locked 14701696a8beSPeter Zijlstra */ 14711696a8beSPeter Zijlstra void __sched rt_mutex_lock(struct rt_mutex *lock) 14721696a8beSPeter Zijlstra { 14731696a8beSPeter Zijlstra might_sleep(); 14741696a8beSPeter Zijlstra 1475c051b21fSThomas Gleixner rt_mutex_fastlock(lock, TASK_UNINTERRUPTIBLE, rt_mutex_slowlock); 14761696a8beSPeter Zijlstra } 14771696a8beSPeter Zijlstra EXPORT_SYMBOL_GPL(rt_mutex_lock); 14781696a8beSPeter Zijlstra 14791696a8beSPeter Zijlstra /** 14801696a8beSPeter Zijlstra * rt_mutex_lock_interruptible - lock a rt_mutex interruptible 14811696a8beSPeter Zijlstra * 14821696a8beSPeter Zijlstra * @lock: the rt_mutex to be locked 14831696a8beSPeter Zijlstra * 14841696a8beSPeter Zijlstra * Returns: 14851696a8beSPeter Zijlstra * 0 on success 14861696a8beSPeter Zijlstra * -EINTR when interrupted by a signal 14871696a8beSPeter Zijlstra */ 1488c051b21fSThomas Gleixner int __sched rt_mutex_lock_interruptible(struct rt_mutex *lock) 14891696a8beSPeter Zijlstra { 14901696a8beSPeter Zijlstra might_sleep(); 14911696a8beSPeter Zijlstra 1492c051b21fSThomas Gleixner return rt_mutex_fastlock(lock, TASK_INTERRUPTIBLE, rt_mutex_slowlock); 14931696a8beSPeter Zijlstra } 14941696a8beSPeter Zijlstra EXPORT_SYMBOL_GPL(rt_mutex_lock_interruptible); 14951696a8beSPeter Zijlstra 1496c051b21fSThomas Gleixner /* 1497c051b21fSThomas Gleixner * Futex variant with full deadlock detection. 1498c051b21fSThomas Gleixner */ 1499c051b21fSThomas Gleixner int rt_mutex_timed_futex_lock(struct rt_mutex *lock, 1500c051b21fSThomas Gleixner struct hrtimer_sleeper *timeout) 1501c051b21fSThomas Gleixner { 1502c051b21fSThomas Gleixner might_sleep(); 1503c051b21fSThomas Gleixner 15048930ed80SThomas Gleixner return rt_mutex_timed_fastlock(lock, TASK_INTERRUPTIBLE, timeout, 15058930ed80SThomas Gleixner RT_MUTEX_FULL_CHAINWALK, 1506c051b21fSThomas Gleixner rt_mutex_slowlock); 1507c051b21fSThomas Gleixner } 1508c051b21fSThomas Gleixner 15091696a8beSPeter Zijlstra /** 15101696a8beSPeter Zijlstra * rt_mutex_timed_lock - lock a rt_mutex interruptible 15111696a8beSPeter Zijlstra * the timeout structure is provided 15121696a8beSPeter Zijlstra * by the caller 15131696a8beSPeter Zijlstra * 15141696a8beSPeter Zijlstra * @lock: the rt_mutex to be locked 15151696a8beSPeter Zijlstra * @timeout: timeout structure or NULL (no timeout) 15161696a8beSPeter Zijlstra * 15171696a8beSPeter Zijlstra * Returns: 15181696a8beSPeter Zijlstra * 0 on success 15191696a8beSPeter Zijlstra * -EINTR when interrupted by a signal 15201696a8beSPeter Zijlstra * -ETIMEDOUT when the timeout expired 15211696a8beSPeter Zijlstra */ 15221696a8beSPeter Zijlstra int 1523c051b21fSThomas Gleixner rt_mutex_timed_lock(struct rt_mutex *lock, struct hrtimer_sleeper *timeout) 15241696a8beSPeter Zijlstra { 15251696a8beSPeter Zijlstra might_sleep(); 15261696a8beSPeter Zijlstra 15278930ed80SThomas Gleixner return rt_mutex_timed_fastlock(lock, TASK_INTERRUPTIBLE, timeout, 15288930ed80SThomas Gleixner RT_MUTEX_MIN_CHAINWALK, 1529c051b21fSThomas Gleixner rt_mutex_slowlock); 15301696a8beSPeter Zijlstra } 15311696a8beSPeter Zijlstra EXPORT_SYMBOL_GPL(rt_mutex_timed_lock); 15321696a8beSPeter Zijlstra 15331696a8beSPeter Zijlstra /** 15341696a8beSPeter Zijlstra * rt_mutex_trylock - try to lock a rt_mutex 15351696a8beSPeter Zijlstra * 15361696a8beSPeter Zijlstra * @lock: the rt_mutex to be locked 15371696a8beSPeter Zijlstra * 15386ce47fd9SThomas Gleixner * This function can only be called in thread context. It's safe to 15396ce47fd9SThomas Gleixner * call it from atomic regions, but not from hard interrupt or soft 15406ce47fd9SThomas Gleixner * interrupt context. 15416ce47fd9SThomas Gleixner * 15421696a8beSPeter Zijlstra * Returns 1 on success and 0 on contention 15431696a8beSPeter Zijlstra */ 15441696a8beSPeter Zijlstra int __sched rt_mutex_trylock(struct rt_mutex *lock) 15451696a8beSPeter Zijlstra { 1546a461d587SSebastian Andrzej Siewior if (WARN_ON_ONCE(in_irq() || in_nmi() || in_serving_softirq())) 15476ce47fd9SThomas Gleixner return 0; 15486ce47fd9SThomas Gleixner 15491696a8beSPeter Zijlstra return rt_mutex_fasttrylock(lock, rt_mutex_slowtrylock); 15501696a8beSPeter Zijlstra } 15511696a8beSPeter Zijlstra EXPORT_SYMBOL_GPL(rt_mutex_trylock); 15521696a8beSPeter Zijlstra 15531696a8beSPeter Zijlstra /** 15541696a8beSPeter Zijlstra * rt_mutex_unlock - unlock a rt_mutex 15551696a8beSPeter Zijlstra * 15561696a8beSPeter Zijlstra * @lock: the rt_mutex to be unlocked 15571696a8beSPeter Zijlstra */ 15581696a8beSPeter Zijlstra void __sched rt_mutex_unlock(struct rt_mutex *lock) 15591696a8beSPeter Zijlstra { 15601696a8beSPeter Zijlstra rt_mutex_fastunlock(lock, rt_mutex_slowunlock); 15611696a8beSPeter Zijlstra } 15621696a8beSPeter Zijlstra EXPORT_SYMBOL_GPL(rt_mutex_unlock); 15631696a8beSPeter Zijlstra 15641696a8beSPeter Zijlstra /** 1565802ab58dSSebastian Andrzej Siewior * rt_mutex_futex_unlock - Futex variant of rt_mutex_unlock 1566802ab58dSSebastian Andrzej Siewior * @lock: the rt_mutex to be unlocked 1567802ab58dSSebastian Andrzej Siewior * 1568802ab58dSSebastian Andrzej Siewior * Returns: true/false indicating whether priority adjustment is 1569802ab58dSSebastian Andrzej Siewior * required or not. 1570802ab58dSSebastian Andrzej Siewior */ 1571802ab58dSSebastian Andrzej Siewior bool __sched rt_mutex_futex_unlock(struct rt_mutex *lock, 1572802ab58dSSebastian Andrzej Siewior struct wake_q_head *wqh) 1573802ab58dSSebastian Andrzej Siewior { 1574700318d1SDavidlohr Bueso if (likely(rt_mutex_cmpxchg_release(lock, current, NULL))) { 1575802ab58dSSebastian Andrzej Siewior rt_mutex_deadlock_account_unlock(current); 1576802ab58dSSebastian Andrzej Siewior return false; 1577802ab58dSSebastian Andrzej Siewior } 1578802ab58dSSebastian Andrzej Siewior return rt_mutex_slowunlock(lock, wqh); 1579802ab58dSSebastian Andrzej Siewior } 1580802ab58dSSebastian Andrzej Siewior 1581802ab58dSSebastian Andrzej Siewior /** 15821696a8beSPeter Zijlstra * rt_mutex_destroy - mark a mutex unusable 15831696a8beSPeter Zijlstra * @lock: the mutex to be destroyed 15841696a8beSPeter Zijlstra * 15851696a8beSPeter Zijlstra * This function marks the mutex uninitialized, and any subsequent 15861696a8beSPeter Zijlstra * use of the mutex is forbidden. The mutex must not be locked when 15871696a8beSPeter Zijlstra * this function is called. 15881696a8beSPeter Zijlstra */ 15891696a8beSPeter Zijlstra void rt_mutex_destroy(struct rt_mutex *lock) 15901696a8beSPeter Zijlstra { 15911696a8beSPeter Zijlstra WARN_ON(rt_mutex_is_locked(lock)); 15921696a8beSPeter Zijlstra #ifdef CONFIG_DEBUG_RT_MUTEXES 15931696a8beSPeter Zijlstra lock->magic = NULL; 15941696a8beSPeter Zijlstra #endif 15951696a8beSPeter Zijlstra } 15961696a8beSPeter Zijlstra 15971696a8beSPeter Zijlstra EXPORT_SYMBOL_GPL(rt_mutex_destroy); 15981696a8beSPeter Zijlstra 15991696a8beSPeter Zijlstra /** 16001696a8beSPeter Zijlstra * __rt_mutex_init - initialize the rt lock 16011696a8beSPeter Zijlstra * 16021696a8beSPeter Zijlstra * @lock: the rt lock to be initialized 16031696a8beSPeter Zijlstra * 16041696a8beSPeter Zijlstra * Initialize the rt lock to unlocked state. 16051696a8beSPeter Zijlstra * 16061696a8beSPeter Zijlstra * Initializing of a locked rt lock is not allowed 16071696a8beSPeter Zijlstra */ 16081696a8beSPeter Zijlstra void __rt_mutex_init(struct rt_mutex *lock, const char *name) 16091696a8beSPeter Zijlstra { 16101696a8beSPeter Zijlstra lock->owner = NULL; 16111696a8beSPeter Zijlstra raw_spin_lock_init(&lock->wait_lock); 1612fb00aca4SPeter Zijlstra lock->waiters = RB_ROOT; 1613fb00aca4SPeter Zijlstra lock->waiters_leftmost = NULL; 16141696a8beSPeter Zijlstra 16151696a8beSPeter Zijlstra debug_rt_mutex_init(lock, name); 16161696a8beSPeter Zijlstra } 16171696a8beSPeter Zijlstra EXPORT_SYMBOL_GPL(__rt_mutex_init); 16181696a8beSPeter Zijlstra 16191696a8beSPeter Zijlstra /** 16201696a8beSPeter Zijlstra * rt_mutex_init_proxy_locked - initialize and lock a rt_mutex on behalf of a 16211696a8beSPeter Zijlstra * proxy owner 16221696a8beSPeter Zijlstra * 16231696a8beSPeter Zijlstra * @lock: the rt_mutex to be locked 16241696a8beSPeter Zijlstra * @proxy_owner:the task to set as owner 16251696a8beSPeter Zijlstra * 16261696a8beSPeter Zijlstra * No locking. Caller has to do serializing itself 162784d82ec5SThomas Gleixner * 162884d82ec5SThomas Gleixner * Special API call for PI-futex support. This initializes the rtmutex and 162984d82ec5SThomas Gleixner * assigns it to @proxy_owner. Concurrent operations on the rtmutex are not 163084d82ec5SThomas Gleixner * possible at this point because the pi_state which contains the rtmutex 163184d82ec5SThomas Gleixner * is not yet visible to other tasks. 16321696a8beSPeter Zijlstra */ 16331696a8beSPeter Zijlstra void rt_mutex_init_proxy_locked(struct rt_mutex *lock, 16341696a8beSPeter Zijlstra struct task_struct *proxy_owner) 16351696a8beSPeter Zijlstra { 16361696a8beSPeter Zijlstra __rt_mutex_init(lock, NULL); 16371696a8beSPeter Zijlstra debug_rt_mutex_proxy_lock(lock, proxy_owner); 16381696a8beSPeter Zijlstra rt_mutex_set_owner(lock, proxy_owner); 16391696a8beSPeter Zijlstra rt_mutex_deadlock_account_lock(lock, proxy_owner); 16401696a8beSPeter Zijlstra } 16411696a8beSPeter Zijlstra 16421696a8beSPeter Zijlstra /** 16431696a8beSPeter Zijlstra * rt_mutex_proxy_unlock - release a lock on behalf of owner 16441696a8beSPeter Zijlstra * 16451696a8beSPeter Zijlstra * @lock: the rt_mutex to be locked 16461696a8beSPeter Zijlstra * 16471696a8beSPeter Zijlstra * No locking. Caller has to do serializing itself 164884d82ec5SThomas Gleixner * 164984d82ec5SThomas Gleixner * Special API call for PI-futex support. This merrily cleans up the rtmutex 165084d82ec5SThomas Gleixner * (debugging) state. Concurrent operations on this rt_mutex are not 165184d82ec5SThomas Gleixner * possible because it belongs to the pi_state which is about to be freed 165284d82ec5SThomas Gleixner * and it is not longer visible to other tasks. 16531696a8beSPeter Zijlstra */ 16541696a8beSPeter Zijlstra void rt_mutex_proxy_unlock(struct rt_mutex *lock, 16551696a8beSPeter Zijlstra struct task_struct *proxy_owner) 16561696a8beSPeter Zijlstra { 16571696a8beSPeter Zijlstra debug_rt_mutex_proxy_unlock(lock); 16581696a8beSPeter Zijlstra rt_mutex_set_owner(lock, NULL); 16591696a8beSPeter Zijlstra rt_mutex_deadlock_account_unlock(proxy_owner); 16601696a8beSPeter Zijlstra } 16611696a8beSPeter Zijlstra 16621696a8beSPeter Zijlstra /** 16631696a8beSPeter Zijlstra * rt_mutex_start_proxy_lock() - Start lock acquisition for another task 16641696a8beSPeter Zijlstra * @lock: the rt_mutex to take 16651696a8beSPeter Zijlstra * @waiter: the pre-initialized rt_mutex_waiter 16661696a8beSPeter Zijlstra * @task: the task to prepare 16671696a8beSPeter Zijlstra * 16681696a8beSPeter Zijlstra * Returns: 16691696a8beSPeter Zijlstra * 0 - task blocked on lock 16701696a8beSPeter Zijlstra * 1 - acquired the lock for task, caller should wake it up 16711696a8beSPeter Zijlstra * <0 - error 16721696a8beSPeter Zijlstra * 16731696a8beSPeter Zijlstra * Special API call for FUTEX_REQUEUE_PI support. 16741696a8beSPeter Zijlstra */ 16751696a8beSPeter Zijlstra int rt_mutex_start_proxy_lock(struct rt_mutex *lock, 16761696a8beSPeter Zijlstra struct rt_mutex_waiter *waiter, 1677c051b21fSThomas Gleixner struct task_struct *task) 16781696a8beSPeter Zijlstra { 16791696a8beSPeter Zijlstra int ret; 16801696a8beSPeter Zijlstra 1681b4abf910SThomas Gleixner raw_spin_lock_irq(&lock->wait_lock); 16821696a8beSPeter Zijlstra 16831696a8beSPeter Zijlstra if (try_to_take_rt_mutex(lock, task, NULL)) { 1684b4abf910SThomas Gleixner raw_spin_unlock_irq(&lock->wait_lock); 16851696a8beSPeter Zijlstra return 1; 16861696a8beSPeter Zijlstra } 16871696a8beSPeter Zijlstra 16883d5c9340SThomas Gleixner /* We enforce deadlock detection for futexes */ 16898930ed80SThomas Gleixner ret = task_blocks_on_rt_mutex(lock, waiter, task, 16908930ed80SThomas Gleixner RT_MUTEX_FULL_CHAINWALK); 16911696a8beSPeter Zijlstra 16921696a8beSPeter Zijlstra if (ret && !rt_mutex_owner(lock)) { 16931696a8beSPeter Zijlstra /* 16941696a8beSPeter Zijlstra * Reset the return value. We might have 16951696a8beSPeter Zijlstra * returned with -EDEADLK and the owner 16961696a8beSPeter Zijlstra * released the lock while we were walking the 16971696a8beSPeter Zijlstra * pi chain. Let the waiter sort it out. 16981696a8beSPeter Zijlstra */ 16991696a8beSPeter Zijlstra ret = 0; 17001696a8beSPeter Zijlstra } 17011696a8beSPeter Zijlstra 17021696a8beSPeter Zijlstra if (unlikely(ret)) 17031696a8beSPeter Zijlstra remove_waiter(lock, waiter); 17041696a8beSPeter Zijlstra 1705b4abf910SThomas Gleixner raw_spin_unlock_irq(&lock->wait_lock); 17061696a8beSPeter Zijlstra 17071696a8beSPeter Zijlstra debug_rt_mutex_print_deadlock(waiter); 17081696a8beSPeter Zijlstra 17091696a8beSPeter Zijlstra return ret; 17101696a8beSPeter Zijlstra } 17111696a8beSPeter Zijlstra 17121696a8beSPeter Zijlstra /** 17131696a8beSPeter Zijlstra * rt_mutex_next_owner - return the next owner of the lock 17141696a8beSPeter Zijlstra * 17151696a8beSPeter Zijlstra * @lock: the rt lock query 17161696a8beSPeter Zijlstra * 17171696a8beSPeter Zijlstra * Returns the next owner of the lock or NULL 17181696a8beSPeter Zijlstra * 17191696a8beSPeter Zijlstra * Caller has to serialize against other accessors to the lock 17201696a8beSPeter Zijlstra * itself. 17211696a8beSPeter Zijlstra * 17221696a8beSPeter Zijlstra * Special API call for PI-futex support 17231696a8beSPeter Zijlstra */ 17241696a8beSPeter Zijlstra struct task_struct *rt_mutex_next_owner(struct rt_mutex *lock) 17251696a8beSPeter Zijlstra { 17261696a8beSPeter Zijlstra if (!rt_mutex_has_waiters(lock)) 17271696a8beSPeter Zijlstra return NULL; 17281696a8beSPeter Zijlstra 17291696a8beSPeter Zijlstra return rt_mutex_top_waiter(lock)->task; 17301696a8beSPeter Zijlstra } 17311696a8beSPeter Zijlstra 17321696a8beSPeter Zijlstra /** 17331696a8beSPeter Zijlstra * rt_mutex_finish_proxy_lock() - Complete lock acquisition 17341696a8beSPeter Zijlstra * @lock: the rt_mutex we were woken on 17351696a8beSPeter Zijlstra * @to: the timeout, null if none. hrtimer should already have 17361696a8beSPeter Zijlstra * been started. 17371696a8beSPeter Zijlstra * @waiter: the pre-initialized rt_mutex_waiter 17381696a8beSPeter Zijlstra * 17391696a8beSPeter Zijlstra * Complete the lock acquisition started our behalf by another thread. 17401696a8beSPeter Zijlstra * 17411696a8beSPeter Zijlstra * Returns: 17421696a8beSPeter Zijlstra * 0 - success 1743c051b21fSThomas Gleixner * <0 - error, one of -EINTR, -ETIMEDOUT 17441696a8beSPeter Zijlstra * 17451696a8beSPeter Zijlstra * Special API call for PI-futex requeue support 17461696a8beSPeter Zijlstra */ 17471696a8beSPeter Zijlstra int rt_mutex_finish_proxy_lock(struct rt_mutex *lock, 17481696a8beSPeter Zijlstra struct hrtimer_sleeper *to, 1749c051b21fSThomas Gleixner struct rt_mutex_waiter *waiter) 17501696a8beSPeter Zijlstra { 17511696a8beSPeter Zijlstra int ret; 17521696a8beSPeter Zijlstra 1753b4abf910SThomas Gleixner raw_spin_lock_irq(&lock->wait_lock); 17541696a8beSPeter Zijlstra 17551696a8beSPeter Zijlstra set_current_state(TASK_INTERRUPTIBLE); 17561696a8beSPeter Zijlstra 1757afffc6c1SDavidlohr Bueso /* sleep on the mutex */ 17581696a8beSPeter Zijlstra ret = __rt_mutex_slowlock(lock, TASK_INTERRUPTIBLE, to, waiter); 17591696a8beSPeter Zijlstra 17601696a8beSPeter Zijlstra if (unlikely(ret)) 17611696a8beSPeter Zijlstra remove_waiter(lock, waiter); 17621696a8beSPeter Zijlstra 17631696a8beSPeter Zijlstra /* 17641696a8beSPeter Zijlstra * try_to_take_rt_mutex() sets the waiter bit unconditionally. We might 17651696a8beSPeter Zijlstra * have to fix that up. 17661696a8beSPeter Zijlstra */ 17671696a8beSPeter Zijlstra fixup_rt_mutex_waiters(lock); 17681696a8beSPeter Zijlstra 1769b4abf910SThomas Gleixner raw_spin_unlock_irq(&lock->wait_lock); 17701696a8beSPeter Zijlstra 17711696a8beSPeter Zijlstra return ret; 17721696a8beSPeter Zijlstra } 1773