Skip to contentSkip to conversation

rwsem: generic rwsem

RFC PATCH In review Nick Piggin 2 participants 8 messages Dec 4, 2006 – Dec 11, 2006

Subsystems (14)
lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 rwsem: generic rwsem

(resending with correct ML addresses, sorry)

Hi,

This patch needs review and testing from the architecture guys, but I would like to consider it because of the obvious maintenance benefits.

I know people will want to scream because it costs 3 more cycles on some obscure architecture, but please try to stay in perspective. If it is a real problem, we could look at extending the asm/mutex.h locking helpers to make them usable for rwsem as well. It isn't a big deal.

Anyway, I hope this patch is a good starting point. Comments?

Thanks,
Nick

--
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.

 include/asm-alpha/rwsem.h         |  259 -------------------------
 include/asm-i386/rwsem.h          |  296 -----------------------------
 include/asm-ia64/rwsem.h          |  178 -----------------
 include/asm-powerpc/rwsem.h       |  152 --------------
 include/asm-s390/rwsem.h          |  387 -------------------------------------- include/asm-sh/rwsem.h            |  159 ---------------
 include/asm-sparc64/rwsem-const.h |   12 -
 include/asm-sparc64/rwsem.h       |   66 ------
 include/asm-um/rwsem.h            |    6
 include/asm-xtensa/rwsem.h        |  164 ----------------
 lib/rwsem-spinlock.c              |  316 -------------------------------
 lib/rwsem.c                       |  257 -------------------------
 linux-2.6/arch/alpha/Kconfig      |    7
 linux-2.6/arch/arm/Kconfig        |    7
 linux-2.6/arch/arm26/Kconfig      |    7
 linux-2.6/arch/cris/Kconfig       |    7
 linux-2.6/arch/frv/Kconfig        |    7
 linux-2.6/arch/h8300/Kconfig      |    8
 linux-2.6/arch/i386/Kconfig.cpu   |   10
 linux-2.6/arch/ia64/Kconfig       |    4
 linux-2.6/arch/m32r/Kconfig       |    9
 linux-2.6/arch/m68k/Kconfig       |    7
 linux-2.6/arch/m68knommu/Kconfig  |    8
 linux-2.6/arch/mips/Kconfig       |   11 -
 linux-2.6/arch/parisc/Kconfig     |    6
 linux-2.6/arch/powerpc/Kconfig    |    7
 linux-2.6/arch/ppc/Kconfig        |    7
 linux-2.6/arch/s390/Kconfig       |    7
 linux-2.6/arch/sh/Kconfig         |    7
 linux-2.6/arch/sh64/Kconfig       |    7
 linux-2.6/arch/sparc/Kconfig      |    7
 linux-2.6/arch/sparc64/Kconfig    |    7
 linux-2.6/arch/um/Kconfig.x86_64  |    4
 linux-2.6/arch/v850/Kconfig       |    6
 linux-2.6/arch/x86_64/Kconfig     |    7
 linux-2.6/arch/xtensa/Kconfig     |    4
 linux-2.6/include/linux/rwsem.h   |   76 ++++++-
 linux-2.6/kernel/rwsem.c          |  292 +++++++++++++++++++++++++++-
 linux-2.6/lib/Makefile            |    2
 39 files changed, 351 insertions(+), 2439 deletions(-)
include/asm-powerpc/rwsem.h deleted +0 -152
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 */
include/linux/rwsem.h +51 -6

74 lines not on this page · raw message

lib/rwsem-spinlock.c deleted +0 -316

316 lines not on this page · raw message

include/asm-alpha/rwsem.h deleted +0 -259

259 lines not on this page · raw message

include/asm-i386/rwsem.h deleted +0 -258

258 lines not on this page · raw message

include/asm-ia64/rwsem.h deleted +0 -178

178 lines not on this page · raw message

include/asm-s390/rwsem.h deleted +0 -387

387 lines not on this page · raw message

include/asm-sh/rwsem.h deleted +0 -159

159 lines not on this page · raw message

include/asm-sparc64/rwsem-const.h deleted +0 -12
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 */
include/asm-sparc64/rwsem.h deleted +0 -66

66 lines not on this page · raw message

include/asm-um/rwsem.h deleted +0 -6
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
include/asm-xtensa/rwsem.h deleted +0 -164

164 lines not on this page · raw message

