Date: Tue, 11 Oct 2011 11:42:08 -0600 (MDT) From: Ian Lepore <freebsd@damnhippie.dyndns.org> To: FreeBSD-gnats-submit@FreeBSD.org Subject: arm/161498: [patch] ARM RAS code can fail to restart an atomic sequence. Message-ID: <201110111742.p9BHg8kJ070893@revolution.hippie.lan> Resent-Message-ID: <201110111750.p9BHo2Ra074403@freefall.freebsd.org>
next in thread | raw e-mail | index | archive | help
>Number: 161498
>Category: arm
>Synopsis: [patch] ARM RAS code can fail to restart an atomic sequence.
>Confidential: no
>Severity: critical
>Priority: high
>Responsible: freebsd-arm
>State: open
>Quarter:
>Keywords:
>Date-Required:
>Class: sw-bug
>Submitter-Id: current-users
>Arrival-Date: Tue Oct 11 17:50:02 UTC 2011
>Closed-Date:
>Last-Modified:
>Originator: Ian Lepore <freebsd@damnhippie.dyndns.org>
>Release: FreeBSD 8.2-STABLE arm
>Organization:
Symmetricom, Inc.
>Environment:
FreeBSD tflex 8.2-STABLE FreeBSD 8.2-STABLE #29: Tue Oct 11 13:32:35 UTC 2011 root@revolution.hippie.lan:/usr/obj/arm/usr/src/sys/TFLEX arm
>Description:
The RAS implementation for ARM can occasionally fail to restart a sequence
after being interrupted, leading to a failure of atomic operations which
manifests in ways such as granting the same pthread mutex to multiple threads
concurrently.
The "normal" RAS sequence goes like this:
On entry, RAS_START = 0x00000000, RAS_END = 0xffffffff
1: Set RAS_START to address of Step 1
2: Set RAS_END to address of Step 4
3: Do the atomic operation
4: Set RAS_START to 0x00000000
5: Set RAS_END to 0xffffffff
While the normal entry condition is for RAS_START/END to be 0x0/0xffffffff
the code in PUSHFRAMEINSVC does not reliably enforce this (it sometimes
leaves a stale value in RAS_END), which is the source of one of the two bugs
in the current implementation. The other bug is that the PUSHFRAMEINSVC
code compares the PC to RAS_END using signed-value logic, but proper
operation of the RAS sequence requires that 0xffffffff be interpreted as the
highest possible memory address, not -1.
The first bug happens with interaction between a pair of threads doing RAS
sequences at the same time. Thread 1 runs through step 4 of the sequence
and gets interrupted before completing step 5. The PUSHFRAMEINSVC code
sees a zero in RAS_START and does nothing; notably it does not change the
value in RAS_END because START was zero. Thread 2 begins to run and gets
interrupted between steps 1 and 2. Now PUSHFRAMEINSVC sees a non-zero
RAS_START, and the RAS_END value is whatever thread 1 left there when it
got interrupted. The behavior now depends on whether the RAS sequence in
thread 2 is at a higher or lower memory address than the one in thread 1.
In one case it accidentally works right, in the other case an interrupt
between steps 1 and 2 wouldn't lead to a proper restart because the PC is
not between RAS_START and RAS_END. But because RAS_START was non-zero
when thread 2 got interrupted, RAS_START/END get reset, so when thread 2
gets resumed at step 2 it never reloads RAS_START, and another interrrupt
in the sequence leads to misbehavior.
The second bug (signed value logic) is conceptually simpler, here is a
sequence that triggers that bug:
On entry, RAS_START/END are 0x0/0xffffffff. A thread enters a RAS
sequence and completes step 1, then gets interrupted before completing
step 2. The PUSHFRAMEINSVC code sees a non-zero RAS_START so it compares
the PC to RAS_END. Because of the signed-value logic, the PC will never be
between RAS_START and -1, so the PUSHFRAMEINSVC code doesn't set up for a
restart at the RAS_START location. When the thread eventually resumes at
step 2, RAS_START will be zero, and if it gets interrupted again before
the end of the atomic operation it would not get restarted.
The attached patch addresses these two conditions as follows:
Now the PUSHFRAMEINSVC macro always resets RAS_START to zero if it has a non-
zero value, and always sets RAS_END to 0xffffffff if it has a different value.
This differs from the original in that the value of RAS_START isn't used to
decide whether to reset RAS_END. The two decisions are made independently,
which allows them to reliably enforce the entry-condition for the next thread
regardless of where in the RAS sequence the current thread was interrupted.
The macro now uses conditional execution based on an unsigned compare of the
PC against RAS_END to decide whether to set up for a restart (strhi rather
than strgt instruction). In the case where RAS_START has been set and
RAS_END is still at 0xffffffff, this will result in setting up for a restart
at the beginning of the sequence so that an interrupt on the second time
through will still result in atomic behavior (I.E. yet another restart for a
3rd attempt at the atomic op).
Note that there is some typical ARM conditional-execution trickiness in the
new logic: the strhi instruction that changes the saved PC to the RAS_START
address will execute only if the carry flag is set and the zero flag is not.
If the RAS_START value is zero then the compare with the RAS_END address is
skipped and the zero flag is still set from the RAS_START compare, causing
the strhi to get skipped based soley on the RAS_START value, regardless of
the carry flag. If RAS_START is non-zero then the RAS_END compare happens and
the strhi executes based on the zero/carry status of the RAS_END compare.
Note also that the patched code assumes that if RAS_START is non-zero, the
userland PC in PUSHFRAMEINSVC must be greater than RAS_START. This is
implicit in the definition of RAS, which prohibits function calls during a
RAS sequence. This allows the code to avoid a specific check for the PC
being greater than RAS_START if RAS_START is non-zero, and explains why the
series of instructions that used to be conditional on 'gt' are now 'ne'.
Thanks go to Symmetricom, Inc, for sponsoring this work, and to my
collegue there, Lars Boehnke, for crafting test code to demonstrate the
original problem and prove the fix works.
>How-To-Repeat:
The following small program will demonstrate the problem using the
atomic_cmpset_int() function. The failure will be provoked most quickly
in the presence of lots of interrupts, so running with a kernel that has
HZ set unreasonably high will help demonstrate the problem.
--- atomictest.c begins here ---
/*
* atomictest.c - Demonstrate non-atomicity of ARM RAS code.
*
* Build using: make LDFLAGS=-pthread atomictest
*
* Run in an environment with lots of interrupts going on (HZ=4096 does
* the trick nicely for me). On a 180mhz rm9200 with HZ=100 it takes
* hours-to-months to see a failure; with HZ=4096 it takes minutes.
*/
#include <pthread.h>
#include <signal.h>
#include <stdio.h>
#include <time.h>
#include <unistd.h>
#include <machine/atomic.h>
static int sStopThreads = 0;
static const int sNumThreads = 3;
static unsigned int sAtomicLock = 0;
// The implementation is defined in a macro because the RAS sections need to
// be at different addresses to demonstrate the problem.
// CMPSET test -
// If a thread is able to "lock" sAtomicLock, it should be able to "release"
// it. Failure to release indicates multiple threads were able to change the
// value of sAtomicLock at the same time.
#define THREAD_IMP(thrIdx) \
unsigned int locked, released; \
\
while (! sStopThreads) \
{ \
locked = atomic_cmpset_int(&sAtomicLock, 0, (thrIdx+1)); \
released = atomic_cmpset_int(&sAtomicLock, (thrIdx+1), 0); \
if (locked != released) \
{ \
printf("*** ERROR: locked=%u, released=%u\n", locked, released); \
sStopThreads = 1; \
break; \
} \
} \
\
return NULL; \
void* ThreadFunc1(void* varg)
{
THREAD_IMP(0);
}
void* ThreadFunc2(void* varg)
{
THREAD_IMP(1);
}
void* ThreadFunc3(void* varg)
{
THREAD_IMP(2);
}
void SigHandler(int sig)
{
if (sig == SIGINT)
sStopThreads = 1;
return;
}
int main(int argc, const char* argv[])
{
pthread_t threads[sNumThreads];
size_t idx;
time_t start = time(NULL);
signal(SIGINT, SigHandler);
pthread_create(&threads[0], NULL, ThreadFunc1, NULL);
pthread_create(&threads[1], NULL, ThreadFunc2, NULL);
pthread_create(&threads[2], NULL, ThreadFunc3, NULL);
while (! sStopThreads)
sleep(1);
// make sure all threads have stopped
for (idx = 0; idx < sNumThreads; idx ++)
pthread_join(threads[idx], NULL);
printf("Elapsed %lld seconds\n", (int64_t)(time(NULL)-start));
return 0;
}
--- atomictest.c ends here ---
>Fix:
The following patch fixes the problems described above. The changes to
sysarch.h are just updates to the comments to help future maintainers.
These diffs were developed for freebsd 8.x but apply cleanly to -current.
These changes have been extensively tested at Symmetricom; we are currently
deploying products that include these fixes.
--- ras-current.diff begins here ---
Index: sys/arm/include/asmacros.h
===================================================================
RCS file: /local/base/FreeBSD-CVS/src/sys/arm/include/asmacros.h,v
retrieving revision 1.8
diff -u -p -r1.8 asmacros.h
--- sys/arm/include/asmacros.h 5 Feb 2008 10:22:33 -0000 1.8
+++ sys/arm/include/asmacros.h 11 Oct 2011 17:02:52 -0000
@@ -71,9 +71,8 @@
ldr r0, =ARM_RAS_START; \
mov r1, #0; \
str r1, [r0]; \
- ldr r0, =ARM_RAS_END; \
mov r1, #0xffffffff; \
- str r1, [r0];
+ str r1, [r0, #4];
/*
* PULLFRAME - macro to pull a trap frame from the stack in the current mode
@@ -118,23 +117,22 @@
stmia sp, {r0-r12}; /* Push the user mode registers */ \
add r0, sp, #(4*13); /* Adjust the stack pointer */ \
stmia r0, {r13-r14}^; /* Push the user mode registers */ \
- mov r0, r0; /* NOP for previous instruction */ \
- ldr r5, =ARM_RAS_START; /* Check if there's any RAS */ \
- ldr r3, [r5]; \
- cmp r3, #0; /* Is the update needed ? */ \
- ldrgt lr, [r0, #16]; \
- ldrgt r1, =ARM_RAS_END; \
- ldrgt r4, [r1]; /* Get the end of the RAS */ \
- movgt r2, #0; /* Reset the magic addresses */ \
- strgt r2, [r5]; \
- movgt r2, #0xffffffff; \
- strgt r2, [r1]; \
- cmpgt lr, r3; /* Were we in the RAS ? */ \
- cmpgt r4, lr; \
- strgt r3, [r0, #16]; /* Yes, update the pc */ \
- mrs r0, spsr_all; /* Put the SPSR on the stack */ \
- str r0, [sp, #-4]!
-
+ mov r0, r0; /* NOP for previous instruction */ \
+ ldr r5, =ARM_RAS_START; /* Retrieve global RAS_END and */ \
+ ldr r4, [r5, #4]; /* reset it to point at the */ \
+ cmp r4, #0xffffffff; /* end of memory if necessary; */ \
+ movne r1, #0xffffffff; /* leave value in r4 for later */ \
+ strne r1, [r5, #4]; /* comparision against PC. */ \
+ ldr r3, [r5]; /* Retrieve global RAS_START */ \
+ cmp r3, #0; /* and reset it if non-zero. */ \
+ movne r1, #0; /* If non-zero RAS_START and */ \
+ strne r1, [r5]; /* PC was lower than RAS_END, */ \
+ ldrne r1, [r0, #16]; /* adjust the saved PC so that */ \
+ cmpne r4, r1; /* execution later resumes at */ \
+ strhi r3, [r0, #16]; /* the RAS_START location. */ \
+ mrs r0, spsr_all; \
+ str r0, [sp, #-4]!
+
/*
* PULLFRAMEFROMSVCANDEXIT - macro to pull a trap frame from the stack
* in SVC32 mode and restore the saved processor mode and PC.
Index: sys/arm/include/sysarch.h
=================================================================== RCS file:
/local/base/FreeBSD-CVS/src/sys/arm/include/sysarch.h,v retrieving revision 1.6
diff -u -p -r1.6 sysarch.h
--- sys/arm/include/sysarch.h 12 Feb 2009 23:23:30 -0000 1.6
+++ sys/arm/include/sysarch.h 11 Oct 2011 17:02:56 -0000
@@ -42,9 +42,13 @@
* The ARM_TP_ADDRESS points to a special purpose page, which is used as local
* store for the ARM per-thread data and Restartable Atomic Sequences support.
* Put it just above the "high" vectors' page.
- * the cpu_switch() code assumes ARM_RAS_START is ARM_TP_ADDRESS + 4, and
+ * The cpu_switch() code assumes ARM_RAS_START is ARM_TP_ADDRESS + 4, and
* ARM_RAS_END is ARM_TP_ADDRESS + 8, so if that ever changes, be sure to
* update the cpu_switch() (and cpu_throw()) code as well.
+ * In addition, code in arm/include/atomic.h and arm/include/asmacros.h
+ * assumes that ARM_RAS_END is at ARM_RAS_START+4, so be sure to update those
+ * if ARM_RAS_END moves in relation to ARM_RAS_START (look for occurrances
+ * of ldr/str rm,[rn, #4]).
*/
#define ARM_TP_ADDRESS (ARM_VECTORS_HIGH + 0x1000)
#define ARM_RAS_START (ARM_TP_ADDRESS + 4)
--- ras-current.diff ends here ---
>Release-Note:
>Audit-Trail:
>Unformatted:
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201110111742.p9BHg8kJ070893>