// src/include/storage/s_lock.h
typedef unsigned char slock_t;    // x86_64 平台

// 关键的 TAS (Test-And-Set) 宏：测试并设置锁
// 返回 0（拿到锁）或 1（锁被占用）
// 在 x86_64 上用 xchgb 指令实现：
//   movb $1, %al
//   xchgb %al, (%rdi)    // 原子交换
//   testb %al, %al        // 检查原值
```text

获取 SpinLock 的函数签名和调用路径：

```c
// src/include/storage/spin.h
extern int s_lock(volatile slock_t *lock, const char *file, int line);

// SpinLockAcquire 宏展开为 s_lock()
#define SpinLockAcquire(lock) s_lock(lock, __FILE__, __LINE__)

#define SpinLockRelease(lock) do { *(lock) = 0; } while (0)
// 在某些平台上使用原子 store 保证内存屏障
```bash

### 使用边界

SpinLock 的临界区必须满足极严格的约束：

1. **临界区极短**：几十个 CPU 指令周期以内。自旋等待不释放 CPU，持锁时间越长，浪费的 CPU 周期越多。
2. **临界区不能触发上下文切换**：不能调用 `palloc()`（可能触发 malloc 和系统调用）、不能写 elog/ereport（可能触发 syslog 写）、不能调用任何可能导致 `errno` 被修改的函数、不能获取 LWLock 或 Heavyweight Lock。
3. **持有 SpinLock 时不能再次获取同一 SpinLock**：不是可重入锁，会死锁。
4. **在中断上下文中也可能需要 SpinLock**：部分信号处理器会竞争 SpinLock，所以临界区必须信号安全。

PG 中 SpinLock 的典型使用场景：

```c
// 例 1：更新共享内存中的统计计数器
// src/backend/postmaster/pgstat.c
SpinLockAcquire(&pgStatDBHashLock);
// ... 更新几个整数字段 ...
SpinLockRelease(&pgStatDBHashLock);

// 例 2：保护 LWLock 的内部状态
// src/backend/storage/lmgr/lwlock.c
// LWLock 自身用 SpinLock 保护 wait list 操作
SpinLockAcquire(&lock->waitlist_lock);
// ... 修改等待列表的指针 ...
SpinLockRelease(&lock->waitlist_lock);

// src/include/storage/lwlock.h
typedef struct LWLock {
    pg_atomic_uint32 state;   // 锁状态：是否被持有、等待者计数
    pg_atomic_uint32 nwaiters; // 等待者数量（用于决定是否需要信号量唤醒）
    int             sema;     // 信号量索引（仅在需要阻塞等待时使用）
    // ...
} LWLock;
```text

获取 LWLock 的流程（简化）：

```c
// src/backend/storage/lmgr/lwlock.c, LWLockAttemptLock()
// 尝试用原子 CAS 获取锁
static bool LWLockAttemptLock(LWLock *lock, LWLockMode mode) {
    uint32 old_state = pg_atomic_read_u32(&lock->state);

    while (true) {
        uint32 desired_state;

        if (mode == LW_EXCLUSIVE) {
            // 排他模式：如果当前 lock 未被持有（state 的 lock count 为 0），则获取
            if (old_state & LW_FLAG_HAS_WAITERS || old_state & LW_LOCK_MASK)
                return false;  // 锁已被持有
            desired_state = old_state | LW_FLAG_HAS_WAITERS | 1;
        } else { // LW_SHARED
            // 共享模式：如果当前没有被排他持有，则递增共享计数
            if (old_state & LW_LOCK_MASK) {
                // 排他锁持有中，不能获取共享锁
                return false;
            }
            desired_state = old_state + (1 << LW_SHARED_SHIFT);
        }

        // CAS 尝试设置新状态
        if (pg_atomic_compare_exchange_u32(&lock->state, &old_state, desired_state))
            return true;
        // CAS 失败（其他进程同时修改了 state），重试
    }
}

