Wound/Wait Deadlock-Proof Mutex Design — The Linux Kernel documentation

The Linux Kernel

7.2.0

Quick search

Contents

Development process

Submitting patches

Code of conduct

Maintainer handbook

All development-process docs

Core API

Driver APIs

Subsystems

Locking<br>Lock types and their rules

Runtime locking correctness validator

Lock Statistics

Kernel Lock Torture Test Operation

Generic Mutex Subsystem

RT-mutex implementation design

RT-mutex subsystem with PI support

Sequence counters and sequential locks

Locking lessons

Wound/Wait Deadlock-Proof Mutex Design<br>Motivation for WW-Mutexes

Concepts

Usage

Implementation Details

Proper Locking Under a Preemptible Kernel: Keeping Kernel Code Preempt-Safe

Lightweight PI-futexes

Futex Requeue PI

Hardware Spinlock Framework

Percpu rw semaphores

A description of what robust futexes are

The robust futex ABI

Licensing rules

Writing documentation

Development tools

Testing guide

Hacking guide

Tracing

Fault injection

Livepatching

Rust

Administration

Build system

Reporting issues

Userspace tools

Userspace API

Firmware

Firmware and Devicetree

CPU architectures

Unsorted documentation

Translations

This Page

Show Source

Wound/Wait Deadlock-Proof Mutex Design¶

Please read Generic Mutex Subsystem first, as it applies to wait/wound mutexes too.

Motivation for WW-Mutexes¶

GPU’s do operations that commonly involve many buffers. Those buffers<br>can be shared across contexts/processes, exist in different memory<br>domains (for example VRAM vs system memory), and so on. And with<br>PRIME / dmabuf, they can even be shared across devices. So there are<br>a handful of situations where the driver needs to wait for buffers to<br>become ready. If you think about this in terms of waiting on a buffer<br>mutex for it to become available, this presents a problem because<br>there is no way to guarantee that buffers appear in a execbuf/batch in<br>the same order in all contexts. That is directly under control of<br>userspace, and a result of the sequence of GL calls that an application<br>makes. Which results in the potential for deadlock. The problem gets<br>more complex when you consider that the kernel may need to migrate the<br>buffer(s) into VRAM before the GPU operates on the buffer(s), which<br>may in turn require evicting some other buffers (and you don’t want to<br>evict other buffers which are already queued up to the GPU), but for a<br>simplified understanding of the problem you can ignore this.

The algorithm that the TTM graphics subsystem came up with for dealing with<br>this problem is quite simple. For each group of buffers (execbuf) that need<br>to be locked, the caller would be assigned a unique reservation id/ticket,<br>from a global counter. In case of deadlock while locking all the buffers<br>associated with a execbuf, the one with the lowest reservation ticket (i.e.<br>the oldest task) wins, and the one with the higher reservation id (i.e. the<br>younger task) unlocks all of the buffers that it has already locked, and then<br>tries again.

In the RDBMS literature, a reservation ticket is associated with a transaction.<br>and the deadlock handling approach is called Wait-Die. The name is based on<br>the actions of a locking thread when it encounters an already locked mutex.<br>If the transaction holding the lock is younger, the locking transaction waits.<br>If the transaction holding the lock is older, the locking transaction backs off<br>and dies. Hence Wait-Die.<br>There is also another algorithm called Wound-Wait:<br>If the transaction holding the lock is younger, the locking transaction<br>wounds the transaction holding the lock, requesting it to die.<br>If the transaction holding the lock is older, it waits for the other<br>transaction. Hence Wound-Wait.<br>The two algorithms are both fair in that a transaction will eventually succeed.<br>However, the Wound-Wait algorithm is typically stated to generate fewer backoffs<br>compared to Wait-Die, but is, on the other hand, associated with more work than<br>Wait-Die when recovering from a backoff. Wound-Wait is also a preemptive<br>algorithm in that transactions are wounded by other transactions, and that<br>requires a reliable way to pick up the wounded condition and preempt the<br>running transaction. Note that this is not the same as process preemption. A<br>Wound-Wait transaction is considered preempted when it dies (returning<br>-EDEADLK) following a wound.

Concepts¶

Compared to normal mutexes two additional concepts/objects show up in the lock<br>interface for w/w mutexes:

Acquire context: To ensure eventual forward progress it is important that a task<br>trying to acquire locks doesn’t grab a new reservation id, but keeps the one it<br>acquired when starting the lock acquisition. This ticket is stored in the<br>acquire context. Furthermore the acquire context keeps track of debugging state<br>to catch w/w mutex interface abuse. An acquire context is representing a<br>transaction.

W/w class: In contrast to normal mutexes the lock class needs to be explicit for<br>w/w mutexes, since it is required to...