8
\$\begingroup\$

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);
    }
};
\$\endgroup\$
8
\$\begingroup\$

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);
\$\endgroup\$
  • \$\begingroup\$ 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. \$\endgroup\$ – Martin York May 16 '17 at 2:22
  • \$\begingroup\$ 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. \$\endgroup\$ – Quuxplusone May 16 '17 at 6:08
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ – Sergei Kurenkov May 16 '17 at 7:02
  • \$\begingroup\$ @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. \$\endgroup\$ – Sergei Kurenkov May 16 '17 at 7:04
  • 1
    \$\begingroup\$ @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? \$\endgroup\$ – Quuxplusone May 16 '17 at 14:08
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ 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"). \$\endgroup\$ – Quuxplusone Jun 17 at 0:53

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.