futex-more

Futex

futex = Fast Userspace muTexes（快速用户空间互斥体），2002 年由 IBM 的 Hubertus Franke 等人在 Linux 上提出，2.5.7 起进入内核。它不是一把锁，而是一份用户态与内核态的合作契约：

[!tip] 一句话本质 无竞争时在用户态用一条原子指令完成加解锁；仅当真的发生竞争时，才通过 futex(2) 系统调用陷入内核，把线程挂到内核按地址索引的等待队列上休眠。

相关笔记：[[多线程]]、[[内核中的同步]]、[[进程：调度]]、[[内存模型]]、[[协程]]

---

1 第一性原理：为什么需要 futex

从成本模型出发，只有两个事实：

1. 锁在绝大多数时刻是无竞争的。一个线程拿到锁、出临界区的窗口内，往往根本没别人来抢。
2. 系统调用比原子指令贵几个数量级。系统调用要陷入内核、上下文切换；原子指令（x86 的 cmpxchg/lock 前缀）虽比普通指令贵，但仍在用户态完成。

而 futex 之前的同步原语（System V 信号量 semop、文件锁 flock）把两件事都做错了：每次加锁/解锁都无条件陷入内核去操作内核对象——哪怕根本没人竞争。

因此 futex 的设计必然是两层的：

层	形态	职责
用户态	一个 32 位原子变量（位于共享内存）	快速路径：CAS 判定无竞争，直接完成
内核态	futex(2) 系统调用	慢速路径：休眠等待 / 唤醒等待者

[!warning] futex 机制 ≠ futex 系统调用 直接拿 futex(2) 写应用代码是错的。futex 机制的性能来自用户态那一半（glibc 已替你写好），系统调用只是慢速路径。应用层永远用 std::mutex / pthread_mutex。

---

2 全景时序

以两线程竞争 pthread_mutex 为例（state：0 无主 / 1 有主无等待 / 2 有主有等待）：

sequenceDiagram
    participant T1 as 线程 T1
    participant U as 用户态锁变量 state
    participant K as 内核 futex
    participant T2 as 线程 T2

    T1->>U: CAS(0 → 1) 成功
    Note over T1,U: 无竞争，纯用户态，零系统调用
    T2->>U: CAS(0 → 1) 失败（state==1）
    T2->>U: 置 state = 2（标记有等待者）
    T2->>K: futex(&state, FUTEX_WAIT, 2)
    K->>K: 校验 *uaddr==2 → 挂入哈希桶等待队列，休眠
    T1->>U: 临界区执行完毕，unlock
    T1->>U: xchg(state → 0)，发现旧值==2
    Note over T1: 旧值>1 说明有人在睡，必须叫醒
    T1->>K: futex(&state, FUTEX_WAKE, 1)
    K->>T2: 移出队列，置 TASK_RUNNING，重新调度
    T2->>U: 返回用户态重抢：CAS(0 → 2)，成功

关键在 unlock 一侧：只有发现旧值是 2（曾有等待者）才进内核唤醒——这就是「无竞争不系统调用」在释放路径上的体现。

---

3 futex 系统调用

#include <linux/futex.h>
long futex(uint32_t *uaddr, int futex_op, uint32_t val,
           const struct timespec *timeout,   /* 或 uint32_t val2 */
           uint32_t *uaddr2, uint32_t val3);

参数	含义
uaddr	用户态共享内存中 futex 变量的地址（内核只存地址，不给它赋予任何语义）
futex_op = FUTEX_WAIT	若 *uaddr == val 则休眠，挂到 uaddr 对应的等待队列；否则立即返回 EAGAIN
futex_op = FUTEX_WAKE	最多唤醒 val 个等待在 uaddr 上的任务，返回实际唤醒数
FUTEX_PRIVATE_FLAG	op 的低位标志：声明 futex 仅用于进程内线程同步，内核可走更快的 key 计算路径
其他 op	FUTEX_REQUEUE、FUTEX_WAKE_OP、FUTEX_LOCK_PI（优先级继承）等进阶操作

[!note] EAGAIN 防「丢失唤醒」 FUTEX_WAIT 要求调用者先读 *uaddr 再传入。若在「读之后、入睡之前」值被人改了，说明该事件已在半路发生——内核拒绝入睡并返回 EAGAIN，让调用者回到用户态重新检查条件。没有这个约定，唤醒方在检查之后、入睡之前的缝隙里发出的 FUTEX_WAKE 就会永远丢失。

