Wound/Wait 防死锁互斥锁设计¶

请先阅读通用互斥锁子系统，因为它也适用于 wait/wound 互斥锁。

WW-互斥锁的动机¶

GPU 执行的操作通常涉及许多缓冲区。这些缓冲区可以在上下文/进程之间共享，存在于不同的内存域（例如，VRAM 与系统内存）等等。并且通过 PRIME / dmabuf，它们甚至可以在设备之间共享。因此，驱动程序需要在许多情况下等待缓冲区准备就绪。如果您从等待缓冲区互斥锁变为可用状态的角度来考虑这一点，则会出现一个问题，因为无法保证缓冲区在所有上下文中都以相同的顺序出现在 execbuf/batch 中。这直接受用户空间的控制，并且是应用程序发出的 GL 调用序列的结果。这会导致死锁的可能性。当您考虑到内核可能需要在 GPU 在缓冲区上操作之前将缓冲区迁移到 VRAM 中时，问题会变得更加复杂，这可能又需要驱逐其他一些缓冲区（并且您不想驱逐已经排队到 GPU 的其他缓冲区），但为了简化对该问题的理解，您可以忽略这一点。

TTM 图形子系统为处理此问题而提出的算法非常简单。对于需要锁定的每组缓冲区 (execbuf)，调用者将从全局计数器分配一个唯一的保留 id/票证。如果在锁定与 execbuf 关联的所有缓冲区时发生死锁，则保留票证最低的（即，最旧的任务）获胜，而保留 id 较高的（即，较新的任务）解锁已锁定的所有缓冲区，然后重试。

在 RDBMS 文献中，保留票证与事务相关联。死锁处理方法称为 Wait-Die。该名称基于锁定线程遇到已锁定互斥锁时的行为。如果持有锁的事务较新，则锁定事务等待。如果持有锁的事务较旧，则锁定事务退避并终止。因此称为 Wait-Die。还有另一种算法称为 Wound-Wait：如果持有锁的事务较新，则锁定事务会“伤害”持有锁的事务，请求其终止。如果持有锁的事务较旧，则它会等待另一个事务。因此称为 Wound-Wait。这两种算法都是公平的，因为事务最终会成功。但是，通常认为 Wound-Wait 算法比 Wait-Die 产生更少的退避，但是，另一方面，从退避中恢复时，Wound-Wait 与比 Wait-Die 更多的工作相关联。Wound-Wait 也是一种抢占式算法，因为事务会被其他事务“伤害”，这需要一种可靠的方法来拾取“伤害”状态并抢占正在运行的事务。请注意，这与进程抢占不同。在 Wound-Wait 事务死亡（返回 -EDEADLK）之后，它被认为是被抢占了。

概念¶

与普通互斥锁相比，w/w 互斥锁的锁接口中出现了两个额外的概念/对象

获取上下文：为了确保最终向前进展，重要的是尝试获取锁的任务不会获取新的保留 id，而是保留它在开始获取锁时获得的那个 id。该票证存储在获取上下文中。此外，获取上下文会跟踪调试状态，以捕获 w/w 互斥锁接口滥用。获取上下文代表一个事务。

W/w 类：与普通互斥锁相反，对于 w/w 互斥锁，锁类需要是显式的，因为需要初始化获取上下文。锁类还指定要使用的算法，Wound-Wait 或 Wait-Die。

此外，还有三种不同的 w/w 锁获取函数类

使用上下文的正常锁获取，使用 ww_mutex_lock。
在争用锁上进行慢速路径锁获取，由刚刚终止其事务（在放弃所有已获取的锁之后）的任务使用。这些函数具有 _slow 后缀。

从简单的语义角度来看，_slow 函数不是严格必需的，因为在争用锁上简单地调用正常的 ww_mutex_lock 函数（在放弃所有其他已获取的锁之后）可以正常工作。毕竟，如果尚未获取其他 ww 互斥锁，则不存在死锁的可能性，因此 ww_mutex_lock 调用将阻塞并且不会过早地返回 -EDEADLK。_slow 函数的优点在于接口安全
- ww_mutex_lock 具有 __must_check int 返回类型，而 ww_mutex_lock_slow 具有 void 返回类型。请注意，由于 ww 互斥锁代码无论如何都需要循环/重试，因此即使第一个锁操作永远不会失败，__must_check 也不会导致虚假警告。
- 当启用完整调试时，ww_mutex_lock_slow 会检查是否已释放所有已获取的 ww 互斥锁（防止死锁），并确保我们在争用锁上阻塞（防止在 -EDEADLK 慢速路径中旋转，直到可以获取争用锁）。
仅获取单个 w/w 互斥锁的函数，其结果与普通互斥锁的语义完全相同。这通过使用 NULL 上下文调用 ww_mutex_lock 来完成。

同样，这不是严格必需的。但是通常您只想获取一个锁，在这种情况下，设置获取上下文毫无意义（因此最好避免获取死锁避免票证）。

