[PATCH] Fix rwlock stall with PREFER_WRITER_NONRECURSIVE_NP (bug 23861)

[PATCH] Fix rwlock stall with PREFER_WRITER_NONRECURSIVE_NP (bug 23861)

[Andreas Schwab]

	[BZ #23861]
	* nptl/pthread_rwlock_common.c (__pthread_rwlock_rdlock_full):
	Update expected value for __readers while waiting on
	PTHREAD_RWLOCK_RWAITING.
	* nptl/tst-rwlock-pwn.c: New file.
	* nptl/Makefile (tests): Add tst-rwlock-pwn.
---
 nptl/Makefile                |  3 +-
 nptl/pthread_rwlock_common.c |  6 +--
 nptl/tst-rwlock-pwn.c        | 78 ++++++++++++++++++++++++++++++++++++
 3 files changed, 83 insertions(+), 4 deletions(-)
 create mode 100644 nptl/tst-rwlock-pwn.c

diff --git a/nptl/Makefile b/nptl/Makefile
index 49b6faa330..c164b929b7 100644
--- a/nptl/Makefile
+++ b/nptl/Makefile
@@ -318,7 +318,8 @@ tests = tst-attr1 tst-attr2 tst-attr3 tst-default-attr \
 	tst-minstack-throw \
 	tst-cnd-basic tst-mtx-trylock tst-cnd-broadcast \
 	tst-cnd-timedwait tst-thrd-detach tst-mtx-basic tst-thrd-sleep \
-	tst-mtx-recursive tst-tss-basic tst-call-once tst-mtx-timedlock
+	tst-mtx-recursive tst-tss-basic tst-call-once tst-mtx-timedlock \
+	tst-rwlock-pwn
 
 tests-internal := tst-rwlock19 tst-rwlock20 \
 		  tst-sem11 tst-sem12 tst-sem13 \
diff --git a/nptl/pthread_rwlock_common.c b/nptl/pthread_rwlock_common.c
index a290d08332..e95cbe4033 100644
--- a/nptl/pthread_rwlock_common.c
+++ b/nptl/pthread_rwlock_common.c
@@ -314,12 +314,12 @@ __pthread_rwlock_rdlock_full (pthread_rwlock_t *rwlock,
 		 harmless because the flag is just about the state of
 		 __readers, and all threads set the flag under the same
 		 conditions.  */
-	      while ((atomic_load_relaxed (&rwlock->__data.__readers)
-		  & PTHREAD_RWLOCK_RWAITING) != 0)
+	      while (((r = atomic_load_relaxed (&rwlock->__data.__readers))
+		      & PTHREAD_RWLOCK_RWAITING) != 0)
 		{
 		  int private = __pthread_rwlock_get_private (rwlock);
 		  int err = futex_abstimed_wait (&rwlock->__data.__readers,
-		      r, abstime, private);
+						 r, abstime, private);
 		  /* We ignore EAGAIN and EINTR.  On time-outs, we can just
 		     return because we don't need to clean up anything.  */
 		  if (err == ETIMEDOUT)
diff --git a/nptl/tst-rwlock-pwn.c b/nptl/tst-rwlock-pwn.c
new file mode 100644
index 0000000000..a2be59576a
--- /dev/null
+++ b/nptl/tst-rwlock-pwn.c
@@ -0,0 +1,78 @@
+/* Test rwlock with PREFER_WRITER_NONRECURSIVE_NP.
+   Copyright (C) 2018 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library 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
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <pthread.h>
+#include <support/xthread.h>
+
+#define LOOPS 10
+#define NTHREADS 3
+
+volatile int do_exit;
+pthread_rwlockattr_t mylock_attr;
+pthread_rwlock_t mylock;
+
+void *
+wrloop (void *a)
+{
+  while (!do_exit)
+    {
+      if (random () & 1)
+	{
+	  xpthread_rwlock_wrlock (&mylock);
+	  xpthread_rwlock_unlock (&mylock);
+	}
+      else
+	{
+	  xpthread_rwlock_rdlock (&mylock);
+	  xpthread_rwlock_unlock (&mylock);
+	}
+    }
+  return NULL;
+}
+
+int
+do_test (void)
+{
+  xpthread_rwlockattr_init (&mylock_attr);
+  xpthread_rwlockattr_setkind_np (&mylock_attr,
+				  PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP);
+  xpthread_rwlock_init (&mylock, &mylock_attr);
+
+  for (int n = 0; n < LOOPS; n++)
+    {
+      pthread_t tids[NTHREADS];
+      do_exit = 0;
+      for (int i = 0; i < NTHREADS; i++)
+	tids[i] = xpthread_create (NULL, wrloop, NULL);
+      sleep (1);
+      printf ("Exiting..."); fflush (stdout);
+      do_exit = 1;
+      for (int i = 0; i < NTHREADS; i++)
+	xpthread_join (tids[i]);
+      printf ("done.\n");
+    }
+  pthread_rwlock_destroy (&mylock);
+  pthread_rwlockattr_destroy (&mylock_attr);
+  return 0;
+}
+
+#define TIMEOUT 3 * LOOPS
+#include <support/test-driver.c>
-- 
2.19.1


-- 
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Re: [PATCH] Fix rwlock stall with PREFER_WRITER_NONRECURSIVE_NP (bug 23861)

[Carlos O'Donell]

On 11/8/18 9:54 AM, Andreas Schwab wrote:
> 	[BZ #23861]
> 	* nptl/pthread_rwlock_common.c (__pthread_rwlock_rdlock_full):
> 	Update expected value for __readers while waiting on
> 	PTHREAD_RWLOCK_RWAITING.
> 	* nptl/tst-rwlock-pwn.c: New file.
> 	* nptl/Makefile (tests): Add tst-rwlock-pwn.

Is this at all related to this bug?

https://sourceware.org/bugzilla/show_bug.cgi?id=23844

I know this bug is not using PREFER_WRITER_NONRECURSIVE_NP, but I was curious
if you looked at this bug also when reviewing this code?

> ---
>  nptl/Makefile                |  3 +-
>  nptl/pthread_rwlock_common.c |  6 +--
>  nptl/tst-rwlock-pwn.c        | 78 ++++++++++++++++++++++++++++++++++++
>  3 files changed, 83 insertions(+), 4 deletions(-)
>  create mode 100644 nptl/tst-rwlock-pwn.c
> 
> diff --git a/nptl/Makefile b/nptl/Makefile
> index 49b6faa330..c164b929b7 100644
> --- a/nptl/Makefile
> +++ b/nptl/Makefile
> @@ -318,7 +318,8 @@ tests = tst-attr1 tst-attr2 tst-attr3 tst-default-attr \
>  	tst-minstack-throw \
>  	tst-cnd-basic tst-mtx-trylock tst-cnd-broadcast \
>  	tst-cnd-timedwait tst-thrd-detach tst-mtx-basic tst-thrd-sleep \
> -	tst-mtx-recursive tst-tss-basic tst-call-once tst-mtx-timedlock
> +	tst-mtx-recursive tst-tss-basic tst-call-once tst-mtx-timedlock \
> +	tst-rwlock-pwn

Please don't call this pwn :-)

Please use a more descriptive name like "tst-rwlock-stall"

>  
>  tests-internal := tst-rwlock19 tst-rwlock20 \
>  		  tst-sem11 tst-sem12 tst-sem13 \
> diff --git a/nptl/pthread_rwlock_common.c b/nptl/pthread_rwlock_common.c
> index a290d08332..e95cbe4033 100644
> --- a/nptl/pthread_rwlock_common.c
> +++ b/nptl/pthread_rwlock_common.c
> @@ -314,12 +314,12 @@ __pthread_rwlock_rdlock_full (pthread_rwlock_t *rwlock,
>  		 harmless because the flag is just about the state of
>  		 __readers, and all threads set the flag under the same
>  		 conditions.  */
> -	      while ((atomic_load_relaxed (&rwlock->__data.__readers)
> -		  & PTHREAD_RWLOCK_RWAITING) != 0)
> +	      while (((r = atomic_load_relaxed (&rwlock->__data.__readers))
> +		      & PTHREAD_RWLOCK_RWAITING) != 0)
>  		{
>  		  int private = __pthread_rwlock_get_private (rwlock);
>  		  int err = futex_abstimed_wait (&rwlock->__data.__readers,
> -		      r, abstime, private);
> +						 r, abstime, private);

Why is this change correct?

>  		  /* We ignore EAGAIN and EINTR.  On time-outs, we can just
>  		     return because we don't need to clean up anything.  */
>  		  if (err == ETIMEDOUT)
> diff --git a/nptl/tst-rwlock-pwn.c b/nptl/tst-rwlock-pwn.c
> new file mode 100644
> index 0000000000..a2be59576a
> --- /dev/null
> +++ b/nptl/tst-rwlock-pwn.c
> @@ -0,0 +1,78 @@
> +/* Test rwlock with PREFER_WRITER_NONRECURSIVE_NP.

OK.

> +   Copyright (C) 2018 Free Software Foundation, Inc.
> +   This file is part of the GNU C Library.
> +
> +   The GNU C Library is free software; you can redistribute it and/or
> +   modify it under the terms of the GNU Lesser General Public
> +   License as published by the Free Software Foundation; either
> +   version 2.1 of the License, or (at your option) any later version.
> +
> +   The GNU C Library 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
> +   Lesser General Public License for more details.
> +
> +   You should have received a copy of the GNU Lesser General Public
> +   License along with the GNU C Library; if not, see
> +   <http://www.gnu.org/licenses/>.  */
> +
> +#include <stdio.h>
> +#include <stdlib.h>
> +#include <unistd.h>
> +#include <pthread.h>
> +#include <support/xthread.h>
> +
> +#define LOOPS 10

Why 10?

> +#define NTHREADS 3

Why 3?

Suggest:

/* We choose 10 iterations and 3 threads because this happens
   to be able to trigger the stall today on modern hardware.  */

> +
> +volatile int do_exit;
> +pthread_rwlockattr_t mylock_attr;
> +pthread_rwlock_t mylock;
> +
> +void *
> +wrloop (void *a)

Misleading function name, it executes a wrlock or rdlock
not just 'writes in loop'.

Suggest 'wr_rd_loop' or just 'lock_loop'.

> +{
> +  while (!do_exit)
> +    {
> +      if (random () & 1)

Please make the test deterministic.

Does it still stall if you just increment a counter
and then alternate between the two operations?

> +	{
> +	  xpthread_rwlock_wrlock (&mylock);
> +	  xpthread_rwlock_unlock (&mylock);
> +	}
> +      else
> +	{
> +	  xpthread_rwlock_rdlock (&mylock);
> +	  xpthread_rwlock_unlock (&mylock);
> +	}
> +    }
> +  return NULL;
> +}
> +
> +int
> +do_test (void)
> +{
> +  xpthread_rwlockattr_init (&mylock_attr);
> +  xpthread_rwlockattr_setkind_np (&mylock_attr,
> +				  PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP);
> +  xpthread_rwlock_init (&mylock, &mylock_attr);

OK.

> +
> +  for (int n = 0; n < LOOPS; n++)
> +    {
> +      pthread_t tids[NTHREADS];
> +      do_exit = 0;
> +      for (int i = 0; i < NTHREADS; i++)
> +	tids[i] = xpthread_create (NULL, wrloop, NULL);
> +      sleep (1);

Why sleep?

> +      printf ("Exiting..."); fflush (stdout);

Two lines please.

> +      do_exit = 1;
> +      for (int i = 0; i < NTHREADS; i++)
> +	xpthread_join (tids[i]);
> +      printf ("done.\n");
> +    }
> +  pthread_rwlock_destroy (&mylock);
> +  pthread_rwlockattr_destroy (&mylock_attr);
> +  return 0;
> +}
> +
> +#define TIMEOUT 3 * LOOPS

Please add a constant startup time.

Suggest:

#define TIMEOUT (DEFAULT_TIMEOUT + 3 * LOOPS)

> +#include <support/test-driver.c>
> 


-- 
Cheers,
Carlos.

Re: [PATCH] Fix rwlock stall with PREFER_WRITER_NONRECURSIVE_NP (bug 23861)

[Andreas Schwab]

On Nov 08 2018, Carlos O'Donell <carlos@redhat.com> wrote:

> On 11/8/18 9:54 AM, Andreas Schwab wrote:
>> 	[BZ #23861]
>> 	* nptl/pthread_rwlock_common.c (__pthread_rwlock_rdlock_full):
>> 	Update expected value for __readers while waiting on
>> 	PTHREAD_RWLOCK_RWAITING.
>> 	* nptl/tst-rwlock-pwn.c: New file.
>> 	* nptl/Makefile (tests): Add tst-rwlock-pwn.
>
> Is this at all related to this bug?
>
> https://sourceware.org/bugzilla/show_bug.cgi?id=23844

This part of the code is exclusively used for
PREFER_WRITER_NONRECURSIVE_NP rwlocks.

> Please don't call this pwn :-)

Why?

> Please use a more descriptive name like "tst-rwlock-stall"

It is testing PREFER_WRITER_NONRECURSIVE_NP, so pwn is very descriptive.

>>  		  int err = futex_abstimed_wait (&rwlock->__data.__readers,
>> -		      r, abstime, private);
>> +						 r, abstime, private);
>
> Why is this change correct?

Emacs told me so, and Emacs is always right.

>> +#define LOOPS 10
>
> Why 10?

Just to make the bug reproducable enough.

>
>> +#define NTHREADS 3
>
> Why 3?

From the original test case.

> Does it still stall if you just increment a counter
> and then alternate between the two operations?

No.

>> +  for (int n = 0; n < LOOPS; n++)
>> +    {
>> +      pthread_t tids[NTHREADS];
>> +      do_exit = 0;
>> +      for (int i = 0; i < NTHREADS; i++)
>> +	tids[i] = xpthread_create (NULL, wrloop, NULL);
>> +      sleep (1);
>
> Why sleep?

To let the threads running for some time.

Andreas.

-- 
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Re: [PATCH] Fix rwlock stall with PREFER_WRITER_NONRECURSIVE_NP (bug 23861)

[Torvald Riegel]

On Thu, 2018-11-08 at 14:36 -0500, Carlos O'Donell wrote:
> On 11/8/18 9:54 AM, Andreas Schwab wrote:
> > 	[BZ #23861]
> > 	* nptl/pthread_rwlock_common.c (__pthread_rwlock_rdlock_full):
> > 	Update expected value for __readers while waiting on
> > 	PTHREAD_RWLOCK_RWAITING.
> > 	* nptl/tst-rwlock-pwn.c: New file.
> > 	* nptl/Makefile (tests): Add tst-rwlock-pwn.
> 
> Is this at all related to this bug?
> 
> https://sourceware.org/bugzilla/show_bug.cgi?id=23844

No that's a different bug.  At least the bug in the code is different, not
sure whether it could result in the same symptoms.

> >  
> >  tests-internal := tst-rwlock19 tst-rwlock20 \
> >  		  tst-sem11 tst-sem12 tst-sem13 \
> > diff --git a/nptl/pthread_rwlock_common.c b/nptl/pthread_rwlock_common.c
> > index a290d08332..e95cbe4033 100644
> > --- a/nptl/pthread_rwlock_common.c
> > +++ b/nptl/pthread_rwlock_common.c
> > @@ -314,12 +314,12 @@ __pthread_rwlock_rdlock_full (pthread_rwlock_t *rwlock,
> >  		 harmless because the flag is just about the state of
> >  		 __readers, and all threads set the flag under the same
> >  		 conditions.  */

I'd add this to the comment:
"Update r so that the futex call in the loop uses the correct value."

> > -	      while ((atomic_load_relaxed (&rwlock->__data.__readers)
> > -		  & PTHREAD_RWLOCK_RWAITING) != 0)
> > +	      while (((r = atomic_load_relaxed (&rwlock->__data.__readers))
> > +		      & PTHREAD_RWLOCK_RWAITING) != 0)
> >  		{
> >  		  int private = __pthread_rwlock_get_private (rwlock);
> >  		  int err = futex_abstimed_wait (&rwlock->__data.__readers,
> > -		      r, abstime, private);
> > +						 r, abstime, private);
> 
> Why is this change correct?

The fix is fine (and the formatting too, I guess).  I think the comment
above should explain the fix.  The futex call needs to wait on the based on
the value that lead to calling futex_wait in the first place.

Re: [PATCH] Fix rwlock stall with PREFER_WRITER_NONRECURSIVE_NP (bug 23861)

[Carlos O'Donell]

On 12/12/18 6:49 AM, Andreas Schwab wrote:
> 	[BZ #23861]
> 	* nptl/pthread_rwlock_common.c (__pthread_rwlock_rdlock_full):
> 	Update expected value for __readers while waiting on
> 	PTHREAD_RWLOCK_RWAITING.
> 	* nptl/tst-rwlock-pwn.c: New file.
> 	* nptl/Makefile (tests): Add tst-rwlock-pwn.

OK for master with:
- the following commit message (or a variant)
- more comments added to the test case (see suggestions below).

Reviewed-by: Carlos O'Donell <carlos@redhat.com>

Thank you for the fix. In the future please provide a more detailed 
description of the problem and the fix. The more detailed your description
the more valuable you'll find my review as I'm able to review intent and
changes together with my own understanding of the code, without having 
to replicate all of the work that went into it.

I have tested this version on my own systems, and find that tst-rwlock-pwn
passes and doesn't fail after several days of testing. Testing was only
done on x86_64.

I suggest the following commit message:
~~~
Fix rwlock stall with PREFER_WRITER_NONRECURSIVE_NP (bug 23861)

In the read lock function (__pthread_rwlock_rdlock_full) there was a
code path which would fail to reload __readers while waiting for
PTHREAD_RWLOCK_RWAITING to change. This failure to reload __readers
into a local value meant that various conditionals used the old value
of __readers and with only two threads left it could result in an
indefinite stall of one of the readers (waiting for PTHREAD_RWLOCK_RWAITING
to go to zero, but it never would).

Reviewed-by: Carlos O'Donell <carlos@redhat.com>
~~~
Feel free to add or modify the message.

> ---
>  nptl/Makefile                |  3 +-
>  nptl/pthread_rwlock_common.c |  2 +-
>  nptl/tst-rwlock-pwn.c        | 82 ++++++++++++++++++++++++++++++++++++
>  3 files changed, 85 insertions(+), 2 deletions(-)
>  create mode 100644 nptl/tst-rwlock-pwn.c
> 
> diff --git a/nptl/Makefile b/nptl/Makefile
> index 34ae830276..b01f2b0626 100644
> --- a/nptl/Makefile
> +++ b/nptl/Makefile
> @@ -318,7 +318,8 @@ tests = tst-attr1 tst-attr2 tst-attr3 tst-default-attr \
>  	tst-minstack-throw \
>  	tst-cnd-basic tst-mtx-trylock tst-cnd-broadcast \
>  	tst-cnd-timedwait tst-thrd-detach tst-mtx-basic tst-thrd-sleep \
> -	tst-mtx-recursive tst-tss-basic tst-call-once tst-mtx-timedlock
> +	tst-mtx-recursive tst-tss-basic tst-call-once tst-mtx-timedlock \
> +	tst-rwlock-pwn

OK.

>  
>  tests-internal := tst-rwlock19 tst-rwlock20 \
>  		  tst-sem11 tst-sem12 tst-sem13 \
> diff --git a/nptl/pthread_rwlock_common.c b/nptl/pthread_rwlock_common.c
> index 5dd534271a..85fc1bcfc7 100644
> --- a/nptl/pthread_rwlock_common.c
> +++ b/nptl/pthread_rwlock_common.c
> @@ -314,7 +314,7 @@ __pthread_rwlock_rdlock_full (pthread_rwlock_t *rwlock,
>  		 harmless because the flag is just about the state of
>  		 __readers, and all threads set the flag under the same
>  		 conditions.  */
> -	      while ((atomic_load_relaxed (&rwlock->__data.__readers)
> +	      while (((r = atomic_load_relaxed (&rwlock->__data.__readers))
>  		      & PTHREAD_RWLOCK_RWAITING) != 0)

This is OK.

(a) Issues with atomic.h API.

It took me a while to review the entire algorithm, and this particular readlock
section of the algorithm has some interesting choices which were made in atomic.h
which I think lead to this defect. I wonder if we can't improve atomic.h to fix this.

There is a mix of atomic operations that upon completion load the result of the most
recent read into the expected memory location. In fact this is what the previous
call to atomic_compare_exchange_weak_relaxed() does because it uses
__atomic_compare_exchange_n() e.g. "If they are not equal, the operation is a read 
and the current contents of *ptr are written into *expected."

Then in the loop that is waiting for RWAITING to clear (this is the other half of
__pthread_rwlock_rdunlock, which ensures readers are able to make progress) the
algorithm uses atomic_load_relaxed which *returns* the value rather than having
any it written into a pointer as __atomic_load() would have done.

It is this mixing of "some atomic operations return the most recently read value"
and "some atomic operations write the most recently read value into expected" that
I think is hard to keep track of and actually requires looking at the underlying
implementation in atomic.h to determine which of the two operations is going on.

(b) rwlock stall problem.

In the inner-most loop of the PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP within
__pthread_rwlock_rdlock_full, we fail to reload the value of r, and this means the
following:

313               /* Wait for as long as the flag is set.  An ABA situation is
314                  harmless because the flag is just about the state of
315                  __readers, and all threads set the flag under the same
316                  conditions.  */
317               while ((atomic_load_relaxed (&rwlock->__data.__readers)
318                   & PTHREAD_RWLOCK_RWAITING) != 0)

This does not reload r.

319                 {
320                   int private = __pthread_rwlock_get_private (rwlock);
321                   int err = futex_abstimed_wait (&rwlock->__data.__readers,
322                       r, abstime, private);

This will fail continuously if r is different.

323                   /* We ignore EAGAIN and EINTR.  On time-outs, we can just
324                      return because we don't need to clean up anything.  */
325                   if (err == ETIMEDOUT)
326                     return err;
327                 }

However, the atomic_load_relaxed reads and returns the real value of __readers
and eventually it should succeed and exit the loop after consuming a lot of cpu
to busy-wait for r to change i.e. RWAITING to clear.

299   if (rwlock->__data.__flags == PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP)
300     { 
301       r = atomic_load_relaxed (&rwlock->__data.__readers);
302       while (((r & PTHREAD_RWLOCK_WRPHASE) == 0)
303               && ((r & PTHREAD_RWLOCK_WRLOCKED) != 0)
304               && ((r >> PTHREAD_RWLOCK_READER_SHIFT) > 0))

It's very likely this is true with old data in r.

305         {
306           /* TODO Spin first.  */
307           /* Try setting the flag signaling that we are waiting without having
308              incremented the number of readers.  Relaxed MO is fine because
309              this is just about waiting for a state change in __readers.  */
310           if (atomic_compare_exchange_weak_relaxed
311               (&rwlock->__data.__readers, &r, r | PTHREAD_RWLOCK_RWAITING))

When this fails, because r is old data, it updates r with the most recent value
because it uses __atomic_compare_exchange_n() which updates *expected with the
most recently read value.

312             { 

This loop can go on forever if the failure occurs in the second to last reader.
The second to last reader will clear RWAITING, and if the rest of r matches,
the if on line 310 can succeed and set RWAITING *again*, but this time the last
reader should have succeeded and didn't and therefore it waits forever for an
unlock that will not arrive.

This also supports why 3 is the required minimum number of threads, you need one
writer, and two readers, to trigger the stall. With the minimum number of threads
you're more likely to get them on distinct CPUs and trigger the stall case.

>  		{
>  		  int private = __pthread_rwlock_get_private (rwlock);
> diff --git a/nptl/tst-rwlock-pwn.c b/nptl/tst-rwlock-pwn.c
> new file mode 100644
> index 0000000000..91fa452610
> --- /dev/null
> +++ b/nptl/tst-rwlock-pwn.c
> @@ -0,0 +1,82 @@
> +/* Test rwlock with PREFER_WRITER_NONRECURSIVE_NP.

This is related to a bug.

Please use:

Bug 23861: Test rwlock with PREFER_WRITER_NONRECURSIVE_NP.

> +   Copyright (C) 2018 Free Software Foundation, Inc.
> +   This file is part of the GNU C Library.
> +
> +   The GNU C Library is free software; you can redistribute it and/or
> +   modify it under the terms of the GNU Lesser General Public
> +   License as published by the Free Software Foundation; either
> +   version 2.1 of the License, or (at your option) any later version.
> +
> +   The GNU C Library 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
> +   Lesser General Public License for more details.
> +
> +   You should have received a copy of the GNU Lesser General Public
> +   License along with the GNU C Library; if not, see
> +   <http://www.gnu.org/licenses/>.  */
> +
> +#include <stdio.h>
> +#include <stdlib.h>
> +#include <unistd.h>
> +#include <pthread.h>
> +#include <support/xthread.h>
> +
> +/* We choose 10 iterations and 3 threads because this happens to be able
> +   to trigger the stall today on modern hardware.  */

This should say:

/* We choose 10 iterations because this happens to be able
   to trigger the stall today on modern hardware.  */

> +#define LOOPS 10

Please add:

/* We need 3 threads to trigger bug 23861.  One thread as a writer, and
   two reader threads.  The test verifies that the second-to-last reader
   is able to notify the *last* reader that it should be done waiting.
   If the second-to-last reader fails to notify the last reader or does
   so incorrectly then the last reader may stall indefinitely.  */

> +#define NTHREADS 3
> +
> +_Atomic int do_exit;
> +pthread_rwlockattr_t mylock_attr;
> +pthread_rwlock_t mylock;
> +
> +void *
> +run_loop (void *a)
> +{
> +  while (!do_exit)
> +    {
> +      if (random () & 1)
> +	{
> +	  xpthread_rwlock_wrlock (&mylock);
> +	  xpthread_rwlock_unlock (&mylock);
> +	}
> +      else
> +	{
> +	  xpthread_rwlock_rdlock (&mylock);
> +	  xpthread_rwlock_unlock (&mylock);
> +	}	

OK.

> +    }
> +  return NULL;
> +}
> +
> +int
> +do_test (void)
> +{
> +  xpthread_rwlockattr_init (&mylock_attr);
> +  xpthread_rwlockattr_setkind_np (&mylock_attr,
> +				  PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP);
> +  xpthread_rwlock_init (&mylock, &mylock_attr);
> +
> +  for (int n = 0; n < LOOPS; n++)
> +    {
> +      pthread_t tids[NTHREADS];
> +      do_exit = 0;
> +      for (int i = 0; i < NTHREADS; i++)
> +	tids[i] = xpthread_create (NULL, run_loop, NULL);
> +      /* Let the threads run for some time.  */
> +      sleep (1);
> +      printf ("Exiting...");
> +      fflush (stdout);
> +      do_exit = 1;
> +      for (int i = 0; i < NTHREADS; i++)
> +	xpthread_join (tids[i]);
> +      printf ("done.\n");
> +    }
> +  pthread_rwlock_destroy (&mylock);
> +  pthread_rwlockattr_destroy (&mylock_attr);
> +  return 0;
> +}
> +
> +#define TIMEOUT (DEFAULT_TIMEOUT + 3 * LOOPS)
> +#include <support/test-driver.c>
> 

OK.

-- 
Cheers,
Carlos.

[PATCH] Fix rwlock stall with PREFER_WRITER_NONRECURSIVE_NP (bug 23861)

[Andreas Schwab]

	[BZ #23861]
	* nptl/pthread_rwlock_common.c (__pthread_rwlock_rdlock_full):
	Update expected value for __readers while waiting on
	PTHREAD_RWLOCK_RWAITING.
	* nptl/tst-rwlock-pwn.c: New file.
	* nptl/Makefile (tests): Add tst-rwlock-pwn.
---
 nptl/Makefile                |  3 +-
 nptl/pthread_rwlock_common.c |  2 +-
 nptl/tst-rwlock-pwn.c        | 82 ++++++++++++++++++++++++++++++++++++
 3 files changed, 85 insertions(+), 2 deletions(-)
 create mode 100644 nptl/tst-rwlock-pwn.c

diff --git a/nptl/Makefile b/nptl/Makefile
index 34ae830276..b01f2b0626 100644
--- a/nptl/Makefile
+++ b/nptl/Makefile
@@ -318,7 +318,8 @@ tests = tst-attr1 tst-attr2 tst-attr3 tst-default-attr \
 	tst-minstack-throw \
 	tst-cnd-basic tst-mtx-trylock tst-cnd-broadcast \
 	tst-cnd-timedwait tst-thrd-detach tst-mtx-basic tst-thrd-sleep \
-	tst-mtx-recursive tst-tss-basic tst-call-once tst-mtx-timedlock
+	tst-mtx-recursive tst-tss-basic tst-call-once tst-mtx-timedlock \
+	tst-rwlock-pwn
 
 tests-internal := tst-rwlock19 tst-rwlock20 \
 		  tst-sem11 tst-sem12 tst-sem13 \
diff --git a/nptl/pthread_rwlock_common.c b/nptl/pthread_rwlock_common.c
index 5dd534271a..85fc1bcfc7 100644
--- a/nptl/pthread_rwlock_common.c
+++ b/nptl/pthread_rwlock_common.c
@@ -314,7 +314,7 @@ __pthread_rwlock_rdlock_full (pthread_rwlock_t *rwlock,
 		 harmless because the flag is just about the state of
 		 __readers, and all threads set the flag under the same
 		 conditions.  */
-	      while ((atomic_load_relaxed (&rwlock->__data.__readers)
+	      while (((r = atomic_load_relaxed (&rwlock->__data.__readers))
 		      & PTHREAD_RWLOCK_RWAITING) != 0)
 		{
 		  int private = __pthread_rwlock_get_private (rwlock);
diff --git a/nptl/tst-rwlock-pwn.c b/nptl/tst-rwlock-pwn.c
new file mode 100644
index 0000000000..91fa452610
--- /dev/null
+++ b/nptl/tst-rwlock-pwn.c
@@ -0,0 +1,82 @@
+/* Test rwlock with PREFER_WRITER_NONRECURSIVE_NP.
+   Copyright (C) 2018 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library 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
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <pthread.h>
+#include <support/xthread.h>
+
+/* We choose 10 iterations and 3 threads because this happens to be able
+   to trigger the stall today on modern hardware.  */
+#define LOOPS 10
+#define NTHREADS 3
+
+_Atomic int do_exit;
+pthread_rwlockattr_t mylock_attr;
+pthread_rwlock_t mylock;
+
+void *
+run_loop (void *a)
+{
+  while (!do_exit)
+    {
+      if (random () & 1)
+	{
+	  xpthread_rwlock_wrlock (&mylock);
+	  xpthread_rwlock_unlock (&mylock);
+	}
+      else
+	{
+	  xpthread_rwlock_rdlock (&mylock);
+	  xpthread_rwlock_unlock (&mylock);
+	}
+    }
+  return NULL;
+}
+
+int
+do_test (void)
+{
+  xpthread_rwlockattr_init (&mylock_attr);
+  xpthread_rwlockattr_setkind_np (&mylock_attr,
+				  PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP);
+  xpthread_rwlock_init (&mylock, &mylock_attr);
+
+  for (int n = 0; n < LOOPS; n++)
+    {
+      pthread_t tids[NTHREADS];
+      do_exit = 0;
+      for (int i = 0; i < NTHREADS; i++)
+	tids[i] = xpthread_create (NULL, run_loop, NULL);
+      /* Let the threads run for some time.  */
+      sleep (1);
+      printf ("Exiting...");
+      fflush (stdout);
+      do_exit = 1;
+      for (int i = 0; i < NTHREADS; i++)
+	xpthread_join (tids[i]);
+      printf ("done.\n");
+    }
+  pthread_rwlock_destroy (&mylock);
+  pthread_rwlockattr_destroy (&mylock_attr);
+  return 0;
+}
+
+#define TIMEOUT (DEFAULT_TIMEOUT + 3 * LOOPS)
+#include <support/test-driver.c>
-- 
2.20.0


-- 
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Re: [PATCH] Fix rwlock stall with PREFER_WRITER_NONRECURSIVE_NP (bug 23861)

[Andreas Schwab]

On Dez 11 2018, Florian Weimer <fweimer@redhat.com> wrote:

> * Andreas Schwab:
>
>> On Dez 11 2018, Florian Weimer <fweimer@redhat.com> wrote:
>>
>>> * Andreas Schwab:
>>>
>>>>> No, without atomics, the code has a data race and undefined behavior.
>>>>
>>>> In which way?  There is a single setter, and it doesn't matter how long
>>>> the thread takes to see the transition from zero to non-zero.
>>>
>>> | The execution of a program contains a data race if it contains two
>>> | conflicting actions in different threads,
>>
>> In which way do the actions conflict?
>
> | Two expression evaluations conflict if one of them modifies a memory
> | location and the other one reads or modifies the same memory location.

And how is that a problem in this pariticular case?

Andreas.

-- 
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Re: [PATCH] Fix rwlock stall with PREFER_WRITER_NONRECURSIVE_NP (bug 23861)

[Carlos O'Donell]

On 12/11/18 11:16 AM, Andreas Schwab wrote:
> On Dez 11 2018, Florian Weimer <fweimer@redhat.com> wrote:
> 
>> * Andreas Schwab:
>>
>>> On Dez 11 2018, Florian Weimer <fweimer@redhat.com> wrote:
>>>
>>>> * Andreas Schwab:
>>>>
>>>>>> No, without atomics, the code has a data race and undefined behavior.
>>>>>
>>>>> In which way?  There is a single setter, and it doesn't matter how long
>>>>> the thread takes to see the transition from zero to non-zero.
>>>>
>>>> | The execution of a program contains a data race if it contains two
>>>> | conflicting actions in different threads,
>>>
>>> In which way do the actions conflict?
>>
>> | Two expression evaluations conflict if one of them modifies a memory
>> | location and the other one reads or modifies the same memory location.
> 
> And how is that a problem in this pariticular case?

Some data races can be benign, but they are still data races and they
still render the program invalid (undefined behvaiour).

Use relaxed MO loads/stores if you need them.

-- 
Cheers,
Carlos.

Re: [PATCH] Fix rwlock stall with PREFER_WRITER_NONRECURSIVE_NP (bug 23861)

[Florian Weimer]

* Andreas Schwab:

> On Dez 11 2018, Florian Weimer <fweimer@redhat.com> wrote:
>
>> * Andreas Schwab:
>>
>>>> No, without atomics, the code has a data race and undefined behavior.
>>>
>>> In which way?  There is a single setter, and it doesn't matter how long
>>> the thread takes to see the transition from zero to non-zero.
>>
>> | The execution of a program contains a data race if it contains two
>> | conflicting actions in different threads,
>
> In which way do the actions conflict?

| Two expression evaluations conflict if one of them modifies a memory
| location and the other one reads or modifies the same memory location.

Thanks,
Florian

Re: [PATCH] Fix rwlock stall with PREFER_WRITER_NONRECURSIVE_NP (bug 23861)

[Andreas Schwab]

On Dez 11 2018, Florian Weimer <fweimer@redhat.com> wrote:

> * Andreas Schwab:
>
>>> No, without atomics, the code has a data race and undefined behavior.
>>
>> In which way?  There is a single setter, and it doesn't matter how long
>> the thread takes to see the transition from zero to non-zero.
>
> | The execution of a program contains a data race if it contains two
> | conflicting actions in different threads,

In which way do the actions conflict?

Andreas.

-- 
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Re: [PATCH] Fix rwlock stall with PREFER_WRITER_NONRECURSIVE_NP (bug 23861)

[Florian Weimer]

* Andreas Schwab:

>> No, without atomics, the code has a data race and undefined behavior.
>
> In which way?  There is a single setter, and it doesn't matter how long
> the thread takes to see the transition from zero to non-zero.

| The execution of a program contains a data race if it contains two
| conflicting actions in different threads, at least one of which is not
| atomic, and neither happens before the other. Any such data race
| results in undefined behavior.

Florian

Re: [PATCH] Fix rwlock stall with PREFER_WRITER_NONRECURSIVE_NP (bug 23861)

[Andreas Schwab]

On Dez 11 2018, Florian Weimer <fweimer@redhat.com> wrote:

> * Andreas Schwab:
>
>> On Dez 11 2018, Florian Weimer <fweimer@redhat.com> wrote:
>>
>>> * Andreas Schwab:
>>>
>>>> +volatile int do_exit;
>>>
>>> Please no volatile, and use the GCC __atomic builtins instead (not the
>>> glibc-internal ones, which are inaccessible).
>>
>> It's only about the compiler not optimizing the access, no atomicity
>> required.
>
> No, without atomics, the code has a data race and undefined behavior.

In which way?  There is a single setter, and it doesn't matter how long
the thread takes to see the transition from zero to non-zero.

Andreas.

-- 
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Re: [PATCH] Fix rwlock stall with PREFER_WRITER_NONRECURSIVE_NP (bug 23861)

[Florian Weimer]

* Andreas Schwab:

> On Dez 11 2018, Florian Weimer <fweimer@redhat.com> wrote:
>
>> * Andreas Schwab:
>>
>>> +volatile int do_exit;
>>
>> Please no volatile, and use the GCC __atomic builtins instead (not the
>> glibc-internal ones, which are inaccessible).
>
> It's only about the compiler not optimizing the access, no atomicity
> required.

No, without atomics, the code has a data race and undefined behavior.

Thanks,
Florian

Re: [PATCH] Fix rwlock stall with PREFER_WRITER_NONRECURSIVE_NP (bug 23861)

[Andreas Schwab]

On Dez 11 2018, Florian Weimer <fweimer@redhat.com> wrote:

> * Andreas Schwab:
>
>> +volatile int do_exit;
>
> Please no volatile, and use the GCC __atomic builtins instead (not the
> glibc-internal ones, which are inaccessible).

It's only about the compiler not optimizing the access, no atomicity
required.

Andreas.

-- 
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Re: [PATCH] Fix rwlock stall with PREFER_WRITER_NONRECURSIVE_NP (bug 23861)

[Florian Weimer]

* Andreas Schwab:

> +volatile int do_exit;

Please no volatile, and use the GCC __atomic builtins instead (not the
glibc-internal ones, which are inaccessible).  I think the minimum GCC
version does not yet support proper C11 atomics.

Thanks,
Florian

[PATCH] Fix rwlock stall with PREFER_WRITER_NONRECURSIVE_NP (bug 23861)

[Andreas Schwab]

	[BZ #23861]
	* nptl/pthread_rwlock_common.c (__pthread_rwlock_rdlock_full):
	Update expected value for __readers while waiting on
	PTHREAD_RWLOCK_RWAITING.
	* nptl/tst-rwlock-pwn.c: New file.
	* nptl/Makefile (tests): Add tst-rwlock-pwn.
---
 nptl/Makefile                |  3 +-
 nptl/pthread_rwlock_common.c |  2 +-
 nptl/tst-rwlock-pwn.c        | 82 ++++++++++++++++++++++++++++++++++++
 3 files changed, 85 insertions(+), 2 deletions(-)
 create mode 100644 nptl/tst-rwlock-pwn.c

diff --git a/nptl/Makefile b/nptl/Makefile
index 34ae830276..b01f2b0626 100644
--- a/nptl/Makefile
+++ b/nptl/Makefile
@@ -318,7 +318,8 @@ tests = tst-attr1 tst-attr2 tst-attr3 tst-default-attr \
 	tst-minstack-throw \
 	tst-cnd-basic tst-mtx-trylock tst-cnd-broadcast \
 	tst-cnd-timedwait tst-thrd-detach tst-mtx-basic tst-thrd-sleep \
-	tst-mtx-recursive tst-tss-basic tst-call-once tst-mtx-timedlock
+	tst-mtx-recursive tst-tss-basic tst-call-once tst-mtx-timedlock \
+	tst-rwlock-pwn
 
 tests-internal := tst-rwlock19 tst-rwlock20 \
 		  tst-sem11 tst-sem12 tst-sem13 \
diff --git a/nptl/pthread_rwlock_common.c b/nptl/pthread_rwlock_common.c
index 6662536812..e55bf5431a 100644
--- a/nptl/pthread_rwlock_common.c
+++ b/nptl/pthread_rwlock_common.c
@@ -314,7 +314,7 @@ __pthread_rwlock_rdlock_full (pthread_rwlock_t *rwlock,
 		 harmless because the flag is just about the state of
 		 __readers, and all threads set the flag under the same
 		 conditions.  */
-	      while ((atomic_load_relaxed (&rwlock->__data.__readers)
+	      while (((r = atomic_load_relaxed (&rwlock->__data.__readers))
 		      & PTHREAD_RWLOCK_RWAITING) != 0)
 		{
 		  int private = __pthread_rwlock_get_private (rwlock);
diff --git a/nptl/tst-rwlock-pwn.c b/nptl/tst-rwlock-pwn.c
new file mode 100644
index 0000000000..57a5034515
--- /dev/null
+++ b/nptl/tst-rwlock-pwn.c
@@ -0,0 +1,82 @@
+/* Test rwlock with PREFER_WRITER_NONRECURSIVE_NP.
+   Copyright (C) 2018 Free Software Foundation, Inc.
+   This file is part of the GNU C Library.
+
+   The GNU C Library is free software; you can redistribute it and/or
+   modify it under the terms of the GNU Lesser General Public
+   License as published by the Free Software Foundation; either
+   version 2.1 of the License, or (at your option) any later version.
+
+   The GNU C Library 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
+   Lesser General Public License for more details.
+
+   You should have received a copy of the GNU Lesser General Public
+   License along with the GNU C Library; if not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+#include <pthread.h>
+#include <support/xthread.h>
+
+/* We choose 10 iterations and 3 threads because this happens to be able
+   to trigger the stall today on modern hardware.  */
+#define LOOPS 10
+#define NTHREADS 3
+
+volatile int do_exit;
+pthread_rwlockattr_t mylock_attr;
+pthread_rwlock_t mylock;
+
+void *
+run_loop (void *a)
+{
+  while (!do_exit)
+    {
+      if (random () & 1)
+	{
+	  xpthread_rwlock_wrlock (&mylock);
+	  xpthread_rwlock_unlock (&mylock);
+	}
+      else
+	{
+	  xpthread_rwlock_rdlock (&mylock);
+	  xpthread_rwlock_unlock (&mylock);
+	}
+    }
+  return NULL;
+}
+
+int
+do_test (void)
+{
+  xpthread_rwlockattr_init (&mylock_attr);
+  xpthread_rwlockattr_setkind_np (&mylock_attr,
+				  PTHREAD_RWLOCK_PREFER_WRITER_NONRECURSIVE_NP);
+  xpthread_rwlock_init (&mylock, &mylock_attr);
+
+  for (int n = 0; n < LOOPS; n++)
+    {
+      pthread_t tids[NTHREADS];
+      do_exit = 0;
+      for (int i = 0; i < NTHREADS; i++)
+	tids[i] = xpthread_create (NULL, run_loop, NULL);
+      /* Let the threads run for some time.  */
+      sleep (1);
+      printf ("Exiting...");
+      fflush (stdout);
+      do_exit = 1;
+      for (int i = 0; i < NTHREADS; i++)
+	xpthread_join (tids[i]);
+      printf ("done.\n");
+    }
+  pthread_rwlock_destroy (&mylock);
+  pthread_rwlockattr_destroy (&mylock_attr);
+  return 0;
+}
+
+#define TIMEOUT (DEFAULT_TIMEOUT + 3 * LOOPS)
+#include <support/test-driver.c>
-- 
2.20.0


-- 
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."