The dumbest (futex-based) mutex

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);
}

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);
}
};


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();
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);

• busy-waiting is blocking. Not a very good blocking but it is still blocking. The lock() is not required to release the core for other uses. – Martin York May 16 '17 at 2:22
• Hm. You really see 100% CPU usage? You don't see mt.lock() doing a single atomic XCHG and then going to sleep in the futex_wait syscall? I don't have the capability to check right now, but I'll try to find someone with a Linux laptop tomorrow and see if I can reproduce what you're seeing. – Quuxplusone May 16 '17 at 6:08
• @Loki Astari Look, this mutex does busy-waiting by mistake, not on intention. I believe in the futex_wait function the third parameter is simply wrong. – Sergei Kurenkov May 16 '17 at 7:02
• @Quuxplusone, updated my answer. Yes, indeed, I don't see your mutex going to sleep in the futex_wait syscall. I think your third argument in this cal is wrong. – Sergei Kurenkov May 16 '17 at 7:04
• @Sergei yikes! Of course you're right about the typo in futex_wait. Did you (could you?) try the code again with the obvious fix? It should say return syscall(SYS_futex, addr, FUTEX_WAIT, block_if_value_is, nullptr, nullptr, 0);. Does that fix the bug? – Quuxplusone May 16 '17 at 14:08

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.

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() {
}

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.

• In my experience, "spin" and "busy-wait" are synonyms. I think that your "for" loop is an example of spinning/busy-waiting. I think both places in your answer where you use the term "busy-wait," what you mean is "block"/"wait"/"sleep" (all of which are synonymous with each other in my experience, and none of which is synonymous with "spin"/"poll"/"busy-wait"). – Quuxplusone Jun 17 at 0:53