kernel/rwsem.c +307 -12

379 lines not on this page · raw message

lib/rwsem.c deleted +0 -257

257 lines not on this page · raw message

arch/alpha/Kconfig +0 -7
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 GENERIC_FIND_NEXT_BIT
 	bool
 	default y
arch/arm/Kconfig +0 -7
Index: linux-2.6/arch/arm/Kconfig
===================================================================
@@ -67,13 +67,6 @@ config GENERIC_IRQ_PROBE
 	bool
 	default y
 
-config RWSEM_GENERIC_SPINLOCK
-	bool
-	default y
-
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-
 config GENERIC_HWEIGHT
 	bool
 	default y
arch/arm26/Kconfig +0 -7
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 GENERIC_HWEIGHT
 	bool
 	default y
arch/cris/Kconfig +0 -7
Index: linux-2.6/arch/cris/Kconfig
===================================================================
@@ -9,13 +9,6 @@ config MMU
 	bool
 	default y
 
-config RWSEM_GENERIC_SPINLOCK
-	bool
-	default y
-
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-
 config GENERIC_FIND_NEXT_BIT
 	bool
 	default y
arch/frv/Kconfig +0 -7
Index: linux-2.6/arch/frv/Kconfig
===================================================================
@@ -6,13 +6,6 @@ config FRV
 	bool
 	default y
 
-config RWSEM_GENERIC_SPINLOCK
-	bool
-	default y
-
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-
 config GENERIC_FIND_NEXT_BIT
 	bool
 	default y
arch/h8300/Kconfig +0 -8
Index: linux-2.6/arch/h8300/Kconfig
===================================================================
@@ -21,14 +21,6 @@ config FPU
 	bool
 	default n
 
-config RWSEM_GENERIC_SPINLOCK
-	bool
-	default y
-
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-	default n
-
 config GENERIC_FIND_NEXT_BIT
 	bool
 	default y
arch/ia64/Kconfig +0 -4
Index: linux-2.6/arch/ia64/Kconfig
===================================================================
@@ -30,10 +30,6 @@ config SWIOTLB
        bool
        default y
 
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-	default y
-
 config GENERIC_FIND_NEXT_BIT
 	bool
 	default y
arch/m32r/Kconfig +0 -9
Index: linux-2.6/arch/m32r/Kconfig
===================================================================
@@ -205,15 +205,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 GENERIC_FIND_NEXT_BIT
 	bool
 	default y
arch/m68k/Kconfig +0 -7
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 GENERIC_HWEIGHT
 	bool
 	default y
arch/m68knommu/Kconfig +0 -8
Index: linux-2.6/arch/m68knommu/Kconfig
===================================================================
@@ -17,14 +17,6 @@ config FPU
 	bool
 	default n
 
-config RWSEM_GENERIC_SPINLOCK
-	bool
-	default y
-
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-	default n
-
 config GENERIC_FIND_NEXT_BIT
 	bool
 	default y
arch/mips/Kconfig +0 -11
Index: linux-2.6/arch/mips/Kconfig
===================================================================
@@ -782,13 +782,6 @@ source "arch/mips/cobalt/Kconfig"
 
 endmenu
 
-config RWSEM_GENERIC_SPINLOCK
-	bool
-	default y
-
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-
 config GENERIC_FIND_NEXT_BIT
 	bool
 	default y
@@ -1786,10 +1779,6 @@ config MIPS_INSANE_LARGE
 
 endmenu
 
-config RWSEM_GENERIC_SPINLOCK
-	bool
-	default y
-
 config LOCKDEP_SUPPORT
 	bool
 	default y
arch/parisc/Kconfig +0 -6
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 GENERIC_FIND_NEXT_BIT
 	bool
 	default y
arch/powerpc/Kconfig +0 -7
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 GENERIC_HWEIGHT
 	bool
 	default y
arch/ppc/Kconfig +0 -7
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 GENERIC_HWEIGHT
 	bool
 	default y
arch/s390/Kconfig +0 -7
Index: linux-2.6/arch/s390/Kconfig
===================================================================
@@ -15,13 +15,6 @@ config STACKTRACE_SUPPORT
 	bool
 	default y
 
-config RWSEM_GENERIC_SPINLOCK
-	bool
-
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-	default y
-
 config GENERIC_HWEIGHT
 	bool
 	default y