// src/backend/storage/lmgr/lwlock.c, LWLockRelease()
void LWLockRelease(LWLock *lock) {
    // 更新 state，清除持有标志
    old_state = pg_atomic_sub_fetch_u32(&lock->state, ...);

    // 如果有等待者，唤醒它们
    if (old_state & LW_FLAG_HAS_WAITERS) {
        pg_atomic_fetch_and_u32(&lock->state, ~LW_FLAG_HAS_WAITERS);
        // 用 semop() 唤醒等待者
        PGSemaphoreUnlock(&lock->sema);
    }
}
```bash

### 第三代：PG 16 的 LWLockWaitListLock 优化

PG 16 引入了一个微架构改进：**`LWLockWaitListLock`**。在 PG 9.5-15 的实现中，等待者共享同一个信号量并执行"惊群"（thundering herd）式的唤醒：释放者调用 `semop()` 唤醒所有等待者，每个等待者从 `semop()` 返回后重新竞争 CAS。这在高并发时造成大量不必要的 CPU 消耗和缓存颠簸。

PG 16 在 LWLock 结构中新增了 per-lock 的等待列表锁：

```c
// PG 16 的 LWLock 结构（简化）
typedef struct LWLock {
    pg_atomic_uint32 state;
    pg_atomic_uint32 nwaiters;
    proclist_head   waiters;        // 等待者的双向链表
    slock_t         waitlist_lock;  // PG 16 新增：保护 waiters 链表的 spinlock
} LWLock;

SELECT pid, wait_event_type, wait_event, state, query
FROM pg_stat_activity
WHERE wait_event_type = 'LWLock';
```text

常见的 LWLock 等待事件含义：

| wait_event | 对应的锁 | 常见原因 |
|------------|---------|---------|
| `WALWriteLock` | WAL 写入锁 | 大量事务提交时 WAL 写入竞争 |
| `WALInsertLock` | WAL 插入锁 | PG 9.4- 是瓶颈，PG 9.5+ 分段后大幅缓解 |
| `BufferContent` | Buffer 页面内容锁 | 并发读写同一页面（热点页） |
| `LockManager` | 重量级锁分区的 LWLock | 高并发锁获取/释放 |
| `ProcArrayLock` | 进程数组锁 | 大量连接时 GetSnapshotData() 竞争 |
| `CLogControl` | CLOG SLRU 锁 | 大量事务状态查询/更新 |

---

## 四、Heavyweight Lock：事务级的重量级锁

### 设计目标

Heavyweight Lock（在 PG 源码中直接称为 `LOCK`）是锁层级的最上层。它解决 SpinLock 和 LWLock 解决不了的问题：

1. **事务语义**：锁在事务结束时自动释放，支持 `ROLLBACK` 和子事务（savepoint）回滚。
2. **死锁检测**：自动检测等待环路，选择一个事务回滚。
3. **锁升级/转换**：支持在共享锁和排他锁之间转换，支持锁强度的比较（`ACCESS SHARE` < `ROW SHARE` < `ROW EXCLUSIVE` < `SHARE UPDATE EXCLUSIVE` < `SHARE` < `SHARE ROW EXCLUSIVE` < `EXCLUSIVE` < `ACCESS EXCLUSIVE`）。
4. **等待队列**：等待者按 FIFO 排队，支持队列跳跃（在特定条件下）。

PG 定义了 8 种锁模式，按强度递增：

| 锁模式 | 数值 | 典型 SQL |
|-------|------|---------|
| `AccessShareLock` | 1 | `SELECT` |
| `RowShareLock` | 2 | `SELECT ... FOR SHARE` |
| `RowExclusiveLock` | 3 | `INSERT` / `UPDATE` / `DELETE` |
| `ShareUpdateExclusiveLock` | 4 | `VACUUM`（不 FULL）、`ANALYZE`、`CREATE INDEX CONCURRENTLY` |
| `ShareLock` | 5 | `CREATE INDEX`（非 CONCURRENTLY） |
| `ShareRowExclusiveLock` | 6 | `CREATE TRIGGER` |
| `ExclusiveLock` | 7 | `REFRESH MATERIALIZED VIEW CONCURRENTLY` |
| `AccessExclusiveLock` | 8 | `ALTER TABLE`、`DROP TABLE`、`VACUUM FULL` |

这 8 种模式通过**冲突矩阵**（conflict table，`src/backend/storage/lmgr/lock.c` 中的 `LockConflicts[]`）定义哪些模式可以共存。例如，`AccessShareLock` 和 `RowExclusiveLock` 不冲突——读和写可以并行——这是 MVCC 的核心优势。但 `AccessExclusiveLock` 和所有模式都冲突，所以 `ALTER TABLE` 会阻塞一切。

### Lock hash table 的结构

所有 Heavyweight Lock 存储在共享内存中的一个哈希表中，称为 `LockMethodLockHash`。哈希键由**锁目标（locktag）**组成：

```c
// src/include/storage/lock.h
typedef struct LOCKTAG {
    uint32      locktag_field1;  // 数据库 OID
    uint32      locktag_field2;  // 关系 OID
    uint32      locktag_field3;  // 页面号（页级锁）或 0
    uint32      locktag_field4;  // 元组号（行级锁）或 0
    uint16      locktag_type;    // 锁类型：LOCKTAG_RELATION / LOCKTAG_PAGE / LOCKTAG_TUPLE
    // ...
} LOCKTAG;

