Post by Pavel RaiskupI 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 <***@clisp.org>
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 <***@clisp.org>, 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@