PI mutex support on ARM

PI mutex support on ARM

[Remy Bohmer]

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

Hello Thomas,

I have build an implementation for the routine
futex_atomic_cmpxchg_inatomic() to make PTHREAD_PRIO_INHERIT mutex
work on ARM.
Compared to other architectures where CPU specific assembler is used,
it is probably not the most optimal implementation possible, but I
tested it successfully on a Atmel AT91RM9200 core, and it could work
on other (UP) architectures as well.

What do you think of it?
Or do you know a better solution?

Kind Regards,

Remy

[-- Attachment #2: fix-userspace-prio-inherit.patch --]
[-- Type: text/x-patch, Size: 2039 bytes --]

Index: linux-2.6.21/include/asm/futex.h
===================================================================
--- linux-2.6.21.orig/include/asm/futex.h	2007-04-26 05:08:32.000000000 +0200
+++ linux-2.6.21/include/asm/futex.h	2007-07-06 15:11:01.000000000 +0200
@@ -1,6 +1,79 @@
-#ifndef _ASM_FUTEX_H
-#define _ASM_FUTEX_H
+#ifndef _ASM_ARM_FUTEX_H
+#define _ASM_ARM_FUTEX_H
 
-#include <asm-generic/futex.h>
+#ifdef __KERNEL__
+
+#include <linux/futex.h>
+#include <asm/errno.h>
+#include <asm/uaccess.h>
+
+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:
+	case FUTEX_OP_ADD:
+	case FUTEX_OP_OR:
+	case FUTEX_OP_ANDN:
+	case FUTEX_OP_XOR:
+	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 err = 0;
+	int uval;
+	unsigned long flags;
+
+	if (!access_ok(VERIFY_WRITE, uaddr, sizeof(int)))
+		return -EFAULT;
+
+	local_irq_save(flags);
+
+	err = get_user(uval, uaddr);
+	if (err)
+	{
+		local_irq_restore(flags);
+		 return -EFAULT;
+	}
+	if (uval == oldval)
+		err = put_user(newval, uaddr);
+
+	local_irq_restore(flags);
+
+	if (err) return -EFAULT;
+	return uval;
+}
 
 #endif

Re: PI mutex support on ARM

[Ingo Molnar]

* Remy Bohmer <l.pinguin@gmail.com> wrote:

> --- linux-2.6.21.orig/include/asm/futex.h	2007-04-26 05:08:32.000000000 +0200

patch format problem: never diff the asm/ files, diff the asm-arm/ 
files.

> +	local_irq_save(flags);
> +
> +	err = get_user(uval, uaddr);

is it safe to do a get_user() with irqs off?

> +	if (err)
> +	{
> +		local_irq_restore(flags);
> +		 return -EFAULT;
> +	}

(style problems. Use scripts/checkpatch.pl to verify your patches.)

> +	local_irq_restore(flags);

is this method of atomic ops SMP-safe?

	Ingo

Re: PI mutex support on ARM

[Remy Bohmer]

Hello Ingo,

> patch format problem: never diff the asm/ files, diff the asm-arm/ files.
Yeah, of course, I know, I believe I made a real mess of this one ...

> is it safe to do a get_user() with irqs off?
rhetorical question ;-))
I was wondering, Is it safe to use a normal spinlock here, like this?

------- 8-< -------------
	spin_lock(&futex_lock);

	err = get_user(uval, uaddr);
	if ((!err) && (uval == oldval))
		err = put_user(newval, uaddr);

	spin_unlock(&futex_lock);
------- 8-< -------------

> is this method of atomic ops SMP-safe?
another rhetorical question ;-))
Nope, I already knew that, that why I mentioned that it probably only
worked on UP...

Remy

Re: PI mutex support on ARM

[Matthieu CASTET]

Hi,

Remy Bohmer <l.pinguin <at> gmail.com> writes:

> 
> Hello Thomas,
> 
> I have build an implementation for the routine
> futex_atomic_cmpxchg_inatomic() to make PTHREAD_PRIO_INHERIT mutex
> work on ARM.
> Compared to other architectures where CPU specific assembler is used,
> it is probably not the most optimal implementation possible, but I
> tested it successfully on a Atmel AT91RM9200 core, and it could work
> on other (UP) architectures as well.
> 
> What do you think of it?
> Or do you know a better solution?

May be you could have a look at __kuser_cmpxchg (arch/arm/kernel/entry-armv.S).
There stuff for smp for armv6 and newer.
For armv5 and older, maybe masking interrupt is the best solution.


But I believe you should CC arm linux mailling list. You should find more arm
expert :)


Matthieu

Re: PI mutex support on ARM

[Arjan van de Ven]

