generic rwsems

OK, this patch is against 2.6.21-rc6 + Mathieu's atomic_long patches.

Last time this came up I was asked to get some numbers, so here are some in the changelog, captured with a simple kernel module tester. I got motivated again because of the MySQL/glibc/mmap_sem issue.

This patch converts all architectures to a generic rwsem implementation, which will compile down to the same code for i386, or powerpc, for example, and will allow some (eg. x86-64) to move away from spinlock based rwsems.

Comments?
--

Move to an architecture independent rwsem implementation, using the better of the two rwsem implementations (ie. the one which doesn't take a spinlock to take an uncontested rwsem) as a basis. This gives us a single rwsem design instead of two.

Use high level atomic primitives for the implementation, rather than open coded assembly. This gives us a single implementation, rather than a handful.

Use atomic_long_t rather than atomic_t for the count, which solves the parallelism limitation for those architectures (actually found to be a problem with ia64, powerpc and x86-64 may not be far behind).

Remove one level of indirection (kernel/rwsem.c -> lib/rwsem.c), and give a bit of a cleanup (eg remove the fastcall junk) to make the code a bit easier to read.

Out-of-line the fastpaths, to bring rw-semaphores into line with mutexes and spinlocks WRT our icache vs function call policy.

Test system is a 16 core 8 socket Opteron. Numbers are the total number of lock/unlock pairs performed in a given time -- 10s for single-thread tests, 30s for others. 1r/0w means 1 read locker and 0 write locker threads, "generic" is patched kernel, and "irq" is plain kernel but with _irq* removed from rwsem spinlocks because otherwise all the multi-threaded tests start losing timer interrupts due to spinlock contention and measurements go silly.

Spinlock based rwsems are inferior to atomic based ones one most architectures that can do atomic ops without spinlocks:

- The atomic version is faster (on x86_64) by more than 2 times in single threaded performance.

	1r/0w		0r/1w

irq 115577784 131483401
generic 270112870 264038942

- The spinlock based rwsem can gather a lot of spinlock contention even when only rwsem readers are present (eg. threaded malloc/free workload after glibc gets converted to use MADV_DONTNEED). Throughput is improved by a factor of 4 with 16 cores.

	16r/0w		0r/16w

irq 52793019 7752277
generic 199174486 7750554

- At high concurrencies, with both readers and writers, the spinlock in the fastpath can get tangled up with the spinlock in the slow wakeup path. This is also a reason why atomic based rwsems will be better even for architectures that do atomics with hashed spinlocks.

At 16 readers and 1 writer, reader throughput goes up by an order of magnitude and writer throughput increases significantly. At 128 readers and 4 writers, throughput goes up by more than double for both readers and writers.

	      16r/1w		    128r/4w

irq 13084481/265663 5233988/256034
generic 104505771/349811 11963683/554682

 arch/alpha/Kconfig                |    7 
 arch/arm/Kconfig                  |    7 
 arch/arm26/Kconfig                |    7 
 arch/cris/Kconfig                 |    7 
 arch/frv/Kconfig                  |    7 
 arch/h8300/Kconfig                |    8 
 arch/i386/Kconfig.cpu             |   10 
 arch/ia64/Kconfig                 |    4 
 arch/m32r/Kconfig                 |    9 
 arch/m68k/Kconfig                 |    7 
 arch/m68knommu/Kconfig            |    8 
 arch/mips/Kconfig                 |   11 -
 arch/parisc/Kconfig               |    6 
 arch/powerpc/Kconfig              |    7 
 arch/ppc/Kconfig                  |    7 
 arch/s390/Kconfig                 |    7 
 arch/sh/Kconfig                   |    7 
 arch/sh64/Kconfig                 |    7 
 arch/sparc/Kconfig                |    7 
 arch/sparc/lib/rwsem.S            |  204 --------------------
 arch/sparc64/Kconfig              |    7 
 arch/sparc64/lib/rwsem.S          |  170 ----------------
 arch/um/Kconfig.x86_64            |    4 
 arch/v850/Kconfig                 |    6 
 arch/x86_64/Kconfig               |    7 
 arch/xtensa/Kconfig               |    4 
 include/asm-alpha/rwsem.h         |  259 -------------------------
 include/asm-i386/rwsem.h          |  258 -------------------------
 include/asm-ia64/rwsem.h          |  178 -----------------
 include/asm-powerpc/rwsem.h       |  152 --------------
 include/asm-s390/rwsem.h          |  387 --------------------------------------
 include/asm-sh/rwsem.h            |  184 ------------------
 include/asm-sparc64/rwsem-const.h |   12 -
 include/asm-sparc64/rwsem.h       |   84 --------
 include/asm-um/rwsem.h            |    6 
 include/asm-xtensa/rwsem.h        |  164 ----------------
 include/linux/rwsem-spinlock.h    |   78 -------
 include/linux/rwsem.h             |   62 +++++-
 kernel/rwsem.c                    |  320 ++++++++++++++++++++++++++++++-
 lib/Makefile                      |    2 
 lib/rwsem-spinlock.c              |  316 -------------------------------
 lib/rwsem.c                       |  257 -------------------------
 42 files changed, 364 insertions(+), 2897 deletions(-)

Index: linux-2.6/include/asm-powerpc/rwsem.h
===================================================================
@@ -1,152 +0,0 @@
-#ifndef _ASM_POWERPC_RWSEM_H
-#define _ASM_POWERPC_RWSEM_H
-
-#ifdef __KERNEL__
-
-/*
- * include/asm-powerpc/rwsem.h: R/W semaphores for PPC using the stuff
- * in lib/rwsem.c.  Adapted largely from include/asm-i386/rwsem.h
- * by Paul Mackerras <[email protected]>.
- */
-
-#include <linux/list.h>
-#include <linux/spinlock.h>
-#include <asm/atomic.h>
-#include <asm/system.h>
-
-/*
- * the semaphore definition
- */
-struct rw_semaphore {
-	/* XXX this should be able to be an atomic_t  -- paulus */
-	signed int		count;
-#define RWSEM_UNLOCKED_VALUE		0x00000000
-#define RWSEM_ACTIVE_BIAS		0x00000001
-#define RWSEM_ACTIVE_MASK		0x0000ffff
-#define RWSEM_WAITING_BIAS		(-0x00010000)
-#define RWSEM_ACTIVE_READ_BIAS		RWSEM_ACTIVE_BIAS
-#define RWSEM_ACTIVE_WRITE_BIAS		(RWSEM_WAITING_BIAS + RWSEM_ACTIVE_BIAS)
-	spinlock_t		wait_lock;
-	struct list_head	wait_list;
-};
-
-#define __RWSEM_INITIALIZER(name) \
-	{ RWSEM_UNLOCKED_VALUE, SPIN_LOCK_UNLOCKED, \
-	  LIST_HEAD_INIT((name).wait_list) }
-
-#define DECLARE_RWSEM(name)		\
-	struct rw_semaphore name = __RWSEM_INITIALIZER(name)
-
-extern struct rw_semaphore *rwsem_down_read_failed(struct rw_semaphore *sem);
-extern struct rw_semaphore *rwsem_down_write_failed(struct rw_semaphore *sem);
-extern struct rw_semaphore *rwsem_wake(struct rw_semaphore *sem);
-extern struct rw_semaphore *rwsem_downgrade_wake(struct rw_semaphore *sem);
-
-static inline void init_rwsem(struct rw_semaphore *sem)
-{
-	sem->count = RWSEM_UNLOCKED_VALUE;
-	spin_lock_init(&sem->wait_lock);
-	INIT_LIST_HEAD(&sem->wait_list);
-}
-
-/*
- * lock for reading
- */
-static inline void __down_read(struct rw_semaphore *sem)
-{
-	if (unlikely(atomic_inc_return((atomic_t *)(&sem->count)) <= 0))
-		rwsem_down_read_failed(sem);
-}
-
-static inline int __down_read_trylock(struct rw_semaphore *sem)
-{
-	int tmp;
-
-	while ((tmp = sem->count) >= 0) {
-		if (tmp == cmpxchg(&sem->count, tmp,
-				   tmp + RWSEM_ACTIVE_READ_BIAS)) {
-			return 1;
-		}
-	}
-	return 0;
-}
-
-/*
- * lock for writing
- */
-static inline void __down_write(struct rw_semaphore *sem)
-{
-	int tmp;
-
-	tmp = atomic_add_return(RWSEM_ACTIVE_WRITE_BIAS,
-				(atomic_t *)(&sem->count));
-	if (unlikely(tmp != RWSEM_ACTIVE_WRITE_BIAS))
-		rwsem_down_write_failed(sem);
-}
-
-static inline int __down_write_trylock(struct rw_semaphore *sem)
-{
-	int tmp;
-
-	tmp = cmpxchg(&sem->count, RWSEM_UNLOCKED_VALUE,
-		      RWSEM_ACTIVE_WRITE_BIAS);
-	return tmp == RWSEM_UNLOCKED_VALUE;
-}
-
-/*
- * unlock after reading
- */
-static inline void __up_read(struct rw_semaphore *sem)
-{
-	int tmp;
-
-	tmp = atomic_dec_return((atomic_t *)(&sem->count));
-	if (unlikely(tmp < -1 && (tmp & RWSEM_ACTIVE_MASK) == 0))
-		rwsem_wake(sem);
-}
-
-/*
- * unlock after writing
- */
-static inline void __up_write(struct rw_semaphore *sem)
-{
-	if (unlikely(atomic_sub_return(RWSEM_ACTIVE_WRITE_BIAS,
-			      (atomic_t *)(&sem->count)) < 0))
-		rwsem_wake(sem);
-}
-
-/*
- * implement atomic add functionality
- */
-static inline void rwsem_atomic_add(int delta, struct rw_semaphore *sem)
-{
-	atomic_add(delta, (atomic_t *)(&sem->count));
-}
-
-/*
- * downgrade write lock to read lock
- */
-static inline void __downgrade_write(struct rw_semaphore *sem)
-{
-	int tmp;
-
-	tmp = atomic_add_return(-RWSEM_WAITING_BIAS, (atomic_t *)(&sem->count));
-	if (tmp < 0)
-		rwsem_downgrade_wake(sem);
-}
-
-/*
- * implement exchange and add functionality
- */
-static inline int rwsem_atomic_update(int delta, struct rw_semaphore *sem)
-{
-	return atomic_add_return(delta, (atomic_t *)(&sem->count));
-}
-
-static inline int rwsem_is_locked(struct rw_semaphore *sem)
-{
-	return (sem->count != 0);
-}
-
-#endif	/* __KERNEL__ */
-#endif	/* _ASM_POWERPC_RWSEM_H */

Index: linux-2.6/include/asm-sparc64/rwsem-const.h
===================================================================
@@ -1,12 +0,0 @@
-/* rwsem-const.h: RW semaphore counter constants.  */
-#ifndef _SPARC64_RWSEM_CONST_H
-#define _SPARC64_RWSEM_CONST_H
-
-#define RWSEM_UNLOCKED_VALUE		0x00000000
-#define RWSEM_ACTIVE_BIAS		0x00000001
-#define RWSEM_ACTIVE_MASK		0x0000ffff
-#define RWSEM_WAITING_BIAS		0xffff0000
-#define RWSEM_ACTIVE_READ_BIAS		RWSEM_ACTIVE_BIAS
-#define RWSEM_ACTIVE_WRITE_BIAS		(RWSEM_WAITING_BIAS + RWSEM_ACTIVE_BIAS)
-
-#endif /* _SPARC64_RWSEM_CONST_H */

Index: linux-2.6/include/asm-um/rwsem.h
===================================================================
@@ -1,6 +0,0 @@
-#ifndef __UM_RWSEM_H__
-#define __UM_RWSEM_H__
-
-#include "asm/arch/rwsem.h"
-
-#endif

Index: linux-2.6/arch/alpha/Kconfig
===================================================================
@@ -18,13 +18,6 @@ config MMU
 	bool
 	default y
 
-config RWSEM_GENERIC_SPINLOCK
-	bool
-
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-	default y
-
 config ARCH_HAS_ILOG2_U32
 	bool
 	default n

Index: linux-2.6/arch/arm/Kconfig
===================================================================
@@ -79,13 +79,6 @@ config GENERIC_IRQ_PROBE
 	bool
 	default y
 
-config RWSEM_GENERIC_SPINLOCK
-	bool
-	default y
-
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-
 config ARCH_HAS_ILOG2_U32
 	bool
 	default n

Index: linux-2.6/arch/arm26/Kconfig
===================================================================
@@ -34,13 +34,6 @@ config FORCE_MAX_ZONEORDER
         int
         default 9
 
-config RWSEM_GENERIC_SPINLOCK
-	bool
-	default y
-
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-
 config ARCH_HAS_ILOG2_U32
 	bool
 	default n

Index: linux-2.6/arch/cris/Kconfig
===================================================================
@@ -13,13 +13,6 @@ config ZONE_DMA
 	bool
 	default y
 
-config RWSEM_GENERIC_SPINLOCK
-	bool
-	default y
-
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-
 config ARCH_HAS_ILOG2_U32
 	bool
 	default n

Index: linux-2.6/arch/frv/Kconfig
===================================================================
@@ -10,13 +10,6 @@ config ZONE_DMA
 	bool
 	default y
 
-config RWSEM_GENERIC_SPINLOCK
-	bool
-	default y
-
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-
 config GENERIC_FIND_NEXT_BIT
 	bool
 	default y

Index: linux-2.6/arch/h8300/Kconfig
===================================================================
@@ -25,14 +25,6 @@ config FPU
 	bool
 	default n
 
-config RWSEM_GENERIC_SPINLOCK
-	bool
-	default y
-
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-	default n
-
 config ARCH_HAS_ILOG2_U32
 	bool
 	default n

Index: linux-2.6/arch/ia64/Kconfig
===================================================================
@@ -37,10 +37,6 @@ config MMU
 config SWIOTLB
        bool
 
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-	default y
-
 config ARCH_HAS_ILOG2_U32
 	bool
 	default n

Index: linux-2.6/arch/m32r/Kconfig
===================================================================
@@ -212,15 +212,6 @@ config IRAM_SIZE
 # Define implied options from the CPU selection here
 #
 
-config RWSEM_GENERIC_SPINLOCK
-	bool
-	depends on M32R
-	default y
-
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-	default n
-
 config ARCH_HAS_ILOG2_U32
 	bool
 	default n

Index: linux-2.6/arch/m68k/Kconfig
===================================================================
@@ -10,13 +10,6 @@ config MMU
 	bool
 	default y
 
-config RWSEM_GENERIC_SPINLOCK
-	bool
-	default y
-
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-
 config ARCH_HAS_ILOG2_U32
 	bool
 	default n

Index: linux-2.6/arch/m68knommu/Kconfig
===================================================================
@@ -21,14 +21,6 @@ config ZONE_DMA
 	bool
 	default y
 
-config RWSEM_GENERIC_SPINLOCK
-	bool
-	default y
-
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-	default n
-
 config ARCH_HAS_ILOG2_U32
 	bool
 	default n

Index: linux-2.6/arch/mips/Kconfig
===================================================================
@@ -838,13 +838,6 @@ source "arch/mips/philips/pnx8550/common
 
 endmenu
 
-config RWSEM_GENERIC_SPINLOCK
-	bool
-	default y
-
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-
 config ARCH_HAS_ILOG2_U32
 	bool
 	default n

@@ -1970,10 +1963,6 @@ config SECCOMP
 
 endmenu
 
-config RWSEM_GENERIC_SPINLOCK
-	bool
-	default y
-
 config LOCKDEP_SUPPORT
 	bool
 	default y

Index: linux-2.6/arch/parisc/Kconfig
===================================================================
@@ -19,12 +19,6 @@ config MMU
 config STACK_GROWSUP
 	def_bool y
 
-config RWSEM_GENERIC_SPINLOCK
-	def_bool y
-
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-
 config ARCH_HAS_ILOG2_U32
 	bool
 	default n

Index: linux-2.6/arch/powerpc/Kconfig
===================================================================
@@ -34,13 +34,6 @@ config IRQ_PER_CPU
 	bool
 	default y
 
-config RWSEM_GENERIC_SPINLOCK
-	bool
-
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-	default y
-
 config ARCH_HAS_ILOG2_U32
 	bool
 	default y

Index: linux-2.6/arch/ppc/Kconfig
===================================================================
@@ -12,13 +12,6 @@ config GENERIC_HARDIRQS
 	bool
 	default y
 
-config RWSEM_GENERIC_SPINLOCK
-	bool
-
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-	default y
-
 config ARCH_HAS_ILOG2_U32
 	bool
 	default y

Index: linux-2.6/arch/s390/Kconfig
===================================================================
@@ -19,13 +19,6 @@ config STACKTRACE_SUPPORT
 	bool
 	default y
 
-config RWSEM_GENERIC_SPINLOCK
-	bool
-
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-	default y
-
 config ARCH_HAS_ILOG2_U32
 	bool
 	default n

Index: linux-2.6/arch/sh/Kconfig
===================================================================
@@ -15,13 +15,6 @@ config SUPERH
 	  gaming console.  The SuperH port has a home page at
 	  <http://www.linux-sh.org/>.
 
-config RWSEM_GENERIC_SPINLOCK
-	bool
-	default y
-
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-
 config GENERIC_FIND_NEXT_BIT
 	bool
 	default y

Index: linux-2.6/arch/sh64/Kconfig
===================================================================
@@ -17,10 +17,6 @@ config MMU
 	bool
 	default y
 
-config RWSEM_GENERIC_SPINLOCK
-	bool
-	default y
-
 config GENERIC_FIND_NEXT_BIT
 	bool
 	default y

@@ -33,9 +29,6 @@ config GENERIC_CALIBRATE_DELAY
 	bool
 	default y
 
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-
 config ARCH_HAS_ILOG2_U32
 	bool
 	default n

Index: linux-2.6/arch/sparc/Kconfig
===================================================================
@@ -147,13 +147,6 @@ config SUN_IO
 	bool
 	default y
 
-config RWSEM_GENERIC_SPINLOCK
-	bool
-	default y
-
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-
 config GENERIC_FIND_NEXT_BIT
 	bool
 	default y

Index: linux-2.6/arch/sparc64/Kconfig
===================================================================
@@ -167,13 +167,6 @@ config US2E_FREQ
 	  If in doubt, say N.
 
 # Global things across all Sun machines.
-config RWSEM_GENERIC_SPINLOCK
-	bool
-
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-	default y
-
 config GENERIC_FIND_NEXT_BIT
 	bool
 	default y

Index: linux-2.6/arch/v850/Kconfig
===================================================================
@@ -13,12 +13,6 @@ config MMU
 config ZONE_DMA
 	bool
 	default y
-config RWSEM_GENERIC_SPINLOCK
-	bool
-	default y
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-	default n
 config GENERIC_FIND_NEXT_BIT
 	bool
 	default y

Index: linux-2.6/arch/x86_64/Kconfig
===================================================================
@@ -62,13 +62,6 @@ config ISA
 config SBUS
[… more lines in the raw message]

Index: linux-2.6/arch/xtensa/Kconfig
===================================================================

Index: linux-2.6/arch/i386/Kconfig.cpu
===================================================================

Index: linux-2.6/arch/um/Kconfig.x86_64
===================================================================

Index: linux-2.6/lib/Makefile
===================================================================

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Part of the diff is not shown here. View the raw message.

Arpopos fastcalls, now that -mregparam=3 is the defaul on i386 and FASTCALL/fastcall is a noop everywhere else can we please get rid of this attribute entirely? If any other architecture provides a more optimal non-standard calling convention we can just use it by default in kernelspace as a few architectures already do.

I don't see why not. David objected me removing them I think because the rwsem code called some from asm (but of course that's removed too). However AFAIK, this situation should be using the asmlinkage attribute anyway.

