atomic::compare_exchange returns wrong value

[KernelAddress]

Bugzilla Link	30675
Version	trunk
OS	Linux
CC	@chandlerc,@eugenis,@kcc,@mclow,@rengolin

Extended Description

llvm/clang/libc++ are on rev 271514.

Test is:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <atomic>

template<int kSize>
struct MyStruct {
  char data[kSize];

  explicit MyStruct(char v = 0) noexcept {
    memset(&data[0], v, sizeof(data));
  }

  bool operator == (const MyStruct &other) const {
    return memcmp(&data[0], &other.data[0], sizeof(data)) == 0;
  }

  bool operator != (const MyStruct &other) const {
    return !(*this == other);
  }

  operator int() const {
    return data[0];
  }
};

int main() {
  typedef MyStruct<6> T;
  std::atomic<T> a(T(0));
  T cmp(17);
  if (a.compare_exchange_strong(cmp, T(18), std::memory_order_acquire)) {
    fprintf(stderr, "%d: bad atomic value %d\n", __LINE__, (int)cmp);
    exit(1);
  }
  if (cmp != T(0)) {
    fprintf(stderr, "%d: bad atomic value %d\n", __LINE__, (int)cmp);
    exit(1);
  }
}

The test works with libstdc++:

$ bin/clang++ /tmp/atomic.cc -std=c++11 -latomic && ./a.out

But fails with libc++:

$ bin/clang++ /tmp/atomic.cc -std=c++11 -stdlib=libc++ -latomic && LD_LIBRARY_PATH=./lib/ ./a.out
36: bad atomic value 17

[llvmbot]

Could this be related to #29793 ?

[KernelAddress]

#29793 looks like a different bug: it talks about corruption of the atomic variable itself, and it tests atomic.

[llvmbot]

Argh! Ignore me please, that one is ARM specific. I got confused.

[llvmbot]

So this bug seems to have something to do with types with trailing padding. sizeof(T) == 6 but sizeof(_Atomic(T)) == 8. Adding two more bytes onto T works around the issue.

I'm rebinning this as Clang since it reproduces with Clang's intrinsics.

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <atomic>

template<int kSize>
struct MyStruct {
  char data[kSize];

  explicit MyStruct(char v = 0) noexcept {
    memset(&data[0], v, sizeof(data));
  }

  bool operator==(const MyStruct &other) const {
    return memcmp(&data[0], &other.data[0], sizeof(data)) == 0;
  }

  bool operator != (const MyStruct &other) const {
    return !(*this == other);
  }

  int get_int() const {
    return data[0];
  }
};

int main() {
  typedef MyStruct<6> T;
  _Atomic(T) a(T(0));
  T cmp(17);
  if (__c11_atomic_compare_exchange_weak(&a, &cmp, T(18),
                                         std::memory_order_seq_cst,
                                         std::memory_order_seq_cst)) {
    fprintf(stderr, "%d: bad atomic value %d\n", __LINE__, cmp.get_int());
    exit(1);
  }
  if (cmp != T(0)) {
    fprintf(stderr, "%d: bad atomic value %d\n", __LINE__, cmp.get_int());
    exit(1);
  }
}

[ecatmur]

This is still an issue on current trunk 18.0.0git 2e45326. This affects classes for which sizeof is not a power of 2; adding an appropriate alignas makes the problem go away even for kSize not a power of 2.

[ecatmur]

The problem appears to be that clang/libc++ is using a lock-free implementation (lock cmpxchg) where this is inappropriate (it is only appropriate for register sized types); std::atomic<T>::is_always_lock_free is (inappropriately) true for these odd-sized types.

[13steinj]

simpler example (godbolt):

#include <atomic>

#include <cstddef>

template<std::size_t N>
struct S {
    char a;
    char padding_bytes[N];
};

#if PADDING > 0
static constexpr std::size_t padding = PADDING;
#else
static constexpr std::size_t padding = 0;
#endif

int main() {
    std::atomic<S<padding>> x{{1}};
    S<padding> expected{2};
    const S<padding> desired{3};
    x.compare_exchange_strong(expected, desired);
    return expected.a;
}

[13steinj]

my bad this part is actually a godbolt error #56778 (comment)

more (interestingly? insane?): even in cases where it is using libatomic you still get the warning

clang++: warning: -latomic: 'linker' input unused [-Wunused-command-line-argument]

and if you take off -latomic then linker failure

/opt/compiler-explorer/gcc-snapshot/lib/gcc/x86_64-linux-gnu/14.0.0/../../../../x86_64-linux-gnu/bin/ld: /tmp/example-11345c.o: in function `bool std::__atomic_impl::__compare_exchange<false, S<2ul> >(S<2ul>&, std::remove_volatile<S<2ul> >::type&, std::remove_volatile<S<2ul> >::type&, bool, std::memory_order, std::memory_order)':
/opt/compiler-explorer/gcc-snapshot/lib/gcc/x86_64-linux-gnu/14.0.0/../../../../include/c++/14.0.0/bits/atomic_base.h:1002: undefined reference to `__atomic_compare_exchange'
clang++: error: linker command failed with exit code 1 (use -v to see invocation)
Execution build compiler returned: 1

[shafik]

CC @mordante @ldionne earlier comment indicates this is a libc++ issues, do you agree?

[mordante]

This indeed looks wrong, based on the fact that Clang does the right thing with libstdc++ I indeed expect it is our bug.
@huixie90 maybe you want to have a look at it.

[huixie90]

Hello @shafik @13steinj @ecatmur ,

The issue of compare_exchange is expected in the sense that we have not implemented P0528R3 yet. That paper requires atomic::compare_exchange_[weak, strong] to work with types with paddings.

