#include <linux/futex.h>
#include <sys/syscall.h>

int syscall(SYS_futex, uint32_t *uaddr, int futex_op, uint32_t val, 
            const struct timespec *timeout, uint32_t *uaddr2, uint32_t val3);

// 用戶態(tài)嘗試原子交換
if (atomic_cas(uaddr, 0, 1) == success) return; // 成功獲得鎖
// 失敗則進(jìn)入內(nèi)核等待
syscall(SYS_futex, uaddr, FUTEX_WAIT, 1, NULL, NULL, 0);

atomic_set(uaddr, 0);                   // 先釋放鎖
syscall(SYS_futex, uaddr, FUTEX_WAKE, 1); // 喚醒一個(gè)等待線程

// 偽代碼：用戶態(tài)鎖的加鎖流程
void pthread_mutex_lock(pthread_mutex_t *mutex) {
    // 1. 用戶態(tài)快速路徑（無競(jìng)爭(zhēng)）
    if (atomic_cas(&mutex->state, UNLOCKED, LOCKED) == success) 
        return;

    // 2. 慢速路徑：通過 futex 請(qǐng)求內(nèi)核協(xié)助
    while (true) {
        if (atomic_cas(&mutex->state, UNLOCKED, LOCKED_WAITERS) == success) 
            return;
        
        // 調(diào)用 futex 讓內(nèi)核阻塞線程
        syscall(SYS_futex, &mutex->state, FUTEX_WAIT_PRIVATE, LOCKED_WAITERS, NULL);
    }
}

// 內(nèi)核源碼（kernel/locking/mutex.c）
void __sched mutex_lock(struct mutex *lock)
{
	might_sleep();

	if (!__mutex_trylock_fast(lock)) // 1. 快速嘗試
		__mutex_lock_slowpath(lock); // 2. 慢路徑：內(nèi)核調(diào)度介入
}

  用戶程序
     │
     ├── 無競(jìng)爭(zhēng) → 用戶態(tài)原子操作（極快）
     │
     └── 有競(jìng)爭(zhēng) → 調(diào)用 futex 陷入內(nèi)核
                 │
                 ▼
              內(nèi)核調(diào)度器
                 │
                 ├── 掛起線程（FUTEX_WAIT）
                 │
                 └── 喚醒線程（FUTEX_WAKE）

// 線程A
data = 42;        // 寫數(shù)據(jù)
flag = 1;         // 寫標(biāo)志位

// 線程B
while (flag != 1); // 等待標(biāo)志位
print(data);       // 讀取數(shù)據(jù)

ldxr x0, [x1]    ; 獨(dú)占加載：標(biāo)記地址 x1 為當(dāng)前 CPU 獨(dú)占
stxr w2, x3, [x1] ; 獨(dú)占存儲(chǔ)：若標(biāo)記未失效則寫入 x3 → [x1]，結(jié)果狀態(tài)存入 w2

// 原子比較交換（用戶態(tài)偽代碼）
//stxr僅在標(biāo)記未被破壞時(shí)執(zhí)行寫入，否則失敗并重試。這種“嘗試-檢測(cè)-重試”機(jī)制確保了“讀-改-寫”操作的原子性
bool atomic_cas(uint64_t *ptr, uint64_t old, uint64_t new) {
    uint64_t tmp;
    int status;
    do {
        asm volatile("ldxr %0, [%2]\n"   // 獨(dú)占加載
                     "cmp %0, %3\n"       // 比較舊值
                     "b.ne 1f\n"          // 不相等則跳轉(zhuǎn)
                     "stxr %w1, %4, [%2]\n" // 嘗試存儲(chǔ)新值
                     "1:"
                     : "=&r"(tmp), "=&r"(status)
                     : "r"(ptr), "r"(old), "r"(new));
    } while (status != 0); // 失敗則重試
    return (tmp == old);
}

ldaddal x0, x1, [x2]  ; 原子操作：[x2] = [x2] + x0, x1 = 原值

// 原子加法（用戶態(tài)）
__atomic_add_fetch(&counter, 1, __ATOMIC_SEQ_CST);

std::atomic<int> counter;
counter.fetch_add(1, std::memory_order_relaxed);

dmb ish  ; 數(shù)據(jù)內(nèi)存屏障（Inner Shareable Domain）

// 內(nèi)核原子加法（源碼片段：arch/arm64/include/asm/atomic_ll_sc.h）
static inline void atomic_add(int i, atomic_t *v) {
    unsigned long tmp;
    asm volatile("http:// atomic_add\n"
        "1: ldxr %w0, %2\n"        // 獨(dú)占加載
        "add %w0, %w0, %w3\n"      // 執(zhí)行加法
        "stxr %w1, %w0, %2\n"      // 條件存儲(chǔ)
        "cbnz %w1, 1b"             // 失敗則重試
        : "=&r" (tmp), "=&r" (tmp2)
        : "Q" (v->counter), "Ir" (i));
}

