[Revised document] Crossrelease lockdep

[Byungchul Park]

Hello,

I rewrote the document so that the need of crossrelease feature can be
described logically. I think it's more important than to post specific
implementation. Could you let me know your opinions about this?

Thanks,
Byungchul

----->8-----

Crossrelease
============

Started by Byungchul Park <byungchul.park@xxxxxxx>

Contents:

 (*) Background.

     - What causes deadlock.
     - What lockdep detects.
     - How lockdep works.

 (*) Limitation.

     - Limit to typical lock.
     - Pros from the limitation.
     - Cons from the limitation.

 (*) Generalization.

     - Relax the limitation.

 (*) Crossrelease.

     - Introduce crossrelease.
     - Introduce commit.

 (*) Implementation.

     - Data structures.
     - How crossrelease works.

 (*) Optimizations.

     - Avoid duplication.
     - Avoid lock contention.


==========
Background
==========

What causes deadlock
--------------------

A deadlock occurs when a context is waiting for an event to be issued
which cannot be issued because the context or another context who can
issue the event is also waiting for an event to be issued which cannot
be issued. Single context or more than one context both waiting for an
event and issuing an event may paricipate in a deadlock.

For example,

A context who can issue event D is waiting for event A to be issued.
A context who can issue event A is waiting for event B to be issued.
A context who can issue event B is waiting for event C to be issued.
A context who can issue event C is waiting for event D to be issued.

A deadlock occurs when these four operations are run at a time because
event D cannot be issued if event A isn't issued which in turn cannot be
issued if event B isn't issued which in turn cannot be issued if event C
isn't issued which in turn cannot be issued if event D isn't issued. No
event can be issued since any of them never meets its precondition.

We can easily recognize that each wait operation creates a dependency
between two issuings e.g. between issuing D and issuing A like, 'event D
cannot be issued if event A isn't issued', in other words, 'issuing
event D depends on issuing event A'. So the whole example can be
rewritten in terms of dependency,

Do an operation making 'event D cannot be issued if event A isn't issued'.
Do an operation making 'event A cannot be issued if event B isn't issued'.
Do an operation making 'event B cannot be issued if event C isn't issued'.
Do an operation making 'event C cannot be issued if event D isn't issued'.

or,

Do an operation making 'issuing event D depends on issuing event A'.
Do an operation making 'issuing event A depends on issuing event B'.
Do an operation making 'issuing event B depends on issuing event C'.
Do an operation making 'issuing event C depends on issuing event D'.

What causes a deadlock is a set of dependencies a chain of which forms a
cycle, which means that issuing event D depending on issuing event A
depending on issuing event B depending on issuing event C depending on
issuing event D, finally depends on issuing event D itself, which means
no event can be issued.

Any set of operations creating dependencies causes a deadlock. The set
of lock operations e.g. acquire and release is an example. Waiting for a
lock to be released corresponds to waiting for an event and releasing a
lock corresponds to issuing an event. So the description of dependency
above can be altered to one in terms of lock.

In terms of event, issuing event A depends on issuing event B if,

	Event A cannot be issued if event B isn't issued.

In terms of lock, releasing lock A depends on releasing lock B if,

	Lock A cannot be released if lock B isn't released.

CONCLUSION

A set of dependencies a chain of which forms a cycle, causes a deadlock,
no matter what creates the dependencies.


What lockdep detects
--------------------

A deadlock actually occurs only when all operations creating problematic
dependencies are run at a time. However, even if it has not happend, the
deadlock potentially can occur if the problematic dependencies obviously
exist. Thus it's meaningful to detect not only an actual deadlock but
also its possibility. Lockdep does the both.

Whether a deadlock actually occurs or not depends on several factors,
which means a deadlock may not occur even though problematic
dependencies exist. For example, what order contexts are switched in is
a factor. A deadlock will occur when contexts are switched so that all
operations causing a deadlock become run simultaneously.

Lockdep tries to detect a deadlock or its possibility aggressively,
though it also tries to avoid false positive detections. So lockdep is
designed to consider all possible combinations of dependencies so that
it can detect all potential possibilities of deadlock in advance. What
lockdep tries in order to consider all possibilities are,

1. Use a global dependency graph including all dependencies.

   What lockdep checks is based on dependencies instead of what actually
   happened. So no matter which context or call path a new dependency is
   detected in, it's just referred to as a global factor.

2. Use lock classes than lock instances when checking dependencies.

   What actually causes a deadlock is lock instances. However, lockdep
   uses lock classes than its instances when checking dependencies since
   any instance of a same lock class can be altered anytime.