arch/sh/Kconfig +0 -7
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
arch/sh64/Kconfig +0 -7
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 GENERIC_ISA_DMA
 	bool
 
arch/sparc/Kconfig +0 -7
Index: linux-2.6/arch/sparc/Kconfig
===================================================================
@@ -143,13 +143,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
arch/sparc64/Kconfig +0 -7
Index: linux-2.6/arch/sparc64/Kconfig
===================================================================
@@ -163,13 +163,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
arch/v850/Kconfig +0 -6
Index: linux-2.6/arch/v850/Kconfig
===================================================================
@@ -10,12 +10,6 @@ mainmenu "uClinux/v850 (w/o MMU) Kernel 
 config MMU
        	bool
 	default n
-config RWSEM_GENERIC_SPINLOCK
-	bool
-	default y
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-	default n
 config GENERIC_FIND_NEXT_BIT
 	bool
 	default y
arch/x86_64/Kconfig +0 -7
Index: linux-2.6/arch/x86_64/Kconfig
===================================================================
@@ -50,13 +50,6 @@ config ISA
 config SBUS
 	bool
 
-config RWSEM_GENERIC_SPINLOCK
-	bool
-	default y
-
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-
 config GENERIC_HWEIGHT
 	bool
 	default y
arch/xtensa/Kconfig +0 -4
Index: linux-2.6/arch/xtensa/Kconfig
===================================================================
@@ -18,10 +18,6 @@ config XTENSA
 	  with reasonable minimum requirements.  The Xtensa Linux project has
 	  a home page at <http://xtensa.sourceforge.net/>.
 
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-	default y
-
 config GENERIC_FIND_NEXT_BIT
 	bool
 	default y
arch/i386/Kconfig.cpu +0 -10
Index: linux-2.6/arch/i386/Kconfig.cpu
===================================================================
@@ -231,16 +231,6 @@ config X86_L1_CACHE_SHIFT
 	default "5" if MWINCHIP3D || MWINCHIP2 || MWINCHIPC6 || MCRUSOE || MEFFICEON || MCYRIXIII || MK6 || MPENTIUMIII || MPENTIUMII || M686 || M586MMX || M586TSC || M586 || MVIAC3_2 || MGEODE_LX
 	default "6" if MK7 || MK8 || MPENTIUMM
 
-config RWSEM_GENERIC_SPINLOCK
-	bool
-	depends on M386
-	default y
-
-config RWSEM_XCHGADD_ALGORITHM
-	bool
-	depends on !M386
-	default y
-
 config GENERIC_CALIBRATE_DELAY
 	bool
 	default y
arch/um/Kconfig.x86_64 +0 -4
Index: linux-2.6/arch/um/Kconfig.x86_64
===================================================================
@@ -7,10 +7,6 @@ config 64BIT
 	default y
 
 #XXX: this is so in the underlying arch, but it's wrong!!!
-config RWSEM_GENERIC_SPINLOCK
-	bool
-	default y
-
 config SEMAPHORE_SLEEPERS
 	bool
 	default y
lib/Makefile +0 -2
Index: linux-2.6/lib/Makefile
===================================================================
@@ -21,8 +21,6 @@ endif
 
 obj-$(CONFIG_DEBUG_LOCKING_API_SELFTESTS) += locking-selftest.o
 obj-$(CONFIG_DEBUG_SPINLOCK) += spinlock_debug.o
-lib-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o
-lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o
 lib-$(CONFIG_SEMAPHORE_SLEEPERS) += semaphore-sleepers.o
 lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += find_next_bit.o
 lib-$(CONFIG_GENERIC_HWEIGHT) += hweight.o
include/linux/rwsem-spinlock.h deleted +0 -77

1 line not on this page · raw message

arch/sparc/lib/rwsem.S deleted +0 -204

204 lines not on this page · raw message

arch/sparc64/lib/rwsem.S deleted +0 -170

170 lines not on this page · raw message

The rest of this diff is not shown. View the raw message.

----- End forwarded message -----

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

#1 lore raw
Quoted 6 lines · Nick Piggin

(resending with correct ML addresses, sorry)

Hi,

This patch needs review and testing from the architecture guys, but I would like to consider it because of the obvious maintenance benefits.

Hah, very important detail: patch is on top of Mathieu Desnoyers' recent "[PATCH 1/2] atomic.h atomic64_t standardization", which gives us atomic_long_cmpxchg on all architectures.

