Skip to contentSkip to conversation

locking/rwsem: Remove arch specific rwsem files

PATCH Superseded Waiman Long 4 participants 11 messages Feb 11, 2019 – Feb 13, 2019

Subsystems (12)
Arm (32-bit) x86 PowerPC arm64 +8 more subsystems

v2 of 5 Superseded Latest is v5 →

lore
Share & tools
lore

Waiman Long

author reviewer
#0 lore raw

v2 cover locking/rwsem: Remove arch specific rwsem files

v2:
- Add patch 2 to optimize __down_read_trylock() as suggested by PeterZ.
- Update performance test data in patch 1.

This is part 0 of my rwsem patchset. It just removes the architecture specific files to make it easer to add enhancements in the upcoming rwsem patches.

Since the two ll/sc platforms that I can tested on (arm64 & ppc) are both using the generic C codes, the rwsem performance shouldn't be affected by this patch except the down_read_trylock() code which was included in patch 2 for arm64.

Waiman Long (2):
locking/rwsem: Remove arch specific rwsem files
locking/rwsem: Optimize down_read_trylock()

 MAINTAINERS                     |   1 -
 arch/alpha/include/asm/rwsem.h  | 211 -----------------------------------
 arch/arm/include/asm/Kbuild     |   1 -
 arch/arm64/include/asm/Kbuild   |   1 -
 arch/hexagon/include/asm/Kbuild |   1 -
 arch/ia64/include/asm/rwsem.h   | 172 -----------------------------
 arch/powerpc/include/asm/Kbuild |   1 -
 arch/s390/include/asm/Kbuild    |   1 -
 arch/sh/include/asm/Kbuild      |   1 -
 arch/sparc/include/asm/Kbuild   |   1 -
 arch/x86/include/asm/rwsem.h    | 237 ----------------------------------------
 arch/x86/lib/Makefile           |   1 -
 arch/x86/lib/rwsem.S            | 156 --------------------------
 arch/xtensa/include/asm/Kbuild  |   1 -
 include/asm-generic/rwsem.h     | 140 ------------------------
 include/linux/rwsem.h           |   4 +-
 kernel/locking/percpu-rwsem.c   |   2 +
 kernel/locking/rwsem.h          | 130 ++++++++++++++++++++++
 18 files changed, 133 insertions(+), 929 deletions(-)
 delete mode 100644 arch/alpha/include/asm/rwsem.h
 delete mode 100644 arch/ia64/include/asm/rwsem.h
 delete mode 100644 arch/x86/include/asm/rwsem.h
 delete mode 100644 arch/x86/lib/rwsem.S
 delete mode 100644 include/asm-generic/rwsem.h
Signature · 1 line
1.8.3.1
author reviewer
#1 lore raw

PATCH v2 1/2 locking/rwsem: Remove arch specific rwsem files

As the generic rwsem-xadd code is using the appropriate acquire and release versions of the atomic operations, the arch specific rwsem.h files will not be that much faster than the generic code as long as the atomic functions are properly implemented. So we can remove those arch specific rwsem.h and stop building asm/rwsem.h to reduce maintenance effort.

Currently, only x86, alpha and ia64 have implemented architecture specific fast paths. I don't have access to alpha and ia64 systems for testing, but they are legacy systems that are not likely to be updated to the latest kernel anyway.

