how to implement a seqlock lock using c++11 atomic library

Question

I want to write a seqlock using c++11 atomic library. I have read some questions about seqlock on stackoverflow， but no one helped me. The algorithm I use is common, and you can find it everywhere.That's my code:

struct sequence_spinlock_t {

    void write_lock() {
        lock.lock();
        flags.fetch_add(1, memory_order_acquire); //A

    }

    void write_unlock() {
        flags.fetch_add(1, memory_order_release); //B
        lock.unlock();
    }

    void read_enter(uintptr_t *flag) {
        for (;;) {
            uintptr_t f = flags.load(memory_order_acquire); //C
            if ((f & 1) == 0) {
                *flag = f;
                break;
            }
            pause();
        }
    }

    bool_ read_leave(uintptr_t flag) {                                        

        uintptr_t f = flags.load(memory_order_relaxed); //D
        return f == flag;
    }

    spinlock_t lock;
    atomic_uintptr_t flags;
};

    //read thread
    uintptr_t flag;
    do {
        lock.read_enter(&flag);      (0)
        //read something             (1)
    } while(!lock.read_leave(flag))  (2)


    //write thread
    lock.write_lock();              (3)
    //write something               (4)
    lock.write_unlock();            (5)

I ensure I use the memory_order tags correctly at B and C.

I don't think it's correct at A and D.

Think about we read and write protected data at same time.I worry that the read value of flags at D is too old, and we don't read the newest value written by write_lock().But we read the newest value of protected data written by the write thread(That may not happens on x86 system, but I don't assume the code is running on x86.).After read thread finished reading protected data, because of the read value of flags is too old, I don't find the sequence have been increased.read thread yield out from loop and we make a bug.

The read value of protected data at (1) is written at (4), and the read value of flags at (2) is NOT written at (3) (it is written when we unlock write lock last time.).That is why I think there is a bug.

But I really don't know to fix this.I have tried to make a “synchronized with” relationship between read_leavee() and write_locke()(I want "read_leave() synchronized with write_locke()").But there is no store action in read_leave(),So I failed.

(Oh!The c++ standard specification is too hard for me to understand.Partly because I'm not from an English speaking country.)

Cobalt

Is this essentially a "readable" mutex/cs? – Tour

Sorry.I don't understand what is "readable" mutex/cs? – Cobalt

Not sure if it has an official name these days, but some time ago, I created a class that along with the typical lock semantics allows for concurrent reading of critical regions given no active write lock. The write lock cannot enter until all the readers left the region. I'm curious if that's the eventual intention of your class. – Tour

No!That is NOT my intention.What you said about is similar to shared_lock(in c++14 standard) or read_write_lock (in linux kernel). – Cobalt

For seqlock, the write thread CAN acquire the lock while read thread is still reading.But when read thread try to leave the critical region，it may find the write thread have edited the protected data.In that case,read thread should try read protected data again. – Cobalt

Related: Implementing 64 bit atomic counter with 32 bit atomics / A readers/writer lock... without having a lock for the readers? – Wristwatch

Answer 1

Using memory_order_relaxed in read_leave is per se ok, but you indeed need to ensure that the data values have been loaded before loading the flag variable. You can do this with std::atomic_thread_fence. I.e. your read_leave ought to look like

bool read_leave(uintptr_t flag) {
    atomic_thread_fence(memory_order_acquire);
    uintptr_t f = flag.load(memory_order_relaxed);
    return f == flag;
}

FWIW, with this change your code looks roughly like Example 3 in http://safari.ece.cmu.edu/MSPC2012/slides_posters/boehm-slides.pdf

Woolcott

Ok,I read the file,I don't understand version 3，but I understand version 4. – Cobalt

Answer 2

It is worth noting that the data that the seqlock is protecting has to have an atomic type and you have to use atomic load/stores to access it. Not ideal, but that is what C11/C++11 gives you. Han Boehm's MSPC paper goes through the details.

Repugn