133 lines · plain
1================2Futex Requeue PI3================4 5Requeueing of tasks from a non-PI futex to a PI futex requires6special handling in order to ensure the underlying rt_mutex is never7left without an owner if it has waiters; doing so would break the PI8boosting logic [see rt-mutex-design.rst] For the purposes of9brevity, this action will be referred to as "requeue_pi" throughout10this document. Priority inheritance is abbreviated throughout as11"PI".12 13Motivation14----------15 16Without requeue_pi, the glibc implementation of17pthread_cond_broadcast() must resort to waking all the tasks waiting18on a pthread_condvar and letting them try to sort out which task19gets to run first in classic thundering-herd formation. An ideal20implementation would wake the highest-priority waiter, and leave the21rest to the natural wakeup inherent in unlocking the mutex22associated with the condvar.23 24Consider the simplified glibc calls::25 26 /* caller must lock mutex */27 pthread_cond_wait(cond, mutex)28 {29 lock(cond->__data.__lock);30 unlock(mutex);31 do {32 unlock(cond->__data.__lock);33 futex_wait(cond->__data.__futex);34 lock(cond->__data.__lock);35 } while(...)36 unlock(cond->__data.__lock);37 lock(mutex);38 }39 40 pthread_cond_broadcast(cond)41 {42 lock(cond->__data.__lock);43 unlock(cond->__data.__lock);44 futex_requeue(cond->data.__futex, cond->mutex);45 }46 47Once pthread_cond_broadcast() requeues the tasks, the cond->mutex48has waiters. Note that pthread_cond_wait() attempts to lock the49mutex only after it has returned to user space. This will leave the50underlying rt_mutex with waiters, and no owner, breaking the51previously mentioned PI-boosting algorithms.52 53In order to support PI-aware pthread_condvar's, the kernel needs to54be able to requeue tasks to PI futexes. This support implies that55upon a successful futex_wait system call, the caller would return to56user space already holding the PI futex. The glibc implementation57would be modified as follows::58 59 60 /* caller must lock mutex */61 pthread_cond_wait_pi(cond, mutex)62 {63 lock(cond->__data.__lock);64 unlock(mutex);65 do {66 unlock(cond->__data.__lock);67 futex_wait_requeue_pi(cond->__data.__futex);68 lock(cond->__data.__lock);69 } while(...)70 unlock(cond->__data.__lock);71 /* the kernel acquired the mutex for us */72 }73 74 pthread_cond_broadcast_pi(cond)75 {76 lock(cond->__data.__lock);77 unlock(cond->__data.__lock);78 futex_requeue_pi(cond->data.__futex, cond->mutex);79 }80 81The actual glibc implementation will likely test for PI and make the82necessary changes inside the existing calls rather than creating new83calls for the PI cases. Similar changes are needed for84pthread_cond_timedwait() and pthread_cond_signal().85 86Implementation87--------------88 89In order to ensure the rt_mutex has an owner if it has waiters, it90is necessary for both the requeue code, as well as the waiting code,91to be able to acquire the rt_mutex before returning to user space.92The requeue code cannot simply wake the waiter and leave it to93acquire the rt_mutex as it would open a race window between the94requeue call returning to user space and the waiter waking and95starting to run. This is especially true in the uncontended case.96 97The solution involves two new rt_mutex helper routines,98rt_mutex_start_proxy_lock() and rt_mutex_finish_proxy_lock(), which99allow the requeue code to acquire an uncontended rt_mutex on behalf100of the waiter and to enqueue the waiter on a contended rt_mutex.101Two new system calls provide the kernel<->user interface to102requeue_pi: FUTEX_WAIT_REQUEUE_PI and FUTEX_CMP_REQUEUE_PI.103 104FUTEX_WAIT_REQUEUE_PI is called by the waiter (pthread_cond_wait()105and pthread_cond_timedwait()) to block on the initial futex and wait106to be requeued to a PI-aware futex. The implementation is the107result of a high-speed collision between futex_wait() and108futex_lock_pi(), with some extra logic to check for the additional109wake-up scenarios.110 111FUTEX_CMP_REQUEUE_PI is called by the waker112(pthread_cond_broadcast() and pthread_cond_signal()) to requeue and113possibly wake the waiting tasks. Internally, this system call is114still handled by futex_requeue (by passing requeue_pi=1). Before115requeueing, futex_requeue() attempts to acquire the requeue target116PI futex on behalf of the top waiter. If it can, this waiter is117woken. futex_requeue() then proceeds to requeue the remaining118nr_wake+nr_requeue tasks to the PI futex, calling119rt_mutex_start_proxy_lock() prior to each requeue to prepare the120task as a waiter on the underlying rt_mutex. It is possible that121the lock can be acquired at this stage as well, if so, the next122waiter is woken to finish the acquisition of the lock.123 124FUTEX_CMP_REQUEUE_PI accepts nr_wake and nr_requeue as arguments, but125their sum is all that really matters. futex_requeue() will wake or126requeue up to nr_wake + nr_requeue tasks. It will wake only as many127tasks as it can acquire the lock for, which in the majority of cases128should be 0 as good programming practice dictates that the caller of129either pthread_cond_broadcast() or pthread_cond_signal() acquire the130mutex prior to making the call. FUTEX_CMP_REQUEUE_PI requires that131nr_wake=1. nr_requeue should be INT_MAX for broadcast and 0 for132signal.133