Skip to contentSkip to conversation

Fast Userspace Mutexes.

PATCH New Rusty Russell 1 participant 1 message Mar 1, 2002

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

PATCH 1/1 Fast Userspace Mutexes.

OK. New implementation. Compiles (PPC), but due to personal reasons, UNTESTED. Thanks especially to Hubertus for his prior work and feedback.

1) Turned into syscalls.
2) Added arch-specific sys_futex_region() to enable mutexes on region, and give a chance to detect lack of support via -ENOSYS.
3) Just a single atomic_t variable for mutex (thanks Paul M).
- This means -ENOSYS on SMP 386s, as we need cmpxchg.
- We can no longer do generic semaphores: mutexes only.
- Requires arch __update_count atomic op.
4) Current valid args to sys_futex are -1 and +1: we can implement other lock types by using other values later (eg. rw locks).

Size of futex.c dropped from 244 to 161 lines, so it's clearly 40% better!

Get your complaints in now...
Rusty.
--
Anyone who quotes me in their sig is an idiot. -- Rusty Russell.

kernel/Makefile +1 -1
diff -urN -I \$.*\$ --exclude TAGS -X /home/rusty/devel/kernel/kernel-patches/current-dontdiff --minimal linux-2.5.6-pre1/kernel/Makefile working-2.5.6-pre1-futex/kernel/Makefile
@@ -15,7 +15,7 @@
 obj-y     = sched.o dma.o fork.o exec_domain.o panic.o printk.o \
 	    module.o exit.o itimer.o info.o time.o softirq.o resource.o \
 	    sysctl.o acct.o capability.o ptrace.o timer.o user.o \
-	    signal.o sys.o kmod.o context.o 
+	    signal.o sys.o kmod.o context.o futex.o
 
 obj-$(CONFIG_UID16) += uid16.o
 obj-$(CONFIG_MODULES) += ksyms.o
kernel/futex.c +161 -0

161 lines not on this page · raw message

arch/i386/kernel/entry.S +2 -0
diff -urN -I \$.*\$ --exclude TAGS -X /home/rusty/devel/kernel/kernel-patches/current-dontdiff --minimal linux-2.5.6-pre1/arch/i386/kernel/entry.S working-2.5.6-pre1-futex/arch/i386/kernel/entry.S
@@ -716,6 +716,8 @@
 	.long SYMBOL_NAME(sys_lremovexattr)
 	.long SYMBOL_NAME(sys_fremovexattr)
 	.long SYMBOL_NAME(sys_tkill)
+	.long SYMBOL_NAME(sys_futex_region)
+	.long SYMBOL_NAME(sys_futex)		/* 240 */
 
 	.rept NR_syscalls-(.-sys_call_table)/4
 		.long SYMBOL_NAME(sys_ni_syscall)
arch/i386/kernel/sys_i386.c +10 -0
diff -urN -I \$.*\$ --exclude TAGS -X /home/rusty/devel/kernel/kernel-patches/current-dontdiff --minimal linux-2.5.6-pre1/arch/i386/kernel/sys_i386.c working-2.5.6-pre1-futex/arch/i386/kernel/sys_i386.c
@@ -254,3 +254,13 @@
 	return -ERESTARTNOHAND;
 }
 
+/* Nothing special needs to be done to use atomic ops in userspace */
+asmlinkage int sys_futex_region(const void *uaddr, size_t len)
+{
+#ifndef __HAVE_ARCH_UPDATE_COUNT
+	/* Give them warning that SMP 386 kernels don't support this. */
+	return -ENOSYS;
+#else
+	return 0;
+#endif
+}
arch/ppc/kernel/misc.S +2 -0
diff -urN -I \$.*\$ --exclude TAGS -X /home/rusty/devel/kernel/kernel-patches/current-dontdiff --minimal linux-2.5.6-pre1/arch/ppc/kernel/misc.S working-2.5.6-pre1-futex/arch/ppc/kernel/misc.S
@@ -1246,6 +1246,8 @@
 	.long sys_removexattr
 	.long sys_lremovexattr
 	.long sys_fremovexattr	/* 220 */
+	.long sys_futex_region
+	.long sys_futex
 	.rept NR_syscalls-(.-sys_call_table)/4
 		.long sys_ni_syscall
 	.endr
arch/ppc/kernel/semaphore.c +4 -32
diff -urN -I \$.*\$ --exclude TAGS -X /home/rusty/devel/kernel/kernel-patches/current-dontdiff --minimal linux-2.5.6-pre1/arch/ppc/kernel/semaphore.c working-2.5.6-pre1-futex/arch/ppc/kernel/semaphore.c
@@ -21,34 +21,6 @@
 #include <asm/atomic.h>
 #include <asm/semaphore.h>
 
