Re: [PATCH 2/2] New pthread rwlock that is more scalable.

[Torvald Riegel <triegel@redhat.com>]

[-- Attachment #1: Type: text/plain, Size: 737 bytes --]

On Wed, 2016-07-27 at 23:44 +0200, Torvald Riegel wrote:
> 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.

I have noticed two small oversights, which are taken care of in the
attached patch.  The first is a mssign overflow check (a lock acquired
too often as a reader) in one of the tryrdlock branches.  The second is
a that I had forgotten to apply a cleanup (no correctness change; the
former code did more than it had to).

[-- Attachment #2: rwlock-minorfix.patch --]
[-- Type: text/x-patch, Size: 3010 bytes --]

commit 59c2c0dafb1c1460a457037f222032ade9fc5a74
Author: Torvald Riegel <triegel@redhat.com>
Date:   Mon Jan 2 17:50:37 2017 +0100

    Fix a minor issue and an oversight (not a correctness bug) in tryrdlock

diff --git a/nptl/pthread_rwlock_tryrdlock.c b/nptl/pthread_rwlock_tryrdlock.c
index e002f15..6c3014c 100644
--- a/nptl/pthread_rwlock_tryrdlock.c
+++ b/nptl/pthread_rwlock_tryrdlock.c
@@ -51,12 +51,6 @@ __pthread_rwlock_tryrdlock (pthread_rwlock_t *rwlock)
 		  == PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP))
 	    return EBUSY;
 	  rnew = r + (1 << PTHREAD_RWLOCK_READER_SHIFT);
-	  /* If we could have caused an overflow or take effect during an
-	     overflow, we just can / need to return EAGAIN.  There is no need
-	     to have modified the number of readers because we could have
-	     done that and cleaned up immediately.  */
-	  if (rnew >= PTHREAD_RWLOCK_READER_OVERFLOW)
-	    return EAGAIN;
 	}
       else
 	{
@@ -72,6 +66,12 @@ __pthread_rwlock_tryrdlock (pthread_rwlock_t *rwlock)
 		  ^ PTHREAD_RWLOCK_WRPHASE;
 	    }
 	}
+      /* If we could have caused an overflow or take effect during an
+	 overflow, we just can / need to return EAGAIN.  There is no need to
+	 have actually modified the number of readers because we could have
+	 done that and cleaned up immediately.  */
+      if (rnew >= PTHREAD_RWLOCK_READER_OVERFLOW)
+	return EAGAIN;
     }
   /* If the CAS fails, we retry; this prevents that tryrdlock fails spuriously
      (i.e., fails to acquire the lock although there is no writer), which is
@@ -84,16 +84,25 @@ __pthread_rwlock_tryrdlock (pthread_rwlock_t *rwlock)
      readers or writers that acquire and release in the meantime.  Using
      randomized exponential back-off to make a live-lock unlikely should be
      sufficient.
+     TODO Back-off.
      Acquire MO so we synchronize with prior writers.  */
   while (!atomic_compare_exchange_weak_acquire (&rwlock->__data.__readers,
       &r, rnew));
 
   if ((r & PTHREAD_RWLOCK_WRPHASE) != 0)
     {
-      //FIXME / TODO same as in rdlock_full
-      int private = __pthread_rwlock_get_private (rwlock);
-      atomic_store_release (&rwlock->__data.__wrphase_futex, 0);
-      futex_wake (&rwlock->__data.__wrphase_futex, INT_MAX, private);
+      /* Same as in __pthread_rwlock_rdlock_full:
+	 We started the read phase, so we are also responsible for
+	 updating the write-phase futex.  Relaxed MO is sufficient.
+	 Note that there can be no other reader that we have to wake
+	 because all other readers will see the read phase started by us
+	 (or they will try to start it themselves); if a writer started
+	 the read phase, we cannot have started it.  Furthermore, we
+	 cannot discard a PTHREAD_RWLOCK_FUTEX_USED flag because we will
+	 overwrite the value set by the most recent writer (or the readers
+	 before it in case of explicit hand-over) and we know that there
+	 are no waiting readers.  */
+      atomic_store_relaxed (&rwlock->__data.__wrphase_futex, 0);
     }
 
   return 0;