Nick

#2 lore raw
In reply to Nick Piggin
Quoted 4 lines · Nick Piggin

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.

Sigh.

NAK again!

You are taking the wrong approach. If you must collapse the multiple optimised implementations, then you must choose the spinlock approach. cmpxchg() may have be implemented by spinlock on some archs, and so your approach is really not optimal in such cases. Not all archs have cmpxchg or any way of doing an equivalent. Please don't hold FRV up as an example, because as I've mentioned before, it does not have an SMP-safe implementation of cmpxchg for multiple CPUs. FRV only has XCHG that you can really rely on.

I have another CPU (MN10300/AM33) that we're working on too, and that only has BSET/BCLR - single bit XCHG basically. That can't even do the UP emulation the FRV does.

And if you've got LL/SC equivalents (alpha, mips, powerpc, arm6) then CMPXCHG is also suboptimal.

If you've got XADD, then CMPXCHG is also suboptimal. CMPXCHG may have to spin.

Yes, you say "I know people will want to scream because it costs 3 more cycles on some obscure architecture", but that includes some i386 arch CPUs. OTOH, XADD isn't much cheaper there. On some i386 CPUs, the spinlock algorithm may be the best.

Quoted 2 lines

If it is a real problem, we could look at extending the asm/mutex.h locking helpers to make them usable for rwsem as well.

The asm-mutex stuff is not that nice either.

Quoted 2 lines

This patch needs review and testing from the architecture guys, but I would like to consider it because of the obvious maintenance benefits.

Which are? As far as I know there haven't needed to be any fixes in the rwsem stuff for some time.

So, what problems are you actually trying to fix?

Quoted 3 lines

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

But not all CPUs can be optimised the same way, even within the same arch...

Quoted 3 lines

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).

Then use the spinlock version generically. You have to take the spinlock in the slowpath anyway. This then gives you a maximum number of readers of of 2^30-1. By trading another bit, you can remove the requirement to also contemplate the emptiness of the list of waiters.

Quoted 3 lines

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.

Actually, the code isn't anywhere near as difficult to read as the mutex code or the spinlock code. The fastcall "junk" is quite important wrt the i386 code and permitted a small speedup (though if we compile with regparms=3 nowadays, then the advantage is actually bypassed).

Quoted 1 line

Out-of-line the fastpaths,

Why? I think the fastpaths should be inlined if lockdep is disabled, but Ingo broke that.

Quoted 2 lines

to bring rw-semaphores into line with mutexes and spinlocks WRT our icache vs function call policy.

Which is what? And why do you assume mutexes and spinlocks are the correct way to do things? They may result in slightly smaller code, but they end up with slower code.

David

#3 lore raw
Quoted 7 lines · David Howells
Quoted 4 lines · Nick Piggin

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.

Quoted 6 lines

Sigh.

NAK again!

You are taking the wrong approach. If you must collapse the multiple optimised implementations, then you must choose the spinlock approach. cmpxchg() may

No I don't. Either approach works, and one is better than the current two approaches. This doesn't have to be the final word on rwsem implementation.

Quoted 2 lines

have be implemented by spinlock on some archs, and so your approach is really not optimal in such cases. Not all archs have cmpxchg or any way of doing an

We do lots of things that aren't optimal for everyone. If it hurts, we can special case it. This really doesn't, considering the rarity of rwsems.

Quoted 3 lines

equivalent. Please don't hold FRV up as an example, because as I've mentioned before, it does not have an SMP-safe implementation of cmpxchg for multiple CPUs. FRV only has XCHG that you can really rely on.

FRV doesn't have an SMP port, and I frankly can't read the future and know that you plan to do an SMP port in a year's time and what the code looks like.

I honestly couldn't see why you went on this tangent last time and I can't see your point now. If FRV only has an SMP safe xchg, then it will need to implement SMP atomics with spinlocks anyway, to get things like add_return.

Quoted 3 lines

I have another CPU (MN10300/AM33) that we're working on too, and that only has BSET/BCLR - single bit XCHG basically. That can't even do the UP emulation the FRV does.

And this is relevant how? Why do you imagine that atomic_cmpxchg is so much harder than atomic_add_unless, atomic_add_return (or even atomic_add) on an architecture like this?

Quoted 9 lines

And if you've got LL/SC equivalents (alpha, mips, powerpc, arm6) then CMPXCHG is also suboptimal.