// src/include/storage/lock.h
typedef struct LOCK {
    LOCKTAG     tag;            // 锁目标（哈希键）
    LOCKMASK    grantMask;      // 已授予的锁模式位掩码
    LOCKMASK    waitMask;       // 等待中的锁模式位掩码
    SHM_QUEUE   procLocks;      // 持有本锁的所有 PROCLOCK（链表）
    SHM_QUEUE   waitProcs;      // 等待本锁的进程队列
    int         requested[8];   // 每种锁模式的总请求数
    int         granted[8];     // 每种锁模式的已授予数
    int         nRequested;     // 总请求数
    int         nGranted;       // 总授予数
} LOCK;
```text

每个进程对每个锁的持有信息存储在 `PROCLOCK` 结构体中：

```c
typedef struct PROCLOCK {
    SHM_QUEUE   lockLink;       // 链入 LOCK.procLocks
    SHM_QUEUE   procLink;       // 链入 PGPROC.procLocks
    PROCLOCKTAG tag;            // { LOCK, PGPROC }
    LOCKMASK    holdMask;       // 本进程持有的锁模式位掩码
    // ...
} PROCLOCK;

// src/backend/storage/lmgr/lock.c（简化）
static bool GrantLock(LOCK *lock, PROCLOCK *proclock, LOCKMODE lockmode) {
    // 检查请求的锁模式是否与已授予的模式冲突
    if (!(LockConflicts[lockmode] & lock->grantMask)) {
        // 不冲突：授予锁
        proclock->holdMask |= LOCKBIT_ON(lockmode);
        lock->grantMask |= LOCKBIT_ON(lockmode);
        lock->granted[lockmode]++;
        return true;
    }
    // 冲突：不能授予，等待者继续等待
    return false;
}
```bash

### 锁获取的 fast path 优化

对于最常用的弱锁模式（通常是表级的 `AccessShareLock`），PG 提供了 **fast path** 优化：如果锁不冲突且锁请求不过多，`LockAcquire()` 跳过哈希表查找，直接把锁记录在 `PGPROC` 的一个固定大小数组中（`fpLockBits`，默认 16 个槽位）。

```c
// 判断是否能走 fast path
static bool FastPathLocalUseAllowed(LOCKTAG *locktag, LOCKMODE lockmode) {
    // 只有表级锁、行级锁可以使用 fast path
    // 且锁模式不能强于 ShareUpdateExclusiveLock
    if (lockmode >= ShareUpdateExclusiveLock)
        return false;
    // 弱锁：尝试 fast path
    return true;
}

// src/backend/storage/lmgr/proc.c, ProcSleep()
// 等待进程在等待队列中的主循环
while (waiting) {
    // 等待 deadlock_timeout 毫秒
    timeout = deadlock_timeout;
    WaitOnLock(&locallock, lock, proclock, &timeout);

    // 超时唤醒：执行死锁检测
    if (CheckDeadLock()) {
        // 检测到死锁且本进程被选为牺牲者
        ereport(ERROR, (errcode(ERRCODE_T_R_DEADLOCK_DETECTED),
                errmsg("deadlock detected"),
                errdetail_hint(...)));
    }

    // 检查锁是否可用
    if (GrantLock(lock, proclock, lockmode)) {
        waiting = false;  // 拿到锁，退出循环
    }
    // 否则继续等待
}
```text

注意 `deadlock_timeout` 的双重作用：它同时控制死锁检测间隔和 `log_lock_waits` 的报告阈值。当一个进程等待锁超过 `deadlock_timeout` 时，如果 `log_lock_waits = on`，PG 会记录一条日志。

### 等待图（Wait-For Graph）的构建

`DeadLockCheck()` 的核心算法在 `src/backend/storage/lmgr/deadlock.c` 中。它是一个基于 DFS（深度优先搜索）的环路检测算法。

等待图是隐式构建的，不预先创建完整图：

```c
// src/backend/storage/lmgr/deadlock.c, DeadLockCheck()
// 从当前进程出发，BFS 搜索等待图中的环路
bool DeadLockCheck(PGPROC *proc) {
    // 初始化：从当前等待进程出发
    nDeadlockDetails = 0;
    visitedProcs = 0;
    nPossibleConstraints = 0;
    curConstraints = waitingConstraints;

    // 第一个被访问的节点是当前进程
    // 检查从它出发是否能在等待图中走回自身
    if (!FindLockCycle(proc, possibleConstraints, &nSoftEdges))
        return false;  // 没有环路

    // 找到了环路：确定牺牲者
    // 筛选环路中最适合回滚的事务
    return true;
}