fastcall in kernel is annoying... it seems to imply that we normally rather slow calls ;)

Oh, and it also converts powerpc and sparc64 to 64-bit counters, so they can handle more than 32K tasks waiting (which was apparently a real problem for SGI, and is probably a good thing).

But that reminds me:

It makes no difference. struct lockdep_map contains at least one pointer and so is going to be 8-byte aligned (assuming it's there at all). struct rw_semaphore contains at least one pointer/long, so it will be padded out to 8-byte size.

If you want to make a difference, you'd need to add __attribute__((packed)) but you would need to be very careful with that.

David

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

I hope people are not going to enabled lockdep on their production systems :)

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Fine for me from the x86-64 side. Some more validation with a test suite would be good though.

-Andi

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

David had a test suite somewhere, so I'll give that a run.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Which are better on UP kernels because spinlocks degrade to nothing, and then you're left with a single disable/enable interrupt pair per operation, and no requirement for atomic ops at all.

What you propose may wind up with several per op because if the CPU does not support atomic ops directly and cannot emulate them through other atomic ops, then these have to be emulated by:

	atomic_op() {
		spin_lock_irqsave
		do op
		spin_unlock_irqrestore
	}

That's not necessarily the case, as I said above.

Furthermore, the spinlock implementation struct is smaller on 64-bit machines, and is less prone to counter overrun on 32-bit machines.