On Sun, 2007-07-08 at 22:17 +0200, Remy Bohmer wrote:
> Hello Ingo,
> 
> > patch format problem: never diff the asm/ files, diff the asm-arm/ files.
> Yeah, of course, I know, I believe I made a real mess of this one ...
> 
> > is it safe to do a get_user() with irqs off?
> rhetorical question ;-))
> I was wondering, Is it safe to use a normal spinlock here, like this?

if get_user() isn't allowed with irq's off (and in general it's not,
maybe arm is special) then it also isn't allowed with spinlocks held..

Re: PI mutex support on ARM

[Manfred Gruber]

hi !

Is about the PI Mutex issue on ARM some work going on?
Or does someone have an information for me how to implement this for a armv4 
correct ?

thanks
	fred

Re: PI mutex support on ARM

[Russell King - ARM Linux]

On Mon, Aug 20, 2007 at 02:12:17PM +0200, Manfred Gruber wrote:
> Is about the PI Mutex issue on ARM some work going on?

work best sentences when formed properly they're.

> Or does someone have an information for me how to implement this for a armv4 
> correct ?

The futexes are something I've no interest in at the moment since I'm
not running EABI or even TLS based environments.  People who are get
the privilege of solving the problems found there in.

Re: PI mutex support on ARM

[Remy Bohmer]

Hello Manfred,

At http://www.spinics.net/lists/arm-kernel/msg42349.html you can find
a patch that will probably work. Due to the lack of proper atomic
instructions on the ARM-v4 core this patch is likely to be the best
possible solution.

Kind Regards,

Remy

2007/8/20, Manfred Gruber <m.gruber@tirol.com>:
> hi !
>
> Is about the PI Mutex issue on ARM some work going on?
> Or does someone have an information for me how to implement this for a armv4
> correct ?
>
> thanks
>         fred
>
>

Re: PI mutex support on ARM

[Manfred Gruber]

Hi Remy !

thanks a lot, i will test it on a ARM-v4 with 2.6.23-rc2-rt2 and 
2.6.21.5-rt20.

I have a application which makes a lot of pthread_mutex_lock/unlock 
between rt and non-rt tasks with PI. So i will look what happens.

thanks
	fred

Am Monday 20 August 2007 schrieben Sie:
> Hello Manfred,
>
> At http://www.spinics.net/lists/arm-kernel/msg42349.html you can find
> a patch that will probably work. Due to the lack of proper atomic
> instructions on the ARM-v4 core this patch is likely to be the best
> possible solution.
>
> Kind Regards,
>
> Remy

Re: PI mutex support on ARM

[Manfred Gruber]

hi !

I have now run 2.6.23-rc4-rt1 on my arm920t with the pi_stress test programm 
from http://people.redhat.com/williams/tests

My question if I run the pi_stress, my watchdog triggers, if watchdog is 
disabled i get this:

Admin threads running on processor: 0
Test threads running on processor:  0
Starting PI Stress Test
Number of thread groups: 10
Number of inversions per group: infinite
Test threads using scheduler policy: SCHED_FIFO
    Admin thread priority:  4
10 groups of 3 threads will be created
    High thread priority:   3
    Med  thread priority:   2
    Low thread priority:    1
Press Control-C to stop test
Current Inversions: 15551
Keyboard Interrupt!

Stopping test
Total inversion performed: 15570
Test Duration: 0 days, 0 hours, 0 minutes, 14 seconds

Is this the correct behaviour ? Or does it show a problem ?

thanks, regards 
	fred

Am Tuesday 21 August 2007 schrieben Sie:
> Hi Remy !
>
> thanks a lot, i will test it on a ARM-v4 with 2.6.23-rc2-rt2 and
> 2.6.21.5-rt20.
>
> I have a application which makes a lot of pthread_mutex_lock/unlock
> between rt and non-rt tasks with PI. So i will look what happens.
>
> thanks
> 	fred
>
> Am Monday 20 August 2007 schrieben Sie:
> > Hello Manfred,
> >
> > At http://www.spinics.net/lists/arm-kernel/msg42349.html you can find
> > a patch that will probably work. Due to the lack of proper atomic
> > instructions on the ARM-v4 core this patch is likely to be the best
> > possible solution.
> >
> > Kind Regards,
> >
> > Remy
>
> -
> To unsubscribe from this list: send the line "unsubscribe linux-rt-users"
> in the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: PI mutex support on ARM

[Remy Bohmer]

Hello Manfred,

> My question if I run the pi_stress, my watchdog triggers, if watchdog is
> disabled i get this:
> Is this the correct behaviour ? Or does it show a problem ?