Atomic Add (user): 28 ns
Futex Lock (uncontended): 1200 ns

// 偽代碼：用戶態(tài)互斥鎖實(shí)現(xiàn)（基于 futex）
void mutex_lock(mutex_t *m) {
    // 1. 用戶態(tài)快速路徑（無競(jìng)爭(zhēng)）
    if (atomic_cas(&m->lock, 0, 1) == success) 
        return;

    // 2. 慢速路徑：標(biāo)記有等待者，并陷入內(nèi)核阻塞
    atomic_set(&m->lock, 2); // 設(shè)置等待標(biāo)志
    syscall(SYS_futex, &m->lock, FUTEX_WAIT_PRIVATE, 2, NULL);
}

void mutex_unlock(mutex_t *m) {
    // 1. 釋放鎖并檢查是否有等待者
    if (atomic_swap(&m->lock, 0) == 2) { // 原值為2表示有等待者
        // 2. 喚醒一個(gè)等待線程
        syscall(SYS_futex, &m->lock, FUTEX_WAKE_PRIVATE, 1);
    }
}

// 偽代碼：用戶態(tài)自旋鎖（純?cè)硬僮鳎?
void spin_lock(spinlock_t *lock) {
    while (true) {
        // 嘗試獲取鎖：0表示空閑，1表示占用
        if (atomic_exchange(&lock->flag, 1) == 0) 
            return;
        
        // ARM64優(yōu)化：降低CPU功耗
        asm volatile("wfe" ::: "memory"); // Wait For Event
    }
}

void spin_unlock(spinlock_t *lock) {
    atomic_store(&lock->flag, 0);
    asm volatile("sev" ::: "memory"); // Send Event
}

if C < S : 選自旋鎖（避免切換開銷）
if C > S : 選互斥鎖（避免CPU浪費(fèi)）

// 鎖等待時(shí)進(jìn)入低功耗狀態(tài)
spin_wait:
  wfe         // Wait For Event（暫停CPU流水線）
  b check_lock // 被喚醒后重新檢查鎖狀態(tài)

// 解鎖時(shí)觸發(fā)事件
spin_unlock:
  str wzr, [x0]      // 釋放鎖
  sev         // Send Event（喚醒其他核心的wfe）

// 錯(cuò)誤！單核忙等待導(dǎo)致死鎖
spin_lock(&lock);
// 若鎖已被占用，當(dāng)前線程永不釋放CPU，持有鎖的線程無法運(yùn)行

// 內(nèi)核場(chǎng)景（用戶態(tài)無此問題）
void irq_handler() {
    mutex_lock(&lock); // 可能睡眠 → 崩潰！
}

// 典型用法（中斷安全版）
DEFINE_SPINLOCK(my_lock);
unsigned long flags;

spin_lock_irqsave(&my_lock, flags); // 關(guān)中斷 + 拿鎖
/* 臨界區(qū)操作 */
spin_unlock_irqrestore(&my_lock, flags); // 放鎖 + 開中斷

// 典型用法
DEFINE_MUTEX(my_mutex);

mutex_lock(&my_mutex);  // 可能睡眠
/* 臨界區(qū)（可包含阻塞操作） */
mutex_unlock(&my_mutex);

// 加鎖流程偽代碼（kernel/locking/mutex.c）
void mutex_lock(struct mutex *lock) {
    // 1. 快速路徑：用戶態(tài)式原子獲取
    if (atomic_cas(lock->count, 1, 0)) 
        return;
    
    // 2. 中速路徑：短暫自旋（約100循環(huán)）
    for (int i = 0; i < 100; i++) {
        if (atomic_cas(lock->count, 1, 0)) 
            return;
        cpu_relax(); // 降低CPU壓力（ARM64: wfe）
    }
    
    // 3. 慢速路徑：真正睡眠
    __mutex_lock_slowpath(lock);
}