If you've got XADD, then CMPXCHG is also suboptimal. CMPXCHG may have to spin.

Yes, you say "I know people will want to scream because it costs 3 more cycles on some obscure architecture", but that includes some i386 arch CPUs. OTOH, XADD isn't much cheaper there. On some i386 CPUs, the spinlock algorithm may be the best.

Nor did I understand this objection last time. You must have just read the description, rather than the code. I *do* use xadd on x86 for down read (ie. atomic_add_return). And the place where I use cmpxchg *already* uses cmpxchg on i386. Ditto for alpha and powerpc (which are the ones implementing their own rwsem.h of your above list).

Actually all these architectures will generate basically identical code (ignoring ool vs inline). So will all the UP architectures that supress interrupts for atomic ops.

Quoted 4 lines
Quoted 2 lines

If it is a real problem, we could look at extending the asm/mutex.h locking helpers to make them usable for rwsem as well.

The asm-mutex stuff is not that nice either.

Which is why I'd prefer not to use it. The current rwsem stuff is much worse though, which is why I'd consider it.

Quoted 7 lines
Quoted 2 lines

This patch needs review and testing from the architecture guys, but I would like to consider it because of the obvious maintenance benefits.

Which are? As far as I know there haven't needed to be any fixes in the rwsem stuff for some time.

So, what problems are you actually trying to fix?

2 designs, 8 or so implementations (some subtly different) implemented in arch specific asm. That's the main problem, not actual code bugs.

Quoted 5 lines
Quoted 3 lines

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

But not all CPUs can be optimised the same way, even within the same arch...

And the day someone shows that it makes the slightest difference, we could do something specific for a given CPU of a given arch. As I said, this isn't the last change we make to rwsems.

Quoted 8 lines
Quoted 3 lines

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).

Then use the spinlock version generically. You have to take the spinlock in the slowpath anyway. This then gives you a maximum number of readers of of 2^30-1. By trading another bit, you can remove the requirement to also contemplate the emptiness of the list of waiters.

I moved to the implementation on the most widely used and tested arch, as well as the ones which have the most parallelism and weakly ordered memory (i386, powerpc, ia64). I figure this is likely to be adequately scalable and have less chance of being buggy.

Quoted 8 lines
Quoted 3 lines

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.

Actually, the code isn't anywhere near as difficult to read as the mutex code or the spinlock code. The fastcall "junk" is quite important wrt the i386 code and permitted a small speedup (though if we compile with regparms=3 nowadays, then the advantage is actually bypassed).

No objections, then?

Quoted 4 lines
Quoted 1 line

Out-of-line the fastpaths,

Why? I think the fastpaths should be inlined if lockdep is disabled, but Ingo broke that.

I'm fairly sure that Ingo did not "break" anything. The decision was made to out of line these things. Please do take it up in another thread if you like. I will be happy to inline things if you get agreement.

Quoted 6 lines
Quoted 2 lines

to bring rw-semaphores into line with mutexes and spinlocks WRT our icache vs function call policy.

Which is what? And why do you assume mutexes and spinlocks are the correct way to do things? They may result in slightly smaller code, but they end up with slower code.

Of course the code is slower when it is in L0 icache. I'm sure you know that smaller code is the whole point...

Thanks,
Nick

#4 lore raw
Quoted 1 line · Nick Piggin

Either approach works, and one is better than the current two approaches.

From one point of view that's true. But from other points of view, it isn't.

Quoted 5 lines
Quoted 3 lines

have be implemented by spinlock on some archs, and so your approach is really not optimal in such cases. Not all archs have cmpxchg or any way of doing an

We do lots of things that aren't optimal for everyone.

In this case it can be particularly suboptimal. The approach you've chosen to generalise on is specifically for XADD-based rwsems. XADD is only available on i386, x86_64 and ia64 (FETCHADD), and of those only i386 and ia64 actually use the XADD-optimised rwsems. Andi wants x86_64 to use the spinlock version.

Everywhere else, XADD is emulated.

If you have to emulate XADD by using CMPXCHG or LL/SC equivalents, then there're actually better ways of doing things than either of these approaches that the kernel currently has. I just need to find the time to explore them.

Look at how the counter works in the XADD-based version. That's the way it is *because* I'm using XADD. That's quite limiting.

Quoted 2 lines

