Why does my lock-free message queue segfault :(?

Question

As a purely mental exercise I'm trying to get this to work without locks or mutexes. The idea is that when the consumer thread is reading/executing messages it atomically swaps which std::vector the producer thread uses for writes. Is this possible? I've tried playing around with thread fences to no avail. There's a race condition here somewhere because it occasionally seg faults. I imagine it's somewhere in the enqueue function. Any ideas?

// should execute functions on the original thread
class message_queue {
public:
    using fn = std::function<void()>;
    using queue = std::vector<fn>;

    message_queue() : write_index(0) {
    }

    // should only be called from consumer thread
    void run () {
        // atomically gets the current pending queue and switches it with the other one
        // for example if we're writing to queues[0], we grab a reference to queue[0]
        // and tell the producer to write to queues[1]
        queue& active = queues[write_index.fetch_xor(1)];
        // skip if we don't have any messages
        if (active.size() == 0) return;
        // run all messages/callbacks
        for (auto fn : active) {
            fn();
        }
        // clear the active queue so it can be re-used
        active.clear();
        // swap active and pending threads
        write_index.fetch_xor(1);
    }
    void enqueue (fn value) {
        // loads the current pending queue and append some work
        queues[write_index.load()].push_back(value);
    }
private:
    queue queues[2];
    std::atomic<bool> is_empty; // unused for now
    std::atomic<int> write_index;


};
int main(int argc, const char * argv[])
{

    message_queue queue{};
    // flag to stop the message loop
    // doesn't actually need to be atomic because it's only read/wrote on the main thread
    std::atomic<bool> done(false);
    std::thread worker([&queue, &done] {
        int count = 100;
        // send 100 messages
        while (--count) {
            queue.enqueue([count] {
                // should be executed in the main thread
                std::cout << count << "\n";
            });
        }
        // finally tell the main thread we're done
        queue.enqueue([&] {
            std::cout << "done!\n";
            done = true;
        });
    });
    // run messages until the done flag is set
    while(!done) queue.run();
    worker.join();
}

Answer 1

Your lock-free queue fails to work because you did not start with at least a semi-formal proof of correctness, then turn that proof into an algorithm with the proof being the primary text, comments connecting the proof to the code, all interconnected with the code.

Unless you are copy/pasting someone else's implementation who did do that, any attempt to write a lock-free algorithm will fail. If you are copy-pasting someone else's implementation, please provide it.

Lock free algorithms are not robust unless you have such a proof that they are correct, because the kind of errors that make them fail are subtle, and extreme care must be taken. Simply "rolling" a lock free algorithm, even if it fails to result in apparent problems during testing, is a recipe for unreliable code.

One way to get around writing a formal proof in this kind of situation is to track down someone who has written proven correct pseudo code or the like. Sketch out the pseudo code, together with the proof of correctness, in comments. Then fill in the code in the holes.

In general, proving an "almost correct" lock free algorithm is flawed is harder than writing a solid proof that a lock free algorithm is correct if implemented in a particular way, then implementing it. Now, if your algorithm is so flawed that it is easy to find the flaws, then you aren't showing a basic understanding of the problem domain.

In short, by posting "why is my algorithm wrong", you are approaching how to write lock free algorithms incorrectly. "Where is the flaw in my proof?", "I proved this pseudo-code correct here, and then I implemented it, why do my tests show deadlocks?" are good lock-free questions. "Here is a bunch of code with comments that merely describe what the next line of code does, and no comments describing why I do the next line of code, or how that line of code maintains my lock-free invariants" is not a good lock-free question.

Step back. Find some proven-correct algorithms. Learn how the proof work. Implement some proven correct algorithms via monkey-see monkey-do. Look at the footnotes to note the issues their proof overlooked (like A-B issues). After you have a bunch of those under your belt, try a variation, and do the proof, and check the proof, and do the implementation, and check the implementation.

Answer 2

if I understand your code correctly, there are data races, e.g.:

// producer
int r0 = write_index.load(); // r0 == 0

// consumer
int r1 = write_index.fetch_xor(1); // r1 == 0
queue& active = queues[r1];
active.size();

// producer
queue[r0].push_back(...);

Now both threads access the same queue at the same time. That's a data race, and that means undefined behaviour.