That should depend on whether you optimise for space or for speed. Function calls are relatively heavyweight.

Please re-inline and fix Ingo's mess if you must clean up. Take the i386 version, for instance, I'd made it so that the compiler didn't know it was taking a function call when it went down the slow path, thus meaning the compiler didn't have to deal with that. Furthermore, it only interpolated two or three instructions into the calling code in the fastpath. It's a real shame that gcc inline asm doesn't allow you to use status flags as boolean returns, otherwise I could reduce that even further.

Note the "most" in your statement...

Think about it. This algorithm is only optimal where XADD is available. If you don't have XADD, but you do have LL/SC or CMPXCHG, you can do better.

If the only atomic op you have is XCHG, then this is a really poor choice; similarly if you are using a UP-compiled kernel.

David

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

David, you keep saying the same things and don't listen to me.

On UP, if an IRQ disable/enable pair operation is _faster_ than the atomic op, then the architecture can and should impelemnt atomic ops on UP by doing exactly that.

Yes, this is the case on our 2 premiere SMP powerhouse architectures, sparc32 and parsic.

The other way happens to be better for everyone else, which is why I think your suggestion to instead move everyone to the spinlock version was weird.

Finally: as I said, even for those 2 architectures, this may not be so bad because it is using a different spinlock for the fastpath as it is for the slowpath. So your uncontested, cache cold case will get a little slower, but the contested case could improve a lot (eg. I saw an order of magnitude improvement).

