ARM SWP/SWPB emulation support

ARM SWP/SWPB emulation support

[Stepan Moskovchenko]

Hello

I have two questions regarding the following patch:

commit 64d2dc384e41e2b7acead6804593ddaaf8aad8e1
Author: Leif Lindholm<leif.lindholm@arm.com>
Date:   Thu Sep 16 18:00:47 2010 +0100
ARM: 6396/1: Add SWP/SWPB emulation for ARMv7 processors

First, the Kconfig text for the patch says the following:

  "In some older versions of glibc [<=2.8] SWP is used during futex
   trylock() operations with the assumption that the code will not
   be preempted. This invalid assumption may be more likely to fail
   with SWP emulation enabled, leading to deadlock of the user
   application."

I see that the SWP emulation is done using LDREX / STREX instructions, so it
looks like the SWP emulation should happen in an atomic manner with respect to
loading the previous value at the address being swapped with, and storing the
new value. Does this text simply imply that the old glibc implementation of
futex trylock() is incorrect in the specific way it uses SWP instructions, or
does it mean that there is a specific atomicity problem within the SWP emulation
code itself?

Second, I noticed that the SWP emulation code does not look@the condition
code for the SWP instruction being emulated. From my understanding of the ARM
architecture, the CPU may raise an undefined instruction exception regardless
of the condition code that may appear in the relevant bits of the underfined
instruction. Thus, with the SWP emulation code as-is, it is possible that a
conditional SWP/SWPB instruction may raise an undefined instruction exception
(and thus trigger the swp emulation code to run) even though the condition for
that instruction may not have been met in CPSR. As a result, conditional SWP
instructions may be emulated as if they had not been conditional. I have a patch
to add condition code checking to the SWP emulation code and if this seems right
to you, I could send it out. What do you think?

Thanks
Steve

Sent by an employee of the Qualcomm Innovation Center, Inc.
The Qualcomm Innovation Center, Inc. is a member of the Code Aurora Forum.

ARM SWP/SWPB emulation support

[Catalin Marinas]

On 18 November 2011 23:21, Stepan Moskovchenko <stepanm@codeaurora.org> wrote:
> I have two questions regarding the following patch:
>
> commit 64d2dc384e41e2b7acead6804593ddaaf8aad8e1
> Author: Leif Lindholm<leif.lindholm@arm.com>
> Date: ? Thu Sep 16 18:00:47 2010 +0100
> ARM: 6396/1: Add SWP/SWPB emulation for ARMv7 processors
>
> First, the Kconfig text for the patch says the following:
>
> ?"In some older versions of glibc [<=2.8] SWP is used during futex
> ?trylock() operations with the assumption that the code will not
> ?be preempted. This invalid assumption may be more likely to fail
> ?with SWP emulation enabled, leading to deadlock of the user
> ?application."
>
> I see that the SWP emulation is done using LDREX / STREX instructions, so it
> looks like the SWP emulation should happen in an atomic manner with respect
> to
> loading the previous value at the address being swapped with, and storing
> the
> new value. Does this text simply imply that the old glibc implementation of
> futex trylock() is incorrect in the specific way it uses SWP instructions,
> or
> does it mean that there is a specific atomicity problem within the SWP
> emulation
> code itself?

