Re: [Qemu-devel] [PATCH 0/7] target-ppc/linux-user: NPTL support

[Paul Brook <paul@codesourcery.com>]

On Saturday 06 June 2009, malc wrote:
> On Thu, 4 Jun 2009, Nathan Froyd wrote:
> > This patch series adds NPTL support in Linux user-mode emulation to
> > 32-bit PowerPC targets.
> >
> > The main complication comes from implementing atomic instructions
> > properly.  We chose to implement a simplistic model:
> >
> > - reserved loads record the value loaded;

An important point here is that the address/value pair is per thread/cpu.
A nice side-effect is that these loads reduce to a simple atomic load and some 
thread local bookkeeping. Conditional stores require somewhat more exotic 
atomic operations, but still don't need to go poking at system global state or 
other CPUs.
This sounds strange at first reading, but ll/sc semantics are deliberately 
designed to minimize contention between unrelated CPUs/resources in large 
systems.

> > - conditional stores check that the memory at the effective address
> >   contains the value loaded by the previous reserved load, in addition
> >   to all other checks.  if so, the store succeeds; otherwise, it fails.
>
> I think this will break code that relies on the fact that ll/sc is not
> affected by the ABA problem.

I'm not absolutely certain about PPC, but on other architectures (ARM, MIPS, 
Alpha) this implementation is sufficient.

The only questionable case is when a second thread overwrites and then 
restores the original value between a locked load and a conditional store. 
However limited coherency and memory ordering between CPUs make it impossible 
to know whether this modify+restore occurred before or after the initial load.

The worst that can happen here is that another thread gains and releases the 
lock[1] while the current thread is in the process of acquiring the lock.  
Even when this happens it is impossible for two threads to acquire the lock 
simultaneously. The only difference is the window between ll and sc. During 
this period we don't know whether we have the lock or not, so it's extremely 
unlikely that we will do anything that relies on no other thread having the 
lock. In practice ll/sc are always used as matching pairs with no intervening 
memory accesses, so this is never a problem.

I could probably come up with synthetic testcases where qemu behavior is 
observably different to real hardware. However I'm pretty certain this never 
occurs in real code, and it is questionable whether such behavior is 
architecturally defined.

If you still believe this is a problem you need come up with an actual 
testcase that demonstrates how this can introduce a race condition.

Paul

[1] Lock acquisition is the most obvious example, but the same applies to any 
atomic operation implemented on top of ll/sc.