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

[remi at remlab.net]

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.
---
 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