Lines Matching +full:foo +full:- +full:queue
1 // SPDX-License-Identifier: GPL-2.0-only
3 * RT-Mutexes: simple blocking mutual exclusion locks with PI support
7 * Copyright (C) 2004-2006 Red Hat, Inc., Ingo Molnar <mingo@redhat.com>
8 * Copyright (C) 2005-2006 Timesys Corp., Thomas Gleixner <tglx@timesys.com>
17 * See Documentation/locking/rt-mutex-design.rst for details.
66 * lock->owner state tracking:
68 * lock->owner holds the task_struct pointer of the owner. Bit 0
79 * possible when bit 0 of lock->owner is 0.
82 * with ->wait_lock is held. To prevent any fast path cmpxchg to the lock,
107 * lock->wait_lock is held but explicit acquire semantics are needed in rt_mutex_set_owner()
110 xchg_acquire(&lock->owner, rt_mutex_owner_encode(lock, owner)); in rt_mutex_set_owner()
115 /* lock->wait_lock is held so the unlock provides release semantics. */ in rt_mutex_clear_owner()
116 WRITE_ONCE(lock->owner, rt_mutex_owner_encode(lock, NULL)); in rt_mutex_clear_owner()
121 lock->owner = (struct task_struct *) in clear_rt_mutex_waiters()
122 ((unsigned long)lock->owner & ~RT_MUTEX_HAS_WAITERS); in clear_rt_mutex_waiters()
128 unsigned long owner, *p = (unsigned long *) &lock->owner; in fixup_rt_mutex_waiters()
135 * lock->owner still has the waiters bit set, otherwise the in fixup_rt_mutex_waiters()
139 * l->owner=T1 in fixup_rt_mutex_waiters()
141 * lock(l->lock) in fixup_rt_mutex_waiters()
142 * l->owner = T1 | HAS_WAITERS; in fixup_rt_mutex_waiters()
145 * unlock(l->lock) in fixup_rt_mutex_waiters()
149 * lock(l->lock) in fixup_rt_mutex_waiters()
150 * l->owner = T1 | HAS_WAITERS; in fixup_rt_mutex_waiters()
153 * unlock(l->lock) in fixup_rt_mutex_waiters()
155 * signal(->T2) signal(->T3) in fixup_rt_mutex_waiters()
156 * lock(l->lock) in fixup_rt_mutex_waiters()
159 * unlock(l->lock) in fixup_rt_mutex_waiters()
160 * lock(l->lock) in fixup_rt_mutex_waiters()
164 * unlock(l->lock) in fixup_rt_mutex_waiters()
165 * lock(l->lock) in fixup_rt_mutex_waiters()
168 * l->owner = owner in fixup_rt_mutex_waiters()
169 * owner = l->owner & ~HAS_WAITERS; in fixup_rt_mutex_waiters()
170 * ==> l->owner = T1 in fixup_rt_mutex_waiters()
172 * lock(l->lock) in fixup_rt_mutex_waiters()
175 * owner = l->owner & ~HAS_WAITERS; in fixup_rt_mutex_waiters()
176 * cmpxchg(l->owner, T1, NULL) in fixup_rt_mutex_waiters()
177 * ===> Success (l->owner = NULL) in fixup_rt_mutex_waiters()
179 * l->owner = owner in fixup_rt_mutex_waiters()
180 * ==> l->owner = T1 in fixup_rt_mutex_waiters()
185 * serialized by l->lock, so nothing else can modify the waiters in fixup_rt_mutex_waiters()
186 * bit. If the bit is set then nothing can change l->owner either in fixup_rt_mutex_waiters()
218 return try_cmpxchg_acquire(&lock->owner, &old, new); in rt_mutex_cmpxchg_acquire()
230 return try_cmpxchg_release(&lock->owner, &old, new); in rt_mutex_cmpxchg_release()
234 * Callers must hold the ->wait_lock -- which is the whole purpose as we force
240 unsigned long owner, *p = (unsigned long *) &lock->owner; in mark_rt_mutex_waiters()
248 * The cmpxchg loop above is relaxed to avoid back-to-back ACQUIRE in mark_rt_mutex_waiters()
258 * 2) Drop lock->wait_lock
263 __releases(lock->wait_lock) in unlock_rt_mutex_safe()
268 raw_spin_unlock_irqrestore(&lock->wait_lock, flags); in unlock_rt_mutex_safe()
314 * acquire a non-contended rtmutex. in rt_mutex_try_acquire()
328 lock->owner = (struct task_struct *) in mark_rt_mutex_waiters()
329 ((unsigned long)lock->owner | RT_MUTEX_HAS_WAITERS); in mark_rt_mutex_waiters()
333 * Simple slow path only version: lock->owner is protected by lock->wait_lock.
337 __releases(lock->wait_lock) in unlock_rt_mutex_safe()
339 lock->owner = NULL; in unlock_rt_mutex_safe()
340 raw_spin_unlock_irqrestore(&lock->wait_lock, flags); in unlock_rt_mutex_safe()
347 int prio = task->prio; in __waiter_prio()
356 * Update the waiter->tree copy of the sort keys.
361 lockdep_assert_held(&waiter->lock->wait_lock); in waiter_update_prio()
362 lockdep_assert(RB_EMPTY_NODE(&waiter->tree.entry)); in waiter_update_prio()
364 waiter->tree.prio = __waiter_prio(task); in waiter_update_prio()
365 waiter->tree.deadline = task->dl.deadline; in waiter_update_prio()
369 * Update the waiter->pi_tree copy of the sort keys (from the tree copy).
374 lockdep_assert_held(&waiter->lock->wait_lock); in waiter_clone_prio()
375 lockdep_assert_held(&task->pi_lock); in waiter_clone_prio()
376 lockdep_assert(RB_EMPTY_NODE(&waiter->pi_tree.entry)); in waiter_clone_prio()
378 waiter->pi_tree.prio = waiter->tree.prio; in waiter_clone_prio()
379 waiter->pi_tree.deadline = waiter->tree.deadline; in waiter_clone_prio()
386 &(struct rt_waiter_node){ .prio = __waiter_prio(p), .deadline = (p)->dl.deadline }
393 if (left->prio < right->prio) in rt_waiter_node_less()
402 if (dl_prio(left->prio)) in rt_waiter_node_less()
403 return dl_time_before(left->deadline, right->deadline); in rt_waiter_node_less()
411 if (left->prio != right->prio) in rt_waiter_node_equal()
420 if (dl_prio(left->prio)) in rt_waiter_node_equal()
421 return left->deadline == right->deadline; in rt_waiter_node_equal()
429 if (rt_waiter_node_less(&waiter->tree, &top_waiter->tree)) in rt_mutex_steal()
437 if (rt_prio(waiter->tree.prio) || dl_prio(waiter->tree.prio)) in rt_mutex_steal()
440 return rt_waiter_node_equal(&waiter->tree, &top_waiter->tree); in rt_mutex_steal()
454 if (rt_waiter_node_less(&aw->tree, &bw->tree)) in __waiter_less()
460 if (rt_waiter_node_less(&bw->tree, &aw->tree)) in __waiter_less()
463 /* NOTE: relies on waiter->ww_ctx being set before insertion */ in __waiter_less()
464 if (aw->ww_ctx) { in __waiter_less()
465 if (!bw->ww_ctx) in __waiter_less()
468 return (signed long)(aw->ww_ctx->stamp - in __waiter_less()
469 bw->ww_ctx->stamp) < 0; in __waiter_less()
478 lockdep_assert_held(&lock->wait_lock); in rt_mutex_enqueue()
480 rb_add_cached(&waiter->tree.entry, &lock->waiters, __waiter_less); in rt_mutex_enqueue()
486 lockdep_assert_held(&lock->wait_lock); in rt_mutex_dequeue()
488 if (RB_EMPTY_NODE(&waiter->tree.entry)) in rt_mutex_dequeue()
491 rb_erase_cached(&waiter->tree.entry, &lock->waiters); in rt_mutex_dequeue()
492 RB_CLEAR_NODE(&waiter->tree.entry); in rt_mutex_dequeue()
506 lockdep_assert_held(&task->pi_lock); in rt_mutex_enqueue_pi()
508 rb_add_cached(&waiter->pi_tree.entry, &task->pi_waiters, __pi_waiter_less); in rt_mutex_enqueue_pi()
514 lockdep_assert_held(&task->pi_lock); in rt_mutex_dequeue_pi()
516 if (RB_EMPTY_NODE(&waiter->pi_tree.entry)) in rt_mutex_dequeue_pi()
519 rb_erase_cached(&waiter->pi_tree.entry, &task->pi_waiters); in rt_mutex_dequeue_pi()
520 RB_CLEAR_NODE(&waiter->pi_tree.entry); in rt_mutex_dequeue_pi()
528 lockdep_assert_held(&lock->wait_lock); in rt_mutex_adjust_prio()
530 lockdep_assert_held(&p->pi_lock); in rt_mutex_adjust_prio()
533 pi_task = task_top_pi_waiter(p)->task; in rt_mutex_adjust_prio()
545 WARN_ON_ONCE(wqh->rtlock_task); in rt_mutex_wake_q_add_task()
547 wqh->rtlock_task = task; in rt_mutex_wake_q_add_task()
549 wake_q_add(&wqh->head, task); in rt_mutex_wake_q_add_task()
556 rt_mutex_wake_q_add_task(wqh, w->task, w->wake_state); in rt_mutex_wake_q_add()
561 if (IS_ENABLED(CONFIG_PREEMPT_RT) && wqh->rtlock_task) { in rt_mutex_wake_up_q()
562 wake_up_state(wqh->rtlock_task, TASK_RTLOCK_WAIT); in rt_mutex_wake_up_q()
563 put_task_struct(wqh->rtlock_task); in rt_mutex_wake_up_q()
564 wqh->rtlock_task = NULL; in rt_mutex_wake_up_q()
567 if (!wake_q_empty(&wqh->head)) in rt_mutex_wake_up_q()
568 wake_up_q(&wqh->head); in rt_mutex_wake_up_q()
598 return p->pi_blocked_on ? p->pi_blocked_on->lock : NULL; in task_blocked_on_lock()
603 * Decreases task's usage by one - may thus free the task.
620 * Returns 0 or -EDEADLK.
625 * [Pn] task->pi_lock held
626 * [L] rtmutex->wait_lock held
630 * rtmutex->wait_lock
631 * task->pi_lock
647 * [1] lock(task->pi_lock); [R] acquire [P1]
648 * [2] waiter = task->pi_blocked_on; [P1]
650 * [4] lock = waiter->lock; [P1]
651 * [5] if (!try_lock(lock->wait_lock)) { [P1] try to acquire [L]
652 * unlock(task->pi_lock); release [P1]
657 * [8] unlock(task->pi_lock); release [P1]
662 * lock(task->pi_lock); [L] acquire [P2]
665 * [13] unlock(task->pi_lock); release [P2]
666 * unlock(lock->wait_lock); release [L]
711 top_task->comm, task_pid_nr(top_task)); in rt_mutex_adjust_prio_chain()
715 return -EDEADLK; in rt_mutex_adjust_prio_chain()
728 raw_spin_lock_irq(&task->pi_lock); in rt_mutex_adjust_prio_chain()
733 waiter = task->pi_blocked_on; in rt_mutex_adjust_prio_chain()
736 * [3] check_exit_conditions_1() protected by task->pi_lock. in rt_mutex_adjust_prio_chain()
763 if (next_lock != waiter->lock) in rt_mutex_adjust_prio_chain()
774 * P3 should not return -EDEADLK because it gets trapped in the cycle in rt_mutex_adjust_prio_chain()
775 * created by P1 and P2 (which will resolve -- and runs into in rt_mutex_adjust_prio_chain()
788 if (IS_ENABLED(CONFIG_PREEMPT_RT) && waiter->ww_ctx && detect_deadlock) in rt_mutex_adjust_prio_chain()
820 if (rt_waiter_node_equal(&waiter->tree, task_to_waiter_node(task))) { in rt_mutex_adjust_prio_chain()
828 * [4] Get the next lock; per holding task->pi_lock we can't unblock in rt_mutex_adjust_prio_chain()
831 lock = waiter->lock; in rt_mutex_adjust_prio_chain()
833 * [5] We need to trylock here as we are holding task->pi_lock, in rt_mutex_adjust_prio_chain()
837 * Per the above, holding task->pi_lock guarantees lock exists, so in rt_mutex_adjust_prio_chain()
838 * inverting this lock order is infeasible from a life-time in rt_mutex_adjust_prio_chain()
841 if (!raw_spin_trylock(&lock->wait_lock)) { in rt_mutex_adjust_prio_chain()
842 raw_spin_unlock_irq(&task->pi_lock); in rt_mutex_adjust_prio_chain()
848 * [6] check_exit_conditions_2() protected by task->pi_lock and in rt_mutex_adjust_prio_chain()
849 * lock->wait_lock. in rt_mutex_adjust_prio_chain()
857 ret = -EDEADLK; in rt_mutex_adjust_prio_chain()
862 * logic pick which of the contending threads gets -EDEADLK. in rt_mutex_adjust_prio_chain()
868 if (IS_ENABLED(CONFIG_PREEMPT_RT) && orig_waiter && orig_waiter->ww_ctx) in rt_mutex_adjust_prio_chain()
871 raw_spin_unlock(&lock->wait_lock); in rt_mutex_adjust_prio_chain()
885 raw_spin_unlock(&task->pi_lock); in rt_mutex_adjust_prio_chain()
889 * [9] check_exit_conditions_3 protected by lock->wait_lock. in rt_mutex_adjust_prio_chain()
893 raw_spin_unlock_irq(&lock->wait_lock); in rt_mutex_adjust_prio_chain()
899 raw_spin_lock(&task->pi_lock); in rt_mutex_adjust_prio_chain()
914 raw_spin_unlock(&task->pi_lock); in rt_mutex_adjust_prio_chain()
915 raw_spin_unlock_irq(&lock->wait_lock); in rt_mutex_adjust_prio_chain()
952 * Since we hold lock->waiter_lock, task cannot unblock, even if we in rt_mutex_adjust_prio_chain()
953 * release task->pi_lock. in rt_mutex_adjust_prio_chain()
955 raw_spin_unlock(&task->pi_lock); in rt_mutex_adjust_prio_chain()
959 * [9] check_exit_conditions_3 protected by lock->wait_lock. in rt_mutex_adjust_prio_chain()
973 wake_up_state(top_waiter->task, top_waiter->wake_state); in rt_mutex_adjust_prio_chain()
974 raw_spin_unlock_irq(&lock->wait_lock); in rt_mutex_adjust_prio_chain()
981 * Per holding lock->wait_lock and checking for !owner above, there in rt_mutex_adjust_prio_chain()
985 raw_spin_lock(&task->pi_lock); in rt_mutex_adjust_prio_chain()
1024 * [12] check_exit_conditions_4() protected by task->pi_lock in rt_mutex_adjust_prio_chain()
1025 * and lock->wait_lock. The actual decisions are made after we in rt_mutex_adjust_prio_chain()
1031 * task->pi_lock next_lock cannot be dereferenced anymore. in rt_mutex_adjust_prio_chain()
1041 raw_spin_unlock(&task->pi_lock); in rt_mutex_adjust_prio_chain()
1042 raw_spin_unlock_irq(&lock->wait_lock); in rt_mutex_adjust_prio_chain()
1065 raw_spin_unlock_irq(&task->pi_lock); in rt_mutex_adjust_prio_chain()
1073 * Try to take an rt-mutex
1075 * Must be called with lock->wait_lock held and interrupts disabled
1086 lockdep_assert_held(&lock->wait_lock); in try_to_take_rt_mutex()
1090 * RT_MUTEX_HAS_WAITERS bit in @lock->owner. This forces all in try_to_take_rt_mutex()
1092 * and they serialize on @lock->wait_lock. in try_to_take_rt_mutex()
1097 * - There is a lock owner. The caller must fixup the in try_to_take_rt_mutex()
1101 * - @task acquires the lock and there are no other in try_to_take_rt_mutex()
1140 * the lock. @task->pi_blocked_on is NULL, so it does in try_to_take_rt_mutex()
1157 * pi_lock dance.@task->pi_blocked_on is NULL in try_to_take_rt_mutex()
1166 * Clear @task->pi_blocked_on. Requires protection by in try_to_take_rt_mutex()
1167 * @task->pi_lock. Redundant operation for the @waiter == NULL in try_to_take_rt_mutex()
1171 raw_spin_lock(&task->pi_lock); in try_to_take_rt_mutex()
1172 task->pi_blocked_on = NULL; in try_to_take_rt_mutex()
1176 * waiter into @task->pi_waiters tree. in try_to_take_rt_mutex()
1180 raw_spin_unlock(&task->pi_lock); in try_to_take_rt_mutex()
1197 * This must be called with lock->wait_lock held and interrupts disabled
1210 lockdep_assert_held(&lock->wait_lock); in task_blocks_on_rt_mutex()
1217 * the other will detect the deadlock and return -EDEADLOCK, in task_blocks_on_rt_mutex()
1225 return -EDEADLK; in task_blocks_on_rt_mutex()
1227 raw_spin_lock(&task->pi_lock); in task_blocks_on_rt_mutex()
1228 waiter->task = task; in task_blocks_on_rt_mutex()
1229 waiter->lock = lock; in task_blocks_on_rt_mutex()
1238 task->pi_blocked_on = waiter; in task_blocks_on_rt_mutex()
1240 raw_spin_unlock(&task->pi_lock); in task_blocks_on_rt_mutex()
1249 raw_spin_lock(&task->pi_lock); in task_blocks_on_rt_mutex()
1251 task->pi_blocked_on = NULL; in task_blocks_on_rt_mutex()
1252 raw_spin_unlock(&task->pi_lock); in task_blocks_on_rt_mutex()
1260 raw_spin_lock(&owner->pi_lock); in task_blocks_on_rt_mutex()
1266 if (owner->pi_blocked_on) in task_blocks_on_rt_mutex()
1275 raw_spin_unlock(&owner->pi_lock); in task_blocks_on_rt_mutex()
1291 raw_spin_unlock_irq(&lock->wait_lock); in task_blocks_on_rt_mutex()
1296 raw_spin_lock_irq(&lock->wait_lock); in task_blocks_on_rt_mutex()
1303 * queue it up.
1305 * Called with lock->wait_lock held and interrupts disabled.
1312 lockdep_assert_held(&lock->wait_lock); in mark_wakeup_next_waiter()
1314 raw_spin_lock(¤t->pi_lock); in mark_wakeup_next_waiter()
1319 * Remove it from current->pi_waiters and deboost. in mark_wakeup_next_waiter()
1322 * rt_mutex_setprio() to update p->pi_top_task before the in mark_wakeup_next_waiter()
1336 lock->owner = (void *) RT_MUTEX_HAS_WAITERS; in mark_wakeup_next_waiter()
1341 * p->pi_top_task pointer points to a blocked task). This however can in mark_wakeup_next_waiter()
1350 raw_spin_unlock(¤t->pi_lock); in mark_wakeup_next_waiter()
1367 * Slow path try-lock function:
1376 * This can be done without taking the @lock->wait_lock as in rt_mutex_slowtrylock()
1386 raw_spin_lock_irqsave(&lock->wait_lock, flags); in rt_mutex_slowtrylock()
1390 raw_spin_unlock_irqrestore(&lock->wait_lock, flags); in rt_mutex_slowtrylock()
1404 * Slow path to release a rt-mutex.
1412 raw_spin_lock_irqsave(&lock->wait_lock, flags); in rt_mutex_slowunlock()
1421 * foo->lock->owner = NULL; in rt_mutex_slowunlock()
1422 * rtmutex_lock(foo->lock); <- fast path in rt_mutex_slowunlock()
1423 * free = atomic_dec_and_test(foo->refcnt); in rt_mutex_slowunlock()
1424 * rtmutex_unlock(foo->lock); <- fast path in rt_mutex_slowunlock()
1426 * kfree(foo); in rt_mutex_slowunlock()
1427 * raw_spin_unlock(foo->lock->wait_lock); in rt_mutex_slowunlock()
1432 * lock->wait_lock. So we do the following sequence: in rt_mutex_slowunlock()
1436 * raw_spin_unlock(&lock->wait_lock); in rt_mutex_slowunlock()
1437 * if (cmpxchg(&lock->owner, owner, 0) == owner) in rt_mutex_slowunlock()
1442 * lock->owner is serialized by lock->wait_lock: in rt_mutex_slowunlock()
1444 * lock->owner = NULL; in rt_mutex_slowunlock()
1445 * raw_spin_unlock(&lock->wait_lock); in rt_mutex_slowunlock()
1448 /* Drops lock->wait_lock ! */ in rt_mutex_slowunlock()
1452 raw_spin_lock_irqsave(&lock->wait_lock, flags); in rt_mutex_slowunlock()
1459 * Queue the next waiter for wakeup once we release the wait_lock. in rt_mutex_slowunlock()
1462 raw_spin_unlock_irqrestore(&lock->wait_lock, flags); in rt_mutex_slowunlock()
1496 * - the lock owner has been scheduled out in rtmutex_spin_on_owner()
1497 * - current is not longer the top waiter in rtmutex_spin_on_owner()
1498 * - current is requested to reschedule (redundant in rtmutex_spin_on_owner()
1500 * - the VCPU on which owner runs is preempted in rtmutex_spin_on_owner()
1524 * - rtmutex, futex on all kernels
1525 * - mutex and rwsem substitutions on RT kernels
1531 * Must be called with lock->wait_lock held and interrupts disabled. It must
1541 lockdep_assert_held(&lock->wait_lock); in remove_waiter()
1543 raw_spin_lock(¤t->pi_lock); in remove_waiter()
1545 current->pi_blocked_on = NULL; in remove_waiter()
1546 raw_spin_unlock(¤t->pi_lock); in remove_waiter()
1555 raw_spin_lock(&owner->pi_lock); in remove_waiter()
1567 raw_spin_unlock(&owner->pi_lock); in remove_waiter()
1579 raw_spin_unlock_irq(&lock->wait_lock); in remove_waiter()
1584 raw_spin_lock_irq(&lock->wait_lock); in remove_waiter()
1588 * rt_mutex_slowlock_block() - Perform the wait-wake-try-to-take loop
1593 * @timeout: the pre-initialized and started timer, or NULL for none
1594 * @waiter: the pre-initialized rt_mutex_waiter
1596 * Must be called with lock->wait_lock held and interrupts disabled
1613 if (timeout && !timeout->task) { in rt_mutex_slowlock_block()
1614 ret = -ETIMEDOUT; in rt_mutex_slowlock_block()
1618 ret = -EINTR; in rt_mutex_slowlock_block()
1632 raw_spin_unlock_irq(&lock->wait_lock); in rt_mutex_slowlock_block()
1637 raw_spin_lock_irq(&lock->wait_lock); in rt_mutex_slowlock_block()
1649 * If the result is not -EDEADLOCK or the caller requested in rt_mutex_handle_deadlock()
1652 if (res != -EDEADLOCK || detect_deadlock) in rt_mutex_handle_deadlock()
1655 if (build_ww_mutex() && w->ww_ctx) in rt_mutex_handle_deadlock()
1669 * __rt_mutex_slowlock - Locking slowpath invoked with lock::wait_lock held
1686 lockdep_assert_held(&lock->wait_lock); in __rt_mutex_slowlock()
1708 if (!ww_ctx->is_wait_die) in __rt_mutex_slowlock()
1747 * rt_mutex_slowlock - Locking slowpath invoked when fast path fails
1760 * Do all pre-schedule work here, before we queue a waiter and invoke in rt_mutex_slowlock()
1761 * PI -- any such work that trips on rtlock (PREEMPT_RT spinlock) would in rt_mutex_slowlock()
1772 * rtmutex with lock->wait_lock held. But we cannot unconditionally in rt_mutex_slowlock()
1776 raw_spin_lock_irqsave(&lock->wait_lock, flags); in rt_mutex_slowlock()
1778 raw_spin_unlock_irqrestore(&lock->wait_lock, flags); in rt_mutex_slowlock()
1787 lockdep_assert(!current->pi_blocked_on); in __rt_mutex_lock()
1802 * rtlock_slowlock_locked - Slow path lock acquisition for RT locks
1810 lockdep_assert_held(&lock->wait_lock); in rtlock_slowlock_locked()
1833 raw_spin_unlock_irq(&lock->wait_lock); in rtlock_slowlock_locked()
1838 raw_spin_lock_irq(&lock->wait_lock); in rtlock_slowlock_locked()
1859 raw_spin_lock_irqsave(&lock->wait_lock, flags); in rtlock_slowlock()
1861 raw_spin_unlock_irqrestore(&lock->wait_lock, flags); in rtlock_slowlock()