// arch/arm/include/asm/spinlock.h
static inline void arch_spin_lock(arch_spinlock_t *lock)
{
	unsigned long tmp;        // 用于存儲(chǔ) STREX 指令的返回結(jié)果（0表示成功，非0表示失?。?
	u32 newval;               // 計(jì)算后的新鎖值（當(dāng)前鎖值 + 一個(gè) ticket）
	arch_spinlock_t lockval;  // 存儲(chǔ) LDREX 加載的當(dāng)前鎖狀態(tài)

	// 預(yù)取鎖的內(nèi)存到緩存，優(yōu)化后續(xù)訪問速度
	prefetchw(&lock->slock);

	// 通過 LDREX/STREX 原子操作嘗試獲取 ticket（ARM 架構(gòu)原子操作的核心）
	__asm__ __volatile__(
	"1:	ldrex	%0, [%3]\n"        // 加載當(dāng)前鎖值到 %0（lockval.slock）
	"	add	%1, %0, %4\n"        // 計(jì)算新鎖值：當(dāng)前鎖值 + (1 << TICKET_SHIFT)（分配新 ticket）
	"	strex	%2, %1, [%3]\n"    // 嘗試將新鎖值寫回內(nèi)存，結(jié)果存入 %2（tmp）
	"	teq	%2, #0\n"            // 檢查 STREX 是否成功（結(jié)果為0表示成功）
	"	bne	1b"                  // 失敗則跳轉(zhuǎn)到1標(biāo)號(hào)重試
	: "=&r" (lockval), "=&r" (newval), "=&r" (tmp)  // 輸出操作數(shù)（按順序?qū)?yīng) %0/%1/%2）
	: "r" (&lock->slock), "I" (1 << TICKET_SHIFT)   // 輸入操作數(shù)（鎖地址和 ticket 偏移量）
	: "cc");                                        // 破壞的寄存器：條件碼寄存器

	// 等待當(dāng)前線程的 ticket 被輪到（ticket 機(jī)制核心邏輯）
	// 當(dāng) lockval.tickets.next（當(dāng)前線程的 ticket）等于 lockval.tickets.owner（當(dāng)前持有鎖的 ticket）時(shí)，獲取鎖成功
	while (lockval.tickets.next != lockval.tickets.owner) {
		wfe();  // 進(jìn)入低功耗等待狀態(tài)（Wait For Event），直到收到 SEV 事件喚醒
		// 重新讀取最新的 owner 值（避免緩存臟數(shù)據(jù)，確保獲取最新鎖狀態(tài)）
		lockval.tickets.owner = READ_ONCE(lock->tickets.owner);
	}

	// 內(nèi)存屏障：確保加鎖后的操作不會(huì)被重排序到加鎖之前，保證內(nèi)存可見性
	smp_mb();
}

// include/linux/mutex.h
/*
 * 互斥鎖核心結(jié)構(gòu)體，提供嚴(yán)格的互斥訪問機(jī)制：
 * 成員說明：
 *   owner       - 原子長(zhǎng)整型，記錄當(dāng)前持有鎖的任務(wù)指針（低bit可能包含狀態(tài)標(biāo)志）
 *   wait_lock   - 自旋鎖，用于保護(hù)等待隊(duì)列的并發(fā)訪問
 *   osq         - 樂觀自旋隊(duì)列（MCS鎖），用于實(shí)現(xiàn)自旋優(yōu)化（僅在CONFIG_MUTEX_SPIN_ON_OWNER啟用時(shí)存在）
 *   wait_list   - 等待該鎖的任務(wù)鏈表頭，使用內(nèi)核標(biāo)準(zhǔn)鏈表結(jié)構(gòu)
 *   magic       - 調(diào)試標(biāo)識(shí)指針，用于驗(yàn)證結(jié)構(gòu)體有效性（僅在CONFIG_DEBUG_MUTEXES啟用時(shí)存在）
 *   dep_map     - 鎖依賴跟蹤映射表，用于死鎖檢測(cè)（僅在CONFIG_DEBUG_LOCK_ALLOC啟用時(shí)存在）
 *   ANDROID...  - Android OEM廠商自定義數(shù)據(jù)擴(kuò)展區(qū)
 */
struct mutex {
	atomic_long_t		owner;
	spinlock_t		wait_lock;
#ifdef CONFIG_MUTEX_SPIN_ON_OWNER
	struct optimistic_spin_queue osq; /* Spinner MCS lock */
#endif
	struct list_head	wait_list;
#ifdef CONFIG_DEBUG_MUTEXES
	void			*magic;
#endif
#ifdef CONFIG_DEBUG_LOCK_ALLOC
	struct lockdep_map	dep_map;
#endif
	ANDROID_OEM_DATA_ARRAY(1, 2);
};

// 錯(cuò)誤！導(dǎo)致內(nèi)核崩潰
void irq_handler() {
    mutex_lock(&lock);  // 可能觸發(fā)調(diào)度 → 內(nèi)核oops!
}

// 死鎖風(fēng)險(xiǎn)！
spin_lock(&lock);
// 若中斷到來并嘗試獲取同一鎖 → 死鎖

// CPU資源浪費(fèi)
spin_lock(&lock);
msleep(10);  // 睡眠10ms → 其他核空轉(zhuǎn)10ms
spin_unlock(&lock);