projects/linux·blob v4.11-rc8 · refs

1773 lines · 46.8 KiB

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