New pthread rwlock that is more scalable.

This replaces the pthread rwlock with a new implementation that uses a
more scalable algorithm (primarily through not using a critical section
anymore to make state changes).  The fast path for rdlock acquisition and
release is now basically a single atomic read-modify write or CAS and a few
branches.  See nptl/pthread_rwlock_common.c for details.

	* nptl/DESIGN-rwlock.txt: Remove.
	* nptl/lowlevelrwlock.sym: Remove.
	* nptl/Makefile: Add new tests.
	* nptl/pthread_rwlock_common.c: New file.  Contains the new rwlock.
	* nptl/pthreadP.h (PTHREAD_RWLOCK_PREFER_READER_P): Remove.
	(PTHREAD_RWLOCK_WRPHASE, PTHREAD_RWLOCK_WRLOCKED,
	PTHREAD_RWLOCK_RWAITING, PTHREAD_RWLOCK_READER_SHIFT,
	PTHREAD_RWLOCK_READER_OVERFLOW, PTHREAD_RWLOCK_WRHANDOVER,
	PTHREAD_RWLOCK_FUTEX_USED): New.
	* nptl/pthread_rwlock_init.c (__pthread_rwlock_init): Adapt to new
	implementation.
	* nptl/pthread_rwlock_rdlock.c (__pthread_rwlock_rdlock_slow): Remove.
	(__pthread_rwlock_rdlock): Adapt.
	* nptl/pthread_rwlock_timedrdlock.c
	(pthread_rwlock_timedrdlock): Adapt.
	* nptl/pthread_rwlock_timedwrlock.c
	(pthread_rwlock_timedwrlock): Adapt.
	* nptl/pthread_rwlock_trywrlock.c (pthread_rwlock_trywrlock): Adapt.
	* nptl/pthread_rwlock_tryrdlock.c (pthread_rwlock_tryrdlock): Adapt.
	* nptl/pthread_rwlock_unlock.c (pthread_rwlock_unlock): Adapt.
	* nptl/pthread_rwlock_wrlock.c (__pthread_rwlock_wrlock_slow): Remove.
	(__pthread_rwlock_wrlock): Adapt.
	* nptl/tst-rwlock10.c: Adapt.
	* nptl/tst-rwlock11.c: Adapt.
	* nptl/tst-rwlock17.c: New file.
	* nptl/tst-rwlock18.c: New file.
	* nptl/tst-rwlock19.c: New file.
	* nptl/tst-rwlock2b.c: New file.
	* nptl/tst-rwlock8.c: Adapt.
	* nptl/tst-rwlock9.c: Adapt.
	* sysdeps/aarch64/nptl/bits/pthreadtypes.h (pthread_rwlock_t): Adapt.
	* sysdeps/arm/nptl/bits/pthreadtypes.h (pthread_rwlock_t): Adapt.
	* sysdeps/hppa/nptl/bits/pthreadtypes.h (pthread_rwlock_t): Adapt.
	* sysdeps/ia64/nptl/bits/pthreadtypes.h (pthread_rwlock_t): Adapt.
	* sysdeps/m68k/nptl/bits/pthreadtypes.h (pthread_rwlock_t): Adapt.
	* sysdeps/microblaze/nptl/bits/pthreadtypes.h (pthread_rwlock_t): Adapt.
	* sysdeps/mips/nptl/bits/pthreadtypes.h (pthread_rwlock_t): Adapt.
	* sysdeps/nios2/nptl/bits/pthreadtypes.h (pthread_rwlock_t): Adapt.
	* sysdeps/s390/nptl/bits/pthreadtypes.h (pthread_rwlock_t): Adapt.
	* sysdeps/sh/nptl/bits/pthreadtypes.h (pthread_rwlock_t): Adapt.
	* sysdeps/sparc/nptl/bits/pthreadtypes.h (pthread_rwlock_t): Adapt.
	* sysdeps/tile/nptl/bits/pthreadtypes.h (pthread_rwlock_t): Adapt.
	* sysdeps/unix/sysv/linux/alpha/bits/pthreadtypes.h
	(pthread_rwlock_t): Adapt.
	* sysdeps/unix/sysv/linux/powerpc/bits/pthreadtypes.h
	(pthread_rwlock_t): Adapt.
	* sysdeps/x86/bits/pthreadtypes.h (pthread_rwlock_t): Adapt.
	* nptl/nptl-printers.py (): Adapt.
	* nptl/nptl_lock_constants.pysym: Adapt.
	* nptl/test-rwlock-printers.py: Adapt.
	* nptl/test-rwlockattr-printers.c: Adapt.
	* nptl/test-rwlockattr-printers.py: Adapt.