两个必须写进肌肉记忆的语义：

1. 虚假唤醒（spurious wakeup）：FUTEX_WAIT 可能无缘无故返回（信号、races），所以等待逻辑必须放在循环里重新验证条件。
2. 返回值语义：WAIT 成功返回 0；WAKE 返回唤醒的任务数（可能为 0——没人可叫不算错误）。

最小可用示例（mmap 共享内存 + fork，父子进程握手）：

#include <linux/futex.h>
#include <sys/syscall.h>
#include <sys/mman.h>
#include <unistd.h>
#include <stdio.h>
#include <errno.h>

static int futex(int *uaddr, int op, int val,
                 const struct timespec *timeout, int *uaddr2, int val3) {
    return syscall(SYS_futex, uaddr, op, val, timeout, uaddr2, val3);
}

void wait_on_futex_value(int* futex_addr, int desired_val) {
    while (1) {
        int observed = *futex_addr;
        if (observed == desired_val) return;          // 条件已满足
        int rc = futex(futex_addr, FUTEX_WAIT, observed, NULL, NULL, 0);
        // EAGAIN：读后被改过 → 回去重查；EINTR：被信号打断 → 重试
        if (rc == -1 && errno != EAGAIN && errno != EINTR) {
            perror("FUTEX_WAIT"); exit(1);
        }
        // 虚假唤醒或被唤醒后回到循环头重新检查
    }
}

void wake_futex(int* futex_addr) {
    int rc = futex(futex_addr, FUTEX_WAKE, 1, NULL, NULL, 0);
    if (rc == -1) { perror("FUTEX_WAKE"); exit(1); }  // rc==0 表示没人可唤醒，正常
}

int main(void) {
    // 必须共享内存：fork 后普通写内存会 COW 私有化
    int shm_id = shmget(IPC_PRIVATE, 4096, IPC_CREAT | 0666);
    int* shared = shmat(shm_id, NULL, 0);
    *shared = 0;

    if (fork() == 0) {                    // 子进程：等 A → 写 B
        wait_on_futex_value(shared, 0xA);
        *shared = 0xB;
        wake_futex(shared);
    } else {                              // 父进程：写 A → 等 B
        *shared = 0xA;
        wake_futex(shared);               // 可能唤醒 0 个（子进程还没睡）
        wait_on_futex_value(shared, 0xB);
        wait(NULL);
    }
    return 0;
}

---

4 用户态视角：mutex 的三态状态机

Ulrich Drepper《Futexes Are Tricky》中的经典实现（glibc 低层锁 lll 与 Go runtime 同款思路），用一个 std::atomic<int> 承载三个状态：

stateDiagram-v2
    [*] --> s0: 初始
    s0: 0 = 无锁
    s1: 1 = 有锁，无等待者
    s2: 2 = 有锁，有等待者
    s0 --> s1: lock: CAS(0→1) 成功（快速路径）
    s1 --> s2: 新的 lock 失败者 CAS(1→2)，随后 FUTEX_WAIT
    s2 --> s2: FUTEX_WAIT 中休眠
    s1 --> s0: unlock: fetch_sub 后旧值==1（快速路径，无需唤醒）
    s2 --> s0: unlock: 旧值==2 → 置 0 并 FUTEX_WAKE
    s2 --> s1: 被唤醒者重抢成功

class Mutex {
    std::atomic<int> atom_;   // 0 无锁 / 1 有锁无等待 / 2 有锁有等待
public:
    void lock() {
        if (cmpxchg(&atom_, 0, 1) != 0) {        // 快速路径失败
            do {
                // 标记“有等待者”：置 2。已是 2 则跳过原子操作
                if (c == 2 || cmpxchg(&atom_, 1, 2) != 0)
                    // 睡在“值为 2”上；虚假唤醒无害，
                    // 因为只有 CAS(0→2) 成功才会退出循环
                    syscall(SYS_futex, (int*)&atom_, FUTEX_WAIT, 2, 0, 0, 0);
            } while ((c = cmpxchg(&atom_, 0, 2)) != 0);  // 醒后重抢
        }
    }
    void unlock() {
        if (atom_.fetch_sub(1) != 1) {   // 旧值!=1 → 曾有等待者
            atom_.store(0);
            syscall(SYS_futex, (int*)&atom_, FUTEX_WAKE, 1, 0, 0, 0);
        }
    }
};

