Re: Test-lock hang (not 100% reproducible) on GNU/Linux

[Bruno Haible]

Pavel Raiskup wrote:
> I still see infinite hang on ppc64le (sometimes), as discussed in [1].  It
> looks like starvation of writers in test_rwlock().
> 
> Could we set PTHREAD_RWLOCK_PREFER_WRITER_NP (in test-lock.c) to avoid
> those issues?

Here's what I'm pushing.

You were right with your intuition that some _NP API in glibc would help,
but I wanted to first understand the big picture (when writer starvation
can occur, what POSIX says about it, what glibc actually implements,
what PTHREAD_RWLOCK_PREFER_WRITER_NP actually does) and where to apply
the changes (in the test-lock.c source, in the 'lock' module, as a
pthread_rwlock_init override, etc.)


2017-01-05  Bruno Haible  <address@hidden>

        lock: Provide guarantee to avoid writer starvation for rwlocks.
        The rationale is: 1) Read-preferring read-write locks are prone to
        writer starvation if the number of reader threads multiplied by the
        percentage of time they have the lock held is too high. 2) Write-
        preferring read-write locks are the only reliable way to avoid this.
        3) There have been reports of 'test-lock' hanging on glibc systems
        http://lists.gnu.org/archive/html/bug-gnulib/2017-01/msg00009.html,
        and glibc indeed implements read-preferring rwlocks by default, see
        
http://man7.org/linux/man-pages/man3/pthread_rwlockattr_setkind_np.3.html
        and https://sourceware.org/bugzilla/show_bug.cgi?id=13701 .
        * m4/pthread_rwlock_rdlock.m4: New file.
        * m4/lock.m4 (gl_LOCK): Invoke gl_PTHREAD_RWLOCK_RDLOCK_PREFER_WRITER.
        * lib/glthread/lock.h [USE_POSIX_THREADS]: Test
        HAVE_PTHREAD_RWLOCK_RDLOCK_PREFER_WRITER. Use a different implementation
        of rwlock initialization on glibc systems without
        HAVE_PTHREAD_RWLOCK_RDLOCK_PREFER_WRITER. Use a different implementation
        of rwlocks altogether on non-glibc systems without
        HAVE_PTHREAD_RWLOCK_RDLOCK_PREFER_WRITER.
        [USE_PTH_THREADS]: Use a different implementation of rwlocks altogether.
        * lib/glthread/lock.c [USE_POSIX_THREADS]
        (glthread_rwlock_init_for_glibc): New function.
        [USE_POSIX_THREADS] (glthread_rwlock_rdlock_multithreaded): Update
        comment.
        [USE_PTH_THREADS]: New implementation of rwlocks.
        [USE_WINDOWS_THREADS] (glthread_rwlock_rdlock_func): Prefer writers over
        readers.
        * modules/lock (Files): Add m4/pthread_rwlock_rdlock.m4.
        (Depends-on): Add 'extensions'.
        * tests/test-rwlock1.c: New file.
        * lock-tests (Files): Add it.
        (Depends-on): Add usleep.
        (Makefile.am): Add test-rwlock1 to the tests.

