struct mutex {
    /* 1: unlocked, 0: locked, negative: locked, possible waiters */
    atomic_t		count;
    spinlock_t		wait_lock;
    struct list_head	wait_list;
    struct thread_info	*owner;
};

typedef struct {
    int counter;
} atomic_t;

typedef struct spinlock {
    union {
        struct raw_spinlock rlock;
    }
} spinlock_t;

typedef struct raw_spinlock {
    arch_spinlock_t raw_lock;
} raw_spinlock_t;

typedef struct arch_spinlock {
    unsigned int slock;
} arch_spinlock_t;

struct list_head {
    struct list_head *next, *prev;
};

struct thread_info {
    struct task_struct	*task;		/* main task structure */
    struct exec_domain	*exec_domain;	/* execution domain */
    __u32			flags;		/* low level flags */
    __u32			status;		/* thread synchronous flags */
    __u32			cpu;		/* current CPU */
    int			preempt_count;	/* 0 => preemptable,
                           <0 => BUG */
    mm_segment_t		addr_limit;
    struct restart_block    restart_block;
    void __user		*sysenter_return;
    int			uaccess_err;
};

struct rq {
    struct task_struct *curr, *idle, *stop;
};

void __mutex_init(struct mutex *lock, const char *name, struct lock_class_key *key) {
    // 将 count 设为 1
    atomic_set(&lock->count, 1);
//  spin_lock_init(&lock->wait_lock);
    do {
        spinlock_check(&lock->wait_lock);
        do { 
            *(&(&lock->wait_lock)->rlock) = (raw_spinlock_t) {
                .raw_lock={0},
            }; 
        } while (0);
    }
    while (0)
        
    INIT_LIST_HEAD(&lock->wait_list);
        
//  mutex_clear_owner(lock);
    lock->owner = NULL;

    debug_mutex_init(lock, name, key);
}

static inline void INIT_LIST_HEAD(struct list_head *list) {
    list->next = list;
    list->prev = list;
}

void __sched mutex_lock(struct mutex *lock) {
//  might_sleep();
    do { _cond_resched(); } while (0);
    // 锁定快速路径是从“解锁”到“锁定”状态的 1->0 转换。
//  __mutex_fastpath_lock(&lock->count, __mutex_lock_slowpath);
    do {
        unsigned long dummy;
        ({
            atomic_t *__dummy;
            typeof(&lock->count) __dummy2;
            (void) (&__dummy == &__dummy2);
            1;
        });
        ({
            typeof(
            void(*)
            (atomic_t * ))__tmp = __mutex_lock_slowpath;
            (void) __tmp;
        });
        asm volatile(".section .smp_locks,\"a\"\n" ".balign 4\n" ".long 671f - .\n" ".previous\n" "671:" "\n\t"
                        "lock; "
                        "decl (%%rdi)\n"
                        "jns 1f     \n"
                        "call " "__mutex_lock_slowpath" "\n"
                        "1:"
                        :"=D"(dummy)
                        :"D"(&lock->count)
                        :"rax", "rsi", "rdx", "rcx", "r8", "r9", "r10", "r11", "memory");
    }while (0);
    
//  mutex_set_owner(lock);
    lock->owner = current_thread_info();
}

static __used noinline void __sched __mutex_lock_slowpath(atomic_t *lock_count){
//  struct mutex *lock = container_of(lock_count, struct mutex, count);
    struct mutex *lock = ({
        const typeof(((struct mutex *) 0)->count) *__mptr = (lock_count);
        (struct mutex *) ((char *) __mptr - ((size_t) &((struct mutex *) 0)->count));
    });
    __mutex_lock_common(lock, TASK_UNINTERRUPTIBLE, 0, _RET_IP_);
}

