Lock-class¶

The basic object the validator operates upon is a ‘class’ of locks.

A class of locks is a group of locks that are logically the same withrespect to locking rules, even if the locks may have multiple (possiblytens of thousands of) instantiations. For example a lock in the inodestruct is one class, while each inode has its own instantiation of thatlock class.

The validator tracks the ‘usage state’ of lock-classes, and it tracksthe dependencies between different lock-classes. Lock usage indicateshow a lock is used with regard to its IRQ contexts, while lockdependency can be understood as lock order, where L1 -> L2 suggests thata task is attempting to acquire L2 while holding L1. From lockdep’sperspective, the two locks (L1 and L2) are not necessarily related; thatdependency just means the order ever happened. The validator maintains acontinuing effort to prove lock usages and dependencies are correct orthe validator will shoot a splat if incorrect.

A lock-class’s behavior is constructed by its instances collectively:when the first instance of a lock-class is used after bootup the classgets registered, then all (subsequent) instances will be mapped to theclass and hence their usages and dependecies will contribute to those ofthe class. A lock-class does not go away when a lock instance does, butit can be removed if the memory space of the lock class (static ordynamic) is reclaimed, this happens for example when a module isunloaded or a workqueue is destroyed.

State¶

The validator tracks lock-class usage history and divides the usage into(4 usages * n STATEs + 1) categories:

where the 4 usages can be:- ‘ever held in STATE context’- ‘ever held as readlock in STATE context’- ‘ever held with STATE enabled’- ‘ever held as readlock with STATE enabled’

where the n STATEs are coded in kernel/locking/lockdep_states.h and as ofnow they include:- hardirq- softirq

where the last 1 category is:- ‘ever used’ [ == !unused ]

When locking rules are violated, these usage bits are presented in thelocking error messages, inside curlies, with a total of 2 * n STATEs bits.A contrived example:

