[PATCH] lockref: use cmpxchg64 explicitly for lockless updates

[PATCH] lockref: use cmpxchg64 explicitly for lockless updates

[Will Deacon]

The cmpxchg() function tends not to support 64-bit arguments on 32-bit
architectures. This could be either due to use of unsigned long arguments
(like on ARM) or lack of instruction support (cmpxchgq on x86). However,
these architectures may implement a specific cmpxchg64() function to
provide 64-bit cmpxchg support instead.

Since the lockref code requires a 64-bit cmpxchg and relies on the
architecture selecting ARCH_USE_CMPXCHG_LOCKREF, move to using cmpxchg64
instead of cmpxchg and allow 32-bit architectures to make use of the
lockless lockref implementation.

Cc: Waiman Long <Waiman.Long@hp.com>
Signed-off-by: Will Deacon <will.deacon@arm.com>
---

An alternative to this patch is to go through the 32-bit architectures
that implement cmpxchg64, reworking their cmpxchg definitions to switch
to the 64-bit version based on the sizeof the argument.

 lib/lockref.c | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/lib/lockref.c b/lib/lockref.c
index e2cd2c0..677d036 100644
--- a/lib/lockref.c
+++ b/lib/lockref.c
@@ -14,8 +14,8 @@
 	while (likely(arch_spin_value_unlocked(old.lock.rlock.raw_lock))) {  	\
 		struct lockref new = old, prev = old;				\
 		CODE								\
-		old.lock_count = cmpxchg(&lockref->lock_count,			\
-					 old.lock_count, new.lock_count);	\
+		old.lock_count = cmpxchg64(&lockref->lock_count,		\
+					   old.lock_count, new.lock_count);	\
 		if (likely(old.lock_count == prev.lock_count)) {		\
 			SUCCESS;						\
 		}								\
-- 
1.8.2.2

Re: [PATCH] lockref: use cmpxchg64 explicitly for lockless updates

[Linus Torvalds]

On Thu, Sep 19, 2013 at 1:06 PM, Will Deacon <will.deacon@arm.com> wrote:
> The cmpxchg() function tends not to support 64-bit arguments on 32-bit
> architectures. This could be either due to use of unsigned long arguments
> (like on ARM) or lack of instruction support (cmpxchgq on x86). However,
> these architectures may implement a specific cmpxchg64() function to
> provide 64-bit cmpxchg support instead

I'm certainly ok with this, but I wonder how much point there is to
use the cmpxchg alternatives for 32-bit architectures at all...

>From a performance standpoint, lockref really is expected to mainly
help with big machines. Only insane people would do big machines with
32-bit kernels these days.

Of course, it may be that cmpxchg is actually faster on some
architectures, but at least on x86-32, cmpxchg8b is traditionally
quite slow.

In other words, I'd actually like to see some numbers if there are
loads where this actually helps and matters...

                   Linus

Re: [PATCH] lockref: use cmpxchg64 explicitly for lockless updates

[Waiman Long]

On 09/19/2013 02:11 PM, Linus Torvalds wrote:
> On Thu, Sep 19, 2013 at 1:06 PM, Will Deacon<will.deacon@arm.com>  wrote:
>> The cmpxchg() function tends not to support 64-bit arguments on 32-bit
>> architectures. This could be either due to use of unsigned long arguments
>> (like on ARM) or lack of instruction support (cmpxchgq on x86). However,
>> these architectures may implement a specific cmpxchg64() function to
>> provide 64-bit cmpxchg support instead
> I'm certainly ok with this, but I wonder how much point there is to
> use the cmpxchg alternatives for 32-bit architectures at all...
>
>  From a performance standpoint, lockref really is expected to mainly
> help with big machines. Only insane people would do big machines with
> 32-bit kernels these days.
> Of course, it may be that cmpxchg is actually faster on some
> architectures, but at least on x86-32, cmpxchg8b is traditionally
> quite slow.
>
> In other words, I'd actually like to see some numbers if there are
> loads where this actually helps and matters...
>
>                     Linus

I agreed that 32-bit machines are not likely to be big enough to get 
benefit from this feature. However, I do see a minor problem with the 
current code. If a user tries to turn on CMPXCHG_LOCKREF on a 32-bit 
build, he/she will get a compilation error because a 64-bit data type is 
not supported in 32-bit mode's cmpxchg(). Because of this, my original 
patch also uses cmpxchg64() which is equivalent to cmpxchg() in 64-bit 
machine for 64-bit data type.

I would suggest either change to use cmpxchg64() or add the dependence 
line "depends on 64BIT" to CMPXCHG_LOCKREF.

-Longman

Re: [PATCH] lockref: use cmpxchg64 explicitly for lockless updates

[Will Deacon]

On Thu, Sep 19, 2013 at 07:11:32PM +0100, Linus Torvalds wrote:
> On Thu, Sep 19, 2013 at 1:06 PM, Will Deacon <will.deacon@arm.com> wrote:
> > The cmpxchg() function tends not to support 64-bit arguments on 32-bit
> > architectures. This could be either due to use of unsigned long arguments
> > (like on ARM) or lack of instruction support (cmpxchgq on x86). However,
> > these architectures may implement a specific cmpxchg64() function to
> > provide 64-bit cmpxchg support instead
> 
> I'm certainly ok with this, but I wonder how much point there is to
> use the cmpxchg alternatives for 32-bit architectures at all...
> 
> From a performance standpoint, lockref really is expected to mainly
> help with big machines. Only insane people would do big machines with
> 32-bit kernels these days.

Our definitions of "big" machines probably differ significantly, but it
would be interesting to see if this *does* make a difference on some of the
multi-cluster ARMv7 hardware. Unfortunately, my development boards are all
I/O bound, so I'll need to leave a strategically placed crate of
non-poisoned beer next to the server guys' office...

> Of course, it may be that cmpxchg is actually faster on some
> architectures, but at least on x86-32, cmpxchg8b is traditionally
> quite slow.

On ARMv7, our double-word exclusives shouldn't be slower than the word
exclusives (hell, everything apart from the machine registers will be >=
64-bit).

> In other words, I'd actually like to see some numbers if there are
> loads where this actually helps and matters...

That's fair enough; I just saw the new lockref stuff, thought "that's a cool
hack" then looked at playing with it on ARM. I'll go see what this AIM7
thing is all about...

Cheers,

Will

Re: [PATCH] lockref: use cmpxchg64 explicitly for lockless updates

[Will Deacon]

On Fri, Sep 20, 2013 at 11:08:06AM +0100, Will Deacon wrote:
> On Thu, Sep 19, 2013 at 07:11:32PM +0100, Linus Torvalds wrote:
> > From a performance standpoint, lockref really is expected to mainly
> > help with big machines. Only insane people would do big machines with
> > 32-bit kernels these days.
> 
> Our definitions of "big" machines probably differ significantly, but it
> would be interesting to see if this *does* make a difference on some of the
> multi-cluster ARMv7 hardware.

[...]

> > In other words, I'd actually like to see some numbers if there are
> > loads where this actually helps and matters...
> 
> That's fair enough; I just saw the new lockref stuff, thought "that's a cool
> hack" then looked at playing with it on ARM. I'll go see what this AIM7
> thing is all about...

Right, turns out I can get some interesting numbers from your simple t.c
program on my dual-cluster, 5 CPU ARMv7 machine. The new cmpxchg-based lockref
code gives ~50% improvement, but the fun part is that implementing cmpxchg64
without memory barriers doubles this win to ~100% over current mainline.

If we can guarantee that the CODE just messes around with the lockref, those
barriers probably aren't needed...

As for AIM7/re-aim, I'm having a hard time getting repeatable numbers out of
it to establish a baseline, so it's not proving to be especially helpful.

Will

Re: [PATCH] lockref: use cmpxchg64 explicitly for lockless updates

[Linus Torvalds]

On Fri, Sep 20, 2013 at 10:45 AM, Will Deacon <will.deacon@arm.com> wrote:
>
> Right, turns out I can get some interesting numbers from your simple t.c
> program on my dual-cluster, 5 CPU ARMv7 machine. The new cmpxchg-based lockref
> code gives ~50% improvement, but the fun part is that implementing cmpxchg64
> without memory barriers doubles this win to ~100% over current mainline.

Ok, that's certainly noticeable.

> If we can guarantee that the CODE just messes around with the lockref, those
> barriers probably aren't needed...

Yes. I've been thyinking about the barrier issue, and as far as I can
see, as long as the lockref code only ever messes with the reference
count, a totally unordered cmpxchg is fine.

And at least right now we indeed only ever mess with the reference count.

I have been idly toying with the concept of using the cmpxchg also for
possibly taking the lock (for the "xyz_or_lock" versions), but every
time I look at it it seems unlikely to help, and it would require
memory ordering and various architecture-dependent issues, so I
suspect it's never going to make much sense. So yes, an unordered
cmpxchg64 should be perfectly fine.

> As for AIM7/re-aim, I'm having a hard time getting repeatable numbers out of
> it to establish a baseline, so it's not proving to be especially helpful.

That's fine, and yeah, I doubt the t.c improvement really shows
anywhere else (it's kind of extreme), but your numbers are certainly
already sufficient to say "ok, it makes sense even on 32-bit
machines".

                  Linus

Re: [PATCH] lockref: use cmpxchg64 explicitly for lockless updates

[Will Deacon]

On Fri, Sep 20, 2013 at 05:00:19PM +0100, Linus Torvalds wrote:
> On Fri, Sep 20, 2013 at 10:45 AM, Will Deacon <will.deacon@arm.com> wrote:
> > If we can guarantee that the CODE just messes around with the lockref, those
> > barriers probably aren't needed...
> 
> Yes. I've been thyinking about the barrier issue, and as far as I can
> see, as long as the lockref code only ever messes with the reference
> count, a totally unordered cmpxchg is fine.

The only problem then is the use of cmpxchg64 by the sched_clock code.
Whilst most sched_clock() implementations probably have barrier semantics
due to I/O access, that's certainly not true everywhere so I don't think
the cmpxchg64 there can be relaxed safely.

We could add cmpxchg64_relaxed (at the risk of confusing it with the relaxed
I/O accessors, which aren't well defined)? That might help Tony with ia64
too.

> And at least right now we indeed only ever mess with the reference count.
> 
> I have been idly toying with the concept of using the cmpxchg also for
> possibly taking the lock (for the "xyz_or_lock" versions), but every
> time I look at it it seems unlikely to help, and it would require
> memory ordering and various architecture-dependent issues, so I
> suspect it's never going to make much sense. So yes, an unordered
> cmpxchg64 should be perfectly fine.

Yikes, using cmpxchg for the locking sounds scary. For the contended case, I
think spinlocks would be better since they might have back-off and/or
fairness logic which we'd lose if we somehow moved exclusively to cmpxchg.

> > As for AIM7/re-aim, I'm having a hard time getting repeatable numbers out of
> > it to establish a baseline, so it's not proving to be especially helpful.
> 
> That's fine, and yeah, I doubt the t.c improvement really shows
> anywhere else (it's kind of extreme), but your numbers are certainly
> already sufficient to say "ok, it makes sense even on 32-bit
> machines".

Great, thanks.

Will