// src/backend/storage/lmgr/deadlock.c（简化）
static bool FindLockCycle(PGPROC *checkProc,
                          EDGE *softEdges, int *nSoftEdges) {
    // 1. 找到 checkProc 正在等待的锁
    lock = checkProc->waitLock;
    if (lock == NULL)
        return false;

    // 2. 遍历持有该锁的所有进程（lockedBy）
    for each PROCLOCK held on this lock {
        PGPROC *holder = proclock->tag.myProc;

        // 如果 holder 也在等待某个锁，继续向深处搜索
        if (holder->waitLock != NULL) {
            if (holder == startProc) {
                // 找到了回到起点的环路！
                return true;
            }
            if (FindLockCycle(holder, softEdges, nSoftEdges))
                return true;
        }
    }

    return false;
}
```bash

### 牺牲者选择

检测到环路后，不是任意回滚一个事务。`DeadLockCheck()` 通过以下策略选择牺牲者：

1. **选择所有环路中涉及的事务集合**。
2. **排除已经在回滚的事务**（因为它们会自动释放锁）。
3. **选择回滚代价最小的事务**，优先考虑：已经执行时间最短的、锁请求最少的、事务 ID 最新的。

当死锁被检测到时，PG 中止选中的事务并返回错误：

### 行级锁的死锁检测

行级锁（FOR UPDATE / FOR SHARE）也会触发死锁检测。行级锁的等待信息存储在 `PGPROC` 的 `waitLock` 中，`LOCKTAG` 的 `locktag_type` 为 `LOCKTAG_TUPLE`，`locktag_field4` 是等待的元组的事务 ID。死锁检测算法对行级锁和表级锁使用相同的 BFS 路径。

---

## 六、行级锁：FOR UPDATE/FOR SHARE 与 t_infomask

### 行级锁的语义

PG 的 MVCC 使得 `SELECT` 不需要读锁——每个查询通过快照看到数据库的一致版本。但 `SELECT ... FOR UPDATE` 和 `SELECT ... FOR SHARE` 需要一种机制阻止其他事务修改行，同时不需要在共享内存中为每行创建独立锁对象。

PG 的方案是**把锁信息写在行本身**：Heap Tuple Header 中的 `t_infomask` 字段包含三个 lock bit：

```c
// src/include/access/htup_details.h
#define HEAP_XMAX_KEYSHR_LOCK   0x0010  // xmax 是 key-shared 锁（FOR KEY SHARE，FK 检查用）
#define HEAP_XMAX_EXCL_LOCK     0x0040  // xmax 是排他锁（FOR UPDATE）
#define HEAP_XMAX_LOCK_ONLY     0x0080  // xmax 是锁而非删除
#define HEAP_XMAX_IS_MULTI      0x1000  // xmax 是 MultiXactId

#define HEAP_XMAX_IS_MULTI      0x1000  // xmax 是 MultiXactId，不是单独的事务 ID
```text

MultiXact 的状态存储在 `src/backend/access/transam/multixact.c` 管理的 SLRU（Simple LRU）结构中，包含成员事务列表和每个成员的锁模式。这是一个复杂的子系统，涉及自己的 freezing 策略和 wraparound 风险。

### 行级锁的等待机制

行级锁等待和表级锁使用相同的 Heavyweight Lock 基础设施。每个 `PGPROC` 通过 `waitLock` 字段指向等待的 `LOCK` 对象：

```c
// src/backend/access/heap/heapam.c（简化）
// XactLockTableWait() 用于等待目标事务提交或回滚
// 这是行级锁等待的核心
void XactLockTableWait(TransactionId xid, ...) {
    LOCKTAG tag;
    SET_LOCKTAG_TRANSACTION(tag, xid);  // 锁目标是事务 ID

    // 在锁表中获取锁（等待目标事务完成）
    LockAcquire(&tag, ShareLock, false, false);
    // 拿到锁意味着目标事务已经提交或回滚
    LockRelease(&tag, ShareLock, false);
}

SELECT
    locktype,              -- relation, tuple, transactionid, virtualxid, object, ...
    database,              -- 数据库 OID
    relation::regclass,    -- 关系名
    page,                  -- 页面号（页级锁）
    tuple,                 -- 元组号（行级锁）
    virtualxid,            -- 虚拟事务 ID
    transactionid,         -- 事务 ID
    mode,                  -- 锁模式：AccessShareLock, RowExclusiveLock, ...
    granted,               -- t = 已授予, f = 等待中
    pid,                   -- 持有或等待锁的进程 PID
    waitstart              -- 等待开始时间（仅 waiting 的进程有值）