-/*
- * Atomically update sem->count.
- * This does the equivalent of the following:
- *
- *	old_count = sem->count;
- *	tmp = MAX(old_count, 0) + incr;
- *	sem->count = tmp;
- *	return old_count;
- */
-static inline int __sem_update_count(struct semaphore *sem, int incr)
-{
-	int old_count, tmp;
-
-	__asm__ __volatile__("\n"
-"1:	lwarx	%0,0,%3\n"
-"	srawi	%1,%0,31\n"
-"	andc	%1,%0,%1\n"
-"	add	%1,%1,%4\n"
-	PPC405_ERR77(0,%3)
-"	stwcx.	%1,0,%3\n"
-"	bne	1b"
-	: "=&r" (old_count), "=&r" (tmp), "=m" (sem->count)
-	: "r" (&sem->count), "r" (incr), "m" (sem->count)
-	: "cc");
-
-	return old_count;
-}
-
 void __up(struct semaphore *sem)
 {
 	/*
@@ -59,7 +31,7 @@
 	 * (i.e. because some other cpu has called up() in the meantime),
 	 * in which case we just increment count.
 	 */
-	__sem_update_count(sem, 1);
+	__update_count(&sem->count, 1);
 	wake_up(&sem->wait);
 }
 
@@ -86,7 +58,7 @@
 	 * If the count is 0 or negative, we set it to -1, indicating
 	 * that we are asleep, and then sleep.
 	 */
