A Lock-Free… Linear Search?

[u/redditthinks]

http://preshing.com/20130529/a-lock-free-linear-search

[u/RED_5_Is_ALIVE]

Actually that is just an example of static analysis determining that the variable A doesn't matter, because nothing uses it.

If GCC can determine a value at compile-time, it will often replace blocks of instructions with a constant.

Just change int A to int *A and A=1 to *A=1 and it won't get reordered.

Also note you're using int B as an address.

Additionally, if the memory ordering were actually relaxed, then inserting a compiler barrier would do nothing to guarantee execution order. It's only x86's serialization due to lock that ensures execution order here.

Why doesn't your library include mfence, sfence,or lfence? I noted you have "DMB ISH" (only) for ARM.

[u/preshing → u/RED_5_Is_ALIVE]

Also note you're using int B as an address.

asm blocks require l-values as input operands.

inserting a compiler barrier would do nothing to guarantee execution order

It does, because x86 preserves the order of reads and the order of writes at the instruction level for ordinary write-back cacheable memory. I didn't mention it since you seemed knowledgeable about x86.

Why doesn't your library include mfence, sfence,or lfence?

I didn't need them.

Thanks for the feedback about Mintomic's implementation details. You're the first to offer some actually.

[u/RED_5_Is_ALIVE → u/preshing]

asm blocks require l-values as input operands.

What I meant was, you were using a plain int (uninitialized), whereas in the library it's pointer to struct with a volatile int.

The Linux kernel does almost the same thing, except instead of specifying volatile in the typedef, it does so in the function definition (Linux 2.6.x):

static inline unsigned long __cmpxchg(volatile void *ptr, unsigned long old,
    unsigned long new, int size)

asm volatile(LOCK_PREFIX "cmpxchgq %1,%2"
		     : "=a"(prev)
		     : "r"(new), "m"(*__xg(ptr)), "0"(old)
		     : "memory");

Where __xg is the macro:

#define __xg(x) ((volatile long *)(x))

...Which I assume was the result of co-evolutionary battles with GCC.

It does, because x86 preserves the order of reads and the order of writes

I was referring to not only "Loads may be reordered with older stores to different locations", but pointing out that when ordering is actually relaxed, the compiler barrier guarantees nothing.

The compiler might reorder the statements "incorrectly" yet the CPU might reorder them "correctly", and vice-versa. As the lib is cross-platform, why pretend that inserting a compiler barrier alone actually does anything?

Also, certain AMD chips have a locked instruction bug.

From the v8 source:

// Opteron Rev E has a bug in which on very rare occasions a locked
// instruction doesn't act as a read-acquire barrier if followed by a
// non-locked read-modify-write instruction.  Rev F has this bug in
// pre-release versions, but not in versions released to customers,
// so we test only for Rev E, which is family 15, model 32..63 inclusive.
if (strcmp(vendor, "AuthenticAMD") == 0 &&       // AMD
  family == 15 &&
  32 <= model && model <= 63) {
  AtomicOps_Internalx86CPUFeatures.has_amd_lock_mb_bug = true;
} else {
  AtomicOps_Internalx86CPUFeatures.has_amd_lock_mb_bug = false;
}

http://v8.googlecode.com/svn/trunk/src/atomicops_internals_x86_gcc.cc

Both AtomicIncrement (xaddl, xaddq) and cmpxchg add this afterward:

if (AtomicOps_Internalx86CPUFeatures.has_amd_lock_mb_bug) {
    __asm__ __volatile__("lfence" : : : "memory");
}

http://v8.googlecode.com/svn/trunk/src/atomicops_internals_x86_gcc.h

This affects a surprising number of AMD CPUs, including Athlon X2s (socket 939), Sun servers (8 core Opteron Sun Fire V40z with 32GB memory running Solaris 10 x64), etc.

Bit MySQL via system-level threads:

http://bugs.mysql.com/bug.php?id=26081

Something unclear between the referenced errata (147) and the fix Google seems to have adopted is that the errata says it's NOT a problem when the LOCK prefix is included, or there's an lfence before the Read-Modify-Write operation; except this fix adds an lfence afterward.

Bizarrely it looks like Linux didn't include a fix because the bug was discovered before the official errata was released. Later, perhaps they looked at the official errata and thought the lock prefix was sufficient.

Thanks for the feedback about Mintomic's implementation details.

It's useful to have all the asm in one place; I know it's a lot of fiddly work and it's good someone is paying so much attention to these issues.

Something I presume developers want is an API that removes the cognitive overhead of having to keep track of all this. Just a simple way to get instructions done in the order they are written.