The dumbest (futex-based) mutex

Question

After reading Ulrich Drepper's "Futexes are Tricky", I have written the following "dumbest mutex" in C++14 using the Linux futex primitives. This mutex is simpler than Drepper's; I believe it to be correct. The reason it gets to be so simple is the same as the reason I'm calling it the "dumbest mutex": it makes a system call on every unlock, even if the mutex is not being contended and nobody's waiting for the lock.

Therefore this is not a good mutex if you care about performance.

My question is: Leaving aside the performance issue, is this a correct mutex? Or does it, like most hand-written concurrency code, have some subtle bug? Stylistic comments are also welcome.

#include <atomic>
#include <linux/futex.h>
#include <syscall.h>
#include <unistd.h>

inline int futex_wait(void *addr, int block_if_value_is) {
    return syscall(SYS_futex, addr, block_if_value_is, nullptr, nullptr, 0);
}

inline int futex_wake_one(void *addr) {
    return syscall(SYS_futex, addr, FUTEX_WAKE, 1, nullptr, nullptr, 0);
}

class mutex {
    std::atomic<int> m_state;
    static constexpr int UNLOCKED = 0;
    static constexpr int LOCKED = 1;
public:
    constexpr mutex() noexcept : m_state(UNLOCKED) {}

    bool try_lock() {
        return m_state.exchange(LOCKED) == UNLOCKED;
    }

    void lock() {
        while (m_state.exchange(LOCKED) != UNLOCKED) {
            futex_wait(&m_state, LOCKED);
        }
    }

    void unlock() {
        m_state = UNLOCKED;
        futex_wake_one(&m_state);
    }
};

Answer 1

is this a correct mutex?

It is not correct. There is a requirement for std::mutex::lock (http://en.cppreference.com/w/cpp/thread/mutex/lock):

If another thread has already locked the mutex, a call to lock will block execution until the lock is acquired.

A simple test below that uses your mutex consumes 100% CPU that means it is busy-waiting. I think you did it by mistake.

On the contrary if I use std::mutex for the same test consumes 0% CPU in waiting on mt.lock().

mutex mt;
int main() {
    auto f = []() {
        mt.lock();
        mt.unlock();
    };
    mt.lock();
    std::thread t (f);
    std::this_thread::sleep_for(std::chrono::seconds(60));
    mt.unlock();
    t.join();
}

Below is a pidstat report for running a test with your mutex:

$ pidstat 1 -p $(pidof custom_mutex)  
Linux 3.10.0-229.el7.x86_64 (sk71.net.billing.ru)       05/16/2017      _x86_64_        (2 CPU)

09:44:31 AM   UID       PID    %usr %system  %guest    %CPU   CPU  Command
09:44:32 AM  1000      9806   11.00   88.00    0.00   99.00     0  custom_mutex
09:44:33 AM  1000      9806   14.00   86.00    0.00  100.00     0  custom_mutex
09:44:34 AM  1000      9806   13.00   86.00    0.00   99.00     0  custom_mutex
09:44:35 AM  1000      9806   15.00   84.00    0.00   99.00     0  custom_mutex
09:44:36 AM  1000      9806   15.00   83.00    0.00   98.00     0  custom_mutex
09:44:37 AM  1000      9806   12.00   87.00    0.00   99.00     0  custom_mutex
09:44:38 AM  1000      9806   16.00   83.00    0.00   99.00     0  custom_mutex
09:44:39 AM  1000      9806   15.00   85.00    0.00  100.00     0  custom_mutex

And this is a report for a test that uses std::mutex:

$ pidstat 1 -p $(pidof std_mutex)    
Linux 3.10.0-229.el7.x86_64 (sk71.net.billing.ru)       05/16/2017      _x86_64_        (2 CPU)

09:46:45 AM   UID       PID    %usr %system  %guest    %CPU   CPU  Command
09:46:46 AM  1000      9965    0.00    0.00    0.00    0.00     0  std_mutex
09:46:47 AM  1000      9965    0.00    0.00    0.00    0.00     0  std_mutex
09:46:48 AM  1000      9965    0.00    0.00    0.00    0.00     0  std_mutex
09:46:49 AM  1000      9965    0.00    0.00    0.00    0.00     0  std_mutex
09:46:50 AM  1000      9965    0.00    0.00    0.00    0.00     0  std_mutex
09:46:51 AM  1000      9965    0.00    0.00    0.00    0.00     0  std_mutex
09:46:52 AM  1000      9965    0.00    0.00    0.00    0.00     0  std_mutex
09:46:53 AM  1000      9965    0.00    0.00    0.00    0.00     0  std_mutex

update

---

I believe your mistake is in parameters for syscall. FUTEX_WAKE on my Linux is equal to 1. But take a look at:

inline int futex_wait(void *addr, int block_if_value_is) {
    return syscall(SYS_futex, addr, block_if_value_is, nullptr, nullptr, 0);
}

It passes block_if_value_is to SYS_futex as a parameter for int op. However the value of block_if_value_is in your program is equal to LOCKED and LOCKED is 1 (it means that it is equal to FUTEX_WAKE):

static constexpr int UNLOCKED = 0;
static constexpr int LOCKED = 1;

futex_wait(&m_state, LOCKED);

So you do not wait. You actually ask the kernel to wake up 0 (nullptr) processes. That is why you instead of waiting in kernel on your futex returns:

return syscall(SYS_futex, addr, block_if_value_is, nullptr, nullptr, 0);

Answer 2

Since stylistic comments are also welcome I will start very simple. I prefer to reserve upper-case names for macros. Instead of

static constexpr int UNLOCKED = 0;
static constexpr int LOCKED = 1;

you could/should define an enumeration for named constants

enum class State { unlocked, locked };
std::atomic<State> m_state;

This has the advantage that it guarantees to not consume any memory.

Answer 3

Couple of points on improving the implementation:

1. Line 7: futex_wait doesn't specify FUTEX_WAIT which should be the third argument.

   syscall(SYS_futex, addr, **FUTEX_WAIT,** block_if_value_is, nullptr, nullptr, 0);
   

2. You should use FUTEX_WAIT_PRIVATE and FUTEX_WAKE_PRIVATE - more optimal unless you intend to use this mutex for cross-process synchronization.

3. A more optimal implementation of the lock() method would first check if the spinlock is locked, and if it is, it wouldn't exactly busy-wait but spin consuming as little resources as possible. If it is still locked after that, the calling thread would schedule itself out for a bit because there still is contention, and only then start busy-waiting. Something like:

   bool is_locked() {
       return m_state.load() == LOCKED;
   }
   
   void lock() {
       for (int i = 0; is_locked() && i < 500; ++i) {
           __builtin_ia32_pause();   // on Linux (find an equivalent on other platforms)
       }
   
       if (is_locked()) {
           sched_yield();    // include <sched.h>  on Linux
       }
   
       while (!try_lock()) {
           futex_wait(&m_state, LOCKED);
       }
   }
   

   __builtin_ia32_pause on gcc allows you to spin on a hyperthreaded core without the need for heavy context switching to run the other process sharing the core with you.