基于 futex 的 4 字节单写入器/多读取器锁

Question

寻找一个基于 futex 的单写入器/多读取器锁的最小实现，不需要超出单个 4 字节 futex 状态变量的空间开销。

一些背景：我有一个应用程序，它将在数千万到数亿个小对象中的每一个中嵌入一个锁。由于锁定的粒度非常细以及应用程序的结构，我预计争用最少。此外，作家将变得稀少，而有竞争力的作家则更加稀少。出于所有这些原因，在这种特定设置中，（理论上）容易出现“听到雷声”现象的解决方案是完全可以接受的。

Answer 1

您可以在 https://gist.github.com/smokku/653c469d695d60be4fe8170630ba8205 找到我的

实现是只能有一个线程获取写入锁（futex value 0），锁可以打开（futex value 1），或者可以有多个读取线程（ futex 值大于 1）。因此，低于 1 的值（只有一个）会阻止 futex 上的读取器和写入器，而高于 1 的值仅阻止写入器。解锁线程会唤醒等待线程之一，但您需要小心，不要消耗仅由写入线程唤醒的读取线程。

#define cpu_relax() __builtin_ia32_pause()
#define cmpxchg(P, O, N) __sync_val_compare_and_swap((P), (O), (N))

static unsigned _lock = 1; // read-write lock futex
const static unsigned _lock_open = 1;
const static unsigned _lock_wlocked = 0;

static void _unlock()
{
    unsigned current, wanted;
    do {
        current = _lock;
        if (current == _lock_open) return;
        if (current == _lock_wlocked) {
            wanted = _lock_open;
        } else {
            wanted = current - 1;
        }
    } while (cmpxchg(&_lock, current, wanted) != current);
    syscall(SYS_futex, &_lock, FUTEX_WAKE_PRIVATE, 1, NULL, NULL, 0);
}

static void _rlock()
{
    unsigned current;
    while ((current = _lock) == _lock_wlocked || cmpxchg(&_lock, current, current + 1) != current) {
        while (syscall(SYS_futex, &_lock, FUTEX_WAIT_PRIVATE, current, NULL, NULL, 0) != 0) {
            cpu_relax();
            if (_lock >= _lock_open) break;
        }
        // will be able to acquire rlock no matter what unlock woke us
    }
}

static void _wlock()
{
    unsigned current;
    while ((current = cmpxchg(&_lock, _lock_open, _lock_wlocked)) != _lock_open) {
        while (syscall(SYS_futex, &_lock, FUTEX_WAIT_PRIVATE, current, NULL, NULL, 0) != 0) {
            cpu_relax();
            if (_lock == _lock_open) break;
        }
        if (_lock != _lock_open) {
            // in rlock - won't be able to acquire lock - wake someone else
            syscall(SYS_futex, &_lock, FUTEX_WAKE_PRIVATE, 1, NULL, NULL, 0);
        }
    }
}