Depends on the priority of your watchdog-feeder thread. If it is not
running in RT mode, with a priority higher than used in the pi-stress
test, then yes it is normal that the watchdog kicks in. pi-stress
takes 100% CPU-load, and leaves no room for non-RT processes.

The output you get seems normal to me...

Remy

2007/9/4, Manfred Gruber <m.gruber@tirol.com>:
> hi !
>
> I have now run 2.6.23-rc4-rt1 on my arm920t with the pi_stress test programm
> from http://people.redhat.com/williams/tests
>
> My question if I run the pi_stress, my watchdog triggers, if watchdog is
> disabled i get this:
>
> Admin threads running on processor: 0
> Test threads running on processor:  0
> Starting PI Stress Test
> Number of thread groups: 10
> Number of inversions per group: infinite
> Test threads using scheduler policy: SCHED_FIFO
>     Admin thread priority:  4
> 10 groups of 3 threads will be created
>     High thread priority:   3
>     Med  thread priority:   2
>     Low thread priority:    1
> Press Control-C to stop test
> Current Inversions: 15551
> Keyboard Interrupt!
>
> Stopping test
> Total inversion performed: 15570
> Test Duration: 0 days, 0 hours, 0 minutes, 14 seconds
>
> Is this the correct behaviour ? Or does it show a problem ?
>
> thanks, regards
>         fred
>
> Am Tuesday 21 August 2007 schrieben Sie:
> > Hi Remy !
> >
> > thanks a lot, i will test it on a ARM-v4 with 2.6.23-rc2-rt2 and
> > 2.6.21.5-rt20.
> >
> > I have a application which makes a lot of pthread_mutex_lock/unlock
> > between rt and non-rt tasks with PI. So i will look what happens.
> >
> > thanks
> >       fred
> >
> > Am Monday 20 August 2007 schrieben Sie:
> > > Hello Manfred,
> > >
> > > At http://www.spinics.net/lists/arm-kernel/msg42349.html you can find
> > > a patch that will probably work. Due to the lack of proper atomic
> > > instructions on the ARM-v4 core this patch is likely to be the best
> > > possible solution.
> > >
> > > Kind Regards,
> > >
> > > Remy
> >
> > -
> > To unsubscribe from this list: send the line "unsubscribe linux-rt-users"
> > in the body of a message to majordomo@vger.kernel.org
> > More majordomo info at  http://vger.kernel.org/majordomo-info.html
>

Re: PI mutex support on ARM

[Manfred Gruber]

hi Remy !

Am Wednesday 05 September 2007 schrieben Sie:
> Hello Manfred,
>
> > My question if I run the pi_stress, my watchdog triggers, if watchdog is
> > disabled i get this:
> > Is this the correct behaviour ? Or does it show a problem ?
>
> Depends on the priority of your watchdog-feeder thread. If it is not
> running in RT mode, with a priority higher than used in the pi-stress
> test, then yes it is normal that the watchdog kicks in. pi-stress
> takes 100% CPU-load, and leaves no room for non-RT processes.
>
> The output you get seems normal to me...

Ok, thanks.

The only difference between you patch and now 2.6.23-rc4-rt1 is that now a 
raw_ spinlock is used. So i think when using your patch on 2.6.21.5-rt20, 
because a customer has this kernel running, i have there also to use a 
raw_spinlock ?

thanks, 
regards manfred

Re: PI mutex support on ARM

[Remy Bohmer]

Hello Manfred,

> The only difference between you patch and now 2.6.23-rc4-rt1 is that now a
> raw_ spinlock is used. So i think when using your patch on 2.6.21.5-rt20,
> because a customer has this kernel running, i have there also to use a
> raw_spinlock ?

The same patch applies to older kernels. Besides, I use this patch for
a while now on 2.6.21 and 2.6.22, but with an interrupt lock instead
of a spinlock. A raw_spinlock is better because it is safe in SMP
also, so Ingo has the proper implementation in his patch, which you
should follow. (Probably this is technically the best possible
solution, given the limited amount of atomic-instructions on
ARM-v4/v5)
So, A normal (non-raw) spinlock should NOT be used here, because that
does would be converted to a rt-mutex, which is preemptible. If this
code is preemptible, it could be preempted by another user space
thread which could, in theory, modify the same piece of memory, and
thus causing a race condition.

Notice that there have been raised questions about the interrupt lock
while accessing user space memory in this code, it is considered as
not-safe.
AFAIK the only situation where it is not-safe, is the case where the
memory is not available in RAM, but e.g. somewhere in a swap space. If
the memory has to be paged in, probably interrupts are needed. In my
system things like this will never happen...

Maybe Ingo, Thomas or someone else can acknowledge (or trash) my opinion here?


Kind Regards,

Remy Bohmer

Re: PI mutex support on ARM

[Steven Rostedt]

