cpp compare_exchange_strong fails spuriously?

Question

So I'm pretty new to CPP and i was trying to implement a resource pool (SQLITE connections), for a small project that I'm developing.

The problem is that I have a list(vector) with objects created at the beginning of the program, that have the given connection and its availability (atomic_bool). If my program requests a connection from this pool, the following function gets executed:

gardener_db &connection_pool_inner::get_connection() {
    bool expected = false;

    for(auto & pair : pool) {
        std::atomic_bool &ref = pair->get_is_busy_ref();
        if (ref.compare_exchange_strong(expected, true)) {
            return pair->get_conn();
        }//if false it means that its busy
    }
    std::lock_guard<std::mutex> guard(vector_mutex);//increment size
    std::atomic_bool t = true;
    pool.emplace_back(std::make_shared<pool_elem>());
    pool.back()->get_is_busy_ref().store(t);// because we are giving the resource to the caller
    return pool.back()->get_conn();
}

So I made a simple test to see if my vector is resizing:

constexpr unsigned int CONNECTION_POOL_START_SIZE = 20;
TEST(testConnPool, regrow) {
    auto saturation = std::vector<connection_handler>();
    ASSERT_EQ(saturation.size(), 0);
    for(int i = 0; i < CONNECTION_POOL_START_SIZE; i++) {
        saturation.emplace_back();
    }
    auto ptr = connection_pool_inner::instance();
    auto size = ptr->get_pool().size();

    //it  should be full at this point
    ASSERT_EQ(size, CONNECTION_POOL_START_SIZE);
}

the problem is that I get 22 as my size as opposed to 20 which is what I would expect.

I was able to narrow down the problem to the compare_exchage_strong() but, it was my understanding that the "strong" variant wouldn't fail. So I debugged it, and its always the third element of my vector that gets skipped, (even when working on a single thread).

I already test it the same thing on a different computer(and architecture) but the same problem still occurs so I'm guessing the problem is the logic.

Any ideas about what's going on?

MRE

#include <mutex>
#include <atomic>
#include <iostream>
#include <vector>
#include <memory>

class foo {
    std::atomic_bool inner;
public:
    explicit foo(): inner(false){};
    std::atomic_bool &get(){return inner;}
};

std::mutex vector_mutex;
std::vector<std::shared_ptr<foo>> resources;

void get_resource() {
    bool expected = false;
    for(auto & rsc : resources) {
        if (rsc->get().compare_exchange_strong(expected, true)) {
            return;
        }
    }
    std::lock_guard<std::mutex> guard(vector_mutex);//increment size
    resources.emplace_back(std::make_shared<foo>());
}

int main() {
    std::vector<std::shared_ptr<foo>> *local = &resources;
    for(int i = 0; i < 20; i++) {
        resources.emplace_back(std::make_shared<foo>());
    }
    for(int i = 0; i < 20; i++) {
        get_resource();
    }
    std::cout << resources.size();
}

Answer 1

The code results in undefined behavior in a multithreaded environment.

While the loop for(auto & pair : pool) is runing in one thread, pool.emplace_back(std::make_shared<pool_elem>()) in another thread invalidates pool iterators that are used in the running loop under the hood.

You have the error in the loop. std::atomic::compare_exchange_strong:

<...> loads the actual value stored in *this into expected (performs load operation).

Let's vector busy to be a conditional name for busy states. The first get_connection() call results in the vector busy to be { true, false, ... false }.

The second get_connection() call:

1. expected = false;
2. busy[0] is true is not equal to expected, it gets expected = true;
3. busy[1] is false is not equal to the updated expected, it gets expected = false;
4. busy[2] is false is equal to the updated expected, results in the vector busy to be { true, false, true, false, ... false }.

The further 8 get_connection() calls result in the vector busy to be { (true, false) * 10 }.

The 11th and 12th get_connection() calls add yet a couple of true and result in the vector busy to be { (true, false) * 10, true, true }, the size is 22.

Other get_connection() calls do not modify the vector anymore:

0. <...>
1. busy[10] is true is not equal to expected, it gets expected = true;
2. busy[11] is true is equal to the updated expected, return.

The fix

// bool expected = false;  ───────┐
//                                │
for(auto & pair : pool) {   //    │
    bool expected = false;  // ◄──┘
    std::atomic_bool &ref = pair->get_is_busy_ref();
    if (ref.compare_exchange_strong(expected, true)) {
        return pair->get_conn();
    }//if false it means that its busy
}