The dependency tracker for complex deadlock detection

Deadlocks are a constant threat in concurrent settings with shared data; it is thus not surprising that the kernel project has long since developed tools to detect potential deadlocks so they can be fixed before they affect production users. Byungchul Park thinks that he has developed a better tool that can detect more deadlock-prone situations. At the 2025 Open Source Summit Europe, he presented an introduction to his dependency tracker (or "DEPT") tool and the kinds of problems it can detect.

Park began by presenting a simple ABBA deadlock scenario. Imagine two threads running, each of which makes use of two locks, called A and B. The first thread acquires A, then B, ending up holding both locks; meanwhile, the second thread acquires the same two locks but in the opposite order, taking B first. That can work, until the bad day when each thread succeeds in taking the first of its two locks. Then one holds A, the other holds B, and each is waiting for the other to release the second lock it needs. They will wait for a long time.

Deadlocks like this can be hard to reproduce, and thus hard to track down and fix; it is far better to detect the possibility of such a deadlock ahead of time. The kernel has a tool called "lockdep", originally written by Ingo Molnar, that can perform this detection. Whenever a thread acquires a lock, lockdep remembers that acquisition, along with the context — specifically, any other locks that are currently held. It will thus notice that, in the first case, A is acquired ahead of B. When lockdep observes the second thread acquiring the locks in the opposite order, it will raise the alarm. The problem can then be fixed, hopefully before this particular deadlock ever occurs on a production system.

Park continued with a more complex example, presented in this form:

Thread X	Thread Y	Thread Z
mutex_lock(A)	mutex_lock(C)
	mutex_lock(A)	mutex_lock(C)
wait_for_event(B)
	mutex_unlock(A)	mutex_unlock(C)
mutex_unlock(A)	mutex_unlock(C)
		event B

Thread Y, holding lock C, will be blocked waiting for A to become available. Thread Z, meanwhile, is blocked waiting for C. Thread X is waiting for some sort of event to happen; it is up to Z to produce that event, but that will never happen because Z is waiting on a chain of locks leading back to A, held by X. Park's point here is that deadlocks are not driven only by locks, other types of events can be part of deadlock scenarios as well. Lockdep, being focused on locks, is unable to detect these cases.

Park's DEPT tool, currently in its 16th revision, is meant to address this type of problem. The core idea behind DEPT is a new definition of a dependency; while lockdep sees dependencies as lock acquisitions, DEPT looks at events more generally. If one event occurs prior to another, DEPT will notice the dependency between them. In the example above, the release of A depends on the occurrence of B, which in turn depends on the release of C, which itself depends on the release of A. That is a dependency loop that can cause a deadlock; DEPT will duly report it.

Back in 2023, kernel developers were beating their heads against a complex deadlock problem, and Linus Torvalds asked whether DEPT might be able to track the problem down. Using DEPT, Park was able to pinpoint the problem, which involved a wait on a bit lock; events involving bit locks are invisible to lockdep. Earlier this year, Andrew Morton was struggling with a similar problem:

Nostalgia. A decade or three ago many of us spent much of our lives staring at ABBA deadlocks. Then came lockdep and after a few more years, it all stopped. I've long hoped that lockdep would gain a solution to custom locks such as folio_wait_bit_common(), but not yet.

He, too, asked if DEPT could find this problem; once again, DEPT located the deadlock so that it could be fixed.

DEPT, Park said, has a number of benefits, starting with the fact that it uses a more generalized concept of dependencies rather than just looking at specific locks. It can handle situations involving folio locks, completions, or DMA fences that lockdep cannot. DEPT is also able to properly deal with reader-writer locks. It is, he said, less likely than lockdep to generate false-positive reports, and it is able to continue operating after the first report (unlike lockdep, which shuts down once a problem is found).

Lockdep, he allowed, is better in that it produces far fewer false-positive reports now; he noted that kernel developers have spent 20 years achieving that result. It will, though, miss some deadlock situations. In cases where the deadlock scenario is more complex than lockdep can handle, he concluded, DEPT should be used instead.

I could not resist asking why DEPT is not upstream after 16 revisions and more than three years (the first version was posted in February 2022). Park answered that the real source of resistance is the number of false positives. Lockdep is just a lot quieter.

Another attendee said that, since DEPT is a build-time option, it is hard to use with problems that affect production systems in the field; he suggested that perhaps an approach using BPF would be useful. Park agreed, but seemed to not have considered the BPF option until now; he said that he would look into it.

Finally, another audience member said that he did not think that the false-positive problem should block the merging of this code; he asked what the real problem is. Park did not answer that question, but declared that he would keep working on the code until he manages to get it upstream.

After the talk, with beer in hand, I asked a core-kernel developer about why DEPT has run into resistance. The answer was indeed false positives; the tool generates so many reports that it is difficult to get a real signal out of the noise. The root of the problem, they said, was that Park is attempting to replace lockdep all at once with a large patch set. Something like DEPT could be useful and welcome, but it would need to go upstream as a set of smaller changes that evolve lockdep into something with DEPT's view of dependencies, making the kernel better with every step. Until that approach is taken, attempts to merge DEPT into the mainline are unlikely to be successful.

The slides from Park's talk are available for interested readers.

[Thanks to the Linux Foundation, LWN's travel sponsor, for supporting my travel to this event.]

Index entries for this article
Kernel	Development tools
Conference	Open Source Summit Europe/2025

---

to post comments