1 files changed, 33 insertions, 20 deletions

diff --git a/nptl/pthread_rwlock_trywrlock.c b/nptl/pthread_rwlock_trywrlock.c
index 251ece133f..0d9ccaf79c 100644
--- a/nptl/pthread_rwlock_trywrlock.c
+++ b/nptl/pthread_rwlock_trywrlock.c
@@ -18,31 +18,44 @@
 
 #include <errno.h>
 #include "pthreadP.h"
-#include <lowlevellock.h>
-#include <elide.h>
-
+#include <atomic.h>
 
+/* See pthread_rwlock_common.c for an overview.  */
 int
 __pthread_rwlock_trywrlock (pthread_rwlock_t *rwlock)
 {
-  int result = EBUSY;
-
-  if (ELIDE_TRYLOCK (rwlock->__data.__rwelision,
-		     rwlock->__data.__lock == 0
-		     && rwlock->__data.__nr_readers == 0
-		     && rwlock->__data.__writer, 1))
-    return 0;
-
-  lll_lock (rwlock->__data.__lock, rwlock->__data.__shared);
-
-  if (rwlock->__data.__writer == 0 && rwlock->__data.__nr_readers == 0)
+  /* When in a trywrlock, we can acquire the write lock if it is in states
+     #1 (idle and read phase) and #5 (idle and write phase), and also in #6
+     (readers waiting, write phase) if we prefer writers.
+     If we observe any other state, we are allowed to fail and do not need to
+     "synchronize memory" as specified by POSIX (hence relaxed MO is
+     sufficient for the first load and the CAS failure path).
+     We face a similar issue as in tryrdlock in that we need to both avoid
+     live-locks / starvation and must not fail spuriously (see there for
+     further comments) -- and thus must loop until we get a definitive
+     observation or state change.  */
+  unsigned int r = atomic_load_relaxed (&rwlock->__data.__readers);
+  bool prefer_writer =
+      (rwlock->__data.__flags != PTHREAD_RWLOCK_PREFER_READER_NP);
+  while (((r & PTHREAD_RWLOCK_WRLOCKED) == 0)
+      && (((r >> PTHREAD_RWLOCK_READER_SHIFT) == 0)
+	  || (prefer_writer && ((r & PTHREAD_RWLOCK_WRPHASE) != 0))))
     {
-      rwlock->__data.__writer = THREAD_GETMEM (THREAD_SELF, tid);
-      result = 0;
+      /* Try to transition to states #7 or #8 (i.e., acquire the lock).  */
+      if (atomic_compare_exchange_weak_acquire (
+	  &rwlock->__data.__readers, &r,
+	  r | PTHREAD_RWLOCK_WRPHASE | PTHREAD_RWLOCK_WRLOCKED))
+	{
+	  atomic_store_relaxed (&rwlock->__data.__writers_futex, 1);
+	  atomic_store_relaxed (&rwlock->__data.__wrphase_futex, 1);
+	  atomic_store_relaxed (&rwlock->__data.__cur_writer,
+	      THREAD_GETMEM (THREAD_SELF, tid));
+	  return 0;
+	}
+      /* TODO Back-off.  */
+      /* See above.  */
     }
-
-  lll_unlock (rwlock->__data.__lock, rwlock->__data.__shared);
-
-  return result;
+  return EBUSY;
 }
+
 strong_alias (__pthread_rwlock_trywrlock, pthread_rwlock_trywrlock)