Linux Virtualization - Jun 2014 - [PATCH v11 06/16] qspinlock: prolong the stay in the pending bit path

On Fri, May 30, 2014 at 11:43:52AM -0400, Waiman Long
wrote:
> ---
>  kernel/locking/qspinlock.c |   18 ++++++++++++++++--
>  1 files changed, 16 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
> index fc7fd8c..7f10758 100644
> --- a/kernel/locking/qspinlock.c
> +++ b/kernel/locking/qspinlock.c
> @@ -233,11 +233,25 @@ void queue_spin_lock_slowpath(struct qspinlock *lock,
u32 val)
>  	 */
>  	for (;;) {
>  		/*
> -		 * If we observe any contention; queue.
> +		 * If we observe that the queue is not empty or both
> +		 * the pending and lock bits are set, queue
>  		 */
> -		if (val & ~_Q_LOCKED_MASK)
> +		if ((val & _Q_TAIL_MASK) ||
> +		    (val == (_Q_LOCKED_VAL|_Q_PENDING_VAL)))
>  			goto queue;
>  
> +		if (val == _Q_PENDING_VAL) {
> +			/*
> +			 * Pending bit is set, but not the lock bit.
> +			 * Assuming that the pending bit holder is going to
> +			 * set the lock bit and clear the pending bit soon,
> +			 * it is better to wait than to exit at this point.
> +			 */
> +			cpu_relax();
> +			val = atomic_read(&lock->val);
> +			continue;
> +		}
> +
>  		new = _Q_LOCKED_VAL;
>  		if (val == new)
>  			new |= _Q_PENDING_VAL;

So, again, you just posted a new version without replying to the
previous discussion; so let me try again, what's wrong with the proposal
here:

  lkml.kernel.org/r/20140417163640.GT11096 at twins.programming.kicks-ass.net


-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 836 bytes
Desc: not available
URL:
<http://lists.linuxfoundation.org/pipermail/virtualization/attachments/20140611/3db76015/attachment.sig>

On 6/11/2014 6:26 AM, Peter Zijlstra wrote:
> On Fri, May 30, 2014 at 11:43:52AM -0400, Waiman Long wrote:
>> ---
>>   kernel/locking/qspinlock.c |   18 ++++++++++++++++--
>>   1 files changed, 16 insertions(+), 2 deletions(-)
>>
>> diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
>> index fc7fd8c..7f10758 100644
>> --- a/kernel/locking/qspinlock.c
>> +++ b/kernel/locking/qspinlock.c
>> @@ -233,11 +233,25 @@ void queue_spin_lock_slowpath(struct qspinlock
*lock, u32 val)
>>   	 */
>>   	for (;;) {
>>   		/*
>> -		 * If we observe any contention; queue.
>> +		 * If we observe that the queue is not empty or both
>> +		 * the pending and lock bits are set, queue
>>   		 */
>> -		if (val & ~_Q_LOCKED_MASK)
>> +		if ((val & _Q_TAIL_MASK) ||
>> +		    (val == (_Q_LOCKED_VAL|_Q_PENDING_VAL)))
>>   			goto queue;
>>   
>> +		if (val == _Q_PENDING_VAL) {
>> +			/*
>> +			 * Pending bit is set, but not the lock bit.
>> +			 * Assuming that the pending bit holder is going to
>> +			 * set the lock bit and clear the pending bit soon,
>> +			 * it is better to wait than to exit at this point.
>> +			 */
>> +			cpu_relax();
>> +			val = atomic_read(&lock->val);
>> +			continue;
>> +		}
>> +
>>   		new = _Q_LOCKED_VAL;
>>   		if (val == new)
>>   			new |= _Q_PENDING_VAL;
>
> So, again, you just posted a new version without replying to the
> previous discussion; so let me try again, what's wrong with the
proposal
> here:
>
>    lkml.kernel.org/r/20140417163640.GT11096 at
twins.programming.kicks-ass.net
>
>
I thought I had answered you before, maybe the message was lost or the 
answer was not complete. Anyway, I will try to response to your question 
again here.
> Wouldn't something like:
>
>	while (atomic_read(&lock->val) == _Q_PENDING_VAL)
>		cpu_relax();
>
> before the cmpxchg loop have gotten you all this?
That is not exactly the same. The loop will exit if other bits are set or the
pending
bit cleared. In the case, we will need to do the same check at the beginning of
the
for loop in order to avoid doing an extra cmpxchg that is not necessary.

> I just tried this on my code and I cannot see a difference.
As I said before, I did see a difference with that change. I think it 
depends on the CPU chip that we used for testing. I ran my test on a 
10-core Westmere-EX chip. I run my microbench on different pairs of core 
within the same chip. It produces different results that varies from 
779.5ms to up to 1192ms. Without that patch, the lowest value I can get 
is still close to 800ms, but the highest can be up to 1800ms or so. So I 
believe it is just a matter of timing that you did not observed in your 
test machine.

-Longman

On Wed, Jun 11, 2014 at 05:22:28PM -0400, Long, Wai Man wrote:
> >>@@ -233,11 +233,25 @@ void queue_spin_lock_slowpath(struct
qspinlock *lock, u32 val)
> >>  	 */
> >>  	for (;;) {
> >>  		/*
> >>-		 * If we observe any contention; queue.
> >>+		 * If we observe that the queue is not empty or both
> >>+		 * the pending and lock bits are set, queue
> >>  		 */
> >>-		if (val & ~_Q_LOCKED_MASK)
> >>+		if ((val & _Q_TAIL_MASK) ||
> >>+		    (val == (_Q_LOCKED_VAL|_Q_PENDING_VAL)))
> >>  			goto queue;
> >>+		if (val == _Q_PENDING_VAL) {
> >>+			/*
> >>+			 * Pending bit is set, but not the lock bit.
> >>+			 * Assuming that the pending bit holder is going to
> >>+			 * set the lock bit and clear the pending bit soon,
> >>+			 * it is better to wait than to exit at this point.
> >>+			 */
> >>+			cpu_relax();
> >>+			val = atomic_read(&lock->val);
> >>+			continue;
> >>+		}
> >>+
> >>  		new = _Q_LOCKED_VAL;
> >>  		if (val == new)
> >>  			new |= _Q_PENDING_VAL;
> >Wouldn't something like:
> >
> >	while (atomic_read(&lock->val) == _Q_PENDING_VAL)
> >		cpu_relax();
> >
> >before the cmpxchg loop have gotten you all this?
> 
> That is not exactly the same. The loop will exit if other bits are set or
the pending
> bit cleared. In the case, we will need to do the same check at the
beginning of the
> for loop in order to avoid doing an extra cmpxchg that is not necessary.
If other bits get set we should stop poking at the pending bit and get
queued. The only transition we want to wait for is: 0,1,0 -> 0,0,1.

What extra unneeded cmpxchg() is there? If we have two cpus waiting in
this loop for the pending bit to go away then both will attempt to grab
the now free pending bit, one will loose and get queued?

There's no avoiding that contention.


-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 836 bytes
Desc: not available
URL:
<http://lists.linuxfoundation.org/pipermail/virtualization/attachments/20140612/74010a8c/attachment.sig>