I think 64-bit machines will be happy to take the extra word it if they have double the single threaded performance, quadruple the parallel read performance, and 10 times the contested read performance.

32-bit machines might indeed overflow, but if it hasn't been a problem for i386 or (even 64-bit) powerpc yet, is it a real worry?

This is what spinlocks and mutexes do, and they're much more common than rwsems. I'm just trying to make it consistent, and you can muck around with it all you want after that. It is actually very easy to inline things now, unlike before my patch.

I cleaned it.

You keep saying this too, and I have thought about it but I couldn't think of a much better way. I'm not saying you're wrong, but why don't you just tell me what that better way is?

What is better? spinlocks? I think that considering only 2 dead archs really care at this stage, and I have good reason to believe that the contested case will be impreoved, then why don't you come up with some numbers to prove me wrong?

Then your UP-compiled kernel's atomic ops are suboptimal, not the rwsem implementation.

Anyway, thanks for taking the time again. If you would please address each of my points, then we might finally be able to stop having this discussion every 6 months ;)

Nick

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

sparc32 is ultra-legacy and I have a tremendous amount of work to do on SMP there. I don't feel that efficiency of locking primitives is a crucial issue for sparc32.

-- wli

No, you misunderstand me. My preferred solution is to leave it up to the arch and not to make it generic, though I'm not averse to providing some prepackaged solutions for an arch to pick from if it wants to.

