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.)

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. — bvj
– bvj, Commented Dec 3, 2013 at 18:57
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. — HarryLeong
– HarryLeong, Commented Dec 9, 2013 at 17:50
Related: Implementing 64 bit atomic counter with 32 bit atomics / A readers/writer lock... without having a lock for the readers? — Peter Cordes
– Peter Cordes, Commented Mar 7, 2023 at 8:01

janneb · Accepted Answer · 2013-12-03 07:49:45Z

2

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

answered Dec 3, 2013 at 7:49

janneb

37.4k2 gold badges85 silver badges101 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

HarryLeong Over a year ago

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

briand · Accepted Answer · 2013-12-11 16:58:17Z

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.

answered Dec 11, 2013 at 16:58

briand

3101 silver badge4 bronze badges

Collectives™ on Stack Overflow

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

2 Answers 2

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related