--
On Wed, 5 Sep 2007, Remy Bohmer wrote:
> So, A normal (non-raw) spinlock should NOT be used here, because that
> does would be converted to a rt-mutex, which is preemptible. If this
> code is preemptible, it could be preempted by another user space
> thread which could, in theory, modify the same piece of memory, and
> thus causing a race condition.

Are you talking about this code?

+	spin_lock(&futex_atomic_lock);
+
+	__asm__ __volatile__( "@futex_atomic_cmpxchg_inatomic	\n"
+	"1:     ldrt    %0, [%3]				\n"
+	"       teq     %0, %1					\n"
+	"2:     streqt  %2, [%3]				\n"
+	"3:							\n"
+	"       .section __ex_table, \"a\"			\n"
+	"       .align 3					\n"
+	"       .long   1b, 4f, 2b, 4f				\n"
+	"       .previous					\n"
+	"       .section .fixup,\"ax\"				\n"
+	"4:     mov     %0, %4					\n"
+	"       b       3b					\n"
+	"       .previous"
+	: "=&r" (val)
+	: "r" (oldval), "r" (newval), "r" (uaddr), "Ir" (-EFAULT)
+	: "cc");
+
+	spin_unlock(&futex_atomic_lock);

I don't quite remember ARM (been a few years since working with it), but
this looks like the standard "load store-conditional", or is it simply a
read/test/write? (I don't have a ARM book handy at the moment).

But I would ask, what would touch that memory without first taking the
futex_atomic_lock? So I don't understand your issue of being preempted.

 >
> Notice that there have been raised questions about the interrupt lock
> while accessing user space memory in this code, it is considered as
> not-safe.
> AFAIK the only situation where it is not-safe, is the case where the
> memory is not available in RAM, but e.g. somewhere in a swap space. If
> the memory has to be paged in, probably interrupts are needed. In my
> system things like this will never happen...

That's nice, but other systems might have that happen ;-)

But mainly, yes, the area can be swapped out, _or_ it may not have been
allocated yet. Areas like the BSS section where variables are initialized
to zero may not have memory allocated to them until something actually
writes to it.

-- Steve

Re: PI mutex support on ARM

[Remy Bohmer]

Hello Steven,

Thanks for your explanation, here are my answers:

> > So, A normal (non-raw) spinlock should NOT be used here, because that
> > does would be converted to a rt-mutex, which is preemptible. If this
> > code is preemptible, it could be preempted by another user space
> > thread which could, in theory, modify the same piece of memory, and
> > thus causing a race condition.
>
> Are you talking about this code?

Yes!

>
> +       spin_lock(&futex_atomic_lock);
> +
> +       __asm__ __volatile__( "@futex_atomic_cmpxchg_inatomic   \n"
> +       "1:     ldrt    %0, [%3]                                \n"
> +       "       teq     %0, %1                                  \n"
> +       "2:     streqt  %2, [%3]                                \n"
> +       "3:                                                     \n"
> +       "       .section __ex_table, \"a\"                      \n"
> +       "       .align 3                                        \n"
> +       "       .long   1b, 4f, 2b, 4f                          \n"
> +       "       .previous                                       \n"
> +       "       .section .fixup,\"ax\"                          \n"
> +       "4:     mov     %0, %4                                  \n"
> +       "       b       3b                                      \n"
> +       "       .previous"
> +       : "=&r" (val)
> +       : "r" (oldval), "r" (newval), "r" (uaddr), "Ir" (-EFAULT)
> +       : "cc");
> +
> +       spin_unlock(&futex_atomic_lock);
>
> I don't quite remember ARM (been a few years since working with it), but
> this looks like the standard "load store-conditional", or is it simply a
> read/test/write? (I don't have a ARM book handy at the moment).

it is a read/test/write, or in other words a cmpxchg().

>
> But I would ask, what would touch that memory without first taking the
> futex_atomic_lock? So I don't understand your issue of being preempted.

AFAIK, it is user space memory, allocated in the context of a user
space process.
If this memory location is modified outside this 'protected' section,
like for example in some codepath in glibc also (e.g. futex slowpath
implementation), then this implementation could be dangerous with a
normal spinlock/rt-mutex.

>  >
> > Notice that there have been raised questions about the interrupt lock
> > while accessing user space memory in this code, it is considered as
> > not-safe.
> > AFAIK the only situation where it is not-safe, is the case where the
> > memory is not available in RAM, but e.g. somewhere in a swap space. If
> > the memory has to be paged in, probably interrupts are needed. In my
> > system things like this will never happen...
>
> That's nice, but other systems might have that happen ;-)

And that is exactly the reason, why I have questions with this implementation...


Kind Regards,

Remy