InnoDB：Lock Manager

/** Lock struct; protected by lock_sys latches */
struct lock_t {
  trx_t* trx; // 拥有该锁的事务
  // 同一个事务所有的锁形成一个链表，表头在 trx->lock.trx_locks
  UT_LIST_NODE_T(lock_t) trx_locks;
  dict_index_t*	index; // 数据行所在的索引（如果是行锁）
  lock_t* hash; // 所有的锁形成一个哈希表，用于快速查找

  // 这个结构体代表的是行锁或表锁，只能其一
  union {
    lock_table_t tab_lock;
    lock_rec_t rec_lock;
  };
  
  // 对锁的详细描述，一共 32 个 bit，每个 bit 意义不同。分为：锁的模式、种类和范围
  // 0-3 bit（LOCK_MODE_MASK）: 模式；LOCK_IS/LOCK_IX/LOCK_S/LOCK_X...
  // 4-7 bit（LOCK_TYPE_MASK）: 种类；LOCK_TABLE（表锁）/LOCK_REC（行锁）
  // 8-? bit（precise modes）详细的行锁信息 : 
  // LOCK_WAIT   256	表示正在等待锁
  // 锁的范围：
  // LOCK_ORDINARY 0 	表示 next-key lock ，锁住记录本身和记录之前的 gap
  // LOCK_GAP    512    表示锁住记录之前 gap（不锁记录本身）
  // LOCK_REC_NOT_GAP 1024	表示锁住记录本身，不锁记录前面的 gap
  // LOCK_INSERT_INTENTION 2048	插入意向锁
  // LOCK_PREDICATE 8192
  // LOCK_PRDT_PAGE 16384
  uint32_t type_mode;
}

/** The lock system struct */
struct lock_sys_t {
  /** The latches protecting queues of record and table locks */
  locksys::Latches latches;

  /** The hash table of the record (LOCK_REC) locks, except for predicate
  (LOCK_PREDICATE) and predicate page (LOCK_PRDT_PAGE) locks */
  hash_table_t *rec_hash;
  ...
}

/** Record lock for a page */
struct lock_rec_t {
  // 每个 lock_rec_t 都针对一个数据页，代表某个
  // 事务对该页中数据行（尽可能多）的行锁占有情况
  page_id_t page_id;
  // 该 lock_rec_t 能表示这个页多少行的行锁
  uint32_t n_bits;
}

lock_rec_lock_fast
{
  lock_t *lock = lock_rec_get_first_on_page(lock_sys->rec_hash, block);

  if (lock == nullptr) {
    // 如果 lock_sys->rec_hash 中没有找到这个数据页的行锁，则直接创建一个（第一个）
    RecLock rec_lock(index, block, heap_no, mode);

    rec_lock.create(trx)
    ......
  } else {
    // 如果 lock_sys->rec_hash 中找到了这个数据页的行锁
    // 看是不是可以直接使用（需同时满足）：
    // 1. 该页面只存在一个结构体 lock_t，且这个 lock_t 代表的是行锁
    // 2. lock_t 隶属于当前事务
    // 3. lock_t.lock_rec_t 中预分配的 bitmap 大小能够满足当前的 heap no
    // 直接把 heap no 在 bitmap 对应的 bit 设置为 1，表示加锁完成。否则
    // lock_rec_lock_fast 失败，则调用 lock_rec_lock_slow
  }
}

for (lock_t* lock = static_cast<lock_t*>(HASH_GET_FIRST(lock_hash, hash));
     lock != NULL;
     lock = static_cast<lock_t*>(HASH_GET_NEXT(hash, lock))) {
  ......
}

lock_rec_lock_slow
{
  // 1. 当前事务是否已经获得更强级别的行锁？
  // 针对特定的数据行（由 block 和 heap no 唯一确定），在 lock_sys::rec_hash 中查找当前事务是否
  // 已持有这个数据行的更强的行锁？（例如已持有 X，请求 S）。如果有，则直接返回（无需再申请）
  const auto *held_lock = lock_rec_has_expl(checked_mode, block, heap_no, trx);

  if (held_lock != nullptr) {
    if (checked_mode == mode) {
      /* The trx already has a strong enough lock on rec: do nothing */
      return (DB_SUCCESS);
    }
  }

  // 2. 在 lock_sys::rec_hash 是否其他事务已持有的该数据行的行锁和和当前申请的行锁冲突？
  // （lock_rec_has_to_wait），主要是通过兼容矩阵判断（lock_compatibility_matrix）
  // 如果不兼容，则认为有冲突。除非是一些特殊情况此处不详细暂开（比如请求的是 LOCK_GAP，已持
  // 有的是 LOCK_REC_NOT_GAP。
  // 如果有冲突，则创建一个
  const lock_t *wait_for =
      lock_rec_other_has_conflicting(mode, block, heap_no, trx);

  if (wait_for != nullptr) {
     RecLock rec_lock(thr, index, block, heap_no, mode);

     // 1. 在 add_to_waitq 里首先标记这个 rec_lock 是 LOCK_WAIT (m_mode |= LOCK_WAIT)
     // 2. 把 rec_lock 加入到 lock_sys::rec_hash 中，注意，LOCK_WAIT 模式下需要把 rec_lock
     //    放到 hash_cell_t 链表的尾部（否则是头部）
     // 3. 在 wait-for graph 中创建一条边（当前事务指向持有行锁事务），供死锁检测算法使用
     // 4. 返回 DB_LOCK_WAIT
     dberr_t err = rec_lock.add_to_waitq(wait_for);
  }

  // 当上层函数接收到 DB_LOCK_WAIT 错误时通常会调用 lock_wait_suspend_thread 等待行锁被授予
  // 在 lock_sys_t::waiting_threads 中选择一个 slot，等待 slot->event（当然，也可能最后该
  // 线程被选定为 deadlock victim）
}

void
lock_rec_dequeue_from_page(
/*=======================*/
	lock_t*		in_lock)	/*!< in: record lock object: all
					record locks which are contained in
					this lock object are removed;
					transactions waiting behind will
					get their lock requests granted,
					if they are now qualified to it */
{
  ......
  space = in_lock->un_member.rec_lock.space;
  page_no = in_lock->un_member.rec_lock.page_no;
  
  // 遍历这个数据页的每一个 lock_t
  for (lock = lock_rec_get_first_on_page_addr(lock_hash, space, page_no);
    lock != NULL;
    lock = lock_rec_get_next_on_page(lock)) {
    
    // 如果 lock->type_mode 是 LOCK_WAIT
    // 判断这个行锁（记为 lock1）请求是否可以被授予？（lock_rec_has_to_wait_in_queue）
    // 再次遍历 lock_sys->rec_hash，对于这个数据页的每一个 lock_t（记为 lock2），判断是否
    // 和 lock1 冲突？如果满足以下三点说明冲突：
    // 1. lock1 的 heap_no 小于 lock2 的 lock bitmap 大小
    // 2. lock2 把对应的 heap_no 锁住了，表明和 lock1 可能有冲突
    // 3. 查看兼容性矩阵中 lock1 和 lock2 的请求模式冲突（lock_has_to_wait）
    // 
    // 如果没找到这样的 lock2，则 lock1 的请求被授予，即去掉 lock->type_mode 的 LOCK_WAIT
    // 标记，唤醒等待的线程（lock_reset_lock_and_trx_wait）
    if (lock_get_wait(lock)
      && !lock_rec_has_to_wait_in_queue(lock)) {
      
      /* Grant the lock */
      ut_ad(lock->trx != in_lock->trx);
      lock_grant(lock);
    }
  }
}