[!note] 为什么需要状态 2？ 它是唤醒方视角的“可能有睡着的等待者”标记。没有它，unlock 无法区分「没人等，直接返回」和「有人在内核里睡，必须叫醒」，要么每次 unlock 都白进一次内核，要么丢失唤醒。glibc lowlevellock.h 的注释把三态写作 0 / 1 / >1，同一个意思。

---

5 内核视角：按地址索引的哈希等待队列

内核里 futex 的本体是一张全局哈希表，把「用户态某地址上睡着的任务」组织起来。Eli 的转述：futex 是内核替用户空间维护的队列。

flowchart LR
    subgraph 用户态传入
        UA[uaddr + flags]
    end
    UA -->|get_futex_key| KEY[futex_key]
    KEY -->|jhash| HB["全局哈希表 __futex_data<br/>256 × num_possible_cpus 个桶"]
    HB --> B0["futex_hash_bucket<br/>spinlock_t lock<br/>plist_head chain（优先级链）"]
    B0 --> Q1[futex_q: task_struct + key + plist 节点]
    B0 --> Q2[futex_q ...]

5.1 关键数据结构

/* 一个等待者 = 一条 futex_q：唤醒/休眠操作都先找到它 */
struct futex_q {
    struct plist_node list;      // 链入 bucket 的优先级链表节点
    struct task_struct *task;    // 被挂起的线程
    spinlock_t *lock_ptr;        // 引用所在 bucket 的自旋锁
    union futex_key key;         // 哈希 key（该 futex 变量的唯一标识）
    u32 bitset;                  // 掩码，配合 FUTEX_WAKE_BITSET
    /* pi_state / rt_waiter ... 与优先级继承（PI futex）相关 */
};

struct futex_hash_bucket {
    atomic_t waiters;            // 桶上等待者计数（wake 可快速判空）
    spinlock_t lock;             // 桶级自旋锁（细粒度分锁）
    struct plist_head chain;     // 优先级链表：RT 按 0~99 排序，普通线程 FIFO
} ____cacheline_aligned_in_smp;  // 桶按缓存行对齐，避免伪共享

/* key 是 union，按同步范围二选一解释 */
union futex_key {
    struct { u64 i_seq; unsigned long pgoff; unsigned int offset; } shared;
    struct { struct mm_struct *mm; unsigned long address; unsigned int offset; } private;
};

key 的推导是「private/shared 之分」的根源：

场景	虚拟地址唯一吗	key 构成	成本
线程间（private）	是——同进程线程共享地址空间	(mm_struct 地址, 虚拟地址)	一次比较，极快
进程间（shared）	否——各进程映射地址不同	(inode->i_seq, page->index, 页内偏移)，即物理页定位	需查页表取物理页，慢得多

默认走 private 快路径；FUTEX_PRIVATE_FLAG 缺失时才按 shared 处理。把这个区分暴露给用户态，本身就是一项性能优化——绝大多数锁是线程锁。哈希表在 futex_init（core_initcall）时按 256 × CPU 数 建桶，配合桶级自旋锁把争抢分散。

5.2 futex_wait 流程

flowchart TD
    A["futex_wait(uaddr, val)"] --> B["futex_wait_setup:<br/>get_futex_key + hash_futex 定位桶，持桶锁"]
    B --> C{"*uaddr == val ?"}
    C -- 否 --> X[返回 EAGAIN<br/>防丢失唤醒]
    C -- 是 --> D["futex_wait_queue_me:<br/>置 TASK_INTERRUPTIBLE<br/>queue_me 挂入桶链<br/>启动 hrtimer（若带超时）"]
    D --> E[freezable_schedule 让出 CPU]
    E --> F{被唤醒 / 超时 / 信号?}
    F -- 唤醒 --> G["unqueue_me 出队，返回 0"]
    F -- 虚假唤醒 --> A
    F -- 超时 --> H[返回 ETIMEDOUT]
    F -- 信号 --> I[返回 ERESTARTSYS]

伪代码：

futex_wait(uaddr, val):
    key  = get_futex_key(uaddr, flags)     # 线程锁→(mm,addr)；进程锁→物理定位
    hb   = hash_futex(key)                 # jhash → bucket
    spin_lock(hb.lock)
    if *uaddr != val:                      # 持桶锁状态下的最后校验
        spin_unlock; return EAGAIN         # 值非预期，拒绝入睡
    current.state = TASK_INTERRUPTIBLE
    queue_me(futex_q, hb)                  # 挂链
    spin_unlock(hb.lock)
    schedule()                             # 睡；醒来后从下一行继续
    return 0

