# Runtime Lock Validation in Zircon

## Introduction

Zircon integrates a runtime lock validator to diagnose inconsistent lock
ordering that could lead to deadlocks. This document discusses how the
validator is integrated, how to enable and tune the validator at build time,
and what output the validator produces.

The theory of operation for the validator itself can be found in the
[design document](lockdep-design.md).

## Enabling the Lock Validator

Lock validation is disabled by default. **When disabled the lock instrumentation
is transparent, acting as a zero-overhead wrapper for the underlying locking
primitives**.

The validator is enabled at compile time by setting the GN build argument
`enable_lock_dep` to true. As of this writing logic for this variable is
handled by [zircon/kernel/BUILD.gn](/zircon/kernel/BUILD.gn).

You can set this variable in your GN invocation like this:

```
fx set <your build options> --args 'enable_lock_dep = true'
```

When the lock validator is enabled a set of global lock-free, wait-free data
structures are generated to track the relationships between the instrumented
locks. The acquire/release operations of the locks are augmented to update
these data structures.

## Lock Instrumentation

The current incarnation of the runtime lock validator requires manually
instrumenting each lock in kernel with a wrapper type. The wrapper type provides
the context the validator needs to properly identify the lock and generate a
global tracking structure for locks with the same context or role.

The kernel defines utility macros for this purpose in `kernel/spinlock.h` and
`kernel/mutex.h`.

### Member Locks

A type with a lock member like this:

```C++
#include <kernel/mutex.h>

class MyType {
public:
	// ...
private:
	mutable fbl::Mutex lock_;
	// ...
};
```

May be instrumented like this:

```C++
#include <kernel/mutex.h>

class MyType {
public:
	// ...
private:
	mutable DECLARE_MUTEX(MyType) lock_;
	// ...
};
```

Note that the containing type is passed to the macro
`DECLARE_MUTEX(containing_type)`. This type provides the context the validator
needs to distinguish locks that are members of `MyType` from locks that are
members of other types.

The macro `DECLARE_SPINLOCK(containing_type)` provides similar support for
instrumenting `SpinLock` members.

For those who are curious, the macro in the example above expands to this type
expression: `::lockdep::LockDep<containing_type, fbl::Mutex, __LINE__>`. This
expression results in a unique instantiation of the `lockdep::LockDep<>` type,
both across different containing types, and within a containing type where
there is more than one mutex.

### Global Locks

Global locks are instrumented using a singleton-type pattern. The kernel defines
utility macros for this purpose in `kernel/mutex.h` and `kernel/spinlock.h`.

In Zircon global locks are typically defined either at global/namespace scope or
within another type as a static member.

example.h:

```C++
#include <kernel/mutex.h>

extern fbl::Mutex a_global_lock;

class MyType {
public:
	// ...
private:
	static fbl::Mutex all_objects_lock_;
};
```

example.cpp:

```C++
#include "example.h"

fbl::Mutex a_global_lock;

fbl::Mutex MyType::all_objects_lock_;
```

The instrumentation simplifies declaring locks by declaring singleton types that
may be used in either scope and handles ODR-use automatically.

example.h:

```
#include <kernel/mutex.h>

DECLARE_SINGLETON_MUTEX(AGlobalLock);

class MyType {
public:
	// ...
private:
	DECLARE_SINGLETON_MUTEX(AllObjectsLock);
};
```

These macro invocations declare new singleton types, `AGlobalLock` and
`MyType::AllObjectsLock` respectively. These types have a static `Get()` method
that returns the underlying global lock with all of the necessary
instrumentation. Note that there is no need to separately define storage for the
locks, this is handled automatically by the supporting template types.

The macro `DECLARE_SINGLETON_SPINLOCK(name)` provides similar support for
declaring a global `SpinLock`.

### Lock Guards

Instrumented locks are acquired and released using the scoped capability types
`Guard` and `GuardMultiple`. In the kernel these types are defined in
`kernel/lockdep.h`.

The operation of `Guard` for simple mutexes is similar to `AutoLock`:

```C++
#include <kernel/mutex.h>

class MyType {
public:
	// ...

	int GetData() const {
		Guard<fbl::Mutex> guard{&lock_};
		return data_;
	}

	int DoSomething() {
		Guard<fbl::Mutex> guard{&lock_};
		int data_copy = data_;
		guard.Release();

		return DoWorkUnlocked(data_copy);
	}

private:
	mutable DECLARE_MUTEX(MyType) lock_;
	int data_{0} TA_GUARDED(lock_);
};
```

`SpinLock` types require an additional template argument to `Guard` to select
one of a few possible options when acquiring the lock: `IrqSave`, `NoIrqSave`,
and `TryLockNoIrqSave`. Omitting one of these type tags results in a
compile-time error.

