| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <535083DC.2040406@hp.com>
Date: Thu, 17 Apr 2014 21:46:04 -0400
From: Waiman Long <waiman.long@...com>
To: Peter Zijlstra <peterz@...radead.org>
CC: Thomas Gleixner <tglx@...utronix.de>,
Ingo Molnar <mingo@...hat.com>,
"H. Peter Anvin" <hpa@...or.com>, linux-arch@...r.kernel.org,
x86@...nel.org, linux-kernel@...r.kernel.org,
virtualization@...ts.linux-foundation.org,
xen-devel@...ts.xenproject.org, kvm@...r.kernel.org,
Paolo Bonzini <paolo.bonzini@...il.com>,
Konrad Rzeszutek Wilk <konrad.wilk@...cle.com>,
"Paul E. McKenney" <paulmck@...ux.vnet.ibm.com>,
Rik van Riel <riel@...hat.com>,
Linus Torvalds <torvalds@...ux-foundation.org>,
Raghavendra K T <raghavendra.kt@...ux.vnet.ibm.com>,
David Vrabel <david.vrabel@...rix.com>,
Oleg Nesterov <oleg@...hat.com>,
Gleb Natapov <gleb@...hat.com>,
Scott J Norton <scott.norton@...com>,
Chegu Vinod <chegu_vinod@...com>
Subject: Re: [PATCH v9 06/19] qspinlock: prolong the stay in the pending bit
path
On 04/17/2014 12:36 PM, Peter Zijlstra wrote:
> On Thu, Apr 17, 2014 at 11:03:58AM -0400, Waiman Long wrote:
>> There is a problem in the current trylock_pending() function. When the
>> lock is free, but the pending bit holder hasn't grabbed the lock&
>> cleared the pending bit yet, the trylock_pending() function will fail.
> I remember seeing some of this..
>
>> It can be seen that the queue spinlock is slower than the ticket
>> spinlock when there are 2 or 3 contending tasks. In all the other case,
>> the queue spinlock is either equal or faster than the ticket spinlock.
> So with my code I get:
>
> qspinlock ticket
>
> local: 2: 8741.853010 2: 8812.042460
> remote: 2: 8549.731795 2: 8709.005695
>
> And that is without this optimization.
>
> Also note that I don't have this cmpxchg loop anymore.
It is a matter of timing. If the contending task enters the pending bit
code path at the right time, it will be able to get pending bit and
wait. If it enters at the wrong time, it will bail out and use the
queuing code path. The patch is just to enlarge the timing windows so
that it won't bail out so easily.
From my own testing, using xchg(), for example, will be a bit faster
than cmpxchg(). The downside of that is that I can guarantee strict
ordering between a pending bit waiter and a queue waiter. So I need to
use cmpxchg to set the lock. This didn't slow thing down that much when
I tested it on a Westmere-EX box, but I saw significant slowdown in
IvyBridge-EX. That is why I trade the use of xchg() with cmpxchg() at
the expense of a bit of slowdown in the pending bit code path.
>> kernel/locking/qspinlock.c | 32 ++++++++++++++++++++++++++++++--
>> 1 files changed, 30 insertions(+), 2 deletions(-)
>>
>> diff --git a/kernel/locking/qspinlock.c b/kernel/locking/qspinlock.c
>> index 55601b4..497da24 100644
>> --- a/kernel/locking/qspinlock.c
>> +++ b/kernel/locking/qspinlock.c
>> @@ -216,6 +216,7 @@ xchg_tail(struct qspinlock *lock, u32 tail, u32 *pval)
>> static inline int trylock_pending(struct qspinlock *lock, u32 *pval)
>> {
>> u32 old, new, val = *pval;
>> + int retry = 1;
>>
>> /*
>> * trylock || pending
>> @@ -225,11 +226,38 @@ static inline int trylock_pending(struct qspinlock *lock, u32 *pval)
>> */
>> for (;;) {
>> /*
>> - * If we observe any contention; queue.
>> + * If we observe that the queue is not empty,
>> + * return and be queued.
>> */
>> - if (val& ~_Q_LOCKED_MASK)
>> + if (val& _Q_TAIL_MASK)
>> return 0;
>>
>> + if ((val& _Q_LOCKED_PENDING_MASK) ==
>> + (_Q_LOCKED_VAL|_Q_PENDING_VAL)) {
>> + /*
>> + * If both the lock and pending bits are set, we wait
>> + * a while to see if that either bit will be cleared.
>> + * If that is no change, we return and be queued.
>> + */
>> + if (!retry)
>> + return 0;
>> + retry--;
>> + cpu_relax();
>> + cpu_relax();
>> + *pval = val = atomic_read(&lock->val);
>> + continue;
> Since you gave up optimizing the _Q_PENDING_BITS != 8 case why bother
> with this? The switch from _Q_PENDING_VAL to _Q_LOCKED_VAL is atomic by
> virtue of your (endian challenged) clear_pending_set_locked().
The code is just to extend the timing window a bit more to include cases
where the lock holder is about to release the lock. It applies to both
cases. However, it is not strictly necessary and I can take it out.
BTW, I didn't test out your atomic_test_and_set() change. Did it provide
a noticeable performance benefit when compared with cmpxchg()?
>> + } else if ((val& _Q_LOCKED_PENDING_MASK) == _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();
>> + *pval = 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?
Yes, you are right. I don't need to do a bitwise AND with
_Q_LOCKED_PENDING_MASK. I will try make the loop a bit simpler.
>
> I just tried this on my code and I cannot see a difference.
Again, it is a matter of timing and it depends on the tests that we
used. My test showed a difference, but not yours. Both can be true.
-Longman
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists