alpha: half done futex implementation

alpha: half done futex implementation

[Matt Turner]

Hi,

Going on Richard's advice, I've tried to write an alpha futex
implementation based on the powerpc futex.h.

I've gotten this far.. :\

#define __futex_atomic_op(insn, ret, oldval, uaddr, oparg) \
    __asm__ __volatile(             \
    "1: ldl_l   %0,%2\n"            \
        insn                        \
    /* something needs to happen here
     * to save result of insn across
     * stl_c? */
    "   stl_c   %1,%2\n"            \
    "   beq     %1,2f\n"            \
    "   mb\n"                       \
    /* something needs to happen here
     * for the ret */
    "   .subsection 2\n"            \
    "2: br      1b\n"               \
    "   .previous\n"                \
    : "=&r" (oldval), "=&r" (ret)   \
    : "b" (uaddr) \
    : "memory")

Could someone take a look and help finish it?

For futex_atomic_cmpxchg_inatomic, I think Ivan's DRM_CAS
implementation can be used with only trivial changes. See
http://cgit.freedesktop.org/mesa/drm/commit/?id=6feac49398d0f037103a4ae3d5a512badeed61fb

Please CC me on responses, as I'm not subscribed to linux-kernel@.

Thanks,

Matt Turner

Re: alpha: half done futex implementation

[Tobias Klausmann]

Hi! 

30-rc1 doesn't compile on alpha:

net/socket.c: In function 'sock_alloc':
net/socket.c:496: error: implicit declaration of function 'percpu_add'
net/socket.c:496: error: 'sockets_in_use' undeclared (first use in this function)
net/socket.c:496: error: (Each undeclared identifier is reported only once
net/socket.c:496: error: for each function it appears in.)
net/socket.c: In function 'sock_release':
net/socket.c:538: error: implicit declaration of function 'percpu_sub'
net/socket.c:538: error: 'sockets_in_use' undeclared (first use in this function)

I vaguely remember seeing discussion about this on lkml, but I
can't find it right now.

gcc is 4.3.3. Distro is Gentoo, machine is a UP1500 (Nautilus).

Regards,
Tobias

-- 
Save a tree - disband an ISO working group today.

Re: alpha: half done futex implementation

[Richard Henderson]

Matt Turner wrote:
> Hi,
> 
> Going on Richard's advice, I've tried to write an alpha futex
> implementation based on the powerpc futex.h.
> 
> I've gotten this far.. :\
> 

#define __futex_atomic_op(insn, ret, oldval, uaddr, oparg) \
      __asm__ __volatile(             \
      __ASM_MB                        \
      "1: ldl_l   %0,0(%3)\n"         \
          insn                        \
      "2: stl_c   %1,0(%3)\n"         \
      "   beq     %1,4f\n"            \
      "   mov     $31,%1\n"           \
      "3: .subsection 2\n"            \
      "4: br      1b\n"               \
      "   .previous\n"                \
      ".section __ex_table,\"a\"\n"   \
      "   .long   1b-.\n"             \
      "   lda     %0,3b-1b(%2)\n"     \
      "   .long   2b-.\n"             \
      "   lda     %0,3b-2b(%2)\n"     \
      "   .previous\n"                \
      : "=&r" (oldval), "=&r"(ret)    \
      : "r" (uaddr), "r"(oparg)       \
      : "memory")

   switch (op) {
     case FUTEX_OP_SET:
       __futex_atomic_op("mov %0,%1", ret, oldval, uaddr, oparg);
       break;
     case FUTEX_OP_ADD:
       __futex_atomic_op("addl %0,%4,%1\n", ret, oldval, uaddr, oparg);
       break;
     case FUTEX_OP_OR:
       __futex_atomic_op("or %0,%4,%1\n", ret, oldval, uaddr, oparg);
       break;
     case FUTEX_OP_ANDN:
       __futex_atomic_op("andnot %0,%4,%1\n", ret, oldval, uaddr, oparg);
       break;
     case FUTEX_OP_XOR:
       __futex_atomic_op("xor %0,%4,%1\n", ret, oldval, uaddr, oparg);
       break;
     default:
       ret = -ENOSYS;
   }


Also, there's a bug in the powerpc implementation.  It appears that 
oparg is clobbered, and if stwcx fails the operation will be repeated 
with incorrect inputs.


r~

Re: alpha: half done futex implementation

[Andreas Schwab]

Richard Henderson <rth@twiddle.net> writes:

>   switch (op) {
>     case FUTEX_OP_SET:
>       __futex_atomic_op("mov %0,%1", ret, oldval, uaddr, oparg);

That should probably be "mov %4,%1\n"?

Andreas.

-- 
Andreas Schwab, schwab@linux-m68k.org
GPG Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: alpha: half done futex implementation

[Richard Henderson]

Andreas Schwab wrote:
> Richard Henderson <rth@twiddle.net> writes:
> 
>>   switch (op) {
>>     case FUTEX_OP_SET:
>>       __futex_atomic_op("mov %0,%1", ret, oldval, uaddr, oparg);
> 
> That should probably be "mov %4,%1\n"?

You're right.


r~

Re: alpha: half done futex implementation

[Segher Boessenkool]

> Also, there's a bug in the powerpc implementation.  It appears that  
> oparg is clobbered, and if stwcx fails the operation will be  
> repeated with incorrect inputs.

If either the lwarx or the stwcx. faults, the routine returns -EFAULT
and doesn't retry (label "3" is the end of the asm).

If the stwcx. fails because the CPU lost the reservation, %1 isn't
clobbered as far as I see?


Segher

Re: alpha: half done futex implementation

[Segher Boessenkool]

> If either the lwarx or the stwcx. faults, the routine returns -EFAULT
> and doesn't retry (label "3" is the end of the asm).
>
> If the stwcx. fails because the CPU lost the reservation, %1 isn't
> clobbered as far as I see?

Oh, "insn" writes to %1, never mind.


Segher

Re: alpha: half done futex implementation

[Matt Turner]

[-- Attachment #1: Type: text/plain, Size: 521 bytes --]

Hi,

Attached is a patch to (almost) add native futex support to Alpha.

It doesn't compile...

  CC      kernel/futex.o
kernel/futex.c: In function 'do_futex':
/usr/src/linux-radeon/glisse-drm/arch/alpha/include/asm/futex.h:47:
error: invalid 'asm': operand number out of range
{standard input}: Assembler messages:
{standard input}:3722: Error: bad expression
{standard input}:3722: Error: syntax error

I can't make much sense out of that.

I changed the %4's to %3 as we don't have a %4.

Please review.

Matt Turner

[-- Attachment #2: add-native-futex-support-on-alpha.patch --]
[-- Type: application/octet-stream, Size: 3141 bytes --]

diff --git a/arch/alpha/include/asm/futex.h b/arch/alpha/include/asm/futex.h
index 6a332a9..45b54fa 100644
--- a/arch/alpha/include/asm/futex.h
+++ b/arch/alpha/include/asm/futex.h
@@ -1,6 +1,115 @@
-#ifndef _ASM_FUTEX_H
-#define _ASM_FUTEX_H
+#ifndef _ASM_ALPHA_FUTEX_H
+#define _ASM_ALPHA_FUTEX_H
 
-#include <asm-generic/futex.h>
+#ifdef __KERNEL__
 
+#include <linux/futex.h>
+#include <linux/uaccess.h>
+#include <asm/errno.h>
+
+#define __futex_atomic_op(insn, ret, oldval, uaddr, oparg) \
+	__asm__ __volatile(				\
+	"1:	ldl_l	%0,0(%3)\n"			\
+	insn							\
+	"2:	stl_c	%1,0(%3)\n"			\
+	"	beq		%1,4f\n"			\
+	"	mov		$31,%1\n"			\
+	"3:	.subsection 2\n"			\
+	"4:	br		1b\n"				\
+	"	.previous\n"				\
+	"	.section __ex_table,\"a\"\n"\
+	"	.long	1b-.\n"				\
+	"	lda		%0,3b-1b(%2)\n"		\
+		".long	2b-.\n"				\
+	"	lda		%0,3b-2b(%2)\n"		\
+	"	.previous\n"				\
+	:	"=&r" (oldval), "=&r"(ret)	\
+	:	"r" (uaddr), "r"(oparg)		\
+	:	"memory")
+
+static inline int futex_atomic_op_inuser (int encoded_op, int __user *uaddr)
+{
+	int op = (encoded_op >> 28) & 7;
+	int cmp = (encoded_op >> 24) & 15;
+	int oparg = (encoded_op << 8) >> 20;
+	int cmparg = (encoded_op << 20) >> 20;
+	int oldval = 0, ret;
+	if (encoded_op & (FUTEX_OP_OPARG_SHIFT << 28))
+		oparg = 1 << oparg;
+
+	if (! access_ok (VERIFY_WRITE, uaddr, sizeof(int)))
+		return -EFAULT;
+
+	pagefault_disable();
+
+	switch (op) {
+	case FUTEX_OP_SET:
+		__futex_atomic_op("mov %3,%1", ret, oldval, uaddr, oparg);
+		break;
+	case FUTEX_OP_ADD:
+		__futex_atomic_op("addl %0,%3,%1\n", ret, oldval, uaddr, oparg);
+		break;
+	case FUTEX_OP_OR:
+		__futex_atomic_op("or %0,%3,%1\n", ret, oldval, uaddr, oparg);
+		break;
+	case FUTEX_OP_ANDN:
+		__futex_atomic_op("andnot %0,%3,%1\n", ret, oldval, uaddr, oparg);
+		break;
+	case FUTEX_OP_XOR:
+		__futex_atomic_op("xor %0,%3,%1\n", ret, oldval, uaddr, oparg);
+		break;
+	default:
+		ret = -ENOSYS;
+	}
+
+	pagefault_enable();
+
+	if (!ret) {
+		switch (cmp) {
+		case FUTEX_OP_CMP_EQ: ret = (oldval == cmparg); break;
+		case FUTEX_OP_CMP_NE: ret = (oldval != cmparg); break;
+		case FUTEX_OP_CMP_LT: ret = (oldval < cmparg); break;
+		case FUTEX_OP_CMP_GE: ret = (oldval >= cmparg); break;
+		case FUTEX_OP_CMP_LE: ret = (oldval <= cmparg); break;
+		case FUTEX_OP_CMP_GT: ret = (oldval > cmparg); break;
+		default: ret = -ENOSYS;
+		}
+	}
+	return ret;
+}
+
+static inline int
+futex_atomic_cmpxchg_inatomic(int __user *uaddr, int oldval, int newval)
+{
+	int prev;
+
+	if (!access_ok(VERIFY_WRITE, uaddr, sizeof(int)))
+		return -EFAULT;
+
+	__asm__ __volatile__ (
+#ifdef CONFIG_SMP
+	"	mb\n"
 #endif
+	"1:	ldl_l	%0,0(%3)        # futex_atomic_cmpxchg_inatomic\n"
+	"	cmpeq	%0,%3,%0\n"
+	"	beq		%0,3f\n"
+	"2:	stl_c	%4,0(%2)\n"
+	"	beq		%4,1b\n"
+	"3:	.subsection 2\n"
+	"4:	br		1b\n"
+	"	.previous\n"
+	"	.section __ex_table,\"a\"\n"
+	"	.long	1b-.\n"
+	"	lda		%0,3b-1b(%2)\n"
+		".long	2b-.\n"
+	"	lda		%0,3b-2b(%2)\n"
+	"	.previous\n"
+	: "=&r" (prev), "+m" (*uaddr)
+	: "r" (uaddr), "r" (oldval), "r" (newval), "i" (-EFAULT)
+	: "memory");
+
+	return prev;
+}
+
+#endif /* __KERNEL__ */
+#endif /* _ASM_ALPHA_FUTEX_H */

Re: alpha: half done futex implementation

[Ivan Kokshaysky]

On Tue, Apr 14, 2009 at 06:38:52PM -0400, Matt Turner wrote:
>   CC      kernel/futex.o
> kernel/futex.c: In function 'do_futex':
> /usr/src/linux-radeon/glisse-drm/arch/alpha/include/asm/futex.h:47:
> error: invalid 'asm': operand number out of range
> {standard input}: Assembler messages:
> {standard input}:3722: Error: bad expression
> {standard input}:3722: Error: syntax error
> 
> I can't make much sense out of that.
> 
> I changed the %4's to %3 as we don't have a %4.

Other operands are messed up too.

Here is compile-tested variant.

Ivan.

---
 arch/alpha/include/asm/barrier.h |    2 +
 arch/alpha/include/asm/futex.h   |  118 ++++++++++++++++++++++++++++++++++++-
 2 files changed, 116 insertions(+), 4 deletions(-)

diff --git a/arch/alpha/include/asm/barrier.h b/arch/alpha/include/asm/barrier.h
index ac78eba..ce8860a 100644
--- a/arch/alpha/include/asm/barrier.h
+++ b/arch/alpha/include/asm/barrier.h
@@ -16,11 +16,13 @@ __asm__ __volatile__("wmb": : :"memory")
 __asm__ __volatile__("mb": : :"memory")
 
 #ifdef CONFIG_SMP
+#define __ASM_SMP_MB	"\tmb\n"
 #define smp_mb()	mb()
 #define smp_rmb()	rmb()
 #define smp_wmb()	wmb()
 #define smp_read_barrier_depends()	read_barrier_depends()
 #else
+#define __ASM_SMP_MB
 #define smp_mb()	barrier()
 #define smp_rmb()	barrier()
 #define smp_wmb()	barrier()
diff --git a/arch/alpha/include/asm/futex.h b/arch/alpha/include/asm/futex.h
index 6a332a9..f18ea4e 100644
--- a/arch/alpha/include/asm/futex.h
+++ b/arch/alpha/include/asm/futex.h
@@ -1,6 +1,116 @@
-#ifndef _ASM_FUTEX_H
-#define _ASM_FUTEX_H
+#ifndef _ASM_ALPHA_FUTEX_H
+#define _ASM_ALPHA_FUTEX_H
 
-#include <asm-generic/futex.h>
+#ifdef __KERNEL__
 
-#endif
+#include <linux/futex.h>
+#include <linux/uaccess.h>
+#include <asm/errno.h>
+#include <asm/barrier.h>
+
+#define __futex_atomic_op(insn, ret, oldval, uaddr, oparg)	\
+	__asm__ __volatile__(					\
+		__ASM_SMP_MB					\
+	"1:	ldl_l	%0,0(%2)\n"				\
+		insn						\
+	"2:	stl_c	%1,0(%2)\n"				\
+	"	beq	%1,4f\n"				\
+	"	mov	$31,%1\n"				\
+	"3:	.subsection 2\n"				\
+	"4:	br	1b\n"					\
+	"	.previous\n"					\
+	"	.section __ex_table,\"a\"\n"			\
+	"	.long	1b-.\n"					\
+	"	lda	$31,3b-1b(%1)\n"			\
+	"	.long	2b-.\n"					\
+	"	lda	$31,3b-2b(%1)\n"			\
+	"	.previous\n"					\
+	:	"=&r" (oldval), "=&r"(ret)			\
+	:	"r" (uaddr), "r"(oparg)				\
+	:	"memory")
+
+static inline int futex_atomic_op_inuser (int encoded_op, int __user *uaddr)
+{
+	int op = (encoded_op >> 28) & 7;
+	int cmp = (encoded_op >> 24) & 15;
+	int oparg = (encoded_op << 8) >> 20;
+	int cmparg = (encoded_op << 20) >> 20;
+	int oldval = 0, ret;
+	if (encoded_op & (FUTEX_OP_OPARG_SHIFT << 28))
+		oparg = 1 << oparg;
+
+	if (!access_ok(VERIFY_WRITE, uaddr, sizeof(int)))
+		return -EFAULT;
+
+	pagefault_disable();
+
+	switch (op) {
+	case FUTEX_OP_SET:
+		__futex_atomic_op("mov %3,%1\n", ret, oldval, uaddr, oparg);
+		break;
+	case FUTEX_OP_ADD:
+		__futex_atomic_op("addl %0,%3,%1\n", ret, oldval, uaddr, oparg);
+		break;
+	case FUTEX_OP_OR:
+		__futex_atomic_op("or %0,%3,%1\n", ret, oldval, uaddr, oparg);
+		break;
+	case FUTEX_OP_ANDN:
+		__futex_atomic_op("andnot %0,%3,%1\n", ret, oldval, uaddr, oparg);
+		break;
+	case FUTEX_OP_XOR:
+		__futex_atomic_op("xor %0,%3,%1\n", ret, oldval, uaddr, oparg);
+		break;
+	default:
+		ret = -ENOSYS;
+	}
+
+	pagefault_enable();
+
+	if (!ret) {
+		switch (cmp) {
+		case FUTEX_OP_CMP_EQ: ret = (oldval == cmparg); break;
+		case FUTEX_OP_CMP_NE: ret = (oldval != cmparg); break;
+		case FUTEX_OP_CMP_LT: ret = (oldval < cmparg); break;
+		case FUTEX_OP_CMP_GE: ret = (oldval >= cmparg); break;
+		case FUTEX_OP_CMP_LE: ret = (oldval <= cmparg); break;
+		case FUTEX_OP_CMP_GT: ret = (oldval > cmparg); break;
+		default: ret = -ENOSYS;
+		}
+	}
+	return ret;
+}
+
+static inline int
+futex_atomic_cmpxchg_inatomic(int __user *uaddr, int oldval, int newval)
+{
+	int prev, cmp;
+
+	if (!access_ok(VERIFY_WRITE, uaddr, sizeof(int)))
+		return -EFAULT;
+
+	__asm__ __volatile__ (
+		__ASM_SMP_MB					\
+	"1:	ldl_l	%0,0(%2)\n"
+	"	cmpeq	%0,%3,%1\n"
+	"	beq	%1,3f\n"
+	"	mov	%4,%1\n"
+	"2:	stl_c	%1,0(%2)\n"
+	"	beq	%1,4f\n"
+	"3:	.subsection 2\n"
+	"4:	br	1b\n"
+	"	.previous"
+	"	.section __ex_table,\"a\"\n"
+	"	.long	1b-.\n"
+	"	lda	$31,3b-1b(%0)\n"
+	"	.long	2b-.\n"
+	"	lda	$31,3b-2b(%0)\n"
+	"	.previous\n"
+	:	"=&r"(prev), "=&r"(cmp)
+	:	"r"(uaddr), "r"((long)oldval), "r"(newval)
+	:	"memory");
+
+	return prev;
+}
+
+#endif /* __KERNEL__ */
+#endif /* _ASM_ALPHA_FUTEX_H */

Re: alpha: half done futex implementation

[Ivan Kokshaysky]

On Wed, Apr 15, 2009 at 08:55:52PM -0400, Matt Turner wrote:
> I tested the patch, unfortunately it causes the kernel to panic on start up.

Ah, I see.

Exception fixups for sections other than .text (like one in
futex_init()) break the natural ordering of fixup entries,
so sorting is required.

Without that the result of the exception table search depends
on phase of the moon.

Ivan.

diff --git a/arch/alpha/include/asm/uaccess.h b/arch/alpha/include/asm/uaccess.h
index 163f305..b49ec2f 100644
--- a/arch/alpha/include/asm/uaccess.h
+++ b/arch/alpha/include/asm/uaccess.h
@@ -507,5 +507,7 @@ struct exception_table_entry
 	(pc) + (_fixup)->fixup.bits.nextinsn;			\
 })
 
+#define ARCH_HAS_SORT_EXTABLE
+#define ARCH_HAS_SEARCH_EXTABLE
 
 #endif /* __ALPHA_UACCESS_H */
diff --git a/arch/alpha/mm/extable.c b/arch/alpha/mm/extable.c
index dc7aeda..62dc379 100644
--- a/arch/alpha/mm/extable.c
+++ b/arch/alpha/mm/extable.c
@@ -3,11 +3,49 @@
  */
 
 #include <linux/module.h>
+#include <linux/sort.h>
 #include <asm/uaccess.h>
 
+static inline unsigned long ex_to_addr(const struct exception_table_entry *x)
+{
+	return (unsigned long)&x->insn + x->insn;
+}
+
+static void swap_ex(void *a, void *b, int size)
+{
+	struct exception_table_entry *ex_a = a, *ex_b = b;
+	unsigned long addr_a = ex_to_addr(ex_a), addr_b = ex_to_addr(ex_b);
+	unsigned int t = ex_a->fixup.unit;
+
+	ex_a->fixup.unit = ex_b->fixup.unit;
+	ex_b->fixup.unit = t;
+	ex_a->insn = (int)(addr_b - (unsigned long)&ex_a->insn);
+	ex_b->insn = (int)(addr_a - (unsigned long)&ex_b->insn);
+}
+
+/*
+ * The exception table needs to be sorted so that the binary
+ * search that we use to find entries in it works properly.
+ * This is used both for the kernel exception table and for
+ * the exception tables of modules that get loaded.
+ */
+static int cmp_ex(const void *a, const void *b)
+{
+	const struct exception_table_entry *x = a, *y = b;
+
+	/* avoid overflow */
+	if (ex_to_addr(x) > ex_to_addr(y))
+		return 1;
+	if (ex_to_addr(x) < ex_to_addr(y))
+		return -1;
+	return 0;
+}
+
 void sort_extable(struct exception_table_entry *start,
 		  struct exception_table_entry *finish)
 {
+	sort(start, finish - start, sizeof(struct exception_table_entry),
+	     cmp_ex, swap_ex);
 }
 
 const struct exception_table_entry *
@@ -20,7 +58,7 @@ search_extable(const struct exception_table_entry *first,
 		unsigned long mid_value;
 
 		mid = (last - first) / 2 + first;
-		mid_value = (unsigned long)&mid->insn + mid->insn;
+		mid_value = ex_to_addr(mid);
                 if (mid_value == value)
                         return mid;
                 else if (mid_value < value)