Optimistic locking strategy with atomics in C++ and ordering

Question

After reading up on c++0x's atomics and in combination with non locking queues I decided to have a go at playing with them.

The idea was to write a single producer, multiple consumer queue with optimistic locking. The messages do not need to be consumed. Skipping is perfectly fine as long as that if a consumer reads it reads the last version or knows that it's read was bad.

In the code below the strategy I had in mind fails. The data gets corrupted because data is written out-of-order. Any pointers on why this is, and how to fix it would be greatly appreciated.

Compilation on Linux: g++ -std=c++0x -o code code.cpp -lpthread

Thanks, Dennis

//
// This features 2 threads in which the first writes to a structure
// and the second tries to read from that with an optimistic
// locking strategy. The data is equal to the versioning so we can 
// see if the data is corrupt or not.
//
// @since: 2011-10-28
// @author: Dennis Fleurbaaij <[email protected]>
//

#include <pthread.h>
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <stdatomic.h>
#include <sched.h>
#include <assert.h>
#include <iostream>
#include <xmmintrin.h>

struct structure_t
{
    std::atomic<unsigned int> id;
    unsigned int data_a;
    unsigned int data_b;

    char _pad[ 64 - 12 ];
};

#define NUM_STRUCTURES 2
struct structure_t structures[NUM_STRUCTURES];

std::atomic<size_t> current_version_index;

volatile bool start = false;
volatile bool run = true;
size_t const iter_count = 10000000;

/**
 * Write thread
 */
void* writer(void*)
{
    while(!start)
        sched_yield();

    size_t i;
    for( i=0 ; i<iter_count ; ++i )
    {
        size_t index = current_version_index.load(std::memory_order_relaxed);
        size_t next_index = ( current_version_index + 1 ) & NUM_STRUCTURES-1;

        structures[next_index].data_a = i;
        structures[next_index].data_b = i;

        structures[next_index].id.store(i, std::memory_order_release);

        current_version_index.store(next_index);

        //std::cout << "Queued - id: " << i << ", index: " << next_index << std::endl;
        //sleep(1);
    }

    run=false;
}

/**
 * Read thread
 */
void* reader(void*)
{
    while(!start)
        sched_yield();

    unsigned int prev_id=0;

    size_t i;
    while(run)
    {
        size_t index = current_version_index.load(std::memory_order_relaxed);
        unsigned int id = structures[index].id.load(std::memory_order_acquire);

        if( id > prev_id )
        {
            unsigned int data_a = structures[index].data_a;
            unsigned int data_b = structures[index].data_b;

            // Re-read the data and check optimistic lock. This should be read after 
            // the lines above and should not be optimized away.
            //
            // This is what fails after a while:
            // Error in data. Index: 0, id: 24097, id2: 24097, data_a: 24099, data_b: 24099
            unsigned int id2 = structures[index].id.load(std::memory_order_acquire);
            if( id2 > id )
            {
                continue;
            }

            if( id != id2 ||
                id != data_a ||
                id != data_b )
            {
                std::cerr << "Error in data. Index: " << index << ", id: " << id 
                          << ", id2: " << id2 << ", data_a: " << data_a << ", data_b: " << data_b << std::endl;

                exit(EXIT_FAILURE);
            }

            //std::cout << "Read. Index: " << index << ", id: " << id 
            //              << ", data_a: " << data_a << ", data_b: " << data_b << std::endl;

            prev_id = id;
        }

        _mm_pause();
    }
}

/**
 * Main
 */
int main (int argc, char *argv[])
{
    assert( sizeof(structure_t) == 64 );

    pthread_t write_thread, read_thread;
    pthread_create(&write_thread, NULL, writer, (void*)NULL);
    pthread_create(&read_thread, NULL, reader, (void*)NULL);

    sleep(1);

    start = 1;

    void *status;
    pthread_join(read_thread, &status);
    pthread_join(write_thread, &status);
}

Answer 1

Perhaps, this is a bug:

    structures[next_index].data_a = i;
    structures[next_index].data_b = i;

// **** The writer may be interrupted (preempted) here for a long time ***
// at the same time the reader reads new data but old id (number of reads doesn't matter)

    structures[next_index].id.store(i, std::memory_order_release); // too late!

(current_version_index may be taken by reader from previous steps, so race condition is actually possible)