xref: /docs/lockdep-design.md

# Runtime Lock Validation in Zircon and Fuchsia

## Introduction

Lock validation is a technique for checking the consistency of locking behavior
in a program to find potential deadlock hazards. This document discusses
relevant aspects of the static and dynamic approaches to lock validation and
presents the foundation for the runtime lock validation library available in
Zircon and Fuchsia.

## Background

Lock validation may be performed either statically or dynamically. The following
summarizes the important differences between static and dynamic approaches to
lock validation:

* When the validation is performed: compile time vs. run time.
* How effective the validator is at finding potential problems.
* What level of involvement is required by the programmer.
* The overhead cost of the validation itself.

### Static Validation

Static validation is typically performed at compile time by analyzing the call
graphs produced by the compiler or other source-level processor. With this
approach it is necessary to instrument the code and locking primitives with
annotations to inform the validator about which types represent locks and which
rules to apply (or not) to the code that uses the lock types.

The benefits of static validation include early detection of issues at build
time, deterministic validation results, and zero runtime overhead. This
combination of properties make it attractive to always enable static validation,
ensuring that locking issues are often caught before code makes it into the
build, without impacting the performance of the build artifacts.

Static validation also has some down sides. One problem is that static
validation requires correct, consistent application of a variety of annotations
to both locks and code to provide useful results. This can cause maintenance
issues unless diligent code review standards are implemented. Another issue is
that static validation has limited visibility and can be fooled by conditional
paths, dynamic dispatch, move semantics, and lock dependencies that span
compilation units.

### Dynamic Validation

Dynamic validation is performed online at runtime by observing the relationships
between locks as the code executes. With this approach it is generally
sufficient to instrument just the locking primitives and acquire/release
operations to provide the information required for validation.

