[cpp-threads] A niggle on the atomic model (N2145)

[Lawrence Crowl]

On 4/19/07, Paul E. McKenney <paulmck at linux.vnet.ibm.com> wrote:
> On Thu, Apr 19, 2007 at 12:15:18PM +0100, Nick Maclaren wrote:
> > This is why N2145 can't be implemented in one (VERY small) detail, which
> > should be dropped.  The problem is extending "address-free" to allow two
> > address values in the program (virtual addresses) to map to the same
> > location (physical address), and making that defined behaviour for the
> > atomics.
> >
> > Consider an Alpha-like system (load-locked + store-conditional)
> > operating on an integer/point that may span two hardware memory
> > locations (e.g.  64-bit on a 32-bit 'bus').

The implementation should not identify a operation spanning
(hardware) memory locations as lock-free.

> > One obvious code for
> > an atomic copy is:
> >
> > if (A != B)
> >     do {
> >         X = load_locked(A[0]);
> >         Y = load_locked(A[1]);
> >     } while
> >         store_conditional(B[0]) &&
> >             store_conditional(B[1]);
> >
> > This will loop indefinitely if A and B map to the same location, and
> > I can think of no way that the application can detect that, reliably
> > and portably, let alone for reasonable efficiency.

The atomic paper specifically avoids copy because of the difficulty of
making it a lock-free atomic.  So, at the shallow level, I don't think
your example contradicts the specification.

> > Can anyway see a flaw in my argument?
>
> As I understand it, this will unconditionally fail.  The locations of a
> load_linked() and the corresponding store_conditional() must match, or the
> store_conditional() will fail.  In this case, the enclosing "if" statement
> guarantees mismatch, which in turn guarantees store_conditional() failure.
>
> Even given an extended load_linked()/store_conditional() that did what you
> want, in most implementations, store_conditional() is subject to spurious
> failures due to interrupts, context switches, exceptions, and the like.

Note here that lock-free does not mean wait-free.  The implementation is
allowed to loop until it gets right.

> My take was that the point of the address-free requirement is that
> the data structure should itself either contain or identify any
> mutual-exclusion apparatus required to make accesses to the same object
> from different virtual addresses be atomic.  But I must defer to Lawrence
> and Hans on this.

The address-free requirement only applies to the types specified in N2145.
Any "data structures" do not have any such requirement.  This facility is
intended to provide minimal support for memory mapped files and shared
memory between processes.  I do not want the requirement to become
viral.

Am I missing something?

-- 
Lawrence Crowl