基于 Linux-5.15，下文中进程和线程同指向。
一、Noraml Futex驱动简介
futex驱动提供一种内核阻塞用户空间进程的机制。futex系统调用提供了三种配对的调用接口，满足不同使用场合的，分别为 noraml futex，pi-futex，requeue-pi。本文只讲解 futex 驱动中的 noraml futex 部分。
当执行futex wait系统调用时，驱动中会判断参数 *uaddr 是否等于参数 val，若相等，则将当前线程入在等待队列中，并保证这个比较和挂入的动作是原子的。
当执行 futex wake 系统调用时，唤醒被锁阻塞的 val 个进程。参数 val3 可以指定一个位掩码，逻辑完全由用户空间控制，用来指定唤醒哪类进程，对于 FUTEX_WAIT_PRIVATE 和 FUTEX_WAKE_PRIVATE，val3 在系统调用流程中都被设置为 FUTEX_BITSET_MATCH_ANY，即唤醒所有类型的等待进程。
二、相关结构
1. struct futex_q
struct futex_q { //futex.c struct plist_node list; struct task_struct *task; spinlock_t *lock_ptr; union futex_key key; struct futex_pi_state *pi_state; struct rt_mutex_waiter *rt_waiter; union futex_key *requeue_pi_key; u32 bitset; atomic_t requeue_state; #ifdef CONFIG_PREEMPT_RT struct rcuwait requeue_wait; #endif } __randomize_layout;
会为每一个要休眠等待的waiter构建一个 futex_q 结构，并通过其 list 成员挂入到 futex_hash_bucket::chain 链表上(__queue_me()中挂入，__unqueue_futex()中移除)。
list: 这是一个优先级链表的节点，RT waiter线程对应的优先级是其线程的优先级，非RT线程对应的优先级是 MAX_RT_PRIO，即优先级范围[0, 100]。优先级数值越小优先级越高，挂入时也越靠近链表头位置。
task: waiter 进程的 task_struct 结构体，当要挂入等待链表时，在 __queue_me() 中指向即将要休眠的 waiter 线程。 TODO: 有设置为NULL的时刻吗？ 什么时候会设置为NULL?
lock_ptr: 在waiter挂入链表进行休眠时，在 queue_lock() 中会指向 futex_hash_bucket::lock 成员，__unqueue_futex() 中通过这个成员向 futex_hash_bucket 结构进行路由。这个锁是保证原子比较和阻塞的关键。在 mark_wake_futex() 中会将其赋值为NULL，是否会NULL会作为是否已经执行了唤醒流程的判断依据。
key: 此成员为hash key，通过它得到 futex_hash_bucket 结构。此成员在执行 futex wait 时在 futex_wait_setup() 中初始化，
pi_state/rt_waiter/requeue_pi_key: 不属于 Noraml Futex 范畴，暂不做分析。
bitset: 是个位掩码，用来区别要唤醒哪些线程，这完全是用户空间处理和使用的逻辑。在 futex_wait() 中赋值为来自用户空间的传参，然后将 futex_q 挂在 hb->chains 链表上，执行 futex_wake() 时从 hb->chains
链表上取下来 futex_q，然后和用户空间传下来的bitset进行比较，判断是否唤醒此进程。
requeue_state/requeue_wait: 不属于 Noraml Futex 范畴，暂不做分析。
2. union futex_key
union futex_key { struct { u64 i_seq; unsigned long pgoff; unsigned int offset; } shared; struct { union { struct mm_struct *mm; u64 __tmp; }; unsigned long address; unsigned int offset; } private; struct { u64 ptr; unsigned long word; unsigned int offset; } both; };
用户空间有很多futex lock，在内核中通过hash表进行存储，此结构为 hash key。通过 hash_futex(key) 来由 key 找到其对应的 futex_hash_bucket 结构。遍历 hb->chain 链表，使用 match_futex() 过滤出匹配 key 的 futex_q 结构，匹配上的就是此 futex 的 waiter 线程了。
这是一个联合体，各个子结构的成员的长度是一样的，get_futex_key()中根据不同传参对不同子结构的成员进行赋值，但是比较 match_futex() 函数统一使用的是 both 子结构的成员。
从 get_futex_key() 中看到 Noraml Futex的使用中取值为：
key->both.offset = uaddr % PAGE_SIZE; key->both.ptr = current->mm; // 通过 key->private.mm = current->mm; 赋值 key->both.word = uaddr - uaddr%PAGE_SIZE // 通过 key->private.address = uaddr - uaddr%PAGE_SIZE 赋值
一个 futex 锁对应一个 futex_key，而一个 futex_hash_bucket 对应多个 futex 锁，也即对应多个 futex_key。
3. struct futex_hash_bucket
struct futex_hash_bucket { atomic_t waiters; spinlock_t lock; struct plist_head chain; } ____cacheline_aligned_in_smp;
hash桶描述结构，一个hash桶中包含多个futex锁。
waiters: hash桶的 chain 链表上休眠的waiter的个数。在 queue_lock() 中加1，在 queue_unlock()/__unqueue_futex()中减1.
lock: 通过这个锁来保证 *addr 和 val 的比较与将waiter放入等待队列进行休眠的原子性。
chain: 每一个waiter的线程对应的 futex_q 结构挂在这个链表上。通过 __queue_me() 挂入，通过 __unqueue_futex() 移除。
4. futex_queues
static struct { struct futex_hash_bucket *queues; //2048个元素的数组 unsigned long hashsize;//2048 } __futex_data __read_mostly __aligned(2*sizeof(long)); #define futex_queues (__futex_data.queues) #define futex_hashsize (__futex_data.hashsize)
futex_init() 中初始化这个数组作为一个hash表。全局唯一，用于存储所有 futex 锁的waiter。从这里也可以看出来，futex 没有阻塞线程时内核是不用参与的。
三、futex wait 流程
1. 当用户空间执行类似如下系统调用时会触发 futex wait 流程
futex(state_.Address(), FUTEX_WAIT_PRIVATE, cur_state, nullptr, nullptr, 0); //art/runtime/base/mutex.cc SYSCALL_DEFINE6(futex, u32 __user *, uaddr, int, op, u32, val, const struct __kernel_timespec __user *, utime, u32 __user *, uaddr2, u32, val3) { ktime_t *tp = NULL; //会将超时时间段转换为内核时间点 ... return do_futex(uaddr, op, val, tp, uaddr2, (unsigned long)utime, val3); } long do_futex(u32 __user *uaddr, int op, u32 val, ktime_t *timeout, u32 __user *uaddr2, u32 val2, u32 val3) { int cmd = op & FUTEX_CMD_MASK; ... trace_android_vh_do_futex(cmd, &flags, uaddr2); switch (cmd) { case FUTEX_WAIT: val3 = FUTEX_BITSET_MATCH_ANY; fallthrough; case FUTEX_WAIT_BITSET: return futex_wait(uaddr, flags, val, timeout, val3); case FUTEX_WAKE: val3 = FUTEX_BITSET_MATCH_ANY; fallthrough; case FUTEX_WAKE_BITSET: return futex_wake(uaddr, flags, val, val3); ... }
futex wait 会将主要处理逻辑委托给 futex_wait()，futex wake 流程会将主要处理逻辑委托给 futex_wake().
2. futex_wake() 函数实现
static int futex_wait(u32 __user *uaddr, unsigned int flags, u32 val, ktime_t *abs_time, u32 bitset) { struct hrtimer_sleeper timeout, *to; struct restart_block *restart; struct futex_hash_bucket *hb; struct futex_q q = futex_q_init; //看来每个wait的任务都有一个对应的 futex_q 结构 int ret; if (!bitset) return -EINVAL; q.bitset = bitset; trace_android_vh_futex_wait_start(flags, bitset); /* * 启动一个定时器，超时时间为用户指定的 timeout。对timer进行初始化并将 * t->timer.function = hrtimer_wakeup; t->task = current; 超时后会调用 * hrtimer_wakeup() 并将 t->task = NULL; */ to = futex_setup_timer(abs_time, &timeout, flags, current->timer_slack_ns); retry: /* * Prepare to wait on uaddr. On success, it holds hb->lock and q * is initialized. * * 先持 hb->lock 锁，然后判断 *uaddr 中的 val的值是否改变了。 */ ret = futex_wait_setup(uaddr, val, flags, &q, &hb); if (ret) goto out; /* ---走到这里了，就表示 *uaddr == val 成立的，接下来就要让当前进程休眠了--- */ /* * queue_me and wait for wakeup, timeout, or a signal. * * 当前进程状态改为 TASK_INTERRUPTIBLE，并插入到futex等待队列，然后释放 hb->lock 锁， * 然后触发重新调度。 */ futex_wait_queue_me(hb, &q, to); /* ---下面就是唤醒逻辑了--- */ /* If we were woken (and unqueued), we succeeded, whatever. */ ret = 0; /* * 若返回0说明waiter对应的futex_q结构之前就已经从hb->chain链表上移除了(可能是 * futex wake流程中移除的)，返回1表示时这里的执行移除的。 */ if (!unqueue_me(&q)) goto out; ret = -ETIMEDOUT; /* * 若用户指定了超时时间，且超时时间已经到了(超时唤醒逻辑中会将to->task设置为NULL), * 由于超时而唤醒的。 */ if (to && !to->task) goto out; /* ---下面就是超时时间还没到的处理逻辑了--- */ /* * We expect signal_pending(current), but we might be the * victim of a spurious wakeup as well. * * 若是被信号唤醒的，retry重新走wait流程。 */ if (!signal_pending(current)) goto retry; ret = -ERESTARTSYS; if (!abs_time) goto out; /* 被意外唤醒(?), 重新走futex_wait()函数 */ restart = ¤t->restart_block; restart->futex.uaddr = uaddr; restart->futex.val = val; restart->futex.time = *abs_time; //就是上层传入的 timeout restart->futex.bitset = bitset; //就是 val3 restart->futex.flags = flags | FLAGS_HAS_TIMEOUT; //就是上层传参flag /* 使用bpf查看，是在系统调用的入口会调用它，它里面会重新调用futex_wait()函数 */ ret = set_restart_fn(restart, futex_wait_restart); out: /* 已经超时了，就去掉定时 */ if (to) { hrtimer_cancel(&to->timer); destroy_hrtimer_on_stack(&to->timer); } trace_android_vh_futex_wait_end(flags, bitset); return ret; }
函数主要逻辑是判断 *uaddr == val 后将 waiter 放在 hb->chain 链表上，然后让其休眠。
2.1. futex_wait_setup()
/* futex_wait: (uaddr, val, flags, &q, &hb) */ static int futex_wait_setup(u32 __user *uaddr, u32 val, unsigned int flags, struct futex_q *q, struct futex_hash_bucket **hb) { u32 uval; int ret; retry: /* 获取作为 futex key 保存在 q->key 中 */ ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &q->key, FUTEX_READ); if (unlikely(ret != 0)) return ret; retry_private: /* 由 q->key 得到对应的 hb, 这里面会执行 hb->lock 的上锁操作并提前对 hb->waiters++ */ *hb = queue_lock(q); ret = get_futex_value_locked(&uval, uaddr); //就是执行 uval=*uaddr; if (ret) { //成功返回0，正常不走这里，相当于容错处理 queue_unlock(*hb); ret = get_user(uval, uaddr); if (ret) return ret; if (!(flags & FLAGS_SHARED)) goto retry_private; goto retry; } /* * 如果当期uaddr指向的值不等于val，即说明其他进程修改了uaddr指向的值， * 等待条件不再成立，不用阻塞直接返回。 * * 这一般是一个不常发生的情况。 */ if (uval != val) { queue_unlock(*hb); //释放 hb->lock 锁并将 hb->waiters--; ret = -EWOULDBLOCK; } return ret; }
这个函数主要用来判断是否需要对当前线程进程阻塞。
2.2. futex_wait_queue_me()
/* futex_wait: (hb, &q, to) 执行这个函数前 hb_>lock 必须得是锁定的 */ static void futex_wait_queue_me(struct futex_hash_bucket *hb, struct futex_q *q, struct hrtimer_sleeper *timeout) { /* * 翻译：保证在另一个任务唤醒它之前设置任务状态。 set_current_state() 是使用 * smp_store_mb() 实现的，并且 queue_me() 在完成时调用 spin_unlock() ， * 既序列化对哈希列表的访问，又强制另一个内存屏障。 */ set_current_state(TASK_INTERRUPTIBLE); /* * 将当期进程（q封装）插入到hb->chain等待队列中去，然后释放了自旋锁 hb->lock。 * 优先级链表，会挂入到优先级对应位置。 */ queue_me(q, hb); /* Arm the timer 启动定时器 */ if (timeout) hrtimer_sleeper_start_expires(timeout, HRTIMER_MODE_ABS); /* * If we have been removed from the hash list, then another task * has tried to wake us, and we can skip the call to schedule(). */ /* 对其的移除需要是持有 hb->lock 自旋锁才是安全的，因为上面有释放自旋锁，可能会发生抢占。 TODO: 确认一下 */ if (likely(!plist_node_empty(&q->list))) { /* * 翻译: 如果计时器已经过期，则 current 就已经被标记为需要重新调度了。 * 这里仅在没有指定超时时间或尚未到期时才调用 schedule。 * timeout->task 不为空表示超时时间还没过期 */ if (!timeout || timeout->task) { trace_android_vh_futex_sleep_start(current); freezable_schedule(); } } /* 这个操作不多余吗？ */ __set_current_state(TASK_RUNNING); }
该函数主要作用是将当前这个waiter进程挂入 hb->chain 链表上，并让其休眠。
2.2.1. queue_me()
static inline void queue_me(struct futex_q *q, struct futex_hash_bucket *hb) __releases(&hb->lock) { __queue_me(q, hb); spin_unlock(&hb->lock); //释放 hb->lock锁 } static inline void __queue_me(struct futex_q *q, struct futex_hash_bucket *hb) { int prio; bool already_on_hb = false; /* * 对于RT线程，其prio就是其优先级，对于非RT线程，prio=MAX_RT_PRIO. 也就是说这个优先级是0--100。 * 因此，默认情况下，所有 RT 线程按优先级顺序首先被唤醒，非RT线程按 FIFO 顺序最后唤醒。 */ prio = min(current->normal_prio, MAX_RT_PRIO); plist_node_init(&q->list, prio); trace_android_vh_alter_futex_plist_add(&q->list, &hb->chain, &already_on_hb); if (!already_on_hb) plist_add(&q->list, &hb->chain); /* currrent是即将要休眠的waiter */ q->task = current; }
此函数主要作用是将当前即将要进入休眠 waiter 线程按其优先级挂入到 hb->chain 链表。
2.3. unqueue_me()
被唤醒后 waiter 线程继续执行，执行 unqueue 流程。
static int unqueue_me(struct futex_q *q) { spinlock_t *lock_ptr; int ret = 0; /* In the common case we don't take the spinlock, which is nice. */ retry: /* * 翻译：q->lock_ptr 可以在这个读取和后面的 spin_lock 之间改变。使用 * READ_ONCE 禁止编译器重新加载 q->lock_ptr 和优化 lock_ptr 超出以下逻辑。 * * mark_wake_futex 会将 q->lock_ptr 赋值为 NULL。 */ lock_ptr = READ_ONCE(q->lock_ptr); if (lock_ptr != NULL) { spin_lock(lock_ptr); //指向的是 hb->lock，就是 spin_lock(&hb->lock) /* * 翻译：q->lock_ptr 可以在读取它和 spin_lock() 之间改变，导致 * 我们获取错误的锁。 这更正了竞态条件。 * * 翻译：推理是这样的：如果我们有错误的锁，q->lock_ptr 必须在读取它 * 和 spin_lock() 之间发生变化（可能多次）。 它可以在 spin_lock() * 之后再次更改，但前提是它在 spin_lock() 之前已经更改。 但是，它 * 不能变回原始值。 因此我们可以检测我们是否获得了正确的锁。 */ if (unlikely(lock_ptr != q->lock_ptr)) { //应该小概率出现，当做容错处理 spin_unlock(lock_ptr); goto retry; } /* 将这个futex_q从 hb->chain 上移除，并将 hb->waiters-- */ __unqueue_futex(q); BUG_ON(q->pi_state); spin_unlock(lock_ptr); //就是 spin_lock(&hb->lock) ret = 1; } return ret; }
作用是将被唤醒后的 waiter 对应的 futex_q 从 futex_hash_bucket 中移除，若在执行这个函数前已经是移除的了，就返回0，若在这个函数中进行的移除，返回1。
2.4. set_restart_fn()
这个函数设置了一个回调，futex_wait_restart() 中会重新执行 futex_wait()，使用 bpftrace 查看其调用路径：
bpftrace -e 'kprobe:futex_wait_restart{printf("stack: %s\n", kstack());}' stack: futex_wait_restart+0 el0_svc_common+212 el0_svc+40 el0_sync_handler+140 el0_sync+436
对于64位应用程序在用户模式下生成的同步异常,入口是 el0_sync，对于32位应用程序在用户模式下生成的同步异常,入口是 el0_sync_compat
ARM64处理器把系统调用划分到同步异常，在异常级别1的异常向量表中，系统调用的入口有两个:
(1) 如果是64位应用程序执行系统调用指令svc，系统调用入口是 el0_sync.
(2) 如果是32位应用程序执行系统调用指令svc，系统调用入口是 el0_sync_compat.
以 el0_sync 为例，读取异常寄存器 esr_el1，解析异常症状寄存器的异常类型字段，如果是系统调用，跳转到负责执行系统调用的el0_svc。el0_svc 根据 sys_call_table 和调用号执行相应的系统调用函数。
应该是执行了下面这个系统调用：
SYSCALL_DEFINE0(restart_syscall) //signal.c { struct restart_block *restart = ¤t->restart_block; return restart->fn(restart); }
四、futex wake 流程
1. 当用户空间执行类似如下系统调用时会触发 futex wake 流程
futex(state_.Address(), FUTEX_WAKE_PRIVATE, kWakeAll, nullptr, nullptr, 0); //art/runtime/base/mutex.cc
2. futex 会将wake流程委托给 futex_wake() 函数。
/* * Wake up waiters matching bitset queued on this futex (uaddr). * * do_futex: (uaddr, flags, val, val3) * 参数： * uaddr: 用户空间传的futex字 * nr_wake: 用户传参的val，表示此次要唤醒的个数 * bitset: 上层传参 val3 = FUTEX_BITSET_MATCH_ANY */ static int futex_wake(u32 __user *uaddr, unsigned int flags, int nr_wake, u32 bitset) { struct futex_hash_bucket *hb; struct futex_q *this, *next; union futex_key key = FUTEX_KEY_INIT; int ret; int target_nr; DEFINE_WAKE_Q(wake_q); //struct wake_q_head wake_q if (!bitset) return -EINVAL; /* 1. 先得到 futex_key(根据uaddr、flags、读写标志来获取key), key和hash桶的对应关系是一对多的 */ ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &key, FUTEX_READ); if (unlikely(ret != 0)) return ret; /* 2. 将 futex_key 转换为hash桶 futex_hash_bucket */ hb = hash_futex(&key); /* Make sure we really have tasks to wakeup */ /* 返回 hb->waiters, 这个判断和赋值都在 hb->lock 锁之外 */ if (!hb_waiters_pending(hb)) return ret; /* 3. 上锁，和wait流程互斥 */ spin_lock(&hb->lock); trace_android_vh_futex_wake_traverse_plist(&hb->chain, &target_nr, key, bitset); plist_for_each_entry_safe(this, next, &hb->chain, list) { /* 必须进行这个过滤，因为同一个 hb->chain 上还挂有其它futex锁 */ if (match_futex (&this->key, &key)) { /* 这两个可能标识是其它机制 */ if (this->pi_state || this->rt_waiter) { ret = -EINVAL; break; } /* Check if one of the bits is set in both bitsets * normal-futex 传的是 FUTEX_BITSET_MATCH_ANY, 不会为真 */ if (!(this->bitset & bitset)) continue; trace_android_vh_futex_wake_this(ret, nr_wake, target_nr, this->task); /* 将任务挂到这个 wake_q 待唤醒队列上 */ mark_wake_futex(&wake_q, this); /* 这次最多唤醒多少个等待的任务 */ if (++ret >= nr_wake) break; } } /* 4. 已经挂在待唤醒队列上后释放锁，后续会执行唤醒 */ spin_unlock(&hb->lock); /* 唤醒(多个)等待的任务 */ wake_up_q(&wake_q); trace_android_vh_futex_wake_up_q_finish(nr_wake, target_nr); return ret; }
2.1. mark_wake_futex()
/* * futex_wake: (&wake_q, this) 参数是待唤醒等待队列头，和waiter对应的 futex_q 结构 * 必须要在持有 hb->lock 的条件下调用这个函数 */ static void mark_wake_futex(struct wake_q_head *wake_q, struct futex_q *q) { struct task_struct *p = q->task; if (WARN(q->pi_state || q->rt_waiter, "refusing to wake PI futex\n")) return; /* 要将p移动到等待队列头 wake_q，随后进行唤醒，别释放了 */ get_task_struct(p); /* 从 hb->chain 上移除，然后将 hb->waiters--*/ __unqueue_futex(q); /* * 翻译：waiter可以在 q->lock_ptr = NULL 写入后立即释放 futex_q, 不持有任何锁。 * 例如，在虚假唤醒的情况下这是可能的。 这里需要一个内存屏障来防止对 lock_ptr * 的后续存储领先于 __unqueue_futex() 中的 plist_del。 */ smp_store_release(&q->lock_ptr, NULL); /* * Queue the task for later wakeup for after we've released the hb->lock. */ wake_q_add_safe(wake_q, p); }
五、总结
1. futex wait 流程可以简单总结为
a. 获取 hb->lock 自旋锁。
b. 检测 *uaddr 是否等于 val，如果不相等则会立即返回。
c. 将进程状态设置为 TASK_INTERRUPTIBLE。
d. 将当前 waiter 进程插入到等待队列中。
e. 释放 hb->lock 自旋锁。
f. 开启定时任务，当超时还没被唤醒时，将进程唤醒
g. 挂起当前进程
2. futex wake 流程可以简单总结为
a. 找到 uaddr 对应的 futex_hash_bucket.
b. 获取 hb->lock 自旋锁。
c. 遍历 hb->chain 链表，找到 uaddr 对应的 waiters(futex_q)节点.
d. 将 waiters 移动到 wake_q 待唤醒链表上。
e. 释放 hb->lock 自旋锁。
f. 唤醒所有的 waiters 线程。
2. 通过 hb->lock 自旋锁来保证原子性。
原文地址：http://www.cnblogs.com/hellokitty2/p/16897606.html
