[vlc-devel] [PATCH 2/3] threads: rewrite R/W lock to avoid contention

Steve Lhomme robux4 at ycbcr.xyz
Wed Jan 13 07:28:23 UTC 2021


On 2021-01-12 18:30, remi at remlab.net wrote:
> From: RĂ©mi Denis-Courmont <remi at remlab.net>
> 
> The current implementation would cause threads to sleep upon concurrent
> read lock/unlock. This fixes that. Sleeping now only occurs when writers
> are involved.

I suppose the goal is to make reading lock-free. But there's a slight 
difference in the unlock part.

* Before: Let reader and writer compete. OS scheduler decides who wins.
* After: Wake waiting readers, then Wake one waiting writer

So now the reader always get priority over the writer ? Is it possible 
that a fast reader (and lock-free) will never let the writer be in charge ?

Also you don't need to forward declare vlc_rwlock_tryrdlock, just move 
the definition.

> ---
>   include/vlc_threads.h | 17 +++++++--
>   src/misc/threads.c    | 88 +++++++++++++++++++++++++------------------
>   2 files changed, 65 insertions(+), 40 deletions(-)
> 
> diff --git a/include/vlc_threads.h b/include/vlc_threads.h
> index 2054e632f0..0004ee0ef0 100644
> --- a/include/vlc_threads.h
> +++ b/include/vlc_threads.h
> @@ -532,15 +532,26 @@ VLC_API int vlc_sem_timedwait(vlc_sem_t *sem, vlc_tick_t deadline) VLC_USED;
>    */
>   typedef struct vlc_rwlock
>   {
> +    union {
> +#ifndef __cplusplus
> +        struct {
> +            atomic_uint state;
> +            atomic_uint wait;
> +        };
> +#endif
> +        struct {
> +            unsigned state;
> +            unsigned wait;
> +        } dummy;
> +    };
>       vlc_mutex_t   mutex;
> -    vlc_cond_t    wait;
> -    long          state;
>   } vlc_rwlock_t;
>   
>   /**
>    * Static initializer for (static) read/write lock.
>    */
> -#define VLC_STATIC_RWLOCK { VLC_STATIC_MUTEX, VLC_STATIC_COND, 0 }
> +#define VLC_STATIC_RWLOCK \
> +    { { { ATOMIC_VAR_INIT(0), ATOMIC_VAR_INIT(0) } }, VLC_STATIC_MUTEX }
>   
>   /**
>    * Initializes a read/write lock.
> diff --git a/src/misc/threads.c b/src/misc/threads.c
> index 76c7049f00..a1da0edae5 100644
> --- a/src/misc/threads.c
> +++ b/src/misc/threads.c
> @@ -373,22 +373,16 @@ int vlc_cond_timedwait_daytime(vlc_cond_t *cond, vlc_mutex_t *mutex,
>   }
>   
>   /*** Generic read/write locks ***/
> -/* NOTE:
> - * lock->state is a signed long integer:
> - *  - The sign bit is set when the lock is held for writing.
> - *  - The other bits code the number of times the lock is held for reading.
> - * Consequently:
> - *  - The value is negative if and only if the lock is held for writing.
> - *  - The value is zero if and only if the lock is not held at all.
> +/* vlc_rwlock_t::state counts the number of outstanding read-side locks.
> + * UINT_MAX means lock is held for writing.
>    */
> -#define READER_MASK LONG_MAX
> -#define WRITER_BIT  LONG_MIN
> +static int vlc_rwlock_tryrdlock(vlc_rwlock_t *lock);
>   
>   void vlc_rwlock_init (vlc_rwlock_t *lock)
>   {
> +    atomic_init(&lock->state, 0);
> +    atomic_init(&lock->wait, 0);
>       vlc_mutex_init (&lock->mutex);
> -    vlc_cond_init (&lock->wait);
> -    lock->state = 0;
>   }
>   
>   void vlc_rwlock_destroy (vlc_rwlock_t *lock)
> @@ -398,48 +392,68 @@ void vlc_rwlock_destroy (vlc_rwlock_t *lock)
>   
>   void vlc_rwlock_rdlock (vlc_rwlock_t *lock)
>   {
> -    vlc_mutex_lock (&lock->mutex);
> -    /* Recursive read-locking is allowed.
> -     * Ensure that there is no active writer. */
> -    while (lock->state < 0)
> -    {
> -        assert (lock->state == WRITER_BIT);
> -        vlc_cond_wait (&lock->wait, &lock->mutex);
> -    }
> -    if (unlikely(lock->state >= READER_MASK))
> +    while (vlc_rwlock_tryrdlock(lock))
> +        vlc_atomic_wait(&lock->state, UINT_MAX);
> +}
> +
> +static int vlc_rwlock_tryrdlock(vlc_rwlock_t *lock)
> +{
> +    unsigned state = atomic_load_explicit(&lock->state, memory_order_relaxed);
> +
> +    do
> +        if (state == UINT_MAX)
> +            return EBUSY;
> +    while (!atomic_compare_exchange_weak_explicit(&lock->state, &state,
> +                                                  state + 1,
> +                                                  memory_order_acquire,
> +                                                  memory_order_relaxed));
> +
> +    if (unlikely(state == UINT_MAX - 1))
>           abort (); /* An overflow is certainly a recursion bug. */
> -    lock->state++;
> -    vlc_mutex_unlock (&lock->mutex);
> +
> +    return 0;
>   }
>   
>   void vlc_rwlock_wrlock (vlc_rwlock_t *lock)
>   {
>       vlc_mutex_lock (&lock->mutex);
> -    /* Wait until nobody owns the lock in any way. */
> -    while (lock->state != 0)
> -        vlc_cond_wait (&lock->wait, &lock->mutex);
> -    lock->state = WRITER_BIT;
> -    vlc_mutex_unlock (&lock->mutex);
> +
> +    for (;;) {
> +        unsigned exp = 0;
> +
> +        atomic_store_explicit(&lock->wait, 1, memory_order_seq_cst);
> +
> +        if (atomic_compare_exchange_strong_explicit(&lock->state, &exp,
> +                                                    UINT_MAX,
> +                                                    memory_order_acquire,
> +                                                    memory_order_relaxed))
> +            break;
> +
> +        vlc_atomic_wait(&lock->wait, 1);
> +    }
>   }
>   
>   void vlc_rwlock_unlock (vlc_rwlock_t *lock)
>   {
> -    vlc_mutex_lock (&lock->mutex);
> -    if (lock->state < 0)
> +    unsigned state = atomic_load_explicit(&lock->state, memory_order_relaxed);
> +
> +    if (state == UINT_MAX)
>       {   /* Write unlock */
> -        assert (lock->state == WRITER_BIT);
> -        /* Let reader and writer compete. OS scheduler decides who wins. */
> -        lock->state = 0;
> -        vlc_cond_broadcast (&lock->wait);
> +        atomic_store_explicit(&lock->wait, 0, memory_order_relaxed);
> +        atomic_store_explicit(&lock->state, 0, memory_order_release);
> +        vlc_atomic_notify_all(&lock->state); /* Wake waiting readers */
> +        vlc_mutex_unlock(&lock->mutex); /* Wake one waiting writer */
>       }
>       else
>       {   /* Read unlock */
> -        assert (lock->state > 0);
> +        assert(state != 0);
> +
>           /* If there are no readers left, wake up one pending writer. */
> -        if (--lock->state == 0)
> -            vlc_cond_signal (&lock->wait);
> +        if (atomic_fetch_sub_explicit(&lock->state, 1,
> +                                      memory_order_acq_rel) == 1
> +         && atomic_exchange_explicit(&lock->wait, 0, memory_order_seq_cst))
> +            vlc_atomic_notify_one(&lock->wait);
>       }
> -    vlc_mutex_unlock (&lock->mutex);
>   }
>   
>   /*** Generic semaphores ***/
> -- 
> 2.30.0
> 
> _______________________________________________
> vlc-devel mailing list
> To unsubscribe or modify your subscription options:
> https://mailman.videolan.org/listinfo/vlc-devel
> 


More information about the vlc-devel mailing list