The benefits of dynamic validation include simpler instrumentation (from the
user's perspective) and potentially greater visibility into the actual runtime
behavior of the program. This makes dynamic validation useful in large code
bases, where it may not be possible for static validation to see the full
set of possible lock interactions.

The main downsides of dynamic validation are runtime overhead and execution
coverage requirements. Because dynamic validation must track lock interactions
at runtime, each acquire and release incurs a non-zero execution cost to update
tracking data, in addition to the memory overhead of the tracking data itself.
Runtime tracking also has the consequence that code paths that are not executed
cannot be analyzed by the validator. This may increase the burden on the
developer and QA to ensure sufficient execution coverage if that is not already
a project requirement.


### Locking Ordering Invariant

The job of the lock validator is to determine whether or not the lock invariants
of the program hold. The primary invariant is the order between two or more
locks: all paths in a program that acquire two or more locks must do so in an
order consistent with every other path involving two or more of the same locks to
avoid the potential for deadlock. Environments that deal with hardware
interrupts, such as embedded systems and kernels, have an additional ordering
invariant to avoid interrupt-induced deadlocks. These invariants are illustrated
in the following subsections.

##### Basic Inversion

The simplest form of inversion occurs when a program has two locks that are
both acquired sequentially with inconsistent orders in different paths.

For example, a program with the locks **A** and **B** and code paths
**P<sub>1</sub>** and **P<sub>2</sub>** and the following behavior has the
potential for deadlock:

Path **P<sub>1</sub>** acquires and releases the locks in the sequence:

1. Acquire(**A**)
2. Acquire(**B**)
3. Release(**B**)
4. Release(**A**)

Path **P<sub>2</sub>** acquires and releases the locks in the inverted sequence:

1. Acquire(**B**)
2. Acquire(**A**)
3. Release(**A**)
4. Release(**B**)

With the right interleaving, perhaps due to both paths executing concurrently
on different threads, a deadlock occurs when path **P<sub>1</sub>** holds lock
**A** and blocks waiting for lock **B**, while path **P<sub>2</sub>** holds lock
**B** and blocks waiting for lock **A**.

##### Circular Dependency

Inversion may also occur between more than two locks and paths. This kind of
inversion is much harder to recognize through manual inspection because each
pair of locks involved may appear to be correctly ordered in every path involving
just the pairs, and yet a potential deadlock may still exist given overall
ordering of the locks.

For example, a program with the locks **A**, **B**, and **C**; paths
**P<sub>1</sub>**, **P<sub>2</sub>**, and **P<sub>3</sub>**; with the following
behavior has the potential for deadlock:

Path **P<sub>1</sub>** acquires and releases the locks in the sequence:

1. Acquire(**A**)
2. Acquire(**B**)
3. Release(**B**)
4. Release(**A**)

Path **P<sub>2</sub>** acquires and releases the locks in the sequence:

1. Acquire(**B**)
2. Acquire(**C**)
3. Release(**C**)
4. Release(**B**)

Path **P<sub>3</sub>** acquires and releases the locks in the sequence:

1. Acquire(**C**)
2. Acquire(**A**)
3. Release(**A**)
4. Release(**C**)

With the right interleaving of paths **P<sub>1</sub>**, **P<sub>2</sub>**,
and **P<sub>3</sub>** a deadlock occurs as each path acquires the lock at the
first step and waits for the lock at the second step. In practice this situation
may be compounded by the existence of many different paths that produce the same
pairwise lock sequences.

##### IRQ-Safe Ordering

In systems that deal with hardware interrupts the ordering between irq-safe and
non-irq-safe locks is critical: a non-irq-safe lock must never be acquired while
holding an irq-safe lock to prevent indirect lock inversions. Irq-safe locks
preserve ordering between irq and non-irq context; a consistent order of two or
more irq-safe locks is guaranteed to be safe for paths running in both irq and
non-irq context. The same is not true for non-irq-safe locks. The reason for this
is that non-irq-safe locks permit irq handlers to effectively insert the locks
acquired by the handler at arbitrary points in the interrupted task's lock
sequences.

For example, a system with non-irq-safe lock **A** and irq-safe lock
**B<sub>irq</sub>**; paths **P<sub>1</sub>**, **P<sub>2</sub>**, and irq path
**P<sub>irq</sub>**; with the following behavior has the potential for deadlock:

Path **P<sub>1</sub>** on **CPU1** acquires and releases the lock in sequence:

1. Acquire(**A**)
2. _**P<sub>irq</sub>** interrupts here on **CPU1**_
3. Release(**A**)

Path **P<sub>irq</sub>** on **CPU1** acquires and releases the lock in sequence:

1. Acquire(**B<sub>irq</sub>**)
2. Release(**B<sub>irq</sub>**)

Path **P<sub>2</sub>** on **CPU2** acquires and releases the locks in sequence:

1. Acquire(**B<sub>irq</sub>**)
2. Acquire(**A**)
3. Release(**A**)
4. Release(**B<sub>irq</sub>**)

With the right interleaving of paths **P<sub>1</sub>**, **P<sub>2</sub>**, and
**P<sub>irq</sub>** a deadlock occurs as **P<sub>irq</sub>** attempts to acquire
**B<sub>irq</sub>** while **P<sub>2</sub>** holds **B<sub>irq</sub>** and blocks
waiting for **A**. This is an indirect lock inversion: **P<sub>irq</sub>**
effectively inserts an acquire/release sequence of **B<sub>irq</sub>** in the
middle of the acquire/release sequence of **A** in path **P<sub>1</sub>**, which
is inconsistent with the lock sequence for the same locks in path
**P<sub>2</sub>**.

### Performing Validation

The invariants discussed in the previous section can be validated using a finite
directed graph. The directed graph tracks the identity and order of locks as the
analysis traverses the code paths. Such a graph can be built either by traversing
the call graphs generated by a compiler or source-level processor (static
analysis) or by observing the ordering of locks during program execution (dynamic
analysis). This section introduce the process in abstract terms that apply to
either approach, in preparation for developing a concrete dynamic analysis
strategy later on.

In the most general terms, building a directed graph from a code path requires
maintaining a list of actively held locks as the path is traversed: a node
representing a lock is added to the list whenever the lock is acquired and
removed from the list whenever the lock is released. In addition to maintaining
the active list, a directed edge is added to the graph from a vertex representing
the newly acquired lock to each vertex representing a lock already in the list.

#### Basic Inversion Example

This section illustrates a directed graph approach to detect a basic two-lock
inversion.

Recall from the earlier example a program with the locks **A** and **B**; code
paths **P<sub>1</sub>** and **P<sub>2</sub>**; and the following behavior:

Path **P<sub>1</sub>** acquires and releases the locks in the sequence:

1. Acquire(**A**)
2. Acquire(**B**)
3. Release(**B**)
4. Release(**A**)

Path **P<sub>2</sub>** acquires and releases the locks in the inverted sequence:

1. Acquire(**B**)
2. Acquire(**A**)
3. Release(**A**)
4. Release(**B**)

##### Analysis of Path **P<sub>1</sub>**

Starting with path **P<sub>1</sub>** we define and update the directed graph.

Let **L<sub>1</sub>** be the ordered _active_ list of locks held by path
**P<sub>1</sub>**.

Let **G** = (**V**, **E**) be the directed graph, having the set of vertices
**V** representing observed locks and the set of directed edges between vertices
**E**.

Initial state:

| **L<sub>1</sub>** | **V** | **E** |
|-------------------|-------|-------|
| ()                | {}    | {}    |

After **P<sub>1</sub>** step 1:

| **L<sub>1</sub>** | **V**   | **E** |
|-------------------|---------|-------|
| (**A**)           | {**A**} | {}    |

This step adds lock **A** to the active list and introduces a vertex for the
same lock to the directed graph. Since there are no other locks in the active
list no edges are added.

After **P<sub>1</sub>** step 2:

| **L<sub>1</sub>** | **V**          | **E**            |
|-------------------|----------------|------------------|
| (**A**, **B**)    | {**A**, **B**} | {(**B**, **A**)} |

This step adds lock **B** to the active list and also introduces a corresponding
vertex to the graph. This time the active list does contain a lock, so an edge
from the new lock to the existing lock is added to the graph. This edge
represents that lock **B** now _depends_ on lock **A** preceding it in any
other path that involves both locks.

After **P<sub>1</sub>** step 3:

| **L<sub>1</sub>** | **V**          | **E**            |
|-------------------|----------------|------------------|
| (**A**)           | {**A**, **B**} | {(**B**, **A**)} |

Lock **B** is removed from the active list. No updates to the graph.

After **P<sub>1</sub>** step 4:

| **L<sub>1</sub>** | **V**          | **E**            |
|-------------------|----------------|------------------|
| ()                | {**A**, **B**} | {(**B**, **A**)} |

Lock **A** is removed from the active list. No updates to the graph.

##### Analysis of Path **P<sub>2</sub>**

Let **L<sub>2</sub>** be the active list of locks held by **P<sub>2</sub>**.

Initial state:

| **L<sub>2</sub>** | **V**          | **E**            |
|-------------------|----------------|------------------|
| ()                | {**A**, **B**} | {(**B**, **A**)} |

In this case the initial state is the final state from path **P<sub>1</sub>**.

After **P<sub>2</sub>** step 1:

| **L<sub>2</sub>** | **V**          | **E**            |
|-------------------|----------------|------------------|
| (**B**)           | {**A**, **B**} | {(**B**, **A**)} |

This step adds lock **B** to the active list. As there are no other locks in the
active list no edges are added to the graph. Since **B** already has a vertex in
the graph there is also no change to **V**.

After **P<sub>2</sub>** step 2:

| **L<sub>2</sub>** | **V**          | **E**                            |
|-------------------|----------------|----------------------------------|
| (**B**, **A**)    | {**A**, **B**} | {(**B**, **A**), (**A**, **B**)} |

This step adds lock **A** to the active list. Since this lock already has a
vertex there is no change to **V**. However, because there is a lock in the
active list an edge from the new lock to the existing lock is added to the
graph. With this new edge the graph now forms a cycle between vertices **A** and
**B**, indicating that ordering between these locks is not consistent between
the two paths considered thus far and that a potential deadlock exists.

#### Circular Dependency Example

This section illustrates a directed graph approach to detect a circular
dependency inversion using previously discussed example from the invariants
section. This illustration is somewhat abbreviated due to the similarity to the
previous illustration.

Consider a program with the locks **A**, **B**, and **C** and paths
**P<sub>1</sub>**, **P<sub>2</sub>**, and **P<sub>3</sub>** and the following
behavior:

Path **P<sub>1</sub>** acquires and releases the locks in the sequence:

1. Acquire(**A**)
2. Acquire(**B**)
3. Release(**B**)
4. Release(**A**)

Path **P<sub>2</sub>** acquires and releases the locks in the sequence:

1. Acquire(**B**)
2. Acquire(**C**)
3. Release(**C**)
4. Release(**B**)

Path **P<sub>3</sub>** acquires and releases the locks in the sequence:

1. Acquire(**C**)
2. Acquire(**A**)
3. Release(**A**)
4. Release(**C**)

##### Analysis of Path **P<sub>1</sub>**

Let **L<sub>1</sub>** be the ordered _active_ list of locks held by path
**P<sub>1</sub>**.

Let **G** = (**V**, **E**) be the directed graph, having the set of vertices
**V** representing observed locks and the set of directed edges between vertices
**E**.

Initial state:

| **L<sub>1</sub>** | **V** | **E** |
|-------------------|-------|-------|
| ()                | {}    | {}    |

After **P<sub>1</sub>** step 1:

| **L<sub>1</sub>** | **V**   | **E** |
|-------------------|---------|-------|
| (**A**)           | {**A**} | {}    |


After **P<sub>1</sub>** step 2:

| **L<sub>1</sub>** | **V**          | **E**            |
|-------------------|----------------|------------------|
| (**A**, **B**)    | {**A**, **B**} | {(**B**, **A**)} |


After **P<sub>1</sub>** step 3:

| **L<sub>1</sub>** | **V**          | **E**            |
|-------------------|----------------|------------------|
| (**A**)           | {**A**, **B**} | {(**B**, **A**)} |


After **P<sub>1</sub>** step 4:

| **L<sub>1</sub>** | **V**          | **E**            |
|-------------------|----------------|------------------|
| ()                | {**A**, **B**} | {(**B**, **A**)} |

##### Analysis of Path **P<sub>2</sub>**

Let **L<sub>2</sub>** be the ordered _active_ list of locks held by path
**P<sub>2</sub>**.

Initial state:

| **L<sub>2</sub>** | **V**          | **E**            |
|-------------------|----------------|------------------|
| ()                | {**A**, **B**} | {(**B**, **A**)} |


After **P<sub>2</sub>** step 1:

| **L<sub>2</sub>** | **V**          | **E**            |
|-------------------|----------------|------------------|
| (**B**)           | {**A**, **B**} | {(**B**, **A**)} |

After **P<sub>2</sub>** step 2:

| **L<sub>2</sub>** | **V**                 | **E**                            |
|-------------------|-----------------------|----------------------------------|
| (**B**, **C**)    | {**A**, **B**, **C**} | {(**B**, **A**), (**C**, **B**)} |

This step adds lock **C** to the active list and also introduces a corresponding
vertex to the graph. The active list contains the lock **B**, so an edge is added
from **C** to **B**.

After **P<sub>2</sub>** step 3:

| **L<sub>2</sub>** | **V**                 | **E**                            |
|-------------------|-----------------------|----------------------------------|
| (**B**)           | {**A**, **B**, **C**} | {(**B**, **A**), (**C**, **B**)} |


After **P<sub>2</sub>** step 4:

| **L<sub>2</sub>** | **V**                 | **E**                            |
|-------------------|-----------------------|----------------------------------|
| ()                | {**A**, **B**, **C**} | {(**B**, **A**), (**C**, **B**)} |

##### Analysis of Path **P<sub>3</sub>**

Let **L<sub>3</sub>** be the ordered _active_ list of locks held by path
**P<sub>3</sub>**.

Initial state:

| **L<sub>3</sub>** | **V**                 | **E**                            |
|-------------------|-----------------------|----------------------------------|
| ()                | {**A**, **B**, **C**} | {(**B**, **A**), (**C**, **B**)} |


After **P<sub>3</sub>** step 1:

| **L<sub>3</sub>** | **V**                 | **E**                            |
|-------------------|-----------------------|----------------------------------|
| (**C**)           | {**A**, **B**, **C**} | {(**B**, **A**), (**C**, **B**)} |

After **P<sub>3</sub>** step 2:

| **L<sub>3</sub>** | **V**                 | **E**                                            |
|-------------------|-----------------------|--------------------------------------------------|
| (**C**, **A**)    | {**A**, **B**, **C**} | {(**B**, **A**), (**C**, **B**), (**A**, **C**)} |

This step adds lock **A** to the active list. The active list contains the lock
**C**, so an edge is added from **A** to **C**. With this new edge the graph now
forms a cycle in the vertices (**A**, **B**, **C**), indicating a circular
dependency and the potential for deadlock if paths **P<sub>1</sub>**,
**P<sub>2</sub>**, and **P<sub>3</sub>** are interleaved in the right way.

#### IRQ-Safe Ordering Example

This section illustrates a directed graph approach to detect irq-safe order
violations using the previously discussed example from the invariants section.

Recall the example system with non-irq-safe lock **A** and irq-safe lock
**B<sub>irq</sub>**; paths **P<sub>1</sub>**, **P<sub>2</sub>**, and irq path
**P<sub>irq</sub>**; with the following behavior:

Path **P<sub>1</sub>** acquires and releases the lock in sequence:

1. Acquire(**A**)
2. Release(**A**)

Path **P<sub>irq</sub>** acquires and releases the lock in sequence:

1. Acquire(**B<sub>irq</sub>**)
2. Release(**B<sub>irq</sub>**)

Path **P<sub>2</sub>** acquires and releases the locks in sequence:

1. Acquire(**B<sub>irq</sub>**)
2. Acquire(**A**)
3. Release(**A**)
4. Release(**B<sub>irq</sub>**)

##### Analysis of Path **P<sub>1</sub>**

Let **L<sub>1</sub>** be the ordered _active_ list of locks held by path
**P<sub>1</sub>**.

Let **G** = (**V**, **E**) be the directed graph, having the set of vertices
**V** representing observed locks and the set of directed edges between vertices
**E**.

Initial state:

| **L<sub>1</sub>** | **V** | **E** |
|-------------------|-------|-------|
| ()                | {}    | {}    |

After **P<sub>1</sub>** step 1:

| **L<sub>1</sub>** | **V**   | **E** |
|-------------------|---------|-------|
| (**A**)           | {**A**} | {}    |

After **P<sub>1</sub>** step 2:

| **L<sub>1</sub>** | **V**   | **E** |
|-------------------|---------|-------|
| ()                | {**A**} | {}    |

##### Analysis of Path **P<sub>irq</sub>**

Let **L<sub>irq</sub>** be the ordered _active_ list of locks held by path
**P<sub>irq</sub>**.

Initial state:

| **L<sub>irq</sub>** | **V**   | **E** |
|---------------------|---------|-------|
| ()                  | {**A**} | {}    |

After **P<sub>irq</sub>** step 1:

| **L<sub>irq</sub>**   | **V**                        | **E** |
|-----------------------|------------------------------|-------|
| (**B<sub>irq</sub>**) | {**A**, **B<sub>irq</sub>**} | {}    |

After **P<sub>irq</sub>** step 2:

| **L<sub>irq</sub>** | **V**                        | **E** |
|---------------------|------------------------------|-------|
| ()                  | {**A**, **B<sub>irq</sub>**} | {}    |

##### Analysis of Path **P<sub>irq</sub>**

Let **L<sub>2</sub>** be the ordered _active_ list of locks held by path
**P<sub>2</sub>**.

Initial state:

| **L<sub>2</sub>** | **V**   | **E** |
|-------------------|---------|-------|
| ()                | {**A**} | {}    |

After **P<sub>2</sub>** step 1:

| **L<sub>2</sub>**     | **V**                        | **E** |
|-----------------------|------------------------------|-------|
| (**B<sub>irq</sub>**) | {**A**, **B<sub>irq</sub>**} | {}    |

After **P<sub>2</sub>** step 2:

| **L<sub>2</sub>**            | **V**                        | **E**                          |
|------------------------------|------------------------------|--------------------------------|
| (**B<sub>irq</sub>**, **A**) | {**A**, **B<sub>irq</sub>**} | {(**A**, **B<sub>irq</sub>**)} |

This step adds lock **A** to the active list. The active list contains lock
**B<sub>irq</sub>**, so an edge is added from **A** to **B<sub>irq</sub>**.
Because this is an edge from a non-irq-safe lock to an irq-safe lock the irq-safe
ordering invariant is violated and a potential deadlock exists.

## From Theory to Implementation

This section develops a concrete strategy to implement a directed graph
validator, based on the analysis techniques of the previous section.

The implementation strategy has the following goals:

1. Avoid dynamic allocation if possible.
2. Minimize the overhead of validation.
3. Support environments that manage hardware interrupts.

### Removing Redundancy with Lock Classes

In the analysis earlier in this document, locks are considered abstractly with
the implication that the tracked objects are individual instances of locks.
While tracking individual instances produces correct results, it has several
consequences that might be avoided:

1. Tracking structures must be dynamically adjusted as lock instances come into
   and out of existence, possibly requiring dynamic allocation or other
   per-instance data storage.
2. The graph contains redundant information when multiple instances of locks are
   used identically by the same code paths.
3. Relatedly, it may take longer to identify violations by locks that serve
   identical functions, but have not yet individually propagated through all of
   the necessary code paths.

A key observation is that locks that serve identical functions should follow the
same ordering rules, regardless of the number of instances.

Consider the following types with lock members and an operation that mutates
both types:

```C++
struct Foo {
    Mutex lock;
    int data; GUARDED_BY(lock);
};

struct Bar {
    Mutex lock;
    int data; GUARDED_BY(lock);
};

void Swap(Foo* foo, Bar* bar) {
    foo->lock.Acquire();
    bar->lock.Acquire();

    int temp = foo->data;
    foo->data = bar->data;
    bar->data = temp;

    bar->Release();
    foo->Release();
}
```

Since operation `Swap` may operate on any instance of `Foo` and any instance of
`Bar` it follows that `Swap` establishes an order between the locks of all
instances of `Foo` and `Bar`; failure to apply this order consistently in other
parts of a program could result in a deadlock when the same instances of `Foo`
and `Bar` are locked concurrently in different orders.

Note that it is possible to intentionally or unintentionally segregate different
collections of `Foo` and `Bar` such that instances locked in different orders
never overlap. This is still dangerous however, because seemingly innocuous
changes to the inputs, structure, or timing of the program could defeat the
segregation and introduce a potential deadlock. This problem can be avoided
entirely by treating all instances of `Foo` and `Bar` equivalently and applying
the same ordering rules throughout the program.

Ensuring universal ordering throughout the program can be achieved by tracking
classes of locks instead of lock instances: each lock member in each type
represents a unique lock class. The relationships between each lock class can
be tracked and analyzed using the same directed graph techniques as with
individual locks.

Tracking lock classes has the following benefits:

1. Statically allocated memory: because all lock classes are known at compile
   time, tracking structures can be allocated up front as static global data.
2. Elimination of redundant graph nodes: locks in the same class use the same
   tracking structures.
3. Faster detection of invariant violations: violations are detected when
   lock class orders are inconsistent, even if the individual instances involved
   have never been used together.

#### Additional Ordering Rules

Tracking lock classes introduces additional ordering considerations when locking
multiple locks of the same class. Because individual instances are not tracked
it is necessary to take additional steps to ensure consistency when multiple
locks of the same class must be acquired at the same time.

##### Externally Ordered Locks

Nesting locks of the same class is necessary when a hierarchical or other
ordered data structure has locks in each node and more than one per-node lock
must be held at a time. In this situation the data structure or access pattern
must provide a stable ordering that is used to guarantee ordering of the locks.

Validation of nestable lock classes requires only that the external order is
recorded in the active locks list for each nestable lock and compared when new
locks of the same class are added to the list. A consequence of this design is
that other lock classes may not be interspersed between nested locks of the
same class, only wholly before or after a collection of nested locks.

For example, non-nestable lock classes **A** and **B**, and nestable lock class
**N** may be interspersed like this:

**A**, **N<sub>0</sub>**, **N<sub>1</sub>**, ... **N<sub>n</sub>**, **B**

But not like this:

**A**, **N<sub>0</sub>**, **B**, **N<sub>1</sub>**, ... **N<sub>n</sub>** or
**A**, **N<sub>0</sub>**, **N<sub>1</sub>**, **B**, ... **N<sub>n</sub>** or
... etc

In most situations this is a reasonable constraint, as interspersing other locks
within a nested structure with arbitrary depth is likely to result in inversions
as the structure is updated at runtime. On the other hand, in situations where
nesting is bounded to a few levels it may be more effective to define separate
lock classes for each level instead of using a nested class -- in this case
other locks may be allowed at a specific level following normal lock ordering
rules.

##### Address Ordering

It is difficult to generalize lock ordering between locks of the same class
without an externally provided order when the locks are acquired at different
times. It is possible however, to provide an ordering guarantee when acquiring
multiple locks at the same time, without temporal separation. In this situation
the locks may be ordered by address, guaranteeing that any path that acquires
the same set locks produces a consistent locking order.

For example, consider an operation **F**(**S<sub>a</sub>**, **S<sub>b</sub>**)
that operates on two instances of structure **S**, each with a lock of class
**L** and, as part of the operation **F** must lock both locks.

If instance **S<usb>0</sub>** is ordered in memory before instance
**S<sub>1</sub>** then the locks have the same relative ordering as their
containing instances. We can consider the locks to have the subclasses
**L<sub>0</sub>** and **L<sub>1</sub>** respectively.

A lock ordering problem arises if we perform the operation with different
orders:

**F**(**S<sub>0</sub>**, **S<sub>1</sub>**) and
**F**(**S<sub>1</sub>**, **S<sub>0</sub>**)

Without intervention these produce the inverted lock sequences:

**L<sub>0</sub>**, **L<sub>1</sub>** and **L<sub>1</sub>**, **L<sub>0</sub>**

Since **F** has simultaneous access to both locks at the same time, it is
possible to order the locks by address, resulting in a consistent lock
sequence regardless of the original order of the arguments.

Now suppose we add two more lock classes to the sequence: class **A** acquired
before operation **F** and class **B** acquired after operation **F**. The
resulting lock sequence is:

**A**, **L<sub>0</sub>**, **L<sub>1</sub>**, **B**

Note that this looks similar to the nested lock class sequence diagram in the
previous section. It is in fact the same situation, only the ordering of locks
is provided by address rather than an external order. This means that the same
bookkeeping in the active threads list can be used for both situations.

#### Lock Class Tracking Data Structure

This section discusses implementation details for tracking lock classes and
concrete processing techniques to detect potential deadlocks.

Each lock class has a statically allocated node in the directed graph
representing all locks belonging to that class. Each node has the following data
structures:

##### Lock-Free, Wait-Free Hash Set

Each lock class node has a hash set that tracks the edges from the lock class to
the lock classes ordered before it.

**TODO**: Add implementation details of the hash set.

##### Lock-Free, Wait-Free Disjoint Set Structures

Each lock class node has a parent pointer used to track nodes that are connected
in cycles in the directed graph. This permits reporting cycles that have been
previously by the loop detection algorithm without fully re-traversing the graph.

**TODO**: Add implementation details of the disjoint set structure.

##### Thread-Local Lock List

Each thread maintains a thread-local list of the locks it currently holds.

**TODO**: Add implementation details of the thread-local lock list.

##### Loop Detection Thread

Whenever a new edge is added to the directed graph, the loop detection thread is
triggered to traverse the graph to find circular dependencies involving more than
two locks. Tarjan's strongly connected sets algorithm is an efficient choice,
with worst case complexity of **O**(|**E**| + |**V**|). This algorithm is stable
even when traversing a graph that is updated concurrently by other threads.

**TODO**: Add implementation details of the loop detection thread.

## References

1. Clang static [thread safety analysis](https://clang.llvm.org/docs/ThreadSafetyAnalysis.html).
2. LLVM runtime [thread sanitizer](https://github.com/google/sanitizers/wiki/ThreadSanitizerDeadlockDetector).
3. Linux Kernel [lockdep subsystem](https://www.kernel.org/doc/Documentation/locking/lockdep-design.txt).