« Previous Lecture | Next Lecture »
An AB-BA deadlock is the most common multi-lock deadlock you will run into in real kernel code, and it needs no bug in either individual function — only two threads disagreeing on which lock to take first. In this lecture we build the scenario from scratch on a kernel 6.x system, watch lockdep catch it, and set the lock-ordering discipline that prevents it for good.
This lecture builds directly on the previous one, where we learned to read a lockdep self-deadlock report. Make sure you understand the “trying to acquire” / “already holding” report structure and the lock identity hash before continuing.
What Makes It “AB-BA”
Picture two locks, which we’ll call lock A and lock B, and two independent threads of execution — for example, two kernel threads pinned to two different CPU cores. If thread 1 always takes A first and then B, while thread 2 always takes B first and then A, you have created the exact conditions for a circular wait: each thread can end up holding the lock the other one needs next, and neither can proceed. Neither thread’s code is wrong in isolation. The bug only exists in the relationship between the two.
—————- —————-
lock(A) lock(B)
…work… …work…
lock(B) ←—— waits on Thread 2 lock(A) ←—— waits on Thread 1
● DEADLOCK ●
each thread holds what the other needs
Building the Scenario: An Original Demo Driver
Below is an original module, written for this course, that intentionally reproduces an AB-BA deadlock so you can see lockdep catch it on your own kernel 6.x test machine. Two kernel threads are pinned one-per-CPU using kthread_bind() (covered a few lectures back). A module parameter, ep_wrong_order, controls whether the second thread deliberately violates the agreed lock order:
#include <linux/kthread.h>
#include <linux/spinlock.h>
#include <linux/delay.h>
#include <linux/module.h>
static bool ep_wrong_order;
module_param(ep_wrong_order, bool, 0644);
static DEFINE_SPINLOCK(ep_lockA);
static DEFINE_SPINLOCK(ep_lockB);
static struct task_struct *ep_t1, *ep_t2;
/* Documented rule for this driver: always take lockA before lockB */
static int ep_worker_correct_order(void *arg)
{
while (!kthread_should_stop()) {
spin_lock(&ep_lockA);
msleep(50); /* widen the race window for the demo */
spin_lock(&ep_lockB);
/* ... protected work here ... */
spin_unlock(&ep_lockB);
spin_unlock(&ep_lockA);
msleep(200);
}
return 0;
}
/* Second thread: obeys the rule unless ep_wrong_order=1 is set */
static int ep_worker_second(void *arg)
{
while (!kthread_should_stop()) {
if (ep_wrong_order) {
spin_lock(&ep_lockB); /* violates agreed A-before-B order */
msleep(50);
spin_lock(&ep_lockA);
} else {
spin_lock(&ep_lockA);
msleep(50);
spin_lock(&ep_lockB);
}
/* ... protected work here ... */
spin_unlock(&ep_lockB);
spin_unlock(&ep_lockA);
msleep(200);
}
return 0;
}With ep_wrong_order=0, both threads always take lockA first, so there is no circular wait and the module runs indefinitely without issue. Set ep_wrong_order=1 and reload, and on a lockdep-enabled kernel you will see a "possible circular locking dependency detected" warning printed the very first time both threads race into the mismatched order — often before an actual hang occurs, because lockdep proves the cycle is possible rather than waiting to experience it.
How Lockdep Proves the Cycle
Lockdep does not need to catch both threads deadlocked at the same instant to warn you. It maintains a directed graph of every “lock X was taken while lock Y was already held” relationship it has ever observed. The moment it sees “A then B” recorded from one code path and “B then A” recorded from another, it has proof of a cycle in that graph — which is mathematically sufficient to guarantee a deadlock is possible, regardless of whether your specific test run happened to hit the exact timing. This is what makes lockdep far more powerful than simply waiting for a hang: it finds latent deadlocks that might only occur once in a million boots under production timing.
Observed ordering #2: lockB –> lockA (from ep_worker_second, wrong_order=1)
lockA → lockB
↑ ↓
lockB ← lockA (cycle = deadlock is possible)
The Fix: A Single Documented Lock Order
There is exactly one durable fix for an AB-BA deadlock: pick one global order for every lock that can be held together, document it near the lock declarations, and make every code path — no exceptions — follow it. In the demo above, the fix is simply keeping ep_wrong_order at its default of 0 in real code, i.e. deleting the alternate branch entirely so the “wrong” ordering is not even reachable. In a real driver with several locks, teams typically write the agreed order as a comment directly above the lock definitions, exactly as we did with the /* always lockA before lockB */ comment, so future contributors cannot introduce a reversed path by accident.
If a genuine need exists to take locks in varying order at runtime (for example, locking two dynamically chosen objects of the same type), the standard kernel technique is to always lock the object with the lower memory address first — this guarantees a consistent global order without needing a fixed compile-time rule. That technique is used throughout the kernel’s own inode and dentry locking code.
Do both threads need to run at the exact same instant to deadlock?
No. They need to race into their mismatched acquire order at some point, which can happen rarely under real workloads. This is exactly why AB-BA deadlocks are notorious for passing testing and appearing only in production, and why lockdep’s ordering-graph approach is so valuable.
Can an AB-BA deadlock happen with more than two locks?
Yes — the same circular-wait principle extends to three or more locks, sometimes called an AB-BC-CA chain. Lockdep’s dependency graph detects cycles of any length, not just simple two-lock pairs.
Does using mutexes instead of spinlocks avoid AB-BA deadlocks?
No. The circular-wait problem is about lock ordering, not about which primitive is used. Mutexes, spinlocks, and semaphores are all equally vulnerable, and lockdep tracks all of them through the same dependency graph.
What if I genuinely need to lock two objects of the same type in varying order?
Use a consistent tie-breaker such as always locking the object at the lower memory address first. This produces a stable global order at runtime even though the “which object comes first” decision is dynamic.
Will lockdep catch this in normal use, or do I need to force both orderings to appear?
Lockdep only knows about orderings it has actually observed being taken. If your test never exercises the reversed path, lockdep cannot yet know it’s dangerous. This is why documenting and code-reviewing lock order matters even with lockdep enabled — it complements, but does not replace, disciplined locking design.
Is kthread_bind() required to reproduce this demo?
It is not strictly required — the deadlock can occur on a single CPU too, through preemption — but binding each kernel thread to its own CPU core makes the race far more reliable to reproduce for learning purposes.
Continue the Free Linux Kernel Programming Course
More hands-on lectures on kernel synchronization, device drivers, and debugging — all free.
Next Lecture Course Index
2 Comments