static inline int __sched __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
	       	unsigned long ip){
    struct task_struct *task = get_current();
    struct mutex_waiter waiter;
    unsigned long flags;

//  preempt_disable();
//  mutex_acquire(&lock->dep_map, subclass, 0, ip);
    
    // 乐观自旋锁
    // 当我们发现没有挂起的等待者并且锁所有者当前在（不同的）CPU 上运行时，我们会尝试自旋获取。
    // 理由是如果锁的所有者正在运行，它很可能很快就会释放锁。
    // 由于这需要锁的拥有者，而且这个互斥锁实现不会在锁字段中原子地跟踪拥有者，我们需要非原子地跟踪它。
    // 我们不能对 DEBUG_MUTEXES 执行此操作，因为它依赖于 wait_lock 来序列化所有内容。
    for (;;) {
        struct thread_info *owner;
        // 判断是否获得了大内核锁
        if (unlikely(current->lock_depth >= 0))
            break;
        owner = ACCESS_ONCE(lock->owner);
        if (owner && !mutex_spin_on_owner(lock, owner))
            break;
        // cmpxchg(&lock->count->counter, old, new)
        // 作用是期望 counter 是 1，然后设置为。和信号量有点类似，只是信号量只有1.
        if (atomic_cmpxchg(&lock->count, 1, 0) == 1) { // 能把信号量从 1 变为 0,说明 down 操作执行成功
//          lock_acquired(&lock->dep_map, ip);
//          mutex_set_owner(lock);
            // lock 成功
            lock->owner = current_thread_info();
//          preempt_enable();
            return 0;
        }
        // 当没有所有者时，我们可能会在所有者获取锁和设置所有者字段之间进行抢占。 
        // 如果我们是一个 RT 任务将 live-lock，因为我们不会让所有者完成。 
        if (!owner && (need_resched() || rt_task(task)))
            break;
        
//      arch_mutex_cpu_relax();
        cpu_relax();
    }
    // 到这一步，就要被迫进入等待队列了
    // 自旋获取等待锁，因为只能有一个core 修改 lock->wait_list
//  spin_lock_mutex(&lock->wait_lock, flags);
    do {
        spin_lock(&lock->wait_lock);
        (void) (flags);
    }
    while (0)
    // waiter就是自己，将自己添加到等待队列的队尾
    list_add_tail(&waiter.list, &lock->wait_list);
    // task 就是当前进程
    waiter.task = task;
    // 将 -1 赋值给 &lock->count，返回 &lock->count 的原值
    if (atomic_xchg(&lock->count, -1) == 1) // 应该是再尝试一次获取锁
        goto done;
    
//  lock_contended(&lock->dep_map, ip);
    
    for (;;) {
        // 让我们再次尝试获取锁 - 即使我们第一次到达这里（在未能获取锁后不久），
        // 这也是必需的，以确保一旦解锁我们就会得到唤醒。 
        // 稍后，如果我们休眠，这就是给我们锁的操作。 
        // 我们将其 xchg 为 -1，这样当我们释放锁时，我们可以正确唤醒其他等候者： 
        if (atomic_xchg(&lock->count, -1) == 1)
            break;
        if (unlikely(signal_pending_state(state, task))) {
            // 感觉像是收到了一个信号，当前进程被迫关闭了，所以需要从等待队列移除
            // 从等待队列移除
            mutex_remove_waiter(lock, &waiter, task_thread_info(task));
//          mutex_release(&lock->dep_map, 1, ip);
//            spin_unlock_mutex(&lock->wait_lock, flags);
            do {
                // 释放持有的 wait_lock
                spin_unlock(&lock->wait_lock);
                (void) (flags);
            }
            while (0);

//          debug_mutex_free_waiter(&waiter);
//          preempt_enable();
            // 中断系统调用    
            return -EINTR;
        }
        // 修改任务的状态为 TASK_UNINTERRUPTIBLE
//		__set_task_state(task, state);
        do { (task)->state = (state); } while (0);
        
        // 不要持有这个锁，去 sleep
//      spin_unlock_mutex(&lock->wait_lock, flags);
        do {
            // 释放持有的 wait_lock
            spin_unlock(&lock->wait_lock);
            (void) (flags);
        }
        while (0);
        
//      preempt_enable_no_resched();
        // 把 cpu 的使用权交出去
        schedule();
//      preempt_disable();
        // 既然被唤醒了，那么再尝试一次。尝试前先强占 wait_lock 
        spin_lock_mutex(&lock->wait_lock, flags);
    }
done:
//  lock_acquired(&lock->dep_map, ip);
    // 取到了锁，此时还占有着 wait_lock。所以可以直接把自己从队列中删除
    mutex_remove_waiter(lock, &waiter, current_thread_info());
    // 设置自己为锁的持有者
    mutex_set_owner(lock);

    // 如果当前没有等待者了，就把信号量置为0
    if (likely(list_empty(&lock->wait_list)))
        atomic_set(&lock->count, 0);
    
    // 释放 wait_lock
    spin_unlock_mutex(&lock->wait_lock, flags);

//    debug_mutex_free_waiter(&waiter);
//    preempt_enable();

    return 0;
}

