/* storage/innobase/lock/lock0lock.cc */

 -------------------------
| RecLock::add_to_waitq() |
 -------------------------
  |
  |    /* 创建 lock. */
  |    -------------------
  --> | RecLock::create() |
  |    -------------------
  |      |
  |      |    /* 分配 lock, 初始化 lock_t. */
  |      |    -----------------------
  |      --> | RecLock::lock_alloc() |
  |      |    -----------------------
  |      |
  |      |    /* 插入 lock_sys->rec_hash. */
  |      |    ---------------------
  |      --> | RecLock::lock_add() |
  |           ---------------------
  |
  |    /* 假如事务的优先级较高，尝试跳过低优先级的事务直接获取 lock. */
  |    -----------------------
  --> | RecLock::jump_queue() |
  |    -----------------------
  |
  |   /* 否则需要进行死锁检测. */
  |    ---------------------------
  --> | RecLock::deadlock_check() |
       ---------------------------
         |
         |    /* 死锁检测，假如存在死锁返回一个需要被回滚的事务. */
         |    --------------------------------------
         --> | DeadlockChecker::check_and_resolve() |
         |    --------------------------------------
         |   
         |    /* 检查死锁检测的结果. */
         |    ----------------------------------
         --> | RecLock::check_deadlock_result() |
              ----------------------------------

/* storage/innobase/lock/lock0lock.cc */

/* lock: 当前事务申请的 lock
 * trx:  当前事务
 */ 
const trx_t *DeadlockChecker::check_and_resolve(const lock_t *lock,
                                                trx_t *trx) {
  /* 确保同时持有 lock_sys->mutex 和 trx->mutex. */
  ut_ad(lock_mutex_own());
  ut_ad(trx_mutex_own(trx));
  check_trx_state(trx);
  ut_ad(!srv_read_only_mode);

  if (trx->in_innodb & TRX_FORCE_ROLLBACK_ASYNC) {
    /* 假如 trx 设置了 TRX_FORCE_ROLLBACK_ASYNC, 即不允许该事务等待锁从而
     * 造成可能的死锁，我们应该选择该事务进行回滚操作. */
    return (trx);
  } else if (!innobase_deadlock_detect) {
    /* 假如用户关闭了死锁检测，直接返回 NULL. */
    return (NULL);
  }

  const bool was_trx_mutex_ownership_tracked = trx->owns_mutex;
  trx->owns_mutex = false;
  /* 释放 trx->mutex: trx 的事务状态只能被当前 thread 修改, 所以是安全的. */
  trx_mutex_exit(trx);

  const trx_t *victim_trx;

  do {
    /* 构建死锁检测 DeadlockChecker. */
    DeadlockChecker checker(trx, lock, s_lock_mark_counter);

    /* 进行死锁检测，并返回选中要回滚的事务. */
    victim_trx = checker.search();

    if (checker.is_too_deep()) {
      /* 假如死锁检测过深, 打印死锁信息. */
      ut_ad(trx == checker.m_start);
      ut_ad(trx == victim_trx);

      rollback_print(victim_trx, lock);

      MONITOR_INC(MONITOR_DEADLOCK);

      break;

    } else if (victim_trx != NULL && victim_trx != trx) {
      ut_ad(victim_trx == checker.m_wait_lock->trx);

      /* 进行回滚. 释放持有的锁并唤醒 thread. */
      checker.trx_rollback();

      lock_deadlock_found = true;

      MONITOR_INC(MONITOR_DEADLOCK);
    }

  } while (victim_trx != NULL && victim_trx != trx);

  /* ... */

  /* 重新持有 trx->mutex 锁. */
  trx_mutex_enter(trx);
  trx->owns_mutex = was_trx_mutex_ownership_tracked;

  return (victim_trx);
}

/* storage/innobase/lock/lock0lock.cc */

