struct futex_q {
	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;
};

SYSCALL_DEFINE6(futex, u32 __user *, uaddr, int, op, u32, val,
		struct timespec __user *, utime, u32 __user *, uaddr2,
		u32, val3)
{
    // 省略
    return do_futex(uaddr, op, val, tp, uaddr2, val2, val3);
}

long do_futex(u32 __user *uaddr, int op, u32 val, ktime_t *timeout,
		u32 __user *uaddr2, u32 val2, u32 val3)
{
    int ret = -ENOSYS, cmd = op & FUTEX_CMD_MASK;
    switch (cmd) {
        case FUTEX_WAIT:
            ret = futex_wait(uaddr, flags, val, timeout, val3);
            break;
        case FUTEX_WAKE:
            ret = futex_wake(uaddr, flags, val, val3);
            break;
    }
    return ret;
}

static int futex_wait(u32 __user *uaddr, unsigned int flags, u32 val,
		      ktime_t *abs_time, u32 bitset)
{
retry:
    // 判断 uaddr 的最新值是否等于 val
    // - 相等：ret == 0，并对 uaddr 对应的 bucket 加锁
    // - 不等：说明信号量满足要求，所以直接返回。
    ret = futex_wait_setup(uaddr, val, flags, &q, &hb);
    // 如果返回值 > 0，大概率是 uaddr 对应的值 不是 val。
    // 直白的说，就是如果 uaddr == val，那么就应该去等待,否则不需要等待
    if (ret) 
		goto out;
    // -----------------------
    // 进入队列等待，直到被其他 task 通过 futex_wake 唤醒
    futex_wait_queue_me(hb, &q, to);
    ret = 0;
    // 正常来说既然被唤醒了，应该就不在队列中了。因为会被唤醒者移除队列
	/* unqueue_me() drops q.key ref */
	if (!unqueue_me(&q))
		goto out;
    // -----------------------
    // 代码省略
out:
	if (to) {
		hrtimer_cancel(&to->timer);
		destroy_hrtimer_on_stack(&to->timer);
	}
	return ret;
}

static int unqueue_me(struct futex_q *q) {
    spinlock_t *lock_ptr;
    int ret = 0;
retry:
	lock_ptr = q->lock_ptr;
	barrier();
    // 在其他 task 调用了 wake 之后，会顺带把 lock_ptr 置为 null
	if (lock_ptr != NULL) {
		spin_lock(lock_ptr);
		// 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;
		}
		__unqueue_futex(q);
		spin_unlock(lock_ptr);
		ret = 1;
	}

	drop_futex_key_refs(&q->key);
	return ret;
}

static void futex_wait_queue_me(struct futex_hash_bucket *hb, struct futex_q *q,
				struct hrtimer_sleeper *timeout)
{
    set_current_state(TASK_INTERRUPTIBLE);
//    queue_me(q, hb);
    int prio;
    // 用于注册此元素的优先级是
    // - 实时线程的实际线程优先级（即优先级低于 MAX_RT_PRIO 的线程）
    // - 或 MAX_RT_PRIO 用于非 RT 线程。 因此，所有 RT 线程按优先级顺序首先被唤醒，其他线程按 FIFO 顺序最后唤醒。
    prio = min(current->normal_prio, MAX_RT_PRIO);
    // 初始化
    plist_node_init(&q->list, prio);
    // 扔到队尾
	plist_add(&q->list, &hb->chain);
    // 赋值 task
	q->task = current;
    // 解锁 futex_hash_bucket，在 futex_wait_setup 执行了 spin_lock
	spin_unlock(&hb->lock);
    
    if (likely(!plist_node_empty(&q->list))) {
        if (!timeout || timeout->task)
            // 交出CPU 时间片，等待被他人唤醒
			schedule();
    }
    // 被唤醒
    __set_current_state(TASK_RUNNING);
}

static int futex_wait_setup(u32 __user *uaddr, u32 val, unsigned int flags,
			   struct futex_q *q, struct futex_hash_bucket **hb)
{
retry:
    // 获取锁对应的 key
	ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &q->key);
	if (unlikely(ret != 0))
		return ret;
retry_private:
    // 对 futex 加锁
	*hb = queue_lock(q);
    // uval 是 uaddr 的最新值
	ret = get_futex_value_locked(&uval, uaddr);
//	if (ret) {
//		queue_unlock(q, *hb);
//		ret = get_user(uval, uaddr);
//		if (ret)
//			goto out;
//		if (!(flags & FLAGS_SHARED))
//			goto retry_private;
//		put_futex_key(&q->key);
//		goto retry;
//	}
    // 最新值与期望值不一致
	if (uval != val) {
        // futex 解锁
		queue_unlock(q, *hb);
		ret = -EWOULDBLOCK;
	}

out:
	if (ret)
		put_futex_key(&q->key);
	return ret;    
}

static int get_futex_value_locked(u32 *dest, u32 __user *from)
{
	int ret;

	pagefault_disable();
    // 原子地把 from 地址的值拷贝到 dest 地址中，且限定长度为 32 位
	ret = __copy_from_user_inatomic(dest, from, sizeof(u32));
    // ret == 0 表示操作成功
	pagefault_enable();

	return ret ? -EFAULT : 0;
}

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;
	struct plist_head *head;
	union futex_key key = FUTEX_KEY_INIT;
    int ret;
    // 主要作用是根据 uaddr 找到对应的 bucket 的 key
    ret = get_futex_key(uaddr, flags & FLAGS_SHARED, &key);
	if (unlikely(ret != 0))
		goto out;
    // 获取对应的 bucket
	hb = hash_futex(&key);
    // 对该 bucket 上自旋锁
	spin_lock(&hb->lock);
    head = &hb->chain;
    plist_for_each_entry_safe(this, next, head, list) {
        // 校验key 是否匹配，避免唤醒错误的等待者
		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 */
            // 唤醒的过滤条件，只有满足要求的 task 才会被唤醒
			if (!(this->bitset & bitset))
				continue;
            // 唤醒这个等待中的 task
			wake_futex(this);
            // nr_wake 是本次唤醒的 task 个数
			if (++ret >= nr_wake)
				break;
		}
	}
    // 解锁
    spin_unlock(&hb->lock);
	put_futex_key(&key);
out:
    return ret;
}

static void wake_futex(struct futex_q *q)
{
    struct task_struct *p = q->task;
    get_task_struct(p);
    // 从队列中移除
    __unqueue_futex(q);
//    smp_wmb();
    __asm__ __volatile__("" ::: "memory")
    // 这样就可以保证被唤醒的task可以正常运行
	q->lock_ptr = NULL;
    // 唤醒等待者
	wake_up_state(p, TASK_NORMAL);
	put_task_struct(p);
}

static inline struct futex_hash_bucket *queue_lock(struct futex_q *q)
	__acquires(&hb->lock)
{
	struct futex_hash_bucket *hb;
    // 获取对应的 bucket
	hb = hash_futex(&q->key);
    // 当前 futex 中的锁是 bucket 对应的锁
	q->lock_ptr = &hb->lock;
    // 自旋上锁
	spin_lock(&hb->lock);
	return hb;
}

static inline void
queue_unlock(struct futex_q *q, struct futex_hash_bucket *hb)
	__releases(&hb->lock)
{
	spin_unlock(&hb->lock);
}