Agreed. I can see why the spinlock implementation is bad on SMP. By all means change those cases, and reduce the spinlock implementation to an interrupt disablement only version that may only be used on UP only.

It has happened, I believe. People have tried having >32766 threads on a 32-bit box. Mad it may be, but...

My original stuff was very easy to inline until Ingo got hold of it.

Look at how the counter works in the spinlock case. With the addition of an extra flag in the counter to indicate there's stuff waiting on the queue, you can manipulate the counter if it appears safe to do so, otherwise you have to fall back to the slow path and take a spin lock.

Break the counter down like this:

	0x00000000	- not locked; queue empty
	0x40000000	- locked by writer; queue empty
	0xc0000000	- locket by writer; queue occupied
	0x0nnnnnnn	- n readers; queue empty
	0x8nnnnnnn	- n readers; queue occupied

Now here's a rough guide as to how the main operations would work:

(*) down_read of unlocked

	cmpxchg(0 -> 1) -> 0 [okay - you've got the lock]

(*) down_read of readlocked.

	cmpxchg(0 -> 1) -> n [failed to get the lock]
	do
	  n = cmpxchg(old_n -> old_n+1)
        until n == old_n

(*) down_read of writelocked or contented readlocked.

cmpxchg(0 -> 1) -> 0x80000000|n [lock contended] goto slowpath
spinlock
try to get lock again
if still contended
mark counter contended
add to queue
spinunlock
sleep
spinunlock

(*) down_write of unlocked

	cmpxchg(0 -> 0x40000000) -> 0 [okay - you've got the lock]

(*) down_write of locked, contended or otherwise

cmpxchg(0 -> 0x40000000) -> nz [failed]
goto slowpath
spinlock
try to get lock again
if still unavailable
mark counter contended
add to queue
spinunlock
sleep
else
spinunlock

(*) up_read

        x = cmpxchg(1 -> 0)
        if x == 0
	  done
        else
           do
	     x = cmpxchg(old_x -> old_x-1)
	   until x == old_x
           if old_x == 0x80000000
	     wake_up_writer

(*) up_write

        x = cmpxchg(0x80000000 -> 0)
        if x == 0
	  done
        else
	  wake_up_readers

You can actually do better with LL/SC here because for the initial attempt with CMPXCHG in each case you have to guess what the numbers will be. Furthermore, you might actually be able to do an "atomic increment or set contention flag" operation.

Note that the contention flag may only be set or cleared in the slow path whilst you are holding the spinlock.

Doing down_read and up_read with CMPXCHG is a pain. XADD or LL/SC would be better, and LOCK INC/ADD/DEC/SUB won't work. You can't use XADD in down_*() as you may not change the bottom part of the counter if you're going to end up queuing.

Actually, looking at it, it might be better to have the counter start off at 0x80000000 for "unlocked, no contention" and clear the no-contention flag when you queue something. That way you can check for the counter becoming 0 in the up_*() functions as a trigger to go and invoke the slowpath. Then you could use LOCK DEC/SUB on i386 rather than XADD as you only need to check the Z flag.

Note there is a slight window whereby a reader can jump a writer that's transiting between the fastpath part of down_write() and the slowpath part if there are outstanding readers on the rwsem but nothing yet queued.

OTOH, there's a similar window in the current XADD-based rwsems as the spinlock doesn't implement FIFO semantics, so the first to modify the count and fail to the slowpath may not be the first to get themselves on the queue.

That's usually a function of the CPU designer.

David

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Just doesn't seem to be much payoff. I know you didn't think there is anything wrong with 2 different impleemtnations and hundreds of lines of arch specific assembly, but there is really little gain. Sure you might be able to optimise a few cycles off the i386 asm, but damn I just blitzed that sort of improvement on x86-64... and I still doubt it will be very noticable because rwsems don't get called like spinlocks.

So you missed my point about this above. If your UP atomic ops are slower than interrupt disabling, then implement the damn things using interrupt disabling instead of whatever it is you are using that is slower! ;)

Anyway, I doubt all the 32-bit archs using atomics would convert to the slower spinlocks, so maybe this just has to be a known issue.

I agree that all the locking has turned pretty messy, but that isn't my fault.

[snip]

Ah, thanks. Yeah actually I remember you describing this at LCA, so I apologise for saying you didn't ;)

Really, that isn't going to do much for performance (nothing as dramatic as the x86-64 spinlock->atomic conversion). However it will reduce the lock size by 8 bytes on 64-bit and fix the overflow on 32-bit...

So why don't we implement this as the generic version? UP archs won't care because atomic_cmpxchg is generally just an interrupt disable, similarly for sparc and parisc. Most others except x86 do atomic_add_return with llsc or cas anyway, and even if the cmpxchg is a tiny bit slower for x86, at least it should be much faster than the spinlock version for x86-64, and will solve the overflow for i386.

What do you say?

I mean your atomic_xxx functions are suboptimal for that design of CPU.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

If space considerations are that important, we could then reserve one bit for the 'wait_lock spinlock'

0x20000000 : one cpu gained control of 'wait_list'

This would save 4 bytes on 32 bit platforms.

64 bit platforms could have a limit of 2^60 threads, instead of the way too small 2^28 one ;)

(we loose the debug version of spinlock of course)

Another possibility to save space would be to move wait_lock/wait_list outside of rw_semaphore, in a hashed global array. This would save 12/16 bytes per rw_semaphore (inode structs are probably the most demanding)

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

That makes life quite a bit more tricky, though it does have the advantage that it closes the reader-jumping-writer window I mentioned.

I suspect moving wait_list out would be a bad idea. The ordering of things in the list is very important. You need to perform several operations on the list, all of which would be potentially slower:

(1) glance at the first element of the list to see what sort of wake up to do

(2) iteration of the list when waking up multiple readers

(3) seeing if the list is empty (so you know that there's no more contention)

Moving the spinlock out, on the other hand, might be worth it to cut down on cacheline bouncing some more...

David

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>