循环

跨线程阻塞

现在，用于跨线程阻塞的接口的工作方式如下：

• 当一个线程 T1 希望阻塞另一个线程 T2 正在执行的查询 Q 时，它（T1 方）会调用 Runtime::try_block_on。这将检查循环。假设没有检测到循环，它会阻塞 T1，直到 T2 以 Q 结束。此时，重新唤醒 T1 。但是，我们不知道执行 Q 的结果，所以 T1 现在必须重试 （retry）。通常，这最终成功读取缓存值。
• 当 T1 被阻塞时，运行时将其查询栈（一个 Vec）移动到共享依赖图数据结构中。当重新唤醒 T1 时，它从 try_block_on 返回之前恢复其查询栈的所有权。

检测循环

当线程 T1 试图执行查询 Q 时，它将尝试从记忆表中加载 Q 的值。

如果发现 InProgress 标记，则表示当前正在计算 Q。这表明了一个潜在的循环。然后， T1 会尝试阻止查询 Q：

• 如果 Q 也被 T1 计算，那么就有一个循环。
• 否则，如果 Q 正在被其他线程 T2 计算，则必须检查 T2 是否在 T1 上（传递地）被阻塞。如果是，则存在一个循环。

这两种情况由 Runtime::try_block_on 函数内部处理。检测线程内循环的情况很容易；而为了检测跨线程循环，运行时维护线程之间的依赖 DAG（由 RuntimeId 标识)。

在将 T1 -> T2 边（即阻塞 T1 等待 T2）添加到 DAG 之前，检查是否存在从 T2 到 T1 的路径。如果是，则存在一个循环，且边不能被添加（然后 DAG 将不再是非循环的）。

当检测到循环时，当前线程 T1 具有对参与该循环的查询栈的完全访问权限。思考一下： T1 当然可以访问它自己的栈。

还有一条 T2 -> ... -> Tn -> T1 阻塞线程路径。每个被阻塞的线程 T2 ..= Tn 将它们的查询栈移动到依赖图中，因此这些查询栈可供检查。

通过使用可用的栈，我们可以创建一列 Q0 ... Qn 循环参与者，并将其存储到一个 Cycle 结构体中。如果参与者 Q0 ...Qn 全都没有启用循环恢复，就会因为 Cycle 结构体而 panic，从而触发该线程上的所有查询 panic。

通过回退实现循环恢复

如果任何一个循环参与者已经设置了循环恢复，那么会从循环中恢复。

为了解释这是如何工作的，我们将使用这个三个线程的示例循环。从当前查询开始，循环参与者为 QA3、QB2、QB3、QC2、QC3、QA2。

        The cyclic
        edge we have
        failed to add.
          :
   A      :    B         C
          :
   QA1    v    QB1       QC1
┌► QA2    ┌──► QB2   ┌─► QC2
│  QA3 ───┘    QB3 ──┘   QC3 ───┐
│                               │
└───────────────────────────────┘

恢复工作分阶段进行：

• 分析：当枚举查询参与者时，收集他们的共同输入（到目前为止由任何循环参与者调用的所有查询）以及最大更改时间和最小持续时间。 然后，从该输入列表中删除循环参与者，只留下循环外部的查询。
• 标记：对于每个用 #[salsa::recover] 标注的查询 Q，通过将其 cycle 标志设置为先前构造的 c: Cycle 来标记它及其在同一线程上的所有之后的查询（后继查询）；并将其输入重置为在分析期间收集的共同输入。 如果这些查询稍后继续执行，则这些标记将触发它们立即展开 (unwind) 并使用循环恢复，且其输入将用作恢复值的输入。
  • 注意，在同一线程上标记了 Q 所有后继查询，无论它们是否设置了恢复。稍后将讨论在活动线程（此处为 A）没有设置任何恢复的情况下这是多么重要。
• 解除阻塞：强制重新唤醒每个具有恢复查询的阻塞线程 T；移除从该线程到循环中的后续线程所传出的边 (edge)。用一个 WaitResult::Cycle(c) 向 condvar 发出信号。当重新唤醒线程时，它将看到这一点，并以 c 循环开始展开。
• 处理当前线程：最后，必须选择如何让当前线程继续。如果当前线程包含任何带有恢复信息的循环，则可以开始展开。否则，当前线程就简单地继续，就好像没有循环一样， 因此循环边被添加到图中，当前线程阻塞。这是可能的，因为其他线程有恢复信息，因而已被唤醒。

让我们通过几个例子来演示这个过程。

eg1：在检测线程上的恢复

考虑只有查询 QA2 设置了恢复的情况。QA2 和 QA3 会将其 Cycle 标志设置为 c: Cycle。线程 B 和 C 不会被解除阻塞，因为它们没有任何循环恢复节点。

当前线程（线程 A）将以循环 c 为值发起展开 (unwind)。展开将经过 QA3，并被 QA2 捕获。 QA2 将替代恢复值并正常返回。 QA1 和 QC3 随后将正常完成，依此类推，直到所有查询完成。

eg2：在检测线程上的两个查询中的恢复

考虑查询 QA2 和 QA3 都设置了恢复的情况。与示例 1 执行相同过程，直到线程开始展开，如示例 1 所述。

当 QA3 接收到循环时，它把其恢复值存储起来并正常完成。然后 QA2 添加 QA3 作为输入依赖项：此时， QA2 也设置循环标记，因此它启动展开。因此， QA2 的其余部分永远不会被执行。这种展开被 QA2 的入口点 (entry point) 捕获，它存储恢复值并正常返回。QA1 和 QC3 随后正常继续，因为它们还没有设置其 cycle 标志。

eg3：在另一个线程上恢复

考虑只有查询 QB2 设置了恢复的情况。它和 QB3 将被标记为循环 c: Cycle，线程 B 将被解除阻塞；边 QB3 -> QC2 将从依赖图中移除。然后，线程 A 将添加一条边 QA3 -> QB2 并阻塞线程 B。此时，线程 A 释放依赖图上的锁，因此线程 B 被重新唤醒。它观察到 WaitResult::Cycle 并启动展开。展开经过 QB3 进入 QB2，然后恢复。然后， QB1 能够正常执行， QA3 也正常执行，并从那里继续执行。

eg4：恢复所有查询

考虑所有查询都设置了恢复的情况。此时，它们被标记了循环，并且所有跨线的边都从依赖图中移除。每个线程将独立唤醒并启动展开。每个查询都将恢复。