diff --git a/m4/pthread_rwlock_rdlock.m4 b/m4/pthread_rwlock_rdlock.m4
new file mode 100644
index 0000000..da69865
--- /dev/null
+++ b/m4/pthread_rwlock_rdlock.m4
@@ -0,0 +1,163 @@
+# pthread_rwlock_rdlock.m4 serial 1
+dnl Copyright (C) 2017 Free Software Foundation, Inc.
+dnl This file is free software; the Free Software Foundation
+dnl gives unlimited permission to copy and/or distribute it,
+dnl with or without modifications, as long as this notice is preserved.
+
+dnl From Bruno Haible.
+dnl Inspired by
+dnl 
https://github.com/linux-test-project/ltp/blob/master/testcases/open_posix_testsuite/conformance/interfaces/pthread_rwlock_rdlock/2-2.c
+dnl by Intel Corporation.
+
+dnl Test whether in a situation where
+dnl   - an rwlock is taken by a reader and has a writer waiting,
+dnl   - an additional reader requests the lock,
+dnl   - the waiting writer and the requesting reader threads have the same
+dnl     priority,
+dnl the requesting reader thread gets blocked, so that at some point the
+dnl waiting writer can acquire the lock.
+dnl Without such a guarantee, when there a N readers and each of the readers
+dnl spends more than 1/Nth of the time with the lock held, there is a high
+dnl probability that the waiting writer will not get the lock in a given finite
+dnl time, a phenomenon called "writer starvation".
+dnl Without such a guarantee, applications have a hard time avoiding writer
+dnl starvation.
+dnl
+dnl POSIX:2008 makes this requirement only for implementations that support TPS
+dnl (Thread Priority Scheduling) and only for the scheduling policies 
SCHED_FIFO
+dnl and SCHED_RR, see
+dnl 
http://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_rwlock_rdlock.html
+dnl but test verifies the guarantee regardless of TPS and regardless of
+dnl scheduling policy.
+AC_DEFUN([gl_PTHREAD_RWLOCK_RDLOCK_PREFER_WRITER],
+[
+  AC_REQUIRE([gl_THREADLIB_EARLY])
+  AC_CACHE_CHECK([whether pthread_rwlock_rdlock prefers a writer to a reader],
+    [gl_cv_pthread_rwlock_rdlock_prefer_writer],
+    [save_LIBS="$LIBS"
+     LIBS="$LIBS $LIBMULTITHREAD"
+     AC_RUN_IFELSE(
+       [AC_LANG_SOURCE([[
+#include <errno.h>
+#include <pthread.h>
+#include <stdlib.h>
+#include <unistd.h>
+
+#define SUCCEED() exit (0)
+#define FAILURE() exit (1)
+#define UNEXPECTED(n) (exit (10 + (n)))
+
+/* The main thread creates the waiting writer and the requesting reader threads
+   in the default way; this guarantees that they have the same priority.
+   We can reuse the main thread as first reader thread.  */
+
+static pthread_rwlock_t lock;
+static pthread_t reader1;
+static pthread_t writer;
+static pthread_t reader2;
+static pthread_t timer;
+/* Used to pass control from writer to reader2 and from reader2 to timer,
+   as in a relay race.
+   Passing control from one running thread to another running thread
+   is most likely faster than to create the second thread.  */
+static pthread_mutex_t baton;
+
+static void *
+timer_func (void *ignored)
+{
+  /* Step 13 (can be before or after step 12):
+     The timer thread takes the baton, then waits a moment to make sure
+     it can tell whether the second reader thread is blocked at step 12.  */
+  if (pthread_mutex_lock (&baton))
+    UNEXPECTED (13);
+  usleep (100000);
+  /* By the time we get here, it's clear that the second reader thread is
+     blocked at step 12.  This is the desired behaviour.  */
+  SUCCEED ();
+}
+
+static void *
+reader2_func (void *ignored)
+{
+  int err;
+
+  /* Step 8 (can be before or after step 7):
+     The second reader thread takes the baton, then waits a moment to make sure
+     the writer thread has reached step 7.  */
+  if (pthread_mutex_lock (&baton))
+    UNEXPECTED (8);
+  usleep (100000);
+  /* Step 9: The second reader thread requests the lock.  */
+  err = pthread_rwlock_tryrdlock (&lock);
+  if (err == 0)
+    FAILURE ();
+  else if (err != EBUSY)
+    UNEXPECTED (9);
+  /* Step 10: Launch a timer, to test whether the next call blocks.  */
+  if (pthread_create (&timer, NULL, timer_func, NULL))
+    UNEXPECTED (10);
+  /* Step 11: Release the baton.  */
+  if (pthread_mutex_unlock (&baton))
+    UNEXPECTED (11);
+  /* Step 12: The second reader thread requests the lock.  */
+  err = pthread_rwlock_rdlock (&lock);
+  if (err == 0)
+    FAILURE ();
+  else
+    UNEXPECTED (12);
+}
+
+static void *
+writer_func (void *ignored)
+{
+  /* Step 4: Take the baton, so that the second reader thread does not go ahead
+     too early.  */
+  if (pthread_mutex_lock (&baton))
+    UNEXPECTED (4);
+  /* Step 5: Create the second reader thread.  */
+  if (pthread_create (&reader2, NULL, reader2_func, NULL))
+    UNEXPECTED (5);
+  /* Step 6: Release the baton.  */
+  if (pthread_mutex_unlock (&baton))
+    UNEXPECTED (6);
+  /* Step 7: The writer thread requests the lock.  */
+  if (pthread_rwlock_wrlock (&lock))
+    UNEXPECTED (7);
+  return NULL;
+}
+
+int
+main ()
+{
+  reader1 = pthread_self ();
+
+  /* Step 1: The main thread initializes the lock and the baton.  */
+  if (pthread_rwlock_init (&lock, NULL))
+    UNEXPECTED (1);
+  if (pthread_mutex_init (&baton, NULL))
+    UNEXPECTED (1);
+  /* Step 2: The main thread acquires the lock as a reader.  */
+  if (pthread_rwlock_rdlock (&lock))
+    UNEXPECTED (2);
+  /* Step 3: Create the writer thread.  */
+  if (pthread_create (&writer, NULL, writer_func, NULL))
+    UNEXPECTED (3);
+  /* Job done.  Go to sleep.  */
+  for (;;)
+    {
+      sleep (1);
+    }
+}
+]])],
+       [gl_cv_pthread_rwlock_rdlock_prefer_writer=yes],
+       [gl_cv_pthread_rwlock_rdlock_prefer_writer=no],
+       [gl_cv_pthread_rwlock_rdlock_prefer_writer="guessing yes"])
+     LIBS="$save_LIBS"
+    ])
+  case "$gl_cv_pthread_rwlock_rdlock_prefer_writer" in
+    *yes)
+      AC_DEFINE([HAVE_PTHREAD_RWLOCK_RDLOCK_PREFER_WRITER], [1],
+        [Define if the 'pthread_rwlock_rdlock' function prefers a writer to a 
reader.])
+      ;;
+  esac
+])
diff --git a/m4/lock.m4 b/m4/lock.m4
index 31aea18..cb04a67 100644
--- a/m4/lock.m4
+++ b/m4/lock.m4
@@ -1,4 +1,4 @@
-# lock.m4 serial 13 (gettext-0.18.2)
+# lock.m4 serial 14
 dnl Copyright (C) 2005-2017 Free Software Foundation, Inc.
 dnl This file is free software; the Free Software Foundation
 dnl gives unlimited permission to copy and/or distribute it,
