Wound/Wait 防死锁互斥锁设计¶
请先阅读 通用互斥锁子系统，因为它同样适用于 wait/wound 互斥锁。
WW-Mutex 的设计动机¶
GPU 的操作通常涉及许多缓冲区（buffer）。这些缓冲区可以在上下文/进程之间共享，存在于不同的内存域中（例如 VRAM 与系统内存），等等。通过 PRIME / dmabuf，它们甚至可以跨设备共享。因此，在许多情况下，驱动程序需要等待缓冲区准备就绪。如果你从等待缓冲区互斥锁变为可用这一角度来考虑，这就会带来一个问题：无法保证缓冲区在所有上下文中的 execbuf/batch 里以相同的顺序出现。这是由用户空间直接控制的，并且是应用程序发起的 GL 调用序列的结果。这就会导致潜在的死锁。当你考虑到内核可能需要在 GPU 操作缓冲区之前将缓冲区迁移到 VRAM 中时，问题会变得更加复杂，这反过来可能需要换出（evicting）其他一些缓冲区（而你肯定不想换出已经排队等待 GPU 处理的其他缓冲区），但为了简化对该问题的理解，你可以忽略这一点。
TTM 图形子系统为解决这个问题提出的算法相当简单。对于需要锁定的每组缓冲区（execbuf），调用者将从全局计数器中分配到一个唯一的保留 ID/票据（reservation id/ticket）。如果在锁定与 execbuf 相关的所有缓冲区时发生死锁，拥有最低保留票据（即最旧的任务）的一方获胜，而拥有较高保留 ID（即年轻的任务）的一方会解锁其已锁定的所有缓冲区，然后重试。
在 RDBMS 文献中，保留票据与事务相关联，这种死锁处理方法被称为 Wait-Die（等待-死亡）。该名称基于加锁线程在遇到已被锁定的互斥锁时的动作。如果持有锁的事务较年轻，则加锁事务等待。如果持有锁的事务较年长，则加锁事务退避并死亡（die）。因此得名 Wait-Die。还有另一种名为 Wound-Wait（负伤-等待）的算法：如果持有锁的事务较年轻，则加锁事务会“伤害”（wound）持有锁的事务，请求其死亡。如果持有锁的事务较年长，则它会等待另一个事务。因此得名 Wound-Wait。这两种算法都是公平的，因为事务最终都会成功。然而，通常认为 Wound-Wait 算法比 Wait-Die 产生更少的退避，但另一方面，从退避中恢复时，Wound-Wait 比 Wait-Die 需要更多的工作。Wound-Wait 也是一种抢占式算法，因为事务会被其他事务“伤害”，这需要一种可靠的方式来捕获受损状态并抢占正在运行的事务。请注意，这与进程抢占不同。Wound-Wait 事务在受损后死亡（返回 -EDEADLK）时，即被视为已被抢占。
概念¶
与普通互斥锁相比，w/w 互斥锁的锁接口中出现了两个额外的概念/对象：
获取上下文（Acquire context）：为了确保最终的前进（forward progress），尝试获取锁的任务不能获取新的保留 ID，而是必须保留它在开始获取锁时获得的那一个，这一点非常重要。该票据存储在获取上下文中。此外，获取上下文还跟踪调试状态，以捕获对 w/w 互斥锁接口的滥用。获取上下文代表了一个事务。
W/w 类（W/w class）：与普通互斥锁不同，对于 w/w 互斥锁，锁类（lock class）必须是显式的，因为初始化获取上下文时需要它。锁类还指定要使用哪种算法：Wound-Wait 还是 Wait-Die。
此外，还有三类不同的 w/w 锁获取函数：
使用上下文的常规锁获取，使用 ww_mutex_lock。
对竞争锁的慢路径（slowpath）锁获取，由刚刚终止其事务（在放弃所有已获取的锁之后）的任务使用。这些函数带有 _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 中不允许重新排序的列表。如果所需对象的列表已经在某处被跟踪，这将非常有用。此外，锁辅助函数（lock helper）可以将 -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 进行重复条目检测的语义。但列表重新排序允许编写更符合习惯的代码（idiomatic code）。
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);
}
如果对象列表是临时（ad-hoc）构建的而不是预先构建的，则方法 3 非常有用。例如，在调整图中的边时，其中每个节点都有自己的 ww_mutex 锁，并且只有在持有所有相关节点的锁时才能更改边。由于以下两个原因，w/w 互斥锁非常适合这种情况：
它们可以处理任意顺序的加锁操作，这允许我们从一个起点开始遍历图，然后迭代地发现新边并锁定这些边所连接的节点。
由于 -EALREADY 返回代码表明给定对象已经被持有，因此无需进行额外的记账（book-keeping）来打破图中的循环，也无需跟踪哪些锁已经被持有（当使用多个节点作为起点时）。
请注意，这种方法在两个重要方面与上述方法不同：
由于对象列表是动态构建的（并且在由于命中 -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：仅锁定单个对象。在这种情况下，死锁检测和预防显然是大材小用（overkill），因为仅获取一个锁无法在单个类中产生死锁。为了简化这种情况，可以将 w/w 互斥锁 API 与 NULL 上下文一起使用。
实现细节¶
设计：¶
ww_mutex 目前封装了一个
struct mutex，这意味着对于更为常见的普通互斥锁，没有额外的开销。因此，如果不使用 wait/wound 互斥锁，代码大小只会略有增加。我们为等待列表维护以下不变量（invariants）：
带有获取上下文的等待者按时间戳（stamp）顺序排序；不带获取上下文的等待者以 FIFO（先进先出）顺序穿插其中。
对于 Wait-Die，在带有上下文的等待者中，只有第一个等待者可以已经获取了其他锁（ctx->acquired > 0）。注意，这个等待者可能会排在列表中其他没有上下文的等待者之后。
Wound-Wait 的抢占是通过惰性抢占（lazy-preemption）方案实现的：仅当对新锁存在竞争且因此存在真正发生死锁的机会时，才检查事务的受损（wounded）状态。在这种情况下，如果事务受损，它会退避、清除受损状态并重试。以这种方式实现抢占的一个巨大好处是，受损事务可以在重新启动事务之前确定要等待的竞争锁。盲目地重新启动事务很可能会使事务陷入不得不再次退避的境地。
通常，预计不会有太多的竞争。这些锁通常用于串行化设备资源的访问，因此优化的重点应放在无竞争的情况上。
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_class 与 ww_acquire_ctx 使用的不同。
可能导致死锁的常规 lockdep 错误。
- 可能导致死锁的一些 lockdep 错误：
在对第一个 ww_acquire_ctx 调用 ww_acquire_fini 之前，调用 ww_acquire_init 初始化第二个 ww_acquire_ctx。
可能发生的“常规”死锁。
- 待修复 (FIXME)
一旦实现 TASK_DEADLOCK 任务状态标志的魔术（magic），请更新此节。