[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