rw_semaphores, optimisations

This patch (made against linux-2.4.4-pre6) makes a number of changes to the rwsem implementation:

(1) Fixes a subtle contention bug between up_write and the down_* functions.

(2) Optimises the i386 fastpath implementation and changed the slowpath implementation to aid it.
- The arch/i386/lib/rwsem.c is now gone.
- Better inline asm constraints have been applied.

(3) Changed the sparc64 fastpath implementation to use revised slowpath interface.
[Dave Miller: can you check this please]

(4) Makes the generic spinlock implementation non-inline.
- lib/rwsem.c has been duplicated to lib/rwsem-spinlock.c and a slightly different algorithm has been created. This one is simpler since it does not have to use atomic operations on the counters as all accesses to them are governed by a blanket spinlock.

David

diff -uNr linux-2.4.4-pre6/arch/i386/kernel/i386_ksyms.c linux/arch/i386/kernel/i386_ksyms.c
@@ -80,11 +80,6 @@
 EXPORT_SYMBOL_NOVERS(__down_failed_interruptible);
 EXPORT_SYMBOL_NOVERS(__down_failed_trylock);
 EXPORT_SYMBOL_NOVERS(__up_wakeup);
-#ifdef CONFIG_RWSEM_XCHGADD_ALGORITHM
-EXPORT_SYMBOL_NOVERS(__rwsem_down_write_failed);
-EXPORT_SYMBOL_NOVERS(__rwsem_down_read_failed);
-EXPORT_SYMBOL_NOVERS(__rwsem_wake);
-#endif
 /* Networking helper routines. */
 EXPORT_SYMBOL(csum_partial_copy_generic);
 /* Delay loops */

diff -uNr linux-2.4.4-pre6/arch/i386/lib/Makefile linux/arch/i386/lib/Makefile
@@ -9,7 +9,7 @@
 
 obj-y = checksum.o old-checksum.o delay.o \
 	usercopy.o getuser.o putuser.o \
-	memcpy.o strstr.o rwsem.o
+	memcpy.o strstr.o
 
 obj-$(CONFIG_X86_USE_3DNOW) += mmx.o
 obj-$(CONFIG_HAVE_DEC_LOCK) += dec_and_lock.o

diff -uNr linux-2.4.4-pre6/arch/i386/lib/rwsem.S linux/arch/i386/lib/rwsem.S
@@ -1,36 +0,0 @@
-/* rwsem.S: R/W semaphores, register saving wrapper function stubs
- *
- * Written by David Howells ([email protected]).
- * Derived from arch/i386/kernel/semaphore.c
- */
-
-.text
-.align 4
-.globl __rwsem_down_read_failed
-__rwsem_down_read_failed:
-	pushl	%edx
-	pushl	%ecx
-	call	rwsem_down_read_failed
-	popl	%ecx
-	popl	%edx
-	ret
-
-.align 4
-.globl __rwsem_down_write_failed
-__rwsem_down_write_failed:
-	pushl	%edx
-	pushl	%ecx
-	call	rwsem_down_write_failed
-	popl	%ecx
-	popl	%edx
-	ret
-
-.align 4
-.globl __rwsem_wake
-__rwsem_wake:
-	pushl	%edx
-	pushl	%ecx
-	call	rwsem_wake
-	popl	%ecx
-	popl	%edx
-	ret

diff -uNr linux-2.4.4-pre6/include/asm-sparc64/rwsem.h linux/include/asm-sparc64/rwsem.h
@@ -2,7 +2,7 @@
  * rwsem.h: R/W semaphores implemented using CAS
  *
  * Written by David S. Miller ([email protected]), 2001.
- * Derived from asm-i386/rwsem-xadd.h
+ * Derived from asm-i386/rwsem.h
  */
 #ifndef _SPARC64_RWSEM_H
 #define _SPARC64_RWSEM_H

@@ -127,14 +127,15 @@
 		"save		%%sp, -160, %%sp\n\t"
 		"mov		%%g2, %%l2\n\t"
 		"mov		%%g3, %%l3\n\t"
+		" mov		%%g7, %%o0\n\t"
 		"call		%1\n\t"
