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