5.3 futex_wake 流程

futex_wake(uaddr, nr_wake):
    key = get_futex_key(uaddr, flags)
    hb  = hash_futex(key)
    if !hb_waiters_pending(hb): return 0    # 桶上没人，直接返回
    wake_q = {}
    spin_lock(hb.lock)
    for q in hb.chain where match_futex(q.key, key):
        wake_q += q.task                    # 收集，先不出队
        if len(wake_q) >= nr_wake: break
    spin_unlock(hb.lock)
    wake_up_q(wake_q)                       # 锁外逐个置 TASK_RUNNING 并重调度

先收集到临时 wake_q、放锁后再统一唤醒，避免持自旋锁时做唤醒重调度，缩短临界区。

---

6 从 std::mutex 到 futex：完整调用链

std::mutex → glibc-nptl → futex(2)

flowchart TD
    A["C++ std::mutex::lock()"] -->|__gthread_mutex_lock| B["glibc pthread_mutex_lock<br/>（nptl/pthread_mutex_lock.c）"]
    B -->|类型==TIMED_NP 默认锁| C["LLL_MUTEX_LOCK 宏"]
    C --> D["__lll_lock 宏：<br/>CAS(lock, 1, 0) 成功 → 完成（纯用户态）"]
    D -->|失败| E["__lll_lock_wait_private（汇编）<br/>lock 置 2 → syscall SYS_futex"]
    E --> F["内核 do_futex → futex_wait"]

glibc 侧 pthread_mutex_t 的状态字段与分发逻辑：

typedef union {
    struct __pthread_mutex_s {
        int __lock;          // 三态：0 无锁 / 1 有锁 / 2 有锁+有竞争
        unsigned int __count;   // 可重入锁的递归计数
        int __owner;            // 持有线程 TID
        int __kind;             // 位 0~6 锁类型；位 7 (128) = process-shared
        __pthread_list_t __list;
    } __data;
} pthread_mutex_t;

#define __lll_lock(futex, private)                                          \
    ((void) ({                                                              \
        int *__futex = (futex);                                             \
        if (atomic_compare_and_exchange_bool_acq(__futex, 1, 0))            \
            __lll_lock_wait(__futex, private);   /* CAS 失败才进内核 */      \
    }))

#define __lll_unlock(futex, private)                                        \
    ((void) ({                                                              \
        int *__futex = (futex);                                             \
        int __oldval = atomic_exchange_rel(__futex, 0);                     \
        if (__glibc_unlikely(__oldval > 1))                                 \
            __lll_lock_wake(__futex, private);   /* 旧值 2 才需要唤醒 */     \
    }))

__kind 的第 8 位 PTHREAD_MUTEX_PSHARED 正对应 FUTEX_PRIVATE_FLAG——用户态声明与内核 key 快慢路径一一衔接。

Android bionic 的 pthread_mutex是同一思想的精简版：atomic_exchange(state, locked_contended) != unlocked 则 __futex_wait_ex；unlock 时 exchange(state, unlocked) == locked_contended 则 __futex_wake_ex。pthread_cond（wait/signal）、pthread_rwlock 也都落在 futex_wait/futex_wake 上。Java 侧：synchronized 由 ART 虚拟机实现，monitor 锁先 CAS 自旋，迟迟拿不到则膨胀为重量级锁，最终 futex(FUTEX_WAIT_PRIVATE) 休眠；JUC 的锁体系底层同样收敛到 futex。

Go runtime 不依赖 libc，自建锁：sync.Mutex 快速路径原子交换，慢速路径 runtime.lock（lock_futex.go，常量 mutex_unlocked/locked/sleeping = 0/1/2）→ futexsleep → FUTEX_WAIT_PRIVATE。

---

7 内核优化前沿

针对「同步 IPC 场景下 T1 唤醒 T2、自己休眠，随后 T2 反向唤醒 T1」的乒乓模式，共四次系统调用、多次调度往返，社区给出了一条递进优化链：

flowchart LR
    A["wake + wait<br/>4 次系统调用"] -->|合并为 1 次调用| B["futex_swap<br/>切换耗时 -29.5%"]
    B -->|唤醒者选核=当前 CPU| C["+ prefer_current_cpu<br/>实测 -92.69%"]
    C -->|bypass 调度器| D["direct-thread-switch<br/>较基线 -37.1%（openEuler）"]

