^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 1) ==================================
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 2) RT-mutex subsystem with PI support
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 3) ==================================
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 4)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 5) RT-mutexes with priority inheritance are used to support PI-futexes,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 6) which enable pthread_mutex_t priority inheritance attributes
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 7) (PTHREAD_PRIO_INHERIT). [See Documentation/locking/pi-futex.rst for more details
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 8) about PI-futexes.]
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 9)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 10) This technology was developed in the -rt tree and streamlined for
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 11) pthread_mutex support.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 12)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 13) Basic principles:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 14) -----------------
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 15)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 16) RT-mutexes extend the semantics of simple mutexes by the priority
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 17) inheritance protocol.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 18)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 19) A low priority owner of a rt-mutex inherits the priority of a higher
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 20) priority waiter until the rt-mutex is released. If the temporarily
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 21) boosted owner blocks on a rt-mutex itself it propagates the priority
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 22) boosting to the owner of the other rt_mutex it gets blocked on. The
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 23) priority boosting is immediately removed once the rt_mutex has been
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 24) unlocked.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 25)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 26) This approach allows us to shorten the block of high-prio tasks on
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 27) mutexes which protect shared resources. Priority inheritance is not a
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 28) magic bullet for poorly designed applications, but it allows
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 29) well-designed applications to use userspace locks in critical parts of
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 30) an high priority thread, without losing determinism.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 31)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 32) The enqueueing of the waiters into the rtmutex waiter tree is done in
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 33) priority order. For same priorities FIFO order is chosen. For each
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 34) rtmutex, only the top priority waiter is enqueued into the owner's
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 35) priority waiters tree. This tree too queues in priority order. Whenever
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 36) the top priority waiter of a task changes (for example it timed out or
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 37) got a signal), the priority of the owner task is readjusted. The
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 38) priority enqueueing is handled by "pi_waiters".
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 39)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 40) RT-mutexes are optimized for fastpath operations and have no internal
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 41) locking overhead when locking an uncontended mutex or unlocking a mutex
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 42) without waiters. The optimized fastpath operations require cmpxchg
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 43) support. [If that is not available then the rt-mutex internal spinlock
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 44) is used]
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 45)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 46) The state of the rt-mutex is tracked via the owner field of the rt-mutex
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 47) structure:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 48)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 49) lock->owner holds the task_struct pointer of the owner. Bit 0 is used to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 50) keep track of the "lock has waiters" state:
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 51)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 52) ============ ======= ================================================
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 53) owner bit0 Notes
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 54) ============ ======= ================================================
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 55) NULL 0 lock is free (fast acquire possible)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 56) NULL 1 lock is free and has waiters and the top waiter
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 57) is going to take the lock [1]_
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 58) taskpointer 0 lock is held (fast release possible)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 59) taskpointer 1 lock is held and has waiters [2]_
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 60) ============ ======= ================================================
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 61)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 62) The fast atomic compare exchange based acquire and release is only
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 63) possible when bit 0 of lock->owner is 0.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 64)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 65) .. [1] It also can be a transitional state when grabbing the lock
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 66) with ->wait_lock is held. To prevent any fast path cmpxchg to the lock,
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 67) we need to set the bit0 before looking at the lock, and the owner may
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 68) be NULL in this small time, hence this can be a transitional state.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 69)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 70) .. [2] There is a small time when bit 0 is set but there are no
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 71) waiters. This can happen when grabbing the lock in the slow path.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 72) To prevent a cmpxchg of the owner releasing the lock, we need to
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 73) set this bit before looking at the lock.
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 74)
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 75) BTW, there is still technically a "Pending Owner", it's just not called
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 76) that anymore. The pending owner happens to be the top_waiter of a lock
^8f3ce5b39 (kx 2023-10-28 12:00:06 +0300 77) that has no owner and has been woken up to grab the lock.
Orange Pi5 kernel
Deprecated Linux kernel 5.10.110 for OrangePi 5/5B/5+ boards
3 Commits
0 Branches
0 Tags