@@ -12,11 +12,16 @@ AC_DEFUN([gl_LOCK],
   if test "$gl_threads_api" = posix; then
     # OSF/1 4.0 and Mac OS X 10.1 lack the pthread_rwlock_t type and the
     # pthread_rwlock_* functions.
+    has_rwlock=false
     AC_CHECK_TYPE([pthread_rwlock_t],
-      [AC_DEFINE([HAVE_PTHREAD_RWLOCK], [1],
+      [has_rwlock=true
+       AC_DEFINE([HAVE_PTHREAD_RWLOCK], [1],
          [Define if the POSIX multithreading library has read/write locks.])],
       [],
       [#include <pthread.h>])
+    if $has_rwlock; then
+      gl_PTHREAD_RWLOCK_RDLOCK_PREFER_WRITER
+    fi
     # glibc defines PTHREAD_MUTEX_RECURSIVE as enum, not as a macro.
     AC_COMPILE_IFELSE([
       AC_LANG_PROGRAM(
diff --git a/lib/glthread/lock.h b/lib/glthread/lock.h
index 3ea98d6..69f6e31 100644
--- a/lib/glthread/lock.h
+++ b/lib/glthread/lock.h
@@ -176,7 +176,7 @@ typedef pthread_mutex_t gl_lock_t;
 
 /* ------------------------- gl_rwlock_t datatype ------------------------- */
 
-# if HAVE_PTHREAD_RWLOCK
+# if HAVE_PTHREAD_RWLOCK && (HAVE_PTHREAD_RWLOCK_RDLOCK_PREFER_WRITER || 
(__GNU_LIBRARY__ > 1))
 
 #  ifdef PTHREAD_RWLOCK_INITIALIZER
 
@@ -185,10 +185,18 @@ typedef pthread_rwlock_t gl_rwlock_t;
       STORAGECLASS pthread_rwlock_t NAME;
 #   define gl_rwlock_define_initialized(STORAGECLASS, NAME) \
       STORAGECLASS pthread_rwlock_t NAME = gl_rwlock_initializer;
-#   define gl_rwlock_initializer \
-      PTHREAD_RWLOCK_INITIALIZER
-#   define glthread_rwlock_init(LOCK) \
-      (pthread_in_use () ? pthread_rwlock_init (LOCK, NULL) : 0)
+#   if HAVE_PTHREAD_RWLOCK_RDLOCK_PREFER_WRITER
+#    define gl_rwlock_initializer \
+       PTHREAD_RWLOCK_INITIALIZER
+#    define glthread_rwlock_init(LOCK) \
+       (pthread_in_use () ? pthread_rwlock_init (LOCK, NULL) : 0)
+#   else /* glibc with bug 
https://sourceware.org/bugzilla/show_bug.cgi?id=13701 */
+#    define gl_rwlock_initializer \
+       PTHREAD_RWLOCK_WRITER_NONRECURSIVE_INITIALIZER_NP
+#    define glthread_rwlock_init(LOCK) \
+       (pthread_in_use () ? glthread_rwlock_init_for_glibc (LOCK) : 0)
+extern int glthread_rwlock_init_for_glibc (pthread_rwlock_t *lock);
+#   endif
 #   define glthread_rwlock_rdlock(LOCK) \
       (pthread_in_use () ? pthread_rwlock_rdlock (LOCK) : 0)
 #   define glthread_rwlock_wrlock(LOCK) \
@@ -427,6 +435,9 @@ typedef pth_mutex_t gl_lock_t;
 
 /* ------------------------- gl_rwlock_t datatype ------------------------- */
 
+/* Pth pth_rwlock_acquire always prefers readers.  No autoconf test so far.  */
+# if HAVE_PTH_RWLOCK_ACQUIRE_PREFER_WRITER
+
 typedef pth_rwlock_t gl_rwlock_t;
 #  define gl_rwlock_define(STORAGECLASS, NAME) \
      STORAGECLASS pth_rwlock_t NAME;
@@ -445,6 +456,42 @@ typedef pth_rwlock_t gl_rwlock_t;
 #  define glthread_rwlock_destroy(LOCK) \
      ((void)(LOCK), 0)
 
+# else
+
+typedef struct
+        {
+          int initialized;
+          pth_mutex_t lock; /* protects the remaining fields */
+          pth_cond_t waiting_readers; /* waiting readers */
+          pth_cond_t waiting_writers; /* waiting writers */
+          unsigned int waiting_writers_count; /* number of waiting writers */
+          int runcount; /* number of readers running, or -1 when a writer runs 
*/
+        }
+        gl_rwlock_t;
+#  define gl_rwlock_define(STORAGECLASS, NAME) \
+     STORAGECLASS gl_rwlock_t NAME;
+#  define gl_rwlock_define_initialized(STORAGECLASS, NAME) \
+     STORAGECLASS gl_rwlock_t NAME = gl_rwlock_initializer;
+#  define gl_rwlock_initializer \
+     { 0 }
+#  define glthread_rwlock_init(LOCK) \
+     (pth_in_use () ? glthread_rwlock_init_multithreaded (LOCK) : 0)
+#  define glthread_rwlock_rdlock(LOCK) \
+     (pth_in_use () ? glthread_rwlock_rdlock_multithreaded (LOCK) : 0)
+#  define glthread_rwlock_wrlock(LOCK) \
+     (pth_in_use () ? glthread_rwlock_wrlock_multithreaded (LOCK) : 0)
+#  define glthread_rwlock_unlock(LOCK) \
+     (pth_in_use () ? glthread_rwlock_unlock_multithreaded (LOCK) : 0)
+#  define glthread_rwlock_destroy(LOCK) \
+     (pth_in_use () ? glthread_rwlock_destroy_multithreaded (LOCK) : 0)
+extern int glthread_rwlock_init_multithreaded (gl_rwlock_t *lock);
+extern int glthread_rwlock_rdlock_multithreaded (gl_rwlock_t *lock);
+extern int glthread_rwlock_wrlock_multithreaded (gl_rwlock_t *lock);
+extern int glthread_rwlock_unlock_multithreaded (gl_rwlock_t *lock);
+extern int glthread_rwlock_destroy_multithreaded (gl_rwlock_t *lock);
+
+# endif
+
 /* --------------------- gl_recursive_lock_t datatype --------------------- */
 
 /* In Pth, mutexes are recursive by default.  */
diff --git a/lib/glthread/lock.c b/lib/glthread/lock.c
index 6760bbd..061562b 100644
--- a/lib/glthread/lock.c
+++ b/lib/glthread/lock.c
@@ -30,9 +30,38 @@
 
 /* ------------------------- gl_rwlock_t datatype ------------------------- */
 
-# if HAVE_PTHREAD_RWLOCK
+# if HAVE_PTHREAD_RWLOCK && (HAVE_PTHREAD_RWLOCK_RDLOCK_PREFER_WRITER || 
(__GNU_LIBRARY__ > 1))
 
-#  if !defined PTHREAD_RWLOCK_INITIALIZER
+#  ifdef PTHREAD_RWLOCK_INITIALIZER
+
+#   if !HAVE_PTHREAD_RWLOCK_RDLOCK_PREFER_WRITER
+     /* glibc with bug https://sourceware.org/bugzilla/show_bug.cgi?id=13701 */
+
+int
+glthread_rwlock_init_for_glibc (pthread_rwlock_t *lock)
+{
+  pthread_rwlockattr_t attributes;
+  int err;
+
+  err = pthread_rwlockattr_init (&attributes);
+  if (err != 0)
+    return err;
+  /* Note: PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP is the only value that
+     causes the writer to be preferred. PTHREAD_RWLOCK_PREFER_WRITER_NP does 
not
+     do this; see
+     http://man7.org/linux/man-pages/man3/pthread_rwlockattr_setkind_np.3.html 
*/
+  err = pthread_rwlockattr_setkind_np (&attributes,
+                                       
PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP);
+  if (err == 0)
+    err = pthread_rwlock_init(lock, &attributes);
+  /* pthread_rwlockattr_destroy always returns 0.  It cannot influence the
+     return value.  */
+  pthread_rwlockattr_destroy (&attributes);
+  return err;
+}
+
+#   endif
+#  else
 
 int
 glthread_rwlock_init_multithreaded (gl_rwlock_t *lock)
@@ -152,11 +181,9 @@ glthread_rwlock_rdlock_multithreaded (gl_rwlock_t *lock)
   if (err != 0)
     return err;
   /* Test whether only readers are currently running, and whether the runcount
-     field will not overflow.  */
-  /* POSIX says: "It is implementation-defined whether the calling thread
-     acquires the lock when a writer does not hold the lock and there are
-     writers blocked on the lock."  Let's say, no: give the writers a higher
-     priority.  */
+     field will not overflow, and whether no writer is waiting.  The latter
+     condition is because POSIX recommends that "write locks shall take
+     precedence over read locks", to avoid "writer starvation".  */
   while (!(lock->runcount + 1 > 0 && lock->waiting_writers_count == 0))
     {
       /* This thread has to wait for a while.  Enqueue it among the
@@ -481,6 +508,141 @@ glthread_once_singlethreaded (pthread_once_t 
*once_control)
 
 /* ------------------------- gl_rwlock_t datatype ------------------------- */
 
+# if !HAVE_PTH_RWLOCK_ACQUIRE_PREFER_WRITER
+
+int
+glthread_rwlock_init_multithreaded (gl_rwlock_t *lock)
+{
+  if (!pth_mutex_init (&lock->lock))
+    return errno;
+  if (!pth_cond_init (&lock->waiting_readers))
+    return errno;
+  if (!pth_cond_init (&lock->waiting_writers))
+    return errno;
+  lock->waiting_writers_count = 0;
+  lock->runcount = 0;
+  lock->initialized = 1;
+  return 0;
+}
+
+int
+glthread_rwlock_rdlock_multithreaded (gl_rwlock_t *lock)
+{
+  if (!lock->initialized)
+    glthread_rwlock_init_multithreaded (lock);
+  if (!pth_mutex_acquire (&lock->lock, 0, NULL))
+    return errno;
+  /* Test whether only readers are currently running, and whether the runcount
+     field will not overflow, and whether no writer is waiting.  The latter
+     condition is because POSIX recommends that "write locks shall take
+     precedence over read locks", to avoid "writer starvation".  */
+  while (!(lock->runcount + 1 > 0 && lock->waiting_writers_count == 0))
+    {
+      /* This thread has to wait for a while.  Enqueue it among the
+         waiting_readers.  */
+      if (!pth_cond_await (&lock->waiting_readers, &lock->lock, NULL))
+        {
+          int err = errno;
+          pth_mutex_release (&lock->lock);
+          return err;
+        }
+    }
+  lock->runcount++;
+  return (!pth_mutex_release (&lock->lock) ? errno : 0);
+}
+
+int
+glthread_rwlock_wrlock_multithreaded (gl_rwlock_t *lock)
+{
+  if (!lock->initialized)
+    glthread_rwlock_init_multithreaded (lock);
+  if (!pth_mutex_acquire (&lock->lock, 0, NULL))
+    return errno;
+  /* Test whether no readers or writers are currently running.  */
+  while (!(lock->runcount == 0))
+    {
+      /* This thread has to wait for a while.  Enqueue it among the
+         waiting_writers.  */
+      lock->waiting_writers_count++;
+      if (!pth_cond_await (&lock->waiting_writers, &lock->lock, NULL))
+        {
+          int err = errno;
+          lock->waiting_writers_count--;
+          pth_mutex_release (&lock->lock);
+          return err;
+        }
+      lock->waiting_writers_count--;
+    }
+  lock->runcount--; /* runcount becomes -1 */
+  return (!pth_mutex_release (&lock->lock) ? errno : 0);
+}
+
+int
+glthread_rwlock_unlock_multithreaded (gl_rwlock_t *lock)
+{
+  int err;
+
+  if (!lock->initialized)
+    return EINVAL;
+  if (!pth_mutex_acquire (&lock->lock, 0, NULL))
+    return errno;
+  if (lock->runcount < 0)
+    {
+      /* Drop a writer lock.  */
+      if (!(lock->runcount == -1))
+        {
+          pth_mutex_release (&lock->lock);
+          return EINVAL;
+        }
+      lock->runcount = 0;
+    }
+  else
+    {
+      /* Drop a reader lock.  */
+      if (!(lock->runcount > 0))
+        {
+          pth_mutex_release (&lock->lock);
+          return EINVAL;
+        }
+      lock->runcount--;
+    }
+  if (lock->runcount == 0)
+    {
+      /* POSIX recommends that "write locks shall take precedence over read
+         locks", to avoid "writer starvation".  */
+      if (lock->waiting_writers_count > 0)
+        {
+          /* Wake up one of the waiting writers.  */
+          if (!pth_cond_notify (&lock->waiting_writers, FALSE))
+            {
+              int err = errno;
+              pth_mutex_release (&lock->lock);
+              return err;
+            }
+        }
+      else
+        {
+          /* Wake up all waiting readers.  */
+          if (!pth_cond_notify (&lock->waiting_readers, TRUE))
+            {
+              int err = errno;
+              pth_mutex_release (&lock->lock);
+              return err;
+            }
+        }
+    }
+  return (!pth_mutex_release (&lock->lock) ? errno : 0);
+}
+
+int
+glthread_rwlock_destroy_multithreaded (gl_rwlock_t *lock)
+{
+  lock->initialized = 0;
+  return 0;
+}
+
+# endif
+
 /* --------------------- gl_recursive_lock_t datatype --------------------- */
 
 /* -------------------------- gl_once_t datatype -------------------------- */
@@ -796,8 +958,10 @@ glthread_rwlock_rdlock_func (gl_rwlock_t *lock)
     }
   EnterCriticalSection (&lock->lock);
   /* Test whether only readers are currently running, and whether the runcount
-     field will not overflow.  */
-  if (!(lock->runcount + 1 > 0))
+     field will not overflow, and whether no writer is waiting.  The latter
+     condition is because POSIX recommends that "write locks shall take
+     precedence over read locks", to avoid "writer starvation".  */
+  if (!(lock->runcount + 1 > 0 && lock->waiting_writers.count == 0))
     {
       /* This thread has to wait for a while.  Enqueue it among the
          waiting_readers.  */
diff --git a/modules/lock b/modules/lock
index 1231399..dafeeeb 100644
--- a/modules/lock
+++ b/modules/lock
@@ -5,8 +5,10 @@ Files:
 lib/glthread/lock.h
 lib/glthread/lock.c
 m4/lock.m4
+m4/pthread_rwlock_rdlock.m4
 
 Depends-on:
+extensions
 threadlib
 
 configure.ac:
diff --git a/tests/test-rwlock1.c b/tests/test-rwlock1.c
new file mode 100644
index 0000000..66dfa7b
--- /dev/null
+++ b/tests/test-rwlock1.c
@@ -0,0 +1,157 @@
+/* Test of glthread_rwlock_rdlock function.
+   Copyright (C) 2017 Free Software Foundation, Inc.
+
+   This program is free software: you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; either version 3 of the License, or
+   (at your option) any later version.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+/* Written by Bruno Haible <address@hidden>, 2005.
+   Inspired by
+   
https://github.com/linux-test-project/ltp/blob/master/testcases/open_posix_testsuite/conformance/interfaces/pthread_rwlock_rdlock/2-2.c
+   by Intel Corporation.  */
+
+#include <config.h>
+
+#include "glthread/lock.h"
+
+#include <errno.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+
+#include "glthread/thread.h"
+#include "glthread/yield.h"
+
+/* Verify that in a situation where
+     - an rwlock is taken by a reader and has a writer waiting,
+     - an additional reader requests the lock,
+     - the waiting writer and the requesting reader threads have the same
+       priority,
+   the requesting reader thread gets blocked, so that at some point the
+   waiting writer can acquire the lock.
+   Without such a guarantee, when there a N readers and each of the readers
+   spends more than 1/Nth of the time with the lock held, there is a high
+   probability that the waiting writer will not get the lock in a given finite
+   time, a phenomenon called "writer starvation".
+   Without such a guarantee, applications have a hard time avoiding writer
+   starvation.
+
+   POSIX:2008 makes this requirement only for implementations that support TPS
+   (Thread Priority Scheduling) and only for the scheduling policies SCHED_FIFO
+   and SCHED_RR, see
+   
http://pubs.opengroup.org/onlinepubs/9699919799/functions/pthread_rwlock_rdlock.html
+   but test verifies the guarantee regardless of TPS and regardless of
+   scheduling policy.  */
+
+#define SUCCEED() exit (0)
+#define FAILURE() exit (1)
+#define UNEXPECTED(n) (fprintf (stderr, "Unexpected outcome %d\n", n), abort 
())
+
+/* The main thread creates the waiting writer and the requesting reader threads
+   in the default way; this guarantees that they have the same priority.
+   We can reuse the main thread as first reader thread.  */
+
+static gl_rwlock_t lock;
+static gl_thread_t reader1;
+static gl_thread_t writer;
+static gl_thread_t reader2;
+static gl_thread_t timer;
+/* Used to pass control from writer to reader2 and from reader2 to timer,
+   as in a relay race.
+   Passing control from one running thread to another running thread
+   is most likely faster than to create the second thread.  */
+static gl_lock_t baton;
+
+static void *
+timer_func (void *ignored)
+{
+  /* Step 13 (can be before or after step 12):
+     The timer thread takes the baton, then waits a moment to make sure
+     it can tell whether the second reader thread is blocked at step 12.  */
+  if (glthread_lock_lock (&baton))
+    UNEXPECTED (13);
+  usleep (100000);
+  /* By the time we get here, it's clear that the second reader thread is
+     blocked at step 12.  This is the desired behaviour.  */
+  SUCCEED ();
+}
+
+static void *
+reader2_func (void *ignored)
+{
+  int err;
+
+  /* Step 8 (can be before or after step 7):
+     The second reader thread takes the baton, then waits a moment to make sure
+     the writer thread has reached step 7.  */
+  if (glthread_lock_lock (&baton))
+    UNEXPECTED (8);
+  usleep (100000);
+  /* Step 9 omitted.  */
+  /* Step 10: Launch a timer, to test whether the next call blocks.  */
+  if (glthread_create (&timer, timer_func, NULL))
+    UNEXPECTED (10);
+  /* Step 11: Release the baton.  */
+  if (glthread_lock_unlock (&baton))
+    UNEXPECTED (11);
+  /* Step 12: The second reader thread requests the lock.  */
+  err = glthread_rwlock_rdlock (&lock);
+  if (err == 0)
+    FAILURE ();
+  else
+    UNEXPECTED (12);
+}
+
+static void *
+writer_func (void *ignored)
+{
+  /* Step 4: Take the baton, so that the second reader thread does not go ahead
+     too early.  */
+  if (glthread_lock_lock (&baton))
+    UNEXPECTED (4);
+  /* Step 5: Create the second reader thread.  */
+  if (glthread_create (&reader2, reader2_func, NULL))
+    UNEXPECTED (5);
+  /* Step 6: Release the baton.  */
+  if (glthread_lock_unlock (&baton))
+    UNEXPECTED (6);
+  /* Step 7: The writer thread requests the lock.  */
+  if (glthread_rwlock_wrlock (&lock))
+    UNEXPECTED (7);
+  return NULL;
+}
+
+int
+main ()
+{
+  reader1 = gl_thread_self ();
+
+  /* Step 1: The main thread initializes the lock and the baton.  */
+  if (glthread_rwlock_init (&lock))
+    UNEXPECTED (1);
+  if (glthread_lock_init (&baton))
+    UNEXPECTED (1);
+  /* Step 2: The main thread acquires the lock as a reader.  */
+  if (glthread_rwlock_rdlock (&lock))
+    UNEXPECTED (2);
+  /* Step 3: Create the writer thread.  */
+  if (glthread_create (&writer, writer_func, NULL))
+    UNEXPECTED (3);
+  /* Job done.  Go to sleep.  */
+  for (;;)
+    {
+      /* In cooperative threads implementations (Pth), give other threads
+         a chance to run.  */
+      gl_thread_yield ();
+      sleep (1);
+    }
+}
diff --git a/modules/lock-tests b/modules/lock-tests
index d0e5010..b42740c 100644
--- a/modules/lock-tests
+++ b/modules/lock-tests
@@ -1,13 +1,16 @@
 Files:
+tests/test-rwlock1.c
 tests/test-lock.c
 
 Depends-on:
 thread
+usleep
 yield
 
 configure.ac:
 
 Makefile.am:
-TESTS += test-lock
-check_PROGRAMS += test-lock
+TESTS += test-rwlock1 test-lock
+check_PROGRAMS += test-rwlock1 test-lock
+test_rwlock1_LDADD = $(LDADD) @LIBMULTITHREAD@
 test_lock_LDADD = $(LDADD) @LIBMULTITHREAD@ @YIELD_LIB@