Documentation/locking/futex-requeue-pi.rst

Source file repositories/reference/linux-study-clean/Documentation/locking/futex-requeue-pi.rst

File Facts

System
Linux kernel
Corpus path
Documentation/locking/futex-requeue-pi.rst
Extension
.rst
Size
5189 bytes
Lines
133
Domain
Support Tooling And Documentation
Bucket
Documentation
Inferred role
Support Tooling And Documentation: documentation
Status
atlas-only

Why This File Exists

Repository support layer: documentation, build tooling, samples, user-space helper tools, generated initramfs support, licenses, and validation utilities.

Dependency Surface

Detected Declarations

Annotated Snippet

================
Futex Requeue PI
================

Requeueing of tasks from a non-PI futex to a PI futex requires
special handling in order to ensure the underlying rt_mutex is never
left without an owner if it has waiters; doing so would break the PI
boosting logic [see rt-mutex-design.rst] For the purposes of
brevity, this action will be referred to as "requeue_pi" throughout
this document.  Priority inheritance is abbreviated throughout as
"PI".

Motivation
----------

Without requeue_pi, the glibc implementation of
pthread_cond_broadcast() must resort to waking all the tasks waiting
on a pthread_condvar and letting them try to sort out which task
gets to run first in classic thundering-herd formation.  An ideal
implementation would wake the highest-priority waiter, and leave the
rest to the natural wakeup inherent in unlocking the mutex
associated with the condvar.

Consider the simplified glibc calls::

	/* caller must lock mutex */
	pthread_cond_wait(cond, mutex)
	{
		lock(cond->__data.__lock);
		unlock(mutex);
		do {
		unlock(cond->__data.__lock);
		futex_wait(cond->__data.__futex);
		lock(cond->__data.__lock);
		} while(...)
		unlock(cond->__data.__lock);
		lock(mutex);
	}

	pthread_cond_broadcast(cond)
	{
		lock(cond->__data.__lock);
		unlock(cond->__data.__lock);
		futex_requeue(cond->data.__futex, cond->mutex);
	}

Once pthread_cond_broadcast() requeues the tasks, the cond->mutex
has waiters. Note that pthread_cond_wait() attempts to lock the
mutex only after it has returned to user space.  This will leave the
underlying rt_mutex with waiters, and no owner, breaking the
previously mentioned PI-boosting algorithms.

In order to support PI-aware pthread_condvar's, the kernel needs to
be able to requeue tasks to PI futexes.  This support implies that
upon a successful futex_wait system call, the caller would return to
user space already holding the PI futex.  The glibc implementation
would be modified as follows::


	/* caller must lock mutex */
	pthread_cond_wait_pi(cond, mutex)
	{
		lock(cond->__data.__lock);
		unlock(mutex);
		do {
		unlock(cond->__data.__lock);
		futex_wait_requeue_pi(cond->__data.__futex);
		lock(cond->__data.__lock);
		} while(...)
		unlock(cond->__data.__lock);

Annotation

Implementation Notes