lkml.org 
[lkml]   [2009]   [Oct]   [5]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    Date
    From
    SubjectRe: [RFC] Userspace RCU: (ab)using futexes to save cpu cycles and energy
    * Mathieu Desnoyers (mathieu.desnoyers@polymtl.ca) wrote:
    > (added some CC's, given the length of the answer. Thanks for asking) ;)
    > (Sorry for duplicate, messed up LKML email in original post)
    >
    > * Michael Schnell (mschnell@lumino.de) wrote:
    > > I still don't understand what the advantage of FUTEX is, if the thread
    > > to be waked is always blocked, and thus the fast path is not in use.
    > >
    > > -Michael
    >
    > Hrm, your assumption about the common case does not seem to fit my
    > scenarios. Typically, the wakeup will find the waiter not blocked, and
    > thus skip the call to sys_futex. Here is why.
    >
    > I use this scheme in two different implementations:
    >
    > 1) in call_rcu(), to wake up the worker thread after adding work to the
    > queue.
    >
    > This worker thread, when woken up, sleeps for a few milliseconds before
    > starting to dequeue work. Therefore, if the system is relatively busy,
    > call_rcu() will usually see the worker thread while it's sleeping (and
    > therefore _not_ waiting on the futex). Also, if work is enqueued while
    > the worker thread is executing past RCU callbacks, the worker thread
    > will detect it and won't wait on the futex.
    >
    > Therefore, this is, by design, a very unlikely event to have call_rcu()
    > calling sys_futex.
    >
    > 2) in rcu_read_unlock(), to wake up synchronize_rcu() waiting on past
    > reader's grace periods.
    >
    > Here, synchronize_rcu() busy-waits for the reader's G.P. to end, and if
    > this does not work, after a few attempts (like the pthread mutexes), it
    > adapts and uses sys_futex. The waker only need to call sys_futex if
    > there is a synchronize_rcu() currently running which had to call
    > sys_futex after a few active attempts failed.
    >
    > As you see, in both cases, the common case, "fast path", is to find the
    > futex unlocked and not having to take any lock.
    >
    >
    > Now, about the slow path. I think it's worth discussing too. Indeed,
    > sys_futex takes a per-address spinlock, which happens to serialize all
    > sys_futex operations on the wakeup side. Therefore, for wakeup designs
    > relying on calling sys_futex for wakeup very frequently, this is really
    > bad.
    >
    > There might be ways to mitigate this problem though: changing the
    > sys_futex implementation to use lock-free lists might help.
    >
    > One advantage of calling sys_futex without holding a userspace mutex is
    > that the contention duration on the per-address spinlock is much shorter
    > than the contention on the mutex, because of the system call execution
    > overhead.
    >
    > We could probably turn the sys_futex-dependent locking scheme into
    > something more portable and manage to keep the same fast-path behavior
    > if we replace the way I use sys_futex by a pthread cond var, e.g. :
    >
    > Instead of having:
    >
    >
    > static inline void wake_up_gp(void)
    > {
    > if (unlikely(uatomic_read(&gp_futex) == -1)) {
    > uatomic_set(&gp_futex, 0);
    > futex(&gp_futex, FUTEX_WAKE, 1,
    > NULL, NULL, 0);
    > }
    > }
    >
    > static void wait_gp(void)
    > {
    > uatomic_dec(&gp_futex);
    > smp_mb();
    > if (!num_old_reader_gp()) {
    > smp_mb();
    > atomic_set(&gp_futex, 0);
    > return;
    > }
    > /* Read reader_gp before read futex */
    > smp_rmb();
    > if (uatomic_read(&gp_futex) == -1)
    > futex(&gp_futex, FUTEX_WAIT, -1,
    > NULL, NULL, 0);
    > }
    >
    > We could have:
    >
    > static inline void wake_up_gp(void)
    > {
    > /* just released old reader gp */
    > smp_mb();
    > if (unlikely(uatomic_read(&gp_wait) == -1)) {
    > uatomic_set(&gp_wait, 0);
    > pthread_cond_broadcast(&rcucond);
    > }
    > }
    >
    > static void wait_gp(void)
    > {
    > uatomic_dec(&gp_wait);
    > smp_mb();
    > if (!num_old_reader_gp()) {
    > smp_mb();
    > atomic_set(&gp_wait, 0);
    > goto unlock;
    > }
    > /* Read reader_gp before read futex */
    > smp_rmb();
    > pthread_mutex_lock(&rcumutex);
    > if (uatomic_read(&gp_wait) == -1) {
    > pthread_cond_wait(&rcucond, &rcumutex);
    > pthread_mutex_unlock(&rcumutex);
    > }
    > }
    >
    > Is that what you had in mind ?
    >

    Hrm, thinking about it, the pthread_cond_wait/pthread_cond_broadcast
    scheme I proposed above is racy.

    If a wait_gp executes concurrently with wake_up_gp, we can end up doing:

    gp_wait = 0

    * wait_gp: uatomic_dec(&gp_wait);
    * wait_gp: smp_mb()
    * wait_gp: if (!num_old_reader_gp()) { (false)
    * wait_gp: pthread_mutex_lock(&rcumutex);
    * wait_gp: if (uatomic_read(&gp_wait) == -1) { (true)
    * wake_up_gp: unlikely(uatomic_read(&gp_wait) == -1) { (true)
    * wake_up_gp: uatomic_set(&gp_wait, 0);
    * wait_up_gp: pthread_cond_broadcast(&rcucond);
    * wait_gp: pthread_cond_wait(&rcucond, &rcumutex);

    might wait forever (or until the next wakeup).

    We would need an extra mutex in the wakeup, e.g.:

    static inline void wake_up_gp(void)
    {
    /* just released old reader gp */
    smp_mb();
    if (unlikely(uatomic_read(&gp_wait) == -1)) {
    pthread_mutex_lock(&rcumutex);
    uatomic_set(&gp_wait, 0);
    pthread_cond_broadcast(&rcucond);
    pthread_mutex_unlock(&rcumutex);
    }
    }

    static void wait_gp(void)
    {
    uatomic_dec(&gp_wait);
    smp_mb();
    if (!num_old_reader_gp()) {
    smp_mb();
    atomic_set(&gp_wait, 0);
    goto unlock;
    }
    /* Read reader_gp before read futex */
    smp_rmb();
    pthread_mutex_lock(&rcumutex);
    if (uatomic_read(&gp_wait) == -1) {
    pthread_cond_wait(&rcucond, &rcumutex);
    pthread_mutex_unlock(&rcumutex);
    }
    }

    This should work better, but I'll need to do a formal model to convince
    myself.

    Mathieu

    > Thanks,
    >
    > Mathieu
    >
    > --
    > Mathieu Desnoyers
    > OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68

    --
    Mathieu Desnoyers
    OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F BA06 3F25 A8FE 3BAE 9A68


    \
     
     \ /
      Last update: 2009-10-06 00:31    [W:2.170 / U:0.136 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site