By using a rwsem microbenchmark, the total locking rates on a 4-socket 56-core 112-thread x86-64 system before and after the patch were as follows (mixed means equal # of read and write locks):

Before Patch After Patch

   # of Threads  wlock   rlock   mixed     wlock   rlock   mixed
   ------------  -----   -----   -----     -----   -----   -----
        1        29,201  30,143  29,458    28,615  30,172  29,201
        2         6,807  13,299   1,171     7,725  15,025   1,804
        4         6,504  12,755   1,520     7,127  14,286   1,345
        8         6,762  13,412     764     6,826  13,652     726
       16         6,693  15,408     662     6,599  15,938     626
       32         6,145  15,286     496     5,549  15,487     511
       64         5,812  15,495      60     5,858  15,572      60

There were some run-to-run variations for the multi-thread tests. For x86-64, using the generic C code fast path seems to be a little bit faster than the assembly version with low lock contention. Looking at the assembly version of the fast paths, there are assembly to/from C code wrappers that save and restore all the callee-clobbered registers (7 registers on x86-64). The assembly generated from the generic C code doesn't need to do that. That may explain the slight performance gain here.

The generic asm rwsem.h can also be merged into kernel/locking/rwsem.h with no code change as no other code other than those under kernel/locking needs to access the internal rwsem macros and functions.

---
 MAINTAINERS                     |   1 -
 arch/alpha/include/asm/rwsem.h  | 211 -----------------------------------
 arch/arm/include/asm/Kbuild     |   1 -
 arch/arm64/include/asm/Kbuild   |   1 -
 arch/hexagon/include/asm/Kbuild |   1 -
 arch/ia64/include/asm/rwsem.h   | 172 -----------------------------
 arch/powerpc/include/asm/Kbuild |   1 -
 arch/s390/include/asm/Kbuild    |   1 -
 arch/sh/include/asm/Kbuild      |   1 -
 arch/sparc/include/asm/Kbuild   |   1 -
 arch/x86/include/asm/rwsem.h    | 237 ----------------------------------------
 arch/x86/lib/Makefile           |   1 -
 arch/x86/lib/rwsem.S            | 156 --------------------------
 arch/xtensa/include/asm/Kbuild  |   1 -
 include/asm-generic/rwsem.h     | 140 ------------------------
 include/linux/rwsem.h           |   4 +-
 kernel/locking/percpu-rwsem.c   |   2 +
 kernel/locking/rwsem.h          | 130 ++++++++++++++++++++++
 18 files changed, 133 insertions(+), 929 deletions(-)
 delete mode 100644 arch/alpha/include/asm/rwsem.h
 delete mode 100644 arch/ia64/include/asm/rwsem.h
 delete mode 100644 arch/x86/include/asm/rwsem.h
 delete mode 100644 arch/x86/lib/rwsem.S
 delete mode 100644 include/asm-generic/rwsem.h
MAINTAINERS +0 -1
index 9919840..053f536 100644
@@ -8926,7 +8926,6 @@ F:	arch/*/include/asm/spinlock*.h
 F:	include/linux/rwlock*.h
 F:	include/linux/mutex*.h
 F:	include/linux/rwsem*.h
-F:	arch/*/include/asm/rwsem.h
 F:	include/linux/seqlock.h
 F:	lib/locking*.[ch]
 F:	kernel/locking/
arch/alpha/include/asm/rwsem.h deleted +0 -211

211 lines not on this page · raw message

arch/arm/include/asm/Kbuild +0 -1
index 1d66db9..989e1a7 100644
@@ -12,7 +12,6 @@ generic-y += mm-arch-hooks.h
 generic-y += msi.h
 generic-y += parport.h
 generic-y += preempt.h
-generic-y += rwsem.h
 generic-y += seccomp.h
 generic-y += segment.h
 generic-y += serial.h
arch/arm64/include/asm/Kbuild +0 -1
index 1e17ea5..60a933b 100644
@@ -16,7 +16,6 @@ generic-y += mm-arch-hooks.h
 generic-y += msi.h
 generic-y += qrwlock.h
 generic-y += qspinlock.h
-generic-y += rwsem.h
 generic-y += segment.h
 generic-y += serial.h
 generic-y += set_memory.h
arch/hexagon/include/asm/Kbuild +0 -1
index b25fd42..0a12feb 100644
@@ -26,7 +26,6 @@ generic-y += mm-arch-hooks.h
 generic-y += pci.h
 generic-y += percpu.h
 generic-y += preempt.h
-generic-y += rwsem.h
 generic-y += sections.h
 generic-y += segment.h
 generic-y += serial.h
arch/ia64/include/asm/rwsem.h deleted +0 -172

172 lines not on this page · raw message

arch/powerpc/include/asm/Kbuild +0 -1
index 77ff7fb..75bd77a 100644
@@ -9,6 +9,5 @@ generic-y += irq_work.h
 generic-y += local64.h
 generic-y += mcs_spinlock.h
 generic-y += preempt.h
-generic-y += rwsem.h
 generic-y += vtime.h
 generic-y += msi.h
arch/s390/include/asm/Kbuild +0 -1
index e323977..4b77b42 100644
@@ -21,7 +21,6 @@ generic-y += local64.h
 generic-y += mcs_spinlock.h
 generic-y += mm-arch-hooks.h
 generic-y += preempt.h
-generic-y += rwsem.h
 generic-y += trace_clock.h
 generic-y += unaligned.h
 generic-y += word-at-a-time.h
arch/sh/include/asm/Kbuild +0 -1
index a6ef3fe..b89fce4 100644
@@ -16,7 +16,6 @@ generic-y += mm-arch-hooks.h
 generic-y += parport.h
 generic-y += percpu.h
 generic-y += preempt.h
-generic-y += rwsem.h
 generic-y += serial.h
 generic-y += sizes.h
 generic-y += trace_clock.h
arch/sparc/include/asm/Kbuild +0 -1
index b82f64e..e843fc0 100644
@@ -17,7 +17,6 @@ generic-y += mm-arch-hooks.h
 generic-y += module.h
 generic-y += msi.h
 generic-y += preempt.h
-generic-y += rwsem.h
 generic-y += serial.h
 generic-y += trace_clock.h
 generic-y += word-at-a-time.h
arch/x86/include/asm/rwsem.h deleted +0 -237

237 lines not on this page · raw message

arch/x86/lib/Makefile +0 -1
index 140e618..9866520 100644
@@ -23,7 +23,6 @@ obj-$(CONFIG_SMP) += msr-smp.o cache-smp.o
 lib-y := delay.o misc.o cmdline.o cpu.o
 lib-y += usercopy_$(BITS).o usercopy.o getuser.o putuser.o
 lib-y += memcpy_$(BITS).o
-lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o
 lib-$(CONFIG_INSTRUCTION_DECODER) += insn.o inat.o insn-eval.o
 lib-$(CONFIG_RANDOMIZE_BASE) += kaslr.o
 lib-$(CONFIG_FUNCTION_ERROR_INJECTION)	+= error-inject.o
arch/x86/lib/rwsem.S deleted +0 -156

156 lines not on this page · raw message

arch/xtensa/include/asm/Kbuild +0 -1
index e255683..7026b37 100644
@@ -23,7 +23,6 @@ generic-y += mm-arch-hooks.h
 generic-y += param.h
 generic-y += percpu.h
 generic-y += preempt.h
-generic-y += rwsem.h
 generic-y += sections.h
 generic-y += topology.h
 generic-y += trace_clock.h
include/asm-generic/rwsem.h deleted +0 -140

140 lines not on this page · raw message

include/linux/rwsem.h +1 -3
index 67dbb57..6e56006 100644
@@ -57,15 +57,13 @@ struct rw_semaphore {
 extern struct rw_semaphore *rwsem_wake(struct rw_semaphore *);
 extern struct rw_semaphore *rwsem_downgrade_wake(struct rw_semaphore *sem);
 
-/* Include the arch specific part */
-#include <asm/rwsem.h>
-
 /* In all implementations count != 0 means locked */
 static inline int rwsem_is_locked(struct rw_semaphore *sem)
 {
 	return atomic_long_read(&sem->count) != 0;
 }
 
+#define RWSEM_UNLOCKED_VALUE		0L
 #define __RWSEM_INIT_COUNT(name)	.count = ATOMIC_LONG_INIT(RWSEM_UNLOCKED_VALUE)
 #endif
 
kernel/locking/percpu-rwsem.c +2 -0
index 883cf1b..f17dad9 100644
@@ -7,6 +7,8 @@
 #include <linux/sched.h>
 #include <linux/errno.h>
 
+#include "rwsem.h"
+
 int __percpu_init_rwsem(struct percpu_rw_semaphore *sem,
 			const char *name, struct lock_class_key *rwsem_key)
 {
kernel/locking/rwsem.h +130 -0

139 lines not on this page · raw message

Signature · 1 line
1.8.3.1
author reviewer
#2 lore raw

PATCH v2 2/2 locking/rwsem: Optimize down_read_trylock()

In reply to Waiman Long

Modify __down_read_trylock() to make it generate slightly better code (smaller and maybe a tiny bit faster).

Before this patch, down_read_trylock:

   0x0000000000000000 <+0>:     callq  0x5 <down_read_trylock+5>
   0x0000000000000005 <+5>:     jmp    0x18 <down_read_trylock+24>
   0x0000000000000007 <+7>:     lea    0x1(%rdx),%rcx
   0x000000000000000b <+11>:    mov    %rdx,%rax
   0x000000000000000e <+14>:    lock cmpxchg %rcx,(%rdi)
   0x0000000000000013 <+19>:    cmp    %rax,%rdx
   0x0000000000000016 <+22>:    je     0x23 <down_read_trylock+35>
   0x0000000000000018 <+24>:    mov    (%rdi),%rdx
   0x000000000000001b <+27>:    test   %rdx,%rdx
   0x000000000000001e <+30>:    jns    0x7 <down_read_trylock+7>
   0x0000000000000020 <+32>:    xor    %eax,%eax
   0x0000000000000022 <+34>:    retq
   0x0000000000000023 <+35>:    mov    %gs:0x0,%rax
   0x000000000000002c <+44>:    or     $0x3,%rax
   0x0000000000000030 <+48>:    mov    %rax,0x20(%rdi)
   0x0000000000000034 <+52>:    mov    $0x1,%eax
   0x0000000000000039 <+57>:    retq

After patch, down_read_trylock:

   0x0000000000000000 <+0>:     callq  0x5 <down_read_trylock+5>
   0x0000000000000005 <+5>:     mov    (%rdi),%rax
   0x0000000000000008 <+8>:     test   %rax,%rax
   0x000000000000000b <+11>:    js     0x2f <down_read_trylock+47>
   0x000000000000000d <+13>:    lea    0x1(%rax),%rdx
   0x0000000000000011 <+17>:    lock cmpxchg %rdx,(%rdi)
   0x0000000000000016 <+22>:    jne    0x8 <down_read_trylock+8>
   0x0000000000000018 <+24>:    mov    %gs:0x0,%rax
   0x0000000000000021 <+33>:    or     $0x3,%rax
   0x0000000000000025 <+37>:    mov    %rax,0x20(%rdi)
   0x0000000000000029 <+41>:    mov    $0x1,%eax
   0x000000000000002e <+46>:    retq
   0x000000000000002f <+47>:    xor    %eax,%eax
   0x0000000000000031 <+49>:    retq

By using a rwsem microbenchmark, the down_read_trylock() rate on a x86-64 system before and after the patch were:

Before Patch After Patch

   # of Threads     rlock           rlock
   ------------     -----           -----
        1           27,787          28,259
        2            8,359           9,234

On a ARM64 system, the performance results were:

Before Patch After Patch

   # of Threads     rlock           rlock
   ------------     -----           -----
        1           24,155          25,000
        2            6,820           8,699
---
 kernel/locking/rwsem.h | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)
kernel/locking/rwsem.h +4 -4
index 067e265..028bc33 100644
@@ -175,11 +175,11 @@ static inline int __down_read_killable(struct rw_semaphore *sem)
 
 static inline int __down_read_trylock(struct rw_semaphore *sem)
 {
-	long tmp;
+	long tmp = atomic_long_read(&sem->count);
 
-	while ((tmp = atomic_long_read(&sem->count)) >= 0) {
-		if (tmp == atomic_long_cmpxchg_acquire(&sem->count, tmp,
-				   tmp + RWSEM_ACTIVE_READ_BIAS)) {
+	while (tmp >= 0) {
+		if (atomic_long_try_cmpxchg_acquire(&sem->count, &tmp,
+					tmp + RWSEM_ACTIVE_READ_BIAS)) {
 			return 1;
 		}
 	}
Signature · 1 line
1.8.3.1
maintainer
#3 lore raw

Re: [PATCH v2 2/2] locking/rwsem: Optimize down_read_trylock()

Quoted 40 lines · Waiman Long

Modify __down_read_trylock() to make it generate slightly better code (smaller and maybe a tiny bit faster).

Before this patch, down_read_trylock:

   0x0000000000000000 <+0>:     callq  0x5 <down_read_trylock+5>
   0x0000000000000005 <+5>:     jmp    0x18 <down_read_trylock+24>
   0x0000000000000007 <+7>:     lea    0x1(%rdx),%rcx
   0x000000000000000b <+11>:    mov    %rdx,%rax
   0x000000000000000e <+14>:    lock cmpxchg %rcx,(%rdi)
   0x0000000000000013 <+19>:    cmp    %rax,%rdx
   0x0000000000000016 <+22>:    je     0x23 <down_read_trylock+35>
   0x0000000000000018 <+24>:    mov    (%rdi),%rdx
   0x000000000000001b <+27>:    test   %rdx,%rdx
   0x000000000000001e <+30>:    jns    0x7 <down_read_trylock+7>
   0x0000000000000020 <+32>:    xor    %eax,%eax
   0x0000000000000022 <+34>:    retq
   0x0000000000000023 <+35>:    mov    %gs:0x0,%rax
   0x000000000000002c <+44>:    or     $0x3,%rax
   0x0000000000000030 <+48>:    mov    %rax,0x20(%rdi)
   0x0000000000000034 <+52>:    mov    $0x1,%eax
   0x0000000000000039 <+57>:    retq

After patch, down_read_trylock:

   0x0000000000000000 <+0>:     callq  0x5 <down_read_trylock+5>
   0x0000000000000005 <+5>:     mov    (%rdi),%rax
   0x0000000000000008 <+8>:     test   %rax,%rax
   0x000000000000000b <+11>:    js     0x2f <down_read_trylock+47>
   0x000000000000000d <+13>:    lea    0x1(%rax),%rdx
   0x0000000000000011 <+17>:    lock cmpxchg %rdx,(%rdi)
   0x0000000000000016 <+22>:    jne    0x8 <down_read_trylock+8>
   0x0000000000000018 <+24>:    mov    %gs:0x0,%rax
   0x0000000000000021 <+33>:    or     $0x3,%rax
   0x0000000000000025 <+37>:    mov    %rax,0x20(%rdi)
   0x0000000000000029 <+41>:    mov    $0x1,%eax
   0x000000000000002e <+46>:    retq
   0x000000000000002f <+47>:    xor    %eax,%eax
   0x0000000000000031 <+49>:    retq
Quoted 8 lines

By using a rwsem microbenchmark, the down_read_trylock() rate on a x86-64 system before and after the patch were:

Before Patch After Patch

   # of Threads     rlock           rlock
   ------------     -----           -----
        1           27,787          28,259
        2            8,359           9,234

From 1/2:

1        29,201  30,143  29,458    28,615  30,172  29,201
2         6,807  13,299   1,171     7,725  15,025   1,804
Quoted 38 lines

On a ARM64 system, the performance results were:

Before Patch After Patch

   # of Threads     rlock           rlock
   ------------     -----           -----
        1           24,155          25,000
        2            6,820           8,699
---
 kernel/locking/rwsem.h | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)
kernel/locking/rwsem.h +4 -4
index 067e265..028bc33 100644
@@ -175,11 +175,11 @@ static inline int __down_read_killable(struct rw_semaphore *sem)
 
 static inline int __down_read_trylock(struct rw_semaphore *sem)
 {
-	long tmp;
+	long tmp = atomic_long_read(&sem->count);
 
-	while ((tmp = atomic_long_read(&sem->count)) >= 0) {
-		if (tmp == atomic_long_cmpxchg_acquire(&sem->count, tmp,
-				   tmp + RWSEM_ACTIVE_READ_BIAS)) {
+	while (tmp >= 0) {
+		if (atomic_long_try_cmpxchg_acquire(&sem->count, &tmp,
+					tmp + RWSEM_ACTIVE_READ_BIAS)) {
 			return 1;
 		}
 	}
Signature · 1 line
1.8.3.1
maintainer
#4 lore raw

Re: [PATCH v2 2/2] locking/rwsem: Optimize down_read_trylock()

Quoted 50 lines · Peter Zijlstra
Quoted 40 lines · Waiman Long

Modify __down_read_trylock() to make it generate slightly better code (smaller and maybe a tiny bit faster).

Before this patch, down_read_trylock:

   0x0000000000000000 <+0>:     callq  0x5 <down_read_trylock+5>
   0x0000000000000005 <+5>:     jmp    0x18 <down_read_trylock+24>
   0x0000000000000007 <+7>:     lea    0x1(%rdx),%rcx
   0x000000000000000b <+11>:    mov    %rdx,%rax
   0x000000000000000e <+14>:    lock cmpxchg %rcx,(%rdi)
   0x0000000000000013 <+19>:    cmp    %rax,%rdx
   0x0000000000000016 <+22>:    je     0x23 <down_read_trylock+35>
   0x0000000000000018 <+24>:    mov    (%rdi),%rdx
   0x000000000000001b <+27>:    test   %rdx,%rdx
   0x000000000000001e <+30>:    jns    0x7 <down_read_trylock+7>
   0x0000000000000020 <+32>:    xor    %eax,%eax
   0x0000000000000022 <+34>:    retq
   0x0000000000000023 <+35>:    mov    %gs:0x0,%rax
   0x000000000000002c <+44>:    or     $0x3,%rax
   0x0000000000000030 <+48>:    mov    %rax,0x20(%rdi)
   0x0000000000000034 <+52>:    mov    $0x1,%eax
   0x0000000000000039 <+57>:    retq

After patch, down_read_trylock:

   0x0000000000000000 <+0>:     callq  0x5 <down_read_trylock+5>
   0x0000000000000005 <+5>:     mov    (%rdi),%rax
   0x0000000000000008 <+8>:     test   %rax,%rax
   0x000000000000000b <+11>:    js     0x2f <down_read_trylock+47>
   0x000000000000000d <+13>:    lea    0x1(%rax),%rdx
   0x0000000000000011 <+17>:    lock cmpxchg %rdx,(%rdi)
   0x0000000000000016 <+22>:    jne    0x8 <down_read_trylock+8>
   0x0000000000000018 <+24>:    mov    %gs:0x0,%rax
   0x0000000000000021 <+33>:    or     $0x3,%rax
   0x0000000000000025 <+37>:    mov    %rax,0x20(%rdi)
   0x0000000000000029 <+41>:    mov    $0x1,%eax
   0x000000000000002e <+46>:    retq
   0x000000000000002f <+47>:    xor    %eax,%eax
   0x0000000000000031 <+49>:    retq
Quoted 8 lines

By using a rwsem microbenchmark, the down_read_trylock() rate on a x86-64 system before and after the patch were:

Before Patch After Patch

   # of Threads     rlock           rlock
   ------------     -----           -----
        1           27,787          28,259
        2            8,359           9,234
Quoted 4 lines

From 1/2:

1        29,201  30,143  29,458    28,615  30,172  29,201
2         6,807  13,299   1,171     7,725  15,025   1,804

Argh, fat fingered and send before I was done typing.

What I wanted to say was; those rlock numbers don't match up. What gives?

The before _this_ patch number of 27k787 should be the same as the after first patch number of 30k172.

author reviewer
#5 lore raw

Re: [PATCH v2 2/2] locking/rwsem: Optimize down_read_trylock()

Quoted 54 lines · Peter Zijlstra
Quoted 49 lines · Peter Zijlstra
Quoted 40 lines · Waiman Long

Modify __down_read_trylock() to make it generate slightly better code (smaller and maybe a tiny bit faster).

Before this patch, down_read_trylock:

   0x0000000000000000 <+0>:     callq  0x5 <down_read_trylock+5>
   0x0000000000000005 <+5>:     jmp    0x18 <down_read_trylock+24>
   0x0000000000000007 <+7>:     lea    0x1(%rdx),%rcx
   0x000000000000000b <+11>:    mov    %rdx,%rax
   0x000000000000000e <+14>:    lock cmpxchg %rcx,(%rdi)
   0x0000000000000013 <+19>:    cmp    %rax,%rdx
   0x0000000000000016 <+22>:    je     0x23 <down_read_trylock+35>
   0x0000000000000018 <+24>:    mov    (%rdi),%rdx
   0x000000000000001b <+27>:    test   %rdx,%rdx
   0x000000000000001e <+30>:    jns    0x7 <down_read_trylock+7>
   0x0000000000000020 <+32>:    xor    %eax,%eax
   0x0000000000000022 <+34>:    retq
   0x0000000000000023 <+35>:    mov    %gs:0x0,%rax
   0x000000000000002c <+44>:    or     $0x3,%rax
   0x0000000000000030 <+48>:    mov    %rax,0x20(%rdi)
   0x0000000000000034 <+52>:    mov    $0x1,%eax
   0x0000000000000039 <+57>:    retq

After patch, down_read_trylock:

   0x0000000000000000 <+0>:     callq  0x5 <down_read_trylock+5>
   0x0000000000000005 <+5>:     mov    (%rdi),%rax
   0x0000000000000008 <+8>:     test   %rax,%rax
   0x000000000000000b <+11>:    js     0x2f <down_read_trylock+47>
   0x000000000000000d <+13>:    lea    0x1(%rax),%rdx
   0x0000000000000011 <+17>:    lock cmpxchg %rdx,(%rdi)
   0x0000000000000016 <+22>:    jne    0x8 <down_read_trylock+8>
   0x0000000000000018 <+24>:    mov    %gs:0x0,%rax
   0x0000000000000021 <+33>:    or     $0x3,%rax
   0x0000000000000025 <+37>:    mov    %rax,0x20(%rdi)
   0x0000000000000029 <+41>:    mov    $0x1,%eax
   0x000000000000002e <+46>:    retq
   0x000000000000002f <+47>:    xor    %eax,%eax
   0x0000000000000031 <+49>:    retq
Quoted 8 lines

By using a rwsem microbenchmark, the down_read_trylock() rate on a x86-64 system before and after the patch were:

Before Patch After Patch

   # of Threads     rlock           rlock
   ------------     -----           -----
        1           27,787          28,259
        2            8,359           9,234
Quoted 4 lines

From 1/2:

1        29,201  30,143  29,458    28,615  30,172  29,201
2         6,807  13,299   1,171     7,725  15,025   1,804
Quoted 7 lines

Argh, fat fingered and send before I was done typing.

What I wanted to say was; those rlock numbers don't match up. What gives?

The before _this_ patch number of 27k787 should be the same as the after first patch number of 30k172.

The rlock number in patch 1 refers to down_read() which uses xadd. The number here in patch 2 refers specifically to down_read_trylock() which uses cmpxchg() as this patch changes only __down_read_tryulock(). So the performance data differ.

Cheers,
Longman

author reviewer
#6 lore raw

Re: [PATCH v2 2/2] locking/rwsem: Optimize down_read_trylock()

Quoted 60 lines · Waiman Long
Quoted 59 lines · Peter Zijlstra
Quoted 49 lines · Peter Zijlstra
Quoted 40 lines · Waiman Long

Modify __down_read_trylock() to make it generate slightly better code (smaller and maybe a tiny bit faster).

Before this patch, down_read_trylock:

   0x0000000000000000 <+0>:     callq  0x5 <down_read_trylock+5>
   0x0000000000000005 <+5>:     jmp    0x18 <down_read_trylock+24>
   0x0000000000000007 <+7>:     lea    0x1(%rdx),%rcx
   0x000000000000000b <+11>:    mov    %rdx,%rax
   0x000000000000000e <+14>:    lock cmpxchg %rcx,(%rdi)
   0x0000000000000013 <+19>:    cmp    %rax,%rdx
   0x0000000000000016 <+22>:    je     0x23 <down_read_trylock+35>
   0x0000000000000018 <+24>:    mov    (%rdi),%rdx
   0x000000000000001b <+27>:    test   %rdx,%rdx
   0x000000000000001e <+30>:    jns    0x7 <down_read_trylock+7>
   0x0000000000000020 <+32>:    xor    %eax,%eax
   0x0000000000000022 <+34>:    retq
   0x0000000000000023 <+35>:    mov    %gs:0x0,%rax
   0x000000000000002c <+44>:    or     $0x3,%rax
   0x0000000000000030 <+48>:    mov    %rax,0x20(%rdi)
   0x0000000000000034 <+52>:    mov    $0x1,%eax
   0x0000000000000039 <+57>:    retq

After patch, down_read_trylock:

   0x0000000000000000 <+0>:     callq  0x5 <down_read_trylock+5>
   0x0000000000000005 <+5>:     mov    (%rdi),%rax
   0x0000000000000008 <+8>:     test   %rax,%rax
   0x000000000000000b <+11>:    js     0x2f <down_read_trylock+47>
   0x000000000000000d <+13>:    lea    0x1(%rax),%rdx
   0x0000000000000011 <+17>:    lock cmpxchg %rdx,(%rdi)
   0x0000000000000016 <+22>:    jne    0x8 <down_read_trylock+8>
   0x0000000000000018 <+24>:    mov    %gs:0x0,%rax
   0x0000000000000021 <+33>:    or     $0x3,%rax
   0x0000000000000025 <+37>:    mov    %rax,0x20(%rdi)
   0x0000000000000029 <+41>:    mov    $0x1,%eax
   0x000000000000002e <+46>:    retq
   0x000000000000002f <+47>:    xor    %eax,%eax
   0x0000000000000031 <+49>:    retq
Quoted 8 lines

By using a rwsem microbenchmark, the down_read_trylock() rate on a x86-64 system before and after the patch were:

Before Patch After Patch

   # of Threads     rlock           rlock
   ------------     -----           -----
        1           27,787          28,259
        2            8,359           9,234
Quoted 4 lines

From 1/2:

1        29,201  30,143  29,458    28,615  30,172  29,201
2         6,807  13,299   1,171     7,725  15,025   1,804

Argh, fat fingered and send before I was done typing.

What I wanted to say was; those rlock numbers don't match up. What gives?

Quoted 6 lines
Quoted 2 lines

The before _this_ patch number of 27k787 should be the same as the after first patch number of 30k172.

The rlock number in patch 1 refers to down_read() which uses xadd. The number here in patch 2 refers specifically to down_read_trylock() which uses cmpxchg() as this patch changes only __down_read_tryulock(). So the performance data differ.

You can see that the performance is worse if we use cmpxchg for down_read instead of using xadd.

Cheers,
Longman

#7 lore raw

Re: [PATCH v2 2/2] locking/rwsem: Optimize down_read_trylock()

In reply to Waiman Long
Quoted 3 lines · Waiman Long

Modify __down_read_trylock() to make it generate slightly better code (smaller and maybe a tiny bit faster).

This looks good, but I would ask you to try one slightly different approach.

Instead of this:

Quoted 8 lines
       long tmp = atomic_long_read(&sem->count);

       while (tmp >= 0) {
               if (atomic_long_try_cmpxchg_acquire(&sem->count, &tmp,
                                       tmp + RWSEM_ACTIVE_READ_BIAS)) {
                       return 1;
               }
       }

try doing this instead:

        long tmp = 0;

        do {
                if (atomic_long_try_cmpxchg_acquire(&sem->count, &tmp,
                                        tmp + RWSEM_ACTIVE_READ_BIAS)) {
                        return 1;
        } while (tmp >= 0);
        return 0;

because especially when it comes to locking, it's usually better to just *guess* that the lock is unlocked, than it is to actually read from the line to see what the state is.

Often - but certainly not always - the lock is the first access to the target cacheline, and assuming the trylock is successful (which I think is the case we want to optimize for), we're much better off causing that first access to be a read-for-ownership, rather than a read-for-sharing.

Because if you first read from the line, and then do a cmpxchg, and if the line was not in the cache, your cache coherency protocol will generally go through two states: first shared (for the initial read) and then exclusive-dirty (for the cmpxchg).

Now, this is obviously very micro-architecture dependent, and in fact the microarchitecture could even see the "predict fallthrough to a cmpxchg with the same address" and turn the first read into a read-for-ownership, but we've done this at some point before, and the "guess unlocked" was actually the one that performed better.

Of course, the downside is that it might be worse when the guess is incorrect - either because of a nested read lock or due to an actual conflict with a write, but on the whole those *should* be the rare cases, and not the cases where we necessarily optimize for latency of the operation.

Hmm?

Linus

author reviewer
#8 lore raw

Re: [PATCH v2 2/2] locking/rwsem: Optimize down_read_trylock()

Quoted 47 lines · Linus Torvalds
Quoted 2 lines · Waiman Long

Modify __down_read_trylock() to make it generate slightly better code (smaller and maybe a tiny bit faster).

This looks good, but I would ask you to try one slightly different approach.

Instead of this:

Quoted 8 lines
       long tmp = atomic_long_read(&sem->count);

       while (tmp >= 0) {
               if (atomic_long_try_cmpxchg_acquire(&sem->count, &tmp,
                                       tmp + RWSEM_ACTIVE_READ_BIAS)) {
                       return 1;
               }
       }

try doing this instead:

        long tmp = 0;

        do {
                if (atomic_long_try_cmpxchg_acquire(&sem->count, &tmp,
                                        tmp + RWSEM_ACTIVE_READ_BIAS)) {
                        return 1;
        } while (tmp >= 0);
        return 0;

because especially when it comes to locking, it's usually better to just *guess* that the lock is unlocked, than it is to actually read from the line to see what the state is.

Often - but certainly not always - the lock is the first access to the target cacheline, and assuming the trylock is successful (which I think is the case we want to optimize for), we're much better off causing that first access to be a read-for-ownership, rather than a read-for-sharing.

Because if you first read from the line, and then do a cmpxchg, and if the line was not in the cache, your cache coherency protocol will generally go through two states: first shared (for the initial read) and then exclusive-dirty (for the cmpxchg).

Now, this is obviously very micro-architecture dependent, and in fact the microarchitecture could even see the "predict fallthrough to a cmpxchg with the same address" and turn the first read into a read-for-ownership, but we've done this at some point before, and the "guess unlocked" was actually the one that performed better.

Quoted 7 lines

Of course, the downside is that it might be worse when the guess is incorrect - either because of a nested read lock or due to an actual conflict with a write, but on the whole those *should* be the rare cases, and not the cases where we necessarily optimize for latency of the operation.

Hmm?

I looked at the assembly code in arch/x86/include/asm/rwsem.h. For both trylocks (read & write), the count is read first before attempting to lock it. We did the same for all trylock functions in other locks. Depending on how the trylock is used and how contended the lock is, it may help or hurt performance. Changing down_read_trylock to do an unconditional cmpxchg will change the performance profile of existing code. So I would prefer keeping the current code.

I do notice now that the generic down_write_trylock() code is doing an unconditional compxchg. So I wonder if we should change it to read the lock first like other trylocks or just leave it as it is.

Cheers,
Longman

#9 lore raw

Re: [PATCH v2 2/2] locking/rwsem: Optimize down_read_trylock()

Quoted 11 lines · Waiman Long

I looked at the assembly code in arch/x86/include/asm/rwsem.h. For both trylocks (read & write), the count is read first before attempting to lock it. We did the same for all trylock functions in other locks. Depending on how the trylock is used and how contended the lock is, it may help or hurt performance. Changing down_read_trylock to do an unconditional cmpxchg will change the performance profile of existing code. So I would prefer keeping the current code.

I do notice now that the generic down_write_trylock() code is doing an unconditional compxchg. So I wonder if we should change it to read the lock first like other trylocks or just leave it as it is.

No, I think we should instead move the other trylocks to the try-for-ownership model as well, like Linus suggested.

That's the general assumption we make in locking primitives, that we optimize for the common, expected case - which would be that the trylock succeeds, and I don't see why trylock primitives should be different.

In fact I can see more ways for read-for-sharing to perform suboptimally on larger systems.

Thanks,

Ingo

author reviewer
#10 lore raw

Re: [PATCH v2 2/2] locking/rwsem: Optimize down_read_trylock()

Quoted 16 lines · Ingo Molnar
Quoted 11 lines · Waiman Long

I looked at the assembly code in arch/x86/include/asm/rwsem.h. For both trylocks (read & write), the count is read first before attempting to lock it. We did the same for all trylock functions in other locks. Depending on how the trylock is used and how contended the lock is, it may help or hurt performance. Changing down_read_trylock to do an unconditional cmpxchg will change the performance profile of existing code. So I would prefer keeping the current code.

I do notice now that the generic down_write_trylock() code is doing an unconditional compxchg. So I wonder if we should change it to read the lock first like other trylocks or just leave it as it is.

No, I think we should instead move the other trylocks to the try-for-ownership model as well, like Linus suggested.

Quoted 6 lines

That's the general assumption we make in locking primitives, that we optimize for the common, expected case - which would be that the trylock succeeds, and I don't see why trylock primitives should be different.

In fact I can see more ways for read-for-sharing to perform suboptimally on larger systems.

I don't mind changing to the try-for-ownership model for rwsem and mutex. I do have some concern to do that for spinlock. Some of the lock slowpath code do optimistic trylock. Making them unconditional cmpxchg will impact lock contention performance.

I will update this rwsem patch to make the change while I am working on it. For other locks, I will suggest we go slow and carefully evaluate the performance implication before we make the changes.

Cheers,
Longman