modprobe/2287 is trying to acquire lock: (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24but task is already holding lock: (&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24

For a given lock, the bit positions from left to right indicate the usageof the lock and readlock (if exists), for each of the n STATEs listedabove respectively, and the character displayed at each bit positionindicates:

‘.’	acquired while irqs disabled and not in irq context
‘-‘	acquired in irq context
‘+’	acquired with irqs enabled
‘?’	acquired in irq context with irqs enabled.

The bits are illustrated with an example:

(&sio_locks[i].lock){-.-.}, at: [<c02867fd>] mutex_lock+0x21/0x24                     ||||                     ||| \-> softirq disabled and not in softirq context                     || \--> acquired in softirq context                     | \---> hardirq disabled and not in hardirq context                      \----> acquired in hardirq context

For a given STATE, whether the lock is ever acquired in that STATEcontext and whether that STATE is enabled yields four possible cases asshown in the table below. The bit character is able to indicate whichexact case is for the lock as of the reporting time.

	irq enabled	irq disabled
ever in irq	?
never in irq		.

The character ‘-‘ suggests irq is disabled because if otherwise thecharactor ‘?’ would have been shown instead. Similar deduction can beapplied for ‘+’ too.

Unused locks (e.g., mutexes) cannot be part of the cause of an error.

Single-lock state rules:¶

A lock is irq-safe means it was ever used in an irq context, while a lockis irq-unsafe means it was ever acquired with irq enabled.

A softirq-unsafe lock-class is automatically hardirq-unsafe as well. Thefollowing states must be exclusive: only one of them is allowed to be setfor any lock-class based on its usage:

<hardirq-safe> or <hardirq-unsafe><softirq-safe> or <softirq-unsafe>

This is because if a lock can be used in irq context (irq-safe) then itcannot be ever acquired with irq enabled (irq-unsafe). Otherwise, adeadlock may happen. For example, in the scenario that after this lockwas acquired but before released, if the context is interrupted thislock will be attempted to acquire twice, which creates a deadlock,referred to as lock recursion deadlock.

The validator detects and reports lock usage that violates thesesingle-lock state rules.

Multi-lock dependency rules:¶

The same lock-class must not be acquired twice, because this could leadto lock recursion deadlocks.

Furthermore, two locks can not be taken in inverse order:

<L1> -> <L2><L2> -> <L1>

because this could lead to a deadlock - referred to as lock inversiondeadlock - as attempts to acquire the two locks form a circle whichcould lead to the two contexts waiting for each other permanently. Thevalidator will find such dependency circle in arbitrary complexity,i.e., there can be any other locking sequence between the acquire-lockoperations; the validator will still find whether these locks can beacquired in a circular fashion.

Furthermore, the following usage based lock dependencies are not allowedbetween any two lock-classes:

<hardirq-safe>   ->  <hardirq-unsafe><softirq-safe>   ->  <softirq-unsafe>

The first rule comes from the fact that a hardirq-safe lock could betaken by a hardirq context, interrupting a hardirq-unsafe lock - andthus could result in a lock inversion deadlock. Likewise, a softirq-safelock could be taken by an softirq context, interrupting a softirq-unsafelock.

The above rules are enforced for any locking sequence that occurs in thekernel: when acquiring a new lock, the validator checks whether there isany rule violation between the new lock and any of the held locks.

When a lock-class changes its state, the following aspects of the abovedependency rules are enforced:

• if a new hardirq-safe lock is discovered, we check whether ittook any hardirq-unsafe lock in the past.
• if a new softirq-safe lock is discovered, we check whether it tookany softirq-unsafe lock in the past.
• if a new hardirq-unsafe lock is discovered, we check whether anyhardirq-safe lock took it in the past.
• if a new softirq-unsafe lock is discovered, we check whether anysoftirq-safe lock took it in the past.

(Again, we do these checks too on the basis that an interrupt contextcould interrupt _any_ of the irq-unsafe or hardirq-unsafe locks, whichcould lead to a lock inversion deadlock - even if that lock scenario didnot trigger in practice yet.)

Exception: Nested data dependencies leading to nested locking¶

There are a few cases where the Linux kernel acquires more than oneinstance of the same lock-class. Such cases typically happen when thereis some sort of hierarchy within objects of the same type. In thesecases there is an inherent “natural” ordering between the two objects(defined by the properties of the hierarchy), and the kernel grabs thelocks in this fixed order on each of the objects.

An example of such an object hierarchy that results in “nested locking”is that of a “whole disk” block-dev object and a “partition” block-devobject; the partition is “part of” the whole device and as long as onealways takes the whole disk lock as a higher lock than the partitionlock, the lock ordering is fully correct. The validator does notautomatically detect this natural ordering, as the locking rule behindthe ordering is not static.

In order to teach the validator about this correct usage model, newversions of the various locking primitives were added that allow you tospecify a “nesting level”. An example call, for the block device mutex,looks like this:

enum bdev_bd_mutex_lock_class{     BD_MUTEX_NORMAL,     BD_MUTEX_WHOLE,     BD_MUTEX_PARTITION};

mutex_lock_nested(&bdev->bd_contains->bd_mutex, BD_MUTEX_PARTITION);

In this case the locking is done on a bdev object that is known to be apartition.

The validator treats a lock that is taken in such a nested fashion as aseparate (sub)class for the purposes of validation.

Note: When changing code to use the _nested() primitives, be careful andcheck really thoroughly that the hierarchy is correctly mapped; otherwiseyou can get false positives or false negatives.

Annotations¶

Two constructs can be used to annotate and check where and if certain locksmust be held: lockdep_assert_held*(&lock) and lockdep_*pin_lock(&lock).

As the name suggests, lockdep_assert_held* family of macros assert that aparticular lock is held at a certain time (and generate a WARN() otherwise).This annotation is largely used all over the kernel, e.g. kernel/sched/core.c:

void update_rq_clock(struct rq *rq){      s64 delta;      lockdep_assert_held(&rq->lock);      [...]}

where holding rq->lock is required to safely update a rq’s clock.

The other family of macros is lockdep_*pin_lock(), which is admittedly onlyused for rq->lock ATM. Despite their limited adoption these annotationsgenerate a WARN() if the lock of interest is “accidentally” unlocked. This turnsout to be especially helpful to debug code with callbacks, where an upperlayer assumes a lock remains taken, but a lower layer thinks it can maybe dropand reacquire the lock (“unwittingly” introducing races). lockdep_pin_lock()returns a ‘struct pin_cookie’ that is then used by lockdep_unpin_lock() to checkthat nobody tampered with the lock, e.g. kernel/sched/sched.h:

static inline void rq_pin_lock(struct rq *rq, struct rq_flags *rf){      rf->cookie = lockdep_pin_lock(&rq->lock);      [...]}static inline void rq_unpin_lock(struct rq *rq, struct rq_flags *rf){      [...]      lockdep_unpin_lock(&rq->lock, rf->cookie);}

While comments about locking requirements might provide useful information,the runtime checks performed by annotations are invaluable when debugginglocking problems and they carry the same level of details when inspectingcode. Always prefer annotations when in doubt!

Proof of 100% correctness:¶

The validator achieves perfect, mathematical ‘closure’ (proof of lockingcorrectness) in the sense that for every simple, standalone single-tasklocking sequence that occurred at least once during the lifetime of thekernel, the validator proves it with a 100% certainty that nocombination and timing of these locking sequences can cause any class oflock related deadlock.[1]

I.e. complex multi-CPU and multi-task locking scenarios do not have tooccur in practice to prove a deadlock: only the simple ‘component’locking chains have to occur at least once (anytime, in anytask/context) for the validator to be able to prove correctness. (Forexample, complex deadlocks that would normally need more than 3 CPUs anda very unlikely constellation of tasks, irq-contexts and timings tooccur, can be detected on a plain, lightly loaded single-CPU system aswell!)

This radically decreases the complexity of locking related QA of thekernel: what has to be done during QA is to trigger as many “simple”single-task locking dependencies in the kernel as possible, at leastonce, to prove locking correctness - instead of having to trigger everypossible combination of locking interaction between CPUs, combined withevery possible hardirq and softirq nesting scenario (which is impossibleto do in practice).

Performance:¶

The above rules requiremassive amounts of runtime checking. If we didthat for every lock taken and for every irqs-enable event, it wouldrender the system practically unusably slow. The complexity of checkingis O(N^2), so even with just a few hundred lock-classes we’d have to dotens of thousands of checks for every event.

This problem is solved by checking any given ‘locking scenario’ (uniquesequence of locks taken after each other) only once. A simple stack ofheld locks is maintained, and a lightweight 64-bit hash value iscalculated, which hash is unique for every lock chain. The hash value,when the chain is validated for the first time, is then put into a hashtable, which hash-table can be checked in a lockfree manner. If thelocking chain occurs again later on, the hash table tells us that wedon’t have to validate the chain again.

Troubleshooting:¶

The validator tracks a maximum of MAX_LOCKDEP_KEYS number of lock classes.Exceeding this number will trigger the following lockdep warning:

(DEBUG_LOCKS_WARN_ON(id >= MAX_LOCKDEP_KEYS))

By default, MAX_LOCKDEP_KEYS is currently set to 8191, and typicaldesktop systems have less than 1,000 lock classes, so this warningnormally results from lock-class leakage or failure to properlyinitialize locks. These two problems are illustrated below:

1. Repeated module loading and unloading while running the validatorwill result in lock-class leakage. The issue here is that eachload of the module will create a new set of lock classes forthat module’s locks, but module unloading does not remove oldclasses (see below discussion of reuse of lock classes for why).Therefore, if that module is loaded and unloaded repeatedly,the number of lock classes will eventually reach the maximum.

2. Using structures such as arrays that have large numbers oflocks that are not explicitly initialized. For example,a hash table with 8192 buckets where each bucket has its ownspinlock_t will consume 8192 lock classes -unless- each spinlockis explicitly initialized at runtime, for example, using therun-time spin_lock_init() as opposed to compile-time initializerssuch as __SPIN_LOCK_UNLOCKED(). Failure to properly initializethe per-bucket spinlocks would guarantee lock-class overflow.In contrast, a loop that called spin_lock_init() on each lockwould place all 8192 locks into a single lock class.

   The moral of this story is that you should always explicitlyinitialize your locks.

One might argue that the validator should be modified to allowlock classes to be reused. However, if you are tempted to make thisargument, first review the code and think through the changes that wouldbe required, keeping in mind that the lock classes to be removed arelikely to be linked into the lock-dependency graph. This turns out tobe harder to do than to say.

Of course, if you do run out of lock classes, the next thing to do isto find the offending lock classes. First, the following command givesyou the number of lock classes currently in use along with the maximum:

grep "lock-classes" /proc/lockdep_stats

This command produces the following output on a modest system:

lock-classes:                          748 [max: 8191]

If the number allocated (748 above) increases continually over time,then there is likely a leak. The following command can be used toidentify the leaking lock classes:

grep "BD" /proc/lockdep

Run the command and save the output, then compare against the output froma later run of this command to identify the leakers. This same outputcan also help you find situations where runtime lock initialization hasbeen omitted.