[PATCH] locking/rwsem: Optimize write lock slowpath

[PATCH] locking/rwsem: Optimize write lock slowpath

[Jason Low]

When acquiring the rwsem write lock in the slowpath, we first try
to set count to RWSEM_WAITING_BIAS. When that is successful,
we then atomically add the RWSEM_WAITING_BIAS in cases where
there are other tasks on the wait list. This causes write lock
operations to often issue multiple atomic operations.

We can instead make the list_is_singular() check first, and then
set the count accordingly, so that we issue at most 1 atomic
operation when acquiring the write lock and reduce unnecessary
cacheline contention.

Signed-off-by: Jason Low <jason.low2@hp.com>
---
 kernel/locking/rwsem-xadd.c | 20 +++++++++++++-------
 1 file changed, 13 insertions(+), 7 deletions(-)

diff --git a/kernel/locking/rwsem-xadd.c b/kernel/locking/rwsem-xadd.c
index df4dcb8..23c33e6 100644
--- a/kernel/locking/rwsem-xadd.c
+++ b/kernel/locking/rwsem-xadd.c
@@ -258,14 +258,20 @@ EXPORT_SYMBOL(rwsem_down_read_failed);
 static inline bool rwsem_try_write_lock(long count, struct rw_semaphore *sem)
 {
 	/*
-	 * Try acquiring the write lock. Check count first in order
-	 * to reduce unnecessary expensive cmpxchg() operations.
+	 * Avoid trying to acquire write lock if count isn't RWSEM_WAITING_BIAS.
 	 */
-	if (count == RWSEM_WAITING_BIAS &&
-	    cmpxchg_acquire(&sem->count, RWSEM_WAITING_BIAS,
-		    RWSEM_ACTIVE_WRITE_BIAS) == RWSEM_WAITING_BIAS) {
-		if (!list_is_singular(&sem->wait_list))
-			rwsem_atomic_update(RWSEM_WAITING_BIAS, sem);
+	if (count != RWSEM_WAITING_BIAS)
+		return false;
+
+	/*
+	 * Acquire the lock by trying to set it to ACTIVE_WRITE_BIAS. If there
+	 * are other tasks on the wait list, we need to add on WAITING_BIAS.
+	 */
+	count = list_is_singular(&sem->wait_list) ?
+			RWSEM_ACTIVE_WRITE_BIAS :
+			RWSEM_ACTIVE_WRITE_BIAS + RWSEM_WAITING_BIAS;
+
+	if (cmpxchg_acquire(&sem->count, RWSEM_WAITING_BIAS, count) == RWSEM_WAITING_BIAS) {
 		rwsem_set_owner(sem);
 		return true;
 	}
-- 
2.1.4

Re: [PATCH] locking/rwsem: Optimize write lock slowpath

[Waiman Long]

On 05/09/2016 03:16 PM, Jason Low wrote:
> When acquiring the rwsem write lock in the slowpath, we first try
> to set count to RWSEM_WAITING_BIAS. When that is successful,
> we then atomically add the RWSEM_WAITING_BIAS in cases where
> there are other tasks on the wait list. This causes write lock
> operations to often issue multiple atomic operations.
>
> We can instead make the list_is_singular() check first, and then
> set the count accordingly, so that we issue at most 1 atomic
> operation when acquiring the write lock and reduce unnecessary
> cacheline contention.
>
> Signed-off-by: Jason Low<jason.low2@hp.com>
> ---
>   kernel/locking/rwsem-xadd.c | 20 +++++++++++++-------
>   1 file changed, 13 insertions(+), 7 deletions(-)
>
> diff --git a/kernel/locking/rwsem-xadd.c b/kernel/locking/rwsem-xadd.c
> index df4dcb8..23c33e6 100644
> --- a/kernel/locking/rwsem-xadd.c
> +++ b/kernel/locking/rwsem-xadd.c
> @@ -258,14 +258,20 @@ EXPORT_SYMBOL(rwsem_down_read_failed);
>   static inline bool rwsem_try_write_lock(long count, struct rw_semaphore *sem)
>   {
>   	/*
> -	 * Try acquiring the write lock. Check count first in order
> -	 * to reduce unnecessary expensive cmpxchg() operations.
> +	 * Avoid trying to acquire write lock if count isn't RWSEM_WAITING_BIAS.
>   	 */
> -	if (count == RWSEM_WAITING_BIAS&&
> -	    cmpxchg_acquire(&sem->count, RWSEM_WAITING_BIAS,
> -		    RWSEM_ACTIVE_WRITE_BIAS) == RWSEM_WAITING_BIAS) {
> -		if (!list_is_singular(&sem->wait_list))
> -			rwsem_atomic_update(RWSEM_WAITING_BIAS, sem);
> +	if (count != RWSEM_WAITING_BIAS)
> +		return false;
> +
> +	/*
> +	 * Acquire the lock by trying to set it to ACTIVE_WRITE_BIAS. If there
> +	 * are other tasks on the wait list, we need to add on WAITING_BIAS.
> +	 */
> +	count = list_is_singular(&sem->wait_list) ?
> +			RWSEM_ACTIVE_WRITE_BIAS :
> +			RWSEM_ACTIVE_WRITE_BIAS + RWSEM_WAITING_BIAS;
> +
> +	if (cmpxchg_acquire(&sem->count, RWSEM_WAITING_BIAS, count) == RWSEM_WAITING_BIAS) {
>   		rwsem_set_owner(sem);
>   		return true;
>   	}

Acked-by: Waiman Long<Waiman.Long@hpe.com>

Re: [PATCH] locking/rwsem: Optimize write lock slowpath

[Peter Zijlstra]

On Mon, May 09, 2016 at 12:16:37PM -0700, Jason Low wrote:
> When acquiring the rwsem write lock in the slowpath, we first try
> to set count to RWSEM_WAITING_BIAS. When that is successful,
> we then atomically add the RWSEM_WAITING_BIAS in cases where
> there are other tasks on the wait list. This causes write lock
> operations to often issue multiple atomic operations.
> 
> We can instead make the list_is_singular() check first, and then
> set the count accordingly, so that we issue at most 1 atomic
> operation when acquiring the write lock and reduce unnecessary
> cacheline contention.
> 
> Signed-off-by: Jason Low <jason.low2@hp.com>
> ---
>  kernel/locking/rwsem-xadd.c | 20 +++++++++++++-------
>  1 file changed, 13 insertions(+), 7 deletions(-)
> 
> diff --git a/kernel/locking/rwsem-xadd.c b/kernel/locking/rwsem-xadd.c
> index df4dcb8..23c33e6 100644
> --- a/kernel/locking/rwsem-xadd.c
> +++ b/kernel/locking/rwsem-xadd.c
> @@ -258,14 +258,20 @@ EXPORT_SYMBOL(rwsem_down_read_failed);
>  static inline bool rwsem_try_write_lock(long count, struct rw_semaphore *sem)
>  {
>  	/*
> +	 * Avoid trying to acquire write lock if count isn't RWSEM_WAITING_BIAS.
>  	 */
> +	if (count != RWSEM_WAITING_BIAS)
> +		return false;
> +
> +	/*
> +	 * Acquire the lock by trying to set it to ACTIVE_WRITE_BIAS. If there
> +	 * are other tasks on the wait list, we need to add on WAITING_BIAS.
> +	 */
> +	count = list_is_singular(&sem->wait_list) ?
> +			RWSEM_ACTIVE_WRITE_BIAS :
> +			RWSEM_ACTIVE_WRITE_BIAS + RWSEM_WAITING_BIAS;
> +
> +	if (cmpxchg_acquire(&sem->count, RWSEM_WAITING_BIAS, count) == RWSEM_WAITING_BIAS) {
>  		rwsem_set_owner(sem);
>  		return true;
>  	}

Right; so that whole thing works because we're holding sem->wait_lock.
Should we clarify that someplace?

Also; should we not make rw_semaphore::count an atomic_long_t and kill
rwsem_atomic_{update,add}() ?

Re: [PATCH] locking/rwsem: Optimize write lock slowpath

[Jason Low]

On Wed, 2016-05-11 at 13:49 +0200, Peter Zijlstra wrote:
> On Mon, May 09, 2016 at 12:16:37PM -0700, Jason Low wrote:
> > When acquiring the rwsem write lock in the slowpath, we first try
> > to set count to RWSEM_WAITING_BIAS. When that is successful,
> > we then atomically add the RWSEM_WAITING_BIAS in cases where
> > there are other tasks on the wait list. This causes write lock
> > operations to often issue multiple atomic operations.
> > 
> > We can instead make the list_is_singular() check first, and then
> > set the count accordingly, so that we issue at most 1 atomic
> > operation when acquiring the write lock and reduce unnecessary
> > cacheline contention.
> > 
> > Signed-off-by: Jason Low <jason.low2@hp.com>
> > ---
> >  kernel/locking/rwsem-xadd.c | 20 +++++++++++++-------
> >  1 file changed, 13 insertions(+), 7 deletions(-)
> > 
> > diff --git a/kernel/locking/rwsem-xadd.c b/kernel/locking/rwsem-xadd.c
> > index df4dcb8..23c33e6 100644
> > --- a/kernel/locking/rwsem-xadd.c
> > +++ b/kernel/locking/rwsem-xadd.c
> > @@ -258,14 +258,20 @@ EXPORT_SYMBOL(rwsem_down_read_failed);
> >  static inline bool rwsem_try_write_lock(long count, struct rw_semaphore *sem)
> >  {
> >  	/*
> > +	 * Avoid trying to acquire write lock if count isn't RWSEM_WAITING_BIAS.
> >  	 */
> > +	if (count != RWSEM_WAITING_BIAS)
> > +		return false;
> > +
> > +	/*
> > +	 * Acquire the lock by trying to set it to ACTIVE_WRITE_BIAS. If there
> > +	 * are other tasks on the wait list, we need to add on WAITING_BIAS.
> > +	 */
> > +	count = list_is_singular(&sem->wait_list) ?
> > +			RWSEM_ACTIVE_WRITE_BIAS :
> > +			RWSEM_ACTIVE_WRITE_BIAS + RWSEM_WAITING_BIAS;
> > +
> > +	if (cmpxchg_acquire(&sem->count, RWSEM_WAITING_BIAS, count) == RWSEM_WAITING_BIAS) {
> >  		rwsem_set_owner(sem);
> >  		return true;
> >  	}
> 
> Right; so that whole thing works because we're holding sem->wait_lock.
> Should we clarify that someplace?

Yup, we can mention that the rwsem_try_write_lock() function must be
called with the wait_lock held.

> Also; should we not make rw_semaphore::count an atomic_long_t and kill
> rwsem_atomic_{update,add}() ?

Right, it's better to just make the variable an atomic and remove the
unnecessary rwsem_atomic_update() "abstraction". I'll send out a
separate patch for this.

Re: [PATCH] locking/rwsem: Optimize write lock slowpath

[Peter Zijlstra]

On Wed, May 11, 2016 at 11:26:02AM -0700, Jason Low wrote:
> On Wed, 2016-05-11 at 13:49 +0200, Peter Zijlstra wrote:

> > >  static inline bool rwsem_try_write_lock(long count, struct rw_semaphore *sem)
> > >  {
> > >  	/*
> > > +	 * Avoid trying to acquire write lock if count isn't RWSEM_WAITING_BIAS.
> > >  	 */
> > > +	if (count != RWSEM_WAITING_BIAS)
> > > +		return false;
> > > +
> > > +	/*
> > > +	 * Acquire the lock by trying to set it to ACTIVE_WRITE_BIAS. If there
> > > +	 * are other tasks on the wait list, we need to add on WAITING_BIAS.
> > > +	 */
> > > +	count = list_is_singular(&sem->wait_list) ?
> > > +			RWSEM_ACTIVE_WRITE_BIAS :
> > > +			RWSEM_ACTIVE_WRITE_BIAS + RWSEM_WAITING_BIAS;
> > > +
> > > +	if (cmpxchg_acquire(&sem->count, RWSEM_WAITING_BIAS, count) == RWSEM_WAITING_BIAS) {
> > >  		rwsem_set_owner(sem);
> > >  		return true;
> > >  	}
> > 
> > Right; so that whole thing works because we're holding sem->wait_lock.
> > Should we clarify that someplace?
> 
> Yup, we can mention that the rwsem_try_write_lock() function must be
> called with the wait_lock held.

Also try to explain _why_ it must be held.

Thanks!

Re: [PATCH] locking/rwsem: Optimize write lock slowpath

[Davidlohr Bueso]

On Wed, 11 May 2016, Peter Zijlstra wrote:

>On Mon, May 09, 2016 at 12:16:37PM -0700, Jason Low wrote:
>> When acquiring the rwsem write lock in the slowpath, we first try
>> to set count to RWSEM_WAITING_BIAS. When that is successful,
>> we then atomically add the RWSEM_WAITING_BIAS in cases where
>> there are other tasks on the wait list. This causes write lock
>> operations to often issue multiple atomic operations.
>>
>> We can instead make the list_is_singular() check first, and then
>> set the count accordingly, so that we issue at most 1 atomic
>> operation when acquiring the write lock and reduce unnecessary
>> cacheline contention.
>>
>> Signed-off-by: Jason Low <jason.low2@hp.com>

Acked-by: Davidlohr Bueso <dave@stgolabs.net>

(one nit: the patch title could be more informative to what
optimization we are talking about here... ie: reduce atomic ops
in writer slowpath' or something.)


>> ---
>>  kernel/locking/rwsem-xadd.c | 20 +++++++++++++-------
>>  1 file changed, 13 insertions(+), 7 deletions(-)
>>
>> diff --git a/kernel/locking/rwsem-xadd.c b/kernel/locking/rwsem-xadd.c
>> index df4dcb8..23c33e6 100644
>> --- a/kernel/locking/rwsem-xadd.c
>> +++ b/kernel/locking/rwsem-xadd.c
>> @@ -258,14 +258,20 @@ EXPORT_SYMBOL(rwsem_down_read_failed);
>>  static inline bool rwsem_try_write_lock(long count, struct rw_semaphore *sem)
>>  {
>>	/*
>> +	 * Avoid trying to acquire write lock if count isn't RWSEM_WAITING_BIAS.
>>	 */
>> +	if (count != RWSEM_WAITING_BIAS)
>> +		return false;
>> +
>> +	/*
>> +	 * Acquire the lock by trying to set it to ACTIVE_WRITE_BIAS. If there
>> +	 * are other tasks on the wait list, we need to add on WAITING_BIAS.
>> +	 */
>> +	count = list_is_singular(&sem->wait_list) ?
>> +			RWSEM_ACTIVE_WRITE_BIAS :
>> +			RWSEM_ACTIVE_WRITE_BIAS + RWSEM_WAITING_BIAS;
>> +
>> +	if (cmpxchg_acquire(&sem->count, RWSEM_WAITING_BIAS, count) == RWSEM_WAITING_BIAS) {
>>		rwsem_set_owner(sem);
>>		return true;
>>	}
>
>Right; so that whole thing works because we're holding sem->wait_lock.
>Should we clarify that someplace?

Yes exactly, rwsem_try_write_lock() is always called with the wait_lock held,
unlike the unqueued cousin.

Thanks,
Davidlohr

Re: [PATCH] locking/rwsem: Optimize write lock slowpath

[Jason Low]

On Wed, 2016-05-11 at 11:33 -0700, Davidlohr Bueso wrote:
> On Wed, 11 May 2016, Peter Zijlstra wrote:
> 
> >On Mon, May 09, 2016 at 12:16:37PM -0700, Jason Low wrote:
> >> When acquiring the rwsem write lock in the slowpath, we first try
> >> to set count to RWSEM_WAITING_BIAS. When that is successful,
> >> we then atomically add the RWSEM_WAITING_BIAS in cases where
> >> there are other tasks on the wait list. This causes write lock
> >> operations to often issue multiple atomic operations.
> >>
> >> We can instead make the list_is_singular() check first, and then
> >> set the count accordingly, so that we issue at most 1 atomic
> >> operation when acquiring the write lock and reduce unnecessary
> >> cacheline contention.
> >>
> >> Signed-off-by: Jason Low <jason.low2@hp.com>
> 
> Acked-by: Davidlohr Bueso <dave@stgolabs.net>
> 
> (one nit: the patch title could be more informative to what
> optimization we are talking about here... ie: reduce atomic ops
> in writer slowpath' or something.)

Yeah, the "optimize write lock slowpath" subject is a bit generic. I'll
make the title more specific in the next version.

Thanks,
Jason