```C++
#include <kernel/spinlock.h>

class MyType {
public:
	// ...

	int GetData() const {
		Guard<SpinLock, IrqSave> guard{&lock_};
		return data_;
	}

	void DoSomethingInIrqContext() {
		Guard<SpinLock, NoIrqSave> guard{&lock_};
		// ...
	}

	bool TryToDoSomethingInIrqContext() {
		if (Guard<SpinLock, TryLockNoIrqSave> guard{&lock_}) {
			// ...
			return true;
		}
		return false;
	}

private:
	mutable DECLARE_SPINLOCK(MyType) lock_;
	int data_{0} TA_GUARDED(lock_);
};
```

Instrumented global locks work similarly:

```C++
#include <kernel/mutex.h>
#include <fbl/intrusive_double_list.h>

class MyType : public fbl::DoublyLinkedListable<MyType> {
public:
	// ...

	void AddToList(MyType* object) {
		Guard<fbl::Mutex> guard{AllObjectsLock::Get()};
		all_objects_list_.push_back(*object);
	}

private:
	DECLARE_SINGLETON_MUTEX(AllObjectsLock);
	fbl::DoublyLinkedList<MyType> all_objects_list_ TA_GUARDED(AllObjectsLock::Get());
};
```

Note that instrumented locks do not have manual `Acquire()` and `Release()`
methods; using a `Guard` is the only way to acquire the locks directly. There
are two important reasons for this:

1. Manual acquire/release operations are more error prone than guard, plus
   manual release when necessary.
2. When lock validation is enabled the guard provides the storage that the
   validator uses to account for actively held locks. This approach permits
   temporary storage of validator state on the stack only for the duration the
   lock is held, which corresponds with the use patterns of guard objects.
   Without this approach the tracking data would either have to be stored with
   each lock instance, increasing memory use even when locks are not held, or
   stored in heap allocated memory. Neither of these alternatives is desirable.

In rare circumstances the underlying lock may be accessed using the `lock()`
accessor of the instrumented lock. This should be done with care as manipulating
the underlying lock directly may result inconsistency between the state of the
lock and the state the lock validator; at best this may lead to missing a lock
order warning and at worst may lead to a deadlock. **You have been warned!**

## Clang Static Analysis and Instrumented Locks

The lock instrumentation is designed to interoperate with Clang static lock
analysis. In general usage, an instrumented lock may be used as a "mutex"
capability and specified in any of the static lock annotations.

There are two special cases that need some extra attention:

1. Returning pointers or references to capabilities.
2. Unlocking a guard passed by reference.

### Pointers and References to Capabilities

When returning a lock by pointer or reference it may be convenient or necessary
to use a uniform type. Recall from earlier that instrumented locks are wrapped
in a type that captures the containing type, the underlying lock type, and the
line number to disambiguate locks belonging to different types
(`::lockdep::LockDep<Class, Locktype, Index>`). This can lead to difficulty when
returning a lock from a uniform (virtual) interface (e.g. kernel
`Dispatcher::get_lock()`).

Fortunately there is a straightforward solution: every instrumented lock is also
a subclass of `::lockdep::Lock<LockType>` (or simply `Lock<LockType>` in the
kernel). This type only depends on the underlying `LockType`, not the context in
which the instrumented lock is declared, making it convenient to use as a
pointer or reference type to refer to an instrumented lock more generically.
This type may be used in type annotations as well.

The following illustrates the pattern, which is similar to that employed by the
kernel `Dispatcher` types.

```C++
#include <kernel/mutex.h>


struct LockableInterface {
	virtual ~LockableInterface() {}
	virtual Lock<fbl::Mutex>* get_lock() = 0;
	virtual void DoSomethingLocked() TA_REQ(get_lock()) = 0;
};

class A : public LockableInterface {
public:
	Lock<fbl::Mutex>* get_lock() override { return &lock_; }
	void DoSomethingLocked() override {
		data_++;
	}
	void DoSomething() {
		Guard<fbl::Mutex> guard{get_lock()};
		DoSomethingLocked();
		// ...
	}
private:
	mutable DECLARE_MUTEX(A) lock_;
	int data_ TA_GUARDED(get_lock());
};

class B : public LockableInterface {
public:
	Lock<fbl::Mutex>* get_lock() override { return &lock_; }
	void DoSomethingLocked() override {
		// ...
	}
	void DoSomething() {
		Guard<fbl::Mutex> guard{get_lock()};
		DoSomethingLocked();
		// ...
	}
private:
	mutable DECLARE_MUTEX(B) lock_;
	char data_[32] TA_GUARDED(get_lock());
};
```

Note that the type of `A::lock_` is
`::lockdep::LockDep<A, fbl::Mutex, __LINE__>` and the type of `B::lock_` is
`::lockdep::LockDep<B, fbl::Mutex, __LINE__>`. However, both of these types are
subclasses of `Lock<fbl::Mutex>`, so we can treat them uniformly as this type in
pointer and reference expressions.