The old glibc code assumes that a code sequence that includes SWP is
atomic, not that the SWP instruction itself is atomic. It works as
long as there is no interrupt during that sequence. With the SWP
emulation, the SWP instruction traps into the kernel and the atomicity
is automatically broken (Linux may reschedule a different task). The
SWP emulation in the kernel provides an atomic implementation of SWP
using LDREX/STREX (though only in relation to other CPUs in the inner
shareable domain, it doesn't do bus locking to be used with devices).

> Second, I noticed that the SWP emulation code does not look at the condition
> code for the SWP instruction being emulated.

Leif is just looking at this and should post a patch probably next
week (it was already spotted by someone else).

-- 
Catalin

[PATCH] arm: Add condition code check to SWP emulator

[Stepan Moskovchenko]

When emulating a SWP/SWPB instruction, check the condition
code of the instruction and compare it against CPSR status
bits rather than relying on the architecture to only raise
an undefined instruction exception if the condition checks
are passing.

Signed-off-by: Stepan Moskovchenko <stepanm@codeaurora.org>
---
Hello

I already had a version prepared, so here it is.

Steve

 arch/arm/kernel/swp_emulate.c |   57 +++++++++++++++++++++++++++++++++++++++++
 1 files changed, 57 insertions(+), 0 deletions(-)

diff --git a/arch/arm/kernel/swp_emulate.c b/arch/arm/kernel/swp_emulate.c
index 40ee7e5..7669848 100644
--- a/arch/arm/kernel/swp_emulate.c
+++ b/arch/arm/kernel/swp_emulate.c
@@ -173,6 +173,57 @@ static int emulate_swpX(unsigned int address, unsigned int *data,
 	return res;
 }
 
+static int check_condition(struct pt_regs *regs, unsigned int insn)
+{
+	unsigned int base_cond, neg, cond = 0;
+	unsigned int cpsr_z, cpsr_c, cpsr_n, cpsr_v;
+
+	cpsr_n = (regs->ARM_cpsr & PSR_N_BIT) ? 1 : 0;
+	cpsr_z = (regs->ARM_cpsr & PSR_Z_BIT) ? 1 : 0;
+	cpsr_c = (regs->ARM_cpsr & PSR_C_BIT) ? 1 : 0;
+	cpsr_v = (regs->ARM_cpsr & PSR_V_BIT) ? 1 : 0;
+
+	/* Upper 3 bits indicate condition, lower bit incicates negation */
+	base_cond = insn >> 29;
+	neg = insn & BIT(28) ? 1 : 0;
+
+	switch (base_cond) {
+	case 0x0:	/* equal */
+		cond = cpsr_z;
+		break;
+
+	case 0x1:	/* carry set */
+		cond = cpsr_c;
+		break;
+
+	case 0x2:	/* minus / negative */
+		cond = cpsr_n;
+		break;
+
+	case 0x3:	/* overflow */
+		cond = cpsr_v;
+		break;
+
+	case 0x4:	/* unsigned higher */
+		cond = (cpsr_c == 1) && (cpsr_z == 0);
+		break;
+
+	case 0x5:	/* signed greater / equal */
+		cond = (cpsr_n == cpsr_v);
+		break;
+
+	case 0x6:	/* signed greater */
+		cond = (cpsr_z == 0) && (cpsr_n == cpsr_v);
+		break;
+
+	case 0x7:	/* always */
+		cond = 1;
+		break;
+	};
+
+	return cond && !neg;
+}
+
 /*
  * swp_handler logs the id of calling process, dissects the instruction, sanity
  * checks the memory location, calls emulate_swpX for the actual operation and
@@ -191,6 +242,12 @@ static int swp_handler(struct pt_regs *regs, unsigned int instr)
 		previous_pid = current->pid;
 	}
 
+	/* Ignore the instruction if it fails its condition code check */
+	if (!check_condition(regs, instr)) {
+		regs->ARM_pc += 4;
+		return 0;
+	}
+
 	address = regs->uregs[EXTRACT_REG_NUM(instr, RN_OFFSET)];
 	data	= regs->uregs[EXTRACT_REG_NUM(instr, RT2_OFFSET)];
 	destreg = EXTRACT_REG_NUM(instr, RT_OFFSET);
-- 
Sent by an employee of the Qualcomm Innovation Center, Inc.
The Qualcomm Innovation Center, Inc. is a member of the Code Aurora Forum.

[PATCH] arm: Add condition code check to SWP emulator

[Stepan Moskovchenko]

When emulating a SWP/SWPB instruction, check the condition
code of the instruction and compare it against CPSR status
bits rather than relying on the architecture to only raise
an undefined instruction exception if the condition checks
are passing.

Signed-off-by: Stepan Moskovchenko <stepanm@codeaurora.org>
---
Hello

I already had a version prepared, so here it is.

Steve

 arch/arm/kernel/swp_emulate.c |   57 +++++++++++++++++++++++++++++++++++++++++
 1 files changed, 57 insertions(+), 0 deletions(-)

diff --git a/arch/arm/kernel/swp_emulate.c b/arch/arm/kernel/swp_emulate.c
index 40ee7e5..7669848 100644
--- a/arch/arm/kernel/swp_emulate.c
+++ b/arch/arm/kernel/swp_emulate.c
@@ -173,6 +173,57 @@ static int emulate_swpX(unsigned int address, unsigned int *data,
 	return res;
 }
 
+static int check_condition(struct pt_regs *regs, unsigned int insn)
+{
+	unsigned int base_cond, neg, cond = 0;
+	unsigned int cpsr_z, cpsr_c, cpsr_n, cpsr_v;
+
+	cpsr_n = (regs->ARM_cpsr & PSR_N_BIT) ? 1 : 0;
+	cpsr_z = (regs->ARM_cpsr & PSR_Z_BIT) ? 1 : 0;
+	cpsr_c = (regs->ARM_cpsr & PSR_C_BIT) ? 1 : 0;
+	cpsr_v = (regs->ARM_cpsr & PSR_V_BIT) ? 1 : 0;
+
+	/* Upper 3 bits indicate condition, lower bit incicates negation */
+	base_cond = insn >> 29;
+	neg = insn & BIT(28) ? 1 : 0;
+
+	switch (base_cond) {
+	case 0x0:	/* equal */
+		cond = cpsr_z;
+		break;
+
+	case 0x1:	/* carry set */
+		cond = cpsr_c;
+		break;
+
+	case 0x2:	/* minus / negative */
+		cond = cpsr_n;
+		break;
+
+	case 0x3:	/* overflow */
+		cond = cpsr_v;
+		break;
+
+	case 0x4:	/* unsigned higher */
+		cond = (cpsr_c == 1) && (cpsr_z == 0);
+		break;
+
+	case 0x5:	/* signed greater / equal */
+		cond = (cpsr_n == cpsr_v);
+		break;
+
+	case 0x6:	/* signed greater */
+		cond = (cpsr_z == 0) && (cpsr_n == cpsr_v);
+		break;
+
+	case 0x7:	/* always */
+		cond = 1;
+		break;
+	};
+
+	return cond && !neg;
+}
+
 /*
  * swp_handler logs the id of calling process, dissects the instruction, sanity
  * checks the memory location, calls emulate_swpX for the actual operation and
@@ -191,6 +242,12 @@ static int swp_handler(struct pt_regs *regs, unsigned int instr)
 		previous_pid = current->pid;
 	}
 
+	/* Ignore the instruction if it fails its condition code check */
+	if (!check_condition(regs, instr)) {
+		regs->ARM_pc += 4;
+		return 0;
+	}
+
 	address = regs->uregs[EXTRACT_REG_NUM(instr, RN_OFFSET)];
 	data	= regs->uregs[EXTRACT_REG_NUM(instr, RT2_OFFSET)];
 	destreg = EXTRACT_REG_NUM(instr, RT_OFFSET);
-- 
Sent by an employee of the Qualcomm Innovation Center, Inc.
The Qualcomm Innovation Center, Inc. is a member of the Code Aurora Forum.

[PATCH] arm: Add condition code check to SWP emulator

[Russell King - ARM Linux]

On Sat, Nov 19, 2011 at 05:04:30PM -0800, Stepan Moskovchenko wrote:
> +static int check_condition(struct pt_regs *regs, unsigned int insn)
> +{
> +	unsigned int base_cond, neg, cond = 0;
> +	unsigned int cpsr_z, cpsr_c, cpsr_n, cpsr_v;
> +
> +	cpsr_n = (regs->ARM_cpsr & PSR_N_BIT) ? 1 : 0;
> +	cpsr_z = (regs->ARM_cpsr & PSR_Z_BIT) ? 1 : 0;
> +	cpsr_c = (regs->ARM_cpsr & PSR_C_BIT) ? 1 : 0;
> +	cpsr_v = (regs->ARM_cpsr & PSR_V_BIT) ? 1 : 0;
> +
> +	/* Upper 3 bits indicate condition, lower bit incicates negation */
> +	base_cond = insn >> 29;
> +	neg = insn & BIT(28) ? 1 : 0;
> +
> +	switch (base_cond) {
> +	case 0x0:	/* equal */
> +		cond = cpsr_z;
> +		break;
> +
> +	case 0x1:	/* carry set */
> +		cond = cpsr_c;
> +		break;
> +
> +	case 0x2:	/* minus / negative */
> +		cond = cpsr_n;
> +		break;
> +
> +	case 0x3:	/* overflow */
> +		cond = cpsr_v;
> +		break;
> +
> +	case 0x4:	/* unsigned higher */
> +		cond = (cpsr_c == 1) && (cpsr_z == 0);
> +		break;
> +
> +	case 0x5:	/* signed greater / equal */
> +		cond = (cpsr_n == cpsr_v);
> +		break;
> +
> +	case 0x6:	/* signed greater */
> +		cond = (cpsr_z == 0) && (cpsr_n == cpsr_v);
> +		break;
> +
> +	case 0x7:	/* always */
> +		cond = 1;
> +		break;
> +	};
> +
> +	return cond && !neg;

There's a much better algorithm to check this.  See the bottom of
arch/arm/nwfpe/fpopcode.c.

It would probably be best for there to be a common function for doing
this kind of check, rather than having several implementations of it
scattered around the kernel.

Re: [PATCH] arm: Add condition code check to SWP emulator

[Russell King - ARM Linux]

On Sat, Nov 19, 2011 at 05:04:30PM -0800, Stepan Moskovchenko wrote:
> +static int check_condition(struct pt_regs *regs, unsigned int insn)
> +{
> +	unsigned int base_cond, neg, cond = 0;
> +	unsigned int cpsr_z, cpsr_c, cpsr_n, cpsr_v;
> +
> +	cpsr_n = (regs->ARM_cpsr & PSR_N_BIT) ? 1 : 0;
> +	cpsr_z = (regs->ARM_cpsr & PSR_Z_BIT) ? 1 : 0;
> +	cpsr_c = (regs->ARM_cpsr & PSR_C_BIT) ? 1 : 0;
> +	cpsr_v = (regs->ARM_cpsr & PSR_V_BIT) ? 1 : 0;
> +
> +	/* Upper 3 bits indicate condition, lower bit incicates negation */
> +	base_cond = insn >> 29;
> +	neg = insn & BIT(28) ? 1 : 0;
> +
> +	switch (base_cond) {
> +	case 0x0:	/* equal */
> +		cond = cpsr_z;
> +		break;
> +
> +	case 0x1:	/* carry set */
> +		cond = cpsr_c;
> +		break;
> +
> +	case 0x2:	/* minus / negative */
> +		cond = cpsr_n;
> +		break;
> +
> +	case 0x3:	/* overflow */
> +		cond = cpsr_v;
> +		break;
> +
> +	case 0x4:	/* unsigned higher */
> +		cond = (cpsr_c == 1) && (cpsr_z == 0);
> +		break;
> +
> +	case 0x5:	/* signed greater / equal */
> +		cond = (cpsr_n == cpsr_v);
> +		break;
> +
> +	case 0x6:	/* signed greater */
> +		cond = (cpsr_z == 0) && (cpsr_n == cpsr_v);
> +		break;
> +
> +	case 0x7:	/* always */
> +		cond = 1;
> +		break;
> +	};
> +
> +	return cond && !neg;

There's a much better algorithm to check this.  See the bottom of
arch/arm/nwfpe/fpopcode.c.

It would probably be best for there to be a common function for doing
this kind of check, rather than having several implementations of it
scattered around the kernel.

[PATCH] arm: Add condition code check to SWP emulator

[Catalin Marinas]

On 20 November 2011 08:41, Russell King - ARM Linux
<linux@arm.linux.org.uk> wrote:
> On Sat, Nov 19, 2011 at 05:04:30PM -0800, Stepan Moskovchenko wrote:
>> +static int check_condition(struct pt_regs *regs, unsigned int insn)
>> +{
>> + ? ? unsigned int base_cond, neg, cond = 0;
>> + ? ? unsigned int cpsr_z, cpsr_c, cpsr_n, cpsr_v;
>> +
>> + ? ? cpsr_n = (regs->ARM_cpsr & PSR_N_BIT) ? 1 : 0;
>> + ? ? cpsr_z = (regs->ARM_cpsr & PSR_Z_BIT) ? 1 : 0;
>> + ? ? cpsr_c = (regs->ARM_cpsr & PSR_C_BIT) ? 1 : 0;
>> + ? ? cpsr_v = (regs->ARM_cpsr & PSR_V_BIT) ? 1 : 0;
>> +
>> + ? ? /* Upper 3 bits indicate condition, lower bit incicates negation */
>> + ? ? base_cond = insn >> 29;
>> + ? ? neg = insn & BIT(28) ? 1 : 0;
>> +
>> + ? ? switch (base_cond) {
>> + ? ? case 0x0: ? ? ? /* equal */
>> + ? ? ? ? ? ? cond = cpsr_z;
>> + ? ? ? ? ? ? break;
>> +
>> + ? ? case 0x1: ? ? ? /* carry set */
>> + ? ? ? ? ? ? cond = cpsr_c;
>> + ? ? ? ? ? ? break;
>> +
>> + ? ? case 0x2: ? ? ? /* minus / negative */
>> + ? ? ? ? ? ? cond = cpsr_n;
>> + ? ? ? ? ? ? break;
>> +
>> + ? ? case 0x3: ? ? ? /* overflow */
>> + ? ? ? ? ? ? cond = cpsr_v;
>> + ? ? ? ? ? ? break;
>> +
>> + ? ? case 0x4: ? ? ? /* unsigned higher */
>> + ? ? ? ? ? ? cond = (cpsr_c == 1) && (cpsr_z == 0);
>> + ? ? ? ? ? ? break;
>> +
>> + ? ? case 0x5: ? ? ? /* signed greater / equal */
>> + ? ? ? ? ? ? cond = (cpsr_n == cpsr_v);
>> + ? ? ? ? ? ? break;
>> +
>> + ? ? case 0x6: ? ? ? /* signed greater */
>> + ? ? ? ? ? ? cond = (cpsr_z == 0) && (cpsr_n == cpsr_v);
>> + ? ? ? ? ? ? break;
>> +
>> + ? ? case 0x7: ? ? ? /* always */
>> + ? ? ? ? ? ? cond = 1;
>> + ? ? ? ? ? ? break;
>> + ? ? };
>> +
>> + ? ? return cond && !neg;
>
> There's a much better algorithm to check this. ?See the bottom of
> arch/arm/nwfpe/fpopcode.c.
>
> It would probably be best for there to be a common function for doing
> this kind of check, rather than having several implementations of it
> scattered around the kernel.

That's what Leif started doing.

-- 
Catalin

Re: [PATCH] arm: Add condition code check to SWP emulator

[Catalin Marinas]

On 20 November 2011 08:41, Russell King - ARM Linux
<linux@arm.linux.org.uk> wrote:
> On Sat, Nov 19, 2011 at 05:04:30PM -0800, Stepan Moskovchenko wrote:
>> +static int check_condition(struct pt_regs *regs, unsigned int insn)
>> +{
>> +     unsigned int base_cond, neg, cond = 0;
>> +     unsigned int cpsr_z, cpsr_c, cpsr_n, cpsr_v;
>> +
>> +     cpsr_n = (regs->ARM_cpsr & PSR_N_BIT) ? 1 : 0;
>> +     cpsr_z = (regs->ARM_cpsr & PSR_Z_BIT) ? 1 : 0;
>> +     cpsr_c = (regs->ARM_cpsr & PSR_C_BIT) ? 1 : 0;
>> +     cpsr_v = (regs->ARM_cpsr & PSR_V_BIT) ? 1 : 0;
>> +
>> +     /* Upper 3 bits indicate condition, lower bit incicates negation */
>> +     base_cond = insn >> 29;
>> +     neg = insn & BIT(28) ? 1 : 0;
>> +
>> +     switch (base_cond) {
>> +     case 0x0:       /* equal */
>> +             cond = cpsr_z;
>> +             break;
>> +
>> +     case 0x1:       /* carry set */
>> +             cond = cpsr_c;
>> +             break;
>> +
>> +     case 0x2:       /* minus / negative */
>> +             cond = cpsr_n;
>> +             break;
>> +
>> +     case 0x3:       /* overflow */
>> +             cond = cpsr_v;
>> +             break;
>> +
>> +     case 0x4:       /* unsigned higher */
>> +             cond = (cpsr_c == 1) && (cpsr_z == 0);
>> +             break;
>> +
>> +     case 0x5:       /* signed greater / equal */
>> +             cond = (cpsr_n == cpsr_v);
>> +             break;
>> +
>> +     case 0x6:       /* signed greater */
>> +             cond = (cpsr_z == 0) && (cpsr_n == cpsr_v);
>> +             break;
>> +
>> +     case 0x7:       /* always */
>> +             cond = 1;
>> +             break;
>> +     };
>> +
>> +     return cond && !neg;
>
> There's a much better algorithm to check this.  See the bottom of
> arch/arm/nwfpe/fpopcode.c.
>
> It would probably be best for there to be a common function for doing
> this kind of check, rather than having several implementations of it
> scattered around the kernel.

That's what Leif started doing.

-- 
Catalin

[PATCH] arm: Add condition code check to SWP emulator

[Leif Lindholm]

Stepan, thank you for spotting this.

On 11/20/11 10:55, Catalin Marinas wrote:
> On 20 November 2011 08:41, Russell King - ARM Linux
> <linux@arm.linux.org.uk>  wrote:
>> There's a much better algorithm to check this.  See the bottom of
>> arch/arm/nwfpe/fpopcode.c.
>>
>> It would probably be best for there to be a common function for doing
>> this kind of check, rather than having several implementations of it
>> scattered around the kernel.
>
> That's what Leif started doing.

Yes, I put together an RFC patch set based on that.
But rather than duplicating code, I was looking to break it out for 
generic use. And then it was pointed out to me that we also have an 
additional implementation in kernel/kprobes-test.c (test_check_cc()).

I forgot to add the cover message on the set I just submitted to the 
linux-arm-kernel list, but it was meant to say:
---
There are several locations in the kernel where software needs to
inspect the condition codes of trapped instructions. The original
bitmask implementation in the nwfpe code does this in an efficient
manner. This series breaks this code out of nwfpe/fpopcode.{ch} into
a standalone file for opcode operations, and contains additional
patches to kprobes and SWP eumlation to use this interface.
---

/
     Leif

Re: [PATCH] arm: Add condition code check to SWP emulator

[Leif Lindholm]

Stepan, thank you for spotting this.

On 11/20/11 10:55, Catalin Marinas wrote:
> On 20 November 2011 08:41, Russell King - ARM Linux
> <linux@arm.linux.org.uk>  wrote:
>> There's a much better algorithm to check this.  See the bottom of
>> arch/arm/nwfpe/fpopcode.c.
>>
>> It would probably be best for there to be a common function for doing
>> this kind of check, rather than having several implementations of it
>> scattered around the kernel.
>
> That's what Leif started doing.

Yes, I put together an RFC patch set based on that.
But rather than duplicating code, I was looking to break it out for 
generic use. And then it was pointed out to me that we also have an 
additional implementation in kernel/kprobes-test.c (test_check_cc()).

I forgot to add the cover message on the set I just submitted to the 
linux-arm-kernel list, but it was meant to say:
---
There are several locations in the kernel where software needs to
inspect the condition codes of trapped instructions. The original
bitmask implementation in the nwfpe code does this in an efficient
manner. This series breaks this code out of nwfpe/fpopcode.{ch} into
a standalone file for opcode operations, and contains additional
patches to kprobes and SWP eumlation to use this interface.
---

/
     Leif