-	while (__sem_update_count(sem, -1) <= 0) {
+	while (__update_count(&sem->count, -1) <= 0) {
 		schedule();
 		tsk->state = TASK_UNINTERRUPTIBLE;
 	}
@@ -111,14 +83,14 @@
 	add_wait_queue_exclusive(&sem->wait, &wait);
 	smp_wmb();
 
-	while (__sem_update_count(sem, -1) <= 0) {
+	while (__update_count(&sem->count, -1) <= 0) {
 		if (signal_pending(current)) {
 			/*
 			 * A signal is pending - give up trying.
 			 * Set sem->count to 0 if it is negative,
 			 * since we are no longer sleeping.
 			 */
-			__sem_update_count(sem, 0);
+			__update_count(&sem->count, 0);
 			retval = -EINTR;
 			break;
 		}
arch/ppc/mm/ppc_mmu.c +6 -0
diff -urN -I \$.*\$ --exclude TAGS -X /home/rusty/devel/kernel/kernel-patches/current-dontdiff --minimal linux-2.5.6-pre1/arch/ppc/mm/ppc_mmu.c working-2.5.6-pre1-futex/arch/ppc/mm/ppc_mmu.c
@@ -304,3 +304,9 @@
 		add_hash_page(mm->context, address, ptep);
 	}
 }
+
+/* Nothing special needs to be done to use atomic ops in userspace */
+asmlinkage int sys_futex_region(const void *uaddr, size_t len)
+{
+	return 0;
+}
include/asm-i386/atomic.h +41 -0

51 lines not on this page · raw message

include/asm-i386/unistd.h +2 -0
diff -urN -I \$.*\$ --exclude TAGS -X /home/rusty/devel/kernel/kernel-patches/current-dontdiff --minimal linux-2.5.6-pre1/include/asm-i386/unistd.h working-2.5.6-pre1-futex/include/asm-i386/unistd.h
@@ -243,6 +243,8 @@
 #define __NR_lremovexattr	236
 #define __NR_fremovexattr	237
 #define __NR_tkill		238
+#define __NR_futex_region	239
+#define __NR_futex		240
 
 /* user-visible error numbers are in the range -1 - -124: see <asm-i386/errno.h> */
 
include/asm-ppc/atomic.h +26 -0
diff -urN -I \$.*\$ --exclude TAGS -X /home/rusty/devel/kernel/kernel-patches/current-dontdiff --minimal linux-2.5.6-pre1/include/asm-ppc/atomic.h working-2.5.6-pre1-futex/include/asm-ppc/atomic.h
@@ -198,5 +198,31 @@
 #define smp_mb__before_atomic_inc()	smp_mb()
 #define smp_mb__after_atomic_inc()	smp_mb()
 
+/*
+ * Atomically update count.
+ * This does the equivalent of the following:
+ *
+ *	old_count = *count;
+ *	tmp = MAX(old_count, 0) + incr;
+ *	*count = tmp;
+ *	return old_count;
+ */
+static inline int __update_count(atomic_t *count, int incr)
+{
+	int old_count, tmp;
+
+	__asm__ __volatile__("\n"
+"1:	lwarx	%0,0,%3\n"
+"	srawi	%1,%0,31\n"
+"	andc	%1,%0,%1\n"
+"	add	%1,%1,%4\n"
+"	stwcx.	%1,0,%3\n"
+"	bne	1b"
+	: "=&r" (old_count), "=&r" (tmp), "=m" (*count)
+	: "r" (count), "r" (incr), "m" (*count)
+	: "cc");
+
+	return old_count;
+}
 #endif /* __KERNEL__ */
 #endif /* _ASM_PPC_ATOMIC_H_ */
include/asm-ppc/unistd.h +2 -0
diff -urN -I \$.*\$ --exclude TAGS -X /home/rusty/devel/kernel/kernel-patches/current-dontdiff --minimal linux-2.5.6-pre1/include/asm-ppc/unistd.h working-2.5.6-pre1-futex/include/asm-ppc/unistd.h
@@ -228,6 +228,8 @@
 #define __NR_removexattr	218
 #define __NR_lremovexattr	219
 #define __NR_fremovexattr	220
+#define __NR_futex_region	221
+#define __NR_futex		222
 
 #define __NR(n)	#n
 
include/linux/hash.h +58 -0

58 lines not on this page · raw message

include/linux/mmzone.h +2 -3
diff -urN -I \$.*\$ --exclude TAGS -X /home/rusty/current-dontdiff --minimal linux-2.5.5/include/linux/mmzone.h working-2.5.5-usem/include/linux/mmzone.h
@@ -51,8 +51,7 @@
 	/*
 	 * wait_table		-- the array holding the hash table
 	 * wait_table_size	-- the size of the hash table array
-	 * wait_table_shift	-- wait_table_size
-	 * 				== BITS_PER_LONG (1 << wait_table_bits)
+	 * wait_table_bits	-- wait_table_size == (1 << wait_table_bits)
 	 *
 	 * The purpose of all these is to keep track of the people
 	 * waiting for a page to become available and make them
@@ -75,7 +74,7 @@
 	 */
 	wait_queue_head_t	* wait_table;
 	unsigned long		wait_table_size;
-	unsigned long		wait_table_shift;
+	unsigned long		wait_table_bits;
 
 	/*
 	 * Discontig memory support fields.
mm/filemap.c +2 -25
diff -urN -I \$.*\$ --exclude TAGS -X /home/rusty/current-dontdiff --minimal linux-2.5.5/mm/filemap.c working-2.5.5-usem/mm/filemap.c
@@ -25,6 +25,7 @@
 #include <linux/iobuf.h>
 #include <linux/compiler.h>
 #include <linux/fs.h>
+#include <linux/hash.h>
 
 #include <asm/pgalloc.h>
 #include <asm/uaccess.h>
@@ -773,32 +774,8 @@
 static inline wait_queue_head_t *page_waitqueue(struct page *page)
 {
 	const zone_t *zone = page_zone(page);
-	wait_queue_head_t *wait = zone->wait_table;
-	unsigned long hash = (unsigned long)page;
 
-#if BITS_PER_LONG == 64
-	/*  Sigh, gcc can't optimise this alone like it does for 32 bits. */
-	unsigned long n = hash;
-	n <<= 18;
-	hash -= n;
-	n <<= 33;
-	hash -= n;
-	n <<= 3;
-	hash += n;
-	n <<= 3;
-	hash -= n;
-	n <<= 4;
-	hash += n;
-	n <<= 2;
-	hash += n;
-#else
-	/* On some cpus multiply is faster, on others gcc will do shifts */
-	hash *= GOLDEN_RATIO_PRIME;
-#endif
-
-	hash >>= zone->wait_table_shift;
-
-	return &wait[hash];
+	return &zone->wait_table[hash_ptr(page, zone->wait_table_bits)];
 }
 
 /* 
mm/page_alloc.c +2 -2
diff -urN -I \$.*\$ --exclude TAGS -X /home/rusty/current-dontdiff --minimal linux-2.5.5/mm/page_alloc.c working-2.5.5-usem/mm/page_alloc.c
@@ -776,8 +776,8 @@
 		 * per zone.
 		 */
 		zone->wait_table_size = wait_table_size(size);
-		zone->wait_table_shift =
-			BITS_PER_LONG - wait_table_bits(zone->wait_table_size);
+		zone->wait_table_bits =
+			wait_table_bits(zone->wait_table_size);
 		zone->wait_table = (wait_queue_head_t *)
 			alloc_bootmem_node(pgdat, zone->wait_table_size
 						* sizeof(wait_queue_head_t));