7.1 futex_swap（Google，Peter Oskolkov）

futex_swap(uaddr, val, abs_time, uaddr2)：一次系统调用内完成「唤醒 uaddr2 上至多一个等待者 next + 让自己 wait 在 uaddr 上」。为 SwitchTo（Google 闭源用户态调度框架）而设。

[!note] 魅族实测的泼冷水 移植到 Android 后与 FUTEX_WAKE_WAIT 耗时相差不大。拆解 trace：省下的 2 次系统调用发生在并行时间里，不在关键路径上，只降低系统整体负载。但「一次调用完成唤醒+休眠」为后续优化打开了接口。

7.2 wake_up_process_prefer_current_cpu

futex_swap 唤醒 next 时传入 WF_CURRENT_CPU 标志，select_task_rq_fair 选核时直接选中唤醒者所在 CPU。效果：两线程乒乓跑在同一个核上，schedule() 的 pick_next_task 大概率无缝选中对方。实测 3 轮切换 182µs → 18.4µs（10 倍），但拆解为：CPU 频率 5 倍（单核满载触发提频 500MHz→2.5GHz）× 调度效率 2 倍（免 idle 退出、尾延更低、cache 热）。patch 本身的净收益约 2 倍。与 Android binder 线程互醒场景同构，有移植价值。

7.3 direct-thread-switch（openEuler）

思想出自论文《The Case for Thread Migration》：执行实体与调度实体分离——线程切换时只换执行上下文，不换调度实体，新任务直接用原任务剩余时间片运行，bypass 选核/入队/负载更新，runnable 尾延归零。Linux 的 task_struct 把两者焊死多年，直接拆分不现实；于是基于 futex_swap，在 T1→T2 切换点用 __direct_thread_switch(next) 替代 schedule()，辅以「共享调度实体 shared sched_entry」保住 CFS 公平性。openEuler 数据：futex_swap 较基线 +29.5%，叠加 direct-thread-switch +37.1%。适用面窄：同步线程模型（典型即 IPC）。

7.4 futex vip 插队与继承（魅族落地手机场景）

• 插队：等待队列里普通线程按 FIFO 排，前台 UX（vip）线程排不过 RT/普通线程 → 让 vip 插到 RT 之后、普通线程之前；设防饿死保护（队首普通线程等待超阈值则本次不插队）。
• 继承：vip 线程等一把被普通线程持有的用户锁时，对 owner 临时授予 vip 特权（调度/IO/内存倾斜）直到它 futex_wake，解决用户空间锁的优先级反转。实现难点：futex 协议本身不携带 owner 信息，需扩展接口在 futex_wait 时传入 futex_info（含 owner_id）。

实测（模拟用户场景）：vip 等锁最大等待时间 -70%（重载 -67%），超 100ms 次数 -25%（重载 -38%），vip 等锁总时长 -24%（重载 -21%）。

---

8 陷阱清单

陷阱	后果	对策
不校验 EAGAIN / 不循环检查	丢失唤醒、死等	WAIT 前读值传入；醒后重查条件（见 §3 示例）
假设 WAIT 不虚假返回	条件未满足就往下走	等待逻辑必须包在循环里
拿 futex(2) 直接写应用同步	丢掉用户态快速路径，得不偿失	用 pthread_mutex / std::mutex
进程间共享却没放共享内存	fork 后 COW，各睡各的	shmget/mmap(MAP_SHARED)；op 带 shared 语义
忘记 FUTEX_PRIVATE_FLAG	内核走物理地址 key，白白变慢	线程内锁一律 private
std::atomic<int> 强转 int* 传 futex	平台相关 hack（x86-64 可用）	仅教学演示，勿进生产

---

延伸阅读

• Ulrich Drepper, Futexes Are Tricky — mutex 正确性论证的第一手材料
• Franke, Russell, Kirkwood, Fuss, Futexes and Furwocks（OLS 2002）— futex 起源论文
• LWN: A futex overview and update — 经典哈希队列架构图出处
• futex(2) man page — op 全集与错误码权威定义
• 源码：kernel/futex.c（4.19）/ kernel/futex/core.c（新版拆分）；glibc nptl/pthread_mutex_lock.c、sysdeps/nptl/lowlevellock.h