You can find the libc++ status here:
https://libcxx.llvm.org/Status/Cxx20.html

That being said, I am actively working on this paper just now.
I already started a draft PR here:
#75371

[ecatmur]

I feel that I should point out that MyStruct<6> does not have padding bits; all the bits of its object representation participate in its value representation. The issue appears to be that its object representation (and value representation) is between register sizes.

That said, I don't doubt that this issue is connected to the resolution of P0528R3 and I'm grateful that you're working on it. Can I ask that you add tests for this case?

[huixie90]

I feel that I should point out that MyStruct<6> does not have padding bits; all the bits of its object representation participate in its value representation. The issue appears to be that its object representation (and value representation) is between register sizes.

That said, I don't doubt that this issue is connected to the resolution of P0528R3 and I'm grateful that you're working on it. Can I ask that you add tests for this case?

Yes sure I will definitely add tests for that. Yes the struct itself does not have padding. Actually it is us (Libc++) who adds the padding via _Atomic ( which is meant to make types size power of 2, which IIRC is the IR layer requirement to use compare exchange).

[huixie90]

Investigated a bit and indeed this is a different issue. there might be multiple problems but the first problem I have seen is in CGAtomic.cpp where we emit LLVM IR from from the builtin __c11_atomic_compare_exchange_strong

The following code would assign Val1 and Val2 into temporary buffer of power of 2 when the original expected type is not power of 2.

  if (ShouldCastToIntPtrTy) {
    Ptr = Atomics.castToAtomicIntPointer(Ptr);
    if (Val1.isValid())
      Val1 = Atomics.convertToAtomicIntPointer(Val1);
    if (Val2.isValid())
      Val2 = Atomics.convertToAtomicIntPointer(Val2);
  }

later after cmpxchg, when it stores the results of updated expected, it stores to Val1, which points to the temporary

  CGF.Builder.CreateStore(Old, Val1);

This would generate the following IR

cmpxchg.store_expected:                           ; preds = %entry
  store i64 %5, ptr %atomic-temp, align 8
  br label %cmpxchg.continue

So the updated expected value is never written back to the original reference that user passed in.

https://godbolt.org/z/h44oveaz5

[llvmbot]

@llvm/issue-subscribers-clang-codegen

Author: None (a8b4922b-9ceb-405e-9794-fa0271302cc2)

| | | | --- | --- | | Bugzilla Link | [30675](https://llvm.org/bz30675) | | Version | trunk | | OS | Linux | | CC | @chandlerc,@eugenis,@kcc,@mclow,@rengolin |

Extended Description

llvm/clang/libc++ are on rev 271514.

Test is:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <atomic>

template<int kSize>
struct MyStruct {
  char data[kSize];

  explicit MyStruct(char v = 0) noexcept {
    memset(&data[0], v, sizeof(data));
  }

  bool operator == (const MyStruct &other) const {
    return memcmp(&data[0], &other.data[0], sizeof(data)) == 0;
  }

  bool operator != (const MyStruct &other) const {
    return !(*this == other);
  }

  operator int() const {
    return data[0];
  }
};

int main() {
  typedef MyStruct<6> T;
  std::atomic<T> a(T(0));
  T cmp(17);
  if (a.compare_exchange_strong(cmp, T(18), std::memory_order_acquire)) {
    fprintf(stderr, "%d: bad atomic value %d\n", __LINE__, (int)cmp);
    exit(1);
  }
  if (cmp != T(0)) {
    fprintf(stderr, "%d: bad atomic value %d\n", __LINE__, (int)cmp);
    exit(1);
  }
}

The test works with libstdc++:

$ bin/clang++ /tmp/atomic.cc -std=c++11 -latomic && ./a.out

But fails with libc++:

$ bin/clang++ /tmp/atomic.cc -std=c++11 -stdlib=libc++ -latomic && LD_LIBRARY_PATH=./lib/ ./a.out
36: bad atomic value 17

[llvmbot]

@llvm/issue-subscribers-c-11

Author: None (a8b4922b-9ceb-405e-9794-fa0271302cc2)

| | | | --- | --- | | Bugzilla Link | [30675](https://llvm.org/bz30675) | | Version | trunk | | OS | Linux | | CC | @chandlerc,@eugenis,@kcc,@mclow,@rengolin |

Extended Description

llvm/clang/libc++ are on rev 271514.

Test is:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <atomic>

template<int kSize>
struct MyStruct {
  char data[kSize];

  explicit MyStruct(char v = 0) noexcept {
    memset(&data[0], v, sizeof(data));
  }

  bool operator == (const MyStruct &other) const {
    return memcmp(&data[0], &other.data[0], sizeof(data)) == 0;
  }

  bool operator != (const MyStruct &other) const {
    return !(*this == other);
  }

  operator int() const {
    return data[0];
  }
};

int main() {
  typedef MyStruct<6> T;
  std::atomic<T> a(T(0));
  T cmp(17);
  if (a.compare_exchange_strong(cmp, T(18), std::memory_order_acquire)) {
    fprintf(stderr, "%d: bad atomic value %d\n", __LINE__, (int)cmp);
    exit(1);
  }
  if (cmp != T(0)) {
    fprintf(stderr, "%d: bad atomic value %d\n", __LINE__, (int)cmp);
    exit(1);
  }
}

The test works with libstdc++:

$ bin/clang++ /tmp/atomic.cc -std=c++11 -latomic && ./a.out

But fails with libc++:

$ bin/clang++ /tmp/atomic.cc -std=c++11 -stdlib=libc++ -latomic && LD_LIBRARY_PATH=./lib/ ./a.out
36: bad atomic value 17