当然，还提供了用于处理由于信号引起的唤醒的所有常用变体。

用法¶

该算法（Wait-Die 与 Wound-Wait）通过使用 DEFINE_WW_CLASS() (Wound-Wait) 或 DEFINE_WD_CLASS() (Wait-Die) 来选择。作为一个粗略的经验法则，如果您期望同时竞争的事务数量通常很小，并且您希望减少回滚次数，则使用 Wound-Wait。

在同一个 w/w 类中获取锁的三种不同方法。方法 #1 和 #2 的常见定义

static DEFINE_WW_CLASS(ww_class);

struct obj {
      struct ww_mutex lock;
      /* obj data */
};

struct obj_entry {
      struct list_head head;
      struct obj *obj;
};

方法 1，使用 execbuf->buffers 中的列表，不允许重新排序。如果已在某处跟踪所需对象的列表，这将非常有用。此外，锁助手可以将 -EALREADY 返回代码传播回调用者，作为对象在列表中出现两次的信号。如果列表是从用户空间输入构造的，并且 ABI 要求用户空间没有重复条目（例如，对于 gpu 命令缓冲区提交 ioctl），这将非常有用

int lock_objs(struct list_head *list, struct ww_acquire_ctx *ctx)
{
      struct obj *res_obj = NULL;
      struct obj_entry *contended_entry = NULL;
      struct obj_entry *entry;

      ww_acquire_init(ctx, &ww_class);

retry:
      list_for_each_entry (entry, list, head) {
              if (entry->obj == res_obj) {
                      res_obj = NULL;
                      continue;
              }
              ret = ww_mutex_lock(&entry->obj->lock, ctx);
              if (ret < 0) {
                      contended_entry = entry;
                      goto err;
              }
      }

      ww_acquire_done(ctx);
      return 0;

err:
      list_for_each_entry_continue_reverse (entry, list, head)
              ww_mutex_unlock(&entry->obj->lock);

      if (res_obj)
              ww_mutex_unlock(&res_obj->lock);

      if (ret == -EDEADLK) {
              /* we lost out in a seqno race, lock and retry.. */
              ww_mutex_lock_slow(&contended_entry->obj->lock, ctx);
              res_obj = contended_entry->obj;
              goto retry;
      }
      ww_acquire_fini(ctx);

      return ret;
}

方法 2，使用 execbuf->buffers 中的列表，可以重新排序。使用 -EALREADY 的重复条目检测的语义与上面的方法 1 相同。但是列表重新排序允许使用更符合习惯的代码

int lock_objs(struct list_head *list, struct ww_acquire_ctx *ctx)
{
      struct obj_entry *entry, *entry2;

      ww_acquire_init(ctx, &ww_class);

      list_for_each_entry (entry, list, head) {
              ret = ww_mutex_lock(&entry->obj->lock, ctx);
              if (ret < 0) {
                      entry2 = entry;

                      list_for_each_entry_continue_reverse (entry2, list, head)
                              ww_mutex_unlock(&entry2->obj->lock);

                      if (ret != -EDEADLK) {
                              ww_acquire_fini(ctx);
                              return ret;
                      }

                      /* we lost out in a seqno race, lock and retry.. */
                      ww_mutex_lock_slow(&entry->obj->lock, ctx);

                      /*
                       * Move buf to head of the list, this will point
                       * buf->next to the first unlocked entry,
                       * restarting the for loop.
                       */
                      list_del(&entry->head);
                      list_add(&entry->head, list);
              }
      }

      ww_acquire_done(ctx);
      return 0;
}

对于方法 #1 和 #2，解锁的工作方式相同

void unlock_objs(struct list_head *list, struct ww_acquire_ctx *ctx)
{
      struct obj_entry *entry;

      list_for_each_entry (entry, list, head)
              ww_mutex_unlock(&entry->obj->lock);

      ww_acquire_fini(ctx);
}

如果对象的列表是临时构造的而不是预先构造的，则方法 3 非常有用，例如，在图中调整边缘时，每个节点都有自己的 ww_mutex 锁，并且只有在持有所有涉及节点的锁时才能更改边缘。w/w 互斥锁非常适合这种情况，原因有两个

它们可以按任何顺序处理锁获取，这允许我们从起点开始遍历图，然后迭代地发现新边缘并锁定这些边缘连接到的节点。
由于 -EALREADY 返回代码表示给定的对象已被持有，因此无需额外的簿记来打破图中的循环或跟踪哪些查找已被持有（当使用多个节点作为起点时）。

请注意，此方法与上述方法在两个重要方面有所不同

由于对象列表是动态构造的（并且在由于遇到 -EDEADLK 终止条件而重试时可能非常不同），因此无需在对象未锁定时将任何对象保留在持久列表中。因此，我们可以将 list_head 移动到对象本身中。
另一方面，动态对象列表构造也意味着无法传播 -EALREADY 返回代码。

另请注意，可以组合方法 #1 和 #2 以及方法 #3，例如，首先使用上述方法之一锁定起始节点列表（从用户空间传入）。然后锁定使用下面的方法 #3 影响的任何其他对象。回退/重试过程会更复杂一些，因为当动态锁定步骤遇到 -EDEADLK 时，我们还需要解锁使用固定列表获取的所有对象。但是 w/w 互斥锁调试检查将捕获这些情况下的任何接口滥用。

此外，方法 3 不会使锁获取步骤失败，因为它不会返回 -EALREADY。当然，当使用 _interruptible 变体时，情况会有所不同，但这超出了此处这些示例的范围

struct obj {
      struct ww_mutex ww_mutex;
      struct list_head locked_list;
};

static DEFINE_WW_CLASS(ww_class);

void __unlock_objs(struct list_head *list)
{
      struct obj *entry, *temp;

      list_for_each_entry_safe (entry, temp, list, locked_list) {
              /* need to do that before unlocking, since only the current lock holder is
              allowed to use object */
              list_del(&entry->locked_list);
              ww_mutex_unlock(entry->ww_mutex)
      }
}

void lock_objs(struct list_head *list, struct ww_acquire_ctx *ctx)
{
      struct obj *obj;

      ww_acquire_init(ctx, &ww_class);

retry:
      /* re-init loop start state */
      loop {
              /* magic code which walks over a graph and decides which objects
               * to lock */

              ret = ww_mutex_lock(obj->ww_mutex, ctx);
              if (ret == -EALREADY) {
                      /* we have that one already, get to the next object */
                      continue;
              }
              if (ret == -EDEADLK) {
                      __unlock_objs(list);

                      ww_mutex_lock_slow(obj, ctx);
                      list_add(&entry->locked_list, list);
                      goto retry;
              }

              /* locked a new object, add it to the list */
              list_add_tail(&entry->locked_list, list);
      }

      ww_acquire_done(ctx);
      return 0;
}

void unlock_objs(struct list_head *list, struct ww_acquire_ctx *ctx)
{
      __unlock_objs(list);
      ww_acquire_fini(ctx);
}

方法 4：仅锁定一个对象。在这种情况下，死锁检测和预防显然是过度杀伤，因为仅使用一个锁就无法在单个类中产生死锁。为了简化这种情况，w/w 互斥锁 API 可以与 NULL 上下文一起使用。

实现细节¶

设计：¶

ww_mutex 当前封装了一个 struct mutex，这意味着对于更常见的普通互斥锁，没有额外的开销。因此，如果不使用 wait/wound 互斥锁，代码大小只会略有增加。

我们为等待列表维护以下不变性

具有获取上下文的等待者按时间戳顺序排序；没有获取上下文的等待者以 FIFO 顺序穿插。

对于 Wait-Die，在具有上下文的等待者中，只有第一个可以已经获取了其他锁 (ctx->acquired > 0)。请注意，此等待者可能在列表中没有上下文的其他等待者之后出现。

Wound-Wait 抢占是通过延迟抢占方案实现的：仅当争用新锁并且真正存在死锁机会时，才检查事务的“伤害”状态。在这种情况下，如果事务受到“伤害”，它会退避，清除“伤害”状态并重试。以这种方式实现抢占的一个巨大好处是，“受伤”事务可以识别争用锁，以便在重新启动事务之前等待。盲目地重新启动事务可能会使事务最终陷入不得不再次退避的情况。

总的来说，预计不会有太多的争用。这些锁通常用于序列化对设备资源的访问，因此优化重点应放在非争用情况上。

Lockdep：¶

已特别注意警告尽可能多的 api 滥用情况。一些常见的 api 滥用将通过 CONFIG_DEBUG_MUTEXES 捕获，但建议使用 CONFIG_PROVE_LOCKING。

将警告的一些错误

忘记调用 ww_acquire_fini 或 ww_acquire_init。

在 ww_acquire_done 之后尝试锁定更多互斥锁。

在 -EDEADLK 之后尝试锁定错误的互斥锁并解锁所有互斥锁。

在 -EDEADLK 之后，在解锁所有互斥锁之前，尝试锁定正确的互斥锁。

在返回 -EDEADLK 之前调用 ww_mutex_lock_slow。

使用错误的解锁函数解锁互斥锁。

在同一上下文中两次调用 ww_acquire_* 之一。

对互斥锁使用与 ww_acquire_ctx 不同的 ww_class。

可能导致死锁的正常 lockdep 错误。

可能导致死锁的一些 lockdep 错误

在对第一个 ww_acquire_ctx 调用 ww_acquire_fini 之前，调用 ww_acquire_init 以初始化第二个 ww_acquire_ctx。

可能发生的“正常”死锁。

待办事项: 一旦我们实现了 TASK_DEADLOCK 任务状态标志魔术，就更新此部分。

Linux 内核

目录

本页

Wound/Wait 防死锁互斥锁设计¶

WW-互斥锁的动机¶

概念¶

用法¶

实现细节¶

设计：¶

Lockdep：¶