If it hurts, we can special case it. This really doesn't, considering the rarity of rwsems.

If you're willing to special case it, then what's the point in generalising?

And in case you're wondering, FS-Cache uses a _lot_ of rwsem operations, so I do have an interest in making it quick, and that includes undoing what Ingo did when it's not necessary.

Quoted 4 lines

I honestly couldn't see why you went on this tangent last time and I can't see your point now. If FRV only has an SMP safe xchg, then it will need to implement SMP atomics with spinlocks anyway, to get things like add_return.

That's _exactly_ my point.

Think! If you _require_ the use of atomic ops in implementing rwsems, then you introduce _extra_, _general_ spinlocks into the XADD-based algorithm everywhere you call an atomic_xxx() op that has a side effect.

And if you're going to have to be getting general spinlocks then the XADD-based rwsem really is worse by quite a bit than the current spinlock-based rwsem as the latter _doesn't_ need general spinlocks as it doesn't use atomic ops.

Quoted 3 lines

And this is relevant how? Why do you imagine that atomic_cmpxchg is so much harder than atomic_add_unless, atomic_add_return (or even atomic_add) on an architecture like this?

It isn't, but atomic_xxx() will _have_ to be implemented with spinlocks.

My point here was that last time I believe you said that FRV managed to implement atomic ops without spinlocks, and so the case wasn't worth considering. My points are that (a) FRV would have to to do SMP, and (b) we have another arch lurking in the wings that does have to use spinlocks because I can't do the clever tricks there that I can on FRV.

Quoted 3 lines

Nor did I understand this objection last time. You must have just read the description, rather than the code. I *do* use xadd on x86 for down read (ie. atomic_add_return)

I missed the atomic_add_return(), so I'll forgive you that bit.

Quoted 7 lines

And the place where I use cmpxchg *already* uses cmpxchg on i386. Ditto for alpha and powerpc (which are the ones implementing their own rwsem.h of your above list).

Actually all these architectures will generate basically identical code (ignoring ool vs inline). So will all the UP architectures that supress interrupts for atomic ops.

Alpha and powerpc emulate XADD, so see above.

Quoted 2 lines

Which is why I'd prefer not to use it. The current rwsem stuff is much worse though, which is why I'd consider it.

No, it isn't. It's much more straightforward; or at least it was until Ingo decided to rearrange things.

Quoted 4 lines
Quoted 1 line

So, what problems are you actually trying to fix?

2 designs, 8 or so implementations (some subtly different) implemented in arch specific asm.

Yes, and?

Quoted 1 line

That's the main problem, not actual code bugs.

That's not actually a problem. It's done that way specifically so that the arches _can_ override it if they have a more optimal way to implement things.

That's the whol point of having separate arch code.

Don't generalise just for the sake of generalising things.

Quoted 5 lines
Quoted 1 line

But not all CPUs can be optimised the same way, even within the same arch...

And the day someone shows that it makes the slightest difference, we could do something specific for a given CPU of a given arch. As I said, this isn't the last change we make to rwsems.

You still haven't given a good reason for making your change.

Rwsems can be overridden now for different CPUs if you wish.

Quoted 9 lines
Quoted 4 lines

Then use the spinlock version generically. You have to take the spinlock in the slowpath anyway. This then gives you a maximum number of readers of of 2^30-1. By trading another bit, you can remove the requirement to also contemplate the emptiness of the list of waiters.

I moved to the implementation on the most widely used and tested arch, as well as the ones which have the most parallelism and weakly ordered memory (i386, powerpc, ia64). I figure this is likely to be adequately scalable and have less chance of being buggy.

The spinlock-based approach is easier to verify and has been tested on more archs than the other. I don't think either of them is more buggy than the other. The spinlock-based rwsems are also used on i386 under some circumstances.

Quoted 10 lines
Quoted 8 lines
Quoted 3 lines

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.

Actually, the code isn't anywhere near as difficult to read as the mutex code or the spinlock code. The fastcall "junk" is quite important wrt the i386 code and permitted a small speedup (though if we compile with regparms=3 nowadays, then the advantage is actually bypassed).

No objections, then?

WRONG!

Remove the fastcall and the i386 rwsems will cease to function if CONFIG_REGPARM=n.

Quoted 4 lines
Quoted 2 lines

Why? I think the fastpaths should be inlined if lockdep is disabled, but Ingo broke that.

