3

I have been reading through and coding up examples from Anthony Williams' book Concurrency in Practice and needed to enable double-word-compare-and-exchange for gcc4.8 using -mcx16 so that a struct containing a pointer an int could be manipulated in a lock-free atomic manner.

Does Clang (any version) support double-word-compare-and-exchange on x64?

The following code gives linking errors in GCC4.8 and Clang 3.3 without extra compiler options:

#include <atomic>
#include <thread>

struct ReferenceCountedPointer
{
  int referenceCount;
  void* data;
};

int main()
{
  std::atomic<ReferenceCountedPointer> arcp;
  ReferenceCountedPointer rcp;

  arcp.compare_exchange_weak(rcp, rcp);

  return 0;
}

The above program is pointless but illustrates the linking errors I see.

Compilation commands I used for Clang and GCC are:

Clang 3.3:

clang++-mp-3.3 -std=c++11 -stdlib=libc++ CX16.cpp -o CX16

Fails with:

Undefined symbols for architecture x86_64:
"___atomic_compare_exchange", referenced from:
  _main in CX16-plVSvq.o
ld: symbol(s) not found for architecture x86_64

GCC4.8:

g++-mp-4.8 -std=c++11 CX16.cpp -o CX16

Fails with:

Undefined symbols for architecture x86_64:
"___atomic_compare_exchange_16", referenced from:
  std::atomic<ReferenceCountedPointer>::compare_exchange_weak(ReferenceCountedPointer&,        ReferenceCountedPointer, std::memory_order, std::memory_order) in ccOjp95s.o
ld: symbol(s) not found for architecture x86_64
jbcoe
  • 3,611
  • 1
  • 30
  • 45
  • 1
    Most systems provide this kind of stuff. Why do you want/need to rely on a compiler feature? – Macmade Aug 25 '13 at 19:48
  • You can always use inline assembler – PlasmaHH Aug 25 '13 at 19:49
  • @Macmade neither GCC 4.8 nor Clang 3.3 will link my code without the flag. I'll update the question with a minimal code sample – jbcoe Aug 25 '13 at 19:50
  • @PlasmaHH I don't think I need to. Would be nice to keep things portable. – jbcoe Aug 25 '13 at 19:51
  • 1
    @jcoe: portable is relative here if you are already tied to a specific processor model (range). – PlasmaHH Aug 25 '13 at 19:55
  • 1
    this is obviously a bug in both libraries (llvm's libc++ and gnu's libstdc++), as they seem to declare a method which cannot be resolved at loading. – Walter Aug 25 '13 at 20:38

2 Answers2

6

The issue here is that SOME models of 64-bit processors do not have a cmpxchg16b. The -mcx16 tells the compiler that "I know that this processor supports the cmpxchg16b instructions, so you can generate it". This is to avoid problems with older 64-bit processors which don't support this instruction - they would then cause an "illegal opcode trap". It's the same thing as using for example SSE4.

Mats Petersson
  • 126,704
  • 14
  • 140
  • 227
1

ReferenceCountedPointer is trivially copyable, so the code is valid under C++11. Apparently the library does not conform to the standard.

Pete Becker
  • 74,985
  • 8
  • 76
  • 165
  • It looks like libc++ and libstdc++ are falling short. Both complain about missing symbols. – jbcoe Aug 25 '13 at 20:13
  • I was under the impression that my code would compile and link even without double-word-compare-exchange but would use mutexes and not be lock free. This seems consistent with what you say. – jbcoe Aug 25 '13 at 20:32
  • 1
    @PeteBecker: I'm not entirely sure what you are trying to say. To compare and exchange a data structure that has one pointer and one integer, in a 64-bit architecture, requires a 16-byte compare-exchange operation - if not, then it's not going to be atomic. Of course, one could write some "mutex" locks or similar around it, but I don't think that satisfies the technical definition of atomic. Or have I missed something? – Mats Petersson Aug 25 '13 at 21:59
  • Perhaps I am confused but I thought that atomic<> for user defined-types would be implemented with a mutex by the compiler when double-word operations were not supported by the platform. Even without double-word operations compare-exchange can be made atomic by using a mutex, but not lock-free-atomic. I'm keen to find out what clang's cx16 flag is if it exists. Why the code fails to link might be better as another question if it should be legal c++11. – jbcoe Aug 25 '13 at 22:15
  • 1
    @jcoe - the only atomic type that is **required** to be lock free is `std::atomic_flag`. The others may or may not be, which is why there are the `...is_lock_free` functions and the `ATOMIC...LOCK_FREE` macros. Of course, if `T` in `std::atomic` is small enough, any decent implementation will generate lock-free code; typically that's done for integral types. Microsoft's implementation (which I wrote) makes `atomic` lock-free for **any** `T` that's small enough to be handled without a mutex. – Pete Becker Aug 26 '13 at 12:32
  • 1
    @MatsPetersson - for every type `T` that's trivially copyable (integer types and appropriate UDTs), `atomic` is atomic. For types that are too large to be handled without a lock (mutex or otherwise), the implementation uses a lock; operations on those types are not lock free, but they're still atomic. – Pete Becker Aug 26 '13 at 12:35
  • 1
    @jcoe - just so it doesn't get lost in the weeds, when `T` is too large to be handled by the processor's atomic operations, but is still trivially copyable, the implementation uses some kind of lock (mutex or whatever) and `memcmp` and `memcpy` to implement the atomic operations for `atomic`. – Pete Becker Aug 26 '13 at 12:41
  • 1
    To clarify: "atomic" in the C++11 atomic types means that operations from multiple threads do not create data races, that caches get updated, and that the compiler won't move reads or writes across an atomic operation. That's the abstraction. Processor-level notions such as 16-byte compare-exchange operations are implementation details; if they're available, they should be used; regardless, the implementation has to provide the correct semantics, and its the semantics that you program to, not the implementation details. – Pete Becker Aug 26 '13 at 12:48
  • It looks like GCC4.8 and Clang 3.3 are failing to provide a mutex-based fallback in the absence of primitive operations. Given that this question was initially about a flag for Clang I've asked why the linking errors occur here: http://stackoverflow.com/questions/18437983/missing-atomic-compare-exchange-why-does-code-compile-then-fail-to-link – jbcoe Aug 26 '13 at 14:18
  • Clang 3.4 with Xcode 5.0 libc++ has no problem. As reported above this looks like a library short-coming and thankfully a temporary one. I've been abysmally slow in accepting Pete Becker's answer. Apologies and thanks for you time and help. – jbcoe Nov 11 '13 at 07:56