Skip to contentSkip to conversation

LDREX/STREX and pre-emption on *non*-SMP hardware

DISCUSSION Jamie Lokier 2 participants 3 messages Sep 13, 2009 – Sep 14, 2009

lore
Share & tools
lore
#0 lore raw
Quoted 15 lines · Catalin Marinas

Yes, but the exclusives are not affected (see below).

Quoted 4 lines

Meanwhile, if we could assume that interrupt handlers are always using the LDREX/CLREX in pairs, then the same thing could be assumed for any other contexts in the system, kernel/user threads. Therefore, I do not think that we can make that assumption.

In user space you can get (T1, T2 are threads):

T1 T2
LDREX
LDREX
STREX (succeeds)
STREX (fails)

Quoted 3 lines

So the STREX in T1 shouldn't really succeed because there was a context switch and LDREX in T2 (this particular case may not be a problem but if you create a situation with 3 threads that is incorrect).

Hey, wait a moment. It's true that with >=2 CPUs, another CPU could write the location used by T1, so T1's STREX should not succeed.

But what about a single CPU system?

Even with 3 or more threads, I do not see how any sequence could result in the STREX succeeding wrongly, because it can only be wrong if there's an intermediate write to the same location, and we've established that all writes to that location (including atomic_set) use STREX. And in principle, even if atomic_set is changed in future, all paths leading to it must clear the monitor flag somehow.

In other words, it looks like CLREX is not required in __switch_to() on single CPU systems.

What do you think Catalin? Do you have a counterexample?

-- Jamie

#1 lore raw
Quoted 32 lines · Jamie Lokier
Quoted 15 lines · Catalin Marinas

Yes, but the exclusives are not affected (see below).

Quoted 4 lines

Meanwhile, if we could assume that interrupt handlers are always using the LDREX/CLREX in pairs, then the same thing could be assumed for any other contexts in the system, kernel/user threads. Therefore, I do not think that we can make that assumption.

In user space you can get (T1, T2 are threads):

T1 T2
LDREX
LDREX
STREX (succeeds)
STREX (fails)

Quoted 3 lines

So the STREX in T1 shouldn't really succeed because there was a context switch and LDREX in T2 (this particular case may not be a problem but if you create a situation with 3 threads that is incorrect).

Hey, wait a moment. It's true that with >=2 CPUs, another CPU could write the location used by T1, so T1's STREX should not succeed.

But what about a single CPU system?

Even with 3 or more threads, I do not see how any sequence could result in the STREX succeeding wrongly, because it can only be wrong if there's an intermediate write to the same location, and we've established that all writes to that location (including atomic_set) use STREX. And in principle, even if atomic_set is changed in future, all paths leading to it must clear the monitor flag somehow.

Quoted 2 lines

In other words, it looks like CLREX is not required in __switch_to() on single CPU systems.

With two or more threads, you can have something like below, even on UP systems:

T1 T2
LDREX
LDREX
STREX (succeeds)
LDREX
STREX (succeeds)
STREX (fails)

Thread T2 perform two successive atomic modifications but the context switch happens during the second one, so STREX in T1 should not succeed.

Signature · 1 line
Catalin
#2 lore raw
Quoted 13 lines · Catalin Marinas
Quoted 1 line

But what about a single CPU system?

With two or more threads, you can have something like below, even on UP systems:

T1 T2
LDREX
LDREX
STREX (succeeds)
LDREX
STREX (succeeds)
STREX (fails)

Quoted 2 lines

Thread T2 perform two successive atomic modifications but the context switch happens during the second one, so STREX in T1 should not succeed.

That's very convincing, and you are right of course. Thanks!

-- Jamie