I'm fairly sure that Ingo did not "break" anything.

Okay, "broke" is a bit strong. It still works, but it injects an unnecessary extra function call for each operation done if lockdep is disabled.

Quoted 2 lines

Of course the code is slower when it is in L0 icache. I'm sure you know that smaller code is the whole point...

Not necessarily. Faster code may also be the whole point; it depends on what you want. Enforcing a function call has various effects on what the compiler does at the point of consideration. By tailoring the i386 machine code, I was able to avoid forcing the compiler to realise it was making a function call at all, and only that it had to have the address of the semaphore in EAX when doing an rwsem op. This meant that down_read() was _very_ efficient. It only had two instructions interpolated into the main run of code, and normally the conditional jump would not be taken.

However, someone's changed that also, so it may well not be worth doing the XADD-based rwsems in i386 any more, and that arch should probably revert to the spinlock-based rwsems now.

I don't remember seeing anyone benchmarking the change made, but since it has to do with DWARF unwinding, it's probably necessary.

David

#5 lore raw
Quoted 17 lines · David Howells
Quoted 9 lines · Nick Piggin

Either approach works, and one is better than the current two approaches.

From one point of view that's true. But from other points of view, it isn't.

Quoted 3 lines

have be implemented by spinlock on some archs, and so your approach is really not optimal in such cases. Not all archs have cmpxchg or any way of doing an

We do lots of things that aren't optimal for everyone.

In this case it can be particularly suboptimal. The approach you've chosen to generalise on is specifically for XADD-based rwsems. XADD is only available on i386, x86_64 and ia64 (FETCHADD), and of those only i386 and ia64 actually use the XADD-optimised rwsems. Andi wants x86_64 to use the spinlock version.

Quoted 8 lines

Everywhere else, XADD is emulated.

If you have to emulate XADD by using CMPXCHG or LL/SC equivalents, then there're actually better ways of doing things than either of these approaches that the kernel currently has. I just need to find the time to explore them.

Look at how the counter works in the XADD-based version. That's the way it is *because* I'm using XADD. That's quite limiting.

Not really. ll/sc architectures "emulate" xadd the same as they would emulate a spinlock. There is nothing suboptimal about it.

Look at alpha or powerpc, for example.

Quoted 4 lines
Quoted 2 lines

If it hurts, we can special case it. This really doesn't, considering the rarity of rwsems.

If you're willing to special case it, then what's the point in generalising?

Because I don't like the way it is currently done.

Quoted 3 lines

And in case you're wondering, FS-Cache uses a _lot_ of rwsem operations, so I do have an interest in making it quick, and that includes undoing what Ingo did when it's not necessary.

And I bet you couldn't measure a difference, even on FRV.

Quoted 10 lines
Quoted 4 lines

I honestly couldn't see why you went on this tangent last time and I can't see your point now. If FRV only has an SMP safe xchg, then it will need to implement SMP atomics with spinlocks anyway, to get things like add_return.

That's _exactly_ my point.

Think! If you _require_ the use of atomic ops in implementing rwsems, then you introduce _extra_, _general_ spinlocks into the XADD-based algorithm everywhere you call an atomic_xxx() op that has a side effect.

No, only where you also call down into the contended path. I never claimed this is optimal for atomics-with-spinlocks architectures, and I know how they are going to be impacted.

However, it is not 100% clear that they will be slower. For starters, you are using 2 spinlocks, so if there is a lot of contention, you can have concurrent down_read()s go through while the rwsem spinlock is held for a long time while readers are being worken off the wait list.

Quoted 4 lines

And if you're going to have to be getting general spinlocks then the XADD-based rwsem really is worse by quite a bit than the current spinlock-based rwsem as the latter _doesn't_ need general spinlocks as it doesn't use atomic ops.

It is mostly worse in the contended case, in that it needs to take 2 spinlocks where 1 would do. But for *all* other SMP architectures (ie. all - sparc32 - parisc) spinlock design is slower when there is contention. I don't know how you could be advocating the spinlock version on this basis.

FYI, x86-64 uses spinlocks because of the complexity and task limit of the xadd algorithm, not because it was measured to be any faster.

Quoted 11 lines
Quoted 3 lines

And this is relevant how? Why do you imagine that atomic_cmpxchg is so much harder than atomic_add_unless, atomic_add_return (or even atomic_add) on an architecture like this?