-		" mov		%%g5, %%o0\n\t"
+		" mov		%%g5, %%o1\n\t"
 		"mov		%%l2, %%g2\n\t"
 		"ba,pt		%%xcc, 2b\n\t"
 		" restore	%%l3, %%g0, %%g3\n\t"
 		".previous\n\t"
 		"! ending __up_read"
-		: : "r" (sem), "i" (rwsem_wake),
+		: : "r" (sem), "i" (rwsem_up_read_wake),
 		    "i" (RWSEM_ACTIVE_MASK)
 		: "g1", "g5", "g7", "memory", "cc");
 }

@@ -145,31 +146,28 @@
 		"! beginning __up_write\n\t"
 		"sethi		%%hi(%2), %%g1\n\t"
 		"or		%%g1, %%lo(%2), %%g1\n"
-		"1:\tlduw	[%0], %%g5\n\t"
-		"sub		%%g5, %%g1, %%g7\n\t"
-		"cas		[%0], %%g5, %%g7\n\t"
-		"cmp		%%g5, %%g7\n\t"
-		"bne,pn		%%icc, 1b\n\t"
-		" sub		%%g7, %%g1, %%g7\n\t"
-		"cmp		%%g7, 0\n\t"
-		"bl,pn		%%icc, 3f\n\t"
+		"sub		%%g5, %%g5, %%g5\n\t"
+		"cas		[%0], %%g1, %%g5\n\t"
+		"cmp		%%g1, %%g5\n\t"
+		"bne,pn		%%icc, 1f\n\t"
 		" membar	#StoreStore\n"
 		"2:\n\t"
 		".subsection 2\n"
-		"3:\tmov	%0, %%g5\n\t"
+		"3:\tmov	%0, %%g1\n\t"
 		"save		%%sp, -160, %%sp\n\t"
 		"mov		%%g2, %%l2\n\t"
 		"mov		%%g3, %%l3\n\t"
+		"mov		%%g1, %%o0\n\t"
 		"call		%1\n\t"
-		" mov		%%g5, %%o0\n\t"
+		" mov		%%g5, %%o1\n\t"
 		"mov		%%l2, %%g2\n\t"
 		"ba,pt		%%xcc, 2b\n\t"
 		" restore	%%l3, %%g0, %%g3\n\t"
 		".previous\n\t"
 		"! ending __up_write"
-		: : "r" (sem), "i" (rwsem_wake),
+		: : "r" (sem), "i" (rwsem_up_write_wake),
 		    "i" (RWSEM_ACTIVE_WRITE_BIAS)
-		: "g1", "g5", "g7", "memory", "cc");
+		: "g1", "g5", "memory", "cc");
 }
 
 static inline int rwsem_atomic_update(int delta, struct rw_semaphore *sem)

@@ -191,6 +189,8 @@
 	return tmp + delta;
 }
 
+#define rwsem_atomic_add rwsem_atomic_update
+
 static inline __u16 rwsem_cmpxchgw(struct rw_semaphore *sem, __u16 __old, __u16 __new)
 {
 	u32 old = (sem->count & 0xffff0000) | (u32) __old;

@@ -212,6 +212,11 @@
 		goto again;
 
 	return prev & 0xffff;
+}
+
+static inline signed long rwsem_cmpxchg(struct rw_semaphore *sem, signed long old, signed long new)
+{
+	return cmpxchg(&sem->count,old,new);
 }
 
 #endif /* __KERNEL__ */

diff -uNr linux-2.4.4-pre6/lib/Makefile linux/lib/Makefile
@@ -8,14 +8,12 @@
 
 L_TARGET := lib.a
 
-export-objs := cmdline.o
+export-objs := cmdline.o rwsem-spinlock.o rwsem.o
 
 obj-y := errno.o ctype.o string.o vsprintf.o brlock.o cmdline.o
 
-ifneq ($(CONFIG_RWSEM_GENERIC_SPINLOCK)$(CONFIG_RWSEM_XCHGADD_ALGORITHM),nn)
-export-objs += rwsem.o
-obj-y += rwsem.o
-endif
+obj-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o
+obj-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o
 
 ifneq ($(CONFIG_HAVE_DEC_LOCK),y) 
   obj-y += dec_and_lock.o

