Sunday, October 25, 2015

Implementing a Reader-Writer Lock using RCU

As surprising as this may seem, it is actually possible to implement a Reader-Writer Lock using the RCU API and the C-RW-WP algorithm (or some other algorithm that you prefer). This is not to be confused to using RCU as a replacement to a Reader-Writer Lock, like what is mentioned here:

What we're going to cover in this post is an actual RW-Lock implementation, which happens to use inside it the RCU API.
Now you may ask:
Why is this interesting?
... or maybe if you're not so nice:
Who in their right mind would want to do that? That's crazy talk!

Well, as it so happens, if the underlying RCU implementation is the kernel one, or the one that uses signals, you can profit from this mechanism to make a rw-lock that can provide some interesting performance, and we're always interested in rw-locks with good performance, right?

So how would we implement one in C++1x ?

std::atomic<bool> writerWaiting { false };
std::mutex        writersMutex;

void sharedLock() {
    while (true) {
        while (writerWaiting.load()) std::this_thread::yield();
        rcu_read_lock();
        if (!writerWaiting.load(std::memory_order_acquire)) return;
        rcu_read_unlock();
    }
}

void sharedUnlock() {
    rcu_read_unlock();
}

void exclusiveLock() {
    writersMutex.lock();
    writerWaiting.store(true); // do we need full membar?
    synchronize_rcu();
}

void exclusiveUnlock() {
    writerWaiting.store(false, std::memory_order_release);
    writersMutex.unlock();
}


All I need now is some time to run some Linux benchmarks to check how good this is...


PS: Fixed some incorrect optimizations in the code thanks to David Goldblatt's comments. Thanks David!

Saturday, October 17, 2015

Talk at CppCon 2015

Last year I was supposed to go give a talk at CppCon but one week earlier I was getting surgery so I couldn't go. This year I was able to attend, and give a talk not just about Left-Right, but also about Progress Conditions and how they affect Latency.
If you care about wait-free data structures (for reads) and about low latency software development, then I strongly recommend this talk.... but I'm totally biased   ;)



Yes, that's me in the video... and no, your sound is not mutted, I just speak low, so you'll have to increase the volume  :)

Presentation slides available on github
https://github.com/CppCon/CppCon2015/tree/master/Presentations/How%20to%20make%20your%20data%20structures%20wait-free%20for%20reads



PS: Big thanks to those of you who dropped by at the end of the talk to give some words of encouragement. Don't worry, Andreia and I are still cooking up new algorithms and data structures and will give more info soon  ;)