So lockdep detects both an actual deadlock and its possibility. But the
latter is more valuable than the former. When a deadlock actually
occures, we can identify what happens in the system by some means or
other even without lockdep. However, there's no way to detect possiblity
without lockdep unless the whole code is parsed in head. It's terrible.

CONCLUSION

Lockdep does, the fisrt one is more valuable,

1. Detecting and reporting deadlock possibility.
2. Detecting and reporting a deadlock actually occured.


How lockdep works
-----------------

What lockdep should do, to detect a deadlock or its possibility are,

1. Detect a new dependency created.
2. Keep the dependency in a global data structure esp. graph.
3. Check if any of all possible chains of dependencies forms a cycle.
4. Report a deadlock or its possibility if a cycle is detected.

A graph used by lockdep to keep all dependencies looks like,

A -> B -        -> F -> G
        \      /
         -> E -        -> L
        /      \      /
C -> D -        -> H -
                      \
                       -> I -> K
                      /
                   J -

where A, B,..., L are different lock classes.

Lockdep adds a dependency into graph when a new dependency is detected.
For example, it adds a dependency 'A -> B' when a dependency between
releasing lock A and releasing lock B, which has not been added yet, is
detected. It does same thing on other dependencies, too. See 'What
causes deadlock' section.

NOTE: Precisely speaking, a dependency is one between releasing a lock
and releasing another lock as described in 'What causes deadlock'
section. However from now on, we will describe a dependency as if it's
one between a lock and another lock for simplicity. Then 'A -> B' can be
described as a dependency between lock A and lock B.

We already checked how a problematic set of dependencies causes a
deadlock in 'What causes deadlock' section. This time let's check if a
deadlock or its possibility can be detected using a problematic set of
dependencies. Assume that 'A -> B', 'B -> E' and 'E -> A' were added in
the sequence into graph. Then the graph finally will be,

 -> A -> B -> E -
/                \
\                /
 ----------------

where A, B and E are different lock classes.

>From adding three dependencies, a cycle was created which means, by
definition of dependency, the situation 'lock E must be released to
release lock B which in turn must be released to release lock A which in
turn must be released to release lock E which in turn must be released
to release B and so on infinitely' can happen.

Once the situation happens, no lock can be released since any of them
can never meet each precondition. It's a deadlock. Lockdep can detect a
deadlock or its possibility with checking if a cycle was created after
adding each dependency into graph. This is how lockdep detects a
deadlock or its possibility.

CONCLUSION

Lockdep detects a deadlock or its possibility with checking if a cycle
was created after adding each dependency into graph.


==========
Limitation
==========

Limit to typical lock
---------------------

Limiting what lockdep has to consider to only ones satisfying the
following condition, the implementation of adding dependencies becomes
simple while its capacity for detection becomes limited. Typical lock
e.g. spin lock and mutex is the case. Let's check what pros and cons of
it are, in next section.

	A lock should be released within the context holding the lock.

CONCLUSION

Limiting what lockdep has to consider to typical lock e.g. spin lock and
mutex, the implmentation becomes simple while it has a limited capacity.


Pros from the limitation
------------------------

Given the limitation, when acquiring a lock, any lock being in
held_locks of the acquire context cannot be released if the lock to
acquire was not released yet. Yes. It's the exact case to add a new
dependency 'A -> B' into graph, where lock A represents each lock being
in held_locks and lock B represents the lock to acquire.

For example, only considering typical lock,

	PROCESS X
	--------------
	acquire A

	acquire B -> add a dependency 'A -> B'

	acquire C -> add a dependency 'B -> C'

	release C

	release B

	release A

where A, B and C are different lock classes.

When acquiring lock A, there's nothing in held_locks of PROCESS X thus
no dependency is added. When acquiring lock B, lockdep detects and adds
a new dependency 'A -> B' between lock A being in held_locks and lock B.
And when acquiring lock C, lockdep also adds another dependency 'B -> C'
for same reason. They are added when acquiring each lock, simply.

NOTE: Even though every lock being in held_locks depends on the lock to
acquire, lockdep does not add all dependencies between them because all
of them can be covered by other dependencies except one dependency
between the lock on top of held_locks and the lock to acquire, which
must be added.

Besides, we can expect several advantages from the limitation.

1. Any lock being in held_locks cannot be released unconditionally if
   the context is stuck, thus we can easily identify a dependency when
   acquiring a lock.