FROM pg_locks
ORDER BY pid, granted;
```text

这个查询给出当前所有的锁状态。"正在等待"的锁（`granted = false`）是排查锁等待链的入口。

### 阻塞链追踪：pg_blocking_pids()

`pg_blocking_pids(pid)` 是最实用的锁诊断函数：给定一个进程 PID，返回阻塞它的所有进程的 PID：

```sql
SELECT
    pid,
    pg_blocking_pids(pid) AS blocked_by,
    wait_event_type,
    wait_event,
    state,
    query
FROM pg_stat_activity
WHERE wait_event_type = 'Lock'
  AND pid != pg_backend_pid();

-- 递归查找锁等待链
WITH RECURSIVE wait_chain AS (
    -- 基准：所有正在等待锁的进程
    SELECT
        pid,
        pg_blocking_pids(pid) AS blockers,
        state,
        query,
        1 AS level
    FROM pg_stat_activity
    WHERE wait_event_type = 'Lock'
      AND pid != pg_backend_pid()

    UNION

    -- 递归：找到阻塞者，以及阻塞者的阻塞者
    SELECT
        blocked.pid,
        pg_blocking_pids(blocked.pid),
        blocked.state,
        blocked.query,
        wc.level + 1
    FROM pg_stat_activity blocked
    JOIN wait_chain wc ON blocked.pid = ANY(wc.blockers)
    WHERE pg_blocking_pids(blocked.pid) != ARRAY[]::int[]
)
SELECT DISTINCT pid, blockers, state, level, query
FROM wait_chain
ORDER BY level, pid;
```bash

### 哪些进程持锁最久

```sql
SELECT
    l.pid,
    a.usename,
    a.application_name,
    a.state,
    a.query_start,
    now() - a.query_start AS query_duration,
    a.xact_start,
    now() - a.xact_start AS xact_duration,
    l.mode,
    l.locktype,
    l.relation::regclass AS relation,
    l.granted,
    a.query
FROM pg_locks l
JOIN pg_stat_activity a ON l.pid = a.pid
WHERE l.granted = true
  AND l.locktype = 'relation'
  AND l.relation IS NOT NULL
ORDER BY a.xact_start NULLS LAST;

-- 先看目标进程的会话信息
SELECT pid, state, query, xact_start,
       now() - xact_start AS xact_age
FROM pg_stat_activity
WHERE pid = 12345;

-- 终止进程（发送 SIGTERM，允许事务清理）
SELECT pg_terminate_backend(12345);

-- 更强制的方式（发送 SIGKILL 信号等价物，不做清理）
-- SELECT pg_cancel_backend(12345);  -- 仅取消当前查询，不终止连接
```text

`pg_terminate_backend()` 发送 `SIGTERM` 信号给目标进程，目标进程在下一个 `CHECK_FOR_INTERRUPTS()` 调用处检测到并执行事务回滚和锁释放。如果目标进程卡在内核 I/O 中（如阻塞在磁盘读取），可能需要等待 I/O 超时才能响应。

---

## 八、实验：构造并观察锁等待

### 构造表级锁等待

在 Session A 中：

```sql
BEGIN;
LOCK TABLE test_table IN ACCESS EXCLUSIVE MODE;
-- 不要 COMMIT，保持持锁状态

SELECT * FROM test_table;
-- 阻塞，等待 AccessShareLock
```text

在 Session C（诊断窗口）中观察：

```sql
SELECT
    pid,
    mode,
    granted,
    relation::regclass,
    waitstart
FROM pg_locks
WHERE relation = 'test_table'::regclass
  AND NOT granted;

SELECT pid, pg_blocking_pids(pid), wait_event, query
FROM pg_stat_activity
WHERE pid = (SELECT pid FROM pg_locks
             WHERE relation = 'test_table'::regclass
               AND NOT granted
             LIMIT 1);

BEGIN;
UPDATE accounts SET balance = balance - 100 WHERE id = 1;
-- 持有 id=1 的 RowExclusiveLock
```text

Session B：

```sql
BEGIN;
UPDATE accounts SET balance = balance - 50 WHERE id = 2;
-- 持有 id=2 的 RowExclusiveLock

UPDATE accounts SET balance = balance + 100 WHERE id = 2;
-- 等待 id=2 的锁，被 Session B 阻塞
```text

Session B 试图更新 id=1：

```sql
UPDATE accounts SET balance = balance + 50 WHERE id = 1;
-- 等待 id=1 的锁，被 Session A 阻塞，形成环路
-- 等待 deadlock_timeout 后，PG 检测到死锁，回滚其中一个事务：
-- ERROR: deadlock detected