kernel/locking/rtmutex.c

   1 /*
   2  * RT-Mutexes: simple blocking mutual exclusion locks with PI support
   3  *
   4  * started by Ingo Molnar and Thomas Gleixner.
   5  *
   6  *  Copyright (C) 2004-2006 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
   7  *  Copyright (C) 2005-2006 Timesys Corp., Thomas Gleixner <tglx@timesys.com>
   8  *  Copyright (C) 2005 Kihon Technologies Inc., Steven Rostedt
   9  *  Copyright (C) 2006 Esben Nielsen
  10  *
  11  *  See Documentation/locking/rt-mutex-design.txt for details.
  12  */
  13 #include <linux/spinlock.h>
  14 #include <linux/export.h>
  15 #include <linux/sched.h>
  16 #include <linux/sched/rt.h>
  17 #include <linux/sched/deadline.h>
  18 #include <linux/timer.h>
  19
  20 #include "rtmutex_common.h"
  21
  22 /*
  23  * lock->owner state tracking:
  24  *
  25  * lock->owner holds the task_struct pointer of the owner. Bit 0
  26  * is used to keep track of the "lock has waiters" state.
  27  *
  28  * owner        bit0
  29  * NULL         0       lock is free (fast acquire possible)
  30  * NULL         1       lock is free and has waiters and the top waiter
  31  *                              is going to take the lock*
  32  * taskpointer  0       lock is held (fast release possible)
  33  * taskpointer  1       lock is held and has waiters**
  34  *
  35  * The fast atomic compare exchange based acquire and release is only
  36  * possible when bit 0 of lock->owner is 0.
  37  *
  38  * (*) It also can be a transitional state when grabbing the lock
  39  * with ->wait_lock is held. To prevent any fast path cmpxchg to the lock,
  40  * we need to set the bit0 before looking at the lock, and the owner may be
  41  * NULL in this small time, hence this can be a transitional state.
  42  *
  43  * (**) There is a small time when bit 0 is set but there are no
  44  * waiters. This can happen when grabbing the lock in the slow path.
  45  * To prevent a cmpxchg of the owner releasing the lock, we need to
  46  * set this bit before looking at the lock.
  47  */
  48
  49 static void
  50 rt_mutex_set_owner(struct rt_mutex *lock, struct task_struct *owner)
  51 {
  52         unsigned long val = (unsigned long)owner;
  53
  54         if (rt_mutex_has_waiters(lock))
  55                 val |= RT_MUTEX_HAS_WAITERS;
  56
  57         lock->owner = (struct task_struct *)val;
  58 }
  59
  60 static inline void clear_rt_mutex_waiters(struct rt_mutex *lock)
  61 {
  62         lock->owner = (struct task_struct *)
  63                         ((unsigned long)lock->owner & ~RT_MUTEX_HAS_WAITERS);
  64 }
  65
  66 static void fixup_rt_mutex_waiters(struct rt_mutex *lock)
  67 {
  68         if (!rt_mutex_has_waiters(lock))
  69                 clear_rt_mutex_waiters(lock);
  70 }
  71
  72 /*
  73  * We can speed up the acquire/release, if the architecture
  74  * supports cmpxchg and if there's no debugging state to be set up
  75  */
  76 #if defined(__HAVE_ARCH_CMPXCHG) && !defined(CONFIG_DEBUG_RT_MUTEXES)
  77 # define rt_mutex_cmpxchg(l,c,n)        (cmpxchg(&l->owner, c, n) == c)
  78 static inline void mark_rt_mutex_waiters(struct rt_mutex *lock)
  79 {
  80         unsigned long owner, *p = (unsigned long *) &lock->owner;
  81
  82         do {
  83                 owner = *p;
  84         } while (cmpxchg(p, owner, owner | RT_MUTEX_HAS_WAITERS) != owner);
  85 }
  86
  87 /*
  88  * Safe fastpath aware unlock:
  89  * 1) Clear the waiters bit
  90  * 2) Drop lock->wait_lock
  91  * 3) Try to unlock the lock with cmpxchg
  92  */
  93 static inline bool unlock_rt_mutex_safe(struct rt_mutex *lock)
  94         __releases(lock->wait_lock)
  95 {
  96         struct task_struct *owner = rt_mutex_owner(lock);
  97
  98         clear_rt_mutex_waiters(lock);
  99         raw_spin_unlock(&lock->wait_lock);
 100         /*
 101          * If a new waiter comes in between the unlock and the cmpxchg
 102          * we have two situations:
 103          *
 104          * unlock(wait_lock);
 105          *                                      lock(wait_lock);
 106          * cmpxchg(p, owner, 0) == owner
 107          *                                      mark_rt_mutex_waiters(lock);
 108          *                                      acquire(lock);
 109          * or:
 110          *
 111          * unlock(wait_lock);
 112          *                                      lock(wait_lock);
 113          *                                      mark_rt_mutex_waiters(lock);
 114          *
 115          * cmpxchg(p, owner, 0) != owner
 116          *                                      enqueue_waiter();
 117          *                                      unlock(wait_lock);
 118          * lock(wait_lock);
 119          * wake waiter();
 120          * unlock(wait_lock);
 121          *                                      lock(wait_lock);
 122          *                                      acquire(lock);
 123          */
 124         return rt_mutex_cmpxchg(lock, owner, NULL);
 125 }
 126
 127 #else
 128 # define rt_mutex_cmpxchg(l,c,n)        (0)
 129 static inline void mark_rt_mutex_waiters(struct rt_mutex *lock)
 130 {
 131         lock->owner = (struct task_struct *)
 132                         ((unsigned long)lock->owner | RT_MUTEX_HAS_WAITERS);
 133 }
 134
 135 /*
 136  * Simple slow path only version: lock->owner is protected by lock->wait_lock.
 137  */
 138 static inline bool unlock_rt_mutex_safe(struct rt_mutex *lock)
 139         __releases(lock->wait_lock)
 140 {
 141         lock->owner = NULL;
 142         raw_spin_unlock(&lock->wait_lock);
 143         return true;
 144 }
 145 #endif
 146
 147 static inline int
 148 rt_mutex_waiter_less(struct rt_mutex_waiter *left,
 149                      struct rt_mutex_waiter *right)
 150 {
 151         if (left->prio < right->prio)
 152                 return 1;
 153
 154         /*
 155          * If both waiters have dl_prio(), we check the deadlines of the
 156          * associated tasks.
 157          * If left waiter has a dl_prio(), and we didn't return 1 above,
 158          * then right waiter has a dl_prio() too.
 159          */
 160         if (dl_prio(left->prio))
 161                 return (left->task->dl.deadline < right->task->dl.deadline);
 162
 163         return 0;
 164 }
 165
 166 static void
 167 rt_mutex_enqueue(struct rt_mutex *lock, struct rt_mutex_waiter *waiter)
 168 {
 169         struct rb_node **link = &lock->waiters.rb_node;
 170         struct rb_node *parent = NULL;
 171         struct rt_mutex_waiter *entry;
 172         int leftmost = 1;
 173
 174         while (*link) {
 175                 parent = *link;
 176                 entry = rb_entry(parent, struct rt_mutex_waiter, tree_entry);
 177                 if (rt_mutex_waiter_less(waiter, entry)) {
 178                         link = &parent->rb_left;
 179                 } else {
 180                         link = &parent->rb_right;
 181                         leftmost = 0;
 182                 }
 183         }
 184
 185         if (leftmost)
 186                 lock->waiters_leftmost = &waiter->tree_entry;
 187
 188         rb_link_node(&waiter->tree_entry, parent, link);
 189         rb_insert_color(&waiter->tree_entry, &lock->waiters);
 190 }
 191
 192 static void
 193 rt_mutex_dequeue(struct rt_mutex *lock, struct rt_mutex_waiter *waiter)
 194 {
 195         if (RB_EMPTY_NODE(&waiter->tree_entry))
 196                 return;
 197
 198         if (lock->waiters_leftmost == &waiter->tree_entry)
 199                 lock->waiters_leftmost = rb_next(&waiter->tree_entry);
 200
 201         rb_erase(&waiter->tree_entry, &lock->waiters);
 202         RB_CLEAR_NODE(&waiter->tree_entry);
 203 }
 204
 205 static void
 206 rt_mutex_enqueue_pi(struct task_struct *task, struct rt_mutex_waiter *waiter)
 207 {
 208         struct rb_node **link = &task->pi_waiters.rb_node;
 209         struct rb_node *parent = NULL;
 210         struct rt_mutex_waiter *entry;
 211         int leftmost = 1;
 212
 213         while (*link) {
 214                 parent = *link;
 215                 entry = rb_entry(parent, struct rt_mutex_waiter, pi_tree_entry);
 216                 if (rt_mutex_waiter_less(waiter, entry)) {
 217                         link = &parent->rb_left;
 218                 } else {
 219                         link = &parent->rb_right;
 220                         leftmost = 0;
 221                 }
 222         }
 223
 224         if (leftmost)
 225                 task->pi_waiters_leftmost = &waiter->pi_tree_entry;
 226
 227         rb_link_node(&waiter->pi_tree_entry, parent, link);
 228         rb_insert_color(&waiter->pi_tree_entry, &task->pi_waiters);
 229 }
 230
 231 static void
 232 rt_mutex_dequeue_pi(struct task_struct *task, struct rt_mutex_waiter *waiter)
 233 {
 234         if (RB_EMPTY_NODE(&waiter->pi_tree_entry))
 235                 return;
 236
 237         if (task->pi_waiters_leftmost == &waiter->pi_tree_entry)
 238                 task->pi_waiters_leftmost = rb_next(&waiter->pi_tree_entry);
 239
 240         rb_erase(&waiter->pi_tree_entry, &task->pi_waiters);
 241         RB_CLEAR_NODE(&waiter->pi_tree_entry);
 242 }
 243
 244 /*
 245  * Calculate task priority from the waiter tree priority
 246  *
 247  * Return task->normal_prio when the waiter tree is empty or when
 248  * the waiter is not allowed to do priority boosting
 249  */
 250 int rt_mutex_getprio(struct task_struct *task)
 251 {
 252         if (likely(!task_has_pi_waiters(task)))
 253                 return task->normal_prio;
 254
 255         return min(task_top_pi_waiter(task)->prio,
 256                    task->normal_prio);
 257 }
 258
 259 struct task_struct *rt_mutex_get_top_task(struct task_struct *task)
 260 {
 261         if (likely(!task_has_pi_waiters(task)))
 262                 return NULL;
 263
 264         return task_top_pi_waiter(task)->task;
 265 }
 266
 267 /*
 268  * Called by sched_setscheduler() to get the priority which will be
 269  * effective after the change.
 270  */
 271 int rt_mutex_get_effective_prio(struct task_struct *task, int newprio)
 272 {
 273         if (!task_has_pi_waiters(task))
 274                 return newprio;
 275
 276         if (task_top_pi_waiter(task)->task->prio <= newprio)
 277                 return task_top_pi_waiter(task)->task->prio;
 278         return newprio;
 279 }
 280
 281 /*
 282  * Adjust the priority of a task, after its pi_waiters got modified.
 283  *
 284  * This can be both boosting and unboosting. task->pi_lock must be held.
 285  */
 286 static void __rt_mutex_adjust_prio(struct task_struct *task)
 287 {
 288         int prio = rt_mutex_getprio(task);
 289
 290         if (task->prio != prio || dl_prio(prio))
 291                 rt_mutex_setprio(task, prio);
 292 }
 293
 294 /*
 295  * Adjust task priority (undo boosting). Called from the exit path of
 296  * rt_mutex_slowunlock() and rt_mutex_slowlock().
 297  *
 298  * (Note: We do this outside of the protection of lock->wait_lock to
 299  * allow the lock to be taken while or before we readjust the priority
 300  * of task. We do not use the spin_xx_mutex() variants here as we are
 301  * outside of the debug path.)
 302  */
 303 static void rt_mutex_adjust_prio(struct task_struct *task)
 304 {
 305         unsigned long flags;
 306
 307         raw_spin_lock_irqsave(&task->pi_lock, flags);
 308         __rt_mutex_adjust_prio(task);
 309         raw_spin_unlock_irqrestore(&task->pi_lock, flags);
 310 }
 311
 312 /*
 313  * Deadlock detection is conditional:
 314  *
 315  * If CONFIG_DEBUG_RT_MUTEXES=n, deadlock detection is only conducted
 316  * if the detect argument is == RT_MUTEX_FULL_CHAINWALK.
 317  *
 318  * If CONFIG_DEBUG_RT_MUTEXES=y, deadlock detection is always
 319  * conducted independent of the detect argument.
 320  *
 321  * If the waiter argument is NULL this indicates the deboost path and
 322  * deadlock detection is disabled independent of the detect argument
 323  * and the config settings.
 324  */
 325 static bool rt_mutex_cond_detect_deadlock(struct rt_mutex_waiter *waiter,
 326                                           enum rtmutex_chainwalk chwalk)
 327 {
 328         /*
 329          * This is just a wrapper function for the following call,
 330          * because debug_rt_mutex_detect_deadlock() smells like a magic
 331          * debug feature and I wanted to keep the cond function in the
 332          * main source file along with the comments instead of having
 333          * two of the same in the headers.
 334          */
 335         return debug_rt_mutex_detect_deadlock(waiter, chwalk);
 336 }
 337
 338 /*
 339  * Max number of times we'll walk the boosting chain:
 340  */
 341 int max_lock_depth = 1024;
 342
 343 static inline struct rt_mutex *task_blocked_on_lock(struct task_struct *p)
 344 {
 345         return p->pi_blocked_on ? p->pi_blocked_on->lock : NULL;
 346 }
 347
 348 /*
 349  * Adjust the priority chain. Also used for deadlock detection.
 350  * Decreases task's usage by one - may thus free the task.
 351  *
 352  * @task:       the task owning the mutex (owner) for which a chain walk is
 353  *              probably needed
 354  * @chwalk:     do we have to carry out deadlock detection?
 355  * @orig_lock:  the mutex (can be NULL if we are walking the chain to recheck
 356  *              things for a task that has just got its priority adjusted, and
 357  *              is waiting on a mutex)
 358  * @next_lock:  the mutex on which the owner of @orig_lock was blocked before
 359  *              we dropped its pi_lock. Is never dereferenced, only used for
 360  *              comparison to detect lock chain changes.
 361  * @orig_waiter: rt_mutex_waiter struct for the task that has just donated
 362  *              its priority to the mutex owner (can be NULL in the case
 363  *              depicted above or if the top waiter is gone away and we are
 364  *              actually deboosting the owner)
 365  * @top_task:   the current top waiter
 366  *
 367  * Returns 0 or -EDEADLK.
 368  *
 369  * Chain walk basics and protection scope
 370  *
 371  * [R] refcount on task
 372  * [P] task->pi_lock held
 373  * [L] rtmutex->wait_lock held
 374  *
 375  * Step Description                             Protected by
 376  *      function arguments:
 377  *      @task                                   [R]
 378  *      @orig_lock if != NULL                   @top_task is blocked on it
 379  *      @next_lock                              Unprotected. Cannot be
 380  *                                              dereferenced. Only used for
 381  *                                              comparison.
 382  *      @orig_waiter if != NULL                 @top_task is blocked on it
 383  *      @top_task                               current, or in case of proxy
 384  *                                              locking protected by calling
 385  *                                              code
 386  *      again:
 387  *        loop_sanity_check();
 388  *      retry:
 389  * [1]    lock(task->pi_lock);                  [R] acquire [P]
 390  * [2]    waiter = task->pi_blocked_on;         [P]
 391  * [3]    check_exit_conditions_1();            [P]
 392  * [4]    lock = waiter->lock;                  [P]
 393  * [5]    if (!try_lock(lock->wait_lock)) {     [P] try to acquire [L]
 394  *          unlock(task->pi_lock);              release [P]
 395  *          goto retry;
 396  *        }
 397  * [6]    check_exit_conditions_2();            [P] + [L]
 398  * [7]    requeue_lock_waiter(lock, waiter);    [P] + [L]
 399  * [8]    unlock(task->pi_lock);                release [P]
 400  *        put_task_struct(task);                release [R]
 401  * [9]    check_exit_conditions_3();            [L]
 402  * [10]   task = owner(lock);                   [L]
 403  *        get_task_struct(task);                [L] acquire [R]
 404  *        lock(task->pi_lock);                  [L] acquire [P]
 405  * [11]   requeue_pi_waiter(tsk, waiters(lock));[P] + [L]
 406  * [12]   check_exit_conditions_4();            [P] + [L]
 407  * [13]   unlock(task->pi_lock);                release [P]
 408  *        unlock(lock->wait_lock);              release [L]
 409  *        goto again;
 410  */
 411 static int rt_mutex_adjust_prio_chain(struct task_struct *task,
 412                                       enum rtmutex_chainwalk chwalk,
 413                                       struct rt_mutex *orig_lock,
 414                                       struct rt_mutex *next_lock,
 415                                       struct rt_mutex_waiter *orig_waiter,
 416                                       struct task_struct *top_task)
 417 {
 418         struct rt_mutex_waiter *waiter, *top_waiter = orig_waiter;
 419         struct rt_mutex_waiter *prerequeue_top_waiter;
 420         int ret = 0, depth = 0;
 421         struct rt_mutex *lock;
 422         bool detect_deadlock;
 423         unsigned long flags;
 424         bool requeue = true;
 425
 426         detect_deadlock = rt_mutex_cond_detect_deadlock(orig_waiter, chwalk);
 427
 428         /*
 429          * The (de)boosting is a step by step approach with a lot of
 430          * pitfalls. We want this to be preemptible and we want hold a
 431          * maximum of two locks per step. So we have to check
 432          * carefully whether things change under us.
 433          */
 434  again:
 435         /*
 436          * We limit the lock chain length for each invocation.
 437          */
 438         if (++depth > max_lock_depth) {
 439                 static int prev_max;
 440
 441                 /*
 442                  * Print this only once. If the admin changes the limit,
 443                  * print a new message when reaching the limit again.
 444                  */
 445                 if (prev_max != max_lock_depth) {
 446                         prev_max = max_lock_depth;
 447                         printk(KERN_WARNING "Maximum lock depth %d reached "
 448                                "task: %s (%d)\n", max_lock_depth,
 449                                top_task->comm, task_pid_nr(top_task));
 450                 }
 451                 put_task_struct(task);
 452
 453                 return -EDEADLK;
 454         }
 455
 456         /*
 457          * We are fully preemptible here and only hold the refcount on
 458          * @task. So everything can have changed under us since the
 459          * caller or our own code below (goto retry/again) dropped all
 460          * locks.
 461          */
 462  retry:
 463         /*
 464          * [1] Task cannot go away as we did a get_task() before !
 465          */
 466         raw_spin_lock_irqsave(&task->pi_lock, flags);
 467
 468         /*
 469          * [2] Get the waiter on which @task is blocked on.
 470          */
 471         waiter = task->pi_blocked_on;
 472
 473         /*
 474          * [3] check_exit_conditions_1() protected by task->pi_lock.
 475          */
 476
 477         /*
 478          * Check whether the end of the boosting chain has been
 479          * reached or the state of the chain has changed while we
 480          * dropped the locks.
 481          */
 482         if (!waiter)
 483                 goto out_unlock_pi;
 484
 485         /*
 486          * Check the orig_waiter state. After we dropped the locks,
 487          * the previous owner of the lock might have released the lock.
 488          */
 489         if (orig_waiter && !rt_mutex_owner(orig_lock))
 490                 goto out_unlock_pi;
 491
 492         /*
 493          * We dropped all locks after taking a refcount on @task, so
 494          * the task might have moved on in the lock chain or even left
 495          * the chain completely and blocks now on an unrelated lock or
 496          * on @orig_lock.
 497          *
 498          * We stored the lock on which @task was blocked in @next_lock,
 499          * so we can detect the chain change.
 500          */
 501         if (next_lock != waiter->lock)
 502                 goto out_unlock_pi;
 503
 504         /*
 505          * Drop out, when the task has no waiters. Note,
 506          * top_waiter can be NULL, when we are in the deboosting
 507          * mode!
 508          */
 509         if (top_waiter) {
 510                 if (!task_has_pi_waiters(task))
 511                         goto out_unlock_pi;
 512                 /*
 513                  * If deadlock detection is off, we stop here if we
 514                  * are not the top pi waiter of the task. If deadlock
 515                  * detection is enabled we continue, but stop the
 516                  * requeueing in the chain walk.
 517                  */
 518                 if (top_waiter != task_top_pi_waiter(task)) {
 519                         if (!detect_deadlock)
 520                                 goto out_unlock_pi;
 521                         else
 522                                 requeue = false;
 523                 }
 524         }
 525
 526         /*
 527          * If the waiter priority is the same as the task priority
 528          * then there is no further priority adjustment necessary.  If
 529          * deadlock detection is off, we stop the chain walk. If its
 530          * enabled we continue, but stop the requeueing in the chain
 531          * walk.
 532          */
 533         if (waiter->prio == task->prio) {
 534                 if (!detect_deadlock)
 535                         goto out_unlock_pi;
 536                 else
 537                         requeue = false;
 538         }
 539
 540         /*
 541          * [4] Get the next lock
 542          */
 543         lock = waiter->lock;
 544         /*
 545          * [5] We need to trylock here as we are holding task->pi_lock,
 546          * which is the reverse lock order versus the other rtmutex
 547          * operations.
 548          */
 549         if (!raw_spin_trylock(&lock->wait_lock)) {
 550                 raw_spin_unlock_irqrestore(&task->pi_lock, flags);
 551                 cpu_relax();
 552                 goto retry;
 553         }
 554
 555         /*
 556          * [6] check_exit_conditions_2() protected by task->pi_lock and
 557          * lock->wait_lock.
 558          *
 559          * Deadlock detection. If the lock is the same as the original
 560          * lock which caused us to walk the lock chain or if the
 561          * current lock is owned by the task which initiated the chain
 562          * walk, we detected a deadlock.
 563          */
 564         if (lock == orig_lock || rt_mutex_owner(lock) == top_task) {
 565                 debug_rt_mutex_deadlock(chwalk, orig_waiter, lock);
 566                 raw_spin_unlock(&lock->wait_lock);
 567                 ret = -EDEADLK;
 568                 goto out_unlock_pi;
 569         }
 570
 571         /*
 572          * If we just follow the lock chain for deadlock detection, no
 573          * need to do all the requeue operations. To avoid a truckload
 574          * of conditionals around the various places below, just do the
 575          * minimum chain walk checks.
 576          */
 577         if (!requeue) {
 578                 /*
 579                  * No requeue[7] here. Just release @task [8]
 580                  */
 581                 raw_spin_unlock_irqrestore(&task->pi_lock, flags);
 582                 put_task_struct(task);
 583
 584                 /*
 585                  * [9] check_exit_conditions_3 protected by lock->wait_lock.
 586                  * If there is no owner of the lock, end of chain.
 587                  */
 588                 if (!rt_mutex_owner(lock)) {
 589                         raw_spin_unlock(&lock->wait_lock);
 590                         return 0;
 591                 }
 592
 593                 /* [10] Grab the next task, i.e. owner of @lock */
 594                 task = rt_mutex_owner(lock);
 595                 get_task_struct(task);
 596                 raw_spin_lock_irqsave(&task->pi_lock, flags);
 597
 598                 /*
 599                  * No requeue [11] here. We just do deadlock detection.
 600                  *
 601                  * [12] Store whether owner is blocked
 602                  * itself. Decision is made after dropping the locks
 603                  */
 604                 next_lock = task_blocked_on_lock(task);
 605                 /*
 606                  * Get the top waiter for the next iteration
 607                  */
 608                 top_waiter = rt_mutex_top_waiter(lock);
 609
 610                 /* [13] Drop locks */
 611                 raw_spin_unlock_irqrestore(&task->pi_lock, flags);
 612                 raw_spin_unlock(&lock->wait_lock);
 613
 614                 /* If owner is not blocked, end of chain. */
 615                 if (!next_lock)
 616                         goto out_put_task;
 617                 goto again;
 618         }
 619
 620         /*
 621          * Store the current top waiter before doing the requeue
 622          * operation on @lock. We need it for the boost/deboost
 623          * decision below.
 624          */
 625         prerequeue_top_waiter = rt_mutex_top_waiter(lock);
 626
 627         /* [7] Requeue the waiter in the lock waiter list. */
 628         rt_mutex_dequeue(lock, waiter);
 629         waiter->prio = task->prio;
 630         rt_mutex_enqueue(lock, waiter);
 631
 632         /* [8] Release the task */
 633         raw_spin_unlock_irqrestore(&task->pi_lock, flags);
 634         put_task_struct(task);
 635
 636         /*
 637          * [9] check_exit_conditions_3 protected by lock->wait_lock.
 638          *
 639          * We must abort the chain walk if there is no lock owner even
 640          * in the dead lock detection case, as we have nothing to
 641          * follow here. This is the end of the chain we are walking.
 642          */
 643         if (!rt_mutex_owner(lock)) {
 644                 /*
 645                  * If the requeue [7] above changed the top waiter,
 646                  * then we need to wake the new top waiter up to try
 647                  * to get the lock.
 648                  */
 649                 if (prerequeue_top_waiter != rt_mutex_top_waiter(lock))
 650                         wake_up_process(rt_mutex_top_waiter(lock)->task);
 651                 raw_spin_unlock(&lock->wait_lock);
 652                 return 0;
 653         }
 654
 655         /* [10] Grab the next task, i.e. the owner of @lock */
 656         task = rt_mutex_owner(lock);
 657         get_task_struct(task);
 658         raw_spin_lock_irqsave(&task->pi_lock, flags);
 659
 660         /* [11] requeue the pi waiters if necessary */
 661         if (waiter == rt_mutex_top_waiter(lock)) {
 662                 /*
 663                  * The waiter became the new top (highest priority)
 664                  * waiter on the lock. Replace the previous top waiter
 665                  * in the owner tasks pi waiters list with this waiter
 666                  * and adjust the priority of the owner.
 667                  */
 668                 rt_mutex_dequeue_pi(task, prerequeue_top_waiter);
 669                 rt_mutex_enqueue_pi(task, waiter);
 670                 __rt_mutex_adjust_prio(task);
 671
 672         } else if (prerequeue_top_waiter == waiter) {
 673                 /*
 674                  * The waiter was the top waiter on the lock, but is
 675                  * no longer the top prority waiter. Replace waiter in
 676                  * the owner tasks pi waiters list with the new top
 677                  * (highest priority) waiter and adjust the priority
 678                  * of the owner.
 679                  * The new top waiter is stored in @waiter so that
 680                  * @waiter == @top_waiter evaluates to true below and
 681                  * we continue to deboost the rest of the chain.
 682                  */
 683                 rt_mutex_dequeue_pi(task, waiter);
 684                 waiter = rt_mutex_top_waiter(lock);
 685                 rt_mutex_enqueue_pi(task, waiter);
 686                 __rt_mutex_adjust_prio(task);
 687         } else {
 688                 /*
 689                  * Nothing changed. No need to do any priority
 690                  * adjustment.
 691                  */
 692         }
 693
 694         /*
 695          * [12] check_exit_conditions_4() protected by task->pi_lock
 696          * and lock->wait_lock. The actual decisions are made after we
 697          * dropped the locks.
 698          *
 699          * Check whether the task which owns the current lock is pi
 700          * blocked itself. If yes we store a pointer to the lock for
 701          * the lock chain change detection above. After we dropped
 702          * task->pi_lock next_lock cannot be dereferenced anymore.
 703          */
 704         next_lock = task_blocked_on_lock(task);
 705         /*
 706          * Store the top waiter of @lock for the end of chain walk
 707          * decision below.
 708          */
 709         top_waiter = rt_mutex_top_waiter(lock);
 710
 711         /* [13] Drop the locks */
 712         raw_spin_unlock_irqrestore(&task->pi_lock, flags);
 713         raw_spin_unlock(&lock->wait_lock);
 714
 715         /*
 716          * Make the actual exit decisions [12], based on the stored
 717          * values.
 718          *
 719          * We reached the end of the lock chain. Stop right here. No
 720          * point to go back just to figure that out.
 721          */
 722         if (!next_lock)
 723                 goto out_put_task;
 724
 725         /*
 726          * If the current waiter is not the top waiter on the lock,
 727          * then we can stop the chain walk here if we are not in full
 728          * deadlock detection mode.
 729          */
 730         if (!detect_deadlock && waiter != top_waiter)
 731                 goto out_put_task;
 732
 733         goto again;
 734
 735  out_unlock_pi:
 736         raw_spin_unlock_irqrestore(&task->pi_lock, flags);
 737  out_put_task:
 738         put_task_struct(task);
 739
 740         return ret;
 741 }
 742
 743 /*
 744  * Try to take an rt-mutex
 745  *
 746  * Must be called with lock->wait_lock held.
 747  *
 748  * @lock:   The lock to be acquired.
 749  * @task:   The task which wants to acquire the lock
 750  * @waiter: The waiter that is queued to the lock's wait list if the
 751  *          callsite called task_blocked_on_lock(), otherwise NULL
 752  */
 753 static int try_to_take_rt_mutex(struct rt_mutex *lock, struct task_struct *task,
 754                                 struct rt_mutex_waiter *waiter)
 755 {
 756         unsigned long flags;
 757
 758         /*
 759          * Before testing whether we can acquire @lock, we set the
 760          * RT_MUTEX_HAS_WAITERS bit in @lock->owner. This forces all
 761          * other tasks which try to modify @lock into the slow path
 762          * and they serialize on @lock->wait_lock.
 763          *
 764          * The RT_MUTEX_HAS_WAITERS bit can have a transitional state
 765          * as explained at the top of this file if and only if:
 766          *
 767          * - There is a lock owner. The caller must fixup the
 768          *   transient state if it does a trylock or leaves the lock
 769          *   function due to a signal or timeout.
 770          *
 771          * - @task acquires the lock and there are no other
 772          *   waiters. This is undone in rt_mutex_set_owner(@task) at
 773          *   the end of this function.
 774          */
 775         mark_rt_mutex_waiters(lock);
 776
 777         /*
 778          * If @lock has an owner, give up.
 779          */
 780         if (rt_mutex_owner(lock))
 781                 return 0;
 782
 783         /*
 784          * If @waiter != NULL, @task has already enqueued the waiter
 785          * into @lock waiter list. If @waiter == NULL then this is a
 786          * trylock attempt.
 787          */
 788         if (waiter) {
 789                 /*
 790                  * If waiter is not the highest priority waiter of
 791                  * @lock, give up.
 792                  */
 793                 if (waiter != rt_mutex_top_waiter(lock))
 794                         return 0;
 795
 796                 /*
 797                  * We can acquire the lock. Remove the waiter from the
 798                  * lock waiters list.
 799                  */
 800                 rt_mutex_dequeue(lock, waiter);
 801
 802         } else {
 803                 /*
 804                  * If the lock has waiters already we check whether @task is
 805                  * eligible to take over the lock.
 806                  *
 807                  * If there are no other waiters, @task can acquire
 808                  * the lock.  @task->pi_blocked_on is NULL, so it does
 809                  * not need to be dequeued.
 810                  */
 811                 if (rt_mutex_has_waiters(lock)) {
 812                         /*
 813                          * If @task->prio is greater than or equal to
 814                          * the top waiter priority (kernel view),
 815                          * @task lost.
 816                          */
 817                         if (task->prio >= rt_mutex_top_waiter(lock)->prio)
 818                                 return 0;
 819
 820                         /*
 821                          * The current top waiter stays enqueued. We
 822                          * don't have to change anything in the lock
 823                          * waiters order.
 824                          */
 825                 } else {
 826                         /*
 827                          * No waiters. Take the lock without the
 828                          * pi_lock dance.@task->pi_blocked_on is NULL
 829                          * and we have no waiters to enqueue in @task
 830                          * pi waiters list.
 831                          */
 832                         goto takeit;
 833                 }
 834         }
 835
 836         /*
 837          * Clear @task->pi_blocked_on. Requires protection by
 838          * @task->pi_lock. Redundant operation for the @waiter == NULL
 839          * case, but conditionals are more expensive than a redundant
 840          * store.
 841          */
 842         raw_spin_lock_irqsave(&task->pi_lock, flags);
 843         task->pi_blocked_on = NULL;
 844         /*
 845          * Finish the lock acquisition. @task is the new owner. If
 846          * other waiters exist we have to insert the highest priority
 847          * waiter into @task->pi_waiters list.
 848          */
 849         if (rt_mutex_has_waiters(lock))
 850                 rt_mutex_enqueue_pi(task, rt_mutex_top_waiter(lock));
 851         raw_spin_unlock_irqrestore(&task->pi_lock, flags);
 852
 853 takeit:
 854         /* We got the lock. */
 855         debug_rt_mutex_lock(lock);
 856
 857         /*
 858          * This either preserves the RT_MUTEX_HAS_WAITERS bit if there
 859          * are still waiters or clears it.
 860          */
 861         rt_mutex_set_owner(lock, task);
 862
 863         rt_mutex_deadlock_account_lock(lock, task);
 864
 865         return 1;
 866 }
 867
 868 /*
 869  * Task blocks on lock.
 870  *
 871  * Prepare waiter and propagate pi chain
 872  *
 873  * This must be called with lock->wait_lock held.
 874  */
 875 static int task_blocks_on_rt_mutex(struct rt_mutex *lock,
 876                                    struct rt_mutex_waiter *waiter,
 877                                    struct task_struct *task,
 878                                    enum rtmutex_chainwalk chwalk)
 879 {
 880         struct task_struct *owner = rt_mutex_owner(lock);
 881         struct rt_mutex_waiter *top_waiter = waiter;
 882         struct rt_mutex *next_lock;
 883         int chain_walk = 0, res;
 884         unsigned long flags;
 885
 886         /*
 887          * Early deadlock detection. We really don't want the task to
 888          * enqueue on itself just to untangle the mess later. It's not
 889          * only an optimization. We drop the locks, so another waiter
 890          * can come in before the chain walk detects the deadlock. So
 891          * the other will detect the deadlock and return -EDEADLOCK,
 892          * which is wrong, as the other waiter is not in a deadlock
 893          * situation.
 894          */
 895         if (owner == task)
 896                 return -EDEADLK;
 897
 898         raw_spin_lock_irqsave(&task->pi_lock, flags);
 899         __rt_mutex_adjust_prio(task);
 900         waiter->task = task;
 901         waiter->lock = lock;
 902         waiter->prio = task->prio;
 903
 904         /* Get the top priority waiter on the lock */
 905         if (rt_mutex_has_waiters(lock))
 906                 top_waiter = rt_mutex_top_waiter(lock);
 907         rt_mutex_enqueue(lock, waiter);
 908
 909         task->pi_blocked_on = waiter;
 910
 911         raw_spin_unlock_irqrestore(&task->pi_lock, flags);
 912
 913         if (!owner)
 914                 return 0;
 915
 916         raw_spin_lock_irqsave(&owner->pi_lock, flags);
 917         if (waiter == rt_mutex_top_waiter(lock)) {
 918                 rt_mutex_dequeue_pi(owner, top_waiter);
 919                 rt_mutex_enqueue_pi(owner, waiter);
 920
 921                 __rt_mutex_adjust_prio(owner);
 922                 if (owner->pi_blocked_on)
 923                         chain_walk = 1;
 924         } else if (rt_mutex_cond_detect_deadlock(waiter, chwalk)) {
 925                 chain_walk = 1;
 926         }
 927
 928         /* Store the lock on which owner is blocked or NULL */
 929         next_lock = task_blocked_on_lock(owner);
 930
 931         raw_spin_unlock_irqrestore(&owner->pi_lock, flags);
 932         /*
 933          * Even if full deadlock detection is on, if the owner is not
 934          * blocked itself, we can avoid finding this out in the chain
 935          * walk.
 936          */
 937         if (!chain_walk || !next_lock)
 938                 return 0;
 939
 940         /*
 941          * The owner can't disappear while holding a lock,
 942          * so the owner struct is protected by wait_lock.
 943          * Gets dropped in rt_mutex_adjust_prio_chain()!
 944          */
 945         get_task_struct(owner);
 946
 947         raw_spin_unlock(&lock->wait_lock);
 948
 949         res = rt_mutex_adjust_prio_chain(owner, chwalk, lock,
 950                                          next_lock, waiter, task);
 951
 952         raw_spin_lock(&lock->wait_lock);
 953
 954         return res;
 955 }
 956
 957 /*
 958  * Wake up the next waiter on the lock.
 959  *
 960  * Remove the top waiter from the current tasks pi waiter list and
 961  * wake it up.
 962  *
 963  * Called with lock->wait_lock held.
 964  */
 965 static void wakeup_next_waiter(struct rt_mutex *lock)
 966 {
 967         struct rt_mutex_waiter *waiter;
 968         unsigned long flags;
 969
 970         raw_spin_lock_irqsave(&current->pi_lock, flags);
 971
 972         waiter = rt_mutex_top_waiter(lock);
 973
 974         /*
 975          * Remove it from current->pi_waiters. We do not adjust a
 976          * possible priority boost right now. We execute wakeup in the
 977          * boosted mode and go back to normal after releasing
 978          * lock->wait_lock.
 979          */
 980         rt_mutex_dequeue_pi(current, waiter);
 981
 982         /*
 983          * As we are waking up the top waiter, and the waiter stays
 984          * queued on the lock until it gets the lock, this lock
 985          * obviously has waiters. Just set the bit here and this has
 986          * the added benefit of forcing all new tasks into the
 987          * slow path making sure no task of lower priority than
 988          * the top waiter can steal this lock.
 989          */
 990         lock->owner = (void *) RT_MUTEX_HAS_WAITERS;
 991
 992         raw_spin_unlock_irqrestore(&current->pi_lock, flags);
 993
 994         /*
 995          * It's safe to dereference waiter as it cannot go away as
 996          * long as we hold lock->wait_lock. The waiter task needs to
 997          * acquire it in order to dequeue the waiter.
 998          */
 999         wake_up_process(waiter->task);
1000 }
1001
1002 /*
1003  * Remove a waiter from a lock and give up
1004  *
1005  * Must be called with lock->wait_lock held and
1006  * have just failed to try_to_take_rt_mutex().
1007  */
1008 static void remove_waiter(struct rt_mutex *lock,
1009                           struct rt_mutex_waiter *waiter)
1010 {
1011         bool is_top_waiter = (waiter == rt_mutex_top_waiter(lock));
1012         struct task_struct *owner = rt_mutex_owner(lock);
1013         struct rt_mutex *next_lock;
1014         unsigned long flags;
1015
1016         raw_spin_lock_irqsave(&current->pi_lock, flags);
1017         rt_mutex_dequeue(lock, waiter);
1018         current->pi_blocked_on = NULL;
1019         raw_spin_unlock_irqrestore(&current->pi_lock, flags);
1020
1021         /*
1022          * Only update priority if the waiter was the highest priority
1023          * waiter of the lock and there is an owner to update.
1024          */
1025         if (!owner || !is_top_waiter)
1026                 return;
1027
1028         raw_spin_lock_irqsave(&owner->pi_lock, flags);
1029
1030         rt_mutex_dequeue_pi(owner, waiter);
1031
1032         if (rt_mutex_has_waiters(lock))
1033                 rt_mutex_enqueue_pi(owner, rt_mutex_top_waiter(lock));
1034
1035         __rt_mutex_adjust_prio(owner);
1036
1037         /* Store the lock on which owner is blocked or NULL */
1038         next_lock = task_blocked_on_lock(owner);
1039
1040         raw_spin_unlock_irqrestore(&owner->pi_lock, flags);
1041
1042         /*
1043          * Don't walk the chain, if the owner task is not blocked
1044          * itself.
1045          */
1046         if (!next_lock)
1047                 return;
1048
1049         /* gets dropped in rt_mutex_adjust_prio_chain()! */
1050         get_task_struct(owner);
1051
1052         raw_spin_unlock(&lock->wait_lock);
1053
1054         rt_mutex_adjust_prio_chain(owner, RT_MUTEX_MIN_CHAINWALK, lock,
1055                                    next_lock, NULL, current);
1056
1057         raw_spin_lock(&lock->wait_lock);
1058 }
1059
1060 /*
1061  * Recheck the pi chain, in case we got a priority setting
1062  *
1063  * Called from sched_setscheduler
1064  */
1065 void rt_mutex_adjust_pi(struct task_struct *task)
1066 {
1067         struct rt_mutex_waiter *waiter;
1068         struct rt_mutex *next_lock;
1069         unsigned long flags;
1070
1071         raw_spin_lock_irqsave(&task->pi_lock, flags);
1072
1073         waiter = task->pi_blocked_on;
1074         if (!waiter || (waiter->prio == task->prio &&
1075                         !dl_prio(task->prio))) {
1076                 raw_spin_unlock_irqrestore(&task->pi_lock, flags);
1077                 return;
1078         }
1079         next_lock = waiter->lock;
1080         raw_spin_unlock_irqrestore(&task->pi_lock, flags);
1081
1082         /* gets dropped in rt_mutex_adjust_prio_chain()! */
1083         get_task_struct(task);
1084
1085         rt_mutex_adjust_prio_chain(task, RT_MUTEX_MIN_CHAINWALK, NULL,
1086                                    next_lock, NULL, task);
1087 }
1088
1089 /**
1090  * __rt_mutex_slowlock() - Perform the wait-wake-try-to-take loop
1091  * @lock:                the rt_mutex to take
1092  * @state:               the state the task should block in (TASK_INTERRUPTIBLE
1093  *                       or TASK_UNINTERRUPTIBLE)
1094  * @timeout:             the pre-initialized and started timer, or NULL for none
1095  * @waiter:              the pre-initialized rt_mutex_waiter
1096  *
1097  * lock->wait_lock must be held by the caller.
1098  */
1099 static int __sched
1100 __rt_mutex_slowlock(struct rt_mutex *lock, int state,
1101                     struct hrtimer_sleeper *timeout,
1102                     struct rt_mutex_waiter *waiter)
1103 {
1104         int ret = 0;
1105
1106         for (;;) {
1107                 /* Try to acquire the lock: */
1108                 if (try_to_take_rt_mutex(lock, current, waiter))
1109                         break;
1110
1111                 /*
1112                  * TASK_INTERRUPTIBLE checks for signals and
1113                  * timeout. Ignored otherwise.
1114                  */
1115                 if (unlikely(state == TASK_INTERRUPTIBLE)) {
1116                         /* Signal pending? */
1117                         if (signal_pending(current))
1118                                 ret = -EINTR;
1119                         if (timeout && !timeout->task)
1120                                 ret = -ETIMEDOUT;
1121                         if (ret)
1122                                 break;
1123                 }
1124
1125                 raw_spin_unlock(&lock->wait_lock);
1126
1127                 debug_rt_mutex_print_deadlock(waiter);
1128
1129                 schedule_rt_mutex(lock);
1130
1131                 raw_spin_lock(&lock->wait_lock);
1132                 set_current_state(state);
1133         }
1134
1135         __set_current_state(TASK_RUNNING);
1136         return ret;
1137 }
1138
1139 static void rt_mutex_handle_deadlock(int res, int detect_deadlock,
1140                                      struct rt_mutex_waiter *w)
1141 {
1142         /*
1143          * If the result is not -EDEADLOCK or the caller requested
1144          * deadlock detection, nothing to do here.
1145          */
1146         if (res != -EDEADLOCK || detect_deadlock)
1147                 return;
1148
1149         /*
1150          * Yell lowdly and stop the task right here.
1151          */
1152         rt_mutex_print_deadlock(w);
1153         while (1) {
1154                 set_current_state(TASK_INTERRUPTIBLE);
1155                 schedule();
1156         }
1157 }
1158
1159 /*
1160  * Slow path lock function:
1161  */
1162 static int __sched
1163 rt_mutex_slowlock(struct rt_mutex *lock, int state,
1164                   struct hrtimer_sleeper *timeout,
1165                   enum rtmutex_chainwalk chwalk)
1166 {
1167         struct rt_mutex_waiter waiter;
1168         int ret = 0;
1169
1170         debug_rt_mutex_init_waiter(&waiter);
1171         RB_CLEAR_NODE(&waiter.pi_tree_entry);
1172         RB_CLEAR_NODE(&waiter.tree_entry);
1173
1174         raw_spin_lock(&lock->wait_lock);
1175
1176         /* Try to acquire the lock again: */
1177         if (try_to_take_rt_mutex(lock, current, NULL)) {
1178                 raw_spin_unlock(&lock->wait_lock);
1179                 return 0;
1180         }
1181
1182         set_current_state(state);
1183
1184         /* Setup the timer, when timeout != NULL */
1185         if (unlikely(timeout)) {
1186                 hrtimer_start_expires(&timeout->timer, HRTIMER_MODE_ABS);
1187                 if (!hrtimer_active(&timeout->timer))
1188                         timeout->task = NULL;
1189         }
1190
1191         ret = task_blocks_on_rt_mutex(lock, &waiter, current, chwalk);
1192
1193         if (likely(!ret))
1194                 /* sleep on the mutex */
1195                 ret = __rt_mutex_slowlock(lock, state, timeout, &waiter);
1196
1197         if (unlikely(ret)) {
1198                 __set_current_state(TASK_RUNNING);
1199                 if (rt_mutex_has_waiters(lock))
1200                         remove_waiter(lock, &waiter);
1201                 rt_mutex_handle_deadlock(ret, chwalk, &waiter);
1202         }
1203
1204         /*
1205          * try_to_take_rt_mutex() sets the waiter bit
1206          * unconditionally. We might have to fix that up.
1207          */
1208         fixup_rt_mutex_waiters(lock);
1209
1210         raw_spin_unlock(&lock->wait_lock);
1211
1212         /* Remove pending timer: */
1213         if (unlikely(timeout))
1214                 hrtimer_cancel(&timeout->timer);
1215
1216         debug_rt_mutex_free_waiter(&waiter);
1217
1218         return ret;
1219 }
1220
1221 /*
1222  * Slow path try-lock function:
1223  */
1224 static inline int rt_mutex_slowtrylock(struct rt_mutex *lock)
1225 {
1226         int ret;
1227
1228         /*
1229          * If the lock already has an owner we fail to get the lock.
1230          * This can be done without taking the @lock->wait_lock as
1231          * it is only being read, and this is a trylock anyway.
1232          */
1233         if (rt_mutex_owner(lock))
1234                 return 0;
1235
1236         /*
1237          * The mutex has currently no owner. Lock the wait lock and
1238          * try to acquire the lock.
1239          */
1240         raw_spin_lock(&lock->wait_lock);
1241
1242         ret = try_to_take_rt_mutex(lock, current, NULL);
1243
1244         /*
1245          * try_to_take_rt_mutex() sets the lock waiters bit
1246          * unconditionally. Clean this up.
1247          */
1248         fixup_rt_mutex_waiters(lock);
1249
1250         raw_spin_unlock(&lock->wait_lock);
1251
1252         return ret;
1253 }
1254
1255 /*
1256  * Slow path to release a rt-mutex:
1257  */
1258 static void __sched
1259 rt_mutex_slowunlock(struct rt_mutex *lock)
1260 {
1261         raw_spin_lock(&lock->wait_lock);
1262
1263         debug_rt_mutex_unlock(lock);
1264
1265         rt_mutex_deadlock_account_unlock(current);
1266
1267         /*
1268          * We must be careful here if the fast path is enabled. If we
1269          * have no waiters queued we cannot set owner to NULL here
1270          * because of:
1271          *
1272          * foo->lock->owner = NULL;
1273          *                      rtmutex_lock(foo->lock);   <- fast path
1274          *                      free = atomic_dec_and_test(foo->refcnt);
1275          *                      rtmutex_unlock(foo->lock); <- fast path
1276          *                      if (free)
1277          *                              kfree(foo);
1278          * raw_spin_unlock(foo->lock->wait_lock);
1279          *
1280          * So for the fastpath enabled kernel:
1281          *
1282          * Nothing can set the waiters bit as long as we hold
1283          * lock->wait_lock. So we do the following sequence:
1284          *
1285          *      owner = rt_mutex_owner(lock);
1286          *      clear_rt_mutex_waiters(lock);
1287          *      raw_spin_unlock(&lock->wait_lock);
1288          *      if (cmpxchg(&lock->owner, owner, 0) == owner)
1289          *              return;
1290          *      goto retry;
1291          *
1292          * The fastpath disabled variant is simple as all access to
1293          * lock->owner is serialized by lock->wait_lock:
1294          *
1295          *      lock->owner = NULL;
1296          *      raw_spin_unlock(&lock->wait_lock);
1297          */
1298         while (!rt_mutex_has_waiters(lock)) {
1299                 /* Drops lock->wait_lock ! */
1300                 if (unlock_rt_mutex_safe(lock) == true)
1301                         return;
1302                 /* Relock the rtmutex and try again */
1303                 raw_spin_lock(&lock->wait_lock);
1304         }
1305
1306         /*
1307          * The wakeup next waiter path does not suffer from the above
1308          * race. See the comments there.
1309          */
1310         wakeup_next_waiter(lock);
1311
1312         raw_spin_unlock(&lock->wait_lock);
1313
1314         /* Undo pi boosting if necessary: */
1315         rt_mutex_adjust_prio(current);
1316 }
1317
1318 /*
1319  * debug aware fast / slowpath lock,trylock,unlock
1320  *
1321  * The atomic acquire/release ops are compiled away, when either the
1322  * architecture does not support cmpxchg or when debugging is enabled.
1323  */
1324 static inline int
1325 rt_mutex_fastlock(struct rt_mutex *lock, int state,
1326                   int (*slowfn)(struct rt_mutex *lock, int state,
1327                                 struct hrtimer_sleeper *timeout,
1328                                 enum rtmutex_chainwalk chwalk))
1329 {
1330         if (likely(rt_mutex_cmpxchg(lock, NULL, current))) {
1331                 rt_mutex_deadlock_account_lock(lock, current);
1332                 return 0;
1333         } else
1334                 return slowfn(lock, state, NULL, RT_MUTEX_MIN_CHAINWALK);
1335 }
1336
1337 static inline int
1338 rt_mutex_timed_fastlock(struct rt_mutex *lock, int state,
1339                         struct hrtimer_sleeper *timeout,
1340                         enum rtmutex_chainwalk chwalk,
1341                         int (*slowfn)(struct rt_mutex *lock, int state,
1342                                       struct hrtimer_sleeper *timeout,
1343                                       enum rtmutex_chainwalk chwalk))
1344 {
1345         if (chwalk == RT_MUTEX_MIN_CHAINWALK &&
1346             likely(rt_mutex_cmpxchg(lock, NULL, current))) {
1347                 rt_mutex_deadlock_account_lock(lock, current);
1348                 return 0;
1349         } else
1350                 return slowfn(lock, state, timeout, chwalk);
1351 }
1352
1353 static inline int
1354 rt_mutex_fasttrylock(struct rt_mutex *lock,
1355                      int (*slowfn)(struct rt_mutex *lock))
1356 {
1357         if (likely(rt_mutex_cmpxchg(lock, NULL, current))) {
1358                 rt_mutex_deadlock_account_lock(lock, current);
1359                 return 1;
1360         }
1361         return slowfn(lock);
1362 }
1363
1364 static inline void
1365 rt_mutex_fastunlock(struct rt_mutex *lock,
1366                     void (*slowfn)(struct rt_mutex *lock))
1367 {
1368         if (likely(rt_mutex_cmpxchg(lock, current, NULL)))
1369                 rt_mutex_deadlock_account_unlock(current);
1370         else
1371                 slowfn(lock);
1372 }
1373
1374 /**
1375  * rt_mutex_lock - lock a rt_mutex
1376  *
1377  * @lock: the rt_mutex to be locked
1378  */
1379 void __sched rt_mutex_lock(struct rt_mutex *lock)
1380 {
1381         might_sleep();
1382
1383         rt_mutex_fastlock(lock, TASK_UNINTERRUPTIBLE, rt_mutex_slowlock);
1384 }
1385 EXPORT_SYMBOL_GPL(rt_mutex_lock);
1386
1387 /**
1388  * rt_mutex_lock_interruptible - lock a rt_mutex interruptible
1389  *
1390  * @lock:               the rt_mutex to be locked
1391  *
1392  * Returns:
1393  *  0           on success
1394  * -EINTR       when interrupted by a signal
1395  */
1396 int __sched rt_mutex_lock_interruptible(struct rt_mutex *lock)
1397 {
1398         might_sleep();
1399
1400         return rt_mutex_fastlock(lock, TASK_INTERRUPTIBLE, rt_mutex_slowlock);
1401 }
1402 EXPORT_SYMBOL_GPL(rt_mutex_lock_interruptible);
1403
1404 /*
1405  * Futex variant with full deadlock detection.
1406  */
1407 int rt_mutex_timed_futex_lock(struct rt_mutex *lock,
1408                               struct hrtimer_sleeper *timeout)
1409 {
1410         might_sleep();
1411
1412         return rt_mutex_timed_fastlock(lock, TASK_INTERRUPTIBLE, timeout,
1413                                        RT_MUTEX_FULL_CHAINWALK,
1414                                        rt_mutex_slowlock);
1415 }
1416
1417 /**
1418  * rt_mutex_timed_lock - lock a rt_mutex interruptible
1419  *                      the timeout structure is provided
1420  *                      by the caller
1421  *
1422  * @lock:               the rt_mutex to be locked
1423  * @timeout:            timeout structure or NULL (no timeout)
1424  *
1425  * Returns:
1426  *  0           on success
1427  * -EINTR       when interrupted by a signal
1428  * -ETIMEDOUT   when the timeout expired
1429  */
1430 int
1431 rt_mutex_timed_lock(struct rt_mutex *lock, struct hrtimer_sleeper *timeout)
1432 {
1433         might_sleep();
1434
1435         return rt_mutex_timed_fastlock(lock, TASK_INTERRUPTIBLE, timeout,
1436                                        RT_MUTEX_MIN_CHAINWALK,
1437                                        rt_mutex_slowlock);
1438 }
1439 EXPORT_SYMBOL_GPL(rt_mutex_timed_lock);
1440
1441 /**
1442  * rt_mutex_trylock - try to lock a rt_mutex
1443  *
1444  * @lock:       the rt_mutex to be locked
1445  *
1446  * Returns 1 on success and 0 on contention
1447  */
1448 int __sched rt_mutex_trylock(struct rt_mutex *lock)
1449 {
1450         return rt_mutex_fasttrylock(lock, rt_mutex_slowtrylock);
1451 }
1452 EXPORT_SYMBOL_GPL(rt_mutex_trylock);
1453
1454 /**
1455  * rt_mutex_unlock - unlock a rt_mutex
1456  *
1457  * @lock: the rt_mutex to be unlocked
1458  */
1459 void __sched rt_mutex_unlock(struct rt_mutex *lock)
1460 {
1461         rt_mutex_fastunlock(lock, rt_mutex_slowunlock);
1462 }
1463 EXPORT_SYMBOL_GPL(rt_mutex_unlock);
1464
1465 /**
1466  * rt_mutex_destroy - mark a mutex unusable
1467  * @lock: the mutex to be destroyed
1468  *
1469  * This function marks the mutex uninitialized, and any subsequent
1470  * use of the mutex is forbidden. The mutex must not be locked when
1471  * this function is called.
1472  */
1473 void rt_mutex_destroy(struct rt_mutex *lock)
1474 {
1475         WARN_ON(rt_mutex_is_locked(lock));
1476 #ifdef CONFIG_DEBUG_RT_MUTEXES
1477         lock->magic = NULL;
1478 #endif
1479 }
1480
1481 EXPORT_SYMBOL_GPL(rt_mutex_destroy);
1482
1483 /**
1484  * __rt_mutex_init - initialize the rt lock
1485  *
1486  * @lock: the rt lock to be initialized
1487  *
1488  * Initialize the rt lock to unlocked state.
1489  *
1490  * Initializing of a locked rt lock is not allowed
1491  */
1492 void __rt_mutex_init(struct rt_mutex *lock, const char *name)
1493 {
1494         lock->owner = NULL;
1495         raw_spin_lock_init(&lock->wait_lock);
1496         lock->waiters = RB_ROOT;
1497         lock->waiters_leftmost = NULL;
1498
1499         debug_rt_mutex_init(lock, name);
1500 }
1501 EXPORT_SYMBOL_GPL(__rt_mutex_init);
1502
1503 /**
1504  * rt_mutex_init_proxy_locked - initialize and lock a rt_mutex on behalf of a
1505  *                              proxy owner
1506  *
1507  * @lock:       the rt_mutex to be locked
1508  * @proxy_owner:the task to set as owner
1509  *
1510  * No locking. Caller has to do serializing itself
1511  * Special API call for PI-futex support
1512  */
1513 void rt_mutex_init_proxy_locked(struct rt_mutex *lock,
1514                                 struct task_struct *proxy_owner)
1515 {
1516         __rt_mutex_init(lock, NULL);
1517         debug_rt_mutex_proxy_lock(lock, proxy_owner);
1518         rt_mutex_set_owner(lock, proxy_owner);
1519         rt_mutex_deadlock_account_lock(lock, proxy_owner);
1520 }
1521
1522 /**
1523  * rt_mutex_proxy_unlock - release a lock on behalf of owner
1524  *
1525  * @lock:       the rt_mutex to be locked
1526  *
1527  * No locking. Caller has to do serializing itself
1528  * Special API call for PI-futex support
1529  */
1530 void rt_mutex_proxy_unlock(struct rt_mutex *lock,
1531                            struct task_struct *proxy_owner)
1532 {
1533         debug_rt_mutex_proxy_unlock(lock);
1534         rt_mutex_set_owner(lock, NULL);
1535         rt_mutex_deadlock_account_unlock(proxy_owner);
1536 }
1537
1538 /**
1539  * rt_mutex_start_proxy_lock() - Start lock acquisition for another task
1540  * @lock:               the rt_mutex to take
1541  * @waiter:             the pre-initialized rt_mutex_waiter
1542  * @task:               the task to prepare
1543  *
1544  * Returns:
1545  *  0 - task blocked on lock
1546  *  1 - acquired the lock for task, caller should wake it up
1547  * <0 - error
1548  *
1549  * Special API call for FUTEX_REQUEUE_PI support.
1550  */
1551 int rt_mutex_start_proxy_lock(struct rt_mutex *lock,
1552                               struct rt_mutex_waiter *waiter,
1553                               struct task_struct *task)
1554 {
1555         int ret;
1556
1557         raw_spin_lock(&lock->wait_lock);
1558
1559         if (try_to_take_rt_mutex(lock, task, NULL)) {
1560                 raw_spin_unlock(&lock->wait_lock);
1561                 return 1;
1562         }
1563
1564         /* We enforce deadlock detection for futexes */
1565         ret = task_blocks_on_rt_mutex(lock, waiter, task,
1566                                       RT_MUTEX_FULL_CHAINWALK);
1567
1568         if (ret && !rt_mutex_owner(lock)) {
1569                 /*
1570                  * Reset the return value. We might have
1571                  * returned with -EDEADLK and the owner
1572                  * released the lock while we were walking the
1573                  * pi chain.  Let the waiter sort it out.
1574                  */
1575                 ret = 0;
1576         }
1577
1578         if (unlikely(ret))
1579                 remove_waiter(lock, waiter);
1580
1581         raw_spin_unlock(&lock->wait_lock);
1582
1583         debug_rt_mutex_print_deadlock(waiter);
1584
1585         return ret;
1586 }
1587
1588 /**
1589  * rt_mutex_next_owner - return the next owner of the lock
1590  *
1591  * @lock: the rt lock query
1592  *
1593  * Returns the next owner of the lock or NULL
1594  *
1595  * Caller has to serialize against other accessors to the lock
1596  * itself.
1597  *
1598  * Special API call for PI-futex support
1599  */
1600 struct task_struct *rt_mutex_next_owner(struct rt_mutex *lock)
1601 {
1602         if (!rt_mutex_has_waiters(lock))
1603                 return NULL;
1604
1605         return rt_mutex_top_waiter(lock)->task;
1606 }
1607
1608 /**
1609  * rt_mutex_finish_proxy_lock() - Complete lock acquisition
1610  * @lock:               the rt_mutex we were woken on
1611  * @to:                 the timeout, null if none. hrtimer should already have
1612  *                      been started.
1613  * @waiter:             the pre-initialized rt_mutex_waiter
1614  *
1615  * Complete the lock acquisition started our behalf by another thread.
1616  *
1617  * Returns:
1618  *  0 - success
1619  * <0 - error, one of -EINTR, -ETIMEDOUT
1620  *
1621  * Special API call for PI-futex requeue support
1622  */
1623 int rt_mutex_finish_proxy_lock(struct rt_mutex *lock,
1624                                struct hrtimer_sleeper *to,
1625                                struct rt_mutex_waiter *waiter)
1626 {
1627         int ret;
1628
1629         raw_spin_lock(&lock->wait_lock);
1630
1631         set_current_state(TASK_INTERRUPTIBLE);
1632
1633         /* sleep on the mutex */
1634         ret = __rt_mutex_slowlock(lock, TASK_INTERRUPTIBLE, to, waiter);
1635
1636         if (unlikely(ret))
1637                 remove_waiter(lock, waiter);
1638
1639         /*
1640          * try_to_take_rt_mutex() sets the waiter bit unconditionally. We might
1641          * have to fix that up.
1642          */
1643         fixup_rt_mutex_waiters(lock);
1644
1645         raw_spin_unlock(&lock->wait_lock);
1646
1647         return ret;
1648 }