as "lockdep") is one of the community's most useful pro-active debugging
tools. Since its introduction in 2006, it has eliminated most
from the system. Given that deadlocks can be extremely difficult
to reproduce and diagnose, the result is a far more reliable kernel and
happier users. There
is a shortage of equivalent tools for user-space programming, despite the
fact that deadlock issues can happen there as well. As it happens, making
lockdep available in user space may be far easier than almost anybody might
Lockdep works by adding wrappers around the locking calls in the kernel.
Every time a
specific type of lock is taken or released, that fact is noted, along with
ancillary details like whether the processor was servicing an interrupt at
the time. Lockdep also notes which other locks were already held when the
new lock is taken; that is the key to much of the checking that lockdep is
able to perform.
To illustrate this point, imagine that two threads each need to acquire two
locks, called A and B:
If one thread acquires A first
while the other grabs B first, the situation might look something
Now, when each
thread goes for the lock it lacks, the system is in trouble:
Each thread will now wait forever for the other to release the lock it
holds; the system is now deadlocked. Things may not come to this point
often at all; this deadlock requires each thread to acquire its lock at
exactly the wrong time. But, with computers, even highly unlikely events
will come to pass sooner or later, usually at a highly inopportune time.
This situation can be avoided: if both threads adhere to a rule
stating that A must always be acquired before B, this
particular deadlock (called an "AB-BA deadlock" for obvious reasons) cannot
happen. But, in a system with a large number of locks, it is not always
clear what the rules for locking are, much less that they are consistently
followed. Mistakes are easy to make. That is where lockdep comes in:
by tracking the order of lock acquisition, lockdep can raise the
alarm anytime it sees a thread acquire A while already holding
B. No actual deadlock is required to get a "splat" (a report of a
locking problem) out of lockdep,
meaning that even highly unlikely deadlock situations can be found before
they ruin somebody's day. There is no need to wait for that one time when
the timing is exactly wrong to see that there is a problem.
Lockdep is able to detect more complicated deadlock scenarios than the one
described above. It can also detect related problems, such as locks that
are not interrupt-safe being acquired in interrupt context. As one might
expect, running a kernel with lockdep enabled tends to slow things down
considerably; it is not an option that one would enable on a production
system. But enough developers test with lockdep enabled that most problems
are found before they make their way into a stable kernel release. As a
result, reports of deadlocks on deployed systems are now quite rare.
Kernel-based tools often do not move readily to user space; the kernel's
programming environment differs markedly from a normal C environment, so
kernel code can normally only be expected to run in the kernel itself. In
this case, though, Sasha Levin noticed that there is not much in the
lockdep subsystem that is truly kernel-specific. Lockdep collects data and
builds graphs describing observed lock acquisition patterns; it is code
that could be run in a non-kernel context relatively easily.
So Sasha proceeded to put
together a patch set creating a lockdep
library that is available to programs in user space.
Lockdep does, naturally, call a number of kernel functions, so a big part
of Sasha's patch set is a long list of stub implementations shorting out
calls to functions like local_irq_enable() that have no meaning in
user space. An abbreviated version of struct task_struct is
provided to track threads in user space, and functions like
print_stack_trace() are substituted with user-space equivalents
(backtrace_symbols_fd() in this case). The kernel's internal
(used by lockdep) locks are reimplemented using POSIX thread ("pthread")
mutexes. Stub versions of
the include files used by the lockdep code are provided in a special
directory. And so on. Once all that is
done, the lockdep code can be built directly out of the kernel tree and
turned into a library.
User-space code wanting to take advantage of the lockdep library needs to
start by including <liblockdep/mutex.h>, which, among other
things, adds a set of wrappers around the pthread_mutex_t and
pthread_rwlock_t types and
the functions that work with them. A call to liblockdep_init() is
required; each thread should also make a call to
liblockdep_set_thread() to set up information for any problem
reports. That is about all that is required; programs that are
instrumented in this way will have their pthreads mutex and
rwlock usage checked by lockdep.
As a proof of concept, the patch adds instrumentation to the (thread-based)
perf tool contained within the kernel source tree.
One of the key aspects of Sasha's patch is that it requires no changes to
the in-kernel lockdep code at all. The user-space lockdep library can be
built directly out of the kernel tree. Among other things, that means that
any future lockdep fixes and enhancements will automatically become
available to user space with no additional effort required on the
kernel developers' part.
In summary, this patch looks like a significant win for everybody involved;
it is thus not surprising that opposition to its inclusion has been hard to
find. There has been a call for some
better documentation, explicit mention that the resulting user-space
library is GPL-licensed, and a runtime toggle for lock validation (so that
the library could be built into applications but not actually track locking
unless requested). Such
details should not be hard to fill in, though. So, with luck, user space
should have access to lockdep in the near future, resulting in more
reliable lock usage.
to post comments)