I finally finished dropping the list_empty() check from my generic rwsemaphores.

The new behaviour of my rwsemaphores are:

- max sleepers and max simultanous readers both downgraded to 2^(BITS_PER_LONG>>1) for
higher performance in the fast path
- up_* cannot be recalled from irq/softirq context anymore

I'm using this your latest patch on top of vanilla 2.4.4-pre6 to benchmark my new generic rwsemaphores against yours.

To benchmark I'm using your tar.gz but I left my 50 seconds run of the rwtest with many more readers and writers to stress it a bit more (I posted the changes to the rwsem-rw.c test in the message where I reported the race in your semaphores before pre6).

Here the results (I did two tries for every bench and btw the numbers are quite stable as you can see).

rwsem-2.4.4-pre6 + my new generic rwsem (fast path in C inlined)

rw

reads taken: 6499121
writes taken: 3355701
reads taken: 6413447
writes taken: 3311328

r1

reads taken: 15218540
reads taken: 15203915

r2

reads taken: 5087253
reads taken: 5099084

ro

reads taken: 4274607
reads taken: 4280280

w1

writes taken: 14723159
writes taken: 14708296

wo

writes taken: 1778713
writes taken: 1776248

----------------------------------------------
rwsem-2.4.4-pre6 + my new generic rwsem with fast path out of line (fast path in C out of line)

rw

reads taken: 6116063
writes taken: 3157816
reads taken: 6248542
writes taken: 3226122

r1

reads taken: 14092045
reads taken: 14112771

r2

reads taken: 4002635
reads taken: 4006940

ro

reads taken: 4150747
reads taken: 4150279

w1

writes taken: 13655019
writes taken: 13639011

wo

writes taken: 1757065
writes taken: 1758623

----------------------------------------------
RWSEM_GENERIC_SPINLOCK y in rwsem-2.4.4-pre6 + your latest #try2 (fast path in C out of line)

rw

reads taken: 5872682
writes taken: 3032179
reads taken: 5892582
writes taken: 3042346

r1

reads taken: 13079190
reads taken: 13104405

r2

reads taken: 3907702
reads taken: 3906729

ro

reads taken: 3005924
reads taken: 3006690

w1

writes taken: 12581209
writes taken: 12570627

wo

writes taken: 1376782
writes taken: 1328468

----------------------------------------------
RWSEM_XCHGADD y in rwsem-2.4.4-pre6 + your latest #try2 (fast path in asm in line)

rw

reads taken: 5789650
writes taken: 2989604
reads taken: 5776594
writes taken: 2982812
r1

reads taken: 16935488
reads taken: 16930738

r2

reads taken: 5646446
reads taken: 5651600

ro

reads taken: 4952654
reads taken: 4956992

w1

writes taken: 15432874
writes taken: 15408684

wo

writes taken: 814131
writes taken: 815551

To make it more readable I plotted the numbers in a graph (attached).

So my new C based rw semaphores are faster than your C based semaphores in all tests and they're even faster than your x86 asm inlined semaphores when there's contention (however it's probably normal that with contention the asm semaphores are slower so I'm not sure I can make the asm inlined semaphore faster than yours). I will try to boost my new rwsem with asm in the fast path now (it won't be easy but possibly by only changing a few lines of the slow path inside an #ifdef CONFIG_...) to see where can I go. Once I will have an asm inlined fast path for >=486 integrated I will upload a patch but if you want a patch now with only the new generic C implementation to verify the above numbers let me know of course (ah and btw the machine is a 2-way PII 450mhz).

I think it's interesting also the comparison of my generic rwsem when inlined and not inlined (first four columns). BTW, I also tried to move my only lock in a separated cacheline (growing the size of the rwsem over 32bytes) and that hurted a lot.

Note also the your wo results with your asm version (the one in pre6 + your latest try#2) is scoring more than two times worse than my generic semaphores.

Andrea

btw, I noticed I answered your previous email but for my benchmarks I really used your latest #try2 posted today at 13 (not last night a 1am), just to avoid mistakes this is the the md5sum of the patch I applied on top of pre6:

	510c05d168c2b60e0d9c804381579b51  rwsem.diff

Andrea