const trx_t *DeadlockChecker::search() {
  /* 确保持有 lock_sys->mutex. */
  ut_ad(lock_mutex_own());
  /* 确保没有持有 trx->mutex. */
  ut_ad(!trx_mutex_own(m_start));

  /* m_start: 发起死锁检测的事务, 死锁检测全程不会改变, 以该 trx 为基准判断是否存在环.
   * m_wait_lock: 发起死锁检测的事务等待的 lock, m_wait_lock 会随着 DFS 深度搜索过程改变.
   */
  ut_ad(m_start != NULL);
  ut_ad(m_wait_lock != NULL);
  check_trx_state(m_wait_lock->trx);
  ut_ad(m_mark_start <= s_lock_mark_counter);

  ulint heap_no;
  /* 获取 m_wait_lock 指向的 heap_no 上的第一个 lock. */
  const lock_t *lock = get_first_lock(&heap_no);

  for (;;) {
    /* We should never visit the same sub-tree more than once. */
    ut_ad(lock == NULL || !is_visited(lock));

    while (m_n_elems > 1 && lock == NULL) {
      /* 假如栈的元素数量大于1且 lock 为 NULL, 则代表某一条路径已经被搜索至尽头, 则进行
       * 回溯从而重新搜索未被访问的节点, 即存在一行数据上有多个锁.  */

      pop(lock, heap_no);

      /* 获取同一行数据上的下一个锁. */
      lock = get_next_lock(lock, heap_no);
    }

    if (lock == NULL) {
      /* 假如 lock 为 NULL, DFS 搜索结束, 结束循环. */
      break;
    } else if (lock == m_wait_lock) {
      /* 假如 lock == m_wait_lock, 需要标记该子树已经被访问过. */

      /* 这种情况只存在 DFS 回溯的阶段:
       * lock_t 维护的 hash table 插入的顺序排列, 在 DFS 回溯阶段, 
       * 假如存在一个 record 上有多个 lock_t 在等待,
       * 死锁检测算法会调用 get_next_lock(), 假如拿到了 lock == m_wait_lock,
       * 即代表后面的 lock 应该都是 wait 的顺序的, 所以没有必要再去看那些等待的 trx.
      ut_ad(lock->trx->lock.deadlock_mark <= m_mark_start);

      /* 设置已经被访问的标记. */
      lock->trx->lock.deadlock_mark = ++s_lock_mark_counter;

      ut_ad(s_lock_mark_counter > 0);

      /* 设置 lock 为 NULL. */
      lock = NULL;

    } else if (!lock_has_to_wait(m_wait_lock, lock)) {
      /* 假如 m_wait_lock 和 lock 之间不存在等待关系，则需要
       * 获取 heap_no 对应链表上的下一个lock. */
      /* No conflict, next lock */
      lock = get_next_lock(lock, heap_no);

    } else if (lock->trx == m_start) {
      /* 假如 lock 所指向的事务是当前发起死锁检测的事务, 即存在环. */

      /* 打印关于死锁信息的Log. */
      notify(lock);

      /* ... */

      return (select_victim());

    } else if (is_too_deep()) {
      /* 假如 DFS 搜索的栈元素超过了200或者访问的节点数目超过了 1000000,
       * 则返回 m_start 作为回滚的事务. */
      m_too_deep = true;
      return (m_start);

    } else if (lock->trx_que_state() == TRX_QUE_LOCK_WAIT) {
      /* Another trx ahead has requested a lock in an
      incompatible mode, and is itself waiting for a lock. */

      /* 假如 lock 所属的 trx 处于 TRX_QUE_LOCK_WAIT，即处于锁等待的状态.
       * 需要将<lock, heap_no> 入栈，DeadlockChecker 利用数组实现栈. */
      ++m_cost;

      if (!push(lock, heap_no)) {
        /* 假如入栈失败，即栈的元素数量超过了4096, 标记 m_too_deep, 并返回
         * m_start 事务回滚. */
        m_too_deep = true;
        return (m_start);
      }

      /* 使用 lock 替换 m_wait_lock, 用作下一次搜索. */
      m_wait_lock = lock->trx->lock.wait_lock;

      /* 获取当前 m_wait_lock 所属的 heap_no 的第一个 lock. */
      lock = get_first_lock(&heap_no);

      /* 假如该 lock 已经被访问过，则获取下一个 lock. */
      if (is_visited(lock)) {
        lock = get_next_lock(lock, heap_no);
      }

    } else {
      /* 否则获取下一个 lock. */
      lock = get_next_lock(lock, heap_no);
    }
  }

  ut_a(lock == NULL && m_n_elems == 0);

  /* 没有发现死锁. */
  return (0);
}