2. Considering only locks being in local held_locks of a single context
   makes some races avoidable, even though it fails of course when
   modifying its global dependency graph.

3. To build a dependency graph, lockdep only needs to keep locks not
   released yet. However relaxing the limitation, it might need to keep
   even locks already released, additionally. See 'Crossrelease' section.

CONCLUSION

Given the limitation, the implementation becomes simple and efficient.


Cons from the limitation
------------------------

Given the limitation, lockdep is applicable only to typical lock. For
example, page lock for page access or completion for synchronization
cannot play with lockdep having the limitation. However since page lock
or completion also causes a deadlock, it would be better to detect a
deadlock or its possibility even for them.

Can we detect deadlocks below with lockdep having the limitation?

Example 1:

	PROCESS X	PROCESS Y
	--------------	--------------
	mutext_lock A
			lock_page B
	lock_page B
			mutext_lock A // DEADLOCK
	unlock_page B
			mutext_unlock A
	mutex_unlock A
			unlock_page B

where A and B are different lock classes.

No, we cannot.

Example 2:

	PROCESS X	PROCESS Y	PROCESS Z
	--------------	--------------	--------------
			mutex_lock A
	lock_page B
			lock_page B
					mutext_lock A // DEADLOCK
					mutext_unlock A

					unlock_page B held by X
			unlock_page B
			mutex_unlock A

where A and B are different lock classes.

No, we cannot.

Example 3:

	PROCESS X	PROCESS Y
	--------------	--------------
			mutex_lock A
	mutex_lock A
	mutex_unlock A
			wait_for_complete B // DEADLOCK
	complete B
			mutex_unlock A

where A is a lock class and B is a completion variable.

No, we cannot.

CONCLUSION

Given the limitation, lockdep cannot detect a deadlock or its
possibility caused by page lock or completion.


==============
Generalization
==============

Relax the limitation
--------------------

Detecting and adding new dependencies into graph is very important for
lockdep to work because adding a dependency means adding a chance to
check if it causes a deadlock. More dependencies lockdep adds, more
throughly it can work. Therefore Lockdep has to do its best to add as
many true dependencies as possible.

Relaxing the limitation, lockdep can add additional dependencies since
it makes lockdep deal with additional ones creating the dependencies e.g.
page lock or completion, which might be released in any context. Even so,
it needs to be noted that behaviors adding dependencies created by
typical lock don't need to be changed at all.

For example, only considering typical lock, lockdep builds a graph like,

A -> B -        -> F -> G
        \      /
         -> E -        -> L
        /      \      /
C -> D -        -> H -
                      \
                       -> I -> K
                      /
                   J -

where A, B,..., L are different lock classes, and upper case letters
represent typical lock.

After the relaxing, the graph will have additional dependencies like,

A -> B -        -> F -> G
        \      /
         -> E -        -> L -> c
        /      \      /
C -> D -        -> H -
               /      \
            a -        -> I -> K
                      /
              b -> J -

where a, b, c, A, B,..., L are different lock classes, and upper case
letters represent typical lock while lower case letters represent
non-typical lock e.g. page lock and completion.

However, it might suffer performance degradation since relaxing the
limitation with which design and implementation of lockdep become
efficient might introduce inefficiency inevitably. Each option, that is,
strong detection or efficient detection has its pros and cons, thus the
right of choice between two options should be given to users.

Choosing efficient detection, lockdep only deals with locks satisfying,

	A lock should be released within the context holding the lock.

Choosing strong detection, lockdep deals with any locks satisfying,

	A lock can be released in any context.

In the latter, of course, some contexts are not allowed if they
themselves cause a deadlock. For example, acquiring a lock in irq-safe
context before releasing the lock in irq-unsafe context is not allowed,
which after all ends in a cycle of a dependency chain, meaning a
deadlock. Otherwise, any contexts are allowed to release it.

CONCLUSION

Relaxing the limitation, lockdep adds additional dependencies and gets
additional chances to check if they cause a deadlock. It makes lockdep
additionally deal with what might be released in any context.


============
Crossrelease
============

Introduce crossrelease
----------------------

To allow lockdep to add additional dependencies created by what might be
released in any context, which we call 'crosslock', it's necessary to
introduce a new feature which makes it possible to identify and add the
dependencies. We call the feature 'crossrelease'. Crossrelease feature
has to do,

1. Identify a new dependency created by crosslock.
2. Add the dependency into graph when identifying it.

