Experimental SeqLock

#include <iostream>
#include <thread>
#include <atomic>
#include <mutex>
#include <shared_mutex> // for a benchmark
#include <algorithm>
#include <chrono>
#include <ratio>
#include <cstdlib>



// Sorry about the hardcoded macros! ;^(
#define CT_THREADS 32
#define CT_ITERS 20000000
#define CT_SEQLOCK_CELL 64

// uncomment for to log read spins. SeqLock only...
//#define CT_LOG

// uncomment to test shared mutex
//#define CT_TEST_SHARED_MUTEX


#if defined CT_LOG
static std::atomic<unsigned long> g_log_read_spins(0);
#endif


// User data anyone? ;^)
struct ct_data
{
    int m_a;
    int m_b;
    int m_c;

    ct_data() : m_a(0), m_b(1), m_c(2) {}

    void inc(ct_data const& data)
    {
        m_a = data.m_a + 1;
        m_b = data.m_b + 1;
        m_c = data.m_c + 1;
    }

    bool validate()
    {
        return (m_a + 1 == m_b && m_b + 1 == m_c);
    }
};


// A seqlock data cell
struct ct_cell
{
    std::atomic<unsigned long> m_ver;
    ct_data m_data;

    ct_cell() : m_ver(0) {}
};


// Wrapper for the user
struct ct_cell_ref
{
    unsigned long m_ver;
    ct_data m_data;
    ct_cell* m_next;
};


// The main impl...
struct ct_seqlock
{
    std::mutex m_mutex;
    std::atomic<ct_cell*> m_cur;
    ct_cell m_cells[CT_SEQLOCK_CELL];

    ct_seqlock() : m_cur(m_cells) {}


    bool validate()
    {
        for (std::size_t i = 0; i < CT_SEQLOCK_CELL; ++i)
        {
            if (! m_cells[i].m_data.validate()) return false;
        }

        return true;
    }

    ct_cell_ref write_lock()
    {
        m_mutex.lock();

        ct_cell* cur = m_cur.load(std::memory_order_relaxed);
        ct_cell* next = m_cells + ((cur - m_cells + 1) % CT_SEQLOCK_CELL);

        ct_cell_ref cell_ref = { next->m_ver, cur->m_data, next };

        next->m_ver.store(cell_ref.m_ver + 1, std::memory_order_relaxed);

        std::atomic_thread_fence(std::memory_order_acq_rel);

        return cell_ref;
    }

    void write_unlock(ct_cell_ref const& cell_ref)
    {
        cell_ref.m_next->m_ver.store(cell_ref.m_ver + 2, std::memory_order_release);

        // make it visible to the reader...
        m_cur.store(cell_ref.m_next, std::memory_order_release);

        m_mutex.unlock();
    }


    ct_data read()
    {
        unsigned long spins = 0;

        ct_data data;

        for (;;++spins)
        {
            ct_cell* cell = m_cur.load(std::memory_order_consume);

            unsigned long ver0 = cell->m_ver.load(std::memory_order_acquire);

            if (ver0 & 1)
            {
                // spin on locked state
                // We can spin, backoff or do something else...
                // For now, we just yield and spin away! ;^)
                std::this_thread::yield();
                continue;
            }

            data = cell->m_data;

            std::atomic_thread_fence(std::memory_order_acquire);

            unsigned long ver1 = cell->m_ver.load(std::memory_order_relaxed);

            if (ver0 == ver1) break;

            // spin on data changed
        }

#if defined CT_LOG
        g_log_read_spins.fetch_add(spins, std::memory_order_relaxed);
#endif

        return data;
    }
};



// The test app

// a simple timer
struct ct_time
{
    // Type aliases to make accessing nested type easier
    using clock_type = std::chrono::steady_clock;
    using second_type = std::chrono::duration<double, std::ratio<1> >;

    std::chrono::time_point<std::chrono::steady_clock> m_beg;

    ct_time() : m_beg(std::chrono::steady_clock::now()) {}

    void reset()
    {
        m_beg = std::chrono::steady_clock::now();
    }

    double elapsed() const
    {
        return std::chrono::duration_cast<std::chrono::duration<double, std::ratio<1> >>
            (clock_type::now() - m_beg).count();
    }
};


struct ct_shared_state
{
    ct_seqlock m_seqlock;

#if defined (CT_TEST_SHARED_MUTEX)
    std::shared_mutex m_std_shared_mutex;
#endif

    void write()
    {
#if ! defined (CT_TEST_SHARED_MUTEX)
        ct_cell_ref cell_ref = m_seqlock.write_lock();
        cell_ref.m_next->m_data.inc(cell_ref.m_data);
        m_seqlock.write_unlock(cell_ref);
#else
        m_std_shared_mutex.lock();
        m_seqlock.m_cells[0].m_data.inc(m_seqlock.m_cells[0].m_data);
        m_std_shared_mutex.unlock();

#endif
    }

    bool read()
    {
#if ! defined (CT_TEST_SHARED_MUTEX)
        ct_data data = m_seqlock.read();
        return data.validate();
#else
        m_std_shared_mutex.lock_shared();
        ct_data data = m_seqlock.m_cells[0].m_data;
        m_std_shared_mutex.unlock_shared();
        return data.validate();
#endif
    }
};





void
ct_thread(ct_shared_state& shared)
{
    for (unsigned long i = 0; i < CT_ITERS; ++i)
    {
        if (! shared.read()) break;
        if (! shared.read()) break;
        shared.write();
        if (! shared.read()) break;
        shared.write();
        if (! shared.read()) break;
        if (! shared.read()) break;
    }
}



int main()
{
    std::cout << "Quick and Dirty SeqLock Experiment ver:(0.0.0)\n";
    std::cout << "By: Chris M. Thomasson\n";
    std::cout << "________________________________________\n";
    std::cout << "Threads = " << CT_THREADS << "\n";
    std::cout << "Iterations = " << CT_ITERS << "\n";
    std::cout << "SeqLock Cells = " << CT_SEQLOCK_CELL << "\n";

#if defined (CT_LOG)
    std::cout << "Logging is on\n";
#endif

#if defined (CT_TEST_SHARED_MUTEX)
    std::cout << "Using a shared mutex\n";
#endif


    std::cout << "\nLaunching...\n";
    std::cout.flush();

    ct_shared_state shared_state;

    ct_time timer;

    {
        std::thread threads[CT_THREADS];

        for (unsigned int i = 0; i < CT_THREADS; ++i)
        {
            threads[i] = std::thread(ct_thread, std::ref(shared_state));
        }

        std::cout << "Running...\n";
        std::cout.flush();

        for (unsigned int i = 0; i < CT_THREADS; ++i)
        {
            threads[i].join();
        }
    }

    double time_elpased = timer.elapsed();

    std::cout << "Complete!\n";
    std::cout << "Time = " << time_elpased << "\n";
    std::cout << "________________________________________\n";


    if (shared_state.m_seqlock.validate())
    {
        std::cout << "DATA IS COHERENT!!! :^D\n\n\n";
    }

    else
    {
        std::cout << "DATA IS __FOOBAR__! God DAMN IT!!!! ;^o\n\n\n";
    }

#if defined CT_LOG
    unsigned long log_read_spins = g_log_read_spins.load(std::memory_order_relaxed);
    std::cout << "CT_LOG: log_read_spins = " << log_read_spins << "\n";
#endif

    return 0;
}