It isn't, but atomic_xxx() will _have_ to be implemented with spinlocks.

My point here was that last time I believe you said that FRV managed to implement atomic ops without spinlocks, and so the case wasn't worth considering. My points are that (a) FRV would have to to do SMP, and (b) we have another arch lurking in the wings that does have to use spinlocks because I can't do the clever tricks there that I can on FRV.

So let's take another look when these are in the kernel.

Quoted 5 lines
Quoted 3 lines

Nor did I understand this objection last time. You must have just read the description, rather than the code. I *do* use xadd on x86 for down read (ie. atomic_add_return)

I missed the atomic_add_return(), so I'll forgive you that bit.

You mean I'll forgive you ;) I've been trying to tell you this.

Quoted 9 lines
Quoted 7 lines

And the place where I use cmpxchg *already* uses cmpxchg on i386. Ditto for alpha and powerpc (which are the ones implementing their own rwsem.h of your above list).

Actually all these architectures will generate basically identical code (ignoring ool vs inline). So will all the UP architectures that supress interrupts for atomic ops.

Alpha and powerpc emulate XADD, so see above.

They *implement* atomic_add_return.

Quoted 5 lines
Quoted 2 lines

Which is why I'd prefer not to use it. The current rwsem stuff is much worse though, which is why I'd consider it.

No, it isn't. It's much more straightforward; or at least it was until Ingo decided to rearrange things.

Well I'm working with the mainline kernel.

Anyway, IMO it is cleaner to have down_read be a generic function which calls into an arch helper to perform some simple procedure, rather than have any architecture able implement a completely different algorithm.

Quoted 4 lines
Quoted 2 lines

2 designs, 8 or so implementations (some subtly different) implemented in arch specific asm.

Yes, and?

Ah, that explains why you think this is pointless: you don't think that is a problem. OK... if you think it is not then I won't be able to convince you otherwise.

Quoted 9 lines
Quoted 4 lines

I moved to the implementation on the most widely used and tested arch, as well as the ones which have the most parallelism and weakly ordered memory (i386, powerpc, ia64). I figure this is likely to be adequately scalable and have less chance of being buggy.

The spinlock-based approach is easier to verify and has been tested on more archs than the other. I don't think either of them is more buggy than the other. The spinlock-based rwsems are also used on i386 under some circumstances.

On UP architectures, maybe. That's not too interesting.

Quoted 11 lines
Quoted 6 lines
Quoted 4 lines

Actually, the code isn't anywhere near as difficult to read as the mutex code or the spinlock code. The fastcall "junk" is quite important wrt the i386 code and permitted a small speedup (though if we compile with regparms=3 nowadays, then the advantage is actually bypassed).

No objections, then?

WRONG!

Remove the fastcall and the i386 rwsems will cease to function if CONFIG_REGPARM=n.

WRONG! Because they aren't called by assembly anymore. But if it means that much to you, the fastcalls can stay.

Quoted 4 lines
Quoted 2 lines

Of course the code is slower when it is in L0 icache. I'm sure you know that smaller code is the whole point...

Not necessarily. Faster code may also be the whole point; it depends on what

Do you have to argue everything? I mean the whole point of OOLing spinlocks and mutexes is to generate smaller code (with associated benefits like reuse of branch predictor).

Anyway, this is not a big deal. If you want to continue arguing the point, we can if we get past the other points.

#6 lore raw
Quoted 5 lines · Nick Piggin
Quoted 2 lines

Look at how the counter works in the XADD-based version. That's the way it is *because* I'm using XADD. That's quite limiting.

Not really. ll/sc architectures "emulate" xadd the same as they would emulate a spinlock. There is nothing suboptimal about it.

Yes, really. You've missed the point entirely. Look at *how* the counter *works*.

David

#7 lore raw
Quoted 10 lines · David Howells
Quoted 5 lines · Nick Piggin
Quoted 2 lines

Look at how the counter works in the XADD-based version. That's the way it is *because* I'm using XADD. That's quite limiting.

Not really. ll/sc architectures "emulate" xadd the same as they would emulate a spinlock. There is nothing suboptimal about it.

Yes, really. You've missed the point entirely. Look at *how* the counter *works*.

OK, I've looked but I can't see how you would make it more optimal on an ll/sc architecture. The atomic_add_return variant has no more atomic or barrier operations than the spinlock one, and it has less loads and branches.