int mutex_spin_on_owner(struct mutex *lock, struct thread_info *owner) {
    unsigned int cpu;
	struct rq *rq;

	if (!sched_feat(OWNER_SPIN))
		return 0;
    cpu = owner->cpu;
    // cpu索引不能超过 cpu 上限
    if (cpu >= nr_cpumask_bits)
		return 0;
    if (!cpu_online(cpu))
		return 0;
    // 获取 cpu 的 runqueues
    rq = cpu_rq(cpu);
    for (;;) {
        if (lock->owner != owner) { // 如果我不持有锁
            // 其他人正在持有锁
            if (lock->owner)
				return 0;
            // 没有人在持有锁
			break;
        }
        // 现在锁的持有者是我，但是当前 cpu 的 rq 中 curr 不是我，而且需要重新安排，则自旋失败。
        // 如果当前 cpu 的 rq 中 curr 是我，则再次自旋。
        
        // 条件1:我是否在 runqueues 中，且当前是我在执行
        // 条件2：是否需要重新安排
        // 总结：Is that owner really running on that cpu? 我是否真的运行在这个 cpu 上。
        if (task_thread_info(rq->curr) != owner || need_resched())
			return 0;

//      arch_mutex_cpu_relax();
        // cpu_relax()调用会降低CPU的能量消耗或者让位于超线程双处理器；
        // #define cpu_relax()	asm volatile("rep; nop" ::: "memory");
        cpu_relax(); 
        
    }
    // 没有人持有锁，自旋成功
    return 1;
}

void __sched mutex_unlock(struct mutex *lock) {
    // 解锁快速路径是从“锁定”状态到“解锁”状态的 0->1 转换：
    // 启用调试后，我们不能在时间之前清除所有者，将始终采用慢速路径，
    // 并且在验证所有者字段确实是当前字段后清除它。
//  mutex_clear_owner(lock);
    lock->owner = NULL;
//	__mutex_fastpath_unlock(&lock->count, __mutex_unlock_slowpath);
    do {
        unsigned long dummy;
        ({
            atomic_t *__dummy;
            typeof(&lock->count) __dummy2;
            (void) (&__dummy == &__dummy2);
            1;
        });
        ({
        typeof(
            void(*)
            (atomic_t * ))__tmp = __mutex_unlock_slowpath;
            (void) __tmp;
        });
        asm volatile(".section .smp_locks,\"a\"\n" ".balign 4\n" ".long 671f - .\n" ".previous\n" "671:" "\n\t"
                     // 锁缓存行                                                                                     
                     "lock; "
                     // 将 &lock->count 自增
                     "incl (%%rdi)\n"
                     "jg 1f\n"
                     "call " "__mutex_unlock_slowpath" "\n"
                     "1:"
                     :"=D"(dummy)
                     :"D"(&lock->count)
                     :"rax", "rsi", "rdx", "rcx", "r8", "r9", "r10", "r11", "memory");
    }while (0);
}

static __used noinline void __mutex_unlock_slowpath(atomic_t *lock_count) {
//	__mutex_unlock_common_slowpath(lock_count, 1);
//    struct mutex *lock = container_of(lock_count, struct mutex, count);
    struct mutex *lock = ({
        const typeof(((struct mutex *)0)->count) *__mptr = (lock_count);
        (struct mutex *)((char *)__mptr - ((size_t) & ((struct mutex *)0)->count));
    })
    unsigned long flags;
    // 自旋的方式获取 wait_lock
    spin_lock_mutex(&lock->wait_lock, flags);
//    mutex_release(&lock->dep_map, nested, _RET_IP_);
//    debug_mutex_unlock(lock);
    // 一些架构在快速路径失败的情况下保持解锁状态，而另一些架构则需要保持锁定状态。
    // 在后一种情况下，我们必须在这里解锁
    if (__mutex_slowpath_needs_to_unlock())
        // 释放信号量
        atomic_set(&lock->count, 1);
    
    if (!list_empty(&lock->wait_list)) { // 当前有等待者
        // 获取排第一的等待者
        struct mutex_waiter *waiter =
            list_entry(lock->wait_list.next, struct mutex_waiter, list);

//        debug_mutex_wake_waiter(lock, waiter);
        // 唤醒等待的进程
        wake_up_process(waiter->task);
    }
    // 释放等待锁
    spin_unlock_mutex(&lock->wait_lock, flags);
}