optimised rw-semaphores for MIPS/MIPS64

Hello Ralf,

I've produced an inline-assembly optimised Read/Write Semaphore patch for MIPS against linux-2.4.7-pre6 (rwsem.diff). David Woodhouse has tested it.

I've also included a patch to the MIPS64 arch to supply that with optimised rwsems (rwsem64.diff), but that is untested.

Finally, I've included a patch to fix lib/rwsem.c (lib-rwsem.diff) if you want to try the patch on MIPS64 against anything earlier than 2.4.7-pre6.

David

diff -uNr -x CVS -x TAGS linux-2.4-mips/arch/mips/config.in linux-mips-rwsem/arch/mips/config.in
@@ -68,8 +68,8 @@
    fi
 bool 'Support for Alchemy Semi PB1000 board' CONFIG_MIPS_PB1000
 
-define_bool CONFIG_RWSEM_GENERIC_SPINLOCK y
-define_bool CONFIG_RWSEM_XCHGADD_ALGORITHM n
+define_bool CONFIG_RWSEM_GENERIC_SPINLOCK n
+define_bool CONFIG_RWSEM_XCHGADD_ALGORITHM y
 
 #
 # Select some configuration options automatically for certain systems.

diff -uNr -x CVS -x TAGS linux-2.4-mips/arch/mips64/config.in linux-mips-rwsem/arch/mips64/config.in
@@ -27,8 +27,8 @@
 fi
 endmenu
 
-define_bool CONFIG_RWSEM_GENERIC_SPINLOCK y
-define_bool CONFIG_RWSEM_XCHGADD_ALGORITHM n
+define_bool CONFIG_RWSEM_GENERIC_SPINLOCK n
+define_bool CONFIG_RWSEM_XCHGADD_ALGORITHM y
 
 #
 # Select some configuration options automatically based on user selections

diff -uNr -x CVS -x TAGS linux-2.4-mips/lib/rwsem.c linux-mips-rwsem/lib/rwsem.c
@@ -112,7 +112,7 @@
  */
 static inline struct rw_semaphore *rwsem_down_failed_common(struct rw_semaphore *sem,
 								 struct rwsem_waiter *waiter,
-								 __s32 adjustment)
+								 signed long adjustment)
 {
 	struct task_struct *tsk = current;
 	signed long count;

You'll also need the asm-mips*/compiler.h patch.

David

diff -uNr -x CVS -x TAGS linux-2.4-mips/include/asm-mips/compiler.h linux-mips-rwsem/include/asm-mips/compiler.h
@@ -0,0 +1,13 @@
+#ifndef __ASM_COMPILER_H
+#define __ASM_COMPILER_H
+
+/* Somewhere in the middle of the GCC 2.96 development cycle, we implemented
+   a mechanism by which the user can annotate likely branch directions and
+   expect the blocks to be reordered appropriately.  Define __builtin_expect
+   to nothing for earlier compilers.  */
+
+#if __GNUC__ == 2 && __GNUC_MINOR__ < 96
+#define __builtin_expect(x, expected_value) (x)
+#endif
+
+#endif /* __ASM_COMPILER_H */

diff -uNr -x CVS -x TAGS linux-2.4-mips/include/asm-mips64/compiler.h linux-mips-rwsem/include/asm-mips64/compiler.h
@@ -0,0 +1,13 @@
+#ifndef __ASM_COMPILER_H
+#define __ASM_COMPILER_H
+
+/* Somewhere in the middle of the GCC 2.96 development cycle, we implemented
+   a mechanism by which the user can annotate likely branch directions and
+   expect the blocks to be reordered appropriately.  Define __builtin_expect
+   to nothing for earlier compilers.  */
+
+#if __GNUC__ == 2 && __GNUC_MINOR__ < 96
+#define __builtin_expect(x, expected_value) (x)
+#endif
+
+#endif /* __ASM_COMPILER_H */

I don't understand why you keep writing code on top of your mathematically slower rwsem framework.

the C version is much much slower, measured several times.

The asm version has a inferior slow path design that force you having to do slower and quite tricky stuff in the up_write fast path. This is your up_write fast path:

		"  movl      %2,%%edx\n\t"
LOCK_PREFIX	"  xaddl     %%edx,(%%eax)\n\t" /* tries to transition 0xffff0001 -> 0x00000000 */
		"  jnz       2f\n\t" /* jump if the lock is being waited upon */

Plus you also clobber %dx in the up_write fast path which I don't need to.

This is my up_write fast path:

	__asm__ __volatile__(LOCK "subl %2, %0\n\t"
			     "js 2f\n"

Also the design of my xadd slow path looks more readable to me but ok, I'm biased about that, let's only care about the number of cycles you have to spend on the fast paths as measure of the goodness of the algorithm.

I'd suggest arch maintainers to port their rwsem asm optimized fast paths on top of this patch and to submit me patches:

	ftp://ftp.us.kernel.org/pub/linux/kernel/people/andrea/kernels/v2.4/2.4.7pre5aa1/00_rwsem-14

I also recommend Linus to include the above patch into mainline (it will reject on the alpha since in pre6 there is the asm optimized version on top of the slower framework, you can simply temporary disable the asm optimized version in alpha/config.in and it will compile just fine).

I have an old one from Ivan for alpha which I can just integrate after auditing and comparison with the one in pre6, the port of the others should be fairly easy too.

If arch maintainers will do it and it will be included in mainline this would save me some work and would make the kernel faster. If it won't be included again for whatever reason (I got no reply last times) I will just spend a day on it and I'll port all ports on top of the new code myself and I'll maintain the faster rwsem in my tree for all archs in the kernel (possibly with the exception of the ones that are not converted to the xchgadd asm version yet) as I did so far for x86.

Andrea