CODEWITHSUNDEEP
c++c++11
Florian Loch
Florian Loch

Reputation: 809

std::atomic.compare_and_exchange_strong() fails

I am pretty new to C++ and have to do some exercises on atomic operations. I am implementing a AtomicHashSet - but I get confused by compare_and_exchange_strong()behaving different than I would expect it.

As internal data structure I use an array of std::atomic-instances:

std::atomic<Item<T>> data[N] = {};

The essential part observing the problems is the following:

bool insert(const T &key) {
    if (keysStored.load() == N) {
        return false;
    }

    size_t h = this->hash(key);



    for (size_t i = 0; i < N; i++) {
        size_t pos = (h + i) % N;
        data[pos].load(); //No idea why that is needed...
        Item<T> atPos = data[pos].load();

        if (atPos.dataRef == &key) {
            return false;
        }
        if (atPos.dataRef == nullptr && atPos.state == BucketState::Empty) {
            Item<T> atomDesired(&key, BucketState::Occupied);

            if (data[pos].compare_exchange_strong(atPos, atomDesired)) {
                keysStored++;
                return true;
            }
        }
    }

    return false;
}

Item is defined like this:

enum class BucketState { Empty, Occupied, Deleted };

template<typename T>
struct Item {
Item(): dataRef(nullptr), state(BucketState::Empty) {}
Item(const T* dataRef, BucketState state) : dataRef(dataRef), state(state) {}

const T* dataRef;
BucketState state;
};

I do some assertion tests (inserting an element twice, checking keyStoredetc.). With this code they succeed - but if I remove the nonsense data[pos].load(); call they fail due to compare_exchange_strong() returning false. This strange failing behavior occurs only the first time the function is called...

I also checked with a debugger - the value of atPos is the same as in data[pos] - so in my understanding ces should do the exchange and returjn true.

Another question: Do I have to use a special memory order to ensure atomic (and therefore threadsafe) behaviour?

Upvotes: 1

Views: 1137

Answers (1)

MikeMB
MikeMB

Reputation: 21136

It is hard to say without a mvce, but the problem arises most probably due to padding. std::atomic.compare_and_exchange_strong conceptually uses memcmp to compare the current state with the expected one. Due to alignment requirements, the size of your Itemstructure will be 16 bytes on a 64 bit machine (two pointers) but only 12 of them actually contribute to its value (8 for the pointer and 4 for the enum).

So the statement

Item<T> atPos = data[pos].load();

only copies the first 12 bytes, but std::atomic.compare_and_exchange_strong will compare all 16. To solve this you could explicitly specify the underlying type of BucketState to be an integral type that has the same size as a pointer (usually size_t and uintptr_t have that property).

E.g. Item could look like this:

enum class BucketState :size_t { Empty, Occupied, Deleted };

template<typename T>
struct Item {
    const T* dataRef;
    BucketState state;

    static_assert(sizeof(const T*) == sizeof(BucketState), "state should have same size as dataRef");
};

I can't tell you however, why using the statement data[pos].load(); makes a difference. If I'm not mistaken, your implicit call to std::memcmp causes undefined behavior, as it will read uninitialized memory.

Another question: Do I have to use a special memory order to ensure atomic (and therefore threadsafe) behaviour?

The short answer is no, you don't need to.

The long answer is that first of all, accesses to std::atomics are always thread safe and atomic (those are not the same). Memory ordering become relevant, when you want to use those atomics to guard access to non-atomic shared memory (like if (dataAvalialbe) //readSharedmemory). However, the default memory ordering for all operations on atomics is memory_order_seq_cst, which is the strongest there is.

Upvotes: 4

Related Questions