While this is very convenient, a limitation in Clang static analysis prevents it
from understanding that `LockableInterface::get_lock()` is equivalent to
`A::lock_` or `B::lock_`, even in their local contexts. For this reason is it
necessary to use `get_lock()` in all of the lock annotations.

### Unlocking a Guard Passed by Reference

In very rare circumstances it is useful to release a `Guard` instance held in
a function from a callee of the function.

**TODO(eieio): Complete documentation of this feature.**

## Lock Validation Errors

The lock validator detects and reports two broad classes of violations:

1. Pair-wise violations reported at the point of acquisition.
2. Multi-lock cycles reported asynchronously by a dedicated loop detection
   thread.

### Violations Reported at Acquisition

When a violation is detected at the point of lock acquisition the validator
produces a message like the following in the kernel log:

{# Disable variable substitution to avoid {{ being interpreted by the template engine #}
{% verbatim %}

```
[00002.668] 01032:01039> ZIRCON KERNEL OOPS
[00002.668] 01032:01039> Lock validation failed for thread 0xffff000001e53598 pid 1032 tid 1039 (userboot:userboot):
[00002.668] 01032:01039> Reason: Out Of Order
[00002.668] 01032:01039> Bad lock: name=lockdep::LockClass<SoloDispatcher<ThreadDispatcher, 316111>, Mutex, 282, (lockdep::LockFlags)0> order=0
[00002.668] 01032:01039> Conflict: name=lockdep::LockClass<SoloDispatcher<ProcessDispatcher, 447439>, Mutex, 282, (lockdep::LockFlags)0> order=0
[00002.668] 01032:01039> {{{module:0:kernel:elf:0bf16acb54de1ceef7ffb6ee4449c6aafc0ab392}}}
[00002.668] 01032:01039> {{{mmap:0xffffffff10000000:0x1ae1f0:load:0:rx:0xffffffff00000000}}}
[00002.668] 01032:01039> {{{mmap:0xffffffff101af000:0x49000:load:0:r:0xffffffff001af000}}}
[00002.668] 01032:01039> {{{mmap:0xffffffff101f8000:0x1dc8:load:0:rw:0xffffffff001f8000}}}
[00002.668] 01032:01039> {{{mmap:0xffffffff10200000:0x76000:load:0:rw:0xffffffff00200000}}}
[00002.668] 01032:01039> {{{bt:0:0xffffffff10088574}}}
[00002.668] 01032:01039> {{{bt:1:0xffffffff1008f324}}}
[00002.668] 01032:01039> {{{bt:2:0xffffffff10162860}}}
[00002.668] 01032:01039> {{{bt:3:0xffffffff101711e0}}}
[00002.668] 01032:01039> {{{bt:4:0xffffffff100edae0}}}
```

{# Re-enable variable substitution #}
{% endverbatim %}

The error is informational and non-fatal. The first line identifies the thread
and process where the kernel lock violation occurred. The next line identifies
the type of violation. The next two lines identify which locks were found to be
inconsistent with previous observations: the "Bad lock" is the lock that is
about to be acquired, while "Conflict" is a lock that is already held by the
current context and is the point of inconsistency with the lock that is about to
be acquired. All of the lines following this are part of the stack trace leading
up to the bad lock.

### Multi-Lock Cycles

Circular dependencies between three or more locks are detected with a dedicated
loop detection thread. Because this detection happens in a separate context from
the lock operations that caused the cycle a stack trace is not provided.

Reports from the loop detection thread look like this:

```
[00002.000] 00000.00000> ZIRCON KERNEL OOPS
[00002.000] 00000.00000> Circular lock dependency detected:
[00002.000] 00000.00000>   lockdep::LockClass<VmObject, fbl::Mutex, 249, (lockdep::LockFlags)0>
[00002.000] 00000.00000>   lockdep::LockClass<VmAspace, fbl::Mutex, 198, (lockdep::LockFlags)0>
[00002.000] 00000.00000>   lockdep::LockClass<SoloDispatcher<VmObjectDispatcher>, fbl::Mutex, 362, (lockdep::LockFlags)0>
[00002.000] 00000.00000>   lockdep::LockClass<SoloDispatcher<PortDispatcher>, fbl::Mutex, 362, (lockdep::LockFlags)0>
```

Each of the locks involved in the cycle are reported in a group. Frequently only
two of the circularly-dependent locks are acquired by a single thread at any
given time, making manual detection difficult or impossible. However, the
potential for deadlock between three or more threads is real and should be
addressed for long-term system stability.

## Kernel Commands

When the lock validator is enabled the following kernel commands are available:

* `k lockdep dump` - dumps the dependency graph and connected sets (loops) for
  all instrumented locks.
* `k lockdep loop` - triggers a loop detection pass and reports any loops found
  to the kernel log.