That's all. Once a meaningful dependency is added into graph, lockdep
will work with the graph as it did. So the most important thing to do is
to identify a dependency created by crosslock. Remind what a dependency
is. For example, Lock A depends on lock B if 'lock A cannot be released
if lock B isn't released'. See 'What causes deadlock' section.

By definition, a lock depends on every lock having been added into
held_locks in the lock's release context since the lock was acquired,
because the lock cannot be released if the release context is stuck by
any of dependent locks, not released. So lockdep should technically
consider release contexts of locks to identify dependencies.

It's no matter of course to typical lock because acquire context is same
as release context for typical lock, which means lockdep would work with
considering only acquire contexts for typical lock. However, for
crosslock, lockdep cannot identify release context and any dependency
until the crosslock will be actually released.

Regarding crosslock, lockdep has to record all history by queueing all
locks potentially creating dependencies so that real dependencies can be
added using the history recorded when identifying release context. We
call it 'commit', that is, to add dependencies in batches. See
'Introduce commit' section.

Of course, some actual deadlocks caused by crosslock cannot be detected
at the time it happened, because the deadlocks cannot be indentified and
detected until the crosslock will be actually released. But this way
deadlock possibility can be detected and it's worth just possibility
detection of deadlock. See 'What lockdep does' section.

CONCLUSION

With crossrelease feature, lockdep can works with what might be released
in any context, namely, crosslock.


Introduce commit
----------------

Crossrelease feature names it 'commit' to identify and add dependencies
into graph in batches. Lockdep is already doing what commit does when
acquiring a lock, for typical lock. However, that way must be changed
for crosslock so that it identifies the crosslock's release context
first and then does commit.

The main reason why lockdep performs additional step, namely commit, for
crosslock is that some dependencies by crosslock cannot be identified
until the crosslock's release context is eventually identified, though
some other dependencies by crosslock can. There are four kinds of
dependencies to consider.

1. 'typical lock A -> typical lock B' dependency

   Just when acquiring lock B, lockdep can identify the dependency
   between lock A and lock B as it did. Commit is unnecessary.

2. 'typical lock A -> crosslock b' dependency

   Just when acquiring crosslock b, lockdep can identify the dependency
   between lock A and crosslock B as well. Commit is unnecessary, too.

3. 'crosslock a -> typical lock B' dependency

   When acquiring lock B, lockdep cannot identify the dependency. It can
   be identified only when crosslock a is released. Commit is necessary.

4. 'crosslock a -> crosslock b' dependency

   Creating this kind of dependency directly is unnecessary since it can
   be covered by other kinds of dependencies.

Lockdep works without commit during dealing with only typical locks.
However, it needs to perform commit step, once at least one crosslock is
acquired, until all crosslocks in progress are released. Introducing
commit, lockdep performs three steps i.e. acquire, commit and release.
What lockdep should do in each step is like,

1. Acquire

   1) For typical lock

	Lockdep does what it originally does and queues the lock so
	that lockdep can check dependencies using it at commit step.

   2) For crosslock

	The crosslock is added to a global linked list so that lockdep
	can check dependencies using it at commit step.

2. Commit

   1) For typical lock

	N/A.

   2) For crosslock

	Lockdep checks and adds dependencies using data saved at acquire
	step, as if the dependencies were added without commit step.

3. Release

   1) For typical lock

	No change.

   2) For crosslock

	Lockdep just remove the crosslock from the global linked list,
	to which it was added at acquire step.

CONCLUSION

Lockdep can detect a deadlock or its possibility caused by what might be
released in any context, using commit step, where it checks and adds
dependencies in batches.


==============
Implementation
==============

Data structures
---------------

Crossrelease feature introduces two main data structures.

1. pend_lock (or plock)

   This is an array embedded in task_struct, for keeping locks queued so
   that real dependencies can be added using them at commit step. So
   this data can be accessed locklessly within the owner context. The
   array is filled when acquiring a typical lock and consumed when doing
   commit. And it's managed in circular manner.

2. cross_lock (or xlock)

   This is a global linked list, for keeping all crosslocks in progress.
   The list grows when acquiring a crosslock and is shrunk when
   releasing the crosslock. lockdep_init_map_crosslock() should be used
   to initialize a crosslock instance instead of lockdep_init_map() so
   that lockdep can recognize it as crosslock.

CONCLUSION

Crossrelease feature uses two main data structures.

1. A pend_lock array for queueing typical locks in circular manner.
2. A cross_lock linked list for managing crosslocks in progress.


How crossrelease works
----------------------

Let's take look at how crossrelease feature works step by step, starting
from how lockdep works without crossrelease feaure.

For example, the below is how lockdep works for typical lock.

	RELEASE CONTEXT of A (= ACQUIRE CONTEXT of A)
	--------------------
	acquire A

	acquire B -> add a dependency 'A -> B'

	acquire C -> add a dependency 'B -> C'

	release C

	release B

	release A

where A, B and C are different lock classes, and upper case letters
represent typical lock.

After adding 'A -> B', the dependency graph will be,

A -> B

where A and B are different lock classes, and upper case letters
represent typical lock.

And after adding 'B -> C', the graph will be,

A -> B -> C

where A, B and C are different lock classes, and upper case letters
represent typical lock.

What if applying commit on typical locks? It's not necessary for typical
lock. Just for showing what commit does.

	RELEASE CONTEXT of A (= ACQUIRE CONTEXT of A)
	--------------------
	acquire A -> mark A as started (nothing before, no queueing)

	acquire B -> mark B as started and queue B

	acquire C -> mark C as started and queue C

	release C -> commit C (nothing queued since C started)

	release B -> commit B -> add a dependency 'B -> C'

	release A -> commit A -> add dependencies 'A -> B' and 'A -> C'

where A, B and C are different lock classes, and upper case letters
represent typical lock.

After doing commit A, B and C, the dependency graph becomes like,

A -> B -> C

where A, B and C are different lock classes, and upper case letters
represent typical lock.

NOTE: A dependency 'A -> C' is optimized out.

Here we can see the final graph is same as the graph built without
commit. Of course the former way leads to finish building the graph
earlier than the latter way, which means we can detect a deadlock or its
possibility sooner. So the former way would be prefered if possible. But
we cannot avoid using the latter way using commit, for crosslock.

Let's look at how commit works for crosslock.

	RELEASE CONTEXT of a	ACQUIRE CONTEXT of a
	--------------------	--------------------
				acquire a -> mark a as started

	(serialized by some means e.g. barrier)

	acquire D -> queue D
				acquire B -> queue B
	release D
				acquire C -> add 'B -> C' and queue C
	acquire E -> queue E
				acquire D -> add 'C -> D' and queue D
	release E
				release D
	release a -> commit a -> add 'a -> D' and 'a -> E'
				release C

				release B

where a, B,..., E are different lock classes, and upper case letters
represent typical lock while lower case letters represent crosslock.

When acquiring crosslock a, no dependency can be added since there's
nothing in the held_locks. However, crossrelease feature marks the
crosslock as started, which means all locks to acquire from now are
candidates which might create new dependencies later when identifying
release context.

When acquiring lock B, lockdep does what it originally does for typical
lock and additionally queues the lock for later commit to refer to
because it might be a dependent lock of the crosslock. It does same
thing on lock C, D and E. And then two dependencies 'a -> D' and 'a -> E'
are added when identifying the release context, at commit step.

The final graph is, with crossrelease feature using commit,

B -> C -
        \
         -> D
        /
     a -
        \
         -> E

where a, B,..., E are different lock classes, and upper case letters
represent typical lock while lower case letters represent crosslock.

However, without crossrelease feature, the final graph will be,

B -> C -> D

where B and C are different lock classes, and upper case letters
represent typical lock.

The former graph has two more dependencies 'a -> D' and 'a -> E' giving
additional chances to check if they cause a deadlock. This way lockdep
can detect a deadlock or its possibility caused by crosslock. Again,
behaviors adding dependencies created by only typical locks are not
changed at all.

CONCLUSION

Crossrelease works using commit for crosslock, leaving behaviors adding
dependencies between only typical locks unchanged.


=============
Optimizations
=============

Avoid duplication
-----------------

Crossrelease feature uses a cache like what lockdep already uses for
dependency chains, but this time it's for caching one dependency like
'crosslock -> typical lock' crossing between two different context. Once
that dependency is cached, same dependency will never be added any more.
Even queueing unnecessary locks is also prevented based on the cache.

CONCLUSION

Crossrelease does not add any duplicate dependency.


Avoid lock contention
---------------------

To keep all typical locks for later use, crossrelease feature adopts a
local array embedded in task_struct, which makes accesses to arrays
lockless by forcing each array to be accessed only within each own
context. It's like how held_locks is accessed. Lockless implmentation is
important since typical locks are very frequently accessed.

CONCLUSION

Crossrelease avoids lock contection as far as possible.