• https://www.kernel.org/doc/html/v6.6/locking/ww-mutex-design.html

Wound/Wait死锁安全的互斥锁设计

请先阅读通用互斥锁子系统，因为它也适用于等待/伤害互斥锁。

WW-互斥锁的动机

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

TTM图形子系统为解决这个问题提出的算法非常简单。对于需要被锁定的每组缓冲区（execbuf），调用者将被分配一个唯一的预留ID/票据，来自全局计数器。在锁定与execbuf相关的所有缓冲区时发生死锁时，具有最低预留票据（即最老的任务）的任务获胜，具有较高预留ID（即较年轻的任务）的任务解锁它已经锁定的所有缓冲区，然后再次尝试。

在关系数据库管理系统（RDBMS）文献中，预留票据与事务相关联，死锁处理方法称为等待-死亡（Wait-Die）。名称基于锁定线程在遇到已锁定的互斥锁时的操作。如果持有锁的事务较年轻，则锁定事务等待。如果持有锁的事务较老，则锁定事务后退并死亡。因此称为等待-死亡。还有另一种算法称为伤害-等待（Wound-Wait）：如果持有锁的事务较年轻，则锁定事务伤害持有锁的事务，要求其死亡。如果持有锁的事务较老，则等待另一个事务。因此称为伤害-等待。这两种算法都是公平的，因为事务最终将成功。然而，通常说伤害-等待算法与等待-死亡相比会生成更少的后退，但另一方面，当从后退中恢复时，与等待-死亡相比，伤害-等待需要更多的工作。伤害-等待也是一种抢占算法，事务被其他事务伤害，这需要一种可靠的方式来捕获受伤的状态并抢占正在运行的事务。请注意，这与进程抢占不同。当伤害-等待事务死亡（返回-EDEADLK）时，被视为被抢占。

概念

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

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

w/w类：与普通互斥锁相比，对于w/w互斥锁，锁类需要是显式的，因为需要初始化获取上下文。锁类还指定要使用的算法，伤害-等待或等待-死亡。

此外，有三种不同类别的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互斥锁的函数，这将产生与普通互斥锁完全相同的语义。这是通过使用空上下文调用ww_mutex_lock来实现的。
  

再次强调，这并不是严格要求的。但通常你只想获取一个单独的锁，在这种情况下设置获取上下文是没有意义的（因此最好避免获取死锁避免票据）。

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

使用

通过使用DEFINE_WW_CLASS()（Wound-Wait）或DEFINE_WD_CLASS()（Wait-Die）来选择算法（Wait-Die vs Wound-Wait）。作为一个粗略的经验法则，如果你预计同时竞争的事务数量通常较少，并且希望减少回滚的次数，那么使用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中可以重新排序的列表。与方法1相同，使用-EALREADY进行重复条目检测的语义。但是列表重新排序允许更具惯用性的代码：

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) {
/* 在解锁之前需要这样做，因为只有当前锁持有者才能使用对象 */
              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:
/* 重新初始化循环起始状态 */
      loop {
/* 魔术代码，遍历图并决定要锁定哪些对象 */
              ret = ww_mutex_lock(obj->ww_mutex, ctx);
if (ret == -EALREADY) {
/* 我们已经有了这个，转到下一个对象 */
continue;
              }
if (ret == -EDEADLK) {
                      __unlock_objs(list);
                      ww_mutex_lock_slow(obj, ctx);
                      list_add(&entry->locked_list, list);
goto retry;
              }
/* 锁定了一个新对象，将其添加到列表中 */
              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：仅锁定单个对象。在这种情况下，死锁检测和预防显然是多余的，因为仅仅获取一个锁就不可能在一个类中产生死锁。为了简化这种情况，可以使用带有NULL上下文的w/w互斥体API。

实施细节

设计：

ww_mutex目前封装了一个struct mutex，这意味着对于常见的互斥锁，没有额外的开销。因此，如果不使用等待/抢占互斥锁，代码大小只会略微增加。

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

1. 拥有获取上下文的等待者按时间戳顺序排序；没有获取上下文的等待者按FIFO顺序交错排列。
   
2. 对于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任务状态标志的魔法后，更新此部分。