Re: [tip PATCH v7 0/9] RFC: futex: requeue pi implementation

[Vernon Mauery <vernux@us.ibm.com>]

Darren Hart wrote:
> Thomas Gleixner wrote:
>> Darren,
>>
>> On Fri, 3 Apr 2009, Darren Hart wrote:
[snip]
>> Darren, could you please polish the initial design notes - especially
>> point out the subtle differences between requeue and requeue_pi - and
>> send them into the thread? That might help Uli and Jakub and we
>> definitly want to have that info preserved in Documentation/ as well.
> 
> I'll be away most of the day so I've whipped something up quickly in
> order to get discussion started.  It is probably a little heavy on the
> glibc details and a little light on the kernel details for inclusion in
> Documentation/.  Please review for high-level content and let me know
> what you would like to see more or less of.  I'll pick this back up
> tomorrow to incorporate any suggestions and flesh out the kernel details
> a bit more.
> 

Darren,

A gentle review of your documentation follows.

> 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-desgin.txt]  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 current implementation of pthread_cond_broadcast()
> must resort to waking all the tasks waiting on a pthread_condvar and letting
> them try and sort out which task gets to run first in classic thundering-herd
       ^try to sort out^
> formation.  An ideal implementation would wake the highest priority waiter,
                                                     ^highest-priority^
> 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 userspace.  This will leave the underlying rt_mutex with waiters,
> and no owner, breaking the previously mentioned PI boosting algorithms.
                                                  ^PI-boosting^
> 
> 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 userspace already holding
> the PI futex.  As such the glibc implemenation would be modified as follows:
                                   ^implementation^
> 
> 
> /* 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);
>        /* the kernel acquired the the mutex for us */
> }
> 
> pthread_cond_broadcast_pi(cond)
> {
>     lock(cond->__data.__lock);
>     unlock(cond->__data.__lock);
>     futex_requeue_pi(cond->data.__futex, cond->mutex);
> }
> 
> The actual glibc implemenation will likely test for PI and make the
                   ^implementation^

> necessary changes inside the existing calls rather than creating new calls
> for the PI cases.  Similar changes are needed for pthread_cond_timedwait()
> and pthread_cond_signal().
> 
> Implementation
> --------------
> 
> In order to ensure the rt_mutex has an owner if it has waiters, it is necessary
> for the both the requeue code as well as the waiting code to be able to acquire
> the rt_mutex before returning to userspace (the requeue code cannot simply wake

I would suggest not using a parenthetical expression here because of the length
of the enclosed sentence.  Also, you have a missing right parenthesis.

> the waiter and leave it to acquire the rt_mutex as it would open a race window
> between the requeue call returning to userspace and the waiter waking and
> starting to run.  This is especially true in the uncontended case.
> 
> To accomplish this, rt_mutex lock acquistion has to be able to be accomlished
                                    ^acquisition^                   ^accomplished^
> vicariously by the requeue code on behalf of the waiter.  This is accomplished

Lots of accomplishing going on here^^^.  And one is missing a its p.  Maybe
rewritten as:

To accomplish this, the rt_mutex lock must be acquired vicariously by the
requeue code on behalf of the waiter.  This is done by two new rt_mutex
helper routines: rt_mutex_start_proxy_lock(), called by he requeue code;
and rt_mutex_finish_proxy_lock(), called by the waiter upon wakeup.

> via two new rt_mutex helper routines: rt_mutex_start_proxy_lock() (called by
 > the requeue code) and rt_mutex_finish_proxy_lock(), called by the waiter upon
> wakeup.

I also changed the punctuation there to remove the parenthetical expression
modifying the first function, where only a comma was used on the second.  Too
many commas and modifications made me think that maybe a semicolon would work
well.

> 
> Two new system calls provide the kernel<->userspace interface to requeue_pi:
> FUTEX_WAIT_REQUEUE_PI and FUTEX_REQUEUE_PI (and FUTEX_CMP_REQUEUE_PI).
> 
> FUTEX_WAIT_REQUEUE_PI is called by the waiter (pthread_cond_wait() and
> pthread_cond_timedwait()) to block on the initial futex and wait to be requeued
> to a PI aware futex.  The implemenation is basically the result of a high speed
       ^PI-aware^           ^implementation^                           ^high-speed^
> collision between futex_wait() and futex_lock_pi(), with some extra logic to
> check for the additional wake-up scenarios.
> 
> FUTEX_REQUEUE_PI is called by the waker (pthread_cond_broadcast() and
> pthread_cond_signal()) to requeue and possibly wake the waiting tasks.
> Internally, this system call is still handled by futex_requeue (by passing
> requeue_pi=1).  Before requeueing, futex_requeue() attempts to acquire the
> requeue target PI futex on behalf of the top waiter, if it can, this waiter is
                                                     ^.  If^
> woken.  It then proceeds to requeue the remaining nr_wake+nr_requeue tasks to
> the PI futex.  It calls rt_mutex_start_proxy_lock() prior to each requeue to
> prepare the task as a waiter on the underlying rt_mutex.  It is possible that
> the lock can be acquired at this stage as well, if so, the next waiter is woken
                                                ^.  If^
> to finish the acquisition of the lock.  FUTEX_REQUEUE_PI accepts nr_wake and
> nr_requeue as arguments, but their sum is all that really matters.  It will

Lots of 'It' by this point.  Maybe replacing 'it' with a proper noun a couple
of times would help make sure we are all on the same page.

> wake or requeue up to nr_wake + nr_requeue tasks.  It will wake only as many
> tasks as it can acquire the lock for, which in the majority of cases should be
> 0 as good programming practice dictates that the caller of either
  ^0, as^
> pthread_cond_broadcast() or pthread_cond_signal() acquire the mutex prior to
> making the call.  FUTEX_REQUEUE_PI requires that nr_wake=1.  nr_requeue should
> be INT_MAX for broadcast and 0 for signal.

One final point is that generally numbers less than ten are spelled out, but
since this is a technical document where we see things like nr_wake=1, I figured
it would look more consistent to let those 0s slide.

Keep in mind that I am not really an editor so take my changes with a grain of
salt. (I am only *married* to an editor and if she gets wind that I am
pretending to be one on the side I will be in big trouble :)

--Vernon