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

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).

On 01/02/2017 02:26 PM, Torvald Riegel wrote:
> 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).


These look good to me.

> 

> 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;


OK. Move the overflow check later in the code to catch all cases.

>      }

>    /* 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);


OK.

>      }

>  

>    return 0;