2
\$\begingroup\$

Here is my implementation of std compatible RWSpinLock using 2 atomics.

I think in cases when spinlock is free, it should take just 1 atomic write operation.

class RWSpinLock{
    std::atomic<int> readers_count{0};
    std::atomic<bool> write_now{false};
public:
    void lock() {
        while (!write_now.exchange(true, std::memory_order_acquire)){
            std::this_thread::yield();
        }

        // wait for readers to exit
        while (readers_count != 0 ){
            std::this_thread::yield();
        }
    }
    void unlock() {
        write_now.store(false, std::memory_order_release);
    }

    void lock_shared() {
        // unique_lock have priority
        while(true) {
            while (write_now) {     // wait for unlock
                std::this_thread::yield();
            }

            readers_count.fetch_add(1, std::memory_order_acquire);

            if (write_now){
                // locked while transaction? Fallback. Go another round
                readers_count.fetch_sub(1, std::memory_order_release);
            } else {
                // all ok
                return;
            }
        }
    }
    void unlock_shared() {
        readers_count.fetch_sub(1, std::memory_order_release);
    }
};

On unique_lock wait for write_now flag, then wait for readers_count.

On shared_lock wait for write_now flag, then increase readers_count. If during incrementation write_now flag becomes true, decrease readers_count and wait again for write_now (this should be relativley rare case).

P.S. I'm not sure though, about memory_order, and overall correctness (but seems fine to me).

\$\endgroup\$
  • \$\begingroup\$ Spin locks are not a good thing to implement. But this is not a spin lock because it yields std::this_thread::yield(); A spin lock goes into a loop trying to acquire the lock (not yielding the thread just doing a busy wait). \$\endgroup\$ – Martin York Jul 7 '17 at 19:06
  • 1
    \$\begingroup\$ @LokiAstari, I'd argue that this does count as a spinlock, since it doesn't sleep for any relevant period; it's morally equivalent in my mind to a spinlock on x86 that does PAUSE inside the inner loop. Even if it did sleep_for(1s) in the inner loop, I'd call it morally a spinlock, not a mutex. (The defining characteristic of a proper mutex, for me, is that it wakes up at the proper time and wastes a comparatively little amount of time polling in high-contention situations.) Maybe we can compromise and call this a "polling" mutex? :) \$\endgroup\$ – Quuxplusone Jul 7 '17 at 19:10
  • \$\begingroup\$ @Quuxplusone en.wikipedia.org/wiki/Spinlock \$\endgroup\$ – Martin York Jul 7 '17 at 19:11
  • \$\begingroup\$ @Loki Astari Let's consider that at all places where it yields, it first 40 cycles just spin, than go to yield. Consider yield just for brevity. \$\endgroup\$ – tower120 Jul 7 '17 at 19:12
3
\$\begingroup\$

I'm fairly certain that you have a one-character typo-bug here:

    while (!write_now.exchange(true, std::memory_order_acquire)){

This should read

    while (write_now.exchange(true, std::memory_order_acquire)) {

— that is, "Put true into the write_now bit; and if it was already true, then wait. Only proceed if the old value was actually false."

What you have with the ! is "Put true into the write_now bit; and if it was already true, then continue (oops!). Otherwise, yield once, and then continue anyway because now it'll be true for sure." ["For sure" here being a relative term. Obviously it won't be true if the old writer managed to finish and release the lock in the time we spent yielding.]


Performance nitpick: I've heard that it is useful to put one cache-line's worth of padding in between your two atomic variables, to eliminate false sharing. Of course if you do that then your shared_spinlock class gets much bigger.

But if you don't do that, then all this fiddling with memory orders is useless, because your few seq_cst accesses to the shared cache line in lock and lock_shared will effectively seq_cst all your accesses in those functions.

As usual, I advise staying away from memory orders unless you're sure that you know what you're doing. That said, I think you're using them correctly here.


            if (write_now){

You might consider making this

            if (write_now.load(std::memory_order_seq_cst)) {

and likewise every other time you load an atomic variable without a memory order. As I said, normally I advise not to use memory orders other than seq_cst at all; but since you are using them, maybe it would be a good idea to mark every single load and store, consistently?

I also suspect that that particular load could be memory_order_acquire maybe, but seriously don't quote me on that. I have no idea.


    // unique_lock have priority

This comment should say lock have priority, or simply writers have priority.


C++ nitpick: Consider marking all of these member functions noexcept.


Functionality suggestion: Consider providing a way for a writer to atomically demote itself to a reader, without releasing the lock (i.e., without allowing some other writer B to sneak in and change the value that A just wrote). This should be possible, I think; and it's definitely not possible for anyone but you, the author of the mutex, to provide this functionality.

I think it's as simple as this:

void unlock_and_lock_shared() {
    readers_count.fetch_add(1, std::memory_order_acquire);
    write_now.store(false, std::memory_order_release);
}

The naming convention comes from Boost.

\$\endgroup\$
  • \$\begingroup\$ Can you maybe suggest standalone header only RWSpinLock ? I found only folly github.com/facebook/folly/blob/master/folly/RWSpinLock.h, and that one was diffenetley not standalone . \$\endgroup\$ – tower120 Jul 7 '17 at 19:31
  • \$\begingroup\$ @tower120: I have no special knowledge here; but how about just using libc++'s C++17 shared_mutex? I didn't verify, but it looks header-only, as long as you have a conforming <mutex> and <condition_variable> to use with it. OTOH, that's a RWMutex, definitely not a RWSpinlock. I do tend to agree with Loki that "Spin locks are not a good thing to implement"... \$\endgroup\$ – Quuxplusone Jul 7 '17 at 21:39
  • \$\begingroup\$ Nah, I benchmarked libc++'s/gcc std lib/vs std lib shared_mutexes before. Spinlock, particularly this one , at least twice faster. "Spin locks are not a good thing to implement" - what does this